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