Context Navigation

-                      r4dcd5ea
+                      r7eb6eb5
 % Goes over how all the features are implemented.
+The implementation work for this thesis covers two components: the virtual
+system and exceptions. Each component is discussed in detail.
 \section{Virtual System}
+\label{s:VirtualSystem}
 % Virtual table rules. Virtual tables, the pointer to them and the cast.
+The \CFA virtual system only has one public facing feature: virtual casts.
+However there is a lot of structure to support that and provide some other
+features for the standard library.
+All of this is accessed through a field inserted at the beginning of every
+virtual type. Currently it is called @virtual_table@ but it is not
+ment to be accessed by the user. This field is a pointer to the type's
+virtual table instance. It is assigned once during the object's construction
+and left alone after that.
+\subsection{Virtual Table Construction}
+For each virtual type a virtual table is constructed. This is both a new type
+and an instance of that type. Other instances of the type could be created
+but the system doesn't use them. So this section will go over the creation of
+the type and the instance.
+Creating the single instance is actually very important. The address of the
+table acts as the unique identifier for the virtual type. Similarly the first
+field in every virtual table is the parent's id; a pointer to the parent
+virtual table instance.
+The remaining fields contain the type's virtual members. First come the ones
+present on the parent type, in the same order as they were the parent, and
+then any that this type introduces. The types of the ones inherited from the
+parent may have a slightly modified type, in that references to the
+dispatched type are replaced with the current virtual type. These are always
+taken by pointer or reference.
+The structure itself is created where the virtual type is created. The name
+of the type is created by mangling the name of the base type. The name of the
+instance is also generated by name mangling.
+The fields are initialized automatically.
+While the \CFA virtual system currently has only one public feature, virtual
+cast \see{\VPageref{p:VirtualCast}}, substantial structure is required to
+support it, and provide features for exception handling and the standard
+library.
+\subsection{Virtual Table}
+The virtual system is accessed through a private constant field inserted at the
+beginning of every virtual type, called the virtual-table pointer. This field
+points at a type's virtual table and is assigned during the object's
+construction.  The address of a virtual table acts as the unique identifier for
+the virtual type, and the first field of a virtual table is a pointer to the
+parent virtual-table or @0p@.  The remaining fields are duplicated from the
+parent tables in this type's inheritance chain, followed by any fields this type
+introduces. Parent fields are duplicated so they can be changed (\CC
+\lstinline[language=c++]|override|), so that references to the dispatched type
+are replaced with the current virtual type.
+\PAB{Can you create a simple diagram of the layout?}
+% These are always taken by pointer or reference.
+% For each virtual type, a virtual table is constructed. This is both a new type
+% and an instance of that type. Other instances of the type could be created
+% but the system doesn't use them. So this section will go over the creation of
+% the type and the instance.
+A virtual table is created when the virtual type is created. The name of the
+type is created by mangling the name of the base type. The name of the instance
+is also generated by name mangling.  The fields are initialized automatically.
 The parent field is initialized by getting the type of the parent field and
 using that to calculate the mangled name of the parent's virtual table type.
 There are two special fields that are included like normal fields but have
 special initialization rules: the @size@ field is the type's size and is
+initialized with a sizeof expression, the @align@ field is the type's
+alignment and uses an alignof expression. The remaining fields are resolved
+to a name matching the field's name and type using the normal visibility
+and overload resolution rules of the type system.
+These operations are split up into several groups depending on where they
+take place which can vary for monomorphic and polymorphic types. The first
+devision is between the declarations and the definitions. Declarations, such
+as a function signature or a structure's name, must always be visible but may
+be repeated so they go in headers. Definitions, such as function bodies and a
+structure's layout, don't have to be visible on use but must occur exactly
+once and go into source files.
+initialized with a @sizeof@ expression, the @align@ field is the type's
+alignment and uses an @alignof@ expression. The remaining fields are resolved
+to a name matching the field's name and type using the normal visibility and
+overload resolution rules of the type system.
+These operations are split up into several groups depending on where they take
+place which varies for monomorphic and polymorphic types. The first devision is
+between the declarations and the definitions. Declarations, such as a function
+signature or a aggregate's name, must always be visible but may be repeated in
+the form of forward declarations in headers. Definitions, such as function
+bodies and a aggregate's layout, can be separately compiled but must occur
+exactly once in a source file.
+\begin{sloppypar}
 The declarations include the virtual type definition and forward declarations
 of the virtual table instance, constructor, message function and
 @get_exception_vtable@. The definition includes the storage and
+initialization of the virtual table instance and the bodies of the three
+functions.
+@get_exception_vtable@. The definition includes the storage and initialization
+of the virtual table instance and the bodies of the three functions.
+\end{sloppypar}
 Monomorphic instances put all of these two groups in one place each.
 Polymorphic instances also split out the core declarations and definitions
 from the per-instance information. The virtual table type and most of the
+functions are polymorphic so they are all part of the core. The virtual table
+instance and the @get_exception_vtable@ function.
+Polymorphic instances also split out the core declarations and definitions from
+the per-instance information. The virtual table type and most of the functions
+are polymorphic so they are all part of the core. The virtual table instance
+and the @get_exception_vtable@ function.
+\begin{sloppypar}
 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 the instance is created as well. The definition
+of the virtual table is created at the definition of the main function.
+@ThreadCancelled@ respectively to use all of their functionality.  When a new
+data type is declared with @coroutine@ or @thread@ the forward declaration for
+the instance is created as well. The definition of the virtual table is created
+at the definition of the main function.
+\end{sloppypar}
 \subsection{Virtual Cast}
+Virtual casts are implemented as a function call that does the check and a
+old C-style cast to do the type conversion. The C-cast is just to make sure
+the generated code is correct so the rest of the section is about that
+function.
+The function is @__cfa__virtual_cast@ and it is implemented in the
+standard library. It takes a pointer to the target type's virtual table and
+the object pointer being cast. The function is very simple, getting the
+object's virtual table pointer and then checking to see if it or any of
+its ancestors, by using the parent pointers, are the same as the target type
+virtual table pointer. It does this in a simple loop.
+For the generated code a forward decaration of the virtual works as follows.
+There is a forward declaration of @__cfa__virtual_cast@ in every cfa
+file so it can just be used. The object argument is the expression being cast
+so that is just placed in the argument list.
+To build the target type parameter the compiler will create a mapping from
+concrete type-name -- so for polymorphic types the parameters are filled in
+-- to virtual table address. Every virtual table declaraction is added to the
+this table; repeats are ignored unless they have conflicting definitions.
+This does mean the declaractions have to be in scope, but they should usually
+be introduced as part of the type definition.
+Virtual casts are implemented as a function call that does the subtype check
+and a C coercion-cast to do the type conversion.
+% The C-cast is just to make sure the generated code is correct so the rest of
+% the section is about that function.
+The function is
+\begin{cfa}
+void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent,
+        struct __cfa__parent_vtable const * const * child );
+}
+\end{cfa}
+and it is implemented in the standard library. It takes a pointer to the target
+type's virtual table and the object pointer being cast. The function performs a
+linear search starting at the object's virtual-table and walking through the
+the parent pointers, checking to if it or any of its ancestors are the same as
+the target-type virtual table-pointer.
+For the generated code, a forward declaration of the virtual works as follows.
+There is a forward declaration of @__cfa__virtual_cast@ in every \CFA file so
+it can just be used. The object argument is the expression being cast so that
+is just placed in the argument list.
+To build the target type parameter, the compiler creates a mapping from
+concrete type-name -- so for polymorphic types the parameters are filled in --
+to virtual table address. Every virtual table declaration is added to the this
+table; repeats are ignored unless they have conflicting definitions.  Note,
+these declarations do not have to be in scope, but they should usually be
+introduced as part of the type definition.
+\PAB{I do not understood all of \VRef{s:VirtualSystem}. I think you need to
+write more to make it clear.}
 \section{Exceptions}
 …
 % resumption doesn't as well.
+Many modern languages work with an interal stack that function push and pop
+their local data to. Stack unwinding removes large sections of the stack,
+often across functions.
+At a very basic level this can be done with @setjmp@ \& @longjmp@
+which simply move the top of the stack, discarding everything on the stack
+above a certain point. However this ignores all the clean-up code that should
+be run when certain sections of the stack are removed (for \CFA these are from
+destructors and finally clauses) and also requires that the point to which the
+stack is being unwound is known ahead of time. libunwind is used to address
+both of these problems.
+Libunwind, provided in @unwind.h@ on most platorms, is a C library
+that provides \CPP style stack unwinding. Its operation is divided into two
+phases. The search phase -- phase 1 -- is used to scan the stack and decide
+where the unwinding will stop, this allows for a dynamic target. The clean-up
+phase -- phase 2 -- does the actual unwinding and also runs any clean-up code
+as it goes.
+To use the libunwind each function must have a personality function and an
+LSDA (Language Specific Data Area). Libunwind actually does very little, it
+simply moves down the stack from function to function. Most of the actions are
+implemented by the personality function which libunwind calls on every
+function. Since this is shared across many functions or even every function in
+a language it will need a bit more information. This is provided by the LSDA
+which has the unique information for each function.
+Theoretically the LSDA can contain anything but conventionally it is a table
+with entries reperenting areas of the function and what has to be done there
+during unwinding. These areas are described in terms of where the instruction
+pointer is. If the current value of the instruction pointer is between two
+values reperenting the beginning and end of a region then execution is
+currently being executed. These are used to mark out try blocks and the
+scopes of objects with destructors to run.
+GCC will generate an LSDA and attach its personality function with the
+@-fexceptions@ flag. However this only handles the cleanup attribute.
+This attribute is used on a variable and specifies a function that should be
+run when the variable goes out of scope. The function is passed a pointer to
+the object as well so it can be used to mimic destructors. It however cannot
+be used to mimic try statements.
+\subsection{Implementing Personality Functions}
+Personality functions have a complex interface specified by libunwind.
+This section will cover some of the important parts of that interface.
+\begin{lstlisting}
+typedef _Unwind_Reason_Code (*_Unwind_Personality_Fn)(
+    int version,
+    _Unwind_Action action,
+    _Unwind_Exception_Class exception_class,
+    _Unwind_Exception * exception,
+    struct _Unwind_Context * context);
+% Many modern languages work with an interal stack that function push and pop
+% their local data to. Stack unwinding removes large sections of the stack,
+% often across functions.
+Stack unwinding is the process of removing stack frames (activations) from the
+stack. On function entry and return, unwinding is handled directly by the code
+embedded in the function. Usually, the stack-frame size is known statically
+based on parameter and local variable declarations.  For dynamically-sized
+local variables, a runtime computation is necessary to know the frame
+size. Finally, a function's frame-size may change during execution as local
+variables (static or dynamic sized) go in and out of scope.
+Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
+bumping the hardware stack-pointer up or down as needed.
+Unwinding across multiple stack frames is more complex because individual stack
+management code associated with each frame is bypassed. That is, the location
+of a function's frame-management code is largely unknown and dispersed
+throughout the function, hence the current frame size managed by that code is
+also unknown. Hence, code unwinding across frames does not have direct
+knowledge about what is on the stack, and hence, how much of the stack needs to
+be removed.
+% At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply
+% move the top of the stack, discarding everything on the stack above a certain
+% point. However this ignores all the cleanup code that should be run when
+% certain sections of the stack are removed (for \CFA these are from destructors
+% and finally clauses) and also requires that the point to which the stack is
+% being unwound is known ahead of time. libunwind is used to address both of
+% these problems.
+The traditional unwinding mechanism for C is implemented by saving a snap-shot
+of a function's state with @setjmp@ and restoring that snap-shot with
+@longjmp@. This approach bypasses the need to know stack details by simply
+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, making this unwinding approach fragile with potential errors that are
+difficult to debug because the stack becomes corrupted.
+However, many languages define cleanup actions that must be taken when objects
+are deallocated from the stack or blocks end, such as running a variable's
+destructor or a @try@ statement's @finally@ clause. Handling these mechanisms
+requires walking the stack and checking each stack frame for these potential
+actions.
+For exceptions, it must be possible to walk the stack frames in search of @try@
+statements to match and execute a handler. For termination exceptions, it must
+also be possible to unwind all stack frames from the throw to the matching
+catch, and each of these frames must be checked for cleanup actions. Stack
+walking is where most of the complexity and expense of exception handling
+appears.
+One of the most popular tools for stack management is libunwind, a low-level
+library that provides tools for stack walking, handler execution, and
+unwinding. What follows is an overview of all the relevant features of
+libunwind needed for this work, and how \CFA uses them to implement exception
+handling.
+\subsection{libunwind Usage}
+Libunwind, accessed through @unwind.h@ on most platforms, is a C library that
+provides \CC-style stack-unwinding. Its operation is divided into two phases:
+search and cleanup. The dynamic target search -- phase 1 -- is used to scan the
+stack and decide where unwinding should stop (but no unwinding occurs). The
+cleanup -- phase 2 -- does the unwinding and also runs any cleanup code.
+To use libunwind, each function must have a personality function and a Language
+Specific Data Area (LSDA).  The LSDA has the unique information for each
+function to tell the personality function where a function is executing, its
+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
+unwinding. These regions are bracketed by the instruction pointer. 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.
+% Libunwind actually does very little, it simply moves down the stack from
+% function to function. Most of the actions are implemented by the personality
+% function which libunwind calls on every function. Since this is shared across
+% many functions or even every function in a language it will need a bit more
+% information.
+The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and
+attaches its personality function. \PAB{to what is it attached?}  However, this
+flag only handles the cleanup attribute
+\begin{cfa}
+void clean_up( int * var ) { ... }
+int avar __attribute__(( __cleanup(clean_up) ));
+\end{cfa}
+which is used on a variable and specifies a function, \eg @clean_up@, run when
+the variable goes out of scope. The function is passed a pointer to the object
+so it can be used to mimic destructors. However, this feature cannot be used to
+mimic @try@ statements.
+\subsection{Personality Functions}
+Personality functions have a complex interface specified by libunwind.  This
+section covers some of the important parts of the interface.
+A personality function performs four tasks, although not all have to be
+present.
+\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
+typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) (
+        _Unwind_Action @action@,
+        _Unwind_Exception_Class @exception_class@,
+        _Unwind_Exception * @exception@,
+        struct _Unwind_Context * @context@
+);
 \end{lstlisting}
