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