From patchwork Tue Dec 30 08:48:02 2014 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Liu Bo X-Patchwork-Id: 5551651 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 C6829BF6C3 for ; Tue, 30 Dec 2014 08:48:27 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 22C4720121 for ; Tue, 30 Dec 2014 08:48:26 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id 5FA592010E for ; Tue, 30 Dec 2014 08:48:24 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752002AbaL3IsO (ORCPT ); Tue, 30 Dec 2014 03:48:14 -0500 Received: from aserp1040.oracle.com ([141.146.126.69]:48988 "EHLO aserp1040.oracle.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751967AbaL3IsN (ORCPT ); Tue, 30 Dec 2014 03:48:13 -0500 Received: from acsinet21.oracle.com (acsinet21.oracle.com [141.146.126.237]) by aserp1040.oracle.com (Sentrion-MTA-4.3.2/Sentrion-MTA-4.3.2) with ESMTP id sBU8mCpN027745 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=OK) for ; Tue, 30 Dec 2014 08:48:13 GMT Received: from aserz7021.oracle.com (aserz7021.oracle.com [141.146.126.230]) by acsinet21.oracle.com (8.14.4+Sun/8.14.4) with ESMTP id sBU8mCow005147 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Tue, 30 Dec 2014 08:48:12 GMT Received: from abhmp0007.oracle.com (abhmp0007.oracle.com [141.146.116.13]) by aserz7021.oracle.com (8.14.4+Sun/8.14.4) with ESMTP id sBU8mBZX005142 for ; Tue, 30 Dec 2014 08:48:11 GMT Received: from localhost.localdomain.com (/10.182.228.124) by default (Oracle Beehive Gateway v4.0) with ESMTP ; Tue, 30 Dec 2014 00:48:11 -0800 From: Liu Bo To: linux-btrfs@vger.kernel.org Subject: [PATCH] Btrfs: use list instead of rbtree for free_space cluster Date: Tue, 30 Dec 2014 16:48:02 +0800 Message-Id: <1419929282-6594-1-git-send-email-bo.li.liu@oracle.com> X-Mailer: git-send-email 1.8.1.4 X-Source-IP: acsinet21.oracle.com [141.146.126.237] Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, T_RP_MATCHES_RCVD, UNPARSEABLE_RELAY autolearn=unavailable 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 Our free_space cluster currently only uses rb_next to find a proper free_space entry by interating rbtree, there is no search involved, so it's more efficient to iterate a list rather than a rbtree. This is a straightforward change that converts rbtree to list. Signed-off-by: Liu Bo --- fs/btrfs/ctree.h | 3 +- fs/btrfs/free-space-cache.c | 187 +++++++++++++++++++++++--------------------- fs/btrfs/free-space-cache.h | 1 + 3 files changed, 99 insertions(+), 92 deletions(-) diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h index be47b10..7e539a9 100644 --- a/fs/btrfs/ctree.h +++ b/fs/btrfs/ctree.h @@ -1209,7 +1209,8 @@ struct btrfs_block_rsv { struct btrfs_free_cluster { spinlock_t lock; spinlock_t refill_lock; - struct rb_root root; + + struct list_head free_space; /* largest extent in this cluster */ u64 max_size; diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c index 448cf6f..ad0d845 100644 --- a/fs/btrfs/free-space-cache.c +++ b/fs/btrfs/free-space-cache.c @@ -43,6 +43,26 @@ static int link_free_space(struct btrfs_free_space_ctl *ctl, static void unlink_free_space(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info); +static struct btrfs_free_space *alloc_free_space_cache(gfp_t mask) +{ + struct btrfs_free_space *e; + + e = kmem_cache_zalloc(btrfs_free_space_cachep, + GFP_NOFS); + if (!e) + return NULL; + + RB_CLEAR_NODE(&e->offset_index); + INIT_LIST_HEAD(&e->cluster_list); + return e; +} + +static void reclaim_free_space_cache(struct btrfs_free_space *info) +{ + WARN_ON_ONCE(!list_empty(&info->cluster_list)); + kmem_cache_free(btrfs_free_space_cachep, info); +} + static struct inode *__lookup_free_space_inode(struct btrfs_root *root, struct btrfs_path *path, u64 offset) @@ -630,7 +650,7 @@ again: unlink_free_space(ctl, prev); unlink_free_space(ctl, e); prev->bytes += e->bytes; - kmem_cache_free(btrfs_free_space_cachep, e); + reclaim_free_space_cache(e); link_free_space(ctl, prev); prev = NULL; spin_unlock(&ctl->tree_lock); @@ -725,19 +745,18 @@ static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode, goto free_cache; while (num_entries) { - e = kmem_cache_zalloc(btrfs_free_space_cachep, - GFP_NOFS); + e = alloc_free_space_cache(GFP_NOFS); if (!e) goto free_cache; ret = io_ctl_read_entry(&io_ctl, e, &type); if (ret) { - kmem_cache_free(btrfs_free_space_cachep, e); + reclaim_free_space_cache(e); goto free_cache; } if (!e->bytes) { - kmem_cache_free(btrfs_free_space_cachep, e); + reclaim_free_space_cache(e); goto free_cache; } @@ -748,7 +767,7 @@ static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode, if (ret) { btrfs_err(root->fs_info, "Duplicate entries in free space cache, dumping"); - kmem_cache_free(btrfs_free_space_cachep, e); + reclaim_free_space_cache(e); goto free_cache; } } else { @@ -756,8 +775,7 @@ static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode, num_bitmaps--; e->bitmap = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS); if (!e->bitmap) { - kmem_cache_free( - btrfs_free_space_cachep, e); + reclaim_free_space_cache(e); goto free_cache; } spin_lock(&ctl->tree_lock); @@ -768,7 +786,7 @@ static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode, if (ret) { btrfs_err(root->fs_info, "Duplicate entries in free space cache, dumping"); - kmem_cache_free(btrfs_free_space_cachep, e); + reclaim_free_space_cache(e); goto free_cache; } list_add_tail(&e->list, &bitmaps); @@ -897,9 +915,22 @@ int write_cache_extent_entries(struct io_ctl *io_ctl, block_group_list); } - if (!node && cluster) { - node = rb_first(&cluster->root); - cluster = NULL; + if (cluster) { + struct btrfs_free_space *e; + + list_for_each_entry(e, &cluster->free_space, cluster_list) { + *entries += 1; + + ret = io_ctl_add_entry(io_ctl, e->offset, e->bytes, + e->bitmap); + if (ret) + goto fail; + + if (e->bitmap) { + list_add_tail(&e->list, bitmap_list); + *bitmaps += 1; + } + } } /* Write out the extent entries */ @@ -919,10 +950,6 @@ int write_cache_extent_entries(struct io_ctl *io_ctl, *bitmaps += 1; } node = rb_next(node); - if (!node && cluster) { - node = rb_first(&cluster->root); - cluster = NULL; - } } /* @@ -1488,6 +1515,7 @@ __unlink_free_space(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info) { rb_erase(&info->offset_index, &ctl->free_space_offset); + RB_CLEAR_NODE(&info->offset_index); ctl->free_extents--; } @@ -1726,7 +1754,7 @@ static void free_bitmap(struct btrfs_free_space_ctl *ctl, { unlink_free_space(ctl, bitmap_info); kfree(bitmap_info->bitmap); - kmem_cache_free(btrfs_free_space_cachep, bitmap_info); + reclaim_free_space_cache(bitmap_info); ctl->total_bitmaps--; ctl->op->recalc_thresholds(ctl); } @@ -1893,20 +1921,19 @@ again: */ if (block_group && !list_empty(&block_group->cluster_list)) { struct btrfs_free_cluster *cluster; - struct rb_node *node; struct btrfs_free_space *entry; cluster = list_entry(block_group->cluster_list.next, struct btrfs_free_cluster, block_group_list); spin_lock(&cluster->lock); - node = rb_first(&cluster->root); - if (!node) { + if (list_empty(&cluster->free_space)) { spin_unlock(&cluster->lock); goto no_cluster_bitmap; } - entry = rb_entry(node, struct btrfs_free_space, offset_index); + entry = list_first_entry(&cluster->free_space, + struct btrfs_free_space, cluster_list); if (!entry->bitmap) { spin_unlock(&cluster->lock); goto no_cluster_bitmap; @@ -1955,8 +1982,7 @@ new_bitmap: /* no pre-allocated info, allocate a new one */ if (!info) { - info = kmem_cache_zalloc(btrfs_free_space_cachep, - GFP_NOFS); + info = alloc_free_space_cache(GFP_NOFS); if (!info) { spin_lock(&ctl->tree_lock); ret = -ENOMEM; @@ -1978,7 +2004,7 @@ out: if (info) { if (info->bitmap) kfree(info->bitmap); - kmem_cache_free(btrfs_free_space_cachep, info); + reclaim_free_space_cache(info); } return ret; @@ -2011,7 +2037,7 @@ static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl, else __unlink_free_space(ctl, right_info); info->bytes += right_info->bytes; - kmem_cache_free(btrfs_free_space_cachep, right_info); + reclaim_free_space_cache(right_info); merged = true; } @@ -2023,7 +2049,7 @@ static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl, __unlink_free_space(ctl, left_info); info->offset = left_info->offset; info->bytes += left_info->bytes; - kmem_cache_free(btrfs_free_space_cachep, left_info); + reclaim_free_space_cache(left_info); merged = true; } @@ -2158,13 +2184,12 @@ int __btrfs_add_free_space(struct btrfs_free_space_ctl *ctl, struct btrfs_free_space *info; int ret = 0; - info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS); + info = alloc_free_space_cache(GFP_NOFS); if (!info) return -ENOMEM; info->offset = offset; info->bytes = bytes; - RB_CLEAR_NODE(&info->offset_index); spin_lock(&ctl->tree_lock); @@ -2194,7 +2219,7 @@ link: ret = link_free_space(ctl, info); if (ret) - kmem_cache_free(btrfs_free_space_cachep, info); + reclaim_free_space_cache(info); out: spin_unlock(&ctl->tree_lock); @@ -2252,7 +2277,7 @@ again: ret = link_free_space(ctl, info); WARN_ON(ret); } else { - kmem_cache_free(btrfs_free_space_cachep, info); + reclaim_free_space_cache(info); } offset += to_free; @@ -2352,8 +2377,7 @@ __btrfs_return_cluster_to_free_space( struct btrfs_free_cluster *cluster) { struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; - struct btrfs_free_space *entry; - struct rb_node *node; + struct btrfs_free_space *entry, *tmp; spin_lock(&cluster->lock); if (cluster->block_group != block_group) @@ -2363,14 +2387,11 @@ __btrfs_return_cluster_to_free_space( cluster->window_start = 0; list_del_init(&cluster->block_group_list); - node = rb_first(&cluster->root); - while (node) { + list_for_each_entry_safe(entry, tmp, + &cluster->free_space, cluster_list) { bool bitmap; - entry = rb_entry(node, struct btrfs_free_space, offset_index); - node = rb_next(&entry->offset_index); - rb_erase(&entry->offset_index, &cluster->root); - RB_CLEAR_NODE(&entry->offset_index); + list_del_init(&entry->cluster_list); bitmap = (entry->bitmap != NULL); if (!bitmap) { @@ -2380,7 +2401,6 @@ __btrfs_return_cluster_to_free_space( tree_insert_offset(&ctl->free_space_offset, entry->offset, &entry->offset_index, bitmap); } - cluster->root = RB_ROOT; out: spin_unlock(&cluster->lock); @@ -2398,7 +2418,7 @@ static void __btrfs_remove_free_space_cache_locked( info = rb_entry(node, struct btrfs_free_space, offset_index); if (!info->bitmap) { unlink_free_space(ctl, info); - kmem_cache_free(btrfs_free_space_cachep, info); + reclaim_free_space_cache(info); } else { free_bitmap(ctl, info); } @@ -2474,7 +2494,7 @@ u64 btrfs_find_space_for_alloc(struct btrfs_block_group_cache *block_group, entry->bytes -= bytes + align_gap_len; if (!entry->bytes) - kmem_cache_free(btrfs_free_space_cachep, entry); + reclaim_free_space_cache(entry); else link_free_space(ctl, entry); } @@ -2567,8 +2587,7 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, u64 min_start, u64 *max_extent_size) { struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl; - struct btrfs_free_space *entry = NULL; - struct rb_node *node; + struct btrfs_free_space *entry = NULL, *tmp; u64 ret = 0; spin_lock(&cluster->lock); @@ -2578,38 +2597,23 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, if (cluster->block_group != block_group) goto out; - node = rb_first(&cluster->root); - if (!node) - goto out; - - entry = rb_entry(node, struct btrfs_free_space, offset_index); - while (1) { + list_for_each_entry_safe(entry, tmp, + &cluster->free_space, cluster_list) { if (entry->bytes < bytes && entry->bytes > *max_extent_size) *max_extent_size = entry->bytes; if (entry->bytes < bytes || - (!entry->bitmap && entry->offset < min_start)) { - node = rb_next(&entry->offset_index); - if (!node) - break; - entry = rb_entry(node, struct btrfs_free_space, - offset_index); + (!entry->bitmap && entry->offset < min_start)) continue; - } if (entry->bitmap) { ret = btrfs_alloc_from_bitmap(block_group, cluster, entry, bytes, cluster->window_start, max_extent_size); - if (ret == 0) { - node = rb_next(&entry->offset_index); - if (!node) - break; - entry = rb_entry(node, struct btrfs_free_space, - offset_index); + if (ret == 0) continue; - } + cluster->window_start += bytes; } else { ret = entry->offset; @@ -2619,7 +2623,7 @@ u64 btrfs_alloc_from_cluster(struct btrfs_block_group_cache *block_group, } if (entry->bytes == 0) - rb_erase(&entry->offset_index, &cluster->root); + list_del_init(&entry->cluster_list); break; } out: @@ -2638,7 +2642,7 @@ out: ctl->total_bitmaps--; ctl->op->recalc_thresholds(ctl); } - kmem_cache_free(btrfs_free_space_cachep, entry); + reclaim_free_space_cache(entry); } spin_unlock(&ctl->tree_lock); @@ -2660,7 +2664,6 @@ static int btrfs_bitmap_cluster(struct btrfs_block_group_cache *block_group, unsigned long found_bits; unsigned long start = 0; unsigned long total_found = 0; - int ret; i = offset_to_bit(entry->offset, ctl->unit, max_t(u64, offset, entry->offset)); @@ -2699,9 +2702,10 @@ again: cluster->window_start = start * ctl->unit + entry->offset; rb_erase(&entry->offset_index, &ctl->free_space_offset); - ret = tree_insert_offset(&cluster->root, entry->offset, - &entry->offset_index, 1); - ASSERT(!ret); /* -EEXIST; Logic error */ + RB_CLEAR_NODE(&entry->offset_index); + + WARN_ON_ONCE(!list_empty(&entry->cluster_list)); + list_add_tail(&entry->cluster_list, &cluster->free_space); trace_btrfs_setup_cluster(block_group, cluster, total_found * ctl->unit, 1); @@ -2749,6 +2753,8 @@ setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, max_extent = entry->bytes; first = entry; last = entry; + WARN_ON_ONCE(!list_empty(&entry->cluster_list)); + list_add_tail(&entry->cluster_list, &cluster->free_space); for (node = rb_next(&entry->offset_index); node; node = rb_next(&entry->offset_index)) { @@ -2767,33 +2773,32 @@ setup_cluster_no_bitmap(struct btrfs_block_group_cache *block_group, window_free += entry->bytes; if (entry->bytes > max_extent) max_extent = entry->bytes; + + WARN_ON_ONCE(!list_empty(&entry->cluster_list)); + list_add_tail(&entry->cluster_list, &cluster->free_space); } - if (window_free < bytes || max_extent < cont1_bytes) + if (window_free < bytes || max_extent < cont1_bytes) { + struct btrfs_free_space *tmp; + + list_for_each_entry_safe(entry, tmp, + &cluster->free_space, cluster_list) + list_del_init(&entry->cluster_list); return -ENOSPC; + } cluster->window_start = first->offset; - node = &first->offset_index; - /* * now we've found our entries, pull them out of the free space * cache and put them into the cluster rbtree */ - do { - int ret; - - entry = rb_entry(node, struct btrfs_free_space, offset_index); - node = rb_next(&entry->offset_index); - if (entry->bitmap || entry->bytes < min_bytes) - continue; - + list_for_each_entry(entry, &cluster->free_space, cluster_list) { + WARN_ON_ONCE(entry->bitmap || entry->bytes < min_bytes); rb_erase(&entry->offset_index, &ctl->free_space_offset); - ret = tree_insert_offset(&cluster->root, entry->offset, - &entry->offset_index, 0); + RB_CLEAR_NODE(&entry->offset_index); total_size += entry->bytes; - ASSERT(!ret); /* -EEXIST; Logic error */ - } while (node && entry != last); + } cluster->max_size = max_extent; trace_btrfs_setup_cluster(block_group, cluster, total_size, 0); @@ -2938,9 +2943,9 @@ void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster) { spin_lock_init(&cluster->lock); spin_lock_init(&cluster->refill_lock); - cluster->root = RB_ROOT; cluster->max_size = 0; INIT_LIST_HEAD(&cluster->block_group_list); + INIT_LIST_HEAD(&cluster->free_space); cluster->block_group = NULL; } @@ -3049,7 +3054,7 @@ static int trim_no_bitmap(struct btrfs_block_group_cache *block_group, } unlink_free_space(ctl, entry); - kmem_cache_free(btrfs_free_space_cachep, entry); + reclaim_free_space_cache(entry); spin_unlock(&ctl->tree_lock); trim_entry.start = extent_start; @@ -3241,7 +3246,7 @@ u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root) entry->offset++; entry->bytes--; if (!entry->bytes) - kmem_cache_free(btrfs_free_space_cachep, entry); + reclaim_free_space_cache(entry); else link_free_space(ctl, entry); } else { @@ -3380,7 +3385,7 @@ int test_add_free_space_entry(struct btrfs_block_group_cache *cache, again: if (!info) { - info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS); + info = alloc_free_space_cache(GFP_NOFS); if (!info) return -ENOMEM; } @@ -3392,14 +3397,14 @@ again: ret = link_free_space(ctl, info); spin_unlock(&ctl->tree_lock); if (ret) - kmem_cache_free(btrfs_free_space_cachep, info); + reclaim_free_space_cache(info); return ret; } if (!map) { map = kzalloc(PAGE_CACHE_SIZE, GFP_NOFS); if (!map) { - kmem_cache_free(btrfs_free_space_cachep, info); + reclaim_free_space_cache(info); return -ENOMEM; } } @@ -3424,7 +3429,7 @@ again: goto again; if (info) - kmem_cache_free(btrfs_free_space_cachep, info); + reclaim_free_space_cache(info); if (map) kfree(map); return 0; diff --git a/fs/btrfs/free-space-cache.h b/fs/btrfs/free-space-cache.h index 88b2238..dce9195 100644 --- a/fs/btrfs/free-space-cache.h +++ b/fs/btrfs/free-space-cache.h @@ -25,6 +25,7 @@ struct btrfs_free_space { u64 bytes; unsigned long *bitmap; struct list_head list; + struct list_head cluster_list; }; struct btrfs_free_space_ctl {