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