source: doc/theses/andrew_beach_MMath/unwinding.tex @ 2b878b4

\chapter{\texorpdfstring{Unwinding in \CFA}{Unwinding in Cforall}}

Stack unwinding is the process of removing stack frames (activations) from the
stack. On function entry and return, unwinding is handled directly by the code
embedded in the function. Usually, the stack-frame size is known statically
based on parameters and local variable declarations.  For dynamically-sized
local variables, a runtime computation is necessary to know the frame
size. Finally, a function's frame-size may change during execution as local
variables (static or dynamic sized) go in and out of scope.
Allocating/deallocating stack space is usually an $O(1)$ operation achieved by
bumping the hardware stack-pointer up or down as needed.

Unwinding across multiple stack frames is more complex because individual stack
management code associated with each frame is bypassed. That is, the location
of a function's frame code is largely unknown and dispersed throughout the
function, hence the current stack-frame size managed by that code is also
unknown. Hence, code unwinding across frames does not have direct knowledge
about what is on the stack, and hence, how much of the stack needs to be
removed.

The traditional unwinding mechanism for C is implemented by saving a snap-shot
of a function's state with @setjmp@ and restoring that snap-shot with
@longjmp@. This approach bypasses the need to know stack details by simply
reseting to a snap-shot of an arbitrary but existing function frame on the
stack. It is up to the programmer to ensure the snap-shot is valid when it is
reset, making the code fragile with potential errors that are difficult to
debug because the stack becomes corrupted.

However, many languages define cleanup actions that have to be taken when
something is deallocated from the stack or blocks end, such as running a
variable's destructor or a @try@ statement's @finally@ clause. Handling these
mechanisms requires walking the stack and checking each stack frame for these
potential actions.

For exceptions, it must be possible to walk the stack frames in search of try
statements with handlers to perform exception matching. For termination
exceptions, it must be possible to unwind all stack frames from the throw to
the matching catch, and each of these frames must be checked for cleanup
actions. Stack walking is where the most of the complexity and expense of
exception handling comes from.

One of the most popular tools for stack management is libunwind, a low level
library that provides tools for stack walking and unwinding. What follows is an
overview of all the relevant features of libunwind and how \CFA uses them to
implement its exception handling.

\section{libunwind Usage}
\CFA uses two primary functions in libunwind to create most of its exceptional
control-flow: @_Unwind_RaiseException@ and @_Unwind_ForcedUnwind@.  Their
operation is divided into two phases: search and clean-up. The search phase --
phase 1 -- is used to scan the stack but not unwinding it. The clean-up phase
-- phase 2 -- is used for unwinding.

The raise-exception function uses both phases. It starts by searching for a
handler, and if found, performs a clean-up phase to unwind the stack to the
handler. If a handler is not found, control returns allowing the
exception-handling policy for unhandled exception to be executed. During both
phases, the raise-exception function searches down the stack, calling each
function's \emph{personality function}.

A personality function performs three tasks, although not all have to be
present. The tasks performed are decided by the actions provided.
@_Unwind_Action@ is a bitmask of possible actions and an argument of this type
is passed into the personality function.
\begin{itemize}
\item
\begin{sloppypar}
@_UA_SEARCH_PHASE@ is passed in for the search phase and tells the personality
function to check for handlers. If there is a handler in a stack frame, as
defined by the language, the personality function returns @_URC_HANDLER_FOUND@;
otherwise it return @_URC_CONTINUE_UNWIND@.
\end{sloppypar}
\item
@_UA_CLEANUP_PHASE@ is passed in during the clean-up phase and means part or
all of the stack frame is removed. The personality function does whatever
clean-up the language defines (such as running destructors/finalizers) and then
generally returns @_URC_CONTINUE_UNWIND@.
\item
@_UA_HANDLER_FRAME@ means the personality function must install a handler. It
is also passed in during the clean-up phase and is in addition to the clean-up
action. libunwind provides several helpers for the personality function. Once
it is done, the personality function returns @_URC_INSTALL_CONTEXT@.
\end{itemize}
The personality function is given a number of other arguments. Some arguments
are for compatibility, and there is the @struct _Unwind_Context@ pointer which
is passed to many helpers to get information about the current stack frame.

