fs/btrfs/tests/free-space-tests.c

   1 /*
   2  * Copyright (C) 2013 Fusion IO.  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,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include <linux/slab.h>
  20 #include "btrfs-tests.h"
  21 #include "../ctree.h"
  22 #include "../free-space-cache.h"
  23
  24 #define BITS_PER_BITMAP         (PAGE_CACHE_SIZE * 8)
  25 static struct btrfs_block_group_cache *init_test_block_group(void)
  26 {
  27         struct btrfs_block_group_cache *cache;
  28
  29         cache = kzalloc(sizeof(*cache), GFP_NOFS);
  30         if (!cache)
  31                 return NULL;
  32         cache->free_space_ctl = kzalloc(sizeof(*cache->free_space_ctl),
  33                                         GFP_NOFS);
  34         if (!cache->free_space_ctl) {
  35                 kfree(cache);
  36                 return NULL;
  37         }
  38
  39         cache->key.objectid = 0;
  40         cache->key.offset = 1024 * 1024 * 1024;
  41         cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
  42         cache->sectorsize = 4096;
  43
  44         spin_lock_init(&cache->lock);
  45         INIT_LIST_HEAD(&cache->list);
  46         INIT_LIST_HEAD(&cache->cluster_list);
  47         INIT_LIST_HEAD(&cache->new_bg_list);
  48
  49         btrfs_init_free_space_ctl(cache);
  50
  51         return cache;
  52 }
  53
  54 /*
  55  * This test just does basic sanity checking, making sure we can add an exten
  56  * entry and remove space from either end and the middle, and make sure we can
  57  * remove space that covers adjacent extent entries.
  58  */
  59 static int test_extents(struct btrfs_block_group_cache *cache)
  60 {
  61         int ret = 0;
  62
  63         test_msg("Running extent only tests\n");
  64
  65         /* First just make sure we can remove an entire entry */
  66         ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
  67         if (ret) {
  68                 test_msg("Error adding initial extents %d\n", ret);
  69                 return ret;
  70         }
  71
  72         ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
  73         if (ret) {
  74                 test_msg("Error removing extent %d\n", ret);
  75                 return ret;
  76         }
  77
  78         if (test_check_exists(cache, 0, 4 * 1024 * 1024)) {
  79                 test_msg("Full remove left some lingering space\n");
  80                 return -1;
  81         }
  82
  83         /* Ok edge and middle cases now */
  84         ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
  85         if (ret) {
  86                 test_msg("Error adding half extent %d\n", ret);
  87                 return ret;
  88         }
  89
  90         ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 1 * 1024 * 1024);
  91         if (ret) {
  92                 test_msg("Error removing tail end %d\n", ret);
  93                 return ret;
  94         }
  95
  96         ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
  97         if (ret) {
  98                 test_msg("Error removing front end %d\n", ret);
  99                 return ret;
 100         }
 101
 102         ret = btrfs_remove_free_space(cache, 2 * 1024 * 1024, 4096);
 103         if (ret) {
 104                 test_msg("Error removing middle piece %d\n", ret);
 105                 return ret;
 106         }
 107
 108         if (test_check_exists(cache, 0, 1 * 1024 * 1024)) {
 109                 test_msg("Still have space at the front\n");
 110                 return -1;
 111         }
 112
 113         if (test_check_exists(cache, 2 * 1024 * 1024, 4096)) {
 114                 test_msg("Still have space in the middle\n");
 115                 return -1;
 116         }
 117
 118         if (test_check_exists(cache, 3 * 1024 * 1024, 1 * 1024 * 1024)) {
 119                 test_msg("Still have space at the end\n");
 120                 return -1;
 121         }
 122
 123         /* Cleanup */
 124         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 125
 126         return 0;
 127 }
 128
 129 static int test_bitmaps(struct btrfs_block_group_cache *cache)
 130 {
 131         u64 next_bitmap_offset;
 132         int ret;
 133
 134         test_msg("Running bitmap only tests\n");
 135
 136         ret = test_add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
 137         if (ret) {
 138                 test_msg("Couldn't create a bitmap entry %d\n", ret);
 139                 return ret;
 140         }
 141
 142         ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
 143         if (ret) {
 144                 test_msg("Error removing bitmap full range %d\n", ret);
 145                 return ret;
 146         }
 147
 148         if (test_check_exists(cache, 0, 4 * 1024 * 1024)) {
 149                 test_msg("Left some space in bitmap\n");
 150                 return -1;
 151         }
 152
 153         ret = test_add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
 154         if (ret) {
 155                 test_msg("Couldn't add to our bitmap entry %d\n", ret);
 156                 return ret;
 157         }
 158
 159         ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 2 * 1024 * 1024);
 160         if (ret) {
 161                 test_msg("Couldn't remove middle chunk %d\n", ret);
 162                 return ret;
 163         }
 164
 165         /*
 166          * The first bitmap we have starts at offset 0 so the next one is just
 167          * at the end of the first bitmap.
 168          */
 169         next_bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
 170
 171         /* Test a bit straddling two bitmaps */
 172         ret = test_add_free_space_entry(cache, next_bitmap_offset -
 173                                    (2 * 1024 * 1024), 4 * 1024 * 1024, 1);
 174         if (ret) {
 175                 test_msg("Couldn't add space that straddles two bitmaps %d\n",
 176                                 ret);
 177                 return ret;
 178         }
 179
 180         ret = btrfs_remove_free_space(cache, next_bitmap_offset -
 181                                       (1 * 1024 * 1024), 2 * 1024 * 1024);
 182         if (ret) {
 183                 test_msg("Couldn't remove overlapping space %d\n", ret);
 184                 return ret;
 185         }
 186
 187         if (test_check_exists(cache, next_bitmap_offset - (1 * 1024 * 1024),
 188                          2 * 1024 * 1024)) {
 189                 test_msg("Left some space when removing overlapping\n");
 190                 return -1;
 191         }
 192
 193         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 194
 195         return 0;
 196 }
 197
 198 /* This is the high grade jackassery */
 199 static int test_bitmaps_and_extents(struct btrfs_block_group_cache *cache)
 200 {
 201         u64 bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
 202         int ret;
 203
 204         test_msg("Running bitmap and extent tests\n");
 205
 206         /*
 207          * First let's do something simple, an extent at the same offset as the
 208          * bitmap, but the free space completely in the extent and then
 209          * completely in the bitmap.
 210          */
 211         ret = test_add_free_space_entry(cache, 4 * 1024 * 1024, 1 * 1024 * 1024, 1);
 212         if (ret) {
 213                 test_msg("Couldn't create bitmap entry %d\n", ret);
 214                 return ret;
 215         }
 216
 217         ret = test_add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
 218         if (ret) {
 219                 test_msg("Couldn't add extent entry %d\n", ret);
 220                 return ret;
 221         }
 222
 223         ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
 224         if (ret) {
 225                 test_msg("Couldn't remove extent entry %d\n", ret);
 226                 return ret;
 227         }
 228
 229         if (test_check_exists(cache, 0, 1 * 1024 * 1024)) {
 230                 test_msg("Left remnants after our remove\n");
 231                 return -1;
 232         }
 233
 234         /* Now to add back the extent entry and remove from the bitmap */
 235         ret = test_add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
 236         if (ret) {
 237                 test_msg("Couldn't re-add extent entry %d\n", ret);
 238                 return ret;
 239         }
 240
 241         ret = btrfs_remove_free_space(cache, 4 * 1024 * 1024, 1 * 1024 * 1024);
 242         if (ret) {
 243                 test_msg("Couldn't remove from bitmap %d\n", ret);
 244                 return ret;
 245         }
 246
 247         if (test_check_exists(cache, 4 * 1024 * 1024, 1 * 1024 * 1024)) {
 248                 test_msg("Left remnants in the bitmap\n");
 249                 return -1;
 250         }
 251
 252         /*
 253          * Ok so a little more evil, extent entry and bitmap at the same offset,
 254          * removing an overlapping chunk.
 255          */
 256         ret = test_add_free_space_entry(cache, 1 * 1024 * 1024, 4 * 1024 * 1024, 1);
 257         if (ret) {
 258                 test_msg("Couldn't add to a bitmap %d\n", ret);
 259                 return ret;
 260         }
 261
 262         ret = btrfs_remove_free_space(cache, 512 * 1024, 3 * 1024 * 1024);
 263         if (ret) {
 264                 test_msg("Couldn't remove overlapping space %d\n", ret);
 265                 return ret;
 266         }
 267
 268         if (test_check_exists(cache, 512 * 1024, 3 * 1024 * 1024)) {
 269                 test_msg("Left over pieces after removing overlapping\n");
 270                 return -1;
 271         }
 272
 273         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 274
 275         /* Now with the extent entry offset into the bitmap */
 276         ret = test_add_free_space_entry(cache, 4 * 1024 * 1024, 4 * 1024 * 1024, 1);
 277         if (ret) {
 278                 test_msg("Couldn't add space to the bitmap %d\n", ret);
 279                 return ret;
 280         }
 281
 282         ret = test_add_free_space_entry(cache, 2 * 1024 * 1024, 2 * 1024 * 1024, 0);
 283         if (ret) {
 284                 test_msg("Couldn't add extent to the cache %d\n", ret);
 285                 return ret;
 286         }
 287
 288         ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 4 * 1024 * 1024);
 289         if (ret) {
 290                 test_msg("Problem removing overlapping space %d\n", ret);
 291                 return ret;
 292         }
 293
 294         if (test_check_exists(cache, 3 * 1024 * 1024, 4 * 1024 * 1024)) {
 295                 test_msg("Left something behind when removing space");
 296                 return -1;
 297         }
 298
 299         /*
 300          * This has blown up in the past, the extent entry starts before the
 301          * bitmap entry, but we're trying to remove an offset that falls
 302          * completely within the bitmap range and is in both the extent entry
 303          * and the bitmap entry, looks like this
 304          *
 305          *   [ extent ]
 306          *      [ bitmap ]
 307          *        [ del ]
 308          */
 309         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 310         ret = test_add_free_space_entry(cache, bitmap_offset + 4 * 1024 * 1024,
 311                                    4 * 1024 * 1024, 1);
 312         if (ret) {
 313                 test_msg("Couldn't add bitmap %d\n", ret);
 314                 return ret;
 315         }
 316
 317         ret = test_add_free_space_entry(cache, bitmap_offset - 1 * 1024 * 1024,
 318                                    5 * 1024 * 1024, 0);
 319         if (ret) {
 320                 test_msg("Couldn't add extent entry %d\n", ret);
 321                 return ret;
 322         }
 323
 324         ret = btrfs_remove_free_space(cache, bitmap_offset + 1 * 1024 * 1024,
 325                                       5 * 1024 * 1024);
 326         if (ret) {
 327                 test_msg("Failed to free our space %d\n", ret);
 328                 return ret;
 329         }
 330
 331         if (test_check_exists(cache, bitmap_offset + 1 * 1024 * 1024,
 332                          5 * 1024 * 1024)) {
 333                 test_msg("Left stuff over\n");
 334                 return -1;
 335         }
 336
 337         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 338
 339         /*
 340          * This blew up before, we have part of the free space in a bitmap and
 341          * then the entirety of the rest of the space in an extent.  This used
 342          * to return -EAGAIN back from btrfs_remove_extent, make sure this
 343          * doesn't happen.
 344          */
 345         ret = test_add_free_space_entry(cache, 1 * 1024 * 1024, 2 * 1024 * 1024, 1);
 346         if (ret) {
 347                 test_msg("Couldn't add bitmap entry %d\n", ret);
 348                 return ret;
 349         }
 350
 351         ret = test_add_free_space_entry(cache, 3 * 1024 * 1024, 1 * 1024 * 1024, 0);
 352         if (ret) {
 353                 test_msg("Couldn't add extent entry %d\n", ret);
 354                 return ret;
 355         }
 356
 357         ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 3 * 1024 * 1024);
 358         if (ret) {
 359                 test_msg("Error removing bitmap and extent overlapping %d\n", ret);
 360                 return ret;
 361         }
 362
 363         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 364         return 0;
 365 }
 366
 367 int btrfs_test_free_space_cache(void)
 368 {
 369         struct btrfs_block_group_cache *cache;
 370         int ret;
 371
 372         test_msg("Running btrfs free space cache tests\n");
 373
 374         cache = init_test_block_group();
 375         if (!cache) {
 376                 test_msg("Couldn't run the tests\n");
 377                 return 0;
 378         }
 379
 380         ret = test_extents(cache);
 381         if (ret)
 382                 goto out;
 383         ret = test_bitmaps(cache);
 384         if (ret)
 385                 goto out;
 386         ret = test_bitmaps_and_extents(cache);
 387         if (ret)
 388                 goto out;
 389 out:
 390         __btrfs_remove_free_space_cache(cache->free_space_ctl);
 391         kfree(cache->free_space_ctl);
 392         kfree(cache);
 393         test_msg("Free space cache tests finished\n");
 394         return ret;
 395 }