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