+The return value, the reason code, is an enumeration of possible messages
+The @action@ argument is a bitmask of possible actions:
+\begin{enumerate}
+\item
+@_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function
+to check for handlers.  If there is a handler in a stack frame, as defined by
+the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise
+it return @_URC_CONTINUE_UNWIND@.
+\item
+@_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is
+unwound and all cleanup code is run. The personality function does whatever
+cleanup the language defines (such as running destructors/finalizers) and then
+generally returns @_URC_CONTINUE_UNWIND@.
+\item
+\begin{sloppypar}
+@_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a
+handler. The personality function must prepare to return to normal code
+execution and return @_URC_INSTALL_CONTEXT@.
+\end{sloppypar}
+\item
+@_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}}.
+\end{enumerate}
+The @exception_class@ argument is a copy of the
+\lstinline[language=C]|exception|'s @exception_class@ field.
+The \lstinline[language=C]|exception| argument is a pointer to the user
+provided storage object. It has two public fields, the exception class, which
+is actually just a number, identifying the exception handling mechanism that
+created it, and the cleanup function. The cleanup function is called if
+required by the exception.
+The @context@ argument is a pointer to an opaque type passed to helper
+functions called inside the personality function.
+The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages
 that can be passed several places in libunwind. It includes a number of
 messages for special cases (some of which should never be used by the
 …
 personality function should always return @_URC_CONTINUE_UNWIND@.
-The @version@ argument is the verson of the implementation that is
-calling the personality function. At this point it appears to always be 1 and
-it will likely stay that way until a new version of the API is updated.
-The @action@ argument is set of flags that tell the personality
-function when it is being called and what it must do on this invocation.
-The flags are as follows:
-\begin{itemize}
-\item@_UA_SEARCH_PHASE@: This flag is set whenever the personality
-function is called during the search phase. The personality function should
-decide if unwinding will stop in this function or not. If it does then the
-personality function should return @_URC_HANDLER_FOUND@.
-\item@_UA_CLEANUP_PHASE@: This flag is set whenever the personality
-function is called during the cleanup phase. If no other flags are set this
-means the entire frame will be unwound and all cleanup code should be run.
-\item@_UA_HANDLER_FRAME@: This flag is set during the cleanup phase
-on the function frame that found the handler. The personality function must
-prepare to return to normal code execution and return
-@_URC_INSTALL_CONTEXT@.
-\item@_UA_FORCE_UNWIND@: This flag is set if the personality function
-is called through a forced unwind call. Forced unwind only performs the
-cleanup phase and uses a different means to decide when to stop. See its
-section below.
-\end{itemize}
-The @exception_class@ argument is a copy of the @exception@'s
-@exception_class@ field.
-The @exception@ argument is a pointer to the user provided storage
-object. It has two public fields, the exception class which is actually just
-a number that identifies the exception handling mechanism that created it and
-the other is the clean-up function. The clean-up function is called if the
-exception needs to
-The @context@ argument is a pointer to an opaque type. This is passed
-to the many helper functions that can be called inside the personality
-function.
 \subsection{Raise Exception}
+This could be considered the central function of libunwind. It preforms the
+two staged unwinding the library is built around and most of the rest of the
+interface of libunwind is here to support it. It's signature is as follows:
+\begin{lstlisting}
+Raising an exception is the central function of libunwind and it performs a
+two-staged unwinding.
+\begin{cfa}
 _Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *);
