Alignment, Padding, and Over-Aligned Allocation

Every allocation interface carries an implicit promise about alignment, and the promise is usually stated once in a standard and then relied upon by every compiler, every structure layout, and every vectorised loop in the program. When a request needs more than that promise, the allocator has to do work that is qualitatively different from its normal path, and the consequences propagate into how the memory can be freed and how much of it is wasted.

The default guarantee and what it costs

C requires malloc to return a pointer suitably aligned for any type with a fundamental alignment requirement. The strictest such requirement among scalar types is that of long double and of max_align_t, which is 16 bytes on the x86-64 System V ABI and on the AArch64 AAPCS64 ABI. So a conforming allocator must return 16-byte-aligned pointers on those targets even for a request of one byte.

That guarantee is not free. Rounding every request up to a 16-byte multiple means a 1-byte request consumes at least the minimum block size, and on a heap with a 16-byte header the smallest block is 32 bytes: half of it metadata, and the payload is one byte. The overhead ratio falls quickly as sizes grow: 16 bytes of waste on a 1 KiB allocation is under 2%, but the small-object regime is where allocation counts are highest, which is why the minimum block size and the alignment quantum are the two numbers that dominate a heap’s space efficiency.

The alignment guarantee also constrains the header layout. If the header sits immediately before the payload and must be found by subtracting a constant from an aligned pointer, the header must itself occupy a multiple of the alignment. A 12-byte header followed by 4 bytes of padding is one alignment unit; a header that is not a whole number of units puts the payload at a variable offset and destroys the arithmetic that free relies on.

There is a further subtlety: alignment is a property of the absolute address, not of the block’s position in some list. A block at offset 16 within a page-aligned span is 16-aligned; a block at offset 24 is only 8-aligned. Allocators that pack objects by size class must therefore choose object sizes that are multiples of the class alignment, which is why class sizes in a segregated heap are almost always multiples of 8 or 16.

Requests stronger than the default

Types with extended alignment need more than malloc promises: SIMD vectors whose ABI requires 32 or 64 bytes, structures padded to a cache line to avoid false sharing, buffers for direct I/O that must start on a page boundary. Three mechanisms exist, and they differ in who is responsible for remembering the original allocation.

posix_memalign takes an alignment and a size, requires the alignment to be a power of two and a multiple of sizeof(void *), and returns the pointer through an out-parameter. C11’s aligned_alloc takes alignment and size in the same call, and additionally requires that size be a multiple of the alignment. Both return memory that free accepts, which means the implementation must have arranged, at allocation time, for recovery to be possible from the aligned pointer alone.

C++17 added an aligned form of operator new and a matching operator delete that takes the alignment as a second argument. That is the interesting case, because it concedes that recovery from the pointer is not always possible: when the delete needs the alignment to find the header, the language passes it. The sized form of delete similarly passes the size, for allocators that store no per-block metadata.

aligned_alloc’s requirement that size be a multiple of alignment is not arbitrary. It makes the rounding exact: if the size is a multiple of the alignment and the block starts aligned, the block ends aligned, so a following block can start aligned with no gap. Relaxing the requirement would mean the allocator either wastes the tail of the block or violates alignment for the next one. posix_memalign has no such restriction, which is one reason it remains the more permissive interface.

The over-allocation pattern

The general implementation technique for an alignment greater than the default is to over-allocate and trim. Ask for size + alignment + header bytes from the underlying allocator, round the address after the header up to the alignment, and store enough information before the aligned pointer to recover the base.

#include <stdint.h>
#include <stdlib.h>

void *aligned_alloc_impl(size_t align, size_t size)
{
    if (align < sizeof(void *) || (align & (align - 1)))
        return NULL;                       /* must be a power of two */
    unsigned char *raw = malloc(size + align + sizeof(void *));
    if (!raw)
        return NULL;
    /* First aligned address that leaves room for the back-pointer. */
    uintptr_t p = ((uintptr_t)raw + sizeof(void *) + align - 1) & ~(uintptr_t)(align - 1);
    ((void **)p)[-1] = raw;                /* record the base for free */
    return (void *)p;
}

