Changeset cc7bbe6

Jenkinsfile

-              rf5a51db
+              rcc7bbe6
                 Tools.BuildStage('Test: full', Settings.RunAllTests) {
                         dir (BuildDir) {
+                                        jopt = ""
+                                        if( Settings.Architecture.node == 'x86' ) {
+                                                jopt = "-j2"
+                                        }
                                         //Run the tests from the tests directory
                                         sh """make --no-print-directory -C tests timeouts="--timeout=600 --global-timeout=14400" all-tests debug=yes archiveerrors=${BuildDir}/tests/crashes/full-debug"""
                                         sh """make --no-print-directory -C tests timeouts="--timeout=600 --global-timeout=14400" all-tests debug=no  archiveerrors=${BuildDir}/tests/crashes/full-nodebug"""
+                                        sh """make ${jopt} --no-print-directory -C tests timeouts="--timeout=600 --global-timeout=14400" all-tests debug=yes archiveerrors=${BuildDir}/tests/crashes/full-debug"""
+                                        sh """make ${jopt} --no-print-directory -C tests timeouts="--timeout=600 --global-timeout=14400" all-tests debug=no  archiveerrors=${BuildDir}/tests/crashes/full-nodebug"""
+                        }
+                }

benchmark/io/http/Makefile.am

-              rf5a51db
+              rcc7bbe6
 .dummy_hackxx.cpp:
         @echo "int bar() { return 0; }" > ${@}
+# add dependency of cfa files
+nodist_httpforall_OBJECTS = $(addsuffix .o, $(basename $(filter %.cfa,$(nodist_httpforall_SOURCES))))
+$(nodist_httpforall_OBJECTS) : @CFACC@ @CFACPP@
+# .deps inclusion is not done automatically by automake for new languages
+nodist_httpforall_DEPENDS = $(join \
+        $(addsuffix $(DEPDIR)/ , $(dir $(nodist_httpforall_OBJECTS) ) ), \
+        $(notdir ${nodist_httpforall_OBJECTS:.o=.Po}) \
+)
+-include $(nodist_httpforall_DEPENDS)
+list_libdeps:
+        echo "objects: " $(nodist_httpforall_OBJECTS)
+        echo "depends: " $(nodist_httpforall_DEPENDS)

doc/LaTeXmacros/common.sty

-              rf5a51db
+              rcc7bbe6
 %% Created On       : Sat Apr  9 10:06:17 2016
 %% Last Modified By : Peter A. Buhr
 %% Last Modified On : Mon May 31 09:08:37 2021
 %% Update Count     : 565
