Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (C) 2015 Facebook.  All rights reserved.
0004  */
0005 
0006 #include <linux/types.h>
0007 #include "btrfs-tests.h"
0008 #include "../ctree.h"
0009 #include "../disk-io.h"
0010 #include "../free-space-tree.h"
0011 #include "../transaction.h"
0012 #include "../block-group.h"
0013 
0014 struct free_space_extent {
0015     u64 start;
0016     u64 length;
0017 };
0018 
0019 static int __check_free_space_extents(struct btrfs_trans_handle *trans,
0020                       struct btrfs_fs_info *fs_info,
0021                       struct btrfs_block_group *cache,
0022                       struct btrfs_path *path,
0023                       const struct free_space_extent * const extents,
0024                       unsigned int num_extents)
0025 {
0026     struct btrfs_free_space_info *info;
0027     struct btrfs_key key;
0028     int prev_bit = 0, bit;
0029     u64 extent_start = 0, offset, end;
0030     u32 flags, extent_count;
0031     unsigned int i;
0032     int ret;
0033 
0034     info = search_free_space_info(trans, cache, path, 0);
0035     if (IS_ERR(info)) {
0036         test_err("could not find free space info");
0037         ret = PTR_ERR(info);
0038         goto out;
0039     }
0040     flags = btrfs_free_space_flags(path->nodes[0], info);
0041     extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
0042 
0043     if (extent_count != num_extents) {
0044         test_err("extent count is wrong");
0045         ret = -EINVAL;
0046         goto out;
0047     }
0048     if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
0049         if (path->slots[0] != 0)
0050             goto invalid;
0051         end = cache->start + cache->length;
0052         i = 0;
0053         while (++path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
0054             btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
0055             if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY)
0056                 goto invalid;
0057             offset = key.objectid;
0058             while (offset < key.objectid + key.offset) {
0059                 bit = free_space_test_bit(cache, path, offset);
0060                 if (prev_bit == 0 && bit == 1) {
0061                     extent_start = offset;
0062                 } else if (prev_bit == 1 && bit == 0) {
0063                     if (i >= num_extents ||
0064                         extent_start != extents[i].start ||
0065                         offset - extent_start != extents[i].length)
0066                         goto invalid;
0067                     i++;
0068                 }
0069                 prev_bit = bit;
0070                 offset += fs_info->sectorsize;
0071             }
0072         }
0073         if (prev_bit == 1) {
0074             if (i >= num_extents ||
0075                 extent_start != extents[i].start ||
0076                 end - extent_start != extents[i].length)
0077                 goto invalid;
0078             i++;
0079         }
0080         if (i != num_extents)
0081             goto invalid;
0082     } else {
0083         if (btrfs_header_nritems(path->nodes[0]) != num_extents + 1 ||
0084             path->slots[0] != 0)
0085             goto invalid;
0086         for (i = 0; i < num_extents; i++) {
0087             path->slots[0]++;
0088             btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
0089             if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY ||
0090                 key.objectid != extents[i].start ||
0091                 key.offset != extents[i].length)
0092                 goto invalid;
0093         }
0094     }
0095 
0096     ret = 0;
0097 out:
0098     btrfs_release_path(path);
0099     return ret;
0100 invalid:
0101     test_err("free space tree is invalid");
0102     ret = -EINVAL;
0103     goto out;
0104 }
0105 
0106 static int check_free_space_extents(struct btrfs_trans_handle *trans,
0107                     struct btrfs_fs_info *fs_info,
0108                     struct btrfs_block_group *cache,
0109                     struct btrfs_path *path,
0110                     const struct free_space_extent * const extents,
0111                     unsigned int num_extents)
0112 {
0113     struct btrfs_free_space_info *info;
0114     u32 flags;
0115     int ret;
0116 
0117     info = search_free_space_info(trans, cache, path, 0);
0118     if (IS_ERR(info)) {
0119         test_err("could not find free space info");
0120         btrfs_release_path(path);
0121         return PTR_ERR(info);
0122     }
0123     flags = btrfs_free_space_flags(path->nodes[0], info);
0124     btrfs_release_path(path);
0125 
0126     ret = __check_free_space_extents(trans, fs_info, cache, path, extents,
0127                      num_extents);
0128     if (ret)
0129         return ret;
0130 
0131     /* Flip it to the other format and check that for good measure. */
0132     if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
0133         ret = convert_free_space_to_extents(trans, cache, path);
0134         if (ret) {
0135             test_err("could not convert to extents");
0136             return ret;
0137         }
0138     } else {
0139         ret = convert_free_space_to_bitmaps(trans, cache, path);
0140         if (ret) {
0141             test_err("could not convert to bitmaps");
0142             return ret;
0143         }
0144     }
0145     return __check_free_space_extents(trans, fs_info, cache, path, extents,
0146                       num_extents);
0147 }
0148 
0149 static int test_empty_block_group(struct btrfs_trans_handle *trans,
0150                   struct btrfs_fs_info *fs_info,
0151                   struct btrfs_block_group *cache,
0152                   struct btrfs_path *path,
0153                   u32 alignment)
0154 {
0155     const struct free_space_extent extents[] = {
0156         {cache->start, cache->length},
0157     };
0158 
0159     return check_free_space_extents(trans, fs_info, cache, path,
0160                     extents, ARRAY_SIZE(extents));
0161 }
0162 
0163 static int test_remove_all(struct btrfs_trans_handle *trans,
0164                struct btrfs_fs_info *fs_info,
0165                struct btrfs_block_group *cache,
0166                struct btrfs_path *path,
0167                u32 alignment)
0168 {
0169     const struct free_space_extent extents[] = {};
0170     int ret;
0171 
0172     ret = __remove_from_free_space_tree(trans, cache, path,
0173                         cache->start,
0174                         cache->length);
0175     if (ret) {
0176         test_err("could not remove free space");
0177         return ret;
0178     }
0179 
0180     return check_free_space_extents(trans, fs_info, cache, path,
0181                     extents, ARRAY_SIZE(extents));
0182 }
0183 
0184 static int test_remove_beginning(struct btrfs_trans_handle *trans,
0185                  struct btrfs_fs_info *fs_info,
0186                  struct btrfs_block_group *cache,
0187                  struct btrfs_path *path,
0188                  u32 alignment)
0189 {
0190     const struct free_space_extent extents[] = {
0191         {cache->start + alignment, cache->length - alignment},
0192     };
0193     int ret;
0194 
0195     ret = __remove_from_free_space_tree(trans, cache, path,
0196                         cache->start, alignment);
0197     if (ret) {
0198         test_err("could not remove free space");
0199         return ret;
0200     }
0201 
0202     return check_free_space_extents(trans, fs_info, cache, path,
0203                     extents, ARRAY_SIZE(extents));
0204 
0205 }
0206 
0207 static int test_remove_end(struct btrfs_trans_handle *trans,
0208                struct btrfs_fs_info *fs_info,
0209                struct btrfs_block_group *cache,
0210                struct btrfs_path *path,
0211                u32 alignment)
0212 {
0213     const struct free_space_extent extents[] = {
0214         {cache->start, cache->length - alignment},
0215     };
0216     int ret;
0217 
0218     ret = __remove_from_free_space_tree(trans, cache, path,
0219                     cache->start + cache->length - alignment,
0220                     alignment);
0221     if (ret) {
0222         test_err("could not remove free space");
0223         return ret;
0224     }
0225 
0226     return check_free_space_extents(trans, fs_info, cache, path,
0227                     extents, ARRAY_SIZE(extents));
0228 }
0229 
0230 static int test_remove_middle(struct btrfs_trans_handle *trans,
0231                   struct btrfs_fs_info *fs_info,
0232                   struct btrfs_block_group *cache,
0233                   struct btrfs_path *path,
0234                   u32 alignment)
0235 {
0236     const struct free_space_extent extents[] = {
0237         {cache->start, alignment},
0238         {cache->start + 2 * alignment, cache->length - 2 * alignment},
0239     };
0240     int ret;
0241 
0242     ret = __remove_from_free_space_tree(trans, cache, path,
0243                         cache->start + alignment,
0244                         alignment);
0245     if (ret) {
0246         test_err("could not remove free space");
0247         return ret;
0248     }
0249 
0250     return check_free_space_extents(trans, fs_info, cache, path,
0251                     extents, ARRAY_SIZE(extents));
0252 }
0253 
0254 static int test_merge_left(struct btrfs_trans_handle *trans,
0255                struct btrfs_fs_info *fs_info,
0256                struct btrfs_block_group *cache,
0257                struct btrfs_path *path,
0258                u32 alignment)
0259 {
0260     const struct free_space_extent extents[] = {
0261         {cache->start, 2 * alignment},
0262     };
0263     int ret;
0264 
0265     ret = __remove_from_free_space_tree(trans, cache, path,
0266                         cache->start, cache->length);
0267     if (ret) {
0268         test_err("could not remove free space");
0269         return ret;
0270     }
0271 
0272     ret = __add_to_free_space_tree(trans, cache, path, cache->start,
0273                        alignment);
0274     if (ret) {
0275         test_err("could not add free space");
0276         return ret;
0277     }
0278 
0279     ret = __add_to_free_space_tree(trans, cache, path,
0280                        cache->start + alignment,
0281                        alignment);
0282     if (ret) {
0283         test_err("could not add free space");
0284         return ret;
0285     }
0286 
0287     return check_free_space_extents(trans, fs_info, cache, path,
0288                     extents, ARRAY_SIZE(extents));
0289 }
0290 
0291 static int test_merge_right(struct btrfs_trans_handle *trans,
0292                struct btrfs_fs_info *fs_info,
0293                struct btrfs_block_group *cache,
0294                struct btrfs_path *path,
0295                u32 alignment)
0296 {
0297     const struct free_space_extent extents[] = {
0298         {cache->start + alignment, 2 * alignment},
0299     };
0300     int ret;
0301 
0302     ret = __remove_from_free_space_tree(trans, cache, path,
0303                         cache->start, cache->length);
0304     if (ret) {
0305         test_err("could not remove free space");
0306         return ret;
0307     }
0308 
0309     ret = __add_to_free_space_tree(trans, cache, path,
0310                        cache->start + 2 * alignment,
0311                        alignment);
0312     if (ret) {
0313         test_err("could not add free space");
0314         return ret;
0315     }
0316 
0317     ret = __add_to_free_space_tree(trans, cache, path,
0318                        cache->start + alignment,
0319                        alignment);
0320     if (ret) {
0321         test_err("could not add free space");
0322         return ret;
0323     }
0324 
0325     return check_free_space_extents(trans, fs_info, cache, path,
0326                     extents, ARRAY_SIZE(extents));
0327 }
0328 
0329 static int test_merge_both(struct btrfs_trans_handle *trans,
0330                struct btrfs_fs_info *fs_info,
0331                struct btrfs_block_group *cache,
0332                struct btrfs_path *path,
0333                u32 alignment)
0334 {
0335     const struct free_space_extent extents[] = {
0336         {cache->start, 3 * alignment},
0337     };
0338     int ret;
0339 
0340     ret = __remove_from_free_space_tree(trans, cache, path,
0341                         cache->start, cache->length);
0342     if (ret) {
0343         test_err("could not remove free space");
0344         return ret;
0345     }
0346 
0347     ret = __add_to_free_space_tree(trans, cache, path, cache->start,
0348                        alignment);
0349     if (ret) {
0350         test_err("could not add free space");
0351         return ret;
0352     }
0353 
0354     ret = __add_to_free_space_tree(trans, cache, path,
0355                        cache->start + 2 * alignment, alignment);
0356     if (ret) {
0357         test_err("could not add free space");
0358         return ret;
0359     }
0360 
0361     ret = __add_to_free_space_tree(trans, cache, path,
0362                        cache->start + alignment, alignment);
0363     if (ret) {
0364         test_err("could not add free space");
0365         return ret;
0366     }
0367 
0368     return check_free_space_extents(trans, fs_info, cache, path,
0369                     extents, ARRAY_SIZE(extents));
0370 }
0371 
0372 static int test_merge_none(struct btrfs_trans_handle *trans,
0373                struct btrfs_fs_info *fs_info,
0374                struct btrfs_block_group *cache,
0375                struct btrfs_path *path,
0376                u32 alignment)
0377 {
0378     const struct free_space_extent extents[] = {
0379         {cache->start, alignment},
0380         {cache->start + 2 * alignment, alignment},
0381         {cache->start + 4 * alignment, alignment},
0382     };
0383     int ret;
0384 
0385     ret = __remove_from_free_space_tree(trans, cache, path,
0386                         cache->start, cache->length);
0387     if (ret) {
0388         test_err("could not remove free space");
0389         return ret;
0390     }
0391 
0392     ret = __add_to_free_space_tree(trans, cache, path, cache->start,
0393                        alignment);
0394     if (ret) {
0395         test_err("could not add free space");
0396         return ret;
0397     }
0398 
0399     ret = __add_to_free_space_tree(trans, cache, path,
0400                        cache->start + 4 * alignment, alignment);
0401     if (ret) {
0402         test_err("could not add free space");
0403         return ret;
0404     }
0405 
0406     ret = __add_to_free_space_tree(trans, cache, path,
0407                        cache->start + 2 * alignment, alignment);
0408     if (ret) {
0409         test_err("could not add free space");
0410         return ret;
0411     }
0412 
0413     return check_free_space_extents(trans, fs_info, cache, path,
0414                     extents, ARRAY_SIZE(extents));
0415 }
0416 
0417 typedef int (*test_func_t)(struct btrfs_trans_handle *,
0418                struct btrfs_fs_info *,
0419                struct btrfs_block_group *,
0420                struct btrfs_path *,
0421                u32 alignment);
0422 
0423 static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize,
0424             u32 nodesize, u32 alignment)
0425 {
0426     struct btrfs_fs_info *fs_info;
0427     struct btrfs_root *root = NULL;
0428     struct btrfs_block_group *cache = NULL;
0429     struct btrfs_trans_handle trans;
0430     struct btrfs_path *path = NULL;
0431     int ret;
0432 
0433     fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
0434     if (!fs_info) {
0435         test_std_err(TEST_ALLOC_FS_INFO);
0436         ret = -ENOMEM;
0437         goto out;
0438     }
0439 
0440     root = btrfs_alloc_dummy_root(fs_info);
0441     if (IS_ERR(root)) {
0442         test_std_err(TEST_ALLOC_ROOT);
0443         ret = PTR_ERR(root);
0444         goto out;
0445     }
0446 
0447     btrfs_set_super_compat_ro_flags(root->fs_info->super_copy,
0448                     BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);
0449     root->root_key.objectid = BTRFS_FREE_SPACE_TREE_OBJECTID;
0450     root->root_key.type = BTRFS_ROOT_ITEM_KEY;
0451     root->root_key.offset = 0;
0452     btrfs_global_root_insert(root);
0453     root->fs_info->tree_root = root;
0454 
0455     root->node = alloc_test_extent_buffer(root->fs_info, nodesize);
0456     if (IS_ERR(root->node)) {
0457         test_std_err(TEST_ALLOC_EXTENT_BUFFER);
0458         ret = PTR_ERR(root->node);
0459         goto out;
0460     }
0461     btrfs_set_header_level(root->node, 0);
0462     btrfs_set_header_nritems(root->node, 0);
0463     root->alloc_bytenr += 2 * nodesize;
0464 
0465     cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment);
0466     if (!cache) {
0467         test_std_err(TEST_ALLOC_BLOCK_GROUP);
0468         ret = -ENOMEM;
0469         goto out;
0470     }
0471     cache->bitmap_low_thresh = 0;
0472     cache->bitmap_high_thresh = (u32)-1;
0473     cache->needs_free_space = 1;
0474     cache->fs_info = root->fs_info;
0475 
0476     btrfs_init_dummy_trans(&trans, root->fs_info);
0477 
0478     path = btrfs_alloc_path();
0479     if (!path) {
0480         test_std_err(TEST_ALLOC_ROOT);
0481         ret = -ENOMEM;
0482         goto out;
0483     }
0484 
0485     ret = add_block_group_free_space(&trans, cache);
0486     if (ret) {
0487         test_err("could not add block group free space");
0488         goto out;
0489     }
0490 
0491     if (bitmaps) {
0492         ret = convert_free_space_to_bitmaps(&trans, cache, path);
0493         if (ret) {
0494             test_err("could not convert block group to bitmaps");
0495             goto out;
0496         }
0497     }
0498 
0499     ret = test_func(&trans, root->fs_info, cache, path, alignment);
0500     if (ret)
0501         goto out;
0502 
0503     ret = remove_block_group_free_space(&trans, cache);
0504     if (ret) {
0505         test_err("could not remove block group free space");
0506         goto out;
0507     }
0508 
0509     if (btrfs_header_nritems(root->node) != 0) {
0510         test_err("free space tree has leftover items");
0511         ret = -EINVAL;
0512         goto out;
0513     }
0514 
0515     ret = 0;
0516 out:
0517     btrfs_free_path(path);
0518     btrfs_free_dummy_block_group(cache);
0519     btrfs_free_dummy_root(root);
0520     btrfs_free_dummy_fs_info(fs_info);
0521     return ret;
0522 }
0523 
0524 static int run_test_both_formats(test_func_t test_func, u32 sectorsize,
0525                  u32 nodesize, u32 alignment)
0526 {
0527     int test_ret = 0;
0528     int ret;
0529 
0530     ret = run_test(test_func, 0, sectorsize, nodesize, alignment);
0531     if (ret) {
0532         test_err(
0533     "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u",
0534              test_func, sectorsize, nodesize, alignment);
0535         test_ret = ret;
0536     }
0537 
0538     ret = run_test(test_func, 1, sectorsize, nodesize, alignment);
0539     if (ret) {
0540         test_err(
0541     "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u",
0542              test_func, sectorsize, nodesize, alignment);
0543         test_ret = ret;
0544     }
0545 
0546     return test_ret;
0547 }
0548 
0549 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize)
0550 {
0551     test_func_t tests[] = {
0552         test_empty_block_group,
0553         test_remove_all,
0554         test_remove_beginning,
0555         test_remove_end,
0556         test_remove_middle,
0557         test_merge_left,
0558         test_merge_right,
0559         test_merge_both,
0560         test_merge_none,
0561     };
0562     u32 bitmap_alignment;
0563     int test_ret = 0;
0564     int i;
0565 
0566     /*
0567      * Align some operations to a page to flush out bugs in the extent
0568      * buffer bitmap handling of highmem.
0569      */
0570     bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE;
0571 
0572     test_msg("running free space tree tests");
0573     for (i = 0; i < ARRAY_SIZE(tests); i++) {
0574         int ret;
0575 
0576         ret = run_test_both_formats(tests[i], sectorsize, nodesize,
0577                         sectorsize);
0578         if (ret)
0579             test_ret = ret;
0580 
0581         ret = run_test_both_formats(tests[i], sectorsize, nodesize,
0582                         bitmap_alignment);
0583         if (ret)
0584             test_ret = ret;
0585     }
0586 
0587     return test_ret;
0588 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!