delta-index.h | Explore in Territory

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

#ifndef UDS_DELTA_INDEX_H
#define UDS_DELTA_INDEX_H

#include <linux/cache.h>

#include "numeric.h"
#include "time-utils.h"

#include "config.h"
#include "io-factory.h"

/*
 * A delta index is a key-value store, where each entry maps an address (the key) to a payload (the
 * value). The entries are sorted by address, and only the delta between successive addresses is
 * stored in the entry. The addresses are assumed to be uniformly distributed, and the deltas are
 * therefore exponentially distributed.
 *
 * A delta_index can either be mutable or immutable depending on its expected use. The immutable
 * form of a delta index is used for the indexes of closed chapters committed to the volume. The
 * mutable form of a delta index is used by the volume index, and also by the chapter index in an
 * open chapter. Like the index as a whole, each mutable delta index is divided into a number of
 * independent zones.
 */

struct delta_list { … };

struct delta_zone { … } __aligned(…);

struct delta_list_save_info { … } __packed;

struct delta_index { … };

/*
 * A delta_index_page describes a single page of a chapter index. The delta_index field allows the
 * page to be treated as an immutable delta_index. We use the delta_zone field to treat the chapter
 * index page as a single zone index, and without the need to do an additional memory allocation.
 */
struct delta_index_page { … };

/*
 * Notes on the delta_index_entries:
 *
 * The fields documented as "public" can be read by any code that uses a delta_index. The fields
 * documented as "private" carry information between delta_index method calls and should not be
 * used outside the delta_index module.
 *
 * (1) The delta_index_entry is used like an iterator when searching a delta list.
 *
 * (2) It is also the result of a successful search and can be used to refer to the element found
 *     by the search.
 *
 * (3) It is also the result of an unsuccessful search and can be used to refer to the insertion
 *     point for a new record.
 *
 * (4) If at_end is true, the delta_list entry can only be used as the insertion point for a new
 *     record at the end of the list.
 *
 * (5) If at_end is false and is_collision is true, the delta_list entry fields refer to a
 *     collision entry in the list, and the delta_list entry can be used as a reference to this
 *     entry.
 *
 * (6) If at_end is false and is_collision is false, the delta_list entry fields refer to a
 *     non-collision entry in the list. Such delta_list entries can be used as a reference to a
 *     found entry, or an insertion point for a non-collision entry before this entry, or an
 *     insertion point for a collision entry that collides with this entry.
 */
struct delta_index_entry { … };

struct delta_index_stats { … };

int __must_check uds_initialize_delta_index(struct delta_index *delta_index,
					    unsigned int zone_count, u32 list_count,
					    u32 mean_delta, u32 payload_bits,
					    size_t memory_size, u8 tag);

int __must_check uds_initialize_delta_index_page(struct delta_index_page *delta_index_page,
						 u64 expected_nonce, u32 mean_delta,
						 u32 payload_bits, u8 *memory,
						 size_t memory_size);

void uds_uninitialize_delta_index(struct delta_index *delta_index);

void uds_reset_delta_index(const struct delta_index *delta_index);

int __must_check uds_pack_delta_index_page(const struct delta_index *delta_index,
					   u64 header_nonce, u8 *memory,
					   size_t memory_size,
					   u64 virtual_chapter_number, u32 first_list,
					   u32 *list_count);

int __must_check uds_start_restoring_delta_index(struct delta_index *delta_index,
						 struct buffered_reader **buffered_readers,
						 unsigned int reader_count);

int __must_check uds_finish_restoring_delta_index(struct delta_index *delta_index,
						  struct buffered_reader **buffered_readers,
						  unsigned int reader_count);

int __must_check uds_check_guard_delta_lists(struct buffered_reader **buffered_readers,
					     unsigned int reader_count);

int __must_check uds_start_saving_delta_index(const struct delta_index *delta_index,
					      unsigned int zone_number,
					      struct buffered_writer *buffered_writer);

int __must_check uds_finish_saving_delta_index(const struct delta_index *delta_index,
					       unsigned int zone_number);

int __must_check uds_write_guard_delta_list(struct buffered_writer *buffered_writer);

size_t __must_check uds_compute_delta_index_save_bytes(u32 list_count,
						       size_t memory_size);

int __must_check uds_start_delta_index_search(const struct delta_index *delta_index,
					      u32 list_number, u32 key,
					      struct delta_index_entry *iterator);

int __must_check uds_next_delta_index_entry(struct delta_index_entry *delta_entry);

int __must_check uds_remember_delta_index_offset(const struct delta_index_entry *delta_entry);

int __must_check uds_get_delta_index_entry(const struct delta_index *delta_index,
					   u32 list_number, u32 key, const u8 *name,
					   struct delta_index_entry *delta_entry);

int __must_check uds_get_delta_entry_collision(const struct delta_index_entry *delta_entry,
					       u8 *name);

u32 __must_check uds_get_delta_entry_value(const struct delta_index_entry *delta_entry);

int __must_check uds_set_delta_entry_value(const struct delta_index_entry *delta_entry, u32 value);

int __must_check uds_put_delta_index_entry(struct delta_index_entry *delta_entry, u32 key,
					   u32 value, const u8 *name);

int __must_check uds_remove_delta_index_entry(struct delta_index_entry *delta_entry);

void uds_get_delta_index_stats(const struct delta_index *delta_index,
			       struct delta_index_stats *stats);

size_t __must_check uds_compute_delta_index_size(u32 entry_count, u32 mean_delta,
						 u32 payload_bits);

u32 uds_get_delta_index_page_count(u32 entry_count, u32 list_count, u32 mean_delta,
				   u32 payload_bits, size_t bytes_per_page);

void uds_log_delta_index_entry(struct delta_index_entry *delta_entry);

#endif /* UDS_DELTA_INDEX_H */
linux/drivers/md/dm-vdo/indexer/delta-index.h
