diff options
Diffstat (limited to 'metis/ccnx/forwarder/metis/content_store')
16 files changed, 3747 insertions, 0 deletions
diff --git a/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.c b/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.c new file mode 100644 index 00000000..95fee23e --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.c @@ -0,0 +1,192 @@ +/* + * 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 <parc/algol/parc_Memory.h> +#include <ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.h> + +#include <LongBow/runtime.h> + +const uint64_t metisContentStoreEntry_MaxExpiryTime = UINT64_MAX; +const uint64_t metisContentStoreEntry_MaxRecommendedCacheTime = UINT64_MAX; + +struct metis_contentstore_entry { + MetisMessage *message; + MetisLruListEntry *lruEntry; + unsigned refcount; + + bool hasRecommendedCacheTimeTicks; + uint64_t recommendedCacheTimeTicks; + + bool hasExpiryTimeTicks; + uint64_t expiryTimeTicks; +}; + +MetisContentStoreEntry * +metisContentStoreEntry_Create(MetisMessage *contentMessage, MetisLruList *lruList) +{ + assertNotNull(contentMessage, "Parameter objectMessage must be non-null"); + + MetisContentStoreEntry *entry = parcMemory_AllocateAndClear(sizeof(MetisContentStoreEntry)); + assertNotNull(entry, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(MetisContentStoreEntry)); + entry->message = metisMessage_Acquire(contentMessage); + entry->refcount = 1; + if (lruList != NULL) { + entry->lruEntry = metisLruList_NewHeadEntry(lruList, entry); + } + + entry->hasExpiryTimeTicks = metisMessage_HasExpiryTime(contentMessage); + entry->hasRecommendedCacheTimeTicks = metisMessage_HasRecommendedCacheTime(contentMessage); + + if (entry->hasExpiryTimeTicks) { + entry->expiryTimeTicks = metisMessage_GetExpiryTimeTicks(contentMessage); + } + + if (entry->hasRecommendedCacheTimeTicks) { + entry->recommendedCacheTimeTicks = metisMessage_GetRecommendedCacheTimeTicks(contentMessage); + } + + return entry; +} + +MetisContentStoreEntry * +metisContentStoreEntry_Acquire(const MetisContentStoreEntry *original) +{ + assertNotNull(original, "Parameter must be non-null"); + ((MetisContentStoreEntry *) original)->refcount++; // cast to break the const. + return (MetisContentStoreEntry *) original; +} + +void +metisContentStoreEntry_Release(MetisContentStoreEntry **entryPtr) +{ + assertNotNull(entryPtr, "Parameter must be non-null double pointer"); + assertNotNull(*entryPtr, "Parameter must dereference to non-null pointer"); + + MetisContentStoreEntry *entry = *entryPtr; + assertTrue(entry->refcount > 0, "Illegal state: has refcount of 0"); + + entry->refcount--; + if (entry->refcount == 0) { + if (entry->lruEntry) { + metisLruList_EntryDestroy(&entry->lruEntry); + } + metisMessage_Release(&entry->message); + parcMemory_Deallocate((void **) &entry); + } + *entryPtr = NULL; +} + +MetisMessage * +metisContentStoreEntry_GetMessage(const MetisContentStoreEntry *storeEntry) +{ + assertNotNull(storeEntry, "Parameter must be non-null"); + return storeEntry->message; +} + +bool +metisContentStoreEntry_HasExpiryTimeTicks(const MetisContentStoreEntry *storeEntry) +{ + assertNotNull(storeEntry, "Parameter must be non-null"); + return storeEntry->hasExpiryTimeTicks; +} + +uint64_t +metisContentStoreEntry_GetExpiryTimeTicks(const MetisContentStoreEntry *storeEntry) +{ + assertNotNull(storeEntry, "Parameter must be non-null"); + assertTrue(storeEntry->hasExpiryTimeTicks, + "storeEntry has no ExpiryTimeTicks. Did you call metisContentStoreEntry_HasExpiryTimeTicks() first?"); + return storeEntry->expiryTimeTicks; +} + +bool +metisContentStoreEntry_HasRecommendedCacheTimeTicks(const MetisContentStoreEntry *storeEntry) +{ + assertNotNull(storeEntry, "Parameter must be non-null"); + return storeEntry->hasRecommendedCacheTimeTicks; +} + +uint64_t +metisContentStoreEntry_GetRecommendedCacheTimeTicks(const MetisContentStoreEntry *storeEntry) +{ + assertNotNull(storeEntry, "Parameter must be non-null"); + assertTrue(storeEntry->hasRecommendedCacheTimeTicks, + "storeEntry has no RecommendedCacheTimeTicks. Did you call metisContentStoreEntry_HasRecommendedCacheTimeTicks() first?"); + return storeEntry->recommendedCacheTimeTicks; +} + +int +metisContentStoreEntry_CompareRecommendedCacheTime(const MetisContentStoreEntry *value1, const MetisContentStoreEntry *value2) +{ + // A signum comparison. negative if key 1 is smaller, 0 if key1 == key2, greater than 0 if key1 is bigger. + + MetisContentStoreEntry *v1 = (MetisContentStoreEntry *) value1; + MetisContentStoreEntry *v2 = (MetisContentStoreEntry *) value2; + + if (v1->recommendedCacheTimeTicks < v2->recommendedCacheTimeTicks) { + return -1; + } else if (v1->recommendedCacheTimeTicks > v2->recommendedCacheTimeTicks) { + return +1; + } else { + // At this point, the times are the same. Use the address of the MetisMessage as the decider. + // This allows us to store multiple MetisMessages 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 MetisMessage has been encountered. +} + +int +metisContentStoreEntry_CompareExpiryTime(const MetisContentStoreEntry *value1, const MetisContentStoreEntry *value2) +{ + // A signum comparison. negative if key 1 is smaller, 0 if key1 == key2, greater than 0 if key1 is bigger. + + MetisContentStoreEntry *v1 = (MetisContentStoreEntry *) value1; + MetisContentStoreEntry *v2 = (MetisContentStoreEntry *) 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 MetisMessage as the decider. + // This allows us to store multiple MetisMessages 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 MetisMessage has been encountered. +} + +void +metisContentStoreEntry_MoveToHead(MetisContentStoreEntry *storeEntry) +{ + assertNotNull(storeEntry, "Parameter must be non-null"); + assertNotNull(storeEntry->lruEntry, "MetisContentStoreEntry is not attached to an LRUList"); + if (storeEntry->lruEntry) { + metisLruList_EntryMoveToHead(storeEntry->lruEntry); + } +} diff --git a/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.h b/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.h new file mode 100644 index 00000000..bf8cd9f8 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.h @@ -0,0 +1,213 @@ +/* + * 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. + */ + + +#ifndef Metis_metis_ContentStoreEntry_h +#define Metis_metis_ContentStoreEntry_h + +#include <ccnx/forwarder/metis/core/metis_Message.h> +#include <ccnx/forwarder/metis/content_store/metis_LruList.h> + +struct metis_contentstore_entry; +typedef struct metis_contentstore_entry MetisContentStoreEntry; + +/** + * The max time allowed for an ExpiryTime. Will never be exceeded. + */ +extern const uint64_t metisContentStoreEntry_MaxExpiryTime; + +/** + * The max time allowed for an RecommendedCacheTime. Will never be exceeded. + */ +extern const uint64_t metisContentStoreEntry_MaxRecommendedCacheTime; + + +/** + * Creates a new `MetisContentStoreEntry` instance, acquiring a reference to the supplied `MetisMessage`. + * + * @param message the message to store + * @param lruList the LRU list that this entry will be stored in. + * @return A newly created `MetisContentStoreEntry` instance that must eventually be released by calling + * {@link metisContentStoreEntry_Release}. + * + * @see metisContentStoreEntry_Release + */ +MetisContentStoreEntry *metisContentStoreEntry_Create(MetisMessage *objectMessage, MetisLruList *lruList); + +/** + * Returns a reference counted copy of the supplied `MetisContentStoreEntry`. + * + * @param original the MetisContentStoreEntry to return a reference to. + * @return Reference counted copy, must call <code>metisContentStoreEntry_Destroy()</code> on it. + */ +MetisContentStoreEntry *metisContentStoreEntry_Acquire(const MetisContentStoreEntry *original); + +/** + * Releases one reference count and destroys object when reaches zero + * + * <#Paragraphs Of Explanation#> + * + * @param [in,out] entryPtr A pointer to an allocated MetisContentStoreEntry + * + * Example: + * @code + * <#example#> + * @endcode + */ +void metisContentStoreEntry_Release(MetisContentStoreEntry **entryPtr); + +/** + * Returns a pointer to the contained {@link MetisMessage}. + * The caller must called {@link metisMessage_Acquire()} if they want to keep a reference to the returned + * message. + * + * @param storeEntry the MetisContentStoreEntry from which to retrieve the `MetisMessage` pointer. + * @return the address of the `MetisMessage` contained in the storeEntry. + * @see metisMessage_Acquire + */ +MetisMessage *metisContentStoreEntry_GetMessage(const MetisContentStoreEntry *storeEntry); + +/** + * Return true if the message stored in this `MetisContentStoreEntry` has an ExpiryTime. + * + * @param storeEntry the MetisContentStoreEntry containing the message. + * @return true if the referenced message has an ExpiryTime. False, otherwise. + */ +bool metisContentStoreEntry_HasExpiryTimeTicks(const MetisContentStoreEntry *storeEntry); + +/** + * Return the ExpiryTime stored in this `MetisContentStoreEntry`. + * + * @param storeEntry the MetisContentStoreEntry from which to retrieve the `MetisMessage` pointer. + * @return the address of the `MetisMessage` contained in the storeEntry. + */ +uint64_t metisContentStoreEntry_GetExpiryTimeTicks(const MetisContentStoreEntry *storeEntry); + +/** + * Return true if the message stored in this `MetisContentStoreEntry` has a RecommendedCacheTime. + * + * @param storeEntry the MetisContentStoreEntry containing the message. + * @return true if the referenced message has a RecommendedCacheTime. False, otherwise. + */ +bool metisContentStoreEntry_HasRecommendedCacheTimeTicks(const MetisContentStoreEntry *storeEntry); + +/** + * Return the RecommendedCacheTime stored in this `MetisContentStoreEntry`. + * + * @param storeEntry the MetisContentStoreEntry from which to retrieve the `MetisMessage` pointer. + * @return the address of the `MetisMessage` contained in the storeEntry. + */ +uint64_t metisContentStoreEntry_GetRecommendedCacheTimeTicks(const MetisContentStoreEntry *storeEntry); + +/** + * A signum function comparing two `MetisContentStoreEntry` instances, using their + * RecommendedCacheTime and, if necessary, the addresses of the referenced MetisMessage. In other words, if + * two ContentStoreEntries have the same RecommendedCacheTime, the comparison will then be made on the + * memory addresses of the MetisMessages referenced by the MetisContentStoreEntrys. So, the only way two + * MetisContentStoreEntrys will compare equally (0) is if they both have the same RecommendedCacheTime and reference + * the same MetisMessage. + * + * Used to determine the ordering relationship of two `MetisContentStoreEntry` instances. + * This is used by the {@link MetisTimeOrderedList} to keep a list of MetisContentStoreEntrys, sorted by + * RecommendedCacheTime. + * + * @param [in] storeEntry1 A pointer to a `MetisContentStoreEntry` instance. + * @param [in] storeEntry2 A pointer to a `MetisContentStoreEntry` 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 + * { + * MetisContentStoreEntry *entry1 = metisContentStoreEntry_Create(...); + * MetisContentStoreEntry *entry2 = metisContentStoreEntry_Create(...); + * + * int val = metisContentStoreEntry_CompareRecommendedCacheTime(entry1, entry2); + * if (val < 0) { + * // entry1 has a lower RecommendedCacheTime, or the same RecommendedCacheTime as entry2 and a different message. + * } else if (val > 0) { + * // entry2 has a lower RecommendedCacheTime, or the same RecommendedCacheTime as entry1 and a different message. + * } else { + * // entry1 and entry2 have the same RecommendedCacheTime AND the same message. + * } + * + * metisContentStoreEntry_Release(&entry1); + * metisContentStoreEntry_Release(&entry2); + * + * } + * @endcode + * @see `metisContentStoreEntry_CompareExpiryTime` + */ +int metisContentStoreEntry_CompareRecommendedCacheTime(const MetisContentStoreEntry *storeEntry1, const MetisContentStoreEntry *storeEntry2); + +/** + * A signum function comparing two `MetisContentStoreEntry` instances, using their + * ExpiryTime and, if necessary, the addresses of the referenced MetisMessage. In other words, if + * two ContentStoreEntries have the same ExpiryTime, the comparison will then be made on the + * memory addresses of the MetisMessages referenced by the MetisContentStoreEntrys. So, the only way two + * MetisContentStoreEntrys will compare equally (0) is if they both have the same ExpiryTime and reference + * the same MetisMessage. + * + * Used to determine the ordering relationship of two `MetisContentStoreEntry` instances. + * This is used by the {@link MetisTimeOrderedList} to keep a list of MetisContentStoreEntrys, sorted by + * ExpiryTime. + * + * @param [in] storeEntry1 A pointer to a `MetisContentStoreEntry` instance. + * @param [in] storeEntry2 A pointer to a `MetisContentStoreEntry` 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 + * { + * MetisContentStoreEntry *entry1 = metisContentStoreEntry_Create(...); + * MetisContentStoreEntry *entry2 = metisContentStoreEntry_Create(...); + * + * int val = metisContentStoreEntry_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. + * } + * + * metisContentStoreEntry_Release(&entry1); + * metisContentStoreEntry_Release(&entry2); + * + * } + * @endcode + * @see `metisContentStoreEntry_CompareRecommendedCacheTime` + */ +int metisContentStoreEntry_CompareExpiryTime(const MetisContentStoreEntry *storeEntry1, const MetisContentStoreEntry *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 MetisContenstoreEntry + * + * Example: + * @code + * <#example#> + * @endcode + */ +void metisContentStoreEntry_MoveToHead(MetisContentStoreEntry *storeEntry); +#endif // Metis_metis_ContentStoreEntry_h diff --git a/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.c b/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.c new file mode 100644 index 00000000..d846487f --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.c @@ -0,0 +1,68 @@ +/* + * 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 <ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.h> + +void +metisContentStoreInterface_Release(MetisContentStoreInterface **storeImplPtr) +{ + (*storeImplPtr)->release(storeImplPtr); +} + +bool +metisContentStoreInterface_PutContent(MetisContentStoreInterface *storeImpl, MetisMessage *content, uint64_t currentTimeTicks) +{ + return storeImpl->putContent(storeImpl, content, currentTimeTicks); +} + +bool +metisContentStoreInterface_RemoveContent(MetisContentStoreInterface *storeImpl, MetisMessage *content) +{ + return storeImpl->removeContent(storeImpl, content); +} + +MetisMessage * +metisContentStoreInterface_MatchInterest(MetisContentStoreInterface *storeImpl, MetisMessage *interest) +{ + return storeImpl->matchInterest(storeImpl, interest); +} + +size_t +metisContentStoreInterface_GetObjectCapacity(MetisContentStoreInterface *storeImpl) +{ + return storeImpl->getObjectCapacity(storeImpl); +} + +size_t +metisContentStoreInterface_GetObjectCount(MetisContentStoreInterface *storeImpl) +{ + return storeImpl->getObjectCount(storeImpl); +} + +void +metisContentStoreInterface_Log(MetisContentStoreInterface *storeImpl) +{ + storeImpl->log(storeImpl); +} + +void * +metisContentStoreInterface_GetPrivateData(MetisContentStoreInterface *storeImpl) +{ + return storeImpl->_privateData; +} diff --git a/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.h b/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.h new file mode 100644 index 00000000..fde8cf66 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.h @@ -0,0 +1,197 @@ +/* + * 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. + */ + + +#ifndef Metis_metis_ContentStoreInterface_h +#define Metis_metis_ContentStoreInterface_h + +#include <stdio.h> + +#include <ccnx/forwarder/metis/core/metis_Message.h> + +typedef struct metis_contentstore_config { + size_t objectCapacity; +} MetisContentStoreConfig; + +typedef struct metis_contentstore_interface MetisContentStoreInterface; + +struct metis_contentstore_interface { + /** + * Place a MetisMessage 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 MetisContentStoreInterface instance. + * @param content - a pointer to a `MetisMessage` to place in the store. + * @param currentTimeTicks - the current time, in metis ticks, since the UTC epoch. + */ + bool (*putContent)(MetisContentStoreInterface *storeImpl, MetisMessage *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 MetisContentStoreInterface instance. + * @param content - a pointer to a `MetisMessage` to remove from the store. + */ + bool (*removeContent)(MetisContentStoreInterface *storeImpl, MetisMessage *content); + + /** + * Given a MetisMessage that represents and Interest, try to find a matching ContentObject. Matching is + * done on a most-restrictive basis. + * + * a) If the interest has a ContentObjectHash restriction, it will match on the Name and the Object Hash. + * b) If it has a KeyId, it will match on the Name and the KeyId + * c) otherwise, it matches by Name + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + * @param interest - a pointer to a `MetisMessage` representing the Interest to match. + * + * @return a pointer to a MetisMessage containing the matching ContentObject + * @return NULL if no matching ContentObject was found + */ + MetisMessage * (*matchInterest)(MetisContentStoreInterface*storeImpl, MetisMessage *interest); + + /** + * 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 MetisContentStoreInterface instance. + * + * @return the maximum number of ContentObjects that can be stored + */ + size_t (*getObjectCapacity)(MetisContentStoreInterface *storeImpl); + + /** + * Return the number of ContentObjects currently stored in the ContentStore. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + * + * @return the current number of ContentObjects in the ContentStore + */ + size_t (*getObjectCount)(MetisContentStoreInterface *storeImpl); + + /** + * Loga ContentStore implementation specific version of store-related information. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + */ + void (*log)(MetisContentStoreInterface *storeImpl); + + /** + * Acquire a new reference to the specified ContentStore instance. This reference will eventually need + * to be released by calling {@link metisContentStoreInterface_Release}. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + */ + MetisContentStoreInterface *(*acquire)(const MetisContentStoreInterface *storeImpl); + + /** + * Release the ContentStore, which will also Release any references held by it. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + */ + void (*release)(MetisContentStoreInterface **storeImpl); + + /** + * A pointer to opaque private data used by the ContentStore instance represented by this instance of + * MetisContentStoreInterface. + */ + void *_privateData; +}; + +/** + * Place a MetisMessage 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 MetisContentStoreInterface instance. + * @param content - a pointer to a `MetisMessage` to place in the store. + * + * @param currentTimeTicks - the current time, in metis ticks, since the UTC epoch. + */ +bool metisContentStoreInterface_PutContent(MetisContentStoreInterface *storeImpl, MetisMessage *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 MetisContentStoreInterface instance. + * @param content - a pointer to a `MetisMessage` to remove from the store. + */ +bool metisContentStoreInterface_RemoveContent(MetisContentStoreInterface *storeImpl, MetisMessage *content); + +/** + * Given a MetisMessage that represents and Interest, try to find a matching ContentObject. Matching is + * done on a most-restrictive basis. + * + * a) If the interest has a ContentObjectHash restriction, it will match on the Name and the Object Hash. + * b) If it has a KeyId, it will match on the Name and the KeyId + * c) otherwise, it matches by Name + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + * @param interest - a pointer to a `MetisMessage` representing the Interest to match. + * + * @return a pointer to a MetisMessage containing the matching ContentObject + * @return NULL if no matching ContentObject was found + */ +MetisMessage *metisContentStoreInterface_MatchInterest(MetisContentStoreInterface*storeImpl, MetisMessage *interest); + +/** + * 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 MetisContentStoreInterface instance. + * + * @return the maximum number of ContentObjects that can be stored + */ +size_t metisContentStoreInterface_GetObjectCapacity(MetisContentStoreInterface *storeImpl); + +/** + * Return the number of ContentObjects currently stored in the ContentStore. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + * + * @return the current number of ContentObjects in the ContentStore + */ +size_t metisContentStoreInterface_GetObjectCount(MetisContentStoreInterface *storeImpl); + +/** + * Loga ContentStore implementation specific version of store-related information. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + */ +void metisContentStoreInterface_Log(MetisContentStoreInterface *storeImpl); + +/** + * Acquire a new reference to the specified ContentStore instance. This reference will eventually need + * to be released by calling {@link metisContentStoreInterface_Release}. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + */ +MetisContentStoreInterface *metisContentStoreInterface_Aquire(const MetisContentStoreInterface *storeImpl); + +/** + * Release the ContentStore, which will also Release any references held by it. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + */ +void metisContentStoreInterface_Release(MetisContentStoreInterface **storeImplPtr); + +/** + * Return a pointer to the data private to this implementation of the ContentStore interface. + * + * @param storeImpl - a pointer to this MetisContentStoreInterface instance. + */ +void *metisContentStoreInterface_GetPrivateData(MetisContentStoreInterface *storeImpl); +#endif // Metis_metis_ContentStoreInterface_h 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; +} + diff --git a/metis/ccnx/forwarder/metis/content_store/metis_LRUContentStore.h b/metis/ccnx/forwarder/metis/content_store/metis_LRUContentStore.h new file mode 100644 index 00000000..36738352 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_LRUContentStore.h @@ -0,0 +1,53 @@ +/* + * 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. + */ + + +#ifndef Metis_metis_LRUContentStore_h +#define Metis_metis_LRUContentStore_h + +#include <stdio.h> +#include <ccnx/forwarder/metis/content_store/metis_ContentStoreInterface.h> +#include <ccnx/forwarder/metis/core/metis_Logger.h> + +/** + * Create and Initialize an instance of MetisLRUContentStore. A newly allocated {@link MetisContentStoreInterface} + * object is initialized and returned. It must eventually be released by calling {@link metisContentStoreInterface_Release}. + * + * + * @param config An instance of `MetisContentStoreConfig`, specifying options to be applied + * by the underlying MetisLRUContentStore instance. + * @param logger An instance of a {@link MetisLogger} to use for logging content store events. + * + * @return a newly created MetisLRUContentStore instance. + * + * Example: + * @code + * { + * MetisContentStoreConfig config = { + * .objectCapacity = 10 + * }; + * + * MetisContentStoreInterface *store = metisLRUContentStore_Create(&config, logger); + * assertTrue(status, "Expected to init a content store"); + * + * store->Display(&store); + * metisContentStoreInterface_Release(&store); + * } + * @endcode + * @see MetisContentStoreInterface + * @see metisContentStoreInterface_Release + */ +MetisContentStoreInterface *metisLRUContentStore_Create(MetisContentStoreConfig *config, MetisLogger *logger); +#endif // Metis_metis_LRUContentStore_h diff --git a/metis/ccnx/forwarder/metis/content_store/metis_LruList.c b/metis/ccnx/forwarder/metis/content_store/metis_LruList.c new file mode 100644 index 00000000..6cbd72eb --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_LruList.c @@ -0,0 +1,144 @@ +/* + * 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 <ccnx/forwarder/metis/content_store/metis_LruList.h> +#include <parc/algol/parc_Memory.h> +#include <LongBow/runtime.h> + +struct metis_lru_list_entry { + void *userData; + + // always set to the list + MetisLruList *parentList; + + // indicates if the Entry is currently in the list + bool inList; + + TAILQ_ENTRY(metis_lru_list_entry) list; +}; + +// this defines the TAILQ structure so we can access the tail pointer +TAILQ_HEAD(metis_lru_s, metis_lru_list_entry); + +struct metis_lru_list { + struct metis_lru_s head; + size_t itemsInList; +}; + +void +metisLruList_EntryDestroy(MetisLruListEntry **entryPtr) +{ + assertNotNull(entryPtr, "Parameter entryPtr must be non-null double pointer"); + + MetisLruListEntry *entry = *entryPtr; + if (entry->inList) { + TAILQ_REMOVE(&entry->parentList->head, entry, list); + assertTrue(entry->parentList->itemsInList > 0, "Invalid state, removed entry from list, but itemsInList is 0"); + entry->parentList->itemsInList--; + } + + parcMemory_Deallocate((void **) &entry); + *entryPtr = NULL; +} + +void +metisLruList_EntryMoveToHead(MetisLruListEntry *entry) +{ + assertNotNull(entry, "Parameter entry must be non-null"); + + TAILQ_REMOVE(&entry->parentList->head, entry, list); + TAILQ_INSERT_HEAD(&entry->parentList->head, entry, list); +} + +void * +metisLruList_EntryGetData(MetisLruListEntry *entry) +{ + return entry->userData; +} + +MetisLruList * +metisLruList_Create() +{ + MetisLruList *list = parcMemory_AllocateAndClear(sizeof(MetisLruList)); + assertNotNull(list, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(MetisLruList)); + list->itemsInList = 0; + TAILQ_INIT(&list->head); + return list; +} + +void +metisLruList_Destroy(MetisLruList **lruPtr) +{ + assertNotNull(lruPtr, "Parameter lruPtr must be non-null double pointer"); + + MetisLruList *lru = *lruPtr; + + MetisLruListEntry *entry = TAILQ_FIRST(&lru->head); + while (entry != NULL) { + MetisLruListEntry *next = TAILQ_NEXT(entry, list); + metisLruList_EntryDestroy(&entry); + entry = next; + } + + parcMemory_Deallocate((void **) &lru); + *lruPtr = NULL; +} + +MetisLruListEntry * +metisLruList_NewHeadEntry(MetisLruList *lru, void *data) +{ + assertNotNull(lru, "Parameter lru must be non-null"); + assertNotNull(data, "Parameter data must be non-null"); + + MetisLruListEntry *entry = parcMemory_AllocateAndClear(sizeof(MetisLruListEntry)); + assertNotNull(entry, "parcMemory_AllocateAndClear(%zu) returned NULL", sizeof(MetisLruListEntry)); + entry->userData = data; + entry->parentList = lru; + entry->inList = true; + + TAILQ_INSERT_HEAD(&lru->head, entry, list); + lru->itemsInList++; + + return entry; +} + +MetisLruListEntry * +metisLruList_PopTail(MetisLruList *lru) +{ + assertNotNull(lru, "Parameter lru must be non-null"); + + MetisLruListEntry *entry = TAILQ_LAST(&lru->head, metis_lru_s); + + if (entry) { + assertTrue(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 +metisLruList_Length(const MetisLruList *lru) +{ + assertNotNull(lru, "Parameter lru must be non-null"); + return lru->itemsInList; +} diff --git a/metis/ccnx/forwarder/metis/content_store/metis_LruList.h b/metis/ccnx/forwarder/metis/content_store/metis_LruList.h new file mode 100644 index 00000000..906f8c50 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_LruList.h @@ -0,0 +1,180 @@ +/* + * 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. + */ + +/** + * @file metis_LruList.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. + * + * Example Usage: + * + * <code> + * myClass_Create() { + * ... + * me->lru = metisLruList_Create(); + * ... + * } + * + * myClass_AddAnItem(MyClass *me, ...) { + * size_t length = metisLruList_Length(me->lru); + * if( lenth == me->limit ) + * myClass_Overflow(me); + * + * item_Create(me, ...); + * } + * + * myClass_Overflow(MyClass *me) { + * MetisLruEntry *entry = metisLruList_PopTail(me->lru); + * + * // entry could be NULL, if the list is empty, but you probalby wouldnt have overflow then... + * Item *item = (Item *) metisLruEntry_GetData(entry); + * item_Destroy(&item); + * } + * + * myClass_Destroy(MyClass *me) { + * // this does not destroy the void * data in the entries, just the entries. + * metisLruList_Destroy(&me->lru); + * // destroy all the items from some other knowledge + * } + * + * item_Create(MyClass *me, ...) { + * item = malloc(sizeof(Item)); + * MetisLruEntry *entry = metisLruList_NewHeadEntry(me->lru, item); + * item->lruEntry = entry; + * ... + * } + * + * item_Use(Item *item) { + * metisLruEntry_MoveToHead(item->lruEntry); + * ... + * } + * + * item_Destroy(Item *item) { + * // removes the entry from the list, if its in a list + * metisLruEntry_Destroy(&item->lruEntry); + * free(item); + * } + * + */ + +#ifndef Metis_metis_LruList_h +#define Metis_metis_LruList_h + +struct metis_lru_list_entry; +typedef struct metis_lru_list_entry MetisLruListEntry; + +struct metis_lru_list; +typedef struct metis_lru_list MetisLruList; + +/** + * @function metisLruEntry_Destroy + * @abstract Destroys and element. This will also remove it from the list. + * @discussion + * <#Discussion#> + * + * @param <#param1#> + * @return <#return#> + */ +void metisLruList_EntryDestroy(MetisLruListEntry **entryPtr); + +/** + * @function <#FunctionName#> + * @abstract <#OneLineDescription#> + * @discussion + * <#Discussion#> + * + * @param <#param1#> + * @return <#return#> + */ +void metisLruList_EntryMoveToHead(MetisLruListEntry *entry); + +/** + * @function metisLruEntry_GetData + * @abstract Returns the user-supplied opaque data when the entry was created + * @discussion + * <#Discussion#> + * + * @param <#param1#> + * @return <#return#> + */ +void *metisLruList_EntryGetData(MetisLruListEntry *entry); + +/** + * @function metisLruList_Create + * @abstract Creates a new Least-Recently-Used list + * @discussion + * <#Discussion#> + * + * @param <#param1#> + * @return <#return#> + */ +MetisLruList *metisLruList_Create(); + +/** + * @function metisLruList_Destroy + * @abstract Destroys a list and frees all the elements in it + * @discussion + * <#Discussion#> + * + * @param <#param1#> + */ +void metisLruList_Destroy(MetisLruList **listPtr); + +/** + * Returns the number of items in the list + * + * <#Paragraphs Of Explanation#> + * + * @param [in] lru An allocated MetisLruList + * + * @retval number The number of items in the LRU list + * + * Example: + * @code + * <#example#> + * @endcode + */ +size_t metisLruList_Length(const MetisLruList *lru); + +/** + * @function metisLruList_NewHeadEntry + * @abstract Creates a new entry for the list. It is inserted at the head of the list. + * @discussion + * <#Discussion#> + * + * @param <#param1#> + * @return <#return#> + */ +MetisLruListEntry *metisLruList_NewHeadEntry(MetisLruList *lru, void *data); + +/** + * @function metisLruList_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>MetisLruEntry_Destroy()</code> to free the + * LRU entry. + * + * @param <#param1#> + * @return The tail element, or NULL for an empty list + */ +MetisLruListEntry *metisLruList_PopTail(MetisLruList *list); +#endif // Metis_metis_LruList_h diff --git a/metis/ccnx/forwarder/metis/content_store/metis_TimeOrderedList.c b/metis/ccnx/forwarder/metis/content_store/metis_TimeOrderedList.c new file mode 100644 index 00000000..55054c59 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_TimeOrderedList.c @@ -0,0 +1,103 @@ +/* + * 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 <LongBow/runtime.h> + +#include <ccnx/forwarder/metis/content_store/metis_TimeOrderedList.h> + +#include <parc/algol/parc_Object.h> +#include <parc/algol/parc_TreeRedBlack.h> + +/** + * A list of MetisContentStoreEntrys, kept in sorted order by time. The ordering is calculated by a + * key compare function (e.g. {@link MetisTimeOrderList_KeyCompare}), passed in. + * + * This container does not hold references to the objects that it contains. In other words, it does not Acquire() + * the MetisMessages 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 MetisMessages based on a specified time value. Typically, + * that would be their Recommended Cache Time, or 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 MetisMessage (just as a distringuishing attribute). This allows us to store multiple items with + * the same expiration time. + */ + +struct metis_timeordered_list { + PARCTreeRedBlack *timeOrderedTree; +}; + +static void +_finalRelease(MetisTimeOrderedList **listP) +{ + MetisTimeOrderedList *list = *listP; + parcTreeRedBlack_Destroy(&list->timeOrderedTree); +} + +parcObject_ExtendPARCObject(MetisTimeOrderedList, _finalRelease, NULL, NULL, NULL, NULL, NULL, NULL); + +parcObject_ImplementAcquire(metisTimeOrderedList, MetisTimeOrderedList); + +parcObject_ImplementRelease(metisTimeOrderedList, MetisTimeOrderedList); + + +MetisTimeOrderedList * +metisTimeOrderedList_Create(MetisTimeOrderList_KeyCompare *keyCompareFunction) +{ + MetisTimeOrderedList *result = parcObject_CreateInstance(MetisTimeOrderedList); + if (NULL != result) { + result->timeOrderedTree = parcTreeRedBlack_Create(keyCompareFunction, // keyCompare + NULL, // keyFree + NULL, // keyCopy + NULL, // valueEquals + NULL, // valueFree + NULL); // valueCopy + } + return result; +} + +void +metisTimeOrderedList_Add(MetisTimeOrderedList *list, MetisContentStoreEntry *entry) +{ + parcTreeRedBlack_Insert(list->timeOrderedTree, entry, entry); +} + +MetisContentStoreEntry * +metisTimeOrderedList_GetOldest(MetisTimeOrderedList *list) +{ + return parcTreeRedBlack_FirstKey(list->timeOrderedTree); +} + +bool +metisTimeOrderedList_Remove(MetisTimeOrderedList *list, MetisContentStoreEntry *storeEntry) +{ + bool result = false; + + MetisContentStoreEntry *entry = (MetisContentStoreEntry *) parcTreeRedBlack_Remove(list->timeOrderedTree, storeEntry); + if (entry != NULL) { + result = true; + } + return result; +} + +size_t +metisTimeOrderedList_Length(MetisTimeOrderedList *list) +{ + return (size_t) parcTreeRedBlack_Size(list->timeOrderedTree); +} + + diff --git a/metis/ccnx/forwarder/metis/content_store/metis_TimeOrderedList.h b/metis/ccnx/forwarder/metis/content_store/metis_TimeOrderedList.h new file mode 100644 index 00000000..2f854e12 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/metis_TimeOrderedList.h @@ -0,0 +1,223 @@ +/* + * 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. + */ + +#ifndef __Metis__metis_TimeOrderedList__ +#define __Metis__metis_TimeOrderedList__ + +#include <stdio.h> +#include <ccnx/forwarder/metis/core/metis_Message.h> +#include <ccnx/forwarder/metis/content_store/metis_ContentStoreEntry.h> +#include <parc/algol/parc_TreeRedBlack.h> + +struct metis_timeordered_list; +typedef struct metis_timeordered_list MetisTimeOrderedList; + +/** + * A signum function that takes two instances of MetisContentStoreEntrys and + * returns a value based on their relative values. + */ +typedef PARCTreeRedBlack_KeyCompare MetisTimeOrderList_KeyCompare; + +/** + * Create a new instance of `MetisTimeOrderedList` that will maintain the order of its + * list items using the supplied `keyCompareFunction`. + * + * The newly created `MetisTimeOrderedList` must eventually be released by calling + * {@link metisTimeOrderedList_Release}. + * + * @param keyCompareFunction the signum comparison function to use to sort stored items. + * @return a new instance of `MetisTimeOrderList`. + * @return NULL if the new instance couldn't be created. + * + * Example: + * @code + * { + * MetisTimeOrderedList *list = + * metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + * + * ... + * + * metisTimeOrderedList_Release(&list); + * } + * @endcode + * + * @see metisTimeOrderedList_Release + * @see metisContentStoreEntry_CompareExpiryTime + * @see metisContentStoreEntry_CompareRecommendedCacheTime + */ +MetisTimeOrderedList *metisTimeOrderedList_Create(MetisTimeOrderList_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. + * + * @param [in,out] listP A pointer to a pointer to the instance to release. + * Example: + * @code + * { + * MetisTimeOrderedList *list = + * metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + * + * ... + * + * metisTimeOrderedList_Release(&list); + * } + * @endcode + */ +void metisTimeOrderedList_Release(MetisTimeOrderedList **listP); + +/** + * Add a {@link MetisContentStoreEntry} 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. + * + * Example: + * @code + * { + * MetisLogger *logger = metisLogger_Create(...); + * MetisTimeOrderedList *list = + * metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + * MetisLruList *lruList = metisLruList_Create(); + * MetisMessage *message = metisMessage_CreateFromArray((uint8_t *) "\x00" "ehlo", 5, 111, 2, logger); + * + * MetisContentStoreEntry *entry = metisContentStoreEntry_Create(message, lruList, 2l, 1l); + * + * metisTimeOrderedList_Add(list, entry); + * + * metisTimeOrderedList_Release(&list); + * + * metisContentStoreEntry_Release(&entry); + * metisMessage_Release(&message); + * metisLruList_Destroy(&lruList); + * metisLogger_Release(&logger); + * } + * @endcode + * @see metisTimeOrderedList_Remove + */ +void metisTimeOrderedList_Add(MetisTimeOrderedList *list, MetisContentStoreEntry *storeEntry); + +/** + * Remove a {@link MetisContentStoreEntry} 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. + * + * Example: + * @code + * { + * MetisLogger *logger = metisLogger_Create(...); + * MetisTimeOrderedList *list = + * metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + * MetisMessage *message = metisMessage_CreateFromArray((uint8_t *) "\x00" "ehlo", 5, 111, 2, logger); + * + * MetisContentStoreEntry *entry = metisContentStoreEntry_Create(message, NULL, 2l, 1l); + * + * metisTimeOrderedList_Add(list, entry); + * + * ... + * + * metisTimeOrderedList_Remove(list, entry); + * metisTimeOrderedList_Release(&list); + * + * metisContentStoreEntry_Release(&entry); + * metisMessage_Release(&message); + * metisLogger_Release(&logger); + * } + * @endcode + * @see metisTimeOrderedList_Add + */ +bool metisTimeOrderedList_Remove(MetisTimeOrderedList *list, MetisContentStoreEntry *storeEntry); + +/** + * Return the oldest {@link MetisContentStoreEntry} 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 `MetisContentStoreEntry` in the list + * @param NULL if no `MetisContentStoreEntry` was available. + * + * Example: + * @code + * { + * MetisLogger *logger = metisLogger_Create(...); + * MetisTimeOrderedList *list = + * metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + * MetisLruList *lruList = metisLruList_Create(); + * MetisMessage *message = metisMessage_CreateFromArray((uint8_t *) "\x00" "ehlo", 5, 111, 2, logger); + * + * MetisContentStoreEntry *entry = metisContentStoreEntry_Create(message, lruList, 2l, 1l); + * + * metisTimeOrderedList_Add(list, entry); + * + * MetisContentStoreEntry *oldest = metisTimeOrderedList_GetOldest(list); + * + * ... + * + * metisTimeOrderedList_Release(&list); + * + * metisContentStoreEntry_Release(&entry); + * metisMessage_Release(&message); + * metisLruList_Destroy(&lruList); + * metisLogger_Release(&logger); + * } + * @endcode + * @see metisTimeOrderedList_Remove + */ +MetisContentStoreEntry *metisTimeOrderedList_GetOldest(MetisTimeOrderedList *list); + +/** + * Return the number of items currently stored in the list. + * + * @param list the `MetisTimeOrderedList` instance from which to retrieve the count. + * @return the number of items in the list. + * + * Example: + * @code + * { + * MetisLogger *logger = metisLogger_Create(...); + * MetisTimeOrderedList *list = + * metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + * MetisLruList *lruList = metisLruList_Create(); + * MetisMessage *message = metisMessage_CreateFromArray((uint8_t *) "\x00" "ehlo", 5, 111, 2, logger); + * + * MetisContentStoreEntry *entry = metisContentStoreEntry_Create(message, lruList, 2l, 1l); + * + * metisTimeOrderedList_Add(list, entry); + * + * ... + * size_t numItemsInList = metisTimeOrderedList_Length(list); + * ... + * + * metisTimeOrderedList_Release(&list); + * + * metisContentStoreEntry_Release(&entry); + * metisMessage_Release(&message); + * metisLruList_Destroy(&lruList); + * metisLogger_Release(&logger); + * } + * @endcode + */ +size_t metisTimeOrderedList_Length(MetisTimeOrderedList *list); +#endif /* defined(__Metis__metis_TimeOrderedList__) */ diff --git a/metis/ccnx/forwarder/metis/content_store/test/CMakeLists.txt b/metis/ccnx/forwarder/metis/content_store/test/CMakeLists.txt new file mode 100644 index 00000000..0542732d --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/test/CMakeLists.txt @@ -0,0 +1,17 @@ +# Enable gcov output for the tests +add_definitions(--coverage) +set(CMAKE_EXE_LINKER_FLAGS ${CMAKE_EXE_LINKER_FLAGS} " --coverage") + +set(TestsExpectedToPass + test_metis_LruList + test_metis_ContentStoreEntry + test_metis_ContentStoreInterface + test_metis_TimeOrderedList + test_metis_LRUContentStore +) + + +foreach(test ${TestsExpectedToPass}) + AddTest(${test}) +endforeach() + diff --git a/metis/ccnx/forwarder/metis/content_store/test/test_metis_ContentStoreEntry.c b/metis/ccnx/forwarder/metis/content_store/test/test_metis_ContentStoreEntry.c new file mode 100644 index 00000000..87d154b7 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/test/test_metis_ContentStoreEntry.c @@ -0,0 +1,354 @@ +/* + * 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 "../metis_ContentStoreEntry.c" +#include <LongBow/unit-test.h> + +#include <parc/algol/parc_SafeMemory.h> +#include <parc/logging/parc_LogReporterTextStdout.h> + +#include <ccnx/forwarder/metis/testdata/metis_TestDataV0.h> +#include <ccnx/forwarder/metis/testdata/metis_TestDataV1.h> + + +LONGBOW_TEST_RUNNER(metis_ContentStoreEntry) +{ + // The following Test Fixtures will run their corresponding Test Cases. + // Test Fixtures are run in the order specified, but all tests should be idempotent. + // Never rely on the execution order of tests or share state between them. + LONGBOW_RUN_TEST_FIXTURE(Global); + LONGBOW_RUN_TEST_FIXTURE(Local); +} + +// The Test Runner calls this function once before any Test Fixtures are run. +LONGBOW_TEST_RUNNER_SETUP(metis_ContentStoreEntry) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// The Test Runner calls this function once after all the Test Fixtures are run. +LONGBOW_TEST_RUNNER_TEARDOWN(metis_ContentStoreEntry) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// ============================================================================ + +LONGBOW_TEST_FIXTURE(Global) +{ + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_Create_Destroy_Memory); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_Create_Destroy_State); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_Acquire); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_GetMessage); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_MoveToHead); + + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_GetExpiryTimeInTicks); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_GetRecommendedCacheTimeInTicks); + + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_CompareRecommendedCacheTime); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreEntry_CompareExpiryTime); +} + +LONGBOW_TEST_FIXTURE_SETUP(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Global) +{ + if (parcSafeMemory_ReportAllocation(STDOUT_FILENO) != 0) { + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} +static MetisLogger * +_createLogger() +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + metisLogger_SetLogLevel(logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug); + parcLogReporter_Release(&reporter); + + return logger; +} +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_Create_Destroy_Memory) +{ + MetisLruList *lruList = metisLruList_Create(); + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + MetisMessage *object = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + metisLogger_Release(&logger); + + size_t beforeMemory = parcMemory_Outstanding(); + MetisContentStoreEntry *storeEntry = metisContentStoreEntry_Create(object, lruList); + metisContentStoreEntry_Release(&storeEntry); + size_t afterMemory = parcMemory_Outstanding(); + + metisLruList_Destroy(&lruList); + metisMessage_Release(&object); + + assertTrue(afterMemory == beforeMemory, "Imbalance on create/destroy, expected %zu got %zu", beforeMemory, afterMemory); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_Create_Destroy_State) +{ + MetisLogger *logger = _createLogger(); + + MetisLruList *lruList = metisLruList_Create(); + MetisMessage *object = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + + MetisContentStoreEntry *storeEntry = metisContentStoreEntry_Create(object, lruList); + + assertTrue(storeEntry->refcount == 1, "lruEntry has wrong refcount, expected %u got %u", 1, storeEntry->refcount); + + metisContentStoreEntry_Release(&storeEntry); + metisLruList_Destroy(&lruList); + metisMessage_Release(&object); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_Acquire) +{ + MetisLogger *logger = _createLogger(); + MetisLruList *lruList = metisLruList_Create(); + MetisMessage *object = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + + MetisContentStoreEntry *storeEntry = metisContentStoreEntry_Create(object, lruList); + MetisContentStoreEntry *copy = metisContentStoreEntry_Acquire(storeEntry); + + assertTrue(copy->refcount == 2, "incorrect refcount after copy, expected %u got %u", 2, copy->refcount); + metisContentStoreEntry_Release(&storeEntry); + assertTrue(copy->refcount == 1, "incorrect refcount after destroy, expected %u got %u", 1, copy->refcount); + + metisContentStoreEntry_Release(©); + metisLruList_Destroy(&lruList); + metisMessage_Release(&object); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_GetMessage) +{ + MetisLogger *logger = _createLogger(); + + MetisLruList *lruList = metisLruList_Create(); + MetisMessage *object = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + + MetisContentStoreEntry *storeEntry = metisContentStoreEntry_Create(object, lruList); + + MetisMessage *copy = metisContentStoreEntry_GetMessage(storeEntry); + assertTrue(copy == object, "Incorrect mesage, expected %p got %p", (void *) object, (void *) copy); + + metisContentStoreEntry_Release(&storeEntry); + + metisLruList_Destroy(&lruList); + metisMessage_Release(&object); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_MoveToHead) +{ + MetisLogger *logger = _createLogger(); + MetisLruList *lruList = metisLruList_Create(); + + MetisMessage *object[3]; + MetisContentStoreEntry *storeEntry[3]; + + for (int i = 0; i < 3; i++) { + object[i] = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), i, 2, logger); + storeEntry[i] = metisContentStoreEntry_Create(object[i], lruList); + } + + // object 2 is at top of list and object 0 is at bottom. move 0 to top and 1 should be at bottom + metisContentStoreEntry_MoveToHead(storeEntry[0]); + + MetisLruListEntry *bottom = metisLruList_PopTail(lruList); + + assertTrue(bottom == storeEntry[1]->lruEntry, "Incorrect mesage, expected %p got %p", (void *) storeEntry[1]->lruEntry, (void *) bottom); + for (int i = 0; i < 3; i++) { + metisContentStoreEntry_Release(&storeEntry[i]); + metisMessage_Release(&object[i]); + } + + metisLogger_Release(&logger); + metisLruList_Destroy(&lruList); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_GetExpiryTimeInTicks) +{ + MetisLogger *logger = _createLogger(); + + MetisMessage *object = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + + uint64_t expiryTime = 101l; + metisMessage_SetExpiryTimeTicks(object, expiryTime); + + MetisContentStoreEntry *storeEntry = metisContentStoreEntry_Create(object, NULL); + + assertTrue(metisContentStoreEntry_HasExpiryTimeTicks(storeEntry), "Expected entry to have expiry time"); + assertTrue(metisContentStoreEntry_GetExpiryTimeTicks(storeEntry) == expiryTime, "Got unexpected expiry time"); + + metisContentStoreEntry_Release(&storeEntry); + metisMessage_Release(&object); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_GetRecommendedCacheTimeInTicks) +{ + MetisLogger *logger = _createLogger(); + + MetisMessage *object = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + + uint64_t rct = 202l; + metisMessage_SetRecommendedCacheTimeTicks(object, rct); + + MetisContentStoreEntry *storeEntry = metisContentStoreEntry_Create(object, NULL); + + assertTrue(metisContentStoreEntry_HasRecommendedCacheTimeTicks(storeEntry), "Expected entry to have expiry time"); + assertTrue(metisContentStoreEntry_GetRecommendedCacheTimeTicks(storeEntry) == rct, "Got unexpected cache time"); + + metisContentStoreEntry_Release(&storeEntry); + metisMessage_Release(&object); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_CompareExpiryTime) +{ + MetisLogger *logger = _createLogger(); + + MetisMessage *message = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *message2 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 3, 4, logger); + + metisMessage_SetExpiryTimeTicks(message, 100); + MetisContentStoreEntry *entry1 = metisContentStoreEntry_Create(message, NULL); + + metisMessage_SetExpiryTimeTicks(message, 200); + MetisContentStoreEntry *entry2 = metisContentStoreEntry_Create(message, NULL); + + // Different message, same times as entry1 + metisMessage_SetExpiryTimeTicks(message2, 100); + MetisContentStoreEntry *entry3 = metisContentStoreEntry_Create(message2, NULL); + + // Same message, same times as entry2 + metisMessage_SetExpiryTimeTicks(message, 200); + MetisContentStoreEntry *entry4 = metisContentStoreEntry_Create(message, NULL); + + assertTrue(metisContentStoreEntry_CompareExpiryTime(entry1, entry2) == -1, "Expected -1"); + assertTrue(metisContentStoreEntry_CompareExpiryTime(entry2, entry1) == 1, "Expected +1"); + assertTrue(metisContentStoreEntry_CompareExpiryTime(entry1, entry1) == 0, "Expected 0"); + + // Compare same expiry time, but different Message addressed. + if (message < message2) { + assertTrue(metisContentStoreEntry_CompareExpiryTime(entry1, entry3) == -1, "Expected -1"); + assertTrue(metisContentStoreEntry_CompareExpiryTime(entry3, entry1) == 1, "Expected +1"); + } else { + assertTrue(metisContentStoreEntry_CompareExpiryTime(entry1, entry3) == 1, "Expected 1"); + assertTrue(metisContentStoreEntry_CompareExpiryTime(entry3, entry1) == -1, "Expected -1"); + } + + assertTrue(metisContentStoreEntry_CompareExpiryTime(entry2, entry4) == 0, "Expected 0"); + + metisContentStoreEntry_Release(&entry1); + metisContentStoreEntry_Release(&entry2); + metisContentStoreEntry_Release(&entry3); + metisContentStoreEntry_Release(&entry4); + + metisMessage_Release(&message); + metisMessage_Release(&message2); + + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreEntry_CompareRecommendedCacheTime) +{ + MetisLogger *logger = _createLogger(); + + MetisMessage *message = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *message2 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 3, 4, logger); + + metisMessage_SetRecommendedCacheTimeTicks(message, 200); + MetisContentStoreEntry *entry1 = metisContentStoreEntry_Create(message, NULL); + + metisMessage_SetRecommendedCacheTimeTicks(message, 100); + MetisContentStoreEntry *entry2 = metisContentStoreEntry_Create(message, NULL); + + // Different message, same times as entry1 + metisMessage_SetRecommendedCacheTimeTicks(message2, 200); + MetisContentStoreEntry *entry3 = metisContentStoreEntry_Create(message2, NULL); + + // Same message, same times as entry2 + metisMessage_SetRecommendedCacheTimeTicks(message, 100); + MetisContentStoreEntry *entry4 = metisContentStoreEntry_Create(message, NULL); + + assertTrue(metisContentStoreEntry_CompareRecommendedCacheTime(entry1, entry2) == 1, "Expected 1"); + assertTrue(metisContentStoreEntry_CompareRecommendedCacheTime(entry2, entry1) == -1, "Expected -1"); + assertTrue(metisContentStoreEntry_CompareRecommendedCacheTime(entry1, entry1) == 0, "Expected 0"); + + // Compare same RCT, but different Message addressed. + if (message < message2) { + assertTrue(metisContentStoreEntry_CompareRecommendedCacheTime(entry1, entry3) == -1, "Expected -1"); + assertTrue(metisContentStoreEntry_CompareRecommendedCacheTime(entry3, entry1) == 1, "Expected +1"); + } else { + assertTrue(metisContentStoreEntry_CompareRecommendedCacheTime(entry1, entry3) == 1, "Expected 1"); + assertTrue(metisContentStoreEntry_CompareRecommendedCacheTime(entry3, entry1) == -1, "Expected -1"); + } + + assertTrue(metisContentStoreEntry_CompareRecommendedCacheTime(entry2, entry4) == 0, "Expected 0"); + + metisContentStoreEntry_Release(&entry1); + metisContentStoreEntry_Release(&entry2); + metisContentStoreEntry_Release(&entry3); + metisContentStoreEntry_Release(&entry4); + + metisMessage_Release(&message); + metisMessage_Release(&message2); + + metisLogger_Release(&logger); +} + +// ============================================================================ + +LONGBOW_TEST_FIXTURE(Local) +{ +} + +LONGBOW_TEST_FIXTURE_SETUP(Local) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Local) +{ + if (parcSafeMemory_ReportAllocation(STDOUT_FILENO) != 0) { + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + +// ============================================================================ + +int +main(int argc, char *argv[]) +{ + LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(metis_ContentStoreEntry); + int exitStatus = longBowMain(argc, argv, testRunner, NULL); + longBowTestRunner_Destroy(&testRunner); + exit(exitStatus); +} diff --git a/metis/ccnx/forwarder/metis/content_store/test/test_metis_ContentStoreInterface.c b/metis/ccnx/forwarder/metis/content_store/test/test_metis_ContentStoreInterface.c new file mode 100644 index 00000000..1a32308a --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/test/test_metis_ContentStoreInterface.c @@ -0,0 +1,222 @@ +/* + * 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 "../metis_ContentStoreInterface.c" + +#include <LongBow/unit-test.h> + +#include <parc/logging/parc_LogReporterTextStdout.h> + +#include <parc/algol/parc_SafeMemory.h> + +#include <ccnx/forwarder/metis/content_store/metis_LRUContentStore.h> +#include <ccnx/forwarder/metis/testdata/metis_TestDataV0.h> + +LONGBOW_TEST_RUNNER(metis_ContentStoreInterface) +{ + parcMemory_SetInterface(&PARCSafeMemoryAsPARCMemory); + + LONGBOW_RUN_TEST_FIXTURE(Global); +} + +// The Test Runner calls this function once before any Test Fixtures are run. +LONGBOW_TEST_RUNNER_SETUP(metis_ContentStoreInterface) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// The Test Runner calls this function once after all the Test Fixtures are run. +LONGBOW_TEST_RUNNER_TEARDOWN(metis_ContentStoreInterface) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE(Global) +{ + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreInterface_CreateRelease); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreInterface_PutContent); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreInterface_RemoveContent); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreInterface_MatchInterest); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreInterface_GetObjectCount); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreInterface_GetObjectCapacity); + LONGBOW_RUN_TEST_CASE(Global, metisContentStoreInterface_Log); +} + +LONGBOW_TEST_FIXTURE_SETUP(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Global) +{ + uint32_t outstandingAllocations = parcSafeMemory_ReportAllocation(STDERR_FILENO); + if (outstandingAllocations != 0) { + printf("%s leaks memory by %d allocations\n", longBowTestCase_GetName(testCase), outstandingAllocations); + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + +static MetisLogger * +_createLogger(void) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *result = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + metisLogger_SetLogLevel(result, MetisLoggerFacility_Processor, PARCLogLevel_Debug); + + return result; +} +static MetisContentStoreInterface * +_createContentStore(MetisLogger *logger) +{ + MetisContentStoreConfig config = { + .objectCapacity = 1000, + }; + + MetisContentStoreInterface *result = metisLRUContentStore_Create(&config, logger); + assertNotNull(result, "Expected to allocate a MetisContentStoreInterface"); + + return result; +} + +LONGBOW_TEST_CASE(Global, metisContentStoreInterface_CreateRelease) +{ + MetisLogger *logger = _createLogger(); + MetisContentStoreInterface *store = _createContentStore(logger); + + assertNotNull(store, "Expected to allocate a MetisContentStoreInterface"); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreInterface_PutContent) +{ + MetisLogger *logger = _createLogger(); + MetisContentStoreInterface *store = _createContentStore(logger); + + MetisMessage *content = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + metisContentStoreInterface_PutContent(store, content, 1000); + + metisMessage_Release(&content); + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreInterface_RemoveContent) +{ + MetisLogger *logger = _createLogger(); + MetisContentStoreInterface *store = _createContentStore(logger); + + MetisMessage *content = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + metisContentStoreInterface_PutContent(store, content, 1000); + + bool wasRemoved = metisContentStoreInterface_RemoveContent(store, content); + assertTrue(wasRemoved, "Expected to remove the previously stored MetisMessage"); + + metisMessage_Release(&content); + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreInterface_MatchInterest) +{ + MetisLogger *logger = _createLogger(); + MetisContentStoreInterface *store = _createContentStore(logger); + + MetisMessage *content = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + metisContentStoreInterface_PutContent(store, content, 1000); + + MetisMessage *interest = metisMessage_CreateFromArray(metisTestDataV0_InterestWithName, sizeof(metisTestDataV0_InterestWithName), 1, 2, logger); + MetisMessage *match = metisContentStoreInterface_MatchInterest(store, interest); + + assertTrue(match == content, "Expected to retrieve the stored MetisMessage"); + + metisMessage_Release(&interest); + metisMessage_Release(&content); + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + +static MetisMessage * +_createUniqueMetisMessage(MetisLogger *logger, int tweakNumber, uint8_t *template, size_t templateSize, int nameOffset) +{ + PARCBuffer *buffer = parcBuffer_Allocate(templateSize); + memcpy(parcBuffer_Overlay(buffer, 0), template, templateSize); // Copy the template to new memory + + // Tweak the encoded object's name so the name hash varies each time. + uint8_t *bufPtr = parcBuffer_Overlay(buffer, 0); + bufPtr[nameOffset] = 'a' + tweakNumber; + + MetisMessage *result = metisMessage_CreateFromArray(bufPtr, templateSize, 1, 2, logger); + parcBuffer_Release(&buffer); + + return result; +} + +LONGBOW_TEST_CASE(Global, metisContentStoreInterface_GetObjectCount) +{ + MetisLogger *logger = _createLogger(); + MetisContentStoreInterface *store = _createContentStore(logger); + + for (int i = 1; i < 100; i++) { + MetisMessage *content = _createUniqueMetisMessage(logger, i, metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), + metisTestDataV0_EncodedObject_name.offset + 4); + metisContentStoreInterface_PutContent(store, content, 1000 + i); + metisMessage_Release(&content); + + size_t count = metisContentStoreInterface_GetObjectCount(store); + assertTrue(count == i, "Expected a count of %d items, got %zu", i, count); + } + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreInterface_GetObjectCapacity) +{ + MetisLogger *logger = _createLogger(); + MetisContentStoreConfig config = { + .objectCapacity = 1000, + }; + + MetisContentStoreInterface *store = metisLRUContentStore_Create(&config, logger); + assertTrue(metisContentStoreInterface_GetObjectCapacity(store) == config.objectCapacity, "Expected to get back the capacity we set"); + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisContentStoreInterface_Log) +{ + MetisLogger *logger = _createLogger(); + MetisContentStoreInterface *store = _createContentStore(logger); + + metisContentStoreInterface_Log(store); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + +int +main(int argc, char *argv[]) +{ + LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(metis_ContentStoreInterface); + int exitStatus = longBowMain(argc, argv, testRunner, NULL); + longBowTestRunner_Destroy(&testRunner); + exit(exitStatus); +} diff --git a/metis/ccnx/forwarder/metis/content_store/test/test_metis_LRUContentStore.c b/metis/ccnx/forwarder/metis/content_store/test/test_metis_LRUContentStore.c new file mode 100644 index 00000000..ea55b361 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/test/test_metis_LRUContentStore.c @@ -0,0 +1,788 @@ +/* + * 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 "../metis_LRUContentStore.c" +#include <LongBow/unit-test.h> + +#include <parc/algol/parc_SafeMemory.h> +#include <parc/logging/parc_LogReporterTextStdout.h> + +#include <ccnx/forwarder/metis/testdata/metis_TestDataV0.h> +#include <ccnx/forwarder/metis/testdata/metis_TestDataV1.h> + + +LONGBOW_TEST_RUNNER(metis_LRUContentStore) +{ + parcMemory_SetInterface(&PARCSafeMemoryAsPARCMemory); + + LONGBOW_RUN_TEST_FIXTURE(Global); + LONGBOW_RUN_TEST_FIXTURE(Local); +} + +// The Test Runner calls this function once before any Test Fixtures are run. +LONGBOW_TEST_RUNNER_SETUP(metis_LRUContentStore) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// The Test Runner calls this function once after all the Test Fixtures are run. +LONGBOW_TEST_RUNNER_TEARDOWN(metis_LRUContentStore) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// ============================================================================ + +LONGBOW_TEST_FIXTURE(Global) +{ + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Create_Destroy); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Log); + + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Create_ZeroCapacity); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Fetch_ByName); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Fetch_ByNameAndKeyId); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Fetch_ByNameAndObjectHash); + + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Remove_Content); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Remove_NonExistentContent); + + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Fetch_Lru); + + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Save_ZeroCapacity); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Save_CapacityLimit); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Save_WithoutEviction); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Save_WithEviction); + + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Save_WithEvictionByExpiryTime); + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Save_WithEvictionByRCT); + + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Save_ExpiredContent); + + LONGBOW_RUN_TEST_CASE(Global, metisLRUContentStore_Save_DuplicateHash); +} + +LONGBOW_TEST_FIXTURE_SETUP(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Global) +{ + uint32_t outstandingAllocations = parcSafeMemory_ReportAllocation(STDERR_FILENO); + if (outstandingAllocations != 0) { + printf("%s leaks memory by %d allocations\n", longBowTestCase_GetName(testCase), outstandingAllocations); + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + +static MetisContentStoreInterface * +_createLRUContentStore(size_t capacity) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + metisLogger_SetLogLevel(logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug); + + MetisContentStoreConfig config = { + .objectCapacity = capacity, + }; + + MetisContentStoreInterface *store = metisLRUContentStore_Create(&config, logger); + + metisLogger_Release(&logger); + + return store; +} + +static MetisMessage * +_createUniqueMetisMessage(MetisLogger *logger, int tweakNumber, uint8_t *template, size_t templateSize, int nameOffset) +{ + PARCBuffer *buffer = parcBuffer_Allocate(templateSize); + memcpy(parcBuffer_Overlay(buffer, 0), template, templateSize); // Copy the template to new memory + + // Tweak the encoded object's name so the name hash varies each time. + uint8_t *bufPtr = parcBuffer_Overlay(buffer, 0); + bufPtr[nameOffset] = 'a' + tweakNumber; + + MetisMessage *result = metisMessage_CreateFromArray(bufPtr, templateSize, 1, 2, logger); + parcBuffer_Release(&buffer); + + return result; +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Create_Destroy) +{ + MetisContentStoreInterface *store = _createLRUContentStore(10); + assertNotNull(store, "Expected to init a content store"); + metisContentStoreInterface_Release(&store); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Log) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 20; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + for (int i = 1; i <= capacity; i++) { + int offsetOfNameInEncodedObject = metisTestDataV0_EncodedObject_name.offset + 4; + + MetisMessage *object = _createUniqueMetisMessage(logger, i, + metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), + offsetOfNameInEncodedObject); + + bool success = metisContentStoreInterface_PutContent(store, object, 1); + metisMessage_Release(&object); + + assertTrue(success, "Unexpectedly failed to add entry to ContentStore"); + } + + metisContentStoreInterface_Log(store); + + metisLogger_Release(&logger); + metisContentStoreInterface_Release(&store); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Create_ZeroCapacity) +{ + size_t capacity = 10; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + assertTrue(metisContentStoreInterface_GetObjectCapacity(store) == capacity, "Wrong capacity, expected %zu got %zu", + capacity, metisContentStoreInterface_GetObjectCapacity(store)); + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 0, "Wrong initial count, expected %u got %zu", 0, + metisContentStoreInterface_GetObjectCount(store)); + metisContentStoreInterface_Release(&store); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Fetch_ByName) +{ + size_t capacity = 10; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + uint64_t expiryTime = 300l; + uint64_t rct = 200; + uint64_t now = 100; + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + + metisMessage_SetExpiryTimeTicks(object_1, expiryTime); + metisMessage_SetRecommendedCacheTimeTicks(object_1, rct); + + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + metisMessage_SetExpiryTimeTicks(object_2, expiryTime); + metisMessage_SetRecommendedCacheTimeTicks(object_2, rct); + + metisMessage_SetExpiryTimeTicks(object_1, expiryTime); + metisMessage_SetRecommendedCacheTimeTicks(object_1, rct); + + metisContentStoreInterface_PutContent(store, object_1, now); + metisContentStoreInterface_PutContent(store, object_2, now); + + MetisMessage *interestByName = metisMessage_CreateFromArray(metisTestDataV0_InterestWithName, + sizeof(metisTestDataV0_InterestWithName), 3, 5, logger); + + + MetisMessage *testObject = metisContentStoreInterface_MatchInterest(store, interestByName); + assertNotNull(testObject, "Fetch did not find match when it should have"); + + uint64_t expiryTimeOut = metisMessage_GetExpiryTimeTicks(testObject); + uint64_t rctOut = metisMessage_GetRecommendedCacheTimeTicks(testObject); + bool hasExpiryTime = metisMessage_HasExpiryTime(testObject); + bool hasRCT = metisMessage_HasRecommendedCacheTime(testObject); + + assertTrue(hasRCT, "Expected object to have an RCT"); + assertTrue(hasExpiryTime, "Expected object to have an ExpiryTime"); + assertTrue(expiryTime == expiryTimeOut, "Expected the same expiryTime to be retrieved"); + assertTrue(rct == rctOut, "Expected the same RCT to be retrieved"); + + // two objects with same name, 1st one will win + assertTrue(testObject == object_1, "Fetch returned wrong object, expecting %p got %p", + (void *) object_1, (void *) testObject); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); + metisMessage_Release(&interestByName); +} + + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Fetch_ByNameAndKeyId) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 10; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + + metisContentStoreInterface_PutContent(store, object_1, 1); + metisContentStoreInterface_PutContent(store, object_2, 1); + + MetisMessage *interestByNameKeyId = metisMessage_CreateFromArray(metisTestDataV0_InterestWithName_keyid, + sizeof(metisTestDataV0_InterestWithName_keyid), + 3, 5, logger); + + MetisMessage *testObject = metisContentStoreInterface_MatchInterest(store, interestByNameKeyId); + assertNotNull(testObject, "Fetch did not find match when it should have"); + + // two objects with same name, 1st one will win + assertTrue(testObject == object_1, "Fetch returned wrong object, expecting %p got %p", + (void *) object_1, (void *) testObject); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); + metisMessage_Release(&interestByNameKeyId); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Fetch_ByNameAndObjectHash) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 10; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + + uint64_t expiryTime = 300l; + uint64_t rct = 200l; + uint64_t now = 100l; + + metisMessage_SetExpiryTimeTicks(object_1, expiryTime); + metisMessage_SetRecommendedCacheTimeTicks(object_1, rct); + + metisContentStoreInterface_PutContent(store, object_1, now); + metisContentStoreInterface_PutContent(store, object_2, now); + + MetisMessage *interestByNameObjectHash = + metisMessage_CreateFromArray(metisTestDataV0_InterestWithName_objecthash, + sizeof(metisTestDataV0_InterestWithName_objecthash), 3, 5, logger); + + // this should retrieve object_1 because that is the one whose + // content object hash matches the interest + + MetisMessage *testObject = metisContentStoreInterface_MatchInterest(store, interestByNameObjectHash); + + assertTrue(expiryTime == metisMessage_GetExpiryTimeTicks(testObject), "Expected the same expiryTime to be retrieved"); + assertTrue(rct == metisMessage_GetRecommendedCacheTimeTicks(testObject), "Expected the same RCT to be retrieved"); + + assertNotNull(testObject, "Fetch did not find match when it should have"); + + // two objects with same name, 1st one will win + assertTrue(testObject == object_1, "Fetch returned wrong object, expecting %p got %p", (void *) object_1, (void *) testObject); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); + metisMessage_Release(&interestByNameObjectHash); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Remove_Content) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 10; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + + metisMessage_SetExpiryTimeTicks(object_1, 200); + metisMessage_SetRecommendedCacheTimeTicks(object_1, 100); + + metisContentStoreInterface_PutContent(store, object_1, 10); + metisContentStoreInterface_PutContent(store, object_2, 10); + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 2, "Expected 2 objects in the metisContentStoreInterface_"); + + MetisMessage *interestByNameObjectHash = + metisMessage_CreateFromArray(metisTestDataV0_InterestWithName_objecthash, + sizeof(metisTestDataV0_InterestWithName_objecthash), 3, 5, logger); + + // this should retrieve object_1 because that is the one whose + // content object hash matches the interest + MetisMessage *testObject = metisContentStoreInterface_MatchInterest(store, interestByNameObjectHash); + + + assertNotNull(testObject, "Fetch did not find match when it should have"); + + // two objects with same name, 1st one will win + assertTrue(testObject == object_1, "Fetch returned wrong object, expecting %p got %p", + (void *) object_1, (void *) testObject); + + // Now remove it. + metisContentStoreInterface_RemoveContent(store, object_1); // Releases the contained Message + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Expected 1 object in the store, got %zu", + metisContentStoreInterface_GetObjectCount(store)); + + MetisMessage *nullObject = metisContentStoreInterface_MatchInterest(store, interestByNameObjectHash); + + assertNull(nullObject, "Fetch found a match when it should not have"); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); + metisMessage_Release(&interestByNameObjectHash); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Remove_NonExistentContent) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 10; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + + metisContentStoreInterface_PutContent(store, object_1, 1); + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Expected 1 object in the metisContentStoreInterface_"); + + // Try to remove one that is not in the store. + bool result = metisContentStoreInterface_RemoveContent(store, object_2); // Releases the contained Message + assertFalse(result, "Expected to NOT remove object_2"); + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Expected 1 object in the metisContentStoreInterface_"); + + result = metisContentStoreInterface_RemoveContent(store, object_1); // Releases the contained Message + assertTrue(result, "Expected to remove object_1"); + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 0, "Expected 0 objects in the metisContentStoreInterface_"); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); +} + +/* + * Create an cache and access objects to make sure the LRU is evicting the right way + */ +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Fetch_Lru) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + metisLogger_SetLogLevel(logger, MetisLoggerFacility_Processor, PARCLogLevel_Debug); + parcLogReporter_Release(&reporter); + + size_t capacity = 2; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object2 = metisMessage_CreateFromArray(metisTestDataV0_object_with_othername, + sizeof(metisTestDataV0_object_with_othername), 2, 2, logger); + + metisContentStoreInterface_PutContent(store, object1, 1); + metisContentStoreInterface_PutContent(store, object2, 1); + + // object 2 sould be at top of LRU (was saved last). Fetch object 1, then evict object 2. + + // interest_with_name will match the name in object1. + MetisMessage *interestByName = metisMessage_CreateFromArray(metisTestDataV0_InterestWithName, + sizeof(metisTestDataV0_InterestWithName), 3, 5, logger); + + MetisMessage *testObject = metisContentStoreInterface_MatchInterest(store, interestByName); + + assertTrue(testObject == object1, "Fetch returned wrong object, expecting %p got %p", (void *) object1, (void *) testObject); + + // objectcapacity = 2, so object 3 will evict bottom of LRU + MetisMessage *object3 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 4, 2, logger); + metisContentStoreInterface_PutContent(store, object3, 1); + + // object 2 should be evicted + MetisMessage *interestOtherName = metisMessage_CreateFromArray(metisTestDataV0_InterestWithOtherName, + sizeof(metisTestDataV0_InterestWithOtherName), 5, 5, logger); + MetisMessage *testEvictedObject = metisContentStoreInterface_MatchInterest(store, interestOtherName); + + + assertNull(testEvictedObject, "object with othername should have been evicted"); + + // as final sanity check, make sure object 1 is still in the list + MetisMessage *testObject1Again = metisContentStoreInterface_MatchInterest(store, interestByName); + + assertNotNull(testObject1Again, "Did not retrieve object1 from the content store"); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object1); + metisMessage_Release(&object2); + metisMessage_Release(&object3); + metisMessage_Release(&interestByName); + metisMessage_Release(&interestOtherName); +} + + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Save_WithoutEviction) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 10; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + + metisContentStoreInterface_PutContent(store, object_1, 10); + metisContentStoreInterface_PutContent(store, object_2, 10); + + _MetisLRUContentStore *internalStore = ( _MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(store); + _MetisLRUContentStoreStats *stats = &internalStore->stats; + + assertTrue(stats->countAdds == 2, "Wrong countAdds, expected %u got %" PRIu64, 2, stats->countAdds); + assertTrue(stats->countLruEvictions == 0, "Wrong countLruEvictions, expected %u got %" PRIu64, 0, stats->countLruEvictions); + assertTrue(metisLruList_Length(internalStore->lru) == 2, "Wrong metisLruList_Length, expected %u got %zu", 2, + metisLruList_Length(internalStore->lru)); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Save_WithEviction) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 1; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *content_1 = _createUniqueMetisMessage(logger, 1, metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), + metisTestDataV0_EncodedObject_name.offset + 4); + + MetisMessage *content_2 = _createUniqueMetisMessage(logger, 2, metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), + metisTestDataV0_EncodedObject_name.offset + 4); + + MetisMessage *content_3 = _createUniqueMetisMessage(logger, 3, metisTestDataV0_EncodedObject, sizeof(metisTestDataV0_EncodedObject), + metisTestDataV0_EncodedObject_name.offset + 4); + + + metisContentStoreInterface_PutContent(store, content_1, 1); + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Wrong objectCount. Expected %u, got %zu", 1, metisContentStoreInterface_GetObjectCount(store)); + + metisContentStoreInterface_PutContent(store, content_2, 1); + metisContentStoreInterface_PutContent(store, content_3, 1); + + _MetisLRUContentStore *internalStore = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(store); + _MetisLRUContentStoreStats *stats = &internalStore->stats; + + // Capacity is 1, so we should never grow bigger than that. + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Wrong objectCount. Expected %u, got %zu", 1, metisContentStoreInterface_GetObjectCount(store)); + + assertTrue(stats->countAdds == 3, "Wrong countAdds, expected %u got %" PRIu64, 2, + stats->countAdds); + assertTrue(stats->countLruEvictions == 2, "Wrong countLruEvictions, expected %u got %" PRIu64, 1, stats->countLruEvictions); + assertTrue(metisLruList_Length(internalStore->lru) == 1, "Wrong metisLruList_Length, expected %u got %zu", 1, + metisLruList_Length(internalStore->lru)); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&content_1); + metisMessage_Release(&content_2); + metisMessage_Release(&content_3); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Save_ExpiredContent) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 1; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + + metisMessage_SetRecommendedCacheTimeTicks(object_1, 50); + + assertFalse(metisContentStoreInterface_PutContent(store, object_1, 51), "Should not be able to insert content past its recommended cache time"); + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 0, "Wrong objectCount. Expected 0, got %zu", metisContentStoreInterface_GetObjectCount(store)); + + metisMessage_SetExpiryTimeTicks(object_2, 100); + + assertFalse(metisContentStoreInterface_PutContent(store, object_2, 101), "Should not be able to insert content past its expiry time"); + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 0, "Wrong objectCount. Expected 0, got %zu", metisContentStoreInterface_GetObjectCount(store)); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); +} + + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Save_WithEvictionByExpiryTime) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 1; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + + uint64_t currentMetisTime = 150; + uint64_t expiryTime = 200; + + metisMessage_SetExpiryTimeTicks(object_1, expiryTime); + + // This should add the object, as currentMetisTime is less than expiry or RCT. + metisContentStoreInterface_PutContent(store, object_1, currentMetisTime); + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Wrong objectCount. Expected 1, got %zu", metisContentStoreInterface_GetObjectCount(store)); + + // No expiry time. + metisContentStoreInterface_PutContent(store, object_2, expiryTime + 10); // Add this one after expiration of first one. + + _MetisLRUContentStore *internalStore = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(store); + _MetisLRUContentStoreStats *stats = &internalStore->stats; + + // Capacity is 1, so we should never grow bigger than that. + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Wrong objectCount. Expected 1, got %zu", metisContentStoreInterface_GetObjectCount(store)); + + assertTrue(stats->countAdds == 2, "Wrong countAdds, expected %u got %" PRIu64, 2, + stats->countAdds); + assertTrue(stats->countExpiryEvictions == 1, "Wrong countLruEvictions, expected %u got %" PRIu64, 1, stats->countLruEvictions); + assertTrue(metisLruList_Length(internalStore->lru) == 1, "Wrong metisLruList_Length, expected 1 got %zu", + metisLruList_Length(internalStore->lru)); + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Expected a store count of 1"); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Save_WithEvictionByRCT) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 1; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + MetisMessage *object_2 = metisMessage_CreateFromArray(metisTestDataV0_SecondObject, + sizeof(metisTestDataV0_SecondObject), 1, 2, logger); + + + uint64_t recommendedCacheTime = 1000; + + metisMessage_SetRecommendedCacheTimeTicks(object_1, recommendedCacheTime); + metisContentStoreInterface_PutContent(store, object_1, recommendedCacheTime - 100); // Add it. + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Wrong objectCount. Expected 1, got %zu", + metisContentStoreInterface_GetObjectCount(store)); + + metisContentStoreInterface_PutContent(store, object_2, recommendedCacheTime + 1); // Add this one after the first one's RCT. + + _MetisLRUContentStore *internalStore = (_MetisLRUContentStore *) metisContentStoreInterface_GetPrivateData(store); + _MetisLRUContentStoreStats *stats = &internalStore->stats; + + // Capacity is 1, so we should never grow bigger than that. + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Wrong objectCount. Expected 1, got %zu", + metisContentStoreInterface_GetObjectCount(store)); + + assertTrue(stats->countAdds == 2, "Wrong countAdds, expected %u got %" PRIu64, 2, + stats->countAdds); + assertTrue(stats->countExpiryEvictions == 0, "Wrong countLruEvictions, expected 1got %" PRIu64, stats->countLruEvictions); + assertTrue(stats->countRCTEvictions == 1, "Wrong countLruEvictions, expected 1 got %" PRIu64, stats->countLruEvictions); + + assertTrue(metisLruList_Length(internalStore->lru) == 1, "Wrong metisLruList_Length, expected 1 got %zu", metisLruList_Length(internalStore->lru)); + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "Expected a store count of 1"); + + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); + metisMessage_Release(&object_1); + metisMessage_Release(&object_2); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Save_ZeroCapacity) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 0; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + bool success = metisContentStoreInterface_PutContent(store, object_1, 1); + assertFalse(success, "Should have returned failure with 0 capacity object store saving something"); + + metisMessage_Release(&object_1); + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Save_CapacityLimit) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 5; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + for (int i = 1; i < capacity * 2; i++) { + int offsetOfNameInEncodedObject = metisTestDataV0_EncodedObject_name.offset + 4; + + MetisMessage *object = _createUniqueMetisMessage(logger, i, + metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), + offsetOfNameInEncodedObject); + + bool success = metisContentStoreInterface_PutContent(store, object, 1); + + assertTrue(success, "Unexpectedly failed to add entry to ContentStore"); + + if (i < metisContentStoreInterface_GetObjectCapacity(store)) { + assertTrue(metisContentStoreInterface_GetObjectCount(store) == i, "Unexpected value for metisContentStoreInterface_objectCount"); + } else { + assertTrue(metisContentStoreInterface_GetObjectCount(store) == metisContentStoreInterface_GetObjectCapacity(store), + "Unexpected value (%zu) for metisContentStoreInterface_objectCount (%zu)", + metisContentStoreInterface_GetObjectCount(store), metisContentStoreInterface_GetObjectCapacity(store)); + } + + if (success) { + metisMessage_Release(&object); + } + } + metisLogger_Release(&logger); + metisContentStoreInterface_Release(&store); +} + +LONGBOW_TEST_CASE(Global, metisLRUContentStore_Save_DuplicateHash) +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + + size_t capacity = 5; + MetisContentStoreInterface *store = _createLRUContentStore(capacity); + + MetisMessage *object_1 = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + + + bool success = metisContentStoreInterface_PutContent(store, object_1, 1); + assertTrue(success, "Expected to add object_1 to store"); + + for (int i = 0; i < 10; i++) { + MetisMessage *object_1_dup = metisMessage_CreateFromArray(metisTestDataV0_EncodedObject, + sizeof(metisTestDataV0_EncodedObject), 1, 2, logger); + + success = metisContentStoreInterface_PutContent(store, object_1_dup, 1l); + + assertFalse(success, "Unexpectedly added duplicated entry to ContentStore"); + + assertTrue(metisContentStoreInterface_GetObjectCount(store) == 1, "ObjectCount should be 1"); + + metisMessage_Release(&object_1_dup); + } + + metisMessage_Release(&object_1); + metisContentStoreInterface_Release(&store); + metisLogger_Release(&logger); +} + +// ============================================================================ + +LONGBOW_TEST_FIXTURE(Local) +{ +} + +LONGBOW_TEST_FIXTURE_SETUP(Local) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Local) +{ + uint32_t outstandingAllocations = parcSafeMemory_ReportAllocation(STDERR_FILENO); + if (outstandingAllocations != 0) { + printf("%s leaks memory by %d allocations\n", longBowTestCase_GetName(testCase), outstandingAllocations); + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + + +// ============================================================================ + +int +main(int argc, char *argv[]) +{ + LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(metis_LRUContentStore); + int exitStatus = longBowMain(argc, argv, testRunner, NULL); + longBowTestRunner_Destroy(&testRunner); + exit(exitStatus); +} diff --git a/metis/ccnx/forwarder/metis/content_store/test/test_metis_LruList.c b/metis/ccnx/forwarder/metis/content_store/test/test_metis_LruList.c new file mode 100644 index 00000000..ef01b532 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/test/test_metis_LruList.c @@ -0,0 +1,204 @@ +/* + * 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 "../metis_LruList.c" +#include <LongBow/unit-test.h> +#include <parc/algol/parc_SafeMemory.h> + +LONGBOW_TEST_RUNNER(metis_LruList) +{ + // The following Test Fixtures will run their corresponding Test Cases. + // Test Fixtures are run in the order specified, but all tests should be idempotent. + // Never rely on the execution order of tests or share state between them. + LONGBOW_RUN_TEST_FIXTURE(Global); +} + +// The Test Runner calls this function once before any Test Fixtures are run. +LONGBOW_TEST_RUNNER_SETUP(metis_LruList) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// The Test Runner calls this function once after all the Test Fixtures are run. +LONGBOW_TEST_RUNNER_TEARDOWN(metis_LruList) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// ============================================================================ + +LONGBOW_TEST_FIXTURE(Global) +{ + LONGBOW_RUN_TEST_CASE(Global, metisLruList_Create_Destroy); + + LONGBOW_RUN_TEST_CASE(Global, MetisLruListEntry_Destroy); + LONGBOW_RUN_TEST_CASE(Global, metisLruEntry_GetData); + LONGBOW_RUN_TEST_CASE(Global, metisLruEntry_MoveToHead); + + LONGBOW_RUN_TEST_CASE(Global, metisLruList_NewHeadEntry); + LONGBOW_RUN_TEST_CASE(Global, metisLruList_PopTail); + LONGBOW_RUN_TEST_CASE(Global, MetisLruList_Length); +} + +LONGBOW_TEST_FIXTURE_SETUP(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Global) +{ + if (parcSafeMemory_ReportAllocation(STDOUT_FILENO) != 0) { + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_CASE(Global, MetisLruListEntry_Destroy) +{ + MetisLruList *lru = metisLruList_Create(); + + size_t beforeMemory = parcMemory_Outstanding(); + MetisLruListEntry *entry = (MetisLruListEntry *) metisLruList_NewHeadEntry(lru, (void *) 0x02); + metisLruList_PopTail(lru); + metisLruList_EntryDestroy(&entry); + size_t afterMemory = parcMemory_Outstanding(); + + metisLruList_Destroy(&lru); + + assertTrue(afterMemory == beforeMemory, "Memory imbalance for LruEntry_Destroy, expected %zu got %zu", beforeMemory, afterMemory); +} + +LONGBOW_TEST_CASE(Global, metisLruEntry_GetData) +{ + void *data = (void *) 99; + MetisLruList *lru = metisLruList_Create(); + MetisLruListEntry *entry = (MetisLruListEntry *) metisLruList_NewHeadEntry(lru, data); + void *p = metisLruList_EntryGetData(entry); + + assertTrue(p == data, "Data did not match, expected %p, got %p", data, p); + metisLruList_Destroy(&lru); +} + +LONGBOW_TEST_CASE(Global, metisLruEntry_MoveToHead) +{ + int loops = 10; + + MetisLruList *lru = metisLruList_Create(); + + for (size_t i = 1; i <= loops; i++) { + metisLruList_NewHeadEntry(lru, (void *) i); + } + + MetisLruListEntry *tail = metisLruList_PopTail(lru); + metisLruList_EntryMoveToHead(tail); + + MetisLruListEntry *test = TAILQ_FIRST(&lru->head); + assertTrue(test == tail, "Head element not moved, expected %p got %p", (void *) tail, (void *) test); + + metisLruList_Destroy(&lru); +} + +LONGBOW_TEST_CASE(Global, metisLruList_Create_Destroy) +{ + size_t baselineMemory = parcMemory_Outstanding(); + + MetisLruList *lru = metisLruList_Create(); + metisLruList_Destroy(&lru); + + assertTrue(parcMemory_Outstanding() == baselineMemory, "Memory imbalance on create/destroy: %u", parcMemory_Outstanding()); +} + +LONGBOW_TEST_CASE(Global, metisLruList_Length) +{ + int loops = 10; + + MetisLruList *lru = metisLruList_Create(); + + for (size_t i = 1; i <= loops; i++) { + MetisLruListEntry *entry = (MetisLruListEntry *) metisLruList_NewHeadEntry(lru, (void *) i); + assertTrue(lru->itemsInList == i, "Incorrect list length element %zu, expected %zu got %zu", i, i, lru->itemsInList); + assertTrue(metisLruList_Length(lru) == i, "Incorrect length encountered"); + + MetisLruListEntry *test = TAILQ_FIRST(&lru->head); + assertTrue(test == entry, "Head element not new entry, expected %p got %p", (void *) entry, (void *) test); + } + metisLruList_Destroy(&lru); +} + +LONGBOW_TEST_CASE(Global, metisLruList_NewHeadEntry) +{ + int loops = 10; + + MetisLruList *lru = metisLruList_Create(); + + for (size_t i = 1; i <= loops; i++) { + MetisLruListEntry *entry = (MetisLruListEntry *) metisLruList_NewHeadEntry(lru, (void *) i); + assertTrue(lru->itemsInList == i, "Incorrect list length element %zu, expected %zu got %zu", i, i, lru->itemsInList); + + MetisLruListEntry *test = TAILQ_FIRST(&lru->head); + assertTrue(test == entry, "Head element not new entry, expected %p got %p", (void *) entry, (void *) test); + } + metisLruList_Destroy(&lru); +} + +LONGBOW_TEST_CASE(Global, metisLruList_PopTail) +{ + int loops = 10; + + MetisLruList *lru = metisLruList_Create(); + + for (size_t i = 1; i <= loops; i++) { + metisLruList_NewHeadEntry(lru, (void *) i); + } + + for (size_t i = 1; i <= loops; i++) { + MetisLruListEntry *entry = metisLruList_PopTail(lru); + void *data = metisLruList_EntryGetData(entry); + assertTrue(data == (void *) i, "Got wrong data, expected %p got %p", (void *) i, (void *) data); + + metisLruList_EntryDestroy(&entry); + } + + metisLruList_Destroy(&lru); +} + + +LONGBOW_TEST_CASE(Global, MetisLruList_Length) +{ + int loops = 10; + + MetisLruList *lru = metisLruList_Create(); + + for (size_t i = 1; i <= loops; i++) { + metisLruList_NewHeadEntry(lru, (void *) i); + assertTrue(metisLruList_Length(lru) == i, "Unexpected LruList length"); + } + + metisLruList_Destroy(&lru); +} + +// ============================================================================ + +int +main(int argc, char *argv[]) +{ + LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(metis_LruList); + int exitStatus = longBowMain(argc, argv, testRunner, NULL); + longBowTestRunner_Destroy(&testRunner); + exit(exitStatus); +} diff --git a/metis/ccnx/forwarder/metis/content_store/test/test_metis_TimeOrderedList.c b/metis/ccnx/forwarder/metis/content_store/test/test_metis_TimeOrderedList.c new file mode 100644 index 00000000..c3a7a530 --- /dev/null +++ b/metis/ccnx/forwarder/metis/content_store/test/test_metis_TimeOrderedList.c @@ -0,0 +1,259 @@ +/* + * 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 the file(s) containing the functions to be tested. +// This permits internal static functions to be visible to this Test Runner. + +#include <config.h> +#include <stdlib.h> // for rand() + +#include "../metis_TimeOrderedList.c" + +#include <LongBow/unit-test.h> + +#include <parc/algol/parc_SafeMemory.h> +#include <parc/logging/parc_LogReporterTextStdout.h> + +LONGBOW_TEST_RUNNER(metis_TimeOrderedList) +{ + srand(5150); // A fixed seed for the RNG for consistency. + parcMemory_SetInterface(&PARCSafeMemoryAsPARCMemory); + + LONGBOW_RUN_TEST_FIXTURE(Global); + LONGBOW_RUN_TEST_FIXTURE(Static); +} + +// The Test Runner calls this function once before any Test Fixtures are run. +LONGBOW_TEST_RUNNER_SETUP(metis_TimeOrderedList) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +// The Test Runner calls this function once after all the Test Fixtures are run. +LONGBOW_TEST_RUNNER_TEARDOWN(metis_TimeOrderedList) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE(Global) +{ + LONGBOW_RUN_TEST_CASE(Global, metisTimeOrderedList_CreateRelease); + LONGBOW_RUN_TEST_CASE(Global, metisTimeOrderedList_AcquireRelease); + LONGBOW_RUN_TEST_CASE(Global, metisTimeOrderedList_AddRemove); + LONGBOW_RUN_TEST_CASE(Global, metisTimeOrderedList_GetOldest); + LONGBOW_RUN_TEST_CASE(Global, metisTimeOrderedList_Length); +} + +LONGBOW_TEST_FIXTURE_SETUP(Global) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Global) +{ + uint32_t outstandingAllocations = parcSafeMemory_ReportAllocation(STDERR_FILENO); + if (outstandingAllocations != 0) { + printf("%s leaks memory by %d allocations\n", longBowTestCase_GetName(testCase), outstandingAllocations); + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + +static MetisLogger * +_createLogger() +{ + PARCLogReporter *reporter = parcLogReporterTextStdout_Create(); + MetisLogger *logger = metisLogger_Create(reporter, parcClock_Wallclock()); + parcLogReporter_Release(&reporter); + return logger; +} + +LONGBOW_TEST_CASE(Global, metisTimeOrderedList_CreateRelease) +{ + MetisLogger *logger = _createLogger(); + + MetisTimeOrderedList *list = metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + MetisLruList *lruList = metisLruList_Create(); + MetisMessage *message = metisMessage_CreateFromArray((uint8_t *) "\x00" "ehlo", 5, 111, 2, logger); + + metisMessage_SetRecommendedCacheTimeTicks(message, 100); + metisMessage_SetExpiryTimeTicks(message, 200); + MetisContentStoreEntry *entry = metisContentStoreEntry_Create(message, lruList); + + metisTimeOrderedList_Add(list, entry); + + metisTimeOrderedList_Release(&list); + + metisContentStoreEntry_Release(&entry); + metisMessage_Release(&message); // We must release the message, as it's not acquired by the TimeOrderedList. + metisLruList_Destroy(&lruList); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisTimeOrderedList_AcquireRelease) +{ + MetisTimeOrderedList *list = metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + MetisTimeOrderedList *ref = metisTimeOrderedList_Acquire(list); + + assertTrue(ref == list, "Expected ref and original to be the same"); + + metisTimeOrderedList_Release(&list); + metisTimeOrderedList_Release(&ref); +} + +LONGBOW_TEST_CASE(Global, metisTimeOrderedList_AddRemove) +{ + MetisLogger *logger = _createLogger(); + MetisTimeOrderedList *list = metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + MetisLruList *lruList = metisLruList_Create(); + + size_t numEntries = 100; + MetisContentStoreEntry **contentEntryList = parcMemory_AllocateAndClear(numEntries * sizeof(MetisContentStoreEntry *)); + + for (int i = 1; i <= numEntries; i++) { + MetisMessage *message = metisMessage_CreateFromArray((uint8_t *) "\x00" "ehlo", 5, 111, i, logger); + + metisMessage_SetRecommendedCacheTimeTicks(message, i % 10); // i % 10 will ensure that there are duplicate time entries. + metisMessage_SetExpiryTimeTicks(message, i % 10); + + contentEntryList[i - 1] = metisContentStoreEntry_Create(message, lruList); + metisTimeOrderedList_Add(list, contentEntryList[i - 1]); + + assertTrue(metisTimeOrderedList_Length(list) == i, "Got wrong TimeOrderedList object count"); + } + + for (int i = 1; i <= numEntries; i++) { + MetisContentStoreEntry *contentEntry = contentEntryList[i - 1]; + metisTimeOrderedList_Remove(list, contentEntry); + MetisMessage *message = metisContentStoreEntry_GetMessage(contentEntry); + metisMessage_Release(&message); + + size_t count = metisTimeOrderedList_Length(list); + assertTrue(count == numEntries - i, "Got wrong TimeOrderedList object count"); + metisContentStoreEntry_Release(&contentEntry); + } + + parcMemory_Deallocate((void **) &contentEntryList); + metisTimeOrderedList_Release(&list); + metisLruList_Destroy(&lruList); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisTimeOrderedList_GetOldest) +{ + MetisLogger *logger = _createLogger(); + + // We're going to use the ExpiryTime as the sorting comparison for GetOldest(). + MetisTimeOrderedList *list = metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + + // Add some entries, with randomly ordered ExpiryTimes. + for (int i = 0; i < 100; i++) { + uint64_t time = (uint64_t) rand() + 1; + + MetisMessage *message = metisMessage_CreateFromArray((uint8_t *) "\x00" "ehlo", 5, 111, i, logger); + + metisMessage_SetRecommendedCacheTimeTicks(message, 100); // constant RCT + metisMessage_SetExpiryTimeTicks(message, time); // random expiry time. + + MetisContentStoreEntry *entry = metisContentStoreEntry_Create(message, NULL); + + metisTimeOrderedList_Add(list, entry); + + assertTrue(metisTimeOrderedList_Length(list) == i + 1, "Got wrong TimeOrderedList object count"); + } + + // Ensure that GetOldest() always returns the oldest. + + uint64_t lastTime = 0; + MetisContentStoreEntry *entry = NULL; + while ((entry = metisTimeOrderedList_GetOldest(list)) != NULL) { + MetisMessage *message = metisContentStoreEntry_GetMessage(entry); + uint64_t messageTime = metisMessage_GetExpiryTimeTicks(message); + + // We should always retrieve a time later than the previous time we retrieved. + assertTrue(messageTime > lastTime, "Received out of order message"); + + lastTime = messageTime; + metisTimeOrderedList_Remove(list, entry); + metisMessage_Release(&message); + metisContentStoreEntry_Release(&entry); + } + + metisTimeOrderedList_Release(&list); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_CASE(Global, metisTimeOrderedList_Length) +{ + MetisLogger *logger = _createLogger(); + + MetisTimeOrderedList *list = metisTimeOrderedList_Create((MetisTimeOrderList_KeyCompare *) metisContentStoreEntry_CompareExpiryTime); + + // Add some entries with duplicate times to make sure that duplicate time stamps work. + uint64_t times[] = { 1, 2, 3, 100, 100, 100, 4, 4, 3, 2, 1, 5, 6, 7, 8, 9 }; + size_t numEntriesToMake = sizeof(times) / sizeof(uint64_t); + + for (int i = 0; i < numEntriesToMake; i++) { + MetisMessage *message = metisMessage_CreateFromArray((uint8_t *) "\x00" "ehlo", 5, 111, times[i], logger); + metisMessage_SetExpiryTimeTicks(message, times[i]); + MetisContentStoreEntry *entry = metisContentStoreEntry_Create(message, NULL); + metisTimeOrderedList_Add(list, entry); + assertTrue(metisTimeOrderedList_Length(list) == i + 1, "Got wrong TimeOrderedList object count"); + } + + // Clean up the messages we allocated. + int i = 0; + MetisContentStoreEntry *entry = NULL; + while ((entry = metisTimeOrderedList_GetOldest(list)) != NULL) { + assertTrue(metisTimeOrderedList_Length(list) == numEntriesToMake - i, "Got wrong TimeOrderedList object count"); + + MetisMessage *message = metisContentStoreEntry_GetMessage(entry); + metisTimeOrderedList_Remove(list, entry); + metisMessage_Release(&message); + metisContentStoreEntry_Release(&entry); + i++; + } + + metisTimeOrderedList_Release(&list); + metisLogger_Release(&logger); +} + +LONGBOW_TEST_FIXTURE(Static) +{ +} + +LONGBOW_TEST_FIXTURE_SETUP(Static) +{ + return LONGBOW_STATUS_SUCCEEDED; +} + +LONGBOW_TEST_FIXTURE_TEARDOWN(Static) +{ + if (parcSafeMemory_ReportAllocation(STDOUT_FILENO) != 0) { + return LONGBOW_STATUS_MEMORYLEAK; + } + return LONGBOW_STATUS_SUCCEEDED; +} + +int +main(int argc, char *argv[]) +{ + LongBowRunner *testRunner = LONGBOW_TEST_RUNNER_CREATE(metis_TimeOrderedList); + int exitStatus = longBowMain(argc, argv, testRunner, NULL); + longBowTestRunner_Destroy(&testRunner); + exit(exitStatus); +} + |