source: doc/theses/andrew_beach_MMath/unwinding.tex@ f33eab7

\chapter{Unwinding in \CFA}

Stack unwinding is the process of removing things from the stack. Within
functions and on function return this is handled directly by the code in the
function itself as it knows exactly what is on the stack just from the
current location in the function. Unwinding across stack frames means that it
is no longer knows exactly what is on the stack or even how much of the stack
needs to be removed.

Even this is fairly simple if nothing needs to happen when the stack unwinds.
Traditional C can unwind the stack by saving and restoring state (with
\codeC{setjmp} \& \codeC{longjmp}). However many languages define actions that
have to be taken when something is removed from the stack, such as running
a variable's destructor or a \codeCFA{try} statement's \codeCFA{finally}
clause. Handling this requires walking the stack going through each stack
frame.

For exceptions, this means everything from the point the exception is raised
to the point it is caught, while checking each frame for handlers during the
stack walk to find out where it should be caught. This is where the most of
the expense and complexity of exception handling comes from.

To do all of this we use libunwind, a low level library that provides tools
for stack walking and stack unwinding. What follows is an overview of all the
relivant features of libunwind and then 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: \codeC{_Unwind_RaiseException} and
\codeC{_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.
\codeC{_Unwind_Action} is a bitmask of possible actions and an argument of
this type is passed into the personality function.
\begin{itemize}
\item\codeC{_UA_SEARCH_PHASE} is passed in search phase and tells the
personality function to check for handlers. If there is a handler in this
stack frame, as defined by the language, the personality function should
return \codeC{_URC_HANDLER_FOUND}. Otherwise it should return
\codeC{_URC_CONTINUE_UNWIND}.
\item\codeC{_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
should do whatever clean-up the language defines
(such as running destructors/finalizers) and then generally returns
\codeC{_URC_CONTINUE_UNWIND}.
\item\codeC{_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 here. Once it is done, the personality function must return
\codeC{_URC_INSTALL_CONTEXT}.
\end{itemize}
The personality function is given a number of other arguments. Some are for
compatability and there is the \codeC{struct _Unwind_Context} pointer which
passed to many helpers to get information about the current stack frame.

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 things as phase two of
raise-exception but with some extras.
The first it passes in an extra action to the personality function on each
stack frame, \codeC{_UA_FORCE_UNWIND}, which means a handler cannot be
installed.

The big change is that forced-unwind calls the stop function. Each time it
steps into a frame, before calling the personality function, it calls the
stop function. The stop function receives all the same arguments as the
personality function will 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. By the standard API this is marked 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 \codeC{_UA_END_OF_STACK}.

Each time function the stop function is called it can do one or two things.
When it is not the end of the stack it can return \codeC{_URC_NO_REASON} to
continue unwinding.
% Is there a reason that NO_REASON is used instead of CONTINUE_UNWIND?
Its only other option is to use its own means to transfer control elsewhere
and never return to its caller. It may always do this and no additional tools
are provided to do it.

\section{\CFA 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 very simple. It checks the end of stack flag to see if
it is finished unwinding. If so, it calls \codeC{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 LSDA (Language Specific Data Area). This
step allows a single personality function to be used for multiple functions and
let that personaliity function figure out exactly where in the function
execution was, what is currently in the stack frame and what handlers should
be checked.
% Not that we do that yet.

However, generating the LSDA is difficult. It requires knowledge about the
location of the instruction pointer and stack layout, which varies with
compiler and optimization levels. So for frames where there are only
destructors, GCC's attribute cleanup with the \texttt{-fexception} flag is
sufficient to handle unwinding.

The only functions that require more than that are those that contain
\codeCFA{try} statements. A \codeCFA{try} statement has a \codeCFA{try}
clause, some number of \codeCFA{catch} clauses and \codeCFA{catchResume}
clauses and may have a \codeCFA{finally} clause. Of these only \codeCFA{try}
statements with \codeCFA{catch} clauses need to be transformed and only they
and the \codeCFA{try} clause are involved.

The \codeCFA{try} statement is converted into a series of closures which can
access other parts of the function according to scoping rules but can be
passed around. The \codeCFA{try} clause is converted into the try functions,
almost entirely unchanged. The \codeCFA{catch} clauses are converted into two
functions; the match function and the catch function.

Together the match function and the catch function form the code that runs
when an exception passes out of a try block. The match function is used during
the search phase, it is passed an exception and checks each handler to see if
it will handle the exception. It returns an index that repersents which
handler matched or that none of them did. 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 \codeC{try_terminate}. This 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 LSD does the exception handling in \CFA. During normal
execution all this function does is call 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 does anything if the
handler was found in this frame. If it was then the personality function
installs the handler, which is setting the instruction pointer in
\codeC{try_terminate} to an otherwise unused section that calls the catch
function, passing it the current exception and handler index.
\codeC{try_terminate} returns as soon as the catch function returns.

At this point control has returned to normal control flow.