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
32struct 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
51struct volume_sub_index_zone {
52	u64 virtual_chapter_low;
53	u64 virtual_chapter_high;
54	u64 early_flushes;
55} __aligned(L1_CACHE_BYTES);
56
57struct 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
88struct volume_index_zone {
89	/* Protects the sampled index in this zone */
90	struct mutex hook_mutex;
91} __aligned(L1_CACHE_BYTES);
92
93struct 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 */
116struct 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
140int __must_check uds_make_volume_index(const struct uds_configuration *config,
141				       u64 volume_nonce,
142				       struct volume_index **volume_index);
143
144void uds_free_volume_index(struct volume_index *volume_index);
145
146int __must_check uds_compute_volume_index_save_blocks(const struct uds_configuration *config,
147						      size_t block_size,
148						      u64 *block_count);
149
150unsigned int __must_check uds_get_volume_index_zone(const struct volume_index *volume_index,
151						    const struct uds_record_name *name);
152
153bool __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 */
160u64 __must_check uds_lookup_volume_index_name(const struct volume_index *volume_index,
161					      const struct uds_record_name *name);
162
163int __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
167int __must_check uds_put_volume_index_record(struct volume_index_record *record,
168					     u64 virtual_chapter);
169
170int __must_check uds_remove_volume_index_record(struct volume_index_record *record);
171
172int __must_check uds_set_volume_index_record_chapter(struct volume_index_record *record,
173						     u64 virtual_chapter);
174
175void uds_set_volume_index_open_chapter(struct volume_index *volume_index,
176				       u64 virtual_chapter);
177
178void uds_set_volume_index_zone_open_chapter(struct volume_index *volume_index,
179					    unsigned int zone_number,
180					    u64 virtual_chapter);
181
182int __must_check uds_load_volume_index(struct volume_index *volume_index,
183				       struct buffered_reader **readers,
184				       unsigned int reader_count);
185
186int __must_check uds_save_volume_index(struct volume_index *volume_index,
187				       struct buffered_writer **writers,
188				       unsigned int writer_count);
189
190void 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