Index: doc/theses/andrew_beach_MMath/implement.tex =================================================================== --- doc/theses/andrew_beach_MMath/implement.tex (revision 32b7f5484c2417ea7614a2c4c676cda1ff710fa8) +++ doc/theses/andrew_beach_MMath/implement.tex (revision 9f5a19faedb38ca69f5dbc95f44edc41fdda370b) @@ -20,86 +20,117 @@ \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 -structure so that its location is always known. +A virtual type~(see \autoref{s:Virtuals}) has a pointer to a virtual table, +called the \emph{virtual-table pointer}, which binds an 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. - \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. +Every virtual type needs a unique id, so that type ids can be compared for +equality, which checks if the types representation are the same, or used to +access the type's type information. Here, uniqueness means within a program +composed of multiple translation units (TU), not uniqueness across all +programs. + +One approach for program uniqueness is declaring a static declaration for each +type id, where the runtime storage address of that variable is guaranteed to be +unique during program execution. The type id storage can also be used for other +purposes. + +The problem is that a type id may appear in multiple TUs that compose a +program, see \autoref{ss:VirtualTable}; hence in each TU, it must be declared +as external to prevent multiple definitions. However, the type id must actually +be declared in one of the TUs so the linker creates the storage. Hence, the +problem becomes designating one TU to insert an actual type-id declaration. But +the \CFA compiler does not know the set of the translation units that compose a +program, because TUs can be compile separately, followed by a separate link +step. + +The solution is to mimic a \CFA feature in \Cpp{17}, @inline@ variables and +function: +\begin{quote} +There may be more than one definition of an inline function or variable (since +\Cpp{17} in the program as long as each definition appears in a different +translation unit and (for non-static inline functions and variables (since +\Cpp{17})) all definitions are identical. For example, an inline function or an +inline variable (since \Cpp{17}) may be defined in a header file that is +@#include@'d in multiple source files.~\cite{C++17} +\end{quote} +The underlying mechanism to provide this capability is attribute +\begin{cfa} +section(".gnu.linkonce.NAME") +\end{cfa} +where @NAME@ is the variable/function name duplicated in each TU. The linker than +provides the service of generating a single declaration (instance) across all +TUs, even if a program is linked incrementally. + +C does not support this feature for @inline@, and hence, neither does \CFA. +Again, rather than implement a new @inline@ extension for \CFA, a temporary +solution for the exception handling is to add the following in \CFA. +\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}] +@__attribute__((cfa_linkonce))@ void f() {} +\end{lstlisting} +which becomes +\begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}] +__attribute__((section(".gnu.linkonce._X1fFv___1"))) void @_X1fFv___1@(){} +\end{lstlisting} +where @NAME@ from above is the \CFA mangled variable/function name. Note, +adding this feature is necessary because, when using macros, the mangled name +is unavailable. This attribute is useful for purposes other than exception +handling, and should eventually be rolled into @inline@ processing in \CFA. + +Finally, a type id's data implements a pointers to the type's type information +instance. Dereferencing the pointer gets the type information. + +\subsection{Implementation} + 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. - -Type information is constructed as follows: +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} + +The 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 program 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.} - -Writing that code manually, with helper macros for the early name mangling, -would look like this: -\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} - +\todo{The list is making me realize, some of this isn't ordered.} + + +\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 +157,6 @@ everything that comes after the special prefix, then only one is used and the other is discarded. +\end{comment} + \subsection{Virtual Table} @@ -158,5 +191,5 @@ The first and second sections together mean that every virtual table has a prefix that has the same layout and types as its parent virtual table. -This, combined with the fixed offset to the virtual table pointer, means that +This, combined with the fixed offset to the virtual-table pointer, means that for any virtual type, it is always safe to access its virtual table and, from there, it is safe to check the type id to identify the exact type of the @@ -176,5 +209,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,9 +216,9 @@ 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, -only new ones are added. +These transformations are shown through code re-writing in +\autoref{f:CoroutineTypeTransformation} and +\autoref{f:CoroutineMainTransformation} for a coroutine and a thread is similar. +In both cases, the original declaration is not modified, only new ones are +added. \begin{figure} @@ -207,9 +240,11 @@ extern CoroutineCancelled_vtable & _default_vtable; \end{cfa} -\caption{Concurrency Type Transformation} -\label{f:ConcurrencyTypeTransformation} -\end{figure} - -\begin{figure} +\caption{Coroutine Type Transformation} +\label{f:CoroutineTypeTransformation} +%\end{figure} + +\bigskip + +%\begin{figure} \begin{cfa} void main(Example & this) { @@ -229,6 +264,6 @@ &_default_vtable_object_declaration; \end{cfa} -\caption{Concurrency Main Transformation} -\label{f:ConcurrencyMainTransformation} +\caption{Coroutine Main Transformation} +\label{f:CoroutineMainTransformation} \end{figure} @@ -245,8 +280,7 @@ struct __cfavir_type_id const * child ); \end{cfa} -The type id of target type of the virtual cast is passed in as @parent@ and +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 +294,5 @@ \section{Exceptions} -% Anything about exception construction. +\todo{Anything about exception construction.} \section{Unwinding} @@ -274,10 +308,10 @@ 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 +\PAB{Meaning: 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. +frame.} 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,10 +319,11 @@ 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, which takes longer. 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. +With separate compilation a function does not know its callers nor their frame size. +In general, the caller's frame size is embedded only at the functions entry (push +stack) and exit (pop stack). Without altering the main code path it is also hard to pass that work off to the caller. @@ -302,10 +337,10 @@ 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 (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. @@ -355,9 +390,9 @@ 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. To get full unwinding support, all of these features must be handled directly -in assembly and assembler directives; partiularly the cfi directives +in assembly and assembler directives; particularly the cfi directives \snake{.cfi_lsda} and \snake{.cfi_personality}. @@ -399,10 +434,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 +529,5 @@ needs its own exception context. -The exception context should be retrieved by calling the function +An exception context is retrieved by calling the function \snake{this_exception_context}. For sequential execution, this function is defined as @@ -519,5 +554,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,5 +653,5 @@ \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 @@ -624,15 +659,15 @@ 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. +\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 @__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 a single try statement the function represents. The three functions passed to try terminate are: @@ -646,6 +681,9 @@ 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, first checking to see if the exception type matches. +The match is performed in two steps, first a virtual cast is used to see +if the raised exception is an instance of the declared exception or one of +its descendant type, and then is the condition true, if present. +It 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 +698,6 @@ 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 their lexical scope in other +functions on the stack when called. 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 +707,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 +776,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 +782,14 @@ 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. +operation finishes, unless it throws an exception. 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,10 +797,11 @@ 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 or one of +its descendant type, and then is the condition true, if present. +\PAB{I don't understand this sentence. +This ordering gives the type guarantee used in the predicate.} \autoref{f:ResumptionTransformation} 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 Resumption Transformation figure.} @@ -814,6 +852,6 @@ (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 +860,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 +868,5 @@ \begin{figure} +\centering \input{resumption-marking} \caption{Resumption Marking} @@ -851,9 +890,40 @@ \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. +\autoref{f:FinallyTransformation} shows the pattern used to transform a \CFA +try statement with finally clause into the appropriate C functions. +The 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. + +\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 and all handlers are inside this @@ -869,9 +939,9 @@ The first step of cancellation is to find the cancelled stack and its type: -coroutine, thread or main thread. +coroutine, thread, or main thread. In \CFA, a thread (the construct the user works with) is a user-level thread (point of execution) paired with a coroutine, the thread's main coroutine. The thread library also stores pointers to the main thread and the current -thread. +coroutine. If the current thread's main and current coroutines are the same then the current stack is a thread stack, otherwise it is a coroutine stack. @@ -887,5 +957,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.