Heap Consistency Checker for Malloc Lab

Introduction: Why Heap Consistency Checking Matters

In the CMPSC473 malloc lab, you are tasked with implementing your own dynamic storage allocator – versions of malloc, free, and realloc. One of the most critical (and graded) components is the heap consistency checker, mm_checkheap. This function is not just a checkbox for the rubric; it is your best debugging ally. Dynamic memory allocators are notoriously tricky because they involve raw pointer manipulation, untyped memory, and low-level bit operations. A single off-by-one error can corrupt the heap silently, leading to crashes hours later. By writing a thorough heap checker, you catch bugs early and ensure your allocator is correct and robust.

Think of your heap consistency checker as a real-time health monitor for your allocator. In the same way that a fitness tracker checks your heart rate and steps, your checker scans the heap for invariants that must always hold. This tutorial will guide you through designing and implementing a powerful heap checker, using examples and strategies that align with the assignment requirements.

Understanding the Heap Layout

Before writing the checker, you need to understand the data structures used by your allocator. Most implementations use an implicit free list or an explicit free list (e.g., segregated lists). For this tutorial, we assume an implicit free list with a block header/footer and coalescing. Each block (allocated or free) has a header containing the block size and allocation status. Free blocks additionally have a footer (same as header) and possibly pointers for the free list.

Key invariants to check:

Every block header and footer must be consistent (size and allocated bit match).
No contiguous free blocks (coalescing should have merged them).
All free blocks are properly linked in the free list (if using explicit list).
Allocated blocks do not overlap.
Heap boundaries are respected.

Step-by-Step Implementation of mm_checkheap

Your mm_checkheap function will take a line number (for debugging) and return true if the heap is consistent, false otherwise. It should print error messages using dbg_printf when checks fail. Here's a structured approach:

1. Check the Prologue and Epilogue Blocks

Most allocators have a prologue block (allocated, minimal size) and an epilogue block (sentinel, allocated, size 0). Verify that the prologue and epilogue exist and have correct headers.

if (GET_SIZE(HDRP(heap_start)) != DSIZE || !GET_ALLOC(HDRP(heap_start))) {
    dbg_printf("Prologue block invalid at line %d\n", line_number);
    return false;
}

2. Iterate Through All Blocks

Walk through the heap from start to end, checking each block. For each block, verify:

Header and footer consistency (if using footers).
Block size is positive and aligned.
No overlapping with previous block (check that the next block starts exactly at current block's end).
If the block is free, it should be coalesced with neighbors (i.e., previous and next blocks should not both be free).

char *bp = heap_start;
while (bp < heap_end) {
    size_t size = GET_SIZE(HDRP(bp));
    if (size == 0) break; // epilogue
    // Check alignment
    if (size % DSIZE != 0) { ... }
    // Check header/footer consistency
    if (GET_ALLOC(HDRP(bp)) != GET_ALLOC(FTRP(bp))) { ... }
    // Check coalescing: if free, ensure prev/next are not both free
    if (!GET_ALLOC(HDRP(bp))) {
        if (!GET_ALLOC(HDRP(PREV_BLKP(bp))) && !GET_ALLOC(HDRP(NEXT_BLKP(bp)))) {
            dbg_printf("Coalescing error at line %d\n", line_number);
            return false;
        }
    }
    bp = NEXT_BLKP(bp);
}

3. If Using an Explicit Free List, Validate the List

If your allocator maintains a free list (e.g., singly linked list of free blocks), you must verify that every free block appears exactly once in the list and that the list does not contain allocated blocks or invalid addresses.

// Traverse free list
char *free_ptr = free_list_head;
while (free_ptr != NULL) {
    if (!IS_FREE(HDRP(free_ptr))) {
        dbg_printf("Free list contains allocated block at %p\n", free_ptr);
        return false;
    }
    // Check that the block is within heap bounds
    if (free_ptr < heap_start || free_ptr > heap_end) { ... }
    free_ptr = GET_NEXT_PTR(free_ptr);
}

4. Check for Overlapping Allocated Blocks

While iterating through all blocks, you can also ensure that allocated blocks do not overlap. This is inherently checked by verifying that each block's address and size are consistent.

Debugging with Real-World Analogies

To make the concept more relatable, consider this: Your heap consistency checker is like the error-checking system in a popular video game. In Fortnite, the game constantly checks that player positions, inventory, and building structures are consistent. If a wall appears inside a player, the game flags an error. Similarly, your checker ensures that no two allocated blocks overlap and that free blocks are properly merged.

Another analogy: Think of your allocator as a smart inventory system for a viral e-commerce app (like Temu or Shein). The heap is the warehouse, and each block is a shelf. The consistency checker ensures that shelves are properly labeled, not overlapping, and that empty space is consolidated for efficient storage. Without it, the warehouse would be chaotic, leading to lost items (memory leaks) or crashes.

Testing Your Checker

To verify your checker, intentionally introduce bugs in your allocator (e.g., skip coalescing, corrupt a header) and run your checker. It should detect the inconsistency. Use the provided trace files to test under various workloads.

Remember to call mm_checkheap(__LINE__) frequently during development, especially after malloc and free operations. This will help you pinpoint where things go wrong.

Common Pitfalls and Tips

Alignment: Ensure all pointers are 16-byte aligned as required.
Footers: If you use footers, they must be updated correctly when splitting or coalescing.
Edge cases: Test with zero-size requests, NULL pointers, and realloc that shrinks or grows.
Performance: The checker should not be called in production code, but during development, it's invaluable.

Conclusion

A well-written heap consistency checker is your safety net in the malloc lab. It not only earns you points on the rubric but also saves hours of debugging. By methodically verifying each invariant, you build a robust allocator that you can trust. Start simple, test often, and expand your checker as you add features. Good luck!