diff options
Diffstat (limited to 'cicn-plugin/cicn/cicn_fib.c')
| -rw-r--r-- | cicn-plugin/cicn/cicn_fib.c | 798 |
1 files changed, 798 insertions, 0 deletions
diff --git a/cicn-plugin/cicn/cicn_fib.c b/cicn-plugin/cicn/cicn_fib.c new file mode 100644 index 00000000..a8e1e642 --- /dev/null +++ b/cicn-plugin/cicn/cicn_fib.c @@ -0,0 +1,798 @@ +/* + * Copyright (c) 2017 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. + */ +/* + * cicn_fib.c: Fast-path, vpp-aware FIB, used in the cicn forwarder. + */ + +#include <vlib/vlib.h> + +#include <cicn/cicn.h> +#include <cicn/cicn_fib.h> + +/* + * Init/alloc a new FIB + */ +int +cicn_fib_create (cicn_fib_t * p, uint32_t num_elems) +{ + int ret; + + ret = + cicn_hashtb_alloc (&p->fib_table, num_elems, sizeof (cicn_fib_entry_t)); + if (ret == AOK) + { + /* Reserve last entry in a row/bucket for overflow, to make + * unsynchronized FIB modifications easier. + */ + p->fib_table->ht_flags |= CICN_HASHTB_FLAG_USE_SEVEN; + p->fib_table->ht_flags |= CICN_HASHTB_FLAG_KEY_FMT_PFX; + + p->fib_flags = CICN_FIB_FLAGS_NONE; + + p->fib_capacity = num_elems; + + p->fib_max_comps = 0; + memset (&(p->fib_default_entry), 0, sizeof (cicn_fib_entry_t)); + } + + return (ret); +} + +/* + * FIB lookup using 'pfxhash' struct containing prefix-hash results. This returns + * the longest matching entry (not a virtual entry). If there is no valid FIB + * match and a default FIB entry exists, the default is returned. + */ +int +cicn_fib_lookup (cicn_fib_t * fib, const cicn_prefix_hashinf_t * pfxhash, + cicn_fib_entry_t ** pentry) +{ + int found_p, i, ret = EINVAL; + cicn_hash_node_t *node = NULL; + cicn_fib_entry_t *fe; + + if ((fib == NULL) || (pfxhash == NULL) || (pfxhash->pfx_ptr == NULL) || + (pfxhash->pfx_len == 0) || + (pfxhash->pfx_count > CICN_HASHTB_MAX_NAME_COMPS) || (pentry == NULL)) + { + + goto done; + } + + found_p = FALSE; + + /* If we have a default entry, start with that */ + if (fib->fib_flags & CICN_FIB_FLAG_DEFAULT_SET) + { + *pentry = &fib->fib_default_entry; + + /* And we have some form of success... */ + found_p = TRUE; + } + + /* + * TODO -- souped-up, thoughtful walk through the prefixes, optimized + * to start 'in the middle' and then walk 'up' or 'down' depending on + * what we find. For now, just simple iteration... + */ + + /* + * Iterate through the prefix hashes, looking for the longest match + */ + for (i = 0; i < pfxhash->pfx_count; i++) + { + ret = cicn_hashtb_lookup_node (fib->fib_table, + pfxhash->pfx_ptr, + pfxhash->pfx_lens[i], + pfxhash->pfx_hashes[i], &node); + if (ret == AOK) + { + fe = cicn_fib_get_data (node); + + /* Don't use a 'virtual' entry */ + if (fe->fe_flags & CICN_FIB_ENTRY_FLAG_VIRTUAL) + { + continue; + } + + /* Best match so far */ + *pentry = fe; + found_p = TRUE; + + } + else + { + /* No more possible longer prefixes */ + break; + } + } + + if (found_p) + { + ret = AOK; + } + +done: + + return (ret); +} + +/* + * Insert a new prefix into the FIB (or add an additional next-hop, + * if the prefix already exists, or mod an existing next-hop, if the + * next-hop already exists.) We expect that 'pfx' is the start of the + * name-components only, not the start of a complete 'name' TLV. We expect + * that the prefix-hashing has already been done, into 'pfxhash'. + */ +int +cicn_fib_entry_insert (cicn_fib_t * fib, + const cicn_prefix_hashinf_t * pfxhash, + uint16_t faceid, uint8_t weight, cicn_rd_t * cicn_rd) +{ + int ret = EINVAL; + cicn_rc_e crc = CICN_RC_OK; + int i, j; + cicn_hash_node_t *node_array[CICN_HASHTB_MAX_NAME_COMPS]; + int node_count = 0; + cicn_hash_node_t *pnode; + cicn_fib_entry_t *fe; + int add_ref_val = 0; + + if ((fib == NULL) || (pfxhash == NULL) || (pfxhash->pfx_ptr == NULL) || + (pfxhash->pfx_len == 0) || (pfxhash->pfx_count == 0)) + { + goto done; + } + if (pfxhash->pfx_count > CICN_HASHTB_MAX_NAME_COMPS || + pfxhash->pfx_overflow) + { + crc = CICN_RC_FIB_PFX_COMP_LIMIT; + goto done; + } + + /* Start walking down the series of intermediate prefixes, + * capturing the hash node at each level that already exists. We need + * this in order to manage internal state, like refcounts + * and virtual FIB nodes. + */ + for (i = 0; i < pfxhash->pfx_count; i++) + { + ret = cicn_hashtb_lookup_node (fib->fib_table, + pfxhash->pfx_ptr, + pfxhash->pfx_lens[i], + pfxhash->pfx_hashes[i], &pnode); + if (ret != AOK) + { // this component and beneath not present + break; + } + node_array[node_count] = pnode; + node_count++; + } + + /* Now we've reached either a) the point where parents of the offered + * prefix end, or b) the entry for the offered prefix. + */ + while (i < pfxhash->pfx_count) + { + /* + * There are more components in 'pfx' than are in the existing + * fib. We need to add one or more entries, probably virtual. + */ + + /* Allocate a new node */ + pnode = cicn_hashtb_alloc_node (fib->fib_table); + if (pnode == NULL) + { + /* TODO -- clean up any new virtual nodes we've added! */ + ret = ENOMEM; + goto done; + } + + /* Set up the embedded virtual fib entry */ + fe = cicn_fib_get_data (pnode); + + /* Clear out the new entry */ + memset (fe, 0, sizeof (cicn_fib_entry_t)); + + fe->fe_flags = CICN_FIB_ENTRY_FLAG_VIRTUAL; + + /* Set up the hash node */ + cicn_hashtb_init_node (fib->fib_table, pnode, + pfxhash->pfx_hashes[i], + pfxhash->pfx_ptr, pfxhash->pfx_lens[i]); + + /* Insert into the hashtable */ + ret = cicn_hashtb_insert (fib->fib_table, pnode); + if (ret != AOK) + { + /* Whoa - we didn't expect that */ + goto done; + /* TODO -- cleanup on error */ + } + + /* + * Save new nodes in the array too. + */ + ASSERT (node_count < (CICN_HASHTB_MAX_NAME_COMPS - 1)); + node_array[node_count] = pnode; + + node_count++; + i++; + + /* Count each added 'level' of prefixes */ + add_ref_val++; + } + + /* + * At this point, we've either found or added a new entry node, + * it's the last one in the array of nodes, and we're ready + * to set it up. If it's valid, we'll walk back + * through the parents and update them (refcount, max-comps, etc.) + */ + ASSERT (node_count > 0); + pnode = node_array[node_count - 1]; + + /* Set up (or update) the embedded actual fib entry */ + fe = cicn_fib_get_data (pnode); + + /* If this was an existing _virtual_ entry, convert it to a real one */ + fe->fe_flags &= ~(CICN_FIB_ENTRY_FLAG_VIRTUAL | + CICN_FIB_ENTRY_FLAG_DELETED); + + /* Next-hop face and weight. We'll _update_ a next-hop that matches + * the current face, or else we'll add a new next-hop. + */ + for (i = 0; i < ARRAY_LEN (fe->fe_next_hops); i++) + { + if (fe->fe_next_hops[i].nh_faceid == faceid) + { + if (fe->fe_next_hops[i].nh_weight == weight) + { + ret = EEXIST; + goto done; + } + + /* Found a matching entry */ + fe->fe_next_hops[i].nh_weight = weight; + break; + } + } + + if (i == ARRAY_LEN (fe->fe_next_hops)) + { + /* Didn't find a match, try to find a free nh slot */ + for (i = 0; i < ARRAY_LEN (fe->fe_next_hops); i++) + { + cicn_fib_entry_nh_t *fe_nh = &fe->fe_next_hops[i]; + if (fe->fe_next_hops[i].nh_faceid != 0) + { + continue; + } + /* Found a free entry */ + ret = cicn_face_fib_nh_cnt_update (faceid, 1 /*add */ ); + if (ret != AOK) + { // should not happen + break; + } + fe_nh->nh_faceid = faceid; + fe_nh->nh_weight = weight; + break; + } + if (i == ARRAY_LEN (fe->fe_next_hops)) + { + /* Whoops - can't add any more next-hops */ + /* TODO -- clean up on error at this point, since we may have added + * virtual nodes. + */ + ret = ENOSPC; + crc = CICN_RC_FIB_NHOP_LIMIT; + goto done; + } + } + + + /* Max comps */ + if (pfxhash->pfx_count > fe->fe_max_comps) + { + fe->fe_max_comps = pfxhash->pfx_count; + } + + /* + * Loop back through the nodes, updating the refcounts, max-comps, etc. + */ + for (i = node_count - 1, j = 1; i >= 0; i--, j++) + { + pnode = node_array[i]; + + fe = cicn_fib_get_data (pnode); + + /* + * Update refcounts if we added any new prefixes. + */ + if (add_ref_val > 0) + { + + /* Add refs to all the new nodes */ + if (j < add_ref_val) + { + fe->fe_refcount += j; + } + else + { + /* Add refs for all the new nodes to existing parents */ + fe->fe_refcount += add_ref_val; + } + } + + if (pfxhash->pfx_count > fe->fe_max_comps) + { + fe->fe_max_comps = pfxhash->pfx_count; + } + } + + ret = AOK; + +done: + if (cicn_rd) + { + cicn_rd_set (cicn_rd, crc, ret); + } + + return (ret); +} + +/* + * Delete a FIB prefix, or just delete a next-hop, if 'faceid' != 0. + * If the prefix has children, this may just result in the conversion of + * the entry into a virtual entry. + * We expect that the prefix-hashing has already been done, into 'pfxhash'. + */ +int +cicn_fib_entry_delete (cicn_fib_t * fib, + const cicn_prefix_hashinf_t * pfxhash, uint16_t faceid) +{ + int i, counter, ret = EINVAL; + cicn_hash_node_t *node_array[CICN_HASHTB_MAX_NAME_COMPS]; + int node_count = 0; + cicn_hash_node_t *pnode; + cicn_fib_entry_t *fe; + + if ((fib == NULL) || (pfxhash == NULL) || + (pfxhash->pfx_ptr == NULL) || (pfxhash->pfx_len == 0) || + (pfxhash->pfx_count == 0) || + (pfxhash->pfx_count > CICN_HASHTB_MAX_NAME_COMPS)) + { + goto done; + } + + /* Start walking down the series of intermediate prefixes, + * capturing the hash node at each level that already exists. We need + * this in order to manage internal state, like refcounts + * and virtual FIB nodes. We use the extended 'lookup' api so that we + * will see hashtable nodes that were marked for deletion. + */ + for (i = 0; i < pfxhash->pfx_count; i++) + { + ret = cicn_hashtb_lookup_node_ex (fib->fib_table, + pfxhash->pfx_ptr, + pfxhash->pfx_lens[i], + pfxhash->pfx_hashes[i], TRUE, &pnode); + if (ret != AOK) + { // should not happen + break; + } + node_array[i] = pnode; + } + + /* + * Now we've reached either a) the entry for the offered prefix, or the end + * of the bread-crumb trail... + */ + if (i < pfxhash->pfx_count) + { + /* If we can't get to the prefix specified, + * then we can't really proceed? + */ + ret = ENOENT; + goto done; + } + + node_count = i; + pnode = node_array[node_count - 1]; // first update actual node, then parents + fe = cicn_fib_get_data (pnode); + + /* + * If we're clearing a single next-hop, see whether we should remove the + * whole entry. 'pnode' is the last node in the array, which should be + * the target entry. + */ + if (faceid != 0) + { + counter = 0; + ret = ENOENT; + + for (i = 0; i < ARRAY_LEN (fe->fe_next_hops); i++) + { + cicn_fib_entry_nh_t *fe_nh = &fe->fe_next_hops[i]; + + /* Remove the specific next-hop */ + if (fe_nh->nh_faceid == faceid) + { + cicn_face_fib_nh_cnt_update (faceid, 0 /*!add */ ); + fe_nh->nh_faceid = 0; + + /* Return success if we find the specified next-hop */ + ret = AOK; + } + + /* Count all existing next-hops */ + if (fe_nh->nh_faceid != 0) + { + counter++; + } + } + + if (counter != 0) + { + /* Remove entire entry if no next-hops remaining */ + goto done; + } + } + + /* + * Remove entry if it's a leaf, or convert it to 'virtual' if not. + */ + + /* First clear out next-hop(s) */ + for (i = 0; i < ARRAY_LEN (fe->fe_next_hops); i++) + { + cicn_fib_entry_nh_t *fe_nh = &fe->fe_next_hops[i]; + + if (fe_nh->nh_faceid == 0) + { + continue; + } + cicn_face_fib_nh_cnt_update (fe_nh->nh_faceid, 0 /*!add */ ); + fe_nh->nh_faceid = 0; + } + + if (fe->fe_refcount > 1) + { + /* Convert to virtual entry in-place */ + + /* Set the 'virtual' flag */ + fe->fe_flags |= CICN_FIB_ENTRY_FLAG_VIRTUAL; + + /* No changes to parents, since we aren't changing the internal + * prefix structure, so we're done. + */ + ret = AOK; + goto done; + + } + else + { + /* Remove entry entirely */ + ret = cicn_hashtb_delete (fib->fib_table, &pnode); + pnode = NULL; + } + + + /* + * We've removed a node: loop back through the parents, + * updating the refcounts, max-comps, etc. We may decide to remove + * parent nodes too, if their only descendent has been deleted. + */ + counter = 1; + for (i = node_count - 2; i >= 0; i--) + { + pnode = node_array[i]; + + fe = cicn_fib_get_data (pnode); + + fe->fe_refcount -= counter; + + /* TODO -- figure out whether we can do anything about the max-comps + * at the parents' levels + */ + + if (fe->fe_refcount > 1) + { + continue; + } + + /* This entry is no longer ref'd; if it's 'virtual', we can + * delete it too. + */ + if (fe->fe_flags & CICN_FIB_ENTRY_FLAG_VIRTUAL) + { + /* Remove entry entirely */ + ret = cicn_hashtb_delete (fib->fib_table, &pnode); + + /* Now more nodes have been removed, so more refs need to be + * removed at the parents... + */ + counter++; + } + } + + ret = AOK; + +done: + + return (ret); +} + +/* + * Mark a FIB prefix for delete, before actually deleting through a later + * api call. + * We expect that the prefix-hashing has already been done, into 'pfxhash'. + * This will check virtual parents' refcounts, and will mark them for + * delete also if necessary. + */ +int +cicn_fib_entry_mark_for_delete (cicn_fib_t * fib, + const cicn_prefix_hashinf_t * pfxhash) +{ + int ret = EINVAL; + + return (ret); +} + +/* + * Add, delete, or change weight of fib entry next hop (which may + * lead to add/delete of fib entry) + */ +int +cicn_fib_entry_nh_update (const char *prefix, int faceid, int weight, + int add_p, cicn_rd_t * cicn_rd_res) +{ + cicn_rd_t cicn_rd; + + int len; + uint8_t buf[CICN_PARAM_FIB_ENTRY_PFX_WF_BYTES_MAX]; + cicn_prefix_hashinf_t pfxhash; + + cicn_rd_set (&cicn_rd, CICN_RC_OK, AOK); + + /* Check that we're init-ed */ + if (!cicn_infra_fwdr_initialized) + { + cicn_cli_output ("cicn: disabled"); + + cicn_rd.rd_ux_rc = EINVAL; + goto done; + } + + /* Quick check for valid face for adds */ + if (add_p) + { + if (cicn_face_entry_find_by_id (faceid, NULL) != AOK) + { + cicn_rd.rd_cicn_rc = CICN_RC_FACE_UNKNOWN; + cicn_rd.rd_ux_rc = EINVAL; + goto done; + } + } + + /* Convert prefix to wire-format */ + len = cicn_parse_name_comps_from_str (buf, sizeof (buf), prefix, &cicn_rd); + if (len < 0) + { + goto done; + } + + /* Hash the prefix */ + cicn_rd.rd_ux_rc = + cicn_hashtb_hash_prefixes (buf, len, 0 /*full_name */ , &pfxhash, + 0 /*limit */ ); + if (cicn_rd.rd_ux_rc != AOK) + { + goto done; + } + + /* Call to the fib apis */ + if (add_p) + { + /* TODO -- support next-hop weight */ + cicn_rd.rd_ux_rc = + cicn_fib_entry_insert (&cicn_main.fib, &pfxhash, faceid, weight, + &cicn_rd); + } + else + { + cicn_rd.rd_ux_rc = + cicn_fib_entry_delete (&cicn_main.fib, &pfxhash, faceid); + } + +done: + + if (cicn_rd_res) + { + *cicn_rd_res = cicn_rd; + } + return (cicn_rd.rd_ux_rc); +} + +/*************************************************************************** + * CICN_FIB management plane (debug cli, binary API) helper routines + ***************************************************************************/ + +/* + * CLI show output for fib. if 'prefix', just show a single entry + */ +int +cicn_fib_show (const char *prefix, int detail_p, int internal_p) +{ + int i, ret = 0; + uint64_t cookie; + cicn_hash_node_t *node; + cicn_fib_entry_t *fe; + char cbuf[CICN_PARAM_HASHTB_KEY_BYTES_MAX]; + u8 *strbuf = NULL; + + /* TODO -- use the supplied 'prefix' */ + + /* Check that we're init-ed */ + if (!cicn_infra_fwdr_initialized) + { + cicn_cli_output ("cicn: disabled"); + + ret = EINVAL; + goto done; + } + + cicn_cli_output ("cicn FIB:"); + + /* Walk the FIB hashtable, */ + cookie = CICN_HASH_WALK_CTX_INITIAL; + + while (cicn_hashtb_next_node (cicn_main.fib.fib_table, + &node, &cookie) == AOK) + { + + fe = cicn_fib_get_data (node); + + /* Skip virtual entries unless 'internal_p' */ + if (!internal_p && (fe->fe_flags & CICN_FIB_ENTRY_FLAG_VIRTUAL)) + { + continue; + } + + vec_reset_length (strbuf); + + ret = + cicn_hashtb_key_to_str (cicn_main.fib.fib_table, node, cbuf, + sizeof (cbuf), 0 /*!must_fit */ ); + + strbuf = format (strbuf, " %s/...", cbuf); + int pad = 16 - vec_bytes (strbuf); // even out to column 16 + if (pad > 0) + { + strbuf = format (strbuf, "%*s", pad, ""); + } + + + if (fe->fe_flags & CICN_FIB_ENTRY_FLAG_VIRTUAL) + { + strbuf = format (strbuf, " (virtual)"); + } + + if (internal_p) + { + strbuf = format (strbuf, " (ref:%d)", fe->fe_refcount); + } + + for (i = 0; i < ARRAY_LEN (fe->fe_next_hops); i++) + { + if (fe->fe_next_hops[i].nh_faceid != 0) + { + strbuf = format (strbuf, " (face:%d, weight:%d)", + (int) (fe->fe_next_hops[i].nh_faceid), + (int) (fe->fe_next_hops[i].nh_weight)); + } + } + + /* Oy - vecs are neat, but ... */ + vec_terminate_c_string (strbuf); + vlib_cli_output (cicn_main.vlib_main, "%s", strbuf); + } + +done: + + if (strbuf) + { + vec_free (strbuf); + } + + return (ret); +} + +/* + * Binary serialization for show FIB API. + */ +int + cicn_fib_api_entry_props_serialize + (vl_api_cicn_api_fib_entry_props_get_reply_t * reply, int page) +{ + int rv = CICN_VNET_API_ERROR_NONE; + + int i, nentries = 0; + + uint64_t cookie; + cicn_hash_node_t *node; + cicn_fib_entry_t *fe; + + /* Check that we're init-ed */ + if (!cicn_infra_fwdr_initialized) + { + rv = VNET_API_ERROR_FEATURE_DISABLED; + goto done; + } + + /* Walk the FIB hashtable, */ + cookie = CICN_HASH_WALK_CTX_INITIAL; + + while (cicn_hashtb_next_node (cicn_main.fib.fib_table, + &node, &cookie) == AOK) + { + + fe = cicn_fib_get_data (node); + + /* Skip virtual entries unless 'internal_p' */ + if ((fe->fe_flags & CICN_FIB_ENTRY_FLAG_VIRTUAL)) + { + continue; + } + + /* TODO -- deal with overflow keys */ + i = node->hn_keysize; + if (i > CICN_HASH_KEY_BYTES) + { + i = CICN_HASH_KEY_LIST_BYTES; + } + + cicn_api_fib_entry_t *entry = (cicn_api_fib_entry_t *) + (&reply->fibentry[nentries * sizeof (cicn_api_fib_entry_t)]); + + cicn_hashtb_key_to_str (cicn_main.fib.fib_table, node, + (char *) entry->prefix, sizeof (entry->prefix), + 0 /*!must_fit */ ); + + for (i = 0; i < ARRAY_LEN (fe->fe_next_hops); i++) + { + if (fe->fe_next_hops[i].nh_faceid == 0) + { + continue; + } + entry->faceid[i] = + clib_host_to_net_i32 (fe->fe_next_hops[i].nh_faceid); + + entry->faceweight[i] = + clib_host_to_net_i32 (fe->fe_next_hops[i].nh_weight); + + entry->nfaces = clib_host_to_net_i32 (i + 1); + } + + nentries++; + reply->nentries = clib_host_to_net_i32 (nentries); + } + +done: + return (rv); +} + + + |