chapter-index.c

  1// SPDX-License-Identifier: GPL-2.0-only
  2/*
  3 * Copyright 2023 Red Hat
  4 */
  5
  6#include "chapter-index.h"
  7
  8#include "errors.h"
  9#include "logger.h"
 10#include "memory-alloc.h"
 11#include "permassert.h"
 12
 13#include "hash-utils.h"
 14#include "indexer.h"
 15
 16int uds_make_open_chapter_index(struct open_chapter_index **chapter_index,
 17				const struct index_geometry *geometry, u64 volume_nonce)
 18{
 19	int result;
 20	size_t memory_size;
 21	struct open_chapter_index *index;
 22
 23	result = vdo_allocate(1, struct open_chapter_index, "open chapter index", &index);
 24	if (result != VDO_SUCCESS)
 25		return result;
 26
 27	/*
 28	 * The delta index will rebalance delta lists when memory gets tight,
 29	 * so give the chapter index one extra page.
 30	 */
 31	memory_size = ((geometry->index_pages_per_chapter + 1) * geometry->bytes_per_page);
 32	index->geometry = geometry;
 33	index->volume_nonce = volume_nonce;
 34	result = uds_initialize_delta_index(&index->delta_index, 1,
 35					    geometry->delta_lists_per_chapter,
 36					    geometry->chapter_mean_delta,
 37					    geometry->chapter_payload_bits,
 38					    memory_size, 'm');
 39	if (result != UDS_SUCCESS) {
 40		vdo_free(index);
 41		return result;
 42	}
 43
 44	index->memory_size = index->delta_index.memory_size + sizeof(struct open_chapter_index);
 45	*chapter_index = index;
 46	return UDS_SUCCESS;
 47}
 48
 49void uds_free_open_chapter_index(struct open_chapter_index *chapter_index)
 50{
 51	if (chapter_index == NULL)
 52		return;
 53
 54	uds_uninitialize_delta_index(&chapter_index->delta_index);
 55	vdo_free(chapter_index);
 56}
 57
 58/* Re-initialize an open chapter index for a new chapter. */
 59void uds_empty_open_chapter_index(struct open_chapter_index *chapter_index,
 60				  u64 virtual_chapter_number)
 61{
 62	uds_reset_delta_index(&chapter_index->delta_index);
 63	chapter_index->virtual_chapter_number = virtual_chapter_number;
 64}
 65
 66static inline bool was_entry_found(const struct delta_index_entry *entry, u32 address)
 67{
 68	return (!entry->at_end) && (entry->key == address);
 69}
 70
 71/* Associate a record name with the record page containing its metadata. */
 72int uds_put_open_chapter_index_record(struct open_chapter_index *chapter_index,
 73				      const struct uds_record_name *name,
 74				      u32 page_number)
 75{
 76	int result;
 77	struct delta_index_entry entry;
 78	u32 address;
 79	u32 list_number;
 80	const u8 *found_name;
 81	bool found;
 82	const struct index_geometry *geometry = chapter_index->geometry;
 83	u64 chapter_number = chapter_index->virtual_chapter_number;
 84	u32 record_pages = geometry->record_pages_per_chapter;
 85
 86	result = VDO_ASSERT(page_number < record_pages,
 87			    "Page number within chapter (%u) exceeds the maximum value %u",
 88			    page_number, record_pages);
 89	if (result != VDO_SUCCESS)
 90		return UDS_INVALID_ARGUMENT;
 91
 92	address = uds_hash_to_chapter_delta_address(name, geometry);
 93	list_number = uds_hash_to_chapter_delta_list(name, geometry);
 94	result = uds_get_delta_index_entry(&chapter_index->delta_index, list_number,
 95					   address, name->name, &entry);
 96	if (result != UDS_SUCCESS)
 97		return result;
 98
 99	found = was_entry_found(&entry, address);
100	result = VDO_ASSERT(!(found && entry.is_collision),
101			    "Chunk appears more than once in chapter %llu",
102			    (unsigned long long) chapter_number);
103	if (result != VDO_SUCCESS)
104		return UDS_BAD_STATE;
105
106	found_name = (found ? name->name : NULL);
107	return uds_put_delta_index_entry(&entry, address, page_number, found_name);
108}
109
110/*
111 * Pack a section of an open chapter index into a chapter index page. A range of delta lists
112 * (starting with a specified list index) is copied from the open chapter index into a memory page.
113 * The number of lists copied onto the page is returned to the caller on success.
114 *
115 * @chapter_index: The open chapter index
116 * @memory: The memory page to use
117 * @first_list: The first delta list number to be copied
118 * @last_page: If true, this is the last page of the chapter index and all the remaining lists must
119 *             be packed onto this page
120 * @lists_packed: The number of delta lists that were packed onto this page
121 */
122int uds_pack_open_chapter_index_page(struct open_chapter_index *chapter_index,
123				     u8 *memory, u32 first_list, bool last_page,
124				     u32 *lists_packed)
125{
126	int result;
127	struct delta_index *delta_index = &chapter_index->delta_index;
128	struct delta_index_stats stats;
129	u64 nonce = chapter_index->volume_nonce;
130	u64 chapter_number = chapter_index->virtual_chapter_number;
131	const struct index_geometry *geometry = chapter_index->geometry;
132	u32 list_count = geometry->delta_lists_per_chapter;
133	unsigned int removals = 0;
134	struct delta_index_entry entry;
135	u32 next_list;
136	s32 list_number;
137
138	for (;;) {
139		result = uds_pack_delta_index_page(delta_index, nonce, memory,
140						   geometry->bytes_per_page,
141						   chapter_number, first_list,
142						   lists_packed);
143		if (result != UDS_SUCCESS)
144			return result;
145
146		if ((first_list + *lists_packed) == list_count) {
147			/* All lists are packed. */
148			break;
149		} else if (*lists_packed == 0) {
150			/*
151			 * The next delta list does not fit on a page. This delta list will be
152			 * removed.
153			 */
154		} else if (last_page) {
155			/*
156			 * This is the last page and there are lists left unpacked, but all of the
157			 * remaining lists must fit on the page. Find a list that contains entries
158			 * and remove the entire list. Try the first list that does not fit. If it
159			 * is empty, we will select the last list that already fits and has any
160			 * entries.
161			 */
162		} else {
163			/* This page is done. */
164			break;
165		}
166
167		if (removals == 0) {
168			uds_get_delta_index_stats(delta_index, &stats);
169			vdo_log_warning("The chapter index for chapter %llu contains %llu entries with %llu collisions",
170					(unsigned long long) chapter_number,
171					(unsigned long long) stats.record_count,
172					(unsigned long long) stats.collision_count);
173		}
174
175		list_number = *lists_packed;
176		do {
177			if (list_number < 0)
178				return UDS_OVERFLOW;
179
180			next_list = first_list + list_number--;
181			result = uds_start_delta_index_search(delta_index, next_list, 0,
182							      &entry);
183			if (result != UDS_SUCCESS)
184				return result;
185
186			result = uds_next_delta_index_entry(&entry);
187			if (result != UDS_SUCCESS)
188				return result;
189		} while (entry.at_end);
190
191		do {
192			result = uds_remove_delta_index_entry(&entry);
193			if (result != UDS_SUCCESS)
194				return result;
195
196			removals++;
197		} while (!entry.at_end);
198	}
199
200	if (removals > 0) {
201		vdo_log_warning("To avoid chapter index page overflow in chapter %llu, %u entries were removed from the chapter index",
202				(unsigned long long) chapter_number, removals);
203	}
204
205	return UDS_SUCCESS;
206}
207
208/* Make a new chapter index page, initializing it with the data from a given index_page buffer. */
209int uds_initialize_chapter_index_page(struct delta_index_page *index_page,
210				      const struct index_geometry *geometry,
211				      u8 *page_buffer, u64 volume_nonce)
212{
213	return uds_initialize_delta_index_page(index_page, volume_nonce,
214					       geometry->chapter_mean_delta,
215					       geometry->chapter_payload_bits,
216					       page_buffer, geometry->bytes_per_page);
217}
218
219/* Validate a chapter index page read during rebuild. */
220int uds_validate_chapter_index_page(const struct delta_index_page *index_page,
221				    const struct index_geometry *geometry)
222{
223	int result;
224	const struct delta_index *delta_index = &index_page->delta_index;
225	u32 first = index_page->lowest_list_number;
226	u32 last = index_page->highest_list_number;
227	u32 list_number;
228
229	/* We walk every delta list from start to finish. */
230	for (list_number = first; list_number <= last; list_number++) {
231		struct delta_index_entry entry;
232
233		result = uds_start_delta_index_search(delta_index, list_number - first,
234						      0, &entry);
235		if (result != UDS_SUCCESS)
236			return result;
237
238		for (;;) {
239			result = uds_next_delta_index_entry(&entry);
240			if (result != UDS_SUCCESS) {
241				/*
242				 * A random bit stream is highly likely to arrive here when we go
243				 * past the end of the delta list.
244				 */
245				return result;
246			}
247
248			if (entry.at_end)
249				break;
250
251			/* Also make sure that the record page field contains a plausible value. */
252			if (uds_get_delta_entry_value(&entry) >=
253			    geometry->record_pages_per_chapter) {
254				/*
255				 * Do not log this as an error. It happens in normal operation when
256				 * we are doing a rebuild but haven't written the entire volume
257				 * once.
258				 */
259				return UDS_CORRUPT_DATA;
260			}
261		}
262	}
263	return UDS_SUCCESS;
264}
265
266/*
267 * Search a chapter index page for a record name, returning the record page number that may contain
268 * the name.
269 */
270int uds_search_chapter_index_page(struct delta_index_page *index_page,
271				  const struct index_geometry *geometry,
272				  const struct uds_record_name *name,
273				  u16 *record_page_ptr)
274{
275	int result;
276	struct delta_index *delta_index = &index_page->delta_index;
277	u32 address = uds_hash_to_chapter_delta_address(name, geometry);
278	u32 delta_list_number = uds_hash_to_chapter_delta_list(name, geometry);
279	u32 sub_list_number = delta_list_number - index_page->lowest_list_number;
280	struct delta_index_entry entry;
281
282	result = uds_get_delta_index_entry(delta_index, sub_list_number, address,
283					   name->name, &entry);
284	if (result != UDS_SUCCESS)
285		return result;
286
287	if (was_entry_found(&entry, address))
288		*record_page_ptr = uds_get_delta_entry_value(&entry);
289	else
290		*record_page_ptr = NO_CHAPTER_INDEX_ENTRY;
291
292	return UDS_SUCCESS;
293}