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 | #include "../accessors.h" |
14 | |
15 | struct free_space_extent { |
16 | u64 start; |
17 | u64 length; |
18 | }; |
19 | |
20 | static int __check_free_space_extents(struct btrfs_trans_handle *trans, |
21 | struct btrfs_fs_info *fs_info, |
22 | struct btrfs_block_group *cache, |
23 | struct btrfs_path *path, |
24 | const struct free_space_extent * const extents, |
25 | unsigned int num_extents) |
26 | { |
27 | struct btrfs_free_space_info *info; |
28 | struct btrfs_key key; |
29 | int prev_bit = 0, bit; |
30 | u64 extent_start = 0, offset, end; |
31 | u32 flags, extent_count; |
32 | unsigned int i; |
33 | int ret; |
34 | |
35 | info = search_free_space_info(trans, block_group: cache, path, cow: 0); |
36 | if (IS_ERR(ptr: info)) { |
37 | test_err("could not find free space info" ); |
38 | ret = PTR_ERR(ptr: info); |
39 | goto out; |
40 | } |
41 | flags = btrfs_free_space_flags(eb: path->nodes[0], s: info); |
42 | extent_count = btrfs_free_space_extent_count(eb: path->nodes[0], s: info); |
43 | |
44 | if (extent_count != num_extents) { |
45 | test_err("extent count is wrong" ); |
46 | ret = -EINVAL; |
47 | goto out; |
48 | } |
49 | if (flags & BTRFS_FREE_SPACE_USING_BITMAPS) { |
50 | if (path->slots[0] != 0) |
51 | goto invalid; |
52 | end = cache->start + cache->length; |
53 | i = 0; |
54 | while (++path->slots[0] < btrfs_header_nritems(eb: path->nodes[0])) { |
55 | btrfs_item_key_to_cpu(eb: path->nodes[0], cpu_key: &key, nr: path->slots[0]); |
56 | if (key.type != BTRFS_FREE_SPACE_BITMAP_KEY) |
57 | goto invalid; |
58 | offset = key.objectid; |
59 | while (offset < key.objectid + key.offset) { |
60 | bit = free_space_test_bit(block_group: cache, path, offset); |
61 | if (prev_bit == 0 && bit == 1) { |
62 | extent_start = offset; |
63 | } else if (prev_bit == 1 && bit == 0) { |
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(eb: 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(eb: path->nodes[0], cpu_key: &key, nr: 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(p: 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, |
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, block_group: cache, path, cow: 0); |
119 | if (IS_ERR(ptr: info)) { |
120 | test_err("could not find free space info" ); |
121 | btrfs_release_path(p: path); |
122 | return PTR_ERR(ptr: info); |
123 | } |
124 | flags = btrfs_free_space_flags(eb: path->nodes[0], s: info); |
125 | btrfs_release_path(p: 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, block_group: 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, block_group: 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, |
153 | struct btrfs_path *path, |
154 | u32 alignment) |
155 | { |
156 | const struct free_space_extent extents[] = { |
157 | {cache->start, cache->length}, |
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, |
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, block_group: cache, path, |
174 | start: cache->start, |
175 | size: cache->length); |
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, |
188 | struct btrfs_path *path, |
189 | u32 alignment) |
190 | { |
191 | const struct free_space_extent extents[] = { |
192 | {cache->start + alignment, cache->length - alignment}, |
193 | }; |
194 | int ret; |
195 | |
196 | ret = __remove_from_free_space_tree(trans, block_group: cache, path, |
197 | start: cache->start, size: alignment); |
198 | if (ret) { |
199 | test_err("could not remove free space" ); |
200 | return ret; |
201 | } |
202 | |
203 | return check_free_space_extents(trans, fs_info, cache, path, |
204 | extents, ARRAY_SIZE(extents)); |
205 | |
206 | } |
207 | |
208 | static int test_remove_end(struct btrfs_trans_handle *trans, |
209 | struct btrfs_fs_info *fs_info, |
210 | struct btrfs_block_group *cache, |
211 | struct btrfs_path *path, |
212 | u32 alignment) |
213 | { |
214 | const struct free_space_extent extents[] = { |
215 | {cache->start, cache->length - alignment}, |
216 | }; |
217 | int ret; |
218 | |
219 | ret = __remove_from_free_space_tree(trans, block_group: cache, path, |
220 | start: cache->start + cache->length - alignment, |
221 | size: alignment); |
222 | if (ret) { |
223 | test_err("could not remove free space" ); |
224 | return ret; |
225 | } |
226 | |
227 | return check_free_space_extents(trans, fs_info, cache, path, |
228 | extents, ARRAY_SIZE(extents)); |
229 | } |
230 | |
231 | static int test_remove_middle(struct btrfs_trans_handle *trans, |
232 | struct btrfs_fs_info *fs_info, |
233 | struct btrfs_block_group *cache, |
234 | struct btrfs_path *path, |
235 | u32 alignment) |
236 | { |
237 | const struct free_space_extent extents[] = { |
238 | {cache->start, alignment}, |
239 | {cache->start + 2 * alignment, cache->length - 2 * alignment}, |
240 | }; |
241 | int ret; |
242 | |
243 | ret = __remove_from_free_space_tree(trans, block_group: cache, path, |
244 | start: cache->start + alignment, |
245 | size: alignment); |
246 | if (ret) { |
247 | test_err("could not remove free space" ); |
248 | return ret; |
249 | } |
250 | |
251 | return check_free_space_extents(trans, fs_info, cache, path, |
252 | extents, ARRAY_SIZE(extents)); |
253 | } |
254 | |
255 | static int test_merge_left(struct btrfs_trans_handle *trans, |
256 | struct btrfs_fs_info *fs_info, |
257 | struct btrfs_block_group *cache, |
258 | struct btrfs_path *path, |
259 | u32 alignment) |
260 | { |
261 | const struct free_space_extent extents[] = { |
262 | {cache->start, 2 * alignment}, |
263 | }; |
264 | int ret; |
265 | |
266 | ret = __remove_from_free_space_tree(trans, block_group: cache, path, |
267 | start: cache->start, size: cache->length); |
268 | if (ret) { |
269 | test_err("could not remove free space" ); |
270 | return ret; |
271 | } |
272 | |
273 | ret = __add_to_free_space_tree(trans, block_group: cache, path, start: cache->start, |
274 | size: alignment); |
275 | if (ret) { |
276 | test_err("could not add free space" ); |
277 | return ret; |
278 | } |
279 | |
280 | ret = __add_to_free_space_tree(trans, block_group: cache, path, |
281 | start: cache->start + alignment, |
282 | size: alignment); |
283 | if (ret) { |
284 | test_err("could not add free space" ); |
285 | return ret; |
286 | } |
287 | |
288 | return check_free_space_extents(trans, fs_info, cache, path, |
289 | extents, ARRAY_SIZE(extents)); |
290 | } |
291 | |
292 | static int test_merge_right(struct btrfs_trans_handle *trans, |
293 | struct btrfs_fs_info *fs_info, |
294 | struct btrfs_block_group *cache, |
295 | struct btrfs_path *path, |
296 | u32 alignment) |
297 | { |
298 | const struct free_space_extent extents[] = { |
299 | {cache->start + alignment, 2 * alignment}, |
300 | }; |
301 | int ret; |
302 | |
303 | ret = __remove_from_free_space_tree(trans, block_group: cache, path, |
304 | start: cache->start, size: cache->length); |
305 | if (ret) { |
306 | test_err("could not remove free space" ); |
307 | return ret; |
308 | } |
309 | |
310 | ret = __add_to_free_space_tree(trans, block_group: cache, path, |
311 | start: cache->start + 2 * alignment, |
312 | size: alignment); |
313 | if (ret) { |
314 | test_err("could not add free space" ); |
315 | return ret; |
316 | } |
317 | |
318 | ret = __add_to_free_space_tree(trans, block_group: cache, path, |
319 | start: cache->start + alignment, |
320 | size: alignment); |
321 | if (ret) { |
322 | test_err("could not add free space" ); |
323 | return ret; |
324 | } |
325 | |
326 | return check_free_space_extents(trans, fs_info, cache, path, |
327 | extents, ARRAY_SIZE(extents)); |
328 | } |
329 | |
330 | static int test_merge_both(struct btrfs_trans_handle *trans, |
331 | struct btrfs_fs_info *fs_info, |
332 | struct btrfs_block_group *cache, |
333 | struct btrfs_path *path, |
334 | u32 alignment) |
335 | { |
336 | const struct free_space_extent extents[] = { |
337 | {cache->start, 3 * alignment}, |
338 | }; |
339 | int ret; |
340 | |
341 | ret = __remove_from_free_space_tree(trans, block_group: cache, path, |
342 | start: cache->start, size: cache->length); |
343 | if (ret) { |
344 | test_err("could not remove free space" ); |
345 | return ret; |
346 | } |
347 | |
348 | ret = __add_to_free_space_tree(trans, block_group: cache, path, start: cache->start, |
349 | size: alignment); |
350 | if (ret) { |
351 | test_err("could not add free space" ); |
352 | return ret; |
353 | } |
354 | |
355 | ret = __add_to_free_space_tree(trans, block_group: cache, path, |
356 | start: cache->start + 2 * alignment, size: alignment); |
357 | if (ret) { |
358 | test_err("could not add free space" ); |
359 | return ret; |
360 | } |
361 | |
362 | ret = __add_to_free_space_tree(trans, block_group: cache, path, |
363 | start: cache->start + alignment, size: alignment); |
364 | if (ret) { |
365 | test_err("could not add free space" ); |
366 | return ret; |
367 | } |
368 | |
369 | return check_free_space_extents(trans, fs_info, cache, path, |
370 | extents, ARRAY_SIZE(extents)); |
371 | } |
372 | |
373 | static int test_merge_none(struct btrfs_trans_handle *trans, |
374 | struct btrfs_fs_info *fs_info, |
375 | struct btrfs_block_group *cache, |
376 | struct btrfs_path *path, |
377 | u32 alignment) |
378 | { |
379 | const struct free_space_extent extents[] = { |
380 | {cache->start, alignment}, |
381 | {cache->start + 2 * alignment, alignment}, |
382 | {cache->start + 4 * alignment, alignment}, |
383 | }; |
384 | int ret; |
385 | |
386 | ret = __remove_from_free_space_tree(trans, block_group: cache, path, |
387 | start: cache->start, size: cache->length); |
388 | if (ret) { |
389 | test_err("could not remove free space" ); |
390 | return ret; |
391 | } |
392 | |
393 | ret = __add_to_free_space_tree(trans, block_group: cache, path, start: cache->start, |
394 | size: alignment); |
395 | if (ret) { |
396 | test_err("could not add free space" ); |
397 | return ret; |
398 | } |
399 | |
400 | ret = __add_to_free_space_tree(trans, block_group: cache, path, |
401 | start: cache->start + 4 * alignment, size: alignment); |
402 | if (ret) { |
403 | test_err("could not add free space" ); |
404 | return ret; |
405 | } |
406 | |
407 | ret = __add_to_free_space_tree(trans, block_group: cache, path, |
408 | start: cache->start + 2 * alignment, size: alignment); |
409 | if (ret) { |
410 | test_err("could not add free space" ); |
411 | return ret; |
412 | } |
413 | |
414 | return check_free_space_extents(trans, fs_info, cache, path, |
415 | extents, ARRAY_SIZE(extents)); |
416 | } |
417 | |
418 | typedef int (*test_func_t)(struct btrfs_trans_handle *, |
419 | struct btrfs_fs_info *, |
420 | struct btrfs_block_group *, |
421 | struct btrfs_path *, |
422 | u32 alignment); |
423 | |
424 | static int run_test(test_func_t test_func, int bitmaps, u32 sectorsize, |
425 | u32 nodesize, u32 alignment) |
426 | { |
427 | struct btrfs_fs_info *fs_info; |
428 | struct btrfs_root *root = NULL; |
429 | struct btrfs_block_group *cache = NULL; |
430 | struct btrfs_trans_handle trans; |
431 | struct btrfs_path *path = NULL; |
432 | int ret; |
433 | |
434 | fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize); |
435 | if (!fs_info) { |
436 | test_std_err(TEST_ALLOC_FS_INFO); |
437 | ret = -ENOMEM; |
438 | goto out; |
439 | } |
440 | |
441 | root = btrfs_alloc_dummy_root(fs_info); |
442 | if (IS_ERR(ptr: root)) { |
443 | test_std_err(TEST_ALLOC_ROOT); |
444 | ret = PTR_ERR(ptr: root); |
445 | goto out; |
446 | } |
447 | |
448 | btrfs_set_super_compat_ro_flags(s: root->fs_info->super_copy, |
449 | BTRFS_FEATURE_COMPAT_RO_FREE_SPACE_TREE); |
450 | root->root_key.objectid = BTRFS_FREE_SPACE_TREE_OBJECTID; |
451 | root->root_key.type = BTRFS_ROOT_ITEM_KEY; |
452 | root->root_key.offset = 0; |
453 | btrfs_global_root_insert(root); |
454 | root->fs_info->tree_root = root; |
455 | |
456 | root->node = alloc_test_extent_buffer(fs_info: root->fs_info, start: nodesize); |
457 | if (IS_ERR(ptr: root->node)) { |
458 | test_std_err(TEST_ALLOC_EXTENT_BUFFER); |
459 | ret = PTR_ERR(ptr: root->node); |
460 | goto out; |
461 | } |
462 | btrfs_set_header_level(eb: root->node, val: 0); |
463 | btrfs_set_header_nritems(eb: root->node, val: 0); |
464 | root->alloc_bytenr += 2 * nodesize; |
465 | |
466 | cache = btrfs_alloc_dummy_block_group(fs_info, length: 8 * alignment); |
467 | if (!cache) { |
468 | test_std_err(TEST_ALLOC_BLOCK_GROUP); |
469 | ret = -ENOMEM; |
470 | goto out; |
471 | } |
472 | cache->bitmap_low_thresh = 0; |
473 | cache->bitmap_high_thresh = (u32)-1; |
474 | set_bit(nr: BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, addr: &cache->runtime_flags); |
475 | cache->fs_info = root->fs_info; |
476 | |
477 | btrfs_init_dummy_trans(trans: &trans, fs_info: root->fs_info); |
478 | |
479 | path = btrfs_alloc_path(); |
480 | if (!path) { |
481 | test_std_err(TEST_ALLOC_ROOT); |
482 | ret = -ENOMEM; |
483 | goto out; |
484 | } |
485 | |
486 | ret = add_block_group_free_space(trans: &trans, block_group: cache); |
487 | if (ret) { |
488 | test_err("could not add block group free space" ); |
489 | goto out; |
490 | } |
491 | |
492 | if (bitmaps) { |
493 | ret = convert_free_space_to_bitmaps(trans: &trans, block_group: cache, path); |
494 | if (ret) { |
495 | test_err("could not convert block group to bitmaps" ); |
496 | goto out; |
497 | } |
498 | } |
499 | |
500 | ret = test_func(&trans, root->fs_info, cache, path, alignment); |
501 | if (ret) |
502 | goto out; |
503 | |
504 | ret = remove_block_group_free_space(trans: &trans, block_group: cache); |
505 | if (ret) { |
506 | test_err("could not remove block group free space" ); |
507 | goto out; |
508 | } |
509 | |
510 | if (btrfs_header_nritems(eb: root->node) != 0) { |
511 | test_err("free space tree has leftover items" ); |
512 | ret = -EINVAL; |
513 | goto out; |
514 | } |
515 | |
516 | ret = 0; |
517 | out: |
518 | btrfs_free_path(p: path); |
519 | btrfs_free_dummy_block_group(cache); |
520 | btrfs_free_dummy_root(root); |
521 | btrfs_free_dummy_fs_info(fs_info); |
522 | return ret; |
523 | } |
524 | |
525 | static int run_test_both_formats(test_func_t test_func, u32 sectorsize, |
526 | u32 nodesize, u32 alignment) |
527 | { |
528 | int test_ret = 0; |
529 | int ret; |
530 | |
531 | ret = run_test(test_func, bitmaps: 0, sectorsize, nodesize, alignment); |
532 | if (ret) { |
533 | test_err( |
534 | "%ps failed with extents, sectorsize=%u, nodesize=%u, alignment=%u" , |
535 | test_func, sectorsize, nodesize, alignment); |
536 | test_ret = ret; |
537 | } |
538 | |
539 | ret = run_test(test_func, bitmaps: 1, sectorsize, nodesize, alignment); |
540 | if (ret) { |
541 | test_err( |
542 | "%ps failed with bitmaps, sectorsize=%u, nodesize=%u, alignment=%u" , |
543 | test_func, sectorsize, nodesize, alignment); |
544 | test_ret = ret; |
545 | } |
546 | |
547 | return test_ret; |
548 | } |
549 | |
550 | int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize) |
551 | { |
552 | test_func_t tests[] = { |
553 | test_empty_block_group, |
554 | test_remove_all, |
555 | test_remove_beginning, |
556 | test_remove_end, |
557 | test_remove_middle, |
558 | test_merge_left, |
559 | test_merge_right, |
560 | test_merge_both, |
561 | test_merge_none, |
562 | }; |
563 | u32 bitmap_alignment; |
564 | int test_ret = 0; |
565 | int i; |
566 | |
567 | /* |
568 | * Align some operations to a page to flush out bugs in the extent |
569 | * buffer bitmap handling of highmem. |
570 | */ |
571 | bitmap_alignment = BTRFS_FREE_SPACE_BITMAP_BITS * PAGE_SIZE; |
572 | |
573 | test_msg("running free space tree tests" ); |
574 | for (i = 0; i < ARRAY_SIZE(tests); i++) { |
575 | int ret; |
576 | |
577 | ret = run_test_both_formats(test_func: tests[i], sectorsize, nodesize, |
578 | alignment: sectorsize); |
579 | if (ret) |
580 | test_ret = ret; |
581 | |
582 | ret = run_test_both_formats(test_func: tests[i], sectorsize, nodesize, |
583 | alignment: bitmap_alignment); |
584 | if (ret) |
585 | test_ret = ret; |
586 | } |
587 | |
588 | return test_ret; |
589 | } |
590 | |