source: doc/theses/mubeen_zulfiqar_MMath/background.tex @ 1803d4d

\begin{comment}
====================
Writing Points:
\begin{itemize}
\item
Classification of benchmarks.
\item
Literature review of current benchmarks.
\item
Features and limitations.
\item
Literature review of current memory allocators.
\item
Breakdown of memory allocation techniques.
\item
Features and limitations.
\end{itemize}
\end{comment}

\chapter[Background]{Background\footnote{Part of this chapter draws from similar background work in~\cite{Wasik08} with many updates.}}


A program dynamically allocates and deallocates the storage for a variable, referred to as an \newterm{object}, through calls such as @malloc@ and @free@ in C, and @new@ and @delete@ in \CC.
Space for each allocated object comes from the dynamic-allocation zone.
A \newterm{memory allocator} contains a complex data-structure and code that manages the layout of objects in the dynamic-allocation zone.
The management goals are to make allocation/deallocation operations as fast as possible while densely packing objects to make efficient use of memory.
Objects in C/\CC cannot be moved to aid the packing process, only adjacent free storage can be \newterm{coalesced} into larger free areas.
The allocator grows or shrinks the dynamic-allocation zone to obtain storage for objects and reduce memory usage via operating-system calls, such as @mmap@ or @sbrk@ in UNIX.


\section{Allocator Components}
\label{s:AllocatorComponents}

\VRef[Figure]{f:AllocatorComponents} shows the two important data components for a memory allocator, management and storage, collectively called the \newterm{heap}.
The \newterm{management data} is a data structure located at a known memory address and contains all information necessary to manage the storage data.
The management data starts with fixed-sized information in the static-data memory that references components in the dynamic-allocation memory.
The \newterm{storage data} is composed of allocated and freed objects, and \newterm{reserved memory}.
Allocated objects (light grey) are variable sized, and are allocated and maintained by the program;
\ie only the memory allocator knows the location of allocated storage, not the program.
\begin{figure}[h]
\centering
\input{AllocatorComponents}
\caption{Allocator Components (Heap)}
\label{f:AllocatorComponents}
\end{figure}
Freed objects (white) represent memory deallocated by the program, which are linked into one or more lists facilitating easy location of new allocations.
Often the free list is chained internally so it does not consume additional storage, \ie the link fields are placed at known locations in the unused memory blocks.
Reserved memory (dark grey) is one or more blocks of memory obtained from the operating system but not yet allocated to the program;
if there are multiple reserved blocks, they are also chained together, usually internally.

In some allocator designs, allocated and freed objects have additional management data embedded within them.
\VRef[Figure]{f:AllocatedObject} shows an allocated object with a header, trailer, and alignment padding and spacing around the object.
The header contains information about the object, \eg size, type, etc.
The trailer may be used to simplify an allocation implementation, \eg coalescing, and/or for security purposes to mark the end of an object.
An object may be preceded by padding to ensure proper alignment.
Some algorithms quantize allocation requests into distinct sizes, called \newterm{buckets}, resulting in additional spacing after objects less than the quantized value.
(Note, the buckets are often organized as an array of ascending bucket sizes for fast searching, \eg binary search, and the array is stored in the heap management-area, where each bucket is a top point to the freed objects of that size.)
When padding and spacing are necessary, neither can be used to satisfy a future allocation request while the current allocation exists.
A free object also contains management data, \eg size, chaining, etc.
The amount of management data for a free node defines the minimum allocation size, \eg if 16 bytes are needed for a free-list node, any allocation request less than 16 bytes must be rounded up, otherwise the free list cannot use internal chaining.
The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new management information and possibly data.

\begin{figure}
\centering
\input{AllocatedObject}
\caption{Allocated Object}
\label{f:AllocatedObject}
\end{figure}


\section{Single-Threaded Memory-Allocator}
\label{s:SingleThreadedMemoryAllocator}

A single-threaded memory-allocator does not run any threads itself, but is used by a single-threaded program.
Because the memory allocator is only executed by a single thread, concurrency issues do not exist.
The primary issues in designing a single-threaded memory-allocator are fragmentation and locality.


\subsection{Fragmentation}
\label{s:Fragmentation}

Fragmentation is memory requested from the operating system but not used by the program;
hence, allocated objects are not fragmentation.
\VRef[Figure]{f:InternalExternalFragmentation} shows fragmentation is divided into two forms: internal or external.

\begin{figure}
\centering
\input{IntExtFragmentation}
\caption{Internal and External Fragmentation}
\label{f:InternalExternalFragmentation}
\end{figure}

\newterm{Internal fragmentation} is memory space that is allocated to the program, but is not intended to be accessed by the program, such as headers, trailers, padding, and spacing around an allocated object.
This memory is typically used by the allocator for management purposes or required by the architecture for correctness, \eg alignment.
Internal fragmentation is problematic when management space is a significant proportion of an allocated object.
For example, if internal fragmentation is as large as the object being managed, then the memory usage for that object is doubled.
An allocator should strive to keep internal management information to a minimum.

