|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Copyright (c) 2020 Red Hat, Inc.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is free software; you can redistribute it and/or
|
|
Packit Service |
310c69 |
* modify it under the terms of the GNU General Public License
|
|
Packit Service |
310c69 |
* as published by the Free Software Foundation; either version 2
|
|
Packit Service |
310c69 |
* of the License, or (at your option) any later version.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This program is distributed in the hope that it will be useful,
|
|
Packit Service |
310c69 |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
310c69 |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
310c69 |
* GNU General Public License for more details.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
310c69 |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
310c69 |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
Packit Service |
310c69 |
* 02110-1301, USA.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* $Id: //eng/uds-releases/jasper/src/uds/masterIndex005.c#3 $
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
#include "masterIndex005.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
#include "buffer.h"
|
|
Packit Service |
310c69 |
#include "compiler.h"
|
|
Packit Service |
310c69 |
#include "errors.h"
|
|
Packit Service |
310c69 |
#include "hashUtils.h"
|
|
Packit Service |
310c69 |
#include "logger.h"
|
|
Packit Service |
310c69 |
#include "memoryAlloc.h"
|
|
Packit Service |
310c69 |
#include "uds.h"
|
|
Packit Service |
310c69 |
#include "zone.h"
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* The master index is a kept as a delta index where the payload is a
|
|
Packit Service |
310c69 |
* chapter number. The master index adds 2 basic functions to the delta
|
|
Packit Service |
310c69 |
* index:
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* (1) How to get the delta list number and address out of the chunk name.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* (2) Dealing with chapter numbers, and especially the lazy flushing of
|
|
Packit Service |
310c69 |
* chapters from the index.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* There are three ways of expressing chapter numbers: virtual, index, and
|
|
Packit Service |
310c69 |
* rolling. The interface to the the master index uses virtual chapter
|
|
Packit Service |
310c69 |
* numbers, which are 64 bits long. We do not store such large values in
|
|
Packit Service |
310c69 |
* memory, so we internally use a binary value using the minimal number of
|
|
Packit Service |
310c69 |
* bits.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* The delta index stores the index chapter number, which is the low-order
|
|
Packit Service |
310c69 |
* bits of the virtual chapter number.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* When we need to deal with ordering of index chapter numbers, we roll the
|
|
Packit Service |
310c69 |
* index chapter number around so that the smallest one we are using has
|
|
Packit Service |
310c69 |
* the representation 0. See convertIndexToVirtual() or
|
|
Packit Service |
310c69 |
* flushInvalidEntries() for an example of this technique.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
typedef struct __attribute__((aligned(CACHE_LINE_BYTES))) masterIndexZone {
|
|
Packit Service |
310c69 |
uint64_t virtualChapterLow; // The lowest virtual chapter indexed
|
|
Packit Service |
310c69 |
uint64_t virtualChapterHigh; // The highest virtual chapter indexed
|
|
Packit Service |
310c69 |
long numEarlyFlushes; // The number of early flushes
|
|
Packit Service |
310c69 |
} MasterIndexZone;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
typedef struct {
|
|
Packit Service |
310c69 |
MasterIndex common; // Common master index methods
|
|
Packit Service |
310c69 |
DeltaIndex deltaIndex; // The delta index
|
|
Packit Service |
310c69 |
uint64_t *flushChapters; // The first chapter to be flushed
|
|
Packit Service |
310c69 |
MasterIndexZone *masterZones; // The Zones
|
|
Packit Service |
310c69 |
uint64_t volumeNonce; // The volume nonce
|
|
Packit Service |
310c69 |
uint64_t chapterZoneBits; // Expected size of a chapter (per zone)
|
|
Packit Service |
310c69 |
uint64_t maxZoneBits; // Maximum size index (per zone)
|
|
Packit Service |
310c69 |
unsigned int addressBits; // Number of bits in address mask
|
|
Packit Service |
310c69 |
unsigned int addressMask; // Mask to get address within delta list
|
|
Packit Service |
310c69 |
unsigned int chapterBits; // Number of bits in chapter number
|
|
Packit Service |
310c69 |
unsigned int chapterMask; // Largest storable chapter number
|
|
Packit Service |
310c69 |
unsigned int numChapters; // Number of chapters used
|
|
Packit Service |
310c69 |
unsigned int numDeltaLists; // The number of delta lists
|
|
Packit Service |
310c69 |
unsigned int numZones; // The number of zones
|
|
Packit Service |
310c69 |
} MasterIndex5;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
typedef struct chapterRange {
|
|
Packit Service |
310c69 |
unsigned int chapterStart; // The first chapter
|
|
Packit Service |
310c69 |
unsigned int chapterCount; // The number of chapters
|
|
Packit Service |
310c69 |
} ChapterRange;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Constants for the magic byte of a MasterIndexRecord
|
|
Packit Service |
310c69 |
static const byte masterIndexRecordMagic = 0xAA;
|
|
Packit Service |
310c69 |
static const byte badMagic = 0;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* In production, the default value for minMasterIndexDeltaLists will be
|
|
Packit Service |
310c69 |
* replaced by MAX_ZONES*MAX_ZONES. Some unit tests will replace
|
|
Packit Service |
310c69 |
* minMasterIndexDeltaLists with the non-default value 1, because those
|
|
Packit Service |
310c69 |
* tests really want to run with a single delta list.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
unsigned int minMasterIndexDeltaLists;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Maximum of two unsigned ints
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param a One unsigned int
|
|
Packit Service |
310c69 |
* @param b Another unsigned int
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the bigger one
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE unsigned int maxUint(unsigned int a, unsigned int b)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
return a > b ? a : b;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Extract the address from a block name.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param mi5 The master index
|
|
Packit Service |
310c69 |
* @param name The block name
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the address
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE unsigned int extractAddress(const MasterIndex5 *mi5,
|
|
Packit Service |
310c69 |
const UdsChunkName *name)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
return extractMasterIndexBytes(name) & mi5->addressMask;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Extract the delta list number from a block name.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param mi5 The master index
|
|
Packit Service |
310c69 |
* @param name The block name
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the delta list number
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE unsigned int extractDListNum(const MasterIndex5 *mi5,
|
|
Packit Service |
310c69 |
const UdsChunkName *name)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
uint64_t bits = extractMasterIndexBytes(name);
|
|
Packit Service |
310c69 |
return (bits >> mi5->addressBits) % mi5->numDeltaLists;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Get the master index zone containing a given master index record
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param record The master index record
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the master index zone
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE const MasterIndexZone *getMasterZone(const MasterIndexRecord *record)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = container_of(record->masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
return &mi5->masterZones[record->zoneNumber];
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Convert an index chapter number to a virtual chapter number.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param record The master index record
|
|
Packit Service |
310c69 |
* @param indexChapter The index chapter number
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the virtual chapter number
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE uint64_t convertIndexToVirtual(const MasterIndexRecord *record,
|
|
Packit Service |
310c69 |
unsigned int indexChapter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = container_of(record->masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
const MasterIndexZone *masterZone = getMasterZone(record);
|
|
Packit Service |
310c69 |
unsigned int rollingChapter
|
|
Packit Service |
310c69 |
= ((indexChapter - masterZone->virtualChapterLow) & mi5->chapterMask);
|
|
Packit Service |
310c69 |
return masterZone->virtualChapterLow + rollingChapter;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Convert a virtual chapter number to an index chapter number.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param mi5 The master index
|
|
Packit Service |
310c69 |
* @param virtualChapter The virtual chapter number
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the index chapter number
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE unsigned int convertVirtualToIndex(const MasterIndex5 *mi5,
|
|
Packit Service |
310c69 |
uint64_t virtualChapter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
return virtualChapter & mi5->chapterMask;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Determine whether a virtual chapter number is in the range being indexed
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param record The master index record
|
|
Packit Service |
310c69 |
* @param virtualChapter The virtual chapter number
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return true if the virtual chapter number is being indexed
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE bool isVirtualChapterIndexed(const MasterIndexRecord *record,
|
|
Packit Service |
310c69 |
uint64_t virtualChapter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndexZone *masterZone = getMasterZone(record);
|
|
Packit Service |
310c69 |
return ((virtualChapter >= masterZone->virtualChapterLow)
|
|
Packit Service |
310c69 |
&& (virtualChapter <= masterZone->virtualChapterHigh));
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Flush an invalid entry from the master index, advancing to the next
|
|
Packit Service |
310c69 |
* valid entry.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param record Updated to describe the next valid record
|
|
Packit Service |
310c69 |
* @param flushRange Range of chapters to flush from the index
|
|
Packit Service |
310c69 |
* @param nextChapterToInvalidate Updated to record the next chapter that we
|
|
Packit Service |
310c69 |
* will need to invalidate
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static INLINE int flushInvalidEntries(MasterIndexRecord *record,
|
|
Packit Service |
310c69 |
ChapterRange *flushRange,
|
|
Packit Service |
310c69 |
unsigned int *nextChapterToInvalidate)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = container_of(record->masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
int result = nextDeltaIndexEntry(&record->deltaEntry);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
while (!record->deltaEntry.atEnd) {
|
|
Packit Service |
310c69 |
unsigned int indexChapter = getDeltaEntryValue(&record->deltaEntry);
|
|
Packit Service |
310c69 |
unsigned int relativeChapter = ((indexChapter - flushRange->chapterStart)
|
|
Packit Service |
310c69 |
& mi5->chapterMask);
|
|
Packit Service |
310c69 |
if (likely(relativeChapter >= flushRange->chapterCount)) {
|
|
Packit Service |
310c69 |
if (relativeChapter < *nextChapterToInvalidate) {
|
|
Packit Service |
310c69 |
*nextChapterToInvalidate = relativeChapter;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
break;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = removeDeltaIndexEntry(&record->deltaEntry);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Find the delta index entry, or the insertion point for a delta index
|
|
Packit Service |
310c69 |
* entry, while processing chapter LRU flushing.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param record Updated to describe the entry being looked for
|
|
Packit Service |
310c69 |
* @param listNumber The delta list number
|
|
Packit Service |
310c69 |
* @param key The address field being looked for
|
|
Packit Service |
310c69 |
* @param flushRange The range of chapters to flush from the index
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int getMasterIndexEntry(MasterIndexRecord *record,
|
|
Packit Service |
310c69 |
unsigned int listNumber,
|
|
Packit Service |
310c69 |
unsigned int key,
|
|
Packit Service |
310c69 |
ChapterRange *flushRange)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = container_of(record->masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
unsigned int nextChapterToInvalidate = mi5->chapterMask;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
int result = startDeltaIndexSearch(&mi5->deltaIndex, listNumber, 0,
|
|
Packit Service |
310c69 |
false, &record->deltaEntry);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
do {
|
|
Packit Service |
310c69 |
result = flushInvalidEntries(record, flushRange, &nextChapterToInvalidate);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
} while (!record->deltaEntry.atEnd && (key > record->deltaEntry.key));
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
result = rememberDeltaIndexOffset(&record->deltaEntry);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// We probably found the record we want, but we need to keep going
|
|
Packit Service |
310c69 |
MasterIndexRecord otherRecord = *record;
|
|
Packit Service |
310c69 |
if (!otherRecord.deltaEntry.atEnd && (key == otherRecord.deltaEntry.key)) {
|
|
Packit Service |
310c69 |
for (;;) {
|
|
Packit Service |
310c69 |
result = flushInvalidEntries(&otherRecord, flushRange,
|
|
Packit Service |
310c69 |
&nextChapterToInvalidate);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (otherRecord.deltaEntry.atEnd
|
|
Packit Service |
310c69 |
|| !otherRecord.deltaEntry.isCollision) {
|
|
Packit Service |
310c69 |
break;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
byte collisionName[UDS_CHUNK_NAME_SIZE];
|
|
Packit Service |
310c69 |
result = getDeltaEntryCollision(&otherRecord.deltaEntry, collisionName);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (memcmp(collisionName, record->name, UDS_CHUNK_NAME_SIZE) == 0) {
|
|
Packit Service |
310c69 |
// This collision record is the one we are looking for
|
|
Packit Service |
310c69 |
*record = otherRecord;
|
|
Packit Service |
310c69 |
break;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
while (!otherRecord.deltaEntry.atEnd) {
|
|
Packit Service |
310c69 |
result = flushInvalidEntries(&otherRecord, flushRange,
|
|
Packit Service |
310c69 |
&nextChapterToInvalidate);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
nextChapterToInvalidate += flushRange->chapterStart;
|
|
Packit Service |
310c69 |
nextChapterToInvalidate &= mi5->chapterMask;
|
|
Packit Service |
310c69 |
flushRange->chapterStart = nextChapterToInvalidate;
|
|
Packit Service |
310c69 |
flushRange->chapterCount = 0;
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Terminate and clean up the master index
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index to terminate
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void freeMasterIndex_005(MasterIndex *masterIndex)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if (masterIndex != NULL) {
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5 = container_of(masterIndex, MasterIndex5, common);
|
|
Packit Service |
310c69 |
FREE(mi5->flushChapters);
|
|
Packit Service |
310c69 |
mi5->flushChapters = NULL;
|
|
Packit Service |
310c69 |
FREE(mi5->masterZones);
|
|
Packit Service |
310c69 |
mi5->masterZones = NULL;
|
|
Packit Service |
310c69 |
uninitializeDeltaIndex(&mi5->deltaIndex);
|
|
Packit Service |
310c69 |
FREE(masterIndex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Constants and structures for the saved master index file. "MI5" is for
|
|
Packit Service |
310c69 |
* masterIndex005, and "-XXXX" is a number to increment when the format of
|
|
Packit Service |
310c69 |
* the data changes.
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
enum { MAGIC_SIZE = 8 };
|
|
Packit Service |
310c69 |
static const char MAGIC_MI_START[] = "MI5-0005";
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
struct mi005_data {
|
|
Packit Service |
310c69 |
char magic[MAGIC_SIZE]; // MAGIC_MI_START
|
|
Packit Service |
310c69 |
uint64_t volumeNonce;
|
|
Packit Service |
310c69 |
uint64_t virtualChapterLow;
|
|
Packit Service |
310c69 |
uint64_t virtualChapterHigh;
|
|
Packit Service |
310c69 |
unsigned int firstList;
|
|
Packit Service |
310c69 |
unsigned int numLists;
|
|
Packit Service |
310c69 |
};
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Set the tag value used when saving and/or restoring a master index.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param tag The tag value
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void setMasterIndexTag_005(MasterIndex *masterIndex, byte tag)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5 = container_of(masterIndex, MasterIndex5, common);
|
|
Packit Service |
310c69 |
setDeltaIndexTag(&mi5->deltaIndex, tag);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result))
|
|
Packit Service |
310c69 |
static int encodeMasterIndexHeader(Buffer *buffer, struct mi005_data *header)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
int result = putBytes(buffer, MAGIC_SIZE, MAGIC_MI_START);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = putUInt64LEIntoBuffer(buffer, header->volumeNonce);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = putUInt64LEIntoBuffer(buffer, header->virtualChapterLow);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = putUInt64LEIntoBuffer(buffer, header->virtualChapterHigh);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = putUInt32LEIntoBuffer(buffer, header->firstList);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = putUInt32LEIntoBuffer(buffer, header->numLists);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = ASSERT_LOG_ONLY(contentLength(buffer) == sizeof(struct mi005_data),
|
|
Packit Service |
310c69 |
"%zu bytes of config written, of %zu expected",
|
|
Packit Service |
310c69 |
contentLength(buffer), sizeof(struct mi005_data));
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Start saving a master index to a buffered output stream.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param zoneNumber The number of the zone to save
|
|
Packit Service |
310c69 |
* @param bufferedWriter The index state component being written
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS on success, or an error code on failure
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int startSavingMasterIndex_005(const MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
unsigned int zoneNumber,
|
|
Packit Service |
310c69 |
BufferedWriter *bufferedWriter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
MasterIndexZone *masterZone = &mi5->masterZones[zoneNumber];
|
|
Packit Service |
310c69 |
unsigned int firstList = getDeltaIndexZoneFirstList(&mi5->deltaIndex,
|
|
Packit Service |
310c69 |
zoneNumber);
|
|
Packit Service |
310c69 |
unsigned int numLists = getDeltaIndexZoneNumLists(&mi5->deltaIndex,
|
|
Packit Service |
310c69 |
zoneNumber);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
struct mi005_data header;
|
|
Packit Service |
310c69 |
memset(&header, 0, sizeof(header));
|
|
Packit Service |
310c69 |
memcpy(header.magic, MAGIC_MI_START, MAGIC_SIZE);
|
|
Packit Service |
310c69 |
header.volumeNonce = mi5->volumeNonce;
|
|
Packit Service |
310c69 |
header.virtualChapterLow = masterZone->virtualChapterLow;
|
|
Packit Service |
310c69 |
header.virtualChapterHigh = masterZone->virtualChapterHigh;
|
|
Packit Service |
310c69 |
header.firstList = firstList;
|
|
Packit Service |
310c69 |
header.numLists = numLists;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
Buffer *buffer;
|
|
Packit Service |
310c69 |
int result = makeBuffer(sizeof(struct mi005_data), &buffer);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = encodeMasterIndexHeader(buffer, &header);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = writeToBufferedWriter(bufferedWriter, getBufferContents(buffer),
|
|
Packit Service |
310c69 |
contentLength(buffer));
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(result,
|
|
Packit Service |
310c69 |
"failed to write master index header");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = makeBuffer(numLists * sizeof(uint64_t), &buffer);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
uint64_t *firstFlushChapter = &mi5->flushChapters[firstList];
|
|
Packit Service |
310c69 |
result = putUInt64LEsIntoBuffer(buffer, numLists, firstFlushChapter);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = writeToBufferedWriter(bufferedWriter, getBufferContents(buffer),
|
|
Packit Service |
310c69 |
contentLength(buffer));
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(result,
|
|
Packit Service |
310c69 |
"failed to write master index flush "
|
|
Packit Service |
310c69 |
"ranges");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
return startSavingDeltaIndex(&mi5->deltaIndex, zoneNumber, bufferedWriter);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Have all the data been written while saving a master index to an output
|
|
Packit Service |
310c69 |
* stream? If the answer is yes, it is still necessary to call
|
|
Packit Service |
310c69 |
* finishSavingMasterIndex(), which will return quickly.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param zoneNumber The number of the zone to save
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return true if all the data are written
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static bool isSavingMasterIndexDone_005(const MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
unsigned int zoneNumber)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
return isSavingDeltaIndexDone(&mi5->deltaIndex, zoneNumber);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Finish saving a master index to an output stream. Force the writing of
|
|
Packit Service |
310c69 |
* all of the remaining data. If an error occurred asynchronously during
|
|
Packit Service |
310c69 |
* the save operation, it will be returned here.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param zoneNumber The number of the zone to save
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS on success, or an error code on failure
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int finishSavingMasterIndex_005(const MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
unsigned int zoneNumber)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
return finishSavingDeltaIndex(&mi5->deltaIndex, zoneNumber);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Abort saving a master index to an output stream. If an error occurred
|
|
Packit Service |
310c69 |
* asynchronously during the save operation, it will be dropped.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param zoneNumber The number of the zone to save
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS on success, or an error code on failure
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int abortSavingMasterIndex_005(const MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
unsigned int zoneNumber)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
return abortSavingDeltaIndex(&mi5->deltaIndex, zoneNumber);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
__attribute__((warn_unused_result))
|
|
Packit Service |
310c69 |
static int decodeMasterIndexHeader(Buffer *buffer, struct mi005_data *header)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
int result = getBytesFromBuffer(buffer, sizeof(header->magic),
|
|
Packit Service |
310c69 |
&header->magic);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = getUInt64LEFromBuffer(buffer, &header->volumeNonce);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = getUInt64LEFromBuffer(buffer, &header->virtualChapterLow);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = getUInt64LEFromBuffer(buffer, &header->virtualChapterHigh);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = getUInt32LEFromBuffer(buffer, &header->firstList);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = getUInt32LEFromBuffer(buffer, &header->numLists);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = ASSERT_LOG_ONLY(contentLength(buffer) == 0,
|
|
Packit Service |
310c69 |
"%zu bytes decoded of %zu expected",
|
|
Packit Service |
310c69 |
bufferLength(buffer) - contentLength(buffer),
|
|
Packit Service |
310c69 |
bufferLength(buffer));
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
result = UDS_CORRUPT_COMPONENT;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Start restoring the master index from multiple buffered readers
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index to restore into
|
|
Packit Service |
310c69 |
* @param bufferedReaders The buffered readers to read the master index from
|
|
Packit Service |
310c69 |
* @param numReaders The number of buffered readers
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS on success, or an error code on failure
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int startRestoringMasterIndex_005(MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
BufferedReader **bufferedReaders,
|
|
Packit Service |
310c69 |
int numReaders)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if (masterIndex == NULL) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_BAD_STATE,
|
|
Packit Service |
310c69 |
"cannot restore to null master index");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5 = container_of(masterIndex, MasterIndex5, common);
|
|
Packit Service |
310c69 |
emptyDeltaIndex(&mi5->deltaIndex);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
uint64_t virtualChapterLow = 0;
|
|
Packit Service |
310c69 |
uint64_t virtualChapterHigh = 0;
|
|
Packit Service |
310c69 |
int i;
|
|
Packit Service |
310c69 |
for (i = 0; i < numReaders; i++) {
|
|
Packit Service |
310c69 |
Buffer *buffer;
|
|
Packit Service |
310c69 |
int result = makeBuffer(sizeof(struct mi005_data), &buffer);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = readFromBufferedReader(bufferedReaders[i],
|
|
Packit Service |
310c69 |
getBufferContents(buffer),
|
|
Packit Service |
310c69 |
bufferLength(buffer));
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
return logWarningWithStringError(result,
|
|
Packit Service |
310c69 |
"failed to read master index header");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = resetBufferEnd(buffer, bufferLength(buffer));
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
struct mi005_data header;
|
|
Packit Service |
310c69 |
result = decodeMasterIndexHeader(buffer, &header);
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (memcmp(header.magic, MAGIC_MI_START, MAGIC_SIZE) != 0) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_CORRUPT_COMPONENT,
|
|
Packit Service |
310c69 |
"master index file had bad magic"
|
|
Packit Service |
310c69 |
" number");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (mi5->volumeNonce == 0) {
|
|
Packit Service |
310c69 |
mi5->volumeNonce = header.volumeNonce;
|
|
Packit Service |
310c69 |
} else if (header.volumeNonce != mi5->volumeNonce) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_CORRUPT_COMPONENT,
|
|
Packit Service |
310c69 |
"master index volume nonce incorrect");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (i == 0) {
|
|
Packit Service |
310c69 |
virtualChapterLow = header.virtualChapterLow;
|
|
Packit Service |
310c69 |
virtualChapterHigh = header.virtualChapterHigh;
|
|
Packit Service |
310c69 |
} else if (virtualChapterHigh != header.virtualChapterHigh) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_CORRUPT_COMPONENT,
|
|
Packit Service |
310c69 |
"Inconsistent master index zone files:"
|
|
Packit Service |
310c69 |
" Chapter range is [%llu,%"
|
|
Packit Service |
310c69 |
PRIu64 "], chapter range %d is [%"
|
|
Packit Service |
310c69 |
PRIu64 ",%llu]",
|
|
Packit Service |
310c69 |
virtualChapterLow, virtualChapterHigh,
|
|
Packit Service |
310c69 |
i, header.virtualChapterLow,
|
|
Packit Service |
310c69 |
header.virtualChapterHigh);
|
|
Packit Service |
310c69 |
} else if (virtualChapterLow < header.virtualChapterLow) {
|
|
Packit Service |
310c69 |
virtualChapterLow = header.virtualChapterLow;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
uint64_t *firstFlushChapter = &mi5->flushChapters[header.firstList];
|
|
Packit Service |
310c69 |
result = makeBuffer(header.numLists * sizeof(uint64_t), &buffer);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = readFromBufferedReader(bufferedReaders[i],
|
|
Packit Service |
310c69 |
getBufferContents(buffer),
|
|
Packit Service |
310c69 |
bufferLength(buffer));
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
return logWarningWithStringError(result,
|
|
Packit Service |
310c69 |
"failed to read master index flush"
|
|
Packit Service |
310c69 |
" ranges");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = resetBufferEnd(buffer, bufferLength(buffer));
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = getUInt64LEsFromBuffer(buffer, header.numLists,
|
|
Packit Service |
310c69 |
firstFlushChapter);
|
|
Packit Service |
310c69 |
freeBuffer(&buffer);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
unsigned int z;
|
|
Packit Service |
310c69 |
for (z = 0; z < mi5->numZones; z++) {
|
|
Packit Service |
310c69 |
memset(&mi5->masterZones[z], 0, sizeof(MasterIndexZone));
|
|
Packit Service |
310c69 |
mi5->masterZones[z].virtualChapterLow = virtualChapterLow;
|
|
Packit Service |
310c69 |
mi5->masterZones[z].virtualChapterHigh = virtualChapterHigh;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
int result = startRestoringDeltaIndex(&mi5->deltaIndex, bufferedReaders,
|
|
Packit Service |
310c69 |
numReaders);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(result, "restoring delta index failed");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Have all the data been read while restoring a master index from an
|
|
Packit Service |
310c69 |
* input stream?
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index to restore into
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return true if all the data are read
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static bool isRestoringMasterIndexDone_005(const MasterIndex *masterIndex)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
return isRestoringDeltaIndexDone(&mi5->deltaIndex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Restore a saved delta list
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index to restore into
|
|
Packit Service |
310c69 |
* @param dlsi The DeltaListSaveInfo describing the delta list
|
|
Packit Service |
310c69 |
* @param data The saved delta list bit stream
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return error code or UDS_SUCCESS
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int restoreDeltaListToMasterIndex_005(MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
const DeltaListSaveInfo *dlsi,
|
|
Packit Service |
310c69 |
const byte data[DELTA_LIST_MAX_BYTE_COUNT])
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5 = container_of(masterIndex, MasterIndex5, common);
|
|
Packit Service |
310c69 |
return restoreDeltaListToDeltaIndex(&mi5->deltaIndex, dlsi, data);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Abort restoring a master index from an input stream.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void abortRestoringMasterIndex_005(MasterIndex *masterIndex)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5 = container_of(masterIndex, MasterIndex5, common);
|
|
Packit Service |
310c69 |
abortRestoringDeltaIndex(&mi5->deltaIndex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
static void removeNewestChapters(MasterIndex5 *mi5,
|
|
Packit Service |
310c69 |
unsigned int zoneNumber,
|
|
Packit Service |
310c69 |
uint64_t virtualChapter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
// Get the range of delta lists belonging to this zone
|
|
Packit Service |
310c69 |
unsigned int firstList = getDeltaIndexZoneFirstList(&mi5->deltaIndex,
|
|
Packit Service |
310c69 |
zoneNumber);
|
|
Packit Service |
310c69 |
unsigned int numLists = getDeltaIndexZoneNumLists(&mi5->deltaIndex,
|
|
Packit Service |
310c69 |
zoneNumber);
|
|
Packit Service |
310c69 |
unsigned int lastList = firstList + numLists - 1;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if (virtualChapter > mi5->chapterMask) {
|
|
Packit Service |
310c69 |
// The virtual chapter number is large enough so that we can use the
|
|
Packit Service |
310c69 |
// normal LRU mechanism without an unsigned underflow.
|
|
Packit Service |
310c69 |
virtualChapter -= mi5->chapterMask + 1;
|
|
Packit Service |
310c69 |
// Eliminate the newest chapters by renumbering them to become the
|
|
Packit Service |
310c69 |
// oldest chapters
|
|
Packit Service |
310c69 |
unsigned int i;
|
|
Packit Service |
310c69 |
for (i = firstList; i <= lastList; i++) {
|
|
Packit Service |
310c69 |
if (virtualChapter < mi5->flushChapters[i]) {
|
|
Packit Service |
310c69 |
mi5->flushChapters[i] = virtualChapter;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
} else {
|
|
Packit Service |
310c69 |
// Underflow will prevent the fast path. Do it the slow and painful way.
|
|
Packit Service |
310c69 |
MasterIndexZone *masterZone = &mi5->masterZones[zoneNumber];
|
|
Packit Service |
310c69 |
ChapterRange range;
|
|
Packit Service |
310c69 |
range.chapterStart = convertVirtualToIndex(mi5, virtualChapter);
|
|
Packit Service |
310c69 |
range.chapterCount = (mi5->chapterMask + 1
|
|
Packit Service |
310c69 |
- (virtualChapter - masterZone->virtualChapterLow));
|
|
Packit Service |
310c69 |
UdsChunkName name;
|
|
Packit Service |
310c69 |
memset(&name, 0, sizeof(UdsChunkName));
|
|
Packit Service |
310c69 |
MasterIndexRecord record = (MasterIndexRecord) {
|
|
Packit Service |
310c69 |
.magic = masterIndexRecordMagic,
|
|
Packit Service |
310c69 |
.masterIndex = &mi5->common,
|
|
Packit Service |
310c69 |
.name = &name,
|
|
Packit Service |
310c69 |
.zoneNumber = zoneNumber,
|
|
Packit Service |
310c69 |
};
|
|
Packit Service |
310c69 |
unsigned int i;
|
|
Packit Service |
310c69 |
for (i = firstList; i <= lastList; i++) {
|
|
Packit Service |
310c69 |
ChapterRange tempRange = range;
|
|
Packit Service |
310c69 |
getMasterIndexEntry(&record, i, 0, &tempRange);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Set the open chapter number on a zone. The master index zone will be
|
|
Packit Service |
310c69 |
* modified to index the proper number of chapters ending with the new open
|
|
Packit Service |
310c69 |
* chapter.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param zoneNumber The zone number
|
|
Packit Service |
310c69 |
* @param virtualChapter The new open chapter number
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void setMasterIndexZoneOpenChapter_005(MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
unsigned int zoneNumber,
|
|
Packit Service |
310c69 |
uint64_t virtualChapter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5 = container_of(masterIndex, MasterIndex5, common);
|
|
Packit Service |
310c69 |
MasterIndexZone *masterZone = &mi5->masterZones[zoneNumber];
|
|
Packit Service |
310c69 |
// Take care here to avoid underflow of an unsigned value. Note that
|
|
Packit Service |
310c69 |
// this is the smallest valid virtual low. We may or may not actually
|
|
Packit Service |
310c69 |
// use this value.
|
|
Packit Service |
310c69 |
uint64_t newVirtualLow = (virtualChapter >= mi5->numChapters
|
|
Packit Service |
310c69 |
? virtualChapter - mi5->numChapters + 1
|
|
Packit Service |
310c69 |
: 0);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if (virtualChapter <= masterZone->virtualChapterLow) {
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Moving backwards and the new range is totally before the old range.
|
|
Packit Service |
310c69 |
* Note that moving to the lowest virtual chapter counts as totally before
|
|
Packit Service |
310c69 |
* the old range, as we need to remove the entries in the open chapter.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
emptyDeltaIndexZone(&mi5->deltaIndex, zoneNumber);
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow = virtualChapter;
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh = virtualChapter;
|
|
Packit Service |
310c69 |
} else if (virtualChapter <= masterZone->virtualChapterHigh) {
|
|
Packit Service |
310c69 |
// Moving backwards and the new range overlaps the old range. Note
|
|
Packit Service |
310c69 |
// that moving to the same open chapter counts as backwards, as we need
|
|
Packit Service |
310c69 |
// to remove the entries in the open chapter.
|
|
Packit Service |
310c69 |
removeNewestChapters(mi5, zoneNumber, virtualChapter);
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh = virtualChapter;
|
|
Packit Service |
310c69 |
} else if (newVirtualLow < masterZone->virtualChapterLow) {
|
|
Packit Service |
310c69 |
// Moving forwards and we can keep all the old chapters
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh = virtualChapter;
|
|
Packit Service |
310c69 |
} else if (newVirtualLow <= masterZone->virtualChapterHigh) {
|
|
Packit Service |
310c69 |
// Moving forwards and we can keep some old chapters
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow = newVirtualLow;
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh = virtualChapter;
|
|
Packit Service |
310c69 |
} else {
|
|
Packit Service |
310c69 |
// Moving forwards and the new range is totally after the old range
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow = virtualChapter;
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh = virtualChapter;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
// Check to see if the zone data has grown to be too large
|
|
Packit Service |
310c69 |
if (masterZone->virtualChapterLow < masterZone->virtualChapterHigh) {
|
|
Packit Service |
310c69 |
uint64_t usedBits = getDeltaIndexZoneDlistBitsUsed(&mi5->deltaIndex,
|
|
Packit Service |
310c69 |
zoneNumber);
|
|
Packit Service |
310c69 |
if (usedBits > mi5->maxZoneBits) {
|
|
Packit Service |
310c69 |
// Expire enough chapters to free the desired space
|
|
Packit Service |
310c69 |
uint64_t expireCount
|
|
Packit Service |
310c69 |
= 1 + (usedBits - mi5->maxZoneBits) / mi5->chapterZoneBits;
|
|
Packit Service |
310c69 |
if (expireCount == 1) {
|
|
Packit Service |
310c69 |
logRatelimit(logInfo,
|
|
Packit Service |
310c69 |
"masterZone %u: At chapter %" PRIu64
|
|
Packit Service |
310c69 |
", expiring chapter %llu early",
|
|
Packit Service |
310c69 |
zoneNumber, virtualChapter,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow);
|
|
Packit Service |
310c69 |
masterZone->numEarlyFlushes++;
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow++;
|
|
Packit Service |
310c69 |
} else {
|
|
Packit Service |
310c69 |
uint64_t firstExpired = masterZone->virtualChapterLow;
|
|
Packit Service |
310c69 |
if (firstExpired + expireCount < masterZone->virtualChapterHigh) {
|
|
Packit Service |
310c69 |
masterZone->numEarlyFlushes += expireCount;
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow += expireCount;
|
|
Packit Service |
310c69 |
} else {
|
|
Packit Service |
310c69 |
masterZone->numEarlyFlushes
|
|
Packit Service |
310c69 |
+= masterZone->virtualChapterHigh - masterZone->virtualChapterLow;
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow = masterZone->virtualChapterHigh;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
logRatelimit(logInfo,
|
|
Packit Service |
310c69 |
"masterZone %u: At chapter %" PRIu64
|
|
Packit Service |
310c69 |
", expiring chapters %llu to %llu early",
|
|
Packit Service |
310c69 |
zoneNumber, virtualChapter, firstExpired,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow - 1);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Set the open chapter number. The master index will be modified to index
|
|
Packit Service |
310c69 |
* the proper number of chapters ending with the new open chapter.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param virtualChapter The new open chapter number
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void setMasterIndexOpenChapter_005(MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
uint64_t virtualChapter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5 = container_of(masterIndex, MasterIndex5, common);
|
|
Packit Service |
310c69 |
unsigned int z;
|
|
Packit Service |
310c69 |
for (z = 0; z < mi5->numZones; z++) {
|
|
Packit Service |
310c69 |
// In normal operation, we advance forward one chapter at a time.
|
|
Packit Service |
310c69 |
// Log all abnormal changes.
|
|
Packit Service |
310c69 |
MasterIndexZone *masterZone = &mi5->masterZones[z];
|
|
Packit Service |
310c69 |
bool logMove = virtualChapter != masterZone->virtualChapterHigh + 1;
|
|
Packit Service |
310c69 |
if (logMove) {
|
|
Packit Service |
310c69 |
logDebug("masterZone %u: The range of indexed chapters is moving from [%"
|
|
Packit Service |
310c69 |
PRIu64 ", %llu] ...",
|
|
Packit Service |
310c69 |
z,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
setMasterIndexZoneOpenChapter_005(masterIndex, z, virtualChapter);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if (logMove) {
|
|
Packit Service |
310c69 |
logDebug("masterZone %u: ... and moving to [%llu, %llu]",
|
|
Packit Service |
310c69 |
z,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Find the master index zone associated with a chunk name
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param name The chunk name
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return the zone that the chunk name belongs to
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static unsigned int getMasterIndexZone_005(const MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
const UdsChunkName *name)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
unsigned int deltaListNumber = extractDListNum(mi5, name);
|
|
Packit Service |
310c69 |
return getDeltaIndexZone(&mi5->deltaIndex, deltaListNumber);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Do a quick read-only lookup of the chunk name and return information
|
|
Packit Service |
310c69 |
* needed by the index code to process the chunk name.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param name The chunk name
|
|
Packit Service |
310c69 |
* @param triage Information about the chunk name
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int lookupMasterIndexName_005(const MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
const UdsChunkName *name,
|
|
Packit Service |
310c69 |
MasterIndexTriage *triage)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
triage->isSample = false;
|
|
Packit Service |
310c69 |
triage->inSampledChapter = false;
|
|
Packit Service |
310c69 |
triage->zone = getMasterIndexZone_005(masterIndex, name);
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Do a quick read-only lookup of the sampled chunk name and return
|
|
Packit Service |
310c69 |
* information needed by the index code to process the chunk name.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param name The chunk name
|
|
Packit Service |
310c69 |
* @param triage Information about the chunk name. The zone and
|
|
Packit Service |
310c69 |
* isSample fields are already filled in. Set
|
|
Packit Service |
310c69 |
* inSampledChapter and virtualChapter if the chunk
|
|
Packit Service |
310c69 |
* name is found in the index.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int lookupMasterIndexSampledName_005(const MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
const UdsChunkName *name,
|
|
Packit Service |
310c69 |
MasterIndexTriage *triage)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
unsigned int address = extractAddress(mi5, name);
|
|
Packit Service |
310c69 |
unsigned int deltaListNumber = extractDListNum(mi5, name);
|
|
Packit Service |
310c69 |
DeltaIndexEntry deltaEntry;
|
|
Packit Service |
310c69 |
int result = getDeltaIndexEntry(&mi5->deltaIndex, deltaListNumber, address,
|
|
Packit Service |
310c69 |
name->name, true, &deltaEntry);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
triage->inSampledChapter = !deltaEntry.atEnd && (deltaEntry.key == address);
|
|
Packit Service |
310c69 |
if (triage->inSampledChapter) {
|
|
Packit Service |
310c69 |
const MasterIndexZone *masterZone = &mi5->masterZones[triage->zone];
|
|
Packit Service |
310c69 |
unsigned int indexChapter = getDeltaEntryValue(&deltaEntry);
|
|
Packit Service |
310c69 |
unsigned int rollingChapter = ((indexChapter
|
|
Packit Service |
310c69 |
- masterZone->virtualChapterLow)
|
|
Packit Service |
310c69 |
& mi5->chapterMask);
|
|
Packit Service |
310c69 |
triage->virtualChapter = masterZone->virtualChapterLow + rollingChapter;
|
|
Packit Service |
310c69 |
if (triage->virtualChapter > masterZone->virtualChapterHigh) {
|
|
Packit Service |
310c69 |
triage->inSampledChapter = false;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Find the master index record associated with a block name
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* This is always the first routine to be called when dealing with a delta
|
|
Packit Service |
310c69 |
* master index entry. The fields of the record parameter should be
|
|
Packit Service |
310c69 |
* examined to determine the state of the record:
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* If isFound is false, then we did not find an entry for the block
|
|
Packit Service |
310c69 |
* name. Information is saved in the MasterIndexRecord so that
|
|
Packit Service |
310c69 |
* putMasterIndexRecord() will insert an entry for that block name at
|
|
Packit Service |
310c69 |
* the proper place.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* If isFound is true, then we did find an entry for the block name.
|
|
Packit Service |
310c69 |
* Information is saved in the MasterIndexRecord so that the "chapter"
|
|
Packit Service |
310c69 |
* and "isCollision" fields reflect the entry found.
|
|
Packit Service |
310c69 |
* Calls to removeMasterIndexRecord() will remove the entry, calls to
|
|
Packit Service |
310c69 |
* setMasterIndexRecordChapter() can modify the entry, and calls to
|
|
Packit Service |
310c69 |
* putMasterIndexRecord() can insert a collision record with this
|
|
Packit Service |
310c69 |
* entry.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index to search
|
|
Packit Service |
310c69 |
* @param name The chunk name
|
|
Packit Service |
310c69 |
* @param record Set to the info about the record searched for
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static int getMasterIndexRecord_005(MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
const UdsChunkName *name,
|
|
Packit Service |
310c69 |
MasterIndexRecord *record)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5 = container_of(masterIndex, MasterIndex5, common);
|
|
Packit Service |
310c69 |
unsigned int address = extractAddress(mi5, name);
|
|
Packit Service |
310c69 |
unsigned int deltaListNumber = extractDListNum(mi5, name);
|
|
Packit Service |
310c69 |
uint64_t flushChapter = mi5->flushChapters[deltaListNumber];
|
|
Packit Service |
310c69 |
record->magic = masterIndexRecordMagic;
|
|
Packit Service |
310c69 |
record->masterIndex = masterIndex;
|
|
Packit Service |
310c69 |
record->mutex = NULL;
|
|
Packit Service |
310c69 |
record->name = name;
|
|
Packit Service |
310c69 |
record->zoneNumber = getDeltaIndexZone(&mi5->deltaIndex, deltaListNumber);
|
|
Packit Service |
310c69 |
const MasterIndexZone *masterZone = getMasterZone(record);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
int result;
|
|
Packit Service |
310c69 |
if (flushChapter < masterZone->virtualChapterLow) {
|
|
Packit Service |
310c69 |
ChapterRange range;
|
|
Packit Service |
310c69 |
uint64_t flushCount = masterZone->virtualChapterLow - flushChapter;
|
|
Packit Service |
310c69 |
range.chapterStart = convertVirtualToIndex(mi5, flushChapter);
|
|
Packit Service |
310c69 |
range.chapterCount = (flushCount > mi5->chapterMask
|
|
Packit Service |
310c69 |
? mi5->chapterMask + 1
|
|
Packit Service |
310c69 |
: flushCount);
|
|
Packit Service |
310c69 |
result = getMasterIndexEntry(record, deltaListNumber, address, &range);
|
|
Packit Service |
310c69 |
flushChapter = convertIndexToVirtual(record, range.chapterStart);
|
|
Packit Service |
310c69 |
if (flushChapter > masterZone->virtualChapterHigh) {
|
|
Packit Service |
310c69 |
flushChapter = masterZone->virtualChapterHigh;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
mi5->flushChapters[deltaListNumber] = flushChapter;
|
|
Packit Service |
310c69 |
} else {
|
|
Packit Service |
310c69 |
result = getDeltaIndexEntry(&mi5->deltaIndex, deltaListNumber, address,
|
|
Packit Service |
310c69 |
name->name, false, &record->deltaEntry);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
record->isFound = (!record->deltaEntry.atEnd
|
|
Packit Service |
310c69 |
&& (record->deltaEntry.key == address));
|
|
Packit Service |
310c69 |
if (record->isFound) {
|
|
Packit Service |
310c69 |
unsigned int indexChapter = getDeltaEntryValue(&record->deltaEntry);
|
|
Packit Service |
310c69 |
record->virtualChapter = convertIndexToVirtual(record, indexChapter);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
record->isCollision = record->deltaEntry.isCollision;
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Create a new record associated with a block name.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param record The master index record found by getRecord()
|
|
Packit Service |
310c69 |
* @param virtualChapter The chapter number where block info is found
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
int putMasterIndexRecord(MasterIndexRecord *record, uint64_t virtualChapter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = container_of(record->masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
if (record->magic != masterIndexRecordMagic) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_BAD_STATE,
|
|
Packit Service |
310c69 |
"bad magic number in master index record");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (!isVirtualChapterIndexed(record, virtualChapter)) {
|
|
Packit Service |
310c69 |
const MasterIndexZone *masterZone = getMasterZone(record);
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_INVALID_ARGUMENT,
|
|
Packit Service |
310c69 |
"cannot put record into chapter number %"
|
|
Packit Service |
310c69 |
PRIu64 " that is out of the valid range %"
|
|
Packit Service |
310c69 |
PRIu64 " to %llu",
|
|
Packit Service |
310c69 |
virtualChapter,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
unsigned int address = extractAddress(mi5, record->name);
|
|
Packit Service |
310c69 |
if (unlikely(record->mutex != NULL)) {
|
|
Packit Service |
310c69 |
lockMutex(record->mutex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
int result = putDeltaIndexEntry(&record->deltaEntry, address,
|
|
Packit Service |
310c69 |
convertVirtualToIndex(mi5, virtualChapter),
|
|
Packit Service |
310c69 |
record->isFound ? record->name->name : NULL);
|
|
Packit Service |
310c69 |
if (unlikely(record->mutex != NULL)) {
|
|
Packit Service |
310c69 |
unlockMutex(record->mutex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
switch (result) {
|
|
Packit Service |
310c69 |
case UDS_SUCCESS:
|
|
Packit Service |
310c69 |
record->virtualChapter = virtualChapter;
|
|
Packit Service |
310c69 |
record->isCollision = record->deltaEntry.isCollision;
|
|
Packit Service |
310c69 |
record->isFound = true;
|
|
Packit Service |
310c69 |
break;
|
|
Packit Service |
310c69 |
case UDS_OVERFLOW:
|
|
Packit Service |
310c69 |
logRatelimit(logWarningWithStringError, UDS_OVERFLOW,
|
|
Packit Service |
310c69 |
"Master index entry dropped due to overflow condition");
|
|
Packit Service |
310c69 |
logDeltaIndexEntry(&record->deltaEntry);
|
|
Packit Service |
310c69 |
break;
|
|
Packit Service |
310c69 |
default:
|
|
Packit Service |
310c69 |
break;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/**********************************************************************/
|
|
Packit Service |
310c69 |
static INLINE int validateRecord(MasterIndexRecord *record)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
if (record->magic != masterIndexRecordMagic) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(
|
|
Packit Service |
310c69 |
UDS_BAD_STATE, "bad magic number in master index record");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (!record->isFound) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_BAD_STATE,
|
|
Packit Service |
310c69 |
"illegal operation on new record");
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Remove an existing record.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param record The master index record found by getRecord()
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
int removeMasterIndexRecord(MasterIndexRecord *record)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
int result = validateRecord(record);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
// Mark the record so that it cannot be used again
|
|
Packit Service |
310c69 |
record->magic = badMagic;
|
|
Packit Service |
310c69 |
if (unlikely(record->mutex != NULL)) {
|
|
Packit Service |
310c69 |
lockMutex(record->mutex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = removeDeltaIndexEntry(&record->deltaEntry);
|
|
Packit Service |
310c69 |
if (unlikely(record->mutex != NULL)) {
|
|
Packit Service |
310c69 |
unlockMutex(record->mutex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Set the chapter number associated with a block name.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param record The master index record found by getRecord()
|
|
Packit Service |
310c69 |
* @param virtualChapter The chapter number where the block info is now found.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return UDS_SUCCESS or an error code
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
int setMasterIndexRecordChapter(MasterIndexRecord *record,
|
|
Packit Service |
310c69 |
uint64_t virtualChapter)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = container_of(record->masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
int result = validateRecord(record);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (!isVirtualChapterIndexed(record, virtualChapter)) {
|
|
Packit Service |
310c69 |
const MasterIndexZone *masterZone = getMasterZone(record);
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_INVALID_ARGUMENT,
|
|
Packit Service |
310c69 |
"cannot set chapter number %" PRIu64
|
|
Packit Service |
310c69 |
" that is out of the valid range %" PRIu64
|
|
Packit Service |
310c69 |
" to %llu",
|
|
Packit Service |
310c69 |
virtualChapter,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterLow,
|
|
Packit Service |
310c69 |
masterZone->virtualChapterHigh);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (unlikely(record->mutex != NULL)) {
|
|
Packit Service |
310c69 |
lockMutex(record->mutex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
result = setDeltaEntryValue(&record->deltaEntry,
|
|
Packit Service |
310c69 |
convertVirtualToIndex(mi5, virtualChapter));
|
|
Packit Service |
310c69 |
if (unlikely(record->mutex != NULL)) {
|
|
Packit Service |
310c69 |
unlockMutex(record->mutex);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
record->virtualChapter = virtualChapter;
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Get the number of bytes used for master index entries.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return The number of bytes in use
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static size_t getMasterIndexMemoryUsed_005(const MasterIndex *masterIndex)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
uint64_t bits = getDeltaIndexDlistBitsUsed(&mi5->deltaIndex);
|
|
Packit Service |
310c69 |
return (bits + CHAR_BIT - 1) / CHAR_BIT;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Return the master index stats. There is only one portion of the master
|
|
Packit Service |
310c69 |
* index in this implementation, and we call it the dense portion of the
|
|
Packit Service |
310c69 |
* index.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param dense Stats for the dense portion of the index
|
|
Packit Service |
310c69 |
* @param sparse Stats for the sparse portion of the index
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static void getMasterIndexStats_005(const MasterIndex *masterIndex,
|
|
Packit Service |
310c69 |
MasterIndexStats *dense,
|
|
Packit Service |
310c69 |
MasterIndexStats *sparse)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
const MasterIndex5 *mi5 = const_container_of(masterIndex, MasterIndex5,
|
|
Packit Service |
310c69 |
common);
|
|
Packit Service |
310c69 |
DeltaIndexStats dis;
|
|
Packit Service |
310c69 |
getDeltaIndexStats(&mi5->deltaIndex, &dis);
|
|
Packit Service |
310c69 |
dense->memoryAllocated = (dis.memoryAllocated
|
|
Packit Service |
310c69 |
+ sizeof(MasterIndex5)
|
|
Packit Service |
310c69 |
+ mi5->numDeltaLists * sizeof(uint64_t)
|
|
Packit Service |
310c69 |
+ mi5->numZones * sizeof(MasterIndexZone));
|
|
Packit Service |
310c69 |
dense->rebalanceTime = dis.rebalanceTime;
|
|
Packit Service |
310c69 |
dense->rebalanceCount = dis.rebalanceCount;
|
|
Packit Service |
310c69 |
dense->recordCount = dis.recordCount;
|
|
Packit Service |
310c69 |
dense->collisionCount = dis.collisionCount;
|
|
Packit Service |
310c69 |
dense->discardCount = dis.discardCount;
|
|
Packit Service |
310c69 |
dense->overflowCount = dis.overflowCount;
|
|
Packit Service |
310c69 |
dense->numLists = dis.numLists;
|
|
Packit Service |
310c69 |
dense->earlyFlushes = 0;
|
|
Packit Service |
310c69 |
unsigned int z;
|
|
Packit Service |
310c69 |
for (z = 0; z < mi5->numZones; z++) {
|
|
Packit Service |
310c69 |
dense->earlyFlushes += mi5->masterZones[z].numEarlyFlushes;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
memset(sparse, 0, sizeof(MasterIndexStats));
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
/**
|
|
Packit Service |
310c69 |
* Determine whether a given chunk name is a hook.
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @param masterIndex The master index
|
|
Packit Service |
310c69 |
* @param name The block name
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* @return whether to use as sample
|
|
Packit Service |
310c69 |
**/
|
|
Packit Service |
310c69 |
static bool isMasterIndexSample_005(const MasterIndex *masterIndex
|
|
Packit Service |
310c69 |
__attribute__((unused)),
|
|
Packit Service |
310c69 |
const UdsChunkName *name
|
|
Packit Service |
310c69 |
__attribute__((unused)))
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
return false;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
typedef struct {
|
|
Packit Service |
310c69 |
unsigned int addressBits; // Number of bits in address mask
|
|
Packit Service |
310c69 |
unsigned int chapterBits; // Number of bits in chapter number
|
|
Packit Service |
310c69 |
unsigned int meanDelta; // The mean delta
|
|
Packit Service |
310c69 |
unsigned long numDeltaLists; // The number of delta lists
|
|
Packit Service |
310c69 |
unsigned long numChapters; // Number of chapters used
|
|
Packit Service |
310c69 |
size_t numBitsPerChapter; // The number of bits per chapter
|
|
Packit Service |
310c69 |
size_t memorySize; // The number of bytes of delta list memory
|
|
Packit Service |
310c69 |
size_t targetFreeSize; // The number of free bytes we desire
|
|
Packit Service |
310c69 |
} Parameters005;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
static int computeMasterIndexParameters005(const Configuration *config,
|
|
Packit Service |
310c69 |
Parameters005 *params)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
enum { DELTA_LIST_SIZE = 256 };
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* For a given zone count, setting the the minimum number of delta lists
|
|
Packit Service |
310c69 |
* to the square of the number of zones ensures that the distribution of
|
|
Packit Service |
310c69 |
* delta lists over zones doesn't underflow, leaving the last zone with
|
|
Packit Service |
310c69 |
* an invalid number of delta lists. See the explanation in
|
|
Packit Service |
310c69 |
* initializeDeltaIndex(). Because we can restart with a different number
|
|
Packit Service |
310c69 |
* of zones but the number of delta lists is invariant across restart,
|
|
Packit Service |
310c69 |
* we must use the largest number of zones to compute this minimum.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
unsigned long minDeltaLists = (minMasterIndexDeltaLists
|
|
Packit Service |
310c69 |
? minMasterIndexDeltaLists
|
|
Packit Service |
310c69 |
: MAX_ZONES * MAX_ZONES);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
Geometry *geometry = config->geometry;
|
|
Packit Service |
310c69 |
unsigned long recordsPerChapter = geometry->recordsPerChapter;
|
|
Packit Service |
310c69 |
params->numChapters = geometry->chaptersPerVolume;
|
|
Packit Service |
310c69 |
unsigned long recordsPerVolume = recordsPerChapter * params->numChapters;
|
|
Packit Service |
310c69 |
unsigned int numAddresses = config->masterIndexMeanDelta * DELTA_LIST_SIZE;
|
|
Packit Service |
310c69 |
params->numDeltaLists
|
|
Packit Service |
310c69 |
= maxUint(recordsPerVolume / DELTA_LIST_SIZE, minDeltaLists);
|
|
Packit Service |
310c69 |
params->addressBits = computeBits(numAddresses - 1);
|
|
Packit Service |
310c69 |
params->chapterBits = computeBits(params->numChapters - 1);
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if ((unsigned int) params->numDeltaLists != params->numDeltaLists) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_INVALID_ARGUMENT,
|
|
Packit Service |
310c69 |
"cannot initialize master index with %lu"
|
|
Packit Service |
310c69 |
" delta lists",
|
|
Packit Service |
310c69 |
params->numDeltaLists);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (params->addressBits > 31) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_INVALID_ARGUMENT,
|
|
Packit Service |
310c69 |
"cannot initialize master index with %u"
|
|
Packit Service |
310c69 |
" address bits",
|
|
Packit Service |
310c69 |
params->addressBits);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (geometry->sparseChaptersPerVolume > 0) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_INVALID_ARGUMENT,
|
|
Packit Service |
310c69 |
"cannot initialize dense master index"
|
|
Packit Service |
310c69 |
" with %u sparse chapters",
|
|
Packit Service |
310c69 |
geometry->sparseChaptersPerVolume);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (recordsPerChapter == 0) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_INVALID_ARGUMENT,
|
|
Packit Service |
310c69 |
"cannot initialize master index with %lu"
|
|
Packit Service |
310c69 |
" records per chapter",
|
|
Packit Service |
310c69 |
recordsPerChapter);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
if (params->numChapters == 0) {
|
|
Packit Service |
310c69 |
return logWarningWithStringError(UDS_INVALID_ARGUMENT,
|
|
Packit Service |
310c69 |
"cannot initialize master index with %lu"
|
|
Packit Service |
310c69 |
" chapters per volume",
|
|
Packit Service |
310c69 |
params->numChapters);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* We can now compute the probability that a delta list is not touched during
|
|
Packit Service |
310c69 |
* the writing of an entire chapter. The computation is:
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* double pNotTouched = pow((double) (params->numDeltaLists - 1)
|
|
Packit Service |
310c69 |
* / params->numDeltaLists,
|
|
Packit Service |
310c69 |
* recordsPerChapter);
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* For the standard index sizes, about 78% of the delta lists are not
|
|
Packit Service |
310c69 |
* touched, and therefore contain dead index entries that have not been
|
|
Packit Service |
310c69 |
* eliminated by the lazy LRU processing. We can then compute how many dead
|
|
Packit Service |
310c69 |
* index entries accumulate over time. The computation is:
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* double invalidChapters = pNotTouched / (1.0 - pNotTouched);
|
|
Packit Service |
310c69 |
*
|
|
Packit Service |
310c69 |
* For the standard index sizes, we will need about 3.5 chapters of space for
|
|
Packit Service |
310c69 |
* the dead index entries in a 1K chapter index. Since we do not want to do
|
|
Packit Service |
310c69 |
* that floating point computation, we use 4 chapters per 1K of chapters.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
unsigned long invalidChapters = maxUint(params->numChapters / 256, 2);
|
|
Packit Service |
310c69 |
unsigned long chaptersInMasterIndex = params->numChapters + invalidChapters;
|
|
Packit Service |
310c69 |
unsigned long entriesInMasterIndex
|
|
Packit Service |
310c69 |
= recordsPerChapter * chaptersInMasterIndex;
|
|
Packit Service |
310c69 |
// Compute the mean delta
|
|
Packit Service |
310c69 |
unsigned long addressSpan = params->numDeltaLists << params->addressBits;
|
|
Packit Service |
310c69 |
params->meanDelta = addressSpan / entriesInMasterIndex;
|
|
Packit Service |
310c69 |
// Project how large we expect a chapter to be
|
|
Packit Service |
310c69 |
params->numBitsPerChapter = getDeltaMemorySize(recordsPerChapter,
|
|
Packit Service |
310c69 |
params->meanDelta,
|
|
Packit Service |
310c69 |
params->chapterBits);
|
|
Packit Service |
310c69 |
// Project how large we expect the index to be
|
|
Packit Service |
310c69 |
size_t numBitsPerIndex = params->numBitsPerChapter * chaptersInMasterIndex;
|
|
Packit Service |
310c69 |
size_t expectedIndexSize = numBitsPerIndex / CHAR_BIT;
|
|
Packit Service |
310c69 |
/*
|
|
Packit Service |
310c69 |
* Set the total memory to be 6% larger than the expected index size. We
|
|
Packit Service |
310c69 |
* want this number to be large enough that the we do not do a great many
|
|
Packit Service |
310c69 |
* rebalances as the list when the list is full. We use MasterIndex_p1
|
|
Packit Service |
310c69 |
* to tune this setting.
|
|
Packit Service |
310c69 |
*/
|
|
Packit Service |
310c69 |
params->memorySize = expectedIndexSize * 106 / 100;
|
|
Packit Service |
310c69 |
// Set the target free size to 5% of the expected index size
|
|
Packit Service |
310c69 |
params->targetFreeSize = expectedIndexSize / 20;
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
int computeMasterIndexSaveBytes005(const Configuration *config,
|
|
Packit Service |
310c69 |
size_t *numBytes)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
Parameters005 params = { .addressBits = 0 };
|
|
Packit Service |
310c69 |
int result = computeMasterIndexParameters005(config, ¶ms);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
// Saving a MasterIndex005 needs a header plus one uint64_t per delta
|
|
Packit Service |
310c69 |
// list plus the delta index.
|
|
Packit Service |
310c69 |
*numBytes = (sizeof(struct mi005_data)
|
|
Packit Service |
310c69 |
+ params.numDeltaLists * sizeof(uint64_t)
|
|
Packit Service |
310c69 |
+ computeDeltaIndexSaveBytes(params.numDeltaLists,
|
|
Packit Service |
310c69 |
params.memorySize));
|
|
Packit Service |
310c69 |
return UDS_SUCCESS;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
/***********************************************************************/
|
|
Packit Service |
310c69 |
int makeMasterIndex005(const Configuration *config, unsigned int numZones,
|
|
Packit Service |
310c69 |
uint64_t volumeNonce, MasterIndex **masterIndex)
|
|
Packit Service |
310c69 |
{
|
|
Packit Service |
310c69 |
Parameters005 params = { .addressBits = 0 };
|
|
Packit Service |
310c69 |
int result = computeMasterIndexParameters005(config, ¶ms);
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
MasterIndex5 *mi5;
|
|
Packit Service |
310c69 |
result = ALLOCATE(1, MasterIndex5, "master index", &mi5;;
|
|
Packit Service |
310c69 |
if (result != UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
*masterIndex = NULL;
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
mi5->common.abortRestoringMasterIndex = abortRestoringMasterIndex_005;
|
|
Packit Service |
310c69 |
mi5->common.abortSavingMasterIndex = abortSavingMasterIndex_005;
|
|
Packit Service |
310c69 |
mi5->common.finishSavingMasterIndex = finishSavingMasterIndex_005;
|
|
Packit Service |
310c69 |
mi5->common.freeMasterIndex = freeMasterIndex_005;
|
|
Packit Service |
310c69 |
mi5->common.getMasterIndexMemoryUsed = getMasterIndexMemoryUsed_005;
|
|
Packit Service |
310c69 |
mi5->common.getMasterIndexRecord = getMasterIndexRecord_005;
|
|
Packit Service |
310c69 |
mi5->common.getMasterIndexStats = getMasterIndexStats_005;
|
|
Packit Service |
310c69 |
mi5->common.getMasterIndexZone = getMasterIndexZone_005;
|
|
Packit Service |
310c69 |
mi5->common.isMasterIndexSample = isMasterIndexSample_005;
|
|
Packit Service |
310c69 |
mi5->common.isRestoringMasterIndexDone = isRestoringMasterIndexDone_005;
|
|
Packit Service |
310c69 |
mi5->common.isSavingMasterIndexDone = isSavingMasterIndexDone_005;
|
|
Packit Service |
310c69 |
mi5->common.lookupMasterIndexName = lookupMasterIndexName_005;
|
|
Packit Service |
310c69 |
mi5->common.lookupMasterIndexSampledName = lookupMasterIndexSampledName_005;
|
|
Packit Service |
310c69 |
mi5->common.restoreDeltaListToMasterIndex = restoreDeltaListToMasterIndex_005;
|
|
Packit Service |
310c69 |
mi5->common.setMasterIndexOpenChapter = setMasterIndexOpenChapter_005;
|
|
Packit Service |
310c69 |
mi5->common.setMasterIndexTag = setMasterIndexTag_005;
|
|
Packit Service |
310c69 |
mi5->common.setMasterIndexZoneOpenChapter = setMasterIndexZoneOpenChapter_005;
|
|
Packit Service |
310c69 |
mi5->common.startRestoringMasterIndex = startRestoringMasterIndex_005;
|
|
Packit Service |
310c69 |
mi5->common.startSavingMasterIndex = startSavingMasterIndex_005;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
mi5->addressBits = params.addressBits;
|
|
Packit Service |
310c69 |
mi5->addressMask = (1u << params.addressBits) - 1;
|
|
Packit Service |
310c69 |
mi5->chapterBits = params.chapterBits;
|
|
Packit Service |
310c69 |
mi5->chapterMask = (1u << params.chapterBits) - 1;
|
|
Packit Service |
310c69 |
mi5->numChapters = params.numChapters;
|
|
Packit Service |
310c69 |
mi5->numDeltaLists = params.numDeltaLists;
|
|
Packit Service |
310c69 |
mi5->numZones = numZones;
|
|
Packit Service |
310c69 |
mi5->chapterZoneBits = params.numBitsPerChapter / numZones;
|
|
Packit Service |
310c69 |
mi5->volumeNonce = volumeNonce;
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
result = initializeDeltaIndex(&mi5->deltaIndex, numZones,
|
|
Packit Service |
310c69 |
params.numDeltaLists, params.meanDelta,
|
|
Packit Service |
310c69 |
params.chapterBits, params.memorySize);
|
|
Packit Service |
310c69 |
if (result == UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
mi5->maxZoneBits = ((getDeltaIndexDlistBitsAllocated(&mi5->deltaIndex)
|
|
Packit Service |
310c69 |
- params.targetFreeSize * CHAR_BIT)
|
|
Packit Service |
310c69 |
/ numZones);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Initialize the chapter flush ranges to be empty. This depends upon
|
|
Packit Service |
310c69 |
// allocate returning zeroed memory.
|
|
Packit Service |
310c69 |
if (result == UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
result = ALLOCATE(params.numDeltaLists, uint64_t,
|
|
Packit Service |
310c69 |
"first chapter to flush", &mi5->flushChapters);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
// Initialize the virtual chapter ranges to start at zero. This depends
|
|
Packit Service |
310c69 |
// upon allocate returning zeroed memory.
|
|
Packit Service |
310c69 |
if (result == UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
result = ALLOCATE(numZones, MasterIndexZone, "master index zones",
|
|
Packit Service |
310c69 |
&mi5->masterZones);
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
|
|
Packit Service |
310c69 |
if (result == UDS_SUCCESS) {
|
|
Packit Service |
310c69 |
*masterIndex = &mi5->common;
|
|
Packit Service |
310c69 |
} else {
|
|
Packit Service |
310c69 |
freeMasterIndex_005(&mi5->common);
|
|
Packit Service |
310c69 |
*masterIndex = NULL;
|
|
Packit Service |
310c69 |
}
|
|
Packit Service |
310c69 |
return result;
|
|
Packit Service |
310c69 |
}
|