Implementing free

medium · memory, deallocation, pointers

Free: Marking Blocks for Reuse

Now that we have malloc, we need free(). Without it, memory can only grow - never be reused.

What free() Does

free() does NOT return memory to the OS. It marks the block as available for reuse:

Before free(p):
┌──────────────┬───────────────────┐
│ size=100     │                   │
│ free=0  ────────► ALLOCATED      │
│ next=...     │                   │
└──────────────┴───────────────────┘

After free(p):
┌──────────────┬───────────────────┐
│ size=100     │                   │
│ free=1  ────────► FREE (reusable)│
│ next=...     │                   │
└──────────────┴───────────────────┘

The Critical Pointer Arithmetic

When the user calls free(ptr), they give us the pointer to their DATA. We need to find the HEADER:

void my_free(void *ptr) {
    // ptr points to user data
    // Header is immediately BEFORE the data
    block_header_t *block = (block_header_t*)ptr - 1;
    block->free = 1;
}

Your Task

// Get the block header from a user pointer
block_header_t *get_block(void *ptr);

// Free the memory pointed to by ptr
// - Find the block header
// - Mark it as free
// - Handle NULL gracefully (do nothing)
void my_free(void *ptr);

Safety Considerations

Real allocators add checks:

NULL check: free(NULL) should be a no-op (do nothing)
Double-free detection: Freeing already-freed memory is a bug
Invalid pointer detection: Only free pointers from malloc

For now, just implement the basics with the NULL check.

Why Not Return Memory to OS?

Consider this sequence:

void *a = malloc(100);  // Block A
void *b = malloc(100);  // Block B
void *c = malloc(100);  // Block C
free(b);                // Free middle block

The heap looks like: [A used][B free][C used]

We can't shrink the heap because C is still in use! We can only shrink from the TOP. So free() just marks blocks for reuse.

#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: malloc implementation from previous problem
// ============================================

static void *get_payload(block_header_t *block) {
    return (void*)(block + 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;
}

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 = request_space(size);
    if (block == NULL) return NULL;
    return get_payload(block);
}

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

// Get the block header from a user pointer
// The header is immediately BEFORE the user data
block_header_t *get_block(void *ptr) {
    // TODO: Use pointer arithmetic to find the header
    // Hint: The header is sizeof(block_header_t) bytes before ptr
    // Or equivalently: ((block_header_t*)ptr) - 1
    return NULL;
}

// Free the memory pointed to by ptr
void my_free(void *ptr) {
    // TODO: Handle NULL (do nothing)
    // TODO: Get the block header using get_block()
    // TODO: Mark the block as free (block->free = 1)
}