1 files changed, 455 insertions, 0 deletions
diff --git a/hicn-light/src/content_store/contentStoreLRU.c b/hicn-light/src/content_store/contentStoreLRU.c
new file mode 100755
index 000000000..9b69d51c0
--- /dev/null
+++ b/hicn-light/src/content_store/contentStoreLRU.c
@@ -0,0 +1,455 @@
+/*
+ * 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 <sys/queue.h>
+
+#include <parc/algol/parc_DisplayIndented.h>
+#include <parc/algol/parc_HashCodeTable.h>
+#include <parc/algol/parc_Object.h>
+
+#include <src/core/logger.h>
+
+#include <src/content_store/contentStoreLRU.h>
+
+#include <src/content_store/contentStoreEntry.h>
+#include <src/content_store/contentStoreInterface.h>
+#include <src/content_store/listLRU.h>
+#include <src/content_store/listTimeOrdered.h>
+
+#include <parc/assert/parc_Assert.h>
+#include <src/processor/hashTableFunction.h>
+
+typedef struct contentstore_stats {
+  uint64_t countExpiryEvictions;
+  uint64_t countRCTEvictions;
+  uint64_t countLruEvictions;
+  uint64_t countAdds;
+  uint64_t countHits;
+  uint64_t countMisses;
+} _ContentStoreLRUStats;
+
+typedef struct contentstore_lru_data {
+  size_t objectCapacity;
+  size_t objectCount;
+
+  Logger *logger;
+
+  // This LRU is just for keeping track of insertion and access order.
+  ListLru *lru;
+
+  ListTimeOrdered *indexByExpirationTime;
+
+  PARCHashCodeTable *storageByName;
+
+  _ContentStoreLRUStats stats;
+} _ContentStoreLRU;
+
+static void _destroyIndexes(_ContentStoreLRU *store) {
+  if (store->indexByExpirationTime != NULL) {
+    listTimeOrdered_Release(&(store->indexByExpirationTime));
+  }
+
+  if (store->storageByName != NULL) {
+    parcHashCodeTable_Destroy(&(store->storageByName));
+  }
+
+  if (store->lru != NULL) {
+    listLRU_Destroy(&(store->lru));
+  }
+}
+
+static void _contentStoreInterface_Destroy(
+    ContentStoreInterface **storeImplPtr) {
+  _ContentStoreLRU *store = contentStoreInterface_GetPrivateData(*storeImplPtr);
+
+  parcObject_Release((PARCObject **)&store);
+}
+
+static bool _contentStoreLRU_Destructor(_ContentStoreLRU **storePtr) {
+  _ContentStoreLRU *store = *storePtr;
+
+  _destroyIndexes(store);
+  logger_Release(&store->logger);
+
+  return true;
+}
+
+parcObject_Override(_ContentStoreLRU, PARCObject,
+                    .destructor = (PARCObjectDestructor *)
+                        _contentStoreLRU_Destructor);
+
+parcObject_ExtendPARCObject(ContentStoreInterface,
+                            _contentStoreInterface_Destroy, NULL, NULL, NULL,
+                            NULL, NULL, NULL);
+
+static parcObject_ImplementAcquire(_contentStoreLRU, ContentStoreInterface);
+static parcObject_ImplementRelease(_contentStoreLRU, ContentStoreInterface);
+
+static void _hashTableFunction_ContentStoreEntryDestroyer(void **dataPtr) {
+  contentStoreEntry_Release((ContentStoreEntry **)dataPtr);
+}
+
+static bool _contentStoreLRU_Init(_ContentStoreLRU *store,
+                                  ContentStoreConfig *config, Logger *logger) {
+  bool result = false;
+
+  store->logger = logger_Acquire(logger);
+
+  size_t initialSize = config->objectCapacity * 2;
+  memset(&store->stats, 0, sizeof(_ContentStoreLRUStats));
+
+  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 = listTimeOrdered_Create(
+      (TimeOrderList_KeyCompare *)contentStoreEntry_CompareExpiryTime);
+
+  store->storageByName = parcHashCodeTable_Create_Size(
+      hashTableFunction_MessageNameEquals,
+      hashTableFunction_MessageNameHashCode, NULL,
+      _hashTableFunction_ContentStoreEntryDestroyer, initialSize);
+
+  store->lru = listLRU_Create();
+
+  // If any of the index tables couldn't be allocated, we can't continue.
+  if ((store->indexByExpirationTime == NULL) ||
+      (store->storageByName == NULL) || (store->lru == NULL)) {
+    if (logger_IsLoggable(store->logger, LoggerFacility_Processor,
+                          PARCLogLevel_Error)) {
+      logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Error,
+                 __func__,
+                 "ContentStoreLRU 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 ContentStoreEntry from all tables and indices.
+ */
+static void _contentStoreLRU_PurgeStoreEntry(_ContentStoreLRU *store,
+                                             ContentStoreEntry *entryToPurge) {
+  if (contentStoreEntry_HasExpiryTimeTicks(entryToPurge)) {
+    listTimeOrdered_Remove(store->indexByExpirationTime, entryToPurge);
+  }
+
+  Message *content = contentStoreEntry_GetMessage(entryToPurge);
+
+  // This _Del call will call the Release/Destroy on the ContentStoreEntry,
+  // which will remove it from the LRU as well.
+  parcHashCodeTable_Del(store->storageByName, content);
+
+  store->objectCount--;
+}
+
+static bool _contentStoreLRU_RemoveLeastUsed(_ContentStoreLRU *store) {
+  bool result = false;
+
+  if (store->objectCount > 0) {
+    ListLruEntry *lruEntry = listLRU_PopTail(store->lru);
+    ContentStoreEntry *storeEntry =
+        (ContentStoreEntry *)listLRU_EntryGetData(lruEntry);
+
+    if (logger_IsLoggable(store->logger, LoggerFacility_Processor,
+                          PARCLogLevel_Debug)) {
+      logger_Log(
+          store->logger, LoggerFacility_Processor, PARCLogLevel_Debug, __func__,
+          "ContentStore %p evict message %p by LRU (LRU evictions %" PRIu64 ")",
+          (void *)store, (void *)contentStoreEntry_GetMessage(storeEntry),
+          store->stats.countLruEvictions);
+    }
+
+    _contentStoreLRU_PurgeStoreEntry(store, storeEntry);
+
+    result = true;
+  }
+  return result;
+}
+
+static void _evictByStorePolicy(_ContentStoreLRU *store,
+                                uint64_t currentTimeInTicks) {
+  // 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) Remove the least recently used item.
+
+  ContentStoreEntry *entry =
+      listTimeOrdered_GetOldest(store->indexByExpirationTime);
+  if (entry && contentStoreEntry_HasExpiryTimeTicks(entry) &&
+      (currentTimeInTicks > contentStoreEntry_GetExpiryTimeTicks(entry))) {
+    // Found an expired entry. Remove it, and we're done.
+
+    store->stats.countExpiryEvictions++;
+    if (logger_IsLoggable(store->logger, LoggerFacility_Processor,
+                          PARCLogLevel_Debug)) {
+      logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Debug,
+                 __func__,
+                 "ContentStore %p evict message %p by ExpiryTime (ExpiryTime "
+                 "evictions %" PRIu64 ")",
+                 (void *)store, (void *)contentStoreEntry_GetMessage(entry),
+                 store->stats.countExpiryEvictions);
+    }
+
+    _contentStoreLRU_PurgeStoreEntry(store, entry);
+  } else {
+    store->stats.countLruEvictions++;
+    _contentStoreLRU_RemoveLeastUsed(store);
+  }
+}
+
+static bool _contentStoreLRU_PutContent(ContentStoreInterface *storeImpl,
+                                        Message *content,
+                                        uint64_t currentTimeTicks)
+
+{
+  bool result = false;
+  _ContentStoreLRU *store =
+      (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl);
+  parcAssertNotNull(store, "Parameter store must be non-null");
+  parcAssertNotNull(content, "Parameter objectMessage must be non-null");
+
+  parcAssertTrue(message_GetType(content) == MessagePacketType_ContentObject,
+                 "Parameter objectMessage must be a Content Object");
+
+  if (store->objectCapacity == 0) {
+    return false;
+  }
+
+  uint64_t expiryTimeTicks = contentStoreEntry_MaxExpiryTime;
+
+  if (message_HasContentExpiryTime(content)) {
+    expiryTimeTicks = message_GetContentExpiryTimeTicks(content);
+  }
+  // Don't add anything that's already expired or has exceeded RCT.
+  if (currentTimeTicks >= expiryTimeTicks) {
+    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.
+
+  ContentStoreEntry *entry = contentStoreEntry_Create(content, store->lru);
+
+  if (entry != NULL) {
+    if (parcHashCodeTable_Add(store->storageByName, content, entry)) {
+      if (contentStoreEntry_HasExpiryTimeTicks(entry)) {
+        listTimeOrdered_Add(store->indexByExpirationTime, entry);
+      }
+
+      store->objectCount++;
+      store->stats.countAdds++;
+
+      if (logger_IsLoggable(store->logger, LoggerFacility_Processor,
+                            PARCLogLevel_Debug)) {
+        logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Debug,
+                   __func__,
+                   "ContentStoreLRU %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
+      contentStoreEntry_Release(&entry);
+
+      if (logger_IsLoggable(store->logger, LoggerFacility_Processor,
+                            PARCLogLevel_Warning)) {
+        logger_Log(store->logger, LoggerFacility_Processor,
+                   PARCLogLevel_Warning, __func__,
+                   "ContentStoreLRU %p failed to add message %p to hash table",
+                   (void *)store, (void *)content);
+      }
+    }
+  }
+
+  return result;
+}
+
+static Message *_contentStoreLRU_MatchInterest(ContentStoreInterface *storeImpl,
+                                               Message *interest,
+                                               uint64_t currentTimeTicks) {
+  Message *result = NULL;
+
+  _ContentStoreLRU *store =
+      (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl);
+
+  parcAssertNotNull(store, "Parameter store must be non-null");
+  parcAssertNotNull(interest, "Parameter interestMessage must be non-null");
+  parcAssertTrue(message_GetType(interest) == MessagePacketType_Interest,
+                 "Parameter interestMessage must be an Interest");
+
+  PARCHashCodeTable *table;
+  table = store->storageByName;
+
+  ContentStoreEntry *storeEntry = parcHashCodeTable_Get(table, interest);
+
+  bool foundEntry = false;
+
+  if (storeEntry) {
+    if (contentStoreEntry_HasExpiryTimeTicks(storeEntry) &&
+        contentStoreEntry_GetExpiryTimeTicks(storeEntry) < currentTimeTicks) {
+      // the entry is expired, we can remove it
+      _contentStoreLRU_PurgeStoreEntry(store, storeEntry);
+    } else {
+      foundEntry = true;
+    }
+  }
+
+  if (foundEntry) {
+    contentStoreEntry_MoveToHead(storeEntry);
+    result = contentStoreEntry_GetMessage(storeEntry);
+
+    store->stats.countHits++;
+
+    if (logger_IsLoggable(store->logger, LoggerFacility_Processor,
+                          PARCLogLevel_Debug)) {
+      logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Debug,
+                 __func__,
+                 "ContentStoreLRU %p matched interest %p (hits %" PRIu64
+                 ", misses %" PRIu64 ")",
+                 (void *)store, (void *)interest, store->stats.countHits,
+                 store->stats.countMisses);
+    }
+  } else {
+    store->stats.countMisses++;
+
+    if (logger_IsLoggable(store->logger, LoggerFacility_Processor,
+                          PARCLogLevel_Debug)) {
+      logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_Debug,
+                 __func__,
+                 "ContentStoreLRU %p missed interest %p (hits %" PRIu64
+                 ", misses %" PRIu64 ")",
+                 (void *)store, (void *)interest, store->stats.countHits,
+                 store->stats.countMisses);
+    }
+  }
+
+  return result;
+}
+
+static bool _contentStoreLRU_RemoveContent(ContentStoreInterface *storeImpl,
+                                           Message *content) {
+  bool result = false;
+  _ContentStoreLRU *store =
+      (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl);
+
+  ContentStoreEntry *storeEntry =
+      parcHashCodeTable_Get(store->storageByName, content);
+
+  if (storeEntry != NULL) {
+    _contentStoreLRU_PurgeStoreEntry(store, storeEntry);
+    result = true;
+  }
+
+  return result;
+}
+
+static void _contentStoreLRU_Log(ContentStoreInterface *storeImpl) {
+  _ContentStoreLRU *store =
+      (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl);
+
+  logger_Log(store->logger, LoggerFacility_Processor, PARCLogLevel_All,
+             __func__,
+             "ContentStoreLRU @%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 _contentStoreLRU_GetObjectCapacity(
+    ContentStoreInterface *storeImpl) {
+  _ContentStoreLRU *store =
+      (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl);
+  return store->objectCapacity;
+}
+
+static size_t _contentStoreLRU_GetObjectCount(
+    ContentStoreInterface *storeImpl) {
+  _ContentStoreLRU *store =
+      (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl);
+  return store->objectCount;
+}
+
+static size_t _contentStoreLRU_SetObjectCapacity(
+    ContentStoreInterface *storeImpl, size_t newCapacity) {
+  _ContentStoreLRU *store =
+      (_ContentStoreLRU *)contentStoreInterface_GetPrivateData(storeImpl);
+  return store->objectCapacity = newCapacity;
+}
+
+ContentStoreInterface *contentStoreLRU_Create(ContentStoreConfig *config,
+                                              Logger *logger) {
+  ContentStoreInterface *storeImpl = NULL;
+
+  parcAssertNotNull(logger, "ContentStoreLRU requires a non-NULL logger");
+
+  storeImpl = parcObject_CreateAndClearInstance(ContentStoreInterface);
+
+  if (storeImpl != NULL) {
+    storeImpl->_privateData =
+        parcObject_CreateAndClearInstance(_ContentStoreLRU);
+
+    if (_contentStoreLRU_Init(storeImpl->_privateData, config, logger)) {
+      storeImpl->putContent = &_contentStoreLRU_PutContent;
+      storeImpl->removeContent = &_contentStoreLRU_RemoveContent;
+
+      storeImpl->matchInterest = &_contentStoreLRU_MatchInterest;
+
+      storeImpl->getObjectCount = &_contentStoreLRU_GetObjectCount;
+      storeImpl->getObjectCapacity = &_contentStoreLRU_GetObjectCapacity;
+
+      storeImpl->log = &_contentStoreLRU_Log;
+
+      storeImpl->acquire = &_contentStoreLRU_Acquire;
+      storeImpl->release = &_contentStoreLRU_Release;
+
+      // Initialize from the config passed to us.
+      _contentStoreLRU_SetObjectCapacity(storeImpl, config->objectCapacity);
+
+      if (logger_IsLoggable(logger, LoggerFacility_Processor,
+                            PARCLogLevel_Info)) {
+        logger_Log(logger, LoggerFacility_Processor, PARCLogLevel_Info,
+                   __func__, "ContentStoreLRU %p created with capacity %zu",
+                   (void *)storeImpl,
+                   contentStoreInterface_GetObjectCapacity(storeImpl));
+      }
+    }
+  } else {
+    parcObject_Release((void **)&storeImpl);
+  }
+
+  return storeImpl;
+}