source: doc/theses/andrew_beach_MMath/implement.tex @ 432bffe

ADTast-experimentalenumforall-pointer-decaypthread-emulationqualifiedEnum
Last change on this file since 432bffe was 9cdfa5fb, checked in by Andrew Beach <ajbeach@…>, 3 years ago

Andrew MMath: Used (most of) Gregor's feedback to update the thesis. There are still a few \todo items as well as a general request for examples.

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