10 #include "../free-space-cache.h"
17  * entry and remove space from either end and the middle, and make sure we can
18  * remove space that covers adjacent extent entries.
40 		test_err("full remove left some lingering space");  in test_extents()
70 		test_err("still have space at the front");  in test_extents()
75 		test_err("still have space in the middle");  in test_extents()
80 		test_err("still have space at the end");  in test_extents()
110 		test_err("left some space in bitmap");  in test_bitmaps()
136 		test_err("couldn't add space that straddles two bitmaps %d",  in test_bitmaps()
143 		test_err("couldn't remove overlapping space %d", ret);  in test_bitmaps()
148 		test_err("left some space when removing overlapping");  in test_bitmaps()
168 	 * bitmap, but the free space completely in the extent and then  in test_bitmaps_and_extents()
224 		test_err("couldn't remove overlapping space %d", ret);  in test_bitmaps_and_extents()
238 		test_err("couldn't add space to the bitmap %d", ret);  in test_bitmaps_and_extents()
250 		test_err("problem removing overlapping space %d", ret);  in test_bitmaps_and_extents()
255 		test_err("left something behind when removing space");  in test_bitmaps_and_extents()
285 		test_err("failed to free our space %d", ret);  in test_bitmaps_and_extents()
297 	 * This blew up before, we have part of the free space in a bitmap and  in test_bitmaps_and_extents()
298 	 * then the entirety of the rest of the space in an extent.  This used  in test_bitmaps_and_extents()
359 	 * Now lets confirm that there's absolutely no free space left to  in check_cache_empty()
363 		test_err("cache free space is not 0");  in check_cache_empty()
371 		test_err("space allocation did not fail, returned offset: %llu",  in check_cache_empty()
381  * Before we were able to steal free space from a bitmap entry to an extent
382  * entry, we could end up with 2 entries representing a contiguous free space.
384  * to allocate space to a caller we use only 1 entry, we couldn't return that
386  * either assume ENOSPC or perform several smaller space allocations, which
407 	test_msg("running space stealing from bitmap to extent tests");  in test_steal_space_from_bitmap_to_extent()
413 	 * removing free space to reach into this state, but to get there  in test_steal_space_from_bitmap_to_extent()
414 	 * we need to reach a point where marking new free space doesn't  in test_steal_space_from_bitmap_to_extent()
415 	 * result in adding new extent entries or merging the new space  in test_steal_space_from_bitmap_to_extent()
416 	 * with existing extent entries - the space ends up being marked  in test_steal_space_from_bitmap_to_extent()
417 	 * in an existing bitmap that covers the new free space range.  in test_steal_space_from_bitmap_to_extent()
431 	 * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[  in test_steal_space_from_bitmap_to_extent()
439 	/* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */  in test_steal_space_from_bitmap_to_extent()
453 	 * we end up with only the following ranges marked as free space:  in test_steal_space_from_bitmap_to_extent()
462 		test_err("failed to free part of bitmap space %d", ret);  in test_steal_space_from_bitmap_to_extent()
468 		test_err("free space range missing");  in test_steal_space_from_bitmap_to_extent()
472 		test_err("free space range missing");  in test_steal_space_from_bitmap_to_extent()
482 		test_err("bitmap region not removed from space cache");  in test_steal_space_from_bitmap_to_extent()
506 	 * lets make sure the free space cache marks it as free in the bitmap,  in test_steal_space_from_bitmap_to_extent()
511 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
522 	 * the cache after adding that free space region.  in test_steal_space_from_bitmap_to_extent()
529 	 * Now lets add a small free space region to the right of the previous  in test_steal_space_from_bitmap_to_extent()
531 	 * The goal is to test that the bitmap entry space stealing doesn't  in test_steal_space_from_bitmap_to_extent()
532 	 * steal this space region.  in test_steal_space_from_bitmap_to_extent()
536 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
542 	 * the cache after adding that free space region.  in test_steal_space_from_bitmap_to_extent()
551 	 * the free space [128Mb - 256Kb, 128Mb - 128Kb[.  in test_steal_space_from_bitmap_to_extent()
555 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
565 	 * Confirm that our extent entry didn't stole all free space from the  in test_steal_space_from_bitmap_to_extent()
566 	 * bitmap, because of the small 4Kb free space region.  in test_steal_space_from_bitmap_to_extent()
574 	 * space. Without stealing bitmap free space into extent entry space,  in test_steal_space_from_bitmap_to_extent()
575 	 * we would have all this free space represented by 2 entries in the  in test_steal_space_from_bitmap_to_extent()
581 	 * Attempting to allocate the whole free space (1Mb) would fail, because  in test_steal_space_from_bitmap_to_extent()
583 	 * With the bitmap free space stealing, we get a single extent entry  in test_steal_space_from_bitmap_to_extent()
584 	 * that represents the 1Mb free space, and therefore we're able to  in test_steal_space_from_bitmap_to_extent()
585 	 * allocate the whole free space at once.  in test_steal_space_from_bitmap_to_extent()
593 		test_err("cache free space is not 1Mb + %u", sectorsize);  in test_steal_space_from_bitmap_to_extent()
602 	"failed to allocate 1Mb from space cache, returned offset is: %llu",  in test_steal_space_from_bitmap_to_extent()
608 	 * All that remains is a sectorsize free space region in a bitmap.  in test_steal_space_from_bitmap_to_extent()
616 		test_err("cache free space is not %u", sectorsize);  in test_steal_space_from_bitmap_to_extent()
638 	 * space from a bitmap to the front of an extent entry works.  in test_steal_space_from_bitmap_to_extent()
642 	 * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[  in test_steal_space_from_bitmap_to_extent()
650 	/* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */  in test_steal_space_from_bitmap_to_extent()
663 	 * we end up with only the following ranges marked as free space:  in test_steal_space_from_bitmap_to_extent()
670 		test_err("failed to free part of bitmap space %d", ret);  in test_steal_space_from_bitmap_to_extent()
676 		test_err("free space range missing");  in test_steal_space_from_bitmap_to_extent()
680 		test_err("free space range missing");  in test_steal_space_from_bitmap_to_extent()
689 		test_err("bitmap region not removed from space cache");  in test_steal_space_from_bitmap_to_extent()
704 	 * lets make sure the free space cache marks it as free in the bitmap,  in test_steal_space_from_bitmap_to_extent()
709 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
720 	 * the cache after adding that free space region.  in test_steal_space_from_bitmap_to_extent()
727 	 * Now lets add a small free space region to the left of the previous  in test_steal_space_from_bitmap_to_extent()
729 	 * The goal is to test that the bitmap entry space stealing doesn't  in test_steal_space_from_bitmap_to_extent()
730 	 * steal this space region.  in test_steal_space_from_bitmap_to_extent()
734 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
741 	 * the free space [128Mb + 128Kb, 128Mb + 256Kb[.  in test_steal_space_from_bitmap_to_extent()
745 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
755 	 * Confirm that our extent entry didn't stole all free space from the  in test_steal_space_from_bitmap_to_extent()
756 	 * bitmap, because of the small 2 * sectorsize free space region.  in test_steal_space_from_bitmap_to_extent()
764 	 * space. Without stealing bitmap free space into extent entry space,  in test_steal_space_from_bitmap_to_extent()
765 	 * we would have all this free space represented by 2 entries in the  in test_steal_space_from_bitmap_to_extent()
771 	 * Attempting to allocate the whole free space (1Mb) would fail, because  in test_steal_space_from_bitmap_to_extent()
773 	 * With the bitmap free space stealing, we get a single extent entry  in test_steal_space_from_bitmap_to_extent()
774 	 * that represents the 1Mb free space, and therefore we're able to  in test_steal_space_from_bitmap_to_extent()
775 	 * allocate the whole free space at once.  in test_steal_space_from_bitmap_to_extent()
783 		test_err("cache free space is not 1Mb + %u", 2 * sectorsize);  in test_steal_space_from_bitmap_to_extent()
791 	"failed to allocate 1Mb from space cache, returned offset is: %llu",  in test_steal_space_from_bitmap_to_extent()
797 	 * All that remains is 2 * sectorsize free space region  in test_steal_space_from_bitmap_to_extent()
805 		test_err("cache free space is not %u", 2 * sectorsize);  in test_steal_space_from_bitmap_to_extent()
835 	test_msg("running btrfs free space cache tests");  in btrfs_test_free_space_cache()