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

ADTast-experimentalenumforall-pointer-decayjacob/cs343-translationpthread-emulationqualifiedEnum
Last change on this file since ba2e8f0 was ba2e8f0, checked in by Andrew Beach <ajbeach@…>, 3 years ago

Andrew MMath: Folded in Peter's updates to the implement chapter.

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