+\end{cfa}
+First, the function begins the search phase, calling the personality function
+of the most recent stack frame. It continues to call personality functions
+traversing the stack from newest to oldest until a function finds a handler or
+the end of the stack is reached. In the latter case, raise exception returns
+@_URC_END_OF_STACK@.
+Second, when a handler is matched, raise exception continues onto the cleanup phase.
+Once again, it calls the personality functions of each stack frame from newest
+to oldest. This pass stops at the stack frame containing the matching handler.
+If that personality function has not install a handler, it is an error.
+If an error is encountered, raise exception returns either
+@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the
+error occurred.
+\subsection{Forced Unwind}
+\label{s:ForcedUnwind}
+Forced Unwind is the other central function in libunwind.
+\begin{cfa}
+_Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *,
+        _Unwind_Stop_Fn, void *);
+\end{cfa}
+It also unwinds the stack but it does not use the search phase. Instead another
+function, the stop function, is used to stop searching.  The exception is the
+same as the one passed to raise exception. The extra arguments are the stop
+function and the stop parameter. The stop function has a similar interface as a
+personality function, except it is also passed the stop parameter.
+\begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}]
+typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)(
+        _Unwind_Action @action@,
+        _Unwind_Exception_Class @exception_class@,
+        _Unwind_Exception * @exception@,
+        struct _Unwind_Context * @context@,
+        void * @stop_parameter@);
 \end{lstlisting}
-When called the function begins the search phase, calling the personality
-function of the most recent stack frame. It will continue to call personality
-functions traversing the stack new-to-old until a function finds a handler or
-the end of the stack is reached. In the latter case raise exception will
-return with @_URC_END_OF_STACK@.
-Once a handler has been found raise exception continues onto the the cleanup
-phase. Once again it will call the personality functins of each stack frame
-from newest to oldest. This pass will stop at the stack frame that found the
-handler last time, if that personality function does not install the handler
-it is an error.
-If an error is encountered raise exception will return either
-@_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending
-on when the error occured.
-\subsection{Forced Unwind}
-This is the second big function in libunwind. It also unwinds a stack but it
-does not use the search phase. Instead another function, the stop function,
-is used to decide when to stop.
-\begin{lstlisting}
-_Unwind_Reason_Code _Unwind_ForcedUnwind(
-    _Unwind_Exception *, _Unwind_Stop_Fn, void *);
-\end{lstlisting}
-The exception is the same as the one passed to raise exception. The extra
-arguments are the stop function and the stop parameter. The stop function has
-a similar interface as a personality function, except it is also passed the
-stop parameter.
-\begin{lstlisting}
-typedef _Unwind_Reason_Code (*_Unwind_Stop_Fn)(
-    int version,
-    _Unwind_Action action,
-    _Unwind_Exception_Class exception_class,
-    _Unwind_Exception * exception,
-    struct _Unwind_Context * context,
-    void * stop_parameter);
-\end{lstlisting}
 The stop function is called at every stack frame before the personality
+function is called and then once more once after all frames of the stack have
+been unwound.
+Each time it is called the stop function should return @_URC_NO_REASON@
+or transfer control directly to other code outside of libunwind. The
+framework does not provide any assistance here.
+Its arguments are the same as the paired personality function.
+The actions @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always
+set when it is called. By the official standard that is all but both GCC and
+Clang add an extra action on the last call at the end of the stack:
+@_UA_END_OF_STACK@.
+function is called and then once more after all frames of the stack are
+unwound.
+Each time it is called, the stop function should return @_URC_NO_REASON@ or
+transfer control directly to other code outside of libunwind. The framework
+does not provide any assistance here.
+\begin{sloppypar}
+Its arguments are the same as the paired personality function.  The actions
+@_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is
+called. Beyond the libunwind standard, both GCC and Clang add an extra action
+on the last call at the end of the stack: @_UA_END_OF_STACK@.
+\end{sloppypar}
 \section{Exception Context}
 % Should I have another independent section?
 % There are only two things in it, top_resume and current_exception. How it is
