/* * Copyright (c) 2020 Red Hat, Inc. * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License * as published by the Free Software Foundation; either version 2 * of the License, or (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA * 02110-1301, USA. * * $Id: //eng/uds-releases/jasper/src/uds/sparseCache.c#3 $ */ /** * The sparse chapter index cache is implemented as a simple array of cache * entries. Since the cache is small (seven chapters by default), searching * for a specific virtual chapter is implemented as a linear search. The cache * replacement policy is least-recently-used (LRU). Again, size of the cache * allows the LRU order to be maintained by shifting entries in an array list. * * The most important property of this cache is the absence of synchronization * for read operations. Safe concurrent access to the cache by the zone * threads is controlled by the triage queue and the barrier requests it * issues to the zone queues. The set of cached chapters does not and must not * change between the carefully coordinated calls to updateSparseCache() from * the zone threads. * * The critical invariant for that coordination is the cache membership must * not change between those updates; the calls to sparseCacheContains() from * the zone threads must all receive the same results for any virtual chapter * number. To ensure that critical invariant, state changes such as "that * virtual chapter is no longer in the volume" and "skip searching that * chapter because it has had too many cache misses" are represented * separately from the cache membership information (the virtual chapter * number). * * As a result of this invariant, we have the guarantee that every zone thread * will call updateSparseCache() once and exactly once to request a chapter * that is not in the cache, and the serialization of the barrier requests * from the triage queue ensures they will all request the same chapter * number. This means the only synchronization we need can be provided by a * pair of thread barriers used only in the updateSparseCache() call, * providing a critical section where a single zone thread can drive the cache * update while all the other zone threads are known to be blocked, waiting in * the second barrier. Outside that critical section, all the zone threads * implicitly hold a shared lock. Inside it, the "captain" (the thread that * was uniquely flagged when passing through the first barrier) holds an * exclusive lock. No other threads may access or modify the cache, except for * accessing cache statistics and similar queries. * * Cache statistics must only be modified by a single thread, conventionally * the zone zero thread. All fields that might be frequently updated by that * thread are kept in separate cache-aligned structures so they will not cause * cache contention via "false sharing" with the fields that are frequently * accessed by all of the zone threads. * * LRU order is kept independently by each zone thread, and each zone uses its * own list for searching and cache membership queries. The zone zero list is * used to decide which chapter to evict when the cache is updated, and its * search list is copied to the other threads at that time. * * The virtual chapter number field of the cache entry is the single field * indicating whether a chapter is a member of the cache or not. The value * UINT64_MAX is used to represent a null, undefined, or wildcard * chapter number. When present in the virtual chapter number field * CachedChapterIndex, it indicates that the cache entry is dead, and all * the other fields of that entry (other than immutable pointers to cache * memory) are undefined and irrelevant. Any cache entry that is not marked as * dead is fully defined and a member of the cache--sparseCacheContains() * must always return true for any virtual chapter number that appears in any * of the cache entries. * * A chapter index that is a member of the cache may be marked for different * treatment (disabling search) between calls to updateSparseCache() in two * different ways. When a chapter falls off the end of the volume, its virtual * chapter number will be less that the oldest virtual chapter number. Since * that chapter is no longer part of the volume, there's no point in continuing * to search that chapter index. Once invalidated, that virtual chapter will * still be considered a member of the cache, but it will no longer be searched * for matching chunk names. * * The second mechanism for disabling search is the heuristic based on keeping * track of the number of consecutive search misses in a given chapter index. * Once that count exceeds a threshold, the skipSearch flag will be set to * true, causing the chapter to be skipped in the fallback search of the * entire cache, but still allowing it to be found when searching for a hook * in that specific chapter. Finding a hook will clear the skipSearch flag, * once again allowing the non-hook searches to use the cache entry. Again, * regardless of the state of the skipSearch flag, the virtual chapter must * still considered to be a member of the cache for sparseCacheContains(). * * Barrier requests and the sparse chapter index cache are also described in * * https://intranet.permabit.com/wiki/Chapter_Index_Cache_supports_concurrent_access * * and in a message to the albireo mailing list on 5/28/2011 titled "true * barriers with a hook resolution queue". **/ #include "sparseCache.h" #include "cachedChapterIndex.h" #include "chapterIndex.h" #include "common.h" #include "index.h" #include "logger.h" #include "memoryAlloc.h" #include "permassert.h" #include "searchList.h" #include "threads.h" #include "zone.h" enum { /** The number of consecutive search misses that will disable searching */ SKIP_SEARCH_THRESHOLD = 20000, /** a named constant to use when identifying zone zero */ ZONE_ZERO = 0 }; /** * These counter values are essentially fields of the SparseCache, but are * segregated into this structure because they are frequently modified. We * group them and align them to keep them on different cache lines from the * cache fields that are accessed far more often than they are updated. **/ typedef struct __attribute__((aligned(CACHE_LINE_BYTES))) sparseCacheCounters { /** the total number of virtual chapter probes that succeeded */ uint64_t chapterHits; /** the total number of virtual chapter probes that failed */ uint64_t chapterMisses; /** the total number of cache searches that found a possible match */ uint64_t searchHits; /** the total number of cache searches that found no matches */ uint64_t searchMisses; /** the number of cache entries that fell off the end of the volume */ uint64_t invalidations; /** the number of cache entries that were evicted while still valid */ uint64_t evictions; } SparseCacheCounters; /** * This is the private structure definition of a SparseCache. **/ struct sparseCache { /** the number of cache entries, which is the size of the chapters array */ unsigned int capacity; /** the number of zone threads using the cache */ unsigned int zoneCount; /** the geometry governing the volume */ const Geometry *geometry; /** the number of search misses in zone zero that will disable searching */ unsigned int skipSearchThreshold; /** pointers to the cache-aligned chapter search order for each zone */ SearchList *searchLists[MAX_ZONES]; /** the thread barriers used to synchronize the zone threads for update */ Barrier beginCacheUpdate; Barrier endCacheUpdate; /** frequently-updated counter fields (cache-aligned) */ SparseCacheCounters counters; /** the counted array of chapter index cache entries (cache-aligned) */ CachedChapterIndex chapters[]; }; /** * Initialize a sparse chapter index cache. * * @param cache the sparse cache to initialize * @param geometry the geometry governing the volume * @param capacity the number of chapters the cache will hold * @param zoneCount the number of zone threads using the cache * * @return UDS_SUCCESS or an error code **/ __attribute__((warn_unused_result)) static int initializeSparseCache(SparseCache *cache, const Geometry *geometry, unsigned int capacity, unsigned int zoneCount) { cache->geometry = geometry; cache->capacity = capacity; cache->zoneCount = zoneCount; // Scale down the skip threshold by the number of zones since we count the // chapter search misses only in zone zero. cache->skipSearchThreshold = (SKIP_SEARCH_THRESHOLD / zoneCount); int result = initializeBarrier(&cache->beginCacheUpdate, zoneCount); if (result != UDS_SUCCESS) { return result; } result = initializeBarrier(&cache->endCacheUpdate, zoneCount); if (result != UDS_SUCCESS) { return result; } unsigned int i; for (i = 0; i < capacity; i++) { result = initializeCachedChapterIndex(&cache->chapters[i], geometry); if (result != UDS_SUCCESS) { return result; } } // Allocate each zone's independent LRU order. for (i = 0; i < zoneCount; i++) { result = makeSearchList(capacity, &cache->searchLists[i]); if (result != UDS_SUCCESS) { return result; } } return UDS_SUCCESS; } /**********************************************************************/ int makeSparseCache(const Geometry *geometry, unsigned int capacity, unsigned int zoneCount, SparseCache **cachePtr) { unsigned int bytes = (sizeof(SparseCache) + (capacity * sizeof(CachedChapterIndex))); SparseCache *cache; int result = allocateCacheAligned(bytes, "sparse cache", &cache); if (result != UDS_SUCCESS) { return result; } result = initializeSparseCache(cache, geometry, capacity, zoneCount); if (result != UDS_SUCCESS) { freeSparseCache(cache); return result; } *cachePtr = cache; return UDS_SUCCESS; } /**********************************************************************/ size_t getSparseCacheMemorySize(const SparseCache *cache) { // Count the DeltaIndexPage as cache memory, but ignore all other overhead. size_t pageSize = (sizeof(DeltaIndexPage) + cache->geometry->bytesPerPage); size_t chapterSize = (pageSize * cache->geometry->indexPagesPerChapter); return (cache->capacity * chapterSize); } /** * Update counters to reflect a chapter access hit and clear the skipSearch * flag on the chapter, if set. * * @param cache the cache to update * @param chapter the cache entry to update **/ static void scoreChapterHit(SparseCache *cache, CachedChapterIndex *chapter) { cache->counters.chapterHits += 1; setSkipSearch(chapter, false); } /** * Update counters to reflect a chapter access miss. * * @param cache the cache to update **/ static void scoreChapterMiss(SparseCache *cache) { cache->counters.chapterMisses += 1; } /** * Check if the cache entry that is about to be replaced is already dead, and * if it's not, add to tally of evicted or invalidated cache entries. * * @param zone the zone used to find the oldest chapter * @param cache the cache to update * @param chapter the cache entry about to be replaced **/ static void scoreEviction(IndexZone *zone, SparseCache *cache, CachedChapterIndex *chapter) { if (chapter->virtualChapter == UINT64_MAX) { return; } if (chapter->virtualChapter < zone->oldestVirtualChapter) { cache->counters.invalidations += 1; } else { cache->counters.evictions += 1; } } /** * Update counters to reflect a cache search hit. This bumps the hit * count, clears the miss count, and clears the skipSearch flag. * * @param cache the cache to update * @param chapter the cache entry to update **/ static void scoreSearchHit(SparseCache *cache, CachedChapterIndex *chapter) { cache->counters.searchHits += 1; chapter->counters.searchHits += 1; chapter->counters.consecutiveMisses = 0; setSkipSearch(chapter, false); } /** * Update counters to reflect a cache search miss. This bumps the consecutive * miss count, and if it goes over skipSearchThreshold, sets the skipSearch * flag on the chapter. * * @param cache the cache to update * @param chapter the cache entry to update **/ static void scoreSearchMiss(SparseCache *cache, CachedChapterIndex *chapter) { cache->counters.searchMisses += 1; chapter->counters.searchMisses += 1; chapter->counters.consecutiveMisses += 1; if (chapter->counters.consecutiveMisses > cache->skipSearchThreshold) { setSkipSearch(chapter, true); } } /**********************************************************************/ void freeSparseCache(SparseCache *cache) { if (cache == NULL) { return; } unsigned int i; for (i = 0; i < cache->zoneCount; i++) { freeSearchList(&cache->searchLists[i]); } for (i = 0; i < cache->capacity; i++) { CachedChapterIndex *chapter = &cache->chapters[i]; destroyCachedChapterIndex(chapter); } destroyBarrier(&cache->beginCacheUpdate); destroyBarrier(&cache->endCacheUpdate); FREE(cache); } /**********************************************************************/ bool sparseCacheContains(SparseCache *cache, uint64_t virtualChapter, unsigned int zoneNumber) { /* * The correctness of the barriers depends on the invariant that between * calls to updateSparseCache(), the answers this function returns must * never vary--the result for a given chapter must be identical across * zones. That invariant must be maintained even if the chapter falls off * the end of the volume, or if searching it is disabled because of too many * search misses. */ // Get the chapter search order for this zone thread. SearchListIterator iterator = iterateSearchList(cache->searchLists[zoneNumber], cache->chapters); while (hasNextChapter(&iterator)) { CachedChapterIndex *chapter = getNextChapter(&iterator); if (virtualChapter == chapter->virtualChapter) { if (zoneNumber == ZONE_ZERO) { scoreChapterHit(cache, chapter); } // Move the chapter to the front of the search list. rotateSearchList(iterator.list, iterator.nextEntry); return true; } } // The specified virtual chapter isn't cached. if (zoneNumber == ZONE_ZERO) { scoreChapterMiss(cache); } return false; } /**********************************************************************/ int updateSparseCache(IndexZone *zone, uint64_t virtualChapter) { const Index *index = zone->index; SparseCache *cache = index->volume->sparseCache; // If the chapter is already in the cache, we don't need to do a thing // except update the search list order, which this check does. if (sparseCacheContains(cache, virtualChapter, zone->id)) { return UDS_SUCCESS; } // Wait for every zone thread to have reached its corresponding barrier // request and invoked this function before starting to modify the cache. enterBarrier(&cache->beginCacheUpdate, NULL); /* * This is the start of the critical section: the zone zero thread is * captain, effectively holding an exclusive lock on the sparse cache. All * the other zone threads must do nothing between the two barriers. They * will wait at the endCacheUpdate barrier for the captain to finish the * update. */ int result = UDS_SUCCESS; if (zone->id == ZONE_ZERO) { // Purge invalid chapters from the LRU search list. SearchList *zoneZeroList = cache->searchLists[ZONE_ZERO]; purgeSearchList(zoneZeroList, cache->chapters, zone->oldestVirtualChapter); // First check that the desired chapter is still in the volume. If it's // not, the hook fell out of the index and there's nothing to do for it. if (virtualChapter >= index->oldestVirtualChapter) { // Evict the least recently used live chapter, or replace a dead cache // entry, all by rotating the the last list entry to the front. CachedChapterIndex *victim = &cache->chapters[rotateSearchList(zoneZeroList, cache->capacity)]; // Check if the victim is already dead, and if it's not, add to the // tally of evicted or invalidated cache entries. scoreEviction(zone, cache, victim); // Read the index page bytes and initialize the page array. result = cacheChapterIndex(victim, virtualChapter, index->volume); } // Copy the new search list state to all the other zone threads so they'll // get the result of pruning and see the new chapter. unsigned int z; for (z = 1; z < cache->zoneCount; z++) { copySearchList(zoneZeroList, cache->searchLists[z]); } } // This is the end of the critical section. All cache invariants must have // been restored--it will be shared/read-only again beyond the barrier. enterBarrier(&cache->endCacheUpdate, NULL); return result; } /**********************************************************************/ int searchSparseCache(IndexZone *zone, const UdsChunkName *name, uint64_t *virtualChapterPtr, int *recordPagePtr) { Volume *volume = zone->index->volume; SparseCache *cache = volume->sparseCache; unsigned int zoneNumber = zone->id; // If the caller did not specify a virtual chapter, search the entire cache. bool searchAll = (*virtualChapterPtr == UINT64_MAX); unsigned int chaptersSearched = 0; // Get the chapter search order for this zone thread, searching the chapters // from most recently hit to least recently hit. SearchListIterator iterator = iterateSearchList(cache->searchLists[zoneNumber], cache->chapters); while (hasNextChapter(&iterator)) { CachedChapterIndex *chapter = getNextChapter(&iterator); // Skip chapters no longer cached, or that have too many search misses. if (shouldSkipChapterIndex(zone, chapter, *virtualChapterPtr)) { continue; } int result = searchCachedChapterIndex(chapter, cache->geometry, volume->indexPageMap, name, recordPagePtr); if (result != UDS_SUCCESS) { return result; } chaptersSearched += 1; // Did we find an index entry for the name? if (*recordPagePtr != NO_CHAPTER_INDEX_ENTRY) { if (zoneNumber == ZONE_ZERO) { scoreSearchHit(cache, chapter); } // Move the chapter to the front of the search list. rotateSearchList(iterator.list, iterator.nextEntry); // Return a matching entry as soon as it is found. It might be a false // collision that has a true match in another chapter, but that's a very // rare case and not worth the extra search cost or complexity. *virtualChapterPtr = chapter->virtualChapter; return UDS_SUCCESS; } if (zoneNumber == ZONE_ZERO) { scoreSearchMiss(cache, chapter); } if (!searchAll) { // We just searched the virtual chapter the caller specified and there // was no match, so we're done. break; } } // The name was not found in the cache. *recordPagePtr = NO_CHAPTER_INDEX_ENTRY; return UDS_SUCCESS; }