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 22static 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 34static 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 59static 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 72static 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 84static 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 109static 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 120static 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 127static 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 138static 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 150static 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 168static 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 191static 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 232int 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 /* 249 * We need to set this before the dm_tm_new_block() call below. 250 */ 251 ll->nr_blocks = nr_blocks; 252 for (i = old_blocks; i < blocks; i++) { 253 struct dm_block *b; 254 struct disk_index_entry idx; 255 256 r = dm_tm_new_block(ll->tm, &dm_sm_bitmap_validator, &b); 257 if (r < 0) 258 return r; 259 260 idx.blocknr = cpu_to_le64(dm_block_location(b)); 261 262 r = dm_tm_unlock(ll->tm, b); 263 if (r < 0) 264 return r; 265 266 idx.nr_free = cpu_to_le32(ll->entries_per_block); 267 idx.none_free_before = 0; 268 269 r = ll->save_ie(ll, i, &idx); 270 if (r < 0) 271 return r; 272 } 273 274 return 0; 275} 276 277int sm_ll_lookup_bitmap(struct ll_disk *ll, dm_block_t b, uint32_t *result) 278{ 279 int r; 280 dm_block_t index = b; 281 struct disk_index_entry ie_disk; 282 struct dm_block *blk; 283 284 b = do_div(index, ll->entries_per_block); 285 r = ll->load_ie(ll, index, &ie_disk); 286 if (r < 0) 287 return r; 288 289 r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr), 290 &dm_sm_bitmap_validator, &blk); 291 if (r < 0) 292 return r; 293 294 *result = sm_lookup_bitmap(dm_bitmap_data(blk), b); 295 296 return dm_tm_unlock(ll->tm, blk); 297} 298 299static int sm_ll_lookup_big_ref_count(struct ll_disk *ll, dm_block_t b, 300 uint32_t *result) 301{ 302 __le32 le_rc; 303 int r; 304 305 r = dm_btree_lookup(&ll->ref_count_info, ll->ref_count_root, &b, &le_rc); 306 if (r < 0) 307 return r; 308 309 *result = le32_to_cpu(le_rc); 310 311 return r; 312} 313 314int sm_ll_lookup(struct ll_disk *ll, dm_block_t b, uint32_t *result) 315{ 316 int r = sm_ll_lookup_bitmap(ll, b, result); 317 318 if (r) 319 return r; 320 321 if (*result != 3) 322 return r; 323 324 return sm_ll_lookup_big_ref_count(ll, b, result); 325} 326 327int sm_ll_find_free_block(struct ll_disk *ll, dm_block_t begin, 328 dm_block_t end, dm_block_t *result) 329{ 330 int r; 331 struct disk_index_entry ie_disk; 332 dm_block_t i, index_begin = begin; 333 dm_block_t index_end = dm_sector_div_up(end, ll->entries_per_block); 334 335 /* 336 * FIXME: Use shifts 337 */ 338 begin = do_div(index_begin, ll->entries_per_block); 339 end = do_div(end, ll->entries_per_block); 340 341 for (i = index_begin; i < index_end; i++, begin = 0) { 342 struct dm_block *blk; 343 unsigned position; 344 uint32_t bit_end; 345 346 r = ll->load_ie(ll, i, &ie_disk); 347 if (r < 0) 348 return r; 349 350 if (le32_to_cpu(ie_disk.nr_free) == 0) 351 continue; 352 353 r = dm_tm_read_lock(ll->tm, le64_to_cpu(ie_disk.blocknr), 354 &dm_sm_bitmap_validator, &blk); 355 if (r < 0) 356 return r; 357 358 bit_end = (i == index_end - 1) ? end : ll->entries_per_block; 359 360 r = sm_find_free(dm_bitmap_data(blk), 361 max_t(unsigned, begin, le32_to_cpu(ie_disk.none_free_before)), 362 bit_end, &position); 363 if (r == -ENOSPC) { 364 /* 365 * This might happen because we started searching 366 * part way through the bitmap. 367 */ 368 dm_tm_unlock(ll->tm, blk); 369 continue; 370 371 } else if (r < 0) { 372 dm_tm_unlock(ll->tm, blk); 373 return r; 374 } 375 376 r = dm_tm_unlock(ll->tm, blk); 377 if (r < 0) 378 return r; 379 380 *result = i * ll->entries_per_block + (dm_block_t) position; 381 return 0; 382 } 383 384 return -ENOSPC; 385} 386 387static int sm_ll_mutate(struct ll_disk *ll, dm_block_t b, 388 int (*mutator)(void *context, uint32_t old, uint32_t *new), 389 void *context, enum allocation_event *ev) 390{ 391 int r; 392 uint32_t bit, old, ref_count; 393 struct dm_block *nb; 394 dm_block_t index = b; 395 struct disk_index_entry ie_disk; 396 void *bm_le; 397 int inc; 398 399 bit = do_div(index, ll->entries_per_block); 400 r = ll->load_ie(ll, index, &ie_disk); 401 if (r < 0) 402 return r; 403 404 r = dm_tm_shadow_block(ll->tm, le64_to_cpu(ie_disk.blocknr), 405 &dm_sm_bitmap_validator, &nb, &inc); 406 if (r < 0) { 407 DMERR("dm_tm_shadow_block() failed"); 408 return r; 409 } 410 ie_disk.blocknr = cpu_to_le64(dm_block_location(nb)); 411 412 bm_le = dm_bitmap_data(nb); 413 old = sm_lookup_bitmap(bm_le, bit); 414 415 if (old > 2) { 416 r = sm_ll_lookup_big_ref_count(ll, b, &old); 417 if (r < 0) { 418 dm_tm_unlock(ll->tm, nb); 419 return r; 420 } 421 } 422 423 r = mutator(context, old, &ref_count); 424 if (r) { 425 dm_tm_unlock(ll->tm, nb); 426 return r; 427 } 428 429 if (ref_count <= 2) { 430 sm_set_bitmap(bm_le, bit, ref_count); 431 432 r = dm_tm_unlock(ll->tm, nb); 433 if (r < 0) 434 return r; 435 436 if (old > 2) { 437 r = dm_btree_remove(&ll->ref_count_info, 438 ll->ref_count_root, 439 &b, &ll->ref_count_root); 440 if (r) 441 return r; 442 } 443 444 } else { 445 __le32 le_rc = cpu_to_le32(ref_count); 446 447 sm_set_bitmap(bm_le, bit, 3); 448 r = dm_tm_unlock(ll->tm, nb); 449 if (r < 0) 450 return r; 451 452 __dm_bless_for_disk(&le_rc); 453 r = dm_btree_insert(&ll->ref_count_info, ll->ref_count_root, 454 &b, &le_rc, &ll->ref_count_root); 455 if (r < 0) { 456 DMERR("ref count insert failed"); 457 return r; 458 } 459 } 460 461 if (ref_count && !old) { 462 *ev = SM_ALLOC; 463 ll->nr_allocated++; 464 le32_add_cpu(&ie_disk.nr_free, -1); 465 if (le32_to_cpu(ie_disk.none_free_before) == bit) 466 ie_disk.none_free_before = cpu_to_le32(bit + 1); 467 468 } else if (old && !ref_count) { 469 *ev = SM_FREE; 470 ll->nr_allocated--; 471 le32_add_cpu(&ie_disk.nr_free, 1); 472 ie_disk.none_free_before = cpu_to_le32(min(le32_to_cpu(ie_disk.none_free_before), bit)); 473 } 474 475 return ll->save_ie(ll, index, &ie_disk); 476} 477 478static int set_ref_count(void *context, uint32_t old, uint32_t *new) 479{ 480 *new = *((uint32_t *) context); 481 return 0; 482} 483 484int sm_ll_insert(struct ll_disk *ll, dm_block_t b, 485 uint32_t ref_count, enum allocation_event *ev) 486{ 487 return sm_ll_mutate(ll, b, set_ref_count, &ref_count, ev); 488} 489 490static int inc_ref_count(void *context, uint32_t old, uint32_t *new) 491{ 492 *new = old + 1; 493 return 0; 494} 495 496int sm_ll_inc(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev) 497{ 498 return sm_ll_mutate(ll, b, inc_ref_count, NULL, ev); 499} 500 501static int dec_ref_count(void *context, uint32_t old, uint32_t *new) 502{ 503 if (!old) { 504 DMERR_LIMIT("unable to decrement a reference count below 0"); 505 return -EINVAL; 506 } 507 508 *new = old - 1; 509 return 0; 510} 511 512int sm_ll_dec(struct ll_disk *ll, dm_block_t b, enum allocation_event *ev) 513{ 514 return sm_ll_mutate(ll, b, dec_ref_count, NULL, ev); 515} 516 517int sm_ll_commit(struct ll_disk *ll) 518{ 519 int r = 0; 520 521 if (ll->bitmap_index_changed) { 522 r = ll->commit(ll); 523 if (!r) 524 ll->bitmap_index_changed = false; 525 } 526 527 return r; 528} 529 530/*----------------------------------------------------------------*/ 531 532static int metadata_ll_load_ie(struct ll_disk *ll, dm_block_t index, 533 struct disk_index_entry *ie) 534{ 535 memcpy(ie, ll->mi_le.index + index, sizeof(*ie)); 536 return 0; 537} 538 539static int metadata_ll_save_ie(struct ll_disk *ll, dm_block_t index, 540 struct disk_index_entry *ie) 541{ 542 ll->bitmap_index_changed = true; 543 memcpy(ll->mi_le.index + index, ie, sizeof(*ie)); 544 return 0; 545} 546 547static int metadata_ll_init_index(struct ll_disk *ll) 548{ 549 int r; 550 struct dm_block *b; 551 552 r = dm_tm_new_block(ll->tm, &index_validator, &b); 553 if (r < 0) 554 return r; 555 556 memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le)); 557 ll->bitmap_root = dm_block_location(b); 558 559 return dm_tm_unlock(ll->tm, b); 560} 561 562static int metadata_ll_open(struct ll_disk *ll) 563{ 564 int r; 565 struct dm_block *block; 566 567 r = dm_tm_read_lock(ll->tm, ll->bitmap_root, 568 &index_validator, &block); 569 if (r) 570 return r; 571 572 memcpy(&ll->mi_le, dm_block_data(block), sizeof(ll->mi_le)); 573 return dm_tm_unlock(ll->tm, block); 574} 575 576static dm_block_t metadata_ll_max_entries(struct ll_disk *ll) 577{ 578 return MAX_METADATA_BITMAPS; 579} 580 581static int metadata_ll_commit(struct ll_disk *ll) 582{ 583 int r, inc; 584 struct dm_block *b; 585 586 r = dm_tm_shadow_block(ll->tm, ll->bitmap_root, &index_validator, &b, &inc); 587 if (r) 588 return r; 589 590 memcpy(dm_block_data(b), &ll->mi_le, sizeof(ll->mi_le)); 591 ll->bitmap_root = dm_block_location(b); 592 593 return dm_tm_unlock(ll->tm, b); 594} 595 596int sm_ll_new_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm) 597{ 598 int r; 599 600 r = sm_ll_init(ll, tm); 601 if (r < 0) 602 return r; 603 604 ll->load_ie = metadata_ll_load_ie; 605 ll->save_ie = metadata_ll_save_ie; 606 ll->init_index = metadata_ll_init_index; 607 ll->open_index = metadata_ll_open; 608 ll->max_entries = metadata_ll_max_entries; 609 ll->commit = metadata_ll_commit; 610 611 ll->nr_blocks = 0; 612 ll->nr_allocated = 0; 613 614 r = ll->init_index(ll); 615 if (r < 0) 616 return r; 617 618 r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root); 619 if (r < 0) 620 return r; 621 622 return 0; 623} 624 625int sm_ll_open_metadata(struct ll_disk *ll, struct dm_transaction_manager *tm, 626 void *root_le, size_t len) 627{ 628 int r; 629 struct disk_sm_root *smr = root_le; 630 631 if (len < sizeof(struct disk_sm_root)) { 632 DMERR("sm_metadata root too small"); 633 return -ENOMEM; 634 } 635 636 r = sm_ll_init(ll, tm); 637 if (r < 0) 638 return r; 639 640 ll->load_ie = metadata_ll_load_ie; 641 ll->save_ie = metadata_ll_save_ie; 642 ll->init_index = metadata_ll_init_index; 643 ll->open_index = metadata_ll_open; 644 ll->max_entries = metadata_ll_max_entries; 645 ll->commit = metadata_ll_commit; 646 647 ll->nr_blocks = le64_to_cpu(smr->nr_blocks); 648 ll->nr_allocated = le64_to_cpu(smr->nr_allocated); 649 ll->bitmap_root = le64_to_cpu(smr->bitmap_root); 650 ll->ref_count_root = le64_to_cpu(smr->ref_count_root); 651 652 return ll->open_index(ll); 653} 654 655/*----------------------------------------------------------------*/ 656 657static int disk_ll_load_ie(struct ll_disk *ll, dm_block_t index, 658 struct disk_index_entry *ie) 659{ 660 return dm_btree_lookup(&ll->bitmap_info, ll->bitmap_root, &index, ie); 661} 662 663static int disk_ll_save_ie(struct ll_disk *ll, dm_block_t index, 664 struct disk_index_entry *ie) 665{ 666 __dm_bless_for_disk(ie); 667 return dm_btree_insert(&ll->bitmap_info, ll->bitmap_root, 668 &index, ie, &ll->bitmap_root); 669} 670 671static int disk_ll_init_index(struct ll_disk *ll) 672{ 673 return dm_btree_empty(&ll->bitmap_info, &ll->bitmap_root); 674} 675 676static int disk_ll_open(struct ll_disk *ll) 677{ 678 /* nothing to do */ 679 return 0; 680} 681 682static dm_block_t disk_ll_max_entries(struct ll_disk *ll) 683{ 684 return -1ULL; 685} 686 687static int disk_ll_commit(struct ll_disk *ll) 688{ 689 return 0; 690} 691 692int sm_ll_new_disk(struct ll_disk *ll, struct dm_transaction_manager *tm) 693{ 694 int r; 695 696 r = sm_ll_init(ll, tm); 697 if (r < 0) 698 return r; 699 700 ll->load_ie = disk_ll_load_ie; 701 ll->save_ie = disk_ll_save_ie; 702 ll->init_index = disk_ll_init_index; 703 ll->open_index = disk_ll_open; 704 ll->max_entries = disk_ll_max_entries; 705 ll->commit = disk_ll_commit; 706 707 ll->nr_blocks = 0; 708 ll->nr_allocated = 0; 709 710 r = ll->init_index(ll); 711 if (r < 0) 712 return r; 713 714 r = dm_btree_empty(&ll->ref_count_info, &ll->ref_count_root); 715 if (r < 0) 716 return r; 717 718 return 0; 719} 720 721int sm_ll_open_disk(struct ll_disk *ll, struct dm_transaction_manager *tm, 722 void *root_le, size_t len) 723{ 724 int r; 725 struct disk_sm_root *smr = root_le; 726 727 if (len < sizeof(struct disk_sm_root)) { 728 DMERR("sm_metadata root too small"); 729 return -ENOMEM; 730 } 731 732 r = sm_ll_init(ll, tm); 733 if (r < 0) 734 return r; 735 736 ll->load_ie = disk_ll_load_ie; 737 ll->save_ie = disk_ll_save_ie; 738 ll->init_index = disk_ll_init_index; 739 ll->open_index = disk_ll_open; 740 ll->max_entries = disk_ll_max_entries; 741 ll->commit = disk_ll_commit; 742 743 ll->nr_blocks = le64_to_cpu(smr->nr_blocks); 744 ll->nr_allocated = le64_to_cpu(smr->nr_allocated); 745 ll->bitmap_root = le64_to_cpu(smr->bitmap_root); 746 ll->ref_count_root = le64_to_cpu(smr->ref_count_root); 747 748 return ll->open_index(ll); 749} 750 751/*----------------------------------------------------------------*/ 752