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