summaryrefslogtreecommitdiffstats
path: root/drivers/md/dm-vdo/indexer/delta-index.h
blob: 53f6c6ac0bc7b935c12b2e5740b737e449d007e4 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
/* SPDX-License-Identifier: GPL-2.0-only */
/*
 * Copyright 2023 Red Hat
 */

#ifndef UDS_DELTA_INDEX_H
#define UDS_DELTA_INDEX_H

#include <linux/cache.h>

#include "numeric.h"
#include "time-utils.h"

#include "config.h"
#include "io-factory.h"

/*
 * A delta index is a key-value store, where each entry maps an address (the key) to a payload (the
 * value). The entries are sorted by address, and only the delta between successive addresses is
 * stored in the entry. The addresses are assumed to be uniformly distributed, and the deltas are
 * therefore exponentially distributed.
 *
 * A delta_index can either be mutable or immutable depending on its expected use. The immutable
 * form of a delta index is used for the indexes of closed chapters committed to the volume. The
 * mutable form of a delta index is used by the volume index, and also by the chapter index in an
 * open chapter. Like the index as a whole, each mutable delta index is divided into a number of
 * independent zones.
 */

struct delta_list {
	/* The offset of the delta list start, in bits */
	u64 start;
	/* The number of bits in the delta list */
	u16 size;
	/* Where the last search "found" the key, in bits */
	u16 save_offset;
	/* The key for the record just before save_offset */
	u32 save_key;
};

struct delta_zone {
	/* The delta list memory */
	u8 *memory;
	/* The delta list headers */
	struct delta_list *delta_lists;
	/* Temporary starts of delta lists */
	u64 *new_offsets;
	/* Buffered writer for saving an index */
	struct buffered_writer *buffered_writer;
	/* The size of delta list memory */
	size_t size;
	/* Nanoseconds spent rebalancing */
	ktime_t rebalance_time;
	/* Number of memory rebalances */
	u32 rebalance_count;
	/* The number of bits in a stored value */
	u8 value_bits;
	/* The number of bits in the minimal key code */
	u16 min_bits;
	/* The number of keys used in a minimal code */
	u32 min_keys;
	/* The number of keys used for another code bit */
	u32 incr_keys;
	/* The number of records in the index */
	u64 record_count;
	/* The number of collision records */
	u64 collision_count;
	/* The number of records removed */
	u64 discard_count;
	/* The number of UDS_OVERFLOW errors detected */
	u64 overflow_count;
	/* The index of the first delta list */
	u32 first_list;
	/* The number of delta lists */
	u32 list_count;
	/* Tag belonging to this delta index */
	u8 tag;
} __aligned(L1_CACHE_BYTES);

struct delta_list_save_info {
	/* Tag identifying which delta index this list is in */
	u8 tag;
	/* Bit offset of the start of the list data */
	u8 bit_offset;
	/* Number of bytes of list data */
	u16 byte_count;
	/* The delta list number within the delta index */
	u32 index;
} __packed;

struct delta_index {
	/* The zones */
	struct delta_zone *delta_zones;
	/* The number of zones */
	unsigned int zone_count;
	/* The number of delta lists */
	u32 list_count;
	/* Maximum lists per zone */
	u32 lists_per_zone;
	/* Total memory allocated to this index */
	size_t memory_size;
	/* The number of non-empty lists at load time per zone */
	u32 load_lists[MAX_ZONES];
	/* True if this index is mutable */
	bool mutable;
	/* Tag belonging to this delta index */
	u8 tag;
};

/*
 * A delta_index_page describes a single page of a chapter index. The delta_index field allows the
 * page to be treated as an immutable delta_index. We use the delta_zone field to treat the chapter
 * index page as a single zone index, and without the need to do an additional memory allocation.
 */
struct delta_index_page {
	struct delta_index delta_index;
	/* These values are loaded from the delta_page_header */
	u32 lowest_list_number;
	u32 highest_list_number;
	u64 virtual_chapter_number;
	/* This structure describes the single zone of a delta index page. */
	struct delta_zone delta_zone;
};

/*
 * Notes on the delta_index_entries:
 *
 * The fields documented as "public" can be read by any code that uses a delta_index. The fields
 * documented as "private" carry information between delta_index method calls and should not be
 * used outside the delta_index module.
 *
 * (1) The delta_index_entry is used like an iterator when searching a delta list.
 *
 * (2) It is also the result of a successful search and can be used to refer to the element found
 *     by the search.
 *
 * (3) It is also the result of an unsuccessful search and can be used to refer to the insertion
 *     point for a new record.
 *
 * (4) If at_end is true, the delta_list entry can only be used as the insertion point for a new
 *     record at the end of the list.
 *
 * (5) If at_end is false and is_collision is true, the delta_list entry fields refer to a
 *     collision entry in the list, and the delta_list entry can be used as a reference to this
 *     entry.
 *
 * (6) If at_end is false and is_collision is false, the delta_list entry fields refer to a
 *     non-collision entry in the list. Such delta_list entries can be used as a reference to a
 *     found entry, or an insertion point for a non-collision entry before this entry, or an
 *     insertion point for a collision entry that collides with this entry.
 */
