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