A thread-safe custom heap memory allocator implemented in C, featuring an AVL tree-based free block management system, automatic memory coalescing, and support for both small (brk) and large (mmap) allocations.
- Heap Memory Allocator
- AVL Tree-based free block management for O(log n) allocation/deallocation
- Efficient memory coalescing to reduce fragmentation
- Block splitting to minimize wasted space
- Optimized for both small and large allocations
- Comprehensive boundary checking with headers and footers
- Double-free protection and corruption detection
- Memory pattern verification in debug mode
- Automatic heap trimming to release unused memory
- Thread-safe operations with mutex protection
- Dual allocation strategies: brk() for small allocations, mmap() for large ones
- Automatic fragmentation handling through intelligent coalescing
- Configurable thresholds for allocation strategies
- Comprehensive test suite with unit and integration tests
- Custom testing framework with colorized output
- Stress testing for fragmentation and performance
- Memory integrity verification utilities
The allocator uses a sophisticated block structure with headers and footers for efficient management:
[Block Header][User Data][Footer]
Each block contains:
- Header: Size, state (FREE/ALLOCATED/MMAP_ALLOCATED), AVL tree pointers, height
- User Data: The actual allocated memory returned to the user
- Footer: Size information for backward traversal
Free blocks are organized in an AVL tree (self-balancing binary search tree) sorted by size:
- Primary key: Block size (for efficient best-fit allocation)
- Secondary key: Block address (for deterministic ordering of same-size blocks)
- Balanced operations: O(log n) insertion, deletion, and lookup
-
Small Allocations (< 128KB): Use
brk()system call- Extends the heap boundary
- Efficient for frequent small allocations
- Supports coalescing and splitting
-
Large Allocations (≥ 128KB): Use
mmap()system call- Direct memory mapping from OS
- Avoids heap fragmentation
- Immediate return to OS on free
- GCC or compatible C compiler
- CMake 3.10 or higher
- Linux operating system (uses Linux-specific system calls)
- pthreads library
# Clone the repository
git clone <repository-url>
cd Heap-Memory-Allocator
# Create build directory
mkdir build
cd build
# Configure with CMake
cmake ..
# Build the project
make
# Build specific targets
make alloc # Main demo executable
make run_tests # Build and run all tests# Run the main demonstration
./allocThe demo will:
- Initialize the allocator
- Allocate arrays of different sizes
- Write data to verify memory integrity
- Display allocated data
- Free all memory and show the final free block tree
Initializes a new heap memory allocator instance.
- Parameters:
allocator- Pointer to allocator structure - Thread Safety: Not thread-safe (call before concurrent usage)
Allocates memory of the specified size.
- Parameters:
allocator- Pointer to allocator instancesize- Number of bytes to allocate
- Returns: Pointer to allocated memory or NULL on failure
- Thread Safety: Thread-safe
Frees previously allocated memory.
- Parameters:
allocator- Pointer to allocator instanceptr- Pointer to memory to free
- Thread Safety: Thread-safe
Cleans up allocator resources.
- Parameters:
allocator- Pointer to allocator structure - Thread Safety: Not thread-safe (call after all usage is complete)
Main allocator structure containing:
void *heap_start- Start of the heap regionblock_tree_t free_blocks- AVL tree of free blockspthread_mutex_t lock- Mutex for thread safety
Individual memory block structure:
size_t size- Size of user datablock_state state- Block state (FREE/ALLOCATED/MMAP_ALLOCATED)int height- AVL tree heightstruct block *left, *right- AVL tree pointers
# Run all tests with verbose output
ctest --verbose
# Run specific test categories
./test_basic_malloc
./test_coalescing
./test_integration
# Run tests with memory checking (if Valgrind is installed)
valgrind --leak-check=full ./test_basic_mallocThe test suite includes:
- Basic allocation/deallocation functionality
- Edge cases: zero-size allocation, very large allocations
- Memory alignment verification
- Error handling for invalid parameters
- Stress testing with multiple allocation patterns
- Fragmentation scenarios and coalescing verification
- Mixed size allocations and memory integrity
- Concurrent access patterns (thread safety)
- Allocation/deallocation speed benchmarks
- Memory overhead measurements
- Fragmentation impact analysis
See the comprehensive Testing Guide for detailed instructions on:
- Test file structure and organization
- Available testing macros and utilities
- Best practices for memory testing
- Debugging techniques
- Allocation: O(log n) average case, O(n) worst case for heap growth
- Deallocation: O(log n) for tree operations
- Coalescing: O(log n) for each adjacent block check
- Overhead: 24 bytes per block (header + footer)
- Tree overhead: O(n) for free block tree
- Alignment: 8-byte aligned allocations
Typical performance on modern hardware:
- Small allocations (64B): ~100ns per malloc/free pair
- Medium allocations (1KB): ~200ns per malloc/free pair
- Large allocations (>128KB): ~1µs per malloc/free pair (mmap overhead)
Header (20 bytes): Footer (8 bytes):
┌─────────────────┐ ┌─────────────────┐
│ size_t size │ │ size_t size │
│ block_state │ └─────────────────┘
│ int height │
│ block_t* left │
│ block_t* right │
└─────────────────┘
When a block is freed:
- Check next block: If adjacent and free, merge
- Check previous block: If adjacent and free, merge
- Update tree: Remove old blocks, insert coalesced block
- Update footer: Ensure size consistency
When allocating from a larger free block:
- Check profitability: Ensure remainder is large enough for minimum block size
- Calculate split point: Header + requested size + footer
- Create new block: Initialize remainder as free block
- Update tree: Insert new free block
The allocator is designed for concurrent use:
- Global lock: Protects allocator state during allocation/deallocation
- Tree locks: Fine-grained locking for AVL tree operations
- Atomic operations: Where possible, for performance
// Safe: Multiple threads can use the same allocator
struct HeapMemoryAllocator allocator;
init_HeapMemoryAllocator(&allocator);
// Thread 1
void *ptr1 = my_malloc(&allocator, 100);
// Thread 2 (concurrent)
void *ptr2 = my_malloc(&allocator, 200);
// Both threads can safely free
my_free(&allocator, ptr1);
my_free(&allocator, ptr2);Key configuration constants in include/my_malloc.h:
#define MMAP_THRESHOLD (128 * 1024) // 128KB - Use mmap for larger allocations
#define BRK_TRIM_THRESHOLD (64 * 1024) // 64KB - Trim heap when top block exceeds this
#define MIN_BLOCK_SIZE (48) // Minimum block size for splitting// Compile with -DDEBUG for additional checks
#ifdef DEBUG
#define DEBUG_PRINT(...) printf(__VA_ARGS__)
#else
#define DEBUG_PRINT(...)
#endif#include "my_malloc.h"
int main() {
struct HeapMemoryAllocator allocator;
init_HeapMemoryAllocator(&allocator);
// Allocate memory
int *array = (int*)my_malloc(&allocator, 10 * sizeof(int));
if (array) {
// Use the memory
for (int i = 0; i < 10; i++) {
array[i] = i * i;
}
// Free when done
my_free(&allocator, array);
}
destroy_HeapMemoryAllocator(&allocator);
return 0;
}#include <string.h>
#include <assert.h>
#include "my_malloc.h"
void robust_allocation_example() {
struct HeapMemoryAllocator allocator;
init_HeapMemoryAllocator(&allocator);
// Allocate with error checking
void *ptr = my_malloc(&allocator, 1024);
if (!ptr) {
fprintf(stderr, "Allocation failed\n");
return;
}
// Write pattern to verify memory
memset(ptr, 0xAB, 1024);
// Verify the memory is intact
unsigned char *bytes = (unsigned char*)ptr;
for (int i = 0; i < 1024; i++) {
assert(bytes[i] == 0xAB);
}
my_free(&allocator, ptr);
destroy_HeapMemoryAllocator(&allocator);
}- Cause: Double free, use after free, or corruption
- Solution: Use debugging tools like Valgrind, check for proper free pairing
- Cause: Missing
my_free()calls - Solution: Ensure every
my_malloc()has correspondingmy_free()
- Cause: Excessive fragmentation or inappropriate allocation sizes
- Solution: Adjust allocation patterns, consider memory pooling
- Cause: Missing dependencies or incompatible compiler
- Solution: Ensure GCC and CMake are properly installed
Compile with debugging information:
cmake -DCMAKE_BUILD_TYPE=Debug ..
make# Run with Valgrind for detailed memory analysis
valgrind --leak-check=full --show-leak-kinds=all ./alloc
# Use AddressSanitizer for faster debugging
gcc -fsanitize=address -g main.c src/my_malloc.c -o alloc_debugContributions are welcome! Please:
- Fork the repository
- Create a feature branch (
git checkout -b feature/amazing-feature) - Add tests for new functionality
- Ensure all tests pass (
make run_tests) - Commit changes (
git commit -m 'Add amazing feature') - Push to branch (
git push origin feature/amazing-feature) - Open a Pull Request
- Follow existing code style and naming conventions
- Add comprehensive tests for new features
- Update documentation for API changes
- Ensure thread safety for new operations
This project is licensed under the MIT License.