md/dm-vdo/int-map.c

16  * probing, all the entries that hash to a given bucket are stored within a fixed neighborhood
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
27  * upper bound (the size of the neighborhood). Those entries occupy a small number of memory cache
35  * scheme which is used by this implementation. Since the entries in the neighborhood are within N
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.
60 #define NEIGHBORHOOD 255    /* the number of buckets in each neighborhood */
75 	 * @first_hop: The biased offset of the first entry in the hop list of the neighborhood
163 	 * Allocate NEIGHBORHOOD - 1 extra buckets so the last bucket can have a full neighborhood
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.
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)
250 	return &neighborhood[hop_offset - 1];
254  * insert_in_hop_list() - Add a bucket into the hop list for the neighborhood.
255  * @neighborhood: The first bucket in the neighborhood.
260 static void insert_in_hop_list(struct bucket *neighborhood, struct bucket *new_bucket)
263 	int hop_offset = 1 + (new_bucket - neighborhood);
266 	int next_hop = neighborhood->first_hop;
270 		neighborhood->first_hop = hop_offset;
276 		struct bucket *bucket = dereference_hop(neighborhood, next_hop);
456 	 * Examine every neighborhood that the empty bucket is part of, starting with the one in
466 		 * the hash bucket whose neighborhood is full.
472 			 * There are no buckets in this neighborhood that are in use by this one
486 		 * We've found an entry in this neighborhood that we can "hop" further away, moving
487 		 * the hole closer to the hash bucket, if not all the way into its neighborhood.
502 		/* Insert the filled hole into the hop list for the neighborhood. */
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,
525 	struct bucket *bucket = search_hop_list(neighborhood, key, NULL);
528 		/* There is no bucket containing the key in the neighborhood. */
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
551  * is not available or could not be relocated to the neighborhood.
553  * Return: a pointer to an empty bucket in the desired neighborhood, or NULL if a vacancy could not
557 					   struct bucket *neighborhood)
559 	/* Probe within and beyond the neighborhood for the first empty bucket. */
560 	struct bucket *hole = find_empty_bucket(map, neighborhood, MAX_PROBES);
563 	 * Keep trying until the empty bucket is in the bucket's neighborhood or we are unable to
567 		int distance = hole - neighborhood;
578 		 * The nearest empty bucket isn't within the neighborhood that must contain the new
607 	struct bucket *neighborhood, *bucket;
613 	 * Select the bucket at the start of the neighborhood that must contain any entry for the
616 	neighborhood = select_bucket(map, key);
619 	 * Check whether the neighborhood already contains an entry for the key, in which case we
622 	if (update_mapping(neighborhood, key, new_value, update, old_value_ptr))
626 	 * Find an empty bucket in the desired neighborhood for the new entry or re-arrange entries
630 	while ((bucket = find_or_make_vacancy(map, neighborhood)) == NULL) {
645 		 * neighborhood pointer.
647 		neighborhood = select_bucket(map, key);
650 	/* Put the new entry in the empty bucket, adding it to the neighborhood. */
653 	insert_in_hop_list(neighborhood, bucket);