/*

 * 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/geometry.h#3 $

 */

#ifndef GEOMETRY_H

#define GEOMETRY_H 1

#include "compiler.h"

#include "typeDefs.h"

#include "uds.h"

#include "uds-block.h"

/**

 * Geometry defines constants and a record that parameterize the layout of an

 * Albireo index volume.

 *

 * 
An index volume is divided into a fixed number of fixed-size

 * chapters, each consisting of a fixed number of fixed-size

 * pages. The volume layout is defined by two assumptions and four

 * parameters. The assumptions (constants) are that index records are

 * 64 bytes (32-byte block name plus 32-byte metadata) and that open

 * chapter index hash slots are one byte long. The four parameters are

 * the number of bytes in a page, the number of chapters in a volume,

 * the number of record pages in a chapter, and the number of chapters

 * that are sparse. From these parameters, we derive the rest of the

 * layout and derived properties, ranging from the number of pages in

 * a chapter to the number of records in the volume.

 *

 * 
The default geometry is 64 KByte pages, 1024 chapters, 256

 * record pages in a chapter, and zero sparse chapters. This will

 * allow us to store 2^28 entries (indexing 1TB of 4K blocks) in an

 * approximately 16.5 MByte volume using fourteen index pages in each

 * chapter.

 **/

typedef struct geometry {

  /** Length of a page in a chapter, in bytes */

  size_t bytesPerPage;

  /** Number of record pages in a chapter */

  unsigned int recordPagesPerChapter;

  /** Number of (total) chapters in a volume */

  unsigned int chaptersPerVolume;

  /** Number of sparsely-indexed chapters in a volume */

  unsigned int sparseChaptersPerVolume;

  /** Number of bits used to determine delta list numbers */

  unsigned int chapterDeltaListBits;

  // These are derived properties, expressed as fields for convenience.

  /** Total number of pages in a volume, excluding header */

  unsigned int pagesPerVolume;

  /** Total number of header pages per volume */

  unsigned int headerPagesPerVolume;

  /** Total number of bytes in a volume, including header */

  size_t bytesPerVolume;

  /** Total number of bytes in a chapter */

  size_t bytesPerChapter;

  /** Number of pages in a chapter */

  unsigned int pagesPerChapter;

  /** Number of index pages in a chapter index */

  unsigned int indexPagesPerChapter;

  /** The minimum ratio of hash slots to records in an open chapter */

  unsigned int openChapterLoadRatio;

  /** Number of records that fit on a page */

  unsigned int recordsPerPage;

  /** Number of records that fit in a chapter */

  unsigned int recordsPerChapter;

  /** Number of records that fit in a volume */

  uint64_t recordsPerVolume;

  /** Number of deltaLists per chapter index */

  unsigned int deltaListsPerChapter;

  /** Mean delta in chapter indexes */

  unsigned int chapterMeanDelta;

  /** Number of bits needed for record page numbers */

  unsigned int chapterPayloadBits;

  /** Number of bits used to compute addresses for chapter delta lists */

  unsigned int chapterAddressBits;

  /** Number of densely-indexed chapters in a volume */

  unsigned int denseChaptersPerVolume;

} Geometry;

enum {

  /* The number of bytes in a record (name + metadata) */

  BYTES_PER_RECORD = (UDS_CHUNK_NAME_SIZE + UDS_MAX_BLOCK_DATA_SIZE),

  /* The default length of a page in a chapter, in bytes */

  DEFAULT_BYTES_PER_PAGE = 1024 * BYTES_PER_RECORD,

  /* The default maximum number of records per page */

  DEFAULT_RECORDS_PER_PAGE = DEFAULT_BYTES_PER_PAGE / BYTES_PER_RECORD,

  /** The default number of record pages in a chapter */

  DEFAULT_RECORD_PAGES_PER_CHAPTER = 256,

  /** The default number of record pages in a chapter for a small index */

  SMALL_RECORD_PAGES_PER_CHAPTER = 64,

  /** The default number of chapters in a volume */

  DEFAULT_CHAPTERS_PER_VOLUME = 1024,

  /** The default number of sparsely-indexed chapters in a volume */

  DEFAULT_SPARSE_CHAPTERS_PER_VOLUME = 0,

  /** The log2 of the default mean delta */

  DEFAULT_CHAPTER_MEAN_DELTA_BITS = 16,

  /** The log2 of the number of delta lists in a large chapter */

  DEFAULT_CHAPTER_DELTA_LIST_BITS = 12,

  /** The log2 of the number of delta lists in a small chapter */