The back-pointer slot immediately before the aligned pointer is what makes free work: it reads ((void **)ptr)[-1] to get the original allocation. This is why align must be at least sizeof(void *), otherwise the slot would overlap the payload or land before the raw block. The pattern costs close to align bytes of waste per allocation, the back-pointer slot plus whatever padding the rounding adds, which for a 4096-byte alignment means up to 4 KiB per allocation. For a handful of large buffers that is irrelevant; for a stream of small aligned allocations it is ruinous, and allocators that expect that pattern dedicate whole pages to aligned objects instead.

Dedicating pages removes the padding problem entirely. If the underlying allocator returns page-aligned memory, then any alignment that divides the page size is satisfied by placing the object at a suitable offset within the page, and page-sized alignment is satisfied by returning the page itself. The trade is that a page holding one small aligned object wastes the rest of the page unless the allocator packs multiple aligned objects of the same alignment into it, which is exactly a size class whose objects happen to be aligned.

Page granularity changes the rules

Once the requested alignment reaches the page size, the allocation is structurally a mapping rather than a heap block. A 4 KiB-aligned buffer of 4 KiB is naturally served by one anonymous page; a 2 MiB-aligned buffer is served by a huge page mapping if the kernel can provide one, or by over-mapping and trimming if it cannot.

The reason is that heap spans are themselves page-aligned, so the first object in a span is page-aligned by construction. An allocator can serve page-aligned requests from the start of a span with no padding at all, provided it never splits a span in a way that leaves the requested object at a non-page offset. A span that holds a mix of aligned and unaligned objects cannot make that guarantee, so aligned requests of page granularity are usually served from dedicated spans or from the large-allocation path described in the kernel interface.

Huge pages add a layer. A 2 MiB page must be mapped at a 2 MiB-aligned address, so an allocator using huge pages for its spans obtains them from a region reserved at that alignment. Requests for alignment between the page size and the huge-page size cannot be satisfied by a huge-page span at an arbitrary offset, because the mapping’s alignment is fixed; they must come from ordinary pages or from over-mapping.

There is a performance dimension that has nothing to do with correctness. An object that straddles a cache line boundary costs two cache accesses where one would do, and an object shared between threads that straddles a line shares that line with a neighbour, producing false sharing. Aligning hot per-thread structures to 64 bytes, the common line size, removes both effects. The cost is that padding to a line wastes the tail of each object; for a structure of 68 bytes the padding is 60 bytes, which is why the technique is applied to a small number of hot structures rather than generally.

Failure modes

The arithmetic in the over-allocation pattern is where bugs concentrate.

Overflow. size + align + sizeof(void *) wraps for sizes near SIZE_MAX, producing a small allocation that is then written past. Every implementation must reject sizes above a maximum before adding.

Alignment validation. A non-power-of-two alignment makes the mask arithmetic produce a wrong address; a zero alignment makes align - 1 all ones and the mask zero. Both must be rejected explicitly, and posix_memalign specifies an error return for exactly these cases rather than leaving behaviour undefined.

Free with the wrong function. Memory from posix_memalign must go to free, not to an alignment-aware deallocator; memory from operator new with an alignment must go to the matching operator delete. Mixing them means the deallocator looks for a header at a different displacement and computes a base address that belongs to another block. In C++ this is a real hazard because delete on a pointer from an aligned new is undefined behaviour even though both are “the allocator”.

Slot placement. The back-pointer idiom writes a void * into the eight bytes immediately before the payload. Those bytes lie outside the caller’s object, so the store does not conflict with the payload; the requirement is arithmetic instead. The slot must fall inside the raw allocation, which is why align must be at least sizeof(void *) and why the rounding must leave a full pointer’s worth of headroom before the alignment step. An implementation that instead reuses the first bytes of the payload clobbers the caller’s data on the first write.

The deeper failure mode is the one that cannot be fixed locally: a caller that assumes malloc returns memory aligned to a cache line, or to 4096 bytes, because it happened to observe that on one platform. The guarantee is 16 bytes on the common 64-bit ABIs, and any code relying on more is relying on an implementation detail that changes with the allocator, the size class, and the platform. The alignment promise is the contract; everything above it is a request that must be made explicitly.