Changeset e56eabac
- Timestamp:
- Aug 20, 2021, 9:13:14 AM (3 years ago)
- Branches:
- ADT, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, pthread-emulation, qualifiedEnum
- Children:
- d249e0b, d8f8d08
- Parents:
- 32b7f54
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/implement.tex
r32b7f54 re56eabac 20 20 21 21 \subsection{Virtual Type} 22 Virtual types only have one change to their structure: the addition of a 23 pointer to the virtual table, which is called the \emph{virtual-table pointer}. 24 Internally, the field is called \snake{virtual_table}. 25 The field is fixed after construction. It is always the first field in the 26 structure so that its location is always known. 22 A virtual type~(see \autoref{s:Virtuals}) has a pointer to a virtual table, 23 called the \emph{virtual-table pointer}, which binds an instance of a virtual 24 type to a virtual table. Internally, the field is called \snake{virtual_table} 25 and is fixed after construction. This pointer is also the table's id and how 26 the system accesses the virtual table and the virtual members there. It is 27 always the first field in the structure so that its location is always known. 27 28 \todo{Talk about constructors for virtual types (after they are working).} 28 29 29 The virtual table pointer binds an instance of a virtual type30 to a virtual table.31 The pointer is also the table's id and how the system accesses the32 virtual table and the virtual members there.33 34 30 \subsection{Type Id} 35 Every virtual type has a unique id. 36 Type ids can be compared for equality, 37 which checks if the types reperented are the same, 38 or used to access the type's type information. 31 Every virtual type needs a unique id, so that type ids can be compared for 32 equality, which checks if the types representation are the same, or used to 33 access the type's type information. Here, uniqueness means within a program 34 composed of multiple translation units (TU), not uniqueness across all 35 programs. 36 37 One approach for program uniqueness is declaring a static declaration for each 38 type id, where the runtime storage address of that variable is guaranteed to be 39 unique during program execution. The type id storage can also be used for other 40 purposes. 41 42 The problem is that a type id may appear in multiple TUs that compose a 43 program, see \autoref{ss:VirtualTable}; hence in each TU, it must be declared 44 as external to prevent multiple definitions. However, the type id must actually 45 be declared in one of the TUs so the linker creates the storage. Hence, the 46 problem becomes designating one TU to insert an actual type-id declaration. But 47 the \CFA compiler does not know the set of the translation units that compose a 48 program, because TUs can be compile separately, followed by a separate link 49 step. 50 51 The solution is to mimic a \CFA feature in \Cpp{17}, @inline@ variables and 52 function: 53 \begin{quote} 54 There may be more than one definition of an inline function or variable (since 55 \Cpp{17} in the program as long as each definition appears in a different 56 translation unit and (for non-static inline functions and variables (since 57 \Cpp{17})) all definitions are identical. For example, an inline function or an 58 inline variable (since \Cpp{17}) may be defined in a header file that is 59 @#include@'d in multiple source files.~\cite{C++17} 60 \end{quote} 61 The underlying mechanism to provide this capability is attribute 62 \begin{cfa} 63 section(".gnu.linkonce.NAME") 64 \end{cfa} 65 where @NAME@ is the variable/function name duplicated in each TU. The linker than 66 provides the service of generating a single declaration (instance) across all 67 TUs, even if a program is linked incrementally. 68 69 C does not support this feature for @inline@, and hence, neither does \CFA. 70 Again, rather than implement a new @inline@ extension for \CFA, a temporary 71 solution for the exception handling is to add the following in \CFA. 72 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}] 73 @__attribute__((cfa_linkonce))@ void f() {} 74 \end{lstlisting} 75 which becomes 76 \begin{lstlisting}[language=CFA,{moredelim=**[is][\color{red}]{@}{@}}] 77 __attribute__((section(".gnu.linkonce._X1fFv___1"))) void @_X1fFv___1@(){} 78 \end{lstlisting} 79 where @NAME@ from above is the \CFA mangled variable/function name. Note, 80 adding this feature is necessary because, when using macros, the mangled name 81 is unavailable. This attribute is useful for purposes other than exception 82 handling, and should eventually be rolled into @inline@ processing in \CFA. 83 84 Finally, a type id's data implements a pointers to the type's type information 85 instance. Dereferencing the pointer gets the type information. 86 87 \subsection{Implementation} 88 39 89 The type information currently is only the parent's type id or, if the 40 90 type has no parent, the null pointer. 41 42 The id's are implemented as pointers to the type's type information instance.43 Dereferencing the pointer gets the type information.44 91 The ancestors of a virtual type are found by traversing type ids through 45 92 the type information. 46 The information pushes the issue of creating a unique value (for 47 the type id) to the problem of creating a unique instance (for type 48 information), which the linker can solve. 49 50 The advanced linker support is used here to avoid having to create 51 a new declaration to attach this data to. 52 With C/\CFA's header/implementation file divide for something to appear 53 exactly once it must come from a declaration that appears in exactly one 54 implementation file; the declarations in header files may exist only once 55 they can be included in many different translation units. 56 Therefore, structure's declaration will not work. 57 Neither will attaching the type information to the virtual table -- although 58 a vtable declarations are in implemention files they are not unique, see 59 \autoref{ss:VirtualTable}. 60 Instead the same type information is generated multiple times and then 61 the new attribute \snake{cfa_linkone} is used to removed duplicates. 62 63 Type information is constructed as follows: 93 An example using helper macros looks like: 94 \begin{cfa} 95 struct INFO_TYPE(TYPE) { 96 INFO_TYPE(PARENT) const * parent; 97 }; 98 99 __attribute__((cfa_linkonce)) 100 INFO_TYPE(TYPE) const INFO_NAME(TYPE) = { 101 &INFO_NAME(PARENT), 102 }; 103 \end{cfa} 104 105 The type information is constructed as follows: 64 106 \begin{enumerate} 65 107 \item 66 Use the type's name to generate a name for the type information structure .67 This is saved so it maybe reused.108 Use the type's name to generate a name for the type information structure, 109 which is saved so it can be reused. 68 110 \item 69 111 Generate a new structure definition to store the type 70 112 information. The layout is the same in each case, just the parent's type id, 71 113 but the types used change from instance to instance. 72 The generated name is used for both this structure and, if rel ivant, the114 The generated name is used for both this structure and, if relevant, the 73 115 parent pointer. 74 116 If the virtual type is polymorphic then the type information structure is 75 117 polymorphic as well, with the same polymorphic arguments. 76 118 \item 77 A sep erate name for instances is generated from the type's name.119 A separate name for instances is generated from the type's name. 78 120 \item 79 The definition is generated and initiali sed.121 The definition is generated and initialized. 80 122 The parent id is set to the null pointer or to the address of the parent's 81 123 type information instance. Name resolution handles the rest. 82 124 \item 83 125 \CFA's name mangler does its regular name mangling encoding the type of 84 the declaration into the instance name. This gives a completelyunique name126 the declaration into the instance name. This process gives a program unique name 85 127 including different instances of the same polymorphic type. 86 128 \end{enumerate} 87 \todo{The list is making me realise, some of this isn't ordered.} 88 89 Writing that code manually, with helper macros for the early name mangling, 90 would look like this: 91 \begin{cfa} 92 struct INFO_TYPE(TYPE) { 93 INFO_TYPE(PARENT) const * parent; 94 }; 95 96 __attribute__((cfa_linkonce)) 97 INFO_TYPE(TYPE) const INFO_NAME(TYPE) = { 98 &INFO_NAME(PARENT), 99 }; 100 \end{cfa} 101 129 \todo{The list is making me realize, some of this isn't ordered.} 130 131 132 \begin{comment} 102 133 \subsubsection{\lstinline{cfa\_linkonce} Attribute} 103 % I just reali sed: This is an extension of the inline keyword.134 % I just realized: This is an extension of the inline keyword. 104 135 % An extension of C's at least, it is very similar to C++'s. 105 136 Another feature added to \CFA is a new attribute: \texttt{cfa\_linkonce}. … … 126 157 everything that comes after the special prefix, then only one is used 127 158 and the other is discarded. 159 \end{comment} 160 128 161 129 162 \subsection{Virtual Table} … … 158 191 The first and second sections together mean that every virtual table has a 159 192 prefix that has the same layout and types as its parent virtual table. 160 This, combined with the fixed offset to the virtual 193 This, combined with the fixed offset to the virtual-table pointer, means that 161 194 for any virtual type, it is always safe to access its virtual table and, 162 195 from there, it is safe to check the type id to identify the exact type of the … … 176 209 type's alignment, is set using an @alignof@ expression. 177 210 178 \subs ubsection{Concurrency Integration}211 \subsection{Concurrency Integration} 179 212 Coroutines and threads need instances of @CoroutineCancelled@ and 180 213 @ThreadCancelled@ respectively to use all of their functionality. When a new … … 183 216 at the definition of the main function. 184 217 185 Th is is shownedthrough code re-writing in186 \autoref{f:Co ncurrencyTypeTransformation} and187 \autoref{f:Co ncurrencyMainTransformation}.188 In both cases the original declaration is not modified,189 only new ones areadded.218 These transformations are shown through code re-writing in 219 \autoref{f:CoroutineTypeTransformation} and 220 \autoref{f:CoroutineMainTransformation} for a coroutine and a thread is similar. 221 In both cases, the original declaration is not modified, only new ones are 222 added. 190 223 191 224 \begin{figure} … … 207 240 extern CoroutineCancelled_vtable & _default_vtable; 208 241 \end{cfa} 209 \caption{Concurrency Type Transformation} 210 \label{f:ConcurrencyTypeTransformation} 211 \end{figure} 212 213 \begin{figure} 242 \caption{Coroutine Type Transformation} 243 \label{f:CoroutineTypeTransformation} 244 %\end{figure} 245 246 \bigskip 247 248 %\begin{figure} 214 249 \begin{cfa} 215 250 void main(Example & this) { … … 229 264 &_default_vtable_object_declaration; 230 265 \end{cfa} 231 \caption{Co ncurrencyMain Transformation}232 \label{f:Co ncurrencyMainTransformation}266 \caption{Coroutine Main Transformation} 267 \label{f:CoroutineMainTransformation} 233 268 \end{figure} 234 269 … … 245 280 struct __cfavir_type_id const * child ); 246 281 \end{cfa} 247 The type id oftarget type of the virtual cast is passed in as @parent@ and282 The type id for the target type of the virtual cast is passed in as @parent@ and 248 283 the cast target is passed in as @child@. 249 250 For generated C code wraps both arguments and the result with type casts. 284 The generated C code wraps both arguments and the result with type casts. 251 285 There is also an internal check inside the compiler to make sure that the 252 286 target type is a virtual type. … … 260 294 261 295 \section{Exceptions} 262 % Anything about exception construction. 296 \todo{Anything about exception construction.} 263 297 264 298 \section{Unwinding} … … 274 308 stack. On function entry and return, unwinding is handled directly by the 275 309 call/return code embedded in the function. 276 In many cases, the position of the instruction pointer (relative to parameter310 \PAB{Meaning: In many cases, the position of the instruction pointer (relative to parameter 277 311 and local declarations) is enough to know the current size of the stack 278 frame. 312 frame.} 279 313 280 314 Usually, the stack-frame size is known statically based on parameter and 281 local variable declarations. Even withdynamic stack-size, the information315 local variable declarations. Even for a dynamic stack-size, the information 282 316 to determine how much of the stack has to be removed is still contained 283 317 within the function. … … 285 319 bumping the hardware stack-pointer up or down as needed. 286 320 Constructing/destructing values within a stack frame has 287 a similar complexity but can add additional work and takelonger.321 a similar complexity but larger constants, which takes longer. 288 322 289 323 Unwinding across multiple stack frames is more complex because that 290 324 information is no longer contained within the current function. 291 With seperate compilation a function has no way of knowing what its callers 292 are so it can't know how large those frames are. 325 With separate compilation a function does not know its callers nor their frame size. 326 In general, the caller's frame size is embedded only at the functions entry (push 327 stack) and exit (pop stack). 293 328 Without altering the main code path it is also hard to pass that work off 294 329 to the caller. … … 302 337 This approach is fragile and requires extra work in the surrounding code. 303 338 304 With respect to the extra work in the sur ounding code,339 With respect to the extra work in the surrounding code, 305 340 many languages define clean-up actions that must be taken when certain 306 341 sections of the stack are removed. Such as when the storage for a variable 307 is removed from the stack or when a try statement with a finally clause is342 is removed from the stack (destructor call) or when a try statement with a finally clause is 308 343 (conceptually) popped from the stack. 309 None of these should be handled by the user --- that would contradict the344 None of these cases should be handled by the user --- that would contradict the 310 345 intention of these features --- so they need to be handled automatically. 311 346 … … 355 390 in this case @clean_up@, run when the variable goes out of scope. 356 391 This feature is enough to mimic destructors, 357 but not try statements which can effect392 but not try statements that affect 358 393 the unwinding. 359 394 360 395 To get full unwinding support, all of these features must be handled directly 361 in assembly and assembler directives; parti ularly the cfi directives396 in assembly and assembler directives; particularly the cfi directives 362 397 \snake{.cfi_lsda} and \snake{.cfi_personality}. 363 398 … … 399 434 @_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs 400 435 the cleanup phase and uses a different means to decide when to stop 401 (see \ vref{s:ForcedUnwind}).436 (see \autoref{s:ForcedUnwind}). 402 437 \end{enumerate} 403 438 404 439 The @exception_class@ argument is a copy of the 405 440 \code{C}{exception}'s @exception_class@ field, 406 which is a number that identifies the exception handling mechanism441 which is a number that identifies the EHM 407 442 that created the exception. 408 443 … … 494 529 needs its own exception context. 495 530 496 The exception context should beretrieved by calling the function531 An exception context is retrieved by calling the function 497 532 \snake{this_exception_context}. 498 533 For sequential execution, this function is defined as … … 519 554 The first step of a termination raise is to copy the exception into memory 520 555 managed by the exception system. Currently, the system uses @malloc@, rather 521 than reserved memory or the stack top. The exception handling mechanismmanages556 than reserved memory or the stack top. The EHM manages 522 557 memory for the exception as well as memory for libunwind and the system's own 523 558 per-exception storage. … … 618 653 \subsection{Try Statements and Catch Clauses} 619 654 The try statement with termination handlers is complex because it must 620 compensate for the C code-generation versus 655 compensate for the C code-generation versus proper 621 656 assembly-code generated from \CFA. Libunwind 622 657 requires an LSDA and personality function for control to unwind across a … … 624 659 625 660 The workaround is a function called @__cfaehm_try_terminate@ in the standard 626 library. The contents of a try block and the termination handlers are converted627 into functions. These are then passed to the try terminate function and it628 calls them .661 \CFA library. The contents of a try block and the termination handlers are converted 662 into nested functions. These are then passed to the try terminate function and it 663 calls them, appropriately. 629 664 Because this function is known and fixed (and not an arbitrary function that 630 happens to contain a try statement), theLSDA can be generated ahead665 happens to contain a try statement), its LSDA can be generated ahead 631 666 of time. 632 667 633 Both the LSDA and the personality function are set ahead of time using668 Both the LSDA and the personality function for @__cfaehm_try_terminate@ are set ahead of time using 634 669 embedded assembly. This assembly code is handcrafted using C @asm@ statements 635 670 and contains 636 enough information for a single try statement the function rep ersents.671 enough information for a single try statement the function represents. 637 672 638 673 The three functions passed to try terminate are: … … 646 681 decides if a catch clause matches the termination exception. It is constructed 647 682 from the conditional part of each handler and runs each check, top to bottom, 648 in turn, first checking to see if the exception type matches and then if the 649 condition is true. It takes a pointer to the exception and returns 0 if the 683 in turn, first checking to see if the exception type matches. 684 The match is performed in two steps, first a virtual cast is used to see 685 if the raised exception is an instance of the declared exception or one of 686 its descendant type, and then is the condition true, if present. 687 It takes a pointer to the exception and returns 0 if the 650 688 exception is not handled here. Otherwise the return value is the id of the 651 689 handler that matches the exception. … … 660 698 All three functions are created with GCC nested functions. GCC nested functions 661 699 can be used to create closures, 662 in other words functions that can refer to the state ofother663 functions on the stack . This approach allows the functions to refer to all the700 in other words, functions that can refer to their lexical scope in other 701 functions on the stack when called. This approach allows the functions to refer to all the 664 702 variables in scope for the function containing the @try@ statement. These 665 703 nested functions and all other functions besides @__cfaehm_try_terminate@ in … … 669 707 670 708 \autoref{f:TerminationTransformation} shows the pattern used to transform 671 a \CFA try statement with catch clauses into the appropr ate C functions.709 a \CFA try statement with catch clauses into the appropriate C functions. 672 710 \todo{Explain the Termination Transformation figure.} 673 711 … … 738 776 Instead of storing the data in a special area using assembly, 739 777 there is just a linked list of possible handlers for each stack, 740 with each node on the list rep erenting a try statement on the stack.778 with each node on the list representing a try statement on the stack. 741 779 742 780 The head of the list is stored in the exception context. … … 744 782 to the head of the list. 745 783 Instead of traversing the stack, resumption handling traverses the list. 746 At each node, the EHM checks to see if the try statement the node rep ersents784 At each node, the EHM checks to see if the try statement the node represents 747 785 can handle the exception. If it can, then the exception is handled and 748 786 the operation finishes, otherwise the search continues to the next node. 749 787 If the search reaches the end of the list without finding a try statement 750 788 that can handle the exception, the default handler is executed and the 751 operation finishes .789 operation finishes, unless it throws an exception. 752 790 753 791 Each node has a handler function that does most of the work. 754 792 The handler function is passed the raised exception and returns true 755 793 if the exception is handled and false otherwise. 756 757 794 The handler function checks each of its internal handlers in order, 758 795 top-to-bottom, until it funds a match. If a match is found that handler is … … 760 797 If no match is found the function returns false. 761 798 The match is performed in two steps, first a virtual cast is used to see 762 if the thrown exception is an instance of the declared exception or one of 763 its descendant type, then check to see if passes the custom predicate if one 764 is defined. This ordering gives the type guarantee used in the predicate. 799 if the raised exception is an instance of the declared exception or one of 800 its descendant type, and then is the condition true, if present. 801 \PAB{I don't understand this sentence. 802 This ordering gives the type guarantee used in the predicate.} 765 803 766 804 \autoref{f:ResumptionTransformation} shows the pattern used to transform 767 a \CFA try statement with catch clauses into the appropr ate C functions.805 a \CFA try statement with catch clauses into the appropriate C functions. 768 806 \todo{Explain the Resumption Transformation figure.} 769 807 … … 814 852 (see \vpageref{s:ResumptionMarking}), which ignores parts of 815 853 the stack 816 already examined, is accomplished by updating the front of the list as the817 search continues. Before the handler at a node is called, the head of the list854 already examined, and is accomplished by updating the front of the list as the 855 search continues. Before the handler is called at a matching node, the head of the list 818 856 is updated to the next node of the current node. After the search is complete, 819 857 successful or not, the head of the list is reset. … … 822 860 been checked are not on the list while a handler is run. If a resumption is 823 861 thrown during the handling of another resumption, the active handlers and all 824 the other handler checked up to this point are not checked again.862 the other handlers checked up to this point are not checked again. 825 863 % No paragraph? 826 864 This structure also supports new handlers added while the resumption is being … … 830 868 831 869 \begin{figure} 870 \centering 832 871 \input{resumption-marking} 833 872 \caption{Resumption Marking} … … 851 890 \section{Finally} 852 891 % Uses destructors and GCC nested functions. 853 A finally clause is placed into a GCC nested-function with a unique name, 854 and no arguments or return values. 855 This nested function is then set as the cleanup 856 function of an empty object that is declared at the beginning of a block placed 857 around the context of the associated @try@ statement. 892 \autoref{f:FinallyTransformation} shows the pattern used to transform a \CFA 893 try statement with finally clause into the appropriate C functions. 894 The finally clause is placed into a GCC nested-function 895 with a unique name, and no arguments or return values. This nested function is 896 then set as the cleanup function of an empty object that is declared at the 897 beginning of a block placed around the context of the associated @try@ 898 statement. 899 900 \begin{figure} 901 \begin{cfa} 902 try { 903 // TRY BLOCK 904 } finally { 905 // FINALLY BLOCK 906 } 907 \end{cfa} 908 909 \transformline 910 911 \begin{cfa} 912 { 913 void finally(void *__hook){ 914 // FINALLY BLOCK 915 } 916 __attribute__ ((cleanup(finally))) 917 struct __cfaehm_cleanup_hook __finally_hook; 918 { 919 // TRY BLOCK 920 } 921 922 } 923 \end{cfa} 924 925 \caption{Finally Transformation} 926 \label{f:FinallyTransformation} 927 \end{figure} 858 928 859 929 The rest is handled by GCC. The try block and all handlers are inside this … … 869 939 870 940 The first step of cancellation is to find the cancelled stack and its type: 871 coroutine, thread or main thread.941 coroutine, thread, or main thread. 872 942 In \CFA, a thread (the construct the user works with) is a user-level thread 873 943 (point of execution) paired with a coroutine, the thread's main coroutine. 874 944 The thread library also stores pointers to the main thread and the current 875 thread.945 coroutine. 876 946 If the current thread's main and current coroutines are the same then the 877 947 current stack is a thread stack, otherwise it is a coroutine stack. … … 887 957 passed to the forced-unwind function. The general pattern of all three stop 888 958 functions is the same: continue unwinding until the end of stack and 889 then p reform the appropriate transfer.959 then perform the appropriate transfer. 890 960 891 961 For main stack cancellation, the transfer is just a program abort.
Note: See TracChangeset
for help on using the changeset viewer.