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