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