summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--hicn-light/src/hicn/core/mapMe.c4
-rw-r--r--hicn-light/src/hicn/core/name.c28
-rw-r--r--hicn-light/src/hicn/core/name.h18
-rw-r--r--hicn-light/src/hicn/core/nameBitvector.c137
-rw-r--r--hicn-light/src/hicn/core/nameBitvector.h10
-rw-r--r--hicn-light/src/hicn/processor/fib.c657
-rw-r--r--hicn-light/src/hicn/processor/fib.h8
-rw-r--r--hicn-light/src/hicn/processor/messageProcessor.c2
8 files changed, 417 insertions, 447 deletions
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
@@ -48,6 +48,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
*
*/
@@ -71,17 +76,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 <hicn/utils/commands.h>
-#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 <hicn/hicn-light/config.h>
#include <stdio.h>
+#include <hicn/core/forwarder.h>
#include <hicn/processor/fib.h>
#include <parc/algol/parc_Memory.h>
@@ -23,9 +24,6 @@
#include <parc/assert/parc_Assert.h>
-#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;
}