~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/btrfs/tests/free-space-tests.c

Version: ~ [ linux-5.5-rc1 ] ~ [ linux-5.4.2 ] ~ [ linux-5.3.15 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.88 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.158 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.206 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.206 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.19.8 ] ~ [ linux-3.18.140 ] ~ [ linux-3.17.8 ] ~ [ linux-3.16.78 ] ~ [ linux-3.15.10 ] ~ [ linux-3.14.79 ] ~ [ linux-3.13.11 ] ~ [ linux-3.12.74 ] ~ [ linux-3.11.10 ] ~ [ linux-3.10.108 ] ~ [ linux-3.9.11 ] ~ [ linux-3.8.13 ] ~ [ linux-3.7.10 ] ~ [ linux-3.6.11 ] ~ [ linux-3.5.7 ] ~ [ linux-3.4.113 ] ~ [ linux-3.3.8 ] ~ [ linux-3.2.102 ] ~ [ linux-3.1.10 ] ~ [ linux-3.0.101 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.5 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp