diff options
Diffstat (limited to 'hicn-light/src/hicn/content_store')
| -rw-r--r-- | hicn-light/src/hicn/content_store/CMakeLists.txt | 14 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/contentStoreEntry.c | 136 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/contentStoreEntry.h | 146 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/contentStoreInterface.c | 57 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/contentStoreInterface.h | 211 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/contentStoreLRU.c | 462 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/contentStoreLRU.h | 39 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/listLRU.c | 135 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/listLRU.h | 94 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/listTimeOrdered.c | 94 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/listTimeOrdered.h | 103 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/lru.c | 190 | ||||
| -rw-r--r-- | hicn-light/src/hicn/content_store/lru.h | 34 |
13 files changed, 227 insertions, 1488 deletions
diff --git a/hicn-light/src/hicn/content_store/CMakeLists.txt b/hicn-light/src/hicn/content_store/CMakeLists.txt index 85643cf5e..45cfe2267 100644 --- a/hicn-light/src/hicn/content_store/CMakeLists.txt +++ b/hicn-light/src/hicn/content_store/CMakeLists.txt @@ -14,20 +14,12 @@ cmake_minimum_required(VERSION 3.5 FATAL_ERROR) list(APPEND HEADER_FILES - ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreEntry.h - ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreInterface.h - ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreLRU.h - ${CMAKE_CURRENT_SOURCE_DIR}/listTimeOrdered.h - ${CMAKE_CURRENT_SOURCE_DIR}/listLRU.h + ${CMAKE_CURRENT_SOURCE_DIR}/lru.h ) list(APPEND SOURCE_FILES - ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreInterface.c - ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreLRU.c - ${CMAKE_CURRENT_SOURCE_DIR}/listLRU.c - ${CMAKE_CURRENT_SOURCE_DIR}/listTimeOrdered.c - ${CMAKE_CURRENT_SOURCE_DIR}/contentStoreEntry.c + ${CMAKE_CURRENT_SOURCE_DIR}/lru.c ) set(SOURCE_FILES ${SOURCE_FILES} PARENT_SCOPE) -set(HEADER_FILES ${HEADER_FILES} PARENT_SCOPE)
\ No newline at end of file +set(HEADER_FILES ${HEADER_FILES} PARENT_SCOPE) diff --git a/hicn-light/src/hicn/content_store/contentStoreEntry.c b/hicn-light/src/hicn/content_store/contentStoreEntry.c deleted file mode 100644 index 45f98881e..000000000 --- a/hicn-light/src/hicn/content_store/contentStoreEntry.c +++ /dev/null @@ -1,136 +0,0 @@ -/* - * 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 <hicn/hicn-light/config.h> -#include <stdio.h> - -#include <parc/algol/parc_Memory.h> -#include <hicn/content_store/contentStoreEntry.h> - -#include <parc/assert/parc_Assert.h> - -const uint64_t contentStoreEntry_MaxExpiryTime = UINT64_MAX; - -struct contentstore_entry { - Message *message; - ListLruEntry *lruEntry; - unsigned refcount; - bool hasExpiryTimeTicks; - uint64_t expiryTimeTicks; -}; - -ContentStoreEntry *contentStoreEntry_Create(Message *contentMessage, - ListLru *listLRU) { - parcAssertNotNull(contentMessage, "Parameter objectMessage must be non-null"); - - ContentStoreEntry *entry = - parcMemory_AllocateAndClear(sizeof(ContentStoreEntry)); - parcAssertNotNull(entry, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(ContentStoreEntry)); - entry->message = message_Acquire(contentMessage); - entry->refcount = 1; - - if (listLRU != NULL) { - entry->lruEntry = listLRU_NewHeadEntry(listLRU, entry); - } - - entry->hasExpiryTimeTicks = message_HasContentExpiryTime(contentMessage); - - if (entry->hasExpiryTimeTicks) { - entry->expiryTimeTicks = message_GetContentExpiryTimeTicks(contentMessage); - } - - return entry; -} - -ContentStoreEntry *contentStoreEntry_Acquire( - const ContentStoreEntry *original) { - parcAssertNotNull(original, "Parameter must be non-null"); - ((ContentStoreEntry *)original)->refcount++; - return (ContentStoreEntry *)original; -} - -void contentStoreEntry_Release(ContentStoreEntry **entryPtr) { - parcAssertNotNull(entryPtr, "Parameter must be non-null double pointer"); - parcAssertNotNull(*entryPtr, - "Parameter must dereference to non-null pointer"); - - ContentStoreEntry *entry = *entryPtr; - parcAssertTrue(entry->refcount > 0, "Illegal state: has refcount of 0"); - - entry->refcount--; - if (entry->refcount == 0) { - if (entry->lruEntry) { - listLRU_EntryDestroy(&entry->lruEntry); - } - message_Release(&entry->message); - parcMemory_Deallocate((void **)&entry); - } - *entryPtr = NULL; -} - -Message *contentStoreEntry_GetMessage(const ContentStoreEntry *storeEntry) { - parcAssertNotNull(storeEntry, "Parameter must be non-null"); - return storeEntry->message; -} - -bool contentStoreEntry_HasExpiryTimeTicks(const ContentStoreEntry *storeEntry) { - parcAssertNotNull(storeEntry, "Parameter must be non-null"); - return storeEntry->hasExpiryTimeTicks; -} - -uint64_t contentStoreEntry_GetExpiryTimeTicks( - const ContentStoreEntry *storeEntry) { - parcAssertNotNull(storeEntry, "Parameter must be non-null"); - parcAssertTrue(storeEntry->hasExpiryTimeTicks, - "storeEntry has no ExpiryTimeTicks. Did you call " - "contentStoreEntry_HasExpiryTimeTicks() first?"); - return storeEntry->expiryTimeTicks; -} - -int contentStoreEntry_CompareExpiryTime(const ContentStoreEntry *value1, - const ContentStoreEntry *value2) { - // A signum comparison. negative if key 1 is smaller, 0 if key1 == key2, - // greater than 0 if key1 is bigger. - - ContentStoreEntry *v1 = (ContentStoreEntry *)value1; - ContentStoreEntry *v2 = (ContentStoreEntry *)value2; - - if (v1->expiryTimeTicks < v2->expiryTimeTicks) { - return -1; - } else if (v1->expiryTimeTicks > v2->expiryTimeTicks) { - return +1; - } else { - // At this point, the times are the same. Use the address of the message as - // the decider. This allows us to store multiple messages with the same - // expiry/cache time. - if (v1->message < v2->message) { - return -1; - } else if (v1->message > v2->message) { - return +1; - } - } - - return 0; // The same message has been encountered. -} - -void contentStoreEntry_MoveToHead(ContentStoreEntry *storeEntry) { - parcAssertNotNull(storeEntry, "Parameter must be non-null"); - parcAssertNotNull(storeEntry->lruEntry, - "ContentStoreEntry is not attached to an ListLru"); - if (storeEntry->lruEntry) { - listLRU_EntryMoveToHead(storeEntry->lruEntry); - } -} diff --git a/hicn-light/src/hicn/content_store/contentStoreEntry.h b/hicn-light/src/hicn/content_store/contentStoreEntry.h deleted file mode 100644 index 4f0fd19c1..000000000 --- a/hicn-light/src/hicn/content_store/contentStoreEntry.h +++ /dev/null @@ -1,146 +0,0 @@ -/* - * 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 contentStoreEntry_h -#define contentStoreEntry_h - -#include <hicn/content_store/listLRU.h> -#include <hicn/core/message.h> - -struct contentstore_entry; -typedef struct contentstore_entry ContentStoreEntry; - -/** - * The max time allowed for an ExpiryTime. Will never be exceeded. - */ -extern const uint64_t contentStoreEntry_MaxExpiryTime; - -/** - * Creates a new `ContentStoreEntry` instance, acquiring a reference to the - * supplied `Message`. - * - * @param message the message to store - * @param listLRU the LRU list that this entry will be stored in. - * @return A newly created `ContentStoreEntry` instance that must eventually be - * released by calling - * {@link contentStoreEntry_Release}. - * - * @see contentStoreEntry_Release - */ -ContentStoreEntry *contentStoreEntry_Create(Message *objectMessage, - ListLru *listLRU); - -/** - * Returns a reference counted copy of the supplied `ContentStoreEntry`. - * - * @param original the ContentStoreEntry to return a reference to. - * @return Reference counted copy, must call - * <code>contentStoreEntry_Destroy()</code> on it. - */ -ContentStoreEntry *contentStoreEntry_Acquire(const ContentStoreEntry *original); - -/** - * Releases one reference count and destroys object when reaches zero - * - * @param [in,out] entryPtr A pointer to an allocated ContentStoreEntry - * - */ -void contentStoreEntry_Release(ContentStoreEntry **entryPtr); - -/** - * Returns a pointer to the contained {@link Message}. - * The caller must called {@link message_Acquire()} if they want to keep a - * reference to the returned message. - * - * @param storeEntry the ContentStoreEntry from which to retrieve the `Message` - * pointer. - * @return the address of the `Message` contained in the storeEntry. - * @see message_Acquire - */ -Message *contentStoreEntry_GetMessage(const ContentStoreEntry *storeEntry); - -/** - * Return true if the message stored in this `ContentStoreEntry` has an - * ExpiryTime. - * - * @param storeEntry the ContentStoreEntry containing the message. - * @return true if the referenced message has an ExpiryTime. False, otherwise. - */ -bool contentStoreEntry_HasExpiryTimeTicks(const ContentStoreEntry *storeEntry); - -/** - * Return the ExpiryTime stored in this `ContentStoreEntry`. - * - * @param storeEntry the ContentStoreEntry from which to retrieve the `Message` - * pointer. - * @return the address of the `Message` contained in the storeEntry. - */ -uint64_t contentStoreEntry_GetExpiryTimeTicks( - const ContentStoreEntry *storeEntry); - -/** - * A signum function comparing two `ContentStoreEntry` instances, using their - * ExpiryTime and, if necessary, the addresses of the referenced Message. In - * other words, if two ContentStoreEntries have the same ExpiryTime, the - * comparison will then be made on the memory addresses of the Messages - * referenced by the ContentStoreEntrys. So, the only way two ContentStoreEntrys - * will compare equally (0) is if they both have the same ExpiryTime and - * reference the same Message. - * - * Used to determine the ordering relationship of two `ContentStoreEntry` - * instances. This is used by the {@link ListTimeOrdered} to keep a list of - * ContentStoreEntrys, sorted by ExpiryTime. - * - * @param [in] storeEntry1 A pointer to a `ContentStoreEntry` instance. - * @param [in] storeEntry2 A pointer to a `ContentStoreEntry` instance to be - * compared to `storeEntry1`. - * - * @return 0 if `storeEntry1` and `storeEntry2` are equivalent - * @return < 0 if `storeEntry1` < `storeEntry2` - * @return > 0 if `storeEntry1` > `storeEntry2` - * - * Example: - * @code - * { - * ContentStoreEntry *entry1 = contentStoreEntry_Create(...); - * ContentStoreEntry *entry2 = contentStoreEntry_Create(...); - * - * int val = contentStoreEntry_CompareExpiryTime(entry1, entry2); - * if (val < 0) { - * // entry1 has a lower ExpiryTime, or the same ExpiryTime as entry2 - * and a different message. } else if (val > 0) { - * // entry2 has a lower ExpiryTime, or the same ExpiryTime as entry1 - * and a different message. } else { - * // entry1 and entry2 have the same ExpiryTime AND the same message. - * } - * - * contentStoreEntry_Release(&entry1); - * contentStoreEntry_Release(&entry2); - * - * } - * @endcode - */ -int contentStoreEntry_CompareExpiryTime(const ContentStoreEntry *storeEntry1, - const ContentStoreEntry *storeEntry2); - -/** - * Move this entry to the head of the LRU list - * - * Moves the entry to the head of the LRU list it was created with - * - * @param [in] storeEntry An allocated ContenstoreEntry - */ -void contentStoreEntry_MoveToHead(ContentStoreEntry *storeEntry); -#endif // contentStoreEntry_h diff --git a/hicn-light/src/hicn/content_store/contentStoreInterface.c b/hicn-light/src/hicn/content_store/contentStoreInterface.c deleted file mode 100644 index 2f5ddb8c2..000000000 --- a/hicn-light/src/hicn/content_store/contentStoreInterface.c +++ /dev/null @@ -1,57 +0,0 @@ -/* - * 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 <hicn/hicn-light/config.h> -#include <stdio.h> - -#include <hicn/content_store/contentStoreInterface.h> - -void contentStoreInterface_Release(ContentStoreInterface **storeImplPtr) { - (*storeImplPtr)->release(storeImplPtr); -} - -bool contentStoreInterface_PutContent(ContentStoreInterface *storeImpl, - Message *content, - uint64_t currentTimeTicks) { - return storeImpl->putContent(storeImpl, content, currentTimeTicks); -} - -bool contentStoreInterface_RemoveContent(ContentStoreInterface *storeImpl, - Message *content) { - return storeImpl->removeContent(storeImpl, content); -} - -Message *contentStoreInterface_MatchInterest(ContentStoreInterface *storeImpl, - Message *interest, - uint64_t currentTimeTicks) { - return storeImpl->matchInterest(storeImpl, interest, currentTimeTicks); -} - -size_t contentStoreInterface_GetObjectCapacity( - ContentStoreInterface *storeImpl) { - return storeImpl->getObjectCapacity(storeImpl); -} - -size_t contentStoreInterface_GetObjectCount(ContentStoreInterface *storeImpl) { - return storeImpl->getObjectCount(storeImpl); -} - -void contentStoreInterface_Log(ContentStoreInterface *storeImpl) { - storeImpl->log(storeImpl); -} - -void *contentStoreInterface_GetPrivateData(ContentStoreInterface *storeImpl) { - return storeImpl->_privateData; -} diff --git a/hicn-light/src/hicn/content_store/contentStoreInterface.h b/hicn-light/src/hicn/content_store/contentStoreInterface.h deleted file mode 100644 index b2bc3f919..000000000 --- a/hicn-light/src/hicn/content_store/contentStoreInterface.h +++ /dev/null @@ -1,211 +0,0 @@ -/* - * 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 contentStoreInterface_h -#define contentStoreInterface_h - -#include <stdio.h> - -#include <hicn/core/message.h> - -typedef struct contentstore_config { - size_t objectCapacity; -} ContentStoreConfig; - -typedef struct contentstore_interface ContentStoreInterface; - -struct contentstore_interface { - /** - * Place a Message representing a ContentObject into the ContentStore. If - * necessary to make room, remove expired content or content that has exceeded - * the Recommended Cache Time. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * @param content - a pointer to a `Message` to place in the store. - * @param currentTimeTicks - the current time, in hicn-light ticks, since the - * UTC epoch. - */ - bool (*putContent)(ContentStoreInterface *storeImpl, Message *content, - uint64_t currentTimeTicks); - - /** - * The function to call to remove content from the ContentStore. - * It will Release any references that were created when the content was - * placed into the ContentStore. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * @param content - a pointer to a `Message` to remove from the store. - */ - bool (*removeContent)(ContentStoreInterface *storeImpl, Message *content); - - /** - * Given a Message that represents and Interest, try to find a matching - * ContentObject. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * @param interest - a pointer to a `Message` representing the Interest to - * match. - * - * @return a pointer to a Message containing the matching ContentObject - * @return NULL if no matching ContentObject was found - */ - Message *(*matchInterest)(ContentStoreInterface *storeImpl, Message *interest, - uint64_t currentTimeTicks); - - /** - * Return the maximum number of ContentObjects that can be stored in this - * ContentStore. This is a raw count, not based on memory size. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * - * @return the maximum number of ContentObjects that can be stored - */ - size_t (*getObjectCapacity)(ContentStoreInterface *storeImpl); - - /** - * Return the number of ContentObjects currently stored in the ContentStore. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * - * @return the current number of ContentObjects in the ContentStore - */ - size_t (*getObjectCount)(ContentStoreInterface *storeImpl); - - /** - * Log a ContentStore implementation specific version of store-related - * information. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - */ - void (*log)(ContentStoreInterface *storeImpl); - - /** - * Acquire a new reference to the specified ContentStore instance. This - * reference will eventually need to be released by calling {@link - * contentStoreInterface_Release}. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - */ - ContentStoreInterface *(*acquire)(const ContentStoreInterface *storeImpl); - - /** - * Release the ContentStore, which will also Release any references held by - * it. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - */ - void (*release)(ContentStoreInterface **storeImpl); - - /** - * A pointer to opaque private data used by the ContentStore instance - * represented by this instance of ContentStoreInterface. - */ - void *_privateData; -}; - -/** - * Place a Message representing a ContentObject into the ContentStore. If - * necessary to make room, remove expired content or content that has exceeded - * the Recommended Cache Time. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * @param content - a pointer to a `Message` to place in the store. - * - * @param currentTimeTicks - the current time, in hicn-light ticks, since the - * UTC epoch. - */ -bool contentStoreInterface_PutContent(ContentStoreInterface *storeImpl, - Message *content, - uint64_t currentTimeTicks); - -/** - * The function to call to remove content from the ContentStore. - * It will Release any references that were created when the content was placed - * into the ContentStore. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * @param content - a pointer to a `Message` to remove from the store. - */ -bool contentStoreInterface_RemoveContent(ContentStoreInterface *storeImpl, - Message *content); - -/** - * Given a Message that represents and Interest, try to find a matching - * ContentObject. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * @param interest - a pointer to a `Message` representing the Interest to - * match. - * - * @return a pointer to a Message containing the matching ContentObject - * @return NULL if no matching ContentObject was found - */ -Message *contentStoreInterface_MatchInterest(ContentStoreInterface *storeImpl, - Message *interest, - uint64_t currentTimeTicks); - -/** - * Return the maximum number of ContentObjects that can be stored in this - * ContentStore. This is a raw count, not based on memory size. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * - * @return the maximum number of ContentObjects that can be stored - */ -size_t contentStoreInterface_GetObjectCapacity( - ContentStoreInterface *storeImpl); - -/** - * Return the number of ContentObjects currently stored in the ContentStore. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - * - * @return the current number of ContentObjects in the ContentStore - */ -size_t contentStoreInterface_GetObjectCount(ContentStoreInterface *storeImpl); - -/** - * Loga ContentStore implementation specific version of store-related - * information. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - */ -void contentStoreInterface_Log(ContentStoreInterface *storeImpl); - -/** - * Acquire a new reference to the specified ContentStore instance. This - * reference will eventually need to be released by calling {@link - * contentStoreInterface_Release}. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - */ -ContentStoreInterface *contentStoreInterface_Aquire( - const ContentStoreInterface *storeImpl); - -/** - * Release the ContentStore, which will also Release any references held by it. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - */ -void contentStoreInterface_Release(ContentStoreInterface **storeImplPtr); - -/** - * Return a pointer to the data private to this implementation of the - * ContentStore interface. - * - * @param storeImpl - a pointer to this ContentStoreInterface instance. - */ -void *contentStoreInterface_GetPrivateData(ContentStoreInterface *storeImpl); -#endif // contentStoreInterface_h diff --git a/hicn-light/src/hicn/content_store/contentStoreLRU.c b/hicn-light/src/hicn/content_store/contentStoreLRU.c deleted file mode 100644 index 76a2c8659..000000000 --- a/hicn-light/src/hicn/content_store/contentStoreLRU.c +++ /dev/null @@ -1,462 +0,0 @@ -/* - * 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 _WIN32 -#include <sys/queue.h> -#endif -#include <hicn/hicn-light/config.h> -#include <stdio.h> - -#include <parc/algol/parc_DisplayIndented.h> -#include <parc/algol/parc_HashCodeTable.h> -#include <parc/algol/parc_Object.h> - -#include <hicn/core/logger.h> - -#include <hicn/content_store/contentStoreLRU.h> - -#include <hicn/content_store/contentStoreEntry.h> -#include <hicn/content_store/contentStoreInterface.h> -#include <hicn/content_store/listLRU.h> -#include <hicn/content_store/listTimeOrdered.h> - -#include <parc/assert/parc_Assert.h> -#include <hicn/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; - } - - ContentStoreEntry *storeEntry = parcHashCodeTable_Get(store->storageByName, content); - if(storeEntry){ - _contentStoreLRU_PurgeStoreEntry(store, storeEntry); - } - - 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; -} diff --git a/hicn-light/src/hicn/content_store/contentStoreLRU.h b/hicn-light/src/hicn/content_store/contentStoreLRU.h deleted file mode 100644 index 94ec4d6b2..000000000 --- a/hicn-light/src/hicn/content_store/contentStoreLRU.h +++ /dev/null @@ -1,39 +0,0 @@ -/* - * 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 contentStoreLRU_h -#define contentStoreLRU_h - -#include <hicn/content_store/contentStoreInterface.h> -#include <hicn/core/logger.h> -#include <stdio.h> - -/** - * Create and Initialize an instance of contentStoreLRU. A newly allocated - * {@link ContentStoreInterface} object is initialized and returned. It must - * eventually be released by calling {@link contentStoreInterface_Release}. - * - * - * @param config An instance of `ContentStoreConfig`, specifying options to be - * applied by the underlying contentStoreLRU instance. - * @param logger An instance of a {@link Logger} to use for logging content - * store events. - * - * @return a newly created contentStoreLRU instance. - * - */ -ContentStoreInterface *contentStoreLRU_Create(ContentStoreConfig *config, - Logger *logger); -#endif // contentStoreLRU_h diff --git a/hicn-light/src/hicn/content_store/listLRU.c b/hicn-light/src/hicn/content_store/listLRU.c deleted file mode 100644 index 242af4078..000000000 --- a/hicn-light/src/hicn/content_store/listLRU.c +++ /dev/null @@ -1,135 +0,0 @@ -/* - * 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 _WIN32 -#include <sys/queue.h> -#endif -#include <hicn/hicn-light/config.h> -#include <stdbool.h> -#include <stdio.h> - -#include <parc/algol/parc_Memory.h> -#include <parc/assert/parc_Assert.h> -#include <hicn/content_store/listLRU.h> - -struct list_lru_entry { - void *userData; - - // always set to the list - ListLru *parentList; - - // indicates if the Entry is currently in the list - bool inList; - - TAILQ_ENTRY(list_lru_entry) list; -}; - -// this defines the TAILQ structure so we can access the tail pointer -TAILQ_HEAD(lru_s, list_lru_entry); - -struct list_lru { - struct lru_s head; - size_t itemsInList; -}; - -void listLRU_EntryDestroy(ListLruEntry **entryPtr) { - parcAssertNotNull(entryPtr, - "Parameter entryPtr must be non-null double pointer"); - - ListLruEntry *entry = *entryPtr; - if (entry->inList) { - TAILQ_REMOVE(&entry->parentList->head, entry, list); - parcAssertTrue( - entry->parentList->itemsInList > 0, - "Invalid state, removed entry from list, but itemsInList is 0"); - entry->parentList->itemsInList--; - } - - parcMemory_Deallocate((void **)&entry); - *entryPtr = NULL; -} - -void listLRU_EntryMoveToHead(ListLruEntry *entry) { - parcAssertNotNull(entry, "Parameter entry must be non-null"); - - TAILQ_REMOVE(&entry->parentList->head, entry, list); - TAILQ_INSERT_HEAD(&entry->parentList->head, entry, list); -} - -void *listLRU_EntryGetData(ListLruEntry *entry) { return entry->userData; } - -ListLru *listLRU_Create() { - ListLru *list = parcMemory_AllocateAndClear(sizeof(ListLru)); - parcAssertNotNull(list, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(ListLru)); - list->itemsInList = 0; - TAILQ_INIT(&list->head); - return list; -} - -void listLRU_Destroy(ListLru **lruPtr) { - parcAssertNotNull(lruPtr, "Parameter lruPtr must be non-null double pointer"); - - ListLru *lru = *lruPtr; - - ListLruEntry *entry = TAILQ_FIRST(&lru->head); - while (entry != NULL) { - ListLruEntry *next = TAILQ_NEXT(entry, list); - listLRU_EntryDestroy(&entry); - entry = next; - } - - parcMemory_Deallocate((void **)&lru); - *lruPtr = NULL; -} - -ListLruEntry *listLRU_NewHeadEntry(ListLru *lru, void *data) { - parcAssertNotNull(lru, "Parameter lru must be non-null"); - parcAssertNotNull(data, "Parameter data must be non-null"); - - ListLruEntry *entry = parcMemory_AllocateAndClear(sizeof(ListLruEntry)); - parcAssertNotNull(entry, "parcMemory_AllocateAndClear(%zu) returned NULL", - sizeof(ListLruEntry)); - entry->userData = data; - entry->parentList = lru; - entry->inList = true; - - TAILQ_INSERT_HEAD(&lru->head, entry, list); - lru->itemsInList++; - - return entry; -} - -ListLruEntry *listLRU_PopTail(ListLru *lru) { - parcAssertNotNull(lru, "Parameter lru must be non-null"); - - ListLruEntry *entry = TAILQ_LAST(&lru->head, lru_s); - - if (entry) { - parcAssertTrue( - lru->itemsInList > 0, - "Invalid state, removed entry from list, but itemsInList is 0"); - lru->itemsInList--; - TAILQ_REMOVE(&lru->head, entry, list); - entry->inList = false; - } - - return entry; -} - -size_t listLRU_Length(const ListLru *lru) { - parcAssertNotNull(lru, "Parameter lru must be non-null"); - return lru->itemsInList; -} diff --git a/hicn-light/src/hicn/content_store/listLRU.h b/hicn-light/src/hicn/content_store/listLRU.h deleted file mode 100644 index 75f698b61..000000000 --- a/hicn-light/src/hicn/content_store/listLRU.h +++ /dev/null @@ -1,94 +0,0 @@ -/* - * 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 listLRU.h - * @brief Maintains an LRU for the content store - * - * An LRU list is make up of LRU entries. The entries are bound to the list. - * The user of the list is reponsible for knowing when there's too many things - * and wants to remove one. The LRU list will grow without bound otherwise. - * - * The LRU list is meant to be used as an auxiliary data structure, not the - * primary storage of data elements. - * - */ - -#ifndef listLRU_h -#define listLRU_h - -struct list_lru_entry; -typedef struct list_lru_entry ListLruEntry; - -struct list_lru; -typedef struct list_lru ListLru; - -/** - * @function lruEntry_Destroy - * @abstract Destroys and element. This will also remove it from the list. - */ -void listLRU_EntryDestroy(ListLruEntry **entryPtr); - -/** - * @function listLRU_EntryMoveToHead - * @abstract move an element to head - */ -void listLRU_EntryMoveToHead(ListLruEntry *entry); - -/** - * @function lruEntry_GetData - * @abstract Returns the user-supplied opaque data when the entry was created - */ -void *listLRU_EntryGetData(ListLruEntry *entry); - -/** - * @function listLRU_Create - * @abstract Creates a new Least-Recently-Used list - */ -ListLru *listLRU_Create(); - -/** - * @function listLRU_Destroy - * @abstract Destroys a list and frees all the elements in it - */ -void listLRU_Destroy(ListLru **listPtr); - -/** - * Returns the number of items in the list - * - * @param [in] lru An allocated ListLru - * @retval number The number of items in the LRU list - */ -size_t listLRU_Length(const ListLru *lru); - -/** - * @function listLRU_NewHeadEntry - * @abstract Creates a new entry for the list. It is inserted at the head of - * the list. - */ -ListLruEntry *listLRU_NewHeadEntry(ListLru *lru, void *data); - -/** - * @function listLRU_PopTail - * @abstract Removes the tail element from the list and returns it to the user - * @discussion - * Pops the tail element. The user should examine its data to destroy their - * tail object, then call <code>LruEntry_Destroy()</code> to free the - * LRU entry. - * - * @return The tail element, or NULL for an empty list - */ -ListLruEntry *listLRU_PopTail(ListLru *list); -#endif // listLRU_h diff --git a/hicn-light/src/hicn/content_store/listTimeOrdered.c b/hicn-light/src/hicn/content_store/listTimeOrdered.c deleted file mode 100644 index 690c6e412..000000000 --- a/hicn-light/src/hicn/content_store/listTimeOrdered.c +++ /dev/null @@ -1,94 +0,0 @@ -/* - * 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 <parc/assert/parc_Assert.h> -#include <hicn/hicn-light/config.h> -#include <hicn/content_store/listTimeOrdered.h> - -#include <parc/algol/parc_Object.h> -#include <parc/algol/parc_TreeRedBlack.h> - -/** - * A list of ContentStoreEntrys, kept in sorted order by time. The ordering is - * calculated by a key compare function (e.g. {@link TimeOrderList_KeyCompare}), - * passed in. - * - * This container does not hold references to the objects that it contains. In - * other words, it does not Acquire() the Messages that are placed in it. That - * reference count is managed by the owning ContentStore. This is purely an - * index, and provides an easy to way index Messages based on a specified time - * value. Typically, that would be the Expiration Time. - * - * It maintains a tree, sorted by the time values passed in to the Add() - * function. It does not manage capacity, and can grow uncontrollably if the - * owning ContentStore does not manage it. Items are indexed first by time, then - * address of the Message (just as a distringuishing attribute). This allows us - * to store multiple items with the same expiration time. - */ - -struct list_timeordered { - PARCTreeRedBlack *timeOrderedTree; -}; - -static void _finalRelease(ListTimeOrdered **listP) { - ListTimeOrdered *list = *listP; - parcTreeRedBlack_Destroy(&list->timeOrderedTree); -} - -parcObject_ExtendPARCObject(ListTimeOrdered, _finalRelease, NULL, NULL, NULL, - NULL, NULL, NULL); - -parcObject_ImplementAcquire(listTimeOrdered, ListTimeOrdered); - -parcObject_ImplementRelease(listTimeOrdered, ListTimeOrdered); - -ListTimeOrdered *listTimeOrdered_Create( - TimeOrderList_KeyCompare *keyCompareFunction) { - ListTimeOrdered *result = parcObject_CreateInstance(ListTimeOrdered); - if (NULL != result) { - result->timeOrderedTree = - parcTreeRedBlack_Create(keyCompareFunction, // keyCompare - NULL, // keyFree - NULL, // keyCopy - NULL, // valueEquals - NULL, // valueFree - NULL); // valueCopy - } - return result; -} - -void listTimeOrdered_Add(ListTimeOrdered *list, ContentStoreEntry *entry) { - parcTreeRedBlack_Insert(list->timeOrderedTree, entry, entry); -} - -ContentStoreEntry *listTimeOrdered_GetOldest(ListTimeOrdered *list) { - return parcTreeRedBlack_FirstKey(list->timeOrderedTree); -} - -bool listTimeOrdered_Remove(ListTimeOrdered *list, - ContentStoreEntry *storeEntry) { - bool result = false; - - ContentStoreEntry *entry = (ContentStoreEntry *)parcTreeRedBlack_Remove( - list->timeOrderedTree, storeEntry); - if (entry != NULL) { - result = true; - } - return result; -} - -size_t listTimeOrdered_Length(ListTimeOrdered *list) { - return (size_t)parcTreeRedBlack_Size(list->timeOrderedTree); -} diff --git a/hicn-light/src/hicn/content_store/listTimeOrdered.h b/hicn-light/src/hicn/content_store/listTimeOrdered.h deleted file mode 100644 index 325e7c0d4..000000000 --- a/hicn-light/src/hicn/content_store/listTimeOrdered.h +++ /dev/null @@ -1,103 +0,0 @@ -/* - * 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 listTimeOrdered_h -#define listTimeOrdered_h - -#include <parc/algol/parc_TreeRedBlack.h> -#include <hicn/content_store/contentStoreEntry.h> -#include <hicn/core/message.h> -#include <stdio.h> - -struct list_timeordered; -typedef struct list_timeordered ListTimeOrdered; - -/** - * A signum function that takes two instances of ContentStoreEntrys and - * returns a value based on their relative values. - */ -typedef PARCTreeRedBlack_KeyCompare TimeOrderList_KeyCompare; - -/** - * Create a new instance of `ListTimeOrdered` that will maintain the order of - * its list items using the supplied `keyCompareFunction`. - * - * The newly created `ListTimeOrdered` must eventually be released by calling - * {@link listTimeOrdered_Release}. - * - * @param keyCompareFunction the signum comparison function to use to sort - * stored items. - * @return a new instance of `TimeOrderList`. - * @return NULL if the new instance couldn't be created. - * - */ -ListTimeOrdered *listTimeOrdered_Create( - TimeOrderList_KeyCompare *keyCompareFunction); - -/** - * 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. - * - */ -void listTimeOrdered_Release(ListTimeOrdered **listP); - -/** - * Add a {@link ContentStoreEntry} instance to the specified list. Note that a - * new refernece to the specified `storeEntry` is not acquired. - * - * @param list the list instance into which to add the specified storeEntry. - * @param storeEntry the storeEntry instance to add. - * - */ -void listTimeOrdered_Add(ListTimeOrdered *list, ContentStoreEntry *storeEntry); - -/** - * Remove a {@link ContentStoreEntry} instance from the specified list. - * - * @param list the list instance from which to remove the specified storeEntry. - * @param storeEntry the storeEntry instance to remove. - * @return true if the removal was succesful. - * @return false if the removal was not succesful. - * - */ -bool listTimeOrdered_Remove(ListTimeOrdered *list, - ContentStoreEntry *storeEntry); - -/** - * Return the oldest {@link ContentStoreEntry} instance in this list. That is, - * the one with the smallest time value. - * - * @param list the list instance from which to retrieve the oldest storeEntry. - * @param the oldest `ContentStoreEntry` in the list - * @param NULL if no `ContentStoreEntry` was available. - * - */ -ContentStoreEntry *listTimeOrdered_GetOldest(ListTimeOrdered *list); - -/** - * Return the number of items currently stored in the list. - * - * @param list the `ListTimeOrdered` instance from which to retrieve the count. - * @return the number of items in the list. - * - */ -size_t listTimeOrdered_Length(ListTimeOrdered *list); -#endif /* defined(listTimeOrdered_h) */ diff --git a/hicn-light/src/hicn/content_store/lru.c b/hicn-light/src/hicn/content_store/lru.c new file mode 100644 index 000000000..30f972ce9 --- /dev/null +++ b/hicn-light/src/hicn/content_store/lru.c @@ -0,0 +1,190 @@ +/* + * 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 _WIN32 +#include <sys/queue.h> +#endif + +#include <hicn/util/log.h> + +#include <hicn/hicn-light/config.h> +#include <stdio.h> + +#include <hicn/core/content_store.h> +#include "lru.h" + +// XXX TODO some part to be moved to parent + +// XXX TODO +#if 0 +static void _content_store_lru_Log(ContentStoreInterface *storeImpl) { + content_store_lru_data_t *store = + (content_store_lru_data_t *)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 +bool +_content_store_lru_remove_least_used(content_store_t * cs) +{ + if (content_store_size(cs) == 0) + return false; + +#if 0 + ListLruEntry *lruEntry = listLRU_PopTail(store->lru); + content_store_entry_t *storeEntry = + (content_store_entry_t *)listLRU_EntryGetData(lruEntry); +#else + content_store_entry_t * entry = NULL; +#endif + + DEBUG("CS %p LRU evict msgbuf %p (#evictions %" PRIu64 ")", + cs, content_store_entry_message(entry), + cs->stats.lru.countLruEvictions); + + content_store_purge_entry(cs, entry); + + return true; +} + +static +void +_evictByStorePolicy(content_store_t * cs, 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. + + content_store_entry_t *entry = + listTimeOrdered_GetOldest(store->indexByExpirationTime); + if (entry && content_store_entry_has_expiry_time(entry) && + (currentTimeInTicks > content_store_entry_get_expiry_time(entry))) { + // Found an expired entry. Remove it, and we're done. + + store->stats.countExpiryEvictions++; + DEBUG("ContentStore %p evict message %p by ExpiryTime (ExpiryTime evictions %" PRIu64 ")", + (void *)store, (void *)contentStoreEntry_GetMessage(entry), + store->stats.countExpiryEvictions); + + _content_store_lru_purge_entry(store, entry); + } else { + store->stats.countLruEvictions++; + _content_store_lru_remove_least_used(store); + } +} +#endif + +void +content_store_lru_initialize(content_store_t * cs) +{ + content_store_lru_data_t * data = cs->data; + + data->lru = NULL; + if (!data->lru) { + ERROR("Could not create LRU index"); + goto ERR_INDEX; + } + +ERR_INDEX: + return; +} + +void +content_store_lru_finalize(content_store_t * cs) +{ + content_store_lru_data_t * data = cs->data; + + if (data->lru != NULL) + ; // XXX TODO listLRU_Destroy(&(store->lru)); +} + +bool +content_store_lru_add_entry(content_store_t * cs, content_store_entry_t * entry) +{ + assert(cs); + assert(entry); + + if (content_store_size(cs) == 0) + return false; +#if 0 + content_store_lru_data_t * data = cs->data; + + content_store_entry_t *dataEntry = parcHashCodeTable_Get(data->storageByName, content); + if(dataEntry) + _content_store_lru_purge_entry(data, dataEntry); + + 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 (now >= expiryTimeTicks) + return false; + + if (data->objectCount >= data->objectCapacity) + // Store is full. Need to make room. + _evictByStorePolicy(data, now); + + // And now add a new entry to the head of the LRU. + content_store_entry_t *entry = contentStoreEntry_Create(content, data->lru); + if (!entry) + return false; + + if (!parcHashCodeTable_Add(data->storageByName, content, entry)) { + // Free what we just created, but did not add. 'entry' has ownership of + // 'copy', and so will call _Release() on it + contentStoreEntry_Release(&entry); + WARN("ContentStoreLRU %p failed to add message %p to hash table", + (void *)data, (void *)content); + return false; + } + + if (content_store_entry_has_expiry_time(entry)) + listTimeOrdered_Add(data->indexByExpirationTime, entry); + + data->objectCount++; + data->stats.countAdds++; + + DEBUG("ContentStoreLRU %p saved message %p (object count %" PRIu64 ")", + data, msgbuf, content_store_size(cs)); +#endif + return true; +} + +/** + * Remove a content_store_entry_t from all tables and indices. + */ +static +void +content_store_lru_remove_entry(content_store_t * cs, content_store_entry_t * entry) +{ + assert(cs); + assert(entry); + // + // XXX REMOVE ENTRY FROM LRU +} + + +DECLARE_CONTENT_STORE(lru); diff --git a/hicn-light/src/hicn/content_store/lru.h b/hicn-light/src/hicn/content_store/lru.h new file mode 100644 index 000000000..61341921f --- /dev/null +++ b/hicn-light/src/hicn/content_store/lru.h @@ -0,0 +1,34 @@ +/* + * 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 HICNLIGHT_CONTENT_STORE_LRU_H +#define HICNLIGHT_CONTENT_STORE_LRU_H + +typedef struct { + // This LRU is just for keeping track of insertion and access order. + //ListLru *lru; + void * lru; +} content_store_lru_data_t; + +typedef struct { + uint64_t countExpiryEvictions; + uint64_t countRCTEvictions; + uint64_t countLruEvictions; + uint64_t countAdds; + uint64_t countHits; + uint64_t countMisses; +} content_store_lru_stats_t; + +#endif /* HICNLIGHT_CONTENT_STORE_LRU_H */ |