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

   1 /* SPDX-License-Identifier: GPL-2.0-only */
   2 /*
   3  * Copyright 2023 Red Hat
   4  */
   5
   6 #ifndef UDS_INDEX_GEOMETRY_H
   7 #define UDS_INDEX_GEOMETRY_H
   8
   9 #include "indexer.h"
  10
  11 /*
  12  * The index_geometry records parameters that define the layout of a UDS index volume, and the size and
  13  * shape of various index structures. It is created when the index is created, and is referenced by
  14  * many index sub-components.
  15  */
  16
  17 struct index_geometry {
  18         /* Size of a chapter page, in bytes */
  19         size_t bytes_per_page;
  20         /* Number of record pages in a chapter */
  21         u32 record_pages_per_chapter;
  22         /* Total number of chapters in a volume */
  23         u32 chapters_per_volume;
  24         /* Number of sparsely-indexed chapters in a volume */
  25         u32 sparse_chapters_per_volume;
  26         /* Number of bits used to determine delta list numbers */
  27         u8 chapter_delta_list_bits;
  28         /* Virtual chapter remapped from physical chapter 0 */
  29         u64 remapped_virtual;
  30         /* New physical chapter where the remapped chapter can be found */
  31         u64 remapped_physical;
  32
  33         /*
  34          * The following properties are derived from the ones above, but they are computed and
  35          * recorded as fields for convenience.
  36          */
  37         /* Total number of pages in a volume, excluding the header */
  38         u32 pages_per_volume;
  39         /* Total number of bytes in a volume, including the header */
  40         size_t bytes_per_volume;
  41         /* Number of pages in a chapter */
  42         u32 pages_per_chapter;
  43         /* Number of index pages in a chapter index */
  44         u32 index_pages_per_chapter;
  45         /* Number of records that fit on a page */
  46         u32 records_per_page;
  47         /* Number of records that fit in a chapter */
  48         u32 records_per_chapter;
  49         /* Number of records that fit in a volume */
  50         u64 records_per_volume;
  51         /* Number of delta lists per chapter index */
  52         u32 delta_lists_per_chapter;
  53         /* Mean delta for chapter indexes */
  54         u32 chapter_mean_delta;
  55         /* Number of bits needed for record page numbers */
  56         u8 chapter_payload_bits;
  57         /* Number of bits used to compute addresses for chapter delta lists */
  58         u8 chapter_address_bits;
  59         /* Number of densely-indexed chapters in a volume */
  60         u32 dense_chapters_per_volume;
  61 };
  62
  63 enum {
  64         /* The number of bytes in a record (name + metadata) */
  65         BYTES_PER_RECORD = (UDS_RECORD_NAME_SIZE + UDS_RECORD_DATA_SIZE),
  66
  67         /* The default length of a page in a chapter, in bytes */
  68         DEFAULT_BYTES_PER_PAGE = 1024 * BYTES_PER_RECORD,
  69
  70         /* The default maximum number of records per page */
  71         DEFAULT_RECORDS_PER_PAGE = DEFAULT_BYTES_PER_PAGE / BYTES_PER_RECORD,
  72
  73         /* The default number of record pages in a chapter */
  74         DEFAULT_RECORD_PAGES_PER_CHAPTER = 256,
  75
  76         /* The default number of record pages in a chapter for a small index */
  77         SMALL_RECORD_PAGES_PER_CHAPTER = 64,
  78
  79         /* The default number of chapters in a volume */
  80         DEFAULT_CHAPTERS_PER_VOLUME = 1024,
  81
  82         /* The default number of sparsely-indexed chapters in a volume */
  83         DEFAULT_SPARSE_CHAPTERS_PER_VOLUME = 0,
  84
  85         /* The log2 of the default mean delta */
  86         DEFAULT_CHAPTER_MEAN_DELTA_BITS = 16,
  87
  88         /* The log2 of the number of delta lists in a large chapter */
  89         DEFAULT_CHAPTER_DELTA_LIST_BITS = 12,
  90
  91         /* The log2 of the number of delta lists in a small chapter */
  92         SMALL_CHAPTER_DELTA_LIST_BITS = 10,
  93
  94         /* The number of header pages per volume */
  95         HEADER_PAGES_PER_VOLUME = 1,
  96 };
  97
  98 int __must_check uds_make_index_geometry(size_t bytes_per_page, u32 record_pages_per_chapter,
  99                                          u32 chapters_per_volume,
 100                                          u32 sparse_chapters_per_volume, u64 remapped_virtual,
 101                                          u64 remapped_physical,
 102                                          struct index_geometry **geometry_ptr);
 103
 104 int __must_check uds_copy_index_geometry(struct index_geometry *source,
 105                                          struct index_geometry **geometry_ptr);
 106
 107 void uds_free_index_geometry(struct index_geometry *geometry);
 108
 109 u32 __must_check uds_map_to_physical_chapter(const struct index_geometry *geometry,
 110                                              u64 virtual_chapter);
 111
 112 /*
 113  * Check whether this geometry is reduced by a chapter. This will only be true if the volume was
 114  * converted from a non-lvm volume to an lvm volume.
 115  */
 116 static inline bool __must_check
 117 uds_is_reduced_index_geometry(const struct index_geometry *geometry)
 118 {
 119         return !!(geometry->chapters_per_volume & 1);
 120 }
 121
 122 static inline bool __must_check
 123 uds_is_sparse_index_geometry(const struct index_geometry *geometry)
 124 {
 125         return geometry->sparse_chapters_per_volume > 0;
 126 }
 127
 128 bool __must_check uds_has_sparse_chapters(const struct index_geometry *geometry,
 129                                           u64 oldest_virtual_chapter,
 130                                           u64 newest_virtual_chapter);
 131
 132 bool __must_check uds_is_chapter_sparse(const struct index_geometry *geometry,
 133                                         u64 oldest_virtual_chapter,
 134                                         u64 newest_virtual_chapter,
 135                                         u64 virtual_chapter_number);
 136
 137 u32 __must_check uds_chapters_to_expire(const struct index_geometry *geometry,
 138                                         u64 newest_chapter);
 139
 140 #endif /* UDS_INDEX_GEOMETRY_H */