From patchwork Tue Dec 1 07:11:22 2015 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Qu Wenruo X-Patchwork-Id: 7733451 Return-Path: X-Original-To: patchwork-linux-btrfs@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork1.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork1.web.kernel.org (Postfix) with ESMTP id 80CB49F39D for ; Tue, 1 Dec 2015 07:15:54 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id A6010206AD for ; Tue, 1 Dec 2015 07:15:53 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id AFECB206AC for ; Tue, 1 Dec 2015 07:15:52 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755128AbbLAHOS (ORCPT ); Tue, 1 Dec 2015 02:14:18 -0500 Received: from cn.fujitsu.com ([59.151.112.132]:62711 "EHLO heian.cn.fujitsu.com" rhost-flags-OK-FAIL-OK-FAIL) by vger.kernel.org with ESMTP id S1755048AbbLAHOQ (ORCPT ); Tue, 1 Dec 2015 02:14:16 -0500 X-IronPort-AV: E=Sophos;i="5.20,346,1444665600"; d="scan'208";a="1025398" Received: from unknown (HELO cn.fujitsu.com) ([10.167.250.3]) by heian.cn.fujitsu.com with ESMTP; 01 Dec 2015 15:14:02 +0800 Received: from localhost.localdomain (unknown [10.167.226.34]) by cn.fujitsu.com (Postfix) with ESMTP id 49AA640444C3 for ; Tue, 1 Dec 2015 15:14:00 +0800 (CST) From: Qu Wenruo To: linux-btrfs@vger.kernel.org Subject: [PATCH v2 02/25] btrfs-progs: extent-tree: Add add_merge_cache_extent function Date: Tue, 1 Dec 2015 15:11:22 +0800 Message-Id: <1448953905-28673-3-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: 49AA640444C3.AAEE2 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 This add_merge_cache_extent() function will try to merge adjusted cache_extent. This is used for later btrfs-convert ext2 free space cache. Signed-off-by: Qu Wenruo --- extent-cache.c | 57 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ extent-cache.h | 8 ++++++++ 2 files changed, 65 insertions(+) diff --git a/extent-cache.c b/extent-cache.c index d80aead..38bed8b 100644 --- a/extent-cache.c +++ b/extent-cache.c @@ -282,3 +282,60 @@ void free_extent_cache_tree(struct cache_tree *tree) { cache_tree_free_extents(tree, free_extent_cache); } + +int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size) +{ + struct cache_extent *cache; + struct cache_extent *next = NULL; + struct cache_extent *prev = NULL; + int next_merged = 0; + int prev_merged = 0; + int ret = 0; + + if (cache_tree_empty(tree)) + goto insert; + + cache = search_cache_extent(tree, start); + if (!cache) { + /* + * Either the tree is completely empty, or the no range after + * start. + * Either way, the last cache_extent should be prev. + */ + prev = last_cache_extent(tree); + } else if (start <= cache->start) { + next = cache; + prev = prev_cache_extent(cache); + } else { + prev = cache; + next = next_cache_extent(cache); + } + + /* + * Ensure the range to be inserted won't cover with existings + * Or we will need extra loop to do merge + */ + BUG_ON(next && start + size > next->start); + BUG_ON(prev && prev->start + prev->size > start); + + if (next && start + size == next->start) { + next_merged = 1; + next->size = next->start + next->size - start; + next->start = start; + } + if (prev && prev->start + prev->size == start) { + prev_merged = 1; + if (next_merged) { + next->size = next->start + next->size - prev->start; + next->start = prev->start; + remove_cache_extent(tree, prev); + free(prev); + } else { + prev->size = start + size - prev->start; + } + } +insert: + if (!prev_merged && !next_merged) + ret = add_cache_extent(tree, start, size); + return ret; +} diff --git a/extent-cache.h b/extent-cache.h index 1ce68ef..f031fbf 100644 --- a/extent-cache.h +++ b/extent-cache.h @@ -110,4 +110,12 @@ int add_cache_extent2(struct cache_tree *tree, u64 objectid, u64 start, u64 size); int insert_cache_extent2(struct cache_tree *tree, struct cache_extent *pe); +/* + * Insert a cache_extent range [start, start + size). + * + * This function may merge with existing cache_extent. + * NOTE: caller must ensure the inserted range won't cover with any existing + * range. + */ +int add_merge_cache_extent(struct cache_tree *tree, u64 start, u64 size); #endif