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