\newterm{External fragmentation} is all memory space reserved from the operating system but not allocated to the program~\cite{Wilson95,Lim98,Siebert00}, which includes all external management data, freed objects, and reserved memory.
This memory is problematic in two ways: heap blowup and highly fragmented memory.
\newterm{Heap blowup} occurs when memory freed by the program is not reused for future allocations leading to potentially unbounded external fragmentation growth~\cite{Berger00}.
Heap blowup can occur due to allocator policies that are too restrictive in reusing freed memory and/or no coalescing of free storage.
Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects.
\VRef[Figure]{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time.
Blocks of free memory become smaller and non-contiguous making them less useful in serving allocation requests.
Memory is highly fragmented when most free blocks are unusable because of their sizes.
For example, \VRef[Figure]{f:Contiguous} and \VRef[Figure]{f:HighlyFragmented} have the same quantity of external fragmentation, but \VRef[Figure]{f:HighlyFragmented} is highly fragmented.
If there is a request to allocate a large object, \VRef[Figure]{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while \VRef[Figure]{f:HighlyFragmented} likely has to request more memory from the operating system.

\begin{figure}
\centering
\input{MemoryFragmentation}
\caption{Memory Fragmentation}
\label{f:MemoryFragmentation}
\vspace{10pt}
\subfigure[Contiguous]{
        \input{ContigFragmentation}
        \label{f:Contiguous}
} % subfigure
        \subfigure[Highly Fragmented]{
        \input{NonContigFragmentation}
\label{f:HighlyFragmented}
} % subfigure
\caption{Fragmentation Quality}
\label{f:FragmentationQuality}
\end{figure}

For a single-threaded memory allocator, three basic approaches for controlling fragmentation are identified~\cite{Johnstone99}.
The first approach is a \newterm{sequential-fit algorithm} with one list of free objects that is searched for a block large enough to fit a requested object size.
Different search policies determine the free object selected, \eg the first free object large enough or closest to the requested size.
Any storage larger than the request can become spacing after the object or be split into a smaller free object.
The cost of the search depends on the shape and quality of the free list, \eg a linear versus a binary-tree free-list, a sorted versus unsorted free-list.

The second approach is a \newterm{segregated} or \newterm{binning algorithm} with a set of lists for different sized freed objects.
When an object is allocated, the requested size is rounded up to the nearest bin-size, often leading to spacing after the object.
A binning algorithm is fast at finding free memory of the appropriate size and allocating it, since the first free object on the free list is used.
The fewer bin-sizes, the fewer lists need to be searched and maintained;
however, the bin sizes are less likely to closely fit the requested object size, leading to more internal fragmentation.
The more bin sizes, the longer the search and the less likely free objects are to be reused, leading to more external fragmentation and potentially heap blowup.
A variation of the binning algorithm allows objects to be allocated to the requested size, but when an object is freed, it is placed on the free list of the next smallest or equal bin-size.
For example, with bin sizes of 8 and 16 bytes, a request for 12 bytes allocates only 12 bytes, but when the object is freed, it is placed on the 8-byte bin-list.
For subsequent requests, the bin free-lists contain objects of different sizes, ranging from one bin-size to the next (8-16 in this example), and a sequential-fit algorithm may be used to find an object large enough for the requested size on the associated bin list.

The third approach is \newterm{splitting} and \newterm{coalescing algorithms}.
When an object is allocated, if there are no free objects of the requested size, a larger free object may be split into two smaller objects to satisfy the allocation request without obtaining more memory from the operating system.
For example, in the buddy system, a block of free memory is split into two equal chunks, one of those chunks is again split into two equal chunks, and so on until a block just large enough to fit the requested object is created.
When an object is deallocated it is coalesced with the objects immediately before and after it in memory, if they are free, turning them into one larger object.
Coalescing can be done eagerly at each deallocation or lazily when an allocation cannot be fulfilled.
In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays during coalescing.
While coalescing does not reduce external fragmentation, the coalesced blocks improve fragmentation quality so future allocations are less likely to cause heap blowup.
Splitting and coalescing can be used with other algorithms to avoid highly fragmented memory.


\subsection{Locality}
\label{s:Locality}

The principle of locality recognizes that programs tend to reference a small set of data, called a working set, for a certain period of time, where a working set is composed of temporal and spatial accesses~\cite{Denning05}.
Temporal clustering implies a group of objects are accessed repeatedly within a short time period, while spatial clustering implies a group of objects physically close together (nearby addresses) are accessed repeatedly within a short time period.
Temporal locality commonly occurs during an iterative computation with a fixed set of disjoint variables, while spatial locality commonly occurs when traversing an array.

Hardware takes advantage of temporal and spatial locality through multiple levels of caching, \ie memory hierarchy.
When an object is accessed, the memory physically located around the object is also cached with the expectation that the current and nearby objects will be referenced within a short period of time.
For example, entire cache lines are transferred between memory and cache and entire virtual-memory pages are transferred between disk and memory.
A program exhibiting good locality has better performance due to fewer cache misses and page faults\footnote{With the advent of large RAM memory, paging is becoming less of an issue in modern programming.}.

Temporal locality is largely controlled by how a program accesses its variables~\cite{Feng05}.
Nevertheless, a memory allocator can have some indirect influence on temporal locality and largely dictates spatial locality.
For temporal locality, an allocator can return storage for new allocations that was just freed as these memory locations are still \emph{warm} in the memory hierarchy.
For spatial locality, an allocator can place objects used together close together in memory, so the working set of the program fits into the fewest possible cache lines and pages.
However, usage patterns are different for every program as is the underlying hardware memory architecture;
hence, no general-purpose memory-allocator can provide ideal locality for every program on every computer.

There are a number of ways a memory allocator can degrade locality by increasing the working set.
For example, a memory allocator may access multiple free objects before finding one to satisfy an allocation request, \eg sequential-fit algorithm.
If there are a (large) number of objects accessed in very different areas of memory, the allocator may perturb the program's memory hierarchy causing multiple cache or page misses~\cite{Grunwald93}.
Another way locality can be degraded is by spatially separating related data.
For example, in a binning allocator, objects of different sizes are allocated from different bins that may be located in different pages of memory.


\section{Multi-Threaded Memory-Allocator}
\label{s:MultiThreadedMemoryAllocator}

A multi-threaded memory-allocator does not run any threads itself, but is used by a multi-threaded program.
In addition to single-threaded design issues of fragmentation and locality, a multi-threaded allocator is simultaneously accessed by multiple threads, and hence, must deal with concurrency issues such as mutual exclusion, false sharing, and additional forms of heap blowup.


\subsection{Mutual Exclusion}
\label{s:MutualExclusion}

\newterm{Mutual exclusion} provides sequential access to the shared management data of the heap.
There are two performance issues for mutual exclusion.
First is the overhead necessary to perform (at least) a hardware atomic operation every time a shared resource is accessed.
Second is when multiple threads contend for a shared resource simultaneously, and hence, some threads must wait until the resource is released.
Contention can be reduced in a number of ways:
\begin{itemize}[itemsep=0pt]
\item
using multiple fine-grained locks versus a single lock, spreading the contention across a number of locks;
\item
using trylock and generating new storage if the lock is busy, yielding a classic space versus time tradeoff;
\item
using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Oyama99}.
\end{itemize}
However, all of these approaches have degenerate cases where program contention is high, which occurs outside of the allocator.


\subsection{False Sharing}
\label{s:FalseSharing}

False sharing is a dynamic phenomenon leading to cache thrashing.
When two or more threads on separate CPUs simultaneously change different objects sharing a cache line, the change invalidates the other thread's associated cache, even though these threads may be uninterested in the other modified object.
False sharing can occur in three different ways: program induced, allocator-induced active, and allocator-induced passive;
a memory allocator can only affect the latter two.

\paragraph{\newterm{Program-induced false-sharing}}
occurs when one thread passes an object sharing a cache line to another thread, and both threads modify the respective objects.
\VRef[Figure]{f:ProgramInducedFalseSharing} shows when Thread$_1$ passes Object$_2$ to Thread$_2$, a false-sharing situation forms when Thread$_1$ modifies Object$_1$ and Thread$_2$ modifies Object$_2$.
Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.

\begin{figure}
\centering
\subfigure[Program-Induced False-Sharing]{
        \input{ProgramFalseSharing}
        \label{f:ProgramInducedFalseSharing}
} \\
\vspace{5pt}
\subfigure[Allocator-Induced Active False-Sharing]{
        \input{AllocInducedActiveFalseSharing}
        \label{f:AllocatorInducedActiveFalseSharing}
} \\
\vspace{5pt}
\subfigure[Allocator-Induced Passive False-Sharing]{
        \input{AllocInducedPassiveFalseSharing}
        \label{f:AllocatorInducedPassiveFalseSharing}
} % subfigure
\caption{False Sharing}
\label{f:FalseSharing}
\end{figure}

\paragraph{\newterm{Allocator-induced active false-sharing}}
\label{s:AllocatorInducedActiveFalseSharing}
occurs when objects are allocated within the same cache line but to different threads.
For example, in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}, each thread allocates an object and loads a cache-line of memory into its associated cache.
Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.

