Skip to contentSkip to conversation

- run-length compaction of block numbers

IDEA raymond jennings 7 participants 11 messages Jan 16, 2004 – Feb 8, 2004

lore
Share & tools
lore
#0 lore raw

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

#1 lore raw
Quoted 6 lines · raymond jennings

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

#2 lore raw
Quoted 6 lines · [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?

Signature · 3 lines
========================================================================
Ian Pilcher                                        [email protected]
========================================================================
#3 lore raw
Quoted 11 lines · Ian Pilcher
Quoted 8 lines · [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.

#4 lore raw
In reply to [email protected]
Quoted 5 lines · [email protected] wrote:
Quoted 2 lines · raymond jennings

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.

Quoted 2 lines
Quoted 2 lines

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.

Quoted 8 lines
Quoted 4 lines

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.

Quoted 6 lines

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

Quoted 7 lines

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,

Signature · 1 line
Hans
#5 lore raw
Quoted 3 lines · Hans Reiser

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? :)

#6 lore raw
Quoted 11 lines · [email protected] wrote:
Quoted 3 lines · Hans Reiser

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.

Signature · 1 line
Hans
#7 lore raw
Quoted 4 lines · Hans Reiser
Quoted 3 lines

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.

#8 lore raw

So extents were around at the beginning of filesystems, and then forgotten by Unix for a while.... interesting....

Signature · 1 line
Hans
#9 lore raw
In reply to [email protected]
Quoted 3 lines · On Mon, 19 Jan 2004 11:20:51 -0500, [email protected] wrote:

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.

<old-fogey-mode>

Can't speak for the 1401 or 7xxx series. IBM 1620[*], which was obsolete back in 1977 when I programmed it, also used extent based disk directories. There were three directory areas on disk, one to map file names to extent indexes, one to map the used extents on the disk and one to map the free space extents.

[*] Binary coded decimal. Each digit had 4 numeric bits plus two flag
bits. Two adjacent digits made a letter (and you thought that Unicode was bad!). Card punch or paper tape in/out. No printer, feed the cards through a separate machine for that. 20,000 digits of memory with a 2 Mb disk drive was a big machine.

Five digit addressing with one nice feature, if the flag bit was set on the rightmost digit of an address then it was automatically treated as an indirect address and the real address was fetched from the area referenced by this address, the real address could also be flagged as indirect and the process would continue. The IBM manual claimed that indirect addresses required no extra time (nothing changes about computer claims :). The student's idea of fun was to load all of memory with indirect addresses, each pointing to the next with loop around. Refer to the first and watch the big panel lights slowly cycle through all of memory doing nothing useful.

</old-fogey-mode>

#10 lore raw
In reply to raymond jennings

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.