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_ndp_entry (gid_dictionary_t * db, void (*cb)
 143                                    (BVT (clib_bihash_kv) * kvp, void *arg),
 144                                    void *ht)
 145 {
 146   gid_l2_arp_ndp_table_t *tab = &db->arp_ndp_table;
 147   BV (clib_bihash_foreach_key_value_pair) (&tab->arp_ndp_lookup_table, cb,
 148                                            ht);
 149 }
 150
 151 static void
 152 make_mac_sd_key (BVT (clib_bihash_kv) * kv, u32 vni, u8 src_mac[6],
 153                  u8 dst_mac[6])
 154 {
 155   kv->key[0] = (u64) vni;
 156   kv->key[1] = mac_to_u64 (dst_mac);
 157   kv->key[2] = src_mac ? mac_to_u64 (src_mac) : (u64) 0;
 158 }
 159
 160 static u32
 161 mac_sd_lookup (gid_mac_table_t * db, u32 vni, u8 * dst, u8 * src)
 162 {
 163   int rv;
 164   BVT (clib_bihash_kv) kv, value;
 165
 166   make_mac_sd_key (&kv, vni, src, dst);
 167   rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv, &value);
 168
 169   /* no match, try with src 0, catch all for dst */
 170   if (rv != 0)
 171     {
 172       kv.key[2] = 0;
 173       rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv,
 174                                              &value);
 175       if (rv == 0)
 176         return value.value;
 177     }
 178   else
 179     return value.value;
 180
 181   return GID_LOOKUP_MISS;
 182 }
 183
 184 static u32
 185 ip4_lookup_exact_match (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
 186 {
 187   int rv;
 188   BVT (clib_bihash_kv) kv, value;
 189
 190   ip4_address_t *mask;
 191
 192   mask = &db->ip4_fib_masks[ip_prefix_len (key)];
 193
 194   kv.key[0] = ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
 195   kv.key[1] = 0;
 196   kv.key[2] = 0;
 197
 198   rv = BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
 199   if (rv == 0)
 200     return value.value;
 201
 202   return GID_LOOKUP_MISS;
 203 }
 204
 205 static u32
 206 ip4_lookup (gid_ip4_table_t * db, u32 vni, ip_prefix_t * key)
 207 {
 208   int i, len;
 209   int rv;
 210   BVT (clib_bihash_kv) kv, value;
 211
 212   len = vec_len (db->ip4_prefix_lengths_in_search_order);
 213
 214   for (i = 0; i < len; i++)
 215     {
 216       int dst_address_length = db->ip4_prefix_lengths_in_search_order[i];
 217       ip4_address_t *mask;
 218
 219       ASSERT (dst_address_length >= 0 && dst_address_length <= 32);
 220
 221       mask = &db->ip4_fib_masks[dst_address_length];
 222
 223       kv.key[0] =
 224         ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
 225       kv.key[1] = 0;
 226       kv.key[2] = 0;
 227
 228       rv =
 229         BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
 230       if (rv == 0)
 231         return value.value;
 232     }
 233
 234   return GID_LOOKUP_MISS;
 235 }
 236
 237 static u32
 238 ip6_lookup_exact_match (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
 239 {
 240   int rv;
 241   BVT (clib_bihash_kv) kv, value;
 242
 243   ip6_address_t *mask;
 244   mask = &db->ip6_fib_masks[ip_prefix_len (key)];
 245
 246   kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
 247   kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
 248   kv.key[2] = (u64) vni;
 249
 250   rv = BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
 251   if (rv == 0)
 252     return value.value;
 253
 254   return GID_LOOKUP_MISS;
 255 }
 256
 257 static u32
 258 ip6_lookup (gid_ip6_table_t * db, u32 vni, ip_prefix_t * key)
 259 {
 260   int i, len;
 261   int rv;
 262   BVT (clib_bihash_kv) kv, value;
 263
 264   len = vec_len (db->ip6_prefix_lengths_in_search_order);
 265
 266   for (i = 0; i < len; i++)
 267     {
 268       int dst_address_length = db->ip6_prefix_lengths_in_search_order[i];
 269       ip6_address_t *mask;
 270
 271       ASSERT (dst_address_length >= 0 && dst_address_length <= 128);
 272
 273       mask = &db->ip6_fib_masks[dst_address_length];
 274
 275       kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
 276       kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
 277       kv.key[2] = (u64) vni;
 278
 279       rv =
 280         BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
 281       if (rv == 0)
 282         return value.value;
 283     }
 284
 285   return GID_LOOKUP_MISS;
 286 }
 287
 288 static u32
 289 ip_sd_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst,
 290               ip_prefix_t * src)
 291 {
 292   u32 sfi;
 293   gid_ip4_table_t *sfib4;
 294   gid_ip6_table_t *sfib6;
 295
 296   switch (ip_prefix_version (dst))
 297     {
 298     case IP4:
 299       sfi = ip4_lookup (&db->dst_ip4_table, vni, dst);
 300       if (GID_LOOKUP_MISS != sfi)
 301         sfib4 = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 302       else
 303         return GID_LOOKUP_MISS;
 304
 305       if (!src)
 306         {
 307           ip_prefix_t sp;
 308           clib_memset (&sp, 0, sizeof (sp));
 309           return ip4_lookup_exact_match (sfib4, 0, &sp);
 310         }
 311       else
 312         return ip4_lookup (sfib4, 0, src);
 313
 314       break;
 315     case IP6:
 316       sfi = ip6_lookup (&db->dst_ip6_table, vni, dst);
 317       if (GID_LOOKUP_MISS != sfi)
 318         sfib6 = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 319       else
 320         return GID_LOOKUP_MISS;
 321
 322       if (!src)
 323         {
 324           ip_prefix_t sp;
 325           clib_memset (&sp, 0, sizeof (sp));
 326           ip_prefix_version (&sp) = IP6;
 327           return ip6_lookup_exact_match (sfib6, 0, &sp);
 328         }
 329       else
 330         return ip6_lookup (sfib6, 0, src);
 331
 332       break;
 333     default:
 334       clib_warning ("address type %d not supported!",
 335                     ip_prefix_version (dst));
 336       break;
 337     }
 338   return GID_LOOKUP_MISS;
 339 }
 340
 341 static void
 342 make_arp_ndp_key (BVT (clib_bihash_kv) * kv, u32 bd, ip_address_t * addr)
 343 {
 344   kv->key[0] = ((u64) bd << 32) | (u32) ip_addr_version (addr);
 345   if (ip_addr_version (addr) == IP4)
 346     {
 347       kv->key[1] = (u64) addr->ip.v4.as_u32;
 348       kv->key[2] = (u64) 0;
 349     }
 350   else
 351     {
 352       kv->key[1] = (u64) addr->ip.v6.as_u64[0];
 353       kv->key[2] = (u64) addr->ip.v6.as_u64[1];
 354     }
 355 }
 356
 357 static void
 358 make_nsh_key (BVT (clib_bihash_kv) * kv, u32 vni, u32 spi, u8 si)
 359 {
 360   kv->key[0] = (u64) vni;
 361   kv->key[1] = (u64) spi;
 362   kv->key[2] = (u64) si;
 363 }
 364
 365 static u64
 366 arp_ndp_lookup (gid_l2_arp_ndp_table_t * db, u32 bd, ip_address_t * key)
 367 {
 368   int rv;
 369   BVT (clib_bihash_kv) kv, value;
 370
 371   make_arp_ndp_key (&kv, bd, key);
 372   rv = BV (clib_bihash_search_inline_2) (&db->arp_ndp_lookup_table, &kv,
 373                                          &value);
 374
 375   if (rv == 0)
 376     return value.value;
 377
 378   return GID_LOOKUP_MISS_L2;
 379 }
 380
 381 static u32
 382 nsh_lookup (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si)
 383 {
 384   int rv;
 385   BVT (clib_bihash_kv) kv, value;
 386
 387   make_nsh_key (&kv, vni, spi, si);
 388   rv = BV (clib_bihash_search_inline_2) (&db->nsh_lookup_table, &kv, &value);
 389
 390   if (rv == 0)
 391     return value.value;
 392
 393   return GID_LOOKUP_MISS;
 394 }
 395
 396 u64
 397 gid_dictionary_lookup (gid_dictionary_t * db, gid_address_t * key)
 398 {
 399   switch (gid_address_type (key))
 400     {
 401     case GID_ADDR_IP_PREFIX:
 402       return ip_sd_lookup (db, gid_address_vni (key),
 403                            &gid_address_ippref (key), 0);
 404     case GID_ADDR_MAC:
 405       return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
 406                             gid_address_mac (key), 0);
 407     case GID_ADDR_SRC_DST:
 408       switch (gid_address_sd_dst_type (key))
 409         {
 410         case FID_ADDR_IP_PREF:
 411           return ip_sd_lookup (db, gid_address_vni (key),
 412                                &gid_address_sd_dst_ippref (key),
 413                                &gid_address_sd_src_ippref (key));
 414           break;
 415         case FID_ADDR_MAC:
 416           return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (key),
 417                                 gid_address_sd_dst_mac (key),
 418                                 gid_address_sd_src_mac (key));
 419           break;
 420         default:
 421           clib_warning ("Source/Dest address type %d not supported!",
 422                         gid_address_sd_dst_type (key));
 423           break;
 424         }
 425       break;
 426     case GID_ADDR_ARP:
 427     case GID_ADDR_NDP:
 428       return arp_ndp_lookup (&db->arp_ndp_table, gid_address_arp_ndp_bd (key),
 429                              &gid_address_arp_ndp_ip (key));
 430     case GID_ADDR_NSH:
 431       return nsh_lookup (&db->nsh_table, gid_address_vni (key),
 432                          gid_address_nsh_spi (key), gid_address_nsh_si (key));
 433     default:
 434       clib_warning ("address type %d not supported!", gid_address_type (key));
 435       break;
 436     }
 437   return GID_LOOKUP_MISS;
 438 }
 439
 440 u32
 441 gid_dictionary_sd_lookup (gid_dictionary_t * db, gid_address_t * dst,
 442                           gid_address_t * src)
 443 {
 444   switch (gid_address_type (dst))
 445     {
 446     case GID_ADDR_IP_PREFIX:
 447       return ip_sd_lookup (db, gid_address_vni (dst),
 448                            &gid_address_ippref (dst),
 449                            &gid_address_ippref (src));
 450     case GID_ADDR_MAC:
 451       return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
 452                             gid_address_mac (dst), gid_address_mac (src));
 453     case GID_ADDR_SRC_DST:
 454       switch (gid_address_sd_dst_type (dst))
 455         {
 456         case FID_ADDR_IP_PREF:
 457           return ip_sd_lookup (db, gid_address_vni (dst),
 458                                &gid_address_sd_dst_ippref (dst),
 459                                &gid_address_sd_src_ippref (dst));
 460           break;
 461         case FID_ADDR_MAC:
 462           return mac_sd_lookup (&db->sd_mac_table, gid_address_vni (dst),
 463                                 gid_address_sd_dst_mac (dst),
 464                                 gid_address_sd_src_mac (dst));
 465           break;
 466         default:
 467           clib_warning ("Source/Dest address type %d not supported!",
 468                         gid_address_sd_dst_type (dst));
 469           break;
 470         }
 471       break;
 472     case GID_ADDR_NSH:
 473       return gid_dictionary_lookup (db, dst);
 474       break;
 475     default:
 476       clib_warning ("address type %d not supported!", gid_address_type (dst));
 477       break;
 478     }
 479   return GID_LOOKUP_MISS;
 480 }
 481
 482 static void
 483 ip4_compute_prefix_lengths_in_search_order (gid_ip4_table_t * db)
 484 {
 485   int i;
 486   vec_reset_length (db->ip4_prefix_lengths_in_search_order);
 487   /* Note: bitmap reversed so this is in fact a longest prefix match */
 488
 489   /* *INDENT-OFF* */
 490   clib_bitmap_foreach (i, db->ip4_non_empty_dst_address_length_bitmap,
 491   ({
 492     int dst_address_length = 32 - i;
 493     vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
 494   }));
 495   /* *INDENT-ON* */
 496
 497 }
 498
 499 static u32
 500 add_del_ip4_key (gid_ip4_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 501                  u8 is_add)
 502 {
 503   BVT (clib_bihash_kv) kv, value;
 504   u32 old_val = ~0;
 505   ip4_address_t key;
 506   u8 plen = ip_prefix_len (pref);
 507
 508   clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
 509   key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
 510   if (is_add)
 511     {
 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   /* *INDENT-OFF* */
 673   clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap,
 674   ({
 675     int dst_address_length = 128 - i;
 676     vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
 677   }));
 678   /* *INDENT-ON* */
 679 }
 680
 681 static u32
 682 add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 683                  u8 is_add)
 684 {
 685   BVT (clib_bihash_kv) kv, value;
 686   u32 old_val = ~0;
 687   ip6_address_t key;
 688   u8 plen = ip_prefix_len (pref);
 689
 690   clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
 691   ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
 692   if (is_add)
 693     {
 694       db->ip6_non_empty_dst_address_length_bitmap =
 695         clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 696                          128 - plen, 1);
 697       ip6_compute_prefix_lengths_in_search_order (db);
 698       db->ip6_prefix_len_refcount[plen]++;
 699     }
 700   else
 701     {
 702       ASSERT (db->ip6_prefix_len_refcount[plen] != 0);
 703
 704       db->ip6_prefix_len_refcount[plen]--;
 705
 706       if (db->ip6_prefix_len_refcount[plen] == 0)
 707         {
 708           db->ip6_non_empty_dst_address_length_bitmap =
 709             clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 710                              128 - plen, 0);
 711           ip6_compute_prefix_lengths_in_search_order (db);
 712         }
 713     }
 714
 715   kv.key[0] = key.as_u64[0];
 716   kv.key[1] = key.as_u64[1];
 717   kv.key[2] = (u64) vni;
 718 //  kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);
 719
 720   if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
 721     old_val = value.value;
 722
 723   if (!is_add)
 724     {
 725       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
 726       db->count--;
 727     }
 728   else
 729     {
 730       kv.value = val;
 731       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
 732       db->count++;
 733     }
 734   return old_val;
 735 }
 736
 737 static u32
 738 add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
 739              u32 val, u8 is_add)
 740 {
 741   BVT (clib_bihash_kv) kv, value;
 742   u32 old_val = ~0;
 743
 744   make_mac_sd_key (&kv, vni, src_mac, dst_mac);
 745
 746   if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
 747     old_val = value.value;
 748
 749   if (!is_add)
 750     {
 751       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
 752       db->count--;
 753     }
 754   else
 755     {
 756       kv.value = val;
 757       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
 758       db->count++;
 759     }
 760   return old_val;
 761 }
 762
 763 static void
 764 ip6_lookup_init (gid_ip6_table_t * db)
 765 {
 766   uword i;
 767   BVT (clib_bihash_init2_args) _a, *a = &_a;
 768
 769   clib_memset (db->ip6_prefix_len_refcount, 0,
 770                sizeof (db->ip6_prefix_len_refcount));
 771
 772   for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
 773     {
 774       u32 j, i0, i1;
 775
 776       i0 = i / 32;
 777       i1 = i % 32;
 778
 779       for (j = 0; j < i0; j++)
 780         db->ip6_fib_masks[i].as_u32[j] = ~0;
 781
 782       if (i1)
 783         db->ip6_fib_masks[i].as_u32[i0] =
 784           clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
 785     }
 786
 787   if (db->ip6_lookup_table_nbuckets == 0)
 788     db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 789
 790   db->ip6_lookup_table_nbuckets =
 791     1 << max_log2 (db->ip6_lookup_table_nbuckets);
 792
 793   if (db->ip6_lookup_table_size == 0)
 794     db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 795
 796   /*
 797    * Danger Will Robinson, Danger! gid_ip6_table_t's are allocated from
 798    * a pool. They MUST NOT be listed on the clib_all_bihashes list...
 799    */
 800   memset (a, 0, sizeof (*a));
 801   a->h = &db->ip6_lookup_table;
 802   a->name = "LISP ip6 lookup table";
 803   a->nbuckets = db->ip6_lookup_table_nbuckets;
 804   a->memory_size = db->ip6_lookup_table_size;
 805   a->dont_add_to_all_bihash_list = 1;   /* See comment above */
 806
 807   BV (clib_bihash_init2) (a);
 808 }
 809
 810 static u32
 811 add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 812                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 813 {
 814   u32 sfi, old_val = ~0;
 815   gid_ip6_table_t *sfib;
 816
 817   sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);
 818
 819   if (is_add)
 820     {
 821       if (GID_LOOKUP_MISS == sfi)
 822         {
 823           pool_get (db->src_ip6_table_pool, sfib);
 824           ip6_lookup_init (sfib);
 825           add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
 826                            sfib - db->src_ip6_table_pool, is_add);
 827           if (src_pref)
 828             add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 829           else
 830             {
 831               ip_prefix_t sp;
 832               clib_memset (&sp, 0, sizeof (sp));
 833               ip_prefix_version (&sp) = IP6;
 834               add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 835             }
 836         }
 837       else
 838         {
 839           ASSERT (!pool_is_free_index (db->src_ip6_table_pool, sfi));
 840           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 841           if (src_pref)
 842             {
 843               old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
 844               add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 845             }
 846           else
 847             {
 848               ip_prefix_t sp;
 849               clib_memset (&sp, 0, sizeof (sp));
 850               ip_prefix_version (&sp) = IP6;
 851               old_val =
 852                 add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 853             }
 854         }
 855     }
 856   else
 857     {
 858       if (GID_LOOKUP_MISS != sfi)
 859         {
 860           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 861           if (src_pref)
 862             old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
 863           else
 864             {
 865               ip_prefix_t sp;
 866               clib_memset (&sp, 0, sizeof (sp));
 867               ip_prefix_version (&sp) = IP6;
 868               old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
 869             }
 870
 871           if (sfib->count == 0)
 872             add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
 873         }
 874       else
 875         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 876                       dst_pref);
 877     }
 878   return old_val;
 879 }
 880
 881 static u32
 882 add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
 883             ip_prefix_t * src_key, u32 value, u8 is_add)
 884 {
 885   switch (ip_prefix_version (dst_key))
 886     {
 887     case IP4:
 888       return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
 889       break;
 890     case IP6:
 891       return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
 892       break;
 893     default:
 894       clib_warning ("address type %d not supported!",
 895                     ip_prefix_version (dst_key));
 896       break;
 897     }
 898   return ~0;
 899 }
 900
 901 static u32
 902 add_del_sd (gid_dictionary_t * db, u32 vni, source_dest_t * key, u32 value,
 903             u8 is_add)
 904 {
 905   switch (sd_dst_type (key))
 906     {
 907     case FID_ADDR_IP_PREF:
 908       add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
 909                   value, is_add);
 910
 911     case FID_ADDR_MAC:
 912       return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
 913                           sd_src_mac (key), value, is_add);
 914
 915     default:
 916       clib_warning ("SD address type %d not supported!", sd_dst_type (key));
 917       break;
 918     }
 919
 920   return ~0;
 921 }
 922
 923 static u64
 924 add_del_arp_ndp (gid_l2_arp_ndp_table_t * db, u32 bd, ip_address_t * key,
 925                  u64 value, u8 is_add)
 926 {
 927   BVT (clib_bihash_kv) kv, result;
 928   u32 old_val = ~0;
 929
 930   make_arp_ndp_key (&kv, bd, key);
 931   if (BV (clib_bihash_search) (&db->arp_ndp_lookup_table, &kv, &result) == 0)
 932     old_val = result.value;
 933
 934   if (is_add)
 935     {
 936       kv.value = value;
 937       BV (clib_bihash_add_del) (&db->arp_ndp_lookup_table, &kv,
 938                                 1 /* is_add */ );
 939       db->count++;
 940     }
 941   else
 942     {
 943       BV (clib_bihash_add_del) (&db->arp_ndp_lookup_table, &kv,
 944                                 0 /* is_add */ );
 945       db->count--;
 946     }
 947   return old_val;
 948 }
 949
 950 static u32
 951 add_del_nsh (gid_nsh_table_t * db, u32 vni, u32 spi, u8 si, u32 value,
 952              u8 is_add)
 953 {
 954   BVT (clib_bihash_kv) kv, result;
 955   u32 old_val = ~0;
 956
 957   make_nsh_key (&kv, vni, spi, si);
 958   if (BV (clib_bihash_search) (&db->nsh_lookup_table, &kv, &result) == 0)
 959     old_val = result.value;
 960
 961   if (is_add)
 962     {
 963       kv.value = value;
 964       BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 1 /* is_add */ );
 965       db->count++;
 966     }
 967   else
 968     {
 969       BV (clib_bihash_add_del) (&db->nsh_lookup_table, &kv, 0 /* is_add */ );
 970       db->count--;
 971     }
 972   return old_val;
 973 }
 974
 975 u32
 976 gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u64 value,
 977                         u8 is_add)
 978 {
 979   switch (gid_address_type (key))
 980     {
 981     case GID_ADDR_IP_PREFIX:
 982       return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
 983                          0, (u32) value, is_add);
 984     case GID_ADDR_MAC:
 985       return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
 986                           gid_address_mac (key), 0, (u32) value, is_add);
 987     case GID_ADDR_SRC_DST:
 988       return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
 989                          (u32) value, is_add);
 990     case GID_ADDR_ARP:
 991     case GID_ADDR_NDP:
 992       return add_del_arp_ndp (&db->arp_ndp_table,
 993                               gid_address_arp_ndp_bd (key),
 994                               &gid_address_arp_ndp_ip (key), value, is_add);
 995     case GID_ADDR_NSH:
 996       return add_del_nsh (&db->nsh_table, gid_address_vni (key),
 997                           gid_address_nsh_spi (key), gid_address_nsh_si (key),
 998                           value, is_add);
 999
