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
insert_normal_tree_ref(struct btrfs_root * root,u64 bytenr,u64 num_bytes,u64 parent,u64 root_objectid)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
add_tree_ref(struct btrfs_root * root,u64 bytenr,u64 num_bytes,u64 parent,u64 root_objectid)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
remove_extent_item(struct btrfs_root * root,u64 bytenr,u64 num_bytes)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
remove_extent_ref(struct btrfs_root * root,u64 bytenr,u64 num_bytes,u64 parent,u64 root_objectid)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
test_no_shared_qgroup(struct btrfs_root * root,u32 sectorsize,u32 nodesize)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 */
test_multiple_refs(struct btrfs_root * root,u32 sectorsize,u32 nodesize)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
btrfs_test_qgroups(u32 sectorsize,u32 nodesize)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 btrfs_put_root(tmp_root);
521 if (ret) {
522 test_err("couldn't insert fs root %d", ret);
523 goto out;
524 }
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 btrfs_put_root(tmp_root);
536 if (ret) {
537 test_err("couldn't insert subvolume root %d", ret);
538 goto out;
539 }
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