/*
* 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/searchList.h#1 $
*/
#ifndef SEARCH_LIST_H
#define SEARCH_LIST_H
#include "cachedChapterIndex.h"
#include "compiler.h"
#include "stringUtils.h"
#include "typeDefs.h"
/**
* A SearchList represents the permutations of the sparse chapter index cache
* entry array. Those permutations express an ordering on the chapter indexes,
* from most recently accessed to least recently accessed, which is the order
* in which the indexes should be searched and the reverse order in which they
* should be evicted from the cache (LRU cache replacement policy).
*
* Cache entries that are dead (virtualChapter == UINT64_MAX) are kept as a
* suffix of the list, avoiding the need to even iterate over them to search,
* and ensuring that dead entries are replaced before any live entries are
* evicted.
*
* The search list is intended to be instantated for each zone thread,
* avoiding any need for synchronization. The structure is allocated on a
* cache boundary to avoid false sharing of memory cache lines between zone
* threads.
**/
typedef struct searchList {
/** The number of cached chapter indexes and search list entries */
uint8_t capacity;
/** The index in the entries array of the first dead cache entry */
uint8_t firstDeadEntry;
/** The chapter array indexes representing the chapter search order */
uint8_t entries[];
} SearchList;
/**
* SearchListIterator captures the fields needed to iterate over the live
* entries in a search list and return the CachedChapterIndex pointers that
* the search code actually wants to deal with.
**/
typedef struct {
/** The search list defining the chapter search iteration order */
SearchList *list;
/** The index of the next entry to return from the search list */
unsigned int nextEntry;
/** The cached chapters that are referenced by the search list */
CachedChapterIndex *chapters;
} SearchListIterator;
/**
* Allocate and initialize a new chapter cache search list with the same
* capacity as the cache. The index of each entry in the cache will appear
* exactly once in the array. All the chapters in the cache are assumed to be
* initially dead, so firstDeadEntry will be zero and no chapters will be
* returned when the search list is iterated.
*
* @param [in] capacity the number of entries in the search list
* @param [out] listPtr a pointer in which to return the new search list
**/
int makeSearchList(unsigned int capacity,
SearchList **listPtr)
__attribute__((warn_unused_result));
/**
* Free a search list and null out the reference to it.
*
* @param listPtr the reference to the search list to free
**/
void freeSearchList(SearchList **listPtr);
/**
* Copy the contents of one search list to another.
*
* @param source the list to copy
* @param target the list to replace
**/
static INLINE void copySearchList(const SearchList *source,
SearchList *target)
{
*target = *source;
memcpy(target->entries, source->entries, source->capacity);
}
/**
* Prepare to iterate over the live cache entries a search list.
*
* @param list the list defining the live chapters and the search order
* @param chapters the chapter index entries to return from getNextChapter()
*
* @return an iterator positioned at the start of the search list
**/
static INLINE SearchListIterator
iterateSearchList(SearchList *list, CachedChapterIndex chapters[])
{
SearchListIterator iterator = {
.list = list,
.nextEntry = 0,
.chapters = chapters,
};
return iterator;
}
/**
* Check if the search list iterator has another entry to return.
*
* @param iterator the search list iterator
*
* @return <code>true</code> if getNextChapter() may be called
**/
static INLINE bool hasNextChapter(const SearchListIterator *iterator)
{
return (iterator->nextEntry < iterator->list->firstDeadEntry);
}
/**
* Return a pointer to the next live chapter in the search list iteration and
* advance the iterator. This must only be called when hasNextChapter()
* returns <code>true</code>.
*
* @param iterator the search list iterator
*
* @return a pointer to the next live chapter index in the search list order
**/
static INLINE CachedChapterIndex *getNextChapter(SearchListIterator *iterator)
{
return &iterator->chapters[iterator->list->entries[iterator->nextEntry++]];
}
/**
* Rotate the pointers in a prefix of a search list downwards by one item,
* pushing elements deeper into the list and moving a new chapter to the start
* of the search list. This is the "make most recent" operation on the search
* list.
*
* If the search list provided is <code>[ 0 1 2 3 4 ]</code> and the prefix
* length is <code>4</code>, then <code>3</code> is being moved to the front.
* The search list after the call will be <code>[ 3 0 1 2 4 ]</code> and the
* function will return <code>3</code>.
*
* @param searchList the chapter index search list to rotate
* @param prefixLength the length of the prefix of the list to rotate
*
* @return the array index of the chapter cache entry that is now at the front
* of the search list
**/
static INLINE uint8_t rotateSearchList(SearchList *searchList,
uint8_t prefixLength)
{
// Grab the value of the last entry in the list prefix.
uint8_t mostRecent = searchList->entries[prefixLength - 1];
if (prefixLength > 1) {
// Push the first N-1 entries down by one entry, overwriting the entry
// we just grabbed.
memmove(&searchList->entries[1],
&searchList->entries[0],
prefixLength - 1);
// We now have a hole at the front of the list in which we can place the
// rotated entry.
searchList->entries[0] = mostRecent;
}
// This function is also used to move a dead chapter to the front of the
// list, in which case the suffix of dead chapters was pushed down too.
if (searchList->firstDeadEntry < prefixLength) {
searchList->firstDeadEntry += 1;
}
return mostRecent;
}
/**
* Purge invalid cache entries, marking them as dead and moving them to the
* end of the search list, then push any chapters that have skipSearch set
* down so they follow all the remaining live, valid chapters in the search
* list. This effectively sorts the search list into three regions--active,
* skippable, and dead--while maintaining the LRU ordering that already
* existed (a stable sort).
*
* This operation must only be called during the critical section in
* updateSparseCache() since it effectively changes cache membership.
*
* @param searchList the chapter index search list to purge
* @param chapters the chapter index cache entries
* @param oldestVirtualChapter the oldest virtual chapter
**/
void purgeSearchList(SearchList *searchList,
const CachedChapterIndex chapters[],
uint64_t oldestVirtualChapter);
#endif /* SEARCH_LIST_H */