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

enumforall-pointer-decayjacob/cs343-translationnew-ast-unique-expr
Last change on this file since b6749fd was b6749fd, checked in by Peter A. Buhr <pabuhr@…>, 11 months ago

proofread Andrew's implement, performance and future chapters

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