From patchwork Fri Nov 20 03:24:20 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 7664251 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 5BBD1BF90C for ; Fri, 20 Nov 2015 03:27:17 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 6F8EC20450 for ; Fri, 20 Nov 2015 03:27:16 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 6E16D20444 for ; Fri, 20 Nov 2015 03:27:15 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1161905AbbKTD1L (ORCPT ); Thu, 19 Nov 2015 22:27:11 -0500 Received: from cn.fujitsu.com ([59.151.112.132]:34066 "EHLO heian.cn.fujitsu.com" rhost-flags-OK-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S934965AbbKTD1K (ORCPT ); Thu, 19 Nov 2015 22:27:10 -0500 X-IronPort-AV: E=Sophos;i="5.20,242,1444665600"; d="scan'208";a="654833" Received: from unknown (HELO tang.cn.fujitsu.com) ([10.167.250.3]) by heian.cn.fujitsu.com with ESMTP; 20 Nov 2015 11:26:58 +0800 Received: from localhost.localdomain (tang.cn.fujitsu.com [127.0.0.1]) by tang.cn.fujitsu.com (8.14.3/8.13.1) with ESMTP id tAK3PqdP022290 for ; Fri, 20 Nov 2015 11:26:24 +0800 From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH 16/25] btrfs-progs: extent-tree: Introduce function to find the first overlap extent. Date: Fri, 20 Nov 2015 11:24:20 +0800 Message-Id: <1447989869-24739-17-git-send-email-quwenruo@cn.fujitsu.com> X-Mailer: git-send-email 2.6.2 In-Reply-To: <1447989869-24739-1-git-send-email-quwenruo@cn.fujitsu.com> References: <1447989869-24739-1-git-send-email-quwenruo@cn.fujitsu.com> Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Spam-Status: No, score=-7.5 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=ham version=3.3.1 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..9fa9377 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_DATA_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