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 10 #include <linux/bitops.h> 11 #include <linux/device-mapper.h> 12 13 #define DM_MSG_PREFIX "space map common" 14 15 /*----------------------------------------------------------------*/ 16 17 /* 18 * Index validator. 19 */ 20 #define INDEX_CSUM_XOR 160478 21 22 static void index_prepare_for_write(struct dm_block_validator *v, 23 struct dm_block *b, 24 size_t block_size) 25 { 26 struct disk_metadata_index *mi_le = dm_block_data(b); 27 28 mi_le->blocknr = cpu_to_le64(dm_block_location(b)); 29 mi_le->csum = cpu_to_le32(dm_bm_checksum(&mi_le->padding, 30 block_size - sizeof(__le32), 31 INDEX_CSUM_XOR)); 32 } 33 34 static int index_check(struct dm_block_validator *v, 35 struct dm_block *b, 36 size_t block_size) 37 { 38 struct disk_metadata_index *mi_le = dm_block_data(b); 39 __le32 csum_disk; 40 41 if (dm_block_location(b) != le64_to_cpu(mi_le->blocknr)) { 42 DMERR_LIMIT("index_check failed: blocknr %llu != wanted %llu", 43 le64_to_cpu(mi_le->blocknr), dm_block_location(b)); 44 return -ENOTBLK; 45 } 46 47 csum_disk = cpu_to_le32(dm_bm_checksum(&mi_le->padding, 48 block_size - sizeof(__le32), 49 INDEX_CSUM_XOR)); 50 if (csum_disk != mi_le->csum) { 51 DMERR_LIMIT("index_check failed: csum %u != wanted %u", 52 le32_to_cpu(csum_disk), le32_to_cpu(mi_le->csum)); 53 return -EILSEQ; 54 } 55 56 return 0; 57 } 58 59 static struct dm_block_validator index_validator = { 60 .name = "index", 61 .prepare_for_write = index_prepare_for_write, 62 .check = index_check 63 }; 64 65 /*----------------------------------------------------------------*/ 66 67 /* 68 * Bitmap validator 69 */ 70 #define BITMAP_CSUM_XOR 240779 71 72 static void bitmap_prepare_for_write(struct dm_block_validator *v, 73 struct dm_block *b, 74 size_t block_size) 75 { 76 struct disk_bitmap_header *disk_header = dm_block_data(b); 77 78 disk_header->blocknr = cpu_to_le64(dm_block_location(b)); 79 disk_header->csum = cpu_to_le32(dm_bm_checksum(&disk_header->not_used, 80 block_size - sizeof(__le32), 81 BITMAP_CSUM_XOR)); 82 } 83 84 static int bitmap_check(struct dm_block_validator *v, 85 struct dm_block *b, 86 size_t block_size) 87 { 88 struct disk_bitmap_header *disk_header = dm_block_data(b); 89 __le32 csum_disk; 90 91 if (dm_block_location(b) != le64_to_cpu(disk_header->blocknr)) { 92 DMERR_LIMIT("bitmap check failed: blocknr %llu != wanted %llu", 93 le64_to_cpu(disk_header->blocknr), dm_block_location(b)); 94 return -ENOTBLK; 95 } 96 97 csum_disk = cpu_to_le32(dm_bm_checksum(&disk_header->not_used, 98 block_size - sizeof(__le32), 99 BITMAP_CSUM_XOR)); 100 if (csum_disk != disk_header->csum) { 101 DMERR_LIMIT("bitmap check failed: csum %u != wanted %u", 102 le32_to_cpu(csum_disk), le32_to_cpu(disk_header->csum)); 103 return -EILSEQ; 104 } 105 106 return 0; 107 } 108 109 static struct dm_block_validator dm_sm_bitmap_validator = { 110 .name = "sm_bitmap", 111 .prepare_for_write = bitmap_prepare_for_write, 112 .check = bitmap_check 113 }; 114 115 /*----------------------------------------------------------------*/ 116 117 #define ENTRIES_PER_WORD 32 118 #define ENTRIES_SHIFT 5 119 120 static void *dm_bitmap_data(struct dm_block *b) 121 { 122 return dm_block_data(b) + sizeof(struct disk_bitmap_header); 123 } 124 125 #define WORD_MASK_HIGH 0xAAAAAAAAAAAAAAAAULL 126 127 static unsigned bitmap_word_used(void *addr, unsigned b) 128 { 129 __le64 *words_le = addr; 130 __le64 *w_le = words_le + (b >> ENTRIES_SHIFT); 131 132 uint64_t bits = le64_to_cpu(*w_le); 133 uint64_t mask = (bits + WORD_MASK_HIGH + 1) & WORD_MASK_HIGH; 134 135 return !(~bits & mask); 136 } 137 138 static unsigned sm_lookup_bitmap(void *addr, unsigned b) 139 { 140 __le64 *words_le = addr; 141 __le64 *w_le = words_le + (b >> ENTRIES_SHIFT); 142 unsigned hi, lo; 143 144 b = (b & (ENTRIES_PER_WORD - 1)) << 1; 145 hi = !!test_bit_le(b, (void *) w_le); 146 lo = !!test_bit_le(b + 1, (void *) w_le); 147 return (hi << 1) | lo; 148 } 149 150 static void sm_set_bitmap(void *addr, unsigned b, unsigned val) 151 { 152 __le64 *words_le = addr; 153 __le64 *w_le = words_le + (b >> ENTRIES_SHIFT); 154 155 b = (b & (ENTRIES_PER_WORD - 1)) << 1; 156 157 if (val & 2) 158 __set_bit_le(b, (void *) w_le); 159 else 160 __clear_bit_le(b, (void *) w_le); 161 162 if (val & 1) 163 __set_bit_le(b + 1, (void *) w_le); 164 else 165 __clear_bit_le(b + 1, (void *) w_le); 166 } 167 168 static int sm_find_free(void *addr, unsigned begin, unsigned end, 169 unsigned *result) 170 { 171 while (begin < end) { 172 if (!(begin & (ENTRIES_PER_WORD - 1)) && 173 bitmap_word_used(addr, begin)) { 174 begin += ENTRIES_PER_WORD; 175 continue; 176 } 177 178 if (!sm_lookup_bitmap(addr, begin)) { 179 *result = begin; 180 return 0; 181 } 182 183 begin++; 184 } 185 186 return -ENOSPC; 187 } 188 189 /*----------------------------------------------------------------*/ 190 191 static int sm_ll_init(struct ll_disk *ll, struct dm_transaction_manager *tm) 192 { 193 ll->tm = tm; 194 195 ll->bitmap_info.tm = tm; 196 ll->bitmap_info.levels = 1; 197 198 /* 199 * Because the new bitmap blocks are created via a shadow 200 * operation, the old entry has already had its reference count 201 * decremented and we don't need the btree to do any bookkeeping. 202 */ 203 ll->bitmap_info.value_type.size = sizeof(struct disk_index_entry); 204 ll->bitmap_info.value_type.inc = NULL; 205 ll->bitmap_info.value_type.dec = NULL; 206 ll->bitmap_info.value_type.equal = NULL; 207 208 ll->ref_count_info.tm = tm; 209 ll->ref_count_info.levels = 1; 210 ll->ref_count_info.value_type.size = sizeof(uint32_t); 211 ll->ref_count_info.value_type.inc = NULL; 212 ll->ref_count_info.value_type.dec = NULL; 213 ll->ref_count_info.value_type.equal = NULL; 214 215 ll->block_size = dm_bm_block_size(dm_tm_get_bm(tm)); 216 217 if (ll->block_size > (1 << 30)) { 218 DMERR("block size too big to hold bitmaps"); 219 return -EINVAL; 220 } 221 222 ll->entries_per_block = (ll->block_size - sizeof(struct disk_bitmap_header)) * 223 ENTRIES_PER_BYTE; 224 ll->nr_blocks = 0; 225 ll->bitmap_root = 0; 226 ll->ref_count_root = 0; 227 ll->bitmap_index_changed = false; 228 229 return 0; 230 } 231 232 int sm_ll_extend(struct ll_disk *ll, dm_block_t extra_blocks) 233 { 234 int r; 235 dm_block_t i, nr_blocks, nr_indexes; 236 unsigned old_blocks, blocks; 237 238 nr_blocks = ll->nr_blocks + extra_blocks; 239 old_blocks = dm_sector_div_up(ll->nr_blocks, ll->entries_per_block); 240 blocks = dm_sector_div_up(nr_blocks, ll->entries_per_block); 241 242 nr_indexes = dm_sector_div_up(nr_blocks, ll->entries_per_block); 243 if (nr_indexes > ll->max_entries(ll)) { 244 DMERR("space map too large"); 245 return -EINVAL; 246 } 247 248 for (i = old_blocks; i < blocks; i++) { 249 struct dm_block *b; 250 struct disk_index_entry idx; 251 252 r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b); 253 if (r < 0) 254 return r; 255 idx.blocknr = cpu_to_le64(dm_block_location(b)); 256 257 r = dm_tm_unlock(ll->tm, b); 258 if (r < 0) 259 return r; 260 261 idx.nr_free = cpu_to_le32(ll->entries_per_block); 262 idx.none_free_before = 0; 263 264 r = ll->save_ie(ll, i, &idx); 265 if (r < 0) 266 return r; 267 } 268 269 ll->nr_blocks = nr_blocks; 270 return 0; 271 } 272 273 int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result) 274 { 275 int r; 276 dm_block_t index = b; 277 struct disk_index_entry ie_disk; 278 struct dm_block *blk; 279 280 b = do_div(index, ll->entries_per_block); 281 r = ll->load_ie(ll, index, &ie_disk); 282 if (r < 0) 283 return r; 284 285 r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr), 286 &dm_sm_bitmap_validator, &blk); 287 if (r < 0) 288 return r; 289 290 *result = sm_lookup_bitmap(dm_bitmap_data(blk), b); 291 292 return dm_tm_unlock(ll->tm, blk); 293 } 294 295 static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b, 296 uint32_t *result) 297 { 298 __le32 le_rc; 299 int r; 300 301 r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc); 302 if (r < 0) 303 return r; 304 305 *result = le32_to_cpu(le_rc); 306 307 return r; 308 } 309 310 int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result) 311 { 312 int r = sm_ll_lookup_bitmap(ll, b, result); 313 314 if (r) 315 return r; 316 317 if (*result != 3) 318 return r; 319 320 return sm_ll_lookup_big_ref_count(ll, b, result); 321 } 322 323 int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin, 324 dm_block_t end, dm_block_t *result) 325 { 326 int r; 327 struct disk_index_entry ie_disk; 328 dm_block_t i, index_begin = begin; 329 dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block); 330 331 /* 332 * FIXME: Use shifts 333 */ 334 begin = do_div(index_begin, ll->entries_per_block); 335 end = do_div(end, ll->entries_per_block); 336 337 for (i = index_begin; i < index_end; i++, begin = 0) { 338 struct dm_block *blk; 339 unsigned position; 340 uint32_t bit_end; 341 342 r = ll->load_ie(ll, i, &ie_disk); 343 if (r < 0) 344 return r; 345 346 if (le32_to_cpu(ie_disk.nr_free) == 0) 347 continue; 348 349 r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr), 350 &dm_sm_bitmap_validator, &blk); 351 if (r < 0) 352 return r; 353 354 bit_end = (i == index_end - 1) ? end : ll->entries_per_block; 355 356 r = sm_find_free(dm_bitmap_data(blk), 357 max_t(unsigned, begin, le32_to_cpu(ie_disk.none_free_before)), 358 bit_end, &position); 359 if (r == -ENOSPC) { 360 /* 361 * This might happen because we started searching 362 * part way through the bitmap. 363 */ 364 dm_tm_unlock(ll->tm, blk); 365 continue; 366 367 } else if (r < 0) { 368 dm_tm_unlock(ll->tm, blk); 369 return r; 370 } 371 372 r = dm_tm_unlock(ll->tm, blk); 373 if (r < 0) 374 return r; 375 376 *result = i * ll->entries_per_block + (dm_block_t) position; 377 return 0; 378 } 379 380 return -ENOSPC; 381 } 382 383 static int sm_ll_mutate(struct ll_disk *ll, dm_block_t b, 384 int (*mutator)(void *context, uint32_t old, uint32_t *new), 385 void *context, enum allocation_event *ev) 386 { 387 int r; 388 uint32_t bit, old, ref_count; 389 struct dm_block *nb; 390 dm_block_t index = b; 391 struct disk_index_entry ie_disk; 392 void *bm_le; 393 int inc; 394 395 bit = do_div(index, ll->entries_per_block); 396 r = ll->load_ie(ll, index, &ie_disk); 397 if (r < 0) 398 return r; 399 400 r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr), 401 &dm_sm_bitmap_validator, &nb, &inc); 402 if (r < 0) { 403 DMERR("dm_tm_shadow_block() failed"); 404 return r; 405 } 406 ie_disk.blocknr = cpu_to_le64(dm_block_location(nb)); 407 408 bm_le = dm_bitmap_data(nb); 409 old = sm_lookup_bitmap(bm_le, bit); 410 411 if (old > 2) { 412 r = sm_ll_lookup_big_ref_count(ll, b, &old); 413 if (r < 0) { 414 dm_tm_unlock(ll->tm, nb); 415 return r; 416 } 417 } 418 419 r = mutator(context, old, &ref_count); 420 if (r) { 421 dm_tm_unlock(ll->tm, nb); 422 return r; 423 } 424 425 if (ref_count <= 2) { 426 sm_set_bitmap(bm_le, bit, ref_count); 427 428 r = dm_tm_unlock(ll->tm, nb); 429 if (r < 0) 430 return r; 431 432 if (old > 2) { 433 r = dm_btree_remove(&ll->ref_count_info, 434 ll->ref_count_root, 435 &b, &ll->ref_count_root); 436 if (r) 437 return r; 438 } 439 440 } else { 441 __le32 le_rc = cpu_to_le32(ref_count); 442 443 sm_set_bitmap(bm_le, bit, 3); 444 r = dm_tm_unlock(ll->tm, nb); 445 if (r < 0) 446 return r; 447 448 __dm_bless_for_disk(&le_rc); 449 r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root, 450 &b, &le_rc, &ll->ref_count_root); 451 if (r < 0) { 452 DMERR("ref count insert failed"); 453 return r; 454 } 455 } 456 457 if (ref_count && !old) { 458 *ev = SM_ALLOC; 459 ll->nr_allocated++; 460 le32_add_cpu(&ie_disk.nr_free, -1); 461 if (le32_to_cpu(ie_disk.none_free_before) == bit) 462 ie_disk.none_free_before = cpu_to_le32(bit + 1); 463 464 } else if (old && !ref_count) { 465 *ev = SM_FREE; 466 ll->nr_allocated--; 467 le32_add_cpu(&ie_disk.nr_free, 1); 468 ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit)); 469 } 470 471 return ll->save_ie(ll, index, &ie_disk); 472 } 473 474 static int set_ref_count(void *context, uint32_t old, uint32_t *new) 475 { 476 *new = *((uint32_t *) context); 477 return 0; 478 } 479 480 int sm_ll_insert(struct ll_disk *ll, dm_block_t b, 481 uint32_t ref_count, enum allocation_event *ev) 482 { 483 return sm_ll_mutate(ll, b, set_ref_count, &ref_count, ev); 484 } 485 486 static int inc_ref_count(void *context, uint32_t old, uint32_t *new) 487 { 488 *new = old + 1; 489 return 0; 490 } 491 492 int sm_ll_inc(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev) 493 { 494 return sm_ll_mutate(ll, b, inc_ref_count, NULL, ev); 495 } 496 497 static int dec_ref_count(void *context, uint32_t old, uint32_t *new) 498 { 499 if (!old) { 500 DMERR_LIMIT("unable to decrement a reference count below 0"); 501 return -EINVAL; 502 } 503 504 *new = old - 1; 505 return 0; 506 } 507 508 int sm_ll_dec(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev) 509 { 510 return sm_ll_mutate(ll, b, dec_ref_count, NULL, ev); 511 } 512 513 int sm_ll_commit(struct ll_disk *ll) 514 { 515 int r = 0; 516 517 if (ll->bitmap_index_changed) { 518 r = ll->commit(ll); 519 if (!r) 520 ll->bitmap_index_changed = false; 521 } 522 523 return r; 524 } 525 526 /*----------------------------------------------------------------*/ 527 528 static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index, 529 struct disk_index_entry *ie) 530 { 531 memcpy(ie, ll->mi_le.index + index, sizeof(*ie)); 532 return 0; 533 } 534 535 static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index, 536 struct disk_index_entry *ie) 537 { 538 ll->bitmap_index_changed = true; 539 memcpy(ll->mi_le.index + index, ie, sizeof(*ie)); 540 return 0; 541 } 542 543 static int metadata_ll_init_index(struct ll_disk *ll) 544 { 545 int r; 546 struct dm_block *b; 547 548 r = dm_tm_new_block(ll->tm, &index_validator, &b); 549 if (r < 0) 550 return r; 551 552 memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le)); 553 ll->bitmap_root = dm_block_location(b); 554 555 return dm_tm_unlock(ll->tm, b); 556 } 557 558 static int metadata_ll_open(struct ll_disk *ll) 559 { 560 int r; 561 struct dm_block *block; 562 563 r = dm_tm_read_lock(ll->tm, ll->bitmap_root, 564 &index_validator, &block); 565 if (r) 566 return r; 567 568 memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le)); 569 return dm_tm_unlock(ll->tm, block); 570 } 571 572 static dm_block_t metadata_ll_max_entries(struct ll_disk *ll) 573 { 574 return MAX_METADATA_BITMAPS; 575 } 576 577 static int metadata_ll_commit(struct ll_disk *ll) 578 { 579 int r, inc; 580 struct dm_block *b; 581 582 r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc); 583 if (r) 584 return r; 585 586 memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le)); 587 ll->bitmap_root = dm_block_location(b); 588 589 return dm_tm_unlock(ll->tm, b); 590 } 591 592 int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm) 593 { 594 int r; 595 596 r = sm_ll_init(ll, tm); 597 if (r < 0) 598 return r; 599 600 ll->load_ie = metadata_ll_load_ie; 601 ll->save_ie = metadata_ll_save_ie; 602 ll->init_index = metadata_ll_init_index; 603 ll->open_index = metadata_ll_open; 604 ll->max_entries = metadata_ll_max_entries; 605 ll->commit = metadata_ll_commit; 606 607 ll->nr_blocks = 0; 608 ll->nr_allocated = 0; 609 610 r = ll->init_index(ll); 611 if (r < 0) 612 return r; 613 614 r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root); 615 if (r < 0) 616 return r; 617 618 return 0; 619 } 620 621 int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm, 622 void *root_le, size_t len) 623 { 624 int r; 625 struct disk_sm_root *smr = root_le; 626 627 if (len < sizeof(struct disk_sm_root)) { 628 DMERR("sm_metadata root too small"); 629 return -ENOMEM; 630 } 631 632 r = sm_ll_init(ll, tm); 633 if (r < 0) 634 return r; 635 636 ll->load_ie = metadata_ll_load_ie; 637 ll->save_ie = metadata_ll_save_ie; 638 ll->init_index = metadata_ll_init_index; 639 ll->open_index = metadata_ll_open; 640 ll->max_entries = metadata_ll_max_entries; 641 ll->commit = metadata_ll_commit; 642 643 ll->nr_blocks = le64_to_cpu(smr->nr_blocks); 644 ll->nr_allocated = le64_to_cpu(smr->nr_allocated); 645 ll->bitmap_root = le64_to_cpu(smr->bitmap_root); 646 ll->ref_count_root = le64_to_cpu(smr->ref_count_root); 647 648 return ll->open_index(ll); 649 } 650 651 /*----------------------------------------------------------------*/ 652 653 static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index, 654 struct disk_index_entry *ie) 655 { 656 return dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie); 657 } 658 659 static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index, 660 struct disk_index_entry *ie) 661 { 662 __dm_bless_for_disk(ie); 663 return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root, 664 &index, ie, &ll->bitmap_root); 665 } 666 667 static int disk_ll_init_index(struct ll_disk *ll) 668 { 669 return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root); 670 } 671 672 static int disk_ll_open(struct ll_disk *ll) 673 { 674 /* nothing to do */ 675 return 0; 676 } 677 678 static dm_block_t disk_ll_max_entries(struct ll_disk *ll) 679 { 680 return -1ULL; 681 } 682 683 static int disk_ll_commit(struct ll_disk *ll) 684 { 685 return 0; 686 } 687 688 int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm) 689 { 690 int r; 691 692 r = sm_ll_init(ll, tm); 693 if (r < 0) 694 return r; 695 696 ll->load_ie = disk_ll_load_ie; 697 ll->save_ie = disk_ll_save_ie; 698 ll->init_index = disk_ll_init_index; 699 ll->open_index = disk_ll_open; 700 ll->max_entries = disk_ll_max_entries; 701 ll->commit = disk_ll_commit; 702 703 ll->nr_blocks = 0; 704 ll->nr_allocated = 0; 705 706 r = ll->init_index(ll); 707 if (r < 0) 708 return r; 709 710 r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root); 711 if (r < 0) 712 return r; 713 714 return 0; 715 } 716 717 int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm, 718 void *root_le, size_t len) 719 { 720 int r; 721 struct disk_sm_root *smr = root_le; 722 723 if (len < sizeof(struct disk_sm_root)) { 724 DMERR("sm_metadata root too small"); 725 return -ENOMEM; 726 } 727 728 r = sm_ll_init(ll, tm); 729 if (r < 0) 730 return r; 731 732 ll->load_ie = disk_ll_load_ie; 733 ll->save_ie = disk_ll_save_ie; 734 ll->init_index = disk_ll_init_index; 735 ll->open_index = disk_ll_open; 736 ll->max_entries = disk_ll_max_entries; 737 ll->commit = disk_ll_commit; 738 739 ll->nr_blocks = le64_to_cpu(smr->nr_blocks); 740 ll->nr_allocated = le64_to_cpu(smr->nr_allocated); 741 ll->bitmap_root = le64_to_cpu(smr->bitmap_root); 742 ll->ref_count_root = le64_to_cpu(smr->ref_count_root); 743 744 return ll->open_index(ll); 745 } 746 747 /*----------------------------------------------------------------*/ 748