[BK PATCH] Add ext3 indexed directory (htree) support

tytso
2002-09-25T19:59:01Z

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.)