From patchwork Sat Nov 29 10:54:19 2008 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Schultz X-Patchwork-Id: 11392 Return-Path: X-Original-To: patchwork-incoming@ozlabs.org Delivered-To: patchwork-incoming@ozlabs.org Received: from vger.kernel.org (vger.kernel.org [209.132.176.167]) by ozlabs.org (Postfix) with ESMTP id 9064ADDDF5 for ; Sat, 29 Nov 2008 21:54:30 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751207AbYK2Ky3 (ORCPT ); Sat, 29 Nov 2008 05:54:29 -0500 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S1751475AbYK2Ky3 (ORCPT ); Sat, 29 Nov 2008 05:54:29 -0500 Received: from mail.tpip.net ([213.187.84.201]:44197 "EHLO mail.tpip.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751207AbYK2Ky2 (ORCPT ); Sat, 29 Nov 2008 05:54:28 -0500 Received: from localhost (office-old.tpip.net [213.187.84.201]) by mail.tpip.net (Postfix) with ESMTP id 2BCC1FF313 for ; Sat, 29 Nov 2008 11:54:25 +0100 (CET) Received: from mail.tpip.net ([213.187.84.201]) by localhost (office.tpip.net [213.187.84.201]) (amavisd-new, port 10024) with ESMTP id JA18xpycf3ST for ; Sat, 29 Nov 2008 11:54:21 +0100 (CET) Received: from [192.168.2.24] (port-87-193-170-219.static.qsc.de [87.193.170.219]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.tpip.net (Postfix) with ESMTP id 494E462FA8 for ; Sat, 29 Nov 2008 11:54:21 +0100 (CET) Subject: [RFC][PATCH] "tune2fs -I 256" speedup From: Andreas Schultz To: linux-ext4@vger.kernel.org Organization: warp10.net Date: Sat, 29 Nov 2008 11:54:19 +0100 Message-Id: <1227956059.25439.16.camel@ws-aschultz> Mime-Version: 1.0 X-Mailer: Evolution 2.24.2 Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org Hi, After some on and off list discussion about the 'tune2fs -I' performance, Theodore Tso pointed out that the blk_move_list used by transalate_block() was less then optimal. This is my attempt at fixing that. Have fun Andreas replace list search with binary in transalate_block Signed-off-by: Andreas Schultz --- misc/tune2fs.c | 61 +++++++++++++++++++++++++++++-------------------------- 1 files changed, 32 insertions(+), 29 deletions(-) diff --git a/misc/tune2fs.c b/misc/tune2fs.c index e72518a..9c58f87 100644 --- a/misc/tune2fs.c +++ b/misc/tune2fs.c @@ -84,14 +84,14 @@ static unsigned long new_inode_size; int journal_size, journal_flags; char *journal_device; -static struct list_head blk_move_list; - struct blk_move { - struct list_head list; blk_t old_loc; blk_t new_loc; }; +#define BLK_MOVE_BLK (1024 * 512) /* grow blk_move_list this many entries */ +static blk_t blk_move_cnt = 0; +static struct blk_move *blk_move_list = NULL; static const char *please_fsck = N_("Please run e2fsck on the filesystem.\n"); @@ -1006,7 +1006,6 @@ static int move_block(ext2_filsys fs, ext2fs_block_bitmap bmap) blk_t blk, new_blk; struct blk_move *bmv; - retval = ext2fs_get_mem(fs->blocksize, &buf); if (retval) return retval; @@ -1024,15 +1023,17 @@ static int move_block(ext2_filsys fs, ext2fs_block_bitmap bmap) /* Mark this block as allocated */ ext2fs_mark_block_bitmap(fs->block_map, new_blk); - /* Add it to block move list */ - retval = ext2fs_get_mem(sizeof(struct blk_move), &bmv); - if (retval) - goto err_out; - - bmv->old_loc = blk; - bmv->new_loc = new_blk; + if (blk_move_cnt % BLK_MOVE_BLK == 0) { + retval = ext2fs_resize_mem(sizeof(struct blk_move) * blk_move_cnt, + sizeof(struct blk_move) * (blk_move_cnt + BLK_MOVE_BLK), + &blk_move_list); + if (retval) + goto err_out; + } - list_add(&(bmv->list), &blk_move_list); + blk_move_list[blk_move_cnt].old_loc = blk; + blk_move_list[blk_move_cnt].new_loc = new_blk; + blk_move_cnt++; retval = io_channel_read_blk(fs->io, blk, 1, buf); if (retval) @@ -1048,17 +1049,29 @@ err_out: return retval; } +static int comp_blk(const void *a, const void *b) +{ + struct blk_move *blk_a = (struct blk_move *) a; + struct blk_move *blk_b = (struct blk_move *) b; + + if (blk_a->old_loc < blk_b->old_loc) + return -1; + else if (blk_a->old_loc > blk_b->old_loc) + return 1; + return 0; +} + static blk_t transalate_block(blk_t blk) { - struct list_head *entry; + struct blk_move key; struct blk_move *bmv; - list_for_each(entry, &blk_move_list) { + key.old_loc = blk; + bmv = bsearch(&key, blk_move_list, blk_move_cnt, + sizeof(struct blk_move), comp_blk); - bmv = list_entry(entry, struct blk_move, list); - if (bmv->old_loc == blk) - return bmv->new_loc; - } + if (bmv) + return bmv->new_loc; return 0; } @@ -1297,15 +1310,7 @@ static errcode_t ext2fs_calculate_summary_stats(ext2_filsys fs) static void free_blk_move_list(void) { - struct list_head *entry, *tmp; - struct blk_move *bmv; - - list_for_each_safe(entry, tmp, &blk_move_list) { - - bmv = list_entry(entry, struct blk_move, list); - list_del(entry); - ext2fs_free_mem(&bmv); - } + ext2fs_free_mem(&blk_move_list); return ; } @@ -1318,8 +1323,6 @@ static int resize_inode(ext2_filsys fs, unsigned long new_size) ext2fs_read_inode_bitmap(fs); ext2fs_read_block_bitmap(fs); - INIT_LIST_HEAD(&blk_move_list); - new_ino_blks_per_grp = ext2fs_div_ceil( EXT2_INODES_PER_GROUP(fs->super)*