[26ca815] | 1 | \chapter{Implementation} |
---|
| 2 | % Goes over how all the features are implemented. |
---|
| 3 | |
---|
[7eb6eb5] | 4 | The implementation work for this thesis covers two components: the virtual |
---|
| 5 | system and exceptions. Each component is discussed in detail. |
---|
| 6 | |
---|
[26ca815] | 7 | \section{Virtual System} |
---|
[7eb6eb5] | 8 | \label{s:VirtualSystem} |
---|
[26ca815] | 9 | % Virtual table rules. Virtual tables, the pointer to them and the cast. |
---|
[7eb6eb5] | 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. |
---|
[26ca815] | 37 | The parent field is initialized by getting the type of the parent field and |
---|
| 38 | using that to calculate the mangled name of the parent's virtual table type. |
---|
| 39 | There are two special fields that are included like normal fields but have |
---|
[f28fdee] | 40 | special initialization rules: the @size@ field is the type's size and is |
---|
[7eb6eb5] | 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} |
---|
[26ca815] | 55 | The declarations include the virtual type definition and forward declarations |
---|
| 56 | of the virtual table instance, constructor, message function and |
---|
[7eb6eb5] | 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} |
---|
[26ca815] | 60 | |
---|
| 61 | Monomorphic instances put all of these two groups in one place each. |
---|
[7eb6eb5] | 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. |
---|
[26ca815] | 66 | |
---|
[7eb6eb5] | 67 | \begin{sloppypar} |
---|
[f28fdee] | 68 | Coroutines and threads need instances of @CoroutineCancelled@ and |
---|
[7eb6eb5] | 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} |
---|
[26ca815] | 74 | |
---|
| 75 | \subsection{Virtual Cast} |
---|
[7eb6eb5] | 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 | |
---|
[26ca815] | 107 | |
---|
| 108 | \section{Exceptions} |
---|
| 109 | % Anything about exception construction. |
---|
| 110 | |
---|
| 111 | \section{Unwinding} |
---|
| 112 | % Adapt the unwind chapter, just describe the sections of libunwind used. |
---|
| 113 | % Mention that termination and cancellation use it. Maybe go into why |
---|
| 114 | % resumption doesn't as well. |
---|
| 115 | |
---|
[7eb6eb5] | 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 | ); |
---|
[26ca815] | 222 | \end{lstlisting} |
---|
[7eb6eb5] | 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 |
---|
[26ca815] | 263 | that can be passed several places in libunwind. It includes a number of |
---|
| 264 | messages for special cases (some of which should never be used by the |
---|
| 265 | personality function) and error codes but unless otherwise noted the |
---|
[f28fdee] | 266 | personality function should always return @_URC_CONTINUE_UNWIND@. |
---|
[26ca815] | 267 | |
---|
| 268 | \subsection{Raise Exception} |
---|
[7eb6eb5] | 269 | Raising an exception is the central function of libunwind and it performs a |
---|
| 270 | two-staged unwinding. |
---|
| 271 | \begin{cfa} |
---|
[26ca815] | 272 | _Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *); |
---|
[7eb6eb5] | 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 | |
---|
[1c1c180] | 280 | Second, when a handler is matched, raise exception continues onto the cleanup |
---|
| 281 | phase. |
---|
[7eb6eb5] | 282 | Once again, it calls the personality functions of each stack frame from newest |
---|
| 283 | to oldest. This pass stops at the stack frame containing the matching handler. |
---|
| 284 | If that personality function has not install a handler, it is an error. |
---|
| 285 | |
---|
| 286 | If an error is encountered, raise exception returns either |
---|
| 287 | @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the |
---|
| 288 | error occurred. |
---|
[26ca815] | 289 | |
---|
| 290 | \subsection{Forced Unwind} |
---|
[7eb6eb5] | 291 | \label{s:ForcedUnwind} |
---|
| 292 | Forced Unwind is the other central function in libunwind. |
---|
| 293 | \begin{cfa} |
---|
| 294 | _Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *, |
---|
| 295 | _Unwind_Stop_Fn, void *); |
---|
| 296 | \end{cfa} |
---|
| 297 | 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. The exception is the |
---|
| 299 | same as the one passed to raise exception. The extra arguments are the stop |
---|
| 300 | function and the stop parameter. The stop function has a similar interface as a |
---|
| 301 | personality function, except it is also passed the stop parameter. |
---|
| 302 | \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] |
---|
| 303 | typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)( |
---|
| 304 | _Unwind_Action @action@, |
---|
| 305 | _Unwind_Exception_Class @exception_class@, |
---|
| 306 | _Unwind_Exception * @exception@, |
---|
| 307 | struct _Unwind_Context * @context@, |
---|
| 308 | void * @stop_parameter@); |
---|
[26ca815] | 309 | \end{lstlisting} |
---|
| 310 | |
---|
| 311 | The stop function is called at every stack frame before the personality |
---|
[7eb6eb5] | 312 | function is called and then once more after all frames of the stack are |
---|
| 313 | unwound. |
---|
[26ca815] | 314 | |
---|
[7eb6eb5] | 315 | Each time it is called, the stop function should return @_URC_NO_REASON@ or |
---|
| 316 | transfer control directly to other code outside of libunwind. The framework |
---|
| 317 | does not provide any assistance here. |
---|
[26ca815] | 318 | |
---|
[7eb6eb5] | 319 | \begin{sloppypar} |
---|
| 320 | Its arguments are the same as the paired personality function. The actions |
---|
| 321 | @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is |
---|
| 322 | called. Beyond the libunwind standard, both GCC and Clang add an extra action |
---|
| 323 | on the last call at the end of the stack: @_UA_END_OF_STACK@. |
---|
| 324 | \end{sloppypar} |
---|
[26ca815] | 325 | |
---|
| 326 | \section{Exception Context} |
---|
| 327 | % Should I have another independent section? |
---|
| 328 | % There are only two things in it, top_resume and current_exception. How it is |
---|
[7eb6eb5] | 329 | % stored changes depending on whether or not the thread-library is linked. |
---|
| 330 | |
---|
| 331 | The exception context is global storage used to maintain data across different |
---|
| 332 | exception operations and to communicate among different components. |
---|
| 333 | |
---|
| 334 | Each stack must have its own exception context. In a sequential \CFA program, |
---|
| 335 | there is only one stack with a single global exception-context. However, when |
---|
| 336 | the library @libcfathread@ is linked, there are multiple stacks where each |
---|
| 337 | needs its own exception context. |
---|
| 338 | |
---|
| 339 | General access to the exception context is provided by function |
---|
| 340 | @this_exception_context@. For sequential execution, this function is defined as |
---|
| 341 | a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is |
---|
| 342 | concurrent, it links with @libcfathread@, where this function is defined with a |
---|
| 343 | strong symbol replacing the sequential version. |
---|
| 344 | |
---|
| 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. |
---|
[26ca815] | 354 | |
---|
| 355 | \section{Termination} |
---|
| 356 | % Memory management & extra information, the custom function used to implement |
---|
| 357 | % catches. Talk about GCC nested functions. |
---|
| 358 | |
---|
[7eb6eb5] | 359 | Termination exceptions use libunwind heavily because it matches the intended |
---|
| 360 | use from \CC exceptions closely. The main complication for \CFA is that the |
---|
| 361 | compiler generates C code, making it very difficult to generate the assembly to |
---|
| 362 | form the LSDA for try blocks or destructors. |
---|
[26ca815] | 363 | |
---|
| 364 | \subsection{Memory Management} |
---|
[7eb6eb5] | 365 | The first step of a termination raise is to copy the exception into memory |
---|
| 366 | managed by the exception system. Currently, the system uses @malloc@, rather |
---|
| 367 | than reserved memory or the stack top. The exception handling mechanism manages |
---|
| 368 | memory for the exception as well as memory for libunwind and the system's own |
---|
| 369 | per-exception storage. |
---|
| 370 | |
---|
| 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 |
---|
| 373 | information for libunwind and the exception system. The second component is an |
---|
| 374 | area of memory big enough to store the exception. Macros with pointer arthritic |
---|
| 375 | and type cast are used to move between the components or go from the embedded |
---|
[f28fdee] | 376 | @_Unwind_Exception@ to the entire node. |
---|
[26ca815] | 377 | |
---|
[7eb6eb5] | 378 | All of these nodes are linked together in a list, one list per stack, with the |
---|
| 379 | list head stored in the exception context. Within each linked list, the most |
---|
| 380 | recently thrown exception is at the head followed by older thrown |
---|
| 381 | exceptions. This format allows exceptions to be thrown, while a different |
---|
| 382 | exception is being handled. The exception at the head of the list is currently |
---|
| 383 | being handled, while other exceptions wait for the exceptions before them to be |
---|
| 384 | removed. |
---|
| 385 | |
---|
| 386 | The virtual members in the exception's virtual table provide the size of the |
---|
| 387 | exception, the copy function, and the free function, so they are specific to an |
---|
| 388 | exception type. The size and copy function are used immediately to copy an |
---|
| 389 | 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. |
---|
| 391 | |
---|
| 392 | \subsection{Try Statements and Catch Clauses} |
---|
| 393 | The try statement with termination handlers is complex because it must |
---|
| 394 | compensate for the lack of assembly-code generated from \CFA. Libunwind |
---|
| 395 | requires an LSDA and personality function for control to unwind across a |
---|
| 396 | function. The LSDA in particular is hard to mimic in generated C code. |
---|
| 397 | |
---|
| 398 | The workaround is a function called @__cfaehm_try_terminate@ in the standard |
---|
| 399 | library. The contents of a try block and the termination handlers are converted |
---|
| 400 | 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.} |
---|
[26ca815] | 412 | |
---|
| 413 | The three functions passed to try terminate are: |
---|
[7eb6eb5] | 414 | \begin{description} |
---|
| 415 | \item[try function:] This function is the try block, all the code inside the |
---|
| 416 | try block is placed inside the try function. It takes no parameters and has no |
---|
| 417 | return value. This function is called during regular execution to run the try |
---|
| 418 | block. |
---|
| 419 | |
---|
| 420 | \item[match function:] This function is called during the search phase and |
---|
| 421 | decides if a catch clause matches the termination exception. It is constructed |
---|
| 422 | from the conditional part of each handler and runs each check, top to bottom, |
---|
| 423 | in turn, first checking to see if the exception type matches and then if the |
---|
| 424 | condition is true. It takes a pointer to the exception and returns 0 if the |
---|
| 425 | exception is not handled here. Otherwise the return value is the id of the |
---|
| 426 | handler that matches the exception. |
---|
| 427 | |
---|
| 428 | \item[handler function:] This function handles the exception. It takes a |
---|
| 429 | pointer to the exception and the handler's id and returns nothing. It is called |
---|
| 430 | after the cleanup phase. It is constructed by stitching together the bodies of |
---|
| 431 | each handler and dispatches to the selected handler. |
---|
| 432 | \end{description} |
---|
| 433 | All three functions are created with GCC nested functions. GCC nested functions |
---|
| 434 | can be used to create closures, functions that can refer to the state of other |
---|
| 435 | 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. These |
---|
| 437 | nested functions and all other functions besides @__cfaehm_try_terminate@ in |
---|
| 438 | \CFA use the GCC personality function and the @-fexceptions@ flag to generate |
---|
| 439 | the LSDA. This allows destructors to be implemented with the cleanup attribute. |
---|
[26ca815] | 440 | |
---|
| 441 | \section{Resumption} |
---|
| 442 | % The stack-local data, the linked list of nodes. |
---|
| 443 | |
---|
[7eb6eb5] | 444 | Resumption simple to implement because there is no stack unwinding. The |
---|
| 445 | resumption raise uses a list of nodes for its stack traversal. The head of the |
---|
| 446 | list is stored in the exception context. The nodes in the list have a pointer |
---|
[26ca815] | 447 | to the next node and a pointer to the handler function. |
---|
| 448 | |
---|
[7eb6eb5] | 449 | A resumption raise traverses this list. At each node the handler function is |
---|
| 450 | called, passing the exception by pointer. It returns true if the exception is |
---|
| 451 | handled and false otherwise. |
---|
[26ca815] | 452 | |
---|
[7eb6eb5] | 453 | The handler function does both the matching and handling. It computes the |
---|
| 454 | condition of each @catchResume@ in top-to-bottom order, until it finds a |
---|
| 455 | handler that matches. If no handler matches then the function returns |
---|
| 456 | false. Otherwise the matching handler is run; if it completes successfully, the |
---|
| 457 | function returns true. Reresume, through the @throwResume;@ statement, cause |
---|
| 458 | the function to return true. |
---|
[26ca815] | 459 | |
---|
[12b4ab4] | 460 | % Recursive Resumption Stuff: |
---|
[7eb6eb5] | 461 | Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack |
---|
| 462 | already examined, is accomplished by updating the front of the list as the |
---|
| 463 | search continues. Before the handler at a node is called the head of the list |
---|
| 464 | is updated to the next node of the current node. After the search is complete, |
---|
| 465 | successful or not, the head of the list is reset. |
---|
[12b4ab4] | 466 | |
---|
[7eb6eb5] | 467 | This mechanism means the current handler and every handler that has already |
---|
| 468 | been checked are not on the list while a handler is run. If a resumption is |
---|
| 469 | thrown during the handling of another resumption the active handlers and all |
---|
| 470 | the other handler checked up to this point are not checked again. |
---|
[12b4ab4] | 471 | |
---|
| 472 | This structure also supports new handler added while the resumption is being |
---|
| 473 | handled. These are added to the front of the list, pointing back along the |
---|
[7eb6eb5] | 474 | stack -- the first one points over all the checked handlers -- and the ordering |
---|
| 475 | is maintained. |
---|
| 476 | |
---|
| 477 | \label{p:zero-cost} |
---|
| 478 | Note, the resumption implementation has a cost for entering/exiting a @try@ |
---|
| 479 | statement with @catchResume@ clauses, whereas a @try@ statement with @catch@ |
---|
| 480 | clauses has zero-cost entry/exit. While resumption does not need the stack |
---|
| 481 | unwinding and cleanup provided by libunwind, it could use the search phase to |
---|
| 482 | providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way |
---|
| 483 | to return from a libunwind search without installing a handler or raising an |
---|
| 484 | error. Although workarounds might be possible, they are beyond the scope of |
---|
| 485 | this thesis. The current resumption implementation has simplicity in its |
---|
| 486 | favour. |
---|
[26ca815] | 487 | % Seriously, just compare the size of the two chapters and then consider |
---|
| 488 | % that unwind is required knowledge for that chapter. |
---|
| 489 | |
---|
| 490 | \section{Finally} |
---|
| 491 | % Uses destructors and GCC nested functions. |
---|
[7eb6eb5] | 492 | Finally clauses is placed into a GCC nested-function with a unique name, and no |
---|
| 493 | arguments or return values. This nested function is then set as the cleanup |
---|
| 494 | function of an empty object that is declared at the beginning of a block placed |
---|
| 495 | around the context of the associated @try@ statement. |
---|
[26ca815] | 496 | |
---|
| 497 | The rest is handled by GCC. The try block and all handlers are inside the |
---|
[7eb6eb5] | 498 | block. At completion, control exits the block and the empty object is cleaned |
---|
| 499 | up, which runs the function that contains the finally code. |
---|
[26ca815] | 500 | |
---|
| 501 | \section{Cancellation} |
---|
| 502 | % Stack selections, the three internal unwind functions. |
---|
| 503 | |
---|
| 504 | Cancellation also uses libunwind to do its stack traversal and unwinding, |
---|
[7eb6eb5] | 505 | however it uses a different primary function @_Unwind_ForcedUnwind@. Details |
---|
| 506 | of its interface can be found in the \VRef{s:ForcedUnwind}. |
---|
[26ca815] | 507 | |
---|
[7eb6eb5] | 508 | The first step of cancellation is to find the cancelled stack and its type: |
---|
| 509 | coroutine or thread. Fortunately, the thread library stores the main thread |
---|
| 510 | pointer and the current thread pointer, and every thread stores a pointer to |
---|
[26ca815] | 511 | its main coroutine and the coroutine it is currently executing. |
---|
| 512 | |
---|
[7eb6eb5] | 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.} |
---|
| 517 | |
---|
| 518 | However, if the threading library is not linked, the sequential execution is on |
---|
| 519 | the main stack. Hence, the entire check is skipped because the weak-symbol |
---|
| 520 | function is loaded. Therefore, a main thread cancellation is unconditionally |
---|
| 521 | performed. |
---|
| 522 | |
---|
| 523 | Regardless of how the stack is chosen, the stop function and parameter are |
---|
| 524 | passed to the forced-unwind function. The general pattern of all three stop |
---|
| 525 | functions is the same: they continue unwinding until the end of stack when they |
---|
| 526 | do there primary work. |
---|
| 527 | |
---|
| 528 | For main stack cancellation, the transfer is just a program abort. |
---|
| 529 | |
---|
| 530 | For coroutine cancellation, the exception is stored on the coroutine's stack, |
---|
| 531 | and the coroutine context switches to its last resumer. The rest is handled on |
---|
| 532 | the backside of the resume, which check if the resumed coroutine is |
---|
| 533 | cancelled. If cancelled, the exception is retrieved from the resumed coroutine, |
---|
| 534 | and a @CoroutineCancelled@ exception is constructed and loaded with the |
---|
| 535 | cancelled exception. It is then resumed as a regular exception with the default |
---|
| 536 | handler coming from the context of the resumption call. |
---|
| 537 | |
---|
| 538 | For thread cancellation, the exception is stored on the thread's main stack and |
---|
| 539 | then context switched to the scheduler. The rest is handled by the thread |
---|
| 540 | joiner. When the join is complete, the joiner checks if the joined thread is |
---|
| 541 | cancelled. If cancelled, the exception is retrieved and the joined thread, and |
---|
| 542 | a @ThreadCancelled@ exception is constructed and loaded with the cancelled |
---|
| 543 | exception. The default handler is passed in as a function pointer. If it is |
---|
| 544 | null (as it is for the auto-generated joins on destructor call), the default is |
---|
| 545 | used, which is a program abort. |
---|
| 546 | %; which gives the required handling on implicate join. |
---|