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