dm-snap.c 54.1 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10
/*
 * dm-snapshot.c
 *
 * Copyright (C) 2001-2002 Sistina Software (UK) Limited.
 *
 * This file is released under the GPL.
 */

#include <linux/blkdev.h>
#include <linux/device-mapper.h>
11
#include <linux/delay.h>
Linus Torvalds's avatar
Linus Torvalds committed
12 13 14 15 16 17 18 19
#include <linux/fs.h>
#include <linux/init.h>
#include <linux/kdev_t.h>
#include <linux/list.h>
#include <linux/mempool.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/vmalloc.h>
vignesh babu's avatar
vignesh babu committed
20
#include <linux/log2.h>
21
#include <linux/dm-kcopyd.h>
Linus Torvalds's avatar
Linus Torvalds committed
22

23
#include "dm-exception-store.h"
Linus Torvalds's avatar
Linus Torvalds committed
24

25 26
#define DM_MSG_PREFIX "snapshots"

27 28 29 30 31
static const char dm_snapshot_merge_target_name[] = "snapshot-merge";

#define dm_target_is_snapshot_merge(ti) \
	((ti)->type->name == dm_snapshot_merge_target_name)

32 33 34 35 36
/*
 * The size of the mempool used to track chunks in use.
 */
#define MIN_IOS 256

37 38 39 40
#define DM_TRACKED_CHUNK_HASH_SIZE	16
#define DM_TRACKED_CHUNK_HASH(x)	((unsigned long)(x) & \
					 (DM_TRACKED_CHUNK_HASH_SIZE - 1))

41
struct dm_exception_table {
42 43 44 45 46 47 48 49 50
	uint32_t hash_mask;
	unsigned hash_shift;
	struct list_head *table;
};

struct dm_snapshot {
	struct rw_semaphore lock;

	struct dm_dev *origin;
51 52 53
	struct dm_dev *cow;

	struct dm_target *ti;
54 55 56 57

	/* List of snapshots per Origin */
	struct list_head list;

58 59 60 61
	/*
	 * You can't use a snapshot if this is 0 (e.g. if full).
	 * A snapshot-merge target never clears this.
	 */
62 63 64 65 66 67 68
	int valid;

	/* Origin writes don't trigger exceptions until this is set */
	int active;

	atomic_t pending_exceptions_count;

69 70 71 72 73 74 75 76 77 78 79 80
	/* Protected by "lock" */
	sector_t exception_start_sequence;

	/* Protected by kcopyd single-threaded callback */
	sector_t exception_complete_sequence;

	/*
	 * A list of pending exceptions that completed out of order.
	 * Protected by kcopyd single-threaded callback.
	 */
	struct list_head out_of_order_list;

81 82
	mempool_t *pending_pool;

83 84
	struct dm_exception_table pending;
	struct dm_exception_table complete;
85 86 87 88 89 90 91

	/*
	 * pe_lock protects all pending_exception operations and access
	 * as well as the snapshot_bios list.
	 */
	spinlock_t pe_lock;

92 93 94 95
	/* Chunks with outstanding reads */
	spinlock_t tracked_chunk_lock;
	struct hlist_head tracked_chunk_hash[DM_TRACKED_CHUNK_HASH_SIZE];

96 97 98 99 100
	/* The on disk metadata handler */
	struct dm_exception_store *store;

	struct dm_kcopyd_client *kcopyd_client;

101 102 103 104 105 106
	/* Wait for events based on state_bits */
	unsigned long state_bits;

	/* Range of chunks currently being merged. */
	chunk_t first_merging_chunk;
	int num_merging_chunks;
107

108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
	/*
	 * The merge operation failed if this flag is set.
	 * Failure modes are handled as follows:
	 * - I/O error reading the header
	 *   	=> don't load the target; abort.
	 * - Header does not have "valid" flag set
	 *   	=> use the origin; forget about the snapshot.
	 * - I/O error when reading exceptions
	 *   	=> don't load the target; abort.
	 *         (We can't use the intermediate origin state.)
	 * - I/O error while merging
	 *	=> stop merging; set merge_failed; process I/O normally.
	 */
	int merge_failed;

123 124 125 126 127
	/*
	 * Incoming bios that overlap with chunks being merged must wait
	 * for them to be committed.
	 */
	struct bio_list bios_queued_during_merge;
128 129
};

130 131 132 133 134 135 136 137 138
/*
 * state_bits:
 *   RUNNING_MERGE  - Merge operation is in progress.
 *   SHUTDOWN_MERGE - Set to signal that merge needs to be stopped;
 *                    cleared afterwards.
 */
#define RUNNING_MERGE          0
#define SHUTDOWN_MERGE         1

139 140 141
DECLARE_DM_KCOPYD_THROTTLE_WITH_MODULE_PARM(snapshot_copy_throttle,
		"A percentage of time allocated for copy on write");

142 143 144 145 146 147
struct dm_dev *dm_snap_origin(struct dm_snapshot *s)
{
	return s->origin;
}
EXPORT_SYMBOL(dm_snap_origin);

148 149 150 151 152 153
struct dm_dev *dm_snap_cow(struct dm_snapshot *s)
{
	return s->cow;
}
EXPORT_SYMBOL(dm_snap_cow);

154 155 156 157 158 159 160 161 162 163 164 165 166 167 168
static sector_t chunk_to_sector(struct dm_exception_store *store,
				chunk_t chunk)
{
	return chunk << store->chunk_shift;
}

static int bdev_equal(struct block_device *lhs, struct block_device *rhs)
{
	/*
	 * There is only ever one instance of a particular block
	 * device so we can compare pointers safely.
	 */
	return lhs == rhs;
}

169
struct dm_snap_pending_exception {
170
	struct dm_exception e;
Linus Torvalds's avatar
Linus Torvalds committed
171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186

	/*
	 * Origin buffers waiting for this to complete are held
	 * in a bio list
	 */
	struct bio_list origin_bios;
	struct bio_list snapshot_bios;

	/* Pointer back to snapshot context */
	struct dm_snapshot *snap;

	/*
	 * 1 indicates the exception has already been sent to
	 * kcopyd.
	 */
	int started;
187

188 189 190 191 192 193 194 195
	/* There was copying error. */
	int copy_error;

	/* A sequence number, it is used for in-order completion. */
	sector_t exception_sequence;

	struct list_head out_of_order_entry;

196 197 198 199 200 201
	/*
	 * For writing a complete chunk, bypassing the copy.
	 */
	struct bio *full_bio;
	bio_end_io_t *full_bio_end_io;
	void *full_bio_private;
Linus Torvalds's avatar
Linus Torvalds committed
202 203 204 205 206 207
};

/*
 * Hash table mapping origin volumes to lists of snapshots and
 * a lock to protect it
 */
208 209
static struct kmem_cache *exception_cache;
static struct kmem_cache *pending_cache;
Linus Torvalds's avatar
Linus Torvalds committed
210

211 212 213 214 215
struct dm_snap_tracked_chunk {
	struct hlist_node node;
	chunk_t chunk;
};

216 217 218 219 220 221 222 223 224 225 226 227 228
static void init_tracked_chunk(struct bio *bio)
{
	struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk));
	INIT_HLIST_NODE(&c->node);
}

static bool is_bio_tracked(struct bio *bio)
{
	struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk));
	return !hlist_unhashed(&c->node);
}

