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

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