MyMalloc

A learning-oriented fixed-heap memory allocator implemented in C11.

The project simulates a small part of malloc and free inside a static byte array. It is an educational allocator for studying pointer arithmetic, metadata, alignment, fragmentation, invariants, testing, and Linux debugging. It is not a replacement for the C standard library allocator.

Current Version: v0.3 - Explicit Free List

v0.3 keeps the v0.2 in-heap headers, but upgrades the allocator from an implicit scan of every physical block to an explicit, address-ordered doubly linked list of free blocks.

v0.2: physical block chain + First Fit scan over every block
v0.3: physical block chain + explicit free list + local coalescing + stats

The allocator still uses one global fixed-size heap. This version deliberately does not add calloc, realloc, multiple allocation strategies, OS memory requests, or threading.

Block Metadata and Two Chains

Each physical block is laid out as:

+-------------------------------------------------+-------------------+
| Block_Header                                    | payload           |
| size | is_free | prev_size | prev_free | next_free             |
+-------------------------------------------------+-------------------+

size is the payload capacity only; it never includes the header.

The header participates in two different structures:

1. Physical block chain

   • Blocks are contiguous inside the heap.
   • next_block() moves right using sizeof(Block_Header) + size.
   • prev_size stores the previous physical block's payload capacity, so prev_block() finds the left neighbour in O(1).

2. Explicit free list

   • free_head points to the lowest-address free block.
   • prev_free and next_free link only free blocks in ascending physical-address order.
   • These two fields have no meaning while a block is allocated.

Physical order:
[p1 used] [p2 free] [p3 used] [p4 free]

Free-list order:
free_head -> p2 <-> p4 -> NULL

Allocation and Freeing

heap_malloc(size)

1. Reject zero-size, overflowing, or oversized requests.
2. Round the request up to ALIGNMENT.
3. Lazily initialize the heap when needed.
4. Traverse the free list using address-ordered First Fit.
5. Remove the selected free-list node in O(1).
6. Split it if the remainder can contain a header and an aligned payload.
7. Insert a newly created right-side free block into the free list.
8. Return the allocated payload address.

If a block is too small to split, its original payload capacity is retained as internal fragmentation.

heap_free(ptr)

heap_free preserves v0.2's defensive contract:

• heap_free(NULL) does nothing.
• Only an exact allocated payload start is accepted.
• Interior pointers, unknown pointers, repeated frees, and pre-reset pointers are ignored.
• Invalid input must not corrupt allocator metadata.

After a valid release, the allocator checks the immediate physical neighbours:

no free neighbour:      [used] [new free] [used]
left free only:         [free] [new free] [used]  -> [merged free] [used]
right free only:        [used] [new free] [free]  -> [used] [merged free]
both neighbours free:   [free] [new free] [free]  -> [one merged free]

Physical coalescing itself is O(1). A right free neighbour is removed from the free list before its header is absorbed. If the left neighbour is free, it already represents the final merged block in the free list.

Complexity Boundaries

• heap_malloc: O(F), where F is the number of free blocks; the worst case is O(N), where N is the number of physical blocks.
• heap_free: O(N) overall because it scans the physical chain to defensively validate ptr.
• Neighbour discovery and physical coalescing: O(1), using prev_size and next_block().
• The free list stays address-ordered. Generic insertion can traverse free-list nodes, but it does not change the allocator's O(F) allocation bound.

Public API

void *heap_malloc(size_t size);
void heap_free(void *ptr);
void heap_reset(void);
bool heap_check(void);

typedef struct
{
    size_t allocated_payload_capacity;
    size_t free_payload_bytes;
    size_t free_block_count;
    size_t largest_free_block;
    size_t allocation_searches;
    size_t allocation_search_steps;
} Heap_Stats;

bool heap_get_stats(Heap_Stats *out);

heap_get_stats

• Returns false when out == NULL, the heap is uninitialized, or heap_check() fails.
• Does not modify *out on failure.
• Fills a local Heap_Stats value first, then copies it to *out only on success.
• Payload byte fields exclude all headers.
• allocated_payload_capacity reports assigned payload capacity, including internal fragmentation.
• allocation_searches counts valid allocation requests that reach First Fit, including no-space failures.
• allocation_search_steps counts every inspected free-list node.
• heap_reset() clears both cumulative search counters.

External fragmentation is reported by the benchmark as:

1 - largest_free_block / free_payload_bytes

It is shown as N/A when there are no free payload bytes.

Integrity Checking

heap_check() verifies both structures:

• Physical blocks are aligned, bounded, contiguous, non-empty, and cover exactly the heap.
• Each block's prev_size agrees with its physical left neighbour.
• Adjacent physical free blocks do not remain after coalescing.
• The free list has no cycle or duplicate node.
• Every free-list node is a physical block, is marked free, and has consistent prev_free / next_free links.
• Free-list addresses are strictly ascending.
• Every physical free block appears in the free list exactly once.

Build and Run

The project requires a C11 compiler and GNU Make.

make test
make bench
make clean

• make test builds and runs the assertion-based test suite.
• make bench builds and runs the deterministic allocator behaviour benchmark.
• make clean removes generated objects and binaries.

For a Linux memory-tool check:

valgrind --leak-check=full --show-leak-kinds=all \
    --track-origins=yes --error-exitcode=1 ./malloc_test

Benchmark Workloads

My_malloc_bench.c intentionally reports structure and search behaviour instead of timing.

1. First Fit search workload

   • Creates six too-small free blocks before a large tail block.
   • A 128-byte request checks seven free-list nodes.
   • Expected delta: searches +1, steps +7.

2. Fragmentation and coalescing workload

   • Fills the tail, then frees two separated 64-byte blocks.
   • The fragmented state has two 64-byte free blocks: 50% external fragmentation.
   • Freeing the middle block coalesces all three into one 288-byte block: 0% external fragmentation.

This is not a timing benchmark and does not claim that First Fit is faster than other policies.

Test Coverage

The deterministic test suite covers:

• Pre-initialization behaviour and lazy initialization
• Alignment, overflow-sized requests, exhaustion, and recovery
• Splitting and exact reuse without splitting
• First Fit ordering and exact search-counter deltas
• No coalescing, left-only coalescing, right-only coalescing, and two-sided coalescing
• Free-list node count changes after allocation and merging
• heap_free(NULL), interior pointers, unknown/old pointers, and repeated frees
• Heap consistency after each important transition

A fixed-seed random stress test is intentionally deferred to a future version.

Project Structure

My_Malloc/
|-- My_malloc.c
|-- My_malloc.h
|-- My_malloc_test.c
|-- My_malloc_bench.c
|-- Makefile
|-- README.md
|-- version_note/
|   |-- malloc_note.md
|   |-- Header_Allocator.md
|   `-- Explicit_Free_List.md
`-- .gitignore

Current Limitations and Deferred Work

• One global static heap of 640000 bytes
• First Fit only
• No calloc, realloc, or custom allocator context
• No sbrk, mmap, VirtualAlloc, or other OS memory source
• No thread safety, arenas, bins, or multiple policies
• No red zones, canaries, or full payload-overflow detection
• No random stress/fuzz testing in v0.3

Roadmap

• v0.1 external chunk-list allocator
• v0.2 in-heap header allocator with defensive free
• v0.3 explicit doubly linked free list, prev_size, local coalescing, statistics, benchmark, Makefile workflow, Valgrind, and GDB inspection
• Future: randomized testing, calloc, realloc, and allocator contexts
• Future: explicit free-list variants, boundary tags, bins, and alternative fit policies
• Future: OS-backed allocation and concurrency

License

This project is for educational purposes.