Memory allocation

Memory allocation reserves computer memory for a program’s data and makes that storage accessible through memory addresses. Allocation determines where data can live and how long the storage remains available; initialization determines the data’s initial value. A language can arrange storage automatically for local variables, retain storage for the duration of a program, or request storage dynamically while the program runs.

In the C programming language, malloc(n) requests a block of $n$ bytes and returns a pointer to it, or a null pointer if allocation fails. Successful allocation does not initialize those bytes. The free operation releases a previously allocated block for subsequent allocation; accessing it through an old pointer is no longer valid.^[ref][ref] Allocation and deallocation are therefore separate from reading and writing an object. Deallocation need not erase its former contents or immediately return its storage to the operating system.

For a process using virtual memory, a contiguous interval of memory addresses does not require a contiguous interval of physical memory. The memory management unit can map successive virtual pages to different physical page frames. Conversely, a successful small allocation may be satisfied from an existing free block without asking the operating system for another page.

Two small bookkeeping examples explain why free capacity alone does not determine whether an allocation succeeds. If an allocator rounds a 17-byte request up to a 32-byte allocation unit, 15 bytes are unused inside that unit: internal fragmentation, before counting any allocator metadata. If two free 32-byte blocks are separated by an occupied block, a request for one contiguous 48-byte block cannot fit in either hole, even though 64 bytes are free. That is external memory fragmentation, under the assumption that the occupied block cannot be moved and no further storage is available. Adjacent free blocks can sometimes be combined; separated ones require a different placement or movement strategy.

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.

A movable memory object is a live allocation that its memory-management system may relocate while preserving its identity and valid references. Moving the stored bytes is only part of the operation: references must be updated, or an indirection mechanism must continue to locate the object. This capability permits memory compaction. Microsoft's primary runtime documentation describes separate marking, reference-relocation and object-compaction phases of garbage collection.^[ref]

For an illustrative16-byte object initially starting at offset24, compaction may place its bytes at offset0. A reference to its beginning then changes from24 to0; a reference five bytes inside it changes from29 to5. In general, moving the base from $a$ to $a^{\prime }$ maps a tracked interior reference $a+k$ to $a^{\prime }+k$. An unrelated integer with value29 must not be rewritten merely because it resembles the old address.

The memory manager therefore needs reliable knowledge of roots and references, including those held in other live objects. A garbage collection root can keep an object reachable while its address changes. If an external consumer requires the address to stay fixed, a pinned memory object imposes a relocation constraint instead. Movability is a property of the reference-management arrangement, not simply of whether the object contains bytes that can be copied.

A raw C programming language pointer returned by an ordinary allocator generally prevents arbitrary hidden movement, because the allocator does not control all copies of that address.^[ref] Physical-page movement under virtual memory is another layer: an operating system may preserve virtual addresses while changing the underlying physical mapping. It need not make the application-level object movable in its own address space.

A pinned memory object is a normally movable memory object whose address must remain unchanged during a specified operation. Pinning permits a pointer to remain usable when the code consuming it cannot participate in the runtime's relocation of references. The pinning lifetime is part of that guarantee: an address retained beyond the protected operation need not remain valid. Microsoft's language reference specifies that a fixed statement prevents relocation during its body and restricts the declared pointer to that statement.^[ref]

For an original layout example, consider96 bytes with a pinned16-byte object at offsets $[32,48)$ and one other16-byte live object. The remaining64 bytes are free. Even if the other object can move anywhere, the pinned object divides the address range into regions of32 and48 bytes. A56-byte contiguous allocation cannot fit. Moving the other object into $[0,16)$ gives free intervals $[16,32)$ and $[48,96)$, whose largest size is48 bytes. If both live objects could move, placing them in $[0,32)$ would instead leave a64-byte interval. Pinning can therefore limit memory compaction despite ample total free capacity.

The numerical layout omits allocation headers and memory alignment; a real allocator must include them. Pinning an object's address also does not by itself specify how its virtual memory pages are backed. The garbage collector's object-relocation guarantee and an operating system's physical-page residency rules concern different layers. Likewise, a pinned buffer in a storage cache may mean protection from eviction rather than this object-relocation guarantee.

Once the protected operation is finished, releasing its pin can restore the runtime's freedom to move the object during a later collection. The program still has to obey the language's reference-lifetime rules: releasing a pin does not convert an old unmanaged address into a relocatable reference. The general garbage collection process must update references when it moves surviving objects.^[ref]

