--PGNNI9BzQDUtgA2J
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline

Hi,

On Thu, Mar 18, 2004 at 03:12:07PM +0100, Ignatios Souvatzis wrote:

> Different problem, I think. As far as I recall, the "find block" algorithm
> uses a hash function, and thus gets ineffective if the table is too full.

Found the reference. From /usr/src/share/doc/smm/05.fastfs:

++++++++++++++++++++++++++++++++++++++++
     If  a requested block is not available, the local allo-
cator uses a four level allocation strategy:

1)   Use the next available block  rotationally  closest  to
     the  requested  block  on  the  same  cylinder.   It is
     assumed here that head switching time is zero.  On disk
     controllers  where this is not the case, it may be pos-
     sible  to  incorporate  the  time  required  to  switch
     between  disk platters when constructing the rotational
     layout tables.  This, however, has not yet been  tried.

2)   If  there are no blocks available on the same cylinder,
     use a block within the same cylinder group.


3)   If that cylinder group is entirely full,  quadratically
     hash the cylinder group number to choose another cylin-
     der group to look for a free block.

4)   Finally if the hash fails, apply an  exhaustive  search
     to all cylinder groups.

  Quadratic  hash is used because of its speed in finding
unused slots in nearly full  hash  tables  [Knuth75].   File
systems that are parameterized to maintain at least 10% free
space rarely use this strategy.  File systems that  are  run
without  maintaining  any  free  space typically have so few
free blocks that almost any allocation is random;  the  most
important  characteristic  of  the  strategy used under such
conditions is that the strategy be fast.

[Knuth75] is TAoCP Vol 3 pp 506-549
++++++++++++++++++++++++++++++++++++++++

--PGNNI9BzQDUtgA2J
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: 2.6.i

iQEVAgUBQFmxKTCn4om+4LhpAQGUywf9FyC0fCTw1qVJ5k+t9DV/rWnJ864vGJSk
qK8i9/aTb9Z4JTQvtlMxwVmmBldWAB9OWFCgDzV6Ey97/j2O8teuDwfBkfPOEgKV
8rsHPnTZnMHTrPW7FnpKaGygC7zKQkeJVyp6KMhymtfzxxOjUunhxfdylmn8KwWI
UoSlNoI3FNeP6qr6dQyjcsiEX536SQuPV98taDj7bZ83WAW4RBNYXm3eyJS65Iuz
KT3dfQK235S6do0EDTVBCHaFapPUodiPN7yMqqJ7mK0pmmm04eU7NtVTujG1rZGY
uQJIfk+j+g4Ylo4m2l9X3kheE6zGmmuKsr5aZJj07C+fqqVq2ah5PA==
=7NOs
-----END PGP SIGNATURE-----

--PGNNI9BzQDUtgA2J--