/*
* 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/deltaIndex.h#4 $
*/
#ifndef DELTAINDEX_H
#define DELTAINDEX_H 1
#include "compiler.h"
#include "deltaMemory.h"
enum {
// the number of extra bytes and bits needed to store a collision entry
COLLISION_BYTES = UDS_CHUNK_NAME_SIZE,
COLLISION_BITS = COLLISION_BYTES * CHAR_BIT
};
typedef struct deltaIndex {
DeltaMemory *deltaZones; // The zones
unsigned int numZones; // The number of zones
unsigned int numLists; // The number of delta lists
unsigned int listsPerZone; // Lists per zone (last zone can be smaller)
bool isMutable; // True if this index is mutable
byte tag; // Tag belonging to this delta index
} DeltaIndex;
/*
* A DeltaIndexPage describes a single page of a chapter index. The deltaIndex
* field allows the page to be treated as an immutable DeltaIndex. We use the
* deltaMemory field to treat the chapter index page as a single zone index,
* and without the need to do an additional memory allocation.
*/
typedef struct deltaIndexPage {
DeltaIndex deltaIndex;
// These values are loaded from the DeltaPageHeader
unsigned int lowestListNumber;
unsigned int highestListNumber;
uint64_t virtualChapterNumber;
// This structure describes the single zone of a delta index page.
DeltaMemory deltaMemory;
} DeltaIndexPage;
/*
* Notes on the DeltaIndexEntries:
*
* The fields documented as "public" can be read by any code that uses a
* DeltaIndex. The fields documented as "private" carry information
* between DeltaIndex method calls and should not be used outside the
* DeltaIndex module.
*
* (1) The DeltaIndexEntry is used like an iterator when searching a delta
* list.
*
* (2) And it is also the result of a successful search and can be used to
* refer to the element found by the search.
*
* (3) And it is also the result of an unsuccessful search and can be used
* to refer to the insertion point for a new record.
*
* (4) If atEnd==true, the DeltaListEntry can only be used as the insertion
* point for a new record at the end of the list.
*
* (5) If atEnd==false and isCollision==true, the DeltaListEntry fields
* refer to a collision entry in the list, and the DeltaListEntry can
* be used a a reference to this entry.
*
* (6) If atEnd==false and isCollision==false, the DeltaListEntry fields
* refer to a non-collision entry in the list. Such DeltaListEntries
* can be used as a reference to a found entry, or an insertion point
* for a non-collision entry before this entry, or an insertion point
* for a collision entry that collides with this entry.
*/
typedef struct deltaIndexEntry {
// Public fields
unsigned int key; // The key for this entry
bool atEnd; // We are after the last entry in the list
bool isCollision; // This record is a collision
// Private fields (but DeltaIndex_t1 cheats and looks at them)
bool listOverflow; // This delta list overflowed
unsigned short valueBits; // The number of bits used for the value
unsigned short entryBits; // The number of bits used for the entire entry
DeltaMemory *deltaZone; // The delta index zone
DeltaList *deltaList; // The delta list containing the entry,
unsigned int listNumber; // The delta list number
uint32_t offset; // Bit offset of this entry within the list
unsigned int delta; // The delta between this and previous entry
DeltaList tempDeltaList; // Temporary delta list for immutable indices
} DeltaIndexEntry;
typedef struct {
size_t memoryAllocated; // Number of bytes allocated
RelTime rebalanceTime; // The time spent rebalancing
int rebalanceCount; // Number of memory rebalances
long recordCount; // The number of records in the index
long collisionCount; // The number of collision records
long discardCount; // The number of records removed
long overflowCount; // The number of UDS_OVERFLOWs detected
unsigned int numLists; // The number of delta lists
} DeltaIndexStats;
/**
* Initialize a delta index.
*
* @param deltaIndex The delta index to initialize
* @param numZones The number of zones in the index
* @param numLists The number of delta lists in the index
* @param meanDelta The mean delta value
* @param numPayloadBits The number of bits in the payload or value
* @param memorySize The number of bytes in memory for the index
*
* @return error code or UDS_SUCCESS
**/
int initializeDeltaIndex(DeltaIndex *deltaIndex, unsigned int numZones,
unsigned int numLists, unsigned int meanDelta,
unsigned int numPayloadBits, size_t memorySize)
__attribute__((warn_unused_result));
/**
* Initialize an immutable delta index page.
*
* @param deltaIndexPage The delta index page to initialize
* @param expectedNonce If non-zero, the expected nonce.
* @param meanDelta The mean delta value
* @param numPayloadBits The number of bits in the payload or value
* @param memory The memory page
* @param memSize The size of the memory page
*
* @return error code or UDS_SUCCESS
**/
int initializeDeltaIndexPage(DeltaIndexPage *deltaIndexPage,
uint64_t expectedNonce,
unsigned int meanDelta,
unsigned int numPayloadBits,
byte *memory,
size_t memSize)
__attribute__((warn_unused_result));
/**
* Uninitialize a delta index.
*
* @param deltaIndex The delta index to uninitialize
**/
void uninitializeDeltaIndex(DeltaIndex *deltaIndex);
/**
* Empty the delta index.
*
* @param deltaIndex The delta index being emptied.
**/
void emptyDeltaIndex(const DeltaIndex *deltaIndex);
/**
* Empty a zone of the delta index.
*
* @param deltaIndex The delta index
* @param zoneNumber The zone being emptied
**/
void emptyDeltaIndexZone(const DeltaIndex *deltaIndex,
unsigned int zoneNumber);
/**
* Pack delta lists from a mutable delta index into an immutable delta index
* page. A range of delta lists (starting with a specified list index) is
* copied from the mutable delta index into a memory page used in the immutable
* index. The number of lists copied onto the page is returned to the caller.
*
* @param deltaIndex The delta index being converted
* @param headerNonce The header nonce to store
* @param headerNativeEndian If true, write native endian header
* @param memory The memory page to use
* @param memSize The size of the memory page
* @param virtualChapterNumber The virtual chapter number
* @param firstList The first delta list number to be copied
* @param numLists The number of delta lists that were copied
*
* @return error code or UDS_SUCCESS. On UDS_SUCCESS, the numLists
* argument contains the number of lists copied.
**/
int packDeltaIndexPage(const DeltaIndex *deltaIndex,
uint64_t headerNonce,
bool headerNativeEndian,
byte *memory,
size_t memSize,
uint64_t virtualChapterNumber,
unsigned int firstList,
unsigned int *numLists)
__attribute__((warn_unused_result));
/**
* Set the tag value used when saving and/or restoring a delta index.
*
* @param deltaIndex The delta index
* @param tag The tag value
**/
void setDeltaIndexTag(DeltaIndex *deltaIndex, byte tag);
/**
* Start restoring a delta index from an input stream.
*
* @param deltaIndex The delta index to read into
* @param bufferedReaders The buffered readers to read the delta index from
* @param numReaders The number of buffered readers
*
* @return UDS_SUCCESS on success, or an error code on failure
**/
int startRestoringDeltaIndex(const DeltaIndex *deltaIndex,
BufferedReader **bufferedReaders, int numReaders)
__attribute__((warn_unused_result));
/**
* Have all the data been read while restoring a delta index from an
* input stream?
*
* @param deltaIndex The delta index
*
* @return true if all the data are read
**/
bool isRestoringDeltaIndexDone(const DeltaIndex *deltaIndex);
/**
* Restore a saved delta list
*
* @param deltaIndex The delta index
* @param dlsi The DeltaListSaveInfo describing the delta list
* @param data The saved delta list bit stream
*
* @return error code or UDS_SUCCESS
**/
int restoreDeltaListToDeltaIndex(const DeltaIndex *deltaIndex,
const DeltaListSaveInfo *dlsi,
const byte data[DELTA_LIST_MAX_BYTE_COUNT])
__attribute__((warn_unused_result));
/**
* Abort restoring a delta index from an input stream.
*
* @param deltaIndex The delta index
**/
void abortRestoringDeltaIndex(const DeltaIndex *deltaIndex);
/**
* Start saving a delta index zone to a buffered output stream.
*
* @param deltaIndex The delta index
* @param zoneNumber The zone number
* @param bufferedWriter The index state component being written
*
* @return UDS_SUCCESS on success, or an error code on failure
**/
int startSavingDeltaIndex(const DeltaIndex *deltaIndex,
unsigned int zoneNumber,
BufferedWriter *bufferedWriter)
__attribute__((warn_unused_result));
/**
* Have all the data been written while saving a delta index zone to an
* output stream? If the answer is yes, it is still necessary to call
* finishSavingDeltaIndex(), which will return quickly.
*
* @param deltaIndex The delta index
* @param zoneNumber The zone number
*
* @return true if all the data are written
**/
bool isSavingDeltaIndexDone(const DeltaIndex *deltaIndex,
unsigned int zoneNumber);
/**
* Finish saving a delta index zone to an output stream. Force the writing
* of all of the remaining data. If an error occurred asynchronously
* during the save operation, it will be returned here.
*
* @param deltaIndex The delta index
* @param zoneNumber The zone number
*
* @return UDS_SUCCESS on success, or an error code on failure
**/
int finishSavingDeltaIndex(const DeltaIndex *deltaIndex,
unsigned int zoneNumber)
__attribute__((warn_unused_result));
/**
* Abort saving a delta index zone to an output stream. If an error
* occurred asynchronously during the save operation, it will be dropped.
*
* @param deltaIndex The delta index
* @param zoneNumber The zone number
*
* @return UDS_SUCCESS on success, or an error code on failure
**/
int abortSavingDeltaIndex(const DeltaIndex *deltaIndex,
unsigned int zoneNumber)
__attribute__((warn_unused_result));
/**
* Compute the number of bytes required to save a delta index
*
* @param numLists The number of delta lists in the index
* @param memorySize The number of bytes in memory for the index
*
* @return numBytes The number of bytes required to save the master index
**/
size_t computeDeltaIndexSaveBytes(unsigned int numLists, size_t memorySize)
__attribute__((warn_unused_result));
/**
* Validate the delta index
*
* @param deltaIndex The delta index
*
* @return UDS_SUCCESS on success, or an error code on failure
**/
int validateDeltaIndex(const DeltaIndex *deltaIndex)
__attribute__((warn_unused_result));
/**
* Prepare to search for an entry in the specified delta list.
*
* <p> This is always the first routine to be called when dealing with delta
* index entries. It is always followed by calls to nextDeltaIndexEntry to
* iterate through a delta list. The fields of the DeltaIndexEntry argument
* will be set up for iteration, but will not contain an entry from the list.
*
* @param deltaIndex The delta index to search
* @param listNumber The delta list number
* @param key First delta list key that the caller is interested in
* @param readOnly True if this is a read-only operation
* @param iterator The index entry being used to search through the list
*
* @return UDS_SUCCESS on success, or an error code on failure
**/
int startDeltaIndexSearch(const DeltaIndex *deltaIndex,
unsigned int listNumber, unsigned int key,
bool readOnly, DeltaIndexEntry *iterator)
__attribute__((warn_unused_result));
/**
* Find the next entry in the specified delta list
*
* @param deltaEntry Info about an entry, which is updated to describe the
* following entry
*
* @return UDS_SUCCESS on success, or an error code on failure
**/
int nextDeltaIndexEntry(DeltaIndexEntry *deltaEntry)
__attribute__((warn_unused_result));
/**
* Remember the position of a delta index entry, so that we can use it when
* starting the next search.
*
* @param deltaEntry Info about an entry found during a search. This should
* be the first entry that matches the key exactly (i.e.
* not a collision entry), or the first entry with a key
* greater than the entry sought for.
*
* @return UDS_SUCCESS on success, or an error code on failure
**/
int rememberDeltaIndexOffset(const DeltaIndexEntry *deltaEntry)
__attribute__((warn_unused_result));
/**
* Find the delta index entry, or the insertion point for a delta index
* entry.
*
* @param deltaIndex The delta index to search
* @param listNumber The delta list number
* @param key The key field being looked for
* @param name The 256 bit full name
* @param readOnly True if this is a read-only index search
* @param deltaEntry Updated to describe the entry being looked for
*
* @return UDS_SUCCESS or an error code
**/
int getDeltaIndexEntry(const DeltaIndex *deltaIndex, unsigned int listNumber,
unsigned int key, const byte *name, bool readOnly,
DeltaIndexEntry *deltaEntry)
__attribute__((warn_unused_result));
/**
* Get the full name from a collision DeltaIndexEntry
*
* @param deltaEntry The delta index record
* @param name The 256 bit full name
*
* @return UDS_SUCCESS or an error code
**/
int getDeltaEntryCollision(const DeltaIndexEntry *deltaEntry, byte *name)
__attribute__((warn_unused_result));
/**
* Get the bit offset into delta memory of a delta index entry.
*
* @param deltaEntry The delta index entry
*
* @return the bit offset into delta memory
**/
static INLINE uint64_t getDeltaEntryOffset(const DeltaIndexEntry *deltaEntry)
{
return getDeltaListStart(deltaEntry->deltaList) + deltaEntry->offset;
}
/**
* Get the number of bits used to encode the entry key (the delta).
*
* @param entry The delta index record
*
* @return the number of bits used to encode the key
**/
static INLINE unsigned int getDeltaEntryKeyBits(const DeltaIndexEntry *entry)
{
/*
* Derive keyBits by subtracting the sizes of the other two fields from the
* total. We don't actually use this for encoding/decoding, so it doesn't
* need to be super-fast. We save time where it matters by not storing it.
*/
return (entry->entryBits - entry->valueBits
- (entry->isCollision ? COLLISION_BITS : 0));
}
/**
* Get the value field of the DeltaIndexEntry
*
* @param deltaEntry The delta index record
*
* @return the value
**/
static INLINE unsigned int getDeltaEntryValue(const DeltaIndexEntry *deltaEntry)
{
return getField(deltaEntry->deltaZone->memory,
getDeltaEntryOffset(deltaEntry), deltaEntry->valueBits);
}
/**
* Set the value field of the DeltaIndexEntry
*
* @param deltaEntry The delta index record
* @param value The new value
*
* @return UDS_SUCCESS or an error code
**/
int setDeltaEntryValue(const DeltaIndexEntry *deltaEntry, unsigned int value)
__attribute__((warn_unused_result));
/**
* Create a new entry in the delta index
*
* @param deltaEntry The delta index entry that indicates the insertion point
* for the new record. For a collision entry, this is the
* non-collision entry that the new entry collides with.
* For a non-collision entry, this new entry is inserted
* before the specified entry.
* @param key The key field
* @param value The value field
* @param name For collision entries, the 256 bit full name;
* Otherwise null
*
* @return UDS_SUCCESS or an error code
**/
int putDeltaIndexEntry(DeltaIndexEntry *deltaEntry, unsigned int key,
unsigned int value, const byte *name)
__attribute__((warn_unused_result));
/**
* Remove an existing delta index entry, and advance to the next entry in
* the delta list.
*
* @param deltaEntry On call the delta index record to remove. After
* returning, the following entry in the delta list.
*
* @return UDS_SUCCESS or an error code
**/
int removeDeltaIndexEntry(DeltaIndexEntry *deltaEntry)
__attribute__((warn_unused_result));
/**
* Map a delta list number to a delta zone number
*
* @param deltaIndex The delta index
* @param listNumber The delta list number
*
* @return the zone number containing the delta list
**/
static INLINE unsigned int getDeltaIndexZone(const DeltaIndex *deltaIndex,
unsigned int listNumber)
{
return listNumber / deltaIndex->listsPerZone;
}
/**
* Get the first delta list number in a zone
*
* @param deltaIndex The delta index
* @param zoneNumber The zone number
*
* @return the first delta list index in the zone
**/
unsigned int getDeltaIndexZoneFirstList(const DeltaIndex *deltaIndex,
unsigned int zoneNumber);
/**
* Get the number of delta lists in a zone
*
* @param deltaIndex The delta index
* @param zoneNumber The zone number
*
* @return the number of delta lists in the zone
**/
unsigned int getDeltaIndexZoneNumLists(const DeltaIndex *deltaIndex,
unsigned int zoneNumber);
/**
* Get the number of bytes used for master index entries in a zone
*
* @param deltaIndex The delta index
* @param zoneNumber The zone number
*
* @return The number of bits in use
**/
uint64_t getDeltaIndexZoneDlistBitsUsed(const DeltaIndex *deltaIndex,
unsigned int zoneNumber)
__attribute__((warn_unused_result));
/**
* Get the number of bytes used for master index entries.
*
* @param deltaIndex The delta index
*
* @return The number of bits in use
**/
uint64_t getDeltaIndexDlistBitsUsed(const DeltaIndex *deltaIndex)
__attribute__((warn_unused_result));
/**
* Get the number of bytes allocated for master index entries.
*
* @param deltaIndex The delta index
*
* @return The number of bits allocated
**/
uint64_t getDeltaIndexDlistBitsAllocated(const DeltaIndex *deltaIndex)
__attribute__((warn_unused_result));
/**
* Get the delta index statistics.
*
* @param deltaIndex The delta index
* @param stats The statistics
**/
void getDeltaIndexStats(const DeltaIndex *deltaIndex, DeltaIndexStats *stats);
/**
* Get the number of pages needed for an immutable delta index.
*
* @param numEntries The number of entries in the index
* @param numLists The number of delta lists
* @param meanDelta The mean delta value
* @param numPayloadBits The number of bits in the payload or value
* @param bytesPerPage The number of bytes in a page
*
* @return the number of pages needed for the index
**/
unsigned int getDeltaIndexPageCount(unsigned int numEntries,
unsigned int numLists,
unsigned int meanDelta,
unsigned int numPayloadBits,
size_t bytesPerPage);
/**
* Log a delta index entry, and any error conditions related to the entry.
*
* @param deltaEntry The delta index entry.
**/
void logDeltaIndexEntry(DeltaIndexEntry *deltaEntry);
#endif /* DELTAINDEX_H */