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                                                 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,
 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,
 154                                   struct btrfs_path *path,
 155                                   u32 alignment)
 156 {
 157         const struct free_space_extent extents[] = {
 158                 {cache->start, cache->length},
 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,
 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->start,
 176                                             cache->length);
 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,
 189                                  struct btrfs_path *path,
 190                                  u32 alignment)
 191 {
 192         const struct free_space_extent extents[] = {
 193                 {cache->start + alignment, cache->length - alignment},
 194         };
 195         int ret;
 196
 197         ret = __remove_from_free_space_tree(trans, cache, path,
 198                                             cache->start, alignment);
 199         if (ret) {
 200                 test_err("could not remove free space");
 201                 return ret;
 202         }
 203
 204         return check_free_space_extents(trans, fs_info, cache, path,
 205                                         extents, ARRAY_SIZE(extents));
 206
 207 }
 208
 209 static int test_remove_end(struct btrfs_trans_handle *trans,
 210                            struct btrfs_fs_info *fs_info,
 211                            struct btrfs_block_group *cache,
 212                            struct btrfs_path *path,
 213                            u32 alignment)
 214 {
 215         const struct free_space_extent extents[] = {
 216                 {cache->start, cache->length - alignment},
 217         };
 218         int ret;
 219
 220         ret = __remove_from_free_space_tree(trans, cache, path,
 221                                     cache->start + cache->length - alignment,
 222                                     alignment);
 223         if (ret) {
 224                 test_err("could not remove free space");
 225                 return ret;
 226         }
 227
 228         return check_free_space_extents(trans, fs_info, cache, path,
 229                                         extents, ARRAY_SIZE(extents));
 230 }
 231
 232 static int test_remove_middle(struct btrfs_trans_handle *trans,
 233                               struct btrfs_fs_info *fs_info,
 234                               struct btrfs_block_group *cache,
 235                               struct btrfs_path *path,
 236                               u32 alignment)
 237 {
 238         const struct free_space_extent extents[] = {
 239                 {cache->start, alignment},
 240                 {cache->start + 2 * alignment, cache->length - 2 * alignment},
 241         };
 242         int ret;
 243
 244         ret = __remove_from_free_space_tree(trans, cache, path,
 245                                             cache->start + alignment,
 246                                             alignment);
 247         if (ret) {
 248                 test_err("could not remove free space");
 249                 return ret;
 250         }
 251
 252         return check_free_space_extents(trans, fs_info, cache, path,
 253                                         extents, ARRAY_SIZE(extents));
 254 }
 255
 256 static int test_merge_left(struct btrfs_trans_handle *trans,
 257                            struct btrfs_fs_info *fs_info,
 258                            struct btrfs_block_group *cache,
 259                            struct btrfs_path *path,
 260                            u32 alignment)
 261 {
 262         const struct free_space_extent extents[] = {
 263                 {cache->start, 2 * alignment},
 264         };
 265         int ret;
 266
 267         ret = __remove_from_free_space_tree(trans, cache, path,
 268                                             cache->start, cache->length);
 269         if (ret) {
 270                 test_err("could not remove free space");
 271                 return ret;
 272         }
 273
 274         ret = __add_to_free_space_tree(trans, cache, path, cache->start,
 275                                        alignment);
 276         if (ret) {
 277                 test_err("could not add free space");
 278                 return ret;
 279         }
 280
 281         ret = __add_to_free_space_tree(trans, cache, path,
 282                                        cache->start + alignment,
 283                                        alignment);
 284         if (ret) {
 285                 test_err("could not add free space");
 286                 return ret;
 287         }
 288
 289         return check_free_space_extents(trans, fs_info, cache, path,
 290                                         extents, ARRAY_SIZE(extents));
 291 }
 292
 293 static int test_merge_right(struct btrfs_trans_handle *trans,
 294                            struct btrfs_fs_info *fs_info,
 295                            struct btrfs_block_group *cache,
 296                            struct btrfs_path *path,
 297                            u32 alignment)
 298 {
 299         const struct free_space_extent extents[] = {
 300                 {cache->start + alignment, 2 * alignment},
 301         };
 302         int ret;
 303
 304         ret = __remove_from_free_space_tree(trans, cache, path,
 305                                             cache->start, cache->length);
 306         if (ret) {
 307                 test_err("could not remove free space");
 308                 return ret;
 309         }
 310
 311         ret = __add_to_free_space_tree(trans, cache, path,
 312                                        cache->start + 2 * alignment,
 313                                        alignment);
 314         if (ret) {
 315                 test_err("could not add free space");
 316                 return ret;
 317         }
 318
 319         ret = __add_to_free_space_tree(trans, cache, path,
 320                                        cache->start + alignment,
 321                                        alignment);
 322         if (ret) {
 323                 test_err("could not add free space");
 324                 return ret;
 325         }
 326
 327         return check_free_space_extents(trans, fs_info, cache, path,
 328                                         extents, ARRAY_SIZE(extents));
 329 }
 330
 331 static int test_merge_both(struct btrfs_trans_handle *trans,
 332                            struct btrfs_fs_info *fs_info,
 333                            struct btrfs_block_group *cache,
 334                            struct btrfs_path *path,
 335                            u32 alignment)
 336 {
 337         const struct free_space_extent extents[] = {
 338                 {cache->start, 3 * alignment},
 339         };
 340         int ret;
 341
 342         ret = __remove_from_free_space_tree(trans, cache, path,
 343                                             cache->start, cache->length);
 344         if (ret) {
 345                 test_err("could not remove free space");
 346                 return ret;
 347         }
 348
 349         ret = __add_to_free_space_tree(trans, cache, path, cache->start,
 350                                        alignment);
 351         if (ret) {
 352                 test_err("could not add free space");
 353                 return ret;
 354         }
 355
 356         ret = __add_to_free_space_tree(trans, cache, path,
 357                                        cache->start + 2 * alignment, alignment);
 358         if (ret) {
 359                 test_err("could not add free space");
 360                 return ret;
 361         }
 362
 363         ret = __add_to_free_space_tree(trans, cache, path,
 364                                        cache->start + alignment, alignment);
 365         if (ret) {
 366                 test_err("could not add free space");
 367                 return ret;
 368         }
 369
 370         return check_free_space_extents(trans, fs_info, cache, path,
 371                                         extents, ARRAY_SIZE(extents));
 372 }
 373
 374 static int test_merge_none(struct btrfs_trans_handle *trans,
 375                            struct btrfs_fs_info *fs_info,
 376                            struct btrfs_block_group *cache,
 377                            struct btrfs_path *path,
 378                            u32 alignment)
 379 {
 380         const struct free_space_extent extents[] = {
 381                 {cache->start, alignment},
 382                 {cache->start + 2 * alignment, alignment},
 383                 {cache->start + 4 * alignment, alignment},
 384         };
 385         int ret;
 386
 387         ret = __remove_from_free_space_tree(trans, cache, path,
 388                                             cache->start, cache->length);
 389         if (ret) {
 390                 test_err("could not remove free space");
 391                 return ret;
 392         }
 393
 394         ret = __add_to_free_space_tree(trans, cache, path, cache->start,
 395                                        alignment);
 396         if (ret) {
 397                 test_err("could not add free space");
 398                 return ret;
 399         }
 400
 401         ret = __add_to_free_space_tree(trans, cache, path,
 402                                        cache->start + 4 * alignment, alignment);
 403         if (ret) {
 404                 test_err("could not add free space");
 405                 return ret;
 406         }
 407
 408         ret = __add_to_free_space_tree(trans, cache, path,
 409                                        cache->start + 2 * alignment, alignment);
 410         if (ret) {
 411                 test_err("could not add free space");
 412                 return ret;
 413         }
 414
 415         return check_free_space_extents(trans, fs_info, cache, path,
 416                                         extents, ARRAY_SIZE(extents));
 417 }
 418
 419 typedef int (*test_func_t)(struct btrfs_trans_handle *,
 420                            struct btrfs_fs_info *,
 421                            struct btrfs_block_group *,
 422                            struct btrfs_path *,
 423                            u32 alignment);
 424
 425 static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize,
 426                     u32 nodesize, u32 alignment)
 427 {
 428         struct btrfs_fs_info *fs_info;
 429         struct btrfs_root *root = NULL;
 430         struct btrfs_block_group *cache = NULL;
 431         struct btrfs_trans_handle trans;
 432         struct btrfs_path *path = NULL;
 433         int ret;
 434
 435         fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
 436         if (!fs_info) {
 437                 test_std_err(TEST_ALLOC_FS_INFO);
 438                 ret = -ENOMEM;
 439                 goto out;
 440         }
 441
 442         root = btrfs_alloc_dummy_root(fs_info);
 443         if (IS_ERR(root)) {
 444                 test_std_err(TEST_ALLOC_ROOT);
 445                 ret = PTR_ERR(root);
 446                 goto out;
 447         }
 448
 449         btrfs_set_super_compat_ro_flags(root->fs_info->super_copy,
 450                                         BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);
 451         root->fs_info->free_space_root = root;
 452         root->fs_info->tree_root = root;
 453
 454         root->node = alloc_test_extent_buffer(root->fs_info, nodesize);
 455         if (IS_ERR(root->node)) {
 456                 test_std_err(TEST_ALLOC_EXTENT_BUFFER);
 457                 ret = PTR_ERR(root->node);
 458                 goto out;
 459         }
 460         btrfs_set_header_level(root->node, 0);
 461         btrfs_set_header_nritems(root->node, 0);
 462         root->alloc_bytenr += 2 * nodesize;
 463
 464         cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment);
 465         if (!cache) {
 466                 test_std_err(TEST_ALLOC_BLOCK_GROUP);
 467                 ret = -ENOMEM;
 468                 goto out;
 469         }
 470         cache->bitmap_low_thresh = 0;
 471         cache->bitmap_high_thresh = (u32)-1;
 472         cache->needs_free_space = 1;
 473         cache->fs_info = root->fs_info;
 474
 475         btrfs_init_dummy_trans(&trans, root->fs_info);
 476
 477         path = btrfs_alloc_path();
 478         if (!path) {
 479                 test_std_err(TEST_ALLOC_ROOT);
 480                 ret = -ENOMEM;
 481                 goto out;
 482         }
 483
 484         ret = add_block_group_free_space(&trans, cache);
 485         if (ret) {
 486                 test_err("could not add block group free space");
 487                 goto out;
 488         }
 489
 490         if (bitmaps) {
 491                 ret = convert_free_space_to_bitmaps(&trans, cache, path);
 492                 if (ret) {
 493                         test_err("could not convert block group to bitmaps");
 494                         goto out;
 495                 }
 496         }
 497
 498         ret = test_func(&trans, root->fs_info, cache, path, alignment);
 499         if (ret)
 500                 goto out;
 501
 502         ret = remove_block_group_free_space(&trans, cache);
 503         if (ret) {
 504                 test_err("could not remove block group free space");
 505                 goto out;
 506         }
 507
 508         if (btrfs_header_nritems(root->node) != 0) {
 509                 test_err("free space tree has leftover items");
 510                 ret = -EINVAL;
 511                 goto out;
 512         }
 513
 514         ret = 0;
 515 out:
 516         btrfs_free_path(path);
 517         btrfs_free_dummy_block_group(cache);
 518         btrfs_free_dummy_root(root);
 519         btrfs_free_dummy_fs_info(fs_info);
 520         return ret;
 521 }
 522
 523 static int run_test_both_formats(test_func_t test_func, u32 sectorsize,
 524                                  u32 nodesize, u32 alignment)
 525 {
 526         int test_ret = 0;
 527         int ret;
 528
 529         ret = run_test(test_func, 0, sectorsize, nodesize, alignment);
 530         if (ret) {
 531                 test_err(
 532         "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u",
 533                          test_func, sectorsize, nodesize, alignment);
 534                 test_ret = ret;
 535         }
 536
 537         ret = run_test(test_func, 1, sectorsize, nodesize, alignment);
 538         if (ret) {
 539                 test_err(
 540         "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u",
 541                          test_func, sectorsize, nodesize, alignment);
 542                 test_ret = ret;
 543         }
 544
 545         return test_ret;
 546 }
 547
 548 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize)
 549 {
 550         test_func_t tests[] = {
 551                 test_empty_block_group,
 552                 test_remove_all,
 553                 test_remove_beginning,
 554                 test_remove_end,
 555                 test_remove_middle,
 556                 test_merge_left,
 557                 test_merge_right,
 558                 test_merge_both,
 559                 test_merge_none,
 560         };
 561         u32 bitmap_alignment;
 562         int test_ret = 0;
 563         int i;
 564
 565         /*
 566          * Align some operations to a page to flush out bugs in the extent
 567          * buffer bitmap handling of highmem.
 568          */
 569         bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE;
 570
 571         test_msg("running free space tree tests");
 572         for (i = 0; i < ARRAY_SIZE(tests); i++) {
 573                 int ret;
 574
 575                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
 576                                             sectorsize);
 577                 if (ret)
 578                         test_ret = ret;
 579
 580                 ret = run_test_both_formats(tests[i], sectorsize, nodesize,
 581                                             bitmap_alignment);
 582                 if (ret)
 583                         test_ret = ret;
 584         }
 585
 586         return test_ret;
 587 }