Memory Alignment

CPUs access memory most efficiently when data is aligned to its natural boundary.

What is Alignment?

An address is "N-byte aligned" if it's divisible by N.

0x1000 - 16-byte aligned (1000 / 16 = 256)
0x1008 - 8-byte aligned, NOT 16-byte aligned
0x1004 - 4-byte aligned only
0x1001 - 1-byte aligned (everything is)

Why Alignment Matters

1. Performance: Misaligned access crosses cache lines, requires multiple fetches
2. Correctness: Some CPUs trap on misaligned access (SIGBUS)
3. SIMD: SSE/AVX instructions require 16/32/64-byte alignment

malloc's Guarantee

Standard malloc must return memory aligned for any built-in type:

// Must work for any type
double *d = malloc(sizeof(double));  // 8-byte aligned
long double *ld = malloc(sizeof(long double));  // 16-byte aligned on x86-64

On 64-bit systems, this typically means 16-byte alignment.

aligned_alloc for Custom Alignment

Sometimes you need more:

// Allocate with 64-byte alignment (cache line)
void *p = aligned_alloc(64, 1024);

// Allocate with 4096-byte alignment (page)
void *p = aligned_alloc(4096, 8192);

Implementing aligned_alloc

The Challenge

malloc gives you some address. You need a specific alignment.

malloc returns: 0x1004
You need:       0x1040 (64-byte aligned)
Gap:            60 bytes wasted

Strategy

1. Allocate extra space: size + alignment - 1 + sizeof(void*)
2. Find aligned address within that space
3. Store original pointer just before aligned address
4. Return aligned address

void *my_aligned_alloc(size_t alignment, size_t size) {
    // Validate
    if (!is_power_of_two(alignment)) return NULL;
    if (alignment < sizeof(void*)) alignment = sizeof(void*);

    // Allocate with extra room
    size_t total = size + alignment - 1 + sizeof(void*);
    void *raw = malloc(total);
    if (!raw) return NULL;

    // Find aligned address (after space for storing raw ptr)
    uintptr_t raw_addr = (uintptr_t)raw + sizeof(void*);
    uintptr_t aligned = (raw_addr + alignment - 1) & ~(alignment - 1);

    // Store original pointer
    ((void**)aligned)[-1] = raw;

    return (void*)aligned;
}

The Alignment Formula

aligned = (addr + alignment - 1) & ~(alignment - 1);

How it works (for 16-byte alignment):

• alignment - 1 = 0x0F = 0000 1111
• ~(alignment - 1) = 0xFFF...F0 = mask
• Adding alignment - 1 ensures we reach or pass the boundary
• ANDing with mask clears low bits (rounds down to boundary)

Freeing Aligned Memory

void my_aligned_free(void *ptr) {
    if (!ptr) return;
    void *raw = ((void**)ptr)[-1];  // Retrieve original
    free(raw);
}

Memory Layout

+------+--------+----------+------------------+
| hdr  | unused | raw_ptr  | aligned data ... |
+------+--------+----------+------------------+
^                ^         ^
raw              aligned-8 aligned (returned)