source: doc/theses/mubeen_zulfiqar_MMath/background.tex @ a114743

Last change on this file since a114743 was a114743, checked in by Peter A. Buhr <pabuhr@…>, 2 years ago

proofread intro and background chapters

  • Property mode set to 100644
File size: 57.3 KB
3Writing Points:
6Classification of benchmarks.
8Literature review of current benchmarks.
10Features and limitations.
12Literature review of current memory allocators.
14Breakdown of memory allocation techniques.
16Features and limitations.
20\chapter[Background]{Background\footnote{Part of this chapter draws from similar background work in~\cite{wasik.thesis} with many updates.}}
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.
31\section{Allocator Components}
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 (white) are variable sized, and allocated and maintained by the program;
39\ie only the program knows the location of allocated storage, not the memory allocator.
43\caption{Allocator Components (Heap)}
46Freed objects (light grey) 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.
51Allocated and freed objects typically 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.
53The header contains information about the object, \eg size, type, etc.
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 resulting in additional spacing after objects less than the quantized value.
57When padding and spacing are necessary, neither can be used to satisfy a future allocation request while the current allocation exists.
58A free object also contains management data, \eg size, chaining, etc.
59The 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.
60The 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.
65\caption{Allocated Object}
70\section{Single-Threaded Memory-Allocator}
73A single-threaded memory-allocator does not run any threads itself, but is used by a single-threaded program.
74Because the memory allocator is only executed by a single thread, concurrency issues do not exist.
75The primary issues in designing a single-threaded memory-allocator are fragmentation and locality.
81Fragmentation is memory requested from the operating system but not used by the program;
82hence, allocated objects are not fragmentation.
83\VRef[Figure]{f:InternalExternalFragmentation} shows fragmentation is divided into two forms: internal or external.
88\caption{Internal and External Fragmentation}
92\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.
93This memory is typically used by the allocator for management purposes or required by the architecture for correctness, \eg alignment.
94Internal fragmentation is problematic when management space is a significant proportion of an allocated object.
95For example, if internal fragmentation is as large as the object being managed, then the memory usage for that object is doubled.
96An allocator should strive to keep internal management information to a minimum.
98\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.
99This memory is problematic in two ways: heap blowup and highly fragmented memory.
100\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}.
101Heap blowup can occur due to allocator policies that are too restrictive in reusing freed memory and/or no coalescing of free storage.
102Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects.
103\VRef[Figure]{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time.
104Blocks of free memory become smaller and non-contiguous making them less useful in serving allocation requests.
105Memory is highly fragmented when the sizes of most free blocks are unusable.
106For 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.
107If 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.
112\caption{Memory Fragmentation}
116        \input{ContigFragmentation}
117        \label{f:Contiguous}
118} % subfigure
119        \subfigure[Highly Fragmented]{
120        \input{NonContigFragmentation}
122} % subfigure
123\caption{Fragmentation Quality}
127For a single-threaded memory allocator, three basic approaches for controlling fragmentation are identified~\cite{Johnstone99}.
128The 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.
129Different search policies determine the free object selected, \eg the first free object large enough or closest to the requested size.
130Any storage larger than the request can become spacing after the object or be split into a smaller free object.
131The 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.
133The second approach is a \newterm{segregated} or \newterm{binning algorithm} with a set of lists for different sized freed objects.
134When an object is allocated, the requested size is rounded up to the nearest bin-size, often leading to spacing after the object.
135A 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.
136The fewer bin-sizes, the fewer lists need to be searched and maintained;
137however, the bin sizes are less likely to closely fit the requested object size, leading to more internal fragmentation.
138The 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.
139A 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.
140For 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.
141For 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.
143The third approach is \newterm{splitting} and \newterm{coalescing algorithms}.
144When 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.
145For 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.
146When 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.
147Coalescing can be done eagerly at each deallocation or lazily when an allocation cannot be fulfilled.
148In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays during coalescing.
149While coalescing does not reduce external fragmentation, the coalesced blocks improve fragmentation quality so future allocations are less likely to cause heap blowup.
150Splitting and coalescing can be used with other algorithms to avoid highly fragmented memory.
156The 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}.
157Temporal 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.
158Temporal locality commonly occurs during an iterative computation with a fix set of disjoint variables, while spatial locality commonly occurs when traversing an array.
160Hardware takes advantage of temporal and spatial locality through multiple levels of caching, \ie memory hierarchy.
161When 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.
162For example, entire cache lines are transferred between memory and cache and entire virtual-memory pages are transferred between disk and memory.
163A 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.}.
165Temporal locality is largely controlled by how a program accesses its variables~\cite{Feng05}.
166Nevertheless, a memory allocator can have some indirect influence on temporal locality and largely dictates spatial locality.
167For 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.
168For 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.
169However, usage patterns are different for every program as is the underlying hardware memory architecture;
170hence, no general-purpose memory-allocator can provide ideal locality for every program on every computer.
172There are a number of ways a memory allocator can degrade locality by increasing the working set.
173For example, a memory allocator may access multiple free objects before finding one to satisfy an allocation request, \eg sequential-fit algorithm.
174If 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}.
175Another way locality can be degraded is by spatially separating related data.
176For example, in a binning allocator, objects of different sizes are allocated from different bins that may be located in different pages of memory.
179\section{Multi-Threaded Memory-Allocator}
182A multi-threaded memory-allocator does not run any threads itself, but is used by a multi-threaded program.
183In 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.
186\subsection{Mutual Exclusion}
189\newterm{Mutual exclusion} provides sequential access to the shared management data of the heap.
190There are two performance issues for mutual exclusion.
191First is the overhead necessary to perform (at least) a hardware atomic operation every time a shared resource is accessed.
192Second is when multiple threads contend for a shared resource simultaneously, and hence, some threads must wait until the resource is released.
193Contention can be reduced in a number of ways:
196using multiple fine-grained locks versus a single lock, spreading the contention across a number of locks;
198using trylock and generating new storage if the lock is busy, yielding a classic space versus time tradeoff;
200using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Oyama99}.
202However, all of these approaches have degenerate cases where program contention is high, which occurs outside of the allocator.
205\subsection{False Sharing}
208False sharing is a dynamic phenomenon leading to cache thrashing.
209When 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.
210False sharing can occur in three different ways: program induced, allocator-induced active, and allocator-induced passive;
211a memory allocator can only affect the latter two.
213\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.
214\VRef[Figure]{f:ProgramInducedFalseSharing} shows when Task$_1$ passes Object$_2$ to Task$_2$, a false-sharing situation forms when Task$_1$ modifies Object$_1$ and Task$_2$ modifies Object$_2$.
215Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
219\subfigure[Program-Induced False-Sharing]{
220        \input{ProgramFalseSharing}
221        \label{f:ProgramInducedFalseSharing}
222} \\
224\subfigure[Allocator-Induced Active False-Sharing]{
225        \input{AllocInducedActiveFalseSharing}
226        \label{f:AllocatorInducedActiveFalseSharing}
227} \\
229\subfigure[Allocator-Induced Passive False-Sharing]{
230        \input{AllocInducedPassiveFalseSharing}
231        \label{f:AllocatorInducedPassiveFalseSharing}
232} % subfigure
233\caption{False Sharing}
237\paragraph{\newterm{Allocator-induced active false-sharing}} occurs when objects are allocated within the same cache line but to different threads.
238For example, in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}, each task allocates an object and loads a cache-line of memory into its associated cache.
239Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
241\paragraph{\newterm{Allocator-induced passive false-sharing}} is another form of allocator-induced false-sharing caused by program-induced false-sharing.
242When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing.
243For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Task$_1$ passes Object$_2$ to Task$_2$, and Task$_2$ subsequently deallocates Object$_2$.
244Allocator-induced passive false-sharing occurs when Object$_2$ is reallocated to Task$_2$ while Task$_1$ is still using Object$_1$.
247\subsection{Heap Blowup}
250In a multi-threaded program, heap blowup can occur when memory freed by one thread is inaccessible to other threads due to the allocation strategy.
251Specific examples are presented in later sections.
254\section{Multi-Threaded Memory-Allocator Features}
257The following features are used in the construction of multi-threaded memory-allocators:
259\item multiple heaps
261\item with or without a global heap
262\item with or without ownership
264\item object containers
266\item with or without ownership
267\item fixed or variable sized
268\item global or local free-lists
270\item hybrid private/public heap
271\item allocation buffer
272\item lock-free operations
274The first feature, multiple heaps, pertains to different kinds of heaps.
275The second feature, object containers, pertains to the organization of objects within the storage area.
276The remaining features apply to different parts of the allocator design or implementation.
279\section{Multiple Heaps}
282A multi-threaded allocator has potentially multiple threads and heaps.
283The multiple threads cause complexity, and multiple heaps are a mechanism for dealing with the complexity.
284The 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.
287\paragraph{T:1 model} where all threads allocate and deallocate objects from one heap.
288Memory is obtained from the freed objects, or reserved memory in the heap, or from the operating system (OS);
289the heap may also return freed memory to the operating system.
290The 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.
291To safely handle concurrency, a single heap uses locking to provide mutual exclusion.
292Whether 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.
297%       \input{SingleHeap.pstex_t}
298        \input{SingleHeap}
299        \label{f:SingleHeap}
300} % subfigure
303%       \input{MultipleHeaps.pstex_t}
304        \input{SharedHeaps}
305        \label{f:SharedHeaps}
306} % subfigure
309%       \input{MultipleHeapsGlobal.pstex_t}
310        \input{PerThreadHeap}
311        \label{f:PerThreadHeap}
312} % subfigure
313\caption{Multiple Heaps, Thread:Heap Relationship}
317\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.
318The decision on when to create a new heap and which heap a thread allocates from depends on the allocator design.
319The performance goal is to reduce the ratio of heaps to threads.
320In 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.
322For 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.
323At creation, a thread is associated with a heap from the pool.
324When the thread attempts an allocation and its associated heap is locked (contention), it scans for an unlocked heap in the pool.
325If an unlocked heap is found, the thread changes its association and uses that heap.
326If all heaps are locked, the thread may create a new heap, use it, and then place the new heap into the pool;
327or the thread can block waiting for a heap to become available.
328While the heap-pool approach often minimizes the number of extant heaps, the worse case can result in more heaps than threads;
329\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.
331Threads using multiple heaps need to determine the specific heap to access for an allocation/deallocation, \ie association of thread to heap.
332A number of techniques are used to establish this association.
333The 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.
334For threading systems with thread-local storage, the heap pointer is created using this mechanism;
335otherwise, 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.
337The storage management for multiple heaps is more complex than for a single heap (see \VRef[Figure]{f:AllocatorComponents}).
338\VRef[Figure]{f:MultipleHeapStorage} illustrates the general storage layout for multiple heaps.
339Allocated and free objects are labelled by the thread or heap they are associated with.
340(Links between free objects are removed for simplicity.)
341The management information in the static zone must be able to locate all heaps in the dynamic zone.
342The management information for the heaps must reside in the dynamic-allocation zone if there are a variable number.
343Each heap in the dynamic zone is composed of a list of a free objects and a pointer to its reserved memory.
344An 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.
345Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
346Other 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.
351\caption{Multiple-Heap Storage}
355Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup.
356The 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.
357Additionally, objects freed by one heap cannot be reused by other threads, except indirectly by returning free memory to the operating system, which can be expensive.
358(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.)
359In 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.
361Adding 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.
362Now, each heap obtains and returns storage to/from the global heap rather than the operating system.
363Storage 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.
364Similarly, the global heap buffers this memory, obtaining and returning storage to/from the operating system as necessary.
365The global heap does not have its own thread and makes no internal allocation requests;
366instead, it uses the application thread, which called one of the multiple heaps and then the global heap, to perform operations.
367Hence, the worst-case cost of a memory operation includes all these steps.
368With 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.
370However, since any thread may indirectly perform a memory operation on the global heap, it is a shared resource that requires locking.
371A single lock can be used to protect the global heap or fine-grained locking can be used to reduce contention.
372In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap.
375\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}).
376An additional benefit of thread heaps is improved locality due to better memory layout.
377As 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.
378In contrast, the T:H model spreads each thread's objects over a larger area in different heaps.
379Thread 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.
380For example, assume page boundaries coincide with cache line boundaries, then if a thread heap always acquires pages of memory, no two threads share a page or cache line unless pointers are passed among them.
381Hence, allocator-induced active false-sharing in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing} cannot occur because the memory for thread heaps never overlaps.
383When a thread terminates, there are two options for handling its heap.
384First is to free all objects in the heap to the global heap and destroy the thread heap.
385Second is to place the thread heap on a list of available heaps and reuse it for a new thread in the future.
386Destroying 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.
387Alternatively, 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..
390\subsection{User-Level Threading}
392It is possible to use any of the heap models with user-level (M:N) threading.
393However, 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).
394It is difficult to retain this goal, if the user-threading model is directly involved with the heap model.
395\VRef[Figure]{f:UserLevelKernelHeaps} shows that virtually all user-level threading systems use whatever kernel-level heap-model is provided by the language runtime.
396Hence, a user thread allocates/deallocates from/to the heap of the kernel thread on which it is currently executing.
401\caption{User-Level Kernel Heaps}
405Adopting this model results in a subtle problem with shared heaps.
406With kernel threading, an operation that is started by a kernel thread is always completed by that thread.
407For 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.
409However, this correctness property is not preserved for user-level threading.
410A 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}.
411When 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.
412To 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.
413However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption is rare (10--100 milliseconds).
414Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it can complete atomically.
415Occasionally ignoring a preemption should be benign, but a persistent lack of preemption can result in both short and long term starvation.
421        \input{MultipleHeapsOwnership}
422} % subfigure
424\subfigure[No Ownership]{
425        \input{MultipleHeapsNoOwnership}
426} % subfigure
427\caption{Heap Ownership}
435\newterm{Ownership} defines which heap an object is returned-to on deallocation.
436If a thread returns an object to the heap it was originally allocated from, a heap has ownership of its objects.
437Alternatively, 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.
438\VRef[Figure]{f:HeapsOwnership} shows an example of multiple heaps (minus the global heap) with and without ownership.
439Again, the arrows indicate the direction memory conceptually moves for each kind of operation.
440For 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}.
441For 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}.
443\VRef[Figure]{f:MultipleHeapStorageOwnership} shows the effect of ownership on storage layout.
444(For simplicity assume the heaps all use the same size of reserves storage.)
445In 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.
446Again, because multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
447The 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.
448In 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.
449As 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.
450% Passive false-sharing may still occur, if delayed ownership is used (see below).
455\caption{Multiple-Heap Storage with Ownership}
459The main advantage of ownership is preventing heap blowup by returning storage for reuse by the owner heap.
460Ownership 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.
461As 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.
462For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, the deallocation by Task$_2$ returns Object$_2$ back to Task$_1$'s heap;
463hence a subsequent allocation by Task$_2$ cannot return this storage.
464The disadvantage of ownership is deallocating to another task's heap so heaps are no longer private and require locks to provide safe concurrent access.
466Object ownership can be immediate or delayed, meaning free objects may be batched on a separate free list either by the returning or receiving thread.
467While 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.
468It 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.
469Batching 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.
471It is possible for heaps to steal objects rather than return them and reallocating these objects when storage runs out on a heap.
472However, stealing can result in passive false-sharing.
473For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Task$_2$'s heap initially.
474If Task$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.
477\section{Object Containers}
480Bracketing every allocation with headers/trailers can result in significant internal fragmentation, as shown in \VRef[Figure]{f:ObjectHeaders}.
481Especially if the headers contain redundant management information, \eg object size may be the same for many objects because programs only allocate a small set of object sizes.
482As 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.
483Spatial locality can also be negatively affected leading to poor cache locality~\cite{Feng05}:
484while the header and object are together in memory, they are generally not accessed together;
485\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.
489\subfigure[Object Headers]{
490        \input{ObjectHeaders}
491        \label{f:ObjectHeaders}
492} % subfigure
493\subfigure[Object Container]{
494        \input{Container}
495        \label{f:ObjectContainer}
496} % subfigure
497\caption{Header Placement}
501An 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}.
502The header for the container holds information necessary for all objects in the container;
503a trailer may also be used at the end of the container.
504Similar 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.
506The 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.
507One 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).
508For 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.
510Normally, 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).
511This 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.
512However, although similar objects are close spatially within the same container, different sized objects are further apart in separate containers.
513Depending on the program, this may or may not improve locality.
514If 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.
515If the program uses many containers, there is poor locality, as both caching and paging increase.
516Another 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.
517However, external fragmentation can be reduced by using small containers.
519Containers with heterogeneous objects implies different headers describing them, which complicates the problem of locating a specific header solely by an address.
520A couple of solutions can be used to implement containers with heterogeneous objects.
521However, the problem with allowing objects of different sizes is that the number of objects, and therefore headers, in a single container is unpredictable.
522One solution allocates headers at one end of the container, while allocating objects from the other end of the container;
523when the headers meet the objects, the container is full.
524Freed objects cannot be split or coalesced since this causes the number of headers to change.
525The difficulty in this strategy remains in finding the header for a specific object;
526in general, a search is necessary to find the object's header among the container headers.
527A second solution combines the use of container headers and individual object headers.
528Each 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.
529This approach allows containers to hold different types of objects, but does not completely separate headers from objects.
530The benefit of the container in this case is to reduce some redundant information that is factored into the container header.
532In 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.
533A consequence of this tradeoff is its effect on spatial locality, which can produce positive or negative results depending on program access-patterns.
536\subsection{Container Ownership}
539Without ownership, objects in a container are deallocated to the heap currently associated with the thread that frees the object.
540Thus, different objects in a container may be on different heap free-lists (see \VRef[Figure]{f:ContainerNoOwnershipFreelist}).
541With 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.
542If multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
543Only with the 1:1 model and ownership is active and passive false-sharing avoided (see \VRef{s:Ownership}).
544Passive false-sharing may still occur, if delayed ownership is used.
545Finally, a completely free container can become reserved storage and be reset to allocate objects of a new size or freed to the global heap.
549\subfigure[No Ownership]{
550        \input{ContainerNoOwnershipFreelist}
551        \label{f:ContainerNoOwnershipFreelist}
552} % subfigure
555        \input{ContainerOwnershipFreelist}
556        \label{f:ContainerOwnershipFreelist}
557} % subfigure
558\caption{Free-list Structure with Container Ownership}
561When a container changes ownership, the ownership of all objects within it change as well.
562Moving a container involves moving all objects on the heap's free-list in that container to the new owner.
563This approach can reduce contention for the global heap, since each request for objects from the global heap returns a container rather than individual objects.
565Additional restrictions may be applied to the movement of containers to prevent active false-sharing.
566For example, in \VRef[Figure]{f:ContainerFalseSharing1}, a container being used by Task$_1$ changes ownership, through the global heap.
567In \VRef[Figure]{f:ContainerFalseSharing2}, when Task$_2$ allocates an object from the newly acquired container it is actively false-sharing even though no objects are passed among threads.
568Note, once the object is freed by Task$_1$, no more false sharing can occur until the container changes ownership again.
569To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free.
570One 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.
575        \input{ContainerFalseSharing1}
576        \label{f:ContainerFalseSharing1}
577} % subfigure
579        \input{ContainerFalseSharing2}
580        \label{f:ContainerFalseSharing2}
581} % subfigure
582\caption{Active False-Sharing using Containers}
586Using containers with ownership increases external fragmentation since a new container for a requested object size must be allocated separately for each thread requesting it.
587In \VRef[Figure]{f:ExternalFragmentationContainerOwnership}, using object ownership allocates 80\% more space than without ownership.
591\subfigure[No Ownership]{
592        \input{ContainerNoOwnership}
593} % subfigure
596        \input{ContainerOwnership}
597} % subfigure
598\caption{External Fragmentation with Container Ownership}
603\subsection{Container Size}
606One 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.
607As 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).
608Aligning containers in this manner also determines the size of the container.
609However, the size of the container has different implications for the allocator.
611The 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.
612However, with more objects in a container, there may be more objects that are unallocated, increasing external fragmentation.
613With smaller containers, not only are there more containers, but a second new problem arises where objects are larger than the container.
614In 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.
615If 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.
616Ideally, 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.
618In order to find the container header when using different sized containers, a super container is used (see~\VRef[Figure]{f:SuperContainers}).
619The super container spans several containers, contains a header with information for finding each container header, and starts on an aligned address.
620Super-container headers are found using the same method used to find container headers by dropping the lower bits of an object address.
621The containers within a super container may be different sizes or all the same size.
622If 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.
623If all containers in the super container are the same size, \eg 16KB, then a specific container header can be found by a simple calculation.
624The free space at the end of a super container is used to allocate new containers.
629% \includegraphics{diagrams/supercontainer.eps}
630\caption{Super Containers}
634Minimal internal and external fragmentation is achieved by having as few containers as possible, each being as full as possible.
635It 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.
636However, this approach assumes it is possible for an allocator to determine in advance which sizes are popular.
637Keeping statistics on requested sizes allows the allocator to make a dynamic decision about which sizes are popular.
638For 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.
639If the decision is incorrect, larger containers than necessary are allocated that remain mostly unused.
640A 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.
643\subsection{Container Free-Lists}
646The container header allows an alternate approach for managing the heap's free-list.
647Rather 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}).
648Note, maintaining free lists within a container assumes all free objects in the container are associated with the same heap;
649thus, this approach only applies to containers with ownership.
651This alternate free-list approach can greatly reduce the complexity of moving all freed objects belonging to a container to another heap.
652To 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.
653Each object is then removed from the free list and linked together to form a local free-list for the move to the new heap.
654With 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.
655Thus, when using local free-lists, the operation of moving containers is reduced from $O(N)$ to $O(1)$.
656The cost is adding information to a header, which increases the header size, and therefore internal fragmentation.
660\subfigure[Global Free-List Among Containers]{
661        \input{FreeListAmongContainers}
662        \label{f:GlobalFreeListAmongContainers}
663} % subfigure
665\subfigure[Local Free-List Within Containers]{
666        \input{FreeListWithinContainers}
667        \label{f:LocalFreeListWithinContainers}
668} % subfigure
669\caption{Container Free-List Structure}
673When all objects in the container are the same size, a single free-list is sufficient.
674However, 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.
675The alternative is to use a different allocation algorithm with a single free-list, such as a sequential-fit allocation-algorithm.
678\subsection{Hybrid Private/Public Heap}
681Section~\Vref{s:Ownership} discusses advantages and disadvantages of public heaps (T:H model and with ownership) and private heaps (thread heaps with ownership).
682For 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}).
683The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
684In the hybrid approach, a task first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
685Similarly, a task first deallocates an object its private heap, and second to the public heap.
686Both 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.
687Note, 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.
688Finally, when a task frees an object it does not own, the object is either freed immediately to its owner's public heap or put in the freeing task's private heap for delayed ownership, which allows the freeing task to temporarily reuse an object before returning it to its owner or batch objects for an owner heap into a single return.
693\caption{Hybrid Private/Public Heap for Per-thread Heaps}
695% \vspace{10pt}
696% \input{RemoteFreeList.pstex_t}
697% \caption{Remote Free-List}
698% \label{f:RemoteFreeList}
701As mentioned, an implementation may have only one heap interact with the global heap, so the other heap can be simplified.
702For 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}.
703To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
704Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
705Clearing 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.
707If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
708In 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.
709If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.
711The 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.
712Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
713In 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.
714For 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.
717\section{Allocation Buffer}
720An 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.
721That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
722Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or operating system, respectively.
723The allocation buffer reduces contention and the number of global/operating-system calls.
724For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.
726Allocation 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).
727Furthermore, to prevent heap blowup, objects should be reused before allocating a new allocation buffer.
728Thus, allocation buffers are often allocated more frequently at program/thread start, and then allocations often diminish.
730Using an allocation buffer with a thread heap avoids active false-sharing, since all objects in the allocation buffer are allocated to the same thread.
731For 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.
732Active false-sharing may still occur if objects are freed to the global heap and reused by another heap.
734Allocation buffers may increase external fragmentation, since some memory in the allocation buffer may never be allocated.
735A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or operating system.
736The allocation buffer also slightly increases internal fragmentation, since a pointer is necessary to locate the next free object in the buffer.
738The unused part of a container, neither allocated or freed, is an allocation buffer.
739For 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.
740This lazy method of constructing objects is beneficial in terms of paging and caching.
741For 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.
744\section{Lock-Free Operations}
747A \newterm{lock-free algorithm} guarantees safe concurrent-access to a data structure, so that at least one thread makes progress, but an individual task has no execution bound and may starve~\cite[pp.~745--746]{Herlihy93}.
748(A \newterm{wait-free algorithm} puts a bound on the number of steps any thread takes to complete an operation to prevent starvation.)
749Lock-free operations can be used in an allocator to reduce or eliminate the use of locks.
750While 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.
751With 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.
752Nevertheless, lock-free algorithms can reduce the number of context switches, since a thread does not yield/block while waiting for a lock;
753on the other hand, a thread may busy-wait for an unbounded period holding a processor.
754Finally, lock-free implementations have greater complexity and hardware dependency.
755Lock-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.
756Implementing lock-free operations for more complex data-structures (queue~\cite{Valois94}/deque~\cite{Sundell08}) is correspondinglyy more complex.
757Michael~\cite{Michael04} and Gidenstam \etal \cite{Gidenstam05} have created lock-free variations of the Hoard allocator.
Note: See TracBrowser for help on using the repository browser.