/*

 * 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/cachedChapterIndex.h#3 $

 */

#ifndef CACHED_CHAPTER_INDEX_H

#define CACHED_CHAPTER_INDEX_H

#include "chapterIndex.h"

#include "common.h"

#include "compiler.h"

#include "cpu.h"

#include "geometry.h"

#include "indexPageMap.h"

#include "typeDefs.h"

#include "volume.h"

#include "volumeStore.h"

/**

 * These counters are essentially fields of the CachedChapterIndex, but are

 * segregated into this structure because they are frequently modified. They

 * are grouped and aligned to keep them on different cache lines from the

 * chapter fields that are accessed far more often than they are updated.

 **/

struct __attribute__((aligned(CACHE_LINE_BYTES))) cachedIndexCounters {

  /** the total number of search hits since this chapter was cached */

  uint64_t searchHits;

  /** the total number of search misses since this chapter was cached */

  uint64_t searchMisses;

  /** the number of consecutive search misses since the last cache hit */

  uint64_t consecutiveMisses;

};

typedef struct cachedIndexCounters CachedIndexCounters;

/**

 * CachedChapterIndex is the structure for a cache entry, representing a

 * single cached chapter index in the sparse chapter index cache.

 **/

struct __attribute__((aligned(CACHE_LINE_BYTES))) cachedChapterIndex {

  /*

   * The virtual chapter number of the cached chapter index. UINT64_MAX means

   * this cache entry is unused. Must only be modified in the critical section

   * in updateSparseCache().

   */

  uint64_t          virtualChapter;

  /* The number of index pages in a chapter */

  unsigned int      indexPagesCount;

  /*

   * This flag is mutable between cache updates, but it rarely changes and

   * is frequently accessed, so it groups with the immutable fields.

   *

   * If set, skip the chapter when searching the entire cache.  This flag is

   * just a performance optimization.  If we do not see a recent change to it,

   * it will be corrected when we pass through a memory barrier while getting

   * the next request from the queue.  So we may do one extra search of the

   * chapter index, or miss one deduplication opportunity.

   */

  bool              skipSearch;

  // These pointers are immutable during the life of the cache. The contents

  // of the arrays change when the cache entry is replaced.

  /* pointer to a cache-aligned array of ChapterIndexPages */

  DeltaIndexPage *indexPages;

  /* pointer to an array of VolumePages containing the index pages */

  struct volume_page *volumePages;

  // The cache-aligned counters change often and are placed at the end of the

  // structure to prevent false sharing with the more stable fields above.

  /* counter values updated by the thread servicing zone zero */

  CachedIndexCounters counters;

};

typedef struct cachedChapterIndex CachedChapterIndex;

/**

 * Initialize a CachedChapterIndex, allocating the memory for the array of

 * ChapterIndexPages and the raw index page data. The chapter index will be

 * marked as unused (virtualChapter == UINT64_MAX).

 *

 * @param chapter   the chapter index cache entry to initialize

 * @param geometry  the geometry governing the volume

 **/

int initializeCachedChapterIndex(CachedChapterIndex *chapter,

                                 const Geometry     *geometry)

  __attribute__((warn_unused_result));

/**

 * Destroy a CachedChapterIndex, freeing the memory allocated for the

 * ChapterIndexPages and raw index page data.

 *

 * @param chapter   the chapter index cache entry to destroy

 **/

void destroyCachedChapterIndex(CachedChapterIndex *chapter);

/**

 * Assign a new value to the skipSearch flag of a cached chapter index.

 *

 * @param chapter     the chapter index cache entry to modify

 * @param skipSearch  the new value of the skipSearch falg

 **/

static INLINE void setSkipSearch(CachedChapterIndex *chapter, bool skipSearch)

{

  // Explicitly check if the field is set so we don't keep dirtying the memory

  // cache line on continued search hits.

  if (READ_ONCE(chapter->skipSearch) != skipSearch) {

    WRITE_ONCE(chapter->skipSearch, skipSearch);

  }

}

/**

 * Check if a cached sparse chapter index should be skipped over in the search

 * for a chunk name. Filters out unused, invalid, disabled, and irrelevant

 * cache entries.

 *

 * @param zone            the zone doing the check

 * @param chapter         the cache entry search candidate

 * @param virtualChapter  the virtualChapter containing a hook, or UINT64_MAX

 *                        if searching the whole cache for a non-hook

 *

 * @return true if the provided chapter index should be skipped

 **/

static INLINE bool shouldSkipChapterIndex(const IndexZone *zone,

                                          const CachedChapterIndex *chapter,

                                          uint64_t virtualChapter)

{

  // Don't search unused entries (contents undefined) or invalid entries

  // (the chapter is no longer the zone's view of the volume).

  if ((chapter->virtualChapter == UINT64_MAX)

      || (chapter->virtualChapter < zone->oldestVirtualChapter)) {

    return true;

  }

  if (virtualChapter != UINT64_MAX) {

    // If the caller specified a virtual chapter, only search the cache

    // entry containing that chapter.

    return (virtualChapter != chapter->virtualChapter);

  } else {

    // When searching the entire cache, save time by skipping over chapters

    // that have had too many consecutive misses.

    return READ_ONCE(chapter->skipSearch);

  }

}

/**

 * Cache a chapter index, reading all the index pages from the volume and

 * initializing the array of ChapterIndexPages in the cache entry to represent

 * them. The virtualChapter field of the cache entry will be set to UINT64_MAX

 * if there is any error since the remaining mutable fields will be in an

 * undefined state.

 *

 * @param chapter         the chapter index cache entry to replace

 * @param virtualChapter  the virtual chapter number of the index to read

 * @param volume          the volume containing the chapter index

 *

 * @return UDS_SUCCESS or an error code

 **/

int cacheChapterIndex(CachedChapterIndex *chapter,

                      uint64_t            virtualChapter,

                      const Volume       *volume)

  __attribute__((warn_unused_result));

/**

 * Search a single cached sparse chapter index for a chunk name, returning the

 * record page number that may contain the name.

 *

 * @param [in]  chapter        the cache entry for the chapter to search

 * @param [in]  geometry       the geometry governing the volume

 * @param [in]  indexPageMap   the index page number map for the volume

 * @param [in]  name           the chunk name to search for

 * @param [out] recordPagePtr  the record page number of a match, else

 *                             NO_CHAPTER_INDEX_ENTRY if nothing matched

 *

 * @return UDS_SUCCESS or an error code

 **/

int searchCachedChapterIndex(CachedChapterIndex *chapter,

                             const Geometry     *geometry,

                             const IndexPageMap *indexPageMap,

                             const UdsChunkName *name,

                             int                *recordPagePtr)

  __attribute__((warn_unused_result));

#endif /* CACHED_CHAPTER_INDEX_H */