\paragraph{\newterm{Allocator-induced passive false-sharing}}
\label{s:AllocatorInducedPassiveFalseSharing}
is another form of allocator-induced false-sharing caused by program-induced false-sharing.
When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing.
For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Thread$_1$ passes Object$_2$ to Thread$_2$, and Thread$_2$ subsequently deallocates Object$_2$.
Allocator-induced passive false-sharing occurs when Object$_2$ is reallocated to Thread$_2$ while Thread$_1$ is still using Object$_1$.


\subsection{Heap Blowup}
\label{s:HeapBlowup}

In a multi-threaded program, heap blowup can occur when memory freed by one thread is inaccessible to other threads due to the allocation strategy.
Specific examples are presented in later sections.


\section{Multi-Threaded Memory-Allocator Features}
\label{s:MultiThreadedMemoryAllocatorFeatures}

The following features are used in the construction of multi-threaded memory-allocators:
\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
\item multiple heaps
\begin{list}{\alph{enumii})}{\usecounter{enumii}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
\item with or without a global heap
\item with or without ownership
\end{list}
\item object containers
\begin{list}{\alph{enumii})}{\usecounter{enumii}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
\item with or without ownership
\item fixed or variable sized
\item global or local free-lists
\end{list}
\item hybrid private/public heap
\item allocation buffer
\item lock-free operations
\end{list}
The first feature, multiple heaps, pertains to different kinds of heaps.
The second feature, object containers, pertains to the organization of objects within the storage area.
The remaining features apply to different parts of the allocator design or implementation.


\section{Multiple Heaps}
\label{s:MultipleHeaps}

A multi-threaded allocator has potentially multiple threads and heaps.
The multiple threads cause complexity, and multiple heaps are a mechanism for dealing with the complexity.
The spectrum ranges from multiple threads using a single heap, denoted as T:1 (see \VRef[Figure]{f:SingleHeap}), to multiple threads sharing multiple heaps, denoted as T:H (see \VRef[Figure]{f:SharedHeaps}), to one thread per heap, denoted as 1:1 (see \VRef[Figure]{f:PerThreadHeap}), which is almost back to a single-threaded allocator.


\paragraph{T:1 model} where all threads allocate and deallocate objects from one heap.
Memory is obtained from the freed objects, or reserved memory in the heap, or from the operating system (OS);
the heap may also return freed memory to the operating system.
The arrows indicate the direction memory conceptually moves for each kind of operation: allocation moves memory along the path from the heap/operating-system to the user application, while deallocation moves memory along the path from the application back to the heap/operating-system.
To safely handle concurrency, a single heap uses locking to provide mutual exclusion.
Whether using a single lock for all heap operations or fine-grained locking for different operations, a single heap may be a significant source of contention for programs with a large amount of memory allocation.

\begin{figure}
\centering
\subfigure[T:1]{
%       \input{SingleHeap.pstex_t}
        \input{SingleHeap}
        \label{f:SingleHeap}
} % subfigure
\vrule
\subfigure[T:H]{
%       \input{MultipleHeaps.pstex_t}
        \input{SharedHeaps}
        \label{f:SharedHeaps}
} % subfigure
\vrule
\subfigure[1:1]{
%       \input{MultipleHeapsGlobal.pstex_t}
        \input{PerThreadHeap}
        \label{f:PerThreadHeap}
} % subfigure
\caption{Multiple Heaps, Thread:Heap Relationship}
\end{figure}


\paragraph{T:H model} where each thread allocates storage from several heaps depending on certain criteria, with the goal of reducing contention by spreading allocations/deallocations across the heaps.
The decision on when to create a new heap and which heap a thread allocates from depends on the allocator design.
The performance goal is to reduce the ratio of heaps to threads.
In general, locking is required, since more than one thread may concurrently access a heap during its lifetime, but contention is reduced because fewer threads access a specific heap.

For example, multiple heaps are managed in a pool, starting with a single or a fixed number of heaps that increase\-/decrease depending on contention\-/space issues.
At creation, a thread is associated with a heap from the pool.
In some implementations of this model, when the thread attempts an allocation and its associated heap is locked (contention), it scans for an unlocked heap in the pool.
If an unlocked heap is found, the thread changes its association and uses that heap.
If all heaps are locked, the thread may create a new heap, use it, and then place the new heap into the pool;
or the thread can block waiting for a heap to become available.
While the heap-pool approach often minimizes the number of extant heaps, the worse case can result in more heaps than threads;
\eg if the number of threads is large at startup with many allocations creating a large number of heaps and then the number of threads reduces.

Threads using multiple heaps need to determine the specific heap to access for an allocation/deallocation, \ie association of thread to heap.
A number of techniques are used to establish this association.
The simplest approach is for each thread to have a pointer to its associated heap (or to administrative information that points to the heap), and this pointer changes if the association changes.
For threading systems with thread-local storage, the heap pointer is created using this mechanism;
otherwise, the heap routines must simulate thread-local storage using approaches like hashing the thread's stack-pointer or thread-id to find its associated heap.

The storage management for multiple heaps is more complex than for a single heap (see \VRef[Figure]{f:AllocatorComponents}).
\VRef[Figure]{f:MultipleHeapStorage} illustrates the general storage layout for multiple heaps.
Allocated and free objects are labelled by the thread or heap they are associated with.
(Links between free objects are removed for simplicity.)
The management information in the static zone must be able to locate all heaps in the dynamic zone.
The management information for the heaps must reside in the dynamic-allocation zone if there are a variable number.
Each heap in the dynamic zone is composed of a list of free objects and a pointer to its reserved memory.
An alternative implementation is for all heaps to share one reserved memory, which requires a separate lock for the reserved storage to ensure mutual exclusion when acquiring new memory.
Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area, pushing part of the storage management complexity back to the operating system.

\begin{figure}
\centering
\input{MultipleHeapsStorage}
\caption{Multiple-Heap Storage}
\label{f:MultipleHeapStorage}
\end{figure}

Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup.
The external fragmentation experienced by a program with a single heap is now multiplied by the number of heaps, since each heap manages its own free storage and allocates its own reserved memory.
Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the operating system, which can be expensive.
Depending on how the operating system provides dynamic storage to an application, returning storage may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.
In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused.

Adding a \newterm{global heap} (G) attempts to reduce the cost of obtaining/returning memory among heaps (sharing) by buffering storage within the application address-space.
Now, each heap obtains and returns storage to/from the global heap rather than the operating system.
Storage is obtained from the global heap only when a heap allocation cannot be fulfilled, and returned to the global heap when a heap's free memory exceeds some threshold.
Similarly, the global heap buffers this memory, obtaining and returning storage to/from the operating system as necessary.
The global heap does not have its own thread and makes no internal allocation requests;
instead, it uses the application thread, which called one of the multiple heaps and then the global heap, to perform operations.
Hence, the worst-case cost of a memory operation includes all these steps.
With respect to heap blowup, the global heap provides an indirect mechanism to move free memory among heaps, which usually has a much lower cost than interacting with the operating system to achieve the same goal and is independent of the mechanism used by the operating system to present dynamic memory to an address space.

However, since any thread may indirectly perform a memory operation on the global heap, it is a shared resource that requires locking.
A single lock can be used to protect the global heap or fine-grained locking can be used to reduce contention.
In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap.


\paragraph{1:1 model (thread heaps)} where each thread has its own heap eliminating most contention and locking because threads seldom access another thread's heap (see ownership in \VRef{s:Ownership}).
An additional benefit of thread heaps is improved locality due to better memory layout.
As each thread only allocates from its heap, all objects for a thread are consolidated in the storage area for that heap, better utilizing each CPUs cache and accessing fewer pages.
In contrast, the T:H model spreads each thread's objects over a larger area in different heaps.
Thread heaps can also eliminate allocator-induced active false-sharing, if memory is acquired so it does not overlap at crucial boundaries with memory for another thread's heap.
For example, assume page boundaries coincide with cache line boundaries, if a thread heap always acquires pages of memory then no two threads share a page or cache line unless pointers are passed among them.
Hence, allocator-induced active false-sharing in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing} cannot occur because the memory for thread heaps never overlaps.

