source: doc/theses/andrew_beach_MMath/implement.tex @ 5a4f1a8

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

Andrew MMath: Folded in feedback into the implement chapter. (6/6 files done.)

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