16  * probing, all the entries that hash to a given bucket are stored within a fixed neighborhood
17  * starting at that bucket. Chaining is effectively represented as a bit vector relative to each
18  * bucket instead of as pointers or explicit offsets.
20  * When an empty bucket cannot be found within a given neighborhood, subsequent neighborhoods are
22  * an empty bucket will move into the desired neighborhood, allowing the entry to be added. When
36  * entries of the hash bucket at the start of the neighborhood, a pair of small offset fields each
41  * in the list is always the bucket closest to the start of the neighborhood.
61 #define MAX_PROBES 1024     /* limit on the number of probes for a free bucket */
66  * struct bucket - hash bucket
73 struct bucket {  struct
76 	 *             that hashes to this bucket.
79 	/** @next_hop: The biased offset of the next bucket in the hop list. */  argument
81 	/** @key: The key stored in this bucket. */  argument
83 	/** @value: The value stored in this bucket (NULL if empty). */  argument
91  * bucket array, we allocate a few more buckets at the end of the array instead, which is why  argument
99 	/** @bucket_count: The number of buckets in the bucket array. */
102 	struct bucket *buckets;
163 	 * Allocate NEIGHBORHOOD - 1 extra buckets so the last bucket can have a full neighborhood  in allocate_buckets()
167 	return vdo_allocate(map->bucket_count, struct bucket,  in allocate_buckets()
236  * dereference_hop() - Convert a biased hop offset within a neighborhood to a pointer to the bucket
238  * @neighborhood: The first bucket in the neighborhood.
239  * @hop_offset: The biased hop offset to the desired bucket.
241  * Return: NULL if hop_offset is zero, otherwise a pointer to the bucket in the neighborhood at
244 static struct bucket *dereference_hop(struct bucket *neighborhood, unsigned int hop_offset)  in dereference_hop()
254  * insert_in_hop_list() - Add a bucket into the hop list for the neighborhood.
255  * @neighborhood: The first bucket in the neighborhood.
256  * @new_bucket: The bucket to add to the hop list.
258  * The bucket is inserted it into the list so the hop list remains sorted by hop offset.
260 static void insert_in_hop_list(struct bucket *neighborhood, struct bucket *new_bucket)  in insert_in_hop_list()
265 	/* Handle the special case of adding a bucket at the start of the list. */  in insert_in_hop_list()
276 		struct bucket *bucket = dereference_hop(neighborhood, next_hop);  in insert_in_hop_list()  local
278 		next_hop = bucket->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.
293 static struct bucket *select_bucket(const struct int_map *map, u64 key)  in select_bucket()
302 	 * Scale the 32-bit hash to a bucket index by treating it as a binary fraction and  in select_bucket()
311  * search_hop_list() - Search the hop list associated with given hash bucket for a given search
313  * @bucket: The map bucket to search for the key.
315  * @previous_ptr: Output. if not NULL, a pointer in which to store the bucket in the list preceding
318  * If the key is found, returns a pointer to the entry (bucket or collision), otherwise returns
323 static struct bucket *search_hop_list(struct bucket *bucket, u64 key,  in search_hop_list()  argument
324 				      struct bucket **previous_ptr)  in search_hop_list()
326 	struct bucket *previous = NULL;  in search_hop_list()
327 	unsigned int next_hop = bucket->first_hop;  in search_hop_list()
331 		 * Check the neighboring bucket indexed by the offset for the  in search_hop_list()
334 		struct bucket *entry = dereference_hop(bucket, next_hop);  in search_hop_list()
357 	struct bucket *match = search_hop_list(select_bucket(map, key), key, NULL);  in vdo_int_map_get()
389 	/* Populate the new hash table from the entries in the old bucket array. */  in resize_buckets()
391 		struct bucket *entry = &old_map.buckets[i];  in resize_buckets()
405 	/* Destroy the old bucket array. */  in resize_buckets()
411  * find_empty_bucket() - Probe the bucket array starting at the given bucket for the next empty
412  *                       bucket, returning a pointer to it.
414  * @bucket: The bucket at which to start probing.
417  * NULL will be returned if the search reaches the end of the bucket array or if the number of
420  * Return: The next empty bucket, or NULL if the search failed.
422 static struct bucket *
423 find_empty_bucket(struct int_map *map, struct bucket *bucket, unsigned int max_probes)  in find_empty_bucket()  argument
426 	 * Limit the search to either the nearer of the end of the bucket array or a fixed distance  in find_empty_bucket()
427 	 * beyond the initial bucket.  in find_empty_bucket()
429 	ptrdiff_t remaining = &map->buckets[map->bucket_count] - bucket;  in find_empty_bucket()
430 	struct bucket *sentinel = &bucket[min_t(ptrdiff_t, remaining, max_probes)];  in find_empty_bucket()
431 	struct bucket *entry;  in find_empty_bucket()
433 	for (entry = bucket; entry < sentinel; entry++) {  in find_empty_bucket()
442  * move_empty_bucket() - Move an empty bucket closer to the start of the bucket array.
443  * @hole: The empty bucket to fill with an entry that precedes it in one of its enclosing
446  * This searches the neighborhoods that contain the empty bucket for a non-empty bucket closer to
447  * the start of the array. If such a bucket is found, this swaps the two buckets by moving the
448  * entry to the empty bucket.
450  * Return: The bucket that was vacated by moving its entry to the provided hole, or NULL if no
453 static struct bucket *move_empty_bucket(struct bucket *hole)  in move_empty_bucket()
456 	 * Examine every neighborhood that the empty bucket is part of, starting with the one in  in move_empty_bucket()
457 	 * which it is the last bucket. No boundary check is needed for the negative array  in move_empty_bucket()
459 	 * deeper into the array than a valid bucket.  in move_empty_bucket()
461 	struct bucket *bucket;  in move_empty_bucket()  local
463 	for (bucket = &hole[1 - NEIGHBORHOOD]; bucket < hole; bucket++) {  in move_empty_bucket()
465 		 * Find the entry that is nearest to the bucket, which means it will be nearest to  in move_empty_bucket()
466 		 * the hash bucket whose neighborhood is full.  in move_empty_bucket()
468 		struct bucket *new_hole = dereference_hop(bucket, bucket->first_hop);  in move_empty_bucket()
479 		 * Skip this bucket if its first entry is actually further away than the hole that  in move_empty_bucket()
487 		 * the hole closer to the hash bucket, if not all the way into its neighborhood.  in move_empty_bucket()
491 		 * The entry that will be the new hole is the first bucket in the list, so setting  in move_empty_bucket()
494 		bucket->first_hop = new_hole->next_hop;  in move_empty_bucket()
503 		insert_in_hop_list(bucket, hole);  in move_empty_bucket()
514  * @neighborhood: The first bucket in the neighborhood that would contain the search key
522 static bool update_mapping(struct bucket *neighborhood, u64 key, void *new_value,  in update_mapping()
525 	struct bucket *bucket = search_hop_list(neighborhood, key, NULL);  in update_mapping()  local
527 	if (bucket == NULL) {  in update_mapping()
528 		/* There is no bucket containing the key in the neighborhood. */  in update_mapping()
537 		*old_value_ptr = bucket->value;  in update_mapping()
539 		bucket->value = new_value;  in update_mapping()
544  * find_or_make_vacancy() - Find an empty bucket.
546  * @neighborhood: The first bucket in the neighborhood in which an empty bucket is needed for a new
549  * Find an empty bucket in a specified neighborhood for a new mapping or attempt to re-arrange
550  * mappings so there is such a bucket. This operation may fail (returning NULL) if an empty bucket
553  * Return: a pointer to an empty bucket in the desired neighborhood, or NULL if a vacancy could not
556 static struct bucket *find_or_make_vacancy(struct int_map *map,  in find_or_make_vacancy()
557 					   struct bucket *neighborhood)  in find_or_make_vacancy()
559 	/* Probe within and beyond the neighborhood for the first empty bucket. */  in find_or_make_vacancy()
560 	struct bucket *hole = find_empty_bucket(map, neighborhood, MAX_PROBES);  in find_or_make_vacancy()
563 	 * Keep trying until the empty bucket is in the bucket's neighborhood or we are unable to  in find_or_make_vacancy()
564 	 * move it any closer by swapping it with a filled bucket.  in find_or_make_vacancy()
571 			 * We've found or relocated an empty bucket close enough to the initial  in find_or_make_vacancy()
572 			 * hash bucket to be referenced by its hop vector.  in find_or_make_vacancy()
578 		 * The nearest empty bucket isn't within the neighborhood that must contain the new  in find_or_make_vacancy()
579 		 * entry, so try to swap it with bucket that is closer.  in find_or_make_vacancy()
607 	struct bucket *neighborhood, *bucket;  in vdo_int_map_put()  local
613 	 * Select the bucket at the start of the neighborhood that must contain any entry for the  in vdo_int_map_put()
626 	 * Find an empty bucket in the desired neighborhood for the new entry or re-arrange entries  in vdo_int_map_put()
627 	 * in the map so there is such a bucket. This operation will usually succeed; the loop body  in vdo_int_map_put()
630 	while ((bucket = find_or_make_vacancy(map, neighborhood)) == NULL) {  in vdo_int_map_put()
634 		 * There is no empty bucket in which to put the new entry in the current map, so  in vdo_int_map_put()
635 		 * we're forced to allocate a new bucket array with a larger capacity, re-hash all  in vdo_int_map_put()
650 	/* Put the new entry in the empty bucket, adding it to the neighborhood. */  in vdo_int_map_put()
651 	bucket->key = key;  in vdo_int_map_put()
652 	bucket->value = new_value;  in vdo_int_map_put()
653 	insert_in_hop_list(neighborhood, bucket);  in vdo_int_map_put()
673 	/* Select the bucket to search and search it for an existing entry. */  in vdo_int_map_remove()
674 	struct bucket *bucket = select_bucket(map, key);  in vdo_int_map_remove()  local
675 	struct bucket *previous;  in vdo_int_map_remove()
676 	struct bucket *victim = search_hop_list(bucket, key, &previous);  in vdo_int_map_remove()
684 	 * We found an entry to remove. Save the mapped value to return later and empty the bucket.  in vdo_int_map_remove()
691 	/* The victim bucket is now empty, but it still needs to be spliced out of the hop list. */  in vdo_int_map_remove()
694 		bucket->first_hop = victim->next_hop;  in vdo_int_map_remove()