# source:doc/theses/mubeen_zulfiqar_MMath/background.tex@fb6691a

Last change on this file since fb6691a was fb6691a, checked in by Peter A. Buhr <pabuhr@…>, 3 months ago

final proofread of Mubeen's MMath thesis

• Property mode set to 100644
File size: 58.4 KB
Line
1\begin{comment}
2====================
3Writing Points:
4\begin{itemize}
5\item
6Classification of benchmarks.
7\item
8Literature review of current benchmarks.
9\item
10Features and limitations.
11\item
12Literature review of current memory allocators.
13\item
14Breakdown of memory allocation techniques.
15\item
16Features and limitations.
17\end{itemize}
18\end{comment}
19
20\chapter[Background]{Background\footnote{Part of this chapter draws from similar background work in~\cite{Wasik08} with many updates.}}
21
22
23A 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.
24Space for each allocated object comes from the dynamic-allocation zone.
25A \newterm{memory allocator} contains a complex data-structure and code that manages the layout of objects in the dynamic-allocation zone.
26The management goals are to make allocation/deallocation operations as fast as possible while densely packing objects to make efficient use of memory.
27Objects in C/\CC cannot be moved to aid the packing process, only adjacent free storage can be \newterm{coalesced} into larger free areas.
28The 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.
29
30
31\section{Allocator Components}
32\label{s:AllocatorComponents}
33
34\VRef[Figure]{f:AllocatorComponents} shows the two important data components for a memory allocator, management and storage, collectively called the \newterm{heap}.
35The \newterm{management data} is a data structure located at a known memory address and contains all information necessary to manage the storage data.
36The management data starts with fixed-sized information in the static-data memory that references components in the dynamic-allocation memory.
37The \newterm{storage data} is composed of allocated and freed objects, and \newterm{reserved memory}.
38Allocated objects (light grey) are variable sized, and are allocated and maintained by the program;
39\ie only the memory allocator knows the location of allocated storage, not the program.
40\begin{figure}[h]
41\centering
42\input{AllocatorComponents}
43\caption{Allocator Components (Heap)}
44\label{f:AllocatorComponents}
45\end{figure}
46Freed objects (white) represent memory deallocated by the program, which are linked into one or more lists facilitating easy location of new allocations.
47Often 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.
48Reserved memory (dark grey) is one or more blocks of memory obtained from the operating system but not yet allocated to the program;
49if there are multiple reserved blocks, they are also chained together, usually internally.
50
51In some allocator designs, allocated and freed objects have additional management data embedded within them.
52\VRef[Figure]{f:AllocatedObject} shows an allocated object with a header, trailer, and alignment padding and spacing around the object.
54The trailer may be used to simplify an allocation implementation, \eg coalescing, and/or for security purposes to mark the end of an object.
55An object may be preceded by padding to ensure proper alignment.
56Some algorithms quantize allocation requests into distinct sizes, called \newterm{buckets}, resulting in additional spacing after objects less than the quantized value.
57(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.)
58When padding and spacing are necessary, neither can be used to satisfy a future allocation request while the current allocation exists.
59A free object also contains management data, \eg size, chaining, etc.
60The 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.
61The 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.
62
63\begin{figure}
64\centering
65\input{AllocatedObject}
66\caption{Allocated Object}
67\label{f:AllocatedObject}
68\end{figure}
69
70
73
75Because the memory allocator is only executed by a single thread, concurrency issues do not exist.
76The primary issues in designing a single-threaded memory-allocator are fragmentation and locality.
77
78
79\subsection{Fragmentation}
80\label{s:Fragmentation}
81
82Fragmentation is memory requested from the operating system but not used by the program;
83hence, allocated objects are not fragmentation.
84\VRef[Figure]{f:InternalExternalFragmentation} shows fragmentation is divided into two forms: internal or external.
85
86\begin{figure}
87\centering
88\input{IntExtFragmentation}
89\caption{Internal and External Fragmentation}
90\label{f:InternalExternalFragmentation}
91\end{figure}
92
93\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.
94This memory is typically used by the allocator for management purposes or required by the architecture for correctness, \eg alignment.
95Internal fragmentation is problematic when management space is a significant proportion of an allocated object.
96For example, if internal fragmentation is as large as the object being managed, then the memory usage for that object is doubled.
97An allocator should strive to keep internal management information to a minimum.
98
99\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.
100This memory is problematic in two ways: heap blowup and highly fragmented memory.
101\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}.
102Heap blowup can occur due to allocator policies that are too restrictive in reusing freed memory and/or no coalescing of free storage.
103Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects.
104\VRef[Figure]{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time.
105Blocks of free memory become smaller and non-contiguous making them less useful in serving allocation requests.
106Memory is highly fragmented when most free blocks are unusable because of their sizes.
107For 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.
108If 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.
109
110\begin{figure}
111\centering
112\input{MemoryFragmentation}
113\caption{Memory Fragmentation}
114\label{f:MemoryFragmentation}
115\vspace{10pt}
116\subfigure[Contiguous]{
117        \input{ContigFragmentation}
118        \label{f:Contiguous}
119} % subfigure
120        \subfigure[Highly Fragmented]{
121        \input{NonContigFragmentation}
122\label{f:HighlyFragmented}
123} % subfigure
124\caption{Fragmentation Quality}
125\label{f:FragmentationQuality}
126\end{figure}
127
128For a single-threaded memory allocator, three basic approaches for controlling fragmentation are identified~\cite{Johnstone99}.
129The 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.
130Different search policies determine the free object selected, \eg the first free object large enough or closest to the requested size.
131Any storage larger than the request can become spacing after the object or be split into a smaller free object.
132The 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.
133
134The second approach is a \newterm{segregated} or \newterm{binning algorithm} with a set of lists for different sized freed objects.
135When an object is allocated, the requested size is rounded up to the nearest bin-size, often leading to spacing after the object.
136A 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.
137The fewer bin-sizes, the fewer lists need to be searched and maintained;
138however, the bin sizes are less likely to closely fit the requested object size, leading to more internal fragmentation.
139The 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.
140A 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.
141For 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.
142For 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.
143
144The third approach is \newterm{splitting} and \newterm{coalescing algorithms}.
145When 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.
146For 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.
147When 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.
148Coalescing can be done eagerly at each deallocation or lazily when an allocation cannot be fulfilled.
149In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays during coalescing.
150While coalescing does not reduce external fragmentation, the coalesced blocks improve fragmentation quality so future allocations are less likely to cause heap blowup.
151Splitting and coalescing can be used with other algorithms to avoid highly fragmented memory.
152
153
154\subsection{Locality}
155\label{s:Locality}
156
157The 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}.
158Temporal 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.
159Temporal locality commonly occurs during an iterative computation with a fixed set of disjoint variables, while spatial locality commonly occurs when traversing an array.
160
161Hardware takes advantage of temporal and spatial locality through multiple levels of caching, \ie memory hierarchy.
162When 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.
163For example, entire cache lines are transferred between memory and cache and entire virtual-memory pages are transferred between disk and memory.
164A 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.}.
165
166Temporal locality is largely controlled by how a program accesses its variables~\cite{Feng05}.
167Nevertheless, a memory allocator can have some indirect influence on temporal locality and largely dictates spatial locality.
168For 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.
169For 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.
170However, usage patterns are different for every program as is the underlying hardware memory architecture;
171hence, no general-purpose memory-allocator can provide ideal locality for every program on every computer.
172
173There are a number of ways a memory allocator can degrade locality by increasing the working set.
174For example, a memory allocator may access multiple free objects before finding one to satisfy an allocation request, \eg sequential-fit algorithm.
175If 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}.
176Another way locality can be degraded is by spatially separating related data.
177For example, in a binning allocator, objects of different sizes are allocated from different bins that may be located in different pages of memory.
178
179
182
184In 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.
185
186
187\subsection{Mutual Exclusion}
188\label{s:MutualExclusion}
189
190\newterm{Mutual exclusion} provides sequential access to the shared management data of the heap.
191There are two performance issues for mutual exclusion.
192First is the overhead necessary to perform (at least) a hardware atomic operation every time a shared resource is accessed.
193Second is when multiple threads contend for a shared resource simultaneously, and hence, some threads must wait until the resource is released.
194Contention can be reduced in a number of ways:
195\begin{itemize}[itemsep=0pt]
196\item
197using multiple fine-grained locks versus a single lock, spreading the contention across a number of locks;
198\item
199using trylock and generating new storage if the lock is busy, yielding a classic space versus time tradeoff;
200\item
201using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Oyama99}.
202\end{itemize}
203However, all of these approaches have degenerate cases where program contention is high, which occurs outside of the allocator.
204
205
206\subsection{False Sharing}
207\label{s:FalseSharing}
208
209False sharing is a dynamic phenomenon leading to cache thrashing.
210When 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.
211False sharing can occur in three different ways: program induced, allocator-induced active, and allocator-induced passive;
212a memory allocator can only affect the latter two.
213
214\paragraph{\newterm{Program-induced false-sharing}}
215occurs when one thread passes an object sharing a cache line to another thread, and both threads modify the respective objects.
216\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$.
217Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
218
219\begin{figure}
220\centering
221\subfigure[Program-Induced False-Sharing]{
222        \input{ProgramFalseSharing}
223        \label{f:ProgramInducedFalseSharing}
224} \\
225\vspace{5pt}
226\subfigure[Allocator-Induced Active False-Sharing]{
227        \input{AllocInducedActiveFalseSharing}
228        \label{f:AllocatorInducedActiveFalseSharing}
229} \\
230\vspace{5pt}
231\subfigure[Allocator-Induced Passive False-Sharing]{
232        \input{AllocInducedPassiveFalseSharing}
233        \label{f:AllocatorInducedPassiveFalseSharing}
234} % subfigure
235\caption{False Sharing}
236\label{f:FalseSharing}
237\end{figure}
238
239\paragraph{\newterm{Allocator-induced active false-sharing}}
240\label{s:AllocatorInducedActiveFalseSharing}
241occurs when objects are allocated within the same cache line but to different threads.
242For example, in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}, each thread allocates an object and loads a cache-line of memory into its associated cache.
243Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
244
245\paragraph{\newterm{Allocator-induced passive false-sharing}}
246\label{s:AllocatorInducedPassiveFalseSharing}
247is another form of allocator-induced false-sharing caused by program-induced false-sharing.
248When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing.
249For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Thread$_1$ passes Object$_2$ to Thread$_2$, and Thread$_2$ subsequently deallocates Object$_2$.
250Allocator-induced passive false-sharing occurs when Object$_2$ is reallocated to Thread$_2$ while Thread$_1$ is still using Object$_1$.
251
252
253\subsection{Heap Blowup}
254\label{s:HeapBlowup}
255
256In a multi-threaded program, heap blowup can occur when memory freed by one thread is inaccessible to other threads due to the allocation strategy.
257Specific examples are presented in later sections.
258
259
262
263The following features are used in the construction of multi-threaded memory-allocators:
264\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
265\item multiple heaps
266\begin{list}{\alph{enumii})}{\usecounter{enumii}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
267\item with or without a global heap
268\item with or without ownership
269\end{list}
270\item object containers
271\begin{list}{\alph{enumii})}{\usecounter{enumii}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
272\item with or without ownership
273\item fixed or variable sized
274\item global or local free-lists
275\end{list}
276\item hybrid private/public heap
277\item allocation buffer
278\item lock-free operations
279\end{list}
280The first feature, multiple heaps, pertains to different kinds of heaps.
281The second feature, object containers, pertains to the organization of objects within the storage area.
282The remaining features apply to different parts of the allocator design or implementation.
283
284
285\section{Multiple Heaps}
286\label{s:MultipleHeaps}
287
289The multiple threads cause complexity, and multiple heaps are a mechanism for dealing with the complexity.
290The 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.
291
292
293\paragraph{T:1 model} where all threads allocate and deallocate objects from one heap.
294Memory is obtained from the freed objects, or reserved memory in the heap, or from the operating system (OS);
295the heap may also return freed memory to the operating system.
296The 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.
297To safely handle concurrency, a single heap uses locking to provide mutual exclusion.
298Whether 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.
299
300\begin{figure}
301\centering
302\subfigure[T:1]{
303%       \input{SingleHeap.pstex_t}
304        \input{SingleHeap}
305        \label{f:SingleHeap}
306} % subfigure
307\vrule
308\subfigure[T:H]{
309%       \input{MultipleHeaps.pstex_t}
310        \input{SharedHeaps}
311        \label{f:SharedHeaps}
312} % subfigure
313\vrule
314\subfigure[1:1]{
315%       \input{MultipleHeapsGlobal.pstex_t}
318} % subfigure
320\end{figure}
321
322
323\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.
324The decision on when to create a new heap and which heap a thread allocates from depends on the allocator design.
325The performance goal is to reduce the ratio of heaps to threads.
326In 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.
327
328For 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.
329At creation, a thread is associated with a heap from the pool.
330In 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.
331If an unlocked heap is found, the thread changes its association and uses that heap.
332If all heaps are locked, the thread may create a new heap, use it, and then place the new heap into the pool;
333or the thread can block waiting for a heap to become available.
334While the heap-pool approach often minimizes the number of extant heaps, the worse case can result in more heaps than threads;
335\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.
336
337Threads using multiple heaps need to determine the specific heap to access for an allocation/deallocation, \ie association of thread to heap.
338A number of techniques are used to establish this association.
339The 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.
340For threading systems with thread-local storage, the heap pointer is created using this mechanism;
341otherwise, 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.
342
343The storage management for multiple heaps is more complex than for a single heap (see \VRef[Figure]{f:AllocatorComponents}).
344\VRef[Figure]{f:MultipleHeapStorage} illustrates the general storage layout for multiple heaps.
345Allocated and free objects are labelled by the thread or heap they are associated with.
346(Links between free objects are removed for simplicity.)
347The management information in the static zone must be able to locate all heaps in the dynamic zone.
348The management information for the heaps must reside in the dynamic-allocation zone if there are a variable number.
349Each heap in the dynamic zone is composed of a list of free objects and a pointer to its reserved memory.
350An 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.
351Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
352Other 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.
353
354\begin{figure}
355\centering
356\input{MultipleHeapsStorage}
357\caption{Multiple-Heap Storage}
358\label{f:MultipleHeapStorage}
359\end{figure}
360
361Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup.
362The 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.
363Additionally, 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.
364Depending 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.
365In 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.
366
367Adding 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.
368Now, each heap obtains and returns storage to/from the global heap rather than the operating system.
369Storage 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.
370Similarly, the global heap buffers this memory, obtaining and returning storage to/from the operating system as necessary.
371The global heap does not have its own thread and makes no internal allocation requests;
372instead, it uses the application thread, which called one of the multiple heaps and then the global heap, to perform operations.
373Hence, the worst-case cost of a memory operation includes all these steps.
374With 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.
375
376However, since any thread may indirectly perform a memory operation on the global heap, it is a shared resource that requires locking.
377A single lock can be used to protect the global heap or fine-grained locking can be used to reduce contention.
378In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap.
379
380
381\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}).
382An additional benefit of thread heaps is improved locality due to better memory layout.
383As 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.
384In contrast, the T:H model spreads each thread's objects over a larger area in different heaps.
385Thread 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.
386For 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.
387Hence, allocator-induced active false-sharing in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing} cannot occur because the memory for thread heaps never overlaps.
388
389When a thread terminates, there are two options for handling its thread heap.
390First is to free all objects in the thread heap to the global heap and destroy the thread heap.
391Second is to place the thread heap on a list of available heaps and reuse it for a new thread in the future.
392Destroying 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.
393Alternatively, 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..
394
395
397
398It is possible to use any of the heap models with user-level (M:N) threading.
399However, 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).
400It is difficult to retain this goal, if the user-threading model is directly involved with the heap model.
401\VRef[Figure]{f:UserLevelKernelHeaps} shows that virtually all user-level threading systems use whatever kernel-level heap-model is provided by the language runtime.
402Hence, a user thread allocates/deallocates from/to the heap of the kernel thread on which it is currently executing.
403
404\begin{figure}
405\centering
406\input{UserKernelHeaps}
407\caption{User-Level Kernel Heaps}
408\label{f:UserLevelKernelHeaps}
409\end{figure}
410
411Adopting this model results in a subtle problem with shared heaps.
412With kernel threading, an operation that is started by a kernel thread is always completed by that thread.
413For 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.
414
415However, this correctness property is not preserved for user-level threading.
416A 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}.
417When 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.
419However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption does not happen that frequently.
420Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it can complete atomically.
421Occasionally ignoring a preemption should be benign, but a persistent lack of preemption can result in both short and long term starvation.
422
423
424\begin{figure}
425\centering
426\subfigure[Ownership]{
427        \input{MultipleHeapsOwnership}
428} % subfigure
429\hspace{0.25in}
430\subfigure[No Ownership]{
431        \input{MultipleHeapsNoOwnership}
432} % subfigure
433\caption{Heap Ownership}
434\label{f:HeapsOwnership}
435\end{figure}
436
437
438\subsection{Ownership}
439\label{s:Ownership}
440
441\newterm{Ownership} defines which heap an object is returned-to on deallocation.
442If a thread returns an object to the heap it was originally allocated from, a heap has ownership of its objects.
443Alternatively, 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.
444\VRef[Figure]{f:HeapsOwnership} shows an example of multiple heaps (minus the global heap) with and without ownership.
445Again, the arrows indicate the direction memory conceptually moves for each kind of operation.
446For 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}.
447For 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}.
448
449\VRef[Figure]{f:MultipleHeapStorageOwnership} shows the effect of ownership on storage layout.
450(For simplicity, assume the heaps all use the same size of reserves storage.)
451In 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.
452Again, because multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
453The 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.
454In 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.
455As 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.
456% Passive false-sharing may still occur, if delayed ownership is used (see below).
457
458\begin{figure}
459\centering
460\input{MultipleHeapsOwnershipStorage.pstex_t}
461\caption{Multiple-Heap Storage with Ownership}
462\label{f:MultipleHeapStorageOwnership}
463\end{figure}
464
465The main advantage of ownership is preventing heap blowup by returning storage for reuse by the owner heap.
466Ownership 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.
467As 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.
468For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, the deallocation by Thread$_2$ returns Object$_2$ back to Thread$_1$'s heap;
469hence a subsequent allocation by Thread$_2$ cannot return this storage.
470The disadvantage of ownership is deallocating to another thread's heap so heaps are no longer private and require locks to provide safe concurrent access.
471
472Object ownership can be immediate or delayed, meaning free objects may be batched on a separate free list either by the returning or receiving thread.
473While 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.
474It 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.
475Batching 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.
476
477It is possible for heaps to steal objects rather than return them and then reallocate these objects again when storage runs out on a heap.
478However, stealing can result in passive false-sharing.
479For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Thread$_2$'s heap initially.
480If Thread$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.
481
482
483\section{Object Containers}
484\label{s:ObjectContainers}
485
486Bracketing every allocation with headers/trailers can result in significant internal fragmentation, as shown in \VRef[Figure]{f:ObjectHeaders}.
487Especially 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.
488As 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.
489Spatial locality can also be negatively affected leading to poor cache locality~\cite{Feng05}:
490while the header and object are together in memory, they are generally not accessed together;
491\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.
492
493\begin{figure}
494\centering
498} % subfigure
499\subfigure[Object Container]{
500        \input{Container}
501        \label{f:ObjectContainer}
502} % subfigure
505\end{figure}
506
507An 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}.
508The header for the container holds information necessary for all objects in the container;
509a trailer may also be used at the end of the container.
510Similar 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.
511
512The 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.
513One 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).
514For 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.
515
516Normally, 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).
517This 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.
518However, although similar objects are close spatially within the same container, different sized objects are further apart in separate containers.
519Depending on the program, this may or may not improve locality.
520If 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.
521If the program uses many containers, there is poor locality, as both caching and paging increase.
522Another 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.
523However, external fragmentation can be reduced by using small containers.
524
525Containers with heterogeneous objects implies different headers describing them, which complicates the problem of locating a specific header solely by an address.
526A couple of solutions can be used to implement containers with heterogeneous objects.
527However, the problem with allowing objects of different sizes is that the number of objects, and therefore headers, in a single container is unpredictable.
528One solution allocates headers at one end of the container, while allocating objects from the other end of the container;
529when the headers meet the objects, the container is full.
530Freed objects cannot be split or coalesced since this causes the number of headers to change.
531The difficulty in this strategy remains in finding the header for a specific object;
532in general, a search is necessary to find the object's header among the container headers.
533A second solution combines the use of container headers and individual object headers.
534Each 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.
535This approach allows containers to hold different types of objects, but does not completely separate headers from objects.
536The benefit of the container in this case is to reduce some redundant information that is factored into the container header.
537
538In 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.
539A consequence of this tradeoff is its effect on spatial locality, which can produce positive or negative results depending on program access-patterns.
540
541
542\subsection{Container Ownership}
543\label{s:ContainerOwnership}
544
545Without ownership, objects in a container are deallocated to the heap currently associated with the thread that frees the object.
546Thus, different objects in a container may be on different heap free-lists (see \VRef[Figure]{f:ContainerNoOwnershipFreelist}).
547With 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.
548If multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
549Only with the 1:1 model and ownership is active and passive false-sharing avoided (see \VRef{s:Ownership}).
550Passive false-sharing may still occur, if delayed ownership is used.
551Finally, a completely free container can become reserved storage and be reset to allocate objects of a new size or freed to the global heap.
552
553\begin{figure}
554\centering
555\subfigure[No Ownership]{
556        \input{ContainerNoOwnershipFreelist}
557        \label{f:ContainerNoOwnershipFreelist}
558} % subfigure
559\vrule
560\subfigure[Ownership]{
561        \input{ContainerOwnershipFreelist}
562        \label{f:ContainerOwnershipFreelist}
563} % subfigure
564\caption{Free-list Structure with Container Ownership}
565\end{figure}
566
567When a container changes ownership, the ownership of all objects within it change as well.
568Moving a container involves moving all objects on the heap's free-list in that container to the new owner.
569This approach can reduce contention for the global heap, since each request for objects from the global heap returns a container rather than individual objects.
570
571Additional restrictions may be applied to the movement of containers to prevent active false-sharing.
572For example, in \VRef[Figure]{f:ContainerFalseSharing1}, a container being used by Thread$_1$ changes ownership, through the global heap.
573In \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.
574Note, once the object is freed by Thread$_1$, no more false sharing can occur until the container changes ownership again.
575To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free.
576One 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.
577
578\begin{figure}
579\centering
580\subfigure[]{
581        \input{ContainerFalseSharing1}
582        \label{f:ContainerFalseSharing1}
583} % subfigure
584\subfigure[]{
585        \input{ContainerFalseSharing2}
586        \label{f:ContainerFalseSharing2}
587} % subfigure
588\caption{Active False-Sharing using Containers}
589\label{f:ActiveFalseSharingContainers}
590\end{figure}
591
592Using containers with ownership increases external fragmentation since a new container for a requested object size must be allocated separately for each thread requesting it.
593In \VRef[Figure]{f:ExternalFragmentationContainerOwnership}, using object ownership allocates 80\% more space than without ownership.
594
595\begin{figure}
596\centering
597\subfigure[No Ownership]{
598        \input{ContainerNoOwnership}
599} % subfigure
600\\
601\subfigure[Ownership]{
602        \input{ContainerOwnership}
603} % subfigure
604\caption{External Fragmentation with Container Ownership}
605\label{f:ExternalFragmentationContainerOwnership}
606\end{figure}
607
608
609\subsection{Container Size}
610\label{s:ContainerSize}
611
612One 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.
613As 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).
614Aligning containers in this manner also determines the size of the container.
615However, the size of the container has different implications for the allocator.
616
617The 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.
618However, with more objects in a container, there may be more objects that are unallocated, increasing external fragmentation.
619With smaller containers, not only are there more containers, but a second new problem arises where objects are larger than the container.
620In 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.
621If 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.
622Ideally, 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.
623
624In order to find the container header when using different sized containers, a super container is used (see~\VRef[Figure]{f:SuperContainers}).
625The super container spans several containers, contains a header with information for finding each container header, and starts on an aligned address.
626Super-container headers are found using the same method used to find container headers by dropping the lower bits of an object address.
627The containers within a super container may be different sizes or all the same size.
628If 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.
629If all containers in the super container are the same size, \eg 16KB, then a specific container header can be found by a simple calculation.
630The free space at the end of a super container is used to allocate new containers.
631
632\begin{figure}
633\centering
634\input{SuperContainers}
635% \includegraphics{diagrams/supercontainer.eps}
636\caption{Super Containers}
637\label{f:SuperContainers}
638\end{figure}
639
640Minimal internal and external fragmentation is achieved by having as few containers as possible, each being as full as possible.
641It 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.
642However, this approach assumes it is possible for an allocator to determine in advance which sizes are popular.
643Keeping statistics on requested sizes allows the allocator to make a dynamic decision about which sizes are popular.
644For 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.
645If the decision is incorrect, larger containers than necessary are allocated that remain mostly unused.
646A 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.
647
648
649\subsection{Container Free-Lists}
650\label{s:containersfreelists}
651
652The container header allows an alternate approach for managing the heap's free-list.
653Rather 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}).
654Note, maintaining free lists within a container assumes all free objects in the container are associated with the same heap;
655thus, this approach only applies to containers with ownership.
656
657This alternate free-list approach can greatly reduce the complexity of moving all freed objects belonging to a container to another heap.
658To 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.
659Each object is then removed from the free list and linked together to form a local free-list for the move to the new heap.
660With 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.
661Thus, when using local free-lists, the operation of moving containers is reduced from $O(N)$ to $O(1)$.
662However, there is the additional storage cost in the header, which increases the header size, and therefore internal fragmentation.
663
664\begin{figure}
665\centering
666\subfigure[Global Free-List Among Containers]{
667        \input{FreeListAmongContainers}
668        \label{f:GlobalFreeListAmongContainers}
669} % subfigure
670\hspace{0.25in}
671\subfigure[Local Free-List Within Containers]{
672        \input{FreeListWithinContainers}
673        \label{f:LocalFreeListWithinContainers}
674} % subfigure
675\caption{Container Free-List Structure}
676\label{f:ContainerFreeListStructure}
677\end{figure}
678
679When all objects in the container are the same size, a single free-list is sufficient.
680However, 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.
681The alternative is to use a different allocation algorithm with a single free-list, such as a sequential-fit allocation-algorithm.
682
683
684\subsection{Hybrid Private/Public Heap}
685\label{s:HybridPrivatePublicHeap}
686
687Section~\Vref{s:Ownership} discusses advantages and disadvantages of public heaps (T:H model and with ownership) and private heaps (thread heaps with ownership).
688For 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}).
689The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
690In 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.
691Similarly, a thread first deallocates an object to its private heap, and second to the public heap.
692Both 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.
693Note, 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.
694Finally, 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.
695
696\begin{figure}
697\centering
698\input{PrivatePublicHeaps.pstex_t}
699\caption{Hybrid Private/Public Heap for Per-thread Heaps}
700\label{f:HybridPrivatePublicHeap}
701% \vspace{10pt}
702% \input{RemoteFreeList.pstex_t}
703% \caption{Remote Free-List}
704% \label{f:RemoteFreeList}
705\end{figure}
706
707As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified.
708For 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}.
709To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
710Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
711Clearing 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.
712
713If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
714In 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.
715If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.
716
717The 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.
718Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
719In 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.
720For 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.
721
722
723\section{Allocation Buffer}
724\label{s:AllocationBuffer}
725
726An 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.
727That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
728Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or operating system, respectively.
729The allocation buffer reduces contention and the number of global/operating-system calls.
730For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.
731
732Allocation 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).
733Furthermore, to prevent heap blowup, objects should be reused before allocating a new allocation buffer.
734Thus, allocation buffers are often allocated more frequently at program/thread start, and then allocations often diminish.
735
736Using an allocation buffer with a thread heap avoids active false-sharing, since all objects in the allocation buffer are allocated to the same thread.
737For 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.
738Active false-sharing may still occur if objects are freed to the global heap and reused by another heap.
739
740Allocation buffers may increase external fragmentation, since some memory in the allocation buffer may never be allocated.
741A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or operating system.
742The allocation buffer also slightly increases internal fragmentation, since a pointer is necessary to locate the next free object in the buffer.
743
744The unused part of a container, neither allocated or freed, is an allocation buffer.
745For 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.
746This lazy method of constructing objects is beneficial in terms of paging and caching.
747For 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.
748
749
750\section{Lock-Free Operations}
751\label{s:LockFreeOperations}
752
753A \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}.
754(A \newterm{wait-free algorithm} puts a bound on the number of steps any thread takes to complete an operation to prevent starvation.)
755Lock-free operations can be used in an allocator to reduce or eliminate the use of locks.
756While 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.
757With 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.
758Nevertheless, lock-free algorithms can reduce the number of context switches, since a thread does not yield/block while waiting for a lock;
759on the other hand, a thread may busy-wait for an unbounded period holding a processor.
760Finally, lock-free implementations have greater complexity and hardware dependency.
761Lock-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.
762Implementing lock-free operations for more complex data-structures (queue~\cite{Valois94}/deque~\cite{Sundell08}) is correspondingly more complex.
763Michael~\cite{Michael04} and Gidenstam \etal \cite{Gidenstam05} have created lock-free variations of the Hoard allocator.
764
765