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

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