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
get_entry_count(const struct index_geometry * geometry)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
uds_make_index_page_map(const struct index_geometry * geometry,struct index_page_map ** map_ptr)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
uds_free_index_page_map(struct index_page_map * map)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
uds_update_index_page_map(struct index_page_map * map,u64 virtual_chapter_number,u32 chapter_number,u32 index_page_number,u32 delta_list_number)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
uds_find_index_page_number(const struct index_page_map * map,const struct uds_record_name * name,u32 chapter_number)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
uds_get_list_number_bounds(const struct index_page_map * map,u32 chapter_number,u32 index_page_number,u32 * lowest_list,u32 * highest_list)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
uds_compute_index_page_map_save_size(const struct index_geometry * geometry)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
uds_write_index_page_map(struct index_page_map * map,struct buffered_writer * writer)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
uds_read_index_page_map(struct index_page_map * map,struct buffered_reader * reader)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