= Allocation alignment padding
<Allocation alignment padding> is the unused space inserted before an allocated payload so its address meets <memory alignment>. If a free extent starts at integer <byte> address $a$, an allocation header consumes $h$ <bytes>, and payload addresses must be multiples of positive integer $A$, the earliest permitted address and its padding are
$$
p=A\left\lceil\frac{a+h}{A}\right\rceil,\qquad
P=p-(a+h).
$$
Equivalently, $P$ is the least nonnegative residue of $-(a+h)$ modulo $A$. The <alignment padding bound> is $0\le P\le A-1$. Already aligned payload starts have zero padding; adding a whole extra alignment unit in that case would waste space unnecessarily.
For an original example, let a free extent be $[3,67)$, with $h=8$ and $A=16$. Then $a+h=11$, $p=16$ and $P=5$ <bytes>. A24-<byte> payload ends at40, so the used prefix occupies37 <bytes>:8 for the header,5 for padding and24 for data. The remaining interval $[40,67)$ has27 <bytes> before other block-rounding or <minimum free-block size> requirements are applied. This accounting distinguishes padding from header storage and from payload-size rounding.
The same header and alignment can produce different padding at another address: $a=8$ gives $a+h=16$ and $P=0$. If the residues of $a+h$ were uniformly distributed over all16 possibilities, the mean padding would be7.5 <bytes>, obtained by averaging0 through15. An actual allocator can constrain its block starts, so that distribution is an explicit model assumption rather than a measured universal overhead.
<Aligned free-block capacity> must deduct this padding when testing whether a request fits. <Allocation alignment padding> can thus make two equally long free extents offer different usable capacities. OSTEP's separation of the allocated payload from its bookkeeping header is the basic layout issue behind this calculation; alignment adds the stated address constraint.<Operating Systems: Three Easy Pieces by Remzi H. Arpaci-Dusseau and others>[Chapter17, §17.2, “Tracking The Size Of Allocated Regions”, printed pp.5–6]{ref}
Back to article page
