1133359Sobrien/* SPDX-License-Identifier: GPL-2.0-only */
2133359Sobrien/*
3226048Sobrien * Copyright 2023 Red Hat
4133359Sobrien */
5226048Sobrien
6133359Sobrien#ifndef UDS_DELTA_INDEX_H
7133359Sobrien#define UDS_DELTA_INDEX_H
8133359Sobrien
9133359Sobrien#include <linux/cache.h>
10133359Sobrien
11133359Sobrien#include "numeric.h"
12133359Sobrien#include "time-utils.h"
13133359Sobrien
14226048Sobrien#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
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 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 */
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 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 */
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