From 0a1c6b5565e20167d1f1f33a5a8b597f420b18b0 Mon Sep 17 00:00:00 2001 From: Jordan Augé Date: Fri, 26 Jul 2019 23:20:30 +0200 Subject: [HICN-252] Add per-application policy framework to hicn-light forwarder MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Change-Id: I0531cd7a7de179581295ae34766c81cd9cf3e172 Signed-off-by: Jordan Augé Signed-off-by: Mauro Sardara Co-authored-by: Mauro Sardara --- hicn-light/src/hicn/processor/fib.c | 117 +++++++++++++++++++++++++++++++++--- 1 file changed, 109 insertions(+), 8 deletions(-) (limited to 'hicn-light/src/hicn/processor/fib.c') diff --git a/hicn-light/src/hicn/processor/fib.c b/hicn-light/src/hicn/processor/fib.c index 19e4db60b..7cb94d4ba 100644 --- a/hicn-light/src/hicn/processor/fib.c +++ b/hicn-light/src/hicn/processor/fib.c @@ -81,7 +81,6 @@ void _destroyNode(FibNode *n) { } void _destroyFib(FIB *fib) { - // XXX // to be done return; } @@ -103,6 +102,13 @@ void fib_Add(FIB *fib, FibEntry *entry) { NameBitvector *name = name_GetContentName(fibEntry_GetPrefix(entry)); + //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; + } + // search the name FibNode *prev = fib->root; FibNode *curr; @@ -122,7 +128,7 @@ void fib_Add(FIB *fib, FibEntry *entry) { } } - if (curr->entry != NULL && + 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 @@ -134,9 +140,10 @@ void fib_Add(FIB *fib, FibEntry *entry) { // 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) + if (curr->entry != NULL && curr->pos != NULL_POS){ pos = nameBitvector_firstDiff( name, name_GetContentName(fibEntry_GetPrefix(curr->entry))); + } // reset pointer and search the insertion point prev = fib->root; @@ -182,6 +189,13 @@ FibEntry *fib_Contains(const FIB *fib, const Name *prefix) { NameBitvector *name = name_GetContentName(prefix); + //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; + } + // 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 @@ -204,7 +218,7 @@ FibEntry *fib_Contains(const FIB *fib, const Name *prefix) { } } - if (curr->entry != NULL && + if (curr->entry != NULL && curr->pos != NULL_POS && nameBitvector_Equals( name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) { return curr->entry; @@ -333,7 +347,17 @@ void fib_Remove(FIB *fib, const Name *name, unsigned connId) { fibEntry_RemoveNexthopByConnectionId(entry, connId); if (fibEntry_NexthopCount(entry) == 0) { - _removeNode(fib, name); + //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); + } } } @@ -352,10 +376,20 @@ void _removeConnectionId(FibNode *n, unsigned pos, unsigned connectionId, 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); @@ -393,7 +427,7 @@ FibEntry *fib_Match(const FIB *fib, const Message *interestMessage) { while (prev->pos > curr->pos) { prev = curr; - if (curr->entry != NULL) { + if (curr->entry != NULL && curr->pos != NULL_POS) { if (nameBitvector_StartsWith( name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) && nameBitvector_GetLength( @@ -410,7 +444,7 @@ FibEntry *fib_Match(const FIB *fib, const Message *interestMessage) { curr = curr->left; } - if (curr->entry != NULL) { + if (curr->entry != NULL && curr->pos != NULL_POS) { if (nameBitvector_StartsWith( name, name_GetContentName(fibEntry_GetPrefix(curr->entry))) && nameBitvector_GetLength( @@ -424,10 +458,73 @@ FibEntry *fib_Match(const FIB *fib, const Message *interestMessage) { if (match != NULL && match->entry != NULL) { return match->entry; } else { - return NULL; + //if there is a default route, return it. + //the dafualt route is in the route + return fib->root->entry; } } +#ifdef WITH_MAPME + +FibEntry *fib_LPM(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); + + 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; + } +} + +#endif /* WITH_MAPME */ + void _collectFibEntries(FibNode *n, int pos, FibEntryList *list) { if (n->pos < (unsigned)pos) { fibEntryList_Append(list, n->entry); @@ -441,6 +538,10 @@ FibEntryList *fib_GetEntries(const FIB *fib) { 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); -- cgit 1.2.3-korg