Changeset 7eb6eb5 for doc/theses/andrew_beach_MMath/implement.tex
- Timestamp:
- Jan 29, 2021, 8:23:52 AM (2 years ago)
- Branches:
- arm-eh, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 5669d0b
- Parents:
- 4dcd5ea
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/implement.tex
r4dcd5ea r7eb6eb5 2 2 % Goes over how all the features are implemented. 3 3 4 The implementation work for this thesis covers two components: the virtual 5 system and exceptions. Each component is discussed in detail. 6 4 7 \section{Virtual System} 8 \label{s:VirtualSystem} 5 9 % Virtual table rules. Virtual tables, the pointer to them and the cast. 6 The \CFA virtual system only has one public facing feature: virtual casts. 7 However there is a lot of structure to support that and provide some other 8 features for the standard library. 9 10 All of this is accessed through a field inserted at the beginning of every 11 virtual type. Currently it is called @virtual_table@ but it is not 12 ment to be accessed by the user. This field is a pointer to the type's 13 virtual table instance. It is assigned once during the object's construction 14 and left alone after that. 15 16 \subsection{Virtual Table Construction} 17 For each virtual type a virtual table is constructed. This is both a new type 18 and an instance of that type. Other instances of the type could be created 19 but the system doesn't use them. So this section will go over the creation of 20 the type and the instance. 21 22 Creating the single instance is actually very important. The address of the 23 table acts as the unique identifier for the virtual type. Similarly the first 24 field in every virtual table is the parent's id; a pointer to the parent 25 virtual table instance. 26 27 The remaining fields contain the type's virtual members. First come the ones 28 present on the parent type, in the same order as they were the parent, and 29 then any that this type introduces. The types of the ones inherited from the 30 parent may have a slightly modified type, in that references to the 31 dispatched type are replaced with the current virtual type. These are always 32 taken by pointer or reference. 33 34 The structure itself is created where the virtual type is created. The name 35 of the type is created by mangling the name of the base type. The name of the 36 instance is also generated by name mangling. 37 38 The fields are initialized automatically. 10 While the \CFA virtual system currently has only one public feature, virtual 11 cast \see{\VPageref{p:VirtualCast}}, substantial structure is required to 12 support it, and provide features for exception handling and the standard 13 library. 14 15 \subsection{Virtual Table} 16 The virtual system is accessed through a private constant field inserted at the 17 beginning of every virtual type, called the virtual-table pointer. This field 18 points at a type's virtual table and is assigned during the object's 19 construction. The address of a virtual table acts as the unique identifier for 20 the virtual type, and the first field of a virtual table is a pointer to the 21 parent virtual-table or @0p@. The remaining fields are duplicated from the 22 parent tables in this type's inheritance chain, followed by any fields this type 23 introduces. Parent fields are duplicated so they can be changed (\CC 24 \lstinline[language=c++]|override|), so that references to the dispatched type 25 are replaced with the current virtual type. 26 \PAB{Can you create a simple diagram of the layout?} 27 % These are always taken by pointer or reference. 28 29 % For each virtual type, a virtual table is constructed. This is both a new type 30 % and an instance of that type. Other instances of the type could be created 31 % but the system doesn't use them. So this section will go over the creation of 32 % the type and the instance. 33 34 A virtual table is created when the virtual type is created. The name of the 35 type is created by mangling the name of the base type. The name of the instance 36 is also generated by name mangling. The fields are initialized automatically. 39 37 The parent field is initialized by getting the type of the parent field and 40 38 using that to calculate the mangled name of the parent's virtual table type. 41 39 There are two special fields that are included like normal fields but have 42 40 special initialization rules: the @size@ field is the type's size and is 43 initialized with a sizeof expression, the @align@ field is the type's 44 alignment and uses an alignof expression. The remaining fields are resolved 45 to a name matching the field's name and type using the normal visibility 46 and overload resolution rules of the type system. 47 48 These operations are split up into several groups depending on where they 49 take place which can vary for monomorphic and polymorphic types. The first 50 devision is between the declarations and the definitions. Declarations, such 51 as a function signature or a structure's name, must always be visible but may 52 be repeated so they go in headers. Definitions, such as function bodies and a 53 structure's layout, don't have to be visible on use but must occur exactly 54 once and go into source files. 55 41 initialized with a @sizeof@ expression, the @align@ field is the type's 42 alignment and uses an @alignof@ expression. The remaining fields are resolved 43 to a name matching the field's name and type using the normal visibility and 44 overload resolution rules of the type system. 45 46 These operations are split up into several groups depending on where they take 47 place which varies for monomorphic and polymorphic types. The first devision is 48 between the declarations and the definitions. Declarations, such as a function 49 signature or a aggregate's name, must always be visible but may be repeated in 50 the form of forward declarations in headers. Definitions, such as function 51 bodies and a aggregate's layout, can be separately compiled but must occur 52 exactly once in a source file. 53 54 \begin{sloppypar} 56 55 The declarations include the virtual type definition and forward declarations 57 56 of the virtual table instance, constructor, message function and 58 @get_exception_vtable@. The definition includes the storage and 59 initialization of the virtual table instance and the bodies of the three 60 functions. 57 @get_exception_vtable@. The definition includes the storage and initialization 58 of the virtual table instance and the bodies of the three functions. 59 \end{sloppypar} 61 60 62 61 Monomorphic instances put all of these two groups in one place each. 63 64 Polymorphic instances also split out the core declarations and definitions65 from the per-instance information. The virtual table type and most of the66 functions are polymorphic so they are all part of the core. The virtual table 67 instance and the @get_exception_vtable@ function. 68 62 Polymorphic instances also split out the core declarations and definitions from 63 the per-instance information. The virtual table type and most of the functions 64 are polymorphic so they are all part of the core. The virtual table instance 65 and the @get_exception_vtable@ function. 66 67 \begin{sloppypar} 69 68 Coroutines and threads need instances of @CoroutineCancelled@ and 70 @ThreadCancelled@ respectively to use all of their functionality. 71 When a new data type is declared with @coroutine@ or @thread@ 72 the forward declaration for the instance is created as well. The definition 73 of the virtual table is created at the definition of the main function. 69 @ThreadCancelled@ respectively to use all of their functionality. When a new 70 data type is declared with @coroutine@ or @thread@ the forward declaration for 71 the instance is created as well. The definition of the virtual table is created 72 at the definition of the main function. 73 \end{sloppypar} 74 74 75 75 \subsection{Virtual Cast} 76 Virtual casts are implemented as a function call that does the check and a 77 old C-style cast to do the type conversion. The C-cast is just to make sure 78 the generated code is correct so the rest of the section is about that 79 function. 80 81 The function is @__cfa__virtual_cast@ and it is implemented in the 82 standard library. It takes a pointer to the target type's virtual table and 83 the object pointer being cast. The function is very simple, getting the 84 object's virtual table pointer and then checking to see if it or any of 85 its ancestors, by using the parent pointers, are the same as the target type 86 virtual table pointer. It does this in a simple loop. 87 88 For the generated code a forward decaration of the virtual works as follows. 89 There is a forward declaration of @__cfa__virtual_cast@ in every cfa 90 file so it can just be used. The object argument is the expression being cast 91 so that is just placed in the argument list. 92 93 To build the target type parameter the compiler will create a mapping from 94 concrete type-name -- so for polymorphic types the parameters are filled in 95 -- to virtual table address. Every virtual table declaraction is added to the 96 this table; repeats are ignored unless they have conflicting definitions. 97 This does mean the declaractions have to be in scope, but they should usually 98 be introduced as part of the type definition. 76 Virtual casts are implemented as a function call that does the subtype check 77 and a C coercion-cast to do the type conversion. 78 % The C-cast is just to make sure the generated code is correct so the rest of 79 % the section is about that function. 80 The function is 81 \begin{cfa} 82 void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent, 83 struct __cfa__parent_vtable const * const * child ); 84 } 85 \end{cfa} 86 and it is implemented in the standard library. It takes a pointer to the target 87 type's virtual table and the object pointer being cast. The function performs a 88 linear search starting at the object's virtual-table and walking through the 89 the parent pointers, checking to if it or any of its ancestors are the same as 90 the target-type virtual table-pointer. 91 92 For the generated code, a forward declaration of the virtual works as follows. 93 There is a forward declaration of @__cfa__virtual_cast@ in every \CFA file so 94 it can just be used. The object argument is the expression being cast so that 95 is just placed in the argument list. 96 97 To build the target type parameter, the compiler creates a mapping from 98 concrete type-name -- so for polymorphic types the parameters are filled in -- 99 to virtual table address. Every virtual table declaration is added to the this 100 table; repeats are ignored unless they have conflicting definitions. Note, 101 these declarations do not have to be in scope, but they should usually be 102 introduced as part of the type definition. 103 104 \PAB{I do not understood all of \VRef{s:VirtualSystem}. I think you need to 105 write more to make it clear.} 106 99 107 100 108 \section{Exceptions} … … 106 114 % resumption doesn't as well. 107 115 108 Many modern languages work with an interal stack that function push and pop 109 their local data to. Stack unwinding removes large sections of the stack, 110 often across functions. 111 112 At a very basic level this can be done with @setjmp@ \& @longjmp@ 113 which simply move the top of the stack, discarding everything on the stack 114 above a certain point. However this ignores all the clean-up code that should 115 be run when certain sections of the stack are removed (for \CFA these are from 116 destructors and finally clauses) and also requires that the point to which the 117 stack is being unwound is known ahead of time. libunwind is used to address 118 both of these problems. 119 120 Libunwind, provided in @unwind.h@ on most platorms, is a C library 121 that provides \CPP style stack unwinding. Its operation is divided into two 122 phases. The search phase -- phase 1 -- is used to scan the stack and decide 123 where the unwinding will stop, this allows for a dynamic target. The clean-up 124 phase -- phase 2 -- does the actual unwinding and also runs any clean-up code 125 as it goes. 126 127 To use the libunwind each function must have a personality function and an 128 LSDA (Language Specific Data Area). Libunwind actually does very little, it 129 simply moves down the stack from function to function. Most of the actions are 130 implemented by the personality function which libunwind calls on every 131 function. Since this is shared across many functions or even every function in 132 a language it will need a bit more information. This is provided by the LSDA 133 which has the unique information for each function. 134 135 Theoretically the LSDA can contain anything but conventionally it is a table 136 with entries reperenting areas of the function and what has to be done there 137 during unwinding. These areas are described in terms of where the instruction 138 pointer is. If the current value of the instruction pointer is between two 139 values reperenting the beginning and end of a region then execution is 140 currently being executed. These are used to mark out try blocks and the 141 scopes of objects with destructors to run. 142 143 GCC will generate an LSDA and attach its personality function with the 144 @-fexceptions@ flag. However this only handles the cleanup attribute. 145 This attribute is used on a variable and specifies a function that should be 146 run when the variable goes out of scope. The function is passed a pointer to 147 the object as well so it can be used to mimic destructors. It however cannot 148 be used to mimic try statements. 149 150 \subsection{Implementing Personality Functions} 151 Personality functions have a complex interface specified by libunwind. 152 This section will cover some of the important parts of that interface. 153 154 \begin{lstlisting} 155 typedef _Unwind_Reason_Code (*_Unwind_Personality_Fn)( 156 int version, 157 _Unwind_Action action, 158 _Unwind_Exception_Class exception_class, 159 _Unwind_Exception * exception, 160 struct _Unwind_Context * context); 116 % Many modern languages work with an interal stack that function push and pop 117 % their local data to. Stack unwinding removes large sections of the stack, 118 % often across functions. 119 120 Stack unwinding is the process of removing stack frames (activations) from the 121 stack. On function entry and return, unwinding is handled directly by the code 122 embedded in the function. Usually, the stack-frame size is known statically 123 based on parameter and local variable declarations. For dynamically-sized 124 local variables, a runtime computation is necessary to know the frame 125 size. Finally, a function's frame-size may change during execution as local 126 variables (static or dynamic sized) go in and out of scope. 127 Allocating/deallocating stack space is usually an $O(1)$ operation achieved by 128 bumping the hardware stack-pointer up or down as needed. 129 130 Unwinding across multiple stack frames is more complex because individual stack 131 management code associated with each frame is bypassed. That is, the location 132 of a function's frame-management code is largely unknown and dispersed 133 throughout the function, hence the current frame size managed by that code is 134 also unknown. Hence, code unwinding across frames does not have direct 135 knowledge about what is on the stack, and hence, how much of the stack needs to 136 be removed. 137 138 % At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply 139 % move the top of the stack, discarding everything on the stack above a certain 140 % point. However this ignores all the cleanup code that should be run when 141 % certain sections of the stack are removed (for \CFA these are from destructors 142 % and finally clauses) and also requires that the point to which the stack is 143 % being unwound is known ahead of time. libunwind is used to address both of 144 % these problems. 145 146 The traditional unwinding mechanism for C is implemented by saving a snap-shot 147 of a function's state with @setjmp@ and restoring that snap-shot with 148 @longjmp@. This approach bypasses the need to know stack details by simply 149 reseting to a snap-shot of an arbitrary but existing function frame on the 150 stack. It is up to the programmer to ensure the snap-shot is valid when it is 151 reset, making this unwinding approach fragile with potential errors that are 152 difficult to debug because the stack becomes corrupted. 153 154 However, many languages define cleanup actions that must be taken when objects 155 are deallocated from the stack or blocks end, such as running a variable's 156 destructor or a @try@ statement's @finally@ clause. Handling these mechanisms 157 requires walking the stack and checking each stack frame for these potential 158 actions. 159 160 For exceptions, it must be possible to walk the stack frames in search of @try@ 161 statements to match and execute a handler. For termination exceptions, it must 162 also be possible to unwind all stack frames from the throw to the matching 163 catch, and each of these frames must be checked for cleanup actions. Stack 164 walking is where most of the complexity and expense of exception handling 165 appears. 166 167 One of the most popular tools for stack management is libunwind, a low-level 168 library that provides tools for stack walking, handler execution, and 169 unwinding. What follows is an overview of all the relevant features of 170 libunwind needed for this work, and how \CFA uses them to implement exception 171 handling. 172 173 \subsection{libunwind Usage} 174 Libunwind, accessed through @unwind.h@ on most platforms, is a C library that 175 provides \CC-style stack-unwinding. Its operation is divided into two phases: 176 search and cleanup. The dynamic target search -- phase 1 -- is used to scan the 177 stack and decide where unwinding should stop (but no unwinding occurs). The 178 cleanup -- phase 2 -- does the unwinding and also runs any cleanup code. 179 180 To use libunwind, each function must have a personality function and a Language 181 Specific Data Area (LSDA). The LSDA has the unique information for each 182 function to tell the personality function where a function is executing, its 183 current stack frame, and what handlers should be checked. Theoretically, the 184 LSDA can contain any information but conventionally it is a table with entries 185 representing regions of the function and what has to be done there during 186 unwinding. These regions are bracketed by the instruction pointer. If the 187 instruction pointer is within a region's start/end, then execution is currently 188 executing in that region. Regions are used to mark out the scopes of objects 189 with destructors and try blocks. 190 191 % Libunwind actually does very little, it simply moves down the stack from 192 % function to function. Most of the actions are implemented by the personality 193 % function which libunwind calls on every function. Since this is shared across 194 % many functions or even every function in a language it will need a bit more 195 % information. 196 197 The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and 198 attaches its personality function. \PAB{to what is it attached?} However, this 199 flag only handles the cleanup attribute 200 \begin{cfa} 201 void clean_up( int * var ) { ... } 202 int avar __attribute__(( __cleanup(clean_up) )); 203 \end{cfa} 204 which is used on a variable and specifies a function, \eg @clean_up@, run when 205 the variable goes out of scope. The function is passed a pointer to the object 206 so it can be used to mimic destructors. However, this feature cannot be used to 207 mimic @try@ statements. 208 209 \subsection{Personality Functions} 210 Personality functions have a complex interface specified by libunwind. This 211 section covers some of the important parts of the interface. 212 213 A personality function performs four tasks, although not all have to be 214 present. 215 \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] 216 typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) ( 217 _Unwind_Action @action@, 218 _Unwind_Exception_Class @exception_class@, 219 _Unwind_Exception * @exception@, 220 struct _Unwind_Context * @context@ 221 ); 161 222 \end{lstlisting} 162 163 The return value, the reason code, is an enumeration of possible messages 223 The @action@ argument is a bitmask of possible actions: 224 \begin{enumerate} 225 \item 226 @_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function 227 to check for handlers. If there is a handler in a stack frame, as defined by 228 the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise 229 it return @_URC_CONTINUE_UNWIND@. 230 231 \item 232 @_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is 233 unwound and all cleanup code is run. The personality function does whatever 234 cleanup the language defines (such as running destructors/finalizers) and then 235 generally returns @_URC_CONTINUE_UNWIND@. 236 237 \item 238 \begin{sloppypar} 239 @_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a 240 handler. The personality function must prepare to return to normal code 241 execution and return @_URC_INSTALL_CONTEXT@. 242 \end{sloppypar} 243 244 \item 245 @_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs 246 the cleanup phase and uses a different means to decide when to stop 247 \see{\VRef{s:ForcedUnwind}}. 248 \end{enumerate} 249 250 The @exception_class@ argument is a copy of the 251 \lstinline[language=C]|exception|'s @exception_class@ field. 252 253 The \lstinline[language=C]|exception| argument is a pointer to the user 254 provided storage object. It has two public fields, the exception class, which 255 is actually just a number, identifying the exception handling mechanism that 256 created it, and the cleanup function. The cleanup function is called if 257 required by the exception. 258 259 The @context@ argument is a pointer to an opaque type passed to helper 260 functions called inside the personality function. 261 262 The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages 164 263 that can be passed several places in libunwind. It includes a number of 165 264 messages for special cases (some of which should never be used by the … … 167 266 personality function should always return @_URC_CONTINUE_UNWIND@. 168 267 169 The @version@ argument is the verson of the implementation that is170 calling the personality function. At this point it appears to always be 1 and171 it will likely stay that way until a new version of the API is updated.172 173 The @action@ argument is set of flags that tell the personality174 function when it is being called and what it must do on this invocation.175 The flags are as follows:176 \begin{itemize}177 \item@_UA_SEARCH_PHASE@: This flag is set whenever the personality178 function is called during the search phase. The personality function should179 decide if unwinding will stop in this function or not. If it does then the180 personality function should return @_URC_HANDLER_FOUND@.181 \item@_UA_CLEANUP_PHASE@: This flag is set whenever the personality182 function is called during the cleanup phase. If no other flags are set this183 means the entire frame will be unwound and all cleanup code should be run.184 \item@_UA_HANDLER_FRAME@: This flag is set during the cleanup phase185 on the function frame that found the handler. The personality function must186 prepare to return to normal code execution and return187 @_URC_INSTALL_CONTEXT@.188 \item@_UA_FORCE_UNWIND@: This flag is set if the personality function189 is called through a forced unwind call. Forced unwind only performs the190 cleanup phase and uses a different means to decide when to stop. See its191 section below.192 \end{itemize}193 194 The @exception_class@ argument is a copy of the @exception@'s195 @exception_class@ field.196 197 The @exception@ argument is a pointer to the user provided storage198 object. It has two public fields, the exception class which is actually just199 a number that identifies the exception handling mechanism that created it and200 the other is the clean-up function. The clean-up function is called if the201 exception needs to202 203 The @context@ argument is a pointer to an opaque type. This is passed204 to the many helper functions that can be called inside the personality205 function.206 207 268 \subsection{Raise Exception} 208 This could be considered the central function of libunwind. It preforms the 209 two staged unwinding the library is built around and most of the rest of the 210 interface of libunwind is here to support it. It's signature is as follows: 211 212 \begin{lstlisting} 269 Raising an exception is the central function of libunwind and it performs a 270 two-staged unwinding. 271 \begin{cfa} 213 272 _Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *); 273 \end{cfa} 274 First, the function begins the search phase, calling the personality function 275 of the most recent stack frame. It continues to call personality functions 276 traversing the stack from newest to oldest until a function finds a handler or 277 the end of the stack is reached. In the latter case, raise exception returns 278 @_URC_END_OF_STACK@. 279 280 Second, when a handler is matched, raise exception continues onto the cleanup phase. 281 Once again, it calls the personality functions of each stack frame from newest 282 to oldest. This pass stops at the stack frame containing the matching handler. 283 If that personality function has not install a handler, it is an error. 284 285 If an error is encountered, raise exception returns either 286 @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the 287 error occurred. 288 289 \subsection{Forced Unwind} 290 \label{s:ForcedUnwind} 291 Forced Unwind is the other central function in libunwind. 292 \begin{cfa} 293 _Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *, 294 _Unwind_Stop_Fn, void *); 295 \end{cfa} 296 It also unwinds the stack but it does not use the search phase. Instead another 297 function, the stop function, is used to stop searching. The exception is the 298 same as the one passed to raise exception. The extra arguments are the stop 299 function and the stop parameter. The stop function has a similar interface as a 300 personality function, except it is also passed the stop parameter. 301 \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] 302 typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)( 303 _Unwind_Action @action@, 304 _Unwind_Exception_Class @exception_class@, 305 _Unwind_Exception * @exception@, 306 struct _Unwind_Context * @context@, 307 void * @stop_parameter@); 214 308 \end{lstlisting} 215 309 216 When called the function begins the search phase, calling the personality217 function of the most recent stack frame. It will continue to call personality218 functions traversing the stack new-to-old until a function finds a handler or219 the end of the stack is reached. In the latter case raise exception will220 return with @_URC_END_OF_STACK@.221 222 Once a handler has been found raise exception continues onto the the cleanup223 phase. Once again it will call the personality functins of each stack frame224 from newest to oldest. This pass will stop at the stack frame that found the225 handler last time, if that personality function does not install the handler226 it is an error.227 228 If an error is encountered raise exception will return either229 @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending230 on when the error occured.231 232 \subsection{Forced Unwind}233 This is the second big function in libunwind. It also unwinds a stack but it234 does not use the search phase. Instead another function, the stop function,235 is used to decide when to stop.236 237 \begin{lstlisting}238 _Unwind_Reason_Code _Unwind_ForcedUnwind(239 _Unwind_Exception *, _Unwind_Stop_Fn, void *);240 \end{lstlisting}241 242 The exception is the same as the one passed to raise exception. The extra243 arguments are the stop function and the stop parameter. The stop function has244 a similar interface as a personality function, except it is also passed the245 stop parameter.246 247 \begin{lstlisting}248 typedef _Unwind_Reason_Code (*_Unwind_Stop_Fn)(249 int version,250 _Unwind_Action action,251 _Unwind_Exception_Class exception_class,252 _Unwind_Exception * exception,253 struct _Unwind_Context * context,254 void * stop_parameter);255 \end{lstlisting}256 257 310 The stop function is called at every stack frame before the personality 258 function is called and then once more once after all frames of the stack have 259 been unwound. 260 261 Each time it is called the stop function should return @_URC_NO_REASON@ 262 or transfer control directly to other code outside of libunwind. The 263 framework does not provide any assistance here. 264 265 Its arguments are the same as the paired personality function. 266 The actions @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always 267 set when it is called. By the official standard that is all but both GCC and 268 Clang add an extra action on the last call at the end of the stack: 269 @_UA_END_OF_STACK@. 311 function is called and then once more after all frames of the stack are 312 unwound. 313 314 Each time it is called, the stop function should return @_URC_NO_REASON@ or 315 transfer control directly to other code outside of libunwind. The framework 316 does not provide any assistance here. 317 318 \begin{sloppypar} 319 Its arguments are the same as the paired personality function. The actions 320 @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is 321 called. Beyond the libunwind standard, both GCC and Clang add an extra action 322 on the last call at the end of the stack: @_UA_END_OF_STACK@. 323 \end{sloppypar} 270 324 271 325 \section{Exception Context} 272 326 % Should I have another independent section? 273 327 % There are only two things in it, top_resume and current_exception. How it is 274 % stored changes depending on wheither or not the thread-library is linked. 275 276 The exception context is a piece of global storage used to maintain data 277 across different exception operations and to communicate between different 278 components. 279 280 Each stack has its own exception context. In a purely sequental program, using 281 only core Cforall, there is only one stack and the context is global. However 282 if the library @libcfathread@ is linked then there can be multiple 283 stacks so they will each need their own. 284 285 To handle this code always gets the exception context from the function 286 @this_exception_context@. The main exception handling code is in 287 @libcfa@ and that library also defines the function as a weak symbol 288 so it acts as a default. Meanwhile in @libcfathread@ the function is 289 defined as a strong symbol that replaces it when the libraries are linked 290 together. 291 292 The version of the function defined in @libcfa@ is very simple. It 293 returns a pointer to a global static variable. With only one stack this 294 global instance is associated with the only stack. 295 296 The version of the function defined in @libcfathread@ has to handle 297 more as there are multiple stacks. The exception context is included as 298 part of the per-stack data stored as part of coroutines. In the cold data 299 section, stored at the base of each stack, is the exception context for that 300 stack. The @this_exception_context@ uses the concurrency library to get 301 the current coroutine and through it the cold data section and the exception 302 context. 328 % stored changes depending on whether or not the thread-library is linked. 329 330 The exception context is global storage used to maintain data across different 331 exception operations and to communicate among different components. 332 333 Each stack must have its own exception context. In a sequential \CFA program, 334 there is only one stack with a single global exception-context. However, when 335 the library @libcfathread@ is linked, there are multiple stacks where each 336 needs its own exception context. 337 338 General access to the exception context is provided by function 339 @this_exception_context@. For sequential execution, this function is defined as 340 a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is 341 concurrent, it links with @libcfathread@, where this function is defined with a 342 strong symbol replacing the sequential version. 343 344 % The version of the function defined in @libcfa@ is very simple. It returns a 345 % pointer to a global static variable. With only one stack this global instance 346 % is associated with the only stack. 347 348 For coroutines, @this_exception_context@ accesses the exception context stored 349 at the base of the stack. For threads, @this_exception_context@ uses the 350 concurrency library to access the current stack of the thread or coroutine 351 being executed by the thread, and then accesses the exception context stored at 352 the base of this stack. 303 353 304 354 \section{Termination} … … 306 356 % catches. Talk about GCC nested functions. 307 357 308 Termination exceptions use libunwind quite heavily because it matches the309 intended use from \CPP exceptions very closely. The main complication is that 310 since the \CFA compiler works by translating to C code it cannot generate the 311 assembly toform the LSDA for try blocks or destructors.358 Termination exceptions use libunwind heavily because it matches the intended 359 use from \CC exceptions closely. The main complication for \CFA is that the 360 compiler generates C code, making it very difficult to generate the assembly to 361 form the LSDA for try blocks or destructors. 312 362 313 363 \subsection{Memory Management} 314 The first step of termination is to copy the exception into memory managed by315 the exception system. Currently the system just uses malloc, without reserved 316 memory or and ``small allocation" optimizations. The exception handling 317 me chanism manages memory for the exception as well as memory for libunwind318 and the system's ownper-exception storage.319 320 Exceptions are stored in variable sized block. The first component is a fixed321 sized data structure that contains the information for libunwind andthe322 exception system. The second component is a blob of memory that is big enough 323 to store the exception. Macros with pointer arthritic and type cast are 324 used to move between the components or go from the embedded364 The first step of a termination raise is to copy the exception into memory 365 managed by the exception system. Currently, the system uses @malloc@, rather 366 than reserved memory or the stack top. The exception handling mechanism manages 367 memory for the exception as well as memory for libunwind and the system's own 368 per-exception storage. 369 370 Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout 371 figure.} The first component is a fixed sized data structure that contains the 372 information for libunwind and the exception system. The second component is an 373 area of memory big enough to store the exception. Macros with pointer arthritic 374 and type cast are used to move between the components or go from the embedded 325 375 @_Unwind_Exception@ to the entire node. 326 376 327 All of these nodes are strung together in a linked list. One linked list per 328 stack, with the head stored in the exception context. Within each linked list 329 the most recently thrown exception is at the head and the older exceptions 330 are further down the list. This list format allows exceptions to be thrown 331 while a different exception is being handled. Only the exception at the head 332 of the list is currently being handled, the other will wait for the 333 exceptions before them to be removed. 334 335 The virtual members in the exception's virtual table. The size of the 336 exception, the copy function and the free function are all in the virtual 337 table so they are decided per-exception type. The size and copy function are 338 used right away when the exception is copied in to managed memory. After the 339 exception is handled the free function is used to clean up the exception and 340 then the entire node is passed to free. 341 342 \subsection{Try Statements \& Catch Clauses} 343 The try statements with termination handlers have a pretty complex conversion 344 to compensate for the lack of assembly generation. Libunwind requires an LSDA 345 (Language Specific Data Area) and personality function for a function to 346 unwind across it. The LSDA in particular is hard to generate at the level of 347 C which is what the \CFA compiler outputs so a work-around is used. 348 349 This work around is a function called @__cfaehm_try_terminate@ in the 350 standard library. The contents of a try block and the termination handlers 351 are converted into functions. These are then passed to the try terminate 352 function and it calls them. This puts the try statements in their own 353 functions so that no function has to deal with both termination handlers and 354 destructors. 355 356 This function has some custom embedded assembly that defines its personality 357 function and LSDA. This is hand coded in C which is why there is only one 358 version of it, the compiler has no capability to generate it. The personality 359 function is structured so that it may be expanded, but really it only handles 360 this one function. Notably it does not handle any destructors so the function 361 is constructed so that it does need to run it. 377 All of these nodes are linked together in a list, one list per stack, with the 378 list head stored in the exception context. Within each linked list, the most 379 recently thrown exception is at the head followed by older thrown 380 exceptions. This format allows exceptions to be thrown, while a different 381 exception is being handled. The exception at the head of the list is currently 382 being handled, while other exceptions wait for the exceptions before them to be 383 removed. 384 385 The virtual members in the exception's virtual table provide the size of the 386 exception, the copy function, and the free function, so they are specific to an 387 exception type. The size and copy function are used immediately to copy an 388 exception into managed memory. After the exception is handled the free function 389 is used to clean up the exception and then the entire node is passed to free. 390 391 \subsection{Try Statements and Catch Clauses} 392 The try statement with termination handlers is complex because it must 393 compensate for the lack of assembly-code generated from \CFA. Libunwind 394 requires an LSDA and personality function for control to unwind across a 395 function. The LSDA in particular is hard to mimic in generated C code. 396 397 The workaround is a function called @__cfaehm_try_terminate@ in the standard 398 library. The contents of a try block and the termination handlers are converted 399 into functions. These are then passed to the try terminate function and it 400 calls them. This approach puts a try statement in its own functions so that no 401 function has to deal with both termination handlers and destructors. \PAB{I do 402 not understand the previous sentence.} 403 404 This function has some custom embedded assembly that defines \emph{its} 405 personality function and LSDA. The assembly is created with handcrafted C @asm@ 406 statements, which is why there is only one version of it. The personality 407 function is structured so that it can be expanded, but currently it only 408 handles this one function. Notably, it does not handle any destructors so the 409 function is constructed so that it does need to run it. \PAB{I do not 410 understand the previous sentence.} 362 411 363 412 The three functions passed to try terminate are: 364 \begin{ itemize}365 \item The try function: This function is the try block, all the code inside366 t he try block is placed inside the try function. It takes no parameters and367 has no return value. This function is called during regular execution to run 368 the tryblock.369 \item The match function: This function decides if this try statement should 370 handle any given termination exception. It takes a pointer to the exception 371 and returns 0 if the exception is not handled here. Otherwise the return value 372 is the id of the handler that should handle the exception. It is called 373 during the search phase. 374 It is constructed from the conditional part of each handler. It runs each 375 check in turn, first checking to see if the object 376 \item The catch function: This function handles the exception. It takes a 377 pointer to the exception and the handler's id and returns nothing. It is 378 called after the clean-up phase. 379 It is constructed by stitching together the bodies of each handler 380 \end{itemize} 381 All three are created with GCC nested functions. GCC nested functions can be 382 used to create closures, functions that can refer to the state of other 383 functions on the stack. This allows the functions to refer to the main 384 function and all the variables in scope. 385 386 These nested functions and all other functions besides 387 @__cfaehm_try_terminate@ in \CFA use the GCC personality function and 388 the @-fexceptions@ flag to generate the LSDA. This allows destructors 389 t o be implemented with the cleanup attribute.413 \begin{description} 414 \item[try function:] This function is the try block, all the code inside the 415 try block is placed inside the try function. It takes no parameters and has no 416 return value. This function is called during regular execution to run the try 417 block. 418 419 \item[match function:] This function is called during the search phase and 420 decides if a catch clause matches the termination exception. It is constructed 421 from the conditional part of each handler and runs each check, top to bottom, 422 in turn, first checking to see if the exception type matches and then if the 423 condition is true. It takes a pointer to the exception and returns 0 if the 424 exception is not handled here. Otherwise the return value is the id of the 425 handler that matches the exception. 426 427 \item[handler function:] This function handles the exception. It takes a 428 pointer to the exception and the handler's id and returns nothing. It is called 429 after the cleanup phase. It is constructed by stitching together the bodies of 430 each handler and dispatches to the selected handler. 431 \end{description} 432 All three functions are created with GCC nested functions. GCC nested functions 433 can be used to create closures, functions that can refer to the state of other 434 functions on the stack. This approach allows the functions to refer to all the 435 variables in scope for the function containing the @try@ statement. These 436 nested functions and all other functions besides @__cfaehm_try_terminate@ in 437 \CFA use the GCC personality function and the @-fexceptions@ flag to generate 438 the LSDA. This allows destructors to be implemented with the cleanup attribute. 390 439 391 440 \section{Resumption} 392 441 % The stack-local data, the linked list of nodes. 393 442 394 Resumption uses a list of nodes for its stack traversal. The head of the list 395 is stored in the exception context. The nodes in the list just have a pointer 443 Resumption simple to implement because there is no stack unwinding. The 444 resumption raise uses a list of nodes for its stack traversal. The head of the 445 list is stored in the exception context. The nodes in the list have a pointer 396 446 to the next node and a pointer to the handler function. 397 447 398 The on a resumption throw the this list is traversed. At each node the 399 handler function is called and is passed the exception by pointer. It returns400 true if the exception washandled and false otherwise.401 402 The handler function does both the matching and catching. It tries each403 the condition of @catchResume@ in order, top-to-bottom and until it 404 finds ahandler that matches. If no handler matches then the function returns405 false. Otherwise the matching handler is run , if it completes successfully406 the function returns true. Rethrows, through the @throwResume;@ 407 statement, causethe function to return true.448 A resumption raise traverses this list. At each node the handler function is 449 called, passing the exception by pointer. It returns true if the exception is 450 handled and false otherwise. 451 452 The handler function does both the matching and handling. It computes the 453 condition of each @catchResume@ in top-to-bottom order, until it finds a 454 handler that matches. If no handler matches then the function returns 455 false. Otherwise the matching handler is run; if it completes successfully, the 456 function returns true. Reresume, through the @throwResume;@ statement, cause 457 the function to return true. 408 458 409 459 % Recursive Resumption Stuff: 410 Blocking out part of the stack is accomplished by updating the front of the 411 list as the search continues. Before the handler at a node is called the head 412 of the list is updated to the next node of the current node. After the search 413 is complete, successful or not, the head of the list is reset. 414 415 This means the current handler and every handler that has already been 416 checked are not on the list while a handler is run. If a resumption is thrown 417 during the handling of another resumption the active handlers and all the 418 other handler checked up to this point will not be checked again. 460 Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack 461 already examined, is accomplished by updating the front of the list as the 462 search continues. Before the handler at a node is called the head of the list 463 is updated to the next node of the current node. After the search is complete, 464 successful or not, the head of the list is reset. 465 466 This mechanism means the current handler and every handler that has already 467 been checked are not on the list while a handler is run. If a resumption is 468 thrown during the handling of another resumption the active handlers and all 469 the other handler checked up to this point are not checked again. 419 470 420 471 This structure also supports new handler added while the resumption is being 421 472 handled. These are added to the front of the list, pointing back along the 422 stack -- the first one will point over all the checked handlers -- and the 423 ordering is maintained. 424 425 \subsection{Libunwind Compatibility} 426 Resumption does not use libunwind for two simple reasons. The first is that 427 it does not have to unwind anything so would never need to use the clean-up 428 phase. Still the search phase could be used to make it free to enter or exit 429 a try statement with resumption handlers in the same way termination handlers 430 are for the same trade off in the cost of the throw. This is where the second 431 reason comes in, there is no way to return from a search without installing 432 a handler or raising an error. 433 434 Although work arounds could be created none seemed to be worth it for the 435 prototype. This implementation has no difference in behaviour and is much 436 simpler. 473 stack -- the first one points over all the checked handlers -- and the ordering 474 is maintained. 475 476 \label{p:zero-cost} 477 Note, the resumption implementation has a cost for entering/exiting a @try@ 478 statement with @catchResume@ clauses, whereas a @try@ statement with @catch@ 479 clauses has zero-cost entry/exit. While resumption does not need the stack 480 unwinding and cleanup provided by libunwind, it could use the search phase to 481 providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way 482 to return from a libunwind search without installing a handler or raising an 483 error. Although workarounds might be possible, they are beyond the scope of 484 this thesis. The current resumption implementation has simplicity in its 485 favour. 437 486 % Seriously, just compare the size of the two chapters and then consider 438 487 % that unwind is required knowledge for that chapter. … … 440 489 \section{Finally} 441 490 % Uses destructors and GCC nested functions. 442 Finally clauses are a simple decomposition to some of the existing features. 443 The code in the block is placed into a GCC nested function with a unique name, 444 no arguments or return values. This nested function is then set as the 445 clean-up function of an empty object that is declared at the beginning of a 446 block placed around the contexts of the try statement. 491 Finally clauses is placed into a GCC nested-function with a unique name, and no 492 arguments or return values. This nested function is then set as the cleanup 493 function of an empty object that is declared at the beginning of a block placed 494 around the context of the associated @try@ statement. 447 495 448 496 The rest is handled by GCC. The try block and all handlers are inside the 449 block. When they are complete control exits the block and the empty object450 is cleanedup, which runs the function that contains the finally code.497 block. At completion, control exits the block and the empty object is cleaned 498 up, which runs the function that contains the finally code. 451 499 452 500 \section{Cancellation} … … 454 502 455 503 Cancellation also uses libunwind to do its stack traversal and unwinding, 456 however it uses a different primary function @_Unwind_ForcedUnwind@. 457 Details of its interface can be found in the unwind section.458 459 The first step of cancellation is to find the stack was cancelled and which460 type of stack it is. Luckily the threadslibrary stores the main thread461 pointer and the current thread pointer and every thread stores a pointer to504 however it uses a different primary function @_Unwind_ForcedUnwind@. Details 505 of its interface can be found in the \VRef{s:ForcedUnwind}. 506 507 The first step of cancellation is to find the cancelled stack and its type: 508 coroutine or thread. Fortunately, the thread library stores the main thread 509 pointer and the current thread pointer, and every thread stores a pointer to 462 510 its main coroutine and the coroutine it is currently executing. 463 511 464 So if the the current thread's main and current coroutine do not match, it is 465 a coroutine cancellation. Otherwise if the main and current thread do not 466 match, it is a thread cancellation. Otherwise it is a main thread 467 cancellation. 468 469 However if the threading library is not linked then execution must be on the 470 main stack as that is the only one that exists. So the entire check is skipped 471 using the linker and weak symbols. Instead the main thread cancellation is 472 unconditionally preformed. 473 474 Regardless of how they are choosen afterwords the stop function and the stop 475 parameter are passed to the forced unwind functon. The general pattern of all 476 three stop functions is the same, they continue unwinding until the end of 477 stack when they do there primary work. 478 479 Main stack cancellation it is very simple. The ``transfer" is just an abort, 480 the program stops executing. 481 482 The coroutine cancellation stores the exception on the coroutine and then 483 does a coroutine context switch. The rest is handled inside resume. Every time 484 control returns from a resumed thread there is a check to see if it is 485 cancelled. If it is the exception is retrieved and the CoroutineCancelled 486 exception is constructed and loaded. It is then thrown as a regular exception 487 with the default handler coming from the context of the resumption call. 488 489 The thread cancellation stores the exception on the thread's main stack and 490 then returns to the scheduler. The rest is handled by the joiner. The wait 491 for the joined thread to finish works the same but after that it checks 492 to see if there was a cancellation. If there was the exception is retrieved 493 and the ThreadCancelled exception is constructed. The default handler is 494 passed in as a function pointer. If it is null (as it is for the 495 auto-generated joins on destructor call) it a default is used that simply 496 calls abort; which gives the required handling on implicate join. 512 The first check is if the current thread's main and current coroutine do not 513 match, implying a coroutine cancellation; otherwise, it is a thread 514 cancellation. Otherwise it is a main thread cancellation. \PAB{Previous 515 sentence does not make sense.} 516 517 However, if the threading library is not linked, the sequential execution is on 518 the main stack. Hence, the entire check is skipped because the weak-symbol 519 function is loaded. Therefore, a main thread cancellation is unconditionally 520 performed. 521 522 Regardless of how the stack is chosen, the stop function and parameter are 523 passed to the forced-unwind function. The general pattern of all three stop 524 functions is the same: they continue unwinding until the end of stack when they 525 do there primary work. 526 527 For main stack cancellation, the transfer is just a program abort. 528 529 For coroutine cancellation, the exception is stored on the coroutine's stack, 530 and the coroutine context switches to its last resumer. The rest is handled on 531 the backside of the resume, which check if the resumed coroutine is 532 cancelled. If cancelled, the exception is retrieved from the resumed coroutine, 533 and a @CoroutineCancelled@ exception is constructed and loaded with the 534 cancelled exception. It is then resumed as a regular exception with the default 535 handler coming from the context of the resumption call. 536 537 For thread cancellation, the exception is stored on the thread's main stack and 538 then context switched to the scheduler. The rest is handled by the thread 539 joiner. When the join is complete, the joiner checks if the joined thread is 540 cancelled. If cancelled, the exception is retrieved and the joined thread, and 541 a @ThreadCancelled@ exception is constructed and loaded with the cancelled 542 exception. The default handler is passed in as a function pointer. If it is 543 null (as it is for the auto-generated joins on destructor call), the default is 544 used, which is a program abort. 545 %; which gives the required handling on implicate join.
Note: See TracChangeset
for help on using the changeset viewer.