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 } 613