When a thread terminates, there are two options for handling its thread heap.
First is to free all objects in the thread heap to the global heap and destroy the thread heap.
Second is to place the thread heap on a list of available heaps and reuse it for a new thread in the future.
Destroying the thread heap immediately may reduce external fragmentation sooner, since all free objects are freed to the global heap and may be reused by other threads.
Alternatively, reusing thread heaps may improve performance if the inheriting thread makes similar allocation requests as the thread that previously held the thread heap because any unfreed storage is immediately accessible.


\subsection{User-Level Threading}

It is possible to use any of the heap models with user-level (M:N) threading.
However, an important goal of user-level threading is for fast operations (creation/termination/context-switching) by not interacting with the operating system, which allows the ability to create large numbers of high-performance interacting threads ($>$ 10,000).
It is difficult to retain this goal, if the user-threading model is directly involved with the heap model.
\VRef[Figure]{f:UserLevelKernelHeaps} shows that virtually all user-level threading systems use whatever kernel-level heap-model is provided by the language runtime.
Hence, a user thread allocates/deallocates from/to the heap of the kernel thread on which it is currently executing.

\begin{figure}
\centering
\input{UserKernelHeaps}
\caption{User-Level Kernel Heaps}
\label{f:UserLevelKernelHeaps}
\end{figure}

