Changeset 7eb6eb5
- Timestamp:
- Jan 29, 2021, 8:23:52 AM (4 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 5669d0b
- Parents:
- 4dcd5ea
- Location:
- doc/theses/andrew_beach_MMath
- Files:
-
- 5 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/features.tex
r4dcd5ea r7eb6eb5 62 62 internally for exception handling. The only user-level feature is the virtual 63 63 cast, which is the same as the \CC \lstinline[language=C++]|dynamic_cast|. 64 \label{p:VirtualCast} 64 65 \begin{cfa} 65 66 (virtual TYPE)EXPRESSION … … 89 90 promises @exceptT@ is a virtual type and a child of the base exception-type. 90 91 91 {\color{blue} PAB:I do not understand this paragraph.}92 \PAB{I do not understand this paragraph.} 92 93 One odd thing about @get_exception_vtable@ is that it should always be a 93 94 constant function, returning the same value regardless of its argument. A … … 102 103 103 104 \section{Raise} 104 \CFA provides two kinds of exception raise: termination (see105 \ VRef{s:Termination}) and resumption (see \VRef{s:Resumption}), which are105 \CFA provides two kinds of exception raise: termination 106 \see{\VRef{s:Termination}} and resumption \see{\VRef{s:Resumption}}, which are 106 107 specified with the following traits. 107 108 \begin{cfa} … … 129 130 parenthesized list of polymorphic arguments. These macros do the name mangling 130 131 to get the virtual-table name and provide the arguments to both sides 131 {\color{blue}(PAB: What's a ``side''?)}132 \PAB{What's a ``side''?} 132 133 133 134 \subsection{Termination} … … 253 254 current point on the stack because new try statements may have been pushed by 254 255 the handler or functions called from the handler. If there is no match back to 255 the point of the current handler, the search skips the stack frames already256 the point of the current handler, the search skips\label{p:searchskip} the stack frames already 256 257 searched by the first resume and continues after the try statement. The default 257 258 handler always continues from default handler associated with the point where … … 291 292 continue searching the stack frames after the try statement. However, the 292 293 current try statement is still on the stack below the handler issuing the 293 reresume (see \VRef{s:Reraise}). Hence, the try statement catches the re-raise294 reresume \see{\VRef{s:Reraise}}. Hence, the try statement catches the re-raise 294 295 again and does another re-raise \emph{ad infinitum}, which is confusing and 295 296 difficult to debug. The \CFA resumption search-pattern skips the try statement … … 377 378 \begin{description} 378 379 \item[Main Stack:] 379 380 380 The main stack is the one used by the program main at the start of execution, 381 381 and is the only stack in a sequential program. Hence, when cancellation is … … 401 401 which exception has priority, the original or new exception? No matter which 402 402 exception is selected, it is possible for the selected one to disrupt or 403 destroy the context required for the other. {\color{blue} PAB: I do not404 understand the following sentences.} This loss of information can happen with 405 join but as the thread destructor is always run when the stack is being unwound 406 and one termination/cancellation is already active. Also since they are 407 implicit theyare easier to forget about.403 destroy the context required for the other. \PAB{I do not understand the 404 following sentences.} This loss of information can happen with join but as the 405 thread destructor is always run when the stack is being unwound and one 406 termination/cancellation is already active. Also since they are implicit they 407 are easier to forget about. 408 408 409 409 \item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object -
doc/theses/andrew_beach_MMath/future.tex
r4dcd5ea r7eb6eb5 1 1 \chapter{Future Work} 2 2 3 \section{Language Improvements} 4 \CFA is a developing programming language. As such, there are partially or 5 unimplemented features of the language (including several broken components) 6 that I had to workaround while building an exception handling system largely in 7 the \CFA language (some C components). The following are a few of these 8 issues, and once implemented/fixed, how this would affect the exception system. 9 \begin{itemize} 10 \item 11 The implementation of termination is not portable because it includes 12 hand-crafted assembly statements. These sections must be generalized to support 13 more hardware architectures, \eg ARM processor. 14 \item 15 Due to a type-system problem, the catch clause cannot bind the exception to a 16 reference instead of a pointer. Since \CFA has a very general reference 17 capability, programmers will want to use it. Once fixed, this capability should 18 result in little or no change in the exception system. 19 \item 20 Termination handlers cannot use local control-flow transfers, \eg by @break@, 21 @return@, \etc. The reason is that current code generation hoists a handler 22 into a nested function for convenience (versus assemble-code generation at the 23 @try@ statement). Hence, when the handler runs, its code is not in the lexical 24 scope of the @try@ statement, where the local control-flow transfers are 25 meaningful. 26 \end{itemize} 27 3 28 \section{Complete Virtual System} 4 The virtual system should be completed. It was n ever supposed to be part of5 this project and so minimal work was done on it. A draft of what the complete 6 system might look like was created but it was never finalized or implemented. 7 A future project in \CFA would be to complete that work and to update the 8 parts of the exception system that usethe current version.29 The virtual system should be completed. It was not supposed to be part of this 30 project, but was thrust upon it to do exception inheritance; hence, only 31 minimal work was done. A draft for a complete virtual system is available but 32 it is not finalized. A future \CFA project is to complete that work and then 33 update the exception system that uses the current version. 9 34 10 There are several improvements to the virtual system that would improve 11 the exception traits. The biggest one is an assertion that checks that one 12 virtual type is a child of another virtual type. This would capture many of 13 the requirements much more precisely.35 There are several improvements to the virtual system that would improve the 36 exception traits. The most important one is an assertion to check one virtual 37 type is a child of another. This check precisely captures many of the 38 correctness requirements. 14 39 15 40 The full virtual system might also include other improvement like associated 16 types. This is a proposed feature that would allow traits to refer to types 17 not listed in their header. This would allow the exception traits to not 18 refer to the virtual table type explicatly which would remove the need for 19 the interface macros. 41 types to allow traits to refer to types not listed in their header. This 42 feature allows exception traits to not refer to the virtual-table type 43 explicitly, removing the need for the current interface macros. 20 44 21 \section{Additional Throws} 22 Several other kinds of throws, beyond the termination throw (@throw@), 23 the resumption throw (@throwResume@) and the re-throws, were considered. 24 None were as useful as the core throws but they would likely be worth 25 revising. 45 \section{Additional Raises} 46 Several other kinds of exception raises were considered beyond termination 47 (@throw@), resumption (@throwResume@), and reraise. 26 48 27 The first ones are throws for asynchronous exceptions, throwing exceptions 28 from one stack to another. These act like signals allowing for communication 29 between the stacks. This is usually used with resumption as it allows the 30 target stack to continue execution normally after the exception has been 31 handled. 49 The first is a non-local/concurrent raise providing asynchronous exceptions, 50 \ie raising an exception on another stack. This semantics acts like signals 51 allowing for out-of-band communication among coroutines and threads. This kind 52 of raise is often restricted to resumption to allow the target stack to 53 continue execution normally after the exception has been handled. That is, 54 allowing one coroutine/thread to unwind the stack of another via termination is 55 bad software engineering. 32 56 33 This would much more coordination between the concurrency system and the 34 exception system to handle. Most of the interesting design decisions around 35 a pplying asynchronous exceptions appear to be around masking (controlling36 w hich exceptions may be thrown at a stack). It would likely require more of37 the virtual system and would also effect howdefault handlers are set.57 Non-local/concurrent requires more coordination between the concurrency system 58 and the exception system. Many of the interesting design decisions centre 59 around masking (controlling which exceptions may be thrown at a stack). It 60 would likely require more of the virtual system and would also effect how 61 default handlers are set. 38 62 39 The other throws were designed to mimic bidirectional algebraic effects.40 Algebraic effects are used in some functional languages a nd allow afunction63 Other raises were considered to mimic bidirectional algebraic effects. 64 Algebraic effects are used in some functional languages allowing one function 41 65 to have another function on the stack resolve an effect (which is defined with 42 a function-like interface). 43 These can be mimiced with resumptions and the the new throws were designed 44 to try and mimic bidirectional algebraic effects, where control can go back 45 and forth between the function effect caller and handler while the effect 46 is underway. 66 a functional-like interface). This semantics can be mimicked with resumptions 67 and new raises were discussed to mimic bidirectional algebraic-effects, where 68 control can go back and forth between the function-effect caller and handler 69 while the effect is underway. 47 70 % resume-top & resume-reply 71 These raises would be like the resumption raise except using different search 72 patterns to find the handler. 48 73 49 These throws would likely be just like the resumption throw except they would 50 use different search patterns to find the handler to reply to. 74 \section{Zero-Cost Try} 75 \CFA does not have zero-cost try-statements because the compiler generates C 76 code rather than assembler code \see{\VPageref{p:zero-cost}}. When the compiler 77 does create its own assembly (or LLVM byte-code), then zero-cost try-statements 78 are possible. The downside of zero-cost try-statements is the LSDA complexity, 79 its size (program bloat), and the high cost of raising an exception. 51 80 52 \section{Zero-Cost Exceptions} 53 \CFA does not have zero-cost exceptions because it does not generate assembly 54 but instead generates C code. See the implementation section. When the 55 compiler does start to create its own assembly (or LLVM byte code) then 56 zero-cost exceptions could be implemented. 81 Alternatively, some research could be done into the simpler alternative method 82 with a non-zero-cost try-statement but much lower cost exception raise. For 83 example, programs are starting to use exception in the normal control path, so 84 more exceptions are thrown. In these cases, the cost balance switches towards 85 low-cost raise. Unfortunately, while exceptions remain exceptional, the 86 libunwind model will probably remain the most effective option. 57 87 58 Now in zero-cost exceptions the only part that is zero-cost are the try 59 blocks. Some research could be done into the alternative methods for systems 60 that expect a lot more exceptions to be thrown, allowing some overhead in 61 entering and leaving try blocks to make throws faster. But while exceptions 62 remain exceptional the libunwind model will probably remain the most effective 63 option. 88 Zero-cost resumptions is still an open problem. First, because libunwind does 89 not support a successful-exiting stack-search without doing an unwind. 90 Workarounds are possible but awkward. Ideally an extension to libunwind could 91 be made, but that would either require separate maintenance or gain enough 92 support to have it folded into the standard. 64 93 65 Zero-cost resumptions have more problems to solve. First because libunwind 66 does not support a successful exiting stack search without doing an unwind. 67 There are several ways to hack that functionality in. Ideally an extension to 68 libunwind could be made, but that would either require seperate maintenance 69 or gain enough support to have it folded into the standard. 70 71 Also new techniques to skip previously searched parts of the stack will have 72 to be developed. The recursive resume problem still remains and ideally the 73 same pattern of ignoring sections of the stack. 94 Also new techniques to skip previously searched parts of the stack need to be 95 developed to handle the recursive resume problem and support advanced algebraic 96 effects. 74 97 75 98 \section{Signal Exceptions} 76 Exception Handling: Issues and a Proposed Notation suggests there are three 77 types of exceptions: escape, notify and signal. 78 Escape exceptions are our termination exceptions, notify exceptions are 79 resumption exceptions and that leaves signal exception unimplemented. 99 Goodenough~\cite{Goodenough75} suggests three types of exceptions: escape, 100 notify and signal. Escape are termination exceptions, notify are resumption 101 exceptions, leaving signal unimplemented. 80 102 81 Signal exceptions allow either behaviour, that is after the exception is 82 handled control can either return to the throw or from where the handler is 83 defined. 103 A signal exception allows either behaviour, \ie after an exception is handled, 104 the handler has the option of returning to the raise or after the @try@ 105 statement. Currently, \CFA fixes the semantics of the handler return 106 syntactically by the @catch@ or @catchResume@ clause. 84 107 85 The design should be rexamined and be updated for \CFA. A very direct 86 translation would perhaps have a new throw and catch pair and astatement87 (or statements) could be used to decide if the handler returns to the throw88 or continues where it is, but there are other options.108 Signal exception should be reexamined and possibly be supported in \CFA. A very 109 direct translation is to have a new raise and catch pair, and a new statement 110 (or statements) would indicate if the handler returns to the raise or continues 111 where it is; but there may be other options. 89 112 90 For instance resumption could be extended to cover this use by allowing91 local control flow out of it. Thiswould require an unwind as part of the92 transition as there are stack frames that have to be removed. 93 This would mean there is no notify like throw but because \CFA does not have 94 exception signatures a termination can be thrown from any resumption handler 95 already so there are already ways one could try to dothis in existing \CFA.113 For instance, resumption could be extended to cover this use by allowing local 114 control flow out of it. This approach would require an unwind as part of the 115 transition as there are stack frames that have to be removed. This approach 116 means there is no notify raise, but because \CFA does not have exception 117 signatures, a termination can be thrown from within any resumption handler so 118 there is already a way to do mimic this in existing \CFA. 96 119 97 120 % Maybe talk about the escape; and escape CONTROL_STMT; statements or how 98 121 % if we could choose if _Unwind_Resume proceeded to the clean-up stage this 99 122 % would be much easier to implement. 100 101 \section{Language Improvements}102 There is also a lot of work that are not follow ups to this work in terms of103 research, some have no interesting research to be done at all, but would104 improve \CFA as a programming language. The full list of these would105 naturally be quite extensive but here are a few examples that involve106 exceptions:107 108 \begin{itemize}109 \item The implementation of termination is not portable because it includes110 some assembly statements. These sections will have to be re-written to so111 \CFA has full support on more machines.112 \item Allowing exception handler to bind the exception to a reference instead113 of a pointer. This should actually result in no change in behaviour so there114 is no reason not to allow it. It is however a small improvement; giving a bit115 of flexibility to the user in what style they want to use.116 \item Enabling local control flow (by @break@, @return@ and117 similar statements) out of a termination handler. The current set-up makes118 this very difficult but the catch function that runs the handler after it has119 been matched could be inlined into the function's body, which would make this120 much easier. (To do the same for try blocks would probably wait for zero-cost121 exceptions, which would allow the try block to be inlined as well.)122 \end{itemize} -
doc/theses/andrew_beach_MMath/implement.tex
r4dcd5ea r7eb6eb5 2 2 % Goes over how all the features are implemented. 3 3 4 The implementation work for this thesis covers two components: the virtual 5 system and exceptions. Each component is discussed in detail. 6 4 7 \section{Virtual System} 8 \label{s:VirtualSystem} 5 9 % Virtual table rules. Virtual tables, the pointer to them and the cast. 6 The \CFA virtual system only has one public facing feature: virtual casts. 7 However there is a lot of structure to support that and provide some other 8 features for the standard library. 9 10 All of this is accessed through a field inserted at the beginning of every 11 virtual type. Currently it is called @virtual_table@ but it is not 12 ment to be accessed by the user. This field is a pointer to the type's 13 virtual table instance. It is assigned once during the object's construction 14 and left alone after that. 15 16 \subsection{Virtual Table Construction} 17 For each virtual type a virtual table is constructed. This is both a new type 18 and an instance of that type. Other instances of the type could be created 19 but the system doesn't use them. So this section will go over the creation of 20 the type and the instance. 21 22 Creating the single instance is actually very important. The address of the 23 table acts as the unique identifier for the virtual type. Similarly the first 24 field in every virtual table is the parent's id; a pointer to the parent 25 virtual table instance. 26 27 The remaining fields contain the type's virtual members. First come the ones 28 present on the parent type, in the same order as they were the parent, and 29 then any that this type introduces. The types of the ones inherited from the 30 parent may have a slightly modified type, in that references to the 31 dispatched type are replaced with the current virtual type. These are always 32 taken by pointer or reference. 33 34 The structure itself is created where the virtual type is created. The name 35 of the type is created by mangling the name of the base type. The name of the 36 instance is also generated by name mangling. 37 38 The fields are initialized automatically. 10 While the \CFA virtual system currently has only one public feature, virtual 11 cast \see{\VPageref{p:VirtualCast}}, substantial structure is required to 12 support it, and provide features for exception handling and the standard 13 library. 14 15 \subsection{Virtual Table} 16 The virtual system is accessed through a private constant field inserted at the 17 beginning of every virtual type, called the virtual-table pointer. This field 18 points at a type's virtual table and is assigned during the object's 19 construction. The address of a virtual table acts as the unique identifier for 20 the virtual type, and the first field of a virtual table is a pointer to the 21 parent virtual-table or @0p@. The remaining fields are duplicated from the 22 parent tables in this type's inheritance chain, followed by any fields this type 23 introduces. Parent fields are duplicated so they can be changed (\CC 24 \lstinline[language=c++]|override|), so that references to the dispatched type 25 are replaced with the current virtual type. 26 \PAB{Can you create a simple diagram of the layout?} 27 % These are always taken by pointer or reference. 28 29 % For each virtual type, a virtual table is constructed. This is both a new type 30 % and an instance of that type. Other instances of the type could be created 31 % but the system doesn't use them. So this section will go over the creation of 32 % the type and the instance. 33 34 A virtual table is created when the virtual type is created. The name of the 35 type is created by mangling the name of the base type. The name of the instance 36 is also generated by name mangling. The fields are initialized automatically. 39 37 The parent field is initialized by getting the type of the parent field and 40 38 using that to calculate the mangled name of the parent's virtual table type. 41 39 There are two special fields that are included like normal fields but have 42 40 special initialization rules: the @size@ field is the type's size and is 43 initialized with a sizeof expression, the @align@ field is the type's 44 alignment and uses an alignof expression. The remaining fields are resolved 45 to a name matching the field's name and type using the normal visibility 46 and overload resolution rules of the type system. 47 48 These operations are split up into several groups depending on where they 49 take place which can vary for monomorphic and polymorphic types. The first 50 devision is between the declarations and the definitions. Declarations, such 51 as a function signature or a structure's name, must always be visible but may 52 be repeated so they go in headers. Definitions, such as function bodies and a 53 structure's layout, don't have to be visible on use but must occur exactly 54 once and go into source files. 55 41 initialized with a @sizeof@ expression, the @align@ field is the type's 42 alignment and uses an @alignof@ expression. The remaining fields are resolved 43 to a name matching the field's name and type using the normal visibility and 44 overload resolution rules of the type system. 45 46 These operations are split up into several groups depending on where they take 47 place which varies for monomorphic and polymorphic types. The first devision is 48 between the declarations and the definitions. Declarations, such as a function 49 signature or a aggregate's name, must always be visible but may be repeated in 50 the form of forward declarations in headers. Definitions, such as function 51 bodies and a aggregate's layout, can be separately compiled but must occur 52 exactly once in a source file. 53 54 \begin{sloppypar} 56 55 The declarations include the virtual type definition and forward declarations 57 56 of the virtual table instance, constructor, message function and 58 @get_exception_vtable@. The definition includes the storage and 59 initialization of the virtual table instance and the bodies of the three 60 functions. 57 @get_exception_vtable@. The definition includes the storage and initialization 58 of the virtual table instance and the bodies of the three functions. 59 \end{sloppypar} 61 60 62 61 Monomorphic instances put all of these two groups in one place each. 63 64 Polymorphic instances also split out the core declarations and definitions65 from the per-instance information. The virtual table type and most of the66 functions are polymorphic so they are all part of the core. The virtual table 67 instance and the @get_exception_vtable@ function. 68 62 Polymorphic instances also split out the core declarations and definitions from 63 the per-instance information. The virtual table type and most of the functions 64 are polymorphic so they are all part of the core. The virtual table instance 65 and the @get_exception_vtable@ function. 66 67 \begin{sloppypar} 69 68 Coroutines and threads need instances of @CoroutineCancelled@ and 70 @ThreadCancelled@ respectively to use all of their functionality. 71 When a new data type is declared with @coroutine@ or @thread@ 72 the forward declaration for the instance is created as well. The definition 73 of the virtual table is created at the definition of the main function. 69 @ThreadCancelled@ respectively to use all of their functionality. When a new 70 data type is declared with @coroutine@ or @thread@ the forward declaration for 71 the instance is created as well. The definition of the virtual table is created 72 at the definition of the main function. 73 \end{sloppypar} 74 74 75 75 \subsection{Virtual Cast} 76 Virtual casts are implemented as a function call that does the check and a 77 old C-style cast to do the type conversion. The C-cast is just to make sure 78 the generated code is correct so the rest of the section is about that 79 function. 80 81 The function is @__cfa__virtual_cast@ and it is implemented in the 82 standard library. It takes a pointer to the target type's virtual table and 83 the object pointer being cast. The function is very simple, getting the 84 object's virtual table pointer and then checking to see if it or any of 85 its ancestors, by using the parent pointers, are the same as the target type 86 virtual table pointer. It does this in a simple loop. 87 88 For the generated code a forward decaration of the virtual works as follows. 89 There is a forward declaration of @__cfa__virtual_cast@ in every cfa 90 file so it can just be used. The object argument is the expression being cast 91 so that is just placed in the argument list. 92 93 To build the target type parameter the compiler will create a mapping from 94 concrete type-name -- so for polymorphic types the parameters are filled in 95 -- to virtual table address. Every virtual table declaraction is added to the 96 this table; repeats are ignored unless they have conflicting definitions. 97 This does mean the declaractions have to be in scope, but they should usually 98 be introduced as part of the type definition. 76 Virtual casts are implemented as a function call that does the subtype check 77 and a C coercion-cast to do the type conversion. 78 % The C-cast is just to make sure the generated code is correct so the rest of 79 % the section is about that function. 80 The function is 81 \begin{cfa} 82 void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent, 83 struct __cfa__parent_vtable const * const * child ); 84 } 85 \end{cfa} 86 and it is implemented in the standard library. It takes a pointer to the target 87 type's virtual table and the object pointer being cast. The function performs a 88 linear search starting at the object's virtual-table and walking through the 89 the parent pointers, checking to if it or any of its ancestors are the same as 90 the target-type virtual table-pointer. 91 92 For the generated code, a forward declaration of the virtual works as follows. 93 There is a forward declaration of @__cfa__virtual_cast@ in every \CFA file so 94 it can just be used. The object argument is the expression being cast so that 95 is just placed in the argument list. 96 97 To build the target type parameter, the compiler creates a mapping from 98 concrete type-name -- so for polymorphic types the parameters are filled in -- 99 to virtual table address. Every virtual table declaration is added to the this 100 table; repeats are ignored unless they have conflicting definitions. Note, 101 these declarations do not have to be in scope, but they should usually be 102 introduced as part of the type definition. 103 104 \PAB{I do not understood all of \VRef{s:VirtualSystem}. I think you need to 105 write more to make it clear.} 106 99 107 100 108 \section{Exceptions} … … 106 114 % resumption doesn't as well. 107 115 108 Many modern languages work with an interal stack that function push and pop 109 their local data to. Stack unwinding removes large sections of the stack, 110 often across functions. 111 112 At a very basic level this can be done with @setjmp@ \& @longjmp@ 113 which simply move the top of the stack, discarding everything on the stack 114 above a certain point. However this ignores all the clean-up code that should 115 be run when certain sections of the stack are removed (for \CFA these are from 116 destructors and finally clauses) and also requires that the point to which the 117 stack is being unwound is known ahead of time. libunwind is used to address 118 both of these problems. 119 120 Libunwind, provided in @unwind.h@ on most platorms, is a C library 121 that provides \CPP style stack unwinding. Its operation is divided into two 122 phases. The search phase -- phase 1 -- is used to scan the stack and decide 123 where the unwinding will stop, this allows for a dynamic target. The clean-up 124 phase -- phase 2 -- does the actual unwinding and also runs any clean-up code 125 as it goes. 126 127 To use the libunwind each function must have a personality function and an 128 LSDA (Language Specific Data Area). Libunwind actually does very little, it 129 simply moves down the stack from function to function. Most of the actions are 130 implemented by the personality function which libunwind calls on every 131 function. Since this is shared across many functions or even every function in 132 a language it will need a bit more information. This is provided by the LSDA 133 which has the unique information for each function. 134 135 Theoretically the LSDA can contain anything but conventionally it is a table 136 with entries reperenting areas of the function and what has to be done there 137 during unwinding. These areas are described in terms of where the instruction 138 pointer is. If the current value of the instruction pointer is between two 139 values reperenting the beginning and end of a region then execution is 140 currently being executed. These are used to mark out try blocks and the 141 scopes of objects with destructors to run. 142 143 GCC will generate an LSDA and attach its personality function with the 144 @-fexceptions@ flag. However this only handles the cleanup attribute. 145 This attribute is used on a variable and specifies a function that should be 146 run when the variable goes out of scope. The function is passed a pointer to 147 the object as well so it can be used to mimic destructors. It however cannot 148 be used to mimic try statements. 149 150 \subsection{Implementing Personality Functions} 151 Personality functions have a complex interface specified by libunwind. 152 This section will cover some of the important parts of that interface. 153 154 \begin{lstlisting} 155 typedef _Unwind_Reason_Code (*_Unwind_Personality_Fn)( 156 int version, 157 _Unwind_Action action, 158 _Unwind_Exception_Class exception_class, 159 _Unwind_Exception * exception, 160 struct _Unwind_Context * context); 116 % Many modern languages work with an interal stack that function push and pop 117 % their local data to. Stack unwinding removes large sections of the stack, 118 % often across functions. 119 120 Stack unwinding is the process of removing stack frames (activations) from the 121 stack. On function entry and return, unwinding is handled directly by the code 122 embedded in the function. Usually, the stack-frame size is known statically 123 based on parameter and local variable declarations. For dynamically-sized 124 local variables, a runtime computation is necessary to know the frame 125 size. Finally, a function's frame-size may change during execution as local 126 variables (static or dynamic sized) go in and out of scope. 127 Allocating/deallocating stack space is usually an $O(1)$ operation achieved by 128 bumping the hardware stack-pointer up or down as needed. 129 130 Unwinding across multiple stack frames is more complex because individual stack 131 management code associated with each frame is bypassed. That is, the location 132 of a function's frame-management code is largely unknown and dispersed 133 throughout the function, hence the current frame size managed by that code is 134 also unknown. Hence, code unwinding across frames does not have direct 135 knowledge about what is on the stack, and hence, how much of the stack needs to 136 be removed. 137 138 % At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply 139 % move the top of the stack, discarding everything on the stack above a certain 140 % point. However this ignores all the cleanup code that should be run when 141 % certain sections of the stack are removed (for \CFA these are from destructors 142 % and finally clauses) and also requires that the point to which the stack is 143 % being unwound is known ahead of time. libunwind is used to address both of 144 % these problems. 145 146 The traditional unwinding mechanism for C is implemented by saving a snap-shot 147 of a function's state with @setjmp@ and restoring that snap-shot with 148 @longjmp@. This approach bypasses the need to know stack details by simply 149 reseting to a snap-shot of an arbitrary but existing function frame on the 150 stack. It is up to the programmer to ensure the snap-shot is valid when it is 151 reset, making this unwinding approach fragile with potential errors that are 152 difficult to debug because the stack becomes corrupted. 153 154 However, many languages define cleanup actions that must be taken when objects 155 are deallocated from the stack or blocks end, such as running a variable's 156 destructor or a @try@ statement's @finally@ clause. Handling these mechanisms 157 requires walking the stack and checking each stack frame for these potential 158 actions. 159 160 For exceptions, it must be possible to walk the stack frames in search of @try@ 161 statements to match and execute a handler. For termination exceptions, it must 162 also be possible to unwind all stack frames from the throw to the matching 163 catch, and each of these frames must be checked for cleanup actions. Stack 164 walking is where most of the complexity and expense of exception handling 165 appears. 166 167 One of the most popular tools for stack management is libunwind, a low-level 168 library that provides tools for stack walking, handler execution, and 169 unwinding. What follows is an overview of all the relevant features of 170 libunwind needed for this work, and how \CFA uses them to implement exception 171 handling. 172 173 \subsection{libunwind Usage} 174 Libunwind, accessed through @unwind.h@ on most platforms, is a C library that 175 provides \CC-style stack-unwinding. Its operation is divided into two phases: 176 search and cleanup. The dynamic target search -- phase 1 -- is used to scan the 177 stack and decide where unwinding should stop (but no unwinding occurs). The 178 cleanup -- phase 2 -- does the unwinding and also runs any cleanup code. 179 180 To use libunwind, each function must have a personality function and a Language 181 Specific Data Area (LSDA). The LSDA has the unique information for each 182 function to tell the personality function where a function is executing, its 183 current stack frame, and what handlers should be checked. Theoretically, the 184 LSDA can contain any information but conventionally it is a table with entries 185 representing regions of the function and what has to be done there during 186 unwinding. These regions are bracketed by the instruction pointer. If the 187 instruction pointer is within a region's start/end, then execution is currently 188 executing in that region. Regions are used to mark out the scopes of objects 189 with destructors and try blocks. 190 191 % Libunwind actually does very little, it simply moves down the stack from 192 % function to function. Most of the actions are implemented by the personality 193 % function which libunwind calls on every function. Since this is shared across 194 % many functions or even every function in a language it will need a bit more 195 % information. 196 197 The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and 198 attaches its personality function. \PAB{to what is it attached?} However, this 199 flag only handles the cleanup attribute 200 \begin{cfa} 201 void clean_up( int * var ) { ... } 202 int avar __attribute__(( __cleanup(clean_up) )); 203 \end{cfa} 204 which is used on a variable and specifies a function, \eg @clean_up@, run when 205 the variable goes out of scope. The function is passed a pointer to the object 206 so it can be used to mimic destructors. However, this feature cannot be used to 207 mimic @try@ statements. 208 209 \subsection{Personality Functions} 210 Personality functions have a complex interface specified by libunwind. This 211 section covers some of the important parts of the interface. 212 213 A personality function performs four tasks, although not all have to be 214 present. 215 \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] 216 typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) ( 217 _Unwind_Action @action@, 218 _Unwind_Exception_Class @exception_class@, 219 _Unwind_Exception * @exception@, 220 struct _Unwind_Context * @context@ 221 ); 161 222 \end{lstlisting} 162 163 The return value, the reason code, is an enumeration of possible messages 223 The @action@ argument is a bitmask of possible actions: 224 \begin{enumerate} 225 \item 226 @_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function 227 to check for handlers. If there is a handler in a stack frame, as defined by 228 the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise 229 it return @_URC_CONTINUE_UNWIND@. 230 231 \item 232 @_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is 233 unwound and all cleanup code is run. The personality function does whatever 234 cleanup the language defines (such as running destructors/finalizers) and then 235 generally returns @_URC_CONTINUE_UNWIND@. 236 237 \item 238 \begin{sloppypar} 239 @_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a 240 handler. The personality function must prepare to return to normal code 241 execution and return @_URC_INSTALL_CONTEXT@. 242 \end{sloppypar} 243 244 \item 245 @_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs 246 the cleanup phase and uses a different means to decide when to stop 247 \see{\VRef{s:ForcedUnwind}}. 248 \end{enumerate} 249 250 The @exception_class@ argument is a copy of the 251 \lstinline[language=C]|exception|'s @exception_class@ field. 252 253 The \lstinline[language=C]|exception| argument is a pointer to the user 254 provided storage object. It has two public fields, the exception class, which 255 is actually just a number, identifying the exception handling mechanism that 256 created it, and the cleanup function. The cleanup function is called if 257 required by the exception. 258 259 The @context@ argument is a pointer to an opaque type passed to helper 260 functions called inside the personality function. 261 262 The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages 164 263 that can be passed several places in libunwind. It includes a number of 165 264 messages for special cases (some of which should never be used by the … … 167 266 personality function should always return @_URC_CONTINUE_UNWIND@. 168 267 169 The @version@ argument is the verson of the implementation that is170 calling the personality function. At this point it appears to always be 1 and171 it will likely stay that way until a new version of the API is updated.172 173 The @action@ argument is set of flags that tell the personality174 function when it is being called and what it must do on this invocation.175 The flags are as follows:176 \begin{itemize}177 \item@_UA_SEARCH_PHASE@: This flag is set whenever the personality178 function is called during the search phase. The personality function should179 decide if unwinding will stop in this function or not. If it does then the180 personality function should return @_URC_HANDLER_FOUND@.181 \item@_UA_CLEANUP_PHASE@: This flag is set whenever the personality182 function is called during the cleanup phase. If no other flags are set this183 means the entire frame will be unwound and all cleanup code should be run.184 \item@_UA_HANDLER_FRAME@: This flag is set during the cleanup phase185 on the function frame that found the handler. The personality function must186 prepare to return to normal code execution and return187 @_URC_INSTALL_CONTEXT@.188 \item@_UA_FORCE_UNWIND@: This flag is set if the personality function189 is called through a forced unwind call. Forced unwind only performs the190 cleanup phase and uses a different means to decide when to stop. See its191 section below.192 \end{itemize}193 194 The @exception_class@ argument is a copy of the @exception@'s195 @exception_class@ field.196 197 The @exception@ argument is a pointer to the user provided storage198 object. It has two public fields, the exception class which is actually just199 a number that identifies the exception handling mechanism that created it and200 the other is the clean-up function. The clean-up function is called if the201 exception needs to202 203 The @context@ argument is a pointer to an opaque type. This is passed204 to the many helper functions that can be called inside the personality205 function.206 207 268 \subsection{Raise Exception} 208 This could be considered the central function of libunwind. It preforms the 209 two staged unwinding the library is built around and most of the rest of the 210 interface of libunwind is here to support it. It's signature is as follows: 211 212 \begin{lstlisting} 269 Raising an exception is the central function of libunwind and it performs a 270 two-staged unwinding. 271 \begin{cfa} 213 272 _Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *); 273 \end{cfa} 274 First, the function begins the search phase, calling the personality function 275 of the most recent stack frame. It continues to call personality functions 276 traversing the stack from newest to oldest until a function finds a handler or 277 the end of the stack is reached. In the latter case, raise exception returns 278 @_URC_END_OF_STACK@. 279 280 Second, when a handler is matched, raise exception continues onto the cleanup phase. 281 Once again, it calls the personality functions of each stack frame from newest 282 to oldest. This pass stops at the stack frame containing the matching handler. 283 If that personality function has not install a handler, it is an error. 284 285 If an error is encountered, raise exception returns either 286 @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the 287 error occurred. 288 289 \subsection{Forced Unwind} 290 \label{s:ForcedUnwind} 291 Forced Unwind is the other central function in libunwind. 292 \begin{cfa} 293 _Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *, 294 _Unwind_Stop_Fn, void *); 295 \end{cfa} 296 It also unwinds the stack but it does not use the search phase. Instead another 297 function, the stop function, is used to stop searching. The exception is the 298 same as the one passed to raise exception. The extra arguments are the stop 299 function and the stop parameter. The stop function has a similar interface as a 300 personality function, except it is also passed the stop parameter. 301 \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] 302 typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)( 303 _Unwind_Action @action@, 304 _Unwind_Exception_Class @exception_class@, 305 _Unwind_Exception * @exception@, 306 struct _Unwind_Context * @context@, 307 void * @stop_parameter@); 214 308 \end{lstlisting} 215 309 216 When called the function begins the search phase, calling the personality217 function of the most recent stack frame. It will continue to call personality218 functions traversing the stack new-to-old until a function finds a handler or219 the end of the stack is reached. In the latter case raise exception will220 return with @_URC_END_OF_STACK@.221 222 Once a handler has been found raise exception continues onto the the cleanup223 phase. Once again it will call the personality functins of each stack frame224 from newest to oldest. This pass will stop at the stack frame that found the225 handler last time, if that personality function does not install the handler226 it is an error.227 228 If an error is encountered raise exception will return either229 @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending230 on when the error occured.231 232 \subsection{Forced Unwind}233 This is the second big function in libunwind. It also unwinds a stack but it234 does not use the search phase. Instead another function, the stop function,235 is used to decide when to stop.236 237 \begin{lstlisting}238 _Unwind_Reason_Code _Unwind_ForcedUnwind(239 _Unwind_Exception *, _Unwind_Stop_Fn, void *);240 \end{lstlisting}241 242 The exception is the same as the one passed to raise exception. The extra243 arguments are the stop function and the stop parameter. The stop function has244 a similar interface as a personality function, except it is also passed the245 stop parameter.246 247 \begin{lstlisting}248 typedef _Unwind_Reason_Code (*_Unwind_Stop_Fn)(249 int version,250 _Unwind_Action action,251 _Unwind_Exception_Class exception_class,252 _Unwind_Exception * exception,253 struct _Unwind_Context * context,254 void * stop_parameter);255 \end{lstlisting}256 257 310 The stop function is called at every stack frame before the personality 258 function is called and then once more once after all frames of the stack have 259 been unwound. 260 261 Each time it is called the stop function should return @_URC_NO_REASON@ 262 or transfer control directly to other code outside of libunwind. The 263 framework does not provide any assistance here. 264 265 Its arguments are the same as the paired personality function. 266 The actions @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always 267 set when it is called. By the official standard that is all but both GCC and 268 Clang add an extra action on the last call at the end of the stack: 269 @_UA_END_OF_STACK@. 311 function is called and then once more after all frames of the stack are 312 unwound. 313 314 Each time it is called, the stop function should return @_URC_NO_REASON@ or 315 transfer control directly to other code outside of libunwind. The framework 316 does not provide any assistance here. 317 318 \begin{sloppypar} 319 Its arguments are the same as the paired personality function. The actions 320 @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is 321 called. Beyond the libunwind standard, both GCC and Clang add an extra action 322 on the last call at the end of the stack: @_UA_END_OF_STACK@. 323 \end{sloppypar} 270 324 271 325 \section{Exception Context} 272 326 % Should I have another independent section? 273 327 % There are only two things in it, top_resume and current_exception. How it is 274 % stored changes depending on wheither or not the thread-library is linked. 275 276 The exception context is a piece of global storage used to maintain data 277 across different exception operations and to communicate between different 278 components. 279 280 Each stack has its own exception context. In a purely sequental program, using 281 only core Cforall, there is only one stack and the context is global. However 282 if the library @libcfathread@ is linked then there can be multiple 283 stacks so they will each need their own. 284 285 To handle this code always gets the exception context from the function 286 @this_exception_context@. The main exception handling code is in 287 @libcfa@ and that library also defines the function as a weak symbol 288 so it acts as a default. Meanwhile in @libcfathread@ the function is 289 defined as a strong symbol that replaces it when the libraries are linked 290 together. 291 292 The version of the function defined in @libcfa@ is very simple. It 293 returns a pointer to a global static variable. With only one stack this 294 global instance is associated with the only stack. 295 296 The version of the function defined in @libcfathread@ has to handle 297 more as there are multiple stacks. The exception context is included as 298 part of the per-stack data stored as part of coroutines. In the cold data 299 section, stored at the base of each stack, is the exception context for that 300 stack. The @this_exception_context@ uses the concurrency library to get 301 the current coroutine and through it the cold data section and the exception 302 context. 328 % stored changes depending on whether or not the thread-library is linked. 329 330 The exception context is global storage used to maintain data across different 331 exception operations and to communicate among different components. 332 333 Each stack must have its own exception context. In a sequential \CFA program, 334 there is only one stack with a single global exception-context. However, when 335 the library @libcfathread@ is linked, there are multiple stacks where each 336 needs its own exception context. 337 338 General access to the exception context is provided by function 339 @this_exception_context@. For sequential execution, this function is defined as 340 a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is 341 concurrent, it links with @libcfathread@, where this function is defined with a 342 strong symbol replacing the sequential version. 343 344 % The version of the function defined in @libcfa@ is very simple. It returns a 345 % pointer to a global static variable. With only one stack this global instance 346 % is associated with the only stack. 347 348 For coroutines, @this_exception_context@ accesses the exception context stored 349 at the base of the stack. For threads, @this_exception_context@ uses the 350 concurrency library to access the current stack of the thread or coroutine 351 being executed by the thread, and then accesses the exception context stored at 352 the base of this stack. 303 353 304 354 \section{Termination} … … 306 356 % catches. Talk about GCC nested functions. 307 357 308 Termination exceptions use libunwind quite heavily because it matches the309 intended use from \CPP exceptions very closely. The main complication is that 310 since the \CFA compiler works by translating to C code it cannot generate the 311 assembly toform the LSDA for try blocks or destructors.358 Termination exceptions use libunwind heavily because it matches the intended 359 use from \CC exceptions closely. The main complication for \CFA is that the 360 compiler generates C code, making it very difficult to generate the assembly to 361 form the LSDA for try blocks or destructors. 312 362 313 363 \subsection{Memory Management} 314 The first step of termination is to copy the exception into memory managed by315 the exception system. Currently the system just uses malloc, without reserved 316 memory or and ``small allocation" optimizations. The exception handling 317 me chanism manages memory for the exception as well as memory for libunwind318 and the system's ownper-exception storage.319 320 Exceptions are stored in variable sized block. The first component is a fixed321 sized data structure that contains the information for libunwind andthe322 exception system. The second component is a blob of memory that is big enough 323 to store the exception. Macros with pointer arthritic and type cast are 324 used to move between the components or go from the embedded364 The first step of a termination raise is to copy the exception into memory 365 managed by the exception system. Currently, the system uses @malloc@, rather 366 than reserved memory or the stack top. The exception handling mechanism manages 367 memory for the exception as well as memory for libunwind and the system's own 368 per-exception storage. 369 370 Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout 371 figure.} The first component is a fixed sized data structure that contains the 372 information for libunwind and the exception system. The second component is an 373 area of memory big enough to store the exception. Macros with pointer arthritic 374 and type cast are used to move between the components or go from the embedded 325 375 @_Unwind_Exception@ to the entire node. 326 376 327 All of these nodes are strung together in a linked list. One linked list per 328 stack, with the head stored in the exception context. Within each linked list 329 the most recently thrown exception is at the head and the older exceptions 330 are further down the list. This list format allows exceptions to be thrown 331 while a different exception is being handled. Only the exception at the head 332 of the list is currently being handled, the other will wait for the 333 exceptions before them to be removed. 334 335 The virtual members in the exception's virtual table. The size of the 336 exception, the copy function and the free function are all in the virtual 337 table so they are decided per-exception type. The size and copy function are 338 used right away when the exception is copied in to managed memory. After the 339 exception is handled the free function is used to clean up the exception and 340 then the entire node is passed to free. 341 342 \subsection{Try Statements \& Catch Clauses} 343 The try statements with termination handlers have a pretty complex conversion 344 to compensate for the lack of assembly generation. Libunwind requires an LSDA 345 (Language Specific Data Area) and personality function for a function to 346 unwind across it. The LSDA in particular is hard to generate at the level of 347 C which is what the \CFA compiler outputs so a work-around is used. 348 349 This work around is a function called @__cfaehm_try_terminate@ in the 350 standard library. The contents of a try block and the termination handlers 351 are converted into functions. These are then passed to the try terminate 352 function and it calls them. This puts the try statements in their own 353 functions so that no function has to deal with both termination handlers and 354 destructors. 355 356 This function has some custom embedded assembly that defines its personality 357 function and LSDA. This is hand coded in C which is why there is only one 358 version of it, the compiler has no capability to generate it. The personality 359 function is structured so that it may be expanded, but really it only handles 360 this one function. Notably it does not handle any destructors so the function 361 is constructed so that it does need to run it. 377 All of these nodes are linked together in a list, one list per stack, with the 378 list head stored in the exception context. Within each linked list, the most 379 recently thrown exception is at the head followed by older thrown 380 exceptions. This format allows exceptions to be thrown, while a different 381 exception is being handled. The exception at the head of the list is currently 382 being handled, while other exceptions wait for the exceptions before them to be 383 removed. 384 385 The virtual members in the exception's virtual table provide the size of the 386 exception, the copy function, and the free function, so they are specific to an 387 exception type. The size and copy function are used immediately to copy an 388 exception into managed memory. After the exception is handled the free function 389 is used to clean up the exception and then the entire node is passed to free. 390 391 \subsection{Try Statements and Catch Clauses} 392 The try statement with termination handlers is complex because it must 393 compensate for the lack of assembly-code generated from \CFA. Libunwind 394 requires an LSDA and personality function for control to unwind across a 395 function. The LSDA in particular is hard to mimic in generated C code. 396 397 The workaround is a function called @__cfaehm_try_terminate@ in the standard 398 library. The contents of a try block and the termination handlers are converted 399 into functions. These are then passed to the try terminate function and it 400 calls them. This approach puts a try statement in its own functions so that no 401 function has to deal with both termination handlers and destructors. \PAB{I do 402 not understand the previous sentence.} 403 404 This function has some custom embedded assembly that defines \emph{its} 405 personality function and LSDA. The assembly is created with handcrafted C @asm@ 406 statements, which is why there is only one version of it. The personality 407 function is structured so that it can be expanded, but currently it only 408 handles this one function. Notably, it does not handle any destructors so the 409 function is constructed so that it does need to run it. \PAB{I do not 410 understand the previous sentence.} 362 411 363 412 The three functions passed to try terminate are: 364 \begin{ itemize}365 \item The try function: This function is the try block, all the code inside366 t he try block is placed inside the try function. It takes no parameters and367 has no return value. This function is called during regular execution to run 368 the tryblock.369 \item The match function: This function decides if this try statement should 370 handle any given termination exception. It takes a pointer to the exception 371 and returns 0 if the exception is not handled here. Otherwise the return value 372 is the id of the handler that should handle the exception. It is called 373 during the search phase. 374 It is constructed from the conditional part of each handler. It runs each 375 check in turn, first checking to see if the object 376 \item The catch function: This function handles the exception. It takes a 377 pointer to the exception and the handler's id and returns nothing. It is 378 called after the clean-up phase. 379 It is constructed by stitching together the bodies of each handler 380 \end{itemize} 381 All three are created with GCC nested functions. GCC nested functions can be 382 used to create closures, functions that can refer to the state of other 383 functions on the stack. This allows the functions to refer to the main 384 function and all the variables in scope. 385 386 These nested functions and all other functions besides 387 @__cfaehm_try_terminate@ in \CFA use the GCC personality function and 388 the @-fexceptions@ flag to generate the LSDA. This allows destructors 389 t o be implemented with the cleanup attribute.413 \begin{description} 414 \item[try function:] This function is the try block, all the code inside the 415 try block is placed inside the try function. It takes no parameters and has no 416 return value. This function is called during regular execution to run the try 417 block. 418 419 \item[match function:] This function is called during the search phase and 420 decides if a catch clause matches the termination exception. It is constructed 421 from the conditional part of each handler and runs each check, top to bottom, 422 in turn, first checking to see if the exception type matches and then if the 423 condition is true. It takes a pointer to the exception and returns 0 if the 424 exception is not handled here. Otherwise the return value is the id of the 425 handler that matches the exception. 426 427 \item[handler function:] This function handles the exception. It takes a 428 pointer to the exception and the handler's id and returns nothing. It is called 429 after the cleanup phase. It is constructed by stitching together the bodies of 430 each handler and dispatches to the selected handler. 431 \end{description} 432 All three functions are created with GCC nested functions. GCC nested functions 433 can be used to create closures, functions that can refer to the state of other 434 functions on the stack. This approach allows the functions to refer to all the 435 variables in scope for the function containing the @try@ statement. These 436 nested functions and all other functions besides @__cfaehm_try_terminate@ in 437 \CFA use the GCC personality function and the @-fexceptions@ flag to generate 438 the LSDA. This allows destructors to be implemented with the cleanup attribute. 390 439 391 440 \section{Resumption} 392 441 % The stack-local data, the linked list of nodes. 393 442 394 Resumption uses a list of nodes for its stack traversal. The head of the list 395 is stored in the exception context. The nodes in the list just have a pointer 443 Resumption simple to implement because there is no stack unwinding. The 444 resumption raise uses a list of nodes for its stack traversal. The head of the 445 list is stored in the exception context. The nodes in the list have a pointer 396 446 to the next node and a pointer to the handler function. 397 447 398 The on a resumption throw the this list is traversed. At each node the 399 handler function is called and is passed the exception by pointer. It returns400 true if the exception washandled and false otherwise.401 402 The handler function does both the matching and catching. It tries each403 the condition of @catchResume@ in order, top-to-bottom and until it 404 finds ahandler that matches. If no handler matches then the function returns405 false. Otherwise the matching handler is run , if it completes successfully406 the function returns true. Rethrows, through the @throwResume;@ 407 statement, causethe function to return true.448 A resumption raise traverses this list. At each node the handler function is 449 called, passing the exception by pointer. It returns true if the exception is 450 handled and false otherwise. 451 452 The handler function does both the matching and handling. It computes the 453 condition of each @catchResume@ in top-to-bottom order, until it finds a 454 handler that matches. If no handler matches then the function returns 455 false. Otherwise the matching handler is run; if it completes successfully, the 456 function returns true. Reresume, through the @throwResume;@ statement, cause 457 the function to return true. 408 458 409 459 % Recursive Resumption Stuff: 410 Blocking out part of the stack is accomplished by updating the front of the 411 list as the search continues. Before the handler at a node is called the head 412 of the list is updated to the next node of the current node. After the search 413 is complete, successful or not, the head of the list is reset. 414 415 This means the current handler and every handler that has already been 416 checked are not on the list while a handler is run. If a resumption is thrown 417 during the handling of another resumption the active handlers and all the 418 other handler checked up to this point will not be checked again. 460 Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack 461 already examined, is accomplished by updating the front of the list as the 462 search continues. Before the handler at a node is called the head of the list 463 is updated to the next node of the current node. After the search is complete, 464 successful or not, the head of the list is reset. 465 466 This mechanism means the current handler and every handler that has already 467 been checked are not on the list while a handler is run. If a resumption is 468 thrown during the handling of another resumption the active handlers and all 469 the other handler checked up to this point are not checked again. 419 470 420 471 This structure also supports new handler added while the resumption is being 421 472 handled. These are added to the front of the list, pointing back along the 422 stack -- the first one will point over all the checked handlers -- and the 423 ordering is maintained. 424 425 \subsection{Libunwind Compatibility} 426 Resumption does not use libunwind for two simple reasons. The first is that 427 it does not have to unwind anything so would never need to use the clean-up 428 phase. Still the search phase could be used to make it free to enter or exit 429 a try statement with resumption handlers in the same way termination handlers 430 are for the same trade off in the cost of the throw. This is where the second 431 reason comes in, there is no way to return from a search without installing 432 a handler or raising an error. 433 434 Although work arounds could be created none seemed to be worth it for the 435 prototype. This implementation has no difference in behaviour and is much 436 simpler. 473 stack -- the first one points over all the checked handlers -- and the ordering 474 is maintained. 475 476 \label{p:zero-cost} 477 Note, the resumption implementation has a cost for entering/exiting a @try@ 478 statement with @catchResume@ clauses, whereas a @try@ statement with @catch@ 479 clauses has zero-cost entry/exit. While resumption does not need the stack 480 unwinding and cleanup provided by libunwind, it could use the search phase to 481 providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way 482 to return from a libunwind search without installing a handler or raising an 483 error. Although workarounds might be possible, they are beyond the scope of 484 this thesis. The current resumption implementation has simplicity in its 485 favour. 437 486 % Seriously, just compare the size of the two chapters and then consider 438 487 % that unwind is required knowledge for that chapter. … … 440 489 \section{Finally} 441 490 % Uses destructors and GCC nested functions. 442 Finally clauses are a simple decomposition to some of the existing features. 443 The code in the block is placed into a GCC nested function with a unique name, 444 no arguments or return values. This nested function is then set as the 445 clean-up function of an empty object that is declared at the beginning of a 446 block placed around the contexts of the try statement. 491 Finally clauses is placed into a GCC nested-function with a unique name, and no 492 arguments or return values. This nested function is then set as the cleanup 493 function of an empty object that is declared at the beginning of a block placed 494 around the context of the associated @try@ statement. 447 495 448 496 The rest is handled by GCC. The try block and all handlers are inside the 449 block. When they are complete control exits the block and the empty object450 is cleanedup, which runs the function that contains the finally code.497 block. At completion, control exits the block and the empty object is cleaned 498 up, which runs the function that contains the finally code. 451 499 452 500 \section{Cancellation} … … 454 502 455 503 Cancellation also uses libunwind to do its stack traversal and unwinding, 456 however it uses a different primary function @_Unwind_ForcedUnwind@. 457 Details of its interface can be found in the unwind section.458 459 The first step of cancellation is to find the stack was cancelled and which460 type of stack it is. Luckily the threadslibrary stores the main thread461 pointer and the current thread pointer and every thread stores a pointer to504 however it uses a different primary function @_Unwind_ForcedUnwind@. Details 505 of its interface can be found in the \VRef{s:ForcedUnwind}. 506 507 The first step of cancellation is to find the cancelled stack and its type: 508 coroutine or thread. Fortunately, the thread library stores the main thread 509 pointer and the current thread pointer, and every thread stores a pointer to 462 510 its main coroutine and the coroutine it is currently executing. 463 511 464 So if the the current thread's main and current coroutine do not match, it is 465 a coroutine cancellation. Otherwise if the main and current thread do not 466 match, it is a thread cancellation. Otherwise it is a main thread 467 cancellation. 468 469 However if the threading library is not linked then execution must be on the 470 main stack as that is the only one that exists. So the entire check is skipped 471 using the linker and weak symbols. Instead the main thread cancellation is 472 unconditionally preformed. 473 474 Regardless of how they are choosen afterwords the stop function and the stop 475 parameter are passed to the forced unwind functon. The general pattern of all 476 three stop functions is the same, they continue unwinding until the end of 477 stack when they do there primary work. 478 479 Main stack cancellation it is very simple. The ``transfer" is just an abort, 480 the program stops executing. 481 482 The coroutine cancellation stores the exception on the coroutine and then 483 does a coroutine context switch. The rest is handled inside resume. Every time 484 control returns from a resumed thread there is a check to see if it is 485 cancelled. If it is the exception is retrieved and the CoroutineCancelled 486 exception is constructed and loaded. It is then thrown as a regular exception 487 with the default handler coming from the context of the resumption call. 488 489 The thread cancellation stores the exception on the thread's main stack and 490 then returns to the scheduler. The rest is handled by the joiner. The wait 491 for the joined thread to finish works the same but after that it checks 492 to see if there was a cancellation. If there was the exception is retrieved 493 and the ThreadCancelled exception is constructed. The default handler is 494 passed in as a function pointer. If it is null (as it is for the 495 auto-generated joins on destructor call) it a default is used that simply 496 calls abort; which gives the required handling on implicate join. 512 The first check is if the current thread's main and current coroutine do not 513 match, implying a coroutine cancellation; otherwise, it is a thread 514 cancellation. Otherwise it is a main thread cancellation. \PAB{Previous 515 sentence does not make sense.} 516 517 However, if the threading library is not linked, the sequential execution is on 518 the main stack. Hence, the entire check is skipped because the weak-symbol 519 function is loaded. Therefore, a main thread cancellation is unconditionally 520 performed. 521 522 Regardless of how the stack is chosen, the stop function and parameter are 523 passed to the forced-unwind function. The general pattern of all three stop 524 functions is the same: they continue unwinding until the end of stack when they 525 do there primary work. 526 527 For main stack cancellation, the transfer is just a program abort. 528 529 For coroutine cancellation, the exception is stored on the coroutine's stack, 530 and the coroutine context switches to its last resumer. The rest is handled on 531 the backside of the resume, which check if the resumed coroutine is 532 cancelled. If cancelled, the exception is retrieved from the resumed coroutine, 533 and a @CoroutineCancelled@ exception is constructed and loaded with the 534 cancelled exception. It is then resumed as a regular exception with the default 535 handler coming from the context of the resumption call. 536 537 For thread cancellation, the exception is stored on the thread's main stack and 538 then context switched to the scheduler. The rest is handled by the thread 539 joiner. When the join is complete, the joiner checks if the joined thread is 540 cancelled. If cancelled, the exception is retrieved and the joined thread, and 541 a @ThreadCancelled@ exception is constructed and loaded with the cancelled 542 exception. The default handler is passed in as a function pointer. If it is 543 null (as it is for the auto-generated joins on destructor call), the default is 544 used, which is a program abort. 545 %; which gives the required handling on implicate join. -
doc/theses/andrew_beach_MMath/unwinding.tex
r4dcd5ea r7eb6eb5 182 182 control has returned to normal control flow. 183 183 184 {\color{blue}PAB:Maybe a diagram would be helpful?}184 \PAB{Maybe a diagram would be helpful?} -
doc/theses/andrew_beach_MMath/uw-ethesis.tex
r4dcd5ea r7eb6eb5 91 91 \hypersetup{ 92 92 plainpages=false, % needed if Roman numbers in frontpages 93 unicode=false, % non-Latin characters in Acrobat ’s bookmarks94 pdftoolbar=true, % show Acrobat ’s toolbar?95 pdfmenubar=true, % show Acrobat ’s menu?93 unicode=false, % non-Latin characters in Acrobat's bookmarks 94 pdftoolbar=true, % show Acrobat's toolbar? 95 pdfmenubar=true, % show Acrobat's menu? 96 96 pdffitwindow=false, % window fit to page when opened 97 97 pdfstartview={FitH}, % fits the width of the page to the window … … 164 164 \CFAStyle % CFA code-style for all languages 165 165 \lstset{language=CFA,basicstyle=\linespread{0.9}\tt} % CFA default lnaguage 166 \newcommand{\PAB}[1]{{\color{blue}PAB: #1}} 166 167 167 168 %====================================================================== … … 188 189 \input{existing} 189 190 \input{features} 190 \input{unwinding} 191 \input{implement} 192 %\input{unwinding} 191 193 \input{future} 192 194
Note: See TracChangeset
for help on using the changeset viewer.