1 // SPDX-License-Identifier: GPL-2.0-only
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"
62 #define NULL_HOP_OFFSET 0   /* the hop offset value terminating the hop list */
66  * struct bucket - hash bucket
69  * tempting to encode the hop offsets separately and maintain alignment of key/value pairs, but
81 	/** @key: The key stored in this bucket. */
82 	u64 key;  member
83 	/** @value: The value stored in this bucket (NULL if empty). */
84 	void *value;  member
88  * struct int_map - The concrete definition of the opaque int_map type.
106  * mix() - The Google CityHash 16-byte hash mixing function.
107  * @input1: The first input value.
108  * @input2: The second input value.
127  * hash_key() - Calculate a 64-bit non-cryptographic hash value for the provided 64-bit integer
128  *              key.
129  * @key: The mapping key.
131  * The implementation is based on Google's CityHash, only handling the specific case of an 8-byte
134  * Return: The hash of the mapping key.
136 static u64 hash_key(u64 key)  in hash_key()  argument
145 	} pun = {.u64 = key};  in hash_key()
147 	return mix(sizeof(key) + (((u64) pun.u32[0]) << 3), pun.u32[1]);  in hash_key()
151  * allocate_buckets() - Initialize an int_map.
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.
209  * vdo_int_map_free() - Free an int_map.
220 	vdo_free(vdo_forget(map->buckets));  in vdo_int_map_free()
225  * vdo_int_map_size() - Get the number of entries stored in an int_map.
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.
291  * @key: The mapping key.
293 static struct bucket *select_bucket(const struct int_map *map, u64 key)  in select_bucket()  argument
296 	 * Calculate a good hash value for the provided key. We want exactly 32 bits, so mask the  in select_bucket()
299 	u64 hash = hash_key(key) & 0xFFFFFFFF;  in select_bucket()
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
312  *                     key.
314  * @bucket: The map bucket to search for the key.
315  * @key: The mapping key.
317  *                the one that had the matching key
319  * If the key is found, returns a pointer to the entry (bucket or collision), otherwise returns
322  * Return: An entry that matches the key, or NULL if not found.
326 				      u64 key,  in search_hop_list()  argument
330 	unsigned int next_hop = bucket->first_hop;  in search_hop_list()
335 		 * desired key.  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.
354  * @key: The key to look up.
356  * Return: The value associated with the given key, or NULL if the key is not mapped to any value.
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.
378 	/* Copy the top-level map data to the stack. */  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()
396 		if (entry->value == NULL)  in resize_buckets()
399 		result = vdo_int_map_put(map, entry->key, entry->value, true, NULL);  in resize_buckets()
402 			vdo_free(vdo_forget(map->buckets));  in resize_buckets()
414  * find_empty_bucket() - Probe the bucket array starting at the given bucket for the next empty
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.
450  * This searches the neighborhoods that contain the empty bucket for a non-empty bucket closer to
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()
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
518  *                    associated with the key in the provided pointer.
520  * @neighborhood: The first bucket in the neighborhood that would contain the search key
521  * @key: The key with which to associate the new value.
522  * @new_value: The value to be associated with the key.
523  * @update: Whether to overwrite an existing value.
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.
529 			   u64 key, void *new_value, bool update, void **old_value_ptr)  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()
539 	 * Return the value of the current mapping (if desired) and update the mapping with the new  in update_mapping()
540 	 * value (if desired).  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.
555  * Find an empty bucket in a specified neighborhood for a new mapping or attempt to re-arrange
573 		int distance = hole - neighborhood;  in find_or_make_vacancy()
594  * vdo_int_map_put() - Try to associate a value with an integer.
596  * @key: The key with which to associate the new value.
597  * @new_value: The value to be associated with the key.
598  * @update: Whether to overwrite an existing value.
599  * @old_value_ptr: A pointer in which to store either the old value (if the key was already mapped)
600  *                 or NULL if the map did not contain the key; NULL may be provided if the caller
601  *                 does not need to know the old value
603  * Try to associate a value (a pointer) with an integer in an int_map. If the map already contains
604  * a mapping for the provided key, the old value is only replaced with the specified value if
605  * update is true. In either case the old value is returned. If the map does not already contain a
606  * value for the specified key, the new value is added regardless of the value of update.
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()
620 	 * provided key.  in vdo_int_map_put()
622 	neighborhood = select_bucket(map, key);  in vdo_int_map_put()
625 	 * Check whether the neighborhood already contains an entry for the key, in which case we  in vdo_int_map_put()
626 	 * optionally update it, returning the old value.  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()
641 		 * we're forced to allocate a new bucket array with a larger capacity, re-hash all  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.
671  * @key: The key whose mapping is to be removed.
673  * Return: the value that was associated with the key, or NULL if it was not mapped.
675 void *vdo_int_map_remove(struct int_map *map, u64 key)  in vdo_int_map_remove()  argument
677 	void *value;  in vdo_int_map_remove()  local
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()
690 	 * We found an entry to remove. Save the mapped value to return later and empty the bucket.  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()
706 	return value;  in vdo_int_map_remove()