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