280 lines · c
1/* SPDX-License-Identifier: GPL-2.0-only */2/*3 * Copyright 2023 Red Hat4 */5 6#ifndef UDS_DELTA_INDEX_H7#define UDS_DELTA_INDEX_H8 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 (the19 * value). The entries are sorted by address, and only the delta between successive addresses is20 * stored in the entry. The addresses are assumed to be uniformly distributed, and the deltas are21 * therefore exponentially distributed.22 *23 * A delta_index can either be mutable or immutable depending on its expected use. The immutable24 * form of a delta index is used for the indexes of closed chapters committed to the volume. The25 * mutable form of a delta index is used by the volume index, and also by the chapter index in an26 * open chapter. Like the index as a whole, each mutable delta index is divided into a number of27 * independent zones.28 */29 30struct 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 41struct 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 80struct 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 91struct 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 the112 * page to be treated as an immutable delta_index. We use the delta_zone field to treat the chapter113 * index page as a single zone index, and without the need to do an additional memory allocation.114 */115struct 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 fields129 * documented as "private" carry information between delta_index method calls and should not be130 * 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 found135 * by the search.136 *137 * (3) It is also the result of an unsuccessful search and can be used to refer to the insertion138 * 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 new141 * 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 a144 * collision entry in the list, and the delta_list entry can be used as a reference to this145 * entry.146 *147 * (6) If at_end is false and is_collision is false, the delta_list entry fields refer to a148 * non-collision entry in the list. Such delta_list entries can be used as a reference to a149 * found entry, or an insertion point for a non-collision entry before this entry, or an150 * insertion point for a collision entry that collides with this entry.151 */152struct 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 182struct 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 201int __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 206int __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 211void uds_uninitialize_delta_index(struct delta_index *delta_index);212 213void uds_reset_delta_index(const struct delta_index *delta_index);214 215int __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 221int __must_check uds_start_restoring_delta_index(struct delta_index *delta_index,222 struct buffered_reader **buffered_readers,223 unsigned int reader_count);224 225int __must_check uds_finish_restoring_delta_index(struct delta_index *delta_index,226 struct buffered_reader **buffered_readers,227 unsigned int reader_count);228 229int __must_check uds_check_guard_delta_lists(struct buffered_reader **buffered_readers,230 unsigned int reader_count);231 232int __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 236int __must_check uds_finish_saving_delta_index(const struct delta_index *delta_index,237 unsigned int zone_number);238 239int __must_check uds_write_guard_delta_list(struct buffered_writer *buffered_writer);240 241size_t __must_check uds_compute_delta_index_save_bytes(u32 list_count,242 size_t memory_size);243 244int __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 248int __must_check uds_next_delta_index_entry(struct delta_index_entry *delta_entry);249 250int __must_check uds_remember_delta_index_offset(const struct delta_index_entry *delta_entry);251 252int __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 256int __must_check uds_get_delta_entry_collision(const struct delta_index_entry *delta_entry,257 u8 *name);258 259u32 __must_check uds_get_delta_entry_value(const struct delta_index_entry *delta_entry);260 261int __must_check uds_set_delta_entry_value(const struct delta_index_entry *delta_entry, u32 value);262 263int __must_check uds_put_delta_index_entry(struct delta_index_entry *delta_entry, u32 key,264 u32 value, const u8 *name);265 266int __must_check uds_remove_delta_index_entry(struct delta_index_entry *delta_entry);267 268void uds_get_delta_index_stats(const struct delta_index *delta_index,269 struct delta_index_stats *stats);270 271size_t __must_check uds_compute_delta_index_size(u32 entry_count, u32 mean_delta,272 u32 payload_bits);273 274u32 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 277void uds_log_delta_index_entry(struct delta_index_entry *delta_entry);278 279#endif /* UDS_DELTA_INDEX_H */280