1 // SPDX-License-Identifier: GPL-2.0-only
2 /*
3 * Copyright 2023 Red Hat
4 */
5
6 #include "geometry.h"
7
8 #include <linux/compiler.h>
9 #include <linux/log2.h>
10
11 #include "errors.h"
12 #include "logger.h"
13 #include "memory-alloc.h"
14 #include "permassert.h"
15
16 #include "delta-index.h"
17 #include "indexer.h"
18
19 /*
20 * An index volume is divided into a fixed number of fixed-size chapters, each consisting of a
21 * fixed number of fixed-size pages. The volume layout is defined by two constants and four
22 * parameters. The constants are that index records are 32 bytes long (16-byte block name plus
23 * 16-byte metadata) and that open chapter index hash slots are one byte long. The four parameters
24 * are the number of bytes in a page, the number of record pages in a chapter, the number of
25 * chapters in a volume, and the number of chapters that are sparse. From these parameters, we can
26 * derive the rest of the layout and other index properties.
27 *
28 * The index volume is sized by its maximum memory footprint. For a dense index, the persistent
29 * storage is about 10 times the size of the memory footprint. For a sparse index, the persistent
30 * storage is about 100 times the size of the memory footprint.
31 *
32 * For a small index with a memory footprint less than 1GB, there are three possible memory
33 * configurations: 0.25GB, 0.5GB and 0.75GB. The default geometry for each is 1024 index records
34 * per 32 KB page, 1024 chapters per volume, and either 64, 128, or 192 record pages per chapter
35 * (resulting in 6, 13, or 20 index pages per chapter) depending on the memory configuration. For
36 * the VDO default of a 0.25 GB index, this yields a deduplication window of 256 GB using about 2.5
37 * GB for the persistent storage and 256 MB of RAM.
38 *
39 * For a larger index with a memory footprint that is a multiple of 1 GB, the geometry is 1024
40 * index records per 32 KB page, 256 record pages per chapter, 26 index pages per chapter, and 1024
41 * chapters for every GB of memory footprint. For a 1 GB volume, this yields a deduplication window
42 * of 1 TB using about 9GB of persistent storage and 1 GB of RAM.
43 *
44 * The above numbers hold for volumes which have no sparse chapters. A sparse volume has 10 times
45 * as many chapters as the corresponding non-sparse volume, which provides 10 times the
46 * deduplication window while using 10 times as much persistent storage as the equivalent
47 * non-sparse volume with the same memory footprint.
48 *
49 * If the volume has been converted from a non-lvm format to an lvm volume, the number of chapters
50 * per volume will have been reduced by one by eliminating physical chapter 0, and the virtual
51 * chapter that formerly mapped to physical chapter 0 may be remapped to another physical chapter.
52 * This remapping is expressed by storing which virtual chapter was remapped, and which physical
53 * chapter it was moved to.
54 */
55
uds_make_index_geometry(size_t bytes_per_page,u32 record_pages_per_chapter,u32 chapters_per_volume,u32 sparse_chapters_per_volume,u64 remapped_virtual,u64 remapped_physical,struct index_geometry ** geometry_ptr)56 int uds_make_index_geometry(size_t bytes_per_page, u32 record_pages_per_chapter,
57 u32 chapters_per_volume, u32 sparse_chapters_per_volume,
58 u64 remapped_virtual, u64 remapped_physical,
59 struct index_geometry **geometry_ptr)
60 {
61 int result;
62 struct index_geometry *geometry;
63
64 result = vdo_allocate(1, struct index_geometry, "geometry", &geometry);
65 if (result != VDO_SUCCESS)
66 return result;
67
68 geometry->bytes_per_page = bytes_per_page;
69 geometry->record_pages_per_chapter = record_pages_per_chapter;
70 geometry->chapters_per_volume = chapters_per_volume;
71 geometry->sparse_chapters_per_volume = sparse_chapters_per_volume;
72 geometry->dense_chapters_per_volume = chapters_per_volume - sparse_chapters_per_volume;
73 geometry->remapped_virtual = remapped_virtual;
74 geometry->remapped_physical = remapped_physical;
75
76 geometry->records_per_page = bytes_per_page / BYTES_PER_RECORD;
77 geometry->records_per_chapter = geometry->records_per_page * record_pages_per_chapter;
78 geometry->records_per_volume = (u64) geometry->records_per_chapter * chapters_per_volume;
79
80 geometry->chapter_mean_delta = 1 << DEFAULT_CHAPTER_MEAN_DELTA_BITS;
81 geometry->chapter_payload_bits = bits_per(record_pages_per_chapter - 1);
82 /*
83 * We want 1 delta list for every 64 records in the chapter.
84 * The "| 077" ensures that the chapter_delta_list_bits computation
85 * does not underflow.
86 */
87 geometry->chapter_delta_list_bits =
88 bits_per((geometry->records_per_chapter - 1) | 077) - 6;
89 geometry->delta_lists_per_chapter = 1 << geometry->chapter_delta_list_bits;
90 /* We need enough address bits to achieve the desired mean delta. */
91 geometry->chapter_address_bits =
92 (DEFAULT_CHAPTER_MEAN_DELTA_BITS -
93 geometry->chapter_delta_list_bits +
94 bits_per(geometry->records_per_chapter - 1));
95 geometry->index_pages_per_chapter =
96 uds_get_delta_index_page_count(geometry->records_per_chapter,
97 geometry->delta_lists_per_chapter,
98 geometry->chapter_mean_delta,
99 geometry->chapter_payload_bits,
100 bytes_per_page);
101
102 geometry->pages_per_chapter = geometry->index_pages_per_chapter + record_pages_per_chapter;
103 geometry->pages_per_volume = geometry->pages_per_chapter * chapters_per_volume;
104 geometry->bytes_per_volume =
105 bytes_per_page * (geometry->pages_per_volume + HEADER_PAGES_PER_VOLUME);
106
107 *geometry_ptr = geometry;
108 return UDS_SUCCESS;
109 }
110
uds_copy_index_geometry(struct index_geometry * source,struct index_geometry ** geometry_ptr)111 int uds_copy_index_geometry(struct index_geometry *source,
112 struct index_geometry **geometry_ptr)
113 {
114 return uds_make_index_geometry(source->bytes_per_page,
115 source->record_pages_per_chapter,
116 source->chapters_per_volume,
117 source->sparse_chapters_per_volume,
118 source->remapped_virtual, source->remapped_physical,
119 geometry_ptr);
120 }
121
uds_free_index_geometry(struct index_geometry * geometry)122 void uds_free_index_geometry(struct index_geometry *geometry)
123 {
124 vdo_free(geometry);
125 }
126
uds_map_to_physical_chapter(const struct index_geometry * geometry,u64 virtual_chapter)127 u32 __must_check uds_map_to_physical_chapter(const struct index_geometry *geometry,
128 u64 virtual_chapter)
129 {
130 u64 delta;
131
132 if (!uds_is_reduced_index_geometry(geometry))
133 return virtual_chapter % geometry->chapters_per_volume;
134
135 if (likely(virtual_chapter > geometry->remapped_virtual)) {
136 delta = virtual_chapter - geometry->remapped_virtual;
137 if (likely(delta > geometry->remapped_physical))
138 return delta % geometry->chapters_per_volume;
139 else
140 return delta - 1;
141 }
142
143 if (virtual_chapter == geometry->remapped_virtual)
144 return geometry->remapped_physical;
145
146 delta = geometry->remapped_virtual - virtual_chapter;
147 if (delta < geometry->chapters_per_volume)
148 return geometry->chapters_per_volume - delta;
149
150 /* This chapter is so old the answer doesn't matter. */
151 return 0;
152 }
153
154 /* Check whether any sparse chapters are in use. */
uds_has_sparse_chapters(const struct index_geometry * geometry,u64 oldest_virtual_chapter,u64 newest_virtual_chapter)155 bool uds_has_sparse_chapters(const struct index_geometry *geometry,
156 u64 oldest_virtual_chapter, u64 newest_virtual_chapter)
157 {
158 return uds_is_sparse_index_geometry(geometry) &&
159 ((newest_virtual_chapter - oldest_virtual_chapter + 1) >
160 geometry->dense_chapters_per_volume);
161 }
162
uds_is_chapter_sparse(const struct index_geometry * geometry,u64 oldest_virtual_chapter,u64 newest_virtual_chapter,u64 virtual_chapter_number)163 bool uds_is_chapter_sparse(const struct index_geometry *geometry,
164 u64 oldest_virtual_chapter, u64 newest_virtual_chapter,
165 u64 virtual_chapter_number)
166 {
167 return uds_has_sparse_chapters(geometry, oldest_virtual_chapter,
168 newest_virtual_chapter) &&
169 ((virtual_chapter_number + geometry->dense_chapters_per_volume) <=
170 newest_virtual_chapter);
171 }
172
173 /* Calculate how many chapters to expire after opening the newest chapter. */
uds_chapters_to_expire(const struct index_geometry * geometry,u64 newest_chapter)174 u32 uds_chapters_to_expire(const struct index_geometry *geometry, u64 newest_chapter)
175 {
176 /* If the index isn't full yet, don't expire anything. */
177 if (newest_chapter < geometry->chapters_per_volume)
178 return 0;
179
180 /* If a chapter is out of order... */
181 if (geometry->remapped_physical > 0) {
182 u64 oldest_chapter = newest_chapter - geometry->chapters_per_volume;
183
184 /*
185 * ... expire an extra chapter when expiring the moved chapter to free physical
186 * space for the new chapter ...
187 */
188 if (oldest_chapter == geometry->remapped_virtual)
189 return 2;
190
191 /*
192 * ... but don't expire anything when the new chapter will use the physical chapter
193 * freed by expiring the moved chapter.
194 */
195 if (oldest_chapter == (geometry->remapped_virtual + geometry->remapped_physical))
196 return 0;
197 }
198
199 /* Normally, just expire one. */
200 return 1;
201 }
202