Changeset d672350 for doc/theses


Ignore:
Timestamp:
Mar 21, 2022, 1:44:06 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, ast-experimental, enum, master, pthread-emulation, qualifiedEnum, stuck-waitfor-destruct
Children:
a76202d
Parents:
ef3c383 (diff), dbe2533 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc/theses
Files:
40 added
10 edited
2 moved

Legend:

Unmodified
Added
Removed

  • doc/theses/mubeen_zulfiqar_MMath/Makefile

    ref3c383 rd672350  
    1 DOC = uw-ethesis.pdf
    2 BASE = ${DOC:%.pdf=%} # remove suffix
    31# directory for latex clutter files
    4 BUILD = build
    5 TEXSRC = $(wildcard *.tex)
    6 FIGSRC = $(wildcard *.fig)
    7 BIBSRC = $(wildcard *.bib)
    8 TEXLIB = .:../../LaTeXmacros:${BUILD}: # common latex macros
    9 BIBLIB = .:../../bibliography # common citation repository
     2Build = build
     3Figures = figures
     4Pictures = pictures
     5TeXSRC = ${wildcard *.tex}
     6FigSRC = ${notdir ${wildcard ${Figures}/*.fig}}
     7PicSRC = ${notdir ${wildcard ${Pictures}/*.fig}}
     8BIBSRC = ${wildcard *.bib}
     9TeXLIB = .:../../LaTeXmacros:${Build}: # common latex macros
     10BibLIB = .:../../bibliography # common citation repository
    1011
    1112MAKEFLAGS = --no-print-directory # --silent
    12 VPATH = ${BUILD}
     13VPATH = ${Build} ${Figures} ${Pictures} # extra search path for file names used in document
    1314
    1415### Special Rules:
    … …  
    1819
    1920### Commands:
    20 LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD}
    21 BIBTEX = BIBINPUTS=${BIBLIB} bibtex
    22 #GLOSSARY = INDEXSTYLE=${BUILD} makeglossaries-lite
     21
     22LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
     23BibTeX = BIBINPUTS=${BibLIB} bibtex
     24#Glossary = INDEXSTYLE=${Build} makeglossaries-lite
    2325
    2426### Rules and Recipes:
    2527
     28DOC = uw-ethesis.pdf
     29BASE = ${DOC:%.pdf=%} # remove suffix
     30
    2631all: ${DOC}
    2732
    28 ${BUILD}/%.dvi: ${TEXSRC} ${FIGSRC:%.fig=%.tex} ${BIBSRC} Makefile | ${BUILD}
    29         ${LATEX} ${BASE}
    30         ${BIBTEX} ${BUILD}/${BASE}
    31         ${LATEX} ${BASE}
    32 #       ${GLOSSARY} ${BUILD}/${BASE}
    33 #       ${LATEX} ${BASE}
     33clean:
     34        @rm -frv ${DOC} ${Build}
    3435
    35 ${BUILD}:
     36# File Dependencies #
     37
     38${Build}/%.dvi : ${TeXSRC} ${FigSRC:%.fig=%.tex} ${PicSRC:%.fig=%.pstex} ${BIBSRC} Makefile | ${Build}
     39        ${LaTeX} ${BASE}
     40        ${BibTeX} ${Build}/${BASE}
     41        ${LaTeX} ${BASE}
     42        # if nedded, run latex again to get citations
     43        if fgrep -s "LaTeX Warning: Citation" ${basename $@}.log ; then ${LaTeX} ${BASE} ; fi
     44#       ${Glossary} ${Build}/${BASE}
     45#       ${LaTeX} ${BASE}
     46
     47${Build}:
    3648        mkdir $@
    3749
    38 %.pdf : ${BUILD}/%.ps | ${BUILD}
     50%.pdf : ${Build}/%.ps | ${Build}
    3951        ps2pdf $<
    4052
    41 %.ps : %.dvi | ${BUILD}
     53%.ps : %.dvi | ${Build}
    4254        dvips $< -o $@
    4355
    44 %.tex : %.fig | ${BUILD}
    45         fig2dev -L eepic $< > ${BUILD}/$@
     56%.tex : %.fig | ${Build}
     57        fig2dev -L eepic $< > ${Build}/$@
    4658
    47 %.ps : %.fig | ${BUILD}
    48         fig2dev -L ps $< > ${BUILD}/$@
     59%.ps : %.fig | ${Build}
     60        fig2dev -L ps $< > ${Build}/$@
    4961
    50 %.pstex : %.fig | ${BUILD}
    51         fig2dev -L pstex $< > ${BUILD}/$@
    52         fig2dev -L pstex_t -p ${BUILD}/$@ $< > ${BUILD}/$@_t
    53 
    54 clean:
    55         @rm -frv ${DOC} ${BUILD} *.fig.bak
     62%.pstex : %.fig | ${Build}
     63        fig2dev -L pstex $< > ${Build}/$@
     64        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t

  • doc/theses/mubeen_zulfiqar_MMath/allocator.tex

    ref3c383 rd672350  
    11\chapter{Allocator}
    22
    3 \noindent
    4 ====================
    5 
    6 Writing Points:
    7 \begin{itemize}
    8 \item
    9 Objective of uHeapLmmm.
    10 \item
    11 Design philosophy.
    12 \item
    13 Background and previous design of uHeapLmmm.
    14 \item
    15 Distributed design of uHeapLmmm.
    16 
    17 ----- SHOULD WE GIVE IMPLEMENTATION DETAILS HERE? -----
    18 
    19 \PAB{Maybe. There might be an Implementation chapter.}
    20 \item
    21 figure.
    22 \item
    23 Advantages of distributed design.
    24 \end{itemize}
    25 
    26 The new features added to uHeapLmmm (incl. @malloc\_size@ routine)
    27 \CFA alloc interface with examples.
    28 
    29 \begin{itemize}
    30 \item
    31 Why did we need it?
    32 \item
    33 The added benefits.
    34 \end{itemize}
    35 
    36 
    37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    38 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    39 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% uHeapLmmm Design
    40 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    41 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    42 
    43 \section{Objective of uHeapLmmm}
    44 UHeapLmmm is a lightweight memory allocator. The objective behind uHeapLmmm is to design a minimal concurrent memory allocator that has new features and also fulfills GNU C Library requirements (FIX ME: cite requirements).
    45 
    46 \subsection{Design philosophy}
    47 The objective of uHeapLmmm's new design was to fulfill following requirements:
    48 \begin{itemize}
    49 \item It should be concurrent to be used in multi-threaded programs.
     3\section{uHeap}
     4uHeap is a lightweight memory allocator. The objective behind uHeap is to design a minimal concurrent memory allocator that has new features and also fulfills GNU C Library requirements (FIX ME: cite requirements).
     5
     6The objective of uHeap's new design was to fulfill following requirements:
     7\begin{itemize}
     8\item It should be concurrent and thread-safe for multi-threaded programs.
    509\item It should avoid global locks, on resources shared across all threads, as much as possible.
    5110\item It's performance (FIX ME: cite performance benchmarks) should be comparable to the commonly used allocators (FIX ME: cite common allocators).
    … …  
    5514%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    5615
    57 \section{Background and previous design of uHeapLmmm}
    58 uHeapLmmm was originally designed by X in X (FIX ME: add original author after confirming with Peter).
    59 (FIX ME: make and add figure of previous design with description)
    60 
    61 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    62 
    63 \section{Distributed design of uHeapLmmm}
    64 uHeapLmmm's design was reviewed and changed to fulfill new requirements (FIX ME: cite allocator philosophy). For this purpose, following two designs of uHeapLmm were proposed:
    65 
    66 \paragraph{Design 1: Decentralized}
     16\section{Design choices for uHeap}
     17uHeap's design was reviewed and changed to fulfill new requirements (FIX ME: cite allocator philosophy). For this purpose, following two designs of uHeapLmm were proposed:
     18
     19\paragraph{Design 1: Centralized}
     20One heap, but lower bucket sizes are N-shared across KTs.
     21This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
     22When KTs $\le$ N, the important bucket sizes are uncontented.
     23When KTs $>$ N, the free buckets are contented.
     24Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
     25\begin{cquote}
     26\centering
     27\input{AllocDS2}
     28\end{cquote}
     29Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
     30When no thread is assigned a bucket number, its free storage is unavailable. All KTs will be contended for one lock on sbrk for their initial allocations (before free-lists gets populated).
     31
     32\paragraph{Design 2: Decentralized N Heaps}
    6733Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the @sbrk@ area.
    6834Kernel threads (KT) are assigned to the N heaps.
    … …  
    7743Problems: need to know when a KT is created and destroyed to know when to assign/un-assign a heap to the KT.
    7844
    79 \paragraph{Design 2: Centralized}
    80 One heap, but lower bucket sizes are N-shared across KTs.
    81 This design leverages the fact that 95\% of allocation requests are less than 512 bytes and there are only 3--5 different request sizes.
    82 When KTs $\le$ N, the important bucket sizes are uncontented.
    83 When KTs $>$ N, the free buckets are contented.
    84 Therefore, threads are only contending for a small number of buckets, which are distributed among them to reduce contention.
    85 \begin{cquote}
     45\paragraph{Design 3: Decentralized Per-thread Heaps}
     46Design 3 is similar to design 2 but instead of having an M:N model, it uses a 1:1 model. So, instead of having N heaos and sharing them among M KTs, Design 3 has one heap for each KT.
     47Dynamic number of heaps: create a thread-local heap for each kernel thread (KT) with a bump-area allocated from the @sbrk@ area.
     48Each KT will have its own exclusive thread-local heap. Heap will be uncontended between KTs regardless how many KTs have been created.
     49Operations on @sbrk@ area will still be protected by locks.
     50%\begin{cquote}
     51%\centering
     52%\input{AllocDS3} FIXME add figs
     53%\end{cquote}
     54Problems: We cannot destroy the heap when a KT exits because our dynamic objects have ownership and they are returned to the heap that created them when the program frees a dynamic object. All dynamic objects point back to their owner heap. If a thread A creates an object O, passes it to another thread B, and A itself exits. When B will free object O, O should return to A's heap so A's heap should be preserved for the lifetime of the whole program as their might be objects in-use of other threads that were allocated by A. Also, we need to know when a KT is created and destroyed to know when to create/destroy a heap for the KT.
     55
     56\paragraph{Design 4: Decentralized Per-CPU Heaps}
     57Design 4 is similar to Design 3 but instead of having a heap for each thread, it creates a heap for each CPU.
     58Fixed number of heaps for a machine: create a heap for each CPU with a bump-area allocated from the @sbrk@ area.
     59Each CPU will have its own CPU-local heap. When the program does a dynamic memory operation, it will be entertained by the heap of the CPU where the process is currently running on.
     60Each CPU will have its own exclusive heap. Just like Design 3(FIXME cite), heap will be uncontended between KTs regardless how many KTs have been created.
     61Operations on @sbrk@ area will still be protected by locks.
     62To deal with preemtion during a dynamic memory operation, librseq(FIXME cite) will be used to make sure that the whole dynamic memory operation completes on one CPU. librseq's restartable sequences can make it possible to re-run a critical section and undo the current writes if a preemption happened during the critical section's execution.
     63%\begin{cquote}
     64%\centering
     65%\input{AllocDS4} FIXME add figs
     66%\end{cquote}
     67
     68Problems: This approach was slower than the per-thread model. Also, librseq does not provide such restartable sequences to detect preemtions in user-level threading system which is important to us as CFA(FIXME cite) has its own threading system that we want to support.
     69
     70Out of the four designs, Design 3 was chosen because of the following reasons.
     71\begin{itemize}
     72\item
     73Decentralized designes are better in general as compared to centralized design because their concurrency is better across all bucket-sizes as design 1 shards a few buckets of selected sizes while other designs shards all the buckets. Decentralized designes shard the whole heap which has all the buckets with the addition of sharding sbrk area. So Design 1 was eliminated.
     74\item
     75Design 2 was eliminated because it has a possibility of contention in-case of KT > N while Design 3 and 4 have no contention in any scenerio.
     76\item
     77Design 4 was eliminated because it was slower than Design 3 and it provided no way to achieve user-threading safety using librseq. We had to use CFA interruption handling to achive user-threading safety which has some cost to it. Desing 4 was already slower than Design 3, adding cost of interruption handling on top of that would have made it even slower.
     78\end{itemize}
     79
     80
     81\subsection{Advantages of distributed design}
     82
     83The distributed design of uHeap is concurrent to work in multi-threaded applications.
     84
     85Some key benefits of the distributed design of uHeap are as follows:
     86
     87\begin{itemize}
     88\item
     89The bump allocation is concurrent as memory taken from sbrk is sharded across all heaps as bump allocation reserve. The call to sbrk will be protected using locks but bump allocation (on memory taken from sbrk) will not be contended once the sbrk call has returned.
     90\item
     91Low or almost no contention on heap resources.
     92\item
     93It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
     94\item
     95Distributed design avoids unnecassry locks on resources shared across all KTs.
     96\end{itemize}
     97
     98%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     99
     100\section{uHeap Structure}
     101
     102As described in (FIXME cite 2.4) uHeap uses following features of multi-threaded memory allocators.
     103\begin{itemize}
     104\item
     105uHeap has multiple heaps without a global heap and uses 1:1 model. (FIXME cite 2.5 1:1 model)
     106\item
     107uHeap uses object ownership. (FIXME cite 2.5.2)
     108\item
     109uHeap does not use object containers (FIXME cite 2.6) or any coalescing technique. Instead each dynamic object allocated by uHeap has a header than contains bookkeeping information.
     110\item
     111Each thread-local heap in uHeap has its own allocation buffer that is taken from the system using sbrk() call. (FIXME cite 2.7)
     112\item
     113Unless a heap is freeing an object that is owned by another thread's heap or heap is using sbrk() system call, uHeap is mostly lock-free which eliminates most of the contention on shared resources. (FIXME cite 2.8)
     114\end{itemize}
     115
     116As uHeap uses a heap per-thread model to reduce contention on heap resources, we manage a list of heaps (heap-list) that can be used by threads. The list is empty at the start of the program. When a kernel thread (KT) is created, we check if heap-list is empty. If no then a heap is removed from the heap-list and is given to this new KT to use exclusively. If yes then a new heap object is created in dynamic memory and is given to this new KT to use exclusively. When a KT exits, its heap is not destroyed but instead its heap is put on the heap-list and is ready to be reused by new KTs.
     117
     118This reduces the memory footprint as the objects on free-lists of a KT that has exited can be reused by a new KT. Also, we preserve all the heaps that were created during the lifetime of the program till the end of the program. uHeap uses object ownership where an object is freed to the free-buckets of the heap that allocated it. Even after a KT A has exited, its heap has to be preserved as there might be objects in-use of other threads that were initially allocated by A and the passed to other threads.
     119
     120\begin{figure}
    86121\centering
    87 \input{AllocDS2}
    88 \end{cquote}
    89 Problems: need to know when a kernel thread (KT) is created and destroyed to know when to assign a shared bucket-number.
    90 When no thread is assigned a bucket number, its free storage is unavailable. All KTs will be contended for one lock on sbrk for their initial allocations (before free-lists gets populated).
    91 
    92 Out of the two designs, Design 1 was chosen because it's concurrency is better across all bucket-sizes as design-2 shards a few buckets of selected sizes while design-1 shards all the buckets. Design-2 shards the whole heap which has all the buckets with the addition of sharding sbrk area.
    93 
    94 \subsection{Advantages of distributed design}
    95 The distributed design of uHeapLmmm is concurrent to work in multi-threaded applications.
    96 
    97 Some key benefits of the distributed design of uHeapLmmm are as follows:
    98 
    99 \begin{itemize}
    100 \item
    101 The bump allocation is concurrent as memory taken from sbrk is sharded across all heaps as bump allocation reserve. The lock on bump allocation (on memory taken from sbrk) will only be contended if KTs > N. The contention on sbrk area is less likely as it will only happen in the case if heaps assigned to two KTs get short of bump allocation reserve simultanously.
    102 \item
    103 N heaps are created at the start of the program and destroyed at the end of program. When a KT is created, we only assign it to one of the heaps. When a KT is destroyed, we only dissociate it from the assigned heap but we do not destroy that heap. That heap will go back to our pool-of-heaps, ready to be used by some new KT. And if that heap was shared among multiple KTs (like the case of KTs > N) then, on deletion of one KT, that heap will be still in-use of the other KTs. This will prevent creation and deletion of heaps during run-time as heaps are re-usable which helps in keeping low-memory footprint.
    104 \item
    105 It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
    106 \item
    107 Distributed design avoids unnecassry locks on resources shared across all KTs.
    108 \end{itemize}
    109 
    110 FIX ME: Cite performance comparison of the two heap designs if required
     122\includegraphics[width=0.65\textwidth]{figures/NewHeapStructure.eps}
     123\caption{HeapStructure}
     124\label{fig:heapStructureFig}
     125\end{figure}
     126
     127Each heap uses seggregated free-buckets that have free objects of a specific size. Each free-bucket of a specific size has following 2 lists in it:
     128\begin{itemize}
     129\item
     130Free list is used when a thread is freeing an object that is owned by its own heap so free list does not use any locks/atomic-operations as it is only used by the owner KT.
     131\item
     132Away list is used when a thread A is freeing an object that is owned by another KT B's heap. This object should be freed to the owner heap (B's heap) so A will place the object on the away list of B. Away list is lock protected as it is shared by all other threads.
     133\end{itemize}
     134
     135When a dynamic object of a size S is requested. The thread-local heap will check if S is greater than or equal to the mmap threshhold. Any request larger than the mmap threshhold is fulfilled by allocating an mmap area of that size and such requests are not allocated on sbrk area. The value of this threshhold can be changed using mallopt routine but the new value should not be larger than our biggest free-bucket size.
     136
     137Algorithm~\ref{alg:heapObjectAlloc} briefly shows how an allocation request is fulfilled.
     138
     139\begin{algorithm}
     140\caption{Dynamic object allocation of size S}\label{alg:heapObjectAlloc}
     141\begin{algorithmic}[1]
     142\State $\textit{O} \gets \text{NULL}$
     143\If {$S < \textit{mmap-threshhold}$}
     144        \State $\textit{B} \gets (\text{smallest free-bucket} \geq S)$
     145        \If {$\textit{B's free-list is empty}$}
     146                \If {$\textit{B's away-list is empty}$}
     147                        \If {$\textit{heap's allocation buffer} < S$}
     148                                \State $\text{get allocation buffer using system call sbrk()}$
     149                        \EndIf
     150                        \State $\textit{O} \gets \text{bump allocate an object of size S from allocation buffer}$
     151                \Else
     152                        \State $\textit{merge B's away-list into free-list}$
     153                        \State $\textit{O} \gets \text{pop an object from B's free-list}$
     154                \EndIf
     155        \Else
     156                \State $\textit{O} \gets \text{pop an object from B's free-list}$
     157        \EndIf
     158        \State $\textit{O's owner} \gets \text{B}$
     159\Else
     160        \State $\textit{O} \gets \text{allocate dynamic memory using system call mmap with size S}$
     161\EndIf
     162\State $\Return \textit{ O}$
     163\end{algorithmic}
     164\end{algorithm}
     165
    111166
    112167%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    113168
    114169\section{Added Features and Methods}
    115 To improve the UHeapLmmm allocator (FIX ME: cite uHeapLmmm) interface and make it more user friendly, we added a few more routines to the C allocator. Also, we built a CFA (FIX ME: cite cforall) interface on top of C interface to increase the usability of the allocator.
     170To improve the uHeap allocator (FIX ME: cite uHeap) interface and make it more user friendly, we added a few more routines to the C allocator. Also, we built a \CFA (FIX ME: cite cforall) interface on top of C interface to increase the usability of the allocator.
    116171
    117172\subsection{C Interface}
    118173We added a few more features and routines to the allocator's C interface that can make the allocator more usable to the programmers. THese features will programmer more control on the dynamic memory allocation.
    119174
    120 \subsubsection void * aalloc( size\_t dim, size\_t elemSize )
    121 aalloc is an extension of malloc. It allows programmer to allocate a dynamic array of objects without calculating the total size of array explicitly. The only alternate of this routine in the other allocators is calloc but calloc also fills the dynamic memory with 0 which makes it slower for a programmer who only wants to dynamically allocate an array of objects without filling it with 0.
    122 \paragraph{Usage}
    123 aalloc takes two parameters.
    124 
    125 \begin{itemize}
    126 \item
    127 dim: number of objects in the array
    128 \item
    129 elemSize: size of the object in the array.
    130 \end{itemize}
    131 It returns address of dynamic object allocatoed on heap that can contain dim number of objects of the size elemSize. On failure, it returns NULL pointer.
    132 
    133 \subsubsection void * resize( void * oaddr, size\_t size )
    134 resize is an extension of relloc. It allows programmer to reuse a cuurently allocated dynamic object with a new size requirement. Its alternate in the other allocators is realloc but relloc also copy the data in old object to the new object which makes it slower for the programmer who only wants to reuse an old dynamic object for a new size requirement but does not want to preserve the data in the old object to the new object.
    135 \paragraph{Usage}
    136 resize takes two parameters.
    137 
    138 \begin{itemize}
    139 \item
    140 oaddr: the address of the old object that needs to be resized.
    141 \item
    142 size: the new size requirement of the to which the old object needs to be resized.
    143 \end{itemize}
    144 It returns an object that is of the size given but it does not preserve the data in the old object. On failure, it returns NULL pointer.
    145 
    146 \subsubsection void * resize( void * oaddr, size\_t nalign, size\_t size )
    147 This resize is an extension of the above resize (FIX ME: cite above resize). In addition to resizing the size of of an old object, it can also realign the old object to a new alignment requirement.
     175\subsection{Out of Memory}
     176
     177Most allocators use @nullptr@ to indicate an allocation failure, specifically out of memory;
     178hence the need to return an alternate value for a zero-sized allocation.
     179The alternative is to abort a program when out of memory.
     180In theory, notifying the programmer allows recovery;
     181in practice, it is almost impossible to gracefully when out of memory, so the cheaper approach of returning @nullptr@ for a zero-sized allocation is chosen.
     182
     183
     184\subsection{\lstinline{void * aalloc( size_t dim, size_t elemSize )}}
     185@aalloc@ is an extension of malloc. It allows programmer to allocate a dynamic array of objects without calculating the total size of array explicitly. The only alternate of this routine in the other allocators is calloc but calloc also fills the dynamic memory with 0 which makes it slower for a programmer who only wants to dynamically allocate an array of objects without filling it with 0.
     186\paragraph{Usage}
     187@aalloc@ takes two parameters.
     188
     189\begin{itemize}
     190\item
     191@dim@: number of objects in the array
     192\item
     193@elemSize@: size of the object in the array.
     194\end{itemize}
     195It returns address of dynamic object allocatoed on heap that can contain dim number of objects of the size elemSize. On failure, it returns a @NULL@ pointer.
     196
     197\subsection{\lstinline{void * resize( void * oaddr, size_t size )}}
     198@resize@ is an extension of relloc. It allows programmer to reuse a cuurently allocated dynamic object with a new size requirement. Its alternate in the other allocators is @realloc@ but relloc also copy the data in old object to the new object which makes it slower for the programmer who only wants to reuse an old dynamic object for a new size requirement but does not want to preserve the data in the old object to the new object.
     199\paragraph{Usage}
     200@resize@ takes two parameters.
     201
     202\begin{itemize}
     203\item
     204@oaddr@: the address of the old object that needs to be resized.
     205\item
     206@size@: the new size requirement of the to which the old object needs to be resized.
     207\end{itemize}
     208It returns an object that is of the size given but it does not preserve the data in the old object. On failure, it returns a @NULL@ pointer.
     209
     210\subsection{\lstinline{void * resize( void * oaddr, size_t nalign, size_t size )}}
     211This @resize@ is an extension of the above @resize@ (FIX ME: cite above resize). In addition to resizing the size of of an old object, it can also realign the old object to a new alignment requirement.
    148212\paragraph{Usage}
    149213This resize takes three parameters. It takes an additional parameter of nalign as compared to the above resize (FIX ME: cite above resize).
    … …  
    151215\begin{itemize}
    152216\item
    153 oaddr: the address of the old object that needs to be resized.
    154 \item
    155 nalign: the new alignment to which the old object needs to be realigned.
    156 \item
    157 size: the new size requirement of the to which the old object needs to be resized.
    158 \end{itemize}
    159 It returns an object with the size and alignment given in the parameters. On failure, it returns a NULL pointer.
    160 
    161 \subsubsection void * amemalign( size\_t alignment, size\_t dim, size\_t elemSize )
     217@oaddr@: the address of the old object that needs to be resized.
     218\item
     219@nalign@: the new alignment to which the old object needs to be realigned.
     220\item
     221@size@: the new size requirement of the to which the old object needs to be resized.
     222\end{itemize}
     223It returns an object with the size and alignment given in the parameters. On failure, it returns a @NULL@ pointer.
     224
     225\subsection{\lstinline{void * amemalign( size_t alignment, size_t dim, size_t elemSize )}}
    162226amemalign is a hybrid of memalign and aalloc. It allows programmer to allocate an aligned dynamic array of objects without calculating the total size of the array explicitly. It frees the programmer from calculating the total size of the array.
    163227\paragraph{Usage}
    … …  
    166230\begin{itemize}
    167231\item
    168 alignment: the alignment to which the dynamic array needs to be aligned.
    169 \item
    170 dim: number of objects in the array
    171 \item
    172 elemSize: size of the object in the array.
    173 \end{itemize}
    174 It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize. The returned dynamic array is aligned to the given alignment. On failure, it returns NULL pointer.
    175 
    176 \subsubsection void * cmemalign( size\_t alignment, size\_t dim, size\_t elemSize )
     232@alignment@: the alignment to which the dynamic array needs to be aligned.
     233\item
     234@dim@: number of objects in the array
     235\item
     236@elemSize@: size of the object in the array.
     237\end{itemize}
     238It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize. The returned dynamic array is aligned to the given alignment. On failure, it returns a @NULL@ pointer.
     239
     240\subsection{\lstinline{void * cmemalign( size_t alignment, size_t dim, size_t elemSize )}}
    177241cmemalign is a hybrid of amemalign and calloc. It allows programmer to allocate an aligned dynamic array of objects that is 0 filled. The current way to do this in other allocators is to allocate an aligned object with memalign and then fill it with 0 explicitly. This routine provides both features of aligning and 0 filling, implicitly.
    178242\paragraph{Usage}
    … …  
    181245\begin{itemize}
    182246\item
    183 alignment: the alignment to which the dynamic array needs to be aligned.
    184 \item
    185 dim: number of objects in the array
    186 \item
    187 elemSize: size of the object in the array.
    188 \end{itemize}
    189 It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize. The returned dynamic array is aligned to the given alignment and is 0 filled. On failure, it returns NULL pointer.
    190 
    191 \subsubsection size\_t malloc\_alignment( void * addr )
    192 malloc\_alignment returns the alignment of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required alignment.
    193 \paragraph{Usage}
    194 malloc\_alignment takes one parameters.
    195 
    196 \begin{itemize}
    197 \item
    198 addr: the address of the currently allocated dynamic object.
    199 \end{itemize}
    200 malloc\_alignment returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeapLmmm allocator.
    201 
    202 \subsubsection bool malloc\_zero\_fill( void * addr )
    203 malloc\_zero\_fill returns whether a currently allocated dynamic object was initially zero filled at the time of allocation. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verifying the zero filled property of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was zero filled at the time of allocation.
    204 \paragraph{Usage}
    205 malloc\_zero\_fill takes one parameters.
    206 
    207 \begin{itemize}
    208 \item
    209 addr: the address of the currently allocated dynamic object.
    210 \end{itemize}
    211 malloc\_zero\_fill returns true if the dynamic object was initially zero filled and return false otherwise. On failure, it returns false.
    212 
    213 \subsubsection size\_t malloc\_size( void * addr )
    214 malloc\_size returns the allocation size of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required size. Its current alternate in the other allocators is malloc\_usable\_size. But, malloc\_size is different from malloc\_usable\_size as malloc\_usabe\_size returns the total data capacity of dynamic object including the extra space at the end of the dynamic object. On the other hand, malloc\_size returns the size that was given to the allocator at the allocation of the dynamic object. This size is updated when an object is realloced, resized, or passed through a similar allocator routine.
    215 \paragraph{Usage}
    216 malloc\_size takes one parameters.
    217 
    218 \begin{itemize}
    219 \item
    220 addr: the address of the currently allocated dynamic object.
    221 \end{itemize}
    222 malloc\_size returns the allocation size of the given dynamic object. On failure, it return zero.
    223 
    224 \subsubsection void * realloc( void * oaddr, size\_t nalign, size\_t size )
    225 This realloc is an extension of the default realloc (FIX ME: cite default realloc). In addition to reallocating an old object and preserving the data in old object, it can also realign the old object to a new alignment requirement.
    226 \paragraph{Usage}
    227 This realloc takes three parameters. It takes an additional parameter of nalign as compared to the default realloc.
    228 
    229 \begin{itemize}
    230 \item
    231 oaddr: the address of the old object that needs to be reallocated.
    232 \item
    233 nalign: the new alignment to which the old object needs to be realigned.
    234 \item
    235 size: the new size requirement of the to which the old object needs to be resized.
    236 \end{itemize}
    237 It returns an object with the size and alignment given in the parameters that preserves the data in the old object. On failure, it returns a NULL pointer.
    238 
    239 \subsection{CFA Malloc Interface}
    240 We added some routines to the malloc interface of CFA. These routines can only be used in CFA and not in our standalone uHeapLmmm allocator as these routines use some features that are only provided by CFA and not by C. It makes the allocator even more usable to the programmers.
    241 CFA provides the liberty to know the returned type of a call to the allocator. So, mainly in these added routines, we removed the object size parameter from the routine as allocator can calculate the size of the object from the returned type.
    242 
    243 \subsubsection T * malloc( void )
     247@alignment@: the alignment to which the dynamic array needs to be aligned.
     248\item
     249@dim@: number of objects in the array
     250\item
     251@elemSize@: size of the object in the array.
     252\end{itemize}
     253It returns a dynamic array of objects that has the capacity to contain dim number of objects of the size of elemSize. The returned dynamic array is aligned to the given alignment and is 0 filled. On failure, it returns a @NULL@ pointer.
     254
     255\subsection{\lstinline{size_t malloc_alignment( void * addr )}}
     256@malloc_alignment@ returns the alignment of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required alignment.
     257\paragraph{Usage}
     258@malloc_alignment@ takes one parameters.
     259
     260\begin{itemize}
     261\item
     262@addr@: the address of the currently allocated dynamic object.
     263\end{itemize}
     264@malloc_alignment@ returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeap allocator.
     265
     266\subsection{\lstinline{bool malloc_zero_fill( void * addr )}}
     267@malloc_zero_fill@ returns whether a currently allocated dynamic object was initially zero filled at the time of allocation. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verifying the zero filled property of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was zero filled at the time of allocation.
     268\paragraph{Usage}
     269@malloc_zero_fill@ takes one parameters.
     270
     271\begin{itemize}
     272\item
     273@addr@: the address of the currently allocated dynamic object.
     274\end{itemize}
     275@malloc_zero_fill@ returns true if the dynamic object was initially zero filled and return false otherwise. On failure, it returns false.
     276
     277\subsection{\lstinline{size_t malloc_size( void * addr )}}
     278@malloc_size@ returns the allocation size of a currently allocated dynamic object. It allows the programmer in memory management and personal bookkeeping. It helps the programmer in verofying the alignment of a dynamic object especially in a scenerio similar to prudcer-consumer where a producer allocates a dynamic object and the consumer needs to assure that the dynamic object was allocated with the required size. Its current alternate in the other allocators is @malloc_usable_size@. But, @malloc_size@ is different from @malloc_usable_size@ as @malloc_usabe_size@ returns the total data capacity of dynamic object including the extra space at the end of the dynamic object. On the other hand, @malloc_size@ returns the size that was given to the allocator at the allocation of the dynamic object. This size is updated when an object is realloced, resized, or passed through a similar allocator routine.
     279\paragraph{Usage}
     280@malloc_size@ takes one parameters.
     281
     282\begin{itemize}
     283\item
     284@addr@: the address of the currently allocated dynamic object.
     285\end{itemize}
     286@malloc_size@ returns the allocation size of the given dynamic object. On failure, it return zero.
     287
     288\subsection{\lstinline{void * realloc( void * oaddr, size_t nalign, size_t size )}}
     289This @realloc@ is an extension of the default @realloc@ (FIX ME: cite default @realloc@). In addition to reallocating an old object and preserving the data in old object, it can also realign the old object to a new alignment requirement.
     290\paragraph{Usage}
     291This @realloc@ takes three parameters. It takes an additional parameter of nalign as compared to the default @realloc@.
     292
     293\begin{itemize}
     294\item
     295@oaddr@: the address of the old object that needs to be reallocated.
     296\item
     297@nalign@: the new alignment to which the old object needs to be realigned.
     298\item
     299@size@: the new size requirement of the to which the old object needs to be resized.
     300\end{itemize}
     301It returns an object with the size and alignment given in the parameters that preserves the data in the old object. On failure, it returns a @NULL@ pointer.
     302
     303\subsection{\CFA Malloc Interface}
     304We added some routines to the malloc interface of \CFA. These routines can only be used in \CFA and not in our standalone uHeap allocator as these routines use some features that are only provided by \CFA and not by C. It makes the allocator even more usable to the programmers.
     305\CFA provides the liberty to know the returned type of a call to the allocator. So, mainly in these added routines, we removed the object size parameter from the routine as allocator can calculate the size of the object from the returned type.
     306
     307\subsection{\lstinline{T * malloc( void )}}
    244308This malloc is a simplified polymorphic form of defualt malloc (FIX ME: cite malloc). It does not take any parameter as compared to default malloc that takes one parameter.
    245309\paragraph{Usage}
    246310This malloc takes no parameters.
    247 It returns a dynamic object of the size of type T. On failure, it return NULL pointer.
    248 
    249 \subsubsection T * aalloc( size\_t dim )
     311It returns a dynamic object of the size of type @T@. On failure, it returns a @NULL@ pointer.
     312
     313\subsection{\lstinline{T * aalloc( size_t dim )}}
    250314This aalloc is a simplified polymorphic form of above aalloc (FIX ME: cite aalloc). It takes one parameter as compared to the above aalloc that takes two parameters.
    251315\paragraph{Usage}
    … …  
    254318\begin{itemize}
    255319\item
    256 dim: required number of objects in the array.
    257 \end{itemize}
    258 It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. On failure, it return NULL pointer.
    259 
    260 \subsubsection T * calloc( size\_t dim )
     320@dim@: required number of objects in the array.
     321\end{itemize}
     322It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type @T@. On failure, it returns a @NULL@ pointer.
     323
     324\subsection{\lstinline{T * calloc( size_t dim )}}
    261325This calloc is a simplified polymorphic form of defualt calloc (FIX ME: cite calloc). It takes one parameter as compared to the default calloc that takes two parameters.
    262326\paragraph{Usage}
    … …  
    265329\begin{itemize}
    266330\item
    267 dim: required number of objects in the array.
    268 \end{itemize}
    269 It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. On failure, it return NULL pointer.
    270 
    271 \subsubsection T * resize( T * ptr, size\_t size )
    272 This resize is a simplified polymorphic form of above resize (FIX ME: cite resize with alignment). It takes two parameters as compared to the above resize that takes three parameters. It frees the programmer from explicitly mentioning the alignment of the allocation as CFA provides gives allocator the liberty to get the alignment of the returned type.
     331@dim@: required number of objects in the array.
     332\end{itemize}
     333It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type @T@. On failure, it returns a @NULL@ pointer.
     334
     335\subsection{\lstinline{T * resize( T * ptr, size_t size )}}
     336This resize is a simplified polymorphic form of above resize (FIX ME: cite resize with alignment). It takes two parameters as compared to the above resize that takes three parameters. It frees the programmer from explicitly mentioning the alignment of the allocation as \CFA provides gives allocator the liberty to get the alignment of the returned type.
    273337\paragraph{Usage}
    274338This resize takes two parameters.
    … …  
    276340\begin{itemize}
    277341\item
    278 ptr: address of the old object.
    279 \item
    280 size: the required size of the new object.
    281 \end{itemize}
    282 It returns a dynamic object of the size given in paramters. The returned object is aligned to the alignemtn of type T. On failure, it return NULL pointer.
    283 
    284 \subsubsection T * realloc( T * ptr, size\_t size )
    285 This realloc is a simplified polymorphic form of defualt realloc (FIX ME: cite realloc with align). It takes two parameters as compared to the above realloc that takes three parameters. It frees the programmer from explicitly mentioning the alignment of the allocation as CFA provides gives allocator the liberty to get the alignment of the returned type.
    286 \paragraph{Usage}
    287 This realloc takes two parameters.
    288 
    289 \begin{itemize}
    290 \item
    291 ptr: address of the old object.
    292 \item
    293 size: the required size of the new object.
    294 \end{itemize}
    295 It returns a dynamic object of the size given in paramters that preserves the data in the given object. The returned object is aligned to the alignemtn of type T. On failure, it return NULL pointer.
    296 
    297 \subsubsection T * memalign( size\_t align )
     342@ptr@: address of the old object.
     343\item
     344@size@: the required size of the new object.
     345\end{itemize}
     346It returns a dynamic object of the size given in paramters. The returned object is aligned to the alignemtn of type @T@. On failure, it returns a @NULL@ pointer.
     347
     348\subsection{\lstinline{T * realloc( T * ptr, size_t size )}}
     349This @realloc@ is a simplified polymorphic form of defualt @realloc@ (FIX ME: cite @realloc@ with align). It takes two parameters as compared to the above @realloc@ that takes three parameters. It frees the programmer from explicitly mentioning the alignment of the allocation as \CFA provides gives allocator the liberty to get the alignment of the returned type.
     350\paragraph{Usage}
     351This @realloc@ takes two parameters.
     352
     353\begin{itemize}
     354\item
     355@ptr@: address of the old object.
     356\item
     357@size@: the required size of the new object.
     358\end{itemize}
     359It returns a dynamic object of the size given in paramters that preserves the data in the given object. The returned object is aligned to the alignemtn of type @T@. On failure, it returns a @NULL@ pointer.
     360
     361\subsection{\lstinline{T * memalign( size_t align )}}
    298362This memalign is a simplified polymorphic form of defualt memalign (FIX ME: cite memalign). It takes one parameters as compared to the default memalign that takes two parameters.
    299363\paragraph{Usage}
    … …  
    302366\begin{itemize}
    303367\item
    304 align: the required alignment of the dynamic object.
    305 \end{itemize}
    306 It returns a dynamic object of the size of type T that is aligned to given parameter align. On failure, it return NULL pointer.
    307 
    308 \subsubsection T * amemalign( size\_t align, size\_t dim )
     368@align@: the required alignment of the dynamic object.
     369\end{itemize}
     370It returns a dynamic object of the size of type @T@ that is aligned to given parameter align. On failure, it returns a @NULL@ pointer.
     371
     372\subsection{\lstinline{T * amemalign( size_t align, size_t dim )}}
    309373This amemalign is a simplified polymorphic form of above amemalign (FIX ME: cite amemalign). It takes two parameter as compared to the above amemalign that takes three parameters.
    310374\paragraph{Usage}
    … …  
    313377\begin{itemize}
    314378\item
    315 align: required alignment of the dynamic array.
    316 \item
    317 dim: required number of objects in the array.
    318 \end{itemize}
    319 It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. The returned object is aligned to the given parameter align. On failure, it return NULL pointer.
    320 
    321 \subsubsection T * cmemalign( size\_t align, size\_t dim  )
     379@align@: required alignment of the dynamic array.
     380\item
     381@dim@: required number of objects in the array.
     382\end{itemize}
     383It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type @T@. The returned object is aligned to the given parameter align. On failure, it returns a @NULL@ pointer.
     384
     385\subsection{\lstinline{T * cmemalign( size_t align, size_t dim  )}}
    322386This cmemalign is a simplified polymorphic form of above cmemalign (FIX ME: cite cmemalign). It takes two parameter as compared to the above cmemalign that takes three parameters.
    323387\paragraph{Usage}
    … …  
    326390\begin{itemize}
    327391\item
    328 align: required alignment of the dynamic array.
    329 \item
    330 dim: required number of objects in the array.
    331 \end{itemize}
    332 It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type T. The returned object is aligned to the given parameter align and is zero filled. On failure, it return NULL pointer.
    333 
    334 \subsubsection T * aligned\_alloc( size\_t align )
    335 This aligned\_alloc is a simplified polymorphic form of defualt aligned\_alloc (FIX ME: cite aligned\_alloc). It takes one parameter as compared to the default aligned\_alloc that takes two parameters.
    336 \paragraph{Usage}
    337 This aligned\_alloc takes one parameter.
    338 
    339 \begin{itemize}
    340 \item
    341 align: required alignment of the dynamic object.
    342 \end{itemize}
    343 It returns a dynamic object of the size of type T that is aligned to the given parameter. On failure, it return NULL pointer.
    344 
    345 \subsubsection int posix\_memalign( T ** ptr, size\_t align )
    346 This posix\_memalign is a simplified polymorphic form of defualt posix\_memalign (FIX ME: cite posix\_memalign). It takes two parameters as compared to the default posix\_memalign that takes three parameters.
    347 \paragraph{Usage}
    348 This posix\_memalign takes two parameter.
    349 
    350 \begin{itemize}
    351 \item
    352 ptr: variable address to store the address of the allocated object.
    353 \item
    354 align: required alignment of the dynamic object.
    355 \end{itemize}
    356 
    357 It stores address of the dynamic object of the size of type T in given parameter ptr. This object is aligned to the given parameter. On failure, it return NULL pointer.
    358 
    359 \subsubsection T * valloc( void )
    360 This valloc is a simplified polymorphic form of defualt valloc (FIX ME: cite valloc). It takes no parameters as compared to the default valloc that takes one parameter.
    361 \paragraph{Usage}
    362 valloc takes no parameters.
    363 It returns a dynamic object of the size of type T that is aligned to the page size. On failure, it return NULL pointer.
    364 
    365 \subsubsection T * pvalloc( void )
    366 This pcvalloc is a simplified polymorphic form of defualt pcvalloc (FIX ME: cite pcvalloc). It takes no parameters as compared to the default pcvalloc that takes one parameter.
    367 \paragraph{Usage}
    368 pvalloc takes no parameters.
    369 It returns a dynamic object of the size that is calcutaed by rouding the size of type T. The returned object is also aligned to the page size. On failure, it return NULL pointer.
    370 
    371 \subsection Alloc Interface
    372 In addition to improve allocator interface both for CFA and our standalone allocator uHeapLmmm in C. We also added a new alloc interface in CFA that increases usability of dynamic memory allocation.
     392@align@: required alignment of the dynamic array.
     393\item
     394@dim@: required number of objects in the array.
     395\end{itemize}
     396It returns a dynamic object that has the capacity to contain dim number of objects, each of the size of type @T@. The returned object is aligned to the given parameter align and is zero filled. On failure, it returns a @NULL@ pointer.
     397
     398\subsection{\lstinline{T * aligned_alloc( size_t align )}}
     399This @aligned_alloc@ is a simplified polymorphic form of defualt @aligned_alloc@ (FIX ME: cite @aligned_alloc@). It takes one parameter as compared to the default @aligned_alloc@ that takes two parameters.
     400\paragraph{Usage}
     401This @aligned_alloc@ takes one parameter.
     402
     403\begin{itemize}
     404\item
     405@align@: required alignment of the dynamic object.
     406\end{itemize}
     407It returns a dynamic object of the size of type @T@ that is aligned to the given parameter. On failure, it returns a @NULL@ pointer.
     408
     409\subsection{\lstinline{int posix_memalign( T ** ptr, size_t align )}}
     410This @posix_memalign@ is a simplified polymorphic form of defualt @posix_memalign@ (FIX ME: cite @posix_memalign@). It takes two parameters as compared to the default @posix_memalign@ that takes three parameters.
     411\paragraph{Usage}
     412This @posix_memalign@ takes two parameter.
     413
     414\begin{itemize}
     415\item
     416@ptr@: variable address to store the address of the allocated object.
     417\item
     418@align@: required alignment of the dynamic object.
     419\end{itemize}
     420
     421It stores address of the dynamic object of the size of type @T@ in given parameter ptr. This object is aligned to the given parameter. On failure, it returns a @NULL@ pointer.
     422
     423\subsection{\lstinline{T * valloc( void )}}
     424This @valloc@ is a simplified polymorphic form of defualt @valloc@ (FIX ME: cite @valloc@). It takes no parameters as compared to the default @valloc@ that takes one parameter.
     425\paragraph{Usage}
     426@valloc@ takes no parameters.
     427It returns a dynamic object of the size of type @T@ that is aligned to the page size. On failure, it returns a @NULL@ pointer.
     428
     429\subsection{\lstinline{T * pvalloc( void )}}
     430\paragraph{Usage}
     431@pvalloc@ takes no parameters.
     432It returns a dynamic object of the size that is calcutaed by rouding the size of type @T@. The returned object is also aligned to the page size. On failure, it returns a @NULL@ pointer.
     433
     434\subsection{Alloc Interface}
     435In addition to improve allocator interface both for \CFA and our standalone allocator uHeap in C. We also added a new alloc interface in \CFA that increases usability of dynamic memory allocation.
    373436This interface helps programmers in three major ways.
    374437
    … …  
    379442Parametre Positions: alloc interface frees programmers from remembering parameter postions in call to routines.
    380443\item
    381 Object Size: alloc interface does not require programmer to mention the object size as CFA allows allocator to determince the object size from returned type of alloc call.
    382 \end{itemize}
    383 
    384 Alloc interface uses polymorphism, backtick routines (FIX ME: cite backtick) and ttype parameters of CFA (FIX ME: cite ttype) to provide a very simple dynamic memory allocation interface to the programmers. The new interfece has just one routine name alloc that can be used to perform a wide range of dynamic allocations. The parameters use backtick functions to provide a similar-to named parameters feature for our alloc interface so that programmers do not have to remember parameter positions in alloc call except the position of dimension (dim) parameter.
    385 
    386 \subsubsection{Routine: T * alloc( ... )}
    387 Call to alloc wihout any parameter returns one object of size of type T allocated dynamically.
     444Object Size: alloc interface does not require programmer to mention the object size as \CFA allows allocator to determince the object size from returned type of alloc call.
     445\end{itemize}
     446
     447Alloc interface uses polymorphism, backtick routines (FIX ME: cite backtick) and ttype parameters of \CFA (FIX ME: cite ttype) to provide a very simple dynamic memory allocation interface to the programmers. The new interfece has just one routine name alloc that can be used to perform a wide range of dynamic allocations. The parameters use backtick functions to provide a similar-to named parameters feature for our alloc interface so that programmers do not have to remember parameter positions in alloc call except the position of dimension (dim) parameter.
     448
     449\subsection{Routine: \lstinline{T * alloc( ... )}}
     450Call to alloc wihout any parameter returns one object of size of type @T@ allocated dynamically.
    388451Only the dimension (dim) parameter for array allocation has the fixed position in the alloc routine. If programmer wants to allocate an array of objects that the required number of members in the array has to be given as the first parameter to the alloc routine.
    389 alocc routine accepts six kinds of arguments. Using different combinations of tha parameters, different kind of allocations can be performed. Any combincation of parameters can be used together except `realloc and `resize that should not be used simultanously in one call to routine as it creates ambiguity about whether to reallocate or resize a currently allocated dynamic object. If both `resize and `realloc are used in a call to alloc then the latter one will take effect or unexpected resulted might be produced.
     452alocc routine accepts six kinds of arguments. Using different combinations of tha parameters, different kind of allocations can be performed. Any combincation of parameters can be used together except @`realloc@ and @`resize@ that should not be used simultanously in one call to routine as it creates ambiguity about whether to reallocate or resize a currently allocated dynamic object. If both @`resize@ and @`realloc@ are used in a call to alloc then the latter one will take effect or unexpected resulted might be produced.
    390453
    391454\paragraph{Dim}
    392 This is the only parameter in the alloc routine that has a fixed-position and it is also the only parameter that does not use a backtick function. It has to be passed at the first position to alloc call in-case of an array allocation of objects of type T.
    393 It represents the required number of members in the array allocation as in CFA's aalloc (FIX ME: cite aalloc).
    394 This parameter should be of type size\_t.
    395 
    396 Example: int a = alloc( 5 )
     455This is the only parameter in the alloc routine that has a fixed-position and it is also the only parameter that does not use a backtick function. It has to be passed at the first position to alloc call in-case of an array allocation of objects of type @T@.
     456It represents the required number of members in the array allocation as in \CFA's aalloc (FIX ME: cite aalloc).
     457This parameter should be of type @size_t@.
     458
     459Example: @int a = alloc( 5 )@
    397460This call will return a dynamic array of five integers.
    398461
    399462\paragraph{Align}
    400 This parameter is position-free and uses a backtick routine align (`align). The parameter passed with `align should be of type size\_t. If the alignment parameter is not a power of two or is less than the default alignment of the allocator (that can be found out using routine libAlign in CFA) then the passed alignment parameter will be rejected and the default alignment will be used.
    401 
    402 Example: int b = alloc( 5 , 64`align )
     463This parameter is position-free and uses a backtick routine align (@`align@). The parameter passed with @`align@ should be of type @size_t@. If the alignment parameter is not a power of two or is less than the default alignment of the allocator (that can be found out using routine libAlign in \CFA) then the passed alignment parameter will be rejected and the default alignment will be used.
     464
     465Example: @int b = alloc( 5 , 64`align )@
    403466This call will return a dynamic array of five integers. It will align the allocated object to 64.
    404467
    405468\paragraph{Fill}
    406 This parameter is position-free and uses a backtick routine fill (`fill). In case of realloc, only the extra space after copying the data in the old object will be filled with given parameter.
     469This parameter is position-free and uses a backtick routine fill (@`fill@). In case of @realloc@, only the extra space after copying the data in the old object will be filled with given parameter.
    407470Three types of parameters can be passed using `fill.
    408471
    409472\begin{itemize}
    410473\item
    411 char: A char can be passed with `fill to fill the whole dynamic allocation with the given char recursively till the end of required allocation.
    412 \item
    413 Object of returned type: An object of type of returned type can be passed with `fill to fill the whole dynamic allocation with the given object recursively till the end of required allocation.
    414 \item
    415 Dynamic object of returned type: A dynamic object of type of returned type can be passed with `fill to fill the dynamic allocation with the given dynamic object. In this case, the allocated memory is not filled recursively till the end of allocation. The filling happen untill the end object passed to `fill or the end of requested allocation reaches.
    416 \end{itemize}
    417 
    418 Example: int b = alloc( 5 , 'a'`fill )
     474@char@: A char can be passed with @`fill@ to fill the whole dynamic allocation with the given char recursively till the end of required allocation.
     475\item
     476Object of returned type: An object of type of returned type can be passed with @`fill@ to fill the whole dynamic allocation with the given object recursively till the end of required allocation.
     477\item
     478Dynamic object of returned type: A dynamic object of type of returned type can be passed with @`fill@ to fill the dynamic allocation with the given dynamic object. In this case, the allocated memory is not filled recursively till the end of allocation. The filling happen untill the end object passed to @`fill@ or the end of requested allocation reaches.
     479\end{itemize}
     480
     481Example: @int b = alloc( 5 , 'a'`fill )@
    419482This call will return a dynamic array of five integers. It will fill the allocated object with character 'a' recursively till the end of requested allocation size.
    420483
    421 Example: int b = alloc( 5 , 4`fill )
     484Example: @int b = alloc( 5 , 4`fill )@
    422485This call will return a dynamic array of five integers. It will fill the allocated object with integer 4 recursively till the end of requested allocation size.
    423486
    424 Example: int b = alloc( 5 , a`fill ) where a is a pointer of int type
     487Example: @int b = alloc( 5 , a`fill )@ where @a@ is a pointer of int type
    425488This call will return a dynamic array of five integers. It will copy data in a to the returned object non-recursively untill end of a or the newly allocated object is reached.
    426489
    427490\paragraph{Resize}
    428 This parameter is position-free and uses a backtick routine resize (`resize). It represents the old dynamic object (oaddr) that the programmer wants to
     491This parameter is position-free and uses a backtick routine resize (@`resize@). It represents the old dynamic object (oaddr) that the programmer wants to
    429492\begin{itemize}
    430493\item
    … …  
    435498fill with something.
    436499\end{itemize}
    437 The data in old dynamic object will not be preserved in the new object. The type of object passed to `resize and the returned type of alloc call can be different.
    438 
    439 Example: int b = alloc( 5 , a`resize )
     500The data in old dynamic object will not be preserved in the new object. The type of object passed to @`resize@ and the returned type of alloc call can be different.
     501
     502Example: @int b = alloc( 5 , a`resize )@
    440503This call will resize object a to a dynamic array that can contain 5 integers.
    441504
    442 Example: int b = alloc( 5 , a`resize , 32`align )
     505Example: @int b = alloc( 5 , a`resize , 32`align )@
    443506This call will resize object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32.
    444507
    445 Example: int b = alloc( 5 , a`resize , 32`align , 2`fill)
     508Example: @int b = alloc( 5 , a`resize , 32`align , 2`fill )@
    446509This call will resize object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32 and will be filled with 2.
    447510
    448511\paragraph{Realloc}
    449 This parameter is position-free and uses a backtick routine realloc (`realloc). It represents the old dynamic object (oaddr) that the programmer wants to
     512This parameter is position-free and uses a backtick routine @realloc@ (@`realloc@). It represents the old dynamic object (oaddr) that the programmer wants to
    450513\begin{itemize}
    451514\item
    … …  
    456519fill with something.
    457520\end{itemize}
    458 The data in old dynamic object will be preserved in the new object. The type of object passed to `realloc and the returned type of alloc call cannot be different.
    459 
    460 Example: int b = alloc( 5 , a`realloc )
     521The data in old dynamic object will be preserved in the new object. The type of object passed to @`realloc@ and the returned type of alloc call cannot be different.
     522
     523Example: @int b = alloc( 5 , a`realloc )@
    461524This call will realloc object a to a dynamic array that can contain 5 integers.
    462525
    463 Example: int b = alloc( 5 , a`realloc , 32`align )
     526Example: @int b = alloc( 5 , a`realloc , 32`align )@
    464527This call will realloc object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32.
    465528
    466 Example: int b = alloc( 5 , a`realloc , 32`align , 2`fill)
     529Example: @int b = alloc( 5 , a`realloc , 32`align , 2`fill )@
    467530This call will resize object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32. The extra space after copying data of a to the returned object will be filled with 2.

  • doc/theses/mubeen_zulfiqar_MMath/background.tex

    ref3c383 rd672350  
    1 \chapter{Background}
    2 
    3 \noindent
     1\begin{comment}
    42====================
    5 
    63Writing Points:
    74\begin{itemize}
    … …  
    1916Features and limitations.
    2017\end{itemize}
    21 
    22 \noindent
    23 ====================
    24 
    25 \section{Background}
    26 
    27 % FIXME: cite wasik
    28 \cite{wasik.thesis}
    29 
    30 \subsection{Memory Allocation}
    31 With dynamic allocation being an important feature of C, there are many standalone memory allocators that have been designed for different purposes. For this thesis, we chose 7 of the most popular and widely used memory allocators.
    32 
    33 \paragraph{dlmalloc}
    34 dlmalloc (FIX ME: cite allocator) is a thread-safe allocator that is single threaded and single heap. dlmalloc maintains free-lists of different sizes to store freed dynamic memory. (FIX ME: cite wasik)
    35 
    36 \paragraph{hoard}
    37 Hoard (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and using a heap layer framework. It has per-thred heaps that have thread-local free-lists, and a gloabl shared heap. (FIX ME: cite wasik)
    38 
    39 \paragraph{jemalloc}
    40 jemalloc (FIX ME: cite allocator) is a thread-safe allocator that uses multiple arenas. Each thread is assigned an arena. Each arena has chunks that contain contagious memory regions of same size. An arena has multiple chunks that contain regions of multiple sizes.
    41 
    42 \paragraph{ptmalloc}
    43 ptmalloc (FIX ME: cite allocator) is a modification of dlmalloc. It is a thread-safe multi-threaded memory allocator that uses multiple heaps. ptmalloc heap has similar design to dlmalloc's heap.
    44 
    45 \paragraph{rpmalloc}
    46 rpmalloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses per-thread heap. Each heap has multiple size-classes and each size-calss contains memory regions of the relevant size.
    47 
    48 \paragraph{tbb malloc}
    49 tbb malloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses private heap for each thread. Each private-heap has multiple bins of different sizes. Each bin contains free regions of the same size.
    50 
    51 \paragraph{tc malloc}
    52 tcmalloc (FIX ME: cite allocator) is a thread-safe allocator. It uses per-thread cache to store free objects that prevents contention on shared resources in multi-threaded application. A central free-list is used to refill per-thread cache when it gets empty.
    53 
    54 \subsection{Benchmarks}
    55 There are multiple benchmarks that are built individually and evaluate different aspects of a memory allocator. But, there is not standard set of benchamrks that can be used to evaluate multiple aspects of memory allocators.
    56 
    57 \paragraph{threadtest}
    58 (FIX ME: cite benchmark and hoard) Each thread repeatedly allocates and then deallocates 100,000 objects. Runtime of the benchmark evaluates its efficiency.
    59 
    60 \paragraph{shbench}
    61 (FIX ME: cite benchmark and hoard) Each thread allocates and randomly frees a number of random-sized objects. It is a stress test that also uses runtime to determine efficiency of the allocator.
    62 
    63 \paragraph{larson}
    64 (FIX ME: cite benchmark and hoard) Larson simulates a server environment. Multiple threads are created where each thread allocator and free a number of objects within a size range. Some objects are passed from threads to the child threads to free. It caluculates memory operations per second as an indicator of memory allocator's performance.
     18\end{comment}
     19
     20\chapter[Background]{Background\footnote{Part of this chapter draws from similar background work in~\cite{wasik.thesis} 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 flows into 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.
     40\begin{figure}[h]
     41\centering
     42\input{AllocatorComponents}
     43\caption{Allocator Components (Heap)}
     44\label{f:AllocatorComponents}
     45\end{figure}
     46Freed objects (light grey) are memory deallocated by the program, which are linked into one or more lists facilitating easy location for 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
     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.
     61
     62\begin{figure}
     63\centering
     64\input{AllocatedObject}
     65\caption{Allocated Object}
     66\label{f:AllocatedObject}
     67\end{figure}
     68
     69
     70\section{Single-Threaded Memory-Allocator}
     71\label{s:SingleThreadedMemoryAllocator}
     72
     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.
     76
     77
     78\subsection{Fragmentation}
     79\label{s:Fragmentation}
     80
     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.
     84
     85\begin{figure}
     86\centering
     87\input{IntExtFragmentation}
     88\caption{Internal and External Fragmentation}
     89\label{f:InternalExternalFragmentation}
     90\end{figure}
     91
     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.
     97
     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 freed objects, all external management data, 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.
     108
     109\begin{figure}
     110\centering
     111\input{MemoryFragmentation}
     112\caption{Memory Fragmentation}
     113\label{f:MemoryFragmentation}
     114\vspace{10pt}
     115\subfigure[Contiguous]{
     116        \input{ContigFragmentation}
     117        \label{f:Contiguous}
     118} % subfigure
     119        \subfigure[Highly Fragmented]{
     120        \input{NonContigFragmentation}
     121\label{f:HighlyFragmented}
     122} % subfigure
     123\caption{Fragmentation Quality}
     124\label{f:FragmentationQuality}
     125\end{figure}
     126
     127For a single-threaded memory allocator, three basic approaches for controlling fragmentation have been 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.
     132
     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, possibly with 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.
     142
     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.
     151
     152
     153\subsection{Locality}
     154\label{s:Locality}
     155
     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.
     159
     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.}.
     164
     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.
     171
     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.
     177
     178
     179\section{Multi-Threaded Memory-Allocator}
     180\label{s:MultiThreadedMemoryAllocator}
     181
     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 locality and fragmentation, a multi-threaded allocator may be simultaneously accessed by multiple threads, and hence, must deal with concurrency issues such as mutual exclusion, false sharing, and additional forms of heap blowup.
     184
     185
     186\subsection{Mutual Exclusion}
     187\label{s:MutualExclusion}
     188
     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:
     194using multiple fine-grained locks versus a single lock, spreading the contention across a number of locks;
     195using trylock and generating new storage if the lock is busy, yielding a classic space versus time tradeoff;
     196using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Oyama99}.
     197However, all of these approaches have degenerate cases where contention occurs.
     198
     199
     200\subsection{False Sharing}
     201\label{s:FalseSharing}
     202
     203False sharing is a dynamic phenomenon leading to cache thrashing.
     204When 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.
     205False sharing can occur in three different ways: program induced, allocator-induced active, and allocator-induced passive;
     206a memory allocator can only affect the latter two.
     207
     208\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.
     209\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$.
     210Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
     211
     212\begin{figure}
     213\centering
     214\subfigure[Program-Induced False-Sharing]{
     215        \input{ProgramFalseSharing}
     216        \label{f:ProgramInducedFalseSharing}
     217} \\
     218\vspace{5pt}
     219\subfigure[Allocator-Induced Active False-Sharing]{
     220        \input{AllocInducedActiveFalseSharing}
     221        \label{f:AllocatorInducedActiveFalseSharing}
     222} \\
     223\vspace{5pt}
     224\subfigure[Allocator-Induced Passive False-Sharing]{
     225        \input{AllocInducedPassiveFalseSharing}
     226        \label{f:AllocatorInducedPassiveFalseSharing}
     227} % subfigure
     228\caption{False Sharing}
     229\label{f:FalseSharing}
     230\end{figure}
     231
     232\paragraph{\newterm{Allocator-induced active false-sharing}} occurs when objects are allocated within the same cache line but to different threads.
     233For example, in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}, each task allocates an object and loads a cache-line of memory into its associated cache.
     234Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
     235
     236\paragraph{\newterm{Allocator-induced passive false-sharing}} is another form of allocator-induced false-sharing caused by program-induced false-sharing.
     237When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing.
     238For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Task$_1$ passes Object$_2$ to Task$_2$, and Task$_2$ subsequently deallocates Object$_2$.
     239Allocator-induced passive false-sharing occurs when Object$_2$ is reallocated to Task$_2$ while Task$_1$ is still using Object$_1$.
     240
     241
     242\subsection{Heap Blowup}
     243\label{s:HeapBlowup}
     244
     245In a multi-threaded program, heap blowup can occur when memory freed by one thread is inaccessible to other threads due to the allocation strategy.
     246Specific examples are presented in later sections.
     247
     248
     249\section{Multi-Threaded Memory-Allocator Features}
     250\label{s:MultiThreadedMemoryAllocatorFeatures}
     251
     252The following features are used in the construction of multi-threaded memory-allocators:
     253\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
     254\item multiple heaps
     255\begin{list}{\alph{enumii})}{\usecounter{enumii}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
     256\item with or without a global heap
     257\item with or without ownership
     258\end{list}
     259\item object containers
     260\begin{list}{\alph{enumii})}{\usecounter{enumii}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
     261\item with or without ownership
     262\item fixed or variable sized
     263\item global or local free-lists
     264\end{list}
     265\item hybrid private/public heap
     266\item allocation buffer
     267\item lock-free operations
     268\end{list}
     269The first feature, multiple heaps, pertains to different kinds of heaps.
     270The second feature, object containers, pertains to the organization of objects within the storage area.
     271The remaining features apply to different parts of the allocator design or implementation.
     272
     273
     274\section{Multiple Heaps}
     275\label{s:MultipleHeaps}
     276
     277A single-threaded allocator has at most one thread and heap, while a multi-threaded allocator has potentially multiple threads and heaps.
     278The multiple threads cause complexity, and multiple heaps are a mechanism for dealing with the complexity.
     279The 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.
     280
     281
     282\paragraph{T:1 model} where all threads allocate and deallocate objects from one heap.
     283Memory is obtained from the freed objects, or reserved memory in the heap, or from the operating system (OS);
     284the heap may also return freed memory to the operating system.
     285The 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.
     286To safely handle concurrency, a single heap uses locking to provide mutual exclusion.
     287Whether 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.
     288
     289\begin{figure}
     290\centering
     291\subfigure[T:1]{
     292%       \input{SingleHeap.pstex_t}
     293        \input{SingleHeap}
     294        \label{f:SingleHeap}
     295} % subfigure
     296\vrule
     297\subfigure[T:H]{
     298%       \input{MultipleHeaps.pstex_t}
     299        \input{SharedHeaps}
     300        \label{f:SharedHeaps}
     301} % subfigure
     302\vrule
     303\subfigure[1:1]{
     304%       \input{MultipleHeapsGlobal.pstex_t}
     305        \input{PerThreadHeap}
     306        \label{f:PerThreadHeap}
     307} % subfigure
     308\caption{Multiple Heaps, Thread:Heap Relationship}
     309\end{figure}
     310
     311
     312\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.
     313The decision on when to create a new heap and which heap a thread allocates from depends on the allocator design.
     314The performance goal is to reduce the ratio of heaps to threads.
     315In 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.
     316
     317For 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.
     318At creation, a thread is associated with a heap from the pool.
     319When the thread attempts an allocation and its associated heap is locked (contention), it scans for an unlocked heap in the pool.
     320If an unlocked heap is found, the thread changes its association and uses that heap.
     321If all heaps are locked, the thread may create a new heap, use it, and then place the new heap into the pool;
     322or the thread can block waiting for a heap to become available.
     323While the heap-pool approach often minimizes the number of extant heaps, the worse case can result in more heaps than threads;
     324\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.
     325
     326Threads using multiple heaps need to determine the specific heap to access for an allocation/deallocation, \ie association of thread to heap.
     327A number of techniques are used to establish this association.
     328The 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.
     329For threading systems with thread-local storage, the heap pointer is created using this mechanism;
     330otherwise, 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.
     331
     332The storage management for multiple heaps is more complex than for a single heap (see \VRef[Figure]{f:AllocatorComponents}).
     333\VRef[Figure]{f:MultipleHeapStorage} illustrates the general storage layout for multiple heaps.
     334Allocated and free objects are labelled by the thread or heap they are associated with.
     335(Links between free objects are removed for simplicity.)
     336The management information in the static zone must be able to locate all heaps in the dynamic zone.
     337The management information for the heaps must reside in the dynamic-allocation zone if there are a variable number.
     338Each heap in the dynamic zone is composed of a list of a free objects and a pointer to its reserved memory.
     339An 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.
     340Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
     341Other 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.
     342
     343\begin{figure}
     344\centering
     345\input{MultipleHeapsStorage}
     346\caption{Multiple-Heap Storage}
     347\label{f:MultipleHeapStorage}
     348\end{figure}
     349
     350Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup.
     351The 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.
     352Additionally, 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.
     353(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.)
     354In 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.
     355
     356Adding 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.
     357Now, each heap obtains and returns storage to/from the global heap rather than the operating system.
     358Storage 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.
     359Similarly, the global heap buffers this memory, obtaining and returning storage to/from the operating system as necessary.
     360The global heap does not have its own thread and makes no internal allocation requests;
     361instead, it uses the application thread, which called one of the multiple heaps and then the global heap, to perform operations.
     362Hence, the worst-case cost of a memory operation includes all these steps.
     363With 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.
     364
     365However, since any thread may indirectly perform a memory operation on the global heap, it is a shared resource that requires locking.
     366A single lock can be used to protect the global heap or fine-grained locking can be used to reduce contention.
     367In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap.
     368
     369
     370\paragraph{1:1 model (thread heaps)} where each thread has its own heap, which eliminates most contention and locking because threads seldom accesses another thread's heap (see ownership in \VRef{s:Ownership}).
     371An additional benefit of thread heaps is improved locality due to better memory layout.
     372As 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.
     373In contrast, the T:H model spreads each thread's objects over a larger area in different heaps.
     374Thread 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.
     375For 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.
     376Hence, allocator-induced active false-sharing in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing} cannot occur because the memory for thread heaps never overlaps.
     377
     378When a thread terminates, there are two options for handling its heap.
     379First is to free all objects in the heap to the global heap and destroy the thread heap.
     380Second is to place the thread heap on a list of available heaps and reuse it for a new thread in the future.
     381Destroying 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.
     382Alternatively, reusing thread heaps may improve performance if the inheriting thread makes similar allocation requests as the thread that previously held the thread heap.
     383
     384
     385\subsection{User-Level Threading}
     386
     387It is possible to use any of the heap models with user-level (M:N) threading.
     388However, 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).
     389It is difficult to retain this goal, if the user-threading model is directly involved with the heap model.
     390\VRef[Figure]{f:UserLevelKernelHeaps} shows that virtually all user-level threading systems use whatever kernel-level heap-model provided by the language runtime.
     391Hence, a user thread allocates/deallocates from/to the heap of the kernel thread on which it is currently executing.
     392
     393\begin{figure}
     394\centering
     395\input{UserKernelHeaps}
     396\caption{User-Level Kernel Heaps}
     397\label{f:UserLevelKernelHeaps}
     398\end{figure}
     399
     400Adopting this model results in a subtle problem with shared heaps.
     401With kernel threading, an operation that is started by a kernel thread is always completed by that thread.
     402For example, if a kernel thread starts an allocation/deallocation on a shared heap, it always completes that operation with that heap even if preempted.
     403Any correctness locking associated with the shared heap is preserved across preemption.
     404
     405However, this correctness property is not preserved for user-level threading.
     406A 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}.
     407When 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.
     408To 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.
     409However, eagerly disabling/enabling time-slicing on the allocation/deallocation fast path is expensive, because preemption is rare (10--100 milliseconds).
     410Instead, techniques exist to lazily detect this case in the interrupt handler, abort the preemption, and return to the operation so it can complete atomically.
     411Occasionally ignoring a preemption should be benign.
     412
     413
     414\begin{figure}
     415\centering
     416\subfigure[Ownership]{
     417        \input{MultipleHeapsOwnership}
     418} % subfigure
     419\hspace{0.25in}
     420\subfigure[No Ownership]{
     421        \input{MultipleHeapsNoOwnership}
     422} % subfigure
     423\caption{Heap Ownership}
     424\label{f:HeapsOwnership}
     425\end{figure}
     426
     427
     428\subsection{Ownership}
     429\label{s:Ownership}
     430
     431\newterm{Ownership} defines which heap an object is returned-to on deallocation.
     432If a thread returns an object to the heap it was originally allocated from, the heap has ownership of its objects.
     433Alternatively, a thread can return an object to the heap it is currently allocating from, which can be any heap accessible during a thread's lifetime.
     434\VRef[Figure]{f:HeapsOwnership} shows an example of multiple heaps (minus the global heap) with and without ownership.
     435Again, the arrows indicate the direction memory conceptually moves for each kind of operation.
     436For 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}.
     437For 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}.
     438
     439\VRef[Figure]{f:MultipleHeapStorageOwnership} shows the effect of ownership on storage layout.
     440(For simplicity assume the heaps all use the same size of reserves storage.)
     441In 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.
     442Again, because multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
     443The 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.
     444In 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.
     445As 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.
     446% Passive false-sharing may still occur, if delayed ownership is used (see below).
     447
     448\begin{figure}
     449\centering
     450\input{MultipleHeapsOwnershipStorage.pstex_t}
     451\caption{Multiple-Heap Storage with Ownership}
     452\label{f:MultipleHeapStorageOwnership}
     453\end{figure}
     454
     455The main advantage of ownership is preventing heap blowup by returning storage for reuse by the owner heap.
     456Ownership 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.
     457As 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.
     458For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, the deallocation by Task$_2$ returns Object$_2$ back to Task$_1$'s heap;
     459hence a subsequent allocation by Task$_2$ cannot return this storage.
     460The disadvantage of ownership is deallocating to another task's heap so heaps are no longer private and require locks to provide safe concurrent access.
     461
     462Object ownership can be immediate or delayed, meaning free objects may be batched on a separate free list either by the returning or receiving thread.
     463While 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.
     464It 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.
     465Batching 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.
     466
     467It is possible for heaps to steal objects rather than return them and reallocating these objects when storage runs out on a heap.
     468However, stealing can result in passive false-sharing.
     469For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Task$_2$'s heap initially.
     470If Task$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.
     471
     472
     473\section{Object Containers}
     474\label{s:ObjectContainers}
     475
     476Bracketing every allocation with headers/trailers can result in significant internal fragmentation, as shown in \VRef[Figure]{f:ObjectHeaders}.
     477Especially 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.
     478As 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.
     479Spatial locality can also be negatively affected leading to poor cache locality~\cite{Feng05}:
     480while the header and object are together in memory, they are generally not accessed together;
     481\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.
     482
     483\begin{figure}
     484\centering
     485\subfigure[Object Headers]{
     486        \input{ObjectHeaders}
     487        \label{f:ObjectHeaders}
     488} % subfigure
     489\subfigure[Object Container]{
     490        \input{Container}
     491        \label{f:ObjectContainer}
     492} % subfigure
     493\caption{Header Placement}
     494\label{f:HeaderPlacement}
     495\end{figure}
     496
     497An 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}.
     498The header for the container holds information necessary for all objects in the container;
     499a trailer may also be used at the end of the container.
     500Similar 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.
     501
     502The 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.
     503One 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).
     504For 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.
     505
     506Normally, 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).
     507This 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.
     508However, although similar objects are close spatially within the same container, different sized objects are further apart in separate containers.
     509Depending on the program, this may or may not improve locality.
     510If 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.
     511If the program uses many containers, there is poor locality, as both caching and paging increase.
     512Another 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.
     513However, external fragmentation can be reduced by using small containers.
     514
     515Containers with heterogeneous objects implies different headers describing them, which complicates the problem of locating a specific header solely by an address.
     516A couple of solutions can be used to implement containers with heterogeneous objects.
     517However, the problem with allowing objects of different sizes is that the number of objects, and therefore headers, in a single container is unpredictable.
     518One solution allocates headers at one end of the container, while allocating objects from the other end of the container;
     519when the headers meet the objects, the container is full.
     520Freed objects cannot be split or coalesced since this causes the number of headers to change.
     521The difficulty in this strategy remains in finding the header for a specific object;
     522in general, a search is necessary to find the object's header among the container headers.
     523A second solution combines the use of container headers and individual object headers.
     524Each 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.
     525This approach allows containers to hold different types of objects, but does not completely separate headers from objects.
     526The benefit of the container in this case is to reduce some redundant information that is factored into the container header.
     527
     528In 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.
     529A consequence of this tradeoff is its effect on spatial locality, which can produce positive or negative results depending on program access-patterns.
     530
     531
     532\subsection{Container Ownership}
     533\label{s:ContainerOwnership}
     534
     535Without ownership, objects in a container are deallocated to the heap currently associated with the thread that frees the object.
     536Thus, different objects in a container may be on different heap free-lists (see \VRef[Figure]{f:ContainerNoOwnershipFreelist}).
     537With 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.
     538If multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
     539Only with the 1:1 model and ownership is active and passive false-sharing avoided (see \VRef{s:Ownership}).
     540Passive false-sharing may still occur, if delayed ownership is used.
     541
     542\begin{figure}
     543\centering
     544\subfigure[No Ownership]{
     545        \input{ContainerNoOwnershipFreelist}
     546        \label{f:ContainerNoOwnershipFreelist}
     547} % subfigure
     548\vrule
     549\subfigure[Ownership]{
     550        \input{ContainerOwnershipFreelist}
     551        \label{f:ContainerOwnershipFreelist}
     552} % subfigure
     553\caption{Free-list Structure with Container Ownership}
     554\end{figure}
     555
     556A fragmented heap has multiple containers that may be partially or completely free.
     557A completely free container can become reserved storage and be reset to allocate objects of a new size.
     558When a heap reaches a threshold of free objects, it moves some free storage to the global heap for reuse to prevent heap blowup.
     559Without ownership, when a heap frees objects to the global heap, individual objects must be passed, and placed on the global-heap's free-list.
     560Containers cannot be freed to the global heap unless completely free because
     561
     562When a container changes ownership, the ownership of all objects within it change as well.
     563Moving a container involves moving all objects on the heap's free-list in that container to the new owner.
     564This approach can reduce contention for the global heap, since each request for objects from the global heap returns a container rather than individual objects.
     565
     566Additional restrictions may be applied to the movement of containers to prevent active false-sharing.
     567For example, in \VRef[Figure]{f:ContainerFalseSharing1}, a container being used by Task$_1$ changes ownership, through the global heap.
     568In \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.
     569Note, once the object is freed by Task$_1$, no more false sharing can occur until the container changes ownership again.
     570To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free.
     571One 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.
     572
     573\begin{figure}
     574\centering
     575\subfigure[]{
     576        \input{ContainerFalseSharing1}
     577        \label{f:ContainerFalseSharing1}
     578} % subfigure
     579\subfigure[]{
     580        \input{ContainerFalseSharing2}
     581        \label{f:ContainerFalseSharing2}
     582} % subfigure
     583\caption{Active False-Sharing using Containers}
     584\label{f:ActiveFalseSharingContainers}
     585\end{figure}
     586
     587Using containers with ownership increases external fragmentation since a new container for a requested object size must be allocated separately for each thread requesting it.
     588In \VRef[Figure]{f:ExternalFragmentationContainerOwnership}, using object ownership allocates 80\% more space than without ownership.
     589
     590\begin{figure}
     591\centering
     592\subfigure[No Ownership]{
     593        \input{ContainerNoOwnership}
     594} % subfigure
     595\\
     596\subfigure[Ownership]{
     597        \input{ContainerOwnership}
     598} % subfigure
     599\caption{External Fragmentation with Container Ownership}
     600\label{f:ExternalFragmentationContainerOwnership}
     601\end{figure}
     602
     603
     604\subsection{Container Size}
     605\label{s:ContainerSize}
     606
     607One 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.
     608As 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).
     609Aligning containers in this manner also determines the size of the container.
     610However, the size of the container has different implications for the allocator.
     611
     612The 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.
     613However, with more objects in a container, there may be more objects that are unallocated, increasing external fragmentation.
     614With smaller containers, not only are there more containers, but a second new problem arises where objects are larger than the container.
     615In 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.
     616If 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.
     617Ideally, 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.
     618
     619In order to find the container header when using different sized containers, a super container is used (see~\VRef[Figure]{f:SuperContainers}).
     620The super container spans several containers, contains a header with information for finding each container header, and starts on an aligned address.
     621Super-container headers are found using the same method used to find container headers by dropping the lower bits of an object address.
     622The containers within a super container may be different sizes or all the same size.
     623If 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.
     624If all containers in the super container are the same size, \eg 16KB, then a specific container header can be found by a simple calculation.
     625The free space at the end of a super container is used to allocate new containers.
     626
     627\begin{figure}
     628\centering
     629\input{SuperContainers}
     630% \includegraphics{diagrams/supercontainer.eps}
     631\caption{Super Containers}
     632\label{f:SuperContainers}
     633\end{figure}
     634
     635Minimal internal and external fragmentation is achieved by having as few containers as possible, each being as full as possible.
     636It 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.
     637However, this approach assumes it is possible for an allocator to determine in advance which sizes are popular.
     638Keeping statistics on requested sizes allows the allocator to make a dynamic decision about which sizes are popular.
     639For 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.
     640If the decision is incorrect, larger containers than necessary are allocated that remain mostly unused.
     641A 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.
     642
     643
     644\subsection{Container Free-Lists}
     645\label{s:containersfreelists}
     646
     647The container header allows an alternate approach for managing the heap's free-list.
     648Rather 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}).
     649Note, maintaining free lists within a container assumes all free objects in the container are associated with the same heap;
     650thus, this approach only applies to containers with ownership.
     651
     652This alternate free-list approach can greatly reduce the complexity of moving all freed objects belonging to a container to another heap.
     653To 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.
     654Each object is then removed from the free list and linked together to form a local free-list for the move to the new heap.
     655With 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.
     656Thus, when using local free-lists, the operation of moving containers is reduced from $O(N)$ to $O(1)$.
     657The cost is adding information to a header, which increases the header size, and therefore internal fragmentation.
     658
     659\begin{figure}
     660\centering
     661\subfigure[Global Free-List Among Containers]{
     662        \input{FreeListAmongContainers}
     663        \label{f:GlobalFreeListAmongContainers}
     664} % subfigure
     665\hspace{0.25in}
     666\subfigure[Local Free-List Within Containers]{
     667        \input{FreeListWithinContainers}
     668        \label{f:LocalFreeListWithinContainers}
     669} % subfigure
     670\caption{Container Free-List Structure}
     671\label{f:ContainerFreeListStructure}
     672\end{figure}
     673
     674When all objects in the container are the same size, a single free-list is sufficient.
     675However, 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.
     676The alternative is to use a different allocation algorithm with a single free-list, such as a sequential-fit allocation-algorithm.
     677
     678
     679\subsection{Hybrid Private/Public Heap}
     680\label{s:HybridPrivatePublicHeap}
     681
     682Section~\Vref{s:Ownership} discusses advantages and disadvantages of public heaps (T:H model and with ownership) and private heaps (thread heaps with ownership).
     683For 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}).
     684The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
     685In 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.
     686Similarly, a task first deallocates an object its private heap, and second to the public heap.
     687Both 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.
     688Note, 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.
     689Finally, 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.
     690
     691\begin{figure}
     692\centering
     693\input{PrivatePublicHeaps.pstex_t}
     694\caption{Hybrid Private/Public Heap for Per-thread Heaps}
     695\label{f:HybridPrivatePublicHeap}
     696% \vspace{10pt}
     697% \input{RemoteFreeList.pstex_t}
     698% \caption{Remote Free-List}
     699% \label{f:RemoteFreeList}
     700\end{figure}
     701
     702As mentioned, an implementation may have only one heap deal with the global heap, so the other heap can be simplified.
     703For 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}.
     704To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
     705Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
     706Clearing 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.
     707
     708If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
     709In 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.
     710If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.
     711
     712The 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.
     713Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
     714In 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.
     715For 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.
     716
     717
     718\section{Allocation Buffer}
     719\label{s:AllocationBuffer}
     720
     721An 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.
     722That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
     723Both any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or operating system, respectively.
     724The allocation buffer reduces contention and the number of global/operating-system calls.
     725For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.
     726
     727Allocation buffers are useful initially when there are no freed objects in a heap because many allocations usually occur when a thread starts.
     728Furthermore, to prevent heap blowup, objects should be reused before allocating a new allocation buffer.
     729Thus, allocation buffers are often allocated more frequently at program/thread start, and then their use often diminishes.
     730
     731Using an allocation buffer with a thread heap avoids active false-sharing, since all objects in the allocation buffer are allocated to the same thread.
     732For 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.
     733Active false-sharing may still occur if objects are freed to the global heap and reused by another heap.
     734
     735Allocation buffers may increase external fragmentation, since some memory in the allocation buffer may never be allocated.
     736A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or operating system.
     737The allocation buffer also slightly increases internal fragmentation, since a pointer is necessary to locate the next free object in the buffer.
     738
     739The unused part of a container, neither allocated or freed, is an allocation buffer.
     740For 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.
     741This lazy method of constructing objects is beneficial in terms of paging and caching.
     742For 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.
     743
     744
     745\section{Lock-Free Operations}
     746\label{s:LockFreeOperations}
     747
     748A lock-free algorithm guarantees safe concurrent-access to a data structure, so that at least one thread can make progress in the system, but an individual task has no bound to execution, and hence, may starve~\cite[pp.~745--746]{Herlihy93}.
     749% A wait-free algorithm puts a finite bound on the number of steps any thread takes to complete an operation, so an individual task cannot starve
     750Lock-free operations can be used in an allocator to reduce or eliminate the use of locks.
     751Locks are a problem for high contention or if the thread holding the lock is preempted and other threads attempt to use that lock.
     752With respect to the heap, these situations are unlikely unless all threads makes extremely high use of dynamic-memory allocation, which can be an indication of poor design.
     753Nevertheless, lock-free algorithms can reduce the number of context switches, since a thread does not yield/block while waiting for a lock;
     754on the other hand, a thread may busy-wait for an unbounded period.
     755Finally, lock-free implementations have greater complexity and hardware dependency.
     756Lock-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.
     757Implementing lock-free operations for more complex data-structures (queue~\cite{Valois94}/deque~\cite{Sundell08}) is more complex.
     758Michael~\cite{Michael04} and Gidenstam \etal \cite{Gidenstam05} have created lock-free variations of the Hoard allocator.

  • doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

    ref3c383 rd672350  
    4141%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    4242
     43
     44\section{Benchmarks}
     45There are multiple benchmarks that are built individually and evaluate different aspects of a memory allocator. But, there is not standard set of benchamrks that can be used to evaluate multiple aspects of memory allocators.
     46
     47\paragraph{threadtest}
     48(FIX ME: cite benchmark and hoard) Each thread repeatedly allocates and then deallocates 100,000 objects. Runtime of the benchmark evaluates its efficiency.
     49
     50\paragraph{shbench}
     51(FIX ME: cite benchmark and hoard) Each thread allocates and randomly frees a number of random-sized objects. It is a stress test that also uses runtime to determine efficiency of the allocator.
     52
     53\paragraph{larson}
     54(FIX ME: cite benchmark and hoard) Larson simulates a server environment. Multiple threads are created where each thread allocator and free a number of objects within a size range. Some objects are passed from threads to the child threads to free. It caluculates memory operations per second as an indicator of memory allocator's performance.
     55
     56
    4357\section{Performance Matrices of Memory Allocators}
    4458

  • doc/theses/mubeen_zulfiqar_MMath/intro.tex

    ref3c383 rd672350  
    11\chapter{Introduction}
    22
     3% Shared-memory multi-processor computers are ubiquitous and important for improving application performance.
     4% However, writing programs that take advantage of multiple processors is not an easy task~\cite{Alexandrescu01b}, \eg shared resources can become a bottleneck when increasing (scaling) threads.
     5% One crucial shared resource is program memory, since it is used by all threads in a shared-memory concurrent-program~\cite{Berger00}.
     6% Therefore, providing high-performance, scalable memory-management is important for virtually all shared-memory multi-threaded programs.
     7
     8\vspace*{-23pt}
     9Memory management takes a sequence of program generated allocation/deallocation requests and attempts to satisfy them within a fixed-sized block of memory while minimizing the total amount of memory used.
     10A general-purpose dynamic-allocation algorithm cannot anticipate future allocation requests so its output is rarely optimal.
     11However, memory allocators do take advantage of regularities in allocation patterns for typical programs to produce excellent results, both in time and space (similar to LRU paging).
     12In general, allocators use a number of similar techniques, each optimizing specific allocation patterns.
     13Nevertheless, memory allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific program-request patterns.
     14
     15
     16\section{Memory Structure}
     17\label{s:MemoryStructure}
     18
     19\VRef[Figure]{f:ProgramAddressSpace} shows the typical layout of a program's address space divided into the following zones (right to left): static code/data, dynamic allocation, dynamic code/data, and stack, with free memory surrounding the dynamic code/data~\cite{memlayout}.
     20Static code and data are placed into memory at load time from the executable and are fixed-sized at runtime.
     21Dynamic-allocation memory starts empty and grows/shrinks as the program dynamically creates/deletes variables with independent lifetime.
     22The programming-language's runtime manages this area, where management complexity is a function of the mechanism for deleting variables.
     23Dynamic code/data memory is managed by the dynamic loader for libraries loaded at runtime, which is complex especially in a multi-threaded program~\cite{Huang06}.
     24However, changes to the dynamic code/data space are typically infrequent, many occurring at program startup, and are largely outside of a program's control.
     25Stack memory is managed by the program call-mechanism using a simple LIFO technique, which works well for sequential programs.
     26For multi-threaded programs (and coroutines), a new stack is created for each thread;
     27these thread stacks are commonly created in dynamic-allocation memory.
     28This thesis focuses on management of the dynamic-allocation memory.
     29
     30\begin{figure}
     31\centering
     32\input{AddressSpace}
     33\vspace{-5pt}
     34\caption{Program Address Space Divided into Zones}
     35\label{f:ProgramAddressSpace}
     36\end{figure}
     37
     38
     39\section{Dynamic Memory-Management}
     40\label{s:DynamicMemoryManagement}
     41
     42Modern programming languages manage dynamic-allocation memory in different ways.
     43Some languages, such as Lisp~\cite{CommonLisp}, Java~\cite{Java}, Haskell~\cite{Haskell}, Go~\cite{Go}, provide explicit allocation but \emph{implicit} deallocation of data through garbage collection~\cite{Wilson92}.
     44In general, garbage collection supports memory compaction, where dynamic (live) data is moved during runtime to better utilize space.
     45However, moving data requires finding pointers to it and updating them to reflect new data locations.
     46Programming languages such as C~\cite{C}, \CC~\cite{C++}, and Rust~\cite{Rust} provide the programmer with explicit allocation \emph{and} deallocation of data.
     47These languages cannot find and subsequently move live data because pointers can be created to any storage zone, including internal components of allocated objects, and may contain temporary invalid values generated by pointer arithmetic.
     48Attempts have been made to perform quasi garbage collection in C/\CC~\cite{Boehm88}, but it is a compromise.
     49This thesis only examines dynamic memory-management with \emph{explicit} deallocation.
     50While garbage collection and compaction are not part this work, many of the results are applicable to the allocation phase in any memory-management approach.
     51
     52Most programs use a general-purpose allocator, often the one provided implicitly by the programming-language's runtime.
     53When this allocator proves inadequate, programmers often write specialize allocators for specific needs.
     54C and \CC allow easy replacement of the default memory allocator with an alternative specialized or general-purpose memory-allocator.
     55(Jikes RVM MMTk~\cite{MMTk} provides a similar generalization for the Java virtual machine.)
     56However, high-performance memory-allocators for kernel and user multi-threaded programs are still being designed and improved.
     57For this reason, several alternative general-purpose allocators have been written for C/\CC with the goal of scaling in a multi-threaded program~\cite{Berger00,mtmalloc,streamflow,tcmalloc}.
     58This thesis examines the design of high-performance allocators for use by kernel and user multi-threaded applications written in C/\CC.
     59
     60
     61\section{Contributions}
     62\label{s:Contributions}
     63
     64This work provides the following contributions in the area of concurrent dynamic allocation:
     65\begin{enumerate}[leftmargin=*]
     66\item
     67Implementation of a new stand-lone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for programming languages \uC and \CFA using user-level threads running over multiple kernel threads (M:N threading).
     68
     69\item
     70Adopt returning of @nullptr@ for a zero-sized allocation, rather than an actual memory address, both of which can be passed to @free@.
     71
     72\item
     73Extended the standard C heap functionality by preserving with each allocation its original request size versus the amount allocated, if an allocation is zero fill, and the allocation alignment.
     74
     75\item
     76Use the zero fill and alignment as \emph{sticky} properties for @realloc@, to realign existing storage, or preserve existing zero-fill and alignment when storage is copied.
     77Without this extension, it is unsafe to @realloc@ storage initially allocated with zero-fill/alignment as these properties are not preserved when copying.
     78This silent generation of a problem is unintuitive to programmers and difficult to locate because it is transient.
     79
     80\item
     81Provide additional heap operations to complete programmer expectation with respect to accessing different allocation properties.
     82\begin{itemize}
     83\item
     84@resize( oaddr, size )@ re-purpose an old allocation for a new type \emph{without} preserving fill or alignment.
     85\item
     86@resize( oaddr, alignment, size )@ re-purpose an old allocation with new alignment but \emph{without} preserving fill.
     87\item
     88@realloc( oaddr, alignment, size )@ same as previous @realloc@ but adding or changing alignment.
     89\item
     90@aalloc( dim, elemSize )@ same as @calloc@ except memory is \emph{not} zero filled.
     91\item
     92@amemalign( alignment, dim, elemSize )@ same as @aalloc@ with memory alignment.
     93\item
     94@cmemalign( alignment, dim, elemSize )@ same as @calloc@ with memory alignment.
     95\end{itemize}
     96
     97\item
     98Provide additional heap wrapper functions in \CFA to provide a complete orthogonal set of allocation operations and properties.
     99
     100\item
     101Provide additional query operations to access information about an allocation:
     102\begin{itemize}
     103\item
     104@malloc_alignment( addr )@ returns the alignment of the allocation pointed-to by @addr@.
     105If the allocation is not aligned or @addr@ is the @nulladdr@, the minimal alignment is returned.
     106\item
     107@malloc_zero_fill( addr )@ returns a boolean result indicating if the memory pointed-to by @addr@ is allocated with zero fill, e.g., by @calloc@/@cmemalign@.
     108\item
     109@malloc_size( addr )@ returns the size of the memory allocation pointed-to by @addr@.
     110\item
     111@malloc_usable_size( addr )@ returns the usable size of the memory pointed-to by @addr@, i.e., the bin size containing the allocation, where @malloc_size( addr )@ $\le$ @malloc_usable_size( addr )@.
     112\end{itemize}
     113
     114\item
     115Provide mostly contention-free allocation and free operations via a heap-per-kernel-thread implementation.
     116
     117\item
     118Provide complete, fast, and contention-free allocation statistics to help understand program behaviour:
     119\begin{itemize}
     120\item
     121@malloc_stats()@ print memory-allocation statistics on the file-descriptor set by @malloc_stats_fd@.
     122\item
     123@malloc_info( options, stream )@ print memory-allocation statistics as an XML string on the specified file-descriptor set by @malloc_stats_fd@.
     124\item
     125@malloc_stats_fd( fd )@ set file-descriptor number for printing memory-allocation statistics (default @STDERR_FILENO@).
     126This file descriptor is used implicitly by @malloc_stats@ and @malloc_info@.
     127\end{itemize}
     128
     129\item
     130Provide extensive runtime checks to valid allocation operations and identify the amount of unfreed storage at program termination.
     131
     132\item
     133Build 4 different versions of the allocator:
     134\begin{itemize}
     135\item
     136static or dynamic linking
     137\item
     138statistic/debugging (testing) or no statistic/debugging (performance)
     139\end{itemize}
     140A program may link to any of these 4 versions of the allocator often without recompilation.
     141(It is possible to separate statistics and debugging, giving 8 different versions.)
     142
     143\item
     144A micro-benchmark test-suite for comparing allocators rather than relying on a suite of arbitrary programs.
     145These micro-benchmarks have adjustment knobs to simulate allocation patterns hard-coded into arbitrary test programs
     146\end{enumerate}
     147
     148\begin{comment}
    3149\noindent
    4150====================
    … …  
    26172
    27173\section{Introduction}
    28 Dynamic memory allocation and management is one of the core features of C. It gives programmer the freedom to allocate, free, use, and manage dynamic memory himself. The programmer is not given the complete control of the dynamic memory management instead an interface of memory allocator is given to the progrmmer that can be used to allocate/free dynamic memory for the application's use.
    29 
    30 Memory allocator is a layer between thr programmer and the system. Allocator gets dynamic memory from the system in heap/mmap area of application storage and manages it for programmer's use.
    31 
    32 GNU C Library (FIX ME: cite this) provides an interchangeable memory allocator that can be replaced with a custom memory allocator that supports required features and fulfills application's custom needs. It also allows others to innovate in memory allocation and design their own memory allocator. GNU C Library has set guidelines that should be followed when designing a standalone memory allocator. GNU C Library requires new memory allocators to have atlease following set of functions in their allocator's interface:
     174Dynamic memory allocation and management is one of the core features of C. It gives programmer the freedom to allocate, free, use, and manage dynamic memory himself. The programmer is not given the complete control of the dynamic memory management instead an interface of memory allocator is given to the programmer that can be used to allocate/free dynamic memory for the application's use.
     175
     176Memory allocator is a layer between the programmer and the system. Allocator gets dynamic memory from the system in heap/mmap area of application storage and manages it for programmer's use.
     177
     178GNU C Library (FIX ME: cite this) provides an interchangeable memory allocator that can be replaced with a custom memory allocator that supports required features and fulfills application's custom needs. It also allows others to innovate in memory allocation and design their own memory allocator. GNU C Library has set guidelines that should be followed when designing a stand-alone memory allocator. GNU C Library requires new memory allocators to have at lease following set of functions in their allocator's interface:
    33179
    34180\begin{itemize}
    … …  
    43189\end{itemize}
    44190
    45 In addition to the above functions, GNU C Library also provides some more functions to increase the usability of the dynamic memory allocator. Most standalone allocators also provide all or some of the above additional functions.
     191In addition to the above functions, GNU C Library also provides some more functions to increase the usability of the dynamic memory allocator. Most stand-alone allocators also provide all or some of the above additional functions.
    46192
    47193\begin{itemize}
    … …  
    60206\end{itemize}
    61207
    62 With the rise of concurrent applications, memory allocators should be able to fulfill dynamic memory requests from multiple threads in parallel without causing contention on shared resources. There needs to be a set of a standard benchmarks that can be used to evaluate an allocator's performance in different scenerios.
     208With the rise of concurrent applications, memory allocators should be able to fulfill dynamic memory requests from multiple threads in parallel without causing contention on shared resources. There needs to be a set of a standard benchmarks that can be used to evaluate an allocator's performance in different scenarios.
    63209
    64210\section{Research Objectives}
    … …  
    69215Design a lightweight concurrent memory allocator with added features and usability that are currently not present in the other memory allocators.
    70216\item
    71 Design a suite of benchmarks to evalute multiple aspects of a memory allocator.
     217Design a suite of benchmarks to evaluate multiple aspects of a memory allocator.
    72218\end{itemize}
    73219
    74220\section{An outline of the thesis}
    75221LAST FIX ME: add outline at the end
     222\end{comment}

  • doc/theses/mubeen_zulfiqar_MMath/performance.tex

    ref3c383 rd672350  
    1818\noindent
    1919====================
     20
     21\section{Machine Specification}
     22
     23The performance experiments were run on three different multicore systems to determine if there is consistency across platforms:
     24\begin{itemize}
     25\item
     26AMD EPYC 7662, 64-core socket $\times$ 2, 2.0 GHz
     27\item
     28Huawei ARM TaiShan 2280 V2 Kunpeng 920, 24-core socket $\times$ 4, 2.6 GHz
     29\item
     30Intel Xeon Gold 5220R, 48-core socket $\times$ 2, 2.20GHz
     31\end{itemize}
     32
     33
     34\section{Existing Memory Allocators}
     35With dynamic allocation being an important feature of C, there are many stand-alone memory allocators that have been designed for different purposes. For this thesis, we chose 7 of the most popular and widely used memory allocators.
     36
     37\paragraph{dlmalloc}
     38dlmalloc (FIX ME: cite allocator) is a thread-safe allocator that is single threaded and single heap. dlmalloc maintains free-lists of different sizes to store freed dynamic memory. (FIX ME: cite wasik)
     39
     40\paragraph{hoard}
     41Hoard (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and using a heap layer framework. It has per-thread heaps that have thread-local free-lists, and a global shared heap. (FIX ME: cite wasik)
     42
     43\paragraph{jemalloc}
     44jemalloc (FIX ME: cite allocator) is a thread-safe allocator that uses multiple arenas. Each thread is assigned an arena. Each arena has chunks that contain contagious memory regions of same size. An arena has multiple chunks that contain regions of multiple sizes.
     45
     46\paragraph{ptmalloc}
     47ptmalloc (FIX ME: cite allocator) is a modification of dlmalloc. It is a thread-safe multi-threaded memory allocator that uses multiple heaps. ptmalloc heap has similar design to dlmalloc's heap.
     48
     49\paragraph{rpmalloc}
     50rpmalloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses per-thread heap. Each heap has multiple size-classes and each size-class contains memory regions of the relevant size.
     51
     52\paragraph{tbb malloc}
     53tbb malloc (FIX ME: cite allocator) is a thread-safe allocator that is multi-threaded and uses private heap for each thread. Each private-heap has multiple bins of different sizes. Each bin contains free regions of the same size.
     54
     55\paragraph{tc malloc}
     56tcmalloc (FIX ME: cite allocator) is a thread-safe allocator. It uses per-thread cache to store free objects that prevents contention on shared resources in multi-threaded application. A central free-list is used to refill per-thread cache when it gets empty.
     57
    2058
    2159\section{Memory Allocators}

  • doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.bib

    ref3c383 rd672350  
    3434    year          = "2008"
    3535}
     36
     37@article{Sleator85,
     38    author      = {Sleator, Daniel Dominic and Tarjan, Robert Endre},
     39    title       = {Self-Adjusting Binary Search Trees},
     40    journal     = jacm,
     41    volume      = 32,
     42    number      = 3,
     43    year        = 1985,
     44    issn        = {0004-5411},
     45    pages       = {652-686},
     46    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/3828.3835},
     47    address     = {New York, NY, USA},
     48}
     49
     50@article{Berger00,
     51    author      = {Emery D. Berger and Kathryn S. McKinley and Robert D. Blumofe and Paul R. Wilson},
     52    title       = {Hoard: A Scalable Memory Allocator for Multithreaded Applications},
     53    booktitle   = {International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX)},
     54    journal     = sigplan,
     55    volume      = 35,
     56    number      = 11,
     57    month       = nov,
     58    year        = 2000,
     59    pages       = {117-128},
     60    note        = {International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX)},
     61}
     62
     63@inproceedings{berger02reconsidering,
     64    author      = {Emery D. Berger and Benjamin G. Zorn and Kathryn S. McKinley},
     65    title       = {Reconsidering Custom Memory Allocation},
     66    booktitle   = {Proceedings of the 17th ACM SIGPLAN Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA) 2002},
     67    month       = nov,
     68    year        = 2002,
     69    location    = {Seattle, Washington, USA},
     70    publisher   = {ACM},
     71    address     = {New York, NY, USA},
     72}
     73
     74@article{larson99memory,
     75    author      = {Per-{\AA}ke Larson and Murali Krishnan},
     76    title       = {Memory Allocation for Long-Running Server Applications},
     77    journal     = sigplan,
     78    volume      = 34,
     79    number      = 3,
     80    pages       = {176-185},
     81    year        = 1999,
     82    url         = {http://citeseer.ist.psu.edu/article/larson98memory.html}
     83}
     84
     85@techreport{gidpt04,
     86    author      = {Anders Gidenstam and Marina Papatriantafilou and Philippas Tsigas},
     87    title       = {Allocating Memory in a Lock-Free Manner},
     88    number      = {2004-04},
     89    institution = {Computing Science},
     90    address     = {Chalmers University of Technology},
     91    year        = 2004,
     92    url         = {http://citeseer.ist.psu.edu/gidenstam04allocating.html}
     93}
     94
     95@phdthesis{berger02thesis,
     96    author      = {Emery Berger},
     97    title       = {Memory Management for High-Performance Applications},
     98    school      = {The University of Texas at Austin},
     99    year        = 2002,
     100    month       = aug,
     101    url         = {http://citeseer.ist.psu.edu/article/berger02memory.html}
     102}
     103
     104@misc{sgimisc,
     105    author      = {SGI},
     106    title       = {The Standard Template Library for {C++}},
     107    note        = {\textsf{www.sgi.com/\-tech/\-stl/\-Allocators.html}},
     108}
     109
     110@misc{dlmalloc,
     111    author      = {Doug Lea},
     112    title       = {dlmalloc version 2.8.4},
     113    month       = may,
     114    year        = 2009,
     115    note        = {\textsf{ftp://g.oswego.edu/\-pub/\-misc/\-malloc.c}},
     116}
     117
     118@misc{ptmalloc2,
     119    author      = {Wolfram Gloger},
     120    title       = {ptmalloc version 2},
     121    month       = jun,
     122    year        = 2006,
     123    note        = {\textsf{http://www.malloc.de/\-malloc/\-ptmalloc2-current.tar.gz}},
     124}
     125
     126@misc{nedmalloc,
     127    author      = {Niall Douglas},
     128    title       = {nedmalloc version 1.06 Beta},
     129    month       = jan,
     130    year        = 2010,
     131    note        = {\textsf{http://\-prdownloads.\-sourceforge.\-net/\-nedmalloc/\-nedmalloc\_v1.06beta1\_svn1151.zip}},
     132}
     133
     134@misc{hoard,
     135    author      = {Emery D. Berger},
     136    title       = {hoard version 3.8},
     137    month       = nov,
     138    year        = 2009,
     139    note        = {\textsf{http://www.cs.umass.edu/\-$\sim$emery/\-hoard/\-hoard-3.8/\-source/hoard-38.tar.gz}},
     140}
     141
     142@comment{mtmalloc,
     143    author      = {Greg Nakhimovsky},
     144    title       = {Improving Scalability of Multithreaded Dynamic Memory Allocation},
     145    journal     = {Dr. Dobb's},
     146    month       = jul,
     147    year        = 2001,
     148    url         = {http://www.ddj.com/mobile/184404685?pgno=1}
     149}
     150
     151@misc{mtmalloc,
     152    key         = {mtmalloc},
     153    title       = {mtmalloc.c},
     154    year        = 2009,
     155    note        = {\textsf{http://src.opensolaris.org/\-source/\-xref/\-onnv/\-onnv-gate/\-usr/\-src/\-lib/\-libmtmalloc/\-common/\-mtmalloc.c}},
     156}
     157
     158@misc{tcmalloc,
     159    author      = {Sanjay Ghemawat and Paul Menage},
     160    title       = {tcmalloc version 1.5},
     161    month       = jan,
     162    year        = 2010,
     163    note        = {\textsf{http://google-perftools.\-googlecode.\-com/\-files/\-google-perftools-1.5.tar.gz}},
     164}
     165
     166@inproceedings{streamflow,
     167    author      = {Scott Schneider and Christos D. Antonopoulos and Dimitrios S. Nikolopoulos},
     168    title       = {Scalable Locality-Conscious Multithreaded Memory Allocation},
     169    booktitle   = {International Symposium on Memory Management (ISSM'06)},
     170    month       = jun,
     171    year        = 2006,
     172    pages       = {84-94},
     173    location    = {Ottawa, Ontario, Canada},
     174    publisher   = {ACM},
     175    address     = {New York, NY, USA},
     176}
     177
     178@misc{streamflowweb,
     179    author      = {Scott Schneider and Christos Antonopoulos and Dimitrios Nikolopoulos},
     180    title       = {Streamflow},
     181    note        = {\textsf{http://people.cs.vt.edu/\-\char`\~scschnei/\-streamflow}},
     182}
     183
     184@inproceedings{Blumofe94,
     185    author      = {R. Blumofe and C. Leiserson},
     186    title       = {Scheduling Multithreaded Computations by Work Stealing},
     187    booktitle   = {Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico.},
     188    pages       = {356-368},
     189    year        = 1994,
     190    month       = nov,
     191    url         = {http://citeseer.ist.psu.edu/article/blumofe94scheduling.html}
     192}
     193
     194@article{Johnstone99,
     195    author      = {Mark S. Johnstone and Paul R. Wilson},
     196    title       = {The Memory Fragmentation Problem: Solved?},
     197    journal     = sigplan,
     198    volume      = 34,
     199    number      = 3,
     200    pages       = {26-36},
     201    year        = 1999,
     202}
     203
     204@inproceedings{Grunwald93,
     205    author      = {Dirk Grunwald and Benjamin G. Zorn and Robert Henderson},
     206    title       = {Improving the Cache Locality of Memory Allocation},
     207    booktitle   = {{SIGPLAN} Conference on Programming Language Design and Implementation},
     208    pages       = {177-186},
     209    year        = 1993,
     210    url         = {http://citeseer.ist.psu.edu/grunwald93improving.html}
     211}
     212
     213@inproceedings{Wilson95,
     214    author      = {Wilson, Paul R. and Johnstone, Mark S. and Neely, Michael and Boles, David},
     215    title       = {Dynamic Storage Allocation: A Survey and Critical Review},
     216    booktitle   = {Proc. Int. Workshop on Memory Management},
     217    address     = {Kinross Scotland, UK},
     218    year        = 1995,
     219    url         = {http://citeseer.ist.psu.edu/wilson95dynamic.html}
     220}
     221
     222@inproceedings{Siebert00,
     223    author      = {Fridtjof Siebert},
     224    title       = {Eliminating External Fragmentation in a Non-moving Garbage Collector for Java},
     225    booktitle   = {CASES '00: Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems},
     226    year        = 2000,
     227    isbn        = {1-58113-338-3},
     228    pages       = {9-17},
     229    location    = {San Jose, California, United States},
     230    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/354880.354883},
     231    publisher   = {ACM Press},
     232    address     = {New York, NY, USA}
     233}
     234
     235@inproceedings{Lim98,
     236   author       = {Tian F. Lim and Przemyslaw Pardyak and Brian N. Bershad},
     237   title        = {A Memory-Efficient Real-Time Non-copying Garbage Collector},
     238   booktitle    = {ISMM '98: Proceedings of the 1st international symposium on Memory management},
     239   year         = 1998,
     240   isbn         = {1-58113-114-3},
     241   pages        = {118-129},
     242   location     = {Vancouver, British Columbia, Canada},
     243   doi          = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/286860.286873},
     244   publisher    = {ACM Press},
     245   address      = {New York, NY, USA}
     246}
     247
     248@article{Chang01,
     249    author      = {J. Morris Chang and Woo Hyong Lee and Witawas Srisa-an},
     250    title       = {A Study of the Allocation Behavior of {C++} Programs},
     251    journal     = {J. Syst. Softw.},
     252    volume      = 57,
     253    number      = 2,
     254    year        = 2001,
     255    issn        = {0164-1212},
     256    pages       = {107-118},
     257    doi         = {http://dx.doi.org/10.1016/S0164-1212(00)00122-9},
     258    publisher   = {Elsevier Science Inc.},
     259    address     = {New York, NY, USA}
     260}
     261
     262@article{Herlihy93,
     263    author      = {Maurice Herlihy},
     264    title       = {A Methodology for Implementing Highly Concurrent Data Objects},
     265    journal     = toplas,
     266    volume      = 15,
     267    number      = 5,
     268    year        = 1993,
     269    issn        = {0164-0925},
     270    pages       = {745-770},
     271    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/161468.161469},
     272    publisher   = {ACM Press},
     273    address     = {New York, NY, USA}
     274}
     275
     276@article{Denning05,
     277    author      = {Peter J. Denning},
     278    title       = {The Locality Principle},
     279    journal     = cacm,
     280    volume      = 48,
     281    number      = 7,
     282    year        = 2005,
     283    issn        = {0001-0782},
     284    pages       = {19-24},
     285    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/1070838.1070856},
     286    publisher   = {ACM Press},
     287    address     = {New York, NY, USA}
     288}
     289
     290@misc{wilson-locality,
     291    author      = {Paul R. Wilson},
     292    title       = {Locality of Reference, Patterns in Program Behavior, Memory Management, and Memory Hierarchies},
     293    url         = {http://citeseer.ist.psu.edu/337869.html}
     294}
     295
     296@inproceedings{Feng05,
     297    author      = {Yi Feng and Emery D. Berger},
     298    title       = {A Locality-Improving Dynamic Memory Allocator},
     299    booktitle   = {Proceedings of the 2005 Workshop on Memory System Performance},
     300    location    = {Chicago, Illinois},
     301    publisher   = {ACM},
     302    address     = {New York, NY, USA},
     303    month       = jun,
     304    year        = 2005,
     305    pages       = {68-77},
     306}
     307
     308@inproceedings{grunwald-locality,
     309    author      = {Dirk Grunwald and Benjamin Zorn and Robert Henderson},
     310    title       = {Improving the Cache Locality of Memory Allocation},
     311    booktitle   = {PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation},
     312    year        = 1993,
     313    isbn        = {0-89791-598-4},
     314    pages       = {177-186},
     315    location    = {Albuquerque, New Mexico, United States},
     316    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/155090.155107},
     317    publisher   = {ACM Press},
     318    address     = {New York, NY, USA}
     319}
     320
     321@article{Alexandrescu01b,
     322    author      = {Andrei Alexandrescu},
     323    title       = {{volatile} -- Multithreaded Programmer's Best Friend},
     324    journal     = {Dr. Dobb's},
     325    month       = feb,
     326    year        = 2001,
     327    url         = {http://www.ddj.com/cpp/184403766}
     328}
     329
     330@article{Attardi03,
     331    author      = {Joseph Attardi and Neelakanth Nadgir},
     332    title       = {A Comparison of Memory Allocators in Multiprocessors},
     333    journal     = {Sun Developer Network},
     334    month       = jun,
     335    year        = 2003,
     336    note        = {\textsf{http://developers.sun.com/\-solaris/\-articles/\-multiproc/\-multiproc.html}},
     337}
     338
     339@unpublished{memlayout,
     340    author      = {Peter Jay Salzman},
     341    title       = {Memory Layout and the Stack},
     342    journal     = {Using GNU's GDB Debugger},
     343    note        = {\textsf{http://dirac.org/\-linux/\-gdb/\-02a-Memory\_Layout\_And\_The\_Stack.php}},
     344}
     345
     346@unpublished{Ferguson07,
     347    author      = {Justin N. Ferguson},
     348    title       = {Understanding the Heap by Breaking It},
     349    note        = {\textsf{https://www.blackhat.com/\-presentations/\-bh-usa-07/Ferguson/\-Whitepaper/\-bh-usa-07-ferguson-WP.pdf}},
     350}
     351
     352@inproceedings{Huang06,
     353    author      = {Xianglong Huang and Brian T Lewis and Kathryn S McKinley},
     354    title       = {Dynamic Code Management: Improving Whole Program Code Locality in Managed Runtimes},
     355    booktitle   = {VEE '06: Proceedings of the 2nd international conference on Virtual execution environments},
     356    year        = 2006,
     357    isbn        = {1-59593-332-6},
     358    pages       = {133-143},
     359    location    = {Ottawa, Ontario, Canada},
     360    doi         = {http://doi.acm.org/10.1145/1134760.1134779},
     361    publisher   = {ACM Press},
     362    address     = {New York, NY, USA}
     363 }
     364
     365@inproceedings{Herlihy03,
     366    author      = {M. Herlihy and V. Luchangco and M. Moir},
     367    title       = {Obstruction-free Synchronization: Double-ended Queues as an Example},
     368    booktitle   = {Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems},
     369    year        = 2003,
     370    month       = may,
     371    url         = {http://www.cs.brown.edu/~mph/publications.html}
     372}
     373
     374@techreport{Detlefs93,
     375    author      = {David L. Detlefs and Al Dosser and Benjamin Zorn},
     376    title       = {Memory Allocation Costs in Large {C} and {C++} Programs},
     377    number      = {CU-CS-665-93},
     378    institution = {University of Colorado},
     379    address     = {130 Lytton Avenue, Palo Alto, CA 94301 and Campus Box 430, Boulder, CO 80309},
     380    year        = 1993,
     381    url         = {http://citeseer.ist.psu.edu/detlefs93memory.html}
     382}
     383
     384@inproceedings{Oyama99,
     385    author      = {Y. Oyama and K. Taura and A. Yonezawa},
     386    title       = {Executing Parallel Programs With Synchronization Bottlenecks Efficiently},
     387    booktitle   = {Proceedings of International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA '99)},
     388    year        = {1999},
     389    pages       = {182--204},
     390    publisher   = {World Scientific},
     391    address     = {Sendai, Japan},
     392}
     393
     394@inproceedings{Dice02,
     395    author      = {Dave Dice and Alex Garthwaite},
     396    title       = {Mostly Lock-Free Malloc},
     397    booktitle   = {Proceedings of the 3rd international symposium on Memory management (ISMM'02)},
     398    month       = jun,
     399    year        = 2002,
     400    pages       = {163-174},
     401    location    = {Berlin, Germany},
     402    publisher   = {ACM},
     403    address     = {New York, NY, USA},
     404}

  • doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex

    ref3c383 rd672350  
    8585\usepackage{comment} % Removes large sections of the document.
    8686\usepackage{tabularx}
     87\usepackage{subfigure}
     88
     89\usepackage{algorithm}
     90\usepackage{algpseudocode}
    8791
    8892% Hyperlinks make it very easy to navigate an electronic document.
    … …  
    168172%\usepackageinput{common}
    169173\CFAStyle                                               % CFA code-style for all languages
    170 \lstset{basicstyle=\linespread{0.9}\tt}                 % CFA typewriter font
     174\lstset{basicstyle=\linespread{0.9}\sf}                 % CFA typewriter font
     175\newcommand{\uC}{$\mu$\CC}
    171176\newcommand{\PAB}[1]{{\color{red}PAB: #1}}
    172177
    … …  
    224229\addcontentsline{toc}{chapter}{\textbf{References}}
    225230
    226 \bibliography{uw-ethesis,pl}
     231\bibliography{pl,uw-ethesis}
    227232% Tip: You can create multiple .bib files to organize your references.
    228233% Just list them all in the \bibliogaphy command, separated by commas (no spaces).

  • doc/theses/thierry_delisle_PhD/thesis/text/existing.tex

    ref3c383 rd672350  
    11\chapter{Previous Work}\label{existing}
    2 Scheduling is a topic with a very long history, predating its use in computer science. As such, early work in computed science was inspired from other fields and focused principally on solving scheduling upfront rather that as the system is running.
     2Scheduling is the process of assigning resources to incomming requests.
     3A very common form of this is assigning available workers to work-requests.
     4The need for scheduling is very common in Computer Science, \eg Operating Systems and Hypervisors schedule available CPUs, NICs schedule available bamdwith, but it is also common in other fields.
     5For example, assmebly lines are an example of scheduling where parts needed assembly are assigned to line workers.
     6
     7In all these cases, the choice of a scheduling algorithm generally depends first and formost on how much information is available to the scheduler.
     8Workloads that are well-kown, consistent and homegenous can benefit from a scheduler that is optimized to use this information while ill-defined inconsistent heterogenous workloads will require general algorithms.
     9A secondary aspect to that is how much information can be gathered versus how much information must be given as part of the input.
     10There is therefore a spectrum of scheduling algorithms, going from static schedulers that are well informed from the start, to schedulers that gather most of the information needed, to schedulers that can only rely on very limitted information.
     11Note that this description includes both infomation about each requests, \eg time to complete or resources needed, and information about the relationships between request, \eg whether or not some request must be completed before another request starts.
     12
     13Scheduling physical resources, for example in assembly lines, is generally amenable to using very well informed scheduling since information can be gathered much faster than the physical resources can be assigned and workloads are likely to stay stable for long periods of time.
     14When a faster pace is needed and changes are much more frequent gathering information on workloads, up-front or live, can become much more limiting and more general schedulers are needed.
    315
    416\section{Naming Convention}
    … …  
    618
    719\section{Static Scheduling}
    8 Static schedulers require that programmers explicitly and exhaustively specify dependencies among tasks in order to schedule them. The scheduler then processes this input ahead of time and producess a \newterm{schedule} to which the system can later adhere. An example application for these schedulers
    9 
     20Static schedulers require that tasks have their dependencies and costs explicitly and exhaustively specified prior schedule.
     21The scheduler then processes this input ahead of time and producess a \newterm{schedule} to which the system can later adhere.
     22This approach is generally popular in real-time systems since the need for strong guarantees justifies the cost of supplying this information.
    1023In general, static schedulers are less relavant to this project since they require input from the programmers that \CFA does not have as part of its concurrency semantic.
    11 \todo{Rate-monotonic scheduling}
     24Specifying this information explicitly can add a significant burden on the programmers and reduces flexibility, for this reason the \CFA scheduler does not require this information.
    1225
    1326
    1427\section{Dynamic Scheduling}
    15 It may be difficult to fulfill the requirements of static scheduler if dependencies are be conditionnal. In this case, it may be preferable to detect dependencies at runtime. This detection effectively takes the form of halting or suspending a task with unfulfilled dependencies and adding one or more new task(s) to the system. The new task(s) have the responsability of adding the dependent task back in the system once completed. As a consequence, the scheduler may have an incomplete view of the system, seeing only tasks we no pending dependencies. Schedulers that support this detection at runtime are referred to as \newterm{Dynamic Schedulers}.
     28It may be difficult to fulfill the requirements of static scheduler if dependencies are conditionnal. In this case, it may be preferable to detect dependencies at runtime. This detection effectively takes the form of halting or suspending a task with unfulfilled dependencies and adding one or more new task(s) to the system. The new task(s) have the responsability of adding the dependent task back in the system once completed. As a consequence, the scheduler may have an incomplete view of the system, seeing only tasks we no pending dependencies. Schedulers that support this detection at runtime are referred to as \newterm{Dynamic Schedulers}.
    1629
    1730\subsection{Explicitly Informed Dynamic Schedulers}
    … …  
    2942\subsubsection{Feedback Scheduling}
    3043As mentionned, Schedulers may also gather information about each tasks to direct their decisions. This design effectively moves the scheduler to some extent into the realm of \newterm{Control Theory}\cite{wiki:controltheory}. This gathering does not generally involve programmers and as such does not increase programmer burden the same way explicitly provided information may. However, some feedback schedulers do offer the option to programmers to offer additionnal information on certain tasks, in order to direct scheduling decision. The important distinction being whether or not the scheduler can function without this additionnal information.
    31 
    32 Feedback scheduler
    3344
    3445

  • doc/theses/thierry_delisle_PhD/thesis/text/io.tex

    ref3c383 rd672350  
    11\chapter{User Level \io}
    22As mentioned in Section~\ref{prev:io}, User-Level \io requires multiplexing the \io operations of many \glspl{thrd} onto fewer \glspl{proc} using asynchronous \io operations.
    3 Different operating systems offer various forms of asynchronous operations and as mentioned in Chapter~\ref{intro}, this work is exclusively focused on the Linux operating-system.
     3Different operating systems offer various forms of asynchronous operations and, as mentioned in Chapter~\ref{intro}, this work is exclusively focused on the Linux operating-system.
    44
    55\section{Kernel Interface}
    … …  
    178178Since completions are sent to the instance where requests were submitted, all instances with pending operations must be polled continously
    179179\footnote{As will be described in Chapter~\ref{practice}, this does not translate into constant cpu usage.}.
     180Note that once an operation completes, there is nothing that ties it to the @io_uring@ instance that handled it.
     181There is nothing preventing a new operation with, for example, the same file descriptors to a different @io_uring@ instance.
    180182
    181183A complicating aspect of submission is @io_uring@'s support for chains of operations, where the completion of an operation triggers the submission of the next operation on the link.
    … …  
    240242To remove this requirement, a \gls{thrd} would need the ability to ``yield to a specific \gls{proc}'', \ie, park with the promise that it will be run next on a specific \gls{proc}, the \gls{proc} attached to the correct ring.}
    241243, greatly simplifying both allocation and submission.
    242 In this design, allocation and submission form a ring partitionned ring buffer as shown in Figure~\ref{fig:pring}.
     244In this design, allocation and submission form a partitionned ring buffer as shown in Figure~\ref{fig:pring}.
    243245Once added to the ring buffer, the attached \gls{proc} has a significant amount of flexibility with regards to when to do the system call.
    244 Possible options are: when the \gls{proc} runs out of \glspl{thrd} to run, after running a given number of threads \glspl{thrd}, etc.
     246Possible options are: when the \gls{proc} runs out of \glspl{thrd} to run, after running a given number of \glspl{thrd}, etc.
    245247
    246248\begin{figure}
Note: See TracChangeset for help on using the changeset viewer.