src/vnet/lisp-cp/gid_dictionary.c

   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 <vnet/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 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
  57 gid_dict_foreach_ip4_subprefix (gid_dictionary_t * db, u32 vni,
  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;
  63   sfib_entry_arg_t a;
  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,
  77                                            foreach_sfib4_subprefix, &a);
  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
 100 gid_dict_foreach_ip6_subprefix (gid_dictionary_t * db, u32 vni,
 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;
 106   sfib_entry_arg_t a;
 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,
 120                                            foreach_sfib6_subprefix, &a);
 121 }
 122
 123 void
 124 gid_dict_foreach_subprefix (gid_dictionary_t * db, gid_address_t * eid,
 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))
 130     gid_dict_foreach_ip4_subprefix (db, gid_address_vni (eid),
 131                                     &gid_address_sd_src_ippref (eid),
 132                                     &gid_address_sd_dst_ippref (eid), cb,
 133                                     arg);
 134   else
 135     gid_dict_foreach_ip6_subprefix (db, gid_address_vni (eid),
 136                                     &gid_address_sd_src_ippref (eid),
 137                                     &gid_address_sd_dst_ippref (eid), cb,
 138                                     arg);
 139 }
 140
 141 void
 142 gid_dict_foreach_l2_arp_entry (gid_dictionary_t * db, void (*cb)
 143                                (BVT (clib_bihash_kv) * kvp, void *arg),
 144                                void *ht)
 145 {
 146   gid_l2_arp_table_t *tab = &db->arp_table;
 147   BV (clib_bihash_foreach_key_value_pair) (&tab->arp_lookup_table, cb, ht);
 148 }
 149
 150 static void
 151 make_mac_sd_key (BVT (clib_bihash_kv) * kv, u32 vni, u8 src_mac[6],
 152                  u8 dst_mac[6])
 153 {
 154   kv->key[0] = (u64) vni;
 155   kv->key[1] = mac_to_u64 (dst_mac);
 156   kv->key[2] = src_mac ? mac_to_u64 (src_mac) : (u64) 0;
 157 }
 158
 159 static u32
 160 mac_sd_lookup (gid_mac_table_t * db, u32 vni, u8 * dst, u8 * src)
 161 {
 162   int rv;
 163   BVT (clib_bihash_kv) kv, value;
 164
 165   make_mac_sd_key (&kv, vni, src, dst);
 166   rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv, &value);
 167
 168   /* no match, try with src 0, catch all for dst */
 169   if (rv != 0)
 170     {
 171       kv.key[2] = 0;
 172       rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv,
 173                                              &value);
 174       if (rv == 0)
 175         return value.value;
 176     }
 177   else
 178     return value.value;
 179
 180   return GID_LOOKUP_MISS;
 181 }
 182
 183 static u32
 184 ip4_lookup_exact_match (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
 185 {
 186   int rv;
 187   BVT (clib_bihash_kv) kv, value;
 188
 189   ip4_address_t *mask;
 190
 191   mask = &db->ip4_fib_masks[ip_prefix_len (key)];
 192
 193   kv.key[0] = ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
 194   kv.key[1] = 0;
 195   kv.key[2] = 0;
 196
 197   rv = BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
 198   if (rv == 0)
 199     return value.value;
 200
 201   return GID_LOOKUP_MISS;
 202 }
 203
 204 static u32
 205 ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
 206 {
 207   int i, len;
 208   int rv;
 209   BVT (clib_bihash_kv) kv, value;
 210
 211   len = vec_len (db->ip4_prefix_lengths_in_search_order);
 212
 213   for (i = 0; i < len; i++)
 214     {
 215       int dst_address_length = db->ip4_prefix_lengths_in_search_order[i];
 216       ip4_address_t *mask;
 217
 218       ASSERT (dst_address_length >= 0 && dst_address_length <= 32);
 219
 220       mask = &db->ip4_fib_masks[dst_address_length];
 221
 222       kv.key[0] =
 223         ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
 224       kv.key[1] = 0;
 225       kv.key[2] = 0;
 226
 227       rv =
 228         BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
 229       if (rv == 0)
 230         return value.value;
 231     }
 232
 233   return GID_LOOKUP_MISS;
 234 }
 235
 236 static u32
 237 ip6_lookup_exact_match (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
 238 {
 239   int rv;
 240   BVT (clib_bihash_kv) kv, value;
 241
 242   ip6_address_t *mask;
 243   mask = &db->ip6_fib_masks[ip_prefix_len (key)];
 244
 245   kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
 246   kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
 247   kv.key[2] = (u64) vni;
 248
 249   rv = BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
 250   if (rv == 0)
 251     return value.value;
 252
 253   return GID_LOOKUP_MISS;
 254 }
 255
 256 static u32
 257 ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
 258 {
 259   int i, len;
 260   int rv;
 261   BVT (clib_bihash_kv) kv, value;
 262
 263   len = vec_len (db->ip6_prefix_lengths_in_search_order);
 264
 265   for (i = 0; i < len; i++)
 266     {
 267       int dst_address_length = db->ip6_prefix_lengths_in_search_order[i];
 268       ip6_address_t *mask;
 269
 270       ASSERT (dst_address_length >= 0 && dst_address_length <= 128);
 271
 272       mask = &db->ip6_fib_masks[dst_address_length];
 273
 274       kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
 275       kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
 276       kv.key[2] = (u64) vni;
 277
 278       rv =
 279         BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
 280       if (rv == 0)
 281         return value.value;
 282     }
 283
 284   return GID_LOOKUP_MISS;
 285 }
 286
 287 static u32
 288 ip_sd_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst,
 289               ip_prefix_t * src)
 290 {
 291   u32 sfi;
 292   gid_ip4_table_t *sfib4;
 293   gid_ip6_table_t *sfib6;
 294
 295   switch (ip_prefix_version (dst))
 296     {
 297     case IP4:
 298       sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
 299       if (GID_LOOKUP_MISS != sfi)
 300         sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 301       else
 302         return GID_LOOKUP_MISS;
 303
 304       if (!src)
 305         {
 306           ip_prefix_t sp;
 307           memset (&sp, 0, sizeof (sp));
 308           return ip4_lookup_exact_match (sfib4, 0, &sp);
 309         }
 310       else
 311         return ip4_lookup (sfib4, 0, src);
 312
 313       break;
 314     case IP6:
 315       sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
 316       if (GID_LOOKUP_MISS != sfi)
 317         sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 318       else
 319         return GID_LOOKUP_MISS;
 320
 321       if (!src)
 322         {
 323           ip_prefix_t sp;
 324           memset (&sp, 0, sizeof (sp));
 325           ip_prefix_version (&sp) = IP6;
 326           return ip6_lookup_exact_match (sfib6, 0, &sp);
 327         }
 328       else
 329         return ip6_lookup (sfib6, 0, src);
 330
 331       break;
 332     default:
 333       clib_warning ("address type %d not supported!",
 334                     ip_prefix_version (dst));
 335       break;
 336     }
 337   return GID_LOOKUP_MISS;
 338 }
 339
 340 static void
 341 make_arp_key (BVT (clib_bihash_kv) * kv, u32 bd, ip4_address_t * addr)
 342 {
 343   kv->key[0] = (u64) bd;
 344   kv->key[1] = (u64) addr->as_u32;
 345   kv->key[2] = (u64) 0;
 346 }
 347
 348 static void
 349 make_nsh_key (BVT (clib_bihash_kv) * kv, u32 vni, u32 spi, u8 si)
 350 {
 351   kv->key[0] = (u64) vni;
 352   kv->key[1] = (u64) spi;
 353   kv->key[2] = (u64) si;
 354 }
 355
 356 static u64
 357 arp_lookup (gid_l2_arp_table_t * db, u32 bd, ip4_address_t * key)
 358 {
 359   int rv;
 360   BVT (clib_bihash_kv) kv, value;
 361
 362   make_arp_key (&kv, bd, key);
 363   rv = BV (clib_bihash_search_inline_2) (&db->arp_lookup_table, &kv, &value);
 364
 365   if (rv == 0)
 366     return value.value;
 367
 368   return GID_LOOKUP_MISS_L2;
 369 }
 370
 371 static u32
 372 nsh_lookup (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si)
 373 {
 374   int rv;
 375   BVT (clib_bihash_kv) kv, value;
 376
 377   make_nsh_key (&kv, vni, spi, si);
 378   rv = BV (clib_bihash_search_inline_2) (&db->nsh_lookup_table, &kv, &value);
 379
 380   if (rv == 0)
 381     return value.value;
 382
 383   return GID_LOOKUP_MISS;
 384 }
 385
 386 u64
 387 gid_dictionary_lookup (gid_dictionary_t * db, gid_address_t * key)
 388 {
 389   switch (gid_address_type (key))
 390     {
 391     case GID_ADDR_IP_PREFIX:
 392       return ip_sd_lookup (db, gid_address_vni (key),
 393                            &gid_address_ippref (key), 0);
 394     case GID_ADDR_MAC:
 395       return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
 396                             gid_address_mac (key), 0);
 397     case GID_ADDR_SRC_DST:
 398       switch (gid_address_sd_dst_type (key))
 399         {
 400         case FID_ADDR_IP_PREF:
 401           return ip_sd_lookup (db, gid_address_vni (key),
 402                                &gid_address_sd_dst_ippref (key),
 403                                &gid_address_sd_src_ippref (key));
 404           break;
 405         case FID_ADDR_MAC:
 406           return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
 407                                 gid_address_sd_dst_mac (key),
 408                                 gid_address_sd_src_mac (key));
 409           break;
 410         default:
 411           clib_warning ("Source/Dest address type %d not supported!",
 412                         gid_address_sd_dst_type (key));
 413           break;
 414         }
 415       break;
 416     case GID_ADDR_ARP:
 417       return arp_lookup (&db->arp_table, gid_address_arp_bd (key),
 418                          &gid_address_arp_ip4 (key));
 419     case GID_ADDR_NSH:
 420       return nsh_lookup (&db->nsh_table, gid_address_vni (key),
 421                          gid_address_nsh_spi (key), gid_address_nsh_si (key));
 422     default:
 423       clib_warning ("address type %d not supported!", gid_address_type (key));
 424       break;
 425     }
 426   return GID_LOOKUP_MISS;
 427 }
 428
 429 u32
 430 gid_dictionary_sd_lookup (gid_dictionary_t * db, gid_address_t * dst,
 431                           gid_address_t * src)
 432 {
 433   switch (gid_address_type (dst))
 434     {
 435     case GID_ADDR_IP_PREFIX:
 436       return ip_sd_lookup (db, gid_address_vni (dst),
 437                            &gid_address_ippref (dst),
 438                            &gid_address_ippref (src));
 439     case GID_ADDR_MAC:
 440       return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
 441                             gid_address_mac (dst), gid_address_mac (src));
 442     case GID_ADDR_SRC_DST:
 443       switch (gid_address_sd_dst_type (dst))
 444         {
 445         case FID_ADDR_IP_PREF:
 446           return ip_sd_lookup (db, gid_address_vni (dst),
 447                                &gid_address_sd_dst_ippref (dst),
 448                                &gid_address_sd_src_ippref (dst));
 449           break;
 450         case FID_ADDR_MAC:
 451           return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
 452                                 gid_address_sd_dst_mac (dst),
 453                                 gid_address_sd_src_mac (dst));
 454           break;
 455         default:
 456           clib_warning ("Source/Dest address type %d not supported!",
 457                         gid_address_sd_dst_type (dst));
 458           break;
 459         }
 460       break;
 461     case GID_ADDR_NSH:
 462       return gid_dictionary_lookup (db, dst);
 463       break;
 464     default:
 465       clib_warning ("address type %d not supported!", gid_address_type (dst));
 466       break;
 467     }
 468   return GID_LOOKUP_MISS;
 469 }
 470
 471 static void
 472 ip4_compute_prefix_lengths_in_search_order (gid_ip4_table_t * db)
 473 {
 474   int i;
 475   vec_reset_length (db->ip4_prefix_lengths_in_search_order);
 476   /* Note: bitmap reversed so this is in fact a longest prefix match */
 477
 478   /* *INDENT-OFF* */
 479   clib_bitmap_foreach (i, db->ip4_non_empty_dst_address_length_bitmap,
 480   ({
 481     int dst_address_length = 32 - i;
 482     vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
 483   }));
 484   /* *INDENT-ON* */
 485
 486 }
 487
 488 static u32
 489 add_del_ip4_key (gid_ip4_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 490                  u8 is_add)
 491 {
 492   BVT (clib_bihash_kv) kv, value;
 493   u32 old_val = ~0;
 494   ip4_address_t key;
 495   u8 plen = ip_prefix_len (pref);
 496
 497   clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
 498   key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
 499   if (is_add)
 500     {
 501       db->ip4_non_empty_dst_address_length_bitmap =
 502         clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 503                          32 - plen, 1);
 504       ip4_compute_prefix_lengths_in_search_order (db);
 505
 506       db->ip4_prefix_len_refcount[plen]++;
 507     }
 508   else
 509     {
 510       ASSERT (db->ip4_prefix_len_refcount[plen] != 0);
 511
 512       db->ip4_prefix_len_refcount[plen]--;
 513
 514       if (db->ip4_prefix_len_refcount[plen] == 0)
 515         {
 516           db->ip4_non_empty_dst_address_length_bitmap =
 517             clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 518                              32 - plen, 0);
 519           ip4_compute_prefix_lengths_in_search_order (db);
 520         }
 521     }
 522
 523   kv.key[0] = ((u64) vni << 32) | key.as_u32;
 524   kv.key[1] = 0;
 525   kv.key[2] = 0;
 526
 527   if (BV (clib_bihash_search) (&db->ip4_lookup_table, &kv, &value) == 0)
 528     old_val = value.value;
 529
 530   if (!is_add)
 531     {
 532       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
 533       db->count--;
 534     }
 535   else
 536     {
 537       kv.value = val;
 538       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
 539       db->count++;
 540     }
 541   return old_val;
 542 }
 543
 544 static void
 545 ip4_lookup_init (gid_ip4_table_t * db)
 546 {
 547   uword i;
 548
 549   memset (db->ip4_prefix_len_refcount, 0,
 550           sizeof (db->ip4_prefix_len_refcount));
 551
 552   for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
 553     {
 554       u32 m;
 555
 556       if (i < 32)
 557         m = pow2_mask (i) << (32 - i);
 558       else
 559         m = ~0;
 560       db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
 561     }
 562   if (db->ip4_lookup_table_nbuckets == 0)
 563     db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 564
 565   db->ip4_lookup_table_nbuckets =
 566     1 << max_log2 (db->ip4_lookup_table_nbuckets);
 567
 568   if (db->ip4_lookup_table_size == 0)
 569     db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 570
 571   BV (clib_bihash_init) (&db->ip4_lookup_table, "ip4 lookup table",
 572                          db->ip4_lookup_table_nbuckets,
 573                          db->ip4_lookup_table_size);
 574 }
 575
 576 static u32
 577 add_del_sd_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 578                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 579 {
 580   u32 sfi, old_val = ~0;
 581   gid_ip4_table_t *sfib;
 582
 583   sfi = ip4_lookup_exact_match (&db->dst_ip4_table, vni, dst_pref);
 584
 585   if (is_add)
 586     {
 587       if (GID_LOOKUP_MISS == sfi)
 588         {
 589           pool_get (db->src_ip4_table_pool, sfib);
 590           ip4_lookup_init (sfib);
 591           add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref,
 592                            sfib - db->src_ip4_table_pool, is_add);
 593           if (src_pref)
 594             add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 595           else
 596             {
 597               ip_prefix_t sp;
 598               memset (&sp, 0, sizeof (sp));
 599               add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 600             }
 601         }
 602       else
 603         {
 604           ASSERT (!pool_is_free_index (db->src_ip4_table_pool, sfi));
 605           sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 606           if (src_pref)
 607             {
 608               old_val = ip4_lookup_exact_match (sfib, 0, src_pref);
 609               add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 610             }
 611           else
 612             {
 613               ip_prefix_t sp;
 614               memset (&sp, 0, sizeof (sp));
 615               old_val =
 616                 add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 617             }
 618         }
 619     }
 620   else
 621     {
 622       if (GID_LOOKUP_MISS != sfi)
 623         {
 624           sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 625           if (src_pref)
 626             old_val = add_del_ip4_key (sfib, 0, src_pref, 0, is_add);
 627           else
 628             {
 629               ip_prefix_t sp;
 630               memset (&sp, 0, sizeof (sp));
 631               old_val = add_del_ip4_key (sfib, 0, &sp, 0, is_add);
 632             }
 633
 634           if (sfib->count == 0)
 635             add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref, 0, is_add);
 636         }
 637       else
 638         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 639                       dst_pref);
 640     }
 641   return old_val;
 642 }
 643
 644 static void
 645 ip6_compute_prefix_lengths_in_search_order (gid_ip6_table_t * db)
 646 {
 647   int i;
 648   vec_reset_length (db->ip6_prefix_lengths_in_search_order);
 649   /* Note: bitmap reversed so this is in fact a longest prefix match */
 650
 651   /* *INDENT-OFF* */
 652   clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap,
 653   ({
 654     int dst_address_length = 128 - i;
 655     vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
 656   }));
 657   /* *INDENT-ON* */
 658 }
 659
 660 static u32
 661 add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 662                  u8 is_add)
 663 {
 664   BVT (clib_bihash_kv) kv, value;
 665   u32 old_val = ~0;
 666   ip6_address_t key;
 667   u8 plen = ip_prefix_len (pref);
 668
 669   clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
 670   ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
 671   if (is_add)
 672     {
 673       db->ip6_non_empty_dst_address_length_bitmap =
 674         clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 675                          128 - plen, 1);
 676       ip6_compute_prefix_lengths_in_search_order (db);
 677       db->ip6_prefix_len_refcount[plen]++;
 678     }
 679   else
 680     {
 681       ASSERT (db->ip6_prefix_len_refcount[plen] != 0);
 682
 683       db->ip6_prefix_len_refcount[plen]--;
 684
 685       if (db->ip6_prefix_len_refcount[plen] == 0)
 686         {
 687           db->ip6_non_empty_dst_address_length_bitmap =
 688             clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 689                              128 - plen, 0);
 690           ip6_compute_prefix_lengths_in_search_order (db);
 691         }
 692     }
 693
 694   kv.key[0] = key.as_u64[0];
 695   kv.key[1] = key.as_u64[1];
 696   kv.key[2] = (u64) vni;
 697 //  kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);
 698
 699   if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
 700     old_val = value.value;
 701
 702   if (!is_add)
 703     {
 704       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
 705       db->count--;
 706     }
 707   else
 708     {
 709       kv.value = val;
 710       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
 711       db->count++;
 712     }
 713   return old_val;
 714 }
 715
 716 static u32
 717 add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
 718              u32 val, u8 is_add)
 719 {
 720   BVT (clib_bihash_kv) kv, value;
 721   u32 old_val = ~0;
 722
 723   make_mac_sd_key (&kv, vni, src_mac, dst_mac);
 724
 725   if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
 726     old_val = value.value;
 727
 728   if (!is_add)
 729     {
 730       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
 731       db->count--;
 732     }
 733   else
 734     {
 735       kv.value = val;
 736       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
 737       db->count++;
 738     }
 739   return old_val;
 740 }
 741
 742 static void
 743 ip6_lookup_init (gid_ip6_table_t * db)
 744 {
 745   uword i;
 746
 747   memset (db->ip6_prefix_len_refcount, 0,
 748           sizeof (db->ip6_prefix_len_refcount));
 749
 750   for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
 751     {
 752       u32 j, i0, i1;
 753
 754       i0 = i / 32;
 755       i1 = i % 32;
 756
 757       for (j = 0; j < i0; j++)
 758         db->ip6_fib_masks[i].as_u32[j] = ~0;
 759
 760       if (i1)
 761         db->ip6_fib_masks[i].as_u32[i0] =
 762           clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
 763     }
 764
 765   if (db->ip6_lookup_table_nbuckets == 0)
 766     db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 767
 768   db->ip6_lookup_table_nbuckets =
 769     1 << max_log2 (db->ip6_lookup_table_nbuckets);
 770
 771   if (db->ip6_lookup_table_size == 0)
 772     db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 773
 774   BV (clib_bihash_init) (&db->ip6_lookup_table, "ip6 lookup table",
 775                          db->ip6_lookup_table_nbuckets,
 776                          db->ip6_lookup_table_size);
 777 }
 778
 779 static u32
 780 add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 781                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 782 {
 783   u32 sfi, old_val = ~0;
 784   gid_ip6_table_t *sfib;
 785
 786   sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);
 787
 788   if (is_add)
 789     {
 790       if (GID_LOOKUP_MISS == sfi)
 791         {
 792           pool_get (db->src_ip6_table_pool, sfib);
 793           ip6_lookup_init (sfib);
 794           add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
 795                            sfib - db->src_ip6_table_pool, is_add);
 796           if (src_pref)
 797             add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 798           else
 799             {
 800               ip_prefix_t sp;
 801               memset (&sp, 0, sizeof (sp));
 802               ip_prefix_version (&sp) = IP6;
 803               add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 804             }
 805         }
 806       else
 807         {
 808           ASSERT (!pool_is_free_index (db->src_ip6_table_pool, sfi));
 809           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 810           if (src_pref)
 811             {
 812               old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
 813               add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 814             }
 815           else
 816             {
 817               ip_prefix_t sp;
 818               memset (&sp, 0, sizeof (sp));
 819               ip_prefix_version (&sp) = IP6;
 820               old_val =
 821                 add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 822             }
 823         }
 824     }
 825   else
 826     {
 827       if (GID_LOOKUP_MISS != sfi)
 828         {
 829           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 830           if (src_pref)
 831             old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
 832           else
 833             {
 834               ip_prefix_t sp;
 835               memset (&sp, 0, sizeof (sp));
 836               ip_prefix_version (&sp) = IP6;
 837               old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
 838             }
 839
 840           if (sfib->count == 0)
 841             add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
 842         }
 843       else
 844         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 845                       dst_pref);
 846     }
 847   return old_val;
 848 }
 849
 850 static u32
 851 add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
 852             ip_prefix_t * src_key, u32 value, u8 is_add)
 853 {
 854   switch (ip_prefix_version (dst_key))
 855     {
 856     case IP4:
 857       return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
 858       break;
 859     case IP6:
 860       return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
 861       break;
 862     default:
 863       clib_warning ("address type %d not supported!",
 864                     ip_prefix_version (dst_key));
 865       break;
 866     }
 867   return ~0;
 868 }
 869
 870 static u32
 871 add_del_sd (gid_dictionary_t * db, u32 vni, source_dest_t * key, u32 value,
 872             u8 is_add)
 873 {
 874   switch (sd_dst_type (key))
 875     {
 876     case FID_ADDR_IP_PREF:
 877       add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
 878                   value, is_add);
 879
 880     case FID_ADDR_MAC:
 881       return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
 882                           sd_src_mac (key), value, is_add);
 883
 884     default:
 885       clib_warning ("SD address type %d not supprted!", sd_dst_type (key));
 886       break;
 887     }
 888
 889   return ~0;
 890 }
 891
 892 static u64
 893 add_del_arp (gid_l2_arp_table_t * db, u32 bd, ip4_address_t * key, u64 value,
 894              u8 is_add)
 895 {
 896   BVT (clib_bihash_kv) kv, result;
 897   u32 old_val = ~0;
 898
 899   make_arp_key (&kv, bd, key);
 900   if (BV (clib_bihash_search) (&db->arp_lookup_table, &kv, &result) == 0)
 901     old_val = result.value;
 902
 903   if (is_add)
 904     {
 905       kv.value = value;
 906       BV (clib_bihash_add_del) (&db->arp_lookup_table, &kv, 1 /* is_add */ );
 907       db->count++;
 908     }
 909   else
 910     {
 911       BV (clib_bihash_add_del) (&db->arp_lookup_table, &kv, 0 /* is_add */ );
 912       db->count--;
 913     }
 914   return old_val;
 915 }
 916
 917 static u32
 918 add_del_nsh (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si, u32 value,
 919              u8 is_add)
 920 {
 921   BVT (clib_bihash_kv) kv, result;
 922   u32 old_val = ~0;
 923
 924   make_nsh_key (&kv, vni, spi, si);
 925   if (BV (clib_bihash_search) (&db->nsh_lookup_table, &kv, &result) == 0)
 926     old_val = result.value;
 927
 928   if (is_add)
 929     {
 930       kv.value = value;
 931       BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 1 /* is_add */ );
 932       db->count++;
 933     }
 934   else
 935     {
 936       BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 0 /* is_add */ );
 937       db->count--;
 938     }
 939   return old_val;
 940 }
 941
 942 u32
 943 gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u64 value,
 944                         u8 is_add)
 945 {
 946   switch (gid_address_type (key))
 947     {
 948     case GID_ADDR_IP_PREFIX:
 949       return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
 950                          0, (u32) value, is_add);
 951     case GID_ADDR_MAC:
 952       return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
 953                           gid_address_mac (key), 0, (u32) value, is_add);
 954     case GID_ADDR_SRC_DST:
 955       return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
 956                          (u32) value, is_add);
 957     case GID_ADDR_ARP:
 958       return add_del_arp (&db->arp_table, gid_address_arp_bd (key),
 959                           &gid_address_arp_ip4 (key), value, is_add);
 960     case GID_ADDR_NSH:
 961       return add_del_nsh (&db->nsh_table, gid_address_vni (key),
 962                           gid_address_nsh_spi (key), gid_address_nsh_si (key),
 963                           value, is_add);
 964
 965     default:
 966       clib_warning ("address type %d not supported!", gid_address_type (key));
 967       break;
 968     }
 969   return ~0;
 970 }
 971
 972 static void
 973 mac_lookup_init (gid_mac_table_t * db)
 974 {
 975   if (db->mac_lookup_table_nbuckets == 0)
 976     db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 977
 978   db->mac_lookup_table_nbuckets =
 979     1 << max_log2 (db->mac_lookup_table_nbuckets);
 980
 981   if (db->mac_lookup_table_size == 0)
 982     db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 983
 984   BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
 985                          db->mac_lookup_table_nbuckets,
 986                          db->mac_lookup_table_size);
 987 }
 988
 989 static void
 990 arp_lookup_init (gid_l2_arp_table_t * db)
 991 {
 992   if (db->arp_lookup_table_nbuckets == 0)
 993     db->arp_lookup_table_nbuckets = ARP_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 994
 995   db->arp_lookup_table_nbuckets =
 996     1 << max_log2 (db->arp_lookup_table_nbuckets);
 997
 998   if (db->arp_lookup_table_size == 0)
 999     db->arp_lookup_table_size = ARP_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1000
1001   BV (clib_bihash_init) (&db->arp_lookup_table, "arp lookup table",
1002                          db->arp_lookup_table_nbuckets,
1003                          db->arp_lookup_table_size);
1004 }
1005
1006 static void
1007 nsh_lookup_init (gid_nsh_table_t * db)
1008 {
1009   if (db->nsh_lookup_table_nbuckets == 0)
1010     db->nsh_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1011
1012   db->nsh_lookup_table_nbuckets =
1013     1 << max_log2 (db->nsh_lookup_table_nbuckets);
1014
1015   if (db->nsh_lookup_table_size == 0)
1016     db->nsh_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1017
1018   BV (clib_bihash_init) (&db->nsh_lookup_table, "nsh lookup table",
1019                          db->nsh_lookup_table_nbuckets,
1020                          db->nsh_lookup_table_size);
1021 }
1022
1023 void
1024 gid_dictionary_init (gid_dictionary_t * db)
1025 {
1026   ip4_lookup_init (&db->dst_ip4_table);
1027   ip6_lookup_init (&db->dst_ip6_table);
1028   mac_lookup_init (&db->sd_mac_table);
1029   arp_lookup_init (&db->arp_table);
1030   nsh_lookup_init (&db->nsh_table);
1031 }
1032
1033 /*
1034  * fd.io coding-style-patch-verification: ON
1035  *
1036  * Local Variables:
1037  * eval: (c-set-style "gnu")
1038  * End:
1039  */