[Tux3] Encoding of extent information

[Philip Pokorny]

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

-- 
Philip Pokorny, RHCE
Technical Director - Penguin Computing
Voice: 415-370-0835  Toll free: 888-PENGUIN
www.penguincomputing.com

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://phunq.net/pipermail/tux3/attachments/20081005/e9cb90f1/attachment.html>
-------------- next part --------------
_______________________________________________
Tux3 mailing list
Tux3 at tux3.org
http://tux3.org/cgi-bin/mailman/listinfo/tux3