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