diff options
Diffstat (limited to 'src/vnet/fib')
| -rw-r--r-- | src/vnet/fib/ip4_fib.c | 394 | ||||
| -rw-r--r-- | src/vnet/fib/ip4_fib.h | 90 | ||||
| -rw-r--r-- | src/vnet/fib/ip4_fib_16.c | 137 | ||||
| -rw-r--r-- | src/vnet/fib/ip4_fib_16.h | 106 | ||||
| -rw-r--r-- | src/vnet/fib/ip4_fib_8.c | 137 | ||||
| -rw-r--r-- | src/vnet/fib/ip4_fib_8.h | 106 | ||||
| -rw-r--r-- | src/vnet/fib/ip4_fib_hash.c | 249 | ||||
| -rw-r--r-- | src/vnet/fib/ip4_fib_hash.h | 74 |
8 files changed, 907 insertions, 386 deletions
diff --git a/src/vnet/fib/ip4_fib.c b/src/vnet/fib/ip4_fib.c index e8ab653e53a..a343c2b5f37 100644 --- a/src/vnet/fib/ip4_fib.c +++ b/src/vnet/fib/ip4_fib.c @@ -99,6 +99,49 @@ static const ip4_fib_table_special_prefix_t ip4_specials[] = { } }; +void +ip4_fib_hash_load_specials (u32 fib_index) +{ + /* + * add the special entries into the new FIB + */ + int ii; + + for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++) + { + fib_prefix_t prefix = ip4_specials[ii].ift_prefix; + + prefix.fp_addr.ip4.data_u32 = + clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32); + + fib_table_entry_special_add(fib_index, + &prefix, + ip4_specials[ii].ift_source, + ip4_specials[ii].ift_flag); + } +} + +void +ip4_fib_hash_flush_specials (u32 fib_index) +{ + int ii; + + /* + * remove all the specials we added when the table was created. + * In reverse order so the default route is last. + */ + for (ii = ARRAY_LEN(ip4_specials) - 1; ii >= 0; ii--) + { + fib_prefix_t prefix = ip4_specials[ii].ift_prefix; + + prefix.fp_addr.ip4.data_u32 = + clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32); + + fib_table_entry_special_remove(fib_index, + &prefix, + ip4_specials[ii].ift_source); + } +} static u32 ip4_create_fib_with_table_id (u32 table_id, @@ -110,44 +153,34 @@ ip4_create_fib_with_table_id (u32 table_id, pool_get(ip4_main.fibs, fib_table); clib_memset(fib_table, 0, sizeof(*fib_table)); - pool_get_aligned(ip4_main.v4_fibs, v4_fib, CLIB_CACHE_LINE_BYTES); - - ASSERT((fib_table - ip4_main.fibs) == - (v4_fib - ip4_main.v4_fibs)); + pool_get_aligned(ip4_fibs, v4_fib, CLIB_CACHE_LINE_BYTES); fib_table->ft_proto = FIB_PROTOCOL_IP4; - fib_table->ft_index = - v4_fib->index = - (fib_table - ip4_main.fibs); + fib_table->ft_index = (v4_fib - ip4_fibs); + + /* + * It is required that the index of the fib_table_t in its pool + * is the same as the index of the ip4_fib_t in its pool, since the + * rest of the code usues the 'fib_index' to mean either of these + * objects, depending on the context. + */ + ASSERT(fib_table->ft_index == fib_table - ip4_main.fibs); hash_set (ip4_main.fib_index_by_table_id, table_id, fib_table->ft_index); fib_table->ft_table_id = - v4_fib->table_id = + v4_fib->hash.table_id = table_id; fib_table->ft_flow_hash_config = IP_FLOW_HASH_DEFAULT; fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_IP4, src); - ip4_mtrie_16_init(&v4_fib->mtrie); + ip4_fib_table_init(v4_fib); /* * add the special entries into the new FIB */ - int ii; - - for (ii = 0; ii < ARRAY_LEN(ip4_specials); ii++) - { - fib_prefix_t prefix = ip4_specials[ii].ift_prefix; - - prefix.fp_addr.ip4.data_u32 = - clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32); - - fib_table_entry_special_add(fib_table->ft_index, - &prefix, - ip4_specials[ii].ift_source, - ip4_specials[ii].ift_flag); - } + ip4_fib_hash_load_specials(fib_table - ip4_main.fibs); return (fib_table->ft_index); } @@ -156,25 +189,14 @@ void ip4_fib_table_destroy (u32 fib_index) { fib_table_t *fib_table = pool_elt_at_index(ip4_main.fibs, fib_index); - ip4_fib_t *v4_fib = pool_elt_at_index(ip4_main.v4_fibs, fib_index); + ip4_fib_t *v4_fib = pool_elt_at_index(ip4_fibs, fib_table->ft_index); u32 *n_locks; - int ii; /* * remove all the specials we added when the table was created. * In reverse order so the default route is last. */ - for (ii = ARRAY_LEN(ip4_specials) - 1; ii >= 0; ii--) - { - fib_prefix_t prefix = ip4_specials[ii].ift_prefix; - - prefix.fp_addr.ip4.data_u32 = - clib_host_to_net_u32(prefix.fp_addr.ip4.data_u32); - - fib_table_entry_special_remove(fib_table->ft_index, - &prefix, - ip4_specials[ii].ift_source); - } + ip4_fib_hash_flush_specials(fib_table - ip4_main.fibs); /* * validate no more routes. @@ -195,9 +217,9 @@ ip4_fib_table_destroy (u32 fib_index) } vec_free(fib_table->ft_src_route_counts); - ip4_mtrie_16_free(&v4_fib->mtrie); + ip4_fib_table_free(v4_fib); - pool_put(ip4_main.v4_fibs, v4_fib); + pool_put(ip4_fibs, v4_fib); pool_put(ip4_main.fibs, fib_table); } @@ -237,268 +259,6 @@ ip4_fib_table_get_index_for_sw_if_index (u32 sw_if_index) return (ip4_main.fib_index_by_sw_if_index[sw_if_index]); } -/* - * ip4_fib_table_lookup_exact_match - * - * Exact match prefix lookup - */ -fib_node_index_t -ip4_fib_table_lookup_exact_match (const ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len) -{ - uword * hash, * result; - u32 key; - - hash = fib->fib_entry_by_dst_address[len]; - key = (addr->data_u32 & ip4_main.fib_masks[len]); - - result = hash_get(hash, key); - - if (NULL != result) { - return (result[0]); - } - return (FIB_NODE_INDEX_INVALID); -} - -/* - * ip4_fib_table_lookup_adj - * - * Longest prefix match - */ -index_t -ip4_fib_table_lookup_lb (ip4_fib_t *fib, - const ip4_address_t *addr) -{ - fib_node_index_t fei; - - fei = ip4_fib_table_lookup(fib, addr, 32); - - if (FIB_NODE_INDEX_INVALID != fei) - { - const dpo_id_t *dpo; - - dpo = fib_entry_contribute_ip_forwarding(fei); - - return (dpo->dpoi_index); - } - return (INDEX_INVALID); -} - -/* - * ip4_fib_table_lookup - * - * Longest prefix match - */ -fib_node_index_t -ip4_fib_table_lookup (const ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len) -{ - uword * hash, * result; - i32 mask_len; - u32 key; - - for (mask_len = len; mask_len >= 0; mask_len--) - { - hash = fib->fib_entry_by_dst_address[mask_len]; - key = (addr->data_u32 & ip4_main.fib_masks[mask_len]); - - result = hash_get (hash, key); - - if (NULL != result) { - return (result[0]); - } - } - return (FIB_NODE_INDEX_INVALID); -} - -void -ip4_fib_table_entry_insert (ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - fib_node_index_t fib_entry_index) -{ - uword * hash, * result; - u32 key; - - key = (addr->data_u32 & ip4_main.fib_masks[len]); - hash = fib->fib_entry_by_dst_address[len]; - result = hash_get (hash, key); - - if (NULL == result) { - /* - * adding a new entry - */ - - if (NULL == hash) { - hash = hash_create (32 /* elts */, sizeof (uword)); - hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK); - - } - hash = hash_set(hash, key, fib_entry_index); - fib->fib_entry_by_dst_address[len] = hash; - } - else - { - ASSERT(0); - } -} - -void -ip4_fib_table_entry_remove (ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len) -{ - uword * hash, * result; - u32 key; - - key = (addr->data_u32 & ip4_main.fib_masks[len]); - hash = fib->fib_entry_by_dst_address[len]; - result = hash_get (hash, key); - - if (NULL == result) - { - /* - * removing a non-existent entry. i'll allow it. - */ - } - else - { - hash_unset(hash, key); - } - - fib->fib_entry_by_dst_address[len] = hash; -} - -void -ip4_fib_table_fwding_dpo_update (ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - const dpo_id_t *dpo) -{ - ip4_mtrie_16_route_add(&fib->mtrie, addr, len, dpo->dpoi_index); -} - -void -ip4_fib_table_fwding_dpo_remove (ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - const dpo_id_t *dpo, - u32 cover_index) -{ - const fib_prefix_t *cover_prefix; - const dpo_id_t *cover_dpo; - - /* - * We need to pass the MTRIE the LB index and address length of the - * covering prefix, so it can fill the plys with the correct replacement - * for the entry being removed - */ - cover_prefix = fib_entry_get_prefix(cover_index); - cover_dpo = fib_entry_contribute_ip_forwarding(cover_index); - - ip4_mtrie_16_route_del(&fib->mtrie, - addr, len, dpo->dpoi_index, - cover_prefix->fp_len, - cover_dpo->dpoi_index); -} - -void -ip4_fib_table_walk (ip4_fib_t *fib, - fib_table_walk_fn_t fn, - void *ctx) -{ - fib_prefix_t root = { - .fp_proto = FIB_PROTOCOL_IP4, - // address and length default to all 0 - }; - - /* - * A full tree walk is the dengenerate case of a sub-tree from - * the very root - */ - return (ip4_fib_table_sub_tree_walk(fib, &root, fn, ctx)); -} - -void -ip4_fib_table_sub_tree_walk (ip4_fib_t *fib, - const fib_prefix_t *root, - fib_table_walk_fn_t fn, - void *ctx) -{ - fib_prefix_t *sub_trees = NULL; - int i; - - /* - * There is no efficient way to walk this array of hash tables. - * so we walk each table with a mask length greater than and equal to - * the required root and check it is covered by the root. - */ - for (i = root->fp_len; - i < ARRAY_LEN (fib->fib_entry_by_dst_address); - i++) - { - uword * hash = fib->fib_entry_by_dst_address[i]; - - if (NULL != hash) - { - ip4_address_t key; - hash_pair_t * p; - - hash_foreach_pair (p, hash, - ({ - key.as_u32 = p->key; - if (ip4_destination_matches_route(&ip4_main, - &key, - &root->fp_addr.ip4, - 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, sub_trees) - { - if (ip4_destination_matches_route(&ip4_main, - &key, - &sub_tree->fp_addr.ip4, - sub_tree->fp_len)) - { - skip = 1; - break; - } - } - - if (!skip) - { - switch (fn(p->value[0], ctx)) - { - case FIB_TABLE_WALK_CONTINUE: - break; - case FIB_TABLE_WALK_SUB_TREE_STOP: { - fib_prefix_t pfx = { - .fp_proto = FIB_PROTOCOL_IP4, - .fp_len = i, - .fp_addr.ip4 = key, - }; - vec_add1(sub_trees, pfx); - break; - } - case FIB_TABLE_WALK_STOP: - goto done; - } - } - } - })); - } - } -done: - vec_free(sub_trees); - return; -} /** * Walk show context @@ -573,12 +333,11 @@ ip4_show_fib (vlib_main_t * vm, vlib_cli_command_t * cmd) { ip4_main_t * im4 = &ip4_main; - fib_table_t * fib_table; u64 total_mtrie_memory, total_hash_memory; int verbose, matching, mtrie, memory; ip4_address_t matching_address; - u32 matching_mask = 32; - int i, table_id = -1, fib_index = ~0; + u32 fib_index, matching_mask = 32; + int i, table_id = -1, user_fib_index = ~0; int detail = 0; verbose = 1; @@ -610,21 +369,22 @@ ip4_show_fib (vlib_main_t * vm, else if (unformat (input, "table %d", &table_id)) ; - else if (unformat (input, "index %d", &fib_index)) + else if (unformat (input, "index %d", &user_fib_index)) ; else break; } - pool_foreach (fib_table, im4->fibs) + pool_foreach_index (fib_index, im4->fibs) { - ip4_fib_t *fib = pool_elt_at_index(im4->v4_fibs, fib_table->ft_index); + fib_table_t *fib_table = pool_elt_at_index(im4->fibs, fib_index); + ip4_fib_t *fib = pool_elt_at_index(ip4_fibs, fib_table->ft_index); fib_source_t source; u8 *s = NULL; - if (table_id >= 0 && table_id != (int)fib->table_id) + if (table_id >= 0 && table_id != (int)fib->hash.table_id) continue; - if (fib_index != ~0 && fib_index != (int)fib->index) + if (user_fib_index != ~0 && user_fib_index != fib_index) continue; if (memory) @@ -632,12 +392,12 @@ ip4_show_fib (vlib_main_t * vm, uword mtrie_size, hash_size; - mtrie_size = ip4_mtrie_16_memory_usage(&fib->mtrie); + mtrie_size = ip4_mtrie_memory_usage(&fib->mtrie); hash_size = 0; - for (i = 0; i < ARRAY_LEN (fib->fib_entry_by_dst_address); i++) + for (i = 0; i < ARRAY_LEN (fib->hash.fib_entry_by_dst_address); i++) { - uword * hash = fib->fib_entry_by_dst_address[i]; + uword * hash = fib->hash.fib_entry_by_dst_address[i]; if (NULL != hash) { hash_size += hash_bytes(hash); @@ -646,7 +406,7 @@ ip4_show_fib (vlib_main_t * vm, if (verbose) vlib_cli_output (vm, "%U mtrie:%d hash:%d", - format_fib_table_name, fib->index, + format_fib_table_name, fib_index, FIB_PROTOCOL_IP4, mtrie_size, hash_size); @@ -656,9 +416,9 @@ ip4_show_fib (vlib_main_t * vm, } s = format(s, "%U, fib_index:%d, flow hash:[%U] epoch:%d flags:%U locks:[", - format_fib_table_name, fib->index, + format_fib_table_name, fib_index, FIB_PROTOCOL_IP4, - fib->index, + fib_index, format_ip_flow_hash_config, fib_table->ft_flow_hash_config, fib_table->ft_epoch, @@ -679,15 +439,15 @@ ip4_show_fib (vlib_main_t * vm, /* Show summary? */ if (mtrie) { - vlib_cli_output (vm, "%U", format_ip4_mtrie_16, &fib->mtrie, verbose); + vlib_cli_output (vm, "%U", format_ip4_mtrie, &fib->mtrie, verbose); continue; } if (! verbose) { vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count"); - for (i = 0; i < ARRAY_LEN (fib->fib_entry_by_dst_address); i++) + for (i = 0; i < ARRAY_LEN (fib->hash.fib_entry_by_dst_address); i++) { - uword * hash = fib->fib_entry_by_dst_address[i]; + uword * hash = fib->hash.fib_entry_by_dst_address[i]; uword n_elts = hash_elts (hash); if (n_elts > 0) vlib_cli_output (vm, "%20d%16d", i, n_elts); diff --git a/src/vnet/fib/ip4_fib.h b/src/vnet/fib/ip4_fib.h index 46bfcaf85f1..0f6911dd3aa 100644 --- a/src/vnet/fib/ip4_fib.h +++ b/src/vnet/fib/ip4_fib.h @@ -34,77 +34,28 @@ #include <vnet/ip/ip.h> #include <vnet/fib/fib_entry.h> #include <vnet/fib/fib_table.h> -#include <vnet/ip/ip4_mtrie.h> - -typedef struct ip4_fib_t_ -{ - /** Required for pool_get_aligned */ - CLIB_CACHE_LINE_ALIGN_MARK(cacheline0); - - /** - * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes. - * First member so it's in the first cacheline. - */ - ip4_mtrie_16_t mtrie; - - /* Hash table for each prefix length mapping. */ - uword *fib_entry_by_dst_address[33]; - - /* Table ID (hash key) for this FIB. */ - u32 table_id; - - /* Index into FIB vector. */ - u32 index; -} ip4_fib_t; - -extern fib_node_index_t ip4_fib_table_lookup(const ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len); -extern fib_node_index_t ip4_fib_table_lookup_exact_match(const ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len); - -extern void ip4_fib_table_entry_remove(ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len); - -extern void ip4_fib_table_entry_insert(ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - fib_node_index_t fib_entry_index); -extern void ip4_fib_table_destroy(u32 fib_index); - -extern void ip4_fib_table_fwding_dpo_update(ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - const dpo_id_t *dpo); - -extern void ip4_fib_table_fwding_dpo_remove(ip4_fib_t *fib, - const ip4_address_t *addr, - u32 len, - const dpo_id_t *dpo, - fib_node_index_t cover_index); -extern u32 ip4_fib_table_lookup_lb (ip4_fib_t *fib, - const ip4_address_t * dst); +#include <vnet/fib/ip4_fib_8.h> +#include <vnet/fib/ip4_fib_16.h> /** - * @brief Walk all entries in a FIB table - * N.B: This is NOT safe to deletes. If you need to delete walk the whole - * table and store elements in a vector, then delete the elements + * the FIB module uses the 16-8-8 stride trie */ -extern void ip4_fib_table_walk(ip4_fib_t *fib, - fib_table_walk_fn_t fn, - void *ctx); - -/** - * @brief Walk all entries in a sub-tree of the FIB table - * N.B: This is NOT safe to deletes. If you need to delete walk the whole - * table and store elements in a vector, then delete the elements - */ -extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib, - const fib_prefix_t *root, - fib_table_walk_fn_t fn, - void *ctx); +typedef ip4_fib_16_t ip4_fib_t; + +#define ip4_fibs ip4_fib_16s +#define ip4_fib_table_lookup ip4_fib_16_table_lookup +#define ip4_fib_table_lookup_exact_match ip4_fib_16_table_lookup_exact_match +#define ip4_fib_table_entry_remove ip4_fib_16_table_entry_remove +#define ip4_fib_table_entry_insert ip4_fib_16_table_entry_insert +#define ip4_fib_table_fwding_dpo_update ip4_fib_16_table_fwding_dpo_update +#define ip4_fib_table_fwding_dpo_remove ip4_fib_16_table_fwding_dpo_remove +#define ip4_fib_table_lookup_lb ip4_fib_16_table_lookup_lb +#define ip4_fib_table_walk ip4_fib_16_table_walk +#define ip4_fib_table_sub_tree_walk ip4_fib_16_table_sub_tree_walk +#define ip4_fib_table_init ip4_fib_16_table_init +#define ip4_fib_table_free ip4_fib_16_table_free +#define ip4_mtrie_memory_usage ip4_mtrie_16_memory_usage +#define format_ip4_mtrie format_ip4_mtrie_16 /** * @brief Get the FIB at the given index @@ -112,7 +63,7 @@ extern void ip4_fib_table_sub_tree_walk(ip4_fib_t *fib, static inline ip4_fib_t * ip4_fib_get (u32 index) { - return (pool_elt_at_index(ip4_main.v4_fibs, index)); + return (pool_elt_at_index(ip4_fibs, index)); } always_inline u32 @@ -138,6 +89,7 @@ ip4_fib_lookup (ip4_main_t * im, u32 sw_if_index, ip4_address_t * dst) extern u32 ip4_fib_table_find_or_create_and_lock(u32 table_id, fib_source_t src); extern u32 ip4_fib_table_create_and_lock(fib_source_t src); +extern void ip4_fib_table_destroy(u32 fib_index); extern u8 *format_ip4_fib_table_memory(u8 * s, va_list * args); diff --git a/src/vnet/fib/ip4_fib_16.c b/src/vnet/fib/ip4_fib_16.c new file mode 100644 index 00000000000..7699e8926f1 --- /dev/null +++ b/src/vnet/fib/ip4_fib_16.c @@ -0,0 +1,137 @@ +/* + * Copyright (c) 2016 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <vnet/fib/fib_table.h> +#include <vnet/fib/fib_entry.h> +#include <vnet/fib/ip4_fib.h> + +ip4_fib_16_t *ip4_fib_16s; + +void +ip4_fib_16_table_init (ip4_fib_16_t *fib) +{ + ip4_mtrie_16_init(&fib->mtrie); +} + +void +ip4_fib_16_table_free (ip4_fib_16_t *fib) +{ + ip4_mtrie_16_free(&fib->mtrie); +} + +/* + * ip4_fib_16_table_lookup_exact_match + * + * Exact match prefix lookup + */ +fib_node_index_t +ip4_fib_16_table_lookup_exact_match (const ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len) +{ + return (ip4_fib_hash_table_lookup_exact_match(&fib->hash, addr, len)); +} + +/* + * ip4_fib_16_table_lookup_adj + * + * Longest prefix match + */ +index_t +ip4_fib_16_table_lookup_lb (ip4_fib_16_t *fib, + const ip4_address_t *addr) +{ + return (ip4_fib_hash_table_lookup_lb(&fib->hash, addr)); +} + +/* + * ip4_fib_16_table_lookup + * + * Longest prefix match + */ +fib_node_index_t +ip4_fib_16_table_lookup (const ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len) +{ + return (ip4_fib_hash_table_lookup(&fib->hash, addr, len)); +} + +void +ip4_fib_16_table_entry_insert (ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len, + fib_node_index_t fib_entry_index) +{ + return (ip4_fib_hash_table_entry_insert(&fib->hash, addr, len, fib_entry_index)); +} + +void +ip4_fib_16_table_entry_remove (ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len) +{ + return (ip4_fib_hash_table_entry_remove(&fib->hash, addr, len)); +} + +void +ip4_fib_16_table_fwding_dpo_update (ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len, + const dpo_id_t *dpo) +{ + ip4_mtrie_16_route_add(&fib->mtrie, addr, len, dpo->dpoi_index); +} + +void +ip4_fib_16_table_fwding_dpo_remove (ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len, + const dpo_id_t *dpo, + u32 cover_index) +{ + const fib_prefix_t *cover_prefix; + const dpo_id_t *cover_dpo; + + /* + * We need to pass the MTRIE the LB index and address length of the + * covering prefix, so it can fill the plys with the correct replacement + * for the entry being removed + */ + cover_prefix = fib_entry_get_prefix(cover_index); + cover_dpo = fib_entry_contribute_ip_forwarding(cover_index); + + ip4_mtrie_16_route_del(&fib->mtrie, + addr, len, dpo->dpoi_index, + cover_prefix->fp_len, + cover_dpo->dpoi_index); +} + +void +ip4_fib_16_table_walk (ip4_fib_16_t *fib, + fib_table_walk_fn_t fn, + void *ctx) +{ + ip4_fib_hash_table_walk(&fib->hash, fn, ctx); +} + +void +ip4_fib_16_table_sub_tree_walk (ip4_fib_16_t *fib, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx) +{ + ip4_fib_hash_table_sub_tree_walk(&fib->hash, root, fn, ctx); +} diff --git a/src/vnet/fib/ip4_fib_16.h b/src/vnet/fib/ip4_fib_16.h new file mode 100644 index 00000000000..b82ad57a04a --- /dev/null +++ b/src/vnet/fib/ip4_fib_16.h @@ -0,0 +1,106 @@ +/* + * Copyright (c) 2016 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** + * @brief The IPv4 FIB + * + * FIBs are composed of two prefix data-bases (akak tables). The non-forwarding + * table contains all the routes that the control plane has programmed, the + * forwarding table contains the sub-set of those routes that can be used to + * forward packets. + * In the IPv4 FIB the non-forwarding table is an array of hash tables indexed + * by mask length, the forwarding table is an mtrie + * + * This IPv4 FIB is used by the protocol independent FIB. So directly using + * this APIs in client code is not encouraged. However, this IPv4 FIB can be + * used if all the client wants is an IPv4 prefix data-base + */ + +#ifndef __IP4_FIB_16_H__ +#define __IP4_FIB_16_H__ + +#include <vnet/fib/ip4_fib_hash.h> +#include <vnet/ip/ip4_mtrie.h> + +typedef struct ip4_fib_16_t_ +{ + /** Required for pool_get_aligned */ + CLIB_CACHE_LINE_ALIGN_MARK(cacheline0); + + /** + * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes. + * First member so it's in the first cacheline. + */ + ip4_mtrie_16_t mtrie; + + /** + * The hash table DB + */ + ip4_fib_hash_t hash; +} ip4_fib_16_t; + +extern ip4_fib_16_t *ip4_fib_16s; + +extern fib_node_index_t ip4_fib_16_table_lookup(const ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len); +extern fib_node_index_t ip4_fib_16_table_lookup_exact_match(const ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len); + +extern void ip4_fib_16_table_entry_remove(ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len); + +extern void ip4_fib_16_table_entry_insert(ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len, + fib_node_index_t fib_entry_index); +extern void ip4_fib_16_table_free(ip4_fib_16_t *fib); +extern void ip4_fib_16_table_init(ip4_fib_16_t *fib); + +extern void ip4_fib_16_table_fwding_dpo_update(ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len, + const dpo_id_t *dpo); + +extern void ip4_fib_16_table_fwding_dpo_remove(ip4_fib_16_t *fib, + const ip4_address_t *addr, + u32 len, + const dpo_id_t *dpo, + fib_node_index_t cover_index); +extern u32 ip4_fib_16_table_lookup_lb (ip4_fib_16_t *fib, + const ip4_address_t * dst); + +/** + * @brief Walk all entries in a FIB table + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void ip4_fib_16_table_walk(ip4_fib_16_t *fib, + fib_table_walk_fn_t fn, + void *ctx); + +/** + * @brief Walk all entries in a sub-tree of the FIB table + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void ip4_fib_16_table_sub_tree_walk(ip4_fib_16_t *fib, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx); + +#endif + diff --git a/src/vnet/fib/ip4_fib_8.c b/src/vnet/fib/ip4_fib_8.c new file mode 100644 index 00000000000..587e28a8c9c --- /dev/null +++ b/src/vnet/fib/ip4_fib_8.c @@ -0,0 +1,137 @@ +/* + * Copyright (c) 2016 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <vnet/fib/fib_table.h> +#include <vnet/fib/fib_entry.h> +#include <vnet/fib/ip4_fib.h> + +ip4_fib_8_t *ip4_fib_8s; + +void +ip4_fib_8_table_init (ip4_fib_8_t *fib) +{ + ip4_mtrie_8_init(&fib->mtrie); +} + +void +ip4_fib_8_table_free (ip4_fib_8_t *fib) +{ + ip4_mtrie_8_free(&fib->mtrie); +} + +/* + * ip4_fib_8_table_lookup_exact_match + * + * Exact match prefix lookup + */ +fib_node_index_t +ip4_fib_8_table_lookup_exact_match (const ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len) +{ + return (ip4_fib_hash_table_lookup_exact_match(&fib->hash, addr, len)); +} + +/* + * ip4_fib_8_table_lookup_adj + * + * Longest prefix match + */ +index_t +ip4_fib_8_table_lookup_lb (ip4_fib_8_t *fib, + const ip4_address_t *addr) +{ + return (ip4_fib_hash_table_lookup_lb(&fib->hash, addr)); +} + +/* + * ip4_fib_8_table_lookup + * + * Longest prefix match + */ +fib_node_index_t +ip4_fib_8_table_lookup (const ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len) +{ + return (ip4_fib_hash_table_lookup(&fib->hash, addr, len)); +} + +void +ip4_fib_8_table_entry_insert (ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len, + fib_node_index_t fib_entry_index) +{ + return (ip4_fib_hash_table_entry_insert(&fib->hash, addr, len, fib_entry_index)); +} + +void +ip4_fib_8_table_entry_remove (ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len) +{ + return (ip4_fib_hash_table_entry_remove(&fib->hash, addr, len)); +} + +void +ip4_fib_8_table_fwding_dpo_update (ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len, + const dpo_id_t *dpo) +{ + ip4_mtrie_8_route_add(&fib->mtrie, addr, len, dpo->dpoi_index); +} + +void +ip4_fib_8_table_fwding_dpo_remove (ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len, + const dpo_id_t *dpo, + u32 cover_index) +{ + const fib_prefix_t *cover_prefix; + const dpo_id_t *cover_dpo; + + /* + * We need to pass the MTRIE the LB index and address length of the + * covering prefix, so it can fill the plys with the correct replacement + * for the entry being removed + */ + cover_prefix = fib_entry_get_prefix(cover_index); + cover_dpo = fib_entry_contribute_ip_forwarding(cover_index); + + ip4_mtrie_8_route_del(&fib->mtrie, + addr, len, dpo->dpoi_index, + cover_prefix->fp_len, + cover_dpo->dpoi_index); +} + +void +ip4_fib_8_table_walk (ip4_fib_8_t *fib, + fib_table_walk_fn_t fn, + void *ctx) +{ + ip4_fib_hash_table_walk(&fib->hash, fn, ctx); +} + +void +ip4_fib_8_table_sub_tree_walk (ip4_fib_8_t *fib, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx) +{ + ip4_fib_hash_table_sub_tree_walk(&fib->hash, root, fn, ctx); +} diff --git a/src/vnet/fib/ip4_fib_8.h b/src/vnet/fib/ip4_fib_8.h new file mode 100644 index 00000000000..0964f3ab133 --- /dev/null +++ b/src/vnet/fib/ip4_fib_8.h @@ -0,0 +1,106 @@ +/* + * Copyright (c) 2016 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** + * @brief The IPv4 FIB + * + * FIBs are composed of two prefix data-bases (akak tables). The non-forwarding + * table contains all the routes that the control plane has programmed, the + * forwarding table contains the sub-set of those routes that can be used to + * forward packets. + * In the IPv4 FIB the non-forwarding table is an array of hash tables indexed + * by mask length, the forwarding table is an mtrie + * + * This IPv4 FIB is used by the protocol independent FIB. So directly using + * this APIs in client code is not encouraged. However, this IPv4 FIB can be + * used if all the client wants is an IPv4 prefix data-base + */ + +#ifndef __IP4_FIB_8_H__ +#define __IP4_FIB_8_H__ + +#include <vnet/fib/ip4_fib_hash.h> +#include <vnet/ip/ip4_mtrie.h> + +typedef struct ip4_fib_8_t_ +{ + /** Required for pool_get_aligned */ + CLIB_CACHE_LINE_ALIGN_MARK(cacheline0); + + /** + * Mtrie for fast lookups. Hash is used to maintain overlapping prefixes. + * First member so it's in the first cacheline. + */ + ip4_mtrie_8_t mtrie; + + /** + * The hash table DB + */ + ip4_fib_hash_t hash; +} ip4_fib_8_t; + +extern ip4_fib_8_t *ip4_fib_8s; + +extern fib_node_index_t ip4_fib_8_table_lookup(const ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len); +extern fib_node_index_t ip4_fib_8_table_lookup_exact_match(const ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len); + +extern void ip4_fib_8_table_entry_remove(ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len); + +extern void ip4_fib_8_table_entry_insert(ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len, + fib_node_index_t fib_entry_index); +extern void ip4_fib_8_table_free(ip4_fib_8_t *fib); +extern void ip4_fib_8_table_init(ip4_fib_8_t *fib); + +extern void ip4_fib_8_table_fwding_dpo_update(ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len, + const dpo_id_t *dpo); + +extern void ip4_fib_8_table_fwding_dpo_remove(ip4_fib_8_t *fib, + const ip4_address_t *addr, + u32 len, + const dpo_id_t *dpo, + fib_node_index_t cover_index); +extern u32 ip4_fib_8_table_lookup_lb (ip4_fib_8_t *fib, + const ip4_address_t * dst); + +/** + * @brief Walk all entries in a FIB table + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void ip4_fib_8_table_walk(ip4_fib_8_t *fib, + fib_table_walk_fn_t fn, + void *ctx); + +/** + * @brief Walk all entries in a sub-tree of the FIB table + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void ip4_fib_8_table_sub_tree_walk(ip4_fib_8_t *fib, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx); + +#endif + diff --git a/src/vnet/fib/ip4_fib_hash.c b/src/vnet/fib/ip4_fib_hash.c new file mode 100644 index 00000000000..f42cf28f53e --- /dev/null +++ b/src/vnet/fib/ip4_fib_hash.c @@ -0,0 +1,249 @@ +/* + * Copyright (c) 2016 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <vnet/fib/fib_table.h> +#include <vnet/fib/fib_entry.h> +#include <vnet/fib/ip4_fib.h> + +/* + * ip4_fib_hash_table_lookup_exact_match + * + * Exact match prefix lookup + */ +fib_node_index_t +ip4_fib_hash_table_lookup_exact_match (const ip4_fib_hash_t *fib, + const ip4_address_t *addr, + u32 len) +{ + uword * hash, * result; + u32 key; + + hash = fib->fib_entry_by_dst_address[len]; + key = (addr->data_u32 & ip4_main.fib_masks[len]); + + result = hash_get(hash, key); + + if (NULL != result) { + return (result[0]); + } + return (FIB_NODE_INDEX_INVALID); +} + +/* + * ip4_fib_hash_table_lookup_adj + * + * Longest prefix match + */ +index_t +ip4_fib_hash_table_lookup_lb (const ip4_fib_hash_t *fib, + const ip4_address_t *addr) +{ + fib_node_index_t fei; + + fei = ip4_fib_hash_table_lookup(fib, addr, 32); + + if (FIB_NODE_INDEX_INVALID != fei) + { + const dpo_id_t *dpo; + + dpo = fib_entry_contribute_ip_forwarding(fei); + + return (dpo->dpoi_index); + } + return (INDEX_INVALID); +} + +/* + * ip4_fib_hash_table_lookup + * + * Longest prefix match + */ +fib_node_index_t +ip4_fib_hash_table_lookup (const ip4_fib_hash_t *fib, + const ip4_address_t *addr, + u32 len) +{ + uword * hash, * result; + i32 mask_len; + u32 key; + + for (mask_len = len; mask_len >= 0; mask_len--) + { + hash = fib->fib_entry_by_dst_address[mask_len]; + key = (addr->data_u32 & ip4_main.fib_masks[mask_len]); + + result = hash_get (hash, key); + + if (NULL != result) { + return (result[0]); + } + } + return (FIB_NODE_INDEX_INVALID); +} + +void +ip4_fib_hash_table_entry_insert (ip4_fib_hash_t *fib, + const ip4_address_t *addr, + u32 len, + fib_node_index_t fib_entry_index) +{ + uword * hash, * result; + u32 key; + + key = (addr->data_u32 & ip4_main.fib_masks[len]); + hash = fib->fib_entry_by_dst_address[len]; + result = hash_get (hash, key); + + if (NULL == result) { + /* + * adding a new entry + */ + + if (NULL == hash) { + hash = hash_create (32 /* elts */, sizeof (uword)); + hash_set_flags (hash, HASH_FLAG_NO_AUTO_SHRINK); + + } + hash = hash_set(hash, key, fib_entry_index); + fib->fib_entry_by_dst_address[len] = hash; + } + else + { + ASSERT(0); + } +} + +void +ip4_fib_hash_table_entry_remove (ip4_fib_hash_t *fib, + const ip4_address_t *addr, + u32 len) +{ + uword * hash, * result; + u32 key; + + key = (addr->data_u32 & ip4_main.fib_masks[len]); + hash = fib->fib_entry_by_dst_address[len]; + result = hash_get (hash, key); + + if (NULL == result) + { + /* + * removing a non-existent entry. i'll allow it. + */ + } + else + { + hash_unset(hash, key); + } + + fib->fib_entry_by_dst_address[len] = hash; +} + +void +ip4_fib_hash_table_walk (ip4_fib_hash_t *fib, + fib_table_walk_fn_t fn, + void *ctx) +{ + fib_prefix_t root = { + .fp_proto = FIB_PROTOCOL_IP4, + // address and length default to all 0 + }; + + /* + * A full tree walk is the dengenerate case of a sub-tree from + * the very root + */ + return (ip4_fib_hash_table_sub_tree_walk(fib, &root, fn, ctx)); +} + +void +ip4_fib_hash_table_sub_tree_walk (ip4_fib_hash_t *fib, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx) +{ + fib_prefix_t *sub_trees = NULL; + int i; + + /* + * There is no efficient way to walk this array of hash tables. + * so we walk each table with a mask length greater than and equal to + * the required root and check it is covered by the root. + */ + for (i = root->fp_len; + i < ARRAY_LEN (fib->fib_entry_by_dst_address); + i++) + { + uword * hash = fib->fib_entry_by_dst_address[i]; + + if (NULL != hash) + { + ip4_address_t key; + hash_pair_t * p; + + hash_foreach_pair (p, hash, + ({ + key.as_u32 = p->key; + if (ip4_destination_matches_route(&ip4_main, + &key, + &root->fp_addr.ip4, + 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, sub_trees) + { + if (ip4_destination_matches_route(&ip4_main, + &key, + &sub_tree->fp_addr.ip4, + sub_tree->fp_len)) + { + skip = 1; + break; + } + } + + if (!skip) + { + switch (fn(p->value[0], ctx)) + { + case FIB_TABLE_WALK_CONTINUE: + break; + case FIB_TABLE_WALK_SUB_TREE_STOP: { + fib_prefix_t pfx = { + .fp_proto = FIB_PROTOCOL_IP4, + .fp_len = i, + .fp_addr.ip4 = key, + }; + vec_add1(sub_trees, pfx); + break; + } + case FIB_TABLE_WALK_STOP: + goto done; + } + } + } + })); + } + } +done: + vec_free(sub_trees); + return; +} + diff --git a/src/vnet/fib/ip4_fib_hash.h b/src/vnet/fib/ip4_fib_hash.h new file mode 100644 index 00000000000..84b3b9ae834 --- /dev/null +++ b/src/vnet/fib/ip4_fib_hash.h @@ -0,0 +1,74 @@ +/* + * Copyright (c) 2016 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +/** + * @brief The IPv4 FIB Hash table + */ + +#ifndef __IP4_FIB_HASH_H__ +#define __IP4_FIB_HASH_H__ + +#include <vlib/vlib.h> +#include <vnet/ip/ip.h> + +typedef struct ip4_fib_hash_t_ +{ + /* Hash table for each prefix length mapping. */ + uword *fib_entry_by_dst_address[33]; + + /* Table ID (hash key) for this FIB. */ + u32 table_id; +} ip4_fib_hash_t; + +extern fib_node_index_t ip4_fib_hash_table_lookup(const ip4_fib_hash_t *fib, + const ip4_address_t *addr, + u32 len); +extern index_t ip4_fib_hash_table_lookup_lb(const ip4_fib_hash_t *fib, + const ip4_address_t *addr); +extern fib_node_index_t ip4_fib_hash_table_lookup_exact_match(const ip4_fib_hash_t *fib, + const ip4_address_t *addr, + u32 len); + +extern void ip4_fib_hash_table_entry_remove(ip4_fib_hash_t *fib, + const ip4_address_t *addr, + u32 len); + +extern void ip4_fib_hash_table_entry_insert(ip4_fib_hash_t *fib, + const ip4_address_t *addr, + u32 len, + fib_node_index_t fib_entry_index); +extern void ip4_fib_hash_table_init(ip4_fib_hash_t *fib); +extern void ip4_fib_hash_table_destroy(ip4_fib_hash_t *fib); + +/** + * @brief Walk all entries in a FIB table + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void ip4_fib_hash_table_walk(ip4_fib_hash_t *fib, + fib_table_walk_fn_t fn, + void *ctx); + +/** + * @brief Walk all entries in a sub-tree of the FIB table + * N.B: This is NOT safe to deletes. If you need to delete walk the whole + * table and store elements in a vector, then delete the elements + */ +extern void ip4_fib_hash_table_sub_tree_walk(ip4_fib_hash_t *fib, + const fib_prefix_t *root, + fib_table_walk_fn_t fn, + void *ctx); + +#endif + |