1 // SPDX-License-Identifier: GPL-2.0-only
9  * Hash table implementation of a map from integers to pointers, implemented using the Hopscotch
15  * are stored in a fixed array of buckets, with no dynamic allocation for collisions. Unlike linear
38  * "no next hop" (i.e. NULL) as the natural initial value of zero, the offsets are biased by one
45  * need to ensure the table is pre-sized to be large enough so no resize is ever needed, or we'll
49 #include "int-map.h"
55 #include "memory-alloc.h"
66  * struct bucket - hash bucket
88  * struct int_map - The concrete definition of the opaque int_map type.
95 	/** @size: The number of entries stored in the map. */
97 	/** @capacity: The number of neighborhoods in the map. */
106  * mix() - The Google CityHash 16-byte hash mixing function.
127  * hash_key() - Calculate a 64-bit non-cryptographic hash value for the provided 64-bit integer
131  * The implementation is based on Google's CityHash, only handling the specific case of an 8-byte
151  * allocate_buckets() - Initialize an int_map.
152  * @map: The map to initialize.
153  * @capacity: The initial capacity of the map.
157 static int allocate_buckets(struct int_map *map, size_t capacity)  in allocate_buckets()  argument
159 	map->size = 0;  in allocate_buckets()
160 	map->capacity = capacity;  in allocate_buckets()
163 	 * Allocate NEIGHBORHOOD - 1 extra buckets so the last bucket can have a full neighborhood  in allocate_buckets()
166 	map->bucket_count = capacity + (NEIGHBORHOOD - 1);  in allocate_buckets()
167 	return vdo_allocate(map->bucket_count, struct bucket,  in allocate_buckets()
168 			    "struct int_map buckets", &map->buckets);  in allocate_buckets()
172  * vdo_int_map_create() - Allocate and initialize an int_map.
173  * @initial_capacity: The number of entries the map should initially be capable of holding (zero
174  *                    tells the map to use its own small default).
181 	struct int_map *map;  in vdo_int_map_create()  local
185 	result = vdo_allocate(1, struct int_map, "struct int_map", &map);  in vdo_int_map_create()
198 	result = allocate_buckets(map, capacity);  in vdo_int_map_create()
200 		vdo_int_map_free(vdo_forget(map));  in vdo_int_map_create()
204 	*map_ptr = map;  in vdo_int_map_create()
209  * vdo_int_map_free() - Free an int_map.
210  * @map: The int_map to free.
212  * NOTE: The map does not own the pointer values stored in the map and they are not freed by this
215 void vdo_int_map_free(struct int_map *map)  in vdo_int_map_free()  argument
217 	if (map == NULL)  in vdo_int_map_free()
220 	vdo_free(vdo_forget(map->buckets));  in vdo_int_map_free()
221 	vdo_free(vdo_forget(map));  in vdo_int_map_free()
225  * vdo_int_map_size() - Get the number of entries stored in an int_map.
226  * @map: The int_map to query.
228  * Return: The number of entries in the map.
230 size_t vdo_int_map_size(const struct int_map *map)  in vdo_int_map_size()  argument
232 	return map->size;  in vdo_int_map_size()
236  * dereference_hop() - Convert a biased hop offset within a neighborhood to a pointer to the bucket
242  *         hop_offset - 1.
250 	return &neighborhood[hop_offset - 1];  in dereference_hop()
254  * insert_in_hop_list() - Add a bucket into the hop list for the neighborhood.
263 	int hop_offset = 1 + (new_bucket - neighborhood);  in insert_in_hop_list()
266 	int next_hop = neighborhood->first_hop;  in insert_in_hop_list()
269 		new_bucket->next_hop = next_hop;  in insert_in_hop_list()
270 		neighborhood->first_hop = hop_offset;  in insert_in_hop_list()
278 		next_hop = bucket->next_hop;  in insert_in_hop_list()
281 			new_bucket->next_hop = next_hop;  in insert_in_hop_list()
282 			bucket->next_hop = hop_offset;  in insert_in_hop_list()
289  * select_bucket() - Select and return the hash bucket for a given search key.
290  * @map: The map to search.
293 static struct bucket *select_bucket(const struct int_map *map, u64 key)  in select_bucket()  argument
302 	 * Scale the 32-bit hash to a bucket index by treating it as a binary fraction and  in select_bucket()
304 	 * 2^32-1], then (hash * capacity / 2^32) should be uniformly distributed over [0 ..  in select_bucket()
305 	 * capacity-1]. The multiply and shift is much faster than a divide (modulus) on X86 CPUs.  in select_bucket()
307 	return &map->buckets[(hash * map->capacity) >> 32];  in select_bucket()
311  * search_hop_list() - Search the hop list associated with given hash bucket for a given search
313  * @map: The map being searched.
314  * @bucket: The map bucket to search for the key.
324 static struct bucket *search_hop_list(struct int_map *map __always_unused,  in search_hop_list()
330 	unsigned int next_hop = bucket->first_hop;  in search_hop_list()
339 		if ((key == entry->key) && (entry->value != NULL)) {  in search_hop_list()
344 		next_hop = entry->next_hop;  in search_hop_list()
352  * vdo_int_map_get() - Retrieve the value associated with a given key from the int_map.
353  * @map: The int_map to query.
358 void *vdo_int_map_get(struct int_map *map, u64 key)  in vdo_int_map_get()  argument
360 	struct bucket *match = search_hop_list(map, select_bucket(map, key), key, NULL);  in vdo_int_map_get()
362 	return ((match != NULL) ? match->value : NULL);  in vdo_int_map_get()
366  * resize_buckets() - Increase the number of hash buckets.
367  * @map: The map to resize.
373 static int resize_buckets(struct int_map *map)  in resize_buckets()  argument
378 	/* Copy the top-level map data to the stack. */  in resize_buckets()
379 	struct int_map old_map = *map;  in resize_buckets()
381 	/* Re-initialize the map to be empty and 50% larger. */  in resize_buckets()
382 	size_t new_capacity = map->capacity / 2 * 3;  in resize_buckets()
385 		     __func__, map->capacity, new_capacity, map->size);  in resize_buckets()
386 	result = allocate_buckets(map, new_capacity);  in resize_buckets()
388 		*map = old_map;  in resize_buckets()
396 		if (entry->value == NULL)  in resize_buckets()
399 		result = vdo_int_map_put(map, entry->key, entry->value, true, NULL);  in resize_buckets()
401 			/* Destroy the new partial map and restore the map from the stack. */  in resize_buckets()
402 			vdo_free(vdo_forget(map->buckets));  in resize_buckets()
403 			*map = old_map;  in resize_buckets()
414  * find_empty_bucket() - Probe the bucket array starting at the given bucket for the next empty
416  * @map: The map containing the buckets to search.
426 find_empty_bucket(struct int_map *map, struct bucket *bucket, unsigned int max_probes)  in find_empty_bucket()  argument
432 	ptrdiff_t remaining = &map->buckets[map->bucket_count] - bucket;  in find_empty_bucket()
437 		if (entry->value == NULL)  in find_empty_bucket()
445  * move_empty_bucket() - Move an empty bucket closer to the start of the bucket array.
446  * @map: The map containing the bucket.
450  * This searches the neighborhoods that contain the empty bucket for a non-empty bucket closer to
454  * Return: The bucket that was vacated by moving its entry to the provided hole, or NULL if no
457 static struct bucket *move_empty_bucket(struct int_map *map __always_unused,  in move_empty_bucket()
462 	 * which it is the last bucket. No boundary check is needed for the negative array  in move_empty_bucket()
468 	for (bucket = &hole[1 - NEIGHBORHOOD]; bucket < hole; bucket++) {  in move_empty_bucket()
473 		struct bucket *new_hole = dereference_hop(bucket, bucket->first_hop);  in move_empty_bucket()
477 			 * There are no buckets in this neighborhood that are in use by this one  in move_empty_bucket()
499 		bucket->first_hop = new_hole->next_hop;  in move_empty_bucket()
500 		new_hole->next_hop = NULL_HOP_OFFSET;  in move_empty_bucket()
503 		hole->key = new_hole->key;  in move_empty_bucket()
504 		hole->value = new_hole->value;  in move_empty_bucket()
505 		new_hole->value = NULL;  in move_empty_bucket()
517  * update_mapping() - Find and update any existing mapping for a given key, returning the value
519  * @map: The int_map to attempt to modify.
524  * @old_value_ptr: a pointer in which to store the old value (unmodified if no mapping was found)
526  * Return: true if the map contains a mapping for the key, false if it does not.
528 static bool update_mapping(struct int_map *map, struct bucket *neighborhood,  in update_mapping()  argument
531 	struct bucket *bucket = search_hop_list(map, neighborhood, key, NULL);  in update_mapping()
534 		/* There is no bucket containing the key in the neighborhood. */  in update_mapping()
543 		*old_value_ptr = bucket->value;  in update_mapping()
545 		bucket->value = new_value;  in update_mapping()
550  * find_or_make_vacancy() - Find an empty bucket.
551  * @map: The int_map to search or modify.
555  * Find an empty bucket in a specified neighborhood for a new mapping or attempt to re-arrange
562 static struct bucket *find_or_make_vacancy(struct int_map *map,  in find_or_make_vacancy()  argument
566 	struct bucket *hole = find_empty_bucket(map, neighborhood, MAX_PROBES);  in find_or_make_vacancy()
573 		int distance = hole - neighborhood;  in find_or_make_vacancy()
587 		hole = move_empty_bucket(map, hole);  in find_or_make_vacancy()
594  * vdo_int_map_put() - Try to associate a value with an integer.
595  * @map: The int_map to attempt to modify.
600  *                 or NULL if the map did not contain the key; NULL may be provided if the caller
603  * Try to associate a value (a pointer) with an integer in an int_map. If the map already contains
605  * update is true. In either case the old value is returned. If the map does not already contain a
610 int vdo_int_map_put(struct int_map *map, u64 key, void *new_value, bool update,  in vdo_int_map_put()  argument
616 		return -EINVAL;  in vdo_int_map_put()
622 	neighborhood = select_bucket(map, key);  in vdo_int_map_put()
628 	if (update_mapping(map, neighborhood, key, new_value, update, old_value_ptr))  in vdo_int_map_put()
632 	 * Find an empty bucket in the desired neighborhood for the new entry or re-arrange entries  in vdo_int_map_put()
633 	 * in the map so there is such a bucket. This operation will usually succeed; the loop body  in vdo_int_map_put()
634 	 * will only be executed on the rare occasions that we have to resize the map.  in vdo_int_map_put()
636 	while ((bucket = find_or_make_vacancy(map, neighborhood)) == NULL) {  in vdo_int_map_put()
640 		 * There is no empty bucket in which to put the new entry in the current map, so  in vdo_int_map_put()
641 		 * we're forced to allocate a new bucket array with a larger capacity, re-hash all  in vdo_int_map_put()
645 		result = resize_buckets(map);  in vdo_int_map_put()
650 		 * Resizing the map invalidates all pointers to buckets, so recalculate the  in vdo_int_map_put()
653 		neighborhood = select_bucket(map, key);  in vdo_int_map_put()
657 	bucket->key = key;  in vdo_int_map_put()
658 	bucket->value = new_value;  in vdo_int_map_put()
660 	map->size += 1;  in vdo_int_map_put()
662 	/* There was no existing entry, so there was no old value to be returned. */  in vdo_int_map_put()
669  * vdo_int_map_remove() - Remove the mapping for a given key from the int_map.
670  * @map: The int_map from which to remove the mapping.
675 void *vdo_int_map_remove(struct int_map *map, u64 key)  in vdo_int_map_remove()  argument
680 	struct bucket *bucket = select_bucket(map, key);  in vdo_int_map_remove()
682 	struct bucket *victim = search_hop_list(map, bucket, key, &previous);  in vdo_int_map_remove()
685 		/* There is no matching entry to remove. */  in vdo_int_map_remove()
692 	map->size -= 1;  in vdo_int_map_remove()
693 	value = victim->value;  in vdo_int_map_remove()
694 	victim->value = NULL;  in vdo_int_map_remove()
695 	victim->key = 0;  in vdo_int_map_remove()
700 		bucket->first_hop = victim->next_hop;  in vdo_int_map_remove()
702 		previous->next_hop = victim->next_hop;  in vdo_int_map_remove()
705 	victim->next_hop = NULL_HOP_OFFSET;  in vdo_int_map_remove()