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