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

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #ifndef UDS_VOLUME_INDEX_H
   7 #define UDS_VOLUME_INDEX_H
   8
   9 #include <linux/limits.h>
  10
  11 #include "thread-utils.h"
  12
  13 #include "config.h"
  14 #include "delta-index.h"
  15 #include "indexer.h"
  16
  17 /*
  18  * The volume index is the primary top-level index for UDS. It contains records which map a record
  19  * name to the chapter where a record with that name is stored. This mapping can definitively say
  20  * when no record exists. However, because we only use a subset of the name for this index, it
  21  * cannot definitively say that a record for the entry does exist. It can only say that if a record
  22  * exists, it will be in a particular chapter. The request can then be dispatched to that chapter
  23  * for further processing.
  24  *
  25  * If the volume_index_record does not actually match the record name, the index can store a more
  26  * specific collision record to disambiguate the new entry from the existing one. Index entries are
  27  * managed with volume_index_record structures.
  28  */
  29
  30 #define NO_CHAPTER U64_MAX
  31
  32 struct volume_index_stats {
  33         /* Nanoseconds spent rebalancing */
  34         ktime_t rebalance_time;
  35         /* Number of memory rebalances */
  36         u32 rebalance_count;
  37         /* The number of records in the index */
  38         u64 record_count;
  39         /* The number of collision records */
  40         u64 collision_count;
  41         /* The number of records removed */
  42         u64 discard_count;
  43         /* The number of UDS_OVERFLOWs detected */
  44         u64 overflow_count;
  45         /* The number of delta lists */
  46         u32 delta_lists;
  47         /* Number of early flushes */
  48         u64 early_flushes;
  49 };
  50
  51 struct volume_sub_index_zone {
  52         u64 virtual_chapter_low;
  53         u64 virtual_chapter_high;
  54         u64 early_flushes;
  55 } __aligned(L1_CACHE_BYTES);
  56
  57 struct volume_sub_index {
  58         /* The delta index */
  59         struct delta_index delta_index;
  60         /* The first chapter to be flushed in each zone */
  61         u64 *flush_chapters;
  62         /* The zones */
  63         struct volume_sub_index_zone *zones;
  64         /* The volume nonce */
  65         u64 volume_nonce;
  66         /* Expected size of a chapter (per zone) */
  67         u64 chapter_zone_bits;
  68         /* Maximum size of the index (per zone) */
  69         u64 max_zone_bits;
  70         /* The number of bits in address mask */
  71         u8 address_bits;
  72         /* Mask to get address within delta list */
  73         u32 address_mask;
  74         /* The number of bits in chapter number */
  75         u8 chapter_bits;
  76         /* The largest storable chapter number */
  77         u32 chapter_mask;
  78         /* The number of chapters used */
  79         u32 chapter_count;
  80         /* The number of delta lists */
  81         u32 list_count;
  82         /* The number of zones */
  83         unsigned int zone_count;
  84         /* The amount of memory allocated */
  85         u64 memory_size;
  86 };
  87
  88 struct volume_index_zone {
  89         /* Protects the sampled index in this zone */
  90         struct mutex hook_mutex;
  91 } __aligned(L1_CACHE_BYTES);
  92
  93 struct volume_index {
  94         u32 sparse_sample_rate;
  95         unsigned int zone_count;
  96         u64 memory_size;
  97         struct volume_sub_index vi_non_hook;
  98         struct volume_sub_index vi_hook;
  99         struct volume_index_zone *zones;
 100 };
 101
 102 /*
 103  * The volume_index_record structure is used to facilitate processing of a record name. A client
 104  * first calls uds_get_volume_index_record() to find the volume index record for a record name. The
 105  * fields of the record can then be examined to determine the state of the record.
 106  *
 107  * If is_found is false, then the index did not find an entry for the record name. Calling
 108  * uds_put_volume_index_record() will insert a new entry for that name at the proper place.
 109  *
 110  * If is_found is true, then we did find an entry for the record name, and the virtual_chapter and
 111  * is_collision fields reflect the entry found. Subsequently, a call to
 112  * uds_remove_volume_index_record() will remove the entry, a call to
 113  * uds_set_volume_index_record_chapter() will update the existing entry, and a call to
 114  * uds_put_volume_index_record() will insert a new collision record after the existing entry.
 115  */
 116 struct volume_index_record {
 117         /* Public fields */
 118
 119         /* Chapter where the record info is found */
 120         u64 virtual_chapter;
 121         /* This record is a collision */
 122         bool is_collision;
 123         /* This record is the requested record */
 124         bool is_found;
 125
 126         /* Private fields */
 127
 128         /* Zone that contains this name */
 129         unsigned int zone_number;
 130         /* The volume index */
 131         struct volume_sub_index *sub_index;
 132         /* Mutex for accessing this delta index entry in the hook index */
 133         struct mutex *mutex;
 134         /* The record name to which this record refers */
 135         const struct uds_record_name *name;
 136         /* The delta index entry for this record */
 137         struct delta_index_entry delta_entry;
 138 };
 139
 140 int __must_check uds_make_volume_index(const struct uds_configuration *config,
 141                                        u64 volume_nonce,
 142                                        struct volume_index **volume_index);
 143
 144 void uds_free_volume_index(struct volume_index *volume_index);
 145
 146 int __must_check uds_compute_volume_index_save_blocks(const struct uds_configuration *config,
 147                                                       size_t block_size,
 148                                                       u64 *block_count);
 149
 150 unsigned int __must_check uds_get_volume_index_zone(const struct volume_index *volume_index,
 151                                                     const struct uds_record_name *name);
 152
 153 bool __must_check uds_is_volume_index_sample(const struct volume_index *volume_index,
 154                                              const struct uds_record_name *name);
 155
 156 /*
 157  * This function is only used to manage sparse cache membership. Most requests should use
 158  * uds_get_volume_index_record() to look up index records instead.
 159  */
 160 u64 __must_check uds_lookup_volume_index_name(const struct volume_index *volume_index,
 161                                               const struct uds_record_name *name);
 162
 163 int __must_check uds_get_volume_index_record(struct volume_index *volume_index,
 164                                              const struct uds_record_name *name,
 165                                              struct volume_index_record *record);
 166
 167 int __must_check uds_put_volume_index_record(struct volume_index_record *record,
 168                                              u64 virtual_chapter);
 169
 170 int __must_check uds_remove_volume_index_record(struct volume_index_record *record);
 171
 172 int __must_check uds_set_volume_index_record_chapter(struct volume_index_record *record,
 173                                                      u64 virtual_chapter);
 174
 175 void uds_set_volume_index_open_chapter(struct volume_index *volume_index,
 176                                        u64 virtual_chapter);
 177
 178 void uds_set_volume_index_zone_open_chapter(struct volume_index *volume_index,
 179                                             unsigned int zone_number,
 180                                             u64 virtual_chapter);
 181
 182 int __must_check uds_load_volume_index(struct volume_index *volume_index,
 183                                        struct buffered_reader **readers,
 184                                        unsigned int reader_count);
 185
 186 int __must_check uds_save_volume_index(struct volume_index *volume_index,
 187                                        struct buffered_writer **writers,
 188                                        unsigned int writer_count);
 189
 190 void uds_get_volume_index_stats(const struct volume_index *volume_index,
 191                                 struct volume_index_stats *stats);
 192
 193 #endif /* UDS_VOLUME_INDEX_H */