1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2013 Facebook. All rights reserved. 4 */ 5 6 #include <linux/types.h> 7 #include "btrfs-tests.h" 8 #include "../ctree.h" 9 #include "../transaction.h" 10 #include "../disk-io.h" 11 #include "../qgroup.h" 12 #include "../backref.h" 13 #include "../fs.h" 14 #include "../accessors.h" 15 16 static int insert_normal_tree_ref(struct btrfs_root *root, u64 bytenr, 17 u64 num_bytes, u64 parent, u64 root_objectid) 18 { 19 struct btrfs_trans_handle trans; 20 struct btrfs_extent_item *item; 21 struct btrfs_extent_inline_ref *iref; 22 struct btrfs_tree_block_info *block_info; 23 struct btrfs_path *path; 24 struct extent_buffer *leaf; 25 struct btrfs_key ins; 26 u32 size = sizeof(*item) + sizeof(*iref) + sizeof(*block_info); 27 int ret; 28 29 btrfs_init_dummy_trans(&trans, NULL); 30 31 ins.objectid = bytenr; 32 ins.type = BTRFS_EXTENT_ITEM_KEY; 33 ins.offset = num_bytes; 34 35 path = btrfs_alloc_path(); 36 if (!path) { 37 test_std_err(TEST_ALLOC_ROOT); 38 return -ENOMEM; 39 } 40 41 ret = btrfs_insert_empty_item(&trans, root, path, &ins, size); 42 if (ret) { 43 test_err("couldn't insert ref %d", ret); 44 btrfs_free_path(path); 45 return ret; 46 } 47 48 leaf = path->nodes[0]; 49 item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item); 50 btrfs_set_extent_refs(leaf, item, 1); 51 btrfs_set_extent_generation(leaf, item, 1); 52 btrfs_set_extent_flags(leaf, item, BTRFS_EXTENT_FLAG_TREE_BLOCK); 53 block_info = (struct btrfs_tree_block_info *)(item + 1); 54 btrfs_set_tree_block_level(leaf, block_info, 0); 55 iref = (struct btrfs_extent_inline_ref *)(block_info + 1); 56 if (parent > 0) { 57 btrfs_set_extent_inline_ref_type(leaf, iref, 58 BTRFS_SHARED_BLOCK_REF_KEY); 59 btrfs_set_extent_inline_ref_offset(leaf, iref, parent); 60 } else { 61 btrfs_set_extent_inline_ref_type(leaf, iref, BTRFS_TREE_BLOCK_REF_KEY); 62 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid); 63 } 64 btrfs_free_path(path); 65 return 0; 66 } 67 68 static int add_tree_ref(struct btrfs_root *root, u64 bytenr, u64 num_bytes, 69 u64 parent, u64 root_objectid) 70 { 71 struct btrfs_trans_handle trans; 72 struct btrfs_extent_item *item; 73 struct btrfs_path *path; 74 struct btrfs_key key; 75 u64 refs; 76 int ret; 77 78 btrfs_init_dummy_trans(&trans, NULL); 79 80 key.objectid = bytenr; 81 key.type = BTRFS_EXTENT_ITEM_KEY; 82 key.offset = num_bytes; 83 84 path = btrfs_alloc_path(); 85 if (!path) { 86 test_std_err(TEST_ALLOC_ROOT); 87 return -ENOMEM; 88 } 89 90 ret = btrfs_search_slot(&trans, root, &key, path, 0, 1); 91 if (ret) { 92 test_err("couldn't find extent ref"); 93 btrfs_free_path(path); 94 return ret; 95 } 96 97 item = btrfs_item_ptr(path->nodes[0], path->slots[0], 98 struct btrfs_extent_item); 99 refs = btrfs_extent_refs(path->nodes[0], item); 100 btrfs_set_extent_refs(path->nodes[0], item, refs + 1); 101 btrfs_release_path(path); 102 103 key.objectid = bytenr; 104 if (parent) { 105 key.type = BTRFS_SHARED_BLOCK_REF_KEY; 106 key.offset = parent; 107 } else { 108 key.type = BTRFS_TREE_BLOCK_REF_KEY; 109 key.offset = root_objectid; 110 } 111 112 ret = btrfs_insert_empty_item(&trans, root, path, &key, 0); 113 if (ret) 114 test_err("failed to insert backref"); 115 btrfs_free_path(path); 116 return ret; 117 } 118 119 static int remove_extent_item(struct btrfs_root *root, u64 bytenr, 120 u64 num_bytes) 121 { 122 struct btrfs_trans_handle trans; 123 struct btrfs_key key; 124 struct btrfs_path *path; 125 int ret; 126 127 btrfs_init_dummy_trans(&trans, NULL); 128 129 key.objectid = bytenr; 130 key.type = BTRFS_EXTENT_ITEM_KEY; 131 key.offset = num_bytes; 132 133 path = btrfs_alloc_path(); 134 if (!path) { 135 test_std_err(TEST_ALLOC_ROOT); 136 return -ENOMEM; 137 } 138 139 ret = btrfs_search_slot(&trans, root, &key, path, -1, 1); 140 if (ret) { 141 test_err("didn't find our key %d", ret); 142 btrfs_free_path(path); 143 return ret; 144 } 145 btrfs_del_item(&trans, root, path); 146 btrfs_free_path(path); 147 return 0; 148 } 149 150 static int remove_extent_ref(struct btrfs_root *root, u64 bytenr, 151 u64 num_bytes, u64 parent, u64 root_objectid) 152 { 153 struct btrfs_trans_handle trans; 154 struct btrfs_extent_item *item; 155 struct btrfs_path *path; 156 struct btrfs_key key; 157 u64 refs; 158 int ret; 159 160 btrfs_init_dummy_trans(&trans, NULL); 161 162 key.objectid = bytenr; 163 key.type = BTRFS_EXTENT_ITEM_KEY; 164 key.offset = num_bytes; 165 166 path = btrfs_alloc_path(); 167 if (!path) { 168 test_std_err(TEST_ALLOC_ROOT); 169 return -ENOMEM; 170 } 171 172 ret = btrfs_search_slot(&trans, root, &key, path, 0, 1); 173 if (ret) { 174 test_err("couldn't find extent ref"); 175 btrfs_free_path(path); 176 return ret; 177 } 178 179 item = btrfs_item_ptr(path->nodes[0], path->slots[0], 180 struct btrfs_extent_item); 181 refs = btrfs_extent_refs(path->nodes[0], item); 182 btrfs_set_extent_refs(path->nodes[0], item, refs - 1); 183 btrfs_release_path(path); 184 185 key.objectid = bytenr; 186 if (parent) { 187 key.type = BTRFS_SHARED_BLOCK_REF_KEY; 188 key.offset = parent; 189 } else { 190 key.type = BTRFS_TREE_BLOCK_REF_KEY; 191 key.offset = root_objectid; 192 } 193 194 ret = btrfs_search_slot(&trans, root, &key, path, -1, 1); 195 if (ret) { 196 test_err("couldn't find backref %d", ret); 197 btrfs_free_path(path); 198 return ret; 199 } 200 btrfs_del_item(&trans, root, path); 201 btrfs_free_path(path); 202 return ret; 203 } 204 205 static int test_no_shared_qgroup(struct btrfs_root *root, 206 u32 sectorsize, u32 nodesize) 207 { 208 struct btrfs_backref_walk_ctx ctx = { 0 }; 209 struct btrfs_trans_handle trans; 210 struct btrfs_fs_info *fs_info = root->fs_info; 211 struct ulist *old_roots = NULL; 212 struct ulist *new_roots = NULL; 213 int ret; 214 215 btrfs_init_dummy_trans(&trans, fs_info); 216 217 test_msg("running qgroup add/remove tests"); 218 ret = btrfs_create_qgroup(&trans, BTRFS_FS_TREE_OBJECTID); 219 if (ret) { 220 test_err("couldn't create a qgroup %d", ret); 221 return ret; 222 } 223 224 ctx.bytenr = nodesize; 225 ctx.trans = &trans; 226 ctx.fs_info = fs_info; 227 228 /* 229 * Since the test trans doesn't have the complicated delayed refs, 230 * we can only call btrfs_qgroup_account_extent() directly to test 231 * quota. 232 */ 233 ret = btrfs_find_all_roots(&ctx, false); 234 if (ret) { 235 test_err("couldn't find old roots: %d", ret); 236 return ret; 237 } 238 old_roots = ctx.roots; 239 ctx.roots = NULL; 240 241 ret = insert_normal_tree_ref(root, nodesize, nodesize, 0, 242 BTRFS_FS_TREE_OBJECTID); 243 if (ret) { 244 ulist_free(old_roots); 245 return ret; 246 } 247 248 ret = btrfs_find_all_roots(&ctx, false); 249 if (ret) { 250 ulist_free(old_roots); 251 test_err("couldn't find old roots: %d", ret); 252 return ret; 253 } 254 new_roots = ctx.roots; 255 ctx.roots = NULL; 256 257 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 258 new_roots); 259 if (ret) { 260 test_err("couldn't account space for a qgroup %d", ret); 261 return ret; 262 } 263 264 /* btrfs_qgroup_account_extent() always frees the ulists passed to it. */ 265 old_roots = NULL; 266 new_roots = NULL; 267 268 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 269 nodesize, nodesize)) { 270 test_err("qgroup counts didn't match expected values"); 271 return -EINVAL; 272 } 273 274 ret = btrfs_find_all_roots(&ctx, false); 275 if (ret) { 276 test_err("couldn't find old roots: %d", ret); 277 return ret; 278 } 279 old_roots = ctx.roots; 280 ctx.roots = NULL; 281 282 ret = remove_extent_item(root, nodesize, nodesize); 283 if (ret) { 284 ulist_free(old_roots); 285 return -EINVAL; 286 } 287 288 ret = btrfs_find_all_roots(&ctx, false); 289 if (ret) { 290 ulist_free(old_roots); 291 test_err("couldn't find old roots: %d", ret); 292 return ret; 293 } 294 new_roots = ctx.roots; 295 ctx.roots = NULL; 296 297 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 298 new_roots); 299 if (ret) { 300 test_err("couldn't account space for a qgroup %d", ret); 301 return -EINVAL; 302 } 303 304 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 0, 0)) { 305 test_err("qgroup counts didn't match expected values"); 306 return -EINVAL; 307 } 308 309 return 0; 310 } 311 312 /* 313 * Add a ref for two different roots to make sure the shared value comes out 314 * right, also remove one of the roots and make sure the exclusive count is 315 * adjusted properly. 316 */ 317 static int test_multiple_refs(struct btrfs_root *root, 318 u32 sectorsize, u32 nodesize) 319 { 320 struct btrfs_backref_walk_ctx ctx = { 0 }; 321 struct btrfs_trans_handle trans; 322 struct btrfs_fs_info *fs_info = root->fs_info; 323 struct ulist *old_roots = NULL; 324 struct ulist *new_roots = NULL; 325 int ret; 326 327 btrfs_init_dummy_trans(&trans, fs_info); 328 329 test_msg("running qgroup multiple refs test"); 330 331 /* 332 * We have BTRFS_FS_TREE_OBJECTID created already from the 333 * previous test. 334 */ 335 ret = btrfs_create_qgroup(&trans, BTRFS_FIRST_FREE_OBJECTID); 336 if (ret) { 337 test_err("couldn't create a qgroup %d", ret); 338 return ret; 339 } 340 341 ctx.bytenr = nodesize; 342 ctx.trans = &trans; 343 ctx.fs_info = fs_info; 344 345 ret = btrfs_find_all_roots(&ctx, false); 346 if (ret) { 347 test_err("couldn't find old roots: %d", ret); 348 return ret; 349 } 350 old_roots = ctx.roots; 351 ctx.roots = NULL; 352 353 ret = insert_normal_tree_ref(root, nodesize, nodesize, 0, 354 BTRFS_FS_TREE_OBJECTID); 355 if (ret) { 356 ulist_free(old_roots); 357 return ret; 358 } 359 360 ret = btrfs_find_all_roots(&ctx, false); 361 if (ret) { 362 ulist_free(old_roots); 363 test_err("couldn't find old roots: %d", ret); 364 return ret; 365 } 366 new_roots = ctx.roots; 367 ctx.roots = NULL; 368 369 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 370 new_roots); 371 if (ret) { 372 test_err("couldn't account space for a qgroup %d", ret); 373 return ret; 374 } 375 376 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 377 nodesize, nodesize)) { 378 test_err("qgroup counts didn't match expected values"); 379 return -EINVAL; 380 } 381 382 ret = btrfs_find_all_roots(&ctx, false); 383 if (ret) { 384 test_err("couldn't find old roots: %d", ret); 385 return ret; 386 } 387 old_roots = ctx.roots; 388 ctx.roots = NULL; 389 390 ret = add_tree_ref(root, nodesize, nodesize, 0, 391 BTRFS_FIRST_FREE_OBJECTID); 392 if (ret) { 393 ulist_free(old_roots); 394 return ret; 395 } 396 397 ret = btrfs_find_all_roots(&ctx, false); 398 if (ret) { 399 ulist_free(old_roots); 400 test_err("couldn't find old roots: %d", ret); 401 return ret; 402 } 403 new_roots = ctx.roots; 404 ctx.roots = NULL; 405 406 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 407 new_roots); 408 if (ret) { 409 test_err("couldn't account space for a qgroup %d", ret); 410 return ret; 411 } 412 413 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 414 nodesize, 0)) { 415 test_err("qgroup counts didn't match expected values"); 416 return -EINVAL; 417 } 418 419 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FIRST_FREE_OBJECTID, 420 nodesize, 0)) { 421 test_err("qgroup counts didn't match expected values"); 422 return -EINVAL; 423 } 424 425 ret = btrfs_find_all_roots(&ctx, false); 426 if (ret) { 427 test_err("couldn't find old roots: %d", ret); 428 return ret; 429 } 430 old_roots = ctx.roots; 431 ctx.roots = NULL; 432 433 ret = remove_extent_ref(root, nodesize, nodesize, 0, 434 BTRFS_FIRST_FREE_OBJECTID); 435 if (ret) { 436 ulist_free(old_roots); 437 return ret; 438 } 439 440 ret = btrfs_find_all_roots(&ctx, false); 441 if (ret) { 442 ulist_free(old_roots); 443 test_err("couldn't find old roots: %d", ret); 444 return ret; 445 } 446 new_roots = ctx.roots; 447 ctx.roots = NULL; 448 449 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 450 new_roots); 451 if (ret) { 452 test_err("couldn't account space for a qgroup %d", ret); 453 return ret; 454 } 455 456 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FIRST_FREE_OBJECTID, 457 0, 0)) { 458 test_err("qgroup counts didn't match expected values"); 459 return -EINVAL; 460 } 461 462 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 463 nodesize, nodesize)) { 464 test_err("qgroup counts didn't match expected values"); 465 return -EINVAL; 466 } 467 468 return 0; 469 } 470 471 int btrfs_test_qgroups(u32 sectorsize, u32 nodesize) 472 { 473 struct btrfs_fs_info *fs_info = NULL; 474 struct btrfs_root *root; 475 struct btrfs_root *tmp_root; 476 int ret = 0; 477 478 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); 479 if (!fs_info) { 480 test_std_err(TEST_ALLOC_FS_INFO); 481 return -ENOMEM; 482 } 483 484 root = btrfs_alloc_dummy_root(fs_info); 485 if (IS_ERR(root)) { 486 test_std_err(TEST_ALLOC_ROOT); 487 ret = PTR_ERR(root); 488 goto out; 489 } 490 491 /* We are using this root as our extent root */ 492 root->root_key.objectid = BTRFS_EXTENT_TREE_OBJECTID; 493 root->root_key.type = BTRFS_ROOT_ITEM_KEY; 494 root->root_key.offset = 0; 495 btrfs_global_root_insert(root); 496 497 /* 498 * Some of the paths we test assume we have a filled out fs_info, so we 499 * just need to add the root in there so we don't panic. 500 */ 501 root->fs_info->tree_root = root; 502 root->fs_info->quota_root = root; 503 set_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags); 504 505 /* 506 * Can't use bytenr 0, some things freak out 507 * *cough*backref walking code*cough* 508 */ 509 root->node = alloc_test_extent_buffer(root->fs_info, nodesize); 510 if (IS_ERR(root->node)) { 511 test_err("couldn't allocate dummy buffer"); 512 ret = PTR_ERR(root->node); 513 goto out; 514 } 515 btrfs_set_header_level(root->node, 0); 516 btrfs_set_header_nritems(root->node, 0); 517 root->alloc_bytenr += 2 * nodesize; 518 519 tmp_root = btrfs_alloc_dummy_root(fs_info); 520 if (IS_ERR(tmp_root)) { 521 test_std_err(TEST_ALLOC_ROOT); 522 ret = PTR_ERR(tmp_root); 523 goto out; 524 } 525 526 tmp_root->root_key.objectid = BTRFS_FS_TREE_OBJECTID; 527 root->fs_info->fs_root = tmp_root; 528 ret = btrfs_insert_fs_root(root->fs_info, tmp_root); 529 if (ret) { 530 test_err("couldn't insert fs root %d", ret); 531 goto out; 532 } 533 btrfs_put_root(tmp_root); 534 535 tmp_root = btrfs_alloc_dummy_root(fs_info); 536 if (IS_ERR(tmp_root)) { 537 test_std_err(TEST_ALLOC_ROOT); 538 ret = PTR_ERR(tmp_root); 539 goto out; 540 } 541 542 tmp_root->root_key.objectid = BTRFS_FIRST_FREE_OBJECTID; 543 ret = btrfs_insert_fs_root(root->fs_info, tmp_root); 544 if (ret) { 545 test_err("couldn't insert fs root %d", ret); 546 goto out; 547 } 548 btrfs_put_root(tmp_root); 549 550 test_msg("running qgroup tests"); 551 ret = test_no_shared_qgroup(root, sectorsize, nodesize); 552 if (ret) 553 goto out; 554 ret = test_multiple_refs(root, sectorsize, nodesize); 555 out: 556 btrfs_free_dummy_root(root); 557 btrfs_free_dummy_fs_info(fs_info); 558 return ret; 559 } 560