source: doc/theses/andrew_beach_MMath/implement.tex @ 1dfe6a6

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 1dfe6a6 was 26ca815, checked in by Andrew Beach <ajbeach@…>, 10 months ago

Andrew MMath: This took way longer than I wanted but, first draft of implementation.

  • Property mode set to 100644
File size: 24.5 KB
Line 
1\chapter{Implementation}
2% Goes over how all the features are implemented.
3
4\section{Virtual System}
5% Virtual table rules. Virtual tables, the pointer to them and the cast.
6The \CFA virtual system only has one public facing feature: virtual casts.
7However there is a lot of structure to support that and provide some other
8features for the standard library.
9
10All of this is accessed through a field inserted at the beginning of every
11virtual type. Currently it is called \codeC{virtual_table} but it is not
12ment to be accessed by the user. This field is a pointer to the type's
13virtual table instance. It is assigned once during the object's construction
14and left alone after that.
15
16\subsection{Virtual Table Construction}
17For each virtual type a virtual table is constructed. This is both a new type
18and an instance of that type. Other instances of the type could be created
19but the system doesn't use them. So this section will go over the creation of
20the type and the instance.
21
22Creating the single instance is actually very important. The address of the
23table acts as the unique identifier for the virtual type. Similarly the first
24field in every virtual table is the parent's id; a pointer to the parent
25virtual table instance.
26
27The remaining fields contain the type's virtual members. First come the ones
28present on the parent type, in the same order as they were the parent, and
29then any that this type introduces. The types of the ones inherited from the
30parent may have a slightly modified type, in that references to the
31dispatched type are replaced with the current virtual type. These are always
32taken by pointer or reference.
33
34The structure itself is created where the virtual type is created. The name
35of the type is created by mangling the name of the base type. The name of the
36instance is also generated by name mangling.
37
38The fields are initialized automatically.
39The parent field is initialized by getting the type of the parent field and
40using that to calculate the mangled name of the parent's virtual table type.
41There are two special fields that are included like normal fields but have
42special initialization rules: the \codeC{size} field is the type's size and is
43initialized with a sizeof expression, the \codeC{align} field is the type's
44alignment and uses an alignof expression. The remaining fields are resolved
45to a name matching the field's name and type using the normal visibility
46and overload resolution rules of the type system.
47
48These operations are split up into several groups depending on where they
49take place which can vary for monomorphic and polymorphic types. The first
50devision is between the declarations and the definitions. Declarations, such
51as a function signature or a structure's name, must always be visible but may
52be repeated so they go in headers. Definitions, such as function bodies and a
53structure's layout, don't have to be visible on use but must occur exactly
54once and go into source files.
55
56The declarations include the virtual type definition and forward declarations
57of the virtual table instance, constructor, message function and
58\codeCFA{get_exception_vtable}. The definition includes the storage and
59initialization of the virtual table instance and the bodies of the three
60functions.
61
62Monomorphic instances put all of these two groups in one place each.
63
64Polymorphic instances also split out the core declarations and definitions
65from the per-instance information. The virtual table type and most of the
66functions are polymorphic so they are all part of the core. The virtual table
67instance and the \codeCFA{get_exception_vtable} function.
68
69Coroutines and threads need instances of \codeCFA{CoroutineCancelled} and
70\codeCFA{ThreadCancelled} respectively to use all of their functionality.
71When a new data type is declared with \codeCFA{coroutine} or \codeCFA{thread}
72the forward declaration for the instance is created as well. The definition
73of the virtual table is created at the definition of the main function.
74
75\subsection{Virtual Cast}
76Virtual casts are implemented as a function call that does the check and a
77old C-style cast to do the type conversion. The C-cast is just to make sure
78the generated code is correct so the rest of the section is about that
79function.
80
81The function is \codeC{__cfa__virtual_cast} and it is implemented in the
82standard library. It takes a pointer to the target type's virtual table and
83the object pointer being cast. The function is very simple, getting the
84object's virtual table pointer and then checking to see if it or any of
85its ancestors, by using the parent pointers, are the same as the target type
86virtual table pointer. It does this in a simple loop.
87
88For the generated code a forward decaration of the virtual works as follows.
89There is a forward declaration of \codeC{__cfa__virtual_cast} in every cfa
90file so it can just be used. The object argument is the expression being cast
91so that is just placed in the argument list.
92
93To build the target type parameter the compiler will create a mapping from
94concrete type-name -- so for polymorphic types the parameters are filled in
95-- to virtual table address. Every virtual table declaraction is added to the
96this table; repeats are ignored unless they have conflicting definitions.
97This does mean the declaractions have to be in scope, but they should usually
98be introduced as part of the type definition.
99
100\section{Exceptions}
101% Anything about exception construction.
102
103\section{Unwinding}
104% Adapt the unwind chapter, just describe the sections of libunwind used.
105% Mention that termination and cancellation use it. Maybe go into why
106% resumption doesn't as well.
107
108Many modern languages work with an interal stack that function push and pop
109their local data to. Stack unwinding removes large sections of the stack,
110often across functions.
111
112At a very basic level this can be done with \codeC{setjmp} \& \codeC{longjmp}
113which simply move the top of the stack, discarding everything on the stack
114above a certain point. However this ignores all the clean-up code that should
115be run when certain sections of the stack are removed (for \CFA these are from
116destructors and finally clauses) and also requires that the point to which the
117stack is being unwound is known ahead of time. libunwind is used to address
118both of these problems.
119
120Libunwind, provided in \texttt{unwind.h} on most platorms, is a C library
121that provides \CPP style stack unwinding. Its operation is divided into two
122phases. The search phase -- phase 1 -- is used to scan the stack and decide
123where the unwinding will stop, this allows for a dynamic target. The clean-up
124phase -- phase 2 -- does the actual unwinding and also runs any clean-up code
125as it goes.
126
127To use the libunwind each function must have a personality function and an
128LSDA (Language Specific Data Area). Libunwind actually does very little, it
129simply moves down the stack from function to function. Most of the actions are
130implemented by the personality function which libunwind calls on every
131function. Since this is shared across many functions or even every function in
132a language it will need a bit more information. This is provided by the LSDA
133which has the unique information for each function.
134
135Theoretically the LSDA can contain anything but conventionally it is a table
136with entries reperenting areas of the function and what has to be done there
137during unwinding. These areas are described in terms of where the instruction
138pointer is. If the current value of the instruction pointer is between two
139values reperenting the beginning and end of a region then execution is
140currently being executed. These are used to mark out try blocks and the
141scopes of objects with destructors to run.
142
143GCC will generate an LSDA and attach its personality function with the
144\texttt{-fexceptions} flag. However this only handles the cleanup attribute.
145This attribute is used on a variable and specifies a function that should be
146run when the variable goes out of scope. The function is passed a pointer to
147the object as well so it can be used to mimic destructors. It however cannot
148be used to mimic try statements.
149
150\subsection{Implementing Personality Functions}
151Personality functions have a complex interface specified by libunwind.
152This section will cover some of the important parts of that interface.
153
154\begin{lstlisting}
155typedef _Unwind_Reason_Code (*_Unwind_Personality_Fn)(
156    int version,
157    _Unwind_Action action,
158    _Unwind_Exception_Class exception_class,
159    _Unwind_Exception * exception,
160    struct _Unwind_Context * context);
161\end{lstlisting}
162
163The return value, the reason code, is an enumeration of possible messages
164that can be passed several places in libunwind. It includes a number of
165messages for special cases (some of which should never be used by the
166personality function) and error codes but unless otherwise noted the
167personality function should always return \codeC{_URC_CONTINUE_UNWIND}.
168
169The \codeC{version} argument is the verson of the implementation that is
170calling the personality function. At this point it appears to always be 1 and
171it will likely stay that way until a new version of the API is updated.
172
173The \codeC{action} argument is set of flags that tell the personality
174function when it is being called and what it must do on this invocation.
175The flags are as follows:
176\begin{itemize}
177\item\codeC{_UA_SEARCH_PHASE}: This flag is set whenever the personality
178function is called during the search phase. The personality function should
179decide if unwinding will stop in this function or not. If it does then the
180personality function should return \codeC{_URC_HANDLER_FOUND}.
181\item\codeC{_UA_CLEANUP_PHASE}: This flag is set whenever the personality
182function is called during the cleanup phase. If no other flags are set this
183means the entire frame will be unwound and all cleanup code should be run.
184\item\codeC{_UA_HANDLER_FRAME}: This flag is set during the cleanup phase
185on the function frame that found the handler. The personality function must
186prepare to return to normal code execution and return
187\codeC{_URC_INSTALL_CONTEXT}.
188\item\codeC{_UA_FORCE_UNWIND}: This flag is set if the personality function
189is called through a forced unwind call. Forced unwind only performs the
190cleanup phase and uses a different means to decide when to stop. See its
191section below.
192\end{itemize}
193
194The \codeC{exception_class} argument is a copy of the \codeC{exception}'s
195\codeC{exception_class} field.
196
197The \codeC{exception} argument is a pointer to the user provided storage
198object. It has two public fields, the exception class which is actually just
199a number that identifies the exception handling mechanism that created it and
200the other is the clean-up function. The clean-up function is called if the
201exception needs to
202
203The \codeC{context} argument is a pointer to an opaque type. This is passed
204to the many helper functions that can be called inside the personality
205function.
206
207\subsection{Raise Exception}
208This could be considered the central function of libunwind. It preforms the
209two staged unwinding the library is built around and most of the rest of the
210interface of libunwind is here to support it. It's signature is as follows:
211
212\begin{lstlisting}
213_Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
214\end{lstlisting}
215
216When called the function begins the search phase, calling the personality
217function of the most recent stack frame. It will continue to call personality
218functions traversing the stack new-to-old until a function finds a handler or
219the end of the stack is reached. In the latter case raise exception will
220return with \codeC{_URC_END_OF_STACK}.
221
222Once a handler has been found raise exception continues onto the the cleanup
223phase. Once again it will call the personality functins of each stack frame
224from newest to oldest. This pass will stop at the stack frame that found the
225handler last time, if that personality function does not install the handler
226it is an error.
227
228If an error is encountered raise exception will return either
229\codeC{_URC_FATAL_PHASE1_ERROR} or \codeC{_URC_FATAL_PHASE2_ERROR} depending
230on when the error occured.
231
232\subsection{Forced Unwind}
233This is the second big function in libunwind. It also unwinds a stack but it
234does not use the search phase. Instead another function, the stop function,
235is used to decide when to stop.
236
237\begin{lstlisting}
238_Unwind_Reason_Code _Unwind_ForcedUnwind(
239    _Unwind_Exception *, _Unwind_Stop_Fn, void *);
240\end{lstlisting}
241
242The exception is the same as the one passed to raise exception. The extra
243arguments are the stop function and the stop parameter. The stop function has
244a similar interface as a personality function, except it is also passed the
245stop parameter.
246
247\begin{lstlisting}
248typedef _Unwind_Reason_Code (*_Unwind_Stop_Fn)(
249    int version,
250    _Unwind_Action action,
251    _Unwind_Exception_Class exception_class,
252    _Unwind_Exception * exception,
253    struct _Unwind_Context * context,
254    void * stop_parameter);
255\end{lstlisting}
256
257The stop function is called at every stack frame before the personality
258function is called and then once more once after all frames of the stack have
259been unwound.
260
261Each time it is called the stop function should return \codeC{_URC_NO_REASON}
262or transfer control directly to other code outside of libunwind. The
263framework does not provide any assistance here.
264
265Its arguments are the same as the paired personality function.
266The actions \codeC{_UA_CLEANUP_PHASE} and \codeC{_UA_FORCE_UNWIND} are always
267set when it is called. By the official standard that is all but both GCC and
268Clang add an extra action on the last call at the end of the stack:
269\codeC{_UA_END_OF_STACK}.
270
271\section{Exception Context}
272% Should I have another independent section?
273% There are only two things in it, top_resume and current_exception. How it is
274% stored changes depending on wheither or not the thread-library is linked.
275
276The exception context is a piece of global storage used to maintain data
277across different exception operations and to communicate between different
278components.
279
280Each stack has its own exception context. In a purely sequental program, using
281only core Cforall, there is only one stack and the context is global. However
282if the library \texttt{libcfathread} is linked then there can be multiple
283stacks so they will each need their own.
284
285To handle this code always gets the exception context from the function
286\codeC{this_exception_context}. The main exception handling code is in
287\texttt{libcfa} and that library also defines the function as a weak symbol
288so it acts as a default. Meanwhile in \texttt{libcfathread} the function is
289defined as a strong symbol that replaces it when the libraries are linked
290together.
291
292The version of the function defined in \texttt{libcfa} is very simple. It
293returns a pointer to a global static variable. With only one stack this
294global instance is associated with the only stack.
295
296The version of the function defined in \texttt{libcfathread} has to handle
297more as there are multiple stacks. The exception context is included as
298part of the per-stack data stored as part of coroutines. In the cold data
299section, stored at the base of each stack, is the exception context for that
300stack. The \codeC{this_exception_context} uses the concurrency library to get
301the current coroutine and through it the cold data section and the exception
302context.
303
304\section{Termination}
305% Memory management & extra information, the custom function used to implement
306% catches. Talk about GCC nested functions.
307
308Termination exceptions use libunwind quite heavily because it matches the
309intended use from \CPP exceptions very closely. The main complication is that
310since the \CFA compiler works by translating to C code it cannot generate the
311assembly to form the LSDA for try blocks or destructors.
312
313\subsection{Memory Management}
314The first step of termination is to copy the exception into memory managed by
315the exception system. Currently the system just uses malloc, without reserved
316memory or and ``small allocation" optimizations. The exception handling
317mechanism manages memory for the exception as well as memory for libunwind
318and the system's own per-exception storage.
319
320Exceptions are stored in variable sized block. The first component is a fixed
321sized data structure that contains the information for libunwind and the
322exception system. The second component is a blob of memory that is big enough
323to store the exception. Macros with pointer arthritic and type cast are
324used to move between the components or go from the embedded
325\codeC{_Unwind_Exception} to the entire node.
326
327All of these nodes are strung together in a linked list. One linked list per
328stack, with the head stored in the exception context. Within each linked list
329the most recently thrown exception is at the head and the older exceptions
330are further down the list. This list format allows exceptions to be thrown
331while a different exception is being handled. Only the exception at the head
332of the list is currently being handled, the other will wait for the
333exceptions before them to be removed.
334
335The virtual members in the exception's virtual table. The size of the
336exception, the copy function and the free function are all in the virtual
337table so they are decided per-exception type. The size and copy function are
338used right away when the exception is copied in to managed memory. After the
339exception is handled the free function is used to clean up the exception and
340then the entire node is passed to free.
341
342\subsection{Try Statements \& Catch Clauses}
343The try statements with termination handlers have a pretty complex conversion
344to compensate for the lack of assembly generation. Libunwind requires an LSDA
345(Language Specific Data Area) and personality function for a function to
346unwind across it. The LSDA in particular is hard to generate at the level of
347C which is what the \CFA compiler outputs so a work-around is used.
348
349This work around is a function called \codeC{__cfaehm_try_terminate} in the
350standard library. The contents of a try block and the termination handlers
351are converted into functions. These are then passed to the try terminate
352function and it calls them. This puts the try statements in their own
353functions so that no function has to deal with both termination handlers and
354destructors.
355
356This function has some custom embedded assembly that defines its personality
357function and LSDA. This is hand coded in C which is why there is only one
358version of it, the compiler has no capability to generate it. The personality
359function is structured so that it may be expanded, but really it only handles
360this one function. Notably it does not handle any destructors so the function
361is constructed so that it does need to run it.
362
363The three functions passed to try terminate are:
364\begin{itemize}
365\item The try function: This function is the try block, all the code inside
366the try block is placed inside the try function. It takes no parameters and
367has no return value. This function is called during regular execution to run
368the try block.
369\item The match function: This function decides if this try statement should
370handle any given termination exception. It takes a pointer to the exception
371and returns 0 if the exception is not handled here. Otherwise the return value
372is the id of the handler that should handle the exception. It is called
373during the search phase.
374It is constructed from the conditional part of each handler. It runs each
375check in turn, first checking to see if the object
376\item The catch function: This function handles the exception. It takes a
377pointer to the exception and the handler's id and returns nothing. It is
378called after the clean-up phase.
379It is constructed by stitching together the bodies of each handler
380\end{itemize}
381All three are created with GCC nested functions. GCC nested functions can be
382used to create closures, functions that can refer to the state of other
383functions on the stack. This allows the functions to refer to the main
384function and all the variables in scope.
385
386These nested functions and all other functions besides
387\codeC{__cfaehm_try_terminate} in \CFA use the GCC personality function and
388the \texttt{-fexceptions} flag to generate the LSDA. This allows destructors
389to be implemented with the cleanup attribute.
390
391\section{Resumption}
392% The stack-local data, the linked list of nodes.
393
394Resumption uses a list of nodes for its stack traversal. The head of the list
395is stored in the exception context. The nodes in the list just have a pointer
396to the next node and a pointer to the handler function.
397
398The on a resumption throw the this list is traversed. At each node the
399handler function is called and is passed the exception by pointer. It returns
400true if the exception was handled and false otherwise.
401
402The handler function does both the matching and catching. It tries each
403the condition of \codeCFA{catchResume} in order, top-to-bottom and until it
404finds a handler that matches. If no handler matches then the function returns
405false. Otherwise the matching handler is run, if it completes successfully
406the function returns true. Rethrows, through the \codeCFA{throwResume;}
407statement, cause the function to return true.
408
409\subsection{Libunwind Compatibility}
410Resumption does not use libunwind for two simple reasons. The first is that
411it does not have to unwind anything so would never need to use the clean-up
412phase. Still the search phase could be used to make it free to enter or exit
413a try statement with resumption handlers in the same way termination handlers
414are for the same trade off in the cost of the throw. This is where the second
415reason comes in, there is no way to return from a search without installing
416a handler or raising an error.
417
418Although work arounds could be created none seemed to be worth it for the
419prototype. This implementation has no difference in behaviour and is much
420simpler.
421% Seriously, just compare the size of the two chapters and then consider
422% that unwind is required knowledge for that chapter.
423
424\section{Finally}
425% Uses destructors and GCC nested functions.
426Finally clauses are a simple decomposition to some of the existing features.
427The code in the block is placed into a GCC nested function with a unique name,
428no arguments or return values. This nested function is then set as the
429clean-up function of an empty object that is declared at the beginning of a
430block placed around the contexts of the try statement.
431
432The rest is handled by GCC. The try block and all handlers are inside the
433block. When they are complete control exits the block and the empty object
434is cleaned up, which runs the function that contains the finally code.
435
436\section{Cancellation}
437% Stack selections, the three internal unwind functions.
438
439Cancellation also uses libunwind to do its stack traversal and unwinding,
440however it uses a different primary function \codeC{_Unwind_ForcedUnwind}.
441Details of its interface can be found in the unwind section.
442
443The first step of cancellation is to find the stack was cancelled and which
444type of stack it is. Luckily the threads library stores the main thread
445pointer and the current thread pointer and every thread stores a pointer to
446its main coroutine and the coroutine it is currently executing.
447
448So if the the current thread's main and current coroutine do not match, it is
449a coroutine cancellation. Otherwise if the main and current thread do not
450match, it is a thread cancellation. Otherwise it is a main thread
451cancellation.
452
453However if the threading library is not linked then execution must be on the
454main stack as that is the only one that exists. So the entire check is skipped
455using the linker and weak symbols. Instead the main thread cancellation is
456unconditionally preformed.
457
458Regardless of how they are choosen afterwords the stop function and the stop
459parameter are passed to the forced unwind functon. The general pattern of all
460three stop functions is the same, they continue unwinding until the end of
461stack when they do there primary work.
462
463Main stack cancellation it is very simple. The ``transfer" is just an abort,
464the program stops executing.
465
466The coroutine cancellation stores the exception on the coroutine and then
467does a coroutine context switch. The rest is handled inside resume. Every time
468control returns from a resumed thread there is a check to see if it is
469cancelled. If it is the exception is retrieved and the CoroutineCancelled
470exception is constructed and loaded. It is then thrown as a regular exception
471with the default handler coming from the context of the resumption call.
472
473The thread cancellation stores the exception on the thread's main stack and
474then returns to the scheduler. The rest is handled by the joiner. The wait
475for the joined thread to finish works the same but after that it checks
476to see if there was a cancellation. If there was the exception is retrieved
477and the ThreadCancelled exception is constructed. The default handler is
478passed in as a function pointer. If it is null (as it is for the
479auto-generated joins on destructor call) it a default is used that simply
480calls abort; which gives the required handling on implicate join.
Note: See TracBrowser for help on using the repository browser.