  SMALL_CHAPTER_DELTA_LIST_BITS = 10,

  /** The default min ratio of slots to records in an open chapter */

  DEFAULT_OPEN_CHAPTER_LOAD_RATIO = 2,

  /** Checkpoint every n chapters written.  Default is to not checkpoint */

  DEFAULT_CHECKPOINT_FREQUENCY = 0

};

/**

 * Allocate and initialize all fields of a volume geometry using the

 * specified layout parameters.

 *

 * @param bytesPerPage            The length of a page in a chapter, in bytes

 * @param recordPagesPerChapter   The number of pages in a chapter

 * @param chaptersPerVolume       The number of chapters in a volume

 * @param sparseChaptersPerVolume The number of sparse chapters in a volume

 * @param geometryPtr             A pointer to hold the new geometry

 *

 * @return UDS_SUCCESS or an error code

 **/

int makeGeometry(size_t       bytesPerPage,

                 unsigned int recordPagesPerChapter,

                 unsigned int chaptersPerVolume,

                 unsigned int sparseChaptersPerVolume,

                 Geometry   **geometryPtr)

  __attribute__((warn_unused_result));

/**

 * Allocate a new geometry and initialize it with the same parameters as an

 * existing geometry.

 *

 * @param source      The geometry record to copy

 * @param geometryPtr A pointer to hold the new geometry

 *

 * @return UDS_SUCCESS or an error code

 **/

int copyGeometry(Geometry  *source,

                 Geometry **geometryPtr)

  __attribute__((warn_unused_result));

/**

 * Clean up a geometry and its memory.

 *

 * @param geometry The geometry record to free

 **/

void freeGeometry(Geometry *geometry);

/**

 * Map a virtual chapter number to a physical chapter number

 *

 * @param geometry        The geometry

 * @param virtualChapter  The virtual chapter number

 *

 * @return the corresponding physical chapter number

 **/

__attribute__((warn_unused_result))

static INLINE unsigned int mapToPhysicalChapter(const Geometry *geometry,

                                                uint64_t virtualChapter)

{

  return (virtualChapter % geometry->chaptersPerVolume);

}

/**

 * Convert a physical chapter number to its current virtual chapter number.

 *

 * @param geometry             The geometry

 * @param newestVirtualChapter The number of the newest virtual chapter

 * @param physicalChapter      The physical chapter number to convert

 *

 * @return The current virtual chapter number of the physical chapter

 *         in question

 **/

uint64_t mapToVirtualChapterNumber(Geometry     *geometry,

                                   uint64_t      newestVirtualChapter,

                                   unsigned int  physicalChapter);

/**

 * Check whether this geometry is for a sparse index.

 *

 * @param geometry   The geometry to check

 *

 * @return true if this geometry has sparse chapters

 **/

__attribute__((warn_unused_result))

static INLINE bool isSparse(const Geometry *geometry)

{

  return (geometry->sparseChaptersPerVolume > 0);

}

/**

 * Check whether any sparse chapters have been filled.

 *

 * @param geometry             The geometry of the index

 * @param oldestVirtualChapter The number of the oldest chapter in the

 *                             index

 * @param newestVirtualChapter The number of the newest chapter in the

 *                             index

 *

 * @return true if the index has filled at least one sparse chapter

 **/

bool hasSparseChapters(const Geometry *geometry,

                       uint64_t        oldestVirtualChapter,

                       uint64_t        newestVirtualChapter)

  __attribute__((warn_unused_result));

/**

 * Check whether a chapter is sparse or dense.

 *

 * @param geometry             The geometry of the index containing the chapter

 * @param oldestVirtualChapter The number of the oldest chapter in the index

 * @param newestVirtualChapter The number of the newest chapter in the index

 * @param virtualChapterNumber The number of the chapter to check

 *

 * @return true if the chapter is sparse

 **/

bool isChapterSparse(const Geometry *geometry,

                     uint64_t        oldestVirtualChapter,

                     uint64_t        newestVirtualChapter,

                     uint64_t        virtualChapterNumber)

  __attribute__((warn_unused_result));

/**

 * Check whether two virtual chapter numbers correspond to the same

 * physical chapter.

 *

 * @param geometry The geometry of the index

 * @param chapter1 The first chapter to compare

 * @param chapter2 The second chapter to compare

 *

 * @return true if both chapters correspond to the same

 *         physical chapter

 **/

bool areSamePhysicalChapter(const Geometry *geometry,

                            uint64_t        chapter1,

                            uint64_t        chapter2)

  __attribute__((warn_unused_result));

#endif /* GEOMETRY_H */