From 822bd391506fd3f0afdc96ea441710fd0787c98b Mon Sep 17 00:00:00 2001 From: michele papalini Date: Wed, 4 Sep 2019 17:53:17 +0200 Subject: [HICN-272] new hicn-light fib Change-Id: Id0f13d6aebecc724556a80d3b3d57e8e06b6b262 Signed-off-by: michele papalini --- hicn-light/src/hicn/core/mapMe.c | 4 +- hicn-light/src/hicn/core/name.c | 28 +- hicn-light/src/hicn/core/name.h | 18 +- hicn-light/src/hicn/core/nameBitvector.c | 137 ++--- hicn-light/src/hicn/core/nameBitvector.h | 10 +- hicn-light/src/hicn/processor/fib.c | 657 +++++++++++------------ hicn-light/src/hicn/processor/fib.h | 8 +- hicn-light/src/hicn/processor/messageProcessor.c | 2 +- 8 files changed, 417 insertions(+), 447 deletions(-) (limited to 'hicn-light') diff --git a/hicn-light/src/hicn/core/mapMe.c b/hicn-light/src/hicn/core/mapMe.c index 865841f67..0f86dfd7e 100644 --- a/hicn-light/src/hicn/core/mapMe.c +++ b/hicn-light/src/hicn/core/mapMe.c @@ -583,7 +583,7 @@ static bool mapMe_onSpecialInterest(const MapMe *mapme, #else fibEntry = fibEntry_Create(name, fwdStrategy); #endif /* WITH_POLICY */ - FibEntry *lpm = fib_LPM(fib, name); + FibEntry *lpm = fib_MatchName(fib, name); mapMe_CreateTFIB(fibEntry); fib_Add(fib, fibEntry); if (!lpm) { @@ -755,7 +755,7 @@ void mapMe_onSpecialInterestAck(const MapMe *mapme, const uint8_t *msgBuffer, const Name * name = name_CreateFromPacket(msgBuffer, MessagePacketType_ContentObject); - name_setLen(name, prefix->len); + name_setLen((Name*) name, prefix->len); char * name_str = name_ToString(name); INFO(mapme, "[MAP-Me] Received ack for name prefix=%s seq=%d on conn id=%d", name_str, params->seq, conn_in_id); diff --git a/hicn-light/src/hicn/core/name.c b/hicn-light/src/hicn/core/name.c index 8cf8dacbc..f4ea7dbca 100644 --- a/hicn-light/src/hicn/core/name.c +++ b/hicn-light/src/hicn/core/name.c @@ -162,6 +162,24 @@ Name *name_Acquire(const Name *original) { return copy; } +Name *name_Copy(const Name *original) { + parcAssertNotNull(original, "Parameter must be non-null"); + Name *copy = parcMemory_AllocateAndClear(sizeof(Name)); + parcAssertNotNull(copy, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(Name)); + + copy->content_name = nameBitvector_Copy(original->content_name); + copy->segment = original->segment; + copy->name_hash = original->name_hash; + + copy->refCountPtr = parcMemory_Allocate(sizeof(unsigned)); + parcAssertNotNull(copy->refCountPtr, "parcMemory_Allocate(%zu) returned NULL", + sizeof(unsigned)); + *copy->refCountPtr = 1; + + return copy; +} + uint32_t name_HashCode(const Name *name) { parcAssertNotNull(name, "Parameter must be non-null"); return name->name_hash; @@ -211,13 +229,6 @@ int name_Compare(const Name *a, const Name *b) { } } -bool name_StartsWith(const Name *name, const Name *prefix) { - parcAssertNotNull(name, "Parameter name must be non-null"); - parcAssertNotNull(prefix, "Parameter prefix must be non-null"); - - return nameBitvector_StartsWith(name->content_name, prefix->content_name); -} - char *name_ToString(const Name *name) { char *output = malloc(128); @@ -231,8 +242,9 @@ char *name_ToString(const Name *name) { return output; } -void name_setLen(const Name *name, uint8_t len) { +void name_setLen(Name *name, uint8_t len) { nameBitvector_setLen(name->content_name, len); + name->name_hash = _computeHash(name); } #ifdef WITH_POLICY diff --git a/hicn-light/src/hicn/core/name.h b/hicn-light/src/hicn/core/name.h index 4eb80cf36..f2ae1f64e 100644 --- a/hicn-light/src/hicn/core/name.h +++ b/hicn-light/src/hicn/core/name.h @@ -47,6 +47,11 @@ void name_Release(Name **namePtr); */ Name *name_Acquire(const Name *original); +/** + * returns a copy of the name + */ +Name *name_Copy(const Name *original); + /** * A hash value for use in hash tables * @@ -70,17 +75,6 @@ bool name_Equals(const Name *a, const Name *b); */ int name_Compare(const Name *a, const Name *b); -/** - * @function metsName_StartsWith - * @abstract Checks if name starts with prefix - * @discussion - * Byte-by-byte prefix comparison - * - * @return True if the name is equal to or begins with prefix - */ - -bool name_StartsWith(const Name *name, const Name *prefix); - /** * return the name in string format (bitvector + segment number) * @@ -93,7 +87,7 @@ char *name_ToString(const Name *name); * @param [in] message - Interest message * @param [in] len - Name length */ -void name_setLen(const Name *name, uint8_t len); +void name_setLen(Name *name, uint8_t len); /** * Creates a name from a Address diff --git a/hicn-light/src/hicn/core/nameBitvector.c b/hicn-light/src/hicn/core/nameBitvector.c index 8078778e3..ad6884d02 100644 --- a/hicn-light/src/hicn/core/nameBitvector.c +++ b/hicn-light/src/hicn/core/nameBitvector.c @@ -27,24 +27,21 @@ #include -#define BLOCKS 2 +#define NAME_LEN 2 -const uint64_t BLOCK_SIZE = 64; +const uint64_t BV_SIZE = 64; const uint64_t WIDTH = 128; -const uint64_t BLOCK_ONE = 0x1; - -// the bits are encoded in the following order: -// 00100101001---101010 00100011---110100100 -// [bits[0] (uint64_t)] [bits[1] (uint64_t)] -// ^ ^ ^ ^ -// 0 63 64 127 -// address 2200::0011 is encoded as: -// 1000 1000 0000 0010 00000 ....0100 0100 -// ^ ^ -// 0 127 +const uint64_t ONE = 0x1; + +// address b000:0000:0000:0001:c000:0000:0000:0001 is encodend as follow +// [bits[0] uint64_t ] [bits[1] unit64_t ] +// ^ ^ ^ ^ +// 63 0 127 64 +// [1000 0000 ... 0000 1101] [1000 0000 ... 0000 0011] //binary +// 1 b 1 c //hex struct name_bitvector { - uint64_t bits[BLOCKS]; + uint64_t bits[NAME_LEN]; uint8_t len; uint8_t IPversion; }; @@ -62,11 +59,11 @@ NameBitvector *nameBitvector_CreateFromInAddr(uint32_t addr, uint8_t len) { uint8_t addr_3 = (addr & 0x0000ff00) >> 8; uint8_t addr_4 = (addr & 0x000000ff); - bitvector->bits[1] = (bitvector->bits[1] | addr_4) << 8; - bitvector->bits[1] = (bitvector->bits[1] | addr_3) << 8; - bitvector->bits[1] = (bitvector->bits[1] | addr_2) << 8; - bitvector->bits[1] = (bitvector->bits[1] | addr_1); - bitvector->bits[1] = bitvector->bits[1] << 32; + bitvector->bits[0] = (bitvector->bits[0] | addr_4) << 8; + bitvector->bits[0] = (bitvector->bits[0] | addr_3) << 8; + bitvector->bits[0] = (bitvector->bits[0] | addr_2) << 8; + bitvector->bits[0] = (bitvector->bits[0] | addr_1); + bitvector->bits[0] = bitvector->bits[0] << 32; bitvector->len = len; @@ -87,11 +84,11 @@ NameBitvector *nameBitvector_CreateFromIn6Addr(struct in6_addr *addr, bitvector->bits[1] = 0; for (int i = 0; i < 8; ++i) { - bitvector->bits[1] = (bitvector->bits[1] << 8) | addr->s6_addr[i]; + bitvector->bits[0] = (bitvector->bits[0] << 8) | addr->s6_addr[i]; } for (int i = 8; i < 16; ++i) { - bitvector->bits[0] = (bitvector->bits[0] << 8) | addr->s6_addr[i]; + bitvector->bits[1] = (bitvector->bits[1] << 8) | addr->s6_addr[i]; } bitvector->len = len; @@ -191,38 +188,13 @@ int nameBitvector_Compare(const NameBitvector *a, const NameBitvector *b) { } } -bool nameBitvector_StartsWith(const NameBitvector *name, - const NameBitvector *prefix) { - parcAssertNotNull(name, "name cannot be NULL"); - parcAssertNotNull(prefix, "prefix cannot be NULL"); - parcAssertTrue(prefix->len > 0, "prefix length can not be 0"); - - if (prefix->len > BLOCK_SIZE) - return (name->bits[1] == prefix->bits[1]) && - ((name->bits[0] ^ prefix->bits[0]) >> - (BLOCK_SIZE - (prefix->len - BLOCK_SIZE)) == - 0); - - return ((name->bits[1] ^ prefix->bits[1]) >> (BLOCK_SIZE - prefix->len) == 0); -} - -bool nameBitvector_testBit(const NameBitvector *name, uint8_t pos) { - if (pos == WIDTH) pos = 127; - - uint8_t final_pos = (uint8_t)(WIDTH - name->len); - - // the bit to test is inside the name/prefix len - if (pos > final_pos) { - return (name->bits[pos / BLOCK_SIZE] & (BLOCK_ONE << (pos % BLOCK_SIZE))); - } +int nameBitvector_testBit(const NameBitvector *name, uint8_t pos, bool *bit) { + if(pos >= name->len || pos > (WIDTH -1)) + return -1; - // the bit to test is outside the name/prefix len - if (pos < final_pos) { - return false; - } + *bit = (name->bits[pos / BV_SIZE] & (ONE << ((BV_SIZE - 1) - (pos % BV_SIZE)))); - // pos is equal to the name/prefix len - return true; + return 0; } uint64_t _diff_bit_log2(uint64_t val) { @@ -257,31 +229,38 @@ uint64_t _diff_bit_log2(uint64_t val) { return result; } -uint8_t nameBitvector_firstDiff(const NameBitvector *a, - const NameBitvector *b) { - uint8_t res = 0; - uint64_t diff = a->bits[1] ^ b->bits[1]; - if (diff) - res = (uint8_t)(64 + _diff_bit_log2(diff)); - else - res = (uint8_t)_diff_bit_log2(a->bits[0] ^ b->bits[0]); - - // res is computed over the bitvector which is composed by 128 bit all the - // times however the prefixes may be diffrent just because the have different - // lengths example: prefix 1: 0::/30 prefix 2: 0::/20 at this point of the - // function res would be 0 since both the bitvectors are composed by 0s but - // the function will return 127-20, which is the position at which the two - // prefix are different, since prefix 2 has only 20 bits - - uint8_t len_diff; +uint32_t nameBitvector_lpm(const NameBitvector *a, + const NameBitvector *b) { + uint32_t limit; + uint32_t prefix_len; if (a->len < b->len) - len_diff = (uint8_t)(WIDTH - a->len); + limit = a->len; else - len_diff = (uint8_t)(WIDTH - b->len); + limit = b->len; + + uint64_t diff = a->bits[0] ^ b->bits[0]; + if(diff){ + prefix_len = BV_SIZE - (_diff_bit_log2(diff) + 1); + //printf("if 1 diff = %lu plen = %d\n", diff, prefix_len); + }else{ + prefix_len = BV_SIZE; + diff = a->bits[1] ^ b->bits[1]; + if(diff){ + prefix_len += (BV_SIZE - (_diff_bit_log2(diff) + 1)); + //printf("if 2 diff = %lu plen = %d\n", diff, prefix_len); + }else{ + prefix_len += BV_SIZE; + } + } - if (len_diff > res) res = len_diff; + if(prefix_len < limit) + return prefix_len; + return limit; +} - return res; +void nameBitvector_clear(NameBitvector *a, uint8_t start_from){ + for(uint8_t pos = start_from; pos < WIDTH; pos++) + a->bits[pos / BV_SIZE] &= ~(ONE << ((BV_SIZE - 1) - (pos % BV_SIZE))); } int nameBitvector_ToIPAddress(const NameBitvector *name, @@ -291,7 +270,7 @@ int nameBitvector_ToIPAddress(const NameBitvector *name, ip_address->family = AF_INET; ip_address->prefix_len = IPV4_ADDR_LEN_BITS; - uint32_t tmp_addr = name->bits[1] >> 32ULL; + uint32_t tmp_addr = name->bits[0] >> 32ULL; uint8_t addr_1 = (tmp_addr & 0xff000000) >> 24; uint8_t addr_2 = (tmp_addr & 0x00ff0000) >> 16; uint8_t addr_3 = (tmp_addr & 0x0000ff00) >> 8; @@ -309,12 +288,12 @@ int nameBitvector_ToIPAddress(const NameBitvector *name, ip_address->prefix_len = name->len; // IPV6_ADDR_LEN_BITS; for (int i = 0; i < 8; i++) { - addr->s6_addr[i] = (uint8_t)((name->bits[1] >> 8 * (7 - i)) & 0xFF); + addr->s6_addr[i] = (uint8_t)((name->bits[0] >> 8 * (7 - i)) & 0xFF); } int x = 0; for (int i = 8; i < 16; ++i) { - addr->s6_addr[i] = (uint8_t)((name->bits[0] >> 8 * (7 - x)) & 0xFF); + addr->s6_addr[i] = (uint8_t)((name->bits[1] >> 8 * (7 - x)) & 0xFF); x++; } } @@ -329,7 +308,7 @@ Address *nameBitvector_ToAddress(const NameBitvector *name) { addr.sin_family = AF_INET; addr.sin_port = htons(1234); - uint32_t tmp_addr = name->bits[1] >> 32ULL; + uint32_t tmp_addr = name->bits[0] >> 32ULL; uint8_t addr_1 = (tmp_addr & 0xff000000) >> 24; uint8_t addr_2 = (tmp_addr & 0x00ff0000) >> 16; uint8_t addr_3 = (tmp_addr & 0x0000ff00) >> 8; @@ -354,13 +333,13 @@ Address *nameBitvector_ToAddress(const NameBitvector *name) { for (int i = 0; i < 8; i++) { addr.sin6_addr.s6_addr[i] = - (uint8_t)((name->bits[1] >> 8 * (7 - i)) & 0xFF); + (uint8_t)((name->bits[0] >> 8 * (7 - i)) & 0xFF); } int x = 0; for (int i = 8; i < 16; ++i) { addr.sin6_addr.s6_addr[i] = - (uint8_t)((name->bits[0] >> 8 * (7 - x)) & 0xFF); + (uint8_t)((name->bits[1] >> 8 * (7 - x)) & 0xFF); x++; } @@ -380,4 +359,4 @@ char *nameBitvector_ToString(const NameBitvector *name) { addressDestroy(&packetAddr); return output; -} \ No newline at end of file +} diff --git a/hicn-light/src/hicn/core/nameBitvector.h b/hicn-light/src/hicn/core/nameBitvector.h index 6ff859e3b..44cc45662 100644 --- a/hicn-light/src/hicn/core/nameBitvector.h +++ b/hicn-light/src/hicn/core/nameBitvector.h @@ -30,9 +30,6 @@ NameBitvector *nameBitvector_CreateFromInAddr(uint32_t addr, uint8_t len); NameBitvector *nameBitvector_CreateFromIn6Addr(struct in6_addr *addr, uint8_t len); -NameBitvector *nameBitvector_CreateFromAddress(const Address *prefix, - uint8_t len); - NameBitvector *nameBitvector_Copy(const NameBitvector *original); void nameBitvector_Destroy(NameBitvector **bitvectorPtr); @@ -45,12 +42,11 @@ bool nameBitvector_Equals(const NameBitvector *a, const NameBitvector *b); int nameBitvector_Compare(const NameBitvector *a, const NameBitvector *b); -bool nameBitvector_StartsWith(const NameBitvector *name, - const NameBitvector *prefix); +int nameBitvector_testBit(const NameBitvector *name, uint8_t pos, bool *bit); -bool nameBitvector_testBit(const NameBitvector *name, uint8_t pos); +uint32_t nameBitvector_lpm(const NameBitvector *a, const NameBitvector *b); -uint8_t nameBitvector_firstDiff(const NameBitvector *a, const NameBitvector *b); +void nameBitvector_clear(NameBitvector *a, uint8_t start_from); int nameBitvector_ToIPAddress(const NameBitvector *name, ip_address_t *ip_address); diff --git a/hicn-light/src/hicn/processor/fib.c b/hicn-light/src/hicn/processor/fib.c index 7cb94d4ba..6489e59e2 100644 --- a/hicn-light/src/hicn/processor/fib.c +++ b/hicn-light/src/hicn/processor/fib.c @@ -16,6 +16,7 @@ #include #include +#include #include #include @@ -23,9 +24,6 @@ #include -#define NULL_POS 128 -#define MSB_POS 127 - struct node; typedef struct node FibNode; @@ -33,10 +31,11 @@ struct node { FibNode *left; FibNode *right; FibEntry *entry; - unsigned pos; + bool is_used; }; struct fib { + Forwarder *forwarder; FibNode *root; unsigned size; }; @@ -45,7 +44,7 @@ struct fib { // Public API FibNode *_createNode(FibNode *left, FibNode *right, FibEntry *entry, - unsigned pos) { + bool is_used) { FibNode *n = parcMemory_AllocateAndClear(sizeof(FibNode)); parcAssertNotNull(n, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(FibNode)); @@ -53,22 +52,18 @@ FibNode *_createNode(FibNode *left, FibNode *right, FibEntry *entry, n->left = left; n->right = right; n->entry = entry; - n->pos = pos; + n->is_used = is_used; return n; } -FIB *fib_Create() { +FIB *fib_Create(Forwarder *forwarder) { FIB *hicnFib = parcMemory_AllocateAndClear(sizeof(FIB)); parcAssertNotNull(hicnFib, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(FIB)); - hicnFib->root = - _createNode(NULL, NULL, NULL, - NULL_POS); // the pos will decrease going down in the trie - hicnFib->root->left = hicnFib->root; - hicnFib->root->right = hicnFib->root; - + hicnFib->forwarder = forwarder; + hicnFib->root = NULL; hicnFib->size = 0; return hicnFib; @@ -80,9 +75,12 @@ void _destroyNode(FibNode *n) { n = NULL; } -void _destroyFib(FIB *fib) { - // to be done - return; +void _destroyFib(FibNode *n) { + if(n != NULL){ + _destroyFib(n->right); + _destroyFib(n->left); + _destroyNode(n); + } } void fib_Destroy(FIB **fibPtr) { @@ -90,8 +88,8 @@ void fib_Destroy(FIB **fibPtr) { parcAssertNotNull(*fibPtr, "Parameter must dereference to non-null pointer"); FIB *fib = *fibPtr; + _destroyFib(fib->root); - _destroyFib(fib); parcMemory_Deallocate((void **)&fib); *fibPtr = NULL; } @@ -100,239 +98,319 @@ void fib_Add(FIB *fib, FibEntry *entry) { parcAssertNotNull(fib, "Parameter must be non-null"); parcAssertNotNull(entry, "Parameter must be non-null"); - NameBitvector *name = name_GetContentName(fibEntry_GetPrefix(entry)); + NameBitvector *new_prefix = name_GetContentName(fibEntry_GetPrefix(entry)); + uint32_t new_prefix_len = nameBitvector_GetLength(new_prefix); + FibNode * curr = fib->root; + FibNode * last = NULL; - //if the name len is 0, we add this entry on the root - if(nameBitvector_GetLength(name) == 0){ - fib->size++; - fib->root->entry = entry; - return; - } + NameBitvector *curr_name; + uint32_t curr_prefix_len; + uint32_t match_len; - // search the name - FibNode *prev = fib->root; - FibNode *curr; + while(curr != NULL){ + curr_name = name_GetContentName(fibEntry_GetPrefix(curr->entry)); - if (nameBitvector_testBit(name, MSB_POS)) { - curr = fib->root->right; - } else { - curr = fib->root->left; - } + match_len = nameBitvector_lpm(new_prefix, curr_name); + curr_prefix_len = nameBitvector_GetLength(curr_name); - while (prev->pos > curr->pos) { - prev = curr; - if (nameBitvector_testBit(name, curr->pos)) { + 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; + bool bit; + int res = nameBitvector_testBit(new_prefix, curr_prefix_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (fib_add)"); + if(bit) curr = curr->right; - } else { + else curr = curr->left; - } } - if (curr->entry != NULL && curr->pos != NULL_POS && - nameBitvector_Equals( - name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) { - // there is already an entry with this name - // do nothing. Before call ADD we should check - // if the node exists, and, in that case update it + //this is the root (empty trie) or an empty child + if(curr == NULL){ + FibNode * new_node = _createNode(NULL, NULL, entry, true); + if(last == NULL){ + fib->root = new_node; + }else{ + uint32_t last_prefix_len = nameBitvector_GetLength( + name_GetContentName(fibEntry_GetPrefix(last->entry))); + bool bit; + int res = nameBitvector_testBit(new_prefix, last_prefix_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (fib_add)"); + if(bit) + last->right = new_node; + else + last->left = new_node; + } + fib->size++; return; } - // if the name is not in the FIB search for the first different bit between - // the new name to add and the node found in the trie - uint8_t pos = MSB_POS; - if (curr->entry != NULL && curr->pos != NULL_POS){ - pos = nameBitvector_firstDiff( - name, name_GetContentName(fibEntry_GetPrefix(curr->entry))); + //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 NumberSet * next_hops = fibEntry_GetNexthops(entry); + unsigned size = (unsigned)fibEntry_NexthopCount(entry); + for(unsigned i = 0; i < size; i++) + fibEntry_AddNexthop(curr->entry,numberSet_GetItem(next_hops, i)); + } } - // reset pointer and search the insertion point - prev = fib->root; - if (nameBitvector_testBit(name, MSB_POS)) - curr = fib->root->right; - else - curr = fib->root->left; - - while (prev->pos > curr->pos && curr->pos > pos) { - prev = curr; - if (nameBitvector_testBit(name, curr->pos)) { - curr = curr->right; - } else { - curr = curr->left; + //key is prefix of the curr node (so new_prefix_len < curr_prefix_len) + if(new_prefix_len == match_len){ + FibNode * new_node = _createNode(NULL, NULL, entry, true); + if(last == NULL){ + fib->root = new_node; + }else{ + uint32_t last_prefix_len = nameBitvector_GetLength( + name_GetContentName(fibEntry_GetPrefix(last->entry))); + + bool bit; + int res = nameBitvector_testBit(new_prefix, last_prefix_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (fib_add)"); + if(bit) + last->right = new_node; + else + last->left = new_node; } + bool bit; + int res = nameBitvector_testBit(curr_name, match_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (fib_add)"); + if(bit) + new_node->right = curr; + else + new_node->left = curr; + fib->size++; + return; } - // insert the node - fib->size++; - FibNode *n = _createNode(NULL, NULL, entry, pos); - - if (nameBitvector_testBit(name, pos)) { - n->left = curr; - n->right = n; - } else { - n->left = n; - n->right = curr; + //in the last case we need to add an inner node + Name * inner_prefix = name_Copy(fibEntry_GetPrefix(entry)); + nameBitvector_clear(name_GetContentName(inner_prefix), match_len); + name_setLen(inner_prefix, match_len); + + FibEntry * inner_entry = fibEntry_Create(inner_prefix, SET_STRATEGY_LOADBALANCER, + fib->forwarder); + + FibNode * inner_node = _createNode(NULL, NULL, inner_entry, false); + FibNode * new_node = _createNode(NULL, NULL, entry, true); + + if(last == NULL){ + //we need to place the inner_node at the root + fib->root = inner_node; + }else{ + uint32_t last_prefix_len = nameBitvector_GetLength( + name_GetContentName(fibEntry_GetPrefix(last->entry))); + bool bit; + int res = nameBitvector_testBit(name_GetContentName(inner_prefix), + last_prefix_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (fib_add)"); + if(bit) + last->right = inner_node; + else + last->left = inner_node; } - uint8_t new_pos = prev->pos; - if (new_pos == NULL_POS) new_pos = MSB_POS; + bool bit; + int res = nameBitvector_testBit(new_prefix, match_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (fib_add)"); - if (nameBitvector_testBit(name, new_pos)) { - prev->right = n; - } else { - prev->left = n; + if(bit){ + inner_node -> left = curr; + inner_node ->right = new_node; + }else{ + inner_node -> left = new_node; + inner_node ->right = curr; } + fib->size ++; } FibEntry *fib_Contains(const FIB *fib, const Name *prefix) { parcAssertNotNull(fib, "Parameter must be non-null"); parcAssertNotNull(prefix, "Parameter must be non-null"); - NameBitvector *name = name_GetContentName(prefix); + NameBitvector *key_name = name_GetContentName(prefix); + uint32_t key_prefix_len = nameBitvector_GetLength(key_name); - //if prefix len is 0 it must be stored in the root. - //if the root entry is null we need to create it, otherwise - //we just need to add an other nexthop - if(nameBitvector_GetLength(name) == 0){ - return fib->root->entry; - } + FibNode * curr = fib->root; - // this is the same as the first part of the add function - // we cannnot call this function inside the add because - // we need the pointer prev and curr for the insertion + while(curr != NULL){ + NameBitvector *curr_name = + name_GetContentName(fibEntry_GetPrefix(curr->entry)); + uint32_t match_len = nameBitvector_lpm(key_name, curr_name); + uint32_t curr_prefix_len = nameBitvector_GetLength(curr_name); - FibNode *prev = fib->root; - FibNode *curr; + 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 (nameBitvector_testBit(name, MSB_POS)) - curr = fib->root->right; - else - curr = fib->root->left; + if(curr_prefix_len == key_prefix_len){ //== match_len + //this is an exact match + if(curr->is_used){ + //we found the key + return curr->entry; + }else{ + //the key does not exists + return NULL; + } + } - while (prev->pos > curr->pos) { - prev = curr; + bool bit; + int res = nameBitvector_testBit(key_name, curr_prefix_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (fib_contains)"); - if (nameBitvector_testBit(name, curr->pos)) { + if(bit) curr = curr->right; - } else { + else curr = curr->left; - } } - if (curr->entry != NULL && curr->pos != NULL_POS && - nameBitvector_Equals( - name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) { - return curr->entry; - } else { - return NULL; - } + return NULL; } -void _removeNode(FIB *fib, const Name *prefix) { +void _removeNode(FIB *fib, const Name *prefix){ parcAssertNotNull(fib, "Parameter must be non-null"); parcAssertNotNull(prefix, "Parameter must be non-null"); - FibNode *grand = NULL; // grandparent - FibNode *prev = - fib->root; // parent: it will points to curr of the next hop in the trie - FibNode *curr; // current node: the node to remove + NameBitvector *key_name = name_GetContentName(prefix); + uint32_t key_prefix_len = nameBitvector_GetLength(key_name); - NameBitvector *name = name_GetContentName(prefix); + FibNode * curr = fib->root; + FibNode * parent = NULL; + FibNode * grandpa = NULL; - if (nameBitvector_testBit(name, MSB_POS)) { - curr = fib->root->right; - } else { - curr = fib->root->left; - } + uint32_t match_len; + uint32_t curr_prefix_len; + while(curr != NULL){ + NameBitvector *curr_name = + name_GetContentName(fibEntry_GetPrefix(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; + } - // in the first loop we always search the node to remove - while (prev->pos > curr->pos) { - grand = prev; - prev = curr; + grandpa = parent; + parent = curr; - if (nameBitvector_testBit(name, curr->pos)) { + bool bit; + int res = nameBitvector_testBit(key_name, curr_prefix_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (_removeNode)"); + + if(bit) curr = curr->right; - } else { + else curr = curr->left; - } } - if (!nameBitvector_Equals( - name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) { - // the node does not exists + if(curr == NULL || + !curr->is_used || + (curr_prefix_len != key_prefix_len)){ + //the node does not exists return; } - // search for the real parent of curr (*tmpPrev) - // prev points to curr or next node in the trie - // this is because of the loopback links - - FibNode *tmpPrev = fib->root; - FibNode *tmpCurr; - - if (nameBitvector_testBit(name, MSB_POS)) { - tmpCurr = fib->root->right; - } else { - tmpCurr = fib->root->left; - } - - // here we compare pointer so we are sure to stop at the right potion - while (tmpCurr != curr) { - tmpPrev = tmpCurr; - - if (nameBitvector_testBit(name, tmpCurr->pos)) { - tmpCurr = tmpCurr->right; - } else { - tmpCurr = tmpCurr->left; - } + //curr has 2 children, leave it there and mark it as inner + if(curr->right != NULL && curr->left != NULL){ + curr->is_used = false; + fib->size--; + return; } - // now curr is the node to remove and tmpPrev is the real parent of curr - - if (curr == prev) { - // this is the case where curr is a leaf node - FibNode *next; // child of curr (the loopback) - - if (nameBitvector_testBit(name, curr->pos)) { - next = curr->left; - } else { - next = curr->right; + //curr has no children + if(curr->right == NULL && curr->left == NULL){ + if (parent == NULL){ + //curr is the root and is the only node in the fib + fib->root = NULL; + fib->size--; + _destroyNode(curr); + return; } - - if (nameBitvector_testBit(name, tmpPrev->pos)) { - tmpPrev->right = next; - } else { - tmpPrev->left = next; + if(grandpa == NULL){ + //parent is the root + if(fib->root->left == curr) + fib->root->left = NULL; + else + fib->root->right = NULL; + fib->size--; + _destroyNode(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 + FibNode * tmp; + if(parent->right == curr) + tmp = parent->left; + else + tmp = parent->right; + + if(grandpa->right == parent) + grandpa->right = tmp; + else + grandpa->left = tmp; - } else { - // curr is an internal node - FibNode *next; // child of prev (loopback) - - if (nameBitvector_testBit(name, prev->pos)) { - next = prev->left; - } else { - next = prev->right; + fib->size--; + _destroyNode(curr); + _destroyNode(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--; + _destroyNode(curr); + return; + } - if (nameBitvector_testBit(name, grand->pos)) { - grand->right = next; - } else { - grand->left = next; + //curr has one child + if(curr->right != NULL || curr->left != NULL){ + if(parent == NULL){ + //curr is the root + if(fib->root->right != NULL) + fib->root = fib->root->right; + else + fib->root = fib->root->left; + fib->size--; + _destroyNode(curr); + return; } + //attach the child of curr to parent + FibNode * tmp; + if(curr->right != NULL) + tmp = curr->right; + else + tmp = curr->left; - if (nameBitvector_testBit(name, tmpPrev->pos)) { - tmpPrev->right = prev; - } else { - tmpPrev->left = prev; - } + if(parent->right == curr) + parent->right = tmp; + else + parent->left = tmp; - prev->left = curr->left; - prev->right = curr->right; - prev->pos = curr->pos; + fib->size--; + _destroyNode(curr); + return; } - - fib->size--; - _destroyNode(curr); } void fib_Remove(FIB *fib, const Name *name, unsigned connId) { @@ -346,60 +424,34 @@ void fib_Remove(FIB *fib, const Name *name, unsigned connId) { } fibEntry_RemoveNexthopByConnectionId(entry, connId); - if (fibEntry_NexthopCount(entry) == 0) { - //if the len is 0, just release the fibEntry on the root node - if(nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(entry))) == 0){ - parcAssertTrue(entry == fib->root->entry, - "prefix len == 0, entry is not in the FIB root"); - fib->size--; - fibEntry_Release(&entry); - fib->root->entry = NULL; - } else { - _removeNode(fib, name); - } - } + if (fibEntry_NexthopCount(entry) == 0) + _removeNode(fib, name); + } -void _removeConnectionId(FibNode *n, unsigned pos, unsigned connectionId, +void _removeConnectionId(FibNode *n, unsigned connectionId, FibEntryList *list) { - if (n->pos < pos) { - fibEntry_RemoveNexthopByConnectionId(n->entry, connectionId); - if (fibEntry_NexthopCount(n->entry) == 0) { - fibEntryList_Append(list, n->entry); + if(n != NULL){ + if(n->is_used){ + fibEntry_RemoveNexthopByConnectionId(n->entry, connectionId); + if (fibEntry_NexthopCount(n->entry) == 0) { + fibEntryList_Append(list, n->entry); + } } - _removeConnectionId(n->left, n->pos, connectionId, list); - _removeConnectionId(n->right, n->pos, connectionId, list); + _removeConnectionId(n->right, connectionId, list); + _removeConnectionId(n->left, connectionId, list); } } void fib_RemoveConnectionId(FIB *fib, unsigned connectionId) { parcAssertNotNull(fib, "Parameter must be non-null"); - // 0 - remove the connection id from the root - // 1 - we vist the tree to remove the connection id - // 2 - during the visit we collect the fib entry with 0 nexthop - // 3 - after the visit we remove this entries - - if(fib->root->entry){ - fibEntry_RemoveNexthopByConnectionId(fib->root->entry, connectionId); - if(fibEntry_NexthopCount(fib->root->entry) == 0){ - fib->size--; - fibEntry_Release(&fib->root->entry); - fib->root->entry = NULL; - } - } - - FibEntryList *list = fibEntryList_Create(); - - _removeConnectionId(fib->root->left, fib->root->pos, connectionId, list); - _removeConnectionId(fib->root->right, fib->root->pos, connectionId, list); + FibEntryList *list = fibEntryList_Create(); + _removeConnectionId(fib->root, connectionId, list); for (int i = 0; i < fibEntryList_Length(list); i++) { _removeNode(fib, fibEntry_GetPrefix(fibEntryList_Get(list, i))); } - - fibEntryList_Destroy(&list); } size_t fib_Length(const FIB *fib) { @@ -407,143 +459,82 @@ size_t fib_Length(const FIB *fib) { return fib->size; } -FibEntry *fib_Match(const FIB *fib, const Message *interestMessage) { +FibEntry *fib_MatchMessage(const FIB *fib, const Message *interestMessage) { parcAssertNotNull(fib, "Parameter must be non-null"); parcAssertNotNull(interestMessage, "Parameter must be non-null"); + return fib_MatchBitvector(fib, name_GetContentName( + message_GetName(interestMessage))); +} - NameBitvector *name = name_GetContentName(message_GetName(interestMessage)); - - FibNode *prev = fib->root; - FibNode *curr; - - FibNode *match = NULL; - unsigned len = 0; - - if (nameBitvector_testBit(name, MSB_POS)) - curr = fib->root->right; - else - curr = fib->root->left; - - while (prev->pos > curr->pos) { - prev = curr; - - if (curr->entry != NULL && curr->pos != NULL_POS) { - if (nameBitvector_StartsWith( - name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) && - nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(curr->entry))) > len) { - match = curr; - len = nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(curr->entry))); - } - } - - if (nameBitvector_testBit(name, curr->pos)) - curr = curr->right; - else - curr = curr->left; - } - - if (curr->entry != NULL && curr->pos != NULL_POS) { - if (nameBitvector_StartsWith( - name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) && - nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(curr->entry))) > len) { - match = curr; - len = nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(curr->entry))); - } - } - - if (match != NULL && match->entry != NULL) { - return match->entry; - } else { - //if there is a default route, return it. - //the dafualt route is in the route - return fib->root->entry; - } +FibEntry *fib_MatchName(const FIB *fib, const Name *name) { + parcAssertNotNull(fib, "Parameter must be non-null"); + parcAssertNotNull(name, "Parameter must be non-null"); + return fib_MatchBitvector(fib, name_GetContentName(name)); } -#ifdef WITH_MAPME -FibEntry *fib_LPM(const FIB *fib, const Name * prefix) { +FibEntry *fib_MatchBitvector(const FIB *fib, const NameBitvector *name){ parcAssertNotNull(fib, "Parameter must be non-null"); - parcAssertNotNull(prefix, "Parameter must be non-null"); + parcAssertNotNull(name, "Parameter must be non-null"); - NameBitvector *name = name_GetContentName(prefix); + uint32_t key_prefix_len = nameBitvector_GetLength(name); - FibNode *prev = fib->root; - FibNode *curr; + FibNode * curr = fib->root; + FibNode * candidate = NULL; - FibNode *match = NULL; - unsigned len = 0; + while(curr != NULL){ + NameBitvector *curr_name = + name_GetContentName(fibEntry_GetPrefix(curr->entry)); + uint32_t match_len = nameBitvector_lpm(name, curr_name); + uint32_t curr_prefix_len = nameBitvector_GetLength(curr_name); - if (nameBitvector_testBit(name, MSB_POS)) - curr = fib->root->right; - else - curr = fib->root->left; + 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; + } - while (prev->pos > curr->pos) { - prev = curr; + if(curr->is_used) + candidate = curr; - if (curr->entry != NULL && curr->pos != NULL_POS) { - if (nameBitvector_StartsWith( - name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) && - nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(curr->entry))) > len) { - match = curr; - len = nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(curr->entry))); - } + //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; } - if (nameBitvector_testBit(name, curr->pos)) + bool bit; + int res = nameBitvector_testBit(name, curr_prefix_len, &bit); + parcAssertFalse(res < 0, "error testing name bit (fib_MatchBitvector)"); + + if(bit) curr = curr->right; else curr = curr->left; } - if (curr->entry != NULL && curr->pos != NULL_POS) { - if (nameBitvector_StartsWith( - name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) && - nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(curr->entry))) > len) { - match = curr; - len = nameBitvector_GetLength( - name_GetContentName(fibEntry_GetPrefix(curr->entry))); - } + if(candidate != NULL){ + return candidate->entry; } - if (match != NULL && match->entry != NULL) { - return match->entry; - } else { - //if there is a default route, return it. - //the dafualt route is in the route - return fib->root->entry; - } + return NULL; } -#endif /* WITH_MAPME */ - -void _collectFibEntries(FibNode *n, int pos, FibEntryList *list) { - if (n->pos < (unsigned)pos) { - fibEntryList_Append(list, n->entry); - _collectFibEntries(n->left, n->pos, list); - _collectFibEntries(n->right, n->pos, list); +void _collectFibEntries(FibNode *n, FibEntryList *list){ + if(n != NULL){ + if(n->is_used) + fibEntryList_Append(list, n->entry); + _collectFibEntries(n->right, list); + _collectFibEntries(n->left, list); } } FibEntryList *fib_GetEntries(const FIB *fib) { parcAssertNotNull(fib, "Parameter must be non-null"); - FibEntryList *list = fibEntryList_Create(); - if(fib->root->entry){ - fibEntryList_Append(list, fib->root->entry); - } - - _collectFibEntries(fib->root->left, fib->root->pos, list); - _collectFibEntries(fib->root->right, fib->root->pos, list); + _collectFibEntries(fib->root, list); return list; } diff --git a/hicn-light/src/hicn/processor/fib.h b/hicn-light/src/hicn/processor/fib.h index 8c03537fe..7507bb85c 100644 --- a/hicn-light/src/hicn/processor/fib.h +++ b/hicn-light/src/hicn/processor/fib.h @@ -35,11 +35,9 @@ void fib_Remove(FIB *fib, const Name *prefix, unsigned connId); void fib_RemoveConnectionId(FIB *fib, unsigned connectionId); -FibEntry *fib_Match(const FIB *fib, const Message *interestMessage); - -#ifdef WITH_MAPME -FibEntry *fib_LPM(const FIB *fib, const Name * name); -#endif /* WITH_MAPME */ +FibEntry *fib_MatchMessage(const FIB *fib, const Message *interestMessage); +FibEntry *fib_MatchName(const FIB *fib, const Name *name); +FibEntry *fib_MatchBitvector(const FIB *fib, const NameBitvector *name); size_t fib_Length(const FIB *fib); diff --git a/hicn-light/src/hicn/processor/messageProcessor.c b/hicn-light/src/hicn/processor/messageProcessor.c index 7b43543a3..456618269 100644 --- a/hicn-light/src/hicn/processor/messageProcessor.c +++ b/hicn-light/src/hicn/processor/messageProcessor.c @@ -576,7 +576,7 @@ static bool messageProcessor_ForwardViaFib(MessageProcessor *processor, static bool messageProcessor_ForwardViaFib(MessageProcessor *processor, Message *interestMessage) { #endif /* WITH_POLICY */ - FibEntry *fibEntry = fib_Match(processor->fib, interestMessage); + FibEntry *fibEntry = fib_MatchMessage(processor->fib, interestMessage); if (fibEntry == NULL) { return false; } -- cgit 1.2.3-korg