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 = s->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, 4, 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, 4, 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");