dm-snap.c

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