drivers/md/dm-vdo/indexer/chapter-index.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #include "chapter-index.h"
   7
   8 #include "errors.h"
   9 #include "logger.h"
  10 #include "memory-alloc.h"
  11 #include "permassert.h"
  12
  13 #include "hash-utils.h"
  14 #include "indexer.h"
  15
  16 int uds_make_open_chapter_index(struct open_chapter_index **chapter_index,
  17                                 const struct index_geometry *geometry, u64 volume_nonce)
  18 {
  19         int result;
  20         size_t memory_size;
  21         struct open_chapter_index *index;
  22
  23         result = vdo_allocate(1, struct open_chapter_index, "open chapter index", &index);
  24         if (result != VDO_SUCCESS)
  25                 return result;
  26
  27         /*
  28          * The delta index will rebalance delta lists when memory gets tight,
  29          * so give the chapter index one extra page.
  30          */
  31         memory_size = ((geometry->index_pages_per_chapter + 1) * geometry->bytes_per_page);
  32         index->geometry = geometry;
  33         index->volume_nonce = volume_nonce;
  34         result = uds_initialize_delta_index(&index->delta_index, 1,
  35                                             geometry->delta_lists_per_chapter,
  36                                             geometry->chapter_mean_delta,
  37                                             geometry->chapter_payload_bits,
  38                                             memory_size, 'm');
  39         if (result != UDS_SUCCESS) {
  40                 vdo_free(index);
  41                 return result;
  42         }
  43
  44         index->memory_size = index->delta_index.memory_size + sizeof(struct open_chapter_index);
  45         *chapter_index = index;
  46         return UDS_SUCCESS;
  47 }
  48
  49 void uds_free_open_chapter_index(struct open_chapter_index *chapter_index)
  50 {
  51         if (chapter_index == NULL)
  52                 return;
  53
  54         uds_uninitialize_delta_index(&chapter_index->delta_index);
  55         vdo_free(chapter_index);
  56 }
  57
  58 /* Re-initialize an open chapter index for a new chapter. */
  59 void uds_empty_open_chapter_index(struct open_chapter_index *chapter_index,
  60                                   u64 virtual_chapter_number)
  61 {
  62         uds_reset_delta_index(&chapter_index->delta_index);
  63         chapter_index->virtual_chapter_number = virtual_chapter_number;
  64 }
  65
  66 static inline bool was_entry_found(const struct delta_index_entry *entry, u32 address)
  67 {
  68         return (!entry->at_end) && (entry->key == address);
  69 }
  70
  71 /* Associate a record name with the record page containing its metadata. */
  72 int uds_put_open_chapter_index_record(struct open_chapter_index *chapter_index,
  73                                       const struct uds_record_name *name,
  74                                       u32 page_number)
  75 {
  76         int result;
  77         struct delta_index_entry entry;
  78         u32 address;
  79         u32 list_number;
  80         const u8 *found_name;
  81         bool found;
  82         const struct index_geometry *geometry = chapter_index->geometry;
  83         u64 chapter_number = chapter_index->virtual_chapter_number;
  84         u32 record_pages = geometry->record_pages_per_chapter;
  85
  86         result = VDO_ASSERT(page_number < record_pages,
  87                             "Page number within chapter (%u) exceeds the maximum value %u",
  88                             page_number, record_pages);
  89         if (result != VDO_SUCCESS)
  90                 return UDS_INVALID_ARGUMENT;
  91
  92         address = uds_hash_to_chapter_delta_address(name, geometry);
  93         list_number = uds_hash_to_chapter_delta_list(name, geometry);
  94         result = uds_get_delta_index_entry(&chapter_index->delta_index, list_number,
  95                                            address, name->name, &entry);
  96         if (result != UDS_SUCCESS)
  97                 return result;
  98
  99         found = was_entry_found(&entry, address);
 100         result = VDO_ASSERT(!(found && entry.is_collision),
 101                             "Chunk appears more than once in chapter %llu",
 102                             (unsigned long long) chapter_number);
 103         if (result != VDO_SUCCESS)
 104                 return UDS_BAD_STATE;
 105
 106         found_name = (found ? name->name : NULL);
 107         return uds_put_delta_index_entry(&entry, address, page_number, found_name);
 108 }
 109
 110 /*
 111  * Pack a section of an open chapter index into a chapter index page. A range of delta lists
 112  * (starting with a specified list index) is copied from the open chapter index into a memory page.
 113  * The number of lists copied onto the page is returned to the caller on success.
 114  *
 115  * @chapter_index: The open chapter index
 116  * @memory: The memory page to use
 117  * @first_list: The first delta list number to be copied
 118  * @last_page: If true, this is the last page of the chapter index and all the remaining lists must
 119  *             be packed onto this page
 120  * @lists_packed: The number of delta lists that were packed onto this page
 121  */
 122 int uds_pack_open_chapter_index_page(struct open_chapter_index *chapter_index,
 123                                      u8 *memory, u32 first_list, bool last_page,
 124                                      u32 *lists_packed)
 125 {
 126         int result;
 127         struct delta_index *delta_index = &chapter_index->delta_index;
 128         struct delta_index_stats stats;
 129         u64 nonce = chapter_index->volume_nonce;
 130         u64 chapter_number = chapter_index->virtual_chapter_number;
 131         const struct index_geometry *geometry = chapter_index->geometry;
 132         u32 list_count = geometry->delta_lists_per_chapter;
 133         unsigned int removals = 0;
 134         struct delta_index_entry entry;
 135         u32 next_list;
 136         s32 list_number;
 137
 138         for (;;) {
 139                 result = uds_pack_delta_index_page(delta_index, nonce, memory,
 140                                                    geometry->bytes_per_page,
 141                                                    chapter_number, first_list,
 142                                                    lists_packed);
 143                 if (result != UDS_SUCCESS)
 144                         return result;
 145
 146                 if ((first_list + *lists_packed) == list_count) {
 147                         /* All lists are packed. */
 148                         break;
 149                 } else if (*lists_packed == 0) {
 150                         /*
 151                          * The next delta list does not fit on a page. This delta list will be
 152                          * removed.
 153                          */
 154                 } else if (last_page) {
 155                         /*
 156                          * This is the last page and there are lists left unpacked, but all of the
 157                          * remaining lists must fit on the page. Find a list that contains entries
 158                          * and remove the entire list. Try the first list that does not fit. If it
 159                          * is empty, we will select the last list that already fits and has any
 160                          * entries.
 161                          */
 162                 } else {
 163                         /* This page is done. */
 164                         break;
 165                 }
 166
 167                 if (removals == 0) {
 168                         uds_get_delta_index_stats(delta_index, &stats);
 169                         vdo_log_warning("The chapter index for chapter %llu contains %llu entries with %llu collisions",
 170                                         (unsigned long long) chapter_number,
 171                                         (unsigned long long) stats.record_count,
 172                                         (unsigned long long) stats.collision_count);
 173                 }
 174
 175                 list_number = *lists_packed;
 176                 do {
 177                         if (list_number < 0)
 178                                 return UDS_OVERFLOW;
 179
 180                         next_list = first_list + list_number--;
 181                         result = uds_start_delta_index_search(delta_index, next_list, 0,
 182                                                               &entry);
 183                         if (result != UDS_SUCCESS)
 184                                 return result;
 185
 186                         result = uds_next_delta_index_entry(&entry);
 187                         if (result != UDS_SUCCESS)
 188                                 return result;
 189                 } while (entry.at_end);
 190
 191                 do {
 192                         result = uds_remove_delta_index_entry(&entry);
 193                         if (result != UDS_SUCCESS)
 194                                 return result;
 195
 196                         removals++;
 197                 } while (!entry.at_end);
 198         }
 199
 200         if (removals > 0) {
 201                 vdo_log_warning("To avoid chapter index page overflow in chapter %llu, %u entries were removed from the chapter index",
 202                                 (unsigned long long) chapter_number, removals);
 203         }
 204
 205         return UDS_SUCCESS;
 206 }
 207
 208 /* Make a new chapter index page, initializing it with the data from a given index_page buffer. */
 209 int uds_initialize_chapter_index_page(struct delta_index_page *index_page,
 210                                       const struct index_geometry *geometry,
 211                                       u8 *page_buffer, u64 volume_nonce)
 212 {
 213         return uds_initialize_delta_index_page(index_page, volume_nonce,
 214                                                geometry->chapter_mean_delta,
 215                                                geometry->chapter_payload_bits,
 216                                                page_buffer, geometry->bytes_per_page);
 217 }
 218
 219 /* Validate a chapter index page read during rebuild. */
 220 int uds_validate_chapter_index_page(const struct delta_index_page *index_page,
 221                                     const struct index_geometry *geometry)
 222 {
 223         int result;
 224         const struct delta_index *delta_index = &index_page->delta_index;
 225         u32 first = index_page->lowest_list_number;
 226         u32 last = index_page->highest_list_number;
 227         u32 list_number;
 228
 229         /* We walk every delta list from start to finish. */
 230         for (list_number = first; list_number <= last; list_number++) {
 231                 struct delta_index_entry entry;
 232
 233                 result = uds_start_delta_index_search(delta_index, list_number - first,
 234                                                       0, &entry);
 235                 if (result != UDS_SUCCESS)
 236                         return result;
 237
 238                 for (;;) {
 239                         result = uds_next_delta_index_entry(&entry);
 240                         if (result != UDS_SUCCESS) {
 241                                 /*
 242                                  * A random bit stream is highly likely to arrive here when we go
 243                                  * past the end of the delta list.
 244                                  */
 245                                 return result;
 246                         }
 247
 248                         if (entry.at_end)
 249                                 break;
 250
 251                         /* Also make sure that the record page field contains a plausible value. */
 252                         if (uds_get_delta_entry_value(&entry) >=
 253                             geometry->record_pages_per_chapter) {
 254                                 /*
 255                                  * Do not log this as an error. It happens in normal operation when
 256                                  * we are doing a rebuild but haven't written the entire volume
 257                                  * once.
 258                                  */
 259                                 return UDS_CORRUPT_DATA;
 260                         }
 261                 }
 262         }
 263         return UDS_SUCCESS;
 264 }
 265
 266 /*
 267  * Search a chapter index page for a record name, returning the record page number that may contain
 268  * the name.
 269  */
 270 int uds_search_chapter_index_page(struct delta_index_page *index_page,
 271                                   const struct index_geometry *geometry,
 272                                   const struct uds_record_name *name,
 273                                   u16 *record_page_ptr)
 274 {
 275         int result;
 276         struct delta_index *delta_index = &index_page->delta_index;
 277         u32 address = uds_hash_to_chapter_delta_address(name, geometry);
 278         u32 delta_list_number = uds_hash_to_chapter_delta_list(name, geometry);
 279         u32 sub_list_number = delta_list_number - index_page->lowest_list_number;
 280         struct delta_index_entry entry;
 281
 282         result = uds_get_delta_index_entry(delta_index, sub_list_number, address,
 283                                            name->name, &entry);
 284         if (result != UDS_SUCCESS)
 285                 return result;
 286
 287         if (was_entry_found(&entry, address))
 288                 *record_page_ptr = uds_get_delta_entry_value(&entry);
 289         else
 290                 *record_page_ptr = NO_CHAPTER_INDEX_ENTRY;
 291
 292         return UDS_SUCCESS;
 293 }