Custom Memory Allocator in C

Course: COMP2221 - Systems Programming
Institution: Durham University
Author: AbdulMuhmeen Leasu
Year: 2025

Overview

This project represents my first major C programming endeavour, completed as part of the COMP2221 Systems Programming coursework. It implements a custom memory allocator that provides malloc, free, read, and write functionality with advanced security features including corruption detection, quarantine mechanisms, and heap visualization.

For a comprehensive technical analysis of the implementation, design decisions, and performance characteristics, please refer to the full coursework report: COMP2221_Systems_Programming_Summative_Coursework_Report.pdf.

Project Structure

Core Files

allocator.c (642 lines): Main implementation of the memory allocator with all core functionality
allocator.h: Public API declarations and data structure definitions
visualiser.c & visualiser.h: Heap visualization system for debugging and monitoring
main.c: Simple demonstration program showcasing basic allocator operations
test_suite.c & test_suite.h: Comprehensive test suite with 40+ test cases
Makefile: Build configuration for both standalone executable and shared library

Build Artifacts

runme: Standalone executable for testing
liballocator.so: Shared library for integration with other programs
Analysis files: analysis.txt, analysis2.txt, analysis3.txt - test output logs

Key Features

1. Memory Management

First-fit allocation strategy: Efficiently searches for suitable free blocks
Block splitting: Divides large blocks when allocating smaller requests to minimize waste
Coalescing: Automatically merges adjacent free blocks to prevent fragmentation
40-byte alignment: All allocations aligned to ALIGNMENT boundary for optimal performance

2. Security & Integrity

Dual Checksum System

As detailed in the report, the allocator implements a sophisticated dual-checksum mechanism:

Header Checksum (16-bit): Uses a rotate-and-XOR hash incorporating:
- Block address
- Size and flags
- Free list pointers
- Payload checksum
Payload Checksum (16-bit): Fletcher-16 algorithm for detecting data corruption

Corruption Detection & Quarantine

Automatic detection of header corruption during allocation
Corrupted blocks are immediately quarantined (marked with quarantine flag)
Quarantined blocks are removed from free list and excluded from future allocations
Prevents cascading corruption through the heap

Brownout Detection

The mm_read function implements brownout detection by identifying when the unused byte pattern appears in locations where actual data should exist, indicating potential memory loss or corruption.

3. Data Structures

Header Structure (see allocator.h)

typedef struct Header {
    size_t total_size;           // Block size with flags in lower 2 bits
    struct Header *prev;         // Previous block in free list
    struct Header *next;         // Next block in free list  
    uint16_t headerChecksum;     // Header integrity check
    size_t payloadChecksum;      // Payload integrity check
} Header;

Bit Packing Optimization

The total_size field cleverly packs two flags into the lower bits:

Bit 0: is_free flag
Bit 1: quarantine flag
Bits 2+: Actual block size

This is possible because all block sizes are multiples of 40 (ALIGNMENT), ensuring lower bits are naturally zero.

HeapManager Structure

typedef struct {
    uint8_t *alloc_start;            // Start of allocatable heap region
    size_t allocatable_heap_size;    // Size available for allocations
    uint8_t unused_byte_pattern[5];  // Pattern for detecting unused memory
    Header *free_list_head;          // Head of sorted free list
} HeapManager;

4. Free List Management

Address-ordered doubly-linked list: Free blocks sorted by memory address
Enables efficient coalescing of adjacent blocks
Supports O(n) insertion with immediate neighbor merging
Robust pointer validation and update mechanisms

5. Heap Visualization

The custom visualization system provides real-time heap state monitoring:

Color-coded block status (free, allocated, corrupted, unused)
40-byte step visualization showing heap layout
Block highlighting for tracking specific allocations
ASCII-art representation for debugging

API Functions

`int mm_init(uint8_t *heap, size_t heap_size)`

Initializes the allocator with a pre-allocated heap region.

Parameters:

heap: Pointer to memory region to manage
heap_size: Size of heap in bytes (minimum: ~200 bytes)

Returns: 0 on success, -1 on failure

`void *mm_malloc(size_t size)`

Allocates a block of memory of at least size bytes.

Strategy:

First-fit search through free list
Validates header checksums during search
Quarantines corrupted blocks automatically
Splits block if remainder ≥ MIN_BLOCK_SIZE
Updates checksums and free list

Returns: Pointer to usable payload, or NULL on failure

`int mm_read(void ptr, size_t offset, void buf, size_t len)`

Safely reads data from an allocated block with validation and brownout detection.

Validation:

Pointer bounds checking
Alignment verification
Quarantine status check
Header and payload checksum validation
Brownout pattern detection

Returns: Number of bytes read, or -1 on error

`int mm_write(void ptr, size_t offset, const void src, size_t len)`

Writes data to an allocated block with automatic padding and checksum updates.

Features:

Bounds and alignment validation
Overwrites unused bytes with pattern
Recalculates both checksums after write
Validates all safety conditions before write

Returns: Number of bytes written, or -1 on error

`void mm_free(void *ptr)`

Frees an allocated block and returns it to the free list.

Coalescing Logic:

Validates pointer and header
Finds insertion point in address-ordered list
Merges with previous block if adjacent
Merges with next block if adjacent
Overwrites freed memory with unused pattern
Updates all checksums and pointers

