Basic Allocation

Now we implement malloc: finding or creating memory blocks.

The Free List

We maintain a linked list of all blocks (free and allocated):

block_header_t *free_list_head = NULL;

Despite its name, the "free list" often contains both free and used blocks. The free flag distinguishes them.

Allocation Strategies

First-Fit

Scan the list and return the first block that:

1. Is marked as free
2. Has size >= requested size

block_header_t *find_first_fit(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;
}

Other Strategies (Not Implemented Here)

• Best-Fit: Find smallest block that fits (reduces waste, slower)
• Worst-Fit: Find largest block (leaves bigger remainders)
• Next-Fit: Start from last allocation point

Requesting New Memory

When no suitable block exists, ask the OS:

block_header_t *request_block(size_t size) {
    size_t total = sizeof(block_header_t) + size;

    block_header_t *block = sbrk(total);
    if (block == (void*)-1) {
        return NULL;  // sbrk failed
    }

    block->size = size;
    block->free = 0;
    block->next = NULL;

    // Add to list
    if (free_list_head == NULL) {
        free_list_head = block;
    } else {
        // Find end and append
        block_header_t *last = free_list_head;
        while (last->next) last = last->next;
        last->next = block;
    }

    return block;
}

The Complete malloc

void *my_malloc(size_t size) {
    if (size == 0) return NULL;

    // Try to find existing free block
    block_header_t *block = find_first_fit(size);

    if (block != NULL) {
        block->free = 0;  // Mark as used
        return block_to_payload(block);
    }

    // No suitable block, request new memory
    block = request_block(size);
    if (block == NULL) {
        return NULL;  // Out of memory
    }

    return block_to_payload(block);
}

Trade-offs

First-fit is simple but has issues:

• Fragments build up at start of heap
• May waste space in large blocks

We'll address these with splitting (later module).