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
12#define BITS_PER_BITMAP (PAGE_SIZE * 8UL)
13
14
15
16
17
18
19static int test_extents(struct btrfs_block_group_cache *cache)
20{
21 int ret = 0;
22
23 test_msg("running extent only tests");
24
25
26 ret = btrfs_add_free_space(cache, 0, SZ_4M);
27 if (ret) {
28 test_err("error adding initial extents %d", ret);
29 return ret;
30 }
31
32 ret = btrfs_remove_free_space(cache, 0, SZ_4M);
33 if (ret) {
34 test_err("error removing extent %d", ret);
35 return ret;
36 }
37
38 if (test_check_exists(cache, 0, SZ_4M)) {
39 test_err("full remove left some lingering space");
40 return -1;
41 }
42
43
44 ret = btrfs_add_free_space(cache, 0, SZ_4M);
45 if (ret) {
46 test_err("error adding half extent %d", ret);
47 return ret;
48 }
49
50 ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_1M);
51 if (ret) {
52 test_err("error removing tail end %d", ret);
53 return ret;
54 }
55
56 ret = btrfs_remove_free_space(cache, 0, SZ_1M);
57 if (ret) {
58 test_err("error removing front end %d", ret);
59 return ret;
60 }
61
62 ret = btrfs_remove_free_space(cache, SZ_2M, 4096);
63 if (ret) {
64 test_err("error removing middle piece %d", ret);
65 return ret;
66 }
67
68 if (test_check_exists(cache, 0, SZ_1M)) {
69 test_err("still have space at the front");
70 return -1;
71 }
72
73 if (test_check_exists(cache, SZ_2M, 4096)) {
74 test_err("still have space in the middle");
75 return -1;
76 }
77
78 if (test_check_exists(cache, 3 * SZ_1M, SZ_1M)) {
79 test_err("still have space at the end");
80 return -1;
81 }
82
83
84 __btrfs_remove_free_space_cache(cache->free_space_ctl);
85
86 return 0;
87}
88
89static int test_bitmaps(struct btrfs_block_group_cache *cache,
90 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 *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 *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 *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 *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 .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds,
403 .use_bitmap = test_use_bitmap,
404 };
405 const struct btrfs_free_space_op *orig_free_space_ops;
406
407 test_msg("running space stealing from bitmap to extent");
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427 orig_free_space_ops = cache->free_space_ctl->op;
428 cache->free_space_ctl->op = &test_free_space_ops;
429
430
431
432
433 ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0);
434 if (ret) {
435 test_err("couldn't add extent entry %d", ret);
436 return ret;
437 }
438
439
440 ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K,
441 SZ_128M - SZ_512K, 1);
442 if (ret) {
443 test_err("couldn't add bitmap entry %d", ret);
444 return ret;
445 }
446
447 ret = check_num_extents_and_bitmaps(cache, 2, 1);
448 if (ret)
449 return ret;
450
451
452
453
454
455
456
457
458 ret = btrfs_remove_free_space(cache,
459 SZ_128M + 768 * SZ_1K,
460 SZ_128M - 768 * SZ_1K);
461 if (ret) {
462 test_err("failed to free part of bitmap space %d", ret);
463 return ret;
464 }
465
466
467 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) {
468 test_err("free space range missing");
469 return -ENOENT;
470 }
471 if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) {
472 test_err("free space range missing");
473 return -ENOENT;
474 }
475
476
477
478
479
480 if (test_check_exists(cache, SZ_128M + 768 * SZ_1K,
481 SZ_128M - 768 * SZ_1K)) {
482 test_err("bitmap region not removed from space cache");
483 return -EINVAL;
484 }
485
486
487
488
489
490 if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) {
491 test_err("invalid bitmap region marked as free");
492 return -EINVAL;
493 }
494
495
496
497
498
499 if (test_check_exists(cache, SZ_128M, SZ_256K)) {
500 test_err("invalid bitmap region marked as free");
501 return -EINVAL;
502 }
503
504
505
506
507
508
509 ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K);
510 if (ret) {
511 test_err("error adding free space: %d", ret);
512 return ret;
513 }
514
515 if (!test_check_exists(cache, SZ_128M, SZ_512K)) {
516 test_err("bitmap region not marked as free");
517 return -ENOENT;
518 }
519
520
521
522
523
524 ret = check_num_extents_and_bitmaps(cache, 2, 1);
525 if (ret)
526 return ret;
527
528
529
530
531
532
533
534 ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, sectorsize);
535 if (ret) {
536 test_err("error adding free space: %d", ret);
537 return ret;
538 }
539
540
541
542
543
544 ret = check_num_extents_and_bitmaps(cache, 2, 1);
545 if (ret)
546 return ret;
547
548
549
550
551
552
553 ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K);
554 if (ret) {
555 test_err("error adding free space: %d", ret);
556 return ret;
557 }
558
559 if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) {
560 test_err("extent region not marked as free");
561 return -ENOENT;
562 }
563
564
565
566
567
568 ret = check_num_extents_and_bitmaps(cache, 2, 1);
569 if (ret)
570 return ret;
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587 if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) {
588 test_err("expected region not marked as free");
589 return -ENOENT;
590 }
591
592 if (cache->free_space_ctl->free_space != (SZ_1M + sectorsize)) {
593 test_err("cache free space is not 1Mb + %u", sectorsize);
594 return -EINVAL;
595 }
596
597 offset = btrfs_find_space_for_alloc(cache,
598 0, SZ_1M, 0,
599 &max_extent_size);
600 if (offset != (SZ_128M - SZ_256K)) {
601 test_err(
602 "failed to allocate 1Mb from space cache, returned offset is: %llu",
603 offset);
604 return -EINVAL;
605 }
606
607
608
609
610
611 ret = check_num_extents_and_bitmaps(cache, 1, 1);
612 if (ret)
613 return ret;
614
615 if (cache->free_space_ctl->free_space != sectorsize) {
616 test_err("cache free space is not %u", sectorsize);
617 return -EINVAL;
618 }
619
620 offset = btrfs_find_space_for_alloc(cache,
621 0, sectorsize, 0,
622 &max_extent_size);
623 if (offset != (SZ_128M + SZ_16M)) {
624 test_err("failed to allocate %u, returned offset : %llu",
625 sectorsize, offset);
626 return -EINVAL;
627 }
628
629 ret = check_cache_empty(cache);
630 if (ret)
631 return ret;
632
633 __btrfs_remove_free_space_cache(cache->free_space_ctl);
634
635
636
637
638
639
640
641
642
643
644 ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0);
645 if (ret) {
646 test_err("couldn't add extent entry %d", ret);
647 return ret;
648 }
649
650
651 ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1);
652 if (ret) {
653 test_err("couldn't add bitmap entry %d", ret);
654 return ret;
655 }
656
657 ret = check_num_extents_and_bitmaps(cache, 2, 1);
658 if (ret)
659 return ret;
660
661
662
663
664
665
666
667
668 ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K);
669 if (ret) {
670 test_err("failed to free part of bitmap space %d", ret);
671 return ret;
672 }
673
674
675 if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) {
676 test_err("free space range missing");
677 return -ENOENT;
678 }
679 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) {
680 test_err("free space range missing");
681 return -ENOENT;
682 }
683
684
685
686
687
688 if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) {
689 test_err("bitmap region not removed from space cache");
690 return -EINVAL;
691 }
692
693
694
695
696
697 if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
698 test_err("invalid bitmap region marked as free");
699 return -EINVAL;
700 }
701
702
703
704
705
706
707 ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K);
708 if (ret) {
709 test_err("error adding free space: %d", ret);
710 return ret;
711 }
712
713 if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
714 test_err("bitmap region not marked as free");
715 return -ENOENT;
716 }
717
718
719
720
721
722 ret = check_num_extents_and_bitmaps(cache, 2, 1);
723 if (ret)
724 return ret;
725
726
727
728
729
730
731
732 ret = btrfs_add_free_space(cache, SZ_32M, 2 * sectorsize);
733 if (ret) {
734 test_err("error adding free space: %d", ret);
735 return ret;
736 }
737
738
739
740
741
742
743 ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K);
744 if (ret) {
745 test_err("error adding free space: %d", ret);
746 return ret;
747 }
748
749 if (!test_check_exists(cache, SZ_128M, SZ_128K)) {
750 test_err("extent region not marked as free");
751 return -ENOENT;
752 }
753
754
755
756
757
758 ret = check_num_extents_and_bitmaps(cache, 2, 1);
759 if (ret)
760 return ret;
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777 if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) {
778 test_err("expected region not marked as free");
779 return -ENOENT;
780 }
781
782 if (cache->free_space_ctl->free_space != (SZ_1M + 2 * sectorsize)) {
783 test_err("cache free space is not 1Mb + %u", 2 * sectorsize);
784 return -EINVAL;
785 }
786
787 offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0,
788 &max_extent_size);
789 if (offset != (SZ_128M - 768 * SZ_1K)) {
790 test_err(
791 "failed to allocate 1Mb from space cache, returned offset is: %llu",
792 offset);
793 return -EINVAL;
794 }
795
796
797
798
799
800 ret = check_num_extents_and_bitmaps(cache, 1, 1);
801 if (ret)
802 return ret;
803
804 if (cache->free_space_ctl->free_space != 2 * sectorsize) {
805 test_err("cache free space is not %u", 2 * sectorsize);
806 return -EINVAL;
807 }
808
809 offset = btrfs_find_space_for_alloc(cache,
810 0, 2 * sectorsize, 0,
811 &max_extent_size);
812 if (offset != SZ_32M) {
813 test_err("failed to allocate %u, offset: %llu",
814 2 * sectorsize, offset);
815 return -EINVAL;
816 }
817
818 ret = check_cache_empty(cache);
819 if (ret)
820 return ret;
821
822 cache->free_space_ctl->op = orig_free_space_ops;
823 __btrfs_remove_free_space_cache(cache->free_space_ctl);
824
825 return 0;
826}
827
828int btrfs_test_free_space_cache(u32 sectorsize, u32 nodesize)
829{
830 struct btrfs_fs_info *fs_info;
831 struct btrfs_block_group_cache *cache;
832 struct btrfs_root *root = NULL;
833 int ret = -ENOMEM;
834
835 test_msg("running btrfs free space cache tests");
836 fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
837 if (!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_err("couldn't run the tests");
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 ret = PTR_ERR(root);
857 goto out;
858 }
859
860 root->fs_info->extent_root = root;
861
862 ret = test_extents(cache);
863 if (ret)
864 goto out;
865 ret = test_bitmaps(cache, sectorsize);
866 if (ret)
867 goto out;
868 ret = test_bitmaps_and_extents(cache, sectorsize);
869 if (ret)
870 goto out;
871
872 ret = test_steal_space_from_bitmap_to_extent(cache, sectorsize);
873out:
874 btrfs_free_dummy_block_group(cache);
875 btrfs_free_dummy_root(root);
876 btrfs_free_dummy_fs_info(fs_info);
877 test_msg("free space cache tests finished");
878 return ret;
879}
880