free-space-cache.c (00361589d2eebd90fca022148c763e40d3e90871) free-space-cache.c (dc11dd5d707a4157882f281c96055d6894d10c8c)
1/*
2 * Copyright (C) 2008 Red Hat. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,

--- 2958 unchanged lines hidden (view full) ---

2967#endif
2968 }
2969
2970 iput(inode);
2971 return ret;
2972}
2973
2974#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
1/*
2 * Copyright (C) 2008 Red Hat. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,

--- 2958 unchanged lines hidden (view full) ---

2967#endif
2968 }
2969
2970 iput(inode);
2971 return ret;
2972}
2973
2974#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
2975static struct btrfs_block_group_cache *init_test_block_group(void)
2975/*
2976 * Use this if you need to make a bitmap or extent entry specifically, it
2977 * doesn't do any of the merging that add_free_space does, this acts a lot like
2978 * how the free space cache loading stuff works, so you can get really weird
2979 * configurations.
2980 */
2981int test_add_free_space_entry(struct btrfs_block_group_cache *cache,
2982 u64 offset, u64 bytes, bool bitmap)
2976{
2983{
2977 struct btrfs_block_group_cache *cache;
2984 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
2985 struct btrfs_free_space *info = NULL, *bitmap_info;
2986 void *map = NULL;
2987 u64 bytes_added;
2988 int ret;
2978
2989
2979 cache = kzalloc(sizeof(*cache), GFP_NOFS);
2980 if (!cache)
2981 return NULL;
2982 cache->free_space_ctl = kzalloc(sizeof(*cache->free_space_ctl),
2983 GFP_NOFS);
2984 if (!cache->free_space_ctl) {
2985 kfree(cache);
2986 return NULL;
2990again:
2991 if (!info) {
2992 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
2993 if (!info)
2994 return -ENOMEM;
2987 }
2988
2995 }
2996
2989 cache->key.objectid = 0;
2990 cache->key.offset = 1024 * 1024 * 1024;
2991 cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
2992 cache->sectorsize = 4096;
2997 if (!bitmap) {
2998 spin_lock(&ctl->tree_lock);
2999 info->offset = offset;
3000 info->bytes = bytes;
3001 ret = link_free_space(ctl, info);
3002 spin_unlock(&ctl->tree_lock);
3003 if (ret)
3004 kmem_cache_free(btrfs_free_space_cachep, info);
3005 return ret;
3006 }
2993
3007
2994 spin_lock_init(&cache->lock);
2995 INIT_LIST_HEAD(&cache->list);
2996 INIT_LIST_HEAD(&cache->cluster_list);
2997 INIT_LIST_HEAD(&cache->new_bg_list);
3008 if (!map) {
3009 map = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
3010 if (!map) {
3011 kmem_cache_free(btrfs_free_space_cachep, info);
3012 return -ENOMEM;
3013 }
3014 }
2998
3015
2999 btrfs_init_free_space_ctl(cache);
3016 spin_lock(&ctl->tree_lock);
3017 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3018 1, 0);
3019 if (!bitmap_info) {
3020 info->bitmap = map;
3021 map = NULL;
3022 add_new_bitmap(ctl, info, offset);
3023 bitmap_info = info;
3024 }
3000
3025
3001 return cache;
3026 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
3027 bytes -= bytes_added;
3028 offset += bytes_added;
3029 spin_unlock(&ctl->tree_lock);
3030
3031 if (bytes)
3032 goto again;
3033
3034 if (map)
3035 kfree(map);
3036 return 0;
3002}
3003
3004/*
3005 * Checks to see if the given range is in the free space cache. This is really
3006 * just used to check the absence of space, so if there is free space in the
3007 * range at all we will return 1.
3008 */
3037}
3038
3039/*
3040 * Checks to see if the given range is in the free space cache. This is really
3041 * just used to check the absence of space, so if there is free space in the
3042 * range at all we will return 1.
3043 */
3009static int check_exists(struct btrfs_block_group_cache *cache, u64 offset,
3010 u64 bytes)
3044int test_check_exists(struct btrfs_block_group_cache *cache,
3045 u64 offset, u64 bytes)
3011{
3012 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3013 struct btrfs_free_space *info;
3014 int ret = 0;
3015
3016 spin_lock(&ctl->tree_lock);
3017 info = tree_search_offset(ctl, offset, 0, 0);
3018 if (!info) {

--- 60 unchanged lines hidden (view full) ---

3079 }
3080
3081 if (offset > info->offset && offset < info->offset + info->bytes)
3082 ret = 1;
3083out:
3084 spin_unlock(&ctl->tree_lock);
3085 return ret;
3086}
3046{
3047 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3048 struct btrfs_free_space *info;
3049 int ret = 0;
3050
3051 spin_lock(&ctl->tree_lock);
3052 info = tree_search_offset(ctl, offset, 0, 0);
3053 if (!info) {

--- 60 unchanged lines hidden (view full) ---

3114 }
3115
3116 if (offset > info->offset && offset < info->offset + info->bytes)
3117 ret = 1;
3118out:
3119 spin_unlock(&ctl->tree_lock);
3120 return ret;
3121}
3087
3088/*
3089 * Use this if you need to make a bitmap or extent entry specifically, it
3090 * doesn't do any of the merging that add_free_space does, this acts a lot like
3091 * how the free space cache loading stuff works, so you can get really weird
3092 * configurations.
3093 */
3094static int add_free_space_entry(struct btrfs_block_group_cache *cache,
3095 u64 offset, u64 bytes, bool bitmap)
3096{
3097 struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
3098 struct btrfs_free_space *info = NULL, *bitmap_info;
3099 void *map = NULL;
3100 u64 bytes_added;
3101 int ret;
3102
3103again:
3104 if (!info) {
3105 info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
3106 if (!info)
3107 return -ENOMEM;
3108 }
3109
3110 if (!bitmap) {
3111 spin_lock(&ctl->tree_lock);
3112 info->offset = offset;
3113 info->bytes = bytes;
3114 ret = link_free_space(ctl, info);
3115 spin_unlock(&ctl->tree_lock);
3116 if (ret)
3117 kmem_cache_free(btrfs_free_space_cachep, info);
3118 return ret;
3119 }
3120
3121 if (!map) {
3122 map = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS);
3123 if (!map) {
3124 kmem_cache_free(btrfs_free_space_cachep, info);
3125 return -ENOMEM;
3126 }
3127 }
3128
3129 spin_lock(&ctl->tree_lock);
3130 bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
3131 1, 0);
3132 if (!bitmap_info) {
3133 info->bitmap = map;
3134 map = NULL;
3135 add_new_bitmap(ctl, info, offset);
3136 bitmap_info = info;
3137 }
3138
3139 bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes);
3140 bytes -= bytes_added;
3141 offset += bytes_added;
3142 spin_unlock(&ctl->tree_lock);
3143
3144 if (bytes)
3145 goto again;
3146
3147 if (map)
3148 kfree(map);
3149 return 0;
3150}
3151
3152#define test_msg(fmt, ...) printk(KERN_INFO "btrfs: selftest: " fmt, ##__VA_ARGS__)
3153
3154/*
3155 * This test just does basic sanity checking, making sure we can add an exten
3156 * entry and remove space from either end and the middle, and make sure we can
3157 * remove space that covers adjacent extent entries.
3158 */
3159static int test_extents(struct btrfs_block_group_cache *cache)
3160{
3161 int ret = 0;
3162
3163 test_msg("Running extent only tests\n");
3164
3165 /* First just make sure we can remove an entire entry */
3166 ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
3167 if (ret) {
3168 test_msg("Error adding initial extents %d\n", ret);
3169 return ret;
3170 }
3171
3172 ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
3173 if (ret) {
3174 test_msg("Error removing extent %d\n", ret);
3175 return ret;
3176 }
3177
3178 if (check_exists(cache, 0, 4 * 1024 * 1024)) {
3179 test_msg("Full remove left some lingering space\n");
3180 return -1;
3181 }
3182
3183 /* Ok edge and middle cases now */
3184 ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
3185 if (ret) {
3186 test_msg("Error adding half extent %d\n", ret);
3187 return ret;
3188 }
3189
3190 ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 1 * 1024 * 1024);
3191 if (ret) {
3192 test_msg("Error removing tail end %d\n", ret);
3193 return ret;
3194 }
3195
3196 ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
3197 if (ret) {
3198 test_msg("Error removing front end %d\n", ret);
3199 return ret;
3200 }
3201
3202 ret = btrfs_remove_free_space(cache, 2 * 1024 * 1024, 4096);
3203 if (ret) {
3204 test_msg("Error removing middle piece %d\n", ret);
3205 return ret;
3206 }
3207
3208 if (check_exists(cache, 0, 1 * 1024 * 1024)) {
3209 test_msg("Still have space at the front\n");
3210 return -1;
3211 }
3212
3213 if (check_exists(cache, 2 * 1024 * 1024, 4096)) {
3214 test_msg("Still have space in the middle\n");
3215 return -1;
3216 }
3217
3218 if (check_exists(cache, 3 * 1024 * 1024, 1 * 1024 * 1024)) {
3219 test_msg("Still have space at the end\n");
3220 return -1;
3221 }
3222
3223 /* Cleanup */
3224 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3225
3226 return 0;
3227}
3228
3229static int test_bitmaps(struct btrfs_block_group_cache *cache)
3230{
3231 u64 next_bitmap_offset;
3232 int ret;
3233
3234 test_msg("Running bitmap only tests\n");
3235
3236 ret = add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
3237 if (ret) {
3238 test_msg("Couldn't create a bitmap entry %d\n", ret);
3239 return ret;
3240 }
3241
3242 ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
3243 if (ret) {
3244 test_msg("Error removing bitmap full range %d\n", ret);
3245 return ret;
3246 }
3247
3248 if (check_exists(cache, 0, 4 * 1024 * 1024)) {
3249 test_msg("Left some space in bitmap\n");
3250 return -1;
3251 }
3252
3253 ret = add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
3254 if (ret) {
3255 test_msg("Couldn't add to our bitmap entry %d\n", ret);
3256 return ret;
3257 }
3258
3259 ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 2 * 1024 * 1024);
3260 if (ret) {
3261 test_msg("Couldn't remove middle chunk %d\n", ret);
3262 return ret;
3263 }
3264
3265 /*
3266 * The first bitmap we have starts at offset 0 so the next one is just
3267 * at the end of the first bitmap.
3268 */
3269 next_bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
3270
3271 /* Test a bit straddling two bitmaps */
3272 ret = add_free_space_entry(cache, next_bitmap_offset -
3273 (2 * 1024 * 1024), 4 * 1024 * 1024, 1);
3274 if (ret) {
3275 test_msg("Couldn't add space that straddles two bitmaps %d\n",
3276 ret);
3277 return ret;
3278 }
3279
3280 ret = btrfs_remove_free_space(cache, next_bitmap_offset -
3281 (1 * 1024 * 1024), 2 * 1024 * 1024);
3282 if (ret) {
3283 test_msg("Couldn't remove overlapping space %d\n", ret);
3284 return ret;
3285 }
3286
3287 if (check_exists(cache, next_bitmap_offset - (1 * 1024 * 1024),
3288 2 * 1024 * 1024)) {
3289 test_msg("Left some space when removing overlapping\n");
3290 return -1;
3291 }
3292
3293 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3294
3295 return 0;
3296}
3297
3298/* This is the high grade jackassery */
3299static int test_bitmaps_and_extents(struct btrfs_block_group_cache *cache)
3300{
3301 u64 bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
3302 int ret;
3303
3304 test_msg("Running bitmap and extent tests\n");
3305
3306 /*
3307 * First let's do something simple, an extent at the same offset as the
3308 * bitmap, but the free space completely in the extent and then
3309 * completely in the bitmap.
3310 */
3311 ret = add_free_space_entry(cache, 4 * 1024 * 1024, 1 * 1024 * 1024, 1);
3312 if (ret) {
3313 test_msg("Couldn't create bitmap entry %d\n", ret);
3314 return ret;
3315 }
3316
3317 ret = add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
3318 if (ret) {
3319 test_msg("Couldn't add extent entry %d\n", ret);
3320 return ret;
3321 }
3322
3323 ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
3324 if (ret) {
3325 test_msg("Couldn't remove extent entry %d\n", ret);
3326 return ret;
3327 }
3328
3329 if (check_exists(cache, 0, 1 * 1024 * 1024)) {
3330 test_msg("Left remnants after our remove\n");
3331 return -1;
3332 }
3333
3334 /* Now to add back the extent entry and remove from the bitmap */
3335 ret = add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
3336 if (ret) {
3337 test_msg("Couldn't re-add extent entry %d\n", ret);
3338 return ret;
3339 }
3340
3341 ret = btrfs_remove_free_space(cache, 4 * 1024 * 1024, 1 * 1024 * 1024);
3342 if (ret) {
3343 test_msg("Couldn't remove from bitmap %d\n", ret);
3344 return ret;
3345 }
3346
3347 if (check_exists(cache, 4 * 1024 * 1024, 1 * 1024 * 1024)) {
3348 test_msg("Left remnants in the bitmap\n");
3349 return -1;
3350 }
3351
3352 /*
3353 * Ok so a little more evil, extent entry and bitmap at the same offset,
3354 * removing an overlapping chunk.
3355 */
3356 ret = add_free_space_entry(cache, 1 * 1024 * 1024, 4 * 1024 * 1024, 1);
3357 if (ret) {
3358 test_msg("Couldn't add to a bitmap %d\n", ret);
3359 return ret;
3360 }
3361
3362 ret = btrfs_remove_free_space(cache, 512 * 1024, 3 * 1024 * 1024);
3363 if (ret) {
3364 test_msg("Couldn't remove overlapping space %d\n", ret);
3365 return ret;
3366 }
3367
3368 if (check_exists(cache, 512 * 1024, 3 * 1024 * 1024)) {
3369 test_msg("Left over peices after removing overlapping\n");
3370 return -1;
3371 }
3372
3373 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3374
3375 /* Now with the extent entry offset into the bitmap */
3376 ret = add_free_space_entry(cache, 4 * 1024 * 1024, 4 * 1024 * 1024, 1);
3377 if (ret) {
3378 test_msg("Couldn't add space to the bitmap %d\n", ret);
3379 return ret;
3380 }
3381
3382 ret = add_free_space_entry(cache, 2 * 1024 * 1024, 2 * 1024 * 1024, 0);
3383 if (ret) {
3384 test_msg("Couldn't add extent to the cache %d\n", ret);
3385 return ret;
3386 }
3387
3388 ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 4 * 1024 * 1024);
3389 if (ret) {
3390 test_msg("Problem removing overlapping space %d\n", ret);
3391 return ret;
3392 }
3393
3394 if (check_exists(cache, 3 * 1024 * 1024, 4 * 1024 * 1024)) {
3395 test_msg("Left something behind when removing space");
3396 return -1;
3397 }
3398
3399 /*
3400 * This has blown up in the past, the extent entry starts before the
3401 * bitmap entry, but we're trying to remove an offset that falls
3402 * completely within the bitmap range and is in both the extent entry
3403 * and the bitmap entry, looks like this
3404 *
3405 * [ extent ]
3406 * [ bitmap ]
3407 * [ del ]
3408 */
3409 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3410 ret = add_free_space_entry(cache, bitmap_offset + 4 * 1024 * 1024,
3411 4 * 1024 * 1024, 1);
3412 if (ret) {
3413 test_msg("Couldn't add bitmap %d\n", ret);
3414 return ret;
3415 }
3416
3417 ret = add_free_space_entry(cache, bitmap_offset - 1 * 1024 * 1024,
3418 5 * 1024 * 1024, 0);
3419 if (ret) {
3420 test_msg("Couldn't add extent entry %d\n", ret);
3421 return ret;
3422 }
3423
3424 ret = btrfs_remove_free_space(cache, bitmap_offset + 1 * 1024 * 1024,
3425 5 * 1024 * 1024);
3426 if (ret) {
3427 test_msg("Failed to free our space %d\n", ret);
3428 return ret;
3429 }
3430
3431 if (check_exists(cache, bitmap_offset + 1 * 1024 * 1024,
3432 5 * 1024 * 1024)) {
3433 test_msg("Left stuff over\n");
3434 return -1;
3435 }
3436
3437 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3438
3439 /*
3440 * This blew up before, we have part of the free space in a bitmap and
3441 * then the entirety of the rest of the space in an extent. This used
3442 * to return -EAGAIN back from btrfs_remove_extent, make sure this
3443 * doesn't happen.
3444 */
3445 ret = add_free_space_entry(cache, 1 * 1024 * 1024, 2 * 1024 * 1024, 1);
3446 if (ret) {
3447 test_msg("Couldn't add bitmap entry %d\n", ret);
3448 return ret;
3449 }
3450
3451 ret = add_free_space_entry(cache, 3 * 1024 * 1024, 1 * 1024 * 1024, 0);
3452 if (ret) {
3453 test_msg("Couldn't add extent entry %d\n", ret);
3454 return ret;
3455 }
3456
3457 ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 3 * 1024 * 1024);
3458 if (ret) {
3459 test_msg("Error removing bitmap and extent overlapping %d\n", ret);
3460 return ret;
3461 }
3462
3463 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3464 return 0;
3465}
3466
3467void btrfs_test_free_space_cache(void)
3468{
3469 struct btrfs_block_group_cache *cache;
3470
3471 test_msg("Running btrfs free space cache tests\n");
3472
3473 cache = init_test_block_group();
3474 if (!cache) {
3475 test_msg("Couldn't run the tests\n");
3476 return;
3477 }
3478
3479 if (test_extents(cache))
3480 goto out;
3481 if (test_bitmaps(cache))
3482 goto out;
3483 if (test_bitmaps_and_extents(cache))
3484 goto out;
3485out:
3486 __btrfs_remove_free_space_cache(cache->free_space_ctl);
3487 kfree(cache->free_space_ctl);
3488 kfree(cache);
3489 test_msg("Free space cache tests finished\n");
3490}
3491#undef test_msg
3492#else /* !CONFIG_BTRFS_FS_RUN_SANITY_TESTS */
3493void btrfs_test_free_space_cache(void) {}
3494#endif /* !CONFIG_BTRFS_FS_RUN_SANITY_TESTS */
3122#endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */