/*

 * 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;

}