- Timestamp:
- May 17, 2021, 9:44:58 AM (3 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 8f910430
- Parents:
- 58d471f (diff), 299b8b2 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)
links above to see all the changes relative to each parent. - Location:
- doc/theses/andrew_beach_MMath
- Files:
-
- 1 added
- 4 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/cfalab.sty
r58d471f rfc1347d0 1 1 % Package for CFA Research Lab. 2 % (Now more a personal collection and testing grounds for common.sty.) 2 3 % 3 4 % This is a collection of commands everyone working on CFA related documents … … 23 24 % space and '{}<whatever-follows>' to force remove one. 24 25 % 26 % \CFA 25 27 % Cforall with the forall symbol. 26 28 \newrobustcmd\CFA{\textsf{C\raisebox{\depth}{\rotatebox{180}{A}}}\xspace} 27 % C++ with kerning. You may optionally append a standard number. 29 % \Cpp[<std>] 30 % C++ symbol name. You may optionally provide <std> to specify a standard. 28 31 \newrobustcmd\Cpp[1][\xspace]{C++#1} 29 32 … … 45 48 \newcommand*\colour[2]{{\color{#1}#2}} 46 49 47 % \code*{<code>} 48 % Use the listings package to format a snipit of <code>. 49 \newrobustcmd*\codeCFA[1]{\lstinline[language=CFA]{#1}} 50 \newrobustcmd*\codeC[1]{\lstinline[language=C]{#1}} 51 \newrobustcmd*\codeCpp[1]{\lstinline[language=C++]{#1}} 52 \newrobustcmd*\codePy[1]{\lstinline[language=Python]{#1}} 50 % \code{<language>}{<code>} 51 % Use the listings package to format the snipit of <code> in <language>. 52 \newrobustcmd*\code[2]{\lstinline[language=#1]{#2}} 53 53 54 % \begin{cfa}[<options>] 55 % \end{cfa} 54 56 % Use the listings package to format a block of CFA code. 55 57 % Extra listings options can be passed in as an optional argument. -
doc/theses/andrew_beach_MMath/features.tex
r58d471f rfc1347d0 24 24 25 25 Some well known examples include the @throw@ statements of \Cpp and Java and 26 the \code Py{raise} statement from Python. In real systems a raise may preform27 some other work (such as memory management) but for the purposes of this 28 overview that can be ignored.26 the \code{Python}{raise} statement from Python. In real systems a raise may 27 preform some other work (such as memory management) but for the 28 purposes of this overview that can be ignored. 29 29 30 30 \subparagraph{Handle} … … 93 93 A handler labelled with any given exception can handle exceptions of that 94 94 type or any child type of that exception. The root of the exception hierarchy 95 (here \code C{exception}) acts as a catch-all, leaf types catch single types95 (here \code{C}{exception}) acts as a catch-all, leaf types catch single types 96 96 and the exceptions in the middle can be used to catch different groups of 97 97 related exceptions. … … 182 182 While much of the virtual infrastructure is created, it is currently only used 183 183 internally for exception handling. The only user-level feature is the virtual 184 cast, which is the same as the \Cpp \code Cpp{dynamic_cast}.184 cast, which is the same as the \Cpp \code{C++}{dynamic_cast}. 185 185 \label{p:VirtualCast} 186 186 \begin{cfa} -
doc/theses/andrew_beach_MMath/implement.tex
r58d471f rfc1347d0 15 15 \subsection{Virtual Type} 16 16 Virtual types only have one change to their structure: the addition of a 17 pointer to the virtual table, called the \emph{virtual-table pointer}. 18 Internally, the field is called 19 @virtual_table@. 20 This constant pointer is always the first field of the table so when 21 casting to a supertype, the field's location is always known. 22 The field is initialized as part of all generated constructors. 23 \todo{They only come as part exceptions and don't work.} 24 %After the object is created the field is constant. 25 Dereferencing it gives the virtual table and access to the 26 type's virtual members. 17 pointer to the virtual table, which is called the \emph{virtual-table pointer}. 18 Internally, the field is called @virtual_table@. 19 The field is fixed after construction. It is always the first field in the 20 structure so that its location is always known. 21 \todo{Talk about constructors for virtual types (after they are working).} 22 23 This is what binds an instance of a virtual type to a virtual table. This 24 pointer can be used as an identity check. It can also be used to access the 25 virtual table and the virtual members there. 26 27 \subsection{Type Id} 28 Every virtual type has a unique id. 29 Type ids can be compared for equality (the types reperented are the same) 30 or used to access the type's type information. 31 The type information currently is only the parent's type id or, if the 32 type has no parent, zero. 33 34 The id's are implemented as pointers to the type's type information instance. 35 Derefencing the pointer gets the type information. 36 By going back-and-forth between the type id and 37 the type info one can find every ancestor of a virtual type. 38 It also pushes the issue of creating a unique value (for 39 the type id) to the problem of creating a unique instance (for type 40 information) which the linker can solve. 41 42 Advanced linker support is required because there is no place that appears 43 only once to attach the type information to. There should be one structure 44 definition but it is included in multiple translation units. Each virtual 45 table definition should be unique but there are an arbitrary number of thoses. 46 So the special section prefix \texttt{.gnu.linkonce} is used. 47 With a unique suffix (making the entire section name unique) the linker will 48 remove multiple definition making sure only one version exists after linking. 49 Then it is just a matter of making sure there is a unique name for each type. 50 51 This is done in three phases. 52 The first phase is to generate a new structure definition to store the type 53 information. The layout is the same in each case, just the parent's type id, 54 but the types are changed. 55 The structure's name is change, it is based off the virtual type's name, and 56 the type of the parent's type id. 57 If the virtual type is polymorphic then the type information structure is 58 polymorphic as well, with the same polymorphic arguments. 59 60 The second phase is to generate an instance of the type information with a 61 almost unique name, generated by mangling the virtual type name. 62 63 The third phase is implicit with \CFA's overloading scheme. \CFA mangles 64 names with type information so that all of the symbols exported to the linker 65 are unique even if in \CFA code they are the same. Having two declarations 66 with the same name and same type is forbidden because it is impossible for 67 overload resolution to pick between them. This is why a unique type is 68 generated for each virtual type. 69 Polymorphic information is included in this mangling so polymorphic 70 types will have seperate instances for each set of polymorphic arguments. 71 72 \begin{cfa} 73 struct /* type name */ { 74 /* parent type name */ const * parent; 75 }; 76 77 __attribute__((section(".gnu.linkonce./* instance name */"))) 78 /* type name */ const /* instance name */ = { 79 &/* parent instance name */, 80 }; 81 \end{cfa} 27 82 28 83 \subsection{Virtual Table} 29 % PAB: These 2 paragraphs are repeated below, and maybe some of the paragraph above, too. 30 \begin{comment} 31 Every time a virtual type is defined, a new virtual table-type is 32 instantiated. 33 The uniqueness of the virtual-table 34 instance is important because its address 35 is used as the identifier for the virtual type. Hence, a pointer to the 36 virtual table and the ID for the virtual type are interchangeable. 37 \todo{Unique instances might be going so we will have to talk about the new 38 system instead.} 39 40 The first step is creating the virtual-table type. 41 The virtual-table type is a structure and is described in terms of 42 its fields. The first field contains the parent-type ID (or a pointer to 43 the parent virtual-table) or 0 (null pointer). 44 Next are repeated fields from on the parent virtual-table. 45 Finally, the fields used to store any new virtual members of the new 46 the virtual type. 47 \end{comment} 48 49 %The virtual system is accessed through a private constant field inserted at the 50 %beginning of every virtual type. This field 51 The virtual-table pointer 52 points at a type's virtual table (see Figure~\vref{f:VirtualTableLayout}). 53 %and is assigned during the object's 54 %construction. 55 The address of a virtual table acts as the unique identifier for 56 the virtual type, and the first field of a virtual table is a pointer to the 57 parent virtual-table or @0p@ (null pointer). The remaining fields are duplicated from the 58 parent tables in this type's inheritance chain, followed by any fields this type 59 introduces. Parent fields are duplicated so they can be changed, \ie all virtual 60 members are overridable, while the parent pointer allows access to the original values. 61 Hence, references to the dispatched type 62 are replaced with the current virtual type. 63 % These are always taken by pointer or reference. 84 Each virtual type has a virtual table type that stores its type id and 85 virtual members. 86 Each virtual type instance is bound to a table instance that is filled with 87 the values of virtual members. 88 Both the layout of the fields and their value are decided by the rules given 89 below. 90 91 The layout always comes in three parts. 92 The first section is just the type id at the head of the table. It is always 93 there to ensure that 94 The second section are all the virtual members of the parent, in the same 95 order as they appear in the parent's virtual table. Note that the type may 96 change slightly as references to the ``this" will change. This is limited to 97 inside pointers/references and via function pointers so that the size (and 98 hence the offsets) are the same. 99 The third section is similar to the second except that it is the new virtual 100 members introduced at this level in the hierarchy. 64 101 65 102 \begin{figure} 66 % Simple ascii diragram:67 103 \begin{cfa} 68 parent_pointer // \C{parent pointer to access its fields} 69 parent_field0 // \C{same layout as parent to allow replacement}104 type_id 105 parent_field0 70 106 ... 71 107 parent_fieldN 72 child_field0 // \C{new types for this virtual table}108 child_field0 73 109 ... 74 110 child_fieldN 75 size76 alignment77 111 \end{cfa} 78 %\todo{Refine the diagram}79 112 \caption{Virtual Table Layout} 80 113 \label{f:VirtualTableLayout} 114 \todo*{Improve the Virtual Table Layout diagram.} 81 115 \end{figure} 82 116 83 % For each virtual type, a virtual table is constructed. This is both a new type 84 % and an instance of that type. Other instances of the type could be created 85 % but the system doesn't use them. So this section will go over the creation of 86 % the type and the instance. 87 88 \begin{comment} 89 PAB: seems to be said already. 90 A virtual table is created when a virtual type is created. The name of the 91 type is created by mangling the name of the base type. The name of the instance 92 is also generated by name mangling. The fields are initialized automatically. 93 The parent field is initialized by getting the type of the parent field and 94 using that to calculate the mangled name of the parent's virtual-table type. 95 \end{comment} 96 There are two special fields that are included like normal fields but have 97 special initialization rules: the @size@ field is the type's size and is 98 initialized with a @sizeof@ expression, the @align@ field is the type's 99 alignment and uses an @alignof@ expression. The remaining fields are resolved 100 to a name matching the field's name and type using the normal visibility and 101 overload resolution rules of the type system. 102 103 These operations are split up into several groups depending on where they take 104 place, which varies for monomorphic and polymorphic types. The first devision is 105 between the declarations and the definitions. Declarations, such as a function 106 signature or an aggregate's name, must always be visible but may be repeated in 107 the form of forward declarations in headers. Definitions, such as function 108 bodies and a aggregate's layout, can be separately compiled but must occur 109 exactly once in a source file. 110 111 The declarations include the virtual-type definition and forward declarations 112 of the virtual-table instance, constructor, message function and 113 @get_exception_vtable@. The definition includes the storage and initialization 114 of the virtual table instance and the bodies of the three functions. 115 116 Monomorphic instances put all of these two groups in one place. 117 Polymorphic instances split out the core declarations and definitions from 118 the per-instance information. The virtual-table type and most of the functions 119 are polymorphic so they are all part of the core. The virtual-table instance 120 and the @get_exception_vtable@ function \PAB{ are ...}. 121 117 The first and second sections together mean that every virtual table has a 118 prefix that has the same layout and types as its parent virtual table. 119 This, combined with the fixed offset to the virtual table pointer, means that 120 for any virtual type it doesn't matter if we have it or any of its 121 descendants, it is still always safe to access the virtual table through 122 the virtual table pointer. 123 From there it is safe to check the type id to identify the exact type of the 124 underlying object, access any of the virtual members and pass the object to 125 any of the method-like virtual members. 126 \todo{Introduce method-like virtual members.} 127 128 When a virtual table is declared the user decides where to declare it and its 129 name. The initialization of the virtual table is entirely automatic based on 130 the context of the declaration. 131 132 The type id is always fixed, each virtual table type will always have one 133 exactly one possible type id. 134 The virtual members are usually filled in by resolution. The best match for 135 a given name and type at the declaration site is filled in. 136 There are two exceptions to that rule: the @size@ field is the type's size 137 and is set to the result of a @sizeof@ expression, the @align@ field is the 138 type's alignment and similarly uses an @alignof@ expression. 139 140 \subsubsection{Concurrency Integration} 122 141 Coroutines and threads need instances of @CoroutineCancelled@ and 123 142 @ThreadCancelled@ respectively to use all of their functionality. When a new 124 data type is declared with @coroutine@ or @thread@ ,the forward declaration for143 data type is declared with @coroutine@ or @thread@ the forward declaration for 125 144 the instance is created as well. The definition of the virtual table is created 126 145 at the definition of the main function. 127 128 \PAB{You need an example here to show what happens for this case.} 129 146 \todo{Add an example with code snipits.} 130 147 131 148 \subsection{Virtual Cast} … … 134 151 % The C-cast is just to make sure the generated code is correct so the rest of 135 152 % the section is about that function. 136 The function is 153 The function is implemented in the standard library and has the following 154 signature: 137 155 \begin{cfa} 138 void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent, 156 void * __cfa__virtual_cast( 157 struct __cfa__parent_vtable const * parent, 139 158 struct __cfa__parent_vtable const * const * child ); 140 159 \end{cfa} 141 and it is implemented in the standard library. The structure represents the 142 head of a virtual table, which is the pointer to the parent virtual table. The 143 @parent@ points directly at the parent-type virtual-table, while the @child@ 144 points at the object of the (possible) child type. 145 146 \PAB{Need a figure to show this relationship.} 147 148 In terms of the virtual-cast expression, @parent@ comes from looking up the 149 type being cast to and @child@ is the result of the expression being cast. 150 Because the complier outputs C code, some C-type casts are also used. 151 The last bit of glue is a map that saves every virtual type the compiler 152 sees. This table is used to check the type used in a virtual cast is a virtual 153 type and to get its virtual table. 154 (It also checks for conflicting definitions.) 155 156 \PAB{Can this be rolled into the figure above?} 157 158 Inside the function is a simple conditional. If the type represented by 159 @parent@ is an ancestor of the type represented by @*child@ (it 160 requires one more level of dereference to pass through the object) then @child@ 161 is returned, otherwise the null pointer is returned. 162 163 The check is a simple linear search (like \Cpp RTTI). If the child 164 virtual table or any of its ancestors (which are retrieved through the first 165 field of every virtual table) are the same as the parent virtual-table then 166 the cast succeeds. 160 \todo{Get rid of \_\_cfa\_\_parent\_vtable in the standard library and then 161 the document.} 162 The type id of target type of the virtual cast is passed in as @parent@ and 163 the cast target is passed in as @child@. 164 165 For C generation both arguments and the result are wrapped with type casts. 166 There is also an internal store inside the compiler to make sure that the 167 target type is a virtual type. 168 % It also checks for conflicting definitions. 169 170 The virtual cast either returns the original pointer as a new type or null. 171 So the function just does the parent check and returns the approprate value. 172 The parent check is a simple linear search of child's ancestors using the 173 type information. 167 174 168 175 \section{Exceptions} … … 174 181 % resumption doesn't as well. 175 182 176 % Many modern languages work with an inter nal stack that function push and pop183 % Many modern languages work with an interal stack that function push and pop 177 184 % their local data to. Stack unwinding removes large sections of the stack, 178 185 % often across functions. 179 186 180 187 Stack unwinding is the process of removing stack frames (activations) from the 181 stack. On function entry and return, unwinding is handled directly by the call/return code 182 embedded in a function. Usually, the stack-frame size is known statically 183 based on parameter and local variable declarations. For dynamically-sized 184 local variables. 185 (Often called a variable-length array or VLA, even when the variable type is an aggregate.) 186 For VLAs, a runtime computation is necessary to know the frame 187 size. Finally, a function's frame-size may change during execution as local 188 variables (static or dynamic sized) go in and out of scope, which is a form of VLA. 188 stack. On function entry and return, unwinding is handled directly by the 189 call/return code embedded in the function. 190 In many cases the position of the instruction pointer (relative to parameter 191 and local declarations) is enough to know the current size of the stack 192 frame. 193 194 Usually, the stack-frame size is known statically based on parameter and 195 local variable declarations. Even with dynamic stack-size the information 196 to determain how much of the stack has to be removed is still contained 197 within the function. 189 198 Allocating/deallocating stack space is usually an $O(1)$ operation achieved by 190 199 bumping the hardware stack-pointer up or down as needed. 191 192 Unwinding across multiple stack frames is more complex because individual stack-management 193 code associated with each frame can be bypassed. That is, the location 194 of a function's frame-management code is largely unknown and dispersed 195 throughout the function, hence the current frame size managed by that code is 196 also unknown. Hence, code unwinding across frames does not have direct 197 knowledge about what is on the stack, and hence, how much of the stack needs to 198 be removed. 199 200 % At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply 201 % move the top of the stack, discarding everything on the stack above a certain 202 % point. However this ignores all the cleanup code that should be run when 203 % certain sections of the stack are removed (for \CFA these are from destructors 204 % and finally clauses) and also requires that the point to which the stack is 205 % being unwound is known ahead of time. libunwind is used to address both of 206 % these problems. 200 Constructing/destructing values on the stack takes longer put in terms of 201 figuring out what needs to be done is of similar complexity. 202 203 Unwinding across multiple stack frames is more complex because that 204 information is no longer contained within the current function. 205 With seperate compilation a function has no way of knowing what its callers 206 are so it can't know how large those frames are. 207 Without altering the main code path it is also hard to pass that work off 208 to the caller. 207 209 208 210 The traditional unwinding mechanism for C is implemented by saving a snap-shot … … 211 213 reseting to a snap-shot of an arbitrary but existing function frame on the 212 214 stack. It is up to the programmer to ensure the snap-shot is valid when it is 213 reset and that unwound frames do not have side-effects. 214 Hence, this unwinding approach is fragile with potential errors that are 215 difficult to debug because the stack becomes corrupted. 216 217 With respect to stack side-effects, many languages define cleanup actions that must be taken when objects 218 are deallocated from the stack, when the function of blocks within the function end, such as running a variable's 219 destructor or a @try@ statement's @finally@ clause. 220 The purpose of these side-effects is to reestablish the global state of the program, such as dynamic memory-allocation or file access. 221 Handling these side-effect mechanisms 222 requires walking the stack and checking each stack frame for these potential 223 actions, where a frame can be any block with declarations. 224 225 In languages like \Cpp and Java, it must be possible to walk the stack frames in search of @try@ 226 statements to match and execute a handler. For termination exceptions, it must 227 also be possible to unwind all stack frames from the throw to the matching 228 catch (including the @try@ block), and each of these frames must be checked for cleanup actions. Stack 229 walking is where most of the complexity and expense of exception handling 230 appears. 215 reset and that all required clean-up from the unwound stacks is preformed. 216 This approach is fragile and forces a work onto the surounding code. 217 218 With respect to that work forced onto the surounding code, 219 many languages define clean-up actions that must be taken when certain 220 sections of the stack are removed. Such as when the storage for a variable 221 is removed from the stack or when a try statement with a finally clause is 222 (conceptually) popped from the stack. 223 None of these should be handled by the user, that would contradict the 224 intention of these features, so they need to be handled automatically. 225 226 To safely remove sections of the stack the language must be able to find and 227 run these clean-up actions even when removing multiple functions unknown at 228 the beginning of the unwinding. 231 229 232 230 One of the most popular tools for stack management is libunwind, a low-level … … 261 259 262 260 The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and 263 attaches its personality function. 264 It attaches a series of opaque directives (@.cfi_personality@ directive) 265 used internally and not part of this work. 266 However, this 261 attaches a personality function to each function. 262 In plain C (which \CFA currently compiles down to) this 267 263 flag only handles the cleanup attribute: 268 264 \begin{cfa} … … 270 266 int avar __attribute__(( cleanup(clean_up) )); 271 267 \end{cfa} 272 that is used on a variable and specifies a function, in this case @clean_up@, 273 run when the variable goes out of scope, which is used to mimic destructors. 274 However, this feature cannot be used to mimic @try@ statements as it cannot 275 control the unwinding. 268 The attribue is used on a variable and specifies a function, 269 in this case @clean_up@, run when the variable goes out of scope. 270 This is enough to mimic destructors, but not try statements which can effect 271 the unwinding. 272 273 To get full unwinding support all of this has to be done directly with 274 assembly and assembler directives. Partiularly the cfi directives 275 \texttt{.cfi\_lsda} and \texttt{.cfi\_personality}. 276 276 277 277 \subsection{Personality Functions} … … 279 279 section covers some of the important parts of the interface. 280 280 281 A personality function can p erform different actions depending on how it is281 A personality function can preform different actions depending on how it is 282 282 called. 283 283 \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] … … 313 313 @_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs 314 314 the cleanup phase and uses a different means to decide when to stop 315 (see Section~\vref{s:ForcedUnwind}).315 (see \vref{s:ForcedUnwind}). 316 316 \end{enumerate} 317 317 318 318 The @exception_class@ argument is a copy of the 319 \lstinline[language=C]|exception|'s @exception_class@ field. 320 \PAB{Say more.} 321 322 The \lstinline[language=C]|exception| argument is a pointer to the user 323 provided storage object. It has two public fields, the exception class, which 324 is just a number, identifying the exception handling mechanism that 325 created it, and the cleanup function. The cleanup function is called if 326 required by the exception. 319 \code{C}{exception}'s @exception_class@ field. 320 This a number that identifies the exception handling mechanism that created 321 the 322 323 The \code{C}{exception} argument is a pointer to the user 324 provided storage object. It has two public fields: the @exception_class@, 325 which is described above, and the @exception_cleanup@ function. 326 The clean-up function is used by the EHM to clean-up the exception if it 327 should need to be freed at an unusual time, it takes an argument that says 328 why it had to be cleaned up. 327 329 328 330 The @context@ argument is a pointer to an opaque type passed to helper … … 347 349 @_URC_END_OF_STACK@. 348 350 349 Second, when a handler is matched, raise exception walks the stack again performing the cleanup350 phase .351 Second, when a handler is matched, raise exception moves to the clean-up 352 phase and walks the stack a second time. 351 353 Once again, it calls the personality functions of each stack frame from newest 352 354 to oldest. This pass stops at the stack frame containing the matching handler. … … 403 405 Each stack must have its own exception context. In a sequential \CFA program, 404 406 there is only one stack with a single global exception-context. However, when 405 the library @libcfathread@ is linked, there are multiple stacks , whereeach407 the library @libcfathread@ is linked, there are multiple stacks and each 406 408 needs its own exception context. 407 409 408 The function @this_exception_context@ provides general access to the exception context.409 For sequential execution, this function is defined as410 The exception context should be retrieved by calling the function 411 @this_exception_context@. For sequential execution, this function is defined as 410 412 a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is 411 413 concurrent, it links with @libcfathread@, where this function is defined with a … … 422 424 % catches. Talk about GCC nested functions. 423 425 424 Termination exceptions use libunwind heavily because \CFA termination exceptions match 426 \CFA termination exceptions use libunwind heavily because they match \Cpp 425 427 \Cpp exceptions closely. The main complication for \CFA is that the 426 428 compiler generates C code, making it very difficult to generate the assembly to … … 430 432 The first step of a termination raise is to copy the exception into memory 431 433 managed by the exception system. Currently, the system uses @malloc@, rather 432 than reserved memory or the stack top. The exception -handling mechanism manages434 than reserved memory or the stack top. The exception handling mechanism manages 433 435 memory for the exception as well as memory for libunwind and the system's own 434 436 per-exception storage. … … 446 448 \label{f:ExceptionLayout} 447 449 \end{figure} 448 449 Exceptions are stored in variable-sized blocks (see Figure~\vref{f:ExceptionLayout}). 450 The first component is a fixed-sized data-structure that contains the 450 \todo*{Convert the exception layout to an actual diagram.} 451 452 Exceptions are stored in variable-sized blocks (see \vref{f:ExceptionLayout}). 453 The first component is a fixed-sized data structure that contains the 451 454 information for libunwind and the exception system. The second component is an 452 455 area of memory big enough to store the exception. Macros with pointer arthritic … … 454 457 @_Unwind_Exception@ to the entire node. 455 458 456 Multiple exceptions can exist because handlers can call functions that raise 457 exceptions. Figure~\vref{f:MultipleExceptions} shows a \Cpp program where 458 exceptions are handled, and then a function is called from the handler that 459 raises a new exception. The previous exception must persist because it is 460 unhandled, and hence, control can return to the handler and that exception is 461 reraised. 459 Multipe exceptions can exist at the same time because exceptions can be 460 raised inside handlers, destructors and finally blocks. 461 Figure~\vref{f:MultipleExceptions} shows a program that has multiple 462 exceptions active at one time. 463 Each time an exception is thrown and caught the stack unwinds and the finally 464 clause runs. This will throw another exception (until @num_exceptions@ gets 465 high enough) which must be allocated. The previous exceptions may not be 466 freed because the handler/catch clause has not been run. 467 So the EHM must keep them alive while it allocates exceptions for new throws. 462 468 463 469 \begin{figure} 464 470 \centering 471 % Andrew: Figure out what these do and give them better names. 465 472 \newsavebox{\myboxA} 466 473 \newsavebox{\myboxB} 467 474 \begin{lrbox}{\myboxA} 468 \begin{lstlisting}[language=C++,{moredelim=**[is][\color{red}]{@}{@}}] 469 struct E {}; 470 int cnt = 3; 471 void f( int i ) { 472 if ( i == 0 ) @throw E();@ 473 try { 474 @f( i - 1 );@ 475 } catch( E ) { // handler h 476 cnt -= 1; 477 if ( cnt > 0 ) @f( 2 );@ 478 } 475 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}] 476 unsigned num_exceptions = 0; 477 void throws() { 478 try { 479 try { 480 ++num_exceptions; 481 throw (Example){table}; 482 } finally { 483 if (num_exceptions < 3) { 484 throws(); 485 } 486 } 487 } catch (exception_t *) { 488 --num_exceptions; 489 } 479 490 } 480 int main() { @f( 2 );@ } 491 int main() { 492 throws(); 493 } 481 494 \end{lstlisting} 482 495 \end{lrbox} … … 484 497 \begin{lrbox}{\myboxB} 485 498 \begin{lstlisting} 486 h $\makebox[0pt][l]{\textbackslash}f$487 f488 f489 h $\makebox[0pt][l]{\textbackslash}f$ throw E$\(_2\)$490 f491 f492 h $\makebox[0pt][l]{\textbackslash}f$ throw E$\(_1\)$493 f494 f495 499 \end{lstlisting} 496 500 \end{lrbox} … … 503 507 \label{f:MultipleExceptions} 504 508 \end{figure} 505 506 In this case, the exception nodes are linked together in a list, one list per stack, with the 509 \todo*{Work on multiple exceptions code sample.} 510 511 All exceptions are stored in nodes which are then linked together in lists, 512 one list per stack, with the 507 513 list head stored in the exception context. Within each linked list, the most 508 514 recently thrown exception is at the head followed by older thrown … … 515 521 exception, the copy function, and the free function, so they are specific to an 516 522 exception type. The size and copy function are used immediately to copy an 517 exception into managed memory. After the exception is handled, the free function518 is used to clean up the exception and then the entire node is passed to free 519 so the memory can be given back to the heap.523 exception into managed memory. After the exception is handled, the free 524 function is used to clean up the exception and then the entire node is 525 passed to free so the memory can be given back to the heap. 520 526 521 527 \subsection{Try Statements and Catch Clauses} 522 528 The try statement with termination handlers is complex because it must 523 compensate for the lack of assembly 529 compensate for the lack of assembly-code generated from \CFA. Libunwind 524 530 requires an LSDA and personality function for control to unwind across a 525 531 function. The LSDA in particular is hard to mimic in generated C code. … … 530 536 calls them. 531 537 Because this function is known and fixed (and not an arbitrary function that 532 happens to contain a try statement), th is means the LSDA can be generated ahead538 happens to contain a try statement), the LSDA can be generated ahead 533 539 of time. 534 540 535 541 Both the LSDA and the personality function are set ahead of time using 536 embedded assembly. This assembly code is handcrafted using C @asm@ statements and contains 537 enough information for the single try statement the function represents. 542 embedded assembly. This assembly code is handcrafted using C @asm@ statements 543 and contains 544 enough information for the single try statement the function repersents. 538 545 539 546 The three functions passed to try terminate are: … … 563 570 nested functions and all other functions besides @__cfaehm_try_terminate@ in 564 571 \CFA use the GCC personality function and the @-fexceptions@ flag to generate 565 the LSDA. Through this mechanism, \CFA destructors are implemented via the cleanup attribute.566 567 \ PAB{Try to put together an example try statement illustrating these components.}572 the LSDA. 573 Using this pattern, \CFA implements destructors with the cleanup attribute. 574 \todo{Add an example of the conversion from try statement to functions.} 568 575 569 576 \section{Resumption} 570 577 % The stack-local data, the linked list of nodes. 571 578 572 Resumption is simpler to implement than termination because there is no stack 573 unwinding. \PAB{You need to explain how the \lstinline{catchResume} clauses are 574 handled. Do you use the personality mechanism in libunwind or do you roll your 575 own mechanism?} 576 577 The 578 resumption raise uses a list of nodes for its stack traversal. The head of the 579 list is stored in the exception context. The nodes in the list have a pointer 580 to the next node and a pointer to the handler function. 581 A resumption raise traverses this list. At each node the handler function is 582 called, passing the exception by pointer. It returns true if the exception is 583 handled and false otherwise. 584 585 The handler function does both the matching and handling. It computes the 586 condition of each @catchResume@ in top-to-bottom order, until it finds a 587 handler that matches. If no handler matches then the function returns 588 false. Otherwise the matching handler is run; if it completes successfully, the 589 function returns true. Rethrowing, through the @throwResume;@ statement, 590 causes the function to return true. 579 Resumption simpler to implement than termination 580 because there is no stack unwinding. 581 Instead of storing the data in a special area using assembly, 582 there is just a linked list of possible handlers for each stack, 583 with each node on the list reperenting a try statement on the stack. 584 585 The head of the list is stored in the exception context. 586 The nodes are stored in order, with the more recent try statements closer 587 to the head of the list. 588 Instead of traversing the stack resumption handling traverses the list. 589 At each node the EHM checks to see if the try statement the node repersents 590 can handle the exception. If it can, then the exception is handled and 591 the operation finishes, otherwise the search continues to the next node. 592 If the search reaches the end of the list without finding a try statement 593 that can handle the exception the default handler is executed and the 594 operation finishes. 595 596 In each node is a handler function which does most of the work there. 597 The handler function is passed the raised the exception and returns true 598 if the exception is handled and false if it cannot be handled here. 599 600 For each @catchResume@ clause the handler function will: 601 check to see if the raised exception is a descendant type of the declared 602 exception type, if it is and there is a conditional expression then it will 603 run the test, if both checks pass the handling code for the clause is run 604 and the function returns true, otherwise it moves onto the next clause. 605 If this is the last @catchResume@ clause then instead of moving onto 606 the next clause the function returns false as no handler could be found. 607 608 \todo{Diagram showing a try statement being converted into resumption handlers.} 591 609 592 610 % Recursive Resumption Stuff: … … 603 621 the other handler checked up to this point are not checked again. 604 622 605 This structure also supports new handler sadded while the resumption is being623 This structure also supports new handler added while the resumption is being 606 624 handled. These are added to the front of the list, pointing back along the 607 625 stack -- the first one points over all the checked handlers -- and the ordering 608 626 is maintained. 609 610 \PAB{Again, a figure to show how this works would be helpful.} 627 \todo{Add a diagram for resumption marking.} 611 628 612 629 \label{p:zero-cost} … … 623 640 % that unwind is required knowledge for that chapter. 624 641 625 \PAB{This paragraph needs to be moved to the start of this Section, where I have have my other comment.}626 627 642 \section{Finally} 628 643 % Uses destructors and GCC nested functions. 629 A finally clause is placed into a GCC nested-function with a unique mangled name, and no 630 arguments or return values. This nested function is then set as the cleanup 644 A finally clause is placed into a GCC nested-function with a unique name, 645 and no arguments or return values. 646 This nested function is then set as the cleanup 631 647 function of an empty object that is declared at the beginning of a block placed 632 around the context of anassociated @try@ statement.648 around the context of the associated @try@ statement. 633 649 634 650 The rest is handled by GCC. The try block and all handlers are inside this … … 640 656 641 657 Cancellation also uses libunwind to do its stack traversal and unwinding, 642 however it uses a different primary function ,@_Unwind_ForcedUnwind@. Details643 of its interface can be found in Section~\vref{s:ForcedUnwind}.658 however it uses a different primary function: @_Unwind_ForcedUnwind@. Details 659 of its interface can be found in the Section~\vref{s:ForcedUnwind}. 644 660 645 661 The first step of cancellation is to find the cancelled stack and its type: 646 coroutine or thread. Fortunately, the thread library stores the program-main thread 647 pointer and the current-thread pointer, and every thread stores a pointer to 648 the current coroutine it is executing. 649 650 \PAB{I don't know if my corrections in the previous paragraph are correct.} 651 652 When the active thread and coroutine are the same, the current stack is the thread stack, otherwise it is a coroutine 653 stack. 654 % PAB: repeated? 655 % If it is a thread stack, then an equality check with the stored main 656 % thread pointer and current thread pointer is enough to tell if the current 657 % thread is the main thread or not. 662 coroutine or thread. Fortunately, the thread library stores the main thread 663 pointer and the current thread pointer, and every thread stores a pointer to 664 its main coroutine and the coroutine it is currently executing. 665 \todo*{Consider adding a description of how threads are coroutines.} 666 667 If a the current thread's main and current coroutines are the same then the 668 current stack is a thread stack. Furthermore it is easy to compare the 669 current thread to the main thread to see if they are the same. And if this 670 is not a thread stack then it must be a coroutine stack. 671 658 672 However, if the threading library is not linked, the sequential execution is on 659 673 the main stack. Hence, the entire check is skipped because the weak-symbol … … 663 677 Regardless of how the stack is chosen, the stop function and parameter are 664 678 passed to the forced-unwind function. The general pattern of all three stop 665 functions is the same: continue unwinding until the end of stack.666 %when they 667 %do there primary work. 679 functions is the same: they continue unwinding until the end of stack and 680 then preform their transfer. 681 668 682 For main stack cancellation, the transfer is just a program abort. 669 683 670 For coroutine cancellation, the exception is stored in the coroutine's stack,684 For coroutine cancellation, the exception is stored on the coroutine's stack, 671 685 and the coroutine context switches to its last resumer. The rest is handled on 672 686 the backside of the resume, which check if the resumed coroutine is -
doc/theses/andrew_beach_MMath/uw-ethesis.tex
r58d471f rfc1347d0 93 93 % Removes large sections of the document. 94 94 \usepackage{comment} 95 % Adds todo s (Must be included after comment.)96 \usepackage{todo notes}95 % Adds todo commands. 96 \usepackage{todo} 97 97 % cfa macros used in the document 98 98 \usepackage{cfalab} … … 145 145 146 146 % Exception to the rule of hyperref being the last add-on package 147 \usepackage[ automake,toc,abbreviations]{glossaries-extra}147 \usepackage[toc,abbreviations]{glossaries-extra} 148 148 % If glossaries-extra is not in your LaTeX distribution, get it from CTAN 149 149 % (http://ctan.org/pkg/glossaries-extra), although it's supposed to be in … … 235 235 % Tip: Putting each sentence on a new line is a way to simplify later editing. 236 236 %---------------------------------------------------------------------- 237 \input{intro} 237 238 \input{existing} 238 239 \input{features} 239 240 \input{implement} 240 %\input{unwinding}241 241 \input{future} 242 242 … … 298 298 \phantomsection % allows hyperref to link to the correct page 299 299 300 \todos 301 300 302 %---------------------------------------------------------------------- 301 303 \end{document} % end of logical document
Note: See TracChangeset
for help on using the changeset viewer.