Re: [IDEA] - run-length compaction of block numbers
From: raymond jennings
Date: Thu Jan 29 2004 - 11:43:59 EST
Well, here's the basic idea. There are four types of "block runs":
Direct runs
Indirect runs
Null runs
Zero runs
struct blockrun_t {
blocknum_t logstart, loglength;
blocknum_t phystart, phylength;
}
Direct runs are determined by nonzero and equal logical and physical
numbers. The only way this can happen is for the run to directly reference
data blocks (I think, some crazy cases can be guarded against).
Indirect runs have a larger logical count than the physical count, meaning
that the referenced blocks actually comprise a list of more block runs.
Functionally equivalent to an indirect block.
Null runs have a zero logical length and are useful as padding. The logical
start should be consistent with surrounding runs to allow binary searching.
Zero runs are a quick and dirty implementation of sparse files. They are
given by a PHYSICAL zero, meaning that the actual data blocks are not stored
on disk. reads of these "blocks" return zeroes.
The top level inode contains eight or so of these runs, listed in logical
block start order (binary searchable). The indirect runs thereof reference
other runs, which may reference others (and so on). Blocks could be as
small as 512 (saves space)
these top level block runs form what is a block chain. It could be as large
or as small as needed.
The superblock contains a blockchain of its own, but this "block chain"
references the dynamic inode space, thus, inodes are only limited by the
range of an inode number (probably 2G), or the amount of space. Unused
inodes could even be sparsified.
fsck.rle will have its work cut out for it however. I suggest that block
chains be abstracted. Manipulating the raw block runs should be left to the
discretion of the rlefs library (if there is one).
If this has already been implemented, feel free to use my suggestions to
improve them (or not). I am unfortunate enough to not have enough space to
unpack my kernel source, so I can't very well keep up :(. I'm running a
system on a mere 212MB hard disk, with gcc, g++, ncurses (devel too), jed,
joe, init, initscripts, mingetty, and midnight commander, and I only have
7.5MB of space left. Naturally, I can't afford swap space :O. This only
happened because my stupid 2GB HD suffered a short circuit, which caused the
dreaded head crash. That's my sob story. Thank's for listening.
Is the
From: Hans Reiser <reiser@xxxxxxxxxxx>
To: Valdis.Kletnieks@xxxxxx
CC: raymond jennings <highwind747@xxxxxxxxxxx>,
linux-kernel@xxxxxxxxxxxxxxx
Subject: Re: [IDEA] - run-length compaction of block numbers
Date: Fri, 16 Jan 2004 23:47:55 +0300
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
_________________________________________________________________
Check out the coupons and bargains on MSN Offers!
http://shopping.msn.com/softcontent/softcontent.aspx?scmId=1418
-
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/