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