Index: doc/theses/mubeen_zulfiqar_MMath/allocator.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/allocator.tex (revision 25fa20aa59f67f5f840b43d7ba80ed7c6eae1da3) +++ doc/theses/mubeen_zulfiqar_MMath/allocator.tex (revision fb6691a550a10fe54f856d0e8db4621a98a991f8) @@ -109,5 +109,5 @@ Need to prevent preemption during a dynamic memory operation because of the \newterm{serially-reusable problem}. \begin{quote} -A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable} +A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable} \end{quote} If a KT is preempted during an allocation operation, the operating system can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness. @@ -138,5 +138,5 @@ (See \VRef[Figure]{f:THSharedHeaps} but with a heap bucket per KT and no bucket or local-pool lock.) Hence, immediately after a KT starts, its heap is created and just before a KT terminates, its heap is (logically) deleted. -\PAB{Heaps are uncontended for a KTs memory operations as every KT has its own thread-local heap which is not shared with any other KT (modulo operations on the global pool and ownership).} +Heaps are uncontended for a KTs memory operations as every KT has its own thread-local heap, modulo operations on the global pool and ownership. Problems: @@ -269,5 +269,5 @@ Each heap uses segregated free-buckets that have free objects distributed across 91 different sizes from 16 to 4M. -\PAB{All objects in a bucket are of the same size.} +All objects in a bucket are of the same size. The number of buckets used is determined dynamically depending on the crossover point from @sbrk@ to @mmap@ allocation using @mallopt( M_MMAP_THRESHOLD )@, \ie small objects managed by the program and large objects managed by the operating system. Each free bucket of a specific size has the following two lists: @@ -401,5 +401,5 @@ \end{center} The storage between @E@ and @H@ is chained onto the appropriate free list for future allocations. -\PAB{The same approach is used for sufficiently large free blocks}, where @E@ is the start of the free block, and any unused storage before @H@ or after the allocated object becomes free storage. +The same approach is used for sufficiently large free blocks, where @E@ is the start of the free block, and any unused storage before @H@ or after the allocated object becomes free storage. In this approach, the aligned address @A@ is the same as the allocated storage address @P@, \ie @P@ $=$ @A@ for all allocation routines, which simplifies deallocation. However, if there are a large number of aligned requests, this approach leads to memory fragmentation from the small free areas around the aligned object. @@ -488,5 +488,5 @@ \end{description} The second field remembers the request size versus the allocation (bucket) size, \eg request 42 bytes which is rounded up to 64 bytes. -\PAB{Since programmers think in request sizes rather than allocation sizes, the request size allows better generation of statistics or errors and also helps in memory management.} +Since programmers think in request sizes rather than allocation sizes, the request size allows better generation of statistics or errors and also helps in memory management. \begin{figure} @@ -497,5 +497,5 @@ \end{figure} -\PAB{The low-order 3-bits of the first field are \emph{unused} for any stored values as these values are 16-byte aligned by default, whereas the second field may use all of its bits.} +The low-order 3-bits of the first field are \emph{unused} for any stored values as these values are 16-byte aligned by default, whereas the second field may use all of its bits. The 3 unused bits are used to represent mapped allocation, zero filled, and alignment, respectively. Note, the alignment bit is not used in the normal header and the zero-filled/mapped bits are not used in the fake header. @@ -515,5 +515,5 @@ To locate all statistic counters, heaps are linked together in statistics mode, and this list is locked and traversed to sum all counters across heaps. Note, the list is locked to prevent errors traversing an active list; -\PAB{the statistics counters are not locked and can flicker during accumulation.} +the statistics counters are not locked and can flicker during accumulation. \VRef[Figure]{f:StatiticsOutput} shows an example of statistics output, which covers all allocation operations and information about deallocating storage not owned by a thread. No other memory allocator studied provides as comprehensive statistical information. @@ -558,18 +558,17 @@ \label{s:UserlevelThreadingSupport} -The serially-reusable problem (see \VRef{s:AllocationFastpath}) occurs for kernel threads in the ``T:H model, H = number of CPUs'' model and for user threads in the ``1:1'' model, where llheap uses the ``1:1'' model. -\PAB{The solution is to prevent interrupts that can result in CPU or KT change during operations that are logically critical sections such as moving free storage from public heap to the private heap.} +The serially-reusable problem (see \VPageref{p:SeriallyReusable}) occurs for kernel threads in the ``T:H model, H = number of CPUs'' model and for user threads in the ``1:1'' model, where llheap uses the ``1:1'' model. +The solution is to prevent interrupts that can result in a CPU or KT change during operations that are logically critical sections such as starting a memory operation on one KT and completing it on another. Locking these critical sections negates any attempt for a quick fastpath and results in high contention. For user-level threading, the serially-reusable problem appears with time slicing for preemptable scheduling, as the signal handler context switches to another user-level thread. Without time slicing, a user thread performing a long computation can prevent the execution of (starve) other threads. -\PAB{To prevent starvation for a memory-allocation-intensive thread, \ie the time slice always triggers in an allocation critical-section for one thread so the thread never gets time sliced, a thread-local \newterm{rollforward} flag is set in the signal handler when it aborts a time slice.} +To prevent starvation for a memory-allocation-intensive thread, \ie the time slice always triggers in an allocation critical-section for one thread so the thread never gets time sliced, a thread-local \newterm{rollforward} flag is set in the signal handler when it aborts a time slice. The rollforward flag is tested at the end of each allocation funnel routine (see \VPageref{p:FunnelRoutine}), and if set, it is reset and a volunteer yield (context switch) is performed to allow other threads to execute. llheap uses two techniques to detect when execution is in an allocation operation or routine called from allocation operation, to abort any time slice during this period. -On the slowpath when executing expensive operations, like @sbrk@ or @mmap@, -\PAB{interrupts are disabled/enabled by setting kernel-thread-local flags so the signal handler aborts immediately.} -\PAB{On the fastpath, disabling/enabling interrupts is too expensive as accessing kernel-thread-local storage can be expensive and not user-thread-safe.} +On the slowpath when executing expensive operations, like @sbrk@ or @mmap@, interrupts are disabled/enabled by setting kernel-thread-local flags so the signal handler aborts immediately. +On the fastpath, disabling/enabling interrupts is too expensive as accessing kernel-thread-local storage can be expensive and not user-thread-safe. For example, the ARM processor stores the thread-local pointer in a coprocessor register that cannot perform atomic base-displacement addressing. -\PAB{Hence, there is a window between loading the kernel-thread-local pointer from the coprocessor register into a normal register and adding the displacement when a time slice can move a thread.} +Hence, there is a window between loading the kernel-thread-local pointer from the coprocessor register into a normal register and adding the displacement when a time slice can move a thread. The fast technique (with lower run time cost) is to define a special code section and places all non-interruptible routines in this section. @@ -589,5 +588,5 @@ Programs can be statically or dynamically linked. \item -\PAB{The order in which the linker schedules startup code is poorly supported so cannot be controlled entirely.} +The order in which the linker schedules startup code is poorly supported so it cannot be controlled entirely. \item Knowing a KT's start and end independently from the KT code is difficult. @@ -607,6 +606,6 @@ The problem is getting initialization done before the first allocator call. However, there does not seem to be mechanism to tell either the static or dynamic loader to first perform initialization code before any calls to a loaded library. -\PAB{Also, initialization code of other libraries and run-time envoronment may call memory allocation routines such as \lstinline{malloc}. -So, this creates an even more difficult situation as there is no mechanism to tell either the static or dynamic loader to first perform initialization code of memory allocator before any other initialization that may involve a dynamic memory allocation call.} +Also, initialization code of other libraries and the run-time environment may call memory allocation routines such as \lstinline{malloc}. +This compounds the situation as there is no mechanism to tell either the static or dynamic loader to first perform the initialization code of the memory allocator before any other initialization that may involve a dynamic memory allocation call. As a result, calls to allocation routines occur without initialization. To deal with this problem, it is necessary to put a conditional initialization check along the allocation fastpath to trigger initialization (singleton pattern). @@ -740,5 +739,5 @@ \paragraph{\lstinline{void * aalloc( size_t dim, size_t elemSize )}} extends @calloc@ for allocating a dynamic array of objects without calculating the total size of array explicitly but \emph{without} zero-filling the memory. -@aalloc@ is significantly faster than @calloc@, \PAB{which is the only alternative given by the memory allocation routines}. +@aalloc@ is significantly faster than @calloc@, which is the only alternative given by the standard memory-allocation routines. \noindent\textbf{Usage} @@ -935,5 +934,5 @@ \paragraph{\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dim, ... )}} is overloaded with a variable number of specific allocation operations, or an integer dimension parameter followed by a variable number of specific allocation operations. -\PAB{These allocation operations can be passed as positional arguments when calling \lstinline{alloc} routine.} +These allocation operations can be passed as named arguments when calling the \lstinline{alloc} routine. A call without parameters returns a dynamically allocated object of type @T@ (@malloc@). A call with only the dimension (dim) parameter returns a dynamically allocated array of objects of type @T@ (@aalloc@). Index: doc/theses/mubeen_zulfiqar_MMath/background.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/background.tex (revision 25fa20aa59f67f5f840b43d7ba80ed7c6eae1da3) +++ doc/theses/mubeen_zulfiqar_MMath/background.tex (revision fb6691a550a10fe54f856d0e8db4621a98a991f8) @@ -37,5 +37,5 @@ The \newterm{storage data} is composed of allocated and freed objects, and \newterm{reserved memory}. Allocated objects (light grey) are variable sized, and are allocated and maintained by the program; -\PAB{\ie only the memory allocator knows the location of allocated storage, not the program.} +\ie only the memory allocator knows the location of allocated storage, not the program. \begin{figure}[h] \centering @@ -49,5 +49,5 @@ if there are multiple reserved blocks, they are also chained together, usually internally. -\PAB{In some allocator designs, allocated and freed objects have additional management data embedded within them.} +In some allocator designs, allocated and freed objects have additional management data embedded within them. \VRef[Figure]{f:AllocatedObject} shows an allocated object with a header, trailer, and alignment padding and spacing around the object. The header contains information about the object, \eg size, type, etc. @@ -104,5 +104,5 @@ \VRef[Figure]{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time. Blocks of free memory become smaller and non-contiguous making them less useful in serving allocation requests. -\PAB{Memory is highly fragmented when most free blocks are unusable because of their sizes.} +Memory is highly fragmented when most free blocks are unusable because of their sizes. For example, \VRef[Figure]{f:Contiguous} and \VRef[Figure]{f:HighlyFragmented} have the same quantity of external fragmentation, but \VRef[Figure]{f:HighlyFragmented} is highly fragmented. If there is a request to allocate a large object, \VRef[Figure]{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while \VRef[Figure]{f:HighlyFragmented} likely has to request more memory from the operating system. @@ -328,5 +328,5 @@ For example, multiple heaps are managed in a pool, starting with a single or a fixed number of heaps that increase\-/decrease depending on contention\-/space issues. At creation, a thread is associated with a heap from the pool. -\PAB{In some implementations of this model, when the thread attempts an allocation and its associated heap is locked (contention), it scans for an unlocked heap in the pool.} +In some implementations of this model, when the thread attempts an allocation and its associated heap is locked (contention), it scans for an unlocked heap in the pool. If an unlocked heap is found, the thread changes its association and uses that heap. If all heaps are locked, the thread may create a new heap, use it, and then place the new heap into the pool; @@ -361,5 +361,5 @@ Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup. The external fragmentation experienced by a program with a single heap is now multiplied by the number of heaps, since each heap manages its own free storage and allocates its own reserved memory. -\PAB{Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the operating system, which can be expensive.} +Additionally, objects freed by one heap cannot be reused by other threads without increasing the cost of the memory operations, except indirectly by returning free memory to the operating system, which can be expensive. Depending on how the operating system provides dynamic storage to an application, returning storage may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix. In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused. @@ -485,5 +485,5 @@ Bracketing every allocation with headers/trailers can result in significant internal fragmentation, as shown in \VRef[Figure]{f:ObjectHeaders}. -Especially if the headers contain redundant management information \PAB{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. +Especially if the headers contain redundant management information, then storing that information is a waste of storage, \eg object size may be the same for many objects because programs only allocate a small set of object sizes. As well, it can result in poor cache usage, since only a portion of the cache line is holding useful information from the program's perspective. Spatial locality can also be negatively affected leading to poor cache locality~\cite{Feng05}: @@ -660,5 +660,5 @@ With local free-lists in containers, as in \VRef[Figure]{f:LocalFreeListWithinContainers}, the container is simply removed from one heap's free list and placed on the new heap's free list. Thus, when using local free-lists, the operation of moving containers is reduced from $O(N)$ to $O(1)$. -\PAB{The cost that we have to pay for it is to add information to a header, which increases the header size, and therefore internal fragmentation.} +However, there is the additional storage cost in the header, which increases the header size, and therefore internal fragmentation. \begin{figure} Index: doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (revision 25fa20aa59f67f5f840b43d7ba80ed7c6eae1da3) +++ doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex (revision fb6691a550a10fe54f856d0e8db4621a98a991f8) @@ -48,5 +48,5 @@ There is no interaction among threads, \ie no object sharing. Each thread repeatedly allocates 100,000 \emph{8-byte} objects then deallocates them in the order they were allocated. -\PAB{Execution time of the benchmark evaluates its efficiency.} +The execution time of the benchmark evaluates its efficiency. @@ -75,5 +75,5 @@ \label{s:ChurnBenchmark} -The churn benchmark measures the runtime speed of an allocator in a multi-threaded scenerio, where each thread extensively allocates and frees dynamic memory. +The churn benchmark measures the runtime speed of an allocator in a multi-threaded scenario, where each thread extensively allocates and frees dynamic memory. Only @malloc@ and @free@ are used to eliminate any extra cost, such as @memcpy@ in @calloc@ or @realloc@. Churn simulates a memory intensive program and can be tuned to create different scenarios. @@ -133,5 +133,5 @@ When threads share a cache line, frequent reads/writes to their cache-line object causes cache misses, which cause escalating delays as cache distance increases. -Cache thrash tries to create a scenerio that leads to false sharing, if the underlying memory allocator is allocating dynamic memory to multiple threads on the same cache lines. +Cache thrash tries to create a scenario that leads to false sharing, if the underlying memory allocator is allocating dynamic memory to multiple threads on the same cache lines. Ideally, a memory allocator should distance the dynamic memory region of one thread from another. Having multiple threads allocating small objects simultaneously can cause a memory allocator to allocate objects on the same cache line, if its not distancing the memory among different threads. @@ -201,5 +201,5 @@ Cache scratch tries to create a scenario that leads to false sharing and should make the memory allocator preserve the program-induced false sharing, if it does not return a freed object to its owner thread and, instead, re-uses it instantly. An allocator using object ownership, as described in section \VRef{s:Ownership}, is less susceptible to allocator-induced passive false-sharing. -\PAB{If the object is returned to the thread that owns it, then the new object that the thread gets is less likely to be on the same cache line.} +If the object is returned to the thread that owns it, then the new object that the thread gets is less likely to be on the same cache line. \VRef[Figure]{fig:benchScratchFig} shows the pseudo code for the cache-scratch micro-benchmark. @@ -245,5 +245,5 @@ Similar to benchmark cache thrash in section \VRef{sec:benchThrashSec}, different cache access scenarios can be created using the following command-line arguments. -\begin{description}[itemsep=0pt,parsep=0pt] +\begin{description}[topsep=0pt,itemsep=0pt,parsep=0pt] \item[threads:] number of threads (K). @@ -259,7 +259,8 @@ \subsection{Speed Micro-Benchmark} \label{s:SpeedMicroBenchmark} +\vspace*{-4pt} The speed benchmark measures the runtime speed of individual and sequences of memory allocation routines: -\begin{enumerate}[itemsep=0pt,parsep=0pt] +\begin{enumerate}[topsep=-5pt,itemsep=0pt,parsep=0pt] \item malloc \item realloc Index: doc/theses/mubeen_zulfiqar_MMath/figures/Header.fig =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/figures/Header.fig (revision 25fa20aa59f67f5f840b43d7ba80ed7c6eae1da3) +++ doc/theses/mubeen_zulfiqar_MMath/figures/Header.fig (revision fb6691a550a10fe54f856d0e8db4621a98a991f8) @@ -20,21 +20,26 @@ 2 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 0 0 2 3300 1500 3300 2400 +2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + 4200 1800 6600 1800 6600 2100 4200 2100 4200 1800 2 1 0 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 3 1 1 1.00 45.00 90.00 - 4050 2625 3750 2625 3750 2400 + 4200 2775 3750 2775 3750 1725 2 1 0 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 3 1 1 1.00 45.00 90.00 - 4050 2850 3450 2850 3450 2400 -2 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 - 4200 1800 6600 1800 6600 2100 4200 2100 4200 1800 + 4200 2550 4050 2550 4050 1725 +2 1 0 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 3 + 1 1 1.00 45.00 90.00 + 4200 3000 3450 3000 3450 2025 4 0 0 50 -1 0 12 0.0000 2 180 1185 1875 1725 bucket pointer\001 4 0 0 50 -1 0 12 0.0000 2 180 1005 1875 2025 mapped size\001 4 0 0 50 -1 0 12 0.0000 2 135 1215 1875 2325 next free block\001 4 2 0 50 -1 0 12 0.0000 2 135 480 1725 2025 union\001 -4 1 0 50 -1 0 12 0.0000 2 135 270 3775 2325 0/1\001 -4 1 0 50 -1 0 12 0.0000 2 135 270 3475 2325 0/1\001 4 1 0 50 -1 0 12 0.0000 2 180 945 5400 2025 request size\001 4 1 0 50 -1 0 12 0.0000 2 180 765 5400 1425 4/8-bytes\001 4 1 0 50 -1 0 12 0.0000 2 180 765 3000 1425 4/8-bytes\001 -4 0 0 50 -1 0 12 0.0000 2 135 825 4125 2700 zero filled\001 -4 0 0 50 -1 0 12 0.0000 2 180 1515 4125 2925 mapped allocation\001 +4 1 0 50 -1 0 12 0.0000 2 135 270 3475 2025 0/1\001 +4 1 0 50 -1 0 12 0.0000 2 135 270 3775 1725 0/1\001 +4 1 0 50 -1 0 12 0.0000 2 135 270 4075 1725 0/1\001 +4 0 0 50 -1 0 12 0.0000 2 180 1515 4275 3075 mapped allocation\001 +4 0 0 50 -1 0 12 0.0000 2 135 825 4275 2850 zero filled\001 +4 0 0 50 -1 0 12 0.0000 2 180 1920 4275 2625 alignment (fake header)\001 Index: doc/theses/mubeen_zulfiqar_MMath/performance.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/performance.tex (revision 25fa20aa59f67f5f840b43d7ba80ed7c6eae1da3) +++ doc/theses/mubeen_zulfiqar_MMath/performance.tex (revision fb6691a550a10fe54f856d0e8db4621a98a991f8) @@ -91,5 +91,5 @@ Each micro-benchmark is configured and run with each of the allocators, -\PAB{The less time an allocator takes to complete a benchmark the better so lower in the graphs is better, except for the Memory micro-benchmark graphs.} +The less time an allocator takes to complete a benchmark the better so lower in the graphs is better, except for the Memory micro-benchmark graphs. All graphs use log scale on the Y-axis, except for the Memory micro-benchmark (see \VRef{s:MemoryMicroBenchmark}). Index: doc/theses/mubeen_zulfiqar_MMath/uw-ethesis-frontpgs.tex =================================================================== --- doc/theses/mubeen_zulfiqar_MMath/uw-ethesis-frontpgs.tex (revision 25fa20aa59f67f5f840b43d7ba80ed7c6eae1da3) +++ doc/theses/mubeen_zulfiqar_MMath/uw-ethesis-frontpgs.tex (revision fb6691a550a10fe54f856d0e8db4621a98a991f8) @@ -108,5 +108,5 @@ % D E C L A R A T I O N P A G E % ------------------------------- - % The following is a sample Delaration Page as provided by the GSO + % The following is a sample Declaration Page as provided by the GSO % December 13th, 2006. It is designed for an electronic thesis. \begin{center}\textbf{Author's Declaration}\end{center} @@ -141,5 +141,5 @@ The C allocation API is also extended with @resize@, advanced @realloc@, @aalloc@, @amemalign@, and @cmemalign@ so programmers do not make mistakes writing theses useful allocation operations. llheap is embedded into the \uC and \CFA runtime systems, both of which have user-level threading. -\PAB{The ability to use \CFA's advanced type-system (and possibly \CC's too) to have one allocation routine with advanced memory operations as positional arguments shows how far the allocation API can be pushed, which increases safety and greatly simplifies programmer's use of dynamic allocation.} +The ability to use \CFA's advanced type-system (and possibly \CC's too) to combine advanced memory operations into one allocation routine using named arguments shows how far the allocation API can be pushed, which increases safety and greatly simplifies programmer's use of dynamic allocation. The llheap allocator also provides comprehensive statistics for all allocation operations, which are invaluable in understanding and debugging a program's dynamic behaviour. @@ -162,6 +162,8 @@ I would like to thank all the people who made this thesis possible. -I would like to acknowledge Peter A. Buhr for his assistance and support throughtout the process. +I would like to acknowledge Peter A. Buhr for his assistance and support throughout the process. It would have been impossible without him. + +I would like to acknowledge Gregor Richards and Trevor Brown for reading my thesis quickly and giving me great feedback on my work. Also, I would say thanks to my team members at PLG especially Thierry, Michael, and Andrew for their input. @@ -195,8 +197,8 @@ % L I S T O F T A B L E S % --------------------------- -\addcontentsline{toc}{chapter}{List of Tables} -\listoftables -\cleardoublepage -\phantomsection % allows hyperref to link to the correct page +% \addcontentsline{toc}{chapter}{List of Tables} +% \listoftables +% \cleardoublepage +% \phantomsection % allows hyperref to link to the correct page % Change page numbering back to Arabic numerals