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 u64
 349 arp_lookup (gid_l2_arp_table_t * db, u32 bd, ip4_address_t * key)
 350 {
 351   int rv;
 352   BVT (clib_bihash_kv) kv, value;
 353
 354   make_arp_key (&kv, bd, key);
 355   rv = BV (clib_bihash_search_inline_2) (&db->arp_lookup_table, &kv, &value);
 356
 357   if (rv == 0)
 358     return value.value;
 359
 360   return GID_LOOKUP_MISS_L2;
 361 }
 362
 363 u64
 364 gid_dictionary_lookup (gid_dictionary_t * db, gid_address_t * key)
 365 {
 366   switch (gid_address_type (key))
 367     {
 368     case GID_ADDR_IP_PREFIX:
 369       return ip_sd_lookup (db, gid_address_vni (key),
 370                            &gid_address_ippref (key), 0);
 371     case GID_ADDR_MAC:
 372       return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
 373                             gid_address_mac (key), 0);
 374     case GID_ADDR_SRC_DST:
 375       switch (gid_address_sd_dst_type (key))
 376         {
 377         case FID_ADDR_IP_PREF:
 378           return ip_sd_lookup (db, gid_address_vni (key),
 379                                &gid_address_sd_dst_ippref (key),
 380                                &gid_address_sd_src_ippref (key));
 381           break;
 382         case FID_ADDR_MAC:
 383           return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
 384                                 gid_address_sd_dst_mac (key),
 385                                 gid_address_sd_src_mac (key));
 386           break;
 387         default:
 388           clib_warning ("Source/Dest address type %d not supported!",
 389                         gid_address_sd_dst_type (key));
 390           break;
 391         }
 392       break;
 393     case GID_ADDR_ARP:
 394       return arp_lookup (&db->arp_table, gid_address_arp_bd (key),
 395                          &gid_address_arp_ip4 (key));
 396     default:
 397       clib_warning ("address type %d not supported!", gid_address_type (key));
 398       break;
 399     }
 400   return GID_LOOKUP_MISS;
 401 }
 402
 403 u32
 404 gid_dictionary_sd_lookup (gid_dictionary_t * db, gid_address_t * dst,
 405                           gid_address_t * src)
 406 {
 407   switch (gid_address_type (dst))
 408     {
 409     case GID_ADDR_IP_PREFIX:
 410       return ip_sd_lookup (db, gid_address_vni (dst),
 411                            &gid_address_ippref (dst),
 412                            &gid_address_ippref (src));
 413     case GID_ADDR_MAC:
 414       return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
 415                             gid_address_mac (dst), gid_address_mac (src));
 416     case GID_ADDR_SRC_DST:
 417       switch (gid_address_sd_dst_type (dst))
 418         {
 419         case FID_ADDR_IP_PREF:
 420           return ip_sd_lookup (db, gid_address_vni (dst),
 421                                &gid_address_sd_dst_ippref (dst),
 422                                &gid_address_sd_src_ippref (dst));
 423           break;
 424         case FID_ADDR_MAC:
 425           return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
 426                                 gid_address_sd_dst_mac (dst),
 427                                 gid_address_sd_src_mac (dst));
 428           break;
 429         default:
 430           clib_warning ("Source/Dest address type %d not supported!",
 431                         gid_address_sd_dst_type (dst));
 432           break;
 433         }
 434       break;
 435     default:
 436       clib_warning ("address type %d not supported!", gid_address_type (dst));
 437       break;
 438     }
 439   return GID_LOOKUP_MISS;
 440 }
 441
 442 static void
 443 ip4_compute_prefix_lengths_in_search_order (gid_ip4_table_t * db)
 444 {
 445   int i;
 446   vec_reset_length (db->ip4_prefix_lengths_in_search_order);
 447   /* Note: bitmap reversed so this is in fact a longest prefix match */
 448
 449   /* *INDENT-OFF* */
 450   clib_bitmap_foreach (i, db->ip4_non_empty_dst_address_length_bitmap,
 451   ({
 452     int dst_address_length = 32 - i;
 453     vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
 454   }));
 455   /* *INDENT-ON* */
 456
 457 }
 458
 459 static u32
 460 add_del_ip4_key (gid_ip4_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 461                  u8 is_add)
 462 {
 463   BVT (clib_bihash_kv) kv, value;
 464   u32 old_val = ~0;
 465   ip4_address_t key;
 466   u8 plen = ip_prefix_len (pref);
 467
 468   clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
 469   key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
 470   if (is_add)
 471     {
 472       db->ip4_non_empty_dst_address_length_bitmap =
 473         clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 474                          32 - plen, 1);
 475       ip4_compute_prefix_lengths_in_search_order (db);
 476
 477       db->ip4_prefix_len_refcount[plen]++;
 478     }
 479   else
 480     {
 481       ASSERT (db->ip4_prefix_len_refcount[plen] != 0);
 482
 483       db->ip4_prefix_len_refcount[plen]--;
 484
 485       if (db->ip4_prefix_len_refcount[plen] == 0)
 486         {
 487           db->ip4_non_empty_dst_address_length_bitmap =
 488             clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 489                              32 - plen, 0);
 490           ip4_compute_prefix_lengths_in_search_order (db);
 491         }
 492     }
 493
 494   kv.key[0] = ((u64) vni << 32) | key.as_u32;
 495   kv.key[1] = 0;
 496   kv.key[2] = 0;
 497
 498   if (BV (clib_bihash_search) (&db->ip4_lookup_table, &kv, &value) == 0)
 499     old_val = value.value;
 500
 501   if (!is_add)
 502     {
 503       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
 504       db->count--;
 505     }
 506   else
 507     {
 508       kv.value = val;
 509       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
 510       db->count++;
 511     }
 512   return old_val;
 513 }
 514
 515 static void
 516 ip4_lookup_init (gid_ip4_table_t * db)
 517 {
 518   uword i;
 519
 520   memset (db->ip4_prefix_len_refcount, 0,
 521           sizeof (db->ip4_prefix_len_refcount));
 522
 523   for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
 524     {
 525       u32 m;
 526
 527       if (i < 32)
 528         m = pow2_mask (i) << (32 - i);
 529       else
 530         m = ~0;
 531       db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
 532     }
 533   if (db->ip4_lookup_table_nbuckets == 0)
 534     db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 535
 536   db->ip4_lookup_table_nbuckets =
 537     1 << max_log2 (db->ip4_lookup_table_nbuckets);
 538
 539   if (db->ip4_lookup_table_size == 0)
 540     db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 541
 542   BV (clib_bihash_init) (&db->ip4_lookup_table, "ip4 lookup table",
 543                          db->ip4_lookup_table_nbuckets,
 544                          db->ip4_lookup_table_size);
 545 }
 546
 547 static u32
 548 add_del_sd_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 549                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 550 {
 551   u32 sfi, old_val = ~0;
 552   gid_ip4_table_t *sfib;
 553
 554   sfi = ip4_lookup_exact_match (&db->dst_ip4_table, vni, dst_pref);
 555
 556   if (is_add)
 557     {
 558       if (GID_LOOKUP_MISS == sfi)
 559         {
 560           pool_get (db->src_ip4_table_pool, sfib);
 561           ip4_lookup_init (sfib);
 562           add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref,
 563                            sfib - db->src_ip4_table_pool, is_add);
 564           if (src_pref)
 565             add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 566           else
 567             {
 568               ip_prefix_t sp;
 569               memset (&sp, 0, sizeof (sp));
 570               add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 571             }
 572         }
 573       else
 574         {
 575           ASSERT (!pool_is_free_index (db->src_ip4_table_pool, sfi));
 576           sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 577           if (src_pref)
 578             {
 579               old_val = ip4_lookup_exact_match (sfib, 0, src_pref);
 580               add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 581             }
 582           else
 583             {
 584               ip_prefix_t sp;
 585               memset (&sp, 0, sizeof (sp));
 586               old_val =
 587                 add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 588             }
 589         }
 590     }
 591   else
 592     {
 593       if (GID_LOOKUP_MISS != sfi)
 594         {
 595           sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 596           if (src_pref)
 597             old_val = add_del_ip4_key (sfib, 0, src_pref, 0, is_add);
 598           else
 599             {
 600               ip_prefix_t sp;
 601               memset (&sp, 0, sizeof (sp));
 602               old_val = add_del_ip4_key (sfib, 0, &sp, 0, is_add);
 603             }
 604
 605           if (sfib->count == 0)
 606             add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref, 0, is_add);
 607         }
 608       else
 609         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 610                       dst_pref);
 611     }
 612   return old_val;
 613 }
 614
 615 static void
 616 ip6_compute_prefix_lengths_in_search_order (gid_ip6_table_t * db)
 617 {
 618   int i;
 619   vec_reset_length (db->ip6_prefix_lengths_in_search_order);
 620   /* Note: bitmap reversed so this is in fact a longest prefix match */
 621
 622   /* *INDENT-OFF* */
 623   clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap,
 624   ({
 625     int dst_address_length = 128 - i;
 626     vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
 627   }));
 628   /* *INDENT-ON* */
 629 }
 630
 631 static u32
 632 add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 633                  u8 is_add)
 634 {
 635   BVT (clib_bihash_kv) kv, value;
 636   u32 old_val = ~0;
 637   ip6_address_t key;
 638   u8 plen = ip_prefix_len (pref);
 639
 640   clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
 641   ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
 642   if (is_add)
 643     {
 644       db->ip6_non_empty_dst_address_length_bitmap =
 645         clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 646                          128 - plen, 1);
 647       ip6_compute_prefix_lengths_in_search_order (db);
 648       db->ip6_prefix_len_refcount[plen]++;
 649     }
 650   else
 651     {
 652       ASSERT (db->ip6_prefix_len_refcount[plen] != 0);
 653
 654       db->ip6_prefix_len_refcount[plen]--;
 655
 656       if (db->ip6_prefix_len_refcount[plen] == 0)
 657         {
 658           db->ip6_non_empty_dst_address_length_bitmap =
 659             clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 660                              128 - plen, 0);
 661           ip6_compute_prefix_lengths_in_search_order (db);
 662         }
 663     }
 664
 665   kv.key[0] = key.as_u64[0];
 666   kv.key[1] = key.as_u64[1];
 667   kv.key[2] = (u64) vni;
 668 //  kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);
 669
 670   if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
 671     old_val = value.value;
 672
 673   if (!is_add)
 674     {
 675       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
 676       db->count--;
 677     }
 678   else
 679     {
 680       kv.value = val;
 681       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
 682       db->count++;
 683     }
 684   return old_val;
 685 }
 686
 687 static u32
 688 add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
 689              u32 val, u8 is_add)
 690 {
 691   BVT (clib_bihash_kv) kv, value;
 692   u32 old_val = ~0;
 693
 694   make_mac_sd_key (&kv, vni, src_mac, dst_mac);
 695
 696   if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
 697     old_val = value.value;
 698
 699   if (!is_add)
 700     {
 701       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
 702       db->count--;
 703     }
 704   else
 705     {
 706       kv.value = val;
 707       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
 708       db->count++;
 709     }
 710   return old_val;
 711 }
 712
 713 static void
 714 ip6_lookup_init (gid_ip6_table_t * db)
 715 {
 716   uword i;
 717
 718   memset (db->ip6_prefix_len_refcount, 0,
 719           sizeof (db->ip6_prefix_len_refcount));
 720
 721   for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
 722     {
 723       u32 j, i0, i1;
 724
 725       i0 = i / 32;
 726       i1 = i % 32;
 727
 728       for (j = 0; j < i0; j++)
 729         db->ip6_fib_masks[i].as_u32[j] = ~0;
 730
 731       if (i1)
 732         db->ip6_fib_masks[i].as_u32[i0] =
 733           clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
 734     }
 735
 736   if (db->ip6_lookup_table_nbuckets == 0)
 737     db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 738
 739   db->ip6_lookup_table_nbuckets =
 740     1 << max_log2 (db->ip6_lookup_table_nbuckets);
 741
 742   if (db->ip6_lookup_table_size == 0)
 743     db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 744
 745   BV (clib_bihash_init) (&db->ip6_lookup_table, "ip6 lookup table",
 746                          db->ip6_lookup_table_nbuckets,
 747                          db->ip6_lookup_table_size);
 748 }
 749
 750 static u32
 751 add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 752                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 753 {
 754   u32 sfi, old_val = ~0;
 755   gid_ip6_table_t *sfib;
 756
 757   sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);
 758
 759   if (is_add)
 760     {
 761       if (GID_LOOKUP_MISS == sfi)
 762         {
 763           pool_get (db->src_ip6_table_pool, sfib);
 764           ip6_lookup_init (sfib);
 765           add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
 766                            sfib - db->src_ip6_table_pool, is_add);
 767           if (src_pref)
 768             add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 769           else
 770             {
 771               ip_prefix_t sp;
 772               memset (&sp, 0, sizeof (sp));
 773               ip_prefix_version (&sp) = IP6;
 774               add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 775             }
 776         }
 777       else
 778         {
 779           ASSERT (!pool_is_free_index (db->src_ip6_table_pool, sfi));
 780           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 781           if (src_pref)
 782             {
 783               old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
 784               add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 785             }
 786           else
 787             {
 788               ip_prefix_t sp;
 789               memset (&sp, 0, sizeof (sp));
 790               ip_prefix_version (&sp) = IP6;
 791               old_val =
 792                 add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 793             }
 794         }
 795     }
 796   else
 797     {
 798       if (GID_LOOKUP_MISS != sfi)
 799         {
 800           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 801           if (src_pref)
 802             old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
 803           else
 804             {
 805               ip_prefix_t sp;
 806               memset (&sp, 0, sizeof (sp));
 807               ip_prefix_version (&sp) = IP6;
 808               old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
 809             }
 810
 811           if (sfib->count == 0)
 812             add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
 813         }
 814       else
 815         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 816                       dst_pref);
 817     }
 818   return old_val;
 819 }
 820
 821 static u32
 822 add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
 823             ip_prefix_t * src_key, u32 value, u8 is_add)
 824 {
 825   switch (ip_prefix_version (dst_key))
 826     {
 827     case IP4:
 828       return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
 829       break;
 830     case IP6:
 831       return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
 832       break;
 833     default:
 834       clib_warning ("address type %d not supported!",
 835                     ip_prefix_version (dst_key));
 836       break;
 837     }
 838   return ~0;
 839 }
 840
 841 static u32
 842 add_del_sd (gid_dictionary_t * db, u32 vni, source_dest_t * key, u32 value,
 843             u8 is_add)
 844 {
 845   switch (sd_dst_type (key))
 846     {
 847     case FID_ADDR_IP_PREF:
 848       add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
 849                   value, is_add);
 850
 851     case FID_ADDR_MAC:
 852       return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
 853                           sd_src_mac (key), value, is_add);
 854
 855     default:
 856       clib_warning ("SD address type %d not supprted!", sd_dst_type (key));
 857       break;
 858     }
 859
 860   return ~0;
 861 }
 862
 863 static u32
 864 add_del_arp (gid_l2_arp_table_t * db, u32 bd, ip4_address_t * key, u64 value,
 865              u8 is_add)
 866 {
 867   BVT (clib_bihash_kv) kv, result;
 868   u32 old_val = ~0;
 869
 870   make_arp_key (&kv, bd, key);
 871   if (BV (clib_bihash_search) (&db->arp_lookup_table, &kv, &result) == 0)
 872     old_val = result.value;
 873
 874   if (is_add)
 875     {
 876       kv.value = value;
 877       BV (clib_bihash_add_del) (&db->arp_lookup_table, &kv, 1 /* is_add */ );
 878       db->count++;
 879     }
 880   else
 881     {
 882       BV (clib_bihash_add_del) (&db->arp_lookup_table, &kv, 0 /* is_add */ );
 883       db->count--;
 884     }
 885   return old_val;
 886 }
 887
 888 u32
 889 gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u64 value,
 890                         u8 is_add)
 891 {
 892   switch (gid_address_type (key))
 893     {
 894     case GID_ADDR_IP_PREFIX:
 895       return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
 896                          0, (u32) value, is_add);
 897     case GID_ADDR_MAC:
 898       return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
 899                           gid_address_mac (key), 0, (u32) value, is_add);
 900     case GID_ADDR_SRC_DST:
 901       return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
 902                          (u32) value, is_add);
 903     case GID_ADDR_ARP:
 904       return add_del_arp (&db->arp_table, gid_address_arp_bd (key),
 905                           &gid_address_arp_ip4 (key), value, is_add);
 906     default:
 907       clib_warning ("address type %d not supported!", gid_address_type (key));
 908       break;
 909     }
 910   return ~0;
 911 }
 912
 913 static void
 914 mac_lookup_init (gid_mac_table_t * db)
 915 {
 916   if (db->mac_lookup_table_nbuckets == 0)
 917     db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 918
 919   db->mac_lookup_table_nbuckets =
 920     1 << max_log2 (db->mac_lookup_table_nbuckets);
 921
 922   if (db->mac_lookup_table_size == 0)
 923     db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 924
 925   BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
 926                          db->mac_lookup_table_nbuckets,
 927                          db->mac_lookup_table_size);
 928 }
 929
 930 static void
 931 arp_lookup_init (gid_l2_arp_table_t * db)
 932 {
 933   if (db->arp_lookup_table_nbuckets == 0)
 934     db->arp_lookup_table_nbuckets = ARP_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 935
 936   db->arp_lookup_table_nbuckets =
 937     1 << max_log2 (db->arp_lookup_table_nbuckets);
 938
 939   if (db->arp_lookup_table_size == 0)
 940     db->arp_lookup_table_size = ARP_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 941
 942   BV (clib_bihash_init) (&db->arp_lookup_table, "arp lookup table",
 943                          db->arp_lookup_table_nbuckets,
 944                          db->arp_lookup_table_size);
 945 }
 946
 947 void
 948 gid_dictionary_init (gid_dictionary_t * db)
 949 {
 950   ip4_lookup_init (&db->dst_ip4_table);
 951   ip6_lookup_init (&db->dst_ip6_table);
 952   mac_lookup_init (&db->sd_mac_table);
 953   arp_lookup_init (&db->arp_table);
 954 }
 955
 956 /*
 957  * fd.io coding-style-patch-verification: ON
 958  *
 959  * Local Variables:
 960  * eval: (c-set-style "gnu")
 961  * End:
 962  */