aboutsummaryrefslogtreecommitdiffstats
path: root/fs/btrfs/free-space-cache.c
diff options
context:
space:
mode:
Diffstat (limited to 'fs/btrfs/free-space-cache.c')
-rw-r--r--fs/btrfs/free-space-cache.c525
1 files changed, 75 insertions, 450 deletions
diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c
index b21a3cd667d8..ef3bea7bb257 100644
--- a/fs/btrfs/free-space-cache.c
+++ b/fs/btrfs/free-space-cache.c
@@ -308,7 +308,7 @@ static void io_ctl_unmap_page(struct io_ctl *io_ctl)
308 308
309static void io_ctl_map_page(struct io_ctl *io_ctl, int clear) 309static void io_ctl_map_page(struct io_ctl *io_ctl, int clear)
310{ 310{
311 BUG_ON(io_ctl->index >= io_ctl->num_pages); 311 ASSERT(io_ctl->index < io_ctl->num_pages);
312 io_ctl->page = io_ctl->pages[io_ctl->index++]; 312 io_ctl->page = io_ctl->pages[io_ctl->index++];
313 io_ctl->cur = kmap(io_ctl->page); 313 io_ctl->cur = kmap(io_ctl->page);
314 io_ctl->orig = io_ctl->cur; 314 io_ctl->orig = io_ctl->cur;
@@ -673,8 +673,7 @@ static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
673 btrfs_err(root->fs_info, 673 btrfs_err(root->fs_info,
674 "free space inode generation (%llu) " 674 "free space inode generation (%llu) "
675 "did not match free space cache generation (%llu)", 675 "did not match free space cache generation (%llu)",
676 (unsigned long long)BTRFS_I(inode)->generation, 676 BTRFS_I(inode)->generation, generation);
677 (unsigned long long)generation);
678 return 0; 677 return 0;
679 } 678 }
680 679
@@ -729,7 +728,7 @@ static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
729 goto free_cache; 728 goto free_cache;
730 } 729 }
731 } else { 730 } else {
732 BUG_ON(!num_bitmaps); 731 ASSERT(num_bitmaps);
733 num_bitmaps--; 732 num_bitmaps--;
734 e->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS); 733 e->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
735 if (!e->bitmap) { 734 if (!e->bitmap) {
@@ -1029,7 +1028,7 @@ static int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
1029 leaf = path->nodes[0]; 1028 leaf = path->nodes[0];
1030 if (ret > 0) { 1029 if (ret > 0) {
1031 struct btrfs_key found_key; 1030 struct btrfs_key found_key;
1032 BUG_ON(!path->slots[0]); 1031 ASSERT(path->slots[0]);
1033 path->slots[0]--; 1032 path->slots[0]--;
1034 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]); 1033 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
1035 if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID || 1034 if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||
@@ -1117,7 +1116,7 @@ int btrfs_write_out_cache(struct btrfs_root *root,
1117static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit, 1116static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
1118 u64 offset) 1117 u64 offset)
1119{ 1118{
1120 BUG_ON(offset < bitmap_start); 1119 ASSERT(offset >= bitmap_start);
1121 offset -= bitmap_start; 1120 offset -= bitmap_start;
1122 return (unsigned long)(div_u64(offset, unit)); 1121 return (unsigned long)(div_u64(offset, unit));
1123} 1122}
@@ -1272,7 +1271,7 @@ tree_search_offset(struct btrfs_free_space_ctl *ctl,
1272 if (n) { 1271 if (n) {
1273 entry = rb_entry(n, struct btrfs_free_space, 1272 entry = rb_entry(n, struct btrfs_free_space,
1274 offset_index); 1273 offset_index);
1275 BUG_ON(entry->offset > offset); 1274 ASSERT(entry->offset <= offset);
1276 } else { 1275 } else {
1277 if (fuzzy) 1276 if (fuzzy)
1278 return entry; 1277 return entry;
@@ -1336,7 +1335,7 @@ static int link_free_space(struct btrfs_free_space_ctl *ctl,
1336{ 1335{
1337 int ret = 0; 1336 int ret = 0;
1338 1337
1339 BUG_ON(!info->bitmap && !info->bytes); 1338 ASSERT(info->bytes || info->bitmap);
1340 ret = tree_insert_offset(&ctl->free_space_offset, info->offset, 1339 ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
1341 &info->offset_index, (info->bitmap != NULL)); 1340 &info->offset_index, (info->bitmap != NULL));
1342 if (ret) 1341 if (ret)
@@ -1359,7 +1358,7 @@ static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
1359 1358
1360 max_bitmaps = max(max_bitmaps, 1); 1359 max_bitmaps = max(max_bitmaps, 1);
1361 1360
1362 BUG_ON(ctl->total_bitmaps > max_bitmaps); 1361 ASSERT(ctl->total_bitmaps <= max_bitmaps);
1363 1362
1364 /* 1363 /*
1365 * The goal is to keep the total amount of memory used per 1gb of space 1364 * The goal is to keep the total amount of memory used per 1gb of space
@@ -1403,7 +1402,7 @@ static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
1403 1402
1404 start = offset_to_bit(info->offset, ctl->unit, offset); 1403 start = offset_to_bit(info->offset, ctl->unit, offset);
1405 count = bytes_to_bits(bytes, ctl->unit); 1404 count = bytes_to_bits(bytes, ctl->unit);
1406 BUG_ON(start + count > BITS_PER_BITMAP); 1405 ASSERT(start + count <= BITS_PER_BITMAP);
1407 1406
1408 bitmap_clear(info->bitmap, start, count); 1407 bitmap_clear(info->bitmap, start, count);
1409 1408
@@ -1426,7 +1425,7 @@ static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
1426 1425
1427 start = offset_to_bit(info->offset, ctl->unit, offset); 1426 start = offset_to_bit(info->offset, ctl->unit, offset);
1428 count = bytes_to_bits(bytes, ctl->unit); 1427 count = bytes_to_bits(bytes, ctl->unit);
1429 BUG_ON(start + count > BITS_PER_BITMAP); 1428 ASSERT(start + count <= BITS_PER_BITMAP);
1430 1429
1431 bitmap_set(info->bitmap, start, count); 1430 bitmap_set(info->bitmap, start, count);
1432 1431
@@ -1742,7 +1741,7 @@ no_cluster_bitmap:
1742 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset), 1741 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
1743 1, 0); 1742 1, 0);
1744 if (!bitmap_info) { 1743 if (!bitmap_info) {
1745 BUG_ON(added); 1744 ASSERT(added == 0);
1746 goto new_bitmap; 1745 goto new_bitmap;
1747 } 1746 }
1748 1747
@@ -1882,7 +1881,7 @@ out:
1882 1881
1883 if (ret) { 1882 if (ret) {
1884 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret); 1883 printk(KERN_CRIT "btrfs: unable to add free space :%d\n", ret);
1885 BUG_ON(ret == -EEXIST); 1884 ASSERT(ret != -EEXIST);
1886 } 1885 }
1887 1886
1888 return ret; 1887 return ret;
@@ -1991,8 +1990,7 @@ void btrfs_dump_free_space(struct btrfs_block_group_cache *block_group,
1991 if (info->bytes >= bytes && !block_group->ro) 1990 if (info->bytes >= bytes && !block_group->ro)
1992 count++; 1991 count++;
1993 printk(KERN_CRIT "entry offset %llu, bytes %llu, bitmap %s\n", 1992 printk(KERN_CRIT "entry offset %llu, bytes %llu, bitmap %s\n",
1994 (unsigned long long)info->offset, 1993 info->offset, info->bytes,
1995 (unsigned long long)info->bytes,
1996 (info->bitmap) ? "yes" : "no"); 1994 (info->bitmap) ? "yes" : "no");
1997 } 1995 }
1998 printk(KERN_INFO "block group has cluster?: %s\n", 1996 printk(KERN_INFO "block group has cluster?: %s\n",
@@ -2371,7 +2369,7 @@ again:
2371 rb_erase(&entry->offset_index, &ctl->free_space_offset); 2369 rb_erase(&entry->offset_index, &ctl->free_space_offset);
2372 ret = tree_insert_offset(&cluster->root, entry->offset, 2370 ret = tree_insert_offset(&cluster->root, entry->offset,
2373 &entry->offset_index, 1); 2371 &entry->offset_index, 1);
2374 BUG_ON(ret); /* -EEXIST; Logic error */ 2372 ASSERT(!ret); /* -EEXIST; Logic error */
2375 2373
2376 trace_btrfs_setup_cluster(block_group, cluster, 2374 trace_btrfs_setup_cluster(block_group, cluster,
2377 total_found * ctl->unit, 1); 2375 total_found * ctl->unit, 1);
@@ -2464,7 +2462,7 @@ setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group,
2464 ret = tree_insert_offset(&cluster->root, entry->offset, 2462 ret = tree_insert_offset(&cluster->root, entry->offset,
2465 &entry->offset_index, 0); 2463 &entry->offset_index, 0);
2466 total_size += entry->bytes; 2464 total_size += entry->bytes;
2467 BUG_ON(ret); /* -EEXIST; Logic error */ 2465 ASSERT(!ret); /* -EEXIST; Logic error */
2468 } while (node && entry != last); 2466 } while (node && entry != last);
2469 2467
2470 cluster->max_size = max_extent; 2468 cluster->max_size = max_extent;
@@ -2525,8 +2523,7 @@ setup_cluster_bitmap(struct btrfs_block_group_cache *block_group,
2525 * returns zero and sets up cluster if things worked out, otherwise 2523 * returns zero and sets up cluster if things worked out, otherwise
2526 * it returns -enospc 2524 * it returns -enospc
2527 */ 2525 */
2528int btrfs_find_space_cluster(struct btrfs_trans_handle *trans, 2526int btrfs_find_space_cluster(struct btrfs_root *root,
2529 struct btrfs_root *root,
2530 struct btrfs_block_group_cache *block_group, 2527 struct btrfs_block_group_cache *block_group,
2531 struct btrfs_free_cluster *cluster, 2528 struct btrfs_free_cluster *cluster,
2532 u64 offset, u64 bytes, u64 empty_size) 2529 u64 offset, u64 bytes, u64 empty_size)
@@ -2856,7 +2853,7 @@ u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root)
2856 2853
2857 ret = search_bitmap(ctl, entry, &offset, &count); 2854 ret = search_bitmap(ctl, entry, &offset, &count);
2858 /* Logic error; Should be empty if it can't find anything */ 2855 /* Logic error; Should be empty if it can't find anything */
2859 BUG_ON(ret); 2856 ASSERT(!ret);
2860 2857
2861 ino = offset; 2858 ino = offset;
2862 bitmap_clear_bits(ctl, entry, offset, 1); 2859 bitmap_clear_bits(ctl, entry, offset, 1);
@@ -2973,33 +2970,68 @@ int btrfs_write_out_ino_cache(struct btrfs_root *root,
2973} 2970}
2974 2971
2975#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS 2972#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
2976static struct btrfs_block_group_cache *init_test_block_group(void) 2973/*
2974 * Use this if you need to make a bitmap or extent entry specifically, it
2975 * doesn't do any of the merging that add_free_space does, this acts a lot like
2976 * how the free space cache loading stuff works, so you can get really weird
2977 * configurations.
2978 */
2979int test_add_free_space_entry(struct btrfs_block_group_cache *cache,
2980 u64 offset, u64 bytes, bool bitmap)
2977{ 2981{
2978 struct btrfs_block_group_cache *cache; 2982 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
2983 struct btrfs_free_space *info = NULL, *bitmap_info;
2984 void *map = NULL;
2985 u64 bytes_added;
2986 int ret;
2979 2987
2980 cache = kzalloc(sizeof(*cache), GFP_NOFS); 2988again:
2981 if (!cache) 2989 if (!info) {
2982 return NULL; 2990 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
2983 cache->free_space_ctl = kzalloc(sizeof(*cache->free_space_ctl), 2991 if (!info)
2984 GFP_NOFS); 2992 return -ENOMEM;
2985 if (!cache->free_space_ctl) {
2986 kfree(cache);
2987 return NULL;
2988 } 2993 }
2989 2994
2990 cache->key.objectid = 0; 2995 if (!bitmap) {
2991 cache->key.offset = 1024 * 1024 * 1024; 2996 spin_lock(&ctl->tree_lock);
2992 cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY; 2997 info->offset = offset;
2993 cache->sectorsize = 4096; 2998 info->bytes = bytes;
2999 ret = link_free_space(ctl, info);
3000 spin_unlock(&ctl->tree_lock);
3001 if (ret)
3002 kmem_cache_free(btrfs_free_space_cachep, info);
3003 return ret;
3004 }
3005
3006 if (!map) {
3007 map = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
3008 if (!map) {
3009 kmem_cache_free(btrfs_free_space_cachep, info);
3010 return -ENOMEM;
3011 }
3012 }
3013
3014 spin_lock(&ctl->tree_lock);
3015 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3016 1, 0);
3017 if (!bitmap_info) {
3018 info->bitmap = map;
3019 map = NULL;
3020 add_new_bitmap(ctl, info, offset);
3021 bitmap_info = info;
3022 }
2994 3023
2995 spin_lock_init(&cache->lock); 3024 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
2996 INIT_LIST_HEAD(&cache->list); 3025 bytes -= bytes_added;
2997 INIT_LIST_HEAD(&cache->cluster_list); 3026 offset += bytes_added;
2998 INIT_LIST_HEAD(&cache->new_bg_list); 3027 spin_unlock(&ctl->tree_lock);
2999 3028
3000 btrfs_init_free_space_ctl(cache); 3029 if (bytes)
3030 goto again;
3001 3031
3002 return cache; 3032 if (map)
3033 kfree(map);
3034 return 0;
3003} 3035}
3004 3036
3005/* 3037/*
@@ -3007,8 +3039,8 @@ static struct btrfs_block_group_cache *init_test_block_group(void)
3007 * just used to check the absence of space, so if there is free space in the 3039 * just used to check the absence of space, so if there is free space in the
3008 * range at all we will return 1. 3040 * range at all we will return 1.
3009 */ 3041 */
3010static int check_exists(struct btrfs_block_group_cache *cache, u64 offset, 3042int test_check_exists(struct btrfs_block_group_cache *cache,
3011 u64 bytes) 3043 u64 offset, u64 bytes)
3012{ 3044{
3013 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl; 3045 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3014 struct btrfs_free_space *info; 3046 struct btrfs_free_space *info;
@@ -3085,411 +3117,4 @@ out:
3085 spin_unlock(&ctl->tree_lock); 3117 spin_unlock(&ctl->tree_lock);
3086 return ret; 3118 return ret;
3087} 3119}
3088 3120#endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */
3089/*
3090 * Use this if you need to make a bitmap or extent entry specifically, it
3091 * doesn't do any of the merging that add_free_space does, this acts a lot like
3092 * how the free space cache loading stuff works, so you can get really weird
3093 * configurations.
3094 */
3095static int add_free_space_entry(struct btrfs_block_group_cache *cache,
3096 u64 offset, u64 bytes, bool bitmap)
3097{
3098 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3099 struct btrfs_free_space *info = NULL, *bitmap_info;
3100 void *map = NULL;
3101 u64 bytes_added;
3102 int ret;
3103
3104again:
3105 if (!info) {
3106 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
3107 if (!info)
3108 return -ENOMEM;
3109 }
3110
3111 if (!bitmap) {
3112 spin_lock(&ctl->tree_lock);
3113 info->offset = offset;
3114 info->bytes = bytes;
3115 ret = link_free_space(ctl, info);
3116 spin_unlock(&ctl->tree_lock);
3117 if (ret)
3118 kmem_cache_free(btrfs_free_space_cachep, info);
3119 return ret;
3120 }
3121
3122 if (!map) {
3123 map = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
3124 if (!map) {
3125 kmem_cache_free(btrfs_free_space_cachep, info);
3126 return -ENOMEM;
3127 }
3128 }
3129
3130 spin_lock(&ctl->tree_lock);
3131 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3132 1, 0);
3133 if (!bitmap_info) {
3134 info->bitmap = map;
3135 map = NULL;
3136 add_new_bitmap(ctl, info, offset);
3137 bitmap_info = info;
3138 }
3139
3140 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
3141 bytes -= bytes_added;
3142 offset += bytes_added;
3143 spin_unlock(&ctl->tree_lock);
3144
3145 if (bytes)
3146 goto again;
3147
3148 if (map)
3149 kfree(map);
3150 return 0;
3151}
3152
3153#define test_msg(fmt, ...) printk(KERN_INFO "btrfs: selftest: " fmt, ##__VA_ARGS__)
3154
3155/*
3156 * This test just does basic sanity checking, making sure we can add an exten
3157 * entry and remove space from either end and the middle, and make sure we can
3158 * remove space that covers adjacent extent entries.
3159 */
3160static int test_extents(struct btrfs_block_group_cache *cache)
3161{
3162 int ret = 0;
3163
3164 test_msg("Running extent only tests\n");
3165
3166 /* First just make sure we can remove an entire entry */
3167 ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
3168 if (ret) {
3169 test_msg("Error adding initial extents %d\n", ret);
3170 return ret;
3171 }
3172
3173 ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
3174 if (ret) {
3175 test_msg("Error removing extent %d\n", ret);
3176 return ret;
3177 }
3178
3179 if (check_exists(cache, 0, 4 * 1024 * 1024)) {
3180 test_msg("Full remove left some lingering space\n");
3181 return -1;
3182 }
3183
3184 /* Ok edge and middle cases now */
3185 ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
3186 if (ret) {
3187 test_msg("Error adding half extent %d\n", ret);
3188 return ret;
3189 }
3190
3191 ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 1 * 1024 * 1024);
3192 if (ret) {
3193 test_msg("Error removing tail end %d\n", ret);
3194 return ret;
3195 }
3196
3197 ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
3198 if (ret) {
3199 test_msg("Error removing front end %d\n", ret);
3200 return ret;
3201 }
3202
3203 ret = btrfs_remove_free_space(cache, 2 * 1024 * 1024, 4096);
3204 if (ret) {
3205 test_msg("Error removing middle piece %d\n", ret);
3206 return ret;
3207 }
3208
3209 if (check_exists(cache, 0, 1 * 1024 * 1024)) {
3210 test_msg("Still have space at the front\n");
3211 return -1;
3212 }
3213
3214 if (check_exists(cache, 2 * 1024 * 1024, 4096)) {
3215 test_msg("Still have space in the middle\n");
3216 return -1;
3217 }
3218
3219 if (check_exists(cache, 3 * 1024 * 1024, 1 * 1024 * 1024)) {
3220 test_msg("Still have space at the end\n");
3221 return -1;
3222 }
3223
3224 /* Cleanup */
3225 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3226
3227 return 0;
3228}
3229
3230static int test_bitmaps(struct btrfs_block_group_cache *cache)
3231{
3232 u64 next_bitmap_offset;
3233 int ret;
3234
3235 test_msg("Running bitmap only tests\n");
3236
3237 ret = add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
3238 if (ret) {
3239 test_msg("Couldn't create a bitmap entry %d\n", ret);
3240 return ret;
3241 }
3242
3243 ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
3244 if (ret) {
3245 test_msg("Error removing bitmap full range %d\n", ret);
3246 return ret;
3247 }
3248
3249 if (check_exists(cache, 0, 4 * 1024 * 1024)) {
3250 test_msg("Left some space in bitmap\n");
3251 return -1;
3252 }
3253
3254 ret = add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
3255 if (ret) {
3256 test_msg("Couldn't add to our bitmap entry %d\n", ret);
3257 return ret;
3258 }
3259
3260 ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 2 * 1024 * 1024);
3261 if (ret) {
3262 test_msg("Couldn't remove middle chunk %d\n", ret);
3263 return ret;
3264 }
3265
3266 /*
3267 * The first bitmap we have starts at offset 0 so the next one is just
3268 * at the end of the first bitmap.
3269 */
3270 next_bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
3271
3272 /* Test a bit straddling two bitmaps */
3273 ret = add_free_space_entry(cache, next_bitmap_offset -
3274 (2 * 1024 * 1024), 4 * 1024 * 1024, 1);
3275 if (ret) {
3276 test_msg("Couldn't add space that straddles two bitmaps %d\n",
3277 ret);
3278 return ret;
3279 }
3280
3281 ret = btrfs_remove_free_space(cache, next_bitmap_offset -
3282 (1 * 1024 * 1024), 2 * 1024 * 1024);
3283 if (ret) {
3284 test_msg("Couldn't remove overlapping space %d\n", ret);
3285 return ret;
3286 }
3287
3288 if (check_exists(cache, next_bitmap_offset - (1 * 1024 * 1024),
3289 2 * 1024 * 1024)) {
3290 test_msg("Left some space when removing overlapping\n");
3291 return -1;
3292 }
3293
3294 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3295
3296 return 0;
3297}
3298
3299/* This is the high grade jackassery */
3300static int test_bitmaps_and_extents(struct btrfs_block_group_cache *cache)
3301{
3302 u64 bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
3303 int ret;
3304
3305 test_msg("Running bitmap and extent tests\n");
3306
3307 /*
3308 * First let's do something simple, an extent at the same offset as the
3309 * bitmap, but the free space completely in the extent and then
3310 * completely in the bitmap.
3311 */
3312 ret = add_free_space_entry(cache, 4 * 1024 * 1024, 1 * 1024 * 1024, 1);
3313 if (ret) {
3314 test_msg("Couldn't create bitmap entry %d\n", ret);
3315 return ret;
3316 }
3317
3318 ret = add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
3319 if (ret) {
3320 test_msg("Couldn't add extent entry %d\n", ret);
3321 return ret;
3322 }
3323
3324 ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
3325 if (ret) {
3326 test_msg("Couldn't remove extent entry %d\n", ret);
3327 return ret;
3328 }
3329
3330 if (check_exists(cache, 0, 1 * 1024 * 1024)) {
3331 test_msg("Left remnants after our remove\n");
3332 return -1;
3333 }
3334
3335 /* Now to add back the extent entry and remove from the bitmap */
3336 ret = add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
3337 if (ret) {
3338 test_msg("Couldn't re-add extent entry %d\n", ret);
3339 return ret;
3340 }
3341
3342 ret = btrfs_remove_free_space(cache, 4 * 1024 * 1024, 1 * 1024 * 1024);
3343 if (ret) {
3344 test_msg("Couldn't remove from bitmap %d\n", ret);
3345 return ret;
3346 }
3347
3348 if (check_exists(cache, 4 * 1024 * 1024, 1 * 1024 * 1024)) {
3349 test_msg("Left remnants in the bitmap\n");
3350 return -1;
3351 }
3352
3353 /*
3354 * Ok so a little more evil, extent entry and bitmap at the same offset,
3355 * removing an overlapping chunk.
3356 */
3357 ret = add_free_space_entry(cache, 1 * 1024 * 1024, 4 * 1024 * 1024, 1);
3358 if (ret) {
3359 test_msg("Couldn't add to a bitmap %d\n", ret);
3360 return ret;
3361 }
3362
3363 ret = btrfs_remove_free_space(cache, 512 * 1024, 3 * 1024 * 1024);
3364 if (ret) {
3365 test_msg("Couldn't remove overlapping space %d\n", ret);
3366 return ret;
3367 }
3368
3369 if (check_exists(cache, 512 * 1024, 3 * 1024 * 1024)) {
3370 test_msg("Left over peices after removing overlapping\n");
3371 return -1;
3372 }
3373
3374 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3375
3376 /* Now with the extent entry offset into the bitmap */
3377 ret = add_free_space_entry(cache, 4 * 1024 * 1024, 4 * 1024 * 1024, 1);
3378 if (ret) {
3379 test_msg("Couldn't add space to the bitmap %d\n", ret);
3380 return ret;
3381 }
3382
3383 ret = add_free_space_entry(cache, 2 * 1024 * 1024, 2 * 1024 * 1024, 0);
3384 if (ret) {
3385 test_msg("Couldn't add extent to the cache %d\n", ret);
3386 return ret;
3387 }
3388
3389 ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 4 * 1024 * 1024);
3390 if (ret) {
3391 test_msg("Problem removing overlapping space %d\n", ret);
3392 return ret;
3393 }
3394
3395 if (check_exists(cache, 3 * 1024 * 1024, 4 * 1024 * 1024)) {
3396 test_msg("Left something behind when removing space");
3397 return -1;
3398 }
3399
3400 /*
3401 * This has blown up in the past, the extent entry starts before the
3402 * bitmap entry, but we're trying to remove an offset that falls
3403 * completely within the bitmap range and is in both the extent entry
3404 * and the bitmap entry, looks like this
3405 *
3406 * [ extent ]
3407 * [ bitmap ]
3408 * [ del ]
3409 */
3410 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3411 ret = add_free_space_entry(cache, bitmap_offset + 4 * 1024 * 1024,
3412 4 * 1024 * 1024, 1);
3413 if (ret) {
3414 test_msg("Couldn't add bitmap %d\n", ret);
3415 return ret;
3416 }
3417
3418 ret = add_free_space_entry(cache, bitmap_offset - 1 * 1024 * 1024,
3419 5 * 1024 * 1024, 0);
3420 if (ret) {
3421 test_msg("Couldn't add extent entry %d\n", ret);
3422 return ret;
3423 }
3424
3425 ret = btrfs_remove_free_space(cache, bitmap_offset + 1 * 1024 * 1024,
3426 5 * 1024 * 1024);
3427 if (ret) {
3428 test_msg("Failed to free our space %d\n", ret);
3429 return ret;
3430 }
3431
3432 if (check_exists(cache, bitmap_offset + 1 * 1024 * 1024,
3433 5 * 1024 * 1024)) {
3434 test_msg("Left stuff over\n");
3435 return -1;
3436 }
3437
3438 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3439
3440 /*
3441 * This blew up before, we have part of the free space in a bitmap and
3442 * then the entirety of the rest of the space in an extent. This used
3443 * to return -EAGAIN back from btrfs_remove_extent, make sure this
3444 * doesn't happen.
3445 */
3446 ret = add_free_space_entry(cache, 1 * 1024 * 1024, 2 * 1024 * 1024, 1);
3447 if (ret) {
3448 test_msg("Couldn't add bitmap entry %d\n", ret);
3449 return ret;
3450 }
3451
3452 ret = add_free_space_entry(cache, 3 * 1024 * 1024, 1 * 1024 * 1024, 0);
3453 if (ret) {
3454 test_msg("Couldn't add extent entry %d\n", ret);
3455 return ret;
3456 }
3457
3458 ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 3 * 1024 * 1024);
3459 if (ret) {
3460 test_msg("Error removing bitmap and extent overlapping %d\n", ret);
3461 return ret;
3462 }
3463
3464 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3465 return 0;
3466}
3467
3468void btrfs_test_free_space_cache(void)
3469{
3470 struct btrfs_block_group_cache *cache;
3471
3472 test_msg("Running btrfs free space cache tests\n");
3473
3474 cache = init_test_block_group();
3475 if (!cache) {
3476 test_msg("Couldn't run the tests\n");
3477 return;
3478 }
3479
3480 if (test_extents(cache))
3481 goto out;
3482 if (test_bitmaps(cache))
3483 goto out;
3484 if (test_bitmaps_and_extents(cache))
3485 goto out;
3486out:
3487 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3488 kfree(cache->free_space_ctl);
3489 kfree(cache);
3490 test_msg("Free space cache tests finished\n");
3491}
3492#undef test_msg
3493#else /* !CONFIG_BTRFS_FS_RUN_SANITY_TESTS */
3494void btrfs_test_free_space_cache(void) {}
3495#endif /* !CONFIG_BTRFS_FS_RUN_SANITY_TESTS */