From 6f0a3087e4ddab4c9f039c154bb21373c1a5d96f Mon Sep 17 00:00:00 2001 From: Michele Papalini Date: Mon, 30 Jan 2023 17:21:38 +0100 Subject: fix(fib): fix lmp on hicn-light fib Ref: HICN-834 Signed-off-by: Michele Papalini Change-Id: Ia5648c8784f2c90fb23d1860f8ee20e21158e5e7 --- hicn-light/src/hicn/core/fib.c | 63 ++++++------ hicn-light/src/hicn/test/test-fib.cc | 188 +++++++++++++++++++++++++++++++---- 2 files changed, 204 insertions(+), 47 deletions(-) diff --git a/hicn-light/src/hicn/core/fib.c b/hicn-light/src/hicn/core/fib.c index 70c5599fb..5f8788155 100644 --- a/hicn-light/src/hicn/core/fib.c +++ b/hicn-light/src/hicn/core/fib.c @@ -92,6 +92,7 @@ typedef struct { /* Result node ancestors (NULL if not applicable) */ fib_node_t *parent; fib_node_t *gparent; + fib_node_t *lpm; /* Information related to the result node */ hicn_prefix_t *prefix; uint32_t prefix_len; @@ -134,6 +135,7 @@ fib_node_t *fib_search(const fib_t *fib, const hicn_prefix_t *prefix, fib_node_t *parent = NULL; fib_node_t *gparent = NULL; + fib_node_t *lpm = NULL; fib_node_t *curr = fib->root; while (curr) { const hicn_prefix_t *curr_prefix = fib_entry_get_prefix(curr->entry); @@ -141,6 +143,9 @@ fib_node_t *fib_search(const fib_t *fib, const hicn_prefix_t *prefix, curr_len = hicn_prefix_get_len(curr_prefix); match_len = hicn_prefix_lpm(prefix, curr_prefix); + // store the lpm + if (match_len == curr_len && curr->is_used) lpm = curr; + // curr_len >= prefix_len l >= L // L is a prefix of l // > means we did not find @@ -158,6 +163,7 @@ fib_node_t *fib_search(const fib_t *fib, const hicn_prefix_t *prefix, if (search) { search->parent = parent; search->gparent = gparent; + search->lpm = lpm; if (curr) { search->prefix_len = curr_len; search->match_len = match_len; @@ -367,10 +373,10 @@ END: * Implementation details: * * To find whether the fib contains a prefix, we issue a search, and based on - * the stopping conditions, we return the entry if and only if curr + * the stopping conditions, we return the fib note if and only if curr * is not NULL, and prefix_len == curr_len (== match_len) */ -fib_entry_t *fib_contains(const fib_t *fib, const hicn_prefix_t *prefix) { +fib_node_t *fib_contains_node(const fib_t *fib, const hicn_prefix_t *prefix) { assert(fib); assert(prefix); @@ -383,7 +389,13 @@ fib_entry_t *fib_contains(const fib_t *fib, const hicn_prefix_t *prefix) { if (search.match_len != prefix_len) return NULL; if (prefix_len != search.prefix_len) return NULL; - return curr->is_used ? curr->entry : NULL; + return curr->is_used ? curr : NULL; +} + +fib_entry_t *fib_contains(const fib_t *fib, const hicn_prefix_t *prefix) { + fib_node_t *node = fib_contains_node(fib, prefix); + if (!node) return NULL; + return node->entry; } /* @@ -500,12 +512,16 @@ void fib_remove(fib_t *fib, const hicn_prefix_t *prefix, unsigned conn_id) { assert(fib); assert(prefix); - fib_entry_t *entry = fib_contains(fib, prefix); - if (!entry) return; + fib_node_t *node = fib_contains_node(fib, prefix); + if (!node) return; - fib_entry_nexthops_remove(entry, conn_id); -#ifndef WITH_MAPME - if (fib_entry_nexthops_len(entry) == 0) fib_node_remove(fib, name); + fib_entry_nexthops_remove(node->entry, conn_id); + if (fib_entry_nexthops_len(node->entry) == 0) + /* When using MAP-Me, we keep empty FIB entries but we mark them as unused*/ +#ifdef WITH_MAPME + node->is_used = false; +#else + fib_node_remove(fib, name); #endif /* WITH_MAPME */ } @@ -515,9 +531,12 @@ static size_t fib_node_remove_connection_id(fib_node_t *node, unsigned conn_id, if (node->is_used) { fib_entry_nexthops_remove(node->entry, conn_id); - /* When using MAP-Me, we keep empty FIB entries */ -#ifndef WITH_MAPME - if (fib_entry_nexthops_len(node->entry) == 0) array[pos++] = node->entry; + /* When using MAP-Me, we keep empty FIB entries but we mark them as unused*/ + if (fib_entry_nexthops_len(node->entry) == 0) +#ifdef WITH_MAPME + node->is_used = false; +#else + array[pos++] = node->entry; #endif /* WITH_MAPME */ } pos = fib_node_remove_connection_id(node->child[ONE], conn_id, array, pos); @@ -564,30 +583,17 @@ fib_entry_t *fib_match_msgbuf(const fib_t *fib, const msgbuf_t *msgbuf) { } /* - * Implementation details: - * * fib_search returns the longest non-strict subprefix. - * - curr == NULL means no such prefix exist and we can return the parent. - * - if we have an exact match (curr_len == key_prefix_len), then we - * return curr unless is_used is false, in which case we return the parent. - * - otherwise, the parent is the longest prefix match + * the LPM is stored in search if it exists */ fib_entry_t *fib_match_prefix(const fib_t *fib, const hicn_prefix_t *prefix) { assert(fib); assert(prefix); fib_search_t search; - fib_node_t *curr = fib_search(fib, prefix, &search); - - if (!curr) { - /* This can happen with an empty FIB for instance */ - if (!search.parent) return NULL; - return search.parent->entry; - } - if ((search.prefix_len == search.match_len) && curr->is_used) - return curr->entry; - if (search.parent) return search.parent->entry; - return NULL; + fib_search(fib, prefix, &search); + if (!search.lpm) return NULL; + return search.lpm->entry; } fib_entry_t *fib_match_name(const fib_t *fib, const hicn_name_t *name) { @@ -632,7 +638,6 @@ bool _fib_is_valid(const fib_node_t *node) { uint32_t match_len = hicn_prefix_lpm(prefix, child_prefix); if (match_len != prefix_len) return false; - if (!node->is_used && !child->is_used) return false; if (hicn_prefix_get_bit(child_prefix, match_len) != i) return false; if (!_fib_is_valid(child)) return false; } diff --git a/hicn-light/src/hicn/test/test-fib.cc b/hicn-light/src/hicn/test/test-fib.cc index 6e1f59077..5068b4fa2 100644 --- a/hicn-light/src/hicn/test/test-fib.cc +++ b/hicn-light/src/hicn/test/test-fib.cc @@ -22,6 +22,7 @@ #include #include #include +#include extern "C" { #define WITH_TESTS @@ -49,18 +50,24 @@ class FibTest : public ::testing::Test { fib_t *fib; }; -fib_entry_t *_fib_add_prefix(fib_t *fib, const hicn_prefix_t *prefix) { +fib_entry_t *_fib_add_prefix(fib_t *fib, const hicn_prefix_t *prefix, + std::vector &nexthops) { fib_entry_t *entry = fib_entry_create(prefix, STRATEGY_TYPE_UNDEFINED, NULL, NULL); + for (size_t i = 0; i < nexthops.size(); i++) + fib_entry_nexthops_add(entry, nexthops[i]); fib_add(fib, entry); return entry; } -#if 0 -static const hicn_prefix_t p0010 = (hicn_prefix_t){ - .name = {.v6 = {.as_u64 = {0x1122334455667788, 0x9900aabbccddeeff}}}, - .len = 4}; -#endif +int compare_str_prefix_to_prefix(char *p1, hicn_prefix_t *p2) { + char prefix_s[MAXSZ_IP_PREFIX]; + hicn_ip_prefix_t ipp; + hicn_prefix_get_ip_prefix(p2, &ipp); + hicn_ip_prefix_snprintf(prefix_s, MAXSZ_IP_PREFIX, + (const hicn_ip_prefix_t *)&ipp); + return strcmp(prefix_s, p1); +} #define HICN_PREFIX(P, STR) \ hicn_prefix_t P; \ @@ -82,9 +89,10 @@ TEST_F(FibTest, FibAddOne) { const hicn_prefix_t *prefix_array[] = {&pfx}; bool used_array[] = {true}; + std::vector empty_nexthop; for (unsigned i = 0; i < ARRAY_SIZE(prefix_array); i++) { if (!used_array[i]) continue; - _fib_add_prefix(fib, prefix_array[i]); + _fib_add_prefix(fib, prefix_array[i], empty_nexthop); } fib_dump(fib); @@ -103,8 +111,9 @@ TEST_F(FibTest, FibAddTwo) { const hicn_prefix_t *prefix_array[] = {&b001, &inner_8000_1, &c001}; bool used_array[] = {true, false, true}; - _fib_add_prefix(fib, &b001); - _fib_add_prefix(fib, &c001); + std::vector empty_nexthop; + _fib_add_prefix(fib, &b001, empty_nexthop); + _fib_add_prefix(fib, &c001, empty_nexthop); fib_dump(fib); @@ -126,11 +135,12 @@ TEST_F(FibTest, FibAddFive) { &b002_abcd_0, &inner_b002_abcd_0, &b002_abcd_1}; bool used_array[] = {true, false, true, true, true, false, true}; - _fib_add_prefix(fib, &b002); - _fib_add_prefix(fib, &b002_abcd_0); - _fib_add_prefix(fib, &b002_2); - _fib_add_prefix(fib, &b002_abcd_1); - _fib_add_prefix(fib, &b002_3); + std::vector empty_nexthop; + _fib_add_prefix(fib, &b002, empty_nexthop); + _fib_add_prefix(fib, &b002_abcd_0, empty_nexthop); + _fib_add_prefix(fib, &b002_2, empty_nexthop); + _fib_add_prefix(fib, &b002_abcd_1, empty_nexthop); + _fib_add_prefix(fib, &b002_3, empty_nexthop); fib_dump(fib); @@ -149,7 +159,8 @@ TEST_F(FibTest, FibAddRemove) { const hicn_prefix_t *prefix_array_3[] = {&b002_64}; bool used_array_3[] = {true}; - fib_entry_t *entry = _fib_add_prefix(fib, &b002_128); + std::vector empty_nexthop; + fib_entry_t *entry = _fib_add_prefix(fib, &b002_128, empty_nexthop); fib_dump(fib); EXPECT_TRUE(fib_is_valid(fib)); EXPECT_TRUE(fib_check_preorder(fib, prefix_array_1, used_array_1)); @@ -159,7 +170,7 @@ TEST_F(FibTest, FibAddRemove) { EXPECT_TRUE(fib_is_valid(fib)); EXPECT_TRUE(fib_check_preorder(fib, prefix_array_2, used_array_2)); - entry = _fib_add_prefix(fib, &b002_64); + entry = _fib_add_prefix(fib, &b002_64, empty_nexthop); fib_dump(fib); EXPECT_TRUE(fib_is_valid(fib)); EXPECT_TRUE(fib_check_preorder(fib, prefix_array_3, used_array_3)); @@ -174,13 +185,154 @@ TEST_F(FibTest, FibAddNested) { const hicn_prefix_t *prefix_array_2[] = {&b002_128, &b002_64}; bool used_array_2[] = {true, true}; - _fib_add_prefix(fib, &b002_128); + std::vector empty_nexthop; + _fib_add_prefix(fib, &b002_128, empty_nexthop); fib_dump(fib); EXPECT_TRUE(fib_is_valid(fib)); EXPECT_TRUE(fib_check_preorder(fib, prefix_array_1, used_array_1)); - _fib_add_prefix(fib, &b002_64); + _fib_add_prefix(fib, &b002_64, empty_nexthop); fib_dump(fib); EXPECT_TRUE(fib_is_valid(fib)); EXPECT_TRUE(fib_check_preorder(fib, prefix_array_2, used_array_2)); } + +TEST_F(FibTest, IRIStest) { + char p_0_s[] = "b001:0:0:3039::/64"; + char p_1_3_s[] = "b001::3039:0:1:2:0/128"; + HICN_PREFIX(p_0, p_0_s); + + HICN_PREFIX(p_1_2, "b001::3039:0:1:0:0/128"); + HICN_PREFIX(p_1_1, "b001::3039:0:1:0:100/128"); + HICN_PREFIX(p_1_3, p_1_3_s); + HICN_PREFIX(p_1_4, "b001::3039:0:1:0:102/128"); + + HICN_PREFIX(p_2_2, "b001::3039:0:2:0:0/128"); + HICN_PREFIX(p_2_1, "b001::3039:0:2:0:100/128"); + HICN_PREFIX(p_2_3, "b001::3039:0:2:2:0/128"); + HICN_PREFIX(p_2_4, "b001::3039:0:2:0:102/128"); + + HICN_PREFIX(to_match1, "b001::3039:0:1:0:101/128"); + HICN_PREFIX(to_match2, "b001:0:0:3039:ffff:ffff::/128"); + HICN_PREFIX(to_match3, "b001:1::/128"); + HICN_PREFIX(to_match4, "b001::3039:0:1:2:0/128"); + + std::vector nexthop; + nexthop.push_back(2); // add nexthop 2 to the fib entry + /*** add ***/ + _fib_add_prefix(fib, &p_0, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + + _fib_add_prefix(fib, &p_1_1, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + + _fib_add_prefix(fib, &p_1_2, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + + _fib_add_prefix(fib, &p_1_3, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + + _fib_add_prefix(fib, &p_1_4, nexthop); + fib_dump(fib); + EXPECT_TRUE(fib_is_valid(fib)); + + /*** match ***/ + fib_entry_t *entry = fib_match_prefix(fib, &to_match1); + // the matching prefix should be p0 + EXPECT_TRUE(entry != NULL); + if (entry) { + int ret = compare_str_prefix_to_prefix(p_0_s, &(entry->prefix)); + EXPECT_EQ(ret, 0); + } + + entry = fib_match_prefix(fib, &to_match2); + // the matching prefix should be p0 + EXPECT_TRUE(entry != NULL); + if (entry) { + int ret = compare_str_prefix_to_prefix(p_0_s, &(entry->prefix)); + EXPECT_EQ(ret, 0); + } + + entry = fib_match_prefix(fib, &to_match3); + // we expect no match + EXPECT_FALSE(entry != NULL); + + entry = fib_match_prefix(fib, &to_match4); + // the matching prefix should be p_1_3 + EXPECT_TRUE(entry != NULL); + if (entry) { + int ret = compare_str_prefix_to_prefix(p_1_3_s, &(entry->prefix)); + EXPECT_EQ(ret, 0); + } + + /*** remove ***/ + fib_remove(fib, &p_0, nexthop[0]); + EXPECT_TRUE(fib_is_valid(fib)); + fib_remove(fib, &p_1_1, nexthop[0]); + EXPECT_TRUE(fib_is_valid(fib)); + fib_remove(fib, &p_1_2, nexthop[0]); + EXPECT_TRUE(fib_is_valid(fib)); + fib_remove(fib, &p_1_3, nexthop[0]); + EXPECT_TRUE(fib_is_valid(fib)); + fib_remove(fib, &p_1_4, nexthop[0]); + EXPECT_TRUE(fib_is_valid(fib)); + fib_dump(fib); + + /*** match ***/ + entry = fib_match_prefix(fib, &to_match1); + // we expect no match + EXPECT_FALSE(entry != NULL); + + entry = fib_match_prefix(fib, &to_match2); + // we expect no match + EXPECT_FALSE(entry != NULL); + + entry = fib_match_prefix(fib, &to_match3); + // we expect no match + EXPECT_FALSE(entry != NULL); + + entry = fib_match_prefix(fib, &to_match4); + // we expect no match + EXPECT_FALSE(entry != NULL); + + // add again + _fib_add_prefix(fib, &p_0, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + _fib_add_prefix(fib, &p_2_1, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + _fib_add_prefix(fib, &p_2_2, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + _fib_add_prefix(fib, &p_2_3, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + _fib_add_prefix(fib, &p_2_4, nexthop); + EXPECT_TRUE(fib_is_valid(fib)); + fib_dump(fib); + + entry = fib_match_prefix(fib, &to_match1); + // the matching prefix should be p0 + EXPECT_TRUE(entry != NULL); + if (entry) { + int ret = compare_str_prefix_to_prefix(p_0_s, &(entry->prefix)); + EXPECT_EQ(ret, 0); + } + + entry = fib_match_prefix(fib, &to_match2); + // the matching prefix should be p0 + EXPECT_TRUE(entry != NULL); + if (entry) { + int ret = compare_str_prefix_to_prefix(p_0_s, &(entry->prefix)); + EXPECT_EQ(ret, 0); + } + + entry = fib_match_prefix(fib, &to_match3); + // we expect no match + EXPECT_FALSE(entry != NULL); + + entry = fib_match_prefix(fib, &to_match4); + // the matching prefix should be p0 + EXPECT_TRUE(entry != NULL); + if (entry) { + int ret = compare_str_prefix_to_prefix(p_0_s, &(entry->prefix)); + EXPECT_EQ(ret, 0); + } +} -- cgit 1.2.3-korg