Ignore:
Timestamp:
May 21, 2021, 4:48:10 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:
f1bce515
Parents:
5407cdc (diff), 7404cdc (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

    r5407cdc r8d66610  
    99% Virtual table rules. Virtual tables, the pointer to them and the cast.
    1010While the \CFA virtual system currently has only one public feature, virtual
    11 cast \see{\VPageref{p:VirtualCast}}, substantial structure is required to
    12 support it, and provide features for exception handling and the standard
    13 library.
     11cast (see the virtual cast feature \vpageref{p:VirtualCast}),
     12substantial structure is required to support it,
     13and provide features for exception handling and the standard library.
    1414
    1515\subsection{Virtual Type}
    16 Virtual types only have one change to their structure, the addition of a
    17 pointer to the virtual table. This is always the first field so that
    18 if it is cast to a supertype the field's location is still known.
    19 
    20 This field is set as part of all new generated constructors.
    21 \todo{They only come as part exceptions and don't work.}
    22 After the object is created the field is constant.
    23 
    24 However 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
    26 type's virtual members.
     16Virtual types only have one change to their structure: the addition of a
     17pointer to the virtual table, which is called the \emph{virtual-table pointer}.
     18Internally, the field is called @virtual_table@.
     19The field is fixed after construction. It is always the first field in the
     20structure so that its location is always known.
     21\todo{Talk about constructors for virtual types (after they are working).}
     22
     23This is what binds an instance of a virtual type to a virtual table. This
     24pointer can be used as an identity check. It can also be used to access the
     25virtual table and the virtual members there.
     26
     27\subsection{Type Id}
     28Every virtual type has a unique id.
     29Type ids can be compared for equality (the types reperented are the same)
     30or used to access the type's type information.
     31The type information currently is only the parent's type id or, if the
     32type has no parent, zero.
     33
     34The id's are implemented as pointers to the type's type information instance.
     35Derefencing the pointer gets the type information.
     36By going back-and-forth between the type id and
     37the type info one can find every ancestor of a virtual type.
     38It also pushes the issue of creating a unique value (for
     39the type id) to the problem of creating a unique instance (for type
     40information) which the linker can solve.
     41
     42Advanced linker support is required because there is no place that appears
     43only once to attach the type information to. There should be one structure
     44definition but it is included in multiple translation units. Each virtual
     45table definition should be unique but there are an arbitrary number of thoses.
     46So the special section prefix \texttt{.gnu.linkonce} is used.
     47With a unique suffix (making the entire section name unique) the linker will
     48remove multiple definition making sure only one version exists after linking.
     49Then it is just a matter of making sure there is a unique name for each type.
     50
     51This is done in three phases.
     52The first phase is to generate a new structure definition to store the type
     53information. The layout is the same in each case, just the parent's type id,
     54but the types are changed.
     55The structure's name is change, it is based off the virtual type's name, and
     56the type of the parent's type id.
     57If the virtual type is polymorphic then the type information structure is
     58polymorphic as well, with the same polymorphic arguments.
     59
     60The second phase is to generate an instance of the type information with a
     61almost unique name, generated by mangling the virtual type name.
     62
     63The third phase is implicit with \CFA's overloading scheme. \CFA mangles
     64names with type information so that all of the symbols exported to the linker
     65are unique even if in \CFA code they are the same. Having two declarations
     66with the same name and same type is forbidden because it is impossible for
     67overload resolution to pick between them. This is why a unique type is
     68generated for each virtual type.
     69Polymorphic information is included in this mangling so polymorphic
     70types will have seperate instances for each set of polymorphic arguments.
     71
     72\begin{cfa}
     73struct TYPE_ID_TYPE {
     74        PARENT_ID_TYPE const * parent;
     75};
     76
     77__attribute__((cfa_linkonce))
     78TYPE_ID_TYPE const TYPE_ID_NAME = {
     79        &PARENT_ID_NAME,
     80};
     81\end{cfa}
     82
     83\subsubsection{cfa\_linkonce Attribute}
     84Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}.
     85This attribute can be put on an object or function definition
     86(any global declaration with a name and a type).
     87This allows you to define that object or function multiple times.
     88All definitions should have the link-once attribute on them and all should
     89be identical.
     90
     91The simplist way to use it is to put a definition in a header where the
     92forward declaration would usually go.
     93This is how it is used for type-id instances. There was is no unique location
     94associated with a type except for the type definition which is in a header.
     95This allows the unique type-id object to be generated there.
     96
     97Internally @cfa_linkonce@ removes all @section@ attributes
     98from the declaration (as well as itself) and replaces them with
     99@section(".gnu.linkonce.NAME")@ where \texttt{NAME} is replaced by the
     100mangled name of the object.
     101The prefix \texttt{.gnu.linkonce} in section names is recognized by the
     102linker. If two of these sections with the same name, including everything
     103that comes after the special prefix, then only one will be used and the other
     104will be discarded.
    27105
    28106\subsection{Virtual Table}
    29 Every time a virtual type is defined the new virtual table type must also be
    30 defined.
    31 
    32 The unique instance is important because the address of the virtual table
    33 instance is used as the identifier for the virtual type. So a pointer to the
    34 virtual 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
    36 system instead.}
    37 
    38 The first step in putting it all together is to create the virtual table type.
    39 The virtual table type is just a structure and can be described in terms of
    40 its fields. The first field is always the parent type ID (or a pointer to
    41 the parent virtual table) or 0 (the null pointer).
    42 Next are other fields on the parent virtual table are repeated.
    43 Finally are the fields used to store any new virtual members of the new
    44 The virtual type
    45 
    46 The virtual system is accessed through a private constant field inserted at the
    47 beginning of every virtual type, called the virtual-table pointer. This field
    48 points at a type's virtual table and is assigned during the object's
    49 construction. The address of a virtual table acts as the unique identifier for
    50 the virtual type, and the first field of a virtual table is a pointer to the
    51 parent virtual-table or @0p@. The remaining fields are duplicated from the
    52 parent tables in this type's inheritance chain, followed by any fields this type
    53 introduces. Parent fields are duplicated so they can be changed (all virtual
    54 members are overridable), so that references to the dispatched type
    55 are replaced with the current virtual type.
    56 % These are always taken by pointer or reference.
    57 
    58 % Simple ascii diragram:
    59 \begin{verbatim}
    60 parent_pointer  \
    61 parent_field0   |
    62 ...             | Same layout as parent.
    63 parent_fieldN   /
     107Each virtual type has a virtual table type that stores its type id and
     108virtual members.
     109Each virtual type instance is bound to a table instance that is filled with
     110the values of virtual members.
     111Both the layout of the fields and their value are decided by the rules given
     112below.
     113
     114The layout always comes in three parts.
     115The first section is just the type id at the head of the table. It is always
     116there to ensure that
     117The second section are all the virtual members of the parent, in the same
     118order as they appear in the parent's virtual table. Note that the type may
     119change slightly as references to the ``this" will change. This is limited to
     120inside pointers/references and via function pointers so that the size (and
     121hence the offsets) are the same.
     122The third section is similar to the second except that it is the new virtual
     123members introduced at this level in the hierarchy.
     124
     125\begin{figure}
     126\begin{cfa}
     127type_id
     128parent_field0
     129...
     130parent_fieldN
    64131child_field0
    65132...
    66133child_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 
    75 A virtual table is created when the virtual type is created. The name of the
    76 type is created by mangling the name of the base type. The name of the instance
    77 is also generated by name mangling. The fields are initialized automatically.
    78 The parent field is initialized by getting the type of the parent field and
    79 using that to calculate the mangled name of the parent's virtual table type.
    80 There are two special fields that are included like normal fields but have
    81 special initialization rules: the @size@ field is the type's size and is
    82 initialized with a @sizeof@ expression, the @align@ field is the type's
    83 alignment and uses an @alignof@ expression. The remaining fields are resolved
    84 to a name matching the field's name and type using the normal visibility and
    85 overload resolution rules of the type system.
    86 
    87 These operations are split up into several groups depending on where they take
    88 place which varies for monomorphic and polymorphic types. The first devision is
    89 between the declarations and the definitions. Declarations, such as a function
    90 signature or a aggregate's name, must always be visible but may be repeated in
    91 the form of forward declarations in headers. Definitions, such as function
    92 bodies and a aggregate's layout, can be separately compiled but must occur
    93 exactly once in a source file.
    94 
    95 \begin{sloppypar}
    96 The declarations include the virtual type definition and forward declarations
    97 of the virtual table instance, constructor, message function and
    98 @get_exception_vtable@. The definition includes the storage and initialization
    99 of the virtual table instance and the bodies of the three functions.
    100 \end{sloppypar}
    101 
    102 Monomorphic instances put all of these two groups in one place each.
    103 Polymorphic instances also split out the core declarations and definitions from
    104 the per-instance information. The virtual table type and most of the functions
    105 are polymorphic so they are all part of the core. The virtual table instance
    106 and the @get_exception_vtable@ function.
    107 
    108 \begin{sloppypar}
     134\end{cfa}
     135\caption{Virtual Table Layout}
     136\label{f:VirtualTableLayout}
     137\todo*{Improve the Virtual Table Layout diagram.}
     138\end{figure}
     139
     140The first and second sections together mean that every virtual table has a
     141prefix that has the same layout and types as its parent virtual table.
     142This, combined with the fixed offset to the virtual table pointer, means that
     143for any virtual type it doesn't matter if we have it or any of its
     144descendants, it is still always safe to access the virtual table through
     145the virtual table pointer.
     146From there it is safe to check the type id to identify the exact type of the
     147underlying object, access any of the virtual members and pass the object to
     148any of the method-like virtual members.
     149
     150When a virtual table is declared the user decides where to declare it and its
     151name. The initialization of the virtual table is entirely automatic based on
     152the context of the declaration.
     153
     154The type id is always fixed, each virtual table type will always have one
     155exactly one possible type id.
     156The virtual members are usually filled in by resolution. The best match for
     157a given name and type at the declaration site is filled in.
     158There are two exceptions to that rule: the @size@ field is the type's size
     159and is set to the result of a @sizeof@ expression, the @align@ field is the
     160type's alignment and similarly uses an @alignof@ expression.
     161
     162\subsubsection{Concurrency Integration}
    109163Coroutines and threads need instances of @CoroutineCancelled@ and
    110164@ThreadCancelled@ respectively to use all of their functionality. When a new
    … …  
    112166the instance is created as well. The definition of the virtual table is created
    113167at the definition of the main function.
    114 \end{sloppypar}
     168
     169\begin{figure}
     170\begin{cfa}
     171coroutine Example {
     172        // fields
     173}
     174\end{cfa}
     175
     176\begin{cfa}
     177__attribute__((cfa_linkonce))
     178struct __cfatid_struct_CoroutineCancelled(Example)
     179                __cfatid_CoroutineCancelled = {
     180        &EXCEPTION_TYPE_ID,
     181};
     182extern CoroutineCancelled_vtable _default_vtable_object_declaration;
     183extern CoroutineCancelled_vtable & _default_vtable;
     184\end{cfa}
     185
     186\begin{cfa}
     187void main(Example & this) {
     188        // body
     189}
     190\end{cfa}
     191
     192\begin{cfa}
     193CoroutineCancelled_vtable _default_vtable_object_declaration = {
     194        __cfatid_CoroutineCancelled,
     195        // Virtual member initialization.
     196};
     197
     198CoroutineCancelled_vtable & _default_vtable =
     199        &_default_vtable_object_declaration;
     200\end{cfa}
     201\caption{Concurrency Transformations}
     202\label{f:ConcurrencyTransformations}
     203\end{figure}
     204\todo{Improve Concurrency Transformations figure.}
    115205
    116206\subsection{Virtual Cast}
    … …  
    119209% The C-cast is just to make sure the generated code is correct so the rest of
    120210% the section is about that function.
    121 The function is
     211The function is implemented in the standard library and has the following
     212signature:
    122213\begin{cfa}
    123214void * __cfa__virtual_cast(
    124         struct __cfa__parent_vtable const * parent,
    125         struct __cfa__parent_vtable const * const * child );
    126 \end{cfa}
    127 and it is implemented in the standard library. The structure reperents the
    128 head 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@
    130 points at the object of the (possibe) child type.
    131 
    132 In terms of the virtual cast expression, @parent@ comes from looking up the
    133 type being cast to and @child@ is the result of the expression being cast.
    134 Because the complier outputs C code, some type C type casts are also used.
    135 The last bit of glue is an map that saves every virtual type the compiler
    136 sees. This is used to check the type used in a virtual cast is a virtual
    137 type and to get its virtual table.
    138 (It also checks for conflicting definitions.)
    139 
    140 Inside 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
    142 requires one more level of derefence to pass through the object) then @child@
    143 is returned, otherwise the null pointer is returned.
    144 
    145 The check itself is preformed is a simple linear search. If the child
    146 virtual table or any of its ancestors (which are retreved through the first
    147 field of every virtual table) are the same as the parent virtual table then
    148 the cast succeeds.
     215        struct __cfavir_type_td parent,
     216        struct __cfavir_type_id const * child );
     217\end{cfa}
     218The type id of target type of the virtual cast is passed in as @parent@ and
     219the cast target is passed in as @child@.
     220
     221For C generation both arguments and the result are wrapped with type casts.
     222There is also an internal store inside the compiler to make sure that the
     223target type is a virtual type.
     224% It also checks for conflicting definitions.
     225
     226The virtual cast either returns the original pointer as a new type or null.
     227So the function just does the parent check and returns the approprate value.
     228The parent check is a simple linear search of child's ancestors using the
     229type information.
    149230
    150231\section{Exceptions}
    … …  
    161242
    162243Stack unwinding is the process of removing stack frames (activations) from the
    163 stack. On function entry and return, unwinding is handled directly by the code
    164 embedded in the function. Usually, the stack-frame size is known statically
    165 based on parameter and local variable declarations. For dynamically-sized
    166 local variables, a runtime computation is necessary to know the frame
    167 size. Finally, a function's frame-size may change during execution as local
    168 variables (static or dynamic sized) go in and out of scope.
     244stack. On function entry and return, unwinding is handled directly by the
     245call/return code embedded in the function.
     246In many cases the position of the instruction pointer (relative to parameter
     247and local declarations) is enough to know the current size of the stack
     248frame.
     249
     250Usually, the stack-frame size is known statically based on parameter and
     251local variable declarations. Even with dynamic stack-size the information
     252to determain how much of the stack has to be removed is still contained
     253within the function.
    169254Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
    170255bumping the hardware stack-pointer up or down as needed.
    171 
    172 Unwinding across multiple stack frames is more complex because individual stack
    173 management code associated with each frame is bypassed. That is, the location
    174 of a function's frame-management code is largely unknown and dispersed
    175 throughout the function, hence the current frame size managed by that code is
    176 also unknown. Hence, code unwinding across frames does not have direct
    177 knowledge about what is on the stack, and hence, how much of the stack needs to
    178 be 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.
     256Constructing/destructing values on the stack takes longer put in terms of
     257figuring out what needs to be done is of similar complexity.
     258
     259Unwinding across multiple stack frames is more complex because that
     260information is no longer contained within the current function.
     261With seperate compilation a function has no way of knowing what its callers
     262are so it can't know how large those frames are.
     263Without altering the main code path it is also hard to pass that work off
     264to the caller.
    187265
    188266The traditional unwinding mechanism for C is implemented by saving a snap-shot
    … …  
    191269reseting to a snap-shot of an arbitrary but existing function frame on the
    192270stack. It is up to the programmer to ensure the snap-shot is valid when it is
    193 reset, making this unwinding approach fragile with potential errors that are
    194 difficult to debug because the stack becomes corrupted.
    195 
    196 However, many languages define cleanup actions that must be taken when objects
    197 are deallocated from the stack or blocks end, such as running a variable's
    198 destructor or a @try@ statement's @finally@ clause. Handling these mechanisms
    199 requires walking the stack and checking each stack frame for these potential
    200 actions.
    201 
    202 For exceptions, it must be possible to walk the stack frames in search of @try@
    203 statements to match and execute a handler. For termination exceptions, it must
    204 also be possible to unwind all stack frames from the throw to the matching
    205 catch, and each of these frames must be checked for cleanup actions. Stack
    206 walking is where most of the complexity and expense of exception handling
    207 appears.
     271reset and that all required clean-up from the unwound stacks is preformed.
     272This approach is fragile and forces a work onto the surounding code.
     273
     274With respect to that work forced onto the surounding code,
     275many languages define clean-up actions that must be taken when certain
     276sections of the stack are removed. Such as when the storage for a variable
     277is removed from the stack or when a try statement with a finally clause is
     278(conceptually) popped from the stack.
     279None of these should be handled by the user, that would contradict the
     280intention of these features, so they need to be handled automatically.
     281
     282To safely remove sections of the stack the language must be able to find and
     283run these clean-up actions even when removing multiple functions unknown at
     284the beginning of the unwinding.
    208285
    209286One of the most popular tools for stack management is libunwind, a low-level
    … …  
    215292\subsection{libunwind Usage}
    216293Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
    217 provides \CC-style stack-unwinding. Its operation is divided into two phases:
     294provides \Cpp-style stack-unwinding. Its operation is divided into two phases:
    218295search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
    219296stack and decide where unwinding should stop (but no unwinding occurs). The
    … …  
    226303LSDA can contain any information but conventionally it is a table with entries
    227304representing regions of the function and what has to be done there during
    228 unwinding. These regions are bracketed by the instruction pointer. If the
     305unwinding. These regions are bracketed by instruction addresses. If the
    229306instruction pointer is within a region's start/end, then execution is currently
    230307executing in that region. Regions are used to mark out the scopes of objects
    … …  
    238315
    239316The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
    240 attaches its personality function. However, this
     317attaches a personality function to each function.
     318In plain C (which \CFA currently compiles down to) this
    241319flag only handles the cleanup attribute:
    242 \todo{Peter: What is attached? Andrew: It uses the .cfi\_personality directive
    243 and that's all I know.}
    244320\begin{cfa}
    245321void clean_up( int * var ) { ... }
    246322int avar __attribute__(( cleanup(clean_up) ));
    247323\end{cfa}
    248 which is used on a variable and specifies a function, in this case @clean_up@,
    249 run when the variable goes out of scope.
    250 The function is passed a pointer to the object being removed from the stack
    251 so it can be used to mimic destructors.
    252 However, this feature cannot be used to mimic @try@ statements as it cannot
    253 control the unwinding.
     324The attribue is used on a variable and specifies a function,
     325in this case @clean_up@, run when the variable goes out of scope.
     326This is enough to mimic destructors, but not try statements which can effect
     327the unwinding.
     328
     329To get full unwinding support all of this has to be done directly with
     330assembly and assembler directives. Partiularly the cfi directives
     331\texttt{.cfi\_lsda} and \texttt{.cfi\_personality}.
    254332
    255333\subsection{Personality Functions}
    … …  
    268346\end{lstlisting}
    269347The @action@ argument is a bitmask of possible actions:
    270 \begin{enumerate}
     348\begin{enumerate}[topsep=5pt]
    271349\item
    272350@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
    … …  
    291369@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
    292370the cleanup phase and uses a different means to decide when to stop
    293 \see{\VRef{s:ForcedUnwind}}.
     371(see \vref{s:ForcedUnwind}).
    294372\end{enumerate}
    295373
    296374The @exception_class@ argument is a copy of the
    297 \lstinline[language=C]|exception|'s @exception_class@ field.
    298 
    299 The \lstinline[language=C]|exception| argument is a pointer to the user
    300 provided storage object. It has two public fields, the exception class, which
    301 is actually just a number, identifying the exception handling mechanism that
    302 created it, and the cleanup function. The cleanup function is called if
    303 required by the exception.
     375\code{C}{exception}'s @exception_class@ field.
     376This a number that identifies the exception handling mechanism that created
     377the
     378
     379The \code{C}{exception} argument is a pointer to the user
     380provided storage object. It has two public fields: the @exception_class@,
     381which is described above, and the @exception_cleanup@ function.
     382The clean-up function is used by the EHM to clean-up the exception if it
     383should need to be freed at an unusual time, it takes an argument that says
     384why it had to be cleaned up.
    304385
    305386The @context@ argument is a pointer to an opaque type passed to helper
    … …  
    309390that can be passed several places in libunwind. It includes a number of
    310391messages for special cases (some of which should never be used by the
    311 personality function) and error codes but unless otherwise noted the
     392personality function) and error codes. However, unless otherwise noted, the
    312393personality function should always return @_URC_CONTINUE_UNWIND@.
    313394
    … …  
    324405@_URC_END_OF_STACK@.
    325406
    326 Second, when a handler is matched, raise exception continues onto the cleanup
    327 phase.
     407Second, when a handler is matched, raise exception moves to the clean-up
     408phase and walks the stack a second time.
    328409Once again, it calls the personality functions of each stack frame from newest
    329410to oldest. This pass stops at the stack frame containing the matching handler.
    … …  
    338419Forced Unwind is the other central function in libunwind.
    339420\begin{cfa}
    340 _Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *,
     421_Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *,
    341422        _Unwind_Stop_Fn, void *);
    342423\end{cfa}
    … …  
    380461Each stack must have its own exception context. In a sequential \CFA program,
    381462there is only one stack with a single global exception-context. However, when
    382 the library @libcfathread@ is linked, there are multiple stacks where each
     463the library @libcfathread@ is linked, there are multiple stacks and each
    383464needs its own exception context.
    384465
    385 General access to the exception context is provided by function
     466The exception context should be retrieved by calling the function
    386467@this_exception_context@. For sequential execution, this function is defined as
    387468a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
    … …  
    390471
    391472The sequential @this_exception_context@ returns a hard-coded pointer to the
    392 global execption context.
     473global exception context.
    393474The concurrent version adds the exception context to the data stored at the
    394 base of each stack. When @this_exception_context@ is called it retrieves the
     475base of each stack. When @this_exception_context@ is called, it retrieves the
    395476active stack and returns the address of the context saved there.
    396477
    … …  
    399480% catches. Talk about GCC nested functions.
    400481
    401 Termination exceptions use libunwind heavily because it matches the intended
    402 use from \CC exceptions closely. The main complication for \CFA is that the
     482\CFA termination exceptions use libunwind heavily because they match \Cpp
     483\Cpp exceptions closely. The main complication for \CFA is that the
    403484compiler generates C code, making it very difficult to generate the assembly to
    404485form the LSDA for try blocks or destructors.
    … …  
    411492per-exception storage.
    412493
    413 [Quick ASCII diagram to get started.]
     494\begin{figure}
    414495\begin{verbatim}
    415496Fixed Header  | _Unwind_Exception   <- pointer target
    … …  
    420501              V ...
    421502\end{verbatim}
    422 
    423 Exceptions are stored in variable-sized blocks.
    424 The first component is a fixed sized data structure that contains the
     503\caption{Exception Layout}
     504\label{f:ExceptionLayout}
     505\end{figure}
     506\todo*{Convert the exception layout to an actual diagram.}
     507
     508Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}).
     509The first component is a fixed-sized data structure that contains the
    425510information for libunwind and the exception system. The second component is an
    426511area of memory big enough to store the exception. Macros with pointer arthritic
    … …  
    428513@_Unwind_Exception@ to the entire node.
    429514
    430 All of these nodes are linked together in a list, one list per stack, with the
     515Multipe exceptions can exist at the same time because exceptions can be
     516raised inside handlers, destructors and finally blocks.
     517Figure~\vref{f:MultipleExceptions} shows a program that has multiple
     518exceptions active at one time.
     519Each time an exception is thrown and caught the stack unwinds and the finally
     520clause runs. This will throw another exception (until @num_exceptions@ gets
     521high enough) which must be allocated. The previous exceptions may not be
     522freed because the handler/catch clause has not been run.
     523So the EHM must keep them alive while it allocates exceptions for new throws.
     524
     525\begin{figure}
     526\centering
     527% Andrew: Figure out what these do and give them better names.
     528\newsavebox{\myboxA}
     529\newsavebox{\myboxB}
     530\begin{lrbox}{\myboxA}
     531\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
     532unsigned num_exceptions = 0;
     533void throws() {
     534    try {
     535        try {
     536            ++num_exceptions;
     537            throw (Example){table};
     538        } finally {
     539            if (num_exceptions < 3) {
     540                throws();
     541            }
     542        }
     543    } catch (exception_t *) {
     544        --num_exceptions;
     545    }
     546}
     547int main() {
     548    throws();
     549}
     550\end{lstlisting}
     551\end{lrbox}
     552
     553\begin{lrbox}{\myboxB}
     554\begin{lstlisting}
     555\end{lstlisting}
     556\end{lrbox}
     557
     558{\usebox\myboxA}
     559\hspace{25pt}
     560{\usebox\myboxB}
     561
     562\caption{Multiple Exceptions}
     563\label{f:MultipleExceptions}
     564\end{figure}
     565\todo*{Work on multiple exceptions code sample.}
     566
     567All exceptions are stored in nodes which are then linked together in lists,
     568one list per stack, with the
    431569list head stored in the exception context. Within each linked list, the most
    432570recently thrown exception is at the head followed by older thrown
    … …  
    439577exception, the copy function, and the free function, so they are specific to an
    440578exception type. The size and copy function are used immediately to copy an
    441 exception into managed memory. After the exception is handled the free function
    442 is used to clean up the exception and then the entire node is passed to free
    443 so the memory can be given back to the heap.
     579exception into managed memory. After the exception is handled, the free
     580function is used to clean up the exception and then the entire node is
     581passed to free so the memory can be given back to the heap.
    444582
    445583\subsection{Try Statements and Catch Clauses}
    … …  
    454592calls them.
    455593Because this function is known and fixed (and not an arbitrary function that
    456 happens to contain a try statement) this means the LSDA can be generated ahead
     594happens to contain a try statement), the LSDA can be generated ahead
    457595of time.
    458596
    459597Both the LSDA and the personality function are set ahead of time using
    460 embedded assembly. This is handcrafted using C @asm@ statements and contains
     598embedded assembly. This assembly code is handcrafted using C @asm@ statements
     599and contains
    461600enough information for the single try statement the function repersents.
    462601
    … …  
    487626nested functions and all other functions besides @__cfaehm_try_terminate@ in
    488627\CFA use the GCC personality function and the @-fexceptions@ flag to generate
    489 the LSDA. This allows destructors to be implemented with the cleanup attribute.
     628the LSDA.
     629Using this pattern, \CFA implements destructors with the cleanup attribute.
     630
     631\begin{figure}
     632\begin{cfa}
     633try {
     634        // TRY BLOCK
     635} catch (Exception1 * name1 ; check(name1)) {
     636        // CATCH BLOCK 1
     637} catch (Exception2 * name2) {
     638        // CATCH BLOCK 2
     639}
     640\end{cfa}
     641
     642\begin{cfa}
     643void try(void) {
     644        // TRY BLOCK
     645}
     646int match(exception_t * __exception_inst) {
     647        {
     648                Exception1 * name1;
     649                if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) {
     650                        return 1;
     651                }
     652        }
     653        {
     654                Exception2 * name2;
     655                if (name2 = (virtual Exception2 *)__exception_inst) {
     656                        return 2;
     657                }
     658        }
     659        return 0;
     660}
     661void catch(exception_t * __exception_inst, int __handler_index) {
     662        switch (__handler_index) {
     663        case 1:
     664        {
     665                Exception1 * name1 = (virtual Exception1 *)__exception_inst;
     666                // CATCH BLOCK 1
     667        }
     668        return;
     669        case 2:
     670        {
     671                Exception2 * name2 = (virtual Exception2 *)__exception_inst;
     672                // CATCH BLOCK 2
     673        }
     674        return;
     675        }
     676}
     677{
     678        __cfaehm_try_terminate(try, catch, match);
     679}
     680\end{cfa}
     681
     682\caption{Termination Transformation}
     683\label{f:TerminationTransformation}
     684\todo*{Improve (compress?) Termination Transformations.}
     685\end{figure}
    490686
    491687\section{Resumption}
    492688% The stack-local data, the linked list of nodes.
    493689
    494 Resumption simple to implement because there is no stack unwinding. The
    495 resumption raise uses a list of nodes for its stack traversal. The head of the
    496 list is stored in the exception context. The nodes in the list have a pointer
    497 to the next node and a pointer to the handler function.
    498 
    499 A resumption raise traverses this list. At each node the handler function is
    500 called, passing the exception by pointer. It returns true if the exception is
    501 handled and false otherwise.
    502 
    503 The handler function does both the matching and handling. It computes the
    504 condition of each @catchResume@ in top-to-bottom order, until it finds a
    505 handler that matches. If no handler matches then the function returns
    506 false. Otherwise the matching handler is run; if it completes successfully, the
    507 function returns true. Rethrowing, through the @throwResume;@ statement,
    508 causes the function to return true.
     690Resumption simpler to implement than termination
     691because there is no stack unwinding.
     692Instead of storing the data in a special area using assembly,
     693there is just a linked list of possible handlers for each stack,
     694with each node on the list reperenting a try statement on the stack.
     695
     696The head of the list is stored in the exception context.
     697The nodes are stored in order, with the more recent try statements closer
     698to the head of the list.
     699Instead of traversing the stack resumption handling traverses the list.
     700At each node the EHM checks to see if the try statement the node repersents
     701can handle the exception. If it can, then the exception is handled and
     702the operation finishes, otherwise the search continues to the next node.
     703If the search reaches the end of the list without finding a try statement
     704that can handle the exception the default handler is executed and the
     705operation finishes.
     706
     707In each node is a handler function which does most of the work there.
     708The handler function is passed the raised the exception and returns true
     709if the exception is handled and false if it cannot be handled here.
     710
     711For each @catchResume@ clause the handler function will:
     712check to see if the raised exception is a descendant type of the declared
     713exception type, if it is and there is a conditional expression then it will
     714run the test, if both checks pass the handling code for the clause is run
     715and the function returns true, otherwise it moves onto the next clause.
     716If this is the last @catchResume@ clause then instead of moving onto
     717the next clause the function returns false as no handler could be found.
     718
     719\begin{figure}
     720\begin{cfa}
     721try {
     722        // TRY BLOCK
     723} catchResume (Exception1 * name1 ; check(name1)) {
     724        // CATCH BLOCK 1
     725} catchResume (Exception2 * name2) {
     726        // CATCH BLOCK 2
     727}
     728\end{cfa}
     729
     730\begin{cfa}
     731bool handle(exception_t * __exception_inst) {
     732        {
     733                Exception1 * name1;
     734                if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) {
     735                        // CATCH BLOCK 1
     736                        return 1;
     737                }
     738        }
     739        {
     740                Exception2 * name2;
     741                if (name2 = (virtual Exception2 *)__exception_inst) {
     742                        // CATCH BLOCK 2
     743                        return 2;
     744                }
     745        }
     746        return false;
     747}
     748struct __try_resume_node __resume_node
     749        __attribute__((cleanup( __cfaehm_try_resume_cleanup )));
     750__cfaehm_try_resume_setup( &__resume_node, handler );
     751\end{cfa}
     752
     753\caption{Resumption Transformation}
     754\label{f:ResumptionTransformation}
     755\todo*{Improve (compress?) Resumption Transformations.}
     756\end{figure}
    509757
    510758% Recursive Resumption Stuff:
    511 Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack
     759Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
     760the stack
    512761already examined, is accomplished by updating the front of the list as the
    513 search continues. Before the handler at a node is called the head of the list
     762search continues. Before the handler at a node is called, the head of the list
    514763is updated to the next node of the current node. After the search is complete,
    515764successful or not, the head of the list is reset.
    … …  
    524773stack -- the first one points over all the checked handlers -- and the ordering
    525774is maintained.
     775
     776\begin{figure}
     777\begin{minipage}[l][][b]{0,2\textwidth}
     778\begin{verbatim}
     779
     780
     781  X <-
     782  |
     783  V
     784  X
     785  |
     786  V
     787  X
     788\end{verbatim}
     789Initial State
     790\end{minipage}
     791\begin{minipage}[l][][b]{0,2\textwidth}
     792\begin{verbatim}
     793
     794
     795  X
     796  |
     797  V
     798  X <-
     799  |
     800  V
     801  X
     802\end{verbatim}
     803Handler Found
     804\end{minipage}
     805\begin{minipage}[l][][b]{0,2\textwidth}
     806\begin{verbatim}
     807  X <-
     808 /
     809/ X
     810| |
     811\ V
     812  X
     813  |
     814  V
     815  X
     816\end{verbatim}
     817Try Block Added
     818\end{minipage}
     819\begin{minipage}[l][][b]{0,2\textwidth}
     820\begin{verbatim}
     821
     822
     823  X <-
     824  |
     825  V
     826  X
     827  |
     828  V
     829  X
     830\end{verbatim}
     831Handler Done
     832\end{minipage}
     833\caption{Resumption Marking}
     834\label{f:ResumptionMarking}
     835\todo*{Convert Resumption Marking into a line figure.}
     836\end{figure}
    526837
    527838\label{p:zero-cost}
    … …  
    540851\section{Finally}
    541852% Uses destructors and GCC nested functions.
    542 Finally clauses is placed into a GCC nested-function with a unique name, and no
    543 arguments or return values. This nested function is then set as the cleanup
     853A finally clause is placed into a GCC nested-function with a unique name,
     854and no arguments or return values.
     855This nested function is then set as the cleanup
    544856function of an empty object that is declared at the beginning of a block placed
    545857around the context of the associated @try@ statement.
    546858
    547 The rest is handled by GCC. The try block and all handlers are inside the
     859The rest is handled by GCC. The try block and all handlers are inside this
    548860block. At completion, control exits the block and the empty object is cleaned
    549861up, which runs the function that contains the finally code.
    … …  
    553865
    554866Cancellation also uses libunwind to do its stack traversal and unwinding,
    555 however it uses a different primary function @_Unwind_ForcedUnwind@. Details
    556 of its interface can be found in the \VRef{s:ForcedUnwind}.
     867however it uses a different primary function: @_Unwind_ForcedUnwind@. Details
     868of its interface can be found in the Section~\vref{s:ForcedUnwind}.
    557869
    558870The first step of cancellation is to find the cancelled stack and its type:
    … …  
    560872pointer and the current thread pointer, and every thread stores a pointer to
    561873its main coroutine and the coroutine it is currently executing.
    562 
    563 So if the active thread's main and current coroutine are the same. If they
    564 are then the current stack is a thread stack, otherwise it is a coroutine
    565 stack. If it is a thread stack then an equality check with the stored main
    566 thread pointer and current thread pointer is enough to tell if the current
    567 thread is the main thread or not.
     874\todo*{Consider adding a description of how threads are coroutines.}
     875
     876If a the current thread's main and current coroutines are the same then the
     877current stack is a thread stack. Furthermore it is easy to compare the
     878current thread to the main thread to see if they are the same. And if this
     879is not a thread stack then it must be a coroutine stack.
    568880
    569881However, if the threading library is not linked, the sequential execution is on
    … …  
    574886Regardless of how the stack is chosen, the stop function and parameter are
    575887passed to the forced-unwind function. The general pattern of all three stop
    576 functions is the same: they continue unwinding until the end of stack when they
    577 do there primary work.
     888functions is the same: they continue unwinding until the end of stack and
     889then preform their transfer.
    578890
    579891For main stack cancellation, the transfer is just a program abort.
Note: See TracChangeset for help on using the changeset viewer.