From patchwork Mon Jan 25 22:05:26 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jaegeuk Kim X-Patchwork-Id: 8116191 Return-Path: X-Original-To: patchwork-linux-fsdevel@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 E1B5CBEEE5 for ; Mon, 25 Jan 2016 22:07:05 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id DE6E020303 for ; Mon, 25 Jan 2016 22:07:04 +0000 (UTC) Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.kernel.org (Postfix) with ESMTP id D0A98202EB for ; Mon, 25 Jan 2016 22:07:03 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932218AbcAYWFm (ORCPT ); Mon, 25 Jan 2016 17:05:42 -0500 Received: from mail.kernel.org ([198.145.29.136]:48835 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755418AbcAYWFj (ORCPT ); Mon, 25 Jan 2016 17:05:39 -0500 Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id 41C0A202FF; Mon, 25 Jan 2016 22:05:37 +0000 (UTC) Received: from localhost (107-1-141-74-ip-static.hfc.comcastbusiness.net [107.1.141.74]) (using TLSv1.2 with cipher AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id 595D7202EB; Mon, 25 Jan 2016 22:05:36 +0000 (UTC) From: Jaegeuk Kim To: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, linux-f2fs-devel@lists.sourceforge.net Cc: Jaegeuk Kim Subject: [PATCH 1/6] f2fs: speed up shrinking extent_node cache Date: Mon, 25 Jan 2016 14:05:26 -0800 Message-Id: <1453759531-16076-1-git-send-email-jaegeuk@kernel.org> X-Mailer: git-send-email 2.6.3 X-Spam-Status: No, score=-6.9 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_HI, 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 Sender: linux-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP This patch speeds up extent_node shrinker by introducing linked list. Signed-off-by: Jaegeuk Kim --- fs/f2fs/extent_cache.c | 74 ++++++++++++++++++++++---------------------------- fs/f2fs/f2fs.h | 2 ++ 2 files changed, 35 insertions(+), 41 deletions(-) diff --git a/fs/f2fs/extent_cache.c b/fs/f2fs/extent_cache.c index ccd5c63..18311ff 100644 --- a/fs/f2fs/extent_cache.c +++ b/fs/f2fs/extent_cache.c @@ -32,7 +32,9 @@ static struct extent_node *__attach_extent_node(struct f2fs_sb_info *sbi, return NULL; en->ei = *ei; + en->et = et; INIT_LIST_HEAD(&en->list); + INIT_LIST_HEAD(&en->vlist); rb_link_node(&en->rb_node, parent, p); rb_insert_color(&en->rb_node, &et->root); @@ -129,7 +131,7 @@ static struct extent_node *__init_extent_tree(struct f2fs_sb_info *sbi, } static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, - struct extent_tree *et, bool free_all) + struct extent_tree *et) { struct rb_node *node, *next; struct extent_node *en; @@ -137,17 +139,19 @@ static unsigned int __free_extent_tree(struct f2fs_sb_info *sbi, node = rb_first(&et->root); while (node) { + bool need_free = false; + next = rb_next(node); en = rb_entry(node, struct extent_node, rb_node); - if (free_all) { - spin_lock(&sbi->extent_lock); - if (!list_empty(&en->list)) - list_del_init(&en->list); - spin_unlock(&sbi->extent_lock); + spin_lock(&sbi->extent_lock); + if (!list_empty(&en->list)) { + list_del_init(&en->list); + need_free = true; } + spin_unlock(&sbi->extent_lock); - if (free_all || list_empty(&en->list)) { + if (need_free) { __detach_extent_node(sbi, et, en); kmem_cache_free(extent_node_slab, en); } @@ -438,6 +442,7 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode, while (en && en->ei.fofs < end) { unsigned int org_end; int parts = 0; /* # of parts current extent split into */ + bool need_free = false; next_en = en1 = NULL; @@ -493,14 +498,16 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode, /* update in global extent list */ spin_lock(&sbi->extent_lock); - if (!parts && !list_empty(&en->list)) + if (!parts && !list_empty(&en->list)) { list_del(&en->list); + need_free = true; + } if (en1) list_add_tail(&en1->list, &sbi->extent_list); spin_unlock(&sbi->extent_lock); /* release extent node */ - if (!parts) + if (!parts && need_free) kmem_cache_free(extent_node_slab, en); en = next_en; @@ -509,6 +516,7 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode, /* 3. update extent in extent cache */ if (blkaddr) { struct extent_node *den = NULL; + bool need_free = false; set_extent_info(&ei, fofs, blkaddr, len); en1 = __try_merge_extent_node(sbi, et, &ei, &den, @@ -532,16 +540,18 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode, else list_move_tail(&en1->list, &sbi->extent_list); } - if (den && !list_empty(&den->list)) + if (den && !list_empty(&den->list)) { list_del(&den->list); + need_free = true; + } spin_unlock(&sbi->extent_lock); - if (den) + if (den && need_free) kmem_cache_free(extent_node_slab, den); } if (is_inode_flag_set(F2FS_I(inode), FI_NO_EXTENT)) - __free_extent_tree(sbi, et, true); + __free_extent_tree(sbi, et); write_unlock(&et->lock); @@ -550,14 +560,12 @@ static unsigned int f2fs_update_extent_tree_range(struct inode *inode, unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) { - struct extent_tree *treevec[EXT_TREE_VEC_SIZE]; struct extent_tree *et, *next; struct extent_node *en, *tmp; - unsigned long ino = F2FS_ROOT_INO(sbi); - unsigned int found; unsigned int node_cnt = 0, tree_cnt = 0; int remained; bool do_free = false; + LIST_HEAD(victim_list); if (!test_opt(sbi, EXTENT_CACHE)) return 0; @@ -572,7 +580,7 @@ unsigned int f2fs_shrink_extent_tree(struct f2fs_sb_info *sbi, int nr_shrink) list_for_each_entry_safe(et, next, &sbi->zombie_list, list) { if (atomic_read(&et->node_cnt)) { write_lock(&et->lock); - node_cnt += __free_extent_tree(sbi, et, true); + node_cnt += __free_extent_tree(sbi, et); write_unlock(&et->lock); } @@ -600,6 +608,8 @@ free_node: if (!remained--) break; list_del_init(&en->list); + list_add_tail(&en->vlist, &victim_list); + tree_cnt++; do_free = true; } spin_unlock(&sbi->extent_lock); @@ -607,31 +617,13 @@ free_node: if (do_free == false) goto unlock_out; - /* - * reset ino for searching victims from beginning of global extent tree. - */ - ino = F2FS_ROOT_INO(sbi); - - while ((found = radix_tree_gang_lookup(&sbi->extent_tree_root, - (void **)treevec, ino, EXT_TREE_VEC_SIZE))) { - unsigned i; - - ino = treevec[found - 1]->ino + 1; - for (i = 0; i < found; i++) { - struct extent_tree *et = treevec[i]; - - if (!atomic_read(&et->node_cnt)) - continue; - - if (write_trylock(&et->lock)) { - node_cnt += __free_extent_tree(sbi, et, false); - write_unlock(&et->lock); - } - - if (node_cnt + tree_cnt >= nr_shrink) - goto unlock_out; - } + list_for_each_entry_safe(en, tmp, &victim_list, vlist) { + write_lock(&en->et->lock); + __detach_extent_node(sbi, en->et, en); + write_unlock(&en->et->lock); + kmem_cache_free(extent_node_slab, en); } + unlock_out: up_write(&sbi->extent_tree_lock); out: @@ -650,7 +642,7 @@ unsigned int f2fs_destroy_extent_node(struct inode *inode) return 0; write_lock(&et->lock); - node_cnt = __free_extent_tree(sbi, et, true); + node_cnt = __free_extent_tree(sbi, et); write_unlock(&et->lock); return node_cnt; diff --git a/fs/f2fs/f2fs.h b/fs/f2fs/f2fs.h index c4e723b..0bbbfed 100644 --- a/fs/f2fs/f2fs.h +++ b/fs/f2fs/f2fs.h @@ -353,7 +353,9 @@ struct extent_info { struct extent_node { struct rb_node rb_node; /* rb node located in rb-tree */ struct list_head list; /* node in global extent list of sbi */ + struct list_head vlist; /* node in victim extent list */ struct extent_info ei; /* extent info */ + struct extent_tree *et; /* extent tree pointer */ }; struct extent_tree {