dm snapshot: fix race during exception creation
[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/ctype.h>
11 #include <linux/device-mapper.h>
12 #include <linux/fs.h>
13 #include <linux/init.h>
14 #include <linux/kdev_t.h>
15 #include <linux/list.h>
16 #include <linux/mempool.h>
17 #include <linux/module.h>
18 #include <linux/slab.h>
19 #include <linux/vmalloc.h>
20 #include <linux/log2.h>
21 #include <linux/dm-kcopyd.h>
22
23 #include "dm-snap.h"
24 #include "dm-bio-list.h"
25
26 #define DM_MSG_PREFIX "snapshots"
27
28 /*
29  * The percentage increment we will wake up users at
30  */
31 #define WAKE_UP_PERCENT 5
32
33 /*
34  * kcopyd priority of snapshot operations
35  */
36 #define SNAPSHOT_COPY_PRIORITY 2
37
38 /*
39  * Reserve 1MB for each snapshot initially (with minimum of 1 page).
40  */
41 #define SNAPSHOT_PAGES (((1UL << 20) >> PAGE_SHIFT) ? : 1)
42
43 /*
44  * The size of the mempool used to track chunks in use.
45  */
46 #define MIN_IOS 256
47
48 static struct workqueue_struct *ksnapd;
49 static void flush_queued_bios(struct work_struct *work);
50
51 struct dm_snap_pending_exception {
52         struct dm_snap_exception e;
53
54         /*
55          * Origin buffers waiting for this to complete are held
56          * in a bio list
57          */
58         struct bio_list origin_bios;
59         struct bio_list snapshot_bios;
60
61         /*
62          * Short-term queue of pending exceptions prior to submission.
63          */
64         struct list_head list;
65
66         /*
67          * The primary pending_exception is the one that holds
68          * the ref_count and the list of origin_bios for a
69          * group of pending_exceptions.  It is always last to get freed.
70          * These fields get set up when writing to the origin.
71          */
72         struct dm_snap_pending_exception *primary_pe;
73
74         /*
75          * Number of pending_exceptions processing this chunk.
76          * When this drops to zero we must complete the origin bios.
77          * If incrementing or decrementing this, hold pe->snap->lock for
78          * the sibling concerned and not pe->primary_pe->snap->lock unless
79          * they are the same.
80          */
81         atomic_t ref_count;
82
83         /* Pointer back to snapshot context */
84         struct dm_snapshot *snap;
85
86         /*
87          * 1 indicates the exception has already been sent to
88          * kcopyd.
89          */
90         int started;
91 };
92
93 /*
94  * Hash table mapping origin volumes to lists of snapshots and
95  * a lock to protect it
96  */
97 static struct kmem_cache *exception_cache;
98 static struct kmem_cache *pending_cache;
99 static mempool_t *pending_pool;
100
101 struct dm_snap_tracked_chunk {
102         struct hlist_node node;
103         chunk_t chunk;
104 };
105
106 static struct kmem_cache *tracked_chunk_cache;
107
108 static struct dm_snap_tracked_chunk *track_chunk(struct dm_snapshot *s,
109                                                  chunk_t chunk)
110 {
111         struct dm_snap_tracked_chunk *c = mempool_alloc(s->tracked_chunk_pool,
112                                                         GFP_NOIO);
113         unsigned long flags;
114
115         c->chunk = chunk;
116
117         spin_lock_irqsave(&s->tracked_chunk_lock, flags);
118         hlist_add_head(&c->node,
119                        &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)]);
120         spin_unlock_irqrestore(&s->tracked_chunk_lock, flags);
121
122         return c;
123 }
124
125 static void stop_tracking_chunk(struct dm_snapshot *s,
126                                 struct dm_snap_tracked_chunk *c)
127 {
128         unsigned long flags;
129
130         spin_lock_irqsave(&s->tracked_chunk_lock, flags);
131         hlist_del(&c->node);
132         spin_unlock_irqrestore(&s->tracked_chunk_lock, flags);
133
134         mempool_free(c, s->tracked_chunk_pool);
135 }
136
137 static int __chunk_is_tracked(struct dm_snapshot *s, chunk_t chunk)
138 {
139         struct dm_snap_tracked_chunk *c;
140         struct hlist_node *hn;
141         int found = 0;
142
143         spin_lock_irq(&s->tracked_chunk_lock);
144
145         hlist_for_each_entry(c, hn,
146             &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)], node) {
147                 if (c->chunk == chunk) {
148                         found = 1;
149                         break;
150                 }
151         }
152
153         spin_unlock_irq(&s->tracked_chunk_lock);
154
155         return found;
156 }
157
158 /*
159  * One of these per registered origin, held in the snapshot_origins hash
160  */
161 struct origin {
162         /* The origin device */
163         struct block_device *bdev;
164
165         struct list_head hash_list;
166
167         /* List of snapshots for this origin */
168         struct list_head snapshots;
169 };
170
171 /*
172  * Size of the hash table for origin volumes. If we make this
173  * the size of the minors list then it should be nearly perfect
174  */
175 #define ORIGIN_HASH_SIZE 256
176 #define ORIGIN_MASK      0xFF
177 static struct list_head *_origins;
178 static struct rw_semaphore _origins_lock;
179
180 static int init_origin_hash(void)
181 {
182         int i;
183
184         _origins = kmalloc(ORIGIN_HASH_SIZE * sizeof(struct list_head),
185                            GFP_KERNEL);
186         if (!_origins) {
187                 DMERR("unable to allocate memory");
188                 return -ENOMEM;
189         }
190
191         for (i = 0; i < ORIGIN_HASH_SIZE; i++)
192                 INIT_LIST_HEAD(_origins + i);
193         init_rwsem(&_origins_lock);
194
195         return 0;
196 }
197
198 static void exit_origin_hash(void)
199 {
200         kfree(_origins);
201 }
202
203 static unsigned origin_hash(struct block_device *bdev)
204 {
205         return bdev->bd_dev & ORIGIN_MASK;
206 }
207
208 static struct origin *__lookup_origin(struct block_device *origin)
209 {
210         struct list_head *ol;
211         struct origin *o;
212
213         ol = &_origins[origin_hash(origin)];
214         list_for_each_entry (o, ol, hash_list)
215                 if (bdev_equal(o->bdev, origin))
216                         return o;
217
218         return NULL;
219 }
220
221 static void __insert_origin(struct origin *o)
222 {
223         struct list_head *sl = &_origins[origin_hash(o->bdev)];
224         list_add_tail(&o->hash_list, sl);
225 }
226
227 /*
228  * Make a note of the snapshot and its origin so we can look it
229  * up when the origin has a write on it.
230  */
231 static int register_snapshot(struct dm_snapshot *snap)
232 {
233         struct origin *o;
234         struct block_device *bdev = snap->origin->bdev;
235
236         down_write(&_origins_lock);
237         o = __lookup_origin(bdev);
238
239         if (!o) {
240                 /* New origin */
241                 o = kmalloc(sizeof(*o), GFP_KERNEL);
242                 if (!o) {
243                         up_write(&_origins_lock);
244                         return -ENOMEM;
245                 }
246
247                 /* Initialise the struct */
248                 INIT_LIST_HEAD(&o->snapshots);
249                 o->bdev = bdev;
250
251                 __insert_origin(o);
252         }
253
254         list_add_tail(&snap->list, &o->snapshots);
255
256         up_write(&_origins_lock);
257         return 0;
258 }
259
260 static void unregister_snapshot(struct dm_snapshot *s)
261 {
262         struct origin *o;
263
264         down_write(&_origins_lock);
265         o = __lookup_origin(s->origin->bdev);
266
267         list_del(&s->list);
268         if (list_empty(&o->snapshots)) {
269                 list_del(&o->hash_list);
270                 kfree(o);
271         }
272
273         up_write(&_origins_lock);
274 }
275
276 /*
277  * Implementation of the exception hash tables.
278  * The lowest hash_shift bits of the chunk number are ignored, allowing
279  * some consecutive chunks to be grouped together.
280  */
281 static int init_exception_table(struct exception_table *et, uint32_t size,
282                                 unsigned hash_shift)
283 {
284         unsigned int i;
285
286         et->hash_shift = hash_shift;
287         et->hash_mask = size - 1;
288         et->table = dm_vcalloc(size, sizeof(struct list_head));
289         if (!et->table)
290                 return -ENOMEM;
291
292         for (i = 0; i < size; i++)
293                 INIT_LIST_HEAD(et->table + i);
294
295         return 0;
296 }
297
298 static void exit_exception_table(struct exception_table *et, struct kmem_cache *mem)
299 {
300         struct list_head *slot;
301         struct dm_snap_exception *ex, *next;
302         int i, size;
303
304         size = et->hash_mask + 1;
305         for (i = 0; i < size; i++) {
306                 slot = et->table + i;
307
308                 list_for_each_entry_safe (ex, next, slot, hash_list)
309                         kmem_cache_free(mem, ex);
310         }
311
312         vfree(et->table);
313 }
314
315 static uint32_t exception_hash(struct exception_table *et, chunk_t chunk)
316 {
317         return (chunk >> et->hash_shift) & et->hash_mask;
318 }
319
320 static void insert_exception(struct exception_table *eh,
321                              struct dm_snap_exception *e)
322 {
323         struct list_head *l = &eh->table[exception_hash(eh, e->old_chunk)];
324         list_add(&e->hash_list, l);
325 }
326
327 static void remove_exception(struct dm_snap_exception *e)
328 {
329         list_del(&e->hash_list);
330 }
331
332 /*
333  * Return the exception data for a sector, or NULL if not
334  * remapped.
335  */
336 static struct dm_snap_exception *lookup_exception(struct exception_table *et,
337                                                   chunk_t chunk)
338 {
339         struct list_head *slot;
340         struct dm_snap_exception *e;
341
342         slot = &et->table[exception_hash(et, chunk)];
343         list_for_each_entry (e, slot, hash_list)
344                 if (chunk >= e->old_chunk &&
345                     chunk <= e->old_chunk + dm_consecutive_chunk_count(e))
346                         return e;
347
348         return NULL;
349 }
350
351 static struct dm_snap_exception *alloc_exception(void)
352 {
353         struct dm_snap_exception *e;
354
355         e = kmem_cache_alloc(exception_cache, GFP_NOIO);
356         if (!e)
357                 e = kmem_cache_alloc(exception_cache, GFP_ATOMIC);
358
359         return e;
360 }
361
362 static void free_exception(struct dm_snap_exception *e)
363 {
364         kmem_cache_free(exception_cache, e);
365 }
366
367 static struct dm_snap_pending_exception *alloc_pending_exception(void)
368 {
369         return mempool_alloc(pending_pool, GFP_NOIO);
370 }
371
372 static void free_pending_exception(struct dm_snap_pending_exception *pe)
373 {
374         mempool_free(pe, pending_pool);
375 }
376
377 static void insert_completed_exception(struct dm_snapshot *s,
378                                        struct dm_snap_exception *new_e)
379 {
380         struct exception_table *eh = &s->complete;
381         struct list_head *l;
382         struct dm_snap_exception *e = NULL;
383
384         l = &eh->table[exception_hash(eh, new_e->old_chunk)];
385
386         /* Add immediately if this table doesn't support consecutive chunks */
387         if (!eh->hash_shift)
388                 goto out;
389
390         /* List is ordered by old_chunk */
391         list_for_each_entry_reverse(e, l, hash_list) {
392                 /* Insert after an existing chunk? */
393                 if (new_e->old_chunk == (e->old_chunk +
394                                          dm_consecutive_chunk_count(e) + 1) &&
395                     new_e->new_chunk == (dm_chunk_number(e->new_chunk) +
396                                          dm_consecutive_chunk_count(e) + 1)) {
397                         dm_consecutive_chunk_count_inc(e);
398                         free_exception(new_e);
399                         return;
400                 }
401
402                 /* Insert before an existing chunk? */
403                 if (new_e->old_chunk == (e->old_chunk - 1) &&
404                     new_e->new_chunk == (dm_chunk_number(e->new_chunk) - 1)) {
405                         dm_consecutive_chunk_count_inc(e);
406                         e->old_chunk--;
407                         e->new_chunk--;
408                         free_exception(new_e);
409                         return;
410                 }
411
412                 if (new_e->old_chunk > e->old_chunk)
413                         break;
414         }
415
416 out:
417         list_add(&new_e->hash_list, e ? &e->hash_list : l);
418 }
419
420 int dm_add_exception(struct dm_snapshot *s, chunk_t old, chunk_t new)
421 {
422         struct dm_snap_exception *e;
423
424         e = alloc_exception();
425         if (!e)
426                 return -ENOMEM;
427
428         e->old_chunk = old;
429
430         /* Consecutive_count is implicitly initialised to zero */
431         e->new_chunk = new;
432
433         insert_completed_exception(s, e);
434
435         return 0;
436 }
437
438 /*
439  * Hard coded magic.
440  */
441 static int calc_max_buckets(void)
442 {
443         /* use a fixed size of 2MB */
444         unsigned long mem = 2 * 1024 * 1024;
445         mem /= sizeof(struct list_head);
446
447         return mem;
448 }
449
450 /*
451  * Allocate room for a suitable hash table.
452  */
453 static int init_hash_tables(struct dm_snapshot *s)
454 {
455         sector_t hash_size, cow_dev_size, origin_dev_size, max_buckets;
456
457         /*
458          * Calculate based on the size of the original volume or
459          * the COW volume...
460          */
461         cow_dev_size = get_dev_size(s->cow->bdev);
462         origin_dev_size = get_dev_size(s->origin->bdev);
463         max_buckets = calc_max_buckets();
464
465         hash_size = min(origin_dev_size, cow_dev_size) >> s->chunk_shift;
466         hash_size = min(hash_size, max_buckets);
467
468         hash_size = rounddown_pow_of_two(hash_size);
469         if (init_exception_table(&s->complete, hash_size,
470                                  DM_CHUNK_CONSECUTIVE_BITS))
471                 return -ENOMEM;
472
473         /*
474          * Allocate hash table for in-flight exceptions
475          * Make this smaller than the real hash table
476          */
477         hash_size >>= 3;
478         if (hash_size < 64)
479                 hash_size = 64;
480
481         if (init_exception_table(&s->pending, hash_size, 0)) {
482                 exit_exception_table(&s->complete, exception_cache);
483                 return -ENOMEM;
484         }
485
486         return 0;
487 }
488
489 /*
490  * Round a number up to the nearest 'size' boundary.  size must
491  * be a power of 2.
492  */
493 static ulong round_up(ulong n, ulong size)
494 {
495         size--;
496         return (n + size) & ~size;
497 }
498
499 static int set_chunk_size(struct dm_snapshot *s, const char *chunk_size_arg,
500                           char **error)
501 {
502         unsigned long chunk_size;
503         char *value;
504
505         chunk_size = simple_strtoul(chunk_size_arg, &value, 10);
506         if (*chunk_size_arg == '\0' || *value != '\0') {
507                 *error = "Invalid chunk size";
508                 return -EINVAL;
509         }
510
511         if (!chunk_size) {
512                 s->chunk_size = s->chunk_mask = s->chunk_shift = 0;
513                 return 0;
514         }
515
516         /*
517          * Chunk size must be multiple of page size.  Silently
518          * round up if it's not.
519          */
520         chunk_size = round_up(chunk_size, PAGE_SIZE >> 9);
521
522         /* Check chunk_size is a power of 2 */
523         if (!is_power_of_2(chunk_size)) {
524                 *error = "Chunk size is not a power of 2";
525                 return -EINVAL;
526         }
527
528         /* Validate the chunk size against the device block size */
529         if (chunk_size % (bdev_hardsect_size(s->cow->bdev) >> 9)) {
530                 *error = "Chunk size is not a multiple of device blocksize";
531                 return -EINVAL;
532         }
533
534         s->chunk_size = chunk_size;
535         s->chunk_mask = chunk_size - 1;
536         s->chunk_shift = ffs(chunk_size) - 1;
537
538         return 0;
539 }
540
541 /*
542  * Construct a snapshot mapping: <origin_dev> <COW-dev> <p/n> <chunk-size>
543  */
544 static int snapshot_ctr(struct dm_target *ti, unsigned int argc, char **argv)
545 {
546         struct dm_snapshot *s;
547         int i;
548         int r = -EINVAL;
549         char persistent;
550         char *origin_path;
551         char *cow_path;
552
553         if (argc != 4) {
554                 ti->error = "requires exactly 4 arguments";
555                 r = -EINVAL;
556                 goto bad1;
557         }
558
559         origin_path = argv[0];
560         cow_path = argv[1];
561         persistent = toupper(*argv[2]);
562
563         if (persistent != 'P' && persistent != 'N') {
564                 ti->error = "Persistent flag is not P or N";
565                 r = -EINVAL;
566                 goto bad1;
567         }
568
569         s = kmalloc(sizeof(*s), GFP_KERNEL);
570         if (s == NULL) {
571                 ti->error = "Cannot allocate snapshot context private "
572                     "structure";
573                 r = -ENOMEM;
574                 goto bad1;
575         }
576
577         r = dm_get_device(ti, origin_path, 0, ti->len, FMODE_READ, &s->origin);
578         if (r) {
579                 ti->error = "Cannot get origin device";
580                 goto bad2;
581         }
582
583         r = dm_get_device(ti, cow_path, 0, 0,
584                           FMODE_READ | FMODE_WRITE, &s->cow);
585         if (r) {
586                 dm_put_device(ti, s->origin);
587                 ti->error = "Cannot get COW device";
588                 goto bad2;
589         }
590
591         r = set_chunk_size(s, argv[3], &ti->error);
592         if (r)
593                 goto bad3;
594
595         s->type = persistent;
596
597         s->valid = 1;
598         s->active = 0;
599         s->last_percent = 0;
600         init_rwsem(&s->lock);
601         spin_lock_init(&s->pe_lock);
602         s->ti = ti;
603
604         /* Allocate hash table for COW data */
605         if (init_hash_tables(s)) {
606                 ti->error = "Unable to allocate hash table space";
607                 r = -ENOMEM;
608                 goto bad3;
609         }
610
611         s->store.snap = s;
612
613         if (persistent == 'P')
614                 r = dm_create_persistent(&s->store);
615         else
616                 r = dm_create_transient(&s->store);
617
618         if (r) {
619                 ti->error = "Couldn't create exception store";
620                 r = -EINVAL;
621                 goto bad4;
622         }
623
624         r = dm_kcopyd_client_create(SNAPSHOT_PAGES, &s->kcopyd_client);
625         if (r) {
626                 ti->error = "Could not create kcopyd client";
627                 goto bad5;
628         }
629
630         s->tracked_chunk_pool = mempool_create_slab_pool(MIN_IOS,
631                                                          tracked_chunk_cache);
632         if (!s->tracked_chunk_pool) {
633                 ti->error = "Could not allocate tracked_chunk mempool for "
634                             "tracking reads";
635                 goto bad6;
636         }
637
638         for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
639                 INIT_HLIST_HEAD(&s->tracked_chunk_hash[i]);
640
641         spin_lock_init(&s->tracked_chunk_lock);
642
643         /* Metadata must only be loaded into one table at once */
644         r = s->store.read_metadata(&s->store);
645         if (r < 0) {
646                 ti->error = "Failed to read snapshot metadata";
647                 goto bad_load_and_register;
648         } else if (r > 0) {
649                 s->valid = 0;
650                 DMWARN("Snapshot is marked invalid.");
651         }
652
653         bio_list_init(&s->queued_bios);
654         INIT_WORK(&s->queued_bios_work, flush_queued_bios);
655
656         /* Add snapshot to the list of snapshots for this origin */
657         /* Exceptions aren't triggered till snapshot_resume() is called */
658         if (register_snapshot(s)) {
659                 r = -EINVAL;
660                 ti->error = "Cannot register snapshot origin";
661                 goto bad_load_and_register;
662         }
663
664         ti->private = s;
665         ti->split_io = s->chunk_size;
666
667         return 0;
668
669  bad_load_and_register:
670         mempool_destroy(s->tracked_chunk_pool);
671
672  bad6:
673         dm_kcopyd_client_destroy(s->kcopyd_client);
674
675  bad5:
676         s->store.destroy(&s->store);
677
678  bad4:
679         exit_exception_table(&s->pending, pending_cache);
680         exit_exception_table(&s->complete, exception_cache);
681
682  bad3:
683         dm_put_device(ti, s->cow);
684         dm_put_device(ti, s->origin);
685
686  bad2:
687         kfree(s);
688
689  bad1:
690         return r;
691 }
692
693 static void __free_exceptions(struct dm_snapshot *s)
694 {
695         dm_kcopyd_client_destroy(s->kcopyd_client);
696         s->kcopyd_client = NULL;
697
698         exit_exception_table(&s->pending, pending_cache);
699         exit_exception_table(&s->complete, exception_cache);
700
701         s->store.destroy(&s->store);
702 }
703
704 static void snapshot_dtr(struct dm_target *ti)
705 {
706 #ifdef CONFIG_DM_DEBUG
707         int i;
708 #endif
709         struct dm_snapshot *s = ti->private;
710
711         flush_workqueue(ksnapd);
712
713         /* Prevent further origin writes from using this snapshot. */
714         /* After this returns there can be no new kcopyd jobs. */
715         unregister_snapshot(s);
716
717 #ifdef CONFIG_DM_DEBUG
718         for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
719                 BUG_ON(!hlist_empty(&s->tracked_chunk_hash[i]));
720 #endif
721
722         mempool_destroy(s->tracked_chunk_pool);
723
724         __free_exceptions(s);
725
726         dm_put_device(ti, s->origin);
727         dm_put_device(ti, s->cow);
728
729         kfree(s);
730 }
731
732 /*
733  * Flush a list of buffers.
734  */
735 static void flush_bios(struct bio *bio)
736 {
737         struct bio *n;
738
739         while (bio) {
740                 n = bio->bi_next;
741                 bio->bi_next = NULL;
742                 generic_make_request(bio);
743                 bio = n;
744         }
745 }
746
747 static void flush_queued_bios(struct work_struct *work)
748 {
749         struct dm_snapshot *s =
750                 container_of(work, struct dm_snapshot, queued_bios_work);
751         struct bio *queued_bios;
752         unsigned long flags;
753
754         spin_lock_irqsave(&s->pe_lock, flags);
755         queued_bios = bio_list_get(&s->queued_bios);
756         spin_unlock_irqrestore(&s->pe_lock, flags);
757
758         flush_bios(queued_bios);
759 }
760
761 /*
762  * Error a list of buffers.
763  */
764 static void error_bios(struct bio *bio)
765 {
766         struct bio *n;
767
768         while (bio) {
769                 n = bio->bi_next;
770                 bio->bi_next = NULL;
771                 bio_io_error(bio);
772                 bio = n;
773         }
774 }
775
776 static void __invalidate_snapshot(struct dm_snapshot *s, int err)
777 {
778         if (!s->valid)
779                 return;
780
781         if (err == -EIO)
782                 DMERR("Invalidating snapshot: Error reading/writing.");
783         else if (err == -ENOMEM)
784                 DMERR("Invalidating snapshot: Unable to allocate exception.");
785
786         if (s->store.drop_snapshot)
787                 s->store.drop_snapshot(&s->store);
788
789         s->valid = 0;
790
791         dm_table_event(s->ti->table);
792 }
793
794 static void get_pending_exception(struct dm_snap_pending_exception *pe)
795 {
796         atomic_inc(&pe->ref_count);
797 }
798
799 static struct bio *put_pending_exception(struct dm_snap_pending_exception *pe)
800 {
801         struct dm_snap_pending_exception *primary_pe;
802         struct bio *origin_bios = NULL;
803
804         primary_pe = pe->primary_pe;
805
806         /*
807          * If this pe is involved in a write to the origin and
808          * it is the last sibling to complete then release
809          * the bios for the original write to the origin.
810          */
811         if (primary_pe &&
812             atomic_dec_and_test(&primary_pe->ref_count))
813                 origin_bios = bio_list_get(&primary_pe->origin_bios);
814
815         /*
816          * Free the pe if it's not linked to an origin write or if
817          * it's not itself a primary pe.
818          */
819         if (!primary_pe || primary_pe != pe)
820                 free_pending_exception(pe);
821
822         /*
823          * Free the primary pe if nothing references it.
824          */
825         if (primary_pe && !atomic_read(&primary_pe->ref_count))
826                 free_pending_exception(primary_pe);
827
828         return origin_bios;
829 }
830
831 static void pending_complete(struct dm_snap_pending_exception *pe, int success)
832 {
833         struct dm_snap_exception *e;
834         struct dm_snapshot *s = pe->snap;
835         struct bio *origin_bios = NULL;
836         struct bio *snapshot_bios = NULL;
837         int error = 0;
838
839         if (!success) {
840                 /* Read/write error - snapshot is unusable */
841                 down_write(&s->lock);
842                 __invalidate_snapshot(s, -EIO);
843                 error = 1;
844                 goto out;
845         }
846
847         e = alloc_exception();
848         if (!e) {
849                 down_write(&s->lock);
850                 __invalidate_snapshot(s, -ENOMEM);
851                 error = 1;
852                 goto out;
853         }
854         *e = pe->e;
855
856         down_write(&s->lock);
857         if (!s->valid) {
858                 free_exception(e);
859                 error = 1;
860                 goto out;
861         }
862
863         /*
864          * Check for conflicting reads. This is extremely improbable,
865          * so yield() is sufficient and there is no need for a wait queue.
866          */
867         while (__chunk_is_tracked(s, pe->e.old_chunk))
868                 yield();
869
870         /*
871          * Add a proper exception, and remove the
872          * in-flight exception from the list.
873          */
874         insert_completed_exception(s, e);
875
876  out:
877         remove_exception(&pe->e);
878         snapshot_bios = bio_list_get(&pe->snapshot_bios);
879         origin_bios = put_pending_exception(pe);
880
881         up_write(&s->lock);
882
883         /* Submit any pending write bios */
884         if (error)
885                 error_bios(snapshot_bios);
886         else
887                 flush_bios(snapshot_bios);
888
889         flush_bios(origin_bios);
890 }
891
892 static void commit_callback(void *context, int success)
893 {
894         struct dm_snap_pending_exception *pe = context;
895
896         pending_complete(pe, success);
897 }
898
899 /*
900  * Called when the copy I/O has finished.  kcopyd actually runs
901  * this code so don't block.
902  */
903 static void copy_callback(int read_err, unsigned long write_err, void *context)
904 {
905         struct dm_snap_pending_exception *pe = context;
906         struct dm_snapshot *s = pe->snap;
907
908         if (read_err || write_err)
909                 pending_complete(pe, 0);
910
911         else
912                 /* Update the metadata if we are persistent */
913                 s->store.commit_exception(&s->store, &pe->e, commit_callback,
914                                           pe);
915 }
916
917 /*
918  * Dispatches the copy operation to kcopyd.
919  */
920 static void start_copy(struct dm_snap_pending_exception *pe)
921 {
922         struct dm_snapshot *s = pe->snap;
923         struct dm_io_region src, dest;
924         struct block_device *bdev = s->origin->bdev;
925         sector_t dev_size;
926
927         dev_size = get_dev_size(bdev);
928
929         src.bdev = bdev;
930         src.sector = chunk_to_sector(s, pe->e.old_chunk);
931         src.count = min(s->chunk_size, dev_size - src.sector);
932
933         dest.bdev = s->cow->bdev;
934         dest.sector = chunk_to_sector(s, pe->e.new_chunk);
935         dest.count = src.count;
936
937         /* Hand over to kcopyd */
938         dm_kcopyd_copy(s->kcopyd_client,
939                     &src, 1, &dest, 0, copy_callback, pe);
940 }
941
942 /*
943  * Looks to see if this snapshot already has a pending exception
944  * for this chunk, otherwise it allocates a new one and inserts
945  * it into the pending table.
946  *
947  * NOTE: a write lock must be held on snap->lock before calling
948  * this.
949  */
950 static struct dm_snap_pending_exception *
951 __find_pending_exception(struct dm_snapshot *s, struct bio *bio)
952 {
953         struct dm_snap_exception *e;
954         struct dm_snap_pending_exception *pe;
955         chunk_t chunk = sector_to_chunk(s, bio->bi_sector);
956
957         /*
958          * Is there a pending exception for this already ?
959          */
960         e = lookup_exception(&s->pending, chunk);
961         if (e) {
962                 /* cast the exception to a pending exception */
963                 pe = container_of(e, struct dm_snap_pending_exception, e);
964                 goto out;
965         }
966
967         /*
968          * Create a new pending exception, we don't want
969          * to hold the lock while we do this.
970          */
971         up_write(&s->lock);
972         pe = alloc_pending_exception();
973         down_write(&s->lock);
974
975         if (!s->valid) {
976                 free_pending_exception(pe);
977                 return NULL;
978         }
979
980         e = lookup_exception(&s->pending, chunk);
981         if (e) {
982                 free_pending_exception(pe);
983                 pe = container_of(e, struct dm_snap_pending_exception, e);
984                 goto out;
985         }
986
987         pe->e.old_chunk = chunk;
988         bio_list_init(&pe->origin_bios);
989         bio_list_init(&pe->snapshot_bios);
990         pe->primary_pe = NULL;
991         atomic_set(&pe->ref_count, 0);
992         pe->snap = s;
993         pe->started = 0;
994
995         if (s->store.prepare_exception(&s->store, &pe->e)) {
996                 free_pending_exception(pe);
997                 return NULL;
998         }
999
1000         get_pending_exception(pe);
1001         insert_exception(&s->pending, &pe->e);
1002
1003  out:
1004         return pe;
1005 }
1006
1007 static void remap_exception(struct dm_snapshot *s, struct dm_snap_exception *e,
1008                             struct bio *bio, chunk_t chunk)
1009 {
1010         bio->bi_bdev = s->cow->bdev;
1011         bio->bi_sector = chunk_to_sector(s, dm_chunk_number(e->new_chunk) +
1012                          (chunk - e->old_chunk)) +
1013                          (bio->bi_sector & s->chunk_mask);
1014 }
1015
1016 static int snapshot_map(struct dm_target *ti, struct bio *bio,
1017                         union map_info *map_context)
1018 {
1019         struct dm_snap_exception *e;
1020         struct dm_snapshot *s = ti->private;
1021         int r = DM_MAPIO_REMAPPED;
1022         chunk_t chunk;
1023         struct dm_snap_pending_exception *pe = NULL;
1024
1025         chunk = sector_to_chunk(s, bio->bi_sector);
1026
1027         /* Full snapshots are not usable */
1028         /* To get here the table must be live so s->active is always set. */
1029         if (!s->valid)
1030                 return -EIO;
1031
1032         /* FIXME: should only take write lock if we need
1033          * to copy an exception */
1034         down_write(&s->lock);
1035
1036         if (!s->valid) {
1037                 r = -EIO;
1038                 goto out_unlock;
1039         }
1040
1041         /* If the block is already remapped - use that, else remap it */
1042         e = lookup_exception(&s->complete, chunk);
1043         if (e) {
1044                 remap_exception(s, e, bio, chunk);
1045                 goto out_unlock;
1046         }
1047
1048         /*
1049          * Write to snapshot - higher level takes care of RW/RO
1050          * flags so we should only get this if we are
1051          * writeable.
1052          */
1053         if (bio_rw(bio) == WRITE) {
1054                 pe = __find_pending_exception(s, bio);
1055                 if (!pe) {
1056                         __invalidate_snapshot(s, -ENOMEM);
1057                         r = -EIO;
1058                         goto out_unlock;
1059                 }
1060
1061                 remap_exception(s, &pe->e, bio, chunk);
1062                 bio_list_add(&pe->snapshot_bios, bio);
1063
1064                 r = DM_MAPIO_SUBMITTED;
1065
1066                 if (!pe->started) {
1067                         /* this is protected by snap->lock */
1068                         pe->started = 1;
1069                         up_write(&s->lock);
1070                         start_copy(pe);
1071                         goto out;
1072                 }
1073         } else {
1074                 bio->bi_bdev = s->origin->bdev;
1075                 map_context->ptr = track_chunk(s, chunk);
1076         }
1077
1078  out_unlock:
1079         up_write(&s->lock);
1080  out:
1081         return r;
1082 }
1083
1084 static int snapshot_end_io(struct dm_target *ti, struct bio *bio,
1085                            int error, union map_info *map_context)
1086 {
1087         struct dm_snapshot *s = ti->private;
1088         struct dm_snap_tracked_chunk *c = map_context->ptr;
1089
1090         if (c)
1091                 stop_tracking_chunk(s, c);
1092
1093         return 0;
1094 }
1095
1096 static void snapshot_resume(struct dm_target *ti)
1097 {
1098         struct dm_snapshot *s = ti->private;
1099
1100         down_write(&s->lock);
1101         s->active = 1;
1102         up_write(&s->lock);
1103 }
1104
1105 static int snapshot_status(struct dm_target *ti, status_type_t type,
1106                            char *result, unsigned int maxlen)
1107 {
1108         struct dm_snapshot *snap = ti->private;
1109
1110         switch (type) {
1111         case STATUSTYPE_INFO:
1112                 if (!snap->valid)
1113                         snprintf(result, maxlen, "Invalid");
1114                 else {
1115                         if (snap->store.fraction_full) {
1116                                 sector_t numerator, denominator;
1117                                 snap->store.fraction_full(&snap->store,
1118                                                           &numerator,
1119                                                           &denominator);
1120                                 snprintf(result, maxlen, "%llu/%llu",
1121                                         (unsigned long long)numerator,
1122                                         (unsigned long long)denominator);
1123                         }
1124                         else
1125                                 snprintf(result, maxlen, "Unknown");
1126                 }
1127                 break;
1128
1129         case STATUSTYPE_TABLE:
1130                 /*
1131                  * kdevname returns a static pointer so we need
1132                  * to make private copies if the output is to
1133                  * make sense.
1134                  */
1135                 snprintf(result, maxlen, "%s %s %c %llu",
1136                          snap->origin->name, snap->cow->name,
1137                          snap->type,
1138                          (unsigned long long)snap->chunk_size);
1139                 break;
1140         }
1141
1142         return 0;
1143 }
1144
1145 /*-----------------------------------------------------------------
1146  * Origin methods
1147  *---------------------------------------------------------------*/
1148 static int __origin_write(struct list_head *snapshots, struct bio *bio)
1149 {
1150         int r = DM_MAPIO_REMAPPED, first = 0;
1151         struct dm_snapshot *snap;
1152         struct dm_snap_exception *e;
1153         struct dm_snap_pending_exception *pe, *next_pe, *primary_pe = NULL;
1154         chunk_t chunk;
1155         LIST_HEAD(pe_queue);
1156
1157         /* Do all the snapshots on this origin */
1158         list_for_each_entry (snap, snapshots, list) {
1159
1160                 down_write(&snap->lock);
1161
1162                 /* Only deal with valid and active snapshots */
1163                 if (!snap->valid || !snap->active)
1164                         goto next_snapshot;
1165
1166                 /* Nothing to do if writing beyond end of snapshot */
1167                 if (bio->bi_sector >= dm_table_get_size(snap->ti->table))
1168                         goto next_snapshot;
1169
1170                 /*
1171                  * Remember, different snapshots can have
1172                  * different chunk sizes.
1173                  */
1174                 chunk = sector_to_chunk(snap, bio->bi_sector);
1175
1176                 /*
1177                  * Check exception table to see if block
1178                  * is already remapped in this snapshot
1179                  * and trigger an exception if not.
1180                  *
1181                  * ref_count is initialised to 1 so pending_complete()
1182                  * won't destroy the primary_pe while we're inside this loop.
1183                  */
1184                 e = lookup_exception(&snap->complete, chunk);
1185                 if (e)
1186                         goto next_snapshot;
1187
1188                 pe = __find_pending_exception(snap, bio);
1189                 if (!pe) {
1190                         __invalidate_snapshot(snap, -ENOMEM);
1191                         goto next_snapshot;
1192                 }
1193
1194                 if (!primary_pe) {
1195                         /*
1196                          * Either every pe here has same
1197                          * primary_pe or none has one yet.
1198                          */
1199                         if (pe->primary_pe)
1200                                 primary_pe = pe->primary_pe;
1201                         else {
1202                                 primary_pe = pe;
1203                                 first = 1;
1204                         }
1205
1206                         bio_list_add(&primary_pe->origin_bios, bio);
1207
1208                         r = DM_MAPIO_SUBMITTED;
1209                 }
1210
1211                 if (!pe->primary_pe) {
1212                         pe->primary_pe = primary_pe;
1213                         get_pending_exception(primary_pe);
1214                 }
1215
1216                 if (!pe->started) {
1217                         pe->started = 1;
1218                         list_add_tail(&pe->list, &pe_queue);
1219                 }
1220
1221  next_snapshot:
1222                 up_write(&snap->lock);
1223         }
1224
1225         if (!primary_pe)
1226                 return r;
1227
1228         /*
1229          * If this is the first time we're processing this chunk and
1230          * ref_count is now 1 it means all the pending exceptions
1231          * got completed while we were in the loop above, so it falls to
1232          * us here to remove the primary_pe and submit any origin_bios.
1233          */
1234
1235         if (first && atomic_dec_and_test(&primary_pe->ref_count)) {
1236                 flush_bios(bio_list_get(&primary_pe->origin_bios));
1237                 free_pending_exception(primary_pe);
1238                 /* If we got here, pe_queue is necessarily empty. */
1239                 return r;
1240         }
1241
1242         /*
1243          * Now that we have a complete pe list we can start the copying.
1244          */
1245         list_for_each_entry_safe(pe, next_pe, &pe_queue, list)
1246                 start_copy(pe);
1247
1248         return r;
1249 }
1250
1251 /*
1252  * Called on a write from the origin driver.
1253  */
1254 static int do_origin(struct dm_dev *origin, struct bio *bio)
1255 {
1256         struct origin *o;
1257         int r = DM_MAPIO_REMAPPED;
1258
1259         down_read(&_origins_lock);
1260         o = __lookup_origin(origin->bdev);
1261         if (o)
1262                 r = __origin_write(&o->snapshots, bio);
1263         up_read(&_origins_lock);
1264
1265         return r;
1266 }
1267
1268 /*
1269  * Origin: maps a linear range of a device, with hooks for snapshotting.
1270  */
1271
1272 /*
1273  * Construct an origin mapping: <dev_path>
1274  * The context for an origin is merely a 'struct dm_dev *'
1275  * pointing to the real device.
1276  */
1277 static int origin_ctr(struct dm_target *ti, unsigned int argc, char **argv)
1278 {
1279         int r;
1280         struct dm_dev *dev;
1281
1282         if (argc != 1) {
1283                 ti->error = "origin: incorrect number of arguments";
1284                 return -EINVAL;
1285         }
1286
1287         r = dm_get_device(ti, argv[0], 0, ti->len,
1288                           dm_table_get_mode(ti->table), &dev);
1289         if (r) {
1290                 ti->error = "Cannot get target device";
1291                 return r;
1292         }
1293
1294         ti->private = dev;
1295         return 0;
1296 }
1297
1298 static void origin_dtr(struct dm_target *ti)
1299 {
1300         struct dm_dev *dev = ti->private;
1301         dm_put_device(ti, dev);
1302 }
1303
1304 static int origin_map(struct dm_target *ti, struct bio *bio,
1305                       union map_info *map_context)
1306 {
1307         struct dm_dev *dev = ti->private;
1308         bio->bi_bdev = dev->bdev;
1309
1310         /* Only tell snapshots if this is a write */
1311         return (bio_rw(bio) == WRITE) ? do_origin(dev, bio) : DM_MAPIO_REMAPPED;
1312 }
1313
1314 #define min_not_zero(l, r) (l == 0) ? r : ((r == 0) ? l : min(l, r))
1315
1316 /*
1317  * Set the target "split_io" field to the minimum of all the snapshots'
1318  * chunk sizes.
1319  */
1320 static void origin_resume(struct dm_target *ti)
1321 {
1322         struct dm_dev *dev = ti->private;
1323         struct dm_snapshot *snap;
1324         struct origin *o;
1325         chunk_t chunk_size = 0;
1326
1327         down_read(&_origins_lock);
1328         o = __lookup_origin(dev->bdev);
1329         if (o)
1330                 list_for_each_entry (snap, &o->snapshots, list)
1331                         chunk_size = min_not_zero(chunk_size, snap->chunk_size);
1332         up_read(&_origins_lock);
1333
1334         ti->split_io = chunk_size;
1335 }
1336
1337 static int origin_status(struct dm_target *ti, status_type_t type, char *result,
1338                          unsigned int maxlen)
1339 {
1340         struct dm_dev *dev = ti->private;
1341
1342         switch (type) {
1343         case STATUSTYPE_INFO:
1344                 result[0] = '\0';
1345                 break;
1346
1347         case STATUSTYPE_TABLE:
1348                 snprintf(result, maxlen, "%s", dev->name);
1349                 break;
1350         }
1351
1352         return 0;
1353 }
1354
1355 static struct target_type origin_target = {
1356         .name    = "snapshot-origin",
1357         .version = {1, 6, 0},
1358         .module  = THIS_MODULE,
1359         .ctr     = origin_ctr,
1360         .dtr     = origin_dtr,
1361         .map     = origin_map,
1362         .resume  = origin_resume,
1363         .status  = origin_status,
1364 };
1365
1366 static struct target_type snapshot_target = {
1367         .name    = "snapshot",
1368         .version = {1, 6, 0},
1369         .module  = THIS_MODULE,
1370         .ctr     = snapshot_ctr,
1371         .dtr     = snapshot_dtr,
1372         .map     = snapshot_map,
1373         .end_io  = snapshot_end_io,
1374         .resume  = snapshot_resume,
1375         .status  = snapshot_status,
1376 };
1377
1378 static int __init dm_snapshot_init(void)
1379 {
1380         int r;
1381
1382         r = dm_register_target(&snapshot_target);
1383         if (r) {
1384                 DMERR("snapshot target register failed %d", r);
1385                 return r;
1386         }
1387
1388         r = dm_register_target(&origin_target);
1389         if (r < 0) {
1390                 DMERR("Origin target register failed %d", r);
1391                 goto bad1;
1392         }
1393
1394         r = init_origin_hash();
1395         if (r) {
1396                 DMERR("init_origin_hash failed.");
1397                 goto bad2;
1398         }
1399
1400         exception_cache = KMEM_CACHE(dm_snap_exception, 0);
1401         if (!exception_cache) {
1402                 DMERR("Couldn't create exception cache.");
1403                 r = -ENOMEM;
1404                 goto bad3;
1405         }
1406
1407         pending_cache = KMEM_CACHE(dm_snap_pending_exception, 0);
1408         if (!pending_cache) {
1409                 DMERR("Couldn't create pending cache.");
1410                 r = -ENOMEM;
1411                 goto bad4;
1412         }
1413
1414         tracked_chunk_cache = KMEM_CACHE(dm_snap_tracked_chunk, 0);
1415         if (!tracked_chunk_cache) {
1416                 DMERR("Couldn't create cache to track chunks in use.");
1417                 r = -ENOMEM;
1418                 goto bad5;
1419         }
1420
1421         pending_pool = mempool_create_slab_pool(128, pending_cache);
1422         if (!pending_pool) {
1423                 DMERR("Couldn't create pending pool.");
1424                 r = -ENOMEM;
1425                 goto bad_pending_pool;
1426         }
1427
1428         ksnapd = create_singlethread_workqueue("ksnapd");
1429         if (!ksnapd) {
1430                 DMERR("Failed to create ksnapd workqueue.");
1431                 r = -ENOMEM;
1432                 goto bad6;
1433         }
1434
1435         return 0;
1436
1437       bad6:
1438         mempool_destroy(pending_pool);
1439       bad_pending_pool:
1440         kmem_cache_destroy(tracked_chunk_cache);
1441       bad5:
1442         kmem_cache_destroy(pending_cache);
1443       bad4:
1444         kmem_cache_destroy(exception_cache);
1445       bad3:
1446         exit_origin_hash();
1447       bad2:
1448         dm_unregister_target(&origin_target);
1449       bad1:
1450         dm_unregister_target(&snapshot_target);
1451         return r;
1452 }
1453
1454 static void __exit dm_snapshot_exit(void)
1455 {
1456         int r;
1457
1458         destroy_workqueue(ksnapd);
1459
1460         r = dm_unregister_target(&snapshot_target);
1461         if (r)
1462                 DMERR("snapshot unregister failed %d", r);
1463
1464         r = dm_unregister_target(&origin_target);
1465         if (r)
1466                 DMERR("origin unregister failed %d", r);
1467
1468         exit_origin_hash();
1469         mempool_destroy(pending_pool);
1470         kmem_cache_destroy(pending_cache);
1471         kmem_cache_destroy(exception_cache);
1472         kmem_cache_destroy(tracked_chunk_cache);
1473 }
1474
1475 /* Module hooks */
1476 module_init(dm_snapshot_init);
1477 module_exit(dm_snapshot_exit);
1478
1479 MODULE_DESCRIPTION(DM_NAME " snapshot target");
1480 MODULE_AUTHOR("Joe Thornber");
1481 MODULE_LICENSE("GPL");