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/pagemap.h>
0007 #include <linux/sched.h>
0008 #include <linux/slab.h>
0009 #include <linux/sizes.h>
0010 #include "btrfs-tests.h"
0011 #include "../ctree.h"
0012 #include "../extent_io.h"
0013 #include "../btrfs_inode.h"
0014 
0015 #define PROCESS_UNLOCK      (1 << 0)
0016 #define PROCESS_RELEASE     (1 << 1)
0017 #define PROCESS_TEST_LOCKED (1 << 2)
0018 
0019 static noinline int process_page_range(struct inode *inode, u64 start, u64 end,
0020                        unsigned long flags)
0021 {
0022     int ret;
0023     struct page *pages[16];
0024     unsigned long index = start >> PAGE_SHIFT;
0025     unsigned long end_index = end >> PAGE_SHIFT;
0026     unsigned long nr_pages = end_index - index + 1;
0027     int i;
0028     int count = 0;
0029     int loops = 0;
0030 
0031     while (nr_pages > 0) {
0032         ret = find_get_pages_contig(inode->i_mapping, index,
0033                      min_t(unsigned long, nr_pages,
0034                      ARRAY_SIZE(pages)), pages);
0035         for (i = 0; i < ret; i++) {
0036             if (flags & PROCESS_TEST_LOCKED &&
0037                 !PageLocked(pages[i]))
0038                 count++;
0039             if (flags & PROCESS_UNLOCK && PageLocked(pages[i]))
0040                 unlock_page(pages[i]);
0041             put_page(pages[i]);
0042             if (flags & PROCESS_RELEASE)
0043                 put_page(pages[i]);
0044         }
0045         nr_pages -= ret;
0046         index += ret;
0047         cond_resched();
0048         loops++;
0049         if (loops > 100000) {
0050             printk(KERN_ERR
0051         "stuck in a loop, start %llu, end %llu, nr_pages %lu, ret %d\n",
0052                 start, end, nr_pages, ret);
0053             break;
0054         }
0055     }
0056     return count;
0057 }
0058 
0059 #define STATE_FLAG_STR_LEN          256
0060 
0061 #define PRINT_ONE_FLAG(state, dest, cur, name)              \
0062 ({                                  \
0063     if (state->state & EXTENT_##name)               \
0064         cur += scnprintf(dest + cur, STATE_FLAG_STR_LEN - cur,  \
0065                  "%s" #name, cur == 0 ? "" : "|");  \
0066 })
0067 
0068 static void extent_flag_to_str(const struct extent_state *state, char *dest)
0069 {
0070     int cur = 0;
0071 
0072     dest[0] = 0;
0073     PRINT_ONE_FLAG(state, dest, cur, DIRTY);
0074     PRINT_ONE_FLAG(state, dest, cur, UPTODATE);
0075     PRINT_ONE_FLAG(state, dest, cur, LOCKED);
0076     PRINT_ONE_FLAG(state, dest, cur, NEW);
0077     PRINT_ONE_FLAG(state, dest, cur, DELALLOC);
0078     PRINT_ONE_FLAG(state, dest, cur, DEFRAG);
0079     PRINT_ONE_FLAG(state, dest, cur, BOUNDARY);
0080     PRINT_ONE_FLAG(state, dest, cur, NODATASUM);
0081     PRINT_ONE_FLAG(state, dest, cur, CLEAR_META_RESV);
0082     PRINT_ONE_FLAG(state, dest, cur, NEED_WAIT);
0083     PRINT_ONE_FLAG(state, dest, cur, DAMAGED);
0084     PRINT_ONE_FLAG(state, dest, cur, NORESERVE);
0085     PRINT_ONE_FLAG(state, dest, cur, QGROUP_RESERVED);
0086     PRINT_ONE_FLAG(state, dest, cur, CLEAR_DATA_RESV);
0087 }
0088 
0089 static void dump_extent_io_tree(const struct extent_io_tree *tree)
0090 {
0091     struct rb_node *node;
0092     char flags_str[STATE_FLAG_STR_LEN];
0093 
0094     node = rb_first(&tree->state);
0095     test_msg("io tree content:");
0096     while (node) {
0097         struct extent_state *state;
0098 
0099         state = rb_entry(node, struct extent_state, rb_node);
0100         extent_flag_to_str(state, flags_str);
0101         test_msg("  start=%llu len=%llu flags=%s", state->start,
0102              state->end + 1 - state->start, flags_str);
0103         node = rb_next(node);
0104     }
0105 }
0106 
0107 static int test_find_delalloc(u32 sectorsize)
0108 {
0109     struct inode *inode;
0110     struct extent_io_tree *tmp;
0111     struct page *page;
0112     struct page *locked_page = NULL;
0113     unsigned long index = 0;
0114     /* In this test we need at least 2 file extents at its maximum size */
0115     u64 max_bytes = BTRFS_MAX_EXTENT_SIZE;
0116     u64 total_dirty = 2 * max_bytes;
0117     u64 start, end, test_start;
0118     bool found;
0119     int ret = -EINVAL;
0120 
0121     test_msg("running find delalloc tests");
0122 
0123     inode = btrfs_new_test_inode();
0124     if (!inode) {
0125         test_std_err(TEST_ALLOC_INODE);
0126         return -ENOMEM;
0127     }
0128     tmp = &BTRFS_I(inode)->io_tree;
0129 
0130     /*
0131      * Passing NULL as we don't have fs_info but tracepoints are not used
0132      * at this point
0133      */
0134     extent_io_tree_init(NULL, tmp, IO_TREE_SELFTEST, NULL);
0135 
0136     /*
0137      * First go through and create and mark all of our pages dirty, we pin
0138      * everything to make sure our pages don't get evicted and screw up our
0139      * test.
0140      */
0141     for (index = 0; index < (total_dirty >> PAGE_SHIFT); index++) {
0142         page = find_or_create_page(inode->i_mapping, index, GFP_KERNEL);
0143         if (!page) {
0144             test_err("failed to allocate test page");
0145             ret = -ENOMEM;
0146             goto out;
0147         }
0148         SetPageDirty(page);
0149         if (index) {
0150             unlock_page(page);
0151         } else {
0152             get_page(page);
0153             locked_page = page;
0154         }
0155     }
0156 
0157     /* Test this scenario
0158      * |--- delalloc ---|
0159      * |---  search  ---|
0160      */
0161     set_extent_delalloc(tmp, 0, sectorsize - 1, 0, NULL);
0162     start = 0;
0163     end = start + PAGE_SIZE - 1;
0164     found = find_lock_delalloc_range(inode, locked_page, &start,
0165                      &end);
0166     if (!found) {
0167         test_err("should have found at least one delalloc");
0168         goto out_bits;
0169     }
0170     if (start != 0 || end != (sectorsize - 1)) {
0171         test_err("expected start 0 end %u, got start %llu end %llu",
0172             sectorsize - 1, start, end);
0173         goto out_bits;
0174     }
0175     unlock_extent(tmp, start, end);
0176     unlock_page(locked_page);
0177     put_page(locked_page);
0178 
0179     /*
0180      * Test this scenario
0181      *
0182      * |--- delalloc ---|
0183      *           |--- search ---|
0184      */
0185     test_start = SZ_64M;
0186     locked_page = find_lock_page(inode->i_mapping,
0187                      test_start >> PAGE_SHIFT);
0188     if (!locked_page) {
0189         test_err("couldn't find the locked page");
0190         goto out_bits;
0191     }
0192     set_extent_delalloc(tmp, sectorsize, max_bytes - 1, 0, NULL);
0193     start = test_start;
0194     end = start + PAGE_SIZE - 1;
0195     found = find_lock_delalloc_range(inode, locked_page, &start,
0196                      &end);
0197     if (!found) {
0198         test_err("couldn't find delalloc in our range");
0199         goto out_bits;
0200     }
0201     if (start != test_start || end != max_bytes - 1) {
0202         test_err("expected start %llu end %llu, got start %llu, end %llu",
0203                 test_start, max_bytes - 1, start, end);
0204         goto out_bits;
0205     }
0206     if (process_page_range(inode, start, end,
0207                    PROCESS_TEST_LOCKED | PROCESS_UNLOCK)) {
0208         test_err("there were unlocked pages in the range");
0209         goto out_bits;
0210     }
0211     unlock_extent(tmp, start, end);
0212     /* locked_page was unlocked above */
0213     put_page(locked_page);
0214 
0215     /*
0216      * Test this scenario
0217      * |--- delalloc ---|
0218      *                    |--- search ---|
0219      */
0220     test_start = max_bytes + sectorsize;
0221     locked_page = find_lock_page(inode->i_mapping, test_start >>
0222                      PAGE_SHIFT);
0223     if (!locked_page) {
0224         test_err("couldn't find the locked page");
0225         goto out_bits;
0226     }
0227     start = test_start;
0228     end = start + PAGE_SIZE - 1;
0229     found = find_lock_delalloc_range(inode, locked_page, &start,
0230                      &end);
0231     if (found) {
0232         test_err("found range when we shouldn't have");
0233         goto out_bits;
0234     }
0235     if (end != test_start + PAGE_SIZE - 1) {
0236         test_err("did not return the proper end offset");
0237         goto out_bits;
0238     }
0239 
0240     /*
0241      * Test this scenario
0242      * [------- delalloc -------|
0243      * [max_bytes]|-- search--|
0244      *
0245      * We are re-using our test_start from above since it works out well.
0246      */
0247     set_extent_delalloc(tmp, max_bytes, total_dirty - 1, 0, NULL);
0248     start = test_start;
0249     end = start + PAGE_SIZE - 1;
0250     found = find_lock_delalloc_range(inode, locked_page, &start,
0251                      &end);
0252     if (!found) {
0253         test_err("didn't find our range");
0254         goto out_bits;
0255     }
0256     if (start != test_start || end != total_dirty - 1) {
0257         test_err("expected start %llu end %llu, got start %llu end %llu",
0258              test_start, total_dirty - 1, start, end);
0259         goto out_bits;
0260     }
0261     if (process_page_range(inode, start, end,
0262                    PROCESS_TEST_LOCKED | PROCESS_UNLOCK)) {
0263         test_err("pages in range were not all locked");
0264         goto out_bits;
0265     }
0266     unlock_extent(tmp, start, end);
0267 
0268     /*
0269      * Now to test where we run into a page that is no longer dirty in the
0270      * range we want to find.
0271      */
0272     page = find_get_page(inode->i_mapping,
0273                  (max_bytes + SZ_1M) >> PAGE_SHIFT);
0274     if (!page) {
0275         test_err("couldn't find our page");
0276         goto out_bits;
0277     }
0278     ClearPageDirty(page);
0279     put_page(page);
0280 
0281     /* We unlocked it in the previous test */
0282     lock_page(locked_page);
0283     start = test_start;
0284     end = start + PAGE_SIZE - 1;
0285     /*
0286      * Currently if we fail to find dirty pages in the delalloc range we
0287      * will adjust max_bytes down to PAGE_SIZE and then re-search.  If
0288      * this changes at any point in the future we will need to fix this
0289      * tests expected behavior.
0290      */
0291     found = find_lock_delalloc_range(inode, locked_page, &start,
0292                      &end);
0293     if (!found) {
0294         test_err("didn't find our range");
0295         goto out_bits;
0296     }
0297     if (start != test_start && end != test_start + PAGE_SIZE - 1) {
0298         test_err("expected start %llu end %llu, got start %llu end %llu",
0299              test_start, test_start + PAGE_SIZE - 1, start, end);
0300         goto out_bits;
0301     }
0302     if (process_page_range(inode, start, end, PROCESS_TEST_LOCKED |
0303                    PROCESS_UNLOCK)) {
0304         test_err("pages in range were not all locked");
0305         goto out_bits;
0306     }
0307     ret = 0;
0308 out_bits:
0309     if (ret)
0310         dump_extent_io_tree(tmp);
0311     clear_extent_bits(tmp, 0, total_dirty - 1, (unsigned)-1);
0312 out:
0313     if (locked_page)
0314         put_page(locked_page);
0315     process_page_range(inode, 0, total_dirty - 1,
0316                PROCESS_UNLOCK | PROCESS_RELEASE);
0317     iput(inode);
0318     return ret;
0319 }
0320 
0321 static int check_eb_bitmap(unsigned long *bitmap, struct extent_buffer *eb,
0322                unsigned long len)
0323 {
0324     unsigned long i;
0325 
0326     for (i = 0; i < len * BITS_PER_BYTE; i++) {
0327         int bit, bit1;
0328 
0329         bit = !!test_bit(i, bitmap);
0330         bit1 = !!extent_buffer_test_bit(eb, 0, i);
0331         if (bit1 != bit) {
0332             test_err("bits do not match");
0333             return -EINVAL;
0334         }
0335 
0336         bit1 = !!extent_buffer_test_bit(eb, i / BITS_PER_BYTE,
0337                         i % BITS_PER_BYTE);
0338         if (bit1 != bit) {
0339             test_err("offset bits do not match");
0340             return -EINVAL;
0341         }
0342     }
0343     return 0;
0344 }
0345 
0346 static int __test_eb_bitmaps(unsigned long *bitmap, struct extent_buffer *eb,
0347                  unsigned long len)
0348 {
0349     unsigned long i, j;
0350     u32 x;
0351     int ret;
0352 
0353     memset(bitmap, 0, len);
0354     memzero_extent_buffer(eb, 0, len);
0355     if (memcmp_extent_buffer(eb, bitmap, 0, len) != 0) {
0356         test_err("bitmap was not zeroed");
0357         return -EINVAL;
0358     }
0359 
0360     bitmap_set(bitmap, 0, len * BITS_PER_BYTE);
0361     extent_buffer_bitmap_set(eb, 0, 0, len * BITS_PER_BYTE);
0362     ret = check_eb_bitmap(bitmap, eb, len);
0363     if (ret) {
0364         test_err("setting all bits failed");
0365         return ret;
0366     }
0367 
0368     bitmap_clear(bitmap, 0, len * BITS_PER_BYTE);
0369     extent_buffer_bitmap_clear(eb, 0, 0, len * BITS_PER_BYTE);
0370     ret = check_eb_bitmap(bitmap, eb, len);
0371     if (ret) {
0372         test_err("clearing all bits failed");
0373         return ret;
0374     }
0375 
0376     /* Straddling pages test */
0377     if (len > PAGE_SIZE) {
0378         bitmap_set(bitmap,
0379             (PAGE_SIZE - sizeof(long) / 2) * BITS_PER_BYTE,
0380             sizeof(long) * BITS_PER_BYTE);
0381         extent_buffer_bitmap_set(eb, PAGE_SIZE - sizeof(long) / 2, 0,
0382                     sizeof(long) * BITS_PER_BYTE);
0383         ret = check_eb_bitmap(bitmap, eb, len);
0384         if (ret) {
0385             test_err("setting straddling pages failed");
0386             return ret;
0387         }
0388 
0389         bitmap_set(bitmap, 0, len * BITS_PER_BYTE);
0390         bitmap_clear(bitmap,
0391             (PAGE_SIZE - sizeof(long) / 2) * BITS_PER_BYTE,
0392             sizeof(long) * BITS_PER_BYTE);
0393         extent_buffer_bitmap_set(eb, 0, 0, len * BITS_PER_BYTE);
0394         extent_buffer_bitmap_clear(eb, PAGE_SIZE - sizeof(long) / 2, 0,
0395                     sizeof(long) * BITS_PER_BYTE);
0396         ret = check_eb_bitmap(bitmap, eb, len);
0397         if (ret) {
0398             test_err("clearing straddling pages failed");
0399             return ret;
0400         }
0401     }
0402 
0403     /*
0404      * Generate a wonky pseudo-random bit pattern for the sake of not using
0405      * something repetitive that could miss some hypothetical off-by-n bug.
0406      */
0407     x = 0;
0408     bitmap_clear(bitmap, 0, len * BITS_PER_BYTE);
0409     extent_buffer_bitmap_clear(eb, 0, 0, len * BITS_PER_BYTE);
0410     for (i = 0; i < len * BITS_PER_BYTE / 32; i++) {
0411         x = (0x19660dULL * (u64)x + 0x3c6ef35fULL) & 0xffffffffU;
0412         for (j = 0; j < 32; j++) {
0413             if (x & (1U << j)) {
0414                 bitmap_set(bitmap, i * 32 + j, 1);
0415                 extent_buffer_bitmap_set(eb, 0, i * 32 + j, 1);
0416             }
0417         }
0418     }
0419 
0420     ret = check_eb_bitmap(bitmap, eb, len);
0421     if (ret) {
0422         test_err("random bit pattern failed");
0423         return ret;
0424     }
0425 
0426     return 0;
0427 }
0428 
0429 static int test_eb_bitmaps(u32 sectorsize, u32 nodesize)
0430 {
0431     struct btrfs_fs_info *fs_info;
0432     unsigned long *bitmap = NULL;
0433     struct extent_buffer *eb = NULL;
0434     int ret;
0435 
0436     test_msg("running extent buffer bitmap tests");
0437 
0438     fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
0439     if (!fs_info) {
0440         test_std_err(TEST_ALLOC_FS_INFO);
0441         return -ENOMEM;
0442     }
0443 
0444     bitmap = kmalloc(nodesize, GFP_KERNEL);
0445     if (!bitmap) {
0446         test_err("couldn't allocate test bitmap");
0447         ret = -ENOMEM;
0448         goto out;
0449     }
0450 
0451     eb = __alloc_dummy_extent_buffer(fs_info, 0, nodesize);
0452     if (!eb) {
0453         test_std_err(TEST_ALLOC_ROOT);
0454         ret = -ENOMEM;
0455         goto out;
0456     }
0457 
0458     ret = __test_eb_bitmaps(bitmap, eb, nodesize);
0459     if (ret)
0460         goto out;
0461 
0462     free_extent_buffer(eb);
0463 
0464     /*
0465      * Test again for case where the tree block is sectorsize aligned but
0466      * not nodesize aligned.
0467      */
0468     eb = __alloc_dummy_extent_buffer(fs_info, sectorsize, nodesize);
0469     if (!eb) {
0470         test_std_err(TEST_ALLOC_ROOT);
0471         ret = -ENOMEM;
0472         goto out;
0473     }
0474 
0475     ret = __test_eb_bitmaps(bitmap, eb, nodesize);
0476 out:
0477     free_extent_buffer(eb);
0478     kfree(bitmap);
0479     btrfs_free_dummy_fs_info(fs_info);
0480     return ret;
0481 }
0482 
0483 static int test_find_first_clear_extent_bit(void)
0484 {
0485     struct extent_io_tree tree;
0486     u64 start, end;
0487     int ret = -EINVAL;
0488 
0489     test_msg("running find_first_clear_extent_bit test");
0490 
0491     extent_io_tree_init(NULL, &tree, IO_TREE_SELFTEST, NULL);
0492 
0493     /* Test correct handling of empty tree */
0494     find_first_clear_extent_bit(&tree, 0, &start, &end, CHUNK_TRIMMED);
0495     if (start != 0 || end != -1) {
0496         test_err(
0497     "error getting a range from completely empty tree: start %llu end %llu",
0498              start, end);
0499         goto out;
0500     }
0501     /*
0502      * Set 1M-4M alloc/discard and 32M-64M thus leaving a hole between
0503      * 4M-32M
0504      */
0505     set_extent_bits(&tree, SZ_1M, SZ_4M - 1,
0506             CHUNK_TRIMMED | CHUNK_ALLOCATED);
0507 
0508     find_first_clear_extent_bit(&tree, SZ_512K, &start, &end,
0509                     CHUNK_TRIMMED | CHUNK_ALLOCATED);
0510 
0511     if (start != 0 || end != SZ_1M - 1) {
0512         test_err("error finding beginning range: start %llu end %llu",
0513              start, end);
0514         goto out;
0515     }
0516 
0517     /* Now add 32M-64M so that we have a hole between 4M-32M */
0518     set_extent_bits(&tree, SZ_32M, SZ_64M - 1,
0519             CHUNK_TRIMMED | CHUNK_ALLOCATED);
0520 
0521     /*
0522      * Request first hole starting at 12M, we should get 4M-32M
0523      */
0524     find_first_clear_extent_bit(&tree, 12 * SZ_1M, &start, &end,
0525                     CHUNK_TRIMMED | CHUNK_ALLOCATED);
0526 
0527     if (start != SZ_4M || end != SZ_32M - 1) {
0528         test_err("error finding trimmed range: start %llu end %llu",
0529              start, end);
0530         goto out;
0531     }
0532 
0533     /*
0534      * Search in the middle of allocated range, should get the next one
0535      * available, which happens to be unallocated -> 4M-32M
0536      */
0537     find_first_clear_extent_bit(&tree, SZ_2M, &start, &end,
0538                     CHUNK_TRIMMED | CHUNK_ALLOCATED);
0539 
0540     if (start != SZ_4M || end != SZ_32M - 1) {
0541         test_err("error finding next unalloc range: start %llu end %llu",
0542              start, end);
0543         goto out;
0544     }
0545 
0546     /*
0547      * Set 64M-72M with CHUNK_ALLOC flag, then search for CHUNK_TRIMMED flag
0548      * being unset in this range, we should get the entry in range 64M-72M
0549      */
0550     set_extent_bits(&tree, SZ_64M, SZ_64M + SZ_8M - 1, CHUNK_ALLOCATED);
0551     find_first_clear_extent_bit(&tree, SZ_64M + SZ_1M, &start, &end,
0552                     CHUNK_TRIMMED);
0553 
0554     if (start != SZ_64M || end != SZ_64M + SZ_8M - 1) {
0555         test_err("error finding exact range: start %llu end %llu",
0556              start, end);
0557         goto out;
0558     }
0559 
0560     find_first_clear_extent_bit(&tree, SZ_64M - SZ_8M, &start, &end,
0561                     CHUNK_TRIMMED);
0562 
0563     /*
0564      * Search in the middle of set range whose immediate neighbour doesn't
0565      * have the bits set so it must be returned
0566      */
0567     if (start != SZ_64M || end != SZ_64M + SZ_8M - 1) {
0568         test_err("error finding next alloc range: start %llu end %llu",
0569              start, end);
0570         goto out;
0571     }
0572 
0573     /*
0574      * Search beyond any known range, shall return after last known range
0575      * and end should be -1
0576      */
0577     find_first_clear_extent_bit(&tree, -1, &start, &end, CHUNK_TRIMMED);
0578     if (start != SZ_64M + SZ_8M || end != -1) {
0579         test_err(
0580         "error handling beyond end of range search: start %llu end %llu",
0581             start, end);
0582         goto out;
0583     }
0584 
0585     ret = 0;
0586 out:
0587     if (ret)
0588         dump_extent_io_tree(&tree);
0589     clear_extent_bits(&tree, 0, (u64)-1, CHUNK_TRIMMED | CHUNK_ALLOCATED);
0590 
0591     return ret;
0592 }
0593 
0594 int btrfs_test_extent_io(u32 sectorsize, u32 nodesize)
0595 {
0596     int ret;
0597 
0598     test_msg("running extent I/O tests");
0599 
0600     ret = test_find_delalloc(sectorsize);
0601     if (ret)
0602         goto out;
0603 
0604     ret = test_find_first_clear_extent_bit();
0605     if (ret)
0606         goto out;
0607 
0608     ret = test_eb_bitmaps(sectorsize, nodesize);
0609 out:
0610     return ret;
0611 }
[ 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!