Memory Allocation

Definition: The mechanism by which operating systems and language runtimes assign memory regions to programs for stack variables and dynamic heap objects.

How It Works

• Stack allocation: contiguous memory managed by push/pop against the CPU stack pointer. Extremely fast (a single register adjustment), automatically reclaimed when a function returns, and scope-bound. Limited in size, typically a few MB per thread by default.
• Heap allocation: dynamic memory requested at runtime via malloc/new (or a garbage-collected allocator in managed languages). Persists until explicitly freed (or until it becomes unreachable, in GC’d languages), and can vastly exceed stack size.
• The OS gives a process’s heap allocator raw memory in large chunks via brk()/sbrk() (extending the end of the heap segment) or mmap() (mapping anonymous pages, typically used for large allocations). The allocator then subdivides these chunks into the small pieces malloc() actually returns.
• Free-list allocators track freed blocks in a linked list (or several, bucketed by size class) so a future allocation request can reuse a freed block instead of asking the OS for more memory.
• Buddy allocators split memory into power-of-two-sized blocks; freeing a block checks whether its “buddy” (the adjacent same-size block) is also free, and if so merges them back into one larger free block, which keeps external fragmentation bounded at the cost of some internal fragmentation from rounding requests up to a power of two.
• Internal fragmentation is wasted space inside an allocated block (allocator rounds a 20-byte request up to a 32-byte size class); external fragmentation is wasted space between allocated blocks, free memory that exists but is too scattered in small pieces to satisfy a larger request.

Under the Hood

glibc’s default allocator (ptmalloc, derived from dlmalloc) organizes free memory into “bins,” sorted free lists for different size ranges: fast bins for very small, recently-freed chunks (reused without merging, for speed), small/large bins for general sizes, and an “unsorted bin” that recently-freed chunks land in first before being sorted into the right bin. Each allocated chunk carries a small header just before the pointer malloc() returns, storing the chunk’s size and flags, which is how free(ptr) knows how much memory to reclaim without being told the size again.

Production-grade allocators like jemalloc (used by Redis, FreeBSD, historically Firefox) and tcmalloc (Google, used in Chrome) improve on this with per-thread caches, small pools of free chunks a thread can allocate from without taking a global lock, which matters enormously in multi-threaded programs where a single shared free list would become a serialization bottleneck under concurrent malloc/free calls from many threads at once.

Virtual memory means the addresses malloc() hands back aren’t physical RAM addresses; they’re virtual addresses backed by page table entries the kernel manages lazily. A large mmap()-based allocation may not consume actual physical RAM until the pages are first touched (demand paging), which is why a process’s virtual memory size (VSZ) can be much larger than its resident set size (RSS) in tools like ps or top.

A buddy allocator’s split/merge logic is worth walking through concretely, since it’s also how the Linux kernel itself manages physical page frames. Memory starts as one large block of size 2^k. A request for something smaller than 2^k splits the block in half repeatedly, each half a “buddy” of the other, until reaching the smallest block that still fits the request. Freeing a block checks whether its buddy (found by flipping one address bit, since buddies are always adjacent and aligned) is also free; if so, they merge back into the parent-sized block, and that merge check repeats one level up. This keeps free memory coalesced into usable larger chunks automatically, rather than accumulating unusable, scattered small fragments the way a plain free-list can.

History

• Early allocators (K&R’s original malloc implementation) used a simple linked list of free blocks with a first-fit or best-fit search, adequate for the smaller, less concurrent programs of the era but a poor fit for later multi-threaded, allocation-heavy workloads.
• The buddy allocator, used in early Unix kernels and still in Linux’s physical page allocator today, was designed specifically to make splitting and coalescing memory blocks fast and predictable, at the cost of some internal fragmentation from power-of-two rounding.
• dlmalloc (Doug Lea, early 1990s) introduced the bin-based, size-class-segregated design that glibc’s ptmalloc still descends from, a major step up in general-purpose allocator performance.
• jemalloc (Jason Evans, 2005, originally for FreeBSD) and tcmalloc (Google, mid-2000s) pushed further with per-thread caching specifically to remove global-lock contention in multi-threaded programs, reflecting how much multi-core hardware had shifted the bottleneck by that point.

Debugging Workflow

Diagnosing a suspected leak or fragmentation problem starts with confirming memory is actually growing unboundedly, not just settling into a higher steady state:

$ watch -n 5 'ps -o pid,vsz,rss,cmd -p <pid>'
$ cat /proc/<pid>/status | grep -E "VmRSS|VmSize|VmData"

A steadily climbing RSS across many watch samples, with no corresponding drop after garbage collection (managed languages) or expected frees (manual languages), is the leak signature. To find the actual source:

$ valgrind --leak-check=full --track-origins=yes ./app
==12345== 4,096 bytes in 1 blocks are definitely lost in loss record 1 of 1
==12345==    at 0x4C2FB0F: malloc
==12345==    by 0x1091A2: load_config (app.c:42)

Valgrind’s memcheck reports the exact allocation site of unreachable memory at exit. For a running production process where restarting under Valgrind isn’t practical (its overhead is often 10-50x), heaptrack or periodic pmap -x <pid> snapshots compared over time narrow down which memory region is growing without needing to stop the process.

Why It Matters