Adopting this model results in a subtle problem with shared heaps.
With kernel threading, an operation that is started by a kernel thread is always completed by that thread.
For example, if a kernel thread starts an allocation/deallocation on a shared heap, it always completes that operation with that heap even if preempted, \ie any locking correctness associated with the shared heap is preserved across preemption.

However, this correctness property is not preserved for user-level threading.
A user thread can start an allocation/deallocation on one kernel thread, be preempted (time slice), and continue running on a different kernel thread to complete the operation~\cite{Dice02}.
When the user thread continues on the new kernel thread, it may have pointers into the previous kernel-thread's heap and hold locks associated with it.
To get the same kernel-thread safety, time slicing must be disabled/\-enabled around these operations, so the user thread cannot jump to another kernel thread.
However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption does not happen that frequently.
Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it can complete atomically.
Occasionally ignoring a preemption should be benign, but a persistent lack of preemption can result in both short and long term starvation.


\subsection{Ownership}
\label{s:Ownership}

\newterm{Ownership} defines which heap an object is returned-to on deallocation.
If a thread returns an object to the heap it was originally allocated from, a heap has ownership of its objects.
Alternatively, a thread can return an object to the heap it is currently associated with, which can be any heap accessible during a thread's lifetime.
\VRef[Figure]{f:HeapsOwnership} shows an example of multiple heaps (minus the global heap) with and without ownership.
Again, the arrows indicate the direction memory conceptually moves for each kind of operation.
For the 1:1 thread:heap relationship, a thread only allocates from its own heap, and without ownership, a thread only frees objects to its own heap, which means the heap is private to its owner thread and does not require any locking, called a \newterm{private heap}.
For the T:1/T:H models with or without ownership or the 1:1 model with ownership, a thread may free objects to different heaps, which makes each heap publicly accessible to all threads, called a \newterm{public heap}.

\begin{figure}
\centering
\subfigure[Ownership]{
        \input{MultipleHeapsOwnership}
} % subfigure
\hspace{0.25in}
\subfigure[No Ownership]{
        \input{MultipleHeapsNoOwnership}
} % subfigure
\caption{Heap Ownership}
\label{f:HeapsOwnership}
\end{figure}

\VRef[Figure]{f:MultipleHeapStorageOwnership} shows the effect of ownership on storage layout.
(For simplicity, assume the heaps all use the same size of reserves storage.)
In contrast to \VRef[Figure]{f:MultipleHeapStorage}, each reserved area used by a heap only contains free storage for that particular heap because threads must return free objects back to the owner heap.
Again, because multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
The exception is for the 1:1 model if reserved memory does not overlap a cache-line because all allocated storage within a used area is associated with a single thread.
In this case, there is no allocator-induced active false-sharing (see \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}) because two adjacent allocated objects used by different threads cannot share a cache-line.
As well, there is no allocator-induced passive false-sharing (see \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}) because two adjacent allocated objects used by different threads cannot occur because free objects are returned to the owner heap.
% Passive false-sharing may still occur, if delayed ownership is used (see below).

\begin{figure}
\centering
\input{MultipleHeapsOwnershipStorage.pstex_t}
\caption{Multiple-Heap Storage with Ownership}
\label{f:MultipleHeapStorageOwnership}
\end{figure}

The main advantage of ownership is preventing heap blowup by returning storage for reuse by the owner heap.
Ownership prevents the classical problem where one thread performs allocations from one heap, passes the object to another thread, and the receiving thread deallocates the object to another heap, hence draining the initial heap of storage.
As well, allocator-induced passive false-sharing is eliminated because returning an object to its owner heap means it can never be allocated to another thread.
For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, the deallocation by Thread$_2$ returns Object$_2$ back to Thread$_1$'s heap;
hence a subsequent allocation by Thread$_2$ cannot return this storage.
The disadvantage of ownership is deallocating to another thread's heap so heaps are no longer private and require locks to provide safe concurrent access.

Object ownership can be immediate or delayed, meaning free objects may be batched on a separate free list either by the returning or receiving thread.
While the returning thread can batch objects, batching across multiple heaps is complex and there is no obvious time when to push back to the owner heap.
It is better for returning threads to immediately return to the receiving thread's batch list as the receiving thread has better knowledge when to incorporate the batch list into its free pool.
Batching leverages the fact that most allocation patterns use the contention-free fast-path, so locking on the batch list is rare for both the returning and receiving threads.

