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