1 /* SPDX-License-Identifier: GPL-2.0-only */
2 /*
3 * Copyright 2023 Red Hat
4 */
5
6 #ifndef UDS_INDEX_GEOMETRY_H
7 #define UDS_INDEX_GEOMETRY_H
8
9 #include "indexer.h"
10
11 /*
12 * The index_geometry records parameters that define the layout of a UDS index volume, and the size and
13 * shape of various index structures. It is created when the index is created, and is referenced by
14 * many index sub-components.
15 */
16
17 struct index_geometry {
18 /* Size of a chapter page, in bytes */
19 size_t bytes_per_page;
20 /* Number of record pages in a chapter */
21 u32 record_pages_per_chapter;
22 /* Total number of chapters in a volume */
23 u32 chapters_per_volume;
24 /* Number of sparsely-indexed chapters in a volume */
25 u32 sparse_chapters_per_volume;
26 /* Number of bits used to determine delta list numbers */
27 u8 chapter_delta_list_bits;
28 /* Virtual chapter remapped from physical chapter 0 */
29 u64 remapped_virtual;
30 /* New physical chapter where the remapped chapter can be found */
31 u64 remapped_physical;
32
33 /*
34 * The following properties are derived from the ones above, but they are computed and
35 * recorded as fields for convenience.
36 */
37 /* Total number of pages in a volume, excluding the header */
38 u32 pages_per_volume;
39 /* Total number of bytes in a volume, including the header */
40 size_t bytes_per_volume;
41 /* Number of pages in a chapter */
42 u32 pages_per_chapter;
43 /* Number of index pages in a chapter index */
44 u32 index_pages_per_chapter;
45 /* Number of records that fit on a page */
46 u32 records_per_page;
47 /* Number of records that fit in a chapter */
48 u32 records_per_chapter;
49 /* Number of records that fit in a volume */
50 u64 records_per_volume;
51 /* Number of delta lists per chapter index */
52 u32 delta_lists_per_chapter;
53 /* Mean delta for chapter indexes */
54 u32 chapter_mean_delta;
55 /* Number of bits needed for record page numbers */
56 u8 chapter_payload_bits;
57 /* Number of bits used to compute addresses for chapter delta lists */
58 u8 chapter_address_bits;
59 /* Number of densely-indexed chapters in a volume */
60 u32 dense_chapters_per_volume;
61 };
62
63 enum {
64 /* The number of bytes in a record (name + metadata) */
65 BYTES_PER_RECORD = (UDS_RECORD_NAME_SIZE + UDS_RECORD_DATA_SIZE),
66
67 /* The default length of a page in a chapter, in bytes */
68 DEFAULT_BYTES_PER_PAGE = 1024 * BYTES_PER_RECORD,
69
70 /* The default maximum number of records per page */
71 DEFAULT_RECORDS_PER_PAGE = DEFAULT_BYTES_PER_PAGE / BYTES_PER_RECORD,
72
73 /* The default number of record pages in a chapter */
74 DEFAULT_RECORD_PAGES_PER_CHAPTER = 256,
75
76 /* The default number of record pages in a chapter for a small index */
77 SMALL_RECORD_PAGES_PER_CHAPTER = 64,
78
79 /* The default number of chapters in a volume */
80 DEFAULT_CHAPTERS_PER_VOLUME = 1024,
81
82 /* The default number of sparsely-indexed chapters in a volume */
83 DEFAULT_SPARSE_CHAPTERS_PER_VOLUME = 0,
84
85 /* The log2 of the default mean delta */
86 DEFAULT_CHAPTER_MEAN_DELTA_BITS = 16,
87
88 /* The log2 of the number of delta lists in a large chapter */
89 DEFAULT_CHAPTER_DELTA_LIST_BITS = 12,
90
91 /* The log2 of the number of delta lists in a small chapter */
92 SMALL_CHAPTER_DELTA_LIST_BITS = 10,
93
94 /* The number of header pages per volume */
95 HEADER_PAGES_PER_VOLUME = 1,
96 };
97
98 int __must_check uds_make_index_geometry(size_t bytes_per_page, u32 record_pages_per_chapter,
99 u32 chapters_per_volume,
100 u32 sparse_chapters_per_volume, u64 remapped_virtual,
101 u64 remapped_physical,
102 struct index_geometry **geometry_ptr);
103
104 int __must_check uds_copy_index_geometry(struct index_geometry *source,
105 struct index_geometry **geometry_ptr);
106
107 void uds_free_index_geometry(struct index_geometry *geometry);
108
109 u32 __must_check uds_map_to_physical_chapter(const struct index_geometry *geometry,
110 u64 virtual_chapter);
111
112 /*
113 * Check whether this geometry is reduced by a chapter. This will only be true if the volume was
114 * converted from a non-lvm volume to an lvm volume.
115 */
116 static inline bool __must_check
uds_is_reduced_index_geometry(const struct index_geometry * geometry)117 uds_is_reduced_index_geometry(const struct index_geometry *geometry)
118 {
119 return !!(geometry->chapters_per_volume & 1);
120 }
121
122 static inline bool __must_check
uds_is_sparse_index_geometry(const struct index_geometry * geometry)123 uds_is_sparse_index_geometry(const struct index_geometry *geometry)
124 {
125 return geometry->sparse_chapters_per_volume > 0;
126 }
127
128 bool __must_check uds_has_sparse_chapters(const struct index_geometry *geometry,
129 u64 oldest_virtual_chapter,
130 u64 newest_virtual_chapter);
131
132 bool __must_check uds_is_chapter_sparse(const struct index_geometry *geometry,
133 u64 oldest_virtual_chapter,
134 u64 newest_virtual_chapter,
135 u64 virtual_chapter_number);
136
137 u32 __must_check uds_chapters_to_expire(const struct index_geometry *geometry,
138 u64 newest_chapter);
139
140 #endif /* UDS_INDEX_GEOMETRY_H */
141