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