Changes in / [f95634e:b7fd9daf]


Ignore:
Files:
86 added
15 deleted
155 edited

Legend:

Unmodified
Added
Removed
  • benchmark/Cargo.toml.in

    rf95634e rb7fd9daf  
    66
    77[[bin]]
    8 name = "cycle-tokio"
     8name = "rdq-cycle-tokio"
    99path = "@abs_srcdir@/readyQ/cycle.rs"
    1010
    1111[[bin]]
    12 name = "locality-tokio"
     12name = "rdq-locality-tokio"
    1313path = "@abs_srcdir@/readyQ/locality.rs"
     14
     15[[bin]]
     16name = "rdq-transfer-tokio"
     17path = "@abs_srcdir@/readyQ/transfer.rs"
     18
     19[[bin]]
     20name = "rdq-yield-tokio"
     21path = "@abs_srcdir@/readyQ/yield.rs"
    1422
    1523[features]
  • benchmark/Makefile.am

    rf95634e rb7fd9daf  
    2121include $(top_srcdir)/tools/build/cfa.make
    2222
    23 AM_CFLAGS = -O2 -Wall -Wextra -I$(srcdir) -lrt -pthread # -Werror
     23AM_CFLAGS = -O3 -Wall -Wextra -I$(srcdir) -lrt -pthread # -Werror
    2424AM_CFAFLAGS = -quiet -nodebug
    2525AM_UPPFLAGS = -quiet -nodebug -multi -std=c++14
     
    197197        $(srcdir)/fixcsv.sh $@
    198198
     199# use --no-print-directory to generate csv appropriately
     200mutexStmt.csv:
     201        echo "building $@"
     202        echo "1-lock,2-lock,4-lock,8-lock,1-no-stmt-lock,2-no-stmt-lock,4-no-stmt-lock,8-no-stmt-lock,1-monitor,2-monitor,4-monitor" > $@
     203        +make mutexStmt-lock1.runquiet >> $@ && echo -n ',' >> $@
     204        +make mutexStmt-lock2.runquiet >> $@ && echo -n ',' >> $@
     205        +make mutexStmt-lock4.runquiet >> $@ && echo -n ',' >> $@
     206        +make mutexStmt-lock8.runquiet >> $@ && echo -n ',' >> $@
     207        +make mutexStmt-no-stmt-lock1.runquiet >> $@ && echo -n ',' >> $@
     208        +make mutexStmt-no-stmt-lock2.runquiet >> $@ && echo -n ',' >> $@
     209        +make mutexStmt-no-stmt-lock4.runquiet >> $@ && echo -n ',' >> $@
     210        +make mutexStmt-no-stmt-lock8.runquiet >> $@ && echo -n ',' >> $@
     211        +make mutexStmt-monitor1.runquiet >> $@ && echo -n ',' >> $@
     212        +make mutexStmt-monitor2.runquiet >> $@ && echo -n ',' >> $@
     213        +make mutexStmt-monitor4.runquiet >> $@
     214        $(srcdir)/fixcsv.sh $@
     215
    199216schedint.csv:
    200217        echo "building $@"
     
    357374## =========================================================================================================
    358375
     376mutexStmt$(EXEEXT) :                \
     377        mutexStmt-cpp1.run                      \
     378        mutexStmt-cpp2.run                      \
     379        mutexStmt-cpp4.run                      \
     380        mutexStmt-cpp8.run                      \
     381        mutexStmt-java.run                      \
     382        mutexStmt-lock1.run                 \
     383        mutexStmt-lock2.run                 \
     384        mutexStmt-lock4.run                 \
     385        mutexStmt-lock8.run                 \
     386        mutexStmt-no-stmt-lock1.run \
     387        mutexStmt-no-stmt-lock2.run \
     388        mutexStmt-no-stmt-lock4.run \
     389        mutexStmt-no-stmt-lock8.run \
     390        mutexStmt-monitor1.run      \
     391        mutexStmt-monitor2.run      \
     392        mutexStmt-monitor4.run
     393
     394mutexStmt-lock1$(EXEEXT):
     395        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/lock1.cfa
     396
     397mutexStmt-lock2$(EXEEXT):
     398        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/lock2.cfa
     399
     400mutexStmt-lock4$(EXEEXT):
     401        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/lock4.cfa
     402
     403mutexStmt-lock8$(EXEEXT):
     404        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/lock8.cfa
     405
     406mutexStmt-cpp1$(EXEEXT):
     407        $(BENCH_V_CXX)$(CXXCOMPILE) -std=c++17 $(srcdir)/mutexStmt/cpp1.cc
     408
     409mutexStmt-cpp2$(EXEEXT):
     410        $(BENCH_V_CXX)$(CXXCOMPILE) -std=c++17 $(srcdir)/mutexStmt/cpp2.cc
     411
     412mutexStmt-cpp4$(EXEEXT):
     413        $(BENCH_V_CXX)$(CXXCOMPILE) -std=c++17 $(srcdir)/mutexStmt/cpp4.cc
     414
     415mutexStmt-cpp8$(EXEEXT):
     416        $(BENCH_V_CXX)$(CXXCOMPILE) -std=c++17 $(srcdir)/mutexStmt/cpp8.cc
     417
     418mutexStmt-monitor1$(EXEEXT):
     419        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/monitor1.cfa
     420
     421mutexStmt-monitor2$(EXEEXT):
     422        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/monitor2.cfa
     423
     424mutexStmt-monitor4$(EXEEXT):
     425        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/monitor4.cfa
     426
     427mutexStmt-no-stmt-lock1$(EXEEXT):
     428        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/no_stmt_lock1.cfa
     429
     430mutexStmt-no-stmt-lock2$(EXEEXT):
     431        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/no_stmt_lock2.cfa
     432
     433mutexStmt-no-stmt-lock4$(EXEEXT):
     434        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/no_stmt_lock4.cfa
     435
     436mutexStmt-no-stmt-lock8$(EXEEXT):
     437        $(BENCH_V_CFA)$(CFACOMPILE) $(srcdir)/mutexStmt/no_stmt_lock8.cfa
     438
     439mutexStmt-java$(EXEEXT):
     440        $(BENCH_V_JAVAC)javac -d $(builddir) $(srcdir)/mutexStmt/JavaThread.java
     441        echo "#!/bin/sh" > a.out
     442        echo "java JavaThread \"$$""@\"" >> a.out
     443        chmod a+x a.out
     444
     445## =========================================================================================================
     446
    359447schedint$(EXEEXT) :             \
    360448        schedint-cfa1.run       \
     
    524612## =========================================================================================================
    525613
    526 %-tokio$(EXEEXT): $(srcdir)/readyQ/%.rs $(srcdir)/bench.rs
    527         cd $(builddir) && cargo build --release
    528         cp $(builddir)/target/release/$(basename $@) $@
     614RDQBENCHES = \
     615        rdq-cycle-cfa \
     616        rdq-cycle-tokio \
     617        rdq-cycle-go \
     618        rdq-cycle-fibre \
     619        rdq-yield-cfa \
     620        rdq-yield-tokio \
     621        rdq-yield-go \
     622        rdq-yield-fibre \
     623        rdq-locality-cfa \
     624        rdq-locality-tokio \
     625        rdq-locality-go \
     626        rdq-locality-fibre \
     627        rdq-transfer-cfa \
     628        rdq-transfer-tokio \
     629        rdq-transfer-go \
     630        rdq-transfer-fibre
     631
     632rdq-benches:
     633        +make $(RDQBENCHES)
     634
     635clean-rdq-benches:
     636        rm -rf $(RDQBENCHES) $(builddir)/target go.mod
     637
     638rdq-%-tokio$(EXEEXT): $(builddir)/target/release/rdq-%-tokio$(EXEEXT)
     639        $(BENCH_V_RUSTC)cp $(builddir)/target/release/$(basename $@) $@
     640
     641$(builddir)/target/release/rdq-%-tokio$(EXEEXT): $(srcdir)/readyQ/%.rs $(srcdir)/bench.rs
     642        $(BENCH_V_RUSTC)cd $(builddir) && cargo build --release
     643
     644rdq-%-cfa$(EXEEXT): $(srcdir)/readyQ/%.cfa $(srcdir)/readyQ/rq_bench.hfa
     645        $(BENCH_V_CFA)$(CFACOMPILE) $< -o $@
     646
     647go.mod:
     648        touch $@
     649        go mod edit -module=rdq.bench
     650        go get golang.org/x/sync/semaphore
     651        go get golang.org/x/text/language
     652        go get golang.org/x/text/message
     653
     654rdq-%-go$(EXEEXT): $(srcdir)/readyQ/%.go $(srcdir)/readyQ/bench.go go.mod
     655        $(BENCH_V_GOC)go build -o $@ $< $(srcdir)/readyQ/bench.go
     656
     657rdq-%-fibre$(EXEEXT): $(srcdir)/readyQ/%.cpp
     658        $(BENCH_V_CXX)$(CXXCOMPILE) $< -o $@ -lfibre -std=c++17 $(AM_CFLAGS)
     659
     660# ## =========================================================================================================
     661
     662CLEANFILES = $(RDQBENCHES) go.mod go.sum
     663
     664clean-local:
     665        -rm -rf target
  • benchmark/bench.h

    rf95634e rb7fd9daf  
    2121        return 1000000000LL * ts.tv_sec + ts.tv_nsec;
    2222} // bench_time
     23
     24
     25#if defined(__cforall)
     26struct test_spinlock {
     27        volatile bool lock;
     28};
     29
     30static inline void lock( test_spinlock & this ) {
     31        for ( ;; ) {
     32                if ( (this.lock == 0) && (__atomic_test_and_set( &this.lock, __ATOMIC_ACQUIRE ) == 0) ) break;
     33        }
     34}
     35
     36static inline void unlock( test_spinlock & this ) {
     37        __atomic_clear( &this.lock, __ATOMIC_RELEASE );
     38}
     39#endif
    2340
    2441#ifndef BENCH_N
  • benchmark/bench.rs

    rf95634e rb7fd9daf  
    11use std::io::{self, Write};
     2use std::option;
    23use std::sync::atomic::{AtomicU64, AtomicBool, Ordering};
    34use std::time::{Instant,Duration};
     5use std::u128;
    46
    57use clap::{Arg, ArgMatches};
     
    2729
    2830impl BenchData {
    29         pub fn new(options: ArgMatches, nthreads: usize) -> BenchData {
     31        pub fn new(options: ArgMatches, nthreads: usize, default_it: option::Option<u64>) -> BenchData {
    3032                let (clock_mode, stop_count, duration) = if options.is_present("iterations") {
    3133                        (false,
    3234                        options.value_of("iterations").unwrap().parse::<u64>().unwrap(),
     35                        -1.0)
     36                } else if !default_it.is_none() {
     37                        (false,
     38                        default_it.unwrap(),
    3339                        -1.0)
    3440                } else {
     
    4854        }
    4955
     56        #[allow(dead_code)]
    5057        pub async fn wait(&self, start: &Instant) -> Duration{
    5158                loop {
     
    6976}
    7077
     78// ==================================================
     79pub fn _lehmer64( state: &mut u128 ) -> u64 {
     80        *state = state.wrapping_mul(0xda942042e4dd58b5);
     81        return (*state >> 64) as u64;
     82}
  • benchmark/io/http/filecache.cfa

    rf95634e rb7fd9daf  
    185185        sout | "Filled cache from path \"" | path | "\" with" | fcount | "files";
    186186        if( conflicts > 0 ) {
    187                 sout | "Found" | conflicts | "conflicts (seed: " | options.file_cache.hash_seed | ")";
     187                sout | "Found" | conflicts | "conflicts (size: " | file_cache.size | ", seed: " | options.file_cache.hash_seed | ")";
    188188                #if defined(REJECT_CONFLICTS)
    189189                        abort("Conflicts found in the cache");
  • benchmark/io/http/http_ring.cpp

    rf95634e rb7fd9daf  
    118118// Get a fix reply based on the return code
    119119const char * http_msgs[] = {
    120         "HTTP/1.1 200 OK\r\nServer: HttoForall\r\nContent-Type: text/plain\r\nContent-Length: 15\r\nConnection: keep-alive\r\n\r\nHello, World!\r\n",
    121         "HTTP/1.1 400 Bad Request\r\nServer: HttoForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
    122         "HTTP/1.1 404 Not Found\r\nServer: HttoForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
    123         "HTTP/1.1 405 Method Not \r\nServer: HttoForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
    124         "HTTP/1.1 408 Request Timeout\r\nServer: HttoForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
    125         "HTTP/1.1 413 Payload Too Large\r\nServer: HttoForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
    126         "HTTP/1.1 414 URI Too Long\r\nServer: HttoForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
     120        "HTTP/1.1 200 OK\r\nServer: HttpForall\r\nContent-Type: text/plain\r\nContent-Length: 15\r\nConnection: keep-alive\r\n\r\nHello, World!\r\n",
     121        "HTTP/1.1 400 Bad Request\r\nServer: HttpForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
     122        "HTTP/1.1 404 Not Found\r\nServer: HttpForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
     123        "HTTP/1.1 405 Method Not \r\nServer: HttpForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
     124        "HTTP/1.1 408 Request Timeout\r\nServer: HttpForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
     125        "HTTP/1.1 413 Payload Too Large\r\nServer: HttpForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
     126        "HTTP/1.1 414 URI Too Long\r\nServer: HttpForall\r\nContent-Type: text/plain\r\nContent-Length: 0 \r\n\r\n",
    127127};
    128128static_assert( KNOWN_CODES == (sizeof(http_msgs) / sizeof(http_msgs[0])) );
  • benchmark/io/http/main.cfa

    rf95634e rb7fd9daf  
    190190                        init_protocol();
    191191                        {
    192                                 Worker workers[options.clopts.nworkers];
     192                                Worker * workers = anew(options.clopts.nworkers);
    193193                                for(i; options.clopts.nworkers) {
    194194                                        // if( options.file_cache.fixed_fds ) {
     
    212212                                }
    213213                                sout | nl;
     214                                if(!options.interactive) park();
    214215                                {
    215216                                        char buffer[128];
     
    249250
    250251                                sout | "Stopping connection threads..." | nonl; flush( sout );
     252                                adelete(workers);
    251253                        }
    252254                        sout | "done";
  • benchmark/io/http/options.cfa

    rf95634e rb7fd9daf  
    2121        false, // log
    2222        false, // stats
     23        true, // interactive
     24        0, // redirect
     25        0, // redirect
    2326
    2427        { // file_cache
     
    5255        // bool sqkpoll = false;
    5356        // bool iokpoll = false;
    54         unsigned nentries = 16;
     57        unsigned nentries = 0;
    5558        bool isolate = false;
    5659
     
    6265                {'\0', "isolate",        "Create one cluster per processor", isolate, parse_settrue},
    6366                {'\0', "log",            "Enable logs", options.log, parse_settrue},
     67                {'\0', "sout",           "Redirect standard out to file", options.reopen_stdout},
     68                {'\0', "serr",           "Redirect standard error to file", options.reopen_stderr},
    6469                {'\0', "stats",          "Enable statistics", options.stats, parse_settrue},
     70                {'\0', "shell",          "Disable interactive mode", options.interactive, parse_setfalse},
    6571                {'\0', "accept-backlog", "Maximum number of pending accepts", options.socket.backlog},
    6672                {'\0', "request_len",    "Maximum number of bytes in the http request, requests with more data will be answered with Http Code 414", options.socket.buflen},
     
    7985        parse_args( argc, argv, opt, opt_cnt, "[OPTIONS]... [PATH]\ncforall http server", left );
    8086
    81         if( !is_pow2(nentries) ) {
     87        if( nentries != 0 && !is_pow2(nentries) ) {
    8288                unsigned v = nentries;
    8389                v--;
     
    131137
    132138        options.file_cache.path = path;
     139
     140        if( options.reopen_stdout && options.reopen_stderr && 0 == strcmp(options.reopen_stdout, options.reopen_stderr) ) {
     141                serr | "Redirect sout and serr to the same file is not supported";
     142                exit(EXIT_FAILURE);
     143        }
     144
     145        if( options.reopen_stdout ) {
     146                sout | "redirecting sout to '" | options.reopen_stdout | "'";
     147                FILE  * ret = freopen( options.reopen_stdout, "w", stdout);
     148                if( ret == 0p ) {
     149                        serr | "Failed to redirect sout to '" | options.reopen_stdout | "'";
     150                        exit(EXIT_FAILURE);
     151                }
     152        }
     153
     154        if( options.reopen_stderr ) {
     155                sout | "redirecting serr to '" | options.reopen_stderr | "'";
     156                FILE  * ret = freopen( options.reopen_stderr, "w", stderr);
     157                if( ret == 0p ) {
     158                        serr | "Failed to redirect serr to '" | options.reopen_stderr | "'";
     159                        exit(EXIT_FAILURE);
     160                }
     161        }
    133162}
  • benchmark/io/http/options.hfa

    rf95634e rb7fd9daf  
    1010        bool log;
    1111        bool stats;
     12        bool interactive;
     13        const char * reopen_stdout;
     14        const char * reopen_stderr;
    1215
    1316        struct {
  • benchmark/io/http/protocol.cfa

    rf95634e rb7fd9daf  
    1111#include <fstream.hfa>
    1212#include <iofwd.hfa>
     13#include <io/types.hfa>
     14#include <mutex_stmt.hfa>
    1315
    1416#include <assert.h>
     
    2628#define PLAINTEXT_MEMCPY
    2729#define PLAINTEXT_NOCOPY
     30#define LINKED_IO
    2831
    2932struct https_msg_str {
     
    5356}
    5457
    55 static inline int answer( int fd, const char * it, int len) {
     58static inline int answer( int fd, const char * it, int len ) {
    5659        while(len > 0) {
    5760                // Call write
    5861                int ret = cfa_send(fd, it, len, 0, CFA_IO_LAZY);
    5962                if( ret < 0 ) {
    60                         if( errno == ECONNRESET || errno == EPIPE ) return -ECONNRESET;
     63                        if( errno == ECONNRESET || errno == EPIPE ) { close(fd); return -ECONNRESET; }
    6164                        if( errno == EAGAIN || errno == EWOULDBLOCK) return -EAGAIN;
    6265
     
    7780}
    7881
    79 int answer_header( int fd, size_t size ) {
    80         char buffer[512];
    81         char * it = buffer;
     82static int fill_header(char * it, size_t size) {
    8283        memcpy(it, http_msgs[OK200]->msg, http_msgs[OK200]->len);
    8384        it += http_msgs[OK200]->len;
    8485        int len = http_msgs[OK200]->len;
    8586        len += snprintf(it, 512 - len, "%d \n\n", size);
     87        return len;
     88}
     89
     90static int answer_header( int fd, size_t size ) {
     91        char buffer[512];
     92        int len = fill_header(buffer, size);
    8693        return answer( fd, buffer, len );
    8794}
     
    135142}
    136143
    137 
    138 [HttpCode code, bool closed, * const char file, size_t len] http_read(int fd, []char buffer, size_t len) {
    139         char * it = buffer;
    140         size_t count = len - 1;
    141         int rlen = 0;
    142         READ:
    143         for() {
    144                 int ret = cfa_recv(fd, (void*)it, count, 0, CFA_IO_LAZY);
    145                 // int ret = read(fd, (void*)it, count);
    146                 if(ret == 0 ) return [OK200, true, 0, 0];
    147                 if(ret < 0 ) {
    148                         if( errno == EAGAIN || errno == EWOULDBLOCK) continue READ;
    149                         if( errno == ECONNRESET ) return [E408, true, 0, 0];
    150                         if( errno == EPIPE ) return [E408, true, 0, 0];
    151                         abort( "read error: (%d) %s\n", (int)errno, strerror(errno) );
    152                 }
    153                 it[ret + 1] = '\0';
    154                 rlen += ret;
    155 
    156                 if( strstr( it, "\r\n\r\n" ) ) break;
    157 
    158                 it += ret;
    159                 count -= ret;
    160 
    161                 if( count < 1 ) return [E414, false, 0, 0];
    162         }
    163 
    164         if( options.log ) {
    165                 write(sout, buffer, rlen);
    166                 sout | nl;
    167         }
    168 
    169         it = buffer;
    170         int ret = memcmp(it, "GET /", 5);
    171         if( ret != 0 ) return [E400, false, 0, 0];
    172         it += 5;
    173 
    174         char * end = strstr( it, " " );
    175         return [OK200, false, it, end - it];
    176 }
    177 
    178 int sendfile( int pipe[2], int fd, int ans_fd, size_t count ) {
     144static int sendfile( int pipe[2], int fd, int ans_fd, size_t count ) {
    179145        unsigned sflags = SPLICE_F_MOVE; // | SPLICE_F_MORE;
    180146        off_t offset = 0;
     
    207173}
    208174
     175static void zero_sqe(struct io_uring_sqe * sqe) {
     176        sqe->flags = 0;
     177        sqe->ioprio = 0;
     178        sqe->fd = 0;
     179        sqe->off = 0;
     180        sqe->addr = 0;
     181        sqe->len = 0;
     182        sqe->fsync_flags = 0;
     183        sqe->__pad2[0] = 0;
     184        sqe->__pad2[1] = 0;
     185        sqe->__pad2[2] = 0;
     186        sqe->fd = 0;
     187        sqe->off = 0;
     188        sqe->addr = 0;
     189        sqe->len = 0;
     190}
     191
     192enum FSM_STATE {
     193        Initial,
     194        Retry,
     195        Error,
     196        Done,
     197};
     198
     199struct FSM_Result {
     200        FSM_STATE state;
     201        int error;
     202};
     203
     204static inline void ?{}(FSM_Result & this) { this.state = Initial; this.error = 0; }
     205static inline bool is_error(FSM_Result & this) { return Error == this.state; }
     206static inline bool is_done(FSM_Result & this) { return Done == this.state; }
     207
     208static inline int error(FSM_Result & this, int error) {
     209        this.error = error;
     210        this.state = Error;
     211        return error;
     212}
     213
     214static inline int done(FSM_Result & this) {
     215        this.state = Done;
     216        return 0;
     217}
     218
     219static inline int retry(FSM_Result & this) {
     220        this.state = Retry;
     221        return 0;
     222}
     223
     224static inline int need(FSM_Result & this) {
     225        switch(this.state) {
     226                case Initial:
     227                case Retry:
     228                        return 1;
     229                case Error:
     230                        if(this.error == 0) mutex(serr) serr | "State marked error but code is 0";
     231                case Done:
     232                        return 0;
     233        }
     234}
     235
     236// Generator that handles sending the header
     237generator header_g {
     238        io_future_t f;
     239        const char * next;
     240        int fd; size_t len;
     241        FSM_Result res;
     242};
     243
     244static inline void ?{}(header_g & this, int fd, const char * it, size_t len ) {
     245        this.next = it;
     246        this.fd = fd;
     247        this.len = len;
     248}
     249
     250static inline void fill(header_g & this, struct io_uring_sqe * sqe) {
     251        zero_sqe(sqe);
     252        sqe->opcode = IORING_OP_SEND;
     253        sqe->user_data = (uintptr_t)&this.f;
     254        sqe->flags = IOSQE_IO_LINK;
     255        sqe->fd = this.fd;
     256        sqe->addr = (uintptr_t)this.next;
     257        sqe->len = this.len;
     258}
     259
     260static inline int error(header_g & this, int error) {
     261        int ret = close(this.fd);
     262        if( ret != 0 ) {
     263                mutex(serr) serr | "Failed to close fd" | errno;
     264        }
     265        return error(this.res, error);
     266}
     267
     268static inline int wait_and_process(header_g & this) {
     269        wait(this.f);
     270
     271        // Did something crazy happen?
     272        if(this.f.result > this.len) {
     273                mutex(serr) serr | "HEADER sent too much!";
     274                return error(this, -ERANGE);
     275        }
     276
     277        // Something failed?
     278        if(this.f.result < 0) {
     279                int error = -this.f.result;
     280                if( error == ECONNRESET ) return error(this, -ECONNRESET);
     281                if( error == EPIPE ) return error(this, -EPIPE);
     282                if( error == ECANCELED ) {
     283                        mutex(serr) serr | "HEADER was cancelled, WTF!";
     284                        return error(this, -ECONNRESET);
     285                }
     286                if( error == EAGAIN || error == EWOULDBLOCK) {
     287                        mutex(serr) serr | "HEADER got eagain, WTF!";
     288                        return error(this, -ECONNRESET);
     289                }
     290        }
     291
     292        // Done?
     293        if(this.f.result == this.len) {
     294                return done(this.res);
     295        }
     296
     297        // It must be a Short read
     298        this.len  -= this.f.result;
     299        this.next += this.f.result;
     300        reset(this.f);
     301        return retry(this.res);
     302}
     303
     304// Generator that handles splicing in a file
     305struct splice_in_t {
     306        io_future_t f;
     307        int fd; int pipe; size_t len; off_t off;
     308        FSM_Result res;
     309};
     310
     311static inline void ?{}(splice_in_t & this, int fd, int pipe, size_t len) {
     312        this.fd = fd;
     313        this.pipe = pipe;
     314        this.len = len;
     315        this.off = 0;
     316}
     317
     318static inline void fill(splice_in_t & this, struct io_uring_sqe * sqe) {
     319        zero_sqe(sqe);
     320        sqe->opcode = IORING_OP_SPLICE;
     321        sqe->user_data = (uintptr_t)&this.f;
     322        sqe->flags = 0;
     323        sqe->splice_fd_in = this.fd;
     324        sqe->splice_off_in = this.off;
     325        sqe->fd = this.pipe;
     326        sqe->off = (__u64)-1;
     327        sqe->len = this.len;
     328        sqe->splice_flags = SPLICE_F_MOVE;
     329}
     330
     331static inline int wait_and_process(splice_in_t & this) {
     332        wait(this.f);
     333
     334        // Did something crazy happen?
     335        if(this.f.result > this.len) {
     336                mutex(serr) serr | "SPLICE IN spliced too much!";
     337                return error(this.res, -ERANGE);
     338        }
     339
     340        // Something failed?
     341        if(this.f.result < 0) {
     342                int error = -this.f.result;
     343                if( error == ECONNRESET ) return error(this.res, -ECONNRESET);
     344                if( error == EPIPE ) return error(this.res, -EPIPE);
     345                if( error == ECANCELED ) {
     346                        mutex(serr) serr | "SPLICE IN was cancelled, WTF!";
     347                        return error(this.res, -ECONNRESET);
     348                }
     349                if( error == EAGAIN || error == EWOULDBLOCK) {
     350                        mutex(serr) serr | "SPLICE IN got eagain, WTF!";
     351                        return error(this.res, -ECONNRESET);
     352                }
     353        }
     354
     355        // Done?
     356        if(this.f.result == this.len) {
     357                return done(this.res);
     358        }
     359
     360        // It must be a Short read
     361        this.len -= this.f.result;
     362        this.off += this.f.result;
     363        reset(this.f);
     364        return retry(this.res);
     365}
     366
     367generator splice_out_g {
     368        io_future_t f;
     369        int pipe; int fd; size_t len;
     370        FSM_Result res;
     371};
     372
     373static inline void ?{}(splice_out_g & this, int pipe, int fd, size_t len) {
     374        this.pipe = pipe;
     375        this.fd = fd;
     376        this.len = len;
     377}
     378
     379static inline void fill(splice_out_g & this, struct io_uring_sqe * sqe) {
     380        zero_sqe(sqe);
     381        sqe->opcode = IORING_OP_SPLICE;
     382        sqe->user_data = (uintptr_t)&this.f;
     383        sqe->flags = 0;
     384        sqe->splice_fd_in = this.pipe;
     385        sqe->splice_off_in = (__u64)-1;
     386        sqe->fd = this.fd;
     387        sqe->off = (__u64)-1;
     388        sqe->len = this.len;
     389        sqe->splice_flags = SPLICE_F_MOVE;
     390}
     391
     392static inline int error(splice_out_g & this, int error) {
     393        int ret = close(this.fd);
     394        if( ret != 0 ) {
     395                mutex(serr) serr | "Failed to close fd" | errno;
     396        }
     397        return error(this.res, error);
     398}
     399
     400static inline void wait_and_process(splice_out_g & this) {
     401        wait(this.f);
     402
     403        // Did something crazy happen?
     404        if(this.f.result > this.len) {
     405                mutex(serr) serr | "SPLICE OUT spliced too much!";
     406                return error(this.res, -ERANGE);
     407        }
     408
     409        // Something failed?
     410        if(this.f.result < 0) {
     411                int error = -this.f.result;
     412                if( error == ECONNRESET ) return error(this, -ECONNRESET);
     413                if( error == EPIPE ) return error(this, -EPIPE);
     414                if( error == ECANCELED ) {
     415                        this.f.result = 0;
     416                        goto SHORT_WRITE;
     417                }
     418                if( error == EAGAIN || error == EWOULDBLOCK) {
     419                        mutex(serr) serr | "SPLICE OUT got eagain, WTF!";
     420                        return error(this, -ECONNRESET);
     421                }
     422        }
     423
     424        // Done?
     425        if(this.f.result == this.len) {
     426                return done(this.res);
     427        }
     428
     429SHORT_WRITE:
     430        // It must be a Short Write
     431        this.len -= this.f.result;
     432        reset(this.f);
     433        return retry(this.res);
     434}
     435
     436int answer_sendfile( int pipe[2], int fd, int ans_fd, size_t fsize ) {
     437        #if defined(LINKED_IO)
     438                char buffer[512];
     439                int len = fill_header(buffer, fsize);
     440                header_g header = { fd, buffer, len };
     441                splice_in_t splice_in = { ans_fd, pipe[1], fsize };
     442                splice_out_g splice_out = { pipe[0], fd, fsize };
     443
     444                RETRY_LOOP: for() {
     445                        int have = need(header.res) + need(splice_in.res) + 1;
     446                        int idx = 0;
     447                        struct io_uring_sqe * sqes[3];
     448                        __u32 idxs[3];
     449                        struct $io_context * ctx = cfa_io_allocate(sqes, idxs, have);
     450
     451                        if(need(splice_in.res)) { fill(splice_in, sqes[idx++]); }
     452                        if(need(   header.res)) { fill(header   , sqes[idx++]); }
     453                        fill(splice_out, sqes[idx]);
     454
     455                        // Submit everything
     456                        asm volatile("": : :"memory");
     457                        cfa_io_submit( ctx, idxs, have, false );
     458
     459                        // wait for the results
     460                        // Always wait for splice-in to complete as
     461                        // we may need to kill the connection if it fails
     462                        // If it already completed, this is a no-op
     463                        wait_and_process(splice_in);
     464
     465                        if(is_error(splice_in.res)) {
     466                                mutex(serr) serr | "SPLICE IN failed with" | splice_in.res.error;
     467                                close(fd);
     468                        }
     469
     470                        // Process the other 2
     471                        wait_and_process(header);
     472                        wait_and_process(splice_out);
     473
     474                        if(is_done(splice_out.res)) {
     475                                break RETRY_LOOP;
     476                        }
     477
     478                        // We need to wait for the completion if
     479                        // - both completed
     480                        // - the header failed
     481                        // -
     482
     483                        if(  is_error(header.res)
     484                          || is_error(splice_in.res)
     485                          || is_error(splice_out.res)) {
     486                                return -ECONNRESET;
     487                        }
     488                }
     489
     490                return len + fsize;
     491        #else
     492                int ret = answer_header(fd, fsize);
     493                if( ret < 0 ) { close(fd); return ret; }
     494                return sendfile(pipe, fd, ans_fd, fsize);
     495        #endif
     496}
     497
     498[HttpCode code, bool closed, * const char file, size_t len] http_read(int fd, []char buffer, size_t len) {
     499        char * it = buffer;
     500        size_t count = len - 1;
     501        int rlen = 0;
     502        READ:
     503        for() {
     504                int ret = cfa_recv(fd, (void*)it, count, 0, CFA_IO_LAZY);
     505                // int ret = read(fd, (void*)it, count);
     506                if(ret == 0 ) return [OK200, true, 0, 0];
     507                if(ret < 0 ) {
     508                        if( errno == EAGAIN || errno == EWOULDBLOCK) continue READ;
     509                        if( errno == ECONNRESET ) { close(fd); return [E408, true, 0, 0]; }
     510                        if( errno == EPIPE ) { close(fd); return [E408, true, 0, 0]; }
     511                        abort( "read error: (%d) %s\n", (int)errno, strerror(errno) );
     512                }
     513                it[ret + 1] = '\0';
     514                rlen += ret;
     515
     516                if( strstr( it, "\r\n\r\n" ) ) break;
     517
     518                it += ret;
     519                count -= ret;
     520
     521                if( count < 1 ) return [E414, false, 0, 0];
     522        }
     523
     524        if( options.log ) {
     525                write(sout, buffer, rlen);
     526                sout | nl;
     527        }
     528
     529        it = buffer;
     530        int ret = memcmp(it, "GET /", 5);
     531        if( ret != 0 ) return [E400, false, 0, 0];
     532        it += 5;
     533
     534        char * end = strstr( it, " " );
     535        return [OK200, false, it, end - it];
     536}
     537
    209538//=============================================================================================
    210539
     
    214543
    215544const char * original_http_msgs[] = {
    216         "HTTP/1.1 200 OK\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: ",
    217         "HTTP/1.1 200 OK\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 15\n\nHello, World!\n\n",
    218         "HTTP/1.1 400 Bad Request\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
    219         "HTTP/1.1 404 Not Found\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
    220         "HTTP/1.1 405 Method Not Allowed\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
    221         "HTTP/1.1 408 Request Timeout\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
    222         "HTTP/1.1 413 Payload Too Large\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
    223         "HTTP/1.1 414 URI Too Long\nServer: HttoForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
     545        "HTTP/1.1 200 OK\nServer: HttpForall\nDate: %s \nContent-Type: text/plain\nContent-Length: ",
     546        "HTTP/1.1 200 OK\r\nServer: HttpForall\r\nDate\r\nConnection: keep-alive\r\nContent-Length: 15\r\nContent-Type: text/html: %s \r\n\r\nHello, World!\r\n",
     547        "HTTP/1.1 400 Bad Request\nServer: HttpForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
     548        "HTTP/1.1 404 Not Found\nServer: HttpForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
     549        "HTTP/1.1 405 Method Not Allowed\nServer: HttpForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
     550        "HTTP/1.1 408 Request Timeout\nServer: HttpForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
     551        "HTTP/1.1 413 Payload Too Large\nServer: HttpForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
     552        "HTTP/1.1 414 URI Too Long\nServer: HttpForall\nDate: %s \nContent-Type: text/plain\nContent-Length: 0 \n\n",
    224553};
    225554
     
    251580                Time now = timeHiRes();
    252581                strftime( buff, 100, "%a, %d %b %Y %H:%M:%S %Z", now );
    253                 sout | "Updated date to '" | buff | "'";
     582                // if( options.log ) sout | "Updated date to '" | buff | "'";
    254583
    255584                for(i; KNOWN_CODES) {
     
    264593                this.idx = (this.idx + 1) % 2;
    265594
    266                 sout | "Date thread sleeping";
     595                // if( options.log ) sout | "Date thread sleeping";
    267596
    268597                sleep(1`s);
  • benchmark/io/http/protocol.hfa

    rf95634e rb7fd9daf  
    1616
    1717int answer_error( int fd, HttpCode code );
    18 int answer_header( int fd, size_t size );
    1918int answer_plaintext( int fd );
    2019int answer_empty( int fd );
     20int answer_sendfile( int pipe[2], int fd, int ans_fd, size_t count );
    2121
    2222[HttpCode code, bool closed, * const char file, size_t len] http_read(int fd, []char buffer, size_t len);
    23 
    24 int sendfile( int pipe[2], int fd, int ans_fd, size_t count );
  • benchmark/io/http/worker.cfa

    rf95634e rb7fd9daf  
    122122                        }
    123123
    124                         // Send the header
    125                         int ret = answer_header(fd, count);
    126                         if( ret == -ECONNRESET ) break REQUEST;
    127 
    128124                        // Send the desired file
    129                         ret = sendfile( this.pipe, fd, ans_fd, count);
     125                        int ret = answer_sendfile( this.pipe, fd, ans_fd, count);
    130126                        if( ret == -ECONNRESET ) break REQUEST;
    131127
     
    134130
    135131                if( options.log ) sout | "=== Connection closed ===";
    136                 close(fd);
    137132                continue CONNECTION;
    138133        }
  • benchmark/readyQ/cycle.cpp

    rf95634e rb7fd9daf  
    4141                        Fibre * threads[tthreads];
    4242                        Partner thddata[tthreads];
    43                         for(int i = 0; i < tthreads; i++) {
     43                        for(unsigned i = 0; i < tthreads; i++) {
    4444                                unsigned pi = (i + nthreads) % tthreads;
    4545                                thddata[i].next = &thddata[pi].self;
    4646                        }
    47                         for(int i = 0; i < tthreads; i++) {
     47                        for(unsigned i = 0; i < tthreads; i++) {
    4848                                threads[i] = new Fibre( reinterpret_cast<void (*)(void *)>(partner_main), &thddata[i] );
    4949                        }
     
    5353                        start = timeHiRes();
    5454
    55                         for(int i = 0; i < nthreads; i++) {
     55                        for(unsigned i = 0; i < nthreads; i++) {
    5656                                thddata[i].self.post();
    5757                        }
     
    6262                        printf("\nDone\n");
    6363
    64                         for(int i = 0; i < tthreads; i++) {
     64                        for(unsigned i = 0; i < tthreads; i++) {
    6565                                thddata[i].self.post();
    6666                                fibre_join( threads[i], nullptr );
  • benchmark/readyQ/cycle.go

    rf95634e rb7fd9daf  
    6060        atomic.StoreInt32(&stop, 1)
    6161        end := time.Now()
    62         delta := end.Sub(start)
     62        duration := end.Sub(start)
    6363
    6464        fmt.Printf("\nDone\n")
     
    7474
    7575        p := message.NewPrinter(language.English)
    76         p.Printf("Duration (ms)        : %f\n", delta.Seconds());
     76        p.Printf("Duration (ms)        : %d\n", duration.Milliseconds())
    7777        p.Printf("Number of processors : %d\n", nprocs);
    7878        p.Printf("Number of threads    : %d\n", tthreads);
    7979        p.Printf("Cycle size (# thrds) : %d\n", ring_size);
    8080        p.Printf("Total Operations(ops): %15d\n", global_counter)
    81         p.Printf("Ops per second       : %18.2f\n", float64(global_counter) / delta.Seconds())
    82         p.Printf("ns per ops           : %18.2f\n", float64(delta.Nanoseconds()) / float64(global_counter))
     81        p.Printf("Ops per second       : %18.2f\n", float64(global_counter) / duration.Seconds())
     82        p.Printf("ns per ops           : %18.2f\n", float64(duration.Nanoseconds()) / float64(global_counter))
    8383        p.Printf("Ops per threads      : %15d\n", global_counter / uint64(tthreads))
    8484        p.Printf("Ops per procs        : %15d\n", global_counter / uint64(nprocs))
    85         p.Printf("Ops/sec/procs        : %18.2f\n", (float64(global_counter) / float64(nprocs)) / delta.Seconds())
    86         p.Printf("ns per ops/procs     : %18.2f\n", float64(delta.Nanoseconds()) / (float64(global_counter) / float64(nprocs)))
     85        p.Printf("Ops/sec/procs        : %18.2f\n", (float64(global_counter) / float64(nprocs)) / duration.Seconds())
     86        p.Printf("ns per ops/procs     : %18.2f\n", float64(duration.Nanoseconds()) / (float64(global_counter) / float64(nprocs)))
    8787
    8888}
  • benchmark/readyQ/cycle.rs

    rf95634e rb7fd9daf  
    4646
    4747        let tthreads = nthreads * ring_size;
    48         let exp = Arc::new(bench::BenchData::new(options, tthreads));
     48        let exp = Arc::new(bench::BenchData::new(options, tthreads, None));
    4949
    5050        let s = (1000000 as u64).to_formatted_string(&Locale::en);
  • benchmark/readyQ/locality.go

    rf95634e rb7fd9daf  
    286286        // Print with nice 's, i.e. 1'000'000 instead of 1000000
    287287        p := message.NewPrinter(language.English)
    288         p.Printf("Duration (s)           : %f\n", delta.Seconds());
     288        p.Printf("Duration (ms)          : %f\n", delta.Milliseconds());
    289289        p.Printf("Number of processors   : %d\n", nprocs);
    290290        p.Printf("Number of threads      : %d\n", nthreads);
  • benchmark/readyQ/locality.rs

    rf95634e rb7fd9daf  
    124124                                                return (r as *mut MyData, true);
    125125                                        }
    126                                         let got = self.ptr.compare_and_swap(expected, ctx as *mut MyCtx as u64, Ordering::SeqCst);
    127                                         if got == expected {
     126                                        let got = self.ptr.compare_exchange_weak(expected, ctx as *mut MyCtx as u64, Ordering::SeqCst, Ordering::SeqCst);
     127                                        if got == Ok(expected) {
    128128                                                break expected;// We got the seat
    129129                                        }
     
    285285        assert_eq!(&s, "1,000,000");
    286286
    287         let exp = Arc::new(bench::BenchData::new(options, nprocs));
     287        let exp = Arc::new(bench::BenchData::new(options, nprocs, None));
    288288        let mut results = Result::new();
    289289
  • benchmark/readyQ/transfer.cfa

    rf95634e rb7fd9daf  
    3939                        Pause();
    4040                        if( (timeHiRes() - start) > 5`s ) {
     41                                print_stats_now( bench_cluster, CFA_STATS_READY_Q | CFA_STATS_IO );
    4142                                serr | "Programs has been blocked for more than 5 secs";
    4243                                exit(1);
     
    110111        cfa_option opt[] = {
    111112                BENCH_OPT,
    112                 { 'e', "exhaust", "Whether or not threads that have seen the new epoch should yield or park.", exhaust, parse_yesno}
     113                { 'e', "exhaust", "Whether or not threads that have seen the new epoch should park instead of yielding.", exhaust, parse_yesno}
    113114        };
    114115        BENCH_OPT_PARSE("cforall transition benchmark");
     
    166167        }
    167168
    168         sout | "Duration                : " | ws(3, 3, unit(eng((end - start)`ds))) | 's';
     169        sout | "Duration (ms)           : " | ws(3, 3, unit(eng((end - start)`dms)));
    169170        sout | "Number of processors    : " | nprocs;
    170171        sout | "Number of threads       : " | nthreads;
  • benchmark/readyQ/transfer.cpp

    rf95634e rb7fd9daf  
    173173        }
    174174
    175         std::cout << "Duration                : " << to_miliseconds(end - start) << "ms" << std::endl;
     175        std::cout << "Duration (ms)           : " << to_miliseconds(end - start) << std::endl;
    176176        std::cout << "Number of processors    : " << nprocs << std::endl;
    177177        std::cout << "Number of threads       : " << nthreads << std::endl;
  • benchmark/readyQ/yield.cfa

    rf95634e rb7fd9daf  
    8080                }
    8181
    82                 printf("Took %'ld ms\n", (end - start)`ms);
     82                printf("Duration (ms)       : %'ld\n", (end - start)`dms);
     83                printf("Number of processors: %'d\n", nprocs);
     84                printf("Number of threads   : %'d\n", nthreads);
     85                printf("Total yields        : %'15llu\n", global_counter);
    8386                printf("Yields per second   : %'18.2lf\n", ((double)global_counter) / (end - start)`s);
    8487                printf("ns per yields       : %'18.2lf\n", ((double)(end - start)`ns) / global_counter);
    85                 printf("Total yields        : %'15llu\n", global_counter);
    8688                printf("Yields per procs    : %'15llu\n", global_counter / nprocs);
    8789                printf("Yields/sec/procs    : %'18.2lf\n", (((double)global_counter) / nprocs) / (end - start)`s);
  • benchmark/readyQ/yield.cpp

    rf95634e rb7fd9daf  
    154154
    155155                auto dur_nano = duration_cast<std::nano>(duration);
     156                auto dur_dms  = duration_cast<std::milli>(duration);
    156157
    157                 std::cout << "Took " << duration << " s\n";
     158                printf("Duration (ms)       : %'.2lf\n", dur_dms );
    158159                printf("Total yields        : %'15llu\n", global_counter );
    159160                printf("Yields per procs    : %'15llu\n", global_counter / nprocs );
  • benchmark/rmit.py

    rf95634e rb7fd9daf  
    1616import random
    1717import re
     18import socket
    1819import subprocess
    1920import sys
     
    9596        return nopts
    9697
     98# returns the first option with key 'opt'
     99def search_option(action, opt):
     100        i = 0
     101        while i < len(action):
     102                if action[i] == opt:
     103                        i += 1
     104                        if i != len(action):
     105                                return action[i]
     106                i += 1
     107
     108        return None
     109
    97110def actions_eta(actions):
    98111        time = 0
    99112        for a in actions:
    100                 i = 0
    101                 while i < len(a):
    102                         if a[i] == '-d':
    103                                 i += 1
    104                                 if i != len(a):
    105                                         time += int(a[i])
    106                         i += 1
     113                o = search_option(a, '-d')
     114                if o :
     115                        time += int(o)
    107116        return time
     117
     118taskset_maps = None
     119
     120def init_taskset_maps():
     121        global taskset_maps
     122        known_hosts = {
     123                "jax": {
     124                        range(  1,  24) : "48-71",
     125                        range( 25,  48) : "48-71,144-167",
     126                        range( 49,  96) : "48-95,144-191",
     127                        range( 97, 144) : "24-95,120-191",
     128                        range(145, 192) : "0-95,96-191",
     129                },
     130        }
     131
     132        if (host := socket.gethostname()) in known_hosts:
     133                taskset_maps = known_hosts[host]
     134                return True
     135
     136        print("Warning unknown host '{}', disable taskset usage".format(host), file=sys.stderr)
     137        return False
     138
     139
     140def settaskset_one(action):
     141        o = search_option(action, '-p')
     142        if not o:
     143                return action
     144        try:
     145                oi = int(o)
     146        except ValueError:
     147                return action
     148
     149        m = "Not found"
     150        for key in taskset_maps:
     151                if oi in key:
     152                        return ['taskset', '-c', taskset_maps[key], *action]
     153
     154        print("Warning no mapping for {} cores".format(oi), file=sys.stderr)
     155        return action
     156
     157def settaskset(actions):
     158        return [settaskset_one(a) for a in actions]
    108159
    109160if __name__ == "__main__":
     
    115166        parser.add_argument('--file', nargs='?', type=argparse.FileType('w'), default=sys.stdout)
    116167        parser.add_argument('--trials', help='Number of trials to run per combinaison', type=int, default=3)
     168        parser.add_argument('--notaskset', help='If specified, the trial will not use taskset to match the -p option', action='store_true')
    117169        parser.add_argument('command', metavar='command', type=str, nargs=1, help='the command prefix to run')
    118170        parser.add_argument('candidates', metavar='candidates', type=str, nargs='*', help='the candidate suffix to run')
     
    170222
    171223        # ================================================================================
    172         # Figure out all the combinations to run
     224        # Fixup the different commands
     225
     226        # Add tasksets
     227        withtaskset = False
     228        if not options.notaskset and init_taskset_maps():
     229                withtaskset = True
     230                actions = settaskset(actions)
     231
     232        # ================================================================================
     233        # Now that we know what to run, print it.
     234        # find expected time
     235        time = actions_eta(actions)
     236        print("Running {} trials{}".format(len(actions), "" if time == 0 else " (expecting to take {})".format(str(datetime.timedelta(seconds=int(time)))) ))
     237
     238        # dry run if options ask for it
    173239        if options.list:
    174240                for a in actions:
     
    180246        # Prepare to run
    181247
    182         # find expected time
    183         time = actions_eta(actions)
    184         print("Running {} trials{}".format(len(actions), "" if time == 0 else " (expecting to take {})".format(str(datetime.timedelta(seconds=int(time)))) ))
    185 
    186248        random.shuffle(actions)
    187249
     
    191253        first = True
    192254        for i, a in enumerate(actions):
    193                 sa = " ".join(a)
     255                sa = " ".join(a[3:] if withtaskset else a)
    194256                if first:
    195257                        first = False
     
    208270                                match = re.search("^(.*):(.*)$", s)
    209271                                if match:
    210                                         fields[match.group(1).strip()] = float(match.group(2).strip().replace(',',''))
    211 
    212                 options.file.write(json.dumps([a[0][2:], sa, fields]))
     272                                        try:
     273                                                fields[match.group(1).strip()] = float(match.group(2).strip().replace(',',''))
     274                                        except:
     275                                                pass
     276
     277                options.file.write(json.dumps([a[3 if withtaskset else 0][2:], sa, fields]))
    213278                options.file.flush()
    214279
  • doc/theses/andrew_beach_MMath/Makefile

    rf95634e rb7fd9daf  
    3131
    3232# The main rule, it does all the tex/latex processing.
    33 ${BUILD}/${BASE}.dvi: ${RAWSRC} ${FIGTEX} Makefile | ${BUILD}
     33${BUILD}/${BASE}.dvi: ${RAWSRC} ${FIGTEX} termhandle.pstex resumhandle.pstex Makefile | ${BUILD}
    3434        ${LATEX} ${BASE}
    3535        ${BIBTEX} ${BUILD}/${BASE}
     
    4040${FIGTEX}: ${BUILD}/%.tex: %.fig | ${BUILD}
    4141        fig2dev -L eepic $< > $@
     42
     43%.pstex : %.fig | ${Build}
     44        fig2dev -L pstex $< > ${BUILD}/$@
     45        fig2dev -L pstex_t -p ${BUILD}/$@ $< > ${BUILD}/$@_t
    4246
    4347# Step through dvi & postscript to handle xfig specials.
  • doc/theses/andrew_beach_MMath/code/CondCatch.java

    rf95634e rb7fd9daf  
    66        static boolean should_catch = false;
    77
    8         static void throw_exception() throws EmptyException {
    9                 throw new EmptyException();
    10         }
    11 
    12         static void cond_catch() throws EmptyException {
    13                 try {
    14                         throw_exception();
    15                 } catch (EmptyException exc) {
    16                         if (!should_catch) {
    17                                 throw exc;
    18                         }
    19                 }
    20         }
    21 
    228        private static long loop(int times) {
    239                long startTime = System.nanoTime();
    2410                for (int count = 0 ; count < times ; ++count) {
    2511                        try {
    26                                 cond_catch();
     12                                try {
     13                                        throw new EmptyException();
     14                                } catch (EmptyException exc) {
     15                                        if (!should_catch) {
     16                                                throw exc;
     17                                        }
     18                                }
    2719                        } catch (EmptyException exc) {
    2820                                // ...
     
    4638
    4739                long time = loop(times);
    48                 System.out.println("Run-Time (ns): " + time);
     40                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    4941        }
    5042}
  • doc/theses/andrew_beach_MMath/code/ThrowEmpty.java

    rf95634e rb7fd9daf  
    3939
    4040                long time = loop(times, total_frames);
    41                 System.out.println("Run-Time (ns): " + time);
     41                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    4242        }
    4343}
  • doc/theses/andrew_beach_MMath/code/ThrowFinally.java

    rf95634e rb7fd9daf  
    4444
    4545                long time = loop(times, total_frames);
    46                 System.out.println("Run-Time (ns): " + time);
     46                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    4747        }
    4848}
  • doc/theses/andrew_beach_MMath/code/ThrowOther.java

    rf95634e rb7fd9daf  
    5252
    5353                long time = loop(times, total_frames);
    54                 System.out.println("Run-Time (ns): " + time);
     54                System.out.format("Run-Time (s): %.1f%n", time / 1_000_000_000.);
    5555        }
    5656}
  • doc/theses/andrew_beach_MMath/code/cond-catch.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.h>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110bool should_catch = false;
    12 
    13 void throw_exception() {
    14         throw (empty_exception){&empty_vt};
    15 }
    16 
    17 void cond_catch() {
    18         try {
    19                 throw_exception();
    20         } catch (empty_exception * exc ; should_catch) {
    21                 asm volatile ("# catch block (conditional)");
    22         }
    23 }
    2411
    2512int main(int argc, char * argv[]) {
    2613        unsigned int times = 1;
    2714        if (1 < argc) {
    28                 times = strtol(argv[1], 0p, 10);
     15                times = strto(argv[1], 0p, 10);
    2916        }
    3017        if (2 < argc) {
    31                 should_catch = strtol(argv[2], 0p, 10);
     18                should_catch = (unsigned int)strto(argv[2], 0p, 2);
    3219        }
    3320
     
    3522        for (unsigned int count = 0 ; count < times ; ++count) {
    3623                try {
    37                         cond_catch();
     24                        throw (empty_exception){&empty_vt};
     25                } catch (empty_exception * exc ; should_catch) {
     26                        asm volatile ("# catch block (conditional)");
    3827                } catch (empty_exception * exc) {
    3928                        asm volatile ("# catch block (unconditional)");
     
    4130        }
    4231        Time end_time = timeHiRes();
    43         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     32        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4433}
  • doc/theses/andrew_beach_MMath/code/cond-catch.cpp

    rf95634e rb7fd9daf  
    44#include <exception>
    55#include <iostream>
     6#include <iomanip>
    67
     8using namespace std;
    79using namespace std::chrono;
    810
     
    1012
    1113bool should_catch = false;
    12 
    13 void throw_exception() {
    14         throw EmptyException();
    15 }
    16 
    17 void cond_catch() {
    18         try {
    19                 throw_exception();
    20         } catch (EmptyException & exc) {
    21                 if (!should_catch) {
    22                         throw;
    23                 }
    24                 asm volatile ("# catch block (conditional)");
    25         }
    26 }
    2714
    2815int main(int argc, char * argv[]) {
     
    3825    for (unsigned int count = 0 ; count < times ; ++count) {
    3926        try {
    40                         cond_catch();
     27                        try {
     28                                throw EmptyException();
     29                        } catch (EmptyException & exc) {
     30                                if (!should_catch) {
     31                                        throw;
     32                                }
     33                                asm volatile ("# catch block (conditional)");
     34                        }
    4135                } catch (EmptyException &) {
    4236                        asm volatile ("# catch block (unconditional)");
     
    4539        time_point<steady_clock> end_time = steady_clock::now();
    4640        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    47         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     41        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    4842}
  • doc/theses/andrew_beach_MMath/code/cond-fixup.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110bool should_catch = false;
    12 
    13 void throw_exception() {
    14         throwResume (empty_exception){&empty_vt};
    15 }
    16 
    17 void cond_catch() {
    18         try {
    19                 throw_exception();
    20         } catchResume (empty_exception * exc ; should_catch) {
    21                 asm volatile ("# fixup block (conditional)");
    22         }
    23 }
    2411
    2512int main(int argc, char * argv[]) {
    2613        unsigned int times = 1;
    2714        if (1 < argc) {
    28                 times = strtol(argv[1], 0p, 10);
     15                times = strto(argv[1], 0p, 10);
    2916        }
    3017        if (2 < argc) {
    31                 should_catch = strtol(argv[2], 0p, 10);
     18                should_catch = (unsigned int)strto(argv[2], 0p, 2);
    3219        }
    3320
     
    3522        for (unsigned int count = 0 ; count < times ; ++count) {
    3623                try {
    37                         cond_catch();
     24                        throwResume (empty_exception){&empty_vt};
     25                } catchResume (empty_exception * exc ; should_catch) {
     26                        asm volatile ("# fixup block (conditional)");
    3827                } catchResume (empty_exception * exc) {
    3928                        asm volatile ("# fixup block (unconditional)");
     
    4130        }
    4231        Time end_time = timeHiRes();
    43         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     32        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4433}
  • doc/theses/andrew_beach_MMath/code/resume-detor.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110struct WithDestructor {};
     
    1716void unwind_destructor(unsigned int frames) {
    1817        if (frames) {
    19 
    2018                WithDestructor object;
    2119                unwind_destructor(frames - 1);
     
    2927        unsigned int total_frames = 1;
    3028        if (1 < argc) {
    31                 times = strtol(argv[1], 0p, 10);
     29                times = strto(argv[1], 0p, 10);
    3230        }
    3331        if (2 < argc) {
    34                 total_frames = strtol(argv[2], 0p, 10);
     32                total_frames = strto(argv[2], 0p, 10);
    3533        }
    3634
     
    4442        }
    4543        Time end_time = timeHiRes();
    46         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     44        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4745}
  • doc/theses/andrew_beach_MMath/code/resume-empty.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    89
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
    10 
    11 void unwind_empty(unsigned int frames) {
     10void nounwind_empty(unsigned int frames) {
    1211        if (frames) {
    13                 unwind_empty(frames - 1);
     12                nounwind_empty(frames - 1);
     13                if ( frames == -1 ) printf( "42" );                             // prevent recursion optimizations
    1414        } else {
    1515                throwResume (empty_exception){&empty_vt};
     
    2121        unsigned int total_frames = 1;
    2222        if (1 < argc) {
    23                 times = strtol(argv[1], 0p, 10);
     23                times = strto(argv[1], 0p, 10);
    2424        }
    2525        if (2 < argc) {
    26                 total_frames = strtol(argv[2], 0p, 10);
     26                total_frames = strto(argv[2], 0p, 10);
    2727        }
    2828
    2929        Time start_time = timeHiRes();
    30         for (int count = 0 ; count < times ; ++count) {
     30        for (unsigned int count = 0 ; count < times ; ++count) {
    3131                try {
    32                         unwind_empty(total_frames);
     32                        nounwind_empty(total_frames);
    3333                } catchResume (empty_exception *) {
    3434                        asm volatile ("# fixup block");
     
    3636        }
    3737        Time end_time = timeHiRes();
    38         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     38        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    3939}
  • doc/theses/andrew_beach_MMath/code/resume-finally.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110void unwind_finally(unsigned int frames) {
     
    2524        unsigned int total_frames = 1;
    2625        if (1 < argc) {
    27                 times = strtol(argv[1], 0p, 10);
     26                times = strto(argv[1], 0p, 10);
    2827        }
    2928        if (2 < argc) {
    30                 total_frames = strtol(argv[2], 0p, 10);
     29                total_frames = strto(argv[2], 0p, 10);
    3130        }
    3231
     
    4039        }
    4140        Time end_time = timeHiRes();
    42         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     41        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4342}
  • doc/theses/andrew_beach_MMath/code/resume-other.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
     9exception not_raised_exception;
    810
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
    10 
    11 EHM_EXCEPTION(not_raised_exception)();
    12 
    13 void unwind_other(unsigned int frames) {
     11void nounwind_other(unsigned int frames) {
    1412        if (frames) {
    1513                try {
    16                         unwind_other(frames - 1);
     14                        nounwind_other(frames - 1);
    1715                } catchResume (not_raised_exception *) {
    1816                        asm volatile ("# fixup block (stack)");
     
    2725        unsigned int total_frames = 1;
    2826        if (1 < argc) {
    29                 times = strtol(argv[1], 0p, 10);
     27                times = strto(argv[1], 0p, 10);
    3028        }
    3129        if (2 < argc) {
    32                 total_frames = strtol(argv[2], 0p, 10);
     30                total_frames = strto(argv[2], 0p, 10);
    3331        }
    3432
     
    3634        for (int count = 0 ; count < times ; ++count) {
    3735                try {
    38                         unwind_other(total_frames);
     36                        nounwind_other(total_frames);
    3937                } catchResume (empty_exception *) {
    4038                        asm volatile ("# fixup block (base)");
     
    4240        }
    4341        Time end_time = timeHiRes();
    44         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     42        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4543}
  • doc/theses/andrew_beach_MMath/code/run.sh

    rf95634e rb7fd9daf  
    11#!/usr/bin/env bash
    22
    3 readonly ALL_TESTS=(cond-match-{all,none} cross-{catch,finally} \
    4                 raise-{detor,empty,finally,other})
     3readonly ALL_TESTS=(raise-{empty,detor,finally,other} try-{catch,finally} \
     4                        cond-match-{all,none} fixup-{empty,other})
    55
    66gen-file-name() (
     
    1818)
    1919
    20 readonly N=${1:-5}
     20readonly N=${1:-1}
    2121readonly OUT_FILE=$(gen-file-name ${2:-run-%-$N})
    2222
  • doc/theses/andrew_beach_MMath/code/test.sh

    rf95634e rb7fd9daf  
    44# test.sh LANGUAGE TEST
    55#   Run the TEST in LANGUAGE.
     6# test.sh -a
     7#   Build all tests.
    68# test.sh -b SOURCE_FILE...
    79#   Build a test from SOURCE_FILE(s).
     10# test.sh -c
     11#   Clean all executables.
    812# test.sh -v LANGUAGE TEST FILE
    913#   View the result from TEST in LANGUAGE stored in FILE.
    1014
    11 readonly ITERATIONS=1000000 # 1 000 000, one million
     15readonly DIR=$(dirname "$(readlink -f "$0")")
     16cd $DIR
     17
     18readonly MIL=000000
     19# Various preset values used as arguments.
     20readonly ITERS_1M=1$MIL
     21readonly ITERS_10M=10$MIL
     22readonly ITERS_100M=100$MIL
     23readonly ITERS_1000M=1000$MIL
    1224readonly STACK_HEIGHT=100
    1325
     
    2335        case "$1" in
    2436        *.cfa)
    25                 # Requires a symbolic link.
    26                 mmake "${1%.cfa}" "$1" ./cfa -DNDEBUG -nodebug -O3 "$1" -o "${1%.cfa}"
     37                # A symbolic link/local copy can be used as an override.
     38                cmd=./cfa
     39                if [ ! -x $cmd ]; then
     40                        cmd=cfa
     41                fi
     42                mmake "${1%.cfa}" "$1" $cmd -DNDEBUG -nodebug -O3 "$1" -o "${1%.cfa}"
    2743                ;;
    2844        *.cpp)
    29                 mmake "${1%.cpp}-cpp" "$1" g++ -DNDEBUG -O3 "$1" -o "${1%.cpp}-cpp"
     45                mmake "${1%.cpp}-cpp" "$1" g++-10 -DNDEBUG -O3 "$1" -o "${1%.cpp}-cpp"
    3046                ;;
    3147        *.java)
     
    3955)
    4056
    41 if [ "-b" = "$1" ]; then
     57if [ "-a" = "$1" ]; then
     58        for file in *.cfa *.cpp *.java; do
     59                build $file
     60        done
     61        exit 0
     62elif [ "-b" = "$1" ]; then
    4263        for file in "${@:2}"; do
    4364                build $file
    4465        done
    4566        exit 0
     67elif [ "-c" = "$1" ]; then
     68        rm $(basename -s ".cfa" -a *.cfa)
     69        rm $(basename -s ".cpp" -a *.cpp)
     70        rm *-cpp
     71        rm *.class
     72        exit 0
    4673elif [ "-v" = "$1" -a 4 = "$#" ]; then
    47     TEST_LANG="$2"
    48     TEST_CASE="$3"
    49     VIEW_FILE="$4"
     74        TEST_LANG="$2"
     75        TEST_CASE="$3"
     76        VIEW_FILE="$4"
    5077elif [ 2 -eq "$#" ]; then
    5178        TEST_LANG="$1"
     
    6390
    6491case "$TEST_CASE" in
    65 cond-match-all)
    66         CFAT="./cond-catch $ITERATIONS 1"
    67         CFAR="./cond-fixup $ITERATIONS 1"
    68         CPP="./cond-catch-cpp $ITERATIONS 1"
    69         JAVA="java CondCatch $ITERATIONS 1"
    70         PYTHON="./cond_catch.py $ITERATIONS 1"
    71         ;;
    72 cond-match-none)
    73         CFAT="./cond-catch $ITERATIONS 0"
    74         CFAR="./cond-fixup $ITERATIONS 0"
    75         CPP="./cond-catch-cpp $ITERATIONS 0"
    76         JAVA="java CondCatch $ITERATIONS 0"
    77         PYTHON="./cond_catch.py $ITERATIONS 0"
    78         ;;
    79 cross-catch)
    80         CFAT="./cross-catch $ITERATIONS"
    81         CFAR="./cross-resume $ITERATIONS"
    82         CPP="./cross-catch-cpp $ITERATIONS"
    83         JAVA="java CrossCatch $ITERATIONS"
    84         PYTHON="./cross_catch.py $ITERATIONS"
    85         ;;
    86 cross-finally)
    87         CFAT="./cross-finally $ITERATIONS"
    88         CFAR=unsupported
    89         CPP=unsupported
    90         JAVA="java CrossFinally $ITERATIONS"
    91         PYTHON="./cross_finally.py $ITERATIONS"
     92raise-empty)
     93        CFAT="./throw-empty $ITERS_1M $STACK_HEIGHT"
     94        CFAR="./resume-empty $ITERS_10M $STACK_HEIGHT"
     95        CPP="./throw-empty-cpp $ITERS_1M $STACK_HEIGHT"
     96        JAVA="java ThrowEmpty $ITERS_1M $STACK_HEIGHT"
     97        PYTHON="./throw-empty.py $ITERS_1M $STACK_HEIGHT"
    9298        ;;
    9399raise-detor)
    94         CFAT="./throw-detor $ITERATIONS $STACK_HEIGHT"
    95         CFAR="./resume-detor $ITERATIONS $STACK_HEIGHT"
    96         CPP="./throw-detor-cpp $ITERATIONS $STACK_HEIGHT"
     100        CFAT="./throw-detor $ITERS_1M $STACK_HEIGHT"
     101        CFAR="./resume-detor $ITERS_10M $STACK_HEIGHT"
     102        CPP="./throw-detor-cpp $ITERS_1M $STACK_HEIGHT"
    97103        JAVA=unsupported
    98104        PYTHON=unsupported
    99105        ;;
    100 raise-empty)
    101         CFAT="./throw-empty $ITERATIONS $STACK_HEIGHT"
    102         CFAR="./resume-empty $ITERATIONS $STACK_HEIGHT"
    103         CPP="./throw-empty-cpp $ITERATIONS $STACK_HEIGHT"
    104         JAVA="java ThrowEmpty $ITERATIONS $STACK_HEIGHT"
    105         PYTHON="./throw_empty.py $ITERATIONS $STACK_HEIGHT"
    106         ;;
    107106raise-finally)
    108         CFAT="./throw-finally $ITERATIONS $STACK_HEIGHT"
    109         CFAR="./resume-finally $ITERATIONS $STACK_HEIGHT"
     107        CFAT="./throw-finally $ITERS_1M $STACK_HEIGHT"
     108        CFAR="./resume-finally $ITERS_10M $STACK_HEIGHT"
    110109        CPP=unsupported
    111         JAVA="java ThrowFinally $ITERATIONS $STACK_HEIGHT"
    112         PYTHON="./throw_finally.py $ITERATIONS $STACK_HEIGHT"
     110        JAVA="java ThrowFinally $ITERS_1M $STACK_HEIGHT"
     111        PYTHON="./throw-finally.py $ITERS_1M $STACK_HEIGHT"
    113112        ;;
    114113raise-other)
    115         CFAT="./throw-other $ITERATIONS $STACK_HEIGHT"
    116         CFAR="./resume-other $ITERATIONS $STACK_HEIGHT"
    117         CPP="./throw-other-cpp $ITERATIONS $STACK_HEIGHT"
    118         JAVA="java ThrowOther $ITERATIONS $STACK_HEIGHT"
    119         PYTHON="./throw_other.py $ITERATIONS $STACK_HEIGHT"
     114        CFAT="./throw-other $ITERS_1M $STACK_HEIGHT"
     115        CFAR="./resume-other $ITERS_10M $STACK_HEIGHT"
     116        CPP="./throw-other-cpp $ITERS_1M $STACK_HEIGHT"
     117        JAVA="java ThrowOther $ITERS_1M $STACK_HEIGHT"
     118        PYTHON="./throw-other.py $ITERS_1M $STACK_HEIGHT"
     119        ;;
     120try-catch)
     121        CFAT="./try-catch $ITERS_1000M"
     122        CFAR="./try-resume $ITERS_1000M"
     123        CPP="./try-catch-cpp $ITERS_1000M"
     124        JAVA="java TryCatch $ITERS_1000M"
     125        PYTHON="./try-catch.py $ITERS_1000M"
     126        ;;
     127try-finally)
     128        CFAT="./try-finally $ITERS_1000M"
     129        CFAR=unsupported
     130        CPP=unsupported
     131        JAVA="java TryFinally $ITERS_1000M"
     132        PYTHON="./try-finally.py $ITERS_1000M"
     133        ;;
     134cond-match-all)
     135        CFAT="./cond-catch $ITERS_10M 1"
     136        CFAR="./cond-fixup $ITERS_100M 1"
     137        CPP="./cond-catch-cpp $ITERS_10M 1"
     138        JAVA="java CondCatch $ITERS_10M 1"
     139        PYTHON="./cond-catch.py $ITERS_10M 1"
     140        ;;
     141cond-match-none)
     142        CFAT="./cond-catch $ITERS_10M 0"
     143        CFAR="./cond-fixup $ITERS_100M 0"
     144        CPP="./cond-catch-cpp $ITERS_10M 0"
     145        JAVA="java CondCatch $ITERS_10M 0"
     146        PYTHON="./cond-catch.py $ITERS_10M 0"
     147        ;;
     148fixup-empty)
     149        CFAT="./fixup-empty-f $ITERS_10M $STACK_HEIGHT"
     150        CFAR="./fixup-empty-r $ITERS_10M $STACK_HEIGHT"
     151        CPP="./fixup-empty-cpp $ITERS_10M $STACK_HEIGHT"
     152        JAVA="java FixupEmpty $ITERS_10M $STACK_HEIGHT"
     153        PYTHON="./fixup-empty.py $ITERS_10M $STACK_HEIGHT"
     154        ;;
     155fixup-other)
     156        CFAT="./fixup-other-f $ITERS_10M $STACK_HEIGHT"
     157        CFAR="./fixup-other-r $ITERS_10M $STACK_HEIGHT"
     158        CPP="./fixup-other-cpp $ITERS_10M $STACK_HEIGHT"
     159        JAVA="java FixupOther $ITERS_10M $STACK_HEIGHT"
     160        PYTHON="./fixup-other.py $ITERS_10M $STACK_HEIGHT"
    120161        ;;
    121162*)
     
    140181
    141182if [ -n "$VIEW_FILE" ]; then
    142     grep -A 1 -B 0 "$CALL" "$VIEW_FILE" | sed -n -e 's!Run-Time (ns): !!;T;p'
    143     exit
     183        grep -A 1 -B 0 "$CALL" "$VIEW_FILE" | sed -n -e 's!Run-Time.*: !!;T;p'
     184        exit
    144185fi
    145186
  • doc/theses/andrew_beach_MMath/code/throw-detor.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110struct WithDestructor {};
     
    2827        unsigned int total_frames = 1;
    2928        if (1 < argc) {
    30                 times = strtol(argv[1], 0p, 10);
     29                times = strto(argv[1], 0p, 10);
    3130        }
    3231        if (2 < argc) {
    33                 total_frames = strtol(argv[2], 0p, 10);
     32                total_frames = strto(argv[2], 0p, 10);
    3433        }
    3534
     
    4342        }
    4443        Time end_time = timeHiRes();
    45         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     44        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4645}
  • doc/theses/andrew_beach_MMath/code/throw-detor.cpp

    rf95634e rb7fd9daf  
    44#include <exception>
    55#include <iostream>
     6#include <iomanip>
    67
     8using namespace std;
    79using namespace std::chrono;
    810
     
    4446        time_point<steady_clock> end_time = steady_clock::now();
    4547        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    46         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     48        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    4749}
  • doc/theses/andrew_beach_MMath/code/throw-empty.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
    8 
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    109
    1110void unwind_empty(unsigned int frames) {
    1211        if (frames) {
    1312                unwind_empty(frames - 1);
     13                if ( frames == -1 ) printf( "42" );                             // prevent recursion optimizations
    1414        } else {
    1515                throw (empty_exception){&empty_vt};
     
    2121        unsigned int total_frames = 1;
    2222        if (1 < argc) {
    23                 times = strtol(argv[1], 0p, 10);
     23                times = strto(argv[1], 0p, 10);
    2424        }
    2525        if (2 < argc) {
    26                 total_frames = strtol(argv[2], 0p, 10);
     26                total_frames = strto(argv[2], 0p, 10);
    2727        }
    2828
     
    3636        }
    3737        Time end_time = timeHiRes();
    38         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     38        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    3939}
  • doc/theses/andrew_beach_MMath/code/throw-empty.cpp

    rf95634e rb7fd9daf  
    11// Throw Across Empty Function
    22#include <chrono>
     3#include <cstdio>
    34#include <cstdlib>
    45#include <exception>
    56#include <iostream>
     7#include <iomanip>
    68
     9using namespace std;
    710using namespace std::chrono;
    811
     
    1215        if (frames) {
    1316                unwind_empty(frames - 1);
     17                if (-1 == frames) printf("~");
    1418        } else {
    1519                throw (EmptyException){};
     
    3741        time_point<steady_clock> end_time = steady_clock::now();
    3842        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    39         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     43        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    4044}
  • doc/theses/andrew_beach_MMath/code/throw-finally.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
    89
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     10unsigned int frames;                                                                    // use global because of gcc thunk problem
    1011
    11 void unwind_finally(unsigned int frames) {
     12void unwind_finally(unsigned int dummy) {
    1213        if (frames) {
     14                frames -= 1;
    1315                try {
    14                         unwind_finally(frames - 1);
     16                        unwind_finally(42);
    1517                } finally {
    1618                        asm volatile ("# finally block");
    1719                }
    1820        } else {
     21                dummy = 42;
    1922                throw (empty_exception){&empty_vt};
    2023        }
     
    2528        unsigned int total_frames = 1;
    2629        if (1 < argc) {
    27                 times = strtol(argv[1], 0p, 10);
     30                times = strto(argv[1], 0p, 10);
    2831        }
    2932        if (2 < argc) {
    30                 total_frames = strtol(argv[2], 0p, 10);
     33                total_frames = strto(argv[2], 0p, 10);
    3134        }
     35        frames = total_frames;
    3236
    3337        Time start_time = timeHiRes();
    3438        for (int count = 0 ; count < times ; ++count) {
    3539                try {
    36                         unwind_finally(total_frames);
     40                        unwind_finally(42);
    3741                } catch (empty_exception *) {
    3842                        asm volatile ("# catch block");
     
    4044        }
    4145        Time end_time = timeHiRes();
    42         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     46        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4347}
  • doc/theses/andrew_beach_MMath/code/throw-other.cfa

    rf95634e rb7fd9daf  
    33#include <exception.hfa>
    44#include <fstream.hfa>
    5 #include <stdlib.hfa>
     5#include <stdlib.hfa>                                                                   // strto
    66
    7 EHM_EXCEPTION(empty_exception)();
     7exception empty_exception;
     8vtable(empty_exception) empty_vt;
     9exception not_raised_exception;
    810
    9 EHM_VIRTUAL_TABLE(empty_exception, empty_vt);
     11unsigned int frames;                                                                    // use global because of gcc thunk problem
    1012
    11 EHM_EXCEPTION(not_raised_exception)();
    12 
    13 void unwind_other(unsigned int frames) {
     13void unwind_other(unsigned int dummy) {
    1414        if (frames) {
     15                frames -= 1;
    1516                try {
    16                         unwind_other(frames - 1);
     17                        unwind_other(42);
    1718                } catch (not_raised_exception *) {
    1819                        asm volatile ("# catch block (stack)");
    1920                }
    2021        } else {
     22                dummy = 42;
    2123                throw (empty_exception){&empty_vt};
    2224        }
     
    2729        unsigned int total_frames = 1;
    2830        if (1 < argc) {
    29                 times = strtol(argv[1], 0p, 10);
     31                times = strto(argv[1], 0p, 10);
    3032        }
    3133        if (2 < argc) {
    32                 total_frames = strtol(argv[2], 0p, 10);
     34                total_frames = strto(argv[2], 0p, 10);
    3335        }
     36        frames = total_frames;
    3437
    3538        Time start_time = timeHiRes();
    3639        for (int count = 0 ; count < times ; ++count) {
    3740                try {
    38                         unwind_other(total_frames);
     41                        unwind_other(42);
    3942                } catch (empty_exception *) {
    4043                        asm volatile ("# catch block (base)");
     
    4245        }
    4346        Time end_time = timeHiRes();
    44         sout | "Run-Time (ns): " | (end_time - start_time)`ns;
     47        sout | "Run-Time (s): " | wd(0,1, (end_time - start_time)`ns / 1_000_000_000.);
    4548}
  • doc/theses/andrew_beach_MMath/code/throw-other.cpp

    rf95634e rb7fd9daf  
    44#include <exception>
    55#include <iostream>
     6#include <iomanip>
    67
     8using namespace std;
    79using namespace std::chrono;
    810
     
    4345        time_point<steady_clock> end_time = steady_clock::now();
    4446        nanoseconds duration = duration_cast<nanoseconds>(end_time - start_time);
    45         std::cout << "Run-Time (ns): " << duration.count() << std::endl;
     47        cout << "Run-Time (s): " << fixed << setprecision(1) << duration.count() / 1'000'000'000. << endl;
    4648}
  • doc/theses/andrew_beach_MMath/conclusion.tex

    rf95634e rb7fd9daf  
    11\chapter{Conclusion}
     2\label{c:conclusion}
    23% Just a little knot to tie the paper together.
    34
    4 In the previous chapters this thesis presents the design and implementation
     5In the previous chapters, this thesis presents the design and implementation
    56of \CFA's exception handling mechanism (EHM).
    6 Both the design and implementation are based off of tools and techniques
    7 developed for other programming languages but they were adapted to better fit
    8 \CFA's feature set.
     7Both the design and implementation are based off of tools and
     8techniques developed for other programming languages but they were adapted to
     9better fit \CFA's feature set and add a few features that do not exist in
     10other EHMs,
     11including conditional matching, default handlers for unhandled exceptions
     12and cancellation though coroutines and threads back to the program main stack.
    913
    1014The resulting features cover all of the major use cases of the most popular
    1115termination EHMs of today, along with reintroducing resumption exceptions and
    12 creating some new features that fix with \CFA's larger programming patterns.
     16creating some new features that fit with \CFA's larger programming patterns,
     17such as virtuals independent of traditional objects.
    1318
    14 The implementation has been tested and compared to other implementations.
     19The \CFA project's test suite has been expanded to test the EHM.
     20The implementation's performance has also been
     21compared to other implementations with a small set of targeted
     22micro-benchmarks.
    1523The results, while not cutting edge, are good enough for prototyping, which
    16 is \CFA's stage of development.
     24is \CFA's current stage of development.
    1725
    18 This is a valuable new feature for \CFA in its own right but also serves
    19 as a tool (and motivation) for other developments in the language.
     26This initial EHM will bring valuable new features to \CFA in its own right
     27but also serves as a tool and motivation for other developments in the
     28language.
  • doc/theses/andrew_beach_MMath/exception-layout.fig

    rf95634e rb7fd9daf  
    2828        0 0 1.00 240.00 240.00
    2929         360 405 360 2070
    30 4 0 0 50 -1 0 12 0.0000 4 135 1080 2700 585 Fixed Header\001
    31 4 0 0 50 -1 0 12 0.0000 4 135 1710 540 990 Cforall Information\001
    32 4 0 0 50 -1 0 12 0.0000 4 165 1530 540 585 _Unwind_Exception\001
    33 4 0 0 50 -1 0 12 0.0000 4 165 1260 540 1530 User Exception\001
    34 4 0 0 50 -1 0 12 0.0000 4 165 1170 2655 1530 Variable Body\001
    35 4 0 0 50 -1 0 12 0.0000 4 165 1260 2655 1215 (Fixed Offset)\001
     304 0 0 50 -1 0 12 0.0000 0 135 1080 2700 585 Fixed Header\001
     314 0 0 50 -1 0 12 0.0000 0 135 1575 540 990 Cforall Information\001
     324 0 0 50 -1 0 12 0.0000 0 180 1695 540 585 _Unwind_Exception\001
     334 0 0 50 -1 0 12 0.0000 0 180 1245 540 1530 User Exception\001
     344 0 0 50 -1 0 12 0.0000 0 180 1185 2655 1530 Variable Body\001
     354 0 0 50 -1 0 12 0.0000 0 165 1110 2655 1215 (Fixed Offset)\001
  • doc/theses/andrew_beach_MMath/existing.tex

    rf95634e rb7fd9daf  
    66compatibility with C and its programmers.  \CFA is designed to have an
    77orthogonal feature-set based closely on the C programming paradigm
    8 (non-object-oriented) and these features can be added incrementally to an
    9 existing C code-base allowing programmers to learn \CFA on an as-needed basis.
     8(non-object-oriented), and these features can be added incrementally to an
     9existing C code-base,
     10allowing programmers to learn \CFA on an as-needed basis.
    1011
    1112Only those \CFA features pertaining to this thesis are discussed.
    12 % Also, only new features of \CFA will be discussed,
    1313A familiarity with
    1414C or C-like languages is assumed.
     
    1717\CFA has extensive overloading, allowing multiple definitions of the same name
    1818to be defined~\cite{Moss18}.
    19 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    20 char @i@; int @i@; double @i@;
    21 int @f@(); double @f@();
    22 void @g@( int ); void @g@( double );
    23 \end{lstlisting}
     19\begin{cfa}
     20char i; int i; double i;
     21int f(); double f();
     22void g( int ); void g( double );
     23\end{cfa}
    2424This feature requires name mangling so the assembly symbols are unique for
    2525different overloads. For compatibility with names in C, there is also a syntax
     
    4646\CFA adds a reference type to C as an auto-dereferencing pointer.
    4747They work very similarly to pointers.
    48 Reference-types are written the same way as a pointer-type but each
     48Reference-types are written the same way as pointer-types, but each
    4949asterisk (@*@) is replaced with a ampersand (@&@);
    50 this includes cv-qualifiers and multiple levels of reference.
    51 
    52 Generally, references act like pointers with an implicate dereferencing
     50this includes cv-qualifiers (\snake{const} and \snake{volatile})
     51and multiple levels of reference.
     52
     53Generally, references act like pointers with an implicit dereferencing
    5354operation added to each use of the variable.
    5455These automatic dereferences may be disabled with the address-of operator
     
    6364int && rri = ri;
    6465rri = 3;
    65 &ri = &j; // rebindable
     66&ri = &j;
    6667ri = 5;
    6768\end{cfa}
     
    7980\end{minipage}
    8081
    81 References are intended for pointer situations where dereferencing is the common usage,
    82 \ie the value is more important than the pointer.
     82References are intended to be used when the indirection of a pointer is
     83required, but the address is not as important as the value and dereferencing
     84is the common usage.
    8385Mutable references may be assigned to by converting them to a pointer
    84 with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above
     86with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above.
    8587
    8688\section{Operators}
    8789
    8890\CFA implements operator overloading by providing special names, where
    89 operator usages are translated into function calls using these names.
     91operator expressions are translated into function calls using these names.
    9092An operator name is created by taking the operator symbols and joining them with
    9193@?@s to show where the arguments go.
    9294For example,
    9395infixed multiplication is @?*?@, while prefix dereference is @*?@.
    94 This syntax make it easy to tell the difference between prefix operations
    95 (such as @++?@) and post-fix operations (@?++@).
    96 For example, plus and equality operators are defined for a point type.
     96This syntax makes it easy to tell the difference between prefix operations
     97(such as @++?@) and postfix operations (@?++@).
     98
     99As an example, here are the addition and equality operators for a point type.
    97100\begin{cfa}
    98101point ?+?(point a, point b) { return point{a.x + b.x, a.y + b.y}; }
     
    102105}
    103106\end{cfa}
    104 Note these special names are not limited to builtin
    105 operators, and hence, may be used with arbitrary types.
    106 \begin{cfa}
    107 double ?+?( int x, point y ); // arbitrary types
    108 \end{cfa}
    109 % Some ``near misses", that are that do not match an operator form but looks like
    110 % it may have been supposed to, will generate warning but otherwise they are
    111 % left alone.
    112 Because operators are never part of the type definition they may be added
    113 at any time, including on built-in types.
     107Note that this syntax works effectively as a textual transformation;
     108the compiler converts all operators into functions and then resolves them
     109normally. This means any combination of types may be used,
     110although nonsensical ones (like @double ?==?(point, int);@) are discouraged.
     111This feature is also used for all builtin operators as well,
     112although those are implicitly provided by the language.
    114113
    115114%\subsection{Constructors and Destructors}
    116 
    117 \CFA also provides constructors and destructors as operators, which means they
    118 are functions with special operator names rather than type names in \Cpp.
    119 While constructors and destructions are normally called implicitly by the compiler,
    120 the special operator names, allow explicit calls.
    121 
    122 % Placement new means that this is actually equivalent to C++.
     115In \CFA, constructors and destructors are operators, which means they are
     116functions with special operator names, rather than type names as in \Cpp.
     117Both constructors and destructors can be implicity called by the compiler,
     118however the operator names allow explicit calls.
     119% Placement new means that this is actually equivant to C++.
    123120
    124121The special name for a constructor is @?{}@, which comes from the
     
    129126struct Example { ... };
    130127void ?{}(Example & this) { ... }
     128{
     129        Example a;
     130        Example b = {};
     131}
    131132void ?{}(Example & this, char first, int num) { ... }
    132 Example a;              // implicit constructor calls
    133 Example b = {};
    134 Example c = {'a', 2};
    135 \end{cfa}
    136 Both @a@ and @b@ are initialized with the first constructor,
    137 while @c@ is initialized with the second.
    138 Constructor calls can be replaced with C initialization using special operator \lstinline{@=}.
    139 \begin{cfa}
    140 Example d @= {42};
    141 \end{cfa}
     133{
     134        Example c = {'a', 2};
     135}
     136\end{cfa}
     137Both @a@ and @b@ will be initalized with the first constructor,
     138@b@ because of the explicit call and @a@ implicitly.
     139@c@ will be initalized with the second constructor.
     140Currently, there is no general way to skip initialization.
     141% I don't use @= anywhere in the thesis.
     142
    142143% I don't like the \^{} symbol but $^\wedge$ isn't better.
    143144Similarly, destructors use the special name @^?{}@ (the @^@ has no special
    144145meaning).
    145 % These are a normally called implicitly called on a variable when it goes out
    146 % of scope. They can be called explicitly as well.
    147146\begin{cfa}
    148147void ^?{}(Example & this) { ... }
    149148{
    150         Example e;      // implicit constructor call
    151         ^?{}(e);                // explicit destructor call
    152         ?{}(e);         // explicit constructor call
    153 } // implicit destructor call
     149        Example d;
     150        ^?{}(d);
     151
     152        Example e;
     153} // Implicit call of ^?{}(e);
    154154\end{cfa}
    155155
     
    203203do_twice(i);
    204204\end{cfa}
    205 Any object with a type fulfilling the assertion may be passed as an argument to
     205Any value with a type fulfilling the assertion may be passed as an argument to
    206206a @do_twice@ call.
    207207
     
    223223function. The matched assertion function is then passed as a function pointer
    224224to @do_twice@ and called within it.
    225 The global definition of @do_once@ is ignored, however if quadruple took a
     225The global definition of @do_once@ is ignored, however if @quadruple@ took a
    226226@double@ argument, then the global definition would be used instead as it
    227 is a better match.
    228 % Aaron's thesis might be a good reference here.
    229 
    230 To avoid typing long lists of assertions, constraints can be collect into
    231 convenient package called a @trait@, which can then be used in an assertion
     227would then be a better match.\cite{Moss19}
     228
     229To avoid typing long lists of assertions, constraints can be collected into
     230a convenient package called a @trait@, which can then be used in an assertion
    232231instead of the individual constraints.
    233232\begin{cfa}
     
    243242functions and variables, and are usually used to create a shorthand for, and
    244243give descriptive names to, common groupings of assertions describing a certain
    245 functionality, like @sumable@, @listable@, \etc.
     244functionality, like @summable@, @listable@, \etc.
    246245
    247246Polymorphic structures and unions are defined by qualifying an aggregate type
    248247with @forall@. The type variables work the same except they are used in field
    249 declarations instead of parameters, returns, and local variable declarations.
     248declarations instead of parameters, returns and local variable declarations.
    250249\begin{cfa}
    251250forall(dtype T)
     
    253252        node(T) * next;
    254253        T * data;
    255 }
     254};
    256255node(int) inode;
    257256\end{cfa}
     
    263262
    264263\section{Control Flow}
    265 \CFA has a number of advanced control-flow features: @generator@, @coroutine@, @monitor@, @mutex@ parameters, and @thread@.
     264\CFA has a number of advanced control-flow features: @generator@, @coroutine@,
     265@monitor@, @mutex@ parameters, and @thread@.
    266266The two features that interact with
    267267the exception system are @coroutine@ and @thread@; they and their supporting
     
    270270\subsection{Coroutine}
    271271A coroutine is a type with associated functions, where the functions are not
    272 required to finish execution when control is handed back to the caller. Instead
     272required to finish execution when control is handed back to the caller.
     273Instead,
    273274they may suspend execution at any time and be resumed later at the point of
    274 last suspension. (Generators are stackless and coroutines are stackful.) These
     275last suspension.
     276Coroutine
    275277types are not concurrent but share some similarities along with common
    276 underpinnings, so they are combined with the \CFA threading library. Further
    277 discussion in this section only refers to the coroutine because generators are
    278 similar.
     278underpinnings, so they are combined with the \CFA threading library.
     279% I had mention of generators, but they don't actually matter here.
    279280
    280281In \CFA, a coroutine is created using the @coroutine@ keyword, which is an
     
    293294};
    294295CountUp countup;
    295 for (10) sout | resume(countup).next; // print 10 values
    296296\end{cfa}
    297297Each coroutine has a @main@ function, which takes a reference to a coroutine
    298298object and returns @void@.
    299299%[numbers=left] Why numbers on this one?
    300 \begin{cfa}[numbers=left,numberstyle=\scriptsize\sf]
     300\begin{cfa}
    301301void main(CountUp & this) {
    302         for (unsigned int up = 0;; ++up) {
    303                 this.next = up;
     302        for (unsigned int next = 0 ; true ; ++next) {
     303                this.next = next;
    304304                suspend;$\label{suspend}$
    305305        }
     
    307307\end{cfa}
    308308In this function, or functions called by this function (helper functions), the
    309 @suspend@ statement is used to return execution to the coroutine's resumer
    310 without terminating the coroutine's function(s).
     309@suspend@ statement is used to return execution to the coroutine's caller
     310without terminating the coroutine's function.
    311311
    312312A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@.
    313313The first resume calls the @main@ function at the top. Thereafter, resume calls
    314314continue a coroutine in the last suspended function after the @suspend@
    315 statement, in this case @main@ line~\ref{suspend}.  The @resume@ function takes
    316 a reference to the coroutine structure and returns the same reference. The
    317 return value allows easy access to communication variables defined in the
    318 coroutine object. For example, the @next@ value for coroutine object @countup@
    319 is both generated and collected in the single expression:
    320 @resume(countup).next@.
     315statement. In this case there is only one and, hence, the difference between
     316subsequent calls is the state of variables inside the function and the
     317coroutine object.
     318The return value of @resume@ is a reference to the coroutine, to make it
     319convent to access fields of the coroutine in the same expression.
     320Here is a simple example in a helper function:
     321\begin{cfa}
     322unsigned int get_next(CountUp & this) {
     323        return resume(this).next;
     324}
     325\end{cfa}
     326
     327When the main function returns, the coroutine halts and can no longer be
     328resumed.
    321329
    322330\subsection{Monitor and Mutex Parameter}
    323 Concurrency does not guarantee ordering; without ordering results are
     331Concurrency does not guarantee ordering; without ordering, results are
    324332non-deterministic. To claw back ordering, \CFA uses monitors and @mutex@
    325333(mutual exclusion) parameters. A monitor is another kind of aggregate, where
     
    327335@mutex@ parameters.
    328336
    329 A function that requires deterministic (ordered) execution, acquires mutual
     337A function that requires deterministic (ordered) execution acquires mutual
    330338exclusion on a monitor object by qualifying an object reference parameter with
    331 @mutex@.
    332 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    333 void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB);
    334 \end{lstlisting}
     339the @mutex@ qualifier.
     340\begin{cfa}
     341void example(MonitorA & mutex argA, MonitorB & mutex argB);
     342\end{cfa}
    335343When the function is called, it implicitly acquires the monitor lock for all of
    336344the mutex parameters without deadlock.  This semantics means all functions with
     
    339347
    340348\subsection{Thread}
    341 Functions, generators, and coroutines are sequential so there is only a single
     349Functions, generators and coroutines are sequential, so there is only a single
    342350(but potentially sophisticated) execution path in a program. Threads introduce
    343351multiple execution paths that continue independently.
    344352
    345353For threads to work safely with objects requires mutual exclusion using
    346 monitors and mutex parameters. For threads to work safely with other threads,
     354monitors and mutex parameters. For threads to work safely with other threads
    347355also requires mutual exclusion in the form of a communication rendezvous, which
    348356also supports internal synchronization as for mutex objects. For exceptions,
     
    362370{
    363371        StringWorker stringworker; // fork thread running in "main"
    364 } // implicitly join with thread / wait for completion
     372} // Implicit call to join(stringworker), waits for completion.
    365373\end{cfa}
    366374The thread main is where a new thread starts execution after a fork operation
  • doc/theses/andrew_beach_MMath/features.tex

    rf95634e rb7fd9daf  
    55and begins with a general overview of EHMs. It is not a strict
    66definition of all EHMs nor an exhaustive list of all possible features.
    7 However it does cover the most common structure and features found in them.
     7However, it does cover the most common structure and features found in them.
    88
    99\section{Overview of EHMs}
     
    1919
    2020\paragraph{Raise}
    21 The raise is the starting point for exception handling
     21The raise is the starting point for exception handling,
    2222by raising an exception, which passes it to
    2323the EHM.
     
    3030\paragraph{Handle}
    3131The primary purpose of an EHM is to run some user code to handle a raised
    32 exception. This code is given, with some other information, in a handler.
     32exception. This code is given, along with some other information,
     33in a handler.
    3334
    3435A handler has three common features: the previously mentioned user code, a
    35 region of code it guards, and an exception label/condition that matches
    36 the raised exception.
     36region of code it guards and an exception label/condition that matches
     37against the raised exception.
    3738Only raises inside the guarded region and raising exceptions that match the
    3839label can be handled by a given handler.
     
    4142
    4243The @try@ statements of \Cpp, Java and Python are common examples. All three
    43 show the common features of guarded region, raise, matching and handler.
    44 \begin{cfa}
    45 try {                           // guarded region
    46         ...     
    47         throw exception;        // raise
    48         ...     
    49 } catch( exception ) {  // matching condition, with exception label
    50         ...                             // handler code
    51 }
    52 \end{cfa}
     44also show another common feature of handlers: they are grouped by the guarded
     45region.
    5346
    5447\subsection{Propagation}
    5548After an exception is raised comes what is usually the biggest step for the
    56 EHM: finding and setting up the handler for execution. The propagation from raise to
     49EHM: finding and setting up the handler for execution.
     50The propagation from raise to
    5751handler can be broken up into three different tasks: searching for a handler,
    5852matching against the handler and installing the handler.
     
    6054\paragraph{Searching}
    6155The EHM begins by searching for handlers that might be used to handle
    62 the exception. The search is restricted to
    63 handlers that have the raise site in their guarded
     56the exception.
     57The search will find handlers that have the raise site in their guarded
    6458region.
    6559The search includes handlers in the current function, as well as any in
     
    6761
    6862\paragraph{Matching}
    69 Each handler found is matched with the raised exception. The exception
     63Each handler found is with the raised exception. The exception
    7064label defines a condition that is used with the exception and decides if
    7165there is a match or not.
     66%
    7267In languages where the first match is used, this step is intertwined with
    7368searching; a match check is performed immediately after the search finds
     
    8479different course of action for this case.
    8580This situation only occurs with unchecked exceptions as checked exceptions
    86 (such as in Java) are guaranteed to find a matching handler.
     81(such as in Java) can make the guarantee.
    8782The unhandled action is usually very general, such as aborting the program.
    8883
    8984\paragraph{Hierarchy}
    9085A common way to organize exceptions is in a hierarchical structure.
    91 This pattern comes from object-orientated languages where the
     86This pattern comes from object-oriented languages where the
    9287exception hierarchy is a natural extension of the object hierarchy.
    9388
     
    9893A handler labeled with any given exception can handle exceptions of that
    9994type or any child type of that exception. The root of the exception hierarchy
    100 (here \code{C}{exception}) acts as a catch-all, leaf types catch single types,
     95(here \code{C}{exception}) acts as a catch-all, leaf types catch single types
    10196and the exceptions in the middle can be used to catch different groups of
    10297related exceptions.
    10398
    10499This system has some notable advantages, such as multiple levels of grouping,
    105 the ability for libraries to add new exception types, and the isolation
     100the ability for libraries to add new exception types and the isolation
    106101between different sub-hierarchies.
    107102This design is used in \CFA even though it is not a object-orientated
    108 language; so different tools are used to create the hierarchy.
     103language, so different tools are used to create the hierarchy.
    109104
    110105% Could I cite the rational for the Python IO exception rework?
     
    124119from the raise to the handler and back again.
    125120So far, only communication of the exception's identity is covered.
    126 A common communication method for passing more information is putting fields into the exception instance
     121A common communication method for adding information to an exception
     122is putting fields into the exception instance
    127123and giving the handler access to them.
    128 Using reference fields pointing to data at the raise location allows data to be
    129 passed in both directions.
     124% You can either have pointers/references in the exception, or have p/rs to
     125% the exception when it doesn't have to be copied.
     126Passing references or pointers allows data at the raise location to be
     127updated, passing information in both directions.
    130128
    131129\section{Virtuals}
    132 \label{s:Virtuals}
     130\label{s:virtuals}
     131A common feature in many programming languages is a tool to pair code
     132(behaviour) with data.
     133In \CFA, this is done with the virtual system,
     134which allow type information to be abstracted away, recovered and allow
     135operations to be performed on the abstract objects.
     136
    133137Virtual types and casts are not part of \CFA's EHM nor are they required for
    134138an EHM.
    135139However, one of the best ways to support an exception hierarchy
    136140is via a virtual hierarchy and dispatch system.
    137 Ideally, the virtual system should have been part of \CFA before the work
     141Ideally, the virtual system would have been part of \CFA before the work
    138142on exception handling began, but unfortunately it was not.
    139143Hence, only the features and framework needed for the EHM were
    140 designed and implemented for this thesis. Other features were considered to ensure that
     144designed and implemented for this thesis.
     145Other features were considered to ensure that
    141146the structure could accommodate other desirable features in the future
    142147but are not implemented.
    143148The rest of this section only discusses the implemented subset of the
    144 virtual-system design.
     149virtual system design.
    145150
    146151The virtual system supports multiple ``trees" of types. Each tree is
     
    149154number of children.
    150155Any type that belongs to any of these trees is called a virtual type.
    151 For example, the following hypothetical syntax creates two virtual-type trees.
    152 \begin{flushleft}
    153 \lstDeleteShortInline@
    154 \begin{tabular}{@{\hspace{20pt}}l@{\hspace{20pt}}l}
    155 \begin{cfa}
    156 vtype V0, V1(V0), V2(V0);
    157 vtype W0, W1(W0), W2(W1);
    158 \end{cfa}
    159 &
    160 \raisebox{-0.6\totalheight}{\input{vtable}}
    161 \end{tabular}
    162 \lstMakeShortInline@
    163 \end{flushleft}
    164156% A type's ancestors are its parent and its parent's ancestors.
    165157% The root type has no ancestors.
    166158% A type's descendants are its children and its children's descendants.
    167 Every virtual type (tree node) has a pointer to a virtual table with a unique
    168 @Id@ and a list of virtual members (see \autoref{s:VirtualSystem} for
    169 details). Children inherit their parent's list of virtual members but may add
    170 and/or replace members.  For example,
    171 \begin{cfa}
    172 vtable W0 | { int ?<?( int, int ); int ?+?( int, int ); }
    173 vtable W1 | { int ?+?( int, int ); int w, int ?-?( int, int ); }
    174 \end{cfa}
    175 creates a virtual table for @W0@ initialized with the matching @<@ and @+@
    176 operations visible at this declaration context.  Similarly, @W1@ is initialized
    177 with @<@ from inheritance with @W0@, @+@ is replaced, and @-@ is added, where
    178 both operations are matched at this declaration context. It is important to
    179 note that these are virtual members, not virtual methods of object-orientated
    180 programming, and can be of any type. Finally, trait names can be used to
    181 specify the list of virtual members.
    182 
    183 \PAB{Need to look at these when done.
    184 
    185 \CFA still supports virtual methods as a special case of virtual members.
    186 Function pointers that take a pointer to the virtual type are modified
    187 with each level of inheritance so that refers to the new type.
    188 This means an object can always be passed to a function in its virtual table
    189 as if it were a method.
    190 \todo{Clarify (with an example) virtual methods.}
    191 }%
    192 
    193 Up until this point the virtual system is similar to ones found in
    194 object-orientated languages but this is where \CFA diverges. Objects encapsulate a
    195 single set of methods in each type, universally across the entire program,
    196 and indeed all programs that use that type definition. Even if a type inherits and adds methods, it still encapsulate a
    197 single set of methods. In this sense,
    198 object-oriented types are ``closed" and cannot be altered.
    199 
    200 In \CFA, types do not encapsulate any code. Traits are local for each function and
    201 types can satisfy a local trait, stop satisfying it or, satisfy the same
    202 trait in a different way at any lexical location in the program where a function is call.
    203 In this sense, the set of functions/variables that satisfy a trait for a type is ``open" as the set can change at every call site.
     159
     160For the purposes of illustration, a proposed, but unimplemented, syntax
     161will be used. Each virtual type is represented by a trait with an annotation
     162that makes it a virtual type. This annotation is empty for a root type, which
     163creates a new tree:
     164\begin{cfa}
     165trait root_type(T) virtual() {}
     166\end{cfa}
     167The annotation may also refer to any existing virtual type to make this new
     168type a child of that type and part of the same tree. The parent may itself
     169be a child or a root type and may have any number of existing children.
     170
     171% OK, for some reason the b and t positioning options are reversed here.
     172\begin{minipage}[b]{0.6\textwidth}
     173\begin{cfa}
     174trait child_a(T) virtual(root_type) {}
     175trait grandchild(T) virtual(child_a) {}
     176trait child_b(T) virtual(root_type) {}
     177\end{cfa}
     178\end{minipage}
     179\begin{minipage}{0.4\textwidth}
     180\begin{center}
     181\input{virtual-tree}
     182\end{center}
     183\end{minipage}
     184
     185Every virtual type also has a list of virtual members and a unique id.
     186Both are stored in a virtual table.
     187Every instance of a virtual type also has a pointer to a virtual table stored
     188in it, although there is no per-type virtual table as in many other languages.
     189
     190The list of virtual members is accumulated from the root type down the tree.
     191Every virtual type
     192inherits the list of virtual members from its parent and may add more
     193virtual members to the end of the list which are passed on to its children.
     194Again, using the unimplemented syntax this might look like:
     195\begin{cfa}
     196trait root_type(T) virtual() {
     197        const char * to_string(T const & this);
     198        unsigned int size;
     199}
     200
     201trait child_type(T) virtual(root_type) {
     202        char * irrelevant_function(int, char);
     203}
     204\end{cfa}
     205% Consider adding a diagram, but we might be good with the explanation.
     206
     207As @child_type@ is a child of @root_type@, it has the virtual members of
     208@root_type@ (@to_string@ and @size@) as well as the one it declared
     209(@irrelevant_function@).
     210
     211It is important to note that these are virtual members, and may contain   
     212arbitrary fields, functions or otherwise.
     213The names ``size" and ``align" are reserved for the size and alignment of the
     214virtual type, and are always automatically initialized as such.
     215The other special case is uses of the trait's polymorphic argument
     216(@T@ in the example), which are always updated to refer to the current
     217virtual type. This allows functions that refer to the polymorphic argument
     218to act as traditional virtual methods (@to_string@ in the example), as the
     219object can always be passed to a virtual method in its virtual table.
     220
     221Up until this point, the virtual system is similar to ones found in
     222object-oriented languages, but this is where \CFA diverges.
     223Objects encapsulate a single set of methods in each type,
     224universally across the entire program,
     225and indeed all programs that use that type definition.
     226The only way to change any method is to inherit and define a new type with
     227its own universal implementation. In this sense,
     228these object-oriented types are ``closed" and cannot be altered.
     229% Because really they are class oriented.
     230
     231In \CFA, types do not encapsulate any code.
     232Whether or not a type satisfies any given assertion, and hence any trait, is
     233context sensitive. Types can begin to satisfy a trait, stop satisfying it or
     234satisfy the same trait at any lexical location in the program.
     235In this sense, a type's implementation in the set of functions and variables
     236that allow it to satisfy a trait is ``open" and can change
     237throughout the program.
    204238This capability means it is impossible to pick a single set of functions
    205239that represent a type's implementation across a program.
     
    208242type. A user can define virtual tables that are filled in at their
    209243declaration and given a name. Anywhere that name is visible, even if it is
    210 defined locally inside a function \PAB{What does this mean? (although that means it does not have a
    211 static lifetime)}, it can be used.
     244defined locally inside a function (although in this case the user must ensure
     245it outlives any objects that use it), it can be used.
    212246Specifically, a virtual type is ``bound" to a virtual table that
    213247sets the virtual members for that object. The virtual members can be accessed
    214248through the object.
    215249
    216 While much of the virtual infrastructure is created, it is currently only used
     250This means virtual tables are declared and named in \CFA.
     251They are declared as variables, using the type
     252@vtable(VIRTUAL_TYPE)@ and any valid name. For example:
     253\begin{cfa}
     254vtable(virtual_type_name) table_name;
     255\end{cfa}
     256
     257Like any variable, they may be forward declared with the @extern@ keyword.
     258Forward declaring virtual tables is relatively common.
     259Many virtual types have an ``obvious" implementation that works in most
     260cases.
     261A pattern that has appeared in the early work using virtuals is to
     262implement a virtual table with the the obvious definition and place a forward
     263declaration of it in the header beside the definition of the virtual type.
     264
     265Even on the full declaration, no initializer should be used.
     266Initialization is automatic.
     267The type id and special virtual members ``size" and ``align" only depend on
     268the virtual type, which is fixed given the type of the virtual table, and
     269so the compiler fills in a fixed value.
     270The other virtual members are resolved using the best match to the member's
     271name and type, in the same context as the virtual table is declared using
     272\CFA's normal resolution rules.
     273
     274While much of the virtual infrastructure has been created,
     275it is currently only used
    217276internally for exception handling. The only user-level feature is the virtual
    218277cast, which is the same as the \Cpp \code{C++}{dynamic_cast}.
     
    223282Note, the syntax and semantics matches a C-cast, rather than the function-like
    224283\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
    225 a pointer to a virtual type.
     284pointers to virtual types.
    226285The cast dynamically checks if the @EXPRESSION@ type is the same or a sub-type
    227286of @TYPE@, and if true, returns a pointer to the
    228287@EXPRESSION@ object, otherwise it returns @0p@ (null pointer).
    229 
    230 \section{Exception}
    231 % Leaving until later, hopefully it can talk about actual syntax instead
    232 % of my many strange macros. Syntax aside I will also have to talk about the
    233 % features all exceptions support.
    234 
    235 Exceptions are defined by the trait system; there are a series of traits, and
    236 if a type satisfies them, then it can be used as an exception. The following
     288This allows the expression to be used as both a cast and a type check.
     289
     290\section{Exceptions}
     291
     292The syntax for declaring an exception is the same as declaring a structure
     293except the keyword:
     294\begin{cfa}
     295exception TYPE_NAME {
     296        FIELDS
     297};
     298\end{cfa}
     299
     300Fields are filled in the same way as a structure as well. However, an extra
     301field is added that contains the pointer to the virtual table.
     302It must be explicitly initialized by the user when the exception is
     303constructed.
     304
     305Here is an example of declaring an exception type along with a virtual table,
     306assuming the exception has an ``obvious" implementation and a default
     307virtual table makes sense.
     308
     309\begin{minipage}[t]{0.4\textwidth}
     310Header (.hfa):
     311\begin{cfa}
     312exception Example {
     313        int data;
     314};
     315
     316extern vtable(Example)
     317        example_base_vtable;
     318\end{cfa}
     319\end{minipage}
     320\begin{minipage}[t]{0.6\textwidth}
     321Implementation (.cfa):
     322\begin{cfa}
     323vtable(Example) example_base_vtable
     324\end{cfa}
     325\vfil
     326\end{minipage}
     327
     328%\subsection{Exception Details}
     329This is the only interface needed when raising and handling exceptions.
     330However, it is actually a shorthand for a more complex
     331trait-based interface.
     332
     333The language views exceptions through a series of traits.
     334If a type satisfies them, then it can be used as an exception. The following
    237335is the base trait all exceptions need to match.
    238336\begin{cfa}
     
    241339};
    242340\end{cfa}
    243 The trait is defined over two types, the exception type and the virtual table
     341The trait is defined over two types: the exception type and the virtual table
    244342type. Each exception type should have a single virtual table type.
    245343There are no actual assertions in this trait because the trait system
     
    247345completing the virtual system). The imaginary assertions would probably come
    248346from a trait defined by the virtual system, and state that the exception type
    249 is a virtual type, is a descendant of @exception_t@ (the base exception type),
    250 and note its virtual table type.
     347is a virtual type,
     348that that the type is a descendant of @exception_t@ (the base exception type)
     349and allow the user to find the virtual table type.
    251350
    252351% I did have a note about how it is the programmer's responsibility to make
     
    266365};
    267366\end{cfa}
    268 Both traits ensure a pair of types are an exception type, its virtual table
    269 type,
     367Both traits ensure a pair of types is an exception type and
     368its virtual table type,
    270369and defines one of the two default handlers. The default handlers are used
    271 as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
     370as fallbacks and are discussed in detail in \autoref{s:ExceptionHandling}.
    272371
    273372However, all three of these traits can be tricky to use directly.
    274373While there is a bit of repetition required,
    275374the largest issue is that the virtual table type is mangled and not in a user
    276 facing way. So these three macros are provided to wrap these traits to
     375facing way. So, these three macros are provided to wrap these traits to
    277376simplify referring to the names:
    278 @IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@, and @IS_RESUMPTION_EXCEPTION@.
     377@IS_EXCEPTION@, @IS_TERMINATION_EXCEPTION@ and @IS_RESUMPTION_EXCEPTION@.
    279378
    280379All three take one or two arguments. The first argument is the name of the
     
    282381The second (optional) argument is a parenthesized list of polymorphic
    283382arguments. This argument is only used with polymorphic exceptions and the
    284 list is be passed to both types.
     383list is passed to both types.
    285384In the current set-up, the two types always have the same polymorphic
    286 arguments so these macros can be used without losing flexibility.
    287 
    288 For example consider a function that is polymorphic over types that have a
     385arguments, so these macros can be used without losing flexibility.
     386
     387For example, consider a function that is polymorphic over types that have a
    289388defined arithmetic exception:
    290389\begin{cfa}
     
    303402Both operations follow the same set of steps.
    304403First, a user raises an exception.
    305 Second, the exception propagates up the stack.
     404Second, the exception propagates up the stack, searching for a handler.
    306405Third, if a handler is found, the exception is caught and the handler is run.
    307406After that control continues at a raise-dependent location.
    308 Fourth, if a handler is not found, a default handler is run and, if it returns, then control
     407As an alternate to the third step,
     408if a handler is not found, a default handler is run and, if it returns,
     409then control
    309410continues after the raise.
    310411
    311 %This general description covers what the two kinds have in common.
    312 The differences in the two operations include how propagation is performed, where execution continues
    313 after an exception is caught and handled, and which default handler is run.
     412The differences between the two operations include how propagation is
     413performed, where execution continues after an exception is handled
     414and which default handler is run.
    314415
    315416\subsection{Termination}
    316417\label{s:Termination}
    317 Termination handling is the familiar EHM and used in most programming
     418Termination handling is the familiar kind of handling
     419used in most programming
    318420languages with exception handling.
    319421It is a dynamic, non-local goto. If the raised exception is matched and
     
    347449Then propagation starts with the search. \CFA uses a ``first match" rule so
    348450matching is performed with the copied exception as the search key.
    349 It starts from the raise in the throwing function and proceeds towards the base of the stack,
     451It starts from the raise site and proceeds towards base of the stack,
    350452from callee to caller.
    351453At each stack frame, a check is made for termination handlers defined by the
     
    361463\end{cfa}
    362464When viewed on its own, a try statement simply executes the statements
    363 in the \snake{GUARDED_BLOCK}, and when those are finished,
     465in the \snake{GUARDED_BLOCK} and when those are finished,
    364466the try statement finishes.
    365467
     
    387489termination exception types.
    388490The global default termination handler performs a cancellation
    389 (see \vref{s:Cancellation} for the justification) on the current stack with the copied exception.
    390 Since it is so general, a more specific handler is usually
    391 defined, possibly with a detailed message, and used for specific exception type, effectively overriding the default handler.
     491(as described in \vref{s:Cancellation})
     492on the current stack with the copied exception.
     493Since it is so general, a more specific handler can be defined,
     494overriding the default behaviour for the specific exception types.
     495
     496For example, consider an error reading a configuration file.
     497This is most likely a problem with the configuration file (@config_error@),
     498but the function could have been passed the wrong file name (@arg_error@).
     499In this case the function could raise one exception and then, if it is
     500unhandled, raise the other.
     501This is not usual behaviour for either exception so changing the
     502default handler will be done locally:
     503\begin{cfa}
     504{
     505        void defaultTerminationHandler(config_error &) {
     506                throw (arg_error){arg_vt};
     507        }
     508        throw (config_error){config_vt};
     509}
     510\end{cfa}
    392511
    393512\subsection{Resumption}
    394513\label{s:Resumption}
    395514
    396 Resumption exception handling is the less familar EHM, but is
     515Resumption exception handling is less familar form of exception handling,
     516but is
    397517just as old~\cite{Goodenough75} and is simpler in many ways.
    398518It is a dynamic, non-local function call. If the raised exception is
     
    403523function once the error is corrected, and
    404524ignorable events, such as logging where nothing needs to happen and control
    405 should always continue from the raise point.
     525should always continue from the raise site.
     526
     527Except for the changes to fit into that pattern, resumption exception
     528handling is symmetric with termination exception handling, by design
     529(see \autoref{s:Termination}).
    406530
    407531A resumption raise is started with the @throwResume@ statement:
     
    409533throwResume EXPRESSION;
    410534\end{cfa}
    411 \todo{Decide on a final set of keywords and use them everywhere.}
    412 It works much the same way as the termination throw.
    413 The expression must return a reference to a resumption exception,
    414 where the resumption exception is any type that satisfies the trait
    415 @is_resumption_exception@ at the call site.
    416 The assertions from this trait are available to
    417 the exception system while handling the exception.
    418 
    419 At run-time, no exception copy is made, since
     535% The new keywords are currently ``experimental" and not used in this work.
     536It works much the same way as the termination raise, except the
     537type must satisfy the \snake{is_resumption_exception} that uses the
     538default handler: \defaultResumptionHandler.
     539This can be specialized for particular exception types.
     540
     541At run-time, no exception copy is made. Since
    420542resumption does not unwind the stack nor otherwise remove values from the
    421 current scope, so there is no need to manage memory to keep the exception in scope.
    422 
    423 Then propagation starts with the search. It starts from the raise in the
    424 resuming function and proceeds towards the base of the stack,
    425 from callee to caller.
    426 At each stack frame, a check is made for resumption handlers defined by the
    427 @catchResume@ clauses of a @try@ statement.
     543current scope, there is no need to manage memory to keep the exception
     544allocated.
     545
     546Then propagation starts with the search,
     547following the same search path as termination,
     548from the raise site to the base of stack and top of try statement to bottom.
     549However, the handlers on try statements are defined by @catchResume@ clauses.
    428550\begin{cfa}
    429551try {
     
    435557}
    436558\end{cfa}
    437 % PAB, you say this above.
    438 % When a try statement is executed, it simply executes the statements in the
    439 % @GUARDED_BLOCK@ and then finishes.
    440 %
    441 % However, while the guarded statements are being executed, including any
    442 % invoked functions, all the handlers in these statements are included in the
    443 % search path.
    444 % Hence, if a resumption exception is raised, these handlers may be matched
    445 % against the exception and may handle it.
    446 %
    447 % Exception matching checks the handler in each catch clause in the order
    448 % they appear, top to bottom. If the representation of the raised exception type
    449 % is the same or a descendant of @EXCEPTION_TYPE@$_i$, then @NAME@$_i$
    450 % (if provided) is bound to a pointer to the exception and the statements in
    451 % @HANDLER_BLOCK@$_i$ are executed.
    452 % If control reaches the end of the handler, execution continues after the
    453 % the raise statement that raised the handled exception.
    454 %
    455 % Like termination, if no resumption handler is found during the search,
    456 % then the default handler (\defaultResumptionHandler) visible at the raise
    457 % statement is called. It will use the best match at the raise sight according
    458 % to \CFA's overloading rules. The default handler is
    459 % passed the exception given to the raise. When the default handler finishes
    460 % execution continues after the raise statement.
    461 %
    462 % There is a global @defaultResumptionHandler{} is polymorphic over all
    463 % resumption exceptions and performs a termination throw on the exception.
    464 % The \defaultTerminationHandler{} can be overridden by providing a new
    465 % function that is a better match.
    466 
    467 The @GUARDED_BLOCK@ and its associated nested guarded statements work the same
    468 for resumption as for termination, as does exception matching at each
    469 @catchResume@. Similarly, if no resumption handler is found during the search,
    470 then the currently visible default handler (\defaultResumptionHandler) is
    471 called and control continues after the raise statement if it returns. Finally,
    472 there is also a global @defaultResumptionHandler@, which can be overridden,
    473 that is polymorphic over all resumption exceptions but performs a termination
    474 throw on the exception rather than a cancellation.
    475 
    476 Throwing the exception in @defaultResumptionHandler@ has the positive effect of
    477 walking the stack a second time for a recovery handler. Hence, a programmer has
    478 two chances for help with a problem, fixup or recovery, should either kind of
    479 handler appear on the stack. However, this dual stack walk leads to following
    480 apparent anomaly:
    481 \begin{cfa}
    482 try {
    483         throwResume E;
    484 } catch (E) {
    485         // this handler runs
    486 }
    487 \end{cfa}
    488 because the @catch@ appears to handle a @throwResume@, but a @throwResume@ only
    489 matches with @catchResume@. The anomaly results because the unmatched
    490 @catchResuem@, calls @defaultResumptionHandler@, which in turn throws @E@.
    491 
    492 % I wonder if there would be some good central place for this.
    493 Note, termination and resumption handlers may be used together
     559Note that termination handlers and resumption handlers may be used together
    494560in a single try statement, intermixing @catch@ and @catchResume@ freely.
    495561Each type of handler only interacts with exceptions from the matching
    496562kind of raise.
     563Like @catch@ clauses, @catchResume@ clauses have no effect if an exception
     564is not raised.
     565
     566The matching rules are exactly the same as well.
     567The first major difference here is that after
     568@EXCEPTION_TYPE@$_i$ is matched and @NAME@$_i$ is bound to the exception,
     569@HANDLER_BLOCK@$_i$ is executed right away without first unwinding the stack.
     570After the block has finished running, control jumps to the raise site, where
     571the just handled exception came from, and continues executing after it,
     572not after the try statement.
     573
     574For instance, a resumption used to send messages to the logger may not
     575need to be handled at all. Putting the following default handler
     576at the global scope can make handling that exception optional by default.
     577\begin{cfa}
     578void defaultResumptionHandler(log_message &) {
     579    // Nothing, it is fine not to handle logging.
     580}
     581// ... No change at raise sites. ...
     582throwResume (log_message){strlit_log, "Begin event processing."}
     583\end{cfa}
    497584
    498585\subsubsection{Resumption Marking}
     
    501588not unwind the stack. A side effect is that, when a handler is matched
    502589and run, its try block (the guarded statements) and every try statement
    503 searched before it are still on the stack. There presence can lead to
    504 the \emph{recursive resumption problem}.
     590searched before it are still on the stack. Their presence can lead to
     591the recursive resumption problem.\cite{Buhr00a}
     592% Other possible citation is MacLaren77, but the form is different.
    505593
    506594The recursive resumption problem is any situation where a resumption handler
     
    516604When this code is executed, the guarded @throwResume@ starts a
    517605search and matches the handler in the @catchResume@ clause. This
    518 call is placed on the stack above the try-block. Now the second raise in the handler
    519 searches the same try block, matches, and puts another instance of the
     606call is placed on the stack above the try-block.
     607Now the second raise in the handler searches the same try block,
     608matches again and then puts another instance of the
    520609same handler on the stack leading to infinite recursion.
    521610
    522 While this situation is trivial and easy to avoid, much more complex cycles can
    523 form with multiple handlers and different exception types.  The key point is
    524 that the programmer's intuition expects every raise in a handler to start
    525 searching \emph{below} the @try@ statement, making it difficult to understand
    526 and fix the problem.
    527 
     611While this situation is trivial and easy to avoid, much more complex cycles
     612can form with multiple handlers and different exception types.
    528613To prevent all of these cases, each try statement is ``marked" from the
    529 time the exception search reaches it to either when a matching handler
    530 completes or when the search reaches the base
     614time the exception search reaches it to either when a handler completes
     615handling that exception or when the search reaches the base
    531616of the stack.
    532617While a try statement is marked, its handlers are never matched, effectively
     
    537622\end{center}
    538623
    539 There are other sets of marking rules that could be used,
    540 for instance, marking just the handlers that caught the exception,
     624There are other sets of marking rules that could be used.
     625For instance, marking just the handlers that caught the exception
    541626would also prevent recursive resumption.
    542 However, the rule selected mirrors what happens with termination,
    543 and hence, matches programmer intuition that a raise searches below a try.
    544 
    545 In detail, the marked try statements are the ones that would be removed from
     627However, the rules selected mirror what happens with termination,
     628so this reduces the amount of rules and patterns a programmer has to know.
     629
     630The marked try statements are the ones that would be removed from
    546631the stack for a termination exception, \ie those on the stack
    547632between the handler and the raise statement.
     
    580665// Handle a failure relating to f2 further down the stack.
    581666\end{cfa}
    582 In this example the file that experienced the IO error is used to decide
     667In this example, the file that experienced the IO error is used to decide
    583668which handler should be run, if any at all.
    584669
     
    609694
    610695\subsection{Comparison with Reraising}
    611 Without conditional catch, the only approach to match in more detail is to reraise
    612 the exception after it has been caught, if it could not be handled.
     696In languages without conditional catch -- that is, no ability to match an
     697exception based on something other than its type -- it can be mimicked
     698by matching all exceptions of the right type, checking any additional
     699conditions inside the handler and re-raising the exception if it does not
     700match those.
     701
     702Here is a minimal example comparing both patterns, using @throw;@
     703(no operand) to start a re-raise.
    613704\begin{center}
    614 \begin{tabular}{l|l}
     705\begin{tabular}{l r}
    615706\begin{cfa}
    616707try {
    617         do_work_may_throw();
    618 } catch(excep_t * ex; can_handle(ex)) {
    619 
    620         handle(ex);
    621 
    622 
    623 
    624 }
     708    do_work_may_throw();
     709} catch(exception_t * exc ;
     710                can_handle(exc)) {
     711    handle(exc);
     712}
     713
     714
     715
    625716\end{cfa}
    626717&
    627718\begin{cfa}
    628719try {
    629         do_work_may_throw();
    630 } catch(excep_t * ex) {
    631         if (can_handle(ex)) {
    632                 handle(ex);
     720    do_work_may_throw();
     721} catch(exception_t * exc) {
     722    if (can_handle(exc)) {
     723        handle(exc);
     724    } else {
     725        throw;
     726    }
     727}
     728\end{cfa}
     729\end{tabular}
     730\end{center}
     731At first glance, catch-and-reraise may appear to just be a quality-of-life
     732feature, but there are some significant differences between the two
     733strategies.
     734
     735A simple difference that is more important for \CFA than many other languages
     736is that the raise site changes with a re-raise, but does not with a
     737conditional catch.
     738This is important in \CFA because control returns to the raise site to run
     739the per-site default handler. Because of this, only a conditional catch can
     740allow the original raise to continue.
     741
     742The more complex issue comes from the difference in how conditional
     743catches and re-raises handle multiple handlers attached to a single try
     744statement. A conditional catch will continue checking later handlers while
     745a re-raise will skip them.
     746If the different handlers could handle some of the same exceptions,
     747translating a try statement that uses one to use the other can quickly
     748become non-trivial:
     749
     750\noindent
     751Original, with conditional catch:
     752\begin{cfa}
     753...
     754} catch (an_exception * e ; check_a(e)) {
     755        handle_a(e);
     756} catch (exception_t * e ; check_b(e)) {
     757        handle_b(e);
     758}
     759\end{cfa}
     760Translated, with re-raise:
     761\begin{cfa}
     762...
     763} catch (exception_t * e) {
     764        an_exception * an_e = (virtual an_exception *)e;
     765        if (an_e && check_a(an_e)) {
     766                handle_a(an_e);
     767        } else if (check_b(e)) {
     768                handle_b(e);
    633769        } else {
    634770                throw;
     
    636772}
    637773\end{cfa}
    638 \end{tabular}
    639 \end{center}
    640 Notice catch-and-reraise increases complexity by adding additional data and
    641 code to the exception process. Nevertheless, catch-and-reraise can simulate
    642 conditional catch straightforwardly, when exceptions are disjoint, \ie no
    643 inheritance.
    644 
    645 However, catch-and-reraise simulation becomes unusable for exception inheritance.
    646 \begin{flushleft}
    647 \begin{cfa}[xleftmargin=6pt]
    648 exception E1;
    649 exception E2(E1); // inheritance
    650 \end{cfa}
    651 \begin{tabular}{l|l}
    652 \begin{cfa}
    653 try {
    654         ... foo(); ... // raise E1/E2
    655         ... bar(); ... // raise E1/E2
    656 } catch( E2 e; e.rtn == foo ) {
    657         ...
    658 } catch( E1 e; e.rtn == foo ) {
    659         ...
    660 } catch( E1 e; e.rtn == bar ) {
    661         ...
    662 }
    663 
    664 \end{cfa}
    665 &
    666 \begin{cfa}
    667 try {
    668         ... foo(); ...
    669         ... bar(); ...
    670 } catch( E2 e ) {
    671         if ( e.rtn == foo ) { ...
    672         } else throw; // reraise
    673 } catch( E1 e ) {
    674         if (e.rtn == foo) { ...
    675         } else if (e.rtn == bar) { ...
    676         else throw; // reraise
    677 }
    678 \end{cfa}
    679 \end{tabular}
    680 \end{flushleft}
    681 The derived exception @E2@ must be ordered first in the catch list, otherwise
    682 the base exception @E1@ catches both exceptions. In the catch-and-reraise code
    683 (right), the @E2@ handler catches exceptions from both @foo@ and
    684 @bar@. However, the reraise misses the following catch clause. To fix this
    685 problem, an enclosing @try@ statement is need to catch @E2@ for @bar@ from the
    686 reraise, and its handler must duplicate the inner handler code for @bar@. To
    687 generalize, this fix for any amount of inheritance and complexity of try
    688 statement requires a technique called \emph{try-block
    689 splitting}~\cite{Krischer02}, which is not discussed in this thesis. It is
    690 sufficient to state that conditional catch is more expressive than
    691 catch-and-reraise in terms of complexity.
    692 
    693 \begin{comment}
    694 That is, they have the same behaviour in isolation.
    695 Two things can expose differences between these cases.
    696 
    697 One is the existence of multiple handlers on a single try statement.
    698 A reraise skips all later handlers for a try statement but a conditional
    699 catch does not.
    700 % Hence, if an earlier handler contains a reraise later handlers are
    701 % implicitly skipped, with a conditional catch they are not.
    702 Still, they are equivalently powerful,
    703 both can be used two mimic the behaviour of the other,
    704 as reraise can pack arbitrary code in the handler and conditional catches
    705 can put arbitrary code in the predicate.
    706 % I was struggling with a long explanation about some simple solutions,
    707 % like repeating a condition on later handlers, and the general solution of
    708 % merging everything together. I don't think it is useful though unless its
    709 % for a proof.
    710 % https://en.cppreference.com/w/cpp/language/throw
    711 
    712 The question then becomes ``Which is a better default?"
    713 We believe that not skipping possibly useful handlers is a better default.
    714 If a handler can handle an exception it should and if the handler can not
    715 handle the exception then it is probably safer to have that explicitly
    716 described in the handler itself instead of implicitly described by its
    717 ordering with other handlers.
    718 % Or you could just alter the semantics of the throw statement. The handler
    719 % index is in the exception so you could use it to know where to start
    720 % searching from in the current try statement.
    721 % No place for the `goto else;` metaphor.
    722 
    723 The other issue is all of the discussion above assumes that the only
    724 way to tell apart two raises is the exception being raised and the remaining
    725 search path.
    726 This is not true generally, the current state of the stack can matter in
    727 a number of cases, even only for a stack trace after an program abort.
    728 But \CFA has a much more significant need of the rest of the stack, the
    729 default handlers for both termination and resumption.
    730 
    731 % For resumption it turns out it is possible continue a raise after the
    732 % exception has been caught, as if it hadn't been caught in the first place.
    733 This becomes a problem combined with the stack unwinding used in termination
    734 exception handling.
    735 The stack is unwound before the handler is installed, and hence before any
    736 reraises can run. So if a reraise happens the previous stack is gone,
    737 the place on the stack where the default handler was supposed to run is gone,
    738 if the default handler was a local function it may have been unwound too.
    739 There is no reasonable way to restore that information, so the reraise has
    740 to be considered as a new raise.
    741 This is the strongest advantage conditional catches have over reraising,
    742 they happen before stack unwinding and avoid this problem.
    743 
    744 % The one possible disadvantage of conditional catch is that it runs user
    745 % code during the exception search. While this is a new place that user code
    746 % can be run destructors and finally clauses are already run during the stack
    747 % unwinding.
     774(There is a simpler solution if @handle_a@ never raises exceptions,
     775using nested try statements.)
     776
     777% } catch (an_exception * e ; check_a(e)) {
     778%     handle_a(e);
     779% } catch (exception_t * e ; !(virtual an_exception *)e && check_b(e)) {
     780%     handle_b(e);
     781% }
    748782%
    749 % https://www.cplusplus.com/reference/exception/current_exception/
    750 %   `exception_ptr current_exception() noexcept;`
    751 % https://www.python.org/dev/peps/pep-0343/
    752 \end{comment}
     783% } catch (an_exception * e)
     784%   if (check_a(e)) {
     785%     handle_a(e);
     786%   } else throw;
     787% } catch (exception_t * e)
     788%   if (check_b(e)) {
     789%     handle_b(e);
     790%   } else throw;
     791% }
     792In similar simple examples, translating from re-raise to conditional catch
     793takes less code but it does not have a general, trivial solution either.
     794
     795So, given that the two patterns do not trivially translate into each other,
     796it becomes a matter of which on should be encouraged and made the default.
     797From the premise that if a handler could handle an exception then it
     798should, it follows that checking as many handlers as possible is preferred.
     799So, conditional catch and checking later handlers is a good default.
    753800
    754801\section{Finally Clauses}
    755802\label{s:FinallyClauses}
    756 Finally clauses are used to preform unconditional clean-up when leaving a
     803Finally clauses are used to perform unconditional cleanup when leaving a
    757804scope and are placed at the end of a try statement after any handler clauses:
    758805\begin{cfa}
     
    766813The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    767814stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    768 finishes, or during an unwind.
     815finishes or during an unwind.
    769816The only time the block is not executed is if the program is exited before
    770817the stack is unwound.
     
    772819Execution of the finally block should always finish, meaning control runs off
    773820the end of the block. This requirement ensures control always continues as if
    774 the finally clause is not present, \ie finally is for cleanup not changing
     821the finally clause is not present, \ie finally is for cleanup, not changing
    775822control flow.
    776823Because of this requirement, local control flow out of the finally block
    777824is forbidden. The compiler precludes any @break@, @continue@, @fallthru@ or
    778825@return@ that causes control to leave the finally block. Other ways to leave
    779 the finally block, such as a long jump or termination are much harder to check,
    780 and at best requiring additional run-time overhead, and so are only
     826the finally block, such as a @longjmp@ or termination are much harder to check,
     827and at best require additional run-time overhead, and so are only
    781828discouraged.
    782829
    783 Not all languages with unwinding have finally clauses. Notably \Cpp does
     830Not all languages with unwinding have finally clauses. Notably, \Cpp does
    784831without it as destructors, and the RAII design pattern, serve a similar role.
    785832Although destructors and finally clauses can be used for the same cases,
    786833they have their own strengths, similar to top-level function and lambda
    787834functions with closures.
    788 Destructors take more work for their creation, but if there is clean-up code
     835Destructors take more work to create, but if there is clean-up code
    789836that needs to be run every time a type is used, they are much easier
    790 to set-up.
    791 On the other hand finally clauses capture the local context, so is easy to
    792 use when the clean-up is not dependent on the type of a variable or requires
     837to set up for each use. % It's automatic.
     838On the other hand, finally clauses capture the local context, so are easy to
     839use when the cleanup is not dependent on the type of a variable or requires
    793840information from multiple variables.
    794841
     
    797844Cancellation is a stack-level abort, which can be thought of as as an
    798845uncatchable termination. It unwinds the entire current stack, and if
    799 possible forwards the cancellation exception to a different stack.
     846possible, forwards the cancellation exception to a different stack.
    800847
    801848Cancellation is not an exception operation like termination or resumption.
    802849There is no special statement for starting a cancellation; instead the standard
    803 library function @cancel_stack@ is called passing an exception. Unlike a
    804 raise, this exception is not used in matching only to pass information about
     850library function @cancel_stack@ is called, passing an exception. Unlike a
     851raise, this exception is not used in matching, only to pass information about
    805852the cause of the cancellation.
    806 Finaly, since a cancellation only unwinds and forwards, there is no default handler.
    807 
    808 After @cancel_stack@ is called the exception is copied into the EHM's memory
     853Finally, as no handler is provided, there is no default handler.
     854
     855After @cancel_stack@ is called, the exception is copied into the EHM's memory
    809856and the current stack is unwound.
    810857The behaviour after that depends on the kind of stack being cancelled.
    811858
    812859\paragraph{Main Stack}
    813 The main stack is the one used by the program main at the start of execution,
     860The main stack is the one used by
     861the program's main function at the start of execution,
    814862and is the only stack in a sequential program.
    815 After the main stack is unwound there is a program-level abort.
    816 
    817 The reasons for this semantics in a sequential program is that there is no more code to execute.
    818 This semantics also applies to concurrent programs, too, even if threads are running.
    819 That is, if any threads starts a cancellation, it implies all threads terminate.
    820 Keeping the same behaviour in sequential and concurrent programs is simple.
    821 Also, even in concurrent programs there may not currently be any other stacks
    822 and even if other stacks do exist, main has no way to know where they are.
     863After the main stack is unwound, there is a program-level abort.
     864
     865The first reason for this behaviour is for sequential programs where there
     866is only one stack, and hence no stack to pass information to.
     867Second, even in concurrent programs, the main stack has no dependency
     868on another stack and no reliable way to find another living stack.
     869Finally, keeping the same behaviour in both sequential and concurrent
     870programs is simple and easy to understand.
    823871
    824872\paragraph{Thread Stack}
     
    832880and an implicit join (from a destructor call). The explicit join takes the
    833881default handler (@defaultResumptionHandler@) from its calling context while
    834 the implicit join provides its own; which does a program abort if the
     882the implicit join provides its own, which does a program abort if the
    835883@ThreadCancelled@ exception cannot be handled.
    836884
     
    850898
    851899With explicit join and a default handler that triggers a cancellation, it is
    852 possible to cascade an error across any number of threads, cleaning up each
     900possible to cascade an error across any number of threads,
     901alternating between the resumption (possibly termination) and cancellation,
     902cleaning up each
    853903in turn, until the error is handled or the main thread is reached.
    854904
     
    858908After a coroutine stack is unwound, control returns to the @resume@ function
    859909that most recently resumed it. @resume@ reports a
    860 @CoroutineCancelled@ exception, which contains a references to the cancelled
     910@CoroutineCancelled@ exception, which contains a reference to the cancelled
    861911coroutine and the exception used to cancel it.
    862912The @resume@ function also takes the \defaultResumptionHandler{} from the
    863913caller's context and passes it to the internal report.
    864914
    865 A coroutine only knows of two other coroutines, its starter and its last resumer.
     915A coroutine only knows of two other coroutines,
     916its starter and its last resumer.
    866917The starter has a much more distant connection, while the last resumer just
    867918(in terms of coroutine state) called resume on this coroutine, so the message
     
    869920
    870921With a default handler that triggers a cancellation, it is possible to
    871 cascade an error across any number of coroutines, cleaning up each in turn,
     922cascade an error across any number of coroutines,
     923alternating between the resumption (possibly termination) and cancellation,
     924cleaning up each in turn,
    872925until the error is handled or a thread stack is reached.
    873 
    874 \PAB{Part of this I do not understand. A cancellation cannot be caught. But you
    875 talk about handling a cancellation in the last sentence. Which is correct?}
  • doc/theses/andrew_beach_MMath/future.tex

    rf95634e rb7fd9daf  
    22\label{c:future}
    33
     4The following discussion covers both possible interesting research
     5that could follow from this work as well as simple implementation
     6improvements.
     7
    48\section{Language Improvements}
    5 \todo{Future/Language Improvements seems to have gotten mixed up. It is
    6 presented as ``waiting on language improvements" but really its more
    7 non-research based impovements.}
     9
    810\CFA is a developing programming language. As such, there are partially or
    9 unimplemented features of the language (including several broken components)
    10 that I had to workaround while building an exception handling system largely in
    11 the \CFA language (some C components).  The following are a few of these
    12 issues, and once implemented/fixed, how they would affect the exception system.
     11unimplemented features (including several broken components)
     12that I had to work around while building the EHM largely in
     13the \CFA language (some C components). Below are a few of these issues
     14and how implementing/fixing them would affect the EHM.
     15In addition, there are some simple improvements that had no interesting
     16research attached to them but would make using the language easier.
    1317\begin{itemize}
    14 \item
    15 The implementation of termination is not portable because it includes
    16 hand-crafted assembly statements.
    17 The existing compilers cannot translate that for other platforms and those
    18 sections must be ported by hand to
    19 support more hardware architectures, such as the ARM processor.
    2018\item
    2119Due to a type-system problem, the catch clause cannot bind the exception to a
     
    2422result in little or no change in the exception system but simplify usage.
    2523\item
     24The @copy@ function in the exception virtual table is an adapter to address
     25some limitations in the \CFA copy constructor. If the copy constructor is
     26improved it can be used directly without the adapter.
     27\item
    2628Termination handlers cannot use local control-flow transfers, \eg by @break@,
    2729@return@, \etc. The reason is that current code generation hoists a handler
    28 into a nested function for convenience (versus assemble-code generation at the
    29 @try@ statement). Hence, when the handler runs, its code is not in the lexical
    30 scope of the @try@ statement, where the local control-flow transfers are
    31 meaningful.
     30into a nested function for convenience (versus assembly-code generation at the
     31try statement). Hence, when the handler runs, it can still access local
     32variables in the lexical scope of the try statement. Still, it does mean
     33that seemingly local control flow is not in fact local and crosses a function
     34boundary.
     35Making the termination handler's code within the surrounding
     36function would remove this limitation.
     37% Try blocks are much more difficult to do practically (requires our own
     38% assembly) and resumption handlers have some theoretical complexity.
    3239\item
    33 There is no detection of colliding unwinds. It is possible for clean-up code
    34 run during an unwind to trigger another unwind that escapes the clean-up code
    35 itself; such as a termination exception caught further down the stack or a
    36 cancellation. There do exist ways to handle this but currently they are not
    37 even detected and the first unwind will simply be forgotten, often leaving
     40There is no detection of colliding unwinds. It is possible for cleanup code
     41run during an unwind to trigger another unwind that escapes the cleanup code
     42itself, such as a termination exception caught further down the stack or a
     43cancellation. There do exist ways to handle this case, but currently there is
     44no detection and the first unwind will simply be forgotten, often leaving
    3845it in a bad state.
    3946\item
    40 Also the exception system did not have a lot of time to be tried and tested.
    41 So just letting people use the exception system more will reveal new
    42 quality of life upgrades that can be made with time.
     47Finally, the exception system has not had a lot of programmer testing.
     48More time with encouraged usage will reveal new
     49quality of life upgrades that can be made.
    4350\end{itemize}
    4451
     
    4754project, but was thrust upon it to do exception inheritance; hence, only
    4855minimal work is done. A draft for a complete virtual system is available but
    49 it is not finalized. A future \CFA project is to complete that work and then
     56not finalized. A future \CFA project is to complete that work and then
    5057update the exception system that uses the current version.
    5158
     
    5360exception traits. The most important one is an assertion to check one virtual
    5461type is a child of another. This check precisely captures many of the
    55 correctness requirements.
     62current ad-hoc correctness requirements.
     63
     64Other features of the virtual system could also remove some of the
     65special cases around exception virtual tables, such as the generation
     66of the @msg@ function.
    5667
    5768The full virtual system might also include other improvement like associated
    5869types to allow traits to refer to types not listed in their header. This
    5970feature allows exception traits to not refer to the virtual-table type
    60 explicitly, removing the need for the current interface macros.
     71explicitly, removing the need for the current interface macros,
     72such as @EHM_IS_EXCEPTION@.
    6173
    6274\section{Additional Raises}
    6375Several other kinds of exception raises were considered beyond termination
    64 (@throw@), resumption (@throwResume@), and reraise.
     76(@throw@), resumption (@throwResume@), and re-raise.
    6577
    6678The first is a non-local/concurrent raise providing asynchronous exceptions,
     
    7486Non-local/concurrent raise requires more
    7587coordination between the concurrency system
    76 and the exception system. Many of the interesting design decisions centre
     88and the exception system. Many of the interesting design decisions center
    7789around masking, \ie controlling which exceptions may be thrown at a stack. It
    7890would likely require more of the virtual system and would also effect how
     
    93105Checked exceptions make exceptions part of a function's type by adding an
    94106exception signature. An exception signature must declare all checked
    95 exceptions that could propagate from the function (either because they were
    96 raised inside the function or came from a sub-function). This improves safety
     107exceptions that could propagate from the function, either because they were
     108raised inside the function or came from a sub-function. This improves safety
    97109by making sure every checked exception is either handled or consciously
    98110passed on.
    99111
    100 However checked exceptions were never seriously considered for this project
    101 because they have significant trade-offs in usablity and code reuse in
     112Checked exceptions were never seriously considered for this project
     113because they have significant trade-offs in usability and code reuse in
    102114exchange for the increased safety.
    103115These trade-offs are most problematic when trying to pass exceptions through
    104116higher-order functions from the functions the user passed into the
    105117higher-order function. There are no well known solutions to this problem
    106 that were satisfactory for \CFA (which carries some of C's flexibility
    107 over safety design) so additional research is needed.
     118that were satisfactory for \CFA (which carries some of C's
     119flexibility-over-safety design) so additional research is needed.
    108120
    109121Follow-up work might add some form of checked exceptions to \CFA,
     
    128140Zero-cost resumptions is still an open problem. First, because libunwind does
    129141not support a successful-exiting stack-search without doing an unwind.
    130 Workarounds are possible but awkward. Ideally an extension to libunwind could
    131 be made, but that would either require separate maintenance or gain enough
    132 support to have it folded into the standard.
     142Workarounds are possible but awkward. Ideally, an extension to libunwind could
     143be made, but that would either require separate maintenance or gaining enough
     144support to have it folded into the official library itself.
    133145
    134 Also new techniques to skip previously searched parts of the stack need to be
     146Also, new techniques to skip previously searched parts of the stack need to be
    135147developed to handle the recursive resume problem and support advanced algebraic
    136148effects.
     
    158170to leave the handler.
    159171Currently, mimicking this behaviour in \CFA is possible by throwing a
    160 termination inside a resumption handler.
     172termination exception inside a resumption handler.
    161173
    162174% Maybe talk about the escape; and escape CONTROL_STMT; statements or how
  • doc/theses/andrew_beach_MMath/implement.tex

    rf95634e rb7fd9daf  
    1414\label{s:VirtualSystem}
    1515% Virtual table rules. Virtual tables, the pointer to them and the cast.
    16 While the \CFA virtual system currently has only one public feature, virtual
    17 cast (see the virtual cast feature \vpageref{p:VirtualCast}),
    18 substantial structure is required to support it,
     16While the \CFA virtual system currently has only two public features, virtual
     17cast and virtual tables,
     18substantial structure is required to support them,
    1919and provide features for exception handling and the standard library.
    2020
    2121\subsection{Virtual Type}
    22 Virtual types only have one change to their structure: the addition of a
    23 pointer to the virtual table, which is called the \emph{virtual-table pointer}.
    24 Internally, the field is called \snake{virtual_table}.
    25 The field is fixed after construction. It is always the first field in the
     22A virtual type~(see \autoref{s:virtuals}) has a pointer to a virtual table,
     23called the \emph{virtual-table pointer},
     24which binds each instance of a virtual type to a virtual table.
     25Internally, the field is called \snake{virtual_table}
     26and is fixed after construction.
     27This pointer is also the table's id and how the system accesses the
     28virtual table and the virtual members there.
     29It is always the first field in the
    2630structure so that its location is always known.
    27 \todo{Talk about constructors for virtual types (after they are working).}
    28 
    29 The virtual table pointer binds an instance of a virtual type
    30 to a virtual table.
    31 The pointer is also the table's id and how the system accesses the
    32 virtual table and the virtual members there.
    33 
    34 \subsection{Type Id}
    35 Every virtual type has a unique id.
    36 Type ids can be compared for equality,
    37 which checks if the types reperented are the same,
    38 or used to access the type's type information.
    39 The type information currently is only the parent's type id or, if the
     31
     32% We have no special rules for these constructors.
     33Virtual table pointers are passed to the constructors of virtual types
     34as part of field-by-field construction.
     35
     36\subsection{Type ID}
     37Every virtual type has a unique ID.
     38These are used in type equality, to check if the representation of two values
     39are the same, and to access the type's type information.
     40This uniqueness means across a program composed of multiple translation
     41units (TU), not uniqueness across all programs or even across multiple
     42processes on the same machine.
     43
     44Our approach for program uniqueness is using a static declaration for each
     45type ID, where the run-time storage address of that variable is guaranteed to
     46be unique during program execution.
     47The type ID storage can also be used for other purposes,
     48and is used for type information.
     49
     50The problem is that a type ID may appear in multiple TUs that compose a
     51program (see \autoref{ss:VirtualTable}), so the initial solution would seem
     52to be make it external in each translation unit. However, the type ID must
     53have a declaration in (exactly) one of the TUs to create the storage.
     54No other declaration related to the virtual type has this property, so doing
     55this through standard C declarations would require the user to do it manually.
     56
     57Instead, the linker is used to handle this problem.
     58% I did not base anything off of C++17; they are solving the same problem.
     59A new feature has been added to \CFA for this purpose, the special attribute
     60\snake{cfa_linkonce}, which uses the special section @.gnu.linkonce@.
     61When used as a prefix (\eg @.gnu.linkonce.example@), the linker does
     62not combine these sections, but instead discards all but one with the same
     63full name.
     64
     65So, each type ID must be given a unique section name with the \snake{linkonce}
     66prefix. Luckily, \CFA already has a way to get unique names, the name mangler.
     67For example, this could be written directly in \CFA:
     68\begin{cfa}
     69__attribute__((cfa_linkonce)) void f() {}
     70\end{cfa}
     71This is translated to:
     72\begin{cfa}
     73__attribute__((section(".gnu.linkonce._X1fFv___1"))) void _X1fFv___1() {}
     74\end{cfa}
     75This is done internally to access the name mangler.
     76This attribute is useful for other purposes, any other place a unique
     77instance required, and should eventually be made part of a public and
     78stable feature in \CFA.
     79
     80\subsection{Type Information}
     81
     82There is data stored at the type ID's declaration, the type information.
     83The type information currently is only the parent's type ID or, if the
    4084type has no parent, the null pointer.
    41 
    42 The id's are implemented as pointers to the type's type information instance.
    43 Dereferencing the pointer gets the type information.
    44 The ancestors of a virtual type are found by traversing type ids through
     85The ancestors of a virtual type are found by traversing type IDs through
    4586the type information.
    46 The information pushes the issue of creating a unique value (for
    47 the type id) to the problem of creating a unique instance (for type
    48 information), which the linker can solve.
    49 
    50 The advanced linker support is used here to avoid having to create
    51 a new declaration to attach this data to.
    52 With C/\CFA's header/implementation file divide for something to appear
    53 exactly once it must come from a declaration that appears in exactly one
    54 implementation file; the declarations in header files may exist only once
    55 they can be included in many different translation units.
    56 Therefore, structure's declaration will not work.
    57 Neither will attaching the type information to the virtual table -- although
    58 a vtable declarations are in implemention files they are not unique, see
    59 \autoref{ss:VirtualTable}.
    60 Instead the same type information is generated multiple times and then
    61 the new attribute \snake{cfa_linkone} is used to removed duplicates.
     87An example using helper macros looks like:
     88\begin{cfa}
     89struct INFO_TYPE(TYPE) {
     90        INFO_TYPE(PARENT) const * parent;
     91};
     92
     93__attribute__((cfa_linkonce))
     94INFO_TYPE(TYPE) const INFO_NAME(TYPE) = {
     95        &INFO_NAME(PARENT),
     96};
     97\end{cfa}
    6298
    6399Type information is constructed as follows:
    64 \begin{enumerate}
     100\begin{enumerate}[nosep]
    65101\item
    66 Use the type's name to generate a name for the type information structure.
    67 This is saved so it may be reused.
     102Use the type's name to generate a name for the type information structure,
     103which is saved so it can be reused.
    68104\item
    69105Generate a new structure definition to store the type
    70 information. The layout is the same in each case, just the parent's type id,
     106information. The layout is the same in each case, just the parent's type ID,
    71107but the types used change from instance to instance.
    72 The generated name is used for both this structure and, if relivant, the
     108The generated name is used for both this structure and, if relevant, the
    73109parent pointer.
    74110If the virtual type is polymorphic then the type information structure is
    75111polymorphic as well, with the same polymorphic arguments.
    76112\item
    77 A seperate name for instances is generated from the type's name.
     113A separate name for instances is generated from the type's name.
    78114\item
    79 The definition is generated and initialised.
    80 The parent id is set to the null pointer or to the address of the parent's
     115The definition is generated and initialized.
     116The parent ID is set to the null pointer or to the address of the parent's
    81117type information instance. Name resolution handles the rest.
    82118\item
    83119\CFA's name mangler does its regular name mangling encoding the type of
    84 the declaration into the instance name. This gives a completely unique name
     120the declaration into the instance name.
     121This process gives a completely unique name
    85122including different instances of the same polymorphic type.
    86123\end{enumerate}
    87 \todo{The list is making me realise, some of this isn't ordered.}
    88124
    89125Writing that code manually, with helper macros for the early name mangling,
     
    100136\end{cfa}
    101137
     138\begin{comment}
    102139\subsubsection{\lstinline{cfa\_linkonce} Attribute}
    103 % I just realised: This is an extension of the inline keyword.
     140% I just realized: This is an extension of the inline keyword.
    104141% An extension of C's at least, it is very similar to C++'s.
    105142Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}.
     
    113150file as if it was a forward declaration, except no definition is required.
    114151
    115 This technique is used for type-id instances. A link-once definition is
     152This technique is used for type ID instances. A link-once definition is
    116153generated each time the structure is seen. This will result in multiple
    117154copies but the link-once attribute ensures all but one are removed for a
     
    126163everything that comes after the special prefix, then only one is used
    127164and the other is discarded.
     165\end{comment}
    128166
    129167\subsection{Virtual Table}
    130168\label{ss:VirtualTable}
    131 Each virtual type has a virtual table type that stores its type id and
     169Each virtual type has a virtual table type that stores its type ID and
    132170virtual members.
    133 Each virtual type instance is bound to a table instance that is filled with
    134 the values of virtual members.
    135 Both the layout of the fields and their value are decided by the rules given
     171An instance of a virtual type is bound to a virtual table instance,
     172which have the values of the virtual members.
     173Both the layout of the fields (in the virtual table type)
     174and their value (in the virtual table instance) are decided by the rules given
    136175below.
    137176
    138 The layout always comes in three parts.
    139 \todo{Add labels to the virtual table layout figure.}
    140 The first section is just the type id at the head of the table. It is always
     177The layout always comes in three parts (see \autoref{f:VirtualTableLayout}).
     178The first section is just the type ID at the head of the table. It is always
    141179there to ensure that it can be found even when the accessing code does not
    142180know which virtual type it has.
    143 The second section are all the virtual members of the parent, in the same
     181The second section is all the virtual members of the parent, in the same
    144182order as they appear in the parent's virtual table. Note that the type may
    145 change slightly as references to the ``this" will change. This is limited to
     183change slightly as references to the ``this" change. This is limited to
    146184inside pointers/references and via function pointers so that the size (and
    147185hence the offsets) are the same.
     
    150188
    151189\begin{figure}
     190\begin{center}
    152191\input{vtable-layout}
     192\end{center}
    153193\caption{Virtual Table Layout}
    154194\label{f:VirtualTableLayout}
    155 \todo*{Improve the Virtual Table Layout diagram.}
    156195\end{figure}
    157196
     
    160199This, combined with the fixed offset to the virtual table pointer, means that
    161200for any virtual type, it is always safe to access its virtual table and,
    162 from there, it is safe to check the type id to identify the exact type of the
     201from there, it is safe to check the type ID to identify the exact type of the
    163202underlying object, access any of the virtual members and pass the object to
    164203any of the method-like virtual members.
     
    168207the context of the declaration.
    169208
    170 The type id is always fixed; with each virtual table type having
    171 exactly one possible type id.
     209The type ID is always fixed, with each virtual table type having
     210exactly one possible type ID.
    172211The virtual members are usually filled in by type resolution.
    173212The best match for a given name and type at the declaration site is used.
    174213There are two exceptions to that rule: the @size@ field, the type's size,
    175 is set using a @sizeof@ expression and the @align@ field, the
     214is set using a @sizeof@ expression, and the @align@ field, the
    176215type's alignment, is set using an @alignof@ expression.
    177216
    178 \subsubsection{Concurrency Integration}
     217Most of these tools are already inside the compiler. Using simple
     218code transformations early on in compilation allows most of that work to be
     219handed off to the existing tools. \autoref{f:VirtualTableTransformation}
     220shows an example transformation; this example shows an exception virtual table.
     221It also shows the transformation on the full declaration.
     222For a forward declaration, the @extern@ keyword is preserved and the
     223initializer is not added.
     224
     225\begin{figure}[htb]
     226\begin{cfa}
     227vtable(example_type) example_name;
     228\end{cfa}
     229\transformline
     230% Check mangling.
     231\begin{cfa}
     232const struct example_type_vtable example_name = {
     233        .__cfavir_typeid : &__cfatid_example_type,
     234        .size : sizeof(example_type),
     235        .copy : copy,
     236        .^?{} : ^?{},
     237        .msg : msg,
     238};
     239\end{cfa}
     240\caption{Virtual Table Transformation}
     241\label{f:VirtualTableTransformation}
     242\end{figure}
     243
     244\subsection{Concurrency Integration}
    179245Coroutines and threads need instances of @CoroutineCancelled@ and
    180246@ThreadCancelled@ respectively to use all of their functionality. When a new
     
    183249at the definition of the main function.
    184250
    185 This is showned through code re-writing in
    186 \autoref{f:ConcurrencyTypeTransformation} and
    187 \autoref{f:ConcurrencyMainTransformation}.
    188 In both cases the original declaration is not modified,
     251These transformations are shown through code re-writing in
     252\autoref{f:CoroutineTypeTransformation} and
     253\autoref{f:CoroutineMainTransformation}.
     254Threads use the same pattern, with some names and types changed.
     255In both cases, the original declaration is not modified,
    189256only new ones are added.
    190257
    191 \begin{figure}
     258\begin{figure}[htb]
    192259\begin{cfa}
    193260coroutine Example {
     
    207274extern CoroutineCancelled_vtable & _default_vtable;
    208275\end{cfa}
    209 \caption{Concurrency Type Transformation}
    210 \label{f:ConcurrencyTypeTransformation}
     276\caption{Coroutine Type Transformation}
     277\label{f:CoroutineTypeTransformation}
    211278\end{figure}
    212279
    213 \begin{figure}
     280\begin{figure}[htb]
    214281\begin{cfa}
    215282void main(Example & this) {
     
    229296        &_default_vtable_object_declaration;
    230297\end{cfa}
    231 \caption{Concurrency Main Transformation}
    232 \label{f:ConcurrencyMainTransformation}
     298\caption{Coroutine Main Transformation}
     299\label{f:CoroutineMainTransformation}
    233300\end{figure}
    234301
     
    242309\begin{cfa}
    243310void * __cfa__virtual_cast(
    244         struct __cfavir_type_td parent,
    245         struct __cfavir_type_id const * child );
    246 \end{cfa}
    247 The type id of target type of the virtual cast is passed in as @parent@ and
     311        struct __cfavir_type_id * parent,
     312        struct __cfavir_type_id * const * child );
     313\end{cfa}
     314The type ID for the target type of the virtual cast is passed in as
     315@parent@ and
    248316the cast target is passed in as @child@.
    249 
    250 For generated C code wraps both arguments and the result with type casts.
     317The generated C code wraps both arguments and the result with type casts.
    251318There is also an internal check inside the compiler to make sure that the
    252319target type is a virtual type.
     
    255322The virtual cast either returns the original pointer or the null pointer
    256323as the new type.
    257 So the function does the parent check and returns the appropriate value.
    258 The parent check is a simple linear search of child's ancestors using the
     324The function does the parent check and returns the appropriate value.
     325The parent check is a simple linear search of the child's ancestors using the
    259326type information.
    260327
    261328\section{Exceptions}
    262 % Anything about exception construction.
     329% The implementation of exception types.
     330
     331Creating exceptions can be roughly divided into two parts:
     332the exceptions themselves and the virtual system interactions.
     333
     334Creating an exception type is just a matter of prepending the field 
     335with the virtual table pointer to the list of the fields
     336(see \autoref{f:ExceptionTypeTransformation}).
     337
     338\begin{figure}[htb]
     339\begin{cfa}
     340exception new_exception {
     341        // EXISTING FIELDS
     342};
     343\end{cfa}
     344\transformline
     345\begin{cfa}
     346struct new_exception {
     347        struct new_exception_vtable const * virtual_table;
     348        // EXISTING FIELDS
     349};
     350\end{cfa}
     351\caption{Exception Type Transformation}
     352\label{f:ExceptionTypeTransformation}
     353\end{figure}
     354
     355The integration between exceptions and the virtual system is a bit more
     356complex simply because of the nature of the virtual system prototype.
     357The primary issue is that the virtual system has no way to detect when it
     358should generate any of its internal types and data. This is handled by
     359the exception code, which tells the virtual system when to generate
     360its components.
     361
     362All types associated with a virtual type,
     363the types of the virtual table and the type ID,
     364are generated when the virtual type (the exception) is first found.
     365The type ID (the instance) is generated with the exception, if it is
     366a monomorphic type.
     367However, if the exception is polymorphic, then a different type ID has to
     368be generated for every instance. In this case, generation is delayed
     369until a virtual table is created.
     370% There are actually some problems with this, which is why it is not used
     371% for monomorphic types.
     372When a virtual table is created and initialized, two functions are created
     373to fill in the list of virtual members.
     374The first is the @copy@ function that adapts the exception's copy constructor
     375to work with pointers, avoiding some issues with the current copy constructor
     376interface.
     377Second is the @msg@ function that returns a C-string with the type's name,
     378including any polymorphic parameters.
    263379
    264380\section{Unwinding}
     
    274390stack. On function entry and return, unwinding is handled directly by the
    275391call/return code embedded in the function.
    276 In many cases, the position of the instruction pointer (relative to parameter
    277 and local declarations) is enough to know the current size of the stack
    278 frame.
    279 
     392
     393% Discussing normal stack unwinding:
    280394Usually, the stack-frame size is known statically based on parameter and
    281 local variable declarations. Even with dynamic stack-size, the information
     395local variable declarations. Even for a dynamic stack-size, the information
    282396to determine how much of the stack has to be removed is still contained
    283397within the function.
     
    285399bumping the hardware stack-pointer up or down as needed.
    286400Constructing/destructing values within a stack frame has
    287 a similar complexity but can add additional work and take longer.
    288 
    289 Unwinding across multiple stack frames is more complex because that
     401a similar complexity but larger constants.
     402
     403% Discussing multiple frame stack unwinding:
     404Unwinding across multiple stack frames is more complex, because that
    290405information is no longer contained within the current function.
    291 With seperate compilation a function has no way of knowing what its callers
    292 are so it can't know how large those frames are.
    293 Without altering the main code path it is also hard to pass that work off
    294 to the caller.
    295 
    296 The traditional unwinding mechanism for C is implemented by saving a snap-shot
    297 of a function's state with @setjmp@ and restoring that snap-shot with
     406With separate compilation,
     407a function does not know its callers nor their frame layout.
     408Even using the return address, that information is encoded in terms of
     409actions in code, intermixed with the actions required to finish the function.
     410Without changing the main code path it is impossible to select one of those
     411two groups of actions at the return site.
     412
     413The traditional unwinding mechanism for C is implemented by saving a snapshot
     414of a function's state with @setjmp@ and restoring that snapshot with
    298415@longjmp@. This approach bypasses the need to know stack details by simply
    299 reseting to a snap-shot of an arbitrary but existing function frame on the
    300 stack. It is up to the programmer to ensure the snap-shot is valid when it is
    301 reset and that all required clean-up from the unwound stacks is performed.
    302 This approach is fragile and requires extra work in the surrounding code.
    303 
    304 With respect to the extra work in the surounding code,
    305 many languages define clean-up actions that must be taken when certain
    306 sections of the stack are removed. Such as when the storage for a variable
    307 is removed from the stack or when a try statement with a finally clause is
     416resetting to a snapshot of an arbitrary but existing function frame on the
     417stack. It is up to the programmer to ensure the snapshot is valid when it is
     418reset and that all required cleanup from the unwound stacks is performed.
     419Because it does not automate or check any of this cleanup,
     420it can be easy to make mistakes and always must be handled manually.
     421
     422With respect to the extra work in the surrounding code,
     423many languages define cleanup actions that must be taken when certain
     424sections of the stack are removed, such as when the storage for a variable
     425is removed from the stack, possibly requiring a destructor call,
     426or when a try statement with a finally clause is
    308427(conceptually) popped from the stack.
    309 None of these should be handled by the user --- that would contradict the
    310 intention of these features --- so they need to be handled automatically.
     428None of these cases should be handled by the user -- that would contradict the
     429intention of these features -- so they need to be handled automatically.
    311430
    312431To safely remove sections of the stack, the language must be able to find and
    313 run these clean-up actions even when removing multiple functions unknown at
     432run these cleanup actions even when removing multiple functions unknown at
    314433the beginning of the unwinding.
    315434
     
    317436library that provides tools for stack walking, handler execution, and
    318437unwinding. What follows is an overview of all the relevant features of
    319 libunwind needed for this work, and how \CFA uses them to implement exception
    320 handling.
     438libunwind needed for this work.
     439Following that is the description of the \CFA code that uses libunwind
     440to implement termination.
    321441
    322442\subsection{libunwind Usage}
     
    348468In plain C (which \CFA currently compiles down to) this
    349469flag only handles the cleanup attribute:
     470%\label{code:cleanup}
    350471\begin{cfa}
    351472void clean_up( int * var ) { ... }
     
    355476in this case @clean_up@, run when the variable goes out of scope.
    356477This feature is enough to mimic destructors,
    357 but not try statements which can effect
     478but not try statements that affect
    358479the unwinding.
    359480
    360481To get full unwinding support, all of these features must be handled directly
    361 in assembly and assembler directives; partiularly the cfi directives
     482in assembly and assembler directives; particularly the cfi directives
    362483\snake{.cfi_lsda} and \snake{.cfi_personality}.
    363484
     
    399520@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
    400521the cleanup phase and uses a different means to decide when to stop
    401 (see \vref{s:ForcedUnwind}).
     522(see \autoref{s:ForcedUnwind}).
    402523\end{enumerate}
    403524
    404525The @exception_class@ argument is a copy of the
    405526\code{C}{exception}'s @exception_class@ field,
    406 which is a number that identifies the exception handling mechanism
     527which is a number that identifies the EHM
    407528that created the exception.
    408529
     
    410531provided storage object. It has two public fields: the @exception_class@,
    411532which is described above, and the @exception_cleanup@ function.
    412 The clean-up function is used by the EHM to clean-up the exception, if it
     533The cleanup function is used by the EHM to clean up the exception. If it
    413534should need to be freed at an unusual time, it takes an argument that says
    414535why it had to be cleaned up.
     
    432553of the most recent stack frame. It continues to call personality functions
    433554traversing the stack from newest to oldest until a function finds a handler or
    434 the end of the stack is reached. In the latter case, raise exception returns
    435 @_URC_END_OF_STACK@.
    436 
    437 Second, when a handler is matched, raise exception moves to the clean-up
    438 phase and walks the stack a second time.
     555the end of the stack is reached. In the latter case,
     556@_Unwind_RaiseException@ returns @_URC_END_OF_STACK@.
     557
     558Second, when a handler is matched, @_Unwind_RaiseException@
     559moves to the cleanup phase and walks the stack a second time.
    439560Once again, it calls the personality functions of each stack frame from newest
    440561to oldest. This pass stops at the stack frame containing the matching handler.
    441 If that personality function has not install a handler, it is an error.
    442 
    443 If an error is encountered, raise exception returns either
     562If that personality function has not installed a handler, it is an error.
     563
     564If an error is encountered, @_Unwind_RaiseException@ returns either
    444565@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
    445566error occurred.
     
    452573        _Unwind_Stop_Fn, void *);
    453574\end{cfa}
    454 It also unwinds the stack but it does not use the search phase. Instead another
     575It also unwinds the stack but it does not use the search phase. Instead,
     576another
    455577function, the stop function, is used to stop searching. The exception is the
    456 same as the one passed to raise exception. The extra arguments are the stop
     578same as the one passed to @_Unwind_RaiseException@.
     579The extra arguments are the stop
    457580function and the stop parameter. The stop function has a similar interface as a
    458581personality function, except it is also passed the stop parameter.
     
    494617needs its own exception context.
    495618
    496 The exception context should be retrieved by calling the function
     619The current exception context should be retrieved by calling the function
    497620\snake{this_exception_context}.
    498621For sequential execution, this function is defined as
     
    519642The first step of a termination raise is to copy the exception into memory
    520643managed by the exception system. Currently, the system uses @malloc@, rather
    521 than reserved memory or the stack top. The exception handling mechanism manages
     644than reserved memory or the stack top. The EHM manages
    522645memory for the exception as well as memory for libunwind and the system's own
    523646per-exception storage.
     
    554677\newsavebox{\stackBox}
    555678\begin{lrbox}{\codeBox}
    556 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     679\begin{cfa}
    557680unsigned num_exceptions = 0;
    558681void throws() {
     
    573696    throws();
    574697}
    575 \end{lstlisting}
     698\end{cfa}
    576699\end{lrbox}
    577700
    578701\begin{lrbox}{\stackBox}
    579702\begin{lstlisting}
    580 | try-finally
    581 | try-catch (Example)
     703| finally block (Example)
     704| try block
    582705throws()
    583 | try-finally
    584 | try-catch (Example)
     706| finally block (Example)
     707| try block
    585708throws()
    586 | try-finally
    587 | try-catch (Example)
     709| finally block (Example)
     710| try block
    588711throws()
    589712main()
     
    598721\label{f:MultipleExceptions}
    599722\end{figure}
    600 \todo*{Work on multiple exceptions code sample.}
    601723
    602724All exceptions are stored in nodes, which are then linked together in lists
    603725one list per stack, with the
    604726list head stored in the exception context. Within each linked list, the most
    605 recently thrown exception is at the head followed by older thrown
     727recently thrown exception is at the head, followed by older thrown
    606728exceptions. This format allows exceptions to be thrown, while a different
    607729exception is being handled. The exception at the head of the list is currently
     
    614736exception into managed memory. After the exception is handled, the free
    615737function is used to clean up the exception and then the entire node is
    616 passed to free, returning the memory back to the heap.
     738passed to @free@, returning the memory back to the heap.
    617739
    618740\subsection{Try Statements and Catch Clauses}
    619741The try statement with termination handlers is complex because it must
    620 compensate for the C code-generation versus
     742compensate for the C code-generation versus proper
    621743assembly-code generated from \CFA. Libunwind
    622744requires an LSDA and personality function for control to unwind across a
    623745function. The LSDA in particular is hard to mimic in generated C code.
    624746
    625 The workaround is a function called @__cfaehm_try_terminate@ in the standard
    626 library. The contents of a try block and the termination handlers are converted
    627 into functions. These are then passed to the try terminate function and it
    628 calls them.
     747The workaround is a function called \snake{__cfaehm_try_terminate} in the
     748standard \CFA library. The contents of a try block and the termination
     749handlers are converted into nested functions. These are then passed to the
     750try terminate function and it calls them, appropriately.
    629751Because this function is known and fixed (and not an arbitrary function that
    630 happens to contain a try statement), the LSDA can be generated ahead
     752happens to contain a try statement), its LSDA can be generated ahead
    631753of time.
    632754
    633 Both the LSDA and the personality function are set ahead of time using
     755Both the LSDA and the personality function for \snake{__cfaehm_try_terminate}
     756are set ahead of time using
    634757embedded assembly. This assembly code is handcrafted using C @asm@ statements
    635758and contains
    636 enough information for a single try statement the function repersents.
     759enough information for the single try statement the function represents.
    637760
    638761The three functions passed to try terminate are:
    639762\begin{description}
    640 \item[try function:] This function is the try block, it is where all the code
     763\item[try function:] This function is the try block. It is where all the code
    641764from inside the try block is placed. It takes no parameters and has no
    642765return value. This function is called during regular execution to run the try
     
    646769decides if a catch clause matches the termination exception. It is constructed
    647770from the conditional part of each handler and runs each check, top to bottom,
    648 in turn, first checking to see if the exception type matches and then if the
    649 condition is true. It takes a pointer to the exception and returns 0 if the
    650 exception is not handled here. Otherwise the return value is the id of the
     771in turn, to see if the exception matches this handler.
     772The match is performed in two steps: first, a virtual cast is used to check
     773if the raised exception is an instance of the declared exception type or
     774one of its descendant types, and then the condition is evaluated, if
     775present.
     776The match function takes a pointer to the exception and returns 0 if the
     777exception is not handled here. Otherwise, the return value is the ID of the
    651778handler that matches the exception.
    652779
     
    659786\end{description}
    660787All three functions are created with GCC nested functions. GCC nested functions
    661 can be used to create closures,
    662 in other words functions that can refer to the state of other
    663 functions on the stack. This approach allows the functions to refer to all the
     788can be used to create closures;
     789in other words,
     790functions that can refer to variables in their lexical scope even though
     791those variables are part of a different function.
     792This approach allows the functions to refer to all the
    664793variables in scope for the function containing the @try@ statement. These
    665794nested functions and all other functions besides @__cfaehm_try_terminate@ in
     
    669798
    670799\autoref{f:TerminationTransformation} shows the pattern used to transform
    671 a \CFA try statement with catch clauses into the approprate C functions.
    672 \todo{Explain the Termination Transformation figure.}
     800a \CFA try statement with catch clauses into the appropriate C functions.
    673801
    674802\begin{figure}
     
    728856\caption{Termination Transformation}
    729857\label{f:TerminationTransformation}
    730 \todo*{Improve (compress?) Termination Transformations.}
    731858\end{figure}
    732859
     
    738865Instead of storing the data in a special area using assembly,
    739866there is just a linked list of possible handlers for each stack,
    740 with each node on the list reperenting a try statement on the stack.
     867with each node on the list representing a try statement on the stack.
    741868
    742869The head of the list is stored in the exception context.
     
    744871to the head of the list.
    745872Instead of traversing the stack, resumption handling traverses the list.
    746 At each node, the EHM checks to see if the try statement the node repersents
     873At each node, the EHM checks to see if the try statement the node represents
    747874can handle the exception. If it can, then the exception is handled and
    748 the operation finishes, otherwise the search continues to the next node.
     875the operation finishes; otherwise, the search continues to the next node.
    749876If the search reaches the end of the list without finding a try statement
    750 that can handle the exception, the default handler is executed and the
    751 operation finishes.
     877with a handler clause
     878that can handle the exception, the default handler is executed.
     879If the default handler returns, control continues after the raise statement.
    752880
    753881Each node has a handler function that does most of the work.
    754882The handler function is passed the raised exception and returns true
    755883if the exception is handled and false otherwise.
    756 
    757884The handler function checks each of its internal handlers in order,
    758 top-to-bottom, until it funds a match. If a match is found that handler is
     885top-to-bottom, until it finds a match. If a match is found that handler is
    759886run, after which the function returns true, ignoring all remaining handlers.
    760887If no match is found the function returns false.
    761 The match is performed in two steps, first a virtual cast is used to see
    762 if the thrown exception is an instance of the declared exception or one of
    763 its descendant type, then check to see if passes the custom predicate if one
    764 is defined. This ordering gives the type guarantee used in the predicate.
     888The match is performed in two steps. First a virtual cast is used to see
     889if the raised exception is an instance of the declared exception type or one
     890of its descendant types, if so, then the second step is to see if the
     891exception passes the custom predicate
     892if one is defined.
     893% You need to make sure the type is correct before running the predicate
     894% because the predicate can depend on that.
    765895
    766896\autoref{f:ResumptionTransformation} shows the pattern used to transform
    767 a \CFA try statement with catch clauses into the approprate C functions.
    768 \todo{Explain the Resumption Transformation figure.}
     897a \CFA try statement with catchResume clauses into the appropriate
     898C functions.
    769899
    770900\begin{figure}
     
    807937\caption{Resumption Transformation}
    808938\label{f:ResumptionTransformation}
    809 \todo*{Improve (compress?) Resumption Transformations.}
    810939\end{figure}
    811940
    812941% Recursive Resumption Stuff:
    813942\autoref{f:ResumptionMarking} shows search skipping
    814 (see \vpageref{s:ResumptionMarking}), which ignores parts of
     943(see \autoref{s:ResumptionMarking}), which ignores parts of
    815944the stack
    816 already examined, is accomplished by updating the front of the list as the
    817 search continues. Before the handler at a node is called, the head of the list
     945already examined, and is accomplished by updating the front of the list as
     946the search continues.
     947Before the handler is called at a matching node, the head of the list
    818948is updated to the next node of the current node. After the search is complete,
    819949successful or not, the head of the list is reset.
     
    822952been checked are not on the list while a handler is run. If a resumption is
    823953thrown during the handling of another resumption, the active handlers and all
    824 the other handler checked up to this point are not checked again.
     954the other handlers checked up to this point are not checked again.
    825955% No paragraph?
    826956This structure also supports new handlers added while the resumption is being
    827957handled. These are added to the front of the list, pointing back along the
    828 stack --- the first one points over all the checked handlers ---
     958stack -- the first one points over all the checked handlers --
    829959and the ordering is maintained.
    830960
    831961\begin{figure}
     962\centering
    832963\input{resumption-marking}
    833964\caption{Resumption Marking}
    834965\label{f:ResumptionMarking}
    835 \todo*{Label Resumption Marking to aid clarity.}
    836966\end{figure}
    837967
     
    851981\section{Finally}
    852982% Uses destructors and GCC nested functions.
    853 A finally clause is placed into a GCC nested-function with a unique name,
    854 and no arguments or return values.
    855 This nested function is then set as the cleanup
    856 function of an empty object that is declared at the beginning of a block placed
    857 around the context of the associated @try@ statement.
    858 
    859 The rest is handled by GCC. The try block and all handlers are inside this
    860 block. At completion, control exits the block and the empty object is cleaned
     983
     984%\autoref{code:cleanup}
     985A finally clause is handled by converting it into a once-off destructor.
     986The code inside the clause is placed into a GCC nested-function
     987with a unique name, and no arguments or return values.
     988This nested function is
     989then set as the cleanup function of an empty object that is declared at the
     990beginning of a block placed around the context of the associated try
     991statement, as shown in \autoref{f:FinallyTransformation}.
     992
     993\begin{figure}
     994\begin{cfa}
     995try {
     996        // TRY BLOCK
     997} finally {
     998        // FINALLY BLOCK
     999}
     1000\end{cfa}
     1001
     1002\transformline
     1003
     1004\begin{cfa}
     1005{
     1006        void finally(void *__hook){
     1007                // FINALLY BLOCK
     1008        }
     1009        __attribute__ ((cleanup(finally)))
     1010        struct __cfaehm_cleanup_hook __finally_hook;
     1011        {
     1012                // TRY BLOCK
     1013        }
     1014}
     1015\end{cfa}
     1016
     1017\caption{Finally Transformation}
     1018\label{f:FinallyTransformation}
     1019\end{figure}
     1020
     1021The rest is handled by GCC.
     1022The TRY BLOCK
     1023contains the try block itself as well as all code generated for handlers.
     1024Once that code has completed,
     1025control exits the block and the empty object is cleaned
    8611026up, which runs the function that contains the finally code.
    8621027
     
    8641029% Stack selections, the three internal unwind functions.
    8651030
    866 Cancellation also uses libunwind to do its stack traversal and unwinding,
    867 however it uses a different primary function: @_Unwind_ForcedUnwind@. Details
    868 of its interface can be found in the Section~\vref{s:ForcedUnwind}.
     1031Cancellation also uses libunwind to do its stack traversal and unwinding.
     1032However, it uses a different primary function: @_Unwind_ForcedUnwind@. Details
     1033of its interface can be found in Section~\vref{s:ForcedUnwind}.
    8691034
    8701035The first step of cancellation is to find the cancelled stack and its type:
     
    8871052passed to the forced-unwind function. The general pattern of all three stop
    8881053functions is the same: continue unwinding until the end of stack and
    889 then preform the appropriate transfer.
     1054then perform the appropriate transfer.
    8901055
    8911056For main stack cancellation, the transfer is just a program abort.
  • doc/theses/andrew_beach_MMath/intro.tex

    rf95634e rb7fd9daf  
    1111
    1212% Now take a step back and explain what exceptions are generally.
     13Exception handling provides dynamic inter-function control flow.
    1314A language's EHM is a combination of language syntax and run-time
    14 components that are used to construct, raise, and handle exceptions,
    15 including all control flow.
    16 Exceptions are an active mechanism for replacing passive error/return codes and return unions (Go and Rust).
    17 Exception handling provides dynamic inter-function control flow.
     15components that construct, raise, propagate and handle exceptions,
     16to provide all of that control flow.
    1817There are two forms of exception handling covered in this thesis:
    1918termination, which acts as a multi-level return,
    2019and resumption, which is a dynamic function call.
    21 % PAB: Maybe this sentence was suppose to be deleted?
    22 Termination handling is much more common,
    23 to the extent that it is often seen as the only form of handling.
    24 % PAB: I like this sentence better than the next sentence.
    25 % This separation is uncommon because termination exception handling is so
    26 % much more common that it is often assumed.
    27 % WHY: Mention other forms of continuation and \cite{CommonLisp} here?
    28 
    29 Exception handling relies on the concept of nested functions to create handlers that deal with exceptions.
     20% About other works:
     21Often, when this separation is not made, termination exceptions are assumed
     22as they are more common and may be the only form of handling provided in
     23a language.
     24
     25All types of exception handling link a raise with a handler.
     26Both operations are usually language primitives, although raises can be
     27treated as a function that takes an exception argument.
     28Handlers are more complex, as they are added to and removed from the stack
     29during execution, must specify what they can handle and must give the code to
     30handle the exception.
     31
     32Exceptions work with different execution models but for the descriptions
     33that follow a simple call stack, with functions added and removed in a
     34first-in-last-out order, is assumed.
     35
     36Termination exception handling searches the stack for the handler, then
     37unwinds the stack to where the handler was found before calling it.
     38The handler is run inside the function that defined it and when it finishes
     39it returns control to that function.
    3040\begin{center}
    31 \begin{tabular}[t]{ll}
    32 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt,language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    33 void f( void (*hp)() ) {
    34         hp();
    35 }
    36 void g( void (*hp)() ) {
    37         f( hp );
    38 }
    39 void h( int @i@, void (*hp)() ) {
    40         void @handler@() { // nested
    41                 printf( "%d\n", @i@ );
    42         }
    43         if ( i == 1 ) hp = handler;
    44         if ( i > 0 ) h( i - 1, hp );
    45         else g( hp );
    46 }
    47 h( 2, 0 );
    48 \end{lstlisting}
    49 &
    50 \raisebox{-0.5\totalheight}{\input{handler}}
    51 \end{tabular}
     41%\input{termination}
     42%
     43%\medskip
     44\input{termhandle.pstex_t}
     45% I hate these diagrams, but I can't access xfig to fix them and they are
     46% better than the alternative.
    5247\end{center}
    53 The nested function @handler@ in the second stack frame is explicitly passed to function @f@.
    54 When this handler is called in @f@, it uses the parameter @i@ in the second stack frame, which is accessible by an implicit lexical-link pointer.
    55 Setting @hp@ in @h@ at different points in the recursion, results in invoking a different handler.
    56 Exception handling extends this idea by eliminating explicit handler passing, and instead, performing a stack search for a handler that matches some criteria (conditional dynamic call), and calls the handler at the top of the stack.
    57 It is the runtime search $O(N)$ that differentiates an EHM call (raise) from normal dynamic call $O(1)$ via a function or virtual-member pointer.
    58 
    59 Termination exception handling searches the stack for a handler, unwinds the stack to the frame containing the matching handler, and calling the handler at the top of the stack.
     48
     49Resumption exception handling searches the stack for a handler and then calls
     50it without removing any other stack frames.
     51The handler is run on top of the existing stack, often as a new function or
     52closure capturing the context in which the handler was defined.
     53After the handler has finished running, it returns control to the function
     54that preformed the raise, usually starting after the raise.
    6055\begin{center}
    61 \input{termination}
     56%\input{resumption}
     57%
     58%\medskip
     59\input{resumhandle.pstex_t}
     60% The other one.
    6261\end{center}
    63 Note, since the handler can reference variables in @h@, @h@ must remain on the stack for the handler call.
    64 After the handler returns, control continues after the lexical location of the handler in @h@ (static return)~\cite[p.~108]{Tennent77}.
    65 Unwinding allows recover to any previous
    66 function on the stack, skipping any functions between it and the
    67 function containing the matching handler.
    68 
    69 Resumption exception handling searches the stack for a handler, does \emph{not} unwind the stack to the frame containing the matching handler, and calls the handler at the top of the stack.
    70 \begin{center}
    71 \input{resumption}
    72 \end{center}
    73 After the handler returns, control continues after the resume in @f@ (dynamic return).
    74 Not unwinding allows fix up of the problem in @f@ by any previous function on the stack, without disrupting the current set of stack frames.
    7562
    7663Although a powerful feature, exception handling tends to be complex to set up
    77 and expensive to use
     64and expensive to use,
    7865so it is often limited to unusual or ``exceptional" cases.
    79 The classic example is error handling, where exceptions are used to
    80 remove error handling logic from the main execution path, while paying
     66The classic example is error handling; exceptions can be used to
     67remove error handling logic from the main execution path, and pay
    8168most of the cost only when the error actually occurs.
    8269
     
    8572The \CFA EHM implements all of the common exception features (or an
    8673equivalent) found in most other EHMs and adds some features of its own.
    87 The design of all the features had to be adapted to \CFA's feature set as
     74The design of all the features had to be adapted to \CFA's feature set, as
    8875some of the underlying tools used to implement and express exception handling
    8976in other languages are absent in \CFA.
    90 Still the resulting basic syntax resembles that of other languages:
    91 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
    92 @try@ {
     77Still, the resulting syntax resembles that of other languages:
     78\begin{cfa}
     79try {