1 // SPDX-License-Identifier: GPL-2.0-only
6 #include "chapter-index.h"
10 #include "memory-alloc.h"
13 #include "hash-utils.h"
31 	memory_size = ((geometry->index_pages_per_chapter + 1) * geometry->bytes_per_page);  in uds_make_open_chapter_index()
32 	index->geometry = geometry;  in uds_make_open_chapter_index()
33 	index->volume_nonce = volume_nonce;  in uds_make_open_chapter_index()
34 	result = uds_initialize_delta_index(&index->delta_index, 1,  in uds_make_open_chapter_index()
35 					    geometry->delta_lists_per_chapter,  in uds_make_open_chapter_index()
36 					    geometry->chapter_mean_delta,  in uds_make_open_chapter_index()
37 					    geometry->chapter_payload_bits,  in uds_make_open_chapter_index()
44 	index->memory_size = index->delta_index.memory_size + sizeof(struct open_chapter_index);  in uds_make_open_chapter_index()
54 	uds_uninitialize_delta_index(&chapter_index->delta_index);  in uds_free_open_chapter_index()
58 /* Re-initialize an open chapter index for a new chapter. */
62 	uds_reset_delta_index(&chapter_index->delta_index);  in uds_empty_open_chapter_index()
63 	chapter_index->virtual_chapter_number = virtual_chapter_number;  in uds_empty_open_chapter_index()
66 static inline bool was_entry_found(const struct delta_index_entry *entry, u32 address)  in was_entry_found()  argument
68 	return (!entry->at_end) && (entry->key == address);  in was_entry_found()
77 	struct delta_index_entry entry;  in uds_put_open_chapter_index_record()  local
78 	u32 address;  in uds_put_open_chapter_index_record()  local
82 	const struct index_geometry *geometry = chapter_index->geometry;  in uds_put_open_chapter_index_record()
83 	u64 chapter_number = chapter_index->virtual_chapter_number;  in uds_put_open_chapter_index_record()
84 	u32 record_pages = geometry->record_pages_per_chapter;  in uds_put_open_chapter_index_record()
92 	address = uds_hash_to_chapter_delta_address(name, geometry);  in uds_put_open_chapter_index_record()
94 	result = uds_get_delta_index_entry(&chapter_index->delta_index, list_number,  in uds_put_open_chapter_index_record()
95 					   address, name->name, &entry);  in uds_put_open_chapter_index_record()
99 	found = was_entry_found(&entry, address);  in uds_put_open_chapter_index_record()
100 	result = VDO_ASSERT(!(found && entry.is_collision),  in uds_put_open_chapter_index_record()
106 	found_name = (found ? name->name : NULL);  in uds_put_open_chapter_index_record()
107 	return uds_put_delta_index_entry(&entry, address, page_number, found_name);  in uds_put_open_chapter_index_record()
127 	struct delta_index *delta_index = &chapter_index->delta_index;  in uds_pack_open_chapter_index_page()
129 	u64 nonce = chapter_index->volume_nonce;  in uds_pack_open_chapter_index_page()
130 	u64 chapter_number = chapter_index->virtual_chapter_number;  in uds_pack_open_chapter_index_page()
131 	const struct index_geometry *geometry = chapter_index->geometry;  in uds_pack_open_chapter_index_page()
132 	u32 list_count = geometry->delta_lists_per_chapter;  in uds_pack_open_chapter_index_page()
134 	struct delta_index_entry entry;  in uds_pack_open_chapter_index_page()  local
140 						   geometry->bytes_per_page,  in uds_pack_open_chapter_index_page()
180 			next_list = first_list + list_number--;  in uds_pack_open_chapter_index_page()
182 							      &entry);  in uds_pack_open_chapter_index_page()
186 			result = uds_next_delta_index_entry(&entry);  in uds_pack_open_chapter_index_page()
189 		} while (entry.at_end);  in uds_pack_open_chapter_index_page()
192 			result = uds_remove_delta_index_entry(&entry);  in uds_pack_open_chapter_index_page()
197 		} while (!entry.at_end);  in uds_pack_open_chapter_index_page()
214 					       geometry->chapter_mean_delta,  in uds_initialize_chapter_index_page()
215 					       geometry->chapter_payload_bits,  in uds_initialize_chapter_index_page()
216 					       page_buffer, geometry->bytes_per_page);  in uds_initialize_chapter_index_page()
224 	const struct delta_index *delta_index = &index_page->delta_index;  in uds_validate_chapter_index_page()
225 	u32 first = index_page->lowest_list_number;  in uds_validate_chapter_index_page()
226 	u32 last = index_page->highest_list_number;  in uds_validate_chapter_index_page()
231 		struct delta_index_entry entry;  in uds_validate_chapter_index_page()  local
233 		result = uds_start_delta_index_search(delta_index, list_number - first,  in uds_validate_chapter_index_page()
234 						      0, &entry);  in uds_validate_chapter_index_page()
239 			result = uds_next_delta_index_entry(&entry);  in uds_validate_chapter_index_page()
248 			if (entry.at_end)  in uds_validate_chapter_index_page()
252 			if (uds_get_delta_entry_value(&entry) >=  in uds_validate_chapter_index_page()
253 			    geometry->record_pages_per_chapter) {  in uds_validate_chapter_index_page()
276 	struct delta_index *delta_index = &index_page->delta_index;  in uds_search_chapter_index_page()
277 	u32 address = uds_hash_to_chapter_delta_address(name, geometry);  in uds_search_chapter_index_page()  local
279 	u32 sub_list_number = delta_list_number - index_page->lowest_list_number;  in uds_search_chapter_index_page()
280 	struct delta_index_entry entry;  in uds_search_chapter_index_page()  local
282 	result = uds_get_delta_index_entry(delta_index, sub_list_number, address,  in uds_search_chapter_index_page()
283 					   name->name, &entry);  in uds_search_chapter_index_page()
287 	if (was_entry_found(&entry, address))  in uds_search_chapter_index_page()
288 		*record_page_ptr = uds_get_delta_entry_value(&entry);  in uds_search_chapter_index_page()