linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: tytso@mit.edu
To: torvalds@transmeta.com
Cc: linux-kernel@vger.kernel.org
Subject: [BK PATCH] Add ext3 indexed directory (htree) support
Date: Wed, 25 Sep 2002 16:03:44 -0400	[thread overview]
Message-ID: <E17uINs-0003bG-00@think.thunk.org> (raw)

Hi Linus,

This changeset contains Daniel Phillip's indexed directory changes,
ported to 2.5 by Christopher Li and Andrew Morton, and then extensively
cleaned up by me.  I also implemented the enhanced dx_readdir code which
returns files would be returned in hash order.  This was necessary so
that concurrent tree splits would not result in filenames to be
erroneously returned twice or not at all when the b-tree splits
reorganized the directory out from underneath readdir().

This patch significantly increases the speed of using large directories.
Creating 100,000 files in a single directory took 38 minutes without
directory indexing... and 11 seconds with the directory indexing turned on.

I've given this code a good bit of testing, under both 2.4 and 2.5
kernels, and believe that it is ready for prime-time.  Please pull it
from:

	bk://extfs.bkbits.net/for-linus-htree-2.5

In order to use the new directory indexing feature, please update your
e2fsprogs to 1.29.  Existing filesystem can be updated to use directory
indexing using the command "tune2fs -O dir_index /dev/hdXXX".  This can
be done while the filesystem is mounted, and subsequent new directories
or directories fit within a single block will be use the new (backwards
compatible) dirctory indexing format when they grow beyond a single
block.

Existing large directories on the filesystem can be converted to use the
new indexed directory format by running the following command on an
unmounted filesystem "e2fsck -fD /dev/hdXXX".  

							- Ted

 fs/ext3/Makefile           |    2 
 fs/ext3/dir.c              |  298 ++++++++++
 fs/ext3/file.c             |    3 
 fs/ext3/hash.c             |  215 +++++++
 fs/ext3/namei.c            | 1305 ++++++++++++++++++++++++++++++++++++++++-----
 fs/ext3/super.c            |    6 
 include/linux/ext3_fs.h    |   86 ++
 include/linux/ext3_fs_sb.h |    2 
 include/linux/ext3_jbd.h   |    2 
 include/linux/rbtree.h     |    1 
 lib/rbtree.c               |   16 
 11 files changed, 1797 insertions(+), 139 deletions(-)

(The changes to rbtree.c were to add a new function rb_first(), which
returns the first node in the rbtree.)

             reply	other threads:[~2002-09-25 19:59 UTC|newest]

Thread overview: 47+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2002-09-25 20:03 tytso [this message]
2002-09-25 20:34 ` Andreas Dilger
2002-09-25 20:41 ` Dave Jones
2002-09-25 21:08   ` Andreas Dilger
2002-09-25 21:34   ` Theodore Ts'o
2002-09-25 22:54 ` Jeff Garzik
2002-09-25 23:29   ` Theodore Ts'o
2002-09-25 23:45     ` Ryan Cumming
2002-09-26  3:27       ` Theodore Ts'o
2002-09-26  5:23         ` Ryan Cumming
2002-09-26  5:57           ` Theodore Ts'o
2002-09-26  6:22             ` Ryan Cumming
2002-09-26 14:05               ` Theodore Ts'o
2002-09-26  6:25             ` Ryan Cumming
2002-09-26 11:25               ` Daniel Egger
2002-09-26  7:41             ` Ryan Cumming
2002-09-26 13:23               ` Theodore Ts'o
2002-09-26 15:42               ` Theodore Ts'o
2002-09-26 19:08                 ` Ryan Cumming
2002-09-26 19:51                   ` Horst von Brand
2002-09-26 19:59                     ` Ryan Cumming
2002-09-26 22:04                   ` Theodore Ts'o
2002-09-26 22:53                     ` Ryan Cumming
2002-09-26 23:57                       ` Theodore Ts'o
2002-09-27  1:00                         ` Ryan Cumming
2002-09-27  3:24                           ` Theodore Ts'o
2002-09-27  4:12                         ` Andreas Dilger
2002-09-27  7:55                           ` Ryan Cumming
2002-09-28  1:20                           ` Ryan Cumming
2002-09-28  1:46                             ` Ryan Cumming
2002-09-28 14:13                             ` Theodore Ts'o
2002-09-28 14:18                               ` Theodore Ts'o
2002-09-28 22:35                                 ` Ryan Cumming
2002-09-28 17:27                               ` [Ext2-devel] " Andreas Dilger
2002-09-28 18:43                                 ` chrisl
2002-09-28 19:45                                 ` chrisl
2002-09-28 22:30                               ` Ryan Cumming
2002-09-29  7:03                               ` [PATCH] fix htree dir corrupt after fsck -fD chrisl
2002-09-29  8:16                                 ` Ryan Cumming
2002-09-29  8:36                                   ` Ryan Cumming
2002-09-30  2:46                                   ` Ryan Cumming
2002-09-29 14:13                                 ` Theodore Ts'o
2002-09-25 23:31 ` [BK PATCH] Add ext3 indexed directory (htree) support Daniel Egger
2002-09-26  0:32   ` Randy.Dunlap
2002-09-26  0:50 ` Aaron Lehmann
2002-09-26  3:28   ` Theodore Ts'o
2002-10-02  9:11 tytso

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=E17uINs-0003bG-00@think.thunk.org \
    --to=tytso@mit.edu \
    --cc=linux-kernel@vger.kernel.org \
    --cc=torvalds@transmeta.com \
    --subject='Re: [BK PATCH] Add ext3 indexed directory (htree) support' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).