Naive malloc: Your First Working Allocator

This is a milestone: you'll implement a working malloc that can be used to allocate memory.

This version is "naive" because it doesn't reuse freed blocks - every allocation grows the heap. That's fine for now; we'll add reuse in the next problem.

How malloc Works

1. User calls: void *ptr = my_malloc(100);

2. We need to store metadata, so allocate header + data:
   ┌─────────────────┬────────────────────────────────────┐
   │  block_header   │        100 bytes user data         │
   │    (24 bytes)   │                                    │
   └─────────────────┴────────────────────────────────────┘
                     ↑
                     Return this pointer to user

3. Total sbrk request: sizeof(block_header_t) + 100 = 124 bytes

Your Task

// The global block list head
extern block_header_t *free_list_head;

// Request a new block from the OS using sbrk
// Initializes the block header and adds it to the list
// Returns pointer to USER DATA (not the header!)
block_header_t *request_space(size_t size);

// The malloc function
// Returns pointer to 'size' bytes of memory, or NULL on failure
void *my_malloc(size_t size);

Implementation Steps

1. my_malloc(size):
   • Return NULL if size is 0
   • Call request_space(size) to get a new block
   • Return pointer to the data area (after the header)
2. request_space(size):
   • Calculate total size: sizeof(block_header_t) + size
   • Call sbrk(total_size) to extend the heap
   • Handle sbrk failure (returns (void*)-1)
   • Initialize the block header
   • Add block to the list
   • Return the block (not the payload!)

Why "Naive"?

This version calls sbrk() for EVERY allocation. If you do:

for (int i = 0; i < 1000; i++) {
    my_malloc(16);
}

We'll make 1000 sbrk calls, even if some blocks were freed!

The next problem adds free() and then we'll make malloc smarter.

Constraints

• Every allocation must add a block to the list
• Return NULL for size 0
• Handle sbrk failure gracefully