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