static void track_chunk(struct dm_snapshot *s, struct bio *bio, chunk_t chunk)
229
{
230
	struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk));
231 232 233

	c->chunk = chunk;

234
	spin_lock_irq(&s->tracked_chunk_lock);
235 236
	hlist_add_head(&c->node,
		       &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)]);
237
	spin_unlock_irq(&s->tracked_chunk_lock);
238 239
}

240
static void stop_tracking_chunk(struct dm_snapshot *s, struct bio *bio)
241
{
242
	struct dm_snap_tracked_chunk *c = dm_per_bio_data(bio, sizeof(struct dm_snap_tracked_chunk));
243 244 245 246 247 248 249
	unsigned long flags;

	spin_lock_irqsave(&s->tracked_chunk_lock, flags);
	hlist_del(&c->node);
	spin_unlock_irqrestore(&s->tracked_chunk_lock, flags);
}

250 251 252 253 254 255 256
static int __chunk_is_tracked(struct dm_snapshot *s, chunk_t chunk)
{
	struct dm_snap_tracked_chunk *c;
	int found = 0;

	spin_lock_irq(&s->tracked_chunk_lock);

257
	hlist_for_each_entry(c,
258 259 260 261 262 263 264 265 266 267 268 269
	    &s->tracked_chunk_hash[DM_TRACKED_CHUNK_HASH(chunk)], node) {
		if (c->chunk == chunk) {
			found = 1;
			break;
		}
	}

	spin_unlock_irq(&s->tracked_chunk_lock);

	return found;
}

270 271 272 273 274 275 276 277 278 279
/*
 * This conflicting I/O is extremely improbable in the caller,
 * so msleep(1) is sufficient and there is no need for a wait queue.
 */
static void __check_for_conflicting_io(struct dm_snapshot *s, chunk_t chunk)
{
	while (__chunk_is_tracked(s, chunk))
		msleep(1);
}

Linus Torvalds's avatar
Linus Torvalds committed
280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
/*
 * One of these per registered origin, held in the snapshot_origins hash
 */
struct origin {
	/* The origin device */
	struct block_device *bdev;

	struct list_head hash_list;

	/* List of snapshots for this origin */
	struct list_head snapshots;
};

/*
 * Size of the hash table for origin volumes. If we make this
 * the size of the minors list then it should be nearly perfect
 */
#define ORIGIN_HASH_SIZE 256
#define ORIGIN_MASK      0xFF
static struct list_head *_origins;
static struct rw_semaphore _origins_lock;

302 303 304 305
static DECLARE_WAIT_QUEUE_HEAD(_pending_exceptions_done);
static DEFINE_SPINLOCK(_pending_exceptions_done_spinlock);
static uint64_t _pending_exceptions_done_count;

Linus Torvalds's avatar
Linus Torvalds committed
306 307 308 309 310 311 312
static int init_origin_hash(void)
{
	int i;

	_origins = kmalloc(ORIGIN_HASH_SIZE * sizeof(struct list_head),
			   GFP_KERNEL);
	if (!_origins) {
313
		DMERR("unable to allocate memory");
Linus Torvalds's avatar
Linus Torvalds committed
314 315 316 317 318 319 320 321 322 323 324 325 326 327 328
		return -ENOMEM;
	}

	for (i = 0; i < ORIGIN_HASH_SIZE; i++)
		INIT_LIST_HEAD(_origins + i);
	init_rwsem(&_origins_lock);

	return 0;
}

static void exit_origin_hash(void)
{
	kfree(_origins);
}

329
static unsigned origin_hash(struct block_device *bdev)
Linus Torvalds's avatar
Linus Torvalds committed
330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352
{
	return bdev->bd_dev & ORIGIN_MASK;
}

static struct origin *__lookup_origin(struct block_device *origin)
{
	struct list_head *ol;
	struct origin *o;

	ol = &_origins[origin_hash(origin)];
	list_for_each_entry (o, ol, hash_list)
		if (bdev_equal(o->bdev, origin))
			return o;

	return NULL;
}

static void __insert_origin(struct origin *o)
{
	struct list_head *sl = &_origins[origin_hash(o->bdev)];
	list_add_tail(&o->hash_list, sl);
}

353 354 355 356 357
/*
 * _origins_lock must be held when calling this function.
 * Returns number of snapshots registered using the supplied cow device, plus:
 * snap_src - a snapshot suitable for use as a source of exception handover
 * snap_dest - a snapshot capable of receiving exception handover.
358 359
 * snap_merge - an existing snapshot-merge target linked to the same origin.
 *   There can be at most one snapshot-merge target. The parameter is optional.
360
 *
361
 * Possible return values and states of snap_src and snap_dest.
362 363 364 365 366 367 368 369
 *   0: NULL, NULL  - first new snapshot
 *   1: snap_src, NULL - normal snapshot
 *   2: snap_src, snap_dest  - waiting for handover
 *   2: snap_src, NULL - handed over, waiting for old to be deleted
 *   1: NULL, snap_dest - source got destroyed without handover
 */
static int __find_snapshots_sharing_cow(struct dm_snapshot *snap,
					struct dm_snapshot **snap_src,
370 371
					struct dm_snapshot **snap_dest,
					struct dm_snapshot **snap_merge)
372 373 374 375 376 377 378 379 380 381 382
{
	struct dm_snapshot *s;
	struct origin *o;
	int count = 0;
	int active;

	o = __lookup_origin(snap->origin->bdev);
	if (!o)
		goto out;

	list_for_each_entry(s, &o->snapshots, list) {
383 384
		if (dm_target_is_snapshot_merge(s->ti) && snap_merge)
			*snap_merge = s;
385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411
		if (!bdev_equal(s->cow->bdev, snap->cow->bdev))
			continue;

		down_read(&s->lock);
		active = s->active;
		up_read(&s->lock);

		if (active) {
			if (snap_src)
				*snap_src = s;
		} else if (snap_dest)
			*snap_dest = s;

		count++;
	}

out:
	return count;
}

/*
 * On success, returns 1 if this snapshot is a handover destination,
 * otherwise returns 0.
 */
static int __validate_exception_handover(struct dm_snapshot *snap)
{
	struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
412
	struct dm_snapshot *snap_merge = NULL;
413 414

	/* Does snapshot need exceptions handed over to it? */
415 416
	if ((__find_snapshots_sharing_cow(snap, &snap_src, &snap_dest,
					  &snap_merge) == 2) ||
417 418 419 420 421 422 423 424 425 426 427 428 429
	    snap_dest) {
		snap->ti->error = "Snapshot cow pairing for exception "
				  "table handover failed";
		return -EINVAL;
	}

	/*
	 * If no snap_src was found, snap cannot become a handover
	 * destination.
	 */
	if (!snap_src)
		return 0;

430 431 432 433 434 435 436 437 438 439 440 441 442 443
	/*
	 * Non-snapshot-merge handover?
	 */
	if (!dm_target_is_snapshot_merge(snap->ti))
		return 1;

	/*
	 * Do not allow more than one merging snapshot.
	 */
	if (snap_merge) {
		snap->ti->error = "A snapshot is already merging.";
		return -EINVAL;
	}

444 445 446 447 448 449 450
	if (!snap_src->store->type->prepare_merge ||
	    !snap_src->store->type->commit_merge) {
		snap->ti->error = "Snapshot exception store does not "
				  "support snapshot-merge.";
		return -EINVAL;
	}

451 452 453 454 455 456 457 458 459 460 461 462 463 464
	return 1;
}

