Free-block Coalescing¶
An allocator operation that combines adjacent eligible free memory blocks into one larger free extent under a declared merge rule.
Core Idea¶
Free-block coalescing is an allocator operation that combines adjacent eligible free memory blocks into one larger free block. It changes the partition of available space: the covered addresses stay free, but the boundary between the blocks disappears. That larger extent may help a later request, though no particular allocation is guaranteed to succeed. GNU’s heap allocator and the Linux buddy page allocator illustrate unlike ways to perform the operation.[ref-64b4ff5ec6a4][ref-e0670a1416f8]
An eligible neighbor must be free and satisfy the allocator’s merge rule. A newly freed block may have no such neighbor, and a general-purpose allocator may defer a merge. Immediate coalescing on every free is not the definition.[ref-05a5cc5f7f20][ref-e0670a1416f8]
Scope of Application¶
For variable-size heap chunks, GNU’s manual says neighboring free chunks can coalesce when a chunk is freed, regardless of their sizes. Doug Lea describes boundary tags as a way to locate neighbors and contrasts immediate with deferred coalescing. Delaying a merge can preserve same-size chunks for reuse; its value depends on workload.[ref-64b4ff5ec6a4][ref-05a5cc5f7f20]
For physical pages, Mel Gorman’s historical Linux buddy-allocator account uses power-of-two block orders. A freed block can merge with its unique free buddy of the same order; the already-free buddy is removed from its free list, and the pair forms a higher-order block. The test can repeat recursively. Physical adjacency without the buddy rule is insufficient. This source documents the described implementation, not every present kernel version.[^ref-e0670a1416f8]
Clarity¶
Describe the free pool, candidate block, eligible neighbor, merge rule, resulting extent and timing. Comparing a local before/after free-space map shows the key invariant: the same addresses are free, while their partition becomes coarser. “Less fragmentation” is a possible consequence, not a substitute for specifying the operation.[ref-05a5cc5f7f20][ref-e0670a1416f8]
Manages Complexity¶
Allocators face requests of changing sizes. Many separately tracked free blocks can leave a large contiguous region unavailable as a single allocatable block. Coalescing can expose a larger extent when free neighbors qualify. It does not move live objects, join discontiguous regions, or guarantee that the entire pool can satisfy every request.[ref-64b4ff5ec6a4][ref-e0670a1416f8]
Immediate merging prepares larger blocks sooner but takes work. Doug Lea’s deferred policy discussion shows why reusing unmerged exact-size blocks can sometimes avoid a merge followed by a split. The right timing depends on the allocation pattern and policy, not on the word coalescing.[^ref-05a5cc5f7f20]
Abstract Reasoning¶
Represent available addresses as a partition into tracked free extents. Check whether a neighboring extent is free and merge-eligible. If so, replace the pair by its union under the allocator’s rule; in a buddy system, test the next order again. If the neighbor is allocated or an invalid buddy, that merge cannot occur. If no larger extent results, the event may be detection or bookkeeping rather than coalescing.[ref-05a5cc5f7f20][ref-e0670a1416f8]
Knowledge Transfer¶
The roles travel from heap chunks to buddy pages: free state → eligible neighbor → merge → larger free extent. Boundary tags and variable chunk sizes belong to the heap example; equal-order buddies and recursive order promotion belong to the page example. The reviewed graph records strict subsumption to the live Transformation Prime: a rule maps a free-space partition into a coarser one while preserving the covered free-address set. The allocator-specific extent relation is the child’s distinct content.
Example¶
Heap chunks. Two compatible neighboring free chunks are combined into a larger free chunk. Doug Lea describes neighbor discovery and immediate or deferred timing; GNU describes chunks that can coalesce on free. Pool → heap; candidate → freed chunk; eligibility → neighboring free chunk under allocator metadata; merge → one larger free chunk; outcome → possible capacity for a later larger request.[ref-05a5cc5f7f20][ref-64b4ff5ec6a4]
Buddy page blocks. Gorman’s account checks whether the unique same-order buddy of a freed page block is free. It removes that already-free buddy from its list and forms one higher-order block, repeating if another eligible buddy exists. Pool → page free areas; candidate → order-k block; eligibility → matching free order-k buddy; merge → order-(k+1) block; outcome → larger contiguous page extent.[^ref-e0670a1416f8]
Relationships to Other Abstractions¶
Current abstraction Free-block Coalescing Domain-specific
Parents (1) — more general patterns this builds on
-
Free-block Coalescing is a kind of Transformation Prime
Eligible adjacent free extents are rulefully restructured into one larger extent while preserving the free-address set.
Hierarchy path (1) — routes to 1 parentless root
- Free-block Coalescing → Transformation → Function (Mapping)
Neighborhood in Abstraction Space¶
Free-block Coalescing sits in a sparse region of the domain-specific corpus (100th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Memory Management — 0.76
- Stochastic Tunneling — 0.74
- In-Place Adjacent-Block Rotation — 0.74
- Sphere packing — 0.73
- Classless Inter-Domain Routing — 0.73
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
GPU memory-access coalescing: combines accesses into transactions, not free extents. Null coalescing: chooses a fallback value. Compaction: may relocate live objects. Deallocation alone: a block can become free without an eligible neighbor. Generic Merge Algorithm: the live entry merges sorted sequences, not allocator blocks. A guaranteed successful large request: the new extent helps only under the later request and allocator state.[ref-05a5cc5f7f20][ref-e0670a1416f8]
References¶
[^ref-05a5cc5f7f20]: Doug Lea, “A Memory Allocator”, author essay, university mirror; “Algorithms” (especially “Boundary Tags”) and “Caching,” for neighbor coalescing, immediate/deferred policy and reuse of same-size chunks. Historical design account, not a benchmark of every modern allocator.
[^ref-64b4ff5ec6a4]: GNU Project, “The GNU C Library Reference Manual, version 2.42: The GNU Allocator”, §3.2.2. First-party description of arenas and neighboring chunks that can coalesce on free regardless of size.
[^ref-e0670a1416f8]: Mel Gorman, Understanding the Linux Virtual Memory Manager, “Physical Page Allocation”, §6.3 “Free Pages.” Author text hosted by kernel.org; historical Linux buddy implementation with same-order free-buddy test and recursive merge, not a claim about every current kernel version.