/* * 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 #include #define __STDC_FORMAT_MACROS #include #include #include #include #include #include #include #include #include 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; }