Implementing realloc

hard · memory, reallocation, edge-cases

Realloc with Data Preservation

realloc is deceptively complex. It must handle:

Growing allocations (may need to move)
Shrinking allocations (can stay in place)
Edge cases: NULL pointer, zero size

Semantics

void *realloc(void *ptr, size_t new_size);

If ptr is NULL: equivalent to malloc(new_size)
If new_size is 0: implementation-defined (we'll treat as free(ptr) and return NULL)
If new_size <= current_size: may shrink in place, return same pointer
If new_size > current_size: allocate new block, copy data, free old block

Critical: If realloc fails (can't allocate new size), it returns NULL but the original block must remain valid and unchanged.

Your Task

// Reallocate a memory block to a new size
// Preserves data up to min(old_size, new_size)
void *my_realloc(void *ptr, size_t new_size);

// Helper: copy n bytes from src to dst
// You implement this - do not use memcpy
void my_memcpy(void *dst, const void *src, size_t n);

// Helper: get the size of an allocated block
size_t get_block_size(void *ptr);

Subtle Issues

Data Preservation

When growing, only copy the OLD size worth of data:

// If old block was 100 bytes, new request is 200 bytes
// Copy exactly 100 bytes, not 200!
my_memcpy(new_ptr, old_ptr, old_size);

The Return Value Contract

void *p = malloc(100);
fill_with_data(p);

void *q = realloc(p, 200);
if (q == NULL) {
    // CRITICAL: p is still valid! Data is preserved!
    // Many programs forget this and leak or corrupt here
}
// If q != NULL: p is now invalid, use only q

In-Place Shrinking

When shrinking, you don't need to allocate new memory:

if (new_size <= block->size) {
    // Optionally update block->size to new_size
    // Optionally split the remainder (covered in later problem)
    return ptr;  // Same pointer, less logical size
}

Overlap Safety

When copying, the old and new regions must not overlap (for realloc they won't - you allocate new then copy). But memcpy requires non-overlapping regions. Since realloc allocates fresh memory before copying, this is safe.

Edge Cases

realloc(NULL, 100) - just malloc
realloc(ptr, 0) - free and return NULL
realloc(ptr, same_size) - return same pointer
realloc(ptr, larger) - malloc new, copy, free old
realloc(ptr, smaller) - may return same pointer

Memory Leak Trap

// WRONG - leaks if realloc fails
ptr = realloc(ptr, new_size);  // If returns NULL, old ptr is lost!

// CORRECT
void *new_ptr = realloc(ptr, new_size);
if (new_ptr != NULL) {
    ptr = new_ptr;
}

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

#define BLOCK_MAGIC 0xDEADBEEF

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;

// ============================================
// PROVIDED: Complete malloc/free implementation
// ============================================

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

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

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_size = sizeof(block_header_t) + size;
    block_header_t *block = sbrk((intptr_t)total_size);
    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;

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

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

void my_free(void *ptr) {
    if (ptr == NULL) return;
    block_header_t *block = get_block_header(ptr);
    block->free = 1;
}

// ============================================
// YOUR TASK: Implement these functions
// ============================================

// Helper: copy n bytes from src to dst
// Implement without using memcpy
void my_memcpy(void *dst, const void *src, size_t n) {
    // TODO: Cast to char* and copy byte by byte
    // char *d = (char*)dst;
    // const char *s = (const char*)src;
    // for (size_t i = 0; i < n; i++) { d[i] = s[i]; }
}

// Helper: get the data size of an allocated block
size_t get_block_size(void *ptr) {
    // TODO: Return 0 if ptr is NULL
    // TODO: Get the block header and return its size field
    return 0;
}

// Reallocate memory to new size, preserving data
void *my_realloc(void *ptr, size_t new_size) {
    // Case 1: ptr is NULL -> equivalent to malloc(new_size)

// Case 2: new_size is 0 -> free(ptr) and return NULL

// Case 3: new_size <= current size -> return same pointer

// Case 4: new_size > current size:
    //   -> allocate new block
    //   -> copy OLD size bytes (not new_size!)
    //   -> free old block
    //   -> return new pointer
    //
    // CRITICAL: If malloc fails:
    //   -> return NULL
    //   -> DO NOT free old block
    //   -> old block must remain valid

return NULL;
}