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

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2015 Facebook.  All rights reserved.
   4  */
   5
   6 #include <linux/types.h>
   7 #include "btrfs-tests.h"
   8 #include "../ctree.h"
   9 #include "../disk-io.h"
  10 #include "../free-space-tree.h"
  11 #include "../transaction.h"
  12 #include "../block-group.h"
  13 #include "../accessors.h"
  14
  15 struct free_space_extent {
  16         u64 start;
  17         u64 length;
  18 };
  19
  20 static int __check_free_space_extents(struct btrfs_trans_handle *trans,
  21                                       struct btrfs_fs_info *fs_info,
  22                                       struct btrfs_block_group *cache,
  23                                       struct btrfs_path *path,
  24                                       const struct free_space_extent * const extents,
  25                                       unsigned int num_extents)
  26 {
  27         struct btrfs_free_space_info *info;
  28         struct btrfs_key key;
  29         int prev_bit = 0, bit;
  30         u64 extent_start = 0, offset, end;
  31         u32 flags, extent_count;
  32         unsigned int i;
  33         int ret;
  34
  35         info = search_free_space_info(trans, cache, path, 0);
  36         if (IS_ERR(info)) {
  37                 test_err("could not find free space info");
  38                 ret = PTR_ERR(info);
  39                 goto out;
  40         }
  41         flags = btrfs_free_space_flags(path->nodes[0], info);
  42         extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
  43
  44         if (extent_count != num_extents) {
  45                 test_err("extent count is wrong");
  46                 ret = -EINVAL;
  47                 goto out;
  48         }
  49         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
  50                 if (path->slots[0] != 0)
  51                         goto invalid;
  52                 end = cache->start + cache->length;
  53                 i = 0;
  54                 while (++path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
  55                         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
  56                         if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY)
  57                                 goto invalid;
  58                         offset = key.objectid;
  59                         while (offset < key.objectid + key.offset) {
  60                                 bit = free_space_test_bit(cache, path, offset);
  61                                 if (prev_bit == 0 && bit == 1) {
  62                                         extent_start = offset;
  63                                 } else if (prev_bit == 1 && bit == 0) {
  64                                         if (i >= num_extents ||
  65                                             extent_start != extents[i].start ||
  66                                             offset - extent_start != extents[i].length)
  67                                                 goto invalid;
  68                                         i++;
  69                                 }
  70                                 prev_bit = bit;
  71                                 offset += fs_info->sectorsize;
  72                         }
  73                 }
  74                 if (prev_bit == 1) {
  75                         if (i >= num_extents ||
  76                             extent_start != extents[i].start ||
  77                             end - extent_start != extents[i].length)
  78                                 goto invalid;
  79                         i++;
  80                 }
  81                 if (i != num_extents)
  82                         goto invalid;
  83         } else {
  84                 if (btrfs_header_nritems(path->nodes[0]) != num_extents + 1 ||
  85                     path->slots[0] != 0)
  86                         goto invalid;
  87                 for (i = 0; i < num_extents; i++) {
  88                         path->slots[0]++;
  89                         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
  90                         if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY ||
  91                             key.objectid != extents[i].start ||
  92                             key.offset != extents[i].length)
  93                                 goto invalid;
  94                 }
  95         }
  96
  97         ret = 0;
  98 out:
  99         btrfs_release_path(path);
 100         return ret;
 101 invalid:
 102         test_err("free space tree is invalid");
 103         ret = -EINVAL;
 104         goto out;
 105 }
 106
 107 static int check_free_space_extents(struct btrfs_trans_handle *trans,
 108                                     struct btrfs_fs_info *fs_info,
 109                                     struct btrfs_block_group *cache,
 110                                     struct btrfs_path *path,
 111                                     const struct free_space_extent * const extents,
 112                                     unsigned int num_extents)
 113 {
 114         struct btrfs_free_space_info *info;
 115         u32 flags;
 116         int ret;
 117
 118         info = search_free_space_info(trans, cache, path, 0);
 119         if (IS_ERR(info)) {
 120                 test_err("could not find free space info");
 121                 btrfs_release_path(path);
 122                 return PTR_ERR(info);
 123         }
 124         flags = btrfs_free_space_flags(path->nodes[0], info);
 125         btrfs_release_path(path);
 126
 127         ret = __check_free_space_extents(trans, fs_info, cache, path, extents,
 128                                          num_extents);
 129         if (ret)
 130                 return ret;
 131
 132         /* Flip it to the other format and check that for good measure. */
 133         if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
 134                 ret = convert_free_space_to_extents(trans, cache, path);
 135                 if (ret) {
 136                         test_err("could not convert to extents");
 137                         return ret;
 138                 }
 139         } else {
 140                 ret = convert_free_space_to_bitmaps(trans, cache, path);
 141                 if (ret) {
 142                         test_err("could not convert to bitmaps");
 143                         return ret;
 144                 }
 145         }
 146         return __check_free_space_extents(trans, fs_info, cache, path, extents,
 147                                           num_extents);
 148 }
 149
 150 static int test_empty_block_group(struct btrfs_trans_handle *trans,
 151                                   struct btrfs_fs_info *fs_info,
 152                                   struct btrfs_block_group *cache,
 153                                   struct btrfs_path *path,
 154                                   u32 alignment)
 155 {
 156         const struct free_space_extent extents[] = {
 157                 {cache->start, cache->length},
 158         };
 159
 160         return check_free_space_extents(trans, fs_info, cache, path,
 161                                         extents, ARRAY_SIZE(extents));
 162 }
 163
 164 static int test_remove_all(struct btrfs_trans_handle *trans,
 165                            struct btrfs_fs_info *fs_info,
 166                            struct btrfs_block_group *cache,
 167                            struct btrfs_path *path,
 168                            u32 alignment)
 169 {
 170         const struct free_space_extent extents[] = {};
 171         int ret;
 172
 173         ret = __remove_from_free_space_tree(trans, cache, path,
 174                                             cache->start,
 175                                             cache->length);
 176         if (ret) {
 177                 test_err("could not remove free space");
 178                 return ret;
 179         }
 180
 181         return check_free_space_extents(trans, fs_info, cache, path,
 182                                         extents, ARRAY_SIZE(extents));
 183 }
 184
 185 static int test_remove_beginning(struct btrfs_trans_handle *trans,
 186                                  struct btrfs_fs_info *fs_info,
 187                                  struct btrfs_block_group *cache,
 188                                  struct btrfs_path *path,
 189                                  u32 alignment)
 190 {
 191         const struct free_space_extent extents[] = {
 192                 {cache->start + alignment, cache->length - alignment},
 193         };
 194         int ret;
 195
 196         ret = __remove_from_free_space_tree(trans, cache, path,
 197                                             cache->start, alignment);
 198         if (ret) {
 199                 test_err("could not remove free space");
 200                 return ret;
 201         }
 202
 203         return check_free_space_extents(trans, fs_info, cache, path,
 204                                         extents, ARRAY_SIZE(extents));
 205
 206 }
 207
 208 static int test_remove_end(struct btrfs_trans_handle *trans,
 209                            struct btrfs_fs_info *fs_info,
 210                            struct btrfs_block_group *cache,
 211                            struct btrfs_path *path,
 212                            u32 alignment)
 213 {
 214         const struct free_space_extent extents[] = {
 215                 {cache->start, cache->length - alignment},
 216         };
 217         int ret;
 218
 219         ret = __remove_from_free_space_tree(trans, cache, path,
 220                                     cache->start + cache->length - alignment,
 221                                     alignment);
 222         if (ret) {
 223                 test_err("could not remove free space");
 224                 return ret;
 225         }
 226
 227         return check_free_space_extents(trans, fs_info, cache, path,
 228                                         extents, ARRAY_SIZE(extents));
 229 }
 230
 231 static int test_remove_middle(struct btrfs_trans_handle *trans,
 232                               struct btrfs_fs_info *fs_info,
 233                               struct btrfs_block_group *cache,
 234                               struct btrfs_path *path,
 235                               u32 alignment)
 236 {
 237         const struct free_space_extent extents[] = {
 238                 {cache->start, alignment},
 239                 {cache->start + 2 * alignment, cache->length - 2 * alignment},
 240         };
 241         int ret;
 242
 243         ret = __remove_from_free_space_tree(trans, cache, path,
 244                                             cache->start + alignment,
 245                                             alignment);
 246         if (ret) {
 247                 test_err("could not remove free space");
 248                 return ret;
 249         }
 250
 251         return check_free_space_extents(trans, fs_info, cache, path,
 252                                         extents, ARRAY_SIZE(extents));
 253 }
 254
 255 static int test_merge_left(struct btrfs_trans_handle *trans,
 256                            struct btrfs_fs_info *fs_info,
 257                            struct btrfs_block_group *cache,
 258                            struct btrfs_path *path,
 259                            u32 alignment)
 260 {
 261         const struct free_space_extent extents[] = {
 262                 {cache->start, 2 * alignment},
 263         };
 264         int ret;
 265
 266         ret = __remove_from_free_space_tree(trans, cache, path,
 267                                             cache->start, cache->length);
 268         if (ret) {
 269                 test_err("could not remove free space");
 270                 return ret;
 271         }
 272
 273         ret = __add_to_free_space_tree(trans, cache, path, cache->start,
 274                                        alignment);
 275         if (ret) {
 276                 test_err("could not add free space");
 277                 return ret;
 278         }
 279
 280         ret = __add_to_free_space_tree(trans, cache, path,
 281                                        cache->start + alignment,
 282                                        alignment);
 283         if (ret) {
 284                 test_err("could not add free space");
 285                 return ret;
 286         }
 287
 288         return check_free_space_extents(trans, fs_info, cache, path,
 289                                         extents, ARRAY_SIZE(extents));
 290 }
 291
 292 static int test_merge_right(struct btrfs_trans_handle *trans,
 293                            struct btrfs_fs_info *fs_info,
 294                            struct btrfs_block_group *cache,
 295                            struct btrfs_path *path,
 296                            u32 alignment)
 297 {
 298         const struct free_space_extent extents[] = {
 299                 {cache->start + alignment, 2 * alignment},
 300         };
 301         int ret;
 302
 303         ret = __remove_from_free_space_tree(trans, cache, path,
 304                                             cache->start, cache->length);
 305         if (ret) {
 306                 test_err("could not remove free space");
 307                 return ret;
 308         }
 309
 310         ret = __add_to_free_space_tree(trans, cache, path,
 311                                        cache->start + 2 * alignment,
 312                                        alignment);
 313         if (ret) {
 314                 test_err("could not add free space");
 315                 return ret;
 316         }
 317
 318         ret = __add_to_free_space_tree(trans, cache, path,
 319                                        cache->start + alignment,
 320                                        alignment);
 321         if (ret) {
 322                 test_err("could not add free space");
 323                 return ret;
 324         }
 325
 326         return check_free_space_extents(trans, fs_info, cache, path,
 327                                         extents, ARRAY_SIZE(extents));
 328 }
 329
 330 static int test_merge_both(struct btrfs_trans_handle *trans,
 331                            struct btrfs_fs_info *fs_info,
 332                            struct btrfs_block_group *cache,
 333                            struct btrfs_path *path,
 334                            u32 alignment)
 335 {
 336         const struct free_space_extent extents[] = {
 337                 {cache->start, 3 * alignment},
 338         };
 339         int ret;
 340
 341         ret = __remove_from_free_space_tree(trans, cache, path,
 342                                             cache->start, cache->length);
 343         if (ret) {
 344                 test_err("could not remove free space");
 345                 return ret;
 346         }
 347
 348         ret = __add_to_free_space_tree(trans, cache, path, cache->start,
 349                                        alignment);
 350         if (ret) {
 351                 test_err("could not add free space");
 352                 return ret;
 353         }
 354
 355         ret = __add_to_free_space_tree(trans, cache, path,
 356                                        cache->start + 2 * alignment, alignment);
 357         if (ret) {
 358                 test_err("could not add free space");
 359                 return ret;
 360         }
 361
 362         ret = __add_to_free_space_tree(trans, cache, path,
 363                                        cache->start + alignment, alignment);
 364         if (ret) {
 365                 test_err("could not add free space");
 366                 return ret;
 367         }
 368
 369         return check_free_space_extents(trans, fs_info, cache, path,
 370                                         extents, ARRAY_SIZE(extents));
 371 }
 372
 373 static int test_merge_none(struct btrfs_trans_handle *trans,
 374                            struct btrfs_fs_info *fs_info,
 375                            struct btrfs_block_group *cache,
 376                            struct btrfs_path *path,
 377                            u32 alignment)
 378 {
 379         const struct free_space_extent extents[] = {
 380                 {cache->start, alignment},
 381                 {cache->start + 2 * alignment, alignment},
 382                 {cache->start + 4 * alignment, alignment},
 383         };
 384         int ret;
 385
 386         ret = __remove_from_free_space_tree(trans, cache, path,
 387                                             cache->start, cache->length);
 388         if (ret) {
 389                 test_err("could not remove free space");
 390                 return ret;
 391         }
 392
 393         ret = __add_to_free_space_tree(trans, cache, path, cache->start,
 394                                        alignment);
 395         if (ret) {
 396                 test_err("could not add free space");
 397                 return ret;
 398         }
 399
 400         ret = __add_to_free_space_tree(trans, cache, path,
 401                                        cache->start + 4 * alignment, alignment);
 402         if (ret) {
 403                 test_err("could not add free space");
 404                 return ret;
 405         }
 406
 407         ret = __add_to_free_space_tree(trans, cache, path,
 408                                        cache->start + 2 * alignment, alignment);
 409         if (ret) {
 410                 test_err("could not add free space");
 411                 return ret;
 412         }
 413
 414         return check_free_space_extents(trans, fs_info, cache, path,
 415                                         extents, ARRAY_SIZE(extents));
 416 }
 417
 418 typedef int (*test_func_t)(struct btrfs_trans_handle *,
 419                            struct btrfs_fs_info *,
 420                            struct btrfs_block_group *,
 421                            struct btrfs_path *,
 422                            u32 alignment);
 423
 424 static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize,
 425                     u32 nodesize, u32 alignment)
 426 {
 427         struct btrfs_fs_info *fs_info;
 428         struct btrfs_root *root = NULL;
 429         struct btrfs_block_group *cache = NULL;
 430         struct btrfs_trans_handle trans;
 431         struct btrfs_path *path = NULL;
 432         int ret;
 433
 434         fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
 435         if (!fs_info) {
 436                 test_std_err(TEST_ALLOC_FS_INFO);
 437                 ret = -ENOMEM;
 438                 goto out;
 439         }
 440
 441         root = btrfs_alloc_dummy_root(fs_info);
 442         if (IS_ERR(root)) {
 443                 test_std_err(TEST_ALLOC_ROOT);
 444                 ret = PTR_ERR(root);
 445                 goto out;
 446         }
 447
 448         btrfs_set_super_compat_ro_flags(root->fs_info->super_copy,
 449                                         BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);
 450         root->root_key.objectid = BTRFS_FREE_SPACE_TREE_OBJECTID;
 451         root->root_key.type = BTRFS_ROOT_ITEM_KEY;
 452         root->root_key.offset = 0;
 453         btrfs_global_root_insert(root);
 454         root->fs_info->tree_root = root;
 455
 456         root->node = alloc_test_extent_buffer(root->fs_info, nodesize);
 457         if (IS_ERR(root->node)) {
 458                 test_std_err(TEST_ALLOC_EXTENT_BUFFER);
 459                 ret = PTR_ERR(root->node);
 460                 goto out;
 461         }
 462         btrfs_set_header_level(root->node, 0);
 463         btrfs_set_header_nritems(root->node, 0);
 464         root->alloc_bytenr += 2 * nodesize;
 465
 466         cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment);
 467         if (!cache) {
 468                 test_std_err(TEST_ALLOC_BLOCK_GROUP);
 469                 ret = -ENOMEM;
 470                 goto out;
 471         }
 472         cache->bitmap_low_thresh = 0;
 473         cache->bitmap_high_thresh = (u32)-1;
 474         set_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &cache->runtime_flags);
 475         cache->fs_info = root->fs_info;
 476
 477         btrfs_init_dummy_trans(&trans, root->fs_info);
 478
 479         path = btrfs_alloc_path();
 480         if (!path) {
 481                 test_std_err(TEST_ALLOC_ROOT);
 482                 ret = -ENOMEM;
 483                 goto out;
 484         }
 485
 486         ret = add_block_group_free_space(&trans, cache);
 487         if (ret) {
 488                 test_err("could not add block group free space");
 489                 goto out;
 490         }
 491
 492         if (bitmaps) {
 493                 ret = convert_free_space_to_bitmaps(&trans, cache, path);
 494                 if (ret) {
 495                         test_err("could not convert block group to bitmaps");
 496                         goto out;
 497                 }
 498         }
 499
 500         ret = test_func(&trans, root->fs_info, cache, path, alignment);
 501         if (ret)
 502                 goto out;
 503
 504         ret = remove_block_group_free_space(&trans, cache);
 505         if (ret) {
 506                 test_err("could not remove block group free space");
 507                 goto out;
 508         }
 509
 510         if (btrfs_header_nritems(root->node) != 0) {
 511                 test_err("free space tree has leftover items");
 512                 ret = -EINVAL;
 513                 goto out;
 514         }
 515
 516         ret = 0;
 517 out:
 518         btrfs_free_path(path);
 519         btrfs_free_dummy_block_group(cache);
 520         btrfs_free_dummy_root(root);
 521         btrfs_free_dummy_fs_info(fs_info);
 522         return ret;
 523 }
 524
 525 static int run_test_both_formats(test_func_t test_func, u32 sectorsize,
 526                                  u32 nodesize, u32 alignment)
 527 {
 528         int test_ret = 0;
 529         int ret;
 530
 531         ret = run_test(test_func, 0, sectorsize, nodesize, alignment);
 532         if (ret) {
 533                 test_err(
 534         "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u",
 535                          test_func, sectorsize, nodesize, alignment);
 536                 test_ret = ret;
 537         }
 538
 539         ret = run_test(test_func, 1, sectorsize, nodesize, alignment);
 540         if (ret) {
 541                 test_err(
 542         "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u",
 543                          test_func, sectorsize, nodesize, alignment);
 544                 test_ret = ret;
 545         }
 546
 547         return test_ret;
 548 }
 549
 550 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize)
 551 {
 552         test_func_t tests[] = {
 553                 test_empty_block_group,
 554                 test_remove_all,
 555                 test_remove_beginning,
 556                 test_remove_end,
 557                 test_remove_middle,
 558                 test_merge_left,
 559                 test_merge_right,
 560                 test_merge_both,
 561                 test_merge_none,
 562         };
 563         u32 bitmap_alignment;
 564         int test_ret = 0;
 565         int i;
 566
 567         /*
 568          * Align some operations to a page to flush out bugs in the extent
 569          * buffer bitmap handling of highmem.
 570          */
 571         bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE;
 572
 573         test_msg("running free space tree tests");
 574         for (i = 0; i < ARRAY_SIZE(tests); i++) {
 575                 int ret;
 576
 577                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
 578                                             sectorsize);
 579                 if (ret)
 580                         test_ret = ret;
 581
 582                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
 583                                             bitmap_alignment);
 584                 if (ret)
 585                         test_ret = ret;
 586         }
 587
 588         return test_ret;
 589 }