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 struct index_geometry uds_init_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 { 60 struct index_geometry geometry = { 61 .bytes_per_page = bytes_per_page, 62 .record_pages_per_chapter = record_pages_per_chapter, 63 .chapters_per_volume = chapters_per_volume, 64 .sparse_chapters_per_volume = sparse_chapters_per_volume, 65 .dense_chapters_per_volume = chapters_per_volume - sparse_chapters_per_volume, 66 .remapped_virtual = remapped_virtual, 67 .remapped_physical = remapped_physical, 68 }; 69 70 geometry.records_per_page = bytes_per_page / BYTES_PER_RECORD; 71 geometry.records_per_chapter = geometry.records_per_page * record_pages_per_chapter; 72 geometry.records_per_volume = (u64) geometry.records_per_chapter * chapters_per_volume; 73 74 geometry.chapter_mean_delta = 1 << DEFAULT_CHAPTER_MEAN_DELTA_BITS; 75 geometry.chapter_payload_bits = bits_per(record_pages_per_chapter - 1); 76 /* 77 * We want 1 delta list for every 64 records in the chapter. 78 * The "| 077" ensures that the chapter_delta_list_bits computation 79 * does not underflow. 80 */ 81 geometry.chapter_delta_list_bits = bits_per((geometry.records_per_chapter - 1) | 077) - 6; 82 geometry.delta_lists_per_chapter = 1 << geometry.chapter_delta_list_bits; 83 /* We need enough address bits to achieve the desired mean delta. */ 84 geometry.chapter_address_bits = 85 (DEFAULT_CHAPTER_MEAN_DELTA_BITS - 86 geometry.chapter_delta_list_bits + 87 bits_per(geometry.records_per_chapter - 1)); 88 geometry.index_pages_per_chapter = 89 uds_get_delta_index_page_count(geometry.records_per_chapter, 90 geometry.delta_lists_per_chapter, 91 geometry.chapter_mean_delta, 92 geometry.chapter_payload_bits, 93 bytes_per_page); 94 95 geometry.pages_per_chapter = geometry.index_pages_per_chapter + record_pages_per_chapter; 96 geometry.pages_per_volume = geometry.pages_per_chapter * chapters_per_volume; 97 geometry.bytes_per_volume = 98 bytes_per_page * (geometry.pages_per_volume + HEADER_PAGES_PER_VOLUME); 99 100 return geometry; 101 } 102 103 u32 __must_check uds_map_to_physical_chapter(const struct index_geometry *geometry, 104 u64 virtual_chapter) 105 { 106 u64 delta; 107 108 if (!uds_is_reduced_index_geometry(geometry)) 109 return virtual_chapter % geometry->chapters_per_volume; 110 111 if (likely(virtual_chapter > geometry->remapped_virtual)) { 112 delta = virtual_chapter - geometry->remapped_virtual; 113 if (likely(delta > geometry->remapped_physical)) 114 return delta % geometry->chapters_per_volume; 115 else 116 return delta - 1; 117 } 118 119 if (virtual_chapter == geometry->remapped_virtual) 120 return geometry->remapped_physical; 121 122 delta = geometry->remapped_virtual - virtual_chapter; 123 if (delta < geometry->chapters_per_volume) 124 return geometry->chapters_per_volume - delta; 125 126 /* This chapter is so old the answer doesn't matter. */ 127 return 0; 128 } 129 130 /* Check whether any sparse chapters are in use. */ 131 bool uds_has_sparse_chapters(const struct index_geometry *geometry, 132 u64 oldest_virtual_chapter, u64 newest_virtual_chapter) 133 { 134 return uds_is_sparse_index_geometry(geometry) && 135 ((newest_virtual_chapter - oldest_virtual_chapter + 1) > 136 geometry->dense_chapters_per_volume); 137 } 138 139 bool uds_is_chapter_sparse(const struct index_geometry *geometry, 140 u64 oldest_virtual_chapter, u64 newest_virtual_chapter, 141 u64 virtual_chapter_number) 142 { 143 return uds_has_sparse_chapters(geometry, oldest_virtual_chapter, 144 newest_virtual_chapter) && 145 ((virtual_chapter_number + geometry->dense_chapters_per_volume) <= 146 newest_virtual_chapter); 147 } 148 149 /* Calculate how many chapters to expire after opening the newest chapter. */ 150 u32 uds_chapters_to_expire(const struct index_geometry *geometry, u64 newest_chapter) 151 { 152 /* If the index isn't full yet, don't expire anything. */ 153 if (newest_chapter < geometry->chapters_per_volume) 154 return 0; 155 156 /* If a chapter is out of order... */ 157 if (geometry->remapped_physical > 0) { 158 u64 oldest_chapter = newest_chapter - geometry->chapters_per_volume; 159 160 /* 161 * ... expire an extra chapter when expiring the moved chapter to free physical 162 * space for the new chapter ... 163 */ 164 if (oldest_chapter == geometry->remapped_virtual) 165 return 2; 166 167 /* 168 * ... but don't expire anything when the new chapter will use the physical chapter 169 * freed by expiring the moved chapter. 170 */ 171 if (oldest_chapter == (geometry->remapped_virtual + geometry->remapped_physical)) 172 return 0; 173 } 174 175 /* Normally, just expire one. */ 176 return 1; 177 } 178