Changeset 8d66610

doc/LaTeXmacros/common.tex

-                      r5407cdc
+                      r8d66610
 %% Created On       : Sat Apr  9 10:06:17 2016
 %% Last Modified By : Peter A. Buhr
 %% Last Modified On : Sun Feb 14 15:52:46 2021
 %% Update Count     : 524
+%% Last Modified On : Sat May  8 08:48:37 2021
+%% Update Count     : 540
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 \usepackage{xspace}
 \newcommand{\CFAIcon}{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}} % Cforall icon
 \newcommand{\CFA}{\protect\CFAIcon\xspace}                      % CFA symbolic name
 \newcommand{\CFL}{\textrm{Cforall}\xspace}                      % Cforall non-icon name
 \newcommand{\Celeven}{\textrm{C11}\xspace}                      % C11 symbolic name
+\newcommand{\CFA}{\protect\CFAIcon\xspace}                              % CFA symbolic name
+\newcommand{\CFL}{\textrm{Cforall}\xspace}                              % Cforall non-icon name
+\newcommand{\Celeven}{\textrm{C11}\xspace}                              % C11 symbolic name
 \newcommand{\CCIcon}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}} % C++ icon
 \newcommand{\CC}{\protect\CCIcon\xspace}                        % C++ symbolic name
+\newcommand{\CC}[1][]{\protect\CCIcon{#1}\xspace}               % C++ symbolic name
 % numbers disallowed in latex variables names => use number names
 \newcommand{\CCeleven}{\protect\CCIcon{11}\xspace}      % C++11 symbolic name
 \newcommand{\CCfourteen}{\protect\CCIcon{14}\xspace} % C++14 symbolic name
 \newcommand{\CCseventeen}{\protect\CCIcon{17}\xspace} % C++17 symbolic name
 \newcommand{\CCtwenty}{\protect\CCIcon{20}\xspace}      % C++20 symbolic name
+\newcommand{\CCeleven}{\protect\CCIcon{11}\xspace}              % C++11 symbolic name
+\newcommand{\CCfourteen}{\protect\CCIcon{14}\xspace}    % C++14 symbolic name
+\newcommand{\CCseventeen}{\protect\CCIcon{17}\xspace}   % C++17 symbolic name
+\newcommand{\CCtwenty}{\protect\CCIcon{20}\xspace}              % C++20 symbolic name
 \newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace} % C# symbolic name
 …
 \renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}{-2.5ex \@plus -1ex \@minus -.2ex}{1.0ex \@plus .2ex}{\normalfont\normalsize\bfseries}}
 \renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}{-2.0ex \@plus -1ex \@minus -.2ex}{-1em}{\normalfont\normalsize\bfseries}}
+\renewcommand\subparagraph{\@startsection{subparagraph}{4}{\z@}{-1.5ex \@plus -1ex \@minus -.2ex}{-1em}{\normalfont\normalsize\bfseries\itshape}}
 % index macros
 …
 % Latin abbreviation
 \newcommand{\abbrevFont}{\textit}                       % set empty for no italics
+% If not followed by a comma or colon, add a comma.
+\newcommand{\CheckCommaColon}{\@ifnextchar{,}{}{\@ifnextchar{:}{}{,\xspace}}}
+% If not followed by a period, add a period.
+\newcommand{\CheckPeriod}{\@ifnextchar{.}{}{.\xspace}}
 \@ifundefined{eg}{
 \newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
+\newcommand*{\eg}{%
+        \@ifnextchar{,}{\EG}%
+                {\@ifnextchar{:}{\EG}%
+                        {\EG,\xspace}}%
+}}{}%
+\newcommand{\eg}{\EG\CheckCommaColon}
+}{}%
 \@ifundefined{ie}{
 \newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.}
+\newcommand*{\ie}{%
+        \@ifnextchar{,}{\IE}%
+                {\@ifnextchar{:}{\IE}%
+                        {\IE,\xspace}}%
+}}{}%
+\newcommand{\ie}{\IE\CheckCommaColon}
+}{}%
 \@ifundefined{etc}{
 \newcommand{\ETC}{\abbrevFont{etc}}
+\newcommand*{\etc}{%
+        \@ifnextchar{.}{\ETC}%
+        {\ETC.\xspace}%
+}}{}%
+\newcommand{\etc}{\ETC\CheckPeriod}
+}{}%
 \@ifundefined{etal}{
 \newcommand{\ETAL}{\abbrevFont{et}~\abbrevFont{al}}
+\newcommand*{\etal}{%
+        \@ifnextchar{.}{\protect\ETAL}%
+                {\protect\ETAL.\xspace}%
+}}{}%
+\newcommand{\etal}{\ETAL\CheckPeriod}
+}{}%
 \@ifundefined{viz}{
 \newcommand{\VIZ}{\abbrevFont{viz}}
+\newcommand*{\viz}{%
+        \@ifnextchar{.}{\VIZ}%
+                {\VIZ.\xspace}%
+}}{}%
+\newcommand{\viz}{\VIZ\CheckPeriod}
+}{}%
 \makeatother
 …
 showlines=true,                                                 % show blank lines at end of code
 aboveskip=4pt,                                                  % spacing above/below code block
 belowskip=0pt,
+belowskip=2pt,
 numberstyle=\footnotesize\sf,                   % numbering style
 % replace/adjust listing characters that look bad in sanserif
 …
 \lstset{
 language=CFA,
 moredelim=**[is][\color{red}]{@}{@},    % red highlighting @...@
 %moredelim=**[is][\color{red}]{®}{®},   % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
+%moredelim=**[is][\color{red}]{@}{@},   % red highlighting @...@
+moredelim=**[is][\color{red}]{®}{®},    % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
 %moredelim=**[is][\color{blue}]{ß}{ß},  % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
 %moredelim=**[is][\color{OliveGreen}]{¢}{¢}, % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"

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}

doc/user/Makefile

-                      r5407cdc
+                      r8d66610
 ${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} \
                 ${Macros}/common.tex ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib build/version | ${Build}
+                ${Macros}/common.sty ${Macros}/lstlang.sty ${Macros}/indexstyle ../bibliography/pl.bib build/version | ${Build}
         # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
         if [ ! -r ${basename $@}.ind ] ; then touch ${Build}/${basename $@}.ind ; fi
 …
         -${BibTeX} ${Build}/${basename $@}
         # Some citations reference others so run again to resolve these citations
         ${LaTeX} ${basename $@}.tex
+#       ${LaTeX} ${basename $@}.tex
         -${BibTeX} ${Build}/${basename $@}
         # Make index from *.aux entries and input index at end of document
 …
         ${LaTeX} ${basename $@}.tex
         # Run again to get index title into table of contents
         ${LaTeX} ${basename $@}.tex
+#       ${LaTeX} ${basename $@}.tex
 ## Define the default recipes.

doc/user/user.tex

-                      r5407cdc
+                      r8d66610
 %% Created On       : Wed Apr  6 14:53:29 2016
 %% Last Modified By : Peter A. Buhr
 %% Last Modified On : Sun Apr 25 19:03:03 2021
 %% Update Count     : 4951
+%% Last Modified On : Sat May  8 08:51:33 2021
+%% Update Count     : 5062
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 …
 % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
 % math escape $...$ (dollar symbol)
+\input{common}                                          % common CFA document macros
+\usepackage{common}                                                                             % common CFA document macros
+%\input{common}                                                                                 % common CFA document macros
 \setlength{\gcolumnposn}{3in}
 \CFAStyle                                                                                               % use default CFA format-style
 …
 For example, the octal ©0© or hexadecimal ©0x© prefix may end with an underscore ©0_377© or ©0x_ff©;
 the exponent infix ©E© may start or end with an underscore ©1.0_E10©, ©1.0E_10© or ©1.0_E_10©;
 the type suffixes ©U©, ©L©, etc. may start with an underscore ©1_U©, ©1_ll© or ©1.0E10_f©.
+the type suffixes ©U©, ©L©, \etc may start with an underscore ©1_U©, ©1_ll© or ©1.0E10_f©.
 \end{enumerate}
 It is significantly easier to read and enter long constants when they are broken up into smaller groupings (many cultures use comma and/or period among digits for the same purpose).
 …
 \end{cquote}
 All type qualifiers, \eg ©const©, ©volatile©, etc., are used in the normal way with the new declarations and also appear left to right, \eg:
