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

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

[Hugo Mills]

[-- 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 --]

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

[Hugo Mills]

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

On Fri, Mar 11, 2016 at 10:17:03PM +0000, Hugo Mills wrote:
>    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:

   I forgot to mention, there's a JavaScript implementation of this
algorithm at:

http://carfax.org.uk/btrfs-usage/js/btrfs-usage.js

   Hugo.

-- 
Hugo Mills             | You can play with your friends' privates, but you
hugo@... carfax.org.uk | can't play with your friends' childrens' privates.
http://carfax.org.uk/  |
PGP: E2AB1DE4          |                                       C++ coding rule

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

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

[David Sterba]

On Fri, Mar 11, 2016 at 10:17:03PM +0000, Hugo Mills wrote:
>    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.

So the algorithm is supposed to implement btrfs_calc_avail_data_space,
the raid5/6 parts are missing from there, otherwise the structure of the
function follows the proposed algorithm.

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

It does sound correct to me. Thanks for writing it up.

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

[Hugo Mills]

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

On Fri, Mar 18, 2016 at 06:58:02PM +0100, David Sterba wrote:
> On Fri, Mar 11, 2016 at 10:17:03PM +0000, Hugo Mills wrote:
> >    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.
> 
> So the algorithm is supposed to implement btrfs_calc_avail_data_space,
> the raid5/6 parts are missing from there, otherwise the structure of the
> function follows the proposed algorithm.

   Well, the current code gets the free space estimation wrong even
with RAID-1. It's not usually *very* wrong, but it's still not right,
somewhere.

> >    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:
> 
> It does sound correct to me. Thanks for writing it up.

   Hugo.

-- 
Hugo Mills             | Great films about cricket: The Umpire Strikes Back
hugo@... carfax.org.uk |
http://carfax.org.uk/  |
PGP: E2AB1DE4          |

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