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
406 	test_msg("running space stealing from bitmap to extent tests");  in test_steal_space_from_bitmap_to_extent()
412 	 * removing free space to reach into this state, but to get there  in test_steal_space_from_bitmap_to_extent()
413 	 * we need to reach a point where marking new free space doesn't  in test_steal_space_from_bitmap_to_extent()
414 	 * result in adding new extent entries or merging the new space  in test_steal_space_from_bitmap_to_extent()
415 	 * with existing extent entries - the space ends up being marked  in test_steal_space_from_bitmap_to_extent()
416 	 * in an existing bitmap that covers the new free space range.  in test_steal_space_from_bitmap_to_extent()
430 	 * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[  in test_steal_space_from_bitmap_to_extent()
438 	/* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */  in test_steal_space_from_bitmap_to_extent()
452 	 * we end up with only the following ranges marked as free space:  in test_steal_space_from_bitmap_to_extent()
461 		test_err("failed to free part of bitmap space %d", ret);  in test_steal_space_from_bitmap_to_extent()
467 		test_err("free space range missing");  in test_steal_space_from_bitmap_to_extent()
471 		test_err("free space range missing");  in test_steal_space_from_bitmap_to_extent()
481 		test_err("bitmap region not removed from space cache");  in test_steal_space_from_bitmap_to_extent()
505 	 * lets make sure the free space cache marks it as free in the bitmap,  in test_steal_space_from_bitmap_to_extent()
510 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
521 	 * the cache after adding that free space region.  in test_steal_space_from_bitmap_to_extent()
528 	 * Now lets add a small free space region to the right of the previous  in test_steal_space_from_bitmap_to_extent()
530 	 * The goal is to test that the bitmap entry space stealing doesn't  in test_steal_space_from_bitmap_to_extent()
531 	 * steal this space region.  in test_steal_space_from_bitmap_to_extent()
535 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
541 	 * the cache after adding that free space region.  in test_steal_space_from_bitmap_to_extent()
550 	 * the free space [128Mb - 256Kb, 128Mb - 128Kb[.  in test_steal_space_from_bitmap_to_extent()
554 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
564 	 * Confirm that our extent entry didn't stole all free space from the  in test_steal_space_from_bitmap_to_extent()
565 	 * bitmap, because of the small 4Kb free space region.  in test_steal_space_from_bitmap_to_extent()
573 	 * space. Without stealing bitmap free space into extent entry space,  in test_steal_space_from_bitmap_to_extent()
574 	 * we would have all this free space represented by 2 entries in the  in test_steal_space_from_bitmap_to_extent()
580 	 * Attempting to allocate the whole free space (1Mb) would fail, because  in test_steal_space_from_bitmap_to_extent()
582 	 * With the bitmap free space stealing, we get a single extent entry  in test_steal_space_from_bitmap_to_extent()
583 	 * that represents the 1Mb free space, and therefore we're able to  in test_steal_space_from_bitmap_to_extent()
584 	 * allocate the whole free space at once.  in test_steal_space_from_bitmap_to_extent()
592 		test_err("cache free space is not 1Mb + %u", sectorsize);  in test_steal_space_from_bitmap_to_extent()
601 	"failed to allocate 1Mb from space cache, returned offset is: %llu",  in test_steal_space_from_bitmap_to_extent()
607 	 * All that remains is a sectorsize free space region in a bitmap.  in test_steal_space_from_bitmap_to_extent()
615 		test_err("cache free space is not %u", sectorsize);  in test_steal_space_from_bitmap_to_extent()
637 	 * space from a bitmap to the front of an extent entry works.  in test_steal_space_from_bitmap_to_extent()
641 	 * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[  in test_steal_space_from_bitmap_to_extent()
649 	/* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */  in test_steal_space_from_bitmap_to_extent()
662 	 * we end up with only the following ranges marked as free space:  in test_steal_space_from_bitmap_to_extent()
669 		test_err("failed to free part of bitmap space %d", ret);  in test_steal_space_from_bitmap_to_extent()
675 		test_err("free space range missing");  in test_steal_space_from_bitmap_to_extent()
679 		test_err("free space range missing");  in test_steal_space_from_bitmap_to_extent()
688 		test_err("bitmap region not removed from space cache");  in test_steal_space_from_bitmap_to_extent()
703 	 * lets make sure the free space cache marks it as free in the bitmap,  in test_steal_space_from_bitmap_to_extent()
708 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
719 	 * the cache after adding that free space region.  in test_steal_space_from_bitmap_to_extent()
726 	 * Now lets add a small free space region to the left of the previous  in test_steal_space_from_bitmap_to_extent()
728 	 * The goal is to test that the bitmap entry space stealing doesn't  in test_steal_space_from_bitmap_to_extent()
729 	 * steal this space region.  in test_steal_space_from_bitmap_to_extent()
733 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
740 	 * the free space [128Mb + 128Kb, 128Mb + 256Kb[.  in test_steal_space_from_bitmap_to_extent()
744 		test_err("error adding free space: %d", ret);  in test_steal_space_from_bitmap_to_extent()
754 	 * Confirm that our extent entry didn't stole all free space from the  in test_steal_space_from_bitmap_to_extent()
755 	 * bitmap, because of the small 2 * sectorsize free space region.  in test_steal_space_from_bitmap_to_extent()
763 	 * space. Without stealing bitmap free space into extent entry space,  in test_steal_space_from_bitmap_to_extent()
764 	 * we would have all this free space represented by 2 entries in the  in test_steal_space_from_bitmap_to_extent()
770 	 * Attempting to allocate the whole free space (1Mb) would fail, because  in test_steal_space_from_bitmap_to_extent()
772 	 * With the bitmap free space stealing, we get a single extent entry  in test_steal_space_from_bitmap_to_extent()
773 	 * that represents the 1Mb free space, and therefore we're able to  in test_steal_space_from_bitmap_to_extent()
774 	 * allocate the whole free space at once.  in test_steal_space_from_bitmap_to_extent()
782 		test_err("cache free space is not 1Mb + %u", 2 * sectorsize);  in test_steal_space_from_bitmap_to_extent()
790 	"failed to allocate 1Mb from space cache, returned offset is: %llu",  in test_steal_space_from_bitmap_to_extent()
796 	 * All that remains is 2 * sectorsize free space region  in test_steal_space_from_bitmap_to_extent()
804 		test_err("cache free space is not %u", 2 * sectorsize);  in test_steal_space_from_bitmap_to_extent()
950 		test_err("found space to alloc even though we don't have enough space");  in test_bytes_index()
1012 	test_msg("running btrfs free space cache tests");  in btrfs_test_free_space_cache()