Diff [4468a7091814c2d7eba30d6aeef76298d814a716:342af5318a163428f4b8796329683bea27e08c86] for / – Cforall

Jenkins/FullBuild

-                      r4468a70
+                      r342af53
                         string(name: 'GitRef', value: commitId),        \
                         string(name: 'Build' , value: buildNum) \
+                ]
+                ],                                                              \
+                propagate: false
         echo(result.result)

benchmark/creation/node_cor.js

r4468a70	r342af53
6	6	function * coroutine() { yield }
7	7
8		for ( var i = 0; i < times; i += 1 ) { // warm ~~jit~~
	8	for ( var i = 0; i < times; i += 1 ) { // warm JIT
9	9	cor = coroutine()
10	10	}

benchmark/ctxswitch/node_cor.js

r4468a70	r342af53
11	11	cor = coroutine()
12	12
13		for ( var i = 0; i < times; i += 1 ) { // warm ~~git~~
	13	for ( var i = 0; i < times; i += 1 ) { // warm JIT
14	14	cor.next();
15	15	}

benchmark/io/http/Makefile.am

r4468a70	r342af53
29	29	EXTRA_PROGRAMS = httpforall .dummy_hack
30	30
	31	CLEANFILES = httpforall
	32
31	33	nodist_httpforall_SOURCES = \
32	34	filecache.cfa \

benchmark/io/http/main.cfa

-                      r4468a70
+                      r342af53
+}
+extern void init_protocol(void);
+extern void deinit_protocol(void);
 //=============================================================================================
 // Main
 …
         //===================
         // Open Socket
         printf("Listening on port %d\n", options.socket.port);
+        printf("%ld : Listening on port %d\n", getpid(), options.socket.port);
         int server_fd = socket(AF_INET, SOCK_STREAM, 0);
         if(server_fd < 0) {
 …
                 ret = bind( server_fd, (struct sockaddr *)&address, sizeof(address) );
                 if(ret < 0) {
                         if(errno == 98) {
+                        if(errno == EADDRINUSE) {
                                 if(waited == 0) {
                                         printf("Waiting for port\n");
 …
                 options.clopts.instance = &cl;
                 int pipe_cnt = options.clopts.nworkers * 2;
                 int pipe_off;
 …
+                {
                         ServerProc procs[options.clopts.nprocs];
+                        init_protocol();
+                        {
                                 Worker workers[options.clopts.nworkers];
 …
                                         printf("Shutting Down\n");
+                                }
+                                for(i; options.clopts.nworkers) {
+                                        printf("Cancelling %p\n", (void*)workers[i].cancel.target);
+                                        workers[i].done = true;
+                                        cancel(workers[i].cancel);
+                                }
+                                printf("Shutting down socket\n");
+                                int ret = shutdown( server_fd, SHUT_RD );
+                                if( ret < 0 ) { abort( "shutdown error: (%d) %s\n", (int)errno, strerror(errno) ); }
+                                //===================
+                                // Close Socket
+                                printf("Closing Socket\n");
+                                ret = close( server_fd );
+                                if(ret < 0) {
+                                        abort( "close socket error: (%d) %s\n", (int)errno, strerror(errno) );
+                                }
+                        }
                         printf("Workers Closed\n");
+                        deinit_protocol();
+                }
 …
+                }
                 free(fds);
+        }
-        //===================
-        // Close Socket
-        printf("Closing Socket\n");
-        ret = close( server_fd );
-        if(ret < 0) {
-                abort( "close socket error: (%d) %s\n", (int)errno, strerror(errno) );
+        }

benchmark/io/http/options.cfa

-                      r4468a70
+                      r342af53
 #include <parseargs.hfa>
+#include <string.h>
 Options options @= {
+        false, // log
         { // file_cache
 ,     // open_flags;
 …
                 {'p', "port",           "Port the server will listen on", options.socket.port},
                 {'c', "cpus",           "Number of processors to use", options.clopts.nprocs},
+                {'L', "log",            "Enable logs", options.log, parse_settrue},
                 {'t', "threads",        "Number of worker threads to use", options.clopts.nworkers},
                 {'b', "accept-backlog", "Maximum number of pending accepts", options.socket.backlog},

benchmark/io/http/options.hfa

r4468a70	r342af53
8	8
9	9	struct Options {
	10	bool log;
	11
10	12	struct {
11	13	int open_flags;

benchmark/io/http/protocol.cfa

-                      r4468a70
+                      r342af53
 #include "options.hfa"
+const char * volatile date = 0p;
 const char * http_msgs[] = {
         "HTTP/1.1 200 OK\nContent-Type: text/plain\nContent-Length: %zu\n\n",
         "HTTP/1.1 400 Bad Request\nContent-Type: text/plain\nContent-Length: 0\n\n",
         "HTTP/1.1 404 Not Found\nContent-Type: text/plain\nContent-Length: 0\n\n",
         "HTTP/1.1 413 Payload Too Large\nContent-Type: text/plain\nContent-Length: 0\n\n",
         "HTTP/1.1 414 URI Too Long\nContent-Type: text/plain\nContent-Length: 0\n\n",
+        "HTTP/1.1 200 OK\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: %zu \n\n",
+        "HTTP/1.1 400 Bad Request\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
+        "HTTP/1.1 404 Not Found\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
+        "HTTP/1.1 413 Payload Too Large\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
+        "HTTP/1.1 414 URI Too Long\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
 };
 …
         while(len > 0) {
                 // Call write
+                int ret = write(fd, it, len);
+                int ret = cfa_write(fd, it, len, 0, -1`s, 0p, 0p);
+                // int ret = write(fd, it, len);
                 if( ret < 0 ) { if( errno != EAGAIN && errno != EWOULDBLOCK) abort( "'answer error' error: (%d) %s\n", (int)errno, strerror(errno) ); }
 …
 int answer_header( int fd, size_t size ) {
         const char * fmt = http_msgs[OK200];
         int len = 100;
+        int len = 200;
         char buffer[len];
         len = snprintf(buffer, len, fmt, size);
+        len = snprintf(buffer, len, fmt, date, size);
         return answer( fd, buffer, len );
+}
+[HttpCode code, bool closed, * const char file, size_t len] http_read(int fd, []char buffer, size_t len) {
+int answer_plain( int fd, char buffer[], size_t size ) {
+        int ret = answer_header(fd, size);
+        if( ret < 0 ) return ret;
+        return answer(fd, buffer, size);
+}
+int answer_empty( int fd ) {
+        return answer_header(fd, 0);
+}
+[HttpCode code, bool closed, * const char file, size_t len] http_read(int fd, []char buffer, size_t len, io_cancellation * cancel) {
         char * it = buffer;
         size_t count = len - 1;
 …
         READ:
         for() {
+                int ret = cfa_read(fd, (void*)it, count, 0, -1`s, 0p, 0p);
+                int ret = cfa_read(fd, (void*)it, count, 0, -1`s, cancel, 0p);
+                // int ret = read(fd, (void*)it, count);
                 if(ret == 0 ) return [OK200, true, 0, 0];
                 if(ret < 0 ) {
                         if( errno == EAGAIN || errno == EWOULDBLOCK) continue READ;
+                        // if( errno == EINVAL ) return [E400, true, 0, 0];
                         abort( "read error: (%d) %s\n", (int)errno, strerror(errno) );
+                }
 …
+        }
         printf("%.*s\n", rlen, buffer);
+        if( options.log ) printf("%.*s\n", rlen, buffer);
         it = buffer;
 …
 void sendfile( int pipe[2], int fd, int ans_fd, size_t count ) {
+        unsigned sflags = SPLICE_F_MOVE; // | SPLICE_F_MORE;
         off_t offset = 0;
         ssize_t ret;
         SPLICE1: while(count > 0) {
+                ret = cfa_splice(ans_fd, &offset, pipe[1], 0p, count, SPLICE_F_MOVE | SPLICE_F_MORE, 0, -1`s, 0p, 0p);
+                ret = cfa_splice(ans_fd, &offset, pipe[1], 0p, count, sflags, 0, -1`s, 0p, 0p);
+                // ret = splice(ans_fd, &offset, pipe[1], 0p, count, sflags);
                 if( ret < 0 ) {
                         if( errno != EAGAIN && errno != EWOULDBLOCK) continue SPLICE1;
 …
                 size_t in_pipe = ret;
                 SPLICE2: while(in_pipe > 0) {
+                        ret = cfa_splice(pipe[0], 0p, fd, 0p, in_pipe, SPLICE_F_MOVE | SPLICE_F_MORE, 0, -1`s, 0p, 0p);
+                        ret = cfa_splice(pipe[0], 0p, fd, 0p, in_pipe, sflags, 0, -1`s, 0p, 0p);
+                        // ret = splice(pipe[0], 0p, fd, 0p, in_pipe, sflags);
                         if( ret < 0 ) {
                                 if( errno != EAGAIN && errno != EWOULDBLOCK) continue SPLICE2;
 …
+        }
+}
+//=============================================================================================
+#include <clock.hfa>
+#include <time.hfa>
+#include <thread.hfa>
+struct date_buffer {
+        char buff[100];
+};
+thread DateFormater {
+        int idx;
+        date_buffer buffers[2];
+};
+void ?{}( DateFormater & this ) {
+        ((thread&)this){ "Server Date Thread", *options.clopts.instance };
+        this.idx = 0;
+        memset( this.buffers[0].buff, 0, sizeof(this.buffers[0]) );
+        memset( this.buffers[1].buff, 0, sizeof(this.buffers[1]) );
+}
+void main(DateFormater & this) {
+        LOOP: for() {
+                waitfor( ^?{} : this) {
+                        break LOOP;
+                }
+                or else {}
+                Time now = getTimeNsec();
+                strftime( this.buffers[this.idx].buff, 100, "%a, %d %b %Y %H:%M:%S %Z", now );
+                char * next = this.buffers[this.idx].buff;
+                __atomic_exchange_n((char * volatile *)&date, next, __ATOMIC_SEQ_CST);
+                this.idx = (this.idx + 1) % 2;
+                sleep(1`s);
+        }
+}
+//=============================================================================================
+DateFormater * the_date_formatter;
+void init_protocol(void) {
+        the_date_formatter = alloc();
+        (*the_date_formatter){};
+}
+void deinit_protocol(void) {
+        ^(*the_date_formatter){};
+        free( the_date_formatter );
+}

benchmark/io/http/protocol.hfa

-                      r4468a70
+                      r342af53
 #pragma once
+struct io_cancellation;
 enum HttpCode {
 …
 int answer_error( int fd, HttpCode code );
 int answer_header( int fd, size_t size );
+int answer_plain( int fd, char buffer [], size_t size );
+int answer_empty( int fd );
 [HttpCode code, bool closed, * const char file, size_t len] http_read(int fd, []char buffer, size_t len);
+[HttpCode code, bool closed, * const char file, size_t len] http_read(int fd, []char buffer, size_t len, io_cancellation *);
 void sendfile( int pipe[2], int fd, int ans_fd, size_t count );

benchmark/io/http/worker.cfa

-                      r4468a70
+                      r342af53
         this.pipe[0] = -1;
         this.pipe[1] = -1;
+        this.done = false;
+}
+extern "C" {
+extern int accept4(int sockfd, struct sockaddr *addr, socklen_t *addrlen, int flags);
+}
 …
         CONNECTION:
         for() {
+                int fd = cfa_accept4( this.[sockfd, addr, addrlen, flags], 0, -1`s, 0p, 0p );
+                if( options.log ) printf("=== Accepting connection ===\n");
+                int fd = cfa_accept4( this.[sockfd, addr, addrlen, flags], 0, -1`s, &this.cancel, 0p );
+                // int fd = accept4( this.[sockfd, addr, addrlen, flags] );
                 if(fd < 0) {
                         if( errno == ECONNABORTED ) break;
+                        if( errno == EINVAL && this.done ) break;
                         abort( "accept error: (%d) %s\n", (int)errno, strerror(errno) );
+                }
                 printf("New connection %d, waiting for requests\n", fd);
+                if( options.log ) printf("=== New connection %d, waiting for requests ===\n", fd);
                 REQUEST:
                 for() {
 …
                         size_t len = options.socket.buflen;
                         char buffer[len];
                         printf("Reading request\n");
                         [code, closed, file, name_size] = http_read(fd, buffer, len);
+                        if( options.log ) printf("=== Reading request ===\n");
+                        [code, closed, file, name_size] = http_read(fd, buffer, len, &this.cancel);
                         // if we are done, break out of the loop
                         if( closed ) {
+                                printf("Connection closed\n");
+                                if( options.log ) printf("=== Connection closed ===\n");
+                                close(fd);
                                 continue CONNECTION;
+                        }
 …
                         // If this wasn't a request retrun 400
                         if( code != OK200 ) {
                                 printf("Invalid Request : %d\n", code_val(code));
+                                printf("=== Invalid Request : %d ===\n", code_val(code));
                                 answer_error(fd, code);
                                 continue REQUEST;
+                        }
+                        printf("Request for file %.*s\n", (int)name_size, file);
+                        if(0 == strncmp(file, "plaintext", min(name_size, sizeof("plaintext") ))) {
+                                if( options.log ) printf("=== Request for /plaintext ===\n");
+                                char text[] = "Hello, World!\n";
+                                // Send the header
+                                answer_plain(fd, text, sizeof(text));
+                                if( options.log ) printf("=== Answer sent ===\n");
+                                continue REQUEST;
+                        }
+                        if(0 == strncmp(file, "ping", min(name_size, sizeof("ping") ))) {
+                                if( options.log ) printf("=== Request for /ping ===\n");
+                                // Send the header
+                                answer_empty(fd);
+                                if( options.log ) printf("=== Answer sent ===\n");
+                                continue REQUEST;
+                        }
+                        if( options.log ) printf("=== Request for file %.*s ===\n", (int)name_size, file);
                         // Get the fd from the file cache
 …
                         // If we can't find the file, return 404
                         if( ans_fd < 0 ) {
                                 printf("File Not Found\n");
+                                printf("=== File Not Found ===\n");
                                 answer_error(fd, E404);
                                 continue REQUEST;
 …
                         sendfile( this.pipe, fd, ans_fd, count);
                         printf("File sent\n");
+                        if( options.log ) printf("=== Answer sent ===\n");
+                }
+        }

benchmark/io/http/worker.hfa

r4468a70	r342af53
17	17	socklen_t * addrlen;
18	18	int flags;
	19	io_cancellation cancel;
	20	volatile bool done;
19	21	};
20	22	void ?{}( Worker & this);

benchmark/io/readv.cfa

-                      r4468a70
+                      r342af53
         char **left;
         parse_args( opt, opt_cnt, "[OPTIONS]...\ncforall yield benchmark", left );
+        parse_args( opt, opt_cnt, "[OPTIONS]...\ncforall readv benchmark", left );
         if(kpollcp || odirect) {
                 if( (buflen % 512) != 0 ) {
                         fprintf(stderr, "Buffer length must be a multiple of 512 when using O_DIRECT, was %lu\n\n", buflen);
                         print_args_usage(opt, opt_cnt, "[OPTIONS]...\ncforall yield benchmark", true);
+                        print_args_usage(opt, opt_cnt, "[OPTIONS]...\ncforall readv benchmark", true);
+                }
+        }

doc/bibliography/pl.bib

-                      r4468a70
+                      r342af53
+}
+@techreport{cfa-cc,
+    keywords    = {Cforall, cfa-cc, transpiler},
+    contributer = {pabuhr@plg},
+    title       = {{\textsf{cfa-cc}} Developer's Reference Manual},
+    author      = {Fangren Yu},
+    institution = {School of Computer Science},
+    address     = {University of Waterloo, Waterloo, Ontario, Canada},
+    month       = aug,
+    year        = {2020},
+    note        = {\href{https://cforall.uwaterloo.ca/doc/Fangren_Yu_Report_S20.pdf}{https://\-cforall.uwaterloo.ca/\-doc/\-Fangren\_Yu\_Report\_S20.pdf}},
+}
 @article{Moss18,
     keywords    = {type systems, polymorphism, tuples, Cforall},
 …
     keywords    = {type system, generic type, resolution algorithm, type environment, Cforall},
     author      = {Aaron Moss},
     title       = {\textsf{C}$\mathbf{\forall}$ Type System Implementation},
+    title       = {\textsf{C}\,$\mathbf{\forall}$ Type System Implementation},
     school      = {School of Computer Science, University of Waterloo},
     year        = 2019,
 …
     keywords    = {ctrie, concurrent map},
     contributer = {a3moss@uwaterloo.ca},
     title       ={Cache-aware lock-free concurrent hash tries},
     author      ={Prokopec, Aleksandar and Bagwell, Phil and Odersky, Martin},
     institution ={EPFL},
     year        ={2011}
+    title       = {Cache-aware lock-free concurrent hash tries},
+    author      = {Prokopec, Aleksandar and Bagwell, Phil and Odersky, Martin},
+    institution = {EPFL},
+    year        = {2011}
+}
 …
     school      = {School of Computer Science, University of Waterloo},
     year        = 2003,
     address     = {Waterloo, Ontario, Canada, N2L 3G1},
+    optaddress  = {Waterloo, Ontario, Canada, N2L 3G1},
     note        = {\href{http://plg.uwaterloo.ca/theses/BilsonThesis.pdf}{http://\-plg.uwaterloo.ca/\-theses/\-BilsonThesis.pdf}},
+}
 …
+}
+@manual{gcc-nested-func,
+    keywords    = {gcc nested functions},
+    contributer = {pabuhr@plg},
+    key         = {gcc nested functions},
+    title       = {Nested Functions},
+    organization= {{gcc} 9.3 Manual},
+    year        = 2019,
+    note        = {\href{https://gcc.gnu.org/onlinedocs/gcc-9.3.0/gcc/Nested-Functions.html}{https://\-gcc.gnu.org/\-onlinedocs/\-gcc-9.3.0/\-gcc/\-Nested-Functions.html}},
+}
 @article{Haddon77,
     keywords    = {monitors, nested monitor calls},
 …
+}
+@manual{POSIX17,
+    keywords    = {POSIX, Standard},
+    contributer = {pabuhr@plg},
+    key         = {POSIX},
+    title       = {1003.1 Standard for Information Technology -- Portable Operating System Interface (POSIX), Base Specifications, Issue 7},
+    organization= {IEEE and The Open Group},
+    year        = 2017,
+    note        = {\href{https://pubs.opengroup.org/onlinepubs/9699919799}{https://\-pubs.opengroup.org/\-onlinepubs/\-9699919799}},
+}
 @inproceedings{ML:NJ,
     keywords    = {continuations, ML},

doc/theses/andrew_beach_MMath/existing.tex

-                      r4468a70
+                      r342af53
 the the call site.
 As an example, even if no function named \codeCFA{do\_once} is not defined
 near the definition of \codeCFA{do\_twice} the following code will work.
+As an example, even if no function named \codeCFA{do_once} is not defined
+near the definition of \codeCFA{do_twice} the following code will work.
 \begin{lstlisting}
 int quadruple(int x) {
 …
 \end{lstlisting}
 This is not the recommended way to implement a quadruple function but it
 does work. The complier will deduce that \codeCFA{do\_twice}'s T is an
+does work. The complier will deduce that \codeCFA{do_twice}'s T is an
 integer from the argument. It will then look for a definition matching the
 assertion which is the \codeCFA{do\_once} defined within the function. That
 function will be passed in as a function pointer to \codeCFA{do\_twice} and
+assertion which is the \codeCFA{do_once} defined within the function. That
+function will be passed in as a function pointer to \codeCFA{do_twice} and
 called within it.
 …
 In \CFA coroutines are created using the \codeCFA{coroutine} keyword which
 works just like \codeCFA{struct} except that the created structure will be
 modified by the compiler to satify the \codeCFA{is\_coroutine} trait.
+modified by the compiler to satify the \codeCFA{is_coroutine} trait.
 These structures act as the interface between callers and the coroutine,

doc/theses/fangren_yu_COOP_S20/Report.tex

-                      r4468a70
+                      r342af53
 \title{\Huge
 cfa-cc Developer's Reference
+\lstinline|cfa-cc| Developer's Reference
 }% title
 …
 The \CFA compiler sets a limit on assertion depth and reports an error if assertion resolution does not terminate within the limit (as for \lstinline[language=C++]@templates@ in \CC).
+\addcontentsline{toc}{section}{\refname}
 \bibliographystyle{plain}
 \bibliography{pl}

doc/theses/thierry_delisle_PhD/thesis/Makefile

-                      r4468a70
+                      r342af53
 BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
 MAKEFLAGS = --no-print-directory --silent #
+MAKEFLAGS = --no-print-directory --silent
 VPATH = ${Build} ${Figures}
 …
 build/%.dvi : %.tex Makefile | ${Build}
+        # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
+        if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi
         # Must have *.aux file containing citations for bibtex
         if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} $< ; fi
 …
         # Make index from *.aux entries and input index at end of document
         -makeglossaries -q -s ${basename $@}.ist ${basename $@}
+        # Make index from *.aux entries and input index at end of document
+        -makeindex ${basename $@}.idx
         # Run again to finish citations
         ${LaTeX} $<

doc/theses/thierry_delisle_PhD/thesis/text/core.tex

-                      r4468a70
+                      r342af53
 \chapter{Scheduling Core}\label{core}
 Before discussing scheduling in general, where it is important to address systems that are changing states, this document discusses scheduling in a somewhat ideal scenerio, where the system has reached a steady state. For this purpose, a steady state is loosely defined as a state where there are always \glspl{thrd} ready to run and the system has the ressources necessary to accomplish the work, \eg, enough workers. In short, the system is neither overloaded nor underloaded.
+Before discussing scheduling in general, where it is important to address systems that are changing states, this document discusses scheduling in a somewhat ideal scenario, where the system has reached a steady state. For this purpose, a steady state is loosely defined as a state where there are always \glspl{thrd} ready to run and the system has the resources necessary to accomplish the work, \eg, enough workers. In short, the system is neither overloaded nor underloaded.
 I believe it is important to discuss the steady state first because it is the easiest case to handle and, relatedly, the case in which the best performance is to be expected. As such, when the system is either overloaded or underloaded, a common approach is to try to adapt the system to the new load and return to the steady state, \eg, adding or removing workers. Flaws in the scheduling when the system is in the steady state can therefore to be pervasive in all states.
+I believe it is important to discuss the steady state first because it is the easiest case to handle and, relatedly, the case in which the best performance is to be expected. As such, when the system is either overloaded or underloaded, a common approach is to try to adapt the system to this new load and return to the steady state, \eg, by adding or removing workers. Therefore, flaws in scheduling the steady state can to be pervasive in all states.
 \section{Design Goals}
 As with most of the design decisions behind \CFA, an important goal is to match the expectation of the programmer, according to their probable mental model. To match these expectations, the design must offer the programmers sufficient guarantees so that, as long as they respect the mental model, the system will also respect this model.
+As with most of the design decisions behind \CFA, an important goal is to match the expectation of the programmer according to their execution mental-model. To match expectations, the design must offer the programmer sufficient guarantees so that, as long as they respect the execution mental-model, the system also respects this model.
 For threading, a simple and common mental model is the ``Ideal multi-tasking CPU'' :
+For threading, a simple and common execution mental-model is the ``Ideal multi-tasking CPU'' :
 \begin{displayquote}[Linux CFS\cit{https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt}]
         {[The]} ``Ideal multi-tasking CPU'' is a (non-existent  :-)) CPU that has 100\% physical power and which can run each task at precise equal speed, in parallel, each at [an equal fraction of the] speed.  For example: if there are 2 tasks running, then it runs each at 50\% physical power --- i.e., actually in parallel.
+        \label{q:LinuxCFS}
 \end{displayquote}
 Applied to threads, this model states that every ready \gls{thrd} immediately runs in parallel with all other ready \glspl{thrd}. While a strict implementation of this model is not feasible, programmers still have expectations about scheduling that come from this model.
 In general, the expectation at the center of this model is that ready \glspl{thrd} do not interfere with eachother but simply share the hardware. This makes it easier to reason about threading because ready \glspl{thrd} can be taken in isolation and the effect of the scheduler can be virtually ignored. This expectation of \gls{thrd} independence means the scheduler is expected to offer two guarantees:
+In general, the expectation at the center of this model is that ready \glspl{thrd} do not interfere with each other but simply share the hardware. This assumption makes it easier to reason about threading because ready \glspl{thrd} can be thought of in isolation and the effect of the scheduler can be virtually ignored. This expectation of \gls{thrd} independence means the scheduler is expected to offer two guarantees:
 \begin{enumerate}
         \item A fairness guarantee: a \gls{thrd} that is ready to run will not be prevented to do so by another thread.
         \item A performance guarantee: a \gls{thrd} that wants to start or stop running will not be slowed down by other threads wanting to do the same.
+        \item A fairness guarantee: a \gls{thrd} that is ready to run is not prevented by another thread.
+        \item A performance guarantee: a \gls{thrd} that wants to start or stop running is not prevented by other threads wanting to do the same.
 \end{enumerate}
 It is important to note that these guarantees are expected only up to a point. \Glspl{thrd} that are ready to run should not be prevented to do so, but they still need to share a limited amount of hardware. Therefore, the guarantee is considered respected if a \gls{thrd} gets access to a \emph{fair share} of the hardware, even if that share is very small.
+It is important to note that these guarantees are expected only up to a point. \Glspl{thrd} that are ready to run should not be prevented to do so, but they still share the limited hardware resources. Therefore, the guarantee is considered respected if a \gls{thrd} gets access to a \emph{fair share} of the hardware resources, even if that share is very small.
 Similarly the performance guarantee, the lack of interferance between threads, is only relevant up to a point. Ideally the cost of running and blocking would be constant regardless of contention, but the guarantee is considered satisfied if the cost is not \emph{too high} with or without contention. How much is an acceptable cost is obviously highly variable. For this document the performance experimentation will attempt to show that the cost of scheduling is at worst equivalent to existing algorithms used in popular languages. This demonstration can be made by comparing application built in \CFA to applications built with other languages or other models. Recall from a few paragraphs ago that the expectation of programmers is that the impact of the scheduler can be ignored. Therefore, if the cost of scheduling is equivalent or lower to other popular languages, I will consider the guarantee achieved.
+Similarly the performance guarantee, the lack of interference among threads, is only relevant up to a point. Ideally, the cost of running and blocking should be constant regardless of contention, but the guarantee is considered satisfied if the cost is not \emph{too high} with or without contention. How much is an acceptable cost is obviously highly variable. For this document, the performance experimentation attempts to show the cost of scheduling is at worst equivalent to existing algorithms used in popular languages. This demonstration can be made by comparing applications built in \CFA to applications built with other languages or other models. Recall programmer expectation is that the impact of the scheduler can be ignored. Therefore, if the cost of scheduling is equivalent to or lower than other popular languages, I consider the guarantee achieved.
 More precisely the scheduler should be:
 \begin{itemize}
         \item As fast as other schedulers that are less fair.
         \item Faster than other scheduler that have equal or better fairness.
+        \item Faster than other schedulers that have equal or better fairness.
 \end{itemize}
 \subsection{Fairness vs Scheduler Locality}
 An important performance factor in modern architectures is cache locality. Waiting for data not present in the cache can have a major impact on performance, and having multiple \glspl{hthrd} writing to the same cache lines can lead to cache lines that need to be waited on again. It is therefore preferable to divide the data among each \gls{hthrd}\footnote{This can be an explicit division up front or using data structures where different \glspl{hthrd} are naturally routed to different cache lines.}.
+An important performance factor in modern architectures is cache locality. Waiting for data at lower levels or not present in the cache can have a major impact on performance. Having multiple \glspl{hthrd} writing to the same cache lines also leads to cache lines that must be waited on. It is therefore preferable to divide data among each \gls{hthrd}\footnote{This partitioning can be an explicit division up front or using data structures where different \glspl{hthrd} are naturally routed to different cache lines.}.
 For a scheduler, having good locality\footnote{This section discusses \emph{internal} locality, \ie, the locality of the data used by the scheduler. \emph{External locality}, \ie, how the data used by the application is affected by scheduling, is a much more complicated subject and will be discussed in the chapters on evaluation.}, \ie, having the data be local to each \gls{hthrd}, generally conflicts with fairness. Indeed, good locality often requires avoiding the movement of cache lines, while fairness requires dynamically moving \gls{thrd}, and as a consequence cache lines, to \glspl{hthrd} that are currently more appropriate.
+For a scheduler, having good locality\footnote{This section discusses \emph{internal locality}, \ie, the locality of the data used by the scheduler versus \emph{external locality}, \ie, how the data used by the application is affected by scheduling. External locality is a much more complicated subject and is discussed in part~\ref{Evaluation} on evaluation.}, \ie, having the data local to each \gls{hthrd}, generally conflicts with fairness. Indeed, good locality often requires avoiding the movement of cache lines, while fairness requires dynamically moving a \gls{thrd}, and as consequence cache lines, to a \gls{hthrd} that is currently available.
 However, I claim that in practice it is possible to strike a balance between fairness and performance because the need for these do not necessarily overlap temporaly. Figure~\ref{fig:fair} shows an visual representation of this behaviour. As mentionned, a little bit of unfairness can be acceptable, therefore it can be desirable to have an algorithm that prioritizes cache locality as long as no threads is left behind for too long.
+However, I claim that in practice it is possible to strike a balance between fairness and performance because these goals do not necessarily overlap temporally, where Figure~\ref{fig:fair} shows a visual representation of this behaviour. As mentioned, some unfairness is acceptable; therefore it is desirable to have an algorithm that prioritizes cache locality as long as thread delay does not exceed the execution mental-model.
 \begin{figure}
         \begin{center}
                 \input{fairness.pstex_t}
         \end{center}
         \caption{Fairness vs Locality}
+        \centering
+        \input{fairness.pstex_t}
+        \vspace*{-10pt}
+        \caption[Fairness vs Locality graph]{Rule of thumb Fairness vs Locality graph \smallskip\newline The importance of Fairness and Locality while a ready \gls{thrd} awaits running is shown as the time the ready \gls{thrd} waits increases, Ready Time, the chances that its data is still in cache, Locality, decreases. At the same time, the need for fairness increases since other \glspl{thrd} may have the chance to run many times, breaking the fairness model. Since the actual values and curves of this graph can be highly variable, the graph is an idealized representation of the two opposing goals.}
         \label{fig:fair}
-        Rule of thumb graph: Importance of Fairness and Locality while a ready \gls{thrd} waits run.
-        As the time a ready \gls{thrd} waits increases, ``Ready Time'', the chances that its data is still in cache decreases. At the same time, the need for fairness increases since other \glspl{thrd} may have the chance to run many times, breaking the fairness model mentionned above. Since the actual values and curves of this graph can be highly variable, the graph is left intentionally fuzzy and innacurate.
 \end{figure}
 \section{Design}
 A naive strictly \glsxtrshort{fifo} ready-queue does not offer sufficient performance. As shown in the evaluation sections, most production schedulers scale when adding multiple \glspl{hthrd} and that is not possible with a single point of contention. Therefore it is vital to shard the ready-queue so that multiple \glspl{hthrd} can access the ready-queue without performance degradation.
+In general, a na\"{i}ve \glsxtrshort{fifo} ready-queue does not scale with increased parallelism from \glspl{hthrd}, resulting in decreased performance. The problem is adding/removing \glspl{thrd} is a single point of contention. As shown in the evaluation sections, most production schedulers do scale when adding \glspl{hthrd}. The common solution to the single point of contention is to shard the ready-queue so each \gls{hthrd} can access the ready-queue without contention, increasing performance though lack of contention.
 \subsection{Sharding} \label{sec:sharding}
 An interesting approach to sharding a queue is presented in \cit{Trevors paper}. This algorithm represents a queue with relaxed \glsxtrshort{fifo} guarantee using an array of strictly \glsxtrshort{fifo} sublists as shown in Figure~\ref{fig:base}. Each cell of the array contains a linked-list with a lock and each node in these list is marked with a timestamp indicating when they were added to the list. Push operations are done by picking a random cell and attempting to push to its list. If the cell is already locked, the operation is simply retried on a new cell until a lock is acquired. Pop operations are done in a similar fashion except two random cells are picked. If both cells are not already locked and both cells contain non-empty lists, the operation pops the node with the oldest timestamp. If only one of the cell is unlocked and non-empty, the operation pops from that cell. If both cells are either locked or empty, the operation picks two new cells and tries again.
+An interesting approach to sharding a queue is presented in \cit{Trevors paper}. This algorithm presents a queue with a relaxed \glsxtrshort{fifo} guarantee using an array of strictly \glsxtrshort{fifo} sublists as shown in Figure~\ref{fig:base}. Each \emph{cell} of the array has a timestamp for the last operation and a pointer to a linked-list with a lock and each node in the list is marked with a timestamp indicating when it is added to the list. A push operation is done by picking a random cell, acquiring the list lock, and pushing to the list. If the cell is locked, the operation is simply retried on another random cell until a lock is acquired. A pop operation is done in a similar fashion except two random cells are picked. If both cells are unlocked with non-empty lists, the operation pops the node with the oldest cell timestamp. If one of the cells is unlocked and non-empty, the operation pops from that cell. If both cells are either locked or empty, the operation picks two new random cells and tries again.
 \begin{figure}
+        \begin{center}
+                \input{base.pstex_t}
+        \end{center}
+        \caption{Relaxed FIFO list}
+        \centering
+        \input{base.pstex_t}
+        \caption[Relaxed FIFO list]{Relaxed FIFO list \smallskip\newline List at the base of the scheduler: an array of strictly FIFO lists. The timestamp is in all nodes and cell arrays.}
         \label{fig:base}
-        List at the base of the scheduler: an array of strictly FIFO lists.
-        The timestamp is in all nodes and cell arrays.
 \end{figure}
 \subsection{Finding threads}
+Once threads have been distributed onto multiple queues, indentifying which queues are empty and which are not can become a problem. Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of these queues are empty. Figure~\ref{fig:empty} shows an example with 2 \glspl{thrd} running on 8 queues, where the chances of getting an empty queue is 75\% per pick, meaning two random picks yield a \gls{thrd} only half the time.
+Once threads have been distributed onto multiple queues, identifying empty queues becomes a problem. Indeed, if the number of \glspl{thrd} does not far exceed the number of queues, it is probable that several of the cell queues are empty. Figure~\ref{fig:empty} shows an example with 2 \glspl{thrd} running on 8 queues, where the chances of getting an empty queue is 75\% per pick, meaning two random picks yield a \gls{thrd} only half the time. This scenario leads to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
 \begin{figure}
+        \begin{center}
+                \input{empty.pstex_t}
+        \end{center}
+        \caption{``More empty'' Relaxed FIFO list}
+        \centering
+        \input{empty.pstex_t}
+        \caption[``More empty'' Relaxed FIFO list]{``More empty'' Relaxed FIFO list \smallskip\newline Emptier state of the queue: the array contains many empty cells, that is strictly FIFO lists containing no elements.}
         \label{fig:empty}
-        Emptier state of the queue: the array contains many empty cells, that is strictly FIFO lists containing no elements.
 \end{figure}
 This can lead to performance problems since picks that do not yield a \gls{thrd} are not useful and do not necessarily help make more informed guesses.
+There are several solutions to this problem, but they ultimately all have to encode if a cell has an empty list. My results show the density and locality of this encoding is generally the dominating factor in these scheme. Classic solutions to this problem use one of three techniques to encode the information:
+Solutions to this problem can take many forms, but they ultimately all have to encode where the threads are in some form. My results show that the density and locality of this encoding is generally the dominating factor in these scheme. Classic solutions to this problem use one of three techniques to encode the information:
+\paragraph{Dense Information} Figure~\ref{fig:emptybit} shows a dense bitmask to identify the cell queues currently in use. This approach means processors can often find \glspl{thrd} in constant time, regardless of how many underlying queues are empty. Furthermore, modern x86 CPUs have extended bit manipulation instructions (BMI2) that allow searching the bitmask with very little overhead compared to the randomized selection approach for a filled ready queue, offering good performance even in cases with many empty inner queues. However, this technique has its limits: with a single word\footnote{Word refers here to however many bits can be written atomically.} bitmask, the total amount of ready-queue sharding is limited to the number of bits in the word. With a multi-word bitmask, this maximum limit can be increased arbitrarily, but the look-up time increases. Finally, a dense bitmap, either single or multi-word, causes additional contention problems that reduces performance because of cache misses after updates. This central update bottleneck also means the information in the bitmask is more often stale before a processor can use it to find an item, \ie mask read says there are available \glspl{thrd} but none on queue when the subsequent atomic check is done.
 \begin{figure}
+        \begin{center}
+                {\resizebox{0.73\textwidth}{!}{\input{emptybit.pstex_t}}}
+        \end{center}
+        \centering
         \vspace*{-5pt}
+        \caption{Underloaded queue with added bitmask to indicate which array cells have items.}
+        {\resizebox{0.75\textwidth}{!}{\input{emptybit.pstex_t}}}
+        \vspace*{-5pt}
+        \caption[Underloaded queue with bitmask]{Underloaded queue with bitmask indicating array cells with items.}
         \label{fig:emptybit}
+        \begin{center}
                 {\resizebox{0.73\textwidth}{!}{\input{emptytree.pstex_t}}}
         \end{center}
+        \vspace*{10pt}
+        {\resizebox{0.75\textwidth}{!}{\input{emptytree.pstex_t}}}
         \vspace*{-5pt}
         \caption{Underloaded queue with added binary search tree indicate which array cells have items.}
+        \caption[Underloaded queue with binary search-tree]{Underloaded queue with binary search-tree indicating array cells with items.}
         \label{fig:emptytree}
+        \begin{center}
                 {\resizebox{0.9\textwidth}{!}{\input{emptytls.pstex_t}}}
         \end{center}
+        \vspace*{10pt}
+        {\resizebox{0.95\textwidth}{!}{\input{emptytls.pstex_t}}}
         \vspace*{-5pt}
         \caption{Underloaded queue with added per processor bitmask to indicate which array cells have items.}
+        \caption[Underloaded queue with per processor bitmask]{Underloaded queue with per processor bitmask indicating array cells with items.}
         \label{fig:emptytls}
 \end{figure}
 \paragraph{Dense Information} Figure~\ref{fig:emptybit} shows a dense bitmask to identify which inner queues are currently in use. This approach means processors can often find \glspl{thrd} in constant time, regardless of how many underlying queues are empty. Furthermore, modern x86 CPUs have extended bit manipulation instructions (BMI2) that allow using the bitmask with very little overhead compared to the randomized selection approach for a filled ready queue, offering good performance even in cases with many empty inner queues. However, this technique has its limits: with a single word\footnote{Word refers here to however many bits can be written atomically.} bitmask, the total number of underlying queues in the ready queue is limited to the number of bits in the word. With a multi-word bitmask, this maximum limit can be increased arbitrarily, but the look-up will nolonger be constant time. Finally, a dense bitmap, either single or multi-word, causes additional contention problems which reduces performance because of cache misses after updates. This central update bottleneck also means the information in the bitmask is more often stale before a processor can use it to find an item, \ie mask read says there are available \glspl{thrd} but none on queue.
+\paragraph{Sparse Information} Figure~\ref{fig:emptytree} shows an approach using a hierarchical tree data-structure to reduce contention and has been shown to work in similar cases~\cite{ellen2007snzi}. However, this approach may lead to poorer performance due to the inherent pointer chasing cost while still allowing significant contention on the nodes of the tree if the tree is shallow.
 \paragraph{Sparse Information} Figure~\ref{fig:emptytree} shows an approach using a hierarchical tree data-structure to reduce contention and has been shown to work in similar cases~\cite{ellen2007snzi}. However, this approach may lead to poorer performance due to the inherent pointer chasing cost while still allowing more contention on the nodes of the tree if the tree is not deep enough.
+\paragraph{Local Information} Figure~\ref{fig:emptytls} shows an approach using dense information, similar to the bitmap, but each \gls{hthrd} keeps its own independent copy. While this approach can offer good scalability \emph{and} low latency, the liveliness and discovery of the information can become a problem. This case is made worst in systems with few processors where even blind random picks can find \glspl{thrd} in a few tries.
+\paragraph{Local Information} Figure~\ref{fig:emptytls} shows an approach using dense information, similar to the bitmap, but have each thread keep its own independent copy of it. While this approach can offer good scalability \emph{and} low latency, the liveliness and discovery of the information can become a problem. This case is made worst in systems with few processors where even blind random picks can find \glspl{thrd} in few tries.
+I built a prototype of these approach and none of these techniques offer satisfying performance when few threads are present. All of these approach hit the same 2 problems. First, blindly picking two sub-queues is very fast which means that any improvement to the hit rate can easily be countered by a slow-down in look-up speed. Second, the array is already as sharded as is needed to avoid contention bottlenecks, so any denser data structure will tend to become a bottleneck. In all cases, these factors meant that the best cases scenerio, many threads, would get worst throughput and the worst case scenario, few threads, would get a better hit rate, but an equivalent throughput. As a result I tried an entirely different approach.
+I built a prototype of these approaches and none of these techniques offer satisfying performance when few threads are present. All of these approach hit the same 2 problems. First, randomly picking sub-queues is very fast but means any improvement to the hit rate can easily be countered by a slow-down in look-up speed when there are empty lists. Second, the array is already as sharded to avoid contention bottlenecks, so any denser data structure tends to become a bottleneck. In all cases, these factors meant the best cases scenario, \ie many threads, would get worst throughput, and the worst-case scenario, few threads, would get a better hit rate, but an equivalent poor throughput. As a result I tried an entirely different approach.
 \subsection{Dynamic Entropy}\cit{https://xkcd.com/2318/}
 In the worst case scenario there are few \glspl{thrd} ready to run, or more accuratly given $P$ \glspl{proc}, $T$ \glspl{thrd} and $\epsilon$, as usual, a very small number, in this case $\epsilon \ll P$, we have $T = P + \epsilon$. An important thing to note is that in this case, fairness is effectively irrelevant. Indeed, this case is close to \emph{actually matching} the model of the ``Ideal multi-tasking CPU'' presented in this chapter\footnote{For simplicity, this assumes there is a one-to-one match between \glspl{proc} and \glspl{hthrd}.}. Therefore, in this context it is possible to use a purely internal locality based approach and still meet the fairness requirements. This approach would simply have each \gls{proc} running a single \gls{thrd} repeatedly. Or from the shared ready-queue viewpoint, each \gls{proc} would push to a given sub-queue and then pop from the \emph{same} subqueue. Ideally, the scheduler would achieve this without affecting the fairness guarantees in cases where $T \gg P$.
+In the worst-case scenario there are only few \glspl{thrd} ready to run, or more precisely given $P$ \glspl{proc}\footnote{For simplicity, this assumes there is a one-to-one match between \glspl{proc} and \glspl{hthrd}.}, $T$ \glspl{thrd} and $\epsilon$ a very small number, than the worst case scenario can be represented by $\epsilon \ll P$, than $T = P + \epsilon$. It is important to note in this case that fairness is effectively irrelevant. Indeed, this case is close to \emph{actually matching} the model of the ``Ideal multi-tasking CPU'' on page \pageref{q:LinuxCFS}. In this context, it is possible to use a purely internal-locality based approach and still meet the fairness requirements. This approach simply has each \gls{proc} running a single \gls{thrd} repeatedly. Or from the shared ready-queue viewpoint, each \gls{proc} pushes to a given sub-queue and then popes from the \emph{same} subqueue. In cases where $T \gg P$, the scheduler should also achieves similar performance without affecting the fairness guarantees.
 To achieve this, I use a communication channel I have not mentionned yet and which I believe I use in a novel way : the \glsxtrshort{prng}. If the scheduler has a \glsxtrshort{prng} instance per \gls{proc} exclusively used for scheduling, its seed effectively encodes a list of all the accessed subqueues, from the latest to the oldest. The only requirement to achieve this is to be able to ``replay'' the \glsxtrshort{prng} backwards. As it turns out, this is an entirely reasonnable requirement and there already exist \glsxtrshort{prng}s that are fast, compact \emph{and} can be run forward and backwards. Linear congruential generators\cite{wiki:lcg} are an example of \glsxtrshort{prng}s that match these requirements.
+To handle this case, I use a pseudo random-number generator, \glsxtrshort{prng} in a novel way. When the scheduler uses a \glsxtrshort{prng} instance per \gls{proc} exclusively, the random-number seed effectively starts an encoding that produces a list of all accessed subqueues, from latest to oldest. The novel approach is to be able to ``replay'' the \glsxtrshort{prng} backwards and there exist \glsxtrshort{prng}s that are fast, compact \emph{and} can be run forward and backwards. Linear congruential generators~\cite{wiki:lcg} are an example of \glsxtrshort{prng}s that match these requirements.
 The algorithm works as follows :
+The algorithm works as follows:
 \begin{itemize}
         \item Each \gls{proc} has two \glsxtrshort{prng} instances, $F$ and $B$.
         \item Push and Pop operations happen as mentionned in Section~\ref{sec:sharding} with the following exceptions:
+        \item Push and Pop operations occur as discussed in Section~\ref{sec:sharding} with the following exceptions:
         \begin{itemize}
                 \item Push operations use $F$ going forward on each try and on success $F$ is copied into $B$.
 …
 \end{itemize}
 The main benefit of this technique is that it basically repects the desired properties of Figure~\ref{fig:fair}. When looking for work, \glspl{proc} will look first at the last cells they pushed to, if any, and then move backwards through the cells. As the \glspl{proc} continue looking for work, $F$ moves back and $B$ stays in place. As a result the relation between the two becomes weaker, which means that the probablisitic fairness of the algorithm reverts to normal. Chapter~\ref{proofs} discusses more formally the fairness guarantees of this algorithm.
+The main benefit of this technique is that it basically respects the desired properties of Figure~\ref{fig:fair}. When looking for work, a \gls{proc} first looks at the last cell they pushed to, if any, and then move backwards through its accessed cells. As the \gls{proc} continues looking for work, $F$ moves backwards and $B$ stays in place. As a result, the relation between the two becomes weaker, which means that the probablisitic fairness of the algorithm reverts to normal. Chapter~\ref{proofs} discusses more formally the fairness guarantees of this algorithm.
 \section{Details}

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

-                      r4468a70
+                      r342af53
 Since \glsxtrshort{io} operations are generally handled by the
 \subsection{\texttt{epoll}, \texttt{poll} and \texttt{select}}
+\subsection{\lstinline|epoll|, \lstinline|poll| and \lstinline|select|}
 \subsection{Linux's AIO}
 …
 \subsection{\texttt{io\_uring}}
 A very recent addition to Linux, \texttt{io\_uring}\cit{io\_uring} is a framework that aims to solve many of the problems listed with the above mentioned solutions.
+A very recent addition to Linux, @io_uring@\cit{io\_uring} is a framework that aims to solve many of the problems listed with the above mentioned solutions.
 \subsection{Extra Kernel Threads}\label{io:morethreads}

doc/theses/thierry_delisle_PhD/thesis/text/runtime.tex

-                      r4468a70
+                      r342af53
 \chapter{\CFA Runtime}
 This chapter offers an overview of the capabilities of the \CFA runtime prior to this work.
+This chapter presents an overview of the capabilities of the \CFA runtime prior to this thesis work.
 Threading in \CFA offers is based on \Gls{uthrding}, where \glspl{thrd} are the representation of a unit of work. As such, \CFA programmers should expect these units to be fairly inexpensive, that is: programmers should be able to create a large number of \glspl{thrd} and switch between \glspl{thrd} liberally without many concerns for performance.
+\Celeven introduced threading features, such the @_Thread_local@ storage class, and libraries @stdatomic.h@ and @threads.h@. Interestingly, almost a decade after the \Celeven standard, the most recent versions of gcc, clang, and msvc do not support the \Celeven include @threads.h@, indicating no interest in the C11 concurrency approach (possibly because of the recent effort to add concurrency to \CC). While the \Celeven standard does not state a threading model, the historical association with pthreads suggests implementations would adopt kernel-level threading (1:1)~\cite{ThreadModel}, as for \CC. This model uses \glspl{kthrd} to achieve parallelism and concurrency. In this model, every thread of computation maps to an object in the kernel. The kernel then has the responsibility of managing these threads, \eg creating, scheduling, blocking. This also entails that the kernel has a perfect view of every thread executing in the system\footnote{This is not completely true due to primitives like \lstinline|futex|es, which have a significant portion of their logic in user space.}.
 \section{M:N Threading}\label{prev:model}
 C traditionnally uses a 1:1 threading model. This model uses \glspl{kthrd} to achive parallelism and concurrency. In this model, every thread of computation maps to an object in the kernel. The kernel then has the responsibility of managing these threads, \eg creating, scheduling, blocking. This also entails that the kernel has a perfect view of every thread executing in the system\footnote{This is not completly true due to primitives like \texttt{futex}es, which have a significant portion of their logic in user space.}.
+Threading in \CFA is based on \Gls{uthrding}, where \glspl{thrd} are the representation of a unit of work. As such, \CFA programmers should expect these units to be fairly inexpensive, \ie programmers should be able to create a large number of \glspl{thrd} and switch among \glspl{thrd} liberally without many concerns for performance.
 By contrast \CFA uses an M:N threading models, where concurrency is achieved using many user-level threads mapped onto fewer \glspl{kthrd}. The user-level threads have the same semantic meaning as a \glspl{kthrd} in the 1:1 model, they represent an independant thread of execution with it's on stack. The difference is that user-level threads do not have a corresponding object in the kernel, they are handled by the runtime in user space and scheduled onto \glspl{kthrd}, referred to as \glspl{proc} in this document. \Glspl{proc} run a \gls{thrd} until it context switches out, it then choses a different \gls{thrd} to run.
+The \CFA M:N threading models is implemented using many user-level threads mapped onto fewer \glspl{kthrd}. The user-level threads have the same semantic meaning as a \glspl{kthrd} in the 1:1 model: they represent an independent thread of execution with its own stack. The difference is that user-level threads do not have a corresponding object in the kernel, they are handled by the runtime in user space and scheduled onto \glspl{kthrd}, referred to as \glspl{proc} in this document. \Glspl{proc} run a \gls{thrd} until it context switches out, it then chooses a different \gls{thrd} to run.
 \section{Clusters}
+\CFA allows the option to group user-level threading, in the form of clusters. Both \glspl{thrd} and \glspl{proc} belong to a specific cluster. \Glspl{thrd} are only be scheduled onto \glspl{proc} in the same cluster and scheduling is done independently of other clusters. Figure~\ref{fig:system} shows an overview of the \CFA runtime, which allows programmers to tightly control parallelism. It also opens the door to handling effects like NUMA, by pining clusters to a specific NUMA node\footnote{This is not currently implemented in \CFA, but the only hurdle left is creating a generic interface for cpu masks.}.
 \begin{figure}
         \begin{center}
                 \input{system.pstex_t}
         \end{center}
         \caption{Overview of the \CFA runtime}
+        \caption[Overview of the \CFA runtime]{Overview of the \CFA runtime \newline \Glspl{thrd} are scheduled inside a particular cluster, where it only runs on the \glspl{proc} which belong to the cluster. The discrete-event manager, which handles preemption and timeout, is a \gls{kthrd} which lives outside any cluster and does not run \glspl{thrd}.}
         \label{fig:system}
-        \Glspl{thrd} are scheduled inside a particular cluster, where it only runs on the \glspl{proc} which belong to the cluster. The discrete-event manager, which handles preemption and timeout, is a \gls{kthrd} which lives outside any cluster and does not run \glspl{thrd}.
 \end{figure}
-\CFA allows the option to group user-level threading, in the form of clusters. Both \glspl{thrd} and \glspl{proc} belong to a specific cluster. \Glspl{thrd} will only be scheduled onto \glspl{proc} in the same cluster and scheduling is done independantly of other clusters. Figure~\ref{fig:system} shows an overview if this system. This allows programmers to control more tightly parallelism. It also opens the door to handling effects like NUMA, by pining clusters to specific NUMA node\footnote{This is not currently implemented in \CFA, but the only hurdle left is creating a generic interface for cpu masks.}.
 \section{Scheduling}
 The \CFA runtime was previously using a strictly \glsxtrshort{fifo} ready queue with a single lock. This setup offers perfect fairness in terms of opportunities to run/ However, it offers poor scalability, since the performance of the ready queue can never be improved by adding more \glspl{hthrd}, but the contention can cause significant performance degradation.
+The \CFA runtime previously used a \glsxtrshort{fifo} ready-queue with a single lock. This setup offers perfect fairness in terms of opportunities to run. However, it offers poor scalability, since the performance of the ready queue can never be improved by adding more \glspl{hthrd} and contention can cause significant performance degradation.
 \section{\glsxtrshort{io}}\label{prev:io}
+Prior to this work, the \CFA runtime did not add any particular support for \glsxtrshort{io} operations. \CFA being built on C, this means that, while all the operations available in C are available in \CFA, \glsxtrshort{io} operations are designed for the POSIX threading model\cit{pthreads}. Using these operations in a M:N threading model, when they are built for 1:1 threading, means that operations block \glspl{proc} instead of \glspl{thrd}. While this can work in certain cases, it limits the number of concurrent operations to the number of \glspl{proc} rather than \glspl{thrd}. This also means that deadlocks can occur because all \glspl{proc} are blocked even if at least one \gls{thrd} is ready to run. A simple example of this type of deadlock would be as follows:
+Prior to this work, the \CFA runtime did not add any particular support for \glsxtrshort{io} operations. %\CFA being built on C, this means that,
+While all I/O operations available in C are available in \CFA, \glsxtrshort{io} operations are designed for the POSIX threading model~\cite{pthreads}. Using these 1:1 threading operations in an M:N threading model means I/O operations block \glspl{proc} instead of \glspl{thrd}. While this can work in certain cases, it limits the number of concurrent operations to the number of \glspl{proc} rather than \glspl{thrd}. It also means deadlock can occur because all \glspl{proc} are blocked even if at least one \gls{thrd} is ready to run. A simple example of this type of deadlock would be as follows:
+\begin{quote}
+Given a simple network program with 2 \glspl{thrd} and a single \gls{proc}, one \gls{thrd} sends network requests to a server and the other \gls{thrd} waits for a response from the server. If the second \gls{thrd} races ahead, it may wait for responses to requests that have not been sent yet. In theory, this should not be a problem, even if the second \gls{thrd} waits, because the first \gls{thrd} is still ready to run and should be able to get CPU time to send the request. With M:N threading, while the first \gls{thrd} is ready, the lone \gls{proc} \emph{cannot} run the first \gls{thrd} if it is blocked in the \glsxtrshort{io} operation of the second \gls{thrd}. If this happen, the system is in a synchronization deadlock\footnote{In this example, the deadlocked could be resolved if the server sends unprompted messages to the client. However, this solution is not general and may not be appropriate even in this simple case.}.
+\end{quote}
+Therefore, one of the objective of this work is to introduce \emph{User-Level \glsxtrshort{io}}, like \glslink{uthrding}{User-Level \emph{Threading}} blocks \glspl{thrd} rather than \glspl{proc} when doing \glsxtrshort{io} operations, which entails multiplexing the \glsxtrshort{io} operations of many \glspl{thrd} onto fewer \glspl{proc}. This multiplexing requires that a single \gls{proc} be able to execute multiple I/O operations in parallel. This requirement cannot be done with operations that block \glspl{proc}, \ie \glspl{kthrd}, since the first operation would prevent starting new operations for its blocking duration. Executing I/O operations in parallel requires \emph{asynchronous} \glsxtrshort{io}, sometimes referred to as \emph{non-blocking}, since the \gls{kthrd} does not block.
+Given a simple network program with 2 \glspl{thrd} and a single \gls{proc}, one \gls{thrd} sends network requests to a server and the other \gls{thrd} waits for response from the server. If the second \gls{thrd} races ahead, it may wait for responses to requests that have not been sent yet. In theory, this should not be a problem, even if the second \gls{thrd} waits, the first \gls{thrd} is still ready to run and should just be able to get CPU time and send the request. In practice with M:N threading, while the first \gls{thrd} is ready, the lone \gls{proc} in this example will \emph{not} try to run the first \gls{thrd} if it is blocked in the \glsxtrshort{io} operation of the second \gls{thrd}. If this happen, the system is effectively deadlocked\footnote{In this example, the deadlocked could be resolved if the server sends unprompted messages to the client. However, this solution is not general and may not be appropriate even in this simple case.}.
+\section{Interoperating with C}
+While \glsxtrshort{io} operations are the classical example of operations that block \glspl{kthrd}, the non-blocking challenge extends to all blocking system-calls. The POSIX standard states~\cite[\S~2.9.1]{POSIX17}:
+\begin{quote}
+All functions defined by this volume of POSIX.1-2017 shall be thread-safe, except that the following functions1 need not be thread-safe. ... (list of 70+ potentially excluded functions)
+\end{quote}
+Only UNIX @man@ pages identify whether or not a library function is thread safe, and hence, may block on a pthread lock or system call; hence interoperability with UNIX library functions is a challenge for an M:N threading model.
 One of the objective of this work, is to introduce \emph{User-Level \glsxtrshort{io}} which, as a parallel to \glslink{uthrding}{User-Level \emph{Threading}}, blocks \glspl{thrd} rather than \glspl{proc} when doing \glsxtrshort{io} operations. This entails multiplexing the \glsxtrshort{io} operations of many \glspl{thrd} onto fewer \glspl{proc}. This multiplexing requires that a single \gls{proc} be able to execute multiple operations in parallel. This cannot be done with operations that block \glspl{proc}, \ie \glspl{kthrd}, since the first operation would prevent starting new operations for its duration. Executing operations in parallel requires \emph{asynchronous} \glsxtrshort{io}, sometimes referred to as \emph{non-blocking}, since the \gls{kthrd} is not blocked.
+Languages like Go and Java, which have strict interoperability with C\cit{JNI, GoLang with C}, can control operations in C by ``sandboxing'' them, \eg a blocking function may be delegated to a \gls{kthrd}. Sandboxing may help towards guaranteeing that the kind of deadlock mentioned above does not occur.
+\section{Interoperating with \texttt{C}}
+While \glsxtrshort{io} operations are the classical example of operations that block \glspl{kthrd}, the challenges mentioned in the previous section do not require \glsxtrshort{io} to be involved. These challenges are a product of blocking system calls rather than \glsxtrshort{io}. C offers no tools to identify whether or not a librairy function will lead to a blocking system call. This fact means interoperatability with C becomes a challenge in a M:N threading model.
+Languages like Go and Java, which have strict interoperatability with C\cit{JNI, GoLang with C}, can control operations in C by ``sandboxing'' them. They can, for example, delegate C operations to \glspl{kthrd} that are not \glspl{proc}. Sandboxing may help towards guaranteeing that the deadlocks mentioned in the previous section do not occur.
+As mentioned in Section~\cit{\CFA intro}, \CFA is binary compatible with C and, as such, trivially supports calls to and from C librairies. Furthermore, interoperatability can happen within a single library, through inline code or simply C and \CFA translation units archived together. The fine-grained interoperatability between C and \CFA has two consequences:
+As mentioned in Section~\ref{intro}, \CFA is binary compatible with C and, as such, must support all C library functions. Furthermore, interoperability can happen at the function-call level, inline code, or C and \CFA translation units linked together. This fine-grained interoperability between C and \CFA has two consequences:
 \begin{enumerate}
         \item Precisely identifying C calls that could block is difficult.
         \item Introducing code where interoperatability occurs could have a significant impact on general performance.
+        \item Precisely identifying blocking C calls is difficult.
+        \item Introducing new code can have a significant impact on general performance.
 \end{enumerate}
+Because of these consequences, this work does not attempt to ``sandbox'' calls to C. It is possible that conflicting calls to C could lead to deadlocks on \CFA's M:N threading model where they would not in the traditionnal 1:1 threading model. However, I judge that solving this problem in general, in a way that is composable and flexible, is too complex in itself and would add too much work to this thesis. Therefore it is outside the scope of this thesis.
+Because of these consequences, this work does not attempt to ``sandbox'' calls to C. Therefore, it is possible for an unidentified library calls to block a \gls{kthrd} leading to deadlocks in \CFA's M:N threading model, which would not occur in a traditional 1:1 threading model. Currently, all M:N thread systems interacting with UNIX without sandboxing suffer from this problem but manage to work very well in the majority of applications. Therefore, a complete solution to this problem is outside the scope of this thesis.

doc/theses/thierry_delisle_PhD/thesis/thesis.tex

-                      r4468a70
+                      r342af53
 % although it's supposed to be in both the TeX Live and MikTeX distributions. There are also documentation and
 % installation instructions there.
+\renewcommand*{\glstextformat}[1]{\textsf{#1}}
 \usepackage{csquotes}
 …
 % Setting up the page margins...
+\setlength{\textheight}{9in}\setlength{\topmargin}{-0.45in}\setlength{\headsep}{0.25in}
 % uWaterloo thesis requirements specify a minimum of 1 inch (72pt) margin at the
 % top, bottom, and outside page edges and a 1.125 in. (81pt) gutter
 …
 % cfa macros used in the document
 \input{common}
+\CFAStyle                                               % CFA code-style for all languages
+\lstset{basicstyle=\linespread{0.9}\tt}
 % glossary of terms to use
 \input{glossary}
+\makeindex
 %======================================================================
 …
 \input{text/io.tex}
 \part{Evaluation}
+\label{Evaluation}
 \chapter{Theoretical and Existance Proofs}
 \chapter{Micro-Benchmarks}
 …
 \addcontentsline{toc}{chapter}{\textbf{References}}
 \bibliography{local}
+\bibliography{local,pl}
 % Tip 5: You can create multiple .bib files to organize your references.
 % Just list them all in the \bibliogaphy command, separated by commas (no spaces).
 …
 \printglossary
 \cleardoublepage
+% Index
+% -----------------------------
+%\input{thesis.ind}                             % index
 \phantomsection

example/io/simple/server_epoll.c

-                      r4468a70
+                      r342af53
+      }
       ev.events = EPOLLIN | EPOLLONESHOT;
+      ev.events = EPOLLOUT | EPOLLIN | EPOLLONESHOT;
       ev.data.u64 = (uint64_t)&ring;
       if (epoll_ctl(epollfd, EPOLL_CTL_ADD, ring.ring_fd, &ev) == -1) {
 …
         while(1) {
             BLOCK:
+            BLOCK:;
             int nfds = epoll_wait(epollfd, events, MAX_EVENTS, -1);
             if (nfds == -1) {

libcfa/src/Makefile.am

-                      r4468a70
+                      r342af53
         concurrency/iofwd.hfa \
         containers/list.hfa \
+        containers/stackLockFree.hfa
+        containers/stackLockFree.hfa \
+        vec/vec.hfa \
+        vec/vec2.hfa \
+        vec/vec3.hfa \
+        vec/vec4.hfa
 inst_headers_src = \
 …
         concurrency/clib/cfathread.h \
         concurrency/invoke.h \
+        concurrency/future.hfa \
         concurrency/kernel/fwd.hfa

libcfa/src/bits/locks.hfa

-                      r4468a70
+                      r342af53
                 void ^?{}(future_t &) {}
+                void reset(future_t & this) {
+                        // needs to be in 0p or 1p
+                        __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST);
+                }
                 // check if the future is available
                 bool available( future_t & this ) {
 …
                 // Mark the future as abandoned, meaning it will be deleted by the server
+                void abandon( future_t & this ) {
+                bool abandon( future_t & this ) {
+                        /* paranoid */ verify( this.ptr != 3p );
+                        // Mark the future as abandonned
                         struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST);
+                        // If the future isn't already fulfilled, let the server delete it
+                        if( got == 0p ) return false;
                         // got == 2p: the future is ready but the context hasn't fully been consumed
 …
                         if( got == 2p ) {
                                 while( this.ptr != 1p ) Pause();
+                        }
+                        return;
+                                got = 1p;
+                        }
+                        // The future is completed delete it now
+                        /* paranoid */ verify( this.ptr != 1p );
+                        free( &this );
+                        return true;
+                }

libcfa/src/concurrency/io.cfa

-                      r4468a70
+                      r342af53
         extern "C" {
-                #include <sys/epoll.h>
                 #include <sys/syscall.h>
 …
         #include "kernel/fwd.hfa"
         #include "io/types.hfa"
+        static const char * opcodes[] = {
+                "OP_NOP",
+                "OP_READV",
+                "OP_WRITEV",
+                "OP_FSYNC",
+                "OP_READ_FIXED",
+                "OP_WRITE_FIXED",
+                "OP_POLL_ADD",
+                "OP_POLL_REMOVE",
+                "OP_SYNC_FILE_RANGE",
+                "OP_SENDMSG",
+                "OP_RECVMSG",
+                "OP_TIMEOUT",
+                "OP_TIMEOUT_REMOVE",
+                "OP_ACCEPT",
+                "OP_ASYNC_CANCEL",
+                "OP_LINK_TIMEOUT",
+                "OP_CONNECT",
+                "OP_FALLOCATE",
+                "OP_OPENAT",
+                "OP_CLOSE",
+                "OP_FILES_UPDATE",
+                "OP_STATX",
+                "OP_READ",
+                "OP_WRITE",
+                "OP_FADVISE",
+                "OP_MADVISE",
+                "OP_SEND",
+                "OP_RECV",
+                "OP_OPENAT2",
+                "OP_EPOLL_CTL",
+                "OP_SPLICE",
+                "OP_PROVIDE_BUFFERS",
+                "OP_REMOVE_BUFFERS",
+                "OP_TEE",
+                "INVALID_OP"
+        };
         // returns true of acquired as leader or second leader
 …
                 int ret = 0;
                 if( need_sys_to_submit || need_sys_to_complete ) {
+                        __cfadbg_print_safe(io_core, "Kernel I/O : IO_URING enter %d %u %u\n", ring.fd, to_submit, flags);
                         ret = syscall( __NR_io_uring_enter, ring.fd, to_submit, 0, flags, (sigset_t *)0p, _NSIG / 8);
                         if( ret < 0 ) {
 …
         static unsigned __collect_submitions( struct __io_data & ring );
         static __u32 __release_consumed_submission( struct __io_data & ring );
+        static inline void process(struct io_uring_cqe & cqe ) {
+        static inline void __clean( volatile struct io_uring_sqe * sqe );
+        // Process a single completion message from the io_uring
+        // This is NOT thread-safe
+        static inline void process( volatile struct io_uring_cqe & cqe ) {
                 struct io_future_t * future = (struct io_future_t *)(uintptr_t)cqe.user_data;
                 __cfadbg_print_safe( io, "Kernel I/O : Syscall completed : cqe %p, result %d for %p\n", &cqe, cqe.res, future );
 …
+        }
-        // Process a single completion message from the io_uring
-        // This is NOT thread-safe
         static [int, bool] __drain_io( & struct __io_data ring ) {
                 /* paranoid */ verify( ! __preemption_enabled() );
 …
+                }
+                __atomic_thread_fence( __ATOMIC_SEQ_CST );
                 // Release the consumed SQEs
                 __release_consumed_submission( ring );
 …
                 for(i; count) {
                         unsigned idx = (head + i) & mask;
                         struct io_uring_cqe & cqe = ring.completion_q.cqes[idx];
+                        volatile struct io_uring_cqe & cqe = ring.completion_q.cqes[idx];
                         /* paranoid */ verify(&cqe);
 …
                 // Mark to the kernel that the cqe has been seen
                 // Ensure that the kernel only sees the new value of the head index after the CQEs have been read.
+                __atomic_thread_fence( __ATOMIC_SEQ_CST );
+                __atomic_fetch_add( ring.completion_q.head, count, __ATOMIC_RELAXED );
+                __atomic_fetch_add( ring.completion_q.head, count, __ATOMIC_SEQ_CST );
                 return [count, count > 0 || to_submit > 0];
 …
         void main( $io_ctx_thread & this ) {
                 epoll_event ev;
+                __ioctx_register( this, ev );
+                __cfadbg_print_safe(io_core, "Kernel I/O : IO poller %p for ring %p ready\n", &this, &this.ring);
                 int reset = 0;
+                __ioctx_register( this );
+                __cfadbg_print_safe(io_core, "Kernel I/O : IO poller %d (%p) ready\n", this.ring->fd, &this);
+                const int reset_cnt = 5;
+                int reset = reset_cnt;
                 // Then loop until we need to start
+                LOOP:
                 while(!__atomic_load_n(&this.done, __ATOMIC_SEQ_CST)) {
                         // Drain the io
 …
                                 [count, again] = __drain_io( *this.ring );
                                 if(!again) reset++;
+                                if(!again) reset--;
                                 // Update statistics
 …
                         // If we got something, just yield and check again
                         if(reset < 5) {
+                        if(reset > 1) {
                                 yield();
+                        }
+                        // We didn't get anything baton pass to the slow poller
+                        else {
+                                continue LOOP;
+                        }
+                        // We alread failed to find completed entries a few time.
+                        if(reset == 1) {
+                                // Rearm the context so it can block
+                                // but don't block right away
+                                // we need to retry one last time in case
+                                // something completed *just now*
+                                __ioctx_prepare_block( this );
+                                continue LOOP;
+                        }
                                 __STATS__( false,
                                         io.complete_q.blocks += 1;
+                                )
+                                __cfadbg_print_safe(io_core, "Kernel I/O : Parking io poller %p\n", &this.self);
+                                reset = 0;
+                                __cfadbg_print_safe(io_core, "Kernel I/O : Parking io poller %d (%p)\n", this.ring->fd, &this);
                                 // block this thread
-                                __ioctx_prepare_block( this, ev );
                                 wait( this.sem );
+                        }
+                }
+                __cfadbg_print_safe(io_core, "Kernel I/O : Fast poller for ring %p stopping\n", &this.ring);
+                        // restore counter
+                        reset = reset_cnt;
+                }
+                __cfadbg_print_safe(io_core, "Kernel I/O : Fast poller %d (%p) stopping\n", this.ring->fd, &this);
+        }
 …
 //
+        [* struct io_uring_sqe, __u32] __submit_alloc( struct __io_data & ring, __u64 data ) {
+        // Allocate an submit queue entry.
+        // The kernel cannot see these entries until they are submitted, but other threads must be
+        // able to see which entries can be used and which are already un used by an other thread
+        // for convenience, return both the index and the pointer to the sqe
+        // sqe == &sqes[idx]
+        [* volatile struct io_uring_sqe, __u32] __submit_alloc( struct __io_data & ring, __u64 data ) {
                 /* paranoid */ verify( data != 0 );
 …
                         // Look through the list starting at some offset
                         for(i; cnt) {
                                 __u64 expected = 0;
                                 __u32 idx = (i + off) & mask;
                                 struct io_uring_sqe * sqe = &ring.submit_q.sqes[idx];
+                                __u64 expected = 3;
+                                __u32 idx = (i + off) & mask; // Get an index from a random
+                                volatile struct io_uring_sqe * sqe = &ring.submit_q.sqes[idx];
                                 volatile __u64 * udata = &sqe->user_data;
+                                // Allocate the entry by CASing the user_data field from 0 to the future address
                                 if( *udata == expected &&
                                         __atomic_compare_exchange_n( udata, &expected, data, true, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED ) )
 …
+                                        )
+                                        // debug log
+                                        __cfadbg_print_safe( io, "Kernel I/O : allocated [%p, %u] for %p (%p)\n", sqe, idx, active_thread(), (void*)data );
                                         // Success return the data
 …
                                 verify(expected != data);
+                                // This one was used
                                 len ++;
+                        }
                         block++;
+                        abort( "Kernel I/O : all submit queue entries used, yielding\n" );
                         yield();
+                }
 …
         void __submit( struct io_context * ctx, __u32 idx ) __attribute__((nonnull (1))) {
                 __io_data & ring = *ctx->thrd.ring;
+                {
+                        __attribute__((unused)) volatile struct io_uring_sqe * sqe = &ring.submit_q.sqes[idx];
+                        __cfadbg_print_safe( io,
+                                "Kernel I/O : submitting %u (%p) for %p\n"
+                                "    data: %p\n"
+                                "    opcode: %s\n"
+                                "    fd: %d\n"
+                                "    flags: %d\n"
+                                "    prio: %d\n"
+                                "    off: %p\n"
+                                "    addr: %p\n"
+                                "    len: %d\n"
+                                "    other flags: %d\n"
+                                "    splice fd: %d\n"
+                                "    pad[0]: %llu\n"
+                                "    pad[1]: %llu\n"
+                                "    pad[2]: %llu\n",
+                                idx, sqe,
+                                active_thread(),
+                                (void*)sqe->user_data,
+                                opcodes[sqe->opcode],
+                                sqe->fd,
+                                sqe->flags,
+                                sqe->ioprio,
+                                sqe->off,
+                                sqe->addr,
+                                sqe->len,
+                                sqe->accept_flags,
+                                sqe->splice_fd_in,
+                                sqe->__pad2[0],
+                                sqe->__pad2[1],
+                                sqe->__pad2[2]
+                        );
+                }
                 // Get now the data we definetely need
                 volatile __u32 * const tail = ring.submit_q.tail;
 …
                                 unlock(ring.submit_q.submit_lock);
                         #endif
+                        if( ret < 0 ) return;
+                        if( ret < 0 ) {
+                                return;
+                        }
                         // Release the consumed SQEs
 …
                                 io.submit_q.submit_avg.cnt += 1;
+                        )
+                }
+                else {
+                        __cfadbg_print_safe( io, "Kernel I/O : submitted %u (among %u) for %p\n", idx, ret, active_thread() );
+                }
+                else
+                {
                         // get mutual exclusion
                         #if defined(LEADER_LOCK)
 …
                         #endif
                         /* paranoid */ verifyf( ring.submit_q.sqes[ idx ].user_data != 0,
+                        /* paranoid */ verifyf( ring.submit_q.sqes[ idx ].user_data != 3ul64,
                         /* paranoid */  "index %u already reclaimed\n"
                         /* paranoid */  "head %u, prev %u, tail %u\n"
 …
+                        }
+                        /* paranoid */ verify(ret == 1);
                         // update statistics
                         __STATS__( false,
 …
+                        )
+                        {
+                                __attribute__((unused)) volatile __u32 * const head = ring.submit_q.head;
+                                __attribute__((unused)) __u32 last_idx = ring.submit_q.array[ ((*head) - 1) & mask ];
+                                __attribute__((unused)) volatile struct io_uring_sqe * sqe = &ring.submit_q.sqes[last_idx];
+                                __cfadbg_print_safe( io,
+                                        "Kernel I/O : last submitted is %u (%p)\n"
+                                        "    data: %p\n"
+                                        "    opcode: %s\n"
+                                        "    fd: %d\n"
+                                        "    flags: %d\n"
+                                        "    prio: %d\n"
+                                        "    off: %p\n"
+                                        "    addr: %p\n"
+                                        "    len: %d\n"
+                                        "    other flags: %d\n"
+                                        "    splice fd: %d\n"
+                                        "    pad[0]: %llu\n"
+                                        "    pad[1]: %llu\n"
+                                        "    pad[2]: %llu\n",
+                                        last_idx, sqe,
+                                        (void*)sqe->user_data,
+                                        opcodes[sqe->opcode],
+                                        sqe->fd,
+                                        sqe->flags,
+                                        sqe->ioprio,
+                                        sqe->off,
+                                        sqe->addr,
+                                        sqe->len,
+                                        sqe->accept_flags,
+                                        sqe->splice_fd_in,
+                                        sqe->__pad2[0],
+                                        sqe->__pad2[1],
+                                        sqe->__pad2[2]
+                                );
+                        }
+                        __atomic_thread_fence( __ATOMIC_SEQ_CST );
                         // Release the consumed SQEs
                         __release_consumed_submission( ring );
+                        // ring.submit_q.sqes[idx].user_data = 3ul64;
                         #if defined(LEADER_LOCK)
 …
                         #endif
                         __cfadbg_print_safe( io, "Kernel I/O : Performed io_submit for %p, returned %d\n", active_thread(), ret );
+                        __cfadbg_print_safe( io, "Kernel I/O : submitted %u for %p\n", idx, active_thread() );
+                }
+        }
         // #define PARTIAL_SUBMIT 32
+        // go through the list of submissions in the ready array and moved them into
+        // the ring's submit queue
         static unsigned __collect_submitions( struct __io_data & ring ) {
                 /* paranoid */ verify( ring.submit_q.ready != 0p );
 …
+        }
+        // Go through the ring's submit queue and release everything that has already been consumed
+        // by io_uring
         static __u32 __release_consumed_submission( struct __io_data & ring ) {
                 const __u32 smask = *ring.submit_q.mask;
+                // We need to get the lock to copy the old head and new head
                 if( !try_lock(ring.submit_q.release_lock __cfaabi_dbg_ctx2) ) return 0;
+                __u32 chead = *ring.submit_q.head;
+                __u32 phead = ring.submit_q.prev_head;
+                ring.submit_q.prev_head = chead;
+                __attribute__((unused))
+                __u32 ctail = *ring.submit_q.tail;        // get the current tail of the queue
+                __u32 chead = *ring.submit_q.head;              // get the current head of the queue
+                __u32 phead = ring.submit_q.prev_head;  // get the head the last time we were here
+                ring.submit_q.prev_head = chead;                // note up to were we processed
                 unlock(ring.submit_q.release_lock);
+                // the 3 fields are organized like this diagram
+                // except it's are ring
+                // ---+--------+--------+----
+                // ---+--------+--------+----
+                //    ^        ^        ^
+                // phead    chead    ctail
+                // make sure ctail doesn't wrap around and reach phead
+                /* paranoid */ verify(
+                           (ctail >= chead && chead >= phead)
+                        || (chead >= phead && phead >= ctail)
+                        || (phead >= ctail && ctail >= chead)
+                );
+                // find the range we need to clear
                 __u32 count = chead - phead;
+                // We acquired an previous-head/current-head range
+                // go through the range and release the sqes
                 for( i; count ) {
                         __u32 idx = ring.submit_q.array[ (phead + i) & smask ];
+                        ring.submit_q.sqes[ idx ].user_data = 0;
+                        /* paranoid */ verify( 0 != ring.submit_q.sqes[ idx ].user_data );
+                        __clean( &ring.submit_q.sqes[ idx ] );
+                }
                 return count;
+        }
+        void __sqe_clean( volatile struct io_uring_sqe * sqe ) {
+                __clean( sqe );
+        }
+        static inline void __clean( volatile struct io_uring_sqe * sqe ) {
+                // If we are in debug mode, thrash the fields to make sure we catch reclamation errors
+                __cfaabi_dbg_debug_do(
+                        memset(sqe, 0xde, sizeof(*sqe));
+                        sqe->opcode = (sizeof(opcodes) / sizeof(const char *)) - 1;
+                );
+                // Mark the entry as unused
+                __atomic_store_n(&sqe->user_data, 3ul64, __ATOMIC_SEQ_CST);
+        }
 #endif

libcfa/src/concurrency/io/call.cfa.in

-                      r4468a70
+                      r342af53
+        ;
         extern [* struct io_uring_sqe, __u32] __submit_alloc( struct __io_data & ring, __u64 data );
+        extern [* volatile struct io_uring_sqe, __u32] __submit_alloc( struct __io_data & ring, __u64 data );
         extern void __submit( struct io_context * ctx, __u32 idx ) __attribute__((nonnull (1)));
 …
                 __u32 idx;
                 struct io_uring_sqe * sqe;
+                [sqe, idx] = __submit_alloc( ring, (__u64)(uintptr_t)&future );
+                sqe->__pad2[0] = sqe->__pad2[1] = sqe->__pad2[2] = 0;
+                [(volatile struct io_uring_sqe *) sqe, idx] = __submit_alloc( ring, (__u64)(uintptr_t)&future );
                 sqe->opcode = IORING_OP_{op};
+                sqe->flags = sflags;{body}
+                sqe->flags = sflags;
+                sqe->ioprio = 0;
+                sqe->fd = 0;
+                sqe->off = 0;
+                sqe->addr = 0;
+                sqe->len = 0;
+                sqe->fsync_flags = 0;
+                sqe->__pad2[0] = 0;
+                sqe->__pad2[1] = 0;
+                sqe->__pad2[2] = 0;{body}
+                asm volatile("": : :"memory");
                 verify( sqe->user_data == (__u64)(uintptr_t)&future );
 …
         }),
         # CFA_HAVE_IORING_OP_ACCEPT
         Call('ACCEPT4', 'int accept4(int sockfd, struct sockaddr *addr, socklen_t *addrlen, int flags)', {
+        Call('ACCEPT', 'int accept4(int sockfd, struct sockaddr *addr, socklen_t *addrlen, int flags)', {
                 'fd': 'sockfd',
                 'addr': 'addr',
                 'addr2': 'addrlen',
+                'addr': '(__u64)addr',
+                'addr2': '(__u64)addrlen',
                 'accept_flags': 'flags'
         }),
 …
 print("""
+//-----------------------------------------------------------------------------
+bool cancel(io_cancellation & this) {
+        #if !defined(CFA_HAVE_LINUX_IO_URING_H) || !defined(CFA_HAVE_IORING_OP_ASYNC_CANCEL)
+                return false;
+        #else
+                io_future_t future;
+                io_context * context = __get_io_context();
+                __u8 sflags = 0;
+                struct __io_data & ring = *context->thrd.ring;
+                __u32 idx;
+                volatile struct io_uring_sqe * sqe;
+                [sqe, idx] = __submit_alloc( ring, (__u64)(uintptr_t)&future );
+                sqe->__pad2[0] = sqe->__pad2[1] = sqe->__pad2[2] = 0;
+                sqe->opcode = IORING_OP_ASYNC_CANCEL;
+                sqe->flags = sflags;
+                sqe->addr = this.target;
+                verify( sqe->user_data == (__u64)(uintptr_t)&future );
+                __submit( context, idx );
+                wait(future);
+                if( future.result == 0 ) return true; // Entry found
+                if( future.result == -EALREADY) return true; // Entry found but in progress
+                if( future.result == -ENOENT ) return false; // Entry not found
+                return false;
+        #endif
+}
 //-----------------------------------------------------------------------------
 // Check if a function is has asynchronous

libcfa/src/concurrency/io/setup.cfa

-                      r4468a70
+                      r342af53
                 #include <pthread.h>
                 #include <sys/epoll.h>
+                #include <sys/eventfd.h>
                 #include <sys/mman.h>
                 #include <sys/syscall.h>
 …
                 // Main loop
                 while( iopoll.run ) {
+                        __cfadbg_print_safe(io_core, "Kernel I/O - epoll : waiting on io_uring contexts\n");
                         // Wait for events
                         int nfds = epoll_pwait( iopoll.epollfd, events, 10, -1, &mask );
+                        __cfadbg_print_safe(io_core, "Kernel I/O - epoll : %d io contexts events, waking up\n", nfds);
                         // Check if an error occured
 …
                                 $io_ctx_thread * io_ctx = ($io_ctx_thread *)(uintptr_t)events[i].data.u64;
                                 /* paranoid */ verify( io_ctx );
                                 __cfadbg_print_safe(io_core, "Kernel I/O : Unparking io poller %p\n", io_ctx);
+                                __cfadbg_print_safe(io_core, "Kernel I/O - epoll : Unparking io poller %d (%p)\n", io_ctx->ring->fd, io_ctx);
                                 #if !defined( __CFA_NO_STATISTICS__ )
                                         __cfaabi_tls.this_stats = io_ctx->self.curr_cluster->stats;
                                 #endif
+                                eventfd_t v;
+                                eventfd_read(io_ctx->ring->efd, &v);
                                 post( io_ctx->sem );
+                        }
 …
                 $thread & thrd = this.thrd.self;
                 if( cluster_context ) {
+                        // We are about to do weird things with the threads
+                        // we don't need interrupts to complicate everything
+                        disable_interrupts();
+                        // Get cluster info
                         cluster & cltr = *thrd.curr_cluster;
                         /* paranoid */ verify( cltr.idles.total == 0 || &cltr == mainCluster );
 …
                         // We need to adjust the clean-up based on where the thread is
                         if( thrd.state == Ready || thrd.preempted != __NO_PREEMPTION ) {
+                                // This is the tricky case
+                                // The thread was preempted or ready to run and now it is on the ready queue
+                                // but the cluster is shutting down, so there aren't any processors to run the ready queue
+                                // the solution is to steal the thread from the ready-queue and pretend it was blocked all along
                                 ready_schedule_lock();
+                                        // This is the tricky case
+                                        // The thread was preempted and now it is on the ready queue
+                                        // The thread should on the list
+                                        /* paranoid */ verify( thrd.link.next != 0p );
+                                        // Remove the thread from the ready queue of this cluster
                                         // The thread should be the last on the list
-                                        /* paranoid */ verify( thrd.link.next != 0p );
-                                        // Remove the thread from the ready queue of this cluster
                                         __attribute__((unused)) bool removed = remove_head( &cltr, &thrd );
                                         /* paranoid */ verify( removed );
 …
+                        }
                         // !!! This is not an else if !!!
+                        // Ok, now the thread is blocked (whether we cheated to get here or not)
                         if( thrd.state == Blocked ) {
                                 // This is the "easy case"
                                 // The thread is parked and can easily be moved to active cluster
 …
+                        }
                         else {
                                 // The thread is in a weird state
                                 // I don't know what to do here
                                 abort("io_context poller thread is in unexpected state, cannot clean-up correctly\n");
+                        }
+                        // The weird thread kidnapping stuff is over, restore interrupts.
+                        enable_interrupts( __cfaabi_dbg_ctx );
                 } else {
                         post( this.thrd.sem );
 …
+                }
+                // Step 3 : Initialize the data structure
                 // Get the pointers from the kernel to fill the structure
                 // submit queue
 …
                         const __u32 num = *sq.num;
                         for( i; num ) {
                                 sq.sqes[i].user_data = 0ul64;
+                                __sqe_clean( &sq.sqes[i] );
+                        }
+                }
 …
                 cq.cqes = (struct io_uring_cqe *)(((intptr_t)cq.ring_ptr) + params.cq_off.cqes);
+                // Step 4 : eventfd
+                int efd;
+                for() {
+                        efd = eventfd(0, 0);
+                        if (efd < 0) {
+                                if (errno == EINTR) continue;
+                                abort("KERNEL ERROR: IO_URING EVENTFD - %s\n", strerror(errno));
+                        }
+                        break;
+                }
+                int ret;
+                for() {
+                        ret = syscall( __NR_io_uring_register, fd, IORING_REGISTER_EVENTFD, &efd, 1);
+                        if (ret < 0) {
+                                if (errno == EINTR) continue;
+                                abort("KERNEL ERROR: IO_URING EVENTFD REGISTER - %s\n", strerror(errno));
+                        }
+                        break;
+                }
                 // some paranoid checks
                 /* paranoid */ verifyf( (*cq.mask) == ((*cq.num) - 1ul32), "IO_URING Expected mask to be %u (%u entries), was %u", (*cq.num) - 1ul32, *cq.num, *cq.mask  );
 …
                 this.ring_flags = params.flags;
                 this.fd         = fd;
+                this.efd        = efd;
                 this.eager_submits  = params_in.eager_submits;
                 this.poller_submits = params_in.poller_submits;
 …
                 // close the file descriptor
                 close(this.fd);
+                close(this.efd);
                 free( this.submit_q.ready ); // Maybe null, doesn't matter
 …
 // I/O Context Sleep
 //=============================================================================================
+        void __ioctx_register($io_ctx_thread & ctx, struct epoll_event & ev) {
+                ev.events = EPOLLIN | EPOLLONESHOT;
+        #define IOEVENTS EPOLLIN | EPOLLONESHOT
+        static inline void __ioctx_epoll_ctl($io_ctx_thread & ctx, int op, const char * error) {
+                struct epoll_event ev;
+                ev.events = IOEVENTS;
                 ev.data.u64 = (__u64)&ctx;
                 int ret = epoll_ctl(iopoll.epollfd, EPOLL_CTL_ADD, ctx.ring->fd, &ev);
+                int ret = epoll_ctl(iopoll.epollfd, op, ctx.ring->efd, &ev);
                 if (ret < 0) {
+                        abort( "KERNEL ERROR: EPOLL ADD - (%d) %s\n", (int)errno, strerror(errno) );
+                }
+        }
+        void __ioctx_prepare_block($io_ctx_thread & ctx, struct epoll_event & ev) {
+                int ret = epoll_ctl(iopoll.epollfd, EPOLL_CTL_MOD, ctx.ring->fd, &ev);
+                if (ret < 0) {
+                        abort( "KERNEL ERROR: EPOLL REARM - (%d) %s\n", (int)errno, strerror(errno) );
+                }
+                        abort( "KERNEL ERROR: EPOLL %s - (%d) %s\n", error, (int)errno, strerror(errno) );
+                }
+        }
+        void __ioctx_register($io_ctx_thread & ctx) {
+                __ioctx_epoll_ctl(ctx, EPOLL_CTL_ADD, "ADD");
+        }
+        void __ioctx_prepare_block($io_ctx_thread & ctx) {
+                __cfadbg_print_safe(io_core, "Kernel I/O - epoll : Re-arming io poller %d (%p)\n", ctx.ring->fd, &ctx);
+                __ioctx_epoll_ctl(ctx, EPOLL_CTL_MOD, "REARM");
+        }

libcfa/src/concurrency/io/types.hfa

-                      r4468a70
+                      r342af53
                 // A buffer of sqes (not the actual ring)
                 struct io_uring_sqe * sqes;
+                volatile struct io_uring_sqe * sqes;
                 // The location and size of the mmaped area
 …
                 // the kernel ring
                 struct io_uring_cqe * cqes;
+                volatile struct io_uring_cqe * cqes;
                 // The location and size of the mmaped area
 …
                 __u32 ring_flags;
                 int fd;
+                int efd;
                 bool eager_submits:1;
                 bool poller_submits:1;
 …
         #endif
-        struct epoll_event;
         struct $io_ctx_thread;
+        void __ioctx_register($io_ctx_thread & ctx, struct epoll_event & ev);
+        void __ioctx_prepare_block($io_ctx_thread & ctx, struct epoll_event & ev);
+        void __ioctx_register($io_ctx_thread & ctx);
+        void __ioctx_prepare_block($io_ctx_thread & ctx);
+        void __sqe_clean( volatile struct io_uring_sqe * sqe );
 #endif

libcfa/src/concurrency/monitor.hfa

-                      r4468a70
+                      r342af53
               void wait        ( condition & this, uintptr_t user_info = 0 );
+static inline bool is_empty    ( condition & this ) { return this.blocked.head == 1p; }
               bool signal      ( condition & this );
               bool signal_block( condition & this );
 static inline bool is_empty    ( condition & this ) { return this.blocked.head == 1p; }
+static inline bool signal_all  ( condition & this ) { bool ret = false; while(!is_empty(this)) { ret = signal(this) || ret; } return ret; }
          uintptr_t front       ( condition & this );

libcfa/src/heap.cfa

-                      r4468a70
+                      r342af53
 // Created On       : Tue Dec 19 21:58:35 2017
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Wed Dec 16 12:28:25 2020
 // Update Count     : 1023
+// Last Modified On : Sun Jan 10 11:20:49 2021
+// Update Count     : 1031
 //
 …
 #ifdef __STATISTICS__
 // Heap statistics counters.
 static unsigned int malloc_calls;
+static unsigned int malloc_zero_calls, malloc_calls;
 static unsigned long long int malloc_storage;
 static unsigned int aalloc_calls;
+static unsigned int aalloc_zero_calls, aalloc_calls;
 static unsigned long long int aalloc_storage;
 static unsigned int calloc_calls;
+static unsigned int calloc_zero_calls, calloc_calls;
 static unsigned long long int calloc_storage;
 static unsigned int memalign_calls;
+static unsigned int memalign_zero_calls, memalign_calls;
 static unsigned long long int memalign_storage;
 static unsigned int amemalign_calls;
+static unsigned int amemalign_zero_calls, amemalign_calls;
 static unsigned long long int amemalign_storage;
 static unsigned int cmemalign_calls;
+static unsigned int cmemalign_zero_calls, cmemalign_calls;
 static unsigned long long int cmemalign_storage;
 static unsigned int resize_calls;
+static unsigned int resize_zero_calls, resize_calls;
 static unsigned long long int resize_storage;
 static unsigned int realloc_calls;
+static unsigned int realloc_zero_calls, realloc_calls;
 static unsigned long long int realloc_storage;
 static unsigned int free_calls;
+static unsigned int free_zero_calls, free_calls;
 static unsigned long long int free_storage;
 static unsigned int mmap_calls;
 …
 static unsigned long long int sbrk_storage;
 // Statistics file descriptor (changed by malloc_stats_fd).
 static int stat_fd = STDERR_FILENO;                                             // default stderr
+static int stats_fd = STDERR_FILENO;                                    // default stderr
 // Use "write" because streams may be shutdown when calls are made.
 …
         char helpText[1024];
         __cfaabi_bits_print_buffer( STDERR_FILENO, helpText, sizeof(helpText),
                                                                         "\nHeap statistics:\n"
                                                                         "  malloc: calls %u / storage %llu\n"
                                                                         "  aalloc: calls %u / storage %llu\n"
                                                                         "  calloc: calls %u / storage %llu\n"
                                                                         "  memalign: calls %u / storage %llu\n"
                                                                         "  amemalign: calls %u / storage %llu\n"
                                                                         "  cmemalign: calls %u / storage %llu\n"
                                                                         "  resize: calls %u / storage %llu\n"
                                                                         "  realloc: calls %u / storage %llu\n"
                                                                         "  free: calls %u / storage %llu\n"
                                                                         "  mmap: calls %u / storage %llu\n"
                                                                         "  munmap: calls %u / storage %llu\n"
                                                                         "  sbrk: calls %u / storage %llu\n",
                                                                         malloc_calls, malloc_storage,
                                                                         aalloc_calls, aalloc_storage,
                                                                         calloc_calls, calloc_storage,
                                                                         memalign_calls, memalign_storage,
                                                                         amemalign_calls, amemalign_storage,
                                                                         cmemalign_calls, cmemalign_storage,
                                                                         resize_calls, resize_storage,
                                                                         realloc_calls, realloc_storage,
                                                                         free_calls, free_storage,
                                                                         mmap_calls, mmap_storage,
                                                                         munmap_calls, munmap_storage,
                                                                         sbrk_calls, sbrk_storage
+                                                                "\nHeap statistics:\n"
+                                                                "  malloc    0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  aalloc    0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  calloc    0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  memalign  0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  amemalign 0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  cmemalign 0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  resize    0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  realloc   0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  free      0-calls %'u; >0-calls %'u; storage %'llu bytes\n"
+                                                                "  mmap      calls %'u; storage %'llu bytes\n"
+                                                                "  munmap    calls %'u; storage %'llu bytes\n"
+                                                                "  sbrk      calls %'u; storage %'llu bytes\n",
+                                                                malloc_zero_calls, malloc_calls, malloc_storage,
+                                                                aalloc_zero_calls, aalloc_calls, aalloc_storage,
+                                                                calloc_zero_calls, calloc_calls, calloc_storage,
+                                                                memalign_zero_calls, memalign_calls, memalign_storage,
+                                                                amemalign_zero_calls, amemalign_calls, amemalign_storage,
+                                                                cmemalign_zero_calls, cmemalign_calls, cmemalign_storage,
+                                                                resize_zero_calls, resize_calls, resize_storage,
+                                                                realloc_zero_calls, realloc_calls, realloc_storage,
+                                                                free_zero_calls, free_calls, free_storage,
+                                                                mmap_calls, mmap_storage,
+                                                                munmap_calls, munmap_storage,
+                                                                sbrk_calls, sbrk_storage
                 );
 } // printStats
 …
                                                 "<sizes>\n"
                                                 "</sizes>\n"
                                                 "<total type=\"malloc\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"aalloc\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"calloc\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"memalign\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"amemalign\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"cmemalign\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"resize\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"realloc\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"free\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"mmap\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"munmap\" count=\"%u\" size=\"%llu\"/>\n"
                                                 "<total type=\"sbrk\" count=\"%u\" size=\"%llu\"/>\n"
+                                                "<total type=\"malloc\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"aalloc\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"calloc\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"memalign\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"amemalign\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"cmemalign\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"resize\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"realloc\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"free\" 0 count=\"%'u;\" >0 count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"mmap\" count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"munmap\" count=\"%'u;\" size=\"%'llu\"/> bytes\n"
+                                                "<total type=\"sbrk\" count=\"%'u;\" size=\"%'llu\"/> bytes\n"
                                                 "</malloc>",
                                                 malloc_calls, malloc_storage,
                                                 aalloc_calls, aalloc_storage,
                                                 calloc_calls, calloc_storage,
                                                 memalign_calls, memalign_storage,
                                                 amemalign_calls, amemalign_storage,
                                                 cmemalign_calls, cmemalign_storage,
                                                 resize_calls, resize_storage,
                                                 realloc_calls, realloc_storage,
                                                 free_calls, free_storage,
+                                                malloc_zero_calls, malloc_calls, malloc_storage,
+                                                aalloc_zero_calls, aalloc_calls, aalloc_storage,
+                                                calloc_zero_calls, calloc_calls, calloc_storage,
+                                                memalign_zero_calls, memalign_calls, memalign_storage,
+                                                amemalign_zero_calls, amemalign_calls, amemalign_storage,
+                                                cmemalign_zero_calls, cmemalign_calls, cmemalign_storage,
+                                                resize_zero_calls, resize_calls, resize_storage,
+                                                realloc_zero_calls, realloc_calls, realloc_storage,
+                                                free_zero_calls, free_calls, free_storage,
                                                 mmap_calls, mmap_storage,
                                                 munmap_calls, munmap_storage,
 …
 } // headers
 #ifdef __CFA_DEBUG__
 #if __SIZEOF_POINTER__ == 4
 #define MASK 0xdeadbeef
 #else
 #define MASK 0xdeadbeefdeadbeef
 #endif
 #define STRIDE size_t
 static void * Memset( void * addr, STRIDE size ) {              // debug only
         if ( size % sizeof(STRIDE) != 0 ) abort( "Memset() : internal error, size %zd not multiple of %zd.", size, sizeof(STRIDE) );
         if ( (STRIDE)addr % sizeof(STRIDE) != 0 ) abort( "Memset() : internal error, addr %p not multiple of %zd.", addr, sizeof(STRIDE) );
         STRIDE * end = (STRIDE *)addr + size / sizeof(STRIDE);
         for ( STRIDE * p = (STRIDE *)addr; p < end; p += 1 ) *p = MASK;
         return addr;
 } // Memset
 #endif // __CFA_DEBUG__
+// #ifdef __CFA_DEBUG__
+// #if __SIZEOF_POINTER__ == 4
+// #define MASK 0xdeadbeef
+// #else
+// #define MASK 0xdeadbeefdeadbeef
+// #endif
+// #define STRIDE size_t
+// static void * Memset( void * addr, STRIDE size ) {           // debug only
+//      if ( size % sizeof(STRIDE) != 0 ) abort( "Memset() : internal error, size %zd not multiple of %zd.", size, sizeof(STRIDE) );
+//      if ( (STRIDE)addr % sizeof(STRIDE) != 0 ) abort( "Memset() : internal error, addr %p not multiple of %zd.", addr, sizeof(STRIDE) );
+//      STRIDE * end = (STRIDE *)addr + size / sizeof(STRIDE);
+//      for ( STRIDE * p = (STRIDE *)addr; p < end; p += 1 ) *p = MASK;
+//      return addr;
+// } // Memset
+// #endif // __CFA_DEBUG__
 …
                         unlock( extlock );
                         __cfaabi_bits_print_nolock( STDERR_FILENO, NO_MEMORY_MSG, size );
+                        _exit( EXIT_FAILURE );
+                } // if
+                        _exit( EXIT_FAILURE );                                          // give up
+                } // if
+                // Make storage executable for thunks.
                 if ( mprotect( (char *)heapEnd + heapRemaining, increase, __map_prot ) ) {
                         unlock( extlock );
 …
-static inline void * callocNoStats( size_t dim, size_t elemSize ) {
-        size_t size = dim * elemSize;
-  if ( unlikely( size ) == 0 ) return 0p;                               // 0 BYTE ALLOCATION RETURNS NULL POINTER
-        char * addr = (char *)mallocNoStats( size );
-        HeapManager.Storage.Header * header;
-        HeapManager.FreeHeader * freeElem;
-        size_t bsize, alignment;
-        #ifndef __CFA_DEBUG__
-        bool mapped =
-        #endif // __CFA_DEBUG__
-                headers( "calloc", addr, header, freeElem, bsize, alignment );
-        #ifndef __CFA_DEBUG__
-        // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
-        if ( ! mapped )
-        #endif // __CFA_DEBUG__
-                // <-------0000000000000000000000000000UUUUUUUUUUUUUUUUUUUUUUUUU> bsize (bucket size) U => undefined
-                // `-header`-addr                      `-size
-                memset( addr, '\0', size );                                             // set to zeros
-        header->kind.real.blockSize |= 2;                                       // mark as zero filled
-        return addr;
-} // callocNoStats
 static inline void * memalignNoStats( size_t alignment, size_t size ) {
   if ( unlikely( size ) == 0 ) return 0p;                               // 0 BYTE ALLOCATION RETURNS NULL POINTER
 …
-static inline void * cmemalignNoStats( size_t alignment, size_t dim, size_t elemSize ) {
-        size_t size = dim * elemSize;
-  if ( unlikely( size ) == 0 ) return 0p;                               // 0 BYTE ALLOCATION RETURNS NULL POINTER
-        char * addr = (char *)memalignNoStats( alignment, size );
-        HeapManager.Storage.Header * header;
-        HeapManager.FreeHeader * freeElem;
-        size_t bsize;
-        #ifndef __CFA_DEBUG__
-        bool mapped =
-        #endif // __CFA_DEBUG__
-                headers( "cmemalign", addr, header, freeElem, bsize, alignment );
-        // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
-        #ifndef __CFA_DEBUG__
-        if ( ! mapped )
-        #endif // __CFA_DEBUG__
-                // <-------0000000000000000000000000000UUUUUUUUUUUUUUUUUUUUUUUUU> bsize (bucket size) U => undefined
-                // `-header`-addr                      `-size
-                memset( addr, '\0', size );                                             // set to zeros
-        header->kind.real.blockSize |= 2;                                       // mark as zero filled
-        return addr;
-} // cmemalignNoStats
 extern "C" {
         // Allocates size bytes and returns a pointer to the allocated memory.  The contents are undefined. If size is 0,
 …
         void * malloc( size_t size ) {
                 #ifdef __STATISTICS__
+                __atomic_add_fetch( &malloc_calls, 1, __ATOMIC_SEQ_CST );
+                __atomic_add_fetch( &malloc_storage, size, __ATOMIC_SEQ_CST );
+                if ( likely( size > 0 ) ) {
+                        __atomic_add_fetch( &malloc_calls, 1, __ATOMIC_SEQ_CST );
+                        __atomic_add_fetch( &malloc_storage, size, __ATOMIC_SEQ_CST );
+                } else {
+                        __atomic_add_fetch( &malloc_zero_calls, 1, __ATOMIC_SEQ_CST );
+                } // if
                 #endif // __STATISTICS__
 …
                 size_t size = dim * elemSize;
                 #ifdef __STATISTICS__
+                __atomic_add_fetch( &aalloc_calls, 1, __ATOMIC_SEQ_CST );
+                __atomic_add_fetch( &aalloc_storage, size, __ATOMIC_SEQ_CST );
+                if ( likely( size > 0 ) ) {
+                        __atomic_add_fetch( &aalloc_calls, 1, __ATOMIC_SEQ_CST );
+                        __atomic_add_fetch( &aalloc_storage, size, __ATOMIC_SEQ_CST );
+                } else {
+                        __atomic_add_fetch( &aalloc_zero_calls, 1, __ATOMIC_SEQ_CST );
+                } // if
                 #endif // __STATISTICS__
 …
         // Same as aalloc() with memory set to zero.
         void * calloc( size_t dim, size_t elemSize ) {
+                size_t size = dim * elemSize;
+          if ( unlikely( size ) == 0 ) {                        // 0 BYTE ALLOCATION RETURNS NULL POINTER
+                        #ifdef __STATISTICS__
+                        __atomic_add_fetch( &calloc_zero_calls, 1, __ATOMIC_SEQ_CST );
+                        #endif // __STATISTICS__
+                        return 0p;
+                } // if
                 #ifdef __STATISTICS__
                 __atomic_add_fetch( &calloc_calls, 1, __ATOMIC_SEQ_CST );
 …
                 #endif // __STATISTICS__
+                return callocNoStats( dim, elemSize );
+                char * addr = (char *)mallocNoStats( size );
+                HeapManager.Storage.Header * header;
+                HeapManager.FreeHeader * freeElem;
+                size_t bsize, alignment;
+                #ifndef __CFA_DEBUG__
+                bool mapped =
+                        #endif // __CFA_DEBUG__
+                        headers( "calloc", addr, header, freeElem, bsize, alignment );
+                #ifndef __CFA_DEBUG__
+                // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
+                if ( ! mapped )
+                #endif // __CFA_DEBUG__
+                        // <-------0000000000000000000000000000UUUUUUUUUUUUUUUUUUUUUUUUU> bsize (bucket size) U => undefined
+                        // `-header`-addr                      `-size
+                        memset( addr, '\0', size );                                     // set to zeros
+                header->kind.real.blockSize |= 2;                               // mark as zero filled
+                return addr;
         } // calloc
 …
         // call to malloc(), alloc(), calloc() or realloc(). If the area pointed to was moved, a free(oaddr) is done.
         void * resize( void * oaddr, size_t size ) {
+                // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
+          if ( unlikely( size == 0 ) ) {                                        // special cases
+                        #ifdef __STATISTICS__
+                        __atomic_add_fetch( &resize_zero_calls, 1, __ATOMIC_SEQ_CST );
+                        #endif // __STATISTICS__
+                        free( oaddr );
+                        return 0p;
+                } // if
                 #ifdef __STATISTICS__
                 __atomic_add_fetch( &resize_calls, 1, __ATOMIC_SEQ_CST );
                 #endif // __STATISTICS__
-                // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
-          if ( unlikely( size == 0 ) ) { free( oaddr ); return 0p; } // special cases
           if ( unlikely( oaddr == 0p ) ) {
                         #ifdef __STATISTICS__
 …
                 size_t bsize, oalign;
                 headers( "resize", oaddr, header, freeElem, bsize, oalign );
                 size_t odsize = dataStorage( bsize, oaddr, header ); // data storage available in bucket
                 // same size, DO NOT preserve STICKY PROPERTIES.
                 if ( oalign == libAlign() && size <= odsize && odsize <= size * 2 ) { // allow 50% wasted storage for smaller size
 …
         // the old and new sizes.
         void * realloc( void * oaddr, size_t size ) {
+                // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
+          if ( unlikely( size == 0 ) ) {                                        // special cases
+                        #ifdef __STATISTICS__
+                        __atomic_add_fetch( &realloc_zero_calls, 1, __ATOMIC_SEQ_CST );
+                        #endif // __STATISTICS__
+                        free( oaddr );
+                        return 0p;
+                } // if
                 #ifdef __STATISTICS__
                 __atomic_add_fetch( &realloc_calls, 1, __ATOMIC_SEQ_CST );
                 #endif // __STATISTICS__
-                // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
-          if ( unlikely( size == 0 ) ) { free( oaddr ); return 0p; } // special cases
           if ( unlikely( oaddr == 0p ) ) {
                         #ifdef __STATISTICS__
 …
         void * memalign( size_t alignment, size_t size ) {
                 #ifdef __STATISTICS__
+                __atomic_add_fetch( &memalign_calls, 1, __ATOMIC_SEQ_CST );
+                __atomic_add_fetch( &memalign_storage, size, __ATOMIC_SEQ_CST );
+                if ( likely( size > 0 ) ) {
+                        __atomic_add_fetch( &memalign_calls, 1, __ATOMIC_SEQ_CST );
+                        __atomic_add_fetch( &memalign_storage, size, __ATOMIC_SEQ_CST );
+                } else {
+                        __atomic_add_fetch( &memalign_zero_calls, 1, __ATOMIC_SEQ_CST );
+                } // if
                 #endif // __STATISTICS__
 …
                 size_t size = dim * elemSize;
                 #ifdef __STATISTICS__
+                __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST );
+                __atomic_add_fetch( &cmemalign_storage, size, __ATOMIC_SEQ_CST );
+                if ( likely( size > 0 ) ) {
+                        __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST );
+                        __atomic_add_fetch( &cmemalign_storage, size, __ATOMIC_SEQ_CST );
+                } else {
+                        __atomic_add_fetch( &cmemalign_zero_calls, 1, __ATOMIC_SEQ_CST );
+                } // if
                 #endif // __STATISTICS__
 …
         // Same as calloc() with memory alignment.
         void * cmemalign( size_t alignment, size_t dim, size_t elemSize ) {
+                size_t size = dim * elemSize;
+          if ( unlikely( size ) == 0 ) {                                        // 0 BYTE ALLOCATION RETURNS NULL POINTER
+                        #ifdef __STATISTICS__
+                        __atomic_add_fetch( &cmemalign_zero_calls, 1, __ATOMIC_SEQ_CST );
+                        #endif // __STATISTICS__
+                        return 0p;
+                } // if
                 #ifdef __STATISTICS__
                 __atomic_add_fetch( &cmemalign_calls, 1, __ATOMIC_SEQ_CST );
 …
                 #endif // __STATISTICS__
+                return cmemalignNoStats( alignment, dim, elemSize );
+                char * addr = (char *)memalignNoStats( alignment, size );
+                HeapManager.Storage.Header * header;
+                HeapManager.FreeHeader * freeElem;
+                size_t bsize;
+                #ifndef __CFA_DEBUG__
+                bool mapped =
+                        #endif // __CFA_DEBUG__
+                        headers( "cmemalign", addr, header, freeElem, bsize, alignment );
+                // Mapped storage is zero filled, but in debug mode mapped memory is scrubbed in doMalloc, so it has to be reset to zero.
+                #ifndef __CFA_DEBUG__
+                if ( ! mapped )
+                #endif // __CFA_DEBUG__
+                        // <-------0000000000000000000000000000UUUUUUUUUUUUUUUUUUUUUUUUU> bsize (bucket size) U => undefined
+                        // `-header`-addr                      `-size
+                        memset( addr, '\0', size );                                     // set to zeros
+                header->kind.real.blockSize |= 2;                               // mark as zero filled
+                return addr;
         } // cmemalign
 …
         // 0p, no operation is performed.
         void free( void * addr ) {
-                #ifdef __STATISTICS__
-                __atomic_add_fetch( &free_calls, 1, __ATOMIC_SEQ_CST );
-                #endif // __STATISTICS__
           if ( unlikely( addr == 0p ) ) {                                       // special case
+                        #ifdef __STATISTICS__
+                        __atomic_add_fetch( &free_zero_calls, 1, __ATOMIC_SEQ_CST );
+                        #endif // __STATISTICS__
                         // #ifdef __CFA_DEBUG__
                         // if ( traceHeap() ) {
 …
         int malloc_stats_fd( int fd __attribute__(( unused )) ) {
                 #ifdef __STATISTICS__
                 int temp = stat_fd;
                 stat_fd = fd;
+                int temp = stats_fd;
+                stats_fd = fd;
                 return temp;
                 #else
 …
         // The string is printed on the file stream stream.  The exported string includes information about all arenas (see
         // malloc).
         int malloc_info( int options, FILE * stream ) {
+        int malloc_info( int options, FILE * stream __attribute__(( unused )) ) {
           if ( options != 0 ) { errno = EINVAL; return -1; }
                 #ifdef __STATISTICS__
 …
 // Must have CFA linkage to overload with C linkage realloc.
 void * resize( void * oaddr, size_t nalign, size_t size ) {
+        #ifdef __STATISTICS__
+        __atomic_add_fetch( &resize_calls, 1, __ATOMIC_SEQ_CST );
+        #endif // __STATISTICS__
+        // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
+  if ( unlikely( size == 0 ) ) {                                                // special cases
+                #ifdef __STATISTICS__
+                __atomic_add_fetch( &resize_zero_calls, 1, __ATOMIC_SEQ_CST );
+                #endif // __STATISTICS__
+                free( oaddr );
+                return 0p;
+        } // if
         if ( unlikely( nalign < libAlign() ) ) nalign = libAlign(); // reset alignment to minimum
         #ifdef __CFA_DEBUG__
+        else
+                checkAlign( nalign );                                                   // check alignment
+        else checkAlign( nalign );                                                      // check alignment
         #endif // __CFA_DEBUG__
-        // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
-  if ( unlikely( size == 0 ) ) { free( oaddr ); return 0p; } // special cases
   if ( unlikely( oaddr == 0p ) ) {
                 #ifdef __STATISTICS__
+                __atomic_add_fetch( &resize_calls, 1, __ATOMIC_SEQ_CST );
                 __atomic_add_fetch( &resize_storage, size, __ATOMIC_SEQ_CST );
                 #endif // __STATISTICS__
 …
 void * realloc( void * oaddr, size_t nalign, size_t size ) {
+        // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
+  if ( unlikely( size == 0 ) ) {                                                // special cases
+                #ifdef __STATISTICS__
+                __atomic_add_fetch( &realloc_zero_calls, 1, __ATOMIC_SEQ_CST );
+                #endif // __STATISTICS__
+                free( oaddr );
+                return 0p;
+        } // if
         if ( unlikely( nalign < libAlign() ) ) nalign = libAlign(); // reset alignment to minimum
         #ifdef __CFA_DEBUG__
+        else
+                checkAlign( nalign );                                                   // check alignment
+        else checkAlign( nalign );                                                      // check alignment
         #endif // __CFA_DEBUG__
-        // If size is equal to 0, either NULL or a pointer suitable to be passed to free() is returned.
-  if ( unlikely( size == 0 ) ) { free( oaddr ); return 0p; } // special cases
   if ( unlikely( oaddr == 0p ) ) {
                 #ifdef __STATISTICS__

libcfa/src/startup.cfa

-                      r4468a70
+                      r342af53
 // Created On       : Tue Jul 24 16:21:57 2018
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Tue Feb  4 13:03:18 2020
 // Update Count     : 30
+// Last Modified On : Sat Jan  9 23:18:23 2021
+// Update Count     : 34
 //
+#include <time.h>                // tzset
+#include <locale.h>        // setlocale
+#include <time.h>                                                                               // tzset
+#include <locale.h>                                                                             // setlocale
+#include <stdlib.h>                                                                             // getenv
 #include "startup.hfa"
 …
     void __cfaabi_appready_startup( void ) {
                 tzset();                                                                                // initialize time global variables
                 setlocale(LC_NUMERIC, "");
+                setlocale( LC_NUMERIC, getenv("LANG") );
                 #ifdef __CFA_DEBUG__
                 extern void heapAppStart();

src/AST/Decl.cpp

-                      r4468a70
+                      r342af53
 // Created On       : Thu May 9 10:00:00 2019
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Fri Dec 13 16:23:15 2019
 // Update Count     : 20
+// Last Modified On : Tue Jan 12 16:54:55 2021
+// Update Count     : 23
 //
 …
 const char * TypeDecl::typeString() const {
         static const char * kindNames[] = { "sized data type", "sized object type", "sized function type", "sized tuple type" };
         static_assert( sizeof(kindNames)/sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "typeString: kindNames is out of sync." );
+        static const char * kindNames[] = { "sized data type", "sized data type", "sized object type", "sized function type", "sized tuple type", "sized array length type" };
+        static_assert( sizeof(kindNames) / sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "typeString: kindNames is out of sync." );
         assertf( kind < TypeDecl::NUMBER_OF_KINDS, "TypeDecl kind is out of bounds." );
         return sized ? kindNames[ kind ] : &kindNames[ kind ][ sizeof("sized") ]; // sizeof includes '\0'
 …
 const char * TypeDecl::genTypeString() const {
         static const char * kindNames[] = { "dtype", "otype", "ftype", "ttype" };
         static_assert( sizeof(kindNames)/sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "genTypeString: kindNames is out of sync." );
+        static const char * kindNames[] = { "T &", "T *", "T", "(*)", "T ...", "[T]" };
+        static_assert( sizeof(kindNames) / sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "genTypeString: kindNames is out of sync." );
         assertf( kind < TypeDecl::NUMBER_OF_KINDS, "TypeDecl kind is out of bounds." );
         return kindNames[ kind ];

src/AST/Decl.hpp

-                      r4468a70
+                      r342af53
 // Created On       : Thu May 9 10:00:00 2019
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Fri Dec 13 17:38:33 2019
 // Update Count     : 29
+// Last Modified On : Mon Jan 11 20:48:38 2021
+// Update Count     : 30
 //
 …
 class TypeDecl final : public NamedTypeDecl {
   public:
         enum Kind { Dtype, Otype, Ftype, Ttype, NUMBER_OF_KINDS };
+        enum Kind { Dtype, DStype, Otype, Ftype, Ttype, ALtype, NUMBER_OF_KINDS };
         Kind kind;

src/Parser/DeclarationNode.cc

-                      r4468a70
+                      r342af53
 // Created On       : Sat May 16 12:34:05 2015
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Thu Oct  8 08:03:38 2020
 // Update Count     : 1135
+// Last Modified On : Mon Jan 11 20:58:07 2021
+// Update Count     : 1137
 //
 …
         if ( variable.tyClass != TypeDecl::NUMBER_OF_KINDS ) {
                 // otype is internally converted to dtype + otype parameters
                 static const TypeDecl::Kind kindMap[] = { TypeDecl::Dtype, TypeDecl::Dtype, TypeDecl::Ftype, TypeDecl::Ttype };
                 static_assert( sizeof(kindMap)/sizeof(kindMap[0]) == TypeDecl::NUMBER_OF_KINDS, "DeclarationNode::build: kindMap is out of sync." );
+                static const TypeDecl::Kind kindMap[] = { TypeDecl::Dtype, TypeDecl::DStype, TypeDecl::Dtype, TypeDecl::Ftype, TypeDecl::Ttype, TypeDecl::ALtype };
+                static_assert( sizeof(kindMap) / sizeof(kindMap[0]) == TypeDecl::NUMBER_OF_KINDS, "DeclarationNode::build: kindMap is out of sync." );
                 assertf( variable.tyClass < sizeof(kindMap)/sizeof(kindMap[0]), "Variable's tyClass is out of bounds." );
                 TypeDecl * ret = new TypeDecl( *name, Type::StorageClasses(), nullptr, kindMap[ variable.tyClass ], variable.tyClass == TypeDecl::Otype, variable.initializer ? variable.initializer->buildType() : nullptr );

src/Parser/ParseNode.h

-                      r4468a70
+                      r342af53
 // Created On       : Sat May 16 13:28:16 2015
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Sat Oct 24 03:53:54 2020
 // Update Count     : 895
+// Last Modified On : Sun Jan  3 18:23:01 2021
+// Update Count     : 896
 //
 …
 struct DeclarationNode;
 class DeclarationWithType;
+class Initializer;
 class ExpressionNode;
-class Initializer;
 struct StatementNode;

src/Parser/parser.yy

-                      r4468a70
+                      r342af53
 // Created On       : Sat Sep  1 20:22:55 2001
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Sat Oct 24 08:21:14 2020
 // Update Count     : 4624
+// Last Modified On : Mon Jan 11 21:32:10 2021
+// Update Count     : 4633
 //
 …
 %type<en> conditional_expression                constant_expression                     assignment_expression           assignment_expression_opt
 %type<en> comma_expression                              comma_expression_opt
 %type<en> argument_expression_list_opt  argument_expression                     default_initialize_opt
+%type<en> argument_expression_list_opt  argument_expression                     default_initializer_opt
 %type<ifctl> if_control_expression
 %type<fctl> for_control_expression              for_control_expression_list
 …
 %type<decl> sue_declaration_specifier sue_declaration_specifier_nobody sue_type_specifier sue_type_specifier_nobody
 %type<tclass> type_class
+%type<tclass> type_class new_type_class
 %type<decl> type_declarator type_declarator_name type_declaring_list
 …
         | cfa_function_declaration
         | type_declaring_list
+                { SemanticError( yylloc, "otype declaration is currently unimplemented." ); $$ = nullptr; }
         | trait_specifier
+        ;
 …
+        ;
 cfa_parameter_ellipsis_list_opt:                                                        // CFA, abstract + real
+cfa_parameter_ellipsis_list_opt:                                                // CFA, abstract + real
         // empty
                 { $$ = DeclarationNode::newBasicType( DeclarationNode::Void ); }
 …
 cfa_parameter_declaration:                                                              // CFA, new & old style parameter declaration
         parameter_declaration
         | cfa_identifier_parameter_declarator_no_tuple identifier_or_type_name default_initialize_opt
+        | cfa_identifier_parameter_declarator_no_tuple identifier_or_type_name default_initializer_opt
                 { $$ = $1->addName( $2 ); }
         | cfa_abstract_tuple identifier_or_type_name default_initialize_opt
+        | cfa_abstract_tuple identifier_or_type_name default_initializer_opt
                 // To obtain LR(1), these rules must be duplicated here (see cfa_abstract_declarator).
                 { $$ = $1->addName( $2 ); }
         | type_qualifier_list cfa_abstract_tuple identifier_or_type_name default_initialize_opt
+        | type_qualifier_list cfa_abstract_tuple identifier_or_type_name default_initializer_opt
                 { $$ = $2->addName( $3 )->addQualifiers( $1 ); }
         | cfa_function_specifier
 …
 parameter_declaration:
                 // No SUE declaration in parameter list.
         declaration_specifier_nobody identifier_parameter_declarator default_initialize_opt
+        declaration_specifier_nobody identifier_parameter_declarator default_initializer_opt
                 { $$ = $2->addType( $1 )->addInitializer( $3 ? new InitializerNode( $3 ) : nullptr ); }
         | declaration_specifier_nobody type_parameter_redeclarator default_initialize_opt
+        | declaration_specifier_nobody type_parameter_redeclarator default_initializer_opt
                 { $$ = $2->addType( $1 )->addInitializer( $3 ? new InitializerNode( $3 ) : nullptr ); }
+        ;
 abstract_parameter_declaration:
         declaration_specifier_nobody default_initialize_opt
+        declaration_specifier_nobody default_initializer_opt
                 { $$ = $1->addInitializer( $2 ? new InitializerNode( $2 ) : nullptr ); }
         | declaration_specifier_nobody abstract_parameter_declarator default_initialize_opt
+        | declaration_specifier_nobody abstract_parameter_declarator default_initializer_opt
                 { $$ = $2->addType( $1 )->addInitializer( $3 ? new InitializerNode( $3 ) : nullptr ); }
+        ;
 …
         type_class identifier_or_type_name
                 { typedefTable.addToScope( *$2, TYPEDEFname, "9" ); }
         type_initializer_opt assertion_list_opt
+          type_initializer_opt assertion_list_opt
                 { $$ = DeclarationNode::newTypeParam( $1, $2 )->addTypeInitializer( $4 )->addAssertions( $5 ); }
+        | type_specifier identifier_parameter_declarator
+        | identifier_or_type_name new_type_class
+                { typedefTable.addToScope( *$1, TYPEDEFname, "9" ); }
+          type_initializer_opt assertion_list_opt
+                { $$ = DeclarationNode::newTypeParam( $2, $1 )->addTypeInitializer( $4 )->addAssertions( $5 ); }
+        | '[' identifier_or_type_name ']'
+                {
+                        typedefTable.addToScope( *$2, TYPEDEFname, "9" );
+                        $$ = DeclarationNode::newTypeParam( TypeDecl::ALtype, $2 );
+                }
+        // | type_specifier identifier_parameter_declarator
         | assertion_list
                 { $$ = DeclarationNode::newTypeParam( TypeDecl::Dtype, new string( DeclarationNode::anonymous.newName() ) )->addAssertions( $1 ); }
+        ;
+new_type_class:                                                                                 // CFA
+        // empty
+                { $$ = TypeDecl::Otype; }
+        | '&'
+                { $$ = TypeDecl::Dtype; }
+        | '*'
+                { $$ = TypeDecl::DStype; }                                              // dtype + sized
+        | ELLIPSIS
+                { $$ = TypeDecl::Ttype; }
+        ;
 …
+        ;
 default_initialize_opt:
+default_initializer_opt:
         // empty
                 { $$ = nullptr; }

src/ResolvExpr/ResolveAssertions.cc

r4468a70	r342af53
397	397
398	398	/// Limit to depth of recursion of assertion satisfaction
399		static const int recursionLimit = 4;
	399	static const int recursionLimit = 7;
400	400	/// Maximum number of simultaneously-deferred assertions to attempt concurrent satisfaction of
401	401	static const int deferLimit = 10;

src/ResolvExpr/SatisfyAssertions.cpp

-                      r4468a70
+                      r342af53
                 ast::UniqueId resnSlot;          ///< Slot for any recursive assertion IDs
                 AssnCandidate(
                         const ast::SymbolTable::IdData c, const ast::Type * at, ast::TypeEnvironment && e,
+                AssnCandidate(
+                        const ast::SymbolTable::IdData c, const ast::Type * at, ast::TypeEnvironment && e,
                         ast::AssertionSet && h, ast::AssertionSet && n, ast::OpenVarSet && o, ast::UniqueId rs )
                 : cdata( c ), adjType( at ), env( std::move( e ) ), have( std::move( h ) ),
+                : cdata( c ), adjType( at ), env( std::move( e ) ), have( std::move( h ) ),
                   need( std::move( n ) ), open( std::move( o ) ), resnSlot( rs ) {}
         };
 …
                 const AssnCandidate & match;
         };
         /// Wrapper for the deferred items from a single assertion satisfaction.
+        /// Wrapper for the deferred items from a single assertion satisfaction.
         /// Acts like an indexed list of DeferRef
         struct DeferItem {
 …
                 AssnCandidateList matches;
                 DeferItem(
+                DeferItem(
                         const ast::VariableExpr * d, const ast::AssertionSetValue & i, AssnCandidateList && ms )
                 : expr( d ), info( i ), matches( std::move( ms ) ) {}
 …
                 /// Initial satisfaction state for a candidate
                 SatState( CandidateRef & c, const ast::SymbolTable & syms )
                 : cand( c ), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero },
+                : cand( c ), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero },
                   symtab( syms ) { need.swap( c->need ); }
                 /// Update satisfaction state for next step after previous state
                 SatState( SatState && o, IterateFlag )
                 : cand( std::move( o.cand ) ), need( o.newNeed.begin(), o.newNeed.end() ), newNeed(),
                   deferred(), inferred( std::move( o.inferred ) ), costs( std::move( o.costs ) ),
+                : cand( std::move( o.cand ) ), need( o.newNeed.begin(), o.newNeed.end() ), newNeed(),
+                  deferred(), inferred( std::move( o.inferred ) ), costs( std::move( o.costs ) ),
                   symtab( o.symtab ) { costs.emplace_back( Cost::zero ); }
                 /// Field-wise next step constructor
                 SatState(
                         CandidateRef && c, ast::AssertionSet && nn, InferCache && i, CostVec && cs,
+                        CandidateRef && c, ast::AssertionSet && nn, InferCache && i, CostVec && cs,
                         ast::SymbolTable && syms )
                 : cand( std::move( c ) ), need( nn.begin(), nn.end() ), newNeed(), deferred(),
+                : cand( std::move( c ) ), need( nn.begin(), nn.end() ), newNeed(), deferred(),
                   inferred( std::move( i ) ), costs( std::move( cs ) ), symtab( std::move( syms ) )
                   { costs.emplace_back( Cost::zero ); }
 …
         /// Binds a single assertion, updating satisfaction state
         void bindAssertion(
                 const ast::VariableExpr * expr, const ast::AssertionSetValue & info, CandidateRef & cand,
+        void bindAssertion(
+                const ast::VariableExpr * expr, const ast::AssertionSetValue & info, CandidateRef & cand,
                 AssnCandidate & match, InferCache & inferred
         ) {
                 const ast::DeclWithType * candidate = match.cdata.id;
                 assertf( candidate->uniqueId,
+                assertf( candidate->uniqueId,
                         "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
                 ast::Expr * varExpr = match.cdata.combine( cand->expr->location, cand->cvtCost );
                 varExpr->result = match.adjType;
 …
                         ast::OpenVarSet newOpen{ sat.cand->open };
                         ast::ptr< ast::Type > toType = assn.first->result;
                         ast::ptr< ast::Type > adjType =
+                        ast::ptr< ast::Type > adjType =
                                 renameTyVars( adjustExprType( candidate->get_type(), newEnv, sat.symtab ), GEN_USAGE, false );
 …
+                                }
                                 matches.emplace_back(
+                                matches.emplace_back(
                                         cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ),
                                         std::move( newOpen ), crntResnSlot );
 …
         };
         /// Replace ResnSlots with InferParams and add alternative to output list, if it meets pruning
+        /// Replace ResnSlots with InferParams and add alternative to output list, if it meets pruning
         /// threshold.
         void finalizeAssertions(
                 CandidateRef & cand, InferCache & inferred, PruneMap & thresholds, CostVec && costs,
                 CandidateList & out
+        void finalizeAssertions(
+                CandidateRef & cand, InferCache & inferred, PruneMap & thresholds, CostVec && costs,
+                CandidateList & out
         ) {
                 // prune if cheaper alternative for same key has already been generated
 …
+        }
         /// Combo iterator that combines candidates into an output list, merging their environments.
         /// Rejects an appended candidate if environments cannot be merged. See `Common/FilterCombos.h`
+        /// Combo iterator that combines candidates into an output list, merging their environments.
+        /// Rejects an appended candidate if environments cannot be merged. See `Common/FilterCombos.h`
         /// for description of "combo iterator".
         class CandidateEnvMerger {
 …
 } // anonymous namespace
 void satisfyAssertions(
         CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,
+void satisfyAssertions(
+        CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,
         std::vector<std::string> & errors
 ) {
 …
                         // should a limit be imposed? worst case here is O(n^2) but very unlikely to happen.
                         for (unsigned resetCount = 0; ; ++resetCount) {
+                        for (unsigned resetCount = 0; ; ++resetCount) {
                                 ast::AssertionList next;
                                 resetTyVarRenaming();
 …
                                 // either add successful match or push back next state
                                 if ( sat.newNeed.empty() ) {
                                         finalizeAssertions(
+                                        finalizeAssertions(
                                                 sat.cand, sat.inferred, thresholds, std::move( sat.costs ), out );
                                 } else {
 …
                                 std::vector< CandidateEnvMerger::OutType > compatible = filterCombos(
                                         sat.deferred, CandidateEnvMerger{ sat.cand->env, sat.cand->open, sat.symtab } );
                                 // fail early if no mutually-compatible assertion satisfaction
                                 if ( compatible.empty() ) {
 …
                                         // set up next satisfaction state
                                         CandidateRef nextCand = std::make_shared<Candidate>(
                                                 sat.cand->expr, std::move( compat.env ), std::move( compat.open ),
+                                                sat.cand->expr, std::move( compat.env ), std::move( compat.open ),
                                                 ast::AssertionSet{} /* need moved into satisfaction state */,
                                                 sat.cand->cost, sat.cand->cvtCost );
 …
                                         ast::AssertionSet nextNewNeed{ sat.newNeed };
                                         InferCache nextInferred{ sat.inferred };
                                         CostVec nextCosts{ sat.costs };
                                         nextCosts.back() += compat.cost;
                                         ast::SymbolTable nextSymtab{ sat.symtab };
 …
                                         // either add successful match or push back next state
                                         if ( nextNewNeed.empty() ) {
                                                 finalizeAssertions(
+                                                finalizeAssertions(
                                                         nextCand, nextInferred, thresholds, std::move( nextCosts ), out );
                                         } else {
                                                 nextSats.emplace_back(
                                                         std::move( nextCand ), std::move( nextNewNeed ),
                                                         std::move( nextInferred ), std::move( nextCosts ),
+                                                nextSats.emplace_back(
+                                                        std::move( nextCand ), std::move( nextNewNeed ),
+                                                        std::move( nextInferred ), std::move( nextCosts ),
                                                         std::move( nextSymtab ) );
+                                        }
 …
                 nextSats.clear();
+        }
         // exceeded recursion limit if reaches here
         if ( out.empty() ) {

src/SymTab/Demangle.cc

-                      r4468a70
+                      r342af53
 // Created On       : Thu Jul 19 12:52:41 2018
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Tue Feb 11 15:09:18 2020
 // Update Count     : 10
+// Last Modified On : Mon Jan 11 21:28:27 2021
+// Update Count     : 11
 //
 …
                                 // type variable types
                                 for (size_t k = 0; k < TypeDecl::NUMBER_OF_KINDS; ++k) {
                                         static const std::string typeVariableNames[] = { "DT", "OT", "FT", "TT", };
+                                        static const std::string typeVariableNames[] = { "DT", "DST", "OT", "FT", "TT", "ALT", };
                                         static_assert(
                                                 sizeof(typeVariableNames)/sizeof(typeVariableNames[0]) == TypeDecl::NUMBER_OF_KINDS,

src/SymTab/Mangler.cc

-                      r4468a70
+                      r342af53
 // Created On       : Sun May 17 21:40:29 2015
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Wed Nov 18 12:01:38 2020
 // Update Count     : 64
+// Last Modified On : Mon Jan 11 21:56:06 2021
+// Update Count     : 74
 //
 #include "Mangler.h"
 …
                                 // and the case has not yet come up in practice. Alternatively, if not then this code can be removed
                                 // aside from the assert false.
                                 assertf(false, "Mangler_old should not visit typedecl: %s", toCString(decl));
+                                assertf( false, "Mangler_old should not visit typedecl: %s", toCString(decl));
                                 assertf( decl->kind < TypeDecl::NUMBER_OF_KINDS, "Unhandled type variable kind: %d", decl->kind );
                                 mangleName += Encoding::typeVariables[ decl->kind ] + std::to_string( decl->name.length() ) + decl->name;
 …
                                                         break;
                                                   default:
                                                         assert( false );
+                                                        assertf( false, "unimplemented kind for type variable %s", SymTab::Mangler::Encoding::typeVariables[i->kind].c_str() );
                                                 } // switch
                                                 varNums[ i->name ] = std::make_pair( nextVarNum, (int)i->kind );
 …
                                         for ( auto & decl : ptype->forall ) {
                                                 switch ( decl->kind ) {
                                                 case ast::TypeDecl::Kind::Dtype:
+                                                  case ast::TypeDecl::Kind::Dtype:
                                                         dcount++;
                                                         break;
                                                 case ast::TypeDecl::Kind::Ftype:
+                                                  case ast::TypeDecl::Kind::Ftype:
                                                         fcount++;
                                                         break;
                                                 case ast::TypeDecl::Kind::Ttype:
+                                                  case ast::TypeDecl::Kind::Ttype:
                                                         vcount++;
                                                         break;
                                                 default:
                                                         assert( false );
+                                                  default:
+                                                        assertf( false, "unimplemented kind for type variable %s", SymTab::Mangler::Encoding::typeVariables[decl->kind].c_str() );
                                                 } // switch
                                                 varNums[ decl->name ] = std::make_pair( nextVarNum, (int)decl->kind );

src/SymTab/ManglerCommon.cc

-                      r4468a70
+                      r342af53
 // Created On       : Sun May 17 21:44:03 2015
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Fri Dec 13 14:54:38 2019
 // Update Count     : 28
+// Last Modified On : Mon Jan 11 21:23:10 2021
+// Update Count     : 29
 //
 …
                         const std::string typeVariables[] = {
                                 "BD", // dtype
+                                "BDS", // dtype + sized
                                 "BO", // otype
                                 "BF", // ftype
                                 "BT", // ttype
+                                "BAL", // array length type
                         };
                         static_assert(
                                 sizeof(typeVariables)/sizeof(typeVariables[0]) == TypeDecl::NUMBER_OF_KINDS,
+                                sizeof(typeVariables) / sizeof(typeVariables[0]) == TypeDecl::NUMBER_OF_KINDS,
                                 "Each type variable kind should have a corresponding mangler prefix"
                         );

src/SynTree/Declaration.h

-                      r4468a70
+                      r342af53
 // Created On       : Mon May 18 07:44:20 2015
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Fri Dec 13 23:11:22 2019
 // Update Count     : 157
+// Last Modified On : Mon Jan 11 20:48:39 2021
+// Update Count     : 158
 //
 …
         typedef NamedTypeDecl Parent;
   public:
         enum Kind { Dtype, Otype, Ftype, Ttype, NUMBER_OF_KINDS };
+        enum Kind { Dtype, DStype, Otype, Ftype, Ttype, ALtype, NUMBER_OF_KINDS };
         Kind kind;

src/SynTree/TypeDecl.cc

-                      r4468a70
+                      r342af53
 // Created On       : Mon May 18 07:44:20 2015
 // Last Modified By : Peter A. Buhr
 // Last Modified On : Thu Oct  8 18:18:55 2020
 // Update Count     : 22
+// Last Modified On : Tue Jan 12 16:07:33 2021
+// Update Count     : 26
 //
 …
 const char * TypeDecl::typeString() const {
         static const char * kindNames[] = { "sized data type", "sized object type", "sized function type", "sized tuple type" };
         static_assert( sizeof(kindNames)/sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "typeString: kindNames is out of sync." );
+        static const char * kindNames[] = { "sized data type", "sized data type", "sized object type", "sized function type", "sized tuple type", "sized array length type" };
+        static_assert( sizeof(kindNames) / sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "typeString: kindNames is out of sync." );
         assertf( kind < TypeDecl::NUMBER_OF_KINDS, "TypeDecl kind is out of bounds." );
         return isComplete() ? kindNames[ kind ] : &kindNames[ kind ][ sizeof("sized") ]; // sizeof includes '\0'
 …
 const char * TypeDecl::genTypeString() const {
         static const char * kindNames[] = { "dtype", "otype", "ftype", "ttype" };
         static_assert( sizeof(kindNames)/sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "genTypeString: kindNames is out of sync." );
+        static const char * kindNames[] = { "T &", "T *", "T", "(*)", "T ...", "[T]" };
+        static_assert( sizeof(kindNames) / sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "genTypeString: kindNames is out of sync." );
         assertf( kind < TypeDecl::NUMBER_OF_KINDS, "TypeDecl kind is out of bounds." );
         return kindNames[ kind ];

tests/Makefile.am

-                      r4468a70
+                      r342af53
 mostlyclean-local :
+        find ${builddir} -not -path './__pycache__/*' -path '*.o' -delete
+        find ${builddir} -not -path './__pycache__/*' -path '*/.err/*.log' -delete
+        find ${builddir} -not -path './__pycache__/*' -path '*/.out/*.log' -delete
         rm -f ${EXTRA_PROGRAMS}
         rm -rf __pycache__
-        find ${builddir} -path '*.o' -delete
-        find ${builddir} -path '*/.err/*.log' -delete
-        find ${builddir} -path '*/.out/*.log' -delete
 distclean-local :

tests/concurrent/futures/.expect/basic.txt

r4468a70	r342af53
	1	start
1	2	done

tests/concurrent/futures/basic.cfa

-                      r4468a70
+                      r342af53
 #include <thread.hfa>
 enum {NFUTURES = 10};
 …
 int main() {
+        printf( "start\n" );                            // non-empty .expect file
         processor procs[2];
+        {

Context Navigation

Changes in / [4468a70:342af53]

Legend:

Download in other formats: