1 // SPDX-License-Identifier: GPL-2.0-only
13 #include "memory-alloc.h"
16 #include "delta-index.h"
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
26  * derive the rest of the layout and other index properties.
45  * as many chapters as the corresponding non-sparse volume, which provides 10 times the
47  * non-sparse volume with the same memory footprint.
49  * If the volume has been converted from a non-lvm format to an lvm volume, the number of chapters
68 	geometry->bytes_per_page = bytes_per_page;  in uds_make_index_geometry()
69 	geometry->record_pages_per_chapter = record_pages_per_chapter;  in uds_make_index_geometry()
70 	geometry->chapters_per_volume = chapters_per_volume;  in uds_make_index_geometry()
71 	geometry->sparse_chapters_per_volume = sparse_chapters_per_volume;  in uds_make_index_geometry()
72 	geometry->dense_chapters_per_volume = chapters_per_volume - sparse_chapters_per_volume;  in uds_make_index_geometry()
73 	geometry->remapped_virtual = remapped_virtual;  in uds_make_index_geometry()
74 	geometry->remapped_physical = remapped_physical;  in uds_make_index_geometry()
76 	geometry->records_per_page = bytes_per_page / BYTES_PER_RECORD;  in uds_make_index_geometry()
77 	geometry->records_per_chapter = geometry->records_per_page * record_pages_per_chapter;  in uds_make_index_geometry()
78 	geometry->records_per_volume = (u64) geometry->records_per_chapter * chapters_per_volume;  in uds_make_index_geometry()
80 	geometry->chapter_mean_delta = 1 << DEFAULT_CHAPTER_MEAN_DELTA_BITS;  in uds_make_index_geometry()
81 	geometry->chapter_payload_bits = bits_per(record_pages_per_chapter - 1);  in uds_make_index_geometry()
87 	geometry->chapter_delta_list_bits =  in uds_make_index_geometry()
88 		bits_per((geometry->records_per_chapter - 1) | 077) - 6;  in uds_make_index_geometry()
89 	geometry->delta_lists_per_chapter = 1 << geometry->chapter_delta_list_bits;  in uds_make_index_geometry()
91 	geometry->chapter_address_bits =  in uds_make_index_geometry()
92 		(DEFAULT_CHAPTER_MEAN_DELTA_BITS -  in uds_make_index_geometry()
93 		 geometry->chapter_delta_list_bits +  in uds_make_index_geometry()
94 		 bits_per(geometry->records_per_chapter - 1));  in uds_make_index_geometry()
95 	geometry->index_pages_per_chapter =  in uds_make_index_geometry()
96 		uds_get_delta_index_page_count(geometry->records_per_chapter,  in uds_make_index_geometry()
97 					       geometry->delta_lists_per_chapter,  in uds_make_index_geometry()
98 					       geometry->chapter_mean_delta,  in uds_make_index_geometry()
99 					       geometry->chapter_payload_bits,  in uds_make_index_geometry()
102 	geometry->pages_per_chapter = geometry->index_pages_per_chapter + record_pages_per_chapter;  in uds_make_index_geometry()
103 	geometry->pages_per_volume = geometry->pages_per_chapter * chapters_per_volume;  in uds_make_index_geometry()
104 	geometry->bytes_per_volume =  in uds_make_index_geometry()
105 		bytes_per_page * (geometry->pages_per_volume + HEADER_PAGES_PER_VOLUME);  in uds_make_index_geometry()
114 	return uds_make_index_geometry(source->bytes_per_page,  in uds_copy_index_geometry()
115 				       source->record_pages_per_chapter,  in uds_copy_index_geometry()
116 				       source->chapters_per_volume,  in uds_copy_index_geometry()
117 				       source->sparse_chapters_per_volume,  in uds_copy_index_geometry()
118 				       source->remapped_virtual, source->remapped_physical,  in uds_copy_index_geometry()
133 		return virtual_chapter % geometry->chapters_per_volume;  in uds_map_to_physical_chapter()
135 	if (likely(virtual_chapter > geometry->remapped_virtual)) {  in uds_map_to_physical_chapter()
136 		delta = virtual_chapter - geometry->remapped_virtual;  in uds_map_to_physical_chapter()
137 		if (likely(delta > geometry->remapped_physical))  in uds_map_to_physical_chapter()
138 			return delta % geometry->chapters_per_volume;  in uds_map_to_physical_chapter()
140 			return delta - 1;  in uds_map_to_physical_chapter()
143 	if (virtual_chapter == geometry->remapped_virtual)  in uds_map_to_physical_chapter()
144 		return geometry->remapped_physical;  in uds_map_to_physical_chapter()
146 	delta = geometry->remapped_virtual - virtual_chapter;  in uds_map_to_physical_chapter()
147 	if (delta < geometry->chapters_per_volume)  in uds_map_to_physical_chapter()
148 		return geometry->chapters_per_volume - delta;  in uds_map_to_physical_chapter()
159 		((newest_virtual_chapter - oldest_virtual_chapter + 1) >  in uds_has_sparse_chapters()
160 		 geometry->dense_chapters_per_volume);  in uds_has_sparse_chapters()
169 		((virtual_chapter_number + geometry->dense_chapters_per_volume) <=  in uds_is_chapter_sparse()
177 	if (newest_chapter < geometry->chapters_per_volume)  in uds_chapters_to_expire()
181 	if (geometry->remapped_physical > 0) {  in uds_chapters_to_expire()
182 		u64 oldest_chapter = newest_chapter - geometry->chapters_per_volume;  in uds_chapters_to_expire()
188 		if (oldest_chapter == geometry->remapped_virtual)  in uds_chapters_to_expire()
195 		if (oldest_chapter == (geometry->remapped_virtual + geometry->remapped_physical))  in uds_chapters_to_expire()