aboutsummaryrefslogtreecommitdiffstats
path: root/hicn-light/src/hicn/core/fib.c
diff options
context:
space:
mode:
Diffstat (limited to 'hicn-light/src/hicn/core/fib.c')
-rw-r--r--hicn-light/src/hicn/core/fib.c478
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;
+}