202 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2/*3 * Copyright 2023 Red Hat4 */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 a21 * fixed number of fixed-size pages. The volume layout is defined by two constants and four22 * parameters. The constants are that index records are 32 bytes long (16-byte block name plus23 * 16-byte metadata) and that open chapter index hash slots are one byte long. The four parameters24 * are the number of bytes in a page, the number of record pages in a chapter, the number of25 * chapters in a volume, and the number of chapters that are sparse. From these parameters, we can26 * 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 persistent29 * storage is about 10 times the size of the memory footprint. For a sparse index, the persistent30 * 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 memory33 * configurations: 0.25GB, 0.5GB and 0.75GB. The default geometry for each is 1024 index records34 * per 32 KB page, 1024 chapters per volume, and either 64, 128, or 192 record pages per chapter35 * (resulting in 6, 13, or 20 index pages per chapter) depending on the memory configuration. For36 * the VDO default of a 0.25 GB index, this yields a deduplication window of 256 GB using about 2.537 * 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 102440 * index records per 32 KB page, 256 record pages per chapter, 26 index pages per chapter, and 102441 * chapters for every GB of memory footprint. For a 1 GB volume, this yields a deduplication window42 * 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 times45 * as many chapters as the corresponding non-sparse volume, which provides 10 times the46 * deduplication window while using 10 times as much persistent storage as the equivalent47 * 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 chapters50 * per volume will have been reduced by one by eliminating physical chapter 0, and the virtual51 * 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 physical53 * chapter it was moved to.54 */55 56int 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 computation85 * 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 111int 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 122void uds_free_index_geometry(struct index_geometry *geometry)123{124 vdo_free(geometry);125}126 127u32 __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 else140 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. */155bool 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 163bool 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. */174u32 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 physical186 * 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 chapter193 * 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}202