[Tux3] Encoding of extent information

[Philip Pokorny]

Daniel Phillips wrote:
> On Sunday 05 October 2008 23:33, Philip Pokorny wrote:
>   
>> For any given number N (except 0) that describes an extent, the first unit in the extent is given by the expression "N & (N-1)", the last unit is "N | (N-1)" and the width of the extent is "(N ^ (N-1))+1"
>>
>> Forcing extents to be aligned on 2^n boundaries of the underlying block device should improve I/O to composite devices like RAID arrays (which have 2^n "chunk" sizes).
>>
>> This scheme imposes no limit on the size of an extent and with no sacrifice of high order bits.  Further, using this scheme low-order bits can be used for other purposes at the cost of a larger minimum extent width.  Current filesystems are generally limited to 4k block sizes which would allow for 2 low-order bits for "special purposes" which would be masked off before the above expressions.
>>
>> To illustrate:
>>
>> N = 200   is a 16 block extent from 192 to 207
>>
>> it can be devided into two 8 block extents: N=196 (192-199) and N=204 (200-207)
>> or into four 4 block extents: N=194 (192-195), N=198 (196-199), N=202 (200-203), N=206 (204-207)
>> or finally into eight 2 block extents:  N= 193, 195, 197, 199, 201, 203, 205, 207
>>
>> Just a thought...
>>     
>
> Wow, that is diabolical,
Thank you [grin]

>  it is certainly worth thinking about.  There
> may be other benefits of the alignment restriction, such as helping
> control fragmentation.
It does make the fragmentation somewhat predictable.  For a given extent 
of a given size, the extent "next door" must be the same size or smaller 
if it's a candidate for merging the two into a larger extent.

> But does it not require more extents to
> represent odd sized files at the short end of the scale?
I suppose it requires log2(n) extents at most for any "odd" length of an 
extent.  Specifically the number of "1" bits in the binary 
representation is the number of extents required and their position 
tells you what length of extent is required.  So yes, in the general 
case, you would probably have more extents.  Given the predictability of 
the sizes, this might not be as much of an issue.  For a filesystem, the 
requirement that extents be a power of 2 in length might be a 
significant down-side to this scheme.

> Out of curiosity, where did you run into this?
>   
I believe it's my own idea.  It's something I've been thinking about for 
some time.  The magic properties of the expressions are something I read 
most recently in Donald Knuth's new "chapters" for his next book.  I had 
seen them before that, but the large number of combinations and 
descriptions in that paper helped fire the imagination when I worked out 
the actual encoding.

You're welcome to use the idea.

Phil P.

-- 
Philip Pokorny, RHCE, Chief Arch. & Sr. Dir. HW & Field Eng.
Tel: 415-954-2823   Cell: 415-370-0835
Fax: 415-954-2899   Toll Free: 888-PENGUIN
PENGUIN COMPUTING, INC.
www.penguincomputing.com


_______________________________________________
Tux3 mailing list
Tux3 at tux3.org
http://tux3.org/cgi-bin/mailman/listinfo/tux3