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_CACHE_SIZE * 8) 26 27 /* 28 * This test just does basic sanity checking, making sure we can add an exten 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 benefical, since we always prefer to allocate from 400 * extent entries, both for clustered and non-clustered allocation requests. 401 */ 402 static int 403 test_steal_space_from_bitmap_to_extent(struct btrfs_block_group_cache *cache) 404 { 405 int ret; 406 u64 offset; 407 u64 max_extent_size; 408 const struct btrfs_free_space_op test_free_space_ops = { 409 .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds, 410 .use_bitmap = test_use_bitmap, 411 }; 412 const struct btrfs_free_space_op *orig_free_space_ops; 413 414 test_msg("Running space stealing from bitmap to extent\n"); 415 416 /* 417 * For this test, we want to ensure we end up with an extent entry 418 * immediately adjacent to a bitmap entry, where the bitmap starts 419 * at an offset where the extent entry ends. We keep adding and 420 * removing free space to reach into this state, but to get there 421 * we need to reach a point where marking new free space doesn't 422 * result in adding new extent entries or merging the new space 423 * with existing extent entries - the space ends up being marked 424 * in an existing bitmap that covers the new free space range. 425 * 426 * To get there, we need to reach the threshold defined set at 427 * cache->free_space_ctl->extents_thresh, which currently is 428 * 256 extents on a x86_64 system at least, and a few other 429 * conditions (check free_space_cache.c). Instead of making the 430 * test much longer and complicated, use a "use_bitmap" operation 431 * that forces use of bitmaps as soon as we have at least 1 432 * extent entry. 433 */ 434 orig_free_space_ops = cache->free_space_ctl->op; 435 cache->free_space_ctl->op = &test_free_space_ops; 436 437 /* 438 * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[ 439 */ 440 ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0); 441 if (ret) { 442 test_msg("Couldn't add extent entry %d\n", ret); 443 return ret; 444 } 445 446 /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */ 447 ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K, 448 SZ_128M - SZ_512K, 1); 449 if (ret) { 450 test_msg("Couldn't add bitmap entry %d\n", ret); 451 return ret; 452 } 453 454 ret = check_num_extents_and_bitmaps(cache, 2, 1); 455 if (ret) 456 return ret; 457 458 /* 459 * Now make only the first 256Kb of the bitmap marked as free, so that 460 * we end up with only the following ranges marked as free space: 461 * 462 * [128Mb - 256Kb, 128Mb - 128Kb[ 463 * [128Mb + 512Kb, 128Mb + 768Kb[ 464 */ 465 ret = btrfs_remove_free_space(cache, 466 SZ_128M + 768 * SZ_1K, 467 SZ_128M - 768 * SZ_1K); 468 if (ret) { 469 test_msg("Failed to free part of bitmap space %d\n", ret); 470 return ret; 471 } 472 473 /* Confirm that only those 2 ranges are marked as free. */ 474 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) { 475 test_msg("Free space range missing\n"); 476 return -ENOENT; 477 } 478 if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) { 479 test_msg("Free space range missing\n"); 480 return -ENOENT; 481 } 482 483 /* 484 * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked 485 * as free anymore. 486 */ 487 if (test_check_exists(cache, SZ_128M + 768 * SZ_1K, 488 SZ_128M - 768 * SZ_1K)) { 489 test_msg("Bitmap region not removed from space cache\n"); 490 return -EINVAL; 491 } 492 493 /* 494 * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is 495 * covered by the bitmap, isn't marked as free. 496 */ 497 if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) { 498 test_msg("Invalid bitmap region marked as free\n"); 499 return -EINVAL; 500 } 501 502 /* 503 * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered 504 * by the bitmap too, isn't marked as free either. 505 */ 506 if (test_check_exists(cache, SZ_128M, SZ_256K)) { 507 test_msg("Invalid bitmap region marked as free\n"); 508 return -EINVAL; 509 } 510 511 /* 512 * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But, 513 * lets make sure the free space cache marks it as free in the bitmap, 514 * and doesn't insert a new extent entry to represent this region. 515 */ 516 ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K); 517 if (ret) { 518 test_msg("Error adding free space: %d\n", ret); 519 return ret; 520 } 521 /* Confirm the region is marked as free. */ 522 if (!test_check_exists(cache, SZ_128M, SZ_512K)) { 523 test_msg("Bitmap region not marked as free\n"); 524 return -ENOENT; 525 } 526 527 /* 528 * Confirm that no new extent entries or bitmap entries were added to 529 * the cache after adding that free space region. 530 */ 531 ret = check_num_extents_and_bitmaps(cache, 2, 1); 532 if (ret) 533 return ret; 534 535 /* 536 * Now lets add a small free space region to the right of the previous 537 * one, which is not contiguous with it and is part of the bitmap too. 538 * The goal is to test that the bitmap entry space stealing doesn't 539 * steal this space region. 540 */ 541 ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, 4096); 542 if (ret) { 543 test_msg("Error adding free space: %d\n", ret); 544 return ret; 545 } 546 547 /* 548 * Confirm that no new extent entries or bitmap entries were added to 549 * the cache after adding that free space region. 550 */ 551 ret = check_num_extents_and_bitmaps(cache, 2, 1); 552 if (ret) 553 return ret; 554 555 /* 556 * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will 557 * expand the range covered by the existing extent entry that represents 558 * the free space [128Mb - 256Kb, 128Mb - 128Kb[. 559 */ 560 ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K); 561 if (ret) { 562 test_msg("Error adding free space: %d\n", ret); 563 return ret; 564 } 565 /* Confirm the region is marked as free. */ 566 if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) { 567 test_msg("Extent region not marked as free\n"); 568 return -ENOENT; 569 } 570 571 /* 572 * Confirm that our extent entry didn't stole all free space from the 573 * bitmap, because of the small 4Kb free space region. 574 */ 575 ret = check_num_extents_and_bitmaps(cache, 2, 1); 576 if (ret) 577 return ret; 578 579 /* 580 * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free 581 * space. Without stealing bitmap free space into extent entry space, 582 * we would have all this free space represented by 2 entries in the 583 * cache: 584 * 585 * extent entry covering range: [128Mb - 256Kb, 128Mb[ 586 * bitmap entry covering range: [128Mb, 128Mb + 768Kb[ 587 * 588 * Attempting to allocate the whole free space (1Mb) would fail, because 589 * we can't allocate from multiple entries. 590 * With the bitmap free space stealing, we get a single extent entry 591 * that represents the 1Mb free space, and therefore we're able to 592 * allocate the whole free space at once. 593 */ 594 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) { 595 test_msg("Expected region not marked as free\n"); 596 return -ENOENT; 597 } 598 599 if (cache->free_space_ctl->free_space != (SZ_1M + 4096)) { 600 test_msg("Cache free space is not 1Mb + 4Kb\n"); 601 return -EINVAL; 602 } 603 604 offset = btrfs_find_space_for_alloc(cache, 605 0, SZ_1M, 0, 606 &max_extent_size); 607 if (offset != (SZ_128M - SZ_256K)) { 608 test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n", 609 offset); 610 return -EINVAL; 611 } 612 613 /* All that remains is a 4Kb free space region in a bitmap. Confirm. */ 614 ret = check_num_extents_and_bitmaps(cache, 1, 1); 615 if (ret) 616 return ret; 617 618 if (cache->free_space_ctl->free_space != 4096) { 619 test_msg("Cache free space is not 4Kb\n"); 620 return -EINVAL; 621 } 622 623 offset = btrfs_find_space_for_alloc(cache, 624 0, 4096, 0, 625 &max_extent_size); 626 if (offset != (SZ_128M + SZ_16M)) { 627 test_msg("Failed to allocate 4Kb from space cache, returned offset is: %llu\n", 628 offset); 629 return -EINVAL; 630 } 631 632 ret = check_cache_empty(cache); 633 if (ret) 634 return ret; 635 636 __btrfs_remove_free_space_cache(cache->free_space_ctl); 637 638 /* 639 * Now test a similar scenario, but where our extent entry is located 640 * to the right of the bitmap entry, so that we can check that stealing 641 * space from a bitmap to the front of an extent entry works. 642 */ 643 644 /* 645 * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[ 646 */ 647 ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0); 648 if (ret) { 649 test_msg("Couldn't add extent entry %d\n", ret); 650 return ret; 651 } 652 653 /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */ 654 ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1); 655 if (ret) { 656 test_msg("Couldn't add bitmap entry %d\n", ret); 657 return ret; 658 } 659 660 ret = check_num_extents_and_bitmaps(cache, 2, 1); 661 if (ret) 662 return ret; 663 664 /* 665 * Now make only the last 256Kb of the bitmap marked as free, so that 666 * we end up with only the following ranges marked as free space: 667 * 668 * [128Mb + 128b, 128Mb + 256Kb[ 669 * [128Mb - 768Kb, 128Mb - 512Kb[ 670 */ 671 ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K); 672 if (ret) { 673 test_msg("Failed to free part of bitmap space %d\n", ret); 674 return ret; 675 } 676 677 /* Confirm that only those 2 ranges are marked as free. */ 678 if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) { 679 test_msg("Free space range missing\n"); 680 return -ENOENT; 681 } 682 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) { 683 test_msg("Free space range missing\n"); 684 return -ENOENT; 685 } 686 687 /* 688 * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked 689 * as free anymore. 690 */ 691 if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) { 692 test_msg("Bitmap region not removed from space cache\n"); 693 return -EINVAL; 694 } 695 696 /* 697 * Confirm that the region [128Mb - 512Kb, 128Mb[, which is 698 * covered by the bitmap, isn't marked as free. 699 */ 700 if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { 701 test_msg("Invalid bitmap region marked as free\n"); 702 return -EINVAL; 703 } 704 705 /* 706 * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But, 707 * lets make sure the free space cache marks it as free in the bitmap, 708 * and doesn't insert a new extent entry to represent this region. 709 */ 710 ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K); 711 if (ret) { 712 test_msg("Error adding free space: %d\n", ret); 713 return ret; 714 } 715 /* Confirm the region is marked as free. */ 716 if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) { 717 test_msg("Bitmap region not marked as free\n"); 718 return -ENOENT; 719 } 720 721 /* 722 * Confirm that no new extent entries or bitmap entries were added to 723 * the cache after adding that free space region. 724 */ 725 ret = check_num_extents_and_bitmaps(cache, 2, 1); 726 if (ret) 727 return ret; 728 729 /* 730 * Now lets add a small free space region to the left of the previous 731 * one, which is not contiguous with it and is part of the bitmap too. 732 * The goal is to test that the bitmap entry space stealing doesn't 733 * steal this space region. 734 */ 735 ret = btrfs_add_free_space(cache, SZ_32M, 8192); 736 if (ret) { 737 test_msg("Error adding free space: %d\n", ret); 738 return ret; 739 } 740 741 /* 742 * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will 743 * expand the range covered by the existing extent entry that represents 744 * the free space [128Mb + 128Kb, 128Mb + 256Kb[. 745 */ 746 ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K); 747 if (ret) { 748 test_msg("Error adding free space: %d\n", ret); 749 return ret; 750 } 751 /* Confirm the region is marked as free. */ 752 if (!test_check_exists(cache, SZ_128M, SZ_128K)) { 753 test_msg("Extent region not marked as free\n"); 754 return -ENOENT; 755 } 756 757 /* 758 * Confirm that our extent entry didn't stole all free space from the 759 * bitmap, because of the small 8Kb free space region. 760 */ 761 ret = check_num_extents_and_bitmaps(cache, 2, 1); 762 if (ret) 763 return ret; 764 765 /* 766 * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free 767 * space. Without stealing bitmap free space into extent entry space, 768 * we would have all this free space represented by 2 entries in the 769 * cache: 770 * 771 * extent entry covering range: [128Mb, 128Mb + 256Kb[ 772 * bitmap entry covering range: [128Mb - 768Kb, 128Mb[ 773 * 774 * Attempting to allocate the whole free space (1Mb) would fail, because 775 * we can't allocate from multiple entries. 776 * With the bitmap free space stealing, we get a single extent entry 777 * that represents the 1Mb free space, and therefore we're able to 778 * allocate the whole free space at once. 779 */ 780 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) { 781 test_msg("Expected region not marked as free\n"); 782 return -ENOENT; 783 } 784 785 if (cache->free_space_ctl->free_space != (SZ_1M + 8192)) { 786 test_msg("Cache free space is not 1Mb + 8Kb\n"); 787 return -EINVAL; 788 } 789 790 offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0, 791 &max_extent_size); 792 if (offset != (SZ_128M - 768 * SZ_1K)) { 793 test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n", 794 offset); 795 return -EINVAL; 796 } 797 798 /* All that remains is a 8Kb free space region in a bitmap. Confirm. */ 799 ret = check_num_extents_and_bitmaps(cache, 1, 1); 800 if (ret) 801 return ret; 802 803 if (cache->free_space_ctl->free_space != 8192) { 804 test_msg("Cache free space is not 8Kb\n"); 805 return -EINVAL; 806 } 807 808 offset = btrfs_find_space_for_alloc(cache, 809 0, 8192, 0, 810 &max_extent_size); 811 if (offset != SZ_32M) { 812 test_msg("Failed to allocate 8Kb from space cache, returned offset is: %llu\n", 813 offset); 814 return -EINVAL; 815 } 816 817 ret = check_cache_empty(cache); 818 if (ret) 819 return ret; 820 821 cache->free_space_ctl->op = orig_free_space_ops; 822 __btrfs_remove_free_space_cache(cache->free_space_ctl); 823 824 return 0; 825 } 826 827 int btrfs_test_free_space_cache(void) 828 { 829 struct btrfs_block_group_cache *cache; 830 struct btrfs_root *root = NULL; 831 int ret = -ENOMEM; 832 833 test_msg("Running btrfs free space cache tests\n"); 834 835 cache = btrfs_alloc_dummy_block_group(1024 * 1024 * 1024); 836 if (!cache) { 837 test_msg("Couldn't run the tests\n"); 838 return 0; 839 } 840 841 root = btrfs_alloc_dummy_root(); 842 if (IS_ERR(root)) { 843 ret = PTR_ERR(root); 844 goto out; 845 } 846 847 root->fs_info = btrfs_alloc_dummy_fs_info(); 848 if (!root->fs_info) 849 goto out; 850 851 root->fs_info->extent_root = root; 852 cache->fs_info = root->fs_info; 853 854 ret = test_extents(cache); 855 if (ret) 856 goto out; 857 ret = test_bitmaps(cache); 858 if (ret) 859 goto out; 860 ret = test_bitmaps_and_extents(cache); 861 if (ret) 862 goto out; 863 864 ret = test_steal_space_from_bitmap_to_extent(cache); 865 out: 866 btrfs_free_dummy_block_group(cache); 867 btrfs_free_dummy_root(root); 868 test_msg("Free space cache tests finished\n"); 869 return ret; 870 } 871