+All type qualifiers, \eg ©const©, ©volatile©, \etc, are used in the normal way with the new declarations and also appear left to right, \eg:
 \begin{cquote}
 \begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}}
 …
 \end{tabular}
 \end{cquote}
 All declaration qualifiers, \eg ©extern©, ©static©, etc., are used in the normal way with the new declarations but can only appear at the start of a \CFA routine declaration,\footnote{\label{StorageClassSpecifier}
+All declaration qualifiers, \eg ©extern©, ©static©, \etc, are used in the normal way with the new declarations but can only appear at the start of a \CFA routine declaration,\footnote{\label{StorageClassSpecifier}
 The placement of a storage-class specifier other than at the beginning of the declaration specifiers in a declaration is an obsolescent feature.~\cite[\S~6.11.5(1)]{C11}} \eg:
 \begin{cquote}
 …
 also, it is unnecessary to specify all the fields of a struct in a multiple record-field tuple.
 Since tuple-index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member-access expressions to restructure a tuple (\eg, rearrange components, drop components, duplicate components, etc.).
+Since tuple-index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member-access expressions to restructure a tuple (\eg, rearrange components, drop components, duplicate components, \etc).
 \begin{cfa}
 [ int, int, long, double ] x;
 …
 \section{Tuples}
+\label{tuples}
 In C and \CFA, lists of elements appear in several contexts, such as the parameter list for a routine call.
 …
 \subsection{Tuple Coercions}
+\label{tuple coercions}\label{coercions!tuple}
 There are four coercions that can be performed on tuples and tuple variables: closing, opening, flattening and structuring.
 …
 \subsection{Mass Assignment}
+\label{mass assignment}\label{assignment!mass}
 \CFA permits assignment to several variables at once using mass assignment~\cite{CLU}.
 …
 \subsection{Multiple Assignment}
+\label{multiple assignment}\label{assignment!multiple}
 \CFA also supports the assignment of several values at once, known as multiple assignment~\cite{CLU,Galletly96}.
 …
 \subsection{Cascade Assignment}
+\index{cascade assignment}\index{assignment!cascade}
 As in C, \CFA mass and multiple assignments can be cascaded, producing cascade assignment.
 …
 \section{Stream I/O Library}
 \label{s:StreamIOLibrary}
 \index{input/output stream library}
 \index{stream library}
+\index{input}\index{output}
+\index{stream library}\index{library!stream}
 The goal of \CFA stream input/output (I/O) is to simplify the common cases\index{I/O!common case}, while fully supporting polymorphism and user defined types in a consistent way.
 Stream I/O can be implicitly or explicitly formatted.
 Implicit formatting means \CFA selects the output or input format for values that match with the type of a variable.
+Implicit formatting means \CFA selects the output or input format for values that matches the variable's type.
 Explicit formatting means additional information is specified to augment how an output or input of value is interpreted.
 \CFA formatting is a cross between C ©printf© and \CC ©cout© manipulators, and Python implicit spacing and newline.
+\CFA formatting incorporates ideas from C ©printf©, \CC ©stream© manipulators, and Python implicit spacing and newline.
 Specifically:
 \begin{itemize}
 …
 Hence, it is common programming practice to toggle manipulators on and then back to the default to prevent downstream side-effects.
 Without this programming style, errors occur when moving prints, as manipulator effects incorrectly flow into the new location.
+(To guarantee no side-effects, manipulator values must be saved and restored across function calls.)
 \item
 \CFA has more sophisticated implicit spacing between values than Python, plus implicit newline at the end of a print.
+Furthermore, to guarantee no side-effects, manipulator values must be saved and restored across function calls.
+\item
+\CFA has more sophisticated implicit value spacing than Python, plus implicit newline at the end of a print.
 \end{itemize}
+The standard polymorphic I/Os stream are ©stdin©/©sin© (input), ©stdout©/©sout© and ©stderr©/©serr© (output) (like C++ ©cin©/©cout©/©cerr©).
+Polymorphic streams ©exit© and ©abort© provide implicit program termination without and with generating a stack trace and core file.
+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
+\end{cfa}
+Note, \CFA stream variables ©stdin©, ©stdout©, ©stderr©, ©exit©, and ©abort© overload C variables ©stdin©, ©stdout©, ©stderr©, and functions ©exit© and ©abort©, respectively.
 The \CFA header file for the I/O library is \Indexc{fstream.hfa}.
+\subsection{Basic I/O}
 For implicit formatted output, the common case is printing a series of variables separated by whitespace.
 …
 \begin{cfa}
 cout << x ®<< " "® << y ®<< " "® << z << endl;
+cout  <<  x  ®<< " "®  <<  y  ®<< " "®  <<  z  << endl;
 \end{cfa}
+&
 …
 \end{tabular}
 \end{cquote}
 Input and output use a uniform operator, ©|©, rather than separate operators, as in ©>>© and ©<<© for \CC.
+Input and output use a uniform operator, ©|©, rather than \CC's ©>>© and ©<<© input/output operators.
 There is a weak similarity between the \CFA logical-or operator and the \Index{Shell pipe-operator} for moving data, where data flows in the correct direction for input but the opposite direction for output.
 …
 \end{cquote}
+\VRef[Figure]{f:CFACommand-LineProcessing} shows idiomatic \CFA command-line processing and copying an input file to an output file.
+Note, a stream variable may be copied because it is a reference to an underlying stream data-structures.
+All I/O errors are handles as exceptions, but end-of-file is not an exception as C programmers are use to explicitly checking for it.
+\begin{figure}
+\begin{cfa}
+#include ®<fstream.hfa>®
+int main( int argc, char * argv[] ) {
+        ®ifstream® in  = stdin;                                 $\C{// copy default files}$
+        ®ofstream® out = stdout;
+        try {
+                choose ( argc ) {
+                  case 2, 3:
+                        ®open®( in, argv[1] );                  $\C{// open input file first as output creates file}$
+                        if ( argc == 3 ) ®open®( out, argv[2] ); $\C{// do not create output unless input opens}$
+                  case 1: ;                                                     $\C{// use default files}$
+                  default:
+                        ®exit® | "Usage" | argv[0] | "[ input-file (default stdin) "
+                                   "[ output-file (default stdout) ] ]";
+                } // choose
+        } catch( ®Open_Failure® * ex; ex->istream == &in ) {
+                ®exit® | "Unable to open input file" | argv[1];
+        } catch( ®Open_Failure® * ex; ex->ostream == &out ) {
+                ®close®( in );                                          $\C{// optional}$
+                ®exit® | "Unable to open output file" | argv[2];
+        } // try
+        out | nlOff;                                                    $\C{// turn off auto newline}$
+        in | nlOn;                                                              $\C{// turn on reading newline}$
+        char ch;
+        for () {                                                                $\C{// read/write characters}$
+                in | ch;
+          if ( eof( in ) ) break;                               $\C{// eof ?}$
+                out | ch;
+        } // for
+} // main
+\end{cfa}
+\caption{\CFA Command-Line Processing}
+\label{f:CFACommand-LineProcessing}
+\end{figure}
+\VRef[Figure]{f:StreamFunctions} shows the stream operations.
+\begin{itemize}[topsep=4pt,itemsep=2pt,parsep=0pt]
+\item
+\Indexc{fail} tests the stream error-indicator, returning nonzero if it is set.
+\item
+\Indexc{clear} resets the stream error-indicator.
+\item
+\Indexc{flush} (©ofstream© only) causes any unwritten data for a stream to be written to the file.
+\item
+\Indexc{eof} (©ifstream© only) tests the end-of-file indicator for the stream pointed to by stream.
+Returns true if the end-of-file indicator is set, otherwise false.
+\item
+\Indexc{open} binds the file with ©name© to a stream accessed with ©mode© (see ©fopen©).
+\item
+\Indexc{close} flushes the stream and closes the file.
+\item
+\Indexc{write} (©ofstream© only) write ©size© bytes to the stream.
+The bytes are written lazily to file when internal buffers fill.
+Eager buffer writes are done with ©flush©
+\item
+\Indexc{read} (©ifstream© only) read ©size© bytes to the stream.
+\item
+\Indexc{ungetc} (©ifstream© only) pushes the character back to the input stream.
+Pushed-back characters returned by subsequent reads in the reverse order of pushing.
+\end{itemize}
+The constructor functions:
+\begin{itemize}[topsep=4pt,itemsep=2pt,parsep=0pt]
+\item
+create an unbound stream, which is subsequently bound to a file with ©open©.
+\item
+create a bound stream to the associated file with given ©mode©.
+\end{itemize}
+The destructor closes the stream.
+\begin{figure}
+\begin{cfa}
+// *********************************** ofstream ***********************************
+bool fail( ofstream & );$\indexc{fail}\index{ofstream@©ofstream©!©fail©}$
+void clear( ofstream & );$\indexc{clear}\index{ofstream@©ofstream©!©clear©}$
+int flush( ofstream & );$\indexc{flush}\index{ofstream@©ofstream©!©flush©}$
+void open( ofstream &, const char name[], const char mode[] = "w" );$\indexc{open}\index{ofstream@©ofstream©!©open©}$
+void close( ofstream & );$\indexc{close}\index{ofstream@©ofstream©!©close©}$
+ofstream & write( ofstream &, const char data[], size_t size );$\indexc{write}\index{ofstream@©ofstream©!©write©}$
+void ?{}( ofstream & );$\index{ofstream@©ofstream©!©?{}©}$
+void ?{}( ofstream &, const char name[], const char mode[] = "w" );
+void ^?{}( ofstream & );$\index{ofstream@©ofstream©!©^?{}©}$
+// *********************************** ifstream ***********************************
+bool fail( ifstream & is );$\indexc{fail}\index{ifstream@©ifstream©!©fail©}$
+void clear( ifstream & );$\indexc{clear}\index{ifstream@©ifstream©!©clear©}$
+bool eof( ifstream & is );$\indexc{eof}\index{ifstream@©ifstream©!©eof©}$
+void open( ifstream & is, const char name[], const char mode[] = "r" );$\indexc{open}\index{ifstream@©ifstream©!©open©}$
+void close( ifstream & is );$\indexc{close}\index{ifstream@©ifstream©!©close©}$
+ifstream & read( ifstream & is, char data[], size_t size );$\indexc{read}\index{ifstream@©ifstream©!©read©}$
+ifstream & ungetc( ifstream & is, char c );$\indexc{unget}\index{ifstream@©ifstream©!©unget©}$
+void ?{}( ifstream & is );$\index{ifstream@©ifstream©!©?{}©}$
+void ?{}( ifstream & is, const char name[], const char mode[] = "r" );
+void ^?{}( ifstream & is );$\index{ifstream@©ifstream©!©^?{}©}$
+\end{cfa}
+\caption{Stream Functions}
+\label{f:StreamFunctions}
+\end{figure}
 …
 \item
 \Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} toggle printing the separator with respect to the next printed item, and then return to the global seperator setting.
+\Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} toggle printing the separator with respect to the next printed item, and then return to the global separator setting.
 \begin{cfa}[belowskip=0pt]
 sout | 1 | sepOff | 2 | 3; $\C{// turn off implicit separator for the next item}$
 …
 sout | wd( 4, "ab" ) | wd( 3, "ab" ) | wd( 2, "ab" );
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
+\begin{cfa}[showspaces=true,aboveskip=0pt]
 ®  ®34 ® ®34 34
 ®  ®4.000000 ® ®4.000000 4.000000
 …
 \end{cfa}
+\Textbf{WARNING:} ©printf©\index{printf@©printf©}, ©scanf©\index{scanf@©scanf©} and their derivatives are unsafe when used with user-level threading, as in \CFA.
+These stream routines use kernel-thread locking (©futex©\index{futex@©futex©}), which block kernel threads, to prevent interleaving of I/O.
+However, the following simple example illustrates how a deadlock can occur (other complex scenarios are possible).
+Assume a single kernel thread and two user-level threads calling ©printf©.
+One user-level thread acquires the I/O lock and is time-sliced while performing ©printf©.
+The other user-level thread then starts execution, calls ©printf©, and blocks the only kernel thread because it cannot acquire the I/O lock.
+It does not help if the kernel lock is multiple acquisition, \ie, the lock owner can acquire it multiple times, because it then results in two user threads in the ©printf© critical section, corrupting the stream.
+\section{String Stream}
+All the stream formatting capabilities are available to format text to/from a C string rather than to a stream file.
+\VRef[Figure]{f:StringStreamProcessing} shows writing (output) and reading (input) from a C string.
+\begin{figure}
+\begin{cfa}
+#include <fstream.hfa>
+#include <strstream.hfa>
+int main() {
+        enum { size = 256 };
+        char buf[size]; $\C{// output buffer}$
+        ®ostrstream osstr = { buf, size };® $\C{// bind output buffer/size}$
+        int i = 3, j = 5, k = 7;
+        double x = 12345678.9, y = 98765.4321e-11;
+        osstr | i | hex(j) | wd(10, k) | sci(x) | unit(eng(y)); $\C{// same lines of output}$
+        write( osstr );
+        printf( "%s", buf );
+        sout | i | hex(j) | wd(10, k) | sci(x) | unit(eng(y));
+        char buf2[] = "12 14 15 3.5 7e4"; $\C{// input buffer}$
+        ®istrstream isstr = { buf2 };®
+        isstr | i | j | k | x | y;
+        sout | i | j | k | x | y;
+}
+\end{cfa}
+\caption{String Stream Processing}
+\label{f:StringStreamProcessing}
+\end{figure}
+\VRef[Figure]{f:StringStreamFunctions} shows the string stream operations.
+\begin{itemize}[topsep=4pt,itemsep=2pt,parsep=0pt]
+\item
+\Indexc{write} (©ostrstream© only) writes all the buffered characters to the specified stream (©stdout© default).
+\end{itemize}
+The constructor functions:
+\begin{itemize}[topsep=4pt,itemsep=2pt,parsep=0pt]
+\item
+create a bound stream to a write buffer (©ostrstream©) of ©size© or a read buffer (©istrstream©) containing a C string terminated with ©'\0'©.
+\end{itemize}
+\begin{figure}
+\begin{cfa}
+// *********************************** ostrstream ***********************************
+ostrstream & write( ostrstream & os, FILE * stream = stdout );
+void ?{}( ostrstream &, char buf[], size_t size );
+// *********************************** istrstream ***********************************
+void ?{}( istrstream & is, char buf[] );
+\end{cfa}
+\caption{String Stream Functions}
+\label{f:StringStreamFunctions}
+\end{figure}
 …
 \item
 Package: a container to organize modules for distribution; It has attributes like name, author,
 version, dependences, etc.
 \item
 Project: a working set for a \CFA project; It has attributes like name, author, version, dependences, etc.
+version, dependences, \etc.
+\item
+Project: a working set for a \CFA project; It has attributes like name, author, version, dependences, \etc.
 \end{itemize}
 …
 A package is defined by putting a project description file, Do.prj, with one or more modules into a directory.
 This project description file contains the package's meta data, including package name, author, version, dependences, etc.
+This project description file contains the package's meta data, including package name, author, version, dependences, \etc.
 It should be in the root of the package directory.
 …
 Module: a container to organize a set of related types and methods; It has a module name, and several interfaces visible from outside
 \item
 Package: a container to organize modules for distribution; It has attributes like name, author, version, dependences, etc.
 \item
 Project: a working set for a \CFA project; It has attributes like name, author, version, dependences, etc.
+Package: a container to organize modules for distribution; It has attributes like name, author, version, dependences, \etc.
+\item
+Project: a working set for a \CFA project; It has attributes like name, author, version, dependences, \etc.
 \end{itemize}
 …
 \begin{cquote}
 \begin{tabular}{@{}l@{\hspace{\parindentlnth}}|@{\hspace{\parindentlnth}}l@{}}
 \multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{@{\hspace{\parindentlnth}}c}{\textbf{C}@{}}   \\
+\multicolumn{1}{@{}c|@{\hspace{\parindentlnth}}}{\textbf{\CFA}} & \multicolumn{1}{@{\hspace{\parindentlnth}}c@{}}{\textbf{C}}   \\
 \hline
 \begin{cfa}
 #include <gmp>$\indexc{gmp}$
+#include <gmp.hfa>$\indexc{gmp}$
 int main( void ) {
         sout | "Factorial Numbers";

libcfa/src/common.hfa

-                      r5407cdc
+                      r8d66610
 // Created On       : Wed Jul 11 17:54:36 2018
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Sat Aug 15 08:51:29 2020
 // Update Count     : 14
+// Last Modified On : Wed May  5 14:02:04 2021
+// Update Count     : 18
 //
 …
 static inline {
+        char min( char t1, char t2 ) { return t1 < t2 ? t1 : t2; } // optimization
+        intptr_t min( intptr_t t1, intptr_t t2 ) { return t1 < t2 ? t1 : t2; } // optimization
+        uintptr_t min( uintptr_t t1, uintptr_t t2 ) { return t1 < t2 ? t1 : t2; } // optimization
+        char min( char v1, char v2 ) { return v1 < v2 ? v1 : v2; } // optimization
+        int min( int v1, int v2 ) { return v1 < v2 ? v1 : v2; }
+        unsigned int min( unsigned int v1, unsigned int v2 ) { return v1 < v2 ? v1 : v2; }
+        long int min( long int v1, long int v2 ) { return v1 < v2 ? v1 : v2; }
+        unsigned long int min( unsigned long int v1, unsigned int v2 ) { return v1 < v2 ? v1 : v2; }
+        long long int min( long long int v1, long long int v2 ) { return v1 < v2 ? v1 : v2; }
+        unsigned long long int min( unsigned long long int v1, unsigned int v2 ) { return v1 < v2 ? v1 : v2; }
         forall( T | { int ?<?( T, T ); } )
         T min( T t1, T t2 ) { return t1 < t2 ? t1 : t2; }
+        T min( T v1, T v2 ) { return v1 < v2 ? v1 : v2; }
+        char max( char t1, char t2 ) { return t1 > t2 ? t1 : t2; } // optimization
+        intptr_t max( intptr_t t1, intptr_t t2 ) { return t1 > t2 ? t1 : t2; } // optimization
+        uintptr_t max( uintptr_t t1, uintptr_t t2 ) { return t1 > t2 ? t1 : t2; } // optimization
+        char max( char v1, char v2 ) { return v1 > v2 ? v1 : v2; } // optimization
+        int max( int v1, int v2 ) { return v1 > v2 ? v1 : v2; }
+        unsigned int max( unsigned int v1, unsigned int v2 ) { return v1 > v2 ? v1 : v2; }
+        long int max( long int v1, long int v2 ) { return v1 > v2 ? v1 : v2; }
+        unsigned long int max( unsigned long int v1, unsigned long int v2 ) { return v1 > v2 ? v1 : v2; }
+        long long int max( long long int v1, long long int v2 ) { return v1 > v2 ? v1 : v2; }
+        unsigned long long int max( unsigned long long int v1, unsigned long long int v2 ) { return v1 > v2 ? v1 : v2; }
         forall( T | { int ?>?( T, T ); } )
         T max( T t1, T t2 ) { return t1 > t2 ? t1 : t2; }
+        T max( T v1, T v2 ) { return v1 > v2 ? v1 : v2; }
         forall( T | { T min( T, T ); T max( T, T ); } )

libcfa/src/concurrency/alarm.cfa

-                      r5407cdc
+                      r8d66610
 void __kernel_set_timer( Duration alarm ) {
+        verifyf(alarm >= 1`us || alarm == 0, "Setting timer to < 1us (%jins)", alarm`ns);
+        setitimer( ITIMER_REAL, &(itimerval){ alarm }, 0p );
+        alarm = max(alarm, 1`us);
+        itimerval otv @= { 0 };
+        getitimer( ITIMER_REAL, &otv );
+        Duration od = { otv.it_value };
+        if(od == 0 || od > alarm) {
+                setitimer( ITIMER_REAL, &(itimerval){ alarm }, 0p );
+        }
+}
 …
 //=============================================================================================
+void ?{}( alarm_node_t & this, $thread * thrd, Time alarm, Duration period) with( this ) {
+void ?{}( alarm_node_t & this, $thread * thrd, Duration alarm, Duration period) with( this ) {
+        this.initial = alarm;
+        this.period  = period;
         this.thrd = thrd;
+        this.alarm = alarm;
+        this.period = period;
+        this.timeval = __kernel_get_time() + alarm;
         set = false;
         type = User;
+}
+void ?{}( alarm_node_t & this, processor * proc, Time alarm, Duration period ) with( this ) {
+void ?{}( alarm_node_t & this, processor * proc, Duration alarm, Duration period ) with( this ) {
+        this.initial = alarm;
+        this.period  = period;
         this.proc = proc;
+        this.alarm = alarm;
+        this.period = period;
+        this.timeval = __kernel_get_time() + alarm;
         set = false;
         type = Kernel;
+}
+void ?{}( alarm_node_t & this, Alarm_Callback callback, Time alarm, Duration period ) with( this ) {
+        this.alarm = alarm;
+        this.period = period;
+void ?{}( alarm_node_t & this, Alarm_Callback callback, Duration alarm, Duration period ) with( this ) {
         this.callback = callback;
+        this.initial = alarm;
+        this.period  = period;
+        this.timeval = __kernel_get_time() + alarm;
         set = false;
         type = Callback;
 …
 void insert( alarm_list_t * this, alarm_node_t * n ) {
         alarm_node_t * it = & (*this)`first;
         while( it && (n->alarm > it->alarm) ) {
+        while( it && (n->timeval > it->timeval) ) {
                 it = & (*it)`next;
+        }
 …
         lock( event_kernel->lock __cfaabi_dbg_ctx2 );
+        {
+                verify( validate( alarms ) );
+                bool first = ! & alarms`first;
+                /* paranoid */ verify( validate( alarms ) );
+                __cfadbg_print_safe( preemption, " KERNEL: alarm inserting %p (%lu).\n", this, this->alarm.tn );
+                Time curr = __kernel_get_time();
+                __cfadbg_print_safe( preemption, " KERNEL: alarm inserting %p (%lu -> %lu).\n", this, curr.tn, this->timeval.tn );
                 insert( &alarms, this );
+                if( first ) {
+                        __kernel_set_timer( alarms`first.alarm - __kernel_get_time() );
+                }
+                __kernel_set_timer( this->timeval - curr);
+                this->set = true;
+        }
         unlock( event_kernel->lock );
-        this->set = true;
         enable_interrupts();
+}
 …
+        {
                 verify( validate( event_kernel->alarms ) );
+                remove( *this );
+                if (this->set) remove( *this );
+                this->set = false;
+        }
         unlock( event_kernel->lock );
         enable_interrupts();
-        this->set = false;
+}
 …
 void sleep( Duration duration ) {
         alarm_node_t node = { active_thread(), __kernel_get_time() + duration, 0`s };
+        alarm_node_t node = { active_thread(), duration, 0`s };
         register_self( &node );

libcfa/src/concurrency/alarm.hfa

-                      r5407cdc
+                      r8d66610
 struct alarm_node_t {
         Time alarm;                             // time when alarm goes off
         Duration period;                        // if > 0 => period of alarm
+        Duration initial;       // time when alarm goes off
+        Duration period;        // if > 0 => period of alarm
         DLISTED_MGD_IMPL_IN(alarm_node_t)
+        inline dlink(alarm_node_t);
         union {
                 $thread * thrd;                                 // thrd who created event
                 processor * proc;                               // proc who created event
                 Alarm_Callback callback;                // callback to handle event
+                $thread * thrd;                 // thrd who created event
+                processor * proc;                       // proc who created event
+                Alarm_Callback callback;        // callback to handle event
         };
+        bool set                :1;             // whether or not the alarm has be registered
+        enum alarm_type type;           // true if this is not a user defined alarm
+        Time timeval;           // actual time at which the alarm goes off
+        enum alarm_type type;   // true if this is not a user defined alarm
+        bool set                :1;     // whether or not the alarm has be registered
 };
 DLISTED_MGD_IMPL_OUT(alarm_node_t)
+P9_EMBEDDED( alarm_node_t, dlink(alarm_node_t) )
 void ?{}( alarm_node_t & this, $thread * thrd, Time alarm, Duration period );
 void ?{}( alarm_node_t & this, processor   * proc, Time alarm, Duration period );
 void ?{}( alarm_node_t & this, Alarm_Callback callback, Time alarm, Duration period );
+void ?{}( alarm_node_t & this, $thread * thrd, Duration alarm, Duration period );
+void ?{}( alarm_node_t & this, processor * proc, Duration alarm, Duration period );
+void ?{}( alarm_node_t & this, Alarm_Callback callback, Duration alarm, Duration period );
 void ^?{}( alarm_node_t & this );
 typedef dlist(alarm_node_t, alarm_node_t) alarm_list_t;
+typedef dlist(alarm_node_t) alarm_list_t;
 void insert( alarm_list_t * this, alarm_node_t * n );

libcfa/src/concurrency/clib/cfathread.cfa

-                      r5407cdc
+                      r8d66610
       extern void __cfactx_invoke_thread(void (*main)(void *), void * this);
+}
+extern Time __kernel_get_time();
 //================================================================================
 …
         int cfathread_cond_timedwait(cfathread_cond_t *restrict cond, cfathread_mutex_t *restrict mut, const struct timespec *restrict abstime) __attribute__((nonnull (1,2,3))) {
                 Time t = { *abstime };
+                if( wait( (*cond)->impl, (*mut)->impl, t ) ) {
+                timespec curr;
+                clock_gettime( CLOCK_REALTIME, &curr );
+                Time c = { curr };
+                if( wait( (*cond)->impl, (*mut)->impl, t - c ) ) {
                         return 0;
+                }

libcfa/src/concurrency/clib/cfathread.h

r5407cdc	r8d66610
80	80
81	81	typedef struct cfathread_cond_attr {
	82	// WARNING: adding support for pthread_condattr_setclock would require keeping track of the clock
	83	// and reading it in cond_timedwait
82	84	} cfathread_condattr_t;
83	85	typedef struct cfathread_condition * cfathread_cond_t;

libcfa/src/concurrency/invoke.h

-                      r5407cdc
+                      r8d66610
         struct __thread_desc_link {
                 struct $thread * next;
-                struct $thread * prev;
                 volatile unsigned long long ts;
-                unsigned preferred;
         };
 …
                 // context that is switch during a __cfactx_switch
                 struct __stack_context_t context;
+                // Link lists fields
+                // instrusive link field for threads
+                struct __thread_desc_link link;
                 // current execution status for coroutine
 …
                 struct cluster * curr_cluster;
+                // Link lists fields
+                // instrusive link field for threads
+                struct __thread_desc_link link;
+                // preferred ready-queue
+                unsigned preferred;
                 // coroutine body used to store context

libcfa/src/concurrency/io.cfa

-                      r5407cdc
+                      r8d66610
                 /* paranoid */ verify( proc->io.ctx );
+                __attribute__((unused)) cluster * cltr = proc->cltr;
                 $io_context & ctx = *proc->io.ctx;
+                // for(i; 2) {
+                //      unsigned idx = proc->rdq.id + i;
+                //      cltr->ready_queue.lanes.tscs[idx].tv = -1ull;
+                // }
                 __ioarbiter_flush( ctx );
 …
                                 // Update statistics
                                 __STATS__( false, io.calls.errors.busy ++; )
+                                // for(i; 2) {
+                                //      unsigned idx = proc->rdq.id + i;
+                                //      cltr->ready_queue.lanes.tscs[idx].tv = rdtscl();
+                                // }
                                 return;
                         default:
 …
                 ctx.proc->io.pending = false;
+                ready_schedule_lock();
+                __cfa_io_drain( proc );
+                ready_schedule_unlock();
+                // for(i; 2) {
+                //      unsigned idx = proc->rdq.id + i;
+                //      cltr->ready_queue.lanes.tscs[idx].tv = rdtscl();
+                // }
+        }

libcfa/src/concurrency/kernel.cfa

-                      r5407cdc
+                      r8d66610
         #if !defined(__CFA_NO_STATISTICS__)
                 if( this->print_halts ) {
                         __cfaabi_bits_print_safe( STDOUT_FILENO, "Processor : %d - %s (%p)\n", this->id, this->name, (void*)this);
+                        __cfaabi_bits_print_safe( STDOUT_FILENO, "Processor : %d - %s (%p)\n", this->unique_id, this->name, (void*)this);
+                }
         #endif
 …
                 // Setup preemption data
                 preemption_scope scope = { this };
-                __STATS( unsigned long long last_tally = rdtscl(); )
                 // if we need to run some special setup, now is the time to do it.
 …
                 MAIN_LOOP:
                 for() {
+                        #define OLD_MAIN 1
+                        #if OLD_MAIN
                         // Check if there is pending io
                         __maybe_io_drain( this );
 …
                                 #if !defined(__CFA_NO_STATISTICS__)
                                         if(this->print_halts) {
                                                 __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 0\n", this->id, rdtscl());
+                                                __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 0\n", this->unique_id, rdtscl());
+                                        }
                                 #endif
 …
                                 #if !defined(__CFA_NO_STATISTICS__)
                                         if(this->print_halts) {
                                                 __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 1\n", this->id, rdtscl());
+                                                __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 1\n", this->unique_id, rdtscl());
+                                        }
                                 #endif
 …
                         if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
-                        #if !defined(__CFA_NO_STATISTICS__)
-                                unsigned long long curr = rdtscl();
-                                if(curr > (last_tally + 500000000)) {
-                                        __tally_stats(this->cltr->stats, __cfaabi_tls.this_stats);
-                                        last_tally = curr;
+                                }
-                        #endif
                         if(this->io.pending && !this->io.dirty) {
                                 __cfa_io_flush( this );
+                        }
+                //      SEARCH: {
+                //              /* paranoid */ verify( ! __preemption_enabled() );
+                //              /* paranoid */ verify( kernelTLS().this_proc_id );
+                //              // First, lock the scheduler since we are searching for a thread
+                //              // Try to get the next thread
+                //              ready_schedule_lock();
+                //              readyThread = pop_fast( this->cltr );
+                //              ready_schedule_unlock();
+                //              if(readyThread) {  break SEARCH; }
+                //              // If we can't find a thread, might as well flush any outstanding I/O
+                //              if(this->io.pending) { __cfa_io_flush( this ); }
+                //              // Spin a little on I/O, just in case
+                //              for(25) {
+                //                      __maybe_io_drain( this );
+                //                      ready_schedule_lock();
+                //                      readyThread = pop_fast( this->cltr );
+                //                      ready_schedule_unlock();
+                //                      if(readyThread) {  break SEARCH; }
+                //              }
+                //              // no luck, try stealing a few times
+                //              for(25) {
+                //                      if( __maybe_io_drain( this ) ) {
+                //                              ready_schedule_lock();
+                //                              readyThread = pop_fast( this->cltr );
+                //                      } else {
+                //                              ready_schedule_lock();
+                //                              readyThread = pop_slow( this->cltr );
+                //                      }
+                //                      ready_schedule_unlock();
+                //                      if(readyThread) {  break SEARCH; }
+                //              }
+                //              // still no luck, search for a thread
+                //              ready_schedule_lock();
+                //              readyThread = pop_search( this->cltr );
+                //              ready_schedule_unlock();
+                //              if(readyThread) { break SEARCH; }
+                //              // Don't block if we are done
+                //              if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
+                //              __STATS( __tls_stats()->ready.sleep.halts++; )
+                //              // Push self to idle stack
+                //              mark_idle(this->cltr->procs, * this);
+                //              // Confirm the ready-queue is empty
+                //              __maybe_io_drain( this );
+                //              ready_schedule_lock();
+                //              readyThread = pop_search( this->cltr );
+                //              ready_schedule_unlock();
+                //              if( readyThread ) {
+                //                      // A thread was found, cancel the halt
+                //                      mark_awake(this->cltr->procs, * this);
+                //                      __STATS( __tls_stats()->ready.sleep.cancels++; )
+                //                      // continue the main loop
+                //                      break SEARCH;
+                //              }
+                //              __STATS( if(this->print_halts) __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 0\n", this->id, rdtscl()); )
+                //              __cfadbg_print_safe(runtime_core, "Kernel : core %p waiting on eventfd %d\n", this, this->idle);
+                //              // __disable_interrupts_hard();
+                //              eventfd_t val;
+                //              eventfd_read( this->idle, &val );
+                //              // __enable_interrupts_hard();
+                //              __STATS( if(this->print_halts) __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 1\n", this->id, rdtscl()); )
+                //              // We were woken up, remove self from idle
+                //              mark_awake(this->cltr->procs, * this);
+                //              // DON'T just proceed, start looking again
+                //              continue MAIN_LOOP;
+                //      }
+                // RUN_THREAD:
+                //      /* paranoid */ verify( kernelTLS().this_proc_id );
+                //      /* paranoid */ verify( ! __preemption_enabled() );
+                //      /* paranoid */ verify( readyThread );
+                //      // Reset io dirty bit
+                //      this->io.dirty = false;
+                //      // We found a thread run it
+                //      __run_thread(this, readyThread);
+                //      // Are we done?
+                //      if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
+                //      #if !defined(__CFA_NO_STATISTICS__)
+                //              unsigned long long curr = rdtscl();
+                //              if(curr > (last_tally + 500000000)) {
+                //                      __tally_stats(this->cltr->stats, __cfaabi_tls.this_stats);
+                //                      last_tally = curr;
+                //              }
+                //      #endif
+                //      if(this->io.pending && !this->io.dirty) {
+                //              __cfa_io_flush( this );
+                //      }
+                //      // Check if there is pending io
+                //      __maybe_io_drain( this );
+                        #else
+                                #warning new kernel loop
+                        SEARCH: {
+                                /* paranoid */ verify( ! __preemption_enabled() );
+                                // First, lock the scheduler since we are searching for a thread
+                                ready_schedule_lock();
+                                // Try to get the next thread
+                                readyThread = pop_fast( this->cltr );
+                                if(readyThread) { ready_schedule_unlock(); break SEARCH; }
+                                // If we can't find a thread, might as well flush any outstanding I/O
+                                if(this->io.pending) { __cfa_io_flush( this ); }
+                                // Spin a little on I/O, just in case
+                                        for(5) {
+                                        __maybe_io_drain( this );
+                                        readyThread = pop_fast( this->cltr );
+                                        if(readyThread) { ready_schedule_unlock(); break SEARCH; }
+                                }
+                                // no luck, try stealing a few times
+                                        for(5) {
+                                        if( __maybe_io_drain( this ) ) {
+                                                readyThread = pop_fast( this->cltr );
+                                        } else {
+                                                readyThread = pop_slow( this->cltr );
+                                        }
+                                        if(readyThread) { ready_schedule_unlock(); break SEARCH; }
+                                }
+                                // still no luck, search for a thread
+                                readyThread = pop_search( this->cltr );
+                                if(readyThread) { ready_schedule_unlock(); break SEARCH; }
+                                // Don't block if we are done
+                                if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
+                                __STATS( __tls_stats()->ready.sleep.halts++; )
+                                // Push self to idle stack
+                                ready_schedule_unlock();
+                                mark_idle(this->cltr->procs, * this);
+                                ready_schedule_lock();
+                                // Confirm the ready-queue is empty
+                                __maybe_io_drain( this );
+                                readyThread = pop_search( this->cltr );
+                                ready_schedule_unlock();
+                                if( readyThread ) {
+                                        // A thread was found, cancel the halt
+                                        mark_awake(this->cltr->procs, * this);
+                                        __STATS( __tls_stats()->ready.sleep.cancels++; )
+                                        // continue the main loop
+                                        break SEARCH;
+                                }
+                                        __STATS( if(this->print_halts) __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 0\n", this->unique_id, rdtscl()); )
+                                __cfadbg_print_safe(runtime_core, "Kernel : core %p waiting on eventfd %d\n", this, this->idle);
+                                // __disable_interrupts_hard();
+                                eventfd_t val;
+                                eventfd_read( this->idle, &val );
+                                // __enable_interrupts_hard();
+                                        __STATS( if(this->print_halts) __cfaabi_bits_print_safe( STDOUT_FILENO, "PH:%d - %lld 1\n", this->unique_id, rdtscl()); )
+                                // We were woken up, remove self from idle
+                                mark_awake(this->cltr->procs, * this);
+                                // DON'T just proceed, start looking again
+                                continue MAIN_LOOP;
+                        }
+                RUN_THREAD:
+                        /* paranoid */ verify( ! __preemption_enabled() );
+                        /* paranoid */ verify( readyThread );
+                        // Reset io dirty bit
+                        this->io.dirty = false;
+                        // We found a thread run it
+                        __run_thread(this, readyThread);
+                        // Are we done?
+                        if( __atomic_load_n(&this->do_terminate, __ATOMIC_SEQ_CST) ) break MAIN_LOOP;
+                        if(this->io.pending && !this->io.dirty) {
+                                __cfa_io_flush( this );
+                        }
+                        ready_schedule_lock();
+                        __maybe_io_drain( this );
+                        ready_schedule_unlock();
+                        #endif
+                }
 …
         post( this->terminated );
         if(this == mainProcessor) {
 …
 static void __schedule_thread( $thread * thrd ) {
         /* paranoid */ verify( ! __preemption_enabled() );
-        /* paranoid */ verify( kernelTLS().this_proc_id );
         /* paranoid */ verify( ready_schedule_islocked());
         /* paranoid */ verify( thrd );
 …
         /* paranoid */ verify( 0x0D15EA5E0D15EA5Ep == thrd->canary );
+        const bool local = thrd->state != Start;
         if (thrd->preempted == __NO_PREEMPTION) thrd->state = Ready;
 …
         // push the thread to the cluster ready-queue
         push( cl, thrd );
+        push( cl, thrd, local );
         // variable thrd is no longer safe to use
 …
 static inline $thread * __next_thread(cluster * this) with( *this ) {
         /* paranoid */ verify( ! __preemption_enabled() );
-        /* paranoid */ verify( kernelTLS().this_proc_id );
         ready_schedule_lock();
 …
         ready_schedule_unlock();
-        /* paranoid */ verify( kernelTLS().this_proc_id );
         /* paranoid */ verify( ! __preemption_enabled() );
         return thrd;
 …
 static inline $thread * __next_thread_slow(cluster * this) with( *this ) {
         /* paranoid */ verify( ! __preemption_enabled() );
-        /* paranoid */ verify( kernelTLS().this_proc_id );
         ready_schedule_lock();
 …
         ready_schedule_unlock();
-        /* paranoid */ verify( kernelTLS().this_proc_id );
         /* paranoid */ verify( ! __preemption_enabled() );
         return thrd;
 …
                 unsigned tail = *ctx->cq.tail;
                 if(head == tail) return false;
+                #if OLD_MAIN
                 ready_schedule_lock();
                 ret = __cfa_io_drain( proc );
                 ready_schedule_unlock();
+                #else
+                        ret = __cfa_io_drain( proc );
+        #endif
         #endif
         return ret;
 …
+        }
+        static void crawl_list( cluster * cltr, dlist(processor) & list, unsigned count ) {
+                /* paranoid */ verify( cltr->stats );
+                processor * it = &list`first;
+                for(unsigned i = 0; i < count; i++) {
+                        /* paranoid */ verifyf( it, "Unexpected null iterator, at index %u of %u\n", i, count);
+                        /* paranoid */ verify( it->local_data->this_stats );
+                        __tally_stats( cltr->stats, it->local_data->this_stats );
+                        it = &(*it)`next;
+                }
+        }
+        void crawl_cluster_stats( cluster & this ) {
+                // Stop the world, otherwise stats could get really messed-up
+                // this doesn't solve all problems but does solve many
+                // so it's probably good enough
+                uint_fast32_t last_size = ready_mutate_lock();
+                        crawl_list(&this, this.procs.actives, this.procs.total - this.procs.idle);
+                        crawl_list(&this, this.procs.idles  , this.procs.idle );
+                // Unlock the RWlock
+                ready_mutate_unlock( last_size );
+        }
         void print_stats_now( cluster & this, int flags ) {
+                crawl_cluster_stats( this );
                 __print_stats( this.stats, this.print_stats, "Cluster", this.name, (void*)&this );
+        }

libcfa/src/concurrency/kernel.hfa

-                      r5407cdc
+                      r8d66610
 // Processor id, required for scheduling threads
+struct __processor_id_t {
+        unsigned id:24;
+        #if !defined(__CFA_NO_STATISTICS__)
+                struct __stats_t * stats;
+        #endif
+};
 coroutine processorCtx_t {
 …
 // Wrapper around kernel threads
 struct __attribute__((aligned(128))) processor {
-        // Main state
-        inline __processor_id_t;
         // Cluster from which to get threads
         struct cluster * cltr;
 …
         pthread_t kernel_thread;
+        // Unique id for the processor (not per cluster)
+        unsigned unique_id;
         struct {
                 $io_context * ctx;
 …
         // Link lists fields
         DLISTED_MGD_IMPL_IN(processor)
+        inline dlink(processor);
         // special init fields
 …
         } init;
+        struct KernelThreadData * local_data;
         #if !defined(__CFA_NO_STATISTICS__)
                 int print_stats;
 …
 #endif
 };
+P9_EMBEDDED( processor, dlink(processor) )
 void  ?{}(processor & this, const char name[], struct cluster & cltr);
 …
 static inline void  ?{}(processor & this, struct cluster & cltr) { this{ "Anonymous Processor", cltr}; }
 static inline void  ?{}(processor & this, const char name[])     { this{name, *mainCluster}; }
-DLISTED_MGD_IMPL_OUT(processor)
 //-----------------------------------------------------------------------------
 …
 // Aligned timestamps which are used by the relaxed ready queue
+struct __attribute__((aligned(128))) __timestamp_t;
+void  ?{}(__timestamp_t & this);
+void ^?{}(__timestamp_t & this);
+struct __attribute__((aligned(128))) __timestamp_t {
+        volatile unsigned long long tv;
+};
+static inline void  ?{}(__timestamp_t & this) { this.tv = 0; }
+static inline void ^?{}(__timestamp_t & this) {}
 //TODO adjust cache size to ARCHITECTURE
 …
 void  ?{}(__ready_queue_t & this);
 void ^?{}(__ready_queue_t & this);
+#if !defined(__CFA_NO_STATISTICS__)
+        unsigned cnt(const __ready_queue_t & this, unsigned idx);
+#endif
 // Idle Sleep
 …
         // List of idle processors
         dlist(processor, processor) idles;
+        dlist(processor) idles;
         // List of active processors
         dlist(processor, processor) actives;
+        dlist(processor) actives;
 };

libcfa/src/concurrency/kernel/fwd.hfa

-                      r5407cdc
+                      r8d66610
                         struct $thread          * volatile this_thread;
                         struct processor        * volatile this_processor;
+                        struct __processor_id_t * volatile this_proc_id;
+                        struct __stats_t        * volatile this_stats;
+                        volatile bool sched_lock;
                         struct {
 …
                                 uint64_t bck_seed;
                         } ready_rng;
+                        struct __stats_t        * volatile this_stats;
+                        #ifdef __CFA_WITH_VERIFY__
+                                // Debug, check if the rwlock is owned for reading
+                                bool in_sched_lock;
+                                unsigned sched_id;
+                        #endif
                 } __cfaabi_tls __attribute__ ((tls_model ( "initial-exec" )));

libcfa/src/concurrency/kernel/startup.cfa

-                      r5407cdc
+                      r8d66610
 static void doregister( struct cluster & cltr );
 static void unregister( struct cluster & cltr );
+static void register_tls( processor * this );
+static void unregister_tls( processor * this );
 static void ?{}( $coroutine & this, current_stack_info_t * info);
 static void ?{}( $thread & this, current_stack_info_t * info);
 …
         NULL,                                                                                           // cannot use 0p
         NULL,
+        false,
+        { 1, false, false },
+,
+        { 0, 0 },
         NULL,
+        NULL,
+        { 1, false, false },
+        #ifdef __CFA_WITH_VERIFY__
+                false,
+,
+        #endif
 };
 …
         (*mainProcessor){};
+        register_tls( mainProcessor );
         //initialize the global state variables
         __cfaabi_tls.this_processor = mainProcessor;
-        __cfaabi_tls.this_proc_id   = (__processor_id_t*)mainProcessor;
         __cfaabi_tls.this_thread    = mainThread;
 …
                 __init_stats( __cfaabi_tls.this_stats );
         #endif
+        mainProcessor->local_data = &__cfaabi_tls;
         // Enable preemption
 …
         #endif
+        mainProcessor->local_data = 0p;
+        unregister_tls( mainProcessor );
         // Destroy the main processor and its context in reverse order of construction
         // These were manually constructed so we need manually destroy them
 …
         processor * proc = (processor *) arg;
         __cfaabi_tls.this_processor = proc;
-        __cfaabi_tls.this_proc_id   = (__processor_id_t*)proc;
         __cfaabi_tls.this_thread    = 0p;
         __cfaabi_tls.preemption_state.[enabled, disable_count] = [false, 1];
+        proc->local_data = &__cfaabi_tls;
+        register_tls( proc );
         // SKULLDUGGERY: We want to create a context for the processor coroutine
         // which is needed for the 2-step context switch. However, there is no reason
 …
                 #endif
         #endif
+        proc->local_data = 0p;
+        unregister_tls( proc );
         return 0p;
 …
         self_mon_p = &self_mon;
         link.next = 0p;
         link.prev = 0p;
         link.preferred = -1u;
+        link.ts   = 0;
+        preferred = -1u;
         last_proc = 0p;
         #if defined( __CFA_WITH_VERIFY__ )
 …
         this.rdq.id  = -1u;
         this.rdq.target = -1u;
         this.rdq.cutoff = -1ull;
+        this.rdq.cutoff = 0ull;
         do_terminate = false;
         preemption_alarm = 0p;
 …
         this.init.thrd = initT;
+        this.local_data = 0p;
         this.idle = eventfd(0, 0);
 …
         #endif
-        // Register and Lock the RWlock so no-one pushes/pops while we are changing the queue
-        uint_fast32_t last_size = ready_mutate_register((__processor_id_t*)&this);
-                this.cltr->procs.total += 1u;
-                insert_last(this.cltr->procs.actives, this);
-                // Adjust the ready queue size
-                ready_queue_grow( cltr );
-        // Unlock the RWlock
-        ready_mutate_unlock( last_size );
         __cfadbg_print_safe(runtime_core, "Kernel : core %p created\n", &this);
+}
 …
 // Not a ctor, it just preps the destruction but should not destroy members
 static void deinit(processor & this) {
-        // Lock the RWlock so no-one pushes/pops while we are changing the queue
-        uint_fast32_t last_size = ready_mutate_lock();
-                this.cltr->procs.total -= 1u;
-                remove(this);
-                // Adjust the ready queue size
-                ready_queue_shrink( this.cltr );
-        // Unlock the RWlock and unregister: we don't need the read_lock any more
-        ready_mutate_unregister((__processor_id_t*)&this, last_size );
         close(this.idle);
+}
 …
         cltr->nthreads -= 1;
         unlock(cltr->thread_list_lock);
+}
+static void register_tls( processor * this ) {
+        // Register and Lock the RWlock so no-one pushes/pops while we are changing the queue
+        uint_fast32_t last_size;
+        [this->unique_id, last_size] = ready_mutate_register();
+                this->cltr->procs.total += 1u;
+                insert_last(this->cltr->procs.actives, *this);
+                // Adjust the ready queue size
+                ready_queue_grow( this->cltr );
+        // Unlock the RWlock
+        ready_mutate_unlock( last_size );
+}
+static void unregister_tls( processor * this ) {
+        // Lock the RWlock so no-one pushes/pops while we are changing the queue
+        uint_fast32_t last_size = ready_mutate_lock();
+                this->cltr->procs.total -= 1u;
+                remove(*this);
+                // clear the cluster so nothing gets pushed to local queues
+                cluster * cltr = this->cltr;
+                this->cltr = 0p;
+                // Adjust the ready queue size
+                ready_queue_shrink( cltr );
+        // Unlock the RWlock and unregister: we don't need the read_lock any more
+        ready_mutate_unregister( this->unique_id, last_size );
+}

libcfa/src/concurrency/kernel_private.hfa

-                      r5407cdc
+                      r8d66610
 // Scheduler
-struct __attribute__((aligned(128))) __scheduler_lock_id_t;
 extern "C" {
 …
 // Lock-Free registering/unregistering of threads
 // Register a processor to a given cluster and get its unique id in return
 void register_proc_id( struct __processor_id_t * );
+unsigned register_proc_id( void );
 // Unregister a processor from a given cluster using its id, getting back the original pointer
 void unregister_proc_id( struct __processor_id_t * proc );
+void unregister_proc_id( unsigned );
 //=======================================================================
 …
+}
+// Cells use by the reader writer lock
+// while not generic it only relies on a opaque pointer
+struct __attribute__((aligned(128))) __scheduler_lock_id_t {
+        // Spin lock used as the underlying lock
+        volatile bool lock;
+        // Handle pointing to the proc owning this cell
+        // Used for allocating cells and debugging
+        __processor_id_t * volatile handle;
+        #ifdef __CFA_WITH_VERIFY__
+                // Debug, check if this is owned for reading
+                bool owned;
+        #endif
+};
+static_assert( sizeof(struct __scheduler_lock_id_t) <= __alignof(struct __scheduler_lock_id_t));
 //-----------------------------------------------------------------------
 …
         // writer lock
         volatile bool lock;
+        volatile bool write_lock;
         // data pointer
         __scheduler_lock_id_t * data;
+        volatile bool * volatile * data;
 };
 …
 static inline void ready_schedule_lock(void) with(*__scheduler_lock) {
         /* paranoid */ verify( ! __preemption_enabled() );
+        /* paranoid */ verify( kernelTLS().this_proc_id );
+        unsigned iproc = kernelTLS().this_proc_id->id;
+        /*paranoid*/ verify(data[iproc].handle == kernelTLS().this_proc_id);
+        /*paranoid*/ verify(iproc < ready);
+        /* paranoid */ verify( ! kernelTLS().in_sched_lock );
+        /* paranoid */ verify( data[kernelTLS().sched_id] == &kernelTLS().sched_lock );
+        /* paranoid */ verify( !kernelTLS().this_processor || kernelTLS().this_processor->unique_id == kernelTLS().sched_id );
         // Step 1 : make sure no writer are in the middle of the critical section
         while(__atomic_load_n(&lock, (int)__ATOMIC_RELAXED))
+        while(__atomic_load_n(&write_lock, (int)__ATOMIC_RELAXED))
                 Pause();
 …
         // Step 2 : acquire our local lock
         __atomic_acquire( &data[iproc].lock );
         /*paranoid*/ verify(data[iproc].lock);
+        __atomic_acquire( &kernelTLS().sched_lock );
+        /*paranoid*/ verify(kernelTLS().sched_lock);
         #ifdef __CFA_WITH_VERIFY__
                 // Debug, check if this is owned for reading
                 data[iproc].owned = true;
+                kernelTLS().in_sched_lock = true;
         #endif
+}
 …
 static inline void ready_schedule_unlock(void) with(*__scheduler_lock) {
         /* paranoid */ verify( ! __preemption_enabled() );
+        /* paranoid */ verify( kernelTLS().this_proc_id );
+        unsigned iproc = kernelTLS().this_proc_id->id;
+        /*paranoid*/ verify(data[iproc].handle == kernelTLS().this_proc_id);
+        /*paranoid*/ verify(iproc < ready);
+        /*paranoid*/ verify(data[iproc].lock);
+        /*paranoid*/ verify(data[iproc].owned);
+        /* paranoid */ verify( data[kernelTLS().sched_id] == &kernelTLS().sched_lock );
+        /* paranoid */ verify( !kernelTLS().this_processor || kernelTLS().this_processor->unique_id == kernelTLS().sched_id );
+        /* paranoid */ verify( kernelTLS().sched_lock );
+        /* paranoid */ verify( kernelTLS().in_sched_lock );
         #ifdef __CFA_WITH_VERIFY__
                 // Debug, check if this is owned for reading
                 data[iproc].owned = false;
+                kernelTLS().in_sched_lock = false;
         #endif
         __atomic_unlock(&data[iproc].lock);
+        __atomic_unlock(&kernelTLS().sched_lock);
+}
 …
         static inline bool ready_schedule_islocked(void) {
                 /* paranoid */ verify( ! __preemption_enabled() );
+                /*paranoid*/ verify( kernelTLS().this_proc_id );
+                __processor_id_t * proc = kernelTLS().this_proc_id;
+                return __scheduler_lock->data[proc->id].owned;
+                /* paranoid */ verify( (!kernelTLS().in_sched_lock) || kernelTLS().sched_lock );
+                return kernelTLS().sched_lock;
+        }
         static inline bool ready_mutate_islocked() {
                 return __scheduler_lock->lock;
+                return __scheduler_lock->write_lock;
+        }
 #endif
 …
 // Register a processor to a given cluster and get its unique id in return
 // For convenience, also acquires the lock
+static inline uint_fast32_t ready_mutate_register( struct __processor_id_t * proc ) {
+        register_proc_id( proc );
+        return ready_mutate_lock();
+static inline [unsigned, uint_fast32_t] ready_mutate_register() {
+        unsigned id = register_proc_id();
+        uint_fast32_t last = ready_mutate_lock();
+        return [id, last];
+}
 // Unregister a processor from a given cluster using its id, getting back the original pointer
 // assumes the lock is acquired
 static inline void ready_mutate_unregister( struct __processor_id_t * proc, uint_fast32_t last_s ) {
+static inline void ready_mutate_unregister( unsigned id, uint_fast32_t last_s ) {
         ready_mutate_unlock( last_s );
         unregister_proc_id( proc );
+        unregister_proc_id( id );
+}
 …
 // push thread onto a ready queue for a cluster
 // returns true if the list was previously empty, false otherwise
 __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd);
+__attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd, bool local);
 //-----------------------------------------------------------------------

libcfa/src/concurrency/locks.cfa

-                      r5407cdc
+                      r8d66610
                 alarm_node_t alarm_node;
                 condition_variable(L) * cond;
                 info_thread(L) * i;
+                info_thread(L) * info_thd;
         };
         void ?{}( alarm_node_wrap(L) & this, Time alarm, Duration period, Alarm_Callback callback, condition_variable(L) * c, info_thread(L) * i ) {
+        void ?{}( alarm_node_wrap(L) & this, Duration alarm, Duration period, Alarm_Callback callback, condition_variable(L) * c, info_thread(L) * i ) {
                 this.alarm_node{ callback, alarm, period };
                 this.cond = c;
                 this.i = i;
+                this.info_thd = i;
+        }
 …
                 //      may still be called after a thread has been removed from the queue but
                 //      before the alarm is unregistered
                 if ( listed(i) ) {      // is thread on queue
                         i->signalled = false;
+                if ( listed(info_thd) ) {       // is thread on queue
+                        info_thd->signalled = false;
                         // remove this thread O(1)
                         remove( cond->blocked_threads, *i );
+                        remove( cond->blocked_threads, *info_thd );
                         cond->count--;
                         if( i->lock ) {
+                        if( info_thd->lock ) {
                                 // call lock's on_notify if a lock was passed
                                 on_notify(*i->lock, i->t);
+                                on_notify(*info_thd->lock, info_thd->t);
                         } else {
                                 // otherwise wake thread
                                 unpark( i->t );
+                                unpark( info_thd->t );
+                        }
+                }
 …
         // helper for wait()'s' with a timeout
         void queue_info_thread_timeout( condition_variable(L) & this, info_thread(L) & info, Time t ) with(this) {
+        void queue_info_thread_timeout( condition_variable(L) & this, info_thread(L) & info, Duration t, Alarm_Callback callback ) with(this) {
                 lock( lock __cfaabi_dbg_ctx2 );
                 size_t recursion_count = queue_and_get_recursion(this, &info);
                 alarm_node_wrap(L) node_wrap = { t, 0`s, alarm_node_wrap_cast, &this, &info };
+                alarm_node_wrap(L) node_wrap = { t, 0`s, callback, &this, &info };
                 register_self( &node_wrap.alarm_node );
                 unlock( lock );
 …
         #define WAIT_TIME( u, l, t ) \
                 info_thread( L ) i = { active_thread(), u, l }; \
                 queue_info_thread_timeout(this, i, t ); \
+                queue_info_thread_timeout(this, i, t, alarm_node_wrap_cast ); \
                 return i.signalled;
 …
         void wait( condition_variable(L) & this, L & l, uintptr_t info ) with(this) { WAIT( info, &l ) }
+        bool wait( condition_variable(L) & this, Duration duration                        ) with(this) { WAIT_TIME( 0   , 0p , __kernel_get_time() + duration ) }
+        bool wait( condition_variable(L) & this, uintptr_t info, Duration duration        ) with(this) { WAIT_TIME( info, 0p , __kernel_get_time() + duration ) }
+        bool wait( condition_variable(L) & this, Time time                                ) with(this) { WAIT_TIME( 0   , 0p , time ) }
+        bool wait( condition_variable(L) & this, uintptr_t info, Time time                ) with(this) { WAIT_TIME( info, 0p , time ) }
+        bool wait( condition_variable(L) & this, L & l, Duration duration                 ) with(this) { WAIT_TIME( 0   , &l , __kernel_get_time() + duration ) }
+        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, &l , __kernel_get_time() + duration ) }
+        bool wait( condition_variable(L) & this, L & l, Time time                         ) with(this) { WAIT_TIME( 0   , &l , time ) }
+        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time         ) with(this) { WAIT_TIME( info, &l , time ) }
+        bool wait( condition_variable(L) & this, Duration duration                        ) with(this) { WAIT_TIME( 0   , 0p , duration ) }
+        bool wait( condition_variable(L) & this, uintptr_t info, Duration duration        ) with(this) { WAIT_TIME( info, 0p , duration ) }
+        bool wait( condition_variable(L) & this, L & l, Duration duration                 ) with(this) { WAIT_TIME( 0   , &l , duration ) }
+        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration ) with(this) { WAIT_TIME( info, &l , duration ) }
+}

libcfa/src/concurrency/locks.hfa

-                      r5407cdc
+                      r8d66610
         bool wait( condition_variable(L) & this, Duration duration );
         bool wait( condition_variable(L) & this, uintptr_t info, Duration duration );
-        bool wait( condition_variable(L) & this, Time time );
-        bool wait( condition_variable(L) & this, uintptr_t info, Time time );
         void wait( condition_variable(L) & this, L & l );
 …
         bool wait( condition_variable(L) & this, L & l, Duration duration );
         bool wait( condition_variable(L) & this, L & l, uintptr_t info, Duration duration );
+        bool wait( condition_variable(L) & this, L & l, Time time );
+        bool wait( condition_variable(L) & this, L & l, uintptr_t info, Time time );
+}
+}

libcfa/src/concurrency/preemption.cfa

-                      r5407cdc
+                      r8d66610
 #include "preemption.hfa"
 #include <assert.h>
 …
 #include <limits.h>                                                                             // PTHREAD_STACK_MIN
+#include "bits/debug.hfa"
 #include "bits/signal.hfa"
 #include "kernel_private.hfa"
 …
 static inline alarm_node_t * get_expired( alarm_list_t * alarms, Time currtime ) {
         if( ! & (*alarms)`first ) return 0p;                                            // If no alarms return null
         if( (*alarms)`first.alarm >= currtime ) return 0p;      // If alarms head not expired return null
+        if( (*alarms)`first.timeval >= currtime ) return 0p;    // If alarms head not expired return null
         return pop(alarms);                                                                     // Otherwise just pop head
+}
 …
                 if( period > 0 ) {
                         __cfadbg_print_buffer_local( preemption, " KERNEL: alarm period is %lu.\n", period`ns );
                         node->alarm = currtime + period;    // Alarm is periodic, add currtime to it (used cached current time)
+                        node->timeval = currtime + period;  // Alarm is periodic, add currtime to it (used cached current time)
                         insert( alarms, node );             // Reinsert the node for the next time it triggers
+                }
 …
         // If there are still alarms pending, reset the timer
         if( & (*alarms)`first ) {
+                Duration delta = (*alarms)`first.alarm - currtime;
+                Duration capped = max(delta, 50`us);
+                __kernel_set_timer( capped );
+                Duration delta = (*alarms)`first.timeval - currtime;
+                __kernel_set_timer( delta );
+        }
+}
 …
         // Alarms need to be enabled
         if ( duration > 0 && ! alarm->set ) {
                 alarm->alarm = __kernel_get_time() + duration;
                 alarm->period = duration;
+                alarm->initial = duration;
+                alarm->period  = duration;
                 register_self( alarm );
+        }
 …
         else if ( duration == 0 && alarm->set ) {
                 unregister_self( alarm );
                 alarm->alarm = 0;
                 alarm->period = 0;
+                alarm->initial = 0;
+                alarm->period  = 0;
+        }
         // If alarm is different from previous, change it
         else if ( duration > 0 && alarm->period != duration ) {
                 unregister_self( alarm );
                 alarm->alarm = __kernel_get_time() + duration;
                 alarm->period = duration;
+                alarm->initial = duration;
+                alarm->period  = duration;
                 register_self( alarm );
+        }
 …
         // Notify the alarm thread of the shutdown
+        sigval val = { 1 };
+        sigval val;
+        val.sival_int = 0;
         pthread_sigqueue( alarm_thread, SIGALRM, val );
 …
 // Used by thread to control when they want to receive preemption signals
 void ?{}( preemption_scope & this, processor * proc ) {
         (this.alarm){ proc, (Time){ 0 }, 0`s };
+        (this.alarm){ proc, 0`s, 0`s };
         this.proc = proc;
         this.proc->preemption_alarm = &this.alarm;
 …
 // Waits on SIGALRM and send SIGUSR1 to whom ever needs it
 static void * alarm_loop( __attribute__((unused)) void * args ) {
+        __processor_id_t id;
+        register_proc_id(&id);
+        __cfaabi_tls.this_proc_id = &id;
+        unsigned id = register_proc_id();
         // Block sigalrms to control when they arrive
 …
                 siginfo_t info;
                 int sig = sigwaitinfo( &mask, &info );
+                __cfadbg_print_buffer_decl ( preemption, " KERNEL: sigwaitinfo returned %d, c: %d, v: %d\n", sig, info.si_code, info.si_value.sival_int );
+                __cfadbg_print_buffer_local( preemption, " KERNEL: SI_QUEUE %d, SI_TIMER %d, SI_KERNEL %d\n", SI_QUEUE, SI_TIMER, SI_KERNEL );
                 if( sig < 0 ) {
 …
                                 case EAGAIN :
                                 case EINTR :
                                         {__cfaabi_dbg_print_buffer_decl( " KERNEL: Spurious wakeup %d.\n", err );}
+                                        {__cfadbg_print_buffer_local( preemption, " KERNEL: Spurious wakeup %d.\n", err );}
                                         continue;
                                 case EINVAL :
 …
                 assertf(sig == SIGALRM, "Kernel Internal Error, sigwait: Unexpected signal %d (%d : %d)\n", sig, info.si_code, info.si_value.sival_int);
-                // __cfaabi_dbg_print_safe( "Kernel : Caught alarm from %d with %d\n", info.si_code, info.si_value.sival_int );
                 // Switch on the code (a.k.a. the sender) to
                 switch( info.si_code )
+                {
+                // Signal was not sent by the kernel but by an other thread
+                case SI_QUEUE:
+                        // other threads may signal the alarm thread to shut it down
+                        // or to manual cause the preemption tick
+                        // use info.si_value and handle the case here
+                        switch( info.si_value.sival_int ) {
+                        case 0:
+                                goto EXIT;
+                        default:
+                                abort( "SI_QUEUE with val %d", info.si_value.sival_int);
+                        }
+                        // fallthrough
                 // Timers can apparently be marked as sent for the kernel
                 // In either case, tick preemption
 …
                         unlock( event_kernel->lock );
                         break;
-                // Signal was not sent by the kernel but by an other thread
-                case SI_QUEUE:
-                        // For now, other thread only signal the alarm thread to shut it down
-                        // If this needs to change use info.si_value and handle the case here
-                        goto EXIT;
+                }
+        }
 …
 EXIT:
         __cfaabi_dbg_print_safe( "Kernel : Preemption thread stopping\n" );
         register_proc_id(&id);
+        unregister_proc_id(id);
         return 0p;

libcfa/src/concurrency/ready_queue.cfa

-                      r5407cdc
+                      r8d66610
 // #define __CFA_DEBUG_PRINT_READY_QUEUE__
-// #define USE_MPSC
 #define USE_RELAXED_FIFO
 …
         this.alloc = 0;
         this.ready = 0;
-        this.lock  = false;
         this.data  = alloc(this.max);
+        /*paranoid*/ verify( 0 == (((uintptr_t)(this.data    )) % 64) );
+        /*paranoid*/ verify( 0 == (((uintptr_t)(this.data + 1)) % 64) );
+        this.write_lock  = false;
         /*paranoid*/ verify(__atomic_is_lock_free(sizeof(this.alloc), &this.alloc));
         /*paranoid*/ verify(__atomic_is_lock_free(sizeof(this.ready), &this.ready));
 …
+}
-void ?{}( __scheduler_lock_id_t & this, __processor_id_t * proc ) {
-        this.handle = proc;
-        this.lock   = false;
-        #ifdef __CFA_WITH_VERIFY__
-                this.owned  = false;
-        #endif
+}
 //=======================================================================
 // Lock-Free registering/unregistering of threads
 void register_proc_id( struct __processor_id_t * proc ) with(*__scheduler_lock) {
+unsigned register_proc_id( void ) with(*__scheduler_lock) {
         __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p for RW-Lock\n", proc);
+        bool * handle = (bool *)&kernelTLS().sched_lock;
         // Step - 1 : check if there is already space in the data
 …
         // Check among all the ready
         for(uint_fast32_t i = 0; i < s; i++) {
+                __processor_id_t * null = 0p; // Re-write every loop since compare thrashes it
+                if( __atomic_load_n(&data[i].handle, (int)__ATOMIC_RELAXED) == null
+                        && __atomic_compare_exchange_n( &data[i].handle, &null, proc, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
+                        /*paranoid*/ verify(i < ready);
+                        /*paranoid*/ verify(0 == (__alignof__(data[i]) % cache_line_size));
+                        /*paranoid*/ verify((((uintptr_t)&data[i]) % cache_line_size) == 0);
+                        proc->id = i;
+                bool * volatile * cell = (bool * volatile *)&data[i]; // Cforall is bugged and the double volatiles causes problems
+                /* paranoid */ verify( handle != *cell );
+                bool * null = 0p; // Re-write every loop since compare thrashes it
+                if( __atomic_load_n(cell, (int)__ATOMIC_RELAXED) == null
+                        && __atomic_compare_exchange_n( cell, &null, handle, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
+                        /* paranoid */ verify(i < ready);
+                        /* paranoid */ verify( (kernelTLS().sched_id = i, true) );
+                        return i;
+                }
+        }
 …
         // Step - 3 : Mark space as used and then publish it.
+        __scheduler_lock_id_t * storage = (__scheduler_lock_id_t *)&data[n];
+        (*storage){ proc };
+        data[n] = handle;
         while() {
                 unsigned copy = n;
 …
         // Return new spot.
+        /*paranoid*/ verify(n < ready);
+        /*paranoid*/ verify(__alignof__(data[n]) == (2 * cache_line_size));
+        /*paranoid*/ verify((((uintptr_t)&data[n]) % cache_line_size) == 0);
+        proc->id = n;
+}
+void unregister_proc_id( struct __processor_id_t * proc ) with(*__scheduler_lock) {
+        unsigned id = proc->id;
+        /*paranoid*/ verify(id < ready);
+        /*paranoid*/ verify(proc == __atomic_load_n(&data[id].handle, __ATOMIC_RELAXED));
+        __atomic_store_n(&data[id].handle, 0p, __ATOMIC_RELEASE);
+        /* paranoid */ verify(n < ready);
+        /* paranoid */ verify( (kernelTLS().sched_id = n, true) );
+        return n;
+}
+void unregister_proc_id( unsigned id ) with(*__scheduler_lock) {
+        /* paranoid */ verify(id < ready);
+        /* paranoid */ verify(id == kernelTLS().sched_id);
+        /* paranoid */ verify(data[id] == &kernelTLS().sched_lock);
+        bool * volatile * cell = (bool * volatile *)&data[id]; // Cforall is bugged and the double volatiles causes problems
+        __atomic_store_n(cell, 0p, __ATOMIC_RELEASE);
         __cfadbg_print_safe(ready_queue, "Kernel : Unregister proc %p\n", proc);
 …
 uint_fast32_t ready_mutate_lock( void ) with(*__scheduler_lock) {
         /* paranoid */ verify( ! __preemption_enabled() );
+        /* paranoid */ verify( ! kernelTLS().sched_lock );
         // Step 1 : lock global lock
         // It is needed to avoid processors that register mid Critical-Section
         //   to simply lock their own lock and enter.
         __atomic_acquire( &lock );
+        __atomic_acquire( &write_lock );
         // Step 2 : lock per-proc lock
 …
         uint_fast32_t s = ready;
         for(uint_fast32_t i = 0; i < s; i++) {
+                __atomic_acquire( &data[i].lock );
+                volatile bool * llock = data[i];
+                if(llock) __atomic_acquire( llock );
+        }
 …
         // Alternative solution : return s in write_lock and pass it to write_unlock
         for(uint_fast32_t i = 0; i < last_s; i++) {
                 verify(data[i].lock);
                 __atomic_store_n(&data[i].lock, (bool)false, __ATOMIC_RELEASE);
+                volatile bool * llock = data[i];
+                if(llock) __atomic_store_n(llock, (bool)false, __ATOMIC_RELEASE);
+        }
         // Step 2 : release global lock
         /*paranoid*/ assert(true == lock);
         __atomic_store_n(&lock, (bool)false, __ATOMIC_RELEASE);
+        /*paranoid*/ assert(true == write_lock);
+        __atomic_store_n(&write_lock, (bool)false, __ATOMIC_RELEASE);
         /* paranoid */ verify( ! __preemption_enabled() );
 …
+        }
         __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
+        __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd, bool push_local) with (cltr->ready_queue) {
                 __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
                 const bool external = (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
+                const bool external = !push_local || (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
                 /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
-                // write timestamp
-                thrd->link.ts = rdtscl();
                 bool local;
 …
                         #endif
-                #if defined(USE_MPSC)
-                        // mpsc always succeeds
-                } while( false );
-                #else
                         // If we can't lock it retry
                 } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-                #endif
                 // Actually push it
                 push(lanes.data[i], thrd);
+                #if !defined(USE_MPSC)
+                        // Unlock and return
+                        __atomic_unlock( &lanes.data[i].lock );
+                #endif
+                // Unlock and return
+                __atomic_unlock( &lanes.data[i].lock );
                 // Mark the current index in the tls rng instance as having an item
 …
 #endif
 #if defined(USE_WORK_STEALING)
         __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd) with (cltr->ready_queue) {
+        __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd, bool push_local) with (cltr->ready_queue) {
                 __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
+                const bool external = (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
+                // #define USE_PREFERRED
+                #if !defined(USE_PREFERRED)
+                const bool external = !push_local || (!kernelTLS().this_processor) || (cltr != kernelTLS().this_processor->cltr);
                 /* paranoid */ verify(external || kernelTLS().this_processor->rdq.id < lanes.count );
+                // write timestamp
+                thrd->link.ts = rdtscl();
+                #else
+                        unsigned preferred = thrd->preferred;
+                        const bool external = push_local || (!kernelTLS().this_processor) || preferred == -1u || thrd->curr_cluster != cltr;
+                        /* paranoid */ verifyf(external || preferred < lanes.count, "Invalid preferred queue %u for %u lanes", preferred, lanes.count );
+                        unsigned r = preferred % READYQ_SHARD_FACTOR;
+                        const unsigned start = preferred - r;
+                #endif
                 // Try to pick a lane and lock it
 …
+                        }
                         else {
+                                processor * proc = kernelTLS().this_processor;
+                                unsigned r = proc->rdq.its++;
+                                i =  proc->rdq.id + (r % READYQ_SHARD_FACTOR);
+                                #if !defined(USE_PREFERRED)
+                                        processor * proc = kernelTLS().this_processor;
+                                        unsigned r = proc->rdq.its++;
+                                        i =  proc->rdq.id + (r % READYQ_SHARD_FACTOR);
+                                #else
+                                        i = start + (r++ % READYQ_SHARD_FACTOR);
+                                #endif
+                        }
-                #if defined(USE_MPSC)
-                        // mpsc always succeeds
-                } while( false );
-                #else
                         // If we can't lock it retry
                 } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
-                #endif
                 // Actually push it
                 push(lanes.data[i], thrd);
+                #if !defined(USE_MPSC)
+                        // Unlock and return
+                        __atomic_unlock( &lanes.data[i].lock );
+                #endif
+                // Unlock and return
+                __atomic_unlock( &lanes.data[i].lock );
                 #if !defined(__CFA_NO_STATISTICS__)
 …
                 if(proc->rdq.target == -1u) {
+                        unsigned long long min = ts(lanes.data[proc->rdq.id]);
+                        for(int i = 0; i < READYQ_SHARD_FACTOR; i++) {
+                                unsigned long long tsc = ts(lanes.data[proc->rdq.id + i]);
+                                if(tsc < min) min = tsc;
+                        }
+                        proc->rdq.cutoff = min;
                         proc->rdq.target = __tls_rand() % lanes.count;
-                        unsigned it1  = proc->rdq.itr;
-                        unsigned it2  = proc->rdq.itr + 1;
-                        unsigned idx1 = proc->rdq.id + (it1 % READYQ_SHARD_FACTOR);
-                        unsigned idx2 = proc->rdq.id + (it2 % READYQ_SHARD_FACTOR);
-                        unsigned long long tsc1 = ts(lanes.data[idx1]);
-                        unsigned long long tsc2 = ts(lanes.data[idx2]);
-                        proc->rdq.cutoff = min(tsc1, tsc2);
-                        if(proc->rdq.cutoff == 0) proc->rdq.cutoff = -1ull;
+                }
                 else {
                         unsigned target = proc->rdq.target;
                         proc->rdq.target = -1u;
+                        if(lanes.tscs[target].tv < proc->rdq.cutoff) {
+                        const unsigned long long bias = 0; //2_500_000_000;
+                        const unsigned long long cutoff = proc->rdq.cutoff > bias ? proc->rdq.cutoff - bias : proc->rdq.cutoff;
+                        if(lanes.tscs[target].tv < cutoff && ts(lanes.data[target]) < cutoff) {
                                 $thread * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
                                 if(t) return t;
 …
                 for(READYQ_SHARD_FACTOR) {
                         unsigned i = proc->rdq.id + (--proc->rdq.itr % READYQ_SHARD_FACTOR);
+                        unsigned i = proc->rdq.id + (proc->rdq.itr++ % READYQ_SHARD_FACTOR);
                         if($thread * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t;
+                }
 …
         // If list looks empty retry
         if( is_empty(lane) ) {
-                __STATS( stats.espec++; )
                 return 0p;
+        }
 …
         // If we can't get the lock retry
         if( !__atomic_try_acquire(&lane.lock) ) {
-                __STATS( stats.elock++; )
                 return 0p;
+        }
 …
         if( is_empty(lane) ) {
                 __atomic_unlock(&lane.lock);
-                __STATS( stats.eempty++; )
                 return 0p;
+        }
 …
         // Actually pop the list
         struct $thread * thrd;
+        thrd = pop(lane);
+        unsigned long long tsv;
+        [thrd, tsv] = pop(lane);
         /* paranoid */ verify(thrd);
+        /* paranoid */ verify(tsv);
         /* paranoid */ verify(lane.lock);
 …
         #if defined(USE_WORK_STEALING)
                 lanes.tscs[w].tv = thrd->link.ts;
+                lanes.tscs[w].tv = tsv;
         #endif
+        thrd->preferred = w;
         // return the popped thread
 …
 // Check that all the intrusive queues in the data structure are still consistent
 static void check( __ready_queue_t & q ) with (q) {
         #if defined(__CFA_WITH_VERIFY__) && !defined(USE_MPSC)
+        #if defined(__CFA_WITH_VERIFY__)
+                {
                         for( idx ; lanes.count ) {
 …
                                 assert(!lanes.data[idx].lock);
+                                assert(head(sl)->link.prev == 0p );
+                                assert(head(sl)->link.next->link.prev == head(sl) );
+                                assert(tail(sl)->link.next == 0p );
+                                assert(tail(sl)->link.prev->link.next == tail(sl) );
+                                if(is_empty(sl)) {
+                                        assert(tail(sl)->link.prev == head(sl));
+                                        assert(head(sl)->link.next == tail(sl));
+                                } else {
+                                        assert(tail(sl)->link.prev != head(sl));
+                                        assert(head(sl)->link.next != tail(sl));
+                                }
+                                        if(is_empty(sl)) {
+                                                assert( sl.anchor.next == 0p );
+                                                assert( sl.anchor.ts   == 0  );
+                                                assert( mock_head(sl)  == sl.prev );
+                                        } else {
+                                                assert( sl.anchor.next != 0p );
+                                                assert( sl.anchor.ts   != 0  );
+                                                assert( mock_head(sl)  != sl.prev );
+                                        }
+                        }
+                }
 …
 // fixes the list so that the pointers back to anchors aren't left dangling
 static inline void fix(__intrusive_lane_t & ll) {
+        #if !defined(USE_MPSC)
+                // if the list is not empty then follow he pointer and fix its reverse
+                if(!is_empty(ll)) {
+                        head(ll)->link.next->link.prev = head(ll);
+                        tail(ll)->link.prev->link.next = tail(ll);
+                }
+                // Otherwise just reset the list
+                else {
+                        verify(tail(ll)->link.next == 0p);
+                        tail(ll)->link.prev = head(ll);
+                        head(ll)->link.next = tail(ll);
+                        verify(head(ll)->link.prev == 0p);
+                }
+        #endif
+}
+static void assign_list(unsigned & value, dlist(processor, processor) & list, unsigned count) {
+                        if(is_empty(ll)) {
+                                verify(ll.anchor.next == 0p);
+                                ll.prev = mock_head(ll);
+                        }
+}
+static void assign_list(unsigned & value, dlist(processor) & list, unsigned count) {
         processor * it = &list`first;
         for(unsigned i = 0; i < count; i++) {
 …
                 lanes.tscs = alloc(lanes.count, lanes.tscs`realloc);
                 for(i; lanes.count) {
+                        lanes.tscs[i].tv = ts(lanes.data[i]);
+                        unsigned long long tsc = ts(lanes.data[i]);
+                        lanes.tscs[i].tv = tsc != 0 ? tsc : rdtscl();
+                }
         #endif
 …
                         while(!is_empty(lanes.data[idx])) {
                                 struct $thread * thrd;
+                                thrd = pop(lanes.data[idx]);
+                                push(cltr, thrd);
+                                unsigned long long _;
+                                [thrd, _] = pop(lanes.data[idx]);
+                                push(cltr, thrd, true);
                                 // for printing count the number of displaced threads
 …
         /* paranoid */ verify( ready_mutate_islocked() );
+}
+#if !defined(__CFA_NO_STATISTICS__)
+        unsigned cnt(const __ready_queue_t & this, unsigned idx) {
+                /* paranoid */ verify(this.lanes.count > idx);
+                return this.lanes.data[idx].cnt;
+        }
+#endif

libcfa/src/concurrency/ready_subqueue.hfa

-                      r5407cdc
+                      r8d66610
 // Intrusives lanes which are used by the relaxed ready queue
 struct __attribute__((aligned(128))) __intrusive_lane_t {
+        #if defined(USE_MPSC)
+                mpsc_queue($thread) queue;
+                __attribute__((aligned(128)))
+        #else
+                // anchor for the head and the tail of the queue
+                __attribute__((aligned(128))) struct __sentinel_t {
+                        // Link lists fields
+                        // instrusive link field for threads
+                        // must be exactly as in $thread
+                        __thread_desc_link link;
+                } before, after;
+        #endif
+        struct $thread * prev;
         // spin lock protecting the queue
         volatile bool lock;
+        // Optional statistic counters
+        #if !defined(__CFA_NO_SCHED_STATS__)
+                struct __attribute__((aligned(64))) {
+                        // difference between number of push and pops
+                        ssize_t diff;
+        __thread_desc_link anchor;
+                        // total number of pushes and pops
+                        size_t  push;
+                        size_t  pop ;
+                } stat;
+        #if !defined(__CFA_NO_STATISTICS__)
+                unsigned cnt;
         #endif
 };
-void  ?{}(__intrusive_lane_t & this);
-void ^?{}(__intrusive_lane_t & this);
 // Get the head pointer (one before the first element) from the anchor
+static inline $thread * head(const __intrusive_lane_t & this) {
+        #if defined(USE_MPSC)
+                return this.queue.head;
+        #else
+                $thread * rhead = ($thread *)(
+                        (uintptr_t)( &this.before ) - offsetof( $thread, link )
+                );
+                /* paranoid */ verify(rhead);
+                return rhead;
+        #endif
+}
+// Get the tail pointer (one after the last element) from the anchor
+static inline $thread * tail(const __intrusive_lane_t & this) {
+        #if defined(USE_MPSC)
+                return this.queue.tail;
+        #else
+                $thread * rtail = ($thread *)(
+                        (uintptr_t)( &this.after ) - offsetof( $thread, link )
+                );
+                /* paranoid */ verify(rtail);
+                return rtail;
+        #endif
+static inline $thread * mock_head(const __intrusive_lane_t & this) {
+        $thread * rhead = ($thread *)(
+                (uintptr_t)( &this.anchor ) - __builtin_offsetof( $thread, link )
+        );
+        return rhead;
+}
 …
 void ?{}( __intrusive_lane_t & this ) {
         this.lock = false;
+        this.prev = mock_head(this);
+        this.anchor.next = 0p;
+        this.anchor.ts   = 0;
+        #if !defined(__CFA_NO_STATISTICS__)
+                this.cnt  = 0;
+        #endif
+        #if !defined(USE_MPSC)
+                this.before.link.prev = 0p;
+                this.before.link.next = tail(this);
+                this.before.link.ts   = 0;
+                this.after .link.prev = head(this);
+                this.after .link.next = 0p;
+                this.after .link.ts   = 0;
+                #if !defined(__CFA_NO_SCHED_STATS__)
+                        this.stat.diff = 0;
+                        this.stat.push = 0;
+                        this.stat.pop  = 0;
+                #endif
+                // We add a boat-load of assertions here because the anchor code is very fragile
+                /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
+                /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
+                /* paranoid */ verify(head(this)->link.prev == 0p );
+                /* paranoid */ verify(head(this)->link.next == tail(this) );
+                /* paranoid */ verify(tail(this)->link.next == 0p );
+                /* paranoid */ verify(tail(this)->link.prev == head(this) );
+                /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
+                /* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
+                /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
+                /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
+                /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
+                /* paranoid */ verify(__alignof__(this) == 128);
+                /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
+        #endif
+        // We add a boat-load of assertions here because the anchor code is very fragile
+        /* paranoid */ _Static_assert( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) );
+        /* paranoid */ verify( offsetof( $thread, link ) == offsetof(__intrusive_lane_t, anchor) );
+        /* paranoid */ verify( ((uintptr_t)( mock_head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.anchor) );
+        /* paranoid */ verify( &mock_head(this)->link.next == &this.anchor.next );
+        /* paranoid */ verify( &mock_head(this)->link.ts   == &this.anchor.ts   );
+        /* paranoid */ verify( mock_head(this)->link.next == 0p );
+        /* paranoid */ verify( mock_head(this)->link.ts   == 0  );
+        /* paranoid */ verify( mock_head(this) == this.prev );
+        /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 );
+        /* paranoid */ verify( __alignof__(this) == 128 );
+        /* paranoid */ verifyf( ((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128) );
+}
 // Dtor is trivial
 void ^?{}( __intrusive_lane_t & this ) {
+        #if !defined(USE_MPSC)
+                // Make sure the list is empty
+                /* paranoid */ verify(head(this)->link.prev == 0p );
+                /* paranoid */ verify(head(this)->link.next == tail(this) );
+                /* paranoid */ verify(tail(this)->link.next == 0p );
+                /* paranoid */ verify(tail(this)->link.prev == head(this) );
+        #endif
+        // Make sure the list is empty
+        /* paranoid */ verify( this.anchor.next == 0p );
+        /* paranoid */ verify( this.anchor.ts   == 0  );
+        /* paranoid */ verify( mock_head(this)  == this.prev );
+}
 // Push a thread onto this lane
 // returns true of lane was empty before push, false otherwise
+bool push(__intrusive_lane_t & this, $thread * node) {
+        #if defined(USE_MPSC)
+                inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
+                        return this->link.next;
+                }
+                push(this.queue, node);
+        #else
+                #if defined(__CFA_WITH_VERIFY__)
+                        /* paranoid */ verify(this.lock);
+                        /* paranoid */ verify(node->link.ts != 0);
+                        /* paranoid */ verify(node->link.next == 0p);
+                        /* paranoid */ verify(node->link.prev == 0p);
+                        /* paranoid */ verify(tail(this)->link.next == 0p);
+                        /* paranoid */ verify(head(this)->link.prev == 0p);
+static inline void push( __intrusive_lane_t & this, $thread * node ) {
+        /* paranoid */ verify( this.lock );
+        /* paranoid */ verify( node->link.next == 0p );
+        /* paranoid */ verify( node->link.ts   == 0  );
+        /* paranoid */ verify( this.prev->link.next == 0p );
+        /* paranoid */ verify( this.prev->link.ts   == 0  );
+        if( this.anchor.next == 0p ) {
+                /* paranoid */ verify( this.anchor.next == 0p );
+                /* paranoid */ verify( this.anchor.ts   == 0  );
+                /* paranoid */ verify( this.prev == mock_head( this ) );
+        } else {
+                /* paranoid */ verify( this.anchor.next != 0p );
+                /* paranoid */ verify( this.anchor.ts   != 0  );
+                /* paranoid */ verify( this.prev != mock_head( this ) );
+        }
+                        if(this.before.link.ts == 0l) {
+                                /* paranoid */ verify(tail(this)->link.prev == head(this));
+                                /* paranoid */ verify(head(this)->link.next == tail(this));
+                        } else {
+                                /* paranoid */ verify(tail(this)->link.prev != head(this));
+                                /* paranoid */ verify(head(this)->link.next != tail(this));
+                        }
+                #endif
+                // Get the relevant nodes locally
+                $thread * tail = tail(this);
+                $thread * prev = tail->link.prev;
+                // Do the push
+                node->link.next = tail;
+                node->link.prev = prev;
+                prev->link.next = node;
+                tail->link.prev = node;
+                // Update stats
+                #if !defined(__CFA_NO_SCHED_STATS__)
+                        this.stat.diff++;
+                        this.stat.push++;
+                #endif
+                verify(node->link.next == tail(this));
+                // Check if the queue used to be empty
+                if(this.before.link.ts == 0l) {
+                        this.before.link.ts = node->link.ts;
+                        /* paranoid */ verify(node->link.prev == head(this));
+                        return true;
+                }
+                return false;
+        // Get the relevant nodes locally
+        this.prev->link.next = node;
+        this.prev->link.ts   = rdtscl();
+        this.prev = node;
+        #if !defined(__CFA_NO_STATISTICS__)
+                this.cnt++;
         #endif
+}
 …
 // returns popped
 // returns true of lane was empty before push, false otherwise
+$thread * pop(__intrusive_lane_t & this) {
+        /* paranoid */ verify(this.lock);
+        #if defined(USE_MPSC)
+                inline $thread * volatile & ?`next ( $thread * this )  __attribute__((const)) {
+                        return this->link.next;
+                }
+                return pop(this.queue);
+        #else
+                /* paranoid */ verify(this.before.link.ts != 0ul);
+static inline [* $thread, unsigned long long] pop( __intrusive_lane_t & this ) {
+        /* paranoid */ verify( this.lock );
+        /* paranoid */ verify( this.anchor.next != 0p );
+        /* paranoid */ verify( this.anchor.ts   != 0  );
+                // Get anchors locally
+                $thread * head = head(this);
+                $thread * tail = tail(this);
+        // Get the relevant nodes locally
+        unsigned long long ts = this.anchor.ts;
+        $thread * node = this.anchor.next;
+        this.anchor.next = node->link.next;
+        this.anchor.ts   = node->link.ts;
+        bool is_empty = this.anchor.ts == 0;
+        node->link.next = 0p;
+        node->link.ts   = 0;
+        #if !defined(__CFA_NO_STATISTICS__)
+                this.cnt--;
+        #endif
+                // Get the relevant nodes locally
+                $thread * node = head->link.next;
+                $thread * next = node->link.next;
+        // Update head time stamp
+        if(is_empty) this.prev = mock_head( this );
+                /* paranoid */ verify(node != tail);
+                /* paranoid */ verify(node);
+                // Do the pop
+                head->link.next = next;
+                next->link.prev = head;
+                node->link.next = 0p;
+                node->link.prev = 0p;
+                // Update head time stamp
+                this.before.link.ts = next->link.ts;
+                // Update stats
+                #ifndef __CFA_NO_SCHED_STATS__
+                        this.stat.diff--;
+                        this.stat.pop ++;
+                #endif
+                // Check if we emptied list and return accordingly
+                /* paranoid */ verify(tail(this)->link.next == 0p);
+                /* paranoid */ verify(head(this)->link.prev == 0p);
+                if(next == tail) {
+                        /* paranoid */ verify(this.before.link.ts == 0);
+                        /* paranoid */ verify(tail(this)->link.prev == head(this));
+                        /* paranoid */ verify(head(this)->link.next == tail(this));
+                        return node;
+                }
+                else {
+                        /* paranoid */ verify(next->link.ts != 0);
+                        /* paranoid */ verify(tail(this)->link.prev != head(this));
+                        /* paranoid */ verify(head(this)->link.next != tail(this));
+                        /* paranoid */ verify(this.before.link.ts != 0);
+                        return node;
+                }
+        #endif
+        /* paranoid */ verify( node->link.next == 0p );
+        /* paranoid */ verify( node->link.ts   == 0  );
+        return [node, ts];
+}
 // Check whether or not list is empty
 static inline bool is_empty(__intrusive_lane_t & this) {
+        #if defined(USE_MPSC)
+                return this.queue.head == 0p;
+        #else
+                // Cannot verify here since it may not be locked
+                return this.before.link.ts == 0;
+        #endif
+        return this.anchor.ts == 0;
+}
 // Return the timestamp
 static inline unsigned long long ts(__intrusive_lane_t & this) {
+        #if defined(USE_MPSC)
+                $thread * tl = this.queue.head;
+                if(!tl) return -1ull;
+                return tl->link.ts;
+        #else
+                // Cannot verify here since it may not be locked
+                return this.before.link.ts;
+        #endif
+        // Cannot verify here since it may not be locked
+        return this.anchor.ts;
+}
-// Aligned timestamps which are used by the relaxed ready queue
-struct __attribute__((aligned(128))) __timestamp_t {
-        volatile unsigned long long tv;
-};
-void  ?{}(__timestamp_t & this) { this.tv = 0; }
-void ^?{}(__timestamp_t & this) {}

libcfa/src/concurrency/stats.cfa

-                      r5407cdc
+                      r8d66610
                 stats->ready.pop.local .attempt = 0;
                 stats->ready.pop.local .success = 0;
-                stats->ready.pop.local .elock   = 0;
-                stats->ready.pop.local .eempty  = 0;
-                stats->ready.pop.local .espec   = 0;
                 stats->ready.pop.help  .attempt = 0;
                 stats->ready.pop.help  .success = 0;
-                stats->ready.pop.help  .elock   = 0;
-                stats->ready.pop.help  .eempty  = 0;
-                stats->ready.pop.help  .espec   = 0;
                 stats->ready.pop.steal .attempt = 0;
                 stats->ready.pop.steal .success = 0;
-                stats->ready.pop.steal .elock   = 0;
-                stats->ready.pop.steal .eempty  = 0;
-                stats->ready.pop.steal .espec   = 0;
                 stats->ready.pop.search.attempt = 0;
                 stats->ready.pop.search.success = 0;
-                stats->ready.pop.search.elock   = 0;
-                stats->ready.pop.search.eempty  = 0;
-                stats->ready.pop.search.espec   = 0;
                 stats->ready.threads.migration = 0;
                 stats->ready.threads.extunpark = 0;
                 stats->ready.threads.threads   = 0;
+                stats->ready.threads.cthreads  = 0;
                 stats->ready.sleep.halts   = 0;
                 stats->ready.sleep.cancels = 0;
 …
                         stats->io.calls.completed   = 0;
                         stats->io.calls.errors.busy = 0;
-                        stats->io.poller.sleeps     = 0;
                 #endif
 …
+        }
+        static inline void tally_one( volatile uint64_t * agg, volatile uint64_t * val) {
+                uint64_t add = __atomic_exchange_n(val, 0_l64u, __ATOMIC_RELAXED);
+                __atomic_fetch_add(agg, add, __ATOMIC_RELAXED);
+        }
+        static inline void tally_one( volatile int64_t * agg, volatile int64_t * val) {
+                int64_t add = __atomic_exchange_n(val, 0_l64, __ATOMIC_RELAXED);
+                __atomic_fetch_add(agg, add, __ATOMIC_RELAXED);
+        }
         void __tally_stats( struct __stats_t * cltr, struct __stats_t * proc ) {
+                __atomic_fetch_add( &cltr->ready.push.local.attempt, proc->ready.push.local.attempt, __ATOMIC_SEQ_CST ); proc->ready.push.local.attempt = 0;
+                __atomic_fetch_add( &cltr->ready.push.local.success, proc->ready.push.local.success, __ATOMIC_SEQ_CST ); proc->ready.push.local.success = 0;
+                __atomic_fetch_add( &cltr->ready.push.share.attempt, proc->ready.push.share.attempt, __ATOMIC_SEQ_CST ); proc->ready.push.share.attempt = 0;
+                __atomic_fetch_add( &cltr->ready.push.share.success, proc->ready.push.share.success, __ATOMIC_SEQ_CST ); proc->ready.push.share.success = 0;
+                __atomic_fetch_add( &cltr->ready.push.extrn.attempt, proc->ready.push.extrn.attempt, __ATOMIC_SEQ_CST ); proc->ready.push.extrn.attempt = 0;

Context Navigation

Legend:

doc/LaTeXmacros/common.tex

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

doc/user/Makefile

doc/user/user.tex

libcfa/src/common.hfa

libcfa/src/concurrency/alarm.cfa

libcfa/src/concurrency/alarm.hfa

libcfa/src/concurrency/clib/cfathread.cfa

libcfa/src/concurrency/clib/cfathread.h

libcfa/src/concurrency/invoke.h

libcfa/src/concurrency/io.cfa

libcfa/src/concurrency/kernel.cfa

libcfa/src/concurrency/kernel.hfa

libcfa/src/concurrency/kernel/fwd.hfa

libcfa/src/concurrency/kernel/startup.cfa

libcfa/src/concurrency/kernel_private.hfa

libcfa/src/concurrency/locks.cfa

libcfa/src/concurrency/locks.hfa

libcfa/src/concurrency/preemption.cfa

libcfa/src/concurrency/ready_queue.cfa

libcfa/src/concurrency/ready_subqueue.hfa

libcfa/src/concurrency/stats.cfa