Memory Deallocation

free() doesn't return memory to the OS. It marks blocks for reuse.

The Simple Implementation

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

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

That's it! The block stays in our list, now available for future allocations.

Why Not Return to OS?

The heap is contiguous. You can only shrink from the top:

[Block A] [Block B] [Block C] <- heap top

If you free Block B:

• Can't return it to OS (Block C is in the way)
• Can only mark it for reuse

Even freeing Block C is tricky - what if you allocate again immediately?

The Reuse Cycle

malloc(100) -> Block A created, used
malloc(50)  -> Block B created, used
free(A)     -> Block A marked free

malloc(80)  -> Block A reused! (100 >= 80)
              Block A marked used again

Dangerous Operations

Double Free

void *p = malloc(100);
free(p);
free(p);  // Undefined behavior!

Second free marks an already-free block. May corrupt allocator state.

Use After Free

void *p = malloc(100);
free(p);
*p = 42;  // Undefined behavior!

The memory might be reused by another allocation.

Invalid Free

int x;
free(&x);  // Disaster! Stack variable, not from malloc

Your allocator will interpret garbage as a block header.

Validation Strategies

Magic Numbers

#define BLOCK_MAGIC 0xDEADBEEF

void my_free(void *ptr) {
    block_header_t *block = payload_to_block(ptr);
    if (block->magic != BLOCK_MAGIC) {
        // Not a valid block!
        abort();
    }
    block->free = 1;
}

Double-Free Detection

void my_free(void *ptr) {
    block_header_t *block = payload_to_block(ptr);
    if (block->free) {
        // Already free!
        abort();
    }
    block->free = 1;
}

Memory Layout After Operations

Initial:
[A: 100, used] -> [B: 50, used] -> [C: 75, used]

After free(B):
[A: 100, used] -> [B: 50, FREE] -> [C: 75, used]

After malloc(30):
[A: 100, used] -> [B: 50, used] -> [C: 75, used]
                  (30 bytes used, 20 wasted - internal fragmentation)