Aligned Memory Allocation

hard · memory, alignment, optimization

Aligned Memory Allocation

Standard malloc guarantees 8-byte alignment. But sometimes you need stronger guarantees:

SIMD instructions (SSE/AVX) require 16/32/64-byte alignment
DMA buffers may require page alignment (4096 bytes)
Cache-line alignment (64 bytes) for performance

The Problem

void *p = my_malloc(100);  // Might return 0x1004
// 0x1004 is NOT 32-byte aligned
// For SIMD, you need 0x1020 (next 32-byte boundary)

Your Task

Implement aligned allocation:

#define BLOCK_MAGIC 0xDEADBEEF

// Check if n is a power of 2
int is_power_of_two(size_t n);

// Round up n to next multiple of alignment
size_t align_up(size_t n, size_t alignment);

// Allocate 'size' bytes with 'alignment' byte alignment
void *my_aligned_alloc(size_t alignment, size_t size);

// Free an aligned allocation
void my_aligned_free(void *ptr);

Strategy

Allocate more than needed: size + alignment - 1 + sizeof(void*)
Find the first aligned address within that region
Store original pointer just before aligned address (for freeing)
Return the aligned pointer

Memory layout:
+----------+--------+----------------+---------------+
| orig_hdr | unused | orig_ptr store | aligned data  |
+----------+--------+----------------+---------------+
^                   ^                ^
original_ptr        aligned-8        returned (aligned)

Critical Test: Alignment Must Be Correct

void *p = my_aligned_alloc(32, 100);
assert(p != NULL);
assert(((uintptr_t)p % 32) == 0);  // Must be 32-byte aligned!

// Use the memory
memset(p, 0xAB, 100);

my_aligned_free(p);  // Must find original pointer!

Finding Aligned Address

// alignment must be power of 2
uintptr_t addr = (uintptr_t)ptr;
uintptr_t aligned = (addr + alignment - 1) & ~(alignment - 1);

The formula works because:

Add alignment - 1 to reach or pass next boundary
AND with ~(alignment - 1) clears lower bits (rounds down)

Storing Original Pointer

To free correctly, store the original pointer just before the aligned address:

// Store original just before aligned
void **ptr_storage = (void**)(aligned_addr - sizeof(void*));
*ptr_storage = original;

// Later, to free:
void *original = ((void**)aligned_ptr)[-1];
my_free(original);

Constraints

alignment must be power of 2 (return NULL otherwise)
alignment must be >= sizeof(void*) to store original pointer

#include <stddef.h>
#include <stdint.h>
#include <unistd.h>

#define BLOCK_MAGIC 0xDEADBEEF
#define MIN_BLOCK_SIZE (sizeof(block_header_t) + 16)

typedef struct block_header {
    size_t size;
    int free;
    unsigned int magic;
    struct block_header *next;
} block_header_t;

block_header_t *free_list_head = NULL;

// ============================================
// Base allocator (provided)
// ============================================

static size_t align8(size_t size) {
    return (size + 7) & ~7;
}

static void *get_payload(block_header_t *block) {
    return (void*)(block + 1);
}

static block_header_t *get_block(void *ptr) {
    return ((block_header_t*)ptr) - 1;
}

static int is_valid_block(void *ptr) {
    if (ptr == NULL) return 0;
    block_header_t *block = get_block(ptr);
    return block->magic == BLOCK_MAGIC;
}

static block_header_t *get_last_block(void) {
    if (free_list_head == NULL) return NULL;
    block_header_t *curr = free_list_head;
    while (curr->next != NULL) curr = curr->next;
    return curr;
}

static block_header_t *find_free_block(size_t size) {
    block_header_t *current = free_list_head;
    while (current != NULL) {
        if (current->free && current->size >= size) {
            return current;
        }
        current = current->next;
    }
    return NULL;
}

static block_header_t *request_space(size_t size) {
    size_t total = sizeof(block_header_t) + size;
    block_header_t *block = sbrk((intptr_t)total);
    if (block == (void*)-1) return NULL;

block->size = size;
    block->free = 0;
    block->magic = BLOCK_MAGIC;
    block->next = NULL;

if (free_list_head == NULL) {
        free_list_head = block;
    } else {
        get_last_block()->next = block;
    }
    return block;
}

void *my_malloc(size_t size) {
    if (size == 0) return NULL;

size_t aligned = align8(size);
    block_header_t *block = find_free_block(aligned);

if (block != NULL) {
        block->free = 0;
        return get_payload(block);
    }

block = request_space(aligned);
    if (block == NULL) return NULL;
    return get_payload(block);
}

void my_free(void *ptr) {
    if (ptr == NULL) return;
    if (!is_valid_block(ptr)) return;

block_header_t *block = get_block(ptr);
    block->free = 1;
}

// ============================================
// YOUR TASK: Implement aligned allocation
// ============================================

// Check if n is a power of 2
int is_power_of_two(size_t n) {
    // TODO: Return 1 if n is a power of 2, 0 otherwise
    // Hint: A power of 2 has exactly one bit set
    // n & (n - 1) == 0 for powers of 2 (and n > 0)
    return 0;
}

// Round up 'n' to next multiple of 'alignment'
size_t align_up(size_t n, size_t alignment) {
    // TODO: Return n rounded up to next multiple of alignment
    // Hint: (n + alignment - 1) & ~(alignment - 1)
    // This works because alignment is a power of 2
    return 0;
}

// Allocate 'size' bytes with 'alignment' byte alignment
void *my_aligned_alloc(size_t alignment, size_t size) {
    // TODO: Implement aligned allocation
    //
    // Validation:
    // 1. alignment must be power of 2
    // 2. alignment must be >= sizeof(void*) to store original ptr
    // 3. size of 0 may return NULL
    //
    // Strategy:
    // 1. Allocate extra space: size + alignment - 1 + sizeof(void*)
    //    (for alignment padding and to store original pointer)
    //
    // 2. Find aligned address within allocated region:
    //    - Start after leaving room for original pointer storage
    //    - Round up to alignment boundary
    //
    // 3. Store original pointer just before aligned address
    //    - ((void**)aligned_ptr)[-1] = original_ptr
    //
    // 4. Return aligned address
    //
    // Memory layout:
    // +----------+--------+----------------+-------------+
    // | orig_hdr | unused | orig_ptr store | aligned data|
    // +----------+--------+----------------+-------------+
    // ^                   ^                ^
    // original_ptr        aligned-sizeof   returned
    //                     (void*)

return NULL;
}

// Free an aligned allocation
void my_aligned_free(void *ptr) {
    // TODO: Free the original allocation
    //
    // 1. If ptr is NULL, do nothing
    // 2. Retrieve original pointer: ((void**)ptr)[-1]
    // 3. Free the original pointer
    //
    // This is why we stored the original pointer!
}