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->root_key.objectid = BTRFS_FREE_SPACE_TREE_OBJECTID;
 450         root->root_key.type = BTRFS_ROOT_ITEM_KEY;
 451         root->root_key.offset = 0;
 452         btrfs_global_root_insert(root);
 453         root->fs_info->tree_root = root;
 454
 455         root->node = alloc_test_extent_buffer(root->fs_info, nodesize);
 456         if (IS_ERR(root->node)) {
 457                 test_std_err(TEST_ALLOC_EXTENT_BUFFER);
 458                 ret = PTR_ERR(root->node);
 459                 goto out;
 460         }
 461         btrfs_set_header_level(root->node, 0);
 462         btrfs_set_header_nritems(root->node, 0);
 463         root->alloc_bytenr += 2 * nodesize;
 464
 465         cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment);
 466         if (!cache) {
 467                 test_std_err(TEST_ALLOC_BLOCK_GROUP);
 468                 ret = -ENOMEM;
 469                 goto out;
 470         }
 471         cache->bitmap_low_thresh = 0;
 472         cache->bitmap_high_thresh = (u32)-1;
 473         set_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &cache->runtime_flags);
 474         cache->fs_info = root->fs_info;
 475
 476         btrfs_init_dummy_trans(&trans, root->fs_info);
 477
 478         path = btrfs_alloc_path();
 479         if (!path) {
 480                 test_std_err(TEST_ALLOC_ROOT);
 481                 ret = -ENOMEM;
 482                 goto out;
 483         }
 484
 485         ret = add_block_group_free_space(&trans, cache);
 486         if (ret) {
 487                 test_err("could not add block group free space");
 488                 goto out;
 489         }
 490
 491         if (bitmaps) {
 492                 ret = convert_free_space_to_bitmaps(&trans, cache, path);
 493                 if (ret) {
 494                         test_err("could not convert block group to bitmaps");
 495                         goto out;
 496                 }
 497         }
 498
 499         ret = test_func(&trans, root->fs_info, cache, path, alignment);
 500         if (ret)
 501                 goto out;
 502
 503         ret = remove_block_group_free_space(&trans, cache);
 504         if (ret) {
 505                 test_err("could not remove block group free space");
 506                 goto out;
 507         }
 508
 509         if (btrfs_header_nritems(root->node) != 0) {
 510                 test_err("free space tree has leftover items");
 511                 ret = -EINVAL;
 512                 goto out;
 513         }
 514
 515         ret = 0;
 516 out:
 517         btrfs_free_path(path);
 518         btrfs_free_dummy_block_group(cache);
 519         btrfs_free_dummy_root(root);
 520         btrfs_free_dummy_fs_info(fs_info);
 521         return ret;
 522 }
 523
 524 static int run_test_both_formats(test_func_t test_func, u32 sectorsize,
 525                                  u32 nodesize, u32 alignment)
 526 {
 527         int test_ret = 0;
 528         int ret;
 529
 530         ret = run_test(test_func, 0, sectorsize, nodesize, alignment);
 531         if (ret) {
 532                 test_err(
 533         "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u",
 534                          test_func, sectorsize, nodesize, alignment);
 535                 test_ret = ret;
 536         }
 537
 538         ret = run_test(test_func, 1, sectorsize, nodesize, alignment);
 539         if (ret) {
 540                 test_err(
 541         "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u",
 542                          test_func, sectorsize, nodesize, alignment);
 543                 test_ret = ret;
 544         }
 545
 546         return test_ret;
 547 }
 548
 549 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize)
 550 {
 551         test_func_t tests[] = {
 552                 test_empty_block_group,
 553                 test_remove_all,
 554                 test_remove_beginning,
 555                 test_remove_end,
 556                 test_remove_middle,
 557                 test_merge_left,
 558                 test_merge_right,
 559                 test_merge_both,
 560                 test_merge_none,
 561         };
 562         u32 bitmap_alignment;
 563         int test_ret = 0;
 564         int i;
 565
 566         /*
 567          * Align some operations to a page to flush out bugs in the extent
 568          * buffer bitmap handling of highmem.
 569          */
 570         bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE;
 571
 572         test_msg("running free space tree tests");
 573         for (i = 0; i < ARRAY_SIZE(tests); i++) {
 574                 int ret;
 575
 576                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
 577                                             sectorsize);
 578                 if (ret)
 579                         test_ret = ret;
 580
 581                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
 582                                             bitmap_alignment);
 583                 if (ret)
 584                         test_ret = ret;
 585         }
 586
 587         return test_ret;
 588 }