Re: [IDEA] - run-length compaction of block numbers
From: Hans Reiser
Date: Fri Jan 16 2004 - 15:49:24 EST
Valdis.Kletnieks@xxxxxx wrote:
On Fri, 16 Jan 2004 11:38:59 PST, raymond jennings <highwind747@xxxxxxxxxxx> said:
Is there any value in creating a new filesystem that encodes long contiguous
blocks as a single block run instead of multiple block numbers? A long file
may use only a few block runs instead of many block numbers if there is
little fragmentation (usually the case).
This is already done, they are called "extent"s. Reiser4 uses them, XFS
uses them, I think Veritas may have been the first to use them but I am
not sure of this, maybe it was IBM.
Also dynamic allocation of
inodes...etc.
ReiserFS does dynamic allocation of stat data (what stat() returns), we
don't have inodes. Many filesystems do dynamic allocation of inodes.
The details are long; anyone interested can e-mail me
privately.
Only question I have is how you make an efficient scheme for finding the block
number for an offset several gigabytes into the file.
Use a tree to store everything in. See www.namesys.com for extensive
details.
You either get to run
through the list linearly (gaak) or you need to stick a tree or hash on the
front to allow semi-random access to a starting point to scan linearly from, at
which point you've probably blown any space savings unless you have a VERY low
fragmentation rate...
On the other hand, dynamic allocation of inodes is interesting, as it means
you're not screwed if over time, the NBPI value for the filesystem changes (or
if you simply guessed wrong at mkfs time) and you run out of inodes when you
still have space free. Reiserfs V3 already does this, in fact...
Cheers,
--
Hans
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/