source: doc/theses/andrew_beach_MMath/implement.tex @ 7eb6eb5

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

complete first proofread of Andrew's thesis

  • Property mode set to 100644
File size: 28.0 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{\VPageref{p:VirtualCast}}, substantial structure is required to
12support it, and provide features for exception handling and the standard
13library.
14
15\subsection{Virtual Table}
16The virtual system is accessed through a private constant field inserted at the
17beginning of every virtual type, called the virtual-table pointer. This field
18points at a type's virtual table and is assigned during the object's
19construction.  The address of a virtual table acts as the unique identifier for
20the virtual type, and the first field of a virtual table is a pointer to the
21parent virtual-table or @0p@.  The remaining fields are duplicated from the
22parent tables in this type's inheritance chain, followed by any fields this type
23introduces. Parent fields are duplicated so they can be changed (\CC
24\lstinline[language=c++]|override|), so that references to the dispatched type
25are replaced with the current virtual type.
26\PAB{Can you create a simple diagram of the layout?}
27% These are always taken by pointer or reference.
28
29% For each virtual type, a virtual table is constructed. This is both a new type
30% and an instance of that type. Other instances of the type could be created
31% but the system doesn't use them. So this section will go over the creation of
32% the type and the instance.
33
34A virtual table is created when the virtual type is created. The name of the
35type is created by mangling the name of the base type. The name of the instance
36is also generated by name mangling.  The fields are initialized automatically.
37The parent field is initialized by getting the type of the parent field and
38using that to calculate the mangled name of the parent's virtual table type.
39There are two special fields that are included like normal fields but have
40special initialization rules: the @size@ field is the type's size and is
41initialized with a @sizeof@ expression, the @align@ field is the type's
42alignment and uses an @alignof@ expression. The remaining fields are resolved
43to a name matching the field's name and type using the normal visibility and
44overload resolution rules of the type system.
45
46These operations are split up into several groups depending on where they take
47place which varies for monomorphic and polymorphic types. The first devision is
48between the declarations and the definitions. Declarations, such as a function
49signature or a aggregate's name, must always be visible but may be repeated in
50the form of forward declarations in headers. Definitions, such as function
51bodies and a aggregate's layout, can be separately compiled but must occur
52exactly once in a source file.
53
54\begin{sloppypar}
55The declarations include the virtual type definition and forward declarations
56of the virtual table instance, constructor, message function and
57@get_exception_vtable@. The definition includes the storage and initialization
58of the virtual table instance and the bodies of the three functions.
59\end{sloppypar}
60
61Monomorphic instances put all of these two groups in one place each.
62Polymorphic instances also split out the core declarations and definitions from
63the per-instance information. The virtual table type and most of the functions
64are polymorphic so they are all part of the core. The virtual table instance
65and the @get_exception_vtable@ function.
66
67\begin{sloppypar}
68Coroutines and threads need instances of @CoroutineCancelled@ and
69@ThreadCancelled@ respectively to use all of their functionality.  When a new
70data type is declared with @coroutine@ or @thread@ the forward declaration for
71the instance is created as well. The definition of the virtual table is created
72at the definition of the main function.
73\end{sloppypar}
74
75\subsection{Virtual Cast}
76Virtual casts are implemented as a function call that does the subtype check
77and a C coercion-cast to do the type conversion.
78% The C-cast is just to make sure the generated code is correct so the rest of
79% the section is about that function.
80The function is
81\begin{cfa}
82void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent,
83        struct __cfa__parent_vtable const * const * child );
84}
85\end{cfa}
86and it is implemented in the standard library. It takes a pointer to the target
87type's virtual table and the object pointer being cast. The function performs a
88linear search starting at the object's virtual-table and walking through the
89the parent pointers, checking to if it or any of its ancestors are the same as
90the target-type virtual table-pointer.
91
92For the generated code, a forward declaration of the virtual works as follows.
93There is a forward declaration of @__cfa__virtual_cast@ in every \CFA file so
94it can just be used. The object argument is the expression being cast so that
95is just placed in the argument list.
96
97To build the target type parameter, the compiler creates a mapping from
98concrete type-name -- so for polymorphic types the parameters are filled in --
99to virtual table address. Every virtual table declaration is added to the this
100table; repeats are ignored unless they have conflicting definitions.  Note,
101these declarations do not have to be in scope, but they should usually be
102introduced as part of the type definition.
103
104\PAB{I do not understood all of \VRef{s:VirtualSystem}. I think you need to
105write more to make it clear.}
106
107
108\section{Exceptions}
109% Anything about exception construction.
110
111\section{Unwinding}
112% Adapt the unwind chapter, just describe the sections of libunwind used.
113% Mention that termination and cancellation use it. Maybe go into why
114% resumption doesn't as well.
115
116% Many modern languages work with an interal stack that function push and pop
117% their local data to. Stack unwinding removes large sections of the stack,
118% often across functions.
119
120Stack unwinding is the process of removing stack frames (activations) from the
121stack. On function entry and return, unwinding is handled directly by the code
122embedded in the function. Usually, the stack-frame size is known statically
123based on parameter and local variable declarations.  For dynamically-sized
124local variables, a runtime computation is necessary to know the frame
125size. Finally, a function's frame-size may change during execution as local
126variables (static or dynamic sized) go in and out of scope.
127Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
128bumping the hardware stack-pointer up or down as needed.
129
130Unwinding across multiple stack frames is more complex because individual stack
131management code associated with each frame is bypassed. That is, the location
132of a function's frame-management code is largely unknown and dispersed
133throughout the function, hence the current frame size managed by that code is
134also unknown. Hence, code unwinding across frames does not have direct
135knowledge about what is on the stack, and hence, how much of the stack needs to
136be removed.
137
138% At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply
139% move the top of the stack, discarding everything on the stack above a certain
140% point. However this ignores all the cleanup code that should be run when
141% certain sections of the stack are removed (for \CFA these are from destructors
142% and finally clauses) and also requires that the point to which the stack is
143% being unwound is known ahead of time. libunwind is used to address both of
144% these problems.
145
146The traditional unwinding mechanism for C is implemented by saving a snap-shot
147of a function's state with @setjmp@ and restoring that snap-shot with
148@longjmp@. This approach bypasses the need to know stack details by simply
149reseting to a snap-shot of an arbitrary but existing function frame on the
150stack. It is up to the programmer to ensure the snap-shot is valid when it is
151reset, making this unwinding approach fragile with potential errors that are
152difficult to debug because the stack becomes corrupted.
153
154However, many languages define cleanup actions that must be taken when objects
155are deallocated from the stack or blocks end, such as running a variable's
156destructor or a @try@ statement's @finally@ clause. Handling these mechanisms
157requires walking the stack and checking each stack frame for these potential
158actions.
159
160For exceptions, it must be possible to walk the stack frames in search of @try@
161statements to match and execute a handler. For termination exceptions, it must
162also be possible to unwind all stack frames from the throw to the matching
163catch, and each of these frames must be checked for cleanup actions. Stack
164walking is where most of the complexity and expense of exception handling
165appears.
166
167One of the most popular tools for stack management is libunwind, a low-level
168library that provides tools for stack walking, handler execution, and
169unwinding. What follows is an overview of all the relevant features of
170libunwind needed for this work, and how \CFA uses them to implement exception
171handling.
172
173\subsection{libunwind Usage}
174Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
175provides \CC-style stack-unwinding. Its operation is divided into two phases:
176search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
177stack and decide where unwinding should stop (but no unwinding occurs). The
178cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
179
180To use libunwind, each function must have a personality function and a Language
181Specific Data Area (LSDA).  The LSDA has the unique information for each
182function to tell the personality function where a function is executing, its
183current stack frame, and what handlers should be checked.  Theoretically, the
184LSDA can contain any information but conventionally it is a table with entries
185representing regions of the function and what has to be done there during
186unwinding. These regions are bracketed by the instruction pointer. If the
187instruction pointer is within a region's start/end, then execution is currently
188executing in that region. Regions are used to mark out the scopes of objects
189with destructors and try blocks.
190
191% Libunwind actually does very little, it simply moves down the stack from
192% function to function. Most of the actions are implemented by the personality
193% function which libunwind calls on every function. Since this is shared across
194% many functions or even every function in a language it will need a bit more
195% information.
196
197The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
198attaches its personality function. \PAB{to what is it attached?}  However, this
199flag only handles the cleanup attribute
200\begin{cfa}
201void clean_up( int * var ) { ... }
202int avar __attribute__(( __cleanup(clean_up) ));
203\end{cfa}
204which is used on a variable and specifies a function, \eg @clean_up@, run when
205the variable goes out of scope. The function is passed a pointer to the object
206so it can be used to mimic destructors. However, this feature cannot be used to
207mimic @try@ statements.
208
209\subsection{Personality Functions}
210Personality functions have a complex interface specified by libunwind.  This
211section covers some of the important parts of the interface.
212
213A personality function performs four tasks, although not all have to be
214present.
215\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
216typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) (
217        _Unwind_Action @action@,
218        _Unwind_Exception_Class @exception_class@,
219        _Unwind_Exception * @exception@,
220        struct _Unwind_Context * @context@
221);
222\end{lstlisting}
223The @action@ argument is a bitmask of possible actions:
224\begin{enumerate}
225\item
226@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
227to check for handlers.  If there is a handler in a stack frame, as defined by
228the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
229it return @_URC_CONTINUE_UNWIND@.
230
231\item
232@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
233unwound and all cleanup code is run. The personality function does whatever
234cleanup the language defines (such as running destructors/finalizers) and then
235generally returns @_URC_CONTINUE_UNWIND@.
236
237\item
238\begin{sloppypar}
239@_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a
240handler. The personality function must prepare to return to normal code
241execution and return @_URC_INSTALL_CONTEXT@.
242\end{sloppypar}
243
244\item
245@_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs
246the cleanup phase and uses a different means to decide when to stop
247\see{\VRef{s:ForcedUnwind}}.
248\end{enumerate}
249
250The @exception_class@ argument is a copy of the
251\lstinline[language=C]|exception|'s @exception_class@ field.
252
253The \lstinline[language=C]|exception| argument is a pointer to the user
254provided storage object. It has two public fields, the exception class, which
255is actually just a number, identifying the exception handling mechanism that
256created it, and the cleanup function. The cleanup function is called if
257required by the exception.
258
259The @context@ argument is a pointer to an opaque type passed to helper
260functions called inside the personality function.
261
262The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
263that can be passed several places in libunwind. It includes a number of
264messages for special cases (some of which should never be used by the
265personality function) and error codes but unless otherwise noted the
266personality function should always return @_URC_CONTINUE_UNWIND@.
267
268\subsection{Raise Exception}
269Raising an exception is the central function of libunwind and it performs a
270two-staged unwinding.
271\begin{cfa}
272_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
273\end{cfa}
274First, the function begins the search phase, calling the personality function
275of the most recent stack frame. It continues to call personality functions
276traversing the stack from newest to oldest until a function finds a handler or
277the end of the stack is reached. In the latter case, raise exception returns
278@_URC_END_OF_STACK@.
279
280Second, when a handler is matched, raise exception continues onto the cleanup phase.
281Once again, it calls the personality functions of each stack frame from newest
282to oldest. This pass stops at the stack frame containing the matching handler.
283If that personality function has not install a handler, it is an error.
284
285If an error is encountered, raise exception returns either
286@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
287error occurred.
288
289\subsection{Forced Unwind}
290\label{s:ForcedUnwind}
291Forced Unwind is the other central function in libunwind.
292\begin{cfa}
293_Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *,
294        _Unwind_Stop_Fn, void *);
295\end{cfa}
296It also unwinds the stack but it does not use the search phase. Instead another
297function, the stop function, is used to stop searching.  The exception is the
298same as the one passed to raise exception. The extra arguments are the stop
299function and the stop parameter. The stop function has a similar interface as a
300personality function, except it is also passed the stop parameter.
301\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
302typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)(
303        _Unwind_Action @action@,
304        _Unwind_Exception_Class @exception_class@,
305        _Unwind_Exception * @exception@,
306        struct _Unwind_Context * @context@,
307        void * @stop_parameter@);
308\end{lstlisting}
309
310The stop function is called at every stack frame before the personality
311function is called and then once more after all frames of the stack are
312unwound.
313
314Each time it is called, the stop function should return @_URC_NO_REASON@ or
315transfer control directly to other code outside of libunwind. The framework
316does not provide any assistance here.
317
318\begin{sloppypar}
319Its arguments are the same as the paired personality function.  The actions
320@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
321called. Beyond the libunwind standard, both GCC and Clang add an extra action
322on the last call at the end of the stack: @_UA_END_OF_STACK@.
323\end{sloppypar}
324
325\section{Exception Context}
326% Should I have another independent section?
327% There are only two things in it, top_resume and current_exception. How it is
328% stored changes depending on whether or not the thread-library is linked.
329
330The exception context is global storage used to maintain data across different
331exception operations and to communicate among different components.
332
333Each stack must have its own exception context. In a sequential \CFA program,
334there is only one stack with a single global exception-context. However, when
335the library @libcfathread@ is linked, there are multiple stacks where each
336needs its own exception context.
337
338General access to the exception context is provided by function
339@this_exception_context@. For sequential execution, this function is defined as
340a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
341concurrent, it links with @libcfathread@, where this function is defined with a
342strong symbol replacing the sequential version.
343
344% The version of the function defined in @libcfa@ is very simple. It returns a
345% pointer to a global static variable. With only one stack this global instance
346% is associated with the only stack.
347
348For coroutines, @this_exception_context@ accesses the exception context stored
349at the base of the stack. For threads, @this_exception_context@ uses the
350concurrency library to access the current stack of the thread or coroutine
351being executed by the thread, and then accesses the exception context stored at
352the base of this stack.
353
354\section{Termination}
355% Memory management & extra information, the custom function used to implement
356% catches. Talk about GCC nested functions.
357
358Termination exceptions use libunwind heavily because it matches the intended
359use from \CC exceptions closely. The main complication for \CFA is that the
360compiler generates C code, making it very difficult to generate the assembly to
361form the LSDA for try blocks or destructors.
362
363\subsection{Memory Management}
364The first step of a termination raise is to copy the exception into memory
365managed by the exception system. Currently, the system uses @malloc@, rather
366than reserved memory or the stack top. The exception handling mechanism manages
367memory for the exception as well as memory for libunwind and the system's own
368per-exception storage.
369
370Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout
371figure.} The first component is a fixed sized data structure that contains the
372information for libunwind and the exception system. The second component is an
373area of memory big enough to store the exception. Macros with pointer arthritic
374and type cast are used to move between the components or go from the embedded
375@_Unwind_Exception@ to the entire node.
376
377All of these nodes are linked together in a list, one list per stack, with the
378list head stored in the exception context. Within each linked list, the most
379recently thrown exception is at the head followed by older thrown
380exceptions. This format allows exceptions to be thrown, while a different
381exception is being handled. The exception at the head of the list is currently
382being handled, while other exceptions wait for the exceptions before them to be
383removed.
384
385The virtual members in the exception's virtual table provide the size of the
386exception, the copy function, and the free function, so they are specific to an
387exception type. The size and copy function are used immediately to copy an
388exception into managed memory. After the exception is handled the free function
389is used to clean up the exception and then the entire node is passed to free.
390
391\subsection{Try Statements and Catch Clauses}
392The try statement with termination handlers is complex because it must
393compensate for the lack of assembly-code generated from \CFA. Libunwind
394requires an LSDA and personality function for control to unwind across a
395function. The LSDA in particular is hard to mimic in generated C code.
396
397The workaround is a function called @__cfaehm_try_terminate@ in the standard
398library. The contents of a try block and the termination handlers are converted
399into functions. These are then passed to the try terminate function and it
400calls them. This approach puts a try statement in its own functions so that no
401function has to deal with both termination handlers and destructors. \PAB{I do
402not understand the previous sentence.}
403
404This function has some custom embedded assembly that defines \emph{its}
405personality function and LSDA. The assembly is created with handcrafted C @asm@
406statements, which is why there is only one version of it. The personality
407function is structured so that it can be expanded, but currently it only
408handles this one function.  Notably, it does not handle any destructors so the
409function is constructed so that it does need to run it. \PAB{I do not
410understand the previous sentence.}
411
412The three functions passed to try terminate are:
413\begin{description}
414\item[try function:] This function is the try block, all the code inside the
415try block is placed inside the try function. It takes no parameters and has no
416return value. This function is called during regular execution to run the try
417block.
418
419\item[match function:] This function is called during the search phase and
420decides if a catch clause matches the termination exception.  It is constructed
421from the conditional part of each handler and runs each check, top to bottom,
422in turn, first checking to see if the exception type matches and then if the
423condition is true. It takes a pointer to the exception and returns 0 if the
424exception is not handled here. Otherwise the return value is the id of the
425handler that matches the exception.
426
427\item[handler function:] This function handles the exception. It takes a
428pointer to the exception and the handler's id and returns nothing. It is called
429after the cleanup phase.  It is constructed by stitching together the bodies of
430each handler and dispatches to the selected handler.
431\end{description}
432All three functions are created with GCC nested functions. GCC nested functions
433can be used to create closures, functions that can refer to the state of other
434functions on the stack. This approach allows the functions to refer to all the
435variables in scope for the function containing the @try@ statement.  These
436nested functions and all other functions besides @__cfaehm_try_terminate@ in
437\CFA use the GCC personality function and the @-fexceptions@ flag to generate
438the LSDA. This allows destructors to be implemented with the cleanup attribute.
439
440\section{Resumption}
441% The stack-local data, the linked list of nodes.
442
443Resumption simple to implement because there is no stack unwinding. The
444resumption raise uses a list of nodes for its stack traversal. The head of the
445list is stored in the exception context. The nodes in the list have a pointer
446to the next node and a pointer to the handler function.
447
448A resumption raise traverses this list. At each node the handler function is
449called, passing the exception by pointer. It returns true if the exception is
450handled and false otherwise.
451
452The handler function does both the matching and handling. It computes the
453condition of each @catchResume@ in top-to-bottom order, until it finds a
454handler that matches. If no handler matches then the function returns
455false. Otherwise the matching handler is run; if it completes successfully, the
456function returns true. Reresume, through the @throwResume;@ statement, cause
457the function to return true.
458
459% Recursive Resumption Stuff:
460Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack
461already examined, is accomplished by updating the front of the list as the
462search continues. Before the handler at a node is called the head of the list
463is updated to the next node of the current node. After the search is complete,
464successful or not, the head of the list is reset.
465
466This mechanism means the current handler and every handler that has already
467been checked are not on the list while a handler is run. If a resumption is
468thrown during the handling of another resumption the active handlers and all
469the other handler checked up to this point are not checked again.
470
471This structure also supports new handler added while the resumption is being
472handled. These are added to the front of the list, pointing back along the
473stack -- the first one points over all the checked handlers -- and the ordering
474is maintained.
475
476\label{p:zero-cost}
477Note, the resumption implementation has a cost for entering/exiting a @try@
478statement with @catchResume@ clauses, whereas a @try@ statement with @catch@
479clauses has zero-cost entry/exit. While resumption does not need the stack
480unwinding and cleanup provided by libunwind, it could use the search phase to
481providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
482to return from a libunwind search without installing a handler or raising an
483error.  Although workarounds might be possible, they are beyond the scope of
484this thesis. The current resumption implementation has simplicity in its
485favour.
486% Seriously, just compare the size of the two chapters and then consider
487% that unwind is required knowledge for that chapter.
488
489\section{Finally}
490% Uses destructors and GCC nested functions.
491Finally clauses is placed into a GCC nested-function with a unique name, and no
492arguments or return values. This nested function is then set as the cleanup
493function of an empty object that is declared at the beginning of a block placed
494around the context of the associated @try@ statement.
495
496The rest is handled by GCC. The try block and all handlers are inside the
497block. At completion, control exits the block and the empty object is cleaned
498up, which runs the function that contains the finally code.
499
500\section{Cancellation}
501% Stack selections, the three internal unwind functions.
502
503Cancellation also uses libunwind to do its stack traversal and unwinding,
504however it uses a different primary function @_Unwind_ForcedUnwind@.  Details
505of its interface can be found in the \VRef{s:ForcedUnwind}.
506
507The first step of cancellation is to find the cancelled stack and its type:
508coroutine or thread. Fortunately, the thread library stores the main thread
509pointer and the current thread pointer, and every thread stores a pointer to
510its main coroutine and the coroutine it is currently executing.
511
512The first check is if the current thread's main and current coroutine do not
513match, implying a coroutine cancellation; otherwise, it is a thread
514cancellation. Otherwise it is a main thread cancellation. \PAB{Previous
515sentence does not make sense.}
516
517However, if the threading library is not linked, the sequential execution is on
518the main stack. Hence, the entire check is skipped because the weak-symbol
519function is loaded. Therefore, a main thread cancellation is unconditionally
520performed.
521
522Regardless of how the stack is chosen, the stop function and parameter are
523passed to the forced-unwind function. The general pattern of all three stop
524functions is the same: they continue unwinding until the end of stack when they
525do there primary work.
526
527For main stack cancellation, the transfer is just a program abort.
528
529For coroutine cancellation, the exception is stored on the coroutine's stack,
530and the coroutine context switches to its last resumer. The rest is handled on
531the backside of the resume, which check if the resumed coroutine is
532cancelled. If cancelled, the exception is retrieved from the resumed coroutine,
533and a @CoroutineCancelled@ exception is constructed and loaded with the
534cancelled exception. It is then resumed as a regular exception with the default
535handler coming from the context of the resumption call.
536
537For thread cancellation, the exception is stored on the thread's main stack and
538then context switched to the scheduler. The rest is handled by the thread
539joiner. When the join is complete, the joiner checks if the joined thread is
540cancelled. If cancelled, the exception is retrieved and the joined thread, and
541a @ThreadCancelled@ exception is constructed and loaded with the cancelled
542exception. The default handler is passed in as a function pointer. If it is
543null (as it is for the auto-generated joins on destructor call), the default is
544used, which is a program abort.
545%; which gives the required handling on implicate join.
Note: See TracBrowser for help on using the repository browser.