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