TLS> Date: Sun, 23 Apr 2006 16:17:32 -0400
TLS> From: Thor Lancelot Simon

TLS> Extents would be a lot more sensible than the current block -- plus up
TLS> to 8 sizes of fragments, but only 8 -- plus some new giant-block scheme;
TLS> and eliminating multiple levels of block indirection would eliminate a
TLS> major source of bugs in the code.

How concerned are we about locality of reference between files in a 
directory?

Rather than a stride-N allocator, what about a logarithmic one that
splits the largest available block in half and uses that?

e.g., take something with 256 storage units.  Allocate 3, 10, 9, 1, 7,
8, 2, and 55 units as follows:

 3 @ 127 - 129
10 @  58 -  67
 9 @ 193 - 201
 1 @ 161 - 161
 7 @  94 - 100
 8 @  25 -  32
 2 @ 228 - 229
55 @ **problem** (no contiguous chunk; switch time-->space or defrag)

At this point, the storage looks like:

Free:    0 -  24 = 25 (F)
Used:   25 -  32 =  8 (U)
Free:   33 -  57 = 25 (F)
Used:   58 -  67 = 10 (U)
Free:   68 -  93 = 26 (F)
Used:   94 - 100 =  7 (U)
Free:  101 - 126 = 26 (F)
Used:  127 - 129 =  3 (U)
Free:  130 - 160 = 31 (F)
Used:  161 - 161 =  1 (U)
Free:  162 - 192 = 31 (F)
Used:  193 - 201 =  9 (U)
Free:  202 - 227 = 26 (F)
Used:  228 - 229 =  2 (U)
Free:  230 - 255 = 26 (F)

Note how moving a single file could easily furnish enough free space for
the 55-unit file.  A more advanced algorithm might track files that
frequently change size and give them more "wiggle room" for growth.

A stride-N allocator would have several small chunks and one/few big
ones available.  Conversely, this method gives many medium-sized
offerings.

"Inodes" could be stored in a single file, which could grow like any
other.  (I'm compelled to mention that the C-64 stored the directory in
the disk center.)

One problem I foresee: Heapifying the free space could involve many I/O
operations.  Perhaps inode-file requests could be batched?


Just thinking out loud...
Eddy
--
Everquick Internet - http://www.everquick.net/
A division of Brotsman & Dreger, Inc. - http://www.brotsman.com/
Bandwidth, consulting, e-commerce, hosting, and network building
Phone: +1 785 865 5885 Lawrence and [inter]national
Phone: +1 316 794 8922 Wichita
________________________________________________________________________
DO NOT send mail to the following addresses:
davidc@brics.com -*- jfconmaapaq@intc.net -*- sam@everquick.net
Sending mail to spambait addresses is a great way to get blocked.
Ditto for broken OOO autoresponders and foolish AV software backscatter.