+%% Last Modified On : Mon Feb  7 23:00:46 2022
+%% Update Count     : 569
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 \newcommand{\CCIcon}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} % C++ icon
 \newcommand{\CC}[1][]{\protect\CCIcon{#1}\xspace}               % C++ symbolic name
+\newcommand{\Cpp}[1][]{\CC{#1}}                                                 % C++ synonym
 % numbers disallowed in latex variables names => use number names
 \newcommand{\CCeleven}{\protect\CCIcon{11}\xspace}              % C++11 symbolic name
 …
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\usepackage{pslatex}                                                                    % reduce size of san serif font
+\usepackage{relsize}                                                                    % must be after change to small or selects old size
+\usepackage{rotating}
+\usepackage{calc}                                                                               % latex arithmetic
 % remove special-character warning in PDF side-bar names
 …
 \newlength{\parindentlnth}
 \setlength{\parindentlnth}{\parindent}
-\usepackage{pslatex}                                                                    % reduce size of san serif font
-\usepackage{relsize}                                                                    % must be after change to small or selects old size
-\usepackage{rotating}
-\usepackage{calc}                                                                               % latex arithmetic
 % reduce size of chapter/section titles
 …
 \newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi}
+% \snake{<identifier>}
+% Improves writing of snake case (or any convention that uses _) by allowing
+% line breaks after _. Disables commands inside the block and formats the
+% identifier to look like code.
+\newcommand*\snake[1]{\snakefont{\expandafter\snake@next\detokenize{#1}\@nil}}
+% \snakefont{<text>}
+% Command used by \snake, you may renew the command to change its formating.
+\newcommand*\snakefont[1]{\LstBasicStyle{#1}}
+% Thanks Manuel of TeX Stack exchange. (I got the base pattern from one of
+% their answers.) Note: \@nil should never be defined.
+\newcommand*\snake@next[1]{\ifx\@nil#1\else
+  \expandafter\ifx\string_#1\string_\allowbreak\else#1\fi
+  \expandafter\snake@next\fi
+}
+% \lang{<language>}{<code>}
+% Use the listings package to format the snipit of <code> in <language>.
+\newcommand{\lang}[2]{\lstinline[language=#1]{#2}}
 % Latin abbreviation
 \newcommand{\abbrevFont}{\textit}                       % set empty for no italics
 …
 extendedchars=true,                                             % allow ASCII characters in the range 128-255
 escapechar=\$,                                                  % LaTeX escape in CFA code §...§ (section symbol), emacs: C-q M-'
 mathescape=false,                                               % LaTeX math escape in CFA code $...$
+mathescape=false,                                               % disable LaTeX math escape in CFA code $...$
 keepspaces=true,                                                %
 showstringspaces=false,                                 % do not show spaces with cup
 …
 }{}
 % inline code @...@ (at symbol)
-\makeatother
 \lstMakeShortInline@                                    % single-character for \lstinline
-\makeatletter
 \fi%

doc/LaTeXmacros/common.tex

-              rf5a51db
+              rcc7bbe6
 %% Created On       : Sat Apr  9 10:06:17 2016
 %% Last Modified By : Peter A. Buhr
 %% Last Modified On : Mon May 31 09:10:49 2021
 %% Update Count     : 546
+%% Last Modified On : Mon Feb  7 23:00:08 2022
+%% Update Count     : 552
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 \newcommand{\CCIcon}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} % C++ icon
 \newcommand{\CC}[1][]{\protect\CCIcon{#1}\xspace}               % C++ symbolic name
+\newcommand{\Cpp}[1][]{\CC{#1}}                                                 % C++ synonym
 % numbers disallowed in latex variables names => use number names
 \newcommand{\CCeleven}{\protect\CCIcon{11}\xspace}              % C++11 symbolic name
 …
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\usepackage{pslatex}                                                                    % reduce size of san serif font
+\usepackage{relsize}                                                                    % must be after change to small or selects old size
+\usepackage{rotating}
+\usepackage{calc}                                                                               % latex arithmetic
 % remove special-character warning in PDF side-bar names
 …
 \newlength{\parindentlnth}
 \setlength{\parindentlnth}{\parindent}
-\usepackage{pslatex}                                                                    % reduce size of san serif font
-\usepackage{relsize}                                                                    % must be after change to small or selects old size
-\usepackage{rotating}
-\usepackage{calc}                                                                               % latex arithmetic
 % reduce size of chapter/section titles
 …
 \newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi}
+% \snake{<identifier>}
+% Improves writing of snake case (or any convention that uses _) by allowing
+% line breaks after _. Disables commands inside the block and formats the
+% identifier to look like code.
+\newcommand*\snake[1]{\snakefont{\expandafter\snake@next\detokenize{#1}\@nil}}
+% \snakefont{<text>}
+% Command used by \snake, you may renew the command to change its formating.
+\newcommand*\snakefont[1]{\LstBasicStyle{#1}}
+% Thanks Manuel of TeX Stack exchange. (I got the base pattern from one of
+% their answers.) Note: \@nil should never be defined.
+\newcommand*\snake@next[1]{\ifx\@nil#1\else
+  \expandafter\ifx\string_#1\string_\allowbreak\else#1\fi
+  \expandafter\snake@next\fi
+}
+% \lang{<language>}{<code>}
+% Use the listings package to format the snipit of <code> in <language>.
+\newcommand{\lang}[2]{\lstinline[language=#1]{#2}}
 % Latin abbreviation
 \newcommand{\abbrevFont}{\textit}                       % set empty for no italics
 …
 extendedchars=true,                                             % allow ASCII characters in the range 128-255
 escapechar=\$,                                                  % LaTeX escape in CFA code §...§ (section symbol), emacs: C-q M-'
 mathescape=false,                                               % LaTeX math escape in CFA code $...$
+mathescape=false,                                               % disable LaTeX math escape in CFA code $...$
 keepspaces=true,                                                %
 showstringspaces=false,                                 % do not show spaces with cup

doc/theses/mubeen_zulfiqar_MMath/Makefile

-              rf5a51db
+              rcc7bbe6
-DOC = uw-ethesis.pdf
-BASE = ${DOC:%.pdf=%} # remove suffix
 # directory for latex clutter files
+BUILD = build
+TEXSRC = $(wildcard *.tex)
+FIGSRC = $(wildcard *.fig)
+BIBSRC = $(wildcard *.bib)
+TEXLIB = .:../../LaTeXmacros:${BUILD}: # common latex macros
+BIBLIB = .:../../bibliography # common citation repository
+Build = build
+Figures = figures
+Pictures = pictures
+TeXSRC = ${wildcard *.tex}
+FigSRC = ${notdir ${wildcard ${Figures}/*.fig}}
+PicSRC = ${notdir ${wildcard ${Pictures}/*.fig}}
+BIBSRC = ${wildcard *.bib}
+TeXLIB = .:../../LaTeXmacros:${Build}: # common latex macros
+BibLIB = .:../../bibliography # common citation repository
 MAKEFLAGS = --no-print-directory # --silent
 VPATH = ${BUILD}
+VPATH = ${Build} ${Figures} ${Pictures} # extra search path for file names used in document
 ### Special Rules:
 …
 ### Commands:
+LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD}
+BIBTEX = BIBINPUTS=${BIBLIB} bibtex
+#GLOSSARY = INDEXSTYLE=${BUILD} makeglossaries-lite
+LaTeX = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
+BibTeX = BIBINPUTS=${BibLIB} bibtex
+#Glossary = INDEXSTYLE=${Build} makeglossaries-lite
 ### Rules and Recipes:
+DOC = uw-ethesis.pdf
+BASE = ${DOC:%.pdf=%} # remove suffix
 all: ${DOC}
+${BUILD}/%.dvi: ${TEXSRC} ${FIGSRC:%.fig=%.tex} ${BIBSRC} Makefile | ${BUILD}
+        ${LATEX} ${BASE}
+        ${BIBTEX} ${BUILD}/${BASE}
+        ${LATEX} ${BASE}
+#       ${GLOSSARY} ${BUILD}/${BASE}
+#       ${LATEX} ${BASE}
+clean:
+        @rm -frv ${DOC} ${Build}
+${BUILD}:
+# File Dependencies #
+${Build}/%.dvi : ${TeXSRC} ${FigSRC:%.fig=%.tex} ${PicSRC:%.fig=%.pstex} ${BIBSRC} Makefile | ${Build}
+        ${LaTeX} ${BASE}
+        ${BibTeX} ${Build}/${BASE}
+        ${LaTeX} ${BASE}
+        # if nedded, run latex again to get citations
+        if fgrep -s "LaTeX Warning: Citation" ${basename $@}.log ; then ${LaTeX} ${BASE} ; fi
+#       ${Glossary} ${Build}/${BASE}
+#       ${LaTeX} ${BASE}
+${Build}:
         mkdir $@
 %.pdf : ${BUILD}/%.ps | ${BUILD}
+%.pdf : ${Build}/%.ps | ${Build}
         ps2pdf $<
 %.ps : %.dvi | ${BUILD}
+%.ps : %.dvi | ${Build}
         dvips $< -o $@
 %.tex : %.fig | ${BUILD}
         fig2dev -L eepic $< > ${BUILD}/$@
+%.tex : %.fig | ${Build}
+        fig2dev -L eepic $< > ${Build}/$@
 %.ps : %.fig | ${BUILD}
         fig2dev -L ps $< > ${BUILD}/$@
+%.ps : %.fig | ${Build}
+        fig2dev -L ps $< > ${Build}/$@
+%.pstex : %.fig | ${BUILD}
+        fig2dev -L pstex $< > ${BUILD}/$@
+        fig2dev -L pstex_t -p ${BUILD}/$@ $< > ${BUILD}/$@_t
+clean:
+        @rm -frv ${DOC} ${BUILD} *.fig.bak
+%.pstex : %.fig | ${Build}
+        fig2dev -L pstex $< > ${Build}/$@
+        fig2dev -L pstex_t -p ${Build}/$@ $< > ${Build}/$@_t

doc/theses/mubeen_zulfiqar_MMath/allocator.tex

-              rf5a51db
+              rcc7bbe6
 \end{itemize}
 The new features added to uHeapLmmm (incl. @malloc\_size@ routine)
+The new features added to uHeapLmmm (incl. @malloc_size@ routine)
 \CFA alloc interface with examples.
 …
 \begin{itemize}
 \item
 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.
 \item
 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.
+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.
+\item
+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.
 \item
 It is possible to use sharing and stealing techniques to share/find unused storage, when a free list is unused or empty.
 …
 \section{Added Features and Methods}
 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.
+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.
 \subsection{C Interface}
 We 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.
+\subsubsection void * aalloc( size\_t dim, size\_t elemSize )
+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.
+\paragraph{Usage}
+aalloc takes two parameters.
+\begin{itemize}
+\item
+dim: number of objects in the array
+\item
+elemSize: size of the object in the array.
+\end{itemize}
+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.
+\subsubsection void * resize( void * oaddr, size\_t size )
+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.
+\paragraph{Usage}
+resize takes two parameters.
+\begin{itemize}
+\item
+oaddr: the address of the old object that needs to be resized.
+\item
+size: the new size requirement of the to which the old object needs to be resized.
+\end{itemize}
+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.
+\subsubsection void * resize( void * oaddr, size\_t nalign, size\_t size )
+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.
+\subsection{Out of Memory}
+Most allocators use @nullptr@ to indicate an allocation failure, specifically out of memory;
+hence the need to return an alternate value for a zero-sized allocation.
+The alternative is to abort a program when out of memory.
+In theory, notifying the programmer allows recovery;
+in 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.
+\subsection{\lstinline{void * aalloc( size_t dim, size_t elemSize )}}
+@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.
+\paragraph{Usage}
+@aalloc@ takes two parameters.
+\begin{itemize}
+\item
+@dim@: number of objects in the array
+\item
+@elemSize@: size of the object in the array.
+\end{itemize}
+It 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.
+\subsection{\lstinline{void * resize( void * oaddr, size_t size )}}
+@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.
+\paragraph{Usage}
+@resize@ takes two parameters.
+\begin{itemize}
+\item
+@oaddr@: the address of the old object that needs to be resized.
+\item
+@size@: the new size requirement of the to which the old object needs to be resized.
+\end{itemize}
+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 a @NULL@ pointer.
+\subsection{\lstinline{void * resize( void * oaddr, size_t nalign, size_t size )}}
+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.
 \paragraph{Usage}
 This resize takes three parameters. It takes an additional parameter of nalign as compared to the above resize (FIX ME: cite above resize).
 …
 \begin{itemize}
 \item
 oaddr: the address of the old object that needs to be resized.
 \item
 nalign: the new alignment to which the old object needs to be realigned.
 \item
 size: the new size requirement of the to which the old object needs to be resized.
 \end{itemize}
 It returns an object with the size and alignment given in the parameters. On failure, it returns a NULL pointer.
 \subsubsection void * amemalign( size\_t alignment, size\_t dim, size\_t elemSize )
+@oaddr@: the address of the old object that needs to be resized.
+\item
+@nalign@: the new alignment to which the old object needs to be realigned.
+\item
+@size@: the new size requirement of the to which the old object needs to be resized.
+\end{itemize}
+It returns an object with the size and alignment given in the parameters. On failure, it returns a @NULL@ pointer.
+\subsection{\lstinline{void * amemalign( size_t alignment, size_t dim, size_t elemSize )}}
 amemalign 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.
 \paragraph{Usage}
 …
 \begin{itemize}
 \item
 alignment: the alignment to which the dynamic array needs to be aligned.
 \item
 dim: number of objects in the array
 \item
 elemSize: size of the object in the array.
 \end{itemize}
 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.
 \subsubsection void * cmemalign( size\_t alignment, size\_t dim, size\_t elemSize )
+@alignment@: the alignment to which the dynamic array needs to be aligned.
+\item
+@dim@: number of objects in the array
+\item
+@elemSize@: size of the object in the array.
+\end{itemize}
+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 a @NULL@ pointer.
+\subsection{\lstinline{void * cmemalign( size_t alignment, size_t dim, size_t elemSize )}}
 cmemalign 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.
 \paragraph{Usage}
 …
 \begin{itemize}
 \item
 alignment: the alignment to which the dynamic array needs to be aligned.
 \item
 dim: number of objects in the array
 \item
 elemSize: size of the object in the array.
 \end{itemize}
 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.
 \subsubsection size\_t malloc\_alignment( void * addr )
 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.
 \paragraph{Usage}
 malloc\_alignment takes one parameters.
 \begin{itemize}
 \item
 addr: the address of the currently allocated dynamic object.
 \end{itemize}
 malloc\_alignment returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeapLmmm allocator.
 \subsubsection bool malloc\_zero\_fill( void * addr )
 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.
 \paragraph{Usage}
 malloc\_zero\_fill takes one parameters.
 \begin{itemize}
 \item
 addr: the address of the currently allocated dynamic object.
 \end{itemize}
 malloc\_zero\_fill returns true if the dynamic object was initially zero filled and return false otherwise. On failure, it returns false.
 \subsubsection size\_t malloc\_size( void * addr )
 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.
 \paragraph{Usage}
 malloc\_size takes one parameters.
 \begin{itemize}
 \item
 addr: the address of the currently allocated dynamic object.
 \end{itemize}
 malloc\_size returns the allocation size of the given dynamic object. On failure, it return zero.
 \subsubsection void * realloc( void * oaddr, size\_t nalign, size\_t size )
 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.
 \paragraph{Usage}
 This realloc takes three parameters. It takes an additional parameter of nalign as compared to the default realloc.
 \begin{itemize}
 \item
 oaddr: the address of the old object that needs to be reallocated.
 \item
 nalign: the new alignment to which the old object needs to be realigned.
 \item
 size: the new size requirement of the to which the old object needs to be resized.
 \end{itemize}
 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.
 \subsection{CFA Malloc Interface}
 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.
 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.
 \subsubsection T * malloc( void )
+@alignment@: the alignment to which the dynamic array needs to be aligned.
+\item
+@dim@: number of objects in the array
+\item
+@elemSize@: size of the object in the array.
+\end{itemize}
+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 a @NULL@ pointer.
+\subsection{\lstinline{size_t malloc_alignment( void * addr )}}
+@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.
+\paragraph{Usage}
+@malloc_alignment@ takes one parameters.
+\begin{itemize}
+\item
+@addr@: the address of the currently allocated dynamic object.
+\end{itemize}
+@malloc_alignment@ returns the alignment of the given dynamic object. On failure, it return the value of default alignment of the uHeapLmmm allocator.
+\subsection{\lstinline{bool malloc_zero_fill( void * addr )}}
+@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.
+\paragraph{Usage}
+@malloc_zero_fill@ takes one parameters.
+\begin{itemize}
+\item
+@addr@: the address of the currently allocated dynamic object.
+\end{itemize}
+@malloc_zero_fill@ returns true if the dynamic object was initially zero filled and return false otherwise. On failure, it returns false.
+\subsection{\lstinline{size_t malloc_size( void * addr )}}
+@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.
+\paragraph{Usage}
+@malloc_size@ takes one parameters.
+\begin{itemize}
+\item
+@addr@: the address of the currently allocated dynamic object.
+\end{itemize}
+@malloc_size@ returns the allocation size of the given dynamic object. On failure, it return zero.
+\subsection{\lstinline{void * realloc( void * oaddr, size_t nalign, size_t size )}}
+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.
+\paragraph{Usage}
+This @realloc@ takes three parameters. It takes an additional parameter of nalign as compared to the default @realloc@.
+\begin{itemize}
+\item
+@oaddr@: the address of the old object that needs to be reallocated.
+\item
+@nalign@: the new alignment to which the old object needs to be realigned.
+\item
+@size@: the new size requirement of the to which the old object needs to be resized.
+\end{itemize}
+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.
+\subsection{\CFA Malloc Interface}
+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.
+\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.
+\subsection{\lstinline{T * malloc( void )}}
 This 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.
 \paragraph{Usage}
 This malloc takes no parameters.
 It returns a dynamic object of the size of type T. On failure, it return NULL pointer.
 \subsubsection T * aalloc( size\_t dim )
+It returns a dynamic object of the size of type @T@. On failure, it returns a @NULL@ pointer.
+\subsection{\lstinline{T * aalloc( size_t dim )}}
 This 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.
 \paragraph{Usage}
 …
 \begin{itemize}
 \item
 dim: required number of objects in the array.
 \end{itemize}
 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.
 \subsubsection T * calloc( size\_t dim )
+@dim@: required number of objects in the array.
+\end{itemize}
+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 returns a @NULL@ pointer.
+\subsection{\lstinline{T * calloc( size_t dim )}}
 This 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.
 \paragraph{Usage}
 …
 \begin{itemize}
 \item
 dim: required number of objects in the array.
 \end{itemize}
 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.
 \subsubsection T * resize( T * ptr, size\_t size )
 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.
+@dim@: required number of objects in the array.
+\end{itemize}
+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 returns a @NULL@ pointer.
+\subsection{\lstinline{T * resize( T * ptr, size_t size )}}
+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.
 \paragraph{Usage}
 This resize takes two parameters.
 …
 \begin{itemize}
 \item
 ptr: address of the old object.
 \item
 size: the required size of the new object.
 \end{itemize}
 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.
 \subsubsection T * realloc( T * ptr, size\_t size )
 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.
 \paragraph{Usage}
 This realloc takes two parameters.
 \begin{itemize}
 \item
 ptr: address of the old object.
 \item
 size: the required size of the new object.
 \end{itemize}
 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.
 \subsubsection T * memalign( size\_t align )
+@ptr@: address of the old object.
+\item
+@size@: the required size of the new object.
+\end{itemize}
+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 returns a @NULL@ pointer.
+\subsection{\lstinline{T * realloc( T * ptr, size_t size )}}
+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.
+\paragraph{Usage}
+This @realloc@ takes two parameters.
+\begin{itemize}
+\item
+@ptr@: address of the old object.
+\item
+@size@: the required size of the new object.
+\end{itemize}
+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 returns a @NULL@ pointer.
+\subsection{\lstinline{T * memalign( size_t align )}}
 This 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.
 \paragraph{Usage}
 …
 \begin{itemize}
 \item
 align: the required alignment of the dynamic object.
 \end{itemize}
 It returns a dynamic object of the size of type T that is aligned to given parameter align. On failure, it return NULL pointer.
 \subsubsection T * amemalign( size\_t align, size\_t dim )
+@align@: the required alignment of the dynamic object.
+\end{itemize}
+It returns a dynamic object of the size of type @T@ that is aligned to given parameter align. On failure, it returns a @NULL@ pointer.
+\subsection{\lstinline{T * amemalign( size_t align, size_t dim )}}
 This 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.
 \paragraph{Usage}
 …
 \begin{itemize}
 \item
 align: required alignment of the dynamic array.
 \item
 dim: required number of objects in the array.
 \end{itemize}
 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.
 \subsubsection T * cmemalign( size\_t align, size\_t dim  )
+@align@: required alignment of the dynamic array.
+\item
+@dim@: required number of objects in the array.
+\end{itemize}
+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 returns a @NULL@ pointer.
+\subsection{\lstinline{T * cmemalign( size_t align, size_t dim  )}}
 This 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.
 \paragraph{Usage}
 …
 \begin{itemize}
 \item
+align: required alignment of the dynamic array.
+\item
+dim: required number of objects in the array.
+\end{itemize}
+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.
+\subsubsection T * aligned\_alloc( size\_t align )
+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.
+\paragraph{Usage}
+This aligned\_alloc takes one parameter.
+\begin{itemize}
+\item
+align: required alignment of the dynamic object.
+\end{itemize}
+It returns a dynamic object of the size of type T that is aligned to the given parameter. On failure, it return NULL pointer.
+\subsubsection int posix\_memalign( T ** ptr, size\_t align )
+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.
+\paragraph{Usage}
+This posix\_memalign takes two parameter.
+\begin{itemize}
+\item
+ptr: variable address to store the address of the allocated object.
+\item
+align: required alignment of the dynamic object.
+\end{itemize}
+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.
+\subsubsection T * valloc( void )
+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.
+\paragraph{Usage}
+valloc takes no parameters.
+It returns a dynamic object of the size of type T that is aligned to the page size. On failure, it return NULL pointer.
+\subsubsection T * pvalloc( void )
+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.
+\paragraph{Usage}
+pvalloc takes no parameters.
+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.
+\subsection Alloc Interface
+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.
+@align@: required alignment of the dynamic array.
+\item
+@dim@: required number of objects in the array.
+\end{itemize}
+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 returns a @NULL@ pointer.
+\subsection{\lstinline{T * aligned_alloc( size_t align )}}
+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.
+\paragraph{Usage}
+This @aligned_alloc@ takes one parameter.
+\begin{itemize}
+\item
+@align@: required alignment of the dynamic object.
+\end{itemize}
+It returns a dynamic object of the size of type @T@ that is aligned to the given parameter. On failure, it returns a @NULL@ pointer.
+\subsection{\lstinline{int posix_memalign( T ** ptr, size_t align )}}
+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.
+\paragraph{Usage}
+This @posix_memalign@ takes two parameter.
+\begin{itemize}
+\item
+@ptr@: variable address to store the address of the allocated object.
+\item
+@align@: required alignment of the dynamic object.
+\end{itemize}
+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 returns a @NULL@ pointer.
+\subsection{\lstinline{T * valloc( void )}}
+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.
+\paragraph{Usage}
+@valloc@ takes no parameters.
+It returns a dynamic object of the size of type @T@ that is aligned to the page size. On failure, it returns a @NULL@ pointer.
+\subsection{\lstinline{T * pvalloc( void )}}
+\paragraph{Usage}
+@pvalloc@ takes no parameters.
+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 returns a @NULL@ pointer.
+\subsection{Alloc Interface}
+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.
 This interface helps programmers in three major ways.
 …
 Parametre Positions: alloc interface frees programmers from remembering parameter postions in call to routines.
 \item
 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.
 \end{itemize}
 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.
 \subsubsection{Routine: T * alloc( ... )}
 Call to alloc wihout any parameter returns one object of size of type T allocated dynamically.
+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.
+\end{itemize}
+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.
+\subsection{Routine: \lstinline{T * alloc( ... )}}
+Call to alloc wihout any parameter returns one object of size of type @T@ allocated dynamically.
 Only 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.
 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.
+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.
 \paragraph{Dim}
 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.
 It represents the required number of members in the array allocation as in CFA's aalloc (FIX ME: cite aalloc).
 This parameter should be of type size\_t.
 Example: int a = alloc( 5 )
+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@.
+It represents the required number of members in the array allocation as in \CFA's aalloc (FIX ME: cite aalloc).
+This parameter should be of type @size_t@.
+Example: @int a = alloc( 5 )@
 This call will return a dynamic array of five integers.
 \paragraph{Align}
 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.
 Example: int b = alloc( 5 , 64`align )
+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.
+Example: @int b = alloc( 5 , 64`align )@
 This call will return a dynamic array of five integers. It will align the allocated object to 64.
 \paragraph{Fill}
 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.
+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.
 Three types of parameters can be passed using `fill.
 \begin{itemize}
 \item
 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.
 \item
 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.
 \item
 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.
 \end{itemize}
 Example: int b = alloc( 5 , 'a'`fill )
+@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.
+\item
+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.
+\item
+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.
+\end{itemize}
+Example: @int b = alloc( 5 , 'a'`fill )@
 This 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.
 Example: int b = alloc( 5 , 4`fill )
+Example: @int b = alloc( 5 , 4`fill )@
 This 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.
 Example: int b = alloc( 5 , a`fill ) where a is a pointer of int type
+Example: @int b = alloc( 5 , a`fill )@ where @a@ is a pointer of int type
 This 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.
 \paragraph{Resize}
 This parameter is position-free and uses a backtick routine resize (`resize). It represents the old dynamic object (oaddr) that the programmer wants to
+This parameter is position-free and uses a backtick routine resize (@`resize@). It represents the old dynamic object (oaddr) that the programmer wants to
 \begin{itemize}
 \item
 …
 fill with something.
 \end{itemize}
 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.
 Example: int b = alloc( 5 , a`resize )
+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.
+Example: @int b = alloc( 5 , a`resize )@
 This call will resize object a to a dynamic array that can contain 5 integers.
 Example: int b = alloc( 5 , a`resize , 32`align )
+Example: @int b = alloc( 5 , a`resize , 32`align )@
 This call will resize object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32.
 Example: int b = alloc( 5 , a`resize , 32`align , 2`fill)
+Example: @int b = alloc( 5 , a`resize , 32`align , 2`fill )@
 This 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.
 \paragraph{Realloc}
 This parameter is position-free and uses a backtick routine realloc (`realloc). It represents the old dynamic object (oaddr) that the programmer wants to
+This parameter is position-free and uses a backtick routine @realloc@ (@`realloc@). It represents the old dynamic object (oaddr) that the programmer wants to
 \begin{itemize}
 \item
 …
 fill with something.
 \end{itemize}
 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.
 Example: int b = alloc( 5 , a`realloc )
+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.
+Example: @int b = alloc( 5 , a`realloc )@
 This call will realloc object a to a dynamic array that can contain 5 integers.
 Example: int b = alloc( 5 , a`realloc , 32`align )
+Example: @int b = alloc( 5 , a`realloc , 32`align )@
 This call will realloc object a to a dynamic array that can contain 5 integers. The returned object will also be aligned to 32.
 Example: int b = alloc( 5 , a`realloc , 32`align , 2`fill)
+Example: @int b = alloc( 5 , a`realloc , 32`align , 2`fill )@
 This 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

-              rf5a51db
+              rcc7bbe6
 \chapter{Background}
+A program dynamically allocates and deallocates the storage for a variable, referred to as an \newterm{object}, through calls such as @malloc@ and @free@ in C, and @new@ and @delete@ in \CC.
+Space for each allocated object comes from the dynamic-allocation zone.
+A \newterm{memory allocator} contains a complex data-structure and code that manages the layout of objects in the dynamic-allocation zone.
+The management goals are to make allocation/deallocation operations as fast as possible while densely packing objects to make efficient use of memory.
+Objects in C/\CC cannot be moved to aid the packing process, only adjacent free storage can be \newterm{coalesced} into larger free areas.
+The allocator grows or shrinks the dynamic-allocation zone to obtain storage for objects and reduce memory usage via operating-system calls, such as @mmap@ or @sbrk@ in UNIX.
+\section{Allocator Components}
+\label{s:AllocatorComponents}
+\VRef[Figure]{f:AllocatorComponents} shows the two important data components for a memory allocator, management and storage, collectively called the \newterm{heap}.
+The \newterm{management data} is a data structure located at a known memory address and contains all information necessary to manage the storage data.
+The management data starts with fixed-sized information in the static-data memory that flows into the dynamic-allocation memory.
+The \newterm{storage data} is composed of allocated and freed objects, and \newterm{reserved memory}.
+Allocated objects (white) are variable sized, and allocated and maintained by the program;
+\ie only the program knows the location of allocated storage, not the memory allocator.
+\begin{figure}[h]
+\centering
+\input{AllocatorComponents}
+\caption{Allocator Components (Heap)}
+\label{f:AllocatorComponents}
+\end{figure}
+Freed objects (light grey) are memory deallocated by the program, which are linked into one or more lists facilitating easy location for new allocations.
+Often the free list is chained internally so it does not consume additional storage, \ie the link fields are placed at known locations in the unused memory blocks.
+Reserved memory (dark grey) is one or more blocks of memory obtained from the operating system but not yet allocated to the program;
+if there are multiple reserved blocks, they are also chained together, usually internally.
+Allocated and freed objects typically have additional management data embedded within them.
+\VRef[Figure]{f:AllocatedObject} shows an allocated object with a header, trailer, and alignment padding and spacing around the object.
+The header contains information about the object, \eg size, type, etc.
+The trailer may be used to simplify an allocation implementation, \eg coalescing, and/or for security purposes to mark the end of an object.
+An object may be preceded by padding to ensure proper alignment.
+Some algorithms quantize allocation requests into distinct sizes resulting in additional spacing after objects less than the quantized value.
+When padding and spacing are necessary, neither can be used to satisfy a future allocation request while the current allocation exists.
+A free object also contains management data, \eg size, chaining, etc.
+The amount of management data for a free node defines the minimum allocation size, \eg if 16 bytes are needed for a free-list node, any allocation request less than 16 bytes must be rounded up, otherwise the free list cannot use internal chaining.
+The information in an allocated or freed object is overwritten when it transitions from allocated to freed and vice-versa by new management information and possibly data.
+\begin{figure}
+\centering
+\input{AllocatedObject}
+\caption{Allocated Object}
+\label{f:AllocatedObject}
+\end{figure}
+\section{Single-Threaded Memory-Allocator}
+\label{s:SingleThreadedMemoryAllocator}
+A single-threaded memory-allocator does not run any threads itself, but is used by a single-threaded program.
+Because the memory allocator is only executed by a single thread, concurrency issues do not exist.
+The primary issues in designing a single-threaded memory-allocator are fragmentation and locality.
+\subsection{Fragmentation}
+\label{s:Fragmentation}
+Fragmentation is memory requested from the operating system but not used by the program;
+hence, allocated objects are not fragmentation.
+\VRef[Figure]{f:InternalExternalFragmentation}) shows fragmentation is divided into two forms: internal or external.
+\begin{figure}
+\centering
+\input{IntExtFragmentation}
+\caption{Internal and External Fragmentation}
+\label{f:InternalExternalFragmentation}
+\end{figure}
+\newterm{Internal fragmentation} is memory space that is allocated to the program, but is not intended to be accessed by the program, such as headers, trailers, padding, and spacing around an allocated object.
+This memory is typically used by the allocator for management purposes or required by the architecture for correctness, \eg alignment.
+Internal fragmentation is problematic when management space is a significant proportion of an allocated object.
+For example, if internal fragmentation is as large as the object being managed, then the memory usage for that object is doubled.
+An allocator should strive to keep internal management information to a minimum.
+\newterm{External fragmentation} is all memory space reserved from the operating system but not allocated to the program~\cite{Wilson95,Lim98,Siebert00}, which includes freed objects, all external management data, and reserved memory.
+This memory is problematic in two ways: heap blowup and highly fragmented memory.
+\newterm{Heap blowup} occurs when memory freed by the program is not reused for future allocations leading to potentially unbounded external fragmentation growth~\cite{Berger00}.
+Heap blowup can occur due to allocator policies that are too restrictive in reusing freed memory and/or no coalescing of free storage.
+Memory can become \newterm{highly fragmented} after multiple allocations and deallocations of objects.
+\VRef[Figure]{f:MemoryFragmentation} shows an example of how a small block of memory fragments as objects are allocated and deallocated over time.
+Blocks of free memory become smaller and non-contiguous making them less useful in serving allocation requests.
+Memory is highly fragmented when the sizes of most free blocks are unusable.
+For example, \VRef[Figure]{f:Contiguous} and \VRef[Figure]{f:HighlyFragmented} have the same quantity of external fragmentation, but \VRef[Figure]{f:HighlyFragmented} is highly fragmented.
+If there is a request to allocate a large object, \VRef[Figure]{f:Contiguous} is more likely to be able to satisfy it with existing free memory, while \VRef[Figure]{f:HighlyFragmented} likely has to request more memory from the operating system.
+\begin{figure}
+\centering
+\input{MemoryFragmentation}
+\caption{Memory Fragmentation}
+\label{f:MemoryFragmentation}
+\vspace{10pt}
+\subfigure[Contiguous]{
+        \input{ContigFragmentation}
+        \label{f:Contiguous}
+} % subfigure
+        \subfigure[Highly Fragmented]{
+        \input{NonContigFragmentation}
+\label{f:HighlyFragmented}
+} % subfigure
+\caption{Fragmentation Quality}
+\label{f:FragmentationQuality}
+\end{figure}
+For a single-threaded memory allocator, three basic approaches for controlling fragmentation have been identified~\cite{Johnstone99}.
+The first approach is a \newterm{sequential-fit algorithm} with one list of free objects that is searched for a block large enough to fit a requested object size.
+Different search policies determine the free object selected, \eg the first free object large enough or closest to the requested size.
+Any storage larger than the request can become spacing after the object or be split into a smaller free object.
+The cost of the search depends on the shape and quality of the free list, \eg a linear versus a binary-tree free-list, a sorted versus unsorted free-list.
+The second approach is a \newterm{segregated} or \newterm{binning algorithm} with a set of lists for different sized freed objects.
+When an object is allocated, the requested size is rounded up to the nearest bin-size, possibly with spacing after the object.
+A binning algorithm is fast at finding free memory of the appropriate size and allocating it, since the first free object on the free list is used.
+The fewer bin-sizes, the fewer lists need to be searched and maintained;
+however, the bin sizes are less likely to closely fit the requested object size, leading to more internal fragmentation.
+The more bin-sizes, the longer the search and the less likely free objects are to be reused, leading to more external fragmentation and potentially heap blowup.
+A variation of the binning algorithm allows objects to be allocated to the requested size, but when an object is freed, it is placed on the free list of the next smallest or equal bin-size.
+For example, with bin sizes of 8 and 16 bytes, a request for 12 bytes allocates only 12 bytes, but when the object is freed, it is placed on the 8-byte bin-list.
+For subsequent requests, the bin free-lists contain objects of different sizes, ranging from one bin-size to the next (8-16 in this example), and a sequential-fit algorithm may be used to find an object large enough for the requested size on the associated bin list.
+The third approach is \newterm{splitting} and \newterm{coalescing algorithms}.
+When an object is allocated, if there are no free objects of the requested size, a larger free object may be split into two smaller objects to satisfy the allocation request without obtaining more memory from the operating system.
+For example, in the buddy system, a block of free memory is split into two equal chunks, one of those chunks is again split into two equal chunks, and so on until a block just large enough to fit the requested object is created.
+When an object is deallocated it is coalesced with the objects immediately before and after it in memory, if they are free, turning them into one larger object.
+Coalescing can be done eagerly at each deallocation or lazily when an allocation cannot be fulfilled.
+In all cases, coalescing increases allocation latency, hence some allocations can cause unbounded delays during coalescing.
+While coalescing does not reduce external fragmentation, the coalesced blocks improve fragmentation quality so future allocations are less likely to cause heap blowup.
+Splitting and coalescing can be used with other algorithms to avoid highly fragmented memory.
+\subsection{Locality}
+\label{s:Locality}
+The principle of locality recognizes that programs tend to reference a small set of data, called a working set, for a certain period of time, where a working set is composed of temporal and spatial accesses~\cite{Denning05}.
+Temporal clustering implies a group of objects are accessed repeatedly within a short time period, while spatial clustering implies a group of objects physically close together (nearby addresses) are accessed repeatedly within a short time period.
+Temporal locality commonly occurs during an iterative computation with a fix set of disjoint variables, while spatial locality commonly occurs when traversing an array.
+Hardware takes advantage of temporal and spatial locality through multiple levels of caching (\ie memory hierarchy).
+When an object is accessed, the memory physically located around the object is also cached with the expectation that the current and nearby objects will be referenced within a short period of time.
+For example, entire cache lines are transferred between memory and cache and entire virtual-memory pages are transferred between disk and memory.
+A program exhibiting good locality has better performance due to fewer cache misses and page faults\footnote{With the advent of large RAM memory, paging is becoming less of an issue in modern programming.}.
+Temporal locality is largely controlled by how a program accesses its variables~\cite{Feng05}.
+Nevertheless, a memory allocator can have some indirect influence on temporal locality and largely dictates spatial locality.
+For temporal locality, an allocator can return storage for new allocations that was just freed as these memory locations are still \emph{warm} in the memory hierarchy.
+For spatial locality, an allocator can place objects used together close together in memory, so the working set of the program fits into the fewest possible cache lines and pages.
+However, usage patterns are different for every program as is the underlying hardware memory architecture;
+hence, no general-purpose memory-allocator can provide ideal locality for every program on every computer.
+There are a number of ways a memory allocator can degrade locality by increasing the working set.
+For example, a memory allocator may access multiple free objects before finding one to satisfy an allocation request (\eg sequential-fit algorithm).
+If there are a (large) number of objects accessed in very different areas of memory, the allocator may perturb the program's memory hierarchy causing multiple cache or page misses~\cite{Grunwald93}.
+Another way locality can be degraded is by spatially separating related data.
+For example, in a binning allocator, objects of different sizes are allocated from different bins that may be located in different pages of memory.
+\section{Multi-Threaded Memory-Allocator}
+\label{s:MultiThreadedMemoryAllocator}
+A multi-threaded memory-allocator does not run any threads itself, but is used by a multi-threaded program.
+In addition to single-threaded design issues of locality and fragmentation, a multi-threaded allocator may be simultaneously accessed by multiple threads, and hence, must deal with concurrency issues such as ymutual exclusion, false sharing, and additional forms of heap blowup.
+\subsection{Mutual Exclusion}
+\label{s:MutualExclusion}
+\newterm{Mutual exclusion} provides sequential access to the shared management data of the heap.
+There are two performance issues for mutual exclusion.
+First is the overhead necessary to perform (at least) a hardware atomic operation every time a shared resource is accessed.
+Second is when multiple threads contend for a shared resource simultaneously, and hence, some threads must wait until the resource is released.
+Contention can be reduced in a number of ways:
+using multiple fine-grained locks versus a single lock, spreading the contention across a number of locks;
+using trylock and generating new storage if the lock is busy, yielding a classic space versus time tradeoff;
+using one of the many lock-free approaches for reducing contention on basic data-structure operations~\cite{Oyama99}.
+However, all of these approaches have degenerate cases where contention occurs.
+\subsection{False Sharing}
+\label{s:FalseSharing}
+False sharing is a dynamic phenomenon leading to cache thrashing.
+When two or more threads on separate CPUs simultaneously change different objects sharing a cache line, the change invalidates the other thread's associated cache, even though these threads may be uninterested in the other modified object.
+False sharing can occur in three different ways: program induced, allocator-induced active, and allocator-induced passive;
+a memory allocator can only affect the latter two.
+\paragraph{\newterm{Program-induced false-sharing}} occurs when one thread passes an object sharing a cache line to another thread, and both threads modify the respective objects.
+\VRef[Figure]{f:ProgramInducedFalseSharing} shows when 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$.
+Changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
+\begin{figure}
+\centering
+\subfigure[Program-Induced False-Sharing]{
+        \input{ProgramFalseSharing}
+        \label{f:ProgramInducedFalseSharing}
+} \\
+\vspace{5pt}
+\subfigure[Allocator-Induced Active False-Sharing]{
+        \input{AllocInducedActiveFalseSharing}
+        \label{f:AllocatorInducedActiveFalseSharing}
+} \\
+\vspace{5pt}
+\subfigure[Allocator-Induced Passive False-Sharing]{
+        \input{AllocInducedPassiveFalseSharing}
+        \label{f:AllocatorInducedPassiveFalseSharing}
+} % subfigure
+\caption{False Sharing}
+\label{f:FalseSharing}
+\end{figure}
+\paragraph{\newterm{Allocator-induced active false-sharing}} occurs when objects are allocated within the same cache line but to different threads.
+For example, in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}, each task allocates an object and loads a cache-line of memory into its associated cache.
+Again, changes to Object$_1$ invalidate CPU$_2$'s cache line, and changes to Object$_2$ invalidate CPU$_1$'s cache line.
+\paragraph{\newterm{Allocator-induced passive false-sharing}} is another form of allocator-induced false-sharing caused by program-induced false-sharing.
+When an object in a program-induced false-sharing situation is deallocated, a future allocation of that object may cause passive false-sharing.
+For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Task$_1$ passes Object$_2$ to Task$_2$, and Task$_2$ subsequently deallocates Object$_2$.
+Allocator-induced passive false-sharing occurs when Object$_2$ is reallocated to Task$_2$ while Task$_1$ is still using Object$_1$.
+\subsection{Heap Blowup}
+\label{s:HeapBlowup}
+In a multi-threaded program, heap blowup can occur when memory freed by one thread is inaccessible to other threads due to the allocation strategy.
+Specific examples are presented in later sections.
+\section{Multi-Threaded Memory-Allocator Features}
+\label{s:MultiThreadedMemoryAllocatorFeatures}
+By analyzing a suite of existing allocators (see \VRef{s:ExistingAllocators}), the following salient features were identified:
+\begin{list}{\arabic{enumi}.}{\usecounter{enumi}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
+\item multiple heaps
+\begin{list}{\alph{enumii})}{\usecounter{enumii}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
+\item with or without a global heap
+\item with or without ownership
+\end{list}
+\item object containers
+\begin{list}{\alph{enumii})}{\usecounter{enumii}\topsep=0.5ex\parsep=0pt\itemsep=0pt}
+\item with or without ownership
+\item fixed or variable sized
+\item global or local free-lists
+\end{list}
+\item hybrid private/public heap
+\item allocation buffer
+\item lock-free operations
+\end{list}
+The first feature, multiple heaps, pertains to different kinds of heaps.
+The second feature, object containers, pertains to the organization of objects within the storage area.
+The remaining features apply to different parts of the allocator design or implementation.
+\section{Multiple Heaps}
+\label{s:MultipleHeaps}
+A single-threaded allocator has at most one thread and heap, while a multi-threaded allocator has potentially multiple threads and heaps.
+The multiple threads cause complexity, and multiple heaps are a mechanism for dealing with the complexity.
+The spectrum ranges from multiple threads using a single heap, denoted as T:1 (see \VRef[Figure]{f:SingleHeap}), to multiple threads sharing multiple heaps, denoted as T:H (see \VRef[Figure]{f:SharedHeaps}), to one thread per heap, denoted as 1:1 (see \VRef[Figure]{f:PerThreadHeap}), which is almost back to a single-threaded allocator.
+In the T:1 model, all threads allocate and deallocate objects from one heap.
+Memory is obtained from the freed objects or reserved memory in the heap, or from the operating system (OS);
+the heap may also return freed memory to the operating system.
+The arrows indicate the direction memory conceptually moves for each kind of operation: allocation moves memory along the path from the heap/operating-system to the user application, while deallocation moves memory along the path from the application back to the heap/operating-system.
+To safely handle concurrency, a single heap uses locking to provide mutual exclusion.
+Whether using a single lock for all heap operations or fine-grained locking for different operations, a single heap may be a significant source of contention for programs with a large amount of memory allocation.
+\begin{figure}
+\centering
+\subfigure[T:1]{
+%       \input{SingleHeap.pstex_t}
+        \input{SingleHeap}
+        \label{f:SingleHeap}
+} % subfigure
+\vrule
+\subfigure[T:H]{
+%       \input{MultipleHeaps.pstex_t}
+        \input{SharedHeaps}
+        \label{f:SharedHeaps}
+} % subfigure
+\vrule
+\subfigure[1:1]{
+%       \input{MultipleHeapsGlobal.pstex_t}
+        \input{PerThreadHeap}
+        \label{f:PerThreadHeap}
+} % subfigure
+\caption{Multiple Heaps, Thread:Heap Relationship}
+\end{figure}
+In the T:H model, each thread allocates storage from several heaps depending on certain criteria, with the goal of reducing contention by spreading allocations/deallocations across the heaps.
+The decision on when to create a new heap and which heap a thread allocates from depends on the allocator design.
+The performance goal is to reduce the ratio of heaps to threads.
+In general, locking is required, since more than one thread may concurrently access a heap during its lifetime, but contention is reduced because fewer threads access a specific heap.
+Two examples of this approach are:
+\begin{description}
+\item[heap pool:]
+Multiple heaps are managed in a pool, starting with a single or a fixed number of heaps that increase\-/decrease depending on contention\-/space issues.
+At creation, a thread is associated with a heap from the pool.
+When the thread attempts an allocation and its associated heap is locked (contention), it scans for an unlocked heap in the pool.
+If an unlocked heap is found, the thread changes its association and uses that heap.
+If all heaps are locked, the thread may create a new heap, use it, and then place the new heap into the pool;
+or the thread can block waiting for a heap to become available.
+While the heap-pool approach often minimizes the number of extant heaps, the worse case can result in more heaps than threads;
+\eg if the number of threads is large at startup with many allocations creating a large number of heaps and then the number of threads reduces.
+\item[kernel threads:]
+Each kernel thread (CPU) executing an application has its own heap.
+A thread allocates/deallocates from/to the heap of the kernel thread on which it is executing.
+Special precautions must be taken to handle or prevent the case where a thread is preempted during allocation/deallocation and restarts execution on a different kernel thread~\cite{Dice02}.
+\end{description}
+In the 1:1 model (thread heaps), each thread has its own heap, which eliminates contention and locking because no thread accesses another thread's heap.
+An additional benefit of thread heaps is improved locality due to better memory layout.
+As each thread only allocates from its heap, all objects for a thread are more consolidated in the storage area for that heap, better utilizing each CPUs cache and accessing fewer pages.
+In contrast, the T:H model spreads each thread's objects over a larger area in different heaps.
+Thread heaps can also eliminate allocator-induced active false-sharing, if memory is acquired so it does not overlap at crucial boundaries with memory for another thread's heap.
+For example, assume page boundaries coincide with cache line boundaries, 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.
+Hence, allocator-induced active false-sharing in \VRef[Figure]{f:AllocatorInducedActiveFalseSharing} cannot occur because the memory for thread heaps never overlaps.
+Threads using multiple heaps need to determine the specific heap to access for an allocation/deallocation, \ie association of thread to heap.
+A number of techniques are used to establish this association.
+The simplest approach is for each thread to have a pointer to its associated heap (or to administrative information that points to the heap), and this pointer changes if the association changes.
+For threading systems with thread-local/specific storage, the heap pointer/data is created using this mechanism;
+otherwise, the heap routines must use approaches like hashing the thread's stack-pointer or thread-id to find its associated heap.
+The storage management for multiple heaps is more complex than for a single heap (see \VRef[Figure]{f:AllocatorComponents}).
+\VRef[Figure]{f:MultipleHeapStorage} illustrates the general storage layout for multiple heaps.
+Allocated and free objects are labelled by the thread or heap they are associated with.
+(Links between free objects are removed for simplicity.)
+The management information in the static zone must be able to locate all heaps in the dynamic zone.
+The management information for the heaps must reside in the dynamic-allocation zone if there are a variable number.
+Each heap in the dynamic zone is composed of a list of a free objects and a pointer to its reserved memory.
+An alternative implementation is for all heaps to share one reserved memory, which requires a separate lock for the reserved storage to ensure mutual exclusion when acquiring new memory.
+Because multiple threads can allocate/free/reallocate adjacent storage, all forms of false sharing may occur.
+Other storage-management options are to use @mmap@ to set aside (large) areas of virtual memory for each heap and suballocate each heap's storage within that area.
+\begin{figure}
+\centering
+\input{MultipleHeapsStorage}
+\caption{Multiple-Heap Storage}
+\label{f:MultipleHeapStorage}
+\end{figure}
+Multiple heaps increase external fragmentation as the ratio of heaps to threads increases, which can lead to heap blowup.
+The external fragmentation experienced by a program with a single heap is now multiplied by the number of heaps, since each heap manages its own free storage and allocates its own reserved memory.
+Additionally, objects freed by one heap cannot be reused by other threads, except indirectly by returning free memory to the operating system, which can be expensive.
+(Depending on how the operating system provides dynamic storage to an application, returning storage may be difficult or impossible, \eg the contiguous @sbrk@ area in Unix.)
+In the worst case, a program in which objects are allocated from one heap but deallocated to another heap means these freed objects are never reused.
+Adding a \newterm{global heap} (G) attempts to reduce the cost of obtaining/returning memory among heaps (sharing) by buffering storage within the application address-space.
+Now, each heap obtains and returns storage to/from the global heap rather than the operating system.
+Storage is obtained from the global heap only when a heap allocation cannot be fulfilled, and returned to the global heap when a heap's free memory exceeds some threshold.
+Similarly, the global heap buffers this memory, obtaining and returning storage to/from the operating system as necessary.
+The global heap does not have its own thread and makes no internal allocation requests;
+instead, it uses the application thread, which called one of the multiple heaps and then the global heap, to perform operations.
+Hence, the worst-case cost of a memory operation includes all these steps.
+With respect to heap blowup, the global heap provides an indirect mechanism to move free memory among heaps, which usually has a much lower cost than interacting with the operating system to achieve the same goal and is independent of the mechanism used by the operating system to present dynamic memory to an address space.
+However, since any thread may indirectly perform a memory operation on the global heap, it is a shared resource that requires locking.
+A single lock can be used to protect the global heap or fine-grained locking can be used to reduce contention.
+In general, the cost is minimal since the majority of memory operations are completed without the use of the global heap.
+For thread heaps, when a kernel/user-thread terminates, there are two options for handling its heap.
+First is to free all objects in the heap to the global heap and destroy the thread heap.
+Second is to place the thread heap on a list of available heaps and reuse it for a new kernel/user thread in the future.
+Destroying the thread heap immediately may reduce external fragmentation sooner, since all free objects are freed to the global heap and may be reused by other threads.
+Alternatively, reusing thread heaps may improve performance if the inheriting thread makes similar allocation requests as the thread that previously held the thread heap.
+As multiple heaps are a key feature for a multi-threaded allocator, all further discussion assumes multiple heaps with a global heap to eliminate direct interaction with the operating system.
+\subsection{Ownership}
+\label{s:Ownership}
+\newterm{Ownership} defines which heap an object is returned-to on deallocation.
+If a thread returns an object to the heap it was originally allocated from, the heap has ownership of its objects.
+Alternatively, 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.
+\VRef[Figure]{f:HeapsOwnership} shows an example of multiple heaps (minus the global heap) with and without ownership.
+Again, the arrows indicate the direction memory conceptually moves for each kind of operation.
+For the 1:1 thread:heap relationship, a thread only allocates from its own heap, and without ownership, a thread only frees objects to its own heap, which means the heap is private to its owner thread and does not require any locking, called a \newterm{private heap}.
+For the T:1/T:H models with or without ownership or the 1:1 model with ownership, a thread may free objects to different heaps, which makes each heap publicly accessible to all threads, called a \newterm{public heap}.
+\begin{figure}
+\centering
+\subfigure[Ownership]{
+        \input{MultipleHeapsOwnership}
+} % subfigure
+\hspace{0.25in}
+\subfigure[No Ownership]{
+        \input{MultipleHeapsNoOwnership}
+} % subfigure
+\caption{Heap Ownership}
+\label{f:HeapsOwnership}
+\end{figure}
+\VRef[Figure]{f:MultipleHeapStorageOwnership} shows the effect of ownership on storage layout.
+(For simplicity assume the heaps all use the same size of reserves storage.)
+In contrast to \VRef[Figure]{f:MultipleHeapStorage}, each reserved area used by a heap only contains free storage for that particular heap because threads must return free objects back to the owner heap.
+Again, because multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
+The exception is for the 1:1 model if reserved memory does not overlap a cache-line because all allocated storage within a used area is associated with a single thread.
+In this case, there is no allocator-induced active false-sharing (see \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}) because two adjacent allocated objects used by different threads cannot share a cache-line.
+As well, there is no allocator-induced passive false-sharing (see \VRef[Figure]{f:AllocatorInducedActiveFalseSharing}) because two adjacent allocated objects used by different threads cannot occur because free objects are returned to the owner heap.
+% Passive false-sharing may still occur, if delayed ownership is used (see below).
+\begin{figure}
+\centering
+\input{MultipleHeapsOwnershipStorage.pstex_t}
+\caption{Multiple-Heap Storage with Ownership}
+\label{f:MultipleHeapStorageOwnership}
+\end{figure}
+The main advantage of ownership is preventing heap blowup by returning storage for reuse by the owner heap.
+Ownership prevents the classical problem where one thread performs allocations from one heap, passes the object to another thread, and the receiving thread deallocates the object to another heap, hence draining the initial heap of storage.
+As well, allocator-induced passive false-sharing is eliminated because returning an object to its owner heap means it can never be allocated to another thread.
+For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, the deallocation by Task$_2$ returns Object$_2$ back to Task$_1$'s heap;
+hence a subsequent allocation by Task$_2$ cannot return this storage.
+The disadvantage of ownership is deallocating to another task's heap so heaps are no longer private and require locks to provide safe concurrent access.
+Object ownership can be immediate or delayed, meaning objects may be returned to the owner heap immediately at deallocation or after some delay.
+A thread may delay the return by storing objects it does not own on a separate free list.
+Delaying can improve performance by batching objects for return to their owner heap and possibly reallocating these objects if storage runs out on the current heap.
+However, reallocation can result in passive false-sharing.
+For example, in \VRef[Figure]{f:AllocatorInducedPassiveFalseSharing}, Object$_2$ may be deallocated to Task$_2$'s heap initially.
+If Task$_2$ reallocates Object$_2$ before it is returned to its owner heap, then passive false-sharing may occur.
+\section{Object Containers}
+\label{s:ObjectContainers}
+One approach for managing objects places headers/trailers around individual objects, meaning memory adjacent to the object is reserved for object-management information, as shown in \VRef[Figure]{f:ObjectHeaders}.
+However, this approach leads to poor cache usage, since only a portion of the cache line is holding useful information from the program's perspective.
+Spatial locality is also negatively affected.
+While the header and object are together in memory, they are generally not accessed together;
+\eg the object is accessed by the program when it is allocated, while the header is accessed by the allocator when the object is free.
+This difference in usage patterns can lead to poor cache locality~\cite{Feng05}.
+Additionally, placing headers on individual objects can lead to redundant management information.
+For example, if a header stores only the object size, then all objects with the same size have identical headers.
+\begin{figure}
+\centering
+\subfigure[Object Headers]{
+        \input{ObjectHeaders}
+        \label{f:ObjectHeaders}
+} % subfigure
+\\
+\subfigure[Object Container]{
+        \input{Container}
+        \label{f:ObjectContainer}
+} % subfigure
+\caption{Header Placement}
+\label{f:HeaderPlacement}
+\end{figure}
+An alternative approach for managing objects factors common header/trailer information to a separate location in memory and organizes associated free storage into blocks called \newterm{object containers} (\newterm{superblocks} in~\cite{Berger00}), as in \VRef[Figure]{f:ObjectContainer}.
+The header for the container holds information necessary for all objects in the container;
+a trailer may also be used at the end of the container.
+Similar to the approach described for thread heaps in \VRef{s:MultipleHeaps}, if container boundaries do not overlap with memory of another container at crucial boundaries and all objects in a container are allocated to the same thread, allocator-induced active false-sharing is avoided.
+The difficulty with object containers lies in finding the object header/trailer given only the object address, since that is normally the only information passed to the deallocation operation.
+One way to do this is to start containers on aligned addresses in memory, then truncate the lower bits of the object address to obtain the header address (or round up and subtract the trailer size to obtain the trailer address).
+For example, if an object at address 0xFC28\,EF08 is freed and containers are aligned on 64\,KB (0x0001\,0000) addresses, then the container header is at 0xFC28\,0000.
+Normally, a container has homogeneous objects of fixed size, with fixed information in the header that applies to all container objects (\eg object size and ownership).
+This approach greatly reduces internal fragmentation since far fewer headers are required, and potentially increases spatial locality as a cache line or page holds more objects since the objects are closer together due to the lack of headers.
+However, although similar objects are close spatially within the same container, different sized objects are further apart in separate containers.
+Depending on the program, this may or may not improve locality.
+If the program uses several objects from a small number of containers in its working set, then locality is improved since fewer cache lines and pages are required.
+If the program uses many containers, there is poor locality, as both caching and paging increase.
+Another drawback is that external fragmentation may be increased since containers reserve space for objects that may never be allocated by the program, \ie there are often multiple containers for each size only partially full.
+However, external fragmentation can be reduced by using small containers.
+Containers with heterogeneous objects implies different headers describing them, which complicates the problem of locating a specific header solely by an address.
+A couple of solutions can be used to implement containers with heterogeneous objects.
+However, the problem with allowing objects of different sizes is that the number of objects, and therefore headers, in a single container is unpredictable.
+One solution allocates headers at one end of the container, while allocating objects from the other end of the container;
+when the headers meet the objects, the container is full.
+Freed objects cannot be split or coalesced since this causes the number of headers to change.
+The difficulty in this strategy remains in finding the header for a specific object;
+in general, a search is necessary to find the object's header among the container headers.
+A second solution combines the use of container headers and individual object headers.
+Each object header stores the object's heterogeneous information, such as its size, while the container header stores the homogeneous information, such as the owner when using ownership.
+This approach allows containers to hold different types of objects, but does not completely separate headers from objects.
+The benefit of the container in this case is to reduce some redundant information that is factored into the container header.
+In summary, object containers trade off internal fragmentation for external fragmentation by isolating common administration information to remove/reduce internal fragmentation, but at the cost of external fragmentation as some portion of a container may not be used and this portion is unusable for other kinds of allocations.
+A consequence of this tradeoff is its effect on spatial locality, which can produce positive or negative results depending on program access-patterns.
+\subsection{Container Ownership}
+\label{s:ContainerOwnership}
+Without ownership, objects in a container are deallocated to the heap currently associated with the thread that frees the object.
+Thus, different objects in a container may be on different heap free-lists (see \VRef[Figure]{f:ContainerNoOwnershipFreelist}).
+With ownership, all objects in a container belong to the same heap (see \VRef[Figure]{f:ContainerOwnershipFreelist}), so ownership of an object is determined by the container owner.
+If multiple threads can allocate/free/reallocate adjacent storage in the same heap, all forms of false sharing may occur.
+Only with the 1:1 model and ownership is active and passive false-sharing avoided (see \VRef{s:Ownership}).
+Passive false-sharing may still occur, if delayed ownership is used.
+\begin{figure}
+\centering
+\subfigure[No Ownership]{
+        \input{ContainerNoOwnershipFreelist}
+        \label{f:ContainerNoOwnershipFreelist}
+} % subfigure
+\vrule
+\subfigure[Ownership]{
+        \input{ContainerOwnershipFreelist}
+        \label{f:ContainerOwnershipFreelist}
+} % subfigure
+\caption{Free-list Structure with Container Ownership}
+\end{figure}
+A fragmented heap has multiple containers that may be partially or completely free.
+A completely free container can become reserved storage and be reset to allocate objects of a new size.
+When a heap reaches a threshold of free objects, it moves some free storage to the global heap for reuse to prevent heap blowup.
+Without ownership, when a heap frees objects to the global heap, individual objects must be passed, and placed on the global-heap's free-list.
+Containers cannot be freed to the global heap unless completely free because
+When a container changes ownership, the ownership of all objects within it change as well.
+Moving a container involves moving all objects on the heap's free-list in that container to the new owner.
+This approach can reduce contention for the global heap, since each request for objects from the global heap returns a container rather than individual objects.
+Additional restrictions may be applied to the movement of containers to prevent active false-sharing.
+For example, in \VRef[Figure]{f:ContainerFalseSharing1}, a container being used by Task$_1$ changes ownership, through the global heap.
+In \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.
+Note, once the object is freed by Task$_1$, no more false sharing can occur until the container changes ownership again.
+To prevent this form of false sharing, container movement may be restricted to when all objects in the container are free.
+One implementation approach that increases the freedom to return a free container to the operating system involves allocating containers using a call like @mmap@, which allows memory at an arbitrary address to be returned versus only storage at the end of the contiguous @sbrk@ area.
+\begin{figure}
+\centering
+\subfigure[]{
+        \input{ContainerFalseSharing1}
+        \label{f:ContainerFalseSharing1}
+} % subfigure
+\subfigure[]{
+        \input{ContainerFalseSharing2}
+        \label{f:ContainerFalseSharing2}
+} % subfigure
+\caption{Active False-Sharing using Containers}
+\label{f:ActiveFalseSharingContainers}
+\end{figure}
+Using containers with ownership increases external fragmentation since a new container for a requested object size must be allocated separately for each thread requesting it.
+In \VRef[Figure]{f:ExternalFragmentationContainerOwnership}, using object ownership allocates 80\% more space than without ownership.
+\begin{figure}
+\centering
+\subfigure[No Ownership]{
+        \input{ContainerNoOwnership}
+} % subfigure
+\\
+\subfigure[Ownership]{
+        \input{ContainerOwnership}
+} % subfigure
+\caption{External Fragmentation with Container Ownership}
+\label{f:ExternalFragmentationContainerOwnership}
+\end{figure}
+\subsection{Container Size}
+\label{s:ContainerSize}
+One way to control the external fragmentation caused by allocating a large container for a small number of requested objects is to vary the size of the container.
+As described earlier, container boundaries need to be aligned on addresses that are a power of two to allow easy location of the header (by truncating lower bits).
+Aligning containers in this manner also determines the size of the container.
+However, the size of the container has different implications for the allocator.
+The larger the container, the fewer containers are needed, and hence, the fewer headers need to be maintained in memory, improving both internal fragmentation and potentially performance.
+However, with more objects in a container, there may be more objects that are unallocated, increasing external fragmentation.
+With smaller containers, not only are there more containers, but a second new problem arises where objects are larger than the container.
+In general, large objects, \eg greater than 64\,KB, are allocated directly from the operating system and are returned immediately to the operating system to reduce long-term external fragmentation.
+If the container size is small, \eg 1\,KB, then a 1.5\,KB object is treated as a large object, which is likely to be inappropriate.
+Ideally, it is best to use smaller containers for smaller objects, and larger containers for medium objects, which leads to the issue of locating the container header.
+In order to find the container header when using different sized containers, a super container is used (see~\VRef[Figure]{f:SuperContainers}).
+The super container spans several containers, contains a header with information for finding each container header, and starts on an aligned address.
+Super-container headers are found using the same method used to find container headers by dropping the lower bits of an object address.
+The containers within a super container may be different sizes or all the same size.
+If the containers in the super container are different sizes, then the super-container header must be searched to determine the specific container for an object given its address.
+If all containers in the super container are the same size, \eg 16KB, then a specific container header can be found by a simple calculation.
+The free space at the end of a super container is used to allocate new containers.
+\begin{figure}
+\centering
+\input{SuperContainers}
+% \includegraphics{diagrams/supercontainer.eps}
+\caption{Super Containers}
+\label{f:SuperContainers}
+\end{figure}
+Minimal internal and external fragmentation is achieved by having as few containers as possible, each being as full as possible.
+It is also possible to achieve additional benefit by using larger containers for popular small sizes, as it reduces the number of containers with associated headers.
+However, this approach assumes it is possible for an allocator to determine in advance which sizes are popular.
+Keeping statistics on requested sizes allows the allocator to make a dynamic decision about which sizes are popular.
+For example, after receiving a number of allocation requests for a particular size, that size is considered a popular request size and larger containers are allocated for that size.
+If the decision is incorrect, larger containers than necessary are allocated that remain mostly unused.
+A programmer may be able to inform the allocator about popular object sizes, using a mechanism like @mallopt@, in order to select an appropriate container size for each object size.
+\subsection{Container Free-Lists}
+\label{s:containersfreelists}
+The container header allows an alternate approach for managing the heap's free-list.
+Rather than maintain a global free-list throughout the heap (see~\VRef[Figure]{f:GlobalFreeListAmongContainers}), the containers are linked through their headers and only the local free objects within a container are linked together (see~\VRef[Figure]{f:LocalFreeListWithinContainers}).
+Note, maintaining free lists within a container assumes all free objects in the container are associated with the same heap;
+thus, this approach only applies to containers with ownership.
+This alternate free-list approach can greatly reduce the complexity of moving all freed objects belonging to a container to another heap.
+To move a container using a global free-list, as in \VRef[Figure]{f:GlobalFreeListAmongContainers}, the free list is first searched to find all objects within the container.
+Each object is then removed from the free list and linked together to form a local free-list for the move to the new heap.
+With local free-lists in containers, as in \VRef[Figure]{f:LocalFreeListWithinContainers}, the container is simply removed from one heap's free list and placed on the new heap's free list.
+Thus, when using local free-lists, the operation of moving containers is reduced from $O(N)$ to $O(1)$.
+The cost is adding information to a header, which increases the header size, and therefore internal fragmentation.
+\begin{figure}
+\centering
+\subfigure[Global Free-List Among Containers]{
+        \input{FreeListAmongContainers}
+        \label{f:GlobalFreeListAmongContainers}
+} % subfigure
+\hspace{0.25in}
+\subfigure[Local Free-List Within Containers]{
+        \input{FreeListWithinContainers}
+        \label{f:LocalFreeListWithinContainers}
+} % subfigure
+\caption{Container Free-List Structure}
+\label{f:ContainerFreeListStructure}
+\end{figure}
+When all objects in the container are the same size, a single free-list is sufficient.
+However, when objects in the container are different size, the header needs a free list for each size class when using a binning allocation algorithm, which can be a significant increase in the container-header size.
+The alternative is to use a different allocation algorithm with a single free-list, such as a sequential-fit allocation-algorithm.
+\subsection{Hybrid Private/Public Heap}
+\label{s:HybridPrivatePublicHeap}
+Section~\Vref{s:Ownership} discusses advantages and disadvantages of public heaps (T:H model and with ownership) and private heaps (thread heaps with ownership).
+For thread heaps with ownership, it is possible to combine these approaches into a hybrid approach with both private and public heaps (see~\VRef[Figure]{f:HybridPrivatePublicHeap}).
+The main goal of the hybrid approach is to eliminate locking on thread-local allocation/deallocation, while providing ownership to prevent heap blowup.
+In the hybrid approach, a task first allocates from its private heap and second from its public heap if no free memory exists in the private heap.
+Similarly, a task first deallocates an object its private heap, and second to the public heap.
+Both private and public heaps can allocate/deallocate to/from the global heap if there is no free memory or excess free memory, although an implementation may choose to funnel all interaction with the global heap through one of the heaps.
+Note, deallocation from the private to the public (dashed line) is unlikely because there is no obvious advantages unless the public heap provides the only interface to the global heap.
+Finally, when a 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.
+\begin{figure}
+\centering
+\input{PrivatePublicHeaps.pstex_t}
+\caption{Hybrid Private/Public Heap for Per-thread Heaps}
+\label{f:HybridPrivatePublicHeap}
+% \vspace{10pt}
+% \input{RemoteFreeList.pstex_t}
+% \caption{Remote Free-List}
+% \label{f:RemoteFreeList}
+\end{figure}
+As mentioned, an implementation may have only one heap deal with the global heap, so the other heap can be simplified.
+For example, if only the private heap interacts with the global heap, the public heap can be reduced to a lock-protected free-list of objects deallocated by other threads due to ownership, called a \newterm{remote free-list}.
+To avoid heap blowup, the private heap allocates from the remote free-list when it reaches some threshold or it has no free storage.
+Since the remote free-list is occasionally cleared during an allocation, this adds to that cost.
+Clearing the remote free-list is $O(1)$ if the list can simply be added to the end of the private-heap's free-list, or $O(N)$ if some action must be performed for each freed object.
+If only the public heap interacts with other threads and the global heap, the private heap can handle thread-local allocations and deallocations without locking.
+In this scenario, the private heap must deallocate storage after reaching a certain threshold to the public heap (and then eventually to the global heap from the public heap) or heap blowup can occur.
+If the public heap does the major management, the private heap can be simplified to provide high-performance thread-local allocations and deallocations.
+The main disadvantage of each thread having both a private and public heap is the complexity of managing two heaps and their interactions in an allocator.
+Interestingly, heap implementations often focus on either a private or public heap, giving the impression a single versus a hybrid approach is being used.
+In many case, the hybrid approach is actually being used, but the simpler heap is just folded into the complex heap, even though the operations logically belong in separate heaps.
+For example, a remote free-list is actually a simple public-heap, but may be implemented as an integral component of the complex private-heap in an allocator, masking the presence of a hybrid approach.
+\section{Allocation Buffer}
+\label{s:AllocationBuffer}
+An allocation buffer is reserved memory (see~\VRef{s:AllocatorComponents}) not yet allocated to the program, and is used for allocating objects when the free list is empty.
+That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
+Both any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or operating system, respectively.
+The allocation buffer reduces contention and the number of global/operating-system calls.
+For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.
+Allocation buffers are useful initially when there are no freed objects in a heap because many allocations usually occur when a thread starts.
+Furthermore, to prevent heap blowup, objects should be reused before allocating a new allocation buffer.
+Thus, allocation buffers are often allocated more frequently at program/thread start, and then their use often diminishes.
+Using an allocation buffer with a thread heap avoids active false-sharing, since all objects in the allocation buffer are allocated to the same thread.
+For example, if all objects sharing a cache line come from the same allocation buffer, then these objects are allocated to the same thread, avoiding active false-sharing.
+Active false-sharing may still occur if objects are freed to the global heap and reused by another heap.
+Allocation buffers may increase external fragmentation, since some memory in the allocation buffer may never be allocated.
+A smaller allocation buffer reduces the amount of external fragmentation, but increases the number of calls to the global heap or operating system.
+The allocation buffer also slightly increases internal fragmentation, since a pointer is necessary to locate the next free object in the buffer.
+The unused part of a container, neither allocated or freed, is an allocation buffer.
+For example, when a container is created, rather than placing all objects within the container on the free list, the objects form an allocation buffer and are allocated from the buffer as allocation requests are made.
+This lazy method of constructing objects is beneficial in terms of paging and caching.
+For example, although an entire container, possibly spanning several pages, is allocated from the operating system, only a small part of the container is used in the working set of the allocator, reducing the number of pages and cache lines that are brought into higher levels of cache.
+\section{Lock-Free Operations}
+\label{s:LockFreeOperations}
+A 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}.
+% 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
+Lock-free operations can be used in an allocator to reduce or eliminate the use of locks.
+Locks are a problem for high contention or if the thread holding the lock is preempted and other threads attempt to use that lock.
+With 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.
+Nevertheless, lock-free algorithms can reduce the number of context switches, since a thread does not yield/block while waiting for a lock;
+on the other hand, a thread may busy-wait for an unbounded period.
+Finally, lock-free implementations have greater complexity and hardware dependency.
+Lock-free algorithms can be applied most easily to simple free-lists, \eg remote free-list, to allow lock-free insertion and removal from the head of a stack.
+Implementing lock-free operations for more complex data-structures (queue~\cite{Valois94}/deque~\cite{Sundell08}) is more complex.
+Michael~\cite{Michael04} and Gidenstam \etal \cite{Gidenstam05} have created lock-free variations of the Hoard allocator.
 \noindent
 …
 ====================
-\section{Background}
 % FIXME: cite wasik
 \cite{wasik.thesis}
 \subsection{Memory Allocation}
 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.
+\section{Existing Memory Allocators}
+With 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.
 \paragraph{dlmalloc}
 …
 \paragraph{hoard}
 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)
+Hoard (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)
 \paragraph{jemalloc}
 …
 \paragraph{rpmalloc}
 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.
+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-class contains memory regions of the relevant size.
 \paragraph{tbb malloc}
 …
 \paragraph{tc malloc}
 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.
-\subsection{Benchmarks}
-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.
-\paragraph{threadtest}
-(FIX ME: cite benchmark and hoard) Each thread repeatedly allocates and then deallocates 100,000 objects. Runtime of the benchmark evaluates its efficiency.
-\paragraph{shbench}
-(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.
-\paragraph{larson}
-(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.

doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

-              rf5a51db
+              rcc7bbe6
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Benchmarks}
+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.
+\paragraph{threadtest}
+(FIX ME: cite benchmark and hoard) Each thread repeatedly allocates and then deallocates 100,000 objects. Runtime of the benchmark evaluates its efficiency.
+\paragraph{shbench}
+(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.
+\paragraph{larson}
+(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.
 \section{Performance Matrices of Memory Allocators}

doc/theses/mubeen_zulfiqar_MMath/intro.tex

-              rf5a51db
+              rcc7bbe6
 \chapter{Introduction}
+% Shared-memory multi-processor computers are ubiquitous and important for improving application performance.
+% 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.
+% One crucial shared resource is program memory, since it is used by all threads in a shared-memory concurrent-program~\cite{Berger00}.
+% Therefore, providing high-performance, scalable memory-management is important for virtually all shared-memory multi-threaded programs.
+\vspace*{-23pt}
+Memory 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.
+A general-purpose dynamic-allocation algorithm cannot anticipate future allocation requests so its output is rarely optimal.
+However, 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).
+In general, allocators use a number of similar techniques, each optimizing specific allocation patterns.
+Nevertheless, memory allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific program-request patterns.
+\section{Memory Structure}
+\label{s:MemoryStructure}
+\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}.
+Static code and data are placed into memory at load time from the executable and are fixed-sized at runtime.
+Dynamic-allocation memory starts empty and grows/shrinks as the program dynamically creates/deletes variables with independent lifetime.
+The programming-language's runtime manages this area, where management complexity is a function of the mechanism for deleting variables.
+Dynamic 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}.
+However, changes to the dynamic code/data space are typically infrequent, many occurring at program startup, and are largely outside of a program's control.
+Stack memory is managed by the program call-mechanism using a simple LIFO technique, which works well for sequential programs.
+For multi-threaded programs (and coroutines), a new stack is created for each thread;
+these thread stacks are commonly created in dynamic-allocation memory.
+This thesis focuses on management of the dynamic-allocation memory.
+\begin{figure}
+\centering
+\input{AddressSpace}
+\vspace{-5pt}
+\caption{Program Address Space Divided into Zones}
+\label{f:ProgramAddressSpace}
+\end{figure}
+\section{Dynamic Memory-Management}
+\label{s:DynamicMemoryManagement}
+Modern programming languages manage dynamic-allocation memory in different ways.
+Some 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}.
+In general, garbage collection supports memory compaction, where dynamic (live) data is moved during runtime to better utilize space.
+However, moving data requires finding pointers to it and updating them to reflect new data locations.
+Programming languages such as C~\cite{C}, \CC~\cite{C++}, and Rust~\cite{Rust} provide the programmer with explicit allocation \emph{and} deallocation of data.
+These 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.
+Attempts have been made to perform quasi garbage collection in C/\CC~\cite{Boehm88}, but it is a compromise.
+This thesis only examines dynamic memory-management with \emph{explicit} deallocation.
+While garbage collection and compaction are not part this work, many of the results are applicable to the allocation phase in any memory-management approach.
+Most programs use a general-purpose allocator, often the one provided implicitly by the programming-language's runtime.
+When this allocator proves inadequate, programmers often write specialize allocators for specific needs.
+C and \CC allow easy replacement of the default memory allocator with an alternative specialized or general-purpose memory-allocator.
+(Jikes RVM MMTk~\cite{MMTk} provides a similar generalization for the Java virtual machine.)
+However, high-performance memory-allocators for kernel and user multi-threaded programs are still being designed and improved.
+For 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}.
+This thesis examines the design of high-performance allocators for use by kernel and user multi-threaded applications written in C/\CC.
+\section{Contributions}
+\label{s:Contributions}
+This work provides the following contributions in the area of concurrent dynamic allocation:
+\begin{enumerate}[leftmargin=*]
+\item
+Implementation 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).
+\item
+Adopt returning of @nullptr@ for a zero-sized allocation, rather than an actual memory address, both of which can be passed to @free@.
+\item
+Extended 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.
+\item
+Use 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.
+Without this extension, it is unsafe to @realloc@ storage initially allocated with zero-fill/alignment as these properties are not preserved when copying.
+This silent generation of a problem is unintuitive to programmers and difficult to locate because it is transient.
+\item
+Provide additional heap operations to complete programmer expectation with respect to accessing different allocation properties.
+\begin{itemize}
+\item
+@resize( oaddr, size )@ re-purpose an old allocation for a new type \emph{without} preserving fill or alignment.
+\item
+@resize( oaddr, alignment, size )@ re-purpose an old allocation with new alignment but \emph{without} preserving fill.
+\item
+@realloc( oaddr, alignment, size )@ same as previous @realloc@ but adding or changing alignment.
+\item
+@aalloc( dim, elemSize )@ same as @calloc@ except memory is \emph{not} zero filled.
+\item
+@amemalign( alignment, dim, elemSize )@ same as @aalloc@ with memory alignment.
+\item
+@cmemalign( alignment, dim, elemSize )@ same as @calloc@ with memory alignment.
+\end{itemize}
+\item
+Provide additional query operations to access information about an allocation:
+\begin{itemize}
+\item
+@malloc_alignment( addr )@ returns the alignment of the allocation pointed-to by @addr@.
+If the allocation is not aligned or @addr@ is the @nulladdr@, the minimal alignment is returned.
+\item
+@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@.
+\item
+@malloc_size( addr )@ returns the size of the memory allocation pointed-to by @addr@.
+\item
+@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 )@.
+\end{itemize}
+\item
+Provide mostly contention-free allocation and free operations via a heap-per-kernel-thread implementation.
+\item
+Provide complete, fast, and contention-free allocation statistics to help understand program behaviour:
+\begin{itemize}
+\item
+@malloc_stats()@ print memory-allocation statistics on the file-descriptor set by @malloc_stats_fd@.
+\item
+@malloc_info( options, stream )@ print memory-allocation statistics as an XML string on the specified file-descriptor set by @malloc_stats_fd@.
+\item
+@malloc_stats_fd( fd )@ set file-descriptor number for printing memory-allocation statistics (default @STDERR_FILENO@).
+This file descriptor is used implicitly by @malloc_stats@ and @malloc_info@.
+\end{itemize}
+\item
+Provide extensive runtime checks to valid allocation operations and identify the amount of unfreed storage at program termination.
+\item
+Build 4 different versions of the allocator:
+\begin{itemize}
+\item
+static or dynamic linking
+\item
+statistic/debugging (testing) or no statistic/debugging (performance)
+\end{itemize}
+A program may link to any of these 4 versions of the allocator often without recompilation.
+(It is possible to separate statistics and debugging, giving 8 different versions.)
+\item
+A micro-benchmark test-suite for comparing allocators rather than relying on a suite of arbitrary programs.
+These micro-benchmarks have adjustment knobs to simulate allocation patterns hard-coded into arbitrary test programs
+\end{enumerate}
+\begin{comment}
 \noindent
 ====================
 …
 \section{Introduction}
 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.
 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.
 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:
+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 programmer that can be used to allocate/free dynamic memory for the application's use.
+Memory 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.
+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 stand-alone memory allocator. GNU C Library requires new memory allocators to have at lease following set of functions in their allocator's interface:
 \begin{itemize}
 …
 \end{itemize}
 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.
+In 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.
 \begin{itemize}
 …
 \end{itemize}
 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.
+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 scenarios.
 \section{Research Objectives}
 …
 Design a lightweight concurrent memory allocator with added features and usability that are currently not present in the other memory allocators.
 \item
 Design a suite of benchmarks to evalute multiple aspects of a memory allocator.
+Design a suite of benchmarks to evaluate multiple aspects of a memory allocator.
 \end{itemize}
 \section{An outline of the thesis}
 LAST FIX ME: add outline at the end
+\end{comment}

doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.bib

-              rf5a51db
+              rcc7bbe6
     year          = "2008"
+}
+@article{Sleator85,
+    author      = {Sleator, Daniel Dominic and Tarjan, Robert Endre},
+    title       = {Self-Adjusting Binary Search Trees},
+    journal     = jacm,
+    volume      = 32,
+    number      = 3,
+    year        = 1985,
+    issn        = {0004-5411},
+    pages       = {652-686},
+    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/3828.3835},
+    address     = {New York, NY, USA},
+}
+@article{Berger00,
+    author      = {Emery D. Berger and Kathryn S. McKinley and Robert D. Blumofe and Paul R. Wilson},
+    title       = {Hoard: A Scalable Memory Allocator for Multithreaded Applications},
+    booktitle   = {International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX)},
+    journal     = sigplan,
+    volume      = 35,
+    number      = 11,
+    month       = nov,
+    year        = 2000,
+    pages       = {117-128},
+    note        = {International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS-IX)},
+}
+@inproceedings{berger02reconsidering,
+    author      = {Emery D. Berger and Benjamin G. Zorn and Kathryn S. McKinley},
+    title       = {Reconsidering Custom Memory Allocation},
+    booktitle   = {Proceedings of the 17th ACM SIGPLAN Conference on Object-Oriented Programming: Systems, Languages, and Applications (OOPSLA) 2002},
+    month       = nov,
+    year        = 2002,
+    location    = {Seattle, Washington, USA},
+    publisher   = {ACM},
+    address     = {New York, NY, USA},
+}
+@article{larson99memory,
+    author      = {Per-{\AA}ke Larson and Murali Krishnan},
+    title       = {Memory Allocation for Long-Running Server Applications},
+    journal     = sigplan,
+    volume      = 34,
+    number      = 3,
+    pages       = {176-185},
+    year        = 1999,
+    url         = {http://citeseer.ist.psu.edu/article/larson98memory.html}
+}
+@techreport{gidpt04,
+    author      = {Anders Gidenstam and Marina Papatriantafilou and Philippas Tsigas},
+    title       = {Allocating Memory in a Lock-Free Manner},
+    number      = {2004-04},
+    institution = {Computing Science},
+    address     = {Chalmers University of Technology},
+    year        = 2004,
+    url         = {http://citeseer.ist.psu.edu/gidenstam04allocating.html}
+}
+@phdthesis{berger02thesis,
+    author      = {Emery Berger},
+    title       = {Memory Management for High-Performance Applications},
+    school      = {The University of Texas at Austin},
+    year        = 2002,
+    month       = aug,
+    url         = {http://citeseer.ist.psu.edu/article/berger02memory.html}
+}
+@misc{sgimisc,
+    author      = {SGI},
+    title       = {The Standard Template Library for {C++}},
+    note        = {\textsf{www.sgi.com/\-tech/\-stl/\-Allocators.html}},
+}
+@misc{dlmalloc,
+    author      = {Doug Lea},
+    title       = {dlmalloc version 2.8.4},
+    month       = may,
+    year        = 2009,
+    note        = {\textsf{ftp://g.oswego.edu/\-pub/\-misc/\-malloc.c}},
+}
+@misc{ptmalloc2,
+    author      = {Wolfram Gloger},
+    title       = {ptmalloc version 2},
+    month       = jun,
+    year        = 2006,
+    note        = {\textsf{http://www.malloc.de/\-malloc/\-ptmalloc2-current.tar.gz}},
+}
+@misc{nedmalloc,
+    author      = {Niall Douglas},
+    title       = {nedmalloc version 1.06 Beta},
+    month       = jan,
+    year        = 2010,
+    note        = {\textsf{http://\-prdownloads.\-sourceforge.\-net/\-nedmalloc/\-nedmalloc\_v1.06beta1\_svn1151.zip}},
+}
+@misc{hoard,
+    author      = {Emery D. Berger},
+    title       = {hoard version 3.8},
+    month       = nov,
+    year        = 2009,
+    note        = {\textsf{http://www.cs.umass.edu/\-$\sim$emery/\-hoard/\-hoard-3.8/\-source/hoard-38.tar.gz}},
+}
+@comment{mtmalloc,
+    author      = {Greg Nakhimovsky},
+    title       = {Improving Scalability of Multithreaded Dynamic Memory Allocation},
+    journal     = {Dr. Dobb's},
+    month       = jul,
+    year        = 2001,
+    url         = {http://www.ddj.com/mobile/184404685?pgno=1}
+}
+@misc{mtmalloc,
+    key         = {mtmalloc},
+    title       = {mtmalloc.c},
+    year        = 2009,
+    note        = {\textsf{http://src.opensolaris.org/\-source/\-xref/\-onnv/\-onnv-gate/\-usr/\-src/\-lib/\-libmtmalloc/\-common/\-mtmalloc.c}},
+}
+@misc{tcmalloc,
+    author      = {Sanjay Ghemawat and Paul Menage},
+    title       = {tcmalloc version 1.5},
+    month       = jan,
+    year        = 2010,
+    note        = {\textsf{http://google-perftools.\-googlecode.\-com/\-files/\-google-perftools-1.5.tar.gz}},
+}
+@inproceedings{streamflow,
+    author      = {Scott Schneider and Christos D. Antonopoulos and Dimitrios S. Nikolopoulos},
+    title       = {Scalable Locality-Conscious Multithreaded Memory Allocation},
+    booktitle   = {International Symposium on Memory Management (ISSM'06)},
+    month       = jun,
+    year        = 2006,
+    pages       = {84-94},
+    location    = {Ottawa, Ontario, Canada},
+    publisher   = {ACM},
+    address     = {New York, NY, USA},
+}
+@misc{streamflowweb,
+    author      = {Scott Schneider and Christos Antonopoulos and Dimitrios Nikolopoulos},
+    title       = {Streamflow},
+    note        = {\textsf{http://people.cs.vt.edu/\-\char`\~scschnei/\-streamflow}},
+}
+@inproceedings{Blumofe94,
+    author      = {R. Blumofe and C. Leiserson},
+    title       = {Scheduling Multithreaded Computations by Work Stealing},
+    booktitle   = {Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico.},
+    pages       = {356-368},
+    year        = 1994,
+    month       = nov,
+    url         = {http://citeseer.ist.psu.edu/article/blumofe94scheduling.html}
+}
+@article{Johnstone99,
+    author      = {Mark S. Johnstone and Paul R. Wilson},
+    title       = {The Memory Fragmentation Problem: Solved?},
+    journal     = sigplan,
+    volume      = 34,
+    number      = 3,
+    pages       = {26-36},
+    year        = 1999,
+}
+@inproceedings{Grunwald93,
+    author      = {Dirk Grunwald and Benjamin G. Zorn and Robert Henderson},
+    title       = {Improving the Cache Locality of Memory Allocation},
+    booktitle   = {{SIGPLAN} Conference on Programming Language Design and Implementation},
+    pages       = {177-186},
+    year        = 1993,
+    url         = {http://citeseer.ist.psu.edu/grunwald93improving.html}
+}
+@inproceedings{Wilson95,
+    author      = {Wilson, Paul R. and Johnstone, Mark S. and Neely, Michael and Boles, David},
+    title       = {Dynamic Storage Allocation: A Survey and Critical Review},
+    booktitle   = {Proc. Int. Workshop on Memory Management},
+    address     = {Kinross Scotland, UK},
+    year        = 1995,
+    url         = {http://citeseer.ist.psu.edu/wilson95dynamic.html}
+}
+@inproceedings{Siebert00,
+    author      = {Fridtjof Siebert},
+    title       = {Eliminating External Fragmentation in a Non-moving Garbage Collector for Java},
+    booktitle   = {CASES '00: Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems},
+    year        = 2000,
+    isbn        = {1-58113-338-3},
+    pages       = {9-17},
+    location    = {San Jose, California, United States},
+    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/354880.354883},
+    publisher   = {ACM Press},
+    address     = {New York, NY, USA}
+}
+@inproceedings{Lim98,
+   author       = {Tian F. Lim and Przemyslaw Pardyak and Brian N. Bershad},
+   title        = {A Memory-Efficient Real-Time Non-copying Garbage Collector},
+   booktitle    = {ISMM '98: Proceedings of the 1st international symposium on Memory management},
+   year         = 1998,
+   isbn         = {1-58113-114-3},
+   pages        = {118-129},
+   location     = {Vancouver, British Columbia, Canada},
+   doi          = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/286860.286873},
+   publisher    = {ACM Press},
+   address      = {New York, NY, USA}
+}
+@article{Chang01,
+    author      = {J. Morris Chang and Woo Hyong Lee and Witawas Srisa-an},
+    title       = {A Study of the Allocation Behavior of {C++} Programs},
+    journal     = {J. Syst. Softw.},
+    volume      = 57,
+    number      = 2,
+    year        = 2001,
+    issn        = {0164-1212},
+    pages       = {107-118},
+    doi         = {http://dx.doi.org/10.1016/S0164-1212(00)00122-9},
+    publisher   = {Elsevier Science Inc.},
+    address     = {New York, NY, USA}
+}
+@article{Herlihy93,
+    author      = {Maurice Herlihy},
+    title       = {A Methodology for Implementing Highly Concurrent Data Objects},
+    journal     = toplas,
+    volume      = 15,
+    number      = 5,
+    year        = 1993,
+    issn        = {0164-0925},
+    pages       = {745-770},
+    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/161468.161469},
+    publisher   = {ACM Press},
+    address     = {New York, NY, USA}
+}
+@article{Denning05,
+    author      = {Peter J. Denning},
+    title       = {The Locality Principle},
+    journal     = cacm,
+    volume      = 48,
+    number      = 7,
+    year        = 2005,
+    issn        = {0001-0782},
+    pages       = {19-24},
+    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/1070838.1070856},
+    publisher   = {ACM Press},
+    address     = {New York, NY, USA}
+}
+@misc{wilson-locality,
+    author      = {Paul R. Wilson},
+    title       = {Locality of Reference, Patterns in Program Behavior, Memory Management, and Memory Hierarchies},
+    url         = {http://citeseer.ist.psu.edu/337869.html}
+}
+@inproceedings{Feng05,
+    author      = {Yi Feng and Emery D. Berger},
+    title       = {A Locality-Improving Dynamic Memory Allocator},
+    booktitle   = {Proceedings of the 2005 Workshop on Memory System Performance},
+    location    = {Chicago, Illinois},
+    publisher   = {ACM},
+    address     = {New York, NY, USA},
+    month       = jun,
+    year        = 2005,
+    pages       = {68-77},
+}
+@inproceedings{grunwald-locality,
+    author      = {Dirk Grunwald and Benjamin Zorn and Robert Henderson},
+    title       = {Improving the Cache Locality of Memory Allocation},
+    booktitle   = {PLDI '93: Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation},
+    year        = 1993,
+    isbn        = {0-89791-598-4},
+    pages       = {177-186},
+    location    = {Albuquerque, New Mexico, United States},
+    doi         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/155090.155107},
+    publisher   = {ACM Press},
+    address     = {New York, NY, USA}
+}
+@article{Alexandrescu01b,
+    author      = {Andrei Alexandrescu},
+    title       = {{volatile} -- Multithreaded Programmer's Best Friend},
+    journal     = {Dr. Dobb's},
+    month       = feb,
+    year        = 2001,
+    url         = {http://www.ddj.com/cpp/184403766}
+}
+@article{Attardi03,
+    author      = {Joseph Attardi and Neelakanth Nadgir},
+    title       = {A Comparison of Memory Allocators in Multiprocessors},
+    journal     = {Sun Developer Network},
+    month       = jun,
+    year        = 2003,
+    note        = {\textsf{http://developers.sun.com/\-solaris/\-articles/\-multiproc/\-multiproc.html}},
+}
+@unpublished{memlayout,
+    author      = {Peter Jay Salzman},
+    title       = {Memory Layout and the Stack},
+    journal     = {Using GNU's GDB Debugger},
+    note        = {\textsf{http://dirac.org/\-linux/\-gdb/\-02a-Memory\_Layout\_And\_The\_Stack.php}},
+}
+@unpublished{Ferguson07,
+    author      = {Justin N. Ferguson},
+    title       = {Understanding the Heap by Breaking It},
+    note        = {\textsf{https://www.blackhat.com/\-presentations/\-bh-usa-07/Ferguson/\-Whitepaper/\-bh-usa-07-ferguson-WP.pdf}},
+}
+@inproceedings{Huang06,
+    author      = {Xianglong Huang and Brian T Lewis and Kathryn S McKinley},
+    title       = {Dynamic Code Management: Improving Whole Program Code Locality in Managed Runtimes},
+    booktitle   = {VEE '06: Proceedings of the 2nd international conference on Virtual execution environments},
+    year        = 2006,
+    isbn        = {1-59593-332-6},
+    pages       = {133-143},
+    location    = {Ottawa, Ontario, Canada},
+    doi         = {http://doi.acm.org/10.1145/1134760.1134779},
+    publisher   = {ACM Press},
+    address     = {New York, NY, USA}
+ }
+@inproceedings{Herlihy03,
+    author      = {M. Herlihy and V. Luchangco and M. Moir},
+    title       = {Obstruction-free Synchronization: Double-ended Queues as an Example},
+    booktitle   = {Proceedings of the 23rd IEEE International Conference on Distributed Computing Systems},
+    year        = 2003,
+    month       = may,
+    url         = {http://www.cs.brown.edu/~mph/publications.html}
+}
+@techreport{Detlefs93,
+    author      = {David L. Detlefs and Al Dosser and Benjamin Zorn},
+    title       = {Memory Allocation Costs in Large {C} and {C++} Programs},
+    number      = {CU-CS-665-93},
+    institution = {University of Colorado},
+    address     = {130 Lytton Avenue, Palo Alto, CA 94301 and Campus Box 430, Boulder, CO 80309},
+    year        = 1993,
+    url         = {http://citeseer.ist.psu.edu/detlefs93memory.html}
+}
+@inproceedings{Oyama99,
+    author      = {Y. Oyama and K. Taura and A. Yonezawa},
+    title       = {Executing Parallel Programs With Synchronization Bottlenecks Efficiently},
+    booktitle   = {Proceedings of International Workshop on Parallel and Distributed Computing for Symbolic and Irregular Applications (PDSIA '99)},
+    year        = {1999},
+    pages       = {182--204},
+    publisher   = {World Scientific},
+    address     = {Sendai, Japan},
+}
+@inproceedings{Dice02,
+    author      = {Dave Dice and Alex Garthwaite},
+    title       = {Mostly Lock-Free Malloc},
+    booktitle   = {Proceedings of the 3rd international symposium on Memory management (ISMM'02)},
+    month       = jun,
+    year        = 2002,
+    pages       = {163-174},
+    location    = {Berlin, Germany},
+    publisher   = {ACM},
+    address     = {New York, NY, USA},
+}

doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex

-              rf5a51db
+              rcc7bbe6
 \usepackage{comment} % Removes large sections of the document.
 \usepackage{tabularx}
+\usepackage{subfigure}
 % Hyperlinks make it very easy to navigate an electronic document.
 …
 %\usepackageinput{common}
 \CFAStyle                                               % CFA code-style for all languages
+\lstset{basicstyle=\linespread{0.9}\tt}                 % CFA typewriter font
+\lstset{basicstyle=\linespread{0.9}\sf}                 % CFA typewriter font
+\newcommand{\uC}{$\mu$\CC}
 \newcommand{\PAB}[1]{{\color{red}PAB: #1}}
 …
 \addcontentsline{toc}{chapter}{\textbf{References}}
 \bibliography{uw-ethesis,pl}
+\bibliography{pl,uw-ethesis}
 % Tip: You can create multiple .bib files to organize your references.
 % Just list them all in the \bibliogaphy command, separated by commas (no spaces).

doc/user/user.tex

-              rf5a51db
+              rcc7bbe6
 %% Created On       : Wed Apr  6 14:53:29 2016
 %% Last Modified By : Peter A. Buhr
 %% Last Modified On : Sun Oct 10 12:45:00 2021
 %% Update Count     : 5095
+%% Last Modified On : Mon Feb 14 17:20:39 2022
+%% Update Count     : 5382
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 % requires tex packages: texlive-base texlive-latex-base tex-common texlive-humanities texlive-latex-extra texlive-fonts-recommended
 \documentclass[twoside,11pt]{article}
+\documentclass[twoside]{article}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
 % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
 % LaTex escape §...§ (section symbol) emacs: C-q M-'
+% LaTex escape ...§ (section symbol) emacs: C-q M-'
 % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
 % math escape $...$ (dollar symbol)
 …
 \newcommand{\B}[1]{{\Textbf[blue]{#1}}}
 \newcommand{\G}[1]{{\Textbf[OliveGreen]{#1}}}
+\newcommand{\Sp}{\R{\textvisiblespace}}
 \newcommand{\KWC}{K-W C\xspace}
 …
 One of the main design philosophies of \CFA is to ``\Index{describe not prescribe}'', which means \CFA tries to provide a pathway from low-level C programming to high-level \CFA programming, but it does not force programmers to ``do the right thing''.
 Programmers can cautiously add \CFA extensions to their C programs in any order and at any time to incrementally move towards safer, higher-level programming.
 A programmer is always free to reach back to C from \CFA, for any reason, and in many cases, new \CFA features can be locally switched back to there C counterpart.
 There is no notion or requirement for \emph{rewriting} a legacy C program in \CFA;
+A programmer is always free to reach back to C from \CFA, for any reason, and in many cases, new \CFA features can be locally switched back to their C counterpart.
+There is no notion or requirement for \emph{rewriting} a legacy C program to \CFA;
 instead, a programmer evolves a legacy program into \CFA by incrementally incorporating \CFA features.
 As well, new programs can be written in \CFA using a combination of C and \CFA features.
 …
 \Index*[C++]{\CC{}}~\cite{c++:v1} had a similar goal 30 years ago, allowing object-oriented programming to be incrementally added to C.
 However, \CC currently has the disadvantages of a strong object-oriented bias, multiple legacy design-choices that cannot be updated, and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project.
+However, \CC currently has the disadvantages of a strong object-oriented bias, multiple legacy design-choices that are difficult to update, and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project.
 In contrast, \CFA has 30 years of hindsight and a clean starting point.
 Like \Index*[C++]{\CC{}}, there may be both old and new ways to achieve the same effect.
 For example, the following programs compare the C, \CFA, and \CC I/O mechanisms, where the programs output the same result.
 \begin{center}
+\begin{flushleft}
 \begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}}
 \multicolumn{1}{c@{\hspace{1em}}}{\textbf{C}}   & \multicolumn{1}{c}{\textbf{\CFA}}     & \multicolumn{1}{c}{\textbf{\CC}}      \\
 \begin{cfa}
+\multicolumn{1}{@{}c@{\hspace{1em}}}{\textbf{C}}        & \multicolumn{1}{c}{\textbf{\CFA}}     & \multicolumn{1}{c@{}}{\textbf{\CC}}   \\
+\begin{cfa}[tabsize=3]
 #include <stdio.h>$\indexc{stdio.h}$
 …
 \end{cfa}
+&
 \begin{cfa}
+\begin{cfa}[tabsize=3]
 #include <fstream>$\indexc{fstream}$
 …
 \end{cfa}
+&
 \begin{cfa}
+\begin{cfa}[tabsize=3]
 #include <iostream>$\indexc{iostream}$
 using namespace std;
 int main() {
         int x = 0, y = 1, z = 2;
         ®cout<<x<<" "<<y<<" "<<z<<endl;®
+        ®cout << x << ' ' << y << ' ' << z << endl;®
+}
 \end{cfa}
 \end{tabular}
 \end{center}
+\end{flushleft}
 While \CFA I/O \see{\VRef{s:StreamIOLibrary}} looks similar to \Index*[C++]{\CC{}}, there are important differences, such as automatic spacing between variables and an implicit newline at the end of the expression list, similar to \Index*{Python}~\cite{Python}.
 …
 however, it largely extended the C language, and did not address many of C's existing problems.\footnote{%
 Two important existing problems addressed were changing the type of character literals from ©int© to ©char© and enumerator from ©int© to the type of its enumerators.}
 \Index*{Fortran}~\cite{Fortran08}, \Index*{Ada}~\cite{Ada12}, and \Index*{Cobol}~\cite{Cobol14} are examples of programming languages that took an evolutionary approach, where modern language-features (\eg objects, concurrency) are added and problems fixed within the framework of the existing language.
+\Index*{Fortran}~\cite{Fortran08}, \Index*{Cobol}~\cite{Cobol14}, and \Index*{Ada}~\cite{Ada12} are examples of programming languages that took an evolutionary approach, where modern language-features (\eg objects, concurrency) are added and problems fixed within the framework of the existing language.
 \Index*{Java}~\cite{Java8}, \Index*{Go}~\cite{Go}, \Index*{Rust}~\cite{Rust} and \Index*{D}~\cite{D} are examples of the revolutionary approach for modernizing C/\CC, resulting in a new language rather than an extension of the descendent.
 These languages have different syntax and semantics from C, do not interoperate directly with C, and are not systems languages because of restrictive memory-management or garbage collection.
 …
 long double _Complex ®abs®( long double _Complex );
 \end{cfa}
 The problem is \Index{name clash} between the C name ©abs© and the \CFA names ©abs©, resulting in two name linkages\index{C linkage}: ©extern "C"© and ©extern "Cforall"© (default).
+The problem is a \Index{name clash} between the C name ©abs© and the \CFA names ©abs©, resulting in two name linkages\index{C linkage}: ©extern "C"© and ©extern "Cforall"© (default).
 Overloaded names must use \newterm{name mangling}\index{mangling!name} to create unique names that are different from unmangled C names.
 Hence, there is the same need as in \CC to know if a name is a C or \CFA name, so it can be correctly formed.
 …
 The program is linked with the debugging version of the runtime system.
 The debug version performs runtime checks to aid the debugging phase of a \CFA program, but can substantially slow program execution.
 The runtime checks should only be removed after the program is completely debugged.
+The runtime checks should only be removed after a program is completely debugged.
 \textbf{This option is the default.}
 …
 cfa $test$.cfa -XCFA -P -XCFA parse -XCFA -n # show program parse without prelude
 \end{lstlisting}
+Alternatively, multiple flages can be specified separated with commas and \emph{without} spaces.
+\begin{lstlisting}[language=sh,{moredelim=**[is][\protect\color{red}]{®}{®}}]
+cfa $test$.cfa -XCFA®,®-Pparse®,®-n # show program parse without prelude
+\end{lstlisting}
 \begin{description}[topsep=5pt,itemsep=0pt,parsep=0pt]
 \item
 …
 double ®``®forall = 3.5;
 \end{cfa}
+Existing C programs with keyword clashes can be converted by enclosing keyword identifiers in backquotes, and eventually the identifier name can be changed to a non-keyword name.
+Existing C programs with keyword clashes can be converted by prefixing the keyword identifiers with double backquotes, and eventually the identifier name can be changed to a non-keyword name.
 \VRef[Figure]{f:HeaderFileInterposition} shows how clashes in existing C header-files \see{\VRef{s:StandardHeaders}} can be handled using preprocessor \newterm{interposition}: ©#include_next© and ©-I filename©.
 Several common C header-files with keyword clashes are fixed in the standard \CFA header-library, so there is a seamless programming-experience.
 …
 \subsection{\texorpdfstring{\LstKeywordStyle{if} / \LstKeywordStyle{while} Statement}{if / while Statement}}
 The ©if©/©while© expression allows declarations, similar to ©for© declaration expression.\footnote{
 Declarations in the ©do©-©while© condition are not useful because they appear after the loop body.}
+The \Indexc{if}/\Indexc{while} expression allows declarations, similar to \Indexc{for} declaration expression.\footnote{
+Declarations in the \Indexc{do}-©while© condition are not useful because they appear after the loop body.}
 \begin{cfa}
 if ( ®int x = f()® ) ... $\C{// x != 0}$
 …
 while ( ®struct S { int i; } x = { f() }; x.i < 4® ) ... $\C{// relational expression}$
 \end{cfa}
 Unless a relational expression is specified, each variable is compared not equal to 0, which is the standard semantics for the ©if©/©while© expression, and the results are combined using the logical ©&&© operator.
 The scope of the declaration(s) is local to the ©if© statement but exist within both the \emph{then} and \emph{else} clauses.
+Unless a relational expression is specified, each variable is compared not equal to 0, which is the standard semantics for the ©if©/©while© expression, and the results are combined using the logical \Indexc{&&} operator.
+The scope of the declaration(s) is local to the ©if©/©while© statement, \ie in both \emph{then} and \emph{else} clauses for ©if©, and loop body for ©while©.
 \CC only provides a single declaration always compared ©!=© to 0.
 …
 \label{s:caseClause}
 C restricts the ©case© clause of a ©switch© statement to a single value.
+C restricts the \Indexc{case} clause of a \Indexc{switch} statement to a single value.
 For multiple ©case© clauses associated with the same statement, it is necessary to have multiple ©case© clauses rather than multiple values.
 Requiring a ©case© clause for each value does not seem to be in the spirit of brevity normally associated with C.
 Therefore, the ©case© clause is extended with a list of values, as in:
+Requiring a ©case© clause for each value is not in the spirit of brevity normally associated with C.
+Therefore, the ©case© clause is extended with a list of values.
 \begin{cquote}
 \begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
 …
 \subsection{\texorpdfstring{\LstKeywordStyle{switch} Statement}{switch Statement}}
 C allows a number of questionable forms for the ©switch© statement:
+C allows a number of questionable forms for the \Indexc{switch} statement:
 \begin{enumerate}
 \item
 By default, the end of a ©case© clause\footnote{
+By default, the end of a \Indexc{case} clause\footnote{
 In this section, the term \emph{case clause} refers to either a ©case© or ©default© clause.}
 \emph{falls through} to the next ©case© clause in the ©switch© statement;
 to exit a ©switch© statement from a ©case© clause requires explicitly terminating the clause with a transfer statement, most commonly ©break©:
+to exit a ©switch© statement from a ©case© clause requires explicitly terminating the clause with a transfer statement, most commonly \Indexc{break}:
 \begin{cfa}
 switch ( i ) {
   case 1:
         ...
         // fall-through
+        $\R{\LstCommentStyle{// fall-through}}$
   case 2:
         ...
         break;  // exit switch statement
+        ®break;®        // exit switch statement
+}
 \end{cfa}
 …
+}
 \end{cfa}
 This situation better handled without fall-through by allowing a list of case values \see{\VRef{s:caseClause}}.
+This situation is better handled by a list of case values \see{\VRef{s:caseClause}}.
 While fall-through itself is not a problem, the problem occurs when fall-through is the default, as this semantics is unintuitive to many programmers and is different from most programming languages with a ©switch© statement.
 Hence, default fall-through semantics results in a large number of programming errors as programmers often \emph{forget} the ©break© statement at the end of a ©case© clause, resulting in inadvertent fall-through.
 …
                 ...
         } // if
-  case 2:
-        while ( j < 5 ) {
-                ...
-          ®case 3:®             // transfer into "while" statement
-                ...
-        } // while
-} // switch
 \end{cfa}
 This usage branches into control structures, which is known to cause both comprehension and technical difficulties.
 …
 The technical problem results from the inability to ensure declaration and initialization of variables when blocks are not entered at the beginning.
 There are few arguments for this kind of control flow, and therefore, there is a strong impetus to eliminate it.
+Nevertheless, C does have an idiom where this capability is used, known as ``\Index*{Duff's device}''~\cite{Duff83}:
+This C idiom is known as ``\Index*{Duff's device}''~\cite{Duff83}, from this example:
 \begin{cfa}
 register int n = (count + 7) / 8;
 …
 still works.
 Nevertheless, reversing the default action would have a non-trivial effect on case actions that compound, such as the above example of processing shell arguments.
 Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called ©choose©, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword ©fallthrough©/©fallthru©, \eg:
+Therefore, to preserve backwards compatibility, it is necessary to introduce a new kind of ©switch© statement, called \Indexc{choose}, with no implicit fall-through semantics and an explicit fall-through if the last statement of a case-clause ends with the new keyword \Indexc{fallthrough}/\Indexc{fallthru}, \eg:
 \begin{cfa}
 ®choose® ( i ) {
 …
 Therefore, no change is made for this issue.
 \item
 Dealing with unreachable code in a ©switch©/©choose© body is solved by restricting declarations and associated initialization to the start of statement body, which is executed \emph{before} the transfer to the appropriate ©case© clause\footnote{
+Dealing with unreachable code in a ©switch©/©choose© body is solved by restricting declarations and initialization to the start of statement body, which is executed \emph{before} the transfer to the appropriate ©case© clause\footnote{
 Essentially, these declarations are hoisted before the ©switch©/©choose© statement and both declarations and statement are surrounded by a compound statement.} and precluding statements before the first ©case© clause.
 Further declarations at the same nesting level as the statement body are disallowed to ensure every transfer into the body is sound.
 …
 \subsection{Non-terminating and Labelled \texorpdfstring{\LstKeywordStyle{fallthrough}}{Non-terminating and Labelled fallthrough}}
 The ©fallthrough© clause may be non-terminating within a ©case© clause or have a target label to common code from multiple case clauses.
+The \Indexc{fallthrough} clause may be non-terminating within a \Indexc{case} clause or have a target label to common code from multiple case clauses.
 \begin{center}
 \begin{tabular}{@{}lll@{}}
 …
 \end{tabular}
 \end{center}
 The target label must be below the ©fallthrough© and may not be nested in a control structure, and
 the target label must be at the same or higher level as the containing ©case© clause and located at
 the same level as a ©case© clause; the target label may be case ©default©, but only associated
 with the current ©switch©/©choose© statement.
+The target label must be below the \Indexc{fallthrough} and may not be nested in a control structure, and
+the target label must be at the same or higher level as the containing \Indexc{case} clause and located at
+the same level as a ©case© clause; the target label may be case \Indexc{default}, but only associated
+with the current \Indexc{switch}/\Indexc{choose} statement.
 \begin{figure}
 …
 Looping a fixed number of times, possibly with a loop index, occurs frequently.
 \CFA condenses simply looping to facilitate coding speed and safety.
 The ©for©/©while©/©do-while© loop-control is augmented as follows \see{examples in \VRef[Figure]{f:LoopControlExamples}}:
+The \Indexc{for}, \Indexc{while}, and \Indexc{do} loop-control is augmented as follows \see{examples in \VRef[Figure]{f:LoopControlExamples}}:
 \begin{itemize}[itemsep=0pt]
 \item
 …
 \subsection{\texorpdfstring{Labelled \LstKeywordStyle{continue} / \LstKeywordStyle{break} Statement}{Labelled continue / break Statement}}
 C ©continue© and ©break© statements, for altering control flow, are restricted to one level of nesting for a particular control structure.
+C \Indexc{continue} and \Indexc{break} statements, for altering control flow, are restricted to one level of nesting for a particular control structure.
 This restriction forces programmers to use \Indexc{goto} to achieve the equivalent control-flow for more than one level of nesting.
 To prevent having to switch to the ©goto©, \CFA extends the \Indexc{continue}\index{continue@©continue©!labelled}\index{labelled!continue@©continue©} and \Indexc{break}\index{break@©break©!labelled}\index{labelled!break@©break©} with a target label to support static multi-level exit\index{multi-level exit}\index{static multi-level exit}~\cite{Buhr85}, as in Java.
 For both ©continue© and ©break©, the target label must be directly associated with a ©for©, ©while© or ©do© statement;
 for ©break©, the target label can also be associated with a ©switch©, ©if© or compound (©{}©) statement.
+For both ©continue© and ©break©, the target label must be directly associated with a \Indexc{for}, \Indexc{while} or \Indexc{do} statement;
+for ©break©, the target label can also be associated with a \Indexc{switch}, \Indexc{if} or compound (©{}©) statement.
 \VRef[Figure]{f:MultiLevelExit} shows a comparison between labelled ©continue© and ©break© and the corresponding C equivalent using ©goto© and labels.
 The innermost loop has 8 exit points, which cause continuation or termination of one or more of the 7 \Index{nested control-structure}s.
 …
 \end{figure}
 Both labelled ©continue© and ©break© are a ©goto©\index{goto@©goto©!restricted} restricted in the following ways:
+Both labelled \Indexc{continue} and \Indexc{break} are a \Indexc{goto}\index{goto@©goto©!restricted} restricted in the following ways:
 \begin{itemize}
 \item
 …
+\subsection{\texorpdfstring{Extended \LstKeywordStyle{else}}{Extended else}}
+\label{s:ExtendedElse}
+\index{extended ©else©}
+The ©if© statement has an optional ©else© clause executed if the conditional is false.
+This concept is extended to the \Indexc{while}, \Indexc{for}, and \Indexc{do} looping constructs (like Python).
+Hence, if the loop conditional becomes false, looping stops and the corresponding ©else© clause is executed, if present.
+The following example is a linear search for the key 3 in an array, where finding the key is handled with a ©break© and not finding with the ©else© clause on the loop construct.
+\begin{cquote}
+\begin{cfa}
+int a[10];
+\end{cfa}
+\begin{tabular}{@{}lll@{}}
+\begin{cfa}
+while ( int i = 0; i < 10 ) {
+  if ( a[i] == 3 ) break; // found
+        i += 1;
+} ®else® { // i == 10
+        sout | "not found";
+}
+\end{cfa}
+&
+\begin{cfa}
+for ( i; 10 ) {
+  if ( a[i] == 3 ) break; // found
+} ®else® { // i == 10
+        sout | "not found";
+}
+\end{cfa}
+&
+\begin{cfa}
+int i = 0;
+do {
+  if ( a[i] == 3 ) break; // found
+        i += 1;
+} while( i < 10 ) ®else® { // i == 10
+        sout | "not found";
+}
+\end{cfa}
+\end{tabular}
+\end{cquote}
+Note, \Index{dangling else} now occurs with \Indexc{if}, \Indexc{while}, \Indexc{for}, \Indexc{do}, and \Indexc{waitfor}.
 %\subsection{\texorpdfstring{\protect\lstinline{with} Statement}{with Statement}}
 \subsection{\texorpdfstring{\LstKeywordStyle{with} Statement}{with Statement}}
 …
 Therefore, reducing aggregate qualification is a useful language design goal.
 C allows unnamed nested aggregates that open their scope into the containing aggregate.
+C partially addresses the problem by eliminating qualification for enumerated types and unnamed \emph{nested} aggregates, which open their scope into the containing aggregate.
 This feature is used to group fields for attributes and/or with ©union© aggregates.
 \begin{cfa}
 struct S {
         struct { int g,  h; } __attribute__(( aligned(64) ));
+        struct $\R{\LstCommentStyle{/* unnamed */}}$ { int g,  h; } __attribute__(( aligned(64) ));
         int tag;
         union {
+        union $\R{\LstCommentStyle{/* unnamed */}}$ {
                 struct { char c1,  c2; } __attribute__(( aligned(128) ));
                 struct { int i1,  i2; };
                 struct { double d1,  d2; };
         };
+};
+s.g; s.h; s.tag; s.c1; s.c2; s.i1; s.i2; s.d1; s.d2;
+} s;
+enum { R, G, B };
+s.g; s.h;   s.tag = R;   s.c1; s.c2;   s.i1 = G; s.i2 = B;   s.d1; s.d2;
 \end{cfa}
 …
 \end{cfa}
 where qualification is only necessary to disambiguate the shadowed variable ©i©.
+In detail, the ©with© statement may appear as the body of a function or nested within a function body.
+In detail, the ©with© statement may form a function body or be nested within a function body.
 The ©with© clause takes a list of expressions, where each expression provides an aggregate type and object.
 (Enumerations are already opened.)
 …
 \end{cfa}
 The expression object is the implicit qualifier for the open structure-fields.
 \CFA's ability to overload variables \see{\VRef{s:VariableOverload}} and use the left-side of assignment in type resolution means most fields with the same name but different types are automatically disambiguated, eliminating qualification.
 All expressions in the expression list are open in parallel within the compound statement.
 …
 \end{cfa}
 A cast or qualification can be used to disambiguate variables within a ©with© \emph{statement}.
 A cast can be used to disambiguate among overload variables in a ©with© \emph{expression}:
+A cast can also be used to disambiguate among overload variables in a ©with© \emph{expression}:
 \begin{cfa}
 with ( w ) { ... }                                                      $\C{// ambiguous, same name and no context}$
 …
 Finally, there is an interesting problem between parameters and the function-body ©with©, \eg:
 \begin{cfa}
+void ?{}( S & s, int i ) with ( s ) { $\C{// constructor}$
+        ®s.i = i;®  j = 3;  m = 5.5; $\C{// initialize fields}$
+}
+\end{cfa}
+Here, the assignment ©s.i = i© means ©s.i = s.i©, which is meaningless, and there is no mechanism to qualify the parameter ©i©, making the assignment impossible using the function-body ©with©.
+To solve this problem, parameters are treated like an initialized aggregate:
+\begin{cfa}
+struct Params {
+        S & s;
+        int i;
+void f( S & s, char c ) with ( s ) {
+        ®s.c = c;®  i = 3;  d = 5.5;                    $\C{// initialize fields}$
+}
+\end{cfa}
+Here, the assignment ©s.c = c© means ©s.c = s.c©, which is meaningless, and there is no mechanism to qualify the parameter ©c©, making the assignment impossible using the function-body ©with©.
+To solve this problem, parameters \emph{not} explicitly opened are treated like an initialized aggregate:
+\begin{cfa}
+struct Params {                                                         $\C{// s explicitly opened so S \& s elided}$
+        char c;
 } params;
 \end{cfa}
 and implicitly opened \emph{after} a function-body open, to give them higher priority:
 \begin{cfa}
 void ?{}( S & s, int ®i® ) with ( s ) ®with( $\emph{\R{params}}$ )® { // syntax not allowed, illustration only
         s.i = ®i®; j = 3; m = 5.5;
+void f( S & s, char ®c® ) with ( s ) ®with( $\emph{\R{params}}$ )® { // syntax not allowed, illustration only
+        s.c = ®c;®  i = 3;  d = 5.5;
+}
 \end{cfa}
 This implicit semantic matches with programmer expectation.
 …
 This requirement is the same as for comma expressions in argument lists.
 Type qualifiers, \ie const and volatile, may modify a tuple type.
 The meaning is the same as for a type qualifier modifying an aggregate type [Int99, x 6.5.2.3(7),x 6.7.3(11)], \ie the qualifier is distributed across all of the types in the tuple, \eg:
+Type qualifiers, \ie ©const© and ©volatile©, may modify a tuple type.
+The meaning is to distribute the qualifier across all of the types in the tuple, \eg:
 \begin{cfa}
 const volatile [ int, float, const int ] x;
 …
 Stream ©exit© implicitly returns ©EXIT_FAILURE© to the shell.
 \begin{cfa}
 ®exit®   | "x (" | x | ") negative value."; // terminate and return EXIT_FAILURE to shell
 ®abort® | "x (" | x | ") negative value."; // terminate and generate stack trace and core file
+®exit®   | "x (" | x | ") negative value.";   // terminate and return EXIT_FAILURE to shell
+®abort® | "x (" | x | ") negative value.";   // terminate and generate stack trace and core file
 \end{cfa}
 Note, \CFA stream variables ©stdin©, ©stdout©, ©stderr©, ©exit©, and ©abort© overload C variables ©stdin©, ©stdout©, ©stderr©, and functions ©exit© and ©abort©, respectively.
 …
         sout | '1' | '2' | '3';
         sout | 1 | "" | 2 | "" | 3;
         sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x ¥"
                 | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10;
+        sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x Â£" | 6 | "x Â¥"
+                | 7 | "x Â¡" | 8 | "x Â¿" | 9 | "x Â«" | 10;
         sout | 1 | ", x" | 2 | ". x" | 3 | "; x" | 4 | "! x" | 5 | "? x" | 6 | "% x"
                 | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x";
+                | 7 | "Â¢ x" | 8 | "Â» x" | 9 | ") x" | 10 | "] x" | 11 | "} x";
         sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx";
         sout | "x ( " | 1 | " ) x" | 2 | " , x" | 3 | " :x: " | 4;
 …
 The common usage is the short form of the mutex statement\index{ostream@©ostream©!mutex@©mutex©} to lock a stream during a single cascaded I/O expression, \eg:
 \begin{cfa}
 $\emph{thread\(_1\)}$ : ®mutex()® sout | "abc " | "def ";
 $\emph{thread\(_2\)}$ : ®mutex()® sout | "uvw " | "xyz ";
+$\emph{thread\(_1\)}$ : ®mutex( sout )® sout | "abc " | "def ";
+$\emph{thread\(_2\)}$ : ®mutex( sout )® sout | "uvw " | "xyz ";
 \end{cfa}
 Now, the order of the thread execution is still non-deterministic, but the output is constrained to two possible lines in either order.
 …
 ®mutex( sout )® {
         sout | 1;
         ®mutex() sout® | 2 | 3;                         $\C{// unnecessary, but ok because of recursive lock}$
+        ®mutex( sout ) sout® | 2 | 3;                           $\C{// unnecessary, but ok because of recursive lock}$
         sout | 4;
 } // implicitly release sout lock
 …
         int x, y, z, w;
         sin | x;
         ®mutex() sin® | y | z;                          $\C{// unnecessary, but ok because of recursive lock}$
+        ®mutex( sin )® sin | y | z;                                     $\C{// unnecessary, but ok because of recursive lock}$
         sin | w;
 } // implicitly release sin lock
 …
 \Textbf{WARNING:} The general problem of \Index{nested locking} can occur if routines are called in an I/O sequence that block, \eg:
 \begin{cfa}
 ®mutex() sout® | "data:" | rtn( mon );  $\C{// mutex call on monitor}$
+®mutex( sout )® sout | "data:" | rtn( mon );    $\C{// mutex call on monitor}$
 \end{cfa}
 If the thread executing the I/O expression blocks in the monitor with the ©sout© lock, other threads writing to ©sout© also block until the thread holding the lock is unblocked and releases it.
 …
 \begin{cfa}
 int ®data® = rtn( mon );
+mutex() sout | "data:" | ®data®;
+\end{cfa}
+mutex( sout ) sout | "data:" | ®data®;
+\end{cfa}
+\subsection{Locale}
+\index{stream!locale}
+\index{locale!stream}
+Cultures use different syntax, called a \newterm{locale}, for printing numbers so they are easier to read, \eg:
+\begin{cfa}
+®,®345®.®123          $\C[1.25in]{// comma separator, period decimal-point}$
+®.®345®,®123          $\C{// period separator, comma decimal-point}$
+$\Sp$345®,®123®.®     $\C{// space separator, comma decimal-point, period terminator}\CRT$
+\end{cfa}
+A locale is selected with function ©setlocale©, and the corresponding locale package \emph{must} be installed on the underlying system;
+©setlocale© returns ©0p© if the requested locale is unavailable.
+Furthermore, a locale covers the syntax for many cultural items, \eg address, measurement, money, etc.
+This discussion applies to item ©LC_NUMERIC© for formatting non-monetary integral and floating-point values.
+\VRef[Figure]{f:StreamLocale} shows selecting different cultural syntax, which may be associated with one or more countries.
+\begin{figure}
+\begin{cfa}
+#include <fstream.hfa>
+#include <locale.h>                                                     $\C{// setlocale}$
+#include <stdlib.h>                                                     $\C{// getenv}$
+int main() {
+        void print() {
+                sout | 12 | 123 | 1234 | 12345 | 123456 | 1234567;
+                sout | 12. | 123.1 | 1234.12 | 12345.123 | 123456.1234 | 1234567.12345;
+                sout | nl;
+        }
+        sout | "Default locale off";
+        print();
+        sout | "Locale on" | ®setlocale( LC_NUMERIC, getenv( "LANG" ) )®;  // enable local locale
+        print();
+        sout | "German" | ®setlocale( LC_NUMERIC, "de_DE.UTF-8" )®;  // enable German locale
+        print();
+        sout | "Ukraine" | ®setlocale( LC_NUMERIC, "uk_UA.utf8" )®;  // enable Ukraine locale
+        print();
+        sout | "Default locale off" | ®setlocale( LC_NUMERIC, "C" )®;  // disable locale
+        print();
+}
+Default locale off
+123 1234 12345 123456 1234567
+. 123.1 1234.12 12345.123 123456.1234 1234567.12345
+Locale on en_US.UTF-8
+123 1®,®234 12®,®345 123®,®456 1®,®234®,®567
+®.® 123®.®1 1®,®234®.®12 12®,®345®.®123 123®,®456®.®1234 1®,®234®,®567®.®12345
+German de_DE.UTF-8
+123 1®.®234 12®.®345 123®.®456 1®.®234®.®567
+®.® 123®,®1®.® 1®.®234®,®12 12®.®345®,®123 123®.®456®,®1234 1®.®234®.®567®,®12345
+Ukraine uk_UA.utf8
+123 1 234 12 345 123 456 1 234 567
+®.® 123®,®1®.® 1$\Sp$234®,®12®.® 12$\Sp$ 345®,®123®.® 123$\Sp$ 456®,®1234®.® 1$\Sp$ 234$\Sp$567®,®12345®.®
+Default locale off C
+123 1234 12345 123456 1234567
+. 123.1 1234.12 12345.123 123456.1234 1234567.12345
+\end{cfa}
+\caption{Stream Locale}
+\label{f:StreamLocale}
+\end{figure}
 …
 \end{figure}
 \begin{comment}
 \section{Types}
 …
 \subsection{Structures}
+\section{Structures}
 Structures in \CFA are basically the same as structures in C.
 …
 \subsection{Coroutine}
 \Index{Coroutines} are the precursor to tasks.
+\Index{Coroutines} are the precursor to threads.
 \VRef[Figure]{f:FibonacciCoroutine} shows a coroutine that computes the \Index*{Fibonacci} numbers.
 …
 \subsection{Tasks}
+\subsection{Threads}
 \CFA also provides a simple mechanism for creating and utilizing user level threads.
 A task provides mutual exclusion like a monitor, and also has its own execution state and a thread of control.
 Similar to a monitor, a task is defined like a structure:
+A thread provides mutual exclusion like a monitor, and also has its own execution state and a thread of control.
+Similar to a monitor, a thread is defined like a structure:
 \begin{figure}
 …
+}
 \end{cfa}
 \caption{Simple Tasks}
 \label{f:SimpleTasks}
+\caption{Simple Threads}
+\label{f:SimpleThreads}
 \end{figure}
 …
 In \CFA, there are ambiguous cases with dereference and operator identifiers, \eg ©int *?*?()©, where the string ©*?*?© can be interpreted as:
 \begin{cfa}
 *?$\R{\textvisiblespace}$*? $\C{// dereference operator, dereference operator}$
 *$\R{\textvisiblespace}$?*? $\C{// dereference, multiplication operator}$
+*?$\Sp$*? $\C{// dereference operator, dereference operator}$
+*$\Sp$?*? $\C{// dereference, multiplication operator}$
 \end{cfa}
 By default, the first interpretation is selected, which does not yield a meaningful parse.
 …
 Therefore, it is necessary to disambiguate these cases with a space:
 \begin{cfa}
 i++$\R{\textvisiblespace}$? i : 0;
 i?$\R{\textvisiblespace}$++i : 0;
+i++$\Sp$? i : 0;
+i?$\Sp$++i : 0;
 \end{cfa}
 …
 char random( void );$\indexc{random}$
 char random( char u ); $\C{// [0,u)}$
 char random( char l, char u ); $\C{// [l,u)}$
+char random( char l, char u ); $\C{// [l,u]}$
 int random( void );
 int random( int u ); $\C{// [0,u)}$
 int random( int l, int u ); $\C{// [l,u)}$
+int random( int l, int u ); $\C{// [l,u]}$
 unsigned int random( void );
 unsigned int random( unsigned int u ); $\C{// [0,u)}$
 unsigned int random( unsigned int l, unsigned int u ); $\C{// [l,u)}$
+unsigned int random( unsigned int l, unsigned int u ); $\C{// [l,u]}$
 long int random( void );
 long int random( long int u ); $\C{// [0,u)}$
 long int random( long int l, long int u ); $\C{// [l,u)}$
+long int random( long int l, long int u ); $\C{// [l,u]}$
 unsigned long int random( void );
 unsigned long int random( unsigned long int u ); $\C{// [0,u)}$
 unsigned long int random( unsigned long int l, unsigned long int u ); $\C{// [l,u)}$
+unsigned long int random( unsigned long int l, unsigned long int u ); $\C{// [l,u]}$
 float random( void );                                            $\C{// [0.0, 1.0)}$
 double random( void );                                           $\C{// [0.0, 1.0)}$
 …
+\section{Pseudo Random Number Generator}
+\label{s:PRNG}
+Random numbers are values generated independently, i.e., new values do not depend on previous values (independent trials), \eg lottery numbers, shuffled cards, dice roll, coin flip.
+While a primary goal of programming is computing values that are \emph{not} random, random values are useful in simulation, cryptography, games, etc.
+A random-number generator is an algorithm that computes independent values.
+If the algorithm uses deterministic computation (a predictable sequence of values), it generates \emph{pseudo} random numbers versus \emph{true} random numbers.
+All \newterm{pseudo random-number generators} (\newterm{PRNG}) involve some technique to scramble bits of a value, \eg multiplicative recurrence:
+\begin{cfa}
+rand = 36973 * (rand & 65535) + (rand >> 16); // scramble bits
+\end{cfa}
+Multiplication of large values adds new least-significant bits and drops most-significant bits.
+\begin{quote}
+\begin{tabular}{@{}r|l@{}}
+bits 63--32 (most)      & bits 31--0 (least)    \\
+\hline
+x0                                     & 0x3e8e36                              \\
+x5f                            & 0x718c25e1                    \\
+xad3e                          & 0x7b5f1dbe                    \\
+xbc3b                          & 0xac69ff19                    \\
+x1070f                         & 0x2d258dc6                    \\
+\end{tabular}
+\end{quote}
+By dropping bits 63--32, bits 31--0 become scrambled after each multiply.
+The least-significant bits \emph{appear} random but the same bits are always generated given a fixed starting value, called the \newterm{seed} (value 0x3e8e36 above).
+Hence, if a program uses the same seed, the same sequence of pseudo-random values is generated from the PRNG.
+Often the seed is set to another random value like a program's process identifier (©getpid©\index{getpid@©getpid©}) or time when the program is run;
+hence, one random value bootstraps another.
+Finally, a PRNG usually generates a range of large values, \eg ©[0, UINT_MAX]©, which are scaled using the modulus operator, \eg ©prng() % 5© produces random values in the range 0--4.
+\CFA provides a sequential PRNG type only accessible by a single thread (not thread-safe) and a set of global and companion thread PRNG functions accessible by multiple threads without contention.
+\begin{itemize}
+\item
+The ©PRNG© type is for sequential programs, like coroutining:
+\begin{cfa}
+struct PRNG { ... }; $\C[3.75in]{// opaque type}$
+void ?{}( PRNG & prng ); $\C{// random seed}$
+void ?{}( PRNG & prng, uint32_t seed ); $\C{// fixed seed}$
+void set_seed( PRNG & prng, uint32_t seed ); $\C{// set seed}$
+uint32_t get_seed( PRNG & prng ); $\C{// get seed}$
+uint32_t prng( PRNG & prng ); $\C{// [0,UINT\_MAX]}$
+uint32_t prng( PRNG & prng, uint32_t u ); $\C{// [0,u)}$
+uint32_t prng( PRNG & prng, uint32_t l, uint32_t u ); $\C{// [l,u]}$
+uint32_t calls( PRNG & prng ); $\C{// number of calls}\CRT$
+\end{cfa}
+A ©PRNG© object is used to randomize behaviour or values during execution, \eg in games, a character makes a random move or an object takes on a random value.
+In this scenario, it is useful to have multiple ©PRNG© objects, \eg one per player or object.
+However, sequential execution is still repeatable given the same starting seeds for all ©PRNG©s.
+\VRef[Figure]{f:SequentialPRNG} shows an example that creates two sequential ©PRNG©s, sets both to the same seed (1009), and illustrates the three forms for generating random values, where both ©PRNG©s generate the same sequence of values.
+\begin{figure}
+\begin{cfa}
+PRNG prng1, prng2;
+®set_seed( prng1, 1009 )®;   ®set_seed( prng2, 1009 )®;
+for ( 10 ) {
+        // Do not cascade prng calls because side-effect functions called in arbitrary order.
+        sout | nlOff | ®prng( prng1 )®;  sout | ®prng( prng1, 5 )®;  sout | ®prng( prng1, 0, 5 )® | '\t';
+        sout | ®prng( prng2 )®;  sout | ®prng( prng2, 5 )®;  sout | ®prng( prng2, 0, 5 )® | nlOn;
+}
+\end{cfa}
+\begin{cquote}
+\begin{tabular}{@{}ll@{}}
+\begin{cfa}
+37301721 2 2
+1681308562 1 3
+290112364 3 2
+1852700364 4 3
+733221210 1 3
+1775396023 2 3
+123981445 2 3
+2062557687 2 0
+283934808 1 0
+672325890 1 3
+\end{cfa}
+&
+\begin{cfa}
+37301721 2 2
+1681308562 1 3
+290112364 3 2
+1852700364 4 3
+733221210 1 3
+1775396023 2 3
+123981445 2 3
+2062557687 2 0
+283934808 1 0
+672325890 1 3
+\end{cfa}
+\end{tabular}
+\end{cquote}
+\caption{Sequential PRNG}
+\label{f:SequentialPRNG}
+\end{figure}
+\item
+The PRNG global and companion thread functions are for concurrent programming, such as randomizing execution in short-running programs, \eg ©yield( prng() % 5 )©.
+\begin{cfa}
+void set_seed( uint32_t seed ); $\C[3.75in]{// set global seed}$
+uint32_t get_seed(); $\C{// get global seed}$
+// SLOWER
+uint32_t prng(); $\C{// [0,UINT\_MAX]}$
+uint32_t prng( uint32_t u ); $\C{// [0,u)}$
+uint32_t prng( uint32_t l, uint32_t u ); $\C{// [l,u]}$
+// FASTER
+uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th );     $\C{// [0,UINT\_MAX]}$
+uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th, uint32_t u ); $\C{// [0,u)}$
+uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th, uint32_t l, uint32_t u );     $\C{// [l,u]}\CRT$
+\end{cfa}
+The only difference between the two sets of ©prng© routines is performance.
+Because concurrent execution is non-deterministic, seeding the concurrent PRNG is less important, as repeatable execution is impossible.
+Hence, there is one system-wide PRNG (global seed) but each \CFA thread has its own non-contended PRNG state.
+If the global seed is set, threads start with this seed, until it is reset and then threads start with the reset seed.
+Hence, these threads generate the same sequence of random numbers from their specific starting seed.
+If the global seed is \emph{not} set, threads start with a random seed, until the global seed is set.
+Hence, these threads generate different sequences of random numbers.
+If each thread needs its own seed, use a sequential ©PRNG© in each thread.
+The slower ©prng© functions \emph{without} a thread argument call ©active_thread© internally to indirectly access the current thread's PRNG state, while the faster ©prng© functions \emph{with} a thread argument directly access the thread through the thread parameter.
+If a thread pointer is available, \eg in thread main, eliminating the call to ©active_thread© significantly reduces the cost of accessing the thread's PRNG state.
+\VRef[Figure]{f:ConcurrentPRNG} shows an example using the slower/faster concurrent PRNG in the program main and a thread.
+\begin{figure}
+\begin{cfa}
+thread T {};
+void main( ®T & th® ) {  // thread address
+        for ( i; 10 ) {
+                sout | nlOff | ®prng()®;  sout | ®prng( 5 )®;  sout | ®prng( 0, 5 )® | '\t';  // SLOWER
+                sout | nlOff | ®prng( th )®;  sout | ®prng( th, 5 )®;  sout | ®prng( th, 0, 5 )® | nlOn;  // FASTER
+        }
+}
+int main() {
+        set_seed( 1009 );
+        $\R{thread\LstStringStyle{\textdollar}}$ ®& th = *active_thread()®;  // program-main thread-address
+        for ( i; 10 ) {
+                sout | nlOff | ®prng()®; sout | ®prng( 5 )®; sout | ®prng( 0, 5 )® | '\t';  // SLOWER
+                sout | nlOff | ®prng( th )®; sout | ®prng( th, 5 )®; sout | ®prng( th, 0, 5 )® | nlOn;  // FASTER
+        }
+        sout | nl;
+        T t; // run thread
+}
+\end{cfa}
+\begin{cquote}
+\begin{tabular}{@{}ll@{}}
+\begin{cfa}
+37301721 2 2
+290112364 3 2
+733221210 1 3
+123981445 2 3
+283934808 1 0
+1414344101 1 3
+871831898 3 4
+2142057611 4 4
+802117363 0 4
+2346353643 1 3
+\end{cfa}
+&
+\begin{cfa}
+1681308562 1 3
+1852700364 4 3
+1775396023 2 3
+2062557687 2 0
+672325890 1 3
+873424536 3 4
+866783532 0 1
+17310256 2 5
+492964499 0 0
+2143013105 3 2
+\end{cfa}
+\end{tabular}
+\begin{cfa}
+// same output as above from thread t
+\end{cfa}
+\end{cquote}
+\caption{Concurrent PRNG}
+\label{f:ConcurrentPRNG}
+\end{figure}
+\end{itemize}
 \section{Multi-precision Integers}
 \label{s:MultiPrecisionIntegers}
 …
 \end{tabular}
 \end{cquote}
+\small
 \begin{cfa}
 Factorial Numbers

driver/Makefile.am

rf5a51db	rcc7bbe6
19	19
20	20	# applies to both programs
21		AM_CXXFLAGS = @HOST_FLAGS@ -Wall -O2 -g -std=c++14 -I${abs_top_srcdir}/src -I${abs_top_srcdir}/src/include
	21	AM_CXXFLAGS = @HOST_FLAGS@ -Wall -Wextra -Werror=return-type -O2 -g -std=c++14 -I${abs_top_srcdir}/src -I${abs_top_srcdir}/src/include
22	22
23	23	# don't install cfa directly

driver/cc1.cc

-              rf5a51db
+              rcc7bbe6
 // Created On       : Fri Aug 26 14:23:51 2005
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Wed Jul 21 09:46:24 2021
 // Update Count     : 419
+// Last Modified On : Thu Feb 17 18:04:23 2022
+// Update Count     : 422
 //
 …
 static string __CFA_FLAGPREFIX__( "__CFA_FLAG" );               // "__CFA_FLAG__=" suffix
 static void checkEnv1( const char * args[], int & nargs ) { // stage 1
+static void checkEnv1() {                                                               // stage 1
         extern char ** environ;
 …
         cerr << "Stage1" << endl;
         #endif // __DEBUG_H__
         checkEnv1( args, nargs );                                                       // arguments passed via environment variables
+        checkEnv1();                                                                            // arguments passed via environment variables
         #ifdef __DEBUG_H__
         for ( int i = 1; i < argc; i += 1 ) {

libcfa/prelude/Makefile.am

rf5a51db	rcc7bbe6
26	26
27	27	CC = @LOCAL_CFACC@
28		AM_CFLAGS = -g -Wall -Wno-unused-function -fPIC @ARCH_FLAGS@ @CONFIG_CFLAGS@
	28	AM_CFLAGS = -g -Wall -Werror=return-type -Wno-unused-function -fPIC @ARCH_FLAGS@ @CONFIG_CFLAGS@
29	29	AM_CFAFLAGS = @CONFIG_CFAFLAGS@
30	30

libcfa/src/Makefile.am

-              rf5a51db
+              rcc7bbe6
 # The built sources must not depend on the installed inst_headers_src
 AM_CFAFLAGS = -quiet -cfalib -I$(srcdir)/stdhdr -I$(srcdir)/concurrency $(if $(findstring ${gdbwaittarget}, ${@}), -XCFA --gdb) @CONFIG_CFAFLAGS@
 AM_CFLAGS = -g -Wall -Wno-unused-function -fPIC -fexceptions -pthread @ARCH_FLAGS@ @CONFIG_CFLAGS@
 AM_CCASFLAGS = -g -Wall -Wno-unused-function @ARCH_FLAGS@ @CONFIG_CFLAGS@
+AM_CFLAGS = -g -Wall -Werror=return-type -Wno-unused-function -fPIC -fexceptions -pthread @ARCH_FLAGS@ @CONFIG_CFLAGS@
+AM_CCASFLAGS = -g -Wall -Werror=return-type -Wno-unused-function @ARCH_FLAGS@ @CONFIG_CFLAGS@
 CFACC = @CFACC@

libcfa/src/concurrency/io/setup.cfa

rf5a51db	rcc7bbe6
32	32
33	33	void __cfa_io_start( processor * proc ) {}
34		bool __cfa_io_flush( processor * proc, int ) {}
	34	bool __cfa_io_flush( processor * proc, int ) { return false; }
35	35	void __cfa_io_stop ( processor * proc ) {}
36	36

libcfa/src/concurrency/kernel.hfa

rf5a51db	rcc7bbe6
173	173
174	174	static inline void ?{}(__timestamp_t & this) { this.tv = 0; this.ma = 0; }
175		static inline void ^?{}(__timestamp_t & ~~this~~) {}
	175	static inline void ^?{}(__timestamp_t &) {}
176	176
177	177	struct __attribute__((aligned(128))) __ready_queue_caches_t;

libcfa/src/concurrency/kernel/startup.cfa

-              rf5a51db
+              rcc7bbe6
 // C Includes
 #include <errno.h>              // errno
+#include <errno.h>                                      // errno
 #include <signal.h>
 #include <string.h>             // strerror
 #include <unistd.h>             // sysconf
+#include <string.h>                                     // strerror
+#include <unistd.h>                                     // sysconf
 extern "C" {
       #include <limits.h>       // PTHREAD_STACK_MIN
         #include <unistd.h>       // syscall
         #include <sys/eventfd.h>  // eventfd
       #include <sys/mman.h>     // mprotect
       #include <sys/resource.h> // getrlimit
+        #include <limits.h>                             // PTHREAD_STACK_MIN
+        #include <unistd.h>                             // syscall
+        #include <sys/eventfd.h>                        // eventfd
+        #include <sys/mman.h>                           // mprotect
+        #include <sys/resource.h>                       // getrlimit
+}
 // CFA Includes
 #include "kernel_private.hfa"
 #include "startup.hfa"          // STARTUP_PRIORITY_XXX
+#include "startup.hfa"                                  // STARTUP_PRIORITY_XXX
 #include "limits.hfa"
 #include "math.hfa"
 …
 extern void __wake_proc(processor *);
 extern int cfa_main_returned;                                                   // from interpose.cfa
 extern uint32_t __global_random_seed;
+uint32_t __global_random_prime = 4_294_967_291u, __global_random_mask = false;
 //-----------------------------------------------------------------------------
 …
         preferred = ready_queue_new_preferred();
         last_proc = 0p;
         random_state = __global_random_seed;
+        random_state = __global_random_mask ? __global_random_prime : __global_random_prime ^ rdtscl();
         #if defined( __CFA_WITH_VERIFY__ )
                 canary = 0x0D15EA5E0D15EA5Ep;
 …
         check( pthread_attr_init( &attr ), "pthread_attr_init" ); // initialize attribute
         size_t stacksize = DEFAULT_STACK_SIZE;
+        size_t stacksize = max( PTHREAD_STACK_MIN, DEFAULT_STACK_SIZE );
         void * stack;

libcfa/src/concurrency/preemption.cfa

-              rf5a51db
+              rcc7bbe6
 // Created On       : Mon Jun 5 14:20:42 2017
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Fri Nov  6 07:42:13 2020
 // Update Count     : 54
+// Last Modified On : Thu Feb 17 11:18:57 2022
+// Update Count     : 59
 //
 …
 //----------
 // special case for preemption since used often
 bool __preemption_enabled() {
+__attribute__((optimize("no-reorder-blocks"))) bool __preemption_enabled() {
         // create a assembler label before
         // marked as clobber all to avoid movement

libcfa/src/concurrency/thread.cfa

-              rf5a51db
+              rcc7bbe6
 // Created On       : Tue Jan 17 12:27:26 2017
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Thu Jan 13 20:11:55 2022
 // Update Count     : 42
+// Last Modified On : Sat Feb 12 15:24:18 2022
+// Update Count     : 66
 //
 …
 #include "invoke.h"
 extern uint32_t __global_random_seed;
+extern uint32_t __global_random_seed, __global_random_prime, __global_random_mask;
 //-----------------------------------------------------------------------------
 …
         preferred = ready_queue_new_preferred();
         last_proc = 0p;
         random_state = __global_random_seed;
+        random_state = __global_random_mask ? __global_random_prime : __global_random_prime ^ rdtscl();
         #if defined( __CFA_WITH_VERIFY__ )
                 canary = 0x0D15EA5E0D15EA5Ep;
 …
 void set_seed( uint32_t seed ) {
+        active_thread()->random_state = __global_random_seed = seed;
+        GENERATOR( active_thread()->random_state );
+        uint32_t & state = active_thread()->random_state;
+        state = __global_random_seed = seed;
+        GENERATOR( state );
+        __global_random_prime = state;
+        __global_random_mask = true;
 } // set_seed
+uint32_t prng( void ) { return GENERATOR( active_thread()->random_state ); } // [0,UINT_MAX]
+uint32_t prng( void ) {                                                                 // [0,UINT_MAX]
+        uint32_t & state = active_thread()->random_state;
+        return GENERATOR( state );
+} // prng
 // Local Variables: //

libcfa/src/concurrency/thread.hfa

-              rf5a51db
+              rcc7bbe6
 // Created On       : Tue Jan 17 12:27:26 2017
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Thu Jan  6 16:40:16 2022
 // Update Count     : 7
+// Last Modified On : Fri Feb 11 16:34:07 2022
+// Update Count     : 20
 //
 …
 T & join( T & this );
+//----------
+// prng
+static inline {
+        uint32_t prng( thread$ & th ) __attribute__(( warn_unused_result )) { return LCG( th.random_state ); } // [0,UINT_MAX]
+        uint32_t prng( thread$ & th, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u)
+        uint32_t prng( thread$ & th, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u]
+        forall( T & | is_thread(T) ) {
+                uint32_t prng( T & th ) __attribute__(( warn_unused_result )) { return prng( (thread &)th ); } // [0,UINT_MAX]
+                uint32_t prng( T & th, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th ) % u; } // [0,u)
+                uint32_t prng( T & th, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( th, u - l + 1 ) + l; } // [l,u]
+        } // distribution
+} // distribution
 // Local Variables: //
 // mode: c //

libcfa/src/math.trait.hfa

-              rf5a51db
+              rcc7bbe6
 #pragma once
 trait Not( T ) {
         void ?{}( T &, zero_t );
         int !?( T );
+trait Not( U ) {
+        void ?{}( U &, zero_t );
+        int !?( U );
 }; // Not
 …
 }; // Equality
 trait Relational( T | Equality( T ) ) {
         int ?<?( T, T );
         int ?<=?( T, T );
         int ?>?( T, T );
         int ?>=?( T, T );
+trait Relational( U | Equality( U ) ) {
+        int ?<?( U, U );
+        int ?<=?( U, U );
+        int ?>?( U, U );
+        int ?>=?( U, U );
 }; // Relational
 …
 }; // Signed
 trait Additive( T | Signed( T ) ) {
         T ?+?( T, T );
         T ?-?( T, T );
         T ?+=?( T &, T );
         T ?-=?( T &, T );
+trait Additive( U | Signed( U ) ) {
+        U ?+?( U, U );
+        U ?-?( U, U );
+        U ?+=?( U &, U );
+        U ?-=?( U &, U );
 }; // Additive
 …
         void ?{}( T &, one_t );
         // T ?++( T & );
         // T ++?( T &);
+        // T ++?( T & );
         // T ?--( T & );
         // T --?( T & );
 }; // Incdec
 trait Multiplicative( T | Incdec( T ) ) {
         T ?*?( T, T );
         T ?/?( T, T );
         T ?%?( T, T );
         T ?/=?( T &, T );
+trait Multiplicative( U | Incdec( U ) ) {
+        U ?*?( U, U );
+        U ?/?( U, U );
+        U ?%?( U, U );
+        U ?/=?( U &, U );
 }; // Multiplicative

libcfa/src/stdlib.cfa

-              rf5a51db
+              rcc7bbe6
 // Created On       : Thu Jan 28 17:10:29 2016
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Thu Jan 13 21:38:30 2022
 // Update Count     : 593
+// Last Modified On : Thu Feb 10 22:41:39 2022
+// Update Count     : 602
 //
 …
 uint32_t __global_random_seed;                                                  // sequential/concurrent
 uint32_t __global_random_state;                                         // sequential only
+uint32_t __global_random_state;                                                 // sequential only
 void set_seed( PRNG & prng, uint32_t seed_ ) with( prng ) { state = seed = seed_; GENERATOR( state ); } // set seed
+uint32_t prng( PRNG & prng ) with( prng ) { callcnt += 1; return GENERATOR( state ); }
+void set_seed( uint32_t seed ) { __global_random_seed = seed; GENERATOR( __global_random_state ); }
+void set_seed( uint32_t seed ) { __global_random_state = __global_random_seed = seed; GENERATOR( __global_random_state ); }
 uint32_t get_seed() { return __global_random_seed; }
 uint32_t prng( void ) { return GENERATOR( __global_random_state ); } // [0,UINT_MAX]

libcfa/src/stdlib.hfa

-              rf5a51db
+              rcc7bbe6
 // Created On       : Thu Jan 28 17:12:35 2016
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Thu Jan 13 21:34:46 2022
 // Update Count     : 636
+// Last Modified On : Sat Feb 12 17:22:25 2022
+// Update Count     : 643
 //
 …
 #include "bits/defs.hfa"                                                                // OPTIONAL_THREAD
 #include "bits/align.hfa"                                                               // libAlign
+#include "bits/random.hfa"                                                              // prng
 #include <stdlib.h>                                                                             // *alloc, strto*, ato*
 …
         forall( TT... | { T * alloc_internal$( void *, T *, size_t, size_t, S_fill(T), TT ); } ) {
                 T * alloc_internal$( void *       , T * Realloc, size_t Align, size_t Dim, S_fill(T) Fill, T_resize Resize, TT rest) {
+                T * alloc_internal$( void *       , T *        , size_t Align, size_t Dim, S_fill(T) Fill, T_resize Resize, TT rest) {
                 return alloc_internal$( Resize, (T*)0p, Align, Dim, Fill, rest);
+                }
                 T * alloc_internal$( void * Resize, T *        , size_t Align, size_t Dim, S_fill(T) Fill, S_realloc(T) Realloc, TT rest) {
+                T * alloc_internal$( void *        , T *        , size_t Align, size_t Dim, S_fill(T) Fill, S_realloc(T) Realloc, TT rest) {
                 return alloc_internal$( (void*)0p, Realloc, Align, Dim, Fill, rest);
+                }
 …
 // Declaration :
 //   PRNG sprng = { 1009 } - set starting seed versus random seed
 //
+//
 // Interface :
 //   set_seed( sprng, 1009 ) - set starting seed for ALL kernel threads versus random seed
 …
 void set_seed( PRNG & prng, uint32_t seed_ );
-uint32_t prng( PRNG & prng ) __attribute__(( warn_unused_result )); // [0,UINT_MAX]
 static inline {
         void ?{}( PRNG & prng ) { set_seed( prng, rdtscl() ); } // random seed
         void ?{}( PRNG & prng, uint32_t seed ) { set_seed( prng, seed ); } // fixed seed
+        void ?{}( PRNG & prng ) with( prng ) { callcnt = 0; set_seed( prng, rdtscl() ); } // random seed
+        void ?{}( PRNG & prng, uint32_t seed ) with( prng ) { callcnt = 0; set_seed( prng, seed ); } // fixed seed
         uint32_t get_seed( PRNG & prng ) __attribute__(( warn_unused_result )) with( prng ) { return seed; } // get seed
+        uint32_t prng( PRNG & prng ) __attribute__(( warn_unused_result )) with( prng ) { callcnt += 1; return LCG( state ); } // [0,UINT_MAX]
         uint32_t prng( PRNG & prng, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( prng ) % u; } // [0,u)
         uint32_t prng( PRNG & prng, uint32_t l, uint32_t u ) __attribute__(( warn_unused_result )) { return prng( prng, u - l + 1 ) + l; } // [l,u]

longrun_tests/Makefile.am

rf5a51db	rcc7bbe6
36	36	-g \
37	37	-Wall \
	38	-Wextra \
	39	-Werror=return-type
38	40	-Wno-unused-function \
39	41	-quiet \

src/AST/Convert.hpp

rf5a51db	rcc7bbe6
20	20	class Declaration;
21	21	namespace ast {
22		~~struct~~ TranslationUnit;
	22	class TranslationUnit;
23	23	};
24	24

src/AST/Decl.cpp

-              rf5a51db
+              rcc7bbe6
         if ( uniqueId ) return;  // ensure only set once
         uniqueId = ++lastUniqueId;
+        idMap[ uniqueId ] = this;
+        // The extra readonly pointer is causing some reference counting issues.
+        // idMap[ uniqueId ] = this;
+}
 readonly<Decl> Decl::fromId( UniqueId id ) {
+        // Right now this map is always empty, so don't use it.
+        assert( false );
         IdMapType::const_iterator i = idMap.find( id );
         if ( i != idMap.end() ) return i->second;

src/AST/Fwd.hpp

rf5a51db	rcc7bbe6
140	140	typedef unsigned int UniqueId;
141	141
142		~~struct~~ TranslationUnit;
	142	class TranslationUnit;
143	143	// TODO: Get from the TranslationUnit:
144	144	extern ptr<Type> sizeType;

src/AST/Pass.hpp

-              rf5a51db
+              rcc7bbe6
 private:
+        // Regular nodes
+        __pass::result1<ast::Stmt> call_accept( const ast::Stmt * );
+        __pass::result1<ast::Expr> call_accept( const ast::Expr * );
+        /// This has a `type` member that is the return type for the
+        /// generic call_accept if the generic call_accept is defined.
         template< typename node_t >
+        struct result1 {
+                bool differs;
+                const node_t * value;
+                template< typename object_t, typename super_t, typename field_t >
+                void apply(object_t *, field_t super_t::* field);
+        };
+        result1<ast::Stmt> call_accept( const ast::Stmt * );
+        result1<ast::Expr> call_accept( const ast::Expr * );
+        using generic_call_accept_result =
+                std::enable_if<
+                                !std::is_base_of<ast::Expr, node_t>::value &&
+                                !std::is_base_of<ast::Stmt, node_t>::value
+                        , __pass::result1<
+                                typename std::remove_pointer< typename std::result_of<
+                                        decltype(&node_t::accept)(node_t*, type&) >::type >::type
+                        >
+                >;
         template< typename node_t >
         auto call_accept( const node_t * node )
+                -> typename std::enable_if<
+                                !std::is_base_of<ast::Expr, node_t>::value &&
+                                !std::is_base_of<ast::Stmt, node_t>::value
+                        , result1<
+                                typename std::remove_pointer< decltype( node->accept(*this) ) >::type
+                        >
+                >::type;
+                -> typename generic_call_accept_result<node_t>::type;
         // requests WithStmtsToAdd directly add to this statement, as if it is a compound.
+        result1<ast::Stmt> call_accept_as_compound(const ast::Stmt *);
+        template<typename it_t, template <class...> class container_t>
+                static inline void take_all_delta( it_t it, container_t<ast::ptr<ast::Decl>> * decls, bool * mutated = nullptr ) {
+                        if(empty(decls)) return;
+                        std::transform(decls->begin(), decls->end(), it, [](ast::ptr<ast::Decl>&& decl) -> auto {
+                                        auto loc = decl->location;
+                                        auto stmt = new DeclStmt( loc, decl.release() );
+                                        return { {stmt}, -1, false };
+                                });
+                        decls->clear();
+                        if(mutated) *mutated = true;
+                }
+        // Container of statements
+        __pass::result1<ast::Stmt> call_accept_as_compound(const ast::Stmt *);
         template< template <class...> class container_t >
+        struct resultNstmt {
+                struct delta {
+                        ptr<Stmt> nval;
+                        ssize_t old_idx;
+                        bool is_old;
+                        delta(const Stmt * s, ssize_t i, bool old) : nval{s}, old_idx{i}, is_old{old} {}
+                };
+                bool differs;
+                container_t< delta > values;
+                resultNstmt() : differs(false), values{} {}
+                resultNstmt(bool diff, container_t< delta > && vals) : differs(diff), values(vals) {}
+                template< typename object_t, typename super_t, typename field_t >
+                void apply(object_t *, field_t super_t::* field);
+                template< template <class...> class incontainer_t >
+                void take_all( incontainer_t<ast::ptr<ast::Stmt>> * stmts ) {
+                        if(!stmts || stmts->empty()) return;
+                        std::transform(stmts->begin(), stmts->end(), std::back_inserter( values ), [](ast::ptr<ast::Stmt>& decl) -> delta {
+                                        return delta( decl.release(), -1, false );
+                                });
+                        stmts->clear();
+                        differs = true;
+                }
+                template< template <class...> class incontainer_t >
+                void take_all( incontainer_t<ast::ptr<ast::Decl>> * decls ) {
+                        if(!decls || decls->empty()) return;
+                        std::transform(decls->begin(), decls->end(), std::back_inserter( values ), [](ast::ptr<ast::Decl>& decl) -> auto {
+                                        auto loc = decl->location;
+                                        auto stmt = new DeclStmt( loc, decl.release() );
+                                        return delta( stmt, -1, false );
+                                });
+                        decls->clear();
+                        differs = true;
+                }
+        };
+        template< template <class...> class container_t >
+        resultNstmt<container_t> call_accept( const container_t< ptr<Stmt> > & );
+        // Container of something
+        __pass::resultNstmt<container_t> call_accept( const container_t< ptr<Stmt> > & );
         template< template <class...> class container_t, typename node_t >
+        struct resultN {
+                bool differs;
+                container_t<ptr<node_t>> values;
+                template< typename object_t, typename super_t, typename field_t >
+                void apply(object_t *, field_t super_t::* field);
+        };
+        template< template <class...> class container_t, typename node_t >
+        resultN< container_t, node_t > call_accept( const container_t< ptr<node_t> > & container );
+        __pass::resultN< container_t, node_t > call_accept( const container_t< ptr<node_t> > & container );
 public:

src/AST/Pass.impl.hpp

-              rf5a51db
+              rcc7bbe6
+                }
                 //------------------------------
                 /// Check if value was mutated, different for pointers and containers
 …
+        }
-        template< typename core_t >
         template< typename node_t >
         template< typename object_t, typename super_t, typename field_t >
         void ast::Pass< core_t >::result1< node_t >::apply(object_t * object, field_t super_t::* field) {
+        void __pass::result1< node_t >::apply( object_t * object, field_t super_t::* field ) {
                 object->*field = value;
+        }
 …
         template< typename node_t >
         auto ast::Pass< core_t >::call_accept( const node_t * node )
+                -> typename std::enable_if<
+                                !std::is_base_of<ast::Expr, node_t>::value &&
+                                !std::is_base_of<ast::Stmt, node_t>::value
+                        , ast::Pass< core_t >::result1<
+                                typename std::remove_pointer< decltype( node->accept(*this) ) >::type
+                        >
+                >::type
+                -> typename ast::Pass< core_t >::template generic_call_accept_result<node_t>::type
+        {
                 __pedantic_pass_assert( __visit_children() );
 …
                 auto nval = node->accept( *this );
                 ast::Pass< core_t >::result1<
+                __pass::result1<
                         typename std::remove_pointer< decltype( node->accept(*this) ) >::type
                 > res;
 …
         template< typename core_t >
         ast::Pass< core_t >::result1<ast::Expr> ast::Pass< core_t >::call_accept( const ast::Expr * expr ) {
+        __pass::template result1<ast::Expr> ast::Pass< core_t >::call_accept( const ast::Expr * expr ) {
                 __pedantic_pass_assert( __visit_children() );
                 __pedantic_pass_assert( expr );
 …
         template< typename core_t >
         ast::Pass< core_t >::result1<ast::Stmt> ast::Pass< core_t >::call_accept( const ast::Stmt * stmt ) {
+        __pass::template result1<ast::Stmt> ast::Pass< core_t >::call_accept( const ast::Stmt * stmt ) {
                 __pedantic_pass_assert( __visit_children() );
                 __pedantic_pass_assert( stmt );
 …
         template< typename core_t >
         ast::Pass< core_t >::result1<ast::Stmt> ast::Pass< core_t >::call_accept_as_compound( const ast::Stmt * stmt ) {
+        __pass::template result1<ast::Stmt> ast::Pass< core_t >::call_accept_as_compound( const ast::Stmt * stmt ) {
                 __pedantic_pass_assert( __visit_children() );
                 __pedantic_pass_assert( stmt );
 …
+        }
-        template< typename core_t >
         template< template <class...> class container_t >
         template< typename object_t, typename super_t, typename field_t >
         void ast::Pass< core_t >::resultNstmt<container_t>::apply(object_t * object, field_t super_t::* field) {
+        void __pass::resultNstmt<container_t>::apply(object_t * object, field_t super_t::* field) {
                 auto & container = object->*field;
                 __pedantic_pass_assert( container.size() <= values.size() );
 …
                 container_t<ptr<Stmt>> nvals;
                 for(delta & d : values) {
                         if( d.is_old ) {
+                for (delta & d : values) {
+                        if ( d.is_old ) {
                                 __pedantic_pass_assert( cit.idx <= d.old_idx );
                                 std::advance( cit, d.old_idx - cit.idx );
                                 nvals.push_back( std::move( (*cit).val) );
                         } else {
                                 nvals.push_back( std::move(d.nval) );
+                                nvals.push_back( std::move(d.new_val) );
+                        }
+                }
+                object->*field = std::move(nvals);
+                container = std::move(nvals);
+        }
+        template< template <class...> class container_t >
+        template< template <class...> class incontainer_t >
+        void __pass::resultNstmt< container_t >::take_all( incontainer_t<ptr<Stmt>> * stmts ) {
+                if (!stmts || stmts->empty()) return;
+                std::transform(stmts->begin(), stmts->end(), std::back_inserter( values ),
+                        [](ast::ptr<ast::Stmt>& stmt) -> delta {
+                                return delta( stmt.release(), -1, false );
+                        });
+                stmts->clear();
+                differs = true;
+        }
+        template< template<class...> class container_t >
+        template< template<class...> class incontainer_t >
+        void __pass::resultNstmt< container_t >::take_all( incontainer_t<ptr<Decl>> * decls ) {
+                if (!decls || decls->empty()) return;
+                std::transform(decls->begin(), decls->end(), std::back_inserter( values ),
+                        [](ast::ptr<ast::Decl>& decl) -> delta {
+                                auto loc = decl->location;
+                                auto stmt = new DeclStmt( loc, decl.release() );
+                                return delta( stmt, -1, false );
+                        });
+                decls->clear();
+                differs = true;
+        }
         template< typename core_t >
         template< template <class...> class container_t >
         ast::Pass< core_t >::resultNstmt<container_t> ast::Pass< core_t >::call_accept( const container_t< ptr<Stmt> > & statements ) {
+        __pass::template resultNstmt<container_t> ast::Pass< core_t >::call_accept( const container_t< ptr<Stmt> > & statements ) {
                 __pedantic_pass_assert( __visit_children() );
                 if( statements.empty() ) return {};
 …
                 pass_visitor_stats.avg->push(pass_visitor_stats.depth);
                 resultNstmt<container_t> new_kids;
+                __pass::resultNstmt<container_t> new_kids;
                 for( auto value : enumerate( statements ) ) {
                         try {
 …
+        }
-        template< typename core_t >
         template< template <class...> class container_t, typename node_t >
         template< typename object_t, typename super_t, typename field_t >
         void ast::Pass< core_t >::resultN<container_t, node_t>::apply(object_t * object, field_t super_t::* field) {
+        void __pass::resultN<container_t, node_t>::apply(object_t * object, field_t super_t::* field) {
                 auto & container = object->*field;
                 __pedantic_pass_assert( container.size() == values.size() );
 …
         template< typename core_t >
         template< template <class...> class container_t, typename node_t >
         ast::Pass< core_t >::resultN<container_t, node_t> ast::Pass< core_t >::call_accept( const container_t< ast::ptr<node_t> > & container ) {
+        __pass::template resultN<container_t, node_t> ast::Pass< core_t >::call_accept( const container_t< ast::ptr<node_t> > & container ) {
                 __pedantic_pass_assert( __visit_children() );
                 if( container.empty() ) return {};
 …
                 if ( ! errors.isEmpty() ) { throw errors; }
                 return ast::Pass< core_t >::resultN<container_t, node_t>{ mutated,  new_kids };
+                return ast::__pass::resultN<container_t, node_t>{ mutated, new_kids };
+        }

src/AST/Pass.proto.hpp

-              rf5a51db
+              rcc7bbe6
 class Pass;
 struct TranslationUnit;
+class TranslationUnit;
 struct PureVisitor;
 …
                 static constexpr bool value = std::is_void< ret_t >::value ||
                         std::is_base_of<const node_t, typename std::remove_pointer<ret_t>::type >::value;
+        };
+        /// The result is a single node.
+        template< typename node_t >
+        struct result1 {
+                bool differs;
+                const node_t * value;
+                template< typename object_t, typename super_t, typename field_t >
+                void apply( object_t *, field_t super_t::* field );
+        };
+        /// The result is a container of statements.
+        template< template<class...> class container_t >
+        struct resultNstmt {
+                /// The delta/change on a single node.
+                struct delta {
+                        ptr<Stmt> new_val;
+                        ssize_t old_idx;
+                        bool is_old;
+                        delta(const Stmt * s, ssize_t i, bool old) :
+                                new_val(s), old_idx(i), is_old(old) {}
+                };
+                bool differs;
+                container_t< delta > values;
+                template< typename object_t, typename super_t, typename field_t >
+                void apply( object_t *, field_t super_t::* field );
+                template< template<class...> class incontainer_t >
+                void take_all( incontainer_t<ptr<Stmt>> * stmts );
+                template< template<class...> class incontainer_t >
+                void take_all( incontainer_t<ptr<Decl>> * decls );
+        };
+        /// The result is a container of nodes.
+        template< template<class...> class container_t, typename node_t >
+        struct resultN {
+                bool differs;
+                container_t<ptr<node_t>> values;
+                template< typename object_t, typename super_t, typename field_t >
+                void apply( object_t *, field_t super_t::* field );
         };

src/AST/TranslationUnit.hpp

-              rf5a51db
+              rcc7bbe6
 namespace ast {
+struct TranslationUnit {
+class TranslationUnit {
+public:
         std::list< ptr< Decl > > decls;

src/AST/module.mk

-              rf5a51db
+              rcc7bbe6
 SRC_AST = \
-        AST/AssertAcyclic.cpp \
-        AST/AssertAcyclic.hpp \
         AST/Attribute.cpp \
         AST/Attribute.hpp \
 …
         AST/TypeSubstitution.cpp \
         AST/TypeSubstitution.hpp \
+        AST/Util.cpp \
+        AST/Util.hpp \
         AST/Visitor.hpp

src/CodeGen/FixNames.h

rf5a51db	rcc7bbe6
20	20	class Declaration;
21	21	namespace ast {
22		~~struct~~ TranslationUnit;
	22	class TranslationUnit;
23	23	}
24	24

src/Common/CodeLocation.h

-              rf5a51db
+              rcc7bbe6
         CodeLocation( const CodeLocation& rhs ) = default;
+        CodeLocation( CodeLocation&& rhs ) = default;
+        CodeLocation& operator=( const CodeLocation & ) = default;
+        CodeLocation& operator=( CodeLocation && ) = default;
         bool isSet () const {

src/Common/CodeLocationTools.hpp

rf5a51db	rcc7bbe6
17	17
18	18	namespace ast {
19		~~struct~~ TranslationUnit;
	19	class TranslationUnit;
20	20	}
21	21

src/Common/ResolvProtoDump.hpp

rf5a51db	rcc7bbe6
17	17
18	18	namespace ast {
19		~~struct~~ TranslationUnit;
	19	class TranslationUnit;
20	20	}
21	21

src/Concurrency/Waitfor.cc

-              rf5a51db
+              rcc7bbe6
                         ),
                         new ListInit(
+                                map_range < std::list<Initializer*> > ( clause.target.arguments, [this](Expression * expr ){
+                                        Expression * init = new CastExpr(
+                                                new UntypedExpr(
+                                                        new NameExpr( "get_monitor" ),
+                                                        { expr }
+                                                ),
+                                                new PointerType(
+                                                        noQualifiers,
+                                                        new StructInstType(
+                                                                noQualifiers,
+                                                                decl_monitor
+                                                        )
+                                                ),
+                                                false
+                                        );
+                                        ResolvExpr::findSingleExpression( init, indexer );
+                                        return new SingleInit( init );
+                                map_range < std::list<Initializer*> > ( clause.target.arguments, [](Expression * expr ){
+                                        return new SingleInit( expr );
                                 })
+                        )

src/ControlStruct/MLEMutator.cc

rf5a51db	rcc7bbe6
66	66
67	67	// break labels have to come after the statement they break out of, so mutate a statement, then if they inform us
68		// through the breakLabel field tha they need a place to jump to on a break statement, add the break label to the
	68	// through the breakLabel field that they need a place to jump to on a break statement, add the break label to the
69	69	// body of statements
70	70	void MultiLevelExitMutator::fixBlock( std::list< Statement * > &kids, bool caseClause ) {

src/ControlStruct/MultiLevelExit.cpp

rf5a51db	rcc7bbe6
176	176	auto mutStmt = mutate( stmt );
177	177	// A child statement may set the break label.
178		mutStmt->kids = ~~move( fixBlock( stmt->kids, false )~~ );
	178	mutStmt->kids = fixBlock( stmt->kids, false );
179	179
180	180	if ( isLabeled ) {

src/InitTweak/FixInit.h

rf5a51db	rcc7bbe6
21	21	class Declaration;
22	22	namespace ast {
23		~~struct~~ TranslationUnit;
	23	class TranslationUnit;
24	24	}
25	25

src/MakeLibCfa.h

-              rf5a51db
+              rcc7bbe6
 // file "LICENCE" distributed with Cforall.
 //
 // MakeLibCfa.h --
+// MakeLibCfa.h --
 //
 // Author           : Richard C. Bilson
 …
 class Declaration;
 namespace ast {
         struct TranslationUnit;
+        class TranslationUnit;
+}

src/Makefile.am

-              rf5a51db
+              rcc7bbe6
 $(srcdir)/AST/Type.hpp : BasicTypes-gen.cc
         ${AM_V_GEN}${CXXCOMPILE} $< -o BasicTypes-gen -Wall -Wextra
+        ${AM_V_GEN}${CXXCOMPILE} $< -o BasicTypes-gen -Wall -Wextra -Werror=return-type
         @./BasicTypes-gen
         @rm BasicTypes-gen
 …
 EXTRA_DIST = include/cassert include/optional BasicTypes-gen.cc
 AM_CXXFLAGS = @HOST_FLAGS@ -Wno-deprecated -Wall -Wextra -DDEBUG_ALL -I./Parser -I$(srcdir)/Parser -I$(srcdir)/include -DYY_NO_INPUT -O3 -g -std=c++14 $(TCMALLOCFLAG)
+AM_CXXFLAGS = @HOST_FLAGS@ -Wno-deprecated -Wall -Wextra -Werror=return-type -DDEBUG_ALL -I./Parser -I$(srcdir)/Parser -I$(srcdir)/include -DYY_NO_INPUT -O3 -g -std=c++14 $(TCMALLOCFLAG)
 AM_LDFLAGS  = @HOST_FLAGS@ -Xlinker -export-dynamic
 ARFLAGS     = cr

src/Parser/parser.yy

-              rf5a51db
+              rcc7bbe6
 // Created On       : Sat Sep  1 20:22:55 2001
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Tue Feb  1 11:06:13 2022
 // Update Count     : 5167
+// Last Modified On : Sat Feb 19 09:47:20 2022
+// Update Count     : 5218
 //
 …
         identifier_or_type_name ':' attribute_list_opt statement
                 { $$ = $4->add_label( $1, $3 ); }
+        | identifier_or_type_name ':' attribute_list_opt error
+                { SemanticError( yylloc, "previous label must be associated with a statement (where a declaration is not a statement). Move the label or terminate with a semi-colon." ); $$ = nullptr; }
+        ;
 …
         | statement_list_nodecl statement
                 { assert( $1 ); $1->set_last( $2 ); $$ = $1; }
+        | statement_list_nodecl error
+                { SemanticError( yylloc, "declarations only allowed at the start of the switch body, i.e., after the '{'." ); $$ = nullptr; }
+        ;
 …
         | MUTEX '(' ')' comma_expression ';'
                 { $$ = new StatementNode( build_mutex( nullptr, new StatementNode( build_expr( $4 ) ) ) ); }
-                // { SemanticError( yylloc, "Mutex expression is currently unimplemented." ); $$ = nullptr; }
+        ;
 …
                         $$ = $7 ? new StatementNode( build_compound( (StatementNode *)((new StatementNode( $7 ))->set_last( sw )) ) ) : sw;
+                }
+        | SWITCH '(' comma_expression ')' '{' error '}'         // CFA
+                { SemanticError( yylloc, "only declarations can appear before the list of case clauses." ); $$ = nullptr; }
         | CHOOSE '(' comma_expression ')' case_clause           // CFA
                 { $$ = new StatementNode( build_switch( false, $3, $5 ) ); }
 …
                         $$ = $7 ? new StatementNode( build_compound( (StatementNode *)((new StatementNode( $7 ))->set_last( sw )) ) ) : sw;
+                }
+        | CHOOSE '(' comma_expression ')' '{' error '}'         // CFA
+                { SemanticError( yylloc, "only declarations can appear before the list of case clauses." ); $$ = nullptr; }
+        ;
 …
 case_label:                                                                                             // CFA
+        CASE case_value_list ':'                                        { $$ = $2; }
+        CASE error
+                { SemanticError( yylloc, "missing case list after case." ); $$ = nullptr; }
+        | CASE case_value_list ':'                                      { $$ = $2; }
+        | CASE case_value_list error
+                { SemanticError( yylloc, "missing colon after case list." ); $$ = nullptr; }
         | DEFAULT ':'                                                           { $$ = new StatementNode( build_default() ); }
                 // A semantic check is required to ensure only one default clause per switch/choose statement.
+        ;
+//label_list_opt:
+//      // empty
+//      | identifier_or_type_name ':'
+//      | label_list_opt identifier_or_type_name ':'
+//      ;
+        | DEFAULT error
+                { SemanticError( yylloc, "missing colon after default." ); $$ = nullptr; }
+        ;
 case_label_list:                                                                                // CFA
 …
                 { $$ = new StatementNode( build_while( $3, maybe_build_compound( $5 ) ) ); }
         | WHILE '(' conditional_declaration ')' statement ELSE statement // CFA
-                // { SemanticError( yylloc, "Loop default block is currently unimplemented." ); $$ = nullptr; }
                 { $$ = new StatementNode( build_while( $3, maybe_build_compound( $5 ), $7 ) ); }
         | DO statement WHILE '(' ')' ';'                                        // CFA => do while( 1 )
 …
                 { $$ = new StatementNode( build_do_while( $5, maybe_build_compound( $2 ) ) ); }
         | DO statement WHILE '(' comma_expression ')' ELSE statement // CFA
-                // { SemanticError( yylloc, "Loop default block is currently unimplemented." ); $$ = nullptr; }
                 { $$ = new StatementNode( build_do_while( $5, maybe_build_compound( $2 ), $8 ) ); }
         | FOR '(' ')' statement                                                         // CFA => for ( ;; )
 …
                 { $$ = new StatementNode( build_for( $3, maybe_build_compound( $5 ) ) ); }
         | FOR '(' for_control_expression_list ')' statement ELSE statement // CFA
-                // { SemanticError( yylloc, "Loop default block is currently unimplemented." ); $$ = nullptr; }
                 { $$ = new StatementNode( build_for( $3, maybe_build_compound( $5 ), $7 ) ); }
+        ;
 …
         | ASM '(' string_literal ')' ';'                                        // GCC, global assembler statement
                 { $$ = DeclarationNode::newAsmStmt( new StatementNode( build_asm( false, $3, 0 ) ) ); }
+        | EXTERN STRINGliteral
+                {
+                        linkageStack.push( linkage );                           // handle nested extern "C"/"Cforall"
+                        linkage = LinkageSpec::update( yylloc, linkage, $2 );
+                }
+          up external_definition down
+                {
+                        linkage = linkageStack.top();
+                        linkageStack.pop();
+                        $$ = $5;
+                }
         | EXTERN STRINGliteral                                                          // C++-style linkage specifier
+                {

src/ResolvExpr/Resolver.cc

-              rf5a51db
+              rcc7bbe6
+                }
         } // anonymous namespace
 /// Establish post-resolver invariants for expressions
 …
         namespace {
                 /// resolve `untyped` to the expression whose candidate satisfies `pred` with the
 …
                         clause2.target.args.reserve( clause.target.args.size() );
+                        const ast::StructDecl * decl_monitor = symtab.lookupStruct( "monitor$" );
                         for ( auto arg : argsCandidates.front() ) {
+                                clause2.target.args.emplace_back( std::move( arg->expr ) );
+                                const auto & loc = stmt->location;
+                                ast::Expr * init = new ast::CastExpr( loc,
+                                        new ast::UntypedExpr( loc,
+                                                new ast::NameExpr( loc, "get_monitor" ),
+                                                { arg->expr }
+                                        ),
+                                        new ast::PointerType(
+                                                new ast::StructInstType(
+                                                        decl_monitor
+                                                )
+                                        )
+                                );
+                                clause2.target.args.emplace_back( findSingleExpression( init, symtab ) );
+                        }
 …
                 if (auto functionDecl = decl.as<ast::FunctionDecl>()) {
                         // xxx - can intrinsic gen ever fail?
                         if (functionDecl->linkage == ast::Linkage::AutoGen) {
+                        if (functionDecl->linkage == ast::Linkage::AutoGen) {
                                 auto mutDecl = mutate(functionDecl);
                                 mutDecl->isDeleted = true;

src/ResolvExpr/Resolver.h

-              rf5a51db
+              rcc7bbe6
         class StmtExpr;
         class SymbolTable;
         struct TranslationUnit;
+        class TranslationUnit;
         class Type;
         class TypeEnvironment;
 …
         ast::ptr< ast::Init > resolveCtorInit(
                 const ast::ConstructorInit * ctorInit, const ast::SymbolTable & symtab );
         /// Resolves a statement expression
+        /// Resolves a statement expression
         const ast::Expr * resolveStmtExpr(
                 const ast::StmtExpr * stmtExpr, const ast::SymbolTable & symtab );

src/SymTab/Validate.cc

-              rf5a51db
+              rcc7bbe6
         };
+        // These structs are the sub-sub-passes of ForallPointerDecay_old.
+        struct TraitExpander_old final {
+                void previsit( FunctionType * );
+                void previsit( StructDecl * );
+                void previsit( UnionDecl * );
+        };
+        struct AssertionFixer_old final {
+                void previsit( FunctionType * );
+                void previsit( StructDecl * );
+                void previsit( UnionDecl * );
+        };
+        struct CheckOperatorTypes_old final {
+                void previsit( ObjectDecl * );
+        };
+        struct FixUniqueIds_old final {
+                void previsit( DeclarationWithType * );
+        };
         struct ReturnChecker : public WithGuards {
                 /// Checks that return statements return nothing if their return type is void
 …
         void validate_D( std::list< Declaration * > & translationUnit ) {
-                PassVisitor<ForallPointerDecay_old> fpd;
+                {
                         Stats::Heap::newPass("validate-D");
 …
                         });
                         Stats::Time::TimeBlock("Forall Pointer Decay", [&]() {
                                 acceptAll( translationUnit, fpd ); // must happen before autogenerateRoutines, after Concurrency::applyKeywords because uniqueIds must be set on declaration before resolution
+                                decayForallPointers( translationUnit ); // must happen before autogenerateRoutines, after Concurrency::applyKeywords because uniqueIds must be set on declaration before resolution
                         });
                         Stats::Time::TimeBlock("Hoist Control Declarations", [&]() {
 …
         void decayForallPointers( std::list< Declaration * > & translationUnit ) {
+                PassVisitor<ForallPointerDecay_old> fpd;
+                acceptAll( translationUnit, fpd );
+                PassVisitor<TraitExpander_old> te;
+                acceptAll( translationUnit, te );
+                PassVisitor<AssertionFixer_old> af;
+                acceptAll( translationUnit, af );
+                PassVisitor<CheckOperatorTypes_old> cot;
+                acceptAll( translationUnit, cot );
+                PassVisitor<FixUniqueIds_old> fui;
+                acceptAll( translationUnit, fui );
+        }
+        void decayForallPointersA( std::list< Declaration * > & translationUnit ) {
+                PassVisitor<TraitExpander_old> te;
+                acceptAll( translationUnit, te );
+        }
+        void decayForallPointersB( std::list< Declaration * > & translationUnit ) {
+                PassVisitor<AssertionFixer_old> af;
+                acceptAll( translationUnit, af );
+        }
+        void decayForallPointersC( std::list< Declaration * > & translationUnit ) {
+                PassVisitor<CheckOperatorTypes_old> cot;
+                acceptAll( translationUnit, cot );
+        }
+        void decayForallPointersD( std::list< Declaration * > & translationUnit ) {
+                PassVisitor<FixUniqueIds_old> fui;
+                acceptAll( translationUnit, fui );
+        }
 …
                 PassVisitor<EnumAndPointerDecay_old> epc;
                 PassVisitor<LinkReferenceToTypes_old> lrt( indexer );
+                PassVisitor<ForallPointerDecay_old> fpd;
+                PassVisitor<TraitExpander_old> te;
+                PassVisitor<AssertionFixer_old> af;
+                PassVisitor<CheckOperatorTypes_old> cot;
+                PassVisitor<FixUniqueIds_old> fui;
                 type->accept( epc );
                 type->accept( lrt );
+                type->accept( fpd );
+                type->accept( te );
+                type->accept( af );
+                type->accept( cot );
+                type->accept( fui );
+        }
 …
+        }
+        /// Replace all traits in assertion lists with their assertions.
+        void expandTraits( std::list< TypeDecl * > & forall ) {
+                for ( TypeDecl * type : forall ) {
+                        std::list< DeclarationWithType * > asserts;
+                        asserts.splice( asserts.end(), type->assertions );
+                        // expand trait instances into their members
+                        for ( DeclarationWithType * assertion : asserts ) {
+                                if ( TraitInstType * traitInst = dynamic_cast< TraitInstType * >( assertion->get_type() ) ) {
+                                        // expand trait instance into all of its members
+                                        expandAssertions( traitInst, back_inserter( type->assertions ) );
+                                        delete traitInst;
+                                } else {
+                                        // pass other assertions through
+                                        type->assertions.push_back( assertion );
+                                } // if
+                        } // for
+                }
+        }
+        /// Fix each function in the assertion list and check for invalid void type.
+        void fixAssertions(
+                        std::list< TypeDecl * > & forall, BaseSyntaxNode * node ) {
+                for ( TypeDecl * type : forall ) {
+                        for ( DeclarationWithType *& assertion : type->assertions ) {
+                                bool isVoid = fixFunction( assertion );
+                                if ( isVoid ) {
+                                        SemanticError( node, "invalid type void in assertion of function " );
+                                } // if
+                        } // for
+                }
+        }
         void ForallPointerDecay_old::previsit( ObjectDecl * object ) {
                 // ensure that operator names only apply to functions or function pointers
 …
         void ForallPointerDecay_old::previsit( UnionDecl * aggrDecl ) {
                 forallFixer( aggrDecl->parameters, aggrDecl );
+        }
+        void TraitExpander_old::previsit( FunctionType * ftype ) {
+                expandTraits( ftype->forall );
+        }
+        void TraitExpander_old::previsit( StructDecl * aggrDecl ) {
+                expandTraits( aggrDecl->parameters );
+        }
+        void TraitExpander_old::previsit( UnionDecl * aggrDecl ) {
+                expandTraits( aggrDecl->parameters );
+        }
+        void AssertionFixer_old::previsit( FunctionType * ftype ) {
+                fixAssertions( ftype->forall, ftype );
+        }
+        void AssertionFixer_old::previsit( StructDecl * aggrDecl ) {
+                fixAssertions( aggrDecl->parameters, aggrDecl );
+        }
+        void AssertionFixer_old::previsit( UnionDecl * aggrDecl ) {
+                fixAssertions( aggrDecl->parameters, aggrDecl );
+        }
+        void CheckOperatorTypes_old::previsit( ObjectDecl * object ) {
+                // ensure that operator names only apply to functions or function pointers
+                if ( CodeGen::isOperator( object->name ) && ! dynamic_cast< FunctionType * >( object->type->stripDeclarator() ) ) {
+                        SemanticError( object->location, toCString( "operator ", object->name.c_str(), " is not a function or function pointer." )  );
+                }
+        }
+        void FixUniqueIds_old::previsit( DeclarationWithType * decl ) {
+                decl->fixUniqueId();
+        }

src/SymTab/Validate.h

-              rf5a51db
+              rcc7bbe6
         void validate_F( std::list< Declaration * > &translationUnit );
         void decayForallPointers( std::list< Declaration * > & translationUnit );
+        void decayForallPointersA( std::list< Declaration * > & translationUnit );
+        void decayForallPointersB( std::list< Declaration * > & translationUnit );
+        void decayForallPointersC( std::list< Declaration * > & translationUnit );
+        void decayForallPointersD( std::list< Declaration * > & translationUnit );
         const ast::Type * validateType(

src/Validate/module.mk

rf5a51db	rcc7bbe6
20	20	Validate/CompoundLiteral.cpp \
21	21	Validate/CompoundLiteral.hpp \
	22	Validate/ForallPointerDecay.cpp \
	23	Validate/ForallPointerDecay.hpp \
22	24	Validate/HandleAttributes.cc \
23	25	Validate/HandleAttributes.h \

src/main.cc

-              rf5a51db
+              rcc7bbe6
 #include "AST/Convert.hpp"
+#include "AST/Print.hpp"
 #include "CompilationState.h"
 #include "../config.h"                      // for CFA_LIBDIR
 …
 #include "Validate/Autogen.hpp"             // for autogenerateRoutines
 #include "Validate/FindSpecialDecls.h"      // for findGlobalDecls
+#include "Validate/ForallPointerDecay.hpp"  // for decayForallPointers
 #include "Validate/CompoundLiteral.hpp"     // for handleCompoundLiterals
 #include "Validate/InitializerLength.hpp"   // for setLengthFromInitializer
 …
                 if( useNewAST ) {
+                        PASS( "Apply Concurrent Keywords", Concurrency::applyKeywords( translationUnit ) );
+                        PASS( "Forall Pointer Decay", SymTab::decayForallPointers( translationUnit ) );
+                        PASS( "Implement Concurrent Keywords", Concurrency::applyKeywords( translationUnit ) );
+                        //PASS( "Forall Pointer Decay - A", SymTab::decayForallPointersA( translationUnit ) );
+                        //PASS( "Forall Pointer Decay - B", SymTab::decayForallPointersB( translationUnit ) );
+                        //PASS( "Forall Pointer Decay - C", SymTab::decayForallPointersC( translationUnit ) );
+                        //PASS( "Forall Pointer Decay - D", SymTab::decayForallPointersD( translationUnit ) );
                         CodeTools::fillLocations( translationUnit );
 …
                         forceFillCodeLocations( transUnit );
+                        // Must be after implement concurrent keywords; because uniqueIds
+                        //   must be set on declaration before resolution.
+                        // Must happen before autogen routines are added.
+                        PASS( "Forall Pointer Decay", Validate::decayForallPointers( transUnit ) );
                         // Must happen before autogen routines are added.

tests/.expect/declarationSpecifier.arm64.txt

-              rf5a51db
+              rcc7bbe6
 char **_X13cfa_args_argvPPc_1;
 char **_X13cfa_args_envpPPc_1;
 signed int _X17cfa_main_returnedi_1 = ((signed int )0);
+__attribute__ ((weak)) extern signed int _X17cfa_main_returnedi_1;
 signed int main(signed int _X4argci_1, char **_X4argvPPc_1, char **_X4envpPPc_1){
     __attribute__ ((unused)) signed int _X12_retval_maini_1;
 …
     signed int _tmp_cp_ret6;
     signed int _X3reti_2 = (((void)(_tmp_cp_ret6=invoke_main(_X4argci_1, _X4argvPPc_1, _X4envpPPc_1))) , _tmp_cp_ret6);
+    {
+        ((void)(_X17cfa_main_returnedi_1=((signed int )1)));
+    if ( ((&_X17cfa_main_returnedi_1)!=((signed int *)0)) ) {
+        {
+            ((void)(_X17cfa_main_returnedi_1=((signed int )1)));
+        }
+    }

tests/.expect/gccExtensions.arm64.txt

-              rf5a51db
+              rcc7bbe6
 char **_X13cfa_args_argvPPc_1;
 char **_X13cfa_args_envpPPc_1;
 signed int _X17cfa_main_returnedi_1 = ((signed int )0);
+__attribute__ ((weak)) extern signed int _X17cfa_main_returnedi_1;
 signed int main(signed int _X4argci_1, char **_X4argvPPc_1, char **_X4envpPPc_1){
     __attribute__ ((unused)) signed int _X12_retval_maini_1;
 …
     signed int _tmp_cp_ret6;
     signed int _X3reti_2 = (((void)(_tmp_cp_ret6=invoke_main(_X4argci_1, _X4argvPPc_1, _X4envpPPc_1))) , _tmp_cp_ret6);
+    {
+        ((void)(_X17cfa_main_returnedi_1=((signed int )1)));
+    if ( ((&_X17cfa_main_returnedi_1)!=((signed int *)0)) ) {
+        {
+            ((void)(_X17cfa_main_returnedi_1=((signed int )1)));
+        }
+    }

tests/.expect/random.arm64.txt

rf5a51db	rcc7bbe6
1	1	õ
2	2	=
3		V
	3	K
4	4	-911259971
5	5	6
6		-4
	6	11
7	7	1232105397
8	8	0
9		18
	9	11
10	10	-914096085
11	11	1
12		15
	12	20
13	13	2077092859
14	14	1
15		11
	15	12
16	16	0.677254
17	17	0.678106775246139

tests/Makefile.am

rf5a51db	rcc7bbe6
43	43	-g \
44	44	-Wall \
	45	-Werror=return-type \
45	46	-Wno-unused-function \
46	47	-Wno-psabi \

tests/meta/dumpable.cfa

rf5a51db	rcc7bbe6
72	72	}
73	73
74		if((buf.f_bsize * buf.f_bavail) < 536870912) {
75		serr \| "Available diskspace is less than ~500Mb: " \| (buf.f_bsize * buf.f_bavail);
	74	uint64_t avail = buf.f_bavail;
	75	avail *= buf.f_bsize;
	76	if(avail < 536870912_l64u) {
	77	serr \| "Available diskspace is less than ~500Mb: " \| avail;
76	78	}
77	79

tests/unified_locking/mutex_test.hfa

rf5a51db	rcc7bbe6
54	54	}
55	55
56		~~int~~ test() {
	56	void test() {
57	57	uint32_t sum = -32;
58	58	mo.sum = -32;

tools/Makefile.am

rf5a51db	rcc7bbe6
19	19
20	20	noinst_PROGRAMS = busy catchsig repeat watchdog
21		AM_CFLAGS = -Wall -Wextra -O2 -g
	21	AM_CFLAGS = -Wall -Wextra -Werror=return-type -O2 -g
22	22	busy_LDFLAGS = -pthread
23	23

tools/prettyprinter/Makefile.am

rf5a51db	rcc7bbe6
32	32	nodist_pretty_SOURCES = ${SRC}
33	33	pretty_LDADD = ${LEXLIB} -ldl # yywrap
34		pretty_CXXFLAGS = -Wno-deprecated -Wall -DYY_NO_INPUT -O2 -g -std=c++14
	34	pretty_CXXFLAGS = -Wno-deprecated -Wall -Wextra -Werror=return-type -DYY_NO_INPUT -O2 -g -std=c++14
35	35
36	36	MOSTLYCLEANFILES = parser.output

Context Navigation

Legend:

Download in other formats: