diff options
Diffstat (limited to 'hicn-light/src/hicn/core/fib.c')
-rw-r--r-- | hicn-light/src/hicn/core/fib.c | 478 |
1 files changed, 478 insertions, 0 deletions
diff --git a/hicn-light/src/hicn/core/fib.c b/hicn-light/src/hicn/core/fib.c new file mode 100644 index 000000000..d8d3c7cfa --- /dev/null +++ b/hicn-light/src/hicn/core/fib.c @@ -0,0 +1,478 @@ +/* + * Copyright (c) 2021 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 <hicn/hicn-light/config.h> +#include <stdio.h> + +#include <hicn/core/fib.h> + +typedef struct fib_node_s { + struct fib_node_s *left; + struct fib_node_s *right; + fib_entry_t *entry; + bool is_used; +} fib_node_t; + +static fib_node_t *fib_node_create(fib_node_t *left, fib_node_t *right, + fib_entry_t *entry, bool is_used) { + fib_node_t *node = malloc(sizeof(fib_node_t)); + if (!node) return NULL; + + *node = (fib_node_t){ + .left = left, + .right = right, + .entry = entry, + .is_used = is_used, + }; + + return node; +} + +static void fib_node_free(fib_node_t *node) { + if (!node) return; + + fib_node_free(node->right); + fib_node_free(node->left); + + fib_entry_free(node->entry); + free(node); +} + +/******************************************************************************/ + +struct fib_s { + void *forwarder; + fib_node_t *root; + unsigned size; +}; + +fib_t *fib_create(void *forwarder) { + fib_t *fib = malloc(sizeof(fib_t)); + if (!fib) return NULL; + + fib->forwarder = forwarder; + fib->root = NULL; + fib->size = 0; + + return fib; +} + +void fib_free(fib_t *fib) { + assert(fib); + + fib_node_free(fib->root); + + free(fib); +} + +size_t fib_get_size(const fib_t *fib) { + assert(fib); + return fib->size; +} + +#define FIB_SET(CURR, NEW_PREFIX, CURR_PREFIX_LEN) \ + do { \ + bool bit; \ + int res = nameBitvector_testBit(NEW_PREFIX, CURR_PREFIX_LEN, &bit); \ + assert(res >= 0); \ + (void)res; /* unused */ \ + CURR = bit ? CURR->right : CURR->left; \ + } while (0) + +#define FIB_INSERT(DST, SRC, PREFIX, PREFIX_LEN) \ + do { \ + bool bit; \ + int res = nameBitvector_testBit(PREFIX, PREFIX_LEN, &bit); \ + assert(res >= 0); \ + (void)res; /* unused */ \ + if (bit) \ + DST->right = SRC; \ + else \ + DST->left = SRC; \ + } while (0) + +void fib_add(fib_t *fib, fib_entry_t *entry) { + assert(fib); + assert(entry); + + NameBitvector *new_prefix = name_GetContentName(fib_entry_get_prefix(entry)); + uint32_t new_prefix_len = nameBitvector_GetLength(new_prefix); + fib_node_t *curr = fib->root; + fib_node_t *last = NULL; + + NameBitvector *curr_name; + uint32_t curr_prefix_len; + uint32_t match_len; + + while (curr) { + curr_name = name_GetContentName(fib_entry_get_prefix(curr->entry)); + + match_len = nameBitvector_lpm(new_prefix, curr_name); + curr_prefix_len = nameBitvector_GetLength(curr_name); + + if (curr_prefix_len != + match_len || // the new entry does not match the curr + curr_prefix_len >= + new_prefix_len) // in this case we cannot procede anymore + break; + + last = curr; + FIB_SET(curr, new_prefix, curr_prefix_len); + } + + // this is the root (empty trie) or an empty child + if (!curr) { + fib_node_t *new_node = fib_node_create(NULL, NULL, entry, true); + if (!last) { + fib->root = new_node; + } else { + uint32_t last_prefix_len = nameBitvector_GetLength( + name_GetContentName(fib_entry_get_prefix(last->entry))); + + FIB_INSERT(last, new_node, new_prefix, last_prefix_len); + } + fib->size++; + return; + } + + // curr is not null + + // the node already exist + // if is not in use we turn it on and we set the rigth fib entry + if (curr_prefix_len == match_len && new_prefix_len == match_len) { + if (!curr->is_used) { + curr->is_used = true; + curr->entry = entry; + fib->size++; + return; + } else { + // this case should never happen beacuse of the way we add + // entries in the fib + const nexthops_t *nexthops = fib_entry_get_nexthops(entry); + unsigned nexthop; + nexthops_foreach(nexthops, nexthop, + { fib_entry_nexthops_add(curr->entry, nexthop); }); + } + } + + // key is prefix of the curr node (so new_prefix_len < curr_prefix_len) + if (new_prefix_len == match_len) { + fib_node_t *new_node = fib_node_create(NULL, NULL, entry, true); + if (!last) { + fib->root = new_node; + } else { + uint32_t last_prefix_len = nameBitvector_GetLength( + name_GetContentName(fib_entry_get_prefix(last->entry))); + FIB_INSERT(last, new_node, new_prefix, last_prefix_len); + } + FIB_INSERT(new_node, curr, curr_name, match_len); + fib->size++; + return; + } + + // in the last case we need to add an inner node + Name inner_prefix = EMPTY_NAME; + name_Copy(fib_entry_get_prefix(entry), &inner_prefix); + nameBitvector_clear(name_GetContentName(&inner_prefix), match_len); + name_setLen(&inner_prefix, match_len); + + // this is an inner node, we don't want an acctive strategy + // like low_latency that sends probes in this node + fib_entry_t *inner_entry = fib_entry_create( + &inner_prefix, STRATEGY_TYPE_UNDEFINED, NULL, fib->forwarder); + + fib_node_t *inner_node = fib_node_create(NULL, NULL, inner_entry, false); + fib_node_t *new_node = fib_node_create(NULL, NULL, entry, true); + + if (!last) { + // we need to place the inner_node at the root + fib->root = inner_node; + } else { + uint32_t last_prefix_len = nameBitvector_GetLength( + name_GetContentName(fib_entry_get_prefix(last->entry))); + NameBitvector *inner_name = name_GetContentName(&inner_prefix); + FIB_INSERT(last, inner_node, inner_name, last_prefix_len); + } + + bool bit; + int res = nameBitvector_testBit(new_prefix, match_len, &bit); + assert(res >= 0); + (void)res; /* unused */ + inner_node->left = bit ? curr : new_node; + inner_node->right = bit ? new_node : curr; + fib->size++; +} + +fib_entry_t *fib_contains(const fib_t *fib, const Name *prefix) { + assert(fib); + assert(prefix); + + NameBitvector *key_name = name_GetContentName(prefix); + uint32_t key_prefix_len = nameBitvector_GetLength(key_name); + + fib_node_t *curr = fib->root; + + while (curr) { + NameBitvector *curr_name = + name_GetContentName(fib_entry_get_prefix(curr->entry)); + uint32_t match_len = nameBitvector_lpm(key_name, curr_name); + uint32_t curr_prefix_len = nameBitvector_GetLength(curr_name); + + if (match_len < curr_prefix_len) { + // the current node does not match completelly the key, so + // the key is not in the trie + // this implies curr_prefix_len > key_prefix_len + return NULL; + } + + if (curr_prefix_len == key_prefix_len) { //== match_len + // this is an exact match + if (!curr->is_used) { + // the key does not exists + return NULL; + } + // we found the key + return curr->entry; + } + + FIB_SET(curr, key_name, curr_prefix_len); + } + + return NULL; +} + +static void fib_node_remove(fib_t *fib, const Name *prefix) { + assert(fib); + assert(prefix); + + NameBitvector *key_name = name_GetContentName(prefix); + uint32_t key_prefix_len = nameBitvector_GetLength(key_name); + + fib_node_t *curr = fib->root; + fib_node_t *parent = NULL; + fib_node_t *grandpa = NULL; + + uint32_t match_len; + uint32_t curr_prefix_len; + + while (curr) { + NameBitvector *curr_name = + name_GetContentName(fib_entry_get_prefix(curr->entry)); + match_len = nameBitvector_lpm(key_name, curr_name); + curr_prefix_len = nameBitvector_GetLength(curr_name); + + if (match_len < curr_prefix_len || curr_prefix_len == key_prefix_len) { + break; + } + + grandpa = parent; + parent = curr; + + FIB_SET(curr, key_name, curr_prefix_len); + } + + if (!curr || !curr->is_used || (curr_prefix_len != key_prefix_len)) { + // the node does not exists + return; + } + + // curr has 2 children, leave it there and mark it as inner + if (curr->right && curr->left) { + curr->is_used = false; + fib->size--; + return; + } + + // curr has no children + if (!curr->right && !curr->left) { + if (!parent) { + // curr is the root and is the only node in the fib + fib->root = NULL; + fib->size--; + fib_node_free(curr); + return; + } + if (!grandpa) { + // parent is the root + if (fib->root->left == curr) + fib->root->left = NULL; + else + fib->root->right = NULL; + fib->size--; + fib_node_free(curr); + return; + } + if (!parent->is_used) { + // parent is an inner node + // remove curr and inner_node (parent), connect the other child + // of the parent to the grandpa + fib_node_t *tmp = (parent->right == curr) ? parent->left : parent->right; + + if (grandpa->right == parent) + grandpa->right = tmp; + else + grandpa->left = tmp; + + fib->size--; + fib_node_free(curr); + fib_node_free(parent); + return; + } + // parent is node not an inner_node + // just remove curr the node + if (parent->right == curr) + parent->right = NULL; + else + parent->left = NULL; + fib->size--; + fib_node_free(curr); + return; + } + + // curr has one child + if (curr->right || curr->left) { + if (!parent) { + // curr is the root + fib->root = fib->root->right ? fib->root->right : fib->root->left; + fib->size--; + fib_node_free(curr); + return; + } + // attach the child of curr to parent + fib_node_t *tmp = curr->right ? curr->right : curr->left; + + if (parent->right == curr) + parent->right = tmp; + else + parent->left = tmp; + + fib->size--; + fib_node_free(curr); + return; + } +} + +void fib_remove(fib_t *fib, const Name *name, unsigned conn_id) { + assert(fib); + assert(name); + + fib_entry_t *entry = fib_contains(fib, name); + if (!entry) return; + + fib_entry_nexthops_remove(entry, conn_id); +#ifndef WITH_MAPME + if (fib_entry_nexthops_len(entry) == 0) fib_node_remove(fib, name); +#endif /* WITH_MAPME */ +} + +static size_t fib_node_remove_connection_id(fib_node_t *node, unsigned conn_id, + fib_entry_t **array, size_t pos) { + if (!node) return pos; + if (node->is_used) { + fib_entry_nexthops_remove(node->entry, conn_id); +#ifndef WITH_MAPME + if (fib_entry_nexthops_len(node->entry) == 0) array[pos++] = node->entry; +#endif /* WITH_MAPME */ + } + pos = fib_node_remove_connection_id(node->right, conn_id, array, pos); + pos = fib_node_remove_connection_id(node->left, conn_id, array, pos); + return pos; +} + +void fib_remove_connection_id(fib_t *fib, unsigned conn_id) { + assert(fib); + + fib_entry_t **array = malloc(sizeof(fib_entry_t *) * fib->size); + + size_t pos = 0; + pos = fib_node_remove_connection_id(fib->root, conn_id, array, pos); + + for (int i = 0; i < pos; i++) + fib_node_remove(fib, fib_entry_get_prefix(array[i])); + free(array); +} + +fib_entry_t *fib_match_message(const fib_t *fib, + const msgbuf_t *interest_msgbuf) { + assert(fib); + assert(interest_msgbuf); + + return fib_match_bitvector( + fib, name_GetContentName(msgbuf_get_name(interest_msgbuf))); +} + +fib_entry_t *fib_match_name(const fib_t *fib, const Name *name) { + assert(fib); + assert(name); + + return fib_match_bitvector(fib, name_GetContentName(name)); +} + +fib_entry_t *fib_match_bitvector(const fib_t *fib, const NameBitvector *name) { + assert(fib); + assert(name); + + uint32_t key_prefix_len = nameBitvector_GetLength(name); + + fib_node_t *curr = fib->root; + fib_node_t *candidate = NULL; + + while (curr) { + NameBitvector *curr_name = + name_GetContentName(fib_entry_get_prefix(curr->entry)); + uint32_t match_len = nameBitvector_lpm(name, curr_name); + uint32_t curr_prefix_len = nameBitvector_GetLength(curr_name); + + if (match_len < curr_prefix_len) { + // the current node does not match completelly the key, so + // return the parent of this node (saved in candidate) + break; + } + + if (curr->is_used) candidate = curr; + + // if we are here match_len == curr_prefix_len (can't be larger) + // so this node is actually a good candidate for a match + if (curr_prefix_len == key_prefix_len) { + // this an exact match, do not continue + break; + } + + FIB_SET(curr, name, curr_prefix_len); + } + + return candidate ? candidate->entry : NULL; +} + +static size_t fib_node_collect_entries(fib_node_t *node, fib_entry_t **array, + size_t pos) { + assert(array); + + if (!node) return pos; + + if (node->is_used) array[pos++] = node->entry; + + pos = fib_node_collect_entries(node->right, array, pos); + pos = fib_node_collect_entries(node->left, array, pos); + return pos; +} + +size_t fib_get_entry_array(const fib_t *fib, fib_entry_t ***array_p) { + size_t pos = 0; + *array_p = malloc(sizeof(fib_entry_t *) * fib->size); + if (!*array_p) return pos; + pos = fib_node_collect_entries(fib->root, *array_p, pos); + return pos; +} |