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