source: doc/theses/andrew_beach_MMath/implement.tex @ 9b0bb79

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

Andrew MMath: Converted all the ASCII diagrams to xfig diagrams.

  • Property mode set to 100644
File size: 35.5 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\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\texttt{.cfi\_lsda} and \texttt{.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@_UA_CLEANUP_PHASE@ and @_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: @_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@this_exception_context@. For sequential execution, this function is defined as
459a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
460concurrent, it links with @libcfathread@, where this function is defined with a
461strong symbol replacing the sequential version.
462
463The sequential @this_exception_context@ returns a hard-coded pointer to the
464global exception context.
465The concurrent version adds the exception context to the data stored at the
466base of each stack. When @this_exception_context@ is called, it retrieves the
467active stack and returns the address of the context saved there.
468
469\section{Termination}
470% Memory management & extra information, the custom function used to implement
471% catches. Talk about GCC nested functions.
472
473\CFA termination exceptions use libunwind heavily because they match \Cpp
474\Cpp exceptions closely. The main complication for \CFA is that the
475compiler generates C code, making it very difficult to generate the assembly to
476form the LSDA for try blocks or destructors.
477
478\subsection{Memory Management}
479The first step of a termination raise is to copy the exception into memory
480managed by the exception system. Currently, the system uses @malloc@, rather
481than reserved memory or the stack top. The exception handling mechanism manages
482memory for the exception as well as memory for libunwind and the system's own
483per-exception storage.
484
485\begin{figure}
486\input{exception-layout}
487\caption{Exception Layout}
488\label{f:ExceptionLayout}
489\end{figure}
490\todo*{Convert the exception layout to an actual diagram.}
491
492Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}).
493The first component is a fixed-sized data structure that contains the
494information for libunwind and the exception system. The second component is an
495area of memory big enough to store the exception. Macros with pointer arthritic
496and type cast are used to move between the components or go from the embedded
497@_Unwind_Exception@ to the entire node.
498
499Multipe exceptions can exist at the same time because exceptions can be
500raised inside handlers, destructors and finally blocks.
501Figure~\vref{f:MultipleExceptions} shows a program that has multiple
502exceptions active at one time.
503Each time an exception is thrown and caught the stack unwinds and the finally
504clause runs. This will throw another exception (until @num_exceptions@ gets
505high enough) which must be allocated. The previous exceptions may not be
506freed because the handler/catch clause has not been run.
507So the EHM must keep them alive while it allocates exceptions for new throws.
508
509\begin{figure}
510\centering
511\newsavebox{\codeBox}
512\newsavebox{\stackBox}
513\begin{lrbox}{\codeBox}
514\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
515unsigned num_exceptions = 0;
516void throws() {
517    try {
518        try {
519            ++num_exceptions;
520            throw (Example){table};
521        } finally {
522            if (num_exceptions < 3) {
523                throws();
524            }
525        }
526    } catch (exception_t *) {
527        --num_exceptions;
528    }
529}
530int main() {
531    throws();
532}
533\end{lstlisting}
534\end{lrbox}
535
536\begin{lrbox}{\stackBox}
537\begin{lstlisting}
538| try-finally
539| try-catch (Example)
540throws()
541| try-finally
542| try-catch (Example)
543throws()
544| try-finally
545| try-catch (Example)
546throws()
547main()
548\end{lstlisting}
549\end{lrbox}
550
551{\usebox\codeBox}
552\hspace{25pt}
553{\usebox\stackBox}
554
555\caption{Multiple Exceptions}
556\label{f:MultipleExceptions}
557\end{figure}
558\todo*{Work on multiple exceptions code sample.}
559
560All exceptions are stored in nodes which are then linked together in lists,
561one list per stack, with the
562list head stored in the exception context. Within each linked list, the most
563recently thrown exception is at the head followed by older thrown
564exceptions. This format allows exceptions to be thrown, while a different
565exception is being handled. The exception at the head of the list is currently
566being handled, while other exceptions wait for the exceptions before them to be
567removed.
568
569The virtual members in the exception's virtual table provide the size of the
570exception, the copy function, and the free function, so they are specific to an
571exception type. The size and copy function are used immediately to copy an
572exception into managed memory. After the exception is handled, the free
573function is used to clean up the exception and then the entire node is
574passed to free so the memory can be given back to the heap.
575
576\subsection{Try Statements and Catch Clauses}
577The try statement with termination handlers is complex because it must
578compensate for the lack of assembly-code generated from \CFA. Libunwind
579requires an LSDA and personality function for control to unwind across a
580function. The LSDA in particular is hard to mimic in generated C code.
581
582The workaround is a function called @__cfaehm_try_terminate@ in the standard
583library. The contents of a try block and the termination handlers are converted
584into functions. These are then passed to the try terminate function and it
585calls them.
586Because this function is known and fixed (and not an arbitrary function that
587happens to contain a try statement), the LSDA can be generated ahead
588of time.
589
590Both the LSDA and the personality function are set ahead of time using
591embedded assembly. This assembly code is handcrafted using C @asm@ statements
592and contains
593enough information for the single try statement the function repersents.
594
595The three functions passed to try terminate are:
596\begin{description}
597\item[try function:] This function is the try block, all the code inside the
598try block is placed inside the try function. It takes no parameters and has no
599return value. This function is called during regular execution to run the try
600block.
601
602\item[match function:] This function is called during the search phase and
603decides if a catch clause matches the termination exception. It is constructed
604from the conditional part of each handler and runs each check, top to bottom,
605in turn, first checking to see if the exception type matches and then if the
606condition is true. It takes a pointer to the exception and returns 0 if the
607exception is not handled here. Otherwise the return value is the id of the
608handler that matches the exception.
609
610\item[handler function:] This function handles the exception. It takes a
611pointer to the exception and the handler's id and returns nothing. It is called
612after the cleanup phase. It is constructed by stitching together the bodies of
613each handler and dispatches to the selected handler.
614\end{description}
615All three functions are created with GCC nested functions. GCC nested functions
616can be used to create closures, functions that can refer to the state of other
617functions on the stack. This approach allows the functions to refer to all the
618variables in scope for the function containing the @try@ statement. These
619nested functions and all other functions besides @__cfaehm_try_terminate@ in
620\CFA use the GCC personality function and the @-fexceptions@ flag to generate
621the LSDA.
622Using this pattern, \CFA implements destructors with the cleanup attribute.
623
624\begin{figure}
625\begin{cfa}
626try {
627        // TRY BLOCK
628} catch (Exception1 * name1 ; check(name1)) {
629        // CATCH BLOCK 1
630} catch (Exception2 * name2) {
631        // CATCH BLOCK 2
632}
633\end{cfa}
634
635\begin{cfa}
636void try(void) {
637        // TRY BLOCK
638}
639int match(exception_t * __exception_inst) {
640        {
641                Exception1 * name1;
642                if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) {
643                        return 1;
644                }
645        }
646        {
647                Exception2 * name2;
648                if (name2 = (virtual Exception2 *)__exception_inst) {
649                        return 2;
650                }
651        }
652        return 0;
653}
654void catch(exception_t * __exception_inst, int __handler_index) {
655        switch (__handler_index) {
656        case 1:
657        {
658                Exception1 * name1 = (virtual Exception1 *)__exception_inst;
659                // CATCH BLOCK 1
660        }
661        return;
662        case 2:
663        {
664                Exception2 * name2 = (virtual Exception2 *)__exception_inst;
665                // CATCH BLOCK 2
666        }
667        return;
668        }
669}
670{
671        __cfaehm_try_terminate(try, catch, match);
672}
673\end{cfa}
674
675\caption{Termination Transformation}
676\label{f:TerminationTransformation}
677\todo*{Improve (compress?) Termination Transformations.}
678\end{figure}
679
680\section{Resumption}
681% The stack-local data, the linked list of nodes.
682
683Resumption simpler to implement than termination
684because there is no stack unwinding.
685Instead of storing the data in a special area using assembly,
686there is just a linked list of possible handlers for each stack,
687with each node on the list reperenting a try statement on the stack.
688
689The head of the list is stored in the exception context.
690The nodes are stored in order, with the more recent try statements closer
691to the head of the list.
692Instead of traversing the stack resumption handling traverses the list.
693At each node the EHM checks to see if the try statement the node repersents
694can handle the exception. If it can, then the exception is handled and
695the operation finishes, otherwise the search continues to the next node.
696If the search reaches the end of the list without finding a try statement
697that can handle the exception the default handler is executed and the
698operation finishes.
699
700In each node is a handler function which does most of the work there.
701The handler function is passed the raised the exception and returns true
702if the exception is handled and false if it cannot be handled here.
703
704For each @catchResume@ clause the handler function will:
705check to see if the raised exception is a descendant type of the declared
706exception type, if it is and there is a conditional expression then it will
707run the test, if both checks pass the handling code for the clause is run
708and the function returns true, otherwise it moves onto the next clause.
709If this is the last @catchResume@ clause then instead of moving onto
710the next clause the function returns false as no handler could be found.
711
712\begin{figure}
713\begin{cfa}
714try {
715        // TRY BLOCK
716} catchResume (Exception1 * name1 ; check(name1)) {
717        // CATCH BLOCK 1
718} catchResume (Exception2 * name2) {
719        // CATCH BLOCK 2
720}
721\end{cfa}
722
723\begin{cfa}
724bool handle(exception_t * __exception_inst) {
725        {
726                Exception1 * name1;
727                if (name1 = (virtual Exception1 *)__exception_inst && check(name1)) {
728                        // CATCH BLOCK 1
729                        return 1;
730                }
731        }
732        {
733                Exception2 * name2;
734                if (name2 = (virtual Exception2 *)__exception_inst) {
735                        // CATCH BLOCK 2
736                        return 2;
737                }
738        }
739        return false;
740}
741struct __try_resume_node __resume_node
742        __attribute__((cleanup( __cfaehm_try_resume_cleanup )));
743__cfaehm_try_resume_setup( &__resume_node, handler );
744\end{cfa}
745
746\caption{Resumption Transformation}
747\label{f:ResumptionTransformation}
748\todo*{Improve (compress?) Resumption Transformations.}
749\end{figure}
750
751% Recursive Resumption Stuff:
752Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
753the stack
754already examined, is accomplished by updating the front of the list as the
755search continues. Before the handler at a node is called, the head of the list
756is updated to the next node of the current node. After the search is complete,
757successful or not, the head of the list is reset.
758
759This mechanism means the current handler and every handler that has already
760been checked are not on the list while a handler is run. If a resumption is
761thrown during the handling of another resumption the active handlers and all
762the other handler checked up to this point are not checked again.
763
764This structure also supports new handler added while the resumption is being
765handled. These are added to the front of the list, pointing back along the
766stack -- the first one points over all the checked handlers -- and the ordering
767is maintained.
768
769\begin{figure}
770\input{resumption-marking}
771\caption{Resumption Marking}
772\label{f:ResumptionMarking}
773\todo*{Convert Resumption Marking into a line figure.}
774\end{figure}
775
776\label{p:zero-cost}
777Note, the resumption implementation has a cost for entering/exiting a @try@
778statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
779clauses has zero-cost entry/exit. While resumption does not need the stack
780unwinding and cleanup provided by libunwind, it could use the search phase to
781providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
782to return from a libunwind search without installing a handler or raising an
783error. Although workarounds might be possible, they are beyond the scope of
784this thesis. The current resumption implementation has simplicity in its
785favour.
786% Seriously, just compare the size of the two chapters and then consider
787% that unwind is required knowledge for that chapter.
788
789\section{Finally}
790% Uses destructors and GCC nested functions.
791A finally clause is placed into a GCC nested-function with a unique name,
792and no arguments or return values.
793This nested function is then set as the cleanup
794function of an empty object that is declared at the beginning of a block placed
795around the context of the associated @try@ statement.
796
797The rest is handled by GCC. The try block and all handlers are inside this
798block. At completion, control exits the block and the empty object is cleaned
799up, which runs the function that contains the finally code.
800
801\section{Cancellation}
802% Stack selections, the three internal unwind functions.
803
804Cancellation also uses libunwind to do its stack traversal and unwinding,
805however it uses a different primary function: @_Unwind_ForcedUnwind@. Details
806of its interface can be found in the Section~\vref{s:ForcedUnwind}.
807
808The first step of cancellation is to find the cancelled stack and its type:
809coroutine or thread. Fortunately, the thread library stores the main thread
810pointer and the current thread pointer, and every thread stores a pointer to
811its main coroutine and the coroutine it is currently executing.
812\todo*{Consider adding a description of how threads are coroutines.}
813
814If a the current thread's main and current coroutines are the same then the
815current stack is a thread stack. Furthermore it is easy to compare the
816current thread to the main thread to see if they are the same. And if this
817is not a thread stack then it must be a coroutine stack.
818
819However, if the threading library is not linked, the sequential execution is on
820the main stack. Hence, the entire check is skipped because the weak-symbol
821function is loaded. Therefore, a main thread cancellation is unconditionally
822performed.
823
824Regardless of how the stack is chosen, the stop function and parameter are
825passed to the forced-unwind function. The general pattern of all three stop
826functions is the same: they continue unwinding until the end of stack and
827then preform their transfer.
828
829For main stack cancellation, the transfer is just a program abort.
830
831For coroutine cancellation, the exception is stored on the coroutine's stack,
832and the coroutine context switches to its last resumer. The rest is handled on
833the backside of the resume, which check if the resumed coroutine is
834cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
835and a @CoroutineCancelled@ exception is constructed and loaded with the
836cancelled exception. It is then resumed as a regular exception with the default
837handler coming from the context of the resumption call.
838
839For thread cancellation, the exception is stored on the thread's main stack and
840then context switched to the scheduler. The rest is handled by the thread
841joiner. When the join is complete, the joiner checks if the joined thread is
842cancelled. If cancelled, the exception is retrieved and the joined thread, and
843a @ThreadCancelled@ exception is constructed and loaded with the cancelled
844exception. The default handler is passed in as a function pointer. If it is
845null (as it is for the auto-generated joins on destructor call), the default is
846used, which is a program abort.
847%; which gives the required handling on implicate join.
Note: See TracBrowser for help on using the repository browser.