Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (C) 2013 Fusion IO.  All rights reserved.
0004  */
0005 
0006 #include <linux/slab.h>
0007 #include "btrfs-tests.h"
0008 #include "../ctree.h"
0009 #include "../disk-io.h"
0010 #include "../free-space-cache.h"
0011 #include "../block-group.h"
0012 
0013 #define BITS_PER_BITMAP     (PAGE_SIZE * 8UL)
0014 
0015 /*
0016  * This test just does basic sanity checking, making sure we can add an extent
0017  * entry and remove space from either end and the middle, and make sure we can
0018  * remove space that covers adjacent extent entries.
0019  */
0020 static int test_extents(struct btrfs_block_group *cache)
0021 {
0022     int ret = 0;
0023 
0024     test_msg("running extent only tests");
0025 
0026     /* First just make sure we can remove an entire entry */
0027     ret = btrfs_add_free_space(cache, 0, SZ_4M);
0028     if (ret) {
0029         test_err("error adding initial extents %d", ret);
0030         return ret;
0031     }
0032 
0033     ret = btrfs_remove_free_space(cache, 0, SZ_4M);
0034     if (ret) {
0035         test_err("error removing extent %d", ret);
0036         return ret;
0037     }
0038 
0039     if (test_check_exists(cache, 0, SZ_4M)) {
0040         test_err("full remove left some lingering space");
0041         return -1;
0042     }
0043 
0044     /* Ok edge and middle cases now */
0045     ret = btrfs_add_free_space(cache, 0, SZ_4M);
0046     if (ret) {
0047         test_err("error adding half extent %d", ret);
0048         return ret;
0049     }
0050 
0051     ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_1M);
0052     if (ret) {
0053         test_err("error removing tail end %d", ret);
0054         return ret;
0055     }
0056 
0057     ret = btrfs_remove_free_space(cache, 0, SZ_1M);
0058     if (ret) {
0059         test_err("error removing front end %d", ret);
0060         return ret;
0061     }
0062 
0063     ret = btrfs_remove_free_space(cache, SZ_2M, 4096);
0064     if (ret) {
0065         test_err("error removing middle piece %d", ret);
0066         return ret;
0067     }
0068 
0069     if (test_check_exists(cache, 0, SZ_1M)) {
0070         test_err("still have space at the front");
0071         return -1;
0072     }
0073 
0074     if (test_check_exists(cache, SZ_2M, 4096)) {
0075         test_err("still have space in the middle");
0076         return -1;
0077     }
0078 
0079     if (test_check_exists(cache, 3 * SZ_1M, SZ_1M)) {
0080         test_err("still have space at the end");
0081         return -1;
0082     }
0083 
0084     /* Cleanup */
0085     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0086 
0087     return 0;
0088 }
0089 
0090 static int test_bitmaps(struct btrfs_block_group *cache, u32 sectorsize)
0091 {
0092     u64 next_bitmap_offset;
0093     int ret;
0094 
0095     test_msg("running bitmap only tests");
0096 
0097     ret = test_add_free_space_entry(cache, 0, SZ_4M, 1);
0098     if (ret) {
0099         test_err("couldn't create a bitmap entry %d", ret);
0100         return ret;
0101     }
0102 
0103     ret = btrfs_remove_free_space(cache, 0, SZ_4M);
0104     if (ret) {
0105         test_err("error removing bitmap full range %d", ret);
0106         return ret;
0107     }
0108 
0109     if (test_check_exists(cache, 0, SZ_4M)) {
0110         test_err("left some space in bitmap");
0111         return -1;
0112     }
0113 
0114     ret = test_add_free_space_entry(cache, 0, SZ_4M, 1);
0115     if (ret) {
0116         test_err("couldn't add to our bitmap entry %d", ret);
0117         return ret;
0118     }
0119 
0120     ret = btrfs_remove_free_space(cache, SZ_1M, SZ_2M);
0121     if (ret) {
0122         test_err("couldn't remove middle chunk %d", ret);
0123         return ret;
0124     }
0125 
0126     /*
0127      * The first bitmap we have starts at offset 0 so the next one is just
0128      * at the end of the first bitmap.
0129      */
0130     next_bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize);
0131 
0132     /* Test a bit straddling two bitmaps */
0133     ret = test_add_free_space_entry(cache, next_bitmap_offset - SZ_2M,
0134                     SZ_4M, 1);
0135     if (ret) {
0136         test_err("couldn't add space that straddles two bitmaps %d",
0137                 ret);
0138         return ret;
0139     }
0140 
0141     ret = btrfs_remove_free_space(cache, next_bitmap_offset - SZ_1M, SZ_2M);
0142     if (ret) {
0143         test_err("couldn't remove overlapping space %d", ret);
0144         return ret;
0145     }
0146 
0147     if (test_check_exists(cache, next_bitmap_offset - SZ_1M, SZ_2M)) {
0148         test_err("left some space when removing overlapping");
0149         return -1;
0150     }
0151 
0152     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0153 
0154     return 0;
0155 }
0156 
0157 /* This is the high grade jackassery */
0158 static int test_bitmaps_and_extents(struct btrfs_block_group *cache,
0159                     u32 sectorsize)
0160 {
0161     u64 bitmap_offset = (u64)(BITS_PER_BITMAP * sectorsize);
0162     int ret;
0163 
0164     test_msg("running bitmap and extent tests");
0165 
0166     /*
0167      * First let's do something simple, an extent at the same offset as the
0168      * bitmap, but the free space completely in the extent and then
0169      * completely in the bitmap.
0170      */
0171     ret = test_add_free_space_entry(cache, SZ_4M, SZ_1M, 1);
0172     if (ret) {
0173         test_err("couldn't create bitmap entry %d", ret);
0174         return ret;
0175     }
0176 
0177     ret = test_add_free_space_entry(cache, 0, SZ_1M, 0);
0178     if (ret) {
0179         test_err("couldn't add extent entry %d", ret);
0180         return ret;
0181     }
0182 
0183     ret = btrfs_remove_free_space(cache, 0, SZ_1M);
0184     if (ret) {
0185         test_err("couldn't remove extent entry %d", ret);
0186         return ret;
0187     }
0188 
0189     if (test_check_exists(cache, 0, SZ_1M)) {
0190         test_err("left remnants after our remove");
0191         return -1;
0192     }
0193 
0194     /* Now to add back the extent entry and remove from the bitmap */
0195     ret = test_add_free_space_entry(cache, 0, SZ_1M, 0);
0196     if (ret) {
0197         test_err("couldn't re-add extent entry %d", ret);
0198         return ret;
0199     }
0200 
0201     ret = btrfs_remove_free_space(cache, SZ_4M, SZ_1M);
0202     if (ret) {
0203         test_err("couldn't remove from bitmap %d", ret);
0204         return ret;
0205     }
0206 
0207     if (test_check_exists(cache, SZ_4M, SZ_1M)) {
0208         test_err("left remnants in the bitmap");
0209         return -1;
0210     }
0211 
0212     /*
0213      * Ok so a little more evil, extent entry and bitmap at the same offset,
0214      * removing an overlapping chunk.
0215      */
0216     ret = test_add_free_space_entry(cache, SZ_1M, SZ_4M, 1);
0217     if (ret) {
0218         test_err("couldn't add to a bitmap %d", ret);
0219         return ret;
0220     }
0221 
0222     ret = btrfs_remove_free_space(cache, SZ_512K, 3 * SZ_1M);
0223     if (ret) {
0224         test_err("couldn't remove overlapping space %d", ret);
0225         return ret;
0226     }
0227 
0228     if (test_check_exists(cache, SZ_512K, 3 * SZ_1M)) {
0229         test_err("left over pieces after removing overlapping");
0230         return -1;
0231     }
0232 
0233     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0234 
0235     /* Now with the extent entry offset into the bitmap */
0236     ret = test_add_free_space_entry(cache, SZ_4M, SZ_4M, 1);
0237     if (ret) {
0238         test_err("couldn't add space to the bitmap %d", ret);
0239         return ret;
0240     }
0241 
0242     ret = test_add_free_space_entry(cache, SZ_2M, SZ_2M, 0);
0243     if (ret) {
0244         test_err("couldn't add extent to the cache %d", ret);
0245         return ret;
0246     }
0247 
0248     ret = btrfs_remove_free_space(cache, 3 * SZ_1M, SZ_4M);
0249     if (ret) {
0250         test_err("problem removing overlapping space %d", ret);
0251         return ret;
0252     }
0253 
0254     if (test_check_exists(cache, 3 * SZ_1M, SZ_4M)) {
0255         test_err("left something behind when removing space");
0256         return -1;
0257     }
0258 
0259     /*
0260      * This has blown up in the past, the extent entry starts before the
0261      * bitmap entry, but we're trying to remove an offset that falls
0262      * completely within the bitmap range and is in both the extent entry
0263      * and the bitmap entry, looks like this
0264      *
0265      *   [ extent ]
0266      *      [ bitmap ]
0267      *        [ del ]
0268      */
0269     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0270     ret = test_add_free_space_entry(cache, bitmap_offset + SZ_4M, SZ_4M, 1);
0271     if (ret) {
0272         test_err("couldn't add bitmap %d", ret);
0273         return ret;
0274     }
0275 
0276     ret = test_add_free_space_entry(cache, bitmap_offset - SZ_1M,
0277                     5 * SZ_1M, 0);
0278     if (ret) {
0279         test_err("couldn't add extent entry %d", ret);
0280         return ret;
0281     }
0282 
0283     ret = btrfs_remove_free_space(cache, bitmap_offset + SZ_1M, 5 * SZ_1M);
0284     if (ret) {
0285         test_err("failed to free our space %d", ret);
0286         return ret;
0287     }
0288 
0289     if (test_check_exists(cache, bitmap_offset + SZ_1M, 5 * SZ_1M)) {
0290         test_err("left stuff over");
0291         return -1;
0292     }
0293 
0294     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0295 
0296     /*
0297      * This blew up before, we have part of the free space in a bitmap and
0298      * then the entirety of the rest of the space in an extent.  This used
0299      * to return -EAGAIN back from btrfs_remove_extent, make sure this
0300      * doesn't happen.
0301      */
0302     ret = test_add_free_space_entry(cache, SZ_1M, SZ_2M, 1);
0303     if (ret) {
0304         test_err("couldn't add bitmap entry %d", ret);
0305         return ret;
0306     }
0307 
0308     ret = test_add_free_space_entry(cache, 3 * SZ_1M, SZ_1M, 0);
0309     if (ret) {
0310         test_err("couldn't add extent entry %d", ret);
0311         return ret;
0312     }
0313 
0314     ret = btrfs_remove_free_space(cache, SZ_1M, 3 * SZ_1M);
0315     if (ret) {
0316         test_err("error removing bitmap and extent overlapping %d", ret);
0317         return ret;
0318     }
0319 
0320     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0321     return 0;
0322 }
0323 
0324 /* Used by test_steal_space_from_bitmap_to_extent(). */
0325 static bool test_use_bitmap(struct btrfs_free_space_ctl *ctl,
0326                 struct btrfs_free_space *info)
0327 {
0328     return ctl->free_extents > 0;
0329 }
0330 
0331 /* Used by test_steal_space_from_bitmap_to_extent(). */
0332 static int
0333 check_num_extents_and_bitmaps(const struct btrfs_block_group *cache,
0334                   const int num_extents,
0335                   const int num_bitmaps)
0336 {
0337     if (cache->free_space_ctl->free_extents != num_extents) {
0338         test_err(
0339         "incorrect # of extent entries in the cache: %d, expected %d",
0340              cache->free_space_ctl->free_extents, num_extents);
0341         return -EINVAL;
0342     }
0343     if (cache->free_space_ctl->total_bitmaps != num_bitmaps) {
0344         test_err(
0345         "incorrect # of extent entries in the cache: %d, expected %d",
0346              cache->free_space_ctl->total_bitmaps, num_bitmaps);
0347         return -EINVAL;
0348     }
0349     return 0;
0350 }
0351 
0352 /* Used by test_steal_space_from_bitmap_to_extent(). */
0353 static int check_cache_empty(struct btrfs_block_group *cache)
0354 {
0355     u64 offset;
0356     u64 max_extent_size;
0357 
0358     /*
0359      * Now lets confirm that there's absolutely no free space left to
0360      * allocate.
0361      */
0362     if (cache->free_space_ctl->free_space != 0) {
0363         test_err("cache free space is not 0");
0364         return -EINVAL;
0365     }
0366 
0367     /* And any allocation request, no matter how small, should fail now. */
0368     offset = btrfs_find_space_for_alloc(cache, 0, 4096, 0,
0369                         &max_extent_size);
0370     if (offset != 0) {
0371         test_err("space allocation did not fail, returned offset: %llu",
0372              offset);
0373         return -EINVAL;
0374     }
0375 
0376     /* And no extent nor bitmap entries in the cache anymore. */
0377     return check_num_extents_and_bitmaps(cache, 0, 0);
0378 }
0379 
0380 /*
0381  * Before we were able to steal free space from a bitmap entry to an extent
0382  * entry, we could end up with 2 entries representing a contiguous free space.
0383  * One would be an extent entry and the other a bitmap entry. Since in order
0384  * to allocate space to a caller we use only 1 entry, we couldn't return that
0385  * whole range to the caller if it was requested. This forced the caller to
0386  * either assume ENOSPC or perform several smaller space allocations, which
0387  * wasn't optimal as they could be spread all over the block group while under
0388  * concurrency (extra overhead and fragmentation).
0389  *
0390  * This stealing approach is beneficial, since we always prefer to allocate
0391  * from extent entries, both for clustered and non-clustered allocation
0392  * requests.
0393  */
0394 static int
0395 test_steal_space_from_bitmap_to_extent(struct btrfs_block_group *cache,
0396                        u32 sectorsize)
0397 {
0398     int ret;
0399     u64 offset;
0400     u64 max_extent_size;
0401     const struct btrfs_free_space_op test_free_space_ops = {
0402         .use_bitmap = test_use_bitmap,
0403     };
0404     const struct btrfs_free_space_op *orig_free_space_ops;
0405 
0406     test_msg("running space stealing from bitmap to extent tests");
0407 
0408     /*
0409      * For this test, we want to ensure we end up with an extent entry
0410      * immediately adjacent to a bitmap entry, where the bitmap starts
0411      * at an offset where the extent entry ends. We keep adding and
0412      * removing free space to reach into this state, but to get there
0413      * we need to reach a point where marking new free space doesn't
0414      * result in adding new extent entries or merging the new space
0415      * with existing extent entries - the space ends up being marked
0416      * in an existing bitmap that covers the new free space range.
0417      *
0418      * To get there, we need to reach the threshold defined set at
0419      * cache->free_space_ctl->extents_thresh, which currently is
0420      * 256 extents on a x86_64 system at least, and a few other
0421      * conditions (check free_space_cache.c). Instead of making the
0422      * test much longer and complicated, use a "use_bitmap" operation
0423      * that forces use of bitmaps as soon as we have at least 1
0424      * extent entry.
0425      */
0426     orig_free_space_ops = cache->free_space_ctl->op;
0427     cache->free_space_ctl->op = &test_free_space_ops;
0428 
0429     /*
0430      * Extent entry covering free space range [128Mb - 256Kb, 128Mb - 128Kb[
0431      */
0432     ret = test_add_free_space_entry(cache, SZ_128M - SZ_256K, SZ_128K, 0);
0433     if (ret) {
0434         test_err("couldn't add extent entry %d", ret);
0435         return ret;
0436     }
0437 
0438     /* Bitmap entry covering free space range [128Mb + 512Kb, 256Mb[ */
0439     ret = test_add_free_space_entry(cache, SZ_128M + SZ_512K,
0440                     SZ_128M - SZ_512K, 1);
0441     if (ret) {
0442         test_err("couldn't add bitmap entry %d", ret);
0443         return ret;
0444     }
0445 
0446     ret = check_num_extents_and_bitmaps(cache, 2, 1);
0447     if (ret)
0448         return ret;
0449 
0450     /*
0451      * Now make only the first 256Kb of the bitmap marked as free, so that
0452      * we end up with only the following ranges marked as free space:
0453      *
0454      * [128Mb - 256Kb, 128Mb - 128Kb[
0455      * [128Mb + 512Kb, 128Mb + 768Kb[
0456      */
0457     ret = btrfs_remove_free_space(cache,
0458                       SZ_128M + 768 * SZ_1K,
0459                       SZ_128M - 768 * SZ_1K);
0460     if (ret) {
0461         test_err("failed to free part of bitmap space %d", ret);
0462         return ret;
0463     }
0464 
0465     /* Confirm that only those 2 ranges are marked as free. */
0466     if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_128K)) {
0467         test_err("free space range missing");
0468         return -ENOENT;
0469     }
0470     if (!test_check_exists(cache, SZ_128M + SZ_512K, SZ_256K)) {
0471         test_err("free space range missing");
0472         return -ENOENT;
0473     }
0474 
0475     /*
0476      * Confirm that the bitmap range [128Mb + 768Kb, 256Mb[ isn't marked
0477      * as free anymore.
0478      */
0479     if (test_check_exists(cache, SZ_128M + 768 * SZ_1K,
0480                   SZ_128M - 768 * SZ_1K)) {
0481         test_err("bitmap region not removed from space cache");
0482         return -EINVAL;
0483     }
0484 
0485     /*
0486      * Confirm that the region [128Mb + 256Kb, 128Mb + 512Kb[, which is
0487      * covered by the bitmap, isn't marked as free.
0488      */
0489     if (test_check_exists(cache, SZ_128M + SZ_256K, SZ_256K)) {
0490         test_err("invalid bitmap region marked as free");
0491         return -EINVAL;
0492     }
0493 
0494     /*
0495      * Confirm that the region [128Mb, 128Mb + 256Kb[, which is covered
0496      * by the bitmap too, isn't marked as free either.
0497      */
0498     if (test_check_exists(cache, SZ_128M, SZ_256K)) {
0499         test_err("invalid bitmap region marked as free");
0500         return -EINVAL;
0501     }
0502 
0503     /*
0504      * Now lets mark the region [128Mb, 128Mb + 512Kb[ as free too. But,
0505      * lets make sure the free space cache marks it as free in the bitmap,
0506      * and doesn't insert a new extent entry to represent this region.
0507      */
0508     ret = btrfs_add_free_space(cache, SZ_128M, SZ_512K);
0509     if (ret) {
0510         test_err("error adding free space: %d", ret);
0511         return ret;
0512     }
0513     /* Confirm the region is marked as free. */
0514     if (!test_check_exists(cache, SZ_128M, SZ_512K)) {
0515         test_err("bitmap region not marked as free");
0516         return -ENOENT;
0517     }
0518 
0519     /*
0520      * Confirm that no new extent entries or bitmap entries were added to
0521      * the cache after adding that free space region.
0522      */
0523     ret = check_num_extents_and_bitmaps(cache, 2, 1);
0524     if (ret)
0525         return ret;
0526 
0527     /*
0528      * Now lets add a small free space region to the right of the previous
0529      * one, which is not contiguous with it and is part of the bitmap too.
0530      * The goal is to test that the bitmap entry space stealing doesn't
0531      * steal this space region.
0532      */
0533     ret = btrfs_add_free_space(cache, SZ_128M + SZ_16M, sectorsize);
0534     if (ret) {
0535         test_err("error adding free space: %d", ret);
0536         return ret;
0537     }
0538 
0539     /*
0540      * Confirm that no new extent entries or bitmap entries were added to
0541      * the cache after adding that free space region.
0542      */
0543     ret = check_num_extents_and_bitmaps(cache, 2, 1);
0544     if (ret)
0545         return ret;
0546 
0547     /*
0548      * Now mark the region [128Mb - 128Kb, 128Mb[ as free too. This will
0549      * expand the range covered by the existing extent entry that represents
0550      * the free space [128Mb - 256Kb, 128Mb - 128Kb[.
0551      */
0552     ret = btrfs_add_free_space(cache, SZ_128M - SZ_128K, SZ_128K);
0553     if (ret) {
0554         test_err("error adding free space: %d", ret);
0555         return ret;
0556     }
0557     /* Confirm the region is marked as free. */
0558     if (!test_check_exists(cache, SZ_128M - SZ_128K, SZ_128K)) {
0559         test_err("extent region not marked as free");
0560         return -ENOENT;
0561     }
0562 
0563     /*
0564      * Confirm that our extent entry didn't stole all free space from the
0565      * bitmap, because of the small 4Kb free space region.
0566      */
0567     ret = check_num_extents_and_bitmaps(cache, 2, 1);
0568     if (ret)
0569         return ret;
0570 
0571     /*
0572      * So now we have the range [128Mb - 256Kb, 128Mb + 768Kb[ as free
0573      * space. Without stealing bitmap free space into extent entry space,
0574      * we would have all this free space represented by 2 entries in the
0575      * cache:
0576      *
0577      * extent entry covering range: [128Mb - 256Kb, 128Mb[
0578      * bitmap entry covering range: [128Mb, 128Mb + 768Kb[
0579      *
0580      * Attempting to allocate the whole free space (1Mb) would fail, because
0581      * we can't allocate from multiple entries.
0582      * With the bitmap free space stealing, we get a single extent entry
0583      * that represents the 1Mb free space, and therefore we're able to
0584      * allocate the whole free space at once.
0585      */
0586     if (!test_check_exists(cache, SZ_128M - SZ_256K, SZ_1M)) {
0587         test_err("expected region not marked as free");
0588         return -ENOENT;
0589     }
0590 
0591     if (cache->free_space_ctl->free_space != (SZ_1M + sectorsize)) {
0592         test_err("cache free space is not 1Mb + %u", sectorsize);
0593         return -EINVAL;
0594     }
0595 
0596     offset = btrfs_find_space_for_alloc(cache,
0597                         0, SZ_1M, 0,
0598                         &max_extent_size);
0599     if (offset != (SZ_128M - SZ_256K)) {
0600         test_err(
0601     "failed to allocate 1Mb from space cache, returned offset is: %llu",
0602              offset);
0603         return -EINVAL;
0604     }
0605 
0606     /*
0607      * All that remains is a sectorsize free space region in a bitmap.
0608      * Confirm.
0609      */
0610     ret = check_num_extents_and_bitmaps(cache, 1, 1);
0611     if (ret)
0612         return ret;
0613 
0614     if (cache->free_space_ctl->free_space != sectorsize) {
0615         test_err("cache free space is not %u", sectorsize);
0616         return -EINVAL;
0617     }
0618 
0619     offset = btrfs_find_space_for_alloc(cache,
0620                         0, sectorsize, 0,
0621                         &max_extent_size);
0622     if (offset != (SZ_128M + SZ_16M)) {
0623         test_err("failed to allocate %u, returned offset : %llu",
0624              sectorsize, offset);
0625         return -EINVAL;
0626     }
0627 
0628     ret = check_cache_empty(cache);
0629     if (ret)
0630         return ret;
0631 
0632     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0633 
0634     /*
0635      * Now test a similar scenario, but where our extent entry is located
0636      * to the right of the bitmap entry, so that we can check that stealing
0637      * space from a bitmap to the front of an extent entry works.
0638      */
0639 
0640     /*
0641      * Extent entry covering free space range [128Mb + 128Kb, 128Mb + 256Kb[
0642      */
0643     ret = test_add_free_space_entry(cache, SZ_128M + SZ_128K, SZ_128K, 0);
0644     if (ret) {
0645         test_err("couldn't add extent entry %d", ret);
0646         return ret;
0647     }
0648 
0649     /* Bitmap entry covering free space range [0, 128Mb - 512Kb[ */
0650     ret = test_add_free_space_entry(cache, 0, SZ_128M - SZ_512K, 1);
0651     if (ret) {
0652         test_err("couldn't add bitmap entry %d", ret);
0653         return ret;
0654     }
0655 
0656     ret = check_num_extents_and_bitmaps(cache, 2, 1);
0657     if (ret)
0658         return ret;
0659 
0660     /*
0661      * Now make only the last 256Kb of the bitmap marked as free, so that
0662      * we end up with only the following ranges marked as free space:
0663      *
0664      * [128Mb + 128b, 128Mb + 256Kb[
0665      * [128Mb - 768Kb, 128Mb - 512Kb[
0666      */
0667     ret = btrfs_remove_free_space(cache, 0, SZ_128M - 768 * SZ_1K);
0668     if (ret) {
0669         test_err("failed to free part of bitmap space %d", ret);
0670         return ret;
0671     }
0672 
0673     /* Confirm that only those 2 ranges are marked as free. */
0674     if (!test_check_exists(cache, SZ_128M + SZ_128K, SZ_128K)) {
0675         test_err("free space range missing");
0676         return -ENOENT;
0677     }
0678     if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_256K)) {
0679         test_err("free space range missing");
0680         return -ENOENT;
0681     }
0682 
0683     /*
0684      * Confirm that the bitmap range [0, 128Mb - 768Kb[ isn't marked
0685      * as free anymore.
0686      */
0687     if (test_check_exists(cache, 0, SZ_128M - 768 * SZ_1K)) {
0688         test_err("bitmap region not removed from space cache");
0689         return -EINVAL;
0690     }
0691 
0692     /*
0693      * Confirm that the region [128Mb - 512Kb, 128Mb[, which is
0694      * covered by the bitmap, isn't marked as free.
0695      */
0696     if (test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
0697         test_err("invalid bitmap region marked as free");
0698         return -EINVAL;
0699     }
0700 
0701     /*
0702      * Now lets mark the region [128Mb - 512Kb, 128Mb[ as free too. But,
0703      * lets make sure the free space cache marks it as free in the bitmap,
0704      * and doesn't insert a new extent entry to represent this region.
0705      */
0706     ret = btrfs_add_free_space(cache, SZ_128M - SZ_512K, SZ_512K);
0707     if (ret) {
0708         test_err("error adding free space: %d", ret);
0709         return ret;
0710     }
0711     /* Confirm the region is marked as free. */
0712     if (!test_check_exists(cache, SZ_128M - SZ_512K, SZ_512K)) {
0713         test_err("bitmap region not marked as free");
0714         return -ENOENT;
0715     }
0716 
0717     /*
0718      * Confirm that no new extent entries or bitmap entries were added to
0719      * the cache after adding that free space region.
0720      */
0721     ret = check_num_extents_and_bitmaps(cache, 2, 1);
0722     if (ret)
0723         return ret;
0724 
0725     /*
0726      * Now lets add a small free space region to the left of the previous
0727      * one, which is not contiguous with it and is part of the bitmap too.
0728      * The goal is to test that the bitmap entry space stealing doesn't
0729      * steal this space region.
0730      */
0731     ret = btrfs_add_free_space(cache, SZ_32M, 2 * sectorsize);
0732     if (ret) {
0733         test_err("error adding free space: %d", ret);
0734         return ret;
0735     }
0736 
0737     /*
0738      * Now mark the region [128Mb, 128Mb + 128Kb[ as free too. This will
0739      * expand the range covered by the existing extent entry that represents
0740      * the free space [128Mb + 128Kb, 128Mb + 256Kb[.
0741      */
0742     ret = btrfs_add_free_space(cache, SZ_128M, SZ_128K);
0743     if (ret) {
0744         test_err("error adding free space: %d", ret);
0745         return ret;
0746     }
0747     /* Confirm the region is marked as free. */
0748     if (!test_check_exists(cache, SZ_128M, SZ_128K)) {
0749         test_err("extent region not marked as free");
0750         return -ENOENT;
0751     }
0752 
0753     /*
0754      * Confirm that our extent entry didn't stole all free space from the
0755      * bitmap, because of the small 2 * sectorsize free space region.
0756      */
0757     ret = check_num_extents_and_bitmaps(cache, 2, 1);
0758     if (ret)
0759         return ret;
0760 
0761     /*
0762      * So now we have the range [128Mb - 768Kb, 128Mb + 256Kb[ as free
0763      * space. Without stealing bitmap free space into extent entry space,
0764      * we would have all this free space represented by 2 entries in the
0765      * cache:
0766      *
0767      * extent entry covering range: [128Mb, 128Mb + 256Kb[
0768      * bitmap entry covering range: [128Mb - 768Kb, 128Mb[
0769      *
0770      * Attempting to allocate the whole free space (1Mb) would fail, because
0771      * we can't allocate from multiple entries.
0772      * With the bitmap free space stealing, we get a single extent entry
0773      * that represents the 1Mb free space, and therefore we're able to
0774      * allocate the whole free space at once.
0775      */
0776     if (!test_check_exists(cache, SZ_128M - 768 * SZ_1K, SZ_1M)) {
0777         test_err("expected region not marked as free");
0778         return -ENOENT;
0779     }
0780 
0781     if (cache->free_space_ctl->free_space != (SZ_1M + 2 * sectorsize)) {
0782         test_err("cache free space is not 1Mb + %u", 2 * sectorsize);
0783         return -EINVAL;
0784     }
0785 
0786     offset = btrfs_find_space_for_alloc(cache, 0, SZ_1M, 0,
0787                         &max_extent_size);
0788     if (offset != (SZ_128M - 768 * SZ_1K)) {
0789         test_err(
0790     "failed to allocate 1Mb from space cache, returned offset is: %llu",
0791              offset);
0792         return -EINVAL;
0793     }
0794 
0795     /*
0796      * All that remains is 2 * sectorsize free space region
0797      * in a bitmap. Confirm.
0798      */
0799     ret = check_num_extents_and_bitmaps(cache, 1, 1);
0800     if (ret)
0801         return ret;
0802 
0803     if (cache->free_space_ctl->free_space != 2 * sectorsize) {
0804         test_err("cache free space is not %u", 2 * sectorsize);
0805         return -EINVAL;
0806     }
0807 
0808     offset = btrfs_find_space_for_alloc(cache,
0809                         0, 2 * sectorsize, 0,
0810                         &max_extent_size);
0811     if (offset != SZ_32M) {
0812         test_err("failed to allocate %u, offset: %llu",
0813              2 * sectorsize, offset);
0814         return -EINVAL;
0815     }
0816 
0817     ret = check_cache_empty(cache);
0818     if (ret)
0819         return ret;
0820 
0821     cache->free_space_ctl->op = orig_free_space_ops;
0822     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0823 
0824     return 0;
0825 }
0826 
0827 static bool bytes_index_use_bitmap(struct btrfs_free_space_ctl *ctl,
0828                    struct btrfs_free_space *info)
0829 {
0830     return true;
0831 }
0832 
0833 static int test_bytes_index(struct btrfs_block_group *cache, u32 sectorsize)
0834 {
0835     const struct btrfs_free_space_op test_free_space_ops = {
0836         .use_bitmap = bytes_index_use_bitmap,
0837     };
0838     const struct btrfs_free_space_op *orig_free_space_ops;
0839     struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
0840     struct btrfs_free_space *entry;
0841     struct rb_node *node;
0842     u64 offset, max_extent_size, bytes;
0843     int ret, i;
0844 
0845     test_msg("running bytes index tests");
0846 
0847     /* First just validate that it does everything in order. */
0848     offset = 0;
0849     for (i = 0; i < 10; i++) {
0850         bytes = (i + 1) * SZ_1M;
0851         ret = test_add_free_space_entry(cache, offset, bytes, 0);
0852         if (ret) {
0853             test_err("couldn't add extent entry %d\n", ret);
0854             return ret;
0855         }
0856         offset += bytes + sectorsize;
0857     }
0858 
0859     for (node = rb_first_cached(&ctl->free_space_bytes), i = 9; node;
0860          node = rb_next(node), i--) {
0861         entry = rb_entry(node, struct btrfs_free_space, bytes_index);
0862         bytes = (i + 1) * SZ_1M;
0863         if (entry->bytes != bytes) {
0864             test_err("invalid bytes index order, found %llu expected %llu",
0865                  entry->bytes, bytes);
0866             return -EINVAL;
0867         }
0868     }
0869 
0870     /* Now validate bitmaps do the correct thing. */
0871     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0872     for (i = 0; i < 2; i++) {
0873         offset = i * BITS_PER_BITMAP * sectorsize;
0874         bytes = (i + 1) * SZ_1M;
0875         ret = test_add_free_space_entry(cache, offset, bytes, 1);
0876         if (ret) {
0877             test_err("couldn't add bitmap entry");
0878             return ret;
0879         }
0880     }
0881 
0882     for (node = rb_first_cached(&ctl->free_space_bytes), i = 1; node;
0883          node = rb_next(node), i--) {
0884         entry = rb_entry(node, struct btrfs_free_space, bytes_index);
0885         bytes = (i + 1) * SZ_1M;
0886         if (entry->bytes != bytes) {
0887             test_err("invalid bytes index order, found %llu expected %llu",
0888                  entry->bytes, bytes);
0889             return -EINVAL;
0890         }
0891     }
0892 
0893     /* Now validate bitmaps with different ->max_extent_size. */
0894     __btrfs_remove_free_space_cache(cache->free_space_ctl);
0895     orig_free_space_ops = cache->free_space_ctl->op;
0896     cache->free_space_ctl->op = &test_free_space_ops;
0897 
0898     ret = test_add_free_space_entry(cache, 0, sectorsize, 1);
0899     if (ret) {
0900         test_err("couldn't add bitmap entry");
0901         return ret;
0902     }
0903 
0904     offset = BITS_PER_BITMAP * sectorsize;
0905     ret = test_add_free_space_entry(cache, offset, sectorsize, 1);
0906     if (ret) {
0907         test_err("couldn't add bitmap_entry");
0908         return ret;
0909     }
0910 
0911     /*
0912      * Now set a bunch of sectorsize extents in the first entry so it's
0913      * ->bytes is large.
0914      */
0915     for (i = 2; i < 20; i += 2) {
0916         offset = sectorsize * i;
0917         ret = btrfs_add_free_space(cache, offset, sectorsize);
0918         if (ret) {
0919             test_err("error populating sparse bitmap %d", ret);
0920             return ret;
0921         }
0922     }
0923 
0924     /*
0925      * Now set a contiguous extent in the second bitmap so its
0926      * ->max_extent_size is larger than the first bitmaps.
0927      */
0928     offset = (BITS_PER_BITMAP * sectorsize) + sectorsize;
0929     ret = btrfs_add_free_space(cache, offset, sectorsize);
0930     if (ret) {
0931         test_err("error adding contiguous extent %d", ret);
0932         return ret;
0933     }
0934 
0935     /*
0936      * Since we don't set ->max_extent_size unless we search everything
0937      * should be indexed on bytes.
0938      */
0939     entry = rb_entry(rb_first_cached(&ctl->free_space_bytes),
0940              struct btrfs_free_space, bytes_index);
0941     if (entry->bytes != (10 * sectorsize)) {
0942         test_err("error, wrong entry in the first slot in bytes_index");
0943         return -EINVAL;
0944     }
0945 
0946     max_extent_size = 0;
0947     offset = btrfs_find_space_for_alloc(cache, cache->start, sectorsize * 3,
0948                         0, &max_extent_size);
0949     if (offset != 0) {
0950         test_err("found space to alloc even though we don't have enough space");
0951         return -EINVAL;
0952     }
0953 
0954     if (max_extent_size != (2 * sectorsize)) {
0955         test_err("got the wrong max_extent size %llu expected %llu",
0956              max_extent_size, (unsigned long long)(2 * sectorsize));
0957         return -EINVAL;
0958     }
0959 
0960     /*
0961      * The search should have re-arranged the bytes index to use the
0962      * ->max_extent_size, validate it's now what we expect it to be.
0963      */
0964     entry = rb_entry(rb_first_cached(&ctl->free_space_bytes),
0965              struct btrfs_free_space, bytes_index);
0966     if (entry->bytes != (2 * sectorsize)) {
0967         test_err("error, the bytes index wasn't recalculated properly");
0968         return -EINVAL;
0969     }
0970 
0971     /* Add another sectorsize to re-arrange the tree back to ->bytes. */
0972     offset = (BITS_PER_BITMAP * sectorsize) - sectorsize;
0973     ret = btrfs_add_free_space(cache, offset, sectorsize);
0974     if (ret) {
0975         test_err("error adding extent to the sparse entry %d", ret);
0976         return ret;
0977     }
0978 
0979     entry = rb_entry(rb_first_cached(&ctl->free_space_bytes),
0980              struct btrfs_free_space, bytes_index);
0981     if (entry->bytes != (11 * sectorsize)) {
0982         test_err("error, wrong entry in the first slot in bytes_index");
0983         return -EINVAL;
0984     }
0985 
0986     /*
0987      * Now make sure we find our correct entry after searching that will
0988      * result in a re-arranging of the tree.
0989      */
0990     max_extent_size = 0;
0991     offset = btrfs_find_space_for_alloc(cache, cache->start, sectorsize * 2,
0992                         0, &max_extent_size);
0993     if (offset != (BITS_PER_BITMAP * sectorsize)) {
0994         test_err("error, found %llu instead of %llu for our alloc",
0995              offset,
0996              (unsigned long long)(BITS_PER_BITMAP * sectorsize));
0997         return -EINVAL;
0998     }
0999 
1000     cache->free_space_ctl->op = orig_free_space_ops;
1001     __btrfs_remove_free_space_cache(cache->free_space_ctl);
1002     return 0;
1003 }
1004 
1005 int btrfs_test_free_space_cache(u32 sectorsize, u32 nodesize)
1006 {
1007     struct btrfs_fs_info *fs_info;
1008     struct btrfs_block_group *cache;
1009     struct btrfs_root *root = NULL;
1010     int ret = -ENOMEM;
1011 
1012     test_msg("running btrfs free space cache tests");
1013     fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
1014     if (!fs_info) {
1015         test_std_err(TEST_ALLOC_FS_INFO);
1016         return -ENOMEM;
1017     }
1018 
1019     /*
1020      * For ppc64 (with 64k page size), bytes per bitmap might be
1021      * larger than 1G.  To make bitmap test available in ppc64,
1022      * alloc dummy block group whose size cross bitmaps.
1023      */
1024     cache = btrfs_alloc_dummy_block_group(fs_info,
1025                       BITS_PER_BITMAP * sectorsize + PAGE_SIZE);
1026     if (!cache) {
1027         test_std_err(TEST_ALLOC_BLOCK_GROUP);
1028         btrfs_free_dummy_fs_info(fs_info);
1029         return 0;
1030     }
1031 
1032     root = btrfs_alloc_dummy_root(fs_info);
1033     if (IS_ERR(root)) {
1034         test_std_err(TEST_ALLOC_ROOT);
1035         ret = PTR_ERR(root);
1036         goto out;
1037     }
1038 
1039     root->root_key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
1040     root->root_key.type = BTRFS_ROOT_ITEM_KEY;
1041     root->root_key.offset = 0;
1042     btrfs_global_root_insert(root);
1043 
1044     ret = test_extents(cache);
1045     if (ret)
1046         goto out;
1047     ret = test_bitmaps(cache, sectorsize);
1048     if (ret)
1049         goto out;
1050     ret = test_bitmaps_and_extents(cache, sectorsize);
1051     if (ret)
1052         goto out;
1053 
1054     ret = test_steal_space_from_bitmap_to_extent(cache, sectorsize);
1055     if (ret)
1056         goto out;
1057     ret = test_bytes_index(cache, sectorsize);
1058 out:
1059     btrfs_free_dummy_block_group(cache);
1060     btrfs_free_dummy_root(root);
1061     btrfs_free_dummy_fs_info(fs_info);
1062     return ret;
1063 }
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!