Index: doc/theses/andrew_beach_MMath/implement.tex =================================================================== --- doc/theses/andrew_beach_MMath/implement.tex (revision 9cd37d9e390510919b7ab3ea6b4d4f2370f7c861) +++ doc/theses/andrew_beach_MMath/implement.tex (revision ba2e8f05748260ec30a40b77230dcf6447330b8a) @@ -20,70 +20,107 @@ \subsection{Virtual Type} -Virtual types only have one change to their structure: the addition of a -pointer to the virtual table, which is called the \emph{virtual-table pointer}. -Internally, the field is called \snake{virtual_table}. -The field is fixed after construction. It is always the first field in the +A virtual type~(see \autoref{s:virtuals}) has a pointer to a virtual table, +called the \emph{virtual-table pointer}, +which binds each instance of a virtual type to a virtual table. +Internally, the field is called \snake{virtual_table} +and is fixed after construction. +This pointer is also the table's id and how the system accesses the +virtual table and the virtual members there. +It is always the first field in the structure so that its location is always known. -\todo{Talk about constructors for virtual types (after they are working).} - -The virtual table pointer binds an instance of a virtual type -to a virtual table. -The pointer is also the table's id and how the system accesses the -virtual table and the virtual members there. + +% We have no special rules for these constructors. +Virtual table pointers are passed to the constructors of virtual types +as part of field-by-field construction. \subsection{Type Id} Every virtual type has a unique id. -Type ids can be compared for equality, -which checks if the types reperented are the same, -or used to access the type's type information. +These are used in type equality, to check if the representation of two values +are the same, and to access the type's type information. +This uniqueness means across a program composed of multiple translation +units (TU), not uniqueness across all programs or even across multiple +processes on the same machine. + +Our approach for program uniqueness is using a static declaration for each +type id, where the run-time storage address of that variable is guaranteed to +be unique during program execution. +The type id storage can also be used for other purposes, +and is used for type information. + +The problem is that a type id may appear in multiple TUs that compose a +program (see \autoref{ss:VirtualTable}); so the initial solution would seem +to be make it external in each translation unit. Honever, the type id must +have a declaration in (exactly) one of the TUs to create the storage. +No other declaration related to the virtual type has this property, so doing +this through standard C declarations would require the user to do it manually. + +Instead the linker is used to handle this problem. +% I did not base anything off of C++17; they are solving the same problem. +A new feature has been added to \CFA for this purpose, the special attribute +\snake{cfa_linkonce}, which uses the special section @.gnu.linkonce@. +When used as a prefix (\eg @.gnu.linkonce.example@) the linker does +not combine these sections, but instead discards all but one with the same +full name. + +So each type id must be given a unique section name with the linkonce +prefix. Luckily \CFA already has a way to get unique names, the name mangler. +For example, this could be written directly in \CFA: +\begin{cfa} +__attribute__((cfa_linkonce)) void f() {} +\end{cfa} +This is translated to: +\begin{cfa} +__attribute__((section(".gnu.linkonce._X1fFv___1"))) void _X1fFv___1() {} +\end{cfa} +This is done internally to access the name manglers. +This attribute is useful for other purposes, any other place a unique +instance required, and should eventually be made part of a public and +stable feature in \CFA. + +\subsection{Type Information} + +There is data stored at the type id's declaration, the type information. The type information currently is only the parent's type id or, if the type has no parent, the null pointer. - -The id's are implemented as pointers to the type's type information instance. -Dereferencing the pointer gets the type information. The ancestors of a virtual type are found by traversing type ids through the type information. -The information pushes the issue of creating a unique value (for -the type id) to the problem of creating a unique instance (for type -information), which the linker can solve. - -The advanced linker support is used here to avoid having to create -a new declaration to attach this data to. -With C/\CFA's header/implementation file divide for something to appear -exactly once it must come from a declaration that appears in exactly one -implementation file; the declarations in header files may exist only once -they can be included in many different translation units. -Therefore, structure's declaration will not work. -Neither will attaching the type information to the virtual table -- although -a vtable declarations are in implemention files they are not unique, see -\autoref{ss:VirtualTable}. -Instead the same type information is generated multiple times and then -the new attribute \snake{cfa_linkone} is used to removed duplicates. +An example using helper macros looks like: +\begin{cfa} +struct INFO_TYPE(TYPE) { + INFO_TYPE(PARENT) const * parent; +}; + +__attribute__((cfa_linkonce)) +INFO_TYPE(TYPE) const INFO_NAME(TYPE) = { + &INFO_NAME(PARENT), +}; +\end{cfa} Type information is constructed as follows: \begin{enumerate} \item -Use the type's name to generate a name for the type information structure. -This is saved so it may be reused. +Use the type's name to generate a name for the type information structure, +which is saved so it can be reused. \item Generate a new structure definition to store the type information. The layout is the same in each case, just the parent's type id, but the types used change from instance to instance. -The generated name is used for both this structure and, if relivant, the +The generated name is used for both this structure and, if relevant, the parent pointer. If the virtual type is polymorphic then the type information structure is polymorphic as well, with the same polymorphic arguments. \item -A seperate name for instances is generated from the type's name. +A separate name for instances is generated from the type's name. \item -The definition is generated and initialised. +The definition is generated and initialized. The parent id is set to the null pointer or to the address of the parent's type information instance. Name resolution handles the rest. \item \CFA's name mangler does its regular name mangling encoding the type of -the declaration into the instance name. This gives a completely unique name +the declaration into the instance name. +This process gives a completely unique name including different instances of the same polymorphic type. \end{enumerate} -\todo{The list is making me realise, some of this isn't ordered.} +\todo{The list is making me realize, some of this isn't ordered.} Writing that code manually, with helper macros for the early name mangling, @@ -100,6 +137,7 @@ \end{cfa} +\begin{comment} \subsubsection{\lstinline{cfa\_linkonce} Attribute} -% I just realised: This is an extension of the inline keyword. +% I just realized: This is an extension of the inline keyword. % An extension of C's at least, it is very similar to C++'s. Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}. @@ -126,4 +164,5 @@ everything that comes after the special prefix, then only one is used and the other is discarded. +\end{comment} \subsection{Virtual Table} @@ -176,5 +215,5 @@ type's alignment, is set using an @alignof@ expression. -\subsubsection{Concurrency Integration} +\subsection{Concurrency Integration} Coroutines and threads need instances of @CoroutineCancelled@ and @ThreadCancelled@ respectively to use all of their functionality. When a new @@ -183,11 +222,12 @@ at the definition of the main function. -This is showned through code re-writing in -\autoref{f:ConcurrencyTypeTransformation} and -\autoref{f:ConcurrencyMainTransformation}. -In both cases the original declaration is not modified, +These transformations are shown through code re-writing in +\autoref{f:CoroutineTypeTransformation} and +\autoref{f:CoroutineMainTransformation}. +Threads use the same pattern, with some names and types changed. +In both cases, the original declaration is not modified, only new ones are added. -\begin{figure} +\begin{figure}[htb] \begin{cfa} coroutine Example { @@ -207,6 +247,6 @@ extern CoroutineCancelled_vtable & _default_vtable; \end{cfa} -\caption{Concurrency Type Transformation} -\label{f:ConcurrencyTypeTransformation} +\caption{Coroutine Type Transformation} +\label{f:CoroutineTypeTransformation} \end{figure} @@ -229,6 +269,6 @@ &_default_vtable_object_declaration; \end{cfa} -\caption{Concurrency Main Transformation} -\label{f:ConcurrencyMainTransformation} +\caption{Coroutine Main Transformation} +\label{f:CoroutineMainTransformation} \end{figure} @@ -242,11 +282,11 @@ \begin{cfa} void * __cfa__virtual_cast( - struct __cfavir_type_td parent, - struct __cfavir_type_id const * child ); -\end{cfa} -The type id of target type of the virtual cast is passed in as @parent@ and + struct __cfavir_type_id * parent, + struct __cfavir_type_id * const * child ); +\end{cfa} +The type id for the target type of the virtual cast is passed in as +@parent@ and the cast target is passed in as @child@. - -For generated C code wraps both arguments and the result with type casts. +The generated C code wraps both arguments and the result with type casts. There is also an internal check inside the compiler to make sure that the target type is a virtual type. @@ -260,5 +300,5 @@ \section{Exceptions} -% Anything about exception construction. +\todo{The entire exceptions section.} \section{Unwinding} @@ -274,10 +314,8 @@ stack. On function entry and return, unwinding is handled directly by the call/return code embedded in the function. -In many cases, the position of the instruction pointer (relative to parameter -and local declarations) is enough to know the current size of the stack -frame. - + +% Discussing normal stack unwinding: Usually, the stack-frame size is known statically based on parameter and -local variable declarations. Even with dynamic stack-size, the information +local variable declarations. Even for a dynamic stack-size, the information to determine how much of the stack has to be removed is still contained within the function. @@ -285,12 +323,15 @@ bumping the hardware stack-pointer up or down as needed. Constructing/destructing values within a stack frame has -a similar complexity but can add additional work and take longer. - +a similar complexity but larger constants. + +% Discussing multiple frame stack unwinding: Unwinding across multiple stack frames is more complex because that information is no longer contained within the current function. -With seperate compilation a function has no way of knowing what its callers -are so it can't know how large those frames are. -Without altering the main code path it is also hard to pass that work off -to the caller. +With seperate compilation, +a function does not know its callers nor their frame layout. +Even using the return address, that information is encoded in terms of +actions in code, intermixed with the actions required finish the function. +Without changing the main code path it is impossible to select one of those +two groups of actions at the return site. The traditional unwinding mechanism for C is implemented by saving a snap-shot @@ -302,10 +343,11 @@ This approach is fragile and requires extra work in the surrounding code. -With respect to the extra work in the surounding code, +With respect to the extra work in the surrounding code, many languages define clean-up actions that must be taken when certain sections of the stack are removed. Such as when the storage for a variable -is removed from the stack or when a try statement with a finally clause is +is removed from the stack, possibly requiring a destructor call, +or when a try statement with a finally clause is (conceptually) popped from the stack. -None of these should be handled by the user --- that would contradict the +None of these cases should be handled by the user --- that would contradict the intention of these features --- so they need to be handled automatically. @@ -348,4 +390,5 @@ In plain C (which \CFA currently compiles down to) this flag only handles the cleanup attribute: +%\label{code:cleanup} \begin{cfa} void clean_up( int * var ) { ... } @@ -355,5 +398,5 @@ in this case @clean_up@, run when the variable goes out of scope. This feature is enough to mimic destructors, -but not try statements which can effect +but not try statements that affect the unwinding. @@ -399,10 +442,10 @@ @_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs the cleanup phase and uses a different means to decide when to stop -(see \vref{s:ForcedUnwind}). +(see \autoref{s:ForcedUnwind}). \end{enumerate} The @exception_class@ argument is a copy of the \code{C}{exception}'s @exception_class@ field, -which is a number that identifies the exception handling mechanism +which is a number that identifies the EHM that created the exception. @@ -494,5 +537,5 @@ needs its own exception context. -The exception context should be retrieved by calling the function +The current exception context should be retrieved by calling the function \snake{this_exception_context}. For sequential execution, this function is defined as @@ -519,5 +562,5 @@ The first step of a termination raise is to copy the exception into memory managed by the exception system. Currently, the system uses @malloc@, rather -than reserved memory or the stack top. The exception handling mechanism manages +than reserved memory or the stack top. The EHM manages memory for the exception as well as memory for libunwind and the system's own per-exception storage. @@ -618,21 +661,22 @@ \subsection{Try Statements and Catch Clauses} The try statement with termination handlers is complex because it must -compensate for the C code-generation versus +compensate for the C code-generation versus proper assembly-code generated from \CFA. Libunwind requires an LSDA and personality function for control to unwind across a function. The LSDA in particular is hard to mimic in generated C code. -The workaround is a function called @__cfaehm_try_terminate@ in the standard -library. The contents of a try block and the termination handlers are converted -into functions. These are then passed to the try terminate function and it -calls them. +The workaround is a function called \snake{__cfaehm_try_terminate} in the +standard \CFA library. The contents of a try block and the termination +handlers are converted into nested functions. These are then passed to the +try terminate function and it calls them, appropriately. Because this function is known and fixed (and not an arbitrary function that -happens to contain a try statement), the LSDA can be generated ahead +happens to contain a try statement), its LSDA can be generated ahead of time. -Both the LSDA and the personality function are set ahead of time using +Both the LSDA and the personality function for \snake{__cfaehm_try_terminate} +are set ahead of time using embedded assembly. This assembly code is handcrafted using C @asm@ statements and contains -enough information for a single try statement the function repersents. +enough information for the single try statement the function represents. The three functions passed to try terminate are: @@ -646,6 +690,10 @@ decides if a catch clause matches the termination exception. It is constructed from the conditional part of each handler and runs each check, top to bottom, -in turn, first checking to see if the exception type matches and then if the -condition is true. It takes a pointer to the exception and returns 0 if the +in turn, to see if the exception matches this handler. +The match is performed in two steps, first a virtual cast is used to check +if the raised exception is an instance of the declared exception type or +one of its descendant types, and then the condition is evaluated, if +present. +The match function takes a pointer to the exception and returns 0 if the exception is not handled here. Otherwise the return value is the id of the handler that matches the exception. @@ -660,6 +708,8 @@ All three functions are created with GCC nested functions. GCC nested functions can be used to create closures, -in other words functions that can refer to the state of other -functions on the stack. This approach allows the functions to refer to all the +in other words, +functions that can refer to variables in their lexical scope even +those variables are part of a different function. +This approach allows the functions to refer to all the variables in scope for the function containing the @try@ statement. These nested functions and all other functions besides @__cfaehm_try_terminate@ in @@ -669,5 +719,5 @@ \autoref{f:TerminationTransformation} shows the pattern used to transform -a \CFA try statement with catch clauses into the approprate C functions. +a \CFA try statement with catch clauses into the appropriate C functions. \todo{Explain the Termination Transformation figure.} @@ -738,5 +788,5 @@ Instead of storing the data in a special area using assembly, there is just a linked list of possible handlers for each stack, -with each node on the list reperenting a try statement on the stack. +with each node on the list representing a try statement on the stack. The head of the list is stored in the exception context. @@ -744,15 +794,15 @@ to the head of the list. Instead of traversing the stack, resumption handling traverses the list. -At each node, the EHM checks to see if the try statement the node repersents +At each node, the EHM checks to see if the try statement the node represents can handle the exception. If it can, then the exception is handled and the operation finishes, otherwise the search continues to the next node. If the search reaches the end of the list without finding a try statement -that can handle the exception, the default handler is executed and the -operation finishes. +with a handler clause +that can handle the exception, the default handler is executed. +If the default handler returns, control continues after the raise statement. Each node has a handler function that does most of the work. The handler function is passed the raised exception and returns true if the exception is handled and false otherwise. - The handler function checks each of its internal handlers in order, top-to-bottom, until it funds a match. If a match is found that handler is @@ -760,7 +810,9 @@ If no match is found the function returns false. The match is performed in two steps, first a virtual cast is used to see -if the thrown exception is an instance of the declared exception or one of -its descendant type, then check to see if passes the custom predicate if one -is defined. This ordering gives the type guarantee used in the predicate. +if the raised exception is an instance of the declared exception type or one +of its descendant types, if so then it is passed to the custom predicate +if one is defined. +% You need to make sure the type is correct before running the predicate +% because the predicate can depend on that. \autoref{f:ResumptionTransformation} shows the pattern used to transform @@ -814,6 +866,7 @@ (see \vpageref{s:ResumptionMarking}), which ignores parts of the stack -already examined, is accomplished by updating the front of the list as the -search continues. Before the handler at a node is called, the head of the list +already examined, and is accomplished by updating the front of the list as +the search continues. +Before the handler is called at a matching node, the head of the list is updated to the next node of the current node. After the search is complete, successful or not, the head of the list is reset. @@ -822,5 +875,5 @@ been checked are not on the list while a handler is run. If a resumption is thrown during the handling of another resumption, the active handlers and all -the other handler checked up to this point are not checked again. +the other handlers checked up to this point are not checked again. % No paragraph? This structure also supports new handlers added while the resumption is being @@ -830,4 +883,5 @@ \begin{figure} +\centering \input{resumption-marking} \caption{Resumption Marking} @@ -851,12 +905,47 @@ \section{Finally} % Uses destructors and GCC nested functions. -A finally clause is placed into a GCC nested-function with a unique name, -and no arguments or return values. -This nested function is then set as the cleanup -function of an empty object that is declared at the beginning of a block placed -around the context of the associated @try@ statement. - -The rest is handled by GCC. The try block and all handlers are inside this -block. At completion, control exits the block and the empty object is cleaned + +%\autoref{code:cleanup} +A finally clause is handled by converting it into a once-off destructor. +The code inside the clause is placed into GCC nested-function +with a unique name, and no arguments or return values. +This nested function is +then set as the cleanup function of an empty object that is declared at the +beginning of a block placed around the context of the associated try +statement (see \autoref{f:FinallyTransformation}). + +\begin{figure} +\begin{cfa} +try { + // TRY BLOCK +} finally { + // FINALLY BLOCK +} +\end{cfa} + +\transformline + +\begin{cfa} +{ + void finally(void *__hook){ + // FINALLY BLOCK + } + __attribute__ ((cleanup(finally))) + struct __cfaehm_cleanup_hook __finally_hook; + { + // TRY BLOCK + } +} +\end{cfa} + +\caption{Finally Transformation} +\label{f:FinallyTransformation} +\end{figure} + +The rest is handled by GCC. +The TRY BLOCK +contains the try block itself as well as all code generated for handlers. +Once that code has completed, +control exits the block and the empty object is cleaned up, which runs the function that contains the finally code. @@ -887,5 +976,5 @@ passed to the forced-unwind function. The general pattern of all three stop functions is the same: continue unwinding until the end of stack and -then preform the appropriate transfer. +then perform the appropriate transfer. For main stack cancellation, the transfer is just a program abort.