FD.io VPP  v17.04.2-2-ga8f93f8
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  uword prefix_len)
46 {
49  memset (p->dst_address_bits_of_leaves, prefix_len,
50  sizeof (p->dst_address_bits_of_leaves));
51 
52  /* Initialize leaves. */
53 #ifdef CLIB_HAVE_VEC128
54  {
55  u32x4 *l, init_x4;
56 
57 #ifndef __ALTIVEC__
58  init_x4 = u32x4_splat (init);
59 #else
60  {
61  u32x4_union_t y;
62  y.as_u32[0] = init;
63  y.as_u32[1] = init;
64  y.as_u32[2] = init;
65  y.as_u32[3] = init;
66  init_x4 = y.as_u32x4;
67  }
68 #endif
69 
70  for (l = p->leaves_as_u32x4;
71  l < p->leaves_as_u32x4 + ARRAY_LEN (p->leaves_as_u32x4); l += 4)
72  {
73  l[0] = init_x4;
74  l[1] = init_x4;
75  l[2] = init_x4;
76  l[3] = init_x4;
77  }
78  }
79 #else
80  {
81  u32 *l;
82 
83  for (l = p->leaves; l < p->leaves + ARRAY_LEN (p->leaves); l += 4)
84  {
85  l[0] = init;
86  l[1] = init;
87  l[2] = init;
88  l[3] = init;
89  }
90  }
91 #endif
92 }
93 
96  uword prefix_len)
97 {
99 
100  /* Get cache aligned ply. */
101  pool_get_aligned (m->ply_pool, p, sizeof (p[0]));
102 
103  ply_init (p, init_leaf, prefix_len);
105 }
106 
109 {
111  /* It better not be the root ply. */
112  ASSERT (n != 0);
113  return pool_elt_at_index (m->ply_pool, n);
114 }
115 
116 static void
118 {
119  uword i, is_root;
120 
121  is_root = p - m->ply_pool == 0;
122 
123  for (i = 0; i < ARRAY_LEN (p->leaves); i++)
124  {
125  ip4_fib_mtrie_leaf_t l = p->leaves[i];
127  ply_free (m, get_next_ply_for_leaf (m, l));
128  }
129 
130  if (is_root)
131  ply_init (p, IP4_FIB_MTRIE_LEAF_EMPTY, /* prefix_len */ 0);
132  else
133  pool_put (m->ply_pool, p);
134 }
135 
136 void
138 {
139  ip4_fib_mtrie_ply_t *root_ply = pool_elt_at_index (m->ply_pool, 0);
140  ply_free (m, root_ply);
141 }
142 
143 u32
145 {
148 
149  l = p->leaves[dst.as_u8[0]];
152 
153  p = get_next_ply_for_leaf (m, l);
154  l = p->leaves[dst.as_u8[1]];
157 
158  p = get_next_ply_for_leaf (m, l);
159  l = p->leaves[dst.as_u8[2]];
162 
163  p = get_next_ply_for_leaf (m, l);
164  l = p->leaves[dst.as_u8[3]];
165 
168 }
169 
170 typedef struct
171 {
176 
177 static void
179  ip4_fib_mtrie_ply_t * ply,
180  ip4_fib_mtrie_leaf_t new_leaf,
181  uword new_leaf_dst_address_bits)
182 {
183  ip4_fib_mtrie_leaf_t old_leaf;
184  uword i;
185 
187  ASSERT (!ip4_fib_mtrie_leaf_is_empty (new_leaf));
188 
189  for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
190  {
191  old_leaf = ply->leaves[i];
192 
193  /* Recurse into sub plies. */
194  if (!ip4_fib_mtrie_leaf_is_terminal (old_leaf))
195  {
196  ip4_fib_mtrie_ply_t *sub_ply = get_next_ply_for_leaf (m, old_leaf);
197  set_ply_with_more_specific_leaf (m, sub_ply, new_leaf,
198  new_leaf_dst_address_bits);
199  }
200 
201  /* Replace less specific terminal leaves with new leaf. */
202  else if (new_leaf_dst_address_bits >=
204  {
205  __sync_val_compare_and_swap (&ply->leaves[i], old_leaf, new_leaf);
206  ASSERT (ply->leaves[i] == new_leaf);
207  ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
209  }
210  }
211 }
212 
213 static void
216  u32 old_ply_index, u32 dst_address_byte_index)
217 {
218  ip4_fib_mtrie_leaf_t old_leaf, new_leaf;
219  i32 n_dst_bits_next_plies;
220  u8 dst_byte;
221 
222  ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
223  ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
224 
225  n_dst_bits_next_plies =
226  a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
227 
228  dst_byte = a->dst_address.as_u8[dst_address_byte_index];
229 
230  /* Number of bits next plies <= 0 => insert leaves this ply. */
231  if (n_dst_bits_next_plies <= 0)
232  {
233  uword i, n_dst_bits_this_ply, old_leaf_is_terminal;
234 
235  n_dst_bits_this_ply = -n_dst_bits_next_plies;
236  ASSERT ((a->dst_address.as_u8[dst_address_byte_index] &
237  pow2_mask (n_dst_bits_this_ply)) == 0);
238 
239  for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
240  {
241  ip4_fib_mtrie_ply_t *old_ply, *new_ply;
242 
243  old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
244 
245  old_leaf = old_ply->leaves[i];
246  old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
247 
248  /* Is leaf to be inserted more specific? */
249  if (a->dst_address_length >= old_ply->dst_address_bits_of_leaves[i])
250  {
252 
253  if (old_leaf_is_terminal)
254  {
255  old_ply->dst_address_bits_of_leaves[i] =
257  __sync_val_compare_and_swap (&old_ply->leaves[i], old_leaf,
258  new_leaf);
259  ASSERT (old_ply->leaves[i] == new_leaf);
260  old_ply->n_non_empty_leafs +=
261  ip4_fib_mtrie_leaf_is_empty (old_leaf);
262  ASSERT (old_ply->n_non_empty_leafs <=
263  ARRAY_LEN (old_ply->leaves));
264  }
265  else
266  {
267  /* Existing leaf points to another ply. We need to place new_leaf into all
268  more specific slots. */
269  new_ply = get_next_ply_for_leaf (m, old_leaf);
270  set_ply_with_more_specific_leaf (m, new_ply, new_leaf,
271  a->dst_address_length);
272  }
273  }
274 
275  else if (!old_leaf_is_terminal)
276  {
277  new_ply = get_next_ply_for_leaf (m, old_leaf);
278  set_leaf (m, a, new_ply - m->ply_pool,
279  dst_address_byte_index + 1);
280  }
281  }
282  }
283  else
284  {
285  ip4_fib_mtrie_ply_t *old_ply, *new_ply;
286 
287  old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
288  old_leaf = old_ply->leaves[dst_byte];
289  if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
290  {
291  new_leaf =
292  ply_create (m, old_leaf,
293  old_ply->dst_address_bits_of_leaves[dst_byte]);
294  new_ply = get_next_ply_for_leaf (m, new_leaf);
295 
296  /* Refetch since ply_create may move pool. */
297  old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
298 
299  __sync_val_compare_and_swap (&old_ply->leaves[dst_byte], old_leaf,
300  new_leaf);
301  ASSERT (old_ply->leaves[dst_byte] == new_leaf);
302  old_ply->dst_address_bits_of_leaves[dst_byte] = 0;
303 
304  old_ply->n_non_empty_leafs -=
306  ASSERT (old_ply->n_non_empty_leafs >= 0);
307 
308  /* Account for the ply we just created. */
309  old_ply->n_non_empty_leafs += 1;
310  }
311  else
312  new_ply = get_next_ply_for_leaf (m, old_leaf);
313 
314  set_leaf (m, a, new_ply - m->ply_pool, dst_address_byte_index + 1);
315  }
316 }
317 
318 static uword
321  ip4_fib_mtrie_ply_t * old_ply, u32 dst_address_byte_index)
322 {
323  ip4_fib_mtrie_leaf_t old_leaf, del_leaf;
324  i32 n_dst_bits_next_plies;
325  i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
326  u8 dst_byte;
327 
328  ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
329  ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
330 
331  n_dst_bits_next_plies =
332  a->dst_address_length - BITS (u8) * (dst_address_byte_index + 1);
333 
334  dst_byte = a->dst_address.as_u8[dst_address_byte_index];
335  if (n_dst_bits_next_plies < 0)
336  dst_byte &= ~pow2_mask (-n_dst_bits_next_plies);
337 
338  n_dst_bits_this_ply =
339  n_dst_bits_next_plies <= 0 ? -n_dst_bits_next_plies : 0;
340  n_dst_bits_this_ply = clib_min (8, n_dst_bits_this_ply);
341 
343 
344  for (i = dst_byte; i < dst_byte + (1 << n_dst_bits_this_ply); i++)
345  {
346  old_leaf = old_ply->leaves[i];
347  old_leaf_is_terminal = ip4_fib_mtrie_leaf_is_terminal (old_leaf);
348 
349  if (old_leaf == del_leaf
350  || (!old_leaf_is_terminal
351  && unset_leaf (m, a, get_next_ply_for_leaf (m, old_leaf),
352  dst_address_byte_index + 1)))
353  {
354  old_ply->leaves[i] = IP4_FIB_MTRIE_LEAF_EMPTY;
355  old_ply->dst_address_bits_of_leaves[i] = 0;
356 
357  /* No matter what we just deleted a non-empty leaf. */
358  ASSERT (!ip4_fib_mtrie_leaf_is_empty (old_leaf));
359  old_ply->n_non_empty_leafs -= 1;
360 
361  ASSERT (old_ply->n_non_empty_leafs >= 0);
362  if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
363  {
364  pool_put (m->ply_pool, old_ply);
365  /* Old ply was deleted. */
366  return 1;
367  }
368  }
369  }
370 
371  /* Old ply was not deleted. */
372  return 0;
373 }
374 
375 void
377 {
379  memset (m, 0, sizeof (m[0]));
381  root = ply_create (m, IP4_FIB_MTRIE_LEAF_EMPTY, /* dst_address_bits_of_leaves */
382  0);
384 }
385 
386 void
388  ip4_address_t dst_address,
389  u32 dst_address_length,
390  u32 adj_index, u32 is_del)
391 {
392  ip4_fib_mtrie_t *m = &fib->mtrie;
393  ip4_fib_mtrie_ply_t *root_ply;
395  ip4_main_t *im = &ip4_main;
396 
397  ASSERT (m->ply_pool != 0);
398 
399  root_ply = pool_elt_at_index (m->ply_pool, 0);
400 
401  /* Honor dst_address_length. Fib masks are in network byte order */
402  dst_address.as_u32 &= im->fib_masks[dst_address_length];
403  a.dst_address = dst_address;
404  a.dst_address_length = dst_address_length;
405  a.adj_index = adj_index;
406 
407  if (!is_del)
408  {
409  if (dst_address_length == 0)
411  else
412  set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
413  }
414  else
415  {
416  if (dst_address_length == 0)
418 
419  else
420  {
421  ip4_main_t *im = &ip4_main;
422  uword i;
423 
424  unset_leaf (m, &a, root_ply, 0);
425 
426  /* Find next less specific route and insert into mtrie. */
427  for (i = dst_address_length - 1; i >= 1; i--)
428  {
429  uword *p;
430  index_t lbi;
431  ip4_address_t key;
432 
433  if (!fib->fib_entry_by_dst_address[i])
434  continue;
435 
436  key.as_u32 = dst_address.as_u32 & im->fib_masks[i];
437  p = hash_get (fib->fib_entry_by_dst_address[i], key.as_u32);
438  if (p)
439  {
441  if (INDEX_INVALID == lbi)
442  continue;
443 
444  a.dst_address = key;
445  a.adj_index = lbi;
446  a.dst_address_length = i;
447 
448  set_leaf (m, &a, /* ply_index */ 0,
449  /* dst_address_byte_index */ 0);
450  break;
451  }
452  }
453  }
454  }
455 }
456 
457 /* Returns number of bytes of memory used by mtrie. */
458 static uword
460 {
461  uword bytes, i;
462 
463  if (!p)
464  {
465  if (pool_is_free_index (m->ply_pool, 0))
466  return 0;
467  p = pool_elt_at_index (m->ply_pool, 0);
468  }
469 
470  bytes = sizeof (p[0]);
471  for (i = 0; i < ARRAY_LEN (p->leaves); i++)
472  {
473  ip4_fib_mtrie_leaf_t l = p->leaves[i];
475  bytes += mtrie_memory_usage (m, get_next_ply_for_leaf (m, l));
476  }
477 
478  return bytes;
479 }
480 
481 static u8 *
482 format_ip4_fib_mtrie_leaf (u8 * s, va_list * va)
483 {
484  ip4_fib_mtrie_leaf_t l = va_arg (*va, ip4_fib_mtrie_leaf_t);
485 
487  s = format (s, "miss");
488  else if (ip4_fib_mtrie_leaf_is_terminal (l))
489  s = format (s, "adj %d", ip4_fib_mtrie_leaf_get_adj_index (l));
490  else
491  s = format (s, "next ply %d", ip4_fib_mtrie_leaf_get_next_ply_index (l));
492  return s;
493 }
494 
495 static u8 *
496 format_ip4_fib_mtrie_ply (u8 * s, va_list * va)
497 {
498  ip4_fib_mtrie_t *m = va_arg (*va, ip4_fib_mtrie_t *);
499  u32 base_address = va_arg (*va, u32);
500  u32 ply_index = va_arg (*va, u32);
501  u32 dst_address_byte_index = va_arg (*va, u32);
503  uword i, indent;
504 
505  p = pool_elt_at_index (m->ply_pool, ply_index);
506  indent = format_get_indent (s);
507  s =
508  format (s, "ply index %d, %d non-empty leaves", ply_index,
509  p->n_non_empty_leafs);
510  for (i = 0; i < ARRAY_LEN (p->leaves); i++)
511  {
512  ip4_fib_mtrie_leaf_t l = p->leaves[i];
513 
515  {
516  u32 a, ia_length;
517  ip4_address_t ia;
518 
519  a = base_address + (i << (24 - 8 * dst_address_byte_index));
520  ia.as_u32 = clib_host_to_net_u32 (a);
522  ia_length = p->dst_address_bits_of_leaves[i];
523  else
524  ia_length = 8 * (1 + dst_address_byte_index);
525  s = format (s, "\n%U%20U %U",
526  format_white_space, indent + 2,
527  format_ip4_address_and_length, &ia, ia_length,
529 
531  s = format (s, "\n%U%U",
532  format_white_space, indent + 2,
535  dst_address_byte_index + 1);
536  }
537  }
538 
539  return s;
540 }
541 
542 u8 *
543 format_ip4_fib_mtrie (u8 * s, va_list * va)
544 {
545  ip4_fib_mtrie_t *m = va_arg (*va, ip4_fib_mtrie_t *);
546 
547  s = format (s, "%d plies, memory usage %U",
548  pool_elts (m->ply_pool),
550 
551  if (pool_elts (m->ply_pool) > 0)
552  {
553  ip4_address_t base_address;
554  base_address.as_u32 = 0;
555  s =
556  format (s, "\n %U", format_ip4_fib_mtrie_ply, m, base_address, 0, 0);
557  }
558 
559  return s;
560 }
561 
562 /*
563  * fd.io coding-style-patch-verification: ON
564  *
565  * Local Variables:
566  * eval: (c-set-style "gnu")
567  * End:
568  */
u8 dst_address_bits_of_leaves[256]
Definition: ip4_mtrie.h:126
sll srl srl sll sra u16x4 i
Definition: vector_sse2.h:343
#define clib_min(x, y)
Definition: clib.h:332
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:98
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:108
static void ply_free(ip4_fib_mtrie_t *m, ip4_fib_mtrie_ply_t *p)
Definition: ip4_mtrie.c:117
const dpo_id_t * fib_entry_contribute_ip_forwarding(fib_node_index_t fib_entry_index)
Definition: fib_entry.c:432
static u32 ip4_fib_mtrie_leaf_is_next_ply(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:92
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
u8 * format(u8 *s, const char *fmt,...)
Definition: format.c:418
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:105
#define IP4_FIB_MTRIE_LEAF_EMPTY
Definition: ip4_mtrie.h:54
void ip4_fib_free(ip4_fib_mtrie_t *m)
Definition: ip4_mtrie.c:137
ip4_fib_mtrie_ply_t * ply_pool
Definition: ip4_mtrie.h:142
#define always_inline
Definition: clib.h:84
static uword pow2_mask(uword x)
Definition: clib.h:257
static uword format_get_indent(u8 *s)
Definition: format.h:72
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
u8 * format_memory_size(u8 *s, va_list *va)
Definition: std-formats.c:193
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:387
static u32 ip4_fib_mtrie_leaf_get_adj_index(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:76
void ip4_mtrie_init(ip4_fib_mtrie_t *m)
Definition: ip4_mtrie.c:376
#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:482
#define pool_elt_at_index(p, i)
Returns pointer to element at given index.
Definition: pool.h:397
uword * fib_entry_by_dst_address[33]
Definition: ip4.h:51
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 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:319
u8 * format_ip4_fib_mtrie(u8 *s, va_list *va)
Definition: ip4_mtrie.c:543
#define pool_put(P, E)
Free an object E in pool P.
Definition: pool.h:241
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:214
#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:178
Definition: ip4.h:48
static ip4_fib_mtrie_leaf_t ip4_fib_mtrie_leaf_set_adj_index(u32 adj_index)
Definition: ip4_mtrie.h:83
#define pool_is_free_index(P, I)
Use free bitmap to query whether given index is free.
Definition: pool.h:238
#define ARRAY_LEN(x)
Definition: clib.h:59
static void init(void)
Definition: pneum.c:76
static uword mtrie_memory_usage(ip4_fib_mtrie_t *m, ip4_fib_mtrie_ply_t *p)
Definition: ip4_mtrie.c:459
#define ASSERT(truth)
ip4_fib_mtrie_leaf_t leaves[256]
Definition: ip4_mtrie.h:118
unsigned int u32
Definition: types.h:88
IPv4 main type.
Definition: ip4.h:107
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:95
static u32 ip4_fib_mtrie_leaf_is_non_empty(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:64
u64 uword
Definition: types.h:112
#define u32x4_splat(i)
index_t dpoi_index
the index of objects of that type
Definition: dpo.h:162
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:58
#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:54
u32 ip4_mtrie_lookup_address(ip4_fib_mtrie_t *m, ip4_address_t dst)
Definition: ip4_mtrie.c:144
ip4_main_t ip4_main
Global ip4 main structure.
Definition: ip4_forward.c:1117
#define BITS(x)
Definition: clib.h:58
static u8 * format_ip4_fib_mtrie_ply(u8 *s, va_list *va)
Definition: ip4_mtrie.c:496
static u32 ip4_fib_mtrie_leaf_is_terminal(ip4_fib_mtrie_leaf_t n)
Definition: ip4_mtrie.h:70
format_function_t format_ip4_address_and_length
Definition: format.h:80
u32 fib_masks[33]
Definition: ip4.h:117
ip4_fib_mtrie_leaf_t default_leaf
Definition: ip4_mtrie.h:145
static uword pool_elts(void *v)
Number of active elements in a pool.
Definition: pool.h:109