How to align on the right - partition alignment algorithm

 In MSDOS 6.22 there are alignment restrictions for partitions. This means a partition of size capacity = /start - end/ = end - start, partition boundaries (start, end) must coincide with certain boundaries; in this case cylinder boundaries.

The following alignment algorithm is taken from the libvirt virtualization API.

In short, the algorithm will make sure allocated continuous space is aligned on the right, that is on the end. If the available free space for alignment already starts at a given boundary value, it will be fully aligned [1].

We'll have:

1. Input: c := capacity, l := alignment interval, s := start
2. Output: e := end

All of these values are in ZZ (actually NN). For e: c <= e - s; e + 1 = n*l (for some natural n), that is, the required capacity fits into the allocated space and the end is aligned while it must end one unit before the next interval starts.

Let r := l - (c mod l). We understand r as the extra space required to reach the interval boundary, e.g. if l is 512 (think of sector size) and I need to allocate capacity 618, then 1*l won't cover c, instead I'd have to used 2*l = 1024 >= 618. But then I have 1024 - 618 = 406 = 512 - (618 mod 512) of extra space I need to allocate that wasn't really required.

The algorithm handles three cases:

1. s = m*l, for some m (the start is aligned at a boundary)
2. s != m*l; s mod l <= r (the start offset fits into the extra space reserved for alignment)
3. s != m*l; s mod l > r (the start offset doesn't fit) 

For 1. the correct e is quite easy, we already know how much extra space to align and subtract 1 to have the partition end just before the next boundary in order to have the next partition start exactly at boundary.

(1)    e = s + c + r - 1

This is the base for the other two cases.

For 2. (1) would surpass the boundary:

boundary=s       ...         s+c          boundary=s+c+r

         |                ...           |                        |

boundary          s         ...       s+c   boundary       s+c+r

         |               |                      |                |              |

But we know that s mod l <= r, therefore s+c+r - s mod l >= s + c proving that the alignment on the right would fit the required capacity. Thus:

(2)    e = s + c + r - s mod l - 1

And e is still on boundary: e = s + c + r - s mod l - 1 =  (c + r) + (s - s mod l) - 1 = n_1*l + n_2*l - 1.

Now for 3. from the above,   e - s = s + c + r - s mod l - s = c + r - s mod l < c. If we originally had defined r to be 2*l - (c mod l), then e - s > c. But we didn't do that because for 1. and 2. that would be a waste of space. However, here for 3. we don't have another choice, so we add another l:

(3)    e = s + c + r + l - s mod l - 1

In the referenced algorithm, you'll see that s mod l is always subtracted. Let's keep in mind that s is at a boundary iff s mod l = 0. So we can actually summarize

                 

(4)    e = s + c + r + d - s mod l - 1, where d := 0 if s mod l < r, else d := l.

QED.

[1]  I wonder if the need for a first partition not starting exactly at the second cylinder to save space or some other MSDOS restrictions are the reason for not aligning the partition start, too.