Index: doc/theses/andrew_beach_MMath/future.tex =================================================================== --- doc/theses/andrew_beach_MMath/future.tex (revision cb5c392b0536a1a55c7cbe8e310dd3f3d21f3367) +++ doc/theses/andrew_beach_MMath/future.tex (revision 27c97673eaef007dbc6ced268535966743ca910d) @@ -7,5 +7,5 @@ that I had to workaround while building an exception handling system largely in the \CFA language (some C components). The following are a few of these -issues, and once implemented/fixed, how this would affect the exception system. +issues, and once implemented/fixed, how they would affect the exception system. \begin{itemize} \item @@ -13,9 +13,11 @@ hand-crafted assembly statements. These sections must be ported by hand to support more hardware architectures, such as the ARM processor. +\PAB{I think this is a straw-man problem because the hand-coded assembler code +has to be generated somewhere, and that somewhere is hand-coded.} \item Due to a type-system problem, the catch clause cannot bind the exception to a reference instead of a pointer. Since \CFA has a very general reference capability, programmers will want to use it. Once fixed, this capability should -result in little or no change in the exception system. +result in little or no change in the exception system but simplify usage. \item Termination handlers cannot use local control-flow transfers, \eg by @break@, @@ -28,8 +30,8 @@ There is no detection of colliding unwinds. It is possible for clean-up code run during an unwind to trigger another unwind that escapes the clean-up code -itself; such as a termination exception caught further down the stack or a -cancellation. There do exist ways to handle this but currently they are not -even detected and the first unwind will simply be forgotten, often leaving -it in a bad state. +itself, \eg, a termination exception caught further down the stack or a +cancellation. There do exist ways to handle this issue, but currently they are not +even detected and the first unwind is simply dropped, often leaving +it in a bad state. \Cpp terminates the program in this case, and Java picks the ... \item Also the exception system did not have a lot of time to be tried and tested. @@ -41,5 +43,5 @@ The virtual system should be completed. It was not supposed to be part of this project, but was thrust upon it to do exception inheritance; hence, only -minimal work was done. A draft for a complete virtual system is available but +minimal work is done. A draft for a complete virtual system is available but it is not finalized. A future \CFA project is to complete that work and then update the exception system that uses the current version. @@ -67,7 +69,7 @@ bad software engineering. -Non-local/concurrent requires more coordination between the concurrency system +Non-local/concurrent raise requires more coordination between the concurrency system and the exception system. Many of the interesting design decisions centre -around masking (controlling which exceptions may be thrown at a stack). It +around masking, \ie controlling which exceptions may be thrown at a stack. It would likely require more of the virtual system and would also effect how default handlers are set. @@ -85,26 +87,22 @@ \section{Checked Exceptions} -Checked exceptions make exceptions part of a function's type by adding the +Checked exceptions make exceptions part of a function's type by adding an exception signature. An exception signature must declare all checked -exceptions that could propogate from the function (either because they were +exceptions that could propagate from the function (either because they were raised inside the function or came from a sub-function). This improves safety by making sure every checked exception is either handled or consciously passed on. -However checked exceptions were never seriously considered for this project -for two reasons. The first is due to time constraints, even copying an -existing checked exception system would be pushing the remaining time and -trying to address the second problem would take even longer. The second -problem is that checked exceptions have some real usability trade-offs in +However checked exceptions were never seriously considered for this project because +they have significant usability and reuse trade-offs in exchange for the increased safety. - These trade-offs are most problematic when trying to pass exceptions through higher-order functions from the functions the user passed into the higher-order function. There are no well known solutions to this problem -that were statifactory for \CFA (which carries some of C's flexability -over safety design) so one would have to be researched and developed. +that were satisfactory for \CFA (which carries some of C's flexibility +over safety design) so additional research is needed. -Follow-up work might add checked exceptions to \CFA, possibly using -polymorphic exception signatures, a form of tunneling\cite{Zhang19} or +Follow-up work might find a compromise design for checked exceptions in \CFA, possibly using +polymorphic exception signatures, a form of tunneling\cite{Zhang19}, or checked and unchecked raises. @@ -150,8 +148,8 @@ For instance, resumption could be extended to cover this use by allowing local control flow out of it. This approach would require an unwind as part of the -transition as there are stack frames that have to be removed. This approach -means there is no notify raise, but because \CFA does not have exception -signatures, a termination can be thrown from within any resumption handler so -there is already a way to do mimic this in existing \CFA. +transition as there are stack frames that have to be removed back to the resumption handler. This approach +means no special statement is required in the handler to continue after it. +Currently, \CFA allows a termination exception to be thrown from within any resumption handler so +there is already a way to partially mimic signal exceptions. % Maybe talk about the escape; and escape CONTROL_STMT; statements or how Index: doc/theses/andrew_beach_MMath/implement.tex =================================================================== --- doc/theses/andrew_beach_MMath/implement.tex (revision cb5c392b0536a1a55c7cbe8e310dd3f3d21f3367) +++ doc/theses/andrew_beach_MMath/implement.tex (revision 27c97673eaef007dbc6ced268535966743ca910d) @@ -2,5 +2,5 @@ \label{c:implement} -The implementation work for this thesis covers two components: the virtual +The implementation work for this thesis covers the two components: virtual system and exceptions. Each component is discussed in detail. @@ -17,37 +17,39 @@ 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 +The field is fixed after construction and is the first field in the structure so that its location is always known. \todo{Talk about constructors for virtual types (after they are working).} -This is what binds an instance of a virtual type to a virtual table. This -pointer can be used as an identity check. It can also be used to access the +The virtual-table pointer is what binds an instance of a virtual type to its virtual table. This +pointer is used as an identity check, and to access 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 (the types reperented are the same) +Type ids can be compared for equality (\ie the types represented are the same) or used to access the type's type information. The type information currently is only the parent's type id or, if the -type has no parent, zero. +type has no parent, @0p@. The id's are implemented as pointers to the type's type information instance. -Derefencing the pointer gets the type information. -By going back-and-forth between the type id and -the type info one can find every ancestor of a virtual type. -It also pushes the issue of creating a unique value (for +Dereferencing the pointer gets the type information. +The ancestors of a virtual type are found by traversing the type id through +the type information. +An id also 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. +information), which the linker can solve. Advanced linker support is required because there is no place that appears only once to attach the type information to. There should be one structure -definition but it is included in multiple translation units. Each virtual -table definition should be unique but there are an arbitrary number of thoses. -So the special section prefix \texttt{.gnu.linkonce} is used. -With a unique suffix (making the entire section name unique) the linker will -remove multiple definition making sure only one version exists after linking. +definition but it is included in multiple translation units because of separate compilation. Each virtual +table definition should be unique but there are an arbitrary number of these, +so the special section prefix \texttt{.gnu.linkonce} is used. +With a generated unique suffix (making the entire section name unique) the linker +removes multiple definition ensuring only one version exists after linking. Then it is just a matter of making sure there is a unique name for each type. -This is done in three phases. +These steps are done in three phases. +\begin{enumerate} +\item The first phase is to generate a new structure definition to store the type information. The layout is the same in each case, just the parent's type id, @@ -55,19 +57,20 @@ The structure's name is change, it is based off the virtual type's name, and the type of the parent's type id. -If the virtual type is polymorphic then the type information structure is +If the virtual type is polymorphic, then the type information structure is polymorphic as well, with the same polymorphic arguments. - +\item The second phase is to generate an instance of the type information with a almost unique name, generated by mangling the virtual type name. - +\item The third phase is implicit with \CFA's overloading scheme. \CFA mangles names with type information so that all of the symbols exported to the linker -are unique even if in \CFA code they are the same. Having two declarations +are unique even if in the \CFA code they are the same. Having two declarations with the same name and same type is forbidden because it is impossible for -overload resolution to pick between them. This is why a unique type is +overload resolution to pick between them. This is the reason why a unique type is generated for each virtual type. Polymorphic information is included in this mangling so polymorphic -types will have seperate instances for each set of polymorphic arguments. - +types have separate instances for each set of polymorphic arguments. +\end{enumerate} +The following example shows the components for a generated virtual type. \begin{cfa} struct TYPE_ID_TYPE { @@ -81,26 +84,26 @@ \end{cfa} -\subsubsection{cfa\_linkonce Attribute} +\subsubsection{\lstinline{cfa_linkonce} Attribute} Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}. -This attribute can be put on an object or function definition -(any global declaration with a name and a type). -This allows you to define that object or function multiple times. -All definitions should have the link-once attribute on them and all should +This attribute is attached to an object or function definition +(any global declaration with a name and a type) +allowing it to be defined multiple times. +All matching definitions must have the link-once attribute on them and should be identical. - -The simplist way to use it is to put a definition in a header where the -forward declaration would usually go. -This is how it is used for type-id instances. There was is no unique location -associated with a type except for the type definition which is in a header. -This allows the unique type-id object to be generated there. - -Internally @cfa_linkonce@ removes all @section@ attributes -from the declaration (as well as itself) and replaces them with +This attributed prototype is placed in a header file with other +forward declaration. + +This technique is used for type-id instances, as there is no unique location +associated with a type, except for the type definition in a header. +The result is the unique type-id object generated by the linker. + +Internally, @cfa_linkonce@ is replaced with @section(".gnu.linkonce.NAME")@ where \texttt{NAME} is replaced by the mangled name of the object. +Any other @section@ attributes are also removed from the declaration. The prefix \texttt{.gnu.linkonce} in section names is recognized by the -linker. If two of these sections with the same name, including everything -that comes after the special prefix, then only one will be used and the other -will be discarded. +linker. If two of these sections appear with the same name, including everything +that comes after the special prefix, then only one is used and the other +discarded. \subsection{Virtual Table} @@ -112,14 +115,20 @@ below. -The layout always comes in three parts. +Figure~\ref{f:VirtualTableLayout} shows the layout is in three parts. +\PAB{Number the parts in the figure.} +\begin{enumerate} +\item The first section is just the type id at the head of the table. It is always -there to ensure that +there to ensure that \PAB{... missing text to end this sentence} +\item The second section are all the virtual members of the parent, in the same order as they appear in the parent's virtual table. Note that the type may -change slightly as references to the ``this" will change. This is limited to +change slightly as references to the @this@ change. This structure is limited to inside pointers/references and via function pointers so that the size (and hence the offsets) are the same. +\item The third section is similar to the second except that it is the new virtual members introduced at this level in the hierarchy. +\end{enumerate} \begin{figure} @@ -133,29 +142,32 @@ 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 -for any virtual type it doesn't matter if we have it or any of its -descendants, it is still always safe to access the virtual table through +for any virtual type, it or any of its +descendants can be accessed through the virtual table pointer. -From there it is safe to check the type id to identify the exact type of the -underlying object, access any of the virtual members and pass the object to +From there, it is safe to check the type id to identify the exact type of the +underlying object, access any of the virtual members, and pass the object to any of the method-like virtual members. -When a virtual table is declared the user decides where to declare it and its +When a virtual table is declared, the user decides where to declare it and its name. The initialization of the virtual table is entirely automatic based on the context of the declaration. -The type id is always fixed, each virtual table type will always have one +The type id is always fixed with each virtual table type having exactly one possible type id. -The virtual members are usually filled in by resolution. The best match for -a given name and type at the declaration site is filled in. +The virtual members are usually filled in during type resolution. The best match for +a given name and type at the declaration site is used. There are two exceptions to that rule: the @size@ field is the type's size -and is set to the result of a @sizeof@ expression, the @align@ field is the -type's alignment and similarly uses an @alignof@ expression. +set using a @sizeof@ expression, and the @align@ field is the +type's alignment set using an @alignof@ expression. \subsubsection{Concurrency Integration} Coroutines and threads need instances of @CoroutineCancelled@ and @ThreadCancelled@ respectively to use all of their functionality. When a new -data type is declared with @coroutine@ or @thread@ the forward declaration for +data type is declared with @coroutine@ or @thread@, a forward declaration for the instance is created as well. The definition of the virtual table is created at the definition of the main function. + +Figure~\ref{f:ConcurrencyTransformations} shows ... +\todo{Improve Concurrency Transformations figure.} \begin{figure} @@ -194,5 +206,4 @@ \label{f:ConcurrencyTransformations} \end{figure} -\todo{Improve Concurrency Transformations figure.} \subsection{Virtual Cast} @@ -211,11 +222,11 @@ the cast target is passed in as @child@. -For C generation both arguments and the result are wrapped with type casts. -There is also an internal store inside the compiler to make sure that the +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. % It also checks for conflicting definitions. -The virtual cast either returns the original pointer as a new type or null. -So the function just does the parent check and returns the approprate value. +The virtual cast either returns the original pointer as a new type or 0p. +So the function just does the parent check and returns the appropriate value. The parent check is a simple linear search of child's ancestors using the type information. @@ -229,5 +240,5 @@ % resumption doesn't as well. -% Many modern languages work with an interal stack that function push and pop +% Many modern languages work with an internal stack that function push and pop % their local data to. Stack unwinding removes large sections of the stack, % often across functions. @@ -236,22 +247,21 @@ 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 +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. Usually, the stack-frame size is known statically based on parameter and -local variable declarations. Even with dynamic stack-size the information -to determain how much of the stack has to be removed is still contained +local variable declarations. Even with dynamic stack-size, the information +to determine how much of the stack has to be removed is still contained within the function. Allocating/deallocating stack space is usually an $O(1)$ operation achieved by bumping the hardware stack-pointer up or down as needed. -Constructing/destructing values on the stack takes longer put in terms of -figuring out what needs to be done is of similar complexity. +In fact, constructing/destructing values within a stack frame is of similar complexity but often 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. -Without altering the main code path it is also hard to pass that work off +With separate compilation a function has no way of knowing what its callers +so it can not know how large those frames are. +Without altering the main code path, it is also hard to pass that work off to the caller. @@ -261,16 +271,16 @@ reseting to a snap-shot of an arbitrary but existing function frame on the stack. It is up to the programmer to ensure the snap-shot is valid when it is -reset and that all required clean-up from the unwound stacks is preformed. -This approach is fragile and forces a work onto the surounding code. - -With respect to that work forced onto the surounding code, +reset and that all required clean-up from the unwound stacks is performed. +This approach is fragile and forces extra work in the surrounding 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 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 -intention of these features, so they need to be handled automatically. - -To safely remove sections of the stack the language must be able to find and +None of these should be handled explicitly by the user --- that would contradict the +intention of these features --- so they need to be handled automatically. + +To safely remove sections of the stack, the language must be able to find and run these clean-up actions even when removing multiple functions unknown at the beginning of the unwinding. @@ -294,9 +304,9 @@ current stack frame, and what handlers should be checked. Theoretically, the LSDA can contain any information but conventionally it is a table with entries -representing regions of the function and what has to be done there during +representing regions of a function and what has to be done there during unwinding. These regions are bracketed by instruction addresses. If the instruction pointer is within a region's start/end, then execution is currently executing in that region. Regions are used to mark out the scopes of objects -with destructors and try blocks. +with destructors and @try@ blocks. % Libunwind actually does very little, it simply moves down the stack from @@ -314,12 +324,12 @@ int avar __attribute__(( cleanup(clean_up) )); \end{cfa} -The attribue is used on a variable and specifies a function, +The attribute is used on a variable and specifies a function, in this case @clean_up@, run when the variable goes out of scope. -This is enough to mimic destructors, but not try statements which can effect +This capability is enough to mimic destructors, but not @try@ statements which can effect the unwinding. -To get full unwinding support all of this has to be done directly with -assembly and assembler directives. Partiularly the cfi directives -\snake{.cfi_lsda} and \snake{.cfi_personality}. +To get full unwinding support, all of these components must done directly with +assembly and assembler directives, particularly the cfi directives +\snake{.cfi_Leda} and \snake{.cfi_personality}. \subsection{Personality Functions} @@ -327,5 +337,5 @@ section covers some of the important parts of the interface. -A personality function can preform different actions depending on how it is +A personality function can perform different actions depending on how it is called. \begin{lstlisting} @@ -364,12 +374,12 @@ The @exception_class@ argument is a copy of the -\code{C}{exception}'s @exception_class@ field. -This a number that identifies the exception handling mechanism that created -the - -The \code{C}{exception} argument is a pointer to the user +\code{C}{exception}'s @exception_class@ field, +which is a number that identifies the exception handling mechanism that created +the \PAB{... missing text to end this sentence} + +The \code{C}{exception} argument is a pointer to a user provided storage object. It has two public fields: the @exception_class@, which is described above, and the @exception_cleanup@ function. -The clean-up function is used by the EHM to clean-up the exception if it +The clean-up function is used by the EHM to clean-up the exception, if it should need to be freed at an unusual time, it takes an argument that says why it had to be cleaned up. @@ -382,8 +392,8 @@ messages for special cases (some of which should never be used by the personality function) and error codes. However, unless otherwise noted, the -personality function should always return @_URC_CONTINUE_UNWIND@. +personality function always return @_URC_CONTINUE_UNWIND@. \subsection{Raise Exception} -Raising an exception is the central function of libunwind and it performs a +Raising an exception is the central function of libunwind and it performs the two-staged unwinding. \begin{cfa} @@ -472,8 +482,8 @@ % catches. Talk about GCC nested functions. -\CFA termination exceptions use libunwind heavily because they match \Cpp +\CFA termination exceptions use libunwind heavily because they match \Cpp exceptions closely. The main complication for \CFA is that the compiler generates C code, making it very difficult to generate the assembly to -form the LSDA for try blocks or destructors. +form the LSDA for @try@ blocks or destructors. \subsection{Memory Management} @@ -485,4 +495,5 @@ \begin{figure} +\centering \input{exception-layout} \caption{Exception Layout} @@ -491,5 +502,5 @@ \todo*{Convert the exception layout to an actual diagram.} -Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}). +Exceptions are stored in variable-sized blocks (see Figure~\vref{f:ExceptionLayout}). The first component is a fixed-sized data structure that contains the information for libunwind and the exception system. The second component is an @@ -498,13 +509,13 @@ @_Unwind_Exception@ to the entire node. -Multipe exceptions can exist at the same time because exceptions can be +Multiple exceptions can exist at the same time because exceptions can be raised inside handlers, destructors and finally blocks. Figure~\vref{f:MultipleExceptions} shows a program that has multiple exceptions active at one time. Each time an exception is thrown and caught the stack unwinds and the finally -clause runs. This will throw another exception (until @num_exceptions@ gets -high enough) which must be allocated. The previous exceptions may not be +clause runs. This handler throws another exception (until @num_exceptions@ gets +high enough), which must be allocated. The previous exceptions may not be freed because the handler/catch clause has not been run. -So the EHM must keep them alive while it allocates exceptions for new throws. +Therefore, the EHM must keep all of these exceptions alive while it allocates exceptions for new throws. \begin{figure} @@ -559,5 +570,5 @@ \todo*{Work on multiple exceptions code sample.} -All exceptions are stored in nodes which are then linked together in lists, +All exceptions are stored in nodes, which are then linked together in lists one list per stack, with the list head stored in the exception context. Within each linked list, the most @@ -566,5 +577,5 @@ exception is being handled. The exception at the head of the list is currently being handled, while other exceptions wait for the exceptions before them to be -removed. +handled and removed. The virtual members in the exception's virtual table provide the size of the @@ -573,18 +584,18 @@ exception into managed memory. After the exception is handled, the free function is used to clean up the exception and then the entire node is -passed to free so the memory can be given back to the heap. +passed to free so the memory is returned to the heap. \subsection{Try Statements and Catch Clauses} -The try statement with termination handlers is complex because it must -compensate for the lack of assembly-code generated from \CFA. Libunwind +The @try@ statement with termination handlers is complex because it must +compensate for the C code-generation versus assembly-code generation 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 +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. 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), the LSDA can be generated ahead of time. @@ -592,10 +603,10 @@ embedded assembly. This assembly code is handcrafted using C @asm@ statements and contains -enough information for the single try statement the function repersents. +enough information for a single @try@ statement the function represents. The three functions passed to try terminate are: \begin{description} -\item[try function:] This function is the try block, all the code inside the -try block is placed inside the try function. It takes no parameters and has no +\item[try function:] This function is the @try@ block, where all the code inside the +@try@ block is wrapped inside the function. It takes no parameters and has no return value. This function is called during regular execution to run the try block. @@ -609,11 +620,13 @@ handler that matches the exception. -\item[handler function:] This function handles the exception. It takes a +\item[handler function:] This function handles the exception, where the code inside +is constructed by stitching together the bodies of +each handler of a @try@ statement and dispatches to the selected handler. +It takes a pointer to the exception and the handler's id and returns nothing. It is called -after the cleanup phase. It is constructed by stitching together the bodies of -each handler and dispatches to the selected handler. +after the cleanup phase. \end{description} All three functions are created with GCC nested functions. GCC nested functions -can be used to create closures, functions that can refer to the state of other +can be used to create closures, \ie functions that can refer to the state of other functions on the stack. This approach allows the functions to refer to all the variables in scope for the function containing the @try@ statement. These @@ -623,4 +636,7 @@ Using this pattern, \CFA implements destructors with the cleanup attribute. +Figure~\ref{f:TerminationTransformation} shows an example transformation for a \CFA @try@ +statement with @catch@ clauses into corresponding C functions. \PAB{Walk the reader through the example code.} + \begin{figure} \begin{cfa} @@ -633,4 +649,8 @@ } \end{cfa} + +\medskip +\hrule +\medskip \begin{cfa} @@ -683,32 +703,43 @@ % The stack-local data, the linked list of nodes. -Resumption simpler to implement than termination +Resumption is simpler to implement than termination because there is no stack unwinding. 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 list node representing a @try@ statement on the stack. The head of the list is stored in the exception context. -The nodes are stored in order, with the more recent try statements closer +The nodes are stored in order, with the more recent @try@ statements closer 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 +Instead of traversing the stack, resumption handling traverses the list. +At each node, the EHM checks to see if the @try@ statement it 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 +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. -In each node is a handler function which does most of the work there. -The handler function is passed the raised the exception and returns true -if the exception is handled and false if it cannot be handled here. - -For each @catchResume@ clause the handler function will: -check to see if the raised exception is a descendant type of the declared -exception type, if it is and there is a conditional expression then it will -run the test, if both checks pass the handling code for the clause is run -and the function returns true, otherwise it moves onto the next clause. +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. + +For each @catchResume@ clause, the handler function: +\begin{itemize} +\item +checks to see if the raised exception is a descendant type of the declared +exception type, +\item +if it is and there is a conditional expression then it +runs the test, +\item +if both checks pass the handling code for the clause is run and the function returns true, +\item +otherwise it moves onto the next clause. +\end{itemize} If this is the last @catchResume@ clause then instead of moving onto the next clause the function returns false as no handler could be found. + +Figure~\ref{f:ResumptionTransformation} shows an example transformation for a \CFA @try@ +statement with @catchResume@ clauses into corresponding C functions. \PAB{Walk the reader through the example code.} \begin{figure} @@ -753,5 +784,5 @@ % Recursive Resumption Stuff: -Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of +Figure~\ref{f:ResumptionMarking} shows the search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of the stack already examined, is accomplished by updating the front of the list as the @@ -759,14 +790,13 @@ 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. - This mechanism means the current handler and every handler that has already 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 +thrown during the handling of another resumption, the active handlers and all the other handler checked up to this point are not checked again. - -This structure also supports new handler added while the resumption is being +This structure also supports new handlers added while the resumption is being handled. These are added to the front of the list, pointing back along the stack -- the first one points over all the checked handlers -- and the ordering is maintained. +\PAB{Maybe number the figure and use the numbers in the description to help the reader follow.} \begin{figure} @@ -778,5 +808,5 @@ \label{p:zero-cost} -Note, the resumption implementation has a cost for entering/exiting a @try@ +Finally, the resumption implementation has a cost for entering/exiting a @try@ statement with @catchResume@ clauses, whereas a @try@ statement with @catch@ clauses has zero-cost entry/exit. While resumption does not need the stack @@ -798,5 +828,5 @@ around the context of the associated @try@ statement. -The rest is handled by GCC. The try block and all handlers are inside this +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 up, which runs the function that contains the finally code. @@ -812,21 +842,24 @@ coroutine or thread. Fortunately, the thread library stores the main thread pointer and the current thread pointer, and every thread stores a pointer to -its main coroutine and the coroutine it is currently executing. -\todo*{Consider adding a description of how threads are coroutines.} - -If a the current thread's main and current coroutines are the same then the -current stack is a thread stack. Furthermore it is easy to compare the -current thread to the main thread to see if they are the same. And if this -is not a thread stack then it must be a coroutine stack. +its coroutine and the coroutine it is currently executing. +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. +Note, the runtime considers a thread as a coroutine with an associated user-level thread; +hence, for many operations a thread and coroutine are treated uniformly. +%\todo*{Consider adding a description of how threads are coroutines.} + +% Furthermore it is easy to compare the +% current thread to the main thread to see if they are the same. And if this +% is not a thread stack then it must be a coroutine stack. However, if the threading library is not linked, the sequential execution is on the main stack. Hence, the entire check is skipped because the weak-symbol -function is loaded. Therefore, a main thread cancellation is unconditionally +function is loaded. Therefore, main thread cancellation is unconditionally performed. Regardless of how the stack is chosen, the stop function and parameter are passed to the forced-unwind function. The general pattern of all three stop -functions is the same: they continue unwinding until the end of stack and -then preform their transfer. +functions is the same: continue unwinding until the end of stack and +then perform the appropriate transfer. For main stack cancellation, the transfer is just a program abort. @@ -834,9 +867,11 @@ For coroutine cancellation, the exception is stored on the coroutine's stack, and the coroutine context switches to its last resumer. The rest is handled on -the backside of the resume, which check if the resumed coroutine is +the backside of the resume, which checks if the resumed coroutine is cancelled. If cancelled, the exception is retrieved from the resumed coroutine, and a @CoroutineCancelled@ exception is constructed and loaded with the cancelled exception. It is then resumed as a regular exception with the default handler coming from the context of the resumption call. +This semantics allows a cancellation to cascade through an arbitrary set of resumed +coroutines back to the thread's coroutine, performing cleanup along the way. For thread cancellation, the exception is stored on the thread's main stack and @@ -848,3 +883,5 @@ null (as it is for the auto-generated joins on destructor call), the default is used, which is a program abort. +This semantics allows a cancellation to cascade through an arbitrary set of joining +threads back to the program's main, performing cleanup along the way. %; which gives the required handling on implicate join. Index: doc/theses/andrew_beach_MMath/performance.tex =================================================================== --- doc/theses/andrew_beach_MMath/performance.tex (revision cb5c392b0536a1a55c7cbe8e310dd3f3d21f3367) +++ doc/theses/andrew_beach_MMath/performance.tex (revision 27c97673eaef007dbc6ced268535966743ca910d) @@ -6,37 +6,37 @@ Performance has been of secondary importance for most of this project. -The driving for has been to get the features working, the only performance -requirements were to make sure the tests for correctness rain in a reasonable +Instead, the goal has been to get the features working. +The only performance +requirements is to ensure the exception tests for correctness ran in a reasonable amount of time. -Still this is an implementation others could use for similar prototypes and -so the results still have some use. +Much of the implementation is still reasonable and could be used for similar prototypes. +Hence, +the work still has some use. +To get a rough idea about the \CFA implementation, tests are run on \CFA, C++ and Java, which have similar termination-handling exceptions. +Tests are also run on \CFA and uC++, which has similar resumption-handling exceptions. -\section{Test Set-Up} -Tests will be run on \CFA, C++ and Java. - +\section{Termination Comparison} C++ is the most comparable language because both it and \CFA use the same framework, libunwind. -In fact the comparison is almost entirely a quality of implementation +In fact, the comparison is almost entirely a quality of implementation comparison. \CFA's EHM has had significantly less time to be optimized and does not generate its own assembly. It does have a slight advantage in that there are some features it does not handle. -% Some languages I left out: -% Python: Its a scripting language, different -% uC++: Not well known and should the same results as C++, except for -% resumption which should be the same. -\todo{Can we find a good language to compare resumptions in.} +The Java comparison is an opportunity to compare a managed memory model with unmanaged, +to see if there are any effects related to the exception model. -All tests will be run inside a main loop which will perform the test -repeatedly. This is to avoid letting and start-up or tear-down time from +\subsection{Test Set-Up} +All tests are run inside a main loop that performs the test +repeatedly. This design avoids start-up or tear-down time from affecting the timing results. -This also means that tests cannot terminate the program, which does limit +A consequence is that tests cannot terminate the program, which does limit how tests can be implemented. There are catch-alls to keep unhandled -exceptions from terminating the program. +exceptions from terminating tests. -The exceptions used in this test will always be a new exception based off of -the base exception. This should minimize and preformance differences based +The exceptions used in this test are always a new exception based off of +the base exception. This requirement minimizes performance differences based on the object model. -Catch-alls will be done by catching the root exception type (not using \Cpp's +Catch-alls are done by catching the root exception type (not using \Cpp's \code{C++}{catch(...)}). @@ -44,9 +44,13 @@ hot. -\section{Tests} +\subsection{Tests} +The following tests capture the most important aspects of exception handling and should provide +a reasonable guide to programmers of where EHM costs occur. + \paragraph{Raise/Handle} What is the basic cost to raise and handle an exception? -There are a number of factors that can effect this, for \CFA this includes +There are a number of factors that can effect this. +For \CFA this includes the type of raise, @@ -61,5 +65,5 @@ This has the same set-up as the raise/handle test except the intermediate stack frames contain either an object declaration with a destructor or a -try statement with no handlers except for a finally clause. +@try@ statement with no handlers except and a @finally@ clause. \paragraph{Enter/Leave} @@ -67,5 +71,5 @@ is thrown? -This is the simplist pattern to test as it is a simple matter of entering +The test is a simple matter of entering and leaving a try statement. @@ -74,9 +78,9 @@ \paragraph{Re-throw and Conditional-Catch} -How expencive it is to run a non-exception type check for a handler? +How expensive it is to run a non-exception type check for a handler? In this case different languages approach this problem differently, either through a re-throw or a conditional-catch. -Where \CFA uses its condition other languages will have to unconditionally +Where \CFA uses its condition, other languages must unconditionally catch the exception then re-throw if the condition if the condition is false. @@ -86,5 +90,5 @@ % We could do a Cforall test without the catch all and a new default handler % that does a catch all. -As a point of comparison one of the raise/handle tests (which one?) has +As a point of comparison, one of the raise/handle tests (which one?) has same layout but never catches anything. @@ -100,2 +104,10 @@ %(I haven't actually figured out how to compare this, probably using something %related to -fexceptions.) + + +\section{Resumption Comparison} +% Some languages I left out: +% Python: Its a scripting language, different +% uC++: Not well known and should the same results as C++, except for +% resumption which should be the same. +\todo{Can we find a good language to compare resumptions in.}