fs/btrfs/tests/extent-io-tests.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2013 Fusion IO.  All rights reserved.
   4  */
   5
   6 #include <linux/pagemap.h>
   7 #include <linux/pagevec.h>
   8 #include <linux/sched.h>
   9 #include <linux/slab.h>
  10 #include <linux/sizes.h>
  11 #include "btrfs-tests.h"
  12 #include "../ctree.h"
  13 #include "../extent_io.h"
  14 #include "../btrfs_inode.h"
  15
  16 #define PROCESS_UNLOCK          (1 << 0)
  17 #define PROCESS_RELEASE         (1 << 1)
  18 #define PROCESS_TEST_LOCKED     (1 << 2)
  19
  20 static noinline int process_page_range(struct inode *inode, u64 start, u64 end,
  21                                        unsigned long flags)
  22 {
  23         int ret;
  24         struct folio_batch fbatch;
  25         unsigned long index = start >> PAGE_SHIFT;
  26         unsigned long end_index = end >> PAGE_SHIFT;
  27         int i;
  28         int count = 0;
  29         int loops = 0;
  30
  31         folio_batch_init(&fbatch);
  32
  33         while (index <= end_index) {
  34                 ret = filemap_get_folios_contig(inode->i_mapping, &index,
  35                                 end_index, &fbatch);
  36                 for (i = 0; i < ret; i++) {
  37                         struct folio *folio = fbatch.folios[i];
  38
  39                         if (flags & PROCESS_TEST_LOCKED &&
  40                             !folio_test_locked(folio))
  41                                 count++;
  42                         if (flags & PROCESS_UNLOCK && folio_test_locked(folio))
  43                                 folio_unlock(folio);
  44                         if (flags & PROCESS_RELEASE)
  45                                 folio_put(folio);
  46                 }
  47                 folio_batch_release(&fbatch);
  48                 cond_resched();
  49                 loops++;
  50                 if (loops > 100000) {
  51                         printk(KERN_ERR
  52                 "stuck in a loop, start %llu, end %llu, ret %d\n",
  53                                 start, end, ret);
  54                         break;
  55                 }
  56         }
  57
  58         return count;
  59 }
  60
  61 #define STATE_FLAG_STR_LEN                      256
  62
  63 #define PRINT_ONE_FLAG(state, dest, cur, name)                          \
  64 ({                                                                      \
  65         if (state->state & EXTENT_##name)                               \
  66                 cur += scnprintf(dest + cur, STATE_FLAG_STR_LEN - cur,  \
  67                                  "%s" #name, cur == 0 ? "" : "|");      \
  68 })
  69
  70 static void extent_flag_to_str(const struct extent_state *state, char *dest)
  71 {
  72         int cur = 0;
  73
  74         dest[0] = 0;
  75         PRINT_ONE_FLAG(state, dest, cur, DIRTY);
  76         PRINT_ONE_FLAG(state, dest, cur, UPTODATE);
  77         PRINT_ONE_FLAG(state, dest, cur, LOCKED);
  78         PRINT_ONE_FLAG(state, dest, cur, NEW);
  79         PRINT_ONE_FLAG(state, dest, cur, DELALLOC);
  80         PRINT_ONE_FLAG(state, dest, cur, DEFRAG);
  81         PRINT_ONE_FLAG(state, dest, cur, BOUNDARY);
  82         PRINT_ONE_FLAG(state, dest, cur, NODATASUM);
  83         PRINT_ONE_FLAG(state, dest, cur, CLEAR_META_RESV);
  84         PRINT_ONE_FLAG(state, dest, cur, NEED_WAIT);
  85         PRINT_ONE_FLAG(state, dest, cur, NORESERVE);
  86         PRINT_ONE_FLAG(state, dest, cur, QGROUP_RESERVED);
  87         PRINT_ONE_FLAG(state, dest, cur, CLEAR_DATA_RESV);
  88 }
  89
  90 static void dump_extent_io_tree(const struct extent_io_tree *tree)
  91 {
  92         struct rb_node *node;
  93         char flags_str[STATE_FLAG_STR_LEN];
  94
  95         node = rb_first(&tree->state);
  96         test_msg("io tree content:");
  97         while (node) {
  98                 struct extent_state *state;
  99
 100                 state = rb_entry(node, struct extent_state, rb_node);
 101                 extent_flag_to_str(state, flags_str);
 102                 test_msg("  start=%llu len=%llu flags=%s", state->start,
 103                          state->end + 1 - state->start, flags_str);
 104                 node = rb_next(node);
 105         }
 106 }
 107
 108 static int test_find_delalloc(u32 sectorsize)
 109 {
 110         struct inode *inode;
 111         struct extent_io_tree *tmp;
 112         struct page *page;
 113         struct page *locked_page = NULL;
 114         unsigned long index = 0;
 115         /* In this test we need at least 2 file extents at its maximum size */
 116         u64 max_bytes = BTRFS_MAX_EXTENT_SIZE;
 117         u64 total_dirty = 2 * max_bytes;
 118         u64 start, end, test_start;
 119         bool found;
 120         int ret = -EINVAL;
 121
 122         test_msg("running find delalloc tests");
 123
 124         inode = btrfs_new_test_inode();
 125         if (!inode) {
 126                 test_std_err(TEST_ALLOC_INODE);
 127                 return -ENOMEM;
 128         }
 129         tmp = &BTRFS_I(inode)->io_tree;
 130
 131         /*
 132          * Passing NULL as we don't have fs_info but tracepoints are not used
 133          * at this point
 134          */
 135         extent_io_tree_init(NULL, tmp, IO_TREE_SELFTEST, NULL);
 136
 137         /*
 138          * First go through and create and mark all of our pages dirty, we pin
 139          * everything to make sure our pages don't get evicted and screw up our
 140          * test.
 141          */
 142         for (index = 0; index < (total_dirty >> PAGE_SHIFT); index++) {
 143                 page = find_or_create_page(inode->i_mapping, index, GFP_KERNEL);
 144                 if (!page) {
 145                         test_err("failed to allocate test page");
 146                         ret = -ENOMEM;
 147                         goto out;
 148                 }
 149                 SetPageDirty(page);
 150                 if (index) {
 151                         unlock_page(page);
 152                 } else {
 153                         get_page(page);
 154                         locked_page = page;
 155                 }
 156         }
 157
 158         /* Test this scenario
 159          * |--- delalloc ---|
 160          * |---  search  ---|
 161          */
 162         set_extent_delalloc(tmp, 0, sectorsize - 1, 0, NULL);
 163         start = 0;
 164         end = start + PAGE_SIZE - 1;
 165         found = find_lock_delalloc_range(inode, locked_page, &start,
 166                                          &end);
 167         if (!found) {
 168                 test_err("should have found at least one delalloc");
 169                 goto out_bits;
 170         }
 171         if (start != 0 || end != (sectorsize - 1)) {
 172                 test_err("expected start 0 end %u, got start %llu end %llu",
 173                         sectorsize - 1, start, end);
 174                 goto out_bits;
 175         }
 176         unlock_extent(tmp, start, end, NULL);
 177         unlock_page(locked_page);
 178         put_page(locked_page);
 179
 180         /*
 181          * Test this scenario
 182          *
 183          * |--- delalloc ---|
 184          *           |--- search ---|
 185          */
 186         test_start = SZ_64M;
 187         locked_page = find_lock_page(inode->i_mapping,
 188                                      test_start >> PAGE_SHIFT);
 189         if (!locked_page) {
 190                 test_err("couldn't find the locked page");
 191                 goto out_bits;
 192         }
 193         set_extent_delalloc(tmp, sectorsize, max_bytes - 1, 0, NULL);
 194         start = test_start;
 195         end = start + PAGE_SIZE - 1;
 196         found = find_lock_delalloc_range(inode, locked_page, &start,
 197                                          &end);
 198         if (!found) {
 199                 test_err("couldn't find delalloc in our range");
 200                 goto out_bits;
 201         }
 202         if (start != test_start || end != max_bytes - 1) {
 203                 test_err("expected start %llu end %llu, got start %llu, end %llu",
 204                                 test_start, max_bytes - 1, start, end);
 205                 goto out_bits;
 206         }
 207         if (process_page_range(inode, start, end,
 208                                PROCESS_TEST_LOCKED | PROCESS_UNLOCK)) {
 209                 test_err("there were unlocked pages in the range");
 210                 goto out_bits;
 211         }
 212         unlock_extent(tmp, start, end, NULL);
 213         /* locked_page was unlocked above */
 214         put_page(locked_page);
 215
 216         /*
 217          * Test this scenario
 218          * |--- delalloc ---|
 219          *                    |--- search ---|
 220          */
 221         test_start = max_bytes + sectorsize;
 222         locked_page = find_lock_page(inode->i_mapping, test_start >>
 223                                      PAGE_SHIFT);
 224         if (!locked_page) {
 225                 test_err("couldn't find the locked page");
 226                 goto out_bits;
 227         }
 228         start = test_start;
 229         end = start + PAGE_SIZE - 1;
 230         found = find_lock_delalloc_range(inode, locked_page, &start,
 231                                          &end);
 232         if (found) {
 233                 test_err("found range when we shouldn't have");
 234                 goto out_bits;
 235         }
 236         if (end != test_start + PAGE_SIZE - 1) {
 237                 test_err("did not return the proper end offset");
 238                 goto out_bits;
 239         }
 240
 241         /*
 242          * Test this scenario
 243          * [------- delalloc -------|
 244          * [max_bytes]|-- search--|
 245          *
 246          * We are re-using our test_start from above since it works out well.
 247          */
 248         set_extent_delalloc(tmp, max_bytes, total_dirty - 1, 0, NULL);
 249         start = test_start;
 250         end = start + PAGE_SIZE - 1;
 251         found = find_lock_delalloc_range(inode, locked_page, &start,
 252                                          &end);
 253         if (!found) {
 254                 test_err("didn't find our range");
 255                 goto out_bits;
 256         }
 257         if (start != test_start || end != total_dirty - 1) {
 258                 test_err("expected start %llu end %llu, got start %llu end %llu",
 259                          test_start, total_dirty - 1, start, end);
 260                 goto out_bits;
 261         }
 262         if (process_page_range(inode, start, end,
 263                                PROCESS_TEST_LOCKED | PROCESS_UNLOCK)) {
 264                 test_err("pages in range were not all locked");
 265                 goto out_bits;
 266         }
 267         unlock_extent(tmp, start, end, NULL);
 268
 269         /*
 270          * Now to test where we run into a page that is no longer dirty in the
 271          * range we want to find.
 272          */
 273         page = find_get_page(inode->i_mapping,
 274                              (max_bytes + SZ_1M) >> PAGE_SHIFT);
 275         if (!page) {
 276                 test_err("couldn't find our page");
 277                 goto out_bits;
 278         }
 279         ClearPageDirty(page);
 280         put_page(page);
 281
 282         /* We unlocked it in the previous test */
 283         lock_page(locked_page);
 284         start = test_start;
 285         end = start + PAGE_SIZE - 1;
 286         /*
 287          * Currently if we fail to find dirty pages in the delalloc range we
 288          * will adjust max_bytes down to PAGE_SIZE and then re-search.  If
 289          * this changes at any point in the future we will need to fix this
 290          * tests expected behavior.
 291          */
 292         found = find_lock_delalloc_range(inode, locked_page, &start,
 293                                          &end);
 294         if (!found) {
 295                 test_err("didn't find our range");
 296                 goto out_bits;
 297         }
 298         if (start != test_start && end != test_start + PAGE_SIZE - 1) {
 299                 test_err("expected start %llu end %llu, got start %llu end %llu",
 300                          test_start, test_start + PAGE_SIZE - 1, start, end);
 301                 goto out_bits;
 302         }
 303         if (process_page_range(inode, start, end, PROCESS_TEST_LOCKED |
 304                                PROCESS_UNLOCK)) {
 305                 test_err("pages in range were not all locked");
 306                 goto out_bits;
 307         }
 308         ret = 0;
 309 out_bits:
 310         if (ret)
 311                 dump_extent_io_tree(tmp);
 312         clear_extent_bits(tmp, 0, total_dirty - 1, (unsigned)-1);
 313 out:
 314         if (locked_page)
 315                 put_page(locked_page);
 316         process_page_range(inode, 0, total_dirty - 1,
 317                            PROCESS_UNLOCK | PROCESS_RELEASE);
 318         iput(inode);
 319         return ret;
 320 }
 321
 322 static int check_eb_bitmap(unsigned long *bitmap, struct extent_buffer *eb,
 323                            unsigned long len)
 324 {
 325         unsigned long i;
 326
 327         for (i = 0; i < len * BITS_PER_BYTE; i++) {
 328                 int bit, bit1;
 329
 330                 bit = !!test_bit(i, bitmap);
 331                 bit1 = !!extent_buffer_test_bit(eb, 0, i);
 332                 if (bit1 != bit) {
 333                         test_err("bits do not match");
 334                         return -EINVAL;
 335                 }
 336
 337                 bit1 = !!extent_buffer_test_bit(eb, i / BITS_PER_BYTE,
 338                                                 i % BITS_PER_BYTE);
 339                 if (bit1 != bit) {
 340                         test_err("offset bits do not match");
 341                         return -EINVAL;
 342                 }
 343         }
 344         return 0;
 345 }
 346
 347 static int __test_eb_bitmaps(unsigned long *bitmap, struct extent_buffer *eb,
 348                              unsigned long len)
 349 {
 350         unsigned long i, j;
 351         u32 x;
 352         int ret;
 353
 354         memset(bitmap, 0, len);
 355         memzero_extent_buffer(eb, 0, len);
 356         if (memcmp_extent_buffer(eb, bitmap, 0, len) != 0) {
 357                 test_err("bitmap was not zeroed");
 358                 return -EINVAL;
 359         }
 360
 361         bitmap_set(bitmap, 0, len * BITS_PER_BYTE);
 362         extent_buffer_bitmap_set(eb, 0, 0, len * BITS_PER_BYTE);
 363         ret = check_eb_bitmap(bitmap, eb, len);
 364         if (ret) {
 365                 test_err("setting all bits failed");
 366                 return ret;
 367         }
 368
 369         bitmap_clear(bitmap, 0, len * BITS_PER_BYTE);
 370         extent_buffer_bitmap_clear(eb, 0, 0, len * BITS_PER_BYTE);
 371         ret = check_eb_bitmap(bitmap, eb, len);
 372         if (ret) {
 373                 test_err("clearing all bits failed");
 374                 return ret;
 375         }
 376
 377         /* Straddling pages test */
 378         if (len > PAGE_SIZE) {
 379                 bitmap_set(bitmap,
 380                         (PAGE_SIZE - sizeof(long) / 2) * BITS_PER_BYTE,
 381                         sizeof(long) * BITS_PER_BYTE);
 382                 extent_buffer_bitmap_set(eb, PAGE_SIZE - sizeof(long) / 2, 0,
 383                                         sizeof(long) * BITS_PER_BYTE);
 384                 ret = check_eb_bitmap(bitmap, eb, len);
 385                 if (ret) {
 386                         test_err("setting straddling pages failed");
 387                         return ret;
 388                 }
 389
 390                 bitmap_set(bitmap, 0, len * BITS_PER_BYTE);
 391                 bitmap_clear(bitmap,
 392                         (PAGE_SIZE - sizeof(long) / 2) * BITS_PER_BYTE,
 393                         sizeof(long) * BITS_PER_BYTE);
 394                 extent_buffer_bitmap_set(eb, 0, 0, len * BITS_PER_BYTE);
 395                 extent_buffer_bitmap_clear(eb, PAGE_SIZE - sizeof(long) / 2, 0,
 396                                         sizeof(long) * BITS_PER_BYTE);
 397                 ret = check_eb_bitmap(bitmap, eb, len);
 398                 if (ret) {
 399                         test_err("clearing straddling pages failed");
 400                         return ret;
 401                 }
 402         }
 403
 404         /*
 405          * Generate a wonky pseudo-random bit pattern for the sake of not using
 406          * something repetitive that could miss some hypothetical off-by-n bug.
 407          */
 408         x = 0;
 409         bitmap_clear(bitmap, 0, len * BITS_PER_BYTE);
 410         extent_buffer_bitmap_clear(eb, 0, 0, len * BITS_PER_BYTE);
 411         for (i = 0; i < len * BITS_PER_BYTE / 32; i++) {
 412                 x = (0x19660dULL * (u64)x + 0x3c6ef35fULL) & 0xffffffffU;
 413                 for (j = 0; j < 32; j++) {
 414                         if (x & (1U << j)) {
 415                                 bitmap_set(bitmap, i * 32 + j, 1);
 416                                 extent_buffer_bitmap_set(eb, 0, i * 32 + j, 1);
 417                         }
 418                 }
 419         }
 420
 421         ret = check_eb_bitmap(bitmap, eb, len);
 422         if (ret) {
 423                 test_err("random bit pattern failed");
 424                 return ret;
 425         }
 426
 427         return 0;
 428 }
 429
 430 static int test_eb_bitmaps(u32 sectorsize, u32 nodesize)
 431 {
 432         struct btrfs_fs_info *fs_info;
 433         unsigned long *bitmap = NULL;
 434         struct extent_buffer *eb = NULL;
 435         int ret;
 436
 437         test_msg("running extent buffer bitmap tests");
 438
 439         fs_info = btrfs_alloc_dummy_fs_info(nodesize, sectorsize);
 440         if (!fs_info) {
 441                 test_std_err(TEST_ALLOC_FS_INFO);
 442                 return -ENOMEM;
 443         }
 444
 445         bitmap = kmalloc(nodesize, GFP_KERNEL);
 446         if (!bitmap) {
 447                 test_err("couldn't allocate test bitmap");
 448                 ret = -ENOMEM;
 449                 goto out;
 450         }
 451
 452         eb = __alloc_dummy_extent_buffer(fs_info, 0, nodesize);
 453         if (!eb) {
 454                 test_std_err(TEST_ALLOC_ROOT);
 455                 ret = -ENOMEM;
 456                 goto out;
 457         }
 458
 459         ret = __test_eb_bitmaps(bitmap, eb, nodesize);
 460         if (ret)
 461                 goto out;
 462
 463         free_extent_buffer(eb);
 464
 465         /*
 466          * Test again for case where the tree block is sectorsize aligned but
 467          * not nodesize aligned.
 468          */
 469         eb = __alloc_dummy_extent_buffer(fs_info, sectorsize, nodesize);
 470         if (!eb) {
 471                 test_std_err(TEST_ALLOC_ROOT);
 472                 ret = -ENOMEM;
 473                 goto out;
 474         }
 475
 476         ret = __test_eb_bitmaps(bitmap, eb, nodesize);
 477 out:
 478         free_extent_buffer(eb);
 479         kfree(bitmap);
 480         btrfs_free_dummy_fs_info(fs_info);
 481         return ret;
 482 }
 483
 484 static int test_find_first_clear_extent_bit(void)
 485 {
 486         struct extent_io_tree tree;
 487         u64 start, end;
 488         int ret = -EINVAL;
 489
 490         test_msg("running find_first_clear_extent_bit test");
 491
 492         extent_io_tree_init(NULL, &tree, IO_TREE_SELFTEST, NULL);
 493
 494         /* Test correct handling of empty tree */
 495         find_first_clear_extent_bit(&tree, 0, &start, &end, CHUNK_TRIMMED);
 496         if (start != 0 || end != -1) {
 497                 test_err(
 498         "error getting a range from completely empty tree: start %llu end %llu",
 499                          start, end);
 500                 goto out;
 501         }
 502         /*
 503          * Set 1M-4M alloc/discard and 32M-64M thus leaving a hole between
 504          * 4M-32M
 505          */
 506         set_extent_bits(&tree, SZ_1M, SZ_4M - 1,
 507                         CHUNK_TRIMMED | CHUNK_ALLOCATED);
 508
 509         find_first_clear_extent_bit(&tree, SZ_512K, &start, &end,
 510                                     CHUNK_TRIMMED | CHUNK_ALLOCATED);
 511
 512         if (start != 0 || end != SZ_1M - 1) {
 513                 test_err("error finding beginning range: start %llu end %llu",
 514                          start, end);
 515                 goto out;
 516         }
 517
 518         /* Now add 32M-64M so that we have a hole between 4M-32M */
 519         set_extent_bits(&tree, SZ_32M, SZ_64M - 1,
 520                         CHUNK_TRIMMED | CHUNK_ALLOCATED);
 521
 522         /*
 523          * Request first hole starting at 12M, we should get 4M-32M
 524          */
 525         find_first_clear_extent_bit(&tree, 12 * SZ_1M, &start, &end,
 526                                     CHUNK_TRIMMED | CHUNK_ALLOCATED);
 527
 528         if (start != SZ_4M || end != SZ_32M - 1) {
 529                 test_err("error finding trimmed range: start %llu end %llu",
 530                          start, end);
 531                 goto out;
 532         }
 533
 534         /*
 535          * Search in the middle of allocated range, should get the next one
 536          * available, which happens to be unallocated -> 4M-32M
 537          */
 538         find_first_clear_extent_bit(&tree, SZ_2M, &start, &end,
 539                                     CHUNK_TRIMMED | CHUNK_ALLOCATED);
 540
 541         if (start != SZ_4M || end != SZ_32M - 1) {
 542                 test_err("error finding next unalloc range: start %llu end %llu",
 543                          start, end);
 544                 goto out;
 545         }
 546
 547         /*
 548          * Set 64M-72M with CHUNK_ALLOC flag, then search for CHUNK_TRIMMED flag
 549          * being unset in this range, we should get the entry in range 64M-72M
 550          */
 551         set_extent_bits(&tree, SZ_64M, SZ_64M + SZ_8M - 1, CHUNK_ALLOCATED);
 552         find_first_clear_extent_bit(&tree, SZ_64M + SZ_1M, &start, &end,
 553                                     CHUNK_TRIMMED);
 554
 555         if (start != SZ_64M || end != SZ_64M + SZ_8M - 1) {
 556                 test_err("error finding exact range: start %llu end %llu",
 557                          start, end);
 558                 goto out;
 559         }
 560
 561         find_first_clear_extent_bit(&tree, SZ_64M - SZ_8M, &start, &end,
 562                                     CHUNK_TRIMMED);
 563
 564         /*
 565          * Search in the middle of set range whose immediate neighbour doesn't
 566          * have the bits set so it must be returned
 567          */
 568         if (start != SZ_64M || end != SZ_64M + SZ_8M - 1) {
 569                 test_err("error finding next alloc range: start %llu end %llu",
 570                          start, end);
 571                 goto out;
 572         }
 573
 574         /*
 575          * Search beyond any known range, shall return after last known range
 576          * and end should be -1
 577          */
 578         find_first_clear_extent_bit(&tree, -1, &start, &end, CHUNK_TRIMMED);
 579         if (start != SZ_64M + SZ_8M || end != -1) {
 580                 test_err(
 581                 "error handling beyond end of range search: start %llu end %llu",
 582                         start, end);
 583                 goto out;
 584         }
 585
 586         ret = 0;
 587 out:
 588         if (ret)
 589                 dump_extent_io_tree(&tree);
 590         clear_extent_bits(&tree, 0, (u64)-1, CHUNK_TRIMMED | CHUNK_ALLOCATED);
 591
 592         return ret;
 593 }
 594
 595 int btrfs_test_extent_io(u32 sectorsize, u32 nodesize)
 596 {
 597         int ret;
 598
 599         test_msg("running extent I/O tests");
 600
 601         ret = test_find_delalloc(sectorsize);
 602         if (ret)
 603                 goto out;
 604
 605         ret = test_find_first_clear_extent_bit();
 606         if (ret)
 607                 goto out;
 608
 609         ret = test_eb_bitmaps(sectorsize, nodesize);
 610 out:
 611         return ret;
 612 }