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