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 = btrfs_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 = btrfs_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 = btrfs_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 = btrfs_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 = btrfs_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 = __btrfs_remove_from_free_space_tree(trans, cache, path, 174 cache->start, cache->length); 175 if (ret) { 176 test_err("could not remove free space"); 177 return ret; 178 } 179 180 return check_free_space_extents(trans, fs_info, cache, path, 181 extents, ARRAY_SIZE(extents)); 182 } 183 184 static int test_remove_beginning(struct btrfs_trans_handle *trans, 185 struct btrfs_fs_info *fs_info, 186 struct btrfs_block_group *cache, 187 struct btrfs_path *path, 188 u32 alignment) 189 { 190 const struct free_space_extent extents[] = { 191 {cache->start + alignment, cache->length - alignment}, 192 }; 193 int ret; 194 195 ret = __btrfs_remove_from_free_space_tree(trans, cache, path, 196 cache->start, alignment); 197 if (ret) { 198 test_err("could not remove free space"); 199 return ret; 200 } 201 202 return check_free_space_extents(trans, fs_info, cache, path, 203 extents, ARRAY_SIZE(extents)); 204 205 } 206 207 static int test_remove_end(struct btrfs_trans_handle *trans, 208 struct btrfs_fs_info *fs_info, 209 struct btrfs_block_group *cache, 210 struct btrfs_path *path, 211 u32 alignment) 212 { 213 const struct free_space_extent extents[] = { 214 {cache->start, cache->length - alignment}, 215 }; 216 int ret; 217 218 ret = __btrfs_remove_from_free_space_tree(trans, cache, path, 219 cache->start + cache->length - alignment, 220 alignment); 221 if (ret) { 222 test_err("could not remove free space"); 223 return ret; 224 } 225 226 return check_free_space_extents(trans, fs_info, cache, path, 227 extents, ARRAY_SIZE(extents)); 228 } 229 230 static int test_remove_middle(struct btrfs_trans_handle *trans, 231 struct btrfs_fs_info *fs_info, 232 struct btrfs_block_group *cache, 233 struct btrfs_path *path, 234 u32 alignment) 235 { 236 const struct free_space_extent extents[] = { 237 {cache->start, alignment}, 238 {cache->start + 2 * alignment, cache->length - 2 * alignment}, 239 }; 240 int ret; 241 242 ret = __btrfs_remove_from_free_space_tree(trans, cache, path, 243 cache->start + alignment, 244 alignment); 245 if (ret) { 246 test_err("could not remove free space"); 247 return ret; 248 } 249 250 return check_free_space_extents(trans, fs_info, cache, path, 251 extents, ARRAY_SIZE(extents)); 252 } 253 254 static int test_merge_left(struct btrfs_trans_handle *trans, 255 struct btrfs_fs_info *fs_info, 256 struct btrfs_block_group *cache, 257 struct btrfs_path *path, 258 u32 alignment) 259 { 260 const struct free_space_extent extents[] = { 261 {cache->start, 2 * alignment}, 262 }; 263 int ret; 264 265 ret = __btrfs_remove_from_free_space_tree(trans, cache, path, 266 cache->start, cache->length); 267 if (ret) { 268 test_err("could not remove free space"); 269 return ret; 270 } 271 272 ret = __btrfs_add_to_free_space_tree(trans, cache, path, cache->start, 273 alignment); 274 if (ret) { 275 test_err("could not add free space"); 276 return ret; 277 } 278 279 ret = __btrfs_add_to_free_space_tree(trans, cache, path, 280 cache->start + alignment, alignment); 281 if (ret) { 282 test_err("could not add free space"); 283 return ret; 284 } 285 286 return check_free_space_extents(trans, fs_info, cache, path, 287 extents, ARRAY_SIZE(extents)); 288 } 289 290 static int test_merge_right(struct btrfs_trans_handle *trans, 291 struct btrfs_fs_info *fs_info, 292 struct btrfs_block_group *cache, 293 struct btrfs_path *path, 294 u32 alignment) 295 { 296 const struct free_space_extent extents[] = { 297 {cache->start + alignment, 2 * alignment}, 298 }; 299 int ret; 300 301 ret = __btrfs_remove_from_free_space_tree(trans, cache, path, 302 cache->start, cache->length); 303 if (ret) { 304 test_err("could not remove free space"); 305 return ret; 306 } 307 308 ret = __btrfs_add_to_free_space_tree(trans, cache, path, 309 cache->start + 2 * alignment, 310 alignment); 311 if (ret) { 312 test_err("could not add free space"); 313 return ret; 314 } 315 316 ret = __btrfs_add_to_free_space_tree(trans, cache, path, 317 cache->start + alignment, alignment); 318 if (ret) { 319 test_err("could not add free space"); 320 return ret; 321 } 322 323 return check_free_space_extents(trans, fs_info, cache, path, 324 extents, ARRAY_SIZE(extents)); 325 } 326 327 static int test_merge_both(struct btrfs_trans_handle *trans, 328 struct btrfs_fs_info *fs_info, 329 struct btrfs_block_group *cache, 330 struct btrfs_path *path, 331 u32 alignment) 332 { 333 const struct free_space_extent extents[] = { 334 {cache->start, 3 * alignment}, 335 }; 336 int ret; 337 338 ret = __btrfs_remove_from_free_space_tree(trans, cache, path, 339 cache->start, cache->length); 340 if (ret) { 341 test_err("could not remove free space"); 342 return ret; 343 } 344 345 ret = __btrfs_add_to_free_space_tree(trans, cache, path, cache->start, 346 alignment); 347 if (ret) { 348 test_err("could not add free space"); 349 return ret; 350 } 351 352 ret = __btrfs_add_to_free_space_tree(trans, cache, path, 353 cache->start + 2 * alignment, alignment); 354 if (ret) { 355 test_err("could not add free space"); 356 return ret; 357 } 358 359 ret = __btrfs_add_to_free_space_tree(trans, cache, path, 360 cache->start + alignment, alignment); 361 if (ret) { 362 test_err("could not add free space"); 363 return ret; 364 } 365 366 return check_free_space_extents(trans, fs_info, cache, path, 367 extents, ARRAY_SIZE(extents)); 368 } 369 370 static int test_merge_none(struct btrfs_trans_handle *trans, 371 struct btrfs_fs_info *fs_info, 372 struct btrfs_block_group *cache, 373 struct btrfs_path *path, 374 u32 alignment) 375 { 376 const struct free_space_extent extents[] = { 377 {cache->start, alignment}, 378 {cache->start + 2 * alignment, alignment}, 379 {cache->start + 4 * alignment, alignment}, 380 }; 381 int ret; 382 383 ret = __btrfs_remove_from_free_space_tree(trans, cache, path, 384 cache->start, cache->length); 385 if (ret) { 386 test_err("could not remove free space"); 387 return ret; 388 } 389 390 ret = __btrfs_add_to_free_space_tree(trans, cache, path, cache->start, 391 alignment); 392 if (ret) { 393 test_err("could not add free space"); 394 return ret; 395 } 396 397 ret = __btrfs_add_to_free_space_tree(trans, cache, path, 398 cache->start + 4 * alignment, alignment); 399 if (ret) { 400 test_err("could not add free space"); 401 return ret; 402 } 403 404 ret = __btrfs_add_to_free_space_tree(trans, cache, path, 405 cache->start + 2 * alignment, alignment); 406 if (ret) { 407 test_err("could not add free space"); 408 return ret; 409 } 410 411 return check_free_space_extents(trans, fs_info, cache, path, 412 extents, ARRAY_SIZE(extents)); 413 } 414 415 typedef int (*test_func_t)(struct btrfs_trans_handle *, 416 struct btrfs_fs_info *, 417 struct btrfs_block_group *, 418 struct btrfs_path *, 419 u32 alignment); 420 421 static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize, 422 u32 nodesize, u32 alignment) 423 { 424 struct btrfs_fs_info *fs_info; 425 struct btrfs_root *root = NULL; 426 struct btrfs_block_group *cache = NULL; 427 struct btrfs_trans_handle trans; 428 struct btrfs_path *path = NULL; 429 int ret; 430 431 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); 432 if (!fs_info) { 433 test_std_err(TEST_ALLOC_FS_INFO); 434 ret = -ENOMEM; 435 goto out; 436 } 437 438 root = btrfs_alloc_dummy_root(fs_info); 439 if (IS_ERR(root)) { 440 test_std_err(TEST_ALLOC_ROOT); 441 ret = PTR_ERR(root); 442 goto out; 443 } 444 445 btrfs_set_super_compat_ro_flags(root->fs_info->super_copy, 446 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE); 447 root->root_key.objectid = BTRFS_FREE_SPACE_TREE_OBJECTID; 448 root->root_key.type = BTRFS_ROOT_ITEM_KEY; 449 root->root_key.offset = 0; 450 btrfs_global_root_insert(root); 451 root->fs_info->tree_root = root; 452 453 root->node = alloc_test_extent_buffer(root->fs_info, nodesize); 454 if (IS_ERR(root->node)) { 455 test_std_err(TEST_ALLOC_EXTENT_BUFFER); 456 ret = PTR_ERR(root->node); 457 goto out; 458 } 459 btrfs_set_header_level(root->node, 0); 460 btrfs_set_header_nritems(root->node, 0); 461 root->alloc_bytenr += 2 * nodesize; 462 463 cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment); 464 if (!cache) { 465 test_std_err(TEST_ALLOC_BLOCK_GROUP); 466 ret = -ENOMEM; 467 goto out; 468 } 469 cache->bitmap_low_thresh = 0; 470 cache->bitmap_high_thresh = (u32)-1; 471 set_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &cache->runtime_flags); 472 cache->fs_info = root->fs_info; 473 474 btrfs_init_dummy_trans(&trans, root->fs_info); 475 476 path = btrfs_alloc_path(); 477 if (!path) { 478 test_std_err(TEST_ALLOC_ROOT); 479 ret = -ENOMEM; 480 goto out; 481 } 482 483 ret = btrfs_add_block_group_free_space(&trans, cache); 484 if (ret) { 485 test_err("could not add block group free space"); 486 goto out; 487 } 488 489 if (bitmaps) { 490 ret = btrfs_convert_free_space_to_bitmaps(&trans, cache, path); 491 if (ret) { 492 test_err("could not convert block group to bitmaps"); 493 goto out; 494 } 495 } 496 497 ret = test_func(&trans, root->fs_info, cache, path, alignment); 498 if (ret) 499 goto out; 500 501 ret = btrfs_remove_block_group_free_space(&trans, cache); 502 if (ret) { 503 test_err("could not remove block group free space"); 504 goto out; 505 } 506 507 if (btrfs_header_nritems(root->node) != 0) { 508 test_err("free space tree has leftover items"); 509 ret = -EINVAL; 510 goto out; 511 } 512 513 ret = 0; 514 out: 515 btrfs_free_path(path); 516 btrfs_free_dummy_block_group(cache); 517 btrfs_free_dummy_root(root); 518 btrfs_free_dummy_fs_info(fs_info); 519 return ret; 520 } 521 522 static int run_test_both_formats(test_func_t test_func, u32 sectorsize, 523 u32 nodesize, u32 alignment) 524 { 525 int test_ret = 0; 526 int ret; 527 528 ret = run_test(test_func, 0, sectorsize, nodesize, alignment); 529 if (ret) { 530 test_err( 531 "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u", 532 test_func, sectorsize, nodesize, alignment); 533 test_ret = ret; 534 } 535 536 ret = run_test(test_func, 1, sectorsize, nodesize, alignment); 537 if (ret) { 538 test_err( 539 "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u", 540 test_func, sectorsize, nodesize, alignment); 541 test_ret = ret; 542 } 543 544 return test_ret; 545 } 546 547 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize) 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 u32 bitmap_alignment; 561 int test_ret = 0; 562 int i; 563 564 /* 565 * Align some operations to a page to flush out bugs in the extent 566 * buffer bitmap handling of highmem. 567 */ 568 bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE; 569 570 test_msg("running free space tree tests"); 571 for (i = 0; i < ARRAY_SIZE(tests); i++) { 572 int ret; 573 574 ret = run_test_both_formats(tests[i], sectorsize, nodesize, 575 sectorsize); 576 if (ret) 577 test_ret = ret; 578 579 ret = run_test_both_formats(tests[i], sectorsize, nodesize, 580 bitmap_alignment); 581 if (ret) 582 test_ret = ret; 583 } 584 585 return test_ret; 586 } 587