Line data Source code
1 : /*
2 : * Copyright (c) 2015 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 : * ip/ip4_fib.h: ip4 mtrie fib
17 : *
18 : * Copyright (c) 2012 Eliot Dresselhaus
19 : *
20 : * Permission is hereby granted, free of charge, to any person obtaining
21 : * a copy of this software and associated documentation files (the
22 : * "Software"), to deal in the Software without restriction, including
23 : * without limitation the rights to use, copy, modify, merge, publish,
24 : * distribute, sublicense, and/or sell copies of the Software, and to
25 : * permit persons to whom the Software is furnished to do so, subject to
26 : * the following conditions:
27 : *
28 : * The above copyright notice and this permission notice shall be
29 : * included in all copies or substantial portions of the Software.
30 : *
31 : * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
32 : * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
33 : * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
34 : * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
35 : * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
36 : * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
37 : * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
38 : */
39 :
40 : #include <vnet/ip/ip.h>
41 : #include <vnet/ip/ip4_mtrie.h>
42 : #include <vnet/fib/ip4_fib.h>
43 :
44 :
45 : /**
46 : * Global pool of IPv4 8bit PLYs
47 : */
48 : ip4_mtrie_8_ply_t *ip4_ply_pool;
49 :
50 : always_inline u32
51 63533900 : ip4_mtrie_leaf_is_non_empty (ip4_mtrie_8_ply_t *p, u8 dst_byte)
52 : {
53 : /*
54 : * It's 'non-empty' if the length of the leaf stored is greater than the
55 : * length of a leaf in the covering ply. i.e. the leaf is more specific
56 : * than it's would be cover in the covering ply
57 : */
58 63533900 : if (p->dst_address_bits_of_leaves[dst_byte] > p->dst_address_bits_base)
59 410158 : return (1);
60 63123700 : return (0);
61 : }
62 :
63 : always_inline ip4_mtrie_leaf_t
64 83203200 : ip4_mtrie_leaf_set_adj_index (u32 adj_index)
65 : {
66 : ip4_mtrie_leaf_t l;
67 83203200 : l = 1 + 2 * adj_index;
68 83203200 : ASSERT (ip4_mtrie_leaf_get_adj_index (l) == adj_index);
69 83203200 : return l;
70 : }
71 :
72 : always_inline u32
73 17518200 : ip4_mtrie_leaf_is_next_ply (ip4_mtrie_leaf_t n)
74 : {
75 17518200 : return (n & 1) == 0;
76 : }
77 :
78 : always_inline u32
79 74600 : ip4_mtrie_leaf_get_next_ply_index (ip4_mtrie_leaf_t n)
80 : {
81 74600 : ASSERT (ip4_mtrie_leaf_is_next_ply (n));
82 74600 : return n >> 1;
83 : }
84 :
85 : always_inline ip4_mtrie_leaf_t
86 9290 : ip4_mtrie_leaf_set_next_ply_index (u32 i)
87 : {
88 : ip4_mtrie_leaf_t l;
89 9290 : l = 0 + 2 * i;
90 9290 : ASSERT (ip4_mtrie_leaf_get_next_ply_index (l) == i);
91 9290 : return l;
92 : }
93 :
94 : static void
95 9290 : ply_8_init (ip4_mtrie_8_ply_t *p, ip4_mtrie_leaf_t init, uword prefix_len,
96 : u32 ply_base_len)
97 : {
98 9290 : p->n_non_empty_leafs = prefix_len > ply_base_len ? ARRAY_LEN (p->leaves) : 0;
99 9290 : clib_memset_u8 (p->dst_address_bits_of_leaves, prefix_len,
100 : sizeof (p->dst_address_bits_of_leaves));
101 9290 : p->dst_address_bits_base = ply_base_len;
102 :
103 9290 : clib_memset_u32 (p->leaves, init, ARRAY_LEN (p->leaves));
104 9290 : }
105 :
106 : static void
107 859 : ply_16_init (ip4_mtrie_16_ply_t *p, ip4_mtrie_leaf_t init, uword prefix_len)
108 : {
109 859 : clib_memset_u8 (p->dst_address_bits_of_leaves, prefix_len,
110 : sizeof (p->dst_address_bits_of_leaves));
111 859 : clib_memset_u32 (p->leaves, init, ARRAY_LEN (p->leaves));
112 859 : }
113 :
114 : static ip4_mtrie_leaf_t
115 9290 : ply_create (ip4_mtrie_leaf_t init_leaf, u32 leaf_prefix_len, u32 ply_base_len)
116 : {
117 : ip4_mtrie_8_ply_t *p;
118 : ip4_mtrie_leaf_t l;
119 9290 : u8 need_barrier_sync = pool_get_will_expand (ip4_ply_pool);
120 9290 : vlib_main_t *vm = vlib_get_main ();
121 9290 : ASSERT (vm->thread_index == 0);
122 :
123 9290 : if (need_barrier_sync)
124 1957 : vlib_worker_thread_barrier_sync (vm);
125 :
126 : /* Get cache aligned ply. */
127 9290 : pool_get_aligned (ip4_ply_pool, p, CLIB_CACHE_LINE_BYTES);
128 :
129 9290 : ply_8_init (p, init_leaf, leaf_prefix_len, ply_base_len);
130 9290 : l = ip4_mtrie_leaf_set_next_ply_index (p - ip4_ply_pool);
131 :
132 9290 : if (need_barrier_sync)
133 1957 : vlib_worker_thread_barrier_release (vm);
134 :
135 9290 : return l;
136 : }
137 :
138 : always_inline ip4_mtrie_8_ply_t *
139 65290 : get_next_ply_for_leaf (ip4_mtrie_leaf_t l)
140 : {
141 65290 : uword n = ip4_mtrie_leaf_get_next_ply_index (l);
142 :
143 65290 : return pool_elt_at_index (ip4_ply_pool, n);
144 : }
145 :
146 : void
147 265 : ip4_mtrie_16_free (ip4_mtrie_16_t *m)
148 : {
149 : /* the root ply is embedded so there is nothing to do,
150 : * the assumption being that the IP4 FIB table has emptied the trie
151 : * before deletion.
152 : */
153 : #if CLIB_DEBUG > 0
154 : int i;
155 17367300 : for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
156 : {
157 17367000 : ASSERT (!ip4_mtrie_leaf_is_next_ply (m->root_ply.leaves[i]));
158 : }
159 : #endif
160 265 : }
161 :
162 : void
163 859 : ip4_mtrie_16_init (ip4_mtrie_16_t *m)
164 : {
165 859 : ply_16_init (&m->root_ply, IP4_MTRIE_LEAF_EMPTY, 0);
166 859 : }
167 :
168 : void
169 0 : ip4_mtrie_8_free (ip4_mtrie_8_t *m)
170 : {
171 : /* the root ply is embedded so there is nothing to do,
172 : * the assumption being that the IP4 FIB table has emptied the trie
173 : * before deletion.
174 : */
175 0 : ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
176 :
177 : #if CLIB_DEBUG > 0
178 : int i;
179 0 : for (i = 0; i < ARRAY_LEN (root->leaves); i++)
180 : {
181 0 : ASSERT (!ip4_mtrie_leaf_is_next_ply (root->leaves[i]));
182 : }
183 : #endif
184 :
185 0 : pool_put (ip4_ply_pool, root);
186 0 : }
187 :
188 : void
189 0 : ip4_mtrie_8_init (ip4_mtrie_8_t *m)
190 : {
191 : ip4_mtrie_8_ply_t *root;
192 :
193 0 : pool_get (ip4_ply_pool, root);
194 0 : m->root_ply = root - ip4_ply_pool;
195 :
196 0 : ply_8_init (root, IP4_MTRIE_LEAF_EMPTY, 0, 0);
197 0 : }
198 :
199 : typedef struct
200 : {
201 : ip4_address_t dst_address;
202 : u32 dst_address_length;
203 : u32 adj_index;
204 : u32 cover_address_length;
205 : u32 cover_adj_index;
206 : } ip4_mtrie_set_unset_leaf_args_t;
207 :
208 : static void
209 28 : set_ply_with_more_specific_leaf (ip4_mtrie_8_ply_t *ply,
210 : ip4_mtrie_leaf_t new_leaf,
211 : uword new_leaf_dst_address_bits)
212 : {
213 : ip4_mtrie_leaf_t old_leaf;
214 : uword i;
215 :
216 28 : ASSERT (ip4_mtrie_leaf_is_terminal (new_leaf));
217 :
218 7196 : for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
219 : {
220 7168 : old_leaf = ply->leaves[i];
221 :
222 : /* Recurse into sub plies. */
223 7168 : if (!ip4_mtrie_leaf_is_terminal (old_leaf))
224 : {
225 1 : ip4_mtrie_8_ply_t *sub_ply = get_next_ply_for_leaf (old_leaf);
226 1 : set_ply_with_more_specific_leaf (sub_ply, new_leaf,
227 : new_leaf_dst_address_bits);
228 : }
229 :
230 : /* Replace less specific terminal leaves with new leaf. */
231 7167 : else if (new_leaf_dst_address_bits >=
232 7167 : ply->dst_address_bits_of_leaves[i])
233 : {
234 6872 : clib_atomic_store_rel_n (&ply->leaves[i], new_leaf);
235 6872 : ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
236 6872 : ply->n_non_empty_leafs += ip4_mtrie_leaf_is_non_empty (ply, i);
237 : }
238 : }
239 28 : }
240 :
241 : static void
242 36461 : set_leaf (const ip4_mtrie_set_unset_leaf_args_t *a, u32 old_ply_index,
243 : u32 dst_address_byte_index)
244 : {
245 : ip4_mtrie_leaf_t old_leaf, new_leaf;
246 : i32 n_dst_bits_next_plies;
247 : u8 dst_byte;
248 : ip4_mtrie_8_ply_t *old_ply;
249 :
250 36461 : old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
251 :
252 36461 : ASSERT (a->dst_address_length <= 32);
253 36461 : ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
254 :
255 : /* how many bits of the destination address are in the next PLY */
256 36461 : n_dst_bits_next_plies =
257 36461 : a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
258 :
259 36461 : dst_byte = a->dst_address.as_u8[dst_address_byte_index];
260 :
261 : /* Number of bits next plies <= 0 => insert leaves this ply. */
262 36461 : if (n_dst_bits_next_plies <= 0)
263 : {
264 : /* The mask length of the address to insert maps to this ply */
265 : uword old_leaf_is_terminal;
266 : u32 i, n_dst_bits_this_ply;
267 :
268 : /* The number of bits, and hence slots/buckets, we will fill */
269 19522 : n_dst_bits_this_ply = clib_min (8, -n_dst_bits_next_plies);
270 19522 : ASSERT ((a->dst_address.as_u8[dst_address_byte_index] &
271 : pow2_mask (n_dst_bits_this_ply)) == 0);
272 :
273 : /* Starting at the value of the byte at this section of the v4 address
274 : * fill the buckets/slots of the ply */
275 41406 : for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
276 : {
277 : ip4_mtrie_8_ply_t *new_ply;
278 :
279 21884 : old_leaf = old_ply->leaves[i];
280 21884 : old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
281 :
282 21884 : if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
283 : {
284 : /* The new leaf is more or equally specific than the one currently
285 : * occupying the slot */
286 21610 : new_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
287 :
288 21610 : if (old_leaf_is_terminal)
289 : {
290 : /* The current leaf is terminal, we can replace it with
291 : * the new one */
292 21584 : old_ply->n_non_empty_leafs -=
293 21584 : ip4_mtrie_leaf_is_non_empty (old_ply, i);
294 :
295 21584 : old_ply->dst_address_bits_of_leaves[i] =
296 21584 : a->dst_address_length;
297 21584 : clib_atomic_store_rel_n (&old_ply->leaves[i], new_leaf);
298 :
299 21584 : old_ply->n_non_empty_leafs +=
300 21584 : ip4_mtrie_leaf_is_non_empty (old_ply, i);
301 21584 : ASSERT (old_ply->n_non_empty_leafs <=
302 : ARRAY_LEN (old_ply->leaves));
303 : }
304 : else
305 : {
306 : /* Existing leaf points to another ply. We need to place
307 : * new_leaf into all more specific slots. */
308 26 : new_ply = get_next_ply_for_leaf (old_leaf);
309 26 : set_ply_with_more_specific_leaf (new_ply, new_leaf,
310 26 : a->dst_address_length);
311 : }
312 : }
313 274 : else if (!old_leaf_is_terminal)
314 : {
315 : /* The current leaf is less specific and not termial (i.e. a ply),
316 : * recurse on down the trie */
317 4 : new_ply = get_next_ply_for_leaf (old_leaf);
318 4 : set_leaf (a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
319 : }
320 : /*
321 : * else
322 : * the route we are adding is less specific than the leaf currently
323 : * occupying this slot. leave it there
324 : */
325 : }
326 : }
327 : else
328 : {
329 : /* The address to insert requires us to move down at a lower level of
330 : * the trie - recurse on down */
331 : ip4_mtrie_8_ply_t *new_ply;
332 : u8 ply_base_len;
333 :
334 16939 : ply_base_len = 8 * (dst_address_byte_index + 1);
335 :
336 16939 : old_leaf = old_ply->leaves[dst_byte];
337 :
338 16939 : if (ip4_mtrie_leaf_is_terminal (old_leaf))
339 : {
340 : /* There is a leaf occupying the slot. Replace it with a new ply */
341 5488 : old_ply->n_non_empty_leafs -=
342 5488 : ip4_mtrie_leaf_is_non_empty (old_ply, dst_byte);
343 :
344 5488 : new_leaf = ply_create (old_leaf,
345 5488 : old_ply->dst_address_bits_of_leaves[dst_byte],
346 : ply_base_len);
347 5488 : new_ply = get_next_ply_for_leaf (new_leaf);
348 :
349 : /* Refetch since ply_create may move pool. */
350 5488 : old_ply = pool_elt_at_index (ip4_ply_pool, old_ply_index);
351 :
352 5488 : clib_atomic_store_rel_n (&old_ply->leaves[dst_byte], new_leaf);
353 5488 : old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
354 :
355 5488 : old_ply->n_non_empty_leafs +=
356 5488 : ip4_mtrie_leaf_is_non_empty (old_ply, dst_byte);
357 5488 : ASSERT (old_ply->n_non_empty_leafs >= 0);
358 : }
359 : else
360 11451 : new_ply = get_next_ply_for_leaf (old_leaf);
361 :
362 16939 : set_leaf (a, new_ply - ip4_ply_pool, dst_address_byte_index + 1);
363 : }
364 36461 : }
365 :
366 : static void
367 22127 : set_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
368 : {
369 : ip4_mtrie_leaf_t old_leaf, new_leaf;
370 : ip4_mtrie_16_ply_t *old_ply;
371 : i32 n_dst_bits_next_plies;
372 : u16 dst_byte;
373 :
374 22127 : old_ply = &m->root_ply;
375 :
376 22127 : ASSERT (a->dst_address_length <= 32);
377 :
378 : /* how many bits of the destination address are in the next PLY */
379 22127 : n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
380 :
381 22127 : dst_byte = a->dst_address.as_u16[0];
382 :
383 : /* Number of bits next plies <= 0 => insert leaves this ply. */
384 22127 : if (n_dst_bits_next_plies <= 0)
385 : {
386 : /* The mask length of the address to insert maps to this ply */
387 : uword old_leaf_is_terminal;
388 : u32 i, n_dst_bits_this_ply;
389 :
390 : /* The number of bits, and hence slots/buckets, we will fill */
391 2614 : n_dst_bits_this_ply = 16 - a->dst_address_length;
392 2614 : ASSERT ((clib_host_to_net_u16 (a->dst_address.as_u16[0]) &
393 : pow2_mask (n_dst_bits_this_ply)) == 0);
394 :
395 : /* Starting at the value of the byte at this section of the v4 address
396 : * fill the buckets/slots of the ply */
397 63340900 : for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
398 : {
399 : ip4_mtrie_8_ply_t *new_ply;
400 : u16 slot;
401 :
402 63338300 : slot = clib_net_to_host_u16 (dst_byte);
403 63338300 : slot += i;
404 63338300 : slot = clib_host_to_net_u16 (slot);
405 :
406 63338300 : old_leaf = old_ply->leaves[slot];
407 63338300 : old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
408 :
409 63338300 : if (a->dst_address_length >=
410 63338300 : old_ply->dst_address_bits_of_leaves[slot])
411 : {
412 : /* The new leaf is more or equally specific than the one currently
413 : * occupying the slot */
414 63338200 : new_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
415 :
416 63338200 : if (old_leaf_is_terminal)
417 : {
418 : /* The current leaf is terminal, we can replace it with
419 : * the new one */
420 63338200 : old_ply->dst_address_bits_of_leaves[slot] =
421 63338200 : a->dst_address_length;
422 63338200 : clib_atomic_store_rel_n (&old_ply->leaves[slot], new_leaf);
423 : }
424 : else
425 : {
426 : /* Existing leaf points to another ply. We need to place
427 : * new_leaf into all more specific slots. */
428 1 : new_ply = get_next_ply_for_leaf (old_leaf);
429 1 : set_ply_with_more_specific_leaf (new_ply, new_leaf,
430 1 : a->dst_address_length);
431 : }
432 : }
433 5 : else if (!old_leaf_is_terminal)
434 : {
435 : /* The current leaf is less specific and not termial (i.e. a ply),
436 : * recurse on down the trie */
437 5 : new_ply = get_next_ply_for_leaf (old_leaf);
438 5 : set_leaf (a, new_ply - ip4_ply_pool, 2);
439 : }
440 : /*
441 : * else
442 : * the route we are adding is less specific than the leaf currently
443 : * occupying this slot. leave it there
444 : */
445 : }
446 : }
447 : else
448 : {
449 : /* The address to insert requires us to move down at a lower level of
450 : * the trie - recurse on down */
451 : ip4_mtrie_8_ply_t *new_ply;
452 : u8 ply_base_len;
453 :
454 19513 : ply_base_len = 16;
455 :
456 19513 : old_leaf = old_ply->leaves[dst_byte];
457 :
458 19513 : if (ip4_mtrie_leaf_is_terminal (old_leaf))
459 : {
460 : /* There is a leaf occupying the slot. Replace it with a new ply */
461 3802 : new_leaf = ply_create (old_leaf,
462 3802 : old_ply->dst_address_bits_of_leaves[dst_byte],
463 : ply_base_len);
464 3802 : new_ply = get_next_ply_for_leaf (new_leaf);
465 :
466 3802 : clib_atomic_store_rel_n (&old_ply->leaves[dst_byte], new_leaf);
467 3802 : old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
468 : }
469 : else
470 15711 : new_ply = get_next_ply_for_leaf (old_leaf);
471 :
472 19513 : set_leaf (a, new_ply - ip4_ply_pool, 2);
473 : }
474 22127 : }
475 :
476 : static uword
477 28791 : unset_leaf (const ip4_mtrie_set_unset_leaf_args_t *a,
478 : ip4_mtrie_8_ply_t *old_ply, u32 dst_address_byte_index)
479 : {
480 : ip4_mtrie_leaf_t old_leaf, del_leaf;
481 : i32 n_dst_bits_next_plies;
482 : i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
483 : u8 dst_byte;
484 :
485 28791 : ASSERT (a->dst_address_length <= 32);
486 28791 : ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
487 :
488 28791 : n_dst_bits_next_plies =
489 28791 : a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
490 :
491 28791 : dst_byte = a->dst_address.as_u8[dst_address_byte_index];
492 28791 : if (n_dst_bits_next_plies < 0)
493 929 : dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
494 :
495 28791 : n_dst_bits_this_ply =
496 28791 : n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
497 28791 : n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
498 :
499 28791 : del_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
500 :
501 286203 : for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
502 : {
503 263968 : old_leaf = old_ply->leaves[i];
504 263968 : old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
505 :
506 263968 : if (old_leaf == del_leaf ||
507 13679 : (!old_leaf_is_terminal &&
508 13679 : unset_leaf (a, get_next_ply_for_leaf (old_leaf),
509 : dst_address_byte_index + 1)))
510 : {
511 252514 : old_ply->n_non_empty_leafs -=
512 252514 : ip4_mtrie_leaf_is_non_empty (old_ply, i);
513 :
514 252514 : clib_atomic_store_rel_n (
515 : &old_ply->leaves[i],
516 : ip4_mtrie_leaf_set_adj_index (a->cover_adj_index));
517 252514 : old_ply->dst_address_bits_of_leaves[i] = a->cover_address_length;
518 :
519 252514 : old_ply->n_non_empty_leafs +=
520 252514 : ip4_mtrie_leaf_is_non_empty (old_ply, i);
521 :
522 252514 : ASSERT (old_ply->n_non_empty_leafs >= 0);
523 252514 : if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
524 : {
525 6556 : pool_put (ip4_ply_pool, old_ply);
526 : /* Old ply was deleted. */
527 6556 : return 1;
528 : }
529 : #if CLIB_DEBUG > 0
530 245958 : else if (dst_address_byte_index)
531 : {
532 245958 : int ii, count = 0;
533 63211200 : for (ii = 0; ii < ARRAY_LEN (old_ply->leaves); ii++)
534 : {
535 62965200 : count += ip4_mtrie_leaf_is_non_empty (old_ply, ii);
536 : }
537 245958 : ASSERT (count);
538 : }
539 : #endif
540 : }
541 : }
542 :
543 : /* Old ply was not deleted. */
544 22235 : return 0;
545 : }
546 :
547 : static void
548 15932 : unset_root_leaf (ip4_mtrie_16_t *m, const ip4_mtrie_set_unset_leaf_args_t *a)
549 : {
550 : ip4_mtrie_leaf_t old_leaf, del_leaf;
551 : i32 n_dst_bits_next_plies;
552 : i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
553 : u16 dst_byte;
554 : ip4_mtrie_16_ply_t *old_ply;
555 :
556 15932 : ASSERT (a->dst_address_length <= 32);
557 :
558 15932 : old_ply = &m->root_ply;
559 15932 : n_dst_bits_next_plies = a->dst_address_length - BITS (u16);
560 :
561 15932 : dst_byte = a->dst_address.as_u16[0];
562 :
563 15932 : n_dst_bits_this_ply = (n_dst_bits_next_plies <= 0 ?
564 15932 : (16 - a->dst_address_length) : 0);
565 :
566 15932 : del_leaf = ip4_mtrie_leaf_set_adj_index (a->adj_index);
567 :
568 : /* Starting at the value of the byte at this section of the v4 address
569 : * fill the buckets/slots of the ply */
570 19574600 : for (i = 0; i < (1 << n_dst_bits_this_ply); i++)
571 : {
572 : u16 slot;
573 :
574 19558700 : slot = clib_net_to_host_u16 (dst_byte);
575 19558700 : slot += i;
576 19558700 : slot = clib_host_to_net_u16 (slot);
577 :
578 19558700 : old_leaf = old_ply->leaves[slot];
579 19558700 : old_leaf_is_terminal = ip4_mtrie_leaf_is_terminal (old_leaf);
580 :
581 19558700 : if (old_leaf == del_leaf ||
582 15112 : (!old_leaf_is_terminal &&
583 15112 : unset_leaf (a, get_next_ply_for_leaf (old_leaf), 2)))
584 : {
585 19546100 : clib_atomic_store_rel_n (
586 : &old_ply->leaves[slot],
587 : ip4_mtrie_leaf_set_adj_index (a->cover_adj_index));
588 19546100 : old_ply->dst_address_bits_of_leaves[slot] = a->cover_address_length;
589 : }
590 : }
591 15932 : }
592 :
593 : void
594 22127 : ip4_mtrie_16_route_add (ip4_mtrie_16_t *m, const ip4_address_t *dst_address,
595 : u32 dst_address_length, u32 adj_index)
596 : {
597 : ip4_mtrie_set_unset_leaf_args_t a;
598 22127 : ip4_main_t *im = &ip4_main;
599 :
600 : /* Honor dst_address_length. Fib masks are in network byte order */
601 22127 : a.dst_address.as_u32 = (dst_address->as_u32 &
602 22127 : im->fib_masks[dst_address_length]);
603 22127 : a.dst_address_length = dst_address_length;
604 22127 : a.adj_index = adj_index;
605 :
606 22127 : set_root_leaf (m, &a);
607 22127 : }
608 :
609 : void
610 0 : ip4_mtrie_8_route_add (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
611 : u32 dst_address_length, u32 adj_index)
612 : {
613 : ip4_mtrie_set_unset_leaf_args_t a;
614 0 : ip4_main_t *im = &ip4_main;
615 :
616 : /* Honor dst_address_length. Fib masks are in network byte order */
617 0 : a.dst_address.as_u32 =
618 0 : (dst_address->as_u32 & im->fib_masks[dst_address_length]);
619 0 : a.dst_address_length = dst_address_length;
620 0 : a.adj_index = adj_index;
621 :
622 0 : ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
623 :
624 0 : set_leaf (&a, root - ip4_ply_pool, 0);
625 0 : }
626 :
627 : void
628 15932 : ip4_mtrie_16_route_del (ip4_mtrie_16_t *m, const ip4_address_t *dst_address,
629 : u32 dst_address_length, u32 adj_index,
630 : u32 cover_address_length, u32 cover_adj_index)
631 : {
632 : ip4_mtrie_set_unset_leaf_args_t a;
633 15932 : ip4_main_t *im = &ip4_main;
634 :
635 : /* Honor dst_address_length. Fib masks are in network byte order */
636 15932 : a.dst_address.as_u32 = (dst_address->as_u32 &
637 15932 : im->fib_masks[dst_address_length]);
638 15932 : a.dst_address_length = dst_address_length;
639 15932 : a.adj_index = adj_index;
640 15932 : a.cover_adj_index = cover_adj_index;
641 15932 : a.cover_address_length = cover_address_length;
642 :
643 : /* the top level ply is never removed */
644 15932 : unset_root_leaf (m, &a);
645 15932 : }
646 :
647 : void
648 0 : ip4_mtrie_8_route_del (ip4_mtrie_8_t *m, const ip4_address_t *dst_address,
649 : u32 dst_address_length, u32 adj_index,
650 : u32 cover_address_length, u32 cover_adj_index)
651 : {
652 0 : ip4_main_t *im = &ip4_main;
653 :
654 : /* Honor dst_address_length. Fib masks are in network byte order */
655 0 : ip4_mtrie_set_unset_leaf_args_t a = {
656 : .dst_address.as_u32 =
657 0 : (dst_address->as_u32 & im->fib_masks[dst_address_length]),
658 : .dst_address_length = dst_address_length,
659 : .adj_index = adj_index,
660 : .cover_adj_index = cover_adj_index,
661 : .cover_address_length = cover_address_length,
662 : };
663 :
664 : /* the top level ply is never removed */
665 0 : ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
666 :
667 0 : unset_leaf (&a, root, 0);
668 0 : }
669 :
670 : /* Returns number of bytes of memory used by mtrie. */
671 : static uword
672 10 : mtrie_ply_memory_usage (ip4_mtrie_8_ply_t *p)
673 : {
674 : uword bytes, i;
675 :
676 10 : bytes = sizeof (p[0]);
677 2570 : for (i = 0; i < ARRAY_LEN (p->leaves); i++)
678 : {
679 2560 : ip4_mtrie_leaf_t l = p->leaves[i];
680 2560 : if (ip4_mtrie_leaf_is_next_ply (l))
681 6 : bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
682 : }
683 :
684 10 : return bytes;
685 : }
686 :
687 : /* Returns number of bytes of memory used by mtrie. */
688 : uword
689 1 : ip4_mtrie_16_memory_usage (ip4_mtrie_16_t *m)
690 : {
691 : uword bytes, i;
692 :
693 1 : bytes = sizeof (*m);
694 65537 : for (i = 0; i < ARRAY_LEN (m->root_ply.leaves); i++)
695 : {
696 65536 : ip4_mtrie_leaf_t l = m->root_ply.leaves[i];
697 65536 : if (ip4_mtrie_leaf_is_next_ply (l))
698 4 : bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
699 : }
700 :
701 1 : return bytes;
702 : }
703 : uword
704 0 : ip4_mtrie_8_memory_usage (ip4_mtrie_8_t *m)
705 : {
706 0 : ip4_mtrie_8_ply_t *root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
707 : uword bytes, i;
708 :
709 0 : bytes = sizeof (*m);
710 0 : for (i = 0; i < ARRAY_LEN (root->leaves); i++)
711 : {
712 0 : ip4_mtrie_leaf_t l = root->leaves[i];
713 0 : if (ip4_mtrie_leaf_is_next_ply (l))
714 0 : bytes += mtrie_ply_memory_usage (get_next_ply_for_leaf (l));
715 : }
716 :
717 0 : return bytes;
718 : }
719 :
720 : static u8 *
721 8475 : format_ip4_mtrie_leaf (u8 *s, va_list *va)
722 : {
723 8475 : ip4_mtrie_leaf_t l = va_arg (*va, ip4_mtrie_leaf_t);
724 :
725 8475 : if (ip4_mtrie_leaf_is_terminal (l))
726 8465 : s = format (s, "lb-index %d", ip4_mtrie_leaf_get_adj_index (l));
727 : else
728 10 : s = format (s, "next ply %d", ip4_mtrie_leaf_get_next_ply_index (l));
729 8475 : return s;
730 : }
731 :
732 : #define FORMAT_PLY(s, _p, _a, _i, _base_address, _ply_max_len, _indent) \
733 : ({ \
734 : u32 a, ia_length; \
735 : ip4_address_t ia; \
736 : ip4_mtrie_leaf_t _l = (_p)->leaves[(_i)]; \
737 : \
738 : a = (_base_address) + ((_a) << (32 - (_ply_max_len))); \
739 : ia.as_u32 = clib_host_to_net_u32 (a); \
740 : ia_length = (_p)->dst_address_bits_of_leaves[(_i)]; \
741 : s = format (s, "\n%U%U %U", format_white_space, (_indent) + 4, \
742 : format_ip4_address_and_length, &ia, ia_length, \
743 : format_ip4_mtrie_leaf, _l); \
744 : \
745 : if (ip4_mtrie_leaf_is_next_ply (_l)) \
746 : s = format (s, "\n%U", format_ip4_mtrie_ply, m, a, (_indent) + 8, \
747 : ip4_mtrie_leaf_get_next_ply_index (_l)); \
748 : s; \
749 : })
750 :
751 : static u8 *
752 10 : format_ip4_mtrie_ply (u8 *s, va_list *va)
753 : {
754 10 : ip4_mtrie_16_t *m = va_arg (*va, ip4_mtrie_16_t *);
755 10 : u32 base_address = va_arg (*va, u32);
756 10 : u32 indent = va_arg (*va, u32);
757 10 : u32 ply_index = va_arg (*va, u32);
758 : ip4_mtrie_8_ply_t *p;
759 : int i;
760 :
761 10 : p = pool_elt_at_index (ip4_ply_pool, ply_index);
762 10 : s = format (s, "%Uply index %d, %d non-empty leaves",
763 : format_white_space, indent, ply_index, p->n_non_empty_leafs);
764 :
765 2570 : for (i = 0; i < ARRAY_LEN (p->leaves); i++)
766 : {
767 2560 : if (ip4_mtrie_leaf_is_non_empty (p, i))
768 : {
769 25 : s = FORMAT_PLY (s, p, i, i, base_address,
770 : p->dst_address_bits_base + 8, indent);
771 : }
772 : }
773 :
774 10 : return s;
775 : }
776 :
777 : u8 *
778 1 : format_ip4_mtrie_16 (u8 *s, va_list *va)
779 : {
780 1 : ip4_mtrie_16_t *m = va_arg (*va, ip4_mtrie_16_t *);
781 1 : int verbose = va_arg (*va, int);
782 : ip4_mtrie_16_ply_t *p;
783 1 : u32 base_address = 0;
784 : int i;
785 :
786 : s =
787 1 : format (s, "16-8-8: %d plies, memory usage %U\n", pool_elts (ip4_ply_pool),
788 : format_memory_size, ip4_mtrie_16_memory_usage (m));
789 1 : p = &m->root_ply;
790 :
791 1 : if (verbose)
792 : {
793 1 : s = format (s, "root-ply");
794 1 : p = &m->root_ply;
795 :
796 65537 : for (i = 0; i < ARRAY_LEN (p->leaves); i++)
797 : {
798 : u16 slot;
799 :
800 65536 : slot = clib_host_to_net_u16 (i);
801 :
802 65536 : if (p->dst_address_bits_of_leaves[slot] > 0)
803 : {
804 8450 : s = FORMAT_PLY (s, p, i, slot, base_address, 16, 0);
805 : }
806 : }
807 : }
808 :
809 1 : return s;
810 : }
811 :
812 : u8 *
813 0 : format_ip4_mtrie_8 (u8 *s, va_list *va)
814 : {
815 0 : ip4_mtrie_8_t *m = va_arg (*va, ip4_mtrie_8_t *);
816 0 : int verbose = va_arg (*va, int);
817 : ip4_mtrie_8_ply_t *root;
818 0 : u32 base_address = 0;
819 : u16 slot;
820 :
821 0 : root = pool_elt_at_index (ip4_ply_pool, m->root_ply);
822 :
823 0 : s = format (s, "8-8-8-8; %d plies, memory usage %U\n",
824 : pool_elts (ip4_ply_pool), format_memory_size,
825 : ip4_mtrie_8_memory_usage (m));
826 :
827 0 : if (verbose)
828 : {
829 0 : s = format (s, "root-ply");
830 :
831 0 : for (slot = 0; slot < ARRAY_LEN (root->leaves); slot++)
832 : {
833 0 : if (root->dst_address_bits_of_leaves[slot] > 0)
834 : {
835 0 : s = FORMAT_PLY (s, root, slot, slot, base_address, 8, 0);
836 : }
837 : }
838 : }
839 :
840 0 : return s;
841 : }
842 :
843 : /** Default heap size for the IPv4 mtries */
844 : #define IP4_FIB_DEFAULT_MTRIE_HEAP_SIZE (32<<20)
845 : #ifndef MAP_HUGE_SHIFT
846 : #define MAP_HUGE_SHIFT 26
847 : #endif
848 :
849 : static clib_error_t *
850 575 : ip4_mtrie_module_init (vlib_main_t * vm)
851 : {
852 : CLIB_UNUSED (ip4_mtrie_8_ply_t * p);
853 575 : clib_error_t *error = NULL;
854 :
855 : /* Burn one ply so index 0 is taken */
856 575 : pool_get (ip4_ply_pool, p);
857 :
858 575 : return (error);
859 : }
860 :
861 37439 : VLIB_INIT_FUNCTION (ip4_mtrie_module_init);
862 :
863 : /*
864 : * fd.io coding-style-patch-verification: ON
865 : *
866 : * Local Variables:
867 : * eval: (c-set-style "gnu")
868 : * End:
869 : */
|
