# 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. ```plaintext ┌─────────────────────────────────────────────────────────────┐ │ HEAP (640KB Fixed Array) │ │ │ │ ┌──────────┐ ┌─────────────┐ ┌──────┐ ┌──────────────┐│ │ │ Allocated│ │ Free │ │Alloc │ │ Free ││ │ │ Chunk │ │ Chunk │ │Chunk │ │ Chunk ││ │ └──────────┘ └─────────────┘ └──────┘ └──────────────┘│ └─────────────────────────────────────────────────────────────┘ │ │ │ │ └───────┬───────┴──────┬───────┴────────────┘ │ │ ┌───────▼──────┐ ┌───▼──────────┐ │ alloced_Chunks│ │ freed_chunks │ │ (Tracking) │ │ (Tracking) │ └───────────────┘ └──────────────┘ ``` ### Core Components 1. **Fixed Heap**: A static 640KB character array serving as the memory pool 2. **Chunk Lists**: Two separate tracking structures for allocated and freed memory 3. **Chunk Operations**: Insert, remove, find, and merge operations 4. **Allocator Interface**: `heap_alloc()` and `heap_free()` functions ## The Chunk Data Structure ### Basic Chunk Definition ```c 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:** ```plaintext Chunk Structure: ┌─────────────────┬─────────────────┐ │ start (void*) │ size (size_t) │ │ (8 bytes) │ (8 bytes) │ └─────────────────┴─────────────────┘ │ └──────► Points to actual memory location in heap ``` ### The Chunk List Structure ```c 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:** ```plaintext 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: ```c 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 ```plaintext 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:** 1. Add the new chunk at the end of the array 2. Bubble it backwards (insertion sort) until it's in the correct position 3. Increment the count **Visual Example:** ```plaintext 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:** ```c // 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:** ```plaintext 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! ```c // BUGGY CODE: for (int i = 0; i < list->count-1; ++i) { list->chunks[i] = list->chunks[i+1]; } ``` **The Bug:** ```plaintext 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:** ```c 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:** 1. Iterate through source chunks in order 2. If current chunk is adjacent to previous chunk, merge them 3. Otherwise, add as separate chunk **Visual Example:** ```plaintext 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:** ```c if ((char *)top_chunk->start + top_chunk->size == chunk.start) { // Chunks are adjacent, merge them top_chunk->size += chunk.size; } ``` **Memory Layout:** ```plaintext 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 ```plaintext 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 ```plaintext 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:** ```c // PROBLEM: Returns chunk.start for ALL iterations! for(int i=0; i= size){ // ... allocation logic ... } return chunk.start; // ← Returns even if size didn't match! } ``` **Fix:** Move `return` inside the if-statement. ### 2\. **Removal Bug** ```c // 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** ```c // Potentially unsafe: (int *)chunk.start + size // ← Advances by size * sizeof(int)! ``` **Fix:** Cast to `char*` for byte-level arithmetic: ```c (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 ```mermaid graph TD subgraph Custom Allocator A[Fixed Heap - 640KB Array] -->|Managed as Chunks| B(alloced_Chunks); A -->|Managed as Chunks| C(freed_chunks); subgraph Allocator Interface direction LR D{heap_alloc} -->|Moves chunk| C; D -->|to| B; E{heap_free} -->|Moves chunk| B; E -->|to| C; end end style A fill:#f9f,stroke:#333,stroke-width:2px style B fill:#lightgreen,stroke:#333,stroke-width:2px style C fill:#lightblue,stroke:#333,stroke-width:2px ``` ### 2\. Data Structures These diagrams illustrate the layout of the `Chunk` and `chunk_List` structs. #### Chunk Structure Code snippet ```mermaid graph LR Chunk --> |Contains| Pointer["start (void*)"]; Chunk --> |Contains| Size["size (size_t)"]; subgraph "Memory in Heap" direction LR MemBlock["Contiguous Memory Block"]; end Pointer --> |Points to| MemBlock; style Chunk fill:#f8d,stroke:#333,stroke-width:2px ``` #### Chunk List Structure Code snippet ```mermaid graph TD Start((Start: chunk_list_merge)):::startNode; End((End)):::endNode; Start --> A["Create new empty temporary list"]; A --> B{"Are there more chunks to process?"}; B -- No --> G["Replace original freed_chunks
with the temporary list"]; B -- Yes --> C["Get next chunk from original list"]; C --> D{"Is temp list empty OR
Is chunk not adjacent to
last chunk in temp list?"}; D -- Yes --> F["Add it as a new chunk to temp list"]; D -- No --> E["Merge with last chunk in temp list"]; E --> B; F --> B; G --> End; classDef startNode fill:#9f9,stroke:#333,stroke-width:2px; classDef endNode fill:#f99,stroke:#333,stroke-width:2px; ``` ### 3\. Algorithm Flowcharts These diagrams detail the logic for the key operations. #### `heap_alloc(size)` Process Flow Code snippet ```mermaid graph TD Start((Start: heap_alloc)) --> A{Iterate through freed_chunks}; A --> B{Find first chunk where
chunk.size >= size}; B -- No suitable chunk found --> C[Return NULL]; B -- Chunk found --> D[Remove chunk from freed_chunks]; D --> E{Does chunk.size > size?}; E -- Yes --> F[Create new 'tail' chunk
with remaining size]; F --> G[Add 'tail' chunk back to freed_chunks]; G --> H[Update original chunk's size to requested 'size']; E -- No --> H; H --> I[Add updated chunk to alloced_Chunks]; I --> J[Return chunk.start pointer]; J --> End((End)); style Start fill:#9f9,stroke:#333,stroke-width:2px style End fill:#f99,stroke:#333,stroke-width:2px ``` #### `heap_free(ptr)` Process Flow Code snippet ```mermaid graph TD Start((Start: heap_free)):::startNode; End((End)):::endNode; Start --> A{"ptr == NULL?"}; A -- Yes --> End; A -- No --> B["Find chunk in alloced_Chunks
where chunk.start == ptr
(using binary search)"]; B -- Not Found --> C["Error: Invalid Pointer / Abort"]; B -- Found --> D["Remove chunk from alloced_Chunks"]; D --> E["Insert chunk into freed_chunks
(maintaining sorted order)"]; E --> F["Optional: Trigger merge/collect operation"]; F --> End; classDef startNode fill:#9f9,stroke:#333,stroke-width:2px; classDef endNode fill:#f99,stroke:#333,stroke-width:2px; ``` #### Chunk Merging Logic Code snippet ```mermaid graph TD subgraph "chunk_List Structure" A["chunk_List"]:::listStyle; A --> B["count (size_t)"]; A --> C["chunks (Array[1024])"]; end C --> D["Chunk 0: {start, size}"]; C --> E["Chunk 1: {start, size}"]; C --> F["..."]; C --> G["Chunk 1023: {start, size}"]; classDef listStyle fill:#dae,stroke:#333,stroke-width:2px; ``` ### 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 ```mermaid sequenceDiagram participant Caller as main() participant Allocator as Heap Allocator participant a_chunks as alloced_Chunks participant f_chunks as freed_chunks Caller->>Allocator: heap_alloc(18) activate Allocator Allocator->>f_chunks: Find chunk >= 18 bytes Note over Allocator, f_chunks: Finds chunk {heap, 640000} Allocator->>f_chunks: Remove {heap, 640000} Allocator->>f_chunks: Insert tail {heap+18, 639982} Allocator->>a_chunks: Insert {heap, 18} Allocator-->>Caller: returns pointer `s` to heap deactivate Allocator Caller->>Caller: strcpy(s, "MIDO LOVES MALOKY") Note over Caller: Memory at `s` is now used Caller->>Allocator: heap_free(s) activate Allocator Allocator->>a_chunks: Find chunk for pointer `s` Note over Allocator, a_chunks: Finds {heap, 18} Allocator->>a_chunks: Remove {heap, 18} Allocator->>f_chunks: Insert {heap, 18} Note right of f_chunks: freed_chunks now has two
adjacent free blocks:
{heap, 18}
{heap+18, 639982} Allocator-->>Caller: return deactivate Allocator ```