From patchwork Tue Dec 1 07:11:36 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 7733301 Return-Path: X-Original-To: patchwork-linux-btrfs@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id C0CD2BEEE5 for ; Tue, 1 Dec 2015 07:14:38 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id B98BD2045A for ; Tue, 1 Dec 2015 07:14:37 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id C96C220661 for ; Tue, 1 Dec 2015 07:14:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755282AbbLAHOe (ORCPT ); Tue, 1 Dec 2015 02:14:34 -0500 Received: from cn.fujitsu.com ([59.151.112.132]:15517 "EHLO heian.cn.fujitsu.com" rhost-flags-OK-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1755251AbbLAHOd (ORCPT ); Tue, 1 Dec 2015 02:14:33 -0500 X-IronPort-AV: E=Sophos;i="5.20,346,1444665600"; d="scan'208";a="1025427" Received: from unknown (HELO cn.fujitsu.com) ([10.167.250.3]) by heian.cn.fujitsu.com with ESMTP; 01 Dec 2015 15:14:18 +0800 Received: from localhost.localdomain (unknown [10.167.226.34]) by cn.fujitsu.com (Postfix) with ESMTP id 9CFFB40444DB for ; Tue, 1 Dec 2015 15:14:10 +0800 (CST) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH v2 16/25] btrfs-progs: extent-tree: Introduce function to find the first overlap extent. Date: Tue, 1 Dec 2015 15:11:36 +0800 Message-Id: <1448953905-28673-17-git-send-email-quwenruo@cn.fujitsu.com> X-Mailer: git-send-email 2.6.2 In-Reply-To: <1448953905-28673-1-git-send-email-quwenruo@cn.fujitsu.com> References: <1448953905-28673-1-git-send-email-quwenruo@cn.fujitsu.com> MIME-Version: 1.0 X-yoursite-MailScanner-Information: Please contact the ISP for more information X-yoursite-MailScanner-ID: 9CFFB40444DB.AF64A X-yoursite-MailScanner: Found to be clean X-yoursite-MailScanner-From: quwenruo@cn.fujitsu.com X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Introduce a new function, btrfs_search_overlap_extent() to find the first overlap extent. It's useful for later btrfs-convert rework. Signed-off-by: Qu Wenruo --- ctree.c | 24 +++++++++++++++++++++++ ctree.h | 2 ++ extent-tree.c | 63 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 89 insertions(+) diff --git a/ctree.c b/ctree.c index 46153e3..dcf824a 100644 --- a/ctree.c +++ b/ctree.c @@ -2937,3 +2937,27 @@ int btrfs_previous_extent_item(struct btrfs_root *root, } return 1; } + +/* + * Search in extent tree to found next meta/data extent + * Caller need to check no-hole or skinny metadata + */ +int btrfs_next_extent_item(struct btrfs_root *root, + struct btrfs_path *path, u64 max_objectid) +{ + struct btrfs_key found_key; + int ret; + + while (1) { + ret = btrfs_next_item(root, path); + if (ret) + return ret; + btrfs_item_key_to_cpu(path->nodes[0], &found_key, + path->slots[0]); + if (found_key.objectid > max_objectid) + return 1; + if (found_key.type == BTRFS_EXTENT_ITEM_KEY || + found_key.type == BTRFS_METADATA_ITEM_KEY) + return 0; + } +} diff --git a/ctree.h b/ctree.h index c57f9ca..f97af7e 100644 --- a/ctree.h +++ b/ctree.h @@ -2301,6 +2301,8 @@ int btrfs_previous_item(struct btrfs_root *root, int type); int btrfs_previous_extent_item(struct btrfs_root *root, struct btrfs_path *path, u64 min_objectid); +int btrfs_next_extent_item(struct btrfs_root *root, + struct btrfs_path *path, u64 max_objectid); int btrfs_cow_block(struct btrfs_trans_handle *trans, struct btrfs_root *root, struct extent_buffer *buf, struct extent_buffer *parent, int parent_slot, diff --git a/extent-tree.c b/extent-tree.c index e04d962..9bd99a4 100644 --- a/extent-tree.c +++ b/extent-tree.c @@ -3908,6 +3908,69 @@ int btrfs_fix_block_accounting(struct btrfs_trans_handle *trans, return 0; } +static void __get_extent_size(struct btrfs_root *root, struct btrfs_path *path, + u64 *start, u64 *len) +{ + struct btrfs_key key; + + btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]); + BUG_ON(!(key.type == BTRFS_EXTENT_ITEM_KEY || + key.type == BTRFS_METADATA_ITEM_KEY)); + *start = key.objectid; + if (key.type == BTRFS_EXTENT_ITEM_KEY) + *len = key.offset; + else + *len = root->nodesize; +} + +/* + * Find first overlap extent for range [bytenr, bytenr + len) + * Return 0 for found and point path to it. + * Return >0 for not found. + * Return <0 for err + */ +int btrfs_search_overlap_extent(struct btrfs_root *root, + struct btrfs_path *path, u64 bytenr, u64 len) +{ + struct btrfs_key key; + u64 cur_start; + u64 cur_len; + int ret; + + key.objectid = bytenr; + key.type = BTRFS_EXTENT_DATA_KEY; + key.offset = (u64)-1; + + ret = btrfs_search_slot(NULL, root, &key, path, 0, 0); + if (ret < 0) + return ret; + BUG_ON(ret == 0); + + ret = btrfs_previous_extent_item(root, path, 0); + if (ret < 0) + return ret; + /* no previous, check next extent */ + if (ret > 0) + goto next; + __get_extent_size(root, path, &cur_start, &cur_len); + /* Tail overlap */ + if (cur_start + cur_len > bytenr) + return 1; + +next: + ret = btrfs_next_extent_item(root, path, bytenr + len); + if (ret < 0) + return ret; + /* No next, prev already checked, no overlap */ + if (ret > 0) + return 0; + __get_extent_size(root, path, &cur_start, &cur_len); + /* head overlap*/ + if (cur_start < bytenr + len) + return 1; + return 0; +} + /* * Record a file extent. Do all the required works, such as inserting * file extent item, inserting extent item and backref item into extent