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