Changeset 660665f


Ignore:
Timestamp:
Jun 29, 2021, 5:35:19 PM (7 months ago)
Author:
caparsons <caparson@…>
Branches:
jacob/cs343-translation, master, new-ast-unique-expr
Children:
dcad80a
Parents:
5a46e09 (diff), d02e547 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Files:
24 added
84 edited
1 moved

Legend:

Unmodified
Added
Removed
  • INSTALL

    r5a46e09 r660665f  
    1 cfa-cc: The Cforall->C Compiler System
     1cfa-cc: Cforall to C Trans-compiler
    22======================================
    33
    44Cforall is built using GNU Make and the GNU Autoconf system.  It also requires
    5 g++ version >= 4.6, bison and flex.  On systems where GNU Make is the default
     5g++ version >= 6, bison and flex.  On systems where GNU Make is the default
    66make, the system is built by entering the commands:
    77
    8 For devs using the root git:
     8For developers using the root git:
    99
    10   ./autogen.sh
    11         ./configure
    12         make
    13         make install
     10  $ ./autogen.sh
     11  $ ./configure [ --prefix=/some/directory ]
     12  $ make -j 8 install
    1413
    15 For users using the distributed tarball:
     14For users using the distributed tarball / github:
    1615
    17         ./configure
    18         make
    19         make install
     16  $ ./configure
     17  $ make -j 8 install
    2018
    21 Options for 'configure'
    22 -----------------------
    23 The script 'configure' accepts many command line arguments.  Run './configure
    24 --help' to see a list of all of them.  This document attempts to summarize the
    25 most useful arguments.
     19where 8 is the number of CPUs on your computer.
    2620
    27 --prefix=/some/directory controls the path prefix common to all installed
    28   cfa-cc components.  Some components are installed in /some/directory/bin,
    29   others in /some/directory/lib.  If unspecified, this defaults to /usr/local.
    30   To use (a subdirectory of) your home directory, ${HOME}/some/dir works, but
    31   it is important not to put quotes around the directory path; Cforall may
    32   appear to build, but the installed version may not work properly.
     21
     22Options for configure
     23======================================
     24The script 'configure' accepts many command-line arguments.  Run
     25
     26  $ ./configure --help
     27
     28to list them.  The most common argument is:
     29
     30  --prefix=/some/directory controls the path prefix common to all installed
     31    cfa-cc components.  Components are installed in directories bin and lib.
     32    If unspecified, prefix defaults to /usr/local.  To use (a subdirectory of)
     33    your home directory, ${HOME}/some/dir, but do not put quotes around the
     34    directory path; Cforall may appear to build, but the installed version may
     35    not work properly.
     36
     37
     38Build Test
     39======================================
     40
     41  $ cd ./test
     42  $ make -j 8 all-tests
     43
     44The tests take about 2-5 minutes and can be stopped at any time.
  • Jenkins/Distribute

    r5a46e09 r660665f  
    22
    33import groovy.transform.Field
    4 
    5 // For skipping stages
    6 import org.jenkinsci.plugins.pipeline.modeldefinition.Utils
    74
    85//===========================================================================================================
     
    107//===========================================================================================================
    118
    12 node('master') {
    13         // Globals
    14         BuildDir  = pwd tmp: true
    15         SrcDir    = pwd tmp: false
    16         Settings  = null
    17         Version   = ''
     9// Globals
     10BuildDir  = null
     11SrcDir    = null
     12Settings  = null
     13Version   = ''
    1814
    19         // Local variables
    20         def err = null
    21         def log_needed = false
     15// Local variables
     16def err = null
     17def log_needed = false
    2218
    23         currentBuild.result = "SUCCESS"
     19currentBuild.result = "SUCCESS"
     20
     21final commit, build
     22node {
    2423
    2524        //Wrap build to add timestamp to command line
    2625        wrap([$class: 'TimestamperBuildWrapper']) {
     26                (commit, build) = prepare_build()
     27        }
     28}
    2729
    28                 final commit, build
    29                 (commit, build) = prepare_build()
    30 
    31                 node('x64') {
    32                         BuildDir  = pwd tmp: true
    33                         SrcDir    = pwd tmp: false
    34 
    35                         Tools.Clean()
    36 
    37                         Tools.Checkout( commit )
    38 
    39                         Version = GetVersion( build )
    40 
    41                         Configure()
    42 
    43                         Package()
    44 
    45                         Test()
    46 
    47                         Archive()
    48                 }
    49 
    50                 // Update the build directories when exiting the node
     30node('x64') {
     31        //Wrap build to add timestamp to command line
     32        wrap([$class: 'TimestamperBuildWrapper']) {
    5133                BuildDir  = pwd tmp: true
    5234                SrcDir    = pwd tmp: false
     35
     36                Tools.Clean()
     37
     38                Tools.Checkout( commit )
     39
     40                Version = GetVersion( build )
     41
     42                Configure()
     43
     44                Package()
     45
     46                Test()
     47
     48                Archive()
    5349        }
    54 
    5550}
    5651
  • Jenkins/FullBuild

    r5a46e09 r660665f  
    55//===========================================================================================================
    66
    7 node ('master') {
     7node {
    88        def err = null
    99
     
    1818
    1919                                parallel (
    20                                         gcc_8_x86_new: { trigger_build( 'gcc-8',   'x86' ) },
    21                                         gcc_7_x86_new: { trigger_build( 'gcc-7',   'x86' ) },
    22                                         gcc_6_x86_new: { trigger_build( 'gcc-6',   'x86' ) },
    23                                         gcc_9_x64_new: { trigger_build( 'gcc-9',   'x64' ) },
    24                                         gcc_8_x64_new: { trigger_build( 'gcc-8',   'x64' ) },
    25                                         gcc_7_x64_new: { trigger_build( 'gcc-7',   'x64' ) },
    26                                         gcc_6_x64_new: { trigger_build( 'gcc-6',   'x64' ) },
    27                                         gcc_5_x64_new: { trigger_build( 'gcc-5',   'x64' ) },
    28                                         clang_x64_new: { trigger_build( 'clang',   'x64' ) },
     20                                        gcc_08_x86_new: { trigger_build( 'gcc-8',   'x86' ) },
     21                                        gcc_07_x86_new: { trigger_build( 'gcc-7',   'x86' ) },
     22                                        gcc_06_x86_new: { trigger_build( 'gcc-6',   'x86' ) },
     23                                        gcc_10_x64_new: { trigger_build( 'gcc-10',  'x64' ) },
     24                                        gcc_09_x64_new: { trigger_build( 'gcc-9',   'x64' ) },
     25                                        gcc_08_x64_new: { trigger_build( 'gcc-8',   'x64' ) },
     26                                        gcc_07_x64_new: { trigger_build( 'gcc-7',   'x64' ) },
     27                                        gcc_06_x64_new: { trigger_build( 'gcc-6',   'x64' ) },
     28                                        clang_x64_new:  { trigger_build( 'clang',   'x64' ) },
    2929                                )
    3030                        }
     
    106106
    107107        if(result.result != 'SUCCESS') {
    108                 sh("wget -q -O - http://localhost:8084/jenkins/job/Cforall/job/master/${result.number}/consoleText")
     108                sh("wget -q -O - https://cforall.uwaterloo.ca/jenkins/job/Cforall/job/master/${result.number}/consoleText")
    109109                error(result.result)
    110110        }
     
    144144//Email notification on a full build failure
    145145def promote_email(boolean success) {
    146         echo('notifying users')
     146        node {
     147                echo('notifying users')
    147148
    148         def result = success ? "PROMOTE - SUCCESS" : "PROMOTE - FAILURE"
     149                def result = success ? "PROMOTE - SUCCESS" : "PROMOTE - FAILURE"
    149150
    150         //Since tokenizer doesn't work, figure stuff out from the environnement variables and command line
    151         //Configurations for email format
    152         def email_subject = "[cforall git][${result}]"
    153         def email_body = """<p>This is an automated email from the Jenkins build machine. It was
    154 generated following the result of the C\u2200 nightly build.</p>
     151                //Since tokenizer doesn't work, figure stuff out from the environnement variables and command line
     152                //Configurations for email format
     153                def email_subject = "[cforall git][${result}]"
     154                def email_body = """<p>This is an automated email from the Jenkins build machine. It was
     155        generated following the result of the C\u2200 nightly build.</p>
    155156
    156 <p>Check console output at ${env.BUILD_URL} to view the results.</p>
     157        <p>Check console output at ${env.BUILD_URL} to view the results.</p>
    157158
    158 <p>- Status --------------------------------------------------------------</p>
     159        <p>- Status --------------------------------------------------------------</p>
    159160
    160 <p>${result}</p>
     161        <p>${result}</p>
    161162
    162 <p>- Performance ---------------------------------------------------------</p>
     163        <p>- Performance ---------------------------------------------------------</p>
    163164
    164 <img src="https://cforall.uwaterloo.ca/jenkins/job/Cforall/job/master/plot/Compilation/getPlot?index=0" >
    165 <img src="https://cforall.uwaterloo.ca/jenkins/job/Cforall/job/master/plot/Compilation/getPlot?index=1" >
     165        <img src="https://cforall.uwaterloo.ca/jenkins/job/Cforall/job/master/plot/Compilation/getPlot?index=0" >
     166        <img src="https://cforall.uwaterloo.ca/jenkins/job/Cforall/job/master/plot/Compilation/getPlot?index=1" >
    166167
    167 <p>- Logs ----------------------------------------------------------------</p>
    168 """
     168        <p>- Logs ----------------------------------------------------------------</p>
     169        """
    169170
    170         def email_to = "cforall@lists.uwaterloo.ca"
     171                def email_to = "cforall@lists.uwaterloo.ca"
    171172
    172         //send email notification
    173         emailext body: email_body, subject: email_subject, to: email_to, attachLog: !success
     173                //send email notification
     174                emailext body: email_body, subject: email_subject, to: email_to, attachLog: !success
     175        }
    174176}
  • Jenkins/tools.groovy

    r5a46e09 r660665f  
    6161}
    6262
    63 PrevGitOldRef = ''
    64 PrevGitNewRef = ''
    65 def GitLogMessage(String oldRef = '', String newRef = '') {
    66         if (!oldRef) { if(!PrevGitOldRef) { return "\nERROR retrieveing current git information!\n"  } else { oldRef = PrevGitOldRef } }
    67         if (!newRef) { if(!PrevGitNewRef) { return "\nERROR retrieveing previous git information!\n" } else { newRef = PrevGitNewRef } }
    68 
     63def ConstructGitLogMessage(String oldRef, String newRef) {
    6964        def revText = sh(returnStdout: true, script: "git rev-list ${oldRef}..${newRef}").trim()
    7065        def revList = SplitLines( revText )
     
    8782        gitDiff = gitDiff.replace('[m', '</span>')
    8883
    89         PrevGitOldRef = oldRef
    90         PrevGitNewRef = newRef
     84        return """
     85<p>- Changes -------------------------------------------------------------</p>
    9186
    92         return """
    9387<pre>
    9488The branch ${env.BRANCH_NAME} has been updated.
    9589${gitUpdate}
    9690</pre>
    97 
    98 <p>Check console output at ${env.BUILD_URL} to view the results.</p>
    99 
    100 <p>- Status --------------------------------------------------------------</p>
    101 
    102 <p>BUILD# ${env.BUILD_NUMBER} - ${currentBuild.result}</p>
    10391
    10492<p>- Log -----------------------------------------------------------------</p>
     
    116104}
    117105
     106EmailMessage = ''
     107def GitLogMessage(String oldRef = '', String newRef = '') {
     108        if(!EmailMessage) {
     109                if (!oldRef) { return "\nERROR retrieveing current git information!\n"  }
     110                if (!newRef) { return "\nERROR retrieveing previous git information!\n" }
     111
     112                echo "Constructing new git message"
     113
     114                EmailMessage = ConstructGitLogMessage(oldRef, newRef)
     115        }
     116        else {
     117                echo "Reusing previously constructed message"
     118        }
     119        return EmailMessage;
     120}
     121
    118122return this;
  • Jenkinsfile

    r5a46e09 r660665f  
    77//===========================================================================================================
    88
    9 node('master') {
    10         // Globals
    11         BuildDir  = pwd tmp: true
    12         SrcDir    = pwd tmp: false
    13         Settings  = null
    14         Tools     = null
    15 
    16         // Local variables
    17         def err = null
    18         def log_needed = false
    19 
    20         currentBuild.result = "SUCCESS"
    21 
    22         try {
     9// Globals
     10BuildDir  = null
     11SrcDir    = null
     12Settings  = null
     13Tools     = null
     14
     15// Local variables
     16def err = null
     17def log_needed = false
     18
     19currentBuild.result = "SUCCESS"
     20
     21try {
     22        node {
    2323                //Wrap build to add timestamp to command line
    2424                wrap([$class: 'TimestamperBuildWrapper']) {
    25 
    2625                        Settings = prepare_build()
    27 
    28                         node(Settings.Architecture.node) {
    29                                 BuildDir  = pwd tmp: true
    30                                 SrcDir    = pwd tmp: false
    31                                 currentBuild.description = "${currentBuild.description} on ${env.NODE_NAME}"
    32 
    33                                 Tools.Clean()
    34 
    35                                 Tools.Checkout()
    36 
    37                                 build()
    38 
    39                                 test()
    40 
    41                                 benchmark()
    42 
    43                                 build_doc()
    44 
    45                                 publish()
    46                         }
    47 
    48                         // Update the build directories when exiting the node
     26                }
     27        }
     28
     29        node(Settings.Architecture.node) {
     30                //Wrap build to add timestamp to command line
     31                wrap([$class: 'TimestamperBuildWrapper']) {
    4932                        BuildDir  = pwd tmp: true
    5033                        SrcDir    = pwd tmp: false
    51                 }
    52         }
    53 
    54         //If an exception is caught we need to change the status and remember to
    55         //attach the build log to the email
    56         catch (Exception caughtError) {
    57                 // Store the result of the build log
    58                 currentBuild.result = "FAILURE"
    59 
    60                 // An error has occured, the build log is relevent
    61                 log_needed = true
    62 
    63                 // rethrow error later
    64                 err = caughtError
    65 
    66                 // print the error so it shows in the log
    67                 echo err.toString()
    68         }
    69 
    70         finally {
    71                 //Send email with final results if this is not a full build
    72                 email(log_needed)
    73 
    74                 echo 'Build Completed'
    75 
    76                 /* Must re-throw exception to propagate error */
    77                 if (err) {
    78                         throw err
    79                 }
     34                        currentBuild.description = "${currentBuild.description} on ${env.NODE_NAME}"
     35
     36                        Tools.Clean()
     37
     38                        Tools.Checkout()
     39
     40                        build()
     41
     42                        test()
     43
     44                        benchmark()
     45
     46                        build_doc()
     47
     48                        publish()
     49                }
     50        }
     51}
     52
     53//If an exception is caught we need to change the status and remember to
     54//attach the build log to the email
     55catch (Exception caughtError) {
     56        // Store the result of the build log
     57        currentBuild.result = "FAILURE"
     58
     59        // An error has occured, the build log is relevent
     60        log_needed = true
     61
     62        // rethrow error later
     63        err = caughtError
     64
     65        // print the error so it shows in the log
     66        echo err.toString()
     67}
     68
     69finally {
     70        //Send email with final results if this is not a full build
     71        email(log_needed)
     72
     73        echo 'Build Completed'
     74
     75        /* Must re-throw exception to propagate error */
     76        if (err) {
     77                throw err
    8078        }
    8179}
     
    228226//Standard build email notification
    229227def email(boolean log) {
    230         //Since tokenizer doesn't work, figure stuff out from the environnement variables and command line
    231         //Configurations for email format
    232         echo 'Notifying users of result'
    233 
    234         def project_name = (env.JOB_NAME =~ /(.+)\/.+/)[0][1].toLowerCase()
    235         def email_subject = "[${project_name} git][BUILD# ${env.BUILD_NUMBER} - ${currentBuild.result}] - branch ${env.BRANCH_NAME}"
    236         def email_body = """<p>This is an automated email from the Jenkins build machine. It was
     228        node {
     229                //Since tokenizer doesn't work, figure stuff out from the environnement variables and command line
     230                //Configurations for email format
     231                echo 'Notifying users of result'
     232
     233                def project_name = (env.JOB_NAME =~ /(.+)\/.+/)[0][1].toLowerCase()
     234                def email_subject = "[${project_name} git][BUILD# ${env.BUILD_NUMBER} - ${currentBuild.result}] - branch ${env.BRANCH_NAME}"
     235                def email_body = """<p>This is an automated email from the Jenkins build machine. It was
    237236generated because of a git hooks/post-receive script following
    238237a ref change which was pushed to the C\u2200 repository.</p>
     238
     239<p>- Status --------------------------------------------------------------</p>
     240
     241<p>BUILD# ${env.BUILD_NUMBER} - ${currentBuild.result}</p>
     242<p>Check console output at ${env.BUILD_URL} to view the results.</p>
    239243""" + Tools.GitLogMessage()
    240244
    241         def email_to = !Settings.IsSandbox ? "cforall@lists.uwaterloo.ca" : "tdelisle@uwaterloo.ca"
    242 
    243         if( Settings && !Settings.Silent ) {
    244                 //send email notification
    245                 emailext body: email_body, subject: email_subject, to: email_to, attachLog: log
    246         } else {
    247                 echo "Would send email to: ${email_to}"
    248                 echo "With title: ${email_subject}"
    249                 echo "Content: \n${email_body}"
     245                def email_to = !Settings.IsSandbox ? "cforall@lists.uwaterloo.ca" : "tdelisle@uwaterloo.ca"
     246
     247                if( Settings && !Settings.Silent ) {
     248                        //send email notification
     249                        emailext body: email_body, subject: email_subject, to: email_to, attachLog: log
     250                } else {
     251                        echo "Would send email to: ${email_to}"
     252                        echo "With title: ${email_subject}"
     253                        echo "Content: \n${email_body}"
     254                }
    250255        }
    251256}
     
    300305        BuildSettings(java.util.Collections$UnmodifiableMap param, String branch) {
    301306                switch( param.Compiler ) {
     307                        case 'gcc-11':
     308                                this.Compiler = new CC_Desc('gcc-11', 'g++-11', 'gcc-11', '-flto=auto')
     309                        break
     310                        case 'gcc-10':
     311                                this.Compiler = new CC_Desc('gcc-10', 'g++-10', 'gcc-10', '-flto=auto')
     312                        break
    302313                        case 'gcc-9':
    303314                                this.Compiler = new CC_Desc('gcc-9', 'g++-9', 'gcc-9', '-flto=auto')
     
    319330                        break
    320331                        case 'clang':
    321                                 this.Compiler = new CC_Desc('clang', 'clang++-10', 'gcc-9', '-flto=thin -flto-jobs=0')
     332                                this.Compiler = new CC_Desc('clang', 'clang++-10', 'gcc-10', '-flto=thin -flto-jobs=0')
    322333                        break
    323334                        default :
     
    390401                                        description: 'Which compiler to use',                                   \
    391402                                        name: 'Compiler',                                                                       \
    392                                         choices: 'gcc-9\ngcc-8\ngcc-7\ngcc-6\ngcc-5\ngcc-4.9\nclang',   \
     403                                        choices: 'gcc-11\ngcc-10\ngcc-9\ngcc-8\ngcc-7\ngcc-6\ngcc-5\ngcc-4.9\nclang',   \
    393404                                        defaultValue: 'gcc-8',                                                          \
    394405                                ],                                                                                              \
  • README

    r5a46e09 r660665f  
    1 cfa-cc: The Cforall->C Compiler System
     1cfa-cc: Cforall to C Trans-compiler
    22======================================
    33
     
    66responsibility for the consequences of any malfunction of the software,
    77including the malfunction of any programs compiled using the software.
     8
    89
    910What is Cforall?
     
    2526into a modern programming language.
    2627
     28
    2729What is cfa-cc?
    2830---------------
    29 cfa-cc is a collection of programs centred around a translator that takes
    30 Cforall code as input and outputs corresponding C code.  This is complemented
    31 by a compiler driver in the style of "gcc", which handles preprocessing,
    32 compiling, assembling, and linking and invokes the translator at appropriate
    33 moments.
     31cfa-cc is a collection of programs centred around a translator (trans-compiler)
     32that takes Cforall code as input and outputs augmented C code that implements
     33new features.  The translator is complemented by a compiler driver in the style
     34of "gcc", which handles preprocessing (including cfa-cc after cpp), compiling,
     35assembling, and linking.
    3436
    35 What is required in order to use cfa-cc?
     37cfa-cc is currently written in C++, but will be eventually rewritten in Cforall.
     38
     39
     40How to download and build cfa-cc?
    3641----------------------------------------
    37 Building cfa-cc requires GNU Make and gcc/g++ 4.  cfa-cc is written in C++.
     42Download cfa-cc using
    3843
    39 The compiler driver uses an installed version of gcc to handle all aspects of
    40 the compilation process except for the Cforall->C translation.  Currently, only
    41 gcc 4.x is supported.
     44  $ git clone https://github.com/cforall/cforall.git
    4245
    43 How is cfa-cc used?
     46Read the ./INSTALL file for build instructions.
     47
     48
     49How to use cfa-cc?
    4450-------------------
    45 The compiler driver "cfa" accepts all of the arguments of gcc, and is used in
     51The compiler driver "cfa" accepts all of the arguments for gcc, and is used in
    4652the same way.  For example:
    4753
    48         cfa -c test.c
    49         cfa test.o
     54  cfa -c test.c
     55  cfa test.o
    5056
    51 Cforall source files must end with '.c' in order to be compiled by the compiler
    52 driver.  In addition, the flag "-CFA" causes cfa to invoke the preprocessor and
    53 translator and send the translator output to standard output.
     57Cforall source files may end with '.c' or '.cfa' in order to be compiled by the
     58compiler driver.  In addition, the flag "-CFA" causes cfa to invoke the C
     59preprocessor and Cforall translator and write the translator output to standard
     60output.
    5461
    55 It is possible to invoke the translator directly.  The translator is installed
    56 by default as /usr/local/lib/cfa-cpp.  A typical invocation is:
    5762
    58         /usr/local/lib/cfa-cpp -cp infile outfile
     63How to use C code with cfa-cc?
     64-----------------------------------
     65cfa-cc should be able to compile and link most ANSI C programs with associated
     66C standard libraries.
    5967
    60 If outfile is omitted, output goes to standard output; if infile is also
    61 omitted, input comes from standard input.  Options to the translator other than
    62 "-cp" will not produce valid C code and are only useful for debugging the
    63 translator.
     68Like C++, Cforall supports overloading, resulting in duplicate names that are
     69disambiguated using name mangling in the translated C code.  To prevent
     70mangling of C names, it is necessary to wrap C declarations in an extern "C"
     71block, as for C++.  For example:
    6472
    65 How can C code be used with cfa-cc?
    66 -----------------------------------
    67 cfa-cc should be able to compile most ANSI C programs.  It is also possible to
    68 link against C libraries in most cases.  Since Cforall supports overloading,
    69 however, names used in Cforall code are mangled in the output C code.  This
    70 caused linker failures when the names refer to functions and objects in code
    71 compiled with a standard C compiler.  For this reason, it is necessary to
    72 enclose the declarations of these functions and objects in extern "C" {}
    73 blocks.  For example:
    74 
    75         extern "C" {
    76         #include <stdio.h>
    77         #include <stdlib.h>
    78         }
     73  extern "C" {
     74  #include <curses.h>
     75  #include <getopt.h>
     76  }
    7977
    8078The extern "C" turns off name mangling for functions and objects declared
    81 within the block.  As a result, it is not possible to overload their names.
     79within the block. All C standard headers are pre-wrapped, so most wrapping is
     80unnecessary.
     81
    8282
    8383What's wrong with cfa-cc?
    8484-------------------------
    8585
    86 The authors consider this software to be in an unstable state.  It is quite
    87 likely that there are many reasonable programs that will fail to compile.  We
    88 encourage users to report their experiences to cforall@plg.uwaterloo.ca, but we
    89 make no promises regarding support.
     86The authors consider cfa-cc to be in a semi-stable state.  It is possible for
     87reasonable Cforall programs to fail compilation.  A list of bugs and fixes is
     88available here: https://cforall.uwaterloo.ca/trac.  We encourage users to
     89report their experiences to cforall@plg.uwaterloo.ca, but we can make no
     90promises regarding support.
    9091
    91 We have fixed most of the problems that we are aware of.  There are some
    92 exceptions:
     92Also, the Cforall features web-page https://cforall.uwaterloo.ca/features lists
     93small syntactic and semantic differences with standard C.
    9394
    94 - initializers are poorly implemented; in particular, file-scope initializers
    95   may result in the generation of invalid C code
    96 
    97 - the ISO C99 designated initialization syntax '[n] = m' or '.n = m' is not
    98   supported; use a colon in place of the equal sign
    99 
    100 - some legitimate programs will produce warnings from the C compiler; these are
    101   harmless (in particular, the creation of libcfa.a in the build process should
    102   cause four warnings from gcc)
    103 
    104 - abstract types introduced using the keyword 'type' are not implemented
    105   (although 'type' can be used to introduce type parameters)
    106 
    107 - the implicit coercion of structure types to the type of their first member is
    108   not implemented
    10995
    11096Who is responsible for cfa-cc?
    11197------------------------------
    112 cfa-cc was written by Peter Buhr, Richard Bilson, and Rodolfo Esteves.
    113 Questions and comments can be sent to cforall@plg.uwaterloo.ca.
     98Cforall was designed and implemented by Andrew Beach, Richard Bilson, Michael
     99Brooks, Peter A. Buhr, Thierry Delisle Glen Ditchfield, Rodolfo G. Esteves,
     100Aaron Moss, Colby Parsons, Rob Schluntz, Fangren Yu, Mubeen Zulfiqar, and others.
    114101
    115 The Cforall project maintains a web page:
    116 
    117         https://cforall.uwaterloo.ca
     102Check the Cforall web site https://cforall.uwaterloo.ca for news and updates.
  • benchmark/io/io_uring.h

    r5a46e09 r660665f  
    11extern "C" {
    2         #ifndef _GNU_SOURCE         /* See feature_test_macros(7) */
    3         #define _GNU_SOURCE         /* See feature_test_macros(7) */
    4         #endif
    52        #include <errno.h>
    63        #include <stdio.h>
  • doc/bibliography/pl.bib

    r5a46e09 r660665f  
    16731673    address     = {Waterloo Ontario, Canada},
    16741674    month       = sep,
    1675     year        = 2018,
     1675    year        = 2020,
    16761676    note        = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-pub/\-uSystem/uC++.pdf}},
    16771677}
     
    45524552    author      = {Martin Karsten},
    45534553    title       = {{libfibre:~User-Level Threading Runtime}},
    4554     howpublished= {\href{https://git.uwaterloo.ca/mkarsten/libfibre}
    4555                   {https://\-git.uwaterloo.ca/\-mkarsten/\-libfibre}},
     4554    howpublished= {\href{https://git.uwaterloo.ca/mkarsten/libfibre}{https://\-git.uwaterloo.ca/\-mkarsten/\-libfibre}},
    45564555    note        = {[Online; accessed 2020-04-15]},
    45574556}
  • doc/theses/andrew_beach_MMath/cfalab.sty

    r5a46e09 r660665f  
    143143}
    144144
     145% These somehow control how much of a page can be a floating element before
     146% the float is forced onto its own page.   
     147\renewcommand{\topfraction}{0.8}
     148\renewcommand{\bottomfraction}{0.8}
     149\renewcommand{\floatpagefraction}{0.8}
     150% Sort of the reverse, I think it is the minimum amount of text that can
     151% be on a page before its all removed. (0 for always fix what you can.)
     152\renewcommand{\textfraction}{0.0}
     153
    145154% common.tex Compatablity ===================================================
    146155% Below this line is for compatability with the old common.tex file.
  • doc/theses/andrew_beach_MMath/existing.tex

    r5a46e09 r660665f  
    1 \chapter{\CFA Existing Features}
     1\chapter{\CFA{} Existing Features}
    22\label{c:existing}
    33
     
    99existing C code-base allowing programmers to learn \CFA on an as-needed basis.
    1010
    11 Only those \CFA features pertaining to this thesis are discussed.  Many of the
    12 \CFA syntactic and semantic features used in the thesis should be fairly
    13 obvious to the reader.
     11Only those \CFA features pertaining to this thesis are discussed.
     12Also, only new features of \CFA will be discussed, a familiarity with
     13C or C-like languages is assumed.
    1414
    1515\section{Overloading and \lstinline{extern}}
     
    2929// name mangling on by default
    3030int i; // _X1ii_1
    31 @extern "C"@ {  // disables name mangling
     31extern "C" {  // disables name mangling
    3232        int j; // j
    33         @extern "Cforall"@ {  // enables name mangling
     33        extern "Cforall" {  // enables name mangling
    3434                int k; // _X1ki_1
    3535        }
     
    4747Reference-types are written the same way as a pointer-type but each
    4848asterisk (@*@) is replaced with a ampersand (@&@);
    49 this includes cv-qualifiers and multiple levels of reference, \eg:
    50 
     49this includes cv-qualifiers and multiple levels of reference.
     50
     51Generally, references act like pointers with an implicate dereferencing
     52operation added to each use of the variable.
     53These automatic dereferences may be disabled with the address-of operator
     54(@&@).
     55
     56% Check to see if these are generating errors.
    5157\begin{minipage}{0,5\textwidth}
    5258With references:
     
    5662int && rri = ri;
    5763rri = 3;
    58 &ri = &j; // reference assignment
     64&ri = &j;
    5965ri = 5;
    6066\end{cfa}
     
    6773int ** ppi = &pi;
    6874**ppi = 3;
    69 pi = &j; // pointer assignment
     75pi = &j;
    7076*pi = 5;
    7177\end{cfa}
    7278\end{minipage}
    7379
    74 References are intended for cases where you would want to use pointers but would
     80References are intended to be used when you would use pointers but would
    7581be dereferencing them (almost) every usage.
    76 In most cases a reference can just be thought of as a pointer that
    77 automatically puts a dereference in front of each of its uses (per-level of
    78 reference).
    79 The address-of operator (@&@) acts as an escape and removes one of the
    80 automatic dereference operations.
    81 Mutable references may be assigned by converting them to a pointer
    82 with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above.
     82Mutable references may be assigned to by converting them to a pointer
     83with a @&@ and then assigning a pointer to them, as in @&ri = &j;@ above
    8384
    8485\section{Operators}
    8586
    86 In general, operator names in \CFA are constructed by bracketing an operator
    87 token with @?@, which indicates the position of the arguments. For example,
     87\CFA implements operator overloading by providing special names.
     88Operator uses are translated into function calls using these names.
     89These names are created by taking the operator symbols and joining them with
     90@?@s to show where the arguments go.
     91For example,
    8892infixed multiplication is @?*?@ while prefix dereference is @*?@.
    8993This syntax make it easy to tell the difference between prefix operations
    9094(such as @++?@) and post-fix operations (@?++@).
    9195
    92 An operator name may describe any function signature (it is just a name) but
    93 only certain signatures may be called in operator form.
    94 \begin{cfa}
    95 int ?+?( int i, int j, int k ) { return i + j + k; }
    96 {
    97         sout | ?+?( 3, 4, 5 ); // no infix form
    98 }
    99 \end{cfa}
    100 Some ``near-misses" for unary/binary operator prototypes generate warnings.
     96\begin{cfa}
     97point ?+?(point a, point b) { return point{a.x + b.x, a.y + b.y}; }
     98bool ?==?(point a, point b) { return a.x == b.x && a.y == b.y; }
     99{
     100        assert(point{1, 2} + point{3, 4} == point{4, 6});
     101}
     102\end{cfa}
     103Note that these special names are not limited to just being used for these
     104operator functions, and may be used name other declarations.
     105Some ``near misses", that will not match an operator form but looks like
     106it may have been supposed to, will generate wantings but otherwise they are
     107left alone.
     108
     109%\subsection{Constructors and Destructors}
    101110
    102111Both constructors and destructors are operators, which means they are
    103112functions with special operator names rather than type names in \Cpp. The
    104 special operator names may be used to call the functions explicitly (not
    105 allowed in \Cpp for constructors).
    106 
    107 The special name for a constructor is @?{}@, where the name @{}@ comes from the
    108 initialization syntax in C, \eg @Structure s = {...}@.
    109 % That initialization syntax is also the operator form.
    110 \CFA generates a constructor call each time a variable is declared,
    111 passing the initialization arguments to the constructor.
    112 \begin{cfa}
    113 struct Structure { ... };
    114 void ?{}(Structure & this) { ... }
    115 {
    116         Structure a;
    117         Structure b = {};
    118 }
    119 void ?{}(Structure & this, char first, int num) { ... }
    120 {
    121         Structure c = {'a', 2};
    122 }
    123 \end{cfa}
    124 Both @a@ and @b@ are initialized with the first constructor,
    125 while @c@ is initialized with the second.
    126 Currently, there is no general way to skip initialization.
     113special operator names may be used to call the functions explicitly.
     114% Placement new means that this is actually equivant to C++.
     115
     116The special name for a constructor is @?{}@, which comes from the
     117initialization syntax in C, \eg @Example e = { ... }@.
     118\CFA will generate a constructor call each time a variable is declared,
     119passing the initialization arguments to the constructort.
     120\begin{cfa}
     121struct Example { ... };
     122void ?{}(Example & this) { ... }
     123{
     124        Example a;
     125        Example b = {};
     126}
     127void ?{}(Example & this, char first, int num) { ... }
     128{
     129        Example c = {'a', 2};
     130}
     131\end{cfa}
     132Both @a@ and @b@ will be initalized with the first constructor,
     133while @c@ will be initalized with the second.
     134Currently, there is no general way to skip initialation.
    127135
    128136% I don't like the \^{} symbol but $^\wedge$ isn't better.
    129 Similarly, destructors use the special name @^?{}@ (the @^@ has no special
    130 meaning).  Normally, they are implicitly called on a variable when it goes out
    131 of scope but they can be called explicitly as well.
    132 \begin{cfa}
    133 void ^?{}(Structure & this) { ... }
    134 {
    135         Structure d;
     137Similarly destructors use the special name @^?{}@ (the @^@ has no special
     138meaning).
     139These are a normally called implicitly called on a variable when it goes out
     140of scope. They can be called explicitly as well.
     141\begin{cfa}
     142void ^?{}(Example & this) { ... }
     143{
     144        Example d;
    136145} // <- implicit destructor call
    137146\end{cfa}
    138147
    139 Whenever a type is defined, \CFA creates a default zero-argument
     148Whenever a type is defined, \CFA will create a default zero-argument
    140149constructor, a copy constructor, a series of argument-per-field constructors
    141150and a destructor. All user constructors are defined after this.
     
    198207void do_once(double y) { ... }
    199208int quadruple(int x) {
    200         void do_once(int y) { y = y * 2; } // replace global do_once
    201         do_twice(x); // use local do_once
    202         do_twice(x + 1.5); // use global do_once
     209        void do_once(int & y) { y = y * 2; }
     210        do_twice(x);
    203211        return x;
    204212}
    205213\end{cfa}
    206214Specifically, the complier deduces that @do_twice@'s T is an integer from the
    207 argument @x@. It then looks for the most \emph{specific} definition matching the
     215argument @x@. It then looks for the most specific definition matching the
    208216assertion, which is the nested integral @do_once@ defined within the
    209217function. The matched assertion function is then passed as a function pointer
    210 to @do_twice@ and called within it.  The global definition of @do_once@ is used
    211 for the second call because the float-point argument is a better match.
     218to @do_twice@ and called within it.
     219The global definition of @do_once@ is ignored, however if quadruple took a
     220@double@ argument then the global definition would be used instead as it
     221would be a better match.
     222% Aaron's thesis might be a good reference here.
    212223
    213224To avoid typing long lists of assertions, constraints can be collect into
     
    279290Each coroutine has a @main@ function, which takes a reference to a coroutine
    280291object and returns @void@.
    281 \begin{cfa}[numbers=left]
     292%[numbers=left] Why numbers on this one?
     293\begin{cfa}
    282294void main(CountUp & this) {
    283295        for (unsigned int next = 0 ; true ; ++next) {
  • doc/theses/andrew_beach_MMath/features.tex

    r5a46e09 r660665f  
    22\label{c:features}
    33
    4 This chapter covers the design and user interface of the \CFA
    5 EHM, % or exception system.
     4This chapter covers the design and user interface of the \CFA EHM
    65and begins with a general overview of EHMs. It is not a strict
    76definition of all EHMs nor an exhaustive list of all possible features.
    8 However it does cover the most common structures and features found in them.
    9 
     7However it does cover the most common structure and features found in them.
     8
     9\section{Overview of EHMs}
    1010% We should cover what is an exception handling mechanism and what is an
    1111% exception before this. Probably in the introduction. Some of this could
    1212% move there.
    13 \section{Raise / Handle}
     13\subsection{Raise / Handle}
    1414An exception operation has two main parts: raise and handle.
    15 These terms are sometimes also known as throw and catch but this work uses
     15These terms are sometimes known as throw and catch but this work uses
    1616throw/catch as a particular kind of raise/handle.
    1717These are the two parts that the user writes and may
     
    2424
    2525Some well known examples include the @throw@ statements of \Cpp and Java and
    26 the \code{Python}{raise} statement from Python. A raise may
    27 perform some other work (such as memory management) but for the
     26the \code{Python}{raise} statement from Python. In real systems a raise may
     27preform some other work (such as memory management) but for the
    2828purposes of this overview that can be ignored.
    2929
     
    3333
    3434A handler has three common features: the previously mentioned user code, a
    35 region of code they guard, and an exception label/condition that matches
     35region of code they guard and an exception label/condition that matches
    3636certain exceptions.
    3737Only raises inside the guarded region and raising exceptions that match the
    3838label can be handled by a given handler.
    39 Different EHMs have different rules to pick a handler,
    40 if multiple handlers could be used, such as ``best match" or ``first found".
     39If multiple handlers could can handle an exception,
     40EHMs will define a rule to pick one, such as ``best match" or ``first found".
    4141
    4242The @try@ statements of \Cpp, Java and Python are common examples. All three
     
    4444region.
    4545
    46 \section{Propagation}
     46\subsection{Propagation}
    4747After an exception is raised comes what is usually the biggest step for the
    4848EHM: finding and setting up the handler. The propagation from raise to
    4949handler can be broken up into three different tasks: searching for a handler,
    50 matching against the handler, and installing the handler.
     50matching against the handler and installing the handler.
    5151
    5252\paragraph{Searching}
     
    5555thrown as it looks for handlers that have the raise site in their guarded
    5656region.
    57 This search includes handlers in the current function, as well as any in callers
    58 on the stack that have the function call in their guarded region.
     57The search includes handlers in the current function, as well as any in
     58callers on the stack that have the function call in their guarded region.
    5959
    6060\paragraph{Matching}
    6161Each handler found has to be matched with the raised exception. The exception
    62 label defines a condition that is used with the exception to decide if
     62label defines a condition that is used with exception and decides if
    6363there is a match or not.
    6464
    6565In languages where the first match is used, this step is intertwined with
    66 searching: a match check is performed immediately after the search finds
     66searching; a match check is preformed immediately after the search finds
    6767a possible handler.
    6868
    69 \section{Installing}
     69\paragraph{Installing}
    7070After a handler is chosen it must be made ready to run.
    7171The implementation can vary widely to fit with the rest of the
     
    7474case when stack unwinding is involved.
    7575
    76 If a matching handler is not guarantied to be found, the EHM needs a
     76If a matching handler is not guaranteed to be found, the EHM needs a
    7777different course of action for the case where no handler matches.
    7878This situation only occurs with unchecked exceptions as checked exceptions
    7979(such as in Java) can make the guarantee.
    80 This unhandled action can abort the program or install a very general handler.
     80This unhandled action is usually very general, such as aborting the program.
    8181
    8282\paragraph{Hierarchy}
    8383A common way to organize exceptions is in a hierarchical structure.
    84 This organization is often used in object-orientated languages where the
     84This pattern comes from object-orientated languages where the
    8585exception hierarchy is a natural extension of the object hierarchy.
    8686
     
    9090\end{center}
    9191
    92 A handler labelled with any given exception can handle exceptions of that
     92A handler labeled with any given exception can handle exceptions of that
    9393type or any child type of that exception. The root of the exception hierarchy
    9494(here \code{C}{exception}) acts as a catch-all, leaf types catch single types
     
    104104% Could I cite the rational for the Python IO exception rework?
    105105
    106 \paragraph{Completion}
    107 After the handler has finished the entire exception operation has to complete
     106\subsection{Completion}
     107After the handler has finished, the entire exception operation has to complete
    108108and continue executing somewhere else. This step is usually simple,
    109109both logically and in its implementation, as the installation of the handler
     
    111111
    112112The EHM can return control to many different places,
    113 the most common are after the handler definition (termination) and after the raise (resumption).
    114 
    115 \paragraph{Communication}
     113the most common are after the handler definition (termination)
     114and after the raise (resumption).
     115
     116\subsection{Communication}
    116117For effective exception handling, additional information is often passed
    117118from the raise to the handler and back again.
    118119So far only communication of the exceptions' identity has been covered.
    119 A common communication method is putting fields into the exception instance and giving the
    120 handler access to them. References in the exception instance can push data back to the raise.
     120A common communication method is putting fields into the exception instance
     121and giving the handler access to them.
     122Passing the exception by reference instead of by value can allow data to be
     123passed in both directions.
    121124
    122125\section{Virtuals}
    123126Virtual types and casts are not part of \CFA's EHM nor are they required for
    124127any EHM.
    125 However, one of the best ways to support an exception hierarchy is via a virtual system
    126 among exceptions and used for exception matching.
     128However, it is one of the best ways to support an exception hierarchy
     129is via a virtual hierarchy and dispatch system.
    127130
    128131Ideally, the virtual system would have been part of \CFA before the work
    129132on exception handling began, but unfortunately it was not.
    130 Therefore, only the features and framework needed for the EHM were
     133Hence, only the features and framework needed for the EHM were
    131134designed and implemented. Other features were considered to ensure that
    132 the structure could accommodate other desirable features in the future but they were not
    133 implemented.
    134 The rest of this section discusses the implemented subset of the
    135 virtual-system design.
     135the structure could accommodate other desirable features in the future
     136but they were not implemented.
     137The rest of this section will only discuss the implemented subset of the
     138virtual system design.
    136139
    137140The virtual system supports multiple ``trees" of types. Each tree is
     
    143146% A type's ancestors are its parent and its parent's ancestors.
    144147% The root type has no ancestors.
    145 % A type's decedents are its children and its children's decedents.
     148% A type's descendants are its children and its children's descendants.
    146149
    147150Every virtual type also has a list of virtual members. Children inherit
     
    150153of object-orientated programming, and can be of any type.
    151154
    152 \PAB{I do not understand these sentences. Can you add an example? $\Rightarrow$
    153155\CFA still supports virtual methods as a special case of virtual members.
    154156Function pointers that take a pointer to the virtual type are modified
    155157with each level of inheritance so that refers to the new type.
    156158This means an object can always be passed to a function in its virtual table
    157 as if it were a method.}
     159as if it were a method.
     160\todo{Clarify (with an example) virtual methods.}
    158161
    159162Each virtual type has a unique id.
     
    161164into a virtual table type. Each virtual type has a pointer to a virtual table
    162165as a hidden field.
    163 
    164 \PAB{God forbid, maybe you need a UML diagram to relate these entities.}
     166\todo{Might need a diagram for virtual structure.}
    165167
    166168Up until this point the virtual system is similar to ones found in
     
    173175types can begin to satisfy a trait, stop satisfying a trait or satisfy the same
    174176trait in a different way at any lexical location in the program.
    175 In this sense, they are ``open" as they can change at any time. This capability means it
    176 is impossible to pick a single set of functions that represent the type's
    177 implementation across the program.
     177In this sense, they are ``open" as they can change at any time.
     178This capability means it is impossible to pick a single set of functions
     179that represent the type's implementation across the program.
    178180
    179181\CFA side-steps this issue by not having a single virtual table for each
    180182type. A user can define virtual tables that are filled in at their
    181 declaration and given a name. Anywhere that name is visible, even if
     183declaration and given a name. Anywhere that name is visible, even if it is
    182184defined locally inside a function (although that means it does not have a
    183185static lifetime), it can be used.
     
    186188through the object.
    187189
    188 \PAB{The above explanation is very good!}
    189 
    190190While much of the virtual infrastructure is created, it is currently only used
    191191internally for exception handling. The only user-level feature is the virtual
    192 cast
     192cast, which is the same as the \Cpp \code{C++}{dynamic_cast}.
    193193\label{p:VirtualCast}
    194194\begin{cfa}
    195195(virtual TYPE)EXPRESSION
    196196\end{cfa}
    197 which is the same as the \Cpp \code{C++}{dynamic_cast}.
    198197Note, the syntax and semantics matches a C-cast, rather than the function-like
    199198\Cpp syntax for special casts. Both the type of @EXPRESSION@ and @TYPE@ must be
     
    218217The trait is defined over two types, the exception type and the virtual table
    219218type. Each exception type should have a single virtual table type.
    220 There are no actual assertions in this trait because currently the trait system
    221 cannot express them (adding such assertions would be part of
     219There are no actual assertions in this trait because the trait system
     220cannot express them yet (adding such assertions would be part of
    222221completing the virtual system). The imaginary assertions would probably come
    223222from a trait defined by the virtual system, and state that the exception type
    224 is a virtual type, is a descendent of @exception_t@ (the base exception type)
     223is a virtual type, is a descendant of @exception_t@ (the base exception type)
    225224and note its virtual table type.
    226225
     
    241240};
    242241\end{cfa}
    243 Both traits ensure a pair of types are an exception type and its virtual table,
     242Both traits ensure a pair of types are an exception type, its virtual table
     243type
    244244and defines one of the two default handlers. The default handlers are used
    245245as fallbacks and are discussed in detail in \vref{s:ExceptionHandling}.
     
    269269\section{Exception Handling}
    270270\label{s:ExceptionHandling}
    271 As stated, \CFA provides two kinds of exception handling: termination and resumption.
     271As stated,
     272\CFA provides two kinds of exception handling: termination and resumption.
    272273These twin operations are the core of \CFA's exception handling mechanism.
    273 This section covers the general patterns shared by the two operations and
    274 then go on to cover the details of each individual operation.
     274This section will cover the general patterns shared by the two operations and
     275then go on to cover the details each individual operation.
    275276
    276277Both operations follow the same set of steps.
    277 Both start with the user performing a raise on an exception.
     278Both start with the user preforming a raise on an exception.
    278279Then the exception propagates up the stack.
    279280If a handler is found the exception is caught and the handler is run.
    280 After that control returns to a point specific to the kind of exception.
    281 If the search fails a default handler is run, and if it returns, control
    282 continues after the raise. Note, the default handler may further change control flow rather than return.
     281After that control continues at a raise-dependent location.
     282If the search fails a default handler is run and, if it returns, then control
     283continues after the raise.
    283284
    284285This general description covers what the two kinds have in common.
    285 Differences include how propagation is performed, where exception continues
     286Differences include how propagation is preformed, where exception continues
    286287after an exception is caught and handled and which default handler is run.
    287288
    288289\subsection{Termination}
    289290\label{s:Termination}
    290 
    291291Termination handling is the familiar kind and used in most programming
    292292languages with exception handling.
     
    313313
    314314The throw copies the provided exception into managed memory to ensure
    315 the exception is not destroyed when the stack is unwound.
     315the exception is not destroyed if the stack is unwound.
    316316It is the user's responsibility to ensure the original exception is cleaned
    317317up whether the stack is unwound or not. Allocating it on the stack is
    318318usually sufficient.
    319319
    320 Then propagation starts the search. \CFA uses a ``first match" rule so
    321 matching is performed with the copied exception as the search continues.
    322 It starts from the throwing function and proceeds towards the base of the stack,
     320% How to say propagation starts, its first sub-step is the search.
     321Then propagation starts with the search. \CFA uses a ``first match" rule so
     322matching is preformed with the copied exception as the search continues.
     323It starts from the throwing function and proceeds towards base of the stack,
    323324from callee to caller.
    324325At each stack frame, a check is made for resumption handlers defined by the
     
    334335\end{cfa}
    335336When viewed on its own, a try statement simply executes the statements
    336 in \snake{GUARDED_BLOCK} and when those are finished, the try statement finishes.
     337in \snake{GUARDED_BLOCK} and when those are finished,
     338the try statement finishes.
    337339
    338340However, while the guarded statements are being executed, including any
    339 invoked functions, all the handlers in these statements are included on the search
    340 path. Hence, if a termination exception is raised, the search includes the added handlers associated with the guarded block and those further up the
    341 stack from the guarded block.
     341invoked functions, all the handlers in these statements are included in the
     342search path.
     343Hence, if a termination exception is raised these handlers may be matched
     344against the exception and may handle it.
    342345
    343346Exception matching checks the handler in each catch clause in the order
    344347they appear, top to bottom. If the representation of the raised exception type
    345348is the same or a descendant of @EXCEPTION_TYPE@$_i$ then @NAME@$_i$
    346 (if provided) is bound to a pointer to the exception and the statements in
    347 @HANDLER_BLOCK@$_i$ are executed.
    348 If control reaches the end of the handler, the exception is
     349(if provided) is
     350bound to a pointer to the exception and the statements in @HANDLER_BLOCK@$_i$
     351are executed. If control reaches the end of the handler, the exception is
    349352freed and control continues after the try statement.
    350353
    351 If no termination handler is found during the search, the default handler
    352 (\defaultTerminationHandler) visible at the raise statement is called.
    353 Through \CFA's trait system, the best match at the raise sight is used.
    354 This function is run and is passed the copied exception. If the default
    355 handler returns, control continues after the throw statement.
     354If no termination handler is found during the search then the default handler
     355(\defaultTerminationHandler) visible at the raise statement is run.
     356Through \CFA's trait system the best match at the raise statement will be used.
     357This function is run and is passed the copied exception.
     358If the default handler is run control continues after the raise statement.
    356359
    357360There is a global @defaultTerminationHandler@ that is polymorphic over all
    358 termination exception types. Since it is so general, a more specific handler can be
     361termination exception types.
     362Since it is so general a more specific handler can be
    359363defined and is used for those types, effectively overriding the handler
    360364for a particular exception type.
     
    370374matched a closure is taken from up the stack and executed,
    371375after which the raising function continues executing.
    372 These are most often used when a potentially repairable error occurs, some handler is found on the stack to fix it, and
    373 the raising function can continue with the correction.
    374 Another common usage is dynamic event analysis, \eg logging, without disrupting control flow.
    375 Note, if an event is raised and there is no interest, control continues normally.
    376 
    377 \PAB{We also have \lstinline{report} instead of \lstinline{throwResume}, \lstinline{recover} instead of \lstinline{catch}, and \lstinline{fixup} instead of \lstinline{catchResume}.
    378 You may or may not want to mention it. You can still stick with \lstinline{catch} and \lstinline{throw/catchResume} in the thesis.}
     376The common uses for resumption exceptions include
     377potentially repairable errors, where execution can continue in the same
     378function once the error is corrected, and
     379ignorable events, such as logging where nothing needs to happen and control
     380should always continue from the same place.
    379381
    380382A resumption raise is started with the @throwResume@ statement:
     
    382384throwResume EXPRESSION;
    383385\end{cfa}
     386\todo{Decide on a final set of keywords and use them everywhere.}
    384387It works much the same way as the termination throw.
    385388The expression must return a reference to a resumption exception,
     
    387390@is_resumption_exception@ at the call site.
    388391The assertions from this trait are available to
    389 the exception system, while handling the exception.
    390 
    391 Resumption does not need to copy the raised exception, as the stack is not unwound.
    392 The exception and
    393 any values on the stack remain in scope, while the resumption is handled.
    394 
    395 The EHM then begins propogation. The search starts from the raise in the
    396 resuming function and proceeds towards the base of the stack, from callee to caller.
     392the exception system while handling the exception.
     393
     394At run-time, no exception copy is made.
     395Resumption does not unwind the stack nor otherwise remove values from the
     396current scope, so there is no need to manage memory to keep things in scope.
     397
     398The EHM then begins propagation. The search starts from the raise in the
     399resuming function and proceeds towards the base of the stack,
     400from callee to caller.
    397401At each stack frame, a check is made for resumption handlers defined by the
    398402@catchResume@ clauses of a @try@ statement.
     
    412416kind of raise.
    413417When a try statement is executed, it simply executes the statements in the
    414 @GUARDED_BLOCK@ and then returns.
     418@GUARDED_BLOCK@ and then finishes.
    415419
    416420However, while the guarded statements are being executed, including any
    417 invoked functions, all the handlers in these statements are included on the search
    418 path. Hence, if a resumption exception is raised the search includes the added handlers associated with the guarded block and those further up the
    419 stack from the guarded block.
     421invoked functions, all the handlers in these statements are included in the
     422search path.
     423Hence, if a resumption exception is raised these handlers may be matched
     424against the exception and may handle it.
    420425
    421426Exception matching checks the handler in each catch clause in the order
     
    427432the raise statement that raised the handled exception.
    428433
    429 Like termination, if no resumption handler is found during the search, the default handler
    430 (\defaultResumptionHandler) visible at the raise statement is called.
    431 It uses the best match at the
    432 raise sight according to \CFA's overloading rules. The default handler is
    433 passed the exception given to the throw. When the default handler finishes
     434Like termination, if no resumption handler is found during the search,
     435the default handler (\defaultResumptionHandler) visible at the raise
     436statement is called. It will use the best match at the raise sight according
     437to \CFA's overloading rules. The default handler is
     438passed the exception given to the raise. When the default handler finishes
    434439execution continues after the raise statement.
    435440
    436 There is a global \defaultResumptionHandler{} that is polymorphic over all
    437 resumption exception types and preforms a termination throw on the exception.
    438 The \defaultTerminationHandler{} can be
    439 customized by introducing a new or better match as well.
     441There is a global \defaultResumptionHandler{} is polymorphic over all
     442resumption exceptions and preforms a termination throw on the exception.
     443The \defaultTerminationHandler{} can be overridden by providing a new
     444function that is a better match.
    440445
    441446\subsubsection{Resumption Marking}
    442447\label{s:ResumptionMarking}
    443 
    444448A key difference between resumption and termination is that resumption does
    445449not unwind the stack. A side effect that is that when a handler is matched
    446 and run, its try block (the guarded statements) and every try statement
    447 searched before it are still on the stack. Their existence can lead to the recursive
    448 resumption problem.
     450and run it's try block (the guarded statements) and every try statement
     451searched before it are still on the stack. There presence can lead to
     452the recursive resumption problem.
    449453
    450454The recursive resumption problem is any situation where a resumption handler
     
    459463\end{cfa}
    460464When this code is executed, the guarded @throwResume@ starts a
    461 search and matchs the handler in the @catchResume@ clause. This
    462 call is placed on the top of stack above the try-block. The second throw
    463 searchs the same try block and puts call another instance of the
    464 same handler on the stack leading to an infinite recursion.
     465search and matches the handler in the @catchResume@ clause. This
     466call is placed on the stack above the try-block. The second raise then
     467searches the same try block and puts another instance of the
     468same handler on the stack leading to infinite recursion.
    465469
    466470While this situation is trivial and easy to avoid, much more complex cycles
    467471can form with multiple handlers and different exception types.
    468472
    469 To prevent all of these cases, the exception search marks the try statements it visits.
    470 A try statement is marked when a match check is preformed with it and an
    471 exception. The statement is unmarked when the handling of that exception
    472 is completed or the search completes without finding a handler.
    473 While a try statement is marked, its handlers are never matched, effectify
    474 skipping over them to the next try statement.
     473To prevent all of these cases, a each try statement is ``marked" from the
     474time the exception search reaches it to either when the exception is being
     475handled completes the matching handler or when the search reaches the base
     476of the stack.
     477While a try statement is marked, its handlers are never matched, effectively
     478skipping over it to the next try statement.
    475479
    476480\begin{center}
     
    478482\end{center}
    479483
    480 These rules mirror what happens with termination.
    481 When a termination throw happens in a handler, the search does not look at
    482 any handlers from the original throw to the original catch because that
    483 part of the stack is unwound.
    484 A resumption raise in the same situation wants to search the entire stack,
    485 but with marking, the search does match exceptions for try statements at equivalent sections
    486 that would have been unwound by termination.
    487 
    488 The symmetry between resumption termination is why this pattern is picked.
    489 Other patterns, such as marking just the handlers that caught the exception, also work but
    490 lack the symmetry, meaning there are more rules to remember.
     484There are other sets of marking rules that could be used,
     485for instance, marking just the handlers that caught the exception,
     486would also prevent recursive resumption.
     487However, these rules mirror what happens with termination.
     488
     489The try statements that are marked are the ones that would be removed from
     490the stack if this was a termination exception, that is those on the stack
     491between the handler and the raise statement.
     492This symmetry applies to the default handler as well, as both kinds of
     493default handlers are run at the raise statement, rather than (physically
     494or logically) at the bottom of the stack.
     495% In early development having the default handler happen after
     496% unmarking was just more useful. We assume that will continue.
    491497
    492498\section{Conditional Catch}
    493 
    494499Both termination and resumption handler clauses can be given an additional
    495500condition to further control which exceptions they handle:
     
    504509did not match.
    505510
    506 The condition matching allows finer matching to check
     511The condition matching allows finer matching by checking
    507512more kinds of information than just the exception type.
    508513\begin{cfa}
     
    519524// Can't handle a failure relating to f2 here.
    520525\end{cfa}
    521 In this example, the file that experianced the IO error is used to decide
     526In this example the file that experienced the IO error is used to decide
    522527which handler should be run, if any at all.
    523528
     
    548553
    549554\subsection{Comparison with Reraising}
    550 
    551555A more popular way to allow handlers to match in more detail is to reraise
    552556the exception after it has been caught, if it could not be handled here.
    553 On the surface these two features seem interchangable.
    554 
    555 If @throw@ is used to start a termination reraise then these two statements
    556 have the same behaviour:
     557On the surface these two features seem interchangeable.
     558
     559If @throw;@ (no argument) starts a termination reraise,
     560which is the same as a raise but reuses the last caught exception,
     561then these two statements have the same behaviour:
    557562\begin{cfa}
    558563try {
     
    574579}
    575580\end{cfa}
    576 However, if there are further handlers after this handler only the first is
    577 check. For multiple handlers on a single try block that could handle the
    578 same exception, the equivalent translations to conditional catch becomes more complex, resulting is multiple nested try blocks for all possible reraises.
    579 So while catch-with-reraise is logically equivilant to conditional catch, there is a lexical explosion for the former.
    580 
    581 \PAB{I think the following discussion makes an incorrect assumption.
    582 A conditional catch CAN happen with the stack unwound.
    583 Roy talked about this issue in Section 2.3.3 here: \newline
    584 \url{http://plg.uwaterloo.ca/theses/KrischerThesis.pdf}}
    585 
    586 Specifically for termination handling, a
    587 conditional catch happens before the stack is unwound, but a reraise happens
    588 afterwards. Normally this might only cause you to loose some debug
    589 information you could get from a stack trace (and that can be side stepped
    590 entirely by collecting information during the unwind). But for \CFA there is
    591 another issue, if the exception is not handled the default handler should be
    592 run at the site of the original raise.
    593 
    594 There are two problems with this: the site of the original raise does not
    595 exist anymore and the default handler might not exist anymore. The site is
    596 always removed as part of the unwinding, often with the entirety of the
    597 function it was in. The default handler could be a stack allocated nested
    598 function removed during the unwind.
    599 
    600 This means actually trying to pretend the catch didn't happening, continuing
    601 the original raise instead of starting a new one, is infeasible.
    602 That is the expected behaviour for most languages and we can't replicate
    603 that behaviour.
     581That is, they will have the same behaviour in isolation.
     582Two things can expose differences between these cases.
     583
     584One is the existence of multiple handlers on a single try statement.
     585A reraise skips all later handlers on this try statement but a conditional
     586catch does not.
     587Hence, if an earlier handler contains a reraise later handlers are
     588implicitly skipped, with a conditional catch they are not.
     589Still, they are equivalently powerful,
     590both can be used two mimic the behaviour of the other,
     591as reraise can pack arbitrary code in the handler and conditional catches
     592can put arbitrary code in the predicate.
     593% I was struggling with a long explanation about some simple solutions,
     594% like repeating a condition on later handlers, and the general solution of
     595% merging everything together. I don't think it is useful though unless its
     596% for a proof.
     597% https://en.cppreference.com/w/cpp/language/throw
     598
     599The question then becomes ``Which is a better default?"
     600We believe that not skipping possibly useful handlers is a better default.
     601If a handler can handle an exception it should and if the handler can not
     602handle the exception then it is probably safer to have that explicitly
     603described in the handler itself instead of implicitly described by its
     604ordering with other handlers.
     605% Or you could just alter the semantics of the throw statement. The handler
     606% index is in the exception so you could use it to know where to start
     607% searching from in the current try statement.
     608% No place for the `goto else;` metaphor.
     609
     610The other issue is all of the discussion above assumes that the only
     611way to tell apart two raises is the exception being raised and the remaining
     612search path.
     613This is not true generally, the current state of the stack can matter in
     614a number of cases, even only for a stack trace after an program abort.
     615But \CFA has a much more significant need of the rest of the stack, the
     616default handlers for both termination and resumption.
     617
     618% For resumption it turns out it is possible continue a raise after the
     619% exception has been caught, as if it hadn't been caught in the first place.
     620This becomes a problem combined with the stack unwinding used in termination
     621exception handling.
     622The stack is unwound before the handler is installed, and hence before any
     623reraises can run. So if a reraise happens the previous stack is gone,
     624the place on the stack where the default handler was supposed to run is gone,
     625if the default handler was a local function it may have been unwound too.
     626There is no reasonable way to restore that information, so the reraise has
     627to be considered as a new raise.
     628This is the strongest advantage conditional catches have over reraising,
     629they happen before stack unwinding and avoid this problem.
     630
     631% The one possible disadvantage of conditional catch is that it runs user
     632% code during the exception search. While this is a new place that user code
     633% can be run destructors and finally clauses are already run during the stack
     634% unwinding.
     635%
     636% https://www.cplusplus.com/reference/exception/current_exception/
     637%   `exception_ptr current_exception() noexcept;`
     638% https://www.python.org/dev/peps/pep-0343/
    604639
    605640\section{Finally Clauses}
    606641\label{s:FinallyClauses}
    607 
    608642Finally clauses are used to preform unconditional clean-up when leaving a
    609643scope and are placed at the end of a try statement after any handler clauses:
     
    618652The @FINALLY_BLOCK@ is executed when the try statement is removed from the
    619653stack, including when the @GUARDED_BLOCK@ finishes, any termination handler
    620 finishes, or during an unwind.
     654finishes or during an unwind.
    621655The only time the block is not executed is if the program is exited before
    622656the stack is unwound.
     
    634668
    635669Not all languages with unwinding have finally clauses. Notably \Cpp does
    636 without it as destructors with RAII serve a similar role. Although destructors and
    637 finally clauses have overlapping usage cases, they have their own
    638 specializations, like top-level functions and lambda functions with closures.
    639 Destructors take more work if a number of unrelated, local variables without destructors or dynamically allocated variables must be passed for de-intialization.
    640 Maintaining this destructor during local-block modification is a source of errors.
    641 A finally clause places local de-intialization inline with direct access to all local variables.
     670without it as descructors, and the RAII design pattern, serve a similar role.
     671Although destructors and finally clauses can be used in the same cases,
     672they have their own strengths, similar to top-level function and lambda
     673functions with closures.
     674Destructors take more work for their first use, but if there is clean-up code
     675that needs to be run every time a type is used they soon become much easier
     676to set-up.
     677On the other hand finally clauses capture the local context, so is easy to
     678use when the clean-up is not dependent on the type of a variable or requires
     679information from multiple variables.
     680% To Peter: I think these are the main points you were going for.
    642681
    643682\section{Cancellation}
     
    652691raise, this exception is not used in matching only to pass information about
    653692the cause of the cancellation.
    654 (This restriction also means matching cannot fail so there is no default handler.)
     693(This also means matching cannot fail so there is no default handler.)
    655694
    656695After @cancel_stack@ is called the exception is copied into the EHM's memory
    657 and the current stack is
    658 unwound.
    659 The result of a cancellation depends on the kind of stack that is being unwound.
     696and the current stack is unwound.
     697The behaviour after that depends on the kind of stack being cancelled.
    660698
    661699\paragraph{Main Stack}
     
    664702After the main stack is unwound there is a program-level abort.
    665703
    666 There are two reasons for this semantics. The first is that it obviously had to do the abort
     704There are two reasons for these semantics.
     705The first is that it had to do this abort.
    667706in a sequential program as there is nothing else to notify and the simplicity
    668707of keeping the same behaviour in sequential and concurrent programs is good.
    669 \PAB{I do not understand this sentence. $\Rightarrow$ Also, even in concurrent programs, there is no stack that an innate connection
    670 to, so it would have be explicitly managed.}
     708Also, even in concurrent programs there may not currently be any other stacks
     709and even if other stacks do exist, main has no way to know where they are.
    671710
    672711\paragraph{Thread Stack}
     
    680719and an implicit join (from a destructor call). The explicit join takes the
    681720default handler (@defaultResumptionHandler@) from its calling context while
    682 the implicit join provides its own, which does a program abort if the
     721the implicit join provides its own; which does a program abort if the
    683722@ThreadCancelled@ exception cannot be handled.
    684723
    685 \PAB{Communication can occur during the lifetime of a thread using shared variable and \lstinline{waitfor} statements.
    686 Are you sure you mean communication here? Maybe you mean synchronization (rendezvous) point. $\Rightarrow$ Communication is done at join because a thread only has two points of
    687 communication with other threads: start and join.}
     724The communication and synchronization are done here because threads only have
     725two structural points (not dependent on user-code) where
     726communication/synchronization happens: start and join.
    688727Since a thread must be running to perform a cancellation (and cannot be
    689728cancelled from another stack), the cancellation must be after start and
    690 before the join, so join is use.
     729before the join, so join is used.
    691730
    692731% TODO: Find somewhere to discuss unwind collisions.
     
    695734a destructor and prevents cascading the error across multiple threads if
    696735the user is not equipped to deal with it.
    697 Also you can always add an explicit join if that is the desired behaviour.
     736It is always possible to add an explicit join if that is the desired behaviour.
     737
     738With explicit join and a default handler that triggers a cancellation, it is
     739possible to cascade an error across any number of threads, cleaning up each
     740in turn, until the error is handled or the main thread is reached.
    698741
    699742\paragraph{Coroutine Stack}
     
    701744satisfies the @is_coroutine@ trait.
    702745After a coroutine stack is unwound, control returns to the @resume@ function
    703 that most recently resumed it. The resume reports a
    704 @CoroutineCancelled@ exception, which contains references to the cancelled
     746that most recently resumed it. @resume@ reports a
     747@CoroutineCancelled@ exception, which contains a references to the cancelled
    705748coroutine and the exception used to cancel it.
    706749The @resume@ function also takes the \defaultResumptionHandler{} from the
    707 caller's context and passes it to the internal cancellation.
     750caller's context and passes it to the internal report.
    708751
    709752A coroutine knows of two other coroutines, its starter and its last resumer.
     
    711754(in terms of coroutine state) called resume on this coroutine, so the message
    712755is passed to the latter.
     756
     757With a default handler that triggers a cancellation, it is possible to
     758cascade an error across any number of coroutines, cleaning up each in turn,
     759until the error is handled or a thread stack is reached.
  • doc/theses/andrew_beach_MMath/future.tex

    r5a46e09 r660665f  
    33
    44\section{Language Improvements}
     5\todo{Future/Language Improvements seems to have gotten mixed up. It is
     6presented as ``waiting on language improvements" but really its more
     7non-research based impovements.}
    58\CFA is a developing programming language. As such, there are partially or
    69unimplemented features of the language (including several broken components)
    710that I had to workaround while building an exception handling system largely in
    811the \CFA language (some C components).  The following are a few of these
    9 issues, and once implemented/fixed, how this would affect the exception system.
     12issues, and once implemented/fixed, how they would affect the exception system.
    1013\begin{itemize}
    1114\item
    1215The implementation of termination is not portable because it includes
    13 hand-crafted assembly statements. These sections must be ported by hand to
     16hand-crafted assembly statements.
     17The existing compilers cannot translate that for other platforms and those
     18sections must be ported by hand to
    1419support more hardware architectures, such as the ARM processor.
    1520\item
     
    1722reference instead of a pointer. Since \CFA has a very general reference
    1823capability, programmers will want to use it. Once fixed, this capability should
    19 result in little or no change in the exception system.
     24result in little or no change in the exception system but simplify usage.
    2025\item
    2126Termination handlers cannot use local control-flow transfers, \eg by @break@,
     
    4146The virtual system should be completed. It was not supposed to be part of this
    4247project, but was thrust upon it to do exception inheritance; hence, only
    43 minimal work was done. A draft for a complete virtual system is available but
     48minimal work is done. A draft for a complete virtual system is available but
    4449it is not finalized.  A future \CFA project is to complete that work and then
    4550update the exception system that uses the current version.
     
    6772bad software engineering.
    6873
    69 Non-local/concurrent requires more coordination between the concurrency system
     74Non-local/concurrent raise requires more
     75coordination between the concurrency system
    7076and the exception system. Many of the interesting design decisions centre
    71 around masking (controlling which exceptions may be thrown at a stack). It
     77around masking, \ie controlling which exceptions may be thrown at a stack. It
    7278would likely require more of the virtual system and would also effect how
    7379default handlers are set.
     
    8591
    8692\section{Checked Exceptions}
    87 Checked exceptions make exceptions part of a function's type by adding the
     93Checked exceptions make exceptions part of a function's type by adding an
    8894exception signature. An exception signature must declare all checked
    89 exceptions that could propogate from the function (either because they were
     95exceptions that could propagate from the function (either because they were
    9096raised inside the function or came from a sub-function). This improves safety
    9197by making sure every checked exception is either handled or consciously
     
    9399
    94100However checked exceptions were never seriously considered for this project
    95 for two reasons. The first is due to time constraints, even copying an
    96 existing checked exception system would be pushing the remaining time and
    97 trying to address the second problem would take even longer. The second
    98 problem is that checked exceptions have some real usability trade-offs in
     101because they have significant trade-offs in usablity and code reuse in
    99102exchange for the increased safety.
    100 
    101103These trade-offs are most problematic when trying to pass exceptions through
    102104higher-order functions from the functions the user passed into the
    103105higher-order function. There are no well known solutions to this problem
    104 that were statifactory for \CFA (which carries some of C's flexability
    105 over safety design) so one would have to be researched and developed.
     106that were satisfactory for \CFA (which carries some of C's flexibility
     107over safety design) so additional research is needed.
    106108
    107 Follow-up work might add checked exceptions to \CFA, possibly using
    108 polymorphic exception signatures, a form of tunneling\cite{Zhang19} or
     109Follow-up work might add some form of checked exceptions to \CFA,
     110possibly using polymorphic exception signatures,
     111a form of tunneling\cite{Zhang19} or
    109112checked and unchecked raises.
    110113
     
    150153For instance, resumption could be extended to cover this use by allowing local
    151154control flow out of it. This approach would require an unwind as part of the
    152 transition as there are stack frames that have to be removed.  This approach
    153 means there is no notify raise, but because \CFA does not have exception
    154 signatures, a termination can be thrown from within any resumption handler so
    155 there is already a way to do mimic this in existing \CFA.
     155transition as there are stack frames that have to be removed between where
     156the resumption handler is installed and where it is defined.
     157This approach would not require, but might benefit from, a special statement
     158to leave the handler.
     159Currently, mimicking this behaviour in \CFA is possible by throwing a
     160termination inside a resumption handler.
    156161
    157162% Maybe talk about the escape; and escape CONTROL_STMT; statements or how
  • doc/theses/andrew_beach_MMath/implement.tex

    r5a46e09 r660665f  
    22\label{c:implement}
    33
    4 The implementation work for this thesis covers two components: the virtual
     4% Local Helpers:
     5\newcommand\transformline[1][becomes...]{
     6  \hrulefill#1\hrulefill
     7  \medskip
     8}
     9
     10The implementation work for this thesis covers the two components: virtual
    511system and exceptions. Each component is discussed in detail.
    612
     
    2127\todo{Talk about constructors for virtual types (after they are working).}
    2228
    23 This is what binds an instance of a virtual type to a virtual table. This
    24 pointer can be used as an identity check. It can also be used to access the
     29The virtual table pointer binds an instance of a virtual type
     30to a virtual table.
     31The pointer is also the table's id and how the system accesses the
    2532virtual table and the virtual members there.
    2633
    2734\subsection{Type Id}
    2835Every virtual type has a unique id.
    29 Type ids can be compared for equality (the types reperented are the same)
     36Type ids can be compared for equality,
     37which checks if the types reperented are the same,
    3038or used to access the type's type information.
    3139The type information currently is only the parent's type id or, if the
    32 type has no parent, zero.
     40type has no parent, the null pointer.
    3341
    3442The id's are implemented as pointers to the type's type information instance.
    35 Derefencing the pointer gets the type information.
    36 By going back-and-forth between the type id and
    37 the type info one can find every ancestor of a virtual type.
    38 It also pushes the issue of creating a unique value (for
     43Dereferencing the pointer gets the type information.
     44The ancestors of a virtual type are found by traversing type ids through
     45the type information.
     46The information pushes the issue of creating a unique value (for
    3947the type id) to the problem of creating a unique instance (for type
    40 information) which the linker can solve.
    41 
    42 Advanced linker support is required because there is no place that appears
    43 only once to attach the type information to. There should be one structure
    44 definition but it is included in multiple translation units. Each virtual
    45 table definition should be unique but there are an arbitrary number of thoses.
    46 So the special section prefix \texttt{.gnu.linkonce} is used.
    47 With a unique suffix (making the entire section name unique) the linker will
    48 remove multiple definition making sure only one version exists after linking.
    49 Then it is just a matter of making sure there is a unique name for each type.
    50 
    51 This is done in three phases.
    52 The first phase is to generate a new structure definition to store the type
     48information), which the linker can solve.
     49
     50The advanced linker support is used here to avoid having to create
     51a new declaration to attach this data to.
     52With C/\CFA's header/implementation file divide for something to appear
     53exactly once it must come from a declaration that appears in exactly one
     54implementation file; the declarations in header files may exist only once
     55they can be included in many different translation units.
     56Therefore, structure's declaration will not work.
     57Neither will attaching the type information to the virtual table -- although
     58a vtable declarations are in implemention files they are not unique, see
     59\autoref{ss:VirtualTable}.
     60Instead the same type information is generated multiple times and then
     61the new attribute \snake{cfa_linkone} is used to removed duplicates.
     62
     63Type information is constructed as follows:
     64\begin{enumerate}
     65\item
     66Use the type's name to generate a name for the type information structure.
     67This is saved so it may be reused.
     68\item
     69Generate a new structure definition to store the type
    5370information. The layout is the same in each case, just the parent's type id,
    54 but the types are changed.
    55 The structure's name is change, it is based off the virtual type's name, and
    56 the type of the parent's type id.
     71but the types used change from instance to instance.
     72The generated name is used for both this structure and, if relivant, the
     73parent pointer.
    5774If the virtual type is polymorphic then the type information structure is
    5875polymorphic as well, with the same polymorphic arguments.
    59 
    60 The second phase is to generate an instance of the type information with a
    61 almost unique name, generated by mangling the virtual type name.
    62 
    63 The third phase is implicit with \CFA's overloading scheme. \CFA mangles
    64 names with type information so that all of the symbols exported to the linker
    65 are unique even if in \CFA code they are the same. Having two declarations
    66 with the same name and same type is forbidden because it is impossible for
    67 overload resolution to pick between them. This is why a unique type is
    68 generated for each virtual type.
    69 Polymorphic information is included in this mangling so polymorphic
    70 types will have seperate instances for each set of polymorphic arguments.
    71 
    72 \begin{cfa}
    73 struct TYPE_ID_TYPE {
    74         PARENT_ID_TYPE const * parent;
     76\item
     77A seperate name for instances is generated from the type's name.
     78\item
     79The definition is generated and initialised.
     80The parent id is set to the null pointer or to the address of the parent's
     81type information instance. Name resolution handles the rest.
     82\item
     83\CFA's name mangler does its regular name mangling encoding the type of
     84the declaration into the instance name. This gives a completely unique name
     85including different instances of the same polymorphic type.
     86\end{enumerate}
     87\todo{The list is making me realise, some of this isn't ordered.}
     88
     89Writing that code manually, with helper macros for the early name mangling,
     90would look like this:
     91\begin{cfa}
     92struct INFO_TYPE(TYPE) {
     93        INFO_TYPE(PARENT) const * parent;
    7594};
    7695
    7796__attribute__((cfa_linkonce))
    78 TYPE_ID_TYPE const TYPE_ID_NAME = {
    79         &PARENT_ID_NAME,
     97INFO_TYPE(TYPE) const INFO_NAME(TYPE) = {
     98        &INFO_NAME(PARENT),
    8099};
    81100\end{cfa}
    82101
    83 \subsubsection{cfa\_linkonce Attribute}
     102\subsubsection{\lstinline{cfa\_linkonce} Attribute}
     103% I just realised: This is an extension of the inline keyword.
     104% An extension of C's at least, it is very similar to C++'s.
    84105Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}.
    85 This attribute can be put on an object or function definition
    86 (any global declaration with a name and a type).
    87 This allows you to define that object or function multiple times.
    88 All definitions should have the link-once attribute on them and all should
    89 be identical.
    90 
    91 The simplist way to use it is to put a definition in a header where the
    92 forward declaration would usually go.
    93 This is how it is used for type-id instances. There was is no unique location
    94 associated with a type except for the type definition which is in a header.
    95 This allows the unique type-id object to be generated there.
    96 
    97 Internally @cfa_linkonce@ removes all @section@ attributes
    98 from the declaration (as well as itself) and replaces them with
     106This attribute is attached to an object or function definition
     107(any global declaration with a name and a type)
     108allowing it to be defined multiple times.
     109All matching definitions mush have the link-once attribute
     110and their implementations should be identical as well.
     111
     112A single definition with the attribute can be included in a header
     113file as if it was a forward declaration, except no definition is required.
     114
     115This technique is used for type-id instances. A link-once definition is
     116generated each time the structure is seen. This will result in multiple
     117copies but the link-once attribute ensures all but one are removed for a
     118unique instance.
     119
     120Internally, @cfa_linkonce@ is replaced with
    99121@section(".gnu.linkonce.NAME")@ where \texttt{NAME} is replaced by the
    100122mangled name of the object.
     123Any other @section@ attributes are removed from the declaration.
    101124The prefix \texttt{.gnu.linkonce} in section names is recognized by the
    102 linker. If two of these sections with the same name, including everything
    103 that comes after the special prefix, then only one will be used and the other
    104 will be discarded.
     125linker. If two of these sections appear with the same name, including
     126everything that comes after the special prefix, then only one is used
     127and the other is discarded.
    105128
    106129\subsection{Virtual Table}
     130\label{ss:VirtualTable}
    107131Each virtual type has a virtual table type that stores its type id and
    108132virtual members.
     
    113137
    114138The layout always comes in three parts.
     139\todo{Add labels to the virtual table layout figure.}
    115140The first section is just the type id at the head of the table. It is always
    116 there to ensure that
     141there to ensure that it can be found even when the accessing code does not
     142know which virtual type it has.
    117143The second section are all the virtual members of the parent, in the same
    118144order as they appear in the parent's virtual table. Note that the type may
     
    133159prefix that has the same layout and types as its parent virtual table.
    134160This, combined with the fixed offset to the virtual table pointer, means that
    135 for any virtual type it doesn't matter if we have it or any of its
    136 descendants, it is still always safe to access the virtual table through
    137 the virtual table pointer.
    138 From there it is safe to check the type id to identify the exact type of the
     161for any virtual type, it is always safe to access its virtual table and,
     162from there, it is safe to check the type id to identify the exact type of the
    139163underlying object, access any of the virtual members and pass the object to
    140164any of the method-like virtual members.
    141165
    142 When a virtual table is declared the user decides where to declare it and its
     166When a virtual table is declared, the user decides where to declare it and its
    143167name. The initialization of the virtual table is entirely automatic based on
    144168the context of the declaration.
    145169
    146 The type id is always fixed, each virtual table type will always have one
     170The type id is always fixed; with each virtual table type having
    147171exactly one possible type id.
    148 The virtual members are usually filled in by resolution. The best match for
    149 a given name and type at the declaration site is filled in.
    150 There are two exceptions to that rule: the @size@ field is the type's size
    151 and is set to the result of a @sizeof@ expression, the @align@ field is the
    152 type's alignment and similarly uses an @alignof@ expression.
     172The virtual members are usually filled in by type resolution.
     173The best match for a given name and type at the declaration site is used.
     174There are two exceptions to that rule: the @size@ field, the type's size,
     175is set using a @sizeof@ expression and the @align@ field, the
     176type's alignment, is set using an @alignof@ expression.
    153177
    154178\subsubsection{Concurrency Integration}
    155179Coroutines and threads need instances of @CoroutineCancelled@ and
    156180@ThreadCancelled@ respectively to use all of their functionality. When a new
    157 data type is declared with @coroutine@ or @thread@ the forward declaration for
     181data type is declared with @coroutine@ or @thread@, a forward declaration for
    158182the instance is created as well. The definition of the virtual table is created
    159183at the definition of the main function.
     184
     185This is showned through code re-writing in
     186\autoref{f:ConcurrencyTypeTransformation} and
     187\autoref{f:ConcurrencyMainTransformation}.
     188In both cases the original declaration is not modified,
     189only new ones are added.
    160190
    161191\begin{figure}
     
    165195};
    166196\end{cfa}
     197
     198\transformline[appends...]
    167199
    168200\begin{cfa}
     
    175207extern CoroutineCancelled_vtable & _default_vtable;
    176208\end{cfa}
    177 
     209\caption{Concurrency Type Transformation}
     210\label{f:ConcurrencyTypeTransformation}
     211\end{figure}
     212
     213\begin{figure}
    178214\begin{cfa}
    179215void main(Example & this) {
     
    181217}
    182218\end{cfa}
     219
     220\transformline[appends...]
    183221
    184222\begin{cfa}
     
    191229        &_default_vtable_object_declaration;
    192230\end{cfa}
    193 \caption{Concurrency Transformations}
    194 \label{f:ConcurrencyTransformations}
     231\caption{Concurrency Main Transformation}
     232\label{f:ConcurrencyMainTransformation}
    195233\end{figure}
    196 \todo{Improve Concurrency Transformations figure.}
    197234
    198235\subsection{Virtual Cast}
     
    211248the cast target is passed in as @child@.
    212249
    213 For C generation both arguments and the result are wrapped with type casts.
    214 There is also an internal store inside the compiler to make sure that the
     250For generated C code wraps both arguments and the result with type casts.
     251There is also an internal check inside the compiler to make sure that the
    215252target type is a virtual type.
    216253% It also checks for conflicting definitions.
    217254
    218 The virtual cast either returns the original pointer as a new type or null.
    219 So the function just does the parent check and returns the approprate value.
     255The virtual cast either returns the original pointer or the null pointer
     256as the new type.
     257So the function does the parent check and returns the appropriate value.
    220258The parent check is a simple linear search of child's ancestors using the
    221259type information.
     
    229267% resumption doesn't as well.
    230268
    231 % Many modern languages work with an interal stack that function push and pop
     269% Many modern languages work with an internal stack that function push and pop
    232270% their local data to. Stack unwinding removes large sections of the stack,
    233271% often across functions.
     
    236274stack. On function entry and return, unwinding is handled directly by the
    237275call/return code embedded in the function.
    238 In many cases the position of the instruction pointer (relative to parameter
     276In many cases, the position of the instruction pointer (relative to parameter
    239277and local declarations) is enough to know the current size of the stack
    240278frame.
    241279
    242280Usually, the stack-frame size is known statically based on parameter and
    243 local variable declarations. Even with dynamic stack-size the information
    244 to determain how much of the stack has to be removed is still contained
     281local variable declarations. Even with dynamic stack-size, the information
     282to determine how much of the stack has to be removed is still contained
    245283within the function.
    246284Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
    247285bumping the hardware stack-pointer up or down as needed.
    248 Constructing/destructing values on the stack takes longer put in terms of
    249 figuring out what needs to be done is of similar complexity.
     286Constructing/destructing values within a stack frame has
     287a similar complexity but can add additional work and take longer.
    250288
    251289Unwinding across multiple stack frames is more complex because that
     
    261299reseting to a snap-shot of an arbitrary but existing function frame on the
    262300stack. It is up to the programmer to ensure the snap-shot is valid when it is
    263 reset and that all required clean-up from the unwound stacks is preformed.
    264 This approach is fragile and forces a work onto the surounding code.
    265 
    266 With respect to that work forced onto the surounding code,
     301reset and that all required clean-up from the unwound stacks is performed.
     302This approach is fragile and requires extra work in the surrounding code.
     303
     304With respect to the extra work in the surounding code,
    267305many languages define clean-up actions that must be taken when certain
    268306sections of the stack are removed. Such as when the storage for a variable
    269307is removed from the stack or when a try statement with a finally clause is
    270308(conceptually) popped from the stack.
    271 None of these should be handled by the user, that would contradict the
    272 intention of these features, so they need to be handled automatically.
    273 
    274 To safely remove sections of the stack the language must be able to find and
     309None of these should be handled by the user --- that would contradict the
     310intention of these features --- so they need to be handled automatically.
     311
     312To safely remove sections of the stack, the language must be able to find and
    275313run these clean-up actions even when removing multiple functions unknown at
    276314the beginning of the unwinding.
     
    294332current stack frame, and what handlers should be checked. Theoretically, the
    295333LSDA can contain any information but conventionally it is a table with entries
    296 representing regions of the function and what has to be done there during
     334representing regions of a function and what has to be done there during
    297335unwinding. These regions are bracketed by instruction addresses. If the
    298336instruction pointer is within a region's start/end, then execution is currently
     
    314352int avar __attribute__(( cleanup(clean_up) ));
    315353\end{cfa}
    316 The attribue is used on a variable and specifies a function,
     354The attribute is used on a variable and specifies a function,
    317355in this case @clean_up@, run when the variable goes out of scope.
    318 This is enough to mimic destructors, but not try statements which can effect
     356This feature is enough to mimic destructors,
     357but not try statements which can effect
    319358the unwinding.
    320359
    321 To get full unwinding support all of this has to be done directly with
    322 assembly and assembler directives. Partiularly the cfi directives
     360To get full unwinding support, all of these features must be handled directly
     361in assembly and assembler directives; partiularly the cfi directives
    323362\snake{.cfi_lsda} and \snake{.cfi_personality}.
    324363
     
    327366section covers some of the important parts of the interface.
    328367
    329 A personality function can preform different actions depending on how it is
     368A personality function can perform different actions depending on how it is
    330369called.
    331370\begin{lstlisting}
     
    364403
    365404The @exception_class@ argument is a copy of the
    366 \code{C}{exception}'s @exception_class@ field.
    367 This a number that identifies the exception handling mechanism that created
    368 the
    369 
    370 The \code{C}{exception} argument is a pointer to the user
     405\code{C}{exception}'s @exception_class@ field,
     406which is a number that identifies the exception handling mechanism
     407that created the exception.
     408
     409The \code{C}{exception} argument is a pointer to a user
    371410provided storage object. It has two public fields: the @exception_class@,
    372411which is described above, and the @exception_cleanup@ function.
    373 The clean-up function is used by the EHM to clean-up the exception if it
     412The clean-up function is used by the EHM to clean-up the exception, if it
    374413should need to be freed at an unusual time, it takes an argument that says
    375414why it had to be cleaned up.
     
    382421messages for special cases (some of which should never be used by the
    383422personality function) and error codes. However, unless otherwise noted, the
    384 personality function should always return @_URC_CONTINUE_UNWIND@.
     423personality function always returns @_URC_CONTINUE_UNWIND@.
    385424
    386425\subsection{Raise Exception}
    387 Raising an exception is the central function of libunwind and it performs a
     426Raising an exception is the central function of libunwind and it performs
    388427two-staged unwinding.
    389428\begin{cfa}
     
    472511% catches. Talk about GCC nested functions.
    473512
    474 \CFA termination exceptions use libunwind heavily because they match \Cpp
     513\CFA termination exceptions use libunwind heavily because they match
    475514\Cpp exceptions closely. The main complication for \CFA is that the
    476515compiler generates C code, making it very difficult to generate the assembly to
     
    485524
    486525\begin{figure}
     526\centering
    487527\input{exception-layout}
    488528\caption{Exception Layout}
    489529\label{f:ExceptionLayout}
    490530\end{figure}
    491 \todo*{Convert the exception layout to an actual diagram.}
    492 
    493 Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}).
     531
     532Exceptions are stored in variable-sized blocks
     533(see \autoref{f:ExceptionLayout}).
    494534The first component is a fixed-sized data structure that contains the
    495535information for libunwind and the exception system. The second component is an
     
    498538@_Unwind_Exception@ to the entire node.
    499539
    500 Multipe exceptions can exist at the same time because exceptions can be
     540Multiple exceptions can exist at the same time because exceptions can be
    501541raised inside handlers, destructors and finally blocks.
    502542Figure~\vref{f:MultipleExceptions} shows a program that has multiple
    503543exceptions active at one time.
    504544Each time an exception is thrown and caught the stack unwinds and the finally
    505 clause runs. This will throw another exception (until @num_exceptions@ gets
    506 high enough) which must be allocated. The previous exceptions may not be
     545clause runs. This handler throws another exception (until @num_exceptions@ gets
     546high enough), which must be allocated. The previous exceptions may not be
    507547freed because the handler/catch clause has not been run.
    508 So the EHM must keep them alive while it allocates exceptions for new throws.
     548Therefore, the EHM must keep all unhandled exceptions alive
     549while it allocates exceptions for new throws.
    509550
    510551\begin{figure}
     
    559600\todo*{Work on multiple exceptions code sample.}
    560601
    561 All exceptions are stored in nodes which are then linked together in lists,
     602All exceptions are stored in nodes, which are then linked together in lists
    562603one list per stack, with the
    563604list head stored in the exception context. Within each linked list, the most
     
    566607exception is being handled. The exception at the head of the list is currently
    567608being handled, while other exceptions wait for the exceptions before them to be
    568 removed.
     609handled and removed.
    569610
    570611The virtual members in the exception's virtual table provide the size of the
     
    573614exception into managed memory. After the exception is handled, the free
    574615function is used to clean up the exception and then the entire node is
    575 passed to free so the memory can be given back to the heap.
     616passed to free, returning the memory back to the heap.
    576617
    577618\subsection{Try Statements and Catch Clauses}
    578619The try statement with termination handlers is complex because it must
    579 compensate for the lack of assembly-code generated from \CFA. Libunwind
     620compensate for the C code-generation versus
     621assembly-code generated from \CFA. Libunwind
    580622requires an LSDA and personality function for control to unwind across a
    581623function. The LSDA in particular is hard to mimic in generated C code.
     
    592634embedded assembly. This assembly code is handcrafted using C @asm@ statements
    593635and contains
    594 enough information for the single try statement the function repersents.
     636enough information for a single try statement the function repersents.
    595637
    596638The three functions passed to try terminate are:
    597639\begin{description}
    598 \item[try function:] This function is the try block, all the code inside the
    599 try block is placed inside the try function. It takes no parameters and has no
     640\item[try function:] This function is the try block, it is where all the code
     641from inside the try block is placed. It takes no parameters and has no
    600642return value. This function is called during regular execution to run the try
    601643block.
     
    609651handler that matches the exception.
    610652
    611 \item[handler function:] This function handles the exception. It takes a
     653\item[handler function:] This function handles the exception, and contains
     654all the code from the handlers in the try statement, joined with a switch
     655statement on the handler's id.
     656It takes a
    612657pointer to the exception and the handler's id and returns nothing. It is called
    613 after the cleanup phase. It is constructed by stitching together the bodies of
    614 each handler and dispatches to the selected handler.
     658after the cleanup phase.
    615659\end{description}
    616660All three functions are created with GCC nested functions. GCC nested functions
    617 can be used to create closures, functions that can refer to the state of other
     661can be used to create closures,
     662in other words functions that can refer to the state of other
    618663functions on the stack. This approach allows the functions to refer to all the
    619664variables in scope for the function containing the @try@ statement. These
     
    623668Using this pattern, \CFA implements destructors with the cleanup attribute.
    624669
     670\autoref{f:TerminationTransformation} shows the pattern used to transform
     671a \CFA try statement with catch clauses into the approprate C functions.
     672\todo{Explain the Termination Transformation figure.}
     673
    625674\begin{figure}
    626675\begin{cfa}
     
    633682}
    634683\end{cfa}
     684
     685\transformline
    635686
    636687\begin{cfa}
     
    683734% The stack-local data, the linked list of nodes.
    684735
    685 Resumption simpler to implement than termination
     736Resumption is simpler to implement than termination
    686737because there is no stack unwinding.
    687738Instead of storing the data in a special area using assembly,
     
    692743The nodes are stored in order, with the more recent try statements closer
    693744to the head of the list.
    694 Instead of traversing the stack resumption handling traverses the list.
    695 At each node the EHM checks to see if the try statement the node repersents
     745Instead of traversing the stack, resumption handling traverses the list.
     746At each node, the EHM checks to see if the try statement the node repersents
    696747can handle the exception. If it can, then the exception is handled and
    697748the operation finishes, otherwise the search continues to the next node.
    698749If the search reaches the end of the list without finding a try statement
    699 that can handle the exception the default handler is executed and the
     750that can handle the exception, the default handler is executed and the
    700751operation finishes.
    701752
    702 In each node is a handler function which does most of the work there.
    703 The handler function is passed the raised the exception and returns true
    704 if the exception is handled and false if it cannot be handled here.
    705 
    706 For each @catchResume@ clause the handler function will:
    707 check to see if the raised exception is a descendant type of the declared
    708 exception type, if it is and there is a conditional expression then it will
    709 run the test, if both checks pass the handling code for the clause is run
    710 and the function returns true, otherwise it moves onto the next clause.
    711 If this is the last @catchResume@ clause then instead of moving onto
    712 the next clause the function returns false as no handler could be found.
     753Each node has a handler function that does most of the work.
     754The handler function is passed the raised exception and returns true
     755if the exception is handled and false otherwise.
     756
     757The handler function checks each of its internal handlers in order,
     758top-to-bottom, until it funds a match. If a match is found that handler is
     759run, after which the function returns true, ignoring all remaining handlers.
     760If no match is found the function returns false.
     761The match is performed in two steps, first a virtual cast is used to see
     762if the thrown exception is an instance of the declared exception or one of
     763its descendant type, then check to see if passes the custom predicate if one
     764is defined. This ordering gives the type guarantee used in the predicate.
     765
     766\autoref{f:ResumptionTransformation} shows the pattern used to transform
     767a \CFA try statement with catch clauses into the approprate C functions.
     768\todo{Explain the Resumption Transformation figure.}
    713769
    714770\begin{figure}
     
    722778}
    723779\end{cfa}
     780
     781\transformline
    724782
    725783\begin{cfa}
     
    753811
    754812% Recursive Resumption Stuff:
    755 Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
     813\autoref{f:ResumptionMarking} shows search skipping
     814(see \vpageref{s:ResumptionMarking}), which ignores parts of
    756815the stack
    757816already examined, is accomplished by updating the front of the list as the
     
    759818is updated to the next node of the current node. After the search is complete,
    760819successful or not, the head of the list is reset.
    761 
     820% No paragraph?
    762821This mechanism means the current handler and every handler that has already
    763822been checked are not on the list while a handler is run. If a resumption is
    764 thrown during the handling of another resumption the active handlers and all
     823thrown during the handling of another resumption, the active handlers and all
    765824the other handler checked up to this point are not checked again.
    766 
    767 This structure also supports new handler added while the resumption is being
     825% No paragraph?
     826This structure also supports new handlers added while the resumption is being
    768827handled. These are added to the front of the list, pointing back along the
    769 stack -- the first one points over all the checked handlers -- and the ordering
    770 is maintained.
     828stack --- the first one points over all the checked handlers ---
     829and the ordering is maintained.
    771830
    772831\begin{figure}
     
    774833\caption{Resumption Marking}
    775834\label{f:ResumptionMarking}
    776 \todo*{Convert Resumption Marking into a line figure.}
     835\todo*{Label Resumption Marking to aid clarity.}
    777836\end{figure}
    778837
    779838\label{p:zero-cost}
    780 Note, the resumption implementation has a cost for entering/exiting a @try@
    781 statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
     839Finally, the resumption implementation has a cost for entering/exiting a try
     840statement with @catchResume@ clauses, whereas a try statement with @catch@
    782841clauses has zero-cost entry/exit. While resumption does not need the stack
    783842unwinding and cleanup provided by libunwind, it could use the search phase to
     
    810869
    811870The first step of cancellation is to find the cancelled stack and its type:
    812 coroutine or thread. Fortunately, the thread library stores the main thread
    813 pointer and the current thread pointer, and every thread stores a pointer to
    814 its main coroutine and the coroutine it is currently executing.
    815 \todo*{Consider adding a description of how threads are coroutines.}
    816 
    817 If a the current thread's main and current coroutines are the same then the
    818 current stack is a thread stack. Furthermore it is easy to compare the
    819 current thread to the main thread to see if they are the same. And if this
    820 is not a thread stack then it must be a coroutine stack.
     871coroutine, thread or main thread.
     872In \CFA, a thread (the construct the user works with) is a user-level thread
     873(point of execution) paired with a coroutine, the thread's main coroutine.
     874The thread library also stores pointers to the main thread and the current
     875thread.
     876If the current thread's main and current coroutines are the same then the
     877current stack is a thread stack, otherwise it is a coroutine stack.
     878If the current stack is a thread stack, it is also the main thread stack
     879if and only if the main and current threads are the same.
    821880
    822881However, if the threading library is not linked, the sequential execution is on
    823882the main stack. Hence, the entire check is skipped because the weak-symbol
    824 function is loaded. Therefore, a main thread cancellation is unconditionally
     883function is loaded. Therefore, main thread cancellation is unconditionally
    825884performed.
    826885
    827886Regardless of how the stack is chosen, the stop function and parameter are
    828887passed to the forced-unwind function. The general pattern of all three stop
    829 functions is the same: they continue unwinding until the end of stack and
    830 then preform their transfer.
     888functions is the same: continue unwinding until the end of stack and
     889then preform the appropriate transfer.
    831890
    832891For main stack cancellation, the transfer is just a program abort.
     
    834893For coroutine cancellation, the exception is stored on the coroutine's stack,
    835894and the coroutine context switches to its last resumer. The rest is handled on
    836 the backside of the resume, which check if the resumed coroutine is
     895the backside of the resume, which checks if the resumed coroutine is
    837896cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
    838897and a @CoroutineCancelled@ exception is constructed and loaded with the
  • doc/theses/andrew_beach_MMath/intro.tex

    r5a46e09 r660665f  
    11\chapter{Introduction}
    22
    3 \PAB{Stay in the present tense. \newline
    4 \url{https://plg.uwaterloo.ca/~pabuhr/technicalWriting.shtml}}
    5 \newline
    6 \PAB{Note, \lstinline{lstlisting} normally bolds keywords. None of the keywords in your thesis are bolded.}
    7 
    8 % Talk about Cforall and exceptions generally.
    9 %This thesis goes over the design and implementation of the exception handling
    10 %mechanism (EHM) of
    11 %\CFA (pernounced sea-for-all and may be written Cforall or CFA).
    12 Exception handling provides alternative dynamic inter-function control flow.
     3% The highest level overview of Cforall and EHMs. Get this done right away.
     4This thesis goes over the design and implementation of the exception handling
     5mechanism (EHM) of
     6\CFA (pronounced sea-for-all and may be written Cforall or CFA).
     7\CFA is a new programming language that extends C, that maintains
     8backwards-compatibility while introducing modern programming features.
     9Adding exception handling to \CFA gives it new ways to handle errors and
     10make other large control-flow jumps.
     11
     12% Now take a step back and explain what exceptions are generally.
     13Exception handling provides dynamic inter-function control flow.
    1314There are two forms of exception handling covered in this thesis:
    1415termination, which acts as a multi-level return,
    1516and resumption, which is a dynamic function call.
    16 Note, termination exception handling is so common it is often assumed to be the only form.
    17 Lesser know derivations of inter-function control flow are continuation passing in Lisp~\cite{CommonLisp}.
     17Termination handling is much more common,
     18to the extent that it is often seen
     19This seperation is uncommon because termination exception handling is so
     20much more common that it is often assumed.
     21% WHY: Mention other forms of continuation and \cite{CommonLisp} here?
     22A language's EHM is the combination of language syntax and run-time
     23components that are used to construct, raise and handle exceptions,
     24including all control flow.
    1825
    1926Termination exception handling allows control to return to any previous
     
    2431\end{center}
    2532
    26 Resumption exception handling calls a function, but asks the functions on the
    27 stack what function that is.
     33Resumption exception handling seaches the stack for a handler and then calls
     34it without adding or removing any other stack frames.
    2835\todo{Add a diagram showing control flow for resumption.}
    2936
     
    3542most of the cost only when the error actually occurs.
    3643
    37 % Overview of exceptions in Cforall.
    38 
    39 \PAB{You need section titles here. Don't take them out.}
    40 
    4144\section{Thesis Overview}
    42 
    43 This thesis goes over the design and implementation of the exception handling
    44 mechanism (EHM) of
    45 \CFA (pernounced sea-for-all and may be written Cforall or CFA).
    46 %This thesis describes the design and implementation of the \CFA EHM.
     45This work describes the design and implementation of the \CFA EHM.
    4746The \CFA EHM implements all of the common exception features (or an
    4847equivalent) found in most other EHMs and adds some features of its own.
     
    7776harder to replicate in other programming languages.
    7877
    79 \section{Background}
    80 
    8178% Talk about other programming languages.
    8279Some existing programming languages that include EHMs/exception handling
     
    8481exceptions which unwind the stack as part of the
    8582Exceptions also can replace return codes and return unions.
    86 In functional languages will also sometimes fold exceptions into monads.
    87 
    88 \PAB{You must demonstrate knowledge of background material here.
    89 It should be at least a full page.}
    90 
    91 \section{Contributions}
    9283
    9384The contributions of this work are:
     
    10293\end{enumerate}
    10394
    104 \todo{I can't figure out a good lead-in to the overview.}
    105 Covering the existing \CFA features in \autoref{c:existing}.
    106 Then the new features are introduce in \autoref{c:features}, explaining their
    107 usage and design.
     95\todo{I can't figure out a good lead-in to the roadmap.}
     96The next section covers the existing state of exceptions.
     97The existing state of \CFA is also covered in \autoref{c:existing}.
     98The new features are introduced in \autoref{c:features},
     99which explains their usage and design.
    108100That is followed by the implementation of those features in
    109101\autoref{c:implement}.
    110 % Future Work \autoref{c:future}
     102The performance results are examined in \autoref{c:performance}.
     103Possibilities to extend this project are discussed in \autoref{c:future}.
     104
     105\section{Background}
     106\label{s:background}
     107
     108Exception handling is not a new concept,
     109with papers on the subject dating back 70s.
     110
     111Their were popularised by \Cpp,
     112which added them in its first major wave of non-object-orientated features
     113in 1990.
     114% https://en.cppreference.com/w/cpp/language/history
     115
     116Java was the next popular language to use exceptions. It is also the most
     117popular language with checked exceptions.
     118Checked exceptions are part of the function interface they are raised from.
     119This includes functions they propogate through, until a handler for that
     120type of exception is found.
     121This makes exception information explicit, which can improve clarity and
     122safety, but can slow down programming.
     123Some of these, such as dealing with high-order methods or an overly specified
     124throws clause, are technical. However some of the issues are much more
     125human, in that writing/updating all the exception signatures can be enough
     126of a burden people will hack the system to avoid them.
     127Including the ``catch-and-ignore" pattern where a catch block is used without
     128anything to repair or recover from the exception.
     129
     130%\subsection
     131Resumption exceptions have been much less popular.
     132Although resumption has a history as old as termination's, very few
     133programming languages have implement them.
     134% http://bitsavers.informatik.uni-stuttgart.de/pdf/xerox/parc/techReports/
     135%   CSL-79-3_Mesa_Language_Manual_Version_5.0.pdf
     136Mesa is one programming languages that did and experiance with that
     137languages is quoted as being one of the reasons resumptions were not
     138included in the \Cpp standard.
     139% https://en.wikipedia.org/wiki/Exception_handling
     140\todo{A comment about why we did include them when they are so unpopular
     141might be approprate.}
     142
     143%\subsection
     144Functional languages, tend to use solutions like the return union, but some
     145exception-like constructs still appear.
     146
     147For instance Haskell's built in error mechanism can make the result of any
     148expression, including function calls. Any expression that examines an
     149error value will in-turn produce an error. This continues until the main
     150function produces an error or until it is handled by one of the catch
     151functions.
     152
     153%\subsection
     154More recently exceptions seem to be vanishing from newer programming
     155languages.
     156Rust and Go reduce this feature to panics.
     157Panicing is somewhere between a termination exception and a program abort.
     158Notably in Rust a panic can trigger either, a panic may unwind the stack or
     159simply kill the process.
     160% https://doc.rust-lang.org/std/panic/fn.catch_unwind.html
     161Go's panic is much more similar to a termination exception but there is
     162only a catch-all function with \code{Go}{recover()}.
     163So exceptions still are appearing, just in reduced forms.
     164
     165%\subsection
     166Exception handling's most common use cases are in error handling.
     167Here are some other ways to handle errors and comparisons with exceptions.
     168\begin{itemize}
     169\item\emph{Error Codes}:
     170This pattern uses an enumeration (or just a set of fixed values) to indicate
     171that an error has occured and which error it was.
     172
     173There are some issues if a function wants to return an error code and another
     174value. The main issue is that it can be easy to forget checking the error
     175code, which can lead to an error being quitely and implicitly ignored.
     176Some new languages have tools that raise warnings if the return value is
     177discarded to avoid this.
     178It also puts more code on the main execution path.
     179\item\emph{Special Return with Global Store}:
     180A function that encounters an error returns some value indicating that it
     181encountered a value but store which error occured in a fixed global location.
     182
     183Perhaps the C standard @errno@ is the most famous example of this,
     184where some standard library functions will return some non-value (often a
     185NULL pointer) and set @errno@.
     186
     187This avoids the multiple results issue encountered with straight error codes
     188but otherwise many of the same advantages and disadvantages.
     189It does however introduce one other major disadvantage:
     190Everything that uses that global location must agree on all possible errors.
     191\item\emph{Return Union}:
     192Replaces error codes with a tagged union.
     193Success is one tag and the errors are another.
     194It is also possible to make each possible error its own tag and carry its own
     195additional information, but the two branch format is easy to make generic
     196so that one type can be used everywhere in error handling code.
     197
     198This pattern is very popular in functional or semi-functional language,
     199anything with primitive support for tagged unions (or algebraic data types).
     200% We need listing Rust/rust to format code snipits from it.
     201% Rust's \code{rust}{Result<T, E>}
     202
     203The main disadvantage is again it puts code on the main execution path.
     204This is also the first technique that allows for more information about an
     205error, other than one of a fix-set of ids, to be sent.
     206They can be missed but some languages can force that they are checked.
     207It is also implicitly forced in any languages with checked union access.
     208\item\emph{Handler Functions}:
     209On error the function that produced the error calls another function to
     210handle it.
     211The handler function can be provided locally (passed in as an argument,
     212either directly as as a field of a structure/object) or globally (a global
     213variable).
     214
     215C++ uses this as its fallback system if exception handling fails.
     216\snake{std::terminate_handler} and for a time \snake{std::unexpected_handler}
     217
     218Handler functions work a lot like resumption exceptions.
     219The difference is they are more expencive to set up but cheaper to use, and
     220so are more suited to more fequent errors.
     221The exception being global handlers if they are rarely change as the time
     222in both cases strinks towards zero.
     223\end{itemize}
     224
     225%\subsection
     226Because of their cost exceptions are rarely used for hot paths of execution.
     227There is an element of self-fulfilling prophocy here as implementation
     228techniques have been designed to make exceptions cheap to set-up at the cost
     229of making them expencive to use.
     230Still, use of exceptions for other tasks is more common in higher-level
     231scripting languages.
     232An iconic example is Python's StopIteration exception which is thrown by
     233an iterator to indicate that it is exausted. Combined with Python's heavy
     234use of the iterator based for-loop.
     235% https://docs.python.org/3/library/exceptions.html#StopIteration
  • doc/theses/andrew_beach_MMath/uw-ethesis.tex

    r5a46e09 r660665f  
    244244\input{features}
    245245\input{implement}
     246\input{performance}
    246247\input{future}
    247248
  • doc/theses/mubeen_zulfiqar_MMath/.gitignore

    r5a46e09 r660665f  
    11# Intermediate Results:
    2 out/
     2build/
    33
    44# Final Files:
  • doc/theses/mubeen_zulfiqar_MMath/allocator.tex

    r5a46e09 r660665f  
    77\begin{itemize}
    88\item
    9 Objective of @uHeapLmmm@.
     9Objective of uHeapLmmm.
    1010\item
    1111Design philosophy.
    1212\item
    13 Background and previous design of @uHeapLmmm@.
     13Background and previous design of uHeapLmmm.
    1414\item
    15 Distributed design of @uHeapLmmm@.
     15Distributed design of uHeapLmmm.
    1616
    1717----- SHOULD WE GIVE IMPLEMENTATION DETAILS HERE? -----
     
    2424\end{itemize}
    2525
    26 The new features added to @uHeapLmmm@ (incl. @malloc_size@ routine)
     26The new features added to uHeapLmmm (incl. @malloc_size@ routine)
    2727\CFA alloc interface with examples.
    2828\begin{itemize}
     
    3333\end{itemize}
    3434
    35 ----- SHOULD WE GIVE PERFORMANCE AND USABILITY COMPARISON OF DIFFERENT INTERFACES THAT WE TRIED? -----
    3635
    37 \PAB{Often Performance is its own chapter. I added one for now.}
     36%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     37%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     38%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% uHeapLmmm Design
     39%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     40%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    3841
    39 Performance evaluation using u-benchmark suite.
     42\section{Objective of uHeapLmmm}
     43UHeapLmmm is a lightweight memory allocator. The objective behind uHeapLmmm is to design a minimal concurrent memory allocator that has new features and also fulfills GNU C Library requirements (FIX ME: cite requirements).
     44
     45\subsection{Design philosophy}
     46
     47
     48%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     49
     50\section{Background and previous design of uHeapLmmm}
     51
     52
     53%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     54
     55\section{Distributed design of uHeapLmmm}
     56
     57
     58\subsection{Advantages of distributed design}
     59
     60
     61%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     62
     63\section{Added Features}
     64
     65
     66\subsection{Methods}
     67Why did we need it?
     68The added benefits.
     69
     70
     71\subsection{Alloc Interface}
     72Why did we need it?
     73The added benefits.
     74
     75
     76%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     77% Following is added by Peter
    4078
    4179\noindent
  • doc/theses/mubeen_zulfiqar_MMath/benchmarks.tex

    r5a46e09 r660665f  
    3434\noindent
    3535====================
     36
     37%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     38%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     39%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Performance Matrices
     40%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     41%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     42
     43\section{Performance Matrices of Memory Allocators}
     44
     45When it comes to memory allocators, there are no set standards of performance. Performance of a memory allocator depends highly on the usage pattern of the application. A memory allocator that is the best performer for a certain application X might be the worst for some other application which has completely different memory usage pattern compared to the application X. It is extremely difficult to make one universally best memory allocator which will outperform every other memory allocator for every usage pattern. So, there is a lack of a set of standard benchmarks that are used to evaluate a memory allocators's performance.
     46
     47If we breakdown the goals of a memory allocator, there are two basic matrices on which a memory allocator's performance is evaluated.
     48\begin{enumerate}
     49\item
     50Memory Overhead
     51\item
     52Speed
     53\end{enumerate}
     54
     55\subsection{Memory Overhead}
     56Memory overhead is the extra memory that a memory allocator takes from OS which is not requested by the application. Ideally, an allocator should get just enough memory from OS that can fulfill application's request and should return this memory to OS as soon as applications frees it. But, allocators retain more memory compared to what application has asked for which causes memory overhead. Memory overhead can happen for various reasons.
     57
     58\subsubsection{Fragmentation}
     59Fragmentation is one of the major reasons behind memory overhead. Fragmentation happens because of situations that are either necassary for proper functioning of the allocator such as internal memory management and book-keeping or are out of allocator's control such as application's usage pattern.
     60
     61\paragraph{Internal Fragmentation}
     62For internal book-keeping, allocators divide raw memory given by OS into chunks, blocks, or lists that can fulfill application's requested size. Allocators use memory given by OS for creating headers, footers etc. to store information about these chunks, blocks, or lists. This increases usage of memory in-addition to the memory requested by application as the allocators need to store their book-keeping information. This extra usage of memory for allocator's own book-keeping is called Internal Fragmentation. Although it cases memory overhead but this overhead is necassary for an allocator's proper funtioning.
     63
     64*** FIX ME: Insert a figure of internal fragmentation with explanation
     65
     66\paragraph{External Fragmentation}
     67External fragmentation is the free bits of memory between or around chunks of memory that are currently in-use of the application. Segmentation in memory due to application's usage pattern causes external fragmentation. The memory which is part of external fragmentation is completely free as it is neither used by allocator's internal book-keeping nor by the application. Ideally, an allocator should return a segment of memory back to the OS as soon as application frees it. But, this is not always the case. Allocators get memory from OS in one of the two ways.
     68
     69\begin{itemize}
     70\item
     71MMap: an allocator can ask OS for whole pages in mmap area. Then, the allocator segments the page internally and fulfills application's request.
     72\item
     73Heap: an allocator can ask OS for memory in heap area using system calls such as sbrk. Heap are grows downwards and shrinks upwards.
     74\begin{itemize}
     75\item
     76If an allocator uses mmap area, it can only return extra memory back to OS if the whole page is free i.e. no chunk on the page is in-use of the application. Even if one chunk on the whole page is currently in-use of the application, the allocator has to retain the whole page.
     77\item
     78If an allocator uses the heap area, it can only return the continous free memory at the end of the heap area that is currently in allocator's possession as heap area shrinks upwards. If there are free bits of memory in-between chunks of memory that are currently in-use of the application, the allocator can not return these free bits.
     79
     80*** FIX ME: Insert a figure of above scenrio with explanation
     81\item
     82Even if the entire heap area is free except one small chunk at the end of heap area that is being used by the application, the allocator cannot return the free heap area back to the OS as it is not a continous region at the end of heap area.
     83
     84*** FIX ME: Insert a figure of above scenrio with explanation
     85
     86\item
     87Such scenerios cause external fragmentation but it is out of the allocator's control and depend on application's usage pattern.
     88\end{itemize}
     89\end{itemize}
     90
     91\subsubsection{Internal Memory Management}
     92Allocators such as je-malloc (FIX ME: insert reference) pro-actively get some memory from the OS and divide it into chunks of certain sizes that can be used in-future to fulfill application's request. This causes memory overhead as these chunks are made before application's request. There is also the possibility that an application may not even request memory of these sizes during their whole life-time.
     93
     94*** FIX ME: Insert a figure of above scenrio with explanation
     95
     96Allocators such as rp-malloc (FIX ME: insert reference) maintain lists or blocks of sized memory segments that is freed by the application for future use. These lists are maintained without any guarantee that application will even request these sizes again.
     97
     98Such tactics are usually used to gain speed as allocator will not have to get raw memory from OS and manage it at the time of application's request but they do cause memory overhead.
     99
     100Fragmentation and managed sized chunks of free memory can lead to Heap Blowup as the allocator may not be able to use the fragments or sized free chunks of free memory to fulfill application's requests of other sizes.
     101
     102\subsection{Speed}
     103When it comes to performance evaluation of any piece of software, its runtime is usually the first thing that is evaluated. The same is true for memory allocators but, in case of memory allocators, speed does not only mean the runtime of memory allocator's routines but there are other factors too.
     104
     105\subsubsection{Runtime Speed}
     106Low runtime is the main goal of a memory allocator when it comes it proving its speed. Runtime is the time that it takes for a routine of memory allocator to complete its execution. As mentioned in (FIX ME: refernce to routines' list), there four basic routines that are used in memory allocation. Ideally, each routine of a memory allocator should be fast. Some memory allocator designs use pro-active measures (FIX ME: local refernce) to gain speed when allocating some memory to the application. Some memory allocators do memory allocation faster than memory freeing (FIX ME: graph refernce) while others show similar speed whether memory is allocated or freed.
     107
     108\subsubsection{Memory Access Speed}
     109Runtime speed is not the only speed matrix in memory allocators. The memory that a memory allocator has allocated to the application also needs to be accessible as quick as possible. The application should be able to read/write allocated memory quickly. The allocation method of a memory allocator may introduce some delays when it comes to memory access speed, which is specially important in concurrent applications. Ideally, a memory allocator should allocate all memory on a cache-line to only one thread and no cache-line should be shared among multiple threads. If a memory allocator allocates memory to multple threads on a same cache line, then cache may get invalidated more frequesntly when two different threads running on two different processes will try to read/write the same memory region. On the other hand, if one cache-line is used by only one thread then the cache may get invalidated less frequently. This sharing of one cache-line among multiple threads is called false sharing (FIX ME: cite wasik).
     110
     111\paragraph{Active False Sharing}
     112Active false sharing is the sharing of one cache-line among multiple threads that is caused by memory allocator. It happens when two threads request memory from memory allocator and the allocator allocates memory to both of them on the same cache-line. After that, if the threads are running on different processes who have their own caches and both threads start reading/writing the allocated memory simultanously, their caches will start getting invalidated every time the other thread writes something to the memory. This will cause the application to slow down as the process has to load cache much more frequently.
     113
     114*** FIX ME: Insert a figure of above scenrio with explanation
     115
     116\paragraph{Passive False Sharing}
     117Passive false sharing is the kind of false sharing which is caused by the application and not the memory allocator. The memory allocator may preservce passive false sharing in future instead of eradicating it. But, passive false sharing is initiated by the application.
     118
     119\subparagraph{Program Induced Passive False Sharing}
     120Program induced false sharing is completely out of memory allocator's control and is purely caused by the application. When a thread in the application creates multiple objects in the dynamic area and allocator allocates memory for these objects on the same cache-line as the objects are created by the same thread. Passive false sharing will occur if this thread passes one of these objects to another thread but it retains the rest of these objects or it passes some/all of the remaining objects to some third thread(s). Now, one cache-line is shared among multiple threads but it is caused by the application and not the allocator. It is out of allocator's control and has the similar performance impact as Active False Sharing (FIX ME: cite local) if these threads, who are sharing the same cache-line, start reading/writing the given objects simultanously.
     121
     122*** FIX ME: Insert a figure of above scenrio 1 with explanation
     123
     124*** FIX ME: Insert a figure of above scenrio 2 with explanation
     125
     126\subparagraph{Program Induced Allocator Preserved Passive False Sharing}
     127Program induced allocator preserved passive false sharing is another interesting case of passive false sharing. Both the application and the allocator are partially responsible for it. It starts the same as Program Induced False Sharing (FIX ME: cite local). Once, an application thread has created multiple dynamic objects on the same cache-line and ditributed these objects among multiple threads causing sharing of one cache-line among multiple threads (Program Induced Passive False Sharing). This kind of false sharing occurs when one of these threads, which got the object on the shared cache-line, frees the passed object then re-allocates another object but the allocator returns the same object (on the shared cache-line) that this thread just freed. Although, the application caused the false sharing to happen in the frst place however, to prevent furthur false sharing, the allocator should have returned the new object on some other cache-line which is only shared by the allocating thread. When it comes to performnce impact, this passive false sharing will slow down the application just like any other kind of false sharing if the threads sharing the cache-line start reading/writing the objects simultanously.
     128
     129
     130*** FIX ME: Insert a figure of above scenrio with explanation
     131
     132%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     133%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     134%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Micro Benchmark Suite
     135%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     136%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     137
     138\section{Micro Benchmark Suite}
     139The aim of micro benchmark suite is to create a set of programs that can evaluate a memory allocator based on the performance matrices described in (FIX ME: local cite). These programs can be taken as a standard to benchmark an allocator's basic goals. These programs give details of an allocator's memory overhead and speed under a certain allocation pattern. The speed of the allocator is benchmarked in different ways. Similarly, false sharing happening in an allocator is also measured in multiple ways. These benchmarks evalute the allocator under a certain allocation pattern which is configurable and can be changed using a few knobs to benchmark observe an allocator's performance under a desired allocation pattern.
     140
     141Micro Benchmark Suite benchmarks an allocator's performance by allocating dynamic objects and, then, measuring specifc matrices. The benchmark suite evaluates an allocator with a certain allocation pattern. Bnechmarks have different knobs that can be used to change allocation pattern and evaluate an allocator under desired conditions. These can be set by giving commandline arguments to the benchmark on execution.
     142
     143Following is the list of avalable knobs.
     144
     145*** FIX ME: Add knobs items after finalize
     146
     147\subsection{Memory Benchmark}
     148Memory benchmark measures memory overhead of an allocator. It allocates a number of dynamic objects. Then, by reading /self/proc/maps, gets the total memory that the allocator has reuested from the OS. Finally, it calculates the memory head by taking the difference between the memory the allocator has requested from the OS and the memory that program has allocated.
     149*** FIX ME: Insert a figure of above benchmark with description
     150
     151\subsubsection{Relevant Knobs}
     152*** FIX ME: Insert Relevant Knobs
     153
     154\subsection{Speed Benchmark}
     155Speed benchmark calculates the runtime speed of an allocator's functions (FIX ME: cite allocator routines). It does by measuring the runtime of allocator routines in two different ways.
     156
     157\subsubsection{Speed Time}
     158The time method does a certain amount of work by calling each routine of the allocator (FIX ME: cite allocator routines) a specific time. It calculates the total time it took to perform this workload. Then, it divides the time it took by the workload and calculates the average time taken by the allocator's routine.
     159*** FIX ME: Insert a figure of above benchmark with description
     160
     161\paragraph{Relevant Knobs}
     162*** FIX ME: Insert Relevant Knobs
     163
     164\subsubsection{Speed Workload}
     165The worload method uses the opposite approach. It calls the allocator's routines for a specific amount of time and measures how much work was done during that time. Then, similar to the time method, it divides the time by the workload done during that time and calculates the average time taken by the allocator's routine.
     166*** FIX ME: Insert a figure of above benchmark with description
     167
     168\paragraph{Relevant Knobs}
     169*** FIX ME: Insert Relevant Knobs
     170
     171\subsection{Cache Scratch}
     172Cache Scratch benchmark measures program induced allocator preserved passive false sharing (FIX ME CITE) in an allocator. It does so in two ways.
     173
     174\subsubsection{Cache Scratch Time}
     175Cache Scratch Time allocates dynamic objects. Then, it benchmarks program induced allocator preserved passive false sharing (FIX ME CITE) in an allocator by measuring the time it takes to read/write these objects.
     176*** FIX ME: Insert a figure of above benchmark with description
     177
     178\paragraph{Relevant Knobs}
     179*** FIX ME: Insert Relevant Knobs
     180
     181\subsubsection{Cache Scratch Layout}
     182Cache Scratch Layout also allocates dynamic objects. Then, it benchmarks program induced allocator preserved passive false sharing (FIX ME CITE) by using heap addresses returned by the allocator. It calculates how many objects were allocated to different threads on the same cache line.
     183*** FIX ME: Insert a figure of above benchmark with description
     184
     185\paragraph{Relevant Knobs}
     186*** FIX ME: Insert Relevant Knobs
     187
     188\subsection{Cache Thrash}
     189Cache Thrash benchmark measures allocator induced passive false sharing (FIX ME CITE) in an allocator. It also does so in two ways.
     190
     191\subsubsection{Cache Thrash Time}
     192Cache Thrash Time allocates dynamic objects. Then, it benchmarks allocator induced false sharing (FIX ME CITE) in an allocator by measuring the time it takes to read/write these objects.
     193*** FIX ME: Insert a figure of above benchmark with description
     194
     195\paragraph{Relevant Knobs}
     196*** FIX ME: Insert Relevant Knobs
     197
     198\subsubsection{Cache Thrash Layout}
     199Cache Thrash Layout also allocates dynamic objects. Then, it benchmarks allocator induced false sharing (FIX ME CITE) by using heap addresses returned by the allocator. It calculates how many objects were allocated to different threads on the same cache line.
     200*** FIX ME: Insert a figure of above benchmark with description
     201
     202\paragraph{Relevant Knobs}
     203*** FIX ME: Insert Relevant Knobs
     204
     205\section{Results}
     206*** FIX ME: add configuration details of memory allocators
     207
     208\subsection{Memory Benchmark}
     209
     210\subsubsection{Relevant Knobs}
     211
     212\subsection{Speed Benchmark}
     213
     214\subsubsection{Speed Time}
     215
     216\paragraph{Relevant Knobs}
     217
     218\subsubsection{Speed Workload}
     219
     220\paragraph{Relevant Knobs}
     221
     222\subsection{Cache Scratch}
     223
     224\subsubsection{Cache Scratch Time}
     225
     226\paragraph{Relevant Knobs}
     227
     228\subsubsection{Cache Scratch Layout}
     229
     230\paragraph{Relevant Knobs}
     231
     232\subsection{Cache Thrash}
     233
     234\subsubsection{Cache Thrash Time}
     235
     236\paragraph{Relevant Knobs}
     237
     238\subsubsection{Cache Thrash Layout}
     239
     240\paragraph{Relevant Knobs}
  • doc/theses/mubeen_zulfiqar_MMath/uw-ethesis.tex

    r5a46e09 r660665f  
    165165% cfa macros used in the document
    166166\input{common}
     167%\usepackageinput{common}
    167168\CFAStyle                                               % CFA code-style for all languages
    168 \lstset{language=CFA,basicstyle=\linespread{0.9}\tt}    % CFA default language
     169\lstset{basicstyle=\linespread{0.9}\tt}                 % CFA typewriter font
    169170\newcommand{\PAB}[1]{{\color{red}PAB: #1}}
    170171
  • libcfa/configure.ac

    r5a46e09 r660665f  
    131131#io_uring 5.5 uses enum values
    132132#io_uring 5.6 and later uses probes
     133
     134AH_TEMPLATE([CFA_HAVE_LINUX_RSEQ_H],[Defined if rseq support is present when compiling libcfathread.])
     135AC_CHECK_HEADERS([linux/rseq.h], [AC_DEFINE(CFA_HAVE_LINUX_RSEQ_H)])
     136
     137AH_TEMPLATE([CFA_HAVE_LINUX_LIBRSEQ],[Defined if librseq support is present when compiling libcfathread.])
     138AC_CHECK_LIB([rseq], [rseq_available], [AC_DEFINE(CFA_HAVE_LINUX_RSEQ_H)], [])
    133139
    134140AH_TEMPLATE([CFA_HAVE_LINUX_IO_URING_H],[Defined if io_uring support is present when compiling libcfathread.])
  • libcfa/prelude/defines.hfa.in

    r5a46e09 r660665f  
    171171#undef CFA_HAVE_LINUX_IO_URING_H
    172172
     173/* Defined if librseq support is present when compiling libcfathread. */
     174#undef CFA_HAVE_LINUX_LIBRSEQ
     175
     176/* Defined if rseq support is present when compiling libcfathread. */
     177#undef CFA_HAVE_LINUX_RSEQ_H
     178
    173179/* Defined if openat2 support is present when compiling libcfathread. */
    174180#undef CFA_HAVE_OPENAT2
     
    205211#undef HAVE_LINUX_IO_URING_H
    206212
     213/* Define to 1 if you have the <linux/rseq.h> header file. */
     214#undef HAVE_LINUX_RSEQ_H
     215
    207216/* Define to 1 if you have the <memory.h> header file. */
    208217#undef HAVE_MEMORY_H
  • libcfa/src/Makefile.am

    r5a46e09 r660665f  
    6161        containers/queueLockFree.hfa \
    6262        containers/stackLockFree.hfa \
     63        containers/vector2.hfa \
    6364        vec/vec.hfa \
    6465        vec/vec2.hfa \
     
    6970        common.hfa \
    7071        fstream.hfa \
    71         strstream.hfa \
    7272        heap.hfa \
    7373        iostream.hfa \
     
    7878        rational.hfa \
    7979        stdlib.hfa \
     80        strstream.hfa \
    8081        time.hfa \
    8182        bits/weakso_locks.hfa \
     
    8384        containers/pair.hfa \
    8485        containers/result.hfa \
    85         containers/vector.hfa
     86        containers/vector.hfa \
     87        device/cpu.hfa
    8688
    8789libsrc = ${inst_headers_src} ${inst_headers_src:.hfa=.cfa} \
  • libcfa/src/bits/signal.hfa

    r5a46e09 r660665f  
    2020
    2121#include <errno.h>
    22 #define __USE_GNU
    2322#include <signal.h>
    24 #undef __USE_GNU
    2523#include <stdlib.h>
    2624#include <string.h>
  • libcfa/src/concurrency/coroutine.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
     17#define _GNU_SOURCE
    1718
    1819#include "coroutine.hfa"
  • libcfa/src/concurrency/io.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
     17#define _GNU_SOURCE
    1718
    1819#if defined(__CFA_DEBUG__)
     
    2324
    2425#if defined(CFA_HAVE_LINUX_IO_URING_H)
    25         #define _GNU_SOURCE         /* See feature_test_macros(7) */
    2626        #include <errno.h>
    2727        #include <signal.h>
  • libcfa/src/concurrency/io/setup.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
    17 #define _GNU_SOURCE         /* See feature_test_macros(7) */
     17#define _GNU_SOURCE
    1818
    1919#if defined(__CFA_DEBUG__)
  • libcfa/src/concurrency/kernel.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
     17#define _GNU_SOURCE
     18
    1719// #define __CFA_DEBUG_PRINT_RUNTIME_CORE__
    1820
     
    278280
    279281                                // Spin a little on I/O, just in case
    280                                         for(5) {
     282                                for(5) {
    281283                                        __maybe_io_drain( this );
    282284                                        readyThread = pop_fast( this->cltr );
     
    285287
    286288                                // no luck, try stealing a few times
    287                                         for(5) {
     289                                for(5) {
    288290                                        if( __maybe_io_drain( this ) ) {
    289291                                                readyThread = pop_fast( this->cltr );
     
    422424                __cfactx_switch( &proc_cor->context, &thrd_dst->context );
    423425                // when __cfactx_switch returns we are back in the processor coroutine
     426
     427
    424428
    425429                /* paranoid */ verify( 0x0D15EA5E0D15EA5Ep == thrd_dst->canary );
     
    522526
    523527        /* paranoid */ verify( ! __preemption_enabled() );
    524         /* paranoid */ verifyf( ((uintptr_t)thrd_src->context.SP) < ((uintptr_t)__get_stack(thrd_src->curr_cor)->base ), "ERROR : Returning $thread %p has been corrupted.\n StackPointer too small.\n", thrd_src );
    525         /* paranoid */ verifyf( ((uintptr_t)thrd_src->context.SP) > ((uintptr_t)__get_stack(thrd_src->curr_cor)->limit), "ERROR : Returning $thread %p has been corrupted.\n StackPointer too large.\n", thrd_src );
     528        /* paranoid */ verifyf( ((uintptr_t)thrd_src->context.SP) < ((uintptr_t)__get_stack(thrd_src->curr_cor)->base ) || thrd_src->corctx_flag, "ERROR : Returning $thread %p has been corrupted.\n StackPointer too small.\n", thrd_src );
     529        /* paranoid */ verifyf( ((uintptr_t)thrd_src->context.SP) > ((uintptr_t)__get_stack(thrd_src->curr_cor)->limit) || thrd_src->corctx_flag, "ERROR : Returning $thread %p has been corrupted.\n StackPointer too large.\n", thrd_src );
    526530}
    527531
  • libcfa/src/concurrency/kernel.hfa

    r5a46e09 r660665f  
    6666                unsigned id;
    6767                unsigned target;
     68                unsigned last;
    6869                unsigned long long int cutoff;
    6970        } rdq;
  • libcfa/src/concurrency/kernel/startup.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
     17#define _GNU_SOURCE
    1718
    1819// C Includes
    1920#include <errno.h>              // errno
     21#include <signal.h>
    2022#include <string.h>             // strerror
    2123#include <unistd.h>             // sysconf
     24
    2225extern "C" {
    2326      #include <limits.h>       // PTHREAD_STACK_MIN
     27        #include <unistd.h>       // syscall
    2428        #include <sys/eventfd.h>  // eventfd
    2529      #include <sys/mman.h>     // mprotect
     
    136140};
    137141
     142#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
     143        // No data needed
     144#elif defined(CFA_HAVE_LINUX_RSEQ_H)
     145        extern "Cforall" {
     146                __attribute__((aligned(128))) thread_local volatile struct rseq __cfaabi_rseq @= {
     147                        .cpu_id : RSEQ_CPU_ID_UNINITIALIZED,
     148                };
     149        }
     150#else
     151        // No data needed
     152#endif
     153
    138154//-----------------------------------------------------------------------------
    139155// Struct to steal stack
     
    468484        self_mon_p = &self_mon;
    469485        link.next = 0p;
    470         link.ts   = 0;
     486        link.ts   = -1llu;
    471487        preferred = -1u;
    472488        last_proc = 0p;
     
    497513        this.rdq.id  = -1u;
    498514        this.rdq.target = -1u;
     515        this.rdq.last = -1u;
    499516        this.rdq.cutoff = 0ull;
    500517        do_terminate = false;
  • libcfa/src/concurrency/kernel_private.hfa

    r5a46e09 r660665f  
    1616#pragma once
    1717
     18#if !defined(__cforall_thread__)
     19        #error kernel_private.hfa should only be included in libcfathread source
     20#endif
     21
    1822#include "kernel.hfa"
    1923#include "thread.hfa"
     
    2226#include "stats.hfa"
    2327
     28extern "C" {
     29#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
     30        #include <rseq/rseq.h>
     31#elif defined(CFA_HAVE_LINUX_RSEQ_H)
     32        #include <linux/rseq.h>
     33#else
     34        #ifndef _GNU_SOURCE
     35        #error kernel_private requires gnu_source
     36        #endif
     37        #include <sched.h>
     38#endif
     39}
     40
    2441//-----------------------------------------------------------------------------
    2542// Scheduler
    26 
    27 
    2843extern "C" {
    2944        void disable_interrupts() OPTIONAL_THREAD;
     
    3954
    4055//-----------------------------------------------------------------------------
     56// Hardware
     57
     58#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
     59        // No data needed
     60#elif defined(CFA_HAVE_LINUX_RSEQ_H)
     61        extern "Cforall" {
     62                extern __attribute__((aligned(128))) thread_local volatile struct rseq __cfaabi_rseq;
     63        }
     64#else
     65        // No data needed
     66#endif
     67
     68static inline int __kernel_getcpu() {
     69        /* paranoid */ verify( ! __preemption_enabled() );
     70#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
     71        return rseq_current_cpu();
     72#elif defined(CFA_HAVE_LINUX_RSEQ_H)
     73        int r = __cfaabi_rseq.cpu_id;
     74        /* paranoid */ verify( r >= 0 );
     75        return r;
     76#else
     77        return sched_getcpu();
     78#endif
     79}
     80
     81//-----------------------------------------------------------------------------
    4182// Processor
    4283void main(processorCtx_t *);
     
    4485void * __create_pthread( pthread_t *, void * (*)(void *), void * );
    4586void __destroy_pthread( pthread_t pthread, void * stack, void ** retval );
    46 
    47 
    4887
    4988extern cluster * mainCluster;
  • libcfa/src/concurrency/locks.cfa

    r5a46e09 r660665f  
    1616
    1717#define __cforall_thread__
     18#define _GNU_SOURCE
    1819
    1920#include "locks.hfa"
  • libcfa/src/concurrency/locks.hfa

    r5a46e09 r660665f  
    2424#include "containers/list.hfa"
    2525
     26#include "limits.hfa"
    2627#include "thread.hfa"
    2728
     
    8788        bool tryP(BinaryBenaphore & this) {
    8889                ssize_t c = this.counter;
     90                /* paranoid */ verify( c > MIN );
    8991                return (c >= 1) && __atomic_compare_exchange_n(&this.counter, &c, c-1, false, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
    9092        }
     
    9496                ssize_t c = 0;
    9597                for () {
     98                        /* paranoid */ verify( this.counter < MAX );
    9699                        if (__atomic_compare_exchange_n(&this.counter, &c, c+1, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
    97100                                if (c == 0) return true;
     
    173176        ThreadBenaphore sem;
    174177};
     178
     179static inline void ?{}(fast_lock & this) { this.owner = 0p; }
    175180
    176181static inline bool $try_lock(fast_lock & this, $thread * thrd) {
  • libcfa/src/concurrency/monitor.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
     17#define _GNU_SOURCE
    1718
    1819#include "monitor.hfa"
  • libcfa/src/concurrency/mutex.cfa

    r5a46e09 r660665f  
    1717
    1818#define __cforall_thread__
     19#define _GNU_SOURCE
    1920
    2021#include "mutex.hfa"
  • libcfa/src/concurrency/preemption.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
     17#define _GNU_SOURCE
     18
    1719// #define __CFA_DEBUG_PRINT_PREEMPTION__
    1820
  • libcfa/src/concurrency/ready_queue.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
     17#define _GNU_SOURCE
     18
    1719// #define __CFA_DEBUG_PRINT_READY_QUEUE__
    1820
     
    2022#define USE_RELAXED_FIFO
    2123// #define USE_WORK_STEALING
     24// #define USE_CPU_WORK_STEALING
    2225
    2326#include "bits/defs.hfa"
     27#include "device/cpu.hfa"
    2428#include "kernel_private.hfa"
    2529
    26 #define _GNU_SOURCE
    2730#include "stdlib.hfa"
    2831#include "math.hfa"
    2932
     33#include <errno.h>
    3034#include <unistd.h>
     35
     36extern "C" {
     37        #include <sys/syscall.h>  // __NR_xxx
     38}
    3139
    3240#include "ready_subqueue.hfa"
     
    4654#endif
    4755
    48 #if   defined(USE_RELAXED_FIFO)
     56#if   defined(USE_CPU_WORK_STEALING)
     57        #define READYQ_SHARD_FACTOR 2
     58#elif defined(USE_RELAXED_FIFO)
    4959        #define BIAS 4
    5060        #define READYQ_SHARD_FACTOR 4
     
    8595}
    8696
     97#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
     98        // No forward declaration needed
     99        #define __kernel_rseq_register rseq_register_current_thread
     100        #define __kernel_rseq_unregister rseq_unregister_current_thread
     101#elif defined(CFA_HAVE_LINUX_RSEQ_H)
     102        void __kernel_raw_rseq_register  (void);
     103        void __kernel_raw_rseq_unregister(void);
     104
     105        #define __kernel_rseq_register __kernel_raw_rseq_register
     106        #define __kernel_rseq_unregister __kernel_raw_rseq_unregister
     107#else
     108        // No forward declaration needed
     109        // No initialization needed
     110        static inline void noop(void) {}
     111
     112        #define __kernel_rseq_register noop
     113        #define __kernel_rseq_unregister noop
     114#endif
     115
    87116//=======================================================================
    88117// Cluster wide reader-writer lock
     
    107136// Lock-Free registering/unregistering of threads
    108137unsigned register_proc_id( void ) with(*__scheduler_lock) {
     138        __kernel_rseq_register();
     139
    109140        __cfadbg_print_safe(ready_queue, "Kernel : Registering proc %p for RW-Lock\n", proc);
    110141        bool * handle = (bool *)&kernelTLS().sched_lock;
     
    161192
    162193        __cfadbg_print_safe(ready_queue, "Kernel : Unregister proc %p\n", proc);
     194
     195        __kernel_rseq_unregister();
    163196}
    164197
     
    214247//=======================================================================
    215248void ?{}(__ready_queue_t & this) with (this) {
    216         lanes.data  = 0p;
    217         lanes.tscs  = 0p;
    218         lanes.count = 0;
     249        #if defined(USE_CPU_WORK_STEALING)
     250                lanes.count = cpu_info.hthrd_count * READYQ_SHARD_FACTOR;
     251                lanes.data = alloc( lanes.count );
     252                lanes.tscs = alloc( lanes.count );
     253
     254                for( idx; (size_t)lanes.count ) {
     255                        (lanes.data[idx]){};
     256                        lanes.tscs[idx].tv = rdtscl();
     257                }
     258        #else
     259                lanes.data  = 0p;
     260                lanes.tscs  = 0p;
     261                lanes.count = 0;
     262        #endif
    219263}
    220264
    221265void ^?{}(__ready_queue_t & this) with (this) {
    222         verify( SEQUENTIAL_SHARD == lanes.count );
     266        #if !defined(USE_CPU_WORK_STEALING)
     267                verify( SEQUENTIAL_SHARD == lanes.count );
     268        #endif
     269
    223270        free(lanes.data);
    224271        free(lanes.tscs);
     
    226273
    227274//-----------------------------------------------------------------------
     275#if defined(USE_CPU_WORK_STEALING)
     276        __attribute__((hot)) void push(struct cluster * cltr, struct $thread * thrd, bool push_local) with (cltr->ready_queue) {
     277                __cfadbg_print_safe(ready_queue, "Kernel : Pushing %p on cluster %p\n", thrd, cltr);
     278
     279                processor * const proc = kernelTLS().this_processor;
     280                const bool external = !push_local || (!proc) || (cltr != proc->cltr);
     281
     282                const int cpu = __kernel_getcpu();
     283                /* paranoid */ verify(cpu >= 0);
     284                /* paranoid */ verify(cpu < cpu_info.hthrd_count);
     285                /* paranoid */ verify(cpu * READYQ_SHARD_FACTOR < lanes.count);
     286
     287                const cpu_map_entry_t & map = cpu_info.llc_map[cpu];
     288                /* paranoid */ verify(map.start * READYQ_SHARD_FACTOR < lanes.count);
     289                /* paranoid */ verify(map.self * READYQ_SHARD_FACTOR < lanes.count);
     290                /* paranoid */ verifyf((map.start + map.count) * READYQ_SHARD_FACTOR <= lanes.count, "have %zu lanes but map can go up to %u", lanes.count, (map.start + map.count) * READYQ_SHARD_FACTOR);
     291
     292                const int start = map.self * READYQ_SHARD_FACTOR;
     293                unsigned i;
     294                do {
     295                        unsigned r;
     296                        if(unlikely(external)) { r = __tls_rand(); }
     297                        else { r = proc->rdq.its++; }
     298                        i = start + (r % READYQ_SHARD_FACTOR);
     299                        // If we can't lock it retry
     300                } while( !__atomic_try_acquire( &lanes.data[i].lock ) );
     301
     302                // Actually push it
     303                push(lanes.data[i], thrd);
     304
     305                // Unlock and return
     306                __atomic_unlock( &lanes.data[i].lock );
     307
     308                #if !defined(__CFA_NO_STATISTICS__)
     309                        if(unlikely(external)) __atomic_fetch_add(&cltr->stats->ready.push.extrn.success, 1, __ATOMIC_RELAXED);
     310                        else __tls_stats()->ready.push.local.success++;
     311                #endif
     312
     313                __cfadbg_print_safe(ready_queue, "Kernel : Pushed %p on cluster %p (idx: %u, mask %llu, first %d)\n", thrd, cltr, i, used.mask[0], lane_first);
     314
     315        }
     316
     317        // Pop from the ready queue from a given cluster
     318        __attribute__((hot)) $thread * pop_fast(struct cluster * cltr) with (cltr->ready_queue) {
     319                /* paranoid */ verify( lanes.count > 0 );
     320                /* paranoid */ verify( kernelTLS().this_processor );
     321
     322                const int cpu = __kernel_getcpu();
     323                /* paranoid */ verify(cpu >= 0);
     324                /* paranoid */ verify(cpu < cpu_info.hthrd_count);
     325                /* paranoid */ verify(cpu * READYQ_SHARD_FACTOR < lanes.count);
     326
     327                const cpu_map_entry_t & map = cpu_info.llc_map[cpu];
     328                /* paranoid */ verify(map.start * READYQ_SHARD_FACTOR < lanes.count);
     329                /* paranoid */ verify(map.self * READYQ_SHARD_FACTOR < lanes.count);
     330                /* paranoid */ verifyf((map.start + map.count) * READYQ_SHARD_FACTOR <= lanes.count, "have %zu lanes but map can go up to %u", lanes.count, (map.start + map.count) * READYQ_SHARD_FACTOR);
     331
     332                processor * const proc = kernelTLS().this_processor;
     333                const int start = map.self * READYQ_SHARD_FACTOR;
     334
     335                // Did we already have a help target
     336                if(proc->rdq.target == -1u) {
     337                        // if We don't have a
     338                        unsigned long long min = ts(lanes.data[start]);
     339                        for(i; READYQ_SHARD_FACTOR) {
     340                                unsigned long long tsc = ts(lanes.data[start + i]);
     341                                if(tsc < min) min = tsc;
     342                        }
     343                        proc->rdq.cutoff = min;
     344
     345                        /* paranoid */ verify(lanes.count < 65536); // The following code assumes max 65536 cores.
     346                        /* paranoid */ verify(map.count < 65536); // The following code assumes max 65536 cores.
     347                        uint64_t chaos = __tls_rand();
     348                        uint64_t high_chaos = (chaos >> 32);
     349                        uint64_t  mid_chaos = (chaos >> 16) & 0xffff;
     350                        uint64_t  low_chaos = chaos & 0xffff;
     351
     352                        unsigned me = map.self;
     353                        unsigned cpu_chaos = map.start + (mid_chaos % map.count);
     354                        bool global = cpu_chaos == me;
     355
     356                        if(global) {
     357                                proc->rdq.target = high_chaos % lanes.count;
     358                        } else {
     359                                proc->rdq.target = (cpu_chaos * READYQ_SHARD_FACTOR) + (low_chaos % READYQ_SHARD_FACTOR);
     360                                /* paranoid */ verify(proc->rdq.target >= (map.start * READYQ_SHARD_FACTOR));
     361                                /* paranoid */ verify(proc->rdq.target <  ((map.start + map.count) * READYQ_SHARD_FACTOR));
     362                        }
     363
     364                        /* paranoid */ verify(proc->rdq.target != -1u);
     365                }
     366                else {
     367                        const unsigned long long bias = 0; //2_500_000_000;
     368                        const unsigned long long cutoff = proc->rdq.cutoff > bias ? proc->rdq.cutoff - bias : proc->rdq.cutoff;
     369                        {
     370                                unsigned target = proc->rdq.target;
     371                                proc->rdq.target = -1u;
     372                                if(lanes.tscs[target].tv < cutoff && ts(lanes.data[target]) < cutoff) {
     373                                        $thread * t = try_pop(cltr, target __STATS(, __tls_stats()->ready.pop.help));
     374                                        proc->rdq.last = target;
     375                                        if(t) return t;
     376                                }
     377                        }
     378
     379                        unsigned last = proc->rdq.last;
     380                        if(last != -1u && lanes.tscs[last].tv < cutoff && ts(lanes.data[last]) < cutoff) {
     381                                $thread * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.help));
     382                                if(t) return t;
     383                        }
     384                        else {
     385                                proc->rdq.last = -1u;
     386                        }
     387                }
     388
     389                for(READYQ_SHARD_FACTOR) {
     390                        unsigned i = start + (proc->rdq.itr++ % READYQ_SHARD_FACTOR);
     391                        if($thread * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t;
     392                }
     393
     394                // All lanes where empty return 0p
     395                return 0p;
     396        }
     397
     398        __attribute__((hot)) struct $thread * pop_slow(struct cluster * cltr) with (cltr->ready_queue) {
     399                processor * const proc = kernelTLS().this_processor;
     400                unsigned last = proc->rdq.last;
     401                if(last != -1u) {
     402                        struct $thread * t = try_pop(cltr, last __STATS(, __tls_stats()->ready.pop.steal));
     403                        if(t) return t;
     404                        proc->rdq.last = -1u;
     405                }
     406
     407                unsigned i = __tls_rand() % lanes.count;
     408                return try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.steal));
     409        }
     410        __attribute__((hot)) struct $thread * pop_search(struct cluster * cltr) {
     411                return search(cltr);
     412        }
     413#endif
    228414#if defined(USE_RELAXED_FIFO)
    229415        //-----------------------------------------------------------------------
     
    519705                                        if(is_empty(sl)) {
    520706                                                assert( sl.anchor.next == 0p );
    521                                                 assert( sl.anchor.ts   == 0 );
     707                                                assert( sl.anchor.ts   == -1llu );
    522708                                                assert( mock_head(sl)  == sl.prev );
    523709                                        } else {
    524710                                                assert( sl.anchor.next != 0p );
    525                                                 assert( sl.anchor.ts   != 0 );
     711                                                assert( sl.anchor.ts   != -1llu );
    526712                                                assert( mock_head(sl)  != sl.prev );
    527713                                        }
     
    573759                lanes.tscs = alloc(lanes.count, lanes.tscs`realloc);
    574760                for(i; lanes.count) {
    575                         unsigned long long tsc = ts(lanes.data[i]);
    576                         lanes.tscs[i].tv = tsc != 0 ? tsc : rdtscl();
     761                        unsigned long long tsc1 = ts(lanes.data[i]);
     762                        unsigned long long tsc2 = rdtscl();
     763                        lanes.tscs[i].tv = min(tsc1, tsc2);
    577764                }
    578765        #endif
    579766}
    580767
    581 // Grow the ready queue
    582 void ready_queue_grow(struct cluster * cltr) {
    583         size_t ncount;
    584         int target = cltr->procs.total;
    585 
    586         /* paranoid */ verify( ready_mutate_islocked() );
    587         __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n");
    588 
    589         // Make sure that everything is consistent
    590         /* paranoid */ check( cltr->ready_queue );
    591 
    592         // grow the ready queue
    593         with( cltr->ready_queue ) {
    594                 // Find new count
    595                 // Make sure we always have atleast 1 list
    596                 if(target >= 2) {
    597                         ncount = target * READYQ_SHARD_FACTOR;
    598                 } else {
    599                         ncount = SEQUENTIAL_SHARD;
    600                 }
    601 
    602                 // Allocate new array (uses realloc and memcpies the data)
    603                 lanes.data = alloc( ncount, lanes.data`realloc );
    604 
    605                 // Fix the moved data
    606                 for( idx; (size_t)lanes.count ) {
    607                         fix(lanes.data[idx]);
    608                 }
    609 
    610                 // Construct new data
    611                 for( idx; (size_t)lanes.count ~ ncount) {
    612                         (lanes.data[idx]){};
    613                 }
    614 
    615                 // Update original
    616                 lanes.count = ncount;
    617         }
    618 
    619         fix_times(cltr);
    620 
    621         reassign_cltr_id(cltr);
    622 
    623         // Make sure that everything is consistent
    624         /* paranoid */ check( cltr->ready_queue );
    625 
    626         __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n");
    627 
    628         /* paranoid */ verify( ready_mutate_islocked() );
    629 }
    630 
    631 // Shrink the ready queue
    632 void ready_queue_shrink(struct cluster * cltr) {
    633         /* paranoid */ verify( ready_mutate_islocked() );
    634         __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n");
    635 
    636         // Make sure that everything is consistent
    637         /* paranoid */ check( cltr->ready_queue );
    638 
    639         int target = cltr->procs.total;
    640 
    641         with( cltr->ready_queue ) {
    642                 // Remember old count
    643                 size_t ocount = lanes.count;
    644 
    645                 // Find new count
    646                 // Make sure we always have atleast 1 list
    647                 lanes.count = target >= 2 ? target * READYQ_SHARD_FACTOR: SEQUENTIAL_SHARD;
    648                 /* paranoid */ verify( ocount >= lanes.count );
    649                 /* paranoid */ verify( lanes.count == target * READYQ_SHARD_FACTOR || target < 2 );
    650 
    651                 // for printing count the number of displaced threads
    652                 #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
    653                         __attribute__((unused)) size_t displaced = 0;
    654                 #endif
    655 
    656                 // redistribute old data
    657                 for( idx; (size_t)lanes.count ~ ocount) {
    658                         // Lock is not strictly needed but makes checking invariants much easier
    659                         __attribute__((unused)) bool locked = __atomic_try_acquire(&lanes.data[idx].lock);
    660                         verify(locked);
    661 
    662                         // As long as we can pop from this lane to push the threads somewhere else in the queue
    663                         while(!is_empty(lanes.data[idx])) {
    664                                 struct $thread * thrd;
    665                                 unsigned long long _;
    666                                 [thrd, _] = pop(lanes.data[idx]);
    667 
    668                                 push(cltr, thrd, true);
    669 
    670                                 // for printing count the number of displaced threads
    671                                 #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
    672                                         displaced++;
    673                                 #endif
    674                         }
    675 
    676                         // Unlock the lane
    677                         __atomic_unlock(&lanes.data[idx].lock);
    678 
    679                         // TODO print the queue statistics here
    680 
    681                         ^(lanes.data[idx]){};
    682                 }
    683 
    684                 __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced);
    685 
    686                 // Allocate new array (uses realloc and memcpies the data)
    687                 lanes.data = alloc( lanes.count, lanes.data`realloc );
    688 
    689                 // Fix the moved data
    690                 for( idx; (size_t)lanes.count ) {
    691                         fix(lanes.data[idx]);
    692                 }
    693         }
    694 
    695         fix_times(cltr);
    696 
    697         reassign_cltr_id(cltr);
    698 
    699         // Make sure that everything is consistent
    700         /* paranoid */ check( cltr->ready_queue );
    701 
    702         __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n");
    703         /* paranoid */ verify( ready_mutate_islocked() );
    704 }
     768#if defined(USE_CPU_WORK_STEALING)
     769        // ready_queue size is fixed in this case
     770        void ready_queue_grow(struct cluster * cltr) {}
     771        void ready_queue_shrink(struct cluster * cltr) {}
     772#else
     773        // Grow the ready queue
     774        void ready_queue_grow(struct cluster * cltr) {
     775                size_t ncount;
     776                int target = cltr->procs.total;
     777
     778                /* paranoid */ verify( ready_mutate_islocked() );
     779                __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue\n");
     780
     781                // Make sure that everything is consistent
     782                /* paranoid */ check( cltr->ready_queue );
     783
     784                // grow the ready queue
     785                with( cltr->ready_queue ) {
     786                        // Find new count
     787                        // Make sure we always have atleast 1 list
     788                        if(target >= 2) {
     789                                ncount = target * READYQ_SHARD_FACTOR;
     790                        } else {
     791                                ncount = SEQUENTIAL_SHARD;
     792                        }
     793
     794                        // Allocate new array (uses realloc and memcpies the data)
     795                        lanes.data = alloc( ncount, lanes.data`realloc );
     796
     797                        // Fix the moved data
     798                        for( idx; (size_t)lanes.count ) {
     799                                fix(lanes.data[idx]);
     800                        }
     801
     802                        // Construct new data
     803                        for( idx; (size_t)lanes.count ~ ncount) {
     804                                (lanes.data[idx]){};
     805                        }
     806
     807                        // Update original
     808                        lanes.count = ncount;
     809                }
     810
     811                fix_times(cltr);
     812
     813                reassign_cltr_id(cltr);
     814
     815                // Make sure that everything is consistent
     816                /* paranoid */ check( cltr->ready_queue );
     817
     818                __cfadbg_print_safe(ready_queue, "Kernel : Growing ready queue done\n");
     819
     820                /* paranoid */ verify( ready_mutate_islocked() );
     821        }
     822
     823        // Shrink the ready queue
     824        void ready_queue_shrink(struct cluster * cltr) {
     825                /* paranoid */ verify( ready_mutate_islocked() );
     826                __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue\n");
     827
     828                // Make sure that everything is consistent
     829                /* paranoid */ check( cltr->ready_queue );
     830
     831                int target = cltr->procs.total;
     832
     833                with( cltr->ready_queue ) {
     834                        // Remember old count
     835                        size_t ocount = lanes.count;
     836
     837                        // Find new count
     838                        // Make sure we always have atleast 1 list
     839                        lanes.count = target >= 2 ? target * READYQ_SHARD_FACTOR: SEQUENTIAL_SHARD;
     840                        /* paranoid */ verify( ocount >= lanes.count );
     841                        /* paranoid */ verify( lanes.count == target * READYQ_SHARD_FACTOR || target < 2 );
     842
     843                        // for printing count the number of displaced threads
     844                        #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
     845                                __attribute__((unused)) size_t displaced = 0;
     846                        #endif
     847
     848                        // redistribute old data
     849                        for( idx; (size_t)lanes.count ~ ocount) {
     850                                // Lock is not strictly needed but makes checking invariants much easier
     851                                __attribute__((unused)) bool locked = __atomic_try_acquire(&lanes.data[idx].lock);
     852                                verify(locked);
     853
     854                                // As long as we can pop from this lane to push the threads somewhere else in the queue
     855                                while(!is_empty(lanes.data[idx])) {
     856                                        struct $thread * thrd;
     857                                        unsigned long long _;
     858                                        [thrd, _] = pop(lanes.data[idx]);
     859
     860                                        push(cltr, thrd, true);
     861
     862                                        // for printing count the number of displaced threads
     863                                        #if defined(__CFA_DEBUG_PRINT__) || defined(__CFA_DEBUG_PRINT_READY_QUEUE__)
     864                                                displaced++;
     865                                        #endif
     866                                }
     867
     868                                // Unlock the lane
     869                                __atomic_unlock(&lanes.data[idx].lock);
     870
     871                                // TODO print the queue statistics here
     872
     873                                ^(lanes.data[idx]){};
     874                        }
     875
     876                        __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue displaced %zu threads\n", displaced);
     877
     878                        // Allocate new array (uses realloc and memcpies the data)
     879                        lanes.data = alloc( lanes.count, lanes.data`realloc );
     880
     881                        // Fix the moved data
     882                        for( idx; (size_t)lanes.count ) {
     883                                fix(lanes.data[idx]);
     884                        }
     885                }
     886
     887                fix_times(cltr);
     888
     889                reassign_cltr_id(cltr);
     890
     891                // Make sure that everything is consistent
     892                /* paranoid */ check( cltr->ready_queue );
     893
     894                __cfadbg_print_safe(ready_queue, "Kernel : Shrinking ready queue done\n");
     895                /* paranoid */ verify( ready_mutate_islocked() );
     896        }
     897#endif
    705898
    706899#if !defined(__CFA_NO_STATISTICS__)
     
    710903        }
    711904#endif
     905
     906
     907#if   defined(CFA_HAVE_LINUX_LIBRSEQ)
     908        // No definition needed
     909#elif defined(CFA_HAVE_LINUX_RSEQ_H)
     910
     911        #if defined( __x86_64 ) || defined( __i386 )
     912                #define RSEQ_SIG        0x53053053
     913        #elif defined( __ARM_ARCH )
     914                #ifdef __ARMEB__
     915                #define RSEQ_SIG    0xf3def5e7      /* udf    #24035    ; 0x5de3 (ARMv6+) */
     916                #else
     917                #define RSEQ_SIG    0xe7f5def3      /* udf    #24035    ; 0x5de3 */
     918                #endif
     919        #endif
     920
     921        extern void __disable_interrupts_hard();
     922        extern void __enable_interrupts_hard();
     923
     924        void __kernel_raw_rseq_register  (void) {
     925                /* paranoid */ verify( __cfaabi_rseq.cpu_id == RSEQ_CPU_ID_UNINITIALIZED );
     926
     927                // int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), 0, (sigset_t *)0p, _NSIG / 8);
     928                int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), 0, RSEQ_SIG);
     929                if(ret != 0) {
     930                        int e = errno;
     931                        switch(e) {
     932                        case EINVAL: abort("KERNEL ERROR: rseq register invalid argument");
     933                        case ENOSYS: abort("KERNEL ERROR: rseq register no supported");
     934                        case EFAULT: abort("KERNEL ERROR: rseq register with invalid argument");
     935                        case EBUSY : abort("KERNEL ERROR: rseq register already registered");
     936                        case EPERM : abort("KERNEL ERROR: rseq register sig  argument  on unregistration does not match the signature received on registration");
     937                        default: abort("KERNEL ERROR: rseq register unexpected return %d", e);
     938                        }
     939                }
     940        }
     941
     942        void __kernel_raw_rseq_unregister(void) {
     943                /* paranoid */ verify( __cfaabi_rseq.cpu_id >= 0 );
     944
     945                // int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), RSEQ_FLAG_UNREGISTER, (sigset_t *)0p, _NSIG / 8);
     946                int ret = syscall(__NR_rseq, &__cfaabi_rseq, sizeof(struct rseq), RSEQ_FLAG_UNREGISTER, RSEQ_SIG);
     947                if(ret != 0) {
     948                        int e = errno;
     949                        switch(e) {
     950                        case EINVAL: abort("KERNEL ERROR: rseq unregister invalid argument");
     951                        case ENOSYS: abort("KERNEL ERROR: rseq unregister no supported");
     952                        case EFAULT: abort("KERNEL ERROR: rseq unregister with invalid argument");
     953                        case EBUSY : abort("KERNEL ERROR: rseq unregister already registered");
     954                        case EPERM : abort("KERNEL ERROR: rseq unregister sig  argument  on unregistration does not match the signature received on registration");
     955                        default: abort("KERNEL ERROR: rseq unregisteunexpected return %d", e);
     956                        }
     957                }
     958        }
     959#else
     960        // No definition needed
     961#endif
  • libcfa/src/concurrency/ready_subqueue.hfa

    r5a46e09 r660665f  
    3232        this.prev = mock_head(this);
    3333        this.anchor.next = 0p;
    34         this.anchor.ts   = 0;
     34        this.anchor.ts   = -1llu;
    3535        #if !defined(__CFA_NO_STATISTICS__)
    3636                this.cnt  = 0;
     
    4444        /* paranoid */ verify( &mock_head(this)->link.ts   == &this.anchor.ts   );
    4545        /* paranoid */ verify( mock_head(this)->link.next == 0p );
    46         /* paranoid */ verify( mock_head(this)->link.ts   == 0  );
     46        /* paranoid */ verify( mock_head(this)->link.ts   == -1llu  );
    4747        /* paranoid */ verify( mock_head(this) == this.prev );
    4848        /* paranoid */ verify( __alignof__(__intrusive_lane_t) == 128 );
     
    5555        // Make sure the list is empty
    5656        /* paranoid */ verify( this.anchor.next == 0p );
    57         /* paranoid */ verify( this.anchor.ts   == 0 );
     57        /* paranoid */ verify( this.anchor.ts   == -1llu );
    5858        /* paranoid */ verify( mock_head(this)  == this.prev );
    5959}
     
    6464        /* paranoid */ verify( this.lock );
    6565        /* paranoid */ verify( node->link.next == 0p );
    66         /* paranoid */ verify( node->link.ts   == 0  );
     66        /* paranoid */ verify( node->link.ts   == -1llu  );
    6767        /* paranoid */ verify( this.prev->link.next == 0p );
    68         /* paranoid */ verify( this.prev->link.ts   == 0  );
     68        /* paranoid */ verify( this.prev->link.ts   == -1llu  );
    6969        if( this.anchor.next == 0p ) {
    7070                /* paranoid */ verify( this.anchor.next == 0p );
    71                 /* paranoid */ verify( this.anchor.ts   == 0  );
     71                /* paranoid */ verify( this.anchor.ts   == -1llu );
     72                /* paranoid */ verify( this.anchor.ts   != 0  );
    7273                /* paranoid */ verify( this.prev == mock_head( this ) );
    7374        } else {
    7475                /* paranoid */ verify( this.anchor.next != 0p );
     76                /* paranoid */ verify( this.anchor.ts   != -1llu );
    7577                /* paranoid */ verify( this.anchor.ts   != 0  );
    7678                /* paranoid */ verify( this.prev != mock_head( this ) );
     
    9294        /* paranoid */ verify( this.lock );
    9395        /* paranoid */ verify( this.anchor.next != 0p );
     96        /* paranoid */ verify( this.anchor.ts   != -1llu );
    9497        /* paranoid */ verify( this.anchor.ts   != 0  );
    9598
     
    99102        this.anchor.next = node->link.next;
    100103        this.anchor.ts   = node->link.ts;
    101         bool is_empty = this.anchor.ts == 0;
     104        bool is_empty = this.anchor.next == 0p;
    102105        node->link.next = 0p;
    103         node->link.ts   = 0;
     106        node->link.ts   = -1llu;
    104107        #if !defined(__CFA_NO_STATISTICS__)
    105108                this.cnt--;
     
    110113
    111114        /* paranoid */ verify( node->link.next == 0p );
    112         /* paranoid */ verify( node->link.ts   == 0  );
     115        /* paranoid */ verify( node->link.ts   == -1llu  );
     116        /* paranoid */ verify( node->link.ts   != 0  );
     117        /* paranoid */ verify( this.anchor.ts  != 0  );
    113118        return [node, ts];
    114119}
     
    116121// Check whether or not list is empty
    117122static inline bool is_empty(__intrusive_lane_t & this) {
    118         return this.anchor.ts == 0;
     123        return this.anchor.next == 0p;
    119124}
    120125
     
    122127static inline unsigned long long ts(__intrusive_lane_t & this) {
    123128        // Cannot verify here since it may not be locked
     129        /* paranoid */ verify(this.anchor.ts != 0);
    124130        return this.anchor.ts;
    125131}
  • libcfa/src/concurrency/thread.cfa

    r5a46e09 r660665f  
    1515
    1616#define __cforall_thread__
     17#define _GNU_SOURCE
    1718
    1819#include "thread.hfa"
     
    3940        curr_cluster = &cl;
    4041        link.next = 0p;
    41         link.ts   = 0;
     42        link.ts   = -1llu;
    4243        preferred = -1u;
    4344        last_proc = 0p;
  • libcfa/src/containers/array.hfa

    r5a46e09 r660665f  
    11
    22
    3 // a type whose size is n
    4 #define Z(n) char[n]
    5 
    6 // the inverse of Z(-)
    7 #define z(N) sizeof(N)
    8 
    9 forall( T & ) struct tag {};
     3forall( __CFA_tysys_id_only_X & ) struct tag {};
    104#define ttag(T) ((tag(T)){})
    11 #define ztag(n) ttag(Z(n))
     5#define ztag(n) ttag(n)
    126
    137
     
    1812forall( [N], S & | sized(S), Timmed &, Tbase & ) {
    1913    struct arpk {
    20         S strides[z(N)];
     14        S strides[N];
    2115    };
    2216
     
    5650
    5751    static inline size_t ?`len( arpk(N, S, Timmed, Tbase) & a ) {
    58         return z(N);
     52        return N;
    5953    }
    6054
    6155    // workaround #226 (and array relevance thereof demonstrated in mike102/otype-slow-ndims.cfa)
    6256    static inline void ?{}( arpk(N, S, Timmed, Tbase) & this ) {
    63         void ?{}( S (&inner)[z(N)] ) {}
     57        void ?{}( S (&inner)[N] ) {}
    6458        ?{}(this.strides);
    6559    }
    6660    static inline void ^?{}( arpk(N, S, Timmed, Tbase) & this ) {
    67         void ^?{}( S (&inner)[z(N)] ) {}
     61        void ^?{}( S (&inner)[N] ) {}
    6862        ^?{}(this.strides);
    6963    }
     
    143137// Base
    144138forall( [Nq], Sq & | sized(Sq), Tbase & )
    145 static inline tag(arpk(Nq, Sq, Tbase, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(Tbase) ) {}
     139static inline tag(arpk(Nq, Sq, Tbase, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(Tbase) ) {
     140    tag(arpk(Nq, Sq, Tbase, Tbase)) ret;
     141    return ret;
     142}
    146143
    147144// Rec
    148145forall( [Nq], Sq & | sized(Sq), [N], S & | sized(S), recq &, recr &, Tbase & | { tag(recr) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(recq) ); } )
    149 static inline tag(arpk(N, S, recr, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(arpk(N, S, recq, Tbase)) ) {}
     146static inline tag(arpk(N, S, recr, Tbase)) enq_( tag(Tbase), tag(Nq), tag(Sq), tag(arpk(N, S, recq, Tbase)) ) {
     147    tag(arpk(N, S, recr, Tbase)) ret;
     148    return ret;
     149}
    150150
    151151// Wrapper
  • libcfa/src/exception.c

    r5a46e09 r660665f  
    2727#include "stdhdr/assert.h"
    2828#include "virtual.h"
    29 
    30 #if defined( __ARM_ARCH )
    31 #warning FIX ME: temporary hack to keep ARM build working
    32 #ifndef _URC_FATAL_PHASE1_ERROR
    33 #define _URC_FATAL_PHASE1_ERROR 3
    34 #endif // ! _URC_FATAL_PHASE1_ERROR
    35 #ifndef _URC_FATAL_PHASE2_ERROR
    36 #define _URC_FATAL_PHASE2_ERROR 2
    37 #endif // ! _URC_FATAL_PHASE2_ERROR
    38 #endif // __ARM_ARCH
    39 
    4029#include "lsda.h"
    4130
     
    267256        // the whole stack.
    268257
     258#if defined( __x86_64 ) || defined( __i386 )
    269259        // We did not simply reach the end of the stack without finding a handler. This is an error.
    270260        if ( ret != _URC_END_OF_STACK ) {
     261#else // defined( __ARM_ARCH )
     262        // The return code from _Unwind_RaiseException seems to be corrupt on ARM at end of stack.
     263        // This workaround tries to keep default exception handling working.
     264        if ( ret == _URC_FATAL_PHASE1_ERROR || ret == _URC_FATAL_PHASE2_ERROR ) {
     265#endif
    271266                printf("UNWIND ERROR %d after raise exception\n", ret);
    272267                abort();
     
    301296}
    302297
    303 #if defined( __x86_64 ) || defined( __i386 )
     298#if defined( __x86_64 ) || defined( __i386 ) || defined( __ARM_ARCH )
    304299// This is our personality routine. For every stack frame annotated with
    305300// ".cfi_personality 0x3,__gcfa_personality_v0" this function will be called twice when unwinding.
     
    419414                                    _Unwind_GetCFA(unwind_context) + 24;
    420415#                               elif defined( __ARM_ARCH )
    421 #                                   warning FIX ME: check if anything needed for ARM
    422                                     42;
     416                                    _Unwind_GetCFA(unwind_context) + 40;
    423417#                               endif
    424418                                int (*matcher)(exception_t *) = *(int(**)(exception_t *))match_pos;
     
    537531        // HEADER
    538532        ".LFECFA1:\n"
     533#if defined( __x86_64 ) || defined( __i386 )
    539534        "       .globl  __gcfa_personality_v0\n"
     535#else // defined( __ARM_ARCH )
     536        "       .global __gcfa_personality_v0\n"
     537#endif
    540538        "       .section        .gcc_except_table,\"a\",@progbits\n"
    541539        // TABLE HEADER (important field is the BODY length at the end)
     
    569567        // No clue what this does specifically
    570568        "       .section        .data.rel.local.CFA.ref.__gcfa_personality_v0,\"awG\",@progbits,CFA.ref.__gcfa_personality_v0,comdat\n"
     569#if defined( __x86_64 ) || defined( __i386 )
    571570        "       .align 8\n"
     571#else // defined( __ARM_ARCH )
     572        "       .align 3\n"
     573#endif
    572574        "       .type CFA.ref.__gcfa_personality_v0, @object\n"
    573575        "       .size CFA.ref.__gcfa_personality_v0, 8\n"
     
    575577#if defined( __x86_64 )
    576578        "       .quad __gcfa_personality_v0\n"
    577 #else // then __i386
     579#elif defined( __i386 )
    578580        "       .long __gcfa_personality_v0\n"
     581#else // defined( __ARM_ARCH )
     582        "       .xword __gcfa_personality_v0\n"
    579583#endif
    580584);
     
    583587        // HEADER
    584588        ".LFECFA1:\n"
     589#if defined( __x86_64 ) || defined( __i386 )
    585590        "       .globl  __gcfa_personality_v0\n"
     591#else // defined( __ARM_ARCH )
     592        "       .global __gcfa_personality_v0\n"
     593#endif
    586594        "       .section        .gcc_except_table,\"a\",@progbits\n"
    587595        // TABLE HEADER (important field is the BODY length at the end)
     
    612620#pragma GCC pop_options
    613621
    614 #elif defined( __ARM_ARCH )
    615 _Unwind_Reason_Code __gcfa_personality_v0(
    616                 int version,
    617                 _Unwind_Action actions,
    618                 unsigned long long exception_class,
    619                 struct _Unwind_Exception * unwind_exception,
    620                 struct _Unwind_Context * unwind_context) {
    621         return _URC_CONTINUE_UNWIND;
    622 }
    623 
    624 __attribute__((noinline))
    625 void __cfaehm_try_terminate(void (*try_block)(),
    626                 void (*catch_block)(int index, exception_t * except),
    627                 __attribute__((unused)) int (*match_block)(exception_t * except)) {
    628 }
    629622#else
    630623        #error unsupported hardware architecture
    631 #endif // __x86_64 || __i386
     624#endif // __x86_64 || __i386 || __ARM_ARCH
  • libcfa/src/interpose.cfa

    r5a46e09 r660665f  
    9595
    9696extern "C" {
    97         void __cfaabi_interpose_startup(void)  __attribute__(( constructor( STARTUP_PRIORITY_CORE ) ));
    9897        void __cfaabi_interpose_startup( void ) {
    9998                const char *version = 0p;
  • libcfa/src/startup.cfa

    r5a46e09 r660665f  
    2020
    2121extern "C" {
    22     void __cfaabi_appready_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_APPREADY ) ));
    23     void __cfaabi_appready_startup( void ) {
     22        void __cfaabi_appready_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_APPREADY ) ));
     23        void __cfaabi_appready_startup( void ) {
    2424                tzset();                                                                                // initialize time global variables
    2525                setlocale( LC_NUMERIC, getenv("LANG") );
     
    2828                heapAppStart();
    2929                #endif // __CFA_DEBUG__
    30     } // __cfaabi_appready_startup
     30        } // __cfaabi_appready_startup
    3131
    32     void __cfaabi_appready_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_APPREADY ) ));
    33     void __cfaabi_appready_shutdown( void ) {
     32        void __cfaabi_appready_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_APPREADY ) ));
     33        void __cfaabi_appready_shutdown( void ) {
    3434                #ifdef __CFA_DEBUG__
    3535                extern void heapAppStop();
    3636                heapAppStop();
    3737                #endif // __CFA_DEBUG__
    38     } // __cfaabi_appready_shutdown
     38        } // __cfaabi_appready_shutdown
    3939
    40     void disable_interrupts() __attribute__(( weak )) {}
    41     void enable_interrupts() __attribute__(( weak )) {}
     40        void disable_interrupts() __attribute__(( weak )) {}
     41        void enable_interrupts() __attribute__(( weak )) {}
     42
     43
     44        extern void __cfaabi_interpose_startup( void );
     45        extern void __cfaabi_device_startup   ( void );
     46        extern void __cfaabi_device_shutdown  ( void );
     47
     48        void __cfaabi_core_startup( void ) __attribute__(( constructor( STARTUP_PRIORITY_CORE ) ));
     49        void __cfaabi_core_startup( void ) {
     50                __cfaabi_interpose_startup();
     51                __cfaabi_device_startup();
     52        } // __cfaabi_core_startup
     53
     54        void __cfaabi_core_shutdown( void ) __attribute__(( destructor( STARTUP_PRIORITY_CORE ) ));
     55        void __cfaabi_core_shutdown( void ) {
     56                __cfaabi_device_shutdown();
     57        } // __cfaabi_core_shutdown
    4258} // extern "C"
    4359
  • src/AST/Convert.cpp

    r5a46e09 r660665f  
    24152415        }
    24162416
     2417        virtual void visit( const DimensionExpr * old ) override final {
     2418                // DimensionExpr gets desugared away in Validate.
     2419                // As long as new-AST passes don't use it, this cheap-cheerful error
     2420                // detection helps ensure that these occurrences have been compiled
     2421                // away, as expected.  To move the DimensionExpr boundary downstream
     2422                // or move the new-AST translation boundary upstream, implement
     2423                // DimensionExpr in the new AST and implement a conversion.
     2424                (void) old;
     2425                assert(false && "DimensionExpr should not be present at new-AST boundary");
     2426        }
     2427
    24172428        virtual void visit( const AsmExpr * old ) override final {
    24182429                this->node = visitBaseExpr( old,
  • src/AST/Decl.cpp

    r5a46e09 r660665f  
    7878
    7979const char * TypeDecl::typeString() const {
    80         static const char * kindNames[] = { "sized data type", "sized data type", "sized object type", "sized function type", "sized tuple type", "sized array length type" };
     80        static const char * kindNames[] = { "sized data type", "sized data type", "sized object type", "sized function type", "sized tuple type", "sized length value" };
    8181        static_assert( sizeof(kindNames) / sizeof(kindNames[0]) == TypeDecl::NUMBER_OF_KINDS, "typeString: kindNames is out of sync." );
    8282        assertf( kind < TypeDecl::NUMBER_OF_KINDS, "TypeDecl kind is out of bounds." );
  • src/AST/Decl.hpp

    r5a46e09 r660665f  
    175175class TypeDecl final : public NamedTypeDecl {
    176176  public:
    177         enum Kind { Dtype, DStype, Otype, Ftype, Ttype, ALtype, NUMBER_OF_KINDS };
     177        enum Kind { Dtype, DStype, Otype, Ftype, Ttype, Dimension, NUMBER_OF_KINDS };
    178178
    179179        Kind kind;
  • src/AST/Pass.impl.hpp

    r5a46e09 r660665f  
    479479                        guard_symtab guard { *this };
    480480                        // implicit add __func__ identifier as specified in the C manual 6.4.2.2
    481                         static ast::ptr< ast::ObjectDecl > func{ new ast::ObjectDecl{ 
     481                        static ast::ptr< ast::ObjectDecl > func{ new ast::ObjectDecl{
    482482                                CodeLocation{}, "__func__",
    483483                                new ast::ArrayType{
     
    522522        VISIT({
    523523                guard_symtab guard { * this };
    524                 maybe_accept( node, &StructDecl::params  );
    525                 maybe_accept( node, &StructDecl::members );
     524                maybe_accept( node, &StructDecl::params     );
     525                maybe_accept( node, &StructDecl::members    );
     526                maybe_accept( node, &StructDecl::attributes );
    526527        })
    527528
     
    543544        VISIT({
    544545                guard_symtab guard { * this };
    545                 maybe_accept( node, &UnionDecl::params  );
    546                 maybe_accept( node, &UnionDecl::members );
     546                maybe_accept( node, &UnionDecl::params     );
     547                maybe_accept( node, &UnionDecl::members    );
     548                maybe_accept( node, &UnionDecl::attributes );
    547549        })
    548550
     
    562564        VISIT(
    563565                // unlike structs, traits, and unions, enums inject their members into the global scope
    564                 maybe_accept( node, &EnumDecl::params  );
    565                 maybe_accept( node, &EnumDecl::members );
     566                maybe_accept( node, &EnumDecl::params     );
     567                maybe_accept( node, &EnumDecl::members    );
     568                maybe_accept( node, &EnumDecl::attributes );
    566569        )
    567570
     
    577580        VISIT({
    578581                guard_symtab guard { *this };
    579                 maybe_accept( node, &TraitDecl::params  );
    580                 maybe_accept( node, &TraitDecl::members );
     582                maybe_accept( node, &TraitDecl::params     );
     583                maybe_accept( node, &TraitDecl::members    );
     584                maybe_accept( node, &TraitDecl::attributes );
    581585        })
    582586
  • src/CodeGen/CodeGenerator.cc

    r5a46e09 r660665f  
    589589                        output << nameExpr->get_name();
    590590                } // if
     591        }
     592
     593        void CodeGenerator::postvisit( DimensionExpr * dimensionExpr ) {
     594                extension( dimensionExpr );
     595                output << "/*non-type*/" << dimensionExpr->get_name();
    591596        }
    592597
  • src/CodeGen/CodeGenerator.h

    r5a46e09 r660665f  
    9292                void postvisit( TupleIndexExpr * tupleExpr );
    9393                void postvisit( TypeExpr *typeExpr );
     94                void postvisit( DimensionExpr *dimensionExpr );
    9495                void postvisit( AsmExpr * );
    9596                void postvisit( StmtExpr * );
  • src/Common/PassVisitor.h

    r5a46e09 r660665f  
    167167        virtual void visit( TypeExpr * typeExpr ) override final;
    168168        virtual void visit( const TypeExpr * typeExpr ) override final;
     169        virtual void visit( DimensionExpr * dimensionExpr ) override final;
     170        virtual void visit( const DimensionExpr * dimensionExpr ) override final;
    169171        virtual void visit( AsmExpr * asmExpr ) override final;
    170172        virtual void visit( const AsmExpr * asmExpr ) override final;
     
    309311        virtual Expression * mutate( CommaExpr * commaExpr ) override final;
    310312        virtual Expression * mutate( TypeExpr * typeExpr ) override final;
     313        virtual Expression * mutate( DimensionExpr * dimensionExpr ) override final;
    311314        virtual Expression * mutate( AsmExpr * asmExpr ) override final;
    312315        virtual Expression * mutate( ImplicitCopyCtorExpr * impCpCtorExpr ) override final;
     
    542545class WithIndexer {
    543546protected:
    544         WithIndexer() {}
     547        WithIndexer( bool trackIdentifiers = true ) : indexer(trackIdentifiers) {}
    545548        ~WithIndexer() {}
    546549
  • src/Common/PassVisitor.impl.h

    r5a46e09 r660665f  
    636636                maybeAccept_impl( node->parameters, *this );
    637637                maybeAccept_impl( node->members   , *this );
     638                maybeAccept_impl( node->attributes, *this );
    638639        }
    639640
     
    656657                maybeAccept_impl( node->parameters, *this );
    657658                maybeAccept_impl( node->members   , *this );
     659                maybeAccept_impl( node->attributes, *this );
    658660        }
    659661
     
    676678                maybeMutate_impl( node->parameters, *this );
    677679                maybeMutate_impl( node->members   , *this );
     680                maybeMutate_impl( node->attributes, *this );
    678681        }
    679682
     
    697700                maybeAccept_impl( node->parameters, *this );
    698701                maybeAccept_impl( node->members   , *this );
     702                maybeAccept_impl( node->attributes, *this );
    699703        }
    700704
     
    714718                maybeAccept_impl( node->parameters, *this );
    715719                maybeAccept_impl( node->members   , *this );
     720                maybeAccept_impl( node->attributes, *this );
    716721        }
    717722
     
    732737                maybeMutate_impl( node->parameters, *this );
    733738                maybeMutate_impl( node->members   , *this );
     739                maybeMutate_impl( node->attributes, *this );
    734740        }
    735741
     
    750756        maybeAccept_impl( node->parameters, *this );
    751757        maybeAccept_impl( node->members   , *this );
     758        maybeAccept_impl( node->attributes, *this );
    752759
    753760        VISIT_END( node );
     
    763770        maybeAccept_impl( node->parameters, *this );
    764771        maybeAccept_impl( node->members   , *this );
     772        maybeAccept_impl( node->attributes, *this );
    765773
    766774        VISIT_END( node );
     
    776784        maybeMutate_impl( node->parameters, *this );
    777785        maybeMutate_impl( node->members   , *this );
     786        maybeMutate_impl( node->attributes, *this );
    778787
    779788        MUTATE_END( Declaration, node );
     
    790799                maybeAccept_impl( node->parameters, *this );
    791800                maybeAccept_impl( node->members   , *this );
     801                maybeAccept_impl( node->attributes, *this );
    792802        }
    793803
     
    805815                maybeAccept_impl( node->parameters, *this );
    806816                maybeAccept_impl( node->members   , *this );
     817                maybeAccept_impl( node->attributes, *this );
    807818        }
    808819
     
    820831                maybeMutate_impl( node->parameters, *this );
    821832                maybeMutate_impl( node->members   , *this );
     833                maybeMutate_impl( node->attributes, *this );
    822834        }
    823835
     
    25072519
    25082520//--------------------------------------------------------------------------
     2521// DimensionExpr
     2522template< typename pass_type >
     2523void PassVisitor< pass_type >::visit( DimensionExpr * node ) {
     2524        VISIT_START( node );
     2525
     2526        indexerScopedAccept( node->result, *this );
     2527
     2528        VISIT_END( node );
     2529}
     2530
     2531template< typename pass_type >
     2532void PassVisitor< pass_type >::visit( const DimensionExpr * node ) {
     2533        VISIT_START( node );
     2534
     2535        indexerScopedAccept( node->result, *this );
     2536
     2537        VISIT_END( node );
     2538}
     2539
     2540template< typename pass_type >
     2541Expression * PassVisitor< pass_type >::mutate( DimensionExpr * node ) {
     2542        MUTATE_START( node );
     2543
     2544        indexerScopedMutate( node->env   , *this );
     2545        indexerScopedMutate( node->result, *this );
     2546
     2547        MUTATE_END( Expression, node );
     2548}
     2549
     2550//--------------------------------------------------------------------------
    25092551// AsmExpr
    25102552template< typename pass_type >
     
    31453187
    31463188        maybeAccept_impl( node->forall, *this );
    3147         // xxx - should PointerType visit/mutate dimension?
     3189        maybeAccept_impl( node->dimension, *this );
    31483190        maybeAccept_impl( node->base, *this );
    31493191
     
    31563198
    31573199        maybeAccept_impl( node->forall, *this );
    3158         // xxx - should PointerType visit/mutate dimension?
     3200        maybeAccept_impl( node->dimension, *this );
    31593201        maybeAccept_impl( node->base, *this );
    31603202
     
    31673209
    31683210        maybeMutate_impl( node->forall, *this );
    3169         // xxx - should PointerType visit/mutate dimension?
     3211        maybeMutate_impl( node->dimension, *this );
    31703212        maybeMutate_impl( node->base, *this );
    31713213
     
    38563898
    38573899//--------------------------------------------------------------------------
    3858 // Attribute
     3900// Constant
    38593901template< typename pass_type >
    38603902void PassVisitor< pass_type >::visit( Constant * node ) {
  • src/InitTweak/InitTweak.cc

    r5a46e09 r660665f  
    1010// Created On       : Fri May 13 11:26:36 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Dec 13 23:15:52 2019
    13 // Update Count     : 8
     12// Last Modified On : Wed Jun 16 20:57:22 2021
     13// Update Count     : 18
    1414//
    1515
     
    12171217        void addDataSectonAttribute( ObjectDecl * objDecl ) {
    12181218                objDecl->attributes.push_back(new Attribute("section", {
    1219                         new ConstantExpr( Constant::from_string(".data#") ),
    1220                 }));
     1219                        new ConstantExpr( Constant::from_string(".data"
     1220#if defined( __x86_64 ) || defined( __i386 ) // assembler comment to prevent assembler warning message
     1221                                        "#"
     1222#else // defined( __ARM_ARCH )
     1223                                        "//"
     1224#endif
     1225                                ))}));
    12211226        }
    12221227
    12231228        void addDataSectionAttribute( ast::ObjectDecl * objDecl ) {
    12241229                objDecl->attributes.push_back(new ast::Attribute("section", {
    1225                         ast::ConstantExpr::from_string(objDecl->location, ".data#"),
    1226                 }));
     1230                        ast::ConstantExpr::from_string(objDecl->location, ".data"
     1231#if defined( __x86_64 ) || defined( __i386 ) // assembler comment to prevent assembler warning message
     1232                                        "#"
     1233#else // defined( __ARM_ARCH )
     1234                                        "//"
     1235#endif
     1236                                )}));
    12271237        }
    12281238
  • src/Parser/DeclarationNode.cc

    r5a46e09 r660665f  
    10761076        if ( variable.tyClass != TypeDecl::NUMBER_OF_KINDS ) {
    10771077                // otype is internally converted to dtype + otype parameters
    1078                 static const TypeDecl::Kind kindMap[] = { TypeDecl::Dtype, TypeDecl::DStype, TypeDecl::Dtype, TypeDecl::Ftype, TypeDecl::Ttype, TypeDecl::Dtype };
     1078                static const TypeDecl::Kind kindMap[] = { TypeDecl::Dtype, TypeDecl::Dtype, TypeDecl::Dtype, TypeDecl::Ftype, TypeDecl::Ttype, TypeDecl::Dimension };
    10791079                static_assert( sizeof(kindMap) / sizeof(kindMap[0]) == TypeDecl::NUMBER_OF_KINDS, "DeclarationNode::build: kindMap is out of sync." );
    10801080                assertf( variable.tyClass < sizeof(kindMap)/sizeof(kindMap[0]), "Variable's tyClass is out of bounds." );
    1081                 TypeDecl * ret = new TypeDecl( *name, Type::StorageClasses(), nullptr, kindMap[ variable.tyClass ], variable.tyClass == TypeDecl::Otype || variable.tyClass == TypeDecl::ALtype, variable.initializer ? variable.initializer->buildType() : nullptr );
     1081                TypeDecl * ret = new TypeDecl( *name, Type::StorageClasses(), nullptr, kindMap[ variable.tyClass ], variable.tyClass == TypeDecl::Otype || variable.tyClass == TypeDecl::DStype, variable.initializer ? variable.initializer->buildType() : nullptr );
    10821082                buildList( variable.assertions, ret->get_assertions() );
    10831083                return ret;
  • src/Parser/ExpressionNode.cc

    r5a46e09 r660665f  
    509509} // build_varref
    510510
     511DimensionExpr * build_dimensionref( const string * name ) {
     512        DimensionExpr * expr = new DimensionExpr( *name );
     513        delete name;
     514        return expr;
     515} // build_varref
    511516// TODO: get rid of this and OperKinds and reuse code from OperatorTable
    512517static const char * OperName[] = {                                              // must harmonize with OperKinds
  • src/Parser/ParseNode.h

    r5a46e09 r660665f  
    183183
    184184NameExpr * build_varref( const std::string * name );
     185DimensionExpr * build_dimensionref( const std::string * name );
    185186
    186187Expression * build_cast( DeclarationNode * decl_node, ExpressionNode * expr_node );
  • src/Parser/TypedefTable.cc

    r5a46e09 r660665f  
    1010// Created On       : Sat May 16 15:20:13 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Mon Mar 15 20:56:47 2021
    13 // Update Count     : 260
     12// Last Modified On : Wed May 19 08:30:14 2021
     13// Update Count     : 262
    1414//
    1515
     
    3131        switch ( kind ) {
    3232          case IDENTIFIER: return "identifier";
     33          case TYPEDIMname: return "typedim";
    3334          case TYPEDEFname: return "typedef";
    3435          case TYPEGENname: return "typegen";
  • src/Parser/lex.ll

    r5a46e09 r660665f  
    1010 * Created On       : Sat Sep 22 08:58:10 2001
    1111 * Last Modified By : Peter A. Buhr
    12  * Last Modified On : Thu Apr  1 13:22:31 2021
    13  * Update Count     : 754
     12 * Last Modified On : Sun Jun 20 18:41:09 2021
     13 * Update Count     : 759
    1414 */
    1515
     
    117117hex_constant {hex_prefix}{hex_digits}{integer_suffix_opt}
    118118
    119                                 // GCC: D (double) and iI (imaginary) suffixes, and DL (long double)
     119                                // GCC: floating D (double), imaginary iI, and decimal floating DF, DD, DL
    120120exponent "_"?[eE]"_"?[+-]?{decimal_digits}
    121121floating_size 16|32|32x|64|64x|80|128|128x
    122122floating_length ([fFdDlLwWqQ]|[fF]{floating_size})
    123123floating_suffix ({floating_length}?[iI]?)|([iI]{floating_length})
    124 floating_suffix_opt ("_"?({floating_suffix}|"DL"))?
     124decimal_floating_suffix [dD][fFdDlL]
     125floating_suffix_opt ("_"?({floating_suffix}|{decimal_floating_suffix}))?
    125126decimal_digits ({decimal})|({decimal}({decimal}|"_")*{decimal})
    126127floating_decimal {decimal_digits}"."{exponent}?{floating_suffix_opt}
     
    234235continue                { KEYWORD_RETURN(CONTINUE); }
    235236coroutine               { KEYWORD_RETURN(COROUTINE); }                  // CFA
     237_Decimal32              { KEYWORD_RETURN(DECIMAL32); }                  // GCC
     238_Decimal64              { KEYWORD_RETURN(DECIMAL64); }                  // GCC
     239_Decimal128             { KEYWORD_RETURN(DECIMAL128); }                 // GCC
    236240default                 { KEYWORD_RETURN(DEFAULT); }
    237241disable                 { KEYWORD_RETURN(DISABLE); }                    // CFA
  • src/Parser/parser.yy

    r5a46e09 r660665f  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Mon Apr 26 18:41:54 2021
    13 // Update Count     : 4990
     12// Last Modified On : Tue Jun 29 09:12:47 2021
     13// Update Count     : 5027
    1414//
    1515
     
    2626// The root language for this grammar is ANSI99/11 C. All of ANSI99/11 is parsed, except for:
    2727//
    28 // 1. designation with '=' (use ':' instead)
    29 //
    30 // Most of the syntactic extensions from ANSI90 to ANSI11 C are marked with the comment "C99/C11". This grammar also has
    31 // two levels of extensions. The first extensions cover most of the GCC C extensions, except for:
    32 //
    33 // 1. designation with and without '=' (use ':' instead)
    34 
    35 //
    36 // All of the syntactic extensions for GCC C are marked with the comment "GCC". The second extensions are for Cforall
    37 // (CFA), which fixes several of C's outstanding problems and extends C with many modern language concepts. All of the
    38 // syntactic extensions for CFA C are marked with the comment "CFA". As noted above, there is one unreconcileable
    39 // parsing problem between C99 and CFA with respect to designators; this is discussed in detail before the "designation"
    40 // grammar rule.
     28//   designation with '=' (use ':' instead)
     29//
     30// This incompatibility is discussed in detail before the "designation" grammar rule.  Most of the syntactic extensions
     31// from ANSI90 to ANSI11 C are marked with the comment "C99/C11".
     32
     33// This grammar also has two levels of extensions. The first extensions cover most of the GCC C extensions All of the
     34// syntactic extensions for GCC C are marked with the comment "GCC". The second extensions are for Cforall (CFA), which
     35// fixes several of C's outstanding problems and extends C with many modern language concepts. All of the syntactic
     36// extensions for CFA C are marked with the comment "CFA".
    4137
    4238%{
     
    269265%token INT128 UINT128 uuFLOAT80 uuFLOAT128                              // GCC
    270266%token uFLOAT16 uFLOAT32 uFLOAT32X uFLOAT64 uFLOAT64X uFLOAT128 // GCC
     267%token DECIMAL32 DECIMAL64 DECIMAL128                                   // GCC
    271268%token ZERO_T ONE_T                                                                             // CFA
    272269%token SIZEOF TYPEOF VALIST AUTO_TYPE                                   // GCC
     
    287284
    288285// names and constants: lexer differentiates between identifier and typedef names
    289 %token<tok> IDENTIFIER          QUOTED_IDENTIFIER       TYPEDEFname             TYPEGENname
     286%token<tok> IDENTIFIER          QUOTED_IDENTIFIER       TYPEDIMname             TYPEDEFname             TYPEGENname
    290287%token<tok> TIMEOUT                     WOR                                     CATCH                   RECOVER                 CATCHRESUME             FIXUP           FINALLY         // CFA
    291288%token<tok> INTEGERconstant     CHARACTERconstant       STRINGliteral
     
    586583        | quasi_keyword
    587584                { $$ = new ExpressionNode( build_varref( $1 ) ); }
     585        | TYPEDIMname                                                                           // CFA, generic length argument
     586                // { $$ = new ExpressionNode( new TypeExpr( maybeMoveBuildType( DeclarationNode::newFromTypedef( $1 ) ) ) ); }
     587                // { $$ = new ExpressionNode( build_varref( $1 ) ); }
     588                { $$ = new ExpressionNode( build_dimensionref( $1 ) ); }
    588589        | tuple
    589590        | '(' comma_expression ')'
     
    630631postfix_expression:
    631632        primary_expression
    632         | postfix_expression '[' assignment_expression ',' comma_expression ']'
    633                 // { $$ = new ExpressionNode( build_binary_val( OperKinds::Index, $1, new ExpressionNode( build_binary_val( OperKinds::Index, $3, $5 ) ) ) ); }
    634                 { SemanticError( yylloc, "New array subscript is currently unimplemented." ); $$ = nullptr; }
     633        | postfix_expression '[' assignment_expression ',' tuple_expression_list ']'
     634                        // Historic, transitional: Disallow commas in subscripts.
     635                        // Switching to this behaviour may help check if a C compatibilty case uses comma-exprs in subscripts.
     636                // { SemanticError( yylloc, "New array subscript is currently unimplemented." ); $$ = nullptr; }
     637                        // Current: Commas in subscripts make tuples.
     638                { $$ = new ExpressionNode( build_binary_val( OperKinds::Index, $1, new ExpressionNode( build_tuple( (ExpressionNode *)($3->set_last( $5 ) ) )) ) ); }
    635639        | postfix_expression '[' assignment_expression ']'
    636640                // CFA, comma_expression disallowed in this context because it results in a common user error: subscripting a
     
    18871891        | uFLOAT128
    18881892                { $$ = DeclarationNode::newBasicType( DeclarationNode::uFloat128 ); }
     1893        | DECIMAL32
     1894                { SemanticError( yylloc, "_Decimal32 is currently unimplemented." ); $$ = nullptr; }
     1895        | DECIMAL64
     1896                { SemanticError( yylloc, "_Decimal64 is currently unimplemented." ); $$ = nullptr; }
     1897        | DECIMAL128
     1898                { SemanticError( yylloc, "_Decimal128 is currently unimplemented." ); $$ = nullptr; }
    18891899        | COMPLEX                                                                                       // C99
    18901900                { $$ = DeclarationNode::newComplexType( DeclarationNode::Complex ); }
     
    19091919        // empty
    19101920                { $$ = nullptr; }
    1911         | vtable;
     1921        | vtable
    19121922        ;
    19131923
     
    25352545        | '[' identifier_or_type_name ']'
    25362546                {
    2537                         typedefTable.addToScope( *$2, TYPEDEFname, "9" );
    2538                         $$ = DeclarationNode::newTypeParam( TypeDecl::ALtype, $2 );
     2547                        typedefTable.addToScope( *$2, TYPEDIMname, "9" );
     2548                        $$ = DeclarationNode::newTypeParam( TypeDecl::Dimension, $2 );
    25392549                }
    25402550        // | type_specifier identifier_parameter_declarator
     
    25502560        | '*'
    25512561                { $$ = TypeDecl::DStype; }                                              // dtype + sized
     2562        // | '(' '*' ')'
     2563        //      { $$ = TypeDecl::Ftype; }
    25522564        | ELLIPSIS
    25532565                { $$ = TypeDecl::Ttype; }
     
    25902602                { $$ = new ExpressionNode( new TypeExpr( maybeMoveBuildType( $1 ) ) ); }
    25912603        | assignment_expression
    2592                 { SemanticError( yylloc, toString("Expression generic parameters are currently unimplemented: ", $1->build()) ); $$ = nullptr; }
    25932604        | type_list ',' type
    25942605                { $$ = (ExpressionNode *)($1->set_last( new ExpressionNode( new TypeExpr( maybeMoveBuildType( $3 ) ) ) )); }
    25952606        | type_list ',' assignment_expression
    2596                 { SemanticError( yylloc, toString("Expression generic parameters are currently unimplemented: ", $3->build()) ); $$ = nullptr; }
    2597                 // { $$ = (ExpressionNode *)( $1->set_last( $3 )); }
     2607                { $$ = (ExpressionNode *)( $1->set_last( $3 )); }
    25982608        ;
    25992609
  • src/SymTab/Indexer.cc

    r5a46e09 r660665f  
    7474        }
    7575
    76         Indexer::Indexer()
     76        Indexer::Indexer( bool trackIdentifiers )
    7777        : idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable(),
    78           prevScope(), scope( 0 ), repScope( 0 ) { ++* stats().count; }
     78          prevScope(), scope( 0 ), repScope( 0 ), trackIdentifiers( trackIdentifiers ) { ++* stats().count; }
    7979
    8080        Indexer::~Indexer() {
     
    110110
    111111        void Indexer::lookupId( const std::string & id, std::list< IdData > &out ) const {
     112                assert( trackIdentifiers );
     113
    112114                ++* stats().lookup_calls;
    113115                if ( ! idTable ) return;
     
    434436                        const Declaration * deleteStmt ) {
    435437                ++* stats().add_calls;
     438                if ( ! trackIdentifiers ) return;
    436439                const std::string &name = decl->name;
    437440                if ( name == "" ) return;
  • src/SymTab/Indexer.h

    r5a46e09 r660665f  
    3131        class Indexer : public std::enable_shared_from_this<SymTab::Indexer> {
    3232        public:
    33                 explicit Indexer();
     33                explicit Indexer( bool trackIdentifiers = true );
    3434                virtual ~Indexer();
    3535
     
    180180                /// returns true if there exists a declaration with C linkage and the given name with a different mangled name
    181181                bool hasIncompatibleCDecl( const std::string & id, const std::string & mangleName ) const;
     182
     183            bool trackIdentifiers;
    182184        };
    183185} // namespace SymTab
  • src/SymTab/Validate.cc

    r5a46e09 r660665f  
    105105
    106106        struct FixQualifiedTypes final : public WithIndexer {
     107                FixQualifiedTypes() : WithIndexer(false) {}
    107108                Type * postmutate( QualifiedType * );
    108109        };
     
    174175        };
    175176
     177        /// Does early resolution on the expressions that give enumeration constants their values
     178        struct ResolveEnumInitializers final : public WithIndexer, public WithGuards, public WithVisitorRef<ResolveEnumInitializers>, public WithShortCircuiting {
     179                ResolveEnumInitializers( const Indexer * indexer );
     180                void postvisit( EnumDecl * enumDecl );
     181
     182          private:
     183                const Indexer * local_indexer;
     184
     185