From patchwork Wed Nov 28 03:11:43 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Su Yue X-Patchwork-Id: 10701723 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 4C4DE1869 for ; Wed, 28 Nov 2018 03:04:21 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 3BD88289FA for ; Wed, 28 Nov 2018 03:04:21 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 303AB2C85C; Wed, 28 Nov 2018 03:04:21 +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 C85E12C854 for ; Wed, 28 Nov 2018 03:04:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1727270AbeK1OEU (ORCPT ); Wed, 28 Nov 2018 09:04:20 -0500 Received: from mail.cn.fujitsu.com ([183.91.158.132]:16765 "EHLO heian.cn.fujitsu.com" rhost-flags-OK-OK-OK-FAIL) by vger.kernel.org with ESMTP id S1727247AbeK1OET (ORCPT ); Wed, 28 Nov 2018 09:04:19 -0500 X-IronPort-AV: E=Sophos;i="5.56,289,1539619200"; d="scan'208";a="48766251" Received: from unknown (HELO cn.fujitsu.com) ([10.167.33.5]) by heian.cn.fujitsu.com with ESMTP; 28 Nov 2018 11:04:14 +0800 Received: from G08CNEXCHPEKD01.g08.fujitsu.local (unknown [10.167.33.80]) by cn.fujitsu.com (Postfix) with ESMTP id 522584B734CC for ; Wed, 28 Nov 2018 11:04:14 +0800 (CST) Received: from localhost.localdomain (10.167.226.22) by G08CNEXCHPEKD01.g08.fujitsu.local (10.167.33.89) with Microsoft SMTP Server (TLS) id 14.3.408.0; Wed, 28 Nov 2018 11:04:19 +0800 From: Su Yue To: CC: Subject: [RFC PATCH 12/17] btrfs: priority alloc: introduce find_free_extent_search() Date: Wed, 28 Nov 2018 11:11:43 +0800 Message-ID: <20181128031148.357-13-suy.fnst@cn.fujitsu.com> X-Mailer: git-send-email 2.19.1 In-Reply-To: <20181128031148.357-1-suy.fnst@cn.fujitsu.com> References: <20181128031148.357-1-suy.fnst@cn.fujitsu.com> MIME-Version: 1.0 X-Originating-IP: [10.167.226.22] X-yoursite-MailScanner-ID: 522584B734CC.A846A X-yoursite-MailScanner: Found to be clean X-yoursite-MailScanner-From: suy.fnst@cn.fujitsu.com 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 origin, find_free_extent() just searches block groups in space_info one by one. In priority aware allocator, we first search block groups in higher priority tree than in lower priority tree. This helper unify above two ways for further use. Signed-off-by: Su Yue --- fs/btrfs/extent-tree.c | 77 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 77 insertions(+) diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c index 74955f79fcce..5484256169dd 100644 --- a/fs/btrfs/extent-tree.c +++ b/fs/btrfs/extent-tree.c @@ -7331,6 +7331,83 @@ struct find_free_extent_ctl { }; +/* + * Helper function for find_free_extent(). + * + * Return next block_group_cache to use. + * Return NULL mean no more block group to use. + * + * If use_priority is false: return the next of @block_group in + * space_info->block_groups[index] or if @blockgroup is NULL, return first + * block group in the list. + * + * If use_priority is true: if *pt_ret is NULL, return first block group in + * highest priority level. If *pt_ret is NOT NULL, return the next of + * @block_group or if @block_group is NULL, return first available block group + * which located in priority level <= *pt_ret->level. + * The tree will be down_read if return value is not NULL. + * + */ +static struct btrfs_block_group_cache * +find_free_extent_search(struct btrfs_space_info *space_info, int index, + struct btrfs_block_group_cache *block_group, bool use_priority, + struct btrfs_priority_tree **pt_ret) +{ + + struct list_head *lentry, *head; + struct rb_root *root; + struct rb_node *node, *bg_node; + struct btrfs_priority_tree *pt; + bool read; + + if (!use_priority) { + head = &space_info->block_groups[index]; + if (!block_group) + lentry = head->next; + else + lentry = block_group->list.next; + if (lentry == head) + return NULL; + return list_entry(lentry, struct btrfs_block_group_cache, + list); + } + + root = &space_info->priority_trees[index]; + pt = pt_ret ? *pt_ret : NULL; + + if (!pt) { + node = rb_first(root); + read = true; + } else { + node = &pt->node; + read = false; + + if (block_group) + bg_node = rb_next(&block_group->node); + else + bg_node = rb_first(&pt->block_groups); + } + + for (; node; node = rb_next(node)) { + pt = rb_entry(node, struct btrfs_priority_tree, node); + if (read) { + down_read(&pt->groups_sem); + bg_node = rb_first(&pt->block_groups); + } + for (; bg_node; bg_node = rb_next(bg_node)) { + if (bg_node) { + *pt_ret = pt; + return rb_entry(bg_node, + struct btrfs_block_group_cache, node); + } + } + + up_read(&pt->groups_sem); + read = true; + } + + return NULL; +} /* * Helper function for find_free_extent(). *