FD.io VPP  v16.12-rc0-308-g931be3a
Vector Packet Processing
ip4_mtrie.c
Go to the documentation of this file.
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/fib/fib_entry.h>
42 
43 static void
45 {
47  memset (p->dst_address_bits_of_leaves, prefix_len, sizeof (p->dst_address_bits_of_leaves));
48 
49  /* Initialize leaves. */
50 #ifdef CLIB_HAVE_VEC128
51  {
52  u32x4 * l, init_x4;
53 
54 #ifndef __ALTIVEC__
55  init_x4 = u32x4_splat (init);
56 #else
57  {
58  u32x4_union_t y;
59  y.as_u32[0] = init;
60  y.as_u32[1] = init;
61  y.as_u32[2] = init;
62  y.as_u32[3] = init;
63  init_x4 = y.as_u32x4;
64  }
65 #endif
66 
67  for (l = p->leaves_as_u32x4; l < p->leaves_as_u32x4 + ARRAY_LEN (p->leaves_as_u32x4); l += 4)
68  {
69  l[0] = init_x4;
70  l[1] = init_x4;
71  l[2] = init_x4;
72  l[3] = init_x4;
73  }
74  }
75 #else
76  {
77  u32 * l;
78 
79  for (l = p->leaves; l < p->leaves + ARRAY_LEN (p->leaves); l += 4)
80  {
81  l[0] = init;
82  l[1] = init;
83  l[2] = init;
84  l[3] = init;
85  }
86  }
87 #endif
88 }
89 
92 {
94 
95  /* Get cache aligned ply. */
96  pool_get_aligned (m->ply_pool, p, sizeof (p[0]));
97 
98  ply_init (p, init_leaf, prefix_len);
100 }
101 
104 {
106  /* It better not be the root ply. */
107  ASSERT (n != 0);
108  return pool_elt_at_index (m->ply_pool, n);
109 }
110 
111 static void
113 {
114  uword i, is_root;
115 
116  is_root = p - m->ply_pool == 0;
117 
118  for (i = 0 ; i < ARRAY_LEN (p->leaves); i++)
119  {
120  ip4_fib_mtrie_leaf_t l = p->leaves[i];
122  ply_free (m, get_next_ply_for_leaf (m, l));
123  }
124 
125  if (is_root)
126  ply_init (p, IP4_FIB_MTRIE_LEAF_EMPTY, /* prefix_len */ 0);
127  else
128  pool_put (m->ply_pool, p);
129 }
130 
132 {
133  ip4_fib_mtrie_ply_t * root_ply = pool_elt_at_index (m->ply_pool, 0);
134  ply_free (m, root_ply);
135 }
136 
138 {
141 
142  l = p->leaves[dst.as_u8[0]];
145 
146  p = get_next_ply_for_leaf (m, l);
147  l = p->leaves[dst.as_u8[1]];
150 
151  p = get_next_ply_for_leaf (m, l);
152  l = p->leaves[dst.as_u8[2]];
155 
156  p = get_next_ply_for_leaf (m, l);
157  l = p->leaves[dst.as_u8[3]];
158 
161 }
162 
163 typedef struct {
168 
169 static void
171  ip4_fib_mtrie_ply_t * ply,
172  ip4_fib_mtrie_leaf_t new_leaf,
173  uword new_leaf_dst_address_bits)
174 {
175  ip4_fib_mtrie_leaf_t old_leaf;
176  uword i;
177 
179  ASSERT (! ip4_fib_mtrie_leaf_is_empty (new_leaf));
180 
181  for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
182  {
183  old_leaf = ply->leaves[i];
184 
185  /* Recurse into sub plies. */
186  if (! ip4_fib_mtrie_leaf_is_terminal (old_leaf))
187  {
188  ip4_fib_mtrie_ply_t * sub_ply = get_next_ply_for_leaf (m, old_leaf);
189  set_ply_with_more_specific_leaf (m, sub_ply, new_leaf, new_leaf_dst_address_bits);
190  }
191 
192  /* Replace less specific terminal leaves with new leaf. */
193  else if (new_leaf_dst_address_bits >= ply->dst_address_bits_of_leaves[i])
194  {
195  __sync_val_compare_and_swap (&ply->leaves[i], old_leaf, new_leaf);
196  ASSERT(ply->leaves[i] == new_leaf);
197  ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
199  }
200  }
201 }
202 
203 static void
206  u32 old_ply_index,
207  u32 dst_address_byte_index)
208 {
209  ip4_fib_mtrie_leaf_t old_leaf, new_leaf;
210  i32 n_dst_bits_next_plies;
211  u8 dst_byte;
212 
213  ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
214  ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
215 
216  n_dst_bits_next_plies = a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
217 
218  dst_byte = a->dst_address.as_u8[dst_address_byte_index];
219 
220  /* Number of bits next plies <= 0 => insert leaves this ply. */
221  if (n_dst_bits_next_plies <= 0)
222  {
223  uword i, n_dst_bits_this_ply, old_leaf_is_terminal;
224 
225  n_dst_bits_this_ply = -n_dst_bits_next_plies;
226  ASSERT ((a->dst_address.as_u8[dst_address_byte_index] & pow2_mask (n_dst_bits_this_ply)) == 0);
227 
228  for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
229  {
230  ip4_fib_mtrie_ply_t * old_ply, * new_ply;
231 
232  old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
233 
234  old_leaf = old_ply->leaves[i];
235  old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
236 
237  /* Is leaf to be inserted more specific? */
238  if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
239  {
241 
242  if (old_leaf_is_terminal)
243  {
245  __sync_val_compare_and_swap (&old_ply->leaves[i], old_leaf,
246  new_leaf);
247  ASSERT(old_ply->leaves[i] == new_leaf);
248  old_ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
249  ASSERT (old_ply->n_non_empty_leafs <= ARRAY_LEN (old_ply->leaves));
250  }
251  else
252  {
253  /* Existing leaf points to another ply. We need to place new_leaf into all
254  more specific slots. */
255  new_ply = get_next_ply_for_leaf (m, old_leaf);
256  set_ply_with_more_specific_leaf (m, new_ply, new_leaf, a->dst_address_length);
257  }
258  }
259 
260  else if (! old_leaf_is_terminal)
261  {
262  new_ply = get_next_ply_for_leaf (m, old_leaf);
263  set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
264  }
265  }
266  }
267  else
268  {
269  ip4_fib_mtrie_ply_t * old_ply, * new_ply;
270 
271  old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
272  old_leaf = old_ply->leaves[dst_byte];
273  if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
274  {
275  new_leaf = ply_create (m, old_leaf, old_ply->dst_address_bits_of_leaves[dst_byte]);
276  new_ply = get_next_ply_for_leaf (m, new_leaf);
277 
278  /* Refetch since ply_create may move pool. */
279  old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
280 
281  __sync_val_compare_and_swap (&old_ply->leaves[dst_byte], old_leaf,
282  new_leaf);
283  ASSERT(old_ply->leaves[dst_byte] == new_leaf);
284  old_ply->dst_address_bits_of_leaves[dst_byte] = 0;
285 
286  old_ply->n_non_empty_leafs -= ip4_fib_mtrie_leaf_is_non_empty (old_leaf);
287  ASSERT (old_ply->n_non_empty_leafs >= 0);
288 
289  /* Account for the ply we just created. */
290  old_ply->n_non_empty_leafs += 1;
291  }
292  else
293  new_ply = get_next_ply_for_leaf (m, old_leaf);
294 
295  set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
296  }
297 }
298 
299 static uword
302  ip4_fib_mtrie_ply_t * old_ply,
303  u32 dst_address_byte_index)
304 {
305  ip4_fib_mtrie_leaf_t old_leaf, del_leaf;
306  i32 n_dst_bits_next_plies;
307  i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
308  u8 dst_byte;
309 
310  ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
311  ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
312 
313  n_dst_bits_next_plies = a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
314 
315  dst_byte = a->dst_address.as_u8[dst_address_byte_index];
316  if (n_dst_bits_next_plies < 0)
317  dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
318 
319  n_dst_bits_this_ply = n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
320  n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
321 
323 
324  for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
325  {
326  old_leaf = old_ply->leaves[i];
327  old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
328 
329  if (old_leaf == del_leaf
330  || (! old_leaf_is_terminal
331  && unset_leaf (m, a, get_next_ply_for_leaf (m, old_leaf), dst_address_byte_index + 1)))
332  {
333  old_ply->leaves[i] = IP4_FIB_MTRIE_LEAF_EMPTY;
334  old_ply->dst_address_bits_of_leaves[i] = 0;
335 
336  /* No matter what we just deleted a non-empty leaf. */
337  ASSERT (! ip4_fib_mtrie_leaf_is_empty (old_leaf));
338  old_ply->n_non_empty_leafs -= 1;
339 
340  ASSERT (old_ply->n_non_empty_leafs >= 0);
341  if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
342  {
343  pool_put (m->ply_pool, old_ply);
344  /* Old ply was deleted. */
345  return 1;
346  }
347  }
348  }
349 
350  /* Old ply was not deleted. */
351  return 0;
352 }
353 
355 {
357  memset (m, 0, sizeof (m[0]));
359  root = ply_create (m, IP4_FIB_MTRIE_LEAF_EMPTY, /* dst_address_bits_of_leaves */ 0);
361 }
362 
363 void
365  ip4_address_t dst_address,
366  u32 dst_address_length,
367  u32 adj_index,
368  u32 is_del)
369 {
370  ip4_fib_mtrie_t * m = &fib->mtrie;
371  ip4_fib_mtrie_ply_t * root_ply;
373  ip4_main_t * im = &ip4_main;
374 
375  ASSERT(m->ply_pool != 0);
376 
377  root_ply = pool_elt_at_index (m->ply_pool, 0);
378 
379  /* Honor dst_address_length. Fib masks are in network byte order */
380  dst_address.as_u32 &= im->fib_masks[dst_address_length];
381  a.dst_address = dst_address;
382  a.dst_address_length = dst_address_length;
383  a.adj_index = adj_index;
384 
385  if (! is_del)
386  {
387  if (dst_address_length == 0)
389  else
390  set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
391  }
392  else
393  {
394  if (dst_address_length == 0)
396 
397  else
398  {
399  ip4_main_t * im = &ip4_main;
400  uword i;
401 
402  unset_leaf (m, &a, root_ply, 0);
403 
404  /* Find next less specific route and insert into mtrie. */
405  for (i = dst_address_length - 1; i >= 1; i--)
406  {
407  uword * p;
408  index_t lbi;
409  ip4_address_t key;
410 
411  if (! fib->fib_entry_by_dst_address[i])
412  continue;
413 
414  key.as_u32 = dst_address.as_u32 & im->fib_masks[i];
415  p = hash_get (fib->fib_entry_by_dst_address[i], key.as_u32);
416  if (p)
417  {
419  if (INDEX_INVALID == lbi)
420  continue;
421 
422  a.dst_address = key;
423  a.adj_index = lbi;
424  a.dst_address_length = i;
425 
426  set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
427  break;
428  }
429  }
430  }
431  }
432 }
433 
434 /* Returns number of bytes of memory used by mtrie. */
436 {
437  uword bytes, i;
438 
439  if (! p)
440  {
441  if (pool_is_free_index (m->ply_pool, 0))
442  return 0;
443  p = pool_elt_at_index (m->ply_pool, 0);
444  }
445 
446  bytes = sizeof (p[0]);
447  for (i = 0 ; i < ARRAY_LEN (p->leaves); i++)
448  {
449  ip4_fib_mtrie_leaf_t l = p->leaves[i];
451  bytes += mtrie_memory_usage (m, get_next_ply_for_leaf (m, l));
452  }
453 
454  return bytes;
455 }
456 
457 static u8 * format_ip4_fib_mtrie_leaf (u8 * s, va_list * va)
458 {
459  ip4_fib_mtrie_leaf_t l = va_arg (*va, ip4_fib_mtrie_leaf_t);
460 
462  s = format (s, "miss");
463  else if (ip4_fib_mtrie_leaf_is_terminal (l))
464  s = format (s, "adj %d", ip4_fib_mtrie_leaf_get_adj_index (l));
465  else
466  s = format (s, "next ply %d", ip4_fib_mtrie_leaf_get_next_ply_index (l));
467  return s;
468 }
469 
470 static u8 * format_ip4_fib_mtrie_ply (u8 * s, va_list * va)
471 {
472  ip4_fib_mtrie_t * m = va_arg (*va, ip4_fib_mtrie_t *);
473  u32 base_address = va_arg (*va, u32);
474  u32 ply_index = va_arg (*va, u32);
475  u32 dst_address_byte_index = va_arg (*va, u32);
477  uword i, indent;
478 
479  p = pool_elt_at_index (m->ply_pool, ply_index);
480  indent = format_get_indent (s);
481  s = format (s, "ply index %d, %d non-empty leaves", ply_index, p->n_non_empty_leafs);
482  for (i = 0; i < ARRAY_LEN (p->leaves); i++)
483  {
484  ip4_fib_mtrie_leaf_t l = p->leaves[i];
485 
486  if (! ip4_fib_mtrie_leaf_is_empty (l))
487  {
488  u32 a, ia_length;
489  ip4_address_t ia;
490 
491  a = base_address + (i << (24 - 8*dst_address_byte_index));
492  ia.as_u32 = clib_host_to_net_u32 (a);
494  ia_length = p->dst_address_bits_of_leaves[i];
495  else
496  ia_length = 8*(1 + dst_address_byte_index);
497  s = format (s, "\n%U%20U %U",
498  format_white_space, indent + 2,
499  format_ip4_address_and_length, &ia, ia_length,
501 
503  s = format (s, "\n%U%U",
504  format_white_space, indent + 2,
507  dst_address_byte_index + 1);
508  }
509  }
510 
511  return s;
512 }
513 
514 u8 * format_ip4_fib_mtrie (u8 * s, va_list * va)
515 {
516  ip4_fib_mtrie_t * m = va_arg (*va, ip4_fib_mtrie_t *);
517 
518  s = format (s, "%d plies, memory usage %U",
519  pool_elts (m->ply_pool),
521 
522  if (pool_elts (m->ply_pool) > 0)
523  {
524  ip4_address_t base_address;
525  base_address.as_u32 = 0;
526  s = format (s, "\n %U", format_ip4_fib_mtrie_ply, m, base_address, 0, 0);
527  }
528 
529  return s;
530 }
u8 dst_address_bits_of_leaves[256]
Definition: ip4_mtrie.h:108
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
#define clib_min(x, y)
Definition: clib.h:326
a
Definition: bitmap.h:516
static u32 ip4_fib_mtrie_leaf_get_next_ply_index(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:83
static ip4_fib_mtrie_ply_t * get_next_ply_for_leaf(ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t l)
Definition: ip4_mtrie.c:103
static void ply_free(ip4_fib_mtrie_t *m, ip4_fib_mtrie_ply_t *p)
Definition: ip4_mtrie.c:112
const dpo_id_t * fib_entry_contribute_ip_forwarding(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:515
static u32 ip4_fib_mtrie_leaf_is_next_ply(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:80
u32 index_t
A Data-Path Object is an object that represents actions that are applied to packets are they are swit...
Definition: dpo.h:41
add_epi add_epi sub_epi sub_epi adds_epu subs_epu i16x8 y
Definition: vector_sse2.h:299
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_next_ply_index(u32 i)
Definition: ip4_mtrie.h:89
#define IP4_FIB_MTRIE_LEAF_EMPTY
Definition: ip4_mtrie.h:54
void ip4_fib_free(ip4_fib_mtrie_t *m)
Definition: ip4_mtrie.c:131
ip4_fib_mtrie_ply_t * ply_pool
Definition: ip4_mtrie.h:123
#define always_inline
Definition: clib.h:84
static uword pow2_mask(uword x)
Definition: clib.h:251
u8 * format_white_space(u8 *s, va_list *va)
Definition: std-formats.c:113
unsigned long long u32x4
Definition: ixge.c:28
int i32
Definition: types.h:81
u32 ip4_fib_mtrie_leaf_t
Definition: ip4_mtrie.h:52
void ip4_fib_mtrie_add_del_route(ip4_fib_t *fib, ip4_address_t dst_address, u32 dst_address_length, u32 adj_index, u32 is_del)
Definition: ip4_mtrie.c:364
static u32 ip4_fib_mtrie_leaf_get_adj_index(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:66
void ip4_mtrie_init(ip4_fib_mtrie_t *m)
Definition: ip4_mtrie.c:354
#define hash_get(h, key)
Definition: hash.h:248
static u8 * format_ip4_fib_mtrie_leaf(u8 *s, va_list *va)
Definition: ip4_mtrie.c:457
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:369
uword * fib_entry_by_dst_address[33]
Definition: ip4.h:50
static void ply_init(ip4_fib_mtrie_ply_t *p, ip4_fib_mtrie_leaf_t init, uword prefix_len)
Definition: ip4_mtrie.c:44
static uword format_get_indent(u8 *s)
Definition: format.h:72
static uword unset_leaf(ip4_fib_mtrie_t *m, ip4_fib_mtrie_set_unset_leaf_args_t *a, ip4_fib_mtrie_ply_t *old_ply, u32 dst_address_byte_index)
Definition: ip4_mtrie.c:300
u8 * format_ip4_fib_mtrie(u8 *s, va_list *va)
Definition: ip4_mtrie.c:514
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:214
static void set_leaf(ip4_fib_mtrie_t *m, ip4_fib_mtrie_set_unset_leaf_args_t *a, u32 old_ply_index, u32 dst_address_byte_index)
Definition: ip4_mtrie.c:204
#define pool_get_aligned(P, E, A)
Allocate an object E from a pool P (general version).
Definition: pool.h:169
static void set_ply_with_more_specific_leaf(ip4_fib_mtrie_t *m, ip4_fib_mtrie_ply_t *ply, ip4_fib_mtrie_leaf_t new_leaf, uword new_leaf_dst_address_bits)
Definition: ip4_mtrie.c:170
Definition: ip4.h:48
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_adj_index(u32 adj_index)
Definition: ip4_mtrie.h:72
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:211
#define ARRAY_LEN(x)
Definition: clib.h:59
static uword mtrie_memory_usage(ip4_fib_mtrie_t *m, ip4_fib_mtrie_ply_t *p)
Definition: ip4_mtrie.c:435
u8 * format_memory_size(u8 *s, va_list *va)
Definition: std-formats.c:193
#define ASSERT(truth)
ip4_fib_mtrie_leaf_t leaves[256]
Definition: ip4_mtrie.h:100
unsigned int u32
Definition: types.h:88
IPv4 main type.
Definition: ip4.h:95
static ip4_fib_mtrie_leaf_t ply_create(ip4_fib_mtrie_t *m, ip4_fib_mtrie_leaf_t init_leaf, uword prefix_len)
Definition: ip4_mtrie.c:91
static u32 ip4_fib_mtrie_leaf_is_non_empty(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:60
u64 uword
Definition: types.h:112
#define u32x4_splat(i)
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:154
unsigned char u8
Definition: types.h:56
static u32 ip4_fib_mtrie_leaf_is_empty(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:57
#define INDEX_INVALID
Invalid index - used when no index is known blazoned capitals INVALID speak volumes where ~0 does not...
Definition: dpo.h:47
ip4_fib_mtrie_t mtrie
Definition: ip4.h:53
u32 ip4_mtrie_lookup_address(ip4_fib_mtrie_t *m, ip4_address_t dst)
Definition: ip4_mtrie.c:137
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:418
ip4_main_t ip4_main
Global ip4 main structure.
Definition: ip4_forward.c:1060
format_function_t format_ip4_address_and_length
Definition: format.h:79
#define BITS(x)
Definition: clib.h:58
static u8 * format_ip4_fib_mtrie_ply(u8 *s, va_list *va)
Definition: ip4_mtrie.c:470
static u32 ip4_fib_mtrie_leaf_is_terminal(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:63
u32 fib_masks[33]
Definition: ip4.h:101
ip4_fib_mtrie_leaf_t default_leaf
Definition: ip4_mtrie.h:126
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:109