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

ADTast-experimentalenumforall-pointer-decayjacob/cs343-translationpthread-emulationqualifiedEnum
Last change on this file since e56eabac was e56eabac, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

proofread implement chapter

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