Re: Ext2fs and hashed table.

Stephen C. Tweedie (sct@dcs.ed.ac.uk)
03 Jun 1997 22:36:39 +0100


Hi all,

smurf@work.smurf.noris.de (Matthias Urlichs) writes:

> R.E.Wolff@BitWizard.nl (Rogier Wolff) writes:
> >
> > You know, apple's fast filesystem (HFS, whatever that stands for)
> > uses btrees. But it has a unified name space. Thus
> >
> "Unified name space" isn't quite right. It's just that all the directory
> entries are stored in one big file, with one inode, instead of one file per
> directory.
>
> Much more interesting, is the fact that the file's position on disk are
> stored as <block number,length> tuples (the first three are stored in the
> "inode", the rest in another big b-tree), not as a direct/indirect/whatever
> list of blocks. I'd like to see that (minus the b-tree) as an ext2fs
> extension, just to see whether it speeds things up any. It should,
> especially for big files

It's already on the ext2fs TODO list. :) Yes, it will speed things
up, mainly by reducing the size of the indirect mapping data structure
and hence the number of IOs required to map a block.

The main problem with this technique is that it completely falls apart
when you consider Unix semantics for files with holes --- you end up
having to reshuffle the entire extent map any time you insert new data
by writing into a hole. The current plan is simply to convert
on-the-fly from extent mapped to direct indexed block mapping if such
a write occurs.

Other related improvements are also planned at the same time,
including caching of the most recently used extent and passing of
extents through the VFS layer with an "emap()" function analogous to
the current "bmap" block mapping function. Both of these will help to
significantly reduce the CPU overhead of block mapping requests.

Cheers,
Stephen.