9  * Hash Locks:
17  * Hash_locks are assigned to hash_zones by computing a modulus on the hash itself. Each hash_zone
49  * lock, releasing the hash_lock itself back to the hash zone (BYPASSING).
74  * on the hash zone thread.  finish_locking() is called by (or continued via callback from) the
97  * to DEDUPE_CONTEXT_COMPLETE, and the associated data_vio will be enqueued to run back in the hash
219 	/* The block hash covered by this lock */
220 	struct uds_record_name hash;  member
298 	/* The hash zones themselves */
324 			    "%s called on hash zone thread", name);  in assert_in_hash_zone()
338  * return_hash_lock_to_pool() - (Re)initialize a hash lock and return it to its pool.
367  * hash_lock_key() - Return hash_lock's record name as a hash code.
368  * @lock: The hash lock.
374 	return get_unaligned_le64(&lock->hash.name);  in hash_lock_key()
378  * get_hash_lock_state_name() - Get the string representation of a hash lock state.
379  * @state: The hash lock state.
391  * assert_hash_lock_agent() - Assert that a data_vio is the agent of its hash lock, and that this
392  *                            is being called in the hash zone.
398 	/* Not safe to access the agent field except from the hash zone. */  in assert_hash_lock_agent()
401 			    "%s must be for the hash lock agent", where);  in assert_hash_lock_agent()
405  * set_duplicate_lock() - Set the duplicate lock held by a hash lock. May only be called in the
407  * @hash_lock: The hash lock to update.
413 			    "hash lock must not already hold a duplicate lock");  in set_duplicate_lock()
430  * set_hash_lock() - Set, change, or clear the hash lock a data_vio is using.
432  * @new_lock: The hash lock the data_vio is joining.
434  * Updates the hash lock (or locks) to reflect the change in membership.
442 				    "must have a hash zone when holding a hash lock");  in set_hash_lock()
444 				    "must be on a hash lock list when holding a hash lock");  in set_hash_lock()
446 				    "hash lock reference must be counted");  in set_hash_lock()
455 					    "hash locks should only become unreferenced in a terminal state, not state %s",  in set_hash_lock()
489  *                    longer needed to be an agent for the hash lock.
494 	/* Release the hash lock now, saving a thread transition in cleanup. */  in exit_hash_lock()
518  *                       make the retired agent exit the hash lock.
519  * @lock: The hash lock to update.
537  * @lock: The hash lock on which to wait.
574  * start_bypassing() - Stop using the hash lock.
575  * @lock: The hash lock.
578  * Stops using the hash lock. This is the final transition for hash locks which did not get an
637 			    "must have released the duplicate lock for the hash lock");  in finish_unlocking()
658 		 * UNLOCKING -> LOCKING transition: A new data_vio entered the hash lock while the  in finish_unlocking()
683  * hash zone thread.
707  * @lock: The hash lock.
788  * @lock: The hash lock.
805  *                     by the hash lock.
806  * @lock: The hash lock.
828 	/* The hash lock must have an agent for all other lock states. */  in finish_deduping()
835 		 * was another change in location, but with only this data_vio using the hash lock,  in finish_deduping()
842 		 * location so the hash lock itself can be released (contingent on no new data_vios  in finish_deduping()
851  * @zone: The zone responsible for the hash.
852  * @hash: The hash to lock.
853  * @replace_lock: If non-NULL, the lock already registered for the hash which should be replaced by
855  * @lock_ptr: A pointer to receive the hash lock.
857  * Gets the lock for the hash (record name) of the data in a data_vio, or if one does not exist (or
858  * if we are explicitly rolling over), initialize a new lock for the hash and register it in the
864 				     const struct uds_record_name *hash,  in acquire_lock()  argument
876 			    "never need to wait for a free hash lock");  in acquire_lock()
884 	 * Fill in the hash of the new lock so we can map it, since we have to use the hash as the  in acquire_lock()
887 	new_lock->hash = *hash;  in acquire_lock()
910 		/* There's already a lock for the hash, so we don't need the borrowed lock. */  in acquire_lock()
919  * enter_forked_lock() - Bind the data_vio to a new hash lock.
921  * Implements waiter_callback_fn. Binds the data_vio that was waiting to a new hash lock and waits
934  * fork_hash_lock() - Fork a hash lock because it has run out of increments on the duplicate PBN.
935  * @old_lock: The hash lock to fork.
938  * Transfers the new agent and any lock waiters to a new hash lock instance which takes the place
972  * @lock: The hash lock.
973  * @data_vio: The data_vio to deduplicate using the hash lock.
976  * If no increments are available, this will roll over to a new hash lock and launch the data_vio
995  * start_deduping() - Enter the hash lock state where data_vios deduplicate in parallel against a
997  * @lock: The hash lock.
1002  * from the duplicate lock, ensuring the hash lock will still have a data_vio holding it.
1060 	 * Must only be mutated on the hash zone thread. Prevents any compiler shenanigans from  in increment_stat()
1182  * @lock: The hash lock (must be LOCKING).
1185  * Continue the deduplication path for a hash lock by using the agent to read (and possibly
1187  * to verify that the candidate is identical to all the data_vios sharing the hash. If so, it can
1200 	VDO_ASSERT_LOG_ONLY(!lock->verified, "hash lock only verifies advice once");  in start_verifying()
1299  *              behalf of its hash lock.
1303  * to finish_locking() on the hash zone thread.
1360 		 * writing on behalf of our hash lock, but that's impossible since we're the lock  in lock_duplicate_pbn()
1369 		 * hash, and finally arrive in the hash lock. We lose a chance to avoid a UDS  in lock_duplicate_pbn()
1371 		 * allocated to a data_vio with the same hash. There's also a chance to save on a  in lock_duplicate_pbn()
1388 		 * rights to acquire all those references. Those rights will be claimed by hash  in lock_duplicate_pbn()
1395 	 * We've successfully acquired a read lock on behalf of the hash lock, so mark it as such.  in lock_duplicate_pbn()
1400 	 * TODO: Optimization: We could directly launch the block verify, then switch to a hash  in lock_duplicate_pbn()
1407  * start_locking() - Continue deduplication for a hash lock that has obtained valid advice of a
1409  * @lock: The hash lock (currently must be QUERYING).
1431  * @lock: The hash lock, which must be in state WRITING.
1439  * agent either exits (and later tears down the hash lock), or it remains the agent and updates
1473 	 * being able to release the hash lock (or just release it).  in finish_writing()
1501  * @lock: The hash lock to modify.
1548  * @lock: The hash lock (currently must be QUERYING).
1551  * Begins the non-duplicate write path for a hash lock that had no advice, selecting a data_vio
1588 	 * return to the hash lock via vdo_continue_hash_lock() and call finish_writing().  in start_writing()
1676 		 * QUERYING agent to start the hash lock on the unverified dedupe path, verifying  in finish_querying()
1695  * start_querying() - Start deduplication for a hash lock.
1696  * @lock: The initialized hash lock.
1699  * Starts deduplication for a hash lock that has finished initializing by making the data_vio that
1717  * @lock: The hash lock.
1722 	VDO_ASSERT_LOG_ONLY(false, "hash lock must not be in unimplemented state %s",  in report_bogus_lock_state()
1730  * @completion: The data_vio completion to continue processing in its hash lock.
1732  * Asynchronously continue processing a data_vio in its hash lock after it has finished writing,
1733  * compressing, or deduplicating, so it can share the result with any data_vios waiting in the hash
1736  * Context: This must only be called in the correct thread for the hash zone.
1775  * is_hash_collision() - Check to see if a hash collision has occurred.
1780  * share the lock, which should only be possible in the extremely unlikely case of a hash
1813 			    "must not already hold a hash lock");  in assert_hash_lock_preconditions()
1818 			    "must not already be a member of a hash lock list");  in assert_hash_lock_preconditions()
1823 			  "must not hold a recovery lock when getting a hash lock");  in assert_hash_lock_preconditions()
1830  * Acquire or share a lock on the hash (record name) of the data in a data_vio, updating the
1832  * the unlikely case of a hash collision, this function will succeed, but the data_vio will not get
1857 		 * Hash collisions are extremely unlikely, but the bogus dedupe would be a data  in vdo_acquire_hash_lock()
1899  * vdo_release_hash_lock() - Release a data_vio's share of a hash lock, if held, and null out the
1901  * @data_vio: The data_vio releasing its hash lock.
1904  * by the hash lock (such as a PBN read lock on a block containing data with the same hash) and
1905  * returns the lock to the hash zone's lock pool.
1907  * Context: This must only be called in the correct thread for the hash zone.
1931 				    "hash lock being released must have been mapped");  in vdo_release_hash_lock()
1934 				    "unregistered hash lock must not be in the lock map");  in vdo_release_hash_lock()
1938 			    "hash lock returned to zone must have no waiters");  in vdo_release_hash_lock()
1940 			    "hash lock returned to zone must not reference a PBN lock");  in vdo_release_hash_lock()
1942 			    "returned hash lock must not be in use with state %s",  in vdo_release_hash_lock()
1945 			    "hash lock returned to zone must not be in a pool list");  in vdo_release_hash_lock()
1947 			    "hash lock returned to zone must not reference DataVIOs");  in vdo_release_hash_lock()
1954  *                              data_vio's hash lock, converting it to a duplicate PBN lock.
1981  * vdo_share_compressed_write_lock() - Make a data_vio's hash lock a shared holder of the PBN lock
2149  * @zones: the hash zones.
2230 		 * This query has not timed out, so send its data_vio back to its hash zone to  in finish_index_operation()
2402  * vdo_make_hash_zones() - Create the hash zones.
2462  * vdo_free_hash_zones() - Free the hash zones.
2511  * suspend_index() - Suspend the UDS index prior to draining hash zones.
2535  * drain_hash_zone() - Drain a hash zone.
2549 /** vdo_drain_hash_zones() - Drain all hash zones. */
2574  * resume_index() - Resume the UDS index prior to resuming hash zones.
2606  * resume_hash_zone() - Resume a hash zone.
2619  * vdo_resume_hash_zones() - Resume a set of hash zones.
2620  * @zones: The hash zones to resume.
2635  * get_hash_zone_statistics() - Add the statistics for this hash zone to the tally for all zones.
2636  * @zone: The hash zone to query.
2682  * vdo_get_dedupe_statistics() - Tally the statistics from all the hash zones and the UDS index.
2683  * @zones: The hash zones to query
2686  * Return: The sum of the hash lock statistics from all hash zones plus the statistics from the UDS
2708  * vdo_select_hash_zone() - Select the hash zone responsible for locking a given record name.
2712  * Return: The hash zone responsible for the record name.
2718 	 * Use a fragment of the record name as a hash code. Eight bits of hash should suffice  in vdo_select_hash_zone()
2719 	 * since the number of hash zones is small.  in vdo_select_hash_zone()
2722 	u32 hash = name->name[0];  in vdo_select_hash_zone()  local
2725 	 * Scale the 8-bit hash fragment to a zone index by treating it as a binary fraction and  in vdo_select_hash_zone()
2726 	 * multiplying that by the zone count. If the hash is uniformly distributed over [0 ..  in vdo_select_hash_zone()
2727 	 * 2^8-1], then (hash * count / 2^8) should be uniformly distributed over [0 .. count-1].  in vdo_select_hash_zone()
2730 	hash = (hash * zones->zone_count) >> 8;  in vdo_select_hash_zone()
2731 	return &zones->zones[hash];  in vdo_select_hash_zone()
2737  * @lock: The hash lock to dump.
2779  * dump_hash_zone() - Dump information about a hash zone to the log for debugging.
2798  * vdo_dump_hash_zones() - Dump information about the hash zones to the log for debugging.
2859  * @zone: the hash zone