md/dm-vdo/dedupe.c

15  * index query is needed for each hash_lock, instead of one for every data_vio.
28  * In all states except DEDUPING, there is a single data_vio, called the lock agent, performing the
30  * lock if the lock is shared by more than one data_vio. data_vios waiting to deduplicate are kept
34  * the last data_vio in the lock calls back in DEDUPING, it becomes the agent and the lock becomes
48  * lock on the duplicate block (UNLOCKING), and if the agent is the last data_vio referencing the
60  * When there are not enough available reference count increments available on a PBN for a data_vio
90  * reference to the data_vio on behalf of which they are performing a query.
97  * to DEDUPE_CONTEXT_COMPLETE, and the associated data_vio will be enqueued to run back in the hash
266 	/* The data_vio designated to act on behalf of the lock */
267 	struct data_vio *agent;
357  * vdo_get_duplicate_lock() - Get the PBN lock on the duplicate data location for a data_vio from
358  *                            the hash_lock the data_vio holds (if there is one).
359  * @data_vio: The data_vio to query.
361  * Return: The PBN lock on the data_vio's duplicate location.
363 struct pbn_lock *vdo_get_duplicate_lock(struct data_vio *data_vio)
365 	if (data_vio->hash_lock == NULL)
368 	return data_vio->hash_lock->duplicate_lock;
396  * assert_hash_lock_agent() - Assert that a data_vio is the agent of its hash lock, and that this
398  * @data_vio: The data_vio expected to be the lock agent.
401 static void assert_hash_lock_agent(struct data_vio *data_vio, const char *where)
404 	assert_data_vio_in_hash_zone(data_vio);
405 	VDO_ASSERT_LOG_ONLY(data_vio == data_vio->hash_lock->agent,
424  * dequeue_lock_waiter() - Remove the first data_vio from the lock's waitq and return it.
429 static inline struct data_vio *dequeue_lock_waiter(struct hash_lock *lock)
435  * set_hash_lock() - Set, change, or clear the hash lock a data_vio is using.
436  * @data_vio: The data_vio to update.
437  * @new_lock: The hash lock the data_vio is joining.
441 static void set_hash_lock(struct data_vio *data_vio, struct hash_lock *new_lock)
443 	struct hash_lock *old_lock = data_vio->hash_lock;
446 		VDO_ASSERT_LOG_ONLY(data_vio->hash_zone != NULL,
448 		VDO_ASSERT_LOG_ONLY(!list_empty(&data_vio->hash_lock_entry),
464 		list_del_init(&data_vio->hash_lock_entry);
467 		data_vio->hash_lock = NULL;
475 		list_move_tail(&data_vio->hash_lock_entry, &new_lock->duplicate_ring);
480 		data_vio->hash_lock = new_lock;
485 static void start_deduping(struct hash_lock *lock, struct data_vio *agent,
487 static void start_locking(struct hash_lock *lock, struct data_vio *agent);
488 static void start_writing(struct hash_lock *lock, struct data_vio *agent);
490 static void transfer_allocation_lock(struct data_vio *data_vio);
495  * @data_vio: The data_vio to complete and send to be cleaned up.
497 static void exit_hash_lock(struct data_vio *data_vio)
500 	vdo_release_hash_lock(data_vio);
502 	/* Complete the data_vio and start the clean-up path to release any locks it still holds. */
503 	data_vio->vio.completion.callback = complete_data_vio;
505 	continue_data_vio(data_vio);
509  * set_duplicate_location() - Set the location of the duplicate block for data_vio, updating the
511  * @data_vio: The data_vio to modify.
514 static void set_duplicate_location(struct data_vio *data_vio,
517 	data_vio->is_duplicate = (source.pbn != VDO_ZERO_BLOCK);
518 	data_vio->duplicate = source;
528 static struct data_vio *retire_lock_agent(struct hash_lock *lock)
530 	struct data_vio *old_agent = lock->agent;
531 	struct data_vio *new_agent = dequeue_lock_waiter(lock);
541  * wait_on_hash_lock() - Add a data_vio to the lock's queue of waiters.
543  * @data_vio: The data_vio to add to the queue.
545 static void wait_on_hash_lock(struct hash_lock *lock, struct data_vio *data_vio)
547 	vdo_waitq_enqueue_waiter(&lock->waiters, &data_vio->waiter);
551 	 * one other data_vio waiting on it.
563 	data_vio->compression.lock_holder = lock->agent;
564 	launch_data_vio_packer_callback(data_vio, vdo_remove_lock_holder_from_packer);
570  * @waiter: The data_vio's waiter link.
581  * @agent: The data_vio acting as the agent for the lock.
586 static void start_bypassing(struct hash_lock *lock, struct data_vio *agent)
592 void vdo_clean_failed_hash_lock(struct data_vio *data_vio)
594 	struct hash_lock *lock = data_vio->hash_lock;
597 		exit_hash_lock(data_vio);
602 		lock->agent = data_vio;
603 	} else if (data_vio != lock->agent) {
604 		exit_hash_lock(data_vio);
617 		data_vio->duplicate = lock->duplicate;
618 		launch_data_vio_duplicate_zone_callback(data_vio, unlock_duplicate_pbn);
623 	data_vio->is_duplicate = false;
624 	exit_hash_lock(data_vio);
630  * @completion: The completion of the data_vio acting as the lock's agent.
636 	struct data_vio *agent = as_data_vio(completion);
663 		 * UNLOCKING -> LOCKING transition: A new data_vio entered the hash lock while the
685  * @completion: The completion of the data_vio acting as the lock's agent.
692 	struct data_vio *agent = as_data_vio(completion);
713  * @agent: The data_vio currently acting as the agent for the lock.
715 static void start_unlocking(struct hash_lock *lock, struct data_vio *agent)
729 static void process_update_result(struct data_vio *agent)
742  * @completion: The completion of the data_vio that performed the update
748 	struct data_vio *agent = as_data_vio(completion);
763 		 * UPDATING -> DEDUPING transition: A new data_vio arrived during the UDS update.
787 static void query_index(struct data_vio *data_vio, enum uds_request_type operation);
793  * @agent: The data_vio currently acting as the agent for the lock.
795 static void start_updating(struct hash_lock *lock, struct data_vio *agent)
808  * finish_deduping() - Handle a data_vio that has finished deduplicating against the block locked
811  * @data_vio: The lock holder that has finished deduplicating.
813  * If there are other data_vios still sharing the lock, this will just release the data_vio's share
814  * of the lock and finish processing the data_vio. If this is the last data_vio holding the lock,
815  * this makes the data_vio the lock agent and uses it to advance the state of the lock so it can
818 static void finish_deduping(struct hash_lock *lock, struct data_vio *data_vio)
820 	struct data_vio *agent = data_vio;
828 		exit_hash_lock(data_vio);
839 		 * was another change in location, but with only this data_vio using the hash lock,
861  * Gets the lock for the hash (record name) of the data in a data_vio, or if one does not exist (or
923  * enter_forked_lock() - Bind the data_vio to a new hash lock.
925  * Implements waiter_callback_fn. Binds the data_vio that was waiting to a new hash lock and waits
930 	struct data_vio *data_vio = vdo_waiter_as_data_vio(waiter);
933 	set_hash_lock(data_vio, new_lock);
934 	wait_on_hash_lock(new_lock, data_vio);
940  * @new_agent: The data_vio that will be the agent for the new lock.
945 static void fork_hash_lock(struct hash_lock *old_lock, struct data_vio *new_agent)
974  * launch_dedupe() - Reserve a reference count increment for a data_vio and launch it on the dedupe
977  * @data_vio: The data_vio to deduplicate using the hash lock.
978  * @has_claim: true if the data_vio already has claimed an increment from the duplicate lock.
980  * If no increments are available, this will roll over to a new hash lock and launch the data_vio
983 static void launch_dedupe(struct hash_lock *lock, struct data_vio *data_vio,
988 		fork_hash_lock(lock, data_vio);
993 	set_duplicate_location(data_vio, lock->duplicate);
994 	data_vio->new_mapped = data_vio->duplicate;
995 	update_metadata_for_data_vio_write(data_vio, lock->duplicate_lock);
1002  * @agent: The data_vio acting as the agent for the lock.
1006  * from the duplicate lock, ensuring the hash lock will still have a data_vio holding it.
1008 static void start_deduping(struct hash_lock *lock, struct data_vio *agent,
1073  * @completion: The completion of the data_vio used to verify dedupe
1079 	struct data_vio *agent = as_data_vio(completion);
1140 	struct data_vio *agent = as_data_vio(completion);
1148 	struct data_vio *agent = as_data_vio(completion);
1164 	struct data_vio *agent = vio_as_data_vio(bio->bi_private);
1187  * @agent: The data_vio to use to read and compare candidate data.
1192  * be deduplicated against, otherwise a data_vio allocation will have to be written to and used for
1195 static void start_verifying(struct hash_lock *lock, struct data_vio *agent)
1222  * @completion: The completion of the data_vio that attempted to get the read lock.
1228 	struct data_vio *agent = as_data_vio(completion);
1280 static bool acquire_provisional_reference(struct data_vio *agent, struct pbn_lock *lock,
1302  * @completion: The completion of the data_vio attempting to acquire the physical block lock on
1315 	struct data_vio *agent = as_data_vio(completion);
1367 		 * 3a) If the lock is held by a data_vio with different data, the advice is already
1370 		 * 3b) If the lock is held by a data_vio that matches us, we may as well either
1375 		 * allocated to a data_vio with the same hash. There's also a chance to save on a
1414  * @agent: The data_vio bearing the dedupe advice.
1416 static void start_locking(struct hash_lock *lock, struct data_vio *agent)
1436  * @agent: The data_vio that wrote its data for the lock.
1446 static void finish_writing(struct hash_lock *lock, struct data_vio *agent)
1504  * select_writing_agent() - Search through the lock waiters for a data_vio that has an allocation.
1510 static struct data_vio *select_writing_agent(struct hash_lock *lock)
1513 	struct data_vio *data_vio;
1521 	while (((data_vio = dequeue_lock_waiter(lock)) != NULL) &&
1522 	       !data_vio_has_allocation(data_vio)) {
1524 		vdo_waitq_enqueue_waiter(&temp_queue, &data_vio->waiter);
1527 	if (data_vio != NULL) {
1539 		lock->agent = data_vio;
1542 		data_vio = lock->agent;
1547 	return data_vio;
1553  * @agent: The data_vio currently acting as the agent for the lock.
1555  * Begins the non-duplicate write path for a hash lock that had no advice, selecting a data_vio
1556  * with an allocation as a new agent, if necessary, then resuming the agent on the data_vio write
1559 static void start_writing(struct hash_lock *lock, struct data_vio *agent)
1604 	struct data_vio *data_vio = context->requestor;
1607 	struct vdo *vdo = vdo_from_data_vio(data_vio);
1608 	struct zoned_pbn *advice = &data_vio->duplicate;
1630 			      (unsigned long long) data_vio->logical.lbn);
1639 			      (unsigned long long) data_vio->logical.lbn);
1647 static void process_query_result(struct data_vio *agent)
1662  * @completion: The completion of the data_vio that performed the query.
1668 	struct data_vio *agent = as_data_vio(completion);
1700  * @data_vio: The data_vio that has just obtained the new lock.
1702  * Starts deduplication for a hash lock that has finished initializing by making the data_vio that
1706 static void start_querying(struct hash_lock *lock, struct data_vio *data_vio)
1708 	lock->agent = data_vio;
1710 	data_vio->last_async_operation = VIO_ASYNC_OP_CHECK_FOR_DUPLICATION;
1711 	set_data_vio_hash_zone_callback(data_vio, finish_querying);
1712 	query_index(data_vio,
1713 		    (data_vio_has_allocation(data_vio) ? UDS_POST : UDS_QUERY));
1717  * report_bogus_lock_state() - Complain that a data_vio has entered a hash_lock that is in an
1718  *                             unimplemented or unusable state and continue the data_vio with an
1721  * @data_vio: The data_vio attempting to enter the lock.
1723 static void report_bogus_lock_state(struct hash_lock *lock, struct data_vio *data_vio)
1727 	continue_data_vio_with_error(data_vio, VDO_LOCK_ERROR);
1733  * @data_vio: The data_vio to continue processing in its hash lock.
1735  * Asynchronously continue processing a data_vio in its hash lock after it has finished writing,
1743 	struct data_vio *data_vio = as_data_vio(completion);
1744 	struct hash_lock *lock = data_vio->hash_lock;
1748 		VDO_ASSERT_LOG_ONLY(data_vio == lock->agent,
1750 		finish_writing(lock, data_vio);
1754 		finish_deduping(lock, data_vio);
1758 		/* This data_vio has finished the write path and the lock doesn't need it. */
1759 		exit_hash_lock(data_vio);
1769 		report_bogus_lock_state(lock, data_vio);
1773 		report_bogus_lock_state(lock, data_vio);
1780  * @candidate: The data_vio seeking to share the lock.
1782  * Check whether the data in data_vios sharing a lock is different than in a data_vio seeking to
1786  * Return: true if the given data_vio must not share the lock because it doesn't have the same data
1789 static bool is_hash_collision(struct hash_lock *lock, struct data_vio *candidate)
1791 	struct data_vio *lock_holder;
1798 	lock_holder = list_first_entry(&lock->duplicate_ring, struct data_vio,
1810 static inline int assert_hash_lock_preconditions(const struct data_vio *data_vio)
1815 	result = VDO_ASSERT(data_vio->hash_lock == NULL,
1820 	result = VDO_ASSERT(list_empty(&data_vio->hash_lock_entry),
1825 	return VDO_ASSERT(data_vio->recovery_sequence_number == 0,
1831  * @data_vio: The data_vio acquiring a lock on its record name.
1833  * Acquire or share a lock on the hash (record name) of the data in a data_vio, updating the
1834  * data_vio to reference the lock. This must only be called in the correct thread for the zone. In
1835  * the unlikely case of a hash collision, this function will succeed, but the data_vio will not get
1840 	struct data_vio *data_vio = as_data_vio(completion);
1844 	assert_data_vio_in_hash_zone(data_vio);
1846 	result = assert_hash_lock_preconditions(data_vio);
1848 		continue_data_vio_with_error(data_vio, result);
1852 	result = acquire_lock(data_vio->hash_zone, &data_vio->record_name, NULL, &lock);
1854 		continue_data_vio_with_error(data_vio, result);
1858 	if (is_hash_collision(lock, data_vio)) {
1861 		 * corruption. Bypass optimization entirely. We can't compress a data_vio without
1865 		write_data_vio(data_vio);
1869 	set_hash_lock(data_vio, lock);
1872 		start_querying(lock, data_vio);
1882 		wait_on_hash_lock(lock, data_vio);
1887 		vdo_release_hash_lock(data_vio);
1888 		write_data_vio(data_vio);
1892 		launch_dedupe(lock, data_vio, false);
1897 		report_bogus_lock_state(lock, data_vio);
1902  * vdo_release_hash_lock() - Release a data_vio's share of a hash lock, if held, and null out the
1903  *                           data_vio's reference to it.
1904  * @data_vio: The data_vio releasing its hash lock.
1906  * If the data_vio is the only one holding the lock, this also releases any resources or locks used
1912 void vdo_release_hash_lock(struct data_vio *data_vio)
1915 	struct hash_lock *lock = data_vio->hash_lock;
1916 	struct hash_zone *zone = data_vio->hash_zone;
1921 	set_hash_lock(data_vio, NULL);
1956  * transfer_allocation_lock() - Transfer a data_vio's downgraded allocation PBN lock to the
1957  *                              data_vio's hash lock, converting it to a duplicate PBN lock.
1958  * @data_vio: The data_vio holding the allocation lock to transfer.
1960 static void transfer_allocation_lock(struct data_vio *data_vio)
1962 	struct allocation *allocation = &data_vio->allocation;
1963 	struct hash_lock *hash_lock = data_vio->hash_lock;
1965 	VDO_ASSERT_LOG_ONLY(data_vio->new_mapped.pbn == allocation->pbn,
1973 	hash_lock->duplicate = data_vio->new_mapped;
1974 	data_vio->duplicate = data_vio->new_mapped;
1984  * vdo_share_compressed_write_lock() - Make a data_vio's hash lock a shared holder of the PBN lock
1986  * @data_vio: The data_vio which was just compressed.
1990  * read lock. This also reserves a reference count increment for the data_vio.
1992 void vdo_share_compressed_write_lock(struct data_vio *data_vio,
1997 	VDO_ASSERT_LOG_ONLY(vdo_get_duplicate_lock(data_vio) == NULL,
1999 	VDO_ASSERT_LOG_ONLY(vdo_is_state_compressed(data_vio->new_mapped.state),
2001 	assert_data_vio_in_new_mapped_zone(data_vio);
2008 	 * Get a share of the PBN lock, ensuring it cannot be released until after this data_vio
2011 	data_vio->duplicate = data_vio->new_mapped;
2012 	data_vio->hash_lock->duplicate = data_vio->new_mapped;
2013 	set_duplicate_lock(data_vio->hash_lock, pbn_lock);
2016 	 * Claim a reference for this data_vio. Necessary since another hash_lock might start
2232 		 * This query has not timed out, so send its data_vio back to its hash zone to
2241 	 * data_vio has already moved on.
2883 static void prepare_uds_request(struct uds_request *request, struct data_vio *data_vio,
2886 	request->record_name = data_vio->record_name;
2893 		encoding->data[offset++] = data_vio->new_mapped.state;
2894 		put_unaligned_le64(data_vio->new_mapped.pbn, &encoding->data[offset]);
2901  * The index operation will inquire about data_vio.record_name, providing (if the operation is
2902  * appropriate) advice from the data_vio's new_mapped fields. The advice found in the index (or
2906 static void query_index(struct data_vio *data_vio, enum uds_request_type operation)
2910 	struct vdo *vdo = vdo_from_data_vio(data_vio);
2911 	struct hash_zone *zone = data_vio->hash_zone;
2913 	assert_data_vio_in_hash_zone(data_vio);
2916 		continue_data_vio(data_vio);
2923 		continue_data_vio(data_vio);
2927 	data_vio->dedupe_context = context;
2928 	context->requestor = data_vio;
2930 	prepare_uds_request(&context->request, data_vio, operation);