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 static u32
  19 mac_lookup (gid_dictionary_t * db, u32 vni, u8 * key)
  20 {
  21   int rv;
  22   BVT (clib_bihash_kv) kv, value;
  23
  24   kv.key[0] = mac_to_u64 (key);
  25   kv.key[1] = (u64) vni;
  26   kv.key[2] = 0;
  27
  28   rv = BV (clib_bihash_search_inline_2) (&db->mac_lookup_table, &kv, &value);
  29   if (rv == 0)
  30     return value.value;
  31
  32   return GID_LOOKUP_MISS;
  33 }
  34
  35 static u32
  36 ip4_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * key)
  37 {
  38   int i, len;
  39   int rv;
  40   BVT (clib_bihash_kv) kv, value;
  41
  42   len = vec_len (db->ip4_prefix_lengths_in_search_order);
  43
  44   for (i = 0; i < len; i++)
  45     {
  46       int dst_address_length = db->ip4_prefix_lengths_in_search_order[i];
  47       ip4_address_t *mask;
  48
  49       ASSERT (dst_address_length >= 0 && dst_address_length <= 32);
  50
  51       mask = &db->ip4_fib_masks[dst_address_length];
  52
  53       kv.key[0] =
  54         ((u64) vni << 32) | (ip_prefix_v4 (key).as_u32 & mask->as_u32);
  55       kv.key[1] = 0;
  56       kv.key[2] = 0;
  57
  58       rv =
  59         BV (clib_bihash_search_inline_2) (&db->ip4_lookup_table, &kv, &value);
  60       if (rv == 0)
  61         return value.value;
  62     }
  63
  64   return GID_LOOKUP_MISS;
  65 }
  66
  67 static u32
  68 ip6_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * key)
  69 {
  70   int i, len;
  71   int rv;
  72   BVT (clib_bihash_kv) kv, value;
  73
  74   len = vec_len (db->ip6_prefix_lengths_in_search_order);
  75
  76   for (i = 0; i < len; i++)
  77     {
  78       int dst_address_length = db->ip6_prefix_lengths_in_search_order[i];
  79       ip6_address_t *mask;
  80
  81       ASSERT (dst_address_length >= 0 && dst_address_length <= 128);
  82
  83       mask = &db->ip6_fib_masks[dst_address_length];
  84
  85       kv.key[0] = ip_prefix_v6 (key).as_u64[0] & mask->as_u64[0];
  86       kv.key[1] = ip_prefix_v6 (key).as_u64[1] & mask->as_u64[1];
  87       kv.key[2] = (u64) vni;
  88
  89       rv =
  90         BV (clib_bihash_search_inline_2) (&db->ip6_lookup_table, &kv, &value);
  91       if (rv == 0)
  92         return value.value;
  93     }
  94
  95   return GID_LOOKUP_MISS;
  96 }
  97
  98 static u32
  99 ip_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t * key)
 100 {
 101   /* XXX for now this only works with ip-prefixes, no lcafs */
 102   switch (ip_prefix_version (key))
 103     {
 104     case IP4:
 105       return ip4_lookup (db, vni, key);
 106       break;
 107     case IP6:
 108       return ip6_lookup (db, vni, key);
 109       break;
 110     default:
 111       clib_warning ("address type %d not supported!",
 112                     ip_prefix_version (key));
 113       break;
 114     }
 115   return ~0;
 116 }
 117
 118 u32
 119 gid_dictionary_lookup (gid_dictionary_t * db, gid_address_t * key)
 120 {
 121   /* XXX for now this only works with ip-prefixes, no lcafs */
 122   switch (gid_address_type (key))
 123     {
 124     case GID_ADDR_IP_PREFIX:
 125       return ip_lookup (db, gid_address_vni (key), &gid_address_ippref (key));
 126     case GID_ADDR_MAC:
 127       return mac_lookup (db, gid_address_vni (key), gid_address_mac (key));
 128     default:
 129       clib_warning ("address type %d not supported!", gid_address_type (key));
 130       break;
 131     }
 132   return GID_LOOKUP_MISS;
 133 }
 134
 135 static void
 136 ip4_compute_prefix_lengths_in_search_order (gid_dictionary_t * db)
 137 {
 138   int i;
 139   vec_reset_length (db->ip4_prefix_lengths_in_search_order);
 140   /* Note: bitmap reversed so this is in fact a longest prefix match */
 141
 142   /* *INDENT-OFF* */
 143   clib_bitmap_foreach (i, db->ip4_non_empty_dst_address_length_bitmap,
 144   ({
 145     int dst_address_length = 32 - i;
 146     vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
 147   }));
 148   /* *INDENT-ON* */
 149
 150 }
 151
 152 static u32
 153 add_del_ip4_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 154                  u8 is_add)
 155 {
 156   BVT (clib_bihash_kv) kv, value;
 157   u32 old_val = ~0;
 158   ip4_address_t key;
 159   u8 plen = ip_prefix_len (pref);
 160
 161   clib_memcpy (&key, &ip_prefix_v4 (pref), sizeof (key));
 162   key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
 163   if (is_add)
 164     {
 165       db->ip4_non_empty_dst_address_length_bitmap =
 166         clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 167                          32 - plen, 1);
 168       ip4_compute_prefix_lengths_in_search_order (db);
 169
 170       db->ip4_prefix_len_refcount[plen]++;
 171     }
 172   else
 173     {
 174       ASSERT (db->ip4_prefix_len_refcount[plen] != 0);
 175
 176       db->ip4_prefix_len_refcount[plen]--;
 177
 178       if (db->ip4_prefix_len_refcount[plen] == 0)
 179         {
 180           db->ip4_non_empty_dst_address_length_bitmap =
 181             clib_bitmap_set (db->ip4_non_empty_dst_address_length_bitmap,
 182                              32 - plen, 0);
 183           ip4_compute_prefix_lengths_in_search_order (db);
 184         }
 185     }
 186
 187   kv.key[0] = ((u64) vni << 32) | key.as_u32;
 188   kv.key[1] = 0;
 189   kv.key[2] = 0;
 190
 191   if (BV (clib_bihash_search) (&db->ip4_lookup_table, &kv, &value) == 0)
 192     old_val = value.value;
 193
 194   if (!is_add)
 195     BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */ );
 196   else
 197     {
 198       kv.value = val;
 199       BV (clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */ );
 200     }
 201   return old_val;
 202 }
 203
 204 static void
 205 ip6_compute_prefix_lengths_in_search_order (gid_dictionary_t * db)
 206 {
 207   int i;
 208   vec_reset_length (db->ip6_prefix_lengths_in_search_order);
 209   /* Note: bitmap reversed so this is in fact a longest prefix match */
 210
 211   /* *INDENT-OFF* */
 212   clib_bitmap_foreach (i, db->ip6_non_empty_dst_address_length_bitmap,
 213   ({
 214     int dst_address_length = 128 - i;
 215     vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
 216   }));
 217   /* *INDENT-ON* */
 218 }
 219
 220 static u32
 221 add_del_ip6_key (gid_dictionary_t * db, u32 vni, ip_prefix_t * pref, u32 val,
 222                  u8 is_add)
 223 {
 224   BVT (clib_bihash_kv) kv, value;
 225   u32 old_val = ~0;
 226   ip6_address_t key;
 227   u8 plen = ip_prefix_len (pref);
 228
 229   clib_memcpy (&key, &ip_prefix_v6 (pref), sizeof (key));
 230   ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
 231   if (is_add)
 232     {
 233       db->ip6_non_empty_dst_address_length_bitmap =
 234         clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 235                          128 - plen, 1);
 236       ip6_compute_prefix_lengths_in_search_order (db);
 237       db->ip6_prefix_len_refcount[plen]++;
 238     }
 239   else
 240     {
 241       ASSERT (db->ip6_prefix_len_refcount[plen] != 0);
 242
 243       db->ip6_prefix_len_refcount[plen]--;
 244
 245       if (db->ip6_prefix_len_refcount[plen] == 0)
 246         {
 247           db->ip6_non_empty_dst_address_length_bitmap =
 248             clib_bitmap_set (db->ip6_non_empty_dst_address_length_bitmap,
 249                              128 - plen, 0);
 250           ip6_compute_prefix_lengths_in_search_order (db);
 251         }
 252     }
 253
 254   kv.key[0] = key.as_u64[0];
 255   kv.key[1] = key.as_u64[1];
 256   kv.key[2] = (u64) vni;
 257 //  kv.key[2] = ((u64)((fib - im->fibs))<<32) | ip_prefix_len(key);
 258
 259   if (BV (clib_bihash_search) (&db->ip6_lookup_table, &kv, &value) == 0)
 260     old_val = value.value;
 261
 262   if (!is_add)
 263     BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */ );
 264   else
 265     {
 266       kv.value = val;
 267       BV (clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */ );
 268     }
 269   return old_val;
 270 }
 271
 272 static u32
 273 add_del_mac (gid_dictionary_t * db, u32 vni, u8 * mac, u32 val, u8 is_add)
 274 {
 275   BVT (clib_bihash_kv) kv, value;
 276   u32 old_val = ~0;
 277
 278   kv.key[0] = ((u64 *) mac)[0];
 279   kv.key[1] = (u64) vni;
 280   kv.key[2] = 0;
 281
 282   if (BV (clib_bihash_search) (&db->mac_lookup_table, &kv, &value) == 0)
 283     old_val = value.value;
 284
 285   if (!is_add)
 286     BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 0 /* is_add */ );
 287   else
 288     {
 289       kv.value = val;
 290       BV (clib_bihash_add_del) (&db->mac_lookup_table, &kv, 1 /* is_add */ );
 291     }
 292   return old_val;
 293 }
 294
 295 static u32
 296 add_del_ip (gid_dictionary_t * db, u32 vni, ip_prefix_t * key, u32 value,
 297             u8 is_add)
 298 {
 299   switch (ip_prefix_version (key))
 300     {
 301     case IP4:
 302       return add_del_ip4_key (db, vni, key, value, is_add);
 303       break;
 304     case IP6:
 305       return add_del_ip6_key (db, vni, key, value, is_add);
 306       break;
 307     default:
 308       clib_warning ("address type %d not supported!",
 309                     ip_prefix_version (key));
 310       break;
 311     }
 312   return ~0;
 313 }
 314
 315 u32
 316 gid_dictionary_add_del (gid_dictionary_t * db, gid_address_t * key, u32 value,
 317                         u8 is_add)
 318 {
 319   /* XXX for now this only works with ip-prefixes, no lcafs */
 320   switch (gid_address_type (key))
 321     {
 322     case GID_ADDR_IP_PREFIX:
 323       return add_del_ip (db, gid_address_vni (key), &gid_address_ippref (key),
 324                          value, is_add);
 325     case GID_ADDR_MAC:
 326       return add_del_mac (db, gid_address_vni (key), gid_address_mac (key),
 327                           value, is_add);
 328     default:
 329       clib_warning ("address type %d not supported!", gid_address_type (key));
 330       break;
 331     }
 332   return ~0;
 333 }
 334
 335 static void
 336 ip4_lookup_init (gid_dictionary_t * db)
 337 {
 338   uword i;
 339
 340   memset (db->ip4_prefix_len_refcount, 0,
 341           sizeof (db->ip4_prefix_len_refcount));
 342
 343   for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
 344     {
 345       u32 m;
 346
 347       if (i < 32)
 348         m = pow2_mask (i) << (32 - i);
 349       else
 350         m = ~0;
 351       db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
 352     }
 353   if (db->ip4_lookup_table_nbuckets == 0)
 354     db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 355
 356   db->ip4_lookup_table_nbuckets =
 357     1 << max_log2 (db->ip4_lookup_table_nbuckets);
 358
 359   if (db->ip4_lookup_table_size == 0)
 360     db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 361
 362   BV (clib_bihash_init) (&db->ip4_lookup_table, "ip4 lookup table",
 363                          db->ip4_lookup_table_nbuckets,
 364                          db->ip4_lookup_table_size);
 365 }
 366
 367 static void
 368 ip6_lookup_init (gid_dictionary_t * db)
 369 {
 370   uword i;
 371
 372   memset (db->ip6_prefix_len_refcount, 0,
 373           sizeof (db->ip6_prefix_len_refcount));
 374
 375   for (i = 0; i < ARRAY_LEN (db->ip6_fib_masks); i++)
 376     {
 377       u32 j, i0, i1;
 378
 379       i0 = i / 32;
 380       i1 = i % 32;
 381
 382       for (j = 0; j < i0; j++)
 383         db->ip6_fib_masks[i].as_u32[j] = ~0;
 384
 385       if (i1)
 386         db->ip6_fib_masks[i].as_u32[i0] =
 387           clib_host_to_net_u32 (pow2_mask (i1) << (32 - i1));
 388     }
 389
 390   if (db->ip6_lookup_table_nbuckets == 0)
 391     db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 392
 393   db->ip6_lookup_table_nbuckets =
 394     1 << max_log2 (db->ip6_lookup_table_nbuckets);
 395
 396   if (db->ip6_lookup_table_size == 0)
 397     db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 398
 399   BV (clib_bihash_init) (&db->ip6_lookup_table, "ip6 lookup table",
 400                          db->ip6_lookup_table_nbuckets,
 401                          db->ip6_lookup_table_size);
 402 }
 403
 404 static void
 405 mac_lookup_init (gid_dictionary_t * db)
 406 {
 407   if (db->mac_lookup_table_nbuckets == 0)
 408     db->mac_lookup_table_nbuckets = MAC_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
 409
 410   db->mac_lookup_table_nbuckets =
 411     1 << max_log2 (db->mac_lookup_table_nbuckets);
 412
 413   if (db->mac_lookup_table_size == 0)
 414     db->mac_lookup_table_size = MAC_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
 415
 416   BV (clib_bihash_init) (&db->mac_lookup_table, "mac lookup table",
 417                          db->mac_lookup_table_nbuckets,
 418                          db->mac_lookup_table_size);
 419 }
 420
 421 void
 422 gid_dictionary_init (gid_dictionary_t * db)
 423 {
 424   ip4_lookup_init (db);
 425   ip6_lookup_init (db);
 426   mac_lookup_init (db);
 427 }
 428
 429 /*
 430  * fd.io coding-style-patch-verification: ON
 431  *
 432  * Local Variables:
 433  * eval: (c-set-style "gnu")
 434  * End:
 435  */