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 exten
  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 benefical, since we always prefer to allocate from
 400  * extent entries, both for clustered and non-clustered allocation requests.
 401  */
 402 static int
 403 test_steal_space_from_bitmap_to_extent(struct btrfs_block_group_cache *cache)
 404 {
 405         int ret;
 406         u64 offset;
 407         u64 max_extent_size;
 408         const struct btrfs_free_space_op test_free_space_ops = {
 409                 .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds,
 410                 .use_bitmap = test_use_bitmap,
 411         };
 412         const struct btrfs_free_space_op *orig_free_space_ops;
 413
 414         test_msg("Running space stealing from bitmap to extent\n");
 415
 416         /*
 417          * For this test, we want to ensure we end up with an extent entry
 418          * immediately adjacent to a bitmap entry, where the bitmap starts
 419          * at an offset where the extent entry ends. We keep adding and
 420          * removing free space to reach into this state, but to get there
 421          * we need to reach a point where marking new free space doesn't
 422          * result in adding new extent entries or merging the new space
 423          * with existing extent entries - the space ends up being marked
 424          * in an existing bitmap that covers the new free space range.
 425          *
 426          * To get there, we need to reach the threshold defined set at
 427          * cache->free_space_ctl->extents_thresh, which currently is
 428          * 256 extents on a x86_64 system at least, and a few other
 429          * conditions (check free_space_cache.c). Instead of making the
 430          * test much longer and complicated, use a "use_bitmap" operation
 431          * that forces use of bitmaps as soon as we have at least 1
 432          * extent entry.
 433          */
 434         orig_free_space_ops = cache->free_space_ctl->op;
 435         cache->free_space_ctl->op = &test_free_space_ops;
 436
 437         /*
 438          * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[
 439          */
 440         ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0);
 441         if (ret) {
 442                 test_msg("Couldn't add extent entry %d\n", ret);
 443                 return ret;
 444         }
 445
 446         /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */
 447         ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K,
 448                                         SZ_128M - SZ_512K, 1);
 449         if (ret) {
 450                 test_msg("Couldn't add bitmap entry %d\n", ret);
 451                 return ret;
 452         }
 453
 454         ret = check_num_extents_and_bitmaps(cache, 2, 1);
 455         if (ret)
 456                 return ret;
 457
 458         /*
 459          * Now make only the first 256Kb of the bitmap marked as free, so that
 460          * we end up with only the following ranges marked as free space:
 461          *
 462          * [128Mb - 256Kb, 128Mb - 128Kb[
 463          * [128Mb + 512Kb, 128Mb + 768Kb[
 464          */
 465         ret = btrfs_remove_free_space(cache,
 466                                       SZ_128M + 768 * SZ_1K,
 467                                       SZ_128M - 768 * SZ_1K);
 468         if (ret) {
 469                 test_msg("Failed to free part of bitmap space %d\n", ret);
 470                 return ret;
 471         }
 472
 473         /* Confirm that only those 2 ranges are marked as free. */
 474         if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) {
 475                 test_msg("Free space range missing\n");
 476                 return -ENOENT;
 477         }
 478         if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) {
 479                 test_msg("Free space range missing\n");
 480                 return -ENOENT;
 481         }
 482
 483         /*
 484          * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked
 485          * as free anymore.
 486          */
 487         if (test_check_exists(cache, SZ_128M + 768 * SZ_1K,
 488                               SZ_128M - 768 * SZ_1K)) {
 489                 test_msg("Bitmap region not removed from space cache\n");
 490                 return -EINVAL;
 491         }
 492
 493         /*
 494          * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is
 495          * covered by the bitmap, isn't marked as free.
 496          */
 497         if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) {
 498                 test_msg("Invalid bitmap region marked as free\n");
 499                 return -EINVAL;
 500         }
 501
 502         /*
 503          * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered
 504          * by the bitmap too, isn't marked as free either.
 505          */
 506         if (test_check_exists(cache, SZ_128M, SZ_256K)) {
 507                 test_msg("Invalid bitmap region marked as free\n");
 508                 return -EINVAL;
 509         }
 510
 511         /*
 512          * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But,
 513          * lets make sure the free space cache marks it as free in the bitmap,
 514          * and doesn't insert a new extent entry to represent this region.
 515          */
 516         ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K);
 517         if (ret) {
 518                 test_msg("Error adding free space: %d\n", ret);
 519                 return ret;
 520         }
 521         /* Confirm the region is marked as free. */
 522         if (!test_check_exists(cache, SZ_128M, SZ_512K)) {
 523                 test_msg("Bitmap region not marked as free\n");
 524                 return -ENOENT;
 525         }
 526
 527         /*
 528          * Confirm that no new extent entries or bitmap entries were added to
 529          * the cache after adding that free space region.
 530          */
 531         ret = check_num_extents_and_bitmaps(cache, 2, 1);
 532         if (ret)
 533                 return ret;
 534
 535         /*
 536          * Now lets add a small free space region to the right of the previous
 537          * one, which is not contiguous with it and is part of the bitmap too.
 538          * The goal is to test that the bitmap entry space stealing doesn't
 539          * steal this space region.
 540          */
 541         ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, 4096);
 542         if (ret) {
 543                 test_msg("Error adding free space: %d\n", ret);
 544                 return ret;
 545         }
 546
 547         /*
 548          * Confirm that no new extent entries or bitmap entries were added to
 549          * the cache after adding that free space region.
 550          */
 551         ret = check_num_extents_and_bitmaps(cache, 2, 1);
 552         if (ret)
 553                 return ret;
 554
 555         /*
 556          * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will
 557          * expand the range covered by the existing extent entry that represents
 558          * the free space [128Mb - 256Kb, 128Mb - 128Kb[.
 559          */
 560         ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K);
 561         if (ret) {
 562                 test_msg("Error adding free space: %d\n", ret);
 563                 return ret;
 564         }
 565         /* Confirm the region is marked as free. */
 566         if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) {
 567                 test_msg("Extent region not marked as free\n");
 568                 return -ENOENT;
 569         }
 570
 571         /*
 572          * Confirm that our extent entry didn't stole all free space from the
 573          * bitmap, because of the small 4Kb free space region.
 574          */
 575         ret = check_num_extents_and_bitmaps(cache, 2, 1);
 576         if (ret)
 577                 return ret;
 578
 579         /*
 580          * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free
 581          * space. Without stealing bitmap free space into extent entry space,
 582          * we would have all this free space represented by 2 entries in the
 583          * cache:
 584          *
 585          * extent entry covering range: [128Mb - 256Kb, 128Mb[
 586          * bitmap entry covering range: [128Mb, 128Mb + 768Kb[
 587          *
 588          * Attempting to allocate the whole free space (1Mb) would fail, because
 589          * we can't allocate from multiple entries.
 590          * With the bitmap free space stealing, we get a single extent entry
 591          * that represents the 1Mb free space, and therefore we're able to
 592          * allocate the whole free space at once.
 593          */
 594         if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) {
 595                 test_msg("Expected region not marked as free\n");
 596                 return -ENOENT;
 597         }
 598
 599         if (cache->free_space_ctl->free_space != (SZ_1M + 4096)) {
 600                 test_msg("Cache free space is not 1Mb + 4Kb\n");
 601                 return -EINVAL;
 602         }
 603
 604         offset = btrfs_find_space_for_alloc(cache,
 605                                             0, SZ_1M, 0,
 606                                             &max_extent_size);
 607         if (offset != (SZ_128M - SZ_256K)) {
 608                 test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n",
 609                          offset);
 610                 return -EINVAL;
 611         }
 612
 613         /* All that remains is a 4Kb free space region in a bitmap. Confirm. */
 614         ret = check_num_extents_and_bitmaps(cache, 1, 1);
 615         if (ret)
 616                 return ret;
 617
 618         if (cache->free_space_ctl->free_space != 4096) {
 619                 test_msg("Cache free space is not 4Kb\n");
 620                 return -EINVAL;
 621         }
 622
 623         offset = btrfs_find_space_for_alloc(cache,
 624                                             0, 4096, 0,
 625                                             &max_extent_size);
 626         if (offset != (SZ_128M + SZ_16M)) {
 627                 test_msg("Failed to allocate 4Kb from space cache, returned offset is: %llu\n",
 628                          offset);
 629                 return -EINVAL;
 630         }
 631
 632         ret = check_cache_empty(cache);
 633         if (ret)
 634                 return ret;
 635
 636         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 637
 638         /*
 639          * Now test a similar scenario, but where our extent entry is located
 640          * to the right of the bitmap entry, so that we can check that stealing
 641          * space from a bitmap to the front of an extent entry works.
 642          */
 643
 644         /*
 645          * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[
 646          */
 647         ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0);
 648         if (ret) {
 649                 test_msg("Couldn't add extent entry %d\n", ret);
 650                 return ret;
 651         }
 652
 653         /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */
 654         ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1);
 655         if (ret) {
 656                 test_msg("Couldn't add bitmap entry %d\n", ret);
 657                 return ret;
 658         }
 659
 660         ret = check_num_extents_and_bitmaps(cache, 2, 1);
 661         if (ret)
 662                 return ret;
 663
 664         /*
 665          * Now make only the last 256Kb of the bitmap marked as free, so that
 666          * we end up with only the following ranges marked as free space:
 667          *
 668          * [128Mb + 128b, 128Mb + 256Kb[
 669          * [128Mb - 768Kb, 128Mb - 512Kb[
 670          */
 671         ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K);
 672         if (ret) {
 673                 test_msg("Failed to free part of bitmap space %d\n", ret);
 674                 return ret;
 675         }
 676
 677         /* Confirm that only those 2 ranges are marked as free. */
 678         if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) {
 679                 test_msg("Free space range missing\n");
 680                 return -ENOENT;
 681         }
 682         if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) {
 683                 test_msg("Free space range missing\n");
 684                 return -ENOENT;
 685         }
 686
 687         /*
 688          * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked
 689          * as free anymore.
 690          */
 691         if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) {
 692                 test_msg("Bitmap region not removed from space cache\n");
 693                 return -EINVAL;
 694         }
 695
 696         /*
 697          * Confirm that the region [128Mb - 512Kb, 128Mb[, which is
 698          * covered by the bitmap, isn't marked as free.
 699          */
 700         if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
 701                 test_msg("Invalid bitmap region marked as free\n");
 702                 return -EINVAL;
 703         }
 704
 705         /*
 706          * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But,
 707          * lets make sure the free space cache marks it as free in the bitmap,
 708          * and doesn't insert a new extent entry to represent this region.
 709          */
 710         ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K);
 711         if (ret) {
 712                 test_msg("Error adding free space: %d\n", ret);
 713                 return ret;
 714         }
 715         /* Confirm the region is marked as free. */
 716         if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
 717                 test_msg("Bitmap region not marked as free\n");
 718                 return -ENOENT;
 719         }
 720
 721         /*
 722          * Confirm that no new extent entries or bitmap entries were added to
 723          * the cache after adding that free space region.
 724          */
 725         ret = check_num_extents_and_bitmaps(cache, 2, 1);
 726         if (ret)
 727                 return ret;
 728
 729         /*
 730          * Now lets add a small free space region to the left of the previous
 731          * one, which is not contiguous with it and is part of the bitmap too.
 732          * The goal is to test that the bitmap entry space stealing doesn't
 733          * steal this space region.
 734          */
 735         ret = btrfs_add_free_space(cache, SZ_32M, 8192);
 736         if (ret) {
 737                 test_msg("Error adding free space: %d\n", ret);
 738                 return ret;
 739         }
 740
 741         /*
 742          * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will
 743          * expand the range covered by the existing extent entry that represents
 744          * the free space [128Mb + 128Kb, 128Mb + 256Kb[.
 745          */
 746         ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K);
 747         if (ret) {
 748                 test_msg("Error adding free space: %d\n", ret);
 749                 return ret;
 750         }
 751         /* Confirm the region is marked as free. */
 752         if (!test_check_exists(cache, SZ_128M, SZ_128K)) {
 753                 test_msg("Extent region not marked as free\n");
 754                 return -ENOENT;
 755         }
 756
 757         /*
 758          * Confirm that our extent entry didn't stole all free space from the
 759          * bitmap, because of the small 8Kb free space region.
 760          */
 761         ret = check_num_extents_and_bitmaps(cache, 2, 1);
 762         if (ret)
 763                 return ret;
 764
 765         /*
 766          * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free
 767          * space. Without stealing bitmap free space into extent entry space,
 768          * we would have all this free space represented by 2 entries in the
 769          * cache:
 770          *
 771          * extent entry covering range: [128Mb, 128Mb + 256Kb[
 772          * bitmap entry covering range: [128Mb - 768Kb, 128Mb[
 773          *
 774          * Attempting to allocate the whole free space (1Mb) would fail, because
 775          * we can't allocate from multiple entries.
 776          * With the bitmap free space stealing, we get a single extent entry
 777          * that represents the 1Mb free space, and therefore we're able to
 778          * allocate the whole free space at once.
 779          */
 780         if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) {
 781                 test_msg("Expected region not marked as free\n");
 782                 return -ENOENT;
 783         }
 784
 785         if (cache->free_space_ctl->free_space != (SZ_1M + 8192)) {
 786                 test_msg("Cache free space is not 1Mb + 8Kb\n");
 787                 return -EINVAL;
 788         }
 789
 790         offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0,
 791                                             &max_extent_size);
 792         if (offset != (SZ_128M - 768 * SZ_1K)) {
 793                 test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n",
 794                          offset);
 795                 return -EINVAL;
 796         }
 797
 798         /* All that remains is a 8Kb free space region in a bitmap. Confirm. */
 799         ret = check_num_extents_and_bitmaps(cache, 1, 1);
 800         if (ret)
 801                 return ret;
 802
 803         if (cache->free_space_ctl->free_space != 8192) {
 804                 test_msg("Cache free space is not 8Kb\n");
 805                 return -EINVAL;
 806         }
 807
 808         offset = btrfs_find_space_for_alloc(cache,
 809                                             0, 8192, 0,
 810                                             &max_extent_size);
 811         if (offset != SZ_32M) {
 812                 test_msg("Failed to allocate 8Kb from space cache, returned offset is: %llu\n",
 813                          offset);
 814                 return -EINVAL;
 815         }
 816
 817         ret = check_cache_empty(cache);
 818         if (ret)
 819                 return ret;
 820
 821         cache->free_space_ctl->op = orig_free_space_ops;
 822         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 823
 824         return 0;
 825 }
 826
 827 int btrfs_test_free_space_cache(void)
 828 {
 829         struct btrfs_block_group_cache *cache;
 830         struct btrfs_root *root = NULL;
 831         int ret = -ENOMEM;
 832
 833         test_msg("Running btrfs free space cache tests\n");
 834
 835         cache = btrfs_alloc_dummy_block_group(1024 * 1024 * 1024);
 836         if (!cache) {
 837                 test_msg("Couldn't run the tests\n");
 838                 return 0;
 839         }
 840
 841         root = btrfs_alloc_dummy_root();
 842         if (IS_ERR(root)) {
 843                 ret = PTR_ERR(root);
 844                 goto out;
 845         }
 846
 847         root->fs_info = btrfs_alloc_dummy_fs_info();
 848         if (!root->fs_info)
 849                 goto out;
 850
 851         root->fs_info->extent_root = root;
 852         cache->fs_info = root->fs_info;
 853
 854         ret = test_extents(cache);
 855         if (ret)
 856                 goto out;
 857         ret = test_bitmaps(cache);
 858         if (ret)
 859                 goto out;
 860         ret = test_bitmaps_and_extents(cache);
 861         if (ret)
 862                 goto out;
 863
 864         ret = test_steal_space_from_bitmap_to_extent(cache);
 865 out:
 866         btrfs_free_dummy_block_group(cache);
 867         btrfs_free_dummy_root(root);
 868         test_msg("Free space cache tests finished\n");
 869         return ret;
 870 }