It is possible for heaps to steal objects rather than return them and then reallocate these objects again when storage runs out on a heap.
However, stealing can result in passive false-sharing.
For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Thread$_2$'s heap initially.
If Thread$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.


\section{Object Containers}
\label{s:ObjectContainers}

Bracketing every allocation with headers/trailers can result in significant internal fragmentation, as shown in \VRef[Figure]{f:ObjectHeaders}.
Especially if the headers contain redundant management information, then storing that information is a waste of storage, \eg object size may be the same for many objects because programs only allocate a small set of object sizes.
As well, it can result in poor cache usage, since only a portion of the cache line is holding useful information from the program's perspective.
Spatial locality can also be negatively affected leading to poor cache locality~\cite{Feng05}:
while the header and object are together in memory, they are generally not accessed together;
\eg the object is accessed by the program when it is allocated, while the header is accessed by the allocator when the object is free.

\begin{figure}
\centering
\subfigure[Object Headers]{
        \input{ObjectHeaders}
        \label{f:ObjectHeaders}
} % subfigure
\subfigure[Object Container]{
        \input{Container}
        \label{f:ObjectContainer}
} % subfigure
\caption{Header Placement}
\label{f:HeaderPlacement}
\end{figure}

An alternative approach factors common header/trailer information to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks} in~\cite{Berger00}), as in \VRef[Figure]{f:ObjectContainer}.
The header for the container holds information necessary for all objects in the container;
a trailer may also be used at the end of the container.
Similar to the approach described for thread heaps in \VRef{s:MultipleHeaps}, if container boundaries do not overlap with memory of another container at crucial boundaries and all objects in a container are allocated to the same thread, allocator-induced active false-sharing is avoided.

The difficulty with object containers lies in finding the object header/trailer given only the object address, since that is normally the only information passed to the deallocation operation.
One way to do this is to start containers on aligned addresses in memory, then truncate the lower bits of the object address to obtain the header address (or round up and subtract the trailer size to obtain the trailer address).
For example, if an object at address 0xFC28\,EF08 is freed and containers are aligned on 64\,KB (0x0001\,0000) addresses, then the container header is at 0xFC28\,0000.

Normally, a container has homogeneous objects of fixed size, with fixed information in the header that applies to all container objects (\eg object size and ownership).
This approach greatly reduces internal fragmentation since far fewer headers are required, and potentially increases spatial locality as a cache line or page holds more objects since the objects are closer together due to the lack of headers.
However, although similar objects are close spatially within the same container, different sized objects are further apart in separate containers.
Depending on the program, this may or may not improve locality.
If the program uses several objects from a small number of containers in its working set, then locality is improved since fewer cache lines and pages are required.
If the program uses many containers, there is poor locality, as both caching and paging increase.
Another drawback is that external fragmentation may be increased since containers reserve space for objects that may never be allocated by the program, \ie there are often multiple containers for each size only partially full.
However, external fragmentation can be reduced by using small containers.

Containers with heterogeneous objects implies different headers describing them, which complicates the problem of locating a specific header solely by an address.
A couple of solutions can be used to implement containers with heterogeneous objects.
However, the problem with allowing objects of different sizes is that the number of objects, and therefore headers, in a single container is unpredictable.
One solution allocates headers at one end of the container, while allocating objects from the other end of the container;
when the headers meet the objects, the container is full.
Freed objects cannot be split or coalesced since this causes the number of headers to change.
The difficulty in this strategy remains in finding the header for a specific object;
in general, a search is necessary to find the object's header among the container headers.
A second solution combines the use of container headers and individual object headers.
Each object header stores the object's heterogeneous information, such as its size, while the container header stores the homogeneous information, such as the owner when using ownership.
This approach allows containers to hold different types of objects, but does not completely separate headers from objects.
The benefit of the container in this case is to reduce some redundant information that is factored into the container header.

In summary, object containers trade off internal fragmentation for external fragmentation by isolating common administration information to remove/reduce internal fragmentation, but at the cost of external fragmentation as some portion of a container may not be used and this portion is unusable for other kinds of allocations.
A consequence of this tradeoff is its effect on spatial locality, which can produce positive or negative results depending on program access-patterns.


\subsection{Container Ownership}
\label{s:ContainerOwnership}

Without ownership, objects in a container are deallocated to the heap currently associated with the thread that frees the object.
Thus, different objects in a container may be on different heap free-lists (see \VRef[Figure]{f:ContainerNoOwnershipFreelist}).
With ownership, all objects in a container belong to the same heap (see \VRef[Figure]{f:ContainerOwnershipFreelist}), so ownership of an object is determined by the container owner.
If multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
Only with the 1:1 model and ownership is active and passive false-sharing avoided (see \VRef{s:Ownership}).
Passive false-sharing may still occur, if delayed ownership is used.
Finally, a completely free container can become reserved storage and be reset to allocate objects of a new size or freed to the global heap.

\begin{figure}
\centering
\subfigure[No Ownership]{
        \input{ContainerNoOwnershipFreelist}
        \label{f:ContainerNoOwnershipFreelist}
} % subfigure
\vrule
\subfigure[Ownership]{
        \input{ContainerOwnershipFreelist}
        \label{f:ContainerOwnershipFreelist}
} % subfigure
\caption{Free-list Structure with Container Ownership}
\end{figure}

When a container changes ownership, the ownership of all objects within it change as well.
Moving a container involves moving all objects on the heap's free-list in that container to the new owner.
This approach can reduce contention for the global heap, since each request for objects from the global heap returns a container rather than individual objects.

Additional restrictions may be applied to the movement of containers to prevent active false-sharing.
For example, in \VRef[Figure]{f:ContainerFalseSharing1}, a container being used by Thread$_1$ changes ownership, through the global heap.
In \VRef[Figure]{f:ContainerFalseSharing2}, when Thread$_2$ allocates an object from the newly acquired container it is actively false-sharing even though no objects are passed among threads.
Note, once the object is freed by Thread$_1$, no more false sharing can occur until the container changes ownership again.
To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free.
One implementation approach that increases the freedom to return a free container to the operating system involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area, again pushing storage management complexity back to the operating system.

\begin{figure}
\centering
\subfigure[]{
        \input{ContainerFalseSharing1}
        \label{f:ContainerFalseSharing1}
} % subfigure
\subfigure[]{
        \input{ContainerFalseSharing2}
        \label{f:ContainerFalseSharing2}
} % subfigure
\caption{Active False-Sharing using Containers}
\label{f:ActiveFalseSharingContainers}
\end{figure}

Using containers with ownership increases external fragmentation since a new container for a requested object size must be allocated separately for each thread requesting it.
In \VRef[Figure]{f:ExternalFragmentationContainerOwnership}, using object ownership allocates 80\% more space than without ownership.

\begin{figure}
\centering
\subfigure[No Ownership]{
        \input{ContainerNoOwnership}
} % subfigure
\\
\subfigure[Ownership]{
        \input{ContainerOwnership}
} % subfigure
\caption{External Fragmentation with Container Ownership}
\label{f:ExternalFragmentationContainerOwnership}
\end{figure}


\subsection{Container Size}
\label{s:ContainerSize}

One way to control the external fragmentation caused by allocating a large container for a small number of requested objects is to vary the size of the container.
As described earlier, container boundaries need to be aligned on addresses that are a power of two to allow easy location of the header (by truncating lower bits).
Aligning containers in this manner also determines the size of the container.
However, the size of the container has different implications for the allocator.

The larger the container, the fewer containers are needed, and hence, the fewer headers need to be maintained in memory, improving both internal fragmentation and potentially performance.
However, with more objects in a container, there may be more objects that are unallocated, increasing external fragmentation.
With smaller containers, not only are there more containers, but a second new problem arises where objects are larger than the container.
In general, large objects, \eg greater than 64\,KB, are allocated directly from the operating system and are returned immediately to the operating system to reduce long-term external fragmentation.
If the container size is small, \eg 1\,KB, then a 1.5\,KB object is treated as a large object, which is likely to be inappropriate.
Ideally, it is best to use smaller containers for smaller objects, and larger containers for medium objects, which leads to the issue of locating the container header.

In order to find the container header when using different sized containers, a super container is used (see~\VRef[Figure]{f:SuperContainers}).
The super container spans several containers, contains a header with information for finding each container header, and starts on an aligned address.
Super-container headers are found using the same method used to find container headers by dropping the lower bits of an object address.
The containers within a super container may be different sizes or all the same size.
If the containers in the super container are different sizes, then the super-container header must be searched to determine the specific container for an object given its address.
If all containers in the super container are the same size, \eg 16KB, then a specific container header can be found by a simple calculation.
The free space at the end of a super container is used to allocate new containers.

\begin{figure}
\centering
\input{SuperContainers}
% \includegraphics{diagrams/supercontainer.eps}
\caption{Super Containers}
\label{f:SuperContainers}
\end{figure}

Minimal internal and external fragmentation is achieved by having as few containers as possible, each being as full as possible.
It is also possible to achieve additional benefit by using larger containers for popular small sizes, as it reduces the number of containers with associated headers.
However, this approach assumes it is possible for an allocator to determine in advance which sizes are popular.
Keeping statistics on requested sizes allows the allocator to make a dynamic decision about which sizes are popular.
For example, after receiving a number of allocation requests for a particular size, that size is considered a popular request size and larger containers are allocated for that size.
If the decision is incorrect, larger containers than necessary are allocated that remain mostly unused.
A programmer may be able to inform the allocator about popular object sizes, using a mechanism like @mallopt@, in order to select an appropriate container size for each object size.


\subsection{Container Free-Lists}
\label{s:containersfreelists}

The container header allows an alternate approach for managing the heap's free-list.
Rather than maintain a global free-list throughout the heap (see~\VRef[Figure]{f:GlobalFreeListAmongContainers}), the containers are linked through their headers and only the local free objects within a container are linked together (see~\VRef[Figure]{f:LocalFreeListWithinContainers}).
Note, maintaining free lists within a container assumes all free objects in the container are associated with the same heap;
thus, this approach only applies to containers with ownership.

This alternate free-list approach can greatly reduce the complexity of moving all freed objects belonging to a container to another heap.
To move a container using a global free-list, as in \VRef[Figure]{f:GlobalFreeListAmongContainers}, the free list is first searched to find all objects within the container.
Each object is then removed from the free list and linked together to form a local free-list for the move to the new heap.
With local free-lists in containers, as in \VRef[Figure]{f:LocalFreeListWithinContainers}, the container is simply removed from one heap's free list and placed on the new heap's free list.
Thus, when using local free-lists, the operation of moving containers is reduced from $O(N)$ to $O(1)$.
However, there is the additional storage cost in the header, which increases the header size, and therefore internal fragmentation.

\begin{figure}
\centering
\subfigure[Global Free-List Among Containers]{
        \input{FreeListAmongContainers}
        \label{f:GlobalFreeListAmongContainers}
} % subfigure
\hspace{0.25in}
\subfigure[Local Free-List Within Containers]{
        \input{FreeListWithinContainers}
        \label{f:LocalFreeListWithinContainers}
} % subfigure
\caption{Container Free-List Structure}
\label{f:ContainerFreeListStructure}
\end{figure}

