source: doc/theses/andrew_beach_MMath/implement.tex @ 692f0c8

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 692f0c8 was 692f0c8, checked in by Peter A. Buhr <pabuhr@…>, 9 months ago

proofread implementation chapter

  • 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, called the \emph{virtual-table pointer}.
18Internally, the field is called
19@virtual_table@.
20This constant pointer is always the first field of the table so when
21casting to a supertype, the field's location is always known.
22The field is initialized as part of all generated constructors.
23\todo{They only come as part exceptions and don't work.}
24%After the object is created the field is constant.
25Dereferencing it gives the virtual table and access to the
26type's virtual members.
27
28\subsection{Virtual Table}
29% PAB: These 2 paragraphs are repeated below, and maybe some of the paragraph above, too.
30\begin{comment}
31Every time a virtual type is defined, a new virtual table-type is
32instantiated.
33The uniqueness of the virtual-table
34instance is important because its address
35is used as the identifier for the virtual type. Hence, a pointer to the
36virtual table and the ID for the virtual type are interchangeable.
37\todo{Unique instances might be going so we will have to talk about the new
38system instead.}
39
40The first step is creating the virtual-table type.
41The virtual-table type is a structure and is described in terms of
42its fields. The first field contains the parent-type ID (or a pointer to
43the parent virtual-table) or 0 (null pointer).
44Next are repeated fields from on the parent virtual-table.
45Finally, the fields used to store any new virtual members of the new
46the virtual type.
47\end{comment}
48
49%The virtual system is accessed through a private constant field inserted at the
50%beginning of every virtual type. This field
51The virtual-table pointer
52points at a type's virtual table (see Figure~\vref{f:VirtualTableLayout}).
53%and is assigned during the object's
54%construction.
55The address of a virtual table acts as the unique identifier for
56the virtual type, and the first field of a virtual table is a pointer to the
57parent virtual-table or @0p@ (null pointer). The remaining fields are duplicated from the
58parent tables in this type's inheritance chain, followed by any fields this type
59introduces. Parent fields are duplicated so they can be changed, \ie all virtual
60members are overridable, while the parent pointer allows access to the original values.
61Hence, references to the dispatched type
62are replaced with the current virtual type.
63% These are always taken by pointer or reference.
64
65\begin{figure}
66% Simple ascii diragram:
67\begin{cfa}
68parent_pointer  // \C{parent pointer to access its fields}
69parent_field0   // \C{same layout as parent to allow replacement}
70...
71parent_fieldN
72child_field0    // \C{new types for this virtual table}
73...
74child_fieldN
75size
76alignment
77\end{cfa}
78%\todo{Refine the diagram}
79\caption{Virtual Table Layout}
80\label{f:VirtualTableLayout}
81\end{figure}
82
83% For each virtual type, a virtual table is constructed. This is both a new type
84% and an instance of that type. Other instances of the type could be created
85% but the system doesn't use them. So this section will go over the creation of
86% the type and the instance.
87
88\begin{comment}
89PAB: seems to be said already.
90A virtual table is created when a virtual type is created. The name of the
91type is created by mangling the name of the base type. The name of the instance
92is also generated by name mangling. The fields are initialized automatically.
93The parent field is initialized by getting the type of the parent field and
94using that to calculate the mangled name of the parent's virtual-table type.
95\end{comment}
96There are two special fields that are included like normal fields but have
97special initialization rules: the @size@ field is the type's size and is
98initialized with a @sizeof@ expression, the @align@ field is the type's
99alignment and uses an @alignof@ expression. The remaining fields are resolved
100to a name matching the field's name and type using the normal visibility and
101overload resolution rules of the type system.
102
103These operations are split up into several groups depending on where they take
104place, which varies for monomorphic and polymorphic types. The first devision is
105between the declarations and the definitions. Declarations, such as a function
106signature or an aggregate's name, must always be visible but may be repeated in
107the form of forward declarations in headers. Definitions, such as function
108bodies and a aggregate's layout, can be separately compiled but must occur
109exactly once in a source file.
110
111The declarations include the virtual-type definition and forward declarations
112of the virtual-table instance, constructor, message function and
113@get_exception_vtable@. The definition includes the storage and initialization
114of the virtual table instance and the bodies of the three functions.
115
116Monomorphic instances put all of these two groups in one place.
117Polymorphic instances split out the core declarations and definitions from
118the per-instance information. The virtual-table type and most of the functions
119are polymorphic so they are all part of the core. The virtual-table instance
120and the @get_exception_vtable@ function \PAB{ are ...}.
121
122Coroutines and threads need instances of @CoroutineCancelled@ and
123@ThreadCancelled@ respectively to use all of their functionality. When a new
124data type is declared with @coroutine@ or @thread@, the forward declaration for
125the instance is created as well. The definition of the virtual table is created
126at the definition of the main function.
127
128\PAB{You need an example here to show what happens for this case.}
129
130
131\subsection{Virtual Cast}
132Virtual casts are implemented as a function call that does the subtype check
133and a C coercion-cast to do the type conversion.
134% The C-cast is just to make sure the generated code is correct so the rest of
135% the section is about that function.
136The function is
137\begin{cfa}
138void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent,
139        struct __cfa__parent_vtable const * const * child );
140\end{cfa}
141and it is implemented in the standard library. The structure represents the
142head of a virtual table, which is the pointer to the parent virtual table. The
143@parent@ points directly at the parent-type virtual-table, while the @child@
144points at the object of the (possible) child type.
145
146\PAB{Need a figure to show this relationship.}
147
148In terms of the virtual-cast expression, @parent@ comes from looking up the
149type being cast to and @child@ is the result of the expression being cast.
150Because the complier outputs C code, some C-type casts are also used.
151The last bit of glue is a map that saves every virtual type the compiler
152sees. This table is used to check the type used in a virtual cast is a virtual
153type and to get its virtual table.
154(It also checks for conflicting definitions.)
155
156\PAB{Can this be rolled into the figure above?}
157
158Inside the function is a simple conditional. If the type represented by
159@parent@ is an ancestor of the type represented by @*child@ (it
160requires one more level of dereference to pass through the object) then @child@
161is returned, otherwise the null pointer is returned.
162
163The check is a simple linear search (like \Cpp RTTI). If the child
164virtual table or any of its ancestors (which are retrieved through the first
165field of every virtual table) are the same as the parent virtual-table then
166the cast succeeds.
167
168\section{Exceptions}
169% Anything about exception construction.
170
171\section{Unwinding}
172% Adapt the unwind chapter, just describe the sections of libunwind used.
173% Mention that termination and cancellation use it. Maybe go into why
174% resumption doesn't as well.
175
176% Many modern languages work with an internal stack that function push and pop
177% their local data to. Stack unwinding removes large sections of the stack,
178% often across functions.
179
180Stack unwinding is the process of removing stack frames (activations) from the
181stack. On function entry and return, unwinding is handled directly by the call/return code
182embedded in a function. Usually, the stack-frame size is known statically
183based on parameter and local variable declarations. For dynamically-sized
184local variables.
185(Often called a variable-length array or VLA, even when the variable type is an aggregate.)
186For VLAs, a runtime computation is necessary to know the frame
187size. Finally, a function's frame-size may change during execution as local
188variables (static or dynamic sized) go in and out of scope, which is a form of VLA.
189Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
190bumping the hardware stack-pointer up or down as needed.
191
192Unwinding across multiple stack frames is more complex because individual stack-management
193code associated with each frame can be bypassed. That is, the location
194of a function's frame-management code is largely unknown and dispersed
195throughout the function, hence the current frame size managed by that code is
196also unknown. Hence, code unwinding across frames does not have direct
197knowledge about what is on the stack, and hence, how much of the stack needs to
198be removed.
199
200% At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply
201% move the top of the stack, discarding everything on the stack above a certain
202% point. However this ignores all the cleanup code that should be run when
203% certain sections of the stack are removed (for \CFA these are from destructors
204% and finally clauses) and also requires that the point to which the stack is
205% being unwound is known ahead of time. libunwind is used to address both of
206% these problems.
207
208The traditional unwinding mechanism for C is implemented by saving a snap-shot
209of a function's state with @setjmp@ and restoring that snap-shot with
210@longjmp@. This approach bypasses the need to know stack details by simply
211reseting to a snap-shot of an arbitrary but existing function frame on the
212stack. It is up to the programmer to ensure the snap-shot is valid when it is
213reset and that unwound frames do not have side-effects.
214Hence, this unwinding approach is fragile with potential errors that are
215difficult to debug because the stack becomes corrupted.
216
217With respect to stack side-effects, many languages define cleanup actions that must be taken when objects
218are deallocated from the stack, when the function of blocks within the function end, such as running a variable's
219destructor or a @try@ statement's @finally@ clause.
220The purpose of these side-effects is to reestablish the global state of the program, such as dynamic memory-allocation or file access.
221Handling these side-effect mechanisms
222requires walking the stack and checking each stack frame for these potential
223actions, where a frame can be any block with declarations.
224
225In languages like \Cpp and Java, it must be possible to walk the stack frames in search of @try@
226statements to match and execute a handler. For termination exceptions, it must
227also be possible to unwind all stack frames from the throw to the matching
228catch (including the @try@ block), and each of these frames must be checked for cleanup actions. Stack
229walking is where most of the complexity and expense of exception handling
230appears.
231
232One of the most popular tools for stack management is libunwind, a low-level
233library that provides tools for stack walking, handler execution, and
234unwinding. What follows is an overview of all the relevant features of
235libunwind needed for this work, and how \CFA uses them to implement exception
236handling.
237
238\subsection{libunwind Usage}
239Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
240provides \Cpp-style stack-unwinding. Its operation is divided into two phases:
241search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
242stack and decide where unwinding should stop (but no unwinding occurs). The
243cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
244
245To use libunwind, each function must have a personality function and a Language
246Specific Data Area (LSDA). The LSDA has the unique information for each
247function to tell the personality function where a function is executing, its
248current stack frame, and what handlers should be checked. Theoretically, the
249LSDA can contain any information but conventionally it is a table with entries
250representing regions of the function and what has to be done there during
251unwinding. These regions are bracketed by instruction addresses. If the
252instruction pointer is within a region's start/end, then execution is currently
253executing in that region. Regions are used to mark out the scopes of objects
254with destructors and try blocks.
255
256% Libunwind actually does very little, it simply moves down the stack from
257% function to function. Most of the actions are implemented by the personality
258% function which libunwind calls on every function. Since this is shared across
259% many functions or even every function in a language it will need a bit more
260% information.
261
262The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
263attaches its personality function.
264It attaches a series of opaque directives (@.cfi_personality@ directive)
265used internally and not part of this work.
266However, this
267flag only handles the cleanup attribute:
268\begin{cfa}
269void clean_up( int * var ) { ... }
270int avar __attribute__(( cleanup(clean_up) ));
271\end{cfa}
272that is used on a variable and specifies a function, in this case @clean_up@,
273run when the variable goes out of scope, which is used to mimic destructors.
274However, this feature cannot be used to mimic @try@ statements as it cannot
275control the unwinding.
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 perform 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 Section~\vref{s:ForcedUnwind}).
316\end{enumerate}
317
318The @exception_class@ argument is a copy of the
319\lstinline[language=C]|exception|'s @exception_class@ field.
320\PAB{Say more.}
321
322The \lstinline[language=C]|exception| argument is a pointer to the user
323provided storage object. It has two public fields, the exception class, which
324is just a number, identifying the exception handling mechanism that
325created it, and the cleanup function. The cleanup function is called if
326required by the exception.
327
328The @context@ argument is a pointer to an opaque type passed to helper
329functions called inside the personality function.
330
331The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
332that can be passed several places in libunwind. It includes a number of
333messages for special cases (some of which should never be used by the
334personality function) and error codes. However, unless otherwise noted, the
335personality function should always return @_URC_CONTINUE_UNWIND@.
336
337\subsection{Raise Exception}
338Raising an exception is the central function of libunwind and it performs a
339two-staged unwinding.
340\begin{cfa}
341_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
342\end{cfa}
343First, the function begins the search phase, calling the personality function
344of the most recent stack frame. It continues to call personality functions
345traversing the stack from newest to oldest until a function finds a handler or
346the end of the stack is reached. In the latter case, raise exception returns
347@_URC_END_OF_STACK@.
348
349Second, when a handler is matched, raise exception walks the stack again performing the cleanup
350phase.
351Once again, it calls the personality functions of each stack frame from newest
352to oldest. This pass stops at the stack frame containing the matching handler.
353If that personality function has not install a handler, it is an error.
354
355If an error is encountered, raise exception returns either
356@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
357error occurred.
358
359\subsection{Forced Unwind}
360\label{s:ForcedUnwind}
361Forced Unwind is the other central function in libunwind.
362\begin{cfa}
363_Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *,
364        _Unwind_Stop_Fn, void *);
365\end{cfa}
366It also unwinds the stack but it does not use the search phase. Instead another
367function, the stop function, is used to stop searching. The exception is the
368same as the one passed to raise exception. The extra arguments are the stop
369function and the stop parameter. The stop function has a similar interface as a
370personality function, except it is also passed the stop parameter.
371\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
372typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)(
373        _Unwind_Action @action@,
374        _Unwind_Exception_Class @exception_class@,
375        _Unwind_Exception * @exception@,
376        struct _Unwind_Context * @context@,
377        void * @stop_parameter@);
378\end{lstlisting}
379
380The stop function is called at every stack frame before the personality
381function is called and then once more after all frames of the stack are
382unwound.
383
384Each time it is called, the stop function should return @_URC_NO_REASON@ or
385transfer control directly to other code outside of libunwind. The framework
386does not provide any assistance here.
387
388\begin{sloppypar}
389Its arguments are the same as the paired personality function. The actions
390@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
391called. Beyond the libunwind standard, both GCC and Clang add an extra action
392on the last call at the end of the stack: @_UA_END_OF_STACK@.
393\end{sloppypar}
394
395\section{Exception Context}
396% Should I have another independent section?
397% There are only two things in it, top_resume and current_exception. How it is
398% stored changes depending on whether or not the thread-library is linked.
399
400The exception context is global storage used to maintain data across different
401exception operations and to communicate among different components.
402
403Each stack must have its own exception context. In a sequential \CFA program,
404there is only one stack with a single global exception-context. However, when
405the library @libcfathread@ is linked, there are multiple stacks, where each
406needs its own exception context.
407
408The function @this_exception_context@ provides general access to the exception context.
409For sequential execution, this function is defined as
410a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
411concurrent, it links with @libcfathread@, where this function is defined with a
412strong symbol replacing the sequential version.
413
414The sequential @this_exception_context@ returns a hard-coded pointer to the
415global exception context.
416The concurrent version adds the exception context to the data stored at the
417base of each stack. When @this_exception_context@ is called, it retrieves the
418active stack and returns the address of the context saved there.
419
420\section{Termination}
421% Memory management & extra information, the custom function used to implement
422% catches. Talk about GCC nested functions.
423
424Termination exceptions use libunwind heavily because \CFA termination exceptions match
425\Cpp exceptions closely. The main complication for \CFA is that the
426compiler generates C code, making it very difficult to generate the assembly to
427form the LSDA for try blocks or destructors.
428
429\subsection{Memory Management}
430The first step of a termination raise is to copy the exception into memory
431managed by the exception system. Currently, the system uses @malloc@, rather
432than reserved memory or the stack top. The exception-handling mechanism manages
433memory for the exception as well as memory for libunwind and the system's own
434per-exception storage.
435
436\begin{figure}
437\begin{verbatim}
438Fixed Header  | _Unwind_Exception   <- pointer target
439              |
440              | Cforall storage
441              |
442Variable Body | the exception       <- fixed offset
443              V ...
444\end{verbatim}
445\caption{Exception Layout}
446\label{f:ExceptionLayout}
447\end{figure}
448
449Exceptions are stored in variable-sized blocks (see Figure~\vref{f:ExceptionLayout}).
450The first component is a fixed-sized data-structure that contains the
451information for libunwind and the exception system. The second component is an
452area of memory big enough to store the exception. Macros with pointer arthritic
453and type cast are used to move between the components or go from the embedded
454@_Unwind_Exception@ to the entire node.
455
456Multiple exceptions can exist because handlers can call functions that raise
457exceptions.  Figure~\vref{f:MultipleExceptions} shows a \Cpp program where
458exceptions are handled, and then a function is called from the handler that
459raises a new exception. The previous exception must persist because it is
460unhandled, and hence, control can return to the handler and that exception is
461reraised.
462
463\begin{figure}
464\centering
465\newsavebox{\myboxA}
466\newsavebox{\myboxB}
467\begin{lrbox}{\myboxA}
468\begin{lstlisting}[language=C++,{moredelim=**[is][\color{red}]{@}{@}}]
469struct E {};
470int cnt = 3;
471void f( int i ) {
472        if ( i == 0 ) @throw E();@
473        try {
474                @f( i - 1 );@
475        } catch( E ) { // handler h
476                cnt -= 1;
477                if ( cnt > 0 ) @f( 2 );@
478        }
479}
480int main() { @f( 2 );@ }
481\end{lstlisting}
482\end{lrbox}
483
484\begin{lrbox}{\myboxB}
485\begin{lstlisting}
486$\makebox[0pt][l]{\textbackslash}f$
487   f
488   f
489$\makebox[0pt][l]{\textbackslash}f$  throw E$\(_2\)$
490   f
491   f
492$\makebox[0pt][l]{\textbackslash}f$  throw E$\(_1\)$
493   f
494   f
495\end{lstlisting}
496\end{lrbox}
497
498{\usebox\myboxA}
499\hspace{25pt}
500{\usebox\myboxB}
501
502\caption{Multiple Exceptions}
503\label{f:MultipleExceptions}
504\end{figure}
505
506In this case, the exception nodes are linked together in a list, one list per stack, with the
507list head stored in the exception context. Within each linked list, the most
508recently thrown exception is at the head followed by older thrown
509exceptions. This format allows exceptions to be thrown, while a different
510exception is being handled. The exception at the head of the list is currently
511being handled, while other exceptions wait for the exceptions before them to be
512removed.
513
514The virtual members in the exception's virtual table provide the size of the
515exception, the copy function, and the free function, so they are specific to an
516exception type. The size and copy function are used immediately to copy an
517exception into managed memory. After the exception is handled, the free function
518is used to clean up the exception and then the entire node is passed to free
519so the memory can be given back to the heap.
520
521\subsection{Try Statements and Catch Clauses}
522The try statement with termination handlers is complex because it must
523compensate for the lack of assembly code generated from \CFA. Libunwind
524requires an LSDA and personality function for control to unwind across a
525function. The LSDA in particular is hard to mimic in generated C code.
526
527The workaround is a function called @__cfaehm_try_terminate@ in the standard
528library. The contents of a try block and the termination handlers are converted
529into functions. These are then passed to the try terminate function and it
530calls them.
531Because this function is known and fixed (and not an arbitrary function that
532happens to contain a try statement), this means the LSDA can be generated ahead
533of time.
534
535Both the LSDA and the personality function are set ahead of time using
536embedded assembly. This assembly code is handcrafted using C @asm@ statements and contains
537enough information for the single try statement the function represents.
538
539The three functions passed to try terminate are:
540\begin{description}
541\item[try function:] This function is the try block, all the code inside the
542try block is placed inside the try function. It takes no parameters and has no
543return value. This function is called during regular execution to run the try
544block.
545
546\item[match function:] This function is called during the search phase and
547decides if a catch clause matches the termination exception. It is constructed
548from the conditional part of each handler and runs each check, top to bottom,
549in turn, first checking to see if the exception type matches and then if the
550condition is true. It takes a pointer to the exception and returns 0 if the
551exception is not handled here. Otherwise the return value is the id of the
552handler that matches the exception.
553
554\item[handler function:] This function handles the exception. It takes a
555pointer to the exception and the handler's id and returns nothing. It is called
556after the cleanup phase. It is constructed by stitching together the bodies of
557each handler and dispatches to the selected handler.
558\end{description}
559All three functions are created with GCC nested functions. GCC nested functions
560can be used to create closures, functions that can refer to the state of other
561functions on the stack. This approach allows the functions to refer to all the
562variables in scope for the function containing the @try@ statement. These
563nested functions and all other functions besides @__cfaehm_try_terminate@ in
564\CFA use the GCC personality function and the @-fexceptions@ flag to generate
565the LSDA. Through this mechanism, \CFA destructors are implemented via the cleanup attribute.
566
567\PAB{Try to put together an example try statement illustrating these components.}
568
569\section{Resumption}
570% The stack-local data, the linked list of nodes.
571
572Resumption is simpler to implement than termination because there is no stack
573unwinding.  \PAB{You need to explain how the \lstinline{catchResume} clauses are
574handled. Do you use the personality mechanism in libunwind or do you roll your
575own mechanism?}
576
577The
578resumption raise uses a list of nodes for its stack traversal. The head of the
579list is stored in the exception context. The nodes in the list have a pointer
580to the next node and a pointer to the handler function.
581A resumption raise traverses this list. At each node the handler function is
582called, passing the exception by pointer. It returns true if the exception is
583handled and false otherwise.
584
585The handler function does both the matching and handling. It computes the
586condition of each @catchResume@ in top-to-bottom order, until it finds a
587handler that matches. If no handler matches then the function returns
588false. Otherwise the matching handler is run; if it completes successfully, the
589function returns true. Rethrowing, through the @throwResume;@ statement,
590causes the function to return true.
591
592% Recursive Resumption Stuff:
593Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of
594the stack
595already examined, is accomplished by updating the front of the list as the
596search continues. Before the handler at a node is called, the head of the list
597is updated to the next node of the current node. After the search is complete,
598successful or not, the head of the list is reset.
599
600This mechanism means the current handler and every handler that has already
601been checked are not on the list while a handler is run. If a resumption is
602thrown during the handling of another resumption the active handlers and all
603the other handler checked up to this point are not checked again.
604
605This structure also supports new handlers added while the resumption is being
606handled. These are added to the front of the list, pointing back along the
607stack -- the first one points over all the checked handlers -- and the ordering
608is maintained.
609
610\PAB{Again, a figure to show how this works would be helpful.}
611
612\label{p:zero-cost}
613Note, the resumption implementation has a cost for entering/exiting a @try@
614statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
615clauses has zero-cost entry/exit. While resumption does not need the stack
616unwinding and cleanup provided by libunwind, it could use the search phase to
617providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
618to return from a libunwind search without installing a handler or raising an
619error. Although workarounds might be possible, they are beyond the scope of
620this thesis. The current resumption implementation has simplicity in its
621favour.
622% Seriously, just compare the size of the two chapters and then consider
623% that unwind is required knowledge for that chapter.
624
625\PAB{This paragraph needs to be moved to the start of this Section, where I have have my other comment.}
626
627\section{Finally}
628% Uses destructors and GCC nested functions.
629A finally clause is placed into a GCC nested-function with a unique mangled name, and no
630arguments or return values. This nested function is then set as the cleanup
631function of an empty object that is declared at the beginning of a block placed
632around the context of an associated @try@ statement.
633
634The rest is handled by GCC. The try block and all handlers are inside this
635block. At completion, control exits the block and the empty object is cleaned
636up, which runs the function that contains the finally code.
637
638\section{Cancellation}
639% Stack selections, the three internal unwind functions.
640
641Cancellation also uses libunwind to do its stack traversal and unwinding,
642however it uses a different primary function, @_Unwind_ForcedUnwind@. Details
643of its interface can be found in Section~\vref{s:ForcedUnwind}.
644
645The first step of cancellation is to find the cancelled stack and its type:
646coroutine or thread. Fortunately, the thread library stores the program-main thread
647pointer and the current-thread pointer, and every thread stores a pointer to
648the current coroutine it is executing.
649
650\PAB{I don't know if my corrections in the previous paragraph are correct.}
651
652When the active thread and coroutine are the same, the current stack is the thread stack, otherwise it is a coroutine
653stack.
654% PAB: repeated?
655% If it is a thread stack, then an equality check with the stored main
656% thread pointer and current thread pointer is enough to tell if the current
657% thread is the main thread or not.
658However, if the threading library is not linked, the sequential execution is on
659the main stack. Hence, the entire check is skipped because the weak-symbol
660function is loaded. Therefore, a main thread cancellation is unconditionally
661performed.
662
663Regardless of how the stack is chosen, the stop function and parameter are
664passed to the forced-unwind function. The general pattern of all three stop
665functions is the same: continue unwinding until the end of stack.
666%when they
667%do there primary work.
668For main stack cancellation, the transfer is just a program abort.
669
670For coroutine cancellation, the exception is stored in the coroutine's stack,
671and the coroutine context switches to its last resumer. The rest is handled on
672the backside of the resume, which check if the resumed coroutine is
673cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
674and a @CoroutineCancelled@ exception is constructed and loaded with the
675cancelled exception. It is then resumed as a regular exception with the default
676handler coming from the context of the resumption call.
677
678For thread cancellation, the exception is stored on the thread's main stack and
679then context switched to the scheduler. The rest is handled by the thread
680joiner. When the join is complete, the joiner checks if the joined thread is
681cancelled. If cancelled, the exception is retrieved and the joined thread, and
682a @ThreadCancelled@ exception is constructed and loaded with the cancelled
683exception. The default handler is passed in as a function pointer. If it is
684null (as it is for the auto-generated joins on destructor call), the default is
685used, which is a program abort.
686%; which gives the required handling on implicate join.
Note: See TracBrowser for help on using the repository browser.