static void __insert_snapshot(struct origin *o, struct dm_snapshot *s)
{
	struct dm_snapshot *l;

	/* Sort the list according to chunk size, largest-first smallest-last */
	list_for_each_entry(l, &o->snapshots, list)
		if (l->store->chunk_size < s->store->chunk_size)
			break;
	list_add_tail(&s->list, &l->list);
}

Linus Torvalds's avatar
Linus Torvalds committed
465 466 467
/*
 * Make a note of the snapshot and its origin so we can look it
 * up when the origin has a write on it.
468 469 470 471
 *
 * Also validate snapshot exception store handovers.
 * On success, returns 1 if this registration is a handover destination,
 * otherwise returns 0.
Linus Torvalds's avatar
Linus Torvalds committed
472 473 474
 */
static int register_snapshot(struct dm_snapshot *snap)
{
475
	struct origin *o, *new_o = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
476
	struct block_device *bdev = snap->origin->bdev;
477
	int r = 0;
Linus Torvalds's avatar
Linus Torvalds committed
478

479 480 481 482
	new_o = kmalloc(sizeof(*new_o), GFP_KERNEL);
	if (!new_o)
		return -ENOMEM;

Linus Torvalds's avatar
Linus Torvalds committed
483 484
	down_write(&_origins_lock);

485 486 487 488 489 490 491
	r = __validate_exception_handover(snap);
	if (r < 0) {
		kfree(new_o);
		goto out;
	}

	o = __lookup_origin(bdev);
492 493 494
	if (o)
		kfree(new_o);
	else {
Linus Torvalds's avatar
Linus Torvalds committed
495
		/* New origin */
496
		o = new_o;
Linus Torvalds's avatar
Linus Torvalds committed
497 498 499 500 501 502 503 504

		/* Initialise the struct */
		INIT_LIST_HEAD(&o->snapshots);
		o->bdev = bdev;

		__insert_origin(o);
	}

505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523
	__insert_snapshot(o, snap);

out:
	up_write(&_origins_lock);

	return r;
}

/*
 * Move snapshot to correct place in list according to chunk size.
 */
static void reregister_snapshot(struct dm_snapshot *s)
{
	struct block_device *bdev = s->origin->bdev;

	down_write(&_origins_lock);

	list_del(&s->list);
	__insert_snapshot(__lookup_origin(bdev), s);
Linus Torvalds's avatar
Linus Torvalds committed
524 525 526 527 528 529 530 531 532 533 534 535

	up_write(&_origins_lock);
}

static void unregister_snapshot(struct dm_snapshot *s)
{
	struct origin *o;

	down_write(&_origins_lock);
	o = __lookup_origin(s->origin->bdev);

	list_del(&s->list);
536
	if (o && list_empty(&o->snapshots)) {
Linus Torvalds's avatar
Linus Torvalds committed
537 538 539 540 541 542 543 544 545
		list_del(&o->hash_list);
		kfree(o);
	}

	up_write(&_origins_lock);
}

/*
 * Implementation of the exception hash tables.
546 547
 * The lowest hash_shift bits of the chunk number are ignored, allowing
 * some consecutive chunks to be grouped together.
Linus Torvalds's avatar
Linus Torvalds committed
548
 */
549 550
static int dm_exception_table_init(struct dm_exception_table *et,
				   uint32_t size, unsigned hash_shift)
Linus Torvalds's avatar
Linus Torvalds committed
551 552 553
{
	unsigned int i;

554
	et->hash_shift = hash_shift;
Linus Torvalds's avatar
Linus Torvalds committed
555 556 557 558 559 560 561 562 563 564 565
	et->hash_mask = size - 1;
	et->table = dm_vcalloc(size, sizeof(struct list_head));
	if (!et->table)
		return -ENOMEM;

	for (i = 0; i < size; i++)
		INIT_LIST_HEAD(et->table + i);

	return 0;
}

566 567
static void dm_exception_table_exit(struct dm_exception_table *et,
				    struct kmem_cache *mem)
Linus Torvalds's avatar
Linus Torvalds committed
568 569
{
	struct list_head *slot;
570
	struct dm_exception *ex, *next;
Linus Torvalds's avatar
Linus Torvalds committed
571 572 573 574 575 576 577 578 579 580 581 582 583
	int i, size;

	size = et->hash_mask + 1;
	for (i = 0; i < size; i++) {
		slot = et->table + i;

		list_for_each_entry_safe (ex, next, slot, hash_list)
			kmem_cache_free(mem, ex);
	}

	vfree(et->table);
}

584
static uint32_t exception_hash(struct dm_exception_table *et, chunk_t chunk)
Linus Torvalds's avatar
Linus Torvalds committed
585
{
586
	return (chunk >> et->hash_shift) & et->hash_mask;
Linus Torvalds's avatar
Linus Torvalds committed
587 588
}

589
static void dm_remove_exception(struct dm_exception *e)
Linus Torvalds's avatar
Linus Torvalds committed
590 591 592 593 594 595 596 597
{
	list_del(&e->hash_list);
}

/*
 * Return the exception data for a sector, or NULL if not
 * remapped.
 */
598 599
static struct dm_exception *dm_lookup_exception(struct dm_exception_table *et,
						chunk_t chunk)
Linus Torvalds's avatar
Linus Torvalds committed
600 601
{
	struct list_head *slot;
602
	struct dm_exception *e;
Linus Torvalds's avatar
Linus Torvalds committed
603 604 605

	slot = &et->table[exception_hash(et, chunk)];
	list_for_each_entry (e, slot, hash_list)
606 607
		if (chunk >= e->old_chunk &&
		    chunk <= e->old_chunk + dm_consecutive_chunk_count(e))
Linus Torvalds's avatar
Linus Torvalds committed
608 609 610 611 612
			return e;

	return NULL;
}

613
static struct dm_exception *alloc_completed_exception(void)
Linus Torvalds's avatar
Linus Torvalds committed
614
{
615
	struct dm_exception *e;
Linus Torvalds's avatar
Linus Torvalds committed
616 617 618 619 620 621 622 623

	e = kmem_cache_alloc(exception_cache, GFP_NOIO);
	if (!e)
		e = kmem_cache_alloc(exception_cache, GFP_ATOMIC);

	return e;
}

624
static void free_completed_exception(struct dm_exception *e)
Linus Torvalds's avatar
Linus Torvalds committed
625 626 627 628
{
	kmem_cache_free(exception_cache, e);
}

629
static struct dm_snap_pending_exception *alloc_pending_exception(struct dm_snapshot *s)
Linus Torvalds's avatar
Linus Torvalds committed
630
{
631 632 633
	struct dm_snap_pending_exception *pe = mempool_alloc(s->pending_pool,
							     GFP_NOIO);

634
	atomic_inc(&s->pending_exceptions_count);
635 636 637
	pe->snap = s;

	return pe;
Linus Torvalds's avatar
Linus Torvalds committed
638 639
}

