Index: doc/theses/andrew_beach_MMath/unwinding.tex =================================================================== --- doc/theses/andrew_beach_MMath/unwinding.tex (revision 71582027d4aee596817893608c7bef096d15cb5b) +++ doc/theses/andrew_beach_MMath/unwinding.tex (revision 4f3a4d75e7b577ec292ebbbeafb3eb9e9cb40c0f) @@ -1,37 +1,54 @@ \chapter{\texorpdfstring{Unwinding in \CFA}{Unwinding in Cforall}} -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. +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. -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 -@setjmp@ \& @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 @try@ statement's @finally@ -clause. Handling this requires walking the stack going through each stack -frame. +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. -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. +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. -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. +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. +\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 @@ -44,57 +61,57 @@ 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. +@_Unwind_Action@ is a bitmask of possible actions and an argument of this type +is passed into the personality function. \begin{itemize} -\item@_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 @_URC_HANDLER_FOUND@. Otherwise it should return -@_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@. +\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 are for -compatability and there is the @struct _Unwind_Context@ pointer which -passed to many helpers to get information about the current stack frame. +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. -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, @_UA_FORCE_UNWIND@, which means a handler cannot be +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. -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. +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. By the standard API this is marked by setting +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 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 @_URC_NO_REASON@ to -continue unwinding. +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? -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. +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. +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 @@ -108,66 +125,60 @@ 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 +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 @exit@ to end the process, -otherwise it returns with no-reason to continue unwinding. +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 LSDA (Language Specific Data Area). This +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 -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. +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. -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 @-fexception@ flag is -sufficient to handle unwinding. +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 than that are those that contain -@try@ statements. A @try@ statement has a @try@ -clause, some number of @catch@ clauses and @catchResume@ -clauses and may have a @finally@ clause. Of these only @try@ -statements with @catch@ clauses need to be transformed and only they -and the @try@ clause are involved. +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. -The @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 @try@ clause is converted into the try functions, -almost entirely unchanged. The @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 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. -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 @try_terminate@. This is an +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 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. +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 +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 -@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. +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. -At this point control has returned to normal control flow. +{\color{blue}PAB: Maybe a diagram would be helpful?}