/*
* 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 <code>true</code> 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 */