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