From 8e6333af19830efdd5adbc994f256fcd5f31e7e7 Mon Sep 17 00:00:00 2001 From: Mike Snitzer Date: Fri, 9 Feb 2024 12:16:13 -0600 Subject: dm vdo indexer: rename uds.h to indexer.h Also remove unnecessary include from funnel-queue.c. Signed-off-by: Mike Snitzer Signed-off-by: Matthew Sakai --- drivers/md/dm-vdo/chapter-index.c | 2 +- drivers/md/dm-vdo/config.h | 2 +- drivers/md/dm-vdo/data-vio.h | 2 +- drivers/md/dm-vdo/dedupe.c | 2 +- drivers/md/dm-vdo/dedupe.h | 2 +- drivers/md/dm-vdo/delta-index.c | 2 +- drivers/md/dm-vdo/encodings.h | 2 +- drivers/md/dm-vdo/funnel-queue.c | 1 - drivers/md/dm-vdo/funnel-requestqueue.h | 2 +- drivers/md/dm-vdo/geometry.c | 2 +- drivers/md/dm-vdo/geometry.h | 2 +- drivers/md/dm-vdo/hash-utils.h | 2 +- drivers/md/dm-vdo/index-layout.h | 2 +- drivers/md/dm-vdo/index-page-map.c | 2 +- drivers/md/dm-vdo/index-session.h | 2 +- drivers/md/dm-vdo/indexer.h | 329 ++++++++++++++++++++++++++++++++ drivers/md/dm-vdo/sparse-cache.h | 2 +- drivers/md/dm-vdo/uds-sysfs.c | 2 +- drivers/md/dm-vdo/uds.h | 329 -------------------------------- drivers/md/dm-vdo/vdo.h | 2 +- drivers/md/dm-vdo/volume-index.c | 2 +- drivers/md/dm-vdo/volume-index.h | 2 +- drivers/md/dm-vdo/volume.h | 2 +- 23 files changed, 349 insertions(+), 350 deletions(-) create mode 100644 drivers/md/dm-vdo/indexer.h delete mode 100644 drivers/md/dm-vdo/uds.h diff --git a/drivers/md/dm-vdo/chapter-index.c b/drivers/md/dm-vdo/chapter-index.c index 363991d56218..9b9185c2c237 100644 --- a/drivers/md/dm-vdo/chapter-index.c +++ b/drivers/md/dm-vdo/chapter-index.c @@ -7,10 +7,10 @@ #include "errors.h" #include "hash-utils.h" +#include "indexer.h" #include "logger.h" #include "memory-alloc.h" #include "permassert.h" -#include "uds.h" int uds_make_open_chapter_index(struct open_chapter_index **chapter_index, const struct index_geometry *geometry, u64 volume_nonce) diff --git a/drivers/md/dm-vdo/config.h b/drivers/md/dm-vdo/config.h index 7d19863800d6..08507dc2f7a1 100644 --- a/drivers/md/dm-vdo/config.h +++ b/drivers/md/dm-vdo/config.h @@ -7,8 +7,8 @@ #define UDS_CONFIG_H #include "geometry.h" +#include "indexer.h" #include "io-factory.h" -#include "uds.h" /* * The uds_configuration records a variety of parameters used to configure a new UDS index. Some diff --git a/drivers/md/dm-vdo/data-vio.h b/drivers/md/dm-vdo/data-vio.h index 78744d064e96..e7729623a6bb 100644 --- a/drivers/md/dm-vdo/data-vio.h +++ b/drivers/md/dm-vdo/data-vio.h @@ -10,8 +10,8 @@ #include #include +#include "indexer.h" #include "permassert.h" -#include "uds.h" #include "block-map.h" #include "completion.h" diff --git a/drivers/md/dm-vdo/dedupe.c b/drivers/md/dm-vdo/dedupe.c index 2a1902c4423c..942a50ef8b0d 100644 --- a/drivers/md/dm-vdo/dedupe.c +++ b/drivers/md/dm-vdo/dedupe.c @@ -126,12 +126,12 @@ #include #include +#include "indexer.h" #include "logger.h" #include "memory-alloc.h" #include "numeric.h" #include "permassert.h" #include "string-utils.h" -#include "uds.h" #include "action-manager.h" #include "admin-state.h" diff --git a/drivers/md/dm-vdo/dedupe.h b/drivers/md/dm-vdo/dedupe.h index 773dde5f9365..1566fc972ea7 100644 --- a/drivers/md/dm-vdo/dedupe.h +++ b/drivers/md/dm-vdo/dedupe.h @@ -9,7 +9,7 @@ #include #include -#include "uds.h" +#include "indexer.h" #include "admin-state.h" #include "constants.h" diff --git a/drivers/md/dm-vdo/delta-index.c b/drivers/md/dm-vdo/delta-index.c index 6306777bb202..66f51b5f8fd2 100644 --- a/drivers/md/dm-vdo/delta-index.c +++ b/drivers/md/dm-vdo/delta-index.c @@ -13,13 +13,13 @@ #include "config.h" #include "cpu.h" #include "errors.h" +#include "indexer.h" #include "logger.h" #include "memory-alloc.h" #include "numeric.h" #include "permassert.h" #include "string-utils.h" #include "time-utils.h" -#include "uds.h" /* * The entries in a delta index could be stored in a single delta list, but to reduce search times diff --git a/drivers/md/dm-vdo/encodings.h b/drivers/md/dm-vdo/encodings.h index ba3db9867f4a..18794fd59b0b 100644 --- a/drivers/md/dm-vdo/encodings.h +++ b/drivers/md/dm-vdo/encodings.h @@ -11,8 +11,8 @@ #include #include +#include "indexer.h" #include "numeric.h" -#include "uds.h" #include "constants.h" #include "types.h" diff --git a/drivers/md/dm-vdo/funnel-queue.c b/drivers/md/dm-vdo/funnel-queue.c index 6940b282086d..d5d96bb38b94 100644 --- a/drivers/md/dm-vdo/funnel-queue.c +++ b/drivers/md/dm-vdo/funnel-queue.c @@ -8,7 +8,6 @@ #include "cpu.h" #include "memory-alloc.h" #include "permassert.h" -#include "uds.h" int uds_make_funnel_queue(struct funnel_queue **queue_ptr) { diff --git a/drivers/md/dm-vdo/funnel-requestqueue.h b/drivers/md/dm-vdo/funnel-requestqueue.h index e74c231fe269..9b0f53939b4d 100644 --- a/drivers/md/dm-vdo/funnel-requestqueue.h +++ b/drivers/md/dm-vdo/funnel-requestqueue.h @@ -6,7 +6,7 @@ #ifndef UDS_REQUEST_QUEUE_H #define UDS_REQUEST_QUEUE_H -#include "uds.h" +#include "indexer.h" /* * A simple request queue which will handle new requests in the order in which they are received, diff --git a/drivers/md/dm-vdo/geometry.c b/drivers/md/dm-vdo/geometry.c index 0e83bba4184a..04c07195a01c 100644 --- a/drivers/md/dm-vdo/geometry.c +++ b/drivers/md/dm-vdo/geometry.c @@ -10,10 +10,10 @@ #include "delta-index.h" #include "errors.h" +#include "indexer.h" #include "logger.h" #include "memory-alloc.h" #include "permassert.h" -#include "uds.h" /* * An index volume is divided into a fixed number of fixed-size chapters, each consisting of a diff --git a/drivers/md/dm-vdo/geometry.h b/drivers/md/dm-vdo/geometry.h index 9a4a66ac2e46..a2ecdb238cf2 100644 --- a/drivers/md/dm-vdo/geometry.h +++ b/drivers/md/dm-vdo/geometry.h @@ -6,7 +6,7 @@ #ifndef UDS_INDEX_GEOMETRY_H #define UDS_INDEX_GEOMETRY_H -#include "uds.h" +#include "indexer.h" /* * The index_geometry records parameters that define the layout of a UDS index volume, and the size and diff --git a/drivers/md/dm-vdo/hash-utils.h b/drivers/md/dm-vdo/hash-utils.h index e22be69695be..e3b865bbe9b2 100644 --- a/drivers/md/dm-vdo/hash-utils.h +++ b/drivers/md/dm-vdo/hash-utils.h @@ -7,8 +7,8 @@ #define UDS_HASH_UTILS_H #include "geometry.h" +#include "indexer.h" #include "numeric.h" -#include "uds.h" /* Utilities for extracting portions of a request name for various uses. */ diff --git a/drivers/md/dm-vdo/index-layout.h b/drivers/md/dm-vdo/index-layout.h index 84a9eb43a49d..e9ac6f4302d6 100644 --- a/drivers/md/dm-vdo/index-layout.h +++ b/drivers/md/dm-vdo/index-layout.h @@ -7,8 +7,8 @@ #define UDS_INDEX_LAYOUT_H #include "config.h" +#include "indexer.h" #include "io-factory.h" -#include "uds.h" /* * The index layout describes the format of the index on the underlying storage, and is responsible diff --git a/drivers/md/dm-vdo/index-page-map.c b/drivers/md/dm-vdo/index-page-map.c index 8441f86ef3a4..1bb12066ad1a 100644 --- a/drivers/md/dm-vdo/index-page-map.c +++ b/drivers/md/dm-vdo/index-page-map.c @@ -7,13 +7,13 @@ #include "errors.h" #include "hash-utils.h" +#include "indexer.h" #include "logger.h" #include "memory-alloc.h" #include "numeric.h" #include "permassert.h" #include "string-utils.h" #include "thread-utils.h" -#include "uds.h" /* * The index page map is conceptually a two-dimensional array indexed by chapter number and index diff --git a/drivers/md/dm-vdo/index-session.h b/drivers/md/dm-vdo/index-session.h index 62a9020dd9fa..733d10f8a56c 100644 --- a/drivers/md/dm-vdo/index-session.h +++ b/drivers/md/dm-vdo/index-session.h @@ -10,8 +10,8 @@ #include #include "config.h" +#include "indexer.h" #include "thread-utils.h" -#include "uds.h" /* * The index session mediates all interactions with a UDS index. Once the index session is created, diff --git a/drivers/md/dm-vdo/indexer.h b/drivers/md/dm-vdo/indexer.h new file mode 100644 index 000000000000..59e6a5ca2acb --- /dev/null +++ b/drivers/md/dm-vdo/indexer.h @@ -0,0 +1,329 @@ +/* SPDX-License-Identifier: GPL-2.0-only */ +/* + * Copyright 2023 Red Hat + */ + +#ifndef INDEXER_H +#define INDEXER_H + +#include + +#include "funnel-queue.h" + +/* + * UDS public API + * + * The Universal Deduplication System (UDS) is an efficient name-value store. When used for + * deduplicating storage, the names are generally hashes of data blocks and the associated data is + * where that block is located on the underlying storage medium. The stored names are expected to + * be randomly distributed among the space of possible names. If this assumption is violated, the + * UDS index will store fewer names than normal but will otherwise continue to work. The data + * associated with each name can be any 16-byte value. + * + * A client must first create an index session to interact with an index. Once created, the session + * can be shared among multiple threads or users. When a session is destroyed, it will also close + * and save any associated index. + * + * To make a request, a client must allocate a uds_request structure and set the required fields + * before launching it. UDS will invoke the provided callback to complete the request. After the + * callback has been called, the uds_request structure can be freed or reused for a new request. + * There are five types of requests: + * + * A UDS_UPDATE request will associate the provided name with the provided data. Any previous data + * associated with that name will be discarded. + * + * A UDS_QUERY request will return the data associated with the provided name, if any. The entry + * for the name will also be marked as most recent, as if the data had been updated. + * + * A UDS_POST request is a combination of UDS_QUERY and UDS_UPDATE. If there is already data + * associated with the provided name, that data is returned. If there is no existing association, + * the name is associated with the newly provided data. This request is equivalent to a UDS_QUERY + * request followed by a UDS_UPDATE request if no data is found, but it is much more efficient. + * + * A UDS_QUERY_NO_UPDATE request will return the data associated with the provided name, but will + * not change the recency of the entry for the name. This request is primarily useful for testing, + * to determine whether an entry exists without changing the internal state of the index. + * + * A UDS_DELETE request removes any data associated with the provided name. This operation is + * generally not necessary, because the index will automatically discard its oldest entries once it + * becomes full. + */ + +/* General UDS constants and structures */ + +enum uds_request_type { + /* Create or update the mapping for a name, and make the name most recent. */ + UDS_UPDATE, + + /* Return any mapped data for a name, and make the name most recent. */ + UDS_QUERY, + + /* + * Return any mapped data for a name, or map the provided data to the name if there is no + * current data, and make the name most recent. + */ + UDS_POST, + + /* Return any mapped data for a name without updating its recency. */ + UDS_QUERY_NO_UPDATE, + + /* Remove any mapping for a name. */ + UDS_DELETE, + +}; + +enum uds_open_index_type { + /* Create a new index. */ + UDS_CREATE, + + /* Load an existing index and try to recover if necessary. */ + UDS_LOAD, + + /* Load an existing index, but only if it was saved cleanly. */ + UDS_NO_REBUILD, +}; + +enum { + /* The record name size in bytes */ + UDS_RECORD_NAME_SIZE = 16, + /* The maximum record data size in bytes */ + UDS_RECORD_DATA_SIZE = 16, +}; + +/* + * A type representing a UDS memory configuration which is either a positive integer number of + * gigabytes or one of the six special constants for configurations smaller than one gigabyte. + */ +typedef int uds_memory_config_size_t; + +enum { + /* The maximum configurable amount of memory */ + UDS_MEMORY_CONFIG_MAX = 1024, + /* Flag indicating that the index has one less chapter than usual */ + UDS_MEMORY_CONFIG_REDUCED = 0x1000, + UDS_MEMORY_CONFIG_REDUCED_MAX = 1024 + UDS_MEMORY_CONFIG_REDUCED, + /* Special values indicating sizes less than 1 GB */ + UDS_MEMORY_CONFIG_256MB = -256, + UDS_MEMORY_CONFIG_512MB = -512, + UDS_MEMORY_CONFIG_768MB = -768, + UDS_MEMORY_CONFIG_REDUCED_256MB = -1280, + UDS_MEMORY_CONFIG_REDUCED_512MB = -1536, + UDS_MEMORY_CONFIG_REDUCED_768MB = -1792, +}; + +struct uds_record_name { + unsigned char name[UDS_RECORD_NAME_SIZE]; +}; + +struct uds_record_data { + unsigned char data[UDS_RECORD_DATA_SIZE]; +}; + +struct uds_volume_record { + struct uds_record_name name; + struct uds_record_data data; +}; + +struct uds_parameters { + /* The block_device used for storage */ + struct block_device *bdev; + /* The maximum allowable size of the index on storage */ + size_t size; + /* The offset where the index should start */ + off_t offset; + /* The maximum memory allocation, in GB */ + uds_memory_config_size_t memory_size; + /* Whether the index should include sparse chapters */ + bool sparse; + /* A 64-bit nonce to validate the index */ + u64 nonce; + /* The number of threads used to process index requests */ + unsigned int zone_count; + /* The number of threads used to read volume pages */ + unsigned int read_threads; +}; + +/* + * These statistics capture characteristics of the current index, including resource usage and + * requests processed since the index was opened. + */ +struct uds_index_stats { + /* The total number of records stored in the index */ + u64 entries_indexed; + /* An estimate of the index's memory usage, in bytes */ + u64 memory_used; + /* The number of collisions recorded in the volume index */ + u64 collisions; + /* The number of entries discarded from the index since startup */ + u64 entries_discarded; + /* The time at which these statistics were fetched */ + s64 current_time; + /* The number of post calls that found an existing entry */ + u64 posts_found; + /* The number of post calls that added an entry */ + u64 posts_not_found; + /* + * The number of post calls that found an existing entry that is current enough to only + * exist in memory and not have been committed to disk yet + */ + u64 in_memory_posts_found; + /* + * The number of post calls that found an existing entry in the dense portion of the index + */ + u64 dense_posts_found; + /* + * The number of post calls that found an existing entry in the sparse portion of the index + */ + u64 sparse_posts_found; + /* The number of update calls that updated an existing entry */ + u64 updates_found; + /* The number of update calls that added a new entry */ + u64 updates_not_found; + /* The number of delete requests that deleted an existing entry */ + u64 deletions_found; + /* The number of delete requests that did nothing */ + u64 deletions_not_found; + /* The number of query calls that found existing entry */ + u64 queries_found; + /* The number of query calls that did not find an entry */ + u64 queries_not_found; + /* The total number of requests processed */ + u64 requests; +}; + +enum uds_index_region { + /* No location information has been determined */ + UDS_LOCATION_UNKNOWN = 0, + /* The index page entry has been found */ + UDS_LOCATION_INDEX_PAGE_LOOKUP, + /* The record page entry has been found */ + UDS_LOCATION_RECORD_PAGE_LOOKUP, + /* The record is not in the index */ + UDS_LOCATION_UNAVAILABLE, + /* The record was found in the open chapter */ + UDS_LOCATION_IN_OPEN_CHAPTER, + /* The record was found in the dense part of the index */ + UDS_LOCATION_IN_DENSE, + /* The record was found in the sparse part of the index */ + UDS_LOCATION_IN_SPARSE, +} __packed; + +/* Zone message requests are used to communicate between index zones. */ +enum uds_zone_message_type { + /* A standard request with no message */ + UDS_MESSAGE_NONE = 0, + /* Add a chapter to the sparse chapter index cache */ + UDS_MESSAGE_SPARSE_CACHE_BARRIER, + /* Close a chapter to keep the zone from falling behind */ + UDS_MESSAGE_ANNOUNCE_CHAPTER_CLOSED, +} __packed; + +struct uds_zone_message { + /* The type of message, determining how it will be processed */ + enum uds_zone_message_type type; + /* The virtual chapter number to which the message applies */ + u64 virtual_chapter; +}; + +struct uds_index_session; +struct uds_index; +struct uds_request; + +/* Once this callback has been invoked, the uds_request structure can be reused or freed. */ +typedef void (*uds_request_callback_fn)(struct uds_request *request); + +struct uds_request { + /* These input fields must be set before launching a request. */ + + /* The name of the record to look up or create */ + struct uds_record_name record_name; + /* New data to associate with the record name, if applicable */ + struct uds_record_data new_metadata; + /* A callback to invoke when the request is complete */ + uds_request_callback_fn callback; + /* The index session that will manage this request */ + struct uds_index_session *session; + /* The type of operation to perform, as describe above */ + enum uds_request_type type; + + /* These output fields are set when a request is complete. */ + + /* The existing data associated with the request name, if any */ + struct uds_record_data old_metadata; + /* Either UDS_SUCCESS or an error code for the request */ + int status; + /* True if the record name had an existing entry in the index */ + bool found; + + /* + * The remaining fields are used internally and should not be altered by clients. The index + * relies on zone_number being the first field in this section. + */ + + /* The number of the zone which will process this request*/ + unsigned int zone_number; + /* A link for adding a request to a lock-free queue */ + struct funnel_queue_entry queue_link; + /* A link for adding a request to a standard linked list */ + struct uds_request *next_request; + /* A pointer to the index processing this request */ + struct uds_index *index; + /* Control message for coordinating between zones */ + struct uds_zone_message zone_message; + /* If true, process request immediately by waking the worker thread */ + bool unbatched; + /* If true, continue this request before processing newer requests */ + bool requeued; + /* The virtual chapter containing the record name, if known */ + u64 virtual_chapter; + /* The region of the index containing the record name */ + enum uds_index_region location; +}; + +/* Compute the number of bytes needed to store an index. */ +int __must_check uds_compute_index_size(const struct uds_parameters *parameters, + u64 *index_size); + +/* A session is required for most index operations. */ +int __must_check uds_create_index_session(struct uds_index_session **session); + +/* Destroying an index session also closes and saves the associated index. */ +int uds_destroy_index_session(struct uds_index_session *session); + +/* + * Create or open an index with an existing session. This operation fails if the index session is + * suspended, or if there is already an open index. + */ +int __must_check uds_open_index(enum uds_open_index_type open_type, + const struct uds_parameters *parameters, + struct uds_index_session *session); + +/* + * Wait until all callbacks for index operations are complete, and prevent new index operations + * from starting. New index operations will fail with EBUSY until the session is resumed. Also + * optionally saves the index. + */ +int __must_check uds_suspend_index_session(struct uds_index_session *session, bool save); + +/* + * Allow new index operations for an index, whether it was suspended or not. If the index is + * suspended and the supplied block device differs from the current backing store, the index will + * start using the new backing store instead. + */ +int __must_check uds_resume_index_session(struct uds_index_session *session, + struct block_device *bdev); + +/* Wait until all outstanding index operations are complete. */ +int __must_check uds_flush_index_session(struct uds_index_session *session); + +/* Close an index. This operation fails if the index session is suspended. */ +int __must_check uds_close_index(struct uds_index_session *session); + +/* Get index statistics since the last time the index was opened. */ +int __must_check uds_get_index_session_stats(struct uds_index_session *session, + struct uds_index_stats *stats); + +/* This function will fail if any required field of the request is not set. */ +int __must_check uds_launch_request(struct uds_request *request); + +#endif /* INDEXER_H */ diff --git a/drivers/md/dm-vdo/sparse-cache.h b/drivers/md/dm-vdo/sparse-cache.h index 90b0be155453..45e2dcf165b5 100644 --- a/drivers/md/dm-vdo/sparse-cache.h +++ b/drivers/md/dm-vdo/sparse-cache.h @@ -7,7 +7,7 @@ #define UDS_SPARSE_CACHE_H #include "geometry.h" -#include "uds.h" +#include "indexer.h" /* * The sparse cache is a cache of entire chapter indexes from sparse chapters used for searching diff --git a/drivers/md/dm-vdo/uds-sysfs.c b/drivers/md/dm-vdo/uds-sysfs.c index eee8a5b7d147..1548092e7de1 100644 --- a/drivers/md/dm-vdo/uds-sysfs.c +++ b/drivers/md/dm-vdo/uds-sysfs.c @@ -9,10 +9,10 @@ #include #include +#include "indexer.h" #include "logger.h" #include "memory-alloc.h" #include "string-utils.h" -#include "uds.h" #define UDS_SYSFS_NAME "uds" diff --git a/drivers/md/dm-vdo/uds.h b/drivers/md/dm-vdo/uds.h deleted file mode 100644 index 1264362f8372..000000000000 --- a/drivers/md/dm-vdo/uds.h +++ /dev/null @@ -1,329 +0,0 @@ -/* SPDX-License-Identifier: GPL-2.0-only */ -/* - * Copyright 2023 Red Hat - */ - -#ifndef UDS_H -#define UDS_H - -#include - -#include "funnel-queue.h" - -/* - * UDS public API - * - * The Universal Deduplication System (UDS) is an efficient name-value store. When used for - * deduplicating storage, the names are generally hashes of data blocks and the associated data is - * where that block is located on the underlying storage medium. The stored names are expected to - * be randomly distributed among the space of possible names. If this assumption is violated, the - * UDS index will store fewer names than normal but will otherwise continue to work. The data - * associated with each name can be any 16-byte value. - * - * A client must first create an index session to interact with an index. Once created, the session - * can be shared among multiple threads or users. When a session is destroyed, it will also close - * and save any associated index. - * - * To make a request, a client must allocate a uds_request structure and set the required fields - * before launching it. UDS will invoke the provided callback to complete the request. After the - * callback has been called, the uds_request structure can be freed or reused for a new request. - * There are five types of requests: - * - * A UDS_UPDATE request will associate the provided name with the provided data. Any previous data - * associated with that name will be discarded. - * - * A UDS_QUERY request will return the data associated with the provided name, if any. The entry - * for the name will also be marked as most recent, as if the data had been updated. - * - * A UDS_POST request is a combination of UDS_QUERY and UDS_UPDATE. If there is already data - * associated with the provided name, that data is returned. If there is no existing association, - * the name is associated with the newly provided data. This request is equivalent to a UDS_QUERY - * request followed by a UDS_UPDATE request if no data is found, but it is much more efficient. - * - * A UDS_QUERY_NO_UPDATE request will return the data associated with the provided name, but will - * not change the recency of the entry for the name. This request is primarily useful for testing, - * to determine whether an entry exists without changing the internal state of the index. - * - * A UDS_DELETE request removes any data associated with the provided name. This operation is - * generally not necessary, because the index will automatically discard its oldest entries once it - * becomes full. - */ - -/* General UDS constants and structures */ - -enum uds_request_type { - /* Create or update the mapping for a name, and make the name most recent. */ - UDS_UPDATE, - - /* Return any mapped data for a name, and make the name most recent. */ - UDS_QUERY, - - /* - * Return any mapped data for a name, or map the provided data to the name if there is no - * current data, and make the name most recent. - */ - UDS_POST, - - /* Return any mapped data for a name without updating its recency. */ - UDS_QUERY_NO_UPDATE, - - /* Remove any mapping for a name. */ - UDS_DELETE, - -}; - -enum uds_open_index_type { - /* Create a new index. */ - UDS_CREATE, - - /* Load an existing index and try to recover if necessary. */ - UDS_LOAD, - - /* Load an existing index, but only if it was saved cleanly. */ - UDS_NO_REBUILD, -}; - -enum { - /* The record name size in bytes */ - UDS_RECORD_NAME_SIZE = 16, - /* The maximum record data size in bytes */ - UDS_RECORD_DATA_SIZE = 16, -}; - -/* - * A type representing a UDS memory configuration which is either a positive integer number of - * gigabytes or one of the six special constants for configurations smaller than one gigabyte. - */ -typedef int uds_memory_config_size_t; - -enum { - /* The maximum configurable amount of memory */ - UDS_MEMORY_CONFIG_MAX = 1024, - /* Flag indicating that the index has one less chapter than usual */ - UDS_MEMORY_CONFIG_REDUCED = 0x1000, - UDS_MEMORY_CONFIG_REDUCED_MAX = 1024 + UDS_MEMORY_CONFIG_REDUCED, - /* Special values indicating sizes less than 1 GB */ - UDS_MEMORY_CONFIG_256MB = -256, - UDS_MEMORY_CONFIG_512MB = -512, - UDS_MEMORY_CONFIG_768MB = -768, - UDS_MEMORY_CONFIG_REDUCED_256MB = -1280, - UDS_MEMORY_CONFIG_REDUCED_512MB = -1536, - UDS_MEMORY_CONFIG_REDUCED_768MB = -1792, -}; - -struct uds_record_name { - unsigned char name[UDS_RECORD_NAME_SIZE]; -}; - -struct uds_record_data { - unsigned char data[UDS_RECORD_DATA_SIZE]; -}; - -struct uds_volume_record { - struct uds_record_name name; - struct uds_record_data data; -}; - -struct uds_parameters { - /* The block_device used for storage */ - struct block_device *bdev; - /* The maximum allowable size of the index on storage */ - size_t size; - /* The offset where the index should start */ - off_t offset; - /* The maximum memory allocation, in GB */ - uds_memory_config_size_t memory_size; - /* Whether the index should include sparse chapters */ - bool sparse; - /* A 64-bit nonce to validate the index */ - u64 nonce; - /* The number of threads used to process index requests */ - unsigned int zone_count; - /* The number of threads used to read volume pages */ - unsigned int read_threads; -}; - -/* - * These statistics capture characteristics of the current index, including resource usage and - * requests processed since the index was opened. - */ -struct uds_index_stats { - /* The total number of records stored in the index */ - u64 entries_indexed; - /* An estimate of the index's memory usage, in bytes */ - u64 memory_used; - /* The number of collisions recorded in the volume index */ - u64 collisions; - /* The number of entries discarded from the index since startup */ - u64 entries_discarded; - /* The time at which these statistics were fetched */ - s64 current_time; - /* The number of post calls that found an existing entry */ - u64 posts_found; - /* The number of post calls that added an entry */ - u64 posts_not_found; - /* - * The number of post calls that found an existing entry that is current enough to only - * exist in memory and not have been committed to disk yet - */ - u64 in_memory_posts_found; - /* - * The number of post calls that found an existing entry in the dense portion of the index - */ - u64 dense_posts_found; - /* - * The number of post calls that found an existing entry in the sparse portion of the index - */ - u64 sparse_posts_found; - /* The number of update calls that updated an existing entry */ - u64 updates_found; - /* The number of update calls that added a new entry */ - u64 updates_not_found; - /* The number of delete requests that deleted an existing entry */ - u64 deletions_found; - /* The number of delete requests that did nothing */ - u64 deletions_not_found; - /* The number of query calls that found existing entry */ - u64 queries_found; - /* The number of query calls that did not find an entry */ - u64 queries_not_found; - /* The total number of requests processed */ - u64 requests; -}; - -enum uds_index_region { - /* No location information has been determined */ - UDS_LOCATION_UNKNOWN = 0, - /* The index page entry has been found */ - UDS_LOCATION_INDEX_PAGE_LOOKUP, - /* The record page entry has been found */ - UDS_LOCATION_RECORD_PAGE_LOOKUP, - /* The record is not in the index */ - UDS_LOCATION_UNAVAILABLE, - /* The record was found in the open chapter */ - UDS_LOCATION_IN_OPEN_CHAPTER, - /* The record was found in the dense part of the index */ - UDS_LOCATION_IN_DENSE, - /* The record was found in the sparse part of the index */ - UDS_LOCATION_IN_SPARSE, -} __packed; - -/* Zone message requests are used to communicate between index zones. */ -enum uds_zone_message_type { - /* A standard request with no message */ - UDS_MESSAGE_NONE = 0, - /* Add a chapter to the sparse chapter index cache */ - UDS_MESSAGE_SPARSE_CACHE_BARRIER, - /* Close a chapter to keep the zone from falling behind */ - UDS_MESSAGE_ANNOUNCE_CHAPTER_CLOSED, -} __packed; - -struct uds_zone_message { - /* The type of message, determining how it will be processed */ - enum uds_zone_message_type type; - /* The virtual chapter number to which the message applies */ - u64 virtual_chapter; -}; - -struct uds_index_session; -struct uds_index; -struct uds_request; - -/* Once this callback has been invoked, the uds_request structure can be reused or freed. */ -typedef void (*uds_request_callback_fn)(struct uds_request *request); - -struct uds_request { - /* These input fields must be set before launching a request. */ - - /* The name of the record to look up or create */ - struct uds_record_name record_name; - /* New data to associate with the record name, if applicable */ - struct uds_record_data new_metadata; - /* A callback to invoke when the request is complete */ - uds_request_callback_fn callback; - /* The index session that will manage this request */ - struct uds_index_session *session; - /* The type of operation to perform, as describe above */ - enum uds_request_type type; - - /* These output fields are set when a request is complete. */ - - /* The existing data associated with the request name, if any */ - struct uds_record_data old_metadata; - /* Either UDS_SUCCESS or an error code for the request */ - int status; - /* True if the record name had an existing entry in the index */ - bool found; - - /* - * The remaining fields are used internally and should not be altered by clients. The index - * relies on zone_number being the first field in this section. - */ - - /* The number of the zone which will process this request*/ - unsigned int zone_number; - /* A link for adding a request to a lock-free queue */ - struct funnel_queue_entry queue_link; - /* A link for adding a request to a standard linked list */ - struct uds_request *next_request; - /* A pointer to the index processing this request */ - struct uds_index *index; - /* Control message for coordinating between zones */ - struct uds_zone_message zone_message; - /* If true, process request immediately by waking the worker thread */ - bool unbatched; - /* If true, continue this request before processing newer requests */ - bool requeued; - /* The virtual chapter containing the record name, if known */ - u64 virtual_chapter; - /* The region of the index containing the record name */ - enum uds_index_region location; -}; - -/* Compute the number of bytes needed to store an index. */ -int __must_check uds_compute_index_size(const struct uds_parameters *parameters, - u64 *index_size); - -/* A session is required for most index operations. */ -int __must_check uds_create_index_session(struct uds_index_session **session); - -/* Destroying an index session also closes and saves the associated index. */ -int uds_destroy_index_session(struct uds_index_session *session); - -/* - * Create or open an index with an existing session. This operation fails if the index session is - * suspended, or if there is already an open index. - */ -int __must_check uds_open_index(enum uds_open_index_type open_type, - const struct uds_parameters *parameters, - struct uds_index_session *session); - -/* - * Wait until all callbacks for index operations are complete, and prevent new index operations - * from starting. New index operations will fail with EBUSY until the session is resumed. Also - * optionally saves the index. - */ -int __must_check uds_suspend_index_session(struct uds_index_session *session, bool save); - -/* - * Allow new index operations for an index, whether it was suspended or not. If the index is - * suspended and the supplied block device differs from the current backing store, the index will - * start using the new backing store instead. - */ -int __must_check uds_resume_index_session(struct uds_index_session *session, - struct block_device *bdev); - -/* Wait until all outstanding index operations are complete. */ -int __must_check uds_flush_index_session(struct uds_index_session *session); - -/* Close an index. This operation fails if the index session is suspended. */ -int __must_check uds_close_index(struct uds_index_session *session); - -/* Get index statistics since the last time the index was opened. */ -int __must_check uds_get_index_session_stats(struct uds_index_session *session, - struct uds_index_stats *stats); - -/* This function will fail if any required field of the request is not set. */ -int __must_check uds_launch_request(struct uds_request *request); - -#endif /* UDS_H */ diff --git a/drivers/md/dm-vdo/vdo.h b/drivers/md/dm-vdo/vdo.h index 772317e6db52..3938e519ae6a 100644 --- a/drivers/md/dm-vdo/vdo.h +++ b/drivers/md/dm-vdo/vdo.h @@ -17,12 +17,12 @@ #include "admin-state.h" #include "encodings.h" #include "funnel-workqueue.h" +#include "indexer.h" #include "packer.h" #include "physical-zone.h" #include "statistics.h" #include "thread-registry.h" #include "types.h" -#include "uds.h" enum notifier_state { /* Notifications are allowed but not in progress */ diff --git a/drivers/md/dm-vdo/volume-index.c b/drivers/md/dm-vdo/volume-index.c index daeafe7691ea..39c4be06780f 100644 --- a/drivers/md/dm-vdo/volume-index.c +++ b/drivers/md/dm-vdo/volume-index.c @@ -14,12 +14,12 @@ #include "errors.h" #include "geometry.h" #include "hash-utils.h" +#include "indexer.h" #include "logger.h" #include "memory-alloc.h" #include "numeric.h" #include "permassert.h" #include "thread-utils.h" -#include "uds.h" /* * The volume index is a combination of two separate subindexes, one containing sparse hook entries diff --git a/drivers/md/dm-vdo/volume-index.h b/drivers/md/dm-vdo/volume-index.h index 2eb2cee7ee58..66bf14fddc90 100644 --- a/drivers/md/dm-vdo/volume-index.h +++ b/drivers/md/dm-vdo/volume-index.h @@ -10,8 +10,8 @@ #include "config.h" #include "delta-index.h" +#include "indexer.h" #include "thread-utils.h" -#include "uds.h" /* * The volume index is the primary top-level index for UDS. It contains records which map a record diff --git a/drivers/md/dm-vdo/volume.h b/drivers/md/dm-vdo/volume.h index 7ef9945d8403..290de5cbf9ec 100644 --- a/drivers/md/dm-vdo/volume.h +++ b/drivers/md/dm-vdo/volume.h @@ -14,13 +14,13 @@ #include "chapter-index.h" #include "config.h" #include "geometry.h" +#include "indexer.h" #include "index-layout.h" #include "index-page-map.h" #include "permassert.h" #include "radix-sort.h" #include "sparse-cache.h" #include "thread-utils.h" -#include "uds.h" /* * The volume manages deduplication records on permanent storage. The term "volume" can also refer -- cgit v1.2.3