For cancellation, forced-unwind only performs the clean-up phase. It takes
three arguments: a pointer to the exception, a pointer to the stop function and
a pointer to the stop parameter. It does most of the same actions as phase two
of raise-exception but passes in an extra action to the personality function on
each stack frame, @_UA_FORCE_UNWIND@, which means a handler cannot be
installed.

As well, forced-unwind calls the stop function each time it steps into a frame,
before calling the personality function. The stop function receives all the
same arguments as the personality function and the stop parameter supplied to
forced-unwind.

The stop function is called one more time at the end of the stack after all
stack frames have been removed. The standard API marks this frame by setting
the stack pointer inside the context passed to the stop function. However both
GCC and Clang add an extra action for this case @_UA_END_OF_STACK@.

Each time the stop function is called, it can do one or two things.  When it is
not the end of the stack it can return @_URC_NO_REASON@ to continue unwinding.
% Is there a reason that NO_REASON is used instead of CONTINUE_UNWIND?
The other option is to use some other means to transfer control elsewhere and
never return to its caller. libunwind provides no additional tools for
alternate transfers of control.

\section{\texorpdfstring{\CFA Implementation}{Cforall Implementation}}

To use libunwind, \CFA provides several wrappers, its own storage, personality
functions, and a stop function.

The wrappers perform three tasks: set-up, clean-up and controlling the
unwinding. The set-up allocates a copy of the \CFA exception into a handler to
control its lifetime, and stores it in the exception context. Clean-up -- run
when control exits a catch clause and returns to normal code -- frees the
exception copy.
% It however does not set up the unwind exception so we can't use any inter-
% runtime/language features. Also the exception context is global.

The core control code is called every time a throw -- after set-up -- or
re-throw is run. It uses raise-exception to search for a handler and to run it
if one is found. If no handler is found and raise-exception returns, then
forced-unwind is called to run all destructors on the stack before terminating
the process.

The stop function is simple. It checks for the end of stack flag to see if
unwinding is finished. If so, it calls @exit@ to end the process, otherwise it
returns with no-reason to continue unwinding.
% Yeah, this is going to have to change.

The personality routine is more complex because it has to obtain information
about the function by scanning the Language Specific Data Area (LSDA). This
step allows a single personality function to be used for multiple functions and
lets that personality function figure out exactly where in the function
execution is, what is currently in the stack frame, and what handlers should be
checked.
% Not that we do that yet.

It is also necessary to generate the LSDA, which is difficult. It requires
knowledge about the location of the instruction pointer and stack layout, which
varies with compiler and optimization levels. Fortunately, for frames where
there are only destructors, GCC's attribute cleanup with the @-fexception@ flag
is sufficient to handle unwinding.

The only functions that require more information are those containing @try@
statements. Specifically, only @try@ statements with @catch@ clauses need to be
transformed.  The @try@ statement is converted into a series of closures that
can access other parts of the function according to scoping rules but can be
passed around. The @catch@ clauses are converted into two functions: the match
function and the handler function.

Together the match function and the catch function form the code that runs when
an exception passes out of the guarded block for a try statement. The match
function is used during the search phase: it is passed an exception and checks
each handler to see if the raised exception matches the handler exception. It
returns an index that represents which handler matched or there is no
match. The catch function is used during the clean-up phase, it is passed an
exception and the index of a handler. It casts the exception to the exception
type declared in that handler and then runs the handler's body.

These three functions are passed to @try_terminate@, which is an
% Maybe I shouldn't quote that, it isn't its actual name.
internal hand-written function that has its own personality function and custom
assembly LSDA for doing the exception handling in \CFA. During normal
execution, this function calls the try function and then return.  It is only
when exceptions are thrown that anything interesting happens.

During the search phase the personality function gets the pointer to the match
function and calls it. If the match function returns a handler index, the
personality function saves it and reports that the handler has been found,
otherwise unwinding continues.  During the clean-up phase, the personality
function only performs an action, when a handler is found in a frame. For each
found frame, the personality function installs the handler, which sets the
instruction pointer in @try_terminate@ to an otherwise unused section that
calls the catch function, passing it the current exception and handler index.
@try_terminate@ returns as soon as the catch function returns.  At this point
control has returned to normal control flow.

{\color{blue}PAB: Maybe a diagram would be helpful?}