Ignore:
Timestamp:
Jan 29, 2021, 8:23:52 AM (9 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
arm-eh, jacob/cs343-translation, master, new-ast-unique-expr
Children:
5669d0b
Parents:
4dcd5ea
Message:

complete first proofread of Andrew's thesis

File:
1 edited

Legend:

Unmodified
Added
Removed
  • 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.
Note: See TracChangeset for help on using the changeset viewer.