struct delta_index_entry {
	/* Public fields */
	/* The key for this entry */
	u32 key;
	/* We are after the last list entry */
	bool at_end;
	/* This record is a collision */
	bool is_collision;

	/* Private fields */
	/* This delta list overflowed */
	bool list_overflow;
	/* The number of bits used for the value */
	u8 value_bits;
	/* The number of bits used for the entire entry */
	u16 entry_bits;
	/* The delta index zone */
	struct delta_zone *delta_zone;
	/* The delta list containing the entry */
	struct delta_list *delta_list;
	/* The delta list number */
	u32 list_number;
	/* Bit offset of this entry within the list */
	u16 offset;
	/* The delta between this and previous entry */
	u32 delta;
	/* Temporary delta list for immutable indices */
	struct delta_list temp_delta_list;
};

struct delta_index_stats {
	/* Number of bytes allocated */
	size_t memory_allocated;
	/* Nanoseconds spent rebalancing */
	ktime_t rebalance_time;
	/* Number of memory rebalances */
	u32 rebalance_count;
	/* The number of records in the index */
	u64 record_count;
	/* The number of collision records */
	u64 collision_count;
	/* The number of records removed */
	u64 discard_count;
	/* The number of UDS_OVERFLOW errors detected */
	u64 overflow_count;
	/* The number of delta lists */
	u32 list_count;
};

int __must_check uds_initialize_delta_index(struct delta_index *delta_index,
					    unsigned int zone_count, u32 list_count,
					    u32 mean_delta, u32 payload_bits,
					    size_t memory_size, u8 tag);

int __must_check uds_initialize_delta_index_page(struct delta_index_page *delta_index_page,
						 u64 expected_nonce, u32 mean_delta,
						 u32 payload_bits, u8 *memory,
						 size_t memory_size);

void uds_uninitialize_delta_index(struct delta_index *delta_index);

void uds_reset_delta_index(const struct delta_index *delta_index);

int __must_check uds_pack_delta_index_page(const struct delta_index *delta_index,
					   u64 header_nonce, u8 *memory,
					   size_t memory_size,
					   u64 virtual_chapter_number, u32 first_list,
					   u32 *list_count);

int __must_check uds_start_restoring_delta_index(struct delta_index *delta_index,
						 struct buffered_reader **buffered_readers,
						 unsigned int reader_count);

int __must_check uds_finish_restoring_delta_index(struct delta_index *delta_index,
						  struct buffered_reader **buffered_readers,
						  unsigned int reader_count);

int __must_check uds_check_guard_delta_lists(struct buffered_reader **buffered_readers,
					     unsigned int reader_count);

int __must_check uds_start_saving_delta_index(const struct delta_index *delta_index,
					      unsigned int zone_number,
					      struct buffered_writer *buffered_writer);

int __must_check uds_finish_saving_delta_index(const struct delta_index *delta_index,
					       unsigned int zone_number);

int __must_check uds_write_guard_delta_list(struct buffered_writer *buffered_writer);

size_t __must_check uds_compute_delta_index_save_bytes(u32 list_count,
						       size_t memory_size);

int __must_check uds_start_delta_index_search(const struct delta_index *delta_index,
					      u32 list_number, u32 key,
					      struct delta_index_entry *iterator);

int __must_check uds_next_delta_index_entry(struct delta_index_entry *delta_entry);

int __must_check uds_remember_delta_index_offset(const struct delta_index_entry *delta_entry);

int __must_check uds_get_delta_index_entry(const struct delta_index *delta_index,
					   u32 list_number, u32 key, const u8 *name,
					   struct delta_index_entry *delta_entry);

int __must_check uds_get_delta_entry_collision(const struct delta_index_entry *delta_entry,
					       u8 *name);

u32 __must_check uds_get_delta_entry_value(const struct delta_index_entry *delta_entry);

int __must_check uds_set_delta_entry_value(const struct delta_index_entry *delta_entry, u32 value);

int __must_check uds_put_delta_index_entry(struct delta_index_entry *delta_entry, u32 key,
					   u32 value, const u8 *name);

int __must_check uds_remove_delta_index_entry(struct delta_index_entry *delta_entry);

void uds_get_delta_index_stats(const struct delta_index *delta_index,
			       struct delta_index_stats *stats);

size_t __must_check uds_compute_delta_index_size(u32 entry_count, u32 mean_delta,
						 u32 payload_bits);

u32 uds_get_delta_index_page_count(u32 entry_count, u32 list_count, u32 mean_delta,
				   u32 payload_bits, size_t bytes_per_page);

void uds_log_delta_index_entry(struct delta_index_entry *delta_entry);

#endif /* UDS_DELTA_INDEX_H */