1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Copyright (C) 2017 Oracle. All rights reserved. 4 */ 5 6 #include <linux/types.h> 7 #include "btrfs-tests.h" 8 #include "../ctree.h" 9 #include "../volumes.h" 10 #include "../disk-io.h" 11 #include "../block-group.h" 12 13 static void free_extent_map_tree(struct extent_map_tree *em_tree) 14 { 15 struct extent_map *em; 16 struct rb_node *node; 17 18 write_lock(&em_tree->lock); 19 while (!RB_EMPTY_ROOT(&em_tree->map.rb_root)) { 20 node = rb_first_cached(&em_tree->map); 21 em = rb_entry(node, struct extent_map, rb_node); 22 remove_extent_mapping(em_tree, em); 23 24 #ifdef CONFIG_BTRFS_DEBUG 25 if (refcount_read(&em->refs) != 1) { 26 test_err( 27 "em leak: em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx) refs %d", 28 em->start, em->len, em->block_start, 29 em->block_len, refcount_read(&em->refs)); 30 31 refcount_set(&em->refs, 1); 32 } 33 #endif 34 free_extent_map(em); 35 } 36 write_unlock(&em_tree->lock); 37 } 38 39 /* 40 * Test scenario: 41 * 42 * Suppose that no extent map has been loaded into memory yet, there is a file 43 * extent [0, 16K), followed by another file extent [16K, 20K), two dio reads 44 * are entering btrfs_get_extent() concurrently, t1 is reading [8K, 16K), t2 is 45 * reading [0, 8K) 46 * 47 * t1 t2 48 * btrfs_get_extent() btrfs_get_extent() 49 * -> lookup_extent_mapping() ->lookup_extent_mapping() 50 * -> add_extent_mapping(0, 16K) 51 * -> return em 52 * ->add_extent_mapping(0, 16K) 53 * -> #handle -EEXIST 54 */ 55 static int test_case_1(struct btrfs_fs_info *fs_info, 56 struct extent_map_tree *em_tree) 57 { 58 struct extent_map *em; 59 u64 start = 0; 60 u64 len = SZ_8K; 61 int ret; 62 63 em = alloc_extent_map(); 64 if (!em) { 65 test_std_err(TEST_ALLOC_EXTENT_MAP); 66 return -ENOMEM; 67 } 68 69 /* Add [0, 16K) */ 70 em->start = 0; 71 em->len = SZ_16K; 72 em->block_start = 0; 73 em->block_len = SZ_16K; 74 write_lock(&em_tree->lock); 75 ret = add_extent_mapping(em_tree, em, 0); 76 write_unlock(&em_tree->lock); 77 if (ret < 0) { 78 test_err("cannot add extent range [0, 16K)"); 79 goto out; 80 } 81 free_extent_map(em); 82 83 /* Add [16K, 20K) following [0, 16K) */ 84 em = alloc_extent_map(); 85 if (!em) { 86 test_std_err(TEST_ALLOC_EXTENT_MAP); 87 ret = -ENOMEM; 88 goto out; 89 } 90 91 em->start = SZ_16K; 92 em->len = SZ_4K; 93 em->block_start = SZ_32K; /* avoid merging */ 94 em->block_len = SZ_4K; 95 write_lock(&em_tree->lock); 96 ret = add_extent_mapping(em_tree, em, 0); 97 write_unlock(&em_tree->lock); 98 if (ret < 0) { 99 test_err("cannot add extent range [16K, 20K)"); 100 goto out; 101 } 102 free_extent_map(em); 103 104 em = alloc_extent_map(); 105 if (!em) { 106 test_std_err(TEST_ALLOC_EXTENT_MAP); 107 ret = -ENOMEM; 108 goto out; 109 } 110 111 /* Add [0, 8K), should return [0, 16K) instead. */ 112 em->start = start; 113 em->len = len; 114 em->block_start = start; 115 em->block_len = len; 116 write_lock(&em_tree->lock); 117 ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, em->start, em->len); 118 write_unlock(&em_tree->lock); 119 if (ret) { 120 test_err("case1 [%llu %llu]: ret %d", start, start + len, ret); 121 goto out; 122 } 123 if (em && 124 (em->start != 0 || extent_map_end(em) != SZ_16K || 125 em->block_start != 0 || em->block_len != SZ_16K)) { 126 test_err( 127 "case1 [%llu %llu]: ret %d return a wrong em (start %llu len %llu block_start %llu block_len %llu", 128 start, start + len, ret, em->start, em->len, 129 em->block_start, em->block_len); 130 ret = -EINVAL; 131 } 132 free_extent_map(em); 133 out: 134 free_extent_map_tree(em_tree); 135 136 return ret; 137 } 138 139 /* 140 * Test scenario: 141 * 142 * Reading the inline ending up with EEXIST, ie. read an inline 143 * extent and discard page cache and read it again. 144 */ 145 static int test_case_2(struct btrfs_fs_info *fs_info, 146 struct extent_map_tree *em_tree) 147 { 148 struct extent_map *em; 149 int ret; 150 151 em = alloc_extent_map(); 152 if (!em) { 153 test_std_err(TEST_ALLOC_EXTENT_MAP); 154 return -ENOMEM; 155 } 156 157 /* Add [0, 1K) */ 158 em->start = 0; 159 em->len = SZ_1K; 160 em->block_start = EXTENT_MAP_INLINE; 161 em->block_len = (u64)-1; 162 write_lock(&em_tree->lock); 163 ret = add_extent_mapping(em_tree, em, 0); 164 write_unlock(&em_tree->lock); 165 if (ret < 0) { 166 test_err("cannot add extent range [0, 1K)"); 167 goto out; 168 } 169 free_extent_map(em); 170 171 /* Add [4K, 8K) following [0, 1K) */ 172 em = alloc_extent_map(); 173 if (!em) { 174 test_std_err(TEST_ALLOC_EXTENT_MAP); 175 ret = -ENOMEM; 176 goto out; 177 } 178 179 em->start = SZ_4K; 180 em->len = SZ_4K; 181 em->block_start = SZ_4K; 182 em->block_len = SZ_4K; 183 write_lock(&em_tree->lock); 184 ret = add_extent_mapping(em_tree, em, 0); 185 write_unlock(&em_tree->lock); 186 if (ret < 0) { 187 test_err("cannot add extent range [4K, 8K)"); 188 goto out; 189 } 190 free_extent_map(em); 191 192 em = alloc_extent_map(); 193 if (!em) { 194 test_std_err(TEST_ALLOC_EXTENT_MAP); 195 ret = -ENOMEM; 196 goto out; 197 } 198 199 /* Add [0, 1K) */ 200 em->start = 0; 201 em->len = SZ_1K; 202 em->block_start = EXTENT_MAP_INLINE; 203 em->block_len = (u64)-1; 204 write_lock(&em_tree->lock); 205 ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, em->start, em->len); 206 write_unlock(&em_tree->lock); 207 if (ret) { 208 test_err("case2 [0 1K]: ret %d", ret); 209 goto out; 210 } 211 if (em && 212 (em->start != 0 || extent_map_end(em) != SZ_1K || 213 em->block_start != EXTENT_MAP_INLINE || em->block_len != (u64)-1)) { 214 test_err( 215 "case2 [0 1K]: ret %d return a wrong em (start %llu len %llu block_start %llu block_len %llu", 216 ret, em->start, em->len, em->block_start, 217 em->block_len); 218 ret = -EINVAL; 219 } 220 free_extent_map(em); 221 out: 222 free_extent_map_tree(em_tree); 223 224 return ret; 225 } 226 227 static int __test_case_3(struct btrfs_fs_info *fs_info, 228 struct extent_map_tree *em_tree, u64 start) 229 { 230 struct extent_map *em; 231 u64 len = SZ_4K; 232 int ret; 233 234 em = alloc_extent_map(); 235 if (!em) { 236 test_std_err(TEST_ALLOC_EXTENT_MAP); 237 return -ENOMEM; 238 } 239 240 /* Add [4K, 8K) */ 241 em->start = SZ_4K; 242 em->len = SZ_4K; 243 em->block_start = SZ_4K; 244 em->block_len = SZ_4K; 245 write_lock(&em_tree->lock); 246 ret = add_extent_mapping(em_tree, em, 0); 247 write_unlock(&em_tree->lock); 248 if (ret < 0) { 249 test_err("cannot add extent range [4K, 8K)"); 250 goto out; 251 } 252 free_extent_map(em); 253 254 em = alloc_extent_map(); 255 if (!em) { 256 test_std_err(TEST_ALLOC_EXTENT_MAP); 257 ret = -ENOMEM; 258 goto out; 259 } 260 261 /* Add [0, 16K) */ 262 em->start = 0; 263 em->len = SZ_16K; 264 em->block_start = 0; 265 em->block_len = SZ_16K; 266 write_lock(&em_tree->lock); 267 ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, start, len); 268 write_unlock(&em_tree->lock); 269 if (ret) { 270 test_err("case3 [0x%llx 0x%llx): ret %d", 271 start, start + len, ret); 272 goto out; 273 } 274 /* 275 * Since bytes within em are contiguous, em->block_start is identical to 276 * em->start. 277 */ 278 if (em && 279 (start < em->start || start + len > extent_map_end(em) || 280 em->start != em->block_start || em->len != em->block_len)) { 281 test_err( 282 "case3 [0x%llx 0x%llx): ret %d em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx)", 283 start, start + len, ret, em->start, em->len, 284 em->block_start, em->block_len); 285 ret = -EINVAL; 286 } 287 free_extent_map(em); 288 out: 289 free_extent_map_tree(em_tree); 290 291 return ret; 292 } 293 294 /* 295 * Test scenario: 296 * 297 * Suppose that no extent map has been loaded into memory yet. 298 * There is a file extent [0, 16K), two jobs are running concurrently 299 * against it, t1 is buffered writing to [4K, 8K) and t2 is doing dio 300 * read from [0, 4K) or [8K, 12K) or [12K, 16K). 301 * 302 * t1 goes ahead of t2 and adds em [4K, 8K) into tree. 303 * 304 * t1 t2 305 * cow_file_range() btrfs_get_extent() 306 * -> lookup_extent_mapping() 307 * -> add_extent_mapping() 308 * -> add_extent_mapping() 309 */ 310 static int test_case_3(struct btrfs_fs_info *fs_info, 311 struct extent_map_tree *em_tree) 312 { 313 int ret; 314 315 ret = __test_case_3(fs_info, em_tree, 0); 316 if (ret) 317 return ret; 318 ret = __test_case_3(fs_info, em_tree, SZ_8K); 319 if (ret) 320 return ret; 321 ret = __test_case_3(fs_info, em_tree, (12 * SZ_1K)); 322 323 return ret; 324 } 325 326 static int __test_case_4(struct btrfs_fs_info *fs_info, 327 struct extent_map_tree *em_tree, u64 start) 328 { 329 struct extent_map *em; 330 u64 len = SZ_4K; 331 int ret; 332 333 em = alloc_extent_map(); 334 if (!em) { 335 test_std_err(TEST_ALLOC_EXTENT_MAP); 336 return -ENOMEM; 337 } 338 339 /* Add [0K, 8K) */ 340 em->start = 0; 341 em->len = SZ_8K; 342 em->block_start = 0; 343 em->block_len = SZ_8K; 344 write_lock(&em_tree->lock); 345 ret = add_extent_mapping(em_tree, em, 0); 346 write_unlock(&em_tree->lock); 347 if (ret < 0) { 348 test_err("cannot add extent range [0, 8K)"); 349 goto out; 350 } 351 free_extent_map(em); 352 353 em = alloc_extent_map(); 354 if (!em) { 355 test_std_err(TEST_ALLOC_EXTENT_MAP); 356 ret = -ENOMEM; 357 goto out; 358 } 359 360 /* Add [8K, 32K) */ 361 em->start = SZ_8K; 362 em->len = 24 * SZ_1K; 363 em->block_start = SZ_16K; /* avoid merging */ 364 em->block_len = 24 * SZ_1K; 365 write_lock(&em_tree->lock); 366 ret = add_extent_mapping(em_tree, em, 0); 367 write_unlock(&em_tree->lock); 368 if (ret < 0) { 369 test_err("cannot add extent range [8K, 32K)"); 370 goto out; 371 } 372 free_extent_map(em); 373 374 em = alloc_extent_map(); 375 if (!em) { 376 test_std_err(TEST_ALLOC_EXTENT_MAP); 377 ret = -ENOMEM; 378 goto out; 379 } 380 /* Add [0K, 32K) */ 381 em->start = 0; 382 em->len = SZ_32K; 383 em->block_start = 0; 384 em->block_len = SZ_32K; 385 write_lock(&em_tree->lock); 386 ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, start, len); 387 write_unlock(&em_tree->lock); 388 if (ret) { 389 test_err("case4 [0x%llx 0x%llx): ret %d", 390 start, len, ret); 391 goto out; 392 } 393 if (em && (start < em->start || start + len > extent_map_end(em))) { 394 test_err( 395 "case4 [0x%llx 0x%llx): ret %d, added wrong em (start 0x%llx len 0x%llx block_start 0x%llx block_len 0x%llx)", 396 start, len, ret, em->start, em->len, em->block_start, 397 em->block_len); 398 ret = -EINVAL; 399 } 400 free_extent_map(em); 401 out: 402 free_extent_map_tree(em_tree); 403 404 return ret; 405 } 406 407 /* 408 * Test scenario: 409 * 410 * Suppose that no extent map has been loaded into memory yet. 411 * There is a file extent [0, 32K), two jobs are running concurrently 412 * against it, t1 is doing dio write to [8K, 32K) and t2 is doing dio 413 * read from [0, 4K) or [4K, 8K). 414 * 415 * t1 goes ahead of t2 and splits em [0, 32K) to em [0K, 8K) and [8K 32K). 416 * 417 * t1 t2 418 * btrfs_get_blocks_direct() btrfs_get_blocks_direct() 419 * -> btrfs_get_extent() -> btrfs_get_extent() 420 * -> lookup_extent_mapping() 421 * -> add_extent_mapping() -> lookup_extent_mapping() 422 * # load [0, 32K) 423 * -> btrfs_new_extent_direct() 424 * -> btrfs_drop_extent_cache() 425 * # split [0, 32K) 426 * -> add_extent_mapping() 427 * # add [8K, 32K) 428 * -> add_extent_mapping() 429 * # handle -EEXIST when adding 430 * # [0, 32K) 431 */ 432 static int test_case_4(struct btrfs_fs_info *fs_info, 433 struct extent_map_tree *em_tree) 434 { 435 int ret; 436 437 ret = __test_case_4(fs_info, em_tree, 0); 438 if (ret) 439 return ret; 440 ret = __test_case_4(fs_info, em_tree, SZ_4K); 441 442 return ret; 443 } 444 445 struct rmap_test_vector { 446 u64 raid_type; 447 u64 physical_start; 448 u64 data_stripe_size; 449 u64 num_data_stripes; 450 u64 num_stripes; 451 /* Assume we won't have more than 5 physical stripes */ 452 u64 data_stripe_phys_start[5]; 453 bool expected_mapped_addr; 454 /* Physical to logical addresses */ 455 u64 mapped_logical[5]; 456 }; 457 458 static int test_rmap_block(struct btrfs_fs_info *fs_info, 459 struct rmap_test_vector *test) 460 { 461 struct extent_map *em; 462 struct map_lookup *map = NULL; 463 u64 *logical = NULL; 464 int i, out_ndaddrs, out_stripe_len; 465 int ret; 466 467 em = alloc_extent_map(); 468 if (!em) { 469 test_std_err(TEST_ALLOC_EXTENT_MAP); 470 return -ENOMEM; 471 } 472 473 map = kmalloc(map_lookup_size(test->num_stripes), GFP_KERNEL); 474 if (!map) { 475 kfree(em); 476 test_std_err(TEST_ALLOC_EXTENT_MAP); 477 return -ENOMEM; 478 } 479 480 set_bit(EXTENT_FLAG_FS_MAPPING, &em->flags); 481 /* Start at 4GiB logical address */ 482 em->start = SZ_4G; 483 em->len = test->data_stripe_size * test->num_data_stripes; 484 em->block_len = em->len; 485 em->orig_block_len = test->data_stripe_size; 486 em->map_lookup = map; 487 488 map->num_stripes = test->num_stripes; 489 map->type = test->raid_type; 490 491 for (i = 0; i < map->num_stripes; i++) { 492 struct btrfs_device *dev = btrfs_alloc_dummy_device(fs_info); 493 494 if (IS_ERR(dev)) { 495 test_err("cannot allocate device"); 496 ret = PTR_ERR(dev); 497 goto out; 498 } 499 map->stripes[i].dev = dev; 500 map->stripes[i].physical = test->data_stripe_phys_start[i]; 501 } 502 503 write_lock(&fs_info->mapping_tree.lock); 504 ret = add_extent_mapping(&fs_info->mapping_tree, em, 0); 505 write_unlock(&fs_info->mapping_tree.lock); 506 if (ret) { 507 test_err("error adding block group mapping to mapping tree"); 508 goto out_free; 509 } 510 511 ret = btrfs_rmap_block(fs_info, em->start, btrfs_sb_offset(1), 512 &logical, &out_ndaddrs, &out_stripe_len); 513 if (ret || (out_ndaddrs == 0 && test->expected_mapped_addr)) { 514 test_err("didn't rmap anything but expected %d", 515 test->expected_mapped_addr); 516 goto out; 517 } 518 519 if (out_stripe_len != BTRFS_STRIPE_LEN) { 520 test_err("calculated stripe length doesn't match"); 521 goto out; 522 } 523 524 if (out_ndaddrs != test->expected_mapped_addr) { 525 for (i = 0; i < out_ndaddrs; i++) 526 test_msg("mapped %llu", logical[i]); 527 test_err("unexpected number of mapped addresses: %d", out_ndaddrs); 528 goto out; 529 } 530 531 for (i = 0; i < out_ndaddrs; i++) { 532 if (logical[i] != test->mapped_logical[i]) { 533 test_err("unexpected logical address mapped"); 534 goto out; 535 } 536 } 537 538 ret = 0; 539 out: 540 write_lock(&fs_info->mapping_tree.lock); 541 remove_extent_mapping(&fs_info->mapping_tree, em); 542 write_unlock(&fs_info->mapping_tree.lock); 543 /* For us */ 544 free_extent_map(em); 545 out_free: 546 /* For the tree */ 547 free_extent_map(em); 548 kfree(logical); 549 return ret; 550 } 551 552 int btrfs_test_extent_map(void) 553 { 554 struct btrfs_fs_info *fs_info = NULL; 555 struct extent_map_tree *em_tree; 556 int ret = 0, i; 557 struct rmap_test_vector rmap_tests[] = { 558 { 559 /* 560 * Test a chunk with 2 data stripes one of which 561 * intersects the physical address of the super block 562 * is correctly recognised. 563 */ 564 .raid_type = BTRFS_BLOCK_GROUP_RAID1, 565 .physical_start = SZ_64M - SZ_4M, 566 .data_stripe_size = SZ_256M, 567 .num_data_stripes = 2, 568 .num_stripes = 2, 569 .data_stripe_phys_start = 570 {SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M}, 571 .expected_mapped_addr = true, 572 .mapped_logical= {SZ_4G + SZ_4M} 573 }, 574 { 575 /* 576 * Test that out-of-range physical addresses are 577 * ignored 578 */ 579 580 /* SINGLE chunk type */ 581 .raid_type = 0, 582 .physical_start = SZ_4G, 583 .data_stripe_size = SZ_256M, 584 .num_data_stripes = 1, 585 .num_stripes = 1, 586 .data_stripe_phys_start = {SZ_256M}, 587 .expected_mapped_addr = false, 588 .mapped_logical = {0} 589 } 590 }; 591 592 test_msg("running extent_map tests"); 593 594 /* 595 * Note: the fs_info is not set up completely, we only need 596 * fs_info::fsid for the tracepoint. 597 */ 598 fs_info = btrfs_alloc_dummy_fs_info(PAGE_SIZE, PAGE_SIZE); 599 if (!fs_info) { 600 test_std_err(TEST_ALLOC_FS_INFO); 601 return -ENOMEM; 602 } 603 604 em_tree = kzalloc(sizeof(*em_tree), GFP_KERNEL); 605 if (!em_tree) { 606 ret = -ENOMEM; 607 goto out; 608 } 609 610 extent_map_tree_init(em_tree); 611 612 ret = test_case_1(fs_info, em_tree); 613 if (ret) 614 goto out; 615 ret = test_case_2(fs_info, em_tree); 616 if (ret) 617 goto out; 618 ret = test_case_3(fs_info, em_tree); 619 if (ret) 620 goto out; 621 ret = test_case_4(fs_info, em_tree); 622 623 test_msg("running rmap tests"); 624 for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) { 625 ret = test_rmap_block(fs_info, &rmap_tests[i]); 626 if (ret) 627 goto out; 628 } 629 630 out: 631 kfree(em_tree); 632 btrfs_free_dummy_fs_info(fs_info); 633 634 return ret; 635 } 636