projects/linux·blob master · refs

2869 lines · 68.1 KiB

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