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\n"); 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_msg("Error adding initial extents %d\n", ret); 29 return ret; 30 } 31 32 ret = btrfs_remove_free_space(cache, 0, SZ_4M); 33 if (ret) { 34 test_msg("Error removing extent %d\n", ret); 35 return ret; 36 } 37 38 if (test_check_exists(cache, 0, SZ_4M)) { 39 test_msg("Full remove left some lingering space\n"); 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_msg("Error adding half extent %d\n", ret); 47 return ret; 48 } 49 50 ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_1M); 51 if (ret) { 52 test_msg("Error removing tail end %d\n", ret); 53 return ret; 54 } 55 56 ret = btrfs_remove_free_space(cache, 0, SZ_1M); 57 if (ret) { 58 test_msg("Error removing front end %d\n", ret); 59 return ret; 60 } 61 62 ret = btrfs_remove_free_space(cache, SZ_2M, 4096); 63 if (ret) { 64 test_msg("Error removing middle piece %d\n", ret); 65 return ret; 66 } 67 68 if (test_check_exists(cache, 0, SZ_1M)) { 69 test_msg("Still have space at the front\n"); 70 return -1; 71 } 72 73 if (test_check_exists(cache, SZ_2M, 4096)) { 74 test_msg("Still have space in the middle\n"); 75 return -1; 76 } 77 78 if (test_check_exists(cache, 3 * SZ_1M, SZ_1M)) { 79 test_msg("Still have space at the end\n"); 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\n"); 96 97 ret = test_add_free_space_entry(cache, 0, SZ_4M, 1); 98 if (ret) { 99 test_msg("Couldn't create a bitmap entry %d\n", ret); 100 return ret; 101 } 102 103 ret = btrfs_remove_free_space(cache, 0, SZ_4M); 104 if (ret) { 105 test_msg("Error removing bitmap full range %d\n", ret); 106 return ret; 107 } 108 109 if (test_check_exists(cache, 0, SZ_4M)) { 110 test_msg("Left some space in bitmap\n"); 111 return -1; 112 } 113 114 ret = test_add_free_space_entry(cache, 0, SZ_4M, 1); 115 if (ret) { 116 test_msg("Couldn't add to our bitmap entry %d\n", ret); 117 return ret; 118 } 119 120 ret = btrfs_remove_free_space(cache, SZ_1M, SZ_2M); 121 if (ret) { 122 test_msg("Couldn't remove middle chunk %d\n", 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_msg("Couldn't add space that straddles two bitmaps %d\n", 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_msg("Couldn't remove overlapping space %d\n", ret); 144 return ret; 145 } 146 147 if (test_check_exists(cache, next_bitmap_offset - SZ_1M, SZ_2M)) { 148 test_msg("Left some space when removing overlapping\n"); 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\n"); 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_msg("Couldn't create bitmap entry %d\n", ret); 174 return ret; 175 } 176 177 ret = test_add_free_space_entry(cache, 0, SZ_1M, 0); 178 if (ret) { 179 test_msg("Couldn't add extent entry %d\n", ret); 180 return ret; 181 } 182 183 ret = btrfs_remove_free_space(cache, 0, SZ_1M); 184 if (ret) { 185 test_msg("Couldn't remove extent entry %d\n", ret); 186 return ret; 187 } 188 189 if (test_check_exists(cache, 0, SZ_1M)) { 190 test_msg("Left remnants after our remove\n"); 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_msg("Couldn't re-add extent entry %d\n", ret); 198 return ret; 199 } 200 201 ret = btrfs_remove_free_space(cache, SZ_4M, SZ_1M); 202 if (ret) { 203 test_msg("Couldn't remove from bitmap %d\n", ret); 204 return ret; 205 } 206 207 if (test_check_exists(cache, SZ_4M, SZ_1M)) { 208 test_msg("Left remnants in the bitmap\n"); 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_msg("Couldn't add to a bitmap %d\n", ret); 219 return ret; 220 } 221 222 ret = btrfs_remove_free_space(cache, SZ_512K, 3 * SZ_1M); 223 if (ret) { 224 test_msg("Couldn't remove overlapping space %d\n", ret); 225 return ret; 226 } 227 228 if (test_check_exists(cache, SZ_512K, 3 * SZ_1M)) { 229 test_msg("Left over pieces after removing overlapping\n"); 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_msg("Couldn't add space to the bitmap %d\n", ret); 239 return ret; 240 } 241 242 ret = test_add_free_space_entry(cache, SZ_2M, SZ_2M, 0); 243 if (ret) { 244 test_msg("Couldn't add extent to the cache %d\n", ret); 245 return ret; 246 } 247 248 ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_4M); 249 if (ret) { 250 test_msg("Problem removing overlapping space %d\n", ret); 251 return ret; 252 } 253 254 if (test_check_exists(cache, 3 * SZ_1M, SZ_4M)) { 255 test_msg("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_msg("Couldn't add bitmap %d\n", 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_msg("Couldn't add extent entry %d\n", 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_msg("Failed to free our space %d\n", ret); 286 return ret; 287 } 288 289 if (test_check_exists(cache, bitmap_offset + SZ_1M, 5 * SZ_1M)) { 290 test_msg("Left stuff over\n"); 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_msg("Couldn't add bitmap entry %d\n", 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_msg("Couldn't add extent entry %d\n", ret); 311 return ret; 312 } 313 314 ret = btrfs_remove_free_space(cache, SZ_1M, 3 * SZ_1M); 315 if (ret) { 316 test_msg("Error removing bitmap and extent overlapping %d\n", 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_msg("Incorrect # of extent entries in the cache: %d, expected %d\n", 339 cache->free_space_ctl->free_extents, num_extents); 340 return -EINVAL; 341 } 342 if (cache->free_space_ctl->total_bitmaps != num_bitmaps) { 343 test_msg("Incorrect # of extent entries in the cache: %d, expected %d\n", 344 cache->free_space_ctl->total_bitmaps, num_bitmaps); 345 return -EINVAL; 346 } 347 return 0; 348 } 349 350 /* Used by test_steal_space_from_bitmap_to_extent(). */ 351 static int check_cache_empty(struct btrfs_block_group_cache *cache) 352 { 353 u64 offset; 354 u64 max_extent_size; 355 356 /* 357 * Now lets confirm that there's absolutely no free space left to 358 * allocate. 359 */ 360 if (cache->free_space_ctl->free_space != 0) { 361 test_msg("Cache free space is not 0\n"); 362 return -EINVAL; 363 } 364 365 /* And any allocation request, no matter how small, should fail now. */ 366 offset = btrfs_find_space_for_alloc(cache, 0, 4096, 0, 367 &max_extent_size); 368 if (offset != 0) { 369 test_msg("Space allocation did not fail, returned offset: %llu", 370 offset); 371 return -EINVAL; 372 } 373 374 /* And no extent nor bitmap entries in the cache anymore. */ 375 return check_num_extents_and_bitmaps(cache, 0, 0); 376 } 377 378 /* 379 * Before we were able to steal free space from a bitmap entry to an extent 380 * entry, we could end up with 2 entries representing a contiguous free space. 381 * One would be an extent entry and the other a bitmap entry. Since in order 382 * to allocate space to a caller we use only 1 entry, we couldn't return that 383 * whole range to the caller if it was requested. This forced the caller to 384 * either assume ENOSPC or perform several smaller space allocations, which 385 * wasn't optimal as they could be spread all over the block group while under 386 * concurrency (extra overhead and fragmentation). 387 * 388 * This stealing approach is beneficial, since we always prefer to allocate 389 * from extent entries, both for clustered and non-clustered allocation 390 * requests. 391 */ 392 static int 393 test_steal_space_from_bitmap_to_extent(struct btrfs_block_group_cache *cache, 394 u32 sectorsize) 395 { 396 int ret; 397 u64 offset; 398 u64 max_extent_size; 399 const struct btrfs_free_space_op test_free_space_ops = { 400 .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds, 401 .use_bitmap = test_use_bitmap, 402 }; 403 const struct btrfs_free_space_op *orig_free_space_ops; 404 405 test_msg("Running space stealing from bitmap to extent\n"); 406 407 /* 408 * For this test, we want to ensure we end up with an extent entry 409 * immediately adjacent to a bitmap entry, where the bitmap starts 410 * at an offset where the extent entry ends. We keep adding and 411 * removing free space to reach into this state, but to get there 412 * we need to reach a point where marking new free space doesn't 413 * result in adding new extent entries or merging the new space 414 * with existing extent entries - the space ends up being marked 415 * in an existing bitmap that covers the new free space range. 416 * 417 * To get there, we need to reach the threshold defined set at 418 * cache->free_space_ctl->extents_thresh, which currently is 419 * 256 extents on a x86_64 system at least, and a few other 420 * conditions (check free_space_cache.c). Instead of making the 421 * test much longer and complicated, use a "use_bitmap" operation 422 * that forces use of bitmaps as soon as we have at least 1 423 * extent entry. 424 */ 425 orig_free_space_ops = cache->free_space_ctl->op; 426 cache->free_space_ctl->op = &test_free_space_ops; 427 428 /* 429 * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[ 430 */ 431 ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0); 432 if (ret) { 433 test_msg("Couldn't add extent entry %d\n", ret); 434 return ret; 435 } 436 437 /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */ 438 ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K, 439 SZ_128M - SZ_512K, 1); 440 if (ret) { 441 test_msg("Couldn't add bitmap entry %d\n", ret); 442 return ret; 443 } 444 445 ret = check_num_extents_and_bitmaps(cache, 2, 1); 446 if (ret) 447 return ret; 448 449 /* 450 * Now make only the first 256Kb of the bitmap marked as free, so that 451 * we end up with only the following ranges marked as free space: 452 * 453 * [128Mb - 256Kb, 128Mb - 128Kb[ 454 * [128Mb + 512Kb, 128Mb + 768Kb[ 455 */ 456 ret = btrfs_remove_free_space(cache, 457 SZ_128M + 768 * SZ_1K, 458 SZ_128M - 768 * SZ_1K); 459 if (ret) { 460 test_msg("Failed to free part of bitmap space %d\n", ret); 461 return ret; 462 } 463 464 /* Confirm that only those 2 ranges are marked as free. */ 465 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) { 466 test_msg("Free space range missing\n"); 467 return -ENOENT; 468 } 469 if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) { 470 test_msg("Free space range missing\n"); 471 return -ENOENT; 472 } 473 474 /* 475 * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked 476 * as free anymore. 477 */ 478 if (test_check_exists(cache, SZ_128M + 768 * SZ_1K, 479 SZ_128M - 768 * SZ_1K)) { 480 test_msg("Bitmap region not removed from space cache\n"); 481 return -EINVAL; 482 } 483 484 /* 485 * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is 486 * covered by the bitmap, isn't marked as free. 487 */ 488 if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) { 489 test_msg("Invalid bitmap region marked as free\n"); 490 return -EINVAL; 491 } 492 493 /* 494 * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered 495 * by the bitmap too, isn't marked as free either. 496 */ 497 if (test_check_exists(cache, SZ_128M, SZ_256K)) { 498 test_msg("Invalid bitmap region marked as free\n"); 499 return -EINVAL; 500 } 501 502 /* 503 * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But, 504 * lets make sure the free space cache marks it as free in the bitmap, 505 * and doesn't insert a new extent entry to represent this region. 506 */ 507 ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K); 508 if (ret) { 509 test_msg("Error adding free space: %d\n", ret); 510 return ret; 511 } 512 /* Confirm the region is marked as free. */ 513 if (!test_check_exists(cache, SZ_128M, SZ_512K)) { 514 test_msg("Bitmap region not marked as free\n"); 515 return -ENOENT; 516 } 517 518 /* 519 * Confirm that no new extent entries or bitmap entries were added to 520 * the cache after adding that free space region. 521 */ 522 ret = check_num_extents_and_bitmaps(cache, 2, 1); 523 if (ret) 524 return ret; 525 526 /* 527 * Now lets add a small free space region to the right of the previous 528 * one, which is not contiguous with it and is part of the bitmap too. 529 * The goal is to test that the bitmap entry space stealing doesn't 530 * steal this space region. 531 */ 532 ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, sectorsize); 533 if (ret) { 534 test_msg("Error adding free space: %d\n", ret); 535 return ret; 536 } 537 538 /* 539 * Confirm that no new extent entries or bitmap entries were added to 540 * the cache after adding that free space region. 541 */ 542 ret = check_num_extents_and_bitmaps(cache, 2, 1); 543 if (ret) 544 return ret; 545 546 /* 547 * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will 548 * expand the range covered by the existing extent entry that represents 549 * the free space [128Mb - 256Kb, 128Mb - 128Kb[. 550 */ 551 ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K); 552 if (ret) { 553 test_msg("Error adding free space: %d\n", ret); 554 return ret; 555 } 556 /* Confirm the region is marked as free. */ 557 if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) { 558 test_msg("Extent region not marked as free\n"); 559 return -ENOENT; 560 } 561 562 /* 563 * Confirm that our extent entry didn't stole all free space from the 564 * bitmap, because of the small 4Kb free space region. 565 */ 566 ret = check_num_extents_and_bitmaps(cache, 2, 1); 567 if (ret) 568 return ret; 569 570 /* 571 * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free 572 * space. Without stealing bitmap free space into extent entry space, 573 * we would have all this free space represented by 2 entries in the 574 * cache: 575 * 576 * extent entry covering range: [128Mb - 256Kb, 128Mb[ 577 * bitmap entry covering range: [128Mb, 128Mb + 768Kb[ 578 * 579 * Attempting to allocate the whole free space (1Mb) would fail, because 580 * we can't allocate from multiple entries. 581 * With the bitmap free space stealing, we get a single extent entry 582 * that represents the 1Mb free space, and therefore we're able to 583 * allocate the whole free space at once. 584 */ 585 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) { 586 test_msg("Expected region not marked as free\n"); 587 return -ENOENT; 588 } 589 590 if (cache->free_space_ctl->free_space != (SZ_1M + sectorsize)) { 591 test_msg("Cache free space is not 1Mb + %u\n", sectorsize); 592 return -EINVAL; 593 } 594 595 offset = btrfs_find_space_for_alloc(cache, 596 0, SZ_1M, 0, 597 &max_extent_size); 598 if (offset != (SZ_128M - SZ_256K)) { 599 test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n", 600 offset); 601 return -EINVAL; 602 } 603 604 /* 605 * All that remains is a sectorsize free space region in a bitmap. 606 * Confirm. 607 */ 608 ret = check_num_extents_and_bitmaps(cache, 1, 1); 609 if (ret) 610 return ret; 611 612 if (cache->free_space_ctl->free_space != sectorsize) { 613 test_msg("Cache free space is not %u\n", sectorsize); 614 return -EINVAL; 615 } 616 617 offset = btrfs_find_space_for_alloc(cache, 618 0, sectorsize, 0, 619 &max_extent_size); 620 if (offset != (SZ_128M + SZ_16M)) { 621 test_msg("Failed to allocate %u, returned offset : %llu\n", 622 sectorsize, offset); 623 return -EINVAL; 624 } 625 626 ret = check_cache_empty(cache); 627 if (ret) 628 return ret; 629 630 __btrfs_remove_free_space_cache(cache->free_space_ctl); 631 632 /* 633 * Now test a similar scenario, but where our extent entry is located 634 * to the right of the bitmap entry, so that we can check that stealing 635 * space from a bitmap to the front of an extent entry works. 636 */ 637 638 /* 639 * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[ 640 */ 641 ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0); 642 if (ret) { 643 test_msg("Couldn't add extent entry %d\n", ret); 644 return ret; 645 } 646 647 /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */ 648 ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1); 649 if (ret) { 650 test_msg("Couldn't add bitmap entry %d\n", ret); 651 return ret; 652 } 653 654 ret = check_num_extents_and_bitmaps(cache, 2, 1); 655 if (ret) 656 return ret; 657 658 /* 659 * Now make only the last 256Kb of the bitmap marked as free, so that 660 * we end up with only the following ranges marked as free space: 661 * 662 * [128Mb + 128b, 128Mb + 256Kb[ 663 * [128Mb - 768Kb, 128Mb - 512Kb[ 664 */ 665 ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K); 666 if (ret) { 667 test_msg("Failed to free part of bitmap space %d\n", ret); 668 return ret; 669 } 670 671 /* Confirm that only those 2 ranges are marked as free. */ 672 if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) { 673 test_msg("Free space range missing\n"); 674 return -ENOENT; 675 } 676 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) { 677 test_msg("Free space range missing\n"); 678 return -ENOENT; 679 } 680 681 /* 682 * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked 683 * as free anymore. 684 */ 685 if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) { 686 test_msg("Bitmap region not removed from space cache\n"); 687 return -EINVAL; 688 } 689 690 /* 691 * Confirm that the region [128Mb - 512Kb, 128Mb[, which is 692 * covered by the bitmap, isn't marked as free. 693 */ 694 if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { 695 test_msg("Invalid bitmap region marked as free\n"); 696 return -EINVAL; 697 } 698 699 /* 700 * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But, 701 * lets make sure the free space cache marks it as free in the bitmap, 702 * and doesn't insert a new extent entry to represent this region. 703 */ 704 ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K); 705 if (ret) { 706 test_msg("Error adding free space: %d\n", ret); 707 return ret; 708 } 709 /* Confirm the region is marked as free. */ 710 if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { 711 test_msg("Bitmap region not marked as free\n"); 712 return -ENOENT; 713 } 714 715 /* 716 * Confirm that no new extent entries or bitmap entries were added to 717 * the cache after adding that free space region. 718 */ 719 ret = check_num_extents_and_bitmaps(cache, 2, 1); 720 if (ret) 721 return ret; 722 723 /* 724 * Now lets add a small free space region to the left of the previous 725 * one, which is not contiguous with it and is part of the bitmap too. 726 * The goal is to test that the bitmap entry space stealing doesn't 727 * steal this space region. 728 */ 729 ret = btrfs_add_free_space(cache, SZ_32M, 2 * sectorsize); 730 if (ret) { 731 test_msg("Error adding free space: %d\n", ret); 732 return ret; 733 } 734 735 /* 736 * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will 737 * expand the range covered by the existing extent entry that represents 738 * the free space [128Mb + 128Kb, 128Mb + 256Kb[. 739 */ 740 ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K); 741 if (ret) { 742 test_msg("Error adding free space: %d\n", ret); 743 return ret; 744 } 745 /* Confirm the region is marked as free. */ 746 if (!test_check_exists(cache, SZ_128M, SZ_128K)) { 747 test_msg("Extent region not marked as free\n"); 748 return -ENOENT; 749 } 750 751 /* 752 * Confirm that our extent entry didn't stole all free space from the 753 * bitmap, because of the small 2 * sectorsize free space region. 754 */ 755 ret = check_num_extents_and_bitmaps(cache, 2, 1); 756 if (ret) 757 return ret; 758 759 /* 760 * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free 761 * space. Without stealing bitmap free space into extent entry space, 762 * we would have all this free space represented by 2 entries in the 763 * cache: 764 * 765 * extent entry covering range: [128Mb, 128Mb + 256Kb[ 766 * bitmap entry covering range: [128Mb - 768Kb, 128Mb[ 767 * 768 * Attempting to allocate the whole free space (1Mb) would fail, because 769 * we can't allocate from multiple entries. 770 * With the bitmap free space stealing, we get a single extent entry 771 * that represents the 1Mb free space, and therefore we're able to 772 * allocate the whole free space at once. 773 */ 774 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) { 775 test_msg("Expected region not marked as free\n"); 776 return -ENOENT; 777 } 778 779 if (cache->free_space_ctl->free_space != (SZ_1M + 2 * sectorsize)) { 780 test_msg("Cache free space is not 1Mb + %u\n", 2 * sectorsize); 781 return -EINVAL; 782 } 783 784 offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0, 785 &max_extent_size); 786 if (offset != (SZ_128M - 768 * SZ_1K)) { 787 test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n", 788 offset); 789 return -EINVAL; 790 } 791 792 /* 793 * All that remains is 2 * sectorsize free space region 794 * in a bitmap. Confirm. 795 */ 796 ret = check_num_extents_and_bitmaps(cache, 1, 1); 797 if (ret) 798 return ret; 799 800 if (cache->free_space_ctl->free_space != 2 * sectorsize) { 801 test_msg("Cache free space is not %u\n", 2 * sectorsize); 802 return -EINVAL; 803 } 804 805 offset = btrfs_find_space_for_alloc(cache, 806 0, 2 * sectorsize, 0, 807 &max_extent_size); 808 if (offset != SZ_32M) { 809 test_msg("Failed to allocate %u, offset: %llu\n", 810 2 * sectorsize, 811 offset); 812 return -EINVAL; 813 } 814 815 ret = check_cache_empty(cache); 816 if (ret) 817 return ret; 818 819 cache->free_space_ctl->op = orig_free_space_ops; 820 __btrfs_remove_free_space_cache(cache->free_space_ctl); 821 822 return 0; 823 } 824 825 int btrfs_test_free_space_cache(u32 sectorsize, u32 nodesize) 826 { 827 struct btrfs_fs_info *fs_info; 828 struct btrfs_block_group_cache *cache; 829 struct btrfs_root *root = NULL; 830 int ret = -ENOMEM; 831 832 test_msg("Running btrfs free space cache tests\n"); 833 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); 834 if (!fs_info) 835 return -ENOMEM; 836 837 838 /* 839 * For ppc64 (with 64k page size), bytes per bitmap might be 840 * larger than 1G. To make bitmap test available in ppc64, 841 * alloc dummy block group whose size cross bitmaps. 842 */ 843 cache = btrfs_alloc_dummy_block_group(fs_info, 844 BITS_PER_BITMAP * sectorsize + PAGE_SIZE); 845 if (!cache) { 846 test_msg("Couldn't run the tests\n"); 847 btrfs_free_dummy_fs_info(fs_info); 848 return 0; 849 } 850 851 root = btrfs_alloc_dummy_root(fs_info); 852 if (IS_ERR(root)) { 853 ret = PTR_ERR(root); 854 goto out; 855 } 856 857 root->fs_info->extent_root = root; 858 859 ret = test_extents(cache); 860 if (ret) 861 goto out; 862 ret = test_bitmaps(cache, sectorsize); 863 if (ret) 864 goto out; 865 ret = test_bitmaps_and_extents(cache, sectorsize); 866 if (ret) 867 goto out; 868 869 ret = test_steal_space_from_bitmap_to_extent(cache, sectorsize); 870 out: 871 btrfs_free_dummy_block_group(cache); 872 btrfs_free_dummy_root(root); 873 btrfs_free_dummy_fs_info(fs_info); 874 test_msg("Free space cache tests finished\n"); 875 return ret; 876 } 877