1. 13 Dec, 2019 2 commits
    • Filipe Manana's avatar
      Btrfs: make tree checker detect checksum items with overlapping ranges · ad1d8c43
      Filipe Manana authored
      Having checksum items, either on the checksums tree or in a log tree, that
      represent ranges that overlap each other is a sign of a corruption. Such
      case confuses the checksum lookup code and can result in not being able to
      find checksums or find stale checksums.
      
      So add a check for such case.
      
      This is motivated by a recent fix for a case where a log tree had checksum
      items covering ranges that overlap each other due to extent cloning, and
      resulted in missing checksums after replaying the log tree. It also helps
      detect past issues such as stale and outdated checksums due to overlapping,
      commit 27b9a812
      
       ("Btrfs: fix csum tree corruption, duplicate and
      outdated checksums").
      
      CC: stable@vger.kernel.org # 4.4+
      Signed-off-by: default avatarFilipe Manana <fdmanana@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      ad1d8c43
    • Andreas Färber's avatar
      btrfs: tree-checker: Fix error format string for size_t · 994bf9cd
      Andreas Färber authored
      Argument BTRFS_FILE_EXTENT_INLINE_DATA_START is defined as offsetof(),
      which returns type size_t, so we need %zu instead of %lu.
      
      This fixes a build warning on 32-bit ARM:
      
        ../fs/btrfs/tree-checker.c: In function 'check_extent_data_item':
        ../fs/btrfs/tree-checker.c:230:43: warning: format '%lu' expects argument of type 'long unsigned int', but argument 5 has type 'unsigned int' [-Wformat=]
          230 |     "invalid item size, have %u expect [%lu, %u)",
              |                                         ~~^
              |                                           long unsigned int
              |                                         %u
      
      Fixes: 153a6d29
      
       ("btrfs: tree-checker: Check item size before reading file extent type")
      Acked-by: default avatarGeert Uytterhoeven <geert@linux-m68k.org>
      Signed-off-by: Andreas Färber's avatarAndreas Färber <afaerber@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      994bf9cd
  2. 18 Nov, 2019 8 commits
  3. 25 Oct, 2019 1 commit
    • Qu Wenruo's avatar
      btrfs: tree-checker: Fix wrong check on max devid · 8bb177d1
      Qu Wenruo authored
      
      
      [BUG]
      The following script will cause false alert on devid check.
        #!/bin/bash
      
        dev1=/dev/test/test
        dev2=/dev/test/scratch1
        mnt=/mnt/btrfs
      
        umount $dev1 &> /dev/null
        umount $dev2 &> /dev/null
        umount $mnt &> /dev/null
      
        mkfs.btrfs -f $dev1
      
        mount $dev1 $mnt
      
        _fail()
        {
                echo "!!! FAILED !!!"
                exit 1
        }
      
        for ((i = 0; i < 4096; i++)); do
                btrfs dev add -f $dev2 $mnt || _fail
                btrfs dev del $dev1 $mnt || _fail
                dev_tmp=$dev1
                dev1=$dev2
                dev2=$dev_tmp
        done
      
      [CAUSE]
      Tree-checker uses BTRFS_MAX_DEVS() and BTRFS_MAX_DEVS_SYS_CHUNK() as
      upper limit for devid.  But we can have devid holes just like above
      script.
      
      So the check for devid is incorrect and could cause false alert.
      
      [FIX]
      Just remove the whole devid check.  We don't have any hard requirement
      for devid assignment.
      
      Furthermore, even devid could get corrupted by a bitflip, we still have
      dev extents verification at mount time, so corrupted data won't sneak
      in.
      
      This fixes fstests btrfs/194.
      Reported-by: default avatarAnand Jain <anand.jain@oracle.com>
      Fixes: ab4ba2e1
      
       ("btrfs: tree-checker: Verify dev item")
      CC: stable@vger.kernel.org # 5.2+
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      8bb177d1
  4. 09 Sep, 2019 5 commits
    • Qu Wenruo's avatar
      btrfs: Detect unbalanced tree with empty leaf before crashing btree operations · 62fdaa52
      Qu Wenruo authored
      [BUG]
      With crafted image, btrfs will panic at btree operations:
      
        kernel BUG at fs/btrfs/ctree.c:3894!
        invalid opcode: 0000 [#1] SMP PTI
        CPU: 0 PID: 1138 Comm: btrfs-transacti Not tainted 5.0.0-rc8+ #9
        RIP: 0010:__push_leaf_left+0x6b6/0x6e0
        RSP: 0018:ffffc0bd4128b990 EFLAGS: 00010246
        RAX: 0000000000000000 RBX: ffffa0a4ab8f0e38 RCX: 0000000000000000
        RDX: ffffa0a280000000 RSI: 0000000000000000 RDI: ffffa0a4b3814000
        RBP: ffffc0bd4128ba38 R08: 0000000000001000 R09: ffffc0bd4128b948
        R10: 0000000000000000 R11: 0000000000000000 R12: 0000000000000240
        R13: ffffa0a4b556fb60 R14: ffffa0a4ab8f0af0 R15: ffffa0a4ab8f0af0
        FS: 0000000000000000(0000) GS:ffffa0a4b7a00000(0000) knlGS:0000000000000000
        CS: 0010 DS: 0000 ES: 0000 CR0: 0000000080050033
        CR2: 00007f2461c80020 CR3: 000000022b32a006 CR4: 00000000000206f0
        Call Trace:
        ? _cond_resched+0x1a/0x50
        push_leaf_left+0x179/0x190
        btrfs_del_items+0x316/0x470
        btrfs_del_csums+0x215/0x3a0
        __btrfs_free_extent.isra.72+0x5a7/0xbe0
        __btrfs_run_delayed_refs+0x539/0x1120
        btrfs_run_delayed_refs+0xdb/0x1b0
        btrfs_commit_transaction+0x52/0x950
        ? start_transaction+0x94/0x450
        transaction_kthread+0x163/0x190
        kthread+0x105/0x140
        ? btrfs_cleanup_transaction+0x560/0x560
        ? kthread_destroy_worker+0x50/0x50
        ret_from_fork+0x35/0x40
        Modules linked in:
        ---[ end trace c2425e6e89b5558f ]---
      
      [CAUSE]
      The offending csum tree looks like this:
      
        checksum tree key (CSUM_TREE ROOT_ITEM 0)
        node 29741056 level 1 items 14 free 107 generation 19 owner CSUM_TREE
      	  ...
      	  key (EXTENT_CSUM EXTENT_CSUM 85975040) block 29630464 gen 17
      	  key (EXTENT_CSUM EXTENT_CSUM 89911296) block 29642752 gen 17 <<<
      	  key (EXTENT_CSUM EXTENT_CSUM 92274688) block 29646848 gen 17
      	  ...
      
        leaf 29630464 items 6 free space 1 generation 17 owner CSUM_TREE
      	  item 0 key (EXTENT_CSUM EXTENT_CSUM 85975040) itemoff 3987 itemsize 8
      		  range start 85975040 end 85983232 length 8192
      	  ...
        leaf 29642752 items 0 free space 3995 generation 17 owner 0
      		      ^ empty leaf            invalid owner ^
      
        leaf 29646848 items 1 free space 602 generation 17 owner CSUM_TREE
      	  item 0 key (EXTENT_CSUM EXTENT_CSUM 92274688) itemoff 627 itemsize 3368
      		  range start 92274688 end 95723520 length 3448832
      
      So we have a corrupted csum tree where one tree leaf is completely
      empty, causing unbalanced btree, thus leading to unexpected btree
      balance error.
      
      [FIX]
      For this particular case, we handle it in two directions to catch it:
      - Check if the tree block is empty through btrfs_verify_level_key()
        So that invalid tree blocks won't be read out through
        btrfs_search_slot() and its variants.
      
      - Check 0 tree owner in tree checker
        NO tree is using 0 as its tree owner, detect it and reject at tree
        block read time.
      
      Bugzilla: https://bugzilla.kernel.org/show_bug.cgi?id=202821
      
      Reviewed-by: default avatarNikolay Borisov <nborisov@suse.com>
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      62fdaa52
    • Qu Wenruo's avatar
      btrfs: tree-checker: Add EXTENT_DATA_REF check · 0785a9aa
      Qu Wenruo authored
      
      
      EXTENT_DATA_REF is a little like DIR_ITEM which contains hash in its
      key->offset.
      
      This patch will check the following contents:
      - Key->objectid
        Basic alignment check.
      
      - Hash
        Hash of each extent_data_ref item must match key->offset.
      
      - Offset
        Basic alignment check.
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      0785a9aa
    • Qu Wenruo's avatar
      btrfs: tree-checker: Add simple keyed refs check · e2406a6f
      Qu Wenruo authored
      
      
      For TREE_BLOCK_REF, SHARED_DATA_REF and SHARED_BLOCK_REF we need to
      check:
                    | TREE_BLOCK_REF | SHARED_BLOCK_REF | SHARED_BLOCK_REF
      --------------+----------------+-----------------+------------------
      key->objectid |    Alignment   |     Alignment    |    Alignment
      key->offset   |    Any value   |     Alignment    |    Alignment
      item_size     |        0       |        0         |   sizeof(le32) (*)
      
      *: sizeof(struct btrfs_shared_data_ref)
      
      So introduce a check to check all these 3 key types together.
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      e2406a6f
    • Qu Wenruo's avatar
      btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check · f82d1c7c
      Qu Wenruo authored
      
      
      This patch introduces the ability to check extent items.
      
      This check involves:
      - key->objectid check
        Basic alignment check.
      
      - key->type check
        Against btrfs_extent_item::type and SKINNY_METADATA feature.
      
      - key->offset alignment check for EXTENT_ITEM
      
      - key->offset check for METADATA_ITEM
      
      - item size check
        Both against minimal size and stepping check.
      
      - btrfs_extent_item check
        Checks its flags and generation.
      
      - btrfs_extent_inline_ref checks
        Against 4 types inline ref.
        Checks bytenr alignment and tree level.
      
      - btrfs_extent_item::refs check
        Check against total refs found in inline refs.
      
      This check would be the most complex single item check due to its nature
      of inlined items.
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      f82d1c7c
    • Qu Wenruo's avatar
      btrfs: tree-checker: Add ROOT_ITEM check · 259ee775
      Qu Wenruo authored
      This patch will introduce ROOT_ITEM check, which includes:
      - Key->objectid and key->offset check
        Currently only some easy check, e.g. 0 as rootid is invalid.
      
      - Item size check
        Root item size is fixed.
      
      - Generation checks
        Generation, generation_v2 and last_snapshot should not be greater than
        super generation + 1
      
      - Level and alignment check
        Level should be in [0, 7], and bytenr must be aligned to sector size.
      
      - Flags check
      
      Bugzilla: https://bugzilla.kernel.org/show_bug.cgi?id=203261
      
      Reported-by: default avatarJungyeon Yoon <jungyeon.yoon@gmail.com>
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Reviewed-by: default avatarDavid Sterba <dsterba@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      259ee775
  5. 01 Jul, 2019 1 commit
    • Qu Wenruo's avatar
      btrfs: tree-checker: Check if the file extent end overflows · 4c094c33
      Qu Wenruo authored
      
      
      Under certain conditions, we could have strange file extent item in log
      tree like:
      
        item 18 key (69599 108 397312) itemoff 15208 itemsize 53
      	extent data disk bytenr 0 nr 0
      	extent data offset 0 nr 18446744073709547520 ram 18446744073709547520
      
      The num_bytes + ram_bytes overflow 64 bit type.
      
      For num_bytes part, we can detect such overflow along with file offset
      (key->offset), as file_offset + num_bytes should never go beyond u64.
      
      For ram_bytes part, it's about the decompressed size of the extent, not
      directly related to the size.
      In theory it is OK to have a large value, and put extra limitation
      on RAM bytes may cause unexpected false alerts.
      
      So in tree-checker, we only check if the file offset and num bytes
      overflow.
      Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
      Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>
      4c094c33
  6. 16 May, 2019 1 commit
  7. 29 Apr, 2019 22 commits