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