Index: doc/theses/andrew_beach_MMath/thesis.tex =================================================================== --- doc/theses/andrew_beach_MMath/thesis.tex (revision 1ef166d6732e0303cc7327d078209f280573c73b) +++ doc/theses/andrew_beach_MMath/thesis.tex (revision 21f914e529861baff6600bbcda477f8adfcca722) @@ -1,6 +1,59 @@ % Main tex file for thesis document. \documentclass[digital]{uw-ethesis} +\usepackage{comment} \usepackage{fullpage} \setlength{\textheight}{8.75in} + +\usepackage{listings} % format program code +% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore +% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR +% AFTER HYPERREF. +%\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}} +\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}} +% parindent is relative, i.e., toggled on/off in environments like itemize, so store the value for +% use rather than use \parident directly. +\newlength{\parindentlnth} +\setlength{\parindentlnth}{\parindent} + +% CFA programming language, based on ANSI C (with some gcc additions) +\lstdefinelanguage{CFA}[ANSI]{C}{ + morekeywords={ + _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__, + auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__, + coroutine, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally, + __float80, float80, __float128, float128, forall, ftype, generator, _Generic, _Imaginary, __imag, __imag__, + inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or, + otype, restrict, resume, __restrict, __restrict__, __signed, __signed__, _Static_assert, suspend, thread, + _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__, + virtual, __volatile, __volatile__, waitfor, when, with, zero_t}, + moredirectives={defined,include_next}, + % replace/adjust listing characters that look bad in sanserif + literate={-}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1 + {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1 + {<}{\textrm{\textless}}1 {>}{\textrm{\textgreater}}1 + {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textrm{\textgreater}}}2, +} + +\lstset{ +language=CFA, +columns=fullflexible, +basicstyle=\linespread{0.9}\tt, % reduce line spacing and use sanserif font +stringstyle=\tt, % use typewriter font +tabsize=5, % N space tabbing +xleftmargin=\parindentlnth, % indent code to paragraph indentation +%mathescape=true, % LaTeX math escape in CFA code $...$ +escapechar=\$, % LaTeX escape in CFA code +keepspaces=true, +showstringspaces=false, % do not show spaces with cup +showlines=true, % show blank lines at end of code +aboveskip=4pt, % spacing above/below code block +belowskip=3pt, +moredelim=**[is][\color{red}]{`}{`}, +}% lstset + +\lstnewenvironment{cfa}[1][] +{\lstset{#1}} +{} +% inline code @...@ % Commands used in documenting how to use the template. To remove. @@ -65,4 +118,7 @@ each dimensional component is determined by a random process} } + +% Must be here of cause problems with glossaries-extra. +\lstMakeShortInline$% % Generate the glossaries defined above. Index: doc/theses/andrew_beach_MMath/unwinding.tex =================================================================== --- doc/theses/andrew_beach_MMath/unwinding.tex (revision 1ef166d6732e0303cc7327d078209f280573c73b) +++ doc/theses/andrew_beach_MMath/unwinding.tex (revision 21f914e529861baff6600bbcda477f8adfcca722) @@ -1,84 +1,105 @@ \chapter{Unwinding in \CFA} -Stack unwinding is the process of removing things from the stack from outside -the functions there. In languages that don't provide a way to garrenty that -code will run when the program leaves a scope or finishes a function, this -can be relatively trivial. C does this with \codeC{longjmp} by setting the -stack pointer and a few other registers. +When a function returns, a \emph{single} stack frame is unwound, removing the +function's parameters and local variables, and control continues in the +function caller using the caller's stack frame. When an exception is raised, +\emph{multiple} stack frames are unwound, removing the function parameters and +local variables for called functions from the exception raise-frame to the +exception catch-frame. + +Unwinding multiple levels is simple for a programming languages without object +destructors or block finalizers because a direct transfer is possible from the +current stack frame to a prior stack frame, where control continues at a +location within the prior caller's function. For example, C provides non-local +transfer using $longjmp$, which stores a function's state including its +frame pointer and program counter, and simply reloads this information to +continue at this prior location on the stack. + +For programming languages with object destructors or block finalizers it is +necessary to walk the stack frames from raise to catch, checking for code that +must be executed as part of terminating each frame. Walking the stack has a +higher cost, and necessary information must available to detect +destructors/finalizers and call them. + +A powerful package to provide stack-walking capabilities is $libunwind$, +which is used in this work to provide exception handling in \CFA. The following +explains how $libunwind$ works and how it is used. + +% Stack unwinding is the process of removing things from the stack from outside +% the functions there. In languages that don't provide a way to guaranty that +% code will run when the program leaves a scope or finishes a function, this +% can be relatively trivial. C does this with $longjmp$ by setting the +% stack pointer and a few other registers. \section{libunwind Usage} -There are two primary functions that \CFA uses in libunwind that create most -of the control flow. These are \codeC{\_Unwind\_RaiseException} and -\codeC{\_Unwind\_ForcedUnwind}. +There are two primary functions that \CFA uses in $libunwind$ to create most of +the exceptional control-flow. These functions are +$_Unwind_RaiseException$ and $_Unwind_ForcedUnwind$. -Their operation is divided amoung two phases, search and clean-up. The search -phase -- phase 1 -- is used while scanning the stack while not actually -unwinding it while the clean-up phase -- phase 2 -- is used while the actual -unwinding is under way. +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 to during unwinding. % Somewhere around here I need to talk about the control structures. -% \codeC{\_Unwind\_Exception} is used to carry the API's universal data. Some +% $_Unwind_Exception$ is used to carry the API's universal data. Some % of this is internal, other fields are used to communicate between different % exception handling mechanisms in different runtimes. -% \codeC{\_Unwind\_Context} is an opaque data structure that is used to pass +% $_Unwind_Context$ is an opaque data structure that is used to pass % information to helper functions. -Raise exception can cover both phases. It starts by searching for the handler -and if it finds it preforms a clean-up phase to unwind the stack to the -hander. If not it returns allowing the program to decide what to do with all -the state and stack that were in place before the call. During both phases -the raise exception function will search down the stack, calling each -function's personality function as they are found. +The raise-exception function uses both phases. It starts by searching for the +handler, and if found, performs a clean-up phase to unwind the stack to the +hander. 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}. -Personality functions must be able to preform three tasks, although not all -of them have to be preformed in a given call. Which tasks must be preformed -are decided by the actions provided. +A personality function performs three tasks, although not all of them have to +be present. The tasks performed are decided by the actions provided. % Something argument something bitmask. \begin{itemize} -\item\codeC{\_UA\_SEARCH\_PHASE} this is being called during the clean-up -phase and means search for handlers. If the hander is found the personality -function should return \codeC{\_URC\_HANDLER\_FOUND}, otherise it should -return \codeC{\_URC\_CONTINUE\_UNWIND}. -\item\codeC{\_UA\_CLEANUP\_PHASE} is passed in during the clean-up phase and -means that part or all of the stack frame is being removed. The personality -function should do whatever clean-up the language defines (such as running -destructors) and then generally returns \codeC{\_URC\_CONTINUE\_UNWIND}. -\item\codeC{\_UA\_HANDLER\_FRAME} means that the personality function must -install a handler. It is also passing in during the clean-up phase and will -be 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}. +\item$_UA_SEARCH_PHASE$ is called during the clean-up phase and means search +for handlers. If the hander is found, the personality function should return +$_URC_HANDLER_FOUND$, otherwise it returns $_URC_CONTINUE_UNWIND$. +\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 should do +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 here. Once it is done, the personality function must return +$_URC_INSTALL_CONTEXT$. \end{itemize} -Forced unwind only preforms the clean-up phase. It is similar to the phase 2 -section of raise exception with a few changes. A simple one is that -it passes in an extra action to the personality function -\codeC{\_UA\_FORCE\_UNWIND} which means a handler cannot be installed. The -most significant is the addition of the stop function, which is passed in as -an argument to the forced unwind. +Forced unwind only performs the clean-up phase. It is similar to the phase 2 +section of raise exception with a few changes. A simple one is that it passes +in an extra action to the personality function $_UA_FORCE_UNWIND$, which means +a handler cannot be installed. The most significant is the addition of the $stop$ +function, which is passed in as an argument to the forced unwind. The stop function is a lot like a personality function. It takes an extra argument, a void pointer passed into force unwind. It may return -\codeC{\_URC\_NO\_REASON} to continue unwinding or it can transfer control -out of the unwind code using its own mechanism. +$_URC_NO_REASON$ to continue unwinding or it can transfer control out of the +unwind code using its own mechanism. % Is there a reason that NO_REASON is used instead of CONTINUE_UNWIND? The stop function is called once on every stack frame and once at the end of -the stack. In a stack frame it is called before the personality routine with +the stack. In a stack frame, it is called before the personality routine with the same arguments (except for the extra void pointer). At the end of the -stack the arguments are mostly the same, except the stack pointer stored in -the context is set to null. Because of the significance of that change both -GCC and Clang add an extra action in this case \codeC{\_UA\_END\_OF\_STACK}. -The stop function may not return at the end of the stack. +stack, the arguments are mostly the same, except the stack pointer stored in +the context is set to null. Because of the significance of that change, both +GCC and Clang add an extra action in this case $_UA_END_OF_STACK$. The stop +function may not return at the end of the stack. \section{\CFA Implementation} -To use libunwind \CFA provides several wrappers, its own storage, the -personality functions and a stop function. +To use $libunwind$, \CFA provides several wrappers, its own storage, the +personality functions, and a stop function. -The wrappers preform three tasks: set-up, clean-up and controlling the -unwinding. The set-up allocates a copy of the \CFA exception into the hander -so it can control its lifetime and stores it in the exception context while -clean-up -- run when control exits a catch clause and return to normal code -- +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 +so it can control its lifetime, and stores it in the exception context. +Clean-up -- run when control exits a catch clause and return to normal code -- frees the exception copy. % It however does not set up the unwind exception so we can't use any inter- @@ -86,18 +107,18 @@ The control code in the middle is run every time a throw or re-throw is -called. It uses raise exception to search for a hander and to run it if one +called. It uses raise exception to search for a handler and to run it if one is found. Otherwise it uses forced unwind to unwind the stack, running all destructors, 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 exit to end the process, otherwise -it tells the system to continue unwinding. +The stop function is very simple, it checks the end of stack flag to see if it +is finished unwinding. If so, it calls exit to end the process, otherwise it +tells the system to continue unwinding. % Yeah, this is going to have to change. -The personality routine is much more complicated. -First because it has to get some information about the function by scanning -the LSDA (Language Specific Data Area). This allows a single personality -function to be used for multiple functions and it accounts for multiple -regions and possible handlers in a single function. +The personality routine is much more complicated. First, because it has to get +some information about the function by scanning the LSDA (Language Specific +Data Area). This allows a single personality function to be used for multiple +functions and it accounts for multiple regions and possible handlers in a +single function. % Not that we do that yet. @@ -113,8 +134,8 @@ unwinding. The clauses of the try block are then converted into GCC inner functions which can be passed around with function pointers while still having -access to the outer function's scope. \codeC{catchResume} and \codeC{finally} -clauses are handled seperately and will not be discussed here. +access to the outer function's scope. $catchResume$ and $finally$ +clauses are handled separately and will not be discussed here. -The \codeC{try} clause is convered to a function directly. The \codeC{catch} +The $try$ clause is converted to a function directly. The $catch$ clauses are combined and then create two functions. The first is the match function which is used during the search phase to see if any of the handler @@ -123,12 +144,12 @@ unwinding except for running destructors and so can be handled by GCC. -These three functions are passed into \codeC{try\_terminate}, an internal -function that repersents the try statement. This is the only function with +These three functions are passed into $try_terminate$, an internal +function that represents the try statement. This is the only function with our personality function as well as assembly statements that create the LSDA. In normal execution all the function does is call the try block closure and -return once that has finished executing. However using libunwind its +return once that has finished executing. However using $libunwind$ its personality function now handles exception matching and catching. -During the search phase the personality function retreaves the match function +During the search phase the personality function retrieves the match function from the stack using the saved stack pointer. The function is called, either returning 0 for no match or the index (a positive integer) of the handler @@ -137,5 +158,5 @@ During the clean-up phase there is nothing for the personality function to -clean-up in \codeC{try\_terminate}. So if this is not the handler frame -unwinding continues. If this is the handler frame than control is transfered +clean-up in $try_terminate$. So if this is not the handler frame +unwinding continues. If this is the handler frame than control is transferred to the catch function, giving it the exception and the handler index.