Changeset 830299f for doc/theses
- Timestamp:
- Feb 17, 2021, 4:45:20 PM (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:
- a76da32
- Parents:
- eb24cec0
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/implement.tex
reb24cec0 r830299f 13 13 library. 14 14 15 \subsection{Virtual Type} 16 Virtual types only have one change to their structure, the addition of a 17 pointer to the virtual table. This is always the first field so that 18 if it is cast to a supertype the field's location is still known. 19 20 This field is set as part of all new generated constructors. 21 \todo{They only come as part exceptions and don't work.} 22 After the object is created the field is constant. 23 24 However it can be read from, internally it is just a regular field called 25 @virtual_table@. Dereferencing it gives the virtual table and access to the 26 type's virtual members. 27 15 28 \subsection{Virtual Table} 29 Every time a virtual type is defined the new virtual table type must also be 30 defined. 31 32 The unique instance is important because the address of the virtual table 33 instance is used as the identifier for the virtual type. So a pointer to the 34 virtual table and the ID for the virtual type are interchangable. 35 \todo{Unique instances might be going so we will have to talk about the new 36 system instead.} 37 38 The first step in putting it all together is to create the virtual table type. 39 The virtual table type is just a structure and can be described in terms of 40 its fields. The first field is always the parent type ID (or a pointer to 41 the parent virtual table) or 0 (the null pointer). 42 Next are other fields on the parent virtual table are repeated. 43 Finally are the fields used to store any new virtual members of the new 44 The virtual type 45 16 46 The virtual system is accessed through a private constant field inserted at the 17 47 beginning of every virtual type, called the virtual-table pointer. This field 18 48 points at a type's virtual table and is assigned during the object's 19 construction. 49 construction. The address of a virtual table acts as the unique identifier for 20 50 the virtual type, and the first field of a virtual table is a pointer to the 21 parent virtual-table or @0p@. 51 parent virtual-table or @0p@. The remaining fields are duplicated from the 22 52 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 ( \CC24 \lstinline[language=c++]|override|), so that references to the dispatched type53 introduces. Parent fields are duplicated so they can be changed (all virtual 54 members are overridable), so that references to the dispatched type 25 55 are replaced with the current virtual type. 26 \PAB{Can you create a simple diagram of the layout?}27 56 % These are always taken by pointer or reference. 57 58 % Simple ascii diragram: 59 \begin{verbatim} 60 parent_pointer \ 61 parent_field0 | 62 ... | Same layout as parent. 63 parent_fieldN / 64 child_field0 65 ... 66 child_fieldN 67 \end{verbatim} 68 \todo{Refine the diagram} 28 69 29 70 % For each virtual type, a virtual table is constructed. This is both a new type … … 34 75 A virtual table is created when the virtual type is created. The name of the 35 76 type is created by mangling the name of the base type. The name of the instance 36 is also generated by name mangling. 77 is also generated by name mangling. The fields are initialized automatically. 37 78 The parent field is initialized by getting the type of the parent field and 38 79 using that to calculate the mangled name of the parent's virtual table type. … … 67 108 \begin{sloppypar} 68 109 Coroutines and threads need instances of @CoroutineCancelled@ and 69 @ThreadCancelled@ respectively to use all of their functionality. 110 @ThreadCancelled@ respectively to use all of their functionality. When a new 70 111 data type is declared with @coroutine@ or @thread@ the forward declaration for 71 112 the instance is created as well. The definition of the virtual table is created … … 80 121 The function is 81 122 \begin{cfa} 82 void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent, 123 void * __cfa__virtual_cast( 124 struct __cfa__parent_vtable const * parent, 83 125 struct __cfa__parent_vtable const * const * child ); 84 }85 126 \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 127 and it is implemented in the standard library. The structure reperents the 128 head of a vtable which is the pointer to the parent virtual table. The 129 @parent@ points directly at the parent type virtual table while the @child@ 130 points at the object of the (possibe) child type. 131 132 In terms of the virtual cast expression, @parent@ comes from looking up the 133 type being cast to and @child@ is the result of the expression being cast. 134 Because the complier outputs C code, some type C type casts are also used. 135 The last bit of glue is an map that saves every virtual type the compiler 136 sees. This is used to check the type used in a virtual cast is a virtual 137 type and to get its virtual table. 138 (It also checks for conflicting definitions.) 139 140 Inside the function it is a simple conditional. If the type repersented by 141 @parent@ is or is an ancestor of the type repersented by @*child@ (it 142 requires one more level of derefence to pass through the object) then @child@ 143 is returned, otherwise the null pointer is returned. 144 145 The check itself is preformed is a simple linear search. If the child 146 virtual table or any of its ancestors (which are retreved through the first 147 field of every virtual table) are the same as the parent virtual table then 148 the cast succeeds. 107 149 108 150 \section{Exceptions} … … 121 163 stack. On function entry and return, unwinding is handled directly by the code 122 164 embedded in the function. Usually, the stack-frame size is known statically 123 based on parameter and local variable declarations. 165 based on parameter and local variable declarations. For dynamically-sized 124 166 local variables, a runtime computation is necessary to know the frame 125 167 size. Finally, a function's frame-size may change during execution as local … … 179 221 180 222 To use libunwind, each function must have a personality function and a Language 181 Specific Data Area (LSDA). 223 Specific Data Area (LSDA). The LSDA has the unique information for each 182 224 function to tell the personality function where a function is executing, its 183 current stack frame, and what handlers should be checked. 225 current stack frame, and what handlers should be checked. Theoretically, the 184 226 LSDA can contain any information but conventionally it is a table with entries 185 227 representing regions of the function and what has to be done there during … … 196 238 197 239 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 240 attaches its personality function. However, this 241 flag only handles the cleanup attribute: 242 \todo{Peter: What is attached? Andrew: It uses the .cfi\_personality directive 243 and that's all I know.} 200 244 \begin{cfa} 201 245 void clean_up( int * var ) { ... } 202 int avar __attribute__(( __cleanup(clean_up) ));246 int avar __attribute__(( cleanup(clean_up) )); 203 247 \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. 248 which is used on a variable and specifies a function, in this case @clean_up@, 249 run when the variable goes out of scope. 250 The function is passed a pointer to the object being removed from the stack 251 so it can be used to mimic destructors. 252 However, this feature cannot be used to mimic @try@ statements as it cannot 253 control the unwinding. 208 254 209 255 \subsection{Personality Functions} 210 Personality functions have a complex interface specified by libunwind. 256 Personality functions have a complex interface specified by libunwind. This 211 257 section covers some of the important parts of the interface. 212 258 213 A personality function performs four tasks, although not all have to be214 present.259 A personality function can preform different actions depending on how it is 260 called. 215 261 \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] 216 262 typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) ( … … 225 271 \item 226 272 @_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function 227 to check for handlers. 273 to check for handlers. If there is a handler in a stack frame, as defined by 228 274 the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise 229 275 it return @_URC_CONTINUE_UNWIND@. … … 296 342 \end{cfa} 297 343 It also unwinds the stack but it does not use the search phase. Instead another 298 function, the stop function, is used to stop searching. 344 function, the stop function, is used to stop searching. The exception is the 299 345 same as the one passed to raise exception. The extra arguments are the stop 300 346 function and the stop parameter. The stop function has a similar interface as a … … 318 364 319 365 \begin{sloppypar} 320 Its arguments are the same as the paired personality function. 366 Its arguments are the same as the paired personality function. The actions 321 367 @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is 322 368 called. Beyond the libunwind standard, both GCC and Clang add an extra action … … 343 389 strong symbol replacing the sequential version. 344 390 345 % The version of the function defined in @libcfa@ is very simple. It returns a 346 % pointer to a global static variable. With only one stack this global instance 347 % is associated with the only stack. 348 349 For coroutines, @this_exception_context@ accesses the exception context stored 350 at the base of the stack. For threads, @this_exception_context@ uses the 351 concurrency library to access the current stack of the thread or coroutine 352 being executed by the thread, and then accesses the exception context stored at 353 the base of this stack. 391 The sequential @this_exception_context@ returns a hard-coded pointer to the 392 global execption context. 393 The concurrent version adds the exception context to the data stored at the 394 base of each stack. When @this_exception_context@ is called it retrieves the 395 active stack and returns the address of the context saved there. 354 396 355 397 \section{Termination} … … 369 411 per-exception storage. 370 412 371 Exceptions are stored in variable-sized blocks. \PAB{Show a memory layout 372 figure.} The first component is a fixed sized data structure that contains the 413 [Quick ASCII diagram to get started.] 414 \begin{verbatim} 415 Fixed Header | _Unwind_Exception <- pointer target 416 | 417 | Cforall storage 418 | 419 Variable Body | the exception <- fixed offset 420 V ... 421 \end{verbatim} 422 423 Exceptions are stored in variable-sized blocks. 424 The first component is a fixed sized data structure that contains the 373 425 information for libunwind and the exception system. The second component is an 374 426 area of memory big enough to store the exception. Macros with pointer arthritic … … 388 440 exception type. The size and copy function are used immediately to copy an 389 441 exception into managed memory. After the exception is handled the free function 390 is used to clean up the exception and then the entire node is passed to free. 442 is used to clean up the exception and then the entire node is passed to free 443 so the memory can be given back to the heap. 391 444 392 445 \subsection{Try Statements and Catch Clauses} … … 399 452 library. The contents of a try block and the termination handlers are converted 400 453 into functions. These are then passed to the try terminate function and it 401 calls them. This approach puts a try statement in its own functions so that no 402 function has to deal with both termination handlers and destructors. \PAB{I do 403 not understand the previous sentence.} 404 405 This function has some custom embedded assembly that defines \emph{its} 406 personality function and LSDA. The assembly is created with handcrafted C @asm@ 407 statements, which is why there is only one version of it. The personality 408 function is structured so that it can be expanded, but currently it only 409 handles this one function. Notably, it does not handle any destructors so the 410 function is constructed so that it does need to run it. \PAB{I do not 411 understand the previous sentence.} 454 calls them. 455 Because this function is known and fixed (and not an arbitrary function that 456 happens to contain a try statement) this means the LSDA can be generated ahead 457 of time. 458 459 Both the LSDA and the personality function are set ahead of time using 460 embedded assembly. This is handcrafted using C @asm@ statements and contains 461 enough information for the single try statement the function repersents. 412 462 413 463 The three functions passed to try terminate are: … … 419 469 420 470 \item[match function:] This function is called during the search phase and 421 decides if a catch clause matches the termination exception. 471 decides if a catch clause matches the termination exception. It is constructed 422 472 from the conditional part of each handler and runs each check, top to bottom, 423 473 in turn, first checking to see if the exception type matches and then if the … … 428 478 \item[handler function:] This function handles the exception. It takes a 429 479 pointer to the exception and the handler's id and returns nothing. It is called 430 after the cleanup phase. 480 after the cleanup phase. It is constructed by stitching together the bodies of 431 481 each handler and dispatches to the selected handler. 432 482 \end{description} … … 434 484 can be used to create closures, functions that can refer to the state of other 435 485 functions on the stack. This approach allows the functions to refer to all the 436 variables in scope for the function containing the @try@ statement. 486 variables in scope for the function containing the @try@ statement. These 437 487 nested functions and all other functions besides @__cfaehm_try_terminate@ in 438 488 \CFA use the GCC personality function and the @-fexceptions@ flag to generate … … 455 505 handler that matches. If no handler matches then the function returns 456 506 false. Otherwise the matching handler is run; if it completes successfully, the 457 function returns true. Re resume, through the @throwResume;@ statement, cause458 the function to return true.507 function returns true. Rethrowing, through the @throwResume;@ statement, 508 causes the function to return true. 459 509 460 510 % Recursive Resumption Stuff: … … 482 532 providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way 483 533 to return from a libunwind search without installing a handler or raising an 484 error. 534 error. Although workarounds might be possible, they are beyond the scope of 485 535 this thesis. The current resumption implementation has simplicity in its 486 536 favour. … … 503 553 504 554 Cancellation also uses libunwind to do its stack traversal and unwinding, 505 however it uses a different primary function @_Unwind_ForcedUnwind@. 555 however it uses a different primary function @_Unwind_ForcedUnwind@. Details 506 556 of its interface can be found in the \VRef{s:ForcedUnwind}. 507 557 … … 511 561 its main coroutine and the coroutine it is currently executing. 512 562 513 The first check is if the current thread's main and current coroutine do not 514 match, implying a coroutine cancellation; otherwise, it is a thread 515 cancellation. Otherwise it is a main thread cancellation. \PAB{Previous 516 sentence does not make sense.} 563 So if the active thread's main and current coroutine are the same. If they 564 are then the current stack is a thread stack, otherwise it is a coroutine 565 stack. If it is a thread stack then an equality check with the stored main 566 thread pointer and current thread pointer is enough to tell if the current 567 thread is the main thread or not. 517 568 518 569 However, if the threading library is not linked, the sequential execution is on
Note: See TracChangeset
for help on using the changeset viewer.