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