drivers/md/dm-vdo/indexer/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
  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 }