+% stored changes depending on wheither or not the thread-library is linked.
+The exception context is a piece of global storage used to maintain data
+across different exception operations and to communicate between different
+components.
+Each stack has its own exception context. In a purely sequental program, using
+only core Cforall, there is only one stack and the context is global. However
+if the library @libcfathread@ is linked then there can be multiple
+stacks so they will each need their own.
+To handle this code always gets the exception context from the function
+@this_exception_context@. The main exception handling code is in
+@libcfa@ and that library also defines the function as a weak symbol
+so it acts as a default. Meanwhile in @libcfathread@ the function is
+defined as a strong symbol that replaces it when the libraries are linked
+together.
+The version of the function defined in @libcfa@ is very simple. It
+returns a pointer to a global static variable. With only one stack this
+global instance is associated with the only stack.
+The version of the function defined in @libcfathread@ has to handle
+more as there are multiple stacks. The exception context is included as
+part of the per-stack data stored as part of coroutines. In the cold data
+section, stored at the base of each stack, is the exception context for that
+stack. The @this_exception_context@ uses the concurrency library to get
+the current coroutine and through it the cold data section and the exception
+context.
+% stored changes depending on whether or not the thread-library is linked.
+The exception context is global storage used to maintain data across different
+exception operations and to communicate among different components.
+Each stack must have its own exception context. In a sequential \CFA program,
+there is only one stack with a single global exception-context. However, when
+the library @libcfathread@ is linked, there are multiple stacks where each
+needs its own exception context.
+General access to the exception context is provided by function
+@this_exception_context@. For sequential execution, this function is defined as
+a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is
+concurrent, it links with @libcfathread@, where this function is defined with a
+strong symbol replacing the sequential version.
+% The version of the function defined in @libcfa@ is very simple. It returns a
+% pointer to a global static variable. With only one stack this global instance
+% is associated with the only stack.
+For coroutines, @this_exception_context@ accesses the exception context stored
+at the base of the stack. For threads, @this_exception_context@ uses the
+concurrency library to access the current stack of the thread or coroutine
+being executed by the thread, and then accesses the exception context stored at
+the base of this stack.
 \section{Termination}
 …
 % catches. Talk about GCC nested functions.
 Termination exceptions use libunwind quite heavily because it matches the
+intended use from \CPP exceptions very closely. The main complication is that
+since the \CFA compiler works by translating to C code it cannot generate the
 assembly to form the LSDA for try blocks or destructors.
+Termination exceptions use libunwind heavily because it matches the intended
+use from \CC 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.
 \subsection{Memory Management}
 The first step of termination is to copy the exception into memory managed by
+the exception system. Currently the system just uses malloc, without reserved
+memory or and ``small allocation" optimizations. The exception handling
 mechanism manages memory for the exception as well as memory for libunwind
 and the system's own per-exception storage.
 Exceptions are stored in variable sized block. The first component is a fixed
 sized data structure that contains the information for libunwind and the
+exception system. The second component is a blob of memory that is big enough
+to store the exception. Macros with pointer arthritic and type cast are
 used to move between the components or go from the embedded
+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
+memory for the exception as well as memory for libunwind and the system's own
+per-exception storage.
+Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout
+figure.} The first component is a fixed sized data structure that contains the
+information for libunwind and the exception system. The second component is an
+area of memory big enough to store the exception. Macros with pointer arthritic
+and type cast are used to move between the components or go from the embedded
 @_Unwind_Exception@ to the entire node.
+All of these nodes are strung together in a linked list. One linked list per
+stack, with the head stored in the exception context. Within each linked list
+the most recently thrown exception is at the head and the older exceptions
+are further down the list. This list format allows exceptions to be thrown
+while a different exception is being handled. Only the exception at the head
+of the list is currently being handled, the other will wait for the
+exceptions before them to be removed.
+The virtual members in the exception's virtual table. The size of the
+exception, the copy function and the free function are all in the virtual
+table so they are decided per-exception type. The size and copy function are
+used right away when the exception is copied in to 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.
+\subsection{Try Statements \& Catch Clauses}
+The try statements with termination handlers have a pretty complex conversion
+to compensate for the lack of assembly generation. Libunwind requires an LSDA
+(Language Specific Data Area) and personality function for a function to
+unwind across it. The LSDA in particular is hard to generate at the level of
+C which is what the \CFA compiler outputs so a work-around is used.
+This work around 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. This puts the try statements in their own
+functions so that no function has to deal with both termination handlers and
+destructors.
+This function has some custom embedded assembly that defines its personality
+function and LSDA. This is hand coded in C which is why there is only one
+version of it, the compiler has no capability to generate it. The personality
+function is structured so that it may be expanded, but really it only handles
+this one function. Notably it does not handle any destructors so the function
+is constructed so that it does need to run it.
+All of these nodes are linked together in a list, one list per stack, with the
+list head stored in the exception context. Within each linked list, the most
+recently thrown exception is at the head followed by older thrown
+exceptions. This format allows exceptions to be thrown, while a different
+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.
+The virtual members in the exception's virtual table provide the size of the
+exception, the copy function, and the free function, so they are specific to an
+exception type. The size and copy function are used immediately to copy an
+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.
+\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
+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. This approach puts a try statement in its own functions so that no
+function has to deal with both termination handlers and destructors. \PAB{I do
+not understand the previous sentence.}
+This function has some custom embedded assembly that defines \emph{its}
+personality function and LSDA. The assembly is created with handcrafted C @asm@
+statements, which is why there is only one version of it. The personality
+function is structured so that it can be expanded, but currently it only
+handles this one function.  Notably, it does not handle any destructors so the
+function is constructed so that it does need to run it. \PAB{I do not
+understand the previous sentence.}
 The three functions passed to try terminate are:
 \begin{itemize}
 \item The 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 return value. This function is called during regular execution to run
 the try block.