640
static void free_pending_exception(struct dm_snap_pending_exception *pe)
Linus Torvalds's avatar
Linus Torvalds committed
641
{
642 643 644 645 646
	struct dm_snapshot *s = pe->snap;

	mempool_free(pe, s->pending_pool);
	smp_mb__before_atomic_dec();
	atomic_dec(&s->pending_exceptions_count);
Linus Torvalds's avatar
Linus Torvalds committed
647 648
}

649 650
static void dm_insert_exception(struct dm_exception_table *eh,
				struct dm_exception *new_e)
651 652
{
	struct list_head *l;
653
	struct dm_exception *e = NULL;
654 655 656 657 658 659 660 661 662 663 664 665 666 667 668

	l = &eh->table[exception_hash(eh, new_e->old_chunk)];

	/* Add immediately if this table doesn't support consecutive chunks */
	if (!eh->hash_shift)
		goto out;

	/* List is ordered by old_chunk */
	list_for_each_entry_reverse(e, l, hash_list) {
		/* Insert after an existing chunk? */
		if (new_e->old_chunk == (e->old_chunk +
					 dm_consecutive_chunk_count(e) + 1) &&
		    new_e->new_chunk == (dm_chunk_number(e->new_chunk) +
					 dm_consecutive_chunk_count(e) + 1)) {
			dm_consecutive_chunk_count_inc(e);
669
			free_completed_exception(new_e);
670 671 672 673 674 675 676 677 678
			return;
		}

		/* Insert before an existing chunk? */
		if (new_e->old_chunk == (e->old_chunk - 1) &&
		    new_e->new_chunk == (dm_chunk_number(e->new_chunk) - 1)) {
			dm_consecutive_chunk_count_inc(e);
			e->old_chunk--;
			e->new_chunk--;
679
			free_completed_exception(new_e);
680 681 682 683 684 685 686 687 688 689 690
			return;
		}

		if (new_e->old_chunk > e->old_chunk)
			break;
	}

out:
	list_add(&new_e->hash_list, e ? &e->hash_list : l);
}

691 692 693 694 695
/*
 * Callback used by the exception stores to load exceptions when
 * initialising.
 */
static int dm_add_exception(void *context, chunk_t old, chunk_t new)
Linus Torvalds's avatar
Linus Torvalds committed
696
{
697
	struct dm_snapshot *s = context;
698
	struct dm_exception *e;
Linus Torvalds's avatar
Linus Torvalds committed
699

700
	e = alloc_completed_exception();
Linus Torvalds's avatar
Linus Torvalds committed
701 702 703 704
	if (!e)
		return -ENOMEM;

	e->old_chunk = old;
705 706

	/* Consecutive_count is implicitly initialised to zero */
Linus Torvalds's avatar
Linus Torvalds committed
707
	e->new_chunk = new;
708

709
	dm_insert_exception(&s->complete, e);
710

Linus Torvalds's avatar
Linus Torvalds committed
711 712 713
	return 0;
}

714 715 716 717
/*
 * Return a minimum chunk size of all snapshots that have the specified origin.
 * Return zero if the origin has no snapshots.
 */
718
static uint32_t __minimum_chunk_size(struct origin *o)
719 720 721 722 723 724 725 726 727
{
	struct dm_snapshot *snap;
	unsigned chunk_size = 0;

	if (o)
		list_for_each_entry(snap, &o->snapshots, list)
			chunk_size = min_not_zero(chunk_size,
						  snap->store->chunk_size);

728
	return (uint32_t) chunk_size;
729 730
}

Linus Torvalds's avatar
Linus Torvalds committed
731 732 733 734 735 736 737 738 739 740 741 742 743 744 745
/*
 * Hard coded magic.
 */
static int calc_max_buckets(void)
{
	/* use a fixed size of 2MB */
	unsigned long mem = 2 * 1024 * 1024;
	mem /= sizeof(struct list_head);

	return mem;
}

/*
 * Allocate room for a suitable hash table.
 */
746
static int init_hash_tables(struct dm_snapshot *s)
Linus Torvalds's avatar
Linus Torvalds committed
747
{
748
	sector_t hash_size, cow_dev_size, max_buckets;
Linus Torvalds's avatar
Linus Torvalds committed
749 750 751 752 753

	/*
	 * Calculate based on the size of the original volume or
	 * the COW volume...
	 */
754
	cow_dev_size = get_dev_size(s->cow->bdev);
Linus Torvalds's avatar
Linus Torvalds committed
755 756
	max_buckets = calc_max_buckets();

757
	hash_size = cow_dev_size >> s->store->chunk_shift;
Linus Torvalds's avatar
Linus Torvalds committed
758 759
	hash_size = min(hash_size, max_buckets);

760 761
	if (hash_size < 64)
		hash_size = 64;
762
	hash_size = rounddown_pow_of_two(hash_size);
763 764
	if (dm_exception_table_init(&s->complete, hash_size,
				    DM_CHUNK_CONSECUTIVE_BITS))
Linus Torvalds's avatar
Linus Torvalds committed
765 766 767 768 769 770 771 772 773 774
		return -ENOMEM;

	/*
	 * Allocate hash table for in-flight exceptions
	 * Make this smaller than the real hash table
	 */
	hash_size >>= 3;
	if (hash_size < 64)
		hash_size = 64;

775 776
	if (dm_exception_table_init(&s->pending, hash_size, 0)) {
		dm_exception_table_exit(&s->complete, exception_cache);
Linus Torvalds's avatar
Linus Torvalds committed
777 778 779 780 781 782
		return -ENOMEM;
	}

	return 0;
}

783 784 785 786 787 788 789
static void merge_shutdown(struct dm_snapshot *s)
{
	clear_bit_unlock(RUNNING_MERGE, &s->state_bits);
	smp_mb__after_clear_bit();
	wake_up_bit(&s->state_bits, RUNNING_MERGE);
}

790 791 792 793 794 795 796 797
static struct bio *__release_queued_bios_after_merge(struct dm_snapshot *s)
{
	s->first_merging_chunk = 0;
	s->num_merging_chunks = 0;

	return bio_list_get(&s->bios_queued_during_merge);
}

798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849
/*
 * Remove one chunk from the index of completed exceptions.
 */
static int __remove_single_exception_chunk(struct dm_snapshot *s,
					   chunk_t old_chunk)
{
	struct dm_exception *e;

	e = dm_lookup_exception(&s->complete, old_chunk);
	if (!e) {
		DMERR("Corruption detected: exception for block %llu is "
		      "on disk but not in memory",
		      (unsigned long long)old_chunk);
		return -EINVAL;
	}

	/*
	 * If this is the only chunk using this exception, remove exception.
	 */
	if (!dm_consecutive_chunk_count(e)) {
		dm_remove_exception(e);
		free_completed_exception(e);
		return 0;
	}

	/*
	 * The chunk may be either at the beginning or the end of a
	 * group of consecutive chunks - never in the middle.  We are
	 * removing chunks in the opposite order to that in which they
	 * were added, so this should always be true.
	 * Decrement the consecutive chunk counter and adjust the
	 * starting point if necessary.
	 */
	if (old_chunk == e->old_chunk) {
		e->old_chunk++;
		e->new_chunk++;
	} else if (old_chunk != e->old_chunk +
		   dm_consecutive_chunk_count(e)) {
		DMERR("Attempt to merge block %llu from the "
		      "middle of a chunk range [%llu - %llu]",
		      (unsigned long long)old_chunk,
		      (unsigned long long)e->old_chunk,
		      (unsigned long long)
		      e->old_chunk + dm_consecutive_chunk_count(e));
		return -EINVAL;
	}

	dm_consecutive_chunk_count_dec(e);

	return 0;
}

