drivers/md/dm-vdo/indexer/geometry.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #include "geometry.h"
   7
   8 #include <linux/compiler.h>
   9 #include <linux/log2.h>
  10
  11 #include "errors.h"
  12 #include "logger.h"
  13 #include "memory-alloc.h"
  14 #include "permassert.h"
  15
  16 #include "delta-index.h"
  17 #include "indexer.h"
  18
  19 /*
  20  * An index volume is divided into a fixed number of fixed-size chapters, each consisting of a
  21  * fixed number of fixed-size pages. The volume layout is defined by two constants and four
  22  * parameters. The constants are that index records are 32 bytes long (16-byte block name plus
  23  * 16-byte metadata) and that open chapter index hash slots are one byte long. The four parameters
  24  * are the number of bytes in a page, the number of record pages in a chapter, the number of
  25  * chapters in a volume, and the number of chapters that are sparse. From these parameters, we can
  26  * derive the rest of the layout and other index properties.
  27  *
  28  * The index volume is sized by its maximum memory footprint. For a dense index, the persistent
  29  * storage is about 10 times the size of the memory footprint. For a sparse index, the persistent
  30  * storage is about 100 times the size of the memory footprint.
  31  *
  32  * For a small index with a memory footprint less than 1GB, there are three possible memory
  33  * configurations: 0.25GB, 0.5GB and 0.75GB. The default geometry for each is 1024 index records
  34  * per 32 KB page, 1024 chapters per volume, and either 64, 128, or 192 record pages per chapter
  35  * (resulting in 6, 13, or 20 index pages per chapter) depending on the memory configuration. For
  36  * the VDO default of a 0.25 GB index, this yields a deduplication window of 256 GB using about 2.5
  37  * GB for the persistent storage and 256 MB of RAM.
  38  *
  39  * For a larger index with a memory footprint that is a multiple of 1 GB, the geometry is 1024
  40  * index records per 32 KB page, 256 record pages per chapter, 26 index pages per chapter, and 1024
  41  * chapters for every GB of memory footprint. For a 1 GB volume, this yields a deduplication window
  42  * of 1 TB using about 9GB of persistent storage and 1 GB of RAM.
  43  *
  44  * The above numbers hold for volumes which have no sparse chapters. A sparse volume has 10 times
  45  * as many chapters as the corresponding non-sparse volume, which provides 10 times the
  46  * deduplication window while using 10 times as much persistent storage as the equivalent
  47  * non-sparse volume with the same memory footprint.
  48  *
  49  * If the volume has been converted from a non-lvm format to an lvm volume, the number of chapters
  50  * per volume will have been reduced by one by eliminating physical chapter 0, and the virtual
  51  * chapter that formerly mapped to physical chapter 0 may be remapped to another physical chapter.
  52  * This remapping is expressed by storing which virtual chapter was remapped, and which physical
  53  * chapter it was moved to.
  54  */
  55
  56 int uds_make_index_geometry(size_t bytes_per_page, u32 record_pages_per_chapter,
  57                             u32 chapters_per_volume, u32 sparse_chapters_per_volume,
  58                             u64 remapped_virtual, u64 remapped_physical,
  59                             struct index_geometry **geometry_ptr)
  60 {
  61         int result;
  62         struct index_geometry *geometry;
  63
  64         result = vdo_allocate(1, struct index_geometry, "geometry", &geometry);
  65         if (result != VDO_SUCCESS)
  66                 return result;
  67
  68         geometry->bytes_per_page = bytes_per_page;
  69         geometry->record_pages_per_chapter = record_pages_per_chapter;
  70         geometry->chapters_per_volume = chapters_per_volume;
  71         geometry->sparse_chapters_per_volume = sparse_chapters_per_volume;
  72         geometry->dense_chapters_per_volume = chapters_per_volume - sparse_chapters_per_volume;
  73         geometry->remapped_virtual = remapped_virtual;
  74         geometry->remapped_physical = remapped_physical;
  75
  76         geometry->records_per_page = bytes_per_page / BYTES_PER_RECORD;
  77         geometry->records_per_chapter = geometry->records_per_page * record_pages_per_chapter;
  78         geometry->records_per_volume = (u64) geometry->records_per_chapter * chapters_per_volume;
  79
  80         geometry->chapter_mean_delta = 1 << DEFAULT_CHAPTER_MEAN_DELTA_BITS;
  81         geometry->chapter_payload_bits = bits_per(record_pages_per_chapter - 1);
  82         /*
  83          * We want 1 delta list for every 64 records in the chapter.
  84          * The "| 077" ensures that the chapter_delta_list_bits computation
  85          * does not underflow.
  86          */
  87         geometry->chapter_delta_list_bits =
  88                 bits_per((geometry->records_per_chapter - 1) | 077) - 6;
  89         geometry->delta_lists_per_chapter = 1 << geometry->chapter_delta_list_bits;
  90         /* We need enough address bits to achieve the desired mean delta. */
  91         geometry->chapter_address_bits =
  92                 (DEFAULT_CHAPTER_MEAN_DELTA_BITS -
  93                  geometry->chapter_delta_list_bits +
  94                  bits_per(geometry->records_per_chapter - 1));
  95         geometry->index_pages_per_chapter =
  96                 uds_get_delta_index_page_count(geometry->records_per_chapter,
  97                                                geometry->delta_lists_per_chapter,
  98                                                geometry->chapter_mean_delta,
  99                                                geometry->chapter_payload_bits,
 100                                                bytes_per_page);
 101
 102         geometry->pages_per_chapter = geometry->index_pages_per_chapter + record_pages_per_chapter;
 103         geometry->pages_per_volume = geometry->pages_per_chapter * chapters_per_volume;
 104         geometry->bytes_per_volume =
 105                 bytes_per_page * (geometry->pages_per_volume + HEADER_PAGES_PER_VOLUME);
 106
 107         *geometry_ptr = geometry;
 108         return UDS_SUCCESS;
 109 }
 110
 111 int uds_copy_index_geometry(struct index_geometry *source,
 112                             struct index_geometry **geometry_ptr)
 113 {
 114         return uds_make_index_geometry(source->bytes_per_page,
 115                                        source->record_pages_per_chapter,
 116                                        source->chapters_per_volume,
 117                                        source->sparse_chapters_per_volume,
 118                                        source->remapped_virtual, source->remapped_physical,
 119                                        geometry_ptr);
 120 }
 121
 122 void uds_free_index_geometry(struct index_geometry *geometry)
 123 {
 124         vdo_free(geometry);
 125 }
 126
 127 u32 __must_check uds_map_to_physical_chapter(const struct index_geometry *geometry,
 128                                              u64 virtual_chapter)
 129 {
 130         u64 delta;
 131
 132         if (!uds_is_reduced_index_geometry(geometry))
 133                 return virtual_chapter % geometry->chapters_per_volume;
 134
 135         if (likely(virtual_chapter > geometry->remapped_virtual)) {
 136                 delta = virtual_chapter - geometry->remapped_virtual;
 137                 if (likely(delta > geometry->remapped_physical))
 138                         return delta % geometry->chapters_per_volume;
 139                 else
 140                         return delta - 1;
 141         }
 142
 143         if (virtual_chapter == geometry->remapped_virtual)
 144                 return geometry->remapped_physical;
 145
 146         delta = geometry->remapped_virtual - virtual_chapter;
 147         if (delta < geometry->chapters_per_volume)
 148                 return geometry->chapters_per_volume - delta;
 149
 150         /* This chapter is so old the answer doesn't matter. */
 151         return 0;
 152 }
 153
 154 /* Check whether any sparse chapters are in use. */
 155 bool uds_has_sparse_chapters(const struct index_geometry *geometry,
 156                              u64 oldest_virtual_chapter, u64 newest_virtual_chapter)
 157 {
 158         return uds_is_sparse_index_geometry(geometry) &&
 159                 ((newest_virtual_chapter - oldest_virtual_chapter + 1) >
 160                  geometry->dense_chapters_per_volume);
 161 }
 162
 163 bool uds_is_chapter_sparse(const struct index_geometry *geometry,
 164                            u64 oldest_virtual_chapter, u64 newest_virtual_chapter,
 165                            u64 virtual_chapter_number)
 166 {
 167         return uds_has_sparse_chapters(geometry, oldest_virtual_chapter,
 168                                        newest_virtual_chapter) &&
 169                 ((virtual_chapter_number + geometry->dense_chapters_per_volume) <=
 170                  newest_virtual_chapter);
 171 }
 172
 173 /* Calculate how many chapters to expire after opening the newest chapter. */
 174 u32 uds_chapters_to_expire(const struct index_geometry *geometry, u64 newest_chapter)
 175 {
 176         /* If the index isn't full yet, don't expire anything. */
 177         if (newest_chapter < geometry->chapters_per_volume)
 178                 return 0;
 179
 180         /* If a chapter is out of order... */
 181         if (geometry->remapped_physical > 0) {
 182                 u64 oldest_chapter = newest_chapter - geometry->chapters_per_volume;
 183
 184                 /*
 185                  * ... expire an extra chapter when expiring the moved chapter to free physical
 186                  * space for the new chapter ...
 187                  */
 188                 if (oldest_chapter == geometry->remapped_virtual)
 189                         return 2;
 190
 191                 /*
 192                  * ... but don't expire anything when the new chapter will use the physical chapter
 193                  * freed by expiring the moved chapter.
 194                  */
 195                 if (oldest_chapter == (geometry->remapped_virtual + geometry->remapped_physical))
 196                         return 0;
 197         }
 198
 199         /* Normally, just expire one. */
 200         return 1;
 201 }