Index: doc/theses/andrew_beach_MMath/implement.tex =================================================================== --- doc/theses/andrew_beach_MMath/implement.tex (revision 1830a8657cb302a89a7ca045bee06baa48b18101) +++ doc/theses/andrew_beach_MMath/implement.tex (revision 830299f580963f7ae015873072bb04ec2fa976cd) @@ -13,17 +13,58 @@ library. +\subsection{Virtual Type} +Virtual types only have one change to their structure, the addition of a +pointer to the virtual table. This is always the first field so that +if it is cast to a supertype the field's location is still known. + +This field is set as part of all new generated constructors. +\todo{They only come as part exceptions and don't work.} +After the object is created the field is constant. + +However it can be read from, internally it is just a regular field called +@virtual_table@. Dereferencing it gives the virtual table and access to the +type's virtual members. + \subsection{Virtual Table} +Every time a virtual type is defined the new virtual table type must also be +defined. + +The unique instance is important because the address of the virtual table +instance is used as the identifier for the virtual type. So a pointer to the +virtual table and the ID for the virtual type are interchangable. +\todo{Unique instances might be going so we will have to talk about the new +system instead.} + +The first step in putting it all together is to create the virtual table type. +The virtual table type is just a structure and can be described in terms of +its fields. The first field is always the parent type ID (or a pointer to +the parent virtual table) or 0 (the null pointer). +Next are other fields on the parent virtual table are repeated. +Finally are the fields used to store any new virtual members of the new +The virtual type + 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 +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 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 +introduces. Parent fields are duplicated so they can be changed (all virtual +members are overridable), 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. + +% Simple ascii diragram: +\begin{verbatim} +parent_pointer \ +parent_field0 | +... | Same layout as parent. +parent_fieldN / +child_field0 +... +child_fieldN +\end{verbatim} +\todo{Refine the diagram} % For each virtual type, a virtual table is constructed. This is both a new type @@ -34,5 +75,5 @@ 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. +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. @@ -67,5 +108,5 @@ \begin{sloppypar} Coroutines and threads need instances of @CoroutineCancelled@ and -@ThreadCancelled@ respectively to use all of their functionality. When a new +@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 @@ -80,29 +121,30 @@ The function is \begin{cfa} -void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent, +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.} - +and it is implemented in the standard library. The structure reperents the +head of a vtable which is the pointer to the parent virtual table. The +@parent@ points directly at the parent type virtual table while the @child@ +points at the object of the (possibe) child type. + +In terms of the virtual cast expression, @parent@ comes from looking up the +type being cast to and @child@ is the result of the expression being cast. +Because the complier outputs C code, some type C type casts are also used. +The last bit of glue is an map that saves every virtual type the compiler +sees. This is used to check the type used in a virtual cast is a virtual +type and to get its virtual table. +(It also checks for conflicting definitions.) + +Inside the function it is a simple conditional. If the type repersented by +@parent@ is or is an ancestor of the type repersented by @*child@ (it +requires one more level of derefence to pass through the object) then @child@ +is returned, otherwise the null pointer is returned. + +The check itself is preformed is a simple linear search. If the child +virtual table or any of its ancestors (which are retreved through the first +field of every virtual table) are the same as the parent virtual table then +the cast succeeds. \section{Exceptions} @@ -121,5 +163,5 @@ 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 +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 @@ -179,7 +221,7 @@ 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 +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 +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 @@ -196,21 +238,25 @@ 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 +attaches its personality function. However, this +flag only handles the cleanup attribute: +\todo{Peter: What is attached? Andrew: It uses the .cfi\_personality directive +and that's all I know.} \begin{cfa} void clean_up( int * var ) { ... } -int avar __attribute__(( __cleanup(clean_up) )); +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. +which is used on a variable and specifies a function, in this case @clean_up@, +run when the variable goes out of scope. +The function is passed a pointer to the object being removed from the stack +so it can be used to mimic destructors. +However, this feature cannot be used to mimic @try@ statements as it cannot +control the unwinding. \subsection{Personality Functions} -Personality functions have a complex interface specified by libunwind. This +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. +A personality function can preform different actions depending on how it is +called. \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) ( @@ -225,5 +271,5 @@ \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 +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@. @@ -296,5 +342,5 @@ \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 +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 @@ -318,5 +364,5 @@ \begin{sloppypar} -Its arguments are the same as the paired personality function. The actions +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 @@ -343,13 +389,9 @@ 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. +The sequential @this_exception_context@ returns a hard-coded pointer to the +global execption context. +The concurrent version adds the exception context to the data stored at the +base of each stack. When @this_exception_context@ is called it retrieves the +active stack and returns the address of the context saved there. \section{Termination} @@ -369,6 +411,16 @@ 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 +[Quick ASCII diagram to get started.] +\begin{verbatim} +Fixed Header | _Unwind_Exception <- pointer target + | + | Cforall storage + | +Variable Body | the exception <- fixed offset + V ... +\end{verbatim} + +Exceptions are stored in variable-sized blocks. +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 @@ -388,5 +440,6 @@ 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. +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. \subsection{Try Statements and Catch Clauses} @@ -399,15 +452,12 @@ 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.} +calls them. +Because this function is known and fixed (and not an arbitrary function that +happens to contain a try statement) this means the LSDA can be generated ahead +of time. + +Both the LSDA and the personality function are set ahead of time using +embedded assembly. This is handcrafted using C @asm@ statements and contains +enough information for the single try statement the function repersents. The three functions passed to try terminate are: @@ -419,5 +469,5 @@ \item[match function:] This function is called during the search phase and -decides if a catch clause matches the termination exception. It is constructed +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 @@ -428,5 +478,5 @@ \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 +after the cleanup phase. It is constructed by stitching together the bodies of each handler and dispatches to the selected handler. \end{description} @@ -434,5 +484,5 @@ 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 +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 @@ -455,6 +505,6 @@ 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. +function returns true. Rethrowing, through the @throwResume;@ statement, +causes the function to return true. % Recursive Resumption Stuff: @@ -482,5 +532,5 @@ 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 +error. Although workarounds might be possible, they are beyond the scope of this thesis. The current resumption implementation has simplicity in its favour. @@ -503,5 +553,5 @@ Cancellation also uses libunwind to do its stack traversal and unwinding, -however it uses a different primary function @_Unwind_ForcedUnwind@. Details +however it uses a different primary function @_Unwind_ForcedUnwind@. Details of its interface can be found in the \VRef{s:ForcedUnwind}. @@ -511,8 +561,9 @@ its main coroutine and the coroutine it is currently executing. -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.} +So if the active thread's main and current coroutine are the same. If they +are then the current stack is a thread stack, otherwise it is a coroutine +stack. If it is a thread stack then an equality check with the stored main +thread pointer and current thread pointer is enough to tell if the current +thread is the main thread or not. However, if the threading library is not linked, the sequential execution is on