Mallocator: A Custom Memory Allocator in C

Mallocator is a from-scratch implementation of a dynamic memory allocator in C. It manages a dedicated memory region (an "arena") and provides functions analogous to the standard library's malloc and free. The project is designed to demonstrate core memory management concepts, including block splitting to reduce internal fragmentation and coalescing to combat external fragmentation.

The codebase is built with a cross-platform Makefile and is extensively tested using the Criterion framework to ensure correctness and stability.

For more background on Linux environments and code I/O, see: Linux Operating Systems - rsiddiq.com.

Features

• Dynamic Memory Arena: Initializes and manages a contiguous block of memory using mmap.
• First-Fit Allocation: Implements a first-fit algorithm to find available memory chunks.
• Block Splitting: Automatically splits larger free blocks to fit allocations, minimizing wasted space.
• Block Coalescing: Merges adjacent free blocks upon deallocation to form larger contiguous free spaces.
• Doubly-Linked List Management: Uses a linked list of headers to track memory chunks, their sizes, and their free/used status.
• Comprehensive Test Suite: Includes a full suite of unit tests built with the Criterion framework to verify allocator behavior.
• Cross-Platform Build: Uses a standard Makefile for easy compilation on Linux, macOS, and WSL.

Project Layout

Mallocator/
├── Makefile
├── README.md
├── unit_tests.c                        # Test runner entry point
├── src/
│   ├── common.h                        # Common headers and logging macros
│   ├── mallocator.h                    # Public API for the allocator
│   └── mallocator.c                    # Core implementation of the allocator
└── tests/
├── unittests_alloc.c                   # Tests for memory allocation
├── unittests_free.c                    # Tests for memory deallocation and coalescing
└── unittests_functions.c               # Tests for helper functions

Build Requirements

• GCC or Clang
• make
• pkg-config (recommended)
• Criterion test framework

Linux / WSL (Ubuntu/Debian)

sudo apt update
sudo apt install -y build-essential pkg-config libcriterion-dev
make            # builds the 'unit_tests' binary
make test       # runs the Criterion test suite

macOS

# Install Xcode Command Line Tools
xcode-select --install
# Install dependencies via Homebrew
brew install criterion pkg-config
make
make test

API and Usage

The allocator's public interface is defined in src/mallocator.h.

Key Data Structure

• node_t: The header for each memory chunk. It's a struct containing:
  • size_t size: The size of the memory block (excluding the header).
  • bool is_free: A flag indicating if the block is available.
  • struct __node_t *fwd: A pointer to the next block in memory.
  • struct __node_t *bwd: A pointer to the previous block in memory.

Core Functions

• int init(size_t size): Initializes the memory arena of a given size. The size will be rounded up to the nearest multiple of the system's page size. Returns the actual size of the arena on success or an error code on failure.
• int destroy(): Releases the entire memory arena back to the operating system using munmap.
• void* mem_alloc(size_t size): Allocates a block of memory of the given size. Returns a pointer to the start of the usable memory block, or NULL if the allocation fails.
• void mem_free(void *ptr): Frees a block of memory previously allocated by mem_alloc. It marks the block as free and attempts to coalesce it with adjacent free blocks.

Error Handling

The statusno global variable is set when a function fails. The possible error codes are defined in mallocator.h:

• ERR_OUT_OF_MEMORY: Allocation failed because no sufficiently large free block was found.
• ERR_BAD_ARGUMENTS: An invalid argument was passed to a function (e.g., NULL pointer, invalid size).
• ERR_SYSCALL_FAILED: A system call like mmap, munmap, or open failed.
• ERR_CALL_FAILED: A function call failed for other reasons (e.g., trying to coalesce a non-free block).
• ERR_UNINITIALIZED: An allocation or free operation was attempted before init() was called.

Development and Testing

• The core logic resides in src/mallocator.c.
• Unit tests are located in the tests/ directory and are run via the unit_tests.c entry point.
• The Makefile handles the compilation of all source files and links against the Criterion library.

To run the tests:

make test

To clean the build artifacts:

make clean