drivers/md/dm-vdo/indexer/delta-index.h

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #ifndef UDS_DELTA_INDEX_H
   7 #define UDS_DELTA_INDEX_H
   8
   9 #include <linux/cache.h>
  10
  11 #include "numeric.h"
  12 #include "time-utils.h"
  13
  14 #include "config.h"
  15 #include "io-factory.h"
  16
  17 /*
  18  * A delta index is a key-value store, where each entry maps an address (the key) to a payload (the
  19  * value). The entries are sorted by address, and only the delta between successive addresses is
  20  * stored in the entry. The addresses are assumed to be uniformly distributed, and the deltas are
  21  * therefore exponentially distributed.
  22  *
  23  * A delta_index can either be mutable or immutable depending on its expected use. The immutable
  24  * form of a delta index is used for the indexes of closed chapters committed to the volume. The
  25  * mutable form of a delta index is used by the volume index, and also by the chapter index in an
  26  * open chapter. Like the index as a whole, each mutable delta index is divided into a number of
  27  * independent zones.
  28  */
  29
  30 struct delta_list {
  31         /* The offset of the delta list start, in bits */
  32         u64 start;
  33         /* The number of bits in the delta list */
  34         u16 size;
  35         /* Where the last search "found" the key, in bits */
  36         u16 save_offset;
  37         /* The key for the record just before save_offset */
  38         u32 save_key;
  39 };
  40
  41 struct delta_zone {
  42         /* The delta list memory */
  43         u8 *memory;
  44         /* The delta list headers */
  45         struct delta_list *delta_lists;
  46         /* Temporary starts of delta lists */
  47         u64 *new_offsets;
  48         /* Buffered writer for saving an index */
  49         struct buffered_writer *buffered_writer;
  50         /* The size of delta list memory */
  51         size_t size;
  52         /* Nanoseconds spent rebalancing */
  53         ktime_t rebalance_time;
  54         /* Number of memory rebalances */
  55         u32 rebalance_count;
  56         /* The number of bits in a stored value */
  57         u8 value_bits;
  58         /* The number of bits in the minimal key code */
  59         u16 min_bits;
  60         /* The number of keys used in a minimal code */
  61         u32 min_keys;
  62         /* The number of keys used for another code bit */
  63         u32 incr_keys;
  64         /* The number of records in the index */
  65         u64 record_count;
  66         /* The number of collision records */
  67         u64 collision_count;
  68         /* The number of records removed */
  69         u64 discard_count;
  70         /* The number of UDS_OVERFLOW errors detected */
  71         u64 overflow_count;
  72         /* The index of the first delta list */
  73         u32 first_list;
  74         /* The number of delta lists */
  75         u32 list_count;
  76         /* Tag belonging to this delta index */
  77         u8 tag;
  78 } __aligned(L1_CACHE_BYTES);
  79
  80 struct delta_list_save_info {
  81         /* Tag identifying which delta index this list is in */
  82         u8 tag;
  83         /* Bit offset of the start of the list data */
  84         u8 bit_offset;
  85         /* Number of bytes of list data */
  86         u16 byte_count;
  87         /* The delta list number within the delta index */
  88         u32 index;
  89 } __packed;
  90
  91 struct delta_index {
  92         /* The zones */
  93         struct delta_zone *delta_zones;
  94         /* The number of zones */
  95         unsigned int zone_count;
  96         /* The number of delta lists */
  97         u32 list_count;
  98         /* Maximum lists per zone */
  99         u32 lists_per_zone;
 100         /* Total memory allocated to this index */
 101         size_t memory_size;
 102         /* The number of non-empty lists at load time per zone */
 103         u32 load_lists[MAX_ZONES];
 104         /* True if this index is mutable */
 105         bool mutable;
 106         /* Tag belonging to this delta index */
 107         u8 tag;
 108 };
 109
 110 /*
 111  * A delta_index_page describes a single page of a chapter index. The delta_index field allows the
 112  * page to be treated as an immutable delta_index. We use the delta_zone field to treat the chapter
 113  * index page as a single zone index, and without the need to do an additional memory allocation.
 114  */
 115 struct delta_index_page {
 116         struct delta_index delta_index;
 117         /* These values are loaded from the delta_page_header */
 118         u32 lowest_list_number;
 119         u32 highest_list_number;
 120         u64 virtual_chapter_number;
 121         /* This structure describes the single zone of a delta index page. */
 122         struct delta_zone delta_zone;
 123 };
 124
 125 /*
 126  * Notes on the delta_index_entries:
 127  *
 128  * The fields documented as "public" can be read by any code that uses a delta_index. The fields
 129  * documented as "private" carry information between delta_index method calls and should not be
 130  * used outside the delta_index module.
 131  *
 132  * (1) The delta_index_entry is used like an iterator when searching a delta list.
 133  *
 134  * (2) It is also the result of a successful search and can be used to refer to the element found
 135  *     by the search.
 136  *
 137  * (3) It is also the result of an unsuccessful search and can be used to refer to the insertion
 138  *     point for a new record.
 139  *
 140  * (4) If at_end is true, the delta_list entry can only be used as the insertion point for a new
 141  *     record at the end of the list.
 142  *
 143  * (5) If at_end is false and is_collision is true, the delta_list entry fields refer to a
 144  *     collision entry in the list, and the delta_list entry can be used as a reference to this
 145  *     entry.
 146  *
 147  * (6) If at_end is false and is_collision is false, the delta_list entry fields refer to a
 148  *     non-collision entry in the list. Such delta_list entries can be used as a reference to a
 149  *     found entry, or an insertion point for a non-collision entry before this entry, or an
 150  *     insertion point for a collision entry that collides with this entry.
 151  */
 152 struct delta_index_entry {
 153         /* Public fields */
 154         /* The key for this entry */
 155         u32 key;
 156         /* We are after the last list entry */
 157         bool at_end;
 158         /* This record is a collision */
 159         bool is_collision;
 160
 161         /* Private fields */
 162         /* This delta list overflowed */
 163         bool list_overflow;
 164         /* The number of bits used for the value */
 165         u8 value_bits;
 166         /* The number of bits used for the entire entry */
 167         u16 entry_bits;
 168         /* The delta index zone */
 169         struct delta_zone *delta_zone;
 170         /* The delta list containing the entry */
 171         struct delta_list *delta_list;
 172         /* The delta list number */
 173         u32 list_number;
 174         /* Bit offset of this entry within the list */
 175         u16 offset;
 176         /* The delta between this and previous entry */
 177         u32 delta;
 178         /* Temporary delta list for immutable indices */
 179         struct delta_list temp_delta_list;
 180 };
 181
 182 struct delta_index_stats {
 183         /* Number of bytes allocated */
 184         size_t memory_allocated;
 185         /* Nanoseconds spent rebalancing */
 186         ktime_t rebalance_time;
 187         /* Number of memory rebalances */
 188         u32 rebalance_count;
 189         /* The number of records in the index */
 190         u64 record_count;
 191         /* The number of collision records */
 192         u64 collision_count;
 193         /* The number of records removed */
 194         u64 discard_count;
 195         /* The number of UDS_OVERFLOW errors detected */
 196         u64 overflow_count;
 197         /* The number of delta lists */
 198         u32 list_count;
 199 };
 200
 201 int __must_check uds_initialize_delta_index(struct delta_index *delta_index,
 202                                             unsigned int zone_count, u32 list_count,
 203                                             u32 mean_delta, u32 payload_bits,
 204                                             size_t memory_size, u8 tag);
 205
 206 int __must_check uds_initialize_delta_index_page(struct delta_index_page *delta_index_page,
 207                                                  u64 expected_nonce, u32 mean_delta,
 208                                                  u32 payload_bits, u8 *memory,
 209                                                  size_t memory_size);
 210
 211 void uds_uninitialize_delta_index(struct delta_index *delta_index);
 212
 213 void uds_reset_delta_index(const struct delta_index *delta_index);
 214
 215 int __must_check uds_pack_delta_index_page(const struct delta_index *delta_index,
 216                                            u64 header_nonce, u8 *memory,
 217                                            size_t memory_size,
 218                                            u64 virtual_chapter_number, u32 first_list,
 219                                            u32 *list_count);
 220
 221 int __must_check uds_start_restoring_delta_index(struct delta_index *delta_index,
 222                                                  struct buffered_reader **buffered_readers,
 223                                                  unsigned int reader_count);
 224
 225 int __must_check uds_finish_restoring_delta_index(struct delta_index *delta_index,
 226                                                   struct buffered_reader **buffered_readers,
 227                                                   unsigned int reader_count);
 228
 229 int __must_check uds_check_guard_delta_lists(struct buffered_reader **buffered_readers,
 230                                              unsigned int reader_count);
 231
 232 int __must_check uds_start_saving_delta_index(const struct delta_index *delta_index,
 233                                               unsigned int zone_number,
 234                                               struct buffered_writer *buffered_writer);
 235
 236 int __must_check uds_finish_saving_delta_index(const struct delta_index *delta_index,
 237                                                unsigned int zone_number);
 238
 239 int __must_check uds_write_guard_delta_list(struct buffered_writer *buffered_writer);
 240
 241 size_t __must_check uds_compute_delta_index_save_bytes(u32 list_count,
 242                                                        size_t memory_size);
 243
 244 int __must_check uds_start_delta_index_search(const struct delta_index *delta_index,
 245                                               u32 list_number, u32 key,
 246                                               struct delta_index_entry *iterator);
 247
 248 int __must_check uds_next_delta_index_entry(struct delta_index_entry *delta_entry);
 249
 250 int __must_check uds_remember_delta_index_offset(const struct delta_index_entry *delta_entry);
 251
 252 int __must_check uds_get_delta_index_entry(const struct delta_index *delta_index,
 253                                            u32 list_number, u32 key, const u8 *name,
 254                                            struct delta_index_entry *delta_entry);
 255
 256 int __must_check uds_get_delta_entry_collision(const struct delta_index_entry *delta_entry,
 257                                                u8 *name);
 258
 259 u32 __must_check uds_get_delta_entry_value(const struct delta_index_entry *delta_entry);
 260
 261 int __must_check uds_set_delta_entry_value(const struct delta_index_entry *delta_entry, u32 value);
 262
 263 int __must_check uds_put_delta_index_entry(struct delta_index_entry *delta_entry, u32 key,
 264                                            u32 value, const u8 *name);
 265
 266 int __must_check uds_remove_delta_index_entry(struct delta_index_entry *delta_entry);
 267
 268 void uds_get_delta_index_stats(const struct delta_index *delta_index,
 269                                struct delta_index_stats *stats);
 270
 271 size_t __must_check uds_compute_delta_index_size(u32 entry_count, u32 mean_delta,
 272                                                  u32 payload_bits);
 273
 274 u32 uds_get_delta_index_page_count(u32 entry_count, u32 list_count, u32 mean_delta,
 275                                    u32 payload_bits, size_t bytes_per_page);
 276
 277 void uds_log_delta_index_entry(struct delta_index_entry *delta_entry);
 278
 279 #endif /* UDS_DELTA_INDEX_H */