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