1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2015 Facebook.  All rights reserved.
4  */
5 
6 #include <linux/types.h>
7 #include "btrfs-tests.h"
8 #include "../ctree.h"
9 #include "../disk-io.h"
10 #include "../free-space-tree.h"
11 #include "../transaction.h"
12 #include "../block-group.h"
13 
14 struct free_space_extent {
15 	u64 start;
16 	u64 length;
17 };
18 
19 static int __check_free_space_extents(struct btrfs_trans_handle *trans,
20 				      struct btrfs_fs_info *fs_info,
21 				      struct btrfs_block_group *cache,
22 				      struct btrfs_path *path,
23 				      const struct free_space_extent * const extents,
24 				      unsigned int num_extents)
25 {
26 	struct btrfs_free_space_info *info;
27 	struct btrfs_key key;
28 	int prev_bit = 0, bit;
29 	u64 extent_start = 0, offset, end;
30 	u32 flags, extent_count;
31 	unsigned int i;
32 	int ret;
33 
34 	info = search_free_space_info(trans, cache, path, 0);
35 	if (IS_ERR(info)) {
36 		test_err("could not find free space info");
37 		ret = PTR_ERR(info);
38 		goto out;
39 	}
40 	flags = btrfs_free_space_flags(path->nodes[0], info);
41 	extent_count = btrfs_free_space_extent_count(path->nodes[0], info);
42 
43 	if (extent_count != num_extents) {
44 		test_err("extent count is wrong");
45 		ret = -EINVAL;
46 		goto out;
47 	}
48 	if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
49 		if (path->slots[0] != 0)
50 			goto invalid;
51 		end = cache->start + cache->length;
52 		i = 0;
53 		while (++path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
54 			btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
55 			if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY)
56 				goto invalid;
57 			offset = key.objectid;
58 			while (offset < key.objectid + key.offset) {
59 				bit = free_space_test_bit(cache, path, offset);
60 				if (prev_bit == 0 && bit == 1) {
61 					extent_start = offset;
62 				} else if (prev_bit == 1 && bit == 0) {
63 					if (i >= num_extents)
64 						goto invalid;
65 					if (i >= num_extents ||
66 					    extent_start != extents[i].start ||
67 					    offset - extent_start != extents[i].length)
68 						goto invalid;
69 					i++;
70 				}
71 				prev_bit = bit;
72 				offset += fs_info->sectorsize;
73 			}
74 		}
75 		if (prev_bit == 1) {
76 			if (i >= num_extents ||
77 			    extent_start != extents[i].start ||
78 			    end - extent_start != extents[i].length)
79 				goto invalid;
80 			i++;
81 		}
82 		if (i != num_extents)
83 			goto invalid;
84 	} else {
85 		if (btrfs_header_nritems(path->nodes[0]) != num_extents + 1 ||
86 		    path->slots[0] != 0)
87 			goto invalid;
88 		for (i = 0; i < num_extents; i++) {
89 			path->slots[0]++;
90 			btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
91 			if (key.type != BTRFS_FREE_SPACE_EXTENT_KEY ||
92 			    key.objectid != extents[i].start ||
93 			    key.offset != extents[i].length)
94 				goto invalid;
95 		}
96 	}
97 
98 	ret = 0;
99 out:
100 	btrfs_release_path(path);
101 	return ret;
102 invalid:
103 	test_err("free space tree is invalid");
104 	ret = -EINVAL;
105 	goto out;
106 }
107 
108 static int check_free_space_extents(struct btrfs_trans_handle *trans,
109 				    struct btrfs_fs_info *fs_info,
110 				    struct btrfs_block_group *cache,
111 				    struct btrfs_path *path,
112 				    const struct free_space_extent * const extents,
113 				    unsigned int num_extents)
114 {
115 	struct btrfs_free_space_info *info;
116 	u32 flags;
117 	int ret;
118 
119 	info = search_free_space_info(trans, cache, path, 0);
120 	if (IS_ERR(info)) {
121 		test_err("could not find free space info");
122 		btrfs_release_path(path);
123 		return PTR_ERR(info);
124 	}
125 	flags = btrfs_free_space_flags(path->nodes[0], info);
126 	btrfs_release_path(path);
127 
128 	ret = __check_free_space_extents(trans, fs_info, cache, path, extents,
129 					 num_extents);
130 	if (ret)
131 		return ret;
132 
133 	/* Flip it to the other format and check that for good measure. */
134 	if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) {
135 		ret = convert_free_space_to_extents(trans, cache, path);
136 		if (ret) {
137 			test_err("could not convert to extents");
138 			return ret;
139 		}
140 	} else {
141 		ret = convert_free_space_to_bitmaps(trans, cache, path);
142 		if (ret) {
143 			test_err("could not convert to bitmaps");
144 			return ret;
145 		}
146 	}
147 	return __check_free_space_extents(trans, fs_info, cache, path, extents,
148 					  num_extents);
149 }
150 
151 static int test_empty_block_group(struct btrfs_trans_handle *trans,
152 				  struct btrfs_fs_info *fs_info,
153 				  struct btrfs_block_group *cache,
154 				  struct btrfs_path *path,
155 				  u32 alignment)
156 {
157 	const struct free_space_extent extents[] = {
158 		{cache->start, cache->length},
159 	};
160 
161 	return check_free_space_extents(trans, fs_info, cache, path,
162 					extents, ARRAY_SIZE(extents));
163 }
164 
165 static int test_remove_all(struct btrfs_trans_handle *trans,
166 			   struct btrfs_fs_info *fs_info,
167 			   struct btrfs_block_group *cache,
168 			   struct btrfs_path *path,
169 			   u32 alignment)
170 {
171 	const struct free_space_extent extents[] = {};
172 	int ret;
173 
174 	ret = __remove_from_free_space_tree(trans, cache, path,
175 					    cache->start,
176 					    cache->length);
177 	if (ret) {
178 		test_err("could not remove free space");
179 		return ret;
180 	}
181 
182 	return check_free_space_extents(trans, fs_info, cache, path,
183 					extents, ARRAY_SIZE(extents));
184 }
185 
186 static int test_remove_beginning(struct btrfs_trans_handle *trans,
187 				 struct btrfs_fs_info *fs_info,
188 				 struct btrfs_block_group *cache,
189 				 struct btrfs_path *path,
190 				 u32 alignment)
191 {
192 	const struct free_space_extent extents[] = {
193 		{cache->start + alignment, cache->length - alignment},
194 	};
195 	int ret;
196 
197 	ret = __remove_from_free_space_tree(trans, cache, path,
198 					    cache->start, alignment);
199 	if (ret) {
200 		test_err("could not remove free space");
201 		return ret;
202 	}
203 
204 	return check_free_space_extents(trans, fs_info, cache, path,
205 					extents, ARRAY_SIZE(extents));
206 
207 }
208 
209 static int test_remove_end(struct btrfs_trans_handle *trans,
210 			   struct btrfs_fs_info *fs_info,
211 			   struct btrfs_block_group *cache,
212 			   struct btrfs_path *path,
213 			   u32 alignment)
214 {
215 	const struct free_space_extent extents[] = {
216 		{cache->start, cache->length - alignment},
217 	};
218 	int ret;
219 
220 	ret = __remove_from_free_space_tree(trans, cache, path,
221 				    cache->start + cache->length - alignment,
222 				    alignment);
223 	if (ret) {
224 		test_err("could not remove free space");
225 		return ret;
226 	}
227 
228 	return check_free_space_extents(trans, fs_info, cache, path,
229 					extents, ARRAY_SIZE(extents));
230 }
231 
232 static int test_remove_middle(struct btrfs_trans_handle *trans,
233 			      struct btrfs_fs_info *fs_info,
234 			      struct btrfs_block_group *cache,
235 			      struct btrfs_path *path,
236 			      u32 alignment)
237 {
238 	const struct free_space_extent extents[] = {
239 		{cache->start, alignment},
240 		{cache->start + 2 * alignment, cache->length - 2 * alignment},
241 	};
242 	int ret;
243 
244 	ret = __remove_from_free_space_tree(trans, cache, path,
245 					    cache->start + alignment,
246 					    alignment);
247 	if (ret) {
248 		test_err("could not remove free space");
249 		return ret;
250 	}
251 
252 	return check_free_space_extents(trans, fs_info, cache, path,
253 					extents, ARRAY_SIZE(extents));
254 }
255 
256 static int test_merge_left(struct btrfs_trans_handle *trans,
257 			   struct btrfs_fs_info *fs_info,
258 			   struct btrfs_block_group *cache,
259 			   struct btrfs_path *path,
260 			   u32 alignment)
261 {
262 	const struct free_space_extent extents[] = {
263 		{cache->start, 2 * alignment},
264 	};
265 	int ret;
266 
267 	ret = __remove_from_free_space_tree(trans, cache, path,
268 					    cache->start, cache->length);
269 	if (ret) {
270 		test_err("could not remove free space");
271 		return ret;
272 	}
273 
274 	ret = __add_to_free_space_tree(trans, cache, path, cache->start,
275 				       alignment);
276 	if (ret) {
277 		test_err("could not add free space");
278 		return ret;
279 	}
280 
281 	ret = __add_to_free_space_tree(trans, cache, path,
282 				       cache->start + alignment,
283 				       alignment);
284 	if (ret) {
285 		test_err("could not add free space");
286 		return ret;
287 	}
288 
289 	return check_free_space_extents(trans, fs_info, cache, path,
290 					extents, ARRAY_SIZE(extents));
291 }
292 
293 static int test_merge_right(struct btrfs_trans_handle *trans,
294 			   struct btrfs_fs_info *fs_info,
295 			   struct btrfs_block_group *cache,
296 			   struct btrfs_path *path,
297 			   u32 alignment)
298 {
299 	const struct free_space_extent extents[] = {
300 		{cache->start + alignment, 2 * alignment},
301 	};
302 	int ret;
303 
304 	ret = __remove_from_free_space_tree(trans, cache, path,
305 					    cache->start, cache->length);
306 	if (ret) {
307 		test_err("could not remove free space");
308 		return ret;
309 	}
310 
311 	ret = __add_to_free_space_tree(trans, cache, path,
312 				       cache->start + 2 * alignment,
313 				       alignment);
314 	if (ret) {
315 		test_err("could not add free space");
316 		return ret;
317 	}
318 
319 	ret = __add_to_free_space_tree(trans, cache, path,
320 				       cache->start + alignment,
321 				       alignment);
322 	if (ret) {
323 		test_err("could not add free space");
324 		return ret;
325 	}
326 
327 	return check_free_space_extents(trans, fs_info, cache, path,
328 					extents, ARRAY_SIZE(extents));
329 }
330 
331 static int test_merge_both(struct btrfs_trans_handle *trans,
332 			   struct btrfs_fs_info *fs_info,
333 			   struct btrfs_block_group *cache,
334 			   struct btrfs_path *path,
335 			   u32 alignment)
336 {
337 	const struct free_space_extent extents[] = {
338 		{cache->start, 3 * alignment},
339 	};
340 	int ret;
341 
342 	ret = __remove_from_free_space_tree(trans, cache, path,
343 					    cache->start, cache->length);
344 	if (ret) {
345 		test_err("could not remove free space");
346 		return ret;
347 	}
348 
349 	ret = __add_to_free_space_tree(trans, cache, path, cache->start,
350 				       alignment);
351 	if (ret) {
352 		test_err("could not add free space");
353 		return ret;
354 	}
355 
356 	ret = __add_to_free_space_tree(trans, cache, path,
357 				       cache->start + 2 * alignment, alignment);
358 	if (ret) {
359 		test_err("could not add free space");
360 		return ret;
361 	}
362 
363 	ret = __add_to_free_space_tree(trans, cache, path,
364 				       cache->start + alignment, alignment);
365 	if (ret) {
366 		test_err("could not add free space");
367 		return ret;
368 	}
369 
370 	return check_free_space_extents(trans, fs_info, cache, path,
371 					extents, ARRAY_SIZE(extents));
372 }
373 
374 static int test_merge_none(struct btrfs_trans_handle *trans,
375 			   struct btrfs_fs_info *fs_info,
376 			   struct btrfs_block_group *cache,
377 			   struct btrfs_path *path,
378 			   u32 alignment)
379 {
380 	const struct free_space_extent extents[] = {
381 		{cache->start, alignment},
382 		{cache->start + 2 * alignment, alignment},
383 		{cache->start + 4 * alignment, alignment},
384 	};
385 	int ret;
386 
387 	ret = __remove_from_free_space_tree(trans, cache, path,
388 					    cache->start, cache->length);
389 	if (ret) {
390 		test_err("could not remove free space");
391 		return ret;
392 	}
393 
394 	ret = __add_to_free_space_tree(trans, cache, path, cache->start,
395 				       alignment);
396 	if (ret) {
397 		test_err("could not add free space");
398 		return ret;
399 	}
400 
401 	ret = __add_to_free_space_tree(trans, cache, path,
402 				       cache->start + 4 * alignment, alignment);
403 	if (ret) {
404 		test_err("could not add free space");
405 		return ret;
406 	}
407 
408 	ret = __add_to_free_space_tree(trans, cache, path,
409 				       cache->start + 2 * alignment, alignment);
410 	if (ret) {
411 		test_err("could not add free space");
412 		return ret;
413 	}
414 
415 	return check_free_space_extents(trans, fs_info, cache, path,
416 					extents, ARRAY_SIZE(extents));
417 }
418 
419 typedef int (*test_func_t)(struct btrfs_trans_handle *,
420 			   struct btrfs_fs_info *,
421 			   struct btrfs_block_group *,
422 			   struct btrfs_path *,
423 			   u32 alignment);
424 
425 static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize,
426 		    u32 nodesize, u32 alignment)
427 {
428 	struct btrfs_fs_info *fs_info;
429 	struct btrfs_root *root = NULL;
430 	struct btrfs_block_group *cache = NULL;
431 	struct btrfs_trans_handle trans;
432 	struct btrfs_path *path = NULL;
433 	int ret;
434 
435 	fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
436 	if (!fs_info) {
437 		test_std_err(TEST_ALLOC_FS_INFO);
438 		ret = -ENOMEM;
439 		goto out;
440 	}
441 
442 	root = btrfs_alloc_dummy_root(fs_info);
443 	if (IS_ERR(root)) {
444 		test_std_err(TEST_ALLOC_ROOT);
445 		ret = PTR_ERR(root);
446 		goto out;
447 	}
448 
449 	btrfs_set_super_compat_ro_flags(root->fs_info->super_copy,
450 					BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE);
451 	root->fs_info->free_space_root = root;
452 	root->fs_info->tree_root = root;
453 
454 	root->node = alloc_test_extent_buffer(root->fs_info, nodesize);
455 	if (IS_ERR(root->node)) {
456 		test_std_err(TEST_ALLOC_EXTENT_BUFFER);
457 		ret = PTR_ERR(root->node);
458 		goto out;
459 	}
460 	btrfs_set_header_level(root->node, 0);
461 	btrfs_set_header_nritems(root->node, 0);
462 	root->alloc_bytenr += 2 * nodesize;
463 
464 	cache = btrfs_alloc_dummy_block_group(fs_info, 8 * alignment);
465 	if (!cache) {
466 		test_std_err(TEST_ALLOC_BLOCK_GROUP);
467 		ret = -ENOMEM;
468 		goto out;
469 	}
470 	cache->bitmap_low_thresh = 0;
471 	cache->bitmap_high_thresh = (u32)-1;
472 	cache->needs_free_space = 1;
473 	cache->fs_info = root->fs_info;
474 
475 	btrfs_init_dummy_trans(&trans, root->fs_info);
476 
477 	path = btrfs_alloc_path();
478 	if (!path) {
479 		test_std_err(TEST_ALLOC_ROOT);
480 		ret = -ENOMEM;
481 		goto out;
482 	}
483 
484 	ret = add_block_group_free_space(&trans, cache);
485 	if (ret) {
486 		test_err("could not add block group free space");
487 		goto out;
488 	}
489 
490 	if (bitmaps) {
491 		ret = convert_free_space_to_bitmaps(&trans, cache, path);
492 		if (ret) {
493 			test_err("could not convert block group to bitmaps");
494 			goto out;
495 		}
496 	}
497 
498 	ret = test_func(&trans, root->fs_info, cache, path, alignment);
499 	if (ret)
500 		goto out;
501 
502 	ret = remove_block_group_free_space(&trans, cache);
503 	if (ret) {
504 		test_err("could not remove block group free space");
505 		goto out;
506 	}
507 
508 	if (btrfs_header_nritems(root->node) != 0) {
509 		test_err("free space tree has leftover items");
510 		ret = -EINVAL;
511 		goto out;
512 	}
513 
514 	ret = 0;
515 out:
516 	btrfs_free_path(path);
517 	btrfs_free_dummy_block_group(cache);
518 	btrfs_free_dummy_root(root);
519 	btrfs_free_dummy_fs_info(fs_info);
520 	return ret;
521 }
522 
523 static int run_test_both_formats(test_func_t test_func, u32 sectorsize,
524 				 u32 nodesize, u32 alignment)
525 {
526 	int test_ret = 0;
527 	int ret;
528 
529 	ret = run_test(test_func, 0, sectorsize, nodesize, alignment);
530 	if (ret) {
531 		test_err(
532 	"%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u",
533 			 test_func, sectorsize, nodesize, alignment);
534 		test_ret = ret;
535 	}
536 
537 	ret = run_test(test_func, 1, sectorsize, nodesize, alignment);
538 	if (ret) {
539 		test_err(
540 	"%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u",
541 			 test_func, sectorsize, nodesize, alignment);
542 		test_ret = ret;
543 	}
544 
545 	return test_ret;
546 }
547 
548 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize)
549 {
550 	test_func_t tests[] = {
551 		test_empty_block_group,
552 		test_remove_all,
553 		test_remove_beginning,
554 		test_remove_end,
555 		test_remove_middle,
556 		test_merge_left,
557 		test_merge_right,
558 		test_merge_both,
559 		test_merge_none,
560 	};
561 	u32 bitmap_alignment;
562 	int test_ret = 0;
563 	int i;
564 
565 	/*
566 	 * Align some operations to a page to flush out bugs in the extent
567 	 * buffer bitmap handling of highmem.
568 	 */
569 	bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE;
570 
571 	test_msg("running free space tree tests");
572 	for (i = 0; i < ARRAY_SIZE(tests); i++) {
573 		int ret;
574 
575 		ret = run_test_both_formats(tests[i], sectorsize, nodesize,
576 					    sectorsize);
577 		if (ret)
578 			test_ret = ret;
579 
580 		ret = run_test_both_formats(tests[i], sectorsize, nodesize,
581 					    bitmap_alignment);
582 		if (ret)
583 			test_ret = ret;
584 	}
585 
586 	return test_ret;
587 }
588