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 #include "../accessors.h" 14 15 struct free_space_extent { 16 u64 start; 17 u64 length; 18 }; 19 20 static 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; 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, 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 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, 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 164 static 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 185 static 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 208 static 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 231 static 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 255 static 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 292 static 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 330 static 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 373 static 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 418 typedef 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 424 static 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; 517 out: 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 525 static 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 550 int 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 extent 569 * 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