/*
* Copyright (c) 2020 Red Hat, Inc.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301, USA.
*
* $Id: //eng/uds-releases/jasper/src/uds/chapterIndex.c#5 $
*/
#include "chapterIndex.h"
#include "compiler.h"
#include "errors.h"
#include "hashUtils.h"
#include "logger.h"
#include "memoryAlloc.h"
#include "permassert.h"
#include "uds.h"
/**********************************************************************/
int makeOpenChapterIndex(OpenChapterIndex **openChapterIndex,
const Geometry *geometry,
bool chapterIndexHeaderNativeEndian,
uint64_t volumeNonce)
{
int result = ALLOCATE(1, OpenChapterIndex, "open chapter index",
openChapterIndex);
if (result != UDS_SUCCESS) {
return result;
}
// The delta index will rebalance delta lists when memory gets tight, so
// give the chapter index one extra page.
size_t memorySize
= (geometry->indexPagesPerChapter + 1) * geometry->bytesPerPage;
(*openChapterIndex)->geometry = geometry;
(*openChapterIndex)->volumeNonce = volumeNonce;
(*openChapterIndex)->headerNativeEndian = chapterIndexHeaderNativeEndian,
result = initializeDeltaIndex(&(*openChapterIndex)->deltaIndex, 1,
geometry->deltaListsPerChapter,
geometry->chapterMeanDelta,
geometry->chapterPayloadBits, memorySize);
if (result != UDS_SUCCESS) {
FREE(*openChapterIndex);
*openChapterIndex = NULL;
}
return result;
}
/**********************************************************************/
void freeOpenChapterIndex(OpenChapterIndex *openChapterIndex)
{
if (openChapterIndex == NULL) {
return;
}
uninitializeDeltaIndex(&openChapterIndex->deltaIndex);
FREE(openChapterIndex);
}
/**********************************************************************/
void emptyOpenChapterIndex(OpenChapterIndex *openChapterIndex,
uint64_t virtualChapterNumber)
{
emptyDeltaIndex(&openChapterIndex->deltaIndex);
openChapterIndex->virtualChapterNumber = virtualChapterNumber;
}
/**
* Check whether a delta list entry reflects a successful search for a given
* address.
*
* @param entry the delta list entry from the search
* @param address the address of the desired entry
*
* @return <code>true</code> iff the address was found
**/
static INLINE bool wasEntryFound(const DeltaIndexEntry *entry,
unsigned int address)
{
return (!entry->atEnd && (entry->key == address));
}
/**********************************************************************/
int putOpenChapterIndexRecord(OpenChapterIndex *openChapterIndex,
const UdsChunkName *name,
unsigned int pageNumber)
{
const Geometry *geometry = openChapterIndex->geometry;
int result
= ASSERT_WITH_ERROR_CODE(pageNumber < geometry->recordPagesPerChapter,
UDS_INVALID_ARGUMENT,
"Page number within chapter (%u) exceeds"
" the maximum value %u",
pageNumber, geometry->recordPagesPerChapter);
if (result != UDS_SUCCESS) {
return result;
}
DeltaIndexEntry entry;
unsigned int address = hashToChapterDeltaAddress(name, geometry);
result = getDeltaIndexEntry(&openChapterIndex->deltaIndex,
hashToChapterDeltaList(name, geometry),
address, name->name, false, &entry);
if (result != UDS_SUCCESS) {
return result;
}
bool found = wasEntryFound(&entry, address);
result = ASSERT_WITH_ERROR_CODE(!(found && entry.isCollision),
UDS_BAD_STATE,
"Chunk appears more than once in chapter %"
PRIu64,
openChapterIndex->virtualChapterNumber);
if (result != UDS_SUCCESS) {
return result;
}
return putDeltaIndexEntry(&entry, address, pageNumber,
(found ? name->name : NULL));
}
/**********************************************************************/
int packOpenChapterIndexPage(OpenChapterIndex *openChapterIndex,
byte *memory,
unsigned int firstList,
bool lastPage,
unsigned int *numLists)
{
DeltaIndex *deltaIndex = &openChapterIndex->deltaIndex;
const Geometry *geometry = openChapterIndex->geometry;
unsigned int removals = 0;
for (;;) {
int result = packDeltaIndexPage(deltaIndex, openChapterIndex->volumeNonce,
openChapterIndex->headerNativeEndian,
memory, geometry->bytesPerPage,
openChapterIndex->virtualChapterNumber,
firstList, numLists);
if (result != UDS_SUCCESS) {
return result;
}
if ((firstList + *numLists) == geometry->deltaListsPerChapter) {
// All lists are packed
break;
} else if (*numLists == 0) {
// The next delta list does not fit on a page. This delta list will
// be removed.
} else if (lastPage) {
/*
* This is the last page and there are lists left unpacked, but all of
* the remaining lists must fit on the page. Find a list that contains
* entries and remove the entire list. Try the first list that does not
* fit. If it is empty, we will select the last list that already fits
* and has any entries.
*/
} else {
// This page is done
break;
}
if (removals == 0) {
DeltaIndexStats stats;
getDeltaIndexStats(deltaIndex, &stats);
logWarning("The chapter index for chapter %" PRIu64
" contains %ld entries with %ld collisions",
openChapterIndex->virtualChapterNumber,
stats.recordCount, stats.collisionCount);
}
DeltaIndexEntry entry;
int listNumber = *numLists;
do {
if (listNumber < 0) {
return UDS_OVERFLOW;
}
result = startDeltaIndexSearch(deltaIndex, firstList + listNumber--,
0, false, &entry);
if (result != UDS_SUCCESS) {
return result;
}
result = nextDeltaIndexEntry(&entry);
if (result != UDS_SUCCESS) {
return result;
}
} while (entry.atEnd);
do {
result = removeDeltaIndexEntry(&entry);
if (result != UDS_SUCCESS) {
return result;
}
removals++;
} while (!entry.atEnd);
}
if (removals > 0) {
logWarning("To avoid chapter index page overflow in chapter %" PRIu64
", %u entries were removed from the chapter index",
openChapterIndex->virtualChapterNumber, removals);
}
return UDS_SUCCESS;
}
/**********************************************************************/
int getOpenChapterIndexSize(OpenChapterIndex *openChapterIndex)
{
DeltaIndexStats stats;
getDeltaIndexStats(&openChapterIndex->deltaIndex, &stats);
return stats.recordCount;
}
/**********************************************************************/
size_t getOpenChapterIndexMemoryAllocated(OpenChapterIndex *openChapterIndex)
{
DeltaIndexStats stats;
getDeltaIndexStats(&openChapterIndex->deltaIndex, &stats);
return stats.memoryAllocated + sizeof(OpenChapterIndex);
}
/**********************************************************************/
int initializeChapterIndexPage(DeltaIndexPage *chapterIndexPage,
const Geometry *geometry,
byte *indexPage,
uint64_t volumeNonce)
{
return initializeDeltaIndexPage(chapterIndexPage, volumeNonce,
geometry->chapterMeanDelta,
geometry->chapterPayloadBits,
indexPage, geometry->bytesPerPage);
}
/**********************************************************************/
int validateChapterIndexPage(const DeltaIndexPage *chapterIndexPage,
const Geometry *geometry)
{
const DeltaIndex *deltaIndex = &chapterIndexPage->deltaIndex;
unsigned int first = chapterIndexPage->lowestListNumber;
unsigned int last = chapterIndexPage->highestListNumber;
// We walk every delta list from start to finish.
unsigned int listNumber;
for (listNumber = first; listNumber <= last; listNumber++) {
DeltaIndexEntry entry;
int result = startDeltaIndexSearch(deltaIndex, listNumber - first, 0, true,
&entry);
if (result != UDS_SUCCESS) {
return result;
}
for (;;) {
result = nextDeltaIndexEntry(&entry);
if (result != UDS_SUCCESS) {
if (result == UDS_CORRUPT_DATA) {
// A random bit stream is highly likely to arrive here when we go
// past the end of the delta list
return UDS_CORRUPT_COMPONENT;
}
return result;
}
if (entry.atEnd) {
break;
}
// Also make sure that the record page field contains a plausible value
if (getDeltaEntryValue(&entry) >= geometry->recordPagesPerChapter) {
// Do not log this as an error. It happens in normal operation when
// we are doing a rebuild but haven't written the entire volume once.
return UDS_CORRUPT_COMPONENT;
}
}
}
return UDS_SUCCESS;
}
/**********************************************************************/
int searchChapterIndexPage(DeltaIndexPage *chapterIndexPage,
const Geometry *geometry,
const UdsChunkName *name,
int *recordPagePtr)
{
DeltaIndex *deltaIndex = &chapterIndexPage->deltaIndex;
unsigned int address = hashToChapterDeltaAddress(name, geometry);
unsigned int deltaListNumber = hashToChapterDeltaList(name, geometry);
unsigned int subListNumber
= deltaListNumber - chapterIndexPage->lowestListNumber;;
DeltaIndexEntry entry;
int result = getDeltaIndexEntry(deltaIndex, subListNumber, address,
name->name, true, &entry);
if (result != UDS_SUCCESS) {
return result;
}
if (wasEntryFound(&entry, address)) {
*recordPagePtr = getDeltaEntryValue(&entry);
} else {
*recordPagePtr = NO_CHAPTER_INDEX_ENTRY;
}
return UDS_SUCCESS;
}