Changeset 7eb6eb5 for doc/theses


Ignore:
Timestamp:
Jan 29, 2021, 8:23:52 AM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
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
Message:

complete first proofread of Andrew's thesis

Location:
doc/theses/andrew_beach_MMath
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/features.tex

    r4dcd5ea r7eb6eb5  
    6262internally for exception handling. The only user-level feature is the virtual
    6363cast, which is the same as the \CC \lstinline[language=C++]|dynamic_cast|.
     64\label{p:VirtualCast}
    6465\begin{cfa}
    6566(virtual TYPE)EXPRESSION
    … …  
    8990promises @exceptT@ is a virtual type and a child of the base exception-type.
    9091
    91 {\color{blue} PAB: I do not understand this paragraph.}
     92\PAB{I do not understand this paragraph.}
    9293One odd thing about @get_exception_vtable@ is that it should always be a
    9394constant function, returning the same value regardless of its argument.  A
    … …  
    102103
    103104\section{Raise}
    104 \CFA provides two kinds of exception raise: termination (see
    105 \VRef{s:Termination}) and resumption (see \VRef{s:Resumption}), which are
     105\CFA provides two kinds of exception raise: termination
     106\see{\VRef{s:Termination}} and resumption \see{\VRef{s:Resumption}}, which are
    106107specified with the following traits.
    107108\begin{cfa}
    … …  
    129130parenthesized list of polymorphic arguments. These macros do the name mangling
    130131to 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''?}
    132133
    133134\subsection{Termination}
    … …  
    253254current point on the stack because new try statements may have been pushed by
    254255the 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 already
     256the point of the current handler, the search skips\label{p:searchskip} the stack frames already
    256257searched by the first resume and continues after the try statement. The default
    257258handler always continues from default handler associated with the point where
    … …  
    291292continue searching the stack frames after the try statement. However, the
    292293current 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-raise
     294reresume \see{\VRef{s:Reraise}}. Hence, the try statement catches the re-raise
    294295again and does another re-raise \emph{ad infinitum}, which is confusing and
    295296difficult to debug. The \CFA resumption search-pattern skips the try statement
    … …  
    377378\begin{description}
    378379\item[Main Stack:]
    379 
    380380The main stack is the one used by the program main at the start of execution,
    381381and is the only stack in a sequential program.  Hence, when cancellation is
    … …  
    401401which exception has priority, the original or new exception? No matter which
    402402exception 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 not
    404 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 they are easier to forget about.
     403destroy the context required for the other. \PAB{I do not understand the
     404following sentences.} This loss of information can happen with join but as the
     405thread destructor is always run when the stack is being unwound and one
     406termination/cancellation is already active. Also since they are implicit they
     407are easier to forget about.
    408408
    409409\item[Coroutine Stack:] A coroutine stack is created for a @coroutine@ object

  • doc/theses/andrew_beach_MMath/future.tex

    r4dcd5ea r7eb6eb5  
    11\chapter{Future Work}
    22
     3\section{Language Improvements}
     4\CFA is a developing programming language. As such, there are partially or
     5unimplemented features of the language (including several broken components)
     6that I had to workaround while building an exception handling system largely in
     7the \CFA language (some C components).  The following are a few of these
     8issues, and once implemented/fixed, how this would affect the exception system.
     9\begin{itemize}
     10\item
     11The implementation of termination is not portable because it includes
     12hand-crafted assembly statements. These sections must be generalized to support
     13more hardware architectures, \eg ARM processor.
     14\item
     15Due to a type-system problem, the catch clause cannot bind the exception to a
     16reference instead of a pointer. Since \CFA has a very general reference
     17capability, programmers will want to use it. Once fixed, this capability should
     18result in little or no change in the exception system.
     19\item
     20Termination handlers cannot use local control-flow transfers, \eg by @break@,
     21@return@, \etc. The reason is that current code generation hoists a handler
     22into 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
     24scope of the @try@ statement, where the local control-flow transfers are
     25meaningful.
     26\end{itemize}
     27
    328\section{Complete Virtual System}
    4 The virtual system should be completed. It was never supposed to be part of
    5 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 use the current version.
     29The virtual system should be completed. It was not supposed to be part of this
     30project, but was thrust upon it to do exception inheritance; hence, only
     31minimal work was done. A draft for a complete virtual system is available but
     32it is not finalized.  A future \CFA project is to complete that work and then
     33update the exception system that uses the current version.
    934
    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.
     35There are several improvements to the virtual system that would improve the
     36exception traits. The most important one is an assertion to check one virtual
     37type is a child of another. This check precisely captures many of the
     38correctness requirements.
    1439
    1540The 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.
     41types to allow traits to refer to types not listed in their header. This
     42feature allows exception traits to not refer to the virtual-table type
     43explicitly, removing the need for the current interface macros.
    2044
    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}
     46Several other kinds of exception raises were considered beyond termination
     47(@throw@), resumption (@throwResume@), and reraise.
    2648
    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.
     49The first is a non-local/concurrent raise providing asynchronous exceptions,
     50\ie raising an exception on another stack. This semantics acts like signals
     51allowing for out-of-band communication among coroutines and threads. This kind
     52of raise is often restricted to resumption to allow the target stack to
     53continue execution normally after the exception has been handled. That is,
     54allowing one coroutine/thread to unwind the stack of another via termination is
     55bad software engineering.
    3256
    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 applying asynchronous exceptions appear to be around masking (controlling
    36 which exceptions may be thrown at a stack). It would likely require more of
    37 the virtual system and would also effect how default handlers are set.
     57Non-local/concurrent requires more coordination between the concurrency system
     58and the exception system. Many of the interesting design decisions centre
     59around masking (controlling which exceptions may be thrown at a stack). It
     60would likely require more of the virtual system and would also effect how
     61default handlers are set.
    3862
    39 The other throws were designed to mimic bidirectional algebraic effects.
    40 Algebraic effects are used in some functional languages and allow a function
     63Other raises were considered to mimic bidirectional algebraic effects.
     64Algebraic effects are used in some functional languages allowing one function
    4165to 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.
     66a functional-like interface).  This semantics can be mimicked with resumptions
     67and new raises were discussed to mimic bidirectional algebraic-effects, where
     68control can go back and forth between the function-effect caller and handler
     69while the effect is underway.
    4770% resume-top & resume-reply
     71These raises would be like the resumption raise except using different search
     72patterns to find the handler.
    4873
    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
     76code rather than assembler code \see{\VPageref{p:zero-cost}}. When the compiler
     77does create its own assembly (or LLVM byte-code), then zero-cost try-statements
     78are possible. The downside of zero-cost try-statements is the LSDA complexity,
     79its size (program bloat), and the high cost of raising an exception.
    5180
    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.
     81Alternatively, some research could be done into the simpler alternative method
     82with a non-zero-cost try-statement but much lower cost exception raise. For
     83example, programs are starting to use exception in the normal control path, so
     84more exceptions are thrown. In these cases, the cost balance switches towards
     85low-cost raise. Unfortunately, while exceptions remain exceptional, the
     86libunwind model will probably remain the most effective option.
    5787
    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.
     88Zero-cost resumptions is still an open problem. First, because libunwind does
     89not support a successful-exiting stack-search without doing an unwind.
     90Workarounds are possible but awkward. Ideally an extension to libunwind could
     91be made, but that would either require separate maintenance or gain enough
     92support to have it folded into the standard.
    6493
    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.
     94Also new techniques to skip previously searched parts of the stack need to be
     95developed to handle the recursive resume problem and support advanced algebraic
     96effects.
    7497
    7598\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.
     99Goodenough~\cite{Goodenough75} suggests three types of exceptions: escape,
     100notify and signal.  Escape are termination exceptions, notify are resumption
     101exceptions, leaving signal unimplemented.
    80102
    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.
     103A signal exception allows either behaviour, \ie after an exception is handled,
     104the handler has the option of returning to the raise or after the @try@
     105statement. Currently, \CFA fixes the semantics of the handler return
     106syntactically by the @catch@ or @catchResume@ clause.
    84107
    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 a statement
    87 (or statements) could be used to decide if the handler returns to the throw
    88 or continues where it is, but there are other options.
     108Signal exception should be reexamined and possibly be supported in \CFA. A very
     109direct 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
     111where it is; but there may be other options.
    89112
    90 For instance resumption could be extended to cover this use by allowing
    91 local control flow out of it. This would require an unwind as part of the
    92 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 do this in existing \CFA.
     113For instance, resumption could be extended to cover this use by allowing local
     114control flow out of it. This approach would require an unwind as part of the
     115transition as there are stack frames that have to be removed.  This approach
     116means there is no notify raise, but because \CFA does not have exception
     117signatures, a termination can be thrown from within any resumption handler so
     118there is already a way to do mimic this in existing \CFA.
    96119
    97120% Maybe talk about the escape; and escape CONTROL_STMT; statements or how
    98121% if we could choose if _Unwind_Resume proceeded to the clean-up stage this
    99122% 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 of
    103 research, some have no interesting research to be done at all, but would
    104 improve \CFA as a programming language. The full list of these would
    105 naturally be quite extensive but here are a few examples that involve
    106 exceptions:
    107 
    108 \begin{itemize}
    109 \item The implementation of termination is not portable because it includes
    110 some assembly statements. These sections will have to be re-written to so
    111 \CFA has full support on more machines.
    112 \item Allowing exception handler to bind the exception to a reference instead
    113 of a pointer. This should actually result in no change in behaviour so there
    114 is no reason not to allow it. It is however a small improvement; giving a bit
    115 of flexibility to the user in what style they want to use.
    116 \item Enabling local control flow (by @break@, @return@ and
    117 similar statements) out of a termination handler. The current set-up makes
    118 this very difficult but the catch function that runs the handler after it has
    119 been matched could be inlined into the function's body, which would make this
    120 much easier. (To do the same for try blocks would probably wait for zero-cost
    121 exceptions, which would allow the try block to be inlined as well.)
    122 \end{itemize}

  • doc/theses/andrew_beach_MMath/implement.tex

    r4dcd5ea r7eb6eb5  
    22% Goes over how all the features are implemented.
    33
     4The implementation work for this thesis covers two components: the virtual
     5system and exceptions. Each component is discussed in detail.
     6
    47\section{Virtual System}
     8\label{s:VirtualSystem}
    59% 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.
     10While the \CFA virtual system currently has only one public feature, virtual
     11cast \see{\VPageref{p:VirtualCast}}, substantial structure is required to
     12support it, and provide features for exception handling and the standard
     13library.
     14
     15\subsection{Virtual Table}
     16The virtual system is accessed through a private constant field inserted at the
     17beginning of every virtual type, called the virtual-table pointer. This field
     18points at a type's virtual table and is assigned during the object's
     19construction.  The address of a virtual table acts as the unique identifier for
     20the virtual type, and the first field of a virtual table is a pointer to the
     21parent virtual-table or @0p@.  The remaining fields are duplicated from the
     22parent tables in this type's inheritance chain, followed by any fields this type
     23introduces. Parent fields are duplicated so they can be changed (\CC
     24\lstinline[language=c++]|override|), so that references to the dispatched type
     25are 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
     34A virtual table is created when the virtual type is created. The name of the
     35type is created by mangling the name of the base type. The name of the instance
     36is also generated by name mangling.  The fields are initialized automatically.
    3937The parent field is initialized by getting the type of the parent field and
    4038using that to calculate the mangled name of the parent's virtual table type.
    4139There are two special fields that are included like normal fields but have
    4240special 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 
     41initialized with a @sizeof@ expression, the @align@ field is the type's
     42alignment and uses an @alignof@ expression. The remaining fields are resolved
     43to a name matching the field's name and type using the normal visibility and
     44overload resolution rules of the type system.
     45
     46These operations are split up into several groups depending on where they take
     47place which varies for monomorphic and polymorphic types. The first devision is
     48between the declarations and the definitions. Declarations, such as a function
     49signature or a aggregate's name, must always be visible but may be repeated in
     50the form of forward declarations in headers. Definitions, such as function
     51bodies and a aggregate's layout, can be separately compiled but must occur
     52exactly once in a source file.
     53
     54\begin{sloppypar}
    5655The declarations include the virtual type definition and forward declarations
    5756of 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
     58of the virtual table instance and the bodies of the three functions.
     59\end{sloppypar}
    6160
    6261Monomorphic instances put all of these two groups in one place each.
    63 
    64 Polymorphic instances also split out the core declarations and definitions
    65 from the per-instance information. The virtual table type and most of the
    66 functions are polymorphic so they are all part of the core. The virtual table
    67 instance and the @get_exception_vtable@ function.
    68 
     62Polymorphic instances also split out the core declarations and definitions from
     63the per-instance information. The virtual table type and most of the functions
     64are polymorphic so they are all part of the core. The virtual table instance
     65and the @get_exception_vtable@ function.
     66
     67\begin{sloppypar}
    6968Coroutines 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
     70data type is declared with @coroutine@ or @thread@ the forward declaration for
     71the instance is created as well. The definition of the virtual table is created
     72at the definition of the main function.
     73\end{sloppypar}
    7474
    7575\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.
     76Virtual casts are implemented as a function call that does the subtype check
     77and 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.
     80The function is
     81\begin{cfa}
     82void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent,
     83        struct __cfa__parent_vtable const * const * child );
     84}
     85\end{cfa}
     86and it is implemented in the standard library. It takes a pointer to the target
     87type's virtual table and the object pointer being cast. The function performs a
     88linear search starting at the object's virtual-table and walking through the
     89the parent pointers, checking to if it or any of its ancestors are the same as
     90the target-type virtual table-pointer.
     91
     92For the generated code, a forward declaration of the virtual works as follows.
     93There is a forward declaration of @__cfa__virtual_cast@ in every \CFA file so
     94it can just be used. The object argument is the expression being cast so that
     95is just placed in the argument list.
     96
     97To build the target type parameter, the compiler creates a mapping from
     98concrete type-name -- so for polymorphic types the parameters are filled in --
     99to virtual table address. Every virtual table declaration is added to the this
     100table; repeats are ignored unless they have conflicting definitions.  Note,
     101these declarations do not have to be in scope, but they should usually be
     102introduced as part of the type definition.
     103
     104\PAB{I do not understood all of \VRef{s:VirtualSystem}. I think you need to
     105write more to make it clear.}
     106
    99107
    100108\section{Exceptions}
    … …  
    106114% resumption doesn't as well.
    107115
    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
     120Stack unwinding is the process of removing stack frames (activations) from the
     121stack. On function entry and return, unwinding is handled directly by the code
     122embedded in the function. Usually, the stack-frame size is known statically
     123based on parameter and local variable declarations.  For dynamically-sized
     124local variables, a runtime computation is necessary to know the frame
     125size. Finally, a function's frame-size may change during execution as local
     126variables (static or dynamic sized) go in and out of scope.
     127Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
     128bumping the hardware stack-pointer up or down as needed.
     129
     130Unwinding across multiple stack frames is more complex because individual stack
     131management code associated with each frame is bypassed. That is, the location
     132of a function's frame-management code is largely unknown and dispersed
     133throughout the function, hence the current frame size managed by that code is
     134also unknown. Hence, code unwinding across frames does not have direct
     135knowledge about what is on the stack, and hence, how much of the stack needs to
     136be 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
     146The traditional unwinding mechanism for C is implemented by saving a snap-shot
     147of 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
     149reseting to a snap-shot of an arbitrary but existing function frame on the
     150stack. It is up to the programmer to ensure the snap-shot is valid when it is
     151reset, making this unwinding approach fragile with potential errors that are
     152difficult to debug because the stack becomes corrupted.
     153
     154However, many languages define cleanup actions that must be taken when objects
     155are deallocated from the stack or blocks end, such as running a variable's
     156destructor or a @try@ statement's @finally@ clause. Handling these mechanisms
     157requires walking the stack and checking each stack frame for these potential
     158actions.
     159
     160For exceptions, it must be possible to walk the stack frames in search of @try@
     161statements to match and execute a handler. For termination exceptions, it must
     162also be possible to unwind all stack frames from the throw to the matching
     163catch, and each of these frames must be checked for cleanup actions. Stack
     164walking is where most of the complexity and expense of exception handling
     165appears.
     166
     167One of the most popular tools for stack management is libunwind, a low-level
     168library that provides tools for stack walking, handler execution, and
     169unwinding. What follows is an overview of all the relevant features of
     170libunwind needed for this work, and how \CFA uses them to implement exception
     171handling.
     172
     173\subsection{libunwind Usage}
     174Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
     175provides \CC-style stack-unwinding. Its operation is divided into two phases:
     176search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
     177stack and decide where unwinding should stop (but no unwinding occurs). The
     178cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
     179
     180To use libunwind, each function must have a personality function and a Language
     181Specific Data Area (LSDA).  The LSDA has the unique information for each
     182function to tell the personality function where a function is executing, its
     183current stack frame, and what handlers should be checked.  Theoretically, the
     184LSDA can contain any information but conventionally it is a table with entries
     185representing regions of the function and what has to be done there during
     186unwinding. These regions are bracketed by the instruction pointer. If the
     187instruction pointer is within a region's start/end, then execution is currently
     188executing in that region. Regions are used to mark out the scopes of objects
     189with 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
     197The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
     198attaches its personality function. \PAB{to what is it attached?}  However, this
     199flag only handles the cleanup attribute
     200\begin{cfa}
     201void clean_up( int * var ) { ... }
     202int avar __attribute__(( __cleanup(clean_up) ));
     203\end{cfa}
     204which is used on a variable and specifies a function, \eg @clean_up@, run when
     205the variable goes out of scope. The function is passed a pointer to the object
     206so it can be used to mimic destructors. However, this feature cannot be used to
     207mimic @try@ statements.
     208
     209\subsection{Personality Functions}
     210Personality functions have a complex interface specified by libunwind.  This
     211section covers some of the important parts of the interface.
     212
     213A personality function performs four tasks, although not all have to be
     214present.
     215\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
     216typedef _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);
    161222\end{lstlisting}
    162 
    163 The return value, the reason code, is an enumeration of possible messages
     223The @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
     227to check for handlers.  If there is a handler in a stack frame, as defined by
     228the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
     229it return @_URC_CONTINUE_UNWIND@.
     230
     231\item
     232@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
     233unwound and all cleanup code is run. The personality function does whatever
     234cleanup the language defines (such as running destructors/finalizers) and then
     235generally 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
     240handler. The personality function must prepare to return to normal code
     241execution and return @_URC_INSTALL_CONTEXT@.
     242\end{sloppypar}
     243
     244\item
     245@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
     246the cleanup phase and uses a different means to decide when to stop
     247\see{\VRef{s:ForcedUnwind}}.
     248\end{enumerate}
     249
     250The @exception_class@ argument is a copy of the
     251\lstinline[language=C]|exception|'s @exception_class@ field.
     252
     253The \lstinline[language=C]|exception| argument is a pointer to the user
     254provided storage object. It has two public fields, the exception class, which
     255is actually just a number, identifying the exception handling mechanism that
     256created it, and the cleanup function. The cleanup function is called if
     257required by the exception.
     258
     259The @context@ argument is a pointer to an opaque type passed to helper
     260functions called inside the personality function.
     261
     262The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
    164263that can be passed several places in libunwind. It includes a number of
    165264messages for special cases (some of which should never be used by the
    … …  
    167266personality function should always return @_URC_CONTINUE_UNWIND@.
    168267
    169 The @version@ argument is the verson of the implementation that is
    170 calling the personality function. At this point it appears to always be 1 and
    171 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 personality
    174 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 personality
    178 function is called during the search phase. The personality function should
    179 decide if unwinding will stop in this function or not. If it does then the
    180 personality function should return @_URC_HANDLER_FOUND@.
    181 \item@_UA_CLEANUP_PHASE@: This flag is set whenever the personality
    182 function is called during the cleanup phase. If no other flags are set this
    183 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 phase
    185 on the function frame that found the handler. The personality function must
    186 prepare to return to normal code execution and return
    187 @_URC_INSTALL_CONTEXT@.
    188 \item@_UA_FORCE_UNWIND@: This flag is set if the personality function
    189 is called through a forced unwind call. Forced unwind only performs the
    190 cleanup phase and uses a different means to decide when to stop. See its
    191 section below.
    192 \end{itemize}
    193 
    194 The @exception_class@ argument is a copy of the @exception@'s
    195 @exception_class@ field.
    196 
    197 The @exception@ argument is a pointer to the user provided storage
    198 object. It has two public fields, the exception class which is actually just
    199 a number that identifies the exception handling mechanism that created it and
    200 the other is the clean-up function. The clean-up function is called if the
    201 exception needs to
    202 
    203 The @context@ argument is a pointer to an opaque type. This is passed
    204 to the many helper functions that can be called inside the personality
    205 function.
    206 
    207268\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}
     269Raising an exception is the central function of libunwind and it performs a
     270two-staged unwinding.
     271\begin{cfa}
    213272_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
     273\end{cfa}
     274First, the function begins the search phase, calling the personality function
     275of the most recent stack frame. It continues to call personality functions
     276traversing the stack from newest to oldest until a function finds a handler or
     277the end of the stack is reached. In the latter case, raise exception returns
     278@_URC_END_OF_STACK@.
     279
     280Second, when a handler is matched, raise exception continues onto the cleanup phase.
     281Once again, it calls the personality functions of each stack frame from newest
     282to oldest. This pass stops at the stack frame containing the matching handler.
     283If that personality function has not install a handler, it is an error.
     284
     285If an error is encountered, raise exception returns either
     286@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
     287error occurred.
     288
     289\subsection{Forced Unwind}
     290\label{s:ForcedUnwind}
     291Forced 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}
     296It also unwinds the stack but it does not use the search phase. Instead another
     297function, the stop function, is used to stop searching.  The exception is the
     298same as the one passed to raise exception. The extra arguments are the stop
     299function and the stop parameter. The stop function has a similar interface as a
     300personality function, except it is also passed the stop parameter.
     301\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
     302typedef _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@);
    214308\end{lstlisting}
    215309
    216 When called the function begins the search phase, calling the personality
    217 function of the most recent stack frame. It will continue to call personality
    218 functions traversing the stack new-to-old until a function finds a handler or
    219 the end of the stack is reached. In the latter case raise exception will
    220 return with @_URC_END_OF_STACK@.
    221 
    222 Once a handler has been found raise exception continues onto the the cleanup
    223 phase. Once again it will call the personality functins of each stack frame
    224 from newest to oldest. This pass will stop at the stack frame that found the
    225 handler last time, if that personality function does not install the handler
    226 it is an error.
    227 
    228 If an error is encountered raise exception will return either
    229 @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending
    230 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 it
    234 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 extra
    243 arguments are the stop function and the stop parameter. The stop function has
    244 a similar interface as a personality function, except it is also passed the
    245 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 
    257310The 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@.
     311function is called and then once more after all frames of the stack are
     312unwound.
     313
     314Each time it is called, the stop function should return @_URC_NO_REASON@ or
     315transfer control directly to other code outside of libunwind. The framework
     316does not provide any assistance here.
     317
     318\begin{sloppypar}
     319Its 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
     321called. Beyond the libunwind standard, both GCC and Clang add an extra action
     322on the last call at the end of the stack: @_UA_END_OF_STACK@.
     323\end{sloppypar}
    270324
    271325\section{Exception Context}
    272326% Should I have another independent section?
    273327% 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
     330The exception context is global storage used to maintain data across different
     331exception operations and to communicate among different components.
     332
     333Each stack must have its own exception context. In a sequential \CFA program,
     334there is only one stack with a single global exception-context. However, when
     335the library @libcfathread@ is linked, there are multiple stacks where each
     336needs its own exception context.
     337
     338General access to the exception context is provided by function
     339@this_exception_context@. For sequential execution, this function is defined as
     340a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
     341concurrent, it links with @libcfathread@, where this function is defined with a
     342strong 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
     348For coroutines, @this_exception_context@ accesses the exception context stored
     349at the base of the stack. For threads, @this_exception_context@ uses the
     350concurrency library to access the current stack of the thread or coroutine
     351being executed by the thread, and then accesses the exception context stored at
     352the base of this stack.
    303353
    304354\section{Termination}
    … …  
    306356% catches. Talk about GCC nested functions.
    307357
    308 Termination exceptions use libunwind quite heavily because it matches the
    309 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 to form the LSDA for try blocks or destructors.
     358Termination exceptions use libunwind heavily because it matches the intended
     359use from \CC exceptions closely. The main complication for \CFA is that the
     360compiler generates C code, making it very difficult to generate the assembly to
     361form the LSDA for try blocks or destructors.
    312362
    313363\subsection{Memory Management}
    314 The first step of termination is to copy the exception into memory managed by
    315 the exception system. Currently the system just uses malloc, without reserved
    316 memory or and ``small allocation" optimizations. The exception handling
    317 mechanism manages memory for the exception as well as memory for libunwind
    318 and the system's own per-exception storage.
    319 
    320 Exceptions are stored in variable sized block. The first component is a fixed
    321 sized data structure that contains the information for libunwind and the
    322 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 embedded
     364The first step of a termination raise is to copy the exception into memory
     365managed by the exception system. Currently, the system uses @malloc@, rather
     366than reserved memory or the stack top. The exception handling mechanism manages
     367memory for the exception as well as memory for libunwind and the system's own
     368per-exception storage.
     369
     370Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout
     371figure.} The first component is a fixed sized data structure that contains the
     372information for libunwind and the exception system. The second component is an
     373area of memory big enough to store the exception. Macros with pointer arthritic
     374and type cast are used to move between the components or go from the embedded
    325375@_Unwind_Exception@ to the entire node.
    326376
    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.
     377All of these nodes are linked together in a list, one list per stack, with the
     378list head stored in the exception context. Within each linked list, the most
     379recently thrown exception is at the head followed by older thrown
     380exceptions. This format allows exceptions to be thrown, while a different
     381exception is being handled. The exception at the head of the list is currently
     382being handled, while other exceptions wait for the exceptions before them to be
     383removed.
     384
     385The virtual members in the exception's virtual table provide the size of the
     386exception, the copy function, and the free function, so they are specific to an
     387exception type. The size and copy function are used immediately to copy an
     388exception into managed memory. After the exception is handled the free function
     389is used to clean up the exception and then the entire node is passed to free.
     390
     391\subsection{Try Statements and Catch Clauses}
     392The try statement with termination handlers is complex because it must
     393compensate for the lack of assembly-code generated from \CFA. Libunwind
     394requires an LSDA and personality function for control to unwind across a
     395function. The LSDA in particular is hard to mimic in generated C code.
     396
     397The workaround is a function called @__cfaehm_try_terminate@ in the standard
     398library. The contents of a try block and the termination handlers are converted
     399into functions. These are then passed to the try terminate function and it
     400calls them. This approach puts a try statement in its own functions so that no
     401function has to deal with both termination handlers and destructors. \PAB{I do
     402not understand the previous sentence.}
     403
     404This function has some custom embedded assembly that defines \emph{its}
     405personality function and LSDA. The assembly is created with handcrafted C @asm@
     406statements, which is why there is only one version of it. The personality
     407function is structured so that it can be expanded, but currently it only
     408handles this one function.  Notably, it does not handle any destructors so the
     409function is constructed so that it does need to run it. \PAB{I do not
     410understand the previous sentence.}
    362411
    363412The three functions passed to try terminate are:
    364 \begin{itemize}
    365 \item The try function: This function is the try block, all the code inside
    366 the try block is placed inside the try function. It takes no parameters and
    367 has no return value. This function is called during regular execution to run
    368 the try block.
    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 to be implemented with the cleanup attribute.
     413\begin{description}
     414\item[try function:] This function is the try block, all the code inside the
     415try block is placed inside the try function. It takes no parameters and has no
     416return value. This function is called during regular execution to run the try
     417block.
     418
     419\item[match function:] This function is called during the search phase and
     420decides if a catch clause matches the termination exception.  It is constructed
     421from the conditional part of each handler and runs each check, top to bottom,
     422in turn, first checking to see if the exception type matches and then if the
     423condition is true. It takes a pointer to the exception and returns 0 if the
     424exception is not handled here. Otherwise the return value is the id of the
     425handler that matches the exception.
     426
     427\item[handler function:] This function handles the exception. It takes a
     428pointer to the exception and the handler's id and returns nothing. It is called
     429after the cleanup phase.  It is constructed by stitching together the bodies of
     430each handler and dispatches to the selected handler.
     431\end{description}
     432All three functions are created with GCC nested functions. GCC nested functions
     433can be used to create closures, functions that can refer to the state of other
     434functions on the stack. This approach allows the functions to refer to all the
     435variables in scope for the function containing the @try@ statement.  These
     436nested functions and all other functions besides @__cfaehm_try_terminate@ in
     437\CFA use the GCC personality function and the @-fexceptions@ flag to generate
     438the LSDA. This allows destructors to be implemented with the cleanup attribute.
    390439
    391440\section{Resumption}
    392441% The stack-local data, the linked list of nodes.
    393442
    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
     443Resumption simple to implement because there is no stack unwinding. The
     444resumption raise uses a list of nodes for its stack traversal. The head of the
     445list is stored in the exception context. The nodes in the list have a pointer
    396446to the next node and a pointer to the handler function.
    397447
    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 returns
    400 true if the exception was handled and false otherwise.
    401 
    402 The handler function does both the matching and catching. It tries each
    403 the condition of @catchResume@ in order, top-to-bottom and until it
    404 finds a handler that matches. If no handler matches then the function returns
    405 false. Otherwise the matching handler is run, if it completes successfully
    406 the function returns true. Rethrows, through the @throwResume;@
    407 statement, cause the function to return true.
     448A resumption raise traverses this list. At each node the handler function is
     449called, passing the exception by pointer. It returns true if the exception is
     450handled and false otherwise.
     451
     452The handler function does both the matching and handling. It computes the
     453condition of each @catchResume@ in top-to-bottom order, until it finds a
     454handler that matches. If no handler matches then the function returns
     455false. Otherwise the matching handler is run; if it completes successfully, the
     456function returns true. Reresume, through the @throwResume;@ statement, cause
     457the function to return true.
    408458
    409459% 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.
     460Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack
     461already examined, is accomplished by updating the front of the list as the
     462search continues. Before the handler at a node is called the head of the list
     463is updated to the next node of the current node. After the search is complete,
     464successful or not, the head of the list is reset.
     465
     466This mechanism means the current handler and every handler that has already
     467been checked are not on the list while a handler is run. If a resumption is
     468thrown during the handling of another resumption the active handlers and all
     469the other handler checked up to this point are not checked again.
    419470
    420471This structure also supports new handler added while the resumption is being
    421472handled. 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.
     473stack -- the first one points over all the checked handlers -- and the ordering
     474is maintained.
     475
     476\label{p:zero-cost}
     477Note, the resumption implementation has a cost for entering/exiting a @try@
     478statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
     479clauses has zero-cost entry/exit. While resumption does not need the stack
     480unwinding and cleanup provided by libunwind, it could use the search phase to
     481providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
     482to return from a libunwind search without installing a handler or raising an
     483error.  Although workarounds might be possible, they are beyond the scope of
     484this thesis. The current resumption implementation has simplicity in its
     485favour.
    437486% Seriously, just compare the size of the two chapters and then consider
    438487% that unwind is required knowledge for that chapter.
    … …  
    440489\section{Finally}
    441490% 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.
     491Finally clauses is placed into a GCC nested-function with a unique name, and no
     492arguments or return values. This nested function is then set as the cleanup
     493function of an empty object that is declared at the beginning of a block placed
     494around the context of the associated @try@ statement.
    447495
    448496The 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 object
    450 is cleaned up, which runs the function that contains the finally code.
     497block. At completion, control exits the block and the empty object is cleaned
     498up, which runs the function that contains the finally code.
    451499
    452500\section{Cancellation}
    … …  
    454502
    455503Cancellation 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 which
    460 type of stack it is. Luckily the threads library stores the main thread
    461 pointer and the current thread pointer and every thread stores a pointer to
     504however it uses a different primary function @_Unwind_ForcedUnwind@.  Details
     505of its interface can be found in the \VRef{s:ForcedUnwind}.
     506
     507The first step of cancellation is to find the cancelled stack and its type:
     508coroutine or thread. Fortunately, the thread library stores the main thread
     509pointer and the current thread pointer, and every thread stores a pointer to
    462510its main coroutine and the coroutine it is currently executing.
    463511
    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.
     512The first check is if the current thread's main and current coroutine do not
     513match, implying a coroutine cancellation; otherwise, it is a thread
     514cancellation. Otherwise it is a main thread cancellation. \PAB{Previous
     515sentence does not make sense.}
     516
     517However, if the threading library is not linked, the sequential execution is on
     518the main stack. Hence, the entire check is skipped because the weak-symbol
     519function is loaded. Therefore, a main thread cancellation is unconditionally
     520performed.
     521
     522Regardless of how the stack is chosen, the stop function and parameter are
     523passed to the forced-unwind function. The general pattern of all three stop
     524functions is the same: they continue unwinding until the end of stack when they
     525do there primary work.
     526
     527For main stack cancellation, the transfer is just a program abort.
     528
     529For coroutine cancellation, the exception is stored on the coroutine's stack,
     530and the coroutine context switches to its last resumer. The rest is handled on
     531the backside of the resume, which check if the resumed coroutine is
     532cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
     533and a @CoroutineCancelled@ exception is constructed and loaded with the
     534cancelled exception. It is then resumed as a regular exception with the default
     535handler coming from the context of the resumption call.
     536
     537For thread cancellation, the exception is stored on the thread's main stack and
     538then context switched to the scheduler. The rest is handled by the thread
     539joiner. When the join is complete, the joiner checks if the joined thread is
     540cancelled. If cancelled, the exception is retrieved and the joined thread, and
     541a @ThreadCancelled@ exception is constructed and loaded with the cancelled
     542exception. The default handler is passed in as a function pointer. If it is
     543null (as it is for the auto-generated joins on destructor call), the default is
     544used, which is a program abort.
     545%; which gives the required handling on implicate join.

  • doc/theses/andrew_beach_MMath/unwinding.tex

    r4dcd5ea r7eb6eb5  
    182182control has returned to normal control flow.
    183183
    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  
    9191\hypersetup{
    9292    plainpages=false,       % needed if Roman numbers in frontpages
    93     unicode=false,          % non-Latin characters in Acrobat’s bookmarks
    94     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?
    9696    pdffitwindow=false,     % window fit to page when opened
    9797    pdfstartview={FitH},    % fits the width of the page to the window
    … …  
    164164\CFAStyle                                               % CFA code-style for all languages
    165165\lstset{language=CFA,basicstyle=\linespread{0.9}\tt}    % CFA default lnaguage
     166\newcommand{\PAB}[1]{{\color{blue}PAB: #1}}
    166167
    167168%======================================================================
    … …  
    188189\input{existing}
    189190\input{features}
    190 \input{unwinding}
     191\input{implement}
     192%\input{unwinding}
    191193\input{future}
    192194
Note: See TracChangeset for help on using the changeset viewer.