850 851 852
static void flush_bios(struct bio *bio);

static int remove_single_exception_chunk(struct dm_snapshot *s)
853
{
854 855 856
	struct bio *b = NULL;
	int r;
	chunk_t old_chunk = s->first_merging_chunk + s->num_merging_chunks - 1;
857 858

	down_write(&s->lock);
859 860 861 862 863 864 865 866 867 868 869 870 871 872

	/*
	 * Process chunks (and associated exceptions) in reverse order
	 * so that dm_consecutive_chunk_count_dec() accounting works.
	 */
	do {
		r = __remove_single_exception_chunk(s, old_chunk);
		if (r)
			goto out;
	} while (old_chunk-- > s->first_merging_chunk);

	b = __release_queued_bios_after_merge(s);

out:
873
	up_write(&s->lock);
874 875
	if (b)
		flush_bios(b);
876 877 878 879

	return r;
}

880 881 882
static int origin_write_extent(struct dm_snapshot *merging_snap,
			       sector_t sector, unsigned chunk_size);

883 884 885
static void merge_callback(int read_err, unsigned long write_err,
			   void *context);

886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905
static uint64_t read_pending_exceptions_done_count(void)
{
	uint64_t pending_exceptions_done;

	spin_lock(&_pending_exceptions_done_spinlock);
	pending_exceptions_done = _pending_exceptions_done_count;
	spin_unlock(&_pending_exceptions_done_spinlock);

	return pending_exceptions_done;
}

static void increment_pending_exceptions_done_count(void)
{
	spin_lock(&_pending_exceptions_done_spinlock);
	_pending_exceptions_done_count++;
	spin_unlock(&_pending_exceptions_done_spinlock);

	wake_up_all(&_pending_exceptions_done);
}

906 907
static void snapshot_merge_next_chunks(struct dm_snapshot *s)
{
908
	int i, linear_chunks;
909 910
	chunk_t old_chunk, new_chunk;
	struct dm_io_region src, dest;
911
	sector_t io_size;
912
	uint64_t previous_count;
913 914 915 916 917 918 919 920 921 922 923 924 925

	BUG_ON(!test_bit(RUNNING_MERGE, &s->state_bits));
	if (unlikely(test_bit(SHUTDOWN_MERGE, &s->state_bits)))
		goto shut;

	/*
	 * valid flag never changes during merge, so no lock required.
	 */
	if (!s->valid) {
		DMERR("Snapshot is invalid: can't merge");
		goto shut;
	}

926 927 928
	linear_chunks = s->store->type->prepare_merge(s->store, &old_chunk,
						      &new_chunk);
	if (linear_chunks <= 0) {
929
		if (linear_chunks < 0) {
930 931
			DMERR("Read error in exception store: "
			      "shutting down merge");
932 933 934 935
			down_write(&s->lock);
			s->merge_failed = 1;
			up_write(&s->lock);
		}
936 937 938
		goto shut;
	}

939 940 941 942 943 944 945 946 947
	/* Adjust old_chunk and new_chunk to reflect start of linear region */
	old_chunk = old_chunk + 1 - linear_chunks;
	new_chunk = new_chunk + 1 - linear_chunks;

	/*
	 * Use one (potentially large) I/O to copy all 'linear_chunks'
	 * from the exception store to the origin
	 */
	io_size = linear_chunks * s->store->chunk_size;
948 949 950

	dest.bdev = s->origin->bdev;
	dest.sector = chunk_to_sector(s->store, old_chunk);
951
	dest.count = min(io_size, get_dev_size(dest.bdev) - dest.sector);
952 953 954 955 956

	src.bdev = s->cow->bdev;
	src.sector = chunk_to_sector(s->store, new_chunk);
	src.count = dest.count;

957 958 959 960 961 962 963 964 965 966
	/*
	 * Reallocate any exceptions needed in other snapshots then
	 * wait for the pending exceptions to complete.
	 * Each time any pending exception (globally on the system)
	 * completes we are woken and repeat the process to find out
	 * if we can proceed.  While this may not seem a particularly
	 * efficient algorithm, it is not expected to have any
	 * significant impact on performance.
	 */
	previous_count = read_pending_exceptions_done_count();
967
	while (origin_write_extent(s, dest.sector, io_size)) {
968 969 970 971 972 973 974
		wait_event(_pending_exceptions_done,
			   (read_pending_exceptions_done_count() !=
			    previous_count));
		/* Retry after the wait, until all exceptions are done. */
		previous_count = read_pending_exceptions_done_count();
	}

975 976
	down_write(&s->lock);
	s->first_merging_chunk = old_chunk;
977
	s->num_merging_chunks = linear_chunks;
978 979
	up_write(&s->lock);

980 981 982
	/* Wait until writes to all 'linear_chunks' drain */
	for (i = 0; i < linear_chunks; i++)
		__check_for_conflicting_io(s, old_chunk + i);
983

984 985 986 987 988 989 990
	dm_kcopyd_copy(s->kcopyd_client, &src, 1, &dest, 0, merge_callback, s);
	return;

shut:
	merge_shutdown(s);
}

991 992
static void error_bios(struct bio *bio);

993 994 995
static void merge_callback(int read_err, unsigned long write_err, void *context)
{
	struct dm_snapshot *s = context;
996
	struct bio *b = NULL;
997 998 999 1000 1001 1002 1003 1004 1005

	if (read_err || write_err) {
		if (read_err)
			DMERR("Read error: shutting down merge.");
		else
			DMERR("Write error: shutting down merge.");
		goto shut;
	}

1006 1007
	if (s->store->type->commit_merge(s->store,
					 s->num_merging_chunks) < 0) {
1008 1009 1010 1011
		DMERR("Write error in exception store: shutting down merge");
		goto shut;
	}

1012 1013 1014
	if (remove_single_exception_chunk(s) < 0)
		goto shut;

1015 1016 1017 1018 1019
	snapshot_merge_next_chunks(s);

	return;

shut:
1020
	down_write(&s->lock);
1021
	s->merge_failed = 1;
1022 1023 1024 1025
	b = __release_queued_bios_after_merge(s);
	up_write(&s->lock);
	error_bios(b);

1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052
	merge_shutdown(s);
}

static void start_merge(struct dm_snapshot *s)
{
	if (!test_and_set_bit(RUNNING_MERGE, &s->state_bits))
		snapshot_merge_next_chunks(s);
}

static int wait_schedule(void *ptr)
{
	schedule();

	return 0;
}

/*
 * Stop the merging process and wait until it finishes.
 */
static void stop_merge(struct dm_snapshot *s)
{
	set_bit(SHUTDOWN_MERGE, &s->state_bits);
	wait_on_bit(&s->state_bits, RUNNING_MERGE, wait_schedule,
		    TASK_UNINTERRUPTIBLE);
	clear_bit(SHUTDOWN_MERGE, &s->state_bits);
}

Linus Torvalds's avatar
Linus Torvalds committed
1053 1054 1055 1056 1057 1058
/*
 * Construct a snapshot mapping: <origin_dev> <COW-dev> <p/n> <chunk-size>
 */
