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 §ors_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