Linked List

Introduction

This document describes an implementation of the malloc function using a linked list of memory blocks.
The core idea is to represent memory as a sequence of blocks, each one holding metadata and user data.

Main characteristics:

• Fast allocation with first-fit strategy.
• Suffers from fragmentation and poor memory efficiency.

Linked-list Structure

Management of Memory

Allocation

1. User requests malloc(s).
2. Traverse the linked list and find the first block with size ≥ s + metadata_size (first-fit).
3. If the block is larger than needed:
   • Split it into two:
     • One block with exactly s bytes for the user.
     • Another block containing the remaining free space.
4. Return the address of the block and mark it as used.

Alternative: best-fit strategy, which searches for the block that best matches the requested size (less wasted space, but slower).

Free

1. Mark the block as free.
2. To reduce fragmentation, attempt to merge neighboring free blocks (fusion operation).
3. If the whole page is free, it can be unmapped.

Metadata

Each block contains metadata before the user’s data. Typical fields include:

• Block status (allocated/free).
• Block size.
• Pointer to the next block.
• Pointer to the previous block if needed.

danger

For this representation, you need to be good at handling raw pointers. Undefined behaviors can quickly occur.