diff options
Diffstat (limited to 'metis/ccnx/forwarder/metis/processor/metis_StandardPIT.c')
| -rw-r--r-- | metis/ccnx/forwarder/metis/processor/metis_StandardPIT.c | 326 |
1 files changed, 326 insertions, 0 deletions
diff --git a/metis/ccnx/forwarder/metis/processor/metis_StandardPIT.c b/metis/ccnx/forwarder/metis/processor/metis_StandardPIT.c new file mode 100644 index 00000000..4c981f23 --- /dev/null +++ b/metis/ccnx/forwarder/metis/processor/metis_StandardPIT.c @@ -0,0 +1,326 @@ +/* + * Copyright (c) 2017 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 <config.h> +#include <stdio.h> + +#define __STDC_FORMAT_MACROS +#include <inttypes.h> + +#include <ccnx/forwarder/metis/processor/metis_PIT.h> +#include <ccnx/forwarder/metis/processor/metis_MatchingRulesTable.h> + +#include <ccnx/forwarder/metis/core/metis_Ticks.h> + +#include <parc/algol/parc_Memory.h> +#include <parc/algol/parc_HashCodeTable.h> +#include <parc/algol/parc_Hash.h> + +#include <ccnx/forwarder/metis/core/metis_Forwarder.h> + +#include <LongBow/runtime.h> + +struct metis_standard_pit; +typedef struct metis_standard_pit MetisStandardPIT; + +struct metis_standard_pit { + MetisForwarder *metis; + MetisLogger *logger; + + MetisMatchingRulesTable *table; + + // counters to track how many of each type of Interest we get + unsigned insertCounterByName; + unsigned insertCounterByKeyId; + unsigned insertCounterByObjectHash; +}; + +static void _metisPIT_StoreInTable(MetisStandardPIT *pit, MetisMessage *interestMessage); + +static void +_metisPIT_PitEntryDestroyer(void **dataPtr) +{ + metisPitEntry_Release((MetisPitEntry **) dataPtr); +} + +static bool +_metisPIT_IngressSetContains(MetisPitEntry *pitEntry, unsigned connectionId) +{ + const MetisNumberSet *set = metisPitEntry_GetIngressSet(pitEntry); + bool numberInSet = metisNumberSet_Contains(set, connectionId); + return numberInSet; +} + +static MetisTicks +_metisPIT_CalculateLifetime(MetisStandardPIT *pit, MetisMessage *interestMessage) +{ + uint64_t interestLifetimeTicks = 0; + + if (metisMessage_HasInterestLifetime(interestMessage)) { + interestLifetimeTicks = metisMessage_GetInterestLifetimeTicks(interestMessage); + } else { + interestLifetimeTicks = metisForwarder_NanosToTicks(4000000000ULL); + } + + MetisTicks expiryTime = metisForwarder_GetTicks(pit->metis) + interestLifetimeTicks; + return expiryTime; +} + +static void +_metisPIT_StoreInTable(MetisStandardPIT *pit, MetisMessage *interestMessage) +{ + MetisMessage *key = metisMessage_Acquire(interestMessage); + + MetisTicks expiryTime = _metisPIT_CalculateLifetime(pit, interestMessage); + + MetisPitEntry *pitEntry = metisPitEntry_Create(key, expiryTime, metisForwarder_GetTicks(pit->metis)); + // this is done in metisPitEntry_Create + // metisPitEntry_AddIngressId(pitEntry, metisMessage_GetIngressConnectionId(interestMessage)); + + metisMatchingRulesTable_AddToBestTable(pit->table, key, pitEntry); + + if (metisLogger_IsLoggable(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "Message %p added to PIT (expiry %" PRIu64 ") ingress %u", + (void *) interestMessage, + metisPitEntry_GetExpiryTime(pitEntry), + metisMessage_GetIngressConnectionId(interestMessage)); + } +} + +static void +_metisPIT_ExtendLifetime(MetisStandardPIT *pit, MetisPitEntry *pitEntry, MetisMessage *interestMessage) +{ + MetisTicks expiryTime = _metisPIT_CalculateLifetime(pit, interestMessage); + metisPitEntry_SetExpiryTime(pitEntry, expiryTime); +} + +// this appears to only be used in some unit tests +__attribute__((unused)) +static void +_metisPIT_AddEgressConnectionId(MetisPIT *generic, const MetisMessage *interestMessage, unsigned connectionId) +{ + assertNotNull(generic, "Parameter pit must be non-null"); + assertNotNull(interestMessage, "Parameter interestMessage must be non-null"); + + MetisStandardPIT *pit = metisPIT_Closure(generic); + + MetisPitEntry *entry = metisMatchingRulesTable_Get(pit->table, interestMessage); + if (entry) { + metisPitEntry_AddEgressId(entry, connectionId); + } +} + + +// ====================================================================== +// Interface API + +static void +_metisStandardPIT_Destroy(MetisPIT **pitPtr) +{ + assertNotNull(pitPtr, "Parameter must be non-null double pointer"); + assertNotNull(*pitPtr, "Parameter must dereference to non-null pointer"); + + MetisStandardPIT *pit = metisPIT_Closure(*pitPtr); + + if (metisLogger_IsLoggable(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "PIT %p destroyed", + (void *) pit); + } + + metisMatchingRulesTable_Destroy(&pit->table); + metisLogger_Release(&pit->logger); + parcMemory_Deallocate(pitPtr); +} + +// There's a bit too much going on in this function, need to break it +// apart for testability and style. +static MetisPITVerdict +_metisStandardPIT_ReceiveInterest(MetisPIT *generic, MetisMessage *interestMessage) +{ + assertNotNull(generic, "Parameter pit must be non-null"); + assertNotNull(interestMessage, "Parameter interestMessage must be non-null"); + + MetisStandardPIT *pit = metisPIT_Closure(generic); + + MetisPitEntry *pitEntry = metisMatchingRulesTable_Get(pit->table, interestMessage); + + if (pitEntry) { + // has it expired? + MetisTicks now = metisForwarder_GetTicks(pit->metis); + if (now < metisPitEntry_GetExpiryTime(pitEntry)) { + _metisPIT_ExtendLifetime(pit, pitEntry, interestMessage); + + // Is the reverse path already in the PIT entry? + if (_metisPIT_IngressSetContains(pitEntry, metisMessage_GetIngressConnectionId(interestMessage))) { + // It is already in the PIT entry, so this is a retransmission, so forward it. + + if (metisLogger_IsLoggable(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "Message %p existing entry (expiry %" PRIu64 ") and reverse path, forwarding", + (void *) interestMessage, + metisPitEntry_GetExpiryTime(pitEntry)); + } + + return MetisPITVerdict_Forward; + } + + // It is in the PIT but this is the first interest for the reverse path + metisPitEntry_AddIngressId(pitEntry, metisMessage_GetIngressConnectionId(interestMessage)); + + if (metisLogger_IsLoggable(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "Message %p existing entry (expiry %" PRIu64 ") and reverse path is new, aggregate", + (void *) interestMessage, + metisPitEntry_GetExpiryTime(pitEntry)); + } + + return MetisPITVerdict_Aggregate; + } + //this is a timeout.... + MetisFibEntry *fibEntry = metisPitEntry_GetFibEntry(pitEntry); + if (fibEntry != NULL) { + metisFibEntry_OnTimeout(fibEntry, metisPitEntry_GetEgressSet(pitEntry)); + } + + // it's an old entry, remove it + metisMatchingRulesTable_RemoveFromBest(pit->table, interestMessage); + } + + _metisPIT_StoreInTable(pit, interestMessage); + + return MetisPITVerdict_Forward; +} + +static MetisNumberSet * +_metisStandardPIT_SatisfyInterest(MetisPIT *generic, const MetisMessage *objectMessage) +{ + assertNotNull(generic, "Parameter pit must be non-null"); + assertNotNull(objectMessage, "Parameter objectMessage must be non-null"); + + MetisStandardPIT *pit = metisPIT_Closure(generic); + + // we need to look in all three tables to see if there's anything + // to satisy in each of them and take the union of the reverse path sets. + + MetisNumberSet *ingressSetUnion = metisNumberSet_Create(); + + PARCArrayList *list = metisMatchingRulesTable_GetUnion(pit->table, objectMessage); + for (size_t i = 0; i < parcArrayList_Size(list); i++) { + MetisPitEntry *pitEntry = (MetisPitEntry *) parcArrayList_Get(list, i); + + MetisFibEntry *fibEntry = metisPitEntry_GetFibEntry(pitEntry); + if (fibEntry != NULL) { + //this is a rough estimation of the residual RTT + MetisTicks rtt = metisForwarder_GetTicks(pit->metis) - metisPitEntry_GetCreationTime(pitEntry); + metisFibEntry_ReceiveObjectMessage(fibEntry, metisPitEntry_GetEgressSet(pitEntry), objectMessage, rtt); //need to implement RTT + } + + // this is a reference counted return + const MetisNumberSet *ingressSet = metisPitEntry_GetIngressSet(pitEntry); + metisNumberSet_AddSet(ingressSetUnion, ingressSet); + + // and remove it from the PIT. Key is a reference counted copy of the pit entry message + MetisMessage *key = metisPitEntry_GetMessage(pitEntry); + metisMatchingRulesTable_RemoveFromBest(pit->table, key); + metisMessage_Release(&key); + } + parcArrayList_Destroy(&list); + + return ingressSetUnion; +} + +static void +_metisStandardPIT_RemoveInterest(MetisPIT *generic, const MetisMessage *interestMessage) +{ + assertNotNull(generic, "Parameter pit must be non-null"); + assertNotNull(interestMessage, "Parameter interestMessage must be non-null"); + + MetisStandardPIT *pit = metisPIT_Closure(generic); + + if (metisLogger_IsLoggable(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "Message %p removed from PIT", + (void *) interestMessage); + } + + metisMatchingRulesTable_RemoveFromBest(pit->table, interestMessage); +} + +static MetisPitEntry * +_metisStandardPIT_GetPitEntry(const MetisPIT *generic, const MetisMessage *interestMessage) +{ + assertNotNull(generic, "Parameter pit must be non-null"); + assertNotNull(interestMessage, "Parameter interestMessage must be non-null"); + + MetisStandardPIT *pit = metisPIT_Closure(generic); + + MetisPitEntry *entry = metisMatchingRulesTable_Get(pit->table, interestMessage); + if (entry) { + return metisPitEntry_Acquire(entry); + } + return NULL; +} + + +// ====================================================================== +// Public API + +MetisPIT * +metisStandardPIT_Create(MetisForwarder *metis) +{ + assertNotNull(metis, "Parameter must be non-null"); + + size_t allocation = sizeof(MetisPIT) + sizeof(MetisStandardPIT); + + MetisPIT *generic = parcMemory_AllocateAndClear(allocation); + assertNotNull(generic, "parcMemory_AllocateAndClear(%zu) returned NULL", allocation); + generic->closure = (uint8_t *) generic + sizeof(MetisPIT); + + MetisStandardPIT *pit = metisPIT_Closure(generic); + pit->metis = metis; + pit->logger = metisLogger_Acquire(metisForwarder_GetLogger(metis)); + pit->table = metisMatchingRulesTable_Create(_metisPIT_PitEntryDestroyer); + + if (metisLogger_IsLoggable(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(pit->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "PIT %p created", + (void *) pit); + } + + generic->getPitEntry = _metisStandardPIT_GetPitEntry; + generic->receiveInterest = _metisStandardPIT_ReceiveInterest; + generic->release = _metisStandardPIT_Destroy; + generic->removeInterest = _metisStandardPIT_RemoveInterest; + generic->satisfyInterest = _metisStandardPIT_SatisfyInterest; + + return generic; +} + |