From patchwork Sun Nov 25 00:36:34 2012 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Theodore Ts'o X-Patchwork-Id: 201501 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.180.67]) by ozlabs.org (Postfix) with ESMTP id CE9462C0093 for ; Sun, 25 Nov 2012 11:42:41 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752788Ab2KYAmk (ORCPT ); Sat, 24 Nov 2012 19:42:40 -0500 Received: from li9-11.members.linode.com ([67.18.176.11]:34512 "EHLO imap.thunk.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752678Ab2KYAmk (ORCPT ); Sat, 24 Nov 2012 19:42:40 -0500 Received: from root (helo=closure.thunk.org) by imap.thunk.org with local-esmtp (Exim 4.72) (envelope-from ) id 1TcQIj-0003u7-Oq; Sun, 25 Nov 2012 00:42:25 +0000 Received: by closure.thunk.org (Postfix, from userid 15806) id 9AD7C246FF9; Sat, 24 Nov 2012 19:36:34 -0500 (EST) From: Theodore Ts'o To: Ext4 Developers List Cc: Theodore Ts'o Subject: [PATCH 6/6] e2fsck: optimize pass 5 for CPU utilization Date: Sat, 24 Nov 2012 19:36:34 -0500 Message-Id: <1353803794-11593-7-git-send-email-tytso@mit.edu> X-Mailer: git-send-email 1.7.12.rc0.22.gcdd159b In-Reply-To: <1353803794-11593-1-git-send-email-tytso@mit.edu> References: <1353803794-11593-1-git-send-email-tytso@mit.edu> X-SA-Exim-Connect-IP: X-SA-Exim-Mail-From: tytso@thunk.org X-SA-Exim-Scanned: No (on imap.thunk.org); SAEximRunCond expanded to false Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org Add a fast past optimization in e2fsck's pass 5 for the common case where the block bitmap is correct. The optimization works by extracting each block group's block allocation bitmap into a memory buffer, and comparing it with the expected allocation bitmap using memcmp(). If it matches, then we can just update the free block counts and be on our way, and skip checking each bit individually. Addresses-Google-Bug: #7534813 Signed-off-by: "Theodore Ts'o" Reviewed-by: Lukas Czerner --- e2fsck/pass5.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 53 insertions(+), 2 deletions(-) diff --git a/e2fsck/pass5.c b/e2fsck/pass5.c index 8312fe0..5aff55c 100644 --- a/e2fsck/pass5.c +++ b/e2fsck/pass5.c @@ -212,6 +212,12 @@ static void check_block_bitmaps(e2fsck_t ctx) int cmp_block = 0; int redo_flag = 0; blk64_t super_blk, old_desc_blk, new_desc_blk; + char *actual_buf, *bitmap_buf; + + actual_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize, + "actual bitmap buffer"); + bitmap_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize, + "bitmap block buffer"); clear_problem_context(&pctx); free_array = (unsigned int *) e2fsck_allocate_memory(ctx, @@ -259,11 +265,53 @@ redo_counts: for (i = B2C(fs->super->s_first_data_block); i < ext2fs_blocks_count(fs->super); i += EXT2FS_CLUSTER_RATIO(fs)) { + int first_block_in_bg = (B2C(i) - + B2C(fs->super->s_first_data_block)) % + fs->super->s_clusters_per_group == 0; + int n, nbytes = fs->super->s_clusters_per_group / 8; + actual = ext2fs_fast_test_block_bitmap2(ctx->block_found_map, i); + /* + * Try to optimize pass5 by extracting a bitmap block + * as expected from what we have on disk, and then + * comparing the two. If they are identical, then + * update the free block counts and go on to the next + * block group. This is much faster than doing the + * individual bit-by-bit comparison. The one downside + * is that this doesn't work if we are asking e2fsck + * to do a discard operation. + */ + if (!first_block_in_bg || + (group == (int)fs->group_desc_count - 1) || + (ctx->options & E2F_OPT_DISCARD)) + goto no_optimize; + + retval = ext2fs_get_block_bitmap_range2(ctx->block_found_map, + B2C(i), fs->super->s_clusters_per_group, + actual_buf); + if (retval) + goto no_optimize; + if (ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT)) + memset(bitmap_buf, 0, nbytes); + else { + retval = ext2fs_get_block_bitmap_range2(fs->block_map, + B2C(i), fs->super->s_clusters_per_group, + bitmap_buf); + if (retval) + goto no_optimize; + } + if (memcmp(actual_buf, bitmap_buf, nbytes) != 0) + goto no_optimize; + n = ext2fs_bitcount(actual_buf, nbytes); + group_free = fs->super->s_clusters_per_group - n; + free_blocks += group_free; + i += fs->super->s_clusters_per_group - 1; + goto next_group; + no_optimize: + if (skip_group) { - if ((B2C(i) - B2C(fs->super->s_first_data_block)) % - fs->super->s_clusters_per_group == 0) { + if (first_block_in_bg) { super_blk = 0; old_desc_blk = 0; new_desc_blk = 0; @@ -401,6 +449,7 @@ redo_counts: if (!bitmap && i >= first_free) e2fsck_discard_blocks(ctx, first_free, (i - first_free) + 1); + next_group: first_free = ext2fs_blocks_count(fs->super); free_array[group] = group_free; @@ -475,6 +524,8 @@ redo_counts: } errout: ext2fs_free_mem(&free_array); + ext2fs_free_mem(&actual_buf); + ext2fs_free_mem(&bitmap_buf); } static void check_inode_bitmaps(e2fsck_t ctx)