1	// SPDX-License-Identifier: GPL-2.0-only
2	/*
3	* Copyright (C) 2001-2002 Sistina Software (UK) Limited.
4	*
5	* This file is released under the GPL.
6	*/
7
8	#include <linux/blkdev.h>
9	#include <linux/device-mapper.h>
10	#include <linux/delay.h>
11	#include <linux/fs.h>
12	#include <linux/init.h>
13	#include <linux/kdev_t.h>
14	#include <linux/list.h>
15	#include <linux/list_bl.h>
16	#include <linux/mempool.h>
17	#include <linux/module.h>
18	#include <linux/slab.h>
19	#include <linux/vmalloc.h>
20	#include <linux/log2.h>
21	#include <linux/dm-kcopyd.h>
22
23	#include "dm.h"
24
25	#include "dm-exception-store.h"
26
27	#define DM_MSG_PREFIX "snapshots"
28
29	static const char dm_snapshot_merge_target_name[] = "snapshot-merge";
30
31	#define dm_target_is_snapshot_merge(ti) \
32	((ti)->type->name == dm_snapshot_merge_target_name)
33
34	/*
35	* The size of the mempool used to track chunks in use.
36	*/
37	#define MIN_IOS 256
38
39	#define DM_TRACKED_CHUNK_HASH_SIZE 16
40	#define DM_TRACKED_CHUNK_HASH(x) ((unsigned long)(x) & \
41	(DM_TRACKED_CHUNK_HASH_SIZE - 1))
42
43	struct dm_hlist_head {
44	struct hlist_head head;
45	spinlock_t lock;
46	};
47
48	struct dm_exception_table {
49	uint32_t hash_mask;
50	unsigned int hash_shift;
51	struct dm_hlist_head *table;
52	};
53
54	struct dm_snapshot {
55	struct rw_semaphore lock;
56
57	struct dm_dev *origin;
58	struct dm_dev *cow;
59
60	struct dm_target *ti;
61
62	/* List of snapshots per Origin */
63	struct list_head list;
64
65	/*
66	* You can't use a snapshot if this is 0 (e.g. if full).
67	* A snapshot-merge target never clears this.
68	*/
69	int valid;
70
71	/*
72	* The snapshot overflowed because of a write to the snapshot device.
73	* We don't have to invalidate the snapshot in this case, but we need
74	* to prevent further writes.
75	*/
76	int snapshot_overflowed;
77
78	/* Origin writes don't trigger exceptions until this is set */
79	int active;
80
81	atomic_t pending_exceptions_count;
82
83	spinlock_t pe_allocation_lock;
84
85	/* Protected by "pe_allocation_lock" */
86	sector_t exception_start_sequence;
87
88	/* Protected by kcopyd single-threaded callback */
89	sector_t exception_complete_sequence;
90
91	/*
92	* A list of pending exceptions that completed out of order.
93	* Protected by kcopyd single-threaded callback.
94	*/
95	struct rb_root out_of_order_tree;
96
97	mempool_t pending_pool;
98
99	struct dm_exception_table pending;
100	struct dm_exception_table complete;
101
102	/*
103	* pe_lock protects all pending_exception operations and access
104	* as well as the snapshot_bios list.
105	*/
106	spinlock_t pe_lock;
107
108	/* Chunks with outstanding reads */
109	spinlock_t tracked_chunk_lock;
110	struct hlist_head tracked_chunk_hash[DM_TRACKED_CHUNK_HASH_SIZE];
111
112	/* The on disk metadata handler */
113	struct dm_exception_store *store;
114
115	unsigned int in_progress;
116	struct wait_queue_head in_progress_wait;
117
118	struct dm_kcopyd_client *kcopyd_client;
119
120	/* Wait for events based on state_bits */
121	unsigned long state_bits;
122
123	/* Range of chunks currently being merged. */
124	chunk_t first_merging_chunk;
125	int num_merging_chunks;
126
127	/*
128	* The merge operation failed if this flag is set.
129	* Failure modes are handled as follows:
130	* - I/O error reading the header
131	* => don't load the target; abort.
132	* - Header does not have "valid" flag set
133	* => use the origin; forget about the snapshot.
134	* - I/O error when reading exceptions
135	* => don't load the target; abort.
136	* (We can't use the intermediate origin state.)
137	* - I/O error while merging
138	* => stop merging; set merge_failed; process I/O normally.
139	*/
140	bool merge_failed:1;
141
142	bool discard_zeroes_cow:1;
143	bool discard_passdown_origin:1;
144
145	/*
146	* Incoming bios that overlap with chunks being merged must wait
147	* for them to be committed.
148	*/
149	struct bio_list bios_queued_during_merge;
150	};
151
152	/*
153	* state_bits:
154	* RUNNING_MERGE - Merge operation is in progress.
155	* SHUTDOWN_MERGE - Set to signal that merge needs to be stopped;
156	* cleared afterwards.
157	*/
158	#define RUNNING_MERGE 0
159	#define SHUTDOWN_MERGE 1
160
161	/*
162	* Maximum number of chunks being copied on write.
163	*
164	* The value was decided experimentally as a trade-off between memory
165	* consumption, stalling the kernel's workqueues and maintaining a high enough
166	* throughput.
167	*/
168	#define DEFAULT_COW_THRESHOLD 2048
169
170	static unsigned int cow_threshold = DEFAULT_COW_THRESHOLD;
171	module_param_named(snapshot_cow_threshold, cow_threshold, uint, 0644);
172	MODULE_PARM_DESC(snapshot_cow_threshold, "Maximum number of chunks being copied on write");
173
174	DECLARE_DM_KCOPYD_THROTTLE_WITH_MODULE_PARM(snapshot_copy_throttle,
175	"A percentage of time allocated for copy on write");
176
177	struct dm_dev *dm_snap_origin(struct dm_snapshot *s)
178	{
179	return s->origin;
180	}
181	EXPORT_SYMBOL(dm_snap_origin);
182
183	struct dm_dev *dm_snap_cow(struct dm_snapshot *s)
184	{
185	return s->cow;
186	}
187	EXPORT_SYMBOL(dm_snap_cow);
188
189	static sector_t chunk_to_sector(struct dm_exception_store *store,
190	chunk_t chunk)
191	{
192	return chunk << store->chunk_shift;
193	}
194
195	static int bdev_equal(struct block_device *lhs, struct block_device *rhs)
196	{
197	/*
198	* There is only ever one instance of a particular block
199	* device so we can compare pointers safely.
200	*/
201	return lhs == rhs;
202	}
203
204	struct dm_snap_pending_exception {
205	struct dm_exception e;
206
207	/*
208	* Origin buffers waiting for this to complete are held
209	* in a bio list
210	*/
211	struct bio_list origin_bios;
212	struct bio_list snapshot_bios;
213
214	/* Pointer back to snapshot context */
215	struct dm_snapshot *snap;
216
217	/*
218	* 1 indicates the exception has already been sent to
219	* kcopyd.
220	*/
221	int started;
222
223	/* There was copying error. */
224	int copy_error;
225
226	/* A sequence number, it is used for in-order completion. */
227	sector_t exception_sequence;
228
229	struct rb_node out_of_order_node;
230
231	/*
232	* For writing a complete chunk, bypassing the copy.
233	*/
234	struct bio *full_bio;
235	bio_end_io_t *full_bio_end_io;
236	};
237
238	/*
239	* Hash table mapping origin volumes to lists of snapshots and
240	* a lock to protect it
241	*/
242	static struct kmem_cache *exception_cache;
243	static struct kmem_cache *pending_cache;
244
245	struct dm_snap_tracked_chunk {
246	struct hlist_node node;
247	chunk_t chunk;
248	};
249
250	static void init_tracked_chunk(struct bio *bio)
251	{
252	struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, data_size: sizeof(struct dm_snap_tracked_chunk));
253
254	INIT_HLIST_NODE(h: &c->node);
255	}
256
257	static bool is_bio_tracked(struct bio *bio)
258	{
259	struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, data_size: sizeof(struct dm_snap_tracked_chunk));
260
261	return !hlist_unhashed(h: &c->node);
262	}
263
264	static void track_chunk(struct dm_snapshot *s, struct bio *bio, chunk_t chunk)
265	{
266	struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, data_size: sizeof(struct dm_snap_tracked_chunk));
267
268	c->chunk = chunk;
269
270	spin_lock_irq(lock: &s->tracked_chunk_lock);
271	hlist_add_head(n: &c->node,
272	h: &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)]);
273	spin_unlock_irq(lock: &s->tracked_chunk_lock);
274	}
275
276	static void stop_tracking_chunk(struct dm_snapshot *s, struct bio *bio)
277	{
278	struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, data_size: sizeof(struct dm_snap_tracked_chunk));
279	unsigned long flags;
280
281	spin_lock_irqsave(&s->tracked_chunk_lock, flags);
282	hlist_del(n: &c->node);
283	spin_unlock_irqrestore(lock: &s->tracked_chunk_lock, flags);
284	}
285
286	static int __chunk_is_tracked(struct dm_snapshot *s, chunk_t chunk)
287	{
288	struct dm_snap_tracked_chunk *c;
289	int found = 0;
290
291	spin_lock_irq(lock: &s->tracked_chunk_lock);
292
293	hlist_for_each_entry(c,
294	&s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)], node) {
295	if (c->chunk == chunk) {
296	found = 1;
297	break;
298	}
299	}
300
301	spin_unlock_irq(lock: &s->tracked_chunk_lock);
302
303	return found;
304	}
305
306	/*
307	* This conflicting I/O is extremely improbable in the caller,
308	* so fsleep(1000) is sufficient and there is no need for a wait queue.
309	*/
310	static void __check_for_conflicting_io(struct dm_snapshot *s, chunk_t chunk)
311	{
312	while (__chunk_is_tracked(s, chunk))
313	fsleep(usecs: 1000);
314	}
315
316	/*
317	* One of these per registered origin, held in the snapshot_origins hash
318	*/
319	struct origin {
320	/* The origin device */
321	struct block_device *bdev;
322
323	struct list_head hash_list;
324
325	/* List of snapshots for this origin */
326	struct list_head snapshots;
327	};
328
329	/*
330	* This structure is allocated for each origin target
331	*/
332	struct dm_origin {
333	struct dm_dev *dev;
334	struct dm_target *ti;
335	unsigned int split_boundary;
336	struct list_head hash_list;
337	};
338
339	/*
340	* Size of the hash table for origin volumes. If we make this
341	* the size of the minors list then it should be nearly perfect
342	*/
343	#define ORIGIN_HASH_SIZE 256
344	#define ORIGIN_MASK 0xFF
345	static struct list_head *_origins;
346	static struct list_head *_dm_origins;
347	static struct rw_semaphore _origins_lock;
348
349	static DECLARE_WAIT_QUEUE_HEAD(_pending_exceptions_done);
350	static DEFINE_SPINLOCK(_pending_exceptions_done_spinlock);
351	static uint64_t _pending_exceptions_done_count;
352
353	static int init_origin_hash(void)
354	{
355	int i;
356
357	_origins = kmalloc_array(ORIGIN_HASH_SIZE, sizeof(struct list_head),
358	GFP_KERNEL);
359	if (!_origins) {
360	DMERR("unable to allocate memory for _origins");
361	return -ENOMEM;
362	}
363	for (i = 0; i < ORIGIN_HASH_SIZE; i++)
364	INIT_LIST_HEAD(list: _origins + i);
365
366	_dm_origins = kmalloc_array(ORIGIN_HASH_SIZE,
367	sizeof(struct list_head),
368	GFP_KERNEL);
369	if (!_dm_origins) {
370	DMERR("unable to allocate memory for _dm_origins");
371	kfree(objp: _origins);
372	return -ENOMEM;
373	}
374	for (i = 0; i < ORIGIN_HASH_SIZE; i++)
375	INIT_LIST_HEAD(list: _dm_origins + i);
376
377	init_rwsem(&_origins_lock);
378
379	return 0;
380	}
381
382	static void exit_origin_hash(void)
383	{
384	kfree(objp: _origins);
385	kfree(objp: _dm_origins);
386	}
387
388	static unsigned int origin_hash(struct block_device *bdev)
389	{
390	return bdev->bd_dev & ORIGIN_MASK;
391	}
392
393	static struct origin *__lookup_origin(struct block_device *origin)
394	{
395	struct list_head *ol;
396	struct origin *o;
397
398	ol = &_origins[origin_hash(bdev: origin)];
399	list_for_each_entry(o, ol, hash_list)
400	if (bdev_equal(lhs: o->bdev, rhs: origin))
401	return o;
402
403	return NULL;
404	}
405
406	static void __insert_origin(struct origin *o)
407	{
408	struct list_head *sl = &_origins[origin_hash(bdev: o->bdev)];
409
410	list_add_tail(new: &o->hash_list, head: sl);
411	}
412
413	static struct dm_origin *__lookup_dm_origin(struct block_device *origin)
414	{
415	struct list_head *ol;
416	struct dm_origin *o;
417
418	ol = &_dm_origins[origin_hash(bdev: origin)];
419	list_for_each_entry(o, ol, hash_list)
420	if (bdev_equal(lhs: o->dev->bdev, rhs: origin))
421	return o;
422
423	return NULL;
424	}
425
426	static void __insert_dm_origin(struct dm_origin *o)
427	{
428	struct list_head *sl = &_dm_origins[origin_hash(bdev: o->dev->bdev)];
429
430	list_add_tail(new: &o->hash_list, head: sl);
431	}
432
433	static void __remove_dm_origin(struct dm_origin *o)
434	{
435	list_del(entry: &o->hash_list);
436	}
437
438	/*
439	* _origins_lock must be held when calling this function.
440	* Returns number of snapshots registered using the supplied cow device, plus:
441	* snap_src - a snapshot suitable for use as a source of exception handover
442	* snap_dest - a snapshot capable of receiving exception handover.
443	* snap_merge - an existing snapshot-merge target linked to the same origin.
444	* There can be at most one snapshot-merge target. The parameter is optional.
445	*
446	* Possible return values and states of snap_src and snap_dest.
447	* 0: NULL, NULL - first new snapshot
448	* 1: snap_src, NULL - normal snapshot
449	* 2: snap_src, snap_dest - waiting for handover
450	* 2: snap_src, NULL - handed over, waiting for old to be deleted
451	* 1: NULL, snap_dest - source got destroyed without handover
452	*/
453	static int __find_snapshots_sharing_cow(struct dm_snapshot *snap,
454	struct dm_snapshot **snap_src,
455	struct dm_snapshot **snap_dest,
456	struct dm_snapshot **snap_merge)
457	{
458	struct dm_snapshot *s;
459	struct origin *o;
460	int count = 0;
461	int active;
462
463	o = __lookup_origin(origin: snap->origin->bdev);
464	if (!o)
465	goto out;
466
467	list_for_each_entry(s, &o->snapshots, list) {
468	if (dm_target_is_snapshot_merge(s->ti) && snap_merge)
469	*snap_merge = s;
470	if (!bdev_equal(lhs: s->cow->bdev, rhs: snap->cow->bdev))
471	continue;
472
473	down_read(sem: &s->lock);
474	active = s->active;
475	up_read(sem: &s->lock);
476
477	if (active) {
478	if (snap_src)
479	*snap_src = s;
480	} else if (snap_dest)
481	*snap_dest = s;
482
483	count++;
484	}
485
486	out:
487	return count;
488	}
489
490	/*
491	* On success, returns 1 if this snapshot is a handover destination,
492	* otherwise returns 0.
493	*/
494	static int __validate_exception_handover(struct dm_snapshot *snap)
495	{
496	struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
497	struct dm_snapshot *snap_merge = NULL;
498
499	/* Does snapshot need exceptions handed over to it? */
500	if ((__find_snapshots_sharing_cow(snap, snap_src: &snap_src, snap_dest: &snap_dest,
501	snap_merge: &snap_merge) == 2) ||
502	snap_dest) {
503	snap->ti->error = "Snapshot cow pairing for exception table handover failed";
504	return -EINVAL;
505	}
506
507	/*
508	* If no snap_src was found, snap cannot become a handover
509	* destination.
510	*/
511	if (!snap_src)
512	return 0;
513
514	/*
515	* Non-snapshot-merge handover?
516	*/
517	if (!dm_target_is_snapshot_merge(snap->ti))
518	return 1;
519
520	/*
521	* Do not allow more than one merging snapshot.
522	*/
523	if (snap_merge) {
524	snap->ti->error = "A snapshot is already merging.";
525	return -EINVAL;
526	}
527
528	if (!snap_src->store->type->prepare_merge ||
529	!snap_src->store->type->commit_merge) {
530	snap->ti->error = "Snapshot exception store does not support snapshot-merge.";
531	return -EINVAL;
532	}
533
534	return 1;
535	}
536
537	static void __insert_snapshot(struct origin *o, struct dm_snapshot *s)
538	{
539	struct dm_snapshot *l;
540
541	/* Sort the list according to chunk size, largest-first smallest-last */
542	list_for_each_entry(l, &o->snapshots, list)
543	if (l->store->chunk_size < s->store->chunk_size)
544	break;
545	list_add_tail(new: &s->list, head: &l->list);
546	}
547
548	/*
549	* Make a note of the snapshot and its origin so we can look it
550	* up when the origin has a write on it.
551	*
552	* Also validate snapshot exception store handovers.
553	* On success, returns 1 if this registration is a handover destination,
554	* otherwise returns 0.
555	*/
556	static int register_snapshot(struct dm_snapshot *snap)
557	{
558	struct origin *o, *new_o = NULL;
559	struct block_device *bdev = snap->origin->bdev;
560	int r = 0;
561
562	new_o = kmalloc(sizeof(*new_o), GFP_KERNEL);
563	if (!new_o)
564	return -ENOMEM;
565
566	down_write(sem: &_origins_lock);
567
568	r = __validate_exception_handover(snap);
569	if (r < 0) {
570	kfree(objp: new_o);
571	goto out;
572	}
573
574	o = __lookup_origin(origin: bdev);
575	if (o)
576	kfree(objp: new_o);
577	else {
578	/* New origin */
579	o = new_o;
580
581	/* Initialise the struct */
582	INIT_LIST_HEAD(list: &o->snapshots);
583	o->bdev = bdev;
584
585	__insert_origin(o);
586	}
587
588	__insert_snapshot(o, s: snap);
589
590	out:
591	up_write(sem: &_origins_lock);
592
593	return r;
594	}
595
596	/*
597	* Move snapshot to correct place in list according to chunk size.
598	*/
599	static void reregister_snapshot(struct dm_snapshot *s)
600	{
601	struct block_device *bdev = s->origin->bdev;
602
603	down_write(sem: &_origins_lock);
604
605	list_del(entry: &s->list);
606	__insert_snapshot(o: __lookup_origin(origin: bdev), s);
607
608	up_write(sem: &_origins_lock);
609	}
610
611	static void unregister_snapshot(struct dm_snapshot *s)
612	{
613	struct origin *o;
614
615	down_write(sem: &_origins_lock);
616	o = __lookup_origin(origin: s->origin->bdev);
617
618	list_del(entry: &s->list);
619	if (o && list_empty(head: &o->snapshots)) {
620	list_del(entry: &o->hash_list);
621	kfree(objp: o);
622	}
623
624	up_write(sem: &_origins_lock);
625	}
626
627	/*
628	* Implementation of the exception hash tables.
629	* The lowest hash_shift bits of the chunk number are ignored, allowing
630	* some consecutive chunks to be grouped together.
631	*/
632	static uint32_t exception_hash(struct dm_exception_table *et, chunk_t chunk);
633
634	/* Lock to protect access to the completed and pending exception hash tables. */
635	struct dm_exception_table_lock {
636	spinlock_t *complete_slot;
637	spinlock_t *pending_slot;
638	};
639
640	static void dm_exception_table_lock_init(struct dm_snapshot *s, chunk_t chunk,
641	struct dm_exception_table_lock *lock)
642	{
643	struct dm_exception_table *complete = &s->complete;
644	struct dm_exception_table *pending = &s->pending;
645
646	lock->complete_slot = &complete->table[exception_hash(et: complete, chunk)].lock;
647	lock->pending_slot = &pending->table[exception_hash(et: pending, chunk)].lock;
648	}
649
650	static void dm_exception_table_lock(struct dm_exception_table_lock *lock)
651	{
652	spin_lock_nested(lock->complete_slot, 1);
653	spin_lock_nested(lock->pending_slot, 2);
654	}
655
656	static void dm_exception_table_unlock(struct dm_exception_table_lock *lock)
657	{
658	spin_unlock(lock: lock->pending_slot);
659	spin_unlock(lock: lock->complete_slot);
660	}
661
662	static int dm_exception_table_init(struct dm_exception_table *et,
663	uint32_t size, unsigned int hash_shift)
664	{
665	unsigned int i;
666
667	et->hash_shift = hash_shift;
668	et->hash_mask = size - 1;
669	et->table = kvmalloc_array(size, sizeof(struct dm_hlist_head),
670	GFP_KERNEL);
671	if (!et->table)
672	return -ENOMEM;
673
674	for (i = 0; i < size; i++) {
675	INIT_HLIST_HEAD(&et->table[i].head);
676	spin_lock_init(&et->table[i].lock);
677	}
678
679	return 0;
680	}
681
682	static void dm_exception_table_exit(struct dm_exception_table *et,
683	struct kmem_cache *mem)
684	{
685	struct dm_hlist_head *slot;
686	struct dm_exception *ex;
687	struct hlist_node *pos;
688	int i, size;
689
690	size = et->hash_mask + 1;
691	for (i = 0; i < size; i++) {
692	slot = et->table + i;
693
694	hlist_for_each_entry_safe(ex, pos, &slot->head, hash_list) {
695	hlist_del(n: &ex->hash_list);
696	kmem_cache_free(s: mem, objp: ex);
697	cond_resched();
698	}
699	}
700
701	kvfree(addr: et->table);
702	}
703
704	static uint32_t exception_hash(struct dm_exception_table *et, chunk_t chunk)
705	{
706	return (chunk >> et->hash_shift) & et->hash_mask;
707	}
708
709	static void dm_remove_exception(struct dm_exception *e)
710	{
711	hlist_del(n: &e->hash_list);
712	}
713
714	/*
715	* Return the exception data for a sector, or NULL if not
716	* remapped.
717	*/
718	static struct dm_exception *dm_lookup_exception(struct dm_exception_table *et,
719	chunk_t chunk)
720	{
721	struct hlist_head *slot;
722	struct dm_exception *e;
723
724	slot = &et->table[exception_hash(et, chunk)].head;
725	hlist_for_each_entry(e, slot, hash_list)
726	if (chunk >= e->old_chunk &&
727	chunk <= e->old_chunk + dm_consecutive_chunk_count(e))
728	return e;
729
730	return NULL;
731	}
732
733	static struct dm_exception *alloc_completed_exception(gfp_t gfp)
734	{
735	struct dm_exception *e;
736
737	e = kmem_cache_alloc(exception_cache, gfp);
738	if (!e && gfp == GFP_NOIO)
739	e = kmem_cache_alloc(exception_cache, GFP_ATOMIC);
740
741	return e;
742	}
743
744	static void free_completed_exception(struct dm_exception *e)
745	{
746	kmem_cache_free(s: exception_cache, objp: e);
747	}
748
749	static struct dm_snap_pending_exception *alloc_pending_exception(struct dm_snapshot *s)
750	{
751	struct dm_snap_pending_exception *pe = mempool_alloc(&s->pending_pool,
752	GFP_NOIO);
753
754	atomic_inc(v: &s->pending_exceptions_count);
755	pe->snap = s;
756
757	return pe;
758	}
759
760	static void free_pending_exception(struct dm_snap_pending_exception *pe)
761	{
762	struct dm_snapshot *s = pe->snap;
763
764	mempool_free(element: pe, pool: &s->pending_pool);
765	smp_mb__before_atomic();
766	atomic_dec(v: &s->pending_exceptions_count);
767	}
768
769	static void dm_insert_exception(struct dm_exception_table *eh,
770	struct dm_exception *new_e)
771	{
772	struct hlist_head *l;
773	struct dm_exception *e = NULL;
774
775	l = &eh->table[exception_hash(et: eh, chunk: new_e->old_chunk)].head;
776
777	/* Add immediately if this table doesn't support consecutive chunks */
778	if (!eh->hash_shift)
779	goto out;
780
781	/* List is ordered by old_chunk */
782	hlist_for_each_entry(e, l, hash_list) {
783	/* Insert after an existing chunk? */
784	if (new_e->old_chunk == (e->old_chunk +
785	dm_consecutive_chunk_count(e) + 1) &&
786	new_e->new_chunk == (dm_chunk_number(chunk: e->new_chunk) +
787	dm_consecutive_chunk_count(e) + 1)) {
788	dm_consecutive_chunk_count_inc(e);
789	free_completed_exception(e: new_e);
790	return;
791	}
792
793	/* Insert before an existing chunk? */
794	if (new_e->old_chunk == (e->old_chunk - 1) &&
795	new_e->new_chunk == (dm_chunk_number(chunk: e->new_chunk) - 1)) {
796	dm_consecutive_chunk_count_inc(e);
797	e->old_chunk--;
798	e->new_chunk--;
799	free_completed_exception(e: new_e);
800	return;
801	}
802
803	if (new_e->old_chunk < e->old_chunk)
804	break;
805	}
806
807	out:
808	if (!e) {
809	/*
810	* Either the table doesn't support consecutive chunks or slot
811	* l is empty.
812	*/
813	hlist_add_head(n: &new_e->hash_list, h: l);
814	} else if (new_e->old_chunk < e->old_chunk) {
815	/* Add before an existing exception */
816	hlist_add_before(n: &new_e->hash_list, next: &e->hash_list);
817	} else {
818	/* Add to l's tail: e is the last exception in this slot */
819	hlist_add_behind(n: &new_e->hash_list, prev: &e->hash_list);
820	}
821	}
822
823	/*
824	* Callback used by the exception stores to load exceptions when
825	* initialising.
826	*/
827	static int dm_add_exception(void *context, chunk_t old, chunk_t new)
828	{
829	struct dm_snapshot *s = context;
830	struct dm_exception *e;
831
832	e = alloc_completed_exception(GFP_KERNEL);
833	if (!e)
834	return -ENOMEM;
835
836	e->old_chunk = old;
837
838	/* Consecutive_count is implicitly initialised to zero */
839	e->new_chunk = new;
840
841	dm_insert_exception(eh: &s->complete, new_e: e);
842
843	return 0;
844	}
845
846	/*
847	* Return a minimum chunk size of all snapshots that have the specified origin.
848	* Return zero if the origin has no snapshots.
849	*/
850	static uint32_t __minimum_chunk_size(struct origin *o)
851	{
852	struct dm_snapshot *snap;
853	unsigned int chunk_size = rounddown_pow_of_two(UINT_MAX);
854
855	if (o)
856	list_for_each_entry(snap, &o->snapshots, list)
857	chunk_size = min_not_zero(chunk_size,
858	snap->store->chunk_size);
859
860	return (uint32_t) chunk_size;
861	}
862
863	/*
864	* Hard coded magic.
865	*/
866	static int calc_max_buckets(void)
867	{
868	/* use a fixed size of 2MB */
869	unsigned long mem = 2 * 1024 * 1024;
870
871	mem /= sizeof(struct dm_hlist_head);
872
873	return mem;
874	}
875
876	/*
877	* Allocate room for a suitable hash table.
878	*/
879	static int init_hash_tables(struct dm_snapshot *s)
880	{
881	sector_t hash_size, cow_dev_size, max_buckets;
882
883	/*
884	* Calculate based on the size of the original volume or
885	* the COW volume...
886	*/
887	cow_dev_size = get_dev_size(bdev: s->cow->bdev);
888	max_buckets = calc_max_buckets();
889
890	hash_size = cow_dev_size >> s->store->chunk_shift;
891	hash_size = min(hash_size, max_buckets);
892
893	if (hash_size < 64)
894	hash_size = 64;
895	hash_size = rounddown_pow_of_two(hash_size);
896	if (dm_exception_table_init(et: &s->complete, size: hash_size,
897	DM_CHUNK_CONSECUTIVE_BITS))
898	return -ENOMEM;
899
900	/*
901	* Allocate hash table for in-flight exceptions
902	* Make this smaller than the real hash table
903	*/
904	hash_size >>= 3;
905	if (hash_size < 64)
906	hash_size = 64;
907
908	if (dm_exception_table_init(et: &s->pending, size: hash_size, hash_shift: 0)) {
909	dm_exception_table_exit(et: &s->complete, mem: exception_cache);
910	return -ENOMEM;
911	}
912
913	return 0;
914	}
915
916	static void merge_shutdown(struct dm_snapshot *s)
917	{
918	clear_bit_unlock(RUNNING_MERGE, addr: &s->state_bits);
919	smp_mb__after_atomic();
920	wake_up_bit(word: &s->state_bits, RUNNING_MERGE);
921	}
922
923	static struct bio *__release_queued_bios_after_merge(struct dm_snapshot *s)
924	{
925	s->first_merging_chunk = 0;
926	s->num_merging_chunks = 0;
927
928	return bio_list_get(bl: &s->bios_queued_during_merge);
929	}
930
931	/*
932	* Remove one chunk from the index of completed exceptions.
933	*/
934	static int __remove_single_exception_chunk(struct dm_snapshot *s,
935	chunk_t old_chunk)
936	{
937	struct dm_exception *e;
938
939	e = dm_lookup_exception(et: &s->complete, chunk: old_chunk);
940	if (!e) {
941	DMERR("Corruption detected: exception for block %llu is on disk but not in memory",
942	(unsigned long long)old_chunk);
943	return -EINVAL;
944	}
945
946	/*
947	* If this is the only chunk using this exception, remove exception.
948	*/
949	if (!dm_consecutive_chunk_count(e)) {
950	dm_remove_exception(e);
951	free_completed_exception(e);
952	return 0;
953	}
954
955	/*
956	* The chunk may be either at the beginning or the end of a
957	* group of consecutive chunks - never in the middle. We are
958	* removing chunks in the opposite order to that in which they
959	* were added, so this should always be true.
960	* Decrement the consecutive chunk counter and adjust the
961	* starting point if necessary.
962	*/
963	if (old_chunk == e->old_chunk) {
964	e->old_chunk++;
965	e->new_chunk++;
966	} else if (old_chunk != e->old_chunk +
967	dm_consecutive_chunk_count(e)) {
968	DMERR("Attempt to merge block %llu from the middle of a chunk range [%llu - %llu]",
969	(unsigned long long)old_chunk,
970	(unsigned long long)e->old_chunk,
971	(unsigned long long)
972	e->old_chunk + dm_consecutive_chunk_count(e));
973	return -EINVAL;
974	}
975
976	dm_consecutive_chunk_count_dec(e);
977
978	return 0;
979	}
980
981	static void flush_bios(struct bio *bio);
982
983	static int remove_single_exception_chunk(struct dm_snapshot *s)
984	{
985	struct bio *b = NULL;
986	int r;
987	chunk_t old_chunk = s->first_merging_chunk + s->num_merging_chunks - 1;
988
989	down_write(sem: &s->lock);
990
991	/*
992	* Process chunks (and associated exceptions) in reverse order
993	* so that dm_consecutive_chunk_count_dec() accounting works.
994	*/
995	do {
996	r = __remove_single_exception_chunk(s, old_chunk);
997	if (r)
998	goto out;
999	} while (old_chunk-- > s->first_merging_chunk);
1000
1001	b = __release_queued_bios_after_merge(s);
1002
1003	out:
1004	up_write(sem: &s->lock);
1005	if (b)
1006	flush_bios(bio: b);
1007
1008	return r;
1009	}
1010
1011	static int origin_write_extent(struct dm_snapshot *merging_snap,
1012	sector_t sector, unsigned int chunk_size);
1013
1014	static void merge_callback(int read_err, unsigned long write_err,
1015	void *context);
1016
1017	static uint64_t read_pending_exceptions_done_count(void)
1018	{
1019	uint64_t pending_exceptions_done;
1020
1021	spin_lock(lock: &_pending_exceptions_done_spinlock);
1022	pending_exceptions_done = _pending_exceptions_done_count;
1023	spin_unlock(lock: &_pending_exceptions_done_spinlock);
1024
1025	return pending_exceptions_done;
1026	}
1027
1028	static void increment_pending_exceptions_done_count(void)
1029	{
1030	spin_lock(lock: &_pending_exceptions_done_spinlock);
1031	_pending_exceptions_done_count++;
1032	spin_unlock(lock: &_pending_exceptions_done_spinlock);
1033
1034	wake_up_all(&_pending_exceptions_done);
1035	}
1036
1037	static void snapshot_merge_next_chunks(struct dm_snapshot *s)
1038	{
1039	int i, linear_chunks;
1040	chunk_t old_chunk, new_chunk;
1041	struct dm_io_region src, dest;
1042	sector_t io_size;
1043	uint64_t previous_count;
1044
1045	BUG_ON(!test_bit(RUNNING_MERGE, &s->state_bits));
1046	if (unlikely(test_bit(SHUTDOWN_MERGE, &s->state_bits)))
1047	goto shut;
1048
1049	/*
1050	* valid flag never changes during merge, so no lock required.
1051	*/
1052	if (!s->valid) {
1053	DMERR("Snapshot is invalid: can't merge");
1054	goto shut;
1055	}
1056
1057	linear_chunks = s->store->type->prepare_merge(s->store, &old_chunk,
1058	&new_chunk);
1059	if (linear_chunks <= 0) {
1060	if (linear_chunks < 0) {
1061	DMERR("Read error in exception store: shutting down merge");
1062	down_write(sem: &s->lock);
1063	s->merge_failed = true;
1064	up_write(sem: &s->lock);
1065	}
1066	goto shut;
1067	}
1068
1069	/* Adjust old_chunk and new_chunk to reflect start of linear region */
1070	old_chunk = old_chunk + 1 - linear_chunks;
1071	new_chunk = new_chunk + 1 - linear_chunks;
1072
1073	/*
1074	* Use one (potentially large) I/O to copy all 'linear_chunks'
1075	* from the exception store to the origin
1076	*/
1077	io_size = linear_chunks * s->store->chunk_size;
1078
1079	dest.bdev = s->origin->bdev;
1080	dest.sector = chunk_to_sector(store: s->store, chunk: old_chunk);
1081	dest.count = min(io_size, get_dev_size(dest.bdev) - dest.sector);
1082
1083	src.bdev = s->cow->bdev;
1084	src.sector = chunk_to_sector(store: s->store, chunk: new_chunk);
1085	src.count = dest.count;
1086
1087	/*
1088	* Reallocate any exceptions needed in other snapshots then
1089	* wait for the pending exceptions to complete.
1090	* Each time any pending exception (globally on the system)
1091	* completes we are woken and repeat the process to find out
1092	* if we can proceed. While this may not seem a particularly
1093	* efficient algorithm, it is not expected to have any
1094	* significant impact on performance.
1095	*/
1096	previous_count = read_pending_exceptions_done_count();
1097	while (origin_write_extent(merging_snap: s, sector: dest.sector, chunk_size: io_size)) {
1098	wait_event(_pending_exceptions_done,
1099	(read_pending_exceptions_done_count() !=
1100	previous_count));
1101	/* Retry after the wait, until all exceptions are done. */
1102	previous_count = read_pending_exceptions_done_count();
1103	}
1104
1105	down_write(sem: &s->lock);
1106	s->first_merging_chunk = old_chunk;
1107	s->num_merging_chunks = linear_chunks;
1108	up_write(sem: &s->lock);
1109
1110	/* Wait until writes to all 'linear_chunks' drain */
1111	for (i = 0; i < linear_chunks; i++)
1112	__check_for_conflicting_io(s, chunk: old_chunk + i);
1113
1114	dm_kcopyd_copy(kc: s->kcopyd_client, from: &src, num_dests: 1, dests: &dest, flags: 0, fn: merge_callback, context: s);
1115	return;
1116
1117	shut:
1118	merge_shutdown(s);
1119	}
1120
1121	static void error_bios(struct bio *bio);
1122
1123	static void merge_callback(int read_err, unsigned long write_err, void *context)
1124	{
1125	struct dm_snapshot *s = context;
1126	struct bio *b = NULL;
1127
1128	if (read_err || write_err) {
1129	if (read_err)
1130	DMERR("Read error: shutting down merge.");
1131	else
1132	DMERR("Write error: shutting down merge.");
1133	goto shut;
1134	}
1135
1136	if (blkdev_issue_flush(bdev: s->origin->bdev) < 0) {
1137	DMERR("Flush after merge failed: shutting down merge");
1138	goto shut;
1139	}
1140
1141	if (s->store->type->commit_merge(s->store,
1142	s->num_merging_chunks) < 0) {
1143	DMERR("Write error in exception store: shutting down merge");
1144	goto shut;
1145	}
1146
1147	if (remove_single_exception_chunk(s) < 0)
1148	goto shut;
1149
1150	snapshot_merge_next_chunks(s);
1151
1152	return;
1153
1154	shut:
1155	down_write(sem: &s->lock);
1156	s->merge_failed = true;
1157	b = __release_queued_bios_after_merge(s);
1158	up_write(sem: &s->lock);
1159	error_bios(bio: b);
1160
1161	merge_shutdown(s);
1162	}
1163
1164	static void start_merge(struct dm_snapshot *s)
1165	{
1166	if (!test_and_set_bit(RUNNING_MERGE, addr: &s->state_bits))
1167	snapshot_merge_next_chunks(s);
1168	}
1169
1170	/*
1171	* Stop the merging process and wait until it finishes.
1172	*/
1173	static void stop_merge(struct dm_snapshot *s)
1174	{
1175	set_bit(SHUTDOWN_MERGE, addr: &s->state_bits);
1176	wait_on_bit(word: &s->state_bits, RUNNING_MERGE, TASK_UNINTERRUPTIBLE);
1177	clear_bit(SHUTDOWN_MERGE, addr: &s->state_bits);
1178	}
1179
1180	static int parse_snapshot_features(struct dm_arg_set *as, struct dm_snapshot *s,
1181	struct dm_target *ti)
1182	{
1183	int r;
1184	unsigned int argc;
1185	const char *arg_name;
1186
1187	static const struct dm_arg _args[] = {
1188	{.min: 0, .max: 2, .error: "Invalid number of feature arguments"},
1189	};
1190
1191	/*
1192	* No feature arguments supplied.
1193	*/
1194	if (!as->argc)
1195	return 0;
1196
1197	r = dm_read_arg_group(arg: _args, arg_set: as, num_args: &argc, error: &ti->error);
1198	if (r)
1199	return -EINVAL;
1200
1201	while (argc && !r) {
1202	arg_name = dm_shift_arg(as);
1203	argc--;
1204
1205	if (!strcasecmp(s1: arg_name, s2: "discard_zeroes_cow"))
1206	s->discard_zeroes_cow = true;
1207
1208	else if (!strcasecmp(s1: arg_name, s2: "discard_passdown_origin"))
1209	s->discard_passdown_origin = true;
1210
1211	else {
1212	ti->error = "Unrecognised feature requested";
1213	r = -EINVAL;
1214	break;
1215	}
1216	}
1217
1218	if (!s->discard_zeroes_cow && s->discard_passdown_origin) {
1219	/*
1220	* TODO: really these are disjoint.. but ti->num_discard_bios
1221	* and dm_bio_get_target_bio_nr() require rigid constraints.
1222	*/
1223	ti->error = "discard_passdown_origin feature depends on discard_zeroes_cow";
1224	r = -EINVAL;
1225	}
1226
1227	return r;
1228	}
1229
1230	/*
1231	* Construct a snapshot mapping:
1232	* <origin_dev> <COW-dev> <p|po|n> <chunk-size> [<# feature args> [<arg>]*]
1233	*/
1234	static int snapshot_ctr(struct dm_target *ti, unsigned int argc, char **argv)
1235	{
1236	struct dm_snapshot *s;
1237	struct dm_arg_set as;
1238	int i;
1239	int r = -EINVAL;
1240	char *origin_path, *cow_path;
1241	unsigned int args_used, num_flush_bios = 1;
1242	blk_mode_t origin_mode = BLK_OPEN_READ;
1243
1244	if (argc < 4) {
1245	ti->error = "requires 4 or more arguments";
1246	r = -EINVAL;
1247	goto bad;
1248	}
1249
1250	if (dm_target_is_snapshot_merge(ti)) {
1251	num_flush_bios = 2;
1252	origin_mode = BLK_OPEN_WRITE;
1253	}
1254
1255	s = kzalloc(sizeof(*s), GFP_KERNEL);
1256	if (!s) {
1257	ti->error = "Cannot allocate private snapshot structure";
1258	r = -ENOMEM;
1259	goto bad;
1260	}
1261
1262	as.argc = argc;
1263	as.argv = argv;
1264	dm_consume_args(as: &as, num_args: 4);
1265	r = parse_snapshot_features(as: &as, s, ti);
1266	if (r)
1267	goto bad_features;
1268
1269	origin_path = argv[0];
1270	argv++;
1271	argc--;
1272
1273	r = dm_get_device(ti, path: origin_path, mode: origin_mode, result: &s->origin);
1274	if (r) {
1275	ti->error = "Cannot get origin device";
1276	goto bad_origin;
1277	}
1278
1279	cow_path = argv[0];
1280	argv++;
1281	argc--;
1282
1283	r = dm_get_device(ti, path: cow_path, mode: dm_table_get_mode(t: ti->table), result: &s->cow);
1284	if (r) {
1285	ti->error = "Cannot get COW device";
1286	goto bad_cow;
1287	}
1288	if (s->cow->bdev && s->cow->bdev == s->origin->bdev) {
1289	ti->error = "COW device cannot be the same as origin device";
1290	r = -EINVAL;
1291	goto bad_store;
1292	}
1293
1294	r = dm_exception_store_create(ti, argc, argv, snap: s, args_used: &args_used, store: &s->store);
1295	if (r) {
1296	ti->error = "Couldn't create exception store";
1297	r = -EINVAL;
1298	goto bad_store;
1299	}
1300
1301	argv += args_used;
1302	argc -= args_used;
1303
1304	s->ti = ti;
1305	s->valid = 1;
1306	s->snapshot_overflowed = 0;
1307	s->active = 0;
1308	atomic_set(v: &s->pending_exceptions_count, i: 0);
1309	spin_lock_init(&s->pe_allocation_lock);
1310	s->exception_start_sequence = 0;
1311	s->exception_complete_sequence = 0;
1312	s->out_of_order_tree = RB_ROOT;
1313	init_rwsem(&s->lock);
1314	INIT_LIST_HEAD(list: &s->list);
1315	spin_lock_init(&s->pe_lock);
1316	s->state_bits = 0;
1317	s->merge_failed = false;
1318	s->first_merging_chunk = 0;
1319	s->num_merging_chunks = 0;
1320	bio_list_init(bl: &s->bios_queued_during_merge);
1321
1322	/* Allocate hash table for COW data */
1323	if (init_hash_tables(s)) {
1324	ti->error = "Unable to allocate hash table space";
1325	r = -ENOMEM;
1326	goto bad_hash_tables;
1327	}
1328
1329	init_waitqueue_head(&s->in_progress_wait);
1330
1331	s->kcopyd_client = dm_kcopyd_client_create(throttle: &dm_kcopyd_throttle);
1332	if (IS_ERR(ptr: s->kcopyd_client)) {
1333	r = PTR_ERR(ptr: s->kcopyd_client);
1334	ti->error = "Could not create kcopyd client";
1335	goto bad_kcopyd;
1336	}
1337
1338	r = mempool_init_slab_pool(&s->pending_pool, MIN_IOS, pending_cache);
1339	if (r) {
1340	ti->error = "Could not allocate mempool for pending exceptions";
1341	goto bad_pending_pool;
1342	}
1343
1344	for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
1345	INIT_HLIST_HEAD(&s->tracked_chunk_hash[i]);
1346
1347	spin_lock_init(&s->tracked_chunk_lock);
1348
1349	ti->private = s;
1350	ti->num_flush_bios = num_flush_bios;
1351	if (s->discard_zeroes_cow)
1352	ti->num_discard_bios = (s->discard_passdown_origin ? 2 : 1);
1353	ti->per_io_data_size = sizeof(struct dm_snap_tracked_chunk);
1354
1355	/* Add snapshot to the list of snapshots for this origin */
1356	/* Exceptions aren't triggered till snapshot_resume() is called */
1357	r = register_snapshot(snap: s);
1358	if (r == -ENOMEM) {
1359	ti->error = "Snapshot origin struct allocation failed";
1360	goto bad_load_and_register;
1361	} else if (r < 0) {
1362	/* invalid handover, register_snapshot has set ti->error */
1363	goto bad_load_and_register;
1364	}
1365
1366	/*
1367	* Metadata must only be loaded into one table at once, so skip this
1368	* if metadata will be handed over during resume.
1369	* Chunk size will be set during the handover - set it to zero to
1370	* ensure it's ignored.
1371	*/
1372	if (r > 0) {
1373	s->store->chunk_size = 0;
1374	return 0;
1375	}
1376
1377	r = s->store->type->read_metadata(s->store, dm_add_exception,
1378	(void *)s);
1379	if (r < 0) {
1380	ti->error = "Failed to read snapshot metadata";
1381	goto bad_read_metadata;
1382	} else if (r > 0) {
1383	s->valid = 0;
1384	DMWARN("Snapshot is marked invalid.");
1385	}
1386
1387	if (!s->store->chunk_size) {
1388	ti->error = "Chunk size not set";
1389	r = -EINVAL;
1390	goto bad_read_metadata;
1391	}
1392
1393	r = dm_set_target_max_io_len(ti, len: s->store->chunk_size);
1394	if (r)
1395	goto bad_read_metadata;
1396
1397	return 0;
1398
1399	bad_read_metadata:
1400	unregister_snapshot(s);
1401	bad_load_and_register:
1402	mempool_exit(pool: &s->pending_pool);
1403	bad_pending_pool:
1404	dm_kcopyd_client_destroy(kc: s->kcopyd_client);
1405	bad_kcopyd:
1406	dm_exception_table_exit(et: &s->pending, mem: pending_cache);
1407	dm_exception_table_exit(et: &s->complete, mem: exception_cache);
1408	bad_hash_tables:
1409	dm_exception_store_destroy(store: s->store);
1410	bad_store:
1411	dm_put_device(ti, d: s->cow);
1412	bad_cow:
1413	dm_put_device(ti, d: s->origin);
1414	bad_origin:
1415	bad_features:
1416	kfree(objp: s);
1417	bad:
1418	return r;
1419	}
1420
1421	static void __free_exceptions(struct dm_snapshot *s)
1422	{
1423	dm_kcopyd_client_destroy(kc: s->kcopyd_client);
1424	s->kcopyd_client = NULL;
1425
1426	dm_exception_table_exit(et: &s->pending, mem: pending_cache);
1427	dm_exception_table_exit(et: &s->complete, mem: exception_cache);
1428	}
1429
1430	static void __handover_exceptions(struct dm_snapshot *snap_src,
1431	struct dm_snapshot *snap_dest)
1432	{
1433	union {
1434	struct dm_exception_table table_swap;
1435	struct dm_exception_store *store_swap;
1436	} u;
1437
1438	/*
1439	* Swap all snapshot context information between the two instances.
1440	*/
1441	u.table_swap = snap_dest->complete;
1442	snap_dest->complete = snap_src->complete;
1443	snap_src->complete = u.table_swap;
1444
1445	u.store_swap = snap_dest->store;
1446	snap_dest->store = snap_src->store;
1447	snap_dest->store->userspace_supports_overflow = u.store_swap->userspace_supports_overflow;
1448	snap_src->store = u.store_swap;
1449
1450	snap_dest->store->snap = snap_dest;
1451	snap_src->store->snap = snap_src;
1452
1453	snap_dest->ti->max_io_len = snap_dest->store->chunk_size;
1454	snap_dest->valid = snap_src->valid;
1455	snap_dest->snapshot_overflowed = snap_src->snapshot_overflowed;
1456
1457	/*
1458	* Set source invalid to ensure it receives no further I/O.
1459	*/
1460	snap_src->valid = 0;
1461	}
1462
1463	static void snapshot_dtr(struct dm_target *ti)
1464	{
1465	#ifdef CONFIG_DM_DEBUG
1466	int i;
1467	#endif
1468	struct dm_snapshot *s = ti->private;
1469	struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
1470
1471	down_read(sem: &_origins_lock);
1472	/* Check whether exception handover must be cancelled */
1473	(void) __find_snapshots_sharing_cow(snap: s, snap_src: &snap_src, snap_dest: &snap_dest, NULL);
1474	if (snap_src && snap_dest && (s == snap_src)) {
1475	down_write(sem: &snap_dest->lock);
1476	snap_dest->valid = 0;
1477	up_write(sem: &snap_dest->lock);
1478	DMERR("Cancelling snapshot handover.");
1479	}
1480	up_read(sem: &_origins_lock);
1481
1482	if (dm_target_is_snapshot_merge(ti))
1483	stop_merge(s);
1484
1485	/* Prevent further origin writes from using this snapshot. */
1486	/* After this returns there can be no new kcopyd jobs. */
1487	unregister_snapshot(s);
1488
1489	while (atomic_read(v: &s->pending_exceptions_count))
1490	fsleep(usecs: 1000);
1491	/*
1492	* Ensure instructions in mempool_exit aren't reordered
1493	* before atomic_read.
1494	*/
1495	smp_mb();
1496
1497	#ifdef CONFIG_DM_DEBUG
1498	for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
1499	BUG_ON(!hlist_empty(&s->tracked_chunk_hash[i]));
1500	#endif
1501
1502	__free_exceptions(s);
1503
1504	mempool_exit(pool: &s->pending_pool);
1505
1506	dm_exception_store_destroy(store: s->store);
1507
1508	dm_put_device(ti, d: s->cow);
1509
1510	dm_put_device(ti, d: s->origin);
1511
1512	WARN_ON(s->in_progress);
1513
1514	kfree(objp: s);
1515	}
1516
1517	static void account_start_copy(struct dm_snapshot *s)
1518	{
1519	spin_lock(lock: &s->in_progress_wait.lock);
1520	s->in_progress++;
1521	spin_unlock(lock: &s->in_progress_wait.lock);
1522	}
1523
1524	static void account_end_copy(struct dm_snapshot *s)
1525	{
1526	spin_lock(lock: &s->in_progress_wait.lock);
1527	BUG_ON(!s->in_progress);
1528	s->in_progress--;
1529	if (likely(s->in_progress <= cow_threshold) &&
1530	unlikely(waitqueue_active(&s->in_progress_wait)))
1531	wake_up_locked(&s->in_progress_wait);
1532	spin_unlock(lock: &s->in_progress_wait.lock);
1533	}
1534
1535	static bool wait_for_in_progress(struct dm_snapshot *s, bool unlock_origins)
1536	{
1537	if (unlikely(s->in_progress > cow_threshold)) {
1538	spin_lock(lock: &s->in_progress_wait.lock);
1539	if (likely(s->in_progress > cow_threshold)) {
1540	/*
1541	* NOTE: this throttle doesn't account for whether
1542	* the caller is servicing an IO that will trigger a COW
1543	* so excess throttling may result for chunks not required
1544	* to be COW'd. But if cow_threshold was reached, extra
1545	* throttling is unlikely to negatively impact performance.
1546	*/
1547	DECLARE_WAITQUEUE(wait, current);
1548
1549	__add_wait_queue(wq_head: &s->in_progress_wait, wq_entry: &wait);
1550	__set_current_state(TASK_UNINTERRUPTIBLE);
1551	spin_unlock(lock: &s->in_progress_wait.lock);
1552	if (unlock_origins)
1553	up_read(sem: &_origins_lock);
1554	io_schedule();
1555	remove_wait_queue(wq_head: &s->in_progress_wait, wq_entry: &wait);
1556	return false;
1557	}
1558	spin_unlock(lock: &s->in_progress_wait.lock);
1559	}
1560	return true;
1561	}
1562
1563	/*
1564	* Flush a list of buffers.
1565	*/
1566	static void flush_bios(struct bio *bio)
1567	{
1568	struct bio *n;
1569
1570	while (bio) {
1571	n = bio->bi_next;
1572	bio->bi_next = NULL;
1573	submit_bio_noacct(bio);
1574	bio = n;
1575	}
1576	}
1577
1578	static int do_origin(struct dm_dev *origin, struct bio *bio, bool limit);
1579
1580	/*
1581	* Flush a list of buffers.
1582	*/
1583	static void retry_origin_bios(struct dm_snapshot *s, struct bio *bio)
1584	{
1585	struct bio *n;
1586	int r;
1587
1588	while (bio) {
1589	n = bio->bi_next;
1590	bio->bi_next = NULL;
1591	r = do_origin(origin: s->origin, bio, limit: false);
1592	if (r == DM_MAPIO_REMAPPED)
1593	submit_bio_noacct(bio);
1594	bio = n;
1595	}
1596	}
1597
1598	/*
1599	* Error a list of buffers.
1600	*/
1601	static void error_bios(struct bio *bio)
1602	{
1603	struct bio *n;
1604
1605	while (bio) {
1606	n = bio->bi_next;
1607	bio->bi_next = NULL;
1608	bio_io_error(bio);
1609	bio = n;
1610	}
1611	}
1612
1613	static void __invalidate_snapshot(struct dm_snapshot *s, int err)
1614	{
1615	if (!s->valid)
1616	return;
1617
1618	if (err == -EIO)
1619	DMERR("Invalidating snapshot: Error reading/writing.");
1620	else if (err == -ENOMEM)
1621	DMERR("Invalidating snapshot: Unable to allocate exception.");
1622
1623	if (s->store->type->drop_snapshot)
1624	s->store->type->drop_snapshot(s->store);
1625
1626	s->valid = 0;
1627
1628	dm_table_event(t: s->ti->table);
1629	}
1630
1631	static void invalidate_snapshot(struct dm_snapshot *s, int err)
1632	{
1633	down_write(sem: &s->lock);
1634	__invalidate_snapshot(s, err);
1635	up_write(sem: &s->lock);
1636	}
1637
1638	static void pending_complete(void *context, int success)
1639	{
1640	struct dm_snap_pending_exception *pe = context;
1641	struct dm_exception *e;
1642	struct dm_snapshot *s = pe->snap;
1643	struct bio *origin_bios = NULL;
1644	struct bio *snapshot_bios = NULL;
1645	struct bio *full_bio = NULL;
1646	struct dm_exception_table_lock lock;
1647	int error = 0;
1648
1649	dm_exception_table_lock_init(s, chunk: pe->e.old_chunk, lock: &lock);
1650
1651	if (!success) {
1652	/* Read/write error - snapshot is unusable */
1653	invalidate_snapshot(s, err: -EIO);
1654	error = 1;
1655
1656	dm_exception_table_lock(lock: &lock);
1657	goto out;
1658	}
1659
1660	e = alloc_completed_exception(GFP_NOIO);
1661	if (!e) {
1662	invalidate_snapshot(s, err: -ENOMEM);
1663	error = 1;
1664
1665	dm_exception_table_lock(lock: &lock);
1666	goto out;
1667	}
1668	*e = pe->e;
1669
1670	down_read(sem: &s->lock);
1671	dm_exception_table_lock(lock: &lock);
1672	if (!s->valid) {
1673	up_read(sem: &s->lock);
1674	free_completed_exception(e);
1675	error = 1;
1676
1677	goto out;
1678	}
1679
1680	/*
1681	* Add a proper exception. After inserting the completed exception all
1682	* subsequent snapshot reads to this chunk will be redirected to the
1683	* COW device. This ensures that we do not starve. Moreover, as long
1684	* as the pending exception exists, neither origin writes nor snapshot
1685	* merging can overwrite the chunk in origin.
1686	*/
1687	dm_insert_exception(eh: &s->complete, new_e: e);
1688	up_read(sem: &s->lock);
1689
1690	/* Wait for conflicting reads to drain */
1691	if (__chunk_is_tracked(s, chunk: pe->e.old_chunk)) {
1692	dm_exception_table_unlock(lock: &lock);
1693	__check_for_conflicting_io(s, chunk: pe->e.old_chunk);
1694	dm_exception_table_lock(lock: &lock);
1695	}
1696
1697	out:
1698	/* Remove the in-flight exception from the list */
1699	dm_remove_exception(e: &pe->e);
1700
1701	dm_exception_table_unlock(lock: &lock);
1702
1703	snapshot_bios = bio_list_get(bl: &pe->snapshot_bios);
1704	origin_bios = bio_list_get(bl: &pe->origin_bios);
1705	full_bio = pe->full_bio;
1706	if (full_bio)
1707	full_bio->bi_end_io = pe->full_bio_end_io;
1708	increment_pending_exceptions_done_count();
1709
1710	/* Submit any pending write bios */
1711	if (error) {
1712	if (full_bio)
1713	bio_io_error(bio: full_bio);
1714	error_bios(bio: snapshot_bios);
1715	} else {
1716	if (full_bio)
1717	bio_endio(full_bio);
1718	flush_bios(bio: snapshot_bios);
1719	}
1720
1721	retry_origin_bios(s, bio: origin_bios);
1722
1723	free_pending_exception(pe);
1724	}
1725
1726	static void complete_exception(struct dm_snap_pending_exception *pe)
1727	{
1728	struct dm_snapshot *s = pe->snap;
1729
1730	/* Update the metadata if we are persistent */
1731	s->store->type->commit_exception(s->store, &pe->e, !pe->copy_error,
1732	pending_complete, pe);
1733	}
1734
1735	/*
1736	* Called when the copy I/O has finished. kcopyd actually runs
1737	* this code so don't block.
1738	*/
1739	static void copy_callback(int read_err, unsigned long write_err, void *context)
1740	{
1741	struct dm_snap_pending_exception *pe = context;
1742	struct dm_snapshot *s = pe->snap;
1743
1744	pe->copy_error = read_err || write_err;
1745
1746	if (pe->exception_sequence == s->exception_complete_sequence) {
1747	struct rb_node *next;
1748
1749	s->exception_complete_sequence++;
1750	complete_exception(pe);
1751
1752	next = rb_first(root: &s->out_of_order_tree);
1753	while (next) {
1754	pe = rb_entry(next, struct dm_snap_pending_exception,
1755	out_of_order_node);
1756	if (pe->exception_sequence != s->exception_complete_sequence)
1757	break;
1758	next = rb_next(next);
1759	s->exception_complete_sequence++;
1760	rb_erase(&pe->out_of_order_node, &s->out_of_order_tree);
1761	complete_exception(pe);
1762	cond_resched();
1763	}
1764	} else {
1765	struct rb_node *parent = NULL;
1766	struct rb_node **p = &s->out_of_order_tree.rb_node;
1767	struct dm_snap_pending_exception *pe2;
1768
1769	while (*p) {
1770	pe2 = rb_entry(*p, struct dm_snap_pending_exception, out_of_order_node);
1771	parent = *p;
1772
1773	BUG_ON(pe->exception_sequence == pe2->exception_sequence);
1774	if (pe->exception_sequence < pe2->exception_sequence)
1775	p = &((*p)->rb_left);
1776	else
1777	p = &((*p)->rb_right);
1778	}
1779
1780	rb_link_node(node: &pe->out_of_order_node, parent, rb_link: p);
1781	rb_insert_color(&pe->out_of_order_node, &s->out_of_order_tree);
1782	}
1783	account_end_copy(s);
1784	}
1785
1786	/*
1787	* Dispatches the copy operation to kcopyd.
1788	*/
1789	static void start_copy(struct dm_snap_pending_exception *pe)
1790	{
1791	struct dm_snapshot *s = pe->snap;
1792	struct dm_io_region src, dest;
1793	struct block_device *bdev = s->origin->bdev;
1794	sector_t dev_size;
1795
1796	dev_size = get_dev_size(bdev);
1797
1798	src.bdev = bdev;
1799	src.sector = chunk_to_sector(store: s->store, chunk: pe->e.old_chunk);
1800	src.count = min((sector_t)s->store->chunk_size, dev_size - src.sector);
1801
1802	dest.bdev = s->cow->bdev;
1803	dest.sector = chunk_to_sector(store: s->store, chunk: pe->e.new_chunk);
1804	dest.count = src.count;
1805
1806	/* Hand over to kcopyd */
1807	account_start_copy(s);
1808	dm_kcopyd_copy(kc: s->kcopyd_client, from: &src, num_dests: 1, dests: &dest, flags: 0, fn: copy_callback, context: pe);
1809	}
1810
1811	static void full_bio_end_io(struct bio *bio)
1812	{
1813	void *callback_data = bio->bi_private;
1814
1815	dm_kcopyd_do_callback(job: callback_data, read_err: 0, write_err: bio->bi_status ? 1 : 0);
1816	}
1817
1818	static void start_full_bio(struct dm_snap_pending_exception *pe,
1819	struct bio *bio)
1820	{
1821	struct dm_snapshot *s = pe->snap;
1822	void *callback_data;
1823
1824	pe->full_bio = bio;
1825	pe->full_bio_end_io = bio->bi_end_io;
1826
1827	account_start_copy(s);
1828	callback_data = dm_kcopyd_prepare_callback(kc: s->kcopyd_client,
1829	fn: copy_callback, context: pe);
1830
1831	bio->bi_end_io = full_bio_end_io;
1832	bio->bi_private = callback_data;
1833
1834	submit_bio_noacct(bio);
1835	}
1836
1837	static struct dm_snap_pending_exception *
1838	__lookup_pending_exception(struct dm_snapshot *s, chunk_t chunk)
1839	{
1840	struct dm_exception *e = dm_lookup_exception(et: &s->pending, chunk);
1841
1842	if (!e)
1843	return NULL;
1844
1845	return container_of(e, struct dm_snap_pending_exception, e);
1846	}
1847
1848	/*
1849	* Inserts a pending exception into the pending table.
1850	*
1851	* NOTE: a write lock must be held on the chunk's pending exception table slot
1852	* before calling this.
1853	*/
1854	static struct dm_snap_pending_exception *
1855	__insert_pending_exception(struct dm_snapshot *s,
1856	struct dm_snap_pending_exception *pe, chunk_t chunk)
1857	{
1858	pe->e.old_chunk = chunk;
1859	bio_list_init(bl: &pe->origin_bios);
1860	bio_list_init(bl: &pe->snapshot_bios);
1861	pe->started = 0;
1862	pe->full_bio = NULL;
1863
1864	spin_lock(lock: &s->pe_allocation_lock);
1865	if (s->store->type->prepare_exception(s->store, &pe->e)) {
1866	spin_unlock(lock: &s->pe_allocation_lock);
1867	free_pending_exception(pe);
1868	return NULL;
1869	}
1870
1871	pe->exception_sequence = s->exception_start_sequence++;
1872	spin_unlock(lock: &s->pe_allocation_lock);
1873
1874	dm_insert_exception(eh: &s->pending, new_e: &pe->e);
1875
1876	return pe;
1877	}
1878
1879	/*
1880	* Looks to see if this snapshot already has a pending exception
1881	* for this chunk, otherwise it allocates a new one and inserts
1882	* it into the pending table.
1883	*
1884	* NOTE: a write lock must be held on the chunk's pending exception table slot
1885	* before calling this.
1886	*/
1887	static struct dm_snap_pending_exception *
1888	__find_pending_exception(struct dm_snapshot *s,
1889	struct dm_snap_pending_exception *pe, chunk_t chunk)
1890	{
1891	struct dm_snap_pending_exception *pe2;
1892
1893	pe2 = __lookup_pending_exception(s, chunk);
1894	if (pe2) {
1895	free_pending_exception(pe);
1896	return pe2;
1897	}
1898
1899	return __insert_pending_exception(s, pe, chunk);
1900	}
1901
1902	static void remap_exception(struct dm_snapshot *s, struct dm_exception *e,
1903	struct bio *bio, chunk_t chunk)
1904	{
1905	bio_set_dev(bio, bdev: s->cow->bdev);
1906	bio->bi_iter.bi_sector =
1907	chunk_to_sector(store: s->store, chunk: dm_chunk_number(chunk: e->new_chunk) +
1908	(chunk - e->old_chunk)) +
1909	(bio->bi_iter.bi_sector & s->store->chunk_mask);
1910	}
1911
1912	static void zero_callback(int read_err, unsigned long write_err, void *context)
1913	{
1914	struct bio *bio = context;
1915	struct dm_snapshot *s = bio->bi_private;
1916
1917	account_end_copy(s);
1918	bio->bi_status = write_err ? BLK_STS_IOERR : 0;
1919	bio_endio(bio);
1920	}
1921
1922	static void zero_exception(struct dm_snapshot *s, struct dm_exception *e,
1923	struct bio *bio, chunk_t chunk)
1924	{
1925	struct dm_io_region dest;
1926
1927	dest.bdev = s->cow->bdev;
1928	dest.sector = bio->bi_iter.bi_sector;
1929	dest.count = s->store->chunk_size;
1930
1931	account_start_copy(s);
1932	WARN_ON_ONCE(bio->bi_private);
1933	bio->bi_private = s;
1934	dm_kcopyd_zero(kc: s->kcopyd_client, num_dests: 1, dests: &dest, flags: 0, fn: zero_callback, context: bio);
1935	}
1936
1937	static bool io_overlaps_chunk(struct dm_snapshot *s, struct bio *bio)
1938	{
1939	return bio->bi_iter.bi_size ==
1940	(s->store->chunk_size << SECTOR_SHIFT);
1941	}
1942
1943	static int snapshot_map(struct dm_target *ti, struct bio *bio)
1944	{
1945	struct dm_exception *e;
1946	struct dm_snapshot *s = ti->private;
1947	int r = DM_MAPIO_REMAPPED;
1948	chunk_t chunk;
1949	struct dm_snap_pending_exception *pe = NULL;
1950	struct dm_exception_table_lock lock;
1951
1952	init_tracked_chunk(bio);
1953
1954	if (bio->bi_opf & REQ_PREFLUSH) {
1955	bio_set_dev(bio, bdev: s->cow->bdev);
1956	return DM_MAPIO_REMAPPED;
1957	}
1958
1959	chunk = sector_to_chunk(store: s->store, sector: bio->bi_iter.bi_sector);
1960	dm_exception_table_lock_init(s, chunk, lock: &lock);
1961
1962	/* Full snapshots are not usable */
1963	/* To get here the table must be live so s->active is always set. */
1964	if (!s->valid)
1965	return DM_MAPIO_KILL;
1966
1967	if (bio_data_dir(bio) == WRITE) {
1968	while (unlikely(!wait_for_in_progress(s, false)))
1969	; /* wait_for_in_progress() has slept */
1970	}
1971
1972	down_read(sem: &s->lock);
1973	dm_exception_table_lock(lock: &lock);
1974
1975	if (!s->valid || (unlikely(s->snapshot_overflowed) &&
1976	bio_data_dir(bio) == WRITE)) {
1977	r = DM_MAPIO_KILL;
1978	goto out_unlock;
1979	}
1980
1981	if (unlikely(bio_op(bio) == REQ_OP_DISCARD)) {
1982	if (s->discard_passdown_origin && dm_bio_get_target_bio_nr(bio)) {
1983	/*
1984	* passdown discard to origin (without triggering
1985	* snapshot exceptions via do_origin; doing so would
1986	* defeat the goal of freeing space in origin that is
1987	* implied by the "discard_passdown_origin" feature)
1988	*/
1989	bio_set_dev(bio, bdev: s->origin->bdev);
1990	track_chunk(s, bio, chunk);
1991	goto out_unlock;
1992	}
1993	/* discard to snapshot (target_bio_nr == 0) zeroes exceptions */
1994	}
1995
1996	/* If the block is already remapped - use that, else remap it */
1997	e = dm_lookup_exception(et: &s->complete, chunk);
1998	if (e) {
1999	remap_exception(s, e, bio, chunk);
2000	if (unlikely(bio_op(bio) == REQ_OP_DISCARD) &&
2001	io_overlaps_chunk(s, bio)) {
2002	dm_exception_table_unlock(lock: &lock);
2003	up_read(sem: &s->lock);
2004	zero_exception(s, e, bio, chunk);
2005	r = DM_MAPIO_SUBMITTED; /* discard is not issued */
2006	goto out;
2007	}
2008	goto out_unlock;
2009	}
2010
2011	if (unlikely(bio_op(bio) == REQ_OP_DISCARD)) {
2012	/*
2013	* If no exception exists, complete discard immediately
2014	* otherwise it'll trigger copy-out.
2015	*/
2016	bio_endio(bio);
2017	r = DM_MAPIO_SUBMITTED;
2018	goto out_unlock;
2019	}
2020
2021	/*
2022	* Write to snapshot - higher level takes care of RW/RO
2023	* flags so we should only get this if we are
2024	* writable.
2025	*/
2026	if (bio_data_dir(bio) == WRITE) {
2027	pe = __lookup_pending_exception(s, chunk);
2028	if (!pe) {
2029	dm_exception_table_unlock(lock: &lock);
2030	pe = alloc_pending_exception(s);
2031	dm_exception_table_lock(lock: &lock);
2032
2033	e = dm_lookup_exception(et: &s->complete, chunk);
2034	if (e) {
2035	free_pending_exception(pe);
2036	remap_exception(s, e, bio, chunk);
2037	goto out_unlock;
2038	}
2039
2040	pe = __find_pending_exception(s, pe, chunk);
2041	if (!pe) {
2042	dm_exception_table_unlock(lock: &lock);
2043	up_read(sem: &s->lock);
2044
2045	down_write(sem: &s->lock);
2046
2047	if (s->store->userspace_supports_overflow) {
2048	if (s->valid && !s->snapshot_overflowed) {
2049	s->snapshot_overflowed = 1;
2050	DMERR("Snapshot overflowed: Unable to allocate exception.");
2051	}
2052	} else
2053	__invalidate_snapshot(s, err: -ENOMEM);
2054	up_write(sem: &s->lock);
2055
2056	r = DM_MAPIO_KILL;
2057	goto out;
2058	}
2059	}
2060
2061	remap_exception(s, e: &pe->e, bio, chunk);
2062
2063	r = DM_MAPIO_SUBMITTED;
2064
2065	if (!pe->started && io_overlaps_chunk(s, bio)) {
2066	pe->started = 1;
2067
2068	dm_exception_table_unlock(lock: &lock);
2069	up_read(sem: &s->lock);
2070
2071	start_full_bio(pe, bio);
2072	goto out;
2073	}
2074
2075	bio_list_add(bl: &pe->snapshot_bios, bio);
2076
2077	if (!pe->started) {
2078	/* this is protected by the exception table lock */
2079	pe->started = 1;
2080
2081	dm_exception_table_unlock(lock: &lock);
2082	up_read(sem: &s->lock);
2083
2084	start_copy(pe);
2085	goto out;
2086	}
2087	} else {
2088	bio_set_dev(bio, bdev: s->origin->bdev);
2089	track_chunk(s, bio, chunk);
2090	}
2091
2092	out_unlock:
2093	dm_exception_table_unlock(lock: &lock);
2094	up_read(sem: &s->lock);
2095	out:
2096	return r;
2097	}
2098
2099	/*
2100	* A snapshot-merge target behaves like a combination of a snapshot
2101	* target and a snapshot-origin target. It only generates new
2102	* exceptions in other snapshots and not in the one that is being
2103	* merged.
2104	*
2105	* For each chunk, if there is an existing exception, it is used to
2106	* redirect I/O to the cow device. Otherwise I/O is sent to the origin,
2107	* which in turn might generate exceptions in other snapshots.
2108	* If merging is currently taking place on the chunk in question, the
2109	* I/O is deferred by adding it to s->bios_queued_during_merge.
2110	*/
2111	static int snapshot_merge_map(struct dm_target *ti, struct bio *bio)
2112	{
2113	struct dm_exception *e;
2114	struct dm_snapshot *s = ti->private;
2115	int r = DM_MAPIO_REMAPPED;
2116	chunk_t chunk;
2117
2118	init_tracked_chunk(bio);
2119
2120	if (bio->bi_opf & REQ_PREFLUSH) {
2121	if (!dm_bio_get_target_bio_nr(bio))
2122	bio_set_dev(bio, bdev: s->origin->bdev);
2123	else
2124	bio_set_dev(bio, bdev: s->cow->bdev);
2125	return DM_MAPIO_REMAPPED;
2126	}
2127
2128	if (unlikely(bio_op(bio) == REQ_OP_DISCARD)) {
2129	/* Once merging, discards no longer effect change */
2130	bio_endio(bio);
2131	return DM_MAPIO_SUBMITTED;
2132	}
2133
2134	chunk = sector_to_chunk(store: s->store, sector: bio->bi_iter.bi_sector);
2135
2136	down_write(sem: &s->lock);
2137
2138	/* Full merging snapshots are redirected to the origin */
2139	if (!s->valid)
2140	goto redirect_to_origin;
2141
2142	/* If the block is already remapped - use that */
2143	e = dm_lookup_exception(et: &s->complete, chunk);
2144	if (e) {
2145	/* Queue writes overlapping with chunks being merged */
2146	if (bio_data_dir(bio) == WRITE &&
2147	chunk >= s->first_merging_chunk &&
2148	chunk < (s->first_merging_chunk +
2149	s->num_merging_chunks)) {
2150	bio_set_dev(bio, bdev: s->origin->bdev);
2151	bio_list_add(bl: &s->bios_queued_during_merge, bio);
2152	r = DM_MAPIO_SUBMITTED;
2153	goto out_unlock;
2154	}
2155
2156	remap_exception(s, e, bio, chunk);
2157
2158	if (bio_data_dir(bio) == WRITE)
2159	track_chunk(s, bio, chunk);
2160	goto out_unlock;
2161	}
2162
2163	redirect_to_origin:
2164	bio_set_dev(bio, bdev: s->origin->bdev);
2165
2166	if (bio_data_dir(bio) == WRITE) {
2167	up_write(sem: &s->lock);
2168	return do_origin(origin: s->origin, bio, limit: false);
2169	}
2170
2171	out_unlock:
2172	up_write(sem: &s->lock);
2173
2174	return r;
2175	}
2176
2177	static int snapshot_end_io(struct dm_target *ti, struct bio *bio,
2178	blk_status_t *error)
2179	{
2180	struct dm_snapshot *s = ti->private;
2181
2182	if (is_bio_tracked(bio))
2183	stop_tracking_chunk(s, bio);
2184
2185	return DM_ENDIO_DONE;
2186	}
2187
2188	static void snapshot_merge_presuspend(struct dm_target *ti)
2189	{
2190	struct dm_snapshot *s = ti->private;
2191
2192	stop_merge(s);
2193	}
2194
2195	static int snapshot_preresume(struct dm_target *ti)
2196	{
2197	int r = 0;
2198	struct dm_snapshot *s = ti->private;
2199	struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
2200
2201	down_read(sem: &_origins_lock);
2202	(void) __find_snapshots_sharing_cow(snap: s, snap_src: &snap_src, snap_dest: &snap_dest, NULL);
2203	if (snap_src && snap_dest) {
2204	down_read(sem: &snap_src->lock);
2205	if (s == snap_src) {
2206	DMERR("Unable to resume snapshot source until handover completes.");
2207	r = -EINVAL;
2208	} else if (!dm_suspended(ti: snap_src->ti)) {
2209	DMERR("Unable to perform snapshot handover until source is suspended.");
2210	r = -EINVAL;
2211	}
2212	up_read(sem: &snap_src->lock);
2213	}
2214	up_read(sem: &_origins_lock);
2215
2216	return r;
2217	}
2218
2219	static void snapshot_resume(struct dm_target *ti)
2220	{
2221	struct dm_snapshot *s = ti->private;
2222	struct dm_snapshot *snap_src = NULL, *snap_dest = NULL, *snap_merging = NULL;
2223	struct dm_origin *o;
2224	struct mapped_device *origin_md = NULL;
2225	bool must_restart_merging = false;
2226
2227	down_read(sem: &_origins_lock);
2228
2229	o = __lookup_dm_origin(origin: s->origin->bdev);
2230	if (o)
2231	origin_md = dm_table_get_md(t: o->ti->table);
2232	if (!origin_md) {
2233	(void) __find_snapshots_sharing_cow(snap: s, NULL, NULL, snap_merge: &snap_merging);
2234	if (snap_merging)
2235	origin_md = dm_table_get_md(t: snap_merging->ti->table);
2236	}
2237	if (origin_md == dm_table_get_md(t: ti->table))
2238	origin_md = NULL;
2239	if (origin_md) {
2240	if (dm_hold(md: origin_md))
2241	origin_md = NULL;
2242	}
2243
2244	up_read(sem: &_origins_lock);
2245
2246	if (origin_md) {
2247	dm_internal_suspend_fast(md: origin_md);
2248	if (snap_merging && test_bit(RUNNING_MERGE, &snap_merging->state_bits)) {
2249	must_restart_merging = true;
2250	stop_merge(s: snap_merging);
2251	}
2252	}
2253
2254	down_read(sem: &_origins_lock);
2255
2256	(void) __find_snapshots_sharing_cow(snap: s, snap_src: &snap_src, snap_dest: &snap_dest, NULL);
2257	if (snap_src && snap_dest) {
2258	down_write(sem: &snap_src->lock);
2259	down_write_nested(sem: &snap_dest->lock, SINGLE_DEPTH_NESTING);
2260	__handover_exceptions(snap_src, snap_dest);
2261	up_write(sem: &snap_dest->lock);
2262	up_write(sem: &snap_src->lock);
2263	}
2264
2265	up_read(sem: &_origins_lock);
2266
2267	if (origin_md) {
2268	if (must_restart_merging)
2269	start_merge(s: snap_merging);
2270	dm_internal_resume_fast(md: origin_md);
2271	dm_put(md: origin_md);
2272	}
2273
2274	/* Now we have correct chunk size, reregister */
2275	reregister_snapshot(s);
2276
2277	down_write(sem: &s->lock);
2278	s->active = 1;
2279	up_write(sem: &s->lock);
2280	}
2281
2282	static uint32_t get_origin_minimum_chunksize(struct block_device *bdev)
2283	{
2284	uint32_t min_chunksize;
2285
2286	down_read(sem: &_origins_lock);
2287	min_chunksize = __minimum_chunk_size(o: __lookup_origin(origin: bdev));
2288	up_read(sem: &_origins_lock);
2289
2290	return min_chunksize;
2291	}
2292
2293	static void snapshot_merge_resume(struct dm_target *ti)
2294	{
2295	struct dm_snapshot *s = ti->private;
2296
2297	/*
2298	* Handover exceptions from existing snapshot.
2299	*/
2300	snapshot_resume(ti);
2301
2302	/*
2303	* snapshot-merge acts as an origin, so set ti->max_io_len
2304	*/
2305	ti->max_io_len = get_origin_minimum_chunksize(bdev: s->origin->bdev);
2306
2307	start_merge(s);
2308	}
2309
2310	static void snapshot_status(struct dm_target *ti, status_type_t type,
2311	unsigned int status_flags, char *result, unsigned int maxlen)
2312	{
2313	unsigned int sz = 0;
2314	struct dm_snapshot *snap = ti->private;
2315	unsigned int num_features;
2316
2317	switch (type) {
2318	case STATUSTYPE_INFO:
2319
2320	down_write(sem: &snap->lock);
2321
2322	if (!snap->valid)
2323	DMEMIT("Invalid");
2324	else if (snap->merge_failed)
2325	DMEMIT("Merge failed");
2326	else if (snap->snapshot_overflowed)
2327	DMEMIT("Overflow");
2328	else {
2329	if (snap->store->type->usage) {
2330	sector_t total_sectors, sectors_allocated,
2331	metadata_sectors;
2332	snap->store->type->usage(snap->store,
2333	&total_sectors,
2334	&sectors_allocated,
2335	&metadata_sectors);
2336	DMEMIT("%llu/%llu %llu",
2337	(unsigned long long)sectors_allocated,
2338	(unsigned long long)total_sectors,
2339	(unsigned long long)metadata_sectors);
2340	} else
2341	DMEMIT("Unknown");
2342	}
2343
2344	up_write(sem: &snap->lock);
2345
2346	break;
2347
2348	case STATUSTYPE_TABLE:
2349	/*
2350	* kdevname returns a static pointer so we need
2351	* to make private copies if the output is to
2352	* make sense.
2353	*/
2354	DMEMIT("%s %s", snap->origin->name, snap->cow->name);
2355	sz += snap->store->type->status(snap->store, type, result + sz,
2356	maxlen - sz);
2357	num_features = snap->discard_zeroes_cow + snap->discard_passdown_origin;
2358	if (num_features) {
2359	DMEMIT(" %u", num_features);
2360	if (snap->discard_zeroes_cow)
2361	DMEMIT(" discard_zeroes_cow");
2362	if (snap->discard_passdown_origin)
2363	DMEMIT(" discard_passdown_origin");
2364	}
2365	break;
2366
2367	case STATUSTYPE_IMA:
2368	DMEMIT_TARGET_NAME_VERSION(ti->type);
2369	DMEMIT(",snap_origin_name=%s", snap->origin->name);
2370	DMEMIT(",snap_cow_name=%s", snap->cow->name);
2371	DMEMIT(",snap_valid=%c", snap->valid ? 'y' : 'n');
2372	DMEMIT(",snap_merge_failed=%c", snap->merge_failed ? 'y' : 'n');
2373	DMEMIT(",snapshot_overflowed=%c", snap->snapshot_overflowed ? 'y' : 'n');
2374	DMEMIT(";");
2375	break;
2376	}
2377	}
2378
2379	static int snapshot_iterate_devices(struct dm_target *ti,
2380	iterate_devices_callout_fn fn, void *data)
2381	{
2382	struct dm_snapshot *snap = ti->private;
2383	int r;
2384
2385	r = fn(ti, snap->origin, 0, ti->len, data);
2386
2387	if (!r)
2388	r = fn(ti, snap->cow, 0, get_dev_size(bdev: snap->cow->bdev), data);
2389
2390	return r;
2391	}
2392
2393	static void snapshot_io_hints(struct dm_target *ti, struct queue_limits *limits)
2394	{
2395	struct dm_snapshot *snap = ti->private;
2396
2397	if (snap->discard_zeroes_cow) {
2398	struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
2399
2400	down_read(sem: &_origins_lock);
2401
2402	(void) __find_snapshots_sharing_cow(snap, snap_src: &snap_src, snap_dest: &snap_dest, NULL);
2403	if (snap_src && snap_dest)
2404	snap = snap_src;
2405
2406	/* All discards are split on chunk_size boundary */
2407	limits->discard_granularity = snap->store->chunk_size;
2408	limits->max_hw_discard_sectors = snap->store->chunk_size;
2409
2410	up_read(sem: &_origins_lock);
2411	}
2412	}
2413
2414	/*
2415	*---------------------------------------------------------------
2416	* Origin methods
2417	*---------------------------------------------------------------
2418	*/
2419	/*
2420	* If no exceptions need creating, DM_MAPIO_REMAPPED is returned and any
2421	* supplied bio was ignored. The caller may submit it immediately.
2422	* (No remapping actually occurs as the origin is always a direct linear
2423	* map.)
2424	*
2425	* If further exceptions are required, DM_MAPIO_SUBMITTED is returned
2426	* and any supplied bio is added to a list to be submitted once all
2427	* the necessary exceptions exist.
2428	*/
2429	static int __origin_write(struct list_head *snapshots, sector_t sector,
2430	struct bio *bio)
2431	{
2432	int r = DM_MAPIO_REMAPPED;
2433	struct dm_snapshot *snap;
2434	struct dm_exception *e;
2435	struct dm_snap_pending_exception *pe, *pe2;
2436	struct dm_snap_pending_exception *pe_to_start_now = NULL;
2437	struct dm_snap_pending_exception *pe_to_start_last = NULL;
2438	struct dm_exception_table_lock lock;
2439	chunk_t chunk;
2440
2441	/* Do all the snapshots on this origin */
2442	list_for_each_entry(snap, snapshots, list) {
2443	/*
2444	* Don't make new exceptions in a merging snapshot
2445	* because it has effectively been deleted
2446	*/
2447	if (dm_target_is_snapshot_merge(snap->ti))
2448	continue;
2449
2450	/* Nothing to do if writing beyond end of snapshot */
2451	if (sector >= dm_table_get_size(t: snap->ti->table))
2452	continue;
2453
2454	/*
2455	* Remember, different snapshots can have
2456	* different chunk sizes.
2457	*/
2458	chunk = sector_to_chunk(store: snap->store, sector);
2459	dm_exception_table_lock_init(s: snap, chunk, lock: &lock);
2460
2461	down_read(sem: &snap->lock);
2462	dm_exception_table_lock(lock: &lock);
2463
2464	/* Only deal with valid and active snapshots */
2465	if (!snap->valid || !snap->active)
2466	goto next_snapshot;
2467
2468	pe = __lookup_pending_exception(s: snap, chunk);
2469	if (!pe) {
2470	/*
2471	* Check exception table to see if block is already
2472	* remapped in this snapshot and trigger an exception
2473	* if not.
2474	*/
2475	e = dm_lookup_exception(et: &snap->complete, chunk);
2476	if (e)
2477	goto next_snapshot;
2478
2479	dm_exception_table_unlock(lock: &lock);
2480	pe = alloc_pending_exception(s: snap);
2481	dm_exception_table_lock(lock: &lock);
2482
2483	pe2 = __lookup_pending_exception(s: snap, chunk);
2484
2485	if (!pe2) {
2486	e = dm_lookup_exception(et: &snap->complete, chunk);
2487	if (e) {
2488	free_pending_exception(pe);
2489	goto next_snapshot;
2490	}
2491
2492	pe = __insert_pending_exception(s: snap, pe, chunk);
2493	if (!pe) {
2494	dm_exception_table_unlock(lock: &lock);
2495	up_read(sem: &snap->lock);
2496
2497	invalidate_snapshot(s: snap, err: -ENOMEM);
2498	continue;
2499	}
2500	} else {
2501	free_pending_exception(pe);
2502	pe = pe2;
2503	}
2504	}
2505
2506	r = DM_MAPIO_SUBMITTED;
2507
2508	/*
2509	* If an origin bio was supplied, queue it to wait for the
2510	* completion of this exception, and start this one last,
2511	* at the end of the function.
2512	*/
2513	if (bio) {
2514	bio_list_add(bl: &pe->origin_bios, bio);
2515	bio = NULL;
2516
2517	if (!pe->started) {
2518	pe->started = 1;
2519	pe_to_start_last = pe;
2520	}
2521	}
2522
2523	if (!pe->started) {
2524	pe->started = 1;
2525	pe_to_start_now = pe;
2526	}
2527
2528	next_snapshot:
2529	dm_exception_table_unlock(lock: &lock);
2530	up_read(sem: &snap->lock);
2531
2532	if (pe_to_start_now) {
2533	start_copy(pe: pe_to_start_now);
2534	pe_to_start_now = NULL;
2535	}
2536	}
2537
2538	/*
2539	* Submit the exception against which the bio is queued last,
2540	* to give the other exceptions a head start.
2541	*/
2542	if (pe_to_start_last)
2543	start_copy(pe: pe_to_start_last);
2544
2545	return r;
2546	}
2547
2548	/*
2549	* Called on a write from the origin driver.
2550	*/
2551	static int do_origin(struct dm_dev *origin, struct bio *bio, bool limit)
2552	{
2553	struct origin *o;
2554	int r = DM_MAPIO_REMAPPED;
2555
2556	again:
2557	down_read(sem: &_origins_lock);
2558	o = __lookup_origin(origin: origin->bdev);
2559	if (o) {
2560	if (limit) {
2561	struct dm_snapshot *s;
2562
2563	list_for_each_entry(s, &o->snapshots, list)
2564	if (unlikely(!wait_for_in_progress(s, true)))
2565	goto again;
2566	}
2567
2568	r = __origin_write(snapshots: &o->snapshots, sector: bio->bi_iter.bi_sector, bio);
2569	}
2570	up_read(sem: &_origins_lock);
2571
2572	return r;
2573	}
2574
2575	/*
2576	* Trigger exceptions in all non-merging snapshots.
2577	*
2578	* The chunk size of the merging snapshot may be larger than the chunk
2579	* size of some other snapshot so we may need to reallocate multiple
2580	* chunks in other snapshots.
2581	*
2582	* We scan all the overlapping exceptions in the other snapshots.
2583	* Returns 1 if anything was reallocated and must be waited for,
2584	* otherwise returns 0.
2585	*
2586	* size must be a multiple of merging_snap's chunk_size.
2587	*/
2588	static int origin_write_extent(struct dm_snapshot *merging_snap,
2589	sector_t sector, unsigned int size)
2590	{
2591	int must_wait = 0;
2592	sector_t n;
2593	struct origin *o;
2594
2595	/*
2596	* The origin's __minimum_chunk_size() got stored in max_io_len
2597	* by snapshot_merge_resume().
2598	*/
2599	down_read(sem: &_origins_lock);
2600	o = __lookup_origin(origin: merging_snap->origin->bdev);
2601	for (n = 0; n < size; n += merging_snap->ti->max_io_len)
2602	if (__origin_write(snapshots: &o->snapshots, sector: sector + n, NULL) ==
2603	DM_MAPIO_SUBMITTED)
2604	must_wait = 1;
2605	up_read(sem: &_origins_lock);
2606
2607	return must_wait;
2608	}
2609
2610	/*
2611	* Origin: maps a linear range of a device, with hooks for snapshotting.
2612	*/
2613
2614	/*
2615	* Construct an origin mapping: <dev_path>
2616	* The context for an origin is merely a 'struct dm_dev *'
2617	* pointing to the real device.
2618	*/
2619	static int origin_ctr(struct dm_target *ti, unsigned int argc, char **argv)
2620	{
2621	int r;
2622	struct dm_origin *o;
2623
2624	if (argc != 1) {
2625	ti->error = "origin: incorrect number of arguments";
2626	return -EINVAL;
2627	}
2628
2629	o = kmalloc(sizeof(struct dm_origin), GFP_KERNEL);
2630	if (!o) {
2631	ti->error = "Cannot allocate private origin structure";
2632	r = -ENOMEM;
2633	goto bad_alloc;
2634	}
2635
2636	r = dm_get_device(ti, path: argv[0], mode: dm_table_get_mode(t: ti->table), result: &o->dev);
2637	if (r) {
2638	ti->error = "Cannot get target device";
2639	goto bad_open;
2640	}
2641
2642	o->ti = ti;
2643	ti->private = o;
2644	ti->num_flush_bios = 1;
2645
2646	return 0;
2647
2648	bad_open:
2649	kfree(objp: o);
2650	bad_alloc:
2651	return r;
2652	}
2653
2654	static void origin_dtr(struct dm_target *ti)
2655	{
2656	struct dm_origin *o = ti->private;
2657
2658	dm_put_device(ti, d: o->dev);
2659	kfree(objp: o);
2660	}
2661
2662	static int origin_map(struct dm_target *ti, struct bio *bio)
2663	{
2664	struct dm_origin *o = ti->private;
2665	unsigned int available_sectors;
2666
2667	bio_set_dev(bio, bdev: o->dev->bdev);
2668
2669	if (unlikely(bio->bi_opf & REQ_PREFLUSH))
2670	return DM_MAPIO_REMAPPED;
2671
2672	if (bio_data_dir(bio) != WRITE)
2673	return DM_MAPIO_REMAPPED;
2674
2675	available_sectors = o->split_boundary -
2676	((unsigned int)bio->bi_iter.bi_sector & (o->split_boundary - 1));
2677
2678	if (bio_sectors(bio) > available_sectors)
2679	dm_accept_partial_bio(bio, n_sectors: available_sectors);
2680
2681	/* Only tell snapshots if this is a write */
2682	return do_origin(origin: o->dev, bio, limit: true);
2683	}
2684
2685	/*
2686	* Set the target "max_io_len" field to the minimum of all the snapshots'
2687	* chunk sizes.
2688	*/
2689	static void origin_resume(struct dm_target *ti)
2690	{
2691	struct dm_origin *o = ti->private;
2692
2693	o->split_boundary = get_origin_minimum_chunksize(bdev: o->dev->bdev);
2694
2695	down_write(sem: &_origins_lock);
2696	__insert_dm_origin(o);
2697	up_write(sem: &_origins_lock);
2698	}
2699
2700	static void origin_postsuspend(struct dm_target *ti)
2701	{
2702	struct dm_origin *o = ti->private;
2703
2704	down_write(sem: &_origins_lock);
2705	__remove_dm_origin(o);
2706	up_write(sem: &_origins_lock);
2707	}
2708
2709	static void origin_status(struct dm_target *ti, status_type_t type,
2710	unsigned int status_flags, char *result, unsigned int maxlen)
2711	{
2712	struct dm_origin *o = ti->private;
2713
2714	switch (type) {
2715	case STATUSTYPE_INFO:
2716	result[0] = '\0';
2717	break;
2718
2719	case STATUSTYPE_TABLE:
2720	snprintf(buf: result, size: maxlen, fmt: "%s", o->dev->name);
2721	break;
2722	case STATUSTYPE_IMA:
2723	result[0] = '\0';
2724	break;
2725	}
2726	}
2727
2728	static int origin_iterate_devices(struct dm_target *ti,
2729	iterate_devices_callout_fn fn, void *data)
2730	{
2731	struct dm_origin *o = ti->private;
2732
2733	return fn(ti, o->dev, 0, ti->len, data);
2734	}
2735
2736	static struct target_type origin_target = {
2737	.name = "snapshot-origin",
2738	.version = {1, 9, 0},
2739	.module = THIS_MODULE,
2740	.ctr = origin_ctr,
2741	.dtr = origin_dtr,
2742	.map = origin_map,
2743	.resume = origin_resume,
2744	.postsuspend = origin_postsuspend,
2745	.status = origin_status,
2746	.iterate_devices = origin_iterate_devices,
2747	};
2748
2749	static struct target_type snapshot_target = {
2750	.name = "snapshot",
2751	.version = {1, 16, 0},
2752	.module = THIS_MODULE,
2753	.ctr = snapshot_ctr,
2754	.dtr = snapshot_dtr,
2755	.map = snapshot_map,
2756	.end_io = snapshot_end_io,
2757	.preresume = snapshot_preresume,
2758	.resume = snapshot_resume,
2759	.status = snapshot_status,
2760	.iterate_devices = snapshot_iterate_devices,
2761	.io_hints = snapshot_io_hints,
2762	};
2763
2764	static struct target_type merge_target = {
2765	.name = dm_snapshot_merge_target_name,
2766	.version = {1, 5, 0},
2767	.module = THIS_MODULE,
2768	.ctr = snapshot_ctr,
2769	.dtr = snapshot_dtr,
2770	.map = snapshot_merge_map,
2771	.end_io = snapshot_end_io,
2772	.presuspend = snapshot_merge_presuspend,
2773	.preresume = snapshot_preresume,
2774	.resume = snapshot_merge_resume,
2775	.status = snapshot_status,
2776	.iterate_devices = snapshot_iterate_devices,
2777	.io_hints = snapshot_io_hints,
2778	};
2779
2780	static int __init dm_snapshot_init(void)
2781	{
2782	int r;
2783
2784	r = dm_exception_store_init();
2785	if (r) {
2786	DMERR("Failed to initialize exception stores");
2787	return r;
2788	}
2789
2790	r = init_origin_hash();
2791	if (r) {
2792	DMERR("init_origin_hash failed.");
2793	goto bad_origin_hash;
2794	}
2795
2796	exception_cache = KMEM_CACHE(dm_exception, 0);
2797	if (!exception_cache) {
2798	DMERR("Couldn't create exception cache.");
2799	r = -ENOMEM;
2800	goto bad_exception_cache;
2801	}
2802
2803	pending_cache = KMEM_CACHE(dm_snap_pending_exception, 0);
2804	if (!pending_cache) {
2805	DMERR("Couldn't create pending cache.");
2806	r = -ENOMEM;
2807	goto bad_pending_cache;
2808	}
2809
2810	r = dm_register_target(t: &snapshot_target);
2811	if (r < 0)
2812	goto bad_register_snapshot_target;
2813
2814	r = dm_register_target(t: &origin_target);
2815	if (r < 0)
2816	goto bad_register_origin_target;
2817
2818	r = dm_register_target(t: &merge_target);
2819	if (r < 0)
2820	goto bad_register_merge_target;
2821
2822	return 0;
2823
2824	bad_register_merge_target:
2825	dm_unregister_target(t: &origin_target);
2826	bad_register_origin_target:
2827	dm_unregister_target(t: &snapshot_target);
2828	bad_register_snapshot_target:
2829	kmem_cache_destroy(s: pending_cache);
2830	bad_pending_cache:
2831	kmem_cache_destroy(s: exception_cache);
2832	bad_exception_cache:
2833	exit_origin_hash();
2834	bad_origin_hash:
2835	dm_exception_store_exit();
2836
2837	return r;
2838	}
2839
2840	static void __exit dm_snapshot_exit(void)
2841	{
2842	dm_unregister_target(t: &snapshot_target);
2843	dm_unregister_target(t: &origin_target);
2844	dm_unregister_target(t: &merge_target);
2845
2846	exit_origin_hash();
2847	kmem_cache_destroy(s: pending_cache);
2848	kmem_cache_destroy(s: exception_cache);
2849
2850	dm_exception_store_exit();
2851	}
2852
2853	/* Module hooks */
2854	module_init(dm_snapshot_init);
2855	module_exit(dm_snapshot_exit);
2856
2857	MODULE_DESCRIPTION(DM_NAME " snapshot target");
2858	MODULE_AUTHOR("Joe Thornber");
2859	MODULE_LICENSE("GPL");
2860	MODULE_ALIAS("dm-snapshot-origin");
2861	MODULE_ALIAS("dm-snapshot-merge");
2862