source: doc/theses/andrew_beach_MMath/implement.tex @ 553f8ab

arm-ehenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 553f8ab was 553f8ab, checked in by Andrew Beach <ajbeach@…>, 12 months ago

Andrew MMath: Responding to Peter's suggestions on the introduction.

  • Property mode set to 100644
File size: 35.5 KB
Line 
1\chapter{Implementation}
2\label{c:implement}
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 \snake{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\input{vtable-layout}
127\caption{Virtual Table Layout}
128\label{f:VirtualTableLayout}
129\todo*{Improve the Virtual Table Layout diagram.}
130\end{figure}
131
132The first and second sections together mean that every virtual table has a
133prefix that has the same layout and types as its parent virtual table.
134This, combined with the fixed offset to the virtual table pointer, means that
135for any virtual type it doesn't matter if we have it or any of its
136descendants, it is still always safe to access the virtual table through
137the virtual table pointer.
138From there it is safe to check the type id to identify the exact type of the
139underlying object, access any of the virtual members and pass the object to
140any of the method-like virtual members.
141
142When a virtual table is declared the user decides where to declare it and its
143name. The initialization of the virtual table is entirely automatic based on
144the context of the declaration.
145
146The type id is always fixed, each virtual table type will always have one
147exactly one possible type id.
148The virtual members are usually filled in by resolution. The best match for
149a given name and type at the declaration site is filled in.
150There are two exceptions to that rule: the @size@ field is the type's size
151and is set to the result of a @sizeof@ expression, the @align@ field is the
152type's alignment and similarly uses an @alignof@ expression.
153
154\subsubsection{Concurrency Integration}
155Coroutines and threads need instances of @CoroutineCancelled@ and
156@ThreadCancelled@ respectively to use all of their functionality. When a new
157data type is declared with @coroutine@ or @thread@ the forward declaration for
158the instance is created as well. The definition of the virtual table is created
159at the definition of the main function.
160
161\begin{figure}
162\begin{cfa}
163coroutine Example {
164        // fields
165};
166\end{cfa}
167
168\begin{cfa}
169__attribute__((cfa_linkonce))
170struct __cfatid_struct_CoroutineCancelled(Example)
171                __cfatid_CoroutineCancelled = {
172        &EXCEPTION_TYPE_ID,
173};
174extern CoroutineCancelled_vtable _default_vtable_object_declaration;
175extern CoroutineCancelled_vtable & _default_vtable;
176\end{cfa}
177
178\begin{cfa}
179void main(Example & this) {
180        // body
181}
182\end{cfa}
183
184\begin{cfa}
185CoroutineCancelled_vtable _default_vtable_object_declaration = {
186        __cfatid_CoroutineCancelled,
187        // Virtual member initialization.
188};
189
190CoroutineCancelled_vtable & _default_vtable =
191        &_default_vtable_object_declaration;
192\end{cfa}
193\caption{Concurrency Transformations}
194\label{f:ConcurrencyTransformations}
195\end{figure}
196\todo{Improve Concurrency Transformations figure.}
197
198\subsection{Virtual Cast}
199Virtual casts are implemented as a function call that does the subtype check
200and a C coercion-cast to do the type conversion.
201% The C-cast is just to make sure the generated code is correct so the rest of
202% the section is about that function.
203The function is implemented in the standard library and has the following
204signature:
205\begin{cfa}
206void * __cfa__virtual_cast(
207        struct __cfavir_type_td parent,
208        struct __cfavir_type_id const * child );
209\end{cfa}
210The type id of target type of the virtual cast is passed in as @parent@ and
211the cast target is passed in as @child@.
212
213For C generation both arguments and the result are wrapped with type casts.
214There is also an internal store inside the compiler to make sure that the
215target type is a virtual type.
216% It also checks for conflicting definitions.
217
218The virtual cast either returns the original pointer as a new type or null.
219So the function just does the parent check and returns the approprate value.
220The parent check is a simple linear search of child's ancestors using the
221type information.
222
223\section{Exceptions}
224% Anything about exception construction.
225
226\section{Unwinding}
227% Adapt the unwind chapter, just describe the sections of libunwind used.
228% Mention that termination and cancellation use it. Maybe go into why
229% resumption doesn't as well.
230
231% Many modern languages work with an interal stack that function push and pop
232% their local data to. Stack unwinding removes large sections of the stack,
233% often across functions.
234
235Stack unwinding is the process of removing stack frames (activations) from the
236stack. On function entry and return, unwinding is handled directly by the
237call/return code embedded in the function.
238In many cases the position of the instruction pointer (relative to parameter
239and local declarations) is enough to know the current size of the stack
240frame.
241
242Usually, the stack-frame size is known statically based on parameter and
243local variable declarations. Even with dynamic stack-size the information
244to determain how much of the stack has to be removed is still contained
245within the function.
246Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
247bumping the hardware stack-pointer up or down as needed.
248Constructing/destructing values on the stack takes longer put in terms of
249figuring out what needs to be done is of similar complexity.
250
251Unwinding across multiple stack frames is more complex because that
252information is no longer contained within the current function.
253With seperate compilation a function has no way of knowing what its callers
254are so it can't know how large those frames are.
255Without altering the main code path it is also hard to pass that work off
256to the caller.
257
258The traditional unwinding mechanism for C is implemented by saving a snap-shot
259of a function's state with @setjmp@ and restoring that snap-shot with
260@longjmp@. This approach bypasses the need to know stack details by simply
261reseting to a snap-shot of an arbitrary but existing function frame on the
262stack. It is up to the programmer to ensure the snap-shot is valid when it is
263reset and that all required clean-up from the unwound stacks is preformed.
264This approach is fragile and forces a work onto the surounding code.
265
266With respect to that work forced onto the surounding code,
267many languages define clean-up actions that must be taken when certain
268sections of the stack are removed. Such as when the storage for a variable
269is removed from the stack or when a try statement with a finally clause is
270(conceptually) popped from the stack.
271None of these should be handled by the user, that would contradict the
272intention of these features, so they need to be handled automatically.
273
274To safely remove sections of the stack the language must be able to find and
275run these clean-up actions even when removing multiple functions unknown at
276the beginning of the unwinding.
277
278One of the most popular tools for stack management is libunwind, a low-level
279library that provides tools for stack walking, handler execution, and
280unwinding. What follows is an overview of all the relevant features of
281libunwind needed for this work, and how \CFA uses them to implement exception
282handling.
283
284\subsection{libunwind Usage}
285Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
286provides \Cpp-style stack-unwinding. Its operation is divided into two phases:
287search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
288stack and decide where unwinding should stop (but no unwinding occurs). The
289cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
290
291To use libunwind, each function must have a personality function and a Language
292Specific Data Area (LSDA). The LSDA has the unique information for each
293function to tell the personality function where a function is executing, its
294current stack frame, and what handlers should be checked. Theoretically, the
295LSDA can contain any information but conventionally it is a table with entries
296representing regions of the function and what has to be done there during
297unwinding. These regions are bracketed by instruction addresses. If the
298instruction pointer is within a region's start/end, then execution is currently
299executing in that region. Regions are used to mark out the scopes of objects
300with destructors and try blocks.
301
302% Libunwind actually does very little, it simply moves down the stack from
303% function to function. Most of the actions are implemented by the personality
304% function which libunwind calls on every function. Since this is shared across
305% many functions or even every function in a language it will need a bit more
306% information.
307
308The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
309attaches a personality function to each function.
310In plain C (which \CFA currently compiles down to) this
311flag only handles the cleanup attribute:
312\begin{cfa}
313void clean_up( int * var ) { ... }
314int avar __attribute__(( cleanup(clean_up) ));
315\end{cfa}
316The attribue is used on a variable and specifies a function,
317in this case @clean_up@, run when the variable goes out of scope.
318This is enough to mimic destructors, but not try statements which can effect
319the unwinding.
320
321To get full unwinding support all of this has to be done directly with
322assembly and assembler directives. Partiularly the cfi directives
323\snake{.cfi_lsda} and \snake{.cfi_personality}.
324
325\subsection{Personality Functions}
326Personality functions have a complex interface specified by libunwind. This
327section covers some of the important parts of the interface.
328
329A personality function can preform different actions depending on how it is
330called.
331\begin{lstlisting}
332typedef _Unwind_Reason_Code (*_Unwind_Personality_Fn) (
333        _Unwind_Action action,
334        _Unwind_Exception_Class exception_class,
335        _Unwind_Exception * exception,
336        struct _Unwind_Context * context);
337\end{lstlisting}
338The @action@ argument is a bitmask of possible actions:
339\begin{enumerate}[topsep=5pt]
340\item
341@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
342to check for handlers. If there is a handler in a stack frame, as defined by
343the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
344it return @_URC_CONTINUE_UNWIND@.
345
346\item
347@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
348unwound and all cleanup code is run. The personality function does whatever
349cleanup the language defines (such as running destructors/finalizers) and then
350generally returns @_URC_CONTINUE_UNWIND@.
351
352\item
353\begin{sloppypar}
354@_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a
355handler. The personality function must prepare to return to normal code
356execution and return @_URC_INSTALL_CONTEXT@.
357\end{sloppypar}
358
359\item
360@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
361the cleanup phase and uses a different means to decide when to stop
362(see \vref{s:ForcedUnwind}).
363\end{enumerate}
364
365The @exception_class@ argument is a copy of the
366\code{C}{exception}'s @exception_class@ field.
367This a number that identifies the exception handling mechanism that created
368the
369
370The \code{C}{exception} argument is a pointer to the user
371provided storage object. It has two public fields: the @exception_class@,
372which is described above, and the @exception_cleanup@ function.
373The clean-up function is used by the EHM to clean-up the exception if it
374should need to be freed at an unusual time, it takes an argument that says
375why it had to be cleaned up.
376
377The @context@ argument is a pointer to an opaque type passed to helper
378functions called inside the personality function.
379
380The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
381that can be passed several places in libunwind. It includes a number of
382messages for special cases (some of which should never be used by the
383personality function) and error codes. However, unless otherwise noted, the
384personality function should always return @_URC_CONTINUE_UNWIND@.
385
386\subsection{Raise Exception}
387Raising an exception is the central function of libunwind and it performs a
388two-staged unwinding.
389\begin{cfa}
390_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
391\end{cfa}
392First, the function begins the search phase, calling the personality function
393of the most recent stack frame. It continues to call personality functions
394traversing the stack from newest to oldest until a function finds a handler or
395the end of the stack is reached. In the latter case, raise exception returns
396@_URC_END_OF_STACK@.
397
398Second, when a handler is matched, raise exception moves to the clean-up
399phase and walks the stack a second time.
400Once again, it calls the personality functions of each stack frame from newest
401to oldest. This pass stops at the stack frame containing the matching handler.
402If that personality function has not install a handler, it is an error.
403
404If an error is encountered, raise exception returns either
405@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
406error occurred.
407
408\subsection{Forced Unwind}
409\label{s:ForcedUnwind}
410Forced Unwind is the other central function in libunwind.
411\begin{cfa}
412_Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *,
413        _Unwind_Stop_Fn, void *);
414\end{cfa}
415It also unwinds the stack but it does not use the search phase. Instead another
416function, the stop function, is used to stop searching. The exception is the
417same as the one passed to raise exception. The extra arguments are the stop
418function and the stop parameter. The stop function has a similar interface as a
419personality function, except it is also passed the stop parameter.
420\begin{lstlisting}
421typedef _Unwind_Reason_Code (*_Unwind_Stop_Fn)(
422        _Unwind_Action action,
423        _Unwind_Exception_Class exception_class,
424        _Unwind_Exception * exception,
425        struct _Unwind_Context * context,
426        void * stop_parameter);
427\end{lstlisting}
428
429The stop function is called at every stack frame before the personality
430function is called and then once more after all frames of the stack are
431unwound.
432
433Each time it is called, the stop function should return @_URC_NO_REASON@ or
434transfer control directly to other code outside of libunwind. The framework
435does not provide any assistance here.
436
437\begin{sloppypar}
438Its arguments are the same as the paired personality function. The actions
439\snake{_UA_CLEANUP_PHASE} and \snake{_UA_FORCE_UNWIND} are always set when it is
440called. Beyond the libunwind standard, both GCC and Clang add an extra action
441on the last call at the end of the stack: \snake{_UA_END_OF_STACK}.
442\end{sloppypar}
443
444\section{Exception Context}
445% Should I have another independent section?
446% There are only two things in it, top_resume and current_exception. How it is
447% stored changes depending on whether or not the thread-library is linked.
448
449The exception context is global storage used to maintain data across different
450exception operations and to communicate among different components.
451
452Each stack must have its own exception context. In a sequential \CFA program,
453there is only one stack with a single global exception-context. However, when
454the library @libcfathread@ is linked, there are multiple stacks and each
455needs its own exception context.
456
457The exception context should be retrieved by calling the function
458\snake{this_exception_context}.
459For sequential execution, this function is defined as
460a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
461concurrent, it links with @libcfathread@, where this function is defined with a
462strong symbol replacing the sequential version.
463
464The sequential @this_exception_context@ returns a hard-coded pointer to the
465global exception context.
466The concurrent version adds the exception context to the data stored at the
467base of each stack. When @this_exception_context@ is called, it retrieves the
468active stack and returns the address of the context saved there.
469
470\section{Termination}
471% Memory management & extra information, the custom function used to implement
472% catches. Talk about GCC nested functions.
473
474\CFA termination exceptions use libunwind heavily because they match \Cpp
475\Cpp exceptions closely. The main complication for \CFA is that the
476compiler generates C code, making it very difficult to generate the assembly to
477form the LSDA for try blocks or destructors.
478
479\subsection{Memory Management}
480The first step of a termination raise is to copy the exception into memory
481managed by the exception system. Currently, the system uses @malloc@, rather
482than reserved memory or the stack top. The exception handling mechanism manages
483memory for the exception as well as memory for libunwind and the system's own
484per-exception storage.
485
486\begin{figure}
487\input{exception-layout}
488\caption{Exception Layout}
489\label{f:ExceptionLayout}
490\end{figure}
491\todo*{Convert the exception layout to an actual diagram.}
492
493Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}).
494The first component is a fixed-sized data structure that contains the
495information for libunwind and the exception system. The second component is an
496area of memory big enough to store the exception. Macros with pointer arthritic
497and type cast are used to move between the components or go from the embedded
498@_Unwind_Exception@ to the entire node.
499
500Multipe exceptions can exist at the same time because exceptions can be
501raised inside handlers, destructors and finally blocks.
502Figure~\vref{f:MultipleExceptions} shows a program that has multiple
503exceptions active at one time.
504Each time an exception is thrown and caught the stack unwinds and the finally
505clause runs. This will throw another exception (until @num_exceptions@ gets
506high enough) which must be allocated. The previous exceptions may not be
507freed because the handler/catch clause has not been run.
508So the EHM must keep them alive while it allocates exceptions for new throws.
509
510\begin{figure}
511\centering
512\newsavebox{\codeBox}
513\newsavebox{\stackBox}
514\begin{lrbox}{\codeBox}
515\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
516unsigned num_exceptions = 0;
517void throws() {
518    try {
519        try {
520            ++num_exceptions;
521            throw (Example){table};
522        } finally {
523            if (num_exceptions < 3) {
524                throws();
525            }
526        }
527    } catch (exception_t *) {
528        --num_exceptions;
529    }
530}
531int main() {
532    throws();
533}
534\end{lstlisting}
535\end{lrbox}
536
537\begin{lrbox}{\stackBox}
538\begin{lstlisting}
539| try-finally
540| try-catch (Example)
541throws()
542| try-finally
543| try-catch (Example)
544throws()
545| try-finally
546| try-catch (Example)
547throws()
548main()
549\end{lstlisting}
550\end{lrbox}
551
552{\usebox\codeBox}
553\hspace{25pt}
554{\usebox\stackBox}
555
556\caption{Multiple Exceptions}
557\label{f:MultipleExceptions}
558\end{figure}
559\todo*{Work on multiple exceptions code sample.}
560
561All exceptions are stored in nodes which are then linked together in lists,
562one list per stack, with the
563list head stored in the exception context. Within each linked list, the most
564recently thrown exception is at the head followed by older thrown
565exceptions. This format allows exceptions to be thrown, while a different
566exception is being handled. The exception at the head of the list is currently
567being handled, while other exceptions wait for the exceptions before them to be
568removed.
569
570The virtual members in the exception's virtual table provide the size of the
571exception, the copy function, and the free function, so they are specific to an
572exception type. The size and copy function are used immediately to copy an
573exception into managed memory. After the exception is handled, the free
574function is used to clean up the exception and then the entire node is
575passed to free so the memory can be given back to the heap.
576
577\subsection{Try Statements and Catch Clauses}
578The try statement with termination handlers is complex because it must
579compensate for the lack of assembly-code generated from \CFA. Libunwind
580requires an LSDA and personality function for control to unwind across a
581function. The LSDA in particular is hard to mimic in generated C code.
582
583The workaround is a function called @__cfaehm_try_terminate@ in the standard
584library. The contents of a try block and the termination handlers are converted
585into functions. These are then passed to the try terminate function and it
586calls them.
587Because this function is known and fixed (and not an arbitrary function that
588happens to contain a try statement), the LSDA can be generated ahead
589of time.
590
591Both the LSDA and the personality function are set ahead of time using
592embedded assembly. This assembly code is handcrafted using C @asm@ statements
593and contains
594enough information for the single try statement the function repersents.
595
596The three functions passed to try terminate are:
597\begin{description}
598\item[try function:] This function is the try block, all the code inside the
599try block is placed inside the try function. It takes no parameters and has no
600return value. This function is called during regular execution to run the try
601block.
602
603\item[match function:] This function is called during the search phase and
604decides if a catch clause matches the termination exception. It is constructed
605from the conditional part of each handler and runs each check, top to bottom,
606in turn, first checking to see if the exception type matches and then if the
607condition is true. It takes a pointer to the exception and returns 0 if the
608exception is not handled here. Otherwise the return value is the id of the
609handler that matches the exception.
610
611\item[handler function:] This function handles the exception. It takes a
612pointer to the exception and the handler's id and returns nothing. It is called
613after the cleanup phase. It is constructed by stitching together the bodies of
614each handler and dispatches to the selected handler.
615\end{description}
616All three functions are created with GCC nested functions. GCC nested functions
617can be used to create closures, functions that can refer to the state of other
618functions on the stack. This approach allows the functions to refer to all the
619variables in scope for the function containing the @try@ statement. These
620nested functions and all other functions besides @__cfaehm_try_terminate@ in
621\CFA use the GCC personality function and the @-fexceptions@ flag to generate
622the LSDA.
623Using this pattern, \CFA implements destructors with the cleanup attribute.
624
625\begin{figure}
626\begin{cfa}
627try {
628        // TRY BLOCK
629} catch (Exception1 * name1 ; check(name1)) {
630        // CATCH BLOCK 1
631} catch (Exception2 * name2) {
632        // CATCH BLOCK 2
633}
634\end{cfa}
635
636\begin{cfa}
637void try(void) {
638        // TRY BLOCK
639}
640int match(exception_t * __exception_inst) {
641        {
642                Exception1 * name1;
643                if (name1 = (virtual Exception1 *)__exception_inst
644                                && check(name1)) {
645                        return 1;
646                }
647        }
648        {
649                Exception2 * name2;
650                if (name2 = (virtual Exception2 *)__exception_inst) {
651                        return 2;
652                }
653        }
654        return 0;
655}
656void catch(exception_t * __exception_inst, int __handler_index) {
657        switch (__handler_index) {
658        case 1:
659        {
660                Exception1 * name1 = (virtual Exception1 *)__exception_inst;
661                // CATCH BLOCK 1
662        }
663        return;
664        case 2:
665        {
666                Exception2 * name2 = (virtual Exception2 *)__exception_inst;
667                // CATCH BLOCK 2
668        }
669        return;
670        }
671}
672{
673        __cfaehm_try_terminate(try, catch, match);
674}
675\end{cfa}
676
677\caption{Termination Transformation}
678\label{f:TerminationTransformation}
679\todo*{Improve (compress?) Termination Transformations.}
680\end{figure}
681
682\section{Resumption}
683% The stack-local data, the linked list of nodes.
684
685Resumption simpler to implement than termination
686because there is no stack unwinding.
687Instead of storing the data in a special area using assembly,
688there is just a linked list of possible handlers for each stack,
689with each node on the list reperenting a try statement on the stack.
690
691The head of the list is stored in the exception context.
692The nodes are stored in order, with the more recent try statements closer
693to the head of the list.
694Instead of traversing the stack resumption handling traverses the list.
695At each node the EHM checks to see if the try statement the node repersents
696can handle the exception. If it can, then the exception is handled and
697the operation finishes, otherwise the search continues to the next node.
698If the search reaches the end of the list without finding a try statement
699that can handle the exception the default handler is executed and the
700operation finishes.
701
702In each node is a handler function which does most of the work there.
703The handler function is passed the raised the exception and returns true
704if the exception is handled and false if it cannot be handled here.
705
706For each @catchResume@ clause the handler function will:
707check to see if the raised exception is a descendant type of the declared
708exception type, if it is and there is a conditional expression then it will
709run the test, if both checks pass the handling code for the clause is run
710and the function returns true, otherwise it moves onto the next clause.
711If this is the last @catchResume@ clause then instead of moving onto
712the next clause the function returns false as no handler could be found.
713
714\begin{figure}
715\begin{cfa}
716try {
717        // TRY BLOCK
718} catchResume (Exception1 * name1 ; check(name1)) {
719        // CATCH BLOCK 1
720} catchResume (Exception2 * name2) {
721        // CATCH BLOCK 2
722}
723\end{cfa}
724
725\begin{cfa}
726bool handle(exception_t * __exception_inst) {
727        {
728                Exception1 * name1;
729                if (name1 = (virtual Exception1 *)__exception_inst
730                                && check(name1)) {
731                        // CATCH BLOCK 1
732                        return 1;
733                }
734        }
735        {
736                Exception2 * name2;
737                if (name2 = (virtual Exception2 *)__exception_inst) {
738                        // CATCH BLOCK 2
739                        return 2;
740                }
741        }
742        return false;
743}
744struct __try_resume_node __resume_node
745        __attribute__((cleanup( __cfaehm_try_resume_cleanup )));
746__cfaehm_try_resume_setup( &__resume_node, handler );
747\end{cfa}
748
749\caption{Resumption Transformation}
750\label{f:ResumptionTransformation}
751\todo*{Improve (compress?) Resumption Transformations.}
752\end{figure}
753
754% Recursive Resumption Stuff:
755Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
756the stack
757already examined, is accomplished by updating the front of the list as the
758search continues. Before the handler at a node is called, the head of the list
759is updated to the next node of the current node. After the search is complete,
760successful or not, the head of the list is reset.
761
762This mechanism means the current handler and every handler that has already
763been checked are not on the list while a handler is run. If a resumption is
764thrown during the handling of another resumption the active handlers and all
765the other handler checked up to this point are not checked again.
766
767This structure also supports new handler added while the resumption is being
768handled. These are added to the front of the list, pointing back along the
769stack -- the first one points over all the checked handlers -- and the ordering
770is maintained.
771
772\begin{figure}
773\input{resumption-marking}
774\caption{Resumption Marking}
775\label{f:ResumptionMarking}
776\todo*{Convert Resumption Marking into a line figure.}
777\end{figure}
778
779\label{p:zero-cost}
780Note, the resumption implementation has a cost for entering/exiting a @try@
781statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
782clauses has zero-cost entry/exit. While resumption does not need the stack
783unwinding and cleanup provided by libunwind, it could use the search phase to
784providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
785to return from a libunwind search without installing a handler or raising an
786error. Although workarounds might be possible, they are beyond the scope of
787this thesis. The current resumption implementation has simplicity in its
788favour.
789% Seriously, just compare the size of the two chapters and then consider
790% that unwind is required knowledge for that chapter.
791
792\section{Finally}
793% Uses destructors and GCC nested functions.
794A finally clause is placed into a GCC nested-function with a unique name,
795and no arguments or return values.
796This nested function is then set as the cleanup
797function of an empty object that is declared at the beginning of a block placed
798around the context of the associated @try@ statement.
799
800The rest is handled by GCC. The try block and all handlers are inside this
801block. At completion, control exits the block and the empty object is cleaned
802up, which runs the function that contains the finally code.
803
804\section{Cancellation}
805% Stack selections, the three internal unwind functions.
806
807Cancellation also uses libunwind to do its stack traversal and unwinding,
808however it uses a different primary function: @_Unwind_ForcedUnwind@. Details
809of its interface can be found in the Section~\vref{s:ForcedUnwind}.
810
811The first step of cancellation is to find the cancelled stack and its type:
812coroutine or thread. Fortunately, the thread library stores the main thread
813pointer and the current thread pointer, and every thread stores a pointer to
814its main coroutine and the coroutine it is currently executing.
815\todo*{Consider adding a description of how threads are coroutines.}
816
817If a the current thread's main and current coroutines are the same then the
818current stack is a thread stack. Furthermore it is easy to compare the
819current thread to the main thread to see if they are the same. And if this
820is not a thread stack then it must be a coroutine stack.
821
822However, if the threading library is not linked, the sequential execution is on
823the main stack. Hence, the entire check is skipped because the weak-symbol
824function is loaded. Therefore, a main thread cancellation is unconditionally
825performed.
826
827Regardless of how the stack is chosen, the stop function and parameter are
828passed to the forced-unwind function. The general pattern of all three stop
829functions is the same: they continue unwinding until the end of stack and
830then preform their transfer.
831
832For main stack cancellation, the transfer is just a program abort.
833
834For coroutine cancellation, the exception is stored on the coroutine's stack,
835and the coroutine context switches to its last resumer. The rest is handled on
836the backside of the resume, which check if the resumed coroutine is
837cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
838and a @CoroutineCancelled@ exception is constructed and loaded with the
839cancelled exception. It is then resumed as a regular exception with the default
840handler coming from the context of the resumption call.
841
842For thread cancellation, the exception is stored on the thread's main stack and
843then context switched to the scheduler. The rest is handled by the thread
844joiner. When the join is complete, the joiner checks if the joined thread is
845cancelled. If cancelled, the exception is retrieved and the joined thread, and
846a @ThreadCancelled@ exception is constructed and loaded with the cancelled
847exception. The default handler is passed in as a function pointer. If it is
848null (as it is for the auto-generated joins on destructor call), the default is
849used, which is a program abort.
850%; which gives the required handling on implicate join.
Note: See TracBrowser for help on using the repository browser.