When all objects in the container are the same size, a single free-list is sufficient.
However, when objects in the container are different size, the header needs a free list for each size class when using a binning allocation algorithm, which can be a significant increase in the container-header size.
The alternative is to use a different allocation algorithm with a single free-list, such as a sequential-fit allocation-algorithm.


\subsection{Hybrid Private/Public Heap}
\label{s:HybridPrivatePublicHeap}

Section~\Vref{s:Ownership} discusses advantages and disadvantages of public heaps (T:H model and with ownership) and private heaps (thread heaps with ownership).
For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps (see~\VRef[Figure]{f:HybridPrivatePublicHeap}).
The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
In the hybrid approach, a thread first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
Similarly, a thread first deallocates an object to its private heap, and second to the public heap.
Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps.
Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap.
Finally, when a thread frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing thread's private heap for delayed ownership, which allows the freeing thread to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return.

\begin{figure}
\centering
\input{PrivatePublicHeaps.pstex_t}
\caption{Hybrid Private/Public Heap for Per-thread Heaps}
\label{f:HybridPrivatePublicHeap}
% \vspace{10pt}
% \input{RemoteFreeList.pstex_t}
% \caption{Remote Free-List}
% \label{f:RemoteFreeList}
\end{figure}

As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified.
For example, if only the private heap interacts with the global heap, the public heap can be reduced to a lock-protected free-list of objects deallocated by other threads due to ownership, called a \newterm{remote free-list}.
To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
Clearing the remote free-list is $O(1)$ if the list can simply be added to the end of the private-heap's free-list, or $O(N)$ if some action must be performed for each freed object.

If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
In this scenario, the private heap must deallocate storage after reaching a certain threshold to the public heap (and then eventually to the global heap from the public heap) or heap blowup can occur.
If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.

The main disadvantage of each thread having both a private and public heap is the complexity of managing two heaps and their interactions in an allocator.
Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
In many case, the hybrid approach is actually being used, but the simpler heap is just folded into the complex heap, even though the operations logically belong in separate heaps.
For example, a remote free-list is actually a simple public-heap, but may be implemented as an integral component of the complex private-heap in an allocator, masking the presence of a hybrid approach.


\section{Allocation Buffer}
\label{s:AllocationBuffer}

An allocation buffer is reserved memory (see~\VRef{s:AllocatorComponents}) not yet allocated to the program, and is used for allocating objects when the free list is empty.
That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or operating system, respectively.
The allocation buffer reduces contention and the number of global/operating-system calls.
For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.

Allocation buffers are useful initially when there are no freed objects in a heap because many allocations usually occur when a thread starts (simple bump allocation).
Furthermore, to prevent heap blowup, objects should be reused before allocating a new allocation buffer.
Thus, allocation buffers are often allocated more frequently at program/thread start, and then allocations often diminish.

Using an allocation buffer with a thread heap avoids active false-sharing, since all objects in the allocation buffer are allocated to the same thread.
For example, if all objects sharing a cache line come from the same allocation buffer, then these objects are allocated to the same thread, avoiding active false-sharing.
Active false-sharing may still occur if objects are freed to the global heap and reused by another heap.

Allocation buffers may increase external fragmentation, since some memory in the allocation buffer may never be allocated.
A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or operating system.
The allocation buffer also slightly increases internal fragmentation, since a pointer is necessary to locate the next free object in the buffer.

The unused part of a container, neither allocated or freed, is an allocation buffer.
For example, when a container is created, rather than placing all objects within the container on the free list, the objects form an allocation buffer and are allocated from the buffer as allocation requests are made.
This lazy method of constructing objects is beneficial in terms of paging and caching.
For example, although an entire container, possibly spanning several pages, is allocated from the operating system, only a small part of the container is used in the working set of the allocator, reducing the number of pages and cache lines that are brought into higher levels of cache.


\section{Lock-Free Operations}
\label{s:LockFreeOperations}

A \newterm{lock-free algorithm} guarantees safe concurrent-access to a data structure, so that at least one thread makes progress, but an individual thread has no execution bound and may starve~\cite[pp.~745--746]{Herlihy93}.
(A \newterm{wait-free algorithm} puts a bound on the number of steps any thread takes to complete an operation to prevent starvation.)
Lock-free operations can be used in an allocator to reduce or eliminate the use of locks.
While locks and lock-free data-structures often have equal performance, lock-free has the advantage of not holding a lock across preemption so other threads can continue to make progress.
With respect to the heap, these situations are unlikely unless all threads make extremely high use of dynamic-memory allocation, which can be an indication of poor design.
Nevertheless, lock-free algorithms can reduce the number of context switches, since a thread does not yield/block while waiting for a lock;
on the other hand, a thread may busy-wait for an unbounded period holding a processor.
Finally, lock-free implementations have greater complexity and hardware dependency.
Lock-free algorithms can be applied most easily to simple free-lists, \eg remote free-list, to allow lock-free insertion and removal from the head of a stack.
Implementing lock-free operations for more complex data-structures (queue~\cite{Valois94}/deque~\cite{Sundell08}) is correspondingly more complex.
Michael~\cite{Michael04} and Gidenstam \etal \cite{Gidenstam05} have created lock-free variations of the Hoard allocator.


% \subsubsection{Speed Workload}
% The worload method uses the opposite approach. It calls the allocator's routines for a specific amount of time and measures how much work was done during that time. Then, similar to the time method, it divides the time by the workload done during that time and calculates the average time taken by the allocator's routine.
% *** FIX ME: Insert a figure of above benchmark with description
% 
% \paragraph{Knobs}
% *** FIX ME: Insert Knobs