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