linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* Ext2 directory index, updated
@ 2001-11-04  2:28 Daniel Phillips
  2001-11-04  2:44 ` Daniel Phillips
  2001-11-04 22:09 ` Christian Laursen
  0 siblings, 2 replies; 19+ messages in thread
From: Daniel Phillips @ 2001-11-04  2:28 UTC (permalink / raw)
  To: linux-kernel

***N.B.: still for use on test partitions only.***

This update mainly fixes a bug, a one-in-a-million occurance on an untested 
code path.  This bug resulted in rm -rf deleting all files but one from a 
million-file directory.  I believe that's the last untested code path, and 
otherwise it's been very stable.

I didn't expect highmem to work properly, and it didn't.  It's on my to-do 
list, but for now highmem has to be off or you will oops on boot.

I elaborated the dx_show_buckets debug output to show dump the full index 
tree instead of just one level.  This function now serves as a capsule 
summary of the index tree structure, and as you can see, it's simple.

I've done quite a bit more testing, including stress testing on a real 
machine and I find that everything works quite comfortably up to about 2 
million files, turning in an average time of about 50 microseconds/create and 
300 microseconds/delete (1 GHz PIII).  In the 4 million file range things go 
pear-shaped, which I believe is not due to the index patch, but to rd.  The 
runs do complete, but require exponentially more time, with cpu 98% idle and 
block throughput in the 300/second range.  I'll look into that more later.

I did run into some bad mm behavior on 2.4.13.  The icache seems to be too 
severely throttled, resulting in delete performance being less than it should 
be.  I also find I am rarely unable to create a million file test run on uml 
(2.4.13) without oom-ing.  In my experience, such problems are not due to 
uml, but to the kernel's memory manager.  These issues may have been 
addressed in recent pre-patch kernels, but it seems there is a still some 
room for improvement in mm stability.

The patch is available at:

  http://nl.linux.org/~phillips/htree/ext2.index-2.4.13

To apply:

  cd /your/source/tree
  patch -p0 <this.patch

--
Daniel


^ permalink raw reply	[flat|nested] 19+ messages in thread
* Ext2 Directory Index, updated
@ 2002-03-04 11:03 Daniel Phillips
  0 siblings, 0 replies; 19+ messages in thread
From: Daniel Phillips @ 2002-03-04 11:03 UTC (permalink / raw)
  To: linux-kernel

After some considerable time letting this patch 'age', here's an update
to 2.4.18:

   http://people.nl.linux.org/~phillips/htree/htree-2.4.18

The diff to 2.4.17 was provided by Ted Ts'o, and bug hunting/fixing by
Chris Li (who has the rather interesting email address
<chrisl@gnuchina.org>).  Chris is working on the Ext3 port as well.

Bill Irwin is providing loving care and attention to the hash function, so I 
feel it's in good hands.

Known Bug:

  - highmem doesn't work (because the kmapping code is wrong)

To Do:

  - Finalize hash function.
  - Coalesce on delete.  I have to do this sooner rather than later,
    since hash bucket fragmentation leads quickly to reduced leaf
    fullness.
  - Stable telldir cookie for NFS
  - Ext2 util updates (in progress, Ted Ts'o)
  - Miscellaneous source cleanups

Because of the unfinalized hash function, this patch is still for testing 
only.

-- 
Daniel

^ permalink raw reply	[flat|nested] 19+ messages in thread
* Ext2 directory index, updated
@ 2001-11-02  3:36 Daniel Phillips
  2001-11-02  5:04 ` Andreas Dilger
  0 siblings, 1 reply; 19+ messages in thread
From: Daniel Phillips @ 2001-11-02  3:36 UTC (permalink / raw)
  To: linux-kernel

Here is the htree directory index patch for ext2, updated to 2.4.13.  
***N.B.: still for use on test partitions only.***

I ran it through some basic tests, up to half a million files/directory, 
without problems.  There are still a few minor warts to clean up, including 
still not having settled on a final-final hash function, although it looks 
likely that it's going to end up being dx_hack_hash, with a more respectable 
name.

I'm not 100% sure I've handled kmap/highmem correctly, and I haven't checked 
that yet.

This patch is just a snapshot of my work-in-progress.  There will be an 
update in another day or so, and a to-do list.  There are a few extra hash 
functions in the code from various sources, including reiserfs and bitkeeper, 
which I'll remove in the next update.  Those who find this kind of thing 
interesting may find these... interesting.

The patch is available at:

  http://nl.linux.org/~phillips/htree/ext2.index-2.4.13

To apply:

  cd /your/source/tree
  patch -p0 <this.patch

--
Daniel

^ permalink raw reply	[flat|nested] 19+ messages in thread

end of thread, other threads:[~2002-03-04 11:07 UTC | newest]

Thread overview: 19+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2001-11-04  2:28 Ext2 directory index, updated Daniel Phillips
2001-11-04  2:44 ` Daniel Phillips
2001-11-04 22:09 ` Christian Laursen
2001-11-04 22:24   ` Daniel Phillips
2001-11-04 22:54     ` Christian Laursen
2001-11-04 23:01     ` Daniel Phillips
2001-11-04 23:09       ` Gábor Lénárt
2001-11-05 22:10       ` Andreas Dilger
2001-11-06  0:38         ` Daniel Phillips
2001-11-05  1:43   ` Daniel Phillips
2001-11-05  7:48     ` Ville Herva
2001-11-05  9:53       ` Daniel Phillips
2001-11-05 22:59     ` Christian Laursen
2001-11-05 23:13       ` Daniel Phillips
2001-11-05 23:45         ` Andreas Dilger
2001-11-08  7:21     ` Christian Laursen
  -- strict thread matches above, loose matches on Subject: below --
2002-03-04 11:03 Ext2 Directory Index, updated Daniel Phillips
2001-11-02  3:36 Ext2 directory index, updated Daniel Phillips
2001-11-02  5:04 ` Andreas Dilger

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