source: doc/theses/andrew_beach_MMath/unwinding.tex @ 1803d4d

ast-experimental
Last change on this file since 1803d4d was 9af0fe2d, checked in by Andrew Beach <ajbeach@…>, 4 years ago

Got rid of the remaining \texorpdfstring commands.

  • Property mode set to 100644
File size: 10.1 KB
Line 
1\chapter{Unwinding in \CFA}
2
3Stack unwinding is the process of removing stack frames (activations) from the
4stack. On function entry and return, unwinding is handled directly by the code
5embedded in the function. Usually, the stack-frame size is known statically
6based on parameters and local variable declarations.  For dynamically-sized
7local variables, a runtime computation is necessary to know the frame
8size. Finally, a function's frame-size may change during execution as local
9variables (static or dynamic sized) go in and out of scope.
10Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
11bumping the hardware stack-pointer up or down as needed.
12
13Unwinding across multiple stack frames is more complex because individual stack
14management code associated with each frame is bypassed. That is, the location
15of a function's frame code is largely unknown and dispersed throughout the
16function, hence the current stack-frame size managed by that code is also
17unknown. Hence, code unwinding across frames does not have direct knowledge
18about what is on the stack, and hence, how much of the stack needs to be
19removed.
20
21The traditional unwinding mechanism for C is implemented by saving a snap-shot
22of a function's state with @setjmp@ and restoring that snap-shot with
23@longjmp@. This approach bypasses the need to know stack details by simply
24reseting to a snap-shot of an arbitrary but existing function frame on the
25stack. It is up to the programmer to ensure the snap-shot is valid when it is
26reset, making the code fragile with potential errors that are difficult to
27debug because the stack becomes corrupted.
28
29However, many languages define cleanup actions that have to be taken when
30something is deallocated from the stack or blocks end, such as running a
31variable's destructor or a @try@ statement's @finally@ clause. Handling these
32mechanisms requires walking the stack and checking each stack frame for these
33potential actions.
34
35For exceptions, it must be possible to walk the stack frames in search of try
36statements with handlers to perform exception matching. For termination
37exceptions, it must be possible to unwind all stack frames from the throw to
38the matching catch, and each of these frames must be checked for cleanup
39actions. Stack walking is where the most of the complexity and expense of
40exception handling comes from.
41
42One of the most popular tools for stack management is libunwind, a low level
43library that provides tools for stack walking and unwinding. What follows is an
44overview of all the relevant features of libunwind and how \CFA uses them to
45implement its exception handling.
46
47\section{libunwind Usage}
48\CFA uses two primary functions in libunwind to create most of its exceptional
49control-flow: @_Unwind_RaiseException@ and @_Unwind_ForcedUnwind@.  Their
50operation is divided into two phases: search and clean-up. The search phase --
51phase 1 -- is used to scan the stack but not unwinding it. The clean-up phase
52-- phase 2 -- is used for unwinding.
53
54The raise-exception function uses both phases. It starts by searching for a
55handler, and if found, performs a clean-up phase to unwind the stack to the
56handler. If a handler is not found, control returns allowing the
57exception-handling policy for unhandled exception to be executed. During both
58phases, the raise-exception function searches down the stack, calling each
59function's \emph{personality function}.
60
61A personality function performs three tasks, although not all have to be
62present. The tasks performed are decided by the actions provided.
63@_Unwind_Action@ is a bitmask of possible actions and an argument of this type
64is passed into the personality function.
65\begin{itemize}
66\item
67\begin{sloppypar}
68@_UA_SEARCH_PHASE@ is passed in for the search phase and tells the personality
69function to check for handlers. If there is a handler in a stack frame, as
70defined by the language, the personality function returns @_URC_HANDLER_FOUND@;
71otherwise it return @_URC_CONTINUE_UNWIND@.
72\end{sloppypar}
73\item
74@_UA_CLEANUP_PHASE@ is passed in during the clean-up phase and means part or
75all of the stack frame is removed. The personality function does whatever
76clean-up the language defines (such as running destructors/finalizers) and then
77generally returns @_URC_CONTINUE_UNWIND@.
78\item
79@_UA_HANDLER_FRAME@ means the personality function must install a handler. It
80is also passed in during the clean-up phase and is in addition to the clean-up
81action. libunwind provides several helpers for the personality function. Once
82it is done, the personality function returns @_URC_INSTALL_CONTEXT@.
83\end{itemize}
84The personality function is given a number of other arguments. Some arguments
85are for compatibility, and there is the @struct _Unwind_Context@ pointer which
86is passed to many helpers to get information about the current stack frame.
87
88For cancellation, forced-unwind only performs the clean-up phase. It takes
89three arguments: a pointer to the exception, a pointer to the stop function and
90a pointer to the stop parameter. It does most of the same actions as phase two
91of raise-exception but passes in an extra action to the personality function on
92each stack frame, @_UA_FORCE_UNWIND@, which means a handler cannot be
93installed.
94
95As well, forced-unwind calls the stop function each time it steps into a frame,
96before calling the personality function. The stop function receives all the
97same arguments as the personality function and the stop parameter supplied to
98forced-unwind.
99
100The stop function is called one more time at the end of the stack after all
101stack frames have been removed. The standard API marks this frame by setting
102the stack pointer inside the context passed to the stop function. However both
103GCC and Clang add an extra action for this case @_UA_END_OF_STACK@.
104
105Each time the stop function is called, it can do one or two things.  When it is
106not the end of the stack it can return @_URC_NO_REASON@ to continue unwinding.
107% Is there a reason that NO_REASON is used instead of CONTINUE_UNWIND?
108The other option is to use some other means to transfer control elsewhere and
109never return to its caller. libunwind provides no additional tools for
110alternate transfers of control.
111
112\section{\CFA Implementation}
113
114To use libunwind, \CFA provides several wrappers, its own storage, personality
115functions, and a stop function.
116
117The wrappers perform three tasks: set-up, clean-up and controlling the
118unwinding. The set-up allocates a copy of the \CFA exception into a handler to
119control its lifetime, and stores it in the exception context. Clean-up -- run
120when control exits a catch clause and returns to normal code -- frees the
121exception copy.
122% It however does not set up the unwind exception so we can't use any inter-
123% runtime/language features. Also the exception context is global.
124
125The core control code is called every time a throw -- after set-up -- or
126re-throw is run. It uses raise-exception to search for a handler and to run it
127if one is found. If no handler is found and raise-exception returns, then
128forced-unwind is called to run all destructors on the stack before terminating
129the process.
130
131The stop function is simple. It checks for the end of stack flag to see if
132unwinding is finished. If so, it calls @exit@ to end the process, otherwise it
133returns with no-reason to continue unwinding.
134% Yeah, this is going to have to change.
135
136The personality routine is more complex because it has to obtain information
137about the function by scanning the Language Specific Data Area (LSDA). This
138step allows a single personality function to be used for multiple functions and
139lets that personality function figure out exactly where in the function
140execution is, what is currently in the stack frame, and what handlers should be
141checked.
142% Not that we do that yet.
143
144It is also necessary to generate the LSDA, which is difficult. It requires
145knowledge about the location of the instruction pointer and stack layout, which
146varies with compiler and optimization levels. Fortunately, for frames where
147there are only destructors, GCC's attribute cleanup with the @-fexception@ flag
148is sufficient to handle unwinding.
149
150The only functions that require more information are those containing @try@
151statements. Specifically, only @try@ statements with @catch@ clauses need to be
152transformed.  The @try@ statement is converted into a series of closures that
153can access other parts of the function according to scoping rules but can be
154passed around. The @catch@ clauses are converted into two functions: the match
155function and the handler function.
156
157Together the match function and the catch function form the code that runs when
158an exception passes out of the guarded block for a try statement. The match
159function is used during the search phase: it is passed an exception and checks
160each handler to see if the raised exception matches the handler exception. It
161returns an index that represents which handler matched or there is no
162match. The catch function is used during the clean-up phase, it is passed an
163exception and the index of a handler. It casts the exception to the exception
164type declared in that handler and then runs the handler's body.
165
166These three functions are passed to @try_terminate@, which is an
167% Maybe I shouldn't quote that, it isn't its actual name.
168internal hand-written function that has its own personality function and custom
169assembly LSDA for doing the exception handling in \CFA. During normal
170execution, this function calls the try function and then return.  It is only
171when exceptions are thrown that anything interesting happens.
172
173During the search phase the personality function gets the pointer to the match
174function and calls it. If the match function returns a handler index, the
175personality function saves it and reports that the handler has been found,
176otherwise unwinding continues.  During the clean-up phase, the personality
177function only performs an action, when a handler is found in a frame. For each
178found frame, the personality function installs the handler, which sets the
179instruction pointer in @try_terminate@ to an otherwise unused section that
180calls the catch function, passing it the current exception and handler index.
181@try_terminate@ returns as soon as the catch function returns.  At this point
182control has returned to normal control flow.
183
184\PAB{Maybe a diagram would be helpful?}
Note: See TracBrowser for help on using the repository browser.