590 lines · c
1// SPDX-License-Identifier: GPL-2.02/*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#include "../accessors.h"14 15struct free_space_extent {16 u64 start;17 u64 length;18};19 20static int __check_free_space_extents(struct btrfs_trans_handle *trans,21 struct btrfs_fs_info *fs_info,22 struct btrfs_block_group *cache,23 struct btrfs_path *path,24 const struct free_space_extent * const extents,25 unsigned int num_extents)26{27 struct btrfs_free_space_info *info;28 struct btrfs_key key;29 int prev_bit = 0, bit;30 u64 extent_start = 0, offset, end;31 u32 flags, extent_count;32 unsigned int i;33 int ret;34 35 info = search_free_space_info(trans, cache, path, 0);36 if (IS_ERR(info)) {37 test_err("could not find free space info");38 ret = PTR_ERR(info);39 goto out;40 }41 flags = btrfs_free_space_flags(path->nodes[0], info);42 extent_count = btrfs_free_space_extent_count(path->nodes[0], info);43 44 if (extent_count != num_extents) {45 test_err("extent count is wrong");46 ret = -EINVAL;47 goto out;48 }49 if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {50 if (path->slots[0] != 0)51 goto invalid;52 end = cache->start + cache->length;53 i = 0;54 while (++path->slots[0] < btrfs_header_nritems(path->nodes[0])) {55 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);56 if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY)57 goto invalid;58 offset = key.objectid;59 while (offset < key.objectid + key.offset) {60 bit = free_space_test_bit(cache, path, offset);61 if (prev_bit == 0 && bit == 1) {62 extent_start = offset;63 } else if (prev_bit == 1 && bit == 0) {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;98out:99 btrfs_release_path(path);100 return ret;101invalid:102 test_err("free space tree is invalid");103 ret = -EINVAL;104 goto out;105}106 107static int check_free_space_extents(struct btrfs_trans_handle *trans,108 struct btrfs_fs_info *fs_info,109 struct btrfs_block_group *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, 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 150static int test_empty_block_group(struct btrfs_trans_handle *trans,151 struct btrfs_fs_info *fs_info,152 struct btrfs_block_group *cache,153 struct btrfs_path *path,154 u32 alignment)155{156 const struct free_space_extent extents[] = {157 {cache->start, cache->length},158 };159 160 return check_free_space_extents(trans, fs_info, cache, path,161 extents, ARRAY_SIZE(extents));162}163 164static int test_remove_all(struct btrfs_trans_handle *trans,165 struct btrfs_fs_info *fs_info,166 struct btrfs_block_group *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->start,175 cache->length);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 185static int test_remove_beginning(struct btrfs_trans_handle *trans,186 struct btrfs_fs_info *fs_info,187 struct btrfs_block_group *cache,188 struct btrfs_path *path,189 u32 alignment)190{191 const struct free_space_extent extents[] = {192 {cache->start + alignment, cache->length - alignment},193 };194 int ret;195 196 ret = __remove_from_free_space_tree(trans, cache, path,197 cache->start, alignment);198 if (ret) {199 test_err("could not remove free space");200 return ret;201 }202 203 return check_free_space_extents(trans, fs_info, cache, path,204 extents, ARRAY_SIZE(extents));205 206}207 208static int test_remove_end(struct btrfs_trans_handle *trans,209 struct btrfs_fs_info *fs_info,210 struct btrfs_block_group *cache,211 struct btrfs_path *path,212 u32 alignment)213{214 const struct free_space_extent extents[] = {215 {cache->start, cache->length - alignment},216 };217 int ret;218 219 ret = __remove_from_free_space_tree(trans, cache, path,220 cache->start + cache->length - alignment,221 alignment);222 if (ret) {223 test_err("could not remove free space");224 return ret;225 }226 227 return check_free_space_extents(trans, fs_info, cache, path,228 extents, ARRAY_SIZE(extents));229}230 231static int test_remove_middle(struct btrfs_trans_handle *trans,232 struct btrfs_fs_info *fs_info,233 struct btrfs_block_group *cache,234 struct btrfs_path *path,235 u32 alignment)236{237 const struct free_space_extent extents[] = {238 {cache->start, alignment},239 {cache->start + 2 * alignment, cache->length - 2 * alignment},240 };241 int ret;242 243 ret = __remove_from_free_space_tree(trans, cache, path,244 cache->start + alignment,245 alignment);246 if (ret) {247 test_err("could not remove free space");248 return ret;249 }250 251 return check_free_space_extents(trans, fs_info, cache, path,252 extents, ARRAY_SIZE(extents));253}254 255static int test_merge_left(struct btrfs_trans_handle *trans,256 struct btrfs_fs_info *fs_info,257 struct btrfs_block_group *cache,258 struct btrfs_path *path,259 u32 alignment)260{261 const struct free_space_extent extents[] = {262 {cache->start, 2 * alignment},263 };264 int ret;265 266 ret = __remove_from_free_space_tree(trans, cache, path,267 cache->start, cache->length);268 if (ret) {269 test_err("could not remove free space");270 return ret;271 }272 273 ret = __add_to_free_space_tree(trans, cache, path, cache->start,274 alignment);275 if (ret) {276 test_err("could not add free space");277 return ret;278 }279 280 ret = __add_to_free_space_tree(trans, cache, path,281 cache->start + alignment,282 alignment);283 if (ret) {284 test_err("could not add free space");285 return ret;286 }287 288 return check_free_space_extents(trans, fs_info, cache, path,289 extents, ARRAY_SIZE(extents));290}291 292static int test_merge_right(struct btrfs_trans_handle *trans,293 struct btrfs_fs_info *fs_info,294 struct btrfs_block_group *cache,295 struct btrfs_path *path,296 u32 alignment)297{298 const struct free_space_extent extents[] = {299 {cache->start + alignment, 2 * alignment},300 };301 int ret;302 303 ret = __remove_from_free_space_tree(trans, cache, path,304 cache->start, cache->length);305 if (ret) {306 test_err("could not remove free space");307 return ret;308 }309 310 ret = __add_to_free_space_tree(trans, cache, path,311 cache->start + 2 * alignment,312 alignment);313 if (ret) {314 test_err("could not add free space");315 return ret;316 }317 318 ret = __add_to_free_space_tree(trans, cache, path,319 cache->start + alignment,320 alignment);321 if (ret) {322 test_err("could not add free space");323 return ret;324 }325 326 return check_free_space_extents(trans, fs_info, cache, path,327 extents, ARRAY_SIZE(extents));328}329 330static int test_merge_both(struct btrfs_trans_handle *trans,331 struct btrfs_fs_info *fs_info,332 struct btrfs_block_group *cache,333 struct btrfs_path *path,334 u32 alignment)335{336 const struct free_space_extent extents[] = {337 {cache->start, 3 * alignment},338 };339 int ret;340 341 ret = __remove_from_free_space_tree(trans, cache, path,342 cache->start, cache->length);343 if (ret) {344 test_err("could not remove free space");345 return ret;346 }347 348 ret = __add_to_free_space_tree(trans, cache, path, cache->start,349 alignment);350 if (ret) {351 test_err("could not add free space");352 return ret;353 }354 355 ret = __add_to_free_space_tree(trans, cache, path,356 cache->start + 2 * alignment, alignment);357 if (ret) {358 test_err("could not add free space");359 return ret;360 }361 362 ret = __add_to_free_space_tree(trans, cache, path,363 cache->start + alignment, alignment);364 if (ret) {365 test_err("could not add free space");366 return ret;367 }368 369 return check_free_space_extents(trans, fs_info, cache, path,370 extents, ARRAY_SIZE(extents));371}372 373static int test_merge_none(struct btrfs_trans_handle *trans,374 struct btrfs_fs_info *fs_info,375 struct btrfs_block_group *cache,376 struct btrfs_path *path,377 u32 alignment)378{379 const struct free_space_extent extents[] = {380 {cache->start, alignment},381 {cache->start + 2 * alignment, alignment},382 {cache->start + 4 * alignment, alignment},383 };384 int ret;385 386 ret = __remove_from_free_space_tree(trans, cache, path,387 cache->start, cache->length);388 if (ret) {389 test_err("could not remove free space");390 return ret;391 }392 393 ret = __add_to_free_space_tree(trans, cache, path, cache->start,394 alignment);395 if (ret) {396 test_err("could not add free space");397 return ret;398 }399 400 ret = __add_to_free_space_tree(trans, cache, path,401 cache->start + 4 * alignment, alignment);402 if (ret) {403 test_err("could not add free space");404 return ret;405 }406 407 ret = __add_to_free_space_tree(trans, cache, path,408 cache->start + 2 * alignment, alignment);409 if (ret) {410 test_err("could not add free space");411 return ret;412 }413 414 return check_free_space_extents(trans, fs_info, cache, path,415 extents, ARRAY_SIZE(extents));416}417 418typedef int (*test_func_t)(struct btrfs_trans_handle *,419 struct btrfs_fs_info *,420 struct btrfs_block_group *,421 struct btrfs_path *,422 u32 alignment);423 424static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize,425 u32 nodesize, u32 alignment)426{427 struct btrfs_fs_info *fs_info;428 struct btrfs_root *root = NULL;429 struct btrfs_block_group *cache = NULL;430 struct btrfs_trans_handle trans;431 struct btrfs_path *path = NULL;432 int ret;433 434 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);435 if (!fs_info) {436 test_std_err(TEST_ALLOC_FS_INFO);437 ret = -ENOMEM;438 goto out;439 }440 441 root = btrfs_alloc_dummy_root(fs_info);442 if (IS_ERR(root)) {443 test_std_err(TEST_ALLOC_ROOT);444 ret = PTR_ERR(root);445 goto out;446 }447 448 btrfs_set_super_compat_ro_flags(root->fs_info->super_copy,449 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);450 root->root_key.objectid = BTRFS_FREE_SPACE_TREE_OBJECTID;451 root->root_key.type = BTRFS_ROOT_ITEM_KEY;452 root->root_key.offset = 0;453 btrfs_global_root_insert(root);454 root->fs_info->tree_root = root;455 456 root->node = alloc_test_extent_buffer(root->fs_info, nodesize);457 if (IS_ERR(root->node)) {458 test_std_err(TEST_ALLOC_EXTENT_BUFFER);459 ret = PTR_ERR(root->node);460 goto out;461 }462 btrfs_set_header_level(root->node, 0);463 btrfs_set_header_nritems(root->node, 0);464 root->alloc_bytenr += 2 * nodesize;465 466 cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment);467 if (!cache) {468 test_std_err(TEST_ALLOC_BLOCK_GROUP);469 ret = -ENOMEM;470 goto out;471 }472 cache->bitmap_low_thresh = 0;473 cache->bitmap_high_thresh = (u32)-1;474 set_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &cache->runtime_flags);475 cache->fs_info = root->fs_info;476 477 btrfs_init_dummy_trans(&trans, root->fs_info);478 479 path = btrfs_alloc_path();480 if (!path) {481 test_std_err(TEST_ALLOC_ROOT);482 ret = -ENOMEM;483 goto out;484 }485 486 ret = add_block_group_free_space(&trans, cache);487 if (ret) {488 test_err("could not add block group free space");489 goto out;490 }491 492 if (bitmaps) {493 ret = convert_free_space_to_bitmaps(&trans, cache, path);494 if (ret) {495 test_err("could not convert block group to bitmaps");496 goto out;497 }498 }499 500 ret = test_func(&trans, root->fs_info, cache, path, alignment);501 if (ret)502 goto out;503 504 ret = remove_block_group_free_space(&trans, cache);505 if (ret) {506 test_err("could not remove block group free space");507 goto out;508 }509 510 if (btrfs_header_nritems(root->node) != 0) {511 test_err("free space tree has leftover items");512 ret = -EINVAL;513 goto out;514 }515 516 ret = 0;517out:518 btrfs_free_path(path);519 btrfs_free_dummy_block_group(cache);520 btrfs_free_dummy_root(root);521 btrfs_free_dummy_fs_info(fs_info);522 return ret;523}524 525static int run_test_both_formats(test_func_t test_func, u32 sectorsize,526 u32 nodesize, u32 alignment)527{528 int test_ret = 0;529 int ret;530 531 ret = run_test(test_func, 0, sectorsize, nodesize, alignment);532 if (ret) {533 test_err(534 "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u",535 test_func, sectorsize, nodesize, alignment);536 test_ret = ret;537 }538 539 ret = run_test(test_func, 1, sectorsize, nodesize, alignment);540 if (ret) {541 test_err(542 "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u",543 test_func, sectorsize, nodesize, alignment);544 test_ret = ret;545 }546 547 return test_ret;548}549 550int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize)551{552 test_func_t tests[] = {553 test_empty_block_group,554 test_remove_all,555 test_remove_beginning,556 test_remove_end,557 test_remove_middle,558 test_merge_left,559 test_merge_right,560 test_merge_both,561 test_merge_none,562 };563 u32 bitmap_alignment;564 int test_ret = 0;565 int i;566 567 /*568 * Align some operations to a page to flush out bugs in the extent569 * buffer bitmap handling of highmem.570 */571 bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE;572 573 test_msg("running free space tree tests");574 for (i = 0; i < ARRAY_SIZE(tests); i++) {575 int ret;576 577 ret = run_test_both_formats(tests[i], sectorsize, nodesize,578 sectorsize);579 if (ret)580 test_ret = ret;581 582 ret = run_test_both_formats(tests[i], sectorsize, nodesize,583 bitmap_alignment);584 if (ret)585 test_ret = ret;586 }587 588 return test_ret;589}590