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 } 396