/* * 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 #include #include /* * 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); }