// SPDX-License-Identifier: GPL-2.0-only /* * Copyright 2023 Red Hat */ #include "index.h" #include "logger.h" #include "memory-alloc.h" #include "funnel-requestqueue.h" #include "hash-utils.h" #include "sparse-cache.h" static const u64 NO_LAST_SAVE = …; /* * When searching for deduplication records, the index first searches the volume index, and then * searches the chapter index for the relevant chapter. If the chapter has been fully committed to * storage, the chapter pages are loaded into the page cache. If the chapter has not yet been * committed (either the open chapter or a recently closed one), the index searches the in-memory * representation of the chapter. Finally, if the volume index does not find a record and the index * is sparse, the index will search the sparse cache. * * The index send two kinds of messages to coordinate between zones: chapter close messages for the * chapter writer, and sparse cache barrier messages for the sparse cache. * * The chapter writer is responsible for committing chapters of records to storage. Since zones can * get different numbers of records, some zones may fall behind others. Each time a zone fills up * its available space in a chapter, it informs the chapter writer that the chapter is complete, * and also informs all other zones that it has closed the chapter. Each other zone will then close * the chapter immediately, regardless of how full it is, in order to minimize skew between zones. * Once every zone has closed the chapter, the chapter writer will commit that chapter to storage. * * The last zone to close the chapter also removes the oldest chapter from the volume index. * Although that chapter is invalid for zones that have moved on, the existence of the open chapter * means that those zones will never ask the volume index about it. No zone is allowed to get more * than one chapter ahead of any other. If a zone is so far ahead that it tries to close another * chapter before the previous one has been closed by all zones, it is forced to wait. * * The sparse cache relies on having the same set of chapter indexes available to all zones. When a * request wants to add a chapter to the sparse cache, it sends a barrier message to each zone * during the triage stage that acts as a rendezvous. Once every zone has reached the barrier and * paused its operations, the cache membership is changed and each zone is then informed that it * can proceed. More details can be found in the sparse cache documentation. * * If a sparse cache has only one zone, it will not create a triage queue, but it still needs the * barrier message to change the sparse cache membership, so the index simulates the message by * invoking the handler directly. */ struct chapter_writer { … }; static bool is_zone_chapter_sparse(const struct index_zone *zone, u64 virtual_chapter) { … } static int launch_zone_message(struct uds_zone_message message, unsigned int zone, struct uds_index *index) { … } static void enqueue_barrier_messages(struct uds_index *index, u64 virtual_chapter) { … } /* * Determine whether this request should trigger a sparse cache barrier message to change the * membership of the sparse cache. If a change in membership is desired, the function returns the * chapter number to add. */ static u64 triage_index_request(struct uds_index *index, struct uds_request *request) { … } /* * Simulate a message to change the sparse cache membership for a single-zone sparse index. This * allows us to forgo the complicated locking required by a multi-zone sparse index. Any other kind * of index does nothing here. */ static int simulate_index_zone_barrier_message(struct index_zone *zone, struct uds_request *request) { … } /* This is the request processing function for the triage queue. */ static void triage_request(struct uds_request *request) { … } static int finish_previous_chapter(struct uds_index *index, u64 current_chapter_number) { … } static int swap_open_chapter(struct index_zone *zone) { … } /* * Inform the chapter writer that this zone is done with this chapter. The chapter won't start * writing until all zones have closed it. */ static unsigned int start_closing_chapter(struct uds_index *index, unsigned int zone_number, struct open_chapter_zone *chapter) { … } static int announce_chapter_closed(struct index_zone *zone, u64 closed_chapter) { … } static int open_next_chapter(struct index_zone *zone) { … } static int handle_chapter_closed(struct index_zone *zone, u64 virtual_chapter) { … } static int dispatch_index_zone_control_request(struct uds_request *request) { … } static void set_request_location(struct uds_request *request, enum uds_index_region new_location) { … } static void set_chapter_location(struct uds_request *request, const struct index_zone *zone, u64 virtual_chapter) { … } static int search_sparse_cache_in_zone(struct index_zone *zone, struct uds_request *request, u64 virtual_chapter, bool *found) { … } static int get_record_from_zone(struct index_zone *zone, struct uds_request *request, bool *found) { … } static int put_record_in_zone(struct index_zone *zone, struct uds_request *request, const struct uds_record_data *metadata) { … } static int search_index_zone(struct index_zone *zone, struct uds_request *request) { … } static int remove_from_index_zone(struct index_zone *zone, struct uds_request *request) { … } static int dispatch_index_request(struct uds_index *index, struct uds_request *request) { … } /* This is the request processing function invoked by each zone's thread. */ static void execute_zone_request(struct uds_request *request) { … } static int initialize_index_queues(struct uds_index *index, const struct index_geometry *geometry) { … } /* This is the driver function for the chapter writer thread. */ static void close_chapters(void *arg) { … } static void stop_chapter_writer(struct chapter_writer *writer) { … } static void free_chapter_writer(struct chapter_writer *writer) { … } static int make_chapter_writer(struct uds_index *index, struct chapter_writer **writer_ptr) { … } static int load_index(struct uds_index *index) { … } static int rebuild_index_page_map(struct uds_index *index, u64 vcn) { … } static int replay_record(struct uds_index *index, const struct uds_record_name *name, u64 virtual_chapter, bool will_be_sparse_chapter) { … } static bool check_for_suspend(struct uds_index *index) { … } static int replay_chapter(struct uds_index *index, u64 virtual, bool sparse) { … } static int replay_volume(struct uds_index *index) { … } static int rebuild_index(struct uds_index *index) { … } static void free_index_zone(struct index_zone *zone) { … } static int make_index_zone(struct uds_index *index, unsigned int zone_number) { … } int uds_make_index(struct uds_configuration *config, enum uds_open_index_type open_type, struct index_load_context *load_context, index_callback_fn callback, struct uds_index **new_index) { … } void uds_free_index(struct uds_index *index) { … } /* Wait for the chapter writer to complete any outstanding writes. */ void uds_wait_for_idle_index(struct uds_index *index) { … } /* This function assumes that all requests have been drained. */ int uds_save_index(struct uds_index *index) { … } int uds_replace_index_storage(struct uds_index *index, struct block_device *bdev) { … } /* Accessing statistics should be safe from any thread. */ void uds_get_index_stats(struct uds_index *index, struct uds_index_stats *counters) { … } void uds_enqueue_request(struct uds_request *request, enum request_stage stage) { … }
Codebase Browser
linux