Changeset 8d66610 for doc/theses

doc/theses/andrew_beach_MMath/Makefile

r5407cdc	r8d66610
34	34	${LATEX} ${BASE}
35	35	${BIBTEX} ${BUILD}/${BASE}
36		~~${LATEX} ${BASE}~~
37	36	${GLOSSARY} ${BUILD}/${BASE}
38	37	${LATEX} ${BASE}

doc/theses/andrew_beach_MMath/cfalab.sty

-                      r5407cdc
+                      r8d66610
 % Package for CFA Research Lab.
+% (Now more a personal collection and testing grounds for common.sty.)
+%
+% Made by combining and updating various macro files people had made.
+% This is a collection of commands everyone working on CFA related documents
+% should find useful. So mostly programming language related tools.
+%
 % Internal commands are prefixed with "\cfalab@".
 …
 % Other packages required.
+%
+% Access to new basic LaTeX tools and other low level commands.
 \RequirePackage{etoolbox}
+% Code formatting tools and environments.
 \RequirePackage{listings}
+% Automatically adds spaces.
 \RequirePackage{xspace}
+% Symbols: All symbols are zero argument robust commands with special rules
+% about the space following the c.s. token. Normally the space might be
+% re-added according to the rules of the xspace package. They may be followed
+% by a star (which the command will consume) to disable this behaviour.
+% Tip for commands that end with \xspace: if the default is not correct then
+% follow the command with {} to disable \xspace, use '{} ' to force add a
+% space and '{}<whatever-follows>' to force remove one.
+%
+% \CFA
+% Cforall with the forall symbol.
+\newrobustcmd\CFA{\textsf{C\raisebox{\depth}{\rotatebox{180}{A}}}\xspace}
+% \Cpp[<std>]
+% C++ symbol name. You may optionally provide <std> to specify a standard.
+\newrobustcmd\Cpp[1][\xspace]{C++#1}
+% \newsymbolcmd{<command>}{<replacement text>}
+%     Defines <command> to be a symbol that has the given <replacement text>.
+\newrobustcmd*\newsymbolcmd[2]{\newrobustcmd{#1}{\cfalab@symbol{#2}}}
+\def\cfalab@symbol#1{\@ifnextchar*{#1\cfalab@eatstar}{#1\xspace}}
+\def\cfalab@eatstar*{}
+% Cforall with the forall symbol.
+\newsymbolcmd\CFA{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}}
+% C++ with kerning. (No standard number support.)
+\newsymbolcmd\CPP{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}}
+% This is executed very early in the \begin{document} code.
+% This is executed very early in the \begin{document} code, before the
+% document's contents but after packages are loaded.
 \AtEndPreamble{
   \@ifpackageloaded{hyperref}{
 …
     \pdfstringdefDisableCommands{
       \def\CFA{CFA}
+      \def\CPP{C++}
+      \def\Cpp{C++}
+      \def\lstinline{}
+      \def\code#1#2{#2}
+    }
   }{}
+}
+% \colour{<colour>}{<text>}
+% Just \color but using the LaTeX style instead of TeX style command.
+\newcommand*\colour[2]{{\color{#1}#2}}
+% \code{<language>}{<code>}
+% Use the listings package to format the snipit of <code> in <language>.
+\newrobustcmd*\code[2]{\lstinline[language=#1]{#2}}
+% \begin{cfa}[<options>]
+% \end{cfa}
+% Use the listings package to format a block of CFA code.
+% Extra listings options can be passed in as an optional argument.
+\lstnewenvironment{cfa}[1][]{\lstset{language=CFA}\lstset{#1}}{}
+% \settextunderscore{(new|old)}
+% Redefines the underscore either as a new repersentation or the old one.
+% Not that some other packages (ex. hyperref) can override this. Set it up
+% after loading them.
+\let\cfalab@textunderscore@old=\textunderscore
+\newcommand\cfalab@textunderscore@new{%
+    \leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
+\newcommand\settextunderscore[1]{%
+    \renewcommand\textunderscore{\csuse{cfalab@textunderscore@#1}}}
 % The CFA listings language. Based off of ANCI C and including GCC extensions.
 …
 \lstset{defaultdialect={[UW]CFA}}
+% The cfalab style defines some common settings useful in different languages.
+\lstdefinestyle{cfalab}{%
+    columns=fullflexible,
+    basicstyle=\linespread{0.9}\tt,
+    stringstyle=\tt,
+% Create an internal paragraph indent amount. This is used internally to
+% mimic the standard indent even when it has been overriden in the document.
+\newlength\cfalab@parindent
+\deflength\cfalab@parindent{\parindent}
+% The cfacommon style has many useful defaults for CFA and other types of
+% code. Use the listings option "style=cfacommon" to load them.
+\lstdefinestyle{cfacommon}{
+  columns=fullflexible,
+  basicstyle=\linespread{0.9}\sf,
+  stringstyle=\tt,
+  tabsize=5,
+  % Indent code to paragraph indentation.
+  xleftmargin=\cfalab@parindent,
+  % Allow ASCII characters in the range 128-255.
+  extendedchars=true,
+  % This allows you to use "math mode" to insert LaTeX into the code.
+  % Use \( and \) if you need to insert math mode inside that code.
+  escapechar=\$,
+  % Disable LaTeX math escape in CFA code $...$
+  mathescape=false,
+  keepspaces=true,
+  % Do not show spaces with cup.
+  showstringspaces=false,
+  % Show blank lines at end of code.
+  showlines=true,
+  % Spacing above/below code block.
+  aboveskip=4pt,belowskip=0pt,
+  numberstyle=\footnotesize\sf,
+  % Replace/adjust listing characters that look bad in sanserif.
+  literate={-}{\makebox[1ex][c]{\raisebox{0.7ex}{\rule{0.75ex}{0.1ex}}}}1
+    {^}{\raisebox{0.6ex}{$\scriptscriptstyle\land\,$}}1
+    {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
+    {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2
+    {->}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex\textgreater}2,
+}
+% \code*[<escape character>]{<code>}
+%     Use the listings package to format a snipit of <code>.
+%     The <escape character> must be a character that does not appear in
+%     <code> and defaults to a backtick.
+\newcommand*\codeC[2][\`]{\lstinline[language=C]#1#2#1}
+\newcommand*\codeCFA[2][\`]{\lstinline[language=CFA]#1#2#1}
+% common.tex Compatablity ===================================================
+% Below this line is for compatability with the old common.tex file.
+% \settextunderscore{(new|old)}
+%     Redefines the underscore either as a new repersentation or the old one.
+%     Not that some other packages (ex. hyperref) can override this. Set it
+%     up after loading them.
+\let\cfalab@textunderscore@old=\textunderscore
+\newcommand\cfalab@textunderscore@new{%
+    \leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
+\newcommand\settextunderscore[1]{%
+    \renewcommand\textunderscore{\csuse{cfalab@textunderscore@#1}}}
+% Backwards compatable way to activate the cfacommon style.
+\newcommand{\CFAStyle}{\lstset{style=cfacommon}}
+% A couple of abbreviations are provided. Just ones someone liked.
+%
+% Abbreviation formatting commands (renew to customize):
+\newcommand{\abbrevFont}{\textit}
+%
+% Abbreviations that, if not followed by a comma or colon, add a comma.
+\newrobustcmd*\cfalab@abbrev@comma{%
+  \@ifnextchar{,}{}{\@ifnextchar{:}{}{,\xspace}}}
+\providerobustcmd*\eg{\abbrevFont{e}.\abbrevFont{g}.\cfalab@abbrev@comma}
+\providerobustcmd*\ie{\abbrevFont{i}.\abbrevFont{e}.\cfalab@abbrev@comma}
+%
+% Abbreviations that, if not followed by a period, add a period.
+\newrobustcmd*\cfalab@abbrev@period{\@ifnextchar{.}{}{.\xspace}}
+\providerobustcmd*\etc{\abbrevFont{etc}\cfalab@abbrev@period}
+\providerobustcmd*\etal{\abbrevFont{et}~\abbrevFont{al}\cfalab@abbrev@period}
+\providerobustcmd*\viz{\abbrevFont{viz}\cfalab@abbrev@period}
 \endinput

doc/theses/andrew_beach_MMath/existing.tex

-                      r5407cdc
+                      r8d66610
 to be defined~\cite{Moss18}.
 \begin{cfa}
 char i; int i; double i;                        $\C[3.75in]{// variable overload}$
 int f(); double f();                            $\C{// return overload}$
 void g( int ); void g( double );        $\C{// parameter overload}\CRT$
+char i; int i; double i;
+int f(); double f();
+void g( int ); void g( double );
 \end{cfa}
 This feature requires name mangling so the assembly symbols are unique for
 …
 mangling is:
 \begin{cfa}
 // name mangling
+// name mangling on by default
 int i; // _X1ii_1
 @extern "C"@ {  // no name mangling
+extern "C" {  // disables name mangling
         int j; // j
         @extern "Cforall"@ {  // name mangling
+        extern "Cforall" {  // enables name mangling
                 int k; // _X1ki_1
+        }
         // no name mangling
+}
 // name mangling
+        // revert to no name mangling
+}
+// revert to name mangling
 \end{cfa}
 Both forms of @extern@ affect all the declarations within their nested lexical
 …
 \begin{cfa}
 int i, j;
 int @&@ ri = i, @&&@ rri = ri;
+int & ri = i, && rri = ri;
 rri = 3;  // auto-dereference assign to i
 @&@ri = @&@j; // rebindable
+&ri = &j; // rebindable
 ri = 5;   // assign to j
 \end{cfa}
 …
 In general, operator names in \CFA are constructed by bracketing an operator
 token with @?@, which indicates the position of the arguments. For example, infixed
+multiplication is @?*?@ while prefix dereference is @*?@. This syntax make it
+easy to tell the difference between prefix operations (such as @++?@) and
 post-fix operations (@?++@).
+token with @?@, which indicates the position of the arguments. For example,
+infixed multiplication is @?*?@ while prefix dereference is @*?@.
+This syntax make it easy to tell the difference between prefix operations
+(such as @++?@) and post-fix operations (@?++@).
 The special name for a constructor is @?{}@, which comes from the
+initialization syntax in C. The special name for a destructor is @^{}@, where
+the @^@ has no special meaning.
+initialization syntax in C. That initialation syntax is also the operator
+form. \CFA will generate a constructor call each time a variable is declared,
+passing the initialization arguments to the constructort.
+\begin{cfa}
+struct Example { ... };
+void ?{}(Example & this) { ... }
+{
+        Example a;
+        Example b = {};
+}
+void ?{}(Example & this, char first, int num) { ... }
+{
+        Example c = {'a', 2};
+}
+\end{cfa}
+Both @a@ and @b@ will be initalized with the first constructor (there is no
+general way to skip initialation) while @c@ will be initalized with the
+second.
 % I don't like the \^{} symbol but $^\wedge$ isn't better.
+\begin{cfa}
+struct T { ... };
+void ?@{}@(@T &@ this, ...) { ... }  // constructor
+void ?@^{}@(@T &@ this, ...) { ... } // destructor
+Similarly destructors use the special name @^?{}@ (the @^@ has no special
+meaning). They can be called explicatly as well but normally they are
+implicitly called on a variable when it goes out of scope.
+\begin{cfa}
+void ^?{}(Example & this) { ... }
+{
+        T s = @{@ ... @}@;  // same constructor/initialization braces
 } // destructor call automatically generated
 \end{cfa}
+The first parameter is a reference parameter to the type for the
+constructor/destructor. Destructors may have multiple parameters.  The compiler
+implicitly matches an overloaded constructor @void ^?{}(T &, ...);@ to an
+object declaration with associated initialization, and generates a construction
+call after the object is allocated. When an object goes out of scope, the
+matching overloaded destructor @void ^?{}(T &);@ is called.  Without explicit
+definition, \CFA creates a default and copy constructor, destructor and
+assignment (like \Cpp). It is possible to define constructors/destructors for
 basic and existing types (unlike \Cpp).
+    Example d;
+} // <- implicit destructor call
+\end{cfa}
+No operator name is restricted in what function signatures they may be bound
+to although most of the forms cannot be called in operator form. Some
+``near-misses" will generate warnings.
+Whenever a type is defined, \CFA will create a default zero-argument
+constructor, a copy constructor, a series of argument-per-field constructors
+and a destructor. All user constructors are defined after this.
+Because operators are never part of the type definition they may be added
+at any time, including on built-in types.
 \section{Polymorphism}
 …
 works on any type @T@:
 \begin{cfa}
+@forall( T )@ @T@ identity( @T@ val ) { return val; }
+int forty_two = identity( 42 ); // T bound to int, forty_two == 42
+\end{cfa}
+forall( T ) T identity( T val ) { return val; }
+int forty_two = identity( 42 );
+char capital_a = identity( 'A' );
+\end{cfa}
+Each use of a polymorphic declaration will resolve its polymorphic parameters
+(in this case, just @T@) to concrete types (@int@ in the first use and @char@
+in the second).
 To allow a polymorphic function to be separately compiled, the type @T@ must be
 …
 types used in a function, \eg:
 \begin{cfa}
 forall( T @| { void do_once(T); }@) // assertion
+forall( T | { void do_once(T); })
 void do_twice(T value) {
         do_once(value);
         do_once(value);
+}
+void do_once(@int@ i) { ... }  // provide assertion
+@int@ i;
+do_twice(i); // implicitly pass assertion do_once to do_twice
+\end{cfa}
+Any object with a type fulfilling the assertion may be passed as an argument to
+a @do_twice@ call.
+\end{cfa}
 A polymorphic function can be used in the same way as a normal function.  The
 …
 all the variables replaced with the concrete types from the arguments) is
 defined at a call site.
+\begin{cfa}
+void do_once(int i) { ... }
+int i;
+do_twice(i);
+\end{cfa}
+Any object with a type fulfilling the assertion may be passed as an argument to
+a @do_twice@ call.
 Note, a function named @do_once@ is not required in the scope of @do_twice@ to
 …
 call.
 \begin{cfa}
 void do_once(double y) { ... } // global
+void do_once(double y) { ... }
 int quadruple(int x) {
         void do_once(int y) { y = y * 2; } // local
         do_twice(x); // using local "do_once"
+        void do_once(int y) { y = y * 2; }
+        do_twice(x);
         return x;
+}
 …
 function. The matched assertion function is then passed as a function pointer
 to @do_twice@ and called within it.
+The global definition of @do_once@ is ignored.
 To avoid typing long lists of assertions, constraints can be collect into
 …
 and the @forall@ list in the previous example is replaced with the trait.
 \begin{cfa}
 forall(dtype T | @done_once(T)@)
+forall(dtype T | done_once(T))
 \end{cfa}
 In general, a trait can contain an arbitrary number of assertions, both
 …
 declarations instead of parameters, returns, and local variable declarations.
 \begin{cfa}
 forall(dtype @T@)
+forall(dtype T)
 struct node {
         node(@T@) * next;  // generic linked node
         @T@ * data;
+}
 node(@int@) inode;
 \end{cfa}
 The generic type @node(T)@ is an example of a polymorphic-type usage.  Like \Cpp
 template usage, a polymorphic-type usage must specify a type parameter.
+        node(T) * next;  // generic linked node
+        T * data;
+}
+node(int) inode;
+\end{cfa}
+The generic type @node(T)@ is an example of a polymorphic type usage.  Like \Cpp
+template usage, a polymorphic type usage must specify a type parameter.
 There are many other polymorphism features in \CFA but these are the ones used
 …
 Each coroutine has a @main@ function, which takes a reference to a coroutine
 object and returns @void@.
+\begin{cfa}[numbers=left]
+void main(@CountUp & this@) { // argument matches trait is_coroutine
+        unsigned int up = 0;  // retained between calls
+        while (true) {
+                next = up; // make "up" available outside function
+                @suspend;@$\label{suspend}$
+                up += 1;
+\begin{cfa}
+void main(CountUp & this) {
+    for (unsigned int next = 0 ; true ; ++next) {
+                next = up;
+                suspend;$\label{suspend}$
+        }
+}
 …
 @mutex@.
 \begin{cfa}
 void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
+void example(MonitorA & mutex argA, MonitorB & mutex argB);
 \end{cfa}
 When the function is called, it implicitly acquires the monitor lock for all of

doc/theses/andrew_beach_MMath/features.tex

-                      r5407cdc
+                      r8d66610
 \subparagraph{Raise}
 The raise is the starting point for exception handling. It marks the beginning
 of exception handling by \newterm{raising} an excepion, which passes it to
+of exception handling by raising an excepion, which passes it to
 the EHM.
 Some well known examples include the @throw@ statements of \Cpp and Java and
 the \codePy{raise} statement from Python. In real systems a raise may preform
+some other work (such as memory management) but for the purposes of this
 overview that can be ignored.
+the \code{Python}{raise} statement from Python. In real systems a raise may
+preform some other work (such as memory management) but for the
+purposes of this overview that can be ignored.
 \subparagraph{Handle}
 …
 A handler labelled with any given exception can handle exceptions of that
 type or any child type of that exception. The root of the exception hierarchy
 (here \codeC{exception}) acts as a catch-all, leaf types catch single types
+(here \code{C}{exception}) acts as a catch-all, leaf types catch single types
 and the exceptions in the middle can be used to catch different groups of
 related exceptions.
 …
 between different sub-hierarchies.
 This design is used in \CFA even though it is not a object-orientated
 language using different tools to create the hierarchy.
+language; so different tools are used to create the hierarchy.
 % Could I cite the rational for the Python IO exception rework?
 …
 \section{Virtuals}
 Virtual types and casts are not part of \CFA's EHM nor are they required for
+any EHM. But \CFA uses a hierarchial system of exceptions and this feature
+is leveraged to create that.
+% Maybe talk about why the virtual system is so minimal.
+% Created for but not a part of the exception system.
+any EHM.
+However the \CFA uses a hierarchy built with the virtual system as the basis
+for exceptions and exception matching.
+The virtual system would have ideally been part of \CFA before the work
+on exception handling began, but unfortunately it was not.
+Because of this only the features and framework needed for the EHM were
+designed and implemented. Other features were considered to ensure that
+the structure could accomidate other desirable features but they were not
+implemented.
+The rest of this section will only discuss the finalized portion of the
+virtual system.
 The virtual system supports multiple ``trees" of types. Each tree is
 …
 It is important to note that these are virtual members, not virtual methods
 of object-orientated programming, and can be of any type.
+However, since \CFA has function pointers and they are allowed, virtual
+members can be used to mimic virtual methods.
+\CFA still supports virtual methods as a special case of virtual members.
+Function pointers that take a pointer to the virtual type will be modified
+with each level of inheritance so that refers to the new type.
+This means an object can always be passed to a function in its virtual table
+as if it were a method.
 Each virtual type has a unique id.
 …
 While much of the virtual infrastructure is created, it is currently only used
 internally for exception handling. The only user-level feature is the virtual
 cast, which is the same as the \Cpp \lstinline[language=C++]|dynamic_cast|.
+cast, which is the same as the \Cpp \code{C++}{dynamic_cast}.
 \label{p:VirtualCast}
 \begin{cfa}
 …
 \begin{cfa}
 trait is_exception(exceptT &, virtualT &) {
         virtualT const & get_exception_vtable(exceptT *);
+        // Numerous imaginary assertions.
 };
 \end{cfa}
 The trait is defined over two types, the exception type and the virtual table
+type. This should be one-to-one: each exception type has only one virtual
+table type and vice versa. The only assertion in the trait is
+@get_exception_vtable@, which takes a pointer of the exception type and
+returns a reference to the virtual table type instance.
+% TODO: This section, and all references to get_exception_vtable, are
+% out-of-data. Perhaps wait until the update is finished before rewriting it.
+The function @get_exception_vtable@ is actually a constant function.
+Regardless of the value passed in (including the null pointer) it should
+return a reference to the virtual table instance for that type.
+The reason it is a function instead of a constant is that it make type
+annotations easier to write as you can use the exception type instead of the
+virtual table type; which usually has a mangled name.
+% Also \CFA's trait system handles functions better than constants and doing
+% it this way reduce the amount of boiler plate we need.
+type. Each exception type should have but a single virtual table type.
+Now there are no actual assertions in this trait because the trait system
+actually can't express them (adding such assertions would be part of
+completing the virtual system). The imaginary assertions would probably come
+from a trait defined by the virtual system, and state that the exception type
+is a virtual type, is a decendent of @exception_t@ (the base exception type)
+and note its virtual table type.
 % I did have a note about how it is the programmer's responsibility to make
 …
 Both traits ensure a pair of types are an exception type and its virtual table
 and defines one of the two default handlers. The default handlers are used
 as fallbacks and are discussed in detail in \VRef{s:ExceptionHandling}.
+as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
 However, all three of these traits can be tricky to use directly.
 …
 for particular exception type.
 The global default termination handler performs a cancellation
 \see{\VRef{s:Cancellation}} on the current stack with the copied exception.
+(see \vref{s:Cancellation}) on the current stack with the copied exception.
 \subsection{Resumption}
 …
 \subsubsection{Resumption Marking}
+\label{s:ResumptionMarking}
 A key difference between resumption and termination is that resumption does
 not unwind the stack. A side effect that is that when a handler is matched
 …
 The symmetry between resumption termination is why this pattern was picked.
 Other patterns, such as marking just the handlers that caught, also work but
 lack the symmetry means there are less rules to remember.
+lack the symmetry means there are more rules to remember.
 \section{Conditional Catch}
 …
 \end{cfa}
 If there are further handlers after this handler only the first version will
 check them. If multiple handlers on a single try block could handle the same
 exception the translations get more complex but they are equivilantly
+check them. If multiple handlers on a single try block that could handle the
+same exception the translations get more complex but they are equivilantly
 powerful.
 …
 and the current stack is
 unwound. After that it depends one which stack is being cancelled.
+\begin{description}
 \item[Main Stack:]
+\paragraph{Main Stack}
 The main stack is the one used by the program main at the start of execution,
 and is the only stack in a sequential program.
 …
 to, so it would have be explicitly managed.
 \item[Thread Stack:]
+\paragraph{Thread Stack}
 A thread stack is created for a \CFA @thread@ object or object that satisfies
 the @is_thread@ trait.
 …
 Also you can always add an explicit join if that is the desired behaviour.
 \item[Coroutine Stack:]
+\paragraph{Coroutine Stack}
 A coroutine stack is created for a @coroutine@ object or object that
 satisfies the @is_coroutine@ trait.
 …
 (in terms of coroutine state) called resume on this coroutine, so the message
 is passed to the latter.
-\end{description}

doc/theses/andrew_beach_MMath/future.tex

r5407cdc	r8d66610
110	110	\section{Zero-Cost Try}
111	111	\CFA does not have zero-cost try-statements because the compiler generates C
112		code rather than assembler code ~~\see{\VPageref{p:zero-cost}}~~. When the compiler
	112	code rather than assembler code (see \vpageref{p:zero-cost}). When the compiler
113	113	does create its own assembly (or LLVM byte-code), then zero-cost try-statements
114	114	are possible. The downside of zero-cost try-statements is the LSDA complexity,

doc/theses/andrew_beach_MMath/implement.tex

-                      r5407cdc
+                      r8d66610
 % Virtual table rules. Virtual tables, the pointer to them and the cast.
 While the \CFA virtual system currently has only one public feature, virtual
 cast \see{\VPageref{p:VirtualCast}}, substantial structure is required to
 support it, and provide features for exception handling and the standard
 library.
+cast (see the virtual cast feature \vpageref{p:VirtualCast}),
+substantial structure is required to support it,
+and provide features for exception handling and the standard library.
 \subsection{Virtual Type}
+Virtual types only have one change to their structure, the addition of a
+pointer to the virtual table. This is always the first field so that
+if it is cast to a supertype the field's location is still known.
+This field is set as part of all new generated constructors.
+\todo{They only come as part exceptions and don't work.}
+After the object is created the field is constant.
+However it can be read from, internally it is just a regular field called
+@virtual_table@. Dereferencing it gives the virtual table and access to the
+type's virtual members.
+Virtual types only have one change to their structure: the addition of a
+pointer to the virtual table, which is called the \emph{virtual-table pointer}.
+Internally, the field is called @virtual_table@.
+The field is fixed after construction. It is always the first field in the
+structure so that its location is always known.
+\todo{Talk about constructors for virtual types (after they are working).}
+This is what binds an instance of a virtual type to a virtual table. This
+pointer can be used as an identity check. It can also be used to access the
+virtual table and the virtual members there.
+\subsection{Type Id}
+Every virtual type has a unique id.
+Type ids can be compared for equality (the types reperented are the same)
+or used to access the type's type information.
+The type information currently is only the parent's type id or, if the
+type has no parent, zero.
+The id's are implemented as pointers to the type's type information instance.
+Derefencing the pointer gets the type information.
+By going back-and-forth between the type id and
+the type info one can find every ancestor of a virtual type.
+It also pushes the issue of creating a unique value (for
+the type id) to the problem of creating a unique instance (for type
+information) which the linker can solve.
+Advanced linker support is required because there is no place that appears
+only once to attach the type information to. There should be one structure
+definition but it is included in multiple translation units. Each virtual
+table definition should be unique but there are an arbitrary number of thoses.
+So the special section prefix \texttt{.gnu.linkonce} is used.
+With a unique suffix (making the entire section name unique) the linker will
+remove multiple definition making sure only one version exists after linking.
+Then it is just a matter of making sure there is a unique name for each type.
+This is done in three phases.
+The first phase is to generate a new structure definition to store the type
+information. The layout is the same in each case, just the parent's type id,
+but the types are changed.
+The structure's name is change, it is based off the virtual type's name, and
+the type of the parent's type id.
+If the virtual type is polymorphic then the type information structure is
+polymorphic as well, with the same polymorphic arguments.
+The second phase is to generate an instance of the type information with a
+almost unique name, generated by mangling the virtual type name.
+The third phase is implicit with \CFA's overloading scheme. \CFA mangles
+names with type information so that all of the symbols exported to the linker
+are unique even if in \CFA code they are the same. Having two declarations
+with the same name and same type is forbidden because it is impossible for
+overload resolution to pick between them. This is why a unique type is
+generated for each virtual type.
+Polymorphic information is included in this mangling so polymorphic
+types will have seperate instances for each set of polymorphic arguments.
+\begin{cfa}
+struct TYPE_ID_TYPE {
+        PARENT_ID_TYPE const * parent;
+};
+__attribute__((cfa_linkonce))
+TYPE_ID_TYPE const TYPE_ID_NAME = {
+        &PARENT_ID_NAME,
+};
+\end{cfa}
+\subsubsection{cfa\_linkonce Attribute}
+Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}.
+This attribute can be put on an object or function definition
+(any global declaration with a name and a type).
+This allows you to define that object or function multiple times.
+All definitions should have the link-once attribute on them and all should
+be identical.
+The simplist way to use it is to put a definition in a header where the
+forward declaration would usually go.
+This is how it is used for type-id instances. There was is no unique location
+associated with a type except for the type definition which is in a header.
+This allows the unique type-id object to be generated there.
+Internally @cfa_linkonce@ removes all @section@ attributes
+from the declaration (as well as itself) and replaces them with
+@section(".gnu.linkonce.NAME")@ where \texttt{NAME} is replaced by the
+mangled name of the object.
+The prefix \texttt{.gnu.linkonce} in section names is recognized by the
+linker. If two of these sections with the same name, including everything
+that comes after the special prefix, then only one will be used and the other
+will be discarded.
 \subsection{Virtual Table}
+Every time a virtual type is defined the new virtual table type must also be
+defined.
+The unique instance is important because the address of the virtual table
+instance is used as the identifier for the virtual type. So a pointer to the
+virtual table and the ID for the virtual type are interchangable.
+\todo{Unique instances might be going so we will have to talk about the new
+system instead.}
+The first step in putting it all together is to create the virtual table type.
+The virtual table type is just a structure and can be described in terms of
+its fields. The first field is always the parent type ID (or a pointer to
+the parent virtual table) or 0 (the null pointer).
+Next are other fields on the parent virtual table are repeated.
+Finally are the fields used to store any new virtual members of the new
+The virtual type
+The virtual system is accessed through a private constant field inserted at the
+beginning of every virtual type, called the virtual-table pointer. This field
+points at a type's virtual table and is assigned during the object's
+construction. The address of a virtual table acts as the unique identifier for
+the virtual type, and the first field of a virtual table is a pointer to the
+parent virtual-table or @0p@. The remaining fields are duplicated from the
+parent tables in this type's inheritance chain, followed by any fields this type
+introduces. Parent fields are duplicated so they can be changed (all virtual
+members are overridable), so that references to the dispatched type
+are replaced with the current virtual type.
+% These are always taken by pointer or reference.
+% Simple ascii diragram:
+\begin{verbatim}
+parent_pointer  \
+parent_field0   |
+...             | Same layout as parent.
+parent_fieldN   /
+Each virtual type has a virtual table type that stores its type id and
+virtual members.
+Each virtual type instance is bound to a table instance that is filled with
+the values of virtual members.
+Both the layout of the fields and their value are decided by the rules given
+below.
+The layout always comes in three parts.
+The first section is just the type id at the head of the table. It is always
+there to ensure that
+The second section are all the virtual members of the parent, in the same
+order as they appear in the parent's virtual table. Note that the type may
+change slightly as references to the ``this" will change. This is limited to
+inside pointers/references and via function pointers so that the size (and
+hence the offsets) are the same.
+The third section is similar to the second except that it is the new virtual
+members introduced at this level in the hierarchy.
+\begin{figure}
+\begin{cfa}
+type_id
+parent_field0
+...
+parent_fieldN
 child_field0
 ...
 child_fieldN
+\end{verbatim}
+\todo{Refine the diagram}
+% For each virtual type, a virtual table is constructed. This is both a new type
+% and an instance of that type. Other instances of the type could be created
+% but the system doesn't use them. So this section will go over the creation of
+% the type and the instance.
+A virtual table is created when the virtual type is created. The name of the
+type is created by mangling the name of the base type. The name of the instance
+is also generated by name mangling. The fields are initialized automatically.
+The parent field is initialized by getting the type of the parent field and
+using that to calculate the mangled name of the parent's virtual table type.
+There are two special fields that are included like normal fields but have
+special initialization rules: the @size@ field is the type's size and is
+initialized with a @sizeof@ expression, the @align@ field is the type's
+alignment and uses an @alignof@ expression. The remaining fields are resolved
+to a name matching the field's name and type using the normal visibility and
+overload resolution rules of the type system.
+These operations are split up into several groups depending on where they take
+place which varies for monomorphic and polymorphic types. The first devision is
+between the declarations and the definitions. Declarations, such as a function
+signature or a aggregate's name, must always be visible but may be repeated in
+the form of forward declarations in headers. Definitions, such as function
+bodies and a aggregate's layout, can be separately compiled but must occur
+exactly once in a source file.
+\begin{sloppypar}
+The declarations include the virtual type definition and forward declarations
+of the virtual table instance, constructor, message function and
+@get_exception_vtable@. The definition includes the storage and initialization
+of the virtual table instance and the bodies of the three functions.
+\end{sloppypar}
+Monomorphic instances put all of these two groups in one place each.
+Polymorphic instances also split out the core declarations and definitions from
+the per-instance information. The virtual table type and most of the functions
+are polymorphic so they are all part of the core. The virtual table instance
+and the @get_exception_vtable@ function.
+\begin{sloppypar}
+\end{cfa}
+\caption{Virtual Table Layout}
+\label{f:VirtualTableLayout}
+\todo*{Improve the Virtual Table Layout diagram.}
+\end{figure}
+The first and second sections together mean that every virtual table has a
+prefix that has the same layout and types as its parent virtual table.
+This, combined with the fixed offset to the virtual table pointer, means that
+for any virtual type it doesn't matter if we have it or any of its
+descendants, it is still always safe to access the virtual table through
+the virtual table pointer.
+From there it is safe to check the type id to identify the exact type of the
+underlying object, access any of the virtual members and pass the object to
+any of the method-like virtual members.
+When a virtual table is declared the user decides where to declare it and its
+name. The initialization of the virtual table is entirely automatic based on
+the context of the declaration.
+The type id is always fixed, each virtual table type will always have one
+exactly one possible type id.
+The virtual members are usually filled in by resolution. The best match for
+a given name and type at the declaration site is filled in.
+There are two exceptions to that rule: the @size@ field is the type's size
+and is set to the result of a @sizeof@ expression, the @align@ field is the
+type's alignment and similarly uses an @alignof@ expression.
+\subsubsection{Concurrency Integration}
 Coroutines and threads need instances of @CoroutineCancelled@ and
 @ThreadCancelled@ respectively to use all of their functionality. When a new
 …
 the instance is created as well. The definition of the virtual table is created
 at the definition of the main function.
+\end{sloppypar}
+\begin{figure}
+\begin{cfa}
+coroutine Example {
+        // fields
+}
+\end{cfa}
+\begin{cfa}
+__attribute__((cfa_linkonce))
+struct __cfatid_struct_CoroutineCancelled(Example)
+                __cfatid_CoroutineCancelled = {
+        &EXCEPTION_TYPE_ID,
+};
+extern CoroutineCancelled_vtable _default_vtable_object_declaration;
+extern CoroutineCancelled_vtable & _default_vtable;
+\end{cfa}
+\begin{cfa}
+void main(Example & this) {
+        // body
+}
+\end{cfa}
+\begin{cfa}
+CoroutineCancelled_vtable _default_vtable_object_declaration = {
+        __cfatid_CoroutineCancelled,
+        // Virtual member initialization.
+};
+CoroutineCancelled_vtable & _default_vtable =
+        &_default_vtable_object_declaration;
+\end{cfa}
+\caption{Concurrency Transformations}
+\label{f:ConcurrencyTransformations}
+\end{figure}
+\todo{Improve Concurrency Transformations figure.}
 \subsection{Virtual Cast}
 …
 % The C-cast is just to make sure the generated code is correct so the rest of
 % the section is about that function.
+The function is
+The function is implemented in the standard library and has the following
+signature:
 \begin{cfa}
 void * __cfa__virtual_cast(
+        struct __cfa__parent_vtable const * parent,
+        struct __cfa__parent_vtable const * const * child );
+\end{cfa}
+and it is implemented in the standard library. The structure reperents the
+head of a vtable which is the pointer to the parent virtual table. The
+@parent@ points directly at the parent type virtual table while the @child@
+points at the object of the (possibe) child type.
+In terms of the virtual cast expression, @parent@ comes from looking up the
+type being cast to and @child@ is the result of the expression being cast.
+Because the complier outputs C code, some type C type casts are also used.
+The last bit of glue is an map that saves every virtual type the compiler
+sees. This is used to check the type used in a virtual cast is a virtual
+type and to get its virtual table.
+(It also checks for conflicting definitions.)
+Inside the function it is a simple conditional. If the type repersented by
+@parent@ is or is an ancestor of the type repersented by @*child@ (it
+requires one more level of derefence to pass through the object) then @child@
+is returned, otherwise the null pointer is returned.
+The check itself is preformed is a simple linear search. If the child
+virtual table or any of its ancestors (which are retreved through the first
+field of every virtual table) are the same as the parent virtual table then
+the cast succeeds.
+        struct __cfavir_type_td parent,
+        struct __cfavir_type_id const * child );
+\end{cfa}
+The type id of target type of the virtual cast is passed in as @parent@ and
+the cast target is passed in as @child@.
+For C generation both arguments and the result are wrapped with type casts.
+There is also an internal store inside the compiler to make sure that the
+target type is a virtual type.
+% It also checks for conflicting definitions.
+The virtual cast either returns the original pointer as a new type or null.
+So the function just does the parent check and returns the approprate value.
+The parent check is a simple linear search of child's ancestors using the
+type information.
 \section{Exceptions}
 …
 Stack unwinding is the process of removing stack frames (activations) from the
+stack. On function entry and return, unwinding is handled directly by the code
+embedded in the function. Usually, the stack-frame size is known statically
+based on parameter and local variable declarations. For dynamically-sized
+local variables, a runtime computation is necessary to know the frame
+size. Finally, a function's frame-size may change during execution as local
+variables (static or dynamic sized) go in and out of scope.
+stack. On function entry and return, unwinding is handled directly by the
+call/return code embedded in the function.
+In many cases the position of the instruction pointer (relative to parameter
+and local declarations) is enough to know the current size of the stack
+frame.
+Usually, the stack-frame size is known statically based on parameter and
+local variable declarations. Even with dynamic stack-size the information
+to determain how much of the stack has to be removed is still contained
+within the function.
 Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
 bumping the hardware stack-pointer up or down as needed.
+Unwinding across multiple stack frames is more complex because individual stack
+management code associated with each frame is bypassed. That is, the location
+of a function's frame-management code is largely unknown and dispersed
+throughout the function, hence the current frame size managed by that code is
+also unknown. Hence, code unwinding across frames does not have direct
+knowledge about what is on the stack, and hence, how much of the stack needs to
+be removed.
+% At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply
+% move the top of the stack, discarding everything on the stack above a certain
+% point. However this ignores all the cleanup code that should be run when
+% certain sections of the stack are removed (for \CFA these are from destructors
+% and finally clauses) and also requires that the point to which the stack is
+% being unwound is known ahead of time. libunwind is used to address both of
+% these problems.
+Constructing/destructing values on the stack takes longer put in terms of
+figuring out what needs to be done is of similar complexity.
+Unwinding across multiple stack frames is more complex because that
+information is no longer contained within the current function.
+With seperate compilation a function has no way of knowing what its callers
+are so it can't know how large those frames are.
+Without altering the main code path it is also hard to pass that work off
+to the caller.
 The traditional unwinding mechanism for C is implemented by saving a snap-shot
 …
 reseting to a snap-shot of an arbitrary but existing function frame on the
 stack. It is up to the programmer to ensure the snap-shot is valid when it is
+reset, making this unwinding approach fragile with potential errors that are
+difficult to debug because the stack becomes corrupted.
+However, many languages define cleanup actions that must be taken when objects
+are deallocated from the stack or blocks end, such as running a variable's
+destructor or a @try@ statement's @finally@ clause. Handling these mechanisms
+requires walking the stack and checking each stack frame for these potential
+actions.
+For exceptions, it must be possible to walk the stack frames in search of @try@
+statements to match and execute a handler. For termination exceptions, it must
+also be possible to unwind all stack frames from the throw to the matching
+catch, and each of these frames must be checked for cleanup actions. Stack
+walking is where most of the complexity and expense of exception handling
+appears.
+reset and that all required clean-up from the unwound stacks is preformed.
+This approach is fragile and forces a work onto the surounding code.
+With respect to that work forced onto the surounding code,
+many languages define clean-up actions that must be taken when certain
+sections of the stack are removed. Such as when the storage for a variable
+is removed from the stack or when a try statement with a finally clause is
+(conceptually) popped from the stack.
+None of these should be handled by the user, that would contradict the
+intention of these features, so they need to be handled automatically.
+To safely remove sections of the stack the language must be able to find and
+run these clean-up actions even when removing multiple functions unknown at
+the beginning of the unwinding.
 One of the most popular tools for stack management is libunwind, a low-level
 …
 \subsection{libunwind Usage}
 Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
 provides \CC-style stack-unwinding. Its operation is divided into two phases:
+provides \Cpp-style stack-unwinding. Its operation is divided into two phases:
 search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
 stack and decide where unwinding should stop (but no unwinding occurs). The
 …
 LSDA can contain any information but conventionally it is a table with entries
 representing regions of the function and what has to be done there during
 unwinding. These regions are bracketed by the instruction pointer. If the
+unwinding. These regions are bracketed by instruction addresses. If the
 instruction pointer is within a region's start/end, then execution is currently
 executing in that region. Regions are used to mark out the scopes of objects
 …
 The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
+attaches its personality function. However, this
+attaches a personality function to each function.
+In plain C (which \CFA currently compiles down to) this
 flag only handles the cleanup attribute:
-\todo{Peter: What is attached? Andrew: It uses the .cfi\_personality directive
-and that's all I know.}
 \begin{cfa}
 void clean_up( int * var ) { ... }
 int avar __attribute__(( cleanup(clean_up) ));
 \end{cfa}
+which is used on a variable and specifies a function, in this case @clean_up@,
+run when the variable goes out of scope.
+The function is passed a pointer to the object being removed from the stack
+so it can be used to mimic destructors.
+However, this feature cannot be used to mimic @try@ statements as it cannot
+control the unwinding.
+The attribue is used on a variable and specifies a function,
+in this case @clean_up@, run when the variable goes out of scope.
+This is enough to mimic destructors, but not try statements which can effect
+the unwinding.
+To get full unwinding support all of this has to be done directly with
+assembly and assembler directives. Partiularly the cfi directives
+\texttt{.cfi\_lsda} and \texttt{.cfi\_personality}.
 \subsection{Personality Functions}
 …
 \end{lstlisting}
 The @action@ argument is a bitmask of possible actions:
 \begin{enumerate}
+\begin{enumerate}[topsep=5pt]
 \item
 @_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
 …
 @_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
 the cleanup phase and uses a different means to decide when to stop
 \see{\VRef{s:ForcedUnwind}}.
+(see \vref{s:ForcedUnwind}).
 \end{enumerate}
 The @exception_class@ argument is a copy of the
+\lstinline[language=C]|exception|'s @exception_class@ field.
+The \lstinline[language=C]|exception| argument is a pointer to the user
+provided storage object. It has two public fields, the exception class, which
+is actually just a number, identifying the exception handling mechanism that
+created it, and the cleanup function. The cleanup function is called if
+required by the exception.
+\code{C}{exception}'s @exception_class@ field.
+This a number that identifies the exception handling mechanism that created
+the
+The \code{C}{exception} argument is a pointer to the user
+provided storage object. It has two public fields: the @exception_class@,
+which is described above, and the @exception_cleanup@ function.
+The clean-up function is used by the EHM to clean-up the exception if it
+should need to be freed at an unusual time, it takes an argument that says
+why it had to be cleaned up.
 The @context@ argument is a pointer to an opaque type passed to helper
 …
 that can be passed several places in libunwind. It includes a number of
 messages for special cases (some of which should never be used by the
 personality function) and error codes but unless otherwise noted the
+personality function) and error codes. However, unless otherwise noted, the
 personality function should always return @_URC_CONTINUE_UNWIND@.
 …
 @_URC_END_OF_STACK@.
 Second, when a handler is matched, raise exception continues onto the cleanup
 phase.
+Second, when a handler is matched, raise exception moves to the clean-up
+phase and walks the stack a second time.
 Once again, it calls the personality functions of each stack frame from newest
 to oldest. This pass stops at the stack frame containing the matching handler.
 …
 Forced Unwind is the other central function in libunwind.
 \begin{cfa}
 _Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *,
+_Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *,
         _Unwind_Stop_Fn, void *);
 \end{cfa}
 …
 Each stack must have its own exception context. In a sequential \CFA program,
 there is only one stack with a single global exception-context. However, when
 the library @libcfathread@ is linked, there are multiple stacks where each
+the library @libcfathread@ is linked, there are multiple stacks and each
 needs its own exception context.
 General access to the exception context is provided by function
+The exception context should be retrieved by calling the function
 @this_exception_context@. For sequential execution, this function is defined as
 a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
 …
 The sequential @this_exception_context@ returns a hard-coded pointer to the
 global execption context.
+global exception context.
 The concurrent version adds the exception context to the data stored at the
 base of each stack. When @this_exception_context@ is called it retrieves the
+base of each stack. When @this_exception_context@ is called, it retrieves the
 active stack and returns the address of the context saved there.
 …
 % catches. Talk about GCC nested functions.
+Termination exceptions use libunwind heavily because it matches the intended
 use from \CC exceptions closely. The main complication for \CFA is that the
+\CFA termination exceptions use libunwind heavily because they match \Cpp
+\Cpp exceptions closely. The main complication for \CFA is that the
 compiler generates C code, making it very difficult to generate the assembly to
 form the LSDA for try blocks or destructors.
 …
 per-exception storage.
+[Quick ASCII diagram to get started.]
+\begin{figure}
 \begin{verbatim}
 Fixed Header  | _Unwind_Exception   <- pointer target
 …
               V ...
 \end{verbatim}
+Exceptions are stored in variable-sized blocks.
+The first component is a fixed sized data structure that contains the
+\caption{Exception Layout}
+\label{f:ExceptionLayout}
+\end{figure}
+\todo*{Convert the exception layout to an actual diagram.}
+Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}).
+The first component is a fixed-sized data structure that contains the
 information for libunwind and the exception system. The second component is an
 area of memory big enough to store the exception. Macros with pointer arthritic
 …
 @_Unwind_Exception@ to the entire node.
+All of these nodes are linked together in a list, one list per stack, with the
+Multipe exceptions can exist at the same time because exceptions can be
+raised inside handlers, destructors and finally blocks.
+Figure~\vref{f:MultipleExceptions} shows a program that has multiple
+exceptions active at one time.
+Each time an exception is thrown and caught the stack unwinds and the finally
+clause runs. This will throw another exception (until @num_exceptions@ gets
+high enough) which must be allocated. The previous exceptions may not be
+freed because the handler/catch clause has not been run.
+So the EHM must keep them alive while it allocates exceptions for new throws.
+\begin{figure}
+\centering
+% Andrew: Figure out what these do and give them better names.
+\newsavebox{\myboxA}
+\newsavebox{\myboxB}
+\begin{lrbox}{\myboxA}
+\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
+unsigned num_exceptions = 0;
+void throws() {
+    try {
+        try {
+            ++num_exceptions;
+            throw (Example){table};
+        } finally {
+            if (num_exceptions < 3) {
+                throws();
+            }
+        }
+    } catch (exception_t *) {
+        --num_exceptions;
+    }
+}
+int main() {
+    throws();
+}
+\end{lstlisting}
+\end{lrbox}
+\begin{lrbox}{\myboxB}
+\begin{lstlisting}
+\end{lstlisting}
+\end{lrbox}
+{\usebox\myboxA}
+\hspace{25pt}
+{\usebox\myboxB}
+\caption{Multiple Exceptions}
+\label{f:MultipleExceptions}
+\end{figure}
+\todo*{Work on multiple exceptions code sample.}
+All exceptions are stored in nodes which are then linked together in lists,
+one list per stack, with the
 list head stored in the exception context. Within each linked list, the most
 recently thrown exception is at the head followed by older thrown
 …
 exception, the copy function, and the free function, so they are specific to an
 exception type. The size and copy function are used immediately to copy an
 exception into managed memory. After the exception is handled the free function
+is used to clean up the exception and then the entire node is passed to free
 so the memory can be given back to the heap.
+exception into managed memory. After the exception is handled, the free
+function is used to clean up the exception and then the entire node is
+passed to free so the memory can be given back to the heap.
 \subsection{Try Statements and Catch Clauses}
 …
 calls them.
 Because this function is known and fixed (and not an arbitrary function that
 happens to contain a try statement) this means the LSDA can be generated ahead
+happens to contain a try statement), the LSDA can be generated ahead
 of time.
 Both the LSDA and the personality function are set ahead of time using
+embedded assembly. This is handcrafted using C @asm@ statements and contains
+embedded assembly. This assembly code is handcrafted using C @asm@ statements
+and contains
 enough information for the single try statement the function repersents.
 …
 nested functions and all other functions besides @__cfaehm_try_terminate@ in
 \CFA use the GCC personality function and the @-fexceptions@ flag to generate
+the LSDA. This allows destructors to be implemented with the cleanup attribute.
+the LSDA.
+Using this pattern, \CFA implements destructors with the cleanup attribute.
+\begin{figure}
+\begin{cfa}
+try {
+        // TRY BLOCK
+} catch (Exception1 * name1 ; check(name1)) {
+        // CATCH BLOCK 1
+} catch (Exception2 * name2) {
+        // CATCH BLOCK 2
+}
+\end{cfa}
+\begin{cfa}
+void try(void) {
+        // TRY BLOCK
+}
+int match(exception_t * __exception_inst) {
+        {
+                Exception1 * name1;
+                if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) {
+                        return 1;
+                }
+        }
+        {
+                Exception2 * name2;
+                if (name2 = (virtual Exception2 *)__exception_inst) {
+                        return 2;
+                }
+        }
+        return 0;
+}
+void catch(exception_t * __exception_inst, int __handler_index) {
+        switch (__handler_index) {
+        case 1:
+        {
+                Exception1 * name1 = (virtual Exception1 *)__exception_inst;
+                // CATCH BLOCK 1
+        }
+        return;
+        case 2:
+        {
+                Exception2 * name2 = (virtual Exception2 *)__exception_inst;
+                // CATCH BLOCK 2
+        }
+        return;
+        }
+}
+{
+        __cfaehm_try_terminate(try, catch, match);
+}
+\end{cfa}
+\caption{Termination Transformation}
+\label{f:TerminationTransformation}
+\todo*{Improve (compress?) Termination Transformations.}
+\end{figure}
 \section{Resumption}
 % The stack-local data, the linked list of nodes.
+Resumption simple to implement because there is no stack unwinding. The
+resumption raise uses a list of nodes for its stack traversal. The head of the
+list is stored in the exception context. The nodes in the list have a pointer
+to the next node and a pointer to the handler function.
+A resumption raise traverses this list. At each node the handler function is
+called, passing the exception by pointer. It returns true if the exception is
+handled and false otherwise.
+The handler function does both the matching and handling. It computes the
+condition of each @catchResume@ in top-to-bottom order, until it finds a
+handler that matches. If no handler matches then the function returns
+false. Otherwise the matching handler is run; if it completes successfully, the
+function returns true. Rethrowing, through the @throwResume;@ statement,
+causes the function to return true.
+Resumption simpler to implement than termination
+because there is no stack unwinding.
+Instead of storing the data in a special area using assembly,
+there is just a linked list of possible handlers for each stack,
+with each node on the list reperenting a try statement on the stack.
+The head of the list is stored in the exception context.
+The nodes are stored in order, with the more recent try statements closer
+to the head of the list.
+Instead of traversing the stack resumption handling traverses the list.
+At each node the EHM checks to see if the try statement the node repersents
+can handle the exception. If it can, then the exception is handled and
+the operation finishes, otherwise the search continues to the next node.
+If the search reaches the end of the list without finding a try statement
+that can handle the exception the default handler is executed and the
+operation finishes.
+In each node is a handler function which does most of the work there.
+The handler function is passed the raised the exception and returns true
+if the exception is handled and false if it cannot be handled here.
+For each @catchResume@ clause the handler function will:
+check to see if the raised exception is a descendant type of the declared
+exception type, if it is and there is a conditional expression then it will
+run the test, if both checks pass the handling code for the clause is run
+and the function returns true, otherwise it moves onto the next clause.
+If this is the last @catchResume@ clause then instead of moving onto
+the next clause the function returns false as no handler could be found.
+\begin{figure}
+\begin{cfa}
+try {
+        // TRY BLOCK
+} catchResume (Exception1 * name1 ; check(name1)) {
+        // CATCH BLOCK 1
+} catchResume (Exception2 * name2) {
+        // CATCH BLOCK 2
+}
+\end{cfa}
+\begin{cfa}
+bool handle(exception_t * __exception_inst) {
+        {
+                Exception1 * name1;
+                if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) {
+                        // CATCH BLOCK 1
+                        return 1;
+                }
+        }
+        {
+                Exception2 * name2;
+                if (name2 = (virtual Exception2 *)__exception_inst) {
+                        // CATCH BLOCK 2
+                        return 2;
+                }
+        }
+        return false;
+}
+struct __try_resume_node __resume_node
+        __attribute__((cleanup( __cfaehm_try_resume_cleanup )));
+__cfaehm_try_resume_setup( &__resume_node, handler );
+\end{cfa}
+\caption{Resumption Transformation}
+\label{f:ResumptionTransformation}
+\todo*{Improve (compress?) Resumption Transformations.}
+\end{figure}
 % Recursive Resumption Stuff:
+Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack
+Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
+the stack
 already examined, is accomplished by updating the front of the list as the
 search continues. Before the handler at a node is called the head of the list
+search continues. Before the handler at a node is called, the head of the list
 is updated to the next node of the current node. After the search is complete,
 successful or not, the head of the list is reset.
 …
 stack -- the first one points over all the checked handlers -- and the ordering
 is maintained.
+\begin{figure}
+\begin{minipage}[l][][b]{0,2\textwidth}
+\begin{verbatim}
+  X <-
+  |
+  V
+  X
+  |
+  V
+  X
+\end{verbatim}
+Initial State
+\end{minipage}
+\begin{minipage}[l][][b]{0,2\textwidth}
+\begin{verbatim}
+  X
+  |
+  V
+  X <-
+  |
+  V
+  X
+\end{verbatim}
+Handler Found
+\end{minipage}
+\begin{minipage}[l][][b]{0,2\textwidth}
+\begin{verbatim}
+  X <-
+ /
+/ X
+| |
+\ V
+  X
+  |
+  V
+  X
+\end{verbatim}
+Try Block Added
+\end{minipage}
+\begin{minipage}[l][][b]{0,2\textwidth}
+\begin{verbatim}
+  X <-
+  |
+  V
+  X
+  |
+  V
+  X
+\end{verbatim}
+Handler Done
+\end{minipage}
+\caption{Resumption Marking}
+\label{f:ResumptionMarking}
+\todo*{Convert Resumption Marking into a line figure.}
+\end{figure}
 \label{p:zero-cost}
 …
 \section{Finally}
 % Uses destructors and GCC nested functions.
+Finally clauses is placed into a GCC nested-function with a unique name, and no
+arguments or return values. This nested function is then set as the cleanup
+A finally clause is placed into a GCC nested-function with a unique name,
+and no arguments or return values.
+This nested function is then set as the cleanup
 function of an empty object that is declared at the beginning of a block placed
 around the context of the associated @try@ statement.
 The rest is handled by GCC. The try block and all handlers are inside the
+The rest is handled by GCC. The try block and all handlers are inside this
 block. At completion, control exits the block and the empty object is cleaned
 up, which runs the function that contains the finally code.
 …
 Cancellation also uses libunwind to do its stack traversal and unwinding,
 however it uses a different primary function @_Unwind_ForcedUnwind@. Details
 of its interface can be found in the \VRef{s:ForcedUnwind}.
+however it uses a different primary function: @_Unwind_ForcedUnwind@. Details
+of its interface can be found in the Section~\vref{s:ForcedUnwind}.
 The first step of cancellation is to find the cancelled stack and its type:
 …
 pointer and the current thread pointer, and every thread stores a pointer to
 its main coroutine and the coroutine it is currently executing.
+So if the active thread's main and current coroutine are the same. If they
 are then the current stack is a thread stack, otherwise it is a coroutine
+stack. If it is a thread stack then an equality check with the stored main
+thread pointer and current thread pointer is enough to tell if the current
 thread is the main thread or not.
+\todo*{Consider adding a description of how threads are coroutines.}
+If a the current thread's main and current coroutines are the same then the
+current stack is a thread stack. Furthermore it is easy to compare the
+current thread to the main thread to see if they are the same. And if this
+is not a thread stack then it must be a coroutine stack.
 However, if the threading library is not linked, the sequential execution is on
 …
 Regardless of how the stack is chosen, the stop function and parameter are
 passed to the forced-unwind function. The general pattern of all three stop
 functions is the same: they continue unwinding until the end of stack when they
 do there primary work.
+functions is the same: they continue unwinding until the end of stack and
+then preform their transfer.
 For main stack cancellation, the transfer is just a program abort.

doc/theses/andrew_beach_MMath/uw-ethesis.tex

-                      r5407cdc
+                      r8d66610
 % Tip: Photographs should be cropped and compressed so as not to be too large.
-% To create a PDF output that is optimized for double-sided printing:
-% 1) comment-out the \documentclass statement in the preamble below, and
-%    un-comment the second \documentclass line.
-% 2) change the value assigned below to the boolean variable "PrintVersion"
-%    from "false" to "true".
 % ======================================================================
 %   D O C U M E N T   P R E A M B L E
 …
+}
+% Some LaTeX commands I define for my own nomenclature.
+% If you have to, it's easier to make changes to nomenclature once here than
+% in a million places throughout your thesis!
+\newcommand{\package}[1]{\textbf{#1}} % package names in bold text
+\newcommand{\cmmd}[1]{\textbackslash\texttt{#1}} % command name in tt font
+\newcommand{\href}[1]{#1} % does nothing, but defines the command so the
+% print-optimized version will ignore \href tags (redefined by hyperref pkg).
+% Anything defined here may be redefined by packages added below...
+% Does nothing, ignores \href tags (redefined by hyperref package).
+\newcommand{\href}[1]{#1}
 % For a nomenclature (optional; available from ctan.org)
 …
 % Removes large sections of the document.
 \usepackage{comment}
+% Adds todos (Must be included after comment.)
+\usepackage{todonotes}
+% Adds todo commands.
+\usepackage{todo}
+% cfa macros used in the document
+\usepackage{cfalab}
+% allow global and individual modification of spacing
+\usepackage{enumitem}
+% Improved reference tools.
+\usepackage[nospace]{varioref}
 % Hyperlinks make it very easy to navigate an electronic document.
 …
 % Exception to the rule of hyperref being the last add-on package
 \usepackage[automake,toc,abbreviations]{glossaries-extra}
+\usepackage[toc,abbreviations]{glossaries-extra}
 % If glossaries-extra is not in your LaTeX distribution, get it from CTAN
 % (http://ctan.org/pkg/glossaries-extra), although it's supposed to be in
 …
 \makeglossaries
+% cfa macros used in the document
+%\usepackage{cfalab}
+% I'm going to bring back eventually.
+\makeatletter
+% Combines all \CC* commands:
+\newrobustcmd*\Cpp[1][\xspace]{\cfalab@Cpp#1}
+\newcommand\cfalab@Cpp{C\kern-.1em\hbox{+\kern-.25em+}}
+% Optional arguments do not work with pdf string. (Some fix-up required.)
+\pdfstringdefDisableCommands{\def\Cpp{C++}}
+% Wrappers for inline code snippits.
+\newrobustcmd*\codeCFA[1]{\lstinline[language=CFA]{#1}}
+\newrobustcmd*\codeC[1]{\lstinline[language=C]{#1}}
+\newrobustcmd*\codeCpp[1]{\lstinline[language=C++]{#1}}
+\newrobustcmd*\codePy[1]{\lstinline[language=Python]{#1}}
+% Colour text, formatted in LaTeX style instead of TeX style.
+\newcommand*\colour[2]{{\color{#1}#2}}
+\makeatother
+\input{common}
+% CFA code-style for all languages
+\CFAStyle
+% CFA default lnaguage
+\lstset{language=CFA,basicstyle=\linespread{0.9}\tt}
+% listings package configuation:
+\lstMakeShortInline@
+\lstset{language=CFA,style=cfacommon,basicstyle=\linespread{0.9}\tt}
+\lstset{moredelim=**[is][\protect\color{red}]{@}{@}}
 % Annotations from Peter:
 \newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
 …
 % Tip: Putting each sentence on a new line is a way to simplify later editing.
 %----------------------------------------------------------------------
+\input{intro}
 \input{existing}
 \input{features}
 \input{implement}
-%\input{unwinding}
 \input{future}
 …
 \phantomsection         % allows hyperref to link to the correct page
+\todos
 %----------------------------------------------------------------------
 \end{document} % end of logical document

doc/theses/mubeen_zulfiqar_MMath/AllocDS1.fig

-                      r5407cdc
+                      r8d66610
 -2
 2
 4950 1275 5250 1425
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5025 1350 20 20 5025 1350 5045 1350
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5100 1350 20 20 5100 1350 5120 1350
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 5175 1350 20 20 5175 1350 5195 1350
+4200 1575 4500 1725
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4275 1650 20 20 4275 1650 4295 1650
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4350 1650 20 20 4350 1650 4370 1650
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4425 1650 20 20 4425 1650 4445 1650
 -6
+5700 1950 6000 2100
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5775 2025 20 20 5775 2025 5795 2025
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5850 2025 20 20 5850 2025 5870 2025
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5925 2025 20 20 5925 2025 5945 2025
+-6
+3600 2100 3900 2475
+2850 2475 3150 2850
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2100 3675 2325
+2475 2925 2700
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2325 3900 2325 3900 2475 3600 2475 3600 2325
+2700 3150 2700 3150 2850 2850 2850 2850 2700
 -6
 5100 2100 5400 2475
+4350 2475 4650 2850
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2100 5175 2325
+2475 4425 2700
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2325 5400 2325 5400 2475 5100 2475 5100 2325
+2700 4650 2700 4650 2850 4350 2850 4350 2700
 -6
 4350 2100 4575 2775
+3600 2475 3825 3150
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2100 4425 2325
+2475 3675 2700
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2325 4575 2325 4575 2475 4350 2475 4350 2325
+2700 3825 2700 3825 2850 3600 2850 3600 2700
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2625 4575 2625 4575 2775 4350 2775 4350 2625
+3000 3825 3000 3825 3150 3600 3150 3600 3000
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2400 4425 2625
+2775 3675 3000
 -6
+5700 3225 6000 3375
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5775 3300 20 20 5775 3300 5795 3300
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5850 3300 20 20 5850 3300 5870 3300
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5925 3300 20 20 5925 3300 5945 3300
+4875 3600 5175 3750
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4950 3675 20 20 4950 3675 4970 3675
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5025 3675 20 20 5025 3675 5045 3675
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5100 3675 20 20 5100 3675 5120 3675
+-6
+4875 2325 5175 2475
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4950 2400 20 20 4950 2400 4970 2400
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5025 2400 20 20 5025 2400 5045 2400
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5100 2400 20 20 5100 2400 5120 2400
+-6
+5625 2325 5925 2475
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5700 2400 20 20 5700 2400 5720 2400
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5775 2400 20 20 5775 2400 5795 2400
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5850 2400 20 20 5850 2400 5870 2400
+-6
+5625 3600 5925 3750
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5700 3675 20 20 5700 3675 5720 3675
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5775 3675 20 20 5775 3675 5795 3675
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 5850 3675 20 20 5850 3675 5870 3675
 -6
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1950 3900 1950
+2100 2400 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 3000 2175
+2100 2550 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 3150 2175
+2100 2700 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 3300 2175
+2100 2850 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 3450 2175
+2100 3000 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 3600 2175
+2100 3600 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 3750 2175
+2100 3900 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1950 5400 1950
+2100 4050 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 4350 2175
+2100 4200 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 4500 2175
+2100 4350 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 4650 2175
+2100 4500 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 4800 2175
+1500 3300 1800
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1800 4950 2175
+1500 3600 1800
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5100 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5250 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1200 4050 1500
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1200 4350 1500
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1200 4650 1500
+1500 3900 1800
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 1200 5550 1200 5550 1500 3750 1500 3750 1200
+1500 4800 1500 4800 1800 3000 1800 3000 1500
 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 1350 3375 1800
+1650 2625 2100
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 1350 3300 1800
+1650 2550 2100
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 1350 4800 1800
+1650 4050 2100
 1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 1350 4725 1800
+1650 3975 2100
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 2850 2175
+2100 2100 2550
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+2250 3150 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+2250 4650 2250
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 1800 3900 1800 3900 2175 2700 2175 2700 1800
+2100 3150 2100 3150 2550 1950 2550 1950 2100
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+1800 5400 1800 5400 2175 4200 2175 4200 1800
+2100 4650 2100 4650 2550 3450 2550 3450 2100
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+2100 2250 2550
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+2100 3750 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2100 2775 2325
+2475 2025 2700
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2400 2775 2625
+2775 2025 3000
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2625 2850 2625 2850 2775 2700 2775 2700 2625
+3000 2100 3000 2100 3150 1950 3150 1950 3000
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2325 2850 2325 2850 2475 2700 2475 2700 2325
+2700 2100 2700 2100 2850 1950 2850 1950 2700
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3
 1 1.00 45.00 90.00
 3375 3450 3375 3450 3150
+3750 2700 3750 2700 3525
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 3150 3900 3150 3900 3525 2700 3525 2700 3150
+3525 3150 3525 3150 3900 1950 3900 1950 3525
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3
 1 1.00 45.00 90.00
 3375 4950 3375 4950 3150
+3750 4200 3750 4200 3525
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 3150 5400 3150 5400 3525 4200 3525 4200 3150
+3525 4650 3525 4650 3900 3450 3900 3450 3525
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3
 1 1.00 45.00 90.00
 4350 4950 4350 4950 3900
+4650 4200 4650 4200 4275
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+3900 5400 3900 5400 4575 3900 4575 3900 3900
+2 0 50 -1 0 12 0.0000 2 135 975 2625 2175 free buckets\001
+2 0 50 -1 0 12 0.0000 2 135 435 2625 1950 locks\001
+1 0 50 -1 0 12 0.0000 2 135 1365 4650 1125 N thread buckets\001
+1 0 50 -1 0 12 0.0000 2 180 390 5175 1725 heap\001
+1 0 50 -1 0 12 0.0000 2 180 390 2925 1725 heap\001
+1 0 50 -1 0 12 0.0000 2 180 915 3300 3075 bump alloc\001
+0 0 50 -1 0 12 0.0000 2 135 360 4275 3325 lock\001
+1 0 50 -1 0 12 0.0000 2 180 915 4800 3075 bump alloc\001
+0 0 50 -1 0 12 0.0000 2 135 360 3975 4075 lock\001
+1 0 50 -1 0 12 0.0000 2 135 345 4725 3825 sbrk\001
+0 0 50 -1 0 12 0.0000 2 135 360 2775 3325 lock\001
+2 0 50 -1 0 12 0.0000 2 135 675 2625 2625 free lists\001
+4275 4650 4275 4650 4875 3150 4875 3150 4275
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+2400 3150 2400
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+2400 4650 2400
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+2100 5400 3900
+2 0 50 -1 0 11 0.0000 2 120 300 1875 2250 lock\001
+1 0 50 -1 0 12 0.0000 2 135 1935 3900 1425 N kernel-thread buckets\001
+1 0 50 -1 0 12 0.0000 2 195 810 4425 2025 heap$_2$\001
+1 0 50 -1 0 12 0.0000 2 195 810 2175 2025 heap$_1$\001
+2 0 50 -1 0 11 0.0000 2 120 270 1875 2400 size\001
+2 0 50 -1 0 11 0.0000 2 120 270 1875 2550 free\001
+1 0 50 -1 0 12 0.0000 2 180 825 2550 3450 local pool\001
+0 0 50 -1 0 12 0.0000 2 135 360 3525 3700 lock\001
+0 0 50 -1 0 12 0.0000 2 135 360 3225 4450 lock\001
+2 0 50 -1 0 12 0.0000 2 135 600 1875 3000 free list\001
+1 0 50 -1 0 12 0.0000 2 180 825 4050 3450 local pool\001
+1 0 50 -1 0 12 0.0000 2 180 1455 3900 4200 global pool (sbrk)\001
+0 0 50 -1 0 12 0.0000 2 135 360 2025 3700 lock\001
+1 0 50 -1 0 12 0.0000 2 180 720 6450 3150 free pool\001
+1 0 50 -1 0 12 0.0000 2 180 390 6450 2925 heap\001

doc/theses/mubeen_zulfiqar_MMath/AllocDS2.fig

-                      r5407cdc
+                      r8d66610
 -2
 2
 2850 2025 3150 2175
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 2925 2100 20 20 2925 2100 2945 2100
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3000 2100 20 20 3000 2100 3020 2100
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3075 2100 20 20 3075 2100 3095 2100
+2850 2100 3150 2250
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 2925 2175 20 20 2925 2175 2945 2175
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 3000 2175 20 20 3000 2175 3020 2175
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 3075 2175 20 20 3075 2175 3095 2175
 -6
 4050 2025 4350 2175
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4125 2100 20 20 4125 2100 4145 2100
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4200 2100 20 20 4200 2100 4220 2100
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4275 2100 20 20 4275 2100 4295 2100
+4050 2100 4350 2250
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4125 2175 20 20 4125 2175 4145 2175
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4200 2175 20 20 4200 2175 4220 2175
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4275 2175 20 20 4275 2175 4295 2175
 -6
 4650 2025 4950 2175
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4725 2100 20 20 4725 2100 4745 2100
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4800 2100 20 20 4800 2100 4820 2100
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 4875 2100 20 20 4875 2100 4895 2100
+4650 2100 4950 2250
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4725 2175 20 20 4725 2175 4745 2175
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4800 2175 20 20 4800 2175 4820 2175
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 4875 2175 20 20 4875 2175 4895 2175
 -6
 3450 2025 3750 2175
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3525 2100 20 20 3525 2100 3545 2100
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3600 2100 20 20 3600 2100 3620 2100
 3 0 1 0 0 50 -1 20 0.000 1 0.0000 3675 2100 20 20 3675 2100 3695 2100
+3450 2100 3750 2250
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 3525 2175 20 20 3525 2175 3545 2175
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 3600 2175 20 20 3600 2175 3620 2175
+3 0 1 0 0 50 -1 20 0.000 1 0.0000 3675 2175 20 20 3675 2175 3695 2175
 -6
 3300 2100 3600 2475
+3300 2175 3600 2550
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2100 3375 2325
+2175 3375 2400
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2325 3600 2325 3600 2475 3300 2475 3300 2325
+2400 3600 2400 3600 2550 3300 2550 3300 2400
 -6
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 3150 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 2850 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 4650 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 4950 2250
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 4500 2250
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 5100 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 3450 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 3750 2250
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 3300 2250
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 3900 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5250 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5400 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5550 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5700 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5850 2250
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 2700 2250
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+1 1.00 45.00 90.00
+1275 3375 1575
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+1 1.00 45.00 90.00
+1275 2700 1575
+1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2
+1 1.00 45.00 90.00
+1275 2775 1575
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+1 1.00 45.00 90.00
+1275 5175 1575
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+1 1.00 45.00 90.00
+1275 5625 1575
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
+1 1.00 45.00 90.00
+1275 3750 1575
+1 1 1 0 7 50 -1 -1 4.000 0 0 -1 1 0 2
+1 1.00 45.00 90.00
+1275 3825 1575
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
 1950 6000 1950
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 3150 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 2850 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 4650 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 4950 2175
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 4500 2175
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 5100 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 3450 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 3750 2175
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 3300 2175
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 3900 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5250 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5400 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5550 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5700 2175
+1 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1800 5850 2175
+1 0 3 0 7 50 -1 -1 0.000 0 0 -1 0 0 2
+1725 2700 2175
+2100 6000 2100
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 1800 6000 1800 6000 2175 2700 2175 2700 1800
+1800 6000 1800 6000 2250 2700 2250 2700 1800
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2100 2775 2325
+2175 2775 2400
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2400 2775 2625
+2475 2775 2700
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2625 2850 2625 2850 2775 2700 2775 2700 2625
+2700 2850 2700 2850 2850 2700 2850 2700 2700
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2325 2850 2325 2850 2475 2700 2475 2700 2325
+2400 2850 2400 2850 2550 2700 2550 2700 2400
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 2
 1 1.00 45.00 90.00
 2100 4575 2325
+2175 4575 2400
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
 2325 5025 2325 5025 2475 4500 2475 4500 2325
+2400 5025 2400 5025 2550 4500 2550 4500 2400
 1 0 1 0 7 50 -1 -1 0.000 0 0 -1 1 0 3
 1 1.00 45.00 90.00
 3525 4650 3525 4650 3075
+3525 4650 3525 4650 3150
 2 0 1 0 7 50 -1 -1 0.000 0 0 -1 0 0 5
+3075 5100 3075 5100 3750 3600 3750 3600 3075
+2 0 50 -1 0 12 0.0000 2 135 975 2625 2175 free buckets\001
+2 0 50 -1 0 12 0.0000 2 135 435 2625 1950 locks\001
+3150 5100 3150 5100 3750 3600 3750 3600 3150
+2 0 50 -1 0 11 0.0000 2 120 300 2625 1950 lock\001
 1 0 50 -1 0 10 0.0000 2 150 1155 3000 1725 N$\\times$S$_1$\001
 1 0 50 -1 0 10 0.0000 2 150 1155 3600 1725 N$\\times$S$_2$\001
+1 0 50 -1 0 12 0.0000 2 180 390 4425 1500 heap\001
+2 0 50 -1 0 12 0.0000 2 135 1140 2550 1425 kernel threads\001
+2 0 50 -1 0 11 0.0000 2 120 270 2625 2100 size\001
+2 0 50 -1 0 11 0.0000 2 120 270 2625 2250 free\001
+2 0 50 -1 0 12 0.0000 2 135 600 2625 2700 free list\001
+0 0 50 -1 0 12 0.0000 2 135 360 3675 3325 lock\001
+1 0 50 -1 0 12 0.0000 2 180 1455 4350 3075 global pool (sbrk)\001
 1 0 50 -1 0 10 0.0000 2 150 1110 4800 1725 N$\\times$S$_t$\001
-2 0 50 -1 0 12 0.0000 2 135 675 2625 2625 free lists\001
-0 0 50 -1 0 12 0.0000 2 135 360 3675 3250 lock\001
-1 0 50 -1 0 12 0.0000 2 135 345 4425 3000 sbrk\001
-1 0 50 -1 0 12 0.0000 2 180 390 4425 1500 heap\001

doc/theses/mubeen_zulfiqar_MMath/Makefile

-                      r5407cdc
+                      r8d66610
 .PHONY: all clean
+.PRECIOUS: %.dvi %.ps # do not delete intermediate files
 ### Commands:
 LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD}
 BIBTEX = BIBINPUTS=${BIBLIB} bibtex
 #GLOSSARY=INDEXSTYLE=${BUILD} makeglossaries-lite
+#GLOSSARY = INDEXSTYLE=${BUILD} makeglossaries-lite
 ### Rules and Recipes:
 …
 all: ${DOC}
 ${BUILD}/%.dvi: ${TEXSRC} ${FIGSRC:.fig=.tex} ${BIBSRC} Makefile | ${BUILD}
+${BUILD}/%.dvi: ${TEXSRC} ${FIGSRC:%.fig=%.tex} ${BIBSRC} Makefile | ${BUILD}
         ${LATEX} ${BASE}
         ${BIBTEX} ${BUILD}/${BASE}

doc/theses/mubeen_zulfiqar_MMath/allocator.tex

-                      r5407cdc
+                      r8d66610
+\chapter{Allocator}
+\chapter{Allocator}
+\noindent
+====================
+Writing Points:
+\begin{itemize}
+\item
+Objective of @uHeapLmmm@.
+\item
+Design philosophy.
+\item
+Background and previous design of @uHeapLmmm@.
+\item
+Distributed design of @uHeapLmmm@.
+----- SHOULD WE GIVE IMPLEMENTATION DETAILS HERE? -----
+\PAB{Maybe. There might be an Implementation chapter.}
+\item
+figure.
+\item
+Advantages of distributed design.
+\end{itemize}
+The new features added to @uHeapLmmm@ (incl. @malloc_size@ routine)
+\CFA alloc interface with examples.
+\begin{itemize}
+\item
+Why did we need it?
+\item
+The added benefits.
+\end{itemize}
+----- SHOULD WE GIVE PERFORMANCE AND USABILITY COMPARISON OF DIFFERENT INTERFACES THAT WE TRIED? -----
+\PAB{Often Performance is its own chapter. I added one for now.}
+Performance evaluation using u-benchmark suite.
+\noindent
+====================
 \newpage
 \paragraph{Design 1: Decentralized}
 Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the sbrk area.
+Fixed number of heaps: shard the heap into N heaps each with a bump-area allocated from the @sbrk@ area.
 Kernel threads (KT) are assigned to the N heaps.
 When KTs $\le$ N, the heaps are uncontented.

doc/theses/mubeen_zulfiqar_MMath/background.tex

-                      r5407cdc
+                      r8d66610
 \chapter{Background}
+\noindent
+====================
+Writing Points:
+\begin{itemize}
+\item
+Classification of benchmarks.
+\item
+Literature review of current benchmarks.
+\item
+Features and limitations.
+\item
+Literature review of current memory allocators.
+\item
+Breakdown of memory allocation techniques.
+\item
+Features and limitations.
+\end{itemize}
+\noindent
+====================
 \cite{Wasik08}

doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

-                      r5407cdc
+                      r8d66610
 \chapter{Benchmarks}
+\noindent
+====================
+Writing Points:
+\begin{itemize}
+\item
+Performance matrices of memory allocation.
+\item
+Aim of micro benchmark suite.
+----- SHOULD WE GIVE IMPLEMENTATION DETAILS HERE? -----
+\PAB{For the benchmarks, yes.}
+\item
+A complete list of benchmarks in micro benchmark suite.
+\item
+One detailed section for each benchmark in micro benchmark suite including:
+\begin{itemize}
+\item
+The introduction of the benchmark.
+\item
+Figure.
+\item
+Results with popular memory allocators.
+\end{itemize}
+\item
+Summarize performance of current memory allocators.
+\end{itemize}
+\noindent
+====================

doc/theses/mubeen_zulfiqar_MMath/conclusion.tex

-                      r5407cdc
+                      r8d66610
 \chapter{Conclusion}
+\noindent
+====================
+Writing Points:
+\begin{itemize}
+\item
+Summarize u-benchmark suite.
+\item
+Summarize @uHeapLmmm@.
+\item
+Make recommendations on memory allocator design.
+\end{itemize}
+\noindent
+====================

doc/theses/mubeen_zulfiqar_MMath/intro.tex

-                      r5407cdc
+                      r8d66610
 \chapter{Introduction}
+\noindent
+====================
+Writing Points:
+\begin{itemize}
+\item
+Introduce dynamic memory allocation with brief background.
+\item
+Scope of the thesis.
+\item
+Importance of memory allocation and micro-benchmark suite.
+\item
+Research problem.
+\item
+Research objectives.
+\item
+The vision behind cfa-malloc.
+\item
+An outline of the thesis.
+\end{itemize}
+\noindent
+====================

doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex

-                      r5407cdc
+                      r8d66610
 \usepackage{graphicx}
 \usepackage{comment} % Removes large sections of the document.
-\usepackage{todonotes} % Adds todos (Must be included after comment.)
 % Hyperlinks make it very easy to navigate an electronic document.
 …
     colorlinks=true,        % false: boxed links; true: colored links
     linkcolor=blue,         % color of internal links
     citecolor=green,        % color of links to bibliography
+    citecolor=blue,        % color of links to bibliography
     filecolor=magenta,      % color of file links
     urlcolor=cyan           % color of external links
+    urlcolor=blue           % color of external links
+}
 \ifthenelse{\boolean{PrintVersion}}{   % for improved print quality, change some hyperref options
 …
 \CFAStyle                                               % CFA code-style for all languages
 \lstset{language=CFA,basicstyle=\linespread{0.9}\tt}    % CFA default language
+\newcommand{\PAB}[1]{{\color{red}PAB: #1}}
 %======================================================================
 …
 \input{allocator}
 \input{benchmarks}
+\input{performance}
 \input{conclusion}

Context Navigation

Legend:

doc/theses/andrew_beach_MMath/Makefile

doc/theses/andrew_beach_MMath/cfalab.sty

doc/theses/andrew_beach_MMath/existing.tex

doc/theses/andrew_beach_MMath/features.tex

doc/theses/andrew_beach_MMath/future.tex

doc/theses/andrew_beach_MMath/implement.tex

doc/theses/andrew_beach_MMath/uw-ethesis.tex

doc/theses/mubeen_zulfiqar_MMath/AllocDS1.fig

doc/theses/mubeen_zulfiqar_MMath/AllocDS2.fig

doc/theses/mubeen_zulfiqar_MMath/Makefile

doc/theses/mubeen_zulfiqar_MMath/allocator.tex

doc/theses/mubeen_zulfiqar_MMath/background.tex

doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

doc/theses/mubeen_zulfiqar_MMath/conclusion.tex

doc/theses/mubeen_zulfiqar_MMath/intro.tex

doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex

Download in other formats: