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 */ 194