// SPDX-License-Identifier: GPL-2.0-only /* * Copyright 2023 Red Hat */ /** * DOC: * * Hash table implementation of a map from integers to pointers, implemented using the Hopscotch * Hashing algorithm by Herlihy, Shavit, and Tzafrir (see * http://en.wikipedia.org/wiki/Hopscotch_hashing). This implementation does not contain any of the * locking/concurrency features of the algorithm, just the collision resolution scheme. * * Hopscotch Hashing is based on hashing with open addressing and linear probing. All the entries * are stored in a fixed array of buckets, with no dynamic allocation for collisions. Unlike linear * probing, all the entries that hash to a given bucket are stored within a fixed neighborhood * starting at that bucket. Chaining is effectively represented as a bit vector relative to each * bucket instead of as pointers or explicit offsets. * * When an empty bucket cannot be found within a given neighborhood, subsequent neighborhoods are * searched, and one or more entries will "hop" into those neighborhoods. When this process works, * an empty bucket will move into the desired neighborhood, allowing the entry to be added. When * that process fails (typically when the buckets are around 90% full), the table must be resized * and the all entries rehashed and added to the expanded table. * * Unlike linear probing, the number of buckets that must be searched in the worst case has a fixed * upper bound (the size of the neighborhood). Those entries occupy a small number of memory cache * lines, leading to improved use of the cache (fewer misses on both successful and unsuccessful * searches). Hopscotch hashing outperforms linear probing at much higher load factors, so even * with the increased memory burden for maintaining the hop vectors, less memory is needed to * achieve that performance. Hopscotch is also immune to "contamination" from deleting entries * since entries are genuinely removed instead of being replaced by a placeholder. * * The published description of the algorithm used a bit vector, but the paper alludes to an offset * scheme which is used by this implementation. Since the entries in the neighborhood are within N * entries of the hash bucket at the start of the neighborhood, a pair of small offset fields each * log2(N) bits wide is all that's needed to maintain the hops as a linked list. In order to encode * "no next hop" (i.e. NULL) as the natural initial value of zero, the offsets are biased by one * (i.e. 0 => NULL, 1 => offset=0, 2 => offset=1, etc.) We can represent neighborhoods of up to 255 * entries with just 8+8=16 bits per entry. The hop list is sorted by hop offset so the first entry * in the list is always the bucket closest to the start of the neighborhood. * * While individual accesses tend to be very fast, the table resize operations are very, very * expensive. If an upper bound on the latency of adding an entry to the table is needed, we either * need to ensure the table is pre-sized to be large enough so no resize is ever needed, or we'll * need to develop an approach to incrementally resize the table. */ #include "int-map.h" #include <linux/minmax.h> #include "errors.h" #include "logger.h" #include "memory-alloc.h" #include "numeric.h" #include "permassert.h" #define DEFAULT_CAPACITY … #define NEIGHBORHOOD … #define MAX_PROBES … #define NULL_HOP_OFFSET … #define DEFAULT_LOAD … /** * struct bucket - hash bucket * * Buckets are packed together to reduce memory usage and improve cache efficiency. It would be * tempting to encode the hop offsets separately and maintain alignment of key/value pairs, but * it's crucial to keep the hop fields near the buckets that they use them so they'll tend to share * cache lines. */ struct __packed bucket { … }; /** * struct int_map - The concrete definition of the opaque int_map type. * * To avoid having to wrap the neighborhoods of the last entries back around to the start of the * bucket array, we allocate a few more buckets at the end of the array instead, which is why * capacity and bucket_count are different. */ struct int_map { … }; /** * mix() - The Google CityHash 16-byte hash mixing function. * @input1: The first input value. * @input2: The second input value. * * Return: A hash of the two inputs. */ static u64 mix(u64 input1, u64 input2) { … } /** * hash_key() - Calculate a 64-bit non-cryptographic hash value for the provided 64-bit integer * key. * @key: The mapping key. * * The implementation is based on Google's CityHash, only handling the specific case of an 8-byte * input. * * Return: The hash of the mapping key. */ static u64 hash_key(u64 key) { … } /** * allocate_buckets() - Initialize an int_map. * @map: The map to initialize. * @capacity: The initial capacity of the map. * * Return: VDO_SUCCESS or an error code. */ static int allocate_buckets(struct int_map *map, size_t capacity) { … } /** * vdo_int_map_create() - Allocate and initialize an int_map. * @initial_capacity: The number of entries the map should initially be capable of holding (zero * tells the map to use its own small default). * @map_ptr: Output, a pointer to hold the new int_map. * * Return: VDO_SUCCESS or an error code. */ int vdo_int_map_create(size_t initial_capacity, struct int_map **map_ptr) { … } /** * vdo_int_map_free() - Free an int_map. * @map: The int_map to free. * * NOTE: The map does not own the pointer values stored in the map and they are not freed by this * call. */ void vdo_int_map_free(struct int_map *map) { … } /** * vdo_int_map_size() - Get the number of entries stored in an int_map. * @map: The int_map to query. * * Return: The number of entries in the map. */ size_t vdo_int_map_size(const struct int_map *map) { … } /** * dereference_hop() - Convert a biased hop offset within a neighborhood to a pointer to the bucket * it references. * @neighborhood: The first bucket in the neighborhood. * @hop_offset: The biased hop offset to the desired bucket. * * Return: NULL if hop_offset is zero, otherwise a pointer to the bucket in the neighborhood at * hop_offset - 1. */ static struct bucket *dereference_hop(struct bucket *neighborhood, unsigned int hop_offset) { … } /** * insert_in_hop_list() - Add a bucket into the hop list for the neighborhood. * @neighborhood: The first bucket in the neighborhood. * @new_bucket: The bucket to add to the hop list. * * The bucket is inserted it into the list so the hop list remains sorted by hop offset. */ static void insert_in_hop_list(struct bucket *neighborhood, struct bucket *new_bucket) { … } /** * select_bucket() - Select and return the hash bucket for a given search key. * @map: The map to search. * @key: The mapping key. */ static struct bucket *select_bucket(const struct int_map *map, u64 key) { … } /** * search_hop_list() - Search the hop list associated with given hash bucket for a given search * key. * @map: The map being searched. * @bucket: The map bucket to search for the key. * @key: The mapping key. * @previous_ptr: Output. if not NULL, a pointer in which to store the bucket in the list preceding * the one that had the matching key * * If the key is found, returns a pointer to the entry (bucket or collision), otherwise returns * NULL. * * Return: An entry that matches the key, or NULL if not found. */ static struct bucket *search_hop_list(struct int_map *map __always_unused, struct bucket *bucket, u64 key, struct bucket **previous_ptr) { … } /** * vdo_int_map_get() - Retrieve the value associated with a given key from the int_map. * @map: The int_map to query. * @key: The key to look up. * * Return: The value associated with the given key, or NULL if the key is not mapped to any value. */ void *vdo_int_map_get(struct int_map *map, u64 key) { … } /** * resize_buckets() - Increase the number of hash buckets. * @map: The map to resize. * * Resizes and rehashes all the existing entries, storing them in the new buckets. * * Return: VDO_SUCCESS or an error code. */ static int resize_buckets(struct int_map *map) { … } /** * find_empty_bucket() - Probe the bucket array starting at the given bucket for the next empty * bucket, returning a pointer to it. * @map: The map containing the buckets to search. * @bucket: The bucket at which to start probing. * @max_probes: The maximum number of buckets to search. * * NULL will be returned if the search reaches the end of the bucket array or if the number of * linear probes exceeds a specified limit. * * Return: The next empty bucket, or NULL if the search failed. */ static struct bucket * find_empty_bucket(struct int_map *map, struct bucket *bucket, unsigned int max_probes) { … } /** * move_empty_bucket() - Move an empty bucket closer to the start of the bucket array. * @map: The map containing the bucket. * @hole: The empty bucket to fill with an entry that precedes it in one of its enclosing * neighborhoods. * * This searches the neighborhoods that contain the empty bucket for a non-empty bucket closer to * the start of the array. If such a bucket is found, this swaps the two buckets by moving the * entry to the empty bucket. * * Return: The bucket that was vacated by moving its entry to the provided hole, or NULL if no * entry could be moved. */ static struct bucket *move_empty_bucket(struct int_map *map __always_unused, struct bucket *hole) { … } /** * update_mapping() - Find and update any existing mapping for a given key, returning the value * associated with the key in the provided pointer. * @map: The int_map to attempt to modify. * @neighborhood: The first bucket in the neighborhood that would contain the search key * @key: The key with which to associate the new value. * @new_value: The value to be associated with the key. * @update: Whether to overwrite an existing value. * @old_value_ptr: a pointer in which to store the old value (unmodified if no mapping was found) * * Return: true if the map contains a mapping for the key, false if it does not. */ static bool update_mapping(struct int_map *map, struct bucket *neighborhood, u64 key, void *new_value, bool update, void **old_value_ptr) { … } /** * find_or_make_vacancy() - Find an empty bucket. * @map: The int_map to search or modify. * @neighborhood: The first bucket in the neighborhood in which an empty bucket is needed for a new * mapping. * * Find an empty bucket in a specified neighborhood for a new mapping or attempt to re-arrange * mappings so there is such a bucket. This operation may fail (returning NULL) if an empty bucket * is not available or could not be relocated to the neighborhood. * * Return: a pointer to an empty bucket in the desired neighborhood, or NULL if a vacancy could not * be found or arranged. */ static struct bucket *find_or_make_vacancy(struct int_map *map, struct bucket *neighborhood) { … } /** * vdo_int_map_put() - Try to associate a value with an integer. * @map: The int_map to attempt to modify. * @key: The key with which to associate the new value. * @new_value: The value to be associated with the key. * @update: Whether to overwrite an existing value. * @old_value_ptr: A pointer in which to store either the old value (if the key was already mapped) * or NULL if the map did not contain the key; NULL may be provided if the caller * does not need to know the old value * * Try to associate a value (a pointer) with an integer in an int_map. If the map already contains * a mapping for the provided key, the old value is only replaced with the specified value if * update is true. In either case the old value is returned. If the map does not already contain a * value for the specified key, the new value is added regardless of the value of update. * * Return: VDO_SUCCESS or an error code. */ int vdo_int_map_put(struct int_map *map, u64 key, void *new_value, bool update, void **old_value_ptr) { … } /** * vdo_int_map_remove() - Remove the mapping for a given key from the int_map. * @map: The int_map from which to remove the mapping. * @key: The key whose mapping is to be removed. * * Return: the value that was associated with the key, or NULL if it was not mapped. */ void *vdo_int_map_remove(struct int_map *map, u64 key) { … }
Codebase Browser
linux