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