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