194 lines · c
1/* SPDX-License-Identifier: GPL-2.0-only */2/*3 * Copyright 2023 Red Hat4 */5 6#ifndef UDS_VOLUME_INDEX_H7#define UDS_VOLUME_INDEX_H8 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 record19 * name to the chapter where a record with that name is stored. This mapping can definitively say20 * when no record exists. However, because we only use a subset of the name for this index, it21 * cannot definitively say that a record for the entry does exist. It can only say that if a record22 * exists, it will be in a particular chapter. The request can then be dispatched to that chapter23 * for further processing.24 *25 * If the volume_index_record does not actually match the record name, the index can store a more26 * specific collision record to disambiguate the new entry from the existing one. Index entries are27 * managed with volume_index_record structures.28 */29 30#define NO_CHAPTER U64_MAX31 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 client104 * first calls uds_get_volume_index_record() to find the volume index record for a record name. The105 * 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. Calling108 * 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 and111 * is_collision fields reflect the entry found. Subsequently, a call to112 * uds_remove_volume_index_record() will remove the entry, a call to113 * uds_set_volume_index_record_chapter() will update the existing entry, and a call to114 * 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 use158 * 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