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