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

enumforall-pointer-decayjacob/cs343-translationnew-ast-unique-expr
Last change on this file since d02e547 was d02e547, checked in by Andrew Beach <ajbeach@…>, 11 months ago

Andrew MMath: Improvements to implement figures.

  • Property mode set to 100644
File size: 37.0 KB
Line 
1\chapter{Implementation}
2\label{c:implement}
3
4% Local Helpers:
5\newcommand\transformline[1][becomes...]{
6  \hrulefill#1\hrulefill
7  \medskip
8}
9
10The implementation work for this thesis covers the two components: virtual
11system and exceptions. Each component is discussed in detail.
12
13\section{Virtual System}
14\label{s:VirtualSystem}
15% Virtual table rules. Virtual tables, the pointer to them and the cast.
16While the \CFA virtual system currently has only one public feature, virtual
17cast (see the virtual cast feature \vpageref{p:VirtualCast}),
18substantial structure is required to support it,
19and provide features for exception handling and the standard library.
20
21\subsection{Virtual Type}
22Virtual types only have one change to their structure: the addition of a
23pointer to the virtual table, which is called the \emph{virtual-table pointer}.
24Internally, the field is called \snake{virtual_table}.
25The field is fixed after construction. It is always the first field in the
26structure so that its location is always known.
27\todo{Talk about constructors for virtual types (after they are working).}
28
29The virtual table pointer binds an instance of a virtual type
30to a virtual table.
31The pointer is also the table's id and how the system accesses the
32virtual table and the virtual members there.
33
34\subsection{Type Id}
35Every virtual type has a unique id.
36Type ids can be compared for equality,
37which checks if the types reperented are the same,
38or used to access the type's type information.
39The type information currently is only the parent's type id or, if the
40type has no parent, the null pointer.
41
42The id's are implemented as pointers to the type's type information instance.
43Dereferencing the pointer gets the type information.
44The ancestors of a virtual type are found by traversing type ids through
45the type information.
46The information pushes the issue of creating a unique value (for
47the type id) to the problem of creating a unique instance (for type
48information), which the linker can solve.
49
50The advanced linker support is used here to avoid having to create
51a new declaration to attach this data to.
52With C/\CFA's header/implementation file divide for something to appear
53exactly once it must come from a declaration that appears in exactly one
54implementation file; the declarations in header files may exist only once
55they can be included in many different translation units.
56Therefore, structure's declaration will not work.
57Neither will attaching the type information to the virtual table -- although
58a vtable declarations are in implemention files they are not unique, see
59\autoref{ss:VirtualTable}.
60Instead the same type information is generated multiple times and then
61the new attribute \snake{cfa_linkone} is used to removed duplicates.
62
63Type information is constructed as follows:
64\begin{enumerate}
65\item
66Use the type's name to generate a name for the type information structure.
67This is saved so it may be reused.
68\item
69Generate a new structure definition to store the type
70information. The layout is the same in each case, just the parent's type id,
71but the types used change from instance to instance.
72The generated name is used for both this structure and, if relivant, the
73parent pointer.
74If the virtual type is polymorphic then the type information structure is
75polymorphic as well, with the same polymorphic arguments.
76\item
77A seperate name for instances is generated from the type's name.
78\item
79The definition is generated and initialised.
80The parent id is set to the null pointer or to the address of the parent's
81type information instance. Name resolution handles the rest.
82\item
83\CFA's name mangler does its regular name mangling encoding the type of
84the declaration into the instance name. This gives a completely unique name
85including different instances of the same polymorphic type.
86\end{enumerate}
87\todo{The list is making me realise, some of this isn't ordered.}
88
89Writing that code manually, with helper macros for the early name mangling,
90would look like this:
91\begin{cfa}
92struct INFO_TYPE(TYPE) {
93        INFO_TYPE(PARENT) const * parent;
94};
95
96__attribute__((cfa_linkonce))
97INFO_TYPE(TYPE) const INFO_NAME(TYPE) = {
98        &INFO_NAME(PARENT),
99};
100\end{cfa}
101
102\subsubsection{\lstinline{cfa\_linkonce} Attribute}
103% I just realised: This is an extension of the inline keyword.
104% An extension of C's at least, it is very similar to C++'s.
105Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}.
106This attribute is attached to an object or function definition
107(any global declaration with a name and a type)
108allowing it to be defined multiple times.
109All matching definitions mush have the link-once attribute
110and their implementations should be identical as well.
111
112A single definition with the attribute can be included in a header
113file as if it was a forward declaration, except no definition is required.
114
115This technique is used for type-id instances. A link-once definition is
116generated each time the structure is seen. This will result in multiple
117copies but the link-once attribute ensures all but one are removed for a
118unique instance.
119
120Internally, @cfa_linkonce@ is replaced with
121@section(".gnu.linkonce.NAME")@ where \texttt{NAME} is replaced by the
122mangled name of the object.
123Any other @section@ attributes are removed from the declaration.
124The prefix \texttt{.gnu.linkonce} in section names is recognized by the
125linker. If two of these sections appear with the same name, including
126everything that comes after the special prefix, then only one is used
127and the other is discarded.
128
129\subsection{Virtual Table}
130\label{ss:VirtualTable}
131Each virtual type has a virtual table type that stores its type id and
132virtual members.
133Each virtual type instance is bound to a table instance that is filled with
134the values of virtual members.
135Both the layout of the fields and their value are decided by the rules given
136below.
137
138The layout always comes in three parts.
139\todo{Add labels to the virtual table layout figure.}
140The first section is just the type id at the head of the table. It is always
141there to ensure that it can be found even when the accessing code does not
142know which virtual type it has.
143The second section are all the virtual members of the parent, in the same
144order as they appear in the parent's virtual table. Note that the type may
145change slightly as references to the ``this" will change. This is limited to
146inside pointers/references and via function pointers so that the size (and
147hence the offsets) are the same.
148The third section is similar to the second except that it is the new virtual
149members introduced at this level in the hierarchy.
150
151\begin{figure}
152\input{vtable-layout}
153\caption{Virtual Table Layout}
154\label{f:VirtualTableLayout}
155\todo*{Improve the Virtual Table Layout diagram.}
156\end{figure}
157
158The first and second sections together mean that every virtual table has a
159prefix that has the same layout and types as its parent virtual table.
160This, combined with the fixed offset to the virtual table pointer, means that
161for any virtual type, it is always safe to access its virtual table and,
162from there, it is safe to check the type id to identify the exact type of the
163underlying object, access any of the virtual members and pass the object to
164any of the method-like virtual members.
165
166When a virtual table is declared, the user decides where to declare it and its
167name. The initialization of the virtual table is entirely automatic based on
168the context of the declaration.
169
170The type id is always fixed; with each virtual table type having
171exactly one possible type id.
172The virtual members are usually filled in by type resolution.
173The best match for a given name and type at the declaration site is used.
174There are two exceptions to that rule: the @size@ field, the type's size,
175is set using a @sizeof@ expression and the @align@ field, the
176type's alignment, is set using an @alignof@ expression.
177
178\subsubsection{Concurrency Integration}
179Coroutines and threads need instances of @CoroutineCancelled@ and
180@ThreadCancelled@ respectively to use all of their functionality. When a new
181data type is declared with @coroutine@ or @thread@, a forward declaration for
182the instance is created as well. The definition of the virtual table is created
183at the definition of the main function.
184
185This is showned through code re-writing in
186\autoref{f:ConcurrencyTypeTransformation} and
187\autoref{f:ConcurrencyMainTransformation}.
188In both cases the original declaration is not modified,
189only new ones are added.
190
191\begin{figure}
192\begin{cfa}
193coroutine Example {
194        // fields
195};
196\end{cfa}
197
198\transformline[appends...]
199
200\begin{cfa}
201__attribute__((cfa_linkonce))
202struct __cfatid_struct_CoroutineCancelled(Example)
203                __cfatid_CoroutineCancelled = {
204        &EXCEPTION_TYPE_ID,
205};
206extern CoroutineCancelled_vtable _default_vtable_object_declaration;
207extern CoroutineCancelled_vtable & _default_vtable;
208\end{cfa}
209\caption{Concurrency Type Transformation}
210\label{f:ConcurrencyTypeTransformation}
211\end{figure}
212
213\begin{figure}
214\begin{cfa}
215void main(Example & this) {
216        // body
217}
218\end{cfa}
219
220\transformline[appends...]
221
222\begin{cfa}
223CoroutineCancelled_vtable _default_vtable_object_declaration = {
224        __cfatid_CoroutineCancelled,
225        // Virtual member initialization.
226};
227
228CoroutineCancelled_vtable & _default_vtable =
229        &_default_vtable_object_declaration;
230\end{cfa}
231\caption{Concurrency Main Transformation}
232\label{f:ConcurrencyMainTransformation}
233\end{figure}
234
235\subsection{Virtual Cast}
236Virtual casts are implemented as a function call that does the subtype check
237and a C coercion-cast to do the type conversion.
238% The C-cast is just to make sure the generated code is correct so the rest of
239% the section is about that function.
240The function is implemented in the standard library and has the following
241signature:
242\begin{cfa}
243void * __cfa__virtual_cast(
244        struct __cfavir_type_td parent,
245        struct __cfavir_type_id const * child );
246\end{cfa}
247The type id of target type of the virtual cast is passed in as @parent@ and
248the cast target is passed in as @child@.
249
250For generated C code wraps both arguments and the result with type casts.
251There is also an internal check inside the compiler to make sure that the
252target type is a virtual type.
253% It also checks for conflicting definitions.
254
255The virtual cast either returns the original pointer or the null pointer
256as the new type.
257So the function does the parent check and returns the appropriate value.
258The parent check is a simple linear search of child's ancestors using the
259type information.
260
261\section{Exceptions}
262% Anything about exception construction.
263
264\section{Unwinding}
265% Adapt the unwind chapter, just describe the sections of libunwind used.
266% Mention that termination and cancellation use it. Maybe go into why
267% resumption doesn't as well.
268
269% Many modern languages work with an internal stack that function push and pop
270% their local data to. Stack unwinding removes large sections of the stack,
271% often across functions.
272
273Stack unwinding is the process of removing stack frames (activations) from the
274stack. On function entry and return, unwinding is handled directly by the
275call/return code embedded in the function.
276In many cases, the position of the instruction pointer (relative to parameter
277and local declarations) is enough to know the current size of the stack
278frame.
279
280Usually, the stack-frame size is known statically based on parameter and
281local variable declarations. Even with dynamic stack-size, the information
282to determine how much of the stack has to be removed is still contained
283within the function.
284Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
285bumping the hardware stack-pointer up or down as needed.
286Constructing/destructing values within a stack frame has
287a similar complexity but can add additional work and take longer.
288
289Unwinding across multiple stack frames is more complex because that
290information is no longer contained within the current function.
291With seperate compilation a function has no way of knowing what its callers
292are so it can't know how large those frames are.
293Without altering the main code path it is also hard to pass that work off
294to the caller.
295
296The traditional unwinding mechanism for C is implemented by saving a snap-shot
297of a function's state with @setjmp@ and restoring that snap-shot with
298@longjmp@. This approach bypasses the need to know stack details by simply
299reseting to a snap-shot of an arbitrary but existing function frame on the
300stack. It is up to the programmer to ensure the snap-shot is valid when it is
301reset and that all required clean-up from the unwound stacks is performed.
302This approach is fragile and requires extra work in the surrounding code.
303
304With respect to the extra work in the surounding code,
305many languages define clean-up actions that must be taken when certain
306sections of the stack are removed. Such as when the storage for a variable
307is removed from the stack or when a try statement with a finally clause is
308(conceptually) popped from the stack.
309None of these should be handled by the user --- that would contradict the
310intention of these features --- so they need to be handled automatically.
311
312To safely remove sections of the stack, the language must be able to find and
313run these clean-up actions even when removing multiple functions unknown at
314the beginning of the unwinding.
315
316One of the most popular tools for stack management is libunwind, a low-level
317library that provides tools for stack walking, handler execution, and
318unwinding. What follows is an overview of all the relevant features of
319libunwind needed for this work, and how \CFA uses them to implement exception
320handling.
321
322\subsection{libunwind Usage}
323Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
324provides \Cpp-style stack-unwinding. Its operation is divided into two phases:
325search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
326stack and decide where unwinding should stop (but no unwinding occurs). The
327cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
328
329To use libunwind, each function must have a personality function and a Language
330Specific Data Area (LSDA). The LSDA has the unique information for each
331function to tell the personality function where a function is executing, its
332current stack frame, and what handlers should be checked. Theoretically, the
333LSDA can contain any information but conventionally it is a table with entries
334representing regions of a function and what has to be done there during
335unwinding. These regions are bracketed by instruction addresses. If the
336instruction pointer is within a region's start/end, then execution is currently
337executing in that region. Regions are used to mark out the scopes of objects
338with destructors and try blocks.
339
340% Libunwind actually does very little, it simply moves down the stack from
341% function to function. Most of the actions are implemented by the personality
342% function which libunwind calls on every function. Since this is shared across
343% many functions or even every function in a language it will need a bit more
344% information.
345
346The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
347attaches a personality function to each function.
348In plain C (which \CFA currently compiles down to) this
349flag only handles the cleanup attribute:
350\begin{cfa}
351void clean_up( int * var ) { ... }
352int avar __attribute__(( cleanup(clean_up) ));
353\end{cfa}
354The attribute is used on a variable and specifies a function,
355in this case @clean_up@, run when the variable goes out of scope.
356This feature is enough to mimic destructors,
357but not try statements which can effect
358the unwinding.
359
360To get full unwinding support, all of these features must be handled directly
361in assembly and assembler directives; partiularly the cfi directives
362\snake{.cfi_lsda} and \snake{.cfi_personality}.
363
364\subsection{Personality Functions}
365Personality functions have a complex interface specified by libunwind. This
366section covers some of the important parts of the interface.
367
368A personality function can perform different actions depending on how it is
369called.
370\begin{lstlisting}
371typedef _Unwind_Reason_Code (*_Unwind_Personality_Fn) (
372        _Unwind_Action action,
373        _Unwind_Exception_Class exception_class,
374        _Unwind_Exception * exception,
375        struct _Unwind_Context * context);
376\end{lstlisting}
377The @action@ argument is a bitmask of possible actions:
378\begin{enumerate}[topsep=5pt]
379\item
380@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
381to check for handlers. If there is a handler in a stack frame, as defined by
382the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
383it return @_URC_CONTINUE_UNWIND@.
384
385\item
386@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
387unwound and all cleanup code is run. The personality function does whatever
388cleanup the language defines (such as running destructors/finalizers) and then
389generally returns @_URC_CONTINUE_UNWIND@.
390
391\item
392\begin{sloppypar}
393@_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a
394handler. The personality function must prepare to return to normal code
395execution and return @_URC_INSTALL_CONTEXT@.
396\end{sloppypar}
397
398\item
399@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
400the cleanup phase and uses a different means to decide when to stop
401(see \vref{s:ForcedUnwind}).
402\end{enumerate}
403
404The @exception_class@ argument is a copy of the
405\code{C}{exception}'s @exception_class@ field,
406which is a number that identifies the exception handling mechanism
407that created the exception.
408
409The \code{C}{exception} argument is a pointer to a user
410provided storage object. It has two public fields: the @exception_class@,
411which is described above, and the @exception_cleanup@ function.
412The clean-up function is used by the EHM to clean-up the exception, if it
413should need to be freed at an unusual time, it takes an argument that says
414why it had to be cleaned up.
415
416The @context@ argument is a pointer to an opaque type passed to helper
417functions called inside the personality function.
418
419The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
420that can be passed several places in libunwind. It includes a number of
421messages for special cases (some of which should never be used by the
422personality function) and error codes. However, unless otherwise noted, the
423personality function always returns @_URC_CONTINUE_UNWIND@.
424
425\subsection{Raise Exception}
426Raising an exception is the central function of libunwind and it performs
427two-staged unwinding.
428\begin{cfa}
429_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
430\end{cfa}
431First, the function begins the search phase, calling the personality function
432of the most recent stack frame. It continues to call personality functions
433traversing the stack from newest to oldest until a function finds a handler or
434the end of the stack is reached. In the latter case, raise exception returns
435@_URC_END_OF_STACK@.
436
437Second, when a handler is matched, raise exception moves to the clean-up
438phase and walks the stack a second time.
439Once again, it calls the personality functions of each stack frame from newest
440to oldest. This pass stops at the stack frame containing the matching handler.
441If that personality function has not install a handler, it is an error.
442
443If an error is encountered, raise exception returns either
444@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
445error occurred.
446
447\subsection{Forced Unwind}
448\label{s:ForcedUnwind}
449Forced Unwind is the other central function in libunwind.
450\begin{cfa}
451_Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *,
452        _Unwind_Stop_Fn, void *);
453\end{cfa}
454It also unwinds the stack but it does not use the search phase. Instead another
455function, the stop function, is used to stop searching. The exception is the
456same as the one passed to raise exception. The extra arguments are the stop
457function and the stop parameter. The stop function has a similar interface as a
458personality function, except it is also passed the stop parameter.
459\begin{lstlisting}
460typedef _Unwind_Reason_Code (*_Unwind_Stop_Fn)(
461        _Unwind_Action action,
462        _Unwind_Exception_Class exception_class,
463        _Unwind_Exception * exception,
464        struct _Unwind_Context * context,
465        void * stop_parameter);
466\end{lstlisting}
467
468The stop function is called at every stack frame before the personality
469function is called and then once more after all frames of the stack are
470unwound.
471
472Each time it is called, the stop function should return @_URC_NO_REASON@ or
473transfer control directly to other code outside of libunwind. The framework
474does not provide any assistance here.
475
476\begin{sloppypar}
477Its arguments are the same as the paired personality function. The actions
478\snake{_UA_CLEANUP_PHASE} and \snake{_UA_FORCE_UNWIND} are always set when it is
479called. Beyond the libunwind standard, both GCC and Clang add an extra action
480on the last call at the end of the stack: \snake{_UA_END_OF_STACK}.
481\end{sloppypar}
482
483\section{Exception Context}
484% Should I have another independent section?
485% There are only two things in it, top_resume and current_exception. How it is
486% stored changes depending on whether or not the thread-library is linked.
487
488The exception context is global storage used to maintain data across different
489exception operations and to communicate among different components.
490
491Each stack must have its own exception context. In a sequential \CFA program,
492there is only one stack with a single global exception-context. However, when
493the library @libcfathread@ is linked, there are multiple stacks and each
494needs its own exception context.
495
496The exception context should be retrieved by calling the function
497\snake{this_exception_context}.
498For sequential execution, this function is defined as
499a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
500concurrent, it links with @libcfathread@, where this function is defined with a
501strong symbol replacing the sequential version.
502
503The sequential @this_exception_context@ returns a hard-coded pointer to the
504global exception context.
505The concurrent version adds the exception context to the data stored at the
506base of each stack. When @this_exception_context@ is called, it retrieves the
507active stack and returns the address of the context saved there.
508
509\section{Termination}
510% Memory management & extra information, the custom function used to implement
511% catches. Talk about GCC nested functions.
512
513\CFA termination exceptions use libunwind heavily because they match
514\Cpp exceptions closely. The main complication for \CFA is that the
515compiler generates C code, making it very difficult to generate the assembly to
516form the LSDA for try blocks or destructors.
517
518\subsection{Memory Management}
519The first step of a termination raise is to copy the exception into memory
520managed by the exception system. Currently, the system uses @malloc@, rather
521than reserved memory or the stack top. The exception handling mechanism manages
522memory for the exception as well as memory for libunwind and the system's own
523per-exception storage.
524
525\begin{figure}
526\centering
527\input{exception-layout}
528\caption{Exception Layout}
529\label{f:ExceptionLayout}
530\end{figure}
531
532Exceptions are stored in variable-sized blocks
533(see \autoref{f:ExceptionLayout}).
534The first component is a fixed-sized data structure that contains the
535information for libunwind and the exception system. The second component is an
536area of memory big enough to store the exception. Macros with pointer arthritic
537and type cast are used to move between the components or go from the embedded
538@_Unwind_Exception@ to the entire node.
539
540Multiple exceptions can exist at the same time because exceptions can be
541raised inside handlers, destructors and finally blocks.
542Figure~\vref{f:MultipleExceptions} shows a program that has multiple
543exceptions active at one time.
544Each time an exception is thrown and caught the stack unwinds and the finally
545clause runs. This handler throws another exception (until @num_exceptions@ gets
546high enough), which must be allocated. The previous exceptions may not be
547freed because the handler/catch clause has not been run.
548Therefore, the EHM must keep all unhandled exceptions alive
549while it allocates exceptions for new throws.
550
551\begin{figure}
552\centering
553\newsavebox{\codeBox}
554\newsavebox{\stackBox}
555\begin{lrbox}{\codeBox}
556\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
557unsigned num_exceptions = 0;
558void throws() {
559    try {
560        try {
561            ++num_exceptions;
562            throw (Example){table};
563        } finally {
564            if (num_exceptions < 3) {
565                throws();
566            }
567        }
568    } catch (exception_t *) {
569        --num_exceptions;
570    }
571}
572int main() {
573    throws();
574}
575\end{lstlisting}
576\end{lrbox}
577
578\begin{lrbox}{\stackBox}
579\begin{lstlisting}
580| try-finally
581| try-catch (Example)
582throws()
583| try-finally
584| try-catch (Example)
585throws()
586| try-finally
587| try-catch (Example)
588throws()
589main()
590\end{lstlisting}
591\end{lrbox}
592
593{\usebox\codeBox}
594\hspace{25pt}
595{\usebox\stackBox}
596
597\caption{Multiple Exceptions}
598\label{f:MultipleExceptions}
599\end{figure}
600\todo*{Work on multiple exceptions code sample.}
601
602All exceptions are stored in nodes, which are then linked together in lists
603one list per stack, with the
604list head stored in the exception context. Within each linked list, the most
605recently thrown exception is at the head followed by older thrown
606exceptions. This format allows exceptions to be thrown, while a different
607exception is being handled. The exception at the head of the list is currently
608being handled, while other exceptions wait for the exceptions before them to be
609handled and removed.
610
611The virtual members in the exception's virtual table provide the size of the
612exception, the copy function, and the free function, so they are specific to an
613exception type. The size and copy function are used immediately to copy an
614exception into managed memory. After the exception is handled, the free
615function is used to clean up the exception and then the entire node is
616passed to free, returning the memory back to the heap.
617
618\subsection{Try Statements and Catch Clauses}
619The try statement with termination handlers is complex because it must
620compensate for the C code-generation versus
621assembly-code generated from \CFA. Libunwind
622requires an LSDA and personality function for control to unwind across a
623function. The LSDA in particular is hard to mimic in generated C code.
624
625The workaround is a function called @__cfaehm_try_terminate@ in the standard
626library. The contents of a try block and the termination handlers are converted
627into functions. These are then passed to the try terminate function and it
628calls them.
629Because this function is known and fixed (and not an arbitrary function that
630happens to contain a try statement), the LSDA can be generated ahead
631of time.
632
633Both the LSDA and the personality function are set ahead of time using
634embedded assembly. This assembly code is handcrafted using C @asm@ statements
635and contains
636enough information for a single try statement the function repersents.
637
638The three functions passed to try terminate are:
639\begin{description}
640\item[try function:] This function is the try block, it is where all the code
641from inside the try block is placed. It takes no parameters and has no
642return value. This function is called during regular execution to run the try
643block.
644
645\item[match function:] This function is called during the search phase and
646decides if a catch clause matches the termination exception. It is constructed
647from the conditional part of each handler and runs each check, top to bottom,
648in turn, first checking to see if the exception type matches and then if the
649condition is true. It takes a pointer to the exception and returns 0 if the
650exception is not handled here. Otherwise the return value is the id of the
651handler that matches the exception.
652
653\item[handler function:] This function handles the exception, and contains
654all the code from the handlers in the try statement, joined with a switch
655statement on the handler's id.
656It takes a
657pointer to the exception and the handler's id and returns nothing. It is called
658after the cleanup phase.
659\end{description}
660All three functions are created with GCC nested functions. GCC nested functions
661can be used to create closures,
662in other words functions that can refer to the state of other
663functions on the stack. This approach allows the functions to refer to all the
664variables in scope for the function containing the @try@ statement. These
665nested functions and all other functions besides @__cfaehm_try_terminate@ in
666\CFA use the GCC personality function and the @-fexceptions@ flag to generate
667the LSDA.
668Using this pattern, \CFA implements destructors with the cleanup attribute.
669
670\autoref{f:TerminationTransformation} shows the pattern used to transform
671a \CFA try statement with catch clauses into the approprate C functions.
672\todo{Explain the Termination Transformation figure.}
673
674\begin{figure}
675\begin{cfa}
676try {
677        // TRY BLOCK
678} catch (Exception1 * name1 ; check(name1)) {
679        // CATCH BLOCK 1
680} catch (Exception2 * name2) {
681        // CATCH BLOCK 2
682}
683\end{cfa}
684
685\transformline
686
687\begin{cfa}
688void try(void) {
689        // TRY BLOCK
690}
691int match(exception_t * __exception_inst) {
692        {
693                Exception1 * name1;
694                if (name1 = (virtual Exception1 *)__exception_inst
695                                && check(name1)) {
696                        return 1;
697                }
698        }
699        {
700                Exception2 * name2;
701                if (name2 = (virtual Exception2 *)__exception_inst) {
702                        return 2;
703                }
704        }
705        return 0;
706}
707void catch(exception_t * __exception_inst, int __handler_index) {
708        switch (__handler_index) {
709        case 1:
710        {
711                Exception1 * name1 = (virtual Exception1 *)__exception_inst;
712                // CATCH BLOCK 1
713        }
714        return;
715        case 2:
716        {
717                Exception2 * name2 = (virtual Exception2 *)__exception_inst;
718                // CATCH BLOCK 2
719        }
720        return;
721        }
722}
723{
724        __cfaehm_try_terminate(try, catch, match);
725}
726\end{cfa}
727
728\caption{Termination Transformation}
729\label{f:TerminationTransformation}
730\todo*{Improve (compress?) Termination Transformations.}
731\end{figure}
732
733\section{Resumption}
734% The stack-local data, the linked list of nodes.
735
736Resumption is simpler to implement than termination
737because there is no stack unwinding.
738Instead of storing the data in a special area using assembly,
739there is just a linked list of possible handlers for each stack,
740with each node on the list reperenting a try statement on the stack.
741
742The head of the list is stored in the exception context.
743The nodes are stored in order, with the more recent try statements closer
744to the head of the list.
745Instead of traversing the stack, resumption handling traverses the list.
746At each node, the EHM checks to see if the try statement the node repersents
747can handle the exception. If it can, then the exception is handled and
748the operation finishes, otherwise the search continues to the next node.
749If the search reaches the end of the list without finding a try statement
750that can handle the exception, the default handler is executed and the
751operation finishes.
752
753Each node has a handler function that does most of the work.
754The handler function is passed the raised exception and returns true
755if the exception is handled and false otherwise.
756
757The handler function checks each of its internal handlers in order,
758top-to-bottom, until it funds a match. If a match is found that handler is
759run, after which the function returns true, ignoring all remaining handlers.
760If no match is found the function returns false.
761The match is performed in two steps, first a virtual cast is used to see
762if the thrown exception is an instance of the declared exception or one of
763its descendant type, then check to see if passes the custom predicate if one
764is defined. This ordering gives the type guarantee used in the predicate.
765
766\autoref{f:ResumptionTransformation} shows the pattern used to transform
767a \CFA try statement with catch clauses into the approprate C functions.
768\todo{Explain the Resumption Transformation figure.}
769
770\begin{figure}
771\begin{cfa}
772try {
773        // TRY BLOCK
774} catchResume (Exception1 * name1 ; check(name1)) {
775        // CATCH BLOCK 1
776} catchResume (Exception2 * name2) {
777        // CATCH BLOCK 2
778}
779\end{cfa}
780
781\transformline
782
783\begin{cfa}
784bool handle(exception_t * __exception_inst) {
785        {
786                Exception1 * name1;
787                if (name1 = (virtual Exception1 *)__exception_inst
788                                && check(name1)) {
789                        // CATCH BLOCK 1
790                        return 1;
791                }
792        }
793        {
794                Exception2 * name2;
795                if (name2 = (virtual Exception2 *)__exception_inst) {
796                        // CATCH BLOCK 2
797                        return 2;
798                }
799        }
800        return false;
801}
802struct __try_resume_node __resume_node
803        __attribute__((cleanup( __cfaehm_try_resume_cleanup )));
804__cfaehm_try_resume_setup( &__resume_node, handler );
805\end{cfa}
806
807\caption{Resumption Transformation}
808\label{f:ResumptionTransformation}
809\todo*{Improve (compress?) Resumption Transformations.}
810\end{figure}
811
812% Recursive Resumption Stuff:
813\autoref{f:ResumptionMarking} shows search skipping
814(see \vpageref{s:ResumptionMarking}), which ignores parts of
815the stack
816already examined, is accomplished by updating the front of the list as the
817search continues. Before the handler at a node is called, the head of the list
818is updated to the next node of the current node. After the search is complete,
819successful or not, the head of the list is reset.
820% No paragraph?
821This mechanism means the current handler and every handler that has already
822been checked are not on the list while a handler is run. If a resumption is
823thrown during the handling of another resumption, the active handlers and all
824the other handler checked up to this point are not checked again.
825% No paragraph?
826This structure also supports new handlers added while the resumption is being
827handled. These are added to the front of the list, pointing back along the
828stack --- the first one points over all the checked handlers ---
829and the ordering is maintained.
830
831\begin{figure}
832\input{resumption-marking}
833\caption{Resumption Marking}
834\label{f:ResumptionMarking}
835\todo*{Label Resumption Marking to aid clarity.}
836\end{figure}
837
838\label{p:zero-cost}
839Finally, 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, thread or main thread.
872In \CFA, a thread (the construct the user works with) is a user-level thread
873(point of execution) paired with a coroutine, the thread's main coroutine.
874The thread library also stores pointers to the main thread and the current
875thread.
876If the current thread's main and current coroutines are the same then the
877current stack is a thread stack, otherwise it is a coroutine stack.
878If the current stack is a thread stack, it is also the main thread stack
879if and only if the main and current threads are the same.
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, 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: continue unwinding until the end of stack and
889then preform the appropriate 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 checks 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.