294 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright 2023 Red Hat4 */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 lists112 * (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 index116 * @memory: The memory page to use117 * @first_list: The first delta list number to be copied118 * @last_page: If true, this is the last page of the chapter index and all the remaining lists must119 * be packed onto this page120 * @lists_packed: The number of delta lists that were packed onto this page121 */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 be152 * removed.153 */154 } else if (last_page) {155 /*156 * This is the last page and there are lists left unpacked, but all of the157 * remaining lists must fit on the page. Find a list that contains entries158 * and remove the entire list. Try the first list that does not fit. If it159 * is empty, we will select the last list that already fits and has any160 * 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 go243 * 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 when256 * we are doing a rebuild but haven't written the entire volume257 * 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 contain268 * 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 else290 *record_page_ptr = NO_CHAPTER_INDEX_ENTRY;291 292 return UDS_SUCCESS;293}294