diff options
Diffstat (limited to 'src/vnet/fib/ip6_fib.c')
-rw-r--r-- | src/vnet/fib/ip6_fib.c | 490 |
1 files changed, 180 insertions, 310 deletions
diff --git a/src/vnet/fib/ip6_fib.c b/src/vnet/fib/ip6_fib.c index ccf8e22f5a7..f844cfaa420 100644 --- a/src/vnet/fib/ip6_fib.c +++ b/src/vnet/fib/ip6_fib.c @@ -20,14 +20,20 @@ #include <vppinfra/bihash_24_8.h> #include <vppinfra/bihash_template.c> -ip6_fib_table_instance_t ip6_fib_table[IP6_FIB_NUM_TABLES]; +ip6_fib_fwding_table_instance_t ip6_fib_fwding_table; /* ip6 lookup table config parameters */ u32 ip6_fib_table_nbuckets; uword ip6_fib_table_size; +typedef struct ip6_fib_hash_key_t_ +{ + ip6_address_t addr; + u8 len; +} ip6_fib_hash_key_t; + static void -vnet_ip6_fib_init (u32 fib_index) +ip6_fib_hash_load_specials (u32 fib_index) { fib_prefix_t pfx = { .fp_proto = FIB_PROTOCOL_IP6, @@ -77,7 +83,7 @@ create_fib_with_table_id (u32 table_id, ASSERT((fib_table - ip6_main.fibs) == (v6_fib - ip6_main.v6_fibs)); - + fib_table->ft_proto = FIB_PROTOCOL_IP6; fib_table->ft_index = v6_fib->index = @@ -92,9 +98,15 @@ create_fib_with_table_id (u32 table_id, fib_table->ft_flags = flags; fib_table->ft_desc = desc; - vnet_ip6_fib_init(fib_table->ft_index); fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_IP6, src); + v6_fib->fib_entry_by_dst_address = hash_create_mem(2, sizeof(ip6_fib_hash_key_t), sizeof(fib_node_index_t)); + + /* + * add the special entries into the new FIB + */ + ip6_fib_hash_load_specials (fib_table->ft_index); + return (fib_table->ft_index); } @@ -173,54 +185,40 @@ ip6_fib_table_destroy (u32 fib_index) } vec_free (fib_table->ft_locks); vec_free(fib_table->ft_src_route_counts); + hash_free(pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address); pool_put_index(ip6_main.v6_fibs, fib_table->ft_index); pool_put(ip6_main.fibs, fib_table); } +static void +ip6_fib_table_mk_key (ip6_fib_hash_key_t *key, const ip6_address_t *addr, u8 len) +{ + const ip6_address_t *mask = &ip6_main.fib_masks[len]; + key->addr.as_u64[0] = addr->as_u64[0] & mask->as_u64[0]; + key->addr.as_u64[1] = addr->as_u64[1] & mask->as_u64[1]; + key->len = len; +} + fib_node_index_t ip6_fib_table_lookup (u32 fib_index, const ip6_address_t *addr, u32 len) { - ip6_fib_table_instance_t *table; - clib_bihash_kv_24_8_t kv, value; - int i, n_p, rv; - u64 fib; - - table = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING]; - n_p = vec_len (table->prefix_lengths_in_search_order); - - kv.key[0] = addr->as_u64[0]; - kv.key[1] = addr->as_u64[1]; - fib = ((u64)((fib_index))<<32); + uword *hash = pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address; + ip6_fib_hash_key_t key; + i32 mask_len; + uword *result; - /* - * start search from a mask length same length or shorter. - * we don't want matches longer than the mask passed - */ - i = 0; - while (i < n_p && table->prefix_lengths_in_search_order[i] > len) + for (mask_len = len; mask_len >= 0; mask_len--) { - i++; + ip6_fib_table_mk_key (&key, addr, mask_len); + result = hash_get_mem(hash, &key); + if (result) { + return result[0]; + } } - for (; i < n_p; i++) - { - int dst_address_length = table->prefix_lengths_in_search_order[i]; - ip6_address_t * mask = &ip6_main.fib_masks[dst_address_length]; - - ASSERT(dst_address_length >= 0 && dst_address_length <= 128); - //As lengths are decreasing, masks are increasingly specific. - kv.key[0] &= mask->as_u64[0]; - kv.key[1] &= mask->as_u64[1]; - kv.key[2] = fib | dst_address_length; - - rv = clib_bihash_search_inline_2_24_8(&table->ip6_hash, &kv, &value); - if (rv == 0) - return value.value; - } - - return (FIB_NODE_INDEX_INVALID); + return FIB_NODE_INDEX_INVALID; } fib_node_index_t @@ -228,53 +226,11 @@ ip6_fib_table_lookup_exact_match (u32 fib_index, const ip6_address_t *addr, u32 len) { - ip6_fib_table_instance_t *table; - clib_bihash_kv_24_8_t kv, value; - ip6_address_t *mask; - u64 fib; - int rv; - - table = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING]; - mask = &ip6_main.fib_masks[len]; - fib = ((u64)((fib_index))<<32); - - kv.key[0] = addr->as_u64[0] & mask->as_u64[0]; - kv.key[1] = addr->as_u64[1] & mask->as_u64[1]; - kv.key[2] = fib | len; - - rv = clib_bihash_search_inline_2_24_8(&table->ip6_hash, &kv, &value); - if (rv == 0) - return value.value; - - return (FIB_NODE_INDEX_INVALID); -} - -static void -compute_prefix_lengths_in_search_order (ip6_fib_table_instance_t *table) -{ - u8 *old, *prefix_lengths_in_search_order = NULL; - int i; - - /* - * build the list in a scratch space then cutover so the workers - * can continue uninterrupted. - */ - old = table->prefix_lengths_in_search_order; - - /* Note: bitmap reversed so this is in fact a longest prefix match */ - clib_bitmap_foreach (i, table->non_empty_dst_address_length_bitmap) - { - int dst_address_length = 128 - i; - vec_add1(prefix_lengths_in_search_order, dst_address_length); - } - - table->prefix_lengths_in_search_order = prefix_lengths_in_search_order; - - /* - * let the workers go once round the track before we free the old set - */ - vlib_worker_wait_one_loop(); - vec_free(old); + uword *hash = pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address; + ip6_fib_hash_key_t key; + ip6_fib_table_mk_key (&key, addr, len); + uword *result = hash_get(hash, &key); + return result ? result[0] : FIB_NODE_INDEX_INVALID; } void @@ -282,30 +238,10 @@ ip6_fib_table_entry_remove (u32 fib_index, const ip6_address_t *addr, u32 len) { - ip6_fib_table_instance_t *table; - clib_bihash_kv_24_8_t kv; - ip6_address_t *mask; - u64 fib; - - table = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING]; - mask = &ip6_main.fib_masks[len]; - fib = ((u64)((fib_index))<<32); - - kv.key[0] = addr->as_u64[0] & mask->as_u64[0]; - kv.key[1] = addr->as_u64[1] & mask->as_u64[1]; - kv.key[2] = fib | len; - - clib_bihash_add_del_24_8(&table->ip6_hash, &kv, 0); - - /* refcount accounting */ - ASSERT (table->dst_address_length_refcounts[len] > 0); - if (--table->dst_address_length_refcounts[len] == 0) - { - table->non_empty_dst_address_length_bitmap = - clib_bitmap_set (table->non_empty_dst_address_length_bitmap, - 128 - len, 0); - compute_prefix_lengths_in_search_order (table); - } + uword **hash = &pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address; + ip6_fib_hash_key_t key; + ip6_fib_table_mk_key (&key, addr, len); + hash_unset_mem_free(hash, &key); } void @@ -314,29 +250,11 @@ ip6_fib_table_entry_insert (u32 fib_index, u32 len, fib_node_index_t fib_entry_index) { - ip6_fib_table_instance_t *table; - clib_bihash_kv_24_8_t kv; - ip6_address_t *mask; - u64 fib; - - table = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING]; - mask = &ip6_main.fib_masks[len]; - fib = ((u64)((fib_index))<<32); - - kv.key[0] = addr->as_u64[0] & mask->as_u64[0]; - kv.key[1] = addr->as_u64[1] & mask->as_u64[1]; - kv.key[2] = fib | len; - kv.value = fib_entry_index; - - clib_bihash_add_del_24_8(&table->ip6_hash, &kv, 1); - - if (0 == table->dst_address_length_refcounts[len]++) - { - table->non_empty_dst_address_length_bitmap = - clib_bitmap_set (table->non_empty_dst_address_length_bitmap, - 128 - len, 1); - compute_prefix_lengths_in_search_order (table); - } + uword **hash = &pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address; + ip6_fib_hash_key_t key; + ip6_fib_table_mk_key (&key, addr, len); + ASSERT (0 == hash_get(*hash, &key) && "entry already exists"); + hash_set_mem_alloc(hash, &key, fib_entry_index); } u32 ip6_fib_table_fwding_lookup_with_if_index (ip6_main_t * im, @@ -361,18 +279,46 @@ ip6_fib_table_get_index_for_sw_if_index (u32 sw_if_index) return (ip6_main.fib_index_by_sw_if_index[sw_if_index]); } +static void +compute_prefix_lengths_in_search_order (ip6_fib_fwding_table_instance_t *table) +{ + u8 *old, *prefix_lengths_in_search_order = NULL; + int i; + + /* + * build the list in a scratch space then cutover so the workers + * can continue uninterrupted. + */ + old = table->prefix_lengths_in_search_order; + + /* Note: bitmap reversed so this is in fact a longest prefix match */ + clib_bitmap_foreach (i, table->non_empty_dst_address_length_bitmap) + { + int dst_address_length = 128 - i; + vec_add1(prefix_lengths_in_search_order, dst_address_length); + } + + table->prefix_lengths_in_search_order = prefix_lengths_in_search_order; + + /* + * let the workers go once round the track before we free the old set + */ + vlib_worker_wait_one_loop(); + vec_free(old); +} + void ip6_fib_table_fwding_dpo_update (u32 fib_index, const ip6_address_t *addr, u32 len, const dpo_id_t *dpo) { - ip6_fib_table_instance_t *table; + ip6_fib_fwding_table_instance_t *table; clib_bihash_kv_24_8_t kv; ip6_address_t *mask; u64 fib; - table = &ip6_fib_table[IP6_FIB_TABLE_FWDING]; + table = &ip6_fib_fwding_table; mask = &ip6_main.fib_masks[len]; fib = ((u64)((fib_index))<<32); @@ -398,12 +344,12 @@ ip6_fib_table_fwding_dpo_remove (u32 fib_index, u32 len, const dpo_id_t *dpo) { - ip6_fib_table_instance_t *table; + ip6_fib_fwding_table_instance_t *table; clib_bihash_kv_24_8_t kv; ip6_address_t *mask; u64 fib; - table = &ip6_fib_table[IP6_FIB_TABLE_FWDING]; + table = &ip6_fib_fwding_table; mask = &ip6_main.fib_masks[len]; fib = ((u64)((fib_index))<<32); @@ -425,101 +371,18 @@ ip6_fib_table_fwding_dpo_remove (u32 fib_index, } } -/** - * @brief Context when walking the IPv6 table. Since all VRFs are in the - * same hash table, we need to filter only those we need as we walk - */ -typedef struct ip6_fib_walk_ctx_t_ -{ - u32 i6w_fib_index; - fib_table_walk_fn_t i6w_fn; - void *i6w_ctx; - fib_prefix_t i6w_root; - fib_prefix_t *i6w_sub_trees; -} ip6_fib_walk_ctx_t; - -static int -ip6_fib_walk_cb (clib_bihash_kv_24_8_t * kvp, - void *arg) -{ - ip6_fib_walk_ctx_t *ctx = arg; - ip6_address_t key; - - if ((kvp->key[2] >> 32) == ctx->i6w_fib_index) - { - key.as_u64[0] = kvp->key[0]; - key.as_u64[1] = kvp->key[1]; - - if (ip6_destination_matches_route(&ip6_main, - &key, - &ctx->i6w_root.fp_addr.ip6, - ctx->i6w_root.fp_len)) - { - const fib_prefix_t *sub_tree; - int skip = 0; - - /* - * exclude sub-trees the walk does not want to explore - */ - vec_foreach(sub_tree, ctx->i6w_sub_trees) - { - if (ip6_destination_matches_route(&ip6_main, - &key, - &sub_tree->fp_addr.ip6, - sub_tree->fp_len)) - { - skip = 1; - break; - } - } - - if (!skip) - { - switch (ctx->i6w_fn(kvp->value, ctx->i6w_ctx)) - { - case FIB_TABLE_WALK_CONTINUE: - break; - case FIB_TABLE_WALK_SUB_TREE_STOP: { - fib_prefix_t pfx = { - .fp_proto = FIB_PROTOCOL_IP6, - .fp_len = kvp->key[2] & 0xffffffff, - .fp_addr.ip6 = key, - }; - vec_add1(ctx->i6w_sub_trees, pfx); - break; - } - case FIB_TABLE_WALK_STOP: - goto done; - } - } - } - } -done: - - return (1); -} - void ip6_fib_table_walk (u32 fib_index, fib_table_walk_fn_t fn, void *arg) { - ip6_fib_walk_ctx_t ctx = { - .i6w_fib_index = fib_index, - .i6w_fn = fn, - .i6w_ctx = arg, - .i6w_root = { - .fp_proto = FIB_PROTOCOL_IP6, - }, - .i6w_sub_trees = NULL, + const fib_prefix_t root = { + .fp_proto = FIB_PROTOCOL_IP6, + // address and length default to all 0 }; - - clib_bihash_foreach_key_value_pair_24_8( - &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash, - ip6_fib_walk_cb, - &ctx); - - vec_free(ctx.i6w_sub_trees); + /* A full tree walk is the dengenerate case of a sub-tree from + * the very root */ + return (ip6_fib_table_sub_tree_walk(fib_index, &root, fn, arg)); } void @@ -528,17 +391,43 @@ ip6_fib_table_sub_tree_walk (u32 fib_index, fib_table_walk_fn_t fn, void *arg) { - ip6_fib_walk_ctx_t ctx = { - .i6w_fib_index = fib_index, - .i6w_fn = fn, - .i6w_ctx = arg, - .i6w_root = *root, - }; + uword *hash = pool_elt_at_index(ip6_main.v6_fibs, fib_index)->fib_entry_by_dst_address; + const ip6_fib_hash_key_t *key, *sub_tree; + ip6_fib_hash_key_t *sub_trees = 0; + u32 fei; - clib_bihash_foreach_key_value_pair_24_8( - &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash, - ip6_fib_walk_cb, - &ctx); + /* + * There is no efficient way to walk this hash table. + * so we walk over all entries and check it is covered by the root. + */ + hash_foreach_mem(key, fei, hash, ({ + /* check if the prefix is covered by the root */ + if (!ip6_destination_matches_route(&ip6_main, &key->addr, &root->fp_addr.ip6, root->fp_len)) + continue; /* not covered by root, ignore */ + + /* exclude sub-trees the walk does not want to explore */ + vec_foreach (sub_tree, sub_trees) + { + if (ip6_destination_matches_route(&ip6_main, &key->addr, &sub_tree->addr, sub_tree->len)) + goto ignore_sub_tree; + } + + switch (fn(fei, arg)) + { + case FIB_TABLE_WALK_STOP: + goto done; + case FIB_TABLE_WALK_CONTINUE: + break; + case FIB_TABLE_WALK_SUB_TREE_STOP: + vec_add1(sub_trees, *key); + break; + } + +ignore_sub_tree:; + })); + +done: + vec_free(sub_trees); } typedef struct ip6_fib_show_ctx_t_ { @@ -599,8 +488,7 @@ format_ip6_fib_table_memory (u8 * s, va_list * args) { uword bytes_inuse; - bytes_inuse = (alloc_arena_next(&(ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash)) + - alloc_arena_next(&(ip6_fib_table[IP6_FIB_TABLE_FWDING].ip6_hash))); + bytes_inuse = alloc_arena_next(&ip6_fib_fwding_table.ip6_hash); s = format(s, "%=30s %=6d %=12ld\n", "IPv6 unicast", @@ -609,26 +497,60 @@ format_ip6_fib_table_memory (u8 * s, va_list * args) return (s); } -typedef struct { - u32 fib_index; - u64 count_by_prefix_length[129]; -} count_routes_in_fib_at_prefix_length_arg_t; - -static int -count_routes_in_fib_at_prefix_length (clib_bihash_kv_24_8_t * kvp, - void *arg) +void +ip6_fib_table_show (vlib_main_t *vm, fib_table_t *fib_table, int summary) { - count_routes_in_fib_at_prefix_length_arg_t * ap = arg; - int mask_width; + ip6_main_t * im6 = &ip6_main; + ip6_fib_t *fib = pool_elt_at_index(im6->v6_fibs, fib_table->ft_index); + fib_source_t source; + u8 *s = NULL; + + s = format(s, "%U, fib_index:%d, flow hash:[%U] epoch:%d flags:%U locks:[", + format_fib_table_name, fib->index, + FIB_PROTOCOL_IP6, + fib->index, + format_ip_flow_hash_config, + fib_table->ft_flow_hash_config, + fib_table->ft_epoch, + format_fib_table_flags, fib_table->ft_flags); + + vec_foreach_index(source, fib_table->ft_locks) + { + if (0 != fib_table->ft_locks[source]) + { + s = format(s, "%U:%d, ", + format_fib_source, source, + fib_table->ft_locks[source]); + } + } + s = format (s, "]"); + vlib_cli_output (vm, "%v", s); + vec_free(s); - if ((kvp->key[2]>>32) != ap->fib_index) - return (BIHASH_WALK_CONTINUE); + /* Show summary? */ + if (summary) + { + u32 count_by_prefix_length[129]; + const ip6_fib_hash_key_t *key; + u32 fei; + int len; - mask_width = kvp->key[2] & 0xFF; + vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count"); - ap->count_by_prefix_length[mask_width]++; + clib_memset (count_by_prefix_length, 0, sizeof(count_by_prefix_length)); - return (BIHASH_WALK_CONTINUE); + hash_foreach_mem(key, fei, fib->fib_entry_by_dst_address, ({ + ASSERT(key->len <= 128); + count_by_prefix_length[key->len]++; + })); + + for (len = 128; len >= 0; len--) + { + if (count_by_prefix_length[len]) + vlib_cli_output (vm, "%=20d%=16lld", + len, count_by_prefix_length[len]); + } + } } static clib_error_t * @@ -636,7 +558,6 @@ ip6_show_fib (vlib_main_t * vm, unformat_input_t * input, vlib_cli_command_t * cmd) { - count_routes_in_fib_at_prefix_length_arg_t _ca, *ca = &_ca; ip6_main_t * im6 = &ip6_main; fib_table_t *fib_table; ip6_fib_t * fib; @@ -683,22 +604,15 @@ ip6_show_fib (vlib_main_t * vm, if (hash) { - vlib_cli_output (vm, "IPv6 Non-Forwarding Hash Table:\n%U\n", - BV (format_bihash), - &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash, - detail); vlib_cli_output (vm, "IPv6 Forwarding Hash Table:\n%U\n", BV (format_bihash), - &ip6_fib_table[IP6_FIB_TABLE_FWDING].ip6_hash, + &ip6_fib_fwding_table.ip6_hash, detail); return (NULL); } pool_foreach (fib_table, im6->fibs) { - fib_source_t source; - u8 *s = NULL; - fib = pool_elt_at_index(im6->v6_fibs, fib_table->ft_index); if (table_id >= 0 && table_id != (int)fib->table_id) continue; @@ -707,50 +621,9 @@ ip6_show_fib (vlib_main_t * vm, if (fib_table->ft_flags & FIB_TABLE_FLAG_IP6_LL) continue; - s = format(s, "%U, fib_index:%d, flow hash:[%U] epoch:%d flags:%U locks:[", - format_fib_table_name, fib->index, - FIB_PROTOCOL_IP6, - fib->index, - format_ip_flow_hash_config, - fib_table->ft_flow_hash_config, - fib_table->ft_epoch, - format_fib_table_flags, fib_table->ft_flags); - - vec_foreach_index(source, fib_table->ft_locks) - { - if (0 != fib_table->ft_locks[source]) - { - s = format(s, "%U:%d, ", - format_fib_source, source, - fib_table->ft_locks[source]); - } - } - s = format (s, "]"); - vlib_cli_output (vm, "%v", s); - vec_free(s); - - /* Show summary? */ - if (! verbose) - { - clib_bihash_24_8_t * h = &ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash; - int len; - - vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count"); - - clib_memset (ca, 0, sizeof(*ca)); - ca->fib_index = fib->index; - - clib_bihash_foreach_key_value_pair_24_8 - (h, count_routes_in_fib_at_prefix_length, ca); - - for (len = 128; len >= 0; len--) - { - if (ca->count_by_prefix_length[len]) - vlib_cli_output (vm, "%=20d%=16lld", - len, ca->count_by_prefix_length[len]); - } - continue; - } + ip6_fib_table_show(vm, fib_table, !verbose); + if (!verbose) + continue; if (!matching) { @@ -906,12 +779,9 @@ ip6_fib_init (vlib_main_t * vm) if (ip6_fib_table_size == 0) ip6_fib_table_size = IP6_FIB_DEFAULT_HASH_MEMORY_SIZE; - clib_bihash_init_24_8 (&(ip6_fib_table[IP6_FIB_TABLE_FWDING].ip6_hash), + clib_bihash_init_24_8 (&(ip6_fib_fwding_table.ip6_hash), "ip6 FIB fwding table", ip6_fib_table_nbuckets, ip6_fib_table_size); - clib_bihash_init_24_8 (&ip6_fib_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash, - "ip6 FIB non-fwding table", - ip6_fib_table_nbuckets, ip6_fib_table_size); return (NULL); } |