fs/btrfs/tests/free-space-tests.c

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