1 | \chapter{Implementation} |
---|
2 | % Goes over how all the features are implemented. |
---|
3 | |
---|
4 | The implementation work for this thesis covers two components: the virtual |
---|
5 | system and exceptions. Each component is discussed in detail. |
---|
6 | |
---|
7 | \section{Virtual System} |
---|
8 | \label{s:VirtualSystem} |
---|
9 | % Virtual table rules. Virtual tables, the pointer to them and the cast. |
---|
10 | While the \CFA virtual system currently has only one public feature, virtual |
---|
11 | cast (see the virtual cast feature \vpageref{p:VirtualCast}), |
---|
12 | substantial structure is required to support it, |
---|
13 | and provide features for exception handling and the standard library. |
---|
14 | |
---|
15 | \subsection{Virtual Type} |
---|
16 | Virtual types only have one change to their structure: the addition of a |
---|
17 | pointer to the virtual table, called the \emph{virtual-table pointer}. |
---|
18 | Internally, the field is called |
---|
19 | @virtual_table@. |
---|
20 | This constant pointer is always the first field of the table so when |
---|
21 | casting to a supertype, the field's location is always known. |
---|
22 | The field is initialized as part of all generated constructors. |
---|
23 | \todo{They only come as part exceptions and don't work.} |
---|
24 | %After the object is created the field is constant. |
---|
25 | Dereferencing it gives the virtual table and access to the |
---|
26 | type's virtual members. |
---|
27 | |
---|
28 | \subsection{Virtual Table} |
---|
29 | % PAB: These 2 paragraphs are repeated below, and maybe some of the paragraph above, too. |
---|
30 | \begin{comment} |
---|
31 | Every time a virtual type is defined, a new virtual table-type is |
---|
32 | instantiated. |
---|
33 | The uniqueness of the virtual-table |
---|
34 | instance is important because its address |
---|
35 | is used as the identifier for the virtual type. Hence, a pointer to the |
---|
36 | virtual table and the ID for the virtual type are interchangeable. |
---|
37 | \todo{Unique instances might be going so we will have to talk about the new |
---|
38 | system instead.} |
---|
39 | |
---|
40 | The first step is creating the virtual-table type. |
---|
41 | The virtual-table type is a structure and is described in terms of |
---|
42 | its fields. The first field contains the parent-type ID (or a pointer to |
---|
43 | the parent virtual-table) or 0 (null pointer). |
---|
44 | Next are repeated fields from on the parent virtual-table. |
---|
45 | Finally, the fields used to store any new virtual members of the new |
---|
46 | the virtual type. |
---|
47 | \end{comment} |
---|
48 | |
---|
49 | %The virtual system is accessed through a private constant field inserted at the |
---|
50 | %beginning of every virtual type. This field |
---|
51 | The virtual-table pointer |
---|
52 | points at a type's virtual table (see Figure~\vref{f:VirtualTableLayout}). |
---|
53 | %and is assigned during the object's |
---|
54 | %construction. |
---|
55 | The address of a virtual table acts as the unique identifier for |
---|
56 | the virtual type, and the first field of a virtual table is a pointer to the |
---|
57 | parent virtual-table or @0p@ (null pointer). The remaining fields are duplicated from the |
---|
58 | parent tables in this type's inheritance chain, followed by any fields this type |
---|
59 | introduces. Parent fields are duplicated so they can be changed, \ie all virtual |
---|
60 | members are overridable, while the parent pointer allows access to the original values. |
---|
61 | Hence, references to the dispatched type |
---|
62 | are replaced with the current virtual type. |
---|
63 | % These are always taken by pointer or reference. |
---|
64 | |
---|
65 | \begin{figure} |
---|
66 | % Simple ascii diragram: |
---|
67 | \begin{cfa} |
---|
68 | parent_pointer // \C{parent pointer to access its fields} |
---|
69 | parent_field0 // \C{same layout as parent to allow replacement} |
---|
70 | ... |
---|
71 | parent_fieldN |
---|
72 | child_field0 // \C{new types for this virtual table} |
---|
73 | ... |
---|
74 | child_fieldN |
---|
75 | size |
---|
76 | alignment |
---|
77 | \end{cfa} |
---|
78 | %\todo{Refine the diagram} |
---|
79 | \caption{Virtual Table Layout} |
---|
80 | \label{f:VirtualTableLayout} |
---|
81 | \end{figure} |
---|
82 | |
---|
83 | % For each virtual type, a virtual table is constructed. This is both a new type |
---|
84 | % and an instance of that type. Other instances of the type could be created |
---|
85 | % but the system doesn't use them. So this section will go over the creation of |
---|
86 | % the type and the instance. |
---|
87 | |
---|
88 | \begin{comment} |
---|
89 | PAB: seems to be said already. |
---|
90 | A virtual table is created when a virtual type is created. The name of the |
---|
91 | type is created by mangling the name of the base type. The name of the instance |
---|
92 | is also generated by name mangling. The fields are initialized automatically. |
---|
93 | The parent field is initialized by getting the type of the parent field and |
---|
94 | using that to calculate the mangled name of the parent's virtual-table type. |
---|
95 | \end{comment} |
---|
96 | There are two special fields that are included like normal fields but have |
---|
97 | special initialization rules: the @size@ field is the type's size and is |
---|
98 | initialized with a @sizeof@ expression, the @align@ field is the type's |
---|
99 | alignment and uses an @alignof@ expression. The remaining fields are resolved |
---|
100 | to a name matching the field's name and type using the normal visibility and |
---|
101 | overload resolution rules of the type system. |
---|
102 | |
---|
103 | These operations are split up into several groups depending on where they take |
---|
104 | place, which varies for monomorphic and polymorphic types. The first devision is |
---|
105 | between the declarations and the definitions. Declarations, such as a function |
---|
106 | signature or an aggregate's name, must always be visible but may be repeated in |
---|
107 | the form of forward declarations in headers. Definitions, such as function |
---|
108 | bodies and a aggregate's layout, can be separately compiled but must occur |
---|
109 | exactly once in a source file. |
---|
110 | |
---|
111 | The declarations include the virtual-type definition and forward declarations |
---|
112 | of the virtual-table instance, constructor, message function and |
---|
113 | @get_exception_vtable@. The definition includes the storage and initialization |
---|
114 | of the virtual table instance and the bodies of the three functions. |
---|
115 | |
---|
116 | Monomorphic instances put all of these two groups in one place. |
---|
117 | Polymorphic instances split out the core declarations and definitions from |
---|
118 | the per-instance information. The virtual-table type and most of the functions |
---|
119 | are polymorphic so they are all part of the core. The virtual-table instance |
---|
120 | and the @get_exception_vtable@ function \PAB{ are ...}. |
---|
121 | |
---|
122 | Coroutines and threads need instances of @CoroutineCancelled@ and |
---|
123 | @ThreadCancelled@ respectively to use all of their functionality. When a new |
---|
124 | data type is declared with @coroutine@ or @thread@, the forward declaration for |
---|
125 | the instance is created as well. The definition of the virtual table is created |
---|
126 | at the definition of the main function. |
---|
127 | |
---|
128 | \PAB{You need an example here to show what happens for this case.} |
---|
129 | |
---|
130 | |
---|
131 | \subsection{Virtual Cast} |
---|
132 | Virtual casts are implemented as a function call that does the subtype check |
---|
133 | and a C coercion-cast to do the type conversion. |
---|
134 | % The C-cast is just to make sure the generated code is correct so the rest of |
---|
135 | % the section is about that function. |
---|
136 | The function is |
---|
137 | \begin{cfa} |
---|
138 | void * __cfa__virtual_cast( struct __cfa__parent_vtable const * parent, |
---|
139 | struct __cfa__parent_vtable const * const * child ); |
---|
140 | \end{cfa} |
---|
141 | and it is implemented in the standard library. The structure represents the |
---|
142 | head of a virtual table, which is the pointer to the parent virtual table. The |
---|
143 | @parent@ points directly at the parent-type virtual-table, while the @child@ |
---|
144 | points at the object of the (possible) child type. |
---|
145 | |
---|
146 | \PAB{Need a figure to show this relationship.} |
---|
147 | |
---|
148 | In terms of the virtual-cast expression, @parent@ comes from looking up the |
---|
149 | type being cast to and @child@ is the result of the expression being cast. |
---|
150 | Because the complier outputs C code, some C-type casts are also used. |
---|
151 | The last bit of glue is a map that saves every virtual type the compiler |
---|
152 | sees. This table is used to check the type used in a virtual cast is a virtual |
---|
153 | type and to get its virtual table. |
---|
154 | (It also checks for conflicting definitions.) |
---|
155 | |
---|
156 | \PAB{Can this be rolled into the figure above?} |
---|
157 | |
---|
158 | Inside the function is a simple conditional. If the type represented by |
---|
159 | @parent@ is an ancestor of the type represented by @*child@ (it |
---|
160 | requires one more level of dereference to pass through the object) then @child@ |
---|
161 | is returned, otherwise the null pointer is returned. |
---|
162 | |
---|
163 | The check is a simple linear search (like \Cpp RTTI). If the child |
---|
164 | virtual table or any of its ancestors (which are retrieved through the first |
---|
165 | field of every virtual table) are the same as the parent virtual-table then |
---|
166 | the cast succeeds. |
---|
167 | |
---|
168 | \section{Exceptions} |
---|
169 | % Anything about exception construction. |
---|
170 | |
---|
171 | \section{Unwinding} |
---|
172 | % Adapt the unwind chapter, just describe the sections of libunwind used. |
---|
173 | % Mention that termination and cancellation use it. Maybe go into why |
---|
174 | % resumption doesn't as well. |
---|
175 | |
---|
176 | % Many modern languages work with an internal stack that function push and pop |
---|
177 | % their local data to. Stack unwinding removes large sections of the stack, |
---|
178 | % often across functions. |
---|
179 | |
---|
180 | Stack unwinding is the process of removing stack frames (activations) from the |
---|
181 | stack. On function entry and return, unwinding is handled directly by the call/return code |
---|
182 | embedded in a function. Usually, the stack-frame size is known statically |
---|
183 | based on parameter and local variable declarations. For dynamically-sized |
---|
184 | local variables. |
---|
185 | (Often called a variable-length array or VLA, even when the variable type is an aggregate.) |
---|
186 | For VLAs, a runtime computation is necessary to know the frame |
---|
187 | size. Finally, a function's frame-size may change during execution as local |
---|
188 | variables (static or dynamic sized) go in and out of scope, which is a form of VLA. |
---|
189 | Allocating/deallocating stack space is usually an $O(1)$ operation achieved by |
---|
190 | bumping the hardware stack-pointer up or down as needed. |
---|
191 | |
---|
192 | Unwinding across multiple stack frames is more complex because individual stack-management |
---|
193 | code associated with each frame can be bypassed. That is, the location |
---|
194 | of a function's frame-management code is largely unknown and dispersed |
---|
195 | throughout the function, hence the current frame size managed by that code is |
---|
196 | also unknown. Hence, code unwinding across frames does not have direct |
---|
197 | knowledge about what is on the stack, and hence, how much of the stack needs to |
---|
198 | be removed. |
---|
199 | |
---|
200 | % At a very basic level this can be done with @setjmp@ \& @longjmp@ which simply |
---|
201 | % move the top of the stack, discarding everything on the stack above a certain |
---|
202 | % point. However this ignores all the cleanup code that should be run when |
---|
203 | % certain sections of the stack are removed (for \CFA these are from destructors |
---|
204 | % and finally clauses) and also requires that the point to which the stack is |
---|
205 | % being unwound is known ahead of time. libunwind is used to address both of |
---|
206 | % these problems. |
---|
207 | |
---|
208 | The traditional unwinding mechanism for C is implemented by saving a snap-shot |
---|
209 | of a function's state with @setjmp@ and restoring that snap-shot with |
---|
210 | @longjmp@. This approach bypasses the need to know stack details by simply |
---|
211 | reseting to a snap-shot of an arbitrary but existing function frame on the |
---|
212 | stack. It is up to the programmer to ensure the snap-shot is valid when it is |
---|
213 | reset and that unwound frames do not have side-effects. |
---|
214 | Hence, this unwinding approach is fragile with potential errors that are |
---|
215 | difficult to debug because the stack becomes corrupted. |
---|
216 | |
---|
217 | With respect to stack side-effects, many languages define cleanup actions that must be taken when objects |
---|
218 | are deallocated from the stack, when the function of blocks within the function end, such as running a variable's |
---|
219 | destructor or a @try@ statement's @finally@ clause. |
---|
220 | The purpose of these side-effects is to reestablish the global state of the program, such as dynamic memory-allocation or file access. |
---|
221 | Handling these side-effect mechanisms |
---|
222 | requires walking the stack and checking each stack frame for these potential |
---|
223 | actions, where a frame can be any block with declarations. |
---|
224 | |
---|
225 | In languages like \Cpp and Java, it must be possible to walk the stack frames in search of @try@ |
---|
226 | statements to match and execute a handler. For termination exceptions, it must |
---|
227 | also be possible to unwind all stack frames from the throw to the matching |
---|
228 | catch (including the @try@ block), and each of these frames must be checked for cleanup actions. Stack |
---|
229 | walking is where most of the complexity and expense of exception handling |
---|
230 | appears. |
---|
231 | |
---|
232 | One of the most popular tools for stack management is libunwind, a low-level |
---|
233 | library that provides tools for stack walking, handler execution, and |
---|
234 | unwinding. What follows is an overview of all the relevant features of |
---|
235 | libunwind needed for this work, and how \CFA uses them to implement exception |
---|
236 | handling. |
---|
237 | |
---|
238 | \subsection{libunwind Usage} |
---|
239 | Libunwind, accessed through @unwind.h@ on most platforms, is a C library that |
---|
240 | provides \Cpp-style stack-unwinding. Its operation is divided into two phases: |
---|
241 | search and cleanup. The dynamic target search -- phase 1 -- is used to scan the |
---|
242 | stack and decide where unwinding should stop (but no unwinding occurs). The |
---|
243 | cleanup -- phase 2 -- does the unwinding and also runs any cleanup code. |
---|
244 | |
---|
245 | To use libunwind, each function must have a personality function and a Language |
---|
246 | Specific Data Area (LSDA). The LSDA has the unique information for each |
---|
247 | function to tell the personality function where a function is executing, its |
---|
248 | current stack frame, and what handlers should be checked. Theoretically, the |
---|
249 | LSDA can contain any information but conventionally it is a table with entries |
---|
250 | representing regions of the function and what has to be done there during |
---|
251 | unwinding. These regions are bracketed by instruction addresses. If the |
---|
252 | instruction pointer is within a region's start/end, then execution is currently |
---|
253 | executing in that region. Regions are used to mark out the scopes of objects |
---|
254 | with destructors and try blocks. |
---|
255 | |
---|
256 | % Libunwind actually does very little, it simply moves down the stack from |
---|
257 | % function to function. Most of the actions are implemented by the personality |
---|
258 | % function which libunwind calls on every function. Since this is shared across |
---|
259 | % many functions or even every function in a language it will need a bit more |
---|
260 | % information. |
---|
261 | |
---|
262 | The GCC compilation flag @-fexceptions@ causes the generation of an LSDA and |
---|
263 | attaches its personality function. |
---|
264 | It attaches a series of opaque directives (@.cfi_personality@ directive) |
---|
265 | used internally and not part of this work. |
---|
266 | However, this |
---|
267 | flag only handles the cleanup attribute: |
---|
268 | \begin{cfa} |
---|
269 | void clean_up( int * var ) { ... } |
---|
270 | int avar __attribute__(( cleanup(clean_up) )); |
---|
271 | \end{cfa} |
---|
272 | that is used on a variable and specifies a function, in this case @clean_up@, |
---|
273 | run when the variable goes out of scope, which is used to mimic destructors. |
---|
274 | However, this feature cannot be used to mimic @try@ statements as it cannot |
---|
275 | control the unwinding. |
---|
276 | |
---|
277 | \subsection{Personality Functions} |
---|
278 | Personality functions have a complex interface specified by libunwind. This |
---|
279 | section covers some of the important parts of the interface. |
---|
280 | |
---|
281 | A personality function can perform different actions depending on how it is |
---|
282 | called. |
---|
283 | \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] |
---|
284 | typedef _Unwind_Reason_Code (*@_Unwind_Personality_Fn@) ( |
---|
285 | _Unwind_Action @action@, |
---|
286 | _Unwind_Exception_Class @exception_class@, |
---|
287 | _Unwind_Exception * @exception@, |
---|
288 | struct _Unwind_Context * @context@ |
---|
289 | ); |
---|
290 | \end{lstlisting} |
---|
291 | The @action@ argument is a bitmask of possible actions: |
---|
292 | \begin{enumerate}[topsep=5pt] |
---|
293 | \item |
---|
294 | @_UA_SEARCH_PHASE@ specifies a search phase and tells the personality function |
---|
295 | to check for handlers. If there is a handler in a stack frame, as defined by |
---|
296 | the language, the personality function returns @_URC_HANDLER_FOUND@; otherwise |
---|
297 | it return @_URC_CONTINUE_UNWIND@. |
---|
298 | |
---|
299 | \item |
---|
300 | @_UA_CLEANUP_PHASE@ specifies a cleanup phase, where the entire frame is |
---|
301 | unwound and all cleanup code is run. The personality function does whatever |
---|
302 | cleanup the language defines (such as running destructors/finalizers) and then |
---|
303 | generally returns @_URC_CONTINUE_UNWIND@. |
---|
304 | |
---|
305 | \item |
---|
306 | \begin{sloppypar} |
---|
307 | @_UA_HANDLER_FRAME@ specifies a cleanup phase on a function frame that found a |
---|
308 | handler. The personality function must prepare to return to normal code |
---|
309 | execution and return @_URC_INSTALL_CONTEXT@. |
---|
310 | \end{sloppypar} |
---|
311 | |
---|
312 | \item |
---|
313 | @_UA_FORCE_UNWIND@ specifies a forced unwind call. Forced unwind only performs |
---|
314 | the cleanup phase and uses a different means to decide when to stop |
---|
315 | (see Section~\vref{s:ForcedUnwind}). |
---|
316 | \end{enumerate} |
---|
317 | |
---|
318 | The @exception_class@ argument is a copy of the |
---|
319 | \lstinline[language=C]|exception|'s @exception_class@ field. |
---|
320 | \PAB{Say more.} |
---|
321 | |
---|
322 | The \lstinline[language=C]|exception| argument is a pointer to the user |
---|
323 | provided storage object. It has two public fields, the exception class, which |
---|
324 | is just a number, identifying the exception handling mechanism that |
---|
325 | created it, and the cleanup function. The cleanup function is called if |
---|
326 | required by the exception. |
---|
327 | |
---|
328 | The @context@ argument is a pointer to an opaque type passed to helper |
---|
329 | functions called inside the personality function. |
---|
330 | |
---|
331 | The return value, @_Unwind_Reason_Code@, is an enumeration of possible messages |
---|
332 | that can be passed several places in libunwind. It includes a number of |
---|
333 | messages for special cases (some of which should never be used by the |
---|
334 | personality function) and error codes. However, unless otherwise noted, the |
---|
335 | personality function should always return @_URC_CONTINUE_UNWIND@. |
---|
336 | |
---|
337 | \subsection{Raise Exception} |
---|
338 | Raising an exception is the central function of libunwind and it performs a |
---|
339 | two-staged unwinding. |
---|
340 | \begin{cfa} |
---|
341 | _Unwind_Reason_Code _Unwind_RaiseException(_Unwind_Exception *); |
---|
342 | \end{cfa} |
---|
343 | First, the function begins the search phase, calling the personality function |
---|
344 | of the most recent stack frame. It continues to call personality functions |
---|
345 | traversing the stack from newest to oldest until a function finds a handler or |
---|
346 | the end of the stack is reached. In the latter case, raise exception returns |
---|
347 | @_URC_END_OF_STACK@. |
---|
348 | |
---|
349 | Second, when a handler is matched, raise exception walks the stack again performing the cleanup |
---|
350 | phase. |
---|
351 | Once again, it calls the personality functions of each stack frame from newest |
---|
352 | to oldest. This pass stops at the stack frame containing the matching handler. |
---|
353 | If that personality function has not install a handler, it is an error. |
---|
354 | |
---|
355 | If an error is encountered, raise exception returns either |
---|
356 | @_URC_FATAL_PHASE1_ERROR@ or @_URC_FATAL_PHASE2_ERROR@ depending on when the |
---|
357 | error occurred. |
---|
358 | |
---|
359 | \subsection{Forced Unwind} |
---|
360 | \label{s:ForcedUnwind} |
---|
361 | Forced Unwind is the other central function in libunwind. |
---|
362 | \begin{cfa} |
---|
363 | _Unwind_Reason_Code _Unwind_ForcedUnwind(_Unwind_Exception *, |
---|
364 | _Unwind_Stop_Fn, void *); |
---|
365 | \end{cfa} |
---|
366 | It also unwinds the stack but it does not use the search phase. Instead another |
---|
367 | function, the stop function, is used to stop searching. The exception is the |
---|
368 | same as the one passed to raise exception. The extra arguments are the stop |
---|
369 | function and the stop parameter. The stop function has a similar interface as a |
---|
370 | personality function, except it is also passed the stop parameter. |
---|
371 | \begin{lstlisting}[language=C,{moredelim=**[is][\color{red}]{@}{@}}] |
---|
372 | typedef _Unwind_Reason_Code (*@_Unwind_Stop_Fn@)( |
---|
373 | _Unwind_Action @action@, |
---|
374 | _Unwind_Exception_Class @exception_class@, |
---|
375 | _Unwind_Exception * @exception@, |
---|
376 | struct _Unwind_Context * @context@, |
---|
377 | void * @stop_parameter@); |
---|
378 | \end{lstlisting} |
---|
379 | |
---|
380 | The stop function is called at every stack frame before the personality |
---|
381 | function is called and then once more after all frames of the stack are |
---|
382 | unwound. |
---|
383 | |
---|
384 | Each time it is called, the stop function should return @_URC_NO_REASON@ or |
---|
385 | transfer control directly to other code outside of libunwind. The framework |
---|
386 | does not provide any assistance here. |
---|
387 | |
---|
388 | \begin{sloppypar} |
---|
389 | Its arguments are the same as the paired personality function. The actions |
---|
390 | @_UA_CLEANUP_PHASE@ and @_UA_FORCE_UNWIND@ are always set when it is |
---|
391 | called. Beyond the libunwind standard, both GCC and Clang add an extra action |
---|
392 | on the last call at the end of the stack: @_UA_END_OF_STACK@. |
---|
393 | \end{sloppypar} |
---|
394 | |
---|
395 | \section{Exception Context} |
---|
396 | % Should I have another independent section? |
---|
397 | % There are only two things in it, top_resume and current_exception. How it is |
---|
398 | % stored changes depending on whether or not the thread-library is linked. |
---|
399 | |
---|
400 | The exception context is global storage used to maintain data across different |
---|
401 | exception operations and to communicate among different components. |
---|
402 | |
---|
403 | Each stack must have its own exception context. In a sequential \CFA program, |
---|
404 | there is only one stack with a single global exception-context. However, when |
---|
405 | the library @libcfathread@ is linked, there are multiple stacks, where each |
---|
406 | needs its own exception context. |
---|
407 | |
---|
408 | The function @this_exception_context@ provides general access to the exception context. |
---|
409 | For sequential execution, this function is defined as |
---|
410 | a weak symbol in the \CFA system-library, @libcfa@. When a \CFA program is |
---|
411 | concurrent, it links with @libcfathread@, where this function is defined with a |
---|
412 | strong symbol replacing the sequential version. |
---|
413 | |
---|
414 | The sequential @this_exception_context@ returns a hard-coded pointer to the |
---|
415 | global exception context. |
---|
416 | The concurrent version adds the exception context to the data stored at the |
---|
417 | base of each stack. When @this_exception_context@ is called, it retrieves the |
---|
418 | active stack and returns the address of the context saved there. |
---|
419 | |
---|
420 | \section{Termination} |
---|
421 | % Memory management & extra information, the custom function used to implement |
---|
422 | % catches. Talk about GCC nested functions. |
---|
423 | |
---|
424 | Termination exceptions use libunwind heavily because \CFA termination exceptions match |
---|
425 | \Cpp exceptions closely. The main complication for \CFA is that the |
---|
426 | compiler generates C code, making it very difficult to generate the assembly to |
---|
427 | form the LSDA for try blocks or destructors. |
---|
428 | |
---|
429 | \subsection{Memory Management} |
---|
430 | The first step of a termination raise is to copy the exception into memory |
---|
431 | managed by the exception system. Currently, the system uses @malloc@, rather |
---|
432 | than reserved memory or the stack top. The exception-handling mechanism manages |
---|
433 | memory for the exception as well as memory for libunwind and the system's own |
---|
434 | per-exception storage. |
---|
435 | |
---|
436 | \begin{figure} |
---|
437 | \begin{verbatim} |
---|
438 | Fixed Header | _Unwind_Exception <- pointer target |
---|
439 | | |
---|
440 | | Cforall storage |
---|
441 | | |
---|
442 | Variable Body | the exception <- fixed offset |
---|
443 | V ... |
---|
444 | \end{verbatim} |
---|
445 | \caption{Exception Layout} |
---|
446 | \label{f:ExceptionLayout} |
---|
447 | \end{figure} |
---|
448 | |
---|
449 | Exceptions are stored in variable-sized blocks (see Figure~\vref{f:ExceptionLayout}). |
---|
450 | The first component is a fixed-sized data-structure that contains the |
---|
451 | information for libunwind and the exception system. The second component is an |
---|
452 | area of memory big enough to store the exception. Macros with pointer arthritic |
---|
453 | and type cast are used to move between the components or go from the embedded |
---|
454 | @_Unwind_Exception@ to the entire node. |
---|
455 | |
---|
456 | Multiple exceptions can exist because handlers can call functions that raise |
---|
457 | exceptions. Figure~\vref{f:MultipleExceptions} shows a \Cpp program where |
---|
458 | exceptions are handled, and then a function is called from the handler that |
---|
459 | raises a new exception. The previous exception must persist because it is |
---|
460 | unhandled, and hence, control can return to the handler and that exception is |
---|
461 | reraised. |
---|
462 | |
---|
463 | \begin{figure} |
---|
464 | \centering |
---|
465 | \newsavebox{\myboxA} |
---|
466 | \newsavebox{\myboxB} |
---|
467 | \begin{lrbox}{\myboxA} |
---|
468 | \begin{lstlisting}[language=C++,{moredelim=**[is][\color{red}]{@}{@}}] |
---|
469 | struct E {}; |
---|
470 | int cnt = 3; |
---|
471 | void f( int i ) { |
---|
472 | if ( i == 0 ) @throw E();@ |
---|
473 | try { |
---|
474 | @f( i - 1 );@ |
---|
475 | } catch( E ) { // handler h |
---|
476 | cnt -= 1; |
---|
477 | if ( cnt > 0 ) @f( 2 );@ |
---|
478 | } |
---|
479 | } |
---|
480 | int main() { @f( 2 );@ } |
---|
481 | \end{lstlisting} |
---|
482 | \end{lrbox} |
---|
483 | |
---|
484 | \begin{lrbox}{\myboxB} |
---|
485 | \begin{lstlisting} |
---|
486 | h $\makebox[0pt][l]{\textbackslash}f$ |
---|
487 | f |
---|
488 | f |
---|
489 | h $\makebox[0pt][l]{\textbackslash}f$ throw E$\(_2\)$ |
---|
490 | f |
---|
491 | f |
---|
492 | h $\makebox[0pt][l]{\textbackslash}f$ throw E$\(_1\)$ |
---|
493 | f |
---|
494 | f |
---|
495 | \end{lstlisting} |
---|
496 | \end{lrbox} |
---|
497 | |
---|
498 | {\usebox\myboxA} |
---|
499 | \hspace{25pt} |
---|
500 | {\usebox\myboxB} |
---|
501 | |
---|
502 | \caption{Multiple Exceptions} |
---|
503 | \label{f:MultipleExceptions} |
---|
504 | \end{figure} |
---|
505 | |
---|
506 | In this case, the exception nodes are linked together in a list, one list per stack, with the |
---|
507 | list head stored in the exception context. Within each linked list, the most |
---|
508 | recently thrown exception is at the head followed by older thrown |
---|
509 | exceptions. This format allows exceptions to be thrown, while a different |
---|
510 | exception is being handled. The exception at the head of the list is currently |
---|
511 | being handled, while other exceptions wait for the exceptions before them to be |
---|
512 | removed. |
---|
513 | |
---|
514 | The virtual members in the exception's virtual table provide the size of the |
---|
515 | exception, the copy function, and the free function, so they are specific to an |
---|
516 | exception type. The size and copy function are used immediately to copy an |
---|
517 | exception into managed memory. After the exception is handled, the free function |
---|
518 | is used to clean up the exception and then the entire node is passed to free |
---|
519 | so the memory can be given back to the heap. |
---|
520 | |
---|
521 | \subsection{Try Statements and Catch Clauses} |
---|
522 | The try statement with termination handlers is complex because it must |
---|
523 | compensate for the lack of assembly code generated from \CFA. Libunwind |
---|
524 | requires an LSDA and personality function for control to unwind across a |
---|
525 | function. The LSDA in particular is hard to mimic in generated C code. |
---|
526 | |
---|
527 | The workaround is a function called @__cfaehm_try_terminate@ in the standard |
---|
528 | library. The contents of a try block and the termination handlers are converted |
---|
529 | into functions. These are then passed to the try terminate function and it |
---|
530 | calls them. |
---|
531 | Because this function is known and fixed (and not an arbitrary function that |
---|
532 | happens to contain a try statement), this means the LSDA can be generated ahead |
---|
533 | of time. |
---|
534 | |
---|
535 | Both the LSDA and the personality function are set ahead of time using |
---|
536 | embedded assembly. This assembly code is handcrafted using C @asm@ statements and contains |
---|
537 | enough information for the single try statement the function represents. |
---|
538 | |
---|
539 | The three functions passed to try terminate are: |
---|
540 | \begin{description} |
---|
541 | \item[try function:] This function is the try block, all the code inside the |
---|
542 | try block is placed inside the try function. It takes no parameters and has no |
---|
543 | return value. This function is called during regular execution to run the try |
---|
544 | block. |
---|
545 | |
---|
546 | \item[match function:] This function is called during the search phase and |
---|
547 | decides if a catch clause matches the termination exception. It is constructed |
---|
548 | from the conditional part of each handler and runs each check, top to bottom, |
---|
549 | in turn, first checking to see if the exception type matches and then if the |
---|
550 | condition is true. It takes a pointer to the exception and returns 0 if the |
---|
551 | exception is not handled here. Otherwise the return value is the id of the |
---|
552 | handler that matches the exception. |
---|
553 | |
---|
554 | \item[handler function:] This function handles the exception. It takes a |
---|
555 | pointer to the exception and the handler's id and returns nothing. It is called |
---|
556 | after the cleanup phase. It is constructed by stitching together the bodies of |
---|
557 | each handler and dispatches to the selected handler. |
---|
558 | \end{description} |
---|
559 | All three functions are created with GCC nested functions. GCC nested functions |
---|
560 | can be used to create closures, functions that can refer to the state of other |
---|
561 | functions on the stack. This approach allows the functions to refer to all the |
---|
562 | variables in scope for the function containing the @try@ statement. These |
---|
563 | nested functions and all other functions besides @__cfaehm_try_terminate@ in |
---|
564 | \CFA use the GCC personality function and the @-fexceptions@ flag to generate |
---|
565 | the LSDA. Through this mechanism, \CFA destructors are implemented via the cleanup attribute. |
---|
566 | |
---|
567 | \PAB{Try to put together an example try statement illustrating these components.} |
---|
568 | |
---|
569 | \section{Resumption} |
---|
570 | % The stack-local data, the linked list of nodes. |
---|
571 | |
---|
572 | Resumption is simpler to implement than termination because there is no stack |
---|
573 | unwinding. \PAB{You need to explain how the \lstinline{catchResume} clauses are |
---|
574 | handled. Do you use the personality mechanism in libunwind or do you roll your |
---|
575 | own mechanism?} |
---|
576 | |
---|
577 | The |
---|
578 | resumption raise uses a list of nodes for its stack traversal. The head of the |
---|
579 | list is stored in the exception context. The nodes in the list have a pointer |
---|
580 | to the next node and a pointer to the handler function. |
---|
581 | A resumption raise traverses this list. At each node the handler function is |
---|
582 | called, passing the exception by pointer. It returns true if the exception is |
---|
583 | handled and false otherwise. |
---|
584 | |
---|
585 | The handler function does both the matching and handling. It computes the |
---|
586 | condition of each @catchResume@ in top-to-bottom order, until it finds a |
---|
587 | handler that matches. If no handler matches then the function returns |
---|
588 | false. Otherwise the matching handler is run; if it completes successfully, the |
---|
589 | function returns true. Rethrowing, through the @throwResume;@ statement, |
---|
590 | causes the function to return true. |
---|
591 | |
---|
592 | % Recursive Resumption Stuff: |
---|
593 | Search skipping (see \vpageref{s:ResumptionMarking}), which ignores parts of |
---|
594 | the stack |
---|
595 | already examined, is accomplished by updating the front of the list as the |
---|
596 | search continues. Before the handler at a node is called, the head of the list |
---|
597 | is updated to the next node of the current node. After the search is complete, |
---|
598 | successful or not, the head of the list is reset. |
---|
599 | |
---|
600 | This mechanism means the current handler and every handler that has already |
---|
601 | been checked are not on the list while a handler is run. If a resumption is |
---|
602 | thrown during the handling of another resumption the active handlers and all |
---|
603 | the other handler checked up to this point are not checked again. |
---|
604 | |
---|
605 | This structure also supports new handlers added while the resumption is being |
---|
606 | handled. These are added to the front of the list, pointing back along the |
---|
607 | stack -- the first one points over all the checked handlers -- and the ordering |
---|
608 | is maintained. |
---|
609 | |
---|
610 | \PAB{Again, a figure to show how this works would be helpful.} |
---|
611 | |
---|
612 | \label{p:zero-cost} |
---|
613 | Note, the resumption implementation has a cost for entering/exiting a @try@ |
---|
614 | statement with @catchResume@ clauses, whereas a @try@ statement with @catch@ |
---|
615 | clauses has zero-cost entry/exit. While resumption does not need the stack |
---|
616 | unwinding and cleanup provided by libunwind, it could use the search phase to |
---|
617 | providing zero-cost enter/exit using the LSDA. Unfortunately, there is no way |
---|
618 | to return from a libunwind search without installing a handler or raising an |
---|
619 | error. Although workarounds might be possible, they are beyond the scope of |
---|
620 | this thesis. The current resumption implementation has simplicity in its |
---|
621 | favour. |
---|
622 | % Seriously, just compare the size of the two chapters and then consider |
---|
623 | % that unwind is required knowledge for that chapter. |
---|
624 | |
---|
625 | \PAB{This paragraph needs to be moved to the start of this Section, where I have have my other comment.} |
---|
626 | |
---|
627 | \section{Finally} |
---|
628 | % Uses destructors and GCC nested functions. |
---|
629 | A finally clause is placed into a GCC nested-function with a unique mangled name, and no |
---|
630 | arguments or return values. This nested function is then set as the cleanup |
---|
631 | function of an empty object that is declared at the beginning of a block placed |
---|
632 | around the context of an associated @try@ statement. |
---|
633 | |
---|
634 | The rest is handled by GCC. The try block and all handlers are inside this |
---|
635 | block. At completion, control exits the block and the empty object is cleaned |
---|
636 | up, which runs the function that contains the finally code. |
---|
637 | |
---|
638 | \section{Cancellation} |
---|
639 | % Stack selections, the three internal unwind functions. |
---|
640 | |
---|
641 | Cancellation also uses libunwind to do its stack traversal and unwinding, |
---|
642 | however it uses a different primary function, @_Unwind_ForcedUnwind@. Details |
---|
643 | of its interface can be found in Section~\vref{s:ForcedUnwind}. |
---|
644 | |
---|
645 | The first step of cancellation is to find the cancelled stack and its type: |
---|
646 | coroutine or thread. Fortunately, the thread library stores the program-main thread |
---|
647 | pointer and the current-thread pointer, and every thread stores a pointer to |
---|
648 | the current coroutine it is executing. |
---|
649 | |
---|
650 | \PAB{I don't know if my corrections in the previous paragraph are correct.} |
---|
651 | |
---|
652 | When the active thread and coroutine are the same, the current stack is the thread stack, otherwise it is a coroutine |
---|
653 | stack. |
---|
654 | % PAB: repeated? |
---|
655 | % If it is a thread stack, then an equality check with the stored main |
---|
656 | % thread pointer and current thread pointer is enough to tell if the current |
---|
657 | % thread is the main thread or not. |
---|
658 | However, if the threading library is not linked, the sequential execution is on |
---|
659 | the main stack. Hence, the entire check is skipped because the weak-symbol |
---|
660 | function is loaded. Therefore, a main thread cancellation is unconditionally |
---|
661 | performed. |
---|
662 | |
---|
663 | Regardless of how the stack is chosen, the stop function and parameter are |
---|
664 | passed to the forced-unwind function. The general pattern of all three stop |
---|
665 | functions is the same: continue unwinding until the end of stack. |
---|
666 | %when they |
---|
667 | %do there primary work. |
---|
668 | For main stack cancellation, the transfer is just a program abort. |
---|
669 | |
---|
670 | For coroutine cancellation, the exception is stored in the coroutine's stack, |
---|
671 | and the coroutine context switches to its last resumer. The rest is handled on |
---|
672 | the backside of the resume, which check if the resumed coroutine is |
---|
673 | cancelled. If cancelled, the exception is retrieved from the resumed coroutine, |
---|
674 | and a @CoroutineCancelled@ exception is constructed and loaded with the |
---|
675 | cancelled exception. It is then resumed as a regular exception with the default |
---|
676 | handler coming from the context of the resumption call. |
---|
677 | |
---|
678 | For thread cancellation, the exception is stored on the thread's main stack and |
---|
679 | then context switched to the scheduler. The rest is handled by the thread |
---|
680 | joiner. When the join is complete, the joiner checks if the joined thread is |
---|
681 | cancelled. If cancelled, the exception is retrieved and the joined thread, and |
---|
682 | a @ThreadCancelled@ exception is constructed and loaded with the cancelled |
---|
683 | exception. The default handler is passed in as a function pointer. If it is |
---|
684 | null (as it is for the auto-generated joins on destructor call), the default is |
---|
685 | used, which is a program abort. |
---|
686 | %; which gives the required handling on implicate join. |
---|