1
2
3
4
5
6#include <linux/slab.h>
7#include "btrfs-tests.h"
8#include "../ctree.h"
9#include "../disk-io.h"
10#include "../free-space-cache.h"
11#include "../block-group.h"
12
13#define BITS_PER_BITMAP (PAGE_SIZE * 8UL)
14
15
16
17
18
19
20static int test_extents(struct btrfs_block_group *cache)
21{
22 int ret = 0;
23
24 test_msg("running extent only tests");
25
26
27 ret = btrfs_add_free_space(cache, 0, SZ_4M);
28 if (ret) {
29 test_err("error adding initial extents %d", ret);
30 return ret;
31 }
32
33 ret = btrfs_remove_free_space(cache, 0, SZ_4M);
34 if (ret) {
35 test_err("error removing extent %d", ret);
36 return ret;
37 }
38
39 if (test_check_exists(cache, 0, SZ_4M)) {
40 test_err("full remove left some lingering space");
41 return -1;
42 }
43
44
45 ret = btrfs_add_free_space(cache, 0, SZ_4M);
46 if (ret) {
47 test_err("error adding half extent %d", ret);
48 return ret;
49 }
50
51 ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_1M);
52 if (ret) {
53 test_err("error removing tail end %d", ret);
54 return ret;
55 }
56
57 ret = btrfs_remove_free_space(cache, 0, SZ_1M);
58 if (ret) {
59 test_err("error removing front end %d", ret);
60 return ret;
61 }
62
63 ret = btrfs_remove_free_space(cache, SZ_2M, 4096);
64 if (ret) {
65 test_err("error removing middle piece %d", ret);
66 return ret;
67 }
68
69 if (test_check_exists(cache, 0, SZ_1M)) {
70 test_err("still have space at the front");
71 return -1;
72 }
73
74 if (test_check_exists(cache, SZ_2M, 4096)) {
75 test_err("still have space in the middle");
76 return -1;
77 }
78
79 if (test_check_exists(cache, 3 * SZ_1M, SZ_1M)) {
80 test_err("still have space at the end");
81 return -1;
82 }
83
84
85 __btrfs_remove_free_space_cache(cache->free_space_ctl);
86
87 return 0;
88}
89
90static int test_bitmaps(struct btrfs_block_group *cache, u32 sectorsize)
91{
92 u64 next_bitmap_offset;
93 int ret;
94
95 test_msg("running bitmap only tests");
96
97 ret = test_add_free_space_entry(cache, 0, SZ_4M, 1);
98 if (ret) {
99 test_err("couldn't create a bitmap entry %d", ret);
100 return ret;
101 }
102
103 ret = btrfs_remove_free_space(cache, 0, SZ_4M);
104 if (ret) {
105 test_err("error removing bitmap full range %d", ret);
106 return ret;
107 }
108
109 if (test_check_exists(cache, 0, SZ_4M)) {
110 test_err("left some space in bitmap");
111 return -1;
112 }
113
114 ret = test_add_free_space_entry(cache, 0, SZ_4M, 1);
115 if (ret) {
116 test_err("couldn't add to our bitmap entry %d", ret);
117 return ret;
118 }
119
120 ret = btrfs_remove_free_space(cache, SZ_1M, SZ_2M);
121 if (ret) {
122 test_err("couldn't remove middle chunk %d", ret);
123 return ret;
124 }
125
126
127
128
129
130 next_bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize);
131
132
133 ret = test_add_free_space_entry(cache, next_bitmap_offset - SZ_2M,
134 SZ_4M, 1);
135 if (ret) {
136 test_err("couldn't add space that straddles two bitmaps %d",
137 ret);
138 return ret;
139 }
140
141 ret = btrfs_remove_free_space(cache, next_bitmap_offset - SZ_1M, SZ_2M);
142 if (ret) {
143 test_err("couldn't remove overlapping space %d", ret);
144 return ret;
145 }
146
147 if (test_check_exists(cache, next_bitmap_offset - SZ_1M, SZ_2M)) {
148 test_err("left some space when removing overlapping");
149 return -1;
150 }
151
152 __btrfs_remove_free_space_cache(cache->free_space_ctl);
153
154 return 0;
155}
156
157
158static int test_bitmaps_and_extents(struct btrfs_block_group *cache,
159 u32 sectorsize)
160{
161 u64 bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize);
162 int ret;
163
164 test_msg("running bitmap and extent tests");
165
166
167
168
169
170
171 ret = test_add_free_space_entry(cache, SZ_4M, SZ_1M, 1);
172 if (ret) {
173 test_err("couldn't create bitmap entry %d", ret);
174 return ret;
175 }
176
177 ret = test_add_free_space_entry(cache, 0, SZ_1M, 0);
178 if (ret) {
179 test_err("couldn't add extent entry %d", ret);
180 return ret;
181 }
182
183 ret = btrfs_remove_free_space(cache, 0, SZ_1M);
184 if (ret) {
185 test_err("couldn't remove extent entry %d", ret);
186 return ret;
187 }
188
189 if (test_check_exists(cache, 0, SZ_1M)) {
190 test_err("left remnants after our remove");
191 return -1;
192 }
193
194
195 ret = test_add_free_space_entry(cache, 0, SZ_1M, 0);
196 if (ret) {
197 test_err("couldn't re-add extent entry %d", ret);
198 return ret;
199 }
200
201 ret = btrfs_remove_free_space(cache, SZ_4M, SZ_1M);
202 if (ret) {
203 test_err("couldn't remove from bitmap %d", ret);
204 return ret;
205 }
206
207 if (test_check_exists(cache, SZ_4M, SZ_1M)) {
208 test_err("left remnants in the bitmap");
209 return -1;
210 }
211
212
213
214
215
216 ret = test_add_free_space_entry(cache, SZ_1M, SZ_4M, 1);
217 if (ret) {
218 test_err("couldn't add to a bitmap %d", ret);
219 return ret;
220 }
221
222 ret = btrfs_remove_free_space(cache, SZ_512K, 3 * SZ_1M);
223 if (ret) {
224 test_err("couldn't remove overlapping space %d", ret);
225 return ret;
226 }
227
228 if (test_check_exists(cache, SZ_512K, 3 * SZ_1M)) {
229 test_err("left over pieces after removing overlapping");
230 return -1;
231 }
232
233 __btrfs_remove_free_space_cache(cache->free_space_ctl);
234
235
236 ret = test_add_free_space_entry(cache, SZ_4M, SZ_4M, 1);
237 if (ret) {
238 test_err("couldn't add space to the bitmap %d", ret);
239 return ret;
240 }
241
242 ret = test_add_free_space_entry(cache, SZ_2M, SZ_2M, 0);
243 if (ret) {
244 test_err("couldn't add extent to the cache %d", ret);
245 return ret;
246 }
247
248 ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_4M);
249 if (ret) {
250 test_err("problem removing overlapping space %d", ret);
251 return ret;
252 }
253
254 if (test_check_exists(cache, 3 * SZ_1M, SZ_4M)) {
255 test_err("left something behind when removing space");
256 return -1;
257 }
258
259
260
261
262
263
264
265
266
267
268
269 __btrfs_remove_free_space_cache(cache->free_space_ctl);
270 ret = test_add_free_space_entry(cache, bitmap_offset + SZ_4M, SZ_4M, 1);
271 if (ret) {
272 test_err("couldn't add bitmap %d", ret);
273 return ret;
274 }
275
276 ret = test_add_free_space_entry(cache, bitmap_offset - SZ_1M,
277 5 * SZ_1M, 0);
278 if (ret) {
279 test_err("couldn't add extent entry %d", ret);
280 return ret;
281 }
282
283 ret = btrfs_remove_free_space(cache, bitmap_offset + SZ_1M, 5 * SZ_1M);
284 if (ret) {
285 test_err("failed to free our space %d", ret);
286 return ret;
287 }
288
289 if (test_check_exists(cache, bitmap_offset + SZ_1M, 5 * SZ_1M)) {
290 test_err("left stuff over");
291 return -1;
292 }
293
294 __btrfs_remove_free_space_cache(cache->free_space_ctl);
295
296
297
298
299
300
301
302 ret = test_add_free_space_entry(cache, SZ_1M, SZ_2M, 1);
303 if (ret) {
304 test_err("couldn't add bitmap entry %d", ret);
305 return ret;
306 }
307
308 ret = test_add_free_space_entry(cache, 3 * SZ_1M, SZ_1M, 0);
309 if (ret) {
310 test_err("couldn't add extent entry %d", ret);
311 return ret;
312 }
313
314 ret = btrfs_remove_free_space(cache, SZ_1M, 3 * SZ_1M);
315 if (ret) {
316 test_err("error removing bitmap and extent overlapping %d", ret);
317 return ret;
318 }
319
320 __btrfs_remove_free_space_cache(cache->free_space_ctl);
321 return 0;
322}
323
324
325static bool test_use_bitmap(struct btrfs_free_space_ctl *ctl,
326 struct btrfs_free_space *info)
327{
328 return ctl->free_extents > 0;
329}
330
331
332static int
333check_num_extents_and_bitmaps(const struct btrfs_block_group *cache,
334 const int num_extents,
335 const int num_bitmaps)
336{
337 if (cache->free_space_ctl->free_extents != num_extents) {
338 test_err(
339 "incorrect # of extent entries in the cache: %d, expected %d",
340 cache->free_space_ctl->free_extents, num_extents);
341 return -EINVAL;
342 }
343 if (cache->free_space_ctl->total_bitmaps != num_bitmaps) {
344 test_err(
345 "incorrect # of extent entries in the cache: %d, expected %d",
346 cache->free_space_ctl->total_bitmaps, num_bitmaps);
347 return -EINVAL;
348 }
349 return 0;
350}
351
352
353static int check_cache_empty(struct btrfs_block_group *cache)
354{
355 u64 offset;
356 u64 max_extent_size;
357
358
359
360
361
362 if (cache->free_space_ctl->free_space != 0) {
363 test_err("cache free space is not 0");
364 return -EINVAL;
365 }
366
367
368 offset = btrfs_find_space_for_alloc(cache, 0, 4096, 0,
369 &max_extent_size);
370 if (offset != 0) {
371 test_err("space allocation did not fail, returned offset: %llu",
372 offset);
373 return -EINVAL;
374 }
375
376
377 return check_num_extents_and_bitmaps(cache, 0, 0);
378}
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394static int
395test_steal_space_from_bitmap_to_extent(struct btrfs_block_group *cache,
396 u32 sectorsize)
397{
398 int ret;
399 u64 offset;
400 u64 max_extent_size;
401 const struct btrfs_free_space_op test_free_space_ops = {
402 .use_bitmap = test_use_bitmap,
403 };
404 const struct btrfs_free_space_op *orig_free_space_ops;
405
406 test_msg("running space stealing from bitmap to extent tests");
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426 orig_free_space_ops = cache->free_space_ctl->op;
427 cache->free_space_ctl->op = &test_free_space_ops;
428
429
430
431
432 ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0);
433 if (ret) {
434 test_err("couldn't add extent entry %d", ret);
435 return ret;
436 }
437
438
439 ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K,
440 SZ_128M - SZ_512K, 1);
441 if (ret) {
442 test_err("couldn't add bitmap entry %d", ret);
443 return ret;
444 }
445
446 ret = check_num_extents_and_bitmaps(cache, 2, 1);
447 if (ret)
448 return ret;
449
450
451
452
453
454
455
456
457 ret = btrfs_remove_free_space(cache,
458 SZ_128M + 768 * SZ_1K,
459 SZ_128M - 768 * SZ_1K);
460 if (ret) {
461 test_err("failed to free part of bitmap space %d", ret);
462 return ret;
463 }
464
465
466 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) {
467 test_err("free space range missing");
468 return -ENOENT;
469 }
470 if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) {
471 test_err("free space range missing");
472 return -ENOENT;
473 }
474
475
476
477
478
479 if (test_check_exists(cache, SZ_128M + 768 * SZ_1K,
480 SZ_128M - 768 * SZ_1K)) {
481 test_err("bitmap region not removed from space cache");
482 return -EINVAL;
483 }
484
485
486
487
488
489 if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) {
490 test_err("invalid bitmap region marked as free");
491 return -EINVAL;
492 }
493
494
495
496
497
498 if (test_check_exists(cache, SZ_128M, SZ_256K)) {
499 test_err("invalid bitmap region marked as free");
500 return -EINVAL;
501 }
502
503
504
505
506
507
508 ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K);
509 if (ret) {
510 test_err("error adding free space: %d", ret);
511 return ret;
512 }
513
514 if (!test_check_exists(cache, SZ_128M, SZ_512K)) {
515 test_err("bitmap region not marked as free");
516 return -ENOENT;
517 }
518
519
520
521
522
523 ret = check_num_extents_and_bitmaps(cache, 2, 1);
524 if (ret)
525 return ret;
526
527
528
529
530
531
532
533 ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, sectorsize);
534 if (ret) {
535 test_err("error adding free space: %d", ret);
536 return ret;
537 }
538
539
540
541
542
543 ret = check_num_extents_and_bitmaps(cache, 2, 1);
544 if (ret)
545 return ret;
546
547
548
549
550
551
552 ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K);
553 if (ret) {
554 test_err("error adding free space: %d", ret);
555 return ret;
556 }
557
558 if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) {
559 test_err("extent region not marked as free");
560 return -ENOENT;
561 }
562
563
564
565
566
567 ret = check_num_extents_and_bitmaps(cache, 2, 1);
568 if (ret)
569 return ret;
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) {
587 test_err("expected region not marked as free");
588 return -ENOENT;
589 }
590
591 if (cache->free_space_ctl->free_space != (SZ_1M + sectorsize)) {
592 test_err("cache free space is not 1Mb + %u", sectorsize);
593 return -EINVAL;
594 }
595
596 offset = btrfs_find_space_for_alloc(cache,
597 0, SZ_1M, 0,
598 &max_extent_size);
599 if (offset != (SZ_128M - SZ_256K)) {
600 test_err(
601 "failed to allocate 1Mb from space cache, returned offset is: %llu",
602 offset);
603 return -EINVAL;
604 }
605
606
607
608
609
610 ret = check_num_extents_and_bitmaps(cache, 1, 1);
611 if (ret)
612 return ret;
613
614 if (cache->free_space_ctl->free_space != sectorsize) {
615 test_err("cache free space is not %u", sectorsize);
616 return -EINVAL;
617 }
618
619 offset = btrfs_find_space_for_alloc(cache,
620 0, sectorsize, 0,
621 &max_extent_size);
622 if (offset != (SZ_128M + SZ_16M)) {
623 test_err("failed to allocate %u, returned offset : %llu",
624 sectorsize, offset);
625 return -EINVAL;
626 }
627
628 ret = check_cache_empty(cache);
629 if (ret)
630 return ret;
631
632 __btrfs_remove_free_space_cache(cache->free_space_ctl);
633
634
635
636
637
638
639
640
641
642
643 ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0);
644 if (ret) {
645 test_err("couldn't add extent entry %d", ret);
646 return ret;
647 }
648
649
650 ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1);
651 if (ret) {
652 test_err("couldn't add bitmap entry %d", ret);
653 return ret;
654 }
655
656 ret = check_num_extents_and_bitmaps(cache, 2, 1);
657 if (ret)
658 return ret;
659
660
661
662
663
664
665
666
667 ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K);
668 if (ret) {
669 test_err("failed to free part of bitmap space %d", ret);
670 return ret;
671 }
672
673
674 if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) {
675 test_err("free space range missing");
676 return -ENOENT;
677 }
678 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) {
679 test_err("free space range missing");
680 return -ENOENT;
681 }
682
683
684
685
686
687 if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) {
688 test_err("bitmap region not removed from space cache");
689 return -EINVAL;
690 }
691
692
693
694
695
696 if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
697 test_err("invalid bitmap region marked as free");
698 return -EINVAL;
699 }
700
701
702
703
704
705
706 ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K);
707 if (ret) {
708 test_err("error adding free space: %d", ret);
709 return ret;
710 }
711
712 if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
713 test_err("bitmap region not marked as free");
714 return -ENOENT;
715 }
716
717
718
719
720
721 ret = check_num_extents_and_bitmaps(cache, 2, 1);
722 if (ret)
723 return ret;
724
725
726
727
728
729
730
731 ret = btrfs_add_free_space(cache, SZ_32M, 2 * sectorsize);
732 if (ret) {
733 test_err("error adding free space: %d", ret);
734 return ret;
735 }
736
737
738
739
740
741
742 ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K);
743 if (ret) {
744 test_err("error adding free space: %d", ret);
745 return ret;
746 }
747
748 if (!test_check_exists(cache, SZ_128M, SZ_128K)) {
749 test_err("extent region not marked as free");
750 return -ENOENT;
751 }
752
753
754
755
756
757 ret = check_num_extents_and_bitmaps(cache, 2, 1);
758 if (ret)
759 return ret;
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) {
777 test_err("expected region not marked as free");
778 return -ENOENT;
779 }
780
781 if (cache->free_space_ctl->free_space != (SZ_1M + 2 * sectorsize)) {
782 test_err("cache free space is not 1Mb + %u", 2 * sectorsize);
783 return -EINVAL;
784 }
785
786 offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0,
787 &max_extent_size);
788 if (offset != (SZ_128M - 768 * SZ_1K)) {
789 test_err(
790 "failed to allocate 1Mb from space cache, returned offset is: %llu",
791 offset);
792 return -EINVAL;
793 }
794
795
796
797
798
799 ret = check_num_extents_and_bitmaps(cache, 1, 1);
800 if (ret)
801 return ret;
802
803 if (cache->free_space_ctl->free_space != 2 * sectorsize) {
804 test_err("cache free space is not %u", 2 * sectorsize);
805 return -EINVAL;
806 }
807
808 offset = btrfs_find_space_for_alloc(cache,
809 0, 2 * sectorsize, 0,
810 &max_extent_size);
811 if (offset != SZ_32M) {
812 test_err("failed to allocate %u, offset: %llu",
813 2 * sectorsize, offset);
814 return -EINVAL;
815 }
816
817 ret = check_cache_empty(cache);
818 if (ret)
819 return ret;
820
821 cache->free_space_ctl->op = orig_free_space_ops;
822 __btrfs_remove_free_space_cache(cache->free_space_ctl);
823
824 return 0;
825}
826
827int btrfs_test_free_space_cache(u32 sectorsize, u32 nodesize)
828{
829 struct btrfs_fs_info *fs_info;
830 struct btrfs_block_group *cache;
831 struct btrfs_root *root = NULL;
832 int ret = -ENOMEM;
833
834 test_msg("running btrfs free space cache tests");
835 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
836 if (!fs_info) {
837 test_std_err(TEST_ALLOC_FS_INFO);
838 return -ENOMEM;
839 }
840
841
842
843
844
845
846 cache = btrfs_alloc_dummy_block_group(fs_info,
847 BITS_PER_BITMAP * sectorsize + PAGE_SIZE);
848 if (!cache) {
849 test_std_err(TEST_ALLOC_BLOCK_GROUP);
850 btrfs_free_dummy_fs_info(fs_info);
851 return 0;
852 }
853
854 root = btrfs_alloc_dummy_root(fs_info);
855 if (IS_ERR(root)) {
856 test_std_err(TEST_ALLOC_ROOT);
857 ret = PTR_ERR(root);
858 goto out;
859 }
860
861 root->fs_info->extent_root = root;
862
863 ret = test_extents(cache);
864 if (ret)
865 goto out;
866 ret = test_bitmaps(cache, sectorsize);
867 if (ret)
868 goto out;
869 ret = test_bitmaps_and_extents(cache, sectorsize);
870 if (ret)
871 goto out;
872
873 ret = test_steal_space_from_bitmap_to_extent(cache, sectorsize);
874out:
875 btrfs_free_dummy_block_group(cache);
876 btrfs_free_dummy_root(root);
877 btrfs_free_dummy_fs_info(fs_info);
878 return ret;
879}
880