 Alignment padding bound

The alignment padding bound limits the extra bytes needed to move an integer payload address to the next permitted memory alignment. Let $x=a+h$ be the first address after an allocated header, and let alignment require a multiple of a positive integer $A$. Withthe exact bound is $0\le P\le A-1$. It applies to the earliest aligned start, not to arbitrary extra space an allocator may choose to reserve.

To prove the bound, write $k=\lceil x/A\rceil$. The ceiling function gives $k-1<x/A\le k$, hence $0\le Ak-x<A$. Since $P=Ak-x$ is an integer number of bytes, $P\le A-1$. The endpoints can occur: an already aligned $x$ gives zero padding, while $x$ one byte beyond an aligned address gives $A-1$. This is also the statement that $P$ is the least nonnegative residue of $-x$ in modular arithmetic.

For an original example, $A=16$, header size $h=8$ and block start $a=9$ give $x=17$, $p=32$ and $P=15$. The worst-case bound is attained. Starting at $a=8$ instead gives $x=16$ and $P=0$. Identical header and payload sizes can therefore incur different allocation alignment padding at different addresses.

A sufficient address-independent reservation for a payload of $R$ bytes is $h+(A-1)+R$, before any trailer, block rounding or minimum free-block size constraint. For $h=8$, $A=16$ and $R=24$,47 bytes suffice under precisely that layout. A known starting address can require less: $a=3$ needs5 bytes of padding and a37-byte used prefix. Separating the payload from its metadata is the bookkeeping principle illustrated in OSTEP; the bound adds a worst-case alignment allowance.^[ref]

These inequalities concern mathematical integers. An implementation using bounded address arithmetic must separately prevent integer overflow when adding the header, padding allowance or payload. A wrapped sum cannot be justified by a correct bound over unbounded integers.