1 // SPDX-License-Identifier: GPL-2.0-only 2 /* 3 * Copyright 2023 Red Hat 4 */ 5 6 #include "index-page-map.h" 7 8 #include "errors.h" 9 #include "logger.h" 10 #include "memory-alloc.h" 11 #include "numeric.h" 12 #include "permassert.h" 13 #include "string-utils.h" 14 #include "thread-utils.h" 15 16 #include "hash-utils.h" 17 #include "indexer.h" 18 19 /* 20 * The index page map is conceptually a two-dimensional array indexed by chapter number and index 21 * page number within the chapter. Each entry contains the number of the last delta list on that 22 * index page. In order to save memory, the information for the last page in each chapter is not 23 * recorded, as it is known from the geometry. 24 */ 25 26 static const u8 PAGE_MAP_MAGIC[] = "ALBIPM02"; 27 28 #define PAGE_MAP_MAGIC_LENGTH (sizeof(PAGE_MAP_MAGIC) - 1) 29 30 static inline u32 get_entry_count(const struct index_geometry *geometry) 31 { 32 return geometry->chapters_per_volume * (geometry->index_pages_per_chapter - 1); 33 } 34 35 int uds_make_index_page_map(const struct index_geometry *geometry, 36 struct index_page_map **map_ptr) 37 { 38 int result; 39 struct index_page_map *map; 40 41 result = vdo_allocate(1, struct index_page_map, "page map", &map); 42 if (result != VDO_SUCCESS) 43 return result; 44 45 map->geometry = geometry; 46 map->entries_per_chapter = geometry->index_pages_per_chapter - 1; 47 result = vdo_allocate(get_entry_count(geometry), u16, "Index Page Map Entries", 48 &map->entries); 49 if (result != VDO_SUCCESS) { 50 uds_free_index_page_map(map); 51 return result; 52 } 53 54 *map_ptr = map; 55 return UDS_SUCCESS; 56 } 57 58 void uds_free_index_page_map(struct index_page_map *map) 59 { 60 if (map != NULL) { 61 vdo_free(map->entries); 62 vdo_free(map); 63 } 64 } 65 66 void uds_update_index_page_map(struct index_page_map *map, u64 virtual_chapter_number, 67 u32 chapter_number, u32 index_page_number, 68 u32 delta_list_number) 69 { 70 size_t slot; 71 72 map->last_update = virtual_chapter_number; 73 if (index_page_number == map->entries_per_chapter) 74 return; 75 76 slot = (chapter_number * map->entries_per_chapter) + index_page_number; 77 map->entries[slot] = delta_list_number; 78 } 79 80 u32 uds_find_index_page_number(const struct index_page_map *map, 81 const struct uds_record_name *name, u32 chapter_number) 82 { 83 u32 delta_list_number = uds_hash_to_chapter_delta_list(name, map->geometry); 84 u32 slot = chapter_number * map->entries_per_chapter; 85 u32 page; 86 87 for (page = 0; page < map->entries_per_chapter; page++) { 88 if (delta_list_number <= map->entries[slot + page]) 89 break; 90 } 91 92 return page; 93 } 94 95 void uds_get_list_number_bounds(const struct index_page_map *map, u32 chapter_number, 96 u32 index_page_number, u32 *lowest_list, 97 u32 *highest_list) 98 { 99 u32 slot = chapter_number * map->entries_per_chapter; 100 101 *lowest_list = ((index_page_number == 0) ? 102 0 : map->entries[slot + index_page_number - 1] + 1); 103 *highest_list = ((index_page_number < map->entries_per_chapter) ? 104 map->entries[slot + index_page_number] : 105 map->geometry->delta_lists_per_chapter - 1); 106 } 107 108 u64 uds_compute_index_page_map_save_size(const struct index_geometry *geometry) 109 { 110 return PAGE_MAP_MAGIC_LENGTH + sizeof(u64) + sizeof(u16) * get_entry_count(geometry); 111 } 112 113 int uds_write_index_page_map(struct index_page_map *map, struct buffered_writer *writer) 114 { 115 int result; 116 u8 *buffer; 117 size_t offset = 0; 118 u64 saved_size = uds_compute_index_page_map_save_size(map->geometry); 119 u32 i; 120 121 result = vdo_allocate(saved_size, u8, "page map data", &buffer); 122 if (result != VDO_SUCCESS) 123 return result; 124 125 memcpy(buffer, PAGE_MAP_MAGIC, PAGE_MAP_MAGIC_LENGTH); 126 offset += PAGE_MAP_MAGIC_LENGTH; 127 encode_u64_le(buffer, &offset, map->last_update); 128 for (i = 0; i < get_entry_count(map->geometry); i++) 129 encode_u16_le(buffer, &offset, map->entries[i]); 130 131 result = uds_write_to_buffered_writer(writer, buffer, offset); 132 vdo_free(buffer); 133 if (result != UDS_SUCCESS) 134 return result; 135 136 return uds_flush_buffered_writer(writer); 137 } 138 139 int uds_read_index_page_map(struct index_page_map *map, struct buffered_reader *reader) 140 { 141 int result; 142 u8 magic[PAGE_MAP_MAGIC_LENGTH]; 143 u8 *buffer; 144 size_t offset = 0; 145 u64 saved_size = uds_compute_index_page_map_save_size(map->geometry); 146 u32 i; 147 148 result = vdo_allocate(saved_size, u8, "page map data", &buffer); 149 if (result != VDO_SUCCESS) 150 return result; 151 152 result = uds_read_from_buffered_reader(reader, buffer, saved_size); 153 if (result != UDS_SUCCESS) { 154 vdo_free(buffer); 155 return result; 156 } 157 158 memcpy(&magic, buffer, PAGE_MAP_MAGIC_LENGTH); 159 offset += PAGE_MAP_MAGIC_LENGTH; 160 if (memcmp(magic, PAGE_MAP_MAGIC, PAGE_MAP_MAGIC_LENGTH) != 0) { 161 vdo_free(buffer); 162 return UDS_CORRUPT_DATA; 163 } 164 165 decode_u64_le(buffer, &offset, &map->last_update); 166 for (i = 0; i < get_entry_count(map->geometry); i++) 167 decode_u16_le(buffer, &offset, &map->entries[i]); 168 169 vdo_free(buffer); 170 vdo_log_debug("read index page map, last update %llu", 171 (unsigned long long) map->last_update); 172 return UDS_SUCCESS; 173 } 174