static int snapshot_ctr(struct dm_target *ti, unsigned int argc, char **argv)
{
	struct dm_snapshot *s;
1059
	int i;
Linus Torvalds's avatar
Linus Torvalds committed
1060
	int r = -EINVAL;
1061
	char *origin_path, *cow_path;
1062
	unsigned args_used, num_flush_bios = 1;
1063
	fmode_t origin_mode = FMODE_READ;
Linus Torvalds's avatar
Linus Torvalds committed
1064

1065
	if (argc != 4) {
1066
		ti->error = "requires exactly 4 arguments";
Linus Torvalds's avatar
Linus Torvalds committed
1067
		r = -EINVAL;
1068
		goto bad;
Linus Torvalds's avatar
Linus Torvalds committed
1069 1070
	}

1071
	if (dm_target_is_snapshot_merge(ti)) {
1072
		num_flush_bios = 2;
1073 1074 1075
		origin_mode = FMODE_WRITE;
	}

1076 1077
	s = kmalloc(sizeof(*s), GFP_KERNEL);
	if (!s) {
1078
		ti->error = "Cannot allocate private snapshot structure";
1079 1080 1081 1082
		r = -ENOMEM;
		goto bad;
	}

1083 1084 1085 1086 1087 1088 1089 1090 1091 1092
	origin_path = argv[0];
	argv++;
	argc--;

	r = dm_get_device(ti, origin_path, origin_mode, &s->origin);
	if (r) {
		ti->error = "Cannot get origin device";
		goto bad_origin;
	}

1093 1094 1095 1096
	cow_path = argv[0];
	argv++;
	argc--;

1097
	r = dm_get_device(ti, cow_path, dm_table_get_mode(ti->table), &s->cow);
1098 1099 1100 1101 1102 1103
	if (r) {
		ti->error = "Cannot get COW device";
		goto bad_cow;
	}

	r = dm_exception_store_create(ti, argc, argv, s, &args_used, &s->store);
1104 1105
	if (r) {
		ti->error = "Couldn't create exception store";
Linus Torvalds's avatar
Linus Torvalds committed
1106
		r = -EINVAL;
1107
		goto bad_store;
Linus Torvalds's avatar
Linus Torvalds committed
1108 1109
	}

1110 1111 1112
	argv += args_used;
	argc -= args_used;

1113
	s->ti = ti;
Linus Torvalds's avatar
Linus Torvalds committed
1114
	s->valid = 1;
1115
	s->active = 0;
1116
	atomic_set(&s->pending_exceptions_count, 0);
1117 1118 1119
	s->exception_start_sequence = 0;
	s->exception_complete_sequence = 0;
	INIT_LIST_HEAD(&s->out_of_order_list);
Linus Torvalds's avatar
Linus Torvalds committed
1120
	init_rwsem(&s->lock);
1121
	INIT_LIST_HEAD(&s->list);
1122
	spin_lock_init(&s->pe_lock);
1123
	s->state_bits = 0;
1124
	s->merge_failed = 0;
1125 1126 1127
	s->first_merging_chunk = 0;
	s->num_merging_chunks = 0;
	bio_list_init(&s->bios_queued_during_merge);
Linus Torvalds's avatar
Linus Torvalds committed
1128 1129

	/* Allocate hash table for COW data */
1130
	if (init_hash_tables(s)) {
Linus Torvalds's avatar
Linus Torvalds committed
1131 1132
		ti->error = "Unable to allocate hash table space";
		r = -ENOMEM;
1133
		goto bad_hash_tables;
Linus Torvalds's avatar
Linus Torvalds committed
1134 1135
	}

1136
	s->kcopyd_client = dm_kcopyd_client_create(&dm_kcopyd_throttle);
1137 1138
	if (IS_ERR(s->kcopyd_client)) {
		r = PTR_ERR(s->kcopyd_client);
Linus Torvalds's avatar
Linus Torvalds committed
1139
		ti->error = "Could not create kcopyd client";
1140
		goto bad_kcopyd;
Linus Torvalds's avatar
Linus Torvalds committed
1141 1142
	}

1143 1144 1145
	s->pending_pool = mempool_create_slab_pool(MIN_IOS, pending_cache);
	if (!s->pending_pool) {
		ti->error = "Could not allocate mempool for pending exceptions";
1146
		r = -ENOMEM;
1147
		goto bad_pending_pool;
1148 1149
	}

1150 1151 1152 1153 1154
	for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
		INIT_HLIST_HEAD(&s->tracked_chunk_hash[i]);

	spin_lock_init(&s->tracked_chunk_lock);

1155
	ti->private = s;
1156
	ti->num_flush_bios = num_flush_bios;
1157
	ti->per_bio_data_size = sizeof(struct dm_snap_tracked_chunk);
1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180

	/* Add snapshot to the list of snapshots for this origin */
	/* Exceptions aren't triggered till snapshot_resume() is called */
	r = register_snapshot(s);
	if (r == -ENOMEM) {
		ti->error = "Snapshot origin struct allocation failed";
		goto bad_load_and_register;
	} else if (r < 0) {
		/* invalid handover, register_snapshot has set ti->error */
		goto bad_load_and_register;
	}

	/*
	 * Metadata must only be loaded into one table at once, so skip this
	 * if metadata will be handed over during resume.
	 * Chunk size will be set during the handover - set it to zero to
	 * ensure it's ignored.
	 */
	if (r > 0) {
		s->store->chunk_size = 0;
		return 0;
	}

1181 1182
	r = s->store->type->read_metadata(s->store, dm_add_exception,
					  (void *)s);
1183
	if (r < 0) {
1184
		ti->error = "Failed to read snapshot metadata";
1185
		goto bad_read_metadata;
1186 1187 1188
	} else if (r > 0) {
		s->valid = 0;
		DMWARN("Snapshot is marked invalid.");
1189
	}
1190

1191 1192
	if (!s->store->chunk_size) {
		ti->error = "Chunk size not set";
1193
		goto bad_read_metadata;
Linus Torvalds's avatar
Linus Torvalds committed
1194
	}
1195 1196 1197 1198

	r = dm_set_target_max_io_len(ti, s->store->chunk_size);
	if (r)
		goto bad_read_metadata;
Linus Torvalds's avatar
Linus Torvalds committed
1199 1200 1201

	return 0;

1202 1203 1204
bad_read_metadata:
	unregister_snapshot(s);

1205
bad_load_and_register:
1206 1207
	mempool_destroy(s->pending_pool);

1208
bad_pending_pool:
1209
	dm_kcopyd_client_destroy(s->kcopyd_client);
Linus Torvalds's avatar
Linus Torvalds committed
1210

1211
bad_kcopyd:
1212 1213
	dm_exception_table_exit(&s->pending, pending_cache);
	dm_exception_table_exit(&s->complete, exception_cache);
Linus Torvalds's avatar
Linus Torvalds committed
1214

1215
bad_hash_tables:
1216
	dm_exception_store_destroy(s->store);
Linus Torvalds's avatar
Linus Torvalds committed
1217

1218 1219
bad_store:
	dm_put_device(ti, s->cow);
1220

1221
bad_cow:
1222 1223 1224
	dm_put_device(ti, s->origin);

bad_origin:
1225 1226 1227
	kfree(s);

bad:
Linus Torvalds's avatar
Linus Torvalds committed
1228 1229 1230
	return r;
}