1000     default:
1001       clib_warning ("address type %d not supported!", gid_address_type (key));
1002       break;
1003     }
1004   return ~0;
1005 }
1006
1007 static void
1008 mac_lookup_init (gid_mac_table_t * db)
1009 {
1010   if (db->mac_lookup_table_nbuckets == 0)
1011     db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1012
1013   db->mac_lookup_table_nbuckets =
1014     1 << max_log2 (db->mac_lookup_table_nbuckets);
1015
1016   if (db->mac_lookup_table_size == 0)
1017     db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1018
1019   BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
1020                          db->mac_lookup_table_nbuckets,
1021                          db->mac_lookup_table_size);
1022 }
1023
1024 static void
1025 arp_ndp_lookup_init (gid_l2_arp_ndp_table_t * db)
1026 {
1027   if (db->arp_ndp_lookup_table_nbuckets == 0)
1028     db->arp_ndp_lookup_table_nbuckets =
1029       ARP_NDP_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1030
1031   db->arp_ndp_lookup_table_nbuckets =
1032     1 << max_log2 (db->arp_ndp_lookup_table_nbuckets);
1033
1034   if (db->arp_ndp_lookup_table_size == 0)
1035     db->arp_ndp_lookup_table_size = ARP_NDP_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1036
1037   BV (clib_bihash_init) (&db->arp_ndp_lookup_table, "arp ndp lookup table",
1038                          db->arp_ndp_lookup_table_nbuckets,
1039                          db->arp_ndp_lookup_table_size);
1040 }
1041
1042 static void
1043 nsh_lookup_init (gid_nsh_table_t * db)
1044 {
1045   if (db->nsh_lookup_table_nbuckets == 0)
1046     db->nsh_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
1047
1048   db->nsh_lookup_table_nbuckets =
1049     1 << max_log2 (db->nsh_lookup_table_nbuckets);
1050
1051   if (db->nsh_lookup_table_size == 0)
1052     db->nsh_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
1053
1054   BV (clib_bihash_init) (&db->nsh_lookup_table, "nsh lookup table",
1055                          db->nsh_lookup_table_nbuckets,
1056                          db->nsh_lookup_table_size);
1057 }
1058
1059 void
1060 gid_dictionary_init (gid_dictionary_t * db)
1061 {
1062   ip4_lookup_init (&db->dst_ip4_table);
1063   ip6_lookup_init (&db->dst_ip6_table);
1064   mac_lookup_init (&db->sd_mac_table);
1065   arp_ndp_lookup_init (&db->arp_ndp_table);
1066   nsh_lookup_init (&db->nsh_table);
1067 }
1068
1069 /*
1070  * fd.io coding-style-patch-verification: ON
1071  *
1072  * Local Variables:
1073  * eval: (c-set-style "gnu")
1074  * End:
1075  */