FD.io VPP  v18.07.1-19-g511ce25
Vector Packet Processing
gid_dictionary.c
Go to the documentation of this file.
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 
17 
18 typedef struct
19 {
20  void *arg;
21  ip_prefix_t src;
23  union
24  {
27  };
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 void
35 foreach_sfib4_subprefix (BVT (clib_bihash_kv) * kvp, void *arg)
36 {
37  sfib_entry_arg_t *a = arg;
38  u32 ip = (u32) kvp->key[0];
39  ip4_address_t *mask;
40  u8 plen = ip_prefix_len (&a->src);
41 
42  ASSERT (plen <= 32);
43  mask = &a->ip4_table->ip4_fib_masks[plen];
44 
45  u32 src_ip = ip_prefix_v4 (&a->src).as_u32;
46  src_ip &= mask->as_u32;
47  ip &= mask->as_u32;
48 
49  if (src_ip == ip)
50  {
51  /* found sub-prefix of src prefix */
52  (a->cb) (kvp->value, a->arg);
53  }
54 }
55 
56 static void
58  ip_prefix_t * src, ip_prefix_t * dst,
59  foreach_subprefix_match_cb_t cb, void *arg)
60 {
61  u32 sfi;
62  gid_ip4_table_t *sfib4;
64 
65  sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
66  if (GID_LOOKUP_MISS == sfi)
67  return;
68 
69  sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);
70 
71  a.arg = arg;
72  a.cb = cb;
73  a.src = src[0];
74  a.ip4_table = sfib4;
75 
76  BV (clib_bihash_foreach_key_value_pair) (&sfib4->ip4_lookup_table,
78 }
79 
80 static void
81 foreach_sfib6_subprefix (BVT (clib_bihash_kv) * kvp, void *arg)
82 {
83  sfib_entry_arg_t *a = arg;
84  ip6_address_t ip;
85  ip6_address_t *mask;
86  u8 plen = ip_prefix_len (&a->src);
87 
88  mask = &a->ip6_table->ip6_fib_masks[plen];
89  ip.as_u64[0] = kvp->key[0];
90  ip.as_u64[1] = kvp->key[1];
91 
92  if (ip6_address_is_equal_masked (&ip_prefix_v6 (&a->src), &ip, mask))
93  {
94  /* found sub-prefix of src prefix */
95  (a->cb) (kvp->value, a->arg);
96  }
97 }
98 
99 static void
101  ip_prefix_t * src, ip_prefix_t * dst,
102  foreach_subprefix_match_cb_t cb, void *arg)
103 {
104  u32 sfi;
105  gid_ip6_table_t *sfib6;
107 
108  sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
109  if (GID_LOOKUP_MISS == sfi)
110  return;
111 
112  sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);
113 
114  a.arg = arg;
115  a.cb = cb;
116  a.src = src[0];
117  a.ip6_table = sfib6;
118 
119  BV (clib_bihash_foreach_key_value_pair) (&sfib6->ip6_lookup_table,
121 }
122 
123 void
125  foreach_subprefix_match_cb_t cb, void *arg)
126 {
127  ip_prefix_t *ippref = &gid_address_sd_dst_ippref (eid);
128 
129  if (IP4 == ip_prefix_version (ippref))
132  &gid_address_sd_dst_ippref (eid), cb,
133  arg);
134  else
137  &gid_address_sd_dst_ippref (eid), cb,
138  arg);
139 }
140 
141 void
143  (BVT (clib_bihash_kv) * kvp, void *arg),
144  void *ht)
145 {
147  BV (clib_bihash_foreach_key_value_pair) (&tab->arp_ndp_lookup_table, cb,
148  ht);
149 }
150 
151 static void
152 make_mac_sd_key (BVT (clib_bihash_kv) * kv, u32 vni, u8 src_mac[6],
153  u8 dst_mac[6])
154 {
155  kv->key[0] = (u64) vni;
156  kv->key[1] = mac_to_u64 (dst_mac);
157  kv->key[2] = src_mac ? mac_to_u64 (src_mac) : (u64) 0;
158 }
159 
160 static u32
161 mac_sd_lookup (gid_mac_table_t * db, u32 vni, u8 * dst, u8 * src)
162 {
163  int rv;
164  BVT (clib_bihash_kv) kv, value;
165 
166  make_mac_sd_key (&kv, vni, src, dst);
167  rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv, &value);
168 
169  /* no match, try with src 0, catch all for dst */
170  if (rv != 0)
171  {
172  kv.key[2] = 0;
173  rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv,
174  &value);
175  if (rv == 0)
176  return value.value;
177  }
178  else
179  return value.value;
180 
181  return GID_LOOKUP_MISS;
182 }
183 
184 static u32
185 ip4_lookup_exact_match (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
186 {
187  int rv;
188  BVT (clib_bihash_kv) kv, value;
189 
190  ip4_address_t *mask;
191 
192  mask = &db->ip4_fib_masks[ip_prefix_len (key)];
193 
194  kv.key[0] = ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
195  kv.key[1] = 0;
196  kv.key[2] = 0;
197 
198  rv = BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
199  if (rv == 0)
200  return value.value;
201 
202  return GID_LOOKUP_MISS;
203 }
204 
205 static u32
206 ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
207 {
208  int i, len;
209  int rv;
210  BVT (clib_bihash_kv) kv, value;
211 
213 
214  for (i = 0; i < len; i++)
215  {
216  int dst_address_length = db->ip4_prefix_lengths_in_search_order[i];
217  ip4_address_t *mask;
218 
219  ASSERT (dst_address_length >= 0 && dst_address_length <= 32);
220 
221  mask = &db->ip4_fib_masks[dst_address_length];
222 
223  kv.key[0] =
224  ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
225  kv.key[1] = 0;
226  kv.key[2] = 0;
227 
228  rv =
229  BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
230  if (rv == 0)
231  return value.value;
232  }
233 
234  return GID_LOOKUP_MISS;
235 }
236 
237 static u32
238 ip6_lookup_exact_match (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
239 {
240  int rv;
241  BVT (clib_bihash_kv) kv, value;
242 
243  ip6_address_t *mask;
244  mask = &db->ip6_fib_masks[ip_prefix_len (key)];
245 
246  kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
247  kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
248  kv.key[2] = (u64) vni;
249 
250  rv = BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
251  if (rv == 0)
252  return value.value;
253 
254  return GID_LOOKUP_MISS;
255 }
256 
257 static u32
258 ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
259 {
260  int i, len;
261  int rv;
262  BVT (clib_bihash_kv) kv, value;
263 
265 
266  for (i = 0; i < len; i++)
267  {
268  int dst_address_length = db->ip6_prefix_lengths_in_search_order[i];
269  ip6_address_t *mask;
270 
271  ASSERT (dst_address_length >= 0 && dst_address_length <= 128);
272 
273  mask = &db->ip6_fib_masks[dst_address_length];
274 
275  kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
276  kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
277  kv.key[2] = (u64) vni;
278 
279  rv =
280  BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
281  if (rv == 0)
282  return value.value;
283  }
284 
285  return GID_LOOKUP_MISS;
286 }
287 
288 static u32
289 ip_sd_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst,
290  ip_prefix_t * src)
291 {
292  u32 sfi;
293  gid_ip4_table_t *sfib4;
294  gid_ip6_table_t *sfib6;
295 
296  switch (ip_prefix_version (dst))
297  {
298  case IP4:
299  sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
300  if (GID_LOOKUP_MISS != sfi)
301  sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);
302  else
303  return GID_LOOKUP_MISS;
304 
305  if (!src)
306  {
307  ip_prefix_t sp;
308  memset (&sp, 0, sizeof (sp));
309  return ip4_lookup_exact_match (sfib4, 0, &sp);
310  }
311  else
312  return ip4_lookup (sfib4, 0, src);
313 
314  break;
315  case IP6:
316  sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
317  if (GID_LOOKUP_MISS != sfi)
318  sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);
319  else
320  return GID_LOOKUP_MISS;
321 
322  if (!src)
323  {
324  ip_prefix_t sp;
325  memset (&sp, 0, sizeof (sp));
326  ip_prefix_version (&sp) = IP6;
327  return ip6_lookup_exact_match (sfib6, 0, &sp);
328  }
329  else
330  return ip6_lookup (sfib6, 0, src);
331 
332  break;
333  default:
334  clib_warning ("address type %d not supported!",
335  ip_prefix_version (dst));
336  break;
337  }
338  return GID_LOOKUP_MISS;
339 }
340 
341 static void
342 make_arp_ndp_key (BVT (clib_bihash_kv) * kv, u32 bd, ip_address_t * addr)
343 {
344  kv->key[0] = ((u64) bd << 32) | (u32) ip_addr_version (addr);
345  if (ip_addr_version (addr) == IP4)
346  {
347  kv->key[1] = (u64) addr->ip.v4.as_u32;
348  kv->key[2] = (u64) 0;
349  }
350  else
351  {
352  kv->key[1] = (u64) addr->ip.v6.as_u64[0];
353  kv->key[2] = (u64) addr->ip.v6.as_u64[1];
354  }
355 }
356 
357 static void
358 make_nsh_key (BVT (clib_bihash_kv) * kv, u32 vni, u32 spi, u8 si)
359 {
360  kv->key[0] = (u64) vni;
361  kv->key[1] = (u64) spi;
362  kv->key[2] = (u64) si;
363 }
364 
365 static u64
366 arp_ndp_lookup (gid_l2_arp_ndp_table_t * db, u32 bd, ip_address_t * key)
367 {
368  int rv;
369  BVT (clib_bihash_kv) kv, value;
370 
371  make_arp_ndp_key (&kv, bd, key);
372  rv = BV (clib_bihash_search_inline_2) (&db->arp_ndp_lookup_table, &kv,
373  &value);
374 
375  if (rv == 0)
376  return value.value;
377 
378  return GID_LOOKUP_MISS_L2;
379 }
380 
381 static u32
382 nsh_lookup (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si)
383 {
384  int rv;
385  BVT (clib_bihash_kv) kv, value;
386 
387  make_nsh_key (&kv, vni, spi, si);
388  rv = BV (clib_bihash_search_inline_2) (&db->nsh_lookup_table, &kv, &value);
389 
390  if (rv == 0)
391  return value.value;
392 
393  return GID_LOOKUP_MISS;
394 }
395 
396 u64
398 {
399  switch (gid_address_type (key))
400  {
401  case GID_ADDR_IP_PREFIX:
402  return ip_sd_lookup (db, gid_address_vni (key),
403  &gid_address_ippref (key), 0);
404  case GID_ADDR_MAC:
405  return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
406  gid_address_mac (key), 0);
407  case GID_ADDR_SRC_DST:
408  switch (gid_address_sd_dst_type (key))
409  {
410  case FID_ADDR_IP_PREF:
411  return ip_sd_lookup (db, gid_address_vni (key),
414  break;
415  case FID_ADDR_MAC:
416  return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
418  gid_address_sd_src_mac (key));
419  break;
420  default:
421  clib_warning ("Source/Dest address type %d not supported!",
423  break;
424  }
425  break;
426  case GID_ADDR_ARP:
427  case GID_ADDR_NDP:
429  &gid_address_arp_ndp_ip (key));
430  case GID_ADDR_NSH:
431  return nsh_lookup (&db->nsh_table, gid_address_vni (key),
433  default:
434  clib_warning ("address type %d not supported!", gid_address_type (key));
435  break;
436  }
437  return GID_LOOKUP_MISS;
438 }
439 
440 u32
442  gid_address_t * src)
443 {
444  switch (gid_address_type (dst))
445  {
446  case GID_ADDR_IP_PREFIX:
447  return ip_sd_lookup (db, gid_address_vni (dst),
448  &gid_address_ippref (dst),
449  &gid_address_ippref (src));
450  case GID_ADDR_MAC:
451  return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
452  gid_address_mac (dst), gid_address_mac (src));
453  case GID_ADDR_SRC_DST:
454  switch (gid_address_sd_dst_type (dst))
455  {
456  case FID_ADDR_IP_PREF:
457  return ip_sd_lookup (db, gid_address_vni (dst),
460  break;
461  case FID_ADDR_MAC:
462  return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
464  gid_address_sd_src_mac (dst));
465  break;
466  default:
467  clib_warning ("Source/Dest address type %d not supported!",
469  break;
470  }
471  break;
472  case GID_ADDR_NSH:
473  return gid_dictionary_lookup (db, dst);
474  break;
475  default:
476  clib_warning ("address type %d not supported!", gid_address_type (dst));
477  break;
478  }
479  return GID_LOOKUP_MISS;
480 }
481 
482 static void
484 {
485  int i;
487  /* Note: bitmap reversed so this is in fact a longest prefix match */
488 
489  /* *INDENT-OFF* */
491  ({
492  int dst_address_length = 32 - i;
493  vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
494  }));
495  /* *INDENT-ON* */
496 
497 }
498 
499 static u32
500 add_del_ip4_key (gid_ip4_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
501  u8 is_add)
502 {
503  BVT (clib_bihash_kv) kv, value;
504  u32 old_val = ~0;
505  ip4_address_t key;
506  u8 plen = ip_prefix_len (pref);
507 
508  clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
509  key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
510  if (is_add)
511  {
514  32 - plen, 1);
516 
517  db->ip4_prefix_len_refcount[plen]++;
518  }
519  else
520  {
521  ASSERT (db->ip4_prefix_len_refcount[plen] != 0);
522 
523  db->ip4_prefix_len_refcount[plen]--;
524 
525  if (db->ip4_prefix_len_refcount[plen] == 0)
526  {
529  32 - plen, 0);
531  }
532  }
533 
534  kv.key[0] = ((u64) vni << 32) | key.as_u32;
535  kv.key[1] = 0;
536  kv.key[2] = 0;
537 
538  if (BV (clib_bihash_search) (&db->ip4_lookup_table, &kv, &value) == 0)
539  old_val = value.value;
540 
541  if (!is_add)
542  {
543  BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
544  db->count--;
545  }
546  else
547  {
548  kv.value = val;
549  BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
550  db->count++;
551  }
552  return old_val;
553 }
554 
555 static void
557 {
558  uword i;
559 
560  memset (db->ip4_prefix_len_refcount, 0,
561  sizeof (db->ip4_prefix_len_refcount));
562 
563  for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
564  {
565  u32 m;
566 
567  if (i < 32)
568  m = pow2_mask (i) << (32 - i);
569  else
570  m = ~0;
571  db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
572  }
573  if (db->ip4_lookup_table_nbuckets == 0)
575 
578 
579  if (db->ip4_lookup_table_size == 0)
581 
582  BV (clib_bihash_init) (&db->ip4_lookup_table, "ip4 lookup table",
585 }
586 
587 static u32
588 add_del_sd_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
589  ip_prefix_t * src_pref, u32 val, u8 is_add)
590 {
591  u32 sfi, old_val = ~0;
592  gid_ip4_table_t *sfib;
593 
594  sfi = ip4_lookup_exact_match (&db->dst_ip4_table, vni, dst_pref);
595 
596  if (is_add)
597  {
598  if (GID_LOOKUP_MISS == sfi)
599  {
600  pool_get (db->src_ip4_table_pool, sfib);
601  ip4_lookup_init (sfib);
602  add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref,
603  sfib - db->src_ip4_table_pool, is_add);
604  if (src_pref)
605  add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
606  else
607  {
608  ip_prefix_t sp;
609  memset (&sp, 0, sizeof (sp));
610  add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
611  }
612  }
613  else
614  {
616  sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
617  if (src_pref)
618  {
619  old_val = ip4_lookup_exact_match (sfib, 0, src_pref);
620  add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
621  }
622  else
623  {
624  ip_prefix_t sp;
625  memset (&sp, 0, sizeof (sp));
626  old_val =
627  add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
628  }
629  }
630  }
631  else
632  {
633  if (GID_LOOKUP_MISS != sfi)
634  {
635  sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
636  if (src_pref)
637  old_val = add_del_ip4_key (sfib, 0, src_pref, 0, is_add);
638  else
639  {
640  ip_prefix_t sp;
641  memset (&sp, 0, sizeof (sp));
642  old_val = add_del_ip4_key (sfib, 0, &sp, 0, is_add);
643  }
644 
645  if (sfib->count == 0)
646  add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref, 0, is_add);
647  }
648  else
649  clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
650  dst_pref);
651  }
652  return old_val;
653 }
654 
655 static void
657 {
658  int i;
660  /* Note: bitmap reversed so this is in fact a longest prefix match */
661 
662  /* *INDENT-OFF* */
664  ({
665  int dst_address_length = 128 - i;
666  vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
667  }));
668  /* *INDENT-ON* */
669 }
670 
671 static u32
672 add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
673  u8 is_add)
674 {
675  BVT (clib_bihash_kv) kv, value;
676  u32 old_val = ~0;
677  ip6_address_t key;
678  u8 plen = ip_prefix_len (pref);
679 
680  clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
681  ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
682  if (is_add)
683  {
686  128 - plen, 1);
688  db->ip6_prefix_len_refcount[plen]++;
689  }
690  else
691  {
692  ASSERT (db->ip6_prefix_len_refcount[plen] != 0);
693 
694  db->ip6_prefix_len_refcount[plen]--;
695 
696  if (db->ip6_prefix_len_refcount[plen] == 0)
697  {
700  128 - plen, 0);
702  }
703  }
704 
705  kv.key[0] = key.as_u64[0];
706  kv.key[1] = key.as_u64[1];
707  kv.key[2] = (u64) vni;
708 // kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);
709 
710  if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
711  old_val = value.value;
712 
713  if (!is_add)
714  {
715  BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
716  db->count--;
717  }
718  else
719  {
720  kv.value = val;
721  BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
722  db->count++;
723  }
724  return old_val;
725 }
726 
727 static u32
728 add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
729  u32 val, u8 is_add)
730 {
731  BVT (clib_bihash_kv) kv, value;
732  u32 old_val = ~0;
733 
734  make_mac_sd_key (&kv, vni, src_mac, dst_mac);
735 
736  if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
737  old_val = value.value;
738 
739  if (!is_add)
740  {
741  BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
742  db->count--;
743  }
744  else
745  {
746  kv.value = val;
747  BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
748  db->count++;
749  }
750  return old_val;
751 }
752 
753 static void
755 {
756  uword i;
757 
758  memset (db->ip6_prefix_len_refcount, 0,
759  sizeof (db->ip6_prefix_len_refcount));
760 
761  for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
762  {
763  u32 j, i0, i1;
764 
765  i0 = i / 32;
766  i1 = i % 32;
767 
768  for (j = 0; j < i0; j++)
769  db->ip6_fib_masks[i].as_u32[j] = ~0;
770 
771  if (i1)
772  db->ip6_fib_masks[i].as_u32[i0] =
773  clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
774  }
775 
776  if (db->ip6_lookup_table_nbuckets == 0)
778 
781 
782  if (db->ip6_lookup_table_size == 0)
784 
785  BV (clib_bihash_init) (&db->ip6_lookup_table, "ip6 lookup table",
788 }
789 
790 static u32
791 add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
792  ip_prefix_t * src_pref, u32 val, u8 is_add)
793 {
794  u32 sfi, old_val = ~0;
795  gid_ip6_table_t *sfib;
796 
797  sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);
798 
799  if (is_add)
800  {
801  if (GID_LOOKUP_MISS == sfi)
802  {
803  pool_get (db->src_ip6_table_pool, sfib);
804  ip6_lookup_init (sfib);
805  add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
806  sfib - db->src_ip6_table_pool, is_add);
807  if (src_pref)
808  add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
809  else
810  {
811  ip_prefix_t sp;
812  memset (&sp, 0, sizeof (sp));
813  ip_prefix_version (&sp) = IP6;
814  add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
815  }
816  }
817  else
818  {
820  sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
821  if (src_pref)
822  {
823  old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
824  add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
825  }
826  else
827  {
828  ip_prefix_t sp;
829  memset (&sp, 0, sizeof (sp));
830  ip_prefix_version (&sp) = IP6;
831  old_val =
832  add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
833  }
834  }
835  }
836  else
837  {
838  if (GID_LOOKUP_MISS != sfi)
839  {
840  sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
841  if (src_pref)
842  old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
843  else
844  {
845  ip_prefix_t sp;
846  memset (&sp, 0, sizeof (sp));
847  ip_prefix_version (&sp) = IP6;
848  old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
849  }
850 
851  if (sfib->count == 0)
852  add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
853  }
854  else
855  clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
856  dst_pref);
857  }
858  return old_val;
859 }
860 
861 static u32
862 add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
863  ip_prefix_t * src_key, u32 value, u8 is_add)
864 {
865  switch (ip_prefix_version (dst_key))
866  {
867  case IP4:
868  return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
869  break;
870  case IP6:
871  return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
872  break;
873  default:
874  clib_warning ("address type %d not supported!",
875  ip_prefix_version (dst_key));
876  break;
877  }
878  return ~0;
879 }
880 
881 static u32
883  u8 is_add)
884 {
885  switch (sd_dst_type (key))
886  {
887  case FID_ADDR_IP_PREF:
888  add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
889  value, is_add);
890 
891  case FID_ADDR_MAC:
892  return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
893  sd_src_mac (key), value, is_add);
894 
895  default:
896  clib_warning ("SD address type %d not supprted!", sd_dst_type (key));
897  break;
898  }
899 
900  return ~0;
901 }
902 
903 static u64
904 add_del_arp_ndp (gid_l2_arp_ndp_table_t * db, u32 bd, ip_address_t * key,
905  u64 value, u8 is_add)
906 {
907  BVT (clib_bihash_kv) kv, result;
908  u32 old_val = ~0;
909 
910  make_arp_ndp_key (&kv, bd, key);
911  if (BV (clib_bihash_search) (&db->arp_ndp_lookup_table, &kv, &result) == 0)
912  old_val = result.value;
913 
914  if (is_add)
915  {
916  kv.value = value;
917  BV (clib_bihash_add_del) (&db->arp_ndp_lookup_table, &kv,
918  1 /* is_add */ );
919  db->count++;
920  }
921  else
922  {
923  BV (clib_bihash_add_del) (&db->arp_ndp_lookup_table, &kv,
924  0 /* is_add */ );
925  db->count--;
926  }
927  return old_val;
928 }
929 
930 static u32
931 add_del_nsh (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si, u32 value,
932  u8 is_add)
933 {
934  BVT (clib_bihash_kv) kv, result;
935  u32 old_val = ~0;
936 
937  make_nsh_key (&kv, vni, spi, si);
938  if (BV (clib_bihash_search) (&db->nsh_lookup_table, &kv, &result) == 0)
939  old_val = result.value;
940 
941  if (is_add)
942  {
943  kv.value = value;
944  BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 1 /* is_add */ );
945  db->count++;
946  }
947  else
948  {
949  BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 0 /* is_add */ );
950  db->count--;
951  }
952  return old_val;
953 }
954 
955 u32
957  u8 is_add)
958 {
959  switch (gid_address_type (key))
960  {
961  case GID_ADDR_IP_PREFIX:
962  return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
963  0, (u32) value, is_add);
964  case GID_ADDR_MAC:
965  return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
966  gid_address_mac (key), 0, (u32) value, is_add);
967  case GID_ADDR_SRC_DST:
968  return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
969  (u32) value, is_add);
970  case GID_ADDR_ARP:
971  case GID_ADDR_NDP:
972  return add_del_arp_ndp (&db->arp_ndp_table,
974  &gid_address_arp_ndp_ip (key), value, is_add);
975  case GID_ADDR_NSH:
976  return add_del_nsh (&db->nsh_table, gid_address_vni (key),
978  value, is_add);
979 
980  default:
981  clib_warning ("address type %d not supported!", gid_address_type (key));
982  break;
983  }
984  return ~0;
985 }
986 
987 static void
989 {
990  if (db->mac_lookup_table_nbuckets == 0)
992 
995 
996  if (db->mac_lookup_table_size == 0)
998 
999  BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
1001  db->mac_lookup_table_size);
1002 }
1003 
1004 static void
1006 {
1007  if (db->arp_ndp_lookup_table_nbuckets == 0)
1010 
1013 
1014  if (db->arp_ndp_lookup_table_size == 0)
1016 
1017  BV (clib_bihash_init) (&db->arp_ndp_lookup_table, "arp ndp lookup table",
1020 }
1021 
1022 static void
1024 {
1025  if (db->nsh_lookup_table_nbuckets == 0)
1027 
1030 
1031  if (db->nsh_lookup_table_size == 0)
1033 
1034  BV (clib_bihash_init) (&db->nsh_lookup_table, "nsh lookup table",
1036  db->nsh_lookup_table_size);
1037 }
1038 
1039 void
1041 {
1046  nsh_lookup_init (&db->nsh_table);
1047 }
1048 
1049 /*
1050  * fd.io coding-style-patch-verification: ON
1051  *
1052  * Local Variables:
1053  * eval: (c-set-style "gnu")
1054  * End:
1055  */
#define ip_prefix_v4(_a)
Definition: lisp_types.h:74
static u32 add_del_ip(gid_dictionary_t *db, u32 vni, ip_prefix_t *dst_key, ip_prefix_t *src_key, u32 value, u8 is_add)
static void ip6_address_mask(ip6_address_t *a, ip6_address_t *mask)
Definition: ip6_packet.h:241
#define IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS
static void make_arp_ndp_key(BVT(clib_bihash_kv)*kv, u32 bd, ip_address_t *addr)
gid_ip4_table_t * src_ip4_table_pool
pool of source IP LPM ip4 lookup tables
#define gid_address_type(_a)
Definition: lisp_types.h:261
#define sd_dst_mac(_a)
Definition: lisp_types.h:150
a
Definition: bitmap.h:538
ip4_address_t ip4_fib_masks[33]
static void make_nsh_key(BVT(clib_bihash_kv)*kv, u32 vni, u32 spi, u8 si)
static u32 mac_sd_lookup(gid_mac_table_t *db, u32 vni, u8 *dst, u8 *src)
static void gid_dict_foreach_ip4_subprefix(gid_dictionary_t *db, u32 vni, ip_prefix_t *src, ip_prefix_t *dst, foreach_subprefix_match_cb_t cb, void *arg)
void * arg
u64 as_u64[2]
Definition: ip6_packet.h:51
unsigned long u64
Definition: types.h:89
static void mac_lookup_init(gid_mac_table_t *db)
u32 mac_lookup_table_nbuckets
static void gid_dict_foreach_ip6_subprefix(gid_dictionary_t *db, u32 vni, ip_prefix_t *src, ip_prefix_t *dst, foreach_subprefix_match_cb_t cb, void *arg)
#define MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS
static u32 add_del_nsh(gid_nsh_table_t *db, u32 vni, u32 spi, u8 si, u32 value, u8 is_add)
static void ip6_compute_prefix_lengths_in_search_order(gid_ip6_table_t *db)
#define gid_address_sd_src_mac(_a)
Definition: lisp_types.h:276
#define ip_prefix_len(_a)
Definition: lisp_types.h:73
static void nsh_lookup_init(gid_nsh_table_t *db)
#define gid_address_sd(_a)
Definition: lisp_types.h:277
u32 ip4_prefix_len_refcount[33]
#define IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS
#define gid_address_sd_src_ippref(_a)
Definition: lisp_types.h:274
int i
static uword * clib_bitmap_set(uword *ai, uword i, uword value)
Sets the ith bit of a bitmap to new_value Removes trailing zeros from the bitmap. ...
Definition: bitmap.h:167
u32 nsh_lookup_table_nbuckets
static uword ip6_address_is_equal_masked(ip6_address_t *a, ip6_address_t *b, ip6_address_t *mask)
Definition: ip6_packet.h:224
#define gid_address_sd_dst_mac(_a)
Definition: lisp_types.h:275
#define IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE
#define pool_get(P, E)
Allocate an object E from a pool P (unspecified alignment).
Definition: pool.h:228
vhost_vring_addr_t addr
Definition: vhost_user.h:116
#define ip_prefix_version(_a)
Definition: lisp_types.h:72
gid_ip4_table_t dst_ip4_table
destination IP LPM ip4 lookup table
static u32 ip4_lookup(gid_ip4_table_t *db, u32 vni, ip_prefix_t *key)
unsigned char u8
Definition: types.h:56
void gid_dictionary_init(gid_dictionary_t *db)
#define vec_reset_length(v)
Reset vector length to zero NULL-pointer tolerant.
static u32 add_del_sd_ip6_key(gid_dictionary_t *db, u32 vni, ip_prefix_t *dst_pref, ip_prefix_t *src_pref, u32 val, u8 is_add)
u32 gid_dictionary_add_del(gid_dictionary_t *db, gid_address_t *key, u64 value, u8 is_add)
int clib_bihash_add_del(clib_bihash *h, clib_bihash_kv *add_v, int is_add)
Add or delete a (key,value) pair from a bi-hash table.
static uword pow2_mask(uword x)
Definition: clib.h:214
static u32 add_del_sd(gid_dictionary_t *db, u32 vni, source_dest_t *key, u32 value, u8 is_add)
static BVT(clib_bihash)
Definition: adj_nbr.c:26
static void foreach_sfib6_subprefix(BVT(clib_bihash_kv)*kvp, void *arg)
unsigned int u32
Definition: types.h:88
ip_prefix_t src
#define ip_addr_version(_a)
Definition: lisp_types.h:56
#define clib_bitmap_foreach(i, ai, body)
Macro to iterate across set bits in a bitmap.
Definition: bitmap.h:361
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:464
#define gid_address_arp_ndp_ip(_a)
Definition: lisp_types.h:284
void gid_dict_foreach_subprefix(gid_dictionary_t *db, gid_address_t *eid, foreach_subprefix_match_cb_t cb, void *arg)
#define gid_address_mac(_a)
Definition: lisp_types.h:267
#define ip_prefix_v6(_a)
Definition: lisp_types.h:75
static u32 ip6_lookup_exact_match(gid_ip6_table_t *db, u32 vni, ip_prefix_t *key)
#define gid_address_sd_dst_type(_a)
Definition: lisp_types.h:281
gid_ip6_table_t * src_ip6_table_pool
pool of source IP LPM ip6 lookup tables
gid_ip6_table_t dst_ip6_table
destination IP LPM ip6 lookup table
static void make_mac_sd_key(BVT(clib_bihash_kv)*kv, u32 vni, u8 src_mac[6], u8 dst_mac[6])
void clib_bihash_init(clib_bihash *h, char *name, u32 nbuckets, uword memory_size)
initialize a bounded index extensible hash table
u32 ip4_lookup_table_nbuckets
static void foreach_sfib4_subprefix(BVT(clib_bihash_kv)*kvp, void *arg)
#define gid_address_ippref(_a)
Definition: lisp_types.h:262
u32 as_u32[4]
Definition: ip6_packet.h:50
void clib_bihash_foreach_key_value_pair(clib_bihash *h, void *callback, void *arg)
Visit active (key,value) pairs in a bi-hash table.
#define sd_src_ippref(_a)
Definition: lisp_types.h:147
u32 ip6_lookup_table_nbuckets
u8 * ip6_prefix_lengths_in_search_order
static u32 add_del_ip4_key(gid_ip4_table_t *db, u32 vni, ip_prefix_t *pref, u32 val, u8 is_add)
uword nsh_lookup_table_size
uword ip6_lookup_table_size
gid_l2_arp_ndp_table_t arp_ndp_table
L2 ARP/NDP table.
#define clib_warning(format, args...)
Definition: error.h:59
static u32 ip4_lookup_exact_match(gid_ip4_table_t *db, u32 vni, ip_prefix_t *key)
#define clib_memcpy(a, b, c)
Definition: string.h:75
static u64 add_del_arp_ndp(gid_l2_arp_ndp_table_t *db, u32 bd, ip_address_t *key, u64 value, u8 is_add)
u8 * ip4_prefix_lengths_in_search_order
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:271
#define ARRAY_LEN(x)
Definition: clib.h:59
#define gid_address_nsh_si(_a)
Definition: lisp_types.h:270
void(* foreach_subprefix_match_cb_t)(u32, void *)
static void arp_ndp_lookup_init(gid_l2_arp_ndp_table_t *db)
#define gid_address_arp_ndp_bd(_a)
Definition: lisp_types.h:283
#define sd_src_mac(_a)
Definition: lisp_types.h:149
struct _gid_address_t gid_address_t
#define ARP_NDP_LOOKUP_DEFAULT_HASH_MEMORY_SIZE
#define ASSERT(truth)
#define IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE
int clib_bihash_search_inline_2(clib_bihash *h, clib_bihash_kv *search_key, clib_bihash_kv *valuep)
Search a bi-hash table.
#define GID_LOOKUP_MISS
u32 gid_dictionary_sd_lookup(gid_dictionary_t *db, gid_address_t *dst, gid_address_t *src)
#define sd_dst_type(_a)
Definition: lisp_types.h:152
gid_nsh_table_t nsh_table
NSH lookup table.
u64 ip6_prefix_len_refcount[129]
static u32 add_del_sd_ip4_key(gid_dictionary_t *db, u32 vni, ip_prefix_t *dst_pref, ip_prefix_t *src_pref, u32 val, u8 is_add)
static u64 mac_to_u64(u8 *m)
Definition: load_balance.c:918
#define gid_address_sd_dst_ippref(_a)
Definition: lisp_types.h:273
u64 gid_dictionary_lookup(gid_dictionary_t *db, gid_address_t *key)
static void ip4_compute_prefix_lengths_in_search_order(gid_ip4_table_t *db)
static void ip6_lookup_init(gid_ip6_table_t *db)
#define ARP_NDP_LOOKUP_DEFAULT_HASH_NUM_BUCKETS
u8 * format_ip_prefix(u8 *s, va_list *args)
Definition: lisp_types.c:179
uword mac_lookup_table_size
uword ip4_lookup_table_size
foreach_subprefix_match_cb_t cb
#define gid_address_vni(_a)
Definition: lisp_types.h:271
gid_mac_table_t sd_mac_table
flat source/dest mac lookup table
uword * ip4_non_empty_dst_address_length_bitmap
static void ip4_lookup_init(gid_ip4_table_t *db)
#define vec_len(v)
Number of elements in vector (rvalue-only, NULL tolerant)
static u32 ip_sd_lookup(gid_dictionary_t *db, u32 vni, ip_prefix_t *dst, ip_prefix_t *src)
#define GID_LOOKUP_MISS_L2
static uword max_log2(uword x)
Definition: clib.h:185
static u32 add_del_mac(gid_mac_table_t *db, u32 vni, u8 *dst_mac, u8 *src_mac, u32 val, u8 is_add)
u64 uword
Definition: types.h:112
#define gid_address_nsh_spi(_a)
Definition: lisp_types.h:269
static u64 arp_ndp_lookup(gid_l2_arp_ndp_table_t *db, u32 bd, ip_address_t *key)
gid_ip6_table_t * ip6_table
Definition: lisp_types.h:37
static u32 add_del_ip6_key(gid_ip6_table_t *db, u32 vni, ip_prefix_t *pref, u32 val, u8 is_add)
gid_ip4_table_t * ip4_table
ip6_address_t ip6_fib_masks[129]
static u32 ip6_lookup(gid_ip6_table_t *db, u32 vni, ip_prefix_t *key)
Definition: lisp_types.h:38
#define MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE
static u32 nsh_lookup(gid_nsh_table_t *db, u32 vni, u32 spi, u8 si)
uword * ip6_non_empty_dst_address_length_bitmap
void gid_dict_foreach_l2_arp_ndp_entry(gid_dictionary_t *db, void(*cb)(BVT(clib_bihash_kv)*kvp, void *arg), void *ht)
#define sd_dst_ippref(_a)
Definition: lisp_types.h:148