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