1231 1232
static void __free_exceptions(struct dm_snapshot *s)
{
1233
	dm_kcopyd_client_destroy(s->kcopyd_client);
1234 1235
	s->kcopyd_client = NULL;

1236 1237
	dm_exception_table_exit(&s->pending, pending_cache);
	dm_exception_table_exit(&s->complete, exception_cache);
1238 1239
}

1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261
static void __handover_exceptions(struct dm_snapshot *snap_src,
				  struct dm_snapshot *snap_dest)
{
	union {
		struct dm_exception_table table_swap;
		struct dm_exception_store *store_swap;
	} u;

	/*
	 * Swap all snapshot context information between the two instances.
	 */
	u.table_swap = snap_dest->complete;
	snap_dest->complete = snap_src->complete;
	snap_src->complete = u.table_swap;

	u.store_swap = snap_dest->store;
	snap_dest->store = snap_src->store;
	snap_src->store = u.store_swap;

	snap_dest->store->snap = snap_dest;
	snap_src->store->snap = snap_src;

1262
	snap_dest->ti->max_io_len = snap_dest->store->chunk_size;
1263 1264 1265 1266 1267 1268 1269 1270
	snap_dest->valid = snap_src->valid;

	/*
	 * Set source invalid to ensure it receives no further I/O.
	 */
	snap_src->valid = 0;
}

Linus Torvalds's avatar
Linus Torvalds committed
1271 1272
static void snapshot_dtr(struct dm_target *ti)
{
1273 1274 1275
#ifdef CONFIG_DM_DEBUG
	int i;
#endif
1276
	struct dm_snapshot *s = ti->private;
1277
	struct dm_snapshot *snap_src = NULL, *snap_dest = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
1278

1279 1280
	down_read(&_origins_lock);
	/* Check whether exception handover must be cancelled */
1281
	(void) __find_snapshots_sharing_cow(s, &snap_src, &snap_dest, NULL);
1282 1283 1284 1285 1286 1287 1288 1289
	if (snap_src && snap_dest && (s == snap_src)) {
		down_write(&snap_dest->lock);
		snap_dest->valid = 0;
		up_write(&snap_dest->lock);
		DMERR("Cancelling snapshot handover.");
	}
	up_read(&_origins_lock);

1290 1291 1292
	if (dm_target_is_snapshot_merge(ti))
		stop_merge(s);

1293 1294
	/* Prevent further origin writes from using this snapshot. */
	/* After this returns there can be no new kcopyd jobs. */
Linus Torvalds's avatar
Linus Torvalds committed
1295 1296
	unregister_snapshot(s);

1297
	while (atomic_read(&s->pending_exceptions_count))
1298
		msleep(1);
1299 1300 1301 1302 1303 1304
	/*
	 * Ensure instructions in mempool_destroy aren't reordered
	 * before atomic_read.
	 */
	smp_mb();

1305 1306 1307 1308 1309
#ifdef CONFIG_DM_DEBUG
	for (i = 0; i < DM_TRACKED_CHUNK_HASH_SIZE; i++)
		BUG_ON(!hlist_empty(&s->tracked_chunk_hash[i]));
#endif

1310
	__free_exceptions(s);
Linus Torvalds's avatar
Linus Torvalds committed
1311

1312 1313
	mempool_destroy(s->pending_pool);

1314
	dm_exception_store_destroy(s->store);
1315

1316 1317
	dm_put_device(ti, s->cow);

1318 1319
	dm_put_device(ti, s->origin);

Linus Torvalds's avatar
Linus Torvalds committed
1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337
	kfree(s);
}

/*
 * Flush a list of buffers.
 */
static void flush_bios(struct bio *bio)
{
	struct bio *n;

	while (bio) {
		n = bio->bi_next;
		bio->bi_next = NULL;
		generic_make_request(bio);
		bio = n;
	}
}

1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357
static int do_origin(struct dm_dev *origin, struct bio *bio);

/*
 * Flush a list of buffers.
 */
static void retry_origin_bios(struct dm_snapshot *s, struct bio *bio)
{
	struct bio *n;
	int r;

	while (bio) {
		n = bio->bi_next;
		bio->bi_next = NULL;
		r = do_origin(s->origin, bio);
		if (r == DM_MAPIO_REMAPPED)
			generic_make_request(bio);
		bio = n;
	}
}

Linus Torvalds's avatar
Linus Torvalds committed
1358 1359 1360 1361 1362 1363 1364 1365 1366 1367
/*
 * Error a list of buffers.
 */
static void error_bios(struct bio *bio)
{
	struct bio *n;

	while (bio) {
		n = bio->bi_next;
		bio->bi_next = NULL;
1368
		bio_io_error(bio);
Linus Torvalds's avatar
Linus Torvalds committed
1369 1370 1371 1372
		bio = n;
	}
}

1373
static void __invalidate_snapshot(struct dm_snapshot *s, int err)
1374 1375 1376 1377 1378 1379 1380 1381 1382
{
	if (!s->valid)
		return;

	if (err == -EIO)
		DMERR("Invalidating snapshot: Error reading/writing.");
	else if (err == -ENOMEM)
		DMERR("Invalidating snapshot: Unable to allocate exception.");

1383 1384
	if (s->store->type->drop_snapshot)
		s->store->type->drop_snapshot(s->store);
1385 1386 1387

	s->valid = 0;

1388
	dm_table_event(s->ti->table);
1389 1390
}

1391
static void pending_complete(struct dm_snap_pending_exception *pe, int success)
Linus Torvalds's avatar
Linus Torvalds committed
1392
{
1393
	struct dm_exception *e;
Linus Torvalds's avatar
Linus Torvalds committed
1394
	struct dm_snapshot *s = pe->snap;
1395 1396
	struct bio *origin_bios = NULL;
	struct bio *snapshot_bios = NULL;
1397
	struct bio *full_bio = NULL;
1398
	int error = 0;
Linus Torvalds's avatar
Linus Torvalds committed
1399

1400 1401
	if (!success) {
		/* Read/write error - snapshot is unusable */
Linus Torvalds's avatar
Linus Torvalds committed
1402
		down_write(&s->lock);
1403
		__invalidate_snapshot(s, -EIO);
1404
		error = 1;
1405 1406 1407
		goto out;
	}

1408
	e = alloc_completed_exception();
1409
	if (!e) {
Linus Torvalds's avatar
Linus Torvalds committed
1410
		down_write(&s->lock);
1411
		__invalidate_snapshot(s, -ENOMEM);
1412
		error = 1;
1413 1414 1415
		goto out;
	}
	*e = pe->e;
Linus Torvalds's avatar
Linus Torvalds committed
1416

1417 1418
	down_write(&s->lock);
	if (!s->valid) {
1419
		free_completed_exception(e);
1420
		error = 1;
1421
		goto out;
Linus Torvalds's avatar
Linus Torvalds committed
1422 1423
	}

1424 1425
	/* Check for conflicting reads */
	__check_for_conflicting_io(s, pe->e.old_chunk);
1426

1427 1428 1429 1430
	/*
	 * Add a proper exception, and remove the
	 * in-flight exception from the list.
	 */
1431
	dm_insert_exception(&s->complete, e);
1432

1433
out:
1434
	dm_remove_exception(&pe->e);
1435
	snapshot_bios = bio_list_get(&pe->snapshot_bios);
1436
	origin_bios = bio_list_get(&pe->origin_bios);
1437 1438 1439 1440 1441
	full_bio = pe->full_bio;
	if (full_bio) {
		full_bio->bi_end_io = pe->full_bio_end_io;
		full_bio->bi_private = pe->full_bio_private;
	}
1442
	free_pending_exception(pe);
Linus Torvalds's avatar
Linus Torvalds committed
1443

1444 1445
	increment_pending_exceptions_done_count();

1446 1447 1448
	up_write(&s->lock);

	/* Submit any pending write bios */
1449 1450 1451
	if (error) {
		if (full_bio)
			bio_io_error(full_bio);
1452
		error_bios(snapshot_bios);
1453 1454 1455
	} else {
		if (full_bio)
			bio_endio(full_bio, 0);
1456
		flush_bios(snapshot_bios);
1457
	}
1458

1459
	retry_origin_bios(s, origin_bios);
Linus Torvalds's avatar
Linus Torvalds committed
1460 1461 1462 1463
}

