diff options
Diffstat (limited to 'metis/ccnx/forwarder/metis/content_store/metis_LRUContentStore.c')
| -rw-r--r-- | metis/ccnx/forwarder/metis/content_store/metis_LRUContentStore.c | 530 |
1 files changed, 530 insertions, 0 deletions
diff --git a/metis/ccnx/forwarder/metis/content_store/metis_LRUContentStore.c b/metis/ccnx/forwarder/metis/content_store/metis_LRUContentStore.c new file mode 100644 index 00000000..82095882 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_LRUContentStore.c @@ -0,0 +1,530 @@ +/* + * 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. + */ + +#include <config.h> +#include <stdio.h> +#include <sys/queue.h> + +#include <parc/algol/parc_Object.h> +#include <parc/algol/parc_HashCodeTable.h> +#include <parc/algol/parc_DisplayIndented.h> + +#include <ccnx/forwarder/metis/core/metis_Logger.h> + +#include <ccnx/forwarder/metis/content_store/metis_LRUContentStore.h> + +#include <ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.h> +#include <ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.h> +#include <ccnx/forwarder/metis/content_store/metis_LruList.h> +#include <ccnx/forwarder/metis/content_store/metis_TimeOrderedList.h> + +#include <ccnx/forwarder/metis/processor/metis_HashTableFunction.h> + +typedef struct metis_lru_contentstore_stats { + uint64_t countExpiryEvictions; + uint64_t countRCTEvictions; + uint64_t countLruEvictions; + uint64_t countAdds; + uint64_t countHits; + uint64_t countMisses; +} _MetisLRUContentStoreStats; + + +typedef struct metis_lru_contentstore_data { + size_t objectCapacity; + size_t objectCount; + + MetisLogger *logger; + + // This LRU is just for keeping track of insertion and access order. + MetisLruList *lru; + + // These are indexes by name and key ID hash + PARCHashCodeTable *indexByNameHash; + PARCHashCodeTable *indexByNameAndKeyIdHash; + + // These are indexes by time. + MetisTimeOrderedList *indexByRecommendedCacheTime; + MetisTimeOrderedList *indexByExpirationTime; + + // This table is responsible for Releasing our ContentStoreEntries. + PARCHashCodeTable *storageByNameAndObjectHashHash; + + _MetisLRUContentStoreStats stats; +} _MetisLRUContentStore; + + + +static void +_destroyIndexes(_MetisLRUContentStore *store) +{ + if (store->indexByNameHash != NULL) { + parcHashCodeTable_Destroy(&(store->indexByNameHash)); + } + + if (store->indexByNameAndKeyIdHash != NULL) { + parcHashCodeTable_Destroy(&(store->indexByNameAndKeyIdHash)); + } + + if (store->indexByRecommendedCacheTime != NULL) { + metisTimeOrderedList_Release(&(store->indexByRecommendedCacheTime)); + } + + if (store->indexByExpirationTime != NULL) { + metisTimeOrderedList_Release(&(store->indexByExpirationTime)); + } + + // This tables must go last. It holds the references to the MetisMessage. + if (store->storageByNameAndObjectHashHash != NULL) { + parcHashCodeTable_Destroy(&(store->storageByNameAndObjectHashHash)); + } + + if (store->lru != NULL) { + metisLruList_Destroy(&(store->lru)); + } +} + +static void +_MetisContentStoreInterface_Destroy(MetisContentStoreInterface **storeImplPtr) +{ + _MetisLRUContentStore *store = metisContentStoreInterface_GetPrivateData(*storeImplPtr); + + parcObject_Release((PARCObject **) &store); +} + +static bool +_MetisLRUContentStore_Destructor(_MetisLRUContentStore **storePtr) +{ + _MetisLRUContentStore *store = *storePtr; + + _destroyIndexes(store); + metisLogger_Release(&store->logger); + + return true; +} + +parcObject_Override(_MetisLRUContentStore, PARCObject, + .destructor = (PARCObjectDestructor *) _MetisLRUContentStore_Destructor + ); + +parcObject_ExtendPARCObject(MetisContentStoreInterface, + _MetisContentStoreInterface_Destroy, NULL, NULL, NULL, NULL, NULL, NULL); + +static parcObject_ImplementAcquire(_metisLRUContentStore, MetisContentStoreInterface); +static parcObject_ImplementRelease(_metisLRUContentStore, MetisContentStoreInterface); + +static void +_hashTableFunction_ContentStoreEntryDestroyer(void **dataPtr) +{ + metisContentStoreEntry_Release((MetisContentStoreEntry **) dataPtr); +} + +static bool +_metisLRUContentStore_Init(_MetisLRUContentStore *store, MetisContentStoreConfig *config, MetisLogger *logger) +{ + bool result = false; + + store->logger = metisLogger_Acquire(logger); + + size_t initialSize = config->objectCapacity * 2; + memset(&store->stats, 0, sizeof(_MetisLRUContentStoreStats)); + + store->objectCapacity = config->objectCapacity; + store->objectCount = 0; + + // initial size must be at least 1 or else the data structures break. + initialSize = (initialSize == 0) ? 1 : initialSize; + + store->indexByExpirationTime = + metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + + store->indexByRecommendedCacheTime = + metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareRecommendedCacheTime); + + store->indexByNameHash = parcHashCodeTable_Create_Size(metisHashTableFunction_MessageNameEquals, + metisHashTableFunction_MessageNameHashCode, + NULL, + NULL, + initialSize); + + store->indexByNameAndKeyIdHash = parcHashCodeTable_Create_Size(metisHashTableFunction_MessageNameAndKeyIdEquals, + metisHashTableFunction_MessageNameAndKeyIdHashCode, + NULL, + NULL, + initialSize); + + store->storageByNameAndObjectHashHash = parcHashCodeTable_Create_Size(metisHashTableFunction_MessageNameAndObjectHashEquals, + metisHashTableFunction_MessageNameAndObjectHashHashCode, + NULL, + _hashTableFunction_ContentStoreEntryDestroyer, + initialSize); + + store->lru = metisLruList_Create(); + + // If any of the index tables couldn't be allocated, we can't continue. + if ((store->indexByExpirationTime == NULL) + || (store->indexByNameAndKeyIdHash == NULL) + || (store->indexByNameHash == NULL) + || (store->indexByRecommendedCacheTime == NULL) + || (store->storageByNameAndObjectHashHash == NULL) + || (store->lru == NULL)) { + if (metisLogger_IsLoggable(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Error)) { + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Error, __func__, + "LRUContentStore could not be created. Could not allocate all index tables.", + (void *) store, store->objectCapacity); + } + + _destroyIndexes(store); + result = false; + } else { + result = true; + } + return result; +} + +/** + * Remove a MetisContentStoreEntry from all tables and indices. + */ +static void +_metisLRUContentStore_PurgeStoreEntry(_MetisLRUContentStore *store, MetisContentStoreEntry *entryToPurge) +{ + if (metisContentStoreEntry_HasExpiryTimeTicks(entryToPurge)) { + metisTimeOrderedList_Remove(store->indexByExpirationTime, entryToPurge); + } + + if (metisContentStoreEntry_HasRecommendedCacheTimeTicks(entryToPurge)) { + metisTimeOrderedList_Remove(store->indexByRecommendedCacheTime, entryToPurge); + } + + MetisMessage *content = metisContentStoreEntry_GetMessage(entryToPurge); + parcHashCodeTable_Del(store->indexByNameHash, content); + + if (metisMessage_HasKeyId(content)) { + parcHashCodeTable_Del(store->indexByNameAndKeyIdHash, content); + } + + // This _Del call will call the Release/Destroy on the ContentStoreEntry, + // which will remove it from the LRU as well. + parcHashCodeTable_Del(store->storageByNameAndObjectHashHash, content); + + store->objectCount--; +} + +static bool +_metisLRUContentStore_RemoveLeastUsed(_MetisLRUContentStore *store) +{ + bool result = false; + + if (store->objectCount > 0) { + MetisLruListEntry *lruEntry = metisLruList_PopTail(store->lru); + MetisContentStoreEntry *storeEntry = + (MetisContentStoreEntry *) metisLruList_EntryGetData(lruEntry); + + if (metisLogger_IsLoggable(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "ContentStore %p evict message %p by LRU (LRU evictions %" PRIu64 ")", + (void *) store, (void *) metisContentStoreEntry_GetMessage(storeEntry), + store->stats.countLruEvictions); + } + + _metisLRUContentStore_PurgeStoreEntry(store, storeEntry); + + result = true; + } + return result; +} + +static void +_evictByStorePolicy(_MetisLRUContentStore *store, uint64_t currentTimeInMetisTicks) +{ + // We need to make room. Here's the plan: + // 1) Check to see if anything has expired. If so, remove it and we're done. If not, + // 2) Check to see if anything has exceeded it's recommended cache time. If so, remove it and we're done. If not, + // 3) Remove the least recently used item. + + MetisContentStoreEntry *entry = metisTimeOrderedList_GetOldest(store->indexByExpirationTime); + if (entry + && metisContentStoreEntry_HasExpiryTimeTicks(entry) + && (currentTimeInMetisTicks > metisContentStoreEntry_GetExpiryTimeTicks(entry))) { + // Found an expired entry. Remove it, and we're done. + + store->stats.countExpiryEvictions++; + if (metisLogger_IsLoggable(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "ContentStore %p evict message %p by ExpiryTime (ExpiryTime evictions %" PRIu64 ")", + (void *) store, (void *) metisContentStoreEntry_GetMessage(entry), + store->stats.countExpiryEvictions); + } + + _metisLRUContentStore_PurgeStoreEntry(store, entry); + } else { + // Check for entries that have exceeded RCT + entry = metisTimeOrderedList_GetOldest(store->indexByRecommendedCacheTime); + if (entry + && metisContentStoreEntry_HasRecommendedCacheTimeTicks(entry) + && (currentTimeInMetisTicks > metisContentStoreEntry_GetRecommendedCacheTimeTicks(entry))) { + // Found an entry passed it's RCT. Remove it, and we're done. + + store->stats.countRCTEvictions++; + if (metisLogger_IsLoggable(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "ContentStore %p evict message %p by RCT (RCT evictions %" PRIu64 ")", + (void *) store, (void *) metisContentStoreEntry_GetMessage(entry), + store->stats.countRCTEvictions); + } + + _metisLRUContentStore_PurgeStoreEntry(store, entry); + } else { + store->stats.countLruEvictions++; + _metisLRUContentStore_RemoveLeastUsed(store); + } + } +} + +static bool +_metisLRUContentStore_PutContent(MetisContentStoreInterface *storeImpl, MetisMessage *content, uint64_t currentTimeTicks) + +{ + bool result = false; + _MetisLRUContentStore *store = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(storeImpl); + assertNotNull(store, "Parameter store must be non-null"); + assertNotNull(content, "Parameter objectMessage must be non-null"); + + assertTrue(metisMessage_GetType(content) == MetisMessagePacketType_ContentObject, + "Parameter objectMessage must be a Content Object"); + + if (store->objectCapacity == 0) { + return false; + } + + uint64_t expiryTimeTicks = metisContentStoreEntry_MaxExpiryTime; + uint64_t recommendedCacheTimeTicks = metisContentStoreEntry_MaxRecommendedCacheTime; + + if (metisMessage_HasExpiryTime(content)) { + expiryTimeTicks = metisMessage_GetExpiryTimeTicks(content); + } + + if (metisMessage_HasRecommendedCacheTime(content)) { + recommendedCacheTimeTicks = metisMessage_GetRecommendedCacheTimeTicks(content); + } + + // Don't add anything that's already expired or has exceeded RCT. + if (currentTimeTicks >= expiryTimeTicks || currentTimeTicks >= recommendedCacheTimeTicks) { + return false; + } + + if (store->objectCount >= store->objectCapacity) { + // Store is full. Need to make room. + _evictByStorePolicy(store, currentTimeTicks); + } + + // And now add a new entry to the head of the LRU. + + MetisContentStoreEntry *entry = metisContentStoreEntry_Create(content, store->lru); + + if (entry != NULL) { + if (parcHashCodeTable_Add(store->storageByNameAndObjectHashHash, content, entry)) { + parcHashCodeTable_Add(store->indexByNameHash, content, entry); + + if (metisMessage_HasKeyId(content)) { + parcHashCodeTable_Add(store->indexByNameAndKeyIdHash, content, entry); + } + + if (metisContentStoreEntry_HasExpiryTimeTicks(entry)) { + metisTimeOrderedList_Add(store->indexByExpirationTime, entry); + } + + if (metisContentStoreEntry_HasRecommendedCacheTimeTicks(entry)) { + metisTimeOrderedList_Add(store->indexByRecommendedCacheTime, entry); + } + + store->objectCount++; + store->stats.countAdds++; + + if (metisLogger_IsLoggable(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "LRUContentStore %p saved message %p (object count %" PRIu64 ")", + (void *) store, (void *) content, store->objectCount); + } + + result = true; + } else { + // Free what we just created, but did not add. 'entry' has ownership of 'copy', and so will + // call _Release() on it + metisContentStoreEntry_Release(&entry); + + if (metisLogger_IsLoggable(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Warning)) { + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Warning, __func__, + "LRUContentStore %p failed to add message %p to hash table", + (void *) store, (void *) content); + } + } + } + + return result; +} + +static MetisMessage * +_metisLRUContentStore_MatchInterest(MetisContentStoreInterface *storeImpl, MetisMessage *interest) +{ + MetisMessage *result = NULL; + + _MetisLRUContentStore *store = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(storeImpl); + + assertNotNull(store, "Parameter store must be non-null"); + assertNotNull(interest, "Parameter interestMessage must be non-null"); + assertTrue(metisMessage_GetType(interest) == MetisMessagePacketType_Interest, + "Parameter interestMessage must be an Interest"); + + // This will do the most restrictive lookup. + // a) If the interest has a ContentObjectHash restriction, it will look only in the ByNameAndObjectHash table. + // b) If it has a KeyId, it will look only in the ByNameAndKeyId table. + // c) otherwise, it looks only in the ByName table. + + PARCHashCodeTable *table; + if (metisMessage_HasContentObjectHash(interest)) { + table = store->storageByNameAndObjectHashHash; + } else if (metisMessage_HasKeyId(interest)) { + table = store->indexByNameAndKeyIdHash; + } else { + table = store->indexByNameHash; + } + + MetisContentStoreEntry *storeEntry = parcHashCodeTable_Get(table, interest); + + if (storeEntry) { + metisContentStoreEntry_MoveToHead(storeEntry); + result = metisContentStoreEntry_GetMessage(storeEntry); + + store->stats.countHits++; + + if (metisLogger_IsLoggable(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "LRUContentStore %p matched interest %p (hits %" PRIu64 ", misses %" PRIu64 ")", + (void *) store, (void *) interest, store->stats.countHits, store->stats.countMisses); + } + } else { + store->stats.countMisses++; + + if (metisLogger_IsLoggable(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug)) { + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug, __func__, + "LRUContentStore %p missed interest %p (hits %" PRIu64 ", misses %" PRIu64 ")", + (void *) store, (void *) interest, store->stats.countHits, store->stats.countMisses); + } + } + + return result; +} + +static bool +_metisLRUContentStore_RemoveContent(MetisContentStoreInterface *storeImpl, MetisMessage *content) +{ + bool result = false; + _MetisLRUContentStore *store = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(storeImpl); + + MetisContentStoreEntry *storeEntry = parcHashCodeTable_Get(store->storageByNameAndObjectHashHash, content); + + if (storeEntry != NULL) { + _metisLRUContentStore_PurgeStoreEntry(store, storeEntry); + result = true; + } + + return result; +} + +static void +_metisLRUContentStore_Log(MetisContentStoreInterface *storeImpl) +{ + _MetisLRUContentStore *store = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(storeImpl); + + metisLogger_Log(store->logger, MetisLoggerFacility_Processor, PARCLogLevel_All, __func__, + "MetisLRUContentStore @%p {count = %zu, capacity = %zu {" + "stats = @%p {adds = %" PRIu64 ", hits = %" PRIu64 ", misses = %" PRIu64 ", LRUEvictons = %" PRIu64 + ", ExpiryEvictions = %" PRIu64 ", RCTEvictions = %" PRIu64 "} }", + store, + store->objectCount, + store->objectCapacity, + &store->stats, + store->stats.countAdds, + store->stats.countHits, + store->stats.countMisses, + store->stats.countLruEvictions, + store->stats.countExpiryEvictions, + store->stats.countRCTEvictions); +} + +static size_t +_metisLRUContentStore_GetObjectCapacity(MetisContentStoreInterface *storeImpl) +{ + _MetisLRUContentStore *store = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(storeImpl); + return store->objectCapacity; +} + +static size_t +_metisLRUContentStore_GetObjectCount(MetisContentStoreInterface *storeImpl) +{ + _MetisLRUContentStore *store = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(storeImpl); + return store->objectCount; +} + +static size_t +_metisLRUContentStore_SetObjectCapacity(MetisContentStoreInterface *storeImpl, size_t newCapacity) +{ + _MetisLRUContentStore *store = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(storeImpl); + return store->objectCapacity = newCapacity; +} + +MetisContentStoreInterface * +metisLRUContentStore_Create(MetisContentStoreConfig *config, MetisLogger *logger) +{ + MetisContentStoreInterface *storeImpl = NULL; + + assertNotNull(logger, "MetisLRUContentStore requires a non-NULL logger"); + + storeImpl = parcObject_CreateAndClearInstance(MetisContentStoreInterface); + + if (storeImpl != NULL) { + storeImpl->_privateData = parcObject_CreateAndClearInstance(_MetisLRUContentStore); + + if (_metisLRUContentStore_Init(storeImpl->_privateData, config, logger)) { + storeImpl->putContent = &_metisLRUContentStore_PutContent; + storeImpl->removeContent = &_metisLRUContentStore_RemoveContent; + + storeImpl->matchInterest = &_metisLRUContentStore_MatchInterest; + + storeImpl->getObjectCount = &_metisLRUContentStore_GetObjectCount; + storeImpl->getObjectCapacity = &_metisLRUContentStore_GetObjectCapacity; + + storeImpl->log = &_metisLRUContentStore_Log; + + storeImpl->acquire = &_metisLRUContentStore_Acquire; + storeImpl->release = &_metisLRUContentStore_Release; + + // Initialize from the config passed to us. + _metisLRUContentStore_SetObjectCapacity(storeImpl, config->objectCapacity); + + if (metisLogger_IsLoggable(logger, MetisLoggerFacility_Processor, PARCLogLevel_Info)) { + metisLogger_Log(logger, MetisLoggerFacility_Processor, PARCLogLevel_Info, __func__, + "LRUContentStore %p created with capacity %zu", + (void *) storeImpl, metisContentStoreInterface_GetObjectCapacity(storeImpl)); + } + } + } else { + parcObject_Release((void **) &storeImpl); + } + + return storeImpl; +} + |