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->fs_info->free_space_root = root; 450 root->fs_info->tree_root = root; 451 452 root->node = alloc_test_extent_buffer(root->fs_info, nodesize); 453 if (IS_ERR(root->node)) { 454 test_std_err(TEST_ALLOC_EXTENT_BUFFER); 455 ret = PTR_ERR(root->node); 456 goto out; 457 } 458 btrfs_set_header_level(root->node, 0); 459 btrfs_set_header_nritems(root->node, 0); 460 root->alloc_bytenr += 2 * nodesize; 461 462 cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment); 463 if (!cache) { 464 test_std_err(TEST_ALLOC_BLOCK_GROUP); 465 ret = -ENOMEM; 466 goto out; 467 } 468 cache->bitmap_low_thresh = 0; 469 cache->bitmap_high_thresh = (u32)-1; 470 cache->needs_free_space = 1; 471 cache->fs_info = root->fs_info; 472 473 btrfs_init_dummy_trans(&trans, root->fs_info); 474 475 path = btrfs_alloc_path(); 476 if (!path) { 477 test_std_err(TEST_ALLOC_ROOT); 478 ret = -ENOMEM; 479 goto out; 480 } 481 482 ret = add_block_group_free_space(&trans, cache); 483 if (ret) { 484 test_err("could not add block group free space"); 485 goto out; 486 } 487 488 if (bitmaps) { 489 ret = convert_free_space_to_bitmaps(&trans, cache, path); 490 if (ret) { 491 test_err("could not convert block group to bitmaps"); 492 goto out; 493 } 494 } 495 496 ret = test_func(&trans, root->fs_info, cache, path, alignment); 497 if (ret) 498 goto out; 499 500 ret = remove_block_group_free_space(&trans, cache); 501 if (ret) { 502 test_err("could not remove block group free space"); 503 goto out; 504 } 505 506 if (btrfs_header_nritems(root->node) != 0) { 507 test_err("free space tree has leftover items"); 508 ret = -EINVAL; 509 goto out; 510 } 511 512 ret = 0; 513 out: 514 btrfs_free_path(path); 515 btrfs_free_dummy_block_group(cache); 516 btrfs_free_dummy_root(root); 517 btrfs_free_dummy_fs_info(fs_info); 518 return ret; 519 } 520 521 static int run_test_both_formats(test_func_t test_func, u32 sectorsize, 522 u32 nodesize, u32 alignment) 523 { 524 int test_ret = 0; 525 int ret; 526 527 ret = run_test(test_func, 0, sectorsize, nodesize, alignment); 528 if (ret) { 529 test_err( 530 "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u", 531 test_func, sectorsize, nodesize, alignment); 532 test_ret = ret; 533 } 534 535 ret = run_test(test_func, 1, sectorsize, nodesize, alignment); 536 if (ret) { 537 test_err( 538 "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u", 539 test_func, sectorsize, nodesize, alignment); 540 test_ret = ret; 541 } 542 543 return test_ret; 544 } 545 546 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize) 547 { 548 test_func_t tests[] = { 549 test_empty_block_group, 550 test_remove_all, 551 test_remove_beginning, 552 test_remove_end, 553 test_remove_middle, 554 test_merge_left, 555 test_merge_right, 556 test_merge_both, 557 test_merge_none, 558 }; 559 u32 bitmap_alignment; 560 int test_ret = 0; 561 int i; 562 563 /* 564 * Align some operations to a page to flush out bugs in the extent 565 * buffer bitmap handling of highmem. 566 */ 567 bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE; 568 569 test_msg("running free space tree tests"); 570 for (i = 0; i < ARRAY_SIZE(tests); i++) { 571 int ret; 572 573 ret = run_test_both_formats(tests[i], sectorsize, nodesize, 574 sectorsize); 575 if (ret) 576 test_ret = ret; 577 578 ret = run_test_both_formats(tests[i], sectorsize, nodesize, 579 bitmap_alignment); 580 if (ret) 581 test_ret = ret; 582 } 583 584 return test_ret; 585 } 586