From patchwork Sat Aug 22 14:20:49 2009 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andreas Schlick X-Patchwork-Id: 31871 Return-Path: X-Original-To: patchwork-incoming@bilbo.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from ozlabs.org (ozlabs.org [203.10.76.45]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (Client CN "mx.ozlabs.org", Issuer "CA Cert Signing Authority" (verified OK)) by bilbo.ozlabs.org (Postfix) with ESMTPS id 03B0EB7B75 for ; Sun, 23 Aug 2009 00:26:51 +1000 (EST) Received: by ozlabs.org (Postfix) id E9F94DDD0B; Sun, 23 Aug 2009 00:26:50 +1000 (EST) 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 2F163DDD04 for ; Sun, 23 Aug 2009 00:26:49 +1000 (EST) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932520AbZHVO0o (ORCPT ); Sat, 22 Aug 2009 10:26:44 -0400 Received: (majordomo@vger.kernel.org) by vger.kernel.org id S932774AbZHVO0o (ORCPT ); Sat, 22 Aug 2009 10:26:44 -0400 Received: from karen.lavabit.com ([72.249.41.33]:57731 "EHLO karen.lavabit.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932520AbZHVO0n (ORCPT ); Sat, 22 Aug 2009 10:26:43 -0400 Received: from c.earth.lavabit.com (c.earth.lavabit.com [192.168.111.12]) by karen.lavabit.com (Postfix) with ESMTP id 576B911B895; Sat, 22 Aug 2009 09:26:45 -0500 (CDT) Received: from 78.52.132.213 (78.52.132.213) by lavabit.com with ESMTP id LJQTLICMVIS4; Sat, 22 Aug 2009 09:26:45 -0500 DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=lavabit; d=lavabit.com; b=IsNiLXdXzJsI2KNjMXc9xt3x+G6MfU11PrFOlaEC9oKAM7s/YHGxOrUukD/a1LEJjrAfsbLYjqJbQoBkc3k1Apt6RixYPaJW2JwThkNOYMedUcbnzghGXQf2gRsk/h/zHsILGujaxfY7epICv9IH5cISYoqIBQ5ZTbG+XYPLGxo=; h=From:To:Subject:Date:User-Agent:References:In-Reply-To:MIME-Version:Content-Disposition:Content-Type:Content-Transfer-Encoding:Message-Id; From: Andreas Schlick To: Theodore Tso , linux-ext4@vger.kernel.org Subject: [PATCH 1/1] dir shrink (was Re: ext3/ext4 directories don't shrink after deleting lots of files) Date: Sat, 22 Aug 2009 16:20:49 +0200 User-Agent: KMail/1.9.10 References: <1242338523.6933.664.camel@timo-desktop> <605A8D56-81CD-4775-8FCD-58CDB12CBA36@iki.fi> <20090517213335.GB32019@mit.edu> In-Reply-To: <20090517213335.GB32019@mit.edu> MIME-Version: 1.0 Content-Disposition: inline Message-Id: <200908221620.50103.schlick@lavabit.com> Sender: linux-ext4-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-ext4@vger.kernel.org Hello, > Anyway, if there's someone interested in trying to implement this, > give me a holler; I'd be happy to give more details as necessary. I'd like to try it. It looks like a nice starting project. Following your outline the first version of the patch tries to remove an empty block at the end of a non-htree directory. I'd appreciate it if you checked it and gave me suggestions for improving it. At the moment I am looking at the dir_index code, so I can extend it to htree directories. Please let me know if you want me to port it to ext3, although personally I think it is better to do so at later point. Greetings Andreas [PATCH] ext4: Add a function to shrink directories by removing last empty block. Current limitations: It only works on directories that don't use htree and will only remove the last block (if it is not used). Signed-off-by: Andreas Schlick --- fs/ext4/namei.c | 70 +++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 files changed, 65 insertions(+), 5 deletions(-) diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c index 1855060..04ac43d 100644 --- a/fs/ext4/namei.c +++ b/fs/ext4/namei.c @@ -79,6 +79,13 @@ static struct buffer_head *ext4_append(handle_t *handle, #define dxtrace(command) #endif +// ext4_dir_cleanup holds information for ext4_shrink_directory(..). +// At the moment it is only a pointer to the directory's inode but this +// will change in later versions of the patch. +struct ext4_dir_cleanup { + struct inode *dir; +}; + struct fake_dirent { __le32 inode; @@ -1684,7 +1691,8 @@ cleanup: static int ext4_delete_entry(handle_t *handle, struct inode *dir, struct ext4_dir_entry_2 *de_del, - struct buffer_head *bh) + struct buffer_head *bh, + struct ext4_dir_cleanup *dc) { struct ext4_dir_entry_2 *de, *pde; unsigned int blocksize = dir->i_sb->s_blocksize; @@ -1711,6 +1719,9 @@ static int ext4_delete_entry(handle_t *handle, dir->i_version++; BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata"); ext4_handle_dirty_metadata(handle, dir, bh); + if (dc) { + dc->dir = dir; + } return 0; } i += ext4_rec_len_from_disk(de->rec_len, blocksize); @@ -1989,6 +2000,49 @@ static int empty_dir(struct inode *inode) return 1; } +/* + * This function tries to shrink the size of a directory. + * + * The current limitations are that it checks only the last block + * and only works on non-indexed directories. + */ +static void ext4_shrink_directory(struct ext4_dir_cleanup *dc) { + struct inode *dir = dc->dir; + struct buffer_head *bh; + struct ext4_dir_entry_2 * de; + char * dlimit; + ext4_lblk_t lblock; + int err=0; + + lblock = dir->i_size >> EXT4_BLOCK_SIZE_BITS(dir->i_sb); + + // We don't handle indexed dirs at the moment and need at least two blocks + if (is_dx(dir) || lblock <= 1) { + return; + } + + bh = ext4_bread(NULL, dir, (lblock-1), 0, &err); + + if (!bh) { + return; + } + + de = (struct ext4_dir_entry_2 *) bh->b_data; + dlimit = bh->b_data + dir->i_sb->s_blocksize; + while ((char *) de < dlimit) { + if (de->inode) { + brelse(bh); + return; + } + de = ext4_next_entry(de, EXT4_BLOCK_SIZE(dir->i_sb)); + } + + brelse(bh); + + dir->i_size -= EXT4_BLOCK_SIZE(dir->i_sb); + ext4_truncate(dir); +} + /* ext4_orphan_add() links an unlinked or truncated inode into a list of * such inodes, starting at the superblock, in case we crash before the * file is closed/deleted, or in case the inode truncate spans multiple @@ -2145,6 +2199,7 @@ static int ext4_rmdir(struct inode *dir, struct dentry *dentry) struct inode *inode; struct buffer_head *bh; struct ext4_dir_entry_2 *de; + struct ext4_dir_cleanup dc; handle_t *handle; /* Initialize quotas before so that eventual writes go in @@ -2172,7 +2227,7 @@ static int ext4_rmdir(struct inode *dir, struct dentry *dentry) if (!empty_dir(inode)) goto end_rmdir; - retval = ext4_delete_entry(handle, dir, de, bh); + retval = ext4_delete_entry(handle, dir, de, bh, &dc); if (retval) goto end_rmdir; if (!EXT4_DIR_LINK_EMPTY(inode)) @@ -2195,6 +2250,7 @@ static int ext4_rmdir(struct inode *dir, struct dentry *dentry) end_rmdir: ext4_journal_stop(handle); brelse(bh); + ext4_shrink_directory(&dc); return retval; } @@ -2204,6 +2260,7 @@ static int ext4_unlink(struct inode *dir, struct dentry *dentry) struct inode *inode; struct buffer_head *bh; struct ext4_dir_entry_2 *de; + struct ext4_dir_cleanup dc; handle_t *handle; /* Initialize quotas before so that eventual writes go @@ -2233,7 +2290,7 @@ static int ext4_unlink(struct inode *dir, struct dentry *dentry) inode->i_ino, inode->i_nlink); inode->i_nlink = 1; } - retval = ext4_delete_entry(handle, dir, de, bh); + retval = ext4_delete_entry(handle, dir, de, bh, &dc); if (retval) goto end_unlink; dir->i_ctime = dir->i_mtime = ext4_current_time(dir); @@ -2249,6 +2306,7 @@ static int ext4_unlink(struct inode *dir, struct dentry *dentry) end_unlink: ext4_journal_stop(handle); brelse(bh); + ext4_shrink_directory(&dc); return retval; } @@ -2369,6 +2427,7 @@ static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry, struct inode *old_inode, *new_inode; struct buffer_head *old_bh, *new_bh, *dir_bh; struct ext4_dir_entry_2 *old_de, *new_de; + struct ext4_dir_cleanup dc; int retval, force_da_alloc = 0; old_bh = new_bh = dir_bh = NULL; @@ -2459,7 +2518,7 @@ static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry, old_de->name_len != old_dentry->d_name.len || strncmp(old_de->name, old_dentry->d_name.name, old_de->name_len) || (retval = ext4_delete_entry(handle, old_dir, - old_de, old_bh)) == -ENOENT) { + old_de, old_bh, &dc)) == -ENOENT) { /* old_de could have moved from under us during htree split, so * make sure that we are deleting the right entry. We might * also be pointing to a stale entry in the unused part of @@ -2470,7 +2529,7 @@ static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry, old_bh2 = ext4_find_entry(old_dir, &old_dentry->d_name, &old_de2); if (old_bh2) { retval = ext4_delete_entry(handle, old_dir, - old_de2, old_bh2); + old_de2, old_bh2, &dc); brelse(old_bh2); } } @@ -2519,6 +2578,7 @@ end_rename: brelse(old_bh); brelse(new_bh); ext4_journal_stop(handle); + ext4_shrink_directory(&dc); if (retval == 0 && force_da_alloc) ext4_alloc_da_blocks(old_inode); return retval;