Heap fragmentation

WHAT is heap fragmentation?

WHY it happens (the root cause): malloc must return a single contiguous range of addresses. The heap is managed as a list of free "holes". When you malloc/free blocks of many different sizes in a mixed order, the free holes end up interleaved with live blocks. You cannot merge two free holes unless they are physically adjacent in memory.

HOW it arises — derive it from scratch

Let the heap be a linear array of bytes. Model allocation by a free-list of (start, size) holes. Start with one big hole [0, 100).

We simulate malloc(n) = take n bytes from a hole (first-fit), free(p) = return a hole, coalescing with neighbours if adjacent.

Step                Heap layout (■=used, ·=free), 100 bytes
malloc A=30         ■■■A■■■············································  free: [30,70)
malloc B=30         ■■■A■■■■■■B■■■······································  free: [60,40)
malloc C=30         ■■■A■■■■■■B■■■■■■C■■■·······························  free: [90,10)
free B              ■■■A■■■······■■■C■■■·······························  free: [30,30)+[90,10)

Now total free = 30 + 10 = 40 bytes. Ask for malloc(40):

Coalescing — the defence

If instead we had freed in stack order (free C, then B, then A), each free coalesces with the growing right-hand hole and the heap returns to one big [0,100) hole — zero fragmentation.

Internal fragmentation — derive the waste

Real allocators round every request up to a block size (for alignment + bookkeeping). Suppose blocks come in sizes that are multiples of 16 bytes, plus an 8-byte header.

Flashcards

What is external fragmentation?

Enough total free memory exists, but it is split into non-contiguous holes, so no single hole is big enough for the request.

What is internal fragmentation?

The allocator gives a block larger than requested (rounding/alignment/header); the unused tail inside the block is wasted.

Why can't malloc combine two free holes to satisfy a big request?

malloc must return one contiguous address range; non-adjacent holes can't be merged across a live block.

What is coalescing?

Merging a freshly freed block with a physically adjacent free neighbour into one larger hole.

Coalescing only works between blocks that are...?

Physically adjacent in memory.

Formula for allocated block size given request r, header h, alignment a?

B = ceil((r+h)/a) * a

For r=20, h=8, a=16, internal waste is?

32 - 20 = 12 bytes.

Which free order avoids fragmentation for nested allocations?

LIFO / stack order (free most-recently-allocated first), so each free coalesces with the adjacent hole.

Does fragmentation mean a memory leak?

No — leaked memory is never freed; fragmented memory IS free but unusably arranged.

Recall Feynman: explain to a 12-year-old

Your toy box has 100 blocks of space. You take out toys and put them back. After playing, you have empty gaps here and there — enough empty space for a big robot toy in total — but the gaps are tiny and spread out between other toys. The robot needs one big empty spot, and there isn't one, even though the box is "kind of empty." That stuck-feeling is fragmentation. If you always put back the toy you took out last first, the empty space stays in one neat corner and the robot fits!

Connections

malloc and free — the allocator whose free-list creates/coalesces holes
Memory leaks — different bug: memory never returned vs. returned but scattered
Stack vs Heap — the stack never fragments (strict LIFO); the heap can
Memory alignment — root cause of internal fragmentation
Pool allocator / Arena allocator — fixed-size pools that eliminate external fragmentation
Garbage collection — compacting GCs physically move objects to defragment

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, heap fragmentation ka matlab hai: memory free toh hai, par use ho nahi sakti, kyunki woh chote-chote tukdo mein bikhri padi hai. Socho ek parking lot — beech beech mein gaadiyan khadi hain aur khaali jagah idhar-udhar bachi hai. Total khaali jagah bahut hai, par ek bus ke liye continuous jagah nahi milti. Yahi external fragmentation hai. malloc ko hamesha ek hi continuous block chahiye, isliye do alag-alag chote holes ko jod nahi sakta jab beech mein koi live block ho.

Jab tum free karte ho, allocator dekhta hai ki bagal wala block bhi free hai kya — agar haan, toh dono ko milakar ek bada hole bana deta hai, isko coalescing kehte hain. Par yeh sirf physically adjacent blocks ke liye chalta hai. Isiliye agar tum random order mein free karte ho, holes scattered reh jaate hain. Trick yeh hai: agar tum LIFO order mein free karo (jo last allocate kiya woh pehle free), toh saari free space ek corner mein jud jaati hai — fragmentation almost zero.

Doosra type hai internal fragmentation — allocator alignment aur header ke liye tumhari request ko upar round kar deta hai. Maan lo tumne 20 bytes maange, header 8 byte, alignment 16 byte ka — toh block ban gaya 32 byte, aur 12 byte andar hi waste ho gaye. Yeh memory tumhare block ke andar phasi rehti hai, free karne par hi wapas milti hai.

Yeh important kyun hai? Lambe samay tak chalne wale programs (servers, games) mein agar fragmentation badhti rahe, toh ek din malloc NULL de dega bina kisi leak ke — sirf isliye ki memory theek se arranged nahi. Solution: same-size objects ke pools/arenas use karo, ya sizes ko alignment ke multiple rakho.