The *right* algorithm for determining the amount of free space

[Hugo Mills <hugo@carfax.org.uk>]

[-- Attachment #1: Type: text/plain, Size: 3632 bytes --]

   I know I promised this a while ago and didn't get round to it, but
Henk's tinkering reminded me of it. I note specifically that the
algorithm used to give the free space to plain old df gives incorrect
results -- probably because it's not using the algorithm below.

   There is an algorithm that (seems to) give the correct number of
block groups which can be allocated, given a current allocation state
of the FS. I haven't been able to prove it correct, but it seems to
work. Here's some pseudocode for it:

(Note that all arrays here are 1-based, not 0-based. I originally
wrote this using maths notation, not C. I've got a slightly more
formal write-up of it in LaTeX if anyone wants, but it's full of
unproven crap as well as the description of the algorithm, so I'd
rather edit that before releasing it).

Variables:
   n: Number of devices
   c[n]: Amount of unallocated space on each device
   s: Number of chunks per block group:
        s = 1 for single
        s = 2 for RAID-1
        s = floor(n/2) for RAID-10
        s = n for RAID-0, -5, -6

FUNCTION USABLE(s)
   if RAID0
      return s
   elif RAID1 or SINGLE
      return 1
   elif RAID10
      return s/2
   elif RAID5
      return s-1
   elif RAID6
      return s-2

FUNCTION CHUNKS(n)
   if RAID0 or RAID5 or RAID6
      return n
   elif RAID1
      return 2
   elif RAID10
      return floor(n/2)
   elif SINGLE
      return 1

FUNCTION LOCAL_BOUND(n, c, s, q)
   x := sum( i=q+1..n: c[i] )
   return floor( x / (s-q) )

FUNCTION ALL_BOUNDS(n, c, s)
   r: integer list

   for q=1..n
      if c[q] >= LOCAL_BOUND(n, c, s, q) then
         r.append(c[q])
      endif
   endfor

   return r

FUNCTION BOUND(n, c, s)
   total := ( sum i=1..n (c[i]) )
   return min(floor( total / s ), ALL_BOUNDS(n, c[n], s))

FUNCTION ALLOCATE(n, c, s)
   # Reduce the free space by the maximum amount possible with s-sized
   # allocations.
   r[n]: integer

   b := BOUND(n, c, s) * s
   for i=n..1
      a := min(c[i], floor( b/i ))
      b := b - a
      r[i] := c[i] - a

   return r

FUNCTION SPACE(n, c)
   s := CHUNKS(n)
   total := 0
   while BOUND(n, c, s) > 0
      # Increase the amount of usable space in this pass
      total := total + BOUND(n, c, s)*USABLE(s)
      c := ALLOCATE(n, c, s)

      # Find the new number of usable devices
      n := 0
      while c[n+1] != 0
         n := n + 1
      s := CHUNKS(n)

   return total

   The algorithm works by setting up the list of free space, c, one
entry for each device in the FS, and sorting it in decreasing
order. The values should be measured in chunks -- so divide the free
space on each device by 1 GiB. Devices with no free space should be
dropped from the list.

   The parameter s is dependent on the RAID level. See the list above
for what it should be set to.

   The BOUND function determines the number of block group allocations
possible for a given configuration, c, and stripe size, s. Multiply
the number of allocations by s to get the number of chunks that can be
allocated.

   The ALLOCATE function returns the list of free space on each device
after the maximum number of block groups has been allocated. This
should be called repeatedly, updating the value of s each time, until
no more allocations are possible.

   I hope that's of use to someone with more spare coding time than
me. And maybe we can finally have free space estimation that gets it
right...

   Hugo.

-- 
Hugo Mills             | A gentleman doesn't do damage unless he's paid for
hugo@... carfax.org.uk | it.
http://carfax.org.uk/  |
PGP: E2AB1DE4          |                                            Juri Papay

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]