1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2013 Fusion IO. All rights reserved. 4 */ 5 6 #include <linux/slab.h> 7 #include "btrfs-tests.h" 8 #include "../ctree.h" 9 #include "../disk-io.h" 10 #include "../free-space-cache.h" 11 #include "../block-group.h" 12 13 #define BITS_PER_BITMAP (PAGE_SIZE * 8UL) 14 15 /* 16 * This test just does basic sanity checking, making sure we can add an extent 17 * entry and remove space from either end and the middle, and make sure we can 18 * remove space that covers adjacent extent entries. 19 */ 20 static int test_extents(struct btrfs_block_group_cache *cache) 21 { 22 int ret = 0; 23 24 test_msg("running extent only tests"); 25 26 /* First just make sure we can remove an entire entry */ 27 ret = btrfs_add_free_space(cache, 0, SZ_4M); 28 if (ret) { 29 test_err("error adding initial extents %d", ret); 30 return ret; 31 } 32 33 ret = btrfs_remove_free_space(cache, 0, SZ_4M); 34 if (ret) { 35 test_err("error removing extent %d", ret); 36 return ret; 37 } 38 39 if (test_check_exists(cache, 0, SZ_4M)) { 40 test_err("full remove left some lingering space"); 41 return -1; 42 } 43 44 /* Ok edge and middle cases now */ 45 ret = btrfs_add_free_space(cache, 0, SZ_4M); 46 if (ret) { 47 test_err("error adding half extent %d", ret); 48 return ret; 49 } 50 51 ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_1M); 52 if (ret) { 53 test_err("error removing tail end %d", ret); 54 return ret; 55 } 56 57 ret = btrfs_remove_free_space(cache, 0, SZ_1M); 58 if (ret) { 59 test_err("error removing front end %d", ret); 60 return ret; 61 } 62 63 ret = btrfs_remove_free_space(cache, SZ_2M, 4096); 64 if (ret) { 65 test_err("error removing middle piece %d", ret); 66 return ret; 67 } 68 69 if (test_check_exists(cache, 0, SZ_1M)) { 70 test_err("still have space at the front"); 71 return -1; 72 } 73 74 if (test_check_exists(cache, SZ_2M, 4096)) { 75 test_err("still have space in the middle"); 76 return -1; 77 } 78 79 if (test_check_exists(cache, 3 * SZ_1M, SZ_1M)) { 80 test_err("still have space at the end"); 81 return -1; 82 } 83 84 /* Cleanup */ 85 __btrfs_remove_free_space_cache(cache->free_space_ctl); 86 87 return 0; 88 } 89 90 static int test_bitmaps(struct btrfs_block_group_cache *cache, 91 u32 sectorsize) 92 { 93 u64 next_bitmap_offset; 94 int ret; 95 96 test_msg("running bitmap only tests"); 97 98 ret = test_add_free_space_entry(cache, 0, SZ_4M, 1); 99 if (ret) { 100 test_err("couldn't create a bitmap entry %d", ret); 101 return ret; 102 } 103 104 ret = btrfs_remove_free_space(cache, 0, SZ_4M); 105 if (ret) { 106 test_err("error removing bitmap full range %d", ret); 107 return ret; 108 } 109 110 if (test_check_exists(cache, 0, SZ_4M)) { 111 test_err("left some space in bitmap"); 112 return -1; 113 } 114 115 ret = test_add_free_space_entry(cache, 0, SZ_4M, 1); 116 if (ret) { 117 test_err("couldn't add to our bitmap entry %d", ret); 118 return ret; 119 } 120 121 ret = btrfs_remove_free_space(cache, SZ_1M, SZ_2M); 122 if (ret) { 123 test_err("couldn't remove middle chunk %d", ret); 124 return ret; 125 } 126 127 /* 128 * The first bitmap we have starts at offset 0 so the next one is just 129 * at the end of the first bitmap. 130 */ 131 next_bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize); 132 133 /* Test a bit straddling two bitmaps */ 134 ret = test_add_free_space_entry(cache, next_bitmap_offset - SZ_2M, 135 SZ_4M, 1); 136 if (ret) { 137 test_err("couldn't add space that straddles two bitmaps %d", 138 ret); 139 return ret; 140 } 141 142 ret = btrfs_remove_free_space(cache, next_bitmap_offset - SZ_1M, SZ_2M); 143 if (ret) { 144 test_err("couldn't remove overlapping space %d", ret); 145 return ret; 146 } 147 148 if (test_check_exists(cache, next_bitmap_offset - SZ_1M, SZ_2M)) { 149 test_err("left some space when removing overlapping"); 150 return -1; 151 } 152 153 __btrfs_remove_free_space_cache(cache->free_space_ctl); 154 155 return 0; 156 } 157 158 /* This is the high grade jackassery */ 159 static int test_bitmaps_and_extents(struct btrfs_block_group_cache *cache, 160 u32 sectorsize) 161 { 162 u64 bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize); 163 int ret; 164 165 test_msg("running bitmap and extent tests"); 166 167 /* 168 * First let's do something simple, an extent at the same offset as the 169 * bitmap, but the free space completely in the extent and then 170 * completely in the bitmap. 171 */ 172 ret = test_add_free_space_entry(cache, SZ_4M, SZ_1M, 1); 173 if (ret) { 174 test_err("couldn't create bitmap entry %d", ret); 175 return ret; 176 } 177 178 ret = test_add_free_space_entry(cache, 0, SZ_1M, 0); 179 if (ret) { 180 test_err("couldn't add extent entry %d", ret); 181 return ret; 182 } 183 184 ret = btrfs_remove_free_space(cache, 0, SZ_1M); 185 if (ret) { 186 test_err("couldn't remove extent entry %d", ret); 187 return ret; 188 } 189 190 if (test_check_exists(cache, 0, SZ_1M)) { 191 test_err("left remnants after our remove"); 192 return -1; 193 } 194 195 /* Now to add back the extent entry and remove from the bitmap */ 196 ret = test_add_free_space_entry(cache, 0, SZ_1M, 0); 197 if (ret) { 198 test_err("couldn't re-add extent entry %d", ret); 199 return ret; 200 } 201 202 ret = btrfs_remove_free_space(cache, SZ_4M, SZ_1M); 203 if (ret) { 204 test_err("couldn't remove from bitmap %d", ret); 205 return ret; 206 } 207 208 if (test_check_exists(cache, SZ_4M, SZ_1M)) { 209 test_err("left remnants in the bitmap"); 210 return -1; 211 } 212 213 /* 214 * Ok so a little more evil, extent entry and bitmap at the same offset, 215 * removing an overlapping chunk. 216 */ 217 ret = test_add_free_space_entry(cache, SZ_1M, SZ_4M, 1); 218 if (ret) { 219 test_err("couldn't add to a bitmap %d", ret); 220 return ret; 221 } 222 223 ret = btrfs_remove_free_space(cache, SZ_512K, 3 * SZ_1M); 224 if (ret) { 225 test_err("couldn't remove overlapping space %d", ret); 226 return ret; 227 } 228 229 if (test_check_exists(cache, SZ_512K, 3 * SZ_1M)) { 230 test_err("left over pieces after removing overlapping"); 231 return -1; 232 } 233 234 __btrfs_remove_free_space_cache(cache->free_space_ctl); 235 236 /* Now with the extent entry offset into the bitmap */ 237 ret = test_add_free_space_entry(cache, SZ_4M, SZ_4M, 1); 238 if (ret) { 239 test_err("couldn't add space to the bitmap %d", ret); 240 return ret; 241 } 242 243 ret = test_add_free_space_entry(cache, SZ_2M, SZ_2M, 0); 244 if (ret) { 245 test_err("couldn't add extent to the cache %d", ret); 246 return ret; 247 } 248 249 ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_4M); 250 if (ret) { 251 test_err("problem removing overlapping space %d", ret); 252 return ret; 253 } 254 255 if (test_check_exists(cache, 3 * SZ_1M, SZ_4M)) { 256 test_err("left something behind when removing space"); 257 return -1; 258 } 259 260 /* 261 * This has blown up in the past, the extent entry starts before the 262 * bitmap entry, but we're trying to remove an offset that falls 263 * completely within the bitmap range and is in both the extent entry 264 * and the bitmap entry, looks like this 265 * 266 * [ extent ] 267 * [ bitmap ] 268 * [ del ] 269 */ 270 __btrfs_remove_free_space_cache(cache->free_space_ctl); 271 ret = test_add_free_space_entry(cache, bitmap_offset + SZ_4M, SZ_4M, 1); 272 if (ret) { 273 test_err("couldn't add bitmap %d", ret); 274 return ret; 275 } 276 277 ret = test_add_free_space_entry(cache, bitmap_offset - SZ_1M, 278 5 * SZ_1M, 0); 279 if (ret) { 280 test_err("couldn't add extent entry %d", ret); 281 return ret; 282 } 283 284 ret = btrfs_remove_free_space(cache, bitmap_offset + SZ_1M, 5 * SZ_1M); 285 if (ret) { 286 test_err("failed to free our space %d", ret); 287 return ret; 288 } 289 290 if (test_check_exists(cache, bitmap_offset + SZ_1M, 5 * SZ_1M)) { 291 test_err("left stuff over"); 292 return -1; 293 } 294 295 __btrfs_remove_free_space_cache(cache->free_space_ctl); 296 297 /* 298 * This blew up before, we have part of the free space in a bitmap and 299 * then the entirety of the rest of the space in an extent. This used 300 * to return -EAGAIN back from btrfs_remove_extent, make sure this 301 * doesn't happen. 302 */ 303 ret = test_add_free_space_entry(cache, SZ_1M, SZ_2M, 1); 304 if (ret) { 305 test_err("couldn't add bitmap entry %d", ret); 306 return ret; 307 } 308 309 ret = test_add_free_space_entry(cache, 3 * SZ_1M, SZ_1M, 0); 310 if (ret) { 311 test_err("couldn't add extent entry %d", ret); 312 return ret; 313 } 314 315 ret = btrfs_remove_free_space(cache, SZ_1M, 3 * SZ_1M); 316 if (ret) { 317 test_err("error removing bitmap and extent overlapping %d", ret); 318 return ret; 319 } 320 321 __btrfs_remove_free_space_cache(cache->free_space_ctl); 322 return 0; 323 } 324 325 /* Used by test_steal_space_from_bitmap_to_extent(). */ 326 static bool test_use_bitmap(struct btrfs_free_space_ctl *ctl, 327 struct btrfs_free_space *info) 328 { 329 return ctl->free_extents > 0; 330 } 331 332 /* Used by test_steal_space_from_bitmap_to_extent(). */ 333 static int 334 check_num_extents_and_bitmaps(const struct btrfs_block_group_cache *cache, 335 const int num_extents, 336 const int num_bitmaps) 337 { 338 if (cache->free_space_ctl->free_extents != num_extents) { 339 test_err( 340 "incorrect # of extent entries in the cache: %d, expected %d", 341 cache->free_space_ctl->free_extents, num_extents); 342 return -EINVAL; 343 } 344 if (cache->free_space_ctl->total_bitmaps != num_bitmaps) { 345 test_err( 346 "incorrect # of extent entries in the cache: %d, expected %d", 347 cache->free_space_ctl->total_bitmaps, num_bitmaps); 348 return -EINVAL; 349 } 350 return 0; 351 } 352 353 /* Used by test_steal_space_from_bitmap_to_extent(). */ 354 static int check_cache_empty(struct btrfs_block_group_cache *cache) 355 { 356 u64 offset; 357 u64 max_extent_size; 358 359 /* 360 * Now lets confirm that there's absolutely no free space left to 361 * allocate. 362 */ 363 if (cache->free_space_ctl->free_space != 0) { 364 test_err("cache free space is not 0"); 365 return -EINVAL; 366 } 367 368 /* And any allocation request, no matter how small, should fail now. */ 369 offset = btrfs_find_space_for_alloc(cache, 0, 4096, 0, 370 &max_extent_size); 371 if (offset != 0) { 372 test_err("space allocation did not fail, returned offset: %llu", 373 offset); 374 return -EINVAL; 375 } 376 377 /* And no extent nor bitmap entries in the cache anymore. */ 378 return check_num_extents_and_bitmaps(cache, 0, 0); 379 } 380 381 /* 382 * Before we were able to steal free space from a bitmap entry to an extent 383 * entry, we could end up with 2 entries representing a contiguous free space. 384 * One would be an extent entry and the other a bitmap entry. Since in order 385 * to allocate space to a caller we use only 1 entry, we couldn't return that 386 * whole range to the caller if it was requested. This forced the caller to 387 * either assume ENOSPC or perform several smaller space allocations, which 388 * wasn't optimal as they could be spread all over the block group while under 389 * concurrency (extra overhead and fragmentation). 390 * 391 * This stealing approach is beneficial, since we always prefer to allocate 392 * from extent entries, both for clustered and non-clustered allocation 393 * requests. 394 */ 395 static int 396 test_steal_space_from_bitmap_to_extent(struct btrfs_block_group_cache *cache, 397 u32 sectorsize) 398 { 399 int ret; 400 u64 offset; 401 u64 max_extent_size; 402 const struct btrfs_free_space_op test_free_space_ops = { 403 .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds, 404 .use_bitmap = test_use_bitmap, 405 }; 406 const struct btrfs_free_space_op *orig_free_space_ops; 407 408 test_msg("running space stealing from bitmap to extent tests"); 409 410 /* 411 * For this test, we want to ensure we end up with an extent entry 412 * immediately adjacent to a bitmap entry, where the bitmap starts 413 * at an offset where the extent entry ends. We keep adding and 414 * removing free space to reach into this state, but to get there 415 * we need to reach a point where marking new free space doesn't 416 * result in adding new extent entries or merging the new space 417 * with existing extent entries - the space ends up being marked 418 * in an existing bitmap that covers the new free space range. 419 * 420 * To get there, we need to reach the threshold defined set at 421 * cache->free_space_ctl->extents_thresh, which currently is 422 * 256 extents on a x86_64 system at least, and a few other 423 * conditions (check free_space_cache.c). Instead of making the 424 * test much longer and complicated, use a "use_bitmap" operation 425 * that forces use of bitmaps as soon as we have at least 1 426 * extent entry. 427 */ 428 orig_free_space_ops = cache->free_space_ctl->op; 429 cache->free_space_ctl->op = &test_free_space_ops; 430 431 /* 432 * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[ 433 */ 434 ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0); 435 if (ret) { 436 test_err("couldn't add extent entry %d", ret); 437 return ret; 438 } 439 440 /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */ 441 ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K, 442 SZ_128M - SZ_512K, 1); 443 if (ret) { 444 test_err("couldn't add bitmap entry %d", ret); 445 return ret; 446 } 447 448 ret = check_num_extents_and_bitmaps(cache, 2, 1); 449 if (ret) 450 return ret; 451 452 /* 453 * Now make only the first 256Kb of the bitmap marked as free, so that 454 * we end up with only the following ranges marked as free space: 455 * 456 * [128Mb - 256Kb, 128Mb - 128Kb[ 457 * [128Mb + 512Kb, 128Mb + 768Kb[ 458 */ 459 ret = btrfs_remove_free_space(cache, 460 SZ_128M + 768 * SZ_1K, 461 SZ_128M - 768 * SZ_1K); 462 if (ret) { 463 test_err("failed to free part of bitmap space %d", ret); 464 return ret; 465 } 466 467 /* Confirm that only those 2 ranges are marked as free. */ 468 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) { 469 test_err("free space range missing"); 470 return -ENOENT; 471 } 472 if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) { 473 test_err("free space range missing"); 474 return -ENOENT; 475 } 476 477 /* 478 * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked 479 * as free anymore. 480 */ 481 if (test_check_exists(cache, SZ_128M + 768 * SZ_1K, 482 SZ_128M - 768 * SZ_1K)) { 483 test_err("bitmap region not removed from space cache"); 484 return -EINVAL; 485 } 486 487 /* 488 * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is 489 * covered by the bitmap, isn't marked as free. 490 */ 491 if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) { 492 test_err("invalid bitmap region marked as free"); 493 return -EINVAL; 494 } 495 496 /* 497 * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered 498 * by the bitmap too, isn't marked as free either. 499 */ 500 if (test_check_exists(cache, SZ_128M, SZ_256K)) { 501 test_err("invalid bitmap region marked as free"); 502 return -EINVAL; 503 } 504 505 /* 506 * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But, 507 * lets make sure the free space cache marks it as free in the bitmap, 508 * and doesn't insert a new extent entry to represent this region. 509 */ 510 ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K); 511 if (ret) { 512 test_err("error adding free space: %d", ret); 513 return ret; 514 } 515 /* Confirm the region is marked as free. */ 516 if (!test_check_exists(cache, SZ_128M, SZ_512K)) { 517 test_err("bitmap region not marked as free"); 518 return -ENOENT; 519 } 520 521 /* 522 * Confirm that no new extent entries or bitmap entries were added to 523 * the cache after adding that free space region. 524 */ 525 ret = check_num_extents_and_bitmaps(cache, 2, 1); 526 if (ret) 527 return ret; 528 529 /* 530 * Now lets add a small free space region to the right of the previous 531 * one, which is not contiguous with it and is part of the bitmap too. 532 * The goal is to test that the bitmap entry space stealing doesn't 533 * steal this space region. 534 */ 535 ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, sectorsize); 536 if (ret) { 537 test_err("error adding free space: %d", ret); 538 return ret; 539 } 540 541 /* 542 * Confirm that no new extent entries or bitmap entries were added to 543 * the cache after adding that free space region. 544 */ 545 ret = check_num_extents_and_bitmaps(cache, 2, 1); 546 if (ret) 547 return ret; 548 549 /* 550 * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will 551 * expand the range covered by the existing extent entry that represents 552 * the free space [128Mb - 256Kb, 128Mb - 128Kb[. 553 */ 554 ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K); 555 if (ret) { 556 test_err("error adding free space: %d", ret); 557 return ret; 558 } 559 /* Confirm the region is marked as free. */ 560 if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) { 561 test_err("extent region not marked as free"); 562 return -ENOENT; 563 } 564 565 /* 566 * Confirm that our extent entry didn't stole all free space from the 567 * bitmap, because of the small 4Kb free space region. 568 */ 569 ret = check_num_extents_and_bitmaps(cache, 2, 1); 570 if (ret) 571 return ret; 572 573 /* 574 * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free 575 * space. Without stealing bitmap free space into extent entry space, 576 * we would have all this free space represented by 2 entries in the 577 * cache: 578 * 579 * extent entry covering range: [128Mb - 256Kb, 128Mb[ 580 * bitmap entry covering range: [128Mb, 128Mb + 768Kb[ 581 * 582 * Attempting to allocate the whole free space (1Mb) would fail, because 583 * we can't allocate from multiple entries. 584 * With the bitmap free space stealing, we get a single extent entry 585 * that represents the 1Mb free space, and therefore we're able to 586 * allocate the whole free space at once. 587 */ 588 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) { 589 test_err("expected region not marked as free"); 590 return -ENOENT; 591 } 592 593 if (cache->free_space_ctl->free_space != (SZ_1M + sectorsize)) { 594 test_err("cache free space is not 1Mb + %u", sectorsize); 595 return -EINVAL; 596 } 597 598 offset = btrfs_find_space_for_alloc(cache, 599 0, SZ_1M, 0, 600 &max_extent_size); 601 if (offset != (SZ_128M - SZ_256K)) { 602 test_err( 603 "failed to allocate 1Mb from space cache, returned offset is: %llu", 604 offset); 605 return -EINVAL; 606 } 607 608 /* 609 * All that remains is a sectorsize free space region in a bitmap. 610 * Confirm. 611 */ 612 ret = check_num_extents_and_bitmaps(cache, 1, 1); 613 if (ret) 614 return ret; 615 616 if (cache->free_space_ctl->free_space != sectorsize) { 617 test_err("cache free space is not %u", sectorsize); 618 return -EINVAL; 619 } 620 621 offset = btrfs_find_space_for_alloc(cache, 622 0, sectorsize, 0, 623 &max_extent_size); 624 if (offset != (SZ_128M + SZ_16M)) { 625 test_err("failed to allocate %u, returned offset : %llu", 626 sectorsize, offset); 627 return -EINVAL; 628 } 629 630 ret = check_cache_empty(cache); 631 if (ret) 632 return ret; 633 634 __btrfs_remove_free_space_cache(cache->free_space_ctl); 635 636 /* 637 * Now test a similar scenario, but where our extent entry is located 638 * to the right of the bitmap entry, so that we can check that stealing 639 * space from a bitmap to the front of an extent entry works. 640 */ 641 642 /* 643 * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[ 644 */ 645 ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0); 646 if (ret) { 647 test_err("couldn't add extent entry %d", ret); 648 return ret; 649 } 650 651 /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */ 652 ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1); 653 if (ret) { 654 test_err("couldn't add bitmap entry %d", ret); 655 return ret; 656 } 657 658 ret = check_num_extents_and_bitmaps(cache, 2, 1); 659 if (ret) 660 return ret; 661 662 /* 663 * Now make only the last 256Kb of the bitmap marked as free, so that 664 * we end up with only the following ranges marked as free space: 665 * 666 * [128Mb + 128b, 128Mb + 256Kb[ 667 * [128Mb - 768Kb, 128Mb - 512Kb[ 668 */ 669 ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K); 670 if (ret) { 671 test_err("failed to free part of bitmap space %d", ret); 672 return ret; 673 } 674 675 /* Confirm that only those 2 ranges are marked as free. */ 676 if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) { 677 test_err("free space range missing"); 678 return -ENOENT; 679 } 680 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) { 681 test_err("free space range missing"); 682 return -ENOENT; 683 } 684 685 /* 686 * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked 687 * as free anymore. 688 */ 689 if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) { 690 test_err("bitmap region not removed from space cache"); 691 return -EINVAL; 692 } 693 694 /* 695 * Confirm that the region [128Mb - 512Kb, 128Mb[, which is 696 * covered by the bitmap, isn't marked as free. 697 */ 698 if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { 699 test_err("invalid bitmap region marked as free"); 700 return -EINVAL; 701 } 702 703 /* 704 * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But, 705 * lets make sure the free space cache marks it as free in the bitmap, 706 * and doesn't insert a new extent entry to represent this region. 707 */ 708 ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K); 709 if (ret) { 710 test_err("error adding free space: %d", ret); 711 return ret; 712 } 713 /* Confirm the region is marked as free. */ 714 if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { 715 test_err("bitmap region not marked as free"); 716 return -ENOENT; 717 } 718 719 /* 720 * Confirm that no new extent entries or bitmap entries were added to 721 * the cache after adding that free space region. 722 */ 723 ret = check_num_extents_and_bitmaps(cache, 2, 1); 724 if (ret) 725 return ret; 726 727 /* 728 * Now lets add a small free space region to the left of the previous 729 * one, which is not contiguous with it and is part of the bitmap too. 730 * The goal is to test that the bitmap entry space stealing doesn't 731 * steal this space region. 732 */ 733 ret = btrfs_add_free_space(cache, SZ_32M, 2 * sectorsize); 734 if (ret) { 735 test_err("error adding free space: %d", ret); 736 return ret; 737 } 738 739 /* 740 * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will 741 * expand the range covered by the existing extent entry that represents 742 * the free space [128Mb + 128Kb, 128Mb + 256Kb[. 743 */ 744 ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K); 745 if (ret) { 746 test_err("error adding free space: %d", ret); 747 return ret; 748 } 749 /* Confirm the region is marked as free. */ 750 if (!test_check_exists(cache, SZ_128M, SZ_128K)) { 751 test_err("extent region not marked as free"); 752 return -ENOENT; 753 } 754 755 /* 756 * Confirm that our extent entry didn't stole all free space from the 757 * bitmap, because of the small 2 * sectorsize free space region. 758 */ 759 ret = check_num_extents_and_bitmaps(cache, 2, 1); 760 if (ret) 761 return ret; 762 763 /* 764 * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free 765 * space. Without stealing bitmap free space into extent entry space, 766 * we would have all this free space represented by 2 entries in the 767 * cache: 768 * 769 * extent entry covering range: [128Mb, 128Mb + 256Kb[ 770 * bitmap entry covering range: [128Mb - 768Kb, 128Mb[ 771 * 772 * Attempting to allocate the whole free space (1Mb) would fail, because 773 * we can't allocate from multiple entries. 774 * With the bitmap free space stealing, we get a single extent entry 775 * that represents the 1Mb free space, and therefore we're able to 776 * allocate the whole free space at once. 777 */ 778 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) { 779 test_err("expected region not marked as free"); 780 return -ENOENT; 781 } 782 783 if (cache->free_space_ctl->free_space != (SZ_1M + 2 * sectorsize)) { 784 test_err("cache free space is not 1Mb + %u", 2 * sectorsize); 785 return -EINVAL; 786 } 787 788 offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0, 789 &max_extent_size); 790 if (offset != (SZ_128M - 768 * SZ_1K)) { 791 test_err( 792 "failed to allocate 1Mb from space cache, returned offset is: %llu", 793 offset); 794 return -EINVAL; 795 } 796 797 /* 798 * All that remains is 2 * sectorsize free space region 799 * in a bitmap. Confirm. 800 */ 801 ret = check_num_extents_and_bitmaps(cache, 1, 1); 802 if (ret) 803 return ret; 804 805 if (cache->free_space_ctl->free_space != 2 * sectorsize) { 806 test_err("cache free space is not %u", 2 * sectorsize); 807 return -EINVAL; 808 } 809 810 offset = btrfs_find_space_for_alloc(cache, 811 0, 2 * sectorsize, 0, 812 &max_extent_size); 813 if (offset != SZ_32M) { 814 test_err("failed to allocate %u, offset: %llu", 815 2 * sectorsize, offset); 816 return -EINVAL; 817 } 818 819 ret = check_cache_empty(cache); 820 if (ret) 821 return ret; 822 823 cache->free_space_ctl->op = orig_free_space_ops; 824 __btrfs_remove_free_space_cache(cache->free_space_ctl); 825 826 return 0; 827 } 828 829 int btrfs_test_free_space_cache(u32 sectorsize, u32 nodesize) 830 { 831 struct btrfs_fs_info *fs_info; 832 struct btrfs_block_group_cache *cache; 833 struct btrfs_root *root = NULL; 834 int ret = -ENOMEM; 835 836 test_msg("running btrfs free space cache tests"); 837 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); 838 if (!fs_info) { 839 test_std_err(TEST_ALLOC_FS_INFO); 840 return -ENOMEM; 841 } 842 843 /* 844 * For ppc64 (with 64k page size), bytes per bitmap might be 845 * larger than 1G. To make bitmap test available in ppc64, 846 * alloc dummy block group whose size cross bitmaps. 847 */ 848 cache = btrfs_alloc_dummy_block_group(fs_info, 849 BITS_PER_BITMAP * sectorsize + PAGE_SIZE); 850 if (!cache) { 851 test_std_err(TEST_ALLOC_BLOCK_GROUP); 852 btrfs_free_dummy_fs_info(fs_info); 853 return 0; 854 } 855 856 root = btrfs_alloc_dummy_root(fs_info); 857 if (IS_ERR(root)) { 858 test_std_err(TEST_ALLOC_ROOT); 859 ret = PTR_ERR(root); 860 goto out; 861 } 862 863 root->fs_info->extent_root = root; 864 865 ret = test_extents(cache); 866 if (ret) 867 goto out; 868 ret = test_bitmaps(cache, sectorsize); 869 if (ret) 870 goto out; 871 ret = test_bitmaps_and_extents(cache, sectorsize); 872 if (ret) 873 goto out; 874 875 ret = test_steal_space_from_bitmap_to_extent(cache, sectorsize); 876 out: 877 btrfs_free_dummy_block_group(cache); 878 btrfs_free_dummy_root(root); 879 btrfs_free_dummy_fs_info(fs_info); 880 return ret; 881 } 882