static void commit_callback(void *context, int success)
{
1464 1465
	struct dm_snap_pending_exception *pe = context;

Linus Torvalds's avatar
Linus Torvalds committed
1466 1467 1468
	pending_complete(pe, success);
}

1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481
static void complete_exception(struct dm_snap_pending_exception *pe)
{
	struct dm_snapshot *s = pe->snap;

	if (unlikely(pe->copy_error))
		pending_complete(pe, 0);

	else
		/* Update the metadata if we are persistent */
		s->store->type->commit_exception(s->store, &pe->e,
						 commit_callback, pe);
}

Linus Torvalds's avatar
Linus Torvalds committed
1482 1483 1484 1485
/*
 * Called when the copy I/O has finished.  kcopyd actually runs
 * this code so don't block.
 */
1486
static void copy_callback(int read_err, unsigned long write_err, void *context)
Linus Torvalds's avatar
Linus Torvalds committed
1487
{
1488
	struct dm_snap_pending_exception *pe = context;
Linus Torvalds's avatar
Linus Torvalds committed
1489 1490
	struct dm_snapshot *s = pe->snap;

1491
	pe->copy_error = read_err || write_err;
Linus Torvalds's avatar
Linus Torvalds committed
1492

1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516
	if (pe->exception_sequence == s->exception_complete_sequence) {
		s->exception_complete_sequence++;
		complete_exception(pe);

		while (!list_empty(&s->out_of_order_list)) {
			pe = list_entry(s->out_of_order_list.next,
					struct dm_snap_pending_exception, out_of_order_entry);
			if (pe->exception_sequence != s->exception_complete_sequence)
				break;
			s->exception_complete_sequence++;
			list_del(&pe->out_of_order_entry);
			complete_exception(pe);
		}
	} else {
		struct list_head *lh;
		struct dm_snap_pending_exception *pe2;

		list_for_each_prev(lh, &s->out_of_order_list) {
			pe2 = list_entry(lh, struct dm_snap_pending_exception, out_of_order_entry);
			if (pe2->exception_sequence < pe->exception_sequence)
				break;
		}
		list_add(&pe->out_of_order_entry, lh);
	}
Linus Torvalds's avatar
Linus Torvalds committed
1517 1518 1519 1520 1521
}

/*
 * Dispatches the copy operation to kcopyd.
 */
1522
static void start_copy(struct dm_snap_pending_exception *pe)
Linus Torvalds's avatar
Linus Torvalds committed
1523 1524
{
	struct dm_snapshot *s = pe->snap;
1525
	struct dm_io_region src, dest;
Linus Torvalds's avatar
Linus Torvalds committed
1526 1527 1528 1529 1530 1531
	struct block_device *bdev = s->origin->bdev;
	sector_t dev_size;

	dev_size = get_dev_size(bdev);

	src.bdev = bdev;
1532
	src.sector = chunk_to_sector(s->store, pe->e.old_chunk);
1533
	src.count = min((sector_t)s->store->chunk_size, dev_size - src.sector);
Linus Torvalds's avatar
Linus Torvalds committed
1534

1535
	dest.bdev = s->cow->bdev;
1536
	dest.sector = chunk_to_sector(s->store, pe->e.new_chunk);
Linus Torvalds's avatar
Linus Torvalds committed
1537 1538 1539
	dest.count = src.count;

	/* Hand over to kcopyd */
1540
	dm_kcopyd_copy(s->kcopyd_client, &src, 1, &dest, 0, copy_callback, pe);
Linus Torvalds's avatar
Linus Torvalds committed
1541 1542
}

1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568
static void full_bio_end_io(struct bio *bio, int error)
{
	void *callback_data = bio->bi_private;

	dm_kcopyd_do_callback(callback_data, 0, error ? 1 : 0);
}

static void start_full_bio(struct dm_snap_pending_exception *pe,
			   struct bio *bio)
{
	struct dm_snapshot *s = pe->snap;
	void *callback_data;

	pe->full_bio = bio;
	pe->full_bio_end_io = bio->bi_end_io;
	pe->full_bio_private = bio->bi_private;

	callback_data = dm_kcopyd_prepare_callback(s->kcopyd_client,
						   copy_callback, pe);

	bio->bi_end_io = full_bio_end_io;
	bio->bi_private = callback_data;

	generic_make_request(bio);
}

1569 1570 1571
static struct dm_snap_pending_exception *
__lookup_pending_exception(struct dm_snapshot *s, chunk_t chunk)
{
1572
	struct dm_exception *e = dm_lookup_exception(&s->pending, chunk);
1573 1574 1575 1576 1577 1578 1579

	if (!e)
		return NULL;

	return container_of(e, struct dm_snap_pending_exception, e);
}

Linus Torvalds's avatar
Linus Torvalds committed
1580 1581 1582 1583 1584 1585 1586 1587
/*
 * Looks to see if this snapshot already has a pending exception
 * for this chunk, otherwise it allocates a new one and inserts
 * it into the pending table.
 *
 * NOTE: a write lock must be held on snap->lock before calling
 * this.
 */
1588
static struct dm_snap_pending_exception *
1589 1590
__find_pending_exception(struct dm_snapshot *s,
			 struct dm_snap_pending_exception *pe, chunk_t chunk)
Linus Torvalds's avatar
Linus Torvalds committed
1591
{
1592
	struct dm_snap_pending_exception *pe2;
Linus Torvalds's avatar
Linus Torvalds committed
1593

1594 1595
	pe2 = __lookup_pending_exception(s, chunk);
	if (pe2) {
1596
		free_pending_exception(pe);
1597
		return pe2;
Linus Torvalds's avatar
Linus Torvalds committed
1598 1599
	}

1600 1601 1602 1603
	pe->e.old_chunk = chunk;
	bio_list_init(&pe->origin_bios);
	bio_list_init(&pe->snapshot_bios);
	pe->started = 0;
1604
	pe->full_bio = NULL;
1605

1606
	if (s->store->type->prepare_exception(s->store, &pe->e)) {
1607 1608 1609 1610
		free_pending_exception(pe);
		return NULL;
	}

1611 1612
	pe->exception_sequence = s->exception_start_sequence++;

1613
	dm_insert_exception(&s->pending, &pe->e);
1614