= 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$. With
$$
p=A\left\lceil\frac{x}{A}\right\rceil,\qquad P=p-x,
$$
the 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.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others>[Chapter17, §17.2, allocation header versus payload, printed pp.5–6]{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.
Back to article page
