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:
7 * http://www.apache.org/licenses/LICENSE-2.0
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.
16 #include <vnet/lisp-cp/gid_dictionary.h>
19 ip4_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t *key)
23 BVT(clib_bihash_kv) kv, value;
25 len = vec_len (db->ip4_prefix_lengths_in_search_order);
27 for (i = 0; i < len; i++)
29 int dst_address_length = db->ip4_prefix_lengths_in_search_order[i];
32 ASSERT(dst_address_length >= 0 && dst_address_length <= 32);
34 mask = &db->ip4_fib_masks[dst_address_length];
36 kv.key[0] = ((u64) vni << 32) | (ip_prefix_v4(key).as_u32 & mask->as_u32);
40 rv = BV(clib_bihash_search_inline_2)(&db->ip4_lookup_table, &kv, &value);
45 return GID_LOOKUP_MISS;
49 ip6_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t *key)
53 BVT(clib_bihash_kv) kv, value;
55 len = vec_len (db->ip6_prefix_lengths_in_search_order);
57 for (i = 0; i < len; i++)
59 int dst_address_length = db->ip6_prefix_lengths_in_search_order[i];
62 ASSERT(dst_address_length >= 0 && dst_address_length <= 128);
64 mask = &db->ip6_fib_masks[dst_address_length];
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];
70 rv = BV(clib_bihash_search_inline_2)(&db->ip6_lookup_table, &kv, &value);
75 return GID_LOOKUP_MISS;
79 ip_lookup (gid_dictionary_t * db, u32 vni, ip_prefix_t *key)
81 /* XXX for now this only works with ip-prefixes, no lcafs */
82 switch (ip_prefix_version (key))
85 return ip4_lookup (db, vni, key);
88 return ip6_lookup (db, vni, key);
91 clib_warning ("address type %d not supported!", ip_prefix_version(key));
98 gid_dictionary_lookup (gid_dictionary_t * db, gid_address_t * key)
100 /* XXX for now this only works with ip-prefixes, no lcafs */
101 switch (gid_address_type (key))
104 return ip_lookup (db, 0, &gid_address_ippref(key));
107 clib_warning ("address type %d not supported!", gid_address_type(key));
114 ip4_compute_prefix_lengths_in_search_order (gid_dictionary_t * db)
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,
121 int dst_address_length = 32 - i;
122 vec_add1 (db->ip4_prefix_lengths_in_search_order, dst_address_length);
127 add_del_ip4_key (gid_dictionary_t *db, u32 vni, ip_prefix_t * pref, u32 val,
130 BVT(clib_bihash_kv) kv, value;
133 u8 plen = ip_prefix_len (pref);
135 clib_memcpy (&key, &ip_prefix_v4(pref), sizeof(key));
136 key.as_u32 &= db->ip4_fib_masks[plen].as_u32;
139 db->ip4_non_empty_dst_address_length_bitmap = clib_bitmap_set (
140 db->ip4_non_empty_dst_address_length_bitmap, 32 - plen,
142 ip4_compute_prefix_lengths_in_search_order (db);
144 db->ip4_prefix_len_refcount[plen]++;
148 ASSERT(db->ip4_prefix_len_refcount[plen] != 0);
150 db->ip4_prefix_len_refcount[plen]--;
152 if (db->ip4_prefix_len_refcount[plen] == 0)
154 db->ip4_non_empty_dst_address_length_bitmap = clib_bitmap_set (
155 db->ip4_non_empty_dst_address_length_bitmap, 32 - plen,
157 ip4_compute_prefix_lengths_in_search_order (db);
161 kv.key[0] = ((u64) vni << 32) | key.as_u32;
165 if (BV(clib_bihash_search)(&db->ip4_lookup_table, &kv, &value) == 0)
166 old_val = value.value;
169 BV(clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 0 /* is_add */);
173 BV(clib_bihash_add_del) (&db->ip4_lookup_table, &kv, 1 /* is_add */);
179 ip6_compute_prefix_lengths_in_search_order (gid_dictionary_t * db)
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,
186 int dst_address_length = 128 - i;
187 vec_add1 (db->ip6_prefix_lengths_in_search_order, dst_address_length);
192 add_del_ip6_key (gid_dictionary_t *db, u32 vni, ip_prefix_t *pref, u32 val,
195 BVT(clib_bihash_kv) kv, value;
198 u8 plen = ip_prefix_len (pref);
200 clib_memcpy (&key, &ip_prefix_v6(pref), sizeof(key));
201 ip6_address_mask (&key, &db->ip6_fib_masks[plen]);
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]++;
211 ASSERT(db->ip6_prefix_len_refcount[plen] != 0);
213 db->ip6_prefix_len_refcount[plen]--;
215 if (db->ip6_prefix_len_refcount[plen] == 0)
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);
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);
228 if (BV(clib_bihash_search)(&db->ip6_lookup_table, &kv, &value) == 0)
229 old_val = value.value;
232 BV(clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 0 /* is_add */);
236 BV(clib_bihash_add_del) (&db->ip6_lookup_table, &kv, 1 /* is_add */);
242 gid_dictionary_add_del_ip (gid_dictionary_t *db, u32 iid, ip_prefix_t *key,
243 u32 value, u8 is_add)
245 switch (ip_prefix_version (key))
248 return add_del_ip4_key (db, iid, key, value, is_add);
251 return add_del_ip6_key (db, iid, key, value, is_add);
254 clib_warning("address type %d not supported!", ip_prefix_version (key));
261 gid_dictionary_add_del (gid_dictionary_t *db, gid_address_t *key, u32 value,
264 /* XXX for now this only works with ip-prefixes, no lcafs */
265 switch (gid_address_type (key))
268 return gid_dictionary_add_del_ip (db, 0, &gid_address_ippref(key), value,
272 clib_warning ("address type %d not supported!", gid_address_type (key));
279 ip4_lookup_init (gid_dictionary_t * db)
283 memset(db->ip4_prefix_len_refcount, 0, sizeof(db->ip4_prefix_len_refcount));
285 for (i = 0; i < ARRAY_LEN (db->ip4_fib_masks); i++)
290 m = pow2_mask (i) << (32 - i);
293 db->ip4_fib_masks[i].as_u32 = clib_host_to_net_u32 (m);
295 if (db->ip4_lookup_table_nbuckets == 0)
296 db->ip4_lookup_table_nbuckets = IP4_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
298 db->ip4_lookup_table_nbuckets = 1 << max_log2 (db->ip4_lookup_table_nbuckets);
300 if (db->ip4_lookup_table_size == 0)
301 db->ip4_lookup_table_size = IP4_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
303 BV(clib_bihash_init) (&db->ip4_lookup_table, "ip4 lookup table",
304 db->ip4_lookup_table_nbuckets, db->ip4_lookup_table_size);
308 ip6_lookup_init (gid_dictionary_t * db)
312 memset(db->ip6_prefix_len_refcount, 0, sizeof(db->ip6_prefix_len_refcount));
314 for (i = 0; i < ARRAY_LEN(db->ip6_fib_masks); i++)
321 for (j = 0; j < i0; j++)
322 db->ip6_fib_masks[i].as_u32[j] = ~0;
325 db->ip6_fib_masks[i].as_u32[i0] = clib_host_to_net_u32 (
326 pow2_mask (i1) << (32 - i1));
329 if (db->ip6_lookup_table_nbuckets == 0)
330 db->ip6_lookup_table_nbuckets = IP6_LOOKUP_DEFAULT_HASH_NUM_BUCKETS;
332 db->ip6_lookup_table_nbuckets = 1 << max_log2 (db->ip6_lookup_table_nbuckets);
334 if (db->ip6_lookup_table_size == 0)
335 db->ip6_lookup_table_size = IP6_LOOKUP_DEFAULT_HASH_MEMORY_SIZE;
337 BV(clib_bihash_init) (&db->ip6_lookup_table, "ip6 lookup table",
338 db->ip6_lookup_table_nbuckets, db->ip6_lookup_table_size);
342 gid_dictionary_init (gid_dictionary_t * db)
344 ip4_lookup_init (db);
345 ip6_lookup_init (db);