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 return ret; 191 } 192 btrfs_del_item(&trans, root, path); 193 return ret; 194 } 195 196 static int test_no_shared_qgroup(struct btrfs_root *root, 197 u32 sectorsize, u32 nodesize) 198 { 199 struct btrfs_backref_walk_ctx ctx = { 0 }; 200 struct btrfs_trans_handle trans; 201 struct btrfs_fs_info *fs_info = root->fs_info; 202 struct ulist *old_roots = NULL; 203 struct ulist *new_roots = NULL; 204 int ret; 205 206 btrfs_init_dummy_trans(&trans, fs_info); 207 208 test_msg("running qgroup add/remove tests"); 209 ret = btrfs_create_qgroup(&trans, BTRFS_FS_TREE_OBJECTID); 210 if (ret) { 211 test_err("couldn't create a qgroup %d", ret); 212 return ret; 213 } 214 215 ctx.bytenr = nodesize; 216 ctx.trans = &trans; 217 ctx.fs_info = fs_info; 218 219 /* 220 * Since the test trans doesn't have the complicated delayed refs, 221 * we can only call btrfs_qgroup_account_extent() directly to test 222 * quota. 223 */ 224 ret = btrfs_find_all_roots(&ctx, false); 225 if (ret) { 226 test_err("couldn't find old roots: %d", ret); 227 return ret; 228 } 229 old_roots = ctx.roots; 230 ctx.roots = NULL; 231 232 ret = insert_normal_tree_ref(root, nodesize, nodesize, 0, 233 BTRFS_FS_TREE_OBJECTID); 234 if (ret) { 235 ulist_free(old_roots); 236 return ret; 237 } 238 239 ret = btrfs_find_all_roots(&ctx, false); 240 if (ret) { 241 ulist_free(old_roots); 242 test_err("couldn't find old roots: %d", ret); 243 return ret; 244 } 245 new_roots = ctx.roots; 246 ctx.roots = NULL; 247 248 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 249 new_roots); 250 if (ret) { 251 test_err("couldn't account space for a qgroup %d", ret); 252 return ret; 253 } 254 255 /* btrfs_qgroup_account_extent() always frees the ulists passed to it. */ 256 old_roots = NULL; 257 new_roots = NULL; 258 259 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 260 nodesize, nodesize)) { 261 test_err("qgroup counts didn't match expected values"); 262 return -EINVAL; 263 } 264 265 ret = btrfs_find_all_roots(&ctx, false); 266 if (ret) { 267 test_err("couldn't find old roots: %d", ret); 268 return ret; 269 } 270 old_roots = ctx.roots; 271 ctx.roots = NULL; 272 273 ret = remove_extent_item(root, nodesize, nodesize); 274 if (ret) { 275 ulist_free(old_roots); 276 return -EINVAL; 277 } 278 279 ret = btrfs_find_all_roots(&ctx, false); 280 if (ret) { 281 ulist_free(old_roots); 282 test_err("couldn't find old roots: %d", ret); 283 return ret; 284 } 285 new_roots = ctx.roots; 286 ctx.roots = NULL; 287 288 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 289 new_roots); 290 if (ret) { 291 test_err("couldn't account space for a qgroup %d", ret); 292 return -EINVAL; 293 } 294 295 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 0, 0)) { 296 test_err("qgroup counts didn't match expected values"); 297 return -EINVAL; 298 } 299 300 return 0; 301 } 302 303 /* 304 * Add a ref for two different roots to make sure the shared value comes out 305 * right, also remove one of the roots and make sure the exclusive count is 306 * adjusted properly. 307 */ 308 static int test_multiple_refs(struct btrfs_root *root, 309 u32 sectorsize, u32 nodesize) 310 { 311 struct btrfs_backref_walk_ctx ctx = { 0 }; 312 struct btrfs_trans_handle trans; 313 struct btrfs_fs_info *fs_info = root->fs_info; 314 struct ulist *old_roots = NULL; 315 struct ulist *new_roots = NULL; 316 int ret; 317 318 btrfs_init_dummy_trans(&trans, fs_info); 319 320 test_msg("running qgroup multiple refs test"); 321 322 /* 323 * We have BTRFS_FS_TREE_OBJECTID created already from the 324 * previous test. 325 */ 326 ret = btrfs_create_qgroup(&trans, BTRFS_FIRST_FREE_OBJECTID); 327 if (ret) { 328 test_err("couldn't create a qgroup %d", ret); 329 return ret; 330 } 331 332 ctx.bytenr = nodesize; 333 ctx.trans = &trans; 334 ctx.fs_info = fs_info; 335 336 ret = btrfs_find_all_roots(&ctx, false); 337 if (ret) { 338 test_err("couldn't find old roots: %d", ret); 339 return ret; 340 } 341 old_roots = ctx.roots; 342 ctx.roots = NULL; 343 344 ret = insert_normal_tree_ref(root, nodesize, nodesize, 0, 345 BTRFS_FS_TREE_OBJECTID); 346 if (ret) { 347 ulist_free(old_roots); 348 return ret; 349 } 350 351 ret = btrfs_find_all_roots(&ctx, false); 352 if (ret) { 353 ulist_free(old_roots); 354 test_err("couldn't find old roots: %d", ret); 355 return ret; 356 } 357 new_roots = ctx.roots; 358 ctx.roots = NULL; 359 360 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 361 new_roots); 362 if (ret) { 363 test_err("couldn't account space for a qgroup %d", ret); 364 return ret; 365 } 366 367 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 368 nodesize, nodesize)) { 369 test_err("qgroup counts didn't match expected values"); 370 return -EINVAL; 371 } 372 373 ret = btrfs_find_all_roots(&ctx, false); 374 if (ret) { 375 test_err("couldn't find old roots: %d", ret); 376 return ret; 377 } 378 old_roots = ctx.roots; 379 ctx.roots = NULL; 380 381 ret = add_tree_ref(root, nodesize, nodesize, 0, 382 BTRFS_FIRST_FREE_OBJECTID); 383 if (ret) { 384 ulist_free(old_roots); 385 return ret; 386 } 387 388 ret = btrfs_find_all_roots(&ctx, false); 389 if (ret) { 390 ulist_free(old_roots); 391 test_err("couldn't find old roots: %d", ret); 392 return ret; 393 } 394 new_roots = ctx.roots; 395 ctx.roots = NULL; 396 397 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 398 new_roots); 399 if (ret) { 400 test_err("couldn't account space for a qgroup %d", ret); 401 return ret; 402 } 403 404 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 405 nodesize, 0)) { 406 test_err("qgroup counts didn't match expected values"); 407 return -EINVAL; 408 } 409 410 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FIRST_FREE_OBJECTID, 411 nodesize, 0)) { 412 test_err("qgroup counts didn't match expected values"); 413 return -EINVAL; 414 } 415 416 ret = btrfs_find_all_roots(&ctx, false); 417 if (ret) { 418 test_err("couldn't find old roots: %d", ret); 419 return ret; 420 } 421 old_roots = ctx.roots; 422 ctx.roots = NULL; 423 424 ret = remove_extent_ref(root, nodesize, nodesize, 0, 425 BTRFS_FIRST_FREE_OBJECTID); 426 if (ret) { 427 ulist_free(old_roots); 428 return ret; 429 } 430 431 ret = btrfs_find_all_roots(&ctx, false); 432 if (ret) { 433 ulist_free(old_roots); 434 test_err("couldn't find old roots: %d", ret); 435 return ret; 436 } 437 new_roots = ctx.roots; 438 ctx.roots = NULL; 439 440 ret = btrfs_qgroup_account_extent(&trans, nodesize, nodesize, old_roots, 441 new_roots); 442 if (ret) { 443 test_err("couldn't account space for a qgroup %d", ret); 444 return ret; 445 } 446 447 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FIRST_FREE_OBJECTID, 448 0, 0)) { 449 test_err("qgroup counts didn't match expected values"); 450 return -EINVAL; 451 } 452 453 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 454 nodesize, nodesize)) { 455 test_err("qgroup counts didn't match expected values"); 456 return -EINVAL; 457 } 458 459 return 0; 460 } 461 462 int btrfs_test_qgroups(u32 sectorsize, u32 nodesize) 463 { 464 struct btrfs_fs_info *fs_info = NULL; 465 struct btrfs_root *root; 466 struct btrfs_root *tmp_root; 467 int ret = 0; 468 469 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); 470 if (!fs_info) { 471 test_std_err(TEST_ALLOC_FS_INFO); 472 return -ENOMEM; 473 } 474 475 root = btrfs_alloc_dummy_root(fs_info); 476 if (IS_ERR(root)) { 477 test_std_err(TEST_ALLOC_ROOT); 478 ret = PTR_ERR(root); 479 goto out; 480 } 481 482 /* We are using this root as our extent root */ 483 root->root_key.objectid = BTRFS_EXTENT_TREE_OBJECTID; 484 root->root_key.type = BTRFS_ROOT_ITEM_KEY; 485 root->root_key.offset = 0; 486 btrfs_global_root_insert(root); 487 488 /* 489 * Some of the paths we test assume we have a filled out fs_info, so we 490 * just need to add the root in there so we don't panic. 491 */ 492 root->fs_info->tree_root = root; 493 root->fs_info->quota_root = root; 494 set_bit(BTRFS_FS_QUOTA_ENABLED, &fs_info->flags); 495 496 /* 497 * Can't use bytenr 0, some things freak out 498 * *cough*backref walking code*cough* 499 */ 500 root->node = alloc_test_extent_buffer(root->fs_info, nodesize); 501 if (IS_ERR(root->node)) { 502 test_err("couldn't allocate dummy buffer"); 503 ret = PTR_ERR(root->node); 504 goto out; 505 } 506 btrfs_set_header_level(root->node, 0); 507 btrfs_set_header_nritems(root->node, 0); 508 root->alloc_bytenr += 2 * nodesize; 509 510 tmp_root = btrfs_alloc_dummy_root(fs_info); 511 if (IS_ERR(tmp_root)) { 512 test_std_err(TEST_ALLOC_ROOT); 513 ret = PTR_ERR(tmp_root); 514 goto out; 515 } 516 517 tmp_root->root_key.objectid = BTRFS_FS_TREE_OBJECTID; 518 root->fs_info->fs_root = tmp_root; 519 ret = btrfs_insert_fs_root(root->fs_info, tmp_root); 520 if (ret) { 521 test_err("couldn't insert fs root %d", ret); 522 goto out; 523 } 524 btrfs_put_root(tmp_root); 525 526 tmp_root = btrfs_alloc_dummy_root(fs_info); 527 if (IS_ERR(tmp_root)) { 528 test_std_err(TEST_ALLOC_ROOT); 529 ret = PTR_ERR(tmp_root); 530 goto out; 531 } 532 533 tmp_root->root_key.objectid = BTRFS_FIRST_FREE_OBJECTID; 534 ret = btrfs_insert_fs_root(root->fs_info, tmp_root); 535 if (ret) { 536 test_err("couldn't insert fs root %d", ret); 537 goto out; 538 } 539 btrfs_put_root(tmp_root); 540 541 test_msg("running qgroup tests"); 542 ret = test_no_shared_qgroup(root, sectorsize, nodesize); 543 if (ret) 544 goto out; 545 ret = test_multiple_refs(root, sectorsize, nodesize); 546 out: 547 btrfs_free_dummy_root(root); 548 btrfs_free_dummy_fs_info(fs_info); 549 return ret; 550 } 551