// SPDX-License-Identifier: GPL-2.0-only /* * Copyright 2023 Red Hat */ #include "volume.h" #include <linux/atomic.h> #include <linux/dm-bufio.h> #include <linux/err.h> #include "errors.h" #include "logger.h" #include "memory-alloc.h" #include "permassert.h" #include "string-utils.h" #include "thread-utils.h" #include "chapter-index.h" #include "config.h" #include "geometry.h" #include "hash-utils.h" #include "index.h" #include "sparse-cache.h" /* * The first block of the volume layout is reserved for the volume header, which is no longer used. * The remainder of the volume is divided into chapters consisting of several pages of records, and * several pages of static index to use to find those records. The index pages are recorded first, * followed by the record pages. The chapters are written in order as they are filled, so the * volume storage acts as a circular log of the most recent chapters, with each new chapter * overwriting the oldest saved one. * * When a new chapter is filled and closed, the records from that chapter are sorted and * interleaved in approximate temporal order, and assigned to record pages. Then a static delta * index is generated to store which record page contains each record. The in-memory index page map * is also updated to indicate which delta lists fall on each chapter index page. This means that * when a record is read, the volume only has to load a single index page and a single record page, * rather than search the entire chapter. These index and record pages are written to storage, and * the index pages are transferred to the page cache under the theory that the most recently * written chapter is likely to be accessed again soon. * * When reading a record, the volume index will indicate which chapter should contain it. The * volume uses the index page map to determine which chapter index page needs to be loaded, and * then reads the relevant record page number from the chapter index. Both index and record pages * are stored in a page cache when read for the common case that subsequent records need the same * pages. The page cache evicts the least recently accessed entries when caching new pages. In * addition, the volume uses dm-bufio to manage access to the storage, which may allow for * additional caching depending on available system resources. * * Record requests are handled from cached pages when possible. If a page needs to be read, it is * placed on a queue along with the request that wants to read it. Any requests for the same page * that arrive while the read is pending are added to the queue entry. A separate reader thread * handles the queued reads, adding the page to the cache and updating any requests queued with it * so they can continue processing. This allows the index zone threads to continue processing new * requests rather than wait for the storage reads. * * When an index rebuild is necessary, the volume reads each stored chapter to determine which * range of chapters contain valid records, so that those records can be used to reconstruct the * in-memory volume index. */ /* The maximum allowable number of contiguous bad chapters */ #define MAX_BAD_CHAPTERS … #define VOLUME_CACHE_MAX_ENTRIES … #define VOLUME_CACHE_QUEUED_FLAG … #define VOLUME_CACHE_MAX_QUEUED_READS … static const u64 BAD_CHAPTER = …; /* * The invalidate counter is two 32 bits fields stored together atomically. The low order 32 bits * are the physical page number of the cached page being read. The high order 32 bits are a * sequence number. This value is written when the zone that owns it begins or completes a cache * search. Any other thread will only read the counter in wait_for_pending_searches() while waiting * to update the cache contents. */ invalidate_counter; static inline u32 map_to_page_number(struct index_geometry *geometry, u32 physical_page) { … } static inline u32 map_to_chapter_number(struct index_geometry *geometry, u32 physical_page) { … } static inline bool is_record_page(struct index_geometry *geometry, u32 physical_page) { … } static u32 map_to_physical_page(const struct index_geometry *geometry, u32 chapter, u32 page) { … } static inline union invalidate_counter get_invalidate_counter(struct page_cache *cache, unsigned int zone_number) { … } static inline void set_invalidate_counter(struct page_cache *cache, unsigned int zone_number, union invalidate_counter invalidate_counter) { … } static inline bool search_pending(union invalidate_counter invalidate_counter) { … } /* Lock the cache for a zone in order to search for a page. */ static void begin_pending_search(struct page_cache *cache, u32 physical_page, unsigned int zone_number) { … } /* Unlock the cache for a zone by clearing its invalidate counter. */ static void end_pending_search(struct page_cache *cache, unsigned int zone_number) { … } static void wait_for_pending_searches(struct page_cache *cache, u32 physical_page) { … } static void release_page_buffer(struct cached_page *page) { … } static void clear_cache_page(struct page_cache *cache, struct cached_page *page) { … } static void make_page_most_recent(struct page_cache *cache, struct cached_page *page) { … } /* Select a page to remove from the cache to make space for a new entry. */ static struct cached_page *select_victim_in_cache(struct page_cache *cache) { … } /* Make a newly filled cache entry available to other threads. */ static int put_page_in_cache(struct page_cache *cache, u32 physical_page, struct cached_page *page) { … } static void cancel_page_in_cache(struct page_cache *cache, u32 physical_page, struct cached_page *page) { … } static inline u16 next_queue_position(u16 position) { … } static inline void advance_queue_position(u16 *position) { … } static inline bool read_queue_is_full(struct page_cache *cache) { … } static bool enqueue_read(struct page_cache *cache, struct uds_request *request, u32 physical_page) { … } static void enqueue_page_read(struct volume *volume, struct uds_request *request, u32 physical_page) { … } /* * Reserve the next read queue entry for processing, but do not actually remove it from the queue. * Must be followed by release_queued_requests(). */ static struct queued_read *reserve_read_queue_entry(struct page_cache *cache) { … } static inline struct queued_read *wait_to_reserve_read_queue_entry(struct volume *volume) { … } static int init_chapter_index_page(const struct volume *volume, u8 *index_page, u32 chapter, u32 index_page_number, struct delta_index_page *chapter_index_page) { … } static int initialize_index_page(const struct volume *volume, u32 physical_page, struct cached_page *page) { … } static bool search_record_page(const u8 record_page[], const struct uds_record_name *name, const struct index_geometry *geometry, struct uds_record_data *metadata) { … } /* * If we've read in a record page, we're going to do an immediate search, to speed up processing by * avoiding get_record_from_zone(), and to ensure that requests make progress even when queued. If * we've read in an index page, we save the record page number so we don't have to resolve the * index page again. We use the location, virtual_chapter, and old_metadata fields in the request * to allow the index code to know where to begin processing the request again. */ static int search_page(struct cached_page *page, const struct volume *volume, struct uds_request *request, u32 physical_page) { … } static int process_entry(struct volume *volume, struct queued_read *entry) { … } static void release_queued_requests(struct volume *volume, struct queued_read *entry, int result) { … } static void read_thread_function(void *arg) { … } static void get_page_and_index(struct page_cache *cache, u32 physical_page, int *queue_index, struct cached_page **page_ptr) { … } static void get_page_from_cache(struct page_cache *cache, u32 physical_page, struct cached_page **page) { … } static int read_page_locked(struct volume *volume, u32 physical_page, struct cached_page **page_ptr) { … } /* Retrieve a page from the cache while holding the read threads mutex. */ static int get_volume_page_locked(struct volume *volume, u32 physical_page, struct cached_page **page_ptr) { … } /* Retrieve a page from the cache while holding a search_pending lock. */ static int get_volume_page_protected(struct volume *volume, struct uds_request *request, u32 physical_page, struct cached_page **page_ptr) { … } static int get_volume_page(struct volume *volume, u32 chapter, u32 page_number, struct cached_page **page_ptr) { … } int uds_get_volume_record_page(struct volume *volume, u32 chapter, u32 page_number, u8 **data_ptr) { … } int uds_get_volume_index_page(struct volume *volume, u32 chapter, u32 page_number, struct delta_index_page **index_page_ptr) { … } /* * Find the record page associated with a name in a given index page. This will return UDS_QUEUED * if the page in question must be read from storage. */ static int search_cached_index_page(struct volume *volume, struct uds_request *request, u32 chapter, u32 index_page_number, u16 *record_page_number) { … } /* * Find the metadata associated with a name in a given record page. This will return UDS_QUEUED if * the page in question must be read from storage. */ int uds_search_cached_record_page(struct volume *volume, struct uds_request *request, u32 chapter, u16 record_page_number, bool *found) { … } void uds_prefetch_volume_chapter(const struct volume *volume, u32 chapter) { … } int uds_read_chapter_index_from_volume(const struct volume *volume, u64 virtual_chapter, struct dm_buffer *volume_buffers[], struct delta_index_page index_pages[]) { … } int uds_search_volume_page_cache(struct volume *volume, struct uds_request *request, bool *found) { … } int uds_search_volume_page_cache_for_rebuild(struct volume *volume, const struct uds_record_name *name, u64 virtual_chapter, bool *found) { … } static void invalidate_page(struct page_cache *cache, u32 physical_page) { … } void uds_forget_chapter(struct volume *volume, u64 virtual_chapter) { … } /* * Donate an index pages from a newly written chapter to the page cache since it is likely to be * used again soon. The caller must already hold the reader thread mutex. */ static int donate_index_page_locked(struct volume *volume, u32 physical_chapter, u32 index_page_number, struct dm_buffer *page_buffer) { … } static int write_index_pages(struct volume *volume, u32 physical_chapter_number, struct open_chapter_index *chapter_index) { … } static u32 encode_tree(u8 record_page[], const struct uds_volume_record *sorted_pointers[], u32 next_record, u32 node, u32 node_count) { … } static int encode_record_page(const struct volume *volume, const struct uds_volume_record records[], u8 record_page[]) { … } static int write_record_pages(struct volume *volume, u32 physical_chapter_number, const struct uds_volume_record *records) { … } int uds_write_chapter(struct volume *volume, struct open_chapter_index *chapter_index, const struct uds_volume_record *records) { … } static void probe_chapter(struct volume *volume, u32 chapter_number, u64 *virtual_chapter_number) { … } /* Find the last valid physical chapter in the volume. */ static void find_real_end_of_volume(struct volume *volume, u32 limit, u32 *limit_ptr) { … } static int find_chapter_limits(struct volume *volume, u32 chapter_limit, u64 *lowest_vcn, u64 *highest_vcn) { … } /* * Find the highest and lowest contiguous chapters present in the volume and determine their * virtual chapter numbers. This is used by rebuild. */ int uds_find_volume_chapter_boundaries(struct volume *volume, u64 *lowest_vcn, u64 *highest_vcn, bool *is_empty) { … } int __must_check uds_replace_volume_storage(struct volume *volume, struct index_layout *layout, struct block_device *bdev) { … } static int __must_check initialize_page_cache(struct page_cache *cache, const struct index_geometry *geometry, u32 chapters_in_cache, unsigned int zone_count) { … } int uds_make_volume(const struct uds_configuration *config, struct index_layout *layout, struct volume **new_volume) { … } static void uninitialize_page_cache(struct page_cache *cache) { … } void uds_free_volume(struct volume *volume) { … }
Codebase Browser
linux