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