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