source: doc/theses/andrew_beach_MMath/implement.tex @ 0a55a53

jacob/cs343-translation
Last change on this file since 0a55a53 was 0a55a53, checked in by Andrew Beach <ajbeach@…>, 5 months ago

Andrew MMath: Implement chapter updated from Peter's focused review.

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