[Tux3] Encoding of extent information

[Daniel Phillips]

On Sunday 05 October 2008 23:33, Philip Pokorny wrote:
> I was wondering how you were encoding the length into "unused" bits of the extent pointers.
> 
> I've seen you use high-order bits elsewhere in your design, so I assume you took 6 bits from the top of the pointer thinking that 2^58 should be big enough for a block pointer.
> 
> I wonder if you have ever heard of this alternate encoding for extents.  It depends on several assumptions:
> 
> 1. The minimum extent size is 2x the addressable unit size.  In the case of a block device with 512 byte sectors, that would be a 1k minimum extent (2 sectors).
> 
> 2. Extents can only be of size 2^n
> 
> 3. An extent of size 2^n is aligned on a 2^n addressable unit boundry.
> 
> For a filesystem, these would seem to be reasonable assumptions.
> 
> 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, it is certainly worth thinking about.  There
may be other benefits of the alignment restriction, such as helping
control fragmentation.   But does it not require more extents to
represent odd sized files at the short end of the scale?  Which is not
necessarily a problem - we might find it useful to allocate a little
more extent space than actually needed anyway.  It needs a quite a bit
more analysis.  The scheme does save bits all right.  Very interesting.

Out of curiosity, where did you run into this?

Regards,

Daniel


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