+\item The match function: This function decides if this try statement should
+handle any given termination exception. 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 should handle the exception. It is called
+during the search phase.
+It is constructed from the conditional part of each handler. It runs each
+check in turn, first checking to see if the object
+\item The catch function: This function handles the exception. It takes a
+pointer to the exception and the handler's id and returns nothing. It is
+called after the clean-up phase.
+It is constructed by stitching together the bodies of each handler
+\end{itemize}
+All three are created with GCC nested functions. GCC nested functions can be
+used to create closures, functions that can refer to the state of other
+functions on the stack. This allows the functions to refer to the main
+function and all the variables in scope.
+These nested functions and all other functions besides
+@__cfaehm_try_terminate@ in \CFA use the GCC personality function and
+the @-fexceptions@ flag to generate the LSDA. This allows destructors
 to be implemented with the cleanup attribute.
+\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
+return value. This function is called during regular execution to run the try
+block.
+\item[match function:] This function is called during the search phase and
+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
+exception is not handled here. Otherwise the return value is the id of the
+handler that matches the exception.
+\item[handler function:] This function handles the exception. 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.
+\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
+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
+nested functions and all other functions besides @__cfaehm_try_terminate@ in
+\CFA use the GCC personality function and the @-fexceptions@ flag to generate
+the LSDA. This allows destructors to be implemented with the cleanup attribute.
 \section{Resumption}
 % The stack-local data, the linked list of nodes.
+Resumption uses a list of nodes for its stack traversal. The head of the list
+is stored in the exception context. The nodes in the list just have a pointer
+Resumption simple to implement because there is no stack unwinding. The
+resumption raise uses a list of nodes for its stack traversal. The head of the
+list is stored in the exception context. The nodes in the list have a pointer
 to the next node and a pointer to the handler function.
+The on a resumption throw the this list is traversed. At each node the
 handler function is called and is passed the exception by pointer. It returns
 true if the exception was handled and false otherwise.
 The handler function does both the matching and catching. It tries each
+the condition of @catchResume@ in order, top-to-bottom and until it
 finds a handler that matches. If no handler matches then the function returns
 false. Otherwise the matching handler is run, if it completes successfully
+the function returns true. Rethrows, through the @throwResume;@
 statement, cause the function to return true.
+A resumption raise traverses this list. At each node the handler function is
+called, passing the exception by pointer. It returns true if the exception is
+handled and false otherwise.
+The handler function does both the matching and handling. It computes the
+condition of each @catchResume@ in top-to-bottom order, until it finds a
+handler that matches. If no handler matches then the function returns
+false. Otherwise the matching handler is run; if it completes successfully, the
+function returns true. Reresume, through the @throwResume;@ statement, cause
+the function to return true.
 % Recursive Resumption Stuff:
+Blocking out part of the stack 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 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 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 the
+other handler checked up to this point will not be checked again.
+Search skipping \see{\VPageref{p:searchskip}}, 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
+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
+the other handler checked up to this point are not checked again.
 This structure also supports new handler added while the resumption is being
 handled. These are added to the front of the list, pointing back along the
+stack -- the first one will point over all the checked handlers -- and the
+ordering is maintained.
+\subsection{Libunwind Compatibility}
+Resumption does not use libunwind for two simple reasons. The first is that
+it does not have to unwind anything so would never need to use the clean-up
+phase. Still the search phase could be used to make it free to enter or exit
+a try statement with resumption handlers in the same way termination handlers
+are for the same trade off in the cost of the throw. This is where the second
+reason comes in, there is no way to return from a search without installing
+a handler or raising an error.
+Although work arounds could be created none seemed to be worth it for the
+prototype. This implementation has no difference in behaviour and is much
+simpler.
+stack -- the first one points over all the checked handlers -- and the ordering
+is maintained.
+\label{p:zero-cost}
+Note, 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
+unwinding and cleanup provided by libunwind, it could use the search phase to
+providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way
+to return from a libunwind search without installing a handler or raising an
+error.  Although workarounds might be possible, they are beyond the scope of
+this thesis. The current resumption implementation has simplicity in its
+favour.
 % Seriously, just compare the size of the two chapters and then consider
 % that unwind is required knowledge for that chapter.
 …
 \section{Finally}
 % Uses destructors and GCC nested functions.
+Finally clauses are a simple decomposition to some of the existing features.
+The code in the block is placed into a GCC nested function with a unique name,
+no arguments or return values. This nested function is then set as the
+clean-up function of an empty object that is declared at the beginning of a
+block placed around the contexts of the try statement.
+Finally clauses 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 the
 block. When they are complete control exits the block and the empty object
 is cleaned up, which runs the function that contains the finally code.
+block. At completion, control exits the block and the empty object is cleaned
+up, which runs the function that contains the finally code.
 \section{Cancellation}
 …
 Cancellation also uses libunwind to do its stack traversal and unwinding,
 however it uses a different primary function @_Unwind_ForcedUnwind@.
 Details of its interface can be found in the unwind section.
 The first step of cancellation is to find the stack was cancelled and which
 type of stack it is. Luckily the threads library stores the main thread
 pointer and the current thread pointer and every thread stores a pointer to
+however it uses a different primary function @_Unwind_ForcedUnwind@.  Details
+of its interface can be found in the \VRef{s:ForcedUnwind}.
+The first step of cancellation is to find the cancelled stack and its type:
+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.
+So if the the current thread's main and current coroutine do not match, it is
+a coroutine cancellation. Otherwise if the main and current thread do not
+match, it is a thread cancellation. Otherwise it is a main thread
+cancellation.
+However if the threading library is not linked then execution must be on the
+main stack as that is the only one that exists. So the entire check is skipped
+using the linker and weak symbols. Instead the main thread cancellation is
+unconditionally preformed.
+Regardless of how they are choosen afterwords the stop function and the stop
+parameter are passed to the forced unwind functon. The general pattern of all
+three stop functions is the same, they continue unwinding until the end of
+stack when they do there primary work.
+Main stack cancellation it is very simple. The ``transfer" is just an abort,
+the program stops executing.
+The coroutine cancellation stores the exception on the coroutine and then
+does a coroutine context switch. The rest is handled inside resume. Every time
+control returns from a resumed thread there is a check to see if it is
+cancelled. If it is the exception is retrieved and the CoroutineCancelled
+exception is constructed and loaded. It is then thrown as a regular exception
+with the default handler coming from the context of the resumption call.
+The thread cancellation stores the exception on the thread's main stack and
+then returns to the scheduler. The rest is handled by the joiner. The wait
+for the joined thread to finish works the same but after that it checks
+to see if there was a cancellation. If there was the exception is retrieved
+and the ThreadCancelled exception is constructed. The default handler is
+passed in as a function pointer. If it is null (as it is for the
+auto-generated joins on destructor call) it a default is used that simply
+calls abort; which gives the required handling on implicate join.
+The first check is if the current thread's main and current coroutine do not
+match, implying a coroutine cancellation; otherwise, it is a thread
+cancellation. Otherwise it is a main thread cancellation. \PAB{Previous
+sentence does not make sense.}
+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
+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 when they
+do there primary work.
+For main stack cancellation, the transfer is just a program abort.
+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
+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.
+For thread cancellation, the exception is stored on the thread's main stack and
+then context switched to the scheduler. The rest is handled by the thread
+joiner. When the join is complete, the joiner checks if the joined thread is
+cancelled. If cancelled, the exception is retrieved and the joined thread, and
+a @ThreadCancelled@ exception is constructed and loaded with the cancelled
+exception. The default handler is passed in as a function pointer. If it is
+null (as it is for the auto-generated joins on destructor call), the default is
+used, which is a program abort.
+%; which gives the required handling on implicate join.

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 7eb6eb5 for doc/theses/andrew_beach_MMath/implement.tex

Legend:

doc/theses/andrew_beach_MMath/implement.tex

Download in other formats: