volume-index.h

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