Dynamic Memory Allocator

This project implements a small C allocator backed by one anonymous 64 MiB mmap() arena. Its public API is:

void *my_malloc(size_t size);
void *my_calloc(size_t count, size_t size);
void *my_realloc(void *ptr, size_t new_size);
void my_free(void *ptr);

The arena is created lazily by the first nonzero allocation request. Later allocations and frees operate entirely inside that mapping; individual blocks are not mapped or unmapped separately.

Block metadata and alignment

Each block contains a hidden Chunk header immediately before its payload:

+--------------------------+--------------------------+
| Chunk metadata           | Payload                  |
| size + allocation state  | Returned to the caller   |
+--------------------------+--------------------------+
^                          ^
Block start                my_malloc() result

size records the block's payload capacity, and is_free records whether that block is available. The header is 16 bytes on the supported 64-bit platforms, and requested sizes are rounded up to 16-byte multiples. Because mmap() returns a page-aligned arena base, the payload of every original or split block is 16-byte aligned.

Implicit free list

The allocator does not store next or previous pointers. Blocks are laid out consecutively in the arena, so the next header is found by advancing over:

sizeof(Chunk) + current block payload size

This physical traversal forms an implicit free list.

First-fit allocation

my_malloc() scans from the first block in the arena and selects the first free block whose payload capacity is at least the aligned request size. If no block fits, it returns NULL and sets errno to ENOMEM.

Zero-sized requests return NULL. Requests that overflow during alignment or cannot fit in the arena also return NULL.

Zero-initialized allocation

my_calloc() checks whether count * size would overflow, allocates the total with my_malloc(), and initializes every requested byte to zero. An overflow returns NULL and sets errno to ENOMEM. If either argument is zero, the total is zero and the result follows my_malloc(0) by returning NULL.

Resizing

my_realloc(NULL, new_size) behaves like my_malloc(new_size), while a zero size frees a non-null pointer and returns NULL. If the current block is already large enough, its pointer is returned unchanged.

To grow a block, my_realloc() first tries to absorb the physically adjacent free block and splits off any usable excess space. Otherwise, it allocates a new block, copies the old payload, frees the old block, and returns the new pointer. If the new allocation fails, the old block remains valid.

Splitting

When a selected free block is larger than necessary, the allocator splits it into:

1. an allocated block sized for the aligned request; and
2. a new free block containing the remaining capacity.

A split occurs only when the remainder has enough room for another Chunk header and at least one 16-byte payload. Smaller remainders stay with the allocated block.

Freeing and reuse

my_free(NULL) is a no-op. Otherwise, my_free() moves backward by sizeof(Chunk) bytes to recover the block header and marks the block free.

The arena remains mapped. A later first-fit search can select the freed block, so released blocks are reused without another mmap() call.

Coalescing

After my_free() marks a block free, the allocator scans the arena and merges adjacent free chunks. When two chunks are merged, the removed chunk's header becomes part of the enlarged current chunk's payload capacity:

current->size += sizeof(Chunk) + next->size;

The allocator checks the enlarged chunk again before advancing, allowing a run of several free chunks to become one block. Coalescing reduces external fragmentation and makes larger allocations possible after neighboring blocks are released.

The current coalescing implementation performs a linear scan of the entire arena after each non-null my_free() call.

Build and run

Compile with:

gcc main.c -o xyz

Run:

./xyz

main.c already includes my_malloc.c, my_calloc.c, my_free.c, and my_realloc.c. Do not list those implementation files separately in the GCC command, because that would define the allocator functions twice.

The checks in main.c cover successful allocation, writable memory, 16-byte alignment, non-overlapping allocations, reuse after free, adjacent-block coalescing, my_malloc(0), and my_free(NULL).

External fragmentation benchmark

Run the fragmentation comparison with:

./benchmarks/run_benchmarks.sh

The runner compiles the same workload twice: once with the allocator's normal coalescing my_free() and once with a benchmark-local free implementation that only marks blocks as free. The production allocator sources are not modified.

The workload fills the arena with 4 KiB allocations and frees the first contiguous half. It reports the free-chunk count, total free space, largest free block, and external fragmentation:

1 - largest free block / total free space

It then attempts an 8 KiB allocation. Coalescing should combine the adjacent 4 KiB blocks and allow the request; without coalescing, the request should fail even though enough total space is free.

Executables are built in a temporary directory and removed when the runner exits. Set CC or CFLAGS to override the default compiler or flags.

Current limitations

• The arena has a fixed 64 MiB capacity and cannot grow.
• Allocation uses a linear first-fit scan.
• Every non-null free performs a linear coalescing scan.
• Invalid pointers and double frees are not detected.
• The allocator is not thread-safe or async-signal-safe.
• The arena is not returned to the operating system before process exit.