`void mm_heap_stats()`

Prints comprehensive heap statistics and visualization for debugging.

Implementation Highlights

Padding Calculation

size_t padding_needed(size_t size) {
    size_t remainder = size % ALIGNMENT;
    return (ALIGNMENT - remainder) % ALIGNMENT;
}

Ensures all blocks maintain 40-byte alignment for consistency.

Checksum Algorithms

Header Checksum (rotate-and-XOR):

uint32_t crc = 0x55555555;  // Non-zero seed
crc ^= (uintptr_t)header;
crc = rotl(crc, 5);
// ... includes size, flags, pointers, payload checksum
return (uint16_t)((crc >> 16) ^ (crc & 0xFFFF));

Payload Checksum (Fletcher-16):

for (size_t i = 0; i < payload_size; ++i) {
    sum1 = (sum1 + payload_ptr[i]) % 255;
    sum2 = (sum2 + sum1) % 255;
}
return (size_t)((sum2 << 8) | sum1);

Bit Manipulation for Flags

// Set is_free flag
size_t set_is_free(size_t total_size, _Bool is_free) {
    return is_free ? (total_size | 0x1) : (total_size & ~0x1);
}

// Get actual size (mask out lower 3 bits)
size_t get_actual_size(size_t total_size) {
    return total_size & ~0x7;
}

Building & Running

Compilation

# Build all targets (runme executable and shared library)
make

# Clean build artifacts
make clean

# Rebuild from scratch
make rebuild

Running Tests

# Run the simple demonstration
./runme

# Run comprehensive test suite
./test_suite

# Run with visualization (uncomment visualization calls in allocator.c first)
./runme

Shared Library Usage

The liballocator.so shared library can be linked against other programs:

gcc -o myprogram myprogram.c -L. -lallocator

Testing

The project includes a comprehensive test suite (test_suite.c) covering:

Initialization tests: Valid/invalid heap parameters
Allocation tests: Various sizes, edge cases, fragmentation scenarios
Read/Write tests: Boundary conditions, validation, brownout detection
Free tests: Single/multiple frees, coalescing verification
Corruption tests: Header/payload corruption detection, quarantine behavior
Stress tests: Intensive allocation/deallocation patterns

See analysis.txt for full test output demonstrating all functionality.

Technical Challenges & Solutions

This being my first major C project, several challenges arose:

1. Pointer Arithmetic Complexity

Managing pointer arithmetic between headers and payloads required careful casting and offset calculations. The consistent use of HEADER_SIZE and alignment calculations proved essential.

2. Checksum Integration

Determining what to include in header checksums (should it include its own value?) required careful thought. The solution: calculate it over all other fields and store separately.

3. Coalescing Logic

Merging adjacent blocks while maintaining free list integrity and updating all neighbor pointers correctly was intricate. The address-ordered list simplified this significantly.

4. Debugging Memory Issues

Without standard debugging tools (can't use printf reliably in corrupted memory), the heap visualizer became invaluable for understanding allocator state.

Code Quality

Compiler Flags: -Wall -Wextra -Werror - Zero warnings policy
Copyright Headers: All source files properly attributed
Consistent Style: Following standard C conventions
Extensive Comments: Key algorithms and edge cases documented
Modular Design: Clear separation of concerns across files

Performance Characteristics

Allocation: O(n) worst case for first-fit search through free list
Deallocation: O(n) for finding insertion point in address-ordered list
Coalescing: O(1) once insertion point found (only checks immediate neighbors)
Read/Write: O(n) for validation and data copy operations

For detailed performance analysis and benchmarks, refer to the coursework report.

Future Improvements

Potential enhancements discussed in the report include:

Best-fit or segregated free lists for improved allocation speed
Explicit doubly-linked list for all blocks (not just free ones)
Memory defragmentation routines
Thread safety with mutexes for concurrent access
Memory pooling for common allocation sizes

Reflection

This coursework served as an intensive introduction to:

Low-level memory management in C
Pointer manipulation and bit-packing techniques
Data structure implementation (linked lists, checksums)
Debugging complex systems-level code
Writing robust, defensive code with comprehensive validation

The experience of building a functional memory allocator from scratch provided invaluable insights into how operating systems and runtime libraries manage memory, and reinforced the importance of rigorous testing and validation in systems programming.

References

Course materials: COMP2221 Systems Programming, Durham University
Full technical documentation: COMP2221_Systems_Programming_Summative_Coursework_Report.pdf
Source code repository: This directory

License

This code was submitted as coursework for COMP2221 at Durham University.

Name		Name	Last commit message	Last commit date
Latest commit History 1 Commit
liballocator.so.dSYM/Contents		liballocator.so.dSYM/Contents
test_suite.dSYM/Contents		test_suite.dSYM/Contents
.gitignore		.gitignore
COMP2221_Systems_Programming_Summative_Coursework_Report.pdf		COMP2221_Systems_Programming_Summative_Coursework_Report.pdf
Makefile		Makefile
allocator.c		allocator.c
allocator.h		allocator.h
main.c		main.c
readme.md		readme.md
test_suite.h		test_suite.h
visualiser.c		visualiser.c
visualiser.h		visualiser.h

Folders and files

Latest commit

History

Repository files navigation