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