• Efficient allocation strategy directly affects application throughput and latency: a poor allocator or access pattern causes fragmentation that degrades performance over a long-running process’s lifetime even without any leak.
• Manual memory management errors are a major source of security vulnerabilities: buffer overflows, use-after-free, and double-free bugs account for a large fraction of memory-safety CVEs in C/C++ software, which is a primary motivation behind memory-safe languages like Rust enforcing allocation lifetime rules at compile time.
• Allocator choice is a real production tuning lever: switching a service from glibc malloc to jemalloc or tcmalloc is a common, low-risk optimization for multi-threaded workloads with heavy allocation churn.

Common Pitfalls

• Use-after-free: freeing memory but continuing to hold and dereference a pointer to it, potentially reading or writing memory now owned by an unrelated allocation.
• Double-free: calling free() twice on the same pointer, which corrupts the allocator’s internal free-list bookkeeping and is a classic path to exploitable memory corruption.
• Buffer overflows: writing past the end of an allocated block, overwriting adjacent heap metadata or neighboring allocations, often the entry point for remote code execution exploits.
• Memory leaks: losing every reference to allocated memory without freeing it. Harmless once, catastrophic in a long-running server process where leaked memory accumulates until the process is killed for exhausting available memory.
• Assuming malloc() always returns quickly. A request that requires the allocator to ask the kernel for more memory (brk/mmap) can trigger page faults and kernel-side work, making allocation latency spiky rather than constant.

Garbage Collection, Briefly

Managed languages (Java, Go, Python, JavaScript, C#) automate heap deallocation instead of requiring an explicit free(). Two dominant strategies:

• Reference counting: each object tracks how many references point to it; when the count hits zero, it’s freed immediately. Simple and predictable, but can’t collect reference cycles on its own (two objects referencing each other, neither externally reachable) without a supplementary cycle collector, and the count updates add overhead to every reference assignment.
• Tracing garbage collection (mark-sweep, generational): periodically walks the object graph from a set of roots (stack variables, globals), marks everything reachable, then reclaims everything unmarked. Generational collectors (used by the JVM, V8) exploit the empirical observation that most objects die young, by collecting a small “young generation” frequently and cheaply, only scanning the larger “old generation” occasionally.

Garbage collection trades manual memory bugs (use-after-free, double-free) for a different cost: collection pauses, moments where the collector runs and can briefly stop application threads, which matters for latency-sensitive systems and is why techniques like concurrent/incremental collection (Go’s collector, Java’s G1/ZGC) exist specifically to shrink those pauses.

Comparison

	Stack	Heap (manual)	Heap (garbage collected)
Speed	Fastest (pointer bump)	Slower (bookkeeping, possible syscall)	Variable (allocation fast, collection pauses)
Lifetime	Scope-bound, automatic	Until explicit free()	Until unreachable
Size limit	Small, fixed per thread	Large, limited by address space/RAM	Large, limited by address space/RAM
Fragmentation risk	None	Yes (internal and external)	Managed by collector (often compacting)
Common bugs	Stack overflow (deep recursion)	Leaks, use-after-free, double-free	Leaks via lingering references
Deallocation trigger	Automatic (function return)	Explicit free() call	Unreachability (collector decides when)
Predictability	Fully deterministic	Deterministic (if used correctly)	Pauses can be non-deterministic

Common Allocation Functions Quick Reference

Function	Language/Context	Behavior
malloc(size)	C	Allocates uninitialized memory
calloc(n, size)	C	Allocates and zero-initializes memory for n elements
realloc(ptr, size)	C	Resizes an existing allocation, possibly moving it
free(ptr)	C	Releases memory back to the allocator
new / delete	C++	Allocates/deallocates and runs constructors/destructors
mmap(NULL, size, ...)	POSIX	Maps pages directly from the kernel, used by allocators for large requests

Example

Manual heap allocation in C:

int *arr = malloc(1024 * sizeof(int));  // request 4KB from the heap
if (arr == NULL) { /* handle allocation failure */ }
arr[0] = 42;
free(arr);                              // release back to the allocator
arr = NULL;                             // avoid a dangling pointer / accidental reuse

Tools like Valgrind’s memcheck or AddressSanitizer (-fsanitize=address) instrument allocations at runtime and catch use-after-free, double-free, and overflow bugs that would otherwise silently corrupt memory. vmstat and /proc/<pid>/status (VmRSS, VmSize) show a running process’s actual memory footprint versus its allocated virtual address space.

FAQ

Does free(ptr) return memory to the operating system immediately? Usually not. free() returns the block to the allocator’s own free lists for reuse by future malloc() calls within the same process; the allocator only occasionally hands large, contiguous freed regions back to the OS via sbrk/munmap, which is why a process’s RSS doesn’t always shrink right after freeing memory.

Why do some languages avoid the heap almost entirely for small values? Stack allocation is dramatically cheaper (no bookkeeping, automatic cleanup on function return), so languages like Rust and C++ favor stack-allocating small, fixed-size, short-lived values whenever the compiler can prove their lifetime fits the enclosing scope.

Is a memory leak in a garbage-collected language impossible? No. GC prevents use-after-free and double-free, but a leak is still possible if code keeps an unnecessary live reference to an object (a growing cache never evicted, an event listener never removed), since the collector correctly considers it reachable and won’t reclaim it.

Related Terms

• Virtual Memory and Paging
• Process and Thread
• File Systems