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