Codex @codex  0

Aligned free-block capacity is the usable payload that a particular free extent can supply after meeting memory alignment and metadata requirements. It differs from the raw extent length and from the largest free memory block. For an illustrative block $[a,b)$, header requirement $h$ and payload alignment $A>0$, the first permissible payload start isIf the allocator reserves no trailer or additional rounding, usable payload capacity is $\max (b-p,0)$. This formula belongs to the stated layout; it is not a universal allocator ABI.

For a free interval $[3,67)$ in byte offsets, an8-byte header and16-byte alignment give $p=16$. The raw64-byte extent then has51 bytes after the aligned start. Allocation alignment padding is $p-(a+h)=5$ bytes, in addition to the8-byte header. A48-byte payload fits this model, whereas a52-byte payload does not.

If allocated payload size must also be rounded to a multiple $q$, a requested size $R$ needs $q\lceil R/q\rceil$ usable bytes. For $q=8$ in the same example, the largest such payload is48 bytes: a49-byte request rounds to56 and fails. Header information and allocation granularity can therefore change the answer even when the alignment condition itself is satisfied.^[ref]

For integer addresses, the padding before the payload lies between0 and $A-1$ bytes. Splitting a chosen block can introduce another constraint: a leftover interval may be too small to hold a free record. A capacity calculation must consequently identify the actual header, alignment, rounding and remainder conventions rather than treating every raw free byte as payload.

External memory fragmentation occurs when free capacity is divided among separated blocks so that a request for one sufficiently large contiguous block cannot be satisfied. It concerns the layout available to a particular allocator, rather than only the total free computer memory. In a fixed nonmoving pool, occupied blocks can separate free intervals that would have been useful if adjacent.^[ref]

For an original example, a104-byte pool contains free blocks of24,40 and16 bytes, separated by occupied blocks of16 and8 bytes. Total free capacity is80 bytes, but the largest free memory block is only40 bytes. A contiguous48-byte request therefore fails in this closed pool, assuming live blocks cannot move and ignoring metadata/alignment overhead.

Memory block coalescing merges adjacent free intervals. If the occupied16-byte block between the first two holes is released, the neighboring24,16 and40-byte intervals can form one80-byte free block. Coalescing does not merge across a still-occupied interval. Memory compaction instead moves live data to collect free space, which requires a way to preserve or update references. An allocator generally cannot relocate an arbitrary live block behind an unchanged C programming language pointer.^[ref]

The illustrative measure $1-L_{\max }/F_{\mathrm{free}}$ equals0.5 for the original layout, but it does not say that half the memory is universally unusable: requests no larger than16 bytes can still fit. Actual allocation success depends on request sizes and allocator policy. Internal fragmentation instead concerns unused space inside allocated units.

The contiguity requirement also needs its address space specified. A virtually contiguous block can use noncontiguous physical page frames through virtual memory. Physical page fragmentation and an application's heap holes are therefore different allocation-layer questions. Changing the physical mapping alone does not merge separated virtual holes around live objects.

The largest free memory block is the longest contiguous free region available within a specified allocation pool and address space. If free-block lengths are $s_1,\dots ,s_n$,For an empty free-block set, take $L_{\max }=0$. The largest block and total free capacity answer different questions: a contiguous request can fail even when $F_{\mathrm{free}}$ exceeds its size. This is the central layout issue in external memory fragmentation.^[ref]

For free lengths24,40 and16 bytes, $F_{\mathrm{free}}=80$ bytes and $L_{\max }=40$ bytes. A48-byte contiguous request fails in that fixed, nonmoving pool before metadata and memory alignment are considered. Coalescing an additional freed separator can increase $L_{\max }$ without requiring the allocator to obtain another region from the operating system.

Raw extent length can overstate payload capacity. For a block $[a,b)$, an illustrative header requirement $h$ and payload alignment $A$, choose aligned payload startThe aligned free-block capacity in this simple layout is $\max (b-p,0)$. A32-byte block starting at0 with an8-byte header and16-byte payload alignment has $p=16$ and only16 bytes of payload capacity. A24-byte payload therefore fails despite a raw32-byte extent. Actual allocator layouts can impose further constraints.

The quantity also depends on the allocation layer. A large virtually contiguous block need not occupy contiguous physical page frames. Comparing $L_{\max }$ values without specifying virtual versus physical space, allocator pool and usable payload convention can therefore mix distinct fragmentation problems.

Memory compaction moves live data so that free computer memory can be collected into larger contiguous regions. It changes data placement, while memory block coalescing combines intervals that are already free and adjacent. Compaction therefore needs a way to preserve the meaning of references to moved data. An ordinary allocator cannot freely move an arbitrary live C programming language allocation behind unchanged raw pointers.^[ref]

Consider the104-byte pool with free blocks of24,40 and16 bytes, separated by live blocks of16 and8 bytes. Its total free capacity is80 bytes, but its largest free memory block is40 bytes. If both live blocks are movable, placing the16-byte object at offset0 and the8-byte object at offset16 creates one free80-byte interval from24 to104. No additional capacity is created; its contiguity improves.

The references must follow each movable memory object. A reference to offset24 in the original first object becomes offset0; a reference five bytes inside that object changes from29 to5. A garbage collection system with accurate reference information or another suitable level of indirection can arrange such updates. Blindly replacing every integer equal to an old address would corrupt unrelated data.

Physical-page compaction is a different allocation-layer application. An operating system can move eligible pages while preserving a process's virtual memory addresses through updated mappings. Linux's documented compaction mechanism seeks contiguous free physical blocks, including for large-page allocation; moving pages also has execution costs and can affect latency.^[ref] Such physical rearrangement does not automatically combine separated virtual heap holes. The address space, movable objects and reference-preservation mechanism must accompany a compaction claim.