174 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright 2023 Red Hat4 */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 index21 * page number within the chapter. Each entry contains the number of the last delta list on that22 * index page. In order to save memory, the information for the last page in each chapter is not23 * 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}174