/*

 * 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 true 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;

}