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