drivers/md/dm-snap.c

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