Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Copyright (C) 2017 Oracle.  All rights reserved.
0004  */
0005 
0006 #include <linux/types.h>
0007 #include "btrfs-tests.h"
0008 #include "../ctree.h"
0009 #include "../volumes.h"
0010 #include "../disk-io.h"
0011 #include "../block-group.h"
0012 
0013 static void free_extent_map_tree(struct extent_map_tree *em_tree)
0014 {
0015     struct extent_map *em;
0016     struct rb_node *node;
0017 
0018     write_lock(&em_tree->lock);
0019     while (!RB_EMPTY_ROOT(&em_tree->map.rb_root)) {
0020         node = rb_first_cached(&em_tree->map);
0021         em = rb_entry(node, struct extent_map, rb_node);
0022         remove_extent_mapping(em_tree, em);
0023 
0024 #ifdef CONFIG_BTRFS_DEBUG
0025         if (refcount_read(&em->refs) != 1) {
0026             test_err(
0027 "em leak: em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx) refs %d",
0028                  em->start, em->len, em->block_start,
0029                  em->block_len, refcount_read(&em->refs));
0030 
0031             refcount_set(&em->refs, 1);
0032         }
0033 #endif
0034         free_extent_map(em);
0035     }
0036     write_unlock(&em_tree->lock);
0037 }
0038 
0039 /*
0040  * Test scenario:
0041  *
0042  * Suppose that no extent map has been loaded into memory yet, there is a file
0043  * extent [0, 16K), followed by another file extent [16K, 20K), two dio reads
0044  * are entering btrfs_get_extent() concurrently, t1 is reading [8K, 16K), t2 is
0045  * reading [0, 8K)
0046  *
0047  *     t1                            t2
0048  *  btrfs_get_extent()              btrfs_get_extent()
0049  *    -> lookup_extent_mapping()      ->lookup_extent_mapping()
0050  *    -> add_extent_mapping(0, 16K)
0051  *    -> return em
0052  *                                    ->add_extent_mapping(0, 16K)
0053  *                                    -> #handle -EEXIST
0054  */
0055 static int test_case_1(struct btrfs_fs_info *fs_info,
0056         struct extent_map_tree *em_tree)
0057 {
0058     struct extent_map *em;
0059     u64 start = 0;
0060     u64 len = SZ_8K;
0061     int ret;
0062 
0063     em = alloc_extent_map();
0064     if (!em) {
0065         test_std_err(TEST_ALLOC_EXTENT_MAP);
0066         return -ENOMEM;
0067     }
0068 
0069     /* Add [0, 16K) */
0070     em->start = 0;
0071     em->len = SZ_16K;
0072     em->block_start = 0;
0073     em->block_len = SZ_16K;
0074     write_lock(&em_tree->lock);
0075     ret = add_extent_mapping(em_tree, em, 0);
0076     write_unlock(&em_tree->lock);
0077     if (ret < 0) {
0078         test_err("cannot add extent range [0, 16K)");
0079         goto out;
0080     }
0081     free_extent_map(em);
0082 
0083     /* Add [16K, 20K) following [0, 16K)  */
0084     em = alloc_extent_map();
0085     if (!em) {
0086         test_std_err(TEST_ALLOC_EXTENT_MAP);
0087         ret = -ENOMEM;
0088         goto out;
0089     }
0090 
0091     em->start = SZ_16K;
0092     em->len = SZ_4K;
0093     em->block_start = SZ_32K; /* avoid merging */
0094     em->block_len = SZ_4K;
0095     write_lock(&em_tree->lock);
0096     ret = add_extent_mapping(em_tree, em, 0);
0097     write_unlock(&em_tree->lock);
0098     if (ret < 0) {
0099         test_err("cannot add extent range [16K, 20K)");
0100         goto out;
0101     }
0102     free_extent_map(em);
0103 
0104     em = alloc_extent_map();
0105     if (!em) {
0106         test_std_err(TEST_ALLOC_EXTENT_MAP);
0107         ret = -ENOMEM;
0108         goto out;
0109     }
0110 
0111     /* Add [0, 8K), should return [0, 16K) instead. */
0112     em->start = start;
0113     em->len = len;
0114     em->block_start = start;
0115     em->block_len = len;
0116     write_lock(&em_tree->lock);
0117     ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, em->start, em->len);
0118     write_unlock(&em_tree->lock);
0119     if (ret) {
0120         test_err("case1 [%llu %llu]: ret %d", start, start + len, ret);
0121         goto out;
0122     }
0123     if (em &&
0124         (em->start != 0 || extent_map_end(em) != SZ_16K ||
0125          em->block_start != 0 || em->block_len != SZ_16K)) {
0126         test_err(
0127 "case1 [%llu %llu]: ret %d return a wrong em (start %llu len %llu block_start %llu block_len %llu",
0128              start, start + len, ret, em->start, em->len,
0129              em->block_start, em->block_len);
0130         ret = -EINVAL;
0131     }
0132     free_extent_map(em);
0133 out:
0134     free_extent_map_tree(em_tree);
0135 
0136     return ret;
0137 }
0138 
0139 /*
0140  * Test scenario:
0141  *
0142  * Reading the inline ending up with EEXIST, ie. read an inline
0143  * extent and discard page cache and read it again.
0144  */
0145 static int test_case_2(struct btrfs_fs_info *fs_info,
0146         struct extent_map_tree *em_tree)
0147 {
0148     struct extent_map *em;
0149     int ret;
0150 
0151     em = alloc_extent_map();
0152     if (!em) {
0153         test_std_err(TEST_ALLOC_EXTENT_MAP);
0154         return -ENOMEM;
0155     }
0156 
0157     /* Add [0, 1K) */
0158     em->start = 0;
0159     em->len = SZ_1K;
0160     em->block_start = EXTENT_MAP_INLINE;
0161     em->block_len = (u64)-1;
0162     write_lock(&em_tree->lock);
0163     ret = add_extent_mapping(em_tree, em, 0);
0164     write_unlock(&em_tree->lock);
0165     if (ret < 0) {
0166         test_err("cannot add extent range [0, 1K)");
0167         goto out;
0168     }
0169     free_extent_map(em);
0170 
0171     /* Add [4K, 8K) following [0, 1K)  */
0172     em = alloc_extent_map();
0173     if (!em) {
0174         test_std_err(TEST_ALLOC_EXTENT_MAP);
0175         ret = -ENOMEM;
0176         goto out;
0177     }
0178 
0179     em->start = SZ_4K;
0180     em->len = SZ_4K;
0181     em->block_start = SZ_4K;
0182     em->block_len = SZ_4K;
0183     write_lock(&em_tree->lock);
0184     ret = add_extent_mapping(em_tree, em, 0);
0185     write_unlock(&em_tree->lock);
0186     if (ret < 0) {
0187         test_err("cannot add extent range [4K, 8K)");
0188         goto out;
0189     }
0190     free_extent_map(em);
0191 
0192     em = alloc_extent_map();
0193     if (!em) {
0194         test_std_err(TEST_ALLOC_EXTENT_MAP);
0195         ret = -ENOMEM;
0196         goto out;
0197     }
0198 
0199     /* Add [0, 1K) */
0200     em->start = 0;
0201     em->len = SZ_1K;
0202     em->block_start = EXTENT_MAP_INLINE;
0203     em->block_len = (u64)-1;
0204     write_lock(&em_tree->lock);
0205     ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, em->start, em->len);
0206     write_unlock(&em_tree->lock);
0207     if (ret) {
0208         test_err("case2 [0 1K]: ret %d", ret);
0209         goto out;
0210     }
0211     if (em &&
0212         (em->start != 0 || extent_map_end(em) != SZ_1K ||
0213          em->block_start != EXTENT_MAP_INLINE || em->block_len != (u64)-1)) {
0214         test_err(
0215 "case2 [0 1K]: ret %d return a wrong em (start %llu len %llu block_start %llu block_len %llu",
0216              ret, em->start, em->len, em->block_start,
0217              em->block_len);
0218         ret = -EINVAL;
0219     }
0220     free_extent_map(em);
0221 out:
0222     free_extent_map_tree(em_tree);
0223 
0224     return ret;
0225 }
0226 
0227 static int __test_case_3(struct btrfs_fs_info *fs_info,
0228         struct extent_map_tree *em_tree, u64 start)
0229 {
0230     struct extent_map *em;
0231     u64 len = SZ_4K;
0232     int ret;
0233 
0234     em = alloc_extent_map();
0235     if (!em) {
0236         test_std_err(TEST_ALLOC_EXTENT_MAP);
0237         return -ENOMEM;
0238     }
0239 
0240     /* Add [4K, 8K) */
0241     em->start = SZ_4K;
0242     em->len = SZ_4K;
0243     em->block_start = SZ_4K;
0244     em->block_len = SZ_4K;
0245     write_lock(&em_tree->lock);
0246     ret = add_extent_mapping(em_tree, em, 0);
0247     write_unlock(&em_tree->lock);
0248     if (ret < 0) {
0249         test_err("cannot add extent range [4K, 8K)");
0250         goto out;
0251     }
0252     free_extent_map(em);
0253 
0254     em = alloc_extent_map();
0255     if (!em) {
0256         test_std_err(TEST_ALLOC_EXTENT_MAP);
0257         ret = -ENOMEM;
0258         goto out;
0259     }
0260 
0261     /* Add [0, 16K) */
0262     em->start = 0;
0263     em->len = SZ_16K;
0264     em->block_start = 0;
0265     em->block_len = SZ_16K;
0266     write_lock(&em_tree->lock);
0267     ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, start, len);
0268     write_unlock(&em_tree->lock);
0269     if (ret) {
0270         test_err("case3 [0x%llx 0x%llx): ret %d",
0271              start, start + len, ret);
0272         goto out;
0273     }
0274     /*
0275      * Since bytes within em are contiguous, em->block_start is identical to
0276      * em->start.
0277      */
0278     if (em &&
0279         (start < em->start || start + len > extent_map_end(em) ||
0280          em->start != em->block_start || em->len != em->block_len)) {
0281         test_err(
0282 "case3 [0x%llx 0x%llx): ret %d em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx)",
0283              start, start + len, ret, em->start, em->len,
0284              em->block_start, em->block_len);
0285         ret = -EINVAL;
0286     }
0287     free_extent_map(em);
0288 out:
0289     free_extent_map_tree(em_tree);
0290 
0291     return ret;
0292 }
0293 
0294 /*
0295  * Test scenario:
0296  *
0297  * Suppose that no extent map has been loaded into memory yet.
0298  * There is a file extent [0, 16K), two jobs are running concurrently
0299  * against it, t1 is buffered writing to [4K, 8K) and t2 is doing dio
0300  * read from [0, 4K) or [8K, 12K) or [12K, 16K).
0301  *
0302  * t1 goes ahead of t2 and adds em [4K, 8K) into tree.
0303  *
0304  *         t1                       t2
0305  *  cow_file_range()         btrfs_get_extent()
0306  *                            -> lookup_extent_mapping()
0307  *   -> add_extent_mapping()
0308  *                            -> add_extent_mapping()
0309  */
0310 static int test_case_3(struct btrfs_fs_info *fs_info,
0311         struct extent_map_tree *em_tree)
0312 {
0313     int ret;
0314 
0315     ret = __test_case_3(fs_info, em_tree, 0);
0316     if (ret)
0317         return ret;
0318     ret = __test_case_3(fs_info, em_tree, SZ_8K);
0319     if (ret)
0320         return ret;
0321     ret = __test_case_3(fs_info, em_tree, (12 * SZ_1K));
0322 
0323     return ret;
0324 }
0325 
0326 static int __test_case_4(struct btrfs_fs_info *fs_info,
0327         struct extent_map_tree *em_tree, u64 start)
0328 {
0329     struct extent_map *em;
0330     u64 len = SZ_4K;
0331     int ret;
0332 
0333     em = alloc_extent_map();
0334     if (!em) {
0335         test_std_err(TEST_ALLOC_EXTENT_MAP);
0336         return -ENOMEM;
0337     }
0338 
0339     /* Add [0K, 8K) */
0340     em->start = 0;
0341     em->len = SZ_8K;
0342     em->block_start = 0;
0343     em->block_len = SZ_8K;
0344     write_lock(&em_tree->lock);
0345     ret = add_extent_mapping(em_tree, em, 0);
0346     write_unlock(&em_tree->lock);
0347     if (ret < 0) {
0348         test_err("cannot add extent range [0, 8K)");
0349         goto out;
0350     }
0351     free_extent_map(em);
0352 
0353     em = alloc_extent_map();
0354     if (!em) {
0355         test_std_err(TEST_ALLOC_EXTENT_MAP);
0356         ret = -ENOMEM;
0357         goto out;
0358     }
0359 
0360     /* Add [8K, 32K) */
0361     em->start = SZ_8K;
0362     em->len = 24 * SZ_1K;
0363     em->block_start = SZ_16K; /* avoid merging */
0364     em->block_len = 24 * SZ_1K;
0365     write_lock(&em_tree->lock);
0366     ret = add_extent_mapping(em_tree, em, 0);
0367     write_unlock(&em_tree->lock);
0368     if (ret < 0) {
0369         test_err("cannot add extent range [8K, 32K)");
0370         goto out;
0371     }
0372     free_extent_map(em);
0373 
0374     em = alloc_extent_map();
0375     if (!em) {
0376         test_std_err(TEST_ALLOC_EXTENT_MAP);
0377         ret = -ENOMEM;
0378         goto out;
0379     }
0380     /* Add [0K, 32K) */
0381     em->start = 0;
0382     em->len = SZ_32K;
0383     em->block_start = 0;
0384     em->block_len = SZ_32K;
0385     write_lock(&em_tree->lock);
0386     ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, start, len);
0387     write_unlock(&em_tree->lock);
0388     if (ret) {
0389         test_err("case4 [0x%llx 0x%llx): ret %d",
0390              start, len, ret);
0391         goto out;
0392     }
0393     if (em && (start < em->start || start + len > extent_map_end(em))) {
0394         test_err(
0395 "case4 [0x%llx 0x%llx): ret %d, added wrong em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx)",
0396              start, len, ret, em->start, em->len, em->block_start,
0397              em->block_len);
0398         ret = -EINVAL;
0399     }
0400     free_extent_map(em);
0401 out:
0402     free_extent_map_tree(em_tree);
0403 
0404     return ret;
0405 }
0406 
0407 /*
0408  * Test scenario:
0409  *
0410  * Suppose that no extent map has been loaded into memory yet.
0411  * There is a file extent [0, 32K), two jobs are running concurrently
0412  * against it, t1 is doing dio write to [8K, 32K) and t2 is doing dio
0413  * read from [0, 4K) or [4K, 8K).
0414  *
0415  * t1 goes ahead of t2 and splits em [0, 32K) to em [0K, 8K) and [8K 32K).
0416  *
0417  *         t1                                t2
0418  *  btrfs_get_blocks_direct()          btrfs_get_blocks_direct()
0419  *   -> btrfs_get_extent()              -> btrfs_get_extent()
0420  *       -> lookup_extent_mapping()
0421  *       -> add_extent_mapping()            -> lookup_extent_mapping()
0422  *          # load [0, 32K)
0423  *   -> btrfs_new_extent_direct()
0424  *       -> btrfs_drop_extent_cache()
0425  *          # split [0, 32K)
0426  *       -> add_extent_mapping()
0427  *          # add [8K, 32K)
0428  *                                          -> add_extent_mapping()
0429  *                                             # handle -EEXIST when adding
0430  *                                             # [0, 32K)
0431  */
0432 static int test_case_4(struct btrfs_fs_info *fs_info,
0433         struct extent_map_tree *em_tree)
0434 {
0435     int ret;
0436 
0437     ret = __test_case_4(fs_info, em_tree, 0);
0438     if (ret)
0439         return ret;
0440     ret = __test_case_4(fs_info, em_tree, SZ_4K);
0441 
0442     return ret;
0443 }
0444 
0445 struct rmap_test_vector {
0446     u64 raid_type;
0447     u64 physical_start;
0448     u64 data_stripe_size;
0449     u64 num_data_stripes;
0450     u64 num_stripes;
0451     /* Assume we won't have more than 5 physical stripes */
0452     u64 data_stripe_phys_start[5];
0453     bool expected_mapped_addr;
0454     /* Physical to logical addresses */
0455     u64 mapped_logical[5];
0456 };
0457 
0458 static int test_rmap_block(struct btrfs_fs_info *fs_info,
0459                struct rmap_test_vector *test)
0460 {
0461     struct extent_map *em;
0462     struct map_lookup *map = NULL;
0463     u64 *logical = NULL;
0464     int i, out_ndaddrs, out_stripe_len;
0465     int ret;
0466 
0467     em = alloc_extent_map();
0468     if (!em) {
0469         test_std_err(TEST_ALLOC_EXTENT_MAP);
0470         return -ENOMEM;
0471     }
0472 
0473     map = kmalloc(map_lookup_size(test->num_stripes), GFP_KERNEL);
0474     if (!map) {
0475         kfree(em);
0476         test_std_err(TEST_ALLOC_EXTENT_MAP);
0477         return -ENOMEM;
0478     }
0479 
0480     set_bit(EXTENT_FLAG_FS_MAPPING, &em->flags);
0481     /* Start at 4GiB logical address */
0482     em->start = SZ_4G;
0483     em->len = test->data_stripe_size * test->num_data_stripes;
0484     em->block_len = em->len;
0485     em->orig_block_len = test->data_stripe_size;
0486     em->map_lookup = map;
0487 
0488     map->num_stripes = test->num_stripes;
0489     map->stripe_len = BTRFS_STRIPE_LEN;
0490     map->type = test->raid_type;
0491 
0492     for (i = 0; i < map->num_stripes; i++) {
0493         struct btrfs_device *dev = btrfs_alloc_dummy_device(fs_info);
0494 
0495         if (IS_ERR(dev)) {
0496             test_err("cannot allocate device");
0497             ret = PTR_ERR(dev);
0498             goto out;
0499         }
0500         map->stripes[i].dev = dev;
0501         map->stripes[i].physical = test->data_stripe_phys_start[i];
0502     }
0503 
0504     write_lock(&fs_info->mapping_tree.lock);
0505     ret = add_extent_mapping(&fs_info->mapping_tree, em, 0);
0506     write_unlock(&fs_info->mapping_tree.lock);
0507     if (ret) {
0508         test_err("error adding block group mapping to mapping tree");
0509         goto out_free;
0510     }
0511 
0512     ret = btrfs_rmap_block(fs_info, em->start, NULL, btrfs_sb_offset(1),
0513                    &logical, &out_ndaddrs, &out_stripe_len);
0514     if (ret || (out_ndaddrs == 0 && test->expected_mapped_addr)) {
0515         test_err("didn't rmap anything but expected %d",
0516              test->expected_mapped_addr);
0517         goto out;
0518     }
0519 
0520     if (out_stripe_len != BTRFS_STRIPE_LEN) {
0521         test_err("calculated stripe length doesn't match");
0522         goto out;
0523     }
0524 
0525     if (out_ndaddrs != test->expected_mapped_addr) {
0526         for (i = 0; i < out_ndaddrs; i++)
0527             test_msg("mapped %llu", logical[i]);
0528         test_err("unexpected number of mapped addresses: %d", out_ndaddrs);
0529         goto out;
0530     }
0531 
0532     for (i = 0; i < out_ndaddrs; i++) {
0533         if (logical[i] != test->mapped_logical[i]) {
0534             test_err("unexpected logical address mapped");
0535             goto out;
0536         }
0537     }
0538 
0539     ret = 0;
0540 out:
0541     write_lock(&fs_info->mapping_tree.lock);
0542     remove_extent_mapping(&fs_info->mapping_tree, em);
0543     write_unlock(&fs_info->mapping_tree.lock);
0544     /* For us */
0545     free_extent_map(em);
0546 out_free:
0547     /* For the tree */
0548     free_extent_map(em);
0549     kfree(logical);
0550     return ret;
0551 }
0552 
0553 int btrfs_test_extent_map(void)
0554 {
0555     struct btrfs_fs_info *fs_info = NULL;
0556     struct extent_map_tree *em_tree;
0557     int ret = 0, i;
0558     struct rmap_test_vector rmap_tests[] = {
0559         {
0560             /*
0561              * Test a chunk with 2 data stripes one of which
0562              * intersects the physical address of the super block
0563              * is correctly recognised.
0564              */
0565             .raid_type = BTRFS_BLOCK_GROUP_RAID1,
0566             .physical_start = SZ_64M - SZ_4M,
0567             .data_stripe_size = SZ_256M,
0568             .num_data_stripes = 2,
0569             .num_stripes = 2,
0570             .data_stripe_phys_start =
0571                 {SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M},
0572             .expected_mapped_addr = true,
0573             .mapped_logical= {SZ_4G + SZ_4M}
0574         },
0575         {
0576             /*
0577              * Test that out-of-range physical addresses are
0578              * ignored
0579              */
0580 
0581              /* SINGLE chunk type */
0582             .raid_type = 0,
0583             .physical_start = SZ_4G,
0584             .data_stripe_size = SZ_256M,
0585             .num_data_stripes = 1,
0586             .num_stripes = 1,
0587             .data_stripe_phys_start = {SZ_256M},
0588             .expected_mapped_addr = false,
0589             .mapped_logical = {0}
0590         }
0591     };
0592 
0593     test_msg("running extent_map tests");
0594 
0595     /*
0596      * Note: the fs_info is not set up completely, we only need
0597      * fs_info::fsid for the tracepoint.
0598      */
0599     fs_info = btrfs_alloc_dummy_fs_info(PAGE_SIZE, PAGE_SIZE);
0600     if (!fs_info) {
0601         test_std_err(TEST_ALLOC_FS_INFO);
0602         return -ENOMEM;
0603     }
0604 
0605     em_tree = kzalloc(sizeof(*em_tree), GFP_KERNEL);
0606     if (!em_tree) {
0607         ret = -ENOMEM;
0608         goto out;
0609     }
0610 
0611     extent_map_tree_init(em_tree);
0612 
0613     ret = test_case_1(fs_info, em_tree);
0614     if (ret)
0615         goto out;
0616     ret = test_case_2(fs_info, em_tree);
0617     if (ret)
0618         goto out;
0619     ret = test_case_3(fs_info, em_tree);
0620     if (ret)
0621         goto out;
0622     ret = test_case_4(fs_info, em_tree);
0623 
0624     test_msg("running rmap tests");
0625     for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) {
0626         ret = test_rmap_block(fs_info, &rmap_tests[i]);
0627         if (ret)
0628             goto out;
0629     }
0630 
0631 out:
0632     kfree(em_tree);
0633     btrfs_free_dummy_fs_info(fs_info);
0634 
0635     return ret;
0636 }
[ 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!