5.1.17 · D5C Programming
Question bank — Heap fragmentation
These items target the misconceptions the topic invites: confusing "free total" with "largest hole", confusing fragmentation with leaks, assuming coalescing always happens, and forgetting the degenerate/edge cases.
Vocabulary you need first
Every trap below leans on four words. Pin them down before you start, so no symbol or term is a surprise.
The picture below is the reference for the whole page — the "parking lot" every question is really talking about.
Look at the figure: three live blocks A, C fence off two holes. Total free may be large, but the largest single hole (orange) is what a request must fit into. That single idea powers most traps here.
The size symbols the edge-cases use
Look at the figure: your requested bytes (blue), the hidden -byte header (gray), and the rounded-up tail (red) that you paid for but can never use — that red slice is internal fragmentation.
True or false — justify
Total free memory ≥ request size guarantees malloc succeeds.
False —
malloc needs one contiguous range; the free bytes may be scattered as small non-adjacent holes around live blocks (like the two holes in figure s01), so no single hole fits.Fragmentation is a kind of memory leak.
False — a leak is memory never freed (lost forever); fragmented memory is free and tracked, just arranged so it can't satisfy a request.
Freeing every allocation eventually removes all fragmentation.
True at the end — once all live blocks are gone the whole heap coalesces back to one hole; but while blocks are still live, freeing others cannot merge across them.
Internal fragmentation can exist even with a single allocation on a fresh heap.
True — rounding a request up to the block size (header + alignment ) wastes bytes inside that one block regardless of anything else on the heap.
External fragmentation can exist even if every individual block was freed correctly.
True — correct freeing prevents leaks, not fragmentation; frees in a scattered order still leave non-adjacent holes.
The stack suffers from the same fragmentation as the heap.
False — the stack allocates/frees in strict LIFO order, so freed space is always adjacent to the top and never leaves interior holes (see Stack vs Heap; e.g. pushing A then B then popping B always frees the topmost bytes, no interior gap).
A single large malloc followed by a single free can fragment the heap.
False — one alloc then its free leaves the heap in one coalesced hole; fragmentation needs mixed sizes freed in a scattered order.
Coalescing merges any two free holes that exist at the same time.
False — coalescing only merges holes that are physically adjacent in memory; a live block between two holes (block C in figure s01) blocks the merge.
Using a Pool allocator of fixed-size blocks eliminates external fragmentation.
True — every hole is exactly one block size, so any freed block fits any request; there is no "too-small scattered hole" problem (though internal waste can remain).
Doubling how often you call free reduces internal fragmentation.
False — internal waste lives inside a live block due to rounding; you only reclaim it by freeing that block, and the next same-size alloc wastes it again.
Bigger size-class gaps (e.g. powers of two) always make fragmentation worse.
False — coarser classes raise internal waste but shrink the variety of hole sizes, which usually lowers external fragmentation; it is a trade-off, not a strict worsening.
Spot the error
"malloc(40) failed, so the program has run out of memory."
Wrong conclusion — failure can mean the largest single hole < 40 (the orange hole in figure s01) even though plenty of total free memory remains; it is fragmentation, not exhaustion.
"I freed B which sits between live A and C, so the freed 30 bytes join the neighbouring free hole."
Error — B's neighbours are live A and live C, not free holes, so nothing coalesces; the 30 bytes stay an isolated hole.
"To measure fragmentation risk I'll track total free bytes over time."
Wrong metric — total free can stay high while allocations fail; you must track the largest contiguous hole (or the ratio largest-hole / total-free).
"Internal fragmentation is caused by non-adjacent holes."
Confused flavours — non-adjacent holes are external fragmentation; internal fragmentation is the wasted tail inside a rounded-up block (the red slice in figure s02).
"Freeing in the order I allocated (FIFO) coalesces best."
Wrong order — FIFO frees the oldest block first, which is usually buried below live newer blocks; LIFO (stack order) is what lets each free touch the growing hole.
"A compacting garbage collector removes internal fragmentation."
Overclaim — Garbage collection that compacts moves objects to remove external fragmentation; the per-object rounded size (internal waste) is unchanged by moving it.
"Since Memory alignment wastes bytes, disabling alignment removes all fragmentation."
Wrong and dangerous — dropping alignment can cause faults or slow access, and only touches internal waste, doing nothing for external fragmentation.
"malloc(1) only reserves 1 byte, so tiny allocations never fragment."
Error — a minimum chunk size (e.g. 16 or 32 bytes) plus the header means
malloc(1) reserves a whole minimum chunk; thousands of tiny allocs still carve the heap into many small blocks.Why questions
Why must malloc return a contiguous address range at all?
Because a returned pointer plus an offset must index into your object linearly; a split object couldn't be addressed with simple pointer arithmetic.
Why does mixed-size allocation fragment more than same-size allocation?
Same-size blocks leave same-size holes that any future request refits exactly; mixed sizes leave holes of odd sizes that rarely match the next request.
Why does coalescing require checking the physical neighbour, not the free-list order?
Two holes can be next to each other in the free-list yet far apart in memory; only bytes that physically touch (as figure s01 shows) can merge into one addressable range.
Why does LIFO / stack-order freeing avoid fragmentation?
Each freed block is always adjacent to the last-created hole, so every
free coalesces into one growing hole, returning the heap toward a single block.Why is an Arena allocator immune to interior fragmentation during its lifetime?
It bumps a pointer forward for every allocation and frees everything at once, so no interior holes are ever created — allocation is just moving one cursor.
Why does rounding requests up to a multiple of the alignment quantum cause waste?
The request plus header rarely lands exactly on a block boundary, so the ceiling pushes it to the next multiple of and the gap becomes untouchable internal waste (see malloc and free).
Why can a heap be "50% free" yet fail a request half that size?
The free half may be shattered into many tiny holes fenced apart by live blocks, so the largest hole is far smaller than the request.
Why do power-of-two size classes trade one fragmentation type for another?
Snapping to the next power of two enlarges (more internal waste) but produces only a handful of distinct block sizes, so freed holes refit future requests more often (less external waste).
Edge cases
malloc(0) — does it fragment?
Edge case — it may return NULL or a unique tiny pointer, but it requests no usable payload; with a minimum chunk size it still reserves one minimum chunk of overhead, contributing minor internal cost, not external fragmentation.
Requesting exactly the block size (e.g. a perfect multiple of ) — internal waste?
Zero rounding waste — the request already lands on a block boundary, so and apart from the header itself.
Heap with exactly one hole and one request of that hole's size — fragmentation?
None — a single hole exactly filling the request is the ideal case; both external and (if boundary-aligned) internal waste are zero.
Two adjacent free holes with no live block between them — is this fragmentation?
Not stable fragmentation — a correct allocator coalesces adjacent holes into one, so they behave as a single larger hole immediately.
All allocations identical size, freed in any order — external fragmentation?
None that blocks requests — every hole equals one block, so any same-size request fits any hole regardless of adjacency; scattered frees are harmless here.
malloc(1) on an allocator with a 16-byte minimum chunk — how much internal waste?
With header bytes plus rounding up to the 16-byte minimum, nearly the whole chunk is waste — payload bytes lost (before counting the header), so tiny requests are the worst internal-waste offenders.
Freeing the same pointer twice (double free) — related to fragmentation?
Unrelated bug — double free corrupts the free-list (undefined behaviour), which is a correctness fault, not the "free but unusable" arrangement that defines fragmentation.
Recall One-line summary to carry away
Fragmentation is about the largest contiguous hole, never the total free bytes; external = scattered holes fenced by live blocks, internal = wasted tail from rounding to a block/size-class; neither is a leak.
Connections
- Heap fragmentation — parent topic these traps drill
- malloc and free — the allocator whose free-list and headers these questions probe
- Memory leaks — the bug fragmentation is repeatedly confused with
- Stack vs Heap — why the stack sidesteps all of this (strict LIFO, no interior holes)
- Memory alignment — the root of the internal-waste edge cases
- Pool allocator / Arena allocator — designs that dodge external fragmentation
- Garbage collection — compaction and what it does (and does not) fix