Ignore:
Timestamp:
Mar 4, 2021, 7:40:25 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
77d601f
Parents:
342af53 (diff), a5040fe (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

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

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/implement.tex

    r342af53 r8e4aa05  
    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 \codeC{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 Type}
     16Virtual types only have one change to their structure, the addition of a
     17pointer to the virtual table. This is always the first field so that
     18if it is cast to a supertype the field's location is still known.
     19
     20This field is set as part of all new generated constructors.
     21\todo{They only come as part exceptions and don't work.}
     22After the object is created the field is constant.
     23
     24However it can be read from, internally it is just a regular field called
     25@virtual_table@. Dereferencing it gives the virtual table and access to the
     26type's virtual members.
     27
     28\subsection{Virtual Table}
     29Every time a virtual type is defined the new virtual table type must also be
     30defined.
     31
     32The unique instance is important because the address of the virtual table
     33instance is used as the identifier for the virtual type. So a pointer to the
     34virtual table and the ID for the virtual type are interchangable.
     35\todo{Unique instances might be going so we will have to talk about the new
     36system instead.}
     37
     38The first step in putting it all together is to create the virtual table type.
     39The virtual table type is just a structure and can be described in terms of
     40its fields. The first field is always the parent type ID (or a pointer to
     41the parent virtual table) or 0 (the null pointer).
     42Next are other fields on the parent virtual table are repeated.
     43Finally are the fields used to store any new virtual members of the new
     44The virtual type
     45
     46The virtual system is accessed through a private constant field inserted at the
     47beginning of every virtual type, called the virtual-table pointer. This field
     48points at a type's virtual table and is assigned during the object's
     49construction. The address of a virtual table acts as the unique identifier for
     50the virtual type, and the first field of a virtual table is a pointer to the
     51parent virtual-table or @0p@. The remaining fields are duplicated from the
     52parent tables in this type's inheritance chain, followed by any fields this type
     53introduces. Parent fields are duplicated so they can be changed (all virtual
     54members are overridable), so that references to the dispatched type
     55are replaced with the current virtual type.
     56% These are always taken by pointer or reference.
     57
     58% Simple ascii diragram:
     59\begin{verbatim}
     60parent_pointer  \
     61parent_field0   |
     62...             | Same layout as parent.
     63parent_fieldN   /
     64child_field0
     65...
     66child_fieldN
     67\end{verbatim}
     68\todo{Refine the diagram}
     69
     70% For each virtual type, a virtual table is constructed. This is both a new type
     71% and an instance of that type. Other instances of the type could be created
     72% but the system doesn't use them. So this section will go over the creation of
     73% the type and the instance.
     74
     75A virtual table is created when the virtual type is created. The name of the
     76type is created by mangling the name of the base type. The name of the instance
     77is also generated by name mangling. The fields are initialized automatically.
    3978The parent field is initialized by getting the type of the parent field and
    4079using that to calculate the mangled name of the parent's virtual table type.
    4180There are two special fields that are included like normal fields but have
    42 special initialization rules: the \codeC{size} field is the type's size and is
    43 initialized with a sizeof expression, the \codeC{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 
     81special initialization rules: the @size@ field is the type's size and is
     82initialized with a @sizeof@ expression, the @align@ field is the type's
     83alignment and uses an @alignof@ expression. The remaining fields are resolved
     84to a name matching the field's name and type using the normal visibility and
     85overload resolution rules of the type system.
     86
     87These operations are split up into several groups depending on where they take
     88place which varies for monomorphic and polymorphic types. The first devision is
     89between the declarations and the definitions. Declarations, such as a function
     90signature or a aggregate's name, must always be visible but may be repeated in
     91the form of forward declarations in headers. Definitions, such as function
     92bodies and a aggregate's layout, can be separately compiled but must occur
     93exactly once in a source file.
     94
     95\begin{sloppypar}
    5696The declarations include the virtual type definition and forward declarations
    5797of the virtual table instance, constructor, message function and
    58 \codeCFA{get_exception_vtable}. The definition includes the storage and
    59 initialization of the virtual table instance and the bodies of the three
    60 functions.
     98@get_exception_vtable@. The definition includes the storage and initialization
     99of the virtual table instance and the bodies of the three functions.
     100\end{sloppypar}
    61101
    62102Monomorphic 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 \codeCFA{get_exception_vtable} function.
    68 
    69 Coroutines and threads need instances of \codeCFA{CoroutineCancelled} and
    70 \codeCFA{ThreadCancelled} respectively to use all of their functionality.
    71 When a new data type is declared with \codeCFA{coroutine} or \codeCFA{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.
     103Polymorphic instances also split out the core declarations and definitions from
     104the per-instance information. The virtual table type and most of the functions
     105are polymorphic so they are all part of the core. The virtual table instance
     106and the @get_exception_vtable@ function.
     107
     108\begin{sloppypar}
     109Coroutines and threads need instances of @CoroutineCancelled@ and
     110@ThreadCancelled@ respectively to use all of their functionality. When a new
     111data type is declared with @coroutine@ or @thread@ the forward declaration for
     112the instance is created as well. The definition of the virtual table is created
     113at the definition of the main function.
     114\end{sloppypar}
    74115
    75116\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 \codeC{__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 \codeC{__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.
     117Virtual casts are implemented as a function call that does the subtype check
     118and a C coercion-cast to do the type conversion.
     119% The C-cast is just to make sure the generated code is correct so the rest of
     120% the section is about that function.
     121The function is
     122\begin{cfa}
     123void * __cfa__virtual_cast(
     124        struct __cfa__parent_vtable const * parent,
     125        struct __cfa__parent_vtable const * const * child );
     126\end{cfa}
     127and it is implemented in the standard library. The structure reperents the
     128head of a vtable which is the pointer to the parent virtual table. The
     129@parent@ points directly at the parent type virtual table while the @child@
     130points at the object of the (possibe) child type.
     131
     132In terms of the virtual cast expression, @parent@ comes from looking up the
     133type being cast to and @child@ is the result of the expression being cast.
     134Because the complier outputs C code, some type C type casts are also used.
     135The last bit of glue is an map that saves every virtual type the compiler
     136sees. This is used to check the type used in a virtual cast is a virtual
     137type and to get its virtual table.
     138(It also checks for conflicting definitions.)
     139
     140Inside the function it is a simple conditional. If the type repersented by
     141@parent@ is or is an ancestor of the type repersented by @*child@ (it
     142requires one more level of derefence to pass through the object) then @child@
     143is returned, otherwise the null pointer is returned.
     144
     145The check itself is preformed is a simple linear search. If the child
     146virtual table or any of its ancestors (which are retreved through the first
     147field of every virtual table) are the same as the parent virtual table then
     148the cast succeeds.
    99149
    100150\section{Exceptions}
    … …  
    106156% resumption doesn't as well.
    107157
    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 \codeC{setjmp} \& \codeC{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 \texttt{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 \texttt{-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);
     158% Many modern languages work with an interal stack that function push and pop
     159% their local data to. Stack unwinding removes large sections of the stack,
     160% often across functions.
     161
     162Stack unwinding is the process of removing stack frames (activations) from the
     163stack. On function entry and return, unwinding is handled directly by the code
     164embedded in the function. Usually, the stack-frame size is known statically
     165based on parameter and local variable declarations. For dynamically-sized
     166local variables, a runtime computation is necessary to know the frame
     167size. Finally, a function's frame-size may change during execution as local
     168variables (static or dynamic sized) go in and out of scope.
     169Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
     170bumping the hardware stack-pointer up or down as needed.
     171
     172Unwinding across multiple stack frames is more complex because individual stack
     173management code associated with each frame is bypassed. That is, the location
     174of a function's frame-management code is largely unknown and dispersed
     175throughout the function, hence the current frame size managed by that code is
     176also unknown. Hence, code unwinding across frames does not have direct
     177knowledge about what is on the stack, and hence, how much of the stack needs to
     178be removed.
     179
     180% At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply
     181% move the top of the stack, discarding everything on the stack above a certain
     182% point. However this ignores all the cleanup code that should be run when
     183% certain sections of the stack are removed (for \CFA these are from destructors
     184% and finally clauses) and also requires that the point to which the stack is
     185% being unwound is known ahead of time. libunwind is used to address both of
     186% these problems.
     187
     188The traditional unwinding mechanism for C is implemented by saving a snap-shot
     189of a function's state with @setjmp@ and restoring that snap-shot with
     190@longjmp@. This approach bypasses the need to know stack details by simply
     191reseting to a snap-shot of an arbitrary but existing function frame on the
     192stack. It is up to the programmer to ensure the snap-shot is valid when it is
     193reset, making this unwinding approach fragile with potential errors that are
     194difficult to debug because the stack becomes corrupted.
     195
     196However, many languages define cleanup actions that must be taken when objects
     197are deallocated from the stack or blocks end, such as running a variable's
     198destructor or a @try@ statement's @finally@ clause. Handling these mechanisms
     199requires walking the stack and checking each stack frame for these potential
     200actions.
     201
     202For exceptions, it must be possible to walk the stack frames in search of @try@
     203statements to match and execute a handler. For termination exceptions, it must
     204also be possible to unwind all stack frames from the throw to the matching
     205catch, and each of these frames must be checked for cleanup actions. Stack
     206walking is where most of the complexity and expense of exception handling
     207appears.
     208
     209One of the most popular tools for stack management is libunwind, a low-level
     210library that provides tools for stack walking, handler execution, and
     211unwinding. What follows is an overview of all the relevant features of
     212libunwind needed for this work, and how \CFA uses them to implement exception
     213handling.
     214
     215\subsection{libunwind Usage}
     216Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
     217provides \CC-style stack-unwinding. Its operation is divided into two phases:
     218search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
     219stack and decide where unwinding should stop (but no unwinding occurs). The
     220cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
     221
     222To use libunwind, each function must have a personality function and a Language
     223Specific Data Area (LSDA). The LSDA has the unique information for each
     224function to tell the personality function where a function is executing, its
     225current stack frame, and what handlers should be checked. Theoretically, the
     226LSDA can contain any information but conventionally it is a table with entries
     227representing regions of the function and what has to be done there during
     228unwinding. These regions are bracketed by the instruction pointer. If the
     229instruction pointer is within a region's start/end, then execution is currently
     230executing in that region. Regions are used to mark out the scopes of objects
     231with destructors and try blocks.
     232
     233% Libunwind actually does very little, it simply moves down the stack from
     234% function to function. Most of the actions are implemented by the personality
     235% function which libunwind calls on every function. Since this is shared across
     236% many functions or even every function in a language it will need a bit more
     237% information.
     238
     239The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
     240attaches its personality function. However, this
     241flag only handles the cleanup attribute:
     242\todo{Peter: What is attached? Andrew: It uses the .cfi\_personality directive
     243and that's all I know.}
     244\begin{cfa}
     245void clean_up( int * var ) { ... }
     246int avar __attribute__(( cleanup(clean_up) ));
     247\end{cfa}
     248which is used on a variable and specifies a function, in this case @clean_up@,
     249run when the variable goes out of scope.
     250The function is passed a pointer to the object being removed from the stack
     251so it can be used to mimic destructors.
     252However, this feature cannot be used to mimic @try@ statements as it cannot
     253control the unwinding.
     254
     255\subsection{Personality Functions}
     256Personality functions have a complex interface specified by libunwind. This
     257section covers some of the important parts of the interface.
     258
     259A personality function can preform different actions depending on how it is
     260called.
     261\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
     262typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) (
     263        _Unwind_Action @action@,
     264        _Unwind_Exception_Class @exception_class@,
     265        _Unwind_Exception * @exception@,
     266        struct _Unwind_Context * @context@
     267);
    161268\end{lstlisting}
    162 
    163 The return value, the reason code, is an enumeration of possible messages
     269The @action@ argument is a bitmask of possible actions:
     270\begin{enumerate}
     271\item
     272@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
     273to check for handlers. If there is a handler in a stack frame, as defined by
     274the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
     275it return @_URC_CONTINUE_UNWIND@.
     276
     277\item
     278@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
     279unwound and all cleanup code is run. The personality function does whatever
     280cleanup the language defines (such as running destructors/finalizers) and then
     281generally returns @_URC_CONTINUE_UNWIND@.
     282
     283\item
     284\begin{sloppypar}
     285@_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a
     286handler. The personality function must prepare to return to normal code
     287execution and return @_URC_INSTALL_CONTEXT@.
     288\end{sloppypar}
     289
     290\item
     291@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
     292the cleanup phase and uses a different means to decide when to stop
     293\see{\VRef{s:ForcedUnwind}}.
     294\end{enumerate}
     295
     296The @exception_class@ argument is a copy of the
     297\lstinline[language=C]|exception|'s @exception_class@ field.
     298
     299The \lstinline[language=C]|exception| argument is a pointer to the user
     300provided storage object. It has two public fields, the exception class, which
     301is actually just a number, identifying the exception handling mechanism that
     302created it, and the cleanup function. The cleanup function is called if
     303required by the exception.
     304
     305The @context@ argument is a pointer to an opaque type passed to helper
     306functions called inside the personality function.
     307
     308The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
    164309that can be passed several places in libunwind. It includes a number of
    165310messages for special cases (some of which should never be used by the
    166311personality function) and error codes but unless otherwise noted the
    167 personality function should always return \codeC{_URC_CONTINUE_UNWIND}.
    168 
    169 The \codeC{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 \codeC{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\codeC{_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 \codeC{_URC_HANDLER_FOUND}.
    181 \item\codeC{_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\codeC{_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 \codeC{_URC_INSTALL_CONTEXT}.
    188 \item\codeC{_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 \codeC{exception_class} argument is a copy of the \codeC{exception}'s
    195 \codeC{exception_class} field.
    196 
    197 The \codeC{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 \codeC{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.
     312personality function should always return @_URC_CONTINUE_UNWIND@.
    206313
    207314\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}
     315Raising an exception is the central function of libunwind and it performs a
     316two-staged unwinding.
     317\begin{cfa}
    213318_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
     319\end{cfa}
     320First, the function begins the search phase, calling the personality function
     321of the most recent stack frame. It continues to call personality functions
     322traversing the stack from newest to oldest until a function finds a handler or
     323the end of the stack is reached. In the latter case, raise exception returns
     324@_URC_END_OF_STACK@.
     325
     326Second, when a handler is matched, raise exception continues onto the cleanup
     327phase.
     328Once again, it calls the personality functions of each stack frame from newest
     329to oldest. This pass stops at the stack frame containing the matching handler.
     330If that personality function has not install a handler, it is an error.
     331
     332If an error is encountered, raise exception returns either
     333@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
     334error occurred.
     335
     336\subsection{Forced Unwind}
     337\label{s:ForcedUnwind}
     338Forced Unwind is the other central function in libunwind.
     339\begin{cfa}
     340_Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *,
     341        _Unwind_Stop_Fn, void *);
     342\end{cfa}
     343It also unwinds the stack but it does not use the search phase. Instead another
     344function, the stop function, is used to stop searching. The exception is the
     345same as the one passed to raise exception. The extra arguments are the stop
     346function and the stop parameter. The stop function has a similar interface as a
     347personality function, except it is also passed the stop parameter.
     348\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
     349typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)(
     350        _Unwind_Action @action@,
     351        _Unwind_Exception_Class @exception_class@,
     352        _Unwind_Exception * @exception@,
     353        struct _Unwind_Context * @context@,
     354        void * @stop_parameter@);
    214355\end{lstlisting}
    215356
    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 \codeC{_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 \codeC{_URC_FATAL_PHASE1_ERROR} or \codeC{_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 
    257357The 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 \codeC{_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 \codeC{_UA_CLEANUP_PHASE} and \codeC{_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 \codeC{_UA_END_OF_STACK}.
     358function is called and then once more after all frames of the stack are
     359unwound.
     360
     361Each time it is called, the stop function should return @_URC_NO_REASON@ or
     362transfer control directly to other code outside of libunwind. The framework
     363does not provide any assistance here.
     364
     365\begin{sloppypar}
     366Its arguments are the same as the paired personality function. The actions
     367@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
     368called. Beyond the libunwind standard, both GCC and Clang add an extra action
     369on the last call at the end of the stack: @_UA_END_OF_STACK@.
     370\end{sloppypar}
    270371
    271372\section{Exception Context}
    272373% Should I have another independent section?
    273374% 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 \texttt{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 \codeC{this_exception_context}. The main exception handling code is in
    287 \texttt{libcfa} and that library also defines the function as a weak symbol
    288 so it acts as a default. Meanwhile in \texttt{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 \texttt{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 \texttt{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 \codeC{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.
     375% stored changes depending on whether or not the thread-library is linked.
     376
     377The exception context is global storage used to maintain data across different
     378exception operations and to communicate among different components.
     379
     380Each stack must have its own exception context. In a sequential \CFA program,
     381there is only one stack with a single global exception-context. However, when
     382the library @libcfathread@ is linked, there are multiple stacks where each
     383needs its own exception context.
     384
     385General access to the exception context is provided by function
     386@this_exception_context@. For sequential execution, this function is defined as
     387a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
     388concurrent, it links with @libcfathread@, where this function is defined with a
     389strong symbol replacing the sequential version.
     390
     391The sequential @this_exception_context@ returns a hard-coded pointer to the
     392global execption context.
     393The concurrent version adds the exception context to the data stored at the
     394base of each stack. When @this_exception_context@ is called it retrieves the
     395active stack and returns the address of the context saved there.
    303396
    304397\section{Termination}
    … …  
    306399% catches. Talk about GCC nested functions.
    307400
    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.
     401Termination exceptions use libunwind heavily because it matches the intended
     402use from \CC exceptions closely. The main complication for \CFA is that the
     403compiler generates C code, making it very difficult to generate the assembly to
     404form the LSDA for try blocks or destructors.
    312405
    313406\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
    325 \codeC{_Unwind_Exception} to the entire node.
    326 
    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 \codeC{__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.
     407The first step of a termination raise is to copy the exception into memory
     408managed by the exception system. Currently, the system uses @malloc@, rather
     409than reserved memory or the stack top. The exception handling mechanism manages
     410memory for the exception as well as memory for libunwind and the system's own
     411per-exception storage.
     412
     413[Quick ASCII diagram to get started.]
     414\begin{verbatim}
     415Fixed Header  | _Unwind_Exception   <- pointer target
     416              |
     417              | Cforall storage
     418              |
     419Variable Body | the exception       <- fixed offset
     420              V ...
     421\end{verbatim}
     422
     423Exceptions are stored in variable-sized blocks.
     424The first component is a fixed sized data structure that contains the
     425information for libunwind and the exception system. The second component is an
     426area of memory big enough to store the exception. Macros with pointer arthritic
     427and type cast are used to move between the components or go from the embedded
     428@_Unwind_Exception@ to the entire node.
     429
     430All of these nodes are linked together in a list, one list per stack, with the
     431list head stored in the exception context. Within each linked list, the most
     432recently thrown exception is at the head followed by older thrown
     433exceptions. This format allows exceptions to be thrown, while a different
     434exception is being handled. The exception at the head of the list is currently
     435being handled, while other exceptions wait for the exceptions before them to be
     436removed.
     437
     438The virtual members in the exception's virtual table provide the size of the
     439exception, the copy function, and the free function, so they are specific to an
     440exception type. The size and copy function are used immediately to copy an
     441exception into managed memory. After the exception is handled the free function
     442is used to clean up the exception and then the entire node is passed to free
     443so the memory can be given back to the heap.
     444
     445\subsection{Try Statements and Catch Clauses}
     446The try statement with termination handlers is complex because it must
     447compensate for the lack of assembly-code generated from \CFA. Libunwind
     448requires an LSDA and personality function for control to unwind across a
     449function. The LSDA in particular is hard to mimic in generated C code.
     450
     451The workaround is a function called @__cfaehm_try_terminate@ in the standard
     452library. The contents of a try block and the termination handlers are converted
     453into functions. These are then passed to the try terminate function and it
     454calls them.
     455Because this function is known and fixed (and not an arbitrary function that
     456happens to contain a try statement) this means the LSDA can be generated ahead
     457of time.
     458
     459Both the LSDA and the personality function are set ahead of time using
     460embedded assembly. This is handcrafted using C @asm@ statements and contains
     461enough information for the single try statement the function repersents.
    362462
    363463The 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 \codeC{__cfaehm_try_terminate} in \CFA use the GCC personality function and
    388 the \texttt{-fexceptions} flag to generate the LSDA. This allows destructors
    389 to be implemented with the cleanup attribute.
     464\begin{description}
     465\item[try function:] This function is the try block, all the code inside the
     466try block is placed inside the try function. It takes no parameters and has no
     467return value. This function is called during regular execution to run the try
     468block.
     469
     470\item[match function:] This function is called during the search phase and
     471decides if a catch clause matches the termination exception. It is constructed
     472from the conditional part of each handler and runs each check, top to bottom,
     473in turn, first checking to see if the exception type matches and then if the
     474condition is true. It takes a pointer to the exception and returns 0 if the
     475exception is not handled here. Otherwise the return value is the id of the
     476handler that matches the exception.
     477
     478\item[handler function:] This function handles the exception. It takes a
     479pointer to the exception and the handler's id and returns nothing. It is called
     480after the cleanup phase. It is constructed by stitching together the bodies of
     481each handler and dispatches to the selected handler.
     482\end{description}
     483All three functions are created with GCC nested functions. GCC nested functions
     484can be used to create closures, functions that can refer to the state of other
     485functions on the stack. This approach allows the functions to refer to all the
     486variables in scope for the function containing the @try@ statement. These
     487nested functions and all other functions besides @__cfaehm_try_terminate@ in
     488\CFA use the GCC personality function and the @-fexceptions@ flag to generate
     489the LSDA. This allows destructors to be implemented with the cleanup attribute.
    390490
    391491\section{Resumption}
    392492% The stack-local data, the linked list of nodes.
    393493
    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
     494Resumption simple to implement because there is no stack unwinding. The
     495resumption raise uses a list of nodes for its stack traversal. The head of the
     496list is stored in the exception context. The nodes in the list have a pointer
    396497to the next node and a pointer to the handler function.
    397498
    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 \codeCFA{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 \codeCFA{throwResume;}
    407 statement, cause the function to return true.
    408 
    409 \subsection{Libunwind Compatibility}
    410 Resumption does not use libunwind for two simple reasons. The first is that
    411 it does not have to unwind anything so would never need to use the clean-up
    412 phase. Still the search phase could be used to make it free to enter or exit
    413 a try statement with resumption handlers in the same way termination handlers
    414 are for the same trade off in the cost of the throw. This is where the second
    415 reason comes in, there is no way to return from a search without installing
    416 a handler or raising an error.
    417 
    418 Although work arounds could be created none seemed to be worth it for the
    419 prototype. This implementation has no difference in behaviour and is much
    420 simpler.
     499A resumption raise traverses this list. At each node the handler function is
     500called, passing the exception by pointer. It returns true if the exception is
     501handled and false otherwise.
     502
     503The handler function does both the matching and handling. It computes the
     504condition of each @catchResume@ in top-to-bottom order, until it finds a
     505handler that matches. If no handler matches then the function returns
     506false. Otherwise the matching handler is run; if it completes successfully, the
     507function returns true. Rethrowing, through the @throwResume;@ statement,
     508causes the function to return true.
     509
     510% Recursive Resumption Stuff:
     511Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack
     512already examined, is accomplished by updating the front of the list as the
     513search continues. Before the handler at a node is called the head of the list
     514is updated to the next node of the current node. After the search is complete,
     515successful or not, the head of the list is reset.
     516
     517This mechanism means the current handler and every handler that has already
     518been checked are not on the list while a handler is run. If a resumption is
     519thrown during the handling of another resumption the active handlers and all
     520the other handler checked up to this point are not checked again.
     521
     522This structure also supports new handler added while the resumption is being
     523handled. These are added to the front of the list, pointing back along the
     524stack -- the first one points over all the checked handlers -- and the ordering
     525is maintained.
     526
     527\label{p:zero-cost}
     528Note, the resumption implementation has a cost for entering/exiting a @try@
     529statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
     530clauses has zero-cost entry/exit. While resumption does not need the stack
     531unwinding and cleanup provided by libunwind, it could use the search phase to
     532providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
     533to return from a libunwind search without installing a handler or raising an
     534error. Although workarounds might be possible, they are beyond the scope of
     535this thesis. The current resumption implementation has simplicity in its
     536favour.
    421537% Seriously, just compare the size of the two chapters and then consider
    422538% that unwind is required knowledge for that chapter.
    … …  
    424540\section{Finally}
    425541% Uses destructors and GCC nested functions.
    426 Finally clauses are a simple decomposition to some of the existing features.
    427 The code in the block is placed into a GCC nested function with a unique name,
    428 no arguments or return values. This nested function is then set as the
    429 clean-up function of an empty object that is declared at the beginning of a
    430 block placed around the contexts of the try statement.
     542Finally clauses is placed into a GCC nested-function with a unique name, and no
     543arguments or return values. This nested function is then set as the cleanup
     544function of an empty object that is declared at the beginning of a block placed
     545around the context of the associated @try@ statement.
    431546
    432547The rest is handled by GCC. The try block and all handlers are inside the
    433 block. When they are complete control exits the block and the empty object
    434 is cleaned up, which runs the function that contains the finally code.
     548block. At completion, control exits the block and the empty object is cleaned
     549up, which runs the function that contains the finally code.
    435550
    436551\section{Cancellation}
    … …  
    438553
    439554Cancellation also uses libunwind to do its stack traversal and unwinding,
    440 however it uses a different primary function \codeC{_Unwind_ForcedUnwind}.
    441 Details of its interface can be found in the unwind section.
    442 
    443 The first step of cancellation is to find the stack was cancelled and which
    444 type of stack it is. Luckily the threads library stores the main thread
    445 pointer and the current thread pointer and every thread stores a pointer to
     555however it uses a different primary function @_Unwind_ForcedUnwind@. Details
     556of its interface can be found in the \VRef{s:ForcedUnwind}.
     557
     558The first step of cancellation is to find the cancelled stack and its type:
     559coroutine or thread. Fortunately, the thread library stores the main thread
     560pointer and the current thread pointer, and every thread stores a pointer to
    446561its main coroutine and the coroutine it is currently executing.
    447562
    448 So if the the current thread's main and current coroutine do not match, it is
    449 a coroutine cancellation. Otherwise if the main and current thread do not
    450 match, it is a thread cancellation. Otherwise it is a main thread
    451 cancellation.
    452 
    453 However if the threading library is not linked then execution must be on the
    454 main stack as that is the only one that exists. So the entire check is skipped
    455 using the linker and weak symbols. Instead the main thread cancellation is
    456 unconditionally preformed.
    457 
    458 Regardless of how they are choosen afterwords the stop function and the stop
    459 parameter are passed to the forced unwind functon. The general pattern of all
    460 three stop functions is the same, they continue unwinding until the end of
    461 stack when they do there primary work.
    462 
    463 Main stack cancellation it is very simple. The ``transfer" is just an abort,
    464 the program stops executing.
    465 
    466 The coroutine cancellation stores the exception on the coroutine and then
    467 does a coroutine context switch. The rest is handled inside resume. Every time
    468 control returns from a resumed thread there is a check to see if it is
    469 cancelled. If it is the exception is retrieved and the CoroutineCancelled
    470 exception is constructed and loaded. It is then thrown as a regular exception
    471 with the default handler coming from the context of the resumption call.
    472 
    473 The thread cancellation stores the exception on the thread's main stack and
    474 then returns to the scheduler. The rest is handled by the joiner. The wait
    475 for the joined thread to finish works the same but after that it checks
    476 to see if there was a cancellation. If there was the exception is retrieved
    477 and the ThreadCancelled exception is constructed. The default handler is
    478 passed in as a function pointer. If it is null (as it is for the
    479 auto-generated joins on destructor call) it a default is used that simply
    480 calls abort; which gives the required handling on implicate join.
     563So if the active thread's main and current coroutine are the same. If they
     564are then the current stack is a thread stack, otherwise it is a coroutine
     565stack. If it is a thread stack then an equality check with the stored main
     566thread pointer and current thread pointer is enough to tell if the current
     567thread is the main thread or not.
     568
     569However, if the threading library is not linked, the sequential execution is on
     570the main stack. Hence, the entire check is skipped because the weak-symbol
     571function is loaded. Therefore, a main thread cancellation is unconditionally
     572performed.
     573
     574Regardless of how the stack is chosen, the stop function and parameter are
     575passed to the forced-unwind function. The general pattern of all three stop
     576functions is the same: they continue unwinding until the end of stack when they
     577do there primary work.
     578
     579For main stack cancellation, the transfer is just a program abort.
     580
     581For coroutine cancellation, the exception is stored on the coroutine's stack,
     582and the coroutine context switches to its last resumer. The rest is handled on
     583the backside of the resume, which check if the resumed coroutine is
     584cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
     585and a @CoroutineCancelled@ exception is constructed and loaded with the
     586cancelled exception. It is then resumed as a regular exception with the default
     587handler coming from the context of the resumption call.
     588
     589For thread cancellation, the exception is stored on the thread's main stack and
     590then context switched to the scheduler. The rest is handled by the thread
     591joiner. When the join is complete, the joiner checks if the joined thread is
     592cancelled. If cancelled, the exception is retrieved and the joined thread, and
     593a @ThreadCancelled@ exception is constructed and loaded with the cancelled
     594exception. The default handler is passed in as a function pointer. If it is
     595null (as it is for the auto-generated joins on destructor call), the default is
     596used, which is a program abort.
     597%; which gives the required handling on implicate join.
Note: See TracChangeset for help on using the changeset viewer.