Line data Source code
1 : /*
2 : * Copyright (c) 2016 Cisco and/or its affiliates.
3 : * Licensed under the Apache License, Version 2.0 (the "License");
4 : * you may not use this file except in compliance with the License.
5 : * You may obtain a copy of the License at:
6 : *
7 : * http://www.apache.org/licenses/LICENSE-2.0
8 : *
9 : * Unless required by applicable law or agreed to in writing, software
10 : * distributed under the License is distributed on an "AS IS" BASIS,
11 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : * See the License for the specific language governing permissions and
13 : * limitations under the License.
14 : */
15 :
16 : #include <lisp/lisp-cp/gid_dictionary.h>
17 :
18 : typedef struct
19 : {
20 : void *arg;
21 : ip_prefix_t src;
22 : foreach_subprefix_match_cb_t cb;
23 : union
24 : {
25 : gid_ip4_table_t *ip4_table;
26 : gid_ip6_table_t *ip6_table;
27 : };
28 : } sfib_entry_arg_t;
29 :
30 : static u32 ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key);
31 :
32 : static u32 ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key);
33 :
34 : static int
35 0 : foreach_sfib4_subprefix (BVT (clib_bihash_kv) * kvp, void *arg)
36 : {
37 0 : sfib_entry_arg_t *a = arg;
38 0 : u32 ip = (u32) kvp->key[0];
39 : ip4_address_t *mask;
40 0 : u8 plen = ip_prefix_len (&a->src);
41 :
42 0 : ASSERT (plen <= 32);
43 0 : mask = &a->ip4_table->ip4_fib_masks[plen];
44 :
45 0 : u32 src_ip = ip_prefix_v4 (&a->src).as_u32;
46 0 : src_ip &= mask->as_u32;
47 0 : ip &= mask->as_u32;
48 :
49 0 : if (src_ip == ip)
50 : {
51 : /* found sub-prefix of src prefix */
52 0 : (a->cb) (kvp->value, a->arg);
53 : }
54 0 : return (BIHASH_WALK_CONTINUE);
55 : }
56 :
57 : static void
58 0 : gid_dict_foreach_ip4_subprefix (gid_dictionary_t * db, u32 vni,
59 : ip_prefix_t * src, ip_prefix_t * dst,
60 : foreach_subprefix_match_cb_t cb, void *arg)
61 : {
62 : u32 sfi;
63 : gid_ip4_table_t *sfib4;
64 : sfib_entry_arg_t a;
65 :
66 0 : sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
67 0 : if (GID_LOOKUP_MISS == sfi)
68 0 : return;
69 :
70 0 : sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);
71 :
72 0 : a.arg = arg;
73 0 : a.cb = cb;
74 0 : a.src = src[0];
75 0 : a.ip4_table = sfib4;
76 :
77 0 : BV (clib_bihash_foreach_key_value_pair) (&sfib4->ip4_lookup_table,
78 : foreach_sfib4_subprefix, &a);
79 : }
80 :
81 : static int
82 0 : foreach_sfib6_subprefix (BVT (clib_bihash_kv) * kvp, void *arg)
83 : {
84 0 : sfib_entry_arg_t *a = arg;
85 : ip6_address_t ip;
86 : ip6_address_t *mask;
87 0 : u8 plen = ip_prefix_len (&a->src);
88 :
89 0 : mask = &a->ip6_table->ip6_fib_masks[plen];
90 0 : ip.as_u64[0] = kvp->key[0];
91 0 : ip.as_u64[1] = kvp->key[1];
92 :
93 0 : if (ip6_address_is_equal_masked (&ip_prefix_v6 (&a->src), &ip, mask))
94 : {
95 : /* found sub-prefix of src prefix */
96 0 : (a->cb) (kvp->value, a->arg);
97 : }
98 0 : return (BIHASH_WALK_CONTINUE);
99 : }
100 :
101 : static void
102 0 : gid_dict_foreach_ip6_subprefix (gid_dictionary_t * db, u32 vni,
103 : ip_prefix_t * src, ip_prefix_t * dst,
104 : foreach_subprefix_match_cb_t cb, void *arg)
105 : {
106 : u32 sfi;
107 : gid_ip6_table_t *sfib6;
108 : sfib_entry_arg_t a;
109 :
110 0 : sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
111 0 : if (GID_LOOKUP_MISS == sfi)
112 0 : return;
113 :
114 0 : sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);
115 :
116 0 : a.arg = arg;
117 0 : a.cb = cb;
118 0 : a.src = src[0];
119 0 : a.ip6_table = sfib6;
120 :
121 0 : BV (clib_bihash_foreach_key_value_pair) (&sfib6->ip6_lookup_table,
122 : foreach_sfib6_subprefix, &a);
123 : }
124 :
125 : void
126 0 : gid_dict_foreach_subprefix (gid_dictionary_t * db, gid_address_t * eid,
127 : foreach_subprefix_match_cb_t cb, void *arg)
128 : {
129 0 : ip_prefix_t *ippref = &gid_address_sd_dst_ippref (eid);
130 :
131 0 : if (AF_IP4 == ip_prefix_version (ippref))
132 0 : gid_dict_foreach_ip4_subprefix (db, gid_address_vni (eid),
133 : &gid_address_sd_src_ippref (eid),
134 : &gid_address_sd_dst_ippref (eid), cb,
135 : arg);
136 : else
137 0 : gid_dict_foreach_ip6_subprefix (db, gid_address_vni (eid),
138 : &gid_address_sd_src_ippref (eid),
139 : &gid_address_sd_dst_ippref (eid), cb,
140 : arg);
141 0 : }
142 :
143 : void
144 0 : gid_dict_foreach_l2_arp_ndp_entry (gid_dictionary_t * db,
145 : BV (clib_bihash_foreach_key_value_pair_cb)
146 : cb, void *ht)
147 : {
148 0 : gid_l2_arp_ndp_table_t *tab = &db->arp_ndp_table;
149 0 : BV (clib_bihash_foreach_key_value_pair) (&tab->arp_ndp_lookup_table, cb,
150 : ht);
151 0 : }
152 :
153 : static void
154 0 : make_mac_sd_key (BVT (clib_bihash_kv) * kv, u32 vni, u8 src_mac[6],
155 : u8 dst_mac[6])
156 : {
157 0 : kv->key[0] = (u64) vni;
158 0 : kv->key[1] = mac_to_u64 (dst_mac);
159 0 : kv->key[2] = src_mac ? mac_to_u64 (src_mac) : (u64) 0;
160 0 : }
161 :
162 : static u32
163 0 : mac_sd_lookup (gid_mac_table_t * db, u32 vni, u8 * dst, u8 * src)
164 : {
165 : int rv;
166 : BVT (clib_bihash_kv) kv, value;
167 :
168 0 : make_mac_sd_key (&kv, vni, src, dst);
169 0 : rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv, &value);
170 :
171 : /* no match, try with src 0, catch all for dst */
172 0 : if (rv != 0)
173 : {
174 0 : kv.key[2] = 0;
175 0 : rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv,
176 : &value);
177 0 : if (rv == 0)
178 0 : return value.value;
179 : }
180 : else
181 0 : return value.value;
182 :
183 0 : return GID_LOOKUP_MISS;
184 : }
185 :
186 : static u32
187 10 : ip4_lookup_exact_match (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
188 : {
189 : int rv;
190 : BVT (clib_bihash_kv) kv, value;
191 :
192 : ip4_address_t *mask;
193 :
194 10 : mask = &db->ip4_fib_masks[ip_prefix_len (key)];
195 :
196 10 : kv.key[0] = ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
197 10 : kv.key[1] = 0;
198 10 : kv.key[2] = 0;
199 :
200 10 : rv = BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
201 10 : if (rv == 0)
202 8 : return value.value;
203 :
204 2 : return GID_LOOKUP_MISS;
205 : }
206 :
207 : static u32
208 15 : ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
209 : {
210 : int i, len;
211 : int rv;
212 : BVT (clib_bihash_kv) kv, value;
213 :
214 15 : len = vec_len (db->ip4_prefix_lengths_in_search_order);
215 :
216 18 : for (i = 0; i < len; i++)
217 : {
218 13 : int dst_address_length = db->ip4_prefix_lengths_in_search_order[i];
219 : ip4_address_t *mask;
220 :
221 13 : ASSERT (dst_address_length >= 0 && dst_address_length <= 32);
222 :
223 13 : mask = &db->ip4_fib_masks[dst_address_length];
224 :
225 13 : kv.key[0] =
226 13 : ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
227 13 : kv.key[1] = 0;
228 13 : kv.key[2] = 0;
229 :
230 : rv =
231 13 : BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
232 13 : if (rv == 0)
233 10 : return value.value;
234 : }
235 :
236 5 : return GID_LOOKUP_MISS;
237 : }
238 :
239 : static u32
240 0 : ip6_lookup_exact_match (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
241 : {
242 : int rv;
243 : BVT (clib_bihash_kv) kv, value;
244 :
245 : ip6_address_t *mask;
246 0 : mask = &db->ip6_fib_masks[ip_prefix_len (key)];
247 :
248 0 : kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
249 0 : kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
250 0 : kv.key[2] = (u64) vni;
251 :
252 0 : rv = BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
253 0 : if (rv == 0)
254 0 : return value.value;
255 :
256 0 : return GID_LOOKUP_MISS;
257 : }
258 :
259 : static u32
260 0 : ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
261 : {
262 : int i, len;
263 : int rv;
264 : BVT (clib_bihash_kv) kv, value;
265 :
266 0 : len = vec_len (db->ip6_prefix_lengths_in_search_order);
267 :
268 0 : for (i = 0; i < len; i++)
269 : {
270 0 : int dst_address_length = db->ip6_prefix_lengths_in_search_order[i];
271 : ip6_address_t *mask;
272 :
273 0 : ASSERT (dst_address_length >= 0 && dst_address_length <= 128);
274 :
275 0 : mask = &db->ip6_fib_masks[dst_address_length];
276 :
277 0 : kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
278 0 : kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
279 0 : kv.key[2] = (u64) vni;
280 :
281 : rv =
282 0 : BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
283 0 : if (rv == 0)
284 0 : return value.value;
285 : }
286 :
287 0 : return GID_LOOKUP_MISS;
288 : }
289 :
290 : static u32
291 13 : ip_sd_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst,
292 : ip_prefix_t * src)
293 : {
294 : u32 sfi;
295 : gid_ip4_table_t *sfib4;
296 : gid_ip6_table_t *sfib6;
297 :
298 13 : switch (ip_prefix_version (dst))
299 : {
300 13 : case AF_IP4:
301 13 : sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
302 13 : if (GID_LOOKUP_MISS != sfi)
303 8 : sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);
304 : else
305 5 : return GID_LOOKUP_MISS;
306 :
307 8 : if (!src)
308 : {
309 : ip_prefix_t sp;
310 6 : clib_memset (&sp, 0, sizeof (sp));
311 6 : return ip4_lookup_exact_match (sfib4, 0, &sp);
312 : }
313 : else
314 2 : return ip4_lookup (sfib4, 0, src);
315 :
316 : break;
317 0 : case AF_IP6:
318 0 : sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
319 0 : if (GID_LOOKUP_MISS != sfi)
320 0 : sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);
321 : else
322 0 : return GID_LOOKUP_MISS;
323 :
324 0 : if (!src)
325 : {
326 : ip_prefix_t sp;
327 0 : clib_memset (&sp, 0, sizeof (sp));
328 0 : ip_prefix_version (&sp) = AF_IP6;
329 0 : return ip6_lookup_exact_match (sfib6, 0, &sp);
330 : }
331 : else
332 0 : return ip6_lookup (sfib6, 0, src);
333 :
334 : break;
335 0 : default:
336 0 : clib_warning ("address type %d not supported!",
337 : ip_prefix_version (dst));
338 0 : break;
339 : }
340 0 : return GID_LOOKUP_MISS;
341 : }
342 :
343 : static void
344 0 : make_arp_ndp_key (BVT (clib_bihash_kv) * kv, u32 bd, ip_address_t * addr)
345 : {
346 0 : kv->key[0] = ((u64) bd << 32) | (u32) ip_addr_version (addr);
347 0 : if (ip_addr_version (addr) == AF_IP4)
348 : {
349 0 : kv->key[1] = (u64) ip_addr_v4 (addr).as_u32;
350 0 : kv->key[2] = (u64) 0;
351 : }
352 : else
353 : {
354 0 : kv->key[1] = (u64) ip_addr_v6 (addr).as_u64[0];
355 0 : kv->key[2] = (u64) ip_addr_v6 (addr).as_u64[1];
356 : }
357 0 : }
358 :
359 : static void
360 0 : make_nsh_key (BVT (clib_bihash_kv) * kv, u32 vni, u32 spi, u8 si)
361 : {
362 0 : kv->key[0] = (u64) vni;
363 0 : kv->key[1] = (u64) spi;
364 0 : kv->key[2] = (u64) si;
365 0 : }
366 :
367 : static u64
368 0 : arp_ndp_lookup (gid_l2_arp_ndp_table_t * db, u32 bd, ip_address_t * key)
369 : {
370 : int rv;
371 : BVT (clib_bihash_kv) kv, value;
372 :
373 0 : make_arp_ndp_key (&kv, bd, key);
374 0 : rv = BV (clib_bihash_search_inline_2) (&db->arp_ndp_lookup_table, &kv,
375 : &value);
376 :
377 0 : if (rv == 0)
378 0 : return value.value;
379 :
380 0 : return GID_LOOKUP_MISS_L2;
381 : }
382 :
383 : static u32
384 0 : nsh_lookup (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si)
385 : {
386 : int rv;
387 : BVT (clib_bihash_kv) kv, value;
388 :
389 0 : make_nsh_key (&kv, vni, spi, si);
390 0 : rv = BV (clib_bihash_search_inline_2) (&db->nsh_lookup_table, &kv, &value);
391 :
392 0 : if (rv == 0)
393 0 : return value.value;
394 :
395 0 : return GID_LOOKUP_MISS;
396 : }
397 :
398 : u64
399 11 : gid_dictionary_lookup (gid_dictionary_t * db, gid_address_t * key)
400 : {
401 11 : switch (gid_address_type (key))
402 : {
403 11 : case GID_ADDR_IP_PREFIX:
404 11 : return ip_sd_lookup (db, gid_address_vni (key),
405 : &gid_address_ippref (key), 0);
406 0 : case GID_ADDR_MAC:
407 0 : return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
408 0 : gid_address_mac (key), 0);
409 0 : case GID_ADDR_SRC_DST:
410 0 : switch (gid_address_sd_dst_type (key))
411 : {
412 0 : case FID_ADDR_IP_PREF:
413 0 : return ip_sd_lookup (db, gid_address_vni (key),
414 : &gid_address_sd_dst_ippref (key),
415 : &gid_address_sd_src_ippref (key));
416 : break;
417 0 : case FID_ADDR_MAC:
418 0 : return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
419 0 : gid_address_sd_dst_mac (key),
420 0 : gid_address_sd_src_mac (key));
421 : break;
422 0 : default:
423 0 : clib_warning ("Source/Dest address type %d not supported!",
424 : gid_address_sd_dst_type (key));
425 0 : break;
426 : }
427 0 : break;
428 0 : case GID_ADDR_ARP:
429 : case GID_ADDR_NDP:
430 0 : return arp_ndp_lookup (&db->arp_ndp_table, gid_address_arp_ndp_bd (key),
431 : &gid_address_arp_ndp_ip (key));
432 0 : case GID_ADDR_NSH:
433 0 : return nsh_lookup (&db->nsh_table, gid_address_vni (key),
434 0 : gid_address_nsh_spi (key), gid_address_nsh_si (key));
435 0 : default:
436 0 : clib_warning ("address type %d not supported!", gid_address_type (key));
437 0 : break;
438 : }
439 0 : return GID_LOOKUP_MISS;
440 : }
441 :
442 : u32
443 2 : gid_dictionary_sd_lookup (gid_dictionary_t * db, gid_address_t * dst,
444 : gid_address_t * src)
445 : {
446 2 : switch (gid_address_type (dst))
447 : {
448 2 : case GID_ADDR_IP_PREFIX:
449 2 : return ip_sd_lookup (db, gid_address_vni (dst),
450 : &gid_address_ippref (dst),
451 : &gid_address_ippref (src));
452 0 : case GID_ADDR_MAC:
453 0 : return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
454 0 : gid_address_mac (dst), gid_address_mac (src));
455 0 : case GID_ADDR_SRC_DST:
456 0 : switch (gid_address_sd_dst_type (dst))
457 : {
458 0 : case FID_ADDR_IP_PREF:
459 0 : return ip_sd_lookup (db, gid_address_vni (dst),
460 : &gid_address_sd_dst_ippref (dst),
461 : &gid_address_sd_src_ippref (dst));
462 : break;
463 0 : case FID_ADDR_MAC:
464 0 : return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
465 0 : gid_address_sd_dst_mac (dst),
466 0 : gid_address_sd_src_mac (dst));
467 : break;
468 0 : default:
469 0 : clib_warning ("Source/Dest address type %d not supported!",
470 : gid_address_sd_dst_type (dst));
471 0 : break;
472 : }
473 0 : break;
474 0 : case GID_ADDR_NSH:
475 0 : return gid_dictionary_lookup (db, dst);
476 : break;
477 0 : default:
478 0 : clib_warning ("address type %d not supported!", gid_address_type (dst));
479 0 : break;
480 : }
481 0 : return GID_LOOKUP_MISS;
482 : }
483 :
484 : static void
485 8 : ip4_compute_prefix_lengths_in_search_order (gid_ip4_table_t * db)
486 : {
487 : int i;
488 8 : vec_reset_length (db->ip4_prefix_lengths_in_search_order);
489 : /* Note: bitmap reversed so this is in fact a longest prefix match */
490 :
491 : /* *INDENT-OFF* */
492 14 : clib_bitmap_foreach (i, db->ip4_non_empty_dst_address_length_bitmap)
493 : {
494 6 : int dst_address_length = 32 - i;
495 6 : vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
496 : }
497 : /* *INDENT-ON* */
498 :
499 8 : }
500 :
501 : static u32
502 8 : add_del_ip4_key (gid_ip4_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
503 : u8 is_add)
504 : {
505 : BVT (clib_bihash_kv) kv, value;
506 8 : u32 old_val = ~0;
507 : ip4_address_t key;
508 8 : u8 plen = ip_prefix_len (pref);
509 :
510 8 : clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
511 8 : key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
512 8 : if (is_add)
513 : {
514 4 : db->ip4_non_empty_dst_address_length_bitmap =
515 4 : clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
516 4 : 32 - plen, 1);
517 4 : ip4_compute_prefix_lengths_in_search_order (db);
518 :
519 4 : db->ip4_prefix_len_refcount[plen]++;
520 : }
521 : else
522 : {
523 4 : ASSERT (db->ip4_prefix_len_refcount[plen] != 0);
524 :
525 4 : db->ip4_prefix_len_refcount[plen]--;
526 :
527 4 : if (db->ip4_prefix_len_refcount[plen] == 0)
528 : {
529 4 : db->ip4_non_empty_dst_address_length_bitmap =
530 4 : clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
531 4 : 32 - plen, 0);
532 4 : ip4_compute_prefix_lengths_in_search_order (db);
533 : }
534 : }
535 :
536 8 : kv.key[0] = ((u64) vni << 32) | key.as_u32;
537 8 : kv.key[1] = 0;
538 8 : kv.key[2] = 0;
539 :
540 8 : if (BV (clib_bihash_search) (&db->ip4_lookup_table, &kv, &value) == 0)
541 4 : old_val = value.value;
542 :
543 8 : if (!is_add)
544 : {
545 4 : BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
546 4 : db->count--;
547 : }
548 : else
549 : {
550 4 : kv.value = val;
551 4 : BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
552 4 : db->count++;
553 : }
554 8 : return old_val;
555 : }
556 :
557 : static void
558 577 : ip4_lookup_init (gid_ip4_table_t * db)
559 : {
560 577 : BVT (clib_bihash_init2_args) _a, *a = &_a;
561 : uword i;
562 :
563 577 : clib_memset (db->ip4_prefix_len_refcount, 0,
564 : sizeof (db->ip4_prefix_len_refcount));
565 :
566 19618 : for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
567 : {
568 : u32 m;
569 :
570 19041 : if (i < 32)
571 18464 : m = pow2_mask (i) << (32 - i);
572 : else
573 577 : m = ~0;
574 19041 : db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
575 : }
576 577 : if (db->ip4_lookup_table_nbuckets == 0)
577 577 : db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
578 :
579 577 : db->ip4_lookup_table_nbuckets =
580 577 : 1 << max_log2 (db->ip4_lookup_table_nbuckets);
581 :
582 577 : if (db->ip4_lookup_table_size == 0)
583 577 : db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
584 :
585 : /*
586 : * Danger Will Robinson, Danger! gid_ip4_table_t's are allocated from
587 : * a pool. They MUST NOT be listed on the clib_all_bihashes list...
588 : */
589 577 : memset (a, 0, sizeof (*a));
590 577 : a->h = &db->ip4_lookup_table;
591 577 : a->name = "LISP ip4 lookup table";
592 577 : a->nbuckets = db->ip4_lookup_table_nbuckets;
593 577 : a->memory_size = db->ip4_lookup_table_size;
594 577 : a->dont_add_to_all_bihash_list = 1; /* See comment above */
595 :
596 577 : BV (clib_bihash_init2) (a);
597 577 : }
598 :
599 : static u32
600 4 : add_del_sd_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
601 : ip_prefix_t * src_pref, u32 val, u8 is_add)
602 : {
603 4 : u32 sfi, old_val = ~0;
604 : gid_ip4_table_t *sfib;
605 :
606 4 : sfi = ip4_lookup_exact_match (&db->dst_ip4_table, vni, dst_pref);
607 :
608 4 : if (is_add)
609 : {
610 2 : if (GID_LOOKUP_MISS == sfi)
611 : {
612 2 : pool_get (db->src_ip4_table_pool, sfib);
613 2 : ip4_lookup_init (sfib);
614 2 : add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref,
615 2 : sfib - db->src_ip4_table_pool, is_add);
616 2 : if (src_pref)
617 0 : add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
618 : else
619 : {
620 : ip_prefix_t sp;
621 2 : clib_memset (&sp, 0, sizeof (sp));
622 2 : add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
623 : }
624 : }
625 : else
626 : {
627 0 : ASSERT (!pool_is_free_index (db->src_ip4_table_pool, sfi));
628 0 : sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
629 0 : if (src_pref)
630 : {
631 0 : old_val = ip4_lookup_exact_match (sfib, 0, src_pref);
632 0 : add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
633 : }
634 : else
635 : {
636 : ip_prefix_t sp;
637 0 : clib_memset (&sp, 0, sizeof (sp));
638 : old_val =
639 0 : add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
640 : }
641 : }
642 : }
643 : else
644 : {
645 2 : if (GID_LOOKUP_MISS != sfi)
646 : {
647 2 : sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
648 2 : if (src_pref)
649 0 : old_val = add_del_ip4_key (sfib, 0, src_pref, 0, is_add);
650 : else
651 : {
652 : ip_prefix_t sp;
653 2 : clib_memset (&sp, 0, sizeof (sp));
654 2 : old_val = add_del_ip4_key (sfib, 0, &sp, 0, is_add);
655 : }
656 :
657 2 : if (sfib->count == 0)
658 2 : add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref, 0, is_add);
659 : }
660 : else
661 0 : clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
662 : dst_pref);
663 : }
664 4 : return old_val;
665 : }
666 :
667 : static void
668 0 : ip6_compute_prefix_lengths_in_search_order (gid_ip6_table_t * db)
669 : {
670 : int i;
671 0 : vec_reset_length (db->ip6_prefix_lengths_in_search_order);
672 : /* Note: bitmap reversed so this is in fact a longest prefix match */
673 :
674 : /* *INDENT-OFF* */
675 0 : clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap)
676 : {
677 0 : int dst_address_length = 128 - i;
678 0 : vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
679 : }
680 : /* *INDENT-ON* */
681 0 : }
682 :
683 : static u32
684 0 : add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
685 : u8 is_add)
686 : {
687 : BVT (clib_bihash_kv) kv, value;
688 0 : u32 old_val = ~0;
689 : ip6_address_t key;
690 0 : u8 plen = ip_prefix_len (pref);
691 :
692 0 : clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
693 0 : ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
694 0 : if (is_add)
695 : {
696 0 : db->ip6_non_empty_dst_address_length_bitmap =
697 0 : clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
698 0 : 128 - plen, 1);
699 0 : ip6_compute_prefix_lengths_in_search_order (db);
700 0 : db->ip6_prefix_len_refcount[plen]++;
701 : }
702 : else
703 : {
704 0 : ASSERT (db->ip6_prefix_len_refcount[plen] != 0);
705 :
706 0 : db->ip6_prefix_len_refcount[plen]--;
707 :
708 0 : if (db->ip6_prefix_len_refcount[plen] == 0)
709 : {
710 0 : db->ip6_non_empty_dst_address_length_bitmap =
711 0 : clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
712 0 : 128 - plen, 0);
713 0 : ip6_compute_prefix_lengths_in_search_order (db);
714 : }
715 : }
716 :
717 0 : kv.key[0] = key.as_u64[0];
718 0 : kv.key[1] = key.as_u64[1];
719 0 : kv.key[2] = (u64) vni;
720 : // kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);
721 :
722 0 : if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
723 0 : old_val = value.value;
724 :
725 0 : if (!is_add)
726 : {
727 0 : BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
728 0 : db->count--;
729 : }
730 : else
731 : {
732 0 : kv.value = val;
733 0 : BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
734 0 : db->count++;
735 : }
736 0 : return old_val;
737 : }
738 :
739 : static u32
740 0 : add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
741 : u32 val, u8 is_add)
742 : {
743 : BVT (clib_bihash_kv) kv, value;
744 0 : u32 old_val = ~0;
745 :
746 0 : make_mac_sd_key (&kv, vni, src_mac, dst_mac);
747 :
748 0 : if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
749 0 : old_val = value.value;
750 :
751 0 : if (!is_add)
752 : {
753 0 : BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
754 0 : db->count--;
755 : }
756 : else
757 : {
758 0 : kv.value = val;
759 0 : BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
760 0 : db->count++;
761 : }
762 0 : return old_val;
763 : }
764 :
765 : static void
766 575 : ip6_lookup_init (gid_ip6_table_t * db)
767 : {
768 : uword i;
769 575 : BVT (clib_bihash_init2_args) _a, *a = &_a;
770 :
771 575 : clib_memset (db->ip6_prefix_len_refcount, 0,
772 : sizeof (db->ip6_prefix_len_refcount));
773 :
774 74750 : for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
775 : {
776 : u32 j, i0, i1;
777 :
778 74175 : i0 = i / 32;
779 74175 : i1 = i % 32;
780 :
781 186875 : for (j = 0; j < i0; j++)
782 112700 : db->ip6_fib_masks[i].as_u32[j] = ~0;
783 :
784 74175 : if (i1)
785 71300 : db->ip6_fib_masks[i].as_u32[i0] =
786 71300 : clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
787 : }
788 :
789 575 : if (db->ip6_lookup_table_nbuckets == 0)
790 575 : db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
791 :
792 575 : db->ip6_lookup_table_nbuckets =
793 575 : 1 << max_log2 (db->ip6_lookup_table_nbuckets);
794 :
795 575 : if (db->ip6_lookup_table_size == 0)
796 575 : db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
797 :
798 : /*
799 : * Danger Will Robinson, Danger! gid_ip6_table_t's are allocated from
800 : * a pool. They MUST NOT be listed on the clib_all_bihashes list...
801 : */
802 575 : memset (a, 0, sizeof (*a));
803 575 : a->h = &db->ip6_lookup_table;
804 575 : a->name = "LISP ip6 lookup table";
805 575 : a->nbuckets = db->ip6_lookup_table_nbuckets;
806 575 : a->memory_size = db->ip6_lookup_table_size;
807 575 : a->dont_add_to_all_bihash_list = 1; /* See comment above */
808 :
809 575 : BV (clib_bihash_init2) (a);
810 575 : }
811 :
812 : static u32
813 0 : add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
814 : ip_prefix_t * src_pref, u32 val, u8 is_add)
815 : {
816 0 : u32 sfi, old_val = ~0;
817 : gid_ip6_table_t *sfib;
818 :
819 0 : sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);
820 :
821 0 : if (is_add)
822 : {
823 0 : if (GID_LOOKUP_MISS == sfi)
824 : {
825 0 : pool_get (db->src_ip6_table_pool, sfib);
826 0 : ip6_lookup_init (sfib);
827 0 : add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
828 0 : sfib - db->src_ip6_table_pool, is_add);
829 0 : if (src_pref)
830 0 : add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
831 : else
832 : {
833 : ip_prefix_t sp;
834 0 : clib_memset (&sp, 0, sizeof (sp));
835 0 : ip_prefix_version (&sp) = AF_IP6;
836 0 : add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
837 : }
838 : }
839 : else
840 : {
841 0 : ASSERT (!pool_is_free_index (db->src_ip6_table_pool, sfi));
842 0 : sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
843 0 : if (src_pref)
844 : {
845 0 : old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
846 0 : add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
847 : }
848 : else
849 : {
850 : ip_prefix_t sp;
851 0 : clib_memset (&sp, 0, sizeof (sp));
852 0 : ip_prefix_version (&sp) = AF_IP6;
853 : old_val =
854 0 : add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
855 : }
856 : }
857 : }
858 : else
859 : {
860 0 : if (GID_LOOKUP_MISS != sfi)
861 : {
862 0 : sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
863 0 : if (src_pref)
864 0 : old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
865 : else
866 : {
867 : ip_prefix_t sp;
868 0 : clib_memset (&sp, 0, sizeof (sp));
869 0 : ip_prefix_version (&sp) = AF_IP6;
870 0 : old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
871 : }
872 :
873 0 : if (sfib->count == 0)
874 0 : add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
875 : }
876 : else
877 0 : clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
878 : dst_pref);
879 : }
880 0 : return old_val;
881 : }
882 :
883 : static u32
884 4 : add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
885 : ip_prefix_t * src_key, u32 value, u8 is_add)
886 : {
887 4 : switch (ip_prefix_version (dst_key))
888 : {
889 4 : case AF_IP4:
890 4 : return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
891 : break;
892 0 : case AF_IP6:
893 0 : return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
894 : break;
895 0 : default:
896 0 : clib_warning ("address type %d not supported!",
897 : ip_prefix_version (dst_key));
898 0 : break;
899 : }
900 0 : return ~0;
901 : }
902 :
903 : static u32
904 0 : add_del_sd (gid_dictionary_t * db, u32 vni, source_dest_t * key, u32 value,
905 : u8 is_add)
906 : {
907 0 : switch (sd_dst_type (key))
908 : {
909 0 : case FID_ADDR_IP_PREF:
910 0 : add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
911 : value, is_add);
912 :
913 0 : case FID_ADDR_MAC:
914 0 : return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
915 0 : sd_src_mac (key), value, is_add);
916 :
917 0 : default:
918 0 : clib_warning ("SD address type %d not supported!", sd_dst_type (key));
919 0 : break;
920 : }
921 :
922 0 : return ~0;
923 : }
924 :
925 : static u64
926 0 : add_del_arp_ndp (gid_l2_arp_ndp_table_t * db, u32 bd, ip_address_t * key,
927 : u64 value, u8 is_add)
928 : {
929 : BVT (clib_bihash_kv) kv, result;
930 0 : u32 old_val = ~0;
931 :
932 0 : make_arp_ndp_key (&kv, bd, key);
933 0 : if (BV (clib_bihash_search) (&db->arp_ndp_lookup_table, &kv, &result) == 0)
934 0 : old_val = result.value;
935 :
936 0 : if (is_add)
937 : {
938 0 : kv.value = value;
939 0 : BV (clib_bihash_add_del) (&db->arp_ndp_lookup_table, &kv,
940 : 1 /* is_add */ );
941 0 : db->count++;
942 : }
943 : else
944 : {
945 0 : BV (clib_bihash_add_del) (&db->arp_ndp_lookup_table, &kv,
946 : 0 /* is_add */ );
947 0 : db->count--;
948 : }
949 0 : return old_val;
950 : }
951 :
952 : static u32
953 0 : add_del_nsh (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si, u32 value,
954 : u8 is_add)
955 : {
956 : BVT (clib_bihash_kv) kv, result;
957 0 : u32 old_val = ~0;
958 :
959 0 : make_nsh_key (&kv, vni, spi, si);
960 0 : if (BV (clib_bihash_search) (&db->nsh_lookup_table, &kv, &result) == 0)
961 0 : old_val = result.value;
962 :
963 0 : if (is_add)
964 : {
965 0 : kv.value = value;
966 0 : BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 1 /* is_add */ );
967 0 : db->count++;
968 : }
969 : else
970 : {
971 0 : BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 0 /* is_add */ );
972 0 : db->count--;
973 : }
974 0 : return old_val;
975 : }
976 :
977 : u32
978 4 : gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u64 value,
979 : u8 is_add)
980 : {
981 4 : switch (gid_address_type (key))
982 : {
983 4 : case GID_ADDR_IP_PREFIX:
984 4 : return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
985 : 0, (u32) value, is_add);
986 0 : case GID_ADDR_MAC:
987 0 : return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
988 0 : gid_address_mac (key), 0, (u32) value, is_add);
989 0 : case GID_ADDR_SRC_DST:
990 0 : return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
991 : (u32) value, is_add);
992 0 : case GID_ADDR_ARP:
993 : case GID_ADDR_NDP:
994 0 : return add_del_arp_ndp (&db->arp_ndp_table,
995 : gid_address_arp_ndp_bd (key),
996 : &gid_address_arp_ndp_ip (key), value, is_add);
997 0 : case GID_ADDR_NSH:
998 0 : return add_del_nsh (&db->nsh_table, gid_address_vni (key),
999 0 : gid_address_nsh_spi (key), gid_address_nsh_si (key),
1000 : value, is_add);
1001 :
1002 0 : default:
1003 0 : clib_warning ("address type %d not supported!", gid_address_type (key));
1004 0 : break;
1005 : }
1006 0 : return ~0;
1007 : }
1008 :
1009 : static void
1010 575 : mac_lookup_init (gid_mac_table_t * db)
1011 : {
1012 575 : if (db->mac_lookup_table_nbuckets == 0)
1013 575 : db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1014 :
1015 575 : db->mac_lookup_table_nbuckets =
1016 575 : 1 << max_log2 (db->mac_lookup_table_nbuckets);
1017 :
1018 575 : if (db->mac_lookup_table_size == 0)
1019 575 : db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1020 :
1021 575 : BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
1022 : db->mac_lookup_table_nbuckets,
1023 : db->mac_lookup_table_size);
1024 575 : }
1025 :
1026 : static void
1027 575 : arp_ndp_lookup_init (gid_l2_arp_ndp_table_t * db)
1028 : {
1029 575 : if (db->arp_ndp_lookup_table_nbuckets == 0)
1030 575 : db->arp_ndp_lookup_table_nbuckets =
1031 : ARP_NDP_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1032 :
1033 575 : db->arp_ndp_lookup_table_nbuckets =
1034 575 : 1 << max_log2 (db->arp_ndp_lookup_table_nbuckets);
1035 :
1036 575 : if (db->arp_ndp_lookup_table_size == 0)
1037 575 : db->arp_ndp_lookup_table_size = ARP_NDP_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1038 :
1039 575 : BV (clib_bihash_init) (&db->arp_ndp_lookup_table, "arp ndp lookup table",
1040 : db->arp_ndp_lookup_table_nbuckets,
1041 : db->arp_ndp_lookup_table_size);
1042 575 : }
1043 :
1044 : static void
1045 575 : nsh_lookup_init (gid_nsh_table_t * db)
1046 : {
1047 575 : if (db->nsh_lookup_table_nbuckets == 0)
1048 575 : db->nsh_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1049 :
1050 575 : db->nsh_lookup_table_nbuckets =
1051 575 : 1 << max_log2 (db->nsh_lookup_table_nbuckets);
1052 :
1053 575 : if (db->nsh_lookup_table_size == 0)
1054 575 : db->nsh_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1055 :
1056 575 : BV (clib_bihash_init) (&db->nsh_lookup_table, "nsh lookup table",
1057 : db->nsh_lookup_table_nbuckets,
1058 : db->nsh_lookup_table_size);
1059 575 : }
1060 :
1061 : void
1062 575 : gid_dictionary_init (gid_dictionary_t * db)
1063 : {
1064 575 : ip4_lookup_init (&db->dst_ip4_table);
1065 575 : ip6_lookup_init (&db->dst_ip6_table);
1066 575 : mac_lookup_init (&db->sd_mac_table);
1067 575 : arp_ndp_lookup_init (&db->arp_ndp_table);
1068 575 : nsh_lookup_init (&db->nsh_table);
1069 575 : }
1070 :
1071 : /*
1072 : * fd.io coding-style-patch-verification: ON
1073 : *
1074 : * Local Variables:
1075 : * eval: (c-set-style "gnu")
1076 : * End:
1077 : */
|
