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