<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
<META NAME="Generator" CONTENT="MS Exchange Server version 6.5.7651.59">
<TITLE>Encoding of extent information</TITLE>
</HEAD>
<BODY>
<!-- Converted from text/plain format -->
<P><FONT SIZE=2>I was wondering how you were encoding the length into "unused" bits of the extent pointers.<BR>
<BR>
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.<BR>
<BR>
I wonder if you have ever heard of this alternate encoding for extents. It depends on several assumptions:<BR>
<BR>
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).<BR>
<BR>
2. Extents can only be of size 2^n<BR>
<BR>
3. An extent of size 2^n is aligned on a 2^n addressable unit boundry.<BR>
<BR>
For a filesystem, these would seem to be reasonable assumptions.<BR>
<BR>
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"<BR>
<BR>
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).<BR>
<BR>
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.<BR>
<BR>
To illustrate:<BR>
<BR>
N = 200 is a 16 block extent from 192 to 207<BR>
<BR>
it can be devided into two 8 block extents: N=196 (192-199) and N=204 (200-207)<BR>
or into four 4 block extents: N=194 (192-195), N=198 (196-199), N=202 (200-203), N=206 (204-207)<BR>
or finally into eight 2 block extents: N= 193, 195, 197, 199, 201, 203, 205, 207<BR>
<BR>
Just a thought...<BR>
<BR>
--<BR>
Philip Pokorny, RHCE<BR>
Technical Director - Penguin Computing<BR>
Voice: 415-370-0835 Toll free: 888-PENGUIN<BR>
www.penguincomputing.com<BR>
<BR>
</FONT>
</P>
</BODY>
</HTML>