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 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   /* *INDENT-OFF* */
 492   clib_bitmap_foreach (i, db->ip4_non_empty_dst_address_length_bitmap,
 493   ({
 494     int dst_address_length = 32 - i;
 495     vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
 496   }));
 497   /* *INDENT-ON* */
 498
 499 }
 500
 501 static u32
 502 add_del_ip4_key (gid_ip4_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 503                  u8 is_add)
 504 {
 505   BVT (clib_bihash_kv) kv, value;
 506   u32 old_val = ~0;
 507   ip4_address_t key;
 508   u8 plen = ip_prefix_len (pref);
 509
 510   clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
 511   key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
 512   if (is_add)
 513     {
 514       db->ip4_non_empty_dst_address_length_bitmap =
 515         clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 516                          32 - plen, 1);
 517       ip4_compute_prefix_lengths_in_search_order (db);
 518
 519       db->ip4_prefix_len_refcount[plen]++;
 520     }
 521   else
 522     {
 523       ASSERT (db->ip4_prefix_len_refcount[plen] != 0);
 524
 525       db->ip4_prefix_len_refcount[plen]--;
 526
 527       if (db->ip4_prefix_len_refcount[plen] == 0)
 528         {
 529           db->ip4_non_empty_dst_address_length_bitmap =
 530             clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 531                              32 - plen, 0);
 532           ip4_compute_prefix_lengths_in_search_order (db);
 533         }
 534     }
 535
 536   kv.key[0] = ((u64) vni << 32) | key.as_u32;
 537   kv.key[1] = 0;
 538   kv.key[2] = 0;
 539
 540   if (BV (clib_bihash_search) (&db->ip4_lookup_table, &kv, &value) == 0)
 541     old_val = value.value;
 542
 543   if (!is_add)
 544     {
 545       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
 546       db->count--;
 547     }
 548   else
 549     {
 550       kv.value = val;
 551       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
 552       db->count++;
 553     }
 554   return old_val;
 555 }
 556
 557 static void
 558 ip4_lookup_init (gid_ip4_table_t * db)
 559 {
 560   BVT (clib_bihash_init2_args) _a, *a = &_a;
 561   uword i;
 562
 563   clib_memset (db->ip4_prefix_len_refcount, 0,
 564                sizeof (db->ip4_prefix_len_refcount));
 565
 566   for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
 567     {
 568       u32 m;
 569
 570       if (i < 32)
 571         m = pow2_mask (i) << (32 - i);
 572       else
 573         m = ~0;
 574       db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
 575     }
 576   if (db->ip4_lookup_table_nbuckets == 0)
 577     db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 578
 579   db->ip4_lookup_table_nbuckets =
 580     1 << max_log2 (db->ip4_lookup_table_nbuckets);
 581
 582   if (db->ip4_lookup_table_size == 0)
 583     db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 584
 585   /*
 586    * Danger Will Robinson, Danger! gid_ip4_table_t's are allocated from
 587    * a pool. They MUST NOT be listed on the clib_all_bihashes list...
 588    */
 589   memset (a, 0, sizeof (*a));
 590   a->h = &db->ip4_lookup_table;
 591   a->name = "LISP ip4 lookup table";
 592   a->nbuckets = db->ip4_lookup_table_nbuckets;
 593   a->memory_size = db->ip4_lookup_table_size;
 594   a->dont_add_to_all_bihash_list = 1;   /* See comment above */
 595
 596   BV (clib_bihash_init2) (a);
 597 }
 598
 599 static u32
 600 add_del_sd_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 601                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 602 {
 603   u32 sfi, old_val = ~0;
 604   gid_ip4_table_t *sfib;
 605
 606   sfi = ip4_lookup_exact_match (&db->dst_ip4_table, vni, dst_pref);
 607
 608   if (is_add)
 609     {
 610       if (GID_LOOKUP_MISS == sfi)
 611         {
 612           pool_get (db->src_ip4_table_pool, sfib);
 613           ip4_lookup_init (sfib);
 614           add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref,
 615                            sfib - db->src_ip4_table_pool, is_add);
 616           if (src_pref)
 617             add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 618           else
 619             {
 620               ip_prefix_t sp;
 621               clib_memset (&sp, 0, sizeof (sp));
 622               add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 623             }
 624         }
 625       else
 626         {
 627           ASSERT (!pool_is_free_index (db->src_ip4_table_pool, sfi));
 628           sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 629           if (src_pref)
 630             {
 631               old_val = ip4_lookup_exact_match (sfib, 0, src_pref);
 632               add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 633             }
 634           else
 635             {
 636               ip_prefix_t sp;
 637               clib_memset (&sp, 0, sizeof (sp));
 638               old_val =
 639                 add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 640             }
 641         }
 642     }
 643   else
 644     {
 645       if (GID_LOOKUP_MISS != sfi)
 646         {
 647           sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 648           if (src_pref)
 649             old_val = add_del_ip4_key (sfib, 0, src_pref, 0, is_add);
 650           else
 651             {
 652               ip_prefix_t sp;
 653               clib_memset (&sp, 0, sizeof (sp));
 654               old_val = add_del_ip4_key (sfib, 0, &sp, 0, is_add);
 655             }
 656
 657           if (sfib->count == 0)
 658             add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref, 0, is_add);
 659         }
 660       else
 661         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 662                       dst_pref);
 663     }
 664   return old_val;
 665 }
 666
 667 static void
 668 ip6_compute_prefix_lengths_in_search_order (gid_ip6_table_t * db)
 669 {
 670   int i;
 671   vec_reset_length (db->ip6_prefix_lengths_in_search_order);
 672   /* Note: bitmap reversed so this is in fact a longest prefix match */
 673
 674   /* *INDENT-OFF* */
 675   clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap,
 676   ({
 677     int dst_address_length = 128 - i;
 678     vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
 679   }));
 680   /* *INDENT-ON* */
 681 }
 682
 683 static u32
 684 add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 685                  u8 is_add)
 686 {
 687   BVT (clib_bihash_kv) kv, value;
 688   u32 old_val = ~0;
 689   ip6_address_t key;
 690   u8 plen = ip_prefix_len (pref);
 691
 692   clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
 693   ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
 694   if (is_add)
 695     {
 696       db->ip6_non_empty_dst_address_length_bitmap =
 697         clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 698                          128 - plen, 1);
 699       ip6_compute_prefix_lengths_in_search_order (db);
 700       db->ip6_prefix_len_refcount[plen]++;
 701     }
 702   else
 703     {
 704       ASSERT (db->ip6_prefix_len_refcount[plen] != 0);
 705
 706       db->ip6_prefix_len_refcount[plen]--;
 707
 708       if (db->ip6_prefix_len_refcount[plen] == 0)
 709         {
 710           db->ip6_non_empty_dst_address_length_bitmap =
 711             clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 712                              128 - plen, 0);
 713           ip6_compute_prefix_lengths_in_search_order (db);
 714         }
 715     }
 716
 717   kv.key[0] = key.as_u64[0];
 718   kv.key[1] = key.as_u64[1];
 719   kv.key[2] = (u64) vni;
 720 //  kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);
 721
 722   if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
 723     old_val = value.value;
 724
 725   if (!is_add)
 726     {
 727       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
 728       db->count--;
 729     }
 730   else
 731     {
 732       kv.value = val;
 733       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
 734       db->count++;
 735     }
 736   return old_val;
 737 }
 738
 739 static u32
 740 add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
 741              u32 val, u8 is_add)
 742 {
 743   BVT (clib_bihash_kv) kv, value;
 744   u32 old_val = ~0;
 745
 746   make_mac_sd_key (&kv, vni, src_mac, dst_mac);
 747
 748   if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
 749     old_val = value.value;
 750
 751   if (!is_add)
 752     {
 753       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
 754       db->count--;
 755     }
 756   else
 757     {
 758       kv.value = val;
 759       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
 760       db->count++;
 761     }
 762   return old_val;
 763 }
 764
 765 static void
 766 ip6_lookup_init (gid_ip6_table_t * db)
 767 {
 768   uword i;
 769   BVT (clib_bihash_init2_args) _a, *a = &_a;
 770
 771   clib_memset (db->ip6_prefix_len_refcount, 0,
 772                sizeof (db->ip6_prefix_len_refcount));
 773
 774   for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
 775     {
 776       u32 j, i0, i1;
 777
 778       i0 = i / 32;
 779       i1 = i % 32;
 780
 781       for (j = 0; j < i0; j++)
 782         db->ip6_fib_masks[i].as_u32[j] = ~0;
 783
 784       if (i1)
 785         db->ip6_fib_masks[i].as_u32[i0] =
 786           clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
 787     }
 788
 789   if (db->ip6_lookup_table_nbuckets == 0)
 790     db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 791
 792   db->ip6_lookup_table_nbuckets =
 793     1 << max_log2 (db->ip6_lookup_table_nbuckets);
 794
 795   if (db->ip6_lookup_table_size == 0)
 796     db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 797
 798   /*
 799    * Danger Will Robinson, Danger! gid_ip6_table_t's are allocated from
 800    * a pool. They MUST NOT be listed on the clib_all_bihashes list...
 801    */
 802   memset (a, 0, sizeof (*a));
 803   a->h = &db->ip6_lookup_table;
 804   a->name = "LISP ip6 lookup table";
 805   a->nbuckets = db->ip6_lookup_table_nbuckets;
 806   a->memory_size = db->ip6_lookup_table_size;
 807   a->dont_add_to_all_bihash_list = 1;   /* See comment above */
 808
 809   BV (clib_bihash_init2) (a);
 810 }
 811
 812 static u32
 813 add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 814                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 815 {
 816   u32 sfi, old_val = ~0;
 817   gid_ip6_table_t *sfib;
 818
 819   sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);
 820
 821   if (is_add)
 822     {
 823       if (GID_LOOKUP_MISS == sfi)
 824         {
 825           pool_get (db->src_ip6_table_pool, sfib);
 826           ip6_lookup_init (sfib);
 827           add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
 828                            sfib - db->src_ip6_table_pool, is_add);
 829           if (src_pref)
 830             add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 831           else
 832             {
 833               ip_prefix_t sp;
 834               clib_memset (&sp, 0, sizeof (sp));
 835               ip_prefix_version (&sp) = AF_IP6;
 836               add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 837             }
 838         }
 839       else
 840         {
 841           ASSERT (!pool_is_free_index (db->src_ip6_table_pool, sfi));
 842           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 843           if (src_pref)
 844             {
 845               old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
 846               add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 847             }
 848           else
 849             {
 850               ip_prefix_t sp;
 851               clib_memset (&sp, 0, sizeof (sp));
 852               ip_prefix_version (&sp) = AF_IP6;
 853               old_val =
 854                 add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 855             }
 856         }
 857     }
 858   else
 859     {
 860       if (GID_LOOKUP_MISS != sfi)
 861         {
 862           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 863           if (src_pref)
 864             old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
 865           else
 866             {
 867               ip_prefix_t sp;
 868               clib_memset (&sp, 0, sizeof (sp));
 869               ip_prefix_version (&sp) = AF_IP6;
 870               old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
 871             }
 872
 873           if (sfib->count == 0)
 874             add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
 875         }
 876       else
 877         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 878                       dst_pref);
 879     }
 880   return old_val;
 881 }
 882
 883 static u32
 884 add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
 885             ip_prefix_t * src_key, u32 value, u8 is_add)
 886 {
 887   switch (ip_prefix_version (dst_key))
 888     {
 889     case AF_IP4:
 890       return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
 891       break;
 892     case AF_IP6:
 893       return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
 894       break;
 895     default:
 896       clib_warning ("address type %d not supported!",
 897                     ip_prefix_version (dst_key));
 898       break;
 899     }
 900   return ~0;
 901 }
 902
 903 static u32
 904 add_del_sd (gid_dictionary_t * db, u32 vni, source_dest_t * key, u32 value,
 905             u8 is_add)
 906 {
 907   switch (sd_dst_type (key))
 908     {
 909     case FID_ADDR_IP_PREF:
 910       add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
 911                   value, is_add);
 912
 913     case FID_ADDR_MAC:
 914       return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
 915                           sd_src_mac (key), value, is_add);
 916
 917     default:
 918       clib_warning ("SD address type %d not supported!", sd_dst_type (key));
 919       break;
 920     }
 921
 922   return ~0;
 923 }
 924
 925 static u64
 926 add_del_arp_ndp (gid_l2_arp_ndp_table_t * db, u32 bd, ip_address_t * key,
 927                  u64 value, u8 is_add)
 928 {
 929   BVT (clib_bihash_kv) kv, result;
 930   u32 old_val = ~0;
 931
 932   make_arp_ndp_key (&kv, bd, key);
 933   if (BV (clib_bihash_search) (&db->arp_ndp_lookup_table, &kv, &result) == 0)
 934     old_val = result.value;
 935
 936   if (is_add)
 937     {
 938       kv.value = value;
 939       BV (clib_bihash_add_del) (&db->arp_ndp_lookup_table, &kv,
 940                                 1 /* is_add */ );
 941       db->count++;
 942     }
 943   else
 944     {
 945       BV (clib_bihash_add_del) (&db->arp_ndp_lookup_table, &kv,
 946                                 0 /* is_add */ );
 947       db->count--;
 948     }
 949   return old_val;
 950 }
 951
 952 static u32
 953 add_del_nsh (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si, u32 value,
 954              u8 is_add)
 955 {
 956   BVT (clib_bihash_kv) kv, result;
 957   u32 old_val = ~0;
 958
 959   make_nsh_key (&kv, vni, spi, si);
 960   if (BV (clib_bihash_search) (&db->nsh_lookup_table, &kv, &result) == 0)
 961     old_val = result.value;
 962
 963   if (is_add)
 964     {
 965       kv.value = value;
 966       BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 1 /* is_add */ );
 967       db->count++;
 968     }
 969   else
 970     {
 971       BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 0 /* is_add */ );
 972       db->count--;
 973     }
 974   return old_val;
 975 }
 976
 977 u32
 978 gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u64 value,
 979                         u8 is_add)
 980 {
 981   switch (gid_address_type (key))
 982     {
 983     case GID_ADDR_IP_PREFIX:
 984       return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
 985                          0, (u32) value, is_add);
 986     case GID_ADDR_MAC:
 987       return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
 988                           gid_address_mac (key), 0, (u32) value, is_add);
 989     case GID_ADDR_SRC_DST:
 990       return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
 991                          (u32) value, is_add);
 992     case GID_ADDR_ARP:
 993     case GID_ADDR_NDP:
 994       return add_del_arp_ndp (&db->arp_ndp_table,
 995                               gid_address_arp_ndp_bd (key),
 996                               &gid_address_arp_ndp_ip (key), value, is_add);
 997     case GID_ADDR_NSH:
 998       return add_del_nsh (&db->nsh_table, gid_address_vni (key),
 999                           gid_address_nsh_spi (key), gid_address_nsh_si (key),
1000                           value, is_add);
1001
1002     default:
1003       clib_warning ("address type %d not supported!", gid_address_type (key));
1004       break;
1005     }
1006   return ~0;
1007 }
1008
1009 static void
1010 mac_lookup_init (gid_mac_table_t * db)
1011 {
1012   if (db->mac_lookup_table_nbuckets == 0)
1013     db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1014
1015   db->mac_lookup_table_nbuckets =
1016     1 << max_log2 (db->mac_lookup_table_nbuckets);
1017
1018   if (db->mac_lookup_table_size == 0)
1019     db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1020
1021   BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
1022                          db->mac_lookup_table_nbuckets,
1023                          db->mac_lookup_table_size);
1024 }
1025
1026 static void
1027 arp_ndp_lookup_init (gid_l2_arp_ndp_table_t * db)
1028 {
1029   if (db->arp_ndp_lookup_table_nbuckets == 0)
1030     db->arp_ndp_lookup_table_nbuckets =
1031       ARP_NDP_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1032
1033   db->arp_ndp_lookup_table_nbuckets =
1034     1 << max_log2 (db->arp_ndp_lookup_table_nbuckets);
1035
1036   if (db->arp_ndp_lookup_table_size == 0)
1037     db->arp_ndp_lookup_table_size = ARP_NDP_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1038
1039   BV (clib_bihash_init) (&db->arp_ndp_lookup_table, "arp ndp lookup table",
1040                          db->arp_ndp_lookup_table_nbuckets,
1041                          db->arp_ndp_lookup_table_size);
1042 }
1043
1044 static void
1045 nsh_lookup_init (gid_nsh_table_t * db)
1046 {
1047   if (db->nsh_lookup_table_nbuckets == 0)
1048     db->nsh_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1049
1050   db->nsh_lookup_table_nbuckets =
1051     1 << max_log2 (db->nsh_lookup_table_nbuckets);
1052
1053   if (db->nsh_lookup_table_size == 0)
1054     db->nsh_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1055
1056   BV (clib_bihash_init) (&db->nsh_lookup_table, "nsh lookup table",
1057                          db->nsh_lookup_table_nbuckets,
1058                          db->nsh_lookup_table_size);
1059 }
1060
1061 void
1062 gid_dictionary_init (gid_dictionary_t * db)
1063 {
1064   ip4_lookup_init (&db->dst_ip4_table);
1065   ip6_lookup_init (&db->dst_ip6_table);
1066   mac_lookup_init (&db->sd_mac_table);
1067   arp_ndp_lookup_init (&db->arp_ndp_table);
1068   nsh_lookup_init (&db->nsh_table);
1069 }
1070
1071 /*
1072  * fd.io coding-style-patch-verification: ON
1073  *
1074  * Local Variables:
1075  * eval: (c-set-style "gnu")
1076  * End:
1077  */