From patchwork Thu Jun 7 03:33:06 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: james harvey X-Patchwork-Id: 10451109 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 956A060375 for ; Thu, 7 Jun 2018 03:33:11 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 841BD29D7B for ; Thu, 7 Jun 2018 03:33:11 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7768529DBC; Thu, 7 Jun 2018 03:33: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.8 required=2.0 tests=BAYES_00, DKIM_ADSP_CUSTOM_MED, DKIM_SIGNED, FREEMAIL_FROM, MAILING_LIST_MULTI, RCVD_IN_DNSWL_HI, T_DKIM_INVALID 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 CBE8429D7B for ; Thu, 7 Jun 2018 03:33:10 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932155AbeFGDdI (ORCPT ); Wed, 6 Jun 2018 23:33:08 -0400 Received: from mail-oi0-f67.google.com ([209.85.218.67]:42481 "EHLO mail-oi0-f67.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752566AbeFGDdH (ORCPT ); Wed, 6 Jun 2018 23:33:07 -0400 Received: by mail-oi0-f67.google.com with SMTP id k190-v6so7280057oib.9 for ; Wed, 06 Jun 2018 20:33:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=2p+841XRFumMf8qt3RJSdMJf6JbUfLiY27TQOFZh4Go=; b=jLzQFic2N072Pu9mvqcB1DQBucE8Zq4ZtO9IM7/C8reEYb8t2tIRr9tRxTHRYI4kYG St4iKrcWgjSHxpCeSZE5ROwejOnQDGvnk/zXkplmmpTTDIQ8dyoGnEFhWUH7J1w0etAc Fz1QY1EpU9ZqOvVPmMzRtv+lRYvMf28sBsKSvnEzEyTfPR1fVq6v27t//QWdkpJG14jd hnn9sgmB3uqNoXG3ZKkkrm91/n1mU3QNYYo7AcoMSi5tuX+Zgeaom7YcE5mppeOPDeC2 wuhoItD5NN4uaKwGUrjgt1GDqH4Y6QHR0atyJy4Zq1OVpTlh5AeIhtQNPJmjIxF3J3FB dAjw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=2p+841XRFumMf8qt3RJSdMJf6JbUfLiY27TQOFZh4Go=; b=SVCzf89FKw1v4qEh38PtOIFIMS6hJcyPpa+XiGNao7c4gy9dMs4we5zUGDQfPVb3JC IrTEzWfmWAPSuMAzlwFmKutGE0fxR97O4OVlSKw8tOk73JqzXDvEa28VrtdmHtZeOQFy Zq8Ue24fOC+AopYiZ52qYtL/ukASAlTNGb/YPuBNUj7OsPrc0YOdTHdsQ/0LKQeSgNmf TYYckpzsQlaKiFv8FVVy+sTAvt+MMOM9ppWzPV99TxSQmE9E25d7kZt2Xv+yHAKQbM0o Z+XOPpiq7GM9Ty7j920RISOMzRzB327/2eXJ6UupWWZgR4YXCcQZ1dZD1krUW+3e+7N0 nk6Q== X-Gm-Message-State: APt69E28vTe+jbwIkHR7XwzzzAretwFK73AhVCqKVH7aSyZymVdI+WPF GFyJ2qiU9OzQY5yVU3zSjgh4xaJD1kd6FGhy3s0ZUg== X-Google-Smtp-Source: ADUXVKIouxQyeBQaEDnm6zjTxsS3N13cdVkubtsLE1symiN2EXUsXytFDSyiWx9uEugCoZFbtmVDH+f2f5B6sivhkkU= X-Received: by 2002:aca:389:: with SMTP id 131-v6mr60644oid.306.1528342386453; Wed, 06 Jun 2018 20:33:06 -0700 (PDT) MIME-Version: 1.0 Received: by 2002:a9d:3535:0:0:0:0:0 with HTTP; Wed, 6 Jun 2018 20:33:06 -0700 (PDT) From: james harvey Date: Wed, 6 Jun 2018 23:33:06 -0400 Message-ID: Subject: [PATCH RFC] btrfs-progs: map-logical: look at next leaf if slot > items To: Btrfs BTRFS 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 goto again; --- 2.17.0 -- To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html =====[ NOTE ]===== I think I found a buffer over-read error that will come up other places, unless EACH caller checks bounds themselves. See "Bonus bug, LEFT FOR READER" below. =====[ PROBLEM ]===== Using btrfs-progs v4.16: No extent found at range [10955980800,10955984896) But, this extent exists. btrfs-debug-tree shows: ... extent tree key (EXTENT_TREE ROOT_ITEM 0) ... leaf 316456960 items 203 free space 3697 generation 84225 owner EXTENT_TREE ... item 197 key (10955931648 EXTENT_ITEM 28672) itemoff 8957 itemsize 37 refs 1 gen 62656 flags DATA shared data backref parent 142622720 count 1 item 198 key (10955960320 EXTENT_ITEM 4096) itemoff 8920 itemsize 37 refs 1 gen 62656 flags DATA shared data backref parent 142622720 count 1 item 199 key (10955964416 EXTENT_ITEM 4096) itemoff 8883 itemsize 37 refs 1 gen 62656 flags DATA shared data backref parent 142622720 count 1 item 200 key (10955968512 EXTENT_ITEM 4096) itemoff 8846 itemsize 37 refs 1 gen 62656 flags DATA shared data backref parent 142622720 count 1 item 201 key (10955972608 EXTENT_ITEM 4096) itemoff 8809 itemsize 37 refs 1 gen 62656 flags DATA shared data backref parent 142655488 count 1 item 202 key (10955976704 EXTENT_ITEM 4096) itemoff 8772 itemsize 37 refs 1 gen 62656 flags DATA shared data backref parent 142655488 count 1 ... leaf 316489728 items 208 free space 3387 generation 84225 owner EXTENT_TREE ... item 0 key (10955980800 EXTENT_ITEM 4096) itemoff 16246 itemsize 37 refs 1 gen 62656 flags DATA shared data backref parent 128958464 count 1 ... checksum tree key (CSUM_TREE ROOT_ITEM 0) ... item 412 key (EXTENT_CSUM EXTENT_CSUM 10955980800) itemoff 10647 itemsize 4 range start 10955980800 end 10955984896 length 4096 .... file tree key (3038 ROOT_ITEM 80009) ... leaf 128958464 items 37 free space 6032 generation 62656 owner FS_TREE ... item 1 key (997645 INODE_ITEM 0) itemoff 15220 itemsize 160 generation 62656 transid 62656 size 4943 nbytes 8192 block group 0 mode 100644 links 1 uid 0 gid 0 rdev 0 sequence 5 flags 0x0(none) atime 1478246492.0 (2016-11-04 08:01:32) ctime 1478246493.129060242 (2016-11-04 08:01:33) mtime 1477487995.0 (2016-10-26 13:19:55) otime 1478246493.129060242 (2016-11-04 08:01:33) item 2 key (997645 INODE_REF 299949) itemoff 15200 itemsize 20 index 13 namelen 10 name: as_map.hpp item 3 key (997645 EXTENT_DATA 0) itemoff 15147 itemsize 53 generation 62656 type 1 (regular) extent data disk byte 10955980800 nr 4096 extent data offset 0 nr 8192 ram 8192 extent compression 2 (lzo) ... =====[ CAUSE ]===== In main's first call to map_one_extent(10955980800, 4096, 0): * btrfs_search_slot() looks for (10955980800, 0, 0), and: ** returns 1 because it doesn't exist ** sets path->slots[0] to 203 (for leaf 316456960), where it should go if inserted (pointing after the last existing item) * ret is reset to 0 * btrfs_item_key_to_cpu sets key to (10955960320, BTRFS_EXTENT_ITEM_KEY, 4096) !!! Bonus bug, LEFT FOR READER. Why is this item #197, 5 items before the 203 given? I think no bounds checking causes a buffer over-read here. btrfs_item_key_to_cpu() calls btrfs_item_key(), which uses the macro read_eb_member() to call read_extent_buffer() which memcpy's using an out of range index, at least for this leaf. * With (!search_forward && key.objectid > logical) being false, the code calling btrfs_next_item() is not run. * logical is set to this too-low key.objectid * !ret, so set *logical_ret and *len_ret with the new values Back in main: * ret is 0, so don't print the first error * ret is still 0, so don't run map_one_extent() with search_forward=1 * At the while loop, (10955960320 + 4096 >= 10955980800 && 10955960320 < 10955980800 + 4096) (10955964416 >= 10955980800 && 10955960320 < 10955984896) (false && true) (false), so don't call map_one_extent() with search_forward=1 here, either. * In the while loop, now call map_one_extent() with search_forward=1 * !found, so print (somewhat deceptive) error only mentioning the user-given logical without mentioning it looked elsewhere, and give up. =====[ FIX ]===== btrfs-map-logical and I are not friends. The "least code" fix for this situation is this patch. Qu's "btrfs-progs: check: Also compare data between mirrors to detect corruption for NODATASUM extents" uses a simpler way, which makes me wonder if that should just be modified to replace how btrfs-map-logical works. But, I'll admit I do not have my head around the entire way everything is done in btrfs-map-logical, and there could be reasons for it needing to be different here. This doesn't touch what I think is the buffer over-read error described above. With this fix, btrfs_item_key_to_cpu() is not asked to read out of bounds, so map_one_extent() leaves cur_logical and cur_len unmodified because they don't need to be. (Both the first time it's ran with search_forward=0, and in the while loop when it's ran with search_forward=1.) Also updated call from btrfs_next_item() to btrfs_next_extent_item(). I can't see any reason not to, while this area's being modified. It looks for both BTRFS_EXTENT_ITEM_KEY and BTRFS_METADATA_ITEM_KEY, which is what we need. (Granted, inside, it's just calling btrfs_next_item().) Also fixed misspelling of "foward" to "forward". Signed-off-by: James Harvey --- btrfs-map-logical.c | 18 +++++++++++++----- 1 file changed, 13 insertions(+), 5 deletions(-) diff --git a/btrfs-map-logical.c b/btrfs-map-logical.c index 7a8bcff9..1c30b22b 100644 --- a/btrfs-map-logical.c +++ b/btrfs-map-logical.c @@ -39,7 +39,7 @@ static FILE *info_file; static int map_one_extent(struct btrfs_fs_info *fs_info, - u64 *logical_ret, u64 *len_ret, int search_foward) + u64 *logical_ret, u64 *len_ret, int search_forward) { struct btrfs_path *path; struct btrfs_key key; @@ -65,17 +65,25 @@ static int map_one_extent(struct btrfs_fs_info *fs_info, BUG_ON(ret == 0); ret = 0; + if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) { + ret = btrfs_next_leaf(fs_info->extent_root, path); + if (ret != 0) { + ret = -1; + goto out; + } + } + again: btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); - if ((search_foward && key.objectid < logical) || - (!search_foward && key.objectid > logical) || + if ((search_forward && key.objectid < logical) || + (!search_forward && key.objectid > logical) || (key.type != BTRFS_EXTENT_ITEM_KEY && key.type != BTRFS_METADATA_ITEM_KEY)) { - if (!search_foward) + if (!search_forward) ret = btrfs_previous_extent_item(fs_info->extent_root, path, 0); else - ret = btrfs_next_item(fs_info->extent_root, path); + ret = btrfs_next_extent_item(fs_info->extent_root, path); if (ret) goto out;