Changeset 4f3a4d75


Ignore:
Timestamp:
Jan 25, 2021, 3:59:42 PM (3 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
408ab79
Parents:
7158202
Message:

proofread chapter "unwind"

File:
1 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/andrew_beach_MMath/unwinding.tex

    r7158202 r4f3a4d75  
    11\chapter{\texorpdfstring{Unwinding in \CFA}{Unwinding in Cforall}}
    22
    3 Stack unwinding is the process of removing things from the stack. Within
    4 functions and on function return this is handled directly by the code in the
    5 function itself as it knows exactly what is on the stack just from the
    6 current location in the function. Unwinding across stack frames means that it
    7 is no longer knows exactly what is on the stack or even how much of the stack
    8 needs to be removed.
     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.
    912
    10 Even this is fairly simple if nothing needs to happen when the stack unwinds.
    11 Traditional C can unwind the stack by saving and restoring state (with
    12 @setjmp@ \& @longjmp@). However many languages define actions that
    13 have to be taken when something is removed from the stack, such as running
    14 a variable's destructor or a @try@ statement's @finally@
    15 clause. Handling this requires walking the stack going through each stack
    16 frame.
     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.
    1720
    18 For exceptions, this means everything from the point the exception is raised
    19 to the point it is caught, while checking each frame for handlers during the
    20 stack walk to find out where it should be caught. This is where the most of
    21 the expense and complexity of exception handling comes from.
     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.
    2228
    23 To do all of this we use libunwind, a low level library that provides tools
    24 for stack walking and stack unwinding. What follows is an overview of all the
    25 relivant features of libunwind and then how \CFA uses them to implement its
    26 exception handling.
     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.
    2746
    2847\section{libunwind Usage}
    29 
    30 \CFA uses two primary functions in libunwind to create most of its
    31 exceptional control-flow: @_Unwind_RaiseException@ and
    32 @_Unwind_ForcedUnwind@.
    33 Their operation is divided into two phases: search and clean-up. The search
    34 phase -- phase 1 -- is used to scan the stack but not unwinding it. The
    35 clean-up phase -- phase 2 -- is used for unwinding.
     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.
    3653
    3754The raise-exception function uses both phases. It starts by searching for a
    … …  
    4461A personality function performs three tasks, although not all have to be
    4562present. The tasks performed are decided by the actions provided.
    46 @_Unwind_Action@ is a bitmask of possible actions and an argument of
    47 this type is passed into the personality function.
     63@_Unwind_Action@ is a bitmask of possible actions and an argument of this type
     64is passed into the personality function.
    4865\begin{itemize}
    49 \item@_UA_SEARCH_PHASE@ is passed in search phase and tells the
    50 personality function to check for handlers. If there is a handler in this
    51 stack frame, as defined by the language, the personality function should
    52 return @_URC_HANDLER_FOUND@. Otherwise it should return
    53 @_URC_CONTINUE_UNWIND@.
    54 \item@_UA_CLEANUP_PHASE@ is passed in during the clean-up phase and
    55 means part or all of the stack frame is removed. The personality function
    56 should do whatever clean-up the language defines
    57 (such as running destructors/finalizers) and then generally returns
    58 @_URC_CONTINUE_UNWIND@.
    59 \item@_UA_HANDLER_FRAME@ means the personality function must install
    60 a handler. It is also passed in during the clean-up phase and is in addition
    61 to the clean-up action. libunwind provides several helpers for the personality
    62 function here. Once it is done, the personality function must return
    63 @_URC_INSTALL_CONTEXT@.
     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@.
    6483\end{itemize}
    65 The personality function is given a number of other arguments. Some are for
    66 compatability and there is the @struct _Unwind_Context@ pointer which
    67 passed to many helpers to get information about the current stack frame.
     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.
    6887
    69 Forced-unwind only performs the clean-up phase. It takes three arguments:
    70 a pointer to the exception, a pointer to the stop function and a pointer to
    71 the stop parameter. It does most of the same things as phase two of
    72 raise-exception but with some extras.
    73 The first it passes in an extra action to the personality function on each
    74 stack frame, @_UA_FORCE_UNWIND@, which means a handler cannot be
     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
    7593installed.
    7694
    77 The big change is that forced-unwind calls the stop function. Each time it
    78 steps into a frame, before calling the personality function, it calls the
    79 stop function. The stop function receives all the same arguments as the
    80 personality function will and the stop parameter supplied to forced-unwind.
     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.
    8199
    82100The stop function is called one more time at the end of the stack after all
    83 stack frames have been removed. By the standard API this is marked by setting
     101stack frames have been removed. The standard API marks this frame by setting
    84102the stack pointer inside the context passed to the stop function. However both
    85103GCC and Clang add an extra action for this case @_UA_END_OF_STACK@.
    86104
    87 Each time function the stop function is called it can do one or two things.
    88 When it is not the end of the stack it can return @_URC_NO_REASON@ to
    89 continue unwinding.
     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.
    90107% Is there a reason that NO_REASON is used instead of CONTINUE_UNWIND?
    91 Its only other option is to use its own means to transfer control elsewhere
    92 and never return to its caller. It may always do this and no additional tools
    93 are provided to do it.
     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.
    94111
    95112\section{\texorpdfstring{\CFA Implementation}{Cforall Implementation}}
    96113
    97 To use libunwind, \CFA provides several wrappers, its own storage,
    98 personality functions, and a stop function.
     114To use libunwind, \CFA provides several wrappers, its own storage, personality
     115functions, and a stop function.
    99116
    100117The wrappers perform three tasks: set-up, clean-up and controlling the
    … …  
    108125The core control code is called every time a throw -- after set-up -- or
    109126re-throw is run. It uses raise-exception to search for a handler and to run it
    110 if one is found. If no handler is found and raise-exception returns then
     127if one is found. If no handler is found and raise-exception returns, then
    111128forced-unwind is called to run all destructors on the stack before terminating
    112129the process.
    113130
    114 The stop function is very simple. It checks the end of stack flag to see if
    115 it is finished unwinding. If so, it calls @exit@ to end the process,
    116 otherwise it returns with no-reason to continue unwinding.
     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.
    117134% Yeah, this is going to have to change.
    118135
    119136The personality routine is more complex because it has to obtain information
    120 about the function by scanning the LSDA (Language Specific Data Area). This
     137about the function by scanning the Language Specific Data Area (LSDA). This
    121138step allows a single personality function to be used for multiple functions and
    122 let that personaliity function figure out exactly where in the function
    123 execution was, what is currently in the stack frame and what handlers should
    124 be checked.
     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.
    125142% Not that we do that yet.
    126143
    127 However, generating the LSDA is difficult. It requires knowledge about the
    128 location of the instruction pointer and stack layout, which varies with
    129 compiler and optimization levels. So for frames where there are only
    130 destructors, GCC's attribute cleanup with the @-fexception@ flag is
    131 sufficient to handle unwinding.
     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.
    132149
    133 The only functions that require more than that are those that contain
    134 @try@ statements. A @try@ statement has a @try@
    135 clause, some number of @catch@ clauses and @catchResume@
    136 clauses and may have a @finally@ clause. Of these only @try@
    137 statements with @catch@ clauses need to be transformed and only they
    138 and the @try@ clause are involved.
     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.
    139156
    140 The @try@ statement is converted into a series of closures which can
    141 access other parts of the function according to scoping rules but can be
    142 passed around. The @try@ clause is converted into the try functions,
    143 almost entirely unchanged. The @catch@ clauses are converted into two
    144 functions; the match function and the catch function.
     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.
    145165
    146 Together the match function and the catch function form the code that runs
    147 when an exception passes out of a try block. The match function is used during
    148 the search phase, it is passed an exception and checks each handler to see if
    149 it will handle the exception. It returns an index that repersents which
    150 handler matched or that none of them did. The catch function is used during
    151 the clean-up phase, it is passed an exception and the index of a handler. It
    152 casts the exception to the exception type declared in that handler and then
    153 runs the handler's body.
    154 
    155 These three functions are passed to @try_terminate@. This is an
     166These three functions are passed to @try_terminate@, which is an
    156167% Maybe I shouldn't quote that, it isn't its actual name.
    157 internal hand-written function that has its own personality function and
    158 custom assembly LSD does the exception handling in \CFA. During normal
    159 execution all this function does is call the try function and then return.
    160 It is only when exceptions are thrown that anything interesting happens.
     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.
    161172
    162173During the search phase the personality function gets the pointer to the match
    163 function and calls it. If the match function returns a handler index the
     174function and calls it. If the match function returns a handler index, the
    164175personality function saves it and reports that the handler has been found,
    165 otherwise unwinding continues.
    166 During the clean-up phase the personality function only does anything if the
    167 handler was found in this frame. If it was then the personality function
    168 installs the handler, which is setting the instruction pointer in
    169 @try_terminate@ to an otherwise unused section that calls the catch
    170 function, passing it the current exception and handler index.
    171 @try_terminate@ returns as soon as the catch function returns.
     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.
    172183
    173 At this point control has returned to normal control flow.
     184{\color{blue}PAB: Maybe a diagram would be helpful?}
Note: See TracChangeset for help on using the changeset viewer.