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     BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
 468   else
 469     {
 470       kv.value = val;
 471       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
 472     }
 473   return old_val;
 474 }
 475
 476 static void
 477 ip4_lookup_init (gid_ip4_table_t * db)
 478 {
 479   uword i;
 480
 481   memset (db->ip4_prefix_len_refcount, 0,
 482           sizeof (db->ip4_prefix_len_refcount));
 483
 484   for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
 485     {
 486       u32 m;
 487
 488       if (i < 32)
 489         m = pow2_mask (i) << (32 - i);
 490       else
 491         m = ~0;
 492       db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
 493     }
 494   if (db->ip4_lookup_table_nbuckets == 0)
 495     db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 496
 497   db->ip4_lookup_table_nbuckets =
 498     1 << max_log2 (db->ip4_lookup_table_nbuckets);
 499
 500   if (db->ip4_lookup_table_size == 0)
 501     db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 502
 503   BV (clib_bihash_init) (&db->ip4_lookup_table, "ip4 lookup table",
 504                          db->ip4_lookup_table_nbuckets,
 505                          db->ip4_lookup_table_size);
 506 }
 507
 508 static u32
 509 add_del_sd_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 510                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 511 {
 512   u32 sfi, old_val = ~0;
 513   gid_ip4_table_t *sfib;
 514
 515   sfi = ip4_lookup_exact_match (&db->dst_ip4_table, vni, dst_pref);
 516
 517   if (is_add)
 518     {
 519       if (GID_LOOKUP_MISS == sfi)
 520         {
 521           pool_get (db->src_ip4_table_pool, sfib);
 522           ip4_lookup_init (sfib);
 523           add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref,
 524                            sfib - db->src_ip4_table_pool, is_add);
 525           if (src_pref)
 526             add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 527           else
 528             {
 529               ip_prefix_t sp;
 530               memset (&sp, 0, sizeof (sp));
 531               add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 532             }
 533         }
 534       else
 535         {
 536           ASSERT (!pool_is_free_index (db->src_ip4_table_pool, sfi));
 537           sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 538           if (src_pref)
 539             {
 540               old_val = ip4_lookup_exact_match (sfib, 0, src_pref);
 541               add_del_ip4_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 542             }
 543           else
 544             {
 545               ip_prefix_t sp;
 546               memset (&sp, 0, sizeof (sp));
 547               old_val =
 548                 add_del_ip4_key (sfib, 0 /* vni */ , &sp, val, is_add);
 549             }
 550         }
 551     }
 552   else
 553     {
 554       if (GID_LOOKUP_MISS != sfi)
 555         {
 556           add_del_ip4_key (&db->dst_ip4_table, vni, dst_pref, 0, is_add);
 557           sfib = pool_elt_at_index (db->src_ip4_table_pool, sfi);
 558           if (src_pref)
 559             old_val = add_del_ip4_key (sfib, 0, src_pref, 0, is_add);
 560           else
 561             {
 562               ip_prefix_t sp;
 563               memset (&sp, 0, sizeof (sp));
 564               old_val = add_del_ip4_key (sfib, 0, &sp, 0, is_add);
 565             }
 566         }
 567       else
 568         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 569                       dst_pref);
 570     }
 571   return old_val;
 572 }
 573
 574 static void
 575 ip6_compute_prefix_lengths_in_search_order (gid_ip6_table_t * db)
 576 {
 577   int i;
 578   vec_reset_length (db->ip6_prefix_lengths_in_search_order);
 579   /* Note: bitmap reversed so this is in fact a longest prefix match */
 580
 581   /* *INDENT-OFF* */
 582   clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap,
 583   ({
 584     int dst_address_length = 128 - i;
 585     vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
 586   }));
 587   /* *INDENT-ON* */
 588 }
 589
 590 static u32
 591 add_del_ip6_key (gid_ip6_table_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 592                  u8 is_add)
 593 {
 594   BVT (clib_bihash_kv) kv, value;
 595   u32 old_val = ~0;
 596   ip6_address_t key;
 597   u8 plen = ip_prefix_len (pref);
 598
 599   clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
 600   ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
 601   if (is_add)
 602     {
 603       db->ip6_non_empty_dst_address_length_bitmap =
 604         clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 605                          128 - plen, 1);
 606       ip6_compute_prefix_lengths_in_search_order (db);
 607       db->ip6_prefix_len_refcount[plen]++;
 608     }
 609   else
 610     {
 611       ASSERT (db->ip6_prefix_len_refcount[plen] != 0);
 612
 613       db->ip6_prefix_len_refcount[plen]--;
 614
 615       if (db->ip6_prefix_len_refcount[plen] == 0)
 616         {
 617           db->ip6_non_empty_dst_address_length_bitmap =
 618             clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 619                              128 - plen, 0);
 620           ip6_compute_prefix_lengths_in_search_order (db);
 621         }
 622     }
 623
 624   kv.key[0] = key.as_u64[0];
 625   kv.key[1] = key.as_u64[1];
 626   kv.key[2] = (u64) vni;
 627 //  kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);
 628
 629   if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
 630     old_val = value.value;
 631
 632   if (!is_add)
 633     BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
 634   else
 635     {
 636       kv.value = val;
 637       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
 638     }
 639   return old_val;
 640 }
 641
 642 static u32
 643 add_del_mac (gid_mac_table_t * db, u32 vni, u8 * dst_mac, u8 * src_mac,
 644              u32 val, u8 is_add)
 645 {
 646   BVT (clib_bihash_kv) kv, value;
 647   u32 old_val = ~0;
 648
 649   make_mac_sd_key (&kv, vni, src_mac, dst_mac);
 650
 651   if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
 652     old_val = value.value;
 653
 654   if (!is_add)
 655     BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
 656   else
 657     {
 658       kv.value = val;
 659       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
 660     }
 661   return old_val;
 662 }
 663
 664 static void
 665 ip6_lookup_init (gid_ip6_table_t * db)
 666 {
 667   uword i;
 668
 669   memset (db->ip6_prefix_len_refcount, 0,
 670           sizeof (db->ip6_prefix_len_refcount));
 671
 672   for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
 673     {
 674       u32 j, i0, i1;
 675
 676       i0 = i / 32;
 677       i1 = i % 32;
 678
 679       for (j = 0; j < i0; j++)
 680         db->ip6_fib_masks[i].as_u32[j] = ~0;
 681
 682       if (i1)
 683         db->ip6_fib_masks[i].as_u32[i0] =
 684           clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
 685     }
 686
 687   if (db->ip6_lookup_table_nbuckets == 0)
 688     db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 689
 690   db->ip6_lookup_table_nbuckets =
 691     1 << max_log2 (db->ip6_lookup_table_nbuckets);
 692
 693   if (db->ip6_lookup_table_size == 0)
 694     db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 695
 696   BV (clib_bihash_init) (&db->ip6_lookup_table, "ip6 lookup table",
 697                          db->ip6_lookup_table_nbuckets,
 698                          db->ip6_lookup_table_size);
 699 }
 700
 701 static u32
 702 add_del_sd_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_pref,
 703                     ip_prefix_t * src_pref, u32 val, u8 is_add)
 704 {
 705   u32 sfi, old_val = ~0;
 706   gid_ip6_table_t *sfib;
 707
 708   sfi = ip6_lookup_exact_match (&db->dst_ip6_table, vni, dst_pref);
 709
 710   if (is_add)
 711     {
 712       if (GID_LOOKUP_MISS == sfi)
 713         {
 714           pool_get (db->src_ip6_table_pool, sfib);
 715           ip6_lookup_init (sfib);
 716           add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref,
 717                            sfib - db->src_ip6_table_pool, is_add);
 718           if (src_pref)
 719             add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 720           else
 721             {
 722               ip_prefix_t sp;
 723               memset (&sp, 0, sizeof (sp));
 724               ip_prefix_version (&sp) = IP6;
 725               add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 726             }
 727         }
 728       else
 729         {
 730           ASSERT (!pool_is_free_index (db->src_ip6_table_pool, sfi));
 731           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 732           if (src_pref)
 733             {
 734               old_val = ip6_lookup_exact_match (sfib, 0, src_pref);
 735               add_del_ip6_key (sfib, 0 /* vni */ , src_pref, val, is_add);
 736             }
 737           else
 738             {
 739               ip_prefix_t sp;
 740               memset (&sp, 0, sizeof (sp));
 741               ip_prefix_version (&sp) = IP6;
 742               old_val =
 743                 add_del_ip6_key (sfib, 0 /* vni */ , &sp, val, is_add);
 744             }
 745         }
 746     }
 747   else
 748     {
 749       if (GID_LOOKUP_MISS != sfi)
 750         {
 751           add_del_ip6_key (&db->dst_ip6_table, vni, dst_pref, 0, is_add);
 752           sfib = pool_elt_at_index (db->src_ip6_table_pool, sfi);
 753           if (src_pref)
 754             old_val = add_del_ip6_key (sfib, 0, src_pref, 0, is_add);
 755           else
 756             {
 757               ip_prefix_t sp;
 758               memset (&sp, 0, sizeof (sp));
 759               ip_prefix_version (&sp) = IP6;
 760               old_val = add_del_ip6_key (sfib, 0, &sp, 0, is_add);
 761             }
 762         }
 763       else
 764         clib_warning ("cannot delete dst mapping %U!", format_ip_prefix,
 765                       dst_pref);
 766     }
 767   return old_val;
 768 }
 769
 770 static u32
 771 add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * dst_key,
 772             ip_prefix_t * src_key, u32 value, u8 is_add)
 773 {
 774   switch (ip_prefix_version (dst_key))
 775     {
 776     case IP4:
 777       return add_del_sd_ip4_key (db, vni, dst_key, src_key, value, is_add);
 778       break;
 779     case IP6:
 780       return add_del_sd_ip6_key (db, vni, dst_key, src_key, value, is_add);
 781       break;
 782     default:
 783       clib_warning ("address type %d not supported!",
 784                     ip_prefix_version (dst_key));
 785       break;
 786     }
 787   return ~0;
 788 }
 789
 790 static u32
 791 add_del_sd (gid_dictionary_t * db, u32 vni, source_dest_t * key, u32 value,
 792             u8 is_add)
 793 {
 794   switch (sd_dst_type (key))
 795     {
 796     case FID_ADDR_IP_PREF:
 797       add_del_ip (db, vni, &sd_dst_ippref (key), &sd_src_ippref (key),
 798                   value, is_add);
 799
 800     case FID_ADDR_MAC:
 801       return add_del_mac (&db->sd_mac_table, vni, sd_dst_mac (key),
 802                           sd_src_mac (key), value, is_add);
 803
 804     default:
 805       clib_warning ("SD address type %d not supprted!", sd_dst_type (key));
 806       break;
 807     }
 808
 809   return ~0;
 810 }
 811
 812 u32
 813 gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u32 value,
 814                         u8 is_add)
 815 {
 816   switch (gid_address_type (key))
 817     {
 818     case GID_ADDR_IP_PREFIX:
 819       return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
 820                          0, value, is_add);
 821     case GID_ADDR_MAC:
 822       return add_del_mac (&db->sd_mac_table, gid_address_vni (key),
 823                           gid_address_mac (key), 0, value, is_add);
 824     case GID_ADDR_SRC_DST:
 825       return add_del_sd (db, gid_address_vni (key), &gid_address_sd (key),
 826                          value, is_add);
 827     default:
 828       clib_warning ("address type %d not supported!", gid_address_type (key));
 829       break;
 830     }
 831   return ~0;
 832 }
 833
 834 static void
 835 mac_lookup_init (gid_mac_table_t * db)
 836 {
 837   if (db->mac_lookup_table_nbuckets == 0)
 838     db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 839
 840   db->mac_lookup_table_nbuckets =
 841     1 << max_log2 (db->mac_lookup_table_nbuckets);
 842
 843   if (db->mac_lookup_table_size == 0)
 844     db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 845
 846   BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
 847                          db->mac_lookup_table_nbuckets,
 848                          db->mac_lookup_table_size);
 849 }
 850
 851 void
 852 gid_dictionary_init (gid_dictionary_t * db)
 853 {
 854   ip4_lookup_init (&db->dst_ip4_table);
 855   ip6_lookup_init (&db->dst_ip6_table);
 856   mac_lookup_init (&db->sd_mac_table);
 857 }
 858
 859 /*
 860  * fd.io coding-style-patch-verification: ON
 861  *
 862  * Local Variables:
 863  * eval: (c-set-style "gnu")
 864  * End:
 865  */