Changeset 21f914e for doc/theses


Ignore:
Timestamp:
Mar 17, 2020, 10:30:22 PM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
734c9664
Parents:
1ef166d
Message:

first pass over Chapter 1

Location:
doc/theses/andrew_beach_MMath
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/andrew_beach_MMath/thesis.tex

    r1ef166d r21f914e  
    11% Main tex file for thesis document.
    22\documentclass[digital]{uw-ethesis}
     3\usepackage{comment}
    34\usepackage{fullpage}
    45\setlength{\textheight}{8.75in}
     6
     7\usepackage{listings}                           % format program code
     8% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
     9% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
     10% AFTER HYPERREF.
     11%\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}
     12\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
     13% parindent is relative, i.e., toggled on/off in environments like itemize, so store the value for
     14% use rather than use \parident directly.
     15\newlength{\parindentlnth}
     16\setlength{\parindentlnth}{\parindent}
     17
     18% CFA programming language, based on ANSI C (with some gcc additions)
     19\lstdefinelanguage{CFA}[ANSI]{C}{
     20        morekeywords={
     21                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__,
     22                auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
     23                coroutine, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally,
     24                __float80, float80, __float128, float128, forall, ftype, generator, _Generic, _Imaginary, __imag, __imag__,
     25                inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
     26                otype, restrict, resume, __restrict, __restrict__, __signed, __signed__, _Static_assert, suspend, thread,
     27                _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
     28                virtual, __volatile, __volatile__, waitfor, when, with, zero_t},
     29        moredirectives={defined,include_next},
     30        % replace/adjust listing characters that look bad in sanserif
     31        literate={-}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1
     32                {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
     33                {<}{\textrm{\textless}}1 {>}{\textrm{\textgreater}}1
     34                {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textrm{\textgreater}}}2,
     35}
     36
     37\lstset{
     38language=CFA,
     39columns=fullflexible,
     40basicstyle=\linespread{0.9}\tt,                 % reduce line spacing and use sanserif font
     41stringstyle=\tt,                                % use typewriter font
     42tabsize=5,                                      % N space tabbing
     43xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
     44%mathescape=true,                               % LaTeX math escape in CFA code $...$
     45escapechar=\$,                                  % LaTeX escape in CFA code
     46keepspaces=true,
     47showstringspaces=false,                         % do not show spaces with cup
     48showlines=true,                                 % show blank lines at end of code
     49aboveskip=4pt,                                  % spacing above/below code block
     50belowskip=3pt,
     51moredelim=**[is][\color{red}]{`}{`},
     52}% lstset
     53
     54\lstnewenvironment{cfa}[1][]
     55{\lstset{#1}}
     56{}
     57% inline code @...@
    558
    659% Commands used in documenting how to use the template. To remove.
     
    65118               each dimensional component is determined by a random process}
    66119}
     120
     121% Must be here of cause problems with glossaries-extra.
     122\lstMakeShortInline$%
    67123
    68124% Generate the glossaries defined above.
  • doc/theses/andrew_beach_MMath/unwinding.tex

    r1ef166d r21f914e  
    11\chapter{Unwinding in \CFA}
    22
    3 Stack unwinding is the process of removing things from the stack from outside
    4 the functions there. In languages that don't provide a way to garrenty that
    5 code will run when the program leaves a scope or finishes a function, this
    6 can be relatively trivial. C does this with \codeC{longjmp} by setting the
    7 stack pointer and a few other registers.
     3When a function returns, a \emph{single} stack frame is unwound, removing the
     4function's parameters and local variables, and control continues in the
     5function caller using the caller's stack frame.  When an exception is raised,
     6\emph{multiple} stack frames are unwound, removing the function parameters and
     7local variables for called functions from the exception raise-frame to the
     8exception catch-frame.
     9
     10Unwinding multiple levels is simple for a programming languages without object
     11destructors or block finalizers because a direct transfer is possible from the
     12current stack frame to a prior stack frame, where control continues at a
     13location within the prior caller's function. For example, C provides non-local
     14transfer using $longjmp$, which stores a function's state including its
     15frame pointer and program counter, and simply reloads this information to
     16continue at this prior location on the stack.
     17
     18For programming languages with object destructors or block finalizers it is
     19necessary to walk the stack frames from raise to catch, checking for code that
     20must be executed as part of terminating each frame. Walking the stack has a
     21higher cost, and necessary information must available to detect
     22destructors/finalizers and call them.
     23
     24A powerful package to provide stack-walking capabilities is $libunwind$,
     25which is used in this work to provide exception handling in \CFA. The following
     26explains how $libunwind$ works and how it is used.
     27
     28% Stack unwinding is the process of removing things from the stack from outside
     29% the functions there. In languages that don't provide a way to guaranty that
     30% code will run when the program leaves a scope or finishes a function, this
     31% can be relatively trivial. C does this with $longjmp$ by setting the
     32% stack pointer and a few other registers.
    833
    934\section{libunwind Usage}
    1035
    11 There are two primary functions that \CFA uses in libunwind that create most
    12 of the control flow. These are \codeC{\_Unwind\_RaiseException} and
    13 \codeC{\_Unwind\_ForcedUnwind}.
     36There are two primary functions that \CFA uses in $libunwind$ to create most of
     37the exceptional control-flow. These functions are
     38$_Unwind_RaiseException$ and $_Unwind_ForcedUnwind$.
    1439
    15 Their operation is divided amoung two phases, search and clean-up. The search
    16 phase -- phase 1 -- is used while scanning the stack while not actually
    17 unwinding it while the clean-up phase -- phase 2 -- is used while the actual
    18 unwinding is under way.
     40Their operation is divided into two phases: search and clean-up. The search
     41phase -- phase 1 -- is used to scan the stack but not unwinding it. The
     42clean-up phase -- phase 2 -- is used to during unwinding.
    1943
    2044% Somewhere around here I need to talk about the control structures.
    21 % \codeC{\_Unwind\_Exception} is used to carry the API's universal data. Some
     45% $_Unwind_Exception$ is used to carry the API's universal data. Some
    2246% of this is internal, other fields are used to communicate between different
    2347% exception handling mechanisms in different runtimes.
    24 % \codeC{\_Unwind\_Context} is an opaque data structure that is used to pass
     48% $_Unwind_Context$ is an opaque data structure that is used to pass
    2549% information to helper functions.
    2650
    27 Raise exception can cover both phases. It starts by searching for the handler
    28 and if it finds it preforms a clean-up phase to unwind the stack to the
    29 hander. If not it returns allowing the program to decide what to do with all
    30 the state and stack that were in place before the call. During both phases
    31 the raise exception function will search down the stack, calling each
    32 function's personality function as they are found.
     51The raise-exception function uses both phases. It starts by searching for the
     52handler, and if found, performs a clean-up phase to unwind the stack to the
     53hander. If a handler is not found, control returns allowing the
     54exception-handling policy for unhandled exception to be executed.  During both
     55phases, the raise exception function searches down the stack, calling each
     56function's \emph{personality function}.
    3357
    34 Personality functions must be able to preform three tasks, although not all
    35 of them have to be preformed in a given call. Which tasks must be preformed
    36 are decided by the actions provided.
     58A personality function performs three tasks, although not all of them have to
     59be present. The tasks performed are decided by the actions provided.
    3760% Something argument something bitmask.
    3861\begin{itemize}
    39 \item\codeC{\_UA\_SEARCH\_PHASE} this is being called during the clean-up
    40 phase and means search for handlers. If the hander is found the personality
    41 function should return \codeC{\_URC\_HANDLER\_FOUND}, otherise it should
    42 return \codeC{\_URC\_CONTINUE\_UNWIND}.
    43 \item\codeC{\_UA\_CLEANUP\_PHASE} is passed in during the clean-up phase and
    44 means that part or all of the stack frame is being removed. The personality
    45 function should do whatever clean-up the language defines (such as running
    46 destructors) and then generally returns \codeC{\_URC\_CONTINUE\_UNWIND}.
    47 \item\codeC{\_UA\_HANDLER\_FRAME} means that the personality function must
    48 install a handler. It is also passing in during the clean-up phase and will
    49 be in addition to the clean-up action. Libunwind provides several helpers
    50 for the personality function here. Once it is done the personality function
    51 must return \codeC{\_URC\_INSTALL\_CONTEXT}.
     62\item$_UA_SEARCH_PHASE$ is called during the clean-up phase and means search
     63for handlers. If the hander is found, the personality function should return
     64$_URC_HANDLER_FOUND$, otherwise it returns $_URC_CONTINUE_UNWIND$.
     65\item$_UA_CLEANUP_PHASE$ is passed in during the clean-up phase and means part
     66or all of the stack frame is removed. The personality function should do
     67whatever clean-up the language defines (such as running destructors/finalizers)
     68and then generally returns $_URC_CONTINUE_UNWIND$.
     69\item$_UA_HANDLER_FRAME$ means the personality function must install a
     70handler. It is also passed in during the clean-up phase and is in addition to
     71the clean-up action. Libunwind provides several helpers for the personality
     72function here. Once it is done, the personality function must return
     73$_URC_INSTALL_CONTEXT$.
    5274\end{itemize}
    5375
    54 Forced unwind only preforms the clean-up phase. It is similar to the phase 2
    55 section of raise exception with a few changes. A simple one is that
    56 it passes in an extra action to the personality function
    57 \codeC{\_UA\_FORCE\_UNWIND} which means a handler cannot be installed. The
    58 most significant is the addition of the stop function, which is passed in as
    59 an argument to the forced unwind.
     76Forced unwind only performs the clean-up phase. It is similar to the phase 2
     77section of raise exception with a few changes. A simple one is that it passes
     78in an extra action to the personality function $_UA_FORCE_UNWIND$, which means
     79a handler cannot be installed. The most significant is the addition of the $stop$
     80function, which is passed in as an argument to the forced unwind.
    6081
    6182The stop function is a lot like a personality function. It takes an extra
    6283argument, a void pointer passed into force unwind. It may return
    63 \codeC{\_URC\_NO\_REASON} to continue unwinding or it can transfer control
    64 out of the unwind code using its own mechanism.
     84$_URC_NO_REASON$ to continue unwinding or it can transfer control out of the
     85unwind code using its own mechanism.
    6586% Is there a reason that NO_REASON is used instead of CONTINUE_UNWIND?
    6687The stop function is called once on every stack frame and once at the end of
    67 the stack. In a stack frame it is called before the personality routine with
     88the stack. In a stack frame, it is called before the personality routine with
    6889the same arguments (except for the extra void pointer). At the end of the
    69 stack the arguments are mostly the same, except the stack pointer stored in
    70 the context is set to null. Because of the significance of that change both
    71 GCC and Clang add an extra action in this case \codeC{\_UA\_END\_OF\_STACK}.
    72 The stop function may not return at the end of the stack.
     90stack, the arguments are mostly the same, except the stack pointer stored in
     91the context is set to null. Because of the significance of that change, both
     92GCC and Clang add an extra action in this case $_UA_END_OF_STACK$.  The stop
     93function may not return at the end of the stack.
    7394
    7495\section{\CFA Implementation}
    7596
    76 To use libunwind \CFA provides several wrappers, its own storage, the
    77 personality functions and a stop function.
     97To use $libunwind$, \CFA provides several wrappers, its own storage, the
     98personality functions, and a stop function.
    7899
    79 The wrappers preform three tasks: set-up, clean-up and controlling the
    80 unwinding. The set-up allocates a copy of the \CFA exception into the hander
    81 so it can control its lifetime and stores it in the exception context while
    82 clean-up -- run when control exits a catch clause and return to normal code --
     100The wrappers perform three tasks: set-up, clean-up and controlling the
     101unwinding. The set-up allocates a copy of the \CFA exception into a handler
     102so it can control its lifetime, and stores it in the exception context.
     103Clean-up -- run when control exits a catch clause and return to normal code --
    83104frees the exception copy.
    84105% It however does not set up the unwind exception so we can't use any inter-
     
    86107
    87108The control code in the middle is run every time a throw or re-throw is
    88 called. It uses raise exception to search for a hander and to run it if one
     109called. It uses raise exception to search for a handler and to run it if one
    89110is found. Otherwise it uses forced unwind to unwind the stack, running all
    90111destructors, before terminating the process.
    91112
    92 The stop function is very simple, it checks the end of stack flag to see if
    93 it is finished unwinding. If so it calls exit to end the process, otherwise
    94 it tells the system to continue unwinding.
     113The stop function is very simple, it checks the end of stack flag to see if it
     114is finished unwinding. If so, it calls exit to end the process, otherwise it
     115tells the system to continue unwinding.
    95116% Yeah, this is going to have to change.
    96117
    97 The personality routine is much more complicated.
    98 First because it has to get some information about the function by scanning
    99 the LSDA (Language Specific Data Area). This allows a single personality
    100 function to be used for multiple functions and it accounts for multiple
    101 regions and possible handlers in a single function.
     118The personality routine is much more complicated.  First, because it has to get
     119some information about the function by scanning the LSDA (Language Specific
     120Data Area). This allows a single personality function to be used for multiple
     121functions and it accounts for multiple regions and possible handlers in a
     122single function.
    102123% Not that we do that yet.
    103124
     
    113134unwinding. The clauses of the try block are then converted into GCC inner
    114135functions which can be passed around with function pointers while still having
    115 access to the outer function's scope. \codeC{catchResume} and \codeC{finally}
    116 clauses are handled seperately and will not be discussed here.
     136access to the outer function's scope. $catchResume$ and $finally$
     137clauses are handled separately and will not be discussed here.
    117138
    118 The \codeC{try} clause is convered to a function directly. The \codeC{catch}
     139The $try$ clause is converted to a function directly. The $catch$
    119140clauses are combined and then create two functions. The first is the match
    120141function which is used during the search phase to see if any of the handler
     
    123144unwinding except for running destructors and so can be handled by GCC.
    124145
    125 These three functions are passed into \codeC{try\_terminate}, an internal
    126 function that repersents the try statement. This is the only function with
     146These three functions are passed into $try_terminate$, an internal
     147function that represents the try statement. This is the only function with
    127148our personality function as well as assembly statements that create the LSDA.
    128149In normal execution all the function does is call the try block closure and
    129 return once that has finished executing. However using libunwind its
     150return once that has finished executing. However using $libunwind$ its
    130151personality function now handles exception matching and catching.
    131152
    132 During the search phase the personality function retreaves the match function
     153During the search phase the personality function retrieves the match function
    133154from the stack using the saved stack pointer. The function is called, either
    134155returning 0 for no match or the index (a positive integer) of the handler
     
    137158
    138159During the clean-up phase there is nothing for the personality function to
    139 clean-up in \codeC{try\_terminate}. So if this is not the handler frame
    140 unwinding continues. If this is the handler frame than control is transfered
     160clean-up in $try_terminate$. So if this is not the handler frame
     161unwinding continues. If this is the handler frame than control is transferred
    141162to the catch function, giving it the exception and the handler index.
Note: See TracChangeset for help on using the changeset viewer.