linux/drivers/md/dm-vdo/indexer/open-chapter.c

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright 2023 Red Hat
 */

#include "open-chapter.h"

#include <linux/log2.h>

#include "logger.h"
#include "memory-alloc.h"
#include "numeric.h"
#include "permassert.h"

#include "config.h"
#include "hash-utils.h"

/*
 * Each index zone has a dedicated open chapter zone structure which gets an equal share of the
 * open chapter space. Records are assigned to zones based on their record name. Within each zone,
 * records are stored in an array in the order they arrive. Additionally, a reference to each
 * record is stored in a hash table to help determine if a new record duplicates an existing one.
 * If new metadata for an existing name arrives, the record is altered in place. The array of
 * records is 1-based so that record number 0 can be used to indicate an unused hash slot.
 *
 * Deleted records are marked with a flag rather than actually removed to simplify hash table
 * management. The array of deleted flags overlays the array of hash slots, but the flags are
 * indexed by record number instead of by record name. The number of hash slots will always be a
 * power of two that is greater than the number of records to be indexed, guaranteeing that hash
 * insertion cannot fail, and that there are sufficient flags for all records.
 *
 * Once any open chapter zone fills its available space, the chapter is closed. The records from
 * each zone are interleaved to attempt to preserve temporal locality and assigned to record pages.
 * Empty or deleted records are replaced by copies of a valid record so that the record pages only
 * contain valid records. The chapter then constructs a delta index which maps each record name to
 * the record page on which that record can be found, which is split into index pages. These
 * structures are then passed to the volume to be recorded on storage.
 *
 * When the index is saved, the open chapter records are saved in a single array, once again
 * interleaved to attempt to preserve temporal locality. When the index is reloaded, there may be a
 * different number of zones than previously, so the records must be parcelled out to their new
 * zones. In addition, depending on the distribution of record names, a new zone may have more
 * records than it has space. In this case, the latest records for that zone will be discarded.
 */

static const u8 OPEN_CHAPTER_MAGIC[] = …;
static const u8 OPEN_CHAPTER_VERSION[] = …;

#define OPEN_CHAPTER_MAGIC_LENGTH …
#define OPEN_CHAPTER_VERSION_LENGTH …
#define LOAD_RATIO …

static inline size_t records_size(const struct open_chapter_zone *open_chapter)
{ … }

static inline size_t slots_size(size_t slot_count)
{ … }

int uds_make_open_chapter(const struct index_geometry *geometry, unsigned int zone_count,
			  struct open_chapter_zone **open_chapter_ptr)
{ … }

void uds_reset_open_chapter(struct open_chapter_zone *open_chapter)
{ … }

static unsigned int probe_chapter_slots(struct open_chapter_zone *open_chapter,
					const struct uds_record_name *name)
{ … }

void uds_search_open_chapter(struct open_chapter_zone *open_chapter,
			     const struct uds_record_name *name,
			     struct uds_record_data *metadata, bool *found)
{ … }

/* Add a record to the open chapter zone and return the remaining space. */
int uds_put_open_chapter(struct open_chapter_zone *open_chapter,
			 const struct uds_record_name *name,
			 const struct uds_record_data *metadata)
{ … }

void uds_remove_from_open_chapter(struct open_chapter_zone *open_chapter,
				  const struct uds_record_name *name)
{ … }

void uds_free_open_chapter(struct open_chapter_zone *open_chapter)
{ … }

/* Map each record name to its record page number in the delta chapter index. */
static int fill_delta_chapter_index(struct open_chapter_zone **chapter_zones,
				    unsigned int zone_count,
				    struct open_chapter_index *index,
				    struct uds_volume_record *collated_records)
{ … }

int uds_close_open_chapter(struct open_chapter_zone **chapter_zones,
			   unsigned int zone_count, struct volume *volume,
			   struct open_chapter_index *chapter_index,
			   struct uds_volume_record *collated_records,
			   u64 virtual_chapter_number)
{ … }

int uds_save_open_chapter(struct uds_index *index, struct buffered_writer *writer)
{ … }

u64 uds_compute_saved_open_chapter_size(struct index_geometry *geometry)
{ … }

static int load_version20(struct uds_index *index, struct buffered_reader *reader)
{ … }

int uds_load_open_chapter(struct uds_index *index, struct buffered_reader *reader)
{ … }