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