[Tux3] Encoding of extent information

[Daniel Phillips]

On Wednesday 08 October 2008 00:26, Philip Pokorny wrote:
> >  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.

I haven't thought about it enough to know if it is a problem.  We win
5 bits and it costs some extra extent entries where it is necessary to
represent extent sizes exactly.  At worst, this is fun to think about,
and there might well be something useful there.

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

Thankyou :-)

Anybody capable of coming up with an idea that twisted is more than 
welcome to hang out here.

One thing you might consider: wait a few days for the extent code to
settle down then try coding it up and running some test cases yourself.
That is just what the unit test setup is for: trying out an idea in
isolation.

Notice we have an extent(block, count) function to create and extent
and an extent_count function to extract the count already, and I can
easily add an extent_block function.  These functions are there to hide
the details of packing the extent fields to make it easier to add the
endian conversionts, but now you can use them to try out your idea.
There also has to be higher level logical to avoid generating misaligned
extents, and code to report any that happen to slip through.

Regards,

Daniel

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