Index: doc/proposals/concurrency/Makefile =================================================================== --- doc/proposals/concurrency/Makefile (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ doc/proposals/concurrency/Makefile (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -13,4 +13,5 @@ annex/glossary \ text/intro \ +text/cforall \ text/basics \ text/concurrency \ Index: doc/proposals/concurrency/build/bump_ver.sh =================================================================== --- doc/proposals/concurrency/build/bump_ver.sh (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ doc/proposals/concurrency/build/bump_ver.sh (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -1,6 +1,6 @@ #!/bin/bash -if [ ! -f build/version ]; then - echo "0.0.0" > build/version +if [ ! -f version ]; then + echo "0.0.0" > version fi -sed -r 's/([0-9]+\.[0-9]+.)([0-9]+)/echo "\1\$((\2+1))" > version/ge' build/version > /dev/null +sed -r 's/([0-9]+\.[0-9]+.)([0-9]+)/echo "\1\$((\2+1))" > version/ge' version > /dev/null Index: doc/proposals/concurrency/build/version =================================================================== --- doc/proposals/concurrency/build/version (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ (revision ) @@ -1,1 +1,0 @@ -0.9.117 Index: doc/proposals/concurrency/text/basics.tex =================================================================== --- doc/proposals/concurrency/text/basics.tex (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ doc/proposals/concurrency/text/basics.tex (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -7,12 +7,11 @@ \section{Basics of concurrency} -At its core, concurrency is based on having multiple call stacks and potentially multiple threads of execution for these stacks. Concurrency alone without parallelism only requires having multiple call stacks (or contexts) for a single thread of execution and switching between these call stacks on a regular basis. A minimal concurrency product can be achieved by creating coroutines which instead of context switching between each other, always ask an oracle where to context switch next. While coroutines do not technically require a stack, stackfull coroutines are the closest abstraction to a practical "naked"" call stack. When writing concurrency in terms of coroutines, the oracle effectively becomes a scheduler and the whole system now follows a cooperative threading model \cit. The oracle/scheduler can either be a stackless or stackfull entity and correspondingly require one or two context switches to run a different coroutine but in any case a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to be present, the only feature missing is preemption. Indeed, concurrency challenges appear with the lack of determinism. Guaranteeing mutual-exclusion or synchronisation are simply ways of limiting the lack of determinism in the system. A scheduler introduces order of execution uncertainty while preemption introduces incertainty about when context-switches occur. Now it is important to understand that uncertainty is not necessarily undesireable, uncertainty can often be used by systems to significantly increase performance and is often the basis of giving the user the illusion that hundred of tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as little determinism as correctness will allow\cit. +At its core, concurrency is based on having call-stacks and potentially multiple threads of execution for these stacks. Concurrency without parallelism only requires having multiple call stacks (or contexts) for a single thread of execution, and switching between these call stacks on a regular basis. A minimal concurrency product can be achieved by creating coroutines, which instead of context switching between each other, always ask an oracle where to context switch next. While coroutines do not technically require a stack, stackfull coroutines are the closest abstraction to a practical "naked"" call stack. When writing concurrency in terms of coroutines, the oracle effectively becomes a scheduler and the whole system now follows a cooperative threading-model \cit. The oracle/scheduler can either be a stackless or stackfull entity and correspondingly require one or two context switches to run a different coroutine. In any case, a subset of concurrency related challenges start to appear. For the complete set of concurrency challenges to occur, the only feature missing is preemption. Indeed, concurrency challenges appear with non-determinism. Guaranteeing mutual-exclusion or synchronisation are simply ways of limiting the lack of determinism in a system. A scheduler introduces order of execution uncertainty, while preemption introduces incertainty about where context-switches occur. Now it is important to understand that uncertainty is not necessarily undesireable; uncertainty can often be used by systems to significantly increase performance and is often the basis of giving a user the illusion that tasks are running in parallel. Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows\cit. \section{\protect\CFA 's Thread Building Blocks} -% As a system-level language, \CFA should offer both performance and flexibilty as its primary goals, simplicity and user-friendliness being a secondary concern. Therefore, the core of parallelism in \CFA should prioritize power and efficiency. With this said, deconstructing popular paradigms in order to get simple building blocks yields \glspl{uthread} as the core parallelism block. \Glspl{pool} and other parallelism paradigms can then be built on top of the underlying threading model. -One of the important features that is missing to C is threading. On modern architectures, the lack of threading is becoming less and less forgivable\cite{Sutter05, Sutter05b} and therefore any modern programming language should have the proper tools to allow users to write performant concurrent and/or parallel programs. As an extension of C, \CFA needs to express these concepts an a way that is as natural as possible to programmers used to imperative languages. And being a system level language means programmers will expect to be able to choose precisely which features they need and which cost they are willing to pay. - -\section{Coroutines A stepping stone}\label{coroutine} -While the main focus of this proposal is concurrency and parallelism, as mentionned above it is important to adress coroutines which are actually a significant underlying aspect of the concurrency system. Indeed, while having nothing todo with parallelism and arguably little to do with concurrency, coroutines need to deal with context-switchs and and other context management operations. Therefore, this proposal includes coroutines both as an intermediate step for the implementation of threads and a first class feature of \CFA. Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant. The core API of coroutines revolve around two features independent call stacks and \code{suspend}/\code{resume}. +One of the important features that is missing in C is threading. On modern architectures, a lack of threading is becoming less and less forgivable\cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write performant concurrent and/or parallel programs. As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers used to imperative languages. And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay. + +\section{Coroutines: A stepping stone}\label{coroutine} +While the main focus of this proposal is concurrency and parallelism, as mentionned above it is important to adress coroutines, which are actually a significant underlying aspect of a concurrency system. Indeed, while having nothing todo with parallelism and arguably little to do with concurrency, coroutines need to deal with context-switchs and and other context-management operations. Therefore, this proposal includes coroutines both as an intermediate step for the implementation of threads, and a first class feature of \CFA. Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant. The core API of coroutines revolve around two features: independent call stacks and \code{suspend}/\code{resume}. Here is an example of a solution to the fibonnaci problem using \CFA coroutines: @@ -26,4 +25,5 @@ } + // main automacically called on first resume void main(Fibonacci* this) { int fn1, fn2; // retained between resumes @@ -59,9 +59,9 @@ \subsection{Construction} -One important design challenge for coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run some code after the user-constructor runs. In the case of the coroutines this challenge is simpler since there is no loss of determinism brough by preemption or scheduling, however, the underlying challenge remains the same for coroutines and threads. - -The runtime system needs to create the coroutine's stack and more importantly prepare it for the first resumption. The timing of the creation is non trivial since users both expect to have fully constructed objects once execution enters the coroutine main and to be able to resume the coroutine from the constructor (Obviously we only solve cases where these two statements don't conflict). There are several solutions to this problem but the chosen options effectively forces the design of the coroutine. - -Furthermore, \CFA faces an extra challenge which is that polymorphique routines rely on invisible thunks when casted to non-polymorphic routines and these thunks have function scope. For example, the following code, while looking benign, can run into undefined behaviour because of thunks: +One important design challenge for coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs. In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling. However, the underlying challenge remains the same for coroutines and threads. + +The runtime system needs to create the coroutine's stack and more importantly prepare it for the first resumption. The timing of the creation is non-trivial since users both expect to have fully constructed objects once execution enters the coroutine main and to be able to resume the coroutine from the constructor. Like for regular objects, constructors can still leak coroutines before they are ready. There are several solutions to this problem but the chosen options effectively forces the design of the coroutine. + +Furthermore, \CFA faces an extra challenge as polymorphic routines create invisible thunks when casted to non-polymorphic routines and these thunks have function scope. For example, the following code, while looking benign, can run into undefined behaviour because of thunks: \begin{cfacode} @@ -78,5 +78,5 @@ } \end{cfacode} -Indeed, the generated C code\footnote{Code trimmed down for brevity} shows that a local thunk is created in order to hold type information: +The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information: \begin{ccode} @@ -95,13 +95,13 @@ } \end{ccode} -The problem in the this example is that there is a race condition between the start of the execution of \code{noop} on the other thread and the stack frame of \code{bar} being destroyed. This extra challenge limits which solutions are viable because storing the function pointer for too long only increases the chances that the race will end in undefined behavior; i.e. the stack based thunk being destroyed before it was used. +The problem in this example is a race condition between the start of the execution of \code{noop} on the other thread and the stack frame of \code{bar} being destroyed. This extra challenge limits which solutions are viable because storing the function pointer for too long only increases the chances that the race will end in undefined behavior; i.e. the stack based thunk being destroyed before it was used. This challenge is an extension of challenges that come with second-class routines. Indeed, GCC nested routines also have the limitation that the routines cannot be passed outside of the scope of the functions these were declared in. The case of coroutines and threads is simply an extension of this problem to multiple call-stacks. \subsection{Alternative: Composition} -One solution to this challenge would be to use inheritence, +One solution to this challenge would be to use composition/containement, \begin{cfacode} struct Fibonacci { int fn; // used for communication - coroutine c; + coroutine c; //composition }; @@ -111,6 +111,5 @@ } \end{cfacode} - -There are two downsides to this approach. The first, which is relatively minor, is that the base class needs to be made aware of the main routine pointer, regardless of whether we use a parameter or a virtual pointer, this means the coroutine data must be made larger to store a value that is actually a compile time constant (The address of the main routine). The second problem which is both subtle but significant, is that now users can get the initialisation order of there coroutines wrong. Indeed, every field of a \CFA struct will be constructed but in the order of declaration, unless users explicitly write otherwise. This means that users who forget to initialize a the coroutine at the right time may resume the coroutine with an uninitilized object. For coroutines, this is unlikely to be a problem, for threads however, this is a significant problem. +There are two downsides to this approach. The first, which is relatively minor, is that the base class needs to be made aware of the main routine pointer, regardless of whether a parameter or a virtual pointer is used, this means the coroutine data must be made larger to store a value that is actually a compile time constant (address of the main routine). The second problem, which is both subtle and significant, is that now users can get the initialisation order of there coroutines wrong. Indeed, every field of a \CFA struct is constructed but in declaration order, unless users explicitly write otherwise. This semantics means that users who forget to initialize a the coroutine may resume the coroutine with an uninitilized object. For coroutines, this is unlikely to be a problem, for threads however, this is a significant problem. \subsection{Alternative: Reserved keyword} @@ -122,5 +121,4 @@ }; \end{cfacode} - This mean the compiler can solve problems by injecting code where needed. The downside of this approach is that it makes coroutine a special case in the language. Users who would want to extend coroutines or build their own for various reasons can only do so in ways offered by the language. Furthermore, implementing coroutines without language supports also displays the power of \CFA. While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can both be constructed by users without using the language support. The reserved keywords are only present to improve ease of use for the common cases. @@ -128,9 +126,31 @@ \subsection{Alternative: Lamda Objects} -For coroutines as for threads, many implementations are based on routine pointers or function objects\cit. For example, Boost implements coroutines in terms of four functor object types \code{asymmetric_coroutine<>::pull_type}, \code{asymmetric_coroutine<>::push_type}, \code{symmetric_coroutine<>::call_type}, \code{symmetric_coroutine<>::yield_type}. Often, the canonical threading paradigm in languages is based on function pointers, pthread being one of the most well known example. The main problem of these approach is that the thread usage is limited to a generic handle that must otherwise be wrapped in a custom type. Since the custom type is simple to write and \CFA and solves several issues, added support for routine/lambda based coroutines adds very little. - -\subsection{Trait based coroutines} - -Finally the underlying approach, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines. This approach defines a coroutine as \say{anything that \say{satisfies the trait \code{is_coroutine} and is used as a coroutine} is a coroutine}. +For coroutines as for threads, many implementations are based on routine pointers or function objects\cit. For example, Boost implements coroutines in terms of four functor object types: +\begin{cfacode} +asymmetric_coroutine<>::pull_type +asymmetric_coroutine<>::push_type +symmetric_coroutine<>::call_type +symmetric_coroutine<>::yield_type +\end{cfacode} +Often, the canonical threading paradigm in languages is based on function pointers, pthread being one of the most well known examples. The main problem of this approach is that the thread usage is limited to a generic handle that must otherwise be wrapped in a custom type. Since the custom type is simple to write in \CFA and solves several issues, added support for routine/lambda based coroutines adds very little. + +A variation of this would be to use an simple function pointer in the same way pthread does for threads : +\begin{cfacode} +void foo( coroutine_t cid, void * arg ) { + int * value = (int *)arg; + //Coroutine body +} + +int main() { + int value = 0; + coroutine_t cid = coroutine_create( &foo, (void*)&value ); + coroutine_resume( &cid ); +} +\end{cfacode} +This semantic is more common for thread interfaces than coroutines but would work equally well. As discussed in section \ref{threads}, this approach is superseeded by static approaches in terms of expressivity. + +\subsection{Alternative: Trait-based coroutines} + +Finally the underlying approach, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines. This approach defines a coroutine as anything that satisfies the trait \code{is_coroutine} and is used as a coroutine is a coroutine. \begin{cfacode} @@ -140,10 +160,34 @@ }; \end{cfacode} - -This entails that an object is not a coroutine until \code{resume} (or \code{prime}) is called on the object. Correspondingly, any object that is passed to \code{resume} is a coroutine since it must satisfy the \code{is_coroutine} trait to compile. The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory foot print of a coroutine is trivial when implementing the \code{get_coroutine} routine. The \CFA keyword \code{coroutine} only has the effect of implementing the getter and forward declarations required for users to only have to implement the main routine. +This ensures an object is not a coroutine until \code{resume} (or \code{prime}) is called on the object. Correspondingly, any object that is passed to \code{resume} is a coroutine since it must satisfy the \code{is_coroutine} trait to compile. The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory foot print of a coroutine is trivial when implementing the \code{get_coroutine} routine. The \CFA keyword \code{coroutine} only has the effect of implementing the getter and forward declarations required for users to only have to implement the main routine. + +\begin{center} +\begin{tabular}{c c c} +\begin{cfacode}[tabsize=3] +coroutine MyCoroutine { + int someValue; +}; +\end{cfacode} & == & \begin{cfacode}[tabsize=3] +struct MyCoroutine { + int someValue; + coroutine_desc __cor; +}; + +static inline +coroutine_desc * get_coroutine( + struct MyCoroutine * this +) { + return &this->__cor; +} + +void main(struct MyCoroutine * this); +\end{cfacode} +\end{tabular} +\end{center} + \section{Thread Interface}\label{threads} -The basic building blocks of multi-threading in \CFA are \glspl{cfathread}. By default these are implemented as \glspl{uthread}, and as such, offer a flexible and lightweight threading interface (lightweight compared to \glspl{kthread}). A thread can be declared using a SUE declaration \code{thread} as follows: +The basic building blocks of multi-threading in \CFA are \glspl{cfathread}. Both use and kernel threads are supported, where user threads are the concurrency mechanism and kernel threads are the parallel mechanism. User threads offer a flexible and lightweight interface. A thread can be declared using a struct declaration \code{thread} as follows: \begin{cfacode} @@ -151,5 +195,5 @@ \end{cfacode} -Like for coroutines, the keyword is a thin wrapper arount a \CFA trait: +As for coroutines, the keyword is a thin wrapper arount a \CFA trait: \begin{cfacode} @@ -170,5 +214,5 @@ \end{cfacode} -In this example, threads of type \code{foo} will start there execution in the \code{void main(foo*)} routine which in this case prints \code{"Hello World!"}. While this proposoal encourages this approach which enforces strongly type programming, users may prefer to use the routine based thread semantics for the sake of simplicity. With these semantics it is trivial to write a thread type that takes a function pointer as parameter and executes it on its stack asynchronously +In this example, threads of type \code{foo} start execution in the \code{void main(foo*)} routine which prints \code{"Hello World!"}. While this proposoal encourages this approach to enforce strongly-typed programming, users may prefer to use the routine based thread semantics for the sake of simplicity. With these semantics it is trivial to write a thread type that takes a function pointer as parameter and executes it on its stack asynchronously \begin{cfacode} typedef void (*voidFunc)(void); @@ -201,7 +245,7 @@ void main() { World w; - //Thread run forks here - - //Printing "Hello " and "World!" will be run concurrently + //Thread forks here + + //Printing "Hello " and "World!" are run concurrently sout | "Hello " | endl; @@ -210,5 +254,27 @@ \end{cfacode} -This semantic has several advantages over explicit semantics typesafety is guaranteed, a thread is always started and stopped exaclty once and users cannot make any progamming errors. However, one of the apparent drawbacks of this system is that threads now always form a lattice, that is they are always destroyed in opposite order of construction. While this seems like a significant limitation, existing \CFA semantics can solve this problem. Indeed, using dynamic allocation to create threads will naturally let threads outlive the scope in which the thread was created much like dynamically allocating memory will let objects outlive the scope in which thy were created +This semantic has several advantages over explicit semantics typesafety is guaranteed, a thread is always started and stopped exaclty once and users cannot make any progamming errors. Another advantage of this semantic is that it naturally scale to multiple threads meaning basic synchronisation is very simple + +\begin{cfacode} + thread MyThread { + //... + }; + + //main + void main(MyThread* this) { + //... + } + + void foo() { + MyThread thrds[10]; + //Start 10 threads at the beginning of the scope + + DoStuff(); + + //Wait for the 10 threads to finish + } +\end{cfacode} + +However, one of the apparent drawbacks of this system is that threads now always form a lattice, that is they are always destroyed in opposite order of construction because of block structure. However, storage allocation os not limited to blocks; dynamic allocation can create threads that outlive the scope in which the thread is created much like dynamically allocating memory lets objects outlive the scope in which they are created \begin{cfacode} @@ -241,24 +307,2 @@ } \end{cfacode} - -Another advantage of this semantic is that it naturally scale to multiple threads meaning basic synchronisation is very simple - -\begin{cfacode} - thread MyThread { - //... - }; - - //main - void main(MyThread* this) { - //... - } - - void foo() { - MyThread thrds[10]; - //Start 10 threads at the beginning of the scope - - DoStuff(); - - //Wait for the 10 threads to finish - } -\end{cfacode} Index: doc/proposals/concurrency/text/cforall.tex =================================================================== --- doc/proposals/concurrency/text/cforall.tex (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) +++ doc/proposals/concurrency/text/cforall.tex (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -0,0 +1,5 @@ +% ====================================================================== +% ====================================================================== +\chapter{Cforall crash course} +% ====================================================================== +% ====================================================================== Index: doc/proposals/concurrency/text/concurrency.tex =================================================================== --- doc/proposals/concurrency/text/concurrency.tex (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ doc/proposals/concurrency/text/concurrency.tex (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -4,14 +4,20 @@ % ====================================================================== % ====================================================================== -Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. This distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account. Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At a lower level, non-concurrent paradigms are often implemented as locks and atomic operations. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}. An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to add such a paradigm to a language like C or \CC\cit, which is why it was rejected as the core paradigm for concurrency in \CFA. One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared memory systems, is the \emph{monitor}. Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}. Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs. In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors. For these reasons, this project proposes monitors as the core concurrency-construct. +Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account. + +Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}. + +An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA. + +One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared memory systems, is the \emph{monitor}. Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}. Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs. In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors. For these reasons, this project proposes monitors as the core concurrency-construct. \section{Basics} -The basic features that concurrency tools neet to offer is support for mutual-exclusion and synchronisation. Mutual-exclusion is the concept that only a fixed number of threads can access a critical section at any given time, where a critical section is the group of instructions on an associated portion of data that requires the limited access. On the other hand, synchronization enforces relative ordering of execution and synchronization tools are used to guarantee that event \textit{X} always happens before \textit{Y}. +Non-determinism requires concurrent systems to offer support for mutual-exclusion and synchronisation. Mutual-exclusion is the concept that only a fixed number of threads can access a critical section at any given time, where a critical section is a group of instructions on an associated portion of data that requires the restricted access. On the other hand, synchronization enforces relative ordering of execution and synchronization tools numerous mechanisms to establish timing relationships among threads. \subsection{Mutual-Exclusion} -As mentionned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once. However, many solution exists for mutual exclusion which vary in terms of performance, flexibility and ease of use. Methods range from low level locks, which are fast and flexible but require significant attention to be correct, to higher level mutual-exclusion methods, which sacrifice some performance in order to improve ease of use. Often by either guaranteeing some problems cannot occur (e.g. being deadlock free) or by offering a more explicit coupling between data and corresponding critical section. For example, the \CC \code{std::atomic} which offer an easy way to express mutual-exclusion on a restricted set of features (.e.g: reading/writing large types atomically). Another challenge with low level locks is composability. Locks are said to not be composable because it takes careful organising for multiple locks to be used and once while preventing deadlocks. Easing composability is another feature higher-level mutual-exclusion mechanisms often offer. +As mentionned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once. However, many solution exists for mutual exclusion which vary in terms of performance, flexibility and ease of use. Methods range from low-level locks, which are fast and flexible but require significant attention to be correct, to higher-level mutual-exclusion methods, which sacrifice some performance in order to improve ease of use. Ease of use comes by either guaranteeing some problems cannot occur (e.g., being deadlock free) or by offering a more explicit coupling between data and corresponding critical section. For example, the \CC \code{std::atomic} which offer an easy way to express mutual-exclusion on a restricted set of operations (.e.g: reading/writing large types atomically). Another challenge with low-level locks is composability. Locks are not composable because it takes careful organising for multiple locks to be used while preventing deadlocks. Easing composability is another feature higher-level mutual-exclusion mechanisms often offer. \subsection{Synchronization} -As for mutual-exclusion, low level synchronisation primitive often offer great performance and good flexibility at the cost of ease of use. Again, higher-level mechanism often simplify usage by adding better coupling between synchronization and data, for example message passing, or offering simple solution to otherwise involved challenges. An example of this is barging. As mentionned above synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}. Most of the time synchronisation happens around a critical section, where threads most acquire said critical section in a certain order. However, it may also be desired to be able to guarantee that event \textit{Z} does not occur between \textit{X} and \textit{Y}. This is called barging, where event \textit{X} tries to effect event \textit{Y} but anoter thread races to grab the critical section and emits \textit{Z} before \textit{Y}. Preventing or detecting barging is an involved challenge with low-level locks, which can be made much easier by higher-level constructs. +As for mutual-exclusion, low level synchronisation primitive often offer good performance and good flexibility at the cost of ease of use. Again, higher-level mechanism often simplify usage by adding better coupling between synchronization and data, .eg., message passing, or offering simple solution to otherwise involved challenges. An example of this is barging. As mentionned above synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}. Most of the time synchronisation happens around a critical section, where threads most acquire said critical section in a certain order. However, it may also be desired to be able to guarantee that event \textit{Z} does not occur between \textit{X} and \textit{Y}. This is called barging, where event \textit{X} tries to effect event \textit{Y} but anoter thread races to grab the critical section and emits \textit{Z} before \textit{Y}. Preventing or detecting barging is an involved challenge with low-level locks, which can be made much easier by higher-level constructs. % ====================================================================== @@ -20,5 +26,5 @@ % ====================================================================== % ====================================================================== -A monitor is a set of routines that ensure mutual exclusion when accessing shared state. This concept is generally associated with Object-Oriented Languages like Java~\cite{Java} or \uC~\cite{uC++book} but does not strictly require OOP semantics. The only requirements is the ability to declare a handle to a shared object and a set of routines that act on it : +A monitor is a set of routines that ensure mutual exclusion when accessing shared state. This concept is generally associated with Object-Oriented Languages like Java~\cite{Java} or \uC~\cite{uC++book} but does not strictly require OO semantics. The only requirements is the ability to declare a handle to a shared object and a set of routines that act on it : \begin{cfacode} typedef /*some monitor type*/ monitor; @@ -36,7 +42,7 @@ % ====================================================================== % ====================================================================== -The above monitor example displays some of the intrinsic characteristics. Indeed, it is necessary to use pass-by-reference over pass-by-value for monitor routines. This semantics is important because at their core, monitors are implicit mutual-exclusion objects (locks), and these objects cannot be copied. Therefore, monitors are implicitly non-copyable. - -Another aspect to consider is when a monitor acquires its mutual exclusion. For example, a monitor may need to be passed through multiple helper routines that do not acquire the monitor mutual-exclusion on entry. Pass through can be both generic helper routines (\code{swap}, \code{sort}, etc.) or specific helper routines like the following to implement an atomic counter : +The above monitor example displays some of the intrinsic characteristics. First, it is necessary to use pass-by-reference over pass-by-value for monitor routines. This semantics is important because at their core, monitors are implicit mutual-exclusion objects (locks), and these objects cannot be copied. Therefore, monitors are implicitly non-copyable objects. + +Another aspect to consider is when a monitor acquires its mutual exclusion. For example, a monitor may need to be passed through multiple helper routines that do not acquire the monitor mutual-exclusion on entry. Pass through can occur for generic helper routines (\code{swap}, \code{sort}, etc.) or specific helper routines like the following to implement an atomic counter : \begin{cfacode} @@ -46,5 +52,5 @@ size_t ++?(counter_t & mutex this); //increment - //need for mutex is platform dependent here + //need for mutex is platform dependent void ?{}(size_t * this, counter_t & mutex cnt); //conversion \end{cfacode} @@ -52,5 +58,5 @@ Here, the constructor(\code{?\{\}}) uses the \code{nomutex} keyword to signify that it does not acquire the monitor mutual-exclusion when constructing. This semantics is because an object not yet constructed should never be shared and therefore does not require mutual exclusion. The prefix increment operator uses \code{mutex} to protect the incrementing process from race conditions. Finally, there is a conversion operator from \code{counter_t} to \code{size_t}. This conversion may or may not require the \code{mutex} keyword depending on whether or not reading an \code{size_t} is an atomic operation. -Having both \code{mutex} and \code{nomutex} keywords could be argued to be redundant based on the meaning of a routine having neither of these keywords. For example, given a routine without qualifiers \code{void foo(counter_t & this)} then it is reasonable that it should default to the safest option \code{mutex}. On the other hand, the option of having routine \code{void foo(counter_t & this)} mean \code{nomutex} is unsafe by default and may easily cause subtle errors. In fact \code{nomutex} is the "normal" parameter behaviour, with the \code{nomutex} keyword effectively stating explicitly that "this routine is not special". Another alternative is to make having exactly one of these keywords mandatory, which would provide the same semantics but without the ambiguity of supporting routines neither keyword. Mandatory keywords would also have the added benefit of being self-documented but at the cost of extra typing. While there are several benefits to mandatory keywords, they do bring a few challenges. Mandatory keywords in \CFA would imply that the compiler must know without a doubt wheter or not a parameter is a monitor or not. Since \CFA relies heavily on traits as an abstraction mechanism, the distinction between a type that is a monitor and a type that looks like a monitor can become blurred. For this reason, \CFA only has the \code{mutex} keyword. +Having both \code{mutex} and \code{nomutex} keywords is redundant based on the meaning of a routine having neither of these keywords. For example, given a routine without qualifiers \code{void foo(counter_t & this)}, then it is reasonable that it should default to the safest option \code{mutex}, whereas assuming \code{nomutex} is unsafe and may cause subtle errors. In fact, \code{nomutex} is the "normal" parameter behaviour, with the \code{nomutex} keyword effectively stating explicitly that "this routine is not special". Another alternative is to make having exactly one of these keywords mandatory, which would provide the same semantics but without the ambiguity of supporting routines neither keyword. Mandatory keywords would also have the added benefit of being self-documented but at the cost of extra typing. While there are several benefits to mandatory keywords, they do bring a few challenges. Mandatory keywords in \CFA would imply that the compiler must know without a doubt wheter or not a parameter is a monitor or not. Since \CFA relies heavily on traits as an abstraction mechanism, the distinction between a type that is a monitor and a type that looks like a monitor can become blurred. For this reason, \CFA only has the \code{mutex} keyword. @@ -60,5 +66,5 @@ int f2(const monitor & mutex m); int f3(monitor ** mutex m); -int f4(monitor *[] mutex m); +int f4(monitor * mutex m []); int f5(graph(monitor*) & mutex m); \end{cfacode} @@ -68,7 +74,7 @@ int f1(monitor & mutex m); //Okay : recommanded case int f2(monitor * mutex m); //Okay : could be an array but probably not -int f3(monitor [] mutex m); //Not Okay : Array of unkown length +int f3(monitor mutex m []); //Not Okay : Array of unkown length int f4(monitor ** mutex m); //Not Okay : Could be an array -int f5(monitor *[] mutex m); //Not Okay : Array of unkown length +int f5(monitor * mutex m []); //Not Okay : Array of unkown length \end{cfacode} Index: doc/proposals/concurrency/text/intro.tex =================================================================== --- doc/proposals/concurrency/text/intro.tex (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ doc/proposals/concurrency/text/intro.tex (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -3,5 +3,5 @@ % ====================================================================== -This proposal provides a minimal concurrency API that is simple, efficient and can be reused to build higher-level features. The simplest possible concurrency core is a thread and a lock but this low-level approach is hard to master. An easier approach for users is to support higher-level constructs as the basis of the concurrency in \CFA. Indeed, for highly productive parallel programming, high-level approaches are much more popular~\cite{HPP:Study}. Examples are task based, message passing and implicit threading. +This proposal provides a minimal concurrency API that is simple, efficient and can be reused to build higher-level features. The simplest possible concurrency system is a thread and a lock but this low-level approach is hard to master. An easier approach for users is to support higher-level constructs as the basis of the concurrency, in \CFA. Indeed, for highly productive parallel programming, high-level approaches are much more popular~\cite{HPP:Study}. Examples are task based, message passing and implicit threading. Therefore a high-level approach is adapted in \CFA -There are actually two problems that need to be solved in the design of concurrency for a programming language: which concurrency tools are available to the users and which parallelism tools are available. While these two concepts are often seen together, they are in fact distinct concepts that require different sorts of tools~\cite{Buhr05a}. Concurrency tools need to handle mutual exclusion and synchronization, while parallelism tools are about performance, cost and resource utilization. +There are actually two problems that need to be solved in the design of concurrency for a programming language: which concurrency and which parallelism tools are available to the users. While these two concepts are often combined, they are in fact distinct concepts that require different tools~\cite{Buhr05a}. Concurrency tools need to handle mutual exclusion and synchronization, while parallelism tools are about performance, cost and resource utilization. Index: doc/proposals/concurrency/thesis.tex =================================================================== --- doc/proposals/concurrency/thesis.tex (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ doc/proposals/concurrency/thesis.tex (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -77,5 +77,5 @@ \fancyhf{} \cfoot{\thepage} -\rfoot{v\input{build/version}} +\rfoot{v\input{version}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -94,4 +94,6 @@ \input{intro} + +\input{cforall} \input{basics} Index: doc/proposals/concurrency/version =================================================================== --- doc/proposals/concurrency/version (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) +++ doc/proposals/concurrency/version (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -0,0 +1,1 @@ +0.9.119 Index: doc/proposals/tagged-struct.txt =================================================================== --- doc/proposals/tagged-struct.txt (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) +++ doc/proposals/tagged-struct.txt (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -0,0 +1,85 @@ +Proposal to add simple inhieritance to the language. + +Tagged structures allow for dynamic casting between types in a hierarchy. +Children (rather pointers to) can be up-cast to their parents, a safe +conversion that may recive language level support or even be implicit. +Parents can be down cast to their children, which might fail if the underlying +object is not of the child type, or a child of that. + +This does not however cause dynamic look-up. During function calls the +underlying type is ignored, and the pointer type is used to type match the +function call. + +Tags cannot be used on unions. This is because the different sides interact +with the casts rather badly. There is a similarity with tagged unions still. +Tagged structures also carry data to identify which out of several +possibilies the object actually is. Although the possibilies are dynamic in +this case. + + +Syntax: + +"struct" name [ "tagged" [ parent-name ] ] "{" fields "}" + +The keywords can change (although they currently reflect the concept name +closely). More formally, in terms of grammar this adds: + +struct-or-union-specifier + ... + struct identifier tagged { struct-declaration-list } + struct identifier tagged parent-identifier { struct-declaration-list } + +"tagged" by itself create a tagged structure that is the root of a new tree. +It has no parent tagged structure. If "tagged" is used with a parent than +that is the parent of this node. + +Tagged structures have fields beyond the ones listed. Root tags have a type +field added which give the type of the instance. Child tags prepend all of +their parent's fields to their field list so they can be upcast. + + +Implemenation: + +Adding to the field list is a simple matter, should be doable during +translation. The type field is just a pointer to a type object. With proper +linking we can create a single unique instance of the type object for each +declared tagged struct. The instance's address is used as an id for the type. +It also holds data about the type, such as its parent's id/a pointer to the +parent type object. + +If the type field is given a simple name, then the user can easily access the +type object. This might be useful depending on what sort of data is in the +type object, especially if the data can be added to by the user in some way. +Ironically one way to accomplish that is to make the type objects tagged +themselves, but that recursion might not have a base case. + +If the name is mangled and direct access to type objects is still wanted, then +a function could be used to access the type object. Say get_type or get_tag +instead of type or tag. + +If the data on the type object is set, than providing direct access may be +unnessary. Instead the libraries or base code might be able to implement +everything the data is for. + + +Traits: + +[is_]tagged[_struct](dtype T) +True if the given T is a tagged struct of some kind. This promises that it has +a type object, but nothing else. + +[is_]tagged_under(dtype parent, dtype child) +True if child is a child type of parent. Requires that both are tagged structs +and that child can upcast to parent. + + +Functions: + +forall(dtype T | is_tagged(T), dtype U | is_tagged(U)) +T * dynamic_cast(U * value) +The cast function, that safely converts the U* into a T*, returning null if +the underlying object value points to is not a child type of T. A shorter name +might be perfered. The runtime should be no more than linear with the depth +of U in the inhiertance tree. + +bug#11 might require `bool dynamic_cast(T ** dst, U * src)` instead. Index: doc/working/exception/impl/except.c =================================================================== --- doc/working/exception/impl/except.c (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ (revision ) @@ -1,229 +1,0 @@ -#include -#include -#include - -#include "lsda.h" - -// This macro should be the only thing that needs to change across machines. -// struct _Unwind_Context * -> _Unwind_Reason_Code(*)() -#define MATCHER_FROM_CONTEXT(ptr_to_context) \ - (*(_Unwind_Reason_Code(**)())(_Unwind_GetCFA(ptr_to_context) + 8)) - - -//Global which defines the current exception -//Currently an int just to make matching easier -int this_exception; - -//This is our personality routine -//For every stack frame anotated with ".cfi_personality 0x3,__gcfa_personality_v0" -//This function will be called twice when unwinding -//Once in the search phased and once in the cleanup phase -_Unwind_Reason_Code __gcfa_personality_v0 ( - int version, _Unwind_Action actions, unsigned long long exceptionClass, - struct _Unwind_Exception* unwind_exception, struct _Unwind_Context* context) -{ - printf("CFA: 0x%lx\n", _Unwind_GetCFA(context)); - - //DEBUG - printf("Personality function (%d, %x, %llu, %p, %p):", version, actions, exceptionClass, unwind_exception, context); - - //If we've reached the end of the stack then there is nothing much we can do... - if( actions & _UA_END_OF_STACK ) return _URC_END_OF_STACK; - - //DEBUG - if (actions & _UA_SEARCH_PHASE) { - printf(" lookup phase"); - } - //DEBUG - else if (actions & _UA_CLEANUP_PHASE) { - printf(" cleanup phase"); - } - //Just in case, probably can't actually happen - else { - printf(" error\n"); - return _URC_FATAL_PHASE1_ERROR; - } - - //Get a pointer to the language specific data from which we will read what we need - const unsigned char * lsd = (const unsigned char*) _Unwind_GetLanguageSpecificData( context ); - - if( !lsd ) { //Nothing to do, keep unwinding - printf(" no LSD"); - goto UNWIND; - } - - //Get the instuction pointer and a reading pointer into the exception table - lsda_header_info lsd_info; - const unsigned char * cur_ptr = parse_lsda_header( context, lsd, &lsd_info); - _Unwind_Ptr instruction_ptr = _Unwind_GetIP( context ); - - //Linearly search the table for stuff to do - while( cur_ptr < lsd_info.action_table ) { - _Unwind_Ptr callsite_start; - _Unwind_Ptr callsite_len; - _Unwind_Ptr callsite_landing_pad; - _uleb128_t callsite_action; - - //Decode the common stuff we have in here - cur_ptr = read_encoded_value (0, lsd_info.call_site_encoding, cur_ptr, &callsite_start); - cur_ptr = read_encoded_value (0, lsd_info.call_site_encoding, cur_ptr, &callsite_len); - cur_ptr = read_encoded_value (0, lsd_info.call_site_encoding, cur_ptr, &callsite_landing_pad); - cur_ptr = read_uleb128 (cur_ptr, &callsite_action); - - //Have we reach the correct frame info yet? - if( lsd_info.Start + callsite_start + callsite_len < instruction_ptr ) { - //DEBUG BEGIN - void * ls = (void*)lsd_info.Start; - void * cs = (void*)callsite_start; - void * cl = (void*)callsite_len; - void * bp = (void*)lsd_info.Start + callsite_start; - void * ep = (void*)lsd_info.Start + callsite_start + callsite_len; - void * ip = (void*)instruction_ptr; - printf("\nfound %p - %p (%p, %p, %p), looking for %p\n", bp, ep, ls, cs, cl, ip); - //DEBUG END - continue; - } - - //Have we gone too far - if( lsd_info.Start + callsite_start > instruction_ptr ) { - printf(" gone too far"); - break; - } - - //Something to do? - if( callsite_landing_pad ) { - //Which phase are we in - if (actions & _UA_SEARCH_PHASE) { - //Search phase, this means we probably found a potential handler and must check if it is a match - - //If we have arbitrarily decided that 0 means nothing to do and 1 means there is a potential handler - //This doesn't seem to conflict the gcc default behavior - if (callsite_action != 0) { - //Now we want to run some code to see if the handler matches - //This is the tricky part where we want to the power to run arbitrary code - //However, generating a new exception table entry and try routine every time - //is way more expansive than we might like - //The information we have is : - // - The GR (Series of registers) - // GR1=GP Global Pointer of frame ref by context - // - The instruction pointer - // - The instruction pointer info (???) - // - The CFA (Canonical Frame Address) - // - The BSP (Probably the base stack pointer) - - - //The current apprach uses one exception table entry per try block - _uleb128_t imatcher; - //Get the relative offset to the - cur_ptr = read_uleb128 (cur_ptr, &imatcher); - - //Get a function pointer from the relative offset and call it - // _Unwind_Reason_Code (*matcher)() = (_Unwind_Reason_Code (*)())lsd_info.LPStart + imatcher; - - _Unwind_Reason_Code (*matcher)() = - MATCHER_FROM_CONTEXT(context); - _Unwind_Reason_Code ret = matcher(); - - //Based on the return value, check if we matched the exception - if( ret == _URC_HANDLER_FOUND) printf(" handler found\n"); - else printf(" no handler\n"); - return ret; - } - - //This is only a cleanup handler, ignore it - printf(" no action"); - } - else if (actions & _UA_CLEANUP_PHASE) { - - if( (callsite_action != 0) && !(actions & _UA_HANDLER_FRAME) ){ - //If this is a potential exception handler - //but not the one that matched the exception in the seach phase, - //just ignore it - goto UNWIND; - } - - //We need to run some clean-up or a handler - //These statment do the right thing but I don't know any specifics at all - _Unwind_SetGR( context, __builtin_eh_return_data_regno(0), (_Unwind_Ptr) unwind_exception ); - _Unwind_SetGR( context, __builtin_eh_return_data_regno(1), 0 ); - - //I assume this sets the instruction pointer to the adress of the landing pad - //It doesn't actually set it, it only state the value that needs to be set once we return _URC_INSTALL_CONTEXT - _Unwind_SetIP( context, lsd_info.LPStart + callsite_landing_pad ); - - //DEBUG - printf(" action\n"); - - //Return have some action to run - return _URC_INSTALL_CONTEXT; - } - } - - //Nothing to do, move along - printf(" no landing pad"); - } - //No handling found - printf(" table end reached\n"); - - //DEBUG - UNWIND: - printf(" unwind\n"); - - //Keep unwinding the stack - return _URC_CONTINUE_UNWIND; -} - -//We need a piece of storage to raise the exception -struct _Unwind_Exception this_exception_storage; - -//Function needed by force unwind -//It basically says to unwind the whole stack and then exit when we reach the end of the stack -static _Unwind_Reason_Code _Stop_Fn( - int version, - _Unwind_Action actions, - _Unwind_Exception_Class exceptionClass, - struct _Unwind_Exception * unwind_exception, - struct _Unwind_Context * context, - void * some_param -) { - if( actions & _UA_END_OF_STACK ) exit(1); - if( actions & _UA_CLEANUP_PHASE ) return _URC_NO_REASON; - - return _URC_FATAL_PHASE2_ERROR; -} - -//Example throw routine -void throw( int val ) { - //Store the current exception - this_exception = val; - - //DEBUG - printf("Throwing exception %d\n", this_exception); - - //Call stdlibc to raise the exception - _Unwind_Reason_Code ret = _Unwind_RaiseException( &this_exception_storage ); - - //If we reach here it means something happened - //For resumption to work we need to find a way to return back to here - //Most of them will probably boil down to setting a global flag and making the phase 1 either stop or fail. - //Causing an error on purpose may help avoiding unnecessary work but it might have some weird side effects. - //If we just pretend no handler was found that would work but may be expensive for no reason since we will always - //search the whole stack - - if( ret == _URC_END_OF_STACK ) { - //No proper handler was found - //This can be handled in several way - //C++ calls std::terminate - //Here we force unwind the stack, basically raising a cancellation - printf("Uncaught exception %p\n", &this_exception_storage); - - ret = _Unwind_ForcedUnwind( &this_exception_storage, _Stop_Fn, (void*)0x22 ); - printf("UNWIND ERROR %d after force unwind\n", ret); - abort(); - } - - //We did not simply reach the end of the stack without finding a handler, - //Something wen't wrong - printf("UNWIND ERROR %d after raise exception\n", ret); - abort(); -} Index: doc/working/exception/impl/except.h =================================================================== --- doc/working/exception/impl/except.h (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ (revision ) @@ -1,3 +1,0 @@ -#include - -void throw( int val ); Index: doc/working/exception/impl/exception.c =================================================================== --- doc/working/exception/impl/exception.c (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) +++ doc/working/exception/impl/exception.c (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -0,0 +1,357 @@ +#include "exception.h" + +// Implementation of the secret header. + +#include +#include +#include + +#include "lsda.h" + +struct shared_stack_t shared_stack; + + +// This macro should be the only thing that needs to change across machines. +// Used in the personality function, way down in termination. +// struct _Unwind_Context * -> _Unwind_Reason_Code(*)() +#define MATCHER_FROM_CONTEXT(ptr_to_context) \ + (*(_Unwind_Reason_Code(**)())(_Unwind_GetCFA(ptr_to_context) + 8)) + + +// RESUMPTION ================================================================ + +void __throw_resume(exception except) { + + // DEBUG + printf("Throwing resumption exception %d\n", except); + + struct __try_resume_node * original_head = shared_stack.current_resume; + struct __try_resume_node * current = + (original_head) ? original_head->next : shared_stack.top_resume; + + for ( ; current ; current = current->next) { + shared_stack.current_resume = current; + if (current->try_to_handle(except)) { + shared_stack.current_resume = original_head; + return; + } + } + + printf("Unhandled exception %d\n", except); + shared_stack.current_resume = original_head; + + // Fall back to termination: + __throw_terminate(except); + // TODO: Default handler for resumption. +} + + +// TERMINATION =============================================================== + +// Requires -fexceptions to work. + +// Global which defines the current exception +// Currently an int just to make matching easier +//int this_exception; (became shared_stack.current_exception) + +// We need a piece of storage to raise the exception +struct _Unwind_Exception this_exception_storage; + +// Function needed by force unwind +// It basically says to unwind the whole stack and then exit when we reach the end of the stack +static _Unwind_Reason_Code _Stop_Fn( + int version, + _Unwind_Action actions, + _Unwind_Exception_Class exceptionClass, + struct _Unwind_Exception * unwind_exception, + struct _Unwind_Context * context, + void * some_param) { + if( actions & _UA_END_OF_STACK ) exit(1); + if( actions & _UA_CLEANUP_PHASE ) return _URC_NO_REASON; + + return _URC_FATAL_PHASE2_ERROR; +} + +void __throw_terminate( int val ) { + // Store the current exception + shared_stack.current_exception = val; + + // DEBUG + printf("Throwing termination exception %d\n", val); + + // Call stdlibc to raise the exception + _Unwind_Reason_Code ret = _Unwind_RaiseException( &this_exception_storage ); + + // If we reach here it means something happened + // For resumption to work we need to find a way to return back to here + // Most of them will probably boil down to setting a global flag and making the phase 1 either stop or fail. + // Causing an error on purpose may help avoiding unnecessary work but it might have some weird side effects. + // If we just pretend no handler was found that would work but may be expensive for no reason since we will always + // search the whole stack + + if( ret == _URC_END_OF_STACK ) { + // No proper handler was found + // This can be handled in several way + // C++ calls std::terminate + // Here we force unwind the stack, basically raising a cancellation + printf("Uncaught exception %p\n", &this_exception_storage); + + ret = _Unwind_ForcedUnwind( &this_exception_storage, _Stop_Fn, (void*)0x22 ); + printf("UNWIND ERROR %d after force unwind\n", ret); + abort(); + } + + // We did not simply reach the end of the stack without finding a handler, + // Something wen't wrong + printf("UNWIND ERROR %d after raise exception\n", ret); + abort(); +} + +// Nesting this the other way would probably be faster. +void __rethrow_terminate(void) { + // DEBUG + printf("Rethrowing termination exception\n"); + + __throw_terminate(shared_stack.current_exception); +} + +// This is our personality routine +// For every stack frame anotated with ".cfi_personality 0x3,__gcfa_personality_v0" +// This function will be called twice when unwinding +// Once in the search phased and once in the cleanup phase +_Unwind_Reason_Code __gcfa_personality_v0 ( + int version, _Unwind_Action actions, unsigned long long exceptionClass, + struct _Unwind_Exception* unwind_exception, + struct _Unwind_Context* context) +{ + + // DEBUG + //printf("CFA: 0x%lx\n", _Unwind_GetCFA(context)); + printf("Personality function (%d, %x, %llu, %p, %p):", version, actions, exceptionClass, unwind_exception, context); + + // If we've reached the end of the stack then there is nothing much we can do... + if( actions & _UA_END_OF_STACK ) return _URC_END_OF_STACK; + + // DEBUG + if (actions & _UA_SEARCH_PHASE) { + printf(" lookup phase"); + } + // DEBUG + else if (actions & _UA_CLEANUP_PHASE) { + printf(" cleanup phase"); + } + // Just in case, probably can't actually happen + else { + printf(" error\n"); + return _URC_FATAL_PHASE1_ERROR; + } + + // Get a pointer to the language specific data from which we will read what we need + const unsigned char * lsd = (const unsigned char*) _Unwind_GetLanguageSpecificData( context ); + + if( !lsd ) { //Nothing to do, keep unwinding + printf(" no LSD"); + goto UNWIND; + } + + // Get the instuction pointer and a reading pointer into the exception table + lsda_header_info lsd_info; + const unsigned char * cur_ptr = parse_lsda_header( context, lsd, &lsd_info); + _Unwind_Ptr instruction_ptr = _Unwind_GetIP( context ); + + // Linearly search the table for stuff to do + while( cur_ptr < lsd_info.action_table ) { + _Unwind_Ptr callsite_start; + _Unwind_Ptr callsite_len; + _Unwind_Ptr callsite_landing_pad; + _uleb128_t callsite_action; + + // Decode the common stuff we have in here + cur_ptr = read_encoded_value (0, lsd_info.call_site_encoding, cur_ptr, &callsite_start); + cur_ptr = read_encoded_value (0, lsd_info.call_site_encoding, cur_ptr, &callsite_len); + cur_ptr = read_encoded_value (0, lsd_info.call_site_encoding, cur_ptr, &callsite_landing_pad); + cur_ptr = read_uleb128 (cur_ptr, &callsite_action); + + // Have we reach the correct frame info yet? + if( lsd_info.Start + callsite_start + callsite_len < instruction_ptr ) { + //DEBUG BEGIN + void * ls = (void*)lsd_info.Start; + void * cs = (void*)callsite_start; + void * cl = (void*)callsite_len; + void * bp = (void*)lsd_info.Start + callsite_start; + void * ep = (void*)lsd_info.Start + callsite_start + callsite_len; + void * ip = (void*)instruction_ptr; + printf("\nfound %p - %p (%p, %p, %p), looking for %p\n", bp, ep, ls, cs, cl, ip); + //DEBUG END + continue; + } + + // Have we gone too far + if( lsd_info.Start + callsite_start > instruction_ptr ) { + printf(" gone too far"); + break; + } + + // Something to do? + if( callsite_landing_pad ) { + // Which phase are we in + if (actions & _UA_SEARCH_PHASE) { + // Search phase, this means we probably found a potential handler and must check if it is a match + + // If we have arbitrarily decided that 0 means nothing to do and 1 means there is a potential handler + // This doesn't seem to conflict the gcc default behavior + if (callsite_action != 0) { + // Now we want to run some code to see if the handler matches + // This is the tricky part where we want to the power to run arbitrary code + // However, generating a new exception table entry and try routine every time + // is way more expansive than we might like + // The information we have is : + // - The GR (Series of registers) + // GR1=GP Global Pointer of frame ref by context + // - The instruction pointer + // - The instruction pointer info (???) + // - The CFA (Canonical Frame Address) + // - The BSP (Probably the base stack pointer) + + + // The current apprach uses one exception table entry per try block + _uleb128_t imatcher; + // Get the relative offset to the + cur_ptr = read_uleb128 (cur_ptr, &imatcher); + + // Get a function pointer from the relative offset and call it + // _Unwind_Reason_Code (*matcher)() = (_Unwind_Reason_Code (*)())lsd_info.LPStart + imatcher; + + _Unwind_Reason_Code (*matcher)() = + MATCHER_FROM_CONTEXT(context); + int index = matcher(shared_stack.current_exception); + _Unwind_Reason_Code ret = (0 == index) + ? _URC_CONTINUE_UNWIND : _URC_HANDLER_FOUND; + shared_stack.current_handler_index = index; + + // Based on the return value, check if we matched the exception + if( ret == _URC_HANDLER_FOUND) printf(" handler found\n"); + else printf(" no handler\n"); + return ret; + } + + // This is only a cleanup handler, ignore it + printf(" no action"); + } + else if (actions & _UA_CLEANUP_PHASE) { + + if( (callsite_action != 0) && !(actions & _UA_HANDLER_FRAME) ){ + // If this is a potential exception handler + // but not the one that matched the exception in the seach phase, + // just ignore it + goto UNWIND; + } + + // We need to run some clean-up or a handler + // These statment do the right thing but I don't know any specifics at all + _Unwind_SetGR( context, __builtin_eh_return_data_regno(0), (_Unwind_Ptr) unwind_exception ); + _Unwind_SetGR( context, __builtin_eh_return_data_regno(1), 0 ); + + // I assume this sets the instruction pointer to the adress of the landing pad + // It doesn't actually set it, it only state the value that needs to be set once we return _URC_INSTALL_CONTEXT + _Unwind_SetIP( context, lsd_info.LPStart + callsite_landing_pad ); + + // DEBUG + printf(" action\n"); + + // Return have some action to run + return _URC_INSTALL_CONTEXT; + } + } + + // Nothing to do, move along + printf(" no landing pad"); + } + // No handling found + printf(" table end reached\n"); + + // DEBUG + UNWIND: + printf(" unwind\n"); + + // Keep unwinding the stack + return _URC_CONTINUE_UNWIND; +} + +// Try statements are hoisted out see comments for details +// With this could probably be unique and simply linked from +// libcfa but there is one problem left, see the exception table +// for details +__attribute__((noinline)) +void __try_terminate(void (*try_block)(), + void (*catch_block)(int index, exception except), + __attribute__((unused)) int (*match_block)(exception except)) { + //! volatile int xy = 0; + //! printf("%p %p %p %p\n", &try_block, &catch_block, &match_block, &xy); + + // Setup statments + // These 2 statments won't actually result in any code, + // they only setup global tables. + // However, they clobber gcc cancellation support from gcc. + // We can replace the personality routine but replacing the exception + // table gcc generates is not really doable, it generates labels based + // on how the assembly works. + // Setup the personality routine + asm volatile (".cfi_personality 0x3,__gcfa_personality_v0"); + // Setup the exception table + asm volatile (".cfi_lsda 0x3, .LLSDACFA2"); + + // Label which defines the start of the area for which the handler is setup + asm volatile (".TRYSTART:"); + + // The actual statements of the try blocks + try_block(); + + // asm statement to prevent deadcode removal + asm volatile goto ("" : : : : CATCH ); + + // Normal return + return; + + // Exceptionnal path + CATCH : __attribute__(( unused )); + // Label which defines the end of the area for which the handler is setup + asm volatile (".TRYEND:"); + // Label which defines the start of the exception landing pad + // basically what will be called when the exception is caught + // Note, if multiple handlers are given, the multiplexing should be done + // by the generated code, not the exception runtime + asm volatile (".CATCH:"); + + // Exception handler + catch_block(shared_stack.current_handler_index, + shared_stack.current_exception); +} + +// Exception table data we need to generate +// While this is almost generic, the custom data refers to +// foo_try_match try match, which is no way generic +// Some more works need to be done if we want to have a single +// call to the try routine +asm ( + //HEADER + ".LFECFA1:\n" + " .globl __gcfa_personality_v0\n" + " .section .gcc_except_table,\"a\",@progbits\n" + ".LLSDACFA2:\n" //TABLE header + " .byte 0xff\n" + " .byte 0xff\n" + " .byte 0x1\n" + " .uleb128 .LLSDACSECFA2-.LLSDACSBCFA2\n" // BODY length + // Body uses language specific data and therefore could be modified arbitrarily + ".LLSDACSBCFA2:\n" // BODY start + " .uleb128 .TRYSTART-__try_terminate\n" // Handled area start (relative to start of function) + " .uleb128 .TRYEND-.TRYSTART\n" // Handled area length + " .uleb128 .CATCH-__try_terminate\n" // Hanlder landing pad adress (relative to start of function) + " .uleb128 1\n" // Action code, gcc seems to use always 0 + ".LLSDACSECFA2:\n" // BODY end + " .text\n" // TABLE footer + " .size __try_terminate, .-__try_terminate\n" + " .ident \"GCC: (Ubuntu 6.2.0-3ubuntu11~16.04) 6.2.0 20160901\"\n" +// " .section .note.GNU-stack,\"x\",@progbits\n" +); Index: doc/working/exception/impl/exception.h =================================================================== --- doc/working/exception/impl/exception.h (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) +++ doc/working/exception/impl/exception.h (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -0,0 +1,39 @@ +// Trying to create the new secret header for the exception handling mechanism. + +// This will have to go in the public header later. +typedef int exception; + + + +// These might be given simpler names and made public. +void __throw_terminate(exception except) __attribute__((noreturn)); +void __rethrow_terminate(void) __attribute__((noreturn)); +void __throw_resume(exception except); + +void __try_terminate(void (*try_block)(), + void (*catch_block)(int index, exception except), + int (*match_block)(exception except)); + +struct __try_resume_node { + struct __try_resume_node * next; + _Bool (*try_to_handle)(exception except); +}; + +struct __cleanup_hook {}; + + + +/* The following code is temperary. How exceptions interact with coroutines + * and threads means that... well I'm going to get it working ignoring those + * first, then get it working with concurrency. + */ +struct shared_stack_t { + //struct lock lock; + struct __try_resume_node * top_resume; + struct __try_resume_node * current_resume; + + exception current_exception; + int current_handler_index; +}; + +extern struct shared_stack_t shared_stack; Index: doc/working/exception/impl/main.c =================================================================== --- doc/working/exception/impl/main.c (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ (revision ) @@ -1,191 +1,0 @@ -#include -#include "except.h" - -// Requires -fexceptions to work. - -#define EXCEPTION 2 - -struct type_raii_t { - char * msg; -}; - -//Dtor function to test clean up routines -void dtor( struct type_raii_t * this ) { - printf("%s\n", this->msg); -} - -//Type macro use to make scope unwinding easier to see. -#define raii_t __attribute__(( cleanup(dtor) )) struct type_raii_t - -//Leaf functions that raises exception -void bar() { - raii_t a = { "Bar dtor" }; - - throw( EXCEPTION ); -} - -//Matcher function which will check if the exception was correctly caught -extern int this_exception; -_Unwind_Reason_Code foo_try_match() { - printf(" (foo_try_match called)"); - return this_exception == EXCEPTION ? _URC_HANDLER_FOUND : _URC_CONTINUE_UNWIND; -} - -//Try statements are hoisted out see comments for details -//With this could probably be unique and simply linked from -//libcfa but there is one problem left, see the exception table -//for details -__attribute__((noinline)) -void try( void (*try_block)(), void (*catch_block)(), - _Unwind_Reason_Code (*match_block)() ) -{ - volatile int xy = 0; - printf("%p %p %p %p\n", &try_block, &catch_block, &match_block, &xy); - - //Setup statments - //These 2 statments won't actually result in any code, - //they only setup global tables. - //However, they clobber gcc cancellation support from gcc. - //We can replace the personality routine but replacing the exception - //table gcc generates is not really doable, it generates labels based - //on how the assembly works. - //Setup the personality routine - asm volatile (".cfi_personality 0x3,__gcfa_personality_v0"); - //Setup the exception table - asm volatile (".cfi_lsda 0x3, .LLSDACFA2"); - - //Label which defines the start of the area for which the handler is setup - asm volatile (".TRYSTART:"); - - //The actual statements of the try blocks - try_block(); - - //asm statement to prevent deadcode removal - asm volatile goto ("" : : : : CATCH ); - - //Normal return - return; - - //Exceptionnal path - CATCH : __attribute__(( unused )); - //Label which defines the end of the area for which the handler is setup - asm volatile (".TRYEND:"); - //Label which defines the start of the exception landing pad - //basically what will be called when the exception is caught - //Note, if multiple handlers are given, the multiplexing should be done - //by the generated code, not the exception runtime - asm volatile (".CATCH:"); - - //Exception handler - catch_block(); -} - -//Exception table data we need to generate -//While this is almost generic, the custom data refers to -//foo_try_match try match, which is no way generic -//Some more works need to be done if we want to have a single -//call to the try routine -asm ( - //HEADER - ".LFECFA1:\n" - " .globl __gcfa_personality_v0\n" - " .section .gcc_except_table,\"a\",@progbits\n" - ".LLSDACFA2:\n" //TABLE header - " .byte 0xff\n" - " .byte 0xff\n" - " .byte 0x1\n" - " .uleb128 .LLSDACSECFA2-.LLSDACSBCFA2\n" //BODY length - //Body uses language specific data and therefore could be modified arbitrarily - ".LLSDACSBCFA2:\n" //BODY start - " .uleb128 .TRYSTART-try\n" //Handled area start (relative to start of function) - " .uleb128 .TRYEND-.TRYSTART\n" //Handled area length - " .uleb128 .CATCH-try\n" //Hanlder landing pad adress (relative to start of function) - " .uleb128 1\n" //Action code, gcc seems to use always 0 - ".LLSDACSECFA2:\n" //BODY end - " .text\n" //TABLE footer - " .size try, .-try\n" - " .ident \"GCC: (Ubuntu 6.2.0-3ubuntu11~16.04) 6.2.0 20160901\"\n" - " .section .note.GNU-stack,\"x\",@progbits\n" -); - -void foo() { - raii_t a = { "Foo dtor" }; - - //Since try will clobber the gcc exception table assembly, - //We need to nest this to have gcc regenerate the data - void foo_try_block() { - raii_t b = { "Foo try dtor" }; - - bar(); - - printf("Called bar successfully\n"); - } - - void foo_catch_block() { - printf("Exception caught\n"); - } - - //Actual call to the try block - try( foo_try_block, foo_catch_block, foo_try_match ); - - printf( "Foo exited normally\n" ); -} - -// Not in main.cfa -void fy() { - // Currently not destroyed if the exception is caught in fee. - raii_t a = { "Fy dtor" }; - - void fy_try_block() { - raii_t b = { "Fy try dtor" }; - - throw( 3 ); - } - - void fy_catch_block() { - printf("Fy caught exception\n"); - } - - _Unwind_Reason_Code fy_match_block() { - return this_exception == 2 ? _URC_HANDLER_FOUND : _URC_CONTINUE_UNWIND; - } - - try(fy_try_block, fy_catch_block, fy_match_block); - - printf( "Fy exited normally\n" ); -} - -void fee() { - raii_t a = { "Fee dtor" }; - - void fee_try_block() { - raii_t b = { "Fee try dtor" }; - - fy(); - - printf("fy returned\n"); - } - - void fee_catch_block() { - printf("Fee caught exception\n"); - } - - _Unwind_Reason_Code fee_match_block() { - return this_exception == 3 ? _URC_HANDLER_FOUND : _URC_CONTINUE_UNWIND; - } - - try(fee_try_block, fee_catch_block, fee_match_block); - - printf( "Fee exited normally\n" ); -} -// End not in main.cfa - -int main() { - raii_t a = { "Main dtor" }; - - //for (unsigned int i = 0 ; i < 100000000 ; ++i) - foo(); - fee(); - - printf("End of program reached\n"); -} Index: doc/working/exception/impl/resume-main.c =================================================================== --- doc/working/exception/impl/resume-main.c (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ (revision ) @@ -1,152 +1,0 @@ -#include -#include - -// Proof of concept for resumption exception handling. -// Names, checks promises and so on all would have to be improved. - -struct resume_group; - -// Stackwise information (global for single stack) -struct code_stack_data { - struct resume_group * top_resume; - struct resume_group * current_resume; -} stack = {NULL, NULL}; - -// private exception header begin ============================================ - -struct resume_group { - struct resume_group * next; - bool (*try_to_handle)(int); -}; - -void __resume_group_dtor(struct resume_group * this) { - stack.top_resume = this->next; -} - -void __cfa_eh__throw_resume(int except) { - struct resume_group * original_head = stack.current_resume; - struct resume_group * current = - (original_head) ? original_head->next : stack.top_resume; - - for ( ; current ; current = current->next) { - stack.current_resume = current; - if (current->try_to_handle(except)) { - stack.current_resume = original_head; - return; - } - } - - printf("Unhandled exception %d\n", except); -} - -// private exception header end ============================================== - -// Set up of unwind checker type. -struct type_raii_t { - char * msg; -}; - -void dtor( struct type_raii_t * this ) { - printf("%s\n", this->msg); -} - -#define raii_t __attribute__((cleanup(dtor))) struct type_raii_t - -void bar() { - raii_t a = { "Bar dtor" }; - - __cfa_eh__throw_resume( 3 ); -} - -void foo() { - raii_t a = { "Foo dtor" }; - - { - bool foo_catch_resume(int exception_id) { - if (exception_id == 3) { - printf("Exception caught\n"); - return true; - } - return false; - } - struct resume_group __attribute__((cleanup(__resume_group_dtor))) - foo_try_resume = {stack.top_resume, foo_catch_resume}; - stack.top_resume = &foo_try_resume; - { - raii_t b = { "Foo try dtor" }; - - bar(); - - printf("Called bar successfully\n"); - } - } - printf( "Foo exited normally\n" ); -} - -// Not in main.cfa -void foe() { - raii_t a = { "Foe dtor" }; - - printf("Foe throws\n"); - __cfa_eh__throw_resume( 4 ); - - printf("Foe exits normally\n"); -} - -void fy() { - raii_t a = { "Fy dtor" }; - - { - bool fy_catch_resume(int exception_id) { - if (4 == exception_id) { - printf("Rethrow in fy\n"); - __cfa_eh__throw_resume(exception_id); - return true; - } - return false; - } - struct resume_group __attribute__((cleanup(__resume_group_dtor))) - fy_try_resume = {stack.top_resume, fy_catch_resume}; - stack.top_resume = &fy_try_resume; - { - raii_t b = { "Fy try dtor" }; - foe(); - } - } - - printf("Fy exits normally\n"); -} - -void fee() { - raii_t a = { "Fee dtor" }; - - { - bool fee_catch_resume(int exception_id) { - if (4 == exception_id) { - printf("fee caught exception\n"); - return true; - } - return false; - } - struct resume_group __attribute__((cleanup(__resume_group_dtor))) - fee_try_resume = {stack.top_resume, fee_catch_resume}; - stack.top_resume = &fee_try_resume; - { - raii_t b = { "Fee try dtor" }; - fy(); - } - } - - printf("Fee exits normally\n"); -} -// End not in main.cfa - -int main() { - raii_t a = { "Main dtor" }; - - foo(); - - fee(); - - printf("End of program reached\n"); -} Index: doc/working/exception/impl/test-main.c =================================================================== --- doc/working/exception/impl/test-main.c (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) +++ doc/working/exception/impl/test-main.c (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -0,0 +1,482 @@ +#include "exception.h" + +// Use: gcc -fexceptions -Wall -Werror -g exception.c test-main.c + +#include +#include + +// Translation Helpers: +#define CLEANUP(function) \ + struct __cleanup_hook __hidden_hook __attribute__((cleanup(function))) + +#define SET_UP_RESUME_NODE(handler_function) \ + struct __try_resume_node node \ + __attribute__((cleanup(__try_resume_node_delete))); \ + __try_resume_node_new(&node, handler_function) + +void __try_resume_node_new(struct __try_resume_node * node, + _Bool (*handler)(exception except)) { + node->next = shared_stack.top_resume; + shared_stack.top_resume = node; + node->try_to_handle = handler; +} + +void __try_resume_node_delete(struct __try_resume_node * node) { + shared_stack.top_resume = node->next; +} + +// Local Print On Exit: +struct raii_base_type { + const char * area; +}; + +void raii_dtor(struct raii_base_type * this) { + printf("Exiting: %s\n", this->area); +} + +#define raii_t __attribute__((cleanup(raii_dtor))) struct raii_base_type + +// =========================================================================== +// Runtime code (post-translation). +void terminate(int except_value) { + raii_t a = {"terminate function"}; + __throw_terminate(except_value); + printf("terminate returned\n"); +} + +void resume(int except_value) { + raii_t a = {"resume function"}; + __throw_resume(except_value); + printf("resume returned\n"); +} + +// Termination Test: Two handlers: no catch, catch +void bar() { + raii_t a = {"bar function"}; + { + void bar_try1() { + terminate(4); + } + void bar_catch1(int index, exception except) { + switch(except) { + case 1: + printf("bar caught exception 3.\n"); + break; + default: + printf("INVALID INDEX in bar: %d (%d)\n", index, except); + } + } + int bar_match1(exception except) { + if (3 == except) { + return 1; + } else { + return 0; + } + } + __try_terminate(bar_try1, bar_catch1, bar_match1); + } +} + +void foo() { + raii_t a = {"foo function"}; + { + void foo_try1() { + bar(); + } + void foo_catch1(int index, exception except) { + switch(index) { + case 1: + printf("foo caught exception 4.\n"); + break; + case 2: + printf("foo caught exception 2.\n"); + break; + default: + printf("INVALID INDEX in foo: %d (%d)\n", index, except); + } + } + int foo_match1(exception except) { + if (4 == except) { + return 1; + } else if (2 == except) { + return 2; + } else { + return 0; + } + } + __try_terminate(foo_try1, foo_catch1, foo_match1); + } +} + +// Resumption Two Handler Test: no catch, catch. +void beta() { + raii_t a = {"beta function"}; + { + bool beta_handle1(exception except) { + if (3 == except) { + printf("beta caught exception 3\n"); + return true; + } else { + return false; + } + } + struct __try_resume_node node + __attribute__((cleanup(__try_resume_node_delete))); + __try_resume_node_new(&node, beta_handle1); + { + resume(4); + } + } +} +void alpha() { + raii_t a = {"alpha function"}; + { + bool alpha_handle1(exception except) { + if (2 == except) { + printf("alpha caught exception 2\n"); + return true; + } else if (4 == except) { + printf("alpha caught exception 4\n"); + return true; + } else { + return false; + } + } + struct __try_resume_node node + __attribute__((cleanup(__try_resume_node_delete))); + __try_resume_node_new(&node, alpha_handle1); + { + beta(); + } + } +} + +// Finally Test: +void farewell() { + { + void farewell_finally1() { + printf("See you next time\n"); + } + struct __cleanup_hook __hidden_hook + __attribute__((cleanup(farewell_finally1))); + { + printf("walk out of farewell\n"); + } + } +} + +// Resume-to-Terminate Test: +void fallback() { + { + void fallback_try1() { + resume(1); + } + void fallback_catch1(int index, exception except) { + switch (index) { + case 1: + printf("fallback caught termination 1\n"); + break; + default: + printf("INVALID INDEX in fallback: %d (%d)\n", index, except); + } + } + int fallback_match1(exception except) { + if (1 == except) { + return 1; + } else { + return 0; + } + } + __try_terminate(fallback_try1, fallback_catch1, fallback_match1); + } +} + +// Terminate Throw New Exception: +void terminate_swap() { + raii_t a = {"terminate_swap"}; + { + void fn_try1() { + terminate(2); + } + void fn_catch1(int index, exception except) { + switch (index) { + case 1: + terminate(1); + break; + default: + printf("INVALID INDEX in terminate_swap: %d (%d)\n", + index, except); + } + } + int fn_match1(exception except) { + if (2 == except) { + return 1; + } else { + return 0; + } + } + __try_terminate(fn_try1, fn_catch1, fn_match1); + } +} + +void terminate_swapped() { + raii_t a = {"terminate_swapped"}; + { + void fn_try1() { + terminate_swap(); + } + void fn_catch1(int index, exception except) { + switch (index) { + case 1: + printf("terminate_swapped caught exception 1\n"); + break; + default: + printf("INVALID INDEX in terminate_swapped: %d (%d)\n", + index, except); + } + } + int fn_match1(exception except) { + if (1 == except) { + return 1; + } else { + return 0; + } + } + __try_terminate(fn_try1, fn_catch1, fn_match1); + } +} + +// Resume Throw New Exception: +void resume_swap() { + raii_t a = {"terminate_swap"}; + { + bool fn_handle1(exception except) { + if (2 == except) { + resume(1); + return true; + } else { + return false; + } + } + struct __try_resume_node node + __attribute__((cleanup(__try_resume_node_delete))); + __try_resume_node_new(&node, fn_handle1); + { + resume(2); + } + } +} + +void resume_swapped() { + { + bool fn_handle1(exception except) { + if (1 == except) { + printf("resume_swapped caught exception 1\n"); + return true; + } else { + return false; + } + } + struct __try_resume_node node + __attribute__((cleanup(__try_resume_node_delete))); + __try_resume_node_new(&node, fn_handle1); + { + resume_swap(); + } + } +} + +// Terminate Rethrow: +// I don't have an implementation for this. +void reterminate() { + { + void fn_try1() { + void fn_try2() { + terminate(1); + } + void fn_catch2(int index, exception except) { + switch (index) { + case 1: + printf("reterminate 2 caught and " + "will rethrow exception 1\n"); + __rethrow_terminate(); + break; + default: + printf("INVALID INDEX in reterminate 2: %d (%d)\n", + index, except); + } + } + int fn_match2(exception except) { + if (1 == except) { + return 1; + } else { + return 0; + } + } + __try_terminate(fn_try2, fn_catch2, fn_match2); + } + void fn_catch1(int index, exception except) { + switch (index) { + case 1: + printf("reterminate 1 caught exception 1\n"); + break; + default: + printf("INVALID INDEX in reterminate 1: %d (%d)\n", + index, except); + } + } + int fn_match1(exception except) { + if (1 == except) { + return 1; + } else { + return 0; + } + } + __try_terminate(fn_try1, fn_catch1, fn_match1); + } +} + +// Resume Rethrow: +void reresume() { + { + bool reresume_handle1(exception except) { + if (1 == except) { + printf("reresume 1 caught exception 1\n"); + return true; + } else { + return false; + } + } + struct __try_resume_node node + __attribute__((cleanup(__try_resume_node_delete))); + __try_resume_node_new(&node, reresume_handle1); + { + bool reresume_handle2(exception except) { + if (1 == except) { + printf("reresume 2 caught and rethrows exception 1\n"); + return false; + } else { + return false; + } + } + struct __try_resume_node node + __attribute__((cleanup(__try_resume_node_delete))); + __try_resume_node_new(&node, reresume_handle2); + { + resume(1); + } + } + } +} + +// Terminate-Resume interaction: +void fum() { + // terminate block, call resume + { + void fum_try1() { + resume(3); + } + void fum_catch1(int index, exception except) { + switch (index) { + case 1: + printf("fum caught exception 3\n"); + break; + default: + printf("INVALID INDEX in fum: %d (%d)\n", index, except); + } + } + int fum_match1(exception except) { + if (3 == except) { + return 1; + } else { + return 0; + } + } + __try_terminate(fum_try1, fum_catch1, fum_match1); + } +} + +void foe() { + // resume block, call terminate + { + bool foe_handle1(exception except) { + if (3 == except) { + printf("foe caught exception 3\n"); + return true; + } else { + return false; + } + } + struct __try_resume_node node + __attribute__((cleanup(__try_resume_node_delete))); + __try_resume_node_new(&node, foe_handle1); + { + terminate(3); + } + } +} + +void fy() { + // terminate block calls fum, call foe + { + void fy_try1() { + foe(); + } + void fy_catch1(int index, exception except) { + switch (index) { + case 1: + printf("fy caught exception 3\n"); + fum(); + break; + default: + printf("INVALID INDEX in fy: %d (%d)\n", index, except); + } + } + int fy_match1(exception except) { + if (3 == except) { + return 1; + } else { + return 0; + } + } + __try_terminate(fy_try1, fy_catch1, fy_match1); + } +} + +void fee() { + // resume block, call fy + { + bool fee_handle1(exception except) { + if (3 == except) { + printf("fee caught exception 3\n"); + return true; + } else { + return false; + } + } + struct __try_resume_node node + __attribute__((cleanup(__try_resume_node_delete))); + __try_resume_node_new(&node, fee_handle1); + { + fy(); + } + } +} + + +// main: choose which tests to run +int main(int argc, char * argv[]) { + raii_t a = {"main function"}; + + foo(); printf("\n"); + alpha(); printf("\n"); + farewell(); printf("\n"); + fallback(); printf("\n"); + terminate_swapped(); printf("\n"); + resume_swapped(); printf("\n"); + reterminate(); printf("\n"); + reresume(); printf("\n"); + fee(); printf("\n"); + // Uncaught termination test. + terminate(7); +} Index: doc/working/exception/translate.c =================================================================== --- doc/working/exception/translate.c (revision 816d61c4e52f3e902a4f1080a0d52b56bec91b53) +++ doc/working/exception/translate.c (revision f13ee31ce49b84afc3073ce57778d6ed16695e87) @@ -54,4 +54,19 @@ __throw_resume(exception_instance); + + + +// Rethrows (inside matching handlers): +"Cforall" + +throw; + +resume; + +"C" + +__rethrow_terminate(); + +return false; @@ -237,5 +252,6 @@ } void finally1() { - // (Finally, because of timing, also work for resume.) + // Finally, because of timing, also works for resume. + // However this might not actually be better in any way. __try_resume_cleanup();