Re: [IDEA] - run-length compaction of block numbers

[Hans Reiser <reiser@namesys.com>]

Valdis.Kletnieks@vt.edu wrote:

>On Fri, 16 Jan 2004 11:38:59 PST, raymond jennings <highwind747@hotmail.com>  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