From patchwork Tue Mar 2 19:27:16 2010 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: number9652 X-Patchwork-Id: 46703 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 78FBCB7D46 for ; Wed, 3 Mar 2010 06:27:20 +1100 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1751601Ab0CBT1R (ORCPT ); Tue, 2 Mar 2010 14:27:17 -0500 Received: from n62.bullet.mail.sp1.yahoo.com ([98.136.44.35]:26091 "HELO n62.bullet.mail.sp1.yahoo.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S1751427Ab0CBT1Q (ORCPT ); Tue, 2 Mar 2010 14:27:16 -0500 Received: from [216.252.122.217] by n62.bullet.mail.sp1.yahoo.com with NNFMP; 02 Mar 2010 19:27:16 -0000 Received: from [69.147.65.155] by t2.bullet.sp1.yahoo.com with NNFMP; 02 Mar 2010 19:27:16 -0000 Received: from [127.0.0.1] by omp403.mail.sp1.yahoo.com with NNFMP; 02 Mar 2010 19:27:16 -0000 X-Yahoo-Newman-Property: ymail-3 X-Yahoo-Newman-Id: 343574.69655.bm@omp403.mail.sp1.yahoo.com Received: (qmail 47209 invoked by uid 60001); 2 Mar 2010 19:27:16 -0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=yahoo.com; s=s1024; t=1267558036; bh=U05jdjWXQa1oAhyz4DSn2wsuCbaMhsTt4/jP2xSgUjg=; h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:MIME-Version:Content-Type; b=3mHIhCGym2vQ0zdlV3lOoPQM8rbwxMhoazsDTqctgyDxss4eykOQjFLu6NgadvDYNfrtyUmrXRNS/A7xgxl2VaGxi3rx5nT6Ug2xJdleQsQ6k36K7d1U8VVmFuR6gJyWIt4hoInV4OTqpqufG7GbXE4zBxF67su1DeBs5jYLcHU= DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=s1024; d=yahoo.com; h=Message-ID:X-YMail-OSG:Received:X-Mailer:Date:From:Subject:To:MIME-Version:Content-Type; b=GDPbxugPj7IXHkCqPCLept1e5wGtertRzfm66pGRUb/Ts/cd5XNlc+pFFT4A2KlZw64OhOmpBjAogolPx3R+G75aZVMI1PZI8TZHCqIayIn/ihhpsVauIKyPZr3YNQ3cwitpQDaWnJsXXuJaKOq53zrWB6AliuCc9tlrhRhpmnw=; Message-ID: <155285.46961.qm@web43507.mail.sp1.yahoo.com> X-YMail-OSG: 17dI3EUVM1klnJnAbtLppwWaiIij9Xa18GfQkMD9WKmgyvz9uQPNrDWGPHR_EoCBp3cLSfcAa1svIwMgTTDNpDuyp80yfkUo0coT.IbH1D8K6kqX_AY4jAG_d2HZdFcbLStXUvdQcun4MClxP92BTklhh1TyFu8UKyezeQ5BilT6cd0K_Qj3RF_JuJZ8gM0_LQ4_Oi.JJaJc.V7pBBLtMdIIMX_7WR0ljVkhYN6f7oGQiKcGL8EjBCS0f8WTDGGnZvBpcvIVze8eLVDEZJsPvXxwwGHigkw2Pl0HQJexkUD6R9xemeA22JXABTYHDCrc7RmOIOi0JA-- Received: from [173.9.226.29] by web43507.mail.sp1.yahoo.com via HTTP; Tue, 02 Mar 2010 11:27:16 PST X-Mailer: YahooMailClassic/9.2.12 YahooMailWebService/0.8.100.260964 Date: Tue, 2 Mar 2010 11:27:16 -0800 (PST) From: Nic Case Subject: [PATCH] libext2fs: fix ext2fs_extent_get when going to the next or previous extent To: linux-ext4@vger.kernel.org MIME-Version: 1.0 Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org Because this patch fixes the handling of the EXT2_EXTENT_NEXT flag in ext2fs_extent_get, it fixes the performance issue noticed when creating large journals with mkfs. When ext2fs_extent_get was called with the EXT2_EXTENT_NEXT flag on the last extent, the handle would get altered to point to the extent above the original extent, which would cause a subsequent call to ext2fs_extent_get to begin at the wrong extent. Also, when ext2fs_extent_get was called with the EXT2_EXTENT_PREV flag, the wrong extent could be found if the original extent was at level 0 and not the first entry. When ext2fs_extent_get is called with the EXT2_EXTENT_NEXT flag when there is no next sibling, it should try to go up until it finds a next sibling, then it should return that sibling. If it goes up and doesn't find a sibling, the handle should still point to the original extent to allow the caller to take appropriate action. When ext2fs_extent_get is called with the EXT2_EXTENT_PREV flag on a file with a three-level extent tree when the handle currently points at the second entry of level 0, it should return the last entry under the first entry of level 0, which would be at level 2. Any time it should go down in the tree, it should go to the leaf level. If called with EXT2_EXTENT_PREV_LEAF with the original extent being the first leaf, the function should go up until it sees there is no previous leaf, then set the handle back to the original extent and return. Signed-off by Nic Case --- To unsubscribe from this list: send the line "unsubscribe linux-ext4" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html --- lib/ext2fs/extent-orig.c 2010-02-05 08:58:41.000000000 -0600 +++ lib/ext2fs/extent.c 2010-03-02 12:47:00.000000000 -0600 @@ -287,7 +287,7 @@ errcode_t retval; blk_t blk; blk64_t end_blk; - int orig_op, op; + int orig_op, op, orig_level; EXT2_CHECK_MAGIC(handle, EXT2_ET_MAGIC_EXTENT_HANDLE); @@ -295,6 +295,7 @@ return EXT2_ET_NO_CURRENT_NODE; orig_op = op = flags & EXT2_EXTENT_MOVE_MASK; + orig_level = handle->level; retry: path = handle->path + handle->level; @@ -309,16 +310,20 @@ op = EXT2_EXTENT_NEXT_SIB; else if (handle->level > 0) op = EXT2_EXTENT_UP; - else + else { + handle->level = orig_level; return EXT2_ET_EXTENT_NO_NEXT; + } } else { /* leaf node */ if (path->left > 0) op = EXT2_EXTENT_NEXT_SIB; else if (handle->level > 0) op = EXT2_EXTENT_UP; - else + else { + handle->level = orig_level; return EXT2_ET_EXTENT_NO_NEXT; + } } if (op != EXT2_EXTENT_NEXT_SIB) { #ifdef DEBUG_GET_EXTENT @@ -340,8 +345,10 @@ op = EXT2_EXTENT_PREV_SIB; else if (handle->level > 0) op = EXT2_EXTENT_UP; - else + else { + handle->level = orig_level; return EXT2_ET_EXTENT_NO_PREV; + } } else { /* leaf node */ if (path->left < path->entries-1) @@ -417,12 +424,16 @@ case EXT2_EXTENT_UP: if (handle->level <= 0) return EXT2_ET_EXTENT_NO_UP; + path->visit_num = 0; handle->level--; path--; ix = path->curr; if ((orig_op == EXT2_EXTENT_PREV) || (orig_op == EXT2_EXTENT_PREV_LEAF)) path->visit_num = 0; + if ((orig_op == EXT2_EXTENT_NEXT) || + (orig_op == EXT2_EXTENT_NEXT_LEAF)) + path->visit_num = 1; break; case EXT2_EXTENT_DOWN: case EXT2_EXTENT_DOWN_AND_LAST: @@ -536,6 +547,16 @@ (path->left != 0))) goto retry; + if (((orig_op == EXT2_EXTENT_NEXT_LEAF) || + (orig_op == EXT2_EXTENT_NEXT)) && + (op == EXT2_EXTENT_UP)) + goto retry; + + if ((orig_op == EXT2_EXTENT_PREV) && + (op == EXT2_EXTENT_PREV_SIB) && + (handle->level != handle->max_depth)) + goto retry; + return 0; }