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 16 int 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 49 void 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. */ 59 void 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 66 static 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. */ 72 int 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 */ 122 int 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. */ 209 int 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. */ 220 int 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 */ 270 int 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 } 294