From patchwork Wed Jul 25 08:18:21 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Misono Tomohiro X-Patchwork-Id: 10543675 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork-2.web.codeaurora.org (Postfix) with ESMTP id 23E84157A for ; Wed, 25 Jul 2018 08:19:11 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 140B429AF8 for ; Wed, 25 Jul 2018 08:19:11 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 08A6A29AFC; Wed, 25 Jul 2018 08:19:11 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-7.9 required=2.0 tests=BAYES_00,MAILING_LIST_MULTI, RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 70F9C29AF8 for ; Wed, 25 Jul 2018 08:19:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1728645AbeGYJ3m (ORCPT ); Wed, 25 Jul 2018 05:29:42 -0400 Received: from mgwym04.jp.fujitsu.com ([211.128.242.43]:60658 "EHLO mgwym04.jp.fujitsu.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1728222AbeGYJ3m (ORCPT ); Wed, 25 Jul 2018 05:29:42 -0400 Received: from yt-mxoi1.gw.nic.fujitsu.com (unknown [192.168.229.67]) by mgwym04.jp.fujitsu.com with smtp id 0179_5265_450dd7eb_5cc8_4a0b_9a30_b738d2ee1e54; Wed, 25 Jul 2018 17:19:03 +0900 Received: from g01jpfmpwkw01.exch.g01.fujitsu.local (g01jpfmpwkw01.exch.g01.fujitsu.local [10.0.193.38]) by yt-mxoi1.gw.nic.fujitsu.com (Postfix) with ESMTP id B35D2AC0210 for ; Wed, 25 Jul 2018 17:19:02 +0900 (JST) Received: from G01JPEXCHKW15.g01.fujitsu.local (G01JPEXCHKW15.g01.fujitsu.local [10.0.194.54]) by g01jpfmpwkw01.exch.g01.fujitsu.local (Postfix) with ESMTP id 0D064692707 for ; Wed, 25 Jul 2018 17:19:02 +0900 (JST) X-SecurityPolicyCheck: OK by SHieldMailChecker v2.5.2 X-SHieldMailCheckerPolicyVersion: FJ-ISEC-20170217-enc X-SHieldMailCheckerMailID: c70661f461374d518f37d37403cd9ccd From: Misono Tomohiro Subject: [PATCH] btrfs: backref: Do not return duplicate refs from find_parent_nodes() To: linux-btrfs Message-ID: Date: Wed, 25 Jul 2018 17:18:21 +0900 User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.9.1 MIME-Version: 1.0 Content-Language: en-US X-SecurityPolicyCheck-GC: OK by FENCE-Mail X-TM-AS-MML: disable Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP In some case, "btrfs inspect-internal logical-resolve" returns duplicate entries for given logical address: [Example] ===== // create a file sharing the exactly same extent $ dd if=/dev/urandom of=/mnt/file bs=4k count=1 $ sync $ cloner -s 0 -d 4096 -l 4096 /mnt/file /mnt/file // cloner from xfstest $ sync $ filefrag -v Filesystem type is: 9123683e File size of /mnt/file is 8192 (2 blocks of 4096 bytes) ext: logical_offset: physical_offset: length: expected: flags: 0: 0.. 0: 3410.. 3410: 1: shared 1: 1.. 1: 3410.. 3410: 1: 3411: last,shared,eof /mnt/file 2 extents found // there are two backrefs $ btrfs inspect-internal dump-tree $DEV | grep -A 3 "$((3410*4096)) EXTENT_ITEM" item 12 key (13967360 EXTENT_ITEM 4096) itemoff 15449 itemsize 82 refs 2 gen 250 flags DATA extent data backref root FS_TREE objectid 268 offset 4096 count 1 extent data backref root FS_TREE objectid 268 offset 0 count 1 $ btrfs inspect-internal logical-resolve -P $((3410*4096)) /mnt inode 268 offset 4096 root 5 inode 268 offset 0 root 5 inode 268 offset 4096 root 5 // Duplicate (Or, see 004.full of xfstest for more complex case.) ===== This problem is related to resolving indirect ref. Related call stack is as below: btrfs_ioctl_logical_to_ino() - iterate_extent_inodes_from_logical() - extent_from_logical() - iterate_extent_inodes() - btrfs_find_all_leafs() - find_parent_nodes() // collect ref and root info - add_delayed_refs() - add_inline_refs() - resolve_indirect_refs() - resolve_indirect_ref() - add_all_parents() In above example, two indirect backrefs of EXTENT_DATA ((268 EXTENT_DATA 0), (268 EXTENT_DATA 4096)) will be added in rb_tree (descending order) in add_inline_refs(). They will be resolved in add_all_parents() in the end. However, add_all_parents() will search all EXTENT_DATA item of the root larger than the given offset which point to the target extent position each time. This is needed since backref may be referenced several time within a file (e.g. when extent is split), but could make duplicate entries. So, in above case, (268 EXTENT_DATA 4096) returns "inode 268 offset 4096 root 5" and (268 EXTENT_DATA 0) returns "inode 268 offset 4096 root 0" and "inode 268 offset 4096 root 5". Fix this problem by only searching the key with the lowest offset when ref's rootid and key objectid is the same. In order to this, sort entry in rb_tree ascending order (by swapping argument order in prelim_ref_compare() in prelim_ref_insert()) and skip call of resolve_indirect_ref() when rootid/key objectid matches the previous search. With this patch, logical-resolve will return correct entries: $ btrfs inspect-internal logical-resolve -P $((3410*4096)) /mnt inode 268 offset 0 root 5 inode 268 offset 4096 root 5 Note that find_parent_nodes() is also used in some other places, but they should not be affected by this patch as stated below: - send/scrub (through iterate_extent_inodes()) - can work correctly with or without duplicate refs - qgroup (through btrfs_find_all_roots()) - use only root info and not ref - snapshot aware defrag (through iterate_extent_inodes_from_logical()) - currently dead code and not used Signed-off-by: Misono Tomohiro --- fs/btrfs/backref.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/fs/btrfs/backref.c b/fs/btrfs/backref.c index 60f4afa8ecbc..7ce0b5f9e99e 100644 --- a/fs/btrfs/backref.c +++ b/fs/btrfs/backref.c @@ -237,7 +237,7 @@ static void prelim_ref_insert(const struct btrfs_fs_info *fs_info, while (*p) { parent = *p; ref = rb_entry(parent, struct prelim_ref, rbnode); - result = prelim_ref_compare(ref, newref); + result = prelim_ref_compare(newref, ref); if (result < 0) { p = &(*p)->rb_left; } else if (result > 0) { @@ -612,6 +612,8 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, { int err; int ret = 0; + u64 prev_rootid = 0; + u64 prev_objectid = 0; struct ulist *parents; struct ulist_node *node; struct ulist_iterator uiter; @@ -640,10 +642,14 @@ static int resolve_indirect_refs(struct btrfs_fs_info *fs_info, rb_erase(&ref->rbnode, &preftrees->indirect.root); preftrees->indirect.count--; - if (ref->count == 0) { + if (ref->count == 0 || + (prev_rootid == ref->root_id && + prev_objectid == ref->key_for_search.objectid)) { free_pref(ref); continue; } + prev_rootid = ref->root_id; + prev_objectid = ref->key_for_search.objectid; if (sc && sc->root_objectid && ref->root_id != sc->root_objectid) {