blob: 69a11e63d668339ecb9f2f3a42b7eeeb22b9d634 [file] [log] [blame]
Josef Bacikdc11dd52013-08-14 15:05:12 -04001/*
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"
Josef Bacikd0bd4562015-09-23 14:54:14 -040022#include "../disk-io.h"
Josef Bacikdc11dd52013-08-14 15:05:12 -040023#include "../free-space-cache.h"
24
25#define BITS_PER_BITMAP (PAGE_CACHE_SIZE * 8)
26static struct btrfs_block_group_cache *init_test_block_group(void)
27{
28 struct btrfs_block_group_cache *cache;
29
30 cache = kzalloc(sizeof(*cache), GFP_NOFS);
31 if (!cache)
32 return NULL;
33 cache->free_space_ctl = kzalloc(sizeof(*cache->free_space_ctl),
34 GFP_NOFS);
35 if (!cache->free_space_ctl) {
36 kfree(cache);
37 return NULL;
38 }
Josef Bacikd0bd4562015-09-23 14:54:14 -040039 cache->fs_info = btrfs_alloc_dummy_fs_info();
40 if (!cache->fs_info) {
41 kfree(cache->free_space_ctl);
42 kfree(cache);
43 return NULL;
44 }
Josef Bacikdc11dd52013-08-14 15:05:12 -040045
46 cache->key.objectid = 0;
47 cache->key.offset = 1024 * 1024 * 1024;
48 cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
49 cache->sectorsize = 4096;
Filipe Manana20005522014-08-29 13:35:13 +010050 cache->full_stripe_len = 4096;
Josef Bacikdc11dd52013-08-14 15:05:12 -040051
52 spin_lock_init(&cache->lock);
53 INIT_LIST_HEAD(&cache->list);
54 INIT_LIST_HEAD(&cache->cluster_list);
Josef Bacik47ab2a62014-09-18 11:20:02 -040055 INIT_LIST_HEAD(&cache->bg_list);
Josef Bacikdc11dd52013-08-14 15:05:12 -040056
57 btrfs_init_free_space_ctl(cache);
58
59 return cache;
60}
61
62/*
63 * This test just does basic sanity checking, making sure we can add an exten
64 * entry and remove space from either end and the middle, and make sure we can
65 * remove space that covers adjacent extent entries.
66 */
67static int test_extents(struct btrfs_block_group_cache *cache)
68{
69 int ret = 0;
70
71 test_msg("Running extent only tests\n");
72
73 /* First just make sure we can remove an entire entry */
74 ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
75 if (ret) {
76 test_msg("Error adding initial extents %d\n", ret);
77 return ret;
78 }
79
80 ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
81 if (ret) {
82 test_msg("Error removing extent %d\n", ret);
83 return ret;
84 }
85
86 if (test_check_exists(cache, 0, 4 * 1024 * 1024)) {
87 test_msg("Full remove left some lingering space\n");
88 return -1;
89 }
90
91 /* Ok edge and middle cases now */
92 ret = btrfs_add_free_space(cache, 0, 4 * 1024 * 1024);
93 if (ret) {
94 test_msg("Error adding half extent %d\n", ret);
95 return ret;
96 }
97
98 ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 1 * 1024 * 1024);
99 if (ret) {
100 test_msg("Error removing tail end %d\n", ret);
101 return ret;
102 }
103
104 ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
105 if (ret) {
106 test_msg("Error removing front end %d\n", ret);
107 return ret;
108 }
109
110 ret = btrfs_remove_free_space(cache, 2 * 1024 * 1024, 4096);
111 if (ret) {
Masanari Iida77d84ff2013-12-09 00:22:53 +0900112 test_msg("Error removing middle piece %d\n", ret);
Josef Bacikdc11dd52013-08-14 15:05:12 -0400113 return ret;
114 }
115
116 if (test_check_exists(cache, 0, 1 * 1024 * 1024)) {
117 test_msg("Still have space at the front\n");
118 return -1;
119 }
120
121 if (test_check_exists(cache, 2 * 1024 * 1024, 4096)) {
122 test_msg("Still have space in the middle\n");
123 return -1;
124 }
125
126 if (test_check_exists(cache, 3 * 1024 * 1024, 1 * 1024 * 1024)) {
127 test_msg("Still have space at the end\n");
128 return -1;
129 }
130
131 /* Cleanup */
132 __btrfs_remove_free_space_cache(cache->free_space_ctl);
133
134 return 0;
135}
136
137static int test_bitmaps(struct btrfs_block_group_cache *cache)
138{
139 u64 next_bitmap_offset;
140 int ret;
141
142 test_msg("Running bitmap only tests\n");
143
144 ret = test_add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
145 if (ret) {
146 test_msg("Couldn't create a bitmap entry %d\n", ret);
147 return ret;
148 }
149
150 ret = btrfs_remove_free_space(cache, 0, 4 * 1024 * 1024);
151 if (ret) {
152 test_msg("Error removing bitmap full range %d\n", ret);
153 return ret;
154 }
155
156 if (test_check_exists(cache, 0, 4 * 1024 * 1024)) {
157 test_msg("Left some space in bitmap\n");
158 return -1;
159 }
160
161 ret = test_add_free_space_entry(cache, 0, 4 * 1024 * 1024, 1);
162 if (ret) {
163 test_msg("Couldn't add to our bitmap entry %d\n", ret);
164 return ret;
165 }
166
167 ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 2 * 1024 * 1024);
168 if (ret) {
169 test_msg("Couldn't remove middle chunk %d\n", ret);
170 return ret;
171 }
172
173 /*
174 * The first bitmap we have starts at offset 0 so the next one is just
175 * at the end of the first bitmap.
176 */
177 next_bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
178
179 /* Test a bit straddling two bitmaps */
180 ret = test_add_free_space_entry(cache, next_bitmap_offset -
181 (2 * 1024 * 1024), 4 * 1024 * 1024, 1);
182 if (ret) {
183 test_msg("Couldn't add space that straddles two bitmaps %d\n",
184 ret);
185 return ret;
186 }
187
188 ret = btrfs_remove_free_space(cache, next_bitmap_offset -
189 (1 * 1024 * 1024), 2 * 1024 * 1024);
190 if (ret) {
191 test_msg("Couldn't remove overlapping space %d\n", ret);
192 return ret;
193 }
194
195 if (test_check_exists(cache, next_bitmap_offset - (1 * 1024 * 1024),
196 2 * 1024 * 1024)) {
197 test_msg("Left some space when removing overlapping\n");
198 return -1;
199 }
200
201 __btrfs_remove_free_space_cache(cache->free_space_ctl);
202
203 return 0;
204}
205
206/* This is the high grade jackassery */
207static int test_bitmaps_and_extents(struct btrfs_block_group_cache *cache)
208{
209 u64 bitmap_offset = (u64)(BITS_PER_BITMAP * 4096);
210 int ret;
211
212 test_msg("Running bitmap and extent tests\n");
213
214 /*
215 * First let's do something simple, an extent at the same offset as the
216 * bitmap, but the free space completely in the extent and then
217 * completely in the bitmap.
218 */
219 ret = test_add_free_space_entry(cache, 4 * 1024 * 1024, 1 * 1024 * 1024, 1);
220 if (ret) {
221 test_msg("Couldn't create bitmap entry %d\n", ret);
222 return ret;
223 }
224
225 ret = test_add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
226 if (ret) {
227 test_msg("Couldn't add extent entry %d\n", ret);
228 return ret;
229 }
230
231 ret = btrfs_remove_free_space(cache, 0, 1 * 1024 * 1024);
232 if (ret) {
233 test_msg("Couldn't remove extent entry %d\n", ret);
234 return ret;
235 }
236
237 if (test_check_exists(cache, 0, 1 * 1024 * 1024)) {
238 test_msg("Left remnants after our remove\n");
239 return -1;
240 }
241
242 /* Now to add back the extent entry and remove from the bitmap */
243 ret = test_add_free_space_entry(cache, 0, 1 * 1024 * 1024, 0);
244 if (ret) {
245 test_msg("Couldn't re-add extent entry %d\n", ret);
246 return ret;
247 }
248
249 ret = btrfs_remove_free_space(cache, 4 * 1024 * 1024, 1 * 1024 * 1024);
250 if (ret) {
251 test_msg("Couldn't remove from bitmap %d\n", ret);
252 return ret;
253 }
254
255 if (test_check_exists(cache, 4 * 1024 * 1024, 1 * 1024 * 1024)) {
256 test_msg("Left remnants in the bitmap\n");
257 return -1;
258 }
259
260 /*
261 * Ok so a little more evil, extent entry and bitmap at the same offset,
262 * removing an overlapping chunk.
263 */
264 ret = test_add_free_space_entry(cache, 1 * 1024 * 1024, 4 * 1024 * 1024, 1);
265 if (ret) {
266 test_msg("Couldn't add to a bitmap %d\n", ret);
267 return ret;
268 }
269
270 ret = btrfs_remove_free_space(cache, 512 * 1024, 3 * 1024 * 1024);
271 if (ret) {
272 test_msg("Couldn't remove overlapping space %d\n", ret);
273 return ret;
274 }
275
276 if (test_check_exists(cache, 512 * 1024, 3 * 1024 * 1024)) {
Masanari Iida8faaaea2014-01-07 21:58:06 +0900277 test_msg("Left over pieces after removing overlapping\n");
Josef Bacikdc11dd52013-08-14 15:05:12 -0400278 return -1;
279 }
280
281 __btrfs_remove_free_space_cache(cache->free_space_ctl);
282
283 /* Now with the extent entry offset into the bitmap */
284 ret = test_add_free_space_entry(cache, 4 * 1024 * 1024, 4 * 1024 * 1024, 1);
285 if (ret) {
286 test_msg("Couldn't add space to the bitmap %d\n", ret);
287 return ret;
288 }
289
290 ret = test_add_free_space_entry(cache, 2 * 1024 * 1024, 2 * 1024 * 1024, 0);
291 if (ret) {
292 test_msg("Couldn't add extent to the cache %d\n", ret);
293 return ret;
294 }
295
296 ret = btrfs_remove_free_space(cache, 3 * 1024 * 1024, 4 * 1024 * 1024);
297 if (ret) {
298 test_msg("Problem removing overlapping space %d\n", ret);
299 return ret;
300 }
301
302 if (test_check_exists(cache, 3 * 1024 * 1024, 4 * 1024 * 1024)) {
303 test_msg("Left something behind when removing space");
304 return -1;
305 }
306
307 /*
308 * This has blown up in the past, the extent entry starts before the
309 * bitmap entry, but we're trying to remove an offset that falls
310 * completely within the bitmap range and is in both the extent entry
311 * and the bitmap entry, looks like this
312 *
313 * [ extent ]
314 * [ bitmap ]
315 * [ del ]
316 */
317 __btrfs_remove_free_space_cache(cache->free_space_ctl);
318 ret = test_add_free_space_entry(cache, bitmap_offset + 4 * 1024 * 1024,
319 4 * 1024 * 1024, 1);
320 if (ret) {
321 test_msg("Couldn't add bitmap %d\n", ret);
322 return ret;
323 }
324
325 ret = test_add_free_space_entry(cache, bitmap_offset - 1 * 1024 * 1024,
326 5 * 1024 * 1024, 0);
327 if (ret) {
328 test_msg("Couldn't add extent entry %d\n", ret);
329 return ret;
330 }
331
332 ret = btrfs_remove_free_space(cache, bitmap_offset + 1 * 1024 * 1024,
333 5 * 1024 * 1024);
334 if (ret) {
335 test_msg("Failed to free our space %d\n", ret);
336 return ret;
337 }
338
339 if (test_check_exists(cache, bitmap_offset + 1 * 1024 * 1024,
340 5 * 1024 * 1024)) {
341 test_msg("Left stuff over\n");
342 return -1;
343 }
344
345 __btrfs_remove_free_space_cache(cache->free_space_ctl);
346
347 /*
348 * This blew up before, we have part of the free space in a bitmap and
349 * then the entirety of the rest of the space in an extent. This used
350 * to return -EAGAIN back from btrfs_remove_extent, make sure this
351 * doesn't happen.
352 */
353 ret = test_add_free_space_entry(cache, 1 * 1024 * 1024, 2 * 1024 * 1024, 1);
354 if (ret) {
355 test_msg("Couldn't add bitmap entry %d\n", ret);
356 return ret;
357 }
358
359 ret = test_add_free_space_entry(cache, 3 * 1024 * 1024, 1 * 1024 * 1024, 0);
360 if (ret) {
361 test_msg("Couldn't add extent entry %d\n", ret);
362 return ret;
363 }
364
365 ret = btrfs_remove_free_space(cache, 1 * 1024 * 1024, 3 * 1024 * 1024);
366 if (ret) {
367 test_msg("Error removing bitmap and extent overlapping %d\n", ret);
368 return ret;
369 }
370
371 __btrfs_remove_free_space_cache(cache->free_space_ctl);
372 return 0;
373}
374
Filipe Manana20005522014-08-29 13:35:13 +0100375/* Used by test_steal_space_from_bitmap_to_extent(). */
376static bool test_use_bitmap(struct btrfs_free_space_ctl *ctl,
377 struct btrfs_free_space *info)
378{
379 return ctl->free_extents > 0;
380}
381
382/* Used by test_steal_space_from_bitmap_to_extent(). */
383static int
384check_num_extents_and_bitmaps(const struct btrfs_block_group_cache *cache,
385 const int num_extents,
386 const int num_bitmaps)
387{
388 if (cache->free_space_ctl->free_extents != num_extents) {
389 test_msg("Incorrect # of extent entries in the cache: %d, expected %d\n",
390 cache->free_space_ctl->free_extents, num_extents);
391 return -EINVAL;
392 }
393 if (cache->free_space_ctl->total_bitmaps != num_bitmaps) {
394 test_msg("Incorrect # of extent entries in the cache: %d, expected %d\n",
395 cache->free_space_ctl->total_bitmaps, num_bitmaps);
396 return -EINVAL;
397 }
398 return 0;
399}
400
401/* Used by test_steal_space_from_bitmap_to_extent(). */
402static int check_cache_empty(struct btrfs_block_group_cache *cache)
403{
404 u64 offset;
405 u64 max_extent_size;
406
407 /*
408 * Now lets confirm that there's absolutely no free space left to
409 * allocate.
410 */
411 if (cache->free_space_ctl->free_space != 0) {
412 test_msg("Cache free space is not 0\n");
413 return -EINVAL;
414 }
415
416 /* And any allocation request, no matter how small, should fail now. */
417 offset = btrfs_find_space_for_alloc(cache, 0, 4096, 0,
418 &max_extent_size);
419 if (offset != 0) {
420 test_msg("Space allocation did not fail, returned offset: %llu",
421 offset);
422 return -EINVAL;
423 }
424
425 /* And no extent nor bitmap entries in the cache anymore. */
426 return check_num_extents_and_bitmaps(cache, 0, 0);
427}
428
429/*
430 * Before we were able to steal free space from a bitmap entry to an extent
431 * entry, we could end up with 2 entries representing a contiguous free space.
432 * One would be an extent entry and the other a bitmap entry. Since in order
433 * to allocate space to a caller we use only 1 entry, we couldn't return that
434 * whole range to the caller if it was requested. This forced the caller to
435 * either assume ENOSPC or perform several smaller space allocations, which
436 * wasn't optimal as they could be spread all over the block group while under
437 * concurrency (extra overhead and fragmentation).
438 *
439 * This stealing approach is benefical, since we always prefer to allocate from
440 * extent entries, both for clustered and non-clustered allocation requests.
441 */
442static int
443test_steal_space_from_bitmap_to_extent(struct btrfs_block_group_cache *cache)
444{
445 int ret;
446 u64 offset;
447 u64 max_extent_size;
David Sterba20e55062015-11-19 11:42:28 +0100448 const struct btrfs_free_space_op test_free_space_ops = {
David Sterba28f07792015-11-19 11:42:24 +0100449 .recalc_thresholds = cache->free_space_ctl->op->recalc_thresholds,
450 .use_bitmap = test_use_bitmap,
451 };
David Sterba20e55062015-11-19 11:42:28 +0100452 const struct btrfs_free_space_op *orig_free_space_ops;
Filipe Manana20005522014-08-29 13:35:13 +0100453
454 test_msg("Running space stealing from bitmap to extent\n");
455
456 /*
457 * For this test, we want to ensure we end up with an extent entry
458 * immediately adjacent to a bitmap entry, where the bitmap starts
459 * at an offset where the extent entry ends. We keep adding and
460 * removing free space to reach into this state, but to get there
461 * we need to reach a point where marking new free space doesn't
462 * result in adding new extent entries or merging the new space
463 * with existing extent entries - the space ends up being marked
464 * in an existing bitmap that covers the new free space range.
465 *
466 * To get there, we need to reach the threshold defined set at
467 * cache->free_space_ctl->extents_thresh, which currently is
468 * 256 extents on a x86_64 system at least, and a few other
469 * conditions (check free_space_cache.c). Instead of making the
470 * test much longer and complicated, use a "use_bitmap" operation
471 * that forces use of bitmaps as soon as we have at least 1
472 * extent entry.
473 */
David Sterba28f07792015-11-19 11:42:24 +0100474 orig_free_space_ops = cache->free_space_ctl->op;
475 cache->free_space_ctl->op = &test_free_space_ops;
Filipe Manana20005522014-08-29 13:35:13 +0100476
477 /*
478 * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[
479 */
480 ret = test_add_free_space_entry(cache, 128 * 1024 * 1024 - 256 * 1024,
481 128 * 1024, 0);
482 if (ret) {
483 test_msg("Couldn't add extent entry %d\n", ret);
484 return ret;
485 }
486
487 /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */
488 ret = test_add_free_space_entry(cache, 128 * 1024 * 1024 + 512 * 1024,
489 128 * 1024 * 1024 - 512 * 1024, 1);
490 if (ret) {
491 test_msg("Couldn't add bitmap entry %d\n", ret);
492 return ret;
493 }
494
495 ret = check_num_extents_and_bitmaps(cache, 2, 1);
496 if (ret)
497 return ret;
498
499 /*
500 * Now make only the first 256Kb of the bitmap marked as free, so that
501 * we end up with only the following ranges marked as free space:
502 *
503 * [128Mb - 256Kb, 128Mb - 128Kb[
504 * [128Mb + 512Kb, 128Mb + 768Kb[
505 */
506 ret = btrfs_remove_free_space(cache,
507 128 * 1024 * 1024 + 768 * 1024,
508 128 * 1024 * 1024 - 768 * 1024);
509 if (ret) {
510 test_msg("Failed to free part of bitmap space %d\n", ret);
511 return ret;
512 }
513
514 /* Confirm that only those 2 ranges are marked as free. */
515 if (!test_check_exists(cache, 128 * 1024 * 1024 - 256 * 1024,
516 128 * 1024)) {
517 test_msg("Free space range missing\n");
518 return -ENOENT;
519 }
520 if (!test_check_exists(cache, 128 * 1024 * 1024 + 512 * 1024,
521 256 * 1024)) {
522 test_msg("Free space range missing\n");
523 return -ENOENT;
524 }
525
526 /*
527 * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked
528 * as free anymore.
529 */
530 if (test_check_exists(cache, 128 * 1024 * 1024 + 768 * 1024,
531 128 * 1024 * 1024 - 768 * 1024)) {
532 test_msg("Bitmap region not removed from space cache\n");
533 return -EINVAL;
534 }
535
536 /*
537 * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is
538 * covered by the bitmap, isn't marked as free.
539 */
540 if (test_check_exists(cache, 128 * 1024 * 1024 + 256 * 1024,
541 256 * 1024)) {
542 test_msg("Invalid bitmap region marked as free\n");
543 return -EINVAL;
544 }
545
546 /*
547 * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered
548 * by the bitmap too, isn't marked as free either.
549 */
550 if (test_check_exists(cache, 128 * 1024 * 1024,
551 256 * 1024)) {
552 test_msg("Invalid bitmap region marked as free\n");
553 return -EINVAL;
554 }
555
556 /*
557 * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But,
558 * lets make sure the free space cache marks it as free in the bitmap,
559 * and doesn't insert a new extent entry to represent this region.
560 */
561 ret = btrfs_add_free_space(cache, 128 * 1024 * 1024, 512 * 1024);
562 if (ret) {
563 test_msg("Error adding free space: %d\n", ret);
564 return ret;
565 }
566 /* Confirm the region is marked as free. */
567 if (!test_check_exists(cache, 128 * 1024 * 1024, 512 * 1024)) {
568 test_msg("Bitmap region not marked as free\n");
569 return -ENOENT;
570 }
571
572 /*
573 * Confirm that no new extent entries or bitmap entries were added to
574 * the cache after adding that free space region.
575 */
576 ret = check_num_extents_and_bitmaps(cache, 2, 1);
577 if (ret)
578 return ret;
579
580 /*
581 * Now lets add a small free space region to the right of the previous
582 * one, which is not contiguous with it and is part of the bitmap too.
583 * The goal is to test that the bitmap entry space stealing doesn't
584 * steal this space region.
585 */
586 ret = btrfs_add_free_space(cache, 128 * 1024 * 1024 + 16 * 1024 * 1024,
587 4096);
588 if (ret) {
589 test_msg("Error adding free space: %d\n", ret);
590 return ret;
591 }
592
593 /*
594 * Confirm that no new extent entries or bitmap entries were added to
595 * the cache after adding that free space region.
596 */
597 ret = check_num_extents_and_bitmaps(cache, 2, 1);
598 if (ret)
599 return ret;
600
601 /*
602 * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will
603 * expand the range covered by the existing extent entry that represents
604 * the free space [128Mb - 256Kb, 128Mb - 128Kb[.
605 */
606 ret = btrfs_add_free_space(cache, 128 * 1024 * 1024 - 128 * 1024,
607 128 * 1024);
608 if (ret) {
609 test_msg("Error adding free space: %d\n", ret);
610 return ret;
611 }
612 /* Confirm the region is marked as free. */
613 if (!test_check_exists(cache, 128 * 1024 * 1024 - 128 * 1024,
614 128 * 1024)) {
615 test_msg("Extent region not marked as free\n");
616 return -ENOENT;
617 }
618
619 /*
620 * Confirm that our extent entry didn't stole all free space from the
621 * bitmap, because of the small 4Kb free space region.
622 */
623 ret = check_num_extents_and_bitmaps(cache, 2, 1);
624 if (ret)
625 return ret;
626
627 /*
628 * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free
629 * space. Without stealing bitmap free space into extent entry space,
630 * we would have all this free space represented by 2 entries in the
631 * cache:
632 *
633 * extent entry covering range: [128Mb - 256Kb, 128Mb[
634 * bitmap entry covering range: [128Mb, 128Mb + 768Kb[
635 *
636 * Attempting to allocate the whole free space (1Mb) would fail, because
637 * we can't allocate from multiple entries.
638 * With the bitmap free space stealing, we get a single extent entry
639 * that represents the 1Mb free space, and therefore we're able to
640 * allocate the whole free space at once.
641 */
642 if (!test_check_exists(cache, 128 * 1024 * 1024 - 256 * 1024,
643 1 * 1024 * 1024)) {
644 test_msg("Expected region not marked as free\n");
645 return -ENOENT;
646 }
647
648 if (cache->free_space_ctl->free_space != (1 * 1024 * 1024 + 4096)) {
649 test_msg("Cache free space is not 1Mb + 4Kb\n");
650 return -EINVAL;
651 }
652
653 offset = btrfs_find_space_for_alloc(cache,
654 0, 1 * 1024 * 1024, 0,
655 &max_extent_size);
656 if (offset != (128 * 1024 * 1024 - 256 * 1024)) {
657 test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n",
658 offset);
659 return -EINVAL;
660 }
661
662 /* All that remains is a 4Kb free space region in a bitmap. Confirm. */
663 ret = check_num_extents_and_bitmaps(cache, 1, 1);
664 if (ret)
665 return ret;
666
667 if (cache->free_space_ctl->free_space != 4096) {
668 test_msg("Cache free space is not 4Kb\n");
669 return -EINVAL;
670 }
671
672 offset = btrfs_find_space_for_alloc(cache,
673 0, 4096, 0,
674 &max_extent_size);
675 if (offset != (128 * 1024 * 1024 + 16 * 1024 * 1024)) {
676 test_msg("Failed to allocate 4Kb from space cache, returned offset is: %llu\n",
677 offset);
678 return -EINVAL;
679 }
680
681 ret = check_cache_empty(cache);
682 if (ret)
683 return ret;
684
685 __btrfs_remove_free_space_cache(cache->free_space_ctl);
686
687 /*
688 * Now test a similar scenario, but where our extent entry is located
689 * to the right of the bitmap entry, so that we can check that stealing
690 * space from a bitmap to the front of an extent entry works.
691 */
692
693 /*
694 * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[
695 */
696 ret = test_add_free_space_entry(cache, 128 * 1024 * 1024 + 128 * 1024,
697 128 * 1024, 0);
698 if (ret) {
699 test_msg("Couldn't add extent entry %d\n", ret);
700 return ret;
701 }
702
703 /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */
704 ret = test_add_free_space_entry(cache, 0,
705 128 * 1024 * 1024 - 512 * 1024, 1);
706 if (ret) {
707 test_msg("Couldn't add bitmap entry %d\n", ret);
708 return ret;
709 }
710
711 ret = check_num_extents_and_bitmaps(cache, 2, 1);
712 if (ret)
713 return ret;
714
715 /*
716 * Now make only the last 256Kb of the bitmap marked as free, so that
717 * we end up with only the following ranges marked as free space:
718 *
719 * [128Mb + 128b, 128Mb + 256Kb[
720 * [128Mb - 768Kb, 128Mb - 512Kb[
721 */
722 ret = btrfs_remove_free_space(cache,
723 0,
724 128 * 1024 * 1024 - 768 * 1024);
725 if (ret) {
726 test_msg("Failed to free part of bitmap space %d\n", ret);
727 return ret;
728 }
729
730 /* Confirm that only those 2 ranges are marked as free. */
731 if (!test_check_exists(cache, 128 * 1024 * 1024 + 128 * 1024,
732 128 * 1024)) {
733 test_msg("Free space range missing\n");
734 return -ENOENT;
735 }
736 if (!test_check_exists(cache, 128 * 1024 * 1024 - 768 * 1024,
737 256 * 1024)) {
738 test_msg("Free space range missing\n");
739 return -ENOENT;
740 }
741
742 /*
743 * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked
744 * as free anymore.
745 */
746 if (test_check_exists(cache, 0,
747 128 * 1024 * 1024 - 768 * 1024)) {
748 test_msg("Bitmap region not removed from space cache\n");
749 return -EINVAL;
750 }
751
752 /*
753 * Confirm that the region [128Mb - 512Kb, 128Mb[, which is
754 * covered by the bitmap, isn't marked as free.
755 */
756 if (test_check_exists(cache, 128 * 1024 * 1024 - 512 * 1024,
757 512 * 1024)) {
758 test_msg("Invalid bitmap region marked as free\n");
759 return -EINVAL;
760 }
761
762 /*
763 * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But,
764 * lets make sure the free space cache marks it as free in the bitmap,
765 * and doesn't insert a new extent entry to represent this region.
766 */
767 ret = btrfs_add_free_space(cache, 128 * 1024 * 1024 - 512 * 1024,
768 512 * 1024);
769 if (ret) {
770 test_msg("Error adding free space: %d\n", ret);
771 return ret;
772 }
773 /* Confirm the region is marked as free. */
774 if (!test_check_exists(cache, 128 * 1024 * 1024 - 512 * 1024,
775 512 * 1024)) {
776 test_msg("Bitmap region not marked as free\n");
777 return -ENOENT;
778 }
779
780 /*
781 * Confirm that no new extent entries or bitmap entries were added to
782 * the cache after adding that free space region.
783 */
784 ret = check_num_extents_and_bitmaps(cache, 2, 1);
785 if (ret)
786 return ret;
787
788 /*
789 * Now lets add a small free space region to the left of the previous
790 * one, which is not contiguous with it and is part of the bitmap too.
791 * The goal is to test that the bitmap entry space stealing doesn't
792 * steal this space region.
793 */
794 ret = btrfs_add_free_space(cache, 32 * 1024 * 1024, 8192);
795 if (ret) {
796 test_msg("Error adding free space: %d\n", ret);
797 return ret;
798 }
799
800 /*
801 * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will
802 * expand the range covered by the existing extent entry that represents
803 * the free space [128Mb + 128Kb, 128Mb + 256Kb[.
804 */
805 ret = btrfs_add_free_space(cache, 128 * 1024 * 1024, 128 * 1024);
806 if (ret) {
807 test_msg("Error adding free space: %d\n", ret);
808 return ret;
809 }
810 /* Confirm the region is marked as free. */
811 if (!test_check_exists(cache, 128 * 1024 * 1024, 128 * 1024)) {
812 test_msg("Extent region not marked as free\n");
813 return -ENOENT;
814 }
815
816 /*
817 * Confirm that our extent entry didn't stole all free space from the
818 * bitmap, because of the small 8Kb free space region.
819 */
820 ret = check_num_extents_and_bitmaps(cache, 2, 1);
821 if (ret)
822 return ret;
823
824 /*
825 * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free
826 * space. Without stealing bitmap free space into extent entry space,
827 * we would have all this free space represented by 2 entries in the
828 * cache:
829 *
830 * extent entry covering range: [128Mb, 128Mb + 256Kb[
831 * bitmap entry covering range: [128Mb - 768Kb, 128Mb[
832 *
833 * Attempting to allocate the whole free space (1Mb) would fail, because
834 * we can't allocate from multiple entries.
835 * With the bitmap free space stealing, we get a single extent entry
836 * that represents the 1Mb free space, and therefore we're able to
837 * allocate the whole free space at once.
838 */
839 if (!test_check_exists(cache, 128 * 1024 * 1024 - 768 * 1024,
840 1 * 1024 * 1024)) {
841 test_msg("Expected region not marked as free\n");
842 return -ENOENT;
843 }
844
845 if (cache->free_space_ctl->free_space != (1 * 1024 * 1024 + 8192)) {
846 test_msg("Cache free space is not 1Mb + 8Kb\n");
847 return -EINVAL;
848 }
849
850 offset = btrfs_find_space_for_alloc(cache,
851 0, 1 * 1024 * 1024, 0,
852 &max_extent_size);
853 if (offset != (128 * 1024 * 1024 - 768 * 1024)) {
854 test_msg("Failed to allocate 1Mb from space cache, returned offset is: %llu\n",
855 offset);
856 return -EINVAL;
857 }
858
859 /* All that remains is a 8Kb free space region in a bitmap. Confirm. */
860 ret = check_num_extents_and_bitmaps(cache, 1, 1);
861 if (ret)
862 return ret;
863
864 if (cache->free_space_ctl->free_space != 8192) {
865 test_msg("Cache free space is not 8Kb\n");
866 return -EINVAL;
867 }
868
869 offset = btrfs_find_space_for_alloc(cache,
870 0, 8192, 0,
871 &max_extent_size);
872 if (offset != (32 * 1024 * 1024)) {
873 test_msg("Failed to allocate 8Kb from space cache, returned offset is: %llu\n",
874 offset);
875 return -EINVAL;
876 }
877
878 ret = check_cache_empty(cache);
879 if (ret)
880 return ret;
881
David Sterba28f07792015-11-19 11:42:24 +0100882 cache->free_space_ctl->op = orig_free_space_ops;
Filipe Manana20005522014-08-29 13:35:13 +0100883 __btrfs_remove_free_space_cache(cache->free_space_ctl);
884
885 return 0;
886}
887
Josef Bacikdc11dd52013-08-14 15:05:12 -0400888int btrfs_test_free_space_cache(void)
889{
890 struct btrfs_block_group_cache *cache;
Josef Bacikd0bd4562015-09-23 14:54:14 -0400891 struct btrfs_root *root = NULL;
892 int ret = -ENOMEM;
Josef Bacikdc11dd52013-08-14 15:05:12 -0400893
894 test_msg("Running btrfs free space cache tests\n");
895
896 cache = init_test_block_group();
897 if (!cache) {
898 test_msg("Couldn't run the tests\n");
899 return 0;
900 }
901
Josef Bacikd0bd4562015-09-23 14:54:14 -0400902 root = btrfs_alloc_dummy_root();
Dan Carpenter89b6c8d2015-11-10 12:10:03 +0300903 if (IS_ERR(root)) {
904 ret = PTR_ERR(root);
Josef Bacikd0bd4562015-09-23 14:54:14 -0400905 goto out;
Dan Carpenter89b6c8d2015-11-10 12:10:03 +0300906 }
Josef Bacikd0bd4562015-09-23 14:54:14 -0400907
908 root->fs_info = btrfs_alloc_dummy_fs_info();
909 if (!root->fs_info)
910 goto out;
911
912 root->fs_info->extent_root = root;
913 cache->fs_info = root->fs_info;
914
Josef Bacikdc11dd52013-08-14 15:05:12 -0400915 ret = test_extents(cache);
916 if (ret)
917 goto out;
918 ret = test_bitmaps(cache);
919 if (ret)
920 goto out;
921 ret = test_bitmaps_and_extents(cache);
922 if (ret)
923 goto out;
Filipe Manana20005522014-08-29 13:35:13 +0100924
925 ret = test_steal_space_from_bitmap_to_extent(cache);
Josef Bacikdc11dd52013-08-14 15:05:12 -0400926out:
927 __btrfs_remove_free_space_cache(cache->free_space_ctl);
928 kfree(cache->free_space_ctl);
929 kfree(cache);
Josef Bacikd0bd4562015-09-23 14:54:14 -0400930 btrfs_free_dummy_root(root);
Josef Bacikdc11dd52013-08-14 15:05:12 -0400931 test_msg("Free space cache tests finished\n");
932 return ret;
933}