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, 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->start + cache->length; 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 extent_start != extents[i].start || 65 offset - extent_start != extents[i].length) 66 goto invalid; 67 i++; 68 } 69 prev_bit = bit; 70 offset += fs_info->sectorsize; 71 } 72 } 73 if (prev_bit == 1) { 74 if (i >= num_extents || 75 extent_start != extents[i].start || 76 end - extent_start != extents[i].length) 77 goto invalid; 78 i++; 79 } 80 if (i != num_extents) 81 goto invalid; 82 } else { 83 if (btrfs_header_nritems(path->nodes[0]) != num_extents + 1 || 84 path->slots[0] != 0) 85 goto invalid; 86 for (i = 0; i < num_extents; i++) { 87 path->slots[0]++; 88 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); 89 if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY || 90 key.objectid != extents[i].start || 91 key.offset != extents[i].length) 92 goto invalid; 93 } 94 } 95 96 ret = 0; 97 out: 98 btrfs_release_path(path); 99 return ret; 100 invalid: 101 test_err("free space tree is invalid"); 102 ret = -EINVAL; 103 goto out; 104 } 105 106 static int check_free_space_extents(struct btrfs_trans_handle *trans, 107 struct btrfs_fs_info *fs_info, 108 struct btrfs_block_group *cache, 109 struct btrfs_path *path, 110 const struct free_space_extent * const extents, 111 unsigned int num_extents) 112 { 113 struct btrfs_free_space_info *info; 114 u32 flags; 115 int ret; 116 117 info = search_free_space_info(trans, cache, path, 0); 118 if (IS_ERR(info)) { 119 test_err("could not find free space info"); 120 btrfs_release_path(path); 121 return PTR_ERR(info); 122 } 123 flags = btrfs_free_space_flags(path->nodes[0], info); 124 btrfs_release_path(path); 125 126 ret = __check_free_space_extents(trans, fs_info, cache, path, extents, 127 num_extents); 128 if (ret) 129 return ret; 130 131 /* Flip it to the other format and check that for good measure. */ 132 if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) { 133 ret = convert_free_space_to_extents(trans, cache, path); 134 if (ret) { 135 test_err("could not convert to extents"); 136 return ret; 137 } 138 } else { 139 ret = convert_free_space_to_bitmaps(trans, cache, path); 140 if (ret) { 141 test_err("could not convert to bitmaps"); 142 return ret; 143 } 144 } 145 return __check_free_space_extents(trans, fs_info, cache, path, extents, 146 num_extents); 147 } 148 149 static int test_empty_block_group(struct btrfs_trans_handle *trans, 150 struct btrfs_fs_info *fs_info, 151 struct btrfs_block_group *cache, 152 struct btrfs_path *path, 153 u32 alignment) 154 { 155 const struct free_space_extent extents[] = { 156 {cache->start, cache->length}, 157 }; 158 159 return check_free_space_extents(trans, fs_info, cache, path, 160 extents, ARRAY_SIZE(extents)); 161 } 162 163 static int test_remove_all(struct btrfs_trans_handle *trans, 164 struct btrfs_fs_info *fs_info, 165 struct btrfs_block_group *cache, 166 struct btrfs_path *path, 167 u32 alignment) 168 { 169 const struct free_space_extent extents[] = {}; 170 int ret; 171 172 ret = __remove_from_free_space_tree(trans, cache, path, 173 cache->start, 174 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 = __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 = __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 = __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 = __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 = __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 = __add_to_free_space_tree(trans, cache, path, 280 cache->start + alignment, 281 alignment); 282 if (ret) { 283 test_err("could not add free space"); 284 return ret; 285 } 286 287 return check_free_space_extents(trans, fs_info, cache, path, 288 extents, ARRAY_SIZE(extents)); 289 } 290 291 static int test_merge_right(struct btrfs_trans_handle *trans, 292 struct btrfs_fs_info *fs_info, 293 struct btrfs_block_group *cache, 294 struct btrfs_path *path, 295 u32 alignment) 296 { 297 const struct free_space_extent extents[] = { 298 {cache->start + alignment, 2 * alignment}, 299 }; 300 int ret; 301 302 ret = __remove_from_free_space_tree(trans, cache, path, 303 cache->start, cache->length); 304 if (ret) { 305 test_err("could not remove free space"); 306 return ret; 307 } 308 309 ret = __add_to_free_space_tree(trans, cache, path, 310 cache->start + 2 * alignment, 311 alignment); 312 if (ret) { 313 test_err("could not add free space"); 314 return ret; 315 } 316 317 ret = __add_to_free_space_tree(trans, cache, path, 318 cache->start + alignment, 319 alignment); 320 if (ret) { 321 test_err("could not add free space"); 322 return ret; 323 } 324 325 return check_free_space_extents(trans, fs_info, cache, path, 326 extents, ARRAY_SIZE(extents)); 327 } 328 329 static int test_merge_both(struct btrfs_trans_handle *trans, 330 struct btrfs_fs_info *fs_info, 331 struct btrfs_block_group *cache, 332 struct btrfs_path *path, 333 u32 alignment) 334 { 335 const struct free_space_extent extents[] = { 336 {cache->start, 3 * alignment}, 337 }; 338 int ret; 339 340 ret = __remove_from_free_space_tree(trans, cache, path, 341 cache->start, cache->length); 342 if (ret) { 343 test_err("could not remove free space"); 344 return ret; 345 } 346 347 ret = __add_to_free_space_tree(trans, cache, path, cache->start, 348 alignment); 349 if (ret) { 350 test_err("could not add free space"); 351 return ret; 352 } 353 354 ret = __add_to_free_space_tree(trans, cache, path, 355 cache->start + 2 * alignment, alignment); 356 if (ret) { 357 test_err("could not add free space"); 358 return ret; 359 } 360 361 ret = __add_to_free_space_tree(trans, cache, path, 362 cache->start + alignment, alignment); 363 if (ret) { 364 test_err("could not add free space"); 365 return ret; 366 } 367 368 return check_free_space_extents(trans, fs_info, cache, path, 369 extents, ARRAY_SIZE(extents)); 370 } 371 372 static int test_merge_none(struct btrfs_trans_handle *trans, 373 struct btrfs_fs_info *fs_info, 374 struct btrfs_block_group *cache, 375 struct btrfs_path *path, 376 u32 alignment) 377 { 378 const struct free_space_extent extents[] = { 379 {cache->start, alignment}, 380 {cache->start + 2 * alignment, alignment}, 381 {cache->start + 4 * alignment, alignment}, 382 }; 383 int ret; 384 385 ret = __remove_from_free_space_tree(trans, cache, path, 386 cache->start, cache->length); 387 if (ret) { 388 test_err("could not remove free space"); 389 return ret; 390 } 391 392 ret = __add_to_free_space_tree(trans, cache, path, cache->start, 393 alignment); 394 if (ret) { 395 test_err("could not add free space"); 396 return ret; 397 } 398 399 ret = __add_to_free_space_tree(trans, cache, path, 400 cache->start + 4 * alignment, alignment); 401 if (ret) { 402 test_err("could not add free space"); 403 return ret; 404 } 405 406 ret = __add_to_free_space_tree(trans, cache, path, 407 cache->start + 2 * alignment, alignment); 408 if (ret) { 409 test_err("could not add free space"); 410 return ret; 411 } 412 413 return check_free_space_extents(trans, fs_info, cache, path, 414 extents, ARRAY_SIZE(extents)); 415 } 416 417 typedef int (*test_func_t)(struct btrfs_trans_handle *, 418 struct btrfs_fs_info *, 419 struct btrfs_block_group *, 420 struct btrfs_path *, 421 u32 alignment); 422 423 static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize, 424 u32 nodesize, u32 alignment) 425 { 426 struct btrfs_fs_info *fs_info; 427 struct btrfs_root *root = NULL; 428 struct btrfs_block_group *cache = NULL; 429 struct btrfs_trans_handle trans; 430 struct btrfs_path *path = NULL; 431 int ret; 432 433 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); 434 if (!fs_info) { 435 test_std_err(TEST_ALLOC_FS_INFO); 436 ret = -ENOMEM; 437 goto out; 438 } 439 440 root = btrfs_alloc_dummy_root(fs_info); 441 if (IS_ERR(root)) { 442 test_std_err(TEST_ALLOC_ROOT); 443 ret = PTR_ERR(root); 444 goto out; 445 } 446 447 btrfs_set_super_compat_ro_flags(root->fs_info->super_copy, 448 BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE); 449 root->root_key.objectid = BTRFS_FREE_SPACE_TREE_OBJECTID; 450 root->root_key.type = BTRFS_ROOT_ITEM_KEY; 451 root->root_key.offset = 0; 452 btrfs_global_root_insert(root); 453 root->fs_info->tree_root = root; 454 455 root->node = alloc_test_extent_buffer(root->fs_info, nodesize); 456 if (IS_ERR(root->node)) { 457 test_std_err(TEST_ALLOC_EXTENT_BUFFER); 458 ret = PTR_ERR(root->node); 459 goto out; 460 } 461 btrfs_set_header_level(root->node, 0); 462 btrfs_set_header_nritems(root->node, 0); 463 root->alloc_bytenr += 2 * nodesize; 464 465 cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment); 466 if (!cache) { 467 test_std_err(TEST_ALLOC_BLOCK_GROUP); 468 ret = -ENOMEM; 469 goto out; 470 } 471 cache->bitmap_low_thresh = 0; 472 cache->bitmap_high_thresh = (u32)-1; 473 cache->needs_free_space = 1; 474 cache->fs_info = root->fs_info; 475 476 btrfs_init_dummy_trans(&trans, root->fs_info); 477 478 path = btrfs_alloc_path(); 479 if (!path) { 480 test_std_err(TEST_ALLOC_ROOT); 481 ret = -ENOMEM; 482 goto out; 483 } 484 485 ret = add_block_group_free_space(&trans, cache); 486 if (ret) { 487 test_err("could not add block group free space"); 488 goto out; 489 } 490 491 if (bitmaps) { 492 ret = convert_free_space_to_bitmaps(&trans, cache, path); 493 if (ret) { 494 test_err("could not convert block group to bitmaps"); 495 goto out; 496 } 497 } 498 499 ret = test_func(&trans, root->fs_info, cache, path, alignment); 500 if (ret) 501 goto out; 502 503 ret = remove_block_group_free_space(&trans, cache); 504 if (ret) { 505 test_err("could not remove block group free space"); 506 goto out; 507 } 508 509 if (btrfs_header_nritems(root->node) != 0) { 510 test_err("free space tree has leftover items"); 511 ret = -EINVAL; 512 goto out; 513 } 514 515 ret = 0; 516 out: 517 btrfs_free_path(path); 518 btrfs_free_dummy_block_group(cache); 519 btrfs_free_dummy_root(root); 520 btrfs_free_dummy_fs_info(fs_info); 521 return ret; 522 } 523 524 static int run_test_both_formats(test_func_t test_func, u32 sectorsize, 525 u32 nodesize, u32 alignment) 526 { 527 int test_ret = 0; 528 int ret; 529 530 ret = run_test(test_func, 0, sectorsize, nodesize, alignment); 531 if (ret) { 532 test_err( 533 "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u", 534 test_func, sectorsize, nodesize, alignment); 535 test_ret = ret; 536 } 537 538 ret = run_test(test_func, 1, sectorsize, nodesize, alignment); 539 if (ret) { 540 test_err( 541 "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u", 542 test_func, sectorsize, nodesize, alignment); 543 test_ret = ret; 544 } 545 546 return test_ret; 547 } 548 549 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize) 550 { 551 test_func_t tests[] = { 552 test_empty_block_group, 553 test_remove_all, 554 test_remove_beginning, 555 test_remove_end, 556 test_remove_middle, 557 test_merge_left, 558 test_merge_right, 559 test_merge_both, 560 test_merge_none, 561 }; 562 u32 bitmap_alignment; 563 int test_ret = 0; 564 int i; 565 566 /* 567 * Align some operations to a page to flush out bugs in the extent 568 * buffer bitmap handling of highmem. 569 */ 570 bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE; 571 572 test_msg("running free space tree tests"); 573 for (i = 0; i < ARRAY_SIZE(tests); i++) { 574 int ret; 575 576 ret = run_test_both_formats(tests[i], sectorsize, nodesize, 577 sectorsize); 578 if (ret) 579 test_ret = ret; 580 581 ret = run_test_both_formats(tests[i], sectorsize, nodesize, 582 bitmap_alignment); 583 if (ret) 584 test_ret = ret; 585 } 586 587 return test_ret; 588 } 589