diff options
Diffstat (limited to 'hicn-light/src/processor')
20 files changed, 3184 insertions, 0 deletions
diff --git a/hicn-light/src/processor/CMakeLists.txt b/hicn-light/src/processor/CMakeLists.txt new file mode 100755 index 000000000..b7eeabe3b --- /dev/null +++ b/hicn-light/src/processor/CMakeLists.txt @@ -0,0 +1,40 @@ +# Copyright (c) 2017-2019 Cisco and/or its affiliates. +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at: +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +cmake_minimum_required(VERSION 3.5 FATAL_ERROR) + +list(APPEND HEADER_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/fibEntry.h + ${CMAKE_CURRENT_SOURCE_DIR}/fibEntryList.h + ${CMAKE_CURRENT_SOURCE_DIR}/messageProcessor.h + ${CMAKE_CURRENT_SOURCE_DIR}/hashTableFunction.h + ${CMAKE_CURRENT_SOURCE_DIR}/pit.h + ${CMAKE_CURRENT_SOURCE_DIR}/fib.h + ${CMAKE_CURRENT_SOURCE_DIR}/pitEntry.h + ${CMAKE_CURRENT_SOURCE_DIR}/pitVerdict.h + ${CMAKE_CURRENT_SOURCE_DIR}/pitStandard.h +) + +list(APPEND SOURCE_FILES + ${CMAKE_CURRENT_SOURCE_DIR}/hashTableFunction.c + ${CMAKE_CURRENT_SOURCE_DIR}/fib.c + ${CMAKE_CURRENT_SOURCE_DIR}/fibEntry.c + ${CMAKE_CURRENT_SOURCE_DIR}/fibEntryList.c + ${CMAKE_CURRENT_SOURCE_DIR}/messageProcessor.c + ${CMAKE_CURRENT_SOURCE_DIR}/pit.c + ${CMAKE_CURRENT_SOURCE_DIR}/pitEntry.c + ${CMAKE_CURRENT_SOURCE_DIR}/pitStandard.c +) + +set(SOURCE_FILES ${SOURCE_FILES} PARENT_SCOPE) +set(HEADER_FILES ${HEADER_FILES} PARENT_SCOPE) diff --git a/hicn-light/src/processor/fib.c b/hicn-light/src/processor/fib.c new file mode 100755 index 000000000..33d31fd8a --- /dev/null +++ b/hicn-light/src/processor/fib.c @@ -0,0 +1,448 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> + +#include <src/processor/fib.h> + +#include <parc/algol/parc_Memory.h> +#include <parc/algol/parc_Network.h> + +#include <parc/assert/parc_Assert.h> + +#define NULL_POS 128 +#define MSB_POS 127 + +struct node; +typedef struct node FibNode; + +struct node { + FibNode *left; + FibNode *right; + FibEntry *entry; + unsigned pos; +}; + +struct fib { + FibNode *root; + unsigned size; +}; + +// ===================================================== +// Public API + +FibNode *_createNode(FibNode *left, FibNode *right, FibEntry *entry, + unsigned pos) { + FibNode *n = parcMemory_AllocateAndClear(sizeof(FibNode)); + parcAssertNotNull(n, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(FibNode)); + + n->left = left; + n->right = right; + n->entry = entry; + n->pos = pos; + + return n; +} + +FIB *fib_Create() { + 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->size = 0; + + return hicnFib; +} + +void _destroyNode(FibNode *n) { + fibEntry_Release(&n->entry); + parcMemory_Deallocate((void **)&n); + n = NULL; +} + +void _destroyFib(FIB *fib) { + // XXX + // to be done + return; +} + +void fib_Destroy(FIB **fibPtr) { + parcAssertNotNull(fibPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*fibPtr, "Parameter must dereference to non-null pointer"); + + FIB *fib = *fibPtr; + + _destroyFib(fib); + parcMemory_Deallocate((void **)&fib); + *fibPtr = NULL; +} + +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)); + + // search the name + FibNode *prev = fib->root; + FibNode *curr; + + if (nameBitvector_testBit(name, MSB_POS)) { + curr = fib->root->right; + } else { + curr = fib->root->left; + } + + while (prev->pos > curr->pos) { + prev = curr; + if (nameBitvector_testBit(name, curr->pos)) { + curr = curr->right; + } else { + curr = curr->left; + } + } + + if (curr->entry != NULL && + 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 + 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) + pos = nameBitvector_firstDiff( + name, name_GetContentName(fibEntry_GetPrefix(curr->entry))); + + // 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; + } + } + + // 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; + } + + uint8_t new_pos = prev->pos; + if (new_pos == NULL_POS) new_pos = MSB_POS; + + if (nameBitvector_testBit(name, new_pos)) { + prev->right = n; + } else { + prev->left = n; + } +} + +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); + + // 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 + + FibNode *prev = fib->root; + FibNode *curr; + + if (nameBitvector_testBit(name, MSB_POS)) + curr = fib->root->right; + else + curr = fib->root->left; + + while (prev->pos > curr->pos) { + prev = curr; + + if (nameBitvector_testBit(name, curr->pos)) { + curr = curr->right; + } else { + curr = curr->left; + } + } + + if (curr->entry != NULL && + nameBitvector_Equals( + name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) { + return curr->entry; + } else { + return NULL; + } +} + +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 *name = name_GetContentName(prefix); + + if (nameBitvector_testBit(name, MSB_POS)) { + curr = fib->root->right; + } else { + curr = fib->root->left; + } + + // in the first loop we always search the node to remove + while (prev->pos > curr->pos) { + grand = prev; + prev = curr; + + if (nameBitvector_testBit(name, curr->pos)) { + curr = curr->right; + } else { + curr = curr->left; + } + } + + if (!nameBitvector_Equals( + name, name_GetContentName(fibEntry_GetPrefix(curr->entry)))) { + // 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; + } + } + + // 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; + } + + if (nameBitvector_testBit(name, tmpPrev->pos)) { + tmpPrev->right = next; + } else { + tmpPrev->left = next; + } + + } 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; + } + + if (nameBitvector_testBit(name, grand->pos)) { + grand->right = next; + } else { + grand->left = next; + } + + if (nameBitvector_testBit(name, tmpPrev->pos)) { + tmpPrev->right = prev; + } else { + tmpPrev->left = prev; + } + + prev->left = curr->left; + prev->right = curr->right; + prev->pos = curr->pos; + } + + fib->size--; + _destroyNode(curr); +} + +void fib_Remove(FIB *fib, const Name *name, unsigned connId) { + parcAssertNotNull(fib, "Parameter must be non-null"); + parcAssertNotNull(name, "Parameter must be non-null"); + + FibEntry *entry = fib_Contains(fib, name); + + if (entry == NULL) { + return; + } + + fibEntry_RemoveNexthopByConnectionId(entry, connId); + if (fibEntry_NexthopCount(entry) == 0) { + _removeNode(fib, name); + } +} + +void _removeConnectionId(FibNode *n, unsigned pos, unsigned connectionId, + FibEntryList *list) { + if (n->pos < pos) { + 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); + } +} + +void fib_RemoveConnectionId(FIB *fib, unsigned connectionId) { + parcAssertNotNull(fib, "Parameter must be non-null"); + + // 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 + + FibEntryList *list = fibEntryList_Create(); + + _removeConnectionId(fib->root->left, fib->root->pos, connectionId, list); + _removeConnectionId(fib->root->right, fib->root->pos, 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) { + parcAssertNotNull(fib, "Parameter must be non-null"); + return fib->size; +} + +FibEntry *fib_Match(const FIB *fib, const Message *interestMessage) { + parcAssertNotNull(fib, "Parameter must be non-null"); + parcAssertNotNull(interestMessage, "Parameter must be non-null"); + + 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) { + 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) { + 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 { + return NULL; + } +} + +void _collectFibEntries(FibNode *n, int pos, FibEntryList *list) { + if (n->pos < pos) { + fibEntryList_Append(list, n->entry); + _collectFibEntries(n->left, n->pos, list); + _collectFibEntries(n->right, n->pos, list); + } +} + +FibEntryList *fib_GetEntries(const FIB *fib) { + parcAssertNotNull(fib, "Parameter must be non-null"); + + FibEntryList *list = fibEntryList_Create(); + + _collectFibEntries(fib->root->left, fib->root->pos, list); + _collectFibEntries(fib->root->right, fib->root->pos, list); + + return list; +} diff --git a/hicn-light/src/processor/fib.h b/hicn-light/src/processor/fib.h new file mode 100755 index 000000000..4409419db --- /dev/null +++ b/hicn-light/src/processor/fib.h @@ -0,0 +1,43 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +#ifndef fib_h +#define fib_h + +#include <src/core/message.h> +#include <src/core/name.h> +#include <src/processor/fibEntry.h> +#include <src/processor/fibEntryList.h> + +struct fib; +typedef struct fib FIB; + +FIB *fib_Create(); + +void fib_Destroy(FIB **fibPtr); + +void fib_Add(FIB *fib, FibEntry *node); + +FibEntry *fib_Contains(const FIB *fib, const Name *prefix); + +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); + +size_t fib_Length(const FIB *fib); + +FibEntryList *fib_GetEntries(const FIB *fib); +#endif // fib_h diff --git a/hicn-light/src/processor/fibEntry.c b/hicn-light/src/processor/fibEntry.c new file mode 100755 index 000000000..bb877030f --- /dev/null +++ b/hicn-light/src/processor/fibEntry.c @@ -0,0 +1,223 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> + +#include <src/core/numberSet.h> +#include <src/processor/fibEntry.h> + +#include <src/core/nameBitvector.h> + +#include <src/strategies/loadBalancer.h> +#include <src/strategies/loadBalancerWithPD.h> +#include <src/strategies/rnd.h> +#include <src/strategies/rndSegment.h> +#include <src/strategies/strategyImpl.h> +#ifdef WITH_MAPME +#include <parc/algol/parc_HashMap.h> +#include <src/core/ticks.h> +#endif /* WITH_MAPME */ + +#include <parc/algol/parc_Memory.h> +#include <parc/assert/parc_Assert.h> + +#include <src/utils/commands.h> + +struct fib_entry { + Name *name; + unsigned refcount; + StrategyImpl *fwdStrategy; +#ifdef WITH_MAPME + void *userData; + void (*userDataRelease)(void **userData); +#endif /* WITH_MAPME */ +}; + +FibEntry *fibEntry_Create(Name *name, strategy_type fwdStrategy) { + FibEntry *fibEntry = parcMemory_AllocateAndClear(sizeof(FibEntry)); + parcAssertNotNull(fibEntry, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(FibEntry)); + fibEntry->name = name_Acquire(name); + + if (fwdStrategy) { + switch (fwdStrategy) { + case SET_STRATEGY_LOADBALANCER: + fibEntry->fwdStrategy = strategyLoadBalancer_Create(); + break; + + case SET_STRATEGY_RANDOM_PER_DASH_SEGMENT: + fibEntry->fwdStrategy = strategyRndSegment_Create(); + break; + + case SET_STRATEGY_LOADBALANCER_WITH_DELAY: + fibEntry->fwdStrategy = strategyLoadBalancerWithPD_Create(); + break; + + default: + // LB is the defualt strategy + fibEntry->fwdStrategy = strategyLoadBalancer_Create(); + // the LB strategy is the default one + // other strategies can be set using the appropiate function + break; + } + + } else { + fibEntry->fwdStrategy = strategyLoadBalancer_Create(); + } + + fibEntry->refcount = 1; + +#ifdef WITH_MAPME + fibEntry->userData = NULL; + fibEntry->userDataRelease = NULL; +#endif /* WITH_MAPME */ + + return fibEntry; +} + +FibEntry *fibEntry_Acquire(const FibEntry *fibEntry) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + FibEntry *copy = (FibEntry *)fibEntry; + copy->refcount++; + return copy; +} + +void fibEntry_Release(FibEntry **fibEntryPtr) { + FibEntry *fibEntry = *fibEntryPtr; + parcAssertTrue(fibEntry->refcount > 0, "Illegal state: refcount is 0"); + fibEntry->refcount--; + if (fibEntry->refcount == 0) { + name_Release(&fibEntry->name); + fibEntry->fwdStrategy->destroy(&(fibEntry->fwdStrategy)); +#ifdef WITH_MAPME + if (fibEntry->userData) { + fibEntry->userDataRelease(&fibEntry->userData); + } +#endif /* WITH_MAPME */ + parcMemory_Deallocate((void **)&fibEntry); + } + *fibEntryPtr = NULL; +} + +void fibEntry_SetStrategy(FibEntry *fibEntry, strategy_type strategy) { + StrategyImpl *fwdStrategyImpl; + + switch (strategy) { + case SET_STRATEGY_LOADBALANCER: + fwdStrategyImpl = strategyLoadBalancer_Create(); + break; + + case SET_STRATEGY_RANDOM_PER_DASH_SEGMENT: + fwdStrategyImpl = strategyRndSegment_Create(); + break; + + case SET_STRATEGY_LOADBALANCER_WITH_DELAY: + fwdStrategyImpl = strategyLoadBalancerWithPD_Create(); + break; + + default: + // LB is the defualt strategy + fwdStrategyImpl = strategyLoadBalancer_Create(); + // the LB strategy is the default one + // other strategies can be set using the appropiate function + break; + } + + const NumberSet *nexthops = fibEntry_GetNexthops(fibEntry); + unsigned size = fibEntry_NexthopCount(fibEntry); + for (unsigned i = 0; i < size; i++) { + fwdStrategyImpl->addNexthop(fwdStrategyImpl, + numberSet_GetItem(nexthops, i)); + } + fibEntry->fwdStrategy->destroy(&(fibEntry->fwdStrategy)); + fibEntry->fwdStrategy = fwdStrategyImpl; +} +void fibEntry_AddNexthop(FibEntry *fibEntry, unsigned connectionId) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + fibEntry->fwdStrategy->addNexthop(fibEntry->fwdStrategy, connectionId); +} + +void fibEntry_RemoveNexthopByConnectionId(FibEntry *fibEntry, + unsigned connectionId) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + fibEntry->fwdStrategy->removeNexthop(fibEntry->fwdStrategy, connectionId); +} + +size_t fibEntry_NexthopCount(const FibEntry *fibEntry) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + return fibEntry->fwdStrategy->countNexthops(fibEntry->fwdStrategy); +} + +const NumberSet *fibEntry_GetNexthops(const FibEntry *fibEntry) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + return fibEntry->fwdStrategy->returnNexthops(fibEntry->fwdStrategy); +} + +const NumberSet *fibEntry_GetNexthopsFromForwardingStrategy( + const FibEntry *fibEntry, const Message *interestMessage) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + return fibEntry->fwdStrategy->lookupNexthop(fibEntry->fwdStrategy, + interestMessage); +} + +void fibEntry_ReceiveObjectMessage(const FibEntry *fibEntry, + const NumberSet *egressId, + const Message *objectMessage, Ticks rtt) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + fibEntry->fwdStrategy->receiveObject(fibEntry->fwdStrategy, egressId, + objectMessage, rtt); +} + +void fibEntry_OnTimeout(const FibEntry *fibEntry, const NumberSet *egressId) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + fibEntry->fwdStrategy->onTimeout(fibEntry->fwdStrategy, egressId); +} + +Name *fibEntry_GetPrefix(const FibEntry *fibEntry) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + return fibEntry->name; + // return metisName_Acquire(fibEntry->name); +} + +strategy_type fibEntry_GetFwdStrategyType(const FibEntry *fibEntry) { + return fibEntry->fwdStrategy->getStrategy(fibEntry->fwdStrategy); +} + +StrategyImpl *fibEntry_GetFwdStrategy(const FibEntry *fibEntry) { + return fibEntry->fwdStrategy; +} + +#ifdef WITH_MAPME + +void fibEntry_AddNexthopByConnectionId(FibEntry *fibEntry, + unsigned connectionId) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + fibEntry->fwdStrategy->addNexthop(fibEntry->fwdStrategy, connectionId); +} + +void *fibEntry_getUserData(const FibEntry *fibEntry) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + return fibEntry->userData; +} + +void fibEntry_setUserData(FibEntry *fibEntry, const void *userData, + void (*userDataRelease)(void **)) { + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + fibEntry->userData = (void *)userData; + fibEntry->userDataRelease = userDataRelease; +} + +#endif /* WITH_MAPME */ diff --git a/hicn-light/src/processor/fibEntry.h b/hicn-light/src/processor/fibEntry.h new file mode 100755 index 000000000..3bcac3884 --- /dev/null +++ b/hicn-light/src/processor/fibEntry.h @@ -0,0 +1,143 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file fibEntry.h + * @brief A forwarding entry in the FIB table + * + * A Forwarding Information Base (FIB) entry (FibEntry) is a + * set of nexthops for a name. It also indicates the forwarding strategy. + * + * Each nexthop contains the ConnectionId assocaited with it. This could be + * something specific like a MAC address or point-to-point tunnel. Or, it + * could be something general like a MAC group address or ip multicast overlay. + * + * See strategy.h for a description of forwarding strategies. + * In short, a strategy is the algorithm used to select one or more nexthops + * from the set of available nexthops. + * + * Each nexthop also contains a void* to a forwarding strategy data container. + * This allows a strategy to keep proprietary information about each nexthop. + * + * + */ + +#ifndef fibEntry_h +#define fibEntry_h + +#include <src/core/name.h> +#include <src/strategies/strategyImpl.h> + +#ifdef WITH_MAPME +#include <parc/algol/parc_EventTimer.h> +#include <parc/algol/parc_Iterator.h> +#endif /* WITH_MAPME */ + +struct fib_entry; +typedef struct fib_entry FibEntry; + +FibEntry *fibEntry_Create(Name *name, strategy_type fwdStrategy); + +/** + * Decrements the reference count by one, and destroys the memory after last + * release + * + */ +void fibEntry_Release(FibEntry **fibEntryPtr); + +/** + * Returns a reference counted copy of the fib entry + * + * The reference count is increased by one. The returned value must be + * released via fibEnty_Release(). + * + * @param [in] fibEntry An allocated FibEntry + * + * @return non-null A reference counted copy of the fibEntry + * + */ +FibEntry *fibEntry_Acquire(const FibEntry *fibEntry); + +void fibEntry_SetStrategy(FibEntry *fibEntry, strategy_type strategy); + +void fibEntry_AddNexthop(FibEntry *fibEntry, unsigned connectionId); + +void fibEntry_RemoveNexthopByConnectionId(FibEntry *fibEntry, + unsigned connectionId); + +size_t fibEntry_NexthopCount(const FibEntry *fibEntry); + +/** + * @function fibEntry_GetNexthops + * @abstract Returns the nexthop set of the FIB entry. You must Acquire if it + * will be saved. + * @discussion + * Returns the next hop set for the FIB entry. + */ +const NumberSet *fibEntry_GetNexthops(const FibEntry *fibEntry); + +const NumberSet *fibEntry_GetNexthopsFromForwardingStrategy( + const FibEntry *fibEntry, const Message *interestMessage); + +void fibEntry_ReceiveObjectMessage(const FibEntry *fibEntry, + const NumberSet *egressId, + const Message *objectMessage, Ticks rtt); + +void fibEntry_OnTimeout(const FibEntry *fibEntry, const NumberSet *egressId); + +strategy_type fibEntry_GetFwdStrategyType(const FibEntry *fibEntry); + +StrategyImpl *fibEntry_GetFwdStrategy(const FibEntry *fibEntry); + +/** + * @function fibEntry_GetPrefix + * @abstract Returns a copy of the prefix. + * @return A reference counted copy that you must destroy + */ +Name *fibEntry_GetPrefix(const FibEntry *fibEntry); + +#ifdef WITH_MAPME + +/** + * @function fibEntry_AddNexthopByConnectionId + * @abstract Adds a next hop directly from the connection id. + * @param [in] fibEntry - Pointer to the FIB entry. + * @return The sequence number stored in the FIB entry. + */ +void fibEntry_AddNexthopByConnectionId(FibEntry *fibEntry, + unsigned connectionId); + +/** + * @function fibEntry_getUserData + * @abstract Returns user data associated to the FIB entry. + * @param [in] fibEntry - Pointer to the FIB entry. + * @return User data as a void pointer + */ +void *fibEntry_getUserData(const FibEntry *fibEntry); + +/** + * @function fibEntry_getUserData + * @abstract Associates user data and release callback to a FIB entry. + * @param [in] fibEntry - Pointer to the FIB entry. + * @param [in] userData - Generic pointer to user data + * @param [in@ userDataRelease - Callback used to release user data upon change + * of FIB entry removal. + */ +void fibEntry_setUserData(FibEntry *fibEntry, const void *userData, + void (*userDataRelease)(void **)); + +#endif /* WITH_MAPME */ + +#endif // fibEntry_h diff --git a/hicn-light/src/processor/fibEntryList.c b/hicn-light/src/processor/fibEntryList.c new file mode 100755 index 000000000..2221fa614 --- /dev/null +++ b/hicn-light/src/processor/fibEntryList.c @@ -0,0 +1,72 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> +#include <stdlib.h> + +#include <parc/algol/parc_ArrayList.h> +#include <parc/algol/parc_Memory.h> +#include <parc/assert/parc_Assert.h> +#include <src/processor/fibEntryList.h> + +struct fib_entry_list { + PARCArrayList *listOfFibEntries; +}; + +static void fibEntryList_ListDestroyer(void **voidPtr) { + FibEntry **entryPtr = (FibEntry **)voidPtr; + fibEntry_Release(entryPtr); +} + +FibEntryList *fibEntryList_Create() { + FibEntryList *fibEntryList = + parcMemory_AllocateAndClear(sizeof(FibEntryList)); + parcAssertNotNull(fibEntryList, + "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(FibEntryList)); + fibEntryList->listOfFibEntries = + parcArrayList_Create(fibEntryList_ListDestroyer); + return fibEntryList; +} + +void fibEntryList_Destroy(FibEntryList **listPtr) { + parcAssertNotNull(listPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*listPtr, "Parameter must dereference to non-null pointer"); + + FibEntryList *list = *listPtr; + parcArrayList_Destroy(&list->listOfFibEntries); + parcMemory_Deallocate((void **)&list); + listPtr = NULL; +} + +void fibEntryList_Append(FibEntryList *list, FibEntry *fibEntry) { + parcAssertNotNull(list, "Parameter list must be non-null pointer"); + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null pointer"); + + FibEntry *copy = fibEntry_Acquire(fibEntry); + parcArrayList_Add(list->listOfFibEntries, copy); +} + +size_t fibEntryList_Length(const FibEntryList *list) { + parcAssertNotNull(list, "Parameter list must be non-null pointer"); + return parcArrayList_Size(list->listOfFibEntries); +} + +const FibEntry *fibEntryList_Get(const FibEntryList *list, size_t index) { + parcAssertNotNull(list, "Parameter list must be non-null pointer"); + FibEntry *entry = parcArrayList_Get(list->listOfFibEntries, index); + return entry; +} diff --git a/hicn-light/src/processor/fibEntryList.h b/hicn-light/src/processor/fibEntryList.h new file mode 100755 index 000000000..0f6066435 --- /dev/null +++ b/hicn-light/src/processor/fibEntryList.h @@ -0,0 +1,96 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file fibEntryList.h + * @brief A typesafe list of FibEntry + * + * <#Detailed Description#> + * + */ + +#ifndef fibEntryList_h +#define fibEntryList_h + +#include <src/processor/fibEntry.h> + +struct fib_entry_list; +typedef struct fib_entry_list FibEntryList; + +/** + * Creates an emtpy FIB entry list + * + * Must be destroyed with fibEntryList_Destroy. + * + * @retval non-null An allocated FibEntryList + * @retval null An error + * + * Example: + * @code + * <#example#> + * @endcode + */ +FibEntryList *fibEntryList_Create(void); + +/** + * @function FibEntryList_Detroy + * @abstract Destroys the list and all entries. + * @discussion + * <#Discussion#> + * + * @param <#param1#> + */ +void fibEntryList_Destroy(FibEntryList **listPtr); + +/** + * @function fibEntryList_Append + * @abstract Will store a reference counted copy of the entry. + * @discussion + * Will create and store a reference counted copy. You keep ownership + * of the parameter <code>fibEntry</code>. + * + * @param <#param1#> + * @return <#return#> + */ +void fibEntryList_Append(FibEntryList *list, FibEntry *fibEntry); + +/** + * Returns the number of entries in the list + * + * <#Paragraphs Of Explanation#> + * + * @param [in] list An allocated FibEntryList + * + * @retval number The number of entries in the list + * + * Example: + * @code + * <#example#> + * @endcode + */ +size_t fibEntryList_Length(const FibEntryList *list); + +/** + * @function fibEntryList_Get + * @abstract Gets an element. This is the internal reference, do not destroy. + * @discussion + * Returns an internal reference from the list. You must not destroy it. + * Will assert if you go off the end of the list. + * + * @param <#param1#> + * @return <#return#> + */ +const FibEntry *fibEntryList_Get(const FibEntryList *list, size_t index); +#endif // fibEntryList_h diff --git a/hicn-light/src/processor/hashTableFunction.c b/hicn-light/src/processor/hashTableFunction.c new file mode 100755 index 000000000..6e70ef91a --- /dev/null +++ b/hicn-light/src/processor/hashTableFunction.c @@ -0,0 +1,47 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> + +#include <parc/algol/parc_Hash.h> +#include <parc/algol/parc_Memory.h> + +#include <src/core/message.h> +#include <src/processor/hashTableFunction.h> + +#include <parc/assert/parc_Assert.h> + +// ====================================================================== +// Hash table key functions +// We use a Message as the key data type + +bool hashTableFunction_MessageNameEquals(const void *messageA, + const void *messageB) { + const Message *a = (const Message *)messageA; + const Message *b = (const Message *)messageB; + + return name_Equals(message_GetName(a), message_GetName(b)); +} + +HashCodeType hashTableFunction_MessageNameHashCode(const void *messageA) { + const Message *message = (const Message *)messageA; + Name *name = message_GetName(message); + + // we want the cumulative hash for the whole name + uint32_t hash = name_HashCode(name); + + return hash; +}
\ No newline at end of file diff --git a/hicn-light/src/processor/hashTableFunction.h b/hicn-light/src/processor/hashTableFunction.h new file mode 100755 index 000000000..eb9989086 --- /dev/null +++ b/hicn-light/src/processor/hashTableFunction.h @@ -0,0 +1,73 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file hashTableFunction.h + * @brief These functions are used in PARCHashCodeTables by the + * MatchingRulesTable and ContentStore and PIT. They perform the equality + * and has generation needed by the PARCHashCodeTable. + * + */ +#ifndef hashTableFunction_h +#define hashTableFunction_h + +#include <parc/algol/parc_HashCodeTable.h> + +// ========================================================== +// These functions operate on a message as the key in the HashTable. +// The functions use void * rather than message instances in the function +// signature because it is using generic has code tables from PARC Library + +/** + * Determine if the Names of two `message` instances are equal. + * + * The following equivalence relations on non-null `message` instances are + * maintained: + * + * * It is reflexive: for any non-null reference value x, + * `hashTableFunction_MessageNameEquals(x, x)` must return true. + * + * * It is symmetric: for any non-null reference values x and y, + * `message_Equals(x, y)` must return true if and only if + * `hashTableFunction_MessageNameEquals(y, x)` returns true. + * + * * It is transitive: for any non-null reference values x, y, and z, if + * `hashTableFunction_MessageNameEquals(x, y)` returns true and + * `hashTableFunction_MessageNameEquals(y, z)` returns true, + * then `hashTableFunction_MessageNameEquals(x, z)` must return true. + * + * * It is consistent: for any non-null reference values x and y, multiple + * invocations of `hashTableFunction_MessageNameEquals(x, y)` consistently + * return true or consistently return false. + * + * * For any non-null reference value x, + * `hashTableFunction_MessageNameEquals(x, NULL)` must return false. + * + * @param a A pointer to a `message` instance. + * @param b A pointer to a `message` instance. + * @return true if the names of the two `message` instances are equal. + */ +bool hashTableFunction_MessageNameEquals(const void *messageA, + const void *messageB); + +/** + * @function hashTableFunction_NameHashCode + * @abstract Computes the hash of the entire name in a message + * + * @param messageA is a message + * @return A non-cryptographic hash of Name + */ +HashCodeType hashTableFunction_MessageNameHashCode(const void *messageA); +#endif // hashTableFunction_h
\ No newline at end of file diff --git a/hicn-light/src/processor/matchingRulesTable.c b/hicn-light/src/processor/matchingRulesTable.c new file mode 100755 index 000000000..56e59c29e --- /dev/null +++ b/hicn-light/src/processor/matchingRulesTable.c @@ -0,0 +1,132 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> + +#include <parc/algol/parc_Hash.h> +#include <parc/algol/parc_Memory.h> + +#include <parc/assert/parc_Assert.h> +#include <src/processor/hashTableFunction.h> +#include <src/processor/matchingRulesTable.h> + +struct matching_rules_table { + // using this wrapper we can manatain multiple hash tables indexed in + // different ways + // for now we use only a table indexed by name + + PARCHashCodeTable *tableByName; + PARCHashCodeTable_Destroyer dataDestroyer; +}; + +static PARCHashCodeTable *matchingRulesTable_GetTableForMessage( + const MatchingRulesTable *pit, const Message *interestMessage); + +// ====================================================================== + +MatchingRulesTable *matchingRulesTable_Create( + PARCHashCodeTable_Destroyer dataDestroyer) { + size_t initialSize = 65535; + + MatchingRulesTable *table = + parcMemory_AllocateAndClear(sizeof(MatchingRulesTable)); + parcAssertNotNull(table, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(MatchingRulesTable)); + table->dataDestroyer = dataDestroyer; + + table->tableByName = parcHashCodeTable_Create_Size( + hashTableFunction_MessageNameEquals, + hashTableFunction_MessageNameHashCode, NULL, dataDestroyer, initialSize); + + return table; +} + +void matchingRulesTable_Destroy(MatchingRulesTable **tablePtr) { + parcAssertNotNull(tablePtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*tablePtr, + "Parameter must dereference to non-null pointer"); + + MatchingRulesTable *table = *tablePtr; + + parcHashCodeTable_Destroy(&table->tableByName); + + parcMemory_Deallocate((void **)&table); + *tablePtr = NULL; +} + +void *matchingRulesTable_Get(const MatchingRulesTable *rulesTable, + const Message *message) { + parcAssertNotNull(rulesTable, "Parameter rulesTable must be non-null"); + parcAssertNotNull(message, "Parameter message must be non-null"); + + PARCHashCodeTable *hashTable = + matchingRulesTable_GetTableForMessage(rulesTable, message); + return parcHashCodeTable_Get(hashTable, message); +} + +PARCArrayList *matchingRulesTable_GetUnion(const MatchingRulesTable *table, + const Message *message) { + PARCArrayList *list = parcArrayList_Create_Capacity(NULL, NULL, 3); + + void *dataByName = parcHashCodeTable_Get(table->tableByName, message); + if (dataByName) { + parcArrayList_Add(list, dataByName); + } + + return list; +} + +void matchingRulesTable_RemoveFromBest(MatchingRulesTable *rulesTable, + const Message *message) { + parcAssertNotNull(rulesTable, "Parameter rulesTable must be non-null"); + parcAssertNotNull(message, "Parameter message must be non-null"); + + PARCHashCodeTable *hashTable = + matchingRulesTable_GetTableForMessage(rulesTable, message); + parcHashCodeTable_Del(hashTable, message); +} + +void matchingRulesTable_RemoveFromAll(MatchingRulesTable *rulesTable, + const Message *message) { + parcAssertNotNull(rulesTable, "Parameter rulesTable must be non-null"); + parcAssertNotNull(message, "Parameter message must be non-null"); + + parcHashCodeTable_Del(rulesTable->tableByName, message); +} + +bool matchingRulesTable_AddToBestTable(MatchingRulesTable *rulesTable, + Message *key, void *data) { + parcAssertNotNull(rulesTable, "Parameter rulesTable must be non-null"); + parcAssertNotNull(key, "Parameter key must be non-null"); + parcAssertNotNull(data, "Parameter data must be non-null"); + + PARCHashCodeTable *hashTable = + matchingRulesTable_GetTableForMessage(rulesTable, key); + + bool success = parcHashCodeTable_Add(hashTable, key, data); + + return success; +} + +// ======================================================================================== + +static PARCHashCodeTable *matchingRulesTable_GetTableForMessage( + const MatchingRulesTable *pit, const Message *interestMessage) { + PARCHashCodeTable *table; + table = pit->tableByName; + + return table; +} diff --git a/hicn-light/src/processor/matchingRulesTable.h b/hicn-light/src/processor/matchingRulesTable.h new file mode 100755 index 000000000..96d099430 --- /dev/null +++ b/hicn-light/src/processor/matchingRulesTable.h @@ -0,0 +1,113 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @header matchingRulesTable + * @abstract A generic table (void *) that matches a Message + * @discussion + * Matching is done based on Name + * + * When used in the PIT, one calls + * <code>matchingRulesTable_AddToBestTable()</code> to add an interest to the + * "best" (i.e. most restrictive match) table, then calls + * <code>matchingRulesTable_GetUnion()</code> on a content object to match + * against all of them. + * + * When used in a ContentStore, one calls + * <code>matchingRulesTable_AddToAllTables()</code> to index a Content Object in + * all the tables. one then calls <code>matchingRulesTable_Get()</code> with an + * Interest to do the "best" matching (i.e by hash first, then keyid, then just + * by name). + * + */ + +#ifndef matchingRulesTable_h +#define matchingRulesTable_h + +#include <parc/algol/parc_ArrayList.h> +#include <parc/algol/parc_HashCodeTable.h> +#include <src/core/message.h> + +struct matching_rules_table; +typedef struct matching_rules_table MatchingRulesTable; + +/** + * Creates a MatchigRulesTable and specifies the function to call to de-allocate + * an entry + * + * The datadestroyer will be called when an entry is removed from a table. It + * may be NULL. + */ +MatchingRulesTable *matchingRulesTable_Create( + PARCHashCodeTable_Destroyer dataDestroyer); + +/** + * Destroys the table and removes all stored elements. + * + */ +void matchingRulesTable_Destroy(MatchingRulesTable **tablePtr); + +/** + * @function matchingRulesTable_Get + * @abstract Returns the data item that best matches the message. + * @discussion + * Indexed by NameAndContentObjectHash, NameAndKeyId, and Name, in that order. + * + * @return NULL if nothing matches, otherwise the stored value + */ +void *matchingRulesTable_Get(const MatchingRulesTable *table, + const Message *message); + +/** + * @function matchingRulesTable_GetUnion + * @abstract Returns matching data items from all index tables. + * @discussion + * The PARCArrayList does not have an item destructor, so destroying it will + * not affect the underlying data. + * + * @return Will not be NULL, but may be empty + */ +PARCArrayList *matchingRulesTable_GetUnion(const MatchingRulesTable *table, + const Message *message); + +/** + * @function matchingRulesTable_Add + * @abstract Adds the data to the best table + * @discussion + * The key must be derived from the data and destroyed when the data is + * destroyed. Only the data destroyer is called. + * + * No duplicates are allowed, will return false if not added. + * + * @return true if unique key and added, false if duplicate and no action taken. + */ +bool matchingRulesTable_AddToBestTable(MatchingRulesTable *rulesTable, + Message *key, void *data); + +/** + * @function matchingRulesTable_Remove + * @abstract Removes the matching entry from the best match table, calling the + * destroyer on the data. + */ +void matchingRulesTable_RemoveFromBest(MatchingRulesTable *rulesTable, + const Message *message); + +/** + * @function matchingRulesTable_RemoveFromAll + * @abstract Removes the message from all tables + */ +void matchingRulesTable_RemoveFromAll(MatchingRulesTable *rulesTable, + const Message *message); +#endif // matchingRulesTable_h diff --git a/hicn-light/src/processor/messageProcessor.c b/hicn-light/src/processor/messageProcessor.c new file mode 100755 index 000000000..8c03ee739 --- /dev/null +++ b/hicn-light/src/processor/messageProcessor.c @@ -0,0 +1,742 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> +#include <string.h> + +#include <parc/algol/parc_ArrayList.h> +#include <parc/algol/parc_Memory.h> +#include <src/processor/messageProcessor.h> + +#include <src/processor/fib.h> +#include <src/processor/pitStandard.h> + +#include <src/content_store/contentStoreInterface.h> +#include <src/content_store/contentStoreLRU.h> + +#include <src/strategies/loadBalancer.h> +#include <src/strategies/loadBalancerWithPD.h> +#include <src/strategies/rnd.h> +#include <src/strategies/rndSegment.h> +#include <src/strategies/strategyImpl.h> + +#include <src/io/streamConnection.h> +#include <src/io/udpListener.h> + +#include <parc/assert/parc_Assert.h> + +#include <src/utils/commands.h> +#include <src/utils/utils.h> + +#include <src/utils/address.h> + +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +typedef struct processor_stats { + uint32_t countReceived; + uint32_t countInterestsReceived; + uint32_t countObjectsReceived; + + uint32_t countInterestsAggregated; + + uint32_t countDropped; + uint32_t countInterestsDropped; + uint32_t countDroppedNoRoute; + uint32_t countDroppedNoReversePath; + + uint32_t countDroppedConnectionNotFound; + uint32_t countObjectsDropped; + + uint32_t countSendFailures; + uint32_t countInterestForwarded; + uint32_t countObjectsForwarded; + uint32_t countInterestsSatisfiedFromStore; + + uint32_t countDroppedNoHopLimit; + uint32_t countDroppedZeroHopLimitFromRemote; + uint32_t countDroppedZeroHopLimitToRemote; +} _ProcessorStats; + +struct message_processor { + Forwarder *forwarder; + Logger *logger; + + PIT *pit; + ContentStoreInterface *contentStore; + FIB *fib; + + bool store_in_cache; + bool serve_from_cache; + + _ProcessorStats stats; +}; + +static void messageProcessor_Drop(MessageProcessor *processor, + Message *message); +static void messageProcessor_ReceiveInterest(MessageProcessor *processor, + Message *interestMessage); +static void messageProcessor_ReceiveContentObject(MessageProcessor *processor, + Message *objectMessage); +static unsigned messageProcessor_ForwardToNexthops(MessageProcessor *processor, + Message *message, + const NumberSet *nexthops); + +static void messageProcessor_ForwardToInterfaceId(MessageProcessor *processor, + Message *message, + unsigned interfaceId); + +// ============================================================ +// Public API + +MessageProcessor *messageProcessor_Create(Forwarder *forwarder) { + size_t objectStoreSize = + configuration_GetObjectStoreSize(forwarder_GetConfiguration(forwarder)); + + MessageProcessor *processor = + parcMemory_AllocateAndClear(sizeof(MessageProcessor)); + parcAssertNotNull(processor, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(MessageProcessor)); + memset(processor, 0, sizeof(MessageProcessor)); + + processor->forwarder = forwarder; + processor->logger = logger_Acquire(forwarder_GetLogger(forwarder)); + processor->pit = pitStandard_Create(forwarder); + + processor->fib = fib_Create(); + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "MessageProcessor %p created", (void *)processor); + } + + ContentStoreConfig contentStoreConfig = { + .objectCapacity = objectStoreSize, + }; + + processor->contentStore = + contentStoreLRU_Create(&contentStoreConfig, processor->logger); + + // the two flags for the cache are set to true by default. If the cache + // is active it always work as expected unless the use modifies this + // values using controller + processor->store_in_cache = true; + processor->serve_from_cache = true; + + return processor; +} + +void messageProcessor_SetContentObjectStoreSize( + MessageProcessor *processor, size_t maximumContentStoreSize) { + parcAssertNotNull(processor, "Parameter processor must be non-null"); + contentStoreInterface_Release(&processor->contentStore); + + ContentStoreConfig contentStoreConfig = {.objectCapacity = + maximumContentStoreSize}; + + processor->contentStore = + contentStoreLRU_Create(&contentStoreConfig, processor->logger); +} + +void messageProcessor_ClearCache(MessageProcessor *processor) { + parcAssertNotNull(processor, "Parameter processor must be non-null"); + size_t objectStoreSize = configuration_GetObjectStoreSize( + forwarder_GetConfiguration(processor->forwarder)); + + contentStoreInterface_Release(&processor->contentStore); + + ContentStoreConfig contentStoreConfig = { + .objectCapacity = objectStoreSize, + }; + + processor->contentStore = + contentStoreLRU_Create(&contentStoreConfig, processor->logger); +} + +ContentStoreInterface *messageProcessor_GetContentObjectStore( + const MessageProcessor *processor) { + parcAssertNotNull(processor, "Parameter processor must be non-null"); + return processor->contentStore; +} + +void messageProcessor_Destroy(MessageProcessor **processorPtr) { + parcAssertNotNull(processorPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*processorPtr, "Parameter dereference to non-null pointer"); + + MessageProcessor *processor = *processorPtr; + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "MessageProcessor %p destroyed", (void *)processor); + } + + logger_Release(&processor->logger); + fib_Destroy(&processor->fib); + contentStoreInterface_Release(&processor->contentStore); + pit_Release(&processor->pit); + + parcMemory_Deallocate((void **)&processor); + *processorPtr = NULL; +} + +void messageProcessor_Receive(MessageProcessor *processor, Message *message) { + parcAssertNotNull(processor, "Parameter processor must be non-null"); + parcAssertNotNull(message, "Parameter message must be non-null"); + + processor->stats.countReceived++; + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + char *nameString = name_ToString(message_GetName(message)); + logger_Log(processor->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "Message %p ingress %3u length %5u received name %s", + (void *)message, message_GetIngressConnectionId(message), + message_Length(message), nameString); + parcMemory_Deallocate((void **)&nameString); + } + + switch (message_GetType(message)) { + case MessagePacketType_Interest: + messageProcessor_ReceiveInterest(processor, message); + break; + + case MessagePacketType_ContentObject: + messageProcessor_ReceiveContentObject(processor, message); + break; + + default: + messageProcessor_Drop(processor, message); + break; + } + + // if someone wanted to save it, they made a copy + message_Release(&message); +} + +bool messageProcessor_AddOrUpdateRoute(MessageProcessor *processor, + add_route_command *control, + unsigned ifidx) { + Configuration *config = forwarder_GetConfiguration(processor->forwarder); + + const char *prefixStr = utils_PrefixLenToString( + control->addressType, &control->address, &control->len); + strategy_type fwdStrategy = + configuration_GetForwardingStrategy(config, prefixStr); + if (fwdStrategy == LAST_STRATEGY_VALUE) { + fwdStrategy = SET_STRATEGY_LOADBALANCER; + } + + Name *prefix = name_CreateFromAddress(control->addressType, control->address, + control->len); + FibEntry *entry = fib_Contains(processor->fib, prefix); + bool newEntry = false; + if (entry != NULL) { + fibEntry_AddNexthop(entry, ifidx); + } else { + newEntry = true; + entry = fibEntry_Create(prefix, fwdStrategy); + fibEntry_AddNexthop(entry, ifidx); + fib_Add(processor->fib, entry); + } + + name_Release(&prefix); + if (newEntry && (fwdStrategy == SET_STRATEGY_LOADBALANCER_WITH_DELAY)) { + strategyLoadBalancerWithPD_SetConnectionTable( + fibEntry_GetFwdStrategy(entry), + forwarder_GetConnectionTable(processor->forwarder)); + } + + return true; +} + +bool messageProcessor_RemoveRoute(MessageProcessor *processor, + remove_route_command *control, + unsigned ifidx) { + Name *name = name_CreateFromAddress(control->addressType, control->address, + control->len); + fib_Remove(processor->fib, name, ifidx); + name_Release(&name); + + return true; +} + +void messageProcessor_RemoveConnectionIdFromRoutes(MessageProcessor *processor, + unsigned connectionId) { + fib_RemoveConnectionId(processor->fib, connectionId); +} + +void processor_SetStrategy(MessageProcessor *processor, Name *prefix, + strategy_type strategy) { + FibEntry *entry = fib_Contains(processor->fib, prefix); + if (entry != NULL) { + fibEntry_SetStrategy(entry, strategy); + if (strategy == SET_STRATEGY_LOADBALANCER_WITH_DELAY) { + strategyLoadBalancerWithPD_SetConnectionTable( + fibEntry_GetFwdStrategy(entry), + forwarder_GetConnectionTable(processor->forwarder)); + } + } +} + +FibEntryList *messageProcessor_GetFibEntries(MessageProcessor *processor) { + parcAssertNotNull(processor, "Parameter processor must be non-null"); + return fib_GetEntries(processor->fib); +} + +// ============================================================ +// Internal API + +/** + * @function messageProcessor_Drop + * @abstract Whenever we "drop" a message, increment countes + * @discussion + * This is a bookkeeping function. It increments the appropriate counters. + * + * The default action for a message is to destroy it in + * <code>messageProcessor_Receive()</code>, so this function does not need to do + * that. + * + */ +static void messageProcessor_Drop(MessageProcessor *processor, + Message *message) { + processor->stats.countDropped++; + + switch (message_GetType(message)) { + case MessagePacketType_Interest: + processor->stats.countInterestsDropped++; + break; + + case MessagePacketType_ContentObject: + processor->stats.countObjectsDropped++; + break; + + default: + break; + } + + // dont destroy message here, its done at end of receive +} + +/** + * @function messageProcessor_AggregateInterestInPit + * @abstract Try to aggregate the interest in the PIT + * @discussion + * Tries to aggregate the interest with another interest. + * + * @return true if interest aggregagted (no more forwarding needed), false if + * need to keep processing it. + */ +static bool messageProcessor_AggregateInterestInPit(MessageProcessor *processor, + Message *interestMessage) { + PITVerdict verdict = pit_ReceiveInterest(processor->pit, interestMessage); + + if (verdict == PITVerdict_Aggregate) { + // PIT has it, we're done + processor->stats.countInterestsAggregated++; + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log( + processor->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "Message %p aggregated in PIT (aggregated count %u)", + (void *)interestMessage, processor->stats.countInterestsAggregated); + } + + return true; + } + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log( + processor->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "Message %p not aggregated in PIT (aggregated count %u)", + (void *)interestMessage, processor->stats.countInterestsAggregated); + } + + return false; +} + +static bool _satisfyFromContentStore(MessageProcessor *processor, + Message *interestMessage) { + bool result = false; + + if (message_GetInterestLifetimeTicks(interestMessage) == 0) { + return false; + } + + if (!processor->serve_from_cache) { + return result; + } + + // See if there's a match in the store. + Message *objectMessage = contentStoreInterface_MatchInterest( + processor->contentStore, interestMessage, + forwarder_GetTicks(processor->forwarder)); + + if (objectMessage != NULL) { + // Remove it from the PIT. nexthops is allocated, so need to destroy + NumberSet *nexthops = pit_SatisfyInterest(processor->pit, objectMessage); + parcAssertNotNull( + nexthops, + "Illegal state: got a null nexthops for an interest we just inserted."); + + // send message in reply, then done + processor->stats.countInterestsSatisfiedFromStore++; + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug, __func__, + "Message %p satisfied from content store (satisfied count %u)", + (void *)interestMessage, + processor->stats.countInterestsSatisfiedFromStore); + } + + message_ResetPathLabel(objectMessage); + + messageProcessor_ForwardToNexthops(processor, objectMessage, nexthops); + numberSet_Release(&nexthops); + + result = true; + } + + return result; +} + +/** + * @function messageProcessor_ForwardViaFib + * @abstract Try to forward the interest via the FIB + * @discussion + * This calls <code>messageProcessor_ForwardToNexthops()</code>, so if we find + * any nexthops, the interest will be sent on its way. Depending on the + * IoOperations of each nexthop, it may be a deferred write and bump up the + * <code>interestMessage</code> refernce count, or it may copy the data out. + * + * A TRUE return means we did our best to forward it via the routes. If those + * routes are actually down or have errors, we still return TRUE. A FALSE + * return means there were no routes to try. + * + * @return true if we found a route and tried to forward it, false if no route + */ +static bool messageProcessor_ForwardViaFib(MessageProcessor *processor, + Message *interestMessage) { + FibEntry *fibEntry = fib_Match(processor->fib, interestMessage); + if (fibEntry == NULL) { + return false; + } + + PitEntry *pitEntry = pit_GetPitEntry(processor->pit, interestMessage); + if (pitEntry == NULL) { + return false; + } + + pitEntry_AddFibEntry(pitEntry, fibEntry); + + NumberSet *nexthops = (NumberSet *)fibEntry_GetNexthopsFromForwardingStrategy( + fibEntry, interestMessage); + // this requires some additional checks. It may happen that some of the output + // faces selected by the forwarding strategy are not usable. So far all the + // forwarding strategy return only valid faces (or an empty list) + for (unsigned i = 0; i < numberSet_Length(nexthops); i++) { + pitEntry_AddEgressId(pitEntry, numberSet_GetItem(nexthops, i)); + } + + // The function GetPitEntry encreases the ref counter in the pit entry + // we need to decrease it + pitEntry_Release(&pitEntry); + + if (messageProcessor_ForwardToNexthops(processor, interestMessage, nexthops) > + 0) { + numberSet_Release(&nexthops); + return true; + } else { + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug, __func__, + "Message %p returned an emtpy next hop set", + (void *)interestMessage); + } + } + + return false; +} + +/** + * @function messageProcessor_ReceiveInterest + * @abstract Receive an interest from the network + * @discussion + * (1) if interest in the PIT, aggregate in PIT + * (2) if interest in the ContentStore, reply + * (3) if in the FIB, forward + * (4) drop + * + */ +static void messageProcessor_ReceiveInterest(MessageProcessor *processor, + Message *interestMessage) { + processor->stats.countInterestsReceived++; + + // (1) Try to aggregate in PIT + if (messageProcessor_AggregateInterestInPit(processor, interestMessage)) { + // done + return; + } + + // At this point, we just created a PIT entry. If we don't forward the + // interest, we need to remove the PIT entry. + + // (2) Try to satisfy from content store + if (_satisfyFromContentStore(processor, interestMessage)) { + // done + // If we found a content object in the CS, + // messageProcess_SatisfyFromContentStore already cleared the PIT state + return; + } + + // (3) Try to forward it + if (messageProcessor_ForwardViaFib(processor, interestMessage)) { + // done + return; + } + + // Remove the PIT entry? + processor->stats.countDroppedNoRoute++; + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "Message %p did not match FIB, no route (count %u)", + (void *)interestMessage, processor->stats.countDroppedNoRoute); + } + + messageProcessor_Drop(processor, interestMessage); +} + +/** + * @function messageProcessor_ReceiveContentObject + * @abstract Process an in-bound content object + * @discussion + * (1) If it does not match anything in the PIT, drop it + * (2) Add to Content Store + * (3) Reverse path forward via PIT entries + * + * @param <#param1#> + */ +static void messageProcessor_ReceiveContentObject(MessageProcessor *processor, + Message *message) { + processor->stats.countObjectsReceived++; + + NumberSet *ingressSetUnion = pit_SatisfyInterest(processor->pit, message); + + if (numberSet_Length(ingressSetUnion) == 0) { + // (1) If it does not match anything in the PIT, drop it + processor->stats.countDroppedNoReversePath++; + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug, __func__, + "Message %p did not match PIT, no reverse path (count %u)", + (void *)message, processor->stats.countDroppedNoReversePath); + } + + // we store the packets in the content store enven in the case where there + // is no match in the PIT table in this way the applications can push the + // content in the CS of the forwarder. We allow this only for local faces + bool isLocal = connection_IsLocal(connectionTable_FindById( + forwarder_GetConnectionTable(processor->forwarder), + message_GetIngressConnectionId((const Message *)message))); + if (processor->store_in_cache && isLocal) { + uint64_t currentTimeTicks = forwarder_GetTicks(processor->forwarder); + contentStoreInterface_PutContent(processor->contentStore, message, + currentTimeTicks); + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug, __func__, + "Message %p sotred in the CS anyway", (void *)message); + } + } + + messageProcessor_Drop(processor, message); + } else { + // (2) Add to Content Store. Store may remove expired content, if necessary, + // depending on store policy. + if (processor->store_in_cache) { + uint64_t currentTimeTicks = forwarder_GetTicks(processor->forwarder); + contentStoreInterface_PutContent(processor->contentStore, message, + currentTimeTicks); + } + // (3) Reverse path forward via PIT entries + messageProcessor_ForwardToNexthops(processor, message, ingressSetUnion); + } + + numberSet_Release(&ingressSetUnion); +} + +/** + * @function messageProcessor_ForwardToNexthops + * @abstract Try to forward to each nexthop listed in the NumberSet + * @discussion + * Will not forward to the ingress connection. + * + * @return The number of nexthops tried + */ +static unsigned messageProcessor_ForwardToNexthops(MessageProcessor *processor, + Message *message, + const NumberSet *nexthops) { + unsigned forwardedCopies = 0; + + size_t length = numberSet_Length(nexthops); + + unsigned ingressId = message_GetIngressConnectionId(message); + uint32_t old_path_label = 0; + + if (message_GetType(message) == MessagePacketType_ContentObject) { + old_path_label = message_GetPathLabel(message); + } + + for (size_t i = 0; i < length; i++) { + unsigned egressId = numberSet_GetItem(nexthops, i); + if (egressId != ingressId) { + forwardedCopies++; + messageProcessor_ForwardToInterfaceId(processor, message, egressId); + + if (message_GetType(message) == MessagePacketType_ContentObject) { + // everytime we send out a message we need to restore the original path + // label of the message this is important because we keep a single copy + // of the message (single pointer) and we modify the path label at each + // send. + message_SetPathLabel(message, old_path_label); + } + } + } + return forwardedCopies; +} + +/** + * caller has checked that the hop limit is ok. Try to send out the connection. + */ +static void messageProcessor_SendWithGoodHopLimit(MessageProcessor *processor, + Message *message, + unsigned interfaceId, + const Connection *conn) { + bool success = connection_Send(conn, message); + if (success) { + switch (message_GetType(message)) { + case MessagePacketType_Interest: + processor->stats.countInterestForwarded++; + break; + + case MessagePacketType_ContentObject: + processor->stats.countObjectsForwarded++; + break; + + default: + break; + } + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log( + processor->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "forward message %p to interface %u (int %u, obj %u)", + (void *)message, interfaceId, processor->stats.countInterestForwarded, + processor->stats.countObjectsForwarded); + } + } else { + processor->stats.countSendFailures++; + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug, __func__, + "forward message %p to interface %u send failure (count %u)", + (void *)message, interfaceId, + processor->stats.countSendFailures); + } + messageProcessor_Drop(processor, message); + } +} + +/* + * If the hoplimit is equal to 0, then we may only forward it to local + * applications. Otherwise, we may forward it off the system. + * + */ +static void messageProcessor_ForwardToInterfaceId(MessageProcessor *processor, + Message *message, + unsigned interfaceId) { + ConnectionTable *connectionTable = + forwarder_GetConnectionTable(processor->forwarder); + const Connection *conn = + connectionTable_FindById(connectionTable, interfaceId); + + if (conn != NULL) { + messageProcessor_SendWithGoodHopLimit(processor, message, interfaceId, + conn); + } else { + processor->stats.countDroppedConnectionNotFound++; + + if (logger_IsLoggable(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(processor->logger, LoggerFacility_Processor, + PARCLogLevel_Debug, __func__, + "forward message %p to interface %u not found (count %u)", + (void *)message, interfaceId, + processor->stats.countDroppedConnectionNotFound); + } + + messageProcessor_Drop(processor, message); + } +} + +void messageProcessor_SetCacheStoreFlag(MessageProcessor *processor, bool val) { + processor->store_in_cache = val; +} + +bool messageProcessor_GetCacheStoreFlag(MessageProcessor *processor) { + return processor->store_in_cache; +} + +void messageProcessor_SetCacheServeFlag(MessageProcessor *processor, bool val) { + processor->serve_from_cache = val; +} + +bool messageProcessor_GetCacheServeFlag(MessageProcessor *processor) { + return processor->serve_from_cache; +} + +#ifdef WITH_MAPME + +FIB *messageProcessor_getFib(MessageProcessor *processor) { + return processor->fib; +} + +#endif /* WITH_MAPME */ diff --git a/hicn-light/src/processor/messageProcessor.h b/hicn-light/src/processor/messageProcessor.h new file mode 100755 index 000000000..ce3049938 --- /dev/null +++ b/hicn-light/src/processor/messageProcessor.h @@ -0,0 +1,166 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file messageProcessor.h + * @brief Executes the set of rules dictated by the PacketType + * + * This is a "run-to-completion" handling of a message based on the PacketType. + * + * The MessageProcessor also owns the PIT and FIB tables. + * + */ + +#ifndef messageProcessor_h +#define messageProcessor_h + +#include <src/content_store/contentStoreInterface.h> +#include <src/core/forwarder.h> +#include <src/core/message.h> + +#include <src/utils/commands.h> + +struct message_processor; +typedef struct message_processor MessageProcessor; + +/** + * Allocates a MessageProcessor along with PIT, FIB and ContentStore tables + * + * The hicn-light pointer is primarily used for logging (forwarder_Log), getting + * the configuration, and accessing the connection table. + * + * @param [in] Pointer to owning hicn-light process + * + * @retval non-null An allocated message processor + * @retval null An error + * + */ +MessageProcessor *messageProcessor_Create(Forwarder *forwarder); + +/** + * Deallocates a message processor an all internal tables + * + * @param [in,out] processorPtr Pointer to message processor to de-allocate, + * will be NULL'd. + */ +void messageProcessor_Destroy(MessageProcessor **processorPtr); + +/** + * @function messageProcessor_Receive + * @abstract Process the message, takes ownership of the memory. + * @discussion + * Will call destroy on the memory when done with it, so if the caller wants + * to keep it, make a reference counted copy. + * + * Receive may modify some fields in the message, such as the HopLimit field. + */ +void messageProcessor_Receive(MessageProcessor *procesor, Message *message); + +/** + * Adds or updates a route in the FIB + * + * If the route already exists, it is replaced + * + * @param [in] procesor An allocated message processor + * @param [in] route The route to update + * + * @retval true added or updated + * @retval false An error + */ +bool messageProcessor_AddOrUpdateRoute(MessageProcessor *processor, + add_route_command *control, + unsigned ifidx); + +/** + * Removes a route from the FIB + * + * Removes a specific nexthop for a route. If there are no nexthops left after + * the removal, the entire route is deleted from the FIB. + * + * @param [in] procesor An allocated message processor + * @param [in] route The route to remove + * + * @retval true Route completely removed + * @retval false There is still a nexthop for the route + */ + +bool messageProcessor_RemoveRoute(MessageProcessor *processor, + remove_route_command *control, + unsigned ifidx); + +/** + * Removes a given connection id from all FIB entries + * + * Iterates the FIB and removes the given connection ID from every route. + */ +void messageProcessor_RemoveConnectionIdFromRoutes(MessageProcessor *processor, + unsigned connectionId); + +/** + * Returns a list of all FIB entries + * + * You must destroy the list. + * + * @retval non-null The list of FIB entries + * @retval null An error + */ +FibEntryList *messageProcessor_GetFibEntries(MessageProcessor *processor); + +/** + * Adjusts the ContentStore to the given size. + * + * This will destroy and re-create the content store, so any cached objects will + * be lost. + * + */ +void messageProcessor_SetContentObjectStoreSize(MessageProcessor *processor, + size_t maximumContentStoreSize); + +/** + * Return the interface to the currently instantiated ContentStore, if any. + * + * @param [in] processor the `MessageProcessor` from which to return the + * ContentStoreInterface. + * + */ +ContentStoreInterface *messageProcessor_GetContentObjectStore( + const MessageProcessor *processor); + +void messageProcessor_SetCacheStoreFlag(MessageProcessor *processor, bool val); + +bool messageProcessor_GetCacheStoreFlag(MessageProcessor *processor); + +void messageProcessor_SetCacheServeFlag(MessageProcessor *processor, bool val); + +bool messageProcessor_GetCacheServeFlag(MessageProcessor *processor); + +void messageProcessor_ClearCache(MessageProcessor *processor); + +void processor_SetStrategy(MessageProcessor *processor, Name *prefix, + strategy_type strategy); + +#ifdef WITH_MAPME + +/** + * @function messageProcessor_getFib + * @abstract Returns the hICN processor's FIB. + * @param [in] forwarder - Pointer to the hICN processor. + * @returns Pointer to the hICN FIB. + */ +FIB *messageProcessor_getFib(MessageProcessor *processor); + +#endif /* WITH_MAPME */ + +#endif // messageProcessor_h diff --git a/hicn-light/src/processor/pit.c b/hicn-light/src/processor/pit.c new file mode 100755 index 000000000..9cae4062e --- /dev/null +++ b/hicn-light/src/processor/pit.c @@ -0,0 +1,45 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * Generic interface to PIT table + * + */ + +#include <parc/assert/parc_Assert.h> +#include <src/config.h> +#include <stdio.h> + +#include <src/processor/pit.h> + +void *pit_Closure(const PIT *pit) { return pit->closure; } + +void pit_Release(PIT **pitPtr) { (*pitPtr)->release(pitPtr); } + +PITVerdict pit_ReceiveInterest(PIT *pit, Message *interestMessage) { + return pit->receiveInterest(pit, interestMessage); +} + +NumberSet *pit_SatisfyInterest(PIT *pit, const Message *objectMessage) { + return pit->satisfyInterest(pit, objectMessage); +} + +void pit_RemoveInterest(PIT *pit, const Message *interestMessage) { + pit->removeInterest(pit, interestMessage); +} + +PitEntry *pit_GetPitEntry(const PIT *pit, const Message *interestMessage) { + return pit->getPitEntry(pit, interestMessage); +} diff --git a/hicn-light/src/processor/pit.h b/hicn-light/src/processor/pit.h new file mode 100755 index 000000000..1f909be3e --- /dev/null +++ b/hicn-light/src/processor/pit.h @@ -0,0 +1,114 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file pit.h + * @brief The Pending Interest Table interface + * + * Interface for implementing a PIT table + * + */ + +#ifndef pit_h +#define pit_h + +#include <src/core/forwarder.h> +#include <src/core/message.h> +#include <src/core/numberSet.h> +#include <src/processor/pitEntry.h> +#include <src/processor/pitVerdict.h> + +struct pit; +typedef struct pit PIT; + +struct pit { + void (*release)(PIT **pitPtr); + PITVerdict (*receiveInterest)(PIT *pit, Message *interestMessage); + NumberSet *(*satisfyInterest)(PIT *pit, const Message *objectMessage); + void (*removeInterest)(PIT *pit, const Message *interestMessage); + PitEntry *(*getPitEntry)(const PIT *pit, const Message *interestMessage); + void *closure; +}; + +void *pit_Closure(const PIT *pit); + +/** + * Destroys the PIT table and all entries contained in it. + * + * PIT entries are reference counted, so if the user has stored one outside the + * PIT table it will still be valid. + * + * @param [in,out] pitPtr Double pointer to PIT table, will be NULLed + */ +void pit_Release(PIT **pitPtr); + +/** + * @function pit_ReceiveInterest + * @abstract Receives an interest and adds to PIT table + * @discussion + * If not present, adds entry to the PIT table and returns + * PIT_VERDICT_NEW_ENTRY. If present and aggregated, returns + * PIT_VERDICT_EXISTING_ENTRY. + * + * Some aggregated interests may return PIT_VERDICT_NEW_ENTRY if the interest + * needs to be forwarded again (e.g. the lifetime is extended). + * + * If the PIT stores the message in its table, it will store a reference + * counted copy. + * + * @return Verdict of receiving the interest + */ +PITVerdict pit_ReceiveInterest(PIT *pit, Message *interestMessage); + +/** + * @function pit_SatisfyInterest + * @abstract Tries to satisfy PIT entries based on the message, returning where + * to send message + * @discussion + * If matching interests are in the PIT, will return the set of reverse + * paths to use to forward the content object. + * + * The return value is allocated and must be destroyed. + * + * @return Set of ConnectionTable id's to forward the message, may be empty or + * NULL. Must be destroyed. + */ +NumberSet *pit_SatisfyInterest(PIT *pit, const Message *objectMessage); + +/** + * @function pit_RemoveInterest + * @abstract Unconditionally remove the interest from the PIT + * @discussion + * The PIT may store a specific name in several tables. This function will + * remove the interest from the specific table it lives it. It will not + * remove PIT entries in different tables with the same name. + * + * The different tables index interests based on their matching criteria, + * such as by name, by name and keyid, etc. + * + */ +void pit_RemoveInterest(PIT *pit, const Message *interestMessage); + +/** + * @function pit_GetPitEntry + * @abstract Retrieve the best matching PIT entry for the message. + * @discussion + * Returns a reference counted copy of the entry, must call + * <code>pitEntry_Destory()</code> on it. + * + * @return NULL if not in table, otherwise a reference counted copy of the entry + */ +PitEntry *pit_GetPitEntry(const PIT *pit, const Message *interestMessage); +#endif // pit_h diff --git a/hicn-light/src/processor/pitEntry.c b/hicn-light/src/processor/pitEntry.c new file mode 100755 index 000000000..38103cb8e --- /dev/null +++ b/hicn-light/src/processor/pitEntry.c @@ -0,0 +1,142 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <src/config.h> +#include <stdio.h> + +#include <parc/algol/parc_Memory.h> +#include <src/core/numberSet.h> +#include <src/processor/pitEntry.h> + +#include <parc/assert/parc_Assert.h> + +struct pit_entry { + Message *message; + NumberSet *ingressIdSet; + NumberSet *egressIdSet; + + FibEntry *fibEntry; + + Ticks creationTime; + Ticks expiryTime; + + unsigned refcount; +}; + +PitEntry *pitEntry_Create(Message *message, Ticks expiryTime, + Ticks creationTime) { + PitEntry *pitEntry = parcMemory_AllocateAndClear(sizeof(PitEntry)); + parcAssertNotNull(pitEntry, "parcMemory_AllocateAndClear(%zu) returned NULL", + sizeof(PitEntry)); + pitEntry->message = message; + pitEntry->ingressIdSet = numberSet_Create(); + pitEntry->egressIdSet = numberSet_Create(); + pitEntry->refcount = 1; + + // add the message to the reverse path set + numberSet_Add(pitEntry->ingressIdSet, + message_GetIngressConnectionId(message)); + + // hack in a 4-second timeout + pitEntry->expiryTime = expiryTime; + pitEntry->fibEntry = NULL; + + pitEntry->creationTime = creationTime; + return pitEntry; +} + +void pitEntry_Release(PitEntry **pitEntryPtr) { + parcAssertNotNull(pitEntryPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*pitEntryPtr, + "Parameter must dereference to non-null pointer"); + + PitEntry *pitEntry = *pitEntryPtr; + parcTrapIllegalValueIf(pitEntry->refcount == 0, + "Illegal state: has refcount of 0"); + + pitEntry->refcount--; + if (pitEntry->refcount == 0) { + if (pitEntry->fibEntry != NULL) { + fibEntry_Release(&pitEntry->fibEntry); + } + numberSet_Release(&pitEntry->ingressIdSet); + numberSet_Release(&pitEntry->egressIdSet); + message_Release(&pitEntry->message); + parcMemory_Deallocate((void **)&pitEntry); + } + *pitEntryPtr = NULL; +} + +PitEntry *pitEntry_Acquire(PitEntry *original) { + parcAssertNotNull(original, "Parameter original must be non-null"); + original->refcount++; + return original; +} + +void pitEntry_AddIngressId(PitEntry *pitEntry, unsigned ingressId) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + numberSet_Add(pitEntry->ingressIdSet, ingressId); +} + +void pitEntry_AddEgressId(PitEntry *pitEntry, unsigned egressId) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + numberSet_Add(pitEntry->egressIdSet, egressId); +} + +void pitEntry_AddFibEntry(PitEntry *pitEntry, FibEntry *fibEntry) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + parcAssertNotNull(fibEntry, "Parameter fibEntry must be non-null"); + // the fibEntry should be always the same for all the interests in the same + // pitEntry + if (pitEntry->fibEntry == NULL) { + fibEntry_Acquire(fibEntry); + pitEntry->fibEntry = fibEntry; + } +} + +FibEntry *pitEntry_GetFibEntry(PitEntry *pitEntry) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + return pitEntry->fibEntry; +} + +Ticks pitEntry_GetExpiryTime(const PitEntry *pitEntry) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + return pitEntry->expiryTime; +} + +Ticks pitEntry_GetCreationTime(const PitEntry *pitEntry) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + return pitEntry->creationTime; +} + +void pitEntry_SetExpiryTime(PitEntry *pitEntry, Ticks expiryTime) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + pitEntry->expiryTime = expiryTime; +} + +const NumberSet *pitEntry_GetIngressSet(const PitEntry *pitEntry) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + return pitEntry->ingressIdSet; +} + +const NumberSet *pitEntry_GetEgressSet(const PitEntry *pitEntry) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + return pitEntry->egressIdSet; +} + +Message *pitEntry_GetMessage(const PitEntry *pitEntry) { + parcAssertNotNull(pitEntry, "Parameter pitEntry must be non-null"); + return message_Acquire(pitEntry->message); +} diff --git a/hicn-light/src/processor/pitEntry.h b/hicn-light/src/processor/pitEntry.h new file mode 100755 index 000000000..b7d45e6a4 --- /dev/null +++ b/hicn-light/src/processor/pitEntry.h @@ -0,0 +1,164 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file pitEntry.h + * @brief The embodiment of a PIT entry + * + * Embodies a PIT entry + * + */ + +#ifndef pitEntry_h +#define pitEntry_h + +#include <src/core/message.h> +#include <src/core/numberSet.h> +#include <src/core/ticks.h> +#include <src/processor/fibEntry.h> + +struct pit_entry; +typedef struct pit_entry PitEntry; + +/** + * @function pitEntry_Create + * @abstract Takes ownership of the message inside the PitEntry + * @discussion + * When the PIT entry is destroyed, will call <code>message_Release()</code> + * on the message. + * + */ +PitEntry *pitEntry_Create(Message *message, Ticks expiryTime, + Ticks CreationTime); + +/** + * Release a previously acquired reference to the specified instance, + * decrementing the reference count for the instance. + * + * The pointer to the instance is set to NULL as a side-effect of this function. + * + * If the invocation causes the last reference to the instance to be released, + * the instance is deallocated and the instance's implementation will perform + * additional cleanup and release other privately held references. + * + * @param [in,out] pitEntryPtr A pointer to a PitEntry instance pointer, which + * will be set to zero on return. + * + */ +void pitEntry_Release(PitEntry **pitEntryPtr); + +/** + * @function pitEntry_Acquire + * @abstract Returns a reference counted copy + * @discussion + * A reference counted copy that shares the same state as the original. + * Caller must use <code>pitEntry_Release()</code> on it when done. + * + * @return A reference counted copy, use Destroy on it. + */ +PitEntry *pitEntry_Acquire(PitEntry *original); + +/** + * @function pitEntry_AddIngressId + * @abstract Add an ingress connection id to the list of reverse paths + * @discussion + * A PitEntry has two NumberSets. The first is the set of ingress ports, + * which make up the reverse path. The second is the set of egress ports, which + * make up its forward path. + * + * This function tracks which reverse paths have sent us the interest. + * + * @param ingressId the reverse path + */ +void pitEntry_AddIngressId(PitEntry *pitEntry, unsigned ingressId); + +/** + * @function pitEntry_AddEgressId + * @abstract Add an egress connection id to the list of attempted paths + * @discussion + * A PitEntry has two NumberSets. The first is the set of ingress ports, + * which make up the reverse path. The second is the set of egress ports, which + * make up its forward path. + * + * This function tracks which forward paths we've tried for the interest. + * + * @param egressId the forwarded path + */ +void pitEntry_AddEgressId(PitEntry *pitEntry, unsigned egressId); + +void pitEntry_AddFibEntry(PitEntry *pitEntry, FibEntry *fibEntry); + +FibEntry *pitEntry_GetFibEntry(PitEntry *pitEntry); + +/** + * @function pitEntry_GetIngressSet + * @abstract The Ingress connection id set + * @discussion + * You must acquire a copy of the number set if you will store the result. + * This is the internal reference. + * + * @return May be empty, will not be null. Must be destroyed. + */ +const NumberSet *pitEntry_GetIngressSet(const PitEntry *pitEntry); + +/** + * @function pitEntry_GetEgressSet + * @abstract The Egress connection id set + * @discussion + * You must acquire a copy of the number set if you will store the result. + * This is the internal reference. + * + * @param <#param1#> + * @return May be empty, will not be null. Must be destroyed. + */ +const NumberSet *pitEntry_GetEgressSet(const PitEntry *pitEntry); + +/** + * @function pitEntry_GetMessage + * @abstract Gets the interest underpinning the PIT entry + * @discussion + * A reference counted copy, call <code>Message_Release()</code> on it. + * + * @return A reference counted copy, call <code>Message_Release()</code> on it. + */ +Message *pitEntry_GetMessage(const PitEntry *pitEntry); + +/** + * Returns the time (in ticks) at which the PIT entry is no longer valid + * + * The ExpiryTime is computed when the PIT entry is added (or via + * pitEntry_SetExpiryTime). It is the aboslute time (in Ticks) at which the Pit + * entry is no longer valid. + * + * @param [in] PitEntry An allocated PIT entry + * + * @retval number The abosolute time (in Ticks) of the Expiry + */ +Ticks pitEntry_GetExpiryTime(const PitEntry *pitEntry); + +Ticks pitEntry_GetCreationTime(const PitEntry *pitEntry); +/** + * Sets the ExpriyTime of the PIT entry to the given value + * + * It is probalby an error to set the expiryTime to a smaller value than + * currently set to, but this is not enforced. PIT entries use lazy delete. + * + * @param [in] pitEntry The allocated PIT entry to modify + * @param [in] expiryTime The new expiryTime (UTC in forwarder Ticks) + * + */ +void pitEntry_SetExpiryTime(PitEntry *pitEntry, Ticks expiryTime); + +#endif // pitEntry_h diff --git a/hicn-light/src/processor/pitStandard.c b/hicn-light/src/processor/pitStandard.c new file mode 100755 index 000000000..8d507626a --- /dev/null +++ b/hicn-light/src/processor/pitStandard.c @@ -0,0 +1,304 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * The pending interest table. + * + * Interest aggregation strategy: + * - The first Interest for a name is forwarded + * - A second Interest for a name from a different reverse path may be + * aggregated + * - A second Interest for a name from an existing Interest is forwarded + * - The Interest Lifetime is like a subscription time. A reverse path entry is + * removed once the lifetime is exceeded. + * - Whan an Interest arrives or is aggregated, the Lifetime for that reverse + * hop is extended. As a simplification, we only keep a single lifetime not per + * reverse hop. + * + */ + +#include <src/config.h> +#include <stdio.h> + +#define __STDC_FORMAT_MACROS +#include <inttypes.h> + +#include <src/processor/hashTableFunction.h> +#include <src/processor/pit.h> + +#include <src/core/ticks.h> + +#include <parc/algol/parc_Hash.h> +#include <parc/algol/parc_HashCodeTable.h> +#include <parc/algol/parc_Memory.h> + +#include <src/core/forwarder.h> + +#include <parc/assert/parc_Assert.h> + +struct standard_pit; +typedef struct standard_pit StandardPIT; + +struct standard_pit { + Forwarder *forwarder; + Logger *logger; + PARCHashCodeTable *table; // PIT indexed by name +}; + +static void _pit_StoreInTable(StandardPIT *pit, Message *interestMessage); + +static void _pit_PitEntryDestroyer(void **dataPtr) { + pitEntry_Release((PitEntry **)dataPtr); +} + +static bool _pit_IngressSetContains(PitEntry *pitEntry, unsigned connectionId) { + const NumberSet *set = pitEntry_GetIngressSet(pitEntry); + bool numberInSet = numberSet_Contains(set, connectionId); + return numberInSet; +} + +static Ticks _pit_CalculateLifetime(StandardPIT *pit, + Message *interestMessage) { + uint64_t interestLifetimeTicks = + message_GetInterestLifetimeTicks(interestMessage); + if (interestLifetimeTicks == 0) { + interestLifetimeTicks = forwarder_NanosToTicks(4000000000ULL); + } + + Ticks expiryTime = forwarder_GetTicks(pit->forwarder) + interestLifetimeTicks; + return expiryTime; +} + +static void _pit_StoreInTable(StandardPIT *pit, Message *interestMessage) { + Message *key = message_Acquire(interestMessage); + + Ticks expiryTime = _pit_CalculateLifetime(pit, interestMessage); + + PitEntry *pitEntry = + pitEntry_Create(key, expiryTime, forwarder_GetTicks(pit->forwarder)); + + parcHashCodeTable_Add(pit->table, key, pitEntry); + + if (logger_IsLoggable(pit->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(pit->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, + "Message %p added to PIT (expiry %" PRIu64 ") ingress %u", + (void *)interestMessage, pitEntry_GetExpiryTime(pitEntry), + message_GetIngressConnectionId(interestMessage)); + } +} + +static void _pit_ExtendLifetime(StandardPIT *pit, PitEntry *pitEntry, + Message *interestMessage) { + Ticks expiryTime = _pit_CalculateLifetime(pit, interestMessage); + + if (expiryTime > pitEntry_GetExpiryTime(pitEntry)) + pitEntry_SetExpiryTime(pitEntry, expiryTime); +} + +// ====================================================================== +// Interface API + +static void _pitStandard_Destroy(PIT **pitPtr) { + parcAssertNotNull(pitPtr, "Parameter must be non-null double pointer"); + parcAssertNotNull(*pitPtr, "Parameter must dereference to non-null pointer"); + + StandardPIT *pit = pit_Closure(*pitPtr); + + if (logger_IsLoggable(pit->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(pit->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "PIT %p destroyed", (void *)pit); + } + + parcHashCodeTable_Destroy(&pit->table); + logger_Release(&pit->logger); + parcMemory_Deallocate(pitPtr); +} + +static PITVerdict _pitStandard_ReceiveInterest(PIT *generic, + Message *interestMessage) { + parcAssertNotNull(generic, "Parameter pit must be non-null"); + parcAssertNotNull(interestMessage, + "Parameter interestMessage must be non-null"); + + StandardPIT *pit = pit_Closure(generic); + + PitEntry *pitEntry = parcHashCodeTable_Get(pit->table, interestMessage); + + if (pitEntry) { + // has it expired? + Ticks now = forwarder_GetTicks(pit->forwarder); + if (now < pitEntry_GetExpiryTime(pitEntry)) { + _pit_ExtendLifetime(pit, pitEntry, interestMessage); + + // Is the reverse path already in the PIT entry? + if (_pit_IngressSetContains( + pitEntry, message_GetIngressConnectionId(interestMessage))) { + // It is already in the PIT entry, so this is a retransmission, so + // forward it. + + if (logger_IsLoggable(pit->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(pit->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, + "Message %p existing entry (expiry %" PRIu64 + ") and reverse path, forwarding", + (void *)interestMessage, pitEntry_GetExpiryTime(pitEntry)); + } + + return PITVerdict_Forward; + } + + // It is in the PIT but this is the first interest for the reverse path + pitEntry_AddIngressId(pitEntry, + message_GetIngressConnectionId(interestMessage)); + + if (logger_IsLoggable(pit->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(pit->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, + "Message %p existing entry (expiry %" PRIu64 + ") and reverse path is new, aggregate", + (void *)interestMessage, pitEntry_GetExpiryTime(pitEntry)); + } + + return PITVerdict_Aggregate; + } + // this is a timeout.... + FibEntry *fibEntry = pitEntry_GetFibEntry(pitEntry); + if (fibEntry != NULL) { + fibEntry_OnTimeout(fibEntry, pitEntry_GetEgressSet(pitEntry)); + } + + // it's an old entry, remove it + parcHashCodeTable_Del(pit->table, interestMessage); + } + + _pit_StoreInTable(pit, interestMessage); + + return PITVerdict_Forward; +} + +static NumberSet *_pitStandard_SatisfyInterest(PIT *generic, + const Message *objectMessage) { + parcAssertNotNull(generic, "Parameter pit must be non-null"); + parcAssertNotNull(objectMessage, "Parameter objectMessage must be non-null"); + + StandardPIT *pit = pit_Closure(generic); + + NumberSet *ingressSet = numberSet_Create(); + + PitEntry *pitEntry = parcHashCodeTable_Get(pit->table, objectMessage); + if (pitEntry) { + // here we need to check if the PIT entry is expired + // if so, remove the PIT entry. + Ticks now = forwarder_GetTicks(pit->forwarder); + if (now < pitEntry_GetExpiryTime(pitEntry)) { + // PIT entry is not expired, use it + FibEntry *fibEntry = pitEntry_GetFibEntry(pitEntry); + if (fibEntry != NULL) { + // this is a rough estimation of the residual RTT + Ticks rtt = forwarder_GetTicks(pit->forwarder) - + pitEntry_GetCreationTime(pitEntry); + fibEntry_ReceiveObjectMessage(fibEntry, pitEntry_GetEgressSet(pitEntry), + objectMessage, + rtt); // need to implement RTT + } + const NumberSet *is = pitEntry_GetIngressSet(pitEntry); + numberSet_AddSet(ingressSet, is); // with this we do a copy so we can + // remove the entry from the PIT + } + // remove the entry from the PIT. Key is a reference counted copy of the + // pit entry message + Message *key = pitEntry_GetMessage(pitEntry); + parcHashCodeTable_Del(pit->table, key); + message_Release(&key); + } + + return ingressSet; +} + +static void _pitStandard_RemoveInterest(PIT *generic, + const Message *interestMessage) { + parcAssertNotNull(generic, "Parameter pit must be non-null"); + parcAssertNotNull(interestMessage, + "Parameter interestMessage must be non-null"); + + StandardPIT *pit = pit_Closure(generic); + + if (logger_IsLoggable(pit->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(pit->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "Message %p removed from PIT", + (void *)interestMessage); + } + + parcHashCodeTable_Del(pit->table, interestMessage); +} + +static PitEntry *_pitStandard_GetPitEntry(const PIT *generic, + const Message *interestMessage) { + parcAssertNotNull(generic, "Parameter pit must be non-null"); + parcAssertNotNull(interestMessage, + "Parameter interestMessage must be non-null"); + + StandardPIT *pit = pit_Closure(generic); + + PitEntry *entry = parcHashCodeTable_Get(pit->table, interestMessage); + if (entry) { + return pitEntry_Acquire(entry); + } + return NULL; +} + +// ====================================================================== +// Public API + +PIT *pitStandard_Create(Forwarder *forwarder) { + parcAssertNotNull(forwarder, "Parameter must be non-null"); + + size_t allocation = sizeof(PIT) + sizeof(StandardPIT); + + PIT *generic = parcMemory_AllocateAndClear(allocation); + parcAssertNotNull(generic, "parcMemory_AllocateAndClear(%zu) returned NULL", + allocation); + generic->closure = (uint8_t *)generic + sizeof(PIT); + + StandardPIT *pit = pit_Closure(generic); + pit->forwarder = forwarder; + pit->logger = logger_Acquire(forwarder_GetLogger(forwarder)); + + size_t initialSize = 65535; + pit->table = + parcHashCodeTable_Create_Size(hashTableFunction_MessageNameEquals, + hashTableFunction_MessageNameHashCode, NULL, + _pit_PitEntryDestroyer, initialSize); + + if (logger_IsLoggable(pit->logger, LoggerFacility_Processor, + PARCLogLevel_Debug)) { + logger_Log(pit->logger, LoggerFacility_Processor, PARCLogLevel_Debug, + __func__, "PIT %p created", (void *)pit); + } + + generic->getPitEntry = _pitStandard_GetPitEntry; + generic->receiveInterest = _pitStandard_ReceiveInterest; + generic->release = _pitStandard_Destroy; + generic->removeInterest = _pitStandard_RemoveInterest; + generic->satisfyInterest = _pitStandard_SatisfyInterest; + + return generic; +} diff --git a/hicn-light/src/processor/pitStandard.h b/hicn-light/src/processor/pitStandard.h new file mode 100755 index 000000000..b9ba026c8 --- /dev/null +++ b/hicn-light/src/processor/pitStandard.h @@ -0,0 +1,41 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file pitStandard.h + * @brief The Pending Interest Table + * + * Implements the standard Pending Interest Table. + * + */ + +#ifndef pitStandard_h +#define pitStandard_h + +#include <src/processor/pit.h> + +/** + * Creates a PIT table + * + * Creates and allocates an emtpy PIT table. The Forwarder reference is + * used for logging and for time functions. + * + * @param [in] hicn-light The releated Forwarder + * + * @return non-null a PIT table + * @return null An error + */ +PIT *pitStandard_Create(Forwarder *forwarder); +#endif // pit_h diff --git a/hicn-light/src/processor/pitVerdict.h b/hicn-light/src/processor/pitVerdict.h new file mode 100755 index 000000000..16631fa51 --- /dev/null +++ b/hicn-light/src/processor/pitVerdict.h @@ -0,0 +1,36 @@ +/* + * Copyright (c) 2017-2019 Cisco and/or its affiliates. + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at: + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +/** + * @file pitVerdict.h + * @brief Adding an entry to the PIT will return NEW or EXISTING + * + * Adding an entry to the PIT will return NEW or EXISTING + * + */ + +#ifndef pitVerdict_h +#define pitVerdict_h + +/** + * @typedef PitVerdict + * @abstract The verdit of the PIT for receiving a message + * @constant PITVerdict_Forward The message made a new PIT entry, the interest + * should be forwarded + * @constant PITVerdict_Aggregate The Interest was aggregated in the PIT, does + * not need to be forwarded + */ +typedef enum { PITVerdict_Forward, PITVerdict_Aggregate } PITVerdict; +#endif // pitVerdict_h |