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