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