/*
* 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/deltaMemory.h#1 $
*/
#ifndef DELTAMEMORY_H
#define DELTAMEMORY_H 1
#include "bits.h"
#include "bufferedReader.h"
#include "bufferedWriter.h"
#include "compiler.h"
#include "cpu.h"
#include "timeUtils.h"
/*
* We encode the delta list information into 16 bytes per list.
*
* Because the master index has 1 million delta lists, each byte of header
* information ends up costing us 1MB. We have an incentive to keep the
* size down.
*
* The master index delta list memory is currently about 780MB in size,
* which is more than 6 gigabits. Therefore we need at least 33 bits to
* address the master index memory and we use the uint64_t type.
*
* The master index delta lists have 256 entries of about 24 bits each,
* which is 6K bits. The index needs 13 bits to represent the size of a
* delta list and we use the uint16_t type.
*/
typedef struct deltaList {
uint64_t startOffset; // The offset of the delta list start within memory
uint16_t size; // The number of bits in the delta list
uint16_t saveOffset; // Where the last search "found" the key
unsigned int saveKey; // The key for the record just before saveOffset.
} DeltaList;
typedef struct __attribute__((aligned(CACHE_LINE_BYTES))) deltaMemory {
byte *memory; // The delta list memory
DeltaList *deltaLists; // The delta list headers
uint64_t *tempOffsets; // Temporary starts of delta lists
byte *flags; // Transfer flags
BufferedWriter *bufferedWriter; // Buffered writer for saving an index
size_t size; // The size of delta list memory
RelTime rebalanceTime; // The time spent rebalancing
int rebalanceCount; // Number of memory rebalances
unsigned short valueBits; // The number of bits of value
unsigned short minBits; // The number of bits in the minimal key code
unsigned int minKeys; // The number of keys used in a minimal code
unsigned int incrKeys; // The number of keys used for another code bit
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 firstList; // The index of the first delta list
unsigned int numLists; // The number of delta lists
unsigned int numTransfers; // Number of transfer flags that are set
int transferStatus; // Status of the transfers in progress
byte tag; // Tag belonging to this delta index
} DeltaMemory;
typedef struct deltaListSaveInfo {
uint8_t tag; // Tag identifying which delta index this list is in
uint8_t bitOffset; // Bit offset of the start of the list data
uint16_t byteCount; // Number of bytes of list data
uint32_t index; // The delta list number within the delta index
} DeltaListSaveInfo;
// The maximum size of a single delta list (in bytes). We add guard bytes
// to this because such a buffer can be used with moveBits.
enum { DELTA_LIST_MAX_BYTE_COUNT = ((UINT16_MAX + CHAR_BIT) / CHAR_BIT
+ POST_FIELD_GUARD_BYTES) };
/**
* Initialize delta list memory.
*
* @param deltaMemory A delta memory structure
* @param size The initial size of the memory array
* @param firstList The index of the first delta list
* @param numLists The number of delta lists
* @param meanDelta The mean delta
* @param numPayloadBits The number of payload bits
*
* @return error code or UDS_SUCCESS
**/
int initializeDeltaMemory(DeltaMemory *deltaMemory, size_t size,
unsigned int firstList, unsigned int numLists,
unsigned int meanDelta, unsigned int numPayloadBits)
__attribute__((warn_unused_result));
/**
* Uninitialize delta list memory.
*
* @param deltaMemory A delta memory structure
**/
void uninitializeDeltaMemory(DeltaMemory *deltaMemory);
/**
* Initialize delta list memory to refer to a cached page.
*
* @param deltaMemory A delta memory structure
* @param memory The memory page
* @param size The size of the memory page
* @param numLists The number of delta lists
* @param meanDelta The mean delta
* @param numPayloadBits The number of payload bits
**/
void initializeDeltaMemoryPage(DeltaMemory *deltaMemory, byte *memory,
size_t size, unsigned int numLists,
unsigned int meanDelta,
unsigned int numPayloadBits);
/**
* Empty the delta lists.
*
* @param deltaMemory The delta memory
**/
void emptyDeltaLists(DeltaMemory *deltaMemory);
/**
* Is there a delta list memory save or restore in progress?
*
* @param deltaMemory A delta memory structure
*
* @return true if there are no delta lists that need to be saved or
* restored
**/
bool areDeltaMemoryTransfersDone(const DeltaMemory *deltaMemory);
/**
* Start restoring delta list memory from a file descriptor
*
* @param deltaMemory A delta memory structure
*
* @return error code or UDS_SUCCESS
**/
int startRestoringDeltaMemory(DeltaMemory *deltaMemory)
__attribute__((warn_unused_result));
/**
* Read a saved delta list from a file descriptor
*
* @param dlsi The DeltaListSaveInfo describing the delta list
* @param data The saved delta list bit stream
* @param bufferedReader The buffered reader to read the delta list from
*
* @return error code or UDS_SUCCESS
* or UDS_END_OF_FILE at end of the data stream
**/
int readSavedDeltaList(DeltaListSaveInfo *dlsi,
byte data[DELTA_LIST_MAX_BYTE_COUNT],
BufferedReader *bufferedReader)
__attribute__((warn_unused_result));
/**
* Restore a saved delta list
*
* @param deltaMemory A delta memory structure
* @param dlsi The DeltaListSaveInfo describing the delta list
* @param data The saved delta list bit stream
*
* @return error code or UDS_SUCCESS
**/
int restoreDeltaList(DeltaMemory *deltaMemory, const DeltaListSaveInfo *dlsi,
const byte data[DELTA_LIST_MAX_BYTE_COUNT])
__attribute__((warn_unused_result));
/**
* Abort restoring delta list memory from an input stream.
*
* @param deltaMemory A delta memory structure
**/
void abortRestoringDeltaMemory(DeltaMemory *deltaMemory);
/**
* Start saving delta list memory to a buffered output stream
*
* @param deltaMemory A delta memory structure
* @param bufferedWriter The index state component being written
**/
void startSavingDeltaMemory(DeltaMemory *deltaMemory,
BufferedWriter *bufferedWriter);
/**
* Finish saving delta list memory 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 deltaMemory A delta memory structure
*
* @return error code or UDS_SUCCESS
**/
int finishSavingDeltaMemory(DeltaMemory *deltaMemory)
__attribute__((warn_unused_result));
/**
* Abort saving delta list memory to an output stream. If an error
* occurred asynchronously during the save operation, it will be dropped.
*
* @param deltaMemory A delta memory structure
**/
void abortSavingDeltaMemory(DeltaMemory *deltaMemory);
/**
* Flush a delta list to an output stream
*
* @param deltaMemory A delta memory structure
* @param flushIndex Index of the delta list that may need to be flushed.
**/
void flushDeltaList(DeltaMemory *deltaMemory, unsigned int flushIndex);
/**
* Write a guard delta list to mark the end of the saved data
*
* @param bufferedWriter The buffered writer to write the guard delta list to
*
* @return error code or UDS_SUCCESS
**/
int writeGuardDeltaList(BufferedWriter *bufferedWriter)
__attribute__((warn_unused_result));
/**
* Extend the memory used by the delta lists and rebalance the lists in the
* new chunk.
*
* <p> The delta memory contains N delta lists, which are guarded by two
* empty delta lists. The valid delta lists are numbered 1 to N, and the
* guards are numbered 0 and (N+1);
*
* <p> When the delta lista are bit streams, it is possible that the tail
* of list J and the head of list (J+1) are in the same byte. In this case
* oldOffsets[j]+sizes[j]==oldOffset[j]-1. We handle this correctly.
*
* @param deltaMemory A delta memory structure
* @param growingIndex Index of the delta list that needs additional space
* left before it (from 1 to N+1).
* @param growingSize Number of additional bytes needed before growingIndex
* @param doCopy True to copy the data, False to just balance the space
*
* @return UDS_SUCCESS or an error code
**/
int extendDeltaMemory(DeltaMemory *deltaMemory, unsigned int growingIndex,
size_t growingSize, bool doCopy)
__attribute__((warn_unused_result));
/**
* Validate the delta list headers.
*
* @param deltaMemory A delta memory structure
*
* @return UDS_SUCCESS or an error code
**/
int validateDeltaLists(const DeltaMemory *deltaMemory)
__attribute__((warn_unused_result));
/**
* Get the number of bytes allocated for delta index entries and any
* associated overhead.
*
* @param deltaMemory A delta memory structure
*
* @return The number of bytes allocated
**/
size_t getDeltaMemoryAllocated(const DeltaMemory *deltaMemory);
/**
* Get the expected number of bits used in a delta index
*
* @param numEntries The number of index entries
* @param meanDelta The mean delta value
* @param numPayloadBits The number of bits in the payload or value
*
* @return The expected size of a delta index in bits
**/
size_t getDeltaMemorySize(unsigned long numEntries, unsigned int meanDelta,
unsigned int numPayloadBits)
__attribute__((warn_unused_result));
/**
* Get the bit offset to the start of the delta list bit stream
*
* @param deltaList The delta list header
*
* @return the start of the delta list
**/
static INLINE uint64_t getDeltaListStart(const DeltaList *deltaList)
{
return deltaList->startOffset;
}
/**
* Get the number of bits in a delta list bit stream
*
* @param deltaList The delta list header
*
* @return the size of the delta list
**/
static INLINE uint16_t getDeltaListSize(const DeltaList *deltaList)
{
return deltaList->size;
}
/**
* Get the bit offset to the end of the delta list bit stream
*
* @param deltaList The delta list header
*
* @return the end of the delta list
**/
static INLINE uint64_t getDeltaListEnd(const DeltaList *deltaList)
{
return getDeltaListStart(deltaList) + getDeltaListSize(deltaList);
}
/**
* Identify mutable vs. immutable delta memory
*
* Mutable delta memory contains delta lists that can be modified, and is
* initialized using initializeDeltaMemory().
*
* Immutable delta memory contains packed delta lists, cannot be modified,
* and is initialized using initializeDeltaMemoryPage().
*
* For mutable delta memory, all of the following expressions are true.
* And for immutable delta memory, all of the following expressions are
* false.
* deltaLists != NULL
* tempOffsets != NULL
* flags != NULL
*
* @param deltaMemory A delta memory structure
*
* @return true if the delta memory is mutable
**/
static INLINE bool isMutable(const DeltaMemory *deltaMemory)
{
return deltaMemory->deltaLists != NULL;
}
/**
* Lazily flush a delta list to an output stream
*
* @param deltaMemory A delta memory structure
* @param flushIndex Index of the delta list that may need to be flushed.
**/
static INLINE void lazyFlushDeltaList(DeltaMemory *deltaMemory,
unsigned int flushIndex)
{
if (getField(deltaMemory->flags, flushIndex, 1) != 0) {
flushDeltaList(deltaMemory, flushIndex);
}
}
#endif /* DELTAMEMORY_H */