The pinning lifetime is the interval during which a pinned memory object must retain its address for all consumers entitled to use a non-relocatable pointer into it. The interval must cover actual memory access, rather than merely the act of handing out the address. Microsoft's fixed statement guarantees address stability during its body and restricts its declared pointer to that statement; a pointer retained for later work needs a guarantee covering that later work too.^[ref]

For an original timing example, suppose a pin starts at0ms, an external operation receives the address at0.5ms, its submission function returns at1ms, and its final memory access finishes at5ms. Releasing the pin at the function's return leaves4ms of possible access after address stability has ended. Releasing it only after completion at5ms can cover the whole access interval. These times describe an illustrative protocol, not a timing claim about a particular runtime or device.

If the pin is active on $[t_p,t_r)$, every access time $t_a$ must satisfy $t_p\le t_a<t_r$. With several users, the release point must follow the last access by all of them. A count of outstanding operations can enforce this rule: after two operations start, one completion changes the count from2 to1 and does not permit release; the last completion changes1 to0. Asynchronous pin release therefore depends on a completion guarantee. Requesting that unfinished work stop does not by itself demonstrate that its final access has ended.

The pinning lifetime and data synchronization solve different problems. Stable addresses do not prevent two users from changing the same bytes concurrently; a mutex or another synchronization mechanism may still be needed. Nor should a pin be held indefinitely just because longer protection seems convenient: pinning can obstruct memory compaction, as the pinned memory object layout example shows. The useful interval is long enough for the access contract and ends when that contract permits release.

Asynchronous pin release ends the address-stability guarantee for a pinned memory object after an operation that can continue beyond its submission call. Its central condition is that no unfinished consumer may still access the pinned address. Returning from submission is sufficient only when the operation's contract says that all access has ended. Microsoft's asynchronous native-call example stores the pin handle in callback state and disposes it during completion cleanup.^[ref]

For an original event sequence, suppose an operation acquires a pin at0ms, submits at1ms, returns a pending result at2ms and finishes its last access at8ms. Completion cleanup at8ms can end the pinning lifetime; cleanup at2ms cannot. If a request to stop arrives at3ms but the operation acknowledges completion only at6ms, the request alone does not authorize release at3ms. The actual access contract, rather than the desired outcome, determines when the address may change.

An implementation needs a single owner for cleanup across all completion paths. Submission might fail before any callback is promised, complete immediately, or complete later. Each path must transfer or retain the cleanup responsibility consistently. The exactly-once pin cleanup requirement avoids both leaking a pin and releasing the same handle twice. The primary Microsoft example explicitly cleans up an exception before a callback can be invoked, and funnels immediate and deferred completion through a completion routine.^[ref]

With overlapping users, releasing one operation's interest does not establish that every user has finished. A reference counting protocol can track outstanding access leases, provided starting new work and deciding that the last lease ended are synchronized. An observed zero count without protection against a simultaneous new user is not sufficient. A mutex or another appropriate synchronization mechanism can protect that transition.

The completion signal must itself describe the end of access. Microsoft's task-based buffer rule forbids a consumer from continuing to use the memory after the returned task reaches a terminal state.^[ref] An API that reports cancellation before its underlying user has stopped requires another completion guarantee before pin cleanup. Retaining the pin protects the address; it does not by itself prevent concurrent data races or determine who may reuse the buffer.

Exactly-once pin cleanup gives one owner responsibility for ending a particular pinning lifetime, despite several possible completion paths. The resource must remain pinned until its consumers finish, and its cleanup must occur once after that condition is met. This combines the safety requirement of asynchronous pin release with a liveness requirement: a pin left permanently owned by nobody can obstruct later memory compaction.

A useful state machine has states “submission in progress”, “completion pending” and “released”. A submission error that guarantees no future consumer can access the address may take the first state directly to released. A pending result transfers cleanup responsibility to a completion path. Immediate completion must follow the API's stated rule about whether a callback will also arrive; it must not independently trigger two owners to dispose of the same handle. Microsoft's native-call example explicitly handles submission exceptions and funnels immediate or deferred completion into cleanup.^[ref]

For an original race example, suppose a completion callback and an error-reporting path can both observe an operation as finished. A plain sequence “test flag; if clear, set flag; release pin” can race: both callers read clear before either writes set, and both release. A synchronized ownership claim, using a mutex or an appropriate compare-and-swap transition, can ensure that only one caller changes pending to released. The losing caller performs no cleanup. This is a schematic ownership protocol, not a claim that every pin API tolerates arbitrary racing callbacks.

For a count $r$ of releases on one acquired handle, the at-most-once condition is $r\le 1$. The requirement that cleanup eventually occurs after all promised access has ended supplies $r\ge 1$ at final completion, so together they give $r=1$. A one-time flag alone establishes neither the end of access nor eventual execution of the winning path.

The operation's state must also stay alive while any callback can inspect it. Reference counting can protect that state independently of the pin being released. Marking a handle released does not permit another caller to access freed callback state. Keeping resource ownership, callback-state lifetime and data synchronization separate makes the protocol easier to verify. The primary task-based memory rule similarly requires all consumer access to finish by task termination.^[ref]

Memory block coalescing merges adjacent free allocation blocks into a larger free block. It improves the allocator's representation and use of free space without moving intervening live objects. The mechanism is useful after deallocation, when a returned block may adjoin free neighbors. A free list records the resulting regions; it can be implemented using a list or another search structure.^[ref]

Using half-open address intervals, two free blocks $[a,b)$ and $[b,c)$ can become $[a,c)$. Their usable bookkeeping lengths add: $(b-a)+(c-b)=c-a$. For an original example, suppose free intervals occupy offsets $[0,24)$ and $[40,80)$ while the intervening16-byte block is live. Releasing that middle block makes all of $[0,80)$ free, so merging its two neighbors produces an80-byte block. An occupied8-byte block after offset80 still separates this region from a later free interval.

An address-aware insertion can check the predecessor's end against the new block's start and the successor's start against its end. When both are adjacent, all three join. An implementation may delay merging, but a search that examines only unmerged entries can miss a sufficiently large contiguous region. Coalescing policy and allocation search therefore affect observed success as well as the physical occupancy pattern.

These examples omit block headers and other allocator metadata. A real merge must maintain those structures, preserve memory alignment guarantees and avoid treating an occupied or separately managed region as free. Coalescing does not cure a hole separated from its neighbor by a still-live allocation; that requires deallocation, a different placement strategy or a valid memory compaction mechanism.

A free list records free memory regions or reusable allocation units so an allocator can find storage for a request. In a variable-size pool, a record typically needs a block's location and length. A linked implementation also stores a link to another free record; these records can occupy the free blocks themselves. The term can also describe the allocator's logical inventory when its search structure is more elaborate than one linked chain.^[ref]

For an illustrative inventory of free extents of16,32 and48 bytes, a24-byte request cannot use the first extent but can use either later one, before metadata and alignment are counted. Choosing the32-byte extent leaves an8-byte remainder if split exactly. Whether that remainder can become a free-list entry depends on the minimum free-block size.

Suppose an explicitly hypothetical in-block free record needs an8-byte length field and an8-byte next-link field. Its16-byte metadata cannot fit in that8-byte remainder. The allocator can instead give the request the entire32-byte block, leaving8 bytes of internal fragmentation, or choose another layout or block. Metadata placement is therefore part of allocation capacity, rather than an afterthought.

When a block is returned, memory block coalescing can combine it with adjacent free neighbors and update the inventory. Address order can make adjacency checks convenient; other orderings can favor allocation searches. A list that contains enough total free bytes may still lack one sufficiently large extent, producing external memory fragmentation. The search policy, split rule, metadata layout and coalescing policy jointly determine which requests succeed.

The minimum free-block size is the smallest extent that an allocator's representation can retain as an independent free record. It depends on where the allocator stores a region's size, links and other metadata, as well as memory alignment. A region may contain unused bytes yet be too short to enter the free list. OSTEP demonstrates why allocator metadata must be counted: free records can be embedded inside the free regions themselves.^[ref]

For a hypothetical allocator, let a free record need an8-byte size field and two8-byte links. Its raw metadata requires24 bytes. If all block lengths are multiples of16 bytes, its minimum independently representable size isThe exact fields and sizes are illustrative. An allocator with separate metadata, a singly linked record or another block granularity can have another minimum.

Suppose the same allocator uses an8-byte allocated-block header. An8-byte payload plus that header would occupy16 bytes before enforcing the minimum. Reserving32 bytes ensures that this block can later become an independent free record. Extra allocation space of this kind contributes to internal fragmentation. The allocator might instead use a distinct representation for tiny blocks, so the formula is a design constraint for the stated representation rather than a universal allocation rule.

A proposed split also needs to respect the minimum. Taking80 bytes from a96-byte extent leaves16 bytes, an unsplittable free-block remainder under this layout. Giving the caller the full96-byte extent avoids making an invalid free record but consumes extra storage. Taking32 bytes would leave64, which can be retained. Memory block coalescing can later join adjacent returned extents, but the allocator must have a valid way to represent each extent until that happens.

An unsplittable free-block remainder is the positive suffix left by a proposed allocation that is too small to retain as a valid independent free list record. Its size is below the allocator's minimum free-block size. The region still contains unused bytes, but the chosen representation cannot manage it as a separate free extent. The issue arises because free-region metadata can occupy the regions themselves.^[ref]

Let a chosen block have size $B$, let the proposed allocated extent after header/alignment rounding be $N\le B$, and let the minimum free size be $M$. With remainder $r=B-N$, an allocator that absorbs an undersized suffix usesThis is one possible policy, not a mandatory allocator interface. The absorbed suffix adds $r$ bytes of internal fragmentation beyond the bookkeeping and rounding already included in $N$.

For an original example, take $B=96$ bytes, an8-byte allocated header,16-byte block granularity and $M=32$ bytes. A56-byte payload gives $N=16\lceil (56+8)/16\rceil =64$, leaving a representable32-byte free block. A57-byte payload instead gives $N=80$, leaving an unusable16-byte suffix. Absorbing it reserves all96 bytes. Increasing the request by just one byte has therefore increased this allocation's occupied extent by32 bytes.

If $M$ and all extents are multiples of a granularity $q$, a positive absorbed suffix is at most $M-q$ bytes. Without that granularity condition, the general integer-byte bound is $M-1$. Choosing another free block or another representation can change the tradeoff. Later memory block coalescing can recover adjacent space when allocations are returned, but it does not make an invalid intermediate free record representable.

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.

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.

Allocation alignment padding is the unused space inserted before an allocated payload so its address meets memory alignment. If a free extent starts at integer byte address $a$, an allocation header consumes $h$ bytes, and payload addresses must be multiples of positive integer $A$, the earliest permitted address and its padding areEquivalently, $P$ is the least nonnegative residue of $-(a+h)$ modulo $A$. The alignment padding bound is $0\le P\le A-1$. Already aligned payload starts have zero padding; adding a whole extra alignment unit in that case would waste space unnecessarily.

For an original example, let a free extent be $[3,67)$, with $h=8$ and $A=16$. Then $a+h=11$, $p=16$ and $P=5$ bytes. A24-byte payload ends at40, so the used prefix occupies37 bytes:8 for the header,5 for padding and24 for data. The remaining interval $[40,67)$ has27 bytes before other block-rounding or minimum free-block size requirements are applied. This accounting distinguishes padding from header storage and from payload-size rounding.

The same header and alignment can produce different padding at another address: $a=8$ gives $a+h=16$ and $P=0$. If the residues of $a+h$ were uniformly distributed over all16 possibilities, the mean padding would be7.5 bytes, obtained by averaging0 through15. An actual allocator can constrain its block starts, so that distribution is an explicit model assumption rather than a measured universal overhead.

Aligned free-block capacity must deduct this padding when testing whether a request fits. Allocation alignment padding can thus make two equally long free extents offer different usable capacities. OSTEP's separation of the allocated payload from its bookkeeping header is the basic layout issue behind this calculation; alignment adds the stated address constraint.^[ref]

The alignment padding bound limits the extra bytes needed to move an integer payload address to the next permitted memory alignment. Let $x=a+h$ be the first address after an allocated header, and let alignment require a multiple of a positive integer $A$. Withthe exact bound is $0\le P\le A-1$. It applies to the earliest aligned start, not to arbitrary extra space an allocator may choose to reserve.

To prove the bound, write $k=\lceil x/A\rceil$. The ceiling function gives $k-1<x/A\le k$, hence $0\le Ak-x<A$. Since $P=Ak-x$ is an integer number of bytes, $P\le A-1$. The endpoints can occur: an already aligned $x$ gives zero padding, while $x$ one byte beyond an aligned address gives $A-1$. This is also the statement that $P$ is the least nonnegative residue of $-x$ in modular arithmetic.

For an original example, $A=16$, header size $h=8$ and block start $a=9$ give $x=17$, $p=32$ and $P=15$. The worst-case bound is attained. Starting at $a=8$ instead gives $x=16$ and $P=0$. Identical header and payload sizes can therefore incur different allocation alignment padding at different addresses.

A sufficient address-independent reservation for a payload of $R$ bytes is $h+(A-1)+R$, before any trailer, block rounding or minimum free-block size constraint. For $h=8$, $A=16$ and $R=24$,47 bytes suffice under precisely that layout. A known starting address can require less: $a=3$ needs5 bytes of padding and a37-byte used prefix. Separating the payload from its metadata is the bookkeeping principle illustrated in OSTEP; the bound adds a worst-case alignment allowance.^[ref]

These inequalities concern mathematical integers. An implementation using bounded address arithmetic must separately prevent integer overflow when adding the header, padding allowance or payload. A wrapped sum cannot be justified by a correct bound over unbounded integers.