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