source: doc/theses/andrew_beach_MMath/implement.tex @ 9d7e5cb

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 9d7e5cb was 9d7e5cb, checked in by Andrew Beach <ajbeach@…>, 8 months ago

Andrew MMath: First draft of the latest round of fixes to implement complete. More will be needed.

  • Property mode set to 100644
File size: 32.4 KB
Line 
1\chapter{Implementation}
2% Goes over how all the features are implemented.
3
4The implementation work for this thesis covers two components: the virtual
5system and exceptions. Each component is discussed in detail.
6
7\section{Virtual System}
8\label{s:VirtualSystem}
9% Virtual table rules. Virtual tables, the pointer to them and the cast.
10While the \CFA virtual system currently has only one public feature, virtual
11cast (see the virtual cast feature \vpageref{p:VirtualCast}),
12substantial structure is required to support it,
13and provide features for exception handling and the standard library.
14
15\subsection{Virtual Type}
16Virtual types only have one change to their structure: the addition of a
17pointer to the virtual table, which is called the \emph{virtual-table pointer}.
18Internally, the field is called @virtual_table@.
19The field is fixed after construction. It is always the first field in the
20structure so that its location is always known.
21\todo{Talk about constructors for virtual types (after they are working).}
22
23This is what binds an instance of a virtual type to a virtual table. This
24pointer can be used as an identity check. It can also be used to access the
25virtual table and the virtual members there.
26
27\subsection{Type Id}
28Every virtual type has a unique id.
29Type ids can be compared for equality (the types reperented are the same)
30or used to access the type's type information.
31The type information currently is only the parent's type id or, if the
32type has no parent, zero.
33
34The id's are implemented as pointers to the type's type information instance.
35Derefencing the pointer gets the type information.
36By going back-and-forth between the type id and
37the type info one can find every ancestor of a virtual type.
38It also pushes the issue of creating a unique value (for
39the type id) to the problem of creating a unique instance (for type
40information) which the linker can solve.
41
42Advanced linker support is required because there is no place that appears
43only once to attach the type information to. There should be one structure
44definition but it is included in multiple translation units. Each virtual
45table definition should be unique but there are an arbitrary number of thoses.
46So the special section prefix \texttt{.gnu.linkonce} is used.
47With a unique suffix (making the entire section name unique) the linker will
48remove multiple definition making sure only one version exists after linking.
49Then it is just a matter of making sure there is a unique name for each type.
50
51This is done in three phases.
52The first phase is to generate a new structure definition to store the type
53information. The layout is the same in each case, just the parent's type id,
54but the types are changed.
55The structure's name is change, it is based off the virtual type's name, and
56the type of the parent's type id.
57If the virtual type is polymorphic then the type information structure is
58polymorphic as well, with the same polymorphic arguments.
59
60The second phase is to generate an instance of the type information with a
61almost unique name, generated by mangling the virtual type name.
62
63The third phase is implicit with \CFA's overloading scheme. \CFA mangles
64names with type information so that all of the symbols exported to the linker
65are unique even if in \CFA code they are the same. Having two declarations
66with the same name and same type is forbidden because it is impossible for
67overload resolution to pick between them. This is why a unique type is
68generated for each virtual type.
69Polymorphic information is included in this mangling so polymorphic
70types will have seperate instances for each set of polymorphic arguments.
71
72\begin{cfa}
73struct /* type name */ {
74        /* parent type name */ const * parent;
75};
76
77__attribute__((section(".gnu.linkonce./* instance name */")))
78/* type name */ const /* instance name */ = {
79        &/* parent instance name */,
80};
81\end{cfa}
82
83\subsection{Virtual Table}
84Each virtual type has a virtual table type that stores its type id and
85virtual members.
86Each virtual type instance is bound to a table instance that is filled with
87the values of virtual members.
88Both the layout of the fields and their value are decided by the rules given
89below.
90
91The layout always comes in three parts.
92The first section is just the type id at the head of the table. It is always
93there to ensure that
94The second section are all the virtual members of the parent, in the same
95order as they appear in the parent's virtual table. Note that the type may
96change slightly as references to the ``this" will change. This is limited to
97inside pointers/references and via function pointers so that the size (and
98hence the offsets) are the same.
99The third section is similar to the second except that it is the new virtual
100members introduced at this level in the hierarchy.
101
102\begin{figure}
103\begin{cfa}
104type_id
105parent_field0
106...
107parent_fieldN
108child_field0
109...
110child_fieldN
111\end{cfa}
112\caption{Virtual Table Layout}
113\label{f:VirtualTableLayout}
114\todo*{Improve the Virtual Table Layout diagram.}
115\end{figure}
116
117The first and second sections together mean that every virtual table has a
118prefix that has the same layout and types as its parent virtual table.
119This, combined with the fixed offset to the virtual table pointer, means that
120for any virtual type it doesn't matter if we have it or any of its
121descendants, it is still always safe to access the virtual table through
122the virtual table pointer.
123From there it is safe to check the type id to identify the exact type of the
124underlying object, access any of the virtual members and pass the object to
125any of the method-like virtual members.
126\todo{Introduce method-like virtual members.}
127
128When a virtual table is declared the user decides where to declare it and its
129name. The initialization of the virtual table is entirely automatic based on
130the context of the declaration.
131
132The type id is always fixed, each virtual table type will always have one
133exactly one possible type id.
134The virtual members are usually filled in by resolution. The best match for
135a given name and type at the declaration site is filled in.
136There are two exceptions to that rule: the @size@ field is the type's size
137and is set to the result of a @sizeof@ expression, the @align@ field is the
138type's alignment and similarly uses an @alignof@ expression.
139
140\subsubsection{Concurrency Integration}
141Coroutines and threads need instances of @CoroutineCancelled@ and
142@ThreadCancelled@ respectively to use all of their functionality. When a new
143data type is declared with @coroutine@ or @thread@ the forward declaration for
144the instance is created as well. The definition of the virtual table is created
145at the definition of the main function.
146\todo{Add an example with code snipits.}
147
148\subsection{Virtual Cast}
149Virtual casts are implemented as a function call that does the subtype check
150and a C coercion-cast to do the type conversion.
151% The C-cast is just to make sure the generated code is correct so the rest of
152% the section is about that function.
153The function is implemented in the standard library and has the following
154signature:
155\begin{cfa}
156void * __cfa__virtual_cast(
157        struct __cfa__parent_vtable const * parent,
158        struct __cfa__parent_vtable const * const * child );
159\end{cfa}
160\todo{Get rid of \_\_cfa\_\_parent\_vtable in the standard library and then
161the document.}
162The type id of target type of the virtual cast is passed in as @parent@ and
163the cast target is passed in as @child@.
164
165For C generation both arguments and the result are wrapped with type casts.
166There is also an internal store inside the compiler to make sure that the
167target type is a virtual type.
168% It also checks for conflicting definitions.
169
170The virtual cast either returns the original pointer as a new type or null.
171So the function just does the parent check and returns the approprate value.
172The parent check is a simple linear search of child's ancestors using the
173type information.
174
175\section{Exceptions}
176% Anything about exception construction.
177
178\section{Unwinding}
179% Adapt the unwind chapter, just describe the sections of libunwind used.
180% Mention that termination and cancellation use it. Maybe go into why
181% resumption doesn't as well.
182
183% Many modern languages work with an interal stack that function push and pop
184% their local data to. Stack unwinding removes large sections of the stack,
185% often across functions.
186
187Stack unwinding is the process of removing stack frames (activations) from the
188stack. On function entry and return, unwinding is handled directly by the
189call/return code embedded in the function.
190In many cases the position of the instruction pointer (relative to parameter
191and local declarations) is enough to know the current size of the stack
192frame.
193
194Usually, the stack-frame size is known statically based on parameter and
195local variable declarations. Even with dynamic stack-size the information
196to determain how much of the stack has to be removed is still contained
197within the function.
198Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
199bumping the hardware stack-pointer up or down as needed.
200Constructing/destructing values on the stack takes longer put in terms of
201figuring out what needs to be done is of similar complexity.
202
203Unwinding across multiple stack frames is more complex because that
204information is no longer contained within the current function.
205With seperate compilation a function has no way of knowing what its callers
206are so it can't know how large those frames are.
207Without altering the main code path it is also hard to pass that work off
208to the caller.
209
210The traditional unwinding mechanism for C is implemented by saving a snap-shot
211of a function's state with @setjmp@ and restoring that snap-shot with
212@longjmp@. This approach bypasses the need to know stack details by simply
213reseting to a snap-shot of an arbitrary but existing function frame on the
214stack. It is up to the programmer to ensure the snap-shot is valid when it is
215reset and that all required clean-up from the unwound stacks is preformed.
216This approach is fragile and forces a work onto the surounding code.
217
218With respect to that work forced onto the surounding code,
219many languages define clean-up actions that must be taken when certain
220sections of the stack are removed. Such as when the storage for a variable
221is removed from the stack or when a try statement with a finally clause is
222(conceptually) popped from the stack.
223None of these should be handled by the user, that would contradict the
224intention of these features, so they need to be handled automatically.
225
226To safely remove sections of the stack the language must be able to find and
227run these clean-up actions even when removing multiple functions unknown at
228the beginning of the unwinding.
229
230One of the most popular tools for stack management is libunwind, a low-level
231library that provides tools for stack walking, handler execution, and
232unwinding. What follows is an overview of all the relevant features of
233libunwind needed for this work, and how \CFA uses them to implement exception
234handling.
235
236\subsection{libunwind Usage}
237Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
238provides \Cpp-style stack-unwinding. Its operation is divided into two phases:
239search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
240stack and decide where unwinding should stop (but no unwinding occurs). The
241cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
242
243To use libunwind, each function must have a personality function and a Language
244Specific Data Area (LSDA). The LSDA has the unique information for each
245function to tell the personality function where a function is executing, its
246current stack frame, and what handlers should be checked. Theoretically, the
247LSDA can contain any information but conventionally it is a table with entries
248representing regions of the function and what has to be done there during
249unwinding. These regions are bracketed by instruction addresses. If the
250instruction pointer is within a region's start/end, then execution is currently
251executing in that region. Regions are used to mark out the scopes of objects
252with destructors and try blocks.
253
254% Libunwind actually does very little, it simply moves down the stack from
255% function to function. Most of the actions are implemented by the personality
256% function which libunwind calls on every function. Since this is shared across
257% many functions or even every function in a language it will need a bit more
258% information.
259
260The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
261attaches a personality function to each function.
262In plain C (which \CFA currently compiles down to) this
263flag only handles the cleanup attribute:
264\begin{cfa}
265void clean_up( int * var ) { ... }
266int avar __attribute__(( cleanup(clean_up) ));
267\end{cfa}
268The attribue is used on a variable and specifies a function,
269in this case @clean_up@, run when the variable goes out of scope.
270This is enough to mimic destructors, but not try statements which can effect
271the unwinding.
272
273To get full unwinding support all of this has to be done directly with
274assembly and assembler directives. Partiularly the cfi directives
275\texttt{.cfi\_lsda} and \texttt{.cfi\_personality}.
276
277\subsection{Personality Functions}
278Personality functions have a complex interface specified by libunwind. This
279section covers some of the important parts of the interface.
280
281A personality function can preform different actions depending on how it is
282called.
283\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
284typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) (
285        _Unwind_Action @action@,
286        _Unwind_Exception_Class @exception_class@,
287        _Unwind_Exception * @exception@,
288        struct _Unwind_Context * @context@
289);
290\end{lstlisting}
291The @action@ argument is a bitmask of possible actions:
292\begin{enumerate}[topsep=5pt]
293\item
294@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
295to check for handlers. If there is a handler in a stack frame, as defined by
296the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
297it return @_URC_CONTINUE_UNWIND@.
298
299\item
300@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
301unwound and all cleanup code is run. The personality function does whatever
302cleanup the language defines (such as running destructors/finalizers) and then
303generally returns @_URC_CONTINUE_UNWIND@.
304
305\item
306\begin{sloppypar}
307@_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a
308handler. The personality function must prepare to return to normal code
309execution and return @_URC_INSTALL_CONTEXT@.
310\end{sloppypar}
311
312\item
313@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
314the cleanup phase and uses a different means to decide when to stop
315(see \vref{s:ForcedUnwind}).
316\end{enumerate}
317
318The @exception_class@ argument is a copy of the
319\code{C}{exception}'s @exception_class@ field.
320This a number that identifies the exception handling mechanism that created
321the
322
323The \code{C}{exception} argument is a pointer to the user
324provided storage object. It has two public fields: the @exception_class@,
325which is described above, and the @exception_cleanup@ function.
326The clean-up function is used by the EHM to clean-up the exception if it
327should need to be freed at an unusual time, it takes an argument that says
328why it had to be cleaned up.
329
330The @context@ argument is a pointer to an opaque type passed to helper
331functions called inside the personality function.
332
333The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
334that can be passed several places in libunwind. It includes a number of
335messages for special cases (some of which should never be used by the
336personality function) and error codes. However, unless otherwise noted, the
337personality function should always return @_URC_CONTINUE_UNWIND@.
338
339\subsection{Raise Exception}
340Raising an exception is the central function of libunwind and it performs a
341two-staged unwinding.
342\begin{cfa}
343_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
344\end{cfa}
345First, the function begins the search phase, calling the personality function
346of the most recent stack frame. It continues to call personality functions
347traversing the stack from newest to oldest until a function finds a handler or
348the end of the stack is reached. In the latter case, raise exception returns
349@_URC_END_OF_STACK@.
350
351Second, when a handler is matched, raise exception moves to the clean-up
352phase and walks the stack a second time.
353Once again, it calls the personality functions of each stack frame from newest
354to oldest. This pass stops at the stack frame containing the matching handler.
355If that personality function has not install a handler, it is an error.
356
357If an error is encountered, raise exception returns either
358@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
359error occurred.
360
361\subsection{Forced Unwind}
362\label{s:ForcedUnwind}
363Forced Unwind is the other central function in libunwind.
364\begin{cfa}
365_Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *,
366        _Unwind_Stop_Fn, void *);
367\end{cfa}
368It also unwinds the stack but it does not use the search phase. Instead another
369function, the stop function, is used to stop searching. The exception is the
370same as the one passed to raise exception. The extra arguments are the stop
371function and the stop parameter. The stop function has a similar interface as a
372personality function, except it is also passed the stop parameter.
373\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
374typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)(
375        _Unwind_Action @action@,
376        _Unwind_Exception_Class @exception_class@,
377        _Unwind_Exception * @exception@,
378        struct _Unwind_Context * @context@,
379        void * @stop_parameter@);
380\end{lstlisting}
381
382The stop function is called at every stack frame before the personality
383function is called and then once more after all frames of the stack are
384unwound.
385
386Each time it is called, the stop function should return @_URC_NO_REASON@ or
387transfer control directly to other code outside of libunwind. The framework
388does not provide any assistance here.
389
390\begin{sloppypar}
391Its arguments are the same as the paired personality function. The actions
392@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
393called. Beyond the libunwind standard, both GCC and Clang add an extra action
394on the last call at the end of the stack: @_UA_END_OF_STACK@.
395\end{sloppypar}
396
397\section{Exception Context}
398% Should I have another independent section?
399% There are only two things in it, top_resume and current_exception. How it is
400% stored changes depending on whether or not the thread-library is linked.
401
402The exception context is global storage used to maintain data across different
403exception operations and to communicate among different components.
404
405Each stack must have its own exception context. In a sequential \CFA program,
406there is only one stack with a single global exception-context. However, when
407the library @libcfathread@ is linked, there are multiple stacks and each
408needs its own exception context.
409
410The exception context should be retrieved by calling the function
411@this_exception_context@. For sequential execution, this function is defined as
412a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
413concurrent, it links with @libcfathread@, where this function is defined with a
414strong symbol replacing the sequential version.
415
416The sequential @this_exception_context@ returns a hard-coded pointer to the
417global exception context.
418The concurrent version adds the exception context to the data stored at the
419base of each stack. When @this_exception_context@ is called, it retrieves the
420active stack and returns the address of the context saved there.
421
422\section{Termination}
423% Memory management & extra information, the custom function used to implement
424% catches. Talk about GCC nested functions.
425
426\CFA termination exceptions use libunwind heavily because they match \Cpp
427\Cpp exceptions closely. The main complication for \CFA is that the
428compiler generates C code, making it very difficult to generate the assembly to
429form the LSDA for try blocks or destructors.
430
431\subsection{Memory Management}
432The first step of a termination raise is to copy the exception into memory
433managed by the exception system. Currently, the system uses @malloc@, rather
434than reserved memory or the stack top. The exception handling mechanism manages
435memory for the exception as well as memory for libunwind and the system's own
436per-exception storage.
437
438\begin{figure}
439\begin{verbatim}
440Fixed Header  | _Unwind_Exception   <- pointer target
441              |
442              | Cforall storage
443              |
444Variable Body | the exception       <- fixed offset
445              V ...
446\end{verbatim}
447\caption{Exception Layout}
448\label{f:ExceptionLayout}
449\end{figure}
450\todo*{Convert the exception layout to an actual diagram.}
451
452Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}).
453The first component is a fixed-sized data structure that contains the
454information for libunwind and the exception system. The second component is an
455area of memory big enough to store the exception. Macros with pointer arthritic
456and type cast are used to move between the components or go from the embedded
457@_Unwind_Exception@ to the entire node.
458
459Multipe exceptions can exist at the same time because exceptions can be
460raised inside handlers, destructors and finally blocks.
461Figure~\vref{f:MultipleExceptions} shows a program that has multiple
462exceptions active at one time.
463Each time an exception is thrown and caught the stack unwinds and the finally
464clause runs. This will throw another exception (until @num_exceptions@ gets
465high enough) which must be allocated. The previous exceptions may not be
466freed because the handler/catch clause has not been run.
467So the EHM must keep them alive while it allocates exceptions for new throws.
468
469\begin{figure}
470\centering
471% Andrew: Figure out what these do and give them better names.
472\newsavebox{\myboxA}
473\newsavebox{\myboxB}
474\begin{lrbox}{\myboxA}
475\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}]
476unsigned num_exceptions = 0;
477void throws() {
478    try {
479        try {
480            ++num_exceptions;
481            throw (Example){table};
482        } finally {
483            if (num_exceptions < 3) {
484                throws();
485            }
486        }
487    } catch (exception_t *) {
488        --num_exceptions;
489    }
490}
491int main() {
492    throws();
493}
494\end{lstlisting}
495\end{lrbox}
496
497\begin{lrbox}{\myboxB}
498\begin{lstlisting}
499\end{lstlisting}
500\end{lrbox}
501
502{\usebox\myboxA}
503\hspace{25pt}
504{\usebox\myboxB}
505
506\caption{Multiple Exceptions}
507\label{f:MultipleExceptions}
508\end{figure}
509\todo*{Work on multiple exceptions code sample.}
510
511All exceptions are stored in nodes which are then linked together in lists,
512one list per stack, with the
513list head stored in the exception context. Within each linked list, the most
514recently thrown exception is at the head followed by older thrown
515exceptions. This format allows exceptions to be thrown, while a different
516exception is being handled. The exception at the head of the list is currently
517being handled, while other exceptions wait for the exceptions before them to be
518removed.
519
520The virtual members in the exception's virtual table provide the size of the
521exception, the copy function, and the free function, so they are specific to an
522exception type. The size and copy function are used immediately to copy an
523exception into managed memory. After the exception is handled, the free
524function is used to clean up the exception and then the entire node is
525passed to free so the memory can be given back to the heap.
526
527\subsection{Try Statements and Catch Clauses}
528The try statement with termination handlers is complex because it must
529compensate for the lack of assembly-code generated from \CFA. Libunwind
530requires an LSDA and personality function for control to unwind across a
531function. The LSDA in particular is hard to mimic in generated C code.
532
533The workaround is a function called @__cfaehm_try_terminate@ in the standard
534library. The contents of a try block and the termination handlers are converted
535into functions. These are then passed to the try terminate function and it
536calls them.
537Because this function is known and fixed (and not an arbitrary function that
538happens to contain a try statement), the LSDA can be generated ahead
539of time.
540
541Both the LSDA and the personality function are set ahead of time using
542embedded assembly. This assembly code is handcrafted using C @asm@ statements
543and contains
544enough information for the single try statement the function repersents.
545
546The three functions passed to try terminate are:
547\begin{description}
548\item[try function:] This function is the try block, all the code inside the
549try block is placed inside the try function. It takes no parameters and has no
550return value. This function is called during regular execution to run the try
551block.
552
553\item[match function:] This function is called during the search phase and
554decides if a catch clause matches the termination exception. It is constructed
555from the conditional part of each handler and runs each check, top to bottom,
556in turn, first checking to see if the exception type matches and then if the
557condition is true. It takes a pointer to the exception and returns 0 if the
558exception is not handled here. Otherwise the return value is the id of the
559handler that matches the exception.
560
561\item[handler function:] This function handles the exception. It takes a
562pointer to the exception and the handler's id and returns nothing. It is called
563after the cleanup phase. It is constructed by stitching together the bodies of
564each handler and dispatches to the selected handler.
565\end{description}
566All three functions are created with GCC nested functions. GCC nested functions
567can be used to create closures, functions that can refer to the state of other
568functions on the stack. This approach allows the functions to refer to all the
569variables in scope for the function containing the @try@ statement. These
570nested functions and all other functions besides @__cfaehm_try_terminate@ in
571\CFA use the GCC personality function and the @-fexceptions@ flag to generate
572the LSDA.
573Using this pattern, \CFA implements destructors with the cleanup attribute.
574\todo{Add an example of the conversion from try statement to functions.}
575
576\section{Resumption}
577% The stack-local data, the linked list of nodes.
578
579Resumption simpler to implement than termination
580because there is no stack unwinding.
581Instead of storing the data in a special area using assembly,
582there is just a linked list of possible handlers for each stack,
583with each node on the list reperenting a try statement on the stack.
584
585The head of the list is stored in the exception context.
586The nodes are stored in order, with the more recent try statements closer
587to the head of the list.
588Instead of traversing the stack resumption handling traverses the list.
589At each node the EHM checks to see if the try statement the node repersents
590can handle the exception. If it can, then the exception is handled and
591the operation finishes, otherwise the search continues to the next node.
592If the search reaches the end of the list without finding a try statement
593that can handle the exception the default handler is executed and the
594operation finishes.
595
596In each node is a handler function which does most of the work there.
597The handler function is passed the raised the exception and returns true
598if the exception is handled and false if it cannot be handled here.
599
600For each @catchResume@ clause the handler function will:
601check to see if the raised exception is a descendant type of the declared
602exception type, if it is and there is a conditional expression then it will
603run the test, if both checks pass the handling code for the clause is run
604and the function returns true, otherwise it moves onto the next clause.
605If this is the last @catchResume@ clause then instead of moving onto
606the next clause the function returns false as no handler could be found.
607
608\todo{Diagram showing a try statement being converted into resumption handlers.}
609
610% Recursive Resumption Stuff:
611Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
612the stack
613already examined, is accomplished by updating the front of the list as the
614search continues. Before the handler at a node is called, the head of the list
615is updated to the next node of the current node. After the search is complete,
616successful or not, the head of the list is reset.
617
618This mechanism means the current handler and every handler that has already
619been checked are not on the list while a handler is run. If a resumption is
620thrown during the handling of another resumption the active handlers and all
621the other handler checked up to this point are not checked again.
622
623This structure also supports new handler added while the resumption is being
624handled. These are added to the front of the list, pointing back along the
625stack -- the first one points over all the checked handlers -- and the ordering
626is maintained.
627\todo{Add a diagram for resumption marking.}
628
629\label{p:zero-cost}
630Note, the resumption implementation has a cost for entering/exiting a @try@
631statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
632clauses has zero-cost entry/exit. While resumption does not need the stack
633unwinding and cleanup provided by libunwind, it could use the search phase to
634providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
635to return from a libunwind search without installing a handler or raising an
636error. Although workarounds might be possible, they are beyond the scope of
637this thesis. The current resumption implementation has simplicity in its
638favour.
639% Seriously, just compare the size of the two chapters and then consider
640% that unwind is required knowledge for that chapter.
641
642\section{Finally}
643% Uses destructors and GCC nested functions.
644A finally clause is placed into a GCC nested-function with a unique name,
645and no arguments or return values.
646This nested function is then set as the cleanup
647function of an empty object that is declared at the beginning of a block placed
648around the context of the associated @try@ statement.
649
650The rest is handled by GCC. The try block and all handlers are inside this
651block. At completion, control exits the block and the empty object is cleaned
652up, which runs the function that contains the finally code.
653
654\section{Cancellation}
655% Stack selections, the three internal unwind functions.
656
657Cancellation also uses libunwind to do its stack traversal and unwinding,
658however it uses a different primary function: @_Unwind_ForcedUnwind@. Details
659of its interface can be found in the Section~\vref{s:ForcedUnwind}.
660
661The first step of cancellation is to find the cancelled stack and its type:
662coroutine or thread. Fortunately, the thread library stores the main thread
663pointer and the current thread pointer, and every thread stores a pointer to
664its main coroutine and the coroutine it is currently executing.
665\todo*{Consider adding a description of how threads are coroutines.}
666
667If a the current thread's main and current coroutines are the same then the
668current stack is a thread stack. Furthermore it is easy to compare the
669current thread to the main thread to see if they are the same. And if this
670is not a thread stack then it must be a coroutine stack.
671
672However, if the threading library is not linked, the sequential execution is on
673the main stack. Hence, the entire check is skipped because the weak-symbol
674function is loaded. Therefore, a main thread cancellation is unconditionally
675performed.
676
677Regardless of how the stack is chosen, the stop function and parameter are
678passed to the forced-unwind function. The general pattern of all three stop
679functions is the same: they continue unwinding until the end of stack and
680then preform their transfer.
681
682For main stack cancellation, the transfer is just a program abort.
683
684For coroutine cancellation, the exception is stored on the coroutine's stack,
685and the coroutine context switches to its last resumer. The rest is handled on
686the backside of the resume, which check if the resumed coroutine is
687cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
688and a @CoroutineCancelled@ exception is constructed and loaded with the
689cancelled exception. It is then resumed as a regular exception with the default
690handler coming from the context of the resumption call.
691
692For thread cancellation, the exception is stored on the thread's main stack and
693then context switched to the scheduler. The rest is handled by the thread
694joiner. When the join is complete, the joiner checks if the joined thread is
695cancelled. If cancelled, the exception is retrieved and the joined thread, and
696a @ThreadCancelled@ exception is constructed and loaded with the cancelled
697exception. The default handler is passed in as a function pointer. If it is
698null (as it is for the auto-generated joins on destructor call), the default is
699used, which is a program abort.
700%; which gives the required handling on implicate join.
Note: See TracBrowser for help on using the repository browser.