1// SPDX-License-Identifier: GPL-2.0-only 2/* 3 * Copyright (C) 2011 Red Hat, Inc. 4 * 5 * This file is released under the GPL. 6 */ 7 8#include "dm-space-map-common.h" 9#include "dm-transaction-manager.h" 10#include "dm-btree-internal.h" 11#include "dm-persistent-data-internal.h" 12 13#include <linux/bitops.h> 14#include <linux/device-mapper.h> 15 16#define DM_MSG_PREFIX "space map common" 17 18/*----------------------------------------------------------------*/ 19 20/* 21 * Index validator. 22 */ 23#define INDEX_CSUM_XOR 160478 24 25static void index_prepare_for_write(struct dm_block_validator *v, 26 struct dm_block *b, 27 size_t block_size) 28{ 29 struct disk_metadata_index *mi_le = dm_block_data(b); 30 31 mi_le->blocknr = cpu_to_le64(dm_block_location(b)); 32 mi_le->csum = cpu_to_le32(dm_bm_checksum(&mi_le->padding, 33 block_size - sizeof(__le32), 34 INDEX_CSUM_XOR)); 35} 36 37static int index_check(struct dm_block_validator *v, 38 struct dm_block *b, 39 size_t block_size) 40{ 41 struct disk_metadata_index *mi_le = dm_block_data(b); 42 __le32 csum_disk; 43 44 if (dm_block_location(b) != le64_to_cpu(mi_le->blocknr)) { 45 DMERR_LIMIT("%s failed: blocknr %llu != wanted %llu", __func__, 46 le64_to_cpu(mi_le->blocknr), dm_block_location(b)); 47 return -ENOTBLK; 48 } 49 50 csum_disk = cpu_to_le32(dm_bm_checksum(&mi_le->padding, 51 block_size - sizeof(__le32), 52 INDEX_CSUM_XOR)); 53 if (csum_disk != mi_le->csum) { 54 DMERR_LIMIT("i%s failed: csum %u != wanted %u", __func__, 55 le32_to_cpu(csum_disk), le32_to_cpu(mi_le->csum)); 56 return -EILSEQ; 57 } 58 59 return 0; 60} 61 62static struct dm_block_validator index_validator = { 63 .name = "index", 64 .prepare_for_write = index_prepare_for_write, 65 .check = index_check 66}; 67 68/*----------------------------------------------------------------*/ 69 70/* 71 * Bitmap validator 72 */ 73#define BITMAP_CSUM_XOR 240779 74 75static void dm_bitmap_prepare_for_write(struct dm_block_validator *v, 76 struct dm_block *b, 77 size_t block_size) 78{ 79 struct disk_bitmap_header *disk_header = dm_block_data(b); 80 81 disk_header->blocknr = cpu_to_le64(dm_block_location(b)); 82 disk_header->csum = cpu_to_le32(dm_bm_checksum(&disk_header->not_used, 83 block_size - sizeof(__le32), 84 BITMAP_CSUM_XOR)); 85} 86 87static int dm_bitmap_check(struct dm_block_validator *v, 88 struct dm_block *b, 89 size_t block_size) 90{ 91 struct disk_bitmap_header *disk_header = dm_block_data(b); 92 __le32 csum_disk; 93 94 if (dm_block_location(b) != le64_to_cpu(disk_header->blocknr)) { 95 DMERR_LIMIT("bitmap check failed: blocknr %llu != wanted %llu", 96 le64_to_cpu(disk_header->blocknr), dm_block_location(b)); 97 return -ENOTBLK; 98 } 99 100 csum_disk = cpu_to_le32(dm_bm_checksum(&disk_header->not_used, 101 block_size - sizeof(__le32), 102 BITMAP_CSUM_XOR)); 103 if (csum_disk != disk_header->csum) { 104 DMERR_LIMIT("bitmap check failed: csum %u != wanted %u", 105 le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum)); 106 return -EILSEQ; 107 } 108 109 return 0; 110} 111 112static struct dm_block_validator dm_sm_bitmap_validator = { 113 .name = "sm_bitmap", 114 .prepare_for_write = dm_bitmap_prepare_for_write, 115 .check = dm_bitmap_check, 116}; 117 118/*----------------------------------------------------------------*/ 119 120#define ENTRIES_PER_WORD 32 121#define ENTRIES_SHIFT 5 122 123static void *dm_bitmap_data(struct dm_block *b) 124{ 125 return dm_block_data(b) + sizeof(struct disk_bitmap_header); 126} 127 128#define WORD_MASK_HIGH 0xAAAAAAAAAAAAAAAAULL 129 130static unsigned int dm_bitmap_word_used(void *addr, unsigned int b) 131{ 132 __le64 *words_le = addr; 133 __le64 *w_le = words_le + (b >> ENTRIES_SHIFT); 134 135 uint64_t bits = le64_to_cpu(*w_le); 136 uint64_t mask = (bits + WORD_MASK_HIGH + 1) & WORD_MASK_HIGH; 137 138 return !(~bits & mask); 139} 140 141static unsigned int sm_lookup_bitmap(void *addr, unsigned int b) 142{ 143 __le64 *words_le = addr; 144 __le64 *w_le = words_le + (b >> ENTRIES_SHIFT); 145 unsigned int hi, lo; 146 147 b = (b & (ENTRIES_PER_WORD - 1)) << 1; 148 hi = !!test_bit_le(b, (void *) w_le); 149 lo = !!test_bit_le(b + 1, (void *) w_le); 150 return (hi << 1) | lo; 151} 152 153static void sm_set_bitmap(void *addr, unsigned int b, unsigned int val) 154{ 155 __le64 *words_le = addr; 156 __le64 *w_le = words_le + (b >> ENTRIES_SHIFT); 157 158 b = (b & (ENTRIES_PER_WORD - 1)) << 1; 159 160 if (val & 2) 161 __set_bit_le(b, (void *) w_le); 162 else 163 __clear_bit_le(b, (void *) w_le); 164 165 if (val & 1) 166 __set_bit_le(b + 1, (void *) w_le); 167 else 168 __clear_bit_le(b + 1, (void *) w_le); 169} 170 171static int sm_find_free(void *addr, unsigned int begin, unsigned int end, 172 unsigned int *result) 173{ 174 while (begin < end) { 175 if (!(begin & (ENTRIES_PER_WORD - 1)) && 176 dm_bitmap_word_used(addr, begin)) { 177 begin += ENTRIES_PER_WORD; 178 continue; 179 } 180 181 if (!sm_lookup_bitmap(addr, begin)) { 182 *result = begin; 183 return 0; 184 } 185 186 begin++; 187 } 188 189 return -ENOSPC; 190} 191 192/*----------------------------------------------------------------*/ 193 194static int sm_ll_init(struct ll_disk *ll, struct dm_transaction_manager *tm) 195{ 196 memset(ll, 0, sizeof(struct ll_disk)); 197 198 ll->tm = tm; 199 200 ll->bitmap_info.tm = tm; 201 ll->bitmap_info.levels = 1; 202 203 /* 204 * Because the new bitmap blocks are created via a shadow 205 * operation, the old entry has already had its reference count 206 * decremented and we don't need the btree to do any bookkeeping. 207 */ 208 ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry); 209 ll->bitmap_info.value_type.inc = NULL; 210 ll->bitmap_info.value_type.dec = NULL; 211 ll->bitmap_info.value_type.equal = NULL; 212 213 ll->ref_count_info.tm = tm; 214 ll->ref_count_info.levels = 1; 215 ll->ref_count_info.value_type.size = sizeof(uint32_t); 216 ll->ref_count_info.value_type.inc = NULL; 217 ll->ref_count_info.value_type.dec = NULL; 218 ll->ref_count_info.value_type.equal = NULL; 219 220 ll->block_size = dm_bm_block_size(dm_tm_get_bm(tm)); 221 222 if (ll->block_size > (1 << 30)) { 223 DMERR("block size too big to hold bitmaps"); 224 return -EINVAL; 225 } 226 227 ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) * 228 ENTRIES_PER_BYTE; 229 ll->nr_blocks = 0; 230 ll->bitmap_root = 0; 231 ll->ref_count_root = 0; 232 ll->bitmap_index_changed = false; 233 234 return 0; 235} 236 237int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks) 238{ 239 int r; 240 dm_block_t i, nr_blocks, nr_indexes; 241 unsigned int old_blocks, blocks; 242 243 nr_blocks = ll->nr_blocks + extra_blocks; 244 old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block); 245 blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block); 246 247 nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block); 248 if (nr_indexes > ll->max_entries(ll)) { 249 DMERR("space map too large"); 250 return -EINVAL; 251 } 252 253 /* 254 * We need to set this before the dm_tm_new_block() call below. 255 */ 256 ll->nr_blocks = nr_blocks; 257 for (i = old_blocks; i < blocks; i++) { 258 struct dm_block *b; 259 struct disk_index_entry idx; 260 261 r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b); 262 if (r < 0) 263 return r; 264 265 idx.blocknr = cpu_to_le64(dm_block_location(b)); 266 267 dm_tm_unlock(ll->tm, b); 268 269 idx.nr_free = cpu_to_le32(ll->entries_per_block); 270 idx.none_free_before = 0; 271 272 r = ll->save_ie(ll, i, &idx); 273 if (r < 0) 274 return r; 275 } 276 277 return 0; 278} 279 280int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result) 281{ 282 int r; 283 dm_block_t index = b; 284 struct disk_index_entry ie_disk; 285 struct dm_block *blk; 286 287 if (b >= ll->nr_blocks) { 288 DMERR_LIMIT("metadata block out of bounds"); 289 return -EINVAL; 290 } 291 292 b = do_div(index, ll->entries_per_block); 293 r = ll->load_ie(ll, index, &ie_disk); 294 if (r < 0) 295 return r; 296 297 r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr), 298 &dm_sm_bitmap_validator, &blk); 299 if (r < 0) 300 return r; 301 302 *result = sm_lookup_bitmap(dm_bitmap_data(blk), b); 303 304 dm_tm_unlock(ll->tm, blk); 305 306 return 0; 307} 308 309static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b, 310 uint32_t *result) 311{ 312 __le32 le_rc; 313 int r; 314 315 r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc); 316 if (r < 0) 317 return r; 318 319 *result = le32_to_cpu(le_rc); 320 321 return r; 322} 323 324int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result) 325{ 326 int r = sm_ll_lookup_bitmap(ll, b, result); 327 328 if (r) 329 return r; 330 331 if (*result != 3) 332 return r; 333 334 return sm_ll_lookup_big_ref_count(ll, b, result); 335} 336 337int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin, 338 dm_block_t end, dm_block_t *result) 339{ 340 int r; 341 struct disk_index_entry ie_disk; 342 dm_block_t i, index_begin = begin; 343 dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block); 344 345 /* 346 * FIXME: Use shifts 347 */ 348 begin = do_div(index_begin, ll->entries_per_block); 349 end = do_div(end, ll->entries_per_block); 350 if (end == 0) 351 end = ll->entries_per_block; 352 353 for (i = index_begin; i < index_end; i++, begin = 0) { 354 struct dm_block *blk; 355 unsigned int position; 356 uint32_t bit_end; 357 358 r = ll->load_ie(ll, i, &ie_disk); 359 if (r < 0) 360 return r; 361 362 if (le32_to_cpu(ie_disk.nr_free) == 0) 363 continue; 364 365 r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr), 366 &dm_sm_bitmap_validator, &blk); 367 if (r < 0) 368 return r; 369 370 bit_end = (i == index_end - 1) ? end : ll->entries_per_block; 371 372 r = sm_find_free(dm_bitmap_data(blk), 373 max_t(unsigned int, begin, le32_to_cpu(ie_disk.none_free_before)), 374 bit_end, &position); 375 if (r == -ENOSPC) { 376 /* 377 * This might happen because we started searching 378 * part way through the bitmap. 379 */ 380 dm_tm_unlock(ll->tm, blk); 381 continue; 382 } 383 384 dm_tm_unlock(ll->tm, blk); 385 386 *result = i * ll->entries_per_block + (dm_block_t) position; 387 return 0; 388 } 389 390 return -ENOSPC; 391} 392 393int sm_ll_find_common_free_block(struct ll_disk *old_ll, struct ll_disk *new_ll, 394 dm_block_t begin, dm_block_t end, dm_block_t *b) 395{ 396 int r; 397 uint32_t count; 398 399 do { 400 r = sm_ll_find_free_block(new_ll, begin, new_ll->nr_blocks, b); 401 if (r) 402 break; 403 404 /* double check this block wasn't used in the old transaction */ 405 if (*b >= old_ll->nr_blocks) 406 count = 0; 407 else { 408 r = sm_ll_lookup(old_ll, *b, &count); 409 if (r) 410 break; 411 412 if (count) 413 begin = *b + 1; 414 } 415 } while (count); 416 417 return r; 418} 419 420/*----------------------------------------------------------------*/ 421 422int sm_ll_insert(struct ll_disk *ll, dm_block_t b, 423 uint32_t ref_count, int32_t *nr_allocations) 424{ 425 int r; 426 uint32_t bit, old; 427 struct dm_block *nb; 428 dm_block_t index = b; 429 struct disk_index_entry ie_disk; 430 void *bm_le; 431 int inc; 432 433 bit = do_div(index, ll->entries_per_block); 434 r = ll->load_ie(ll, index, &ie_disk); 435 if (r < 0) 436 return r; 437 438 r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr), 439 &dm_sm_bitmap_validator, &nb, &inc); 440 if (r < 0) { 441 DMERR("dm_tm_shadow_block() failed"); 442 return r; 443 } 444 ie_disk.blocknr = cpu_to_le64(dm_block_location(nb)); 445 bm_le = dm_bitmap_data(nb); 446 447 old = sm_lookup_bitmap(bm_le, bit); 448 if (old > 2) { 449 r = sm_ll_lookup_big_ref_count(ll, b, &old); 450 if (r < 0) { 451 dm_tm_unlock(ll->tm, nb); 452 return r; 453 } 454 } 455 456 if (r) { 457 dm_tm_unlock(ll->tm, nb); 458 return r; 459 } 460 461 if (ref_count <= 2) { 462 sm_set_bitmap(bm_le, bit, ref_count); 463 dm_tm_unlock(ll->tm, nb); 464 465 if (old > 2) { 466 r = dm_btree_remove(&ll->ref_count_info, 467 ll->ref_count_root, 468 &b, &ll->ref_count_root); 469 if (r) 470 return r; 471 } 472 473 } else { 474 __le32 le_rc = cpu_to_le32(ref_count); 475 476 sm_set_bitmap(bm_le, bit, 3); 477 dm_tm_unlock(ll->tm, nb); 478 479 __dm_bless_for_disk(&le_rc); 480 r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root, 481 &b, &le_rc, &ll->ref_count_root); 482 if (r < 0) { 483 DMERR("ref count insert failed"); 484 return r; 485 } 486 } 487 488 if (ref_count && !old) { 489 *nr_allocations = 1; 490 ll->nr_allocated++; 491 le32_add_cpu(&ie_disk.nr_free, -1); 492 if (le32_to_cpu(ie_disk.none_free_before) == bit) 493 ie_disk.none_free_before = cpu_to_le32(bit + 1); 494 495 } else if (old && !ref_count) { 496 *nr_allocations = -1; 497 ll->nr_allocated--; 498 le32_add_cpu(&ie_disk.nr_free, 1); 499 ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit)); 500 } else 501 *nr_allocations = 0; 502 503 return ll->save_ie(ll, index, &ie_disk); 504} 505 506/*----------------------------------------------------------------*/ 507 508/* 509 * Holds useful intermediate results for the range based inc and dec 510 * operations. 511 */ 512struct inc_context { 513 struct disk_index_entry ie_disk; 514 struct dm_block *bitmap_block; 515 void *bitmap; 516 517 struct dm_block *overflow_leaf; 518}; 519 520static inline void init_inc_context(struct inc_context *ic) 521{ 522 ic->bitmap_block = NULL; 523 ic->bitmap = NULL; 524 ic->overflow_leaf = NULL; 525} 526 527static inline void exit_inc_context(struct ll_disk *ll, struct inc_context *ic) 528{ 529 if (ic->bitmap_block) 530 dm_tm_unlock(ll->tm, ic->bitmap_block); 531 if (ic->overflow_leaf) 532 dm_tm_unlock(ll->tm, ic->overflow_leaf); 533} 534 535static inline void reset_inc_context(struct ll_disk *ll, struct inc_context *ic) 536{ 537 exit_inc_context(ll, ic); 538 init_inc_context(ic); 539} 540 541/* 542 * Confirms a btree node contains a particular key at an index. 543 */ 544static bool contains_key(struct btree_node *n, uint64_t key, int index) 545{ 546 return index >= 0 && 547 index < le32_to_cpu(n->header.nr_entries) && 548 le64_to_cpu(n->keys[index]) == key; 549} 550 551static int __sm_ll_inc_overflow(struct ll_disk *ll, dm_block_t b, struct inc_context *ic) 552{ 553 int r; 554 int index; 555 struct btree_node *n; 556 __le32 *v_ptr; 557 uint32_t rc; 558 559 /* 560 * bitmap_block needs to be unlocked because getting the 561 * overflow_leaf may need to allocate, and thus use the space map. 562 */ 563 reset_inc_context(ll, ic); 564 565 r = btree_get_overwrite_leaf(&ll->ref_count_info, ll->ref_count_root, 566 b, &index, &ll->ref_count_root, &ic->overflow_leaf); 567 if (r < 0) 568 return r; 569 570 n = dm_block_data(ic->overflow_leaf); 571 572 if (!contains_key(n, b, index)) { 573 DMERR("overflow btree is missing an entry"); 574 return -EINVAL; 575 } 576 577 v_ptr = value_ptr(n, index); 578 rc = le32_to_cpu(*v_ptr) + 1; 579 *v_ptr = cpu_to_le32(rc); 580 581 return 0; 582} 583 584static int sm_ll_inc_overflow(struct ll_disk *ll, dm_block_t b, struct inc_context *ic) 585{ 586 int index; 587 struct btree_node *n; 588 __le32 *v_ptr; 589 uint32_t rc; 590 591 /* 592 * Do we already have the correct overflow leaf? 593 */ 594 if (ic->overflow_leaf) { 595 n = dm_block_data(ic->overflow_leaf); 596 index = lower_bound(n, b); 597 if (contains_key(n, b, index)) { 598 v_ptr = value_ptr(n, index); 599 rc = le32_to_cpu(*v_ptr) + 1; 600 *v_ptr = cpu_to_le32(rc); 601 602 return 0; 603 } 604 } 605 606 return __sm_ll_inc_overflow(ll, b, ic); 607} 608 609static inline int shadow_bitmap(struct ll_disk *ll, struct inc_context *ic) 610{ 611 int r, inc; 612 613 r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ic->ie_disk.blocknr), 614 &dm_sm_bitmap_validator, &ic->bitmap_block, &inc); 615 if (r < 0) { 616 DMERR("dm_tm_shadow_block() failed"); 617 return r; 618 } 619 ic->ie_disk.blocknr = cpu_to_le64(dm_block_location(ic->bitmap_block)); 620 ic->bitmap = dm_bitmap_data(ic->bitmap_block); 621 return 0; 622} 623 624/* 625 * Once shadow_bitmap has been called, which always happens at the start of inc/dec, 626 * we can reopen the bitmap with a simple write lock, rather than re calling 627 * dm_tm_shadow_block(). 628 */ 629static inline int ensure_bitmap(struct ll_disk *ll, struct inc_context *ic) 630{ 631 if (!ic->bitmap_block) { 632 int r = dm_bm_write_lock(dm_tm_get_bm(ll->tm), le64_to_cpu(ic->ie_disk.blocknr), 633 &dm_sm_bitmap_validator, &ic->bitmap_block); 634 if (r) { 635 DMERR("unable to re-get write lock for bitmap"); 636 return r; 637 } 638 ic->bitmap = dm_bitmap_data(ic->bitmap_block); 639 } 640 641 return 0; 642} 643 644/* 645 * Loops round incrementing entries in a single bitmap. 646 */ 647static inline int sm_ll_inc_bitmap(struct ll_disk *ll, dm_block_t b, 648 uint32_t bit, uint32_t bit_end, 649 int32_t *nr_allocations, dm_block_t *new_b, 650 struct inc_context *ic) 651{ 652 int r; 653 __le32 le_rc; 654 uint32_t old; 655 656 for (; bit != bit_end; bit++, b++) { 657 /* 658 * We only need to drop the bitmap if we need to find a new btree 659 * leaf for the overflow. So if it was dropped last iteration, 660 * we now re-get it. 661 */ 662 r = ensure_bitmap(ll, ic); 663 if (r) 664 return r; 665 666 old = sm_lookup_bitmap(ic->bitmap, bit); 667 switch (old) { 668 case 0: 669 /* inc bitmap, adjust nr_allocated */ 670 sm_set_bitmap(ic->bitmap, bit, 1); 671 (*nr_allocations)++; 672 ll->nr_allocated++; 673 le32_add_cpu(&ic->ie_disk.nr_free, -1); 674 if (le32_to_cpu(ic->ie_disk.none_free_before) == bit) 675 ic->ie_disk.none_free_before = cpu_to_le32(bit + 1); 676 break; 677 678 case 1: 679 /* inc bitmap */ 680 sm_set_bitmap(ic->bitmap, bit, 2); 681 break; 682 683 case 2: 684 /* inc bitmap and insert into overflow */ 685 sm_set_bitmap(ic->bitmap, bit, 3); 686 reset_inc_context(ll, ic); 687 688 le_rc = cpu_to_le32(3); 689 __dm_bless_for_disk(&le_rc); 690 r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root, 691 &b, &le_rc, &ll->ref_count_root); 692 if (r < 0) { 693 DMERR("ref count insert failed"); 694 return r; 695 } 696 break; 697 698 default: 699 /* 700 * inc within the overflow tree only. 701 */ 702 r = sm_ll_inc_overflow(ll, b, ic); 703 if (r < 0) 704 return r; 705 } 706 } 707 708 *new_b = b; 709 return 0; 710} 711 712/* 713 * Finds a bitmap that contains entries in the block range, and increments 714 * them. 715 */ 716static int __sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e, 717 int32_t *nr_allocations, dm_block_t *new_b) 718{ 719 int r; 720 struct inc_context ic; 721 uint32_t bit, bit_end; 722 dm_block_t index = b; 723 724 init_inc_context(&ic); 725 726 bit = do_div(index, ll->entries_per_block); 727 r = ll->load_ie(ll, index, &ic.ie_disk); 728 if (r < 0) 729 return r; 730 731 r = shadow_bitmap(ll, &ic); 732 if (r) 733 return r; 734 735 bit_end = min(bit + (e - b), (dm_block_t) ll->entries_per_block); 736 r = sm_ll_inc_bitmap(ll, b, bit, bit_end, nr_allocations, new_b, &ic); 737 738 exit_inc_context(ll, &ic); 739 740 if (r) 741 return r; 742 743 return ll->save_ie(ll, index, &ic.ie_disk); 744} 745 746int sm_ll_inc(struct ll_disk *ll, dm_block_t b, dm_block_t e, 747 int32_t *nr_allocations) 748{ 749 *nr_allocations = 0; 750 while (b != e) { 751 int r = __sm_ll_inc(ll, b, e, nr_allocations, &b); 752 753 if (r) 754 return r; 755 } 756 757 return 0; 758} 759 760/*----------------------------------------------------------------*/ 761 762static int __sm_ll_del_overflow(struct ll_disk *ll, dm_block_t b, 763 struct inc_context *ic) 764{ 765 reset_inc_context(ll, ic); 766 return dm_btree_remove(&ll->ref_count_info, ll->ref_count_root, 767 &b, &ll->ref_count_root); 768} 769 770static int __sm_ll_dec_overflow(struct ll_disk *ll, dm_block_t b, 771 struct inc_context *ic, uint32_t *old_rc) 772{ 773 int r; 774 int index = -1; 775 struct btree_node *n; 776 __le32 *v_ptr; 777 uint32_t rc; 778 779 reset_inc_context(ll, ic); 780 r = btree_get_overwrite_leaf(&ll->ref_count_info, ll->ref_count_root, 781 b, &index, &ll->ref_count_root, &ic->overflow_leaf); 782 if (r < 0) 783 return r; 784 785 n = dm_block_data(ic->overflow_leaf); 786 787 if (!contains_key(n, b, index)) { 788 DMERR("overflow btree is missing an entry"); 789 return -EINVAL; 790 } 791 792 v_ptr = value_ptr(n, index); 793 rc = le32_to_cpu(*v_ptr); 794 *old_rc = rc; 795 796 if (rc == 3) 797 return __sm_ll_del_overflow(ll, b, ic); 798 799 rc--; 800 *v_ptr = cpu_to_le32(rc); 801 return 0; 802} 803 804static int sm_ll_dec_overflow(struct ll_disk *ll, dm_block_t b, 805 struct inc_context *ic, uint32_t *old_rc) 806{ 807 /* 808 * Do we already have the correct overflow leaf? 809 */ 810 if (ic->overflow_leaf) { 811 int index; 812 struct btree_node *n; 813 __le32 *v_ptr; 814 uint32_t rc; 815 816 n = dm_block_data(ic->overflow_leaf); 817 index = lower_bound(n, b); 818 if (contains_key(n, b, index)) { 819 v_ptr = value_ptr(n, index); 820 rc = le32_to_cpu(*v_ptr); 821 *old_rc = rc; 822 823 if (rc > 3) { 824 rc--; 825 *v_ptr = cpu_to_le32(rc); 826 return 0; 827 } else { 828 return __sm_ll_del_overflow(ll, b, ic); 829 } 830 831 } 832 } 833 834 return __sm_ll_dec_overflow(ll, b, ic, old_rc); 835} 836 837/* 838 * Loops round incrementing entries in a single bitmap. 839 */ 840static inline int sm_ll_dec_bitmap(struct ll_disk *ll, dm_block_t b, 841 uint32_t bit, uint32_t bit_end, 842 struct inc_context *ic, 843 int32_t *nr_allocations, dm_block_t *new_b) 844{ 845 int r; 846 uint32_t old; 847 848 for (; bit != bit_end; bit++, b++) { 849 /* 850 * We only need to drop the bitmap if we need to find a new btree 851 * leaf for the overflow. So if it was dropped last iteration, 852 * we now re-get it. 853 */ 854 r = ensure_bitmap(ll, ic); 855 if (r) 856 return r; 857 858 old = sm_lookup_bitmap(ic->bitmap, bit); 859 switch (old) { 860 case 0: 861 DMERR("unable to decrement block"); 862 return -EINVAL; 863 864 case 1: 865 /* dec bitmap */ 866 sm_set_bitmap(ic->bitmap, bit, 0); 867 (*nr_allocations)--; 868 ll->nr_allocated--; 869 le32_add_cpu(&ic->ie_disk.nr_free, 1); 870 ic->ie_disk.none_free_before = 871 cpu_to_le32(min(le32_to_cpu(ic->ie_disk.none_free_before), bit)); 872 break; 873 874 case 2: 875 /* dec bitmap and insert into overflow */ 876 sm_set_bitmap(ic->bitmap, bit, 1); 877 break; 878 879 case 3: 880 r = sm_ll_dec_overflow(ll, b, ic, &old); 881 if (r < 0) 882 return r; 883 884 if (old == 3) { 885 r = ensure_bitmap(ll, ic); 886 if (r) 887 return r; 888 889 sm_set_bitmap(ic->bitmap, bit, 2); 890 } 891 break; 892 } 893 } 894 895 *new_b = b; 896 return 0; 897} 898 899static int __sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e, 900 int32_t *nr_allocations, dm_block_t *new_b) 901{ 902 int r; 903 uint32_t bit, bit_end; 904 struct inc_context ic; 905 dm_block_t index = b; 906 907 init_inc_context(&ic); 908 909 bit = do_div(index, ll->entries_per_block); 910 r = ll->load_ie(ll, index, &ic.ie_disk); 911 if (r < 0) 912 return r; 913 914 r = shadow_bitmap(ll, &ic); 915 if (r) 916 return r; 917 918 bit_end = min(bit + (e - b), (dm_block_t) ll->entries_per_block); 919 r = sm_ll_dec_bitmap(ll, b, bit, bit_end, &ic, nr_allocations, new_b); 920 exit_inc_context(ll, &ic); 921 922 if (r) 923 return r; 924 925 return ll->save_ie(ll, index, &ic.ie_disk); 926} 927 928int sm_ll_dec(struct ll_disk *ll, dm_block_t b, dm_block_t e, 929 int32_t *nr_allocations) 930{ 931 *nr_allocations = 0; 932 while (b != e) { 933 int r = __sm_ll_dec(ll, b, e, nr_allocations, &b); 934 935 if (r) 936 return r; 937 } 938 939 return 0; 940} 941 942/*----------------------------------------------------------------*/ 943 944int sm_ll_commit(struct ll_disk *ll) 945{ 946 int r = 0; 947 948 if (ll->bitmap_index_changed) { 949 r = ll->commit(ll); 950 if (!r) 951 ll->bitmap_index_changed = false; 952 } 953 954 return r; 955} 956 957/*----------------------------------------------------------------*/ 958 959static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index, 960 struct disk_index_entry *ie) 961{ 962 memcpy(ie, ll->mi_le.index + index, sizeof(*ie)); 963 return 0; 964} 965 966static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index, 967 struct disk_index_entry *ie) 968{ 969 ll->bitmap_index_changed = true; 970 memcpy(ll->mi_le.index + index, ie, sizeof(*ie)); 971 return 0; 972} 973 974static int metadata_ll_init_index(struct ll_disk *ll) 975{ 976 int r; 977 struct dm_block *b; 978 979 r = dm_tm_new_block(ll->tm, &index_validator, &b); 980 if (r < 0) 981 return r; 982 983 ll->bitmap_root = dm_block_location(b); 984 985 dm_tm_unlock(ll->tm, b); 986 987 return 0; 988} 989 990static int metadata_ll_open(struct ll_disk *ll) 991{ 992 int r; 993 struct dm_block *block; 994 995 r = dm_tm_read_lock(ll->tm, ll->bitmap_root, 996 &index_validator, &block); 997 if (r) 998 return r; 999 1000 memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le)); 1001 dm_tm_unlock(ll->tm, block); 1002 1003 return 0; 1004} 1005 1006static dm_block_t metadata_ll_max_entries(struct ll_disk *ll) 1007{ 1008 return MAX_METADATA_BITMAPS; 1009} 1010 1011static int metadata_ll_commit(struct ll_disk *ll) 1012{ 1013 int r, inc; 1014 struct dm_block *b; 1015 1016 r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc); 1017 if (r) 1018 return r; 1019 1020 memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le)); 1021 ll->bitmap_root = dm_block_location(b); 1022 1023 dm_tm_unlock(ll->tm, b); 1024 1025 return 0; 1026} 1027 1028int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm) 1029{ 1030 int r; 1031 1032 r = sm_ll_init(ll, tm); 1033 if (r < 0) 1034 return r; 1035 1036 ll->load_ie = metadata_ll_load_ie; 1037 ll->save_ie = metadata_ll_save_ie; 1038 ll->init_index = metadata_ll_init_index; 1039 ll->open_index = metadata_ll_open; 1040 ll->max_entries = metadata_ll_max_entries; 1041 ll->commit = metadata_ll_commit; 1042 1043 ll->nr_blocks = 0; 1044 ll->nr_allocated = 0; 1045 1046 r = ll->init_index(ll); 1047 if (r < 0) 1048 return r; 1049 1050 r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root); 1051 if (r < 0) 1052 return r; 1053 1054 return 0; 1055} 1056 1057int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm, 1058 void *root_le, size_t len) 1059{ 1060 int r; 1061 struct disk_sm_root smr; 1062 1063 if (len < sizeof(struct disk_sm_root)) { 1064 DMERR("sm_metadata root too small"); 1065 return -ENOMEM; 1066 } 1067 1068 /* 1069 * We don't know the alignment of the root_le buffer, so need to 1070 * copy into a new structure. 1071 */ 1072 memcpy(&smr, root_le, sizeof(smr)); 1073 1074 r = sm_ll_init(ll, tm); 1075 if (r < 0) 1076 return r; 1077 1078 ll->load_ie = metadata_ll_load_ie; 1079 ll->save_ie = metadata_ll_save_ie; 1080 ll->init_index = metadata_ll_init_index; 1081 ll->open_index = metadata_ll_open; 1082 ll->max_entries = metadata_ll_max_entries; 1083 ll->commit = metadata_ll_commit; 1084 1085 ll->nr_blocks = le64_to_cpu(smr.nr_blocks); 1086 ll->nr_allocated = le64_to_cpu(smr.nr_allocated); 1087 ll->bitmap_root = le64_to_cpu(smr.bitmap_root); 1088 ll->ref_count_root = le64_to_cpu(smr.ref_count_root); 1089 1090 return ll->open_index(ll); 1091} 1092 1093/*----------------------------------------------------------------*/ 1094 1095static inline int ie_cache_writeback(struct ll_disk *ll, struct ie_cache *iec) 1096{ 1097 iec->dirty = false; 1098 __dm_bless_for_disk(iec->ie); 1099 return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root, 1100 &iec->index, &iec->ie, &ll->bitmap_root); 1101} 1102 1103static inline unsigned int hash_index(dm_block_t index) 1104{ 1105 return dm_hash_block(index, IE_CACHE_MASK); 1106} 1107 1108static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index, 1109 struct disk_index_entry *ie) 1110{ 1111 int r; 1112 unsigned int h = hash_index(index); 1113 struct ie_cache *iec = ll->ie_cache + h; 1114 1115 if (iec->valid) { 1116 if (iec->index == index) { 1117 memcpy(ie, &iec->ie, sizeof(*ie)); 1118 return 0; 1119 } 1120 1121 if (iec->dirty) { 1122 r = ie_cache_writeback(ll, iec); 1123 if (r) 1124 return r; 1125 } 1126 } 1127 1128 r = dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie); 1129 if (!r) { 1130 iec->valid = true; 1131 iec->dirty = false; 1132 iec->index = index; 1133 memcpy(&iec->ie, ie, sizeof(*ie)); 1134 } 1135 1136 return r; 1137} 1138 1139static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index, 1140 struct disk_index_entry *ie) 1141{ 1142 int r; 1143 unsigned int h = hash_index(index); 1144 struct ie_cache *iec = ll->ie_cache + h; 1145 1146 ll->bitmap_index_changed = true; 1147 if (iec->valid) { 1148 if (iec->index == index) { 1149 memcpy(&iec->ie, ie, sizeof(*ie)); 1150 iec->dirty = true; 1151 return 0; 1152 } 1153 1154 if (iec->dirty) { 1155 r = ie_cache_writeback(ll, iec); 1156 if (r) 1157 return r; 1158 } 1159 } 1160 1161 iec->valid = true; 1162 iec->dirty = true; 1163 iec->index = index; 1164 memcpy(&iec->ie, ie, sizeof(*ie)); 1165 return 0; 1166} 1167 1168static int disk_ll_init_index(struct ll_disk *ll) 1169{ 1170 unsigned int i; 1171 1172 for (i = 0; i < IE_CACHE_SIZE; i++) { 1173 struct ie_cache *iec = ll->ie_cache + i; 1174 1175 iec->valid = false; 1176 iec->dirty = false; 1177 } 1178 return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root); 1179} 1180 1181static int disk_ll_open(struct ll_disk *ll) 1182{ 1183 return 0; 1184} 1185 1186static dm_block_t disk_ll_max_entries(struct ll_disk *ll) 1187{ 1188 return -1ULL; 1189} 1190 1191static int disk_ll_commit(struct ll_disk *ll) 1192{ 1193 int r = 0; 1194 unsigned int i; 1195 1196 for (i = 0; i < IE_CACHE_SIZE; i++) { 1197 struct ie_cache *iec = ll->ie_cache + i; 1198 1199 if (iec->valid && iec->dirty) 1200 r = ie_cache_writeback(ll, iec); 1201 } 1202 1203 return r; 1204} 1205 1206int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm) 1207{ 1208 int r; 1209 1210 r = sm_ll_init(ll, tm); 1211 if (r < 0) 1212 return r; 1213 1214 ll->load_ie = disk_ll_load_ie; 1215 ll->save_ie = disk_ll_save_ie; 1216 ll->init_index = disk_ll_init_index; 1217 ll->open_index = disk_ll_open; 1218 ll->max_entries = disk_ll_max_entries; 1219 ll->commit = disk_ll_commit; 1220 1221 ll->nr_blocks = 0; 1222 ll->nr_allocated = 0; 1223 1224 r = ll->init_index(ll); 1225 if (r < 0) 1226 return r; 1227 1228 r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root); 1229 if (r < 0) 1230 return r; 1231 1232 return 0; 1233} 1234 1235int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm, 1236 void *root_le, size_t len) 1237{ 1238 int r; 1239 struct disk_sm_root *smr = root_le; 1240 1241 if (len < sizeof(struct disk_sm_root)) { 1242 DMERR("sm_metadata root too small"); 1243 return -ENOMEM; 1244 } 1245 1246 r = sm_ll_init(ll, tm); 1247 if (r < 0) 1248 return r; 1249 1250 ll->load_ie = disk_ll_load_ie; 1251 ll->save_ie = disk_ll_save_ie; 1252 ll->init_index = disk_ll_init_index; 1253 ll->open_index = disk_ll_open; 1254 ll->max_entries = disk_ll_max_entries; 1255 ll->commit = disk_ll_commit; 1256 1257 ll->nr_blocks = le64_to_cpu(smr->nr_blocks); 1258 ll->nr_allocated = le64_to_cpu(smr->nr_allocated); 1259 ll->bitmap_root = le64_to_cpu(smr->bitmap_root); 1260 ll->ref_count_root = le64_to_cpu(smr->ref_count_root); 1261 1262 return ll->open_index(ll); 1263} 1264 1265/*----------------------------------------------------------------*/ 1266