CS Notes

Memory Management & GC

3 min read

Memory is the canvas of the systems programmer. Managing it manually is both a superpower and a curse.

The Three Lives of a Variable

Where a variable lives defines when it dies.

ZoneLifetimeAnalogy
StackFunction Scope. Created when function starts, destroyed when it returns.A Notepad. Fast, convenient, but pages are torn out immediately when you leave the room.
HeapManual Control. Alive until you explicitly kill it (free).A Warehouse. Massive storage, but you must keep a log of where you put things.
Global/StaticProgram Scope. Alive from start to finish.A Billboard. Always visible, never moves.

The Stack Trap

NEVER return a pointer to a stack variable.

int *bad_function() {
    int x = 10;
    return &x; // x dies right here!
}

The caller receives a pointer to a “ghost” memory slot that will be overwritten by the next function call.

The Heap Contract (malloc / free)

Using malloc isn’t just asking for bytes; it’s signing a contract.

  1. Ownership: “I am now responsible for these bytes.”
  2. Responsibility: “I must free them exactly once.”
  3. Limits: “I will not touch bytes outside the requested range.”

Visualizing the Heap Payload

When you ask malloc(16), the allocator gives you a pointer to 16 bytes. But it secretly allocates more.

[ Header (Size: 24, Status: Busy) ]  <-- Hidden from you
[ Payload (16 bytes)              ]  <-- Your pointer 'p' starts here
[ Padding/Alignment               ]

If you write p[-1], you overwrite the header. The allocator gets confused and crashes later.

Garbage Collection (GC): “The Cleaning Crew”

Languages like Java or Python use GC. C does not, but understanding GC is crucial because it’s effectively what you must simulate in your head.

GC is based on Reachability.

  • Imagine memory as a graph of nodes (objects) connected by arrows (pointers).
  • Roots are the entry points: Registers, Stack Variables, Global Variables.

The Algorithm: Mark and Sweep

  1. Stop the World: Pause the program.
  2. Mark: Start at the Roots. Follow every arrow. Mark every node you visit as “Live”.
  3. Sweep: Walk through the entire heap. If a node is not marked, nobody can reach it. It is garbage. Reclaim it.

Fragmentation: The Warehouse Problem

Why can malloc fail even if we have free memory?

External Fragmentation: Imagine you have 100 bytes of free space, but it’s split into two chunks of 50 bytes separated by a used block. If you ask for 80 bytes, malloc fails. Total Free: 100. Max Contiguous: 50.

Internal Fragmentation: You ask for 5 bytes. The allocator works in blocks of 16 bytes. It gives you 16. 11 bytes are wasted inside the block.

Practice: Debugging Memory

Scenario 1: The Leak

Loop running 1,000 times, allocating 1KB, never freeing. Result: RAM usage climbs steadily until the OS kills the process (OOM Killer). Fix: Every malloc needs a matching free in every code path.

Scenario 2: Double Free

free(p);
free(p);

The first free marks the block as “Available”. The second free sees an “Available” block and corrupts the free-list details. This often leads to security exploits. Fix: Set p = NULL; after freeing. free(NULL) is safe (does nothing).

Scenario 3: Use-After-Free

free(p);
printf("%d", *p);

The memory at p might now belong to someone else! You are reading corrupted data or crashing.

Graph View

Backlinks