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:
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 * ip/ip4_fib.h: ip4 mtrie fib
18 * Copyright (c) 2012 Eliot Dresselhaus
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:
28 * The above copyright notice and this permission notice shall be
29 * included in all copies or substantial portions of the Software.
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.
40 #include <vnet/ip/ip.h>
43 ply_init (ip4_fib_mtrie_ply_t * p, ip4_fib_mtrie_leaf_t init, uword prefix_len)
45 p->n_non_empty_leafs = ip4_fib_mtrie_leaf_is_empty (init) ? 0 : ARRAY_LEN (p->leaves);
46 memset (p->dst_address_bits_of_leaves, prefix_len, sizeof (p->dst_address_bits_of_leaves));
48 /* Initialize leaves. */
49 #ifdef CLIB_HAVE_VEC128
54 init_x4 = u32x4_splat (init);
66 for (l = p->leaves_as_u32x4; l < p->leaves_as_u32x4 + ARRAY_LEN (p->leaves_as_u32x4); l += 4)
78 for (l = p->leaves; l < p->leaves + ARRAY_LEN (p->leaves); l += 4)
89 static ip4_fib_mtrie_leaf_t
90 ply_create (ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t init_leaf, uword prefix_len)
92 ip4_fib_mtrie_ply_t * p;
94 /* Get cache aligned ply. */
95 pool_get_aligned (m->ply_pool, p, sizeof (p[0]));
97 ply_init (p, init_leaf, prefix_len);
98 return ip4_fib_mtrie_leaf_set_next_ply_index (p - m->ply_pool);
101 always_inline ip4_fib_mtrie_ply_t *
102 get_next_ply_for_leaf (ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t l)
104 uword n = ip4_fib_mtrie_leaf_get_next_ply_index (l);
105 /* It better not be the root ply. */
107 return pool_elt_at_index (m->ply_pool, n);
111 ply_free (ip4_fib_mtrie_t * m, ip4_fib_mtrie_ply_t * p)
115 is_root = p - m->ply_pool == 0;
117 for (i = 0 ; i < ARRAY_LEN (p->leaves); i++)
119 ip4_fib_mtrie_leaf_t l = p->leaves[i];
120 if (ip4_fib_mtrie_leaf_is_next_ply (l))
121 ply_free (m, get_next_ply_for_leaf (m, l));
125 ply_init (p, IP4_FIB_MTRIE_LEAF_EMPTY, /* prefix_len */ 0);
127 pool_put (m->ply_pool, p);
130 void ip4_fib_free (ip4_fib_mtrie_t * m)
132 ip4_fib_mtrie_ply_t * root_ply = pool_elt_at_index (m->ply_pool, 0);
133 ply_free (m, root_ply);
136 u32 ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst)
138 ip4_fib_mtrie_ply_t * p = pool_elt_at_index (m->ply_pool, 0);
139 ip4_fib_mtrie_leaf_t l;
141 l = p->leaves[dst.as_u8[0]];
142 if (ip4_fib_mtrie_leaf_is_terminal (l))
143 return ip4_fib_mtrie_leaf_get_adj_index (l);
145 p = get_next_ply_for_leaf (m, l);
146 l = p->leaves[dst.as_u8[1]];
147 if (ip4_fib_mtrie_leaf_is_terminal (l))
148 return ip4_fib_mtrie_leaf_get_adj_index (l);
150 p = get_next_ply_for_leaf (m, l);
151 l = p->leaves[dst.as_u8[2]];
152 if (ip4_fib_mtrie_leaf_is_terminal (l))
153 return ip4_fib_mtrie_leaf_get_adj_index (l);
155 p = get_next_ply_for_leaf (m, l);
156 l = p->leaves[dst.as_u8[3]];
158 ASSERT (ip4_fib_mtrie_leaf_is_terminal (l));
159 return ip4_fib_mtrie_leaf_get_adj_index (l);
163 ip4_address_t dst_address;
164 u32 dst_address_length;
166 } ip4_fib_mtrie_set_unset_leaf_args_t;
169 set_ply_with_more_specific_leaf (ip4_fib_mtrie_t * m,
170 ip4_fib_mtrie_ply_t * ply,
171 ip4_fib_mtrie_leaf_t new_leaf,
172 uword new_leaf_dst_address_bits)
174 ip4_fib_mtrie_leaf_t old_leaf;
177 ASSERT (ip4_fib_mtrie_leaf_is_terminal (new_leaf));
178 ASSERT (! ip4_fib_mtrie_leaf_is_empty (new_leaf));
180 for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
182 old_leaf = ply->leaves[i];
184 /* Recurse into sub plies. */
185 if (! ip4_fib_mtrie_leaf_is_terminal (old_leaf))
187 ip4_fib_mtrie_ply_t * sub_ply = get_next_ply_for_leaf (m, old_leaf);
188 set_ply_with_more_specific_leaf (m, sub_ply, new_leaf, new_leaf_dst_address_bits);
191 /* Replace less specific terminal leaves with new leaf. */
192 else if (new_leaf_dst_address_bits >= ply->dst_address_bits_of_leaves[i])
194 __sync_val_compare_and_swap (&ply->leaves[i], old_leaf, new_leaf);
195 ASSERT(ply->leaves[i] == new_leaf);
196 ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
197 ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
203 set_leaf (ip4_fib_mtrie_t * m,
204 ip4_fib_mtrie_set_unset_leaf_args_t * a,
206 u32 dst_address_byte_index)
208 ip4_fib_mtrie_leaf_t old_leaf, new_leaf;
209 i32 n_dst_bits_next_plies;
212 ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
213 ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
215 n_dst_bits_next_plies = a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
217 dst_byte = a->dst_address.as_u8[dst_address_byte_index];
219 /* Number of bits next plies <= 0 => insert leaves this ply. */
220 if (n_dst_bits_next_plies <= 0)
222 uword i, n_dst_bits_this_ply, old_leaf_is_terminal;
224 n_dst_bits_this_ply = -n_dst_bits_next_plies;
225 ASSERT ((a->dst_address.as_u8[dst_address_byte_index] & pow2_mask (n_dst_bits_this_ply)) == 0);
227 for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
229 ip4_fib_mtrie_ply_t * old_ply, * new_ply;
231 old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
233 old_leaf = old_ply->leaves[i];
234 old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
236 /* Is leaf to be inserted more specific? */
237 if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
239 new_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
241 if (old_leaf_is_terminal)
243 old_ply->dst_address_bits_of_leaves[i] = a->dst_address_length;
244 __sync_val_compare_and_swap (&old_ply->leaves[i], old_leaf,
246 ASSERT(old_ply->leaves[i] == new_leaf);
247 old_ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
248 ASSERT (old_ply->n_non_empty_leafs <= ARRAY_LEN (old_ply->leaves));
252 /* Existing leaf points to another ply. We need to place new_leaf into all
253 more specific slots. */
254 new_ply = get_next_ply_for_leaf (m, old_leaf);
255 set_ply_with_more_specific_leaf (m, new_ply, new_leaf, a->dst_address_length);
259 else if (! old_leaf_is_terminal)
261 new_ply = get_next_ply_for_leaf (m, old_leaf);
262 set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
268 ip4_fib_mtrie_ply_t * old_ply, * new_ply;
270 old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
271 old_leaf = old_ply->leaves[dst_byte];
272 if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
274 new_leaf = ply_create (m, old_leaf, old_ply->dst_address_bits_of_leaves[dst_byte]);
275 new_ply = get_next_ply_for_leaf (m, new_leaf);
277 /* Refetch since ply_create may move pool. */
278 old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
280 __sync_val_compare_and_swap (&old_ply->leaves[dst_byte], old_leaf,
282 ASSERT(old_ply->leaves[dst_byte] == new_leaf);
283 old_ply->dst_address_bits_of_leaves[dst_byte] = 0;
285 old_ply->n_non_empty_leafs -= ip4_fib_mtrie_leaf_is_non_empty (old_leaf);
286 ASSERT (old_ply->n_non_empty_leafs >= 0);
288 /* Account for the ply we just created. */
289 old_ply->n_non_empty_leafs += 1;
292 new_ply = get_next_ply_for_leaf (m, old_leaf);
294 set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
299 unset_leaf (ip4_fib_mtrie_t * m,
300 ip4_fib_mtrie_set_unset_leaf_args_t * a,
301 ip4_fib_mtrie_ply_t * old_ply,
302 u32 dst_address_byte_index)
304 ip4_fib_mtrie_leaf_t old_leaf, del_leaf;
305 i32 n_dst_bits_next_plies;
306 uword i, n_dst_bits_this_ply, old_leaf_is_terminal;
309 ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
310 ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
312 n_dst_bits_next_plies = a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
314 dst_byte = a->dst_address.as_u8[dst_address_byte_index];
315 if (n_dst_bits_next_plies < 0)
316 dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
318 n_dst_bits_this_ply = n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
319 n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
321 del_leaf = ip4_fib_mtrie_leaf_set_adj_index (a->adj_index);
323 for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
325 old_leaf = old_ply->leaves[i];
326 old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
328 if (old_leaf == del_leaf
329 || (! old_leaf_is_terminal
330 && unset_leaf (m, a, get_next_ply_for_leaf (m, old_leaf), dst_address_byte_index + 1)))
332 old_ply->leaves[i] = IP4_FIB_MTRIE_LEAF_EMPTY;
333 old_ply->dst_address_bits_of_leaves[i] = 0;
335 /* No matter what we just deleted a non-empty leaf. */
336 ASSERT (! ip4_fib_mtrie_leaf_is_empty (old_leaf));
337 old_ply->n_non_empty_leafs -= 1;
339 ASSERT (old_ply->n_non_empty_leafs >= 0);
340 if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
342 pool_put (m->ply_pool, old_ply);
343 /* Old ply was deleted. */
349 /* Old ply was not deleted. */
353 void ip4_mtrie_init (ip4_fib_mtrie_t * m)
355 ip4_fib_mtrie_leaf_t root;
356 memset (m, 0, sizeof (m[0]));
357 m->default_leaf = IP4_FIB_MTRIE_LEAF_EMPTY;
358 root = ply_create (m, IP4_FIB_MTRIE_LEAF_EMPTY, /* dst_address_bits_of_leaves */ 0);
359 ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (root) == 0);
363 ip4_fib_mtrie_add_del_route (ip4_fib_t * fib,
364 ip4_address_t dst_address,
365 u32 dst_address_length,
369 ip4_fib_mtrie_t * m = &fib->mtrie;
370 ip4_fib_mtrie_ply_t * root_ply;
371 ip4_fib_mtrie_set_unset_leaf_args_t a;
372 ip4_main_t * im = &ip4_main;
374 ASSERT(m->ply_pool != 0);
376 root_ply = pool_elt_at_index (m->ply_pool, 0);
378 /* Honor dst_address_length. Fib masks are in network byte order */
379 dst_address.as_u32 &= im->fib_masks[dst_address_length];
380 a.dst_address = dst_address;
381 a.dst_address_length = dst_address_length;
382 a.adj_index = adj_index;
386 if (dst_address_length == 0)
387 m->default_leaf = ip4_fib_mtrie_leaf_set_adj_index (adj_index);
389 set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
393 if (dst_address_length == 0)
394 m->default_leaf = IP4_FIB_MTRIE_LEAF_EMPTY;
398 ip4_main_t * im = &ip4_main;
401 unset_leaf (m, &a, root_ply, 0);
403 /* Find next less specific route and insert into mtrie. */
404 for (i = ARRAY_LEN (fib->adj_index_by_dst_address) - 1; i >= 1; i--)
409 if (! fib->adj_index_by_dst_address[i])
412 key.as_u32 = dst_address.as_u32 & im->fib_masks[i];
413 p = hash_get (fib->adj_index_by_dst_address[i], key.as_u32);
417 a.dst_address_length = i;
419 set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
428 maybe_remap_leaf (ip_lookup_main_t * lm, ip4_fib_mtrie_leaf_t * p)
430 ip4_fib_mtrie_leaf_t l = p[0];
431 uword was_remapped_to_empty_leaf = 0;
432 if (ip4_fib_mtrie_leaf_is_terminal (l))
434 u32 adj_index = ip4_fib_mtrie_leaf_get_adj_index (l);
435 u32 m = vec_elt (lm->adjacency_remap_table, adj_index);
438 was_remapped_to_empty_leaf = m == ~0;
439 if (was_remapped_to_empty_leaf)
440 p[0] = (was_remapped_to_empty_leaf
441 ? IP4_FIB_MTRIE_LEAF_EMPTY
442 : ip4_fib_mtrie_leaf_set_adj_index (m - 1));
445 return was_remapped_to_empty_leaf;
448 static void maybe_remap_ply (ip_lookup_main_t * lm, ip4_fib_mtrie_ply_t * ply)
450 u32 n_remapped_to_empty = 0;
452 for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
453 n_remapped_to_empty += maybe_remap_leaf (lm, &ply->leaves[i]);
454 if (n_remapped_to_empty > 0)
456 ASSERT (n_remapped_to_empty <= ply->n_non_empty_leafs);
457 ply->n_non_empty_leafs -= n_remapped_to_empty;
458 if (ply->n_non_empty_leafs == 0)
463 void ip4_mtrie_maybe_remap_adjacencies (ip_lookup_main_t * lm, ip4_fib_mtrie_t * m)
465 ip4_fib_mtrie_ply_t * ply;
466 pool_foreach (ply, m->ply_pool, maybe_remap_ply (lm, ply));
467 maybe_remap_leaf (lm, &m->default_leaf);
470 /* Returns number of bytes of memory used by mtrie. */
471 static uword mtrie_memory_usage (ip4_fib_mtrie_t * m, ip4_fib_mtrie_ply_t * p)
477 if (pool_is_free_index (m->ply_pool, 0))
479 p = pool_elt_at_index (m->ply_pool, 0);
482 bytes = sizeof (p[0]);
483 for (i = 0 ; i < ARRAY_LEN (p->leaves); i++)
485 ip4_fib_mtrie_leaf_t l = p->leaves[i];
486 if (ip4_fib_mtrie_leaf_is_next_ply (l))
487 bytes += mtrie_memory_usage (m, get_next_ply_for_leaf (m, l));
493 static u8 * format_ip4_fib_mtrie_leaf (u8 * s, va_list * va)
495 ip4_fib_mtrie_leaf_t l = va_arg (*va, ip4_fib_mtrie_leaf_t);
497 if (ip4_fib_mtrie_leaf_is_empty (l))
498 s = format (s, "miss");
499 else if (ip4_fib_mtrie_leaf_is_terminal (l))
500 s = format (s, "adj %d", ip4_fib_mtrie_leaf_get_adj_index (l));
502 s = format (s, "next ply %d", ip4_fib_mtrie_leaf_get_next_ply_index (l));
506 static u8 * format_ip4_fib_mtrie_ply (u8 * s, va_list * va)
508 ip4_fib_mtrie_t * m = va_arg (*va, ip4_fib_mtrie_t *);
509 u32 base_address = va_arg (*va, u32);
510 u32 ply_index = va_arg (*va, u32);
511 u32 dst_address_byte_index = va_arg (*va, u32);
512 ip4_fib_mtrie_ply_t * p;
515 p = pool_elt_at_index (m->ply_pool, ply_index);
516 indent = format_get_indent (s);
517 s = format (s, "ply index %d, %d non-empty leaves", ply_index, p->n_non_empty_leafs);
518 for (i = 0; i < ARRAY_LEN (p->leaves); i++)
520 ip4_fib_mtrie_leaf_t l = p->leaves[i];
522 if (! ip4_fib_mtrie_leaf_is_empty (l))
527 a = base_address + (i << (24 - 8*dst_address_byte_index));
528 ia.as_u32 = clib_host_to_net_u32 (a);
529 if (ip4_fib_mtrie_leaf_is_terminal (l))
530 ia_length = p->dst_address_bits_of_leaves[i];
532 ia_length = 8*(1 + dst_address_byte_index);
533 s = format (s, "\n%U%20U %U",
534 format_white_space, indent + 2,
535 format_ip4_address_and_length, &ia, ia_length,
536 format_ip4_fib_mtrie_leaf, l);
538 if (ip4_fib_mtrie_leaf_is_next_ply (l))
539 s = format (s, "\n%U%U",
540 format_white_space, indent + 2,
541 format_ip4_fib_mtrie_ply, m, a,
542 ip4_fib_mtrie_leaf_get_next_ply_index (l),
543 dst_address_byte_index + 1);
550 u8 * format_ip4_fib_mtrie (u8 * s, va_list * va)
552 ip4_fib_mtrie_t * m = va_arg (*va, ip4_fib_mtrie_t *);
554 s = format (s, "%d plies, memory usage %U",
555 pool_elts (m->ply_pool),
556 format_memory_size, mtrie_memory_usage (m, 0));
558 if (pool_elts (m->ply_pool) > 0)
560 ip4_address_t base_address;
561 base_address.as_u32 = 0;
562 s = format (s, "\n %U", format_ip4_fib_mtrie_ply, m, base_address, 0, 0);