Building a Garbage Collector from Scratch part2
Introduction
This article explores a custom memory allocator implementation that manages a fixed-size heap using two complementary data structures. The allocator demonstrates fundamental concepts of dynamic memory management, including allocation, deallocation, and memory fragmentation handling through chunk merging.
Architecture Overview
The allocator is built on a simple yet effective architecture that divides memory into chunks and tracks them using separate lists for allocated and freed memory regions.
┌─────────────────────────────────────────────────────────────┐
│ HEAP (640KB Fixed Array) │
│ │
│ ┌──────────┐ ┌─────────────┐ ┌──────┐ ┌──────────────┐│
│ │ Allocated│ │ Free │ │Alloc │ │ Free ││
│ │ Chunk │ │ Chunk │ │Chunk │ │ Chunk ││
│ └──────────┘ └─────────────┘ └──────┘ └──────────────┘│
└─────────────────────────────────────────────────────────────┘
│ │ │ │
└───────┬───────┴──────┬───────┴────────────┘
│ │
┌───────▼──────┐ ┌───▼──────────┐
│ alloced_Chunks│ │ freed_chunks │
│ (Tracking) │ │ (Tracking) │
└───────────────┘ └──────────────┘
Core Components
Fixed Heap: A static 640KB character array serving as the memory pool
Chunk Lists: Two separate tracking structures for allocated and freed memory
Chunk Operations: Insert, remove, find, and merge operations
Allocator Interface:
heap_alloc()andheap_free()functions
The Chunk Data Structure
Basic Chunk Definition
typedef struct {
void *start;
size_t size;
} Chunk;
A Chunk is the fundamental unit representing a contiguous block of memory. It contains:
start: A pointer to the beginning of the memory block
size: The number of bytes in this memory block
Visual Representation:
Chunk Structure:
┌─────────────────┬─────────────────┐
│ start (void*) │ size (size_t) │
│ (8 bytes) │ (8 bytes) │
└─────────────────┴─────────────────┘
│
└──────► Points to actual memory location in heap
The Chunk List Structure
typedef struct {
size_t count;
Chunk chunks[chunk_list_CAP];
} chunk_List;
The chunk_List is a container that manages multiple chunks:
count: Number of currently tracked chunks
chunks: Fixed-size array holding up to 1024 chunks
Visual Layout:
chunk_List Structure:
┌────────────────────────────────────────────────────────┐
│ count: 3 │
├────────────────────────────────────────────────────────┤
│ chunks[0]: {start: 0x1000, size: 100} │
│ chunks[1]: {start: 0x1100, size: 200} │
│ chunks[2]: {start: 0x2000, size: 150} │
│ chunks[3]: {empty} │
│ ... │
│ chunks[1023]: {empty} │
└────────────────────────────────────────────────────────┘
Key Property: The chunks array is maintained in sorted order by starting address, which enables efficient binary search operations.
Global State: Two-List System
The allocator maintains two global chunk lists:
chunk_List alloced_Chunks = {0}; // Tracks allocated memory
chunk_List freed_chunks = { // Tracks available memory
.count = 1,
.chunks = {
[0] = {.start = heap, .size = sizeof(heap)}
}
};
Initial State Diagram
At Startup:
┌─────────────────────────────────────────────────────┐
│ HEAP (640KB) │
│ ┌──────────────────────────────────────────────┐ │
│ │ Entirely Free (640KB) │ │
│ └──────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────┘
alloced_Chunks: freed_chunks:
┌──────────────┐ ┌──────────────────────────┐
│ count: 0 │ │ count: 1 │
│ chunks: [] │ │ chunks[0]: │
└──────────────┘ │ start: heap │
│ size: 640000 │
└──────────────────────────┘
Chunk List Operations
1. Chunk Insertion (chunk_list_insert)
This operation adds a new chunk while maintaining sorted order.
Algorithm:
Add the new chunk at the end of the array
Bubble it backwards (insertion sort) until it's in the correct position
Increment the count
Visual Example:
Before Insertion (inserting chunk at 0x1500, size 100):
chunks: [0x1000] [0x2000] [0x3000] [ empty ]
↑ ↑ ↑
Step 1: Add at end
chunks: [0x1000] [0x2000] [0x3000] [0x1500]
↑ (new)
Step 2: Bubble backwards
chunks: [0x1000] [0x2000] [0x1500] [0x3000]
↑ (moved)
Final: Sorted order maintained
chunks: [0x1000] [0x1500] [0x2000] [0x3000]
Code Flow:
// Add at end
list->chunks[list->count] = new_chunk;
// Bubble backwards while out of order
for (i = count; i > 0 && chunks[i].start < chunks[i-1].start; --i) {
swap(chunks[i], chunks[i-1]);
}
list->count++;
2. Chunk Finding (chunk_list_find)
Uses binary search to locate a chunk by its starting address.
Algorithm Visualization:
Finding chunk at address 0x2000:
chunks: [0x1000] [0x1500] [0x2000] [0x3000] [0x4000]
low mid high
Step 1: Compare with middle
0x2000 < 0x2000? No
0x2000 > 0x2000? No
Found!
Returns: Index 2
Binary Search Benefits:
Time Complexity: O(log n) instead of O(n)
Efficient for large chunk lists
Requires sorted array (maintained by insert operation)
3. Chunk Removal (chunk_list_remove)
Issue in Original Code: The implementation has a critical bug!
// BUGGY CODE:
for (int i = 0; i < list->count-1; ++i) {
list->chunks[i] = list->chunks[i+1];
}
The Bug:
Remove index 1 from: [A] [B] [C] [D]
↑ (remove this)
Wrong: Shifts ALL chunks left, including those before index
Result: [B] [C] [D] [D] ← Wrong!
Correct: Should shift only chunks AFTER the index
Result: [A] [C] [D] ← Correct!
Correct Implementation:
for (int i = index; i < list->count - 1; ++i) {
list->chunks[i] = list->chunks[i+1];
}
list->count--;
4. Chunk Merging (chunk_list_merge)
This operation combines adjacent free chunks to reduce fragmentation.
Algorithm:
Iterate through source chunks in order
If current chunk is adjacent to previous chunk, merge them
Otherwise, add as separate chunk
Visual Example:
Before Merge:
freed_chunks: [0x1000, 100] [0x1064, 50] [0x2000, 200] [0x20C8, 100]
└─────┬─────┘ └────┬────┘ └─────┬─────┘
Adjacent! │ Adjacent!
│
Not adjacent to others
After Merge:
freed_chunks: [0x1000, 150] [0x2000, 300]
└──────┬──────┘ └────┬─────┘
Merged Merged
Adjacency Check:
if ((char *)top_chunk->start + top_chunk->size == chunk.start) {
// Chunks are adjacent, merge them
top_chunk->size += chunk.size;
}
Memory Layout:
Chunk A: Start=0x1000, Size=100
Chunk B: Start=0x1064, Size=50
Check: 0x1000 + 100 = 0x1064 ← Matches Chunk B start!
Result: Merged chunk: Start=0x1000, Size=150
Memory Allocation (heap_alloc)
Algorithm Flow
heap_alloc(size) Process:
1. Search freed_chunks for suitable chunk
┌─────────────────────────────┐
│ For each chunk in freed_chunks│
│ If chunk.size >= size │
└─────────────────────────────┘
│
▼
2. Found suitable chunk
┌─────────────────────────────┐
│ Remove from freed_chunks │
│ Add to alloced_Chunks │
└─────────────────────────────┘
│
▼
3. Handle remaining space
┌─────────────────────────────┐
│ If chunk.size > size │
│ Create tail chunk │
│ Add tail to freed_chunks │
└─────────────────────────────┘
│
▼
4. Return pointer to allocated space
Detailed Example
Request: Allocate 100 bytes
Initial State:
freed_chunks:
┌────────────────────────────────────┐
│ Chunk: start=0x1000, size=500 │
└────────────────────────────────────┘
Step 1: Find suitable chunk (500 >= 100 ✓)
Step 2: Split the chunk
┌──────────────┬─────────────────────┐
│ Allocated │ Remaining │
│ (100 bytes) │ (400 bytes) │
│ 0x1000 │ 0x1064 │
└──────────────┴─────────────────────┘
Step 3: Update lists
alloced_Chunks:
┌────────────────────────────────────┐
│ Chunk: start=0x1000, size=100 │
└────────────────────────────────────┘
freed_chunks:
┌────────────────────────────────────┐
│ Chunk: start=0x1064, size=400 │
└────────────────────────────────────┘
Return: 0x1000
Bug in Original Code:
// PROBLEM: Returns chunk.start for ALL iterations!
for(int i=0; i<freed_chunks.count; i++){
// ... allocation logic ...
return chunk.start; // ← Should be inside if-statement
}
Memory Deallocation (heap_free)
Algorithm Flow
heap_free(ptr) Process:
1. Validate pointer
┌─────────────────────────────┐
│ If ptr == NULL, return │
└─────────────────────────────┘
│
▼
2. Find chunk in alloced_Chunks
┌─────────────────────────────┐
│ Use binary search │
│ Assert: chunk must exist │
└─────────────────────────────┘
│
▼
3. Move chunk to freed list
┌─────────────────────────────┐
│ Insert into freed_chunks │
│ Remove from alloced_Chunks │
└─────────────────────────────┘
Detailed Example
Request: Free pointer at 0x1064
Before Free:
alloced_Chunks:
┌────────────────┬────────────────┬────────────────┐
│ 0x1000 (100) │ 0x1064 (50) │ 0x2000 (200) │
└────────────────┴────────────────┴────────────────┘
↑
Free this!
freed_chunks:
┌────────────────┐
│ 0x3000 (1000) │
└────────────────┘
Step 1: Find chunk at 0x1064 in alloced_Chunks
→ Found at index 1
Step 2: Insert into freed_chunks (maintaining sort)
Step 3: Remove from alloced_Chunks
After Free:
alloced_Chunks:
┌────────────────┬────────────────┐
│ 0x1000 (100) │ 0x2000 (200) │
└────────────────┴────────────────┘
freed_chunks:
┌────────────────┬────────────────┐
│ 0x1064 (50) │ 0x3000 (1000) │
└────────────────┴────────────────┘
Complete Allocation Cycle Example
Let's trace through the example in main():
Step 1: Initial State
HEAP: [═══════════════ 640KB Free ═══════════════]
alloced_Chunks: count=0, []
freed_chunks: count=1, [{heap, 640000}]
Step 2: Allocate String (18 bytes)
char *s = heap_alloc(strlen("MIDO LOVES MALOKY") + 1); // 18 bytes
HEAP: [18B Used][═════ 639982B Free ═════]
↑
s points here
alloced_Chunks: count=1, [{heap, 18}]
freed_chunks: count=1, [{heap+18, 639982}]
Step 3: Use the Memory
strcpy(s, "MIDO LOVES MALOKY");
HEAP: [M][I][D][O][ ][L][O][V][E][S][ ][M][A][L][O][K][Y][\0][Free...]
↑───────────────── 18 bytes ────────────────────────↑
Step 4: Free the Memory
heap_free(s);
HEAP: [═══════════════ 640KB Free ═══════════════]
alloced_Chunks: count=0, []
freed_chunks: count=1, [{heap, 18}, {heap+18, 639982}]
↑ Should be merged! ↑
Note: Without calling heap_collect(), the two adjacent chunks remain separate, causing fragmentation.
Data Structure Efficiency Analysis
Time Complexity
| Operation | Complexity | Reason |
chunk_list_insert | O(n) | Insertion sort for ordering |
chunk_list_find | O(log n) | Binary search |
chunk_list_remove | O(n) | Array shifting |
chunk_list_merge | O(n) | Single pass through chunks |
heap_alloc | O(n²) worst case | Search O(n) + insert O(n) |
heap_free | O(n) | Find O(log n) + insert O(n) |
Space Complexity
Total Memory Usage:
1. Heap: 640,000 bytes
2. alloced_Chunks: 8 + (1024 × 16) = 16,392 bytes
3. freed_chunks: 8 + (1024 × 16) = 16,392 bytes
Total: ~672KB
Overhead: ~5% of heap size
Design Trade-offs
Advantages:
✓ Simple, easy to understand
✓ Fixed memory footprint (no dynamic allocation)
✓ Binary search for fast lookups
✓ Separate tracking prevents allocation/free confusion
Disadvantages:
✗ Fixed maximum number of chunks (1024)
✗ Linear insertion time due to sorting
✗ First-fit allocation (not optimal for all workloads)
✗ No automatic defragmentation without
heap_collect()
Critical Bugs and Issues
1. Allocation Return Bug
// Current (WRONG):
for(int i=0; i<freed_chunks.count; i++){
if(chunk.size >= size){
// ... allocation logic ...
}
return chunk.start; // ← Returns even if size didn't match!
}
Fix: Move return inside the if-statement.
2. Removal Bug
// Current (WRONG):
for (int i = 0; i < list->count-1; ++i) { // ← Starts at 0!
list->chunks[i] = list->chunks[i+1];
}
Fix: Start loop at index instead of 0.
3. Pointer Arithmetic Bug
// Potentially unsafe:
(int *)chunk.start + size // ← Advances by size * sizeof(int)!
Fix: Cast to char* for byte-level arithmetic:
(char *)chunk.start + size
Conclusion
This custom heap allocator demonstrates fundamental memory management concepts through a dual-list tracking system. The Chunk and chunk_List data structures provide a clear separation between allocated and freed memory, enabling efficient allocation and deallocation operations.
The architecture's strength lies in its simplicity and fixed memory footprint, making it suitable for embedded systems or educational purposes. However, the implementation contains several critical bugs that would need correction for production use, and the linear-time insertion operations could be optimized using more sophisticated data structures like balanced trees or segregated free lists.
The sorted-array approach with binary search represents a classic trade-off: simpler code and better cache locality at the cost of O(n) insertions. For systems with frequent allocations and deallocations, a linked-list or tree-based approach might offer better performance.
1. High-Level Architecture Overview
This diagram shows the main components and how they interact. The heap is the raw memory pool, and the two chunk lists track its state.
Code snippet
2. Data Structures
These diagrams illustrate the layout of the Chunk and chunk_List structs.
Chunk Structure
Code snippet
Chunk List Structure
Code snippet
3. Algorithm Flowcharts
These diagrams detail the logic for the key operations.
heap_alloc(size) Process Flow
Code snippet
heap_free(ptr) Process Flow
Code snippet
Chunk Merging Logic
Code snippet
4. Complete Allocation Cycle Sequence
This sequence diagram traces the main() example, showing the interactions between the caller and the allocator's internal state.
Code snippet
