index-page-map.c

  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
 26static const u8 PAGE_MAP_MAGIC[] = "ALBIPM02";
 27
 28#define PAGE_MAP_MAGIC_LENGTH (sizeof(PAGE_MAP_MAGIC) - 1)
 29
 30static 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
 35int 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
 58void 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
 66void 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
 80u32 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
 95void 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
108u64 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
113int 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
139int 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}