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