dm snapshot: avoid allocating exceptions in merge
[linux-2.6.git] / drivers / md / dm-snap.c
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 #include <linux/workqueue.h>
23
24 #include "dm-exception-store.h"
25
26 #define DM_MSG_PREFIX "snapshots"
27
28 static const char dm_snapshot_merge_target_name[] = "snapshot-merge";
29
30 #define dm_target_is_snapshot_merge(ti) \
31         ((ti)->type->name == dm_snapshot_merge_target_name)
32
33 /*
34  * The percentage increment we will wake up users at
35  */
36 #define WAKE_UP_PERCENT 5
37
38 /*
39  * kcopyd priority of snapshot operations
40  */
41 #define SNAPSHOT_COPY_PRIORITY 2
42
43 /*
44  * Reserve 1MB for each snapshot initially (with minimum of 1 page).
45  */
46 #define SNAPSHOT_PAGES (((1UL << 20) >> PAGE_SHIFT) ? : 1)
47
48 /*
49  * The size of the mempool used to track chunks in use.
50  */
51 #define MIN_IOS 256
52
53 #define DM_TRACKED_CHUNK_HASH_SIZE      16
54 #define DM_TRACKED_CHUNK_HASH(x)        ((unsigned long)(x) & \
55                                          (DM_TRACKED_CHUNK_HASH_SIZE - 1))
56
57 struct dm_exception_table {
58         uint32_t hash_mask;
59         unsigned hash_shift;
60         struct list_head *table;
61 };
62
63 struct dm_snapshot {
64         struct rw_semaphore lock;
65
66         struct dm_dev *origin;
67         struct dm_dev *cow;
68
69         struct dm_target *ti;
70
71         /* List of snapshots per Origin */
72         struct list_head list;
73
74         /* You can't use a snapshot if this is 0 (e.g. if full) */
75         int valid;
76
77         /* Origin writes don't trigger exceptions until this is set */
78         int active;
79
80         /* Whether or not owning mapped_device is suspended */
81         int suspended;
82
83         mempool_t *pending_pool;
84
85         atomic_t pending_exceptions_count;
86
87         struct dm_exception_table pending;
88         struct dm_exception_table complete;
89
90         /*
91          * pe_lock protects all pending_exception operations and access
92          * as well as the snapshot_bios list.
93          */
94         spinlock_t pe_lock;
95
96         /* The on disk metadata handler */
97         struct dm_exception_store *store;
98
99         struct dm_kcopyd_client *kcopyd_client;
100
101         /* Queue of snapshot writes for ksnapd to flush */
102         struct bio_list queued_bios;
103         struct work_struct queued_bios_work;
104
105         /* Chunks with outstanding reads */
106         mempool_t *tracked_chunk_pool;
107         spinlock_t tracked_chunk_lock;
108         struct hlist_head tracked_chunk_hash[DM_TRACKED_CHUNK_HASH_SIZE];
109 };
110
111 struct dm_dev *dm_snap_cow(struct dm_snapshot *s)
112 {
113         return s->cow;
114 }
115 EXPORT_SYMBOL(dm_snap_cow);
116
117 static struct workqueue_struct *ksnapd;
118 static void flush_queued_bios(struct work_struct *work);
119
120 static sector_t chunk_to_sector(struct dm_exception_store *store,
121                                 chunk_t chunk)
122 {
123         return chunk << store->chunk_shift;
124 }
125
126 static int bdev_equal(struct block_device *lhs, struct block_device *rhs)
127 {
128         /*
129          * There is only ever one instance of a particular block
130          * device so we can compare pointers safely.
131          */
132         return lhs == rhs;
133 }
134
135 struct dm_snap_pending_exception {
136         struct dm_exception e;
137
138         /*
139          * Origin buffers waiting for this to complete are held
140          * in a bio list
141          */
142         struct bio_list origin_bios;
143         struct bio_list snapshot_bios;
144
145         /* Pointer back to snapshot context */
146         struct dm_snapshot *snap;
147
148         /*
149          * 1 indicates the exception has already been sent to
150          * kcopyd.
151          */
152         int started;
153 };
154
155 /*
156  * Hash table mapping origin volumes to lists of snapshots and
157  * a lock to protect it
158  */
159 static struct kmem_cache *exception_cache;
160 static struct kmem_cache *pending_cache;
161
162 struct dm_snap_tracked_chunk {
163         struct hlist_node node;
164         chunk_t chunk;
165 };
166
167 static struct kmem_cache *tracked_chunk_cache;
168
169 static struct dm_snap_tracked_chunk *track_chunk(struct dm_snapshot *s,
170                                                  chunk_t chunk)
171 {
172         struct dm_snap_tracked_chunk *c = mempool_alloc(s->tracked_chunk_pool,
173                                                         GFP_NOIO);
174         unsigned long flags;
175
176         c->chunk = chunk;
177
178         spin_lock_irqsave(&s->tracked_chunk_lock, flags);
179         hlist_add_head(&c->node,
180                        &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)]);
181         spin_unlock_irqrestore(&s->tracked_chunk_lock, flags);
182
183         return c;
184 }
185
186 static void stop_tracking_chunk(struct dm_snapshot *s,
187                                 struct dm_snap_tracked_chunk *c)
188 {
189         unsigned long flags;
190
191         spin_lock_irqsave(&s->tracked_chunk_lock, flags);
192         hlist_del(&c->node);
193         spin_unlock_irqrestore(&s->tracked_chunk_lock, flags);
194
195         mempool_free(c, s->tracked_chunk_pool);
196 }
197
198 static int __chunk_is_tracked(struct dm_snapshot *s, chunk_t chunk)
199 {
200         struct dm_snap_tracked_chunk *c;
201         struct hlist_node *hn;
202         int found = 0;
203
204         spin_lock_irq(&s->tracked_chunk_lock);
205
206         hlist_for_each_entry(c, hn,
207             &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)], node) {
208                 if (c->chunk == chunk) {
209                         found = 1;
210                         break;
211                 }
212         }
213
214         spin_unlock_irq(&s->tracked_chunk_lock);
215
216         return found;
217 }
218
219 /*
220  * This conflicting I/O is extremely improbable in the caller,
221  * so msleep(1) is sufficient and there is no need for a wait queue.
222  */
223 static void __check_for_conflicting_io(struct dm_snapshot *s, chunk_t chunk)
224 {
225         while (__chunk_is_tracked(s, chunk))
226                 msleep(1);
227 }
228
229 /*
230  * One of these per registered origin, held in the snapshot_origins hash
231  */
232 struct origin {
233         /* The origin device */
234         struct block_device *bdev;
235
236         struct list_head hash_list;
237
238         /* List of snapshots for this origin */
239         struct list_head snapshots;
240 };
241
242 /*
243  * Size of the hash table for origin volumes. If we make this
244  * the size of the minors list then it should be nearly perfect
245  */
246 #define ORIGIN_HASH_SIZE 256
247 #define ORIGIN_MASK      0xFF
248 static struct list_head *_origins;
249 static struct rw_semaphore _origins_lock;
250
251 static int init_origin_hash(void)
252 {
253         int i;
254
255         _origins = kmalloc(ORIGIN_HASH_SIZE * sizeof(struct list_head),
256                            GFP_KERNEL);
257         if (!_origins) {
258                 DMERR("unable to allocate memory");
259                 return -ENOMEM;
260         }
261
262         for (i = 0; i < ORIGIN_HASH_SIZE; i++)
263                 INIT_LIST_HEAD(_origins + i);
264         init_rwsem(&_origins_lock);
265
266         return 0;
267 }
268
269 static void exit_origin_hash(void)
270 {
271         kfree(_origins);
272 }
273
274 static unsigned origin_hash(struct block_device *bdev)
275 {
276         return bdev->bd_dev & ORIGIN_MASK;
277 }
278
279 static struct origin *__lookup_origin(struct block_device *origin)
280 {
281         struct list_head *ol;
282         struct origin *o;
283
284         ol = &_origins[origin_hash(origin)];
285         list_for_each_entry (o, ol, hash_list)
286                 if (bdev_equal(o->bdev, origin))
287                         return o;
288
289         return NULL;
290 }
291
292 static void __insert_origin(struct origin *o)
293 {
294         struct list_head *sl = &_origins[origin_hash(o->bdev)];
295         list_add_tail(&o->hash_list, sl);
296 }
297
298 /*
299  * _origins_lock must be held when calling this function.
300  * Returns number of snapshots registered using the supplied cow device, plus:
301  * snap_src - a snapshot suitable for use as a source of exception handover
302  * snap_dest - a snapshot capable of receiving exception handover.
303  *
304  * Possible return values and states:
305  *   0: NULL, NULL  - first new snapshot
306  *   1: snap_src, NULL - normal snapshot
307  *   2: snap_src, snap_dest  - waiting for handover
308  *   2: snap_src, NULL - handed over, waiting for old to be deleted
309  *   1: NULL, snap_dest - source got destroyed without handover
310  */
311 static int __find_snapshots_sharing_cow(struct dm_snapshot *snap,
312                                         struct dm_snapshot **snap_src,
313                                         struct dm_snapshot **snap_dest)
314 {
315         struct dm_snapshot *s;
316         struct origin *o;
317         int count = 0;
318         int active;
319
320         o = __lookup_origin(snap->origin->bdev);
321         if (!o)
322                 goto out;
323
324         list_for_each_entry(s, &o->snapshots, list) {
325                 if (!bdev_equal(s->cow->bdev, snap->cow->bdev))
326                         continue;
327
328                 down_read(&s->lock);
329                 active = s->active;
330                 up_read(&s->lock);
331
332                 if (active) {
333                         if (snap_src)
334                                 *snap_src = s;
335                 } else if (snap_dest)
336                         *snap_dest = s;
337
338                 count++;
339         }
340
341 out:
342         return count;
343 }
344
345 /*
346  * On success, returns 1 if this snapshot is a handover destination,
347  * otherwise returns 0.
348  */
349 static int __validate_exception_handover(struct dm_snapshot *snap)
350 {
351         struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
352
353         /* Does snapshot need exceptions handed over to it? */
354         if ((__find_snapshots_sharing_cow(snap, &snap_src, &snap_dest) == 2) ||
355             snap_dest) {
356                 snap->ti->error = "Snapshot cow pairing for exception "
357                                   "table handover failed";
358                 return -EINVAL;
359         }
360
361         /*
362          * If no snap_src was found, snap cannot become a handover
363          * destination.
364          */
365         if (!snap_src)
366                 return 0;
367
368         return 1;
369 }
370
371 static void __insert_snapshot(struct origin *o, struct dm_snapshot *s)
372 {
373         struct dm_snapshot *l;
374
375         /* Sort the list according to chunk size, largest-first smallest-last */
376         list_for_each_entry(l, &o->snapshots, list)
377                 if (l->store->chunk_size < s->store->chunk_size)
378                         break;
379         list_add_tail(&s->list, &l->list);
380 }
381
382 /*
383  * Make a note of the snapshot and its origin so we can look it
384  * up when the origin has a write on it.
385  *
386  * Also validate snapshot exception store handovers.
387  * On success, returns 1 if this registration is a handover destination,
388  * otherwise returns 0.
389  */
390 static int register_snapshot(struct dm_snapshot *snap)
391 {
392         struct origin *o, *new_o = NULL;
393         struct block_device *bdev = snap->origin->bdev;
394         int r = 0;
395
396         new_o = kmalloc(sizeof(*new_o), GFP_KERNEL);
397         if (!new_o)
398                 return -ENOMEM;
399
400         down_write(&_origins_lock);
401
402         r = __validate_exception_handover(snap);
403         if (r < 0) {
404                 kfree(new_o);
405                 goto out;
406         }
407
408         o = __lookup_origin(bdev);
409         if (o)
410                 kfree(new_o);
411         else {
412                 /* New origin */
413                 o = new_o;
414
415                 /* Initialise the struct */
416                 INIT_LIST_HEAD(&o->snapshots);
417                 o->bdev = bdev;
418
419                 __insert_origin(o);
420         }
421
422         __insert_snapshot(o, snap);
423
424 out:
425         up_write(&_origins_lock);
426
427         return r;
428 }
429
430 /*
431  * Move snapshot to correct place in list according to chunk size.
432  */
433 static void reregister_snapshot(struct dm_snapshot *s)
434 {
435         struct block_device *bdev = s->origin->bdev;
436
437         down_write(&_origins_lock);
438
439         list_del(&s->list);
440         __insert_snapshot(__lookup_origin(bdev), s);
441
442         up_write(&_origins_lock);
443 }
444
445 static void unregister_snapshot(struct dm_snapshot *s)
446 {
447         struct origin *o;
448
449         down_write(&_origins_lock);
450         o = __lookup_origin(s->origin->bdev);
451
452         list_del(&s->list);
453         if (o && list_empty(&o->snapshots)) {
454                 list_del(&o->hash_list);
455                 kfree(o);
456         }
457
458         up_write(&_origins_lock);
459 }
460
461 /*
462  * Implementation of the exception hash tables.
463  * The lowest hash_shift bits of the chunk number are ignored, allowing
464  * some consecutive chunks to be grouped together.
465  */
466 static int dm_exception_table_init(struct dm_exception_table *et,
467                                    uint32_t size, unsigned hash_shift)
468 {
469         unsigned int i;
470
471         et->hash_shift = hash_shift;
472         et->hash_mask = size - 1;
473         et->table = dm_vcalloc(size, sizeof(struct list_head));
474         if (!et->table)
475                 return -ENOMEM;
476
477         for (i = 0; i < size; i++)
478                 INIT_LIST_HEAD(et->table + i);
479
480         return 0;
481 }
482
483 static void dm_exception_table_exit(struct dm_exception_table *et,
484                                     struct kmem_cache *mem)
485 {
486         struct list_head *slot;
487         struct dm_exception *ex, *next;
488         int i, size;
489
490         size = et->hash_mask + 1;
491         for (i = 0; i < size; i++) {
492                 slot = et->table + i;
493
494                 list_for_each_entry_safe (ex, next, slot, hash_list)
495                         kmem_cache_free(mem, ex);
496         }
497
498         vfree(et->table);
499 }
500
501 static uint32_t exception_hash(struct dm_exception_table *et, chunk_t chunk)
502 {
503         return (chunk >> et->hash_shift) & et->hash_mask;
504 }
505
506 static void dm_remove_exception(struct dm_exception *e)
507 {
508         list_del(&e->hash_list);
509 }
510
511 /*
512  * Return the exception data for a sector, or NULL if not
513  * remapped.
514  */
515 static struct dm_exception *dm_lookup_exception(struct dm_exception_table *et,
516                                                 chunk_t chunk)
517 {
518         struct list_head *slot;
519         struct dm_exception *e;
520
521         slot = &et->table[exception_hash(et, chunk)];
522         list_for_each_entry (e, slot, hash_list)
523                 if (chunk >= e->old_chunk &&
524                     chunk <= e->old_chunk + dm_consecutive_chunk_count(e))
525                         return e;
526
527         return NULL;
528 }
529
530 static struct dm_exception *alloc_completed_exception(void)
531 {
532         struct dm_exception *e;
533
534         e = kmem_cache_alloc(exception_cache, GFP_NOIO);
535         if (!e)
536                 e = kmem_cache_alloc(exception_cache, GFP_ATOMIC);
537
538         return e;
539 }
540
541 static void free_completed_exception(struct dm_exception *e)
542 {
543         kmem_cache_free(exception_cache, e);
544 }
545
546 static struct dm_snap_pending_exception *alloc_pending_exception(struct dm_snapshot *s)
547 {
548         struct dm_snap_pending_exception *pe = mempool_alloc(s->pending_pool,
549                                                              GFP_NOIO);
550
551         atomic_inc(&s->pending_exceptions_count);
552         pe->snap = s;
553
554         return pe;
555 }
556
557 static void free_pending_exception(struct dm_snap_pending_exception *pe)
558 {
559         struct dm_snapshot *s = pe->snap;
560
561         mempool_free(pe, s->pending_pool);
562         smp_mb__before_atomic_dec();
563         atomic_dec(&s->pending_exceptions_count);
564 }
565
566 static void dm_insert_exception(struct dm_exception_table *eh,
567                                 struct dm_exception *new_e)
568 {
569         struct list_head *l;
570         struct dm_exception *e = NULL;
571
572         l = &eh->table[exception_hash(eh, new_e->old_chunk)];
573
574         /* Add immediately if this table doesn't support consecutive chunks */
575         if (!eh->hash_shift)
576                 goto out;
577
578         /* List is ordered by old_chunk */
579         list_for_each_entry_reverse(e, l, hash_list) {
580                 /* Insert after an existing chunk? */
581                 if (new_e->old_chunk == (e->old_chunk +
582                                          dm_consecutive_chunk_count(e) + 1) &&
583                     new_e->new_chunk == (dm_chunk_number(e->new_chunk) +
584                                          dm_consecutive_chunk_count(e) + 1)) {
585                         dm_consecutive_chunk_count_inc(e);
586                         free_completed_exception(new_e);
587                         return;
588                 }
589
590                 /* Insert before an existing chunk? */
591                 if (new_e->old_chunk == (e->old_chunk - 1) &&
592                     new_e->new_chunk == (dm_chunk_number(e->new_chunk) - 1)) {
593                         dm_consecutive_chunk_count_inc(e);
594                         e->old_chunk--;
595                         e->new_chunk--;
596                         free_completed_exception(new_e);
597                         return;
598                 }
599
600                 if (new_e->old_chunk > e->old_chunk)
601                         break;
602         }
603
604 out:
605         list_add(&new_e->hash_list, e ? &e->hash_list : l);
606 }
607
608 /*
609  * Callback used by the exception stores to load exceptions when
610  * initialising.
611  */
612 static int dm_add_exception(void *context, chunk_t old, chunk_t new)
613 {
614         struct dm_snapshot *s = context;
615         struct dm_exception *e;
616
617         e = alloc_completed_exception();
618         if (!e)
619                 return -ENOMEM;
620
621         e->old_chunk = old;
622
623         /* Consecutive_count is implicitly initialised to zero */
624         e->new_chunk = new;
625
626         dm_insert_exception(&s->complete, e);
627
628         return 0;
629 }
630
631 #define min_not_zero(l, r) (((l) == 0) ? (r) : (((r) == 0) ? (l) : min(l, r)))
632
633 /*
634  * Return a minimum chunk size of all snapshots that have the specified origin.
635  * Return zero if the origin has no snapshots.
636  */
637 static sector_t __minimum_chunk_size(struct origin *o)
638 {
639         struct dm_snapshot *snap;
640         unsigned chunk_size = 0;
641
642         if (o)
643                 list_for_each_entry(snap, &o->snapshots, list)
644                         chunk_size = min_not_zero(chunk_size,
645                                                   snap->store->chunk_size);
646
647         return chunk_size;
648 }
649
650 /*
651  * Hard coded magic.
652  */
653 static int calc_max_buckets(void)
654 {
655         /* use a fixed size of 2MB */
656         unsigned long mem = 2 * 1024 * 1024;
657         mem /= sizeof(struct list_head);
658
659         return mem;
660 }
661
662 /*
663  * Allocate room for a suitable hash table.
664  */
665 static int init_hash_tables(struct dm_snapshot *s)
666 {
667         sector_t hash_size, cow_dev_size, origin_dev_size, max_buckets;
668
669         /*
670          * Calculate based on the size of the original volume or
671          * the COW volume...
672          */
673         cow_dev_size = get_dev_size(s->cow->bdev);
674         origin_dev_size = get_dev_size(s->origin->bdev);
675         max_buckets = calc_max_buckets();
676
677         hash_size = min(origin_dev_size, cow_dev_size) >> s->store->chunk_shift;
678         hash_size = min(hash_size, max_buckets);
679
680         if (hash_size < 64)
681                 hash_size = 64;
682         hash_size = rounddown_pow_of_two(hash_size);
683         if (dm_exception_table_init(&s->complete, hash_size,
684                                     DM_CHUNK_CONSECUTIVE_BITS))
685                 return -ENOMEM;
686
687         /*
688          * Allocate hash table for in-flight exceptions
689          * Make this smaller than the real hash table
690          */
691         hash_size >>= 3;
692         if (hash_size < 64)
693                 hash_size = 64;
694
695         if (dm_exception_table_init(&s->pending, hash_size, 0)) {
696                 dm_exception_table_exit(&s->complete, exception_cache);
697                 return -ENOMEM;
698         }
699
700         return 0;
701 }
702
703 /*
704  * Construct a snapshot mapping: <origin_dev> <COW-dev> <p/n> <chunk-size>
705  */
706 static int snapshot_ctr(struct dm_target *ti, unsigned int argc, char **argv)
707 {
708         struct dm_snapshot *s;
709         int i;
710         int r = -EINVAL;
711         char *origin_path, *cow_path;
712         unsigned args_used;
713
714         if (argc != 4) {
715                 ti->error = "requires exactly 4 arguments";
716                 r = -EINVAL;
717                 goto bad;
718         }
719
720         origin_path = argv[0];
721         argv++;
722         argc--;
723
724         s = kmalloc(sizeof(*s), GFP_KERNEL);
725         if (!s) {
726                 ti->error = "Cannot allocate snapshot context private "
727                     "structure";
728                 r = -ENOMEM;
729                 goto bad;
730         }
731
732         cow_path = argv[0];
733         argv++;
734         argc--;
735
736         r = dm_get_device(ti, cow_path, 0, 0,
737                           FMODE_READ | FMODE_WRITE, &s->cow);
738         if (r) {
739                 ti->error = "Cannot get COW device";
740                 goto bad_cow;
741         }
742
743         r = dm_exception_store_create(ti, argc, argv, s, &args_used, &s->store);
744         if (r) {
745                 ti->error = "Couldn't create exception store";
746                 r = -EINVAL;
747                 goto bad_store;
748         }
749
750         argv += args_used;
751         argc -= args_used;
752
753         r = dm_get_device(ti, origin_path, 0, ti->len, FMODE_READ, &s->origin);
754         if (r) {
755                 ti->error = "Cannot get origin device";
756                 goto bad_origin;
757         }
758
759         s->ti = ti;
760         s->valid = 1;
761         s->active = 0;
762         s->suspended = 0;
763         atomic_set(&s->pending_exceptions_count, 0);
764         init_rwsem(&s->lock);
765         INIT_LIST_HEAD(&s->list);
766         spin_lock_init(&s->pe_lock);
767
768         /* Allocate hash table for COW data */
769         if (init_hash_tables(s)) {
770                 ti->error = "Unable to allocate hash table space";
771                 r = -ENOMEM;
772                 goto bad_hash_tables;
773         }
774
775         r = dm_kcopyd_client_create(SNAPSHOT_PAGES, &s->kcopyd_client);
776         if (r) {
777                 ti->error = "Could not create kcopyd client";
778                 goto bad_kcopyd;
779         }
780
781         s->pending_pool = mempool_create_slab_pool(MIN_IOS, pending_cache);
782         if (!s->pending_pool) {
783                 ti->error = "Could not allocate mempool for pending exceptions";
784                 goto bad_pending_pool;
785         }
786
787         s->tracked_chunk_pool = mempool_create_slab_pool(MIN_IOS,
788                                                          tracked_chunk_cache);
789         if (!s->tracked_chunk_pool) {
790                 ti->error = "Could not allocate tracked_chunk mempool for "
791                             "tracking reads";
792                 goto bad_tracked_chunk_pool;
793         }
794
795         for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
796                 INIT_HLIST_HEAD(&s->tracked_chunk_hash[i]);
797
798         spin_lock_init(&s->tracked_chunk_lock);
799
800         bio_list_init(&s->queued_bios);
801         INIT_WORK(&s->queued_bios_work, flush_queued_bios);
802
803         ti->private = s;
804         ti->num_flush_requests = 1;
805
806         /* Add snapshot to the list of snapshots for this origin */
807         /* Exceptions aren't triggered till snapshot_resume() is called */
808         r = register_snapshot(s);
809         if (r == -ENOMEM) {
810                 ti->error = "Snapshot origin struct allocation failed";
811                 goto bad_load_and_register;
812         } else if (r < 0) {
813                 /* invalid handover, register_snapshot has set ti->error */
814                 goto bad_load_and_register;
815         }
816
817         /*
818          * Metadata must only be loaded into one table at once, so skip this
819          * if metadata will be handed over during resume.
820          * Chunk size will be set during the handover - set it to zero to
821          * ensure it's ignored.
822          */
823         if (r > 0) {
824                 s->store->chunk_size = 0;
825                 return 0;
826         }
827
828         r = s->store->type->read_metadata(s->store, dm_add_exception,
829                                           (void *)s);
830         if (r < 0) {
831                 ti->error = "Failed to read snapshot metadata";
832                 goto bad_read_metadata;
833         } else if (r > 0) {
834                 s->valid = 0;
835                 DMWARN("Snapshot is marked invalid.");
836         }
837
838         if (!s->store->chunk_size) {
839                 ti->error = "Chunk size not set";
840                 goto bad_read_metadata;
841         }
842         ti->split_io = s->store->chunk_size;
843
844         return 0;
845
846 bad_read_metadata:
847         unregister_snapshot(s);
848
849 bad_load_and_register:
850         mempool_destroy(s->tracked_chunk_pool);
851
852 bad_tracked_chunk_pool:
853         mempool_destroy(s->pending_pool);
854
855 bad_pending_pool:
856         dm_kcopyd_client_destroy(s->kcopyd_client);
857
858 bad_kcopyd:
859         dm_exception_table_exit(&s->pending, pending_cache);
860         dm_exception_table_exit(&s->complete, exception_cache);
861
862 bad_hash_tables:
863         dm_put_device(ti, s->origin);
864
865 bad_origin:
866         dm_exception_store_destroy(s->store);
867
868 bad_store:
869         dm_put_device(ti, s->cow);
870
871 bad_cow:
872         kfree(s);
873
874 bad:
875         return r;
876 }
877
878 static void __free_exceptions(struct dm_snapshot *s)
879 {
880         dm_kcopyd_client_destroy(s->kcopyd_client);
881         s->kcopyd_client = NULL;
882
883         dm_exception_table_exit(&s->pending, pending_cache);
884         dm_exception_table_exit(&s->complete, exception_cache);
885 }
886
887 static void __handover_exceptions(struct dm_snapshot *snap_src,
888                                   struct dm_snapshot *snap_dest)
889 {
890         union {
891                 struct dm_exception_table table_swap;
892                 struct dm_exception_store *store_swap;
893         } u;
894
895         /*
896          * Swap all snapshot context information between the two instances.
897          */
898         u.table_swap = snap_dest->complete;
899         snap_dest->complete = snap_src->complete;
900         snap_src->complete = u.table_swap;
901
902         u.store_swap = snap_dest->store;
903         snap_dest->store = snap_src->store;
904         snap_src->store = u.store_swap;
905
906         snap_dest->store->snap = snap_dest;
907         snap_src->store->snap = snap_src;
908
909         snap_dest->ti->split_io = snap_dest->store->chunk_size;
910         snap_dest->valid = snap_src->valid;
911
912         /*
913          * Set source invalid to ensure it receives no further I/O.
914          */
915         snap_src->valid = 0;
916 }
917
918 static void snapshot_dtr(struct dm_target *ti)
919 {
920 #ifdef CONFIG_DM_DEBUG
921         int i;
922 #endif
923         struct dm_snapshot *s = ti->private;
924         struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
925
926         flush_workqueue(ksnapd);
927
928         down_read(&_origins_lock);
929         /* Check whether exception handover must be cancelled */
930         (void) __find_snapshots_sharing_cow(s, &snap_src, &snap_dest);
931         if (snap_src && snap_dest && (s == snap_src)) {
932                 down_write(&snap_dest->lock);
933                 snap_dest->valid = 0;
934                 up_write(&snap_dest->lock);
935                 DMERR("Cancelling snapshot handover.");
936         }
937         up_read(&_origins_lock);
938
939         /* Prevent further origin writes from using this snapshot. */
940         /* After this returns there can be no new kcopyd jobs. */
941         unregister_snapshot(s);
942
943         while (atomic_read(&s->pending_exceptions_count))
944                 msleep(1);
945         /*
946          * Ensure instructions in mempool_destroy aren't reordered
947          * before atomic_read.
948          */
949         smp_mb();
950
951 #ifdef CONFIG_DM_DEBUG
952         for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
953                 BUG_ON(!hlist_empty(&s->tracked_chunk_hash[i]));
954 #endif
955
956         mempool_destroy(s->tracked_chunk_pool);
957
958         __free_exceptions(s);
959
960         mempool_destroy(s->pending_pool);
961
962         dm_put_device(ti, s->origin);
963
964         dm_exception_store_destroy(s->store);
965
966         dm_put_device(ti, s->cow);
967
968         kfree(s);
969 }
970
971 /*
972  * Flush a list of buffers.
973  */
974 static void flush_bios(struct bio *bio)
975 {
976         struct bio *n;
977
978         while (bio) {
979                 n = bio->bi_next;
980                 bio->bi_next = NULL;
981                 generic_make_request(bio);
982                 bio = n;
983         }
984 }
985
986 static void flush_queued_bios(struct work_struct *work)
987 {
988         struct dm_snapshot *s =
989                 container_of(work, struct dm_snapshot, queued_bios_work);
990         struct bio *queued_bios;
991         unsigned long flags;
992
993         spin_lock_irqsave(&s->pe_lock, flags);
994         queued_bios = bio_list_get(&s->queued_bios);
995         spin_unlock_irqrestore(&s->pe_lock, flags);
996
997         flush_bios(queued_bios);
998 }
999
1000 static int do_origin(struct dm_dev *origin, struct bio *bio);
1001
1002 /*
1003  * Flush a list of buffers.
1004  */
1005 static void retry_origin_bios(struct dm_snapshot *s, struct bio *bio)
1006 {
1007         struct bio *n;
1008         int r;
1009
1010         while (bio) {
1011                 n = bio->bi_next;
1012                 bio->bi_next = NULL;
1013                 r = do_origin(s->origin, bio);
1014                 if (r == DM_MAPIO_REMAPPED)
1015                         generic_make_request(bio);
1016                 bio = n;
1017         }
1018 }
1019
1020 /*
1021  * Error a list of buffers.
1022  */
1023 static void error_bios(struct bio *bio)
1024 {
1025         struct bio *n;
1026
1027         while (bio) {
1028                 n = bio->bi_next;
1029                 bio->bi_next = NULL;
1030                 bio_io_error(bio);
1031                 bio = n;
1032         }
1033 }
1034
1035 static void __invalidate_snapshot(struct dm_snapshot *s, int err)
1036 {
1037         if (!s->valid)
1038                 return;
1039
1040         if (err == -EIO)
1041                 DMERR("Invalidating snapshot: Error reading/writing.");
1042         else if (err == -ENOMEM)
1043                 DMERR("Invalidating snapshot: Unable to allocate exception.");
1044
1045         if (s->store->type->drop_snapshot)
1046                 s->store->type->drop_snapshot(s->store);
1047
1048         s->valid = 0;
1049
1050         dm_table_event(s->ti->table);
1051 }
1052
1053 static void pending_complete(struct dm_snap_pending_exception *pe, int success)
1054 {
1055         struct dm_exception *e;
1056         struct dm_snapshot *s = pe->snap;
1057         struct bio *origin_bios = NULL;
1058         struct bio *snapshot_bios = NULL;
1059         int error = 0;
1060
1061         if (!success) {
1062                 /* Read/write error - snapshot is unusable */
1063                 down_write(&s->lock);
1064                 __invalidate_snapshot(s, -EIO);
1065                 error = 1;
1066                 goto out;
1067         }
1068
1069         e = alloc_completed_exception();
1070         if (!e) {
1071                 down_write(&s->lock);
1072                 __invalidate_snapshot(s, -ENOMEM);
1073                 error = 1;
1074                 goto out;
1075         }
1076         *e = pe->e;
1077
1078         down_write(&s->lock);
1079         if (!s->valid) {
1080                 free_completed_exception(e);
1081                 error = 1;
1082                 goto out;
1083         }
1084
1085         /* Check for conflicting reads */
1086         __check_for_conflicting_io(s, pe->e.old_chunk);
1087
1088         /*
1089          * Add a proper exception, and remove the
1090          * in-flight exception from the list.
1091          */
1092         dm_insert_exception(&s->complete, e);
1093
1094  out:
1095         dm_remove_exception(&pe->e);
1096         snapshot_bios = bio_list_get(&pe->snapshot_bios);
1097         origin_bios = bio_list_get(&pe->origin_bios);
1098         free_pending_exception(pe);
1099
1100         up_write(&s->lock);
1101
1102         /* Submit any pending write bios */
1103         if (error)
1104                 error_bios(snapshot_bios);
1105         else
1106                 flush_bios(snapshot_bios);
1107
1108         retry_origin_bios(s, origin_bios);
1109 }
1110
1111 static void commit_callback(void *context, int success)
1112 {
1113         struct dm_snap_pending_exception *pe = context;
1114
1115         pending_complete(pe, success);
1116 }
1117
1118 /*
1119  * Called when the copy I/O has finished.  kcopyd actually runs
1120  * this code so don't block.
1121  */
1122 static void copy_callback(int read_err, unsigned long write_err, void *context)
1123 {
1124         struct dm_snap_pending_exception *pe = context;
1125         struct dm_snapshot *s = pe->snap;
1126
1127         if (read_err || write_err)
1128                 pending_complete(pe, 0);
1129
1130         else
1131                 /* Update the metadata if we are persistent */
1132                 s->store->type->commit_exception(s->store, &pe->e,
1133                                                  commit_callback, pe);
1134 }
1135
1136 /*
1137  * Dispatches the copy operation to kcopyd.
1138  */
1139 static void start_copy(struct dm_snap_pending_exception *pe)
1140 {
1141         struct dm_snapshot *s = pe->snap;
1142         struct dm_io_region src, dest;
1143         struct block_device *bdev = s->origin->bdev;
1144         sector_t dev_size;
1145
1146         dev_size = get_dev_size(bdev);
1147
1148         src.bdev = bdev;
1149         src.sector = chunk_to_sector(s->store, pe->e.old_chunk);
1150         src.count = min((sector_t)s->store->chunk_size, dev_size - src.sector);
1151
1152         dest.bdev = s->cow->bdev;
1153         dest.sector = chunk_to_sector(s->store, pe->e.new_chunk);
1154         dest.count = src.count;
1155
1156         /* Hand over to kcopyd */
1157         dm_kcopyd_copy(s->kcopyd_client,
1158                     &src, 1, &dest, 0, copy_callback, pe);
1159 }
1160
1161 static struct dm_snap_pending_exception *
1162 __lookup_pending_exception(struct dm_snapshot *s, chunk_t chunk)
1163 {
1164         struct dm_exception *e = dm_lookup_exception(&s->pending, chunk);
1165
1166         if (!e)
1167                 return NULL;
1168
1169         return container_of(e, struct dm_snap_pending_exception, e);
1170 }
1171
1172 /*
1173  * Looks to see if this snapshot already has a pending exception
1174  * for this chunk, otherwise it allocates a new one and inserts
1175  * it into the pending table.
1176  *
1177  * NOTE: a write lock must be held on snap->lock before calling
1178  * this.
1179  */
1180 static struct dm_snap_pending_exception *
1181 __find_pending_exception(struct dm_snapshot *s,
1182                          struct dm_snap_pending_exception *pe, chunk_t chunk)
1183 {
1184         struct dm_snap_pending_exception *pe2;
1185
1186         pe2 = __lookup_pending_exception(s, chunk);
1187         if (pe2) {
1188                 free_pending_exception(pe);
1189                 return pe2;
1190         }
1191
1192         pe->e.old_chunk = chunk;
1193         bio_list_init(&pe->origin_bios);
1194         bio_list_init(&pe->snapshot_bios);
1195         pe->started = 0;
1196
1197         if (s->store->type->prepare_exception(s->store, &pe->e)) {
1198                 free_pending_exception(pe);
1199                 return NULL;
1200         }
1201
1202         dm_insert_exception(&s->pending, &pe->e);
1203
1204         return pe;
1205 }
1206
1207 static void remap_exception(struct dm_snapshot *s, struct dm_exception *e,
1208                             struct bio *bio, chunk_t chunk)
1209 {
1210         bio->bi_bdev = s->cow->bdev;
1211         bio->bi_sector = chunk_to_sector(s->store,
1212                                          dm_chunk_number(e->new_chunk) +
1213                                          (chunk - e->old_chunk)) +
1214                                          (bio->bi_sector &
1215                                           s->store->chunk_mask);
1216 }
1217
1218 static int snapshot_map(struct dm_target *ti, struct bio *bio,
1219                         union map_info *map_context)
1220 {
1221         struct dm_exception *e;
1222         struct dm_snapshot *s = ti->private;
1223         int r = DM_MAPIO_REMAPPED;
1224         chunk_t chunk;
1225         struct dm_snap_pending_exception *pe = NULL;
1226
1227         if (unlikely(bio_empty_barrier(bio))) {
1228                 bio->bi_bdev = s->cow->bdev;
1229                 return DM_MAPIO_REMAPPED;
1230         }
1231
1232         chunk = sector_to_chunk(s->store, bio->bi_sector);
1233
1234         /* Full snapshots are not usable */
1235         /* To get here the table must be live so s->active is always set. */
1236         if (!s->valid)
1237                 return -EIO;
1238
1239         /* FIXME: should only take write lock if we need
1240          * to copy an exception */
1241         down_write(&s->lock);
1242
1243         if (!s->valid) {
1244                 r = -EIO;
1245                 goto out_unlock;
1246         }
1247
1248         /* If the block is already remapped - use that, else remap it */
1249         e = dm_lookup_exception(&s->complete, chunk);
1250         if (e) {
1251                 remap_exception(s, e, bio, chunk);
1252                 goto out_unlock;
1253         }
1254
1255         /*
1256          * Write to snapshot - higher level takes care of RW/RO
1257          * flags so we should only get this if we are
1258          * writeable.
1259          */
1260         if (bio_rw(bio) == WRITE) {
1261                 pe = __lookup_pending_exception(s, chunk);
1262                 if (!pe) {
1263                         up_write(&s->lock);
1264                         pe = alloc_pending_exception(s);
1265                         down_write(&s->lock);
1266
1267                         if (!s->valid) {
1268                                 free_pending_exception(pe);
1269                                 r = -EIO;
1270                                 goto out_unlock;
1271                         }
1272
1273                         e = dm_lookup_exception(&s->complete, chunk);
1274                         if (e) {
1275                                 free_pending_exception(pe);
1276                                 remap_exception(s, e, bio, chunk);
1277                                 goto out_unlock;
1278                         }
1279
1280                         pe = __find_pending_exception(s, pe, chunk);
1281                         if (!pe) {
1282                                 __invalidate_snapshot(s, -ENOMEM);
1283                                 r = -EIO;
1284                                 goto out_unlock;
1285                         }
1286                 }
1287
1288                 remap_exception(s, &pe->e, bio, chunk);
1289                 bio_list_add(&pe->snapshot_bios, bio);
1290
1291                 r = DM_MAPIO_SUBMITTED;
1292
1293                 if (!pe->started) {
1294                         /* this is protected by snap->lock */
1295                         pe->started = 1;
1296                         up_write(&s->lock);
1297                         start_copy(pe);
1298                         goto out;
1299                 }
1300         } else {
1301                 bio->bi_bdev = s->origin->bdev;
1302                 map_context->ptr = track_chunk(s, chunk);
1303         }
1304
1305  out_unlock:
1306         up_write(&s->lock);
1307  out:
1308         return r;
1309 }
1310
1311 /*
1312  * A snapshot-merge target behaves like a combination of a snapshot
1313  * target and a snapshot-origin target.  It only generates new
1314  * exceptions in other snapshots and not in the one that is being
1315  * merged.
1316  *
1317  * For each chunk, if there is an existing exception, it is used to
1318  * redirect I/O to the cow device.  Otherwise I/O is sent to the origin,
1319  * which in turn might generate exceptions in other snapshots.
1320  */
1321 static int snapshot_merge_map(struct dm_target *ti, struct bio *bio,
1322                               union map_info *map_context)
1323 {
1324         struct dm_exception *e;
1325         struct dm_snapshot *s = ti->private;
1326         int r = DM_MAPIO_REMAPPED;
1327         chunk_t chunk;
1328
1329         chunk = sector_to_chunk(s->store, bio->bi_sector);
1330
1331         down_read(&s->lock);
1332
1333         /* Full snapshots are not usable */
1334         if (!s->valid) {
1335                 r = -EIO;
1336                 goto out_unlock;
1337         }
1338
1339         /* If the block is already remapped - use that */
1340         e = dm_lookup_exception(&s->complete, chunk);
1341         if (e) {
1342                 remap_exception(s, e, bio, chunk);
1343                 goto out_unlock;
1344         }
1345
1346         bio->bi_bdev = s->origin->bdev;
1347
1348         if (bio_rw(bio) == WRITE) {
1349                 up_read(&s->lock);
1350                 return do_origin(s->origin, bio);
1351         }
1352
1353 out_unlock:
1354         up_read(&s->lock);
1355
1356         return r;
1357 }
1358
1359 static int snapshot_end_io(struct dm_target *ti, struct bio *bio,
1360                            int error, union map_info *map_context)
1361 {
1362         struct dm_snapshot *s = ti->private;
1363         struct dm_snap_tracked_chunk *c = map_context->ptr;
1364
1365         if (c)
1366                 stop_tracking_chunk(s, c);
1367
1368         return 0;
1369 }
1370
1371 static void snapshot_postsuspend(struct dm_target *ti)
1372 {
1373         struct dm_snapshot *s = ti->private;
1374
1375         down_write(&s->lock);
1376         s->suspended = 1;
1377         up_write(&s->lock);
1378 }
1379
1380 static int snapshot_preresume(struct dm_target *ti)
1381 {
1382         int r = 0;
1383         struct dm_snapshot *s = ti->private;
1384         struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
1385
1386         down_read(&_origins_lock);
1387         (void) __find_snapshots_sharing_cow(s, &snap_src, &snap_dest);
1388         if (snap_src && snap_dest) {
1389                 down_read(&snap_src->lock);
1390                 if (s == snap_src) {
1391                         DMERR("Unable to resume snapshot source until "
1392                               "handover completes.");
1393                         r = -EINVAL;
1394                 } else if (!snap_src->suspended) {
1395                         DMERR("Unable to perform snapshot handover until "
1396                               "source is suspended.");
1397                         r = -EINVAL;
1398                 }
1399                 up_read(&snap_src->lock);
1400         }
1401         up_read(&_origins_lock);
1402
1403         return r;
1404 }
1405
1406 static void snapshot_resume(struct dm_target *ti)
1407 {
1408         struct dm_snapshot *s = ti->private;
1409         struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
1410
1411         down_read(&_origins_lock);
1412         (void) __find_snapshots_sharing_cow(s, &snap_src, &snap_dest);
1413         if (snap_src && snap_dest) {
1414                 down_write(&snap_src->lock);
1415                 down_write_nested(&snap_dest->lock, SINGLE_DEPTH_NESTING);
1416                 __handover_exceptions(snap_src, snap_dest);
1417                 up_write(&snap_dest->lock);
1418                 up_write(&snap_src->lock);
1419         }
1420         up_read(&_origins_lock);
1421
1422         /* Now we have correct chunk size, reregister */
1423         reregister_snapshot(s);
1424
1425         down_write(&s->lock);
1426         s->active = 1;
1427         s->suspended = 0;
1428         up_write(&s->lock);
1429 }
1430
1431 static int snapshot_status(struct dm_target *ti, status_type_t type,
1432                            char *result, unsigned int maxlen)
1433 {
1434         unsigned sz = 0;
1435         struct dm_snapshot *snap = ti->private;
1436
1437         switch (type) {
1438         case STATUSTYPE_INFO:
1439
1440                 down_write(&snap->lock);
1441
1442                 if (!snap->valid)
1443                         DMEMIT("Invalid");
1444                 else {
1445                         if (snap->store->type->usage) {
1446                                 sector_t total_sectors, sectors_allocated,
1447                                          metadata_sectors;
1448                                 snap->store->type->usage(snap->store,
1449                                                          &total_sectors,
1450                                                          &sectors_allocated,
1451                                                          &metadata_sectors);
1452                                 DMEMIT("%llu/%llu %llu",
1453                                        (unsigned long long)sectors_allocated,
1454                                        (unsigned long long)total_sectors,
1455                                        (unsigned long long)metadata_sectors);
1456                         }
1457                         else
1458                                 DMEMIT("Unknown");
1459                 }
1460
1461                 up_write(&snap->lock);
1462
1463                 break;
1464
1465         case STATUSTYPE_TABLE:
1466                 /*
1467                  * kdevname returns a static pointer so we need
1468                  * to make private copies if the output is to
1469                  * make sense.
1470                  */
1471                 DMEMIT("%s %s", snap->origin->name, snap->cow->name);
1472                 snap->store->type->status(snap->store, type, result + sz,
1473                                           maxlen - sz);
1474                 break;
1475         }
1476
1477         return 0;
1478 }
1479
1480 static int snapshot_iterate_devices(struct dm_target *ti,
1481                                     iterate_devices_callout_fn fn, void *data)
1482 {
1483         struct dm_snapshot *snap = ti->private;
1484
1485         return fn(ti, snap->origin, 0, ti->len, data);
1486 }
1487
1488
1489 /*-----------------------------------------------------------------
1490  * Origin methods
1491  *---------------------------------------------------------------*/
1492
1493 /*
1494  * If no exceptions need creating, DM_MAPIO_REMAPPED is returned and any
1495  * supplied bio was ignored.  The caller may submit it immediately.
1496  * (No remapping actually occurs as the origin is always a direct linear
1497  * map.)
1498  *
1499  * If further exceptions are required, DM_MAPIO_SUBMITTED is returned
1500  * and any supplied bio is added to a list to be submitted once all
1501  * the necessary exceptions exist.
1502  */
1503 static int __origin_write(struct list_head *snapshots, sector_t sector,
1504                           struct bio *bio)
1505 {
1506         int r = DM_MAPIO_REMAPPED;
1507         struct dm_snapshot *snap;
1508         struct dm_exception *e;
1509         struct dm_snap_pending_exception *pe;
1510         struct dm_snap_pending_exception *pe_to_start_now = NULL;
1511         struct dm_snap_pending_exception *pe_to_start_last = NULL;
1512         chunk_t chunk;
1513
1514         /* Do all the snapshots on this origin */
1515         list_for_each_entry (snap, snapshots, list) {
1516                 /*
1517                  * Don't make new exceptions in a merging snapshot
1518                  * because it has effectively been deleted
1519                  */
1520                 if (dm_target_is_snapshot_merge(snap->ti))
1521                         continue;
1522
1523                 down_write(&snap->lock);
1524
1525                 /* Only deal with valid and active snapshots */
1526                 if (!snap->valid || !snap->active)
1527                         goto next_snapshot;
1528
1529                 /* Nothing to do if writing beyond end of snapshot */
1530                 if (sector >= dm_table_get_size(snap->ti->table))
1531                         goto next_snapshot;
1532
1533                 /*
1534                  * Remember, different snapshots can have
1535                  * different chunk sizes.
1536                  */
1537                 chunk = sector_to_chunk(snap->store, sector);
1538
1539                 /*
1540                  * Check exception table to see if block
1541                  * is already remapped in this snapshot
1542                  * and trigger an exception if not.
1543                  */
1544                 e = dm_lookup_exception(&snap->complete, chunk);
1545                 if (e)
1546                         goto next_snapshot;
1547
1548                 pe = __lookup_pending_exception(snap, chunk);
1549                 if (!pe) {
1550                         up_write(&snap->lock);
1551                         pe = alloc_pending_exception(snap);
1552                         down_write(&snap->lock);
1553
1554                         if (!snap->valid) {
1555                                 free_pending_exception(pe);
1556                                 goto next_snapshot;
1557                         }
1558
1559                         e = dm_lookup_exception(&snap->complete, chunk);
1560                         if (e) {
1561                                 free_pending_exception(pe);
1562                                 goto next_snapshot;
1563                         }
1564
1565                         pe = __find_pending_exception(snap, pe, chunk);
1566                         if (!pe) {
1567                                 __invalidate_snapshot(snap, -ENOMEM);
1568                                 goto next_snapshot;
1569                         }
1570                 }
1571
1572                 r = DM_MAPIO_SUBMITTED;
1573
1574                 /*
1575                  * If an origin bio was supplied, queue it to wait for the
1576                  * completion of this exception, and start this one last,
1577                  * at the end of the function.
1578                  */
1579                 if (bio) {
1580                         bio_list_add(&pe->origin_bios, bio);
1581                         bio = NULL;
1582
1583                         if (!pe->started) {
1584                                 pe->started = 1;
1585                                 pe_to_start_last = pe;
1586                         }
1587                 }
1588
1589                 if (!pe->started) {
1590                         pe->started = 1;
1591                         pe_to_start_now = pe;
1592                 }
1593
1594  next_snapshot:
1595                 up_write(&snap->lock);
1596
1597                 if (pe_to_start_now) {
1598                         start_copy(pe_to_start_now);
1599                         pe_to_start_now = NULL;
1600                 }
1601         }
1602
1603         /*
1604          * Submit the exception against which the bio is queued last,
1605          * to give the other exceptions a head start.
1606          */
1607         if (pe_to_start_last)
1608                 start_copy(pe_to_start_last);
1609
1610         return r;
1611 }
1612
1613 /*
1614  * Called on a write from the origin driver.
1615  */
1616 static int do_origin(struct dm_dev *origin, struct bio *bio)
1617 {
1618         struct origin *o;
1619         int r = DM_MAPIO_REMAPPED;
1620
1621         down_read(&_origins_lock);
1622         o = __lookup_origin(origin->bdev);
1623         if (o)
1624                 r = __origin_write(&o->snapshots, bio->bi_sector, bio);
1625         up_read(&_origins_lock);
1626
1627         return r;
1628 }
1629
1630 /*
1631  * Origin: maps a linear range of a device, with hooks for snapshotting.
1632  */
1633
1634 /*
1635  * Construct an origin mapping: <dev_path>
1636  * The context for an origin is merely a 'struct dm_dev *'
1637  * pointing to the real device.
1638  */
1639 static int origin_ctr(struct dm_target *ti, unsigned int argc, char **argv)
1640 {
1641         int r;
1642         struct dm_dev *dev;
1643
1644         if (argc != 1) {
1645                 ti->error = "origin: incorrect number of arguments";
1646                 return -EINVAL;
1647         }
1648
1649         r = dm_get_device(ti, argv[0], 0, ti->len,
1650                           dm_table_get_mode(ti->table), &dev);
1651         if (r) {
1652                 ti->error = "Cannot get target device";
1653                 return r;
1654         }
1655
1656         ti->private = dev;
1657         ti->num_flush_requests = 1;
1658
1659         return 0;
1660 }
1661
1662 static void origin_dtr(struct dm_target *ti)
1663 {
1664         struct dm_dev *dev = ti->private;
1665         dm_put_device(ti, dev);
1666 }
1667
1668 static int origin_map(struct dm_target *ti, struct bio *bio,
1669                       union map_info *map_context)
1670 {
1671         struct dm_dev *dev = ti->private;
1672         bio->bi_bdev = dev->bdev;
1673
1674         if (unlikely(bio_empty_barrier(bio)))
1675                 return DM_MAPIO_REMAPPED;
1676
1677         /* Only tell snapshots if this is a write */
1678         return (bio_rw(bio) == WRITE) ? do_origin(dev, bio) : DM_MAPIO_REMAPPED;
1679 }
1680
1681 /*
1682  * Set the target "split_io" field to the minimum of all the snapshots'
1683  * chunk sizes.
1684  */
1685 static void origin_resume(struct dm_target *ti)
1686 {
1687         struct dm_dev *dev = ti->private;
1688
1689         down_read(&_origins_lock);
1690
1691         ti->split_io = __minimum_chunk_size(__lookup_origin(dev->bdev));
1692
1693         up_read(&_origins_lock);
1694 }
1695
1696 static int origin_status(struct dm_target *ti, status_type_t type, char *result,
1697                          unsigned int maxlen)
1698 {
1699         struct dm_dev *dev = ti->private;
1700
1701         switch (type) {
1702         case STATUSTYPE_INFO:
1703                 result[0] = '\0';
1704                 break;
1705
1706         case STATUSTYPE_TABLE:
1707                 snprintf(result, maxlen, "%s", dev->name);
1708                 break;
1709         }
1710
1711         return 0;
1712 }
1713
1714 static int origin_iterate_devices(struct dm_target *ti,
1715                                   iterate_devices_callout_fn fn, void *data)
1716 {
1717         struct dm_dev *dev = ti->private;
1718
1719         return fn(ti, dev, 0, ti->len, data);
1720 }
1721
1722 static struct target_type origin_target = {
1723         .name    = "snapshot-origin",
1724         .version = {1, 7, 0},
1725         .module  = THIS_MODULE,
1726         .ctr     = origin_ctr,
1727         .dtr     = origin_dtr,
1728         .map     = origin_map,
1729         .resume  = origin_resume,
1730         .status  = origin_status,
1731         .iterate_devices = origin_iterate_devices,
1732 };
1733
1734 static struct target_type snapshot_target = {
1735         .name    = "snapshot",
1736         .version = {1, 9, 0},
1737         .module  = THIS_MODULE,
1738         .ctr     = snapshot_ctr,
1739         .dtr     = snapshot_dtr,
1740         .map     = snapshot_map,
1741         .end_io  = snapshot_end_io,
1742         .postsuspend = snapshot_postsuspend,
1743         .preresume  = snapshot_preresume,
1744         .resume  = snapshot_resume,
1745         .status  = snapshot_status,
1746         .iterate_devices = snapshot_iterate_devices,
1747 };
1748
1749 static struct target_type merge_target = {
1750         .name    = dm_snapshot_merge_target_name,
1751         .version = {1, 0, 0},
1752         .module  = THIS_MODULE,
1753         .ctr     = snapshot_ctr,
1754         .dtr     = snapshot_dtr,
1755         .map     = snapshot_merge_map,
1756         .end_io  = snapshot_end_io,
1757         .postsuspend = snapshot_postsuspend,
1758         .preresume  = snapshot_preresume,
1759         .resume  = snapshot_resume,
1760         .status  = snapshot_status,
1761         .iterate_devices = snapshot_iterate_devices,
1762 };
1763
1764 static int __init dm_snapshot_init(void)
1765 {
1766         int r;
1767
1768         r = dm_exception_store_init();
1769         if (r) {
1770                 DMERR("Failed to initialize exception stores");
1771                 return r;
1772         }
1773
1774         r = dm_register_target(&snapshot_target);
1775         if (r < 0) {
1776                 DMERR("snapshot target register failed %d", r);
1777                 goto bad_register_snapshot_target;
1778         }
1779
1780         r = dm_register_target(&origin_target);
1781         if (r < 0) {
1782                 DMERR("Origin target register failed %d", r);
1783                 goto bad_register_origin_target;
1784         }
1785
1786         r = dm_register_target(&merge_target);
1787         if (r < 0) {
1788                 DMERR("Merge target register failed %d", r);
1789                 goto bad_register_merge_target;
1790         }
1791
1792         r = init_origin_hash();
1793         if (r) {
1794                 DMERR("init_origin_hash failed.");
1795                 goto bad_origin_hash;
1796         }
1797
1798         exception_cache = KMEM_CACHE(dm_exception, 0);
1799         if (!exception_cache) {
1800                 DMERR("Couldn't create exception cache.");
1801                 r = -ENOMEM;
1802                 goto bad_exception_cache;
1803         }
1804
1805         pending_cache = KMEM_CACHE(dm_snap_pending_exception, 0);
1806         if (!pending_cache) {
1807                 DMERR("Couldn't create pending cache.");
1808                 r = -ENOMEM;
1809                 goto bad_pending_cache;
1810         }
1811
1812         tracked_chunk_cache = KMEM_CACHE(dm_snap_tracked_chunk, 0);
1813         if (!tracked_chunk_cache) {
1814                 DMERR("Couldn't create cache to track chunks in use.");
1815                 r = -ENOMEM;
1816                 goto bad_tracked_chunk_cache;
1817         }
1818
1819         ksnapd = create_singlethread_workqueue("ksnapd");
1820         if (!ksnapd) {
1821                 DMERR("Failed to create ksnapd workqueue.");
1822                 r = -ENOMEM;
1823                 goto bad_pending_pool;
1824         }
1825
1826         return 0;
1827
1828 bad_pending_pool:
1829         kmem_cache_destroy(tracked_chunk_cache);
1830 bad_tracked_chunk_cache:
1831         kmem_cache_destroy(pending_cache);
1832 bad_pending_cache:
1833         kmem_cache_destroy(exception_cache);
1834 bad_exception_cache:
1835         exit_origin_hash();
1836 bad_origin_hash:
1837         dm_unregister_target(&merge_target);
1838 bad_register_merge_target:
1839         dm_unregister_target(&origin_target);
1840 bad_register_origin_target:
1841         dm_unregister_target(&snapshot_target);
1842 bad_register_snapshot_target:
1843         dm_exception_store_exit();
1844
1845         return r;
1846 }
1847
1848 static void __exit dm_snapshot_exit(void)
1849 {
1850         destroy_workqueue(ksnapd);
1851
1852         dm_unregister_target(&snapshot_target);
1853         dm_unregister_target(&origin_target);
1854         dm_unregister_target(&merge_target);
1855
1856         exit_origin_hash();
1857         kmem_cache_destroy(pending_cache);
1858         kmem_cache_destroy(exception_cache);
1859         kmem_cache_destroy(tracked_chunk_cache);
1860
1861         dm_exception_store_exit();
1862 }
1863
1864 /* Module hooks */
1865 module_init(dm_snapshot_init);
1866 module_exit(dm_snapshot_exit);
1867
1868 MODULE_DESCRIPTION(DM_NAME " snapshot target");
1869 MODULE_AUTHOR("Joe Thornber");
1870 MODULE_LICENSE("GPL");