Stage 1 · Hands-On Exploration

1 of 4

Work out what a request really costs, spot the frees that go wrong, and coalesce a fragmented heap until a request fits.

A program calls malloc(20). How many bytes does the allocator take out of the pool to serve it?

header size: 8 bytes in front of every block
alignment: 8 bytes for the start of the next block
requested payload: 20 bytes

Your answerbytes

Memory, bits, and pointers in C· 4 of 4

Memory, bits, and pointers in C

Manual heap allocation and free-list allocators

The heap memory region, malloc and free lifecycle, memory fragmentation, boundary tags, block splitting, and coalescing.

25 minute read

⚡

For the best experience: Download the native Atlas Desktop app for instant test running, native IDE sync, and 100% offline practice.

Download Desktop App→

Programs frequently require memory buffers whose sizes cannot be predicted at compile time, or whose lifetimes must extend beyond the activation frame that created them.

The operating system and runtime provide the heap: a dynamic memory region managed manually via memory allocators.

The heap memory region and dynamic lifetimes

Unlike the stack, which is bound strictly to function call lifecycles, heap-allocated memory persists until explicitly deallocated by the program.

The C standard library provides core heap allocation routines:

malloc(size_t size): Allocates size uninitialized bytes and returns a pointer to the start of the memory block.
free(void *ptr): Reclaims the memory block previously returned by malloc.
calloc(size_t num, size_t size): Allocates zero-initialized memory for an array of elements.
realloc(void *ptr, size_t new_size): Resizes an existing heap block, relocating data if necessary.

Operating systems manage the process heap boundary using system calls:

brk / sbrk: Adjusts the program break point, growing or shrinking the contiguous data segment.
mmap: Maps anonymous virtual memory pages directly into the process address space for large allocation requests.

Block headers and boundary tags

Because free(ptr) only accepts a pointer without requiring the caller to pass the block's size, memory allocators store metadata in-band within memory blocks.

Every contiguous memory chunk includes an allocator header preceding the user payload:

+----------------+--------------------------+
| Block Header   | User Payload             |
| (size, status) | (returned to caller)     |
+----------------+--------------------------+
^                ^
|                |
Block Offset     Payload Pointer (returned by malloc)

Typical 8-byte or 16-byte block headers store:

Total block size (including header bytes)
Allocation status bit (free vs allocated)
Pointers to adjacent free chunks (when tracking free lists)

Allocators enforce strict address alignment (typically 8 bytes on 32-bit systems, 16 bytes on 64-bit systems) so that any scalar or vector CPU instruction can read payload addresses without alignment penalties or hardware traps.

Memory fragmentation mechanics

Over time, interleaved allocation and deallocation requests create memory fragmentation:

Internal fragmentation: Occurs when an allocator grants more bytes than requested. If a caller requests 5 bytes and the allocator aligns allocations to 8-byte boundaries with an 8-byte header, 3 payload bytes remain unused inside the block.
External fragmentation: Occurs when total available free memory is sufficient to satisfy a request, but the memory is divided into small, non-contiguous chunks, none of which is individually large enough.

[ Allocated: 64B ] [ Free: 32B ] [ Allocated: 64B ] [ Free: 32B ]

In this state, 64 bytes of free memory exist in total, but an allocation request for 48 contiguous bytes fails.

Free-list algorithms and block splitting

Explicit free-list allocators link all available free blocks into a data structure (such as a doubly linked list).

When malloc(N) is called, the allocator searches the free list for a block that satisfies the request:

First-fit: Searches the free list from the beginning and selects the first block with sufficient size.
Next-fit: Resumes searching from the location of the previous allocation.
Best-fit: Scans the entire free list to find the smallest block that satisfies the request, minimizing wasted remainder bytes at the cost of longer search times.

When a selected free block is larger than the requested size, the allocator performs block splitting:

Before Split:
[ Free Block: 128 Bytes                                      ]

After Split (malloc 32 bytes payload + 8 bytes header = 40 bytes):
[ Allocated: 40B ] [ New Free Block: 88B                     ]

The allocator partitions the chunk, marks the first portion as allocated, and places the remaining portion back into the free list.

Immediate coalescing and common failure modes

When a block is freed via free(ptr), neighboring blocks may also be free. If adjacent free chunks remain separate, the allocator suffers from false fragmentation.

Immediate coalescing merges adjacent free blocks during the free() call:

If the block immediately following (next) is free, merge the two into a single larger block.
If the block immediately preceding (prev) is free, merge the preceding block and the current block.

Heap failure modes

Manual memory management introduces critical bug categories in systems programming:

Use-after-free: Reading from or writing to a pointer after calling free(ptr). If the allocator reallocates that chunk to another component, reads return unexpected data and writes corrupt the new owner's state.
Double free: Calling free(ptr) twice on the same pointer. This corrupts free-list pointers inside the block headers, frequently causing subsequent allocator calls to crash or overwrite arbitrary memory addresses.
Memory leak: Losing all pointer references to an allocated heap block without calling free(). The memory remains reserved until the entire process terminates.

Memory, bits, and pointers in C

Manual heap allocation and free-list allocators

The heap memory region, malloc and free lifecycle, memory fragmentation, boundary tags, block splitting, and coalescing.

25 minute read

⚡

For the best experience: Download the native Atlas Desktop app for instant test running, native IDE sync, and 100% offline practice.

Download Desktop App→

Coding Objective

Implement your solution in the editor on the right or work in your local IDE. All unit tests run against your code in real-time.

Language: Python 3.10+Runner: Local / Pyodide

Exercise

heap-allocator

11 tests, graded on your machine in about a second. Stuck for 30 minutes? The desktop app will offer you the reference solution.

solution.py

"""
Free-list heap memory allocator.

Simulates manual memory management, first-fit allocation, block header
bookkeeping, block splitting, and immediate bidirectional coalescing.

Run `python3 test.py` to test your implementation.
"""

from __future__ import annotations

from typing import Optional

class Block:
    """
    Node in the memory block list representing an allocated or free memory chunk.
    """

def __init__(
        self,
        offset: int,
        size: int,
        is_free: bool = True,
        next: Optional[Block] = None,
        prev: Optional[Block] = None,
    ) -> None:
        """
        Initialize a memory block.

Args:
            offset: Byte offset where this block starts in the memory pool.
            size: Total size of the block in bytes (including 8-byte header).
            is_free: True if block is available for allocation, False if allocated.
            next: Pointer to next contiguous block in the heap.
            prev: Pointer to previous contiguous block in the heap.
        """
        raise NotImplementedError

class FreeListAllocator:
    """
    Explicit free-list memory allocator with first-fit strategy and coalescing.
    """

HEADER_SIZE: int = 8

def __init__(self, total_bytes: int = 1024, alignment: int = 8) -> None:
        """
        Initialize the allocator pool.

Args:
            total_bytes: Total capacity of the memory pool in bytes.
            alignment: Byte alignment boundary for allocated payloads (must be power of 2).

Raises:
            ValueError: If total_bytes < alignment + HEADER_SIZE or alignment is not a power of 2.
        """
        raise NotImplementedError

def malloc(self, size: int) -> int:
        """
        Allocate a memory block with at least size bytes of payload.

Payload is padded to the allocator's alignment boundary and preceded by
        an 8-byte header.

Args:
            size: Requested payload size in bytes.

Returns:
            The byte address (offset) of the allocated payload (block.offset + HEADER_SIZE).

Raises:
            ValueError: If size <= 0.
            MemoryError: If no contiguous free block can satisfy the request.
        """
        raise NotImplementedError

def free(self, address: int) -> None:
        """
        Free a previously allocated block and coalesce with adjacent free blocks.

Args:
            address: The payload address returned by a prior malloc() call.

Raises:
            ValueError: If address does not match an active allocated block or is already free.
        """
        raise NotImplementedError

def is_allocated(self, address: int) -> bool:
        """
        Check if an address corresponds to an active allocated payload.

Args:
            address: The payload address to inspect.

Returns:
            True if address is an active allocated block payload, False otherwise.
        """
        raise NotImplementedError

def get_free_bytes(self) -> int:
        """
        Calculate total free bytes remaining in the allocator pool.

Returns:
            Sum of sizes of all currently free blocks.
        """
        raise NotImplementedError

def get_block_count(self) -> int:
        """
        Count total number of blocks (both free and allocated) in the heap list.

Returns:
            Total block count.
        """
        raise NotImplementedError

Or use the desktop app