fs/btrfs/tests/free-space-tree-tests.c

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