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