Aligned Memory Allocation

hard · memory, alignment, optimization

Aligned Memory Allocation

Return a payload with a requested power-of-two alignment while preserving the original allocation for the paired free. The supplied my_malloc is a limited, single-threaded teaching allocator with 8-byte rounding on the course's 64-bit Linux target. That policy is not the standard C allocation contract: standard allocation provides fundamental alignment, rather than one universal byte count.

Your interface

int is_power_of_two(size_t n);
size_t align_up(size_t n, size_t alignment);
void *my_aligned_alloc(size_t alignment, size_t size);
void my_aligned_free(void *ptr);

is_power_of_two returns 1 exactly for positive powers of two, otherwise 0.
align_up returns the least multiple of alignment greater than or equal to n. Return 0 for invalid alignment or an unrepresentable rounded result. align_up(0, 8) also legitimately returns 0. This helper does not allocate.
my_aligned_alloc rejects zero size and invalid alignment with NULL. Promote a valid alignment smaller than sizeof(void*) to sizeof(void*), so the saved original-pointer slot is suitably aligned on this target. The requested size need not be a multiple of alignment; this is a custom API.
On success, all size payload bytes must be writable, disjoint from the saved pointer, and preserved until the paired free. Separate live allocations cannot overlap. Allocation does not promise zeroed bytes.
Reject overflow in padding, pointer-slot addition, base-allocator rounding, header addition, or conversion to the signed sbrk increment. Rejected arithmetic makes no growth call and changes no existing block, list link, or live data. A growth failure also returns NULL without changing existing allocations.
my_aligned_free(NULL) does nothing. Every other input must be a live pointer returned by my_aligned_alloc; interior pointers, foreign pointers, and double frees are outside the contract. Recover and free its original allocation.

Derive the layout

Reserve size + (effective_alignment - 1) + sizeof(void*) bytes from the provided allocator, checking each addition before computing it. The first part of that allocation leaves room for the saved pointer. Round the address then save the original pointer immediately before the aligned payload. Advance within the acquired region; do not wrap an integer address while rounding.

raw allocation start                    aligned payload
| optional padding | saved raw pointer | size writable bytes | spare bytes |

For an invented raw address 1000, an eight-byte pointer, alignment 64, and size 20: begin the search at 1008, round to 1024, store the original pointer in [1016,1024), and return 1024. The caller owns [1024,1044); the paired free recovers 1000. The underlying header lies before the raw allocation, outside these reserved payload bytes.

Check the boundaries

For a power-of-two alignment, (n + alignment - 1) & ~(alignment - 1) works only when the addition is representable. Check n <= SIZE_MAX - (alignment - 1) first. With a toy maximum 255, rounding 250 to 8 would need 256 and must report failure rather than wrapping to zero and using a small allocation. A successful small allocation is not evidence that the original large request was satisfied.

Test sizes around an alignment boundary, promoted small alignments, invalid alignments, arithmetic rejection, writable payloads, and reuse after the paired free. The hidden tests use bounded simulated growth to check failure and unchanged ownership without trying to exhaust real memory.

#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) & ~(size_t)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) {
    if (size > SIZE_MAX - sizeof(block_header_t)) return NULL;
    size_t total = sizeof(block_header_t) + size;
    if (total > (size_t)INTPTR_MAX) return NULL;
    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 || size > SIZE_MAX - 7) return NULL;

size_t aligned = align8(size);
    if (aligned > SIZE_MAX - sizeof(block_header_t) ||
        aligned + sizeof(block_header_t) > (size_t)INTPTR_MAX) return NULL;
    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; return 0 for invalid alignment or an unrepresentable result.
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)
    // First check nonzero power-of-two alignment and n <= SIZE_MAX-(alignment-1).
    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. Promote smaller powers of two to sizeof(void*) for the stored pointer
    // 3. size == 0 returns NULL; reject overflow without changing allocator state
    //
    // Strategy:
    // 1. Allocate extra space: size + alignment - 1 + sizeof(void*)
    //    (for alignment padding and to store original pointer)
    //    Check each addition BEFORE computing it; the provided allocator also
    //    checks rounding, header size, and the signed sbrk increment bound.
    //
    // 2. Find aligned address within allocated region:
    //    - Start after leaving room for original pointer storage
    //    - Compute padding from address modulo alignment, then advance within
    //      the allocated region; do not wrap an integer address while rounding
    //
    // 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!
}