1 - make the default route non-special, i.e. like any other less specific route. Consequently, all buckets have a valid valid index of either a leaf or a ply. Checks for special indeices in the data-path can thus be removed.
2 - since all leaves are now 'real' i.e. they represent a real load-balance object, to tell if a ply slot is 'empty' requeirs chekcing that the prefix length of the leaf occupying the slot is slot than the minium value for that ply.
3 - when removing a leaf find the cover first, then recurse down the ply and replace the old leaf with the cover. This saves us a ply walk.
Change-Id: Idd523019e8bb1b6ef527b1f5279a5e24bcf18332
Signed-off-by: Neale Ranns <nranns@cisco.com>
#include <vnet/adj/adj_mcast.h>
#include <vnet/fib/fib_node_list.h>
-/*
- * Special Adj with index zero. we need to define this since the v4 mtrie
- * assumes an index of 0 implies the ply is empty. therefore all 'real'
- * adjs need a non-zero index.
- */
-static ip_adjacency_t *special_v4_miss_adj_with_index_zero;
-
/* Adjacency packet/byte counters indexed by adjacency index. */
vlib_combined_counter_main_t adjacency_counters;
adj_midchain_module_init();
adj_mcast_module_init();
- /*
- * one special adj to reserve index 0
- */
- special_v4_miss_adj_with_index_zero = adj_alloc(FIB_PROTOCOL_IP4);
-
return (NULL);
}
adj_index0 = vnet_buffer (p0)->ip.adj_index[VLIB_TX];
- /* We should never rewrite a pkt using the MISS adjacency */
- ASSERT(adj_index0);
-
adj0 = adj_get (adj_index0);
/* Guess we are only writing on simple Ethernet header. */
mtrie0 = &ip4_fib_get (c0->fib_index)->mtrie;
- leaf0 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0,
- &ip0->src_address, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, &ip0->src_address);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0,
&ip0->src_address, 1);
sizeof (c1[0]));
mtrie1 = &ip4_fib_get (c1->fib_index)->mtrie;
- leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1,
- &ip1->src_address, 0);
+ leaf1 = ip4_fib_mtrie_lookup_step_one (mtrie1, &ip1->src_address);
leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1,
&ip1->src_address, 1);
mtrie0 = &ip4_fib_get (c0->fib_index)->mtrie;
- leaf0 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0,
- &ip0->src_address, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, &ip0->src_address);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0,
&ip0->src_address, 1);
{
dpo_register(DPO_LOAD_BALANCE, &lb_vft, load_balance_nodes);
+ /*
+ * Special LB with index zero. we need to define this since the v4 mtrie
+ * assumes an index of 0 implies the ply is empty. therefore all 'real'
+ * adjs need a non-zero index.
+ */
+ load_balance_create(0, DPO_PROTO_IP4, 0);
+
load_balance_map_module_init();
}
const ip4_address_t * addr0,
u32 * src_adj_index0)
{
- ip4_fib_mtrie_leaf_t leaf0, leaf1;
+ ip4_fib_mtrie_leaf_t leaf0;
ip4_fib_mtrie_t * mtrie0;
mtrie0 = &ip4_fib_get (src_fib_index0)->mtrie;
- leaf0 = leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
- leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, addr0);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 1);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 2);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 3);
- /* Handle default route. */
- leaf0 = (leaf0 == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
src_adj_index0[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
}
mtrie0 = &ip4_fib_get (src_fib_index0)->mtrie;
mtrie1 = &ip4_fib_get (src_fib_index1)->mtrie;
- leaf0 = leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 0);
- leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, addr0);
+ leaf1 = ip4_fib_mtrie_lookup_step_one (mtrie1, addr1);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 1);
leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 1);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, addr0, 3);
leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, addr1, 3);
- /* Handle default route. */
- leaf0 = (leaf0 == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
- leaf1 = (leaf1 == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie1->default_leaf : leaf1);
src_adj_index0[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
src_adj_index1[0] = ip4_fib_mtrie_leaf_get_adj_index (leaf1);
}
/*
* remove all the specials we added when the table was created.
+ * In reverse order so the default route is last.
*/
- for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++)
+ for (ii = ARRAY_LEN(ip4_specials) - 1; ii >= 0; ii--)
{
fib_prefix_t prefix = ip4_specials[ii].ift_prefix;
mtrie = &ip4_fib_get(fib_index)->mtrie;
- leaf = IP4_FIB_MTRIE_LEAF_ROOT;
- leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 0);
+ leaf = ip4_fib_mtrie_lookup_step_one (mtrie, addr);
leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 1);
leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 2);
leaf = ip4_fib_mtrie_lookup_step (mtrie, leaf, addr, 3);
- /* Handle default route. */
- leaf = (leaf == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie->default_leaf : leaf);
-
return (ip4_fib_mtrie_leaf_get_adj_index(leaf));
}
mtrie2 = &ip4_fib_get (fib_index2)->mtrie;
mtrie3 = &ip4_fib_get (fib_index3)->mtrie;
- leaf0 = leaf1 = leaf2 = leaf3 = IP4_FIB_MTRIE_LEAF_ROOT;
- leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, dst_addr0, 0);
- leaf1 = ip4_fib_mtrie_lookup_step (mtrie1, leaf1, dst_addr1, 0);
- leaf2 = ip4_fib_mtrie_lookup_step (mtrie2, leaf2, dst_addr2, 0);
- leaf3 = ip4_fib_mtrie_lookup_step (mtrie3, leaf3, dst_addr3, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, dst_addr0);
+ leaf1 = ip4_fib_mtrie_lookup_step_one (mtrie1, dst_addr1);
+ leaf2 = ip4_fib_mtrie_lookup_step_one (mtrie2, dst_addr2);
+ leaf3 = ip4_fib_mtrie_lookup_step_one (mtrie3, dst_addr3);
}
tcp0 = (void *) (ip0 + 1);
}
else
{
- /* Handle default route. */
- leaf0 =
- (leaf0 ==
- IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
- leaf1 =
- (leaf1 ==
- IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie1->default_leaf : leaf1);
- leaf2 =
- (leaf2 ==
- IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie2->default_leaf : leaf2);
- leaf3 =
- (leaf3 ==
- IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie3->default_leaf : leaf3);
lb_index0 = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
lb_index1 = ip4_fib_mtrie_leaf_get_adj_index (leaf1);
lb_index2 = ip4_fib_mtrie_leaf_get_adj_index (leaf2);
lb_index3 = ip4_fib_mtrie_leaf_get_adj_index (leaf3);
}
+ ASSERT (lb_index0 && lb_index1 && lb_index2 && lb_index3);
lb0 = load_balance_get (lb_index0);
lb1 = load_balance_get (lb_index1);
lb2 = load_balance_get (lb_index2);
{
mtrie0 = &ip4_fib_get (fib_index0)->mtrie;
- leaf0 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, dst_addr0, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, dst_addr0);
}
tcp0 = (void *) (ip0 + 1);
else
{
/* Handle default route. */
- leaf0 =
- (leaf0 ==
- IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
lbi0 = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
}
+ ASSERT (lbi0);
lb0 = load_balance_get (lbi0);
/* Use flow hash to compute multipath adjacency. */
mtrie0 = &ip4_fib_get (fib_index0)->mtrie;
mtrie1 = &ip4_fib_get (fib_index1)->mtrie;
- leaf0 = leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf0 =
- ip4_fib_mtrie_lookup_step (mtrie0, leaf0, &ip0->src_address, 0);
- leaf1 =
- ip4_fib_mtrie_lookup_step (mtrie1, leaf1, &ip1->src_address, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, &ip0->src_address);
+ leaf1 = ip4_fib_mtrie_lookup_step_one (mtrie1, &ip1->src_address);
/* Treat IP frag packets as "experimental" protocol for now
until support of IP frag reassembly is implemented */
ip4_fib_mtrie_lookup_step (mtrie0, leaf0, &ip0->src_address, 3);
leaf1 =
ip4_fib_mtrie_lookup_step (mtrie1, leaf1, &ip1->src_address, 3);
- leaf0 =
- (leaf0 ==
- IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
- leaf1 =
- (leaf1 ==
- IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie1->default_leaf : leaf1);
vnet_buffer (p0)->ip.adj_index[VLIB_RX] = lbi0 =
ip4_fib_mtrie_leaf_get_adj_index (leaf0);
mtrie0 = &ip4_fib_get (fib_index0)->mtrie;
- leaf0 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf0 =
- ip4_fib_mtrie_lookup_step (mtrie0, leaf0, &ip0->src_address, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, &ip0->src_address);
/* Treat IP frag packets as "experimental" protocol for now
until support of IP frag reassembly is implemented */
leaf0 =
ip4_fib_mtrie_lookup_step (mtrie0, leaf0, &ip0->src_address, 3);
- leaf0 =
- (leaf0 ==
- IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
lbi0 = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
vnet_buffer (p0)->ip.adj_index[VLIB_TX] = lbi0;
cpu_index, adj_index1);
}
- /* We should never rewrite a pkt using the MISS adjacency */
- ASSERT (adj_index0 && adj_index1);
-
ip0 = vlib_buffer_get_current (p0);
ip1 = vlib_buffer_get_current (p1);
adj_index0 = vnet_buffer (p0)->ip.adj_index[VLIB_TX];
- /* We should never rewrite a pkt using the MISS adjacency */
- ASSERT (adj_index0);
-
adj0 = ip_get_adjacency (lm, adj_index0);
ip0 = vlib_buffer_get_current (p0);
mtrie0 = &ip4_fib_get (fib_index0)->mtrie;
- leaf0 = IP4_FIB_MTRIE_LEAF_ROOT;
- leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, a, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, a);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, a, 1);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, a, 2);
leaf0 = ip4_fib_mtrie_lookup_step (mtrie0, leaf0, a, 3);
- /* Handle default route. */
- leaf0 = (leaf0 == IP4_FIB_MTRIE_LEAF_EMPTY ? mtrie0->default_leaf : leaf0);
-
lbi0 = ip4_fib_mtrie_leaf_get_adj_index (leaf0);
return lbi0 == ip4_fib_table_lookup_lb (ip4_fib_get (fib_index0), a);
#include <vnet/ip/ip.h>
#include <vnet/fib/fib_entry.h>
+always_inline u32
+ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_ply_t * p, u8 dst_byte)
+{
+ /*
+ * It's 'non-empty' if the length of the leaf stored is greater than the
+ * length of a leaf in the covering ply. i.e. the leaf is more specific
+ * than it's would be cover in the covering ply
+ */
+ if (p->dst_address_bits_of_leaves[dst_byte] > p->dst_address_bits_base)
+ return (1);
+ return (0);
+}
+
+always_inline ip4_fib_mtrie_leaf_t
+ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index)
+{
+ ip4_fib_mtrie_leaf_t l;
+ l = 1 + 2 * adj_index;
+ ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index);
+ return l;
+}
+
+always_inline u32
+ip4_fib_mtrie_leaf_is_next_ply (ip4_fib_mtrie_leaf_t n)
+{
+ return (n & 1) == 0;
+}
+
+always_inline u32
+ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n)
+{
+ ASSERT (ip4_fib_mtrie_leaf_is_next_ply (n));
+ return n >> 1;
+}
+
+always_inline ip4_fib_mtrie_leaf_t
+ip4_fib_mtrie_leaf_set_next_ply_index (u32 i)
+{
+ ip4_fib_mtrie_leaf_t l;
+ l = 0 + 2 * i;
+ ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (l) == i);
+ return l;
+}
+
static void
-ply_init (ip4_fib_mtrie_ply_t * p, ip4_fib_mtrie_leaf_t init,
- uword prefix_len)
+ply_init (ip4_fib_mtrie_ply_t * p,
+ ip4_fib_mtrie_leaf_t init, u32 prefix_len, u32 ply_base_len)
{
- p->n_non_empty_leafs =
- ip4_fib_mtrie_leaf_is_empty (init) ? 0 : ARRAY_LEN (p->leaves);
+ /*
+ * A leaf is 'empty' if it represents a leaf from the covering PLY
+ * i.e. if the prefix length of the leaf is less than or equal to
+ * the prefix length of the PLY
+ */
+ p->n_non_empty_leafs = (prefix_len > ply_base_len ?
+ ARRAY_LEN (p->leaves) : 0);
memset (p->dst_address_bits_of_leaves, prefix_len,
sizeof (p->dst_address_bits_of_leaves));
+ p->dst_address_bits_base = ply_base_len;
/* Initialize leaves. */
#ifdef CLIB_HAVE_VEC128
}
static ip4_fib_mtrie_leaf_t
-ply_create (ip4_fib_mtrie_t * m, ip4_fib_mtrie_leaf_t init_leaf,
- uword prefix_len)
+ply_create (ip4_fib_mtrie_t * m,
+ ip4_fib_mtrie_leaf_t init_leaf,
+ u32 leaf_prefix_len, u32 ply_base_len)
{
ip4_fib_mtrie_ply_t *p;
/* Get cache aligned ply. */
pool_get_aligned (m->ply_pool, p, sizeof (p[0]));
- ply_init (p, init_leaf, prefix_len);
+ ply_init (p, init_leaf, leaf_prefix_len, ply_base_len);
return ip4_fib_mtrie_leaf_set_next_ply_index (p - m->ply_pool);
}
}
if (is_root)
- ply_init (p, IP4_FIB_MTRIE_LEAF_EMPTY, /* prefix_len */ 0);
+ ply_init (p, IP4_FIB_MTRIE_LEAF_EMPTY, /* prefix_len */ 0, 0);
else
pool_put (m->ply_pool, p);
}
ply_free (m, root_ply);
}
-u32
-ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst)
-{
- ip4_fib_mtrie_ply_t *p = pool_elt_at_index (m->ply_pool, 0);
- ip4_fib_mtrie_leaf_t l;
-
- l = p->leaves[dst.as_u8[0]];
- if (ip4_fib_mtrie_leaf_is_terminal (l))
- return ip4_fib_mtrie_leaf_get_adj_index (l);
-
- p = get_next_ply_for_leaf (m, l);
- l = p->leaves[dst.as_u8[1]];
- if (ip4_fib_mtrie_leaf_is_terminal (l))
- return ip4_fib_mtrie_leaf_get_adj_index (l);
-
- p = get_next_ply_for_leaf (m, l);
- l = p->leaves[dst.as_u8[2]];
- if (ip4_fib_mtrie_leaf_is_terminal (l))
- return ip4_fib_mtrie_leaf_get_adj_index (l);
-
- p = get_next_ply_for_leaf (m, l);
- l = p->leaves[dst.as_u8[3]];
-
- ASSERT (ip4_fib_mtrie_leaf_is_terminal (l));
- return ip4_fib_mtrie_leaf_get_adj_index (l);
-}
-
typedef struct
{
ip4_address_t dst_address;
u32 dst_address_length;
u32 adj_index;
+ u32 cover_address_length;
+ u32 cover_adj_index;
} ip4_fib_mtrie_set_unset_leaf_args_t;
static void
uword i;
ASSERT (ip4_fib_mtrie_leaf_is_terminal (new_leaf));
- ASSERT (!ip4_fib_mtrie_leaf_is_empty (new_leaf));
for (i = 0; i < ARRAY_LEN (ply->leaves); i++)
{
__sync_val_compare_and_swap (&ply->leaves[i], old_leaf, new_leaf);
ASSERT (ply->leaves[i] == new_leaf);
ply->dst_address_bits_of_leaves[i] = new_leaf_dst_address_bits;
- ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_empty (old_leaf);
+ ply->n_non_empty_leafs += ip4_fib_mtrie_leaf_is_non_empty (ply, i);
}
}
}
i32 n_dst_bits_next_plies;
u8 dst_byte;
- ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
+ ASSERT (a->dst_address_length >= 0 && a->dst_address_length <= 32);
ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
n_dst_bits_next_plies =
{
uword i, n_dst_bits_this_ply, old_leaf_is_terminal;
- n_dst_bits_this_ply = -n_dst_bits_next_plies;
+ n_dst_bits_this_ply = clib_min (8, -n_dst_bits_next_plies);
ASSERT ((a->dst_address.as_u8[dst_address_byte_index] &
pow2_mask (n_dst_bits_this_ply)) == 0);
if (old_leaf_is_terminal)
{
+ old_ply->n_non_empty_leafs -=
+ ip4_fib_mtrie_leaf_is_non_empty (old_ply, i);
old_ply->dst_address_bits_of_leaves[i] =
a->dst_address_length;
__sync_val_compare_and_swap (&old_ply->leaves[i], old_leaf,
new_leaf);
ASSERT (old_ply->leaves[i] == new_leaf);
+
old_ply->n_non_empty_leafs +=
- ip4_fib_mtrie_leaf_is_empty (old_leaf);
+ ip4_fib_mtrie_leaf_is_non_empty (old_ply, i);
ASSERT (old_ply->n_non_empty_leafs <=
ARRAY_LEN (old_ply->leaves));
}
else
{
ip4_fib_mtrie_ply_t *old_ply, *new_ply;
+ u8 ply_base_len;
+ ply_base_len = 8 * (dst_address_byte_index + 1);
old_ply = pool_elt_at_index (m->ply_pool, old_ply_index);
old_leaf = old_ply->leaves[dst_byte];
if (ip4_fib_mtrie_leaf_is_terminal (old_leaf))
{
- new_leaf =
- ply_create (m, old_leaf,
- old_ply->dst_address_bits_of_leaves[dst_byte]);
+ old_ply->n_non_empty_leafs -=
+ ip4_fib_mtrie_leaf_is_non_empty (old_ply, dst_byte);
+
+ new_leaf = ply_create (m, old_leaf,
+ clib_max (old_ply->dst_address_bits_of_leaves
+ [dst_byte], ply_base_len),
+ ply_base_len);
new_ply = get_next_ply_for_leaf (m, new_leaf);
/* Refetch since ply_create may move pool. */
__sync_val_compare_and_swap (&old_ply->leaves[dst_byte], old_leaf,
new_leaf);
ASSERT (old_ply->leaves[dst_byte] == new_leaf);
- old_ply->dst_address_bits_of_leaves[dst_byte] = 0;
-
- old_ply->n_non_empty_leafs -=
- ip4_fib_mtrie_leaf_is_non_empty (old_leaf);
- ASSERT (old_ply->n_non_empty_leafs >= 0);
+ old_ply->dst_address_bits_of_leaves[dst_byte] = ply_base_len;
/* Account for the ply we just created. */
old_ply->n_non_empty_leafs += 1;
+ ASSERT (old_ply->n_non_empty_leafs >= 0);
}
else
new_ply = get_next_ply_for_leaf (m, old_leaf);
i32 i, n_dst_bits_this_ply, old_leaf_is_terminal;
u8 dst_byte;
- ASSERT (a->dst_address_length > 0 && a->dst_address_length <= 32);
+ ASSERT (a->dst_address_length >= 0 && a->dst_address_length <= 32);
ASSERT (dst_address_byte_index < ARRAY_LEN (a->dst_address.as_u8));
n_dst_bits_next_plies =
&& unset_leaf (m, a, get_next_ply_for_leaf (m, old_leaf),
dst_address_byte_index + 1)))
{
- old_ply->leaves[i] = IP4_FIB_MTRIE_LEAF_EMPTY;
- old_ply->dst_address_bits_of_leaves[i] = 0;
+ old_ply->n_non_empty_leafs -=
+ ip4_fib_mtrie_leaf_is_non_empty (old_ply, i);
+
+ old_ply->leaves[i] =
+ ip4_fib_mtrie_leaf_set_adj_index (a->cover_adj_index);
+ old_ply->dst_address_bits_of_leaves[i] =
+ clib_max (old_ply->dst_address_bits_base,
+ a->cover_address_length);
- /* No matter what we just deleted a non-empty leaf. */
- ASSERT (!ip4_fib_mtrie_leaf_is_empty (old_leaf));
- old_ply->n_non_empty_leafs -= 1;
+ old_ply->n_non_empty_leafs +=
+ ip4_fib_mtrie_leaf_is_non_empty (old_ply, i);
ASSERT (old_ply->n_non_empty_leafs >= 0);
if (old_ply->n_non_empty_leafs == 0 && dst_address_byte_index > 0)
/* Old ply was deleted. */
return 1;
}
+#if CLIB_DEBUG > 0
+ else if (dst_address_byte_index)
+ {
+ int ii, count = 0;
+ for (ii = 0; ii < ARRAY_LEN (old_ply->leaves); ii++)
+ {
+ count += ip4_fib_mtrie_leaf_is_non_empty (old_ply, ii);
+ }
+ ASSERT (count);
+ }
+#endif
}
}
{
ip4_fib_mtrie_leaf_t root;
memset (m, 0, sizeof (m[0]));
- m->default_leaf = IP4_FIB_MTRIE_LEAF_EMPTY;
- root = ply_create (m, IP4_FIB_MTRIE_LEAF_EMPTY, /* dst_address_bits_of_leaves */
- 0);
+ root = ply_create (m, IP4_FIB_MTRIE_LEAF_EMPTY, 0, 0);
ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (root) == 0);
}
if (!is_del)
{
- if (dst_address_length == 0)
- m->default_leaf = ip4_fib_mtrie_leaf_set_adj_index (adj_index);
- else
- set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
+ set_leaf (m, &a, /* ply_index */ 0, /* dst_address_byte_index */ 0);
}
else
{
- if (dst_address_length == 0)
- m->default_leaf = IP4_FIB_MTRIE_LEAF_EMPTY;
+ ip4_main_t *im = &ip4_main;
- else
+ if (dst_address_length)
{
- ip4_main_t *im = &ip4_main;
- uword i;
+ word i;
- unset_leaf (m, &a, root_ply, 0);
-
- /* Find next less specific route and insert into mtrie. */
- for (i = dst_address_length - 1; i >= 1; i--)
+ /* If the ply was not deleted, then we need to fill the
+ * bucket just reset will the leaf from the less specfic
+ * cover.
+ * Find next less specific route and insert into mtrie. */
+ for (i = dst_address_length - 1; i >= 0; i--)
{
uword *p;
index_t lbi;
if (INDEX_INVALID == lbi)
continue;
- a.dst_address = key;
- a.adj_index = lbi;
- a.dst_address_length = i;
+ a.cover_adj_index = lbi;
+ a.cover_address_length = i;
- set_leaf (m, &a, /* ply_index */ 0,
- /* dst_address_byte_index */ 0);
break;
}
}
}
+ else
+ {
+ a.cover_adj_index = 0;
+ a.cover_address_length = 0;
+ }
+
+ /* the top level ply is never removed, so we can ignore the return code */
+ unset_leaf (m, &a, root_ply, 0);
}
}
{
ip4_fib_mtrie_leaf_t l = va_arg (*va, ip4_fib_mtrie_leaf_t);
- if (ip4_fib_mtrie_leaf_is_empty (l))
- s = format (s, "miss");
- else if (ip4_fib_mtrie_leaf_is_terminal (l))
- s = format (s, "adj %d", ip4_fib_mtrie_leaf_get_adj_index (l));
+ if (ip4_fib_mtrie_leaf_is_terminal (l))
+ s = format (s, "lb-index %d", ip4_fib_mtrie_leaf_get_adj_index (l));
else
s = format (s, "next ply %d", ip4_fib_mtrie_leaf_get_next_ply_index (l));
return s;
{
ip4_fib_mtrie_leaf_t l = p->leaves[i];
- if (!ip4_fib_mtrie_leaf_is_empty (l))
+ if (ip4_fib_mtrie_leaf_is_non_empty (p, i))
{
u32 a, ia_length;
ip4_address_t ia;
typedef u32 ip4_fib_mtrie_leaf_t;
#define IP4_FIB_MTRIE_LEAF_EMPTY (1 + 2*0)
-#define IP4_FIB_MTRIE_LEAF_ROOT (0 + 2*0)
-always_inline u32
-ip4_fib_mtrie_leaf_is_empty (ip4_fib_mtrie_leaf_t n)
-{
- return n == IP4_FIB_MTRIE_LEAF_EMPTY;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_is_non_empty (ip4_fib_mtrie_leaf_t n)
-{
- return n != IP4_FIB_MTRIE_LEAF_EMPTY;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
-{
- return n & 1;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
-{
- ASSERT (ip4_fib_mtrie_leaf_is_terminal (n));
- return n >> 1;
-}
-
-always_inline ip4_fib_mtrie_leaf_t
-ip4_fib_mtrie_leaf_set_adj_index (u32 adj_index)
-{
- ip4_fib_mtrie_leaf_t l;
- l = 1 + 2 * adj_index;
- ASSERT (ip4_fib_mtrie_leaf_get_adj_index (l) == adj_index);
- return l;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_is_next_ply (ip4_fib_mtrie_leaf_t n)
-{
- return (n & 1) == 0;
-}
-
-always_inline u32
-ip4_fib_mtrie_leaf_get_next_ply_index (ip4_fib_mtrie_leaf_t n)
-{
- ASSERT (ip4_fib_mtrie_leaf_is_next_ply (n));
- return n >> 1;
-}
-
-always_inline ip4_fib_mtrie_leaf_t
-ip4_fib_mtrie_leaf_set_next_ply_index (u32 i)
-{
- ip4_fib_mtrie_leaf_t l;
- l = 0 + 2 * i;
- ASSERT (ip4_fib_mtrie_leaf_get_next_ply_index (l) == i);
- return l;
-}
-
-/* One ply of the 4 ply mtrie fib. */
+/**
+ * @brief One ply of the 4 ply mtrie fib.
+ */
typedef struct
{
+ /**
+ * The leaves/slots/buckets to be filed with leafs
+ */
union
{
ip4_fib_mtrie_leaf_t leaves[256];
#endif
};
- /* Prefix length for terminal leaves. */
+ /**
+ * Prefix length for leaves/ply.
+ */
u8 dst_address_bits_of_leaves[256];
- /* Number of non-empty leafs (whether terminal or not). */
+ /**
+ * Number of non-empty leafs (whether terminal or not).
+ */
i32 n_non_empty_leafs;
+ /**
+ * The length of the ply's coviering prefix. Also a measure of its depth
+ * If a leaf in a slot has a mask length longer than this then it is
+ * 'non-empty'. Otherwise it is the value of the cover.
+ */
+ i32 dst_address_bits_base;
+
/* Pad to cache line boundary. */
- u8 pad[CLIB_CACHE_LINE_BYTES - 1 * sizeof (i32)];
+ u8 pad[CLIB_CACHE_LINE_BYTES - 2 * sizeof (i32)];
}
ip4_fib_mtrie_ply_t;
{
/* Pool of plies. Index zero is root ply. */
ip4_fib_mtrie_ply_t *ply_pool;
-
- /* Special case leaf for default route 0.0.0.0/0. */
- ip4_fib_mtrie_leaf_t default_leaf;
} ip4_fib_mtrie_t;
void ip4_fib_mtrie_init (ip4_fib_mtrie_t * m);
u32 dst_address_length,
u32 adj_index, u32 is_del);
-/* Returns adjacency index. */
-u32 ip4_mtrie_lookup_address (ip4_fib_mtrie_t * m, ip4_address_t dst);
-
format_function_t format_ip4_fib_mtrie;
+always_inline u32
+ip4_fib_mtrie_leaf_is_terminal (ip4_fib_mtrie_leaf_t n)
+{
+ return n & 1;
+}
+
+always_inline u32
+ip4_fib_mtrie_leaf_get_adj_index (ip4_fib_mtrie_leaf_t n)
+{
+ ASSERT (ip4_fib_mtrie_leaf_is_terminal (n));
+ return n >> 1;
+}
+
/* Lookup step. Processes 1 byte of 4 byte ip4 address. */
always_inline ip4_fib_mtrie_leaf_t
-ip4_fib_mtrie_lookup_step (ip4_fib_mtrie_t * m,
+ip4_fib_mtrie_lookup_step (const ip4_fib_mtrie_t * m,
ip4_fib_mtrie_leaf_t current_leaf,
const ip4_address_t * dst_address,
u32 dst_address_byte_index)
{
- ip4_fib_mtrie_leaf_t next_leaf;
ip4_fib_mtrie_ply_t *ply;
uword current_is_terminal = ip4_fib_mtrie_leaf_is_terminal (current_leaf);
- ply = m->ply_pool + (current_is_terminal ? 0 : (current_leaf >> 1));
- next_leaf = ply->leaves[dst_address->as_u8[dst_address_byte_index]];
- next_leaf = current_is_terminal ? current_leaf : next_leaf;
+ if (!current_is_terminal)
+ {
+ ply = m->ply_pool + (current_leaf >> 1);
+ return (ply->leaves[dst_address->as_u8[dst_address_byte_index]]);
+ }
+
+ return current_leaf;
+}
+
+/* Lookup step. Processes 1 byte of 4 byte ip4 address. */
+always_inline ip4_fib_mtrie_leaf_t
+ip4_fib_mtrie_lookup_step_one (const ip4_fib_mtrie_t * m,
+ const ip4_address_t * dst_address)
+{
+ ip4_fib_mtrie_leaf_t next_leaf;
+ ip4_fib_mtrie_ply_t *ply;
+
+ ply = m->ply_pool;
+ next_leaf = ply->leaves[dst_address->as_u8[0]];
return next_leaf;
}
mtrie0 = &ip4_fib_get (c0->fib_index)->mtrie;
mtrie1 = &ip4_fib_get (c1->fib_index)->mtrie;
- leaf0 = leaf1 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf0 =
- ip4_fib_mtrie_lookup_step (mtrie0, leaf0, &ip0->src_address, 0);
- leaf1 =
- ip4_fib_mtrie_lookup_step (mtrie1, leaf1, &ip1->src_address, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, &ip0->src_address);
+ leaf1 = ip4_fib_mtrie_lookup_step_one (mtrie1, &ip1->src_address);
leaf0 =
ip4_fib_mtrie_lookup_step (mtrie0, leaf0, &ip0->src_address, 1);
mtrie0 = &ip4_fib_get (c0->fib_index)->mtrie;
- leaf0 = IP4_FIB_MTRIE_LEAF_ROOT;
-
- leaf0 =
- ip4_fib_mtrie_lookup_step (mtrie0, leaf0, &ip0->src_address, 0);
+ leaf0 = ip4_fib_mtrie_lookup_step_one (mtrie0, &ip0->src_address);
leaf0 =
ip4_fib_mtrie_lookup_step (mtrie0, leaf0, &ip0->src_address, 1);
adj_index0 = vnet_buffer (p0)->ip.adj_index[VLIB_TX];
adj_index1 = vnet_buffer (p1)->ip.adj_index[VLIB_TX];
- /* We should never rewrite a pkt using the MISS adjacency */
- ASSERT (adj_index0 && adj_index1);
-
ip0 = vlib_buffer_get_current (p0);
ip1 = vlib_buffer_get_current (p1);
adj_index0 = vnet_buffer (p0)->ip.adj_index[VLIB_TX];
- /* We should never rewrite a pkt using the MISS adjacency */
- ASSERT (adj_index0);
-
adj0 = ip_get_adjacency (lm, adj_index0);
ip0 = vlib_buffer_get_current (p0);
adj_index0 = vnet_buffer (p0)->ip.adj_index[VLIB_TX];
adj_index1 = vnet_buffer (p1)->ip.adj_index[VLIB_TX];
- /* We should never rewrite a pkt using the MISS adjacency */
- ASSERT(adj_index0);
- ASSERT(adj_index1);
-
adj0 = adj_get(adj_index0);
adj1 = adj_get(adj_index1);
hdr0 = vlib_buffer_get_current (p0);
adj_index0 = vnet_buffer (p0)->ip.adj_index[VLIB_TX];
- /* We should never rewrite a pkt using the MISS adjacency */
- ASSERT(adj_index0);
-
adj0 = adj_get(adj_index0);
hdr0 = vlib_buffer_get_current (p0);
n_left_to_next -= 1;
adj_index0 = vnet_buffer (p0)->ip.adj_index[VLIB_TX];
- ASSERT(adj_index0);
adj0 = adj_get(adj_index0);
Code Review / vpp.git / commitdiff