source: doc/theses/andrew_beach_MMath/implement.tex @ c21f5a9

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulation
Last change on this file since c21f5a9 was c21f5a9, checked in by Andrew Beach <ajbeach@…>, 15 months ago

Andrew MMath: Work on figures and linkonce.

  • Property mode set to 100644
File size: 36.3 KB
Line 
1\chapter{Implementation}
2% Goes over how all the features are implemented.
3
4The implementation work for this thesis covers two components: the virtual
5system and exceptions. Each component is discussed in detail.
6
7\section{Virtual System}
8\label{s:VirtualSystem}
9% Virtual table rules. Virtual tables, the pointer to them and the cast.
10While the \CFA virtual system currently has only one public feature, virtual
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.
14
15\subsection{Virtual Type}
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.
105
106\subsection{Virtual Table}
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
131child_field0
132...
133child_fieldN
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}
163Coroutines and threads need instances of @CoroutineCancelled@ and
164@ThreadCancelled@ respectively to use all of their functionality. When a new
165data type is declared with @coroutine@ or @thread@ the forward declaration for
166the instance is created as well. The definition of the virtual table is created
167at the definition of the main function.
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.}
205
206\subsection{Virtual Cast}
207Virtual casts are implemented as a function call that does the subtype check
208and a C coercion-cast to do the type conversion.
209% The C-cast is just to make sure the generated code is correct so the rest of
210% the section is about that function.
211The function is implemented in the standard library and has the following
212signature:
213\begin{cfa}
214void * __cfa__virtual_cast(
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.
230
231\section{Exceptions}
232% Anything about exception construction.
233
234\section{Unwinding}
235% Adapt the unwind chapter, just describe the sections of libunwind used.
236% Mention that termination and cancellation use it. Maybe go into why
237% resumption doesn't as well.
238
239% Many modern languages work with an interal stack that function push and pop
240% their local data to. Stack unwinding removes large sections of the stack,
241% often across functions.
242
243Stack unwinding is the process of removing stack frames (activations) from the
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.
254Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
255bumping the hardware stack-pointer up or down as needed.
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.
265
266The traditional unwinding mechanism for C is implemented by saving a snap-shot
267of a function's state with @setjmp@ and restoring that snap-shot with
268@longjmp@. This approach bypasses the need to know stack details by simply
269reseting to a snap-shot of an arbitrary but existing function frame on the
270stack. It is up to the programmer to ensure the snap-shot is valid when it is
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.
285
286One of the most popular tools for stack management is libunwind, a low-level
287library that provides tools for stack walking, handler execution, and
288unwinding. What follows is an overview of all the relevant features of
289libunwind needed for this work, and how \CFA uses them to implement exception
290handling.
291
292\subsection{libunwind Usage}
293Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
294provides \Cpp-style stack-unwinding. Its operation is divided into two phases:
295search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
296stack and decide where unwinding should stop (but no unwinding occurs). The
297cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
298
299To use libunwind, each function must have a personality function and a Language
300Specific Data Area (LSDA). The LSDA has the unique information for each
301function to tell the personality function where a function is executing, its
302current stack frame, and what handlers should be checked. Theoretically, the
303LSDA can contain any information but conventionally it is a table with entries
304representing regions of the function and what has to be done there during
305unwinding. These regions are bracketed by instruction addresses. If the
306instruction pointer is within a region's start/end, then execution is currently
307executing in that region. Regions are used to mark out the scopes of objects
308with destructors and try blocks.
309
310% Libunwind actually does very little, it simply moves down the stack from
311% function to function. Most of the actions are implemented by the personality
312% function which libunwind calls on every function. Since this is shared across
313% many functions or even every function in a language it will need a bit more
314% information.
315
316The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
317attaches a personality function to each function.
318In plain C (which \CFA currently compiles down to) this
319flag only handles the cleanup attribute:
320\begin{cfa}
321void clean_up( int * var ) { ... }
322int avar __attribute__(( cleanup(clean_up) ));
323\end{cfa}
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}.
332
333\subsection{Personality Functions}
334Personality functions have a complex interface specified by libunwind. This
335section covers some of the important parts of the interface.
336
337A personality function can preform different actions depending on how it is
338called.
339\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
340typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) (
341        _Unwind_Action @action@,
342        _Unwind_Exception_Class @exception_class@,
343        _Unwind_Exception * @exception@,
344        struct _Unwind_Context * @context@
345);
346\end{lstlisting}
347The @action@ argument is a bitmask of possible actions:
348\begin{enumerate}[topsep=5pt]
349\item
350@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
351to check for handlers. If there is a handler in a stack frame, as defined by
352the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
353it return @_URC_CONTINUE_UNWIND@.
354
355\item
356@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
357unwound and all cleanup code is run. The personality function does whatever
358cleanup the language defines (such as running destructors/finalizers) and then
359generally returns @_URC_CONTINUE_UNWIND@.
360
361\item
362\begin{sloppypar}
363@_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a
364handler. The personality function must prepare to return to normal code
365execution and return @_URC_INSTALL_CONTEXT@.
366\end{sloppypar}
367
368\item
369@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
370the cleanup phase and uses a different means to decide when to stop
371(see \vref{s:ForcedUnwind}).
372\end{enumerate}
373
374The @exception_class@ argument is a copy of the
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.
385
386The @context@ argument is a pointer to an opaque type passed to helper
387functions called inside the personality function.
388
389The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
390that can be passed several places in libunwind. It includes a number of
391messages for special cases (some of which should never be used by the
392personality function) and error codes. However, unless otherwise noted, the
393personality function should always return @_URC_CONTINUE_UNWIND@.
394
395\subsection{Raise Exception}
396Raising an exception is the central function of libunwind and it performs a
397two-staged unwinding.
398\begin{cfa}
399_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
400\end{cfa}
401First, the function begins the search phase, calling the personality function
402of the most recent stack frame. It continues to call personality functions
403traversing the stack from newest to oldest until a function finds a handler or
404the end of the stack is reached. In the latter case, raise exception returns
405@_URC_END_OF_STACK@.
406
407Second, when a handler is matched, raise exception moves to the clean-up
408phase and walks the stack a second time.
409Once again, it calls the personality functions of each stack frame from newest
410to oldest. This pass stops at the stack frame containing the matching handler.
411If that personality function has not install a handler, it is an error.
412
413If an error is encountered, raise exception returns either
414@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
415error occurred.
416
417\subsection{Forced Unwind}
418\label{s:ForcedUnwind}
419Forced Unwind is the other central function in libunwind.
420\begin{cfa}
421_Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *,
422        _Unwind_Stop_Fn, void *);
423\end{cfa}
424It also unwinds the stack but it does not use the search phase. Instead another
425function, the stop function, is used to stop searching. The exception is the
426same as the one passed to raise exception. The extra arguments are the stop
427function and the stop parameter. The stop function has a similar interface as a
428personality function, except it is also passed the stop parameter.
429\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
430typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)(
431        _Unwind_Action @action@,
432        _Unwind_Exception_Class @exception_class@,
433        _Unwind_Exception * @exception@,
434        struct _Unwind_Context * @context@,
435        void * @stop_parameter@);
436\end{lstlisting}
437
438The stop function is called at every stack frame before the personality
439function is called and then once more after all frames of the stack are
440unwound.
441
442Each time it is called, the stop function should return @_URC_NO_REASON@ or
443transfer control directly to other code outside of libunwind. The framework
444does not provide any assistance here.
445
446\begin{sloppypar}
447Its arguments are the same as the paired personality function. The actions
448@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
449called. Beyond the libunwind standard, both GCC and Clang add an extra action
450on the last call at the end of the stack: @_UA_END_OF_STACK@.
451\end{sloppypar}
452
453\section{Exception Context}
454% Should I have another independent section?
455% There are only two things in it, top_resume and current_exception. How it is
456% stored changes depending on whether or not the thread-library is linked.
457
458The exception context is global storage used to maintain data across different
459exception operations and to communicate among different components.
460
461Each stack must have its own exception context. In a sequential \CFA program,
462there is only one stack with a single global exception-context. However, when
463the library @libcfathread@ is linked, there are multiple stacks and each
464needs its own exception context.
465
466The exception context should be retrieved by calling the function
467@this_exception_context@. For sequential execution, this function is defined as
468a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
469concurrent, it links with @libcfathread@, where this function is defined with a
470strong symbol replacing the sequential version.
471
472The sequential @this_exception_context@ returns a hard-coded pointer to the
473global exception context.
474The concurrent version adds the exception context to the data stored at the
475base of each stack. When @this_exception_context@ is called, it retrieves the
476active stack and returns the address of the context saved there.
477
478\section{Termination}
479% Memory management & extra information, the custom function used to implement
480% catches. Talk about GCC nested functions.
481
482\CFA termination exceptions use libunwind heavily because they match \Cpp
483\Cpp exceptions closely. The main complication for \CFA is that the
484compiler generates C code, making it very difficult to generate the assembly to
485form the LSDA for try blocks or destructors.
486
487\subsection{Memory Management}
488The first step of a termination raise is to copy the exception into memory
489managed by the exception system. Currently, the system uses @malloc@, rather
490than reserved memory or the stack top. The exception handling mechanism manages
491memory for the exception as well as memory for libunwind and the system's own
492per-exception storage.
493
494\begin{figure}
495\begin{verbatim}
496Fixed Header  | _Unwind_Exception   <- pointer target
497              |
498              | Cforall storage
499              |
500Variable Body | the exception       <- fixed offset
501              V ...
502\end{verbatim}
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
510information for libunwind and the exception system. The second component is an
511area of memory big enough to store the exception. Macros with pointer arthritic
512and type cast are used to move between the components or go from the embedded
513@_Unwind_Exception@ to the entire node.
514
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
569list head stored in the exception context. Within each linked list, the most
570recently thrown exception is at the head followed by older thrown
571exceptions. This format allows exceptions to be thrown, while a different
572exception is being handled. The exception at the head of the list is currently
573being handled, while other exceptions wait for the exceptions before them to be
574removed.
575
576The virtual members in the exception's virtual table provide the size of the
577exception, the copy function, and the free function, so they are specific to an
578exception type. The size and copy function are used immediately to copy an
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.
582
583\subsection{Try Statements and Catch Clauses}
584The try statement with termination handlers is complex because it must
585compensate for the lack of assembly-code generated from \CFA. Libunwind
586requires an LSDA and personality function for control to unwind across a
587function. The LSDA in particular is hard to mimic in generated C code.
588
589The workaround is a function called @__cfaehm_try_terminate@ in the standard
590library. The contents of a try block and the termination handlers are converted
591into functions. These are then passed to the try terminate function and it
592calls them.
593Because this function is known and fixed (and not an arbitrary function that
594happens to contain a try statement), the LSDA can be generated ahead
595of time.
596
597Both the LSDA and the personality function are set ahead of time using
598embedded assembly. This assembly code is handcrafted using C @asm@ statements
599and contains
600enough information for the single try statement the function repersents.
601
602The three functions passed to try terminate are:
603\begin{description}
604\item[try function:] This function is the try block, all the code inside the
605try block is placed inside the try function. It takes no parameters and has no
606return value. This function is called during regular execution to run the try
607block.
608
609\item[match function:] This function is called during the search phase and
610decides if a catch clause matches the termination exception. It is constructed
611from the conditional part of each handler and runs each check, top to bottom,
612in turn, first checking to see if the exception type matches and then if the
613condition is true. It takes a pointer to the exception and returns 0 if the
614exception is not handled here. Otherwise the return value is the id of the
615handler that matches the exception.
616
617\item[handler function:] This function handles the exception. It takes a
618pointer to the exception and the handler's id and returns nothing. It is called
619after the cleanup phase. It is constructed by stitching together the bodies of
620each handler and dispatches to the selected handler.
621\end{description}
622All three functions are created with GCC nested functions. GCC nested functions
623can be used to create closures, functions that can refer to the state of other
624functions on the stack. This approach allows the functions to refer to all the
625variables in scope for the function containing the @try@ statement. These
626nested functions and all other functions besides @__cfaehm_try_terminate@ in
627\CFA use the GCC personality function and the @-fexceptions@ flag to generate
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}
686
687\section{Resumption}
688% The stack-local data, the linked list of nodes.
689
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}
757
758% Recursive Resumption Stuff:
759Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
760the stack
761already examined, is accomplished by updating the front of the list as the
762search continues. Before the handler at a node is called, the head of the list
763is updated to the next node of the current node. After the search is complete,
764successful or not, the head of the list is reset.
765
766This mechanism means the current handler and every handler that has already
767been checked are not on the list while a handler is run. If a resumption is
768thrown during the handling of another resumption the active handlers and all
769the other handler checked up to this point are not checked again.
770
771This structure also supports new handler added while the resumption is being
772handled. These are added to the front of the list, pointing back along the
773stack -- the first one points over all the checked handlers -- and the ordering
774is 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}
837
838\label{p:zero-cost}
839Note, the resumption implementation has a cost for entering/exiting a @try@
840statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
841clauses has zero-cost entry/exit. While resumption does not need the stack
842unwinding and cleanup provided by libunwind, it could use the search phase to
843providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
844to return from a libunwind search without installing a handler or raising an
845error. Although workarounds might be possible, they are beyond the scope of
846this thesis. The current resumption implementation has simplicity in its
847favour.
848% Seriously, just compare the size of the two chapters and then consider
849% that unwind is required knowledge for that chapter.
850
851\section{Finally}
852% Uses destructors and GCC nested functions.
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
856function of an empty object that is declared at the beginning of a block placed
857around the context of the associated @try@ statement.
858
859The rest is handled by GCC. The try block and all handlers are inside this
860block. At completion, control exits the block and the empty object is cleaned
861up, which runs the function that contains the finally code.
862
863\section{Cancellation}
864% Stack selections, the three internal unwind functions.
865
866Cancellation also uses libunwind to do its stack traversal and unwinding,
867however it uses a different primary function: @_Unwind_ForcedUnwind@. Details
868of its interface can be found in the Section~\vref{s:ForcedUnwind}.
869
870The first step of cancellation is to find the cancelled stack and its type:
871coroutine or thread. Fortunately, the thread library stores the main thread
872pointer and the current thread pointer, and every thread stores a pointer to
873its main coroutine and the coroutine it is currently executing.
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.
880
881However, if the threading library is not linked, the sequential execution is on
882the main stack. Hence, the entire check is skipped because the weak-symbol
883function is loaded. Therefore, a main thread cancellation is unconditionally
884performed.
885
886Regardless of how the stack is chosen, the stop function and parameter are
887passed to the forced-unwind function. The general pattern of all three stop
888functions is the same: they continue unwinding until the end of stack and
889then preform their transfer.
890
891For main stack cancellation, the transfer is just a program abort.
892
893For coroutine cancellation, the exception is stored on the coroutine's stack,
894and the coroutine context switches to its last resumer. The rest is handled on
895the backside of the resume, which check if the resumed coroutine is
896cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
897and a @CoroutineCancelled@ exception is constructed and loaded with the
898cancelled exception. It is then resumed as a regular exception with the default
899handler coming from the context of the resumption call.
900
901For thread cancellation, the exception is stored on the thread's main stack and
902then context switched to the scheduler. The rest is handled by the thread
903joiner. When the join is complete, the joiner checks if the joined thread is
904cancelled. If cancelled, the exception is retrieved and the joined thread, and
905a @ThreadCancelled@ exception is constructed and loaded with the cancelled
906exception. The default handler is passed in as a function pointer. If it is
907null (as it is for the auto-generated joins on destructor call), the default is
908used, which is a program abort.
909%; which gives the required handling on implicate join.
Note: See TracBrowser for help on using the repository browser.