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 if (ret) { 245 ulist_free(old_roots); 246 test_msg("Couldn't find old roots: %d\n", ret); 247 return ret; 248 } 249 250 ret = insert_normal_tree_ref(root, nodesize, nodesize, 0, 251 BTRFS_FS_TREE_OBJECTID); 252 if (ret) 253 return ret; 254 255 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); 256 if (ret) { 257 ulist_free(old_roots); 258 ulist_free(new_roots); 259 test_msg("Couldn't find old roots: %d\n", ret); 260 return ret; 261 } 262 263 ret = btrfs_qgroup_account_extent(&trans, fs_info, nodesize, 264 nodesize, old_roots, new_roots); 265 if (ret) { 266 test_msg("Couldn't account space for a qgroup %d\n", ret); 267 return ret; 268 } 269 270 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 271 nodesize, nodesize)) { 272 test_msg("Qgroup counts didn't match expected values\n"); 273 return -EINVAL; 274 } 275 old_roots = NULL; 276 new_roots = NULL; 277 278 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); 279 if (ret) { 280 ulist_free(old_roots); 281 test_msg("Couldn't find old roots: %d\n", ret); 282 return ret; 283 } 284 285 ret = remove_extent_item(root, nodesize, nodesize); 286 if (ret) 287 return -EINVAL; 288 289 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); 290 if (ret) { 291 ulist_free(old_roots); 292 ulist_free(new_roots); 293 test_msg("Couldn't find old roots: %d\n", ret); 294 return ret; 295 } 296 297 ret = btrfs_qgroup_account_extent(&trans, fs_info, nodesize, 298 nodesize, old_roots, new_roots); 299 if (ret) { 300 test_msg("Couldn't account space for a qgroup %d\n", ret); 301 return -EINVAL; 302 } 303 304 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 0, 0)) { 305 test_msg("Qgroup counts didn't match expected values\n"); 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_trans_handle trans; 321 struct btrfs_fs_info *fs_info = root->fs_info; 322 struct ulist *old_roots = NULL; 323 struct ulist *new_roots = NULL; 324 int ret; 325 326 btrfs_init_dummy_trans(&trans); 327 328 test_msg("Qgroup multiple refs test\n"); 329 330 /* 331 * We have BTRFS_FS_TREE_OBJECTID created already from the 332 * previous test. 333 */ 334 ret = btrfs_create_qgroup(NULL, fs_info, BTRFS_FIRST_FREE_OBJECTID); 335 if (ret) { 336 test_msg("Couldn't create a qgroup %d\n", ret); 337 return ret; 338 } 339 340 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); 341 if (ret) { 342 ulist_free(old_roots); 343 test_msg("Couldn't find old roots: %d\n", ret); 344 return ret; 345 } 346 347 ret = insert_normal_tree_ref(root, nodesize, nodesize, 0, 348 BTRFS_FS_TREE_OBJECTID); 349 if (ret) 350 return ret; 351 352 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); 353 if (ret) { 354 ulist_free(old_roots); 355 ulist_free(new_roots); 356 test_msg("Couldn't find old roots: %d\n", ret); 357 return ret; 358 } 359 360 ret = btrfs_qgroup_account_extent(&trans, fs_info, nodesize, 361 nodesize, old_roots, new_roots); 362 if (ret) { 363 test_msg("Couldn't account space for a qgroup %d\n", ret); 364 return ret; 365 } 366 367 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 368 nodesize, nodesize)) { 369 test_msg("Qgroup counts didn't match expected values\n"); 370 return -EINVAL; 371 } 372 373 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); 374 if (ret) { 375 ulist_free(old_roots); 376 test_msg("Couldn't find old roots: %d\n", ret); 377 return ret; 378 } 379 380 ret = add_tree_ref(root, nodesize, nodesize, 0, 381 BTRFS_FIRST_FREE_OBJECTID); 382 if (ret) 383 return ret; 384 385 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); 386 if (ret) { 387 ulist_free(old_roots); 388 ulist_free(new_roots); 389 test_msg("Couldn't find old roots: %d\n", ret); 390 return ret; 391 } 392 393 ret = btrfs_qgroup_account_extent(&trans, fs_info, nodesize, 394 nodesize, old_roots, new_roots); 395 if (ret) { 396 test_msg("Couldn't account space for a qgroup %d\n", ret); 397 return ret; 398 } 399 400 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 401 nodesize, 0)) { 402 test_msg("Qgroup counts didn't match expected values\n"); 403 return -EINVAL; 404 } 405 406 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FIRST_FREE_OBJECTID, 407 nodesize, 0)) { 408 test_msg("Qgroup counts didn't match expected values\n"); 409 return -EINVAL; 410 } 411 412 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &old_roots); 413 if (ret) { 414 ulist_free(old_roots); 415 test_msg("Couldn't find old roots: %d\n", ret); 416 return ret; 417 } 418 419 ret = remove_extent_ref(root, nodesize, nodesize, 0, 420 BTRFS_FIRST_FREE_OBJECTID); 421 if (ret) 422 return ret; 423 424 ret = btrfs_find_all_roots(&trans, fs_info, nodesize, 0, &new_roots); 425 if (ret) { 426 ulist_free(old_roots); 427 ulist_free(new_roots); 428 test_msg("Couldn't find old roots: %d\n", ret); 429 return ret; 430 } 431 432 ret = btrfs_qgroup_account_extent(&trans, fs_info, nodesize, 433 nodesize, old_roots, new_roots); 434 if (ret) { 435 test_msg("Couldn't account space for a qgroup %d\n", ret); 436 return ret; 437 } 438 439 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FIRST_FREE_OBJECTID, 440 0, 0)) { 441 test_msg("Qgroup counts didn't match expected values\n"); 442 return -EINVAL; 443 } 444 445 if (btrfs_verify_qgroup_counts(fs_info, BTRFS_FS_TREE_OBJECTID, 446 nodesize, nodesize)) { 447 test_msg("Qgroup counts didn't match expected values\n"); 448 return -EINVAL; 449 } 450 451 return 0; 452 } 453 454 int btrfs_test_qgroups(u32 sectorsize, u32 nodesize) 455 { 456 struct btrfs_root *root; 457 struct btrfs_root *tmp_root; 458 int ret = 0; 459 460 root = btrfs_alloc_dummy_root(sectorsize, nodesize); 461 if (IS_ERR(root)) { 462 test_msg("Couldn't allocate root\n"); 463 return PTR_ERR(root); 464 } 465 466 root->fs_info = btrfs_alloc_dummy_fs_info(); 467 if (!root->fs_info) { 468 test_msg("Couldn't allocate dummy fs info\n"); 469 ret = -ENOMEM; 470 goto out; 471 } 472 /* We are using this root as our extent root */ 473 root->fs_info->extent_root = root; 474 475 /* 476 * Some of the paths we test assume we have a filled out fs_info, so we 477 * just need to add the root in there so we don't panic. 478 */ 479 root->fs_info->tree_root = root; 480 root->fs_info->quota_root = root; 481 root->fs_info->quota_enabled = 1; 482 483 /* 484 * Can't use bytenr 0, some things freak out 485 * *cough*backref walking code*cough* 486 */ 487 root->node = alloc_test_extent_buffer(root->fs_info, nodesize, 488 nodesize); 489 if (!root->node) { 490 test_msg("Couldn't allocate dummy buffer\n"); 491 ret = -ENOMEM; 492 goto out; 493 } 494 btrfs_set_header_level(root->node, 0); 495 btrfs_set_header_nritems(root->node, 0); 496 root->alloc_bytenr += 2 * nodesize; 497 498 tmp_root = btrfs_alloc_dummy_root(sectorsize, nodesize); 499 if (IS_ERR(tmp_root)) { 500 test_msg("Couldn't allocate a fs root\n"); 501 ret = PTR_ERR(tmp_root); 502 goto out; 503 } 504 505 tmp_root->root_key.objectid = BTRFS_FS_TREE_OBJECTID; 506 root->fs_info->fs_root = tmp_root; 507 ret = btrfs_insert_fs_root(root->fs_info, tmp_root); 508 if (ret) { 509 test_msg("Couldn't insert fs root %d\n", ret); 510 goto out; 511 } 512 513 tmp_root = btrfs_alloc_dummy_root(sectorsize, nodesize); 514 if (IS_ERR(tmp_root)) { 515 test_msg("Couldn't allocate a fs root\n"); 516 ret = PTR_ERR(tmp_root); 517 goto out; 518 } 519 520 tmp_root->root_key.objectid = BTRFS_FIRST_FREE_OBJECTID; 521 ret = btrfs_insert_fs_root(root->fs_info, tmp_root); 522 if (ret) { 523 test_msg("Couldn't insert fs root %d\n", ret); 524 goto out; 525 } 526 527 test_msg("Running qgroup tests\n"); 528 ret = test_no_shared_qgroup(root, sectorsize, nodesize); 529 if (ret) 530 goto out; 531 ret = test_multiple_refs(root, sectorsize, nodesize); 532 out: 533 btrfs_free_dummy_root(root); 534 return ret; 535 } 536