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