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 "../btrfs_inode.h" 10 #include "../volumes.h" 11 #include "../disk-io.h" 12 #include "../block-group.h" 13 14 static int free_extent_map_tree(struct btrfs_inode *inode) 15 { 16 struct extent_map_tree *em_tree = &inode->extent_tree; 17 struct extent_map *em; 18 struct rb_node *node; 19 int ret = 0; 20 21 write_lock(&em_tree->lock); 22 while (!RB_EMPTY_ROOT(&em_tree->root)) { 23 node = rb_first(&em_tree->root); 24 em = rb_entry(node, struct extent_map, rb_node); 25 btrfs_remove_extent_mapping(inode, em); 26 27 #ifdef CONFIG_BTRFS_DEBUG 28 if (refcount_read(&em->refs) != 1) { 29 ret = -EINVAL; 30 test_err( 31 "em leak: em (start %llu len %llu disk_bytenr %llu disk_num_bytes %llu offset %llu) refs %d", 32 em->start, em->len, em->disk_bytenr, 33 em->disk_num_bytes, em->offset, 34 refcount_read(&em->refs)); 35 36 refcount_set(&em->refs, 1); 37 } 38 #endif 39 btrfs_free_extent_map(em); 40 } 41 write_unlock(&em_tree->lock); 42 43 return ret; 44 } 45 46 /* 47 * Test scenario: 48 * 49 * Suppose that no extent map has been loaded into memory yet, there is a file 50 * extent [0, 16K), followed by another file extent [16K, 20K), two dio reads 51 * are entering btrfs_get_extent() concurrently, t1 is reading [8K, 16K), t2 is 52 * reading [0, 8K) 53 * 54 * t1 t2 55 * btrfs_get_extent() btrfs_get_extent() 56 * -> lookup_extent_mapping() ->lookup_extent_mapping() 57 * -> add_extent_mapping(0, 16K) 58 * -> return em 59 * ->add_extent_mapping(0, 16K) 60 * -> #handle -EEXIST 61 */ 62 static int test_case_1(struct btrfs_fs_info *fs_info, struct btrfs_inode *inode) 63 { 64 struct extent_map_tree *em_tree = &inode->extent_tree; 65 struct extent_map *em; 66 u64 start = 0; 67 u64 len = SZ_8K; 68 int ret; 69 int ret2; 70 71 em = btrfs_alloc_extent_map(); 72 if (!em) { 73 test_std_err(TEST_ALLOC_EXTENT_MAP); 74 return -ENOMEM; 75 } 76 77 /* Add [0, 16K) */ 78 em->start = 0; 79 em->len = SZ_16K; 80 em->disk_bytenr = 0; 81 em->disk_num_bytes = SZ_16K; 82 em->ram_bytes = SZ_16K; 83 write_lock(&em_tree->lock); 84 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 85 write_unlock(&em_tree->lock); 86 if (ret < 0) { 87 test_err("cannot add extent range [0, 16K)"); 88 goto out; 89 } 90 btrfs_free_extent_map(em); 91 92 /* Add [16K, 20K) following [0, 16K) */ 93 em = btrfs_alloc_extent_map(); 94 if (!em) { 95 test_std_err(TEST_ALLOC_EXTENT_MAP); 96 ret = -ENOMEM; 97 goto out; 98 } 99 100 em->start = SZ_16K; 101 em->len = SZ_4K; 102 em->disk_bytenr = SZ_32K; /* avoid merging */ 103 em->disk_num_bytes = SZ_4K; 104 em->ram_bytes = SZ_4K; 105 write_lock(&em_tree->lock); 106 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 107 write_unlock(&em_tree->lock); 108 if (ret < 0) { 109 test_err("cannot add extent range [16K, 20K)"); 110 goto out; 111 } 112 btrfs_free_extent_map(em); 113 114 em = btrfs_alloc_extent_map(); 115 if (!em) { 116 test_std_err(TEST_ALLOC_EXTENT_MAP); 117 ret = -ENOMEM; 118 goto out; 119 } 120 121 /* Add [0, 8K), should return [0, 16K) instead. */ 122 em->start = start; 123 em->len = len; 124 em->disk_bytenr = start; 125 em->disk_num_bytes = len; 126 em->ram_bytes = len; 127 write_lock(&em_tree->lock); 128 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 129 write_unlock(&em_tree->lock); 130 if (ret) { 131 test_err("case1 [%llu %llu]: ret %d", start, start + len, ret); 132 goto out; 133 } 134 if (!em) { 135 test_err("case1 [%llu %llu]: no extent map returned", 136 start, start + len); 137 ret = -ENOENT; 138 goto out; 139 } 140 if (em->start != 0 || btrfs_extent_map_end(em) != SZ_16K || 141 em->disk_bytenr != 0 || em->disk_num_bytes != SZ_16K) { 142 test_err( 143 "case1 [%llu %llu]: ret %d return a wrong em (start %llu len %llu disk_bytenr %llu disk_num_bytes %llu", 144 start, start + len, ret, em->start, em->len, 145 em->disk_bytenr, em->disk_num_bytes); 146 ret = -EINVAL; 147 } 148 btrfs_free_extent_map(em); 149 out: 150 ret2 = free_extent_map_tree(inode); 151 if (ret == 0) 152 ret = ret2; 153 154 return ret; 155 } 156 157 /* 158 * Test scenario: 159 * 160 * Reading the inline ending up with EEXIST, ie. read an inline 161 * extent and discard page cache and read it again. 162 */ 163 static int test_case_2(struct btrfs_fs_info *fs_info, struct btrfs_inode *inode) 164 { 165 struct extent_map_tree *em_tree = &inode->extent_tree; 166 struct extent_map *em; 167 int ret; 168 int ret2; 169 170 em = btrfs_alloc_extent_map(); 171 if (!em) { 172 test_std_err(TEST_ALLOC_EXTENT_MAP); 173 return -ENOMEM; 174 } 175 176 /* 177 * Add [0, 1K) which is inlined. And the extent map length must 178 * be one block. 179 */ 180 em->start = 0; 181 em->len = SZ_4K; 182 em->disk_bytenr = EXTENT_MAP_INLINE; 183 em->disk_num_bytes = 0; 184 em->ram_bytes = SZ_1K; 185 write_lock(&em_tree->lock); 186 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 187 write_unlock(&em_tree->lock); 188 if (ret < 0) { 189 test_err("cannot add extent range [0, 1K)"); 190 goto out; 191 } 192 btrfs_free_extent_map(em); 193 194 /* Add [4K, 8K) following [0, 1K) */ 195 em = btrfs_alloc_extent_map(); 196 if (!em) { 197 test_std_err(TEST_ALLOC_EXTENT_MAP); 198 ret = -ENOMEM; 199 goto out; 200 } 201 202 em->start = SZ_4K; 203 em->len = SZ_4K; 204 em->disk_bytenr = SZ_4K; 205 em->disk_num_bytes = SZ_4K; 206 em->ram_bytes = SZ_4K; 207 write_lock(&em_tree->lock); 208 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 209 write_unlock(&em_tree->lock); 210 if (ret < 0) { 211 test_err("cannot add extent range [4K, 8K)"); 212 goto out; 213 } 214 btrfs_free_extent_map(em); 215 216 em = btrfs_alloc_extent_map(); 217 if (!em) { 218 test_std_err(TEST_ALLOC_EXTENT_MAP); 219 ret = -ENOMEM; 220 goto out; 221 } 222 223 /* Add [0, 1K) */ 224 em->start = 0; 225 em->len = SZ_4K; 226 em->disk_bytenr = EXTENT_MAP_INLINE; 227 em->disk_num_bytes = 0; 228 em->ram_bytes = SZ_1K; 229 write_lock(&em_tree->lock); 230 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 231 write_unlock(&em_tree->lock); 232 if (ret) { 233 test_err("case2 [0 1K]: ret %d", ret); 234 goto out; 235 } 236 if (!em) { 237 test_err("case2 [0 1K]: no extent map returned"); 238 ret = -ENOENT; 239 goto out; 240 } 241 if (em->start != 0 || btrfs_extent_map_end(em) != SZ_4K || 242 em->disk_bytenr != EXTENT_MAP_INLINE) { 243 test_err( 244 "case2 [0 1K]: ret %d return a wrong em (start %llu len %llu disk_bytenr %llu", 245 ret, em->start, em->len, em->disk_bytenr); 246 ret = -EINVAL; 247 } 248 btrfs_free_extent_map(em); 249 out: 250 ret2 = free_extent_map_tree(inode); 251 if (ret == 0) 252 ret = ret2; 253 254 return ret; 255 } 256 257 static int __test_case_3(struct btrfs_fs_info *fs_info, 258 struct btrfs_inode *inode, u64 start) 259 { 260 struct extent_map_tree *em_tree = &inode->extent_tree; 261 struct extent_map *em; 262 u64 len = SZ_4K; 263 int ret; 264 int ret2; 265 266 em = btrfs_alloc_extent_map(); 267 if (!em) { 268 test_std_err(TEST_ALLOC_EXTENT_MAP); 269 return -ENOMEM; 270 } 271 272 /* Add [4K, 8K) */ 273 em->start = SZ_4K; 274 em->len = SZ_4K; 275 em->disk_bytenr = SZ_4K; 276 em->disk_num_bytes = SZ_4K; 277 em->ram_bytes = SZ_4K; 278 write_lock(&em_tree->lock); 279 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 280 write_unlock(&em_tree->lock); 281 if (ret < 0) { 282 test_err("cannot add extent range [4K, 8K)"); 283 goto out; 284 } 285 btrfs_free_extent_map(em); 286 287 em = btrfs_alloc_extent_map(); 288 if (!em) { 289 test_std_err(TEST_ALLOC_EXTENT_MAP); 290 ret = -ENOMEM; 291 goto out; 292 } 293 294 /* Add [0, 16K) */ 295 em->start = 0; 296 em->len = SZ_16K; 297 em->disk_bytenr = 0; 298 em->disk_num_bytes = SZ_16K; 299 em->ram_bytes = SZ_16K; 300 write_lock(&em_tree->lock); 301 ret = btrfs_add_extent_mapping(inode, &em, start, len); 302 write_unlock(&em_tree->lock); 303 if (ret) { 304 test_err("case3 [%llu %llu): ret %d", 305 start, start + len, ret); 306 goto out; 307 } 308 if (!em) { 309 test_err("case3 [%llu %llu): no extent map returned", 310 start, start + len); 311 ret = -ENOENT; 312 goto out; 313 } 314 /* 315 * Since bytes within em are contiguous, em->block_start is identical to 316 * em->start. 317 */ 318 if (start < em->start || start + len > btrfs_extent_map_end(em) || 319 em->start != btrfs_extent_map_block_start(em)) { 320 test_err( 321 "case3 [%llu %llu): ret %d em (start %llu len %llu disk_bytenr %llu block_len %llu)", 322 start, start + len, ret, em->start, em->len, 323 em->disk_bytenr, em->disk_num_bytes); 324 ret = -EINVAL; 325 } 326 btrfs_free_extent_map(em); 327 out: 328 ret2 = free_extent_map_tree(inode); 329 if (ret == 0) 330 ret = ret2; 331 332 return ret; 333 } 334 335 /* 336 * Test scenario: 337 * 338 * Suppose that no extent map has been loaded into memory yet. 339 * There is a file extent [0, 16K), two jobs are running concurrently 340 * against it, t1 is buffered writing to [4K, 8K) and t2 is doing dio 341 * read from [0, 4K) or [8K, 12K) or [12K, 16K). 342 * 343 * t1 goes ahead of t2 and adds em [4K, 8K) into tree. 344 * 345 * t1 t2 346 * cow_file_range() btrfs_get_extent() 347 * -> lookup_extent_mapping() 348 * -> add_extent_mapping() 349 * -> add_extent_mapping() 350 */ 351 static int test_case_3(struct btrfs_fs_info *fs_info, struct btrfs_inode *inode) 352 { 353 int ret; 354 355 ret = __test_case_3(fs_info, inode, 0); 356 if (ret) 357 return ret; 358 ret = __test_case_3(fs_info, inode, SZ_8K); 359 if (ret) 360 return ret; 361 ret = __test_case_3(fs_info, inode, (12 * SZ_1K)); 362 363 return ret; 364 } 365 366 static int __test_case_4(struct btrfs_fs_info *fs_info, 367 struct btrfs_inode *inode, u64 start) 368 { 369 struct extent_map_tree *em_tree = &inode->extent_tree; 370 struct extent_map *em; 371 u64 len = SZ_4K; 372 int ret; 373 int ret2; 374 375 em = btrfs_alloc_extent_map(); 376 if (!em) { 377 test_std_err(TEST_ALLOC_EXTENT_MAP); 378 return -ENOMEM; 379 } 380 381 /* Add [0K, 8K) */ 382 em->start = 0; 383 em->len = SZ_8K; 384 em->disk_bytenr = 0; 385 em->disk_num_bytes = SZ_8K; 386 em->ram_bytes = SZ_8K; 387 write_lock(&em_tree->lock); 388 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 389 write_unlock(&em_tree->lock); 390 if (ret < 0) { 391 test_err("cannot add extent range [0, 8K)"); 392 goto out; 393 } 394 btrfs_free_extent_map(em); 395 396 em = btrfs_alloc_extent_map(); 397 if (!em) { 398 test_std_err(TEST_ALLOC_EXTENT_MAP); 399 ret = -ENOMEM; 400 goto out; 401 } 402 403 /* Add [8K, 32K) */ 404 em->start = SZ_8K; 405 em->len = 24 * SZ_1K; 406 em->disk_bytenr = SZ_16K; /* avoid merging */ 407 em->disk_num_bytes = 24 * SZ_1K; 408 em->ram_bytes = 24 * SZ_1K; 409 write_lock(&em_tree->lock); 410 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 411 write_unlock(&em_tree->lock); 412 if (ret < 0) { 413 test_err("cannot add extent range [8K, 32K)"); 414 goto out; 415 } 416 btrfs_free_extent_map(em); 417 418 em = btrfs_alloc_extent_map(); 419 if (!em) { 420 test_std_err(TEST_ALLOC_EXTENT_MAP); 421 ret = -ENOMEM; 422 goto out; 423 } 424 /* Add [0K, 32K) */ 425 em->start = 0; 426 em->len = SZ_32K; 427 em->disk_bytenr = 0; 428 em->disk_num_bytes = SZ_32K; 429 em->ram_bytes = SZ_32K; 430 write_lock(&em_tree->lock); 431 ret = btrfs_add_extent_mapping(inode, &em, start, len); 432 write_unlock(&em_tree->lock); 433 if (ret) { 434 test_err("case4 [%llu %llu): ret %d", 435 start, start + len, ret); 436 goto out; 437 } 438 if (!em) { 439 test_err("case4 [%llu %llu): no extent map returned", 440 start, start + len); 441 ret = -ENOENT; 442 goto out; 443 } 444 if (start < em->start || start + len > btrfs_extent_map_end(em)) { 445 test_err( 446 "case4 [%llu %llu): ret %d, added wrong em (start %llu len %llu disk_bytenr %llu disk_num_bytes %llu)", 447 start, start + len, ret, em->start, em->len, 448 em->disk_bytenr, em->disk_num_bytes); 449 ret = -EINVAL; 450 } 451 btrfs_free_extent_map(em); 452 out: 453 ret2 = free_extent_map_tree(inode); 454 if (ret == 0) 455 ret = ret2; 456 457 return ret; 458 } 459 460 /* 461 * Test scenario: 462 * 463 * Suppose that no extent map has been loaded into memory yet. 464 * There is a file extent [0, 32K), two jobs are running concurrently 465 * against it, t1 is doing dio write to [8K, 32K) and t2 is doing dio 466 * read from [0, 4K) or [4K, 8K). 467 * 468 * t1 goes ahead of t2 and splits em [0, 32K) to em [0K, 8K) and [8K 32K). 469 * 470 * t1 t2 471 * btrfs_get_blocks_direct() btrfs_get_blocks_direct() 472 * -> btrfs_get_extent() -> btrfs_get_extent() 473 * -> lookup_extent_mapping() 474 * -> add_extent_mapping() -> lookup_extent_mapping() 475 * # load [0, 32K) 476 * -> btrfs_new_extent_direct() 477 * -> btrfs_drop_extent_cache() 478 * # split [0, 32K) 479 * -> add_extent_mapping() 480 * # add [8K, 32K) 481 * -> add_extent_mapping() 482 * # handle -EEXIST when adding 483 * # [0, 32K) 484 */ 485 static int test_case_4(struct btrfs_fs_info *fs_info, struct btrfs_inode *inode) 486 { 487 int ret; 488 489 ret = __test_case_4(fs_info, inode, 0); 490 if (ret) 491 return ret; 492 ret = __test_case_4(fs_info, inode, SZ_4K); 493 494 return ret; 495 } 496 497 static int add_compressed_extent(struct btrfs_inode *inode, 498 u64 start, u64 len, u64 block_start) 499 { 500 struct extent_map_tree *em_tree = &inode->extent_tree; 501 struct extent_map *em; 502 int ret; 503 504 em = btrfs_alloc_extent_map(); 505 if (!em) { 506 test_std_err(TEST_ALLOC_EXTENT_MAP); 507 return -ENOMEM; 508 } 509 510 em->start = start; 511 em->len = len; 512 em->disk_bytenr = block_start; 513 em->disk_num_bytes = SZ_4K; 514 em->ram_bytes = len; 515 em->flags |= EXTENT_FLAG_COMPRESS_ZLIB; 516 write_lock(&em_tree->lock); 517 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 518 write_unlock(&em_tree->lock); 519 btrfs_free_extent_map(em); 520 if (ret < 0) { 521 test_err("cannot add extent map [%llu, %llu)", start, start + len); 522 return ret; 523 } 524 525 return 0; 526 } 527 528 struct extent_range { 529 u64 start; 530 u64 len; 531 }; 532 533 /* The valid states of the tree after every drop, as described below. */ 534 struct extent_range valid_ranges[][7] = { 535 { 536 { .start = 0, .len = SZ_8K }, /* [0, 8K) */ 537 { .start = SZ_4K * 3, .len = SZ_4K * 3}, /* [12k, 24k) */ 538 { .start = SZ_4K * 6, .len = SZ_4K * 3}, /* [24k, 36k) */ 539 { .start = SZ_32K + SZ_4K, .len = SZ_4K}, /* [36k, 40k) */ 540 { .start = SZ_4K * 10, .len = SZ_4K * 6}, /* [40k, 64k) */ 541 }, 542 { 543 { .start = 0, .len = SZ_8K }, /* [0, 8K) */ 544 { .start = SZ_4K * 5, .len = SZ_4K}, /* [20k, 24k) */ 545 { .start = SZ_4K * 6, .len = SZ_4K * 3}, /* [24k, 36k) */ 546 { .start = SZ_32K + SZ_4K, .len = SZ_4K}, /* [36k, 40k) */ 547 { .start = SZ_4K * 10, .len = SZ_4K * 6}, /* [40k, 64k) */ 548 }, 549 { 550 { .start = 0, .len = SZ_8K }, /* [0, 8K) */ 551 { .start = SZ_4K * 5, .len = SZ_4K}, /* [20k, 24k) */ 552 { .start = SZ_4K * 6, .len = SZ_4K}, /* [24k, 28k) */ 553 { .start = SZ_32K, .len = SZ_4K}, /* [32k, 36k) */ 554 { .start = SZ_32K + SZ_4K, .len = SZ_4K}, /* [36k, 40k) */ 555 { .start = SZ_4K * 10, .len = SZ_4K * 6}, /* [40k, 64k) */ 556 }, 557 { 558 { .start = 0, .len = SZ_8K}, /* [0, 8K) */ 559 { .start = SZ_4K * 5, .len = SZ_4K}, /* [20k, 24k) */ 560 { .start = SZ_4K * 6, .len = SZ_4K}, /* [24k, 28k) */ 561 } 562 }; 563 564 static int validate_range(struct extent_map_tree *em_tree, int index) 565 { 566 struct rb_node *n; 567 int i; 568 569 for (i = 0, n = rb_first(&em_tree->root); 570 valid_ranges[index][i].len && n; 571 i++, n = rb_next(n)) { 572 struct extent_map *entry = rb_entry(n, struct extent_map, rb_node); 573 574 if (entry->start != valid_ranges[index][i].start) { 575 test_err("mapping has start %llu expected %llu", 576 entry->start, valid_ranges[index][i].start); 577 return -EINVAL; 578 } 579 580 if (entry->len != valid_ranges[index][i].len) { 581 test_err("mapping has len %llu expected %llu", 582 entry->len, valid_ranges[index][i].len); 583 return -EINVAL; 584 } 585 } 586 587 /* 588 * We exited because we don't have any more entries in the extent_map 589 * but we still expect more valid entries. 590 */ 591 if (valid_ranges[index][i].len) { 592 test_err("missing an entry"); 593 return -EINVAL; 594 } 595 596 /* We exited the loop but still have entries in the extent map. */ 597 if (n) { 598 test_err("we have a left over entry in the extent map we didn't expect"); 599 return -EINVAL; 600 } 601 602 return 0; 603 } 604 605 /* 606 * Test scenario: 607 * 608 * Test the various edge cases of btrfs_drop_extent_map_range, create the 609 * following ranges 610 * 611 * [0, 12k)[12k, 24k)[24k, 36k)[36k, 40k)[40k,64k) 612 * 613 * And then we'll drop: 614 * 615 * [8k, 12k) - test the single front split 616 * [12k, 20k) - test the single back split 617 * [28k, 32k) - test the double split 618 * [32k, 64k) - test whole em dropping 619 * 620 * They'll have the EXTENT_FLAG_COMPRESSED flag set to keep the em tree from 621 * merging the em's. 622 */ 623 static int test_case_5(struct btrfs_fs_info *fs_info, struct btrfs_inode *inode) 624 { 625 u64 start, end; 626 int ret; 627 int ret2; 628 629 test_msg("Running btrfs_drop_extent_map_range tests"); 630 631 /* [0, 12k) */ 632 ret = add_compressed_extent(inode, 0, SZ_4K * 3, 0); 633 if (ret) { 634 test_err("cannot add extent range [0, 12K)"); 635 goto out; 636 } 637 638 /* [12k, 24k) */ 639 ret = add_compressed_extent(inode, SZ_4K * 3, SZ_4K * 3, SZ_4K); 640 if (ret) { 641 test_err("cannot add extent range [12k, 24k)"); 642 goto out; 643 } 644 645 /* [24k, 36k) */ 646 ret = add_compressed_extent(inode, SZ_4K * 6, SZ_4K * 3, SZ_8K); 647 if (ret) { 648 test_err("cannot add extent range [12k, 24k)"); 649 goto out; 650 } 651 652 /* [36k, 40k) */ 653 ret = add_compressed_extent(inode, SZ_32K + SZ_4K, SZ_4K, SZ_4K * 3); 654 if (ret) { 655 test_err("cannot add extent range [12k, 24k)"); 656 goto out; 657 } 658 659 /* [40k, 64k) */ 660 ret = add_compressed_extent(inode, SZ_4K * 10, SZ_4K * 6, SZ_16K); 661 if (ret) { 662 test_err("cannot add extent range [12k, 24k)"); 663 goto out; 664 } 665 666 /* Drop [8k, 12k) */ 667 start = SZ_8K; 668 end = (3 * SZ_4K) - 1; 669 btrfs_drop_extent_map_range(inode, start, end, false); 670 ret = validate_range(&inode->extent_tree, 0); 671 if (ret) 672 goto out; 673 674 /* Drop [12k, 20k) */ 675 start = SZ_4K * 3; 676 end = SZ_16K + SZ_4K - 1; 677 btrfs_drop_extent_map_range(inode, start, end, false); 678 ret = validate_range(&inode->extent_tree, 1); 679 if (ret) 680 goto out; 681 682 /* Drop [28k, 32k) */ 683 start = SZ_32K - SZ_4K; 684 end = SZ_32K - 1; 685 btrfs_drop_extent_map_range(inode, start, end, false); 686 ret = validate_range(&inode->extent_tree, 2); 687 if (ret) 688 goto out; 689 690 /* Drop [32k, 64k) */ 691 start = SZ_32K; 692 end = SZ_64K - 1; 693 btrfs_drop_extent_map_range(inode, start, end, false); 694 ret = validate_range(&inode->extent_tree, 3); 695 if (ret) 696 goto out; 697 out: 698 ret2 = free_extent_map_tree(inode); 699 if (ret == 0) 700 ret = ret2; 701 702 return ret; 703 } 704 705 /* 706 * Test the btrfs_add_extent_mapping helper which will attempt to create an em 707 * for areas between two existing ems. Validate it doesn't do this when there 708 * are two unmerged em's side by side. 709 */ 710 static int test_case_6(struct btrfs_fs_info *fs_info, struct btrfs_inode *inode) 711 { 712 struct extent_map_tree *em_tree = &inode->extent_tree; 713 struct extent_map *em = NULL; 714 int ret; 715 int ret2; 716 717 ret = add_compressed_extent(inode, 0, SZ_4K, 0); 718 if (ret) 719 goto out; 720 721 ret = add_compressed_extent(inode, SZ_4K, SZ_4K, 0); 722 if (ret) 723 goto out; 724 725 em = btrfs_alloc_extent_map(); 726 if (!em) { 727 test_std_err(TEST_ALLOC_EXTENT_MAP); 728 ret = -ENOMEM; 729 goto out; 730 } 731 732 em->start = SZ_4K; 733 em->len = SZ_4K; 734 em->disk_bytenr = SZ_16K; 735 em->disk_num_bytes = SZ_16K; 736 em->ram_bytes = SZ_16K; 737 write_lock(&em_tree->lock); 738 ret = btrfs_add_extent_mapping(inode, &em, 0, SZ_8K); 739 write_unlock(&em_tree->lock); 740 741 if (ret != 0) { 742 test_err("got an error when adding our em: %d", ret); 743 goto out; 744 } 745 746 ret = -EINVAL; 747 if (em->start != 0) { 748 test_err("unexpected em->start at %llu, wanted 0", em->start); 749 goto out; 750 } 751 if (em->len != SZ_4K) { 752 test_err("unexpected em->len %llu, expected 4K", em->len); 753 goto out; 754 } 755 ret = 0; 756 out: 757 btrfs_free_extent_map(em); 758 ret2 = free_extent_map_tree(inode); 759 if (ret == 0) 760 ret = ret2; 761 762 return ret; 763 } 764 765 /* 766 * Regression test for btrfs_drop_extent_map_range. Calling with skip_pinned == 767 * true would mess up the start/end calculations and subsequent splits would be 768 * incorrect. 769 */ 770 static int test_case_7(struct btrfs_fs_info *fs_info, struct btrfs_inode *inode) 771 { 772 struct extent_map_tree *em_tree = &inode->extent_tree; 773 struct extent_map *em; 774 int ret; 775 int ret2; 776 777 test_msg("Running btrfs_drop_extent_cache with pinned"); 778 779 em = btrfs_alloc_extent_map(); 780 if (!em) { 781 test_std_err(TEST_ALLOC_EXTENT_MAP); 782 return -ENOMEM; 783 } 784 785 /* [0, 16K), pinned */ 786 em->start = 0; 787 em->len = SZ_16K; 788 em->disk_bytenr = 0; 789 em->disk_num_bytes = SZ_4K; 790 em->ram_bytes = SZ_16K; 791 em->flags |= (EXTENT_FLAG_PINNED | EXTENT_FLAG_COMPRESS_ZLIB); 792 write_lock(&em_tree->lock); 793 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 794 write_unlock(&em_tree->lock); 795 if (ret < 0) { 796 test_err("couldn't add extent map"); 797 goto out; 798 } 799 btrfs_free_extent_map(em); 800 801 em = btrfs_alloc_extent_map(); 802 if (!em) { 803 test_std_err(TEST_ALLOC_EXTENT_MAP); 804 ret = -ENOMEM; 805 goto out; 806 } 807 808 /* [32K, 48K), not pinned */ 809 em->start = SZ_32K; 810 em->len = SZ_16K; 811 em->disk_bytenr = SZ_32K; 812 em->disk_num_bytes = SZ_16K; 813 em->ram_bytes = SZ_16K; 814 write_lock(&em_tree->lock); 815 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 816 write_unlock(&em_tree->lock); 817 if (ret < 0) { 818 test_err("couldn't add extent map"); 819 goto out; 820 } 821 btrfs_free_extent_map(em); 822 823 /* 824 * Drop [0, 36K) This should skip the [0, 4K) extent and then split the 825 * [32K, 48K) extent. 826 */ 827 btrfs_drop_extent_map_range(inode, 0, (36 * SZ_1K) - 1, true); 828 829 /* Make sure our extent maps look sane. */ 830 ret = -EINVAL; 831 832 em = btrfs_lookup_extent_mapping(em_tree, 0, SZ_16K); 833 if (!em) { 834 test_err("didn't find an em at 0 as expected"); 835 goto out; 836 } 837 838 if (em->start != 0) { 839 test_err("em->start is %llu, expected 0", em->start); 840 goto out; 841 } 842 843 if (em->len != SZ_16K) { 844 test_err("em->len is %llu, expected 16K", em->len); 845 goto out; 846 } 847 848 btrfs_free_extent_map(em); 849 850 read_lock(&em_tree->lock); 851 em = btrfs_lookup_extent_mapping(em_tree, SZ_16K, SZ_16K); 852 read_unlock(&em_tree->lock); 853 if (em) { 854 test_err("found an em when we weren't expecting one"); 855 goto out; 856 } 857 858 read_lock(&em_tree->lock); 859 em = btrfs_lookup_extent_mapping(em_tree, SZ_32K, SZ_16K); 860 read_unlock(&em_tree->lock); 861 if (!em) { 862 test_err("didn't find an em at 32K as expected"); 863 goto out; 864 } 865 866 if (em->start != (36 * SZ_1K)) { 867 test_err("em->start is %llu, expected 36K", em->start); 868 goto out; 869 } 870 871 if (em->len != (12 * SZ_1K)) { 872 test_err("em->len is %llu, expected 12K", em->len); 873 goto out; 874 } 875 876 if (btrfs_extent_map_block_start(em) != SZ_32K + SZ_4K) { 877 test_err("em->block_start is %llu, expected 36K", 878 btrfs_extent_map_block_start(em)); 879 goto out; 880 } 881 882 btrfs_free_extent_map(em); 883 884 read_lock(&em_tree->lock); 885 em = btrfs_lookup_extent_mapping(em_tree, 48 * SZ_1K, (u64)-1); 886 read_unlock(&em_tree->lock); 887 if (em) { 888 test_err("found an unexpected em above 48K"); 889 goto out; 890 } 891 892 ret = 0; 893 out: 894 btrfs_free_extent_map(em); 895 /* Unpin our extent to prevent warning when removing it below. */ 896 ret2 = btrfs_unpin_extent_cache(inode, 0, SZ_16K, 0); 897 if (ret == 0) 898 ret = ret2; 899 ret2 = free_extent_map_tree(inode); 900 if (ret == 0) 901 ret = ret2; 902 903 return ret; 904 } 905 906 /* 907 * Test a regression for compressed extent map adjustment when we attempt to 908 * add an extent map that is partially overlapped by another existing extent 909 * map. The resulting extent map offset was left unchanged despite having 910 * incremented its start offset. 911 */ 912 static int test_case_8(struct btrfs_fs_info *fs_info, struct btrfs_inode *inode) 913 { 914 struct extent_map_tree *em_tree = &inode->extent_tree; 915 struct extent_map *em; 916 int ret; 917 int ret2; 918 919 em = btrfs_alloc_extent_map(); 920 if (!em) { 921 test_std_err(TEST_ALLOC_EXTENT_MAP); 922 return -ENOMEM; 923 } 924 925 /* Compressed extent for the file range [120K, 128K). */ 926 em->start = SZ_1K * 120; 927 em->len = SZ_8K; 928 em->disk_num_bytes = SZ_4K; 929 em->ram_bytes = SZ_8K; 930 em->flags |= EXTENT_FLAG_COMPRESS_ZLIB; 931 write_lock(&em_tree->lock); 932 ret = btrfs_add_extent_mapping(inode, &em, em->start, em->len); 933 write_unlock(&em_tree->lock); 934 btrfs_free_extent_map(em); 935 if (ret < 0) { 936 test_err("couldn't add extent map for range [120K, 128K)"); 937 goto out; 938 } 939 940 em = btrfs_alloc_extent_map(); 941 if (!em) { 942 test_std_err(TEST_ALLOC_EXTENT_MAP); 943 ret = -ENOMEM; 944 goto out; 945 } 946 947 /* 948 * Compressed extent for the file range [108K, 144K), which overlaps 949 * with the [120K, 128K) we previously inserted. 950 */ 951 em->start = SZ_1K * 108; 952 em->len = SZ_1K * 36; 953 em->disk_num_bytes = SZ_4K; 954 em->ram_bytes = SZ_1K * 36; 955 em->flags |= EXTENT_FLAG_COMPRESS_ZLIB; 956 957 /* 958 * Try to add the extent map but with a search range of [140K, 144K), 959 * this should succeed and adjust the extent map to the range 960 * [128K, 144K), with a length of 16K and an offset of 20K. 961 * 962 * This simulates a scenario where in the subvolume tree of an inode we 963 * have a compressed file extent item for the range [108K, 144K) and we 964 * have an overlapping compressed extent map for the range [120K, 128K), 965 * which was created by an encoded write, but its ordered extent was not 966 * yet completed, so the subvolume tree doesn't have yet the file extent 967 * item for that range - we only have the extent map in the inode's 968 * extent map tree. 969 */ 970 write_lock(&em_tree->lock); 971 ret = btrfs_add_extent_mapping(inode, &em, SZ_1K * 140, SZ_4K); 972 write_unlock(&em_tree->lock); 973 btrfs_free_extent_map(em); 974 if (ret < 0) { 975 test_err("couldn't add extent map for range [108K, 144K)"); 976 goto out; 977 } 978 979 if (em->start != SZ_128K) { 980 test_err("unexpected extent map start %llu (should be 128K)", em->start); 981 ret = -EINVAL; 982 goto out; 983 } 984 if (em->len != SZ_16K) { 985 test_err("unexpected extent map length %llu (should be 16K)", em->len); 986 ret = -EINVAL; 987 goto out; 988 } 989 if (em->offset != SZ_1K * 20) { 990 test_err("unexpected extent map offset %llu (should be 20K)", em->offset); 991 ret = -EINVAL; 992 goto out; 993 } 994 out: 995 ret2 = free_extent_map_tree(inode); 996 if (ret == 0) 997 ret = ret2; 998 999 return ret; 1000 } 1001 1002 struct rmap_test_vector { 1003 u64 raid_type; 1004 u64 physical_start; 1005 u64 data_stripe_size; 1006 u64 num_data_stripes; 1007 u64 num_stripes; 1008 /* Assume we won't have more than 5 physical stripes */ 1009 u64 data_stripe_phys_start[5]; 1010 bool expected_mapped_addr; 1011 /* Physical to logical addresses */ 1012 u64 mapped_logical[5]; 1013 }; 1014 1015 static int test_rmap_block(struct btrfs_fs_info *fs_info, 1016 struct rmap_test_vector *test) 1017 { 1018 struct btrfs_chunk_map *map; 1019 u64 AUTO_KFREE(logical); 1020 int i, out_ndaddrs, out_stripe_len; 1021 int ret; 1022 1023 map = btrfs_alloc_chunk_map(test->num_stripes, GFP_KERNEL); 1024 if (!map) { 1025 test_std_err(TEST_ALLOC_CHUNK_MAP); 1026 return -ENOMEM; 1027 } 1028 1029 /* Start at 4GiB logical address */ 1030 map->start = SZ_4G; 1031 map->chunk_len = test->data_stripe_size * test->num_data_stripes; 1032 map->stripe_size = test->data_stripe_size; 1033 map->num_stripes = test->num_stripes; 1034 map->type = test->raid_type; 1035 1036 for (i = 0; i < map->num_stripes; i++) { 1037 struct btrfs_device *dev = btrfs_alloc_dummy_device(fs_info); 1038 1039 if (IS_ERR(dev)) { 1040 test_err("cannot allocate device"); 1041 ret = PTR_ERR(dev); 1042 goto out; 1043 } 1044 map->stripes[i].dev = dev; 1045 map->stripes[i].physical = test->data_stripe_phys_start[i]; 1046 } 1047 1048 ret = btrfs_add_chunk_map(fs_info, map); 1049 if (ret) { 1050 test_err("error adding chunk map to mapping tree"); 1051 btrfs_free_chunk_map(map); 1052 return ret; 1053 } 1054 1055 ret = btrfs_rmap_block(fs_info, map->start, btrfs_sb_offset(1), 1056 &logical, &out_ndaddrs, &out_stripe_len); 1057 if (ret || (out_ndaddrs == 0 && test->expected_mapped_addr)) { 1058 test_err("didn't rmap anything but expected %d", 1059 test->expected_mapped_addr); 1060 goto out; 1061 } 1062 1063 if (out_stripe_len != BTRFS_STRIPE_LEN) { 1064 test_err("calculated stripe length doesn't match"); 1065 ret = -EINVAL; 1066 goto out; 1067 } 1068 1069 if (out_ndaddrs != test->expected_mapped_addr) { 1070 for (i = 0; i < out_ndaddrs; i++) 1071 test_msg("mapped %llu", logical[i]); 1072 test_err("unexpected number of mapped addresses: %d", out_ndaddrs); 1073 ret = -EINVAL; 1074 goto out; 1075 } 1076 1077 for (i = 0; i < out_ndaddrs; i++) { 1078 if (logical[i] != test->mapped_logical[i]) { 1079 test_err("unexpected logical address mapped"); 1080 ret = -EINVAL; 1081 goto out; 1082 } 1083 } 1084 1085 ret = 0; 1086 out: 1087 btrfs_remove_chunk_map(fs_info, map); 1088 return ret; 1089 } 1090 1091 int btrfs_test_extent_map(void) 1092 { 1093 struct btrfs_fs_info *fs_info = NULL; 1094 struct inode *inode; 1095 struct btrfs_root *root = NULL; 1096 int ret = 0, i; 1097 struct rmap_test_vector rmap_tests[] = { 1098 { 1099 /* 1100 * Test a chunk with 2 data stripes one of which 1101 * intersects the physical address of the super block 1102 * is correctly recognized. 1103 */ 1104 .raid_type = BTRFS_BLOCK_GROUP_RAID1, 1105 .physical_start = SZ_64M - SZ_4M, 1106 .data_stripe_size = SZ_256M, 1107 .num_data_stripes = 2, 1108 .num_stripes = 2, 1109 .data_stripe_phys_start = 1110 {SZ_64M - SZ_4M, SZ_64M - SZ_4M + SZ_256M}, 1111 .expected_mapped_addr = true, 1112 .mapped_logical= {SZ_4G + SZ_4M} 1113 }, 1114 { 1115 /* 1116 * Test that out-of-range physical addresses are 1117 * ignored 1118 */ 1119 1120 /* SINGLE chunk type */ 1121 .raid_type = 0, 1122 .physical_start = SZ_4G, 1123 .data_stripe_size = SZ_256M, 1124 .num_data_stripes = 1, 1125 .num_stripes = 1, 1126 .data_stripe_phys_start = {SZ_256M}, 1127 .expected_mapped_addr = false, 1128 .mapped_logical = {0} 1129 } 1130 }; 1131 1132 test_msg("running extent_map tests"); 1133 1134 /* 1135 * Note: the fs_info is not set up completely, we only need 1136 * fs_info::fsid for the tracepoint. 1137 * 1138 * And all the immediate numbers are based on 4K blocksize, 1139 * thus we have to use 4K as sectorsize no matter the page size. 1140 */ 1141 fs_info = btrfs_alloc_dummy_fs_info(SZ_4K, SZ_4K); 1142 if (!fs_info) { 1143 test_std_err(TEST_ALLOC_FS_INFO); 1144 return -ENOMEM; 1145 } 1146 1147 inode = btrfs_new_test_inode(); 1148 if (!inode) { 1149 test_std_err(TEST_ALLOC_INODE); 1150 ret = -ENOMEM; 1151 goto out; 1152 } 1153 1154 root = btrfs_alloc_dummy_root(fs_info); 1155 if (IS_ERR(root)) { 1156 test_std_err(TEST_ALLOC_ROOT); 1157 ret = PTR_ERR(root); 1158 root = NULL; 1159 goto out; 1160 } 1161 1162 BTRFS_I(inode)->root = root; 1163 1164 ret = test_case_1(fs_info, BTRFS_I(inode)); 1165 if (ret) 1166 goto out; 1167 ret = test_case_2(fs_info, BTRFS_I(inode)); 1168 if (ret) 1169 goto out; 1170 ret = test_case_3(fs_info, BTRFS_I(inode)); 1171 if (ret) 1172 goto out; 1173 ret = test_case_4(fs_info, BTRFS_I(inode)); 1174 if (ret) 1175 goto out; 1176 ret = test_case_5(fs_info, BTRFS_I(inode)); 1177 if (ret) 1178 goto out; 1179 ret = test_case_6(fs_info, BTRFS_I(inode)); 1180 if (ret) 1181 goto out; 1182 ret = test_case_7(fs_info, BTRFS_I(inode)); 1183 if (ret) 1184 goto out; 1185 ret = test_case_8(fs_info, BTRFS_I(inode)); 1186 if (ret) 1187 goto out; 1188 1189 test_msg("running rmap tests"); 1190 for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) { 1191 ret = test_rmap_block(fs_info, &rmap_tests[i]); 1192 if (ret) 1193 goto out; 1194 } 1195 1196 out: 1197 iput(inode); 1198 btrfs_free_dummy_root(root); 1199 btrfs_free_dummy_fs_info(fs_info); 1200 1201 return ret; 1202 } 1203