diff options
Diffstat (limited to 'vnet/vnet/fib/ip6_fib.c')
-rw-r--r-- | vnet/vnet/fib/ip6_fib.c | 698 |
1 files changed, 698 insertions, 0 deletions
diff --git a/vnet/vnet/fib/ip6_fib.c b/vnet/vnet/fib/ip6_fib.c new file mode 100644 index 00000000000..772ce74430b --- /dev/null +++ b/vnet/vnet/fib/ip6_fib.c @@ -0,0 +1,698 @@ +/* + * 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/ip6_fib.h> +#include <vnet/fib/fib_table.h> + +static void +vnet_ip6_fib_init (u32 fib_index) +{ + fib_prefix_t pfx = { + .fp_proto = FIB_PROTOCOL_IP6, + .fp_len = 0, + .fp_addr = { + .ip6 = { + { 0, 0, }, + }, + } + }; + + /* + * Add the default route. + */ + fib_table_entry_special_add(fib_index, + &pfx, + FIB_SOURCE_DEFAULT_ROUTE, + FIB_ENTRY_FLAG_DROP, + ADJ_INDEX_INVALID); + + /* + * Add ff02::1:ff00:0/104 via local route for all tables. + * This is required for neighbor discovery to work. + */ + ip6_set_solicited_node_multicast_address(&pfx.fp_addr.ip6, 0); + pfx.fp_len = 104; + fib_table_entry_special_add(fib_index, + &pfx, + FIB_SOURCE_SPECIAL, + FIB_ENTRY_FLAG_LOCAL, + ADJ_INDEX_INVALID); + + /* + * Add all-routers multicast address via local route for all tables + */ + ip6_set_reserved_multicast_address (&pfx.fp_addr.ip6, + IP6_MULTICAST_SCOPE_link_local, + IP6_MULTICAST_GROUP_ID_all_routers); + pfx.fp_len = 128; + fib_table_entry_special_add(fib_index, + &pfx, + FIB_SOURCE_SPECIAL, + FIB_ENTRY_FLAG_LOCAL, + ADJ_INDEX_INVALID); + + /* + * Add all-nodes multicast address via local route for all tables + */ + ip6_set_reserved_multicast_address (&pfx.fp_addr.ip6, + IP6_MULTICAST_SCOPE_link_local, + IP6_MULTICAST_GROUP_ID_all_hosts); + pfx.fp_len = 128; + fib_table_entry_special_add(fib_index, + &pfx, + FIB_SOURCE_SPECIAL, + FIB_ENTRY_FLAG_LOCAL, + ADJ_INDEX_INVALID); + + /* + * Add all-mldv2 multicast address via local route for all tables + */ + ip6_set_reserved_multicast_address (&pfx.fp_addr.ip6, + IP6_MULTICAST_SCOPE_link_local, + IP6_MULTICAST_GROUP_ID_mldv2_routers); + pfx.fp_len = 128; + fib_table_entry_special_add(fib_index, + &pfx, + FIB_SOURCE_SPECIAL, + FIB_ENTRY_FLAG_LOCAL, + ADJ_INDEX_INVALID); + + /* + * all link local for us + */ + pfx.fp_addr.ip6.as_u64[0] = clib_host_to_net_u64 (0xFE80000000000000ULL); + pfx.fp_addr.ip6.as_u64[1] = 0; + pfx.fp_len = 10; + fib_table_entry_special_add(fib_index, + &pfx, + FIB_SOURCE_SPECIAL, + FIB_ENTRY_FLAG_LOCAL, + ADJ_INDEX_INVALID); +} + +static u32 +create_fib_with_table_id (u32 table_id) +{ + fib_table_t *fib_table; + + pool_get_aligned(ip6_main.fibs, fib_table, CLIB_CACHE_LINE_BYTES); + memset(fib_table, 0, sizeof(*fib_table)); + + fib_table->ft_proto = FIB_PROTOCOL_IP6; + fib_table->ft_index = + fib_table->v6.index = + (fib_table - ip6_main.fibs); + + hash_set(ip6_main.fib_index_by_table_id, table_id, fib_table->ft_index); + + fib_table->ft_table_id = + fib_table->v6.table_id = + table_id; + fib_table->ft_flow_hash_config = + fib_table->v6.flow_hash_config = + IP_FLOW_HASH_DEFAULT; + + vnet_ip6_fib_init(fib_table->ft_index); + fib_table_lock(fib_table->ft_index, FIB_PROTOCOL_IP6); + + return (fib_table->ft_index); +} + +u32 +ip6_fib_table_find_or_create_and_lock (u32 table_id) +{ + uword * p; + + p = hash_get (ip6_main.fib_index_by_table_id, table_id); + if (NULL == p) + return create_fib_with_table_id(table_id); + + fib_table_lock(p[0], FIB_PROTOCOL_IP6); + + return (p[0]); +} + +u32 +ip6_fib_table_create_and_lock (void) +{ + return (create_fib_with_table_id(~0)); +} + +void +ip6_fib_table_destroy (u32 fib_index) +{ + fib_prefix_t pfx = { + .fp_proto = FIB_PROTOCOL_IP6, + .fp_len = 0, + .fp_addr = { + .ip6 = { + { 0, 0, }, + }, + } + }; + + /* + * the default route. + */ + fib_table_entry_special_remove(fib_index, + &pfx, + FIB_SOURCE_DEFAULT_ROUTE); + + + /* + * ff02::1:ff00:0/104 + */ + ip6_set_solicited_node_multicast_address(&pfx.fp_addr.ip6, 0); + pfx.fp_len = 104; + fib_table_entry_special_remove(fib_index, + &pfx, + FIB_SOURCE_SPECIAL); + + /* + * all-routers multicast address + */ + ip6_set_reserved_multicast_address (&pfx.fp_addr.ip6, + IP6_MULTICAST_SCOPE_link_local, + IP6_MULTICAST_GROUP_ID_all_routers); + pfx.fp_len = 128; + fib_table_entry_special_remove(fib_index, + &pfx, + FIB_SOURCE_SPECIAL); + + /* + * all-nodes multicast address + */ + ip6_set_reserved_multicast_address (&pfx.fp_addr.ip6, + IP6_MULTICAST_SCOPE_link_local, + IP6_MULTICAST_GROUP_ID_all_hosts); + pfx.fp_len = 128; + fib_table_entry_special_remove(fib_index, + &pfx, + FIB_SOURCE_SPECIAL); + + /* + * all-mldv2 multicast address + */ + ip6_set_reserved_multicast_address (&pfx.fp_addr.ip6, + IP6_MULTICAST_SCOPE_link_local, + IP6_MULTICAST_GROUP_ID_mldv2_routers); + pfx.fp_len = 128; + fib_table_entry_special_remove(fib_index, + &pfx, + FIB_SOURCE_SPECIAL); + + /* + * all link local + */ + pfx.fp_addr.ip6.as_u64[0] = clib_host_to_net_u64 (0xFE80000000000000ULL); + pfx.fp_addr.ip6.as_u64[1] = 0; + pfx.fp_len = 10; + fib_table_entry_special_remove(fib_index, + &pfx, + FIB_SOURCE_SPECIAL); + + fib_table_t *fib_table = fib_table_get(fib_index, FIB_PROTOCOL_IP6); + fib_source_t source; + + /* + * validate no more routes. + */ + ASSERT(0 == fib_table->ft_total_route_counts); + FOR_EACH_FIB_SOURCE(source) + { + ASSERT(0 == fib_table->ft_src_route_counts[source]); + } + + if (~0 != fib_table->ft_table_id) + { + hash_unset (ip6_main.fib_index_by_table_id, fib_table->ft_table_id); + } + pool_put(ip6_main.fibs, fib_table); +} + +fib_node_index_t +ip6_fib_table_lookup (u32 fib_index, + const ip6_address_t *addr, + u32 len) +{ + const ip6_fib_table_instance_t *table; + BVT(clib_bihash_kv) kv, value; + int i, n_p, rv; + u64 fib; + + table = &ip6_main.ip6_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); + + /* + * 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) + { + i++; + } + + 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 = BV(clib_bihash_search_inline_2)(&table->ip6_hash, &kv, &value); + if (rv == 0) + return value.value; + } + + return (FIB_NODE_INDEX_INVALID); +} + +fib_node_index_t +ip6_fib_table_lookup_exact_match (u32 fib_index, + const ip6_address_t *addr, + u32 len) +{ + const ip6_fib_table_instance_t *table; + BVT(clib_bihash_kv) kv, value; + ip6_address_t *mask; + u64 fib; + int rv; + + table = &ip6_main.ip6_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 = BV(clib_bihash_search_inline_2)(&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) +{ + int i; + vec_reset_length (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(table->prefix_lengths_in_search_order, dst_address_length); + })); +} + +void +ip6_fib_table_entry_remove (u32 fib_index, + const ip6_address_t *addr, + u32 len) +{ + ip6_fib_table_instance_t *table; + BVT(clib_bihash_kv) kv; + ip6_address_t *mask; + u64 fib; + + table = &ip6_main.ip6_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; + + BV(clib_bihash_add_del)(&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); + } +} + +void +ip6_fib_table_entry_insert (u32 fib_index, + const ip6_address_t *addr, + u32 len, + fib_node_index_t fib_entry_index) +{ + ip6_fib_table_instance_t *table; + BVT(clib_bihash_kv) kv; + ip6_address_t *mask; + u64 fib; + + table = &ip6_main.ip6_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; + + BV(clib_bihash_add_del)(&table->ip6_hash, &kv, 1); + + 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); +} + +u32 +ip6_fib_table_fwding_lookup (ip6_main_t * im, + u32 fib_index, + const ip6_address_t * dst) +{ + const ip6_fib_table_instance_t *table; + int i, len; + int rv; + BVT(clib_bihash_kv) kv, value; + u64 fib; + + table = &ip6_main.ip6_table[IP6_FIB_TABLE_FWDING]; + len = vec_len (table->prefix_lengths_in_search_order); + + kv.key[0] = dst->as_u64[0]; + kv.key[1] = dst->as_u64[1]; + fib = ((u64)((fib_index))<<32); + + for (i = 0; i < len; 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 = BV(clib_bihash_search_inline_2)(&table->ip6_hash, &kv, &value); + if (rv == 0) + return value.value; + } + + /* default route is always present */ + ASSERT(0); + return 0; +} + +u32 ip6_fib_table_fwding_lookup_with_if_index (ip6_main_t * im, + u32 sw_if_index, + const ip6_address_t * dst) +{ + u32 fib_index = vec_elt (im->fib_index_by_sw_if_index, sw_if_index); + return ip6_fib_table_fwding_lookup(im, fib_index, dst); +} + +flow_hash_config_t +ip6_fib_table_get_flow_hash_config (u32 fib_index) +{ + return (ip6_fib_get(fib_index)->flow_hash_config); +} + +u32 +ip6_fib_table_get_index_for_sw_if_index (u32 sw_if_index) +{ + if (sw_if_index >= vec_len(ip6_main.fib_index_by_sw_if_index)) + { + /* + * This is the case for interfaces that are not yet mapped to + * a IP table + */ + return (~0); + } + return (ip6_main.fib_index_by_sw_if_index[sw_if_index]); +} + +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; + BVT(clib_bihash_kv) kv; + ip6_address_t *mask; + u64 fib; + + table = &ip6_main.ip6_table[IP6_FIB_TABLE_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 = dpo->dpoi_index; + + BV(clib_bihash_add_del)(&table->ip6_hash, &kv, 1); + + 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); +} + +void +ip6_fib_table_fwding_dpo_remove (u32 fib_index, + const ip6_address_t *addr, + u32 len, + const dpo_id_t *dpo) +{ + ip6_fib_table_instance_t *table; + BVT(clib_bihash_kv) kv; + ip6_address_t *mask; + u64 fib; + + table = &ip6_main.ip6_table[IP6_FIB_TABLE_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 = dpo->dpoi_index; + + BV(clib_bihash_add_del)(&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); + } +} + +typedef struct ip6_fib_show_ctx_t_ { + u32 fib_index; + fib_node_index_t *entries; +} ip6_fib_show_ctx_t; + +static void +ip6_fib_table_collect_entries (clib_bihash_kv_24_8_t * kvp, + void *arg) +{ + ip6_fib_show_ctx_t *ctx = arg; + + if ((kvp->key[2] >> 32) == ctx->fib_index) + { + vec_add1(ctx->entries, kvp->value); + } +} + +static void +ip6_fib_table_show_all (ip6_fib_t *fib, + vlib_main_t * vm) +{ + fib_node_index_t *fib_entry_index; + ip6_fib_show_ctx_t ctx = { + .fib_index = fib->index, + .entries = NULL, + }; + ip6_main_t *im = &ip6_main; + + BV(clib_bihash_foreach_key_value_pair)(&im->ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash, + ip6_fib_table_collect_entries, + &ctx); + + vec_sort_with_function(ctx.entries, fib_entry_cmp_for_sort); + + vec_foreach(fib_entry_index, ctx.entries) + { + vlib_cli_output(vm, "%U", + format_fib_entry, + *fib_entry_index, + FIB_ENTRY_FORMAT_BRIEF); + } + + vec_free(ctx.entries); +} + +static void +ip6_fib_table_show_one (ip6_fib_t *fib, + vlib_main_t * vm, + ip6_address_t *address, + u32 mask_len) +{ + vlib_cli_output(vm, "%U", + format_fib_entry, + ip6_fib_table_lookup(fib->index, address, mask_len), + FIB_ENTRY_FORMAT_DETAIL); +} + +typedef struct { + u32 fib_index; + u64 count_by_prefix_length[129]; +} count_routes_in_fib_at_prefix_length_arg_t; + +static void count_routes_in_fib_at_prefix_length +(BVT(clib_bihash_kv) * kvp, void *arg) +{ + count_routes_in_fib_at_prefix_length_arg_t * ap = arg; + int mask_width; + + if ((kvp->key[2]>>32) != ap->fib_index) + return; + + mask_width = kvp->key[2] & 0xFF; + + ap->count_by_prefix_length[mask_width]++; +} + +static clib_error_t * +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; + int verbose, matching; + ip6_address_t matching_address; + u32 mask_len = 128; + int table_id = -1, fib_index = ~0; + + verbose = 1; + matching = 0; + + while (unformat_check_input (input) != UNFORMAT_END_OF_INPUT) + { + if (unformat (input, "brief") || + unformat (input, "summary") || + unformat (input, "sum")) + verbose = 0; + + else if (unformat (input, "%U/%d", + unformat_ip6_address, &matching_address, &mask_len)) + matching = 1; + + else if (unformat (input, "%U", unformat_ip6_address, &matching_address)) + matching = 1; + + else if (unformat (input, "table %d", &table_id)) + ; + else if (unformat (input, "index %d", &fib_index)) + ; + else + break; + } + + pool_foreach (fib_table, im6->fibs, + ({ + fib = &(fib_table->v6); + if (table_id >= 0 && table_id != (int)fib->table_id) + continue; + if (fib_index != ~0 && fib_index != (int)fib->index) + continue; + + vlib_cli_output (vm, "%s, fib_index %d, flow hash: %U", + fib_table->ft_desc, fib->index, + format_ip_flow_hash_config, fib->flow_hash_config); + + /* Show summary? */ + if (! verbose) + { + BVT(clib_bihash) * h = &im6->ip6_table[IP6_FIB_TABLE_NON_FWDING].ip6_hash; + int len; + + vlib_cli_output (vm, "%=20s%=16s", "Prefix length", "Count"); + + memset (ca, 0, sizeof(*ca)); + ca->fib_index = fib->index; + + BV(clib_bihash_foreach_key_value_pair) + (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; + } + + if (!matching) + { + ip6_fib_table_show_all(fib, vm); + } + else + { + ip6_fib_table_show_one(fib, vm, &matching_address, mask_len); + } + })); + + return 0; +} + +/*? + * Show FIB6/route entries + * + * @cliexpar + * @cliexstart{show ip fib} + * Display the IPv6 FIB. + * This command will run for a long time when the FIBs comprise millions of entries. + * See 'show ip fib' + * @cliexend + ?*/ +VLIB_CLI_COMMAND (ip6_show_fib_command, static) = { + .path = "show ip6 fib", + .short_help = "show ip6 fib [summary] [table <n>] [<ip6-addr>] [verboase]", + .function = ip6_show_fib, +}; |