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). Also dynamic allocation of
inodes...etc. The details are long; anyone interested can e-mail me
privately.
_________________________________________________________________
Rethink your business approach for the new year with the helpful tips here.
http://special.msn.com/bcentral/prep04.armx
"raymond jennings" <[email protected]> writes:
> 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).
> Also dynamic allocation of inodes...etc. The details are long; anyone
> interested can e-mail me privately.
Congratulations. You just reinvented the basic specs of JFS and XFS.
-Andi
On Fri, 16 Jan 2004 11:38:59 PST, raymond jennings <[email protected]> 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). Also dynamic allocation of
> inodes...etc. 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. 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...
On Fri, 16 Jan 2004 11:38:59 -0800 "raymond jennings" <[email protected]> wrote:
| 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). Also dynamic allocation of
| inodes...etc. The details are long; anyone interested can e-mail me
| privately.
You mean line ext3fs + extents, or like JFS or XFS, which use extents?
--
~Randy
Everything is relative.
[email protected] wrote:
>On Fri, 16 Jan 2004 11:38:59 PST, raymond jennings <[email protected]> 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 http://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
[email protected] wrote:
>
> 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...
>
As does JFS. Anyone know about XFS?
--
========================================================================
Ian Pilcher [email protected]
========================================================================
On Fri, Jan 16, 2004 at 02:36:03PM -0600, Ian Pilcher wrote:
> [email protected] wrote:
> >
> >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...
> >
>
> As does JFS. Anyone know about XFS?
Yes, XFS has dynamic inodes also.
On Fri, 16 Jan 2004 23:47:55 +0300, Hans Reiser said:
> 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.
Does the extent-based disk allocation used by OS/360 in 1964 count? :)
[email protected] wrote:
>On Fri, 16 Jan 2004 23:47:55 +0300, Hans Reiser said:
>
>
>
>>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.
>>
>>
>
>Does the extent-based disk allocation used by OS/360 in 1964 count? :)
>
>
Probably. Tell me more about it.
--
Hans
On Mon, 19 Jan 2004 13:45:29 +0300, Hans Reiser said:
> >Does the extent-based disk allocation used by OS/360 in 1964 count? :)
> >
> >
> Probably. Tell me more about it.
Well, basically, a dataset was described by an entry in the Volume Table of
Contents (VTOC) with a something conceptually similar to an inode. The actual
data area was described with a initial allocation, and up to 15 additional
"extents" (yes, hard limit of 15 extents per volume, although a dataset could
span volumes). Each extent was described with start/end cylinder/track pairs.
You could allocate space by absolute tracks, by tracks, or by cylinders (of
course, space actually allocated was dependent on the device). So you could
code in the JCL something like SPACE=(CYL,(10.5)) which would allocate 10
cylinders and up to 15 additional 5-cylinder spaces. And yes, it was quite
possible to get hosed on fragementation.
The first 3 allocations were contained in the 'format 1' DSCB (Data Set
Control Block), and additional extents were in a 'format 3' DSCB. Free
space was described in extents in a series of chained 'format 4' DSCB's.
(A single DSCB was only 140 bytes, so there's a lot of chaining;).
I don't know how IBM did disk space management on the earlier systems
such as the 1401, 7040, and 7090 series, but I'd suspect it was a similar
extent-based method.
So extents were around at the beginning of filesystems, and then
forgotten by Unix for a while.... interesting....
--
Hans
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 <[email protected]>
>To: [email protected]
>CC: raymond jennings <[email protected]>,
>[email protected]
>Subject: Re: [IDEA] - run-length compaction of block numbers
>Date: Fri, 16 Jan 2004 23:47:55 +0300
>
>[email protected] wrote:
>
>>On Fri, 16 Jan 2004 11:38:59 PST, raymond jennings
>><[email protected]> 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 http://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