[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 | |
---|
[830299f] | 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 | |
---|
[7eb6eb5] | 28 | \subsection{Virtual Table} |
---|
[830299f] | 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 | |
---|
[7eb6eb5] | 46 | The virtual system is accessed through a private constant field inserted at the |
---|
| 47 | beginning of every virtual type, called the virtual-table pointer. This field |
---|
| 48 | points at a type's virtual table and is assigned during the object's |
---|
[830299f] | 49 | construction. The address of a virtual table acts as the unique identifier for |
---|
[7eb6eb5] | 50 | the virtual type, and the first field of a virtual table is a pointer to the |
---|
[830299f] | 51 | parent virtual-table or @0p@. The remaining fields are duplicated from the |
---|
[7eb6eb5] | 52 | parent tables in this type's inheritance chain, followed by any fields this type |
---|
[830299f] | 53 | introduces. Parent fields are duplicated so they can be changed (all virtual |
---|
| 54 | members are overridable), so that references to the dispatched type |
---|
[7eb6eb5] | 55 | are replaced with the current virtual type. |
---|
| 56 | % These are always taken by pointer or reference. |
---|
| 57 | |
---|
[830299f] | 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} |
---|
| 69 | |
---|
[7eb6eb5] | 70 | % For each virtual type, a virtual table is constructed. This is both a new type |
---|
| 71 | % and an instance of that type. Other instances of the type could be created |
---|
| 72 | % but the system doesn't use them. So this section will go over the creation of |
---|
| 73 | % the type and the instance. |
---|
| 74 | |
---|
| 75 | A virtual table is created when the virtual type is created. The name of the |
---|
| 76 | type is created by mangling the name of the base type. The name of the instance |
---|
[830299f] | 77 | is also generated by name mangling. The fields are initialized automatically. |
---|
[26ca815] | 78 | The parent field is initialized by getting the type of the parent field and |
---|
| 79 | using that to calculate the mangled name of the parent's virtual table type. |
---|
| 80 | There are two special fields that are included like normal fields but have |
---|
[f28fdee] | 81 | special initialization rules: the @size@ field is the type's size and is |
---|
[7eb6eb5] | 82 | initialized with a @sizeof@ expression, the @align@ field is the type's |
---|
| 83 | alignment and uses an @alignof@ expression. The remaining fields are resolved |
---|
| 84 | to a name matching the field's name and type using the normal visibility and |
---|
| 85 | overload resolution rules of the type system. |
---|
| 86 | |
---|
| 87 | These operations are split up into several groups depending on where they take |
---|
| 88 | place which varies for monomorphic and polymorphic types. The first devision is |
---|
| 89 | between the declarations and the definitions. Declarations, such as a function |
---|
| 90 | signature or a aggregate's name, must always be visible but may be repeated in |
---|
| 91 | the form of forward declarations in headers. Definitions, such as function |
---|
| 92 | bodies and a aggregate's layout, can be separately compiled but must occur |
---|
| 93 | exactly once in a source file. |
---|
| 94 | |
---|
| 95 | \begin{sloppypar} |
---|
[26ca815] | 96 | The declarations include the virtual type definition and forward declarations |
---|
| 97 | of the virtual table instance, constructor, message function and |
---|
[7eb6eb5] | 98 | @get_exception_vtable@. The definition includes the storage and initialization |
---|
| 99 | of the virtual table instance and the bodies of the three functions. |
---|
| 100 | \end{sloppypar} |
---|
[26ca815] | 101 | |
---|
| 102 | Monomorphic instances put all of these two groups in one place each. |
---|
[7eb6eb5] | 103 | Polymorphic instances also split out the core declarations and definitions from |
---|
| 104 | the per-instance information. The virtual table type and most of the functions |
---|
| 105 | are polymorphic so they are all part of the core. The virtual table instance |
---|
| 106 | and the @get_exception_vtable@ function. |
---|
[26ca815] | 107 | |
---|
[7eb6eb5] | 108 | \begin{sloppypar} |
---|
[f28fdee] | 109 | Coroutines and threads need instances of @CoroutineCancelled@ and |
---|
[830299f] | 110 | @ThreadCancelled@ respectively to use all of their functionality. When a new |
---|
[7eb6eb5] | 111 | data type is declared with @coroutine@ or @thread@ the forward declaration for |
---|
| 112 | the instance is created as well. The definition of the virtual table is created |
---|
| 113 | at the definition of the main function. |
---|
| 114 | \end{sloppypar} |
---|
[26ca815] | 115 | |
---|
| 116 | \subsection{Virtual Cast} |
---|
[7eb6eb5] | 117 | Virtual casts are implemented as a function call that does the subtype check |
---|
| 118 | and a C coercion-cast to do the type conversion. |
---|
| 119 | % The C-cast is just to make sure the generated code is correct so the rest of |
---|
| 120 | % the section is about that function. |
---|
| 121 | The function is |
---|
| 122 | \begin{cfa} |
---|
[830299f] | 123 | void * __cfa__virtual_cast( |
---|
| 124 | struct __cfa__parent_vtable const * parent, |
---|
[7eb6eb5] | 125 | struct __cfa__parent_vtable const * const * child ); |
---|
| 126 | \end{cfa} |
---|
[830299f] | 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. |
---|
[26ca815] | 149 | |
---|
| 150 | \section{Exceptions} |
---|
| 151 | % Anything about exception construction. |
---|
| 152 | |
---|
| 153 | \section{Unwinding} |
---|
| 154 | % Adapt the unwind chapter, just describe the sections of libunwind used. |
---|
| 155 | % Mention that termination and cancellation use it. Maybe go into why |
---|
| 156 | % resumption doesn't as well. |
---|
| 157 | |
---|
[7eb6eb5] | 158 | % Many modern languages work with an interal stack that function push and pop |
---|
| 159 | % their local data to. Stack unwinding removes large sections of the stack, |
---|
| 160 | % often across functions. |
---|
| 161 | |
---|
| 162 | Stack unwinding is the process of removing stack frames (activations) from the |
---|
| 163 | stack. On function entry and return, unwinding is handled directly by the code |
---|
| 164 | embedded in the function. Usually, the stack-frame size is known statically |
---|
[830299f] | 165 | based on parameter and local variable declarations. For dynamically-sized |
---|
[7eb6eb5] | 166 | local variables, a runtime computation is necessary to know the frame |
---|
| 167 | size. Finally, a function's frame-size may change during execution as local |
---|
| 168 | variables (static or dynamic sized) go in and out of scope. |
---|
| 169 | Allocating/deallocating stack space is usually an $O(1)$ operation achieved by |
---|
| 170 | bumping the hardware stack-pointer up or down as needed. |
---|
| 171 | |
---|
| 172 | Unwinding across multiple stack frames is more complex because individual stack |
---|
| 173 | management code associated with each frame is bypassed. That is, the location |
---|
| 174 | of a function's frame-management code is largely unknown and dispersed |
---|
| 175 | throughout the function, hence the current frame size managed by that code is |
---|
| 176 | also unknown. Hence, code unwinding across frames does not have direct |
---|
| 177 | knowledge about what is on the stack, and hence, how much of the stack needs to |
---|
| 178 | be removed. |
---|
| 179 | |
---|
| 180 | % At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply |
---|
| 181 | % move the top of the stack, discarding everything on the stack above a certain |
---|
| 182 | % point. However this ignores all the cleanup code that should be run when |
---|
| 183 | % certain sections of the stack are removed (for \CFA these are from destructors |
---|
| 184 | % and finally clauses) and also requires that the point to which the stack is |
---|
| 185 | % being unwound is known ahead of time. libunwind is used to address both of |
---|
| 186 | % these problems. |
---|
| 187 | |
---|
| 188 | The traditional unwinding mechanism for C is implemented by saving a snap-shot |
---|
| 189 | of a function's state with @setjmp@ and restoring that snap-shot with |
---|
| 190 | @longjmp@. This approach bypasses the need to know stack details by simply |
---|
| 191 | reseting to a snap-shot of an arbitrary but existing function frame on the |
---|
| 192 | stack. It is up to the programmer to ensure the snap-shot is valid when it is |
---|
| 193 | reset, making this unwinding approach fragile with potential errors that are |
---|
| 194 | difficult to debug because the stack becomes corrupted. |
---|
| 195 | |
---|
| 196 | However, many languages define cleanup actions that must be taken when objects |
---|
| 197 | are deallocated from the stack or blocks end, such as running a variable's |
---|
| 198 | destructor or a @try@ statement's @finally@ clause. Handling these mechanisms |
---|
| 199 | requires walking the stack and checking each stack frame for these potential |
---|
| 200 | actions. |
---|
| 201 | |
---|
| 202 | For exceptions, it must be possible to walk the stack frames in search of @try@ |
---|
| 203 | statements to match and execute a handler. For termination exceptions, it must |
---|
| 204 | also be possible to unwind all stack frames from the throw to the matching |
---|
| 205 | catch, and each of these frames must be checked for cleanup actions. Stack |
---|
| 206 | walking is where most of the complexity and expense of exception handling |
---|
| 207 | appears. |
---|
| 208 | |
---|
| 209 | One of the most popular tools for stack management is libunwind, a low-level |
---|
| 210 | library that provides tools for stack walking, handler execution, and |
---|
| 211 | unwinding. What follows is an overview of all the relevant features of |
---|
| 212 | libunwind needed for this work, and how \CFA uses them to implement exception |
---|
| 213 | handling. |
---|
| 214 | |
---|
| 215 | \subsection{libunwind Usage} |
---|
| 216 | Libunwind, accessed through @unwind.h@ on most platforms, is a C library that |
---|
| 217 | provides \CC-style stack-unwinding. Its operation is divided into two phases: |
---|
| 218 | search and cleanup. The dynamic target search -- phase 1 -- is used to scan the |
---|
| 219 | stack and decide where unwinding should stop (but no unwinding occurs). The |
---|
| 220 | cleanup -- phase 2 -- does the unwinding and also runs any cleanup code. |
---|
| 221 | |
---|
| 222 | To use libunwind, each function must have a personality function and a Language |
---|
[830299f] | 223 | Specific Data Area (LSDA). The LSDA has the unique information for each |
---|
[7eb6eb5] | 224 | function to tell the personality function where a function is executing, its |
---|
[830299f] | 225 | current stack frame, and what handlers should be checked. Theoretically, the |
---|
[7eb6eb5] | 226 | LSDA can contain any information but conventionally it is a table with entries |
---|
| 227 | representing regions of the function and what has to be done there during |
---|
| 228 | unwinding. These regions are bracketed by the instruction pointer. If the |
---|
| 229 | instruction pointer is within a region's start/end, then execution is currently |
---|
| 230 | executing in that region. Regions are used to mark out the scopes of objects |
---|
| 231 | with destructors and try blocks. |
---|
| 232 | |
---|
| 233 | % Libunwind actually does very little, it simply moves down the stack from |
---|
| 234 | % function to function. Most of the actions are implemented by the personality |
---|
| 235 | % function which libunwind calls on every function. Since this is shared across |
---|
| 236 | % many functions or even every function in a language it will need a bit more |
---|
| 237 | % information. |
---|
| 238 | |
---|
| 239 | The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and |
---|
[830299f] | 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.} |
---|
[7eb6eb5] | 244 | \begin{cfa} |
---|
| 245 | void clean_up( int * var ) { ... } |
---|
[830299f] | 246 | int avar __attribute__(( cleanup(clean_up) )); |
---|
[7eb6eb5] | 247 | \end{cfa} |
---|
[830299f] | 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. |
---|
[7eb6eb5] | 254 | |
---|
| 255 | \subsection{Personality Functions} |
---|
[830299f] | 256 | Personality functions have a complex interface specified by libunwind. This |
---|
[7eb6eb5] | 257 | section covers some of the important parts of the interface. |
---|
| 258 | |
---|
[830299f] | 259 | A personality function can preform different actions depending on how it is |
---|
| 260 | called. |
---|
[7eb6eb5] | 261 | \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] |
---|
| 262 | typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) ( |
---|
| 263 | _Unwind_Action @action@, |
---|
| 264 | _Unwind_Exception_Class @exception_class@, |
---|
| 265 | _Unwind_Exception * @exception@, |
---|
| 266 | struct _Unwind_Context * @context@ |
---|
| 267 | ); |
---|
[26ca815] | 268 | \end{lstlisting} |
---|
[7eb6eb5] | 269 | The @action@ argument is a bitmask of possible actions: |
---|
| 270 | \begin{enumerate} |
---|
| 271 | \item |
---|
| 272 | @_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function |
---|
[830299f] | 273 | to check for handlers. If there is a handler in a stack frame, as defined by |
---|
[7eb6eb5] | 274 | the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise |
---|
| 275 | it return @_URC_CONTINUE_UNWIND@. |
---|
| 276 | |
---|
| 277 | \item |
---|
| 278 | @_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is |
---|
| 279 | unwound and all cleanup code is run. The personality function does whatever |
---|
| 280 | cleanup the language defines (such as running destructors/finalizers) and then |
---|
| 281 | generally returns @_URC_CONTINUE_UNWIND@. |
---|
| 282 | |
---|
| 283 | \item |
---|
| 284 | \begin{sloppypar} |
---|
| 285 | @_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a |
---|
| 286 | handler. The personality function must prepare to return to normal code |
---|
| 287 | execution and return @_URC_INSTALL_CONTEXT@. |
---|
| 288 | \end{sloppypar} |
---|
| 289 | |
---|
| 290 | \item |
---|
| 291 | @_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs |
---|
| 292 | the cleanup phase and uses a different means to decide when to stop |
---|
| 293 | \see{\VRef{s:ForcedUnwind}}. |
---|
| 294 | \end{enumerate} |
---|
| 295 | |
---|
| 296 | The @exception_class@ argument is a copy of the |
---|
| 297 | \lstinline[language=C]|exception|'s @exception_class@ field. |
---|
| 298 | |
---|
| 299 | The \lstinline[language=C]|exception| argument is a pointer to the user |
---|
| 300 | provided storage object. It has two public fields, the exception class, which |
---|
| 301 | is actually just a number, identifying the exception handling mechanism that |
---|
| 302 | created it, and the cleanup function. The cleanup function is called if |
---|
| 303 | required by the exception. |
---|
| 304 | |
---|
| 305 | The @context@ argument is a pointer to an opaque type passed to helper |
---|
| 306 | functions called inside the personality function. |
---|
| 307 | |
---|
| 308 | The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages |
---|
[26ca815] | 309 | that can be passed several places in libunwind. It includes a number of |
---|
| 310 | messages for special cases (some of which should never be used by the |
---|
| 311 | personality function) and error codes but unless otherwise noted the |
---|
[f28fdee] | 312 | personality function should always return @_URC_CONTINUE_UNWIND@. |
---|
[26ca815] | 313 | |
---|
| 314 | \subsection{Raise Exception} |
---|
[7eb6eb5] | 315 | Raising an exception is the central function of libunwind and it performs a |
---|
| 316 | two-staged unwinding. |
---|
| 317 | \begin{cfa} |
---|
[26ca815] | 318 | _Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *); |
---|
[7eb6eb5] | 319 | \end{cfa} |
---|
| 320 | First, the function begins the search phase, calling the personality function |
---|
| 321 | of the most recent stack frame. It continues to call personality functions |
---|
| 322 | traversing the stack from newest to oldest until a function finds a handler or |
---|
| 323 | the end of the stack is reached. In the latter case, raise exception returns |
---|
| 324 | @_URC_END_OF_STACK@. |
---|
| 325 | |
---|
[1c1c180] | 326 | Second, when a handler is matched, raise exception continues onto the cleanup |
---|
| 327 | phase. |
---|
[7eb6eb5] | 328 | Once again, it calls the personality functions of each stack frame from newest |
---|
| 329 | to oldest. This pass stops at the stack frame containing the matching handler. |
---|
| 330 | If that personality function has not install a handler, it is an error. |
---|
| 331 | |
---|
| 332 | If an error is encountered, raise exception returns either |
---|
| 333 | @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the |
---|
| 334 | error occurred. |
---|
[26ca815] | 335 | |
---|
| 336 | \subsection{Forced Unwind} |
---|
[7eb6eb5] | 337 | \label{s:ForcedUnwind} |
---|
| 338 | Forced Unwind is the other central function in libunwind. |
---|
| 339 | \begin{cfa} |
---|
| 340 | _Unwind_Reason_Code _Unwind_ForcedUnwind( _Unwind_Exception *, |
---|
| 341 | _Unwind_Stop_Fn, void *); |
---|
| 342 | \end{cfa} |
---|
| 343 | It also unwinds the stack but it does not use the search phase. Instead another |
---|
[830299f] | 344 | function, the stop function, is used to stop searching. The exception is the |
---|
[7eb6eb5] | 345 | same as the one passed to raise exception. The extra arguments are the stop |
---|
| 346 | function and the stop parameter. The stop function has a similar interface as a |
---|
| 347 | personality function, except it is also passed the stop parameter. |
---|
| 348 | \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] |
---|
| 349 | typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)( |
---|
| 350 | _Unwind_Action @action@, |
---|
| 351 | _Unwind_Exception_Class @exception_class@, |
---|
| 352 | _Unwind_Exception * @exception@, |
---|
| 353 | struct _Unwind_Context * @context@, |
---|
| 354 | void * @stop_parameter@); |
---|
[26ca815] | 355 | \end{lstlisting} |
---|
| 356 | |
---|
| 357 | The stop function is called at every stack frame before the personality |
---|
[7eb6eb5] | 358 | function is called and then once more after all frames of the stack are |
---|
| 359 | unwound. |
---|
[26ca815] | 360 | |
---|
[7eb6eb5] | 361 | Each time it is called, the stop function should return @_URC_NO_REASON@ or |
---|
| 362 | transfer control directly to other code outside of libunwind. The framework |
---|
| 363 | does not provide any assistance here. |
---|
[26ca815] | 364 | |
---|
[7eb6eb5] | 365 | \begin{sloppypar} |
---|
[830299f] | 366 | Its arguments are the same as the paired personality function. The actions |
---|
[7eb6eb5] | 367 | @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is |
---|
| 368 | called. Beyond the libunwind standard, both GCC and Clang add an extra action |
---|
| 369 | on the last call at the end of the stack: @_UA_END_OF_STACK@. |
---|
| 370 | \end{sloppypar} |
---|
[26ca815] | 371 | |
---|
| 372 | \section{Exception Context} |
---|
| 373 | % Should I have another independent section? |
---|
| 374 | % There are only two things in it, top_resume and current_exception. How it is |
---|
[7eb6eb5] | 375 | % stored changes depending on whether or not the thread-library is linked. |
---|
| 376 | |
---|
| 377 | The exception context is global storage used to maintain data across different |
---|
| 378 | exception operations and to communicate among different components. |
---|
| 379 | |
---|
| 380 | Each stack must have its own exception context. In a sequential \CFA program, |
---|
| 381 | there is only one stack with a single global exception-context. However, when |
---|
| 382 | the library @libcfathread@ is linked, there are multiple stacks where each |
---|
| 383 | needs its own exception context. |
---|
| 384 | |
---|
| 385 | General access to the exception context is provided by function |
---|
| 386 | @this_exception_context@. For sequential execution, this function is defined as |
---|
| 387 | a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is |
---|
| 388 | concurrent, it links with @libcfathread@, where this function is defined with a |
---|
| 389 | strong symbol replacing the sequential version. |
---|
| 390 | |
---|
[830299f] | 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. |
---|
[26ca815] | 396 | |
---|
| 397 | \section{Termination} |
---|
| 398 | % Memory management & extra information, the custom function used to implement |
---|
| 399 | % catches. Talk about GCC nested functions. |
---|
| 400 | |
---|
[7eb6eb5] | 401 | Termination exceptions use libunwind heavily because it matches the intended |
---|
| 402 | use from \CC exceptions closely. The main complication for \CFA is that the |
---|
| 403 | compiler generates C code, making it very difficult to generate the assembly to |
---|
| 404 | form the LSDA for try blocks or destructors. |
---|
[26ca815] | 405 | |
---|
| 406 | \subsection{Memory Management} |
---|
[7eb6eb5] | 407 | The first step of a termination raise is to copy the exception into memory |
---|
| 408 | managed by the exception system. Currently, the system uses @malloc@, rather |
---|
| 409 | than reserved memory or the stack top. The exception handling mechanism manages |
---|
| 410 | memory for the exception as well as memory for libunwind and the system's own |
---|
| 411 | per-exception storage. |
---|
| 412 | |
---|
[830299f] | 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 |
---|
[7eb6eb5] | 425 | information for libunwind and the exception system. The second component is an |
---|
| 426 | area of memory big enough to store the exception. Macros with pointer arthritic |
---|
| 427 | and type cast are used to move between the components or go from the embedded |
---|
[f28fdee] | 428 | @_Unwind_Exception@ to the entire node. |
---|
[26ca815] | 429 | |
---|
[7eb6eb5] | 430 | All of these nodes are linked together in a list, one list per stack, with the |
---|
| 431 | list head stored in the exception context. Within each linked list, the most |
---|
| 432 | recently thrown exception is at the head followed by older thrown |
---|
| 433 | exceptions. This format allows exceptions to be thrown, while a different |
---|
| 434 | exception is being handled. The exception at the head of the list is currently |
---|
| 435 | being handled, while other exceptions wait for the exceptions before them to be |
---|
| 436 | removed. |
---|
| 437 | |
---|
| 438 | The virtual members in the exception's virtual table provide the size of the |
---|
| 439 | exception, the copy function, and the free function, so they are specific to an |
---|
| 440 | exception type. The size and copy function are used immediately to copy an |
---|
| 441 | exception into managed memory. After the exception is handled the free function |
---|
[830299f] | 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. |
---|
[7eb6eb5] | 444 | |
---|
| 445 | \subsection{Try Statements and Catch Clauses} |
---|
| 446 | The try statement with termination handlers is complex because it must |
---|
| 447 | compensate for the lack of assembly-code generated from \CFA. Libunwind |
---|
| 448 | requires an LSDA and personality function for control to unwind across a |
---|
| 449 | function. The LSDA in particular is hard to mimic in generated C code. |
---|
| 450 | |
---|
| 451 | The workaround is a function called @__cfaehm_try_terminate@ in the standard |
---|
| 452 | library. The contents of a try block and the termination handlers are converted |
---|
| 453 | into functions. These are then passed to the try terminate function and it |
---|
[830299f] | 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. |
---|
[26ca815] | 462 | |
---|
| 463 | The three functions passed to try terminate are: |
---|
[7eb6eb5] | 464 | \begin{description} |
---|
| 465 | \item[try function:] This function is the try block, all the code inside the |
---|
| 466 | try block is placed inside the try function. It takes no parameters and has no |
---|
| 467 | return value. This function is called during regular execution to run the try |
---|
| 468 | block. |
---|
| 469 | |
---|
| 470 | \item[match function:] This function is called during the search phase and |
---|
[830299f] | 471 | decides if a catch clause matches the termination exception. It is constructed |
---|
[7eb6eb5] | 472 | from the conditional part of each handler and runs each check, top to bottom, |
---|
| 473 | in turn, first checking to see if the exception type matches and then if the |
---|
| 474 | condition is true. It takes a pointer to the exception and returns 0 if the |
---|
| 475 | exception is not handled here. Otherwise the return value is the id of the |
---|
| 476 | handler that matches the exception. |
---|
| 477 | |
---|
| 478 | \item[handler function:] This function handles the exception. It takes a |
---|
| 479 | pointer to the exception and the handler's id and returns nothing. It is called |
---|
[830299f] | 480 | after the cleanup phase. It is constructed by stitching together the bodies of |
---|
[7eb6eb5] | 481 | each handler and dispatches to the selected handler. |
---|
| 482 | \end{description} |
---|
| 483 | All three functions are created with GCC nested functions. GCC nested functions |
---|
| 484 | can be used to create closures, functions that can refer to the state of other |
---|
| 485 | functions on the stack. This approach allows the functions to refer to all the |
---|
[830299f] | 486 | variables in scope for the function containing the @try@ statement. These |
---|
[7eb6eb5] | 487 | nested functions and all other functions besides @__cfaehm_try_terminate@ in |
---|
| 488 | \CFA use the GCC personality function and the @-fexceptions@ flag to generate |
---|
| 489 | the LSDA. This allows destructors to be implemented with the cleanup attribute. |
---|
[26ca815] | 490 | |
---|
| 491 | \section{Resumption} |
---|
| 492 | % The stack-local data, the linked list of nodes. |
---|
| 493 | |
---|
[7eb6eb5] | 494 | Resumption simple to implement because there is no stack unwinding. The |
---|
| 495 | resumption raise uses a list of nodes for its stack traversal. The head of the |
---|
| 496 | list is stored in the exception context. The nodes in the list have a pointer |
---|
[26ca815] | 497 | to the next node and a pointer to the handler function. |
---|
| 498 | |
---|
[7eb6eb5] | 499 | A resumption raise traverses this list. At each node the handler function is |
---|
| 500 | called, passing the exception by pointer. It returns true if the exception is |
---|
| 501 | handled and false otherwise. |
---|
[26ca815] | 502 | |
---|
[7eb6eb5] | 503 | The handler function does both the matching and handling. It computes the |
---|
| 504 | condition of each @catchResume@ in top-to-bottom order, until it finds a |
---|
| 505 | handler that matches. If no handler matches then the function returns |
---|
| 506 | false. Otherwise the matching handler is run; if it completes successfully, the |
---|
[830299f] | 507 | function returns true. Rethrowing, through the @throwResume;@ statement, |
---|
| 508 | causes the function to return true. |
---|
[26ca815] | 509 | |
---|
[12b4ab4] | 510 | % Recursive Resumption Stuff: |
---|
[7eb6eb5] | 511 | Search skipping \see{\VPageref{p:searchskip}}, which ignores parts of the stack |
---|
| 512 | already examined, is accomplished by updating the front of the list as the |
---|
| 513 | search continues. Before the handler at a node is called the head of the list |
---|
| 514 | is updated to the next node of the current node. After the search is complete, |
---|
| 515 | successful or not, the head of the list is reset. |
---|
[12b4ab4] | 516 | |
---|
[7eb6eb5] | 517 | This mechanism means the current handler and every handler that has already |
---|
| 518 | been checked are not on the list while a handler is run. If a resumption is |
---|
| 519 | thrown during the handling of another resumption the active handlers and all |
---|
| 520 | the other handler checked up to this point are not checked again. |
---|
[12b4ab4] | 521 | |
---|
| 522 | This structure also supports new handler added while the resumption is being |
---|
| 523 | handled. These are added to the front of the list, pointing back along the |
---|
[7eb6eb5] | 524 | stack -- the first one points over all the checked handlers -- and the ordering |
---|
| 525 | is maintained. |
---|
| 526 | |
---|
| 527 | \label{p:zero-cost} |
---|
| 528 | Note, the resumption implementation has a cost for entering/exiting a @try@ |
---|
| 529 | statement with @catchResume@ clauses, whereas a @try@ statement with @catch@ |
---|
| 530 | clauses has zero-cost entry/exit. While resumption does not need the stack |
---|
| 531 | unwinding and cleanup provided by libunwind, it could use the search phase to |
---|
| 532 | providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way |
---|
| 533 | to return from a libunwind search without installing a handler or raising an |
---|
[830299f] | 534 | error. Although workarounds might be possible, they are beyond the scope of |
---|
[7eb6eb5] | 535 | this thesis. The current resumption implementation has simplicity in its |
---|
| 536 | favour. |
---|
[26ca815] | 537 | % Seriously, just compare the size of the two chapters and then consider |
---|
| 538 | % that unwind is required knowledge for that chapter. |
---|
| 539 | |
---|
| 540 | \section{Finally} |
---|
| 541 | % Uses destructors and GCC nested functions. |
---|
[7eb6eb5] | 542 | Finally clauses is placed into a GCC nested-function with a unique name, and no |
---|
| 543 | arguments or return values. This nested function is then set as the cleanup |
---|
| 544 | function of an empty object that is declared at the beginning of a block placed |
---|
| 545 | around the context of the associated @try@ statement. |
---|
[26ca815] | 546 | |
---|
| 547 | The rest is handled by GCC. The try block and all handlers are inside the |
---|
[7eb6eb5] | 548 | block. At completion, control exits the block and the empty object is cleaned |
---|
| 549 | up, which runs the function that contains the finally code. |
---|
[26ca815] | 550 | |
---|
| 551 | \section{Cancellation} |
---|
| 552 | % Stack selections, the three internal unwind functions. |
---|
| 553 | |
---|
| 554 | Cancellation also uses libunwind to do its stack traversal and unwinding, |
---|
[830299f] | 555 | however it uses a different primary function @_Unwind_ForcedUnwind@. Details |
---|
[7eb6eb5] | 556 | of its interface can be found in the \VRef{s:ForcedUnwind}. |
---|
[26ca815] | 557 | |
---|
[7eb6eb5] | 558 | The first step of cancellation is to find the cancelled stack and its type: |
---|
| 559 | coroutine or thread. Fortunately, the thread library stores the main thread |
---|
| 560 | pointer and the current thread pointer, and every thread stores a pointer to |
---|
[26ca815] | 561 | its main coroutine and the coroutine it is currently executing. |
---|
| 562 | |
---|
[830299f] | 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. |
---|
[7eb6eb5] | 568 | |
---|
| 569 | However, if the threading library is not linked, the sequential execution is on |
---|
| 570 | the main stack. Hence, the entire check is skipped because the weak-symbol |
---|
| 571 | function is loaded. Therefore, a main thread cancellation is unconditionally |
---|
| 572 | performed. |
---|
| 573 | |
---|
| 574 | Regardless of how the stack is chosen, the stop function and parameter are |
---|
| 575 | passed to the forced-unwind function. The general pattern of all three stop |
---|
| 576 | functions is the same: they continue unwinding until the end of stack when they |
---|
| 577 | do there primary work. |
---|
| 578 | |
---|
| 579 | For main stack cancellation, the transfer is just a program abort. |
---|
| 580 | |
---|
| 581 | For coroutine cancellation, the exception is stored on the coroutine's stack, |
---|
| 582 | and the coroutine context switches to its last resumer. The rest is handled on |
---|
| 583 | the backside of the resume, which check if the resumed coroutine is |
---|
| 584 | cancelled. If cancelled, the exception is retrieved from the resumed coroutine, |
---|
| 585 | and a @CoroutineCancelled@ exception is constructed and loaded with the |
---|
| 586 | cancelled exception. It is then resumed as a regular exception with the default |
---|
| 587 | handler coming from the context of the resumption call. |
---|
| 588 | |
---|
| 589 | For thread cancellation, the exception is stored on the thread's main stack and |
---|
| 590 | then context switched to the scheduler. The rest is handled by the thread |
---|
| 591 | joiner. When the join is complete, the joiner checks if the joined thread is |
---|
| 592 | cancelled. If cancelled, the exception is retrieved and the joined thread, and |
---|
| 593 | a @ThreadCancelled@ exception is constructed and loaded with the cancelled |
---|
| 594 | exception. The default handler is passed in as a function pointer. If it is |
---|
| 595 | null (as it is for the auto-generated joins on destructor call), the default is |
---|
| 596 | used, which is a program abort. |
---|
| 597 | %; which gives the required handling on implicate join. |
---|