Changeset 4f3a4d75 for doc/theses/andrew_beach_MMath
- Timestamp:
- Jan 25, 2021, 3:59:42 PM (4 years ago)
- 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
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/andrew_beach_MMath/unwinding.tex
r7158202 r4f3a4d75 1 1 \chapter{\texorpdfstring{Unwinding in \CFA}{Unwinding in Cforall}} 2 2 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. 3 Stack unwinding is the process of removing stack frames (activations) from the 4 stack. On function entry and return, unwinding is handled directly by the code 5 embedded in the function. Usually, the stack-frame size is known statically 6 based on parameters and local variable declarations. For dynamically-sized 7 local variables, a runtime computation is necessary to know the frame 8 size. Finally, a function's frame-size may change during execution as local 9 variables (static or dynamic sized) go in and out of scope. 10 Allocating/deallocating stack space is usually an $O(1)$ operation achieved by 11 bumping the hardware stack-pointer up or down as needed. 9 12 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.13 Unwinding across multiple stack frames is more complex because individual stack 14 management code associated with each frame is bypassed. That is, the location 15 of a function's frame code is largely unknown and dispersed throughout the 16 function, hence the current stack-frame size managed by that code is also 17 unknown. Hence, code unwinding across frames does not have direct knowledge 18 about what is on the stack, and hence, how much of the stack needs to be 19 removed. 17 20 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. 21 The traditional unwinding mechanism for C is implemented by saving a snap-shot 22 of 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 24 reseting to a snap-shot of an arbitrary but existing function frame on the 25 stack. It is up to the programmer to ensure the snap-shot is valid when it is 26 reset, making the code fragile with potential errors that are difficult to 27 debug because the stack becomes corrupted. 22 28 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. 29 However, many languages define cleanup actions that have to be taken when 30 something is deallocated from the stack or blocks end, such as running a 31 variable's destructor or a @try@ statement's @finally@ clause. Handling these 32 mechanisms requires walking the stack and checking each stack frame for these 33 potential actions. 34 35 For exceptions, it must be possible to walk the stack frames in search of try 36 statements with handlers to perform exception matching. For termination 37 exceptions, it must be possible to unwind all stack frames from the throw to 38 the matching catch, and each of these frames must be checked for cleanup 39 actions. Stack walking is where the most of the complexity and expense of 40 exception handling comes from. 41 42 One of the most popular tools for stack management is libunwind, a low level 43 library that provides tools for stack walking and unwinding. What follows is an 44 overview of all the relevant features of libunwind and how \CFA uses them to 45 implement its exception handling. 27 46 28 47 \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 49 control-flow: @_Unwind_RaiseException@ and @_Unwind_ForcedUnwind@. Their 50 operation is divided into two phases: search and clean-up. The search phase -- 51 phase 1 -- is used to scan the stack but not unwinding it. The clean-up phase 52 -- phase 2 -- is used for unwinding. 36 53 37 54 The raise-exception function uses both phases. It starts by searching for a … … 44 61 A personality function performs three tasks, although not all have to be 45 62 present. The tasks performed are decided by the actions provided. 46 @_Unwind_Action@ is a bitmask of possible actions and an argument of 47 this typeis passed into the personality function.63 @_Unwind_Action@ is a bitmask of possible actions and an argument of this type 64 is passed into the personality function. 48 65 \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 69 function to check for handlers. If there is a handler in a stack frame, as 70 defined by the language, the personality function returns @_URC_HANDLER_FOUND@; 71 otherwise 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 75 all of the stack frame is removed. The personality function does whatever 76 clean-up the language defines (such as running destructors/finalizers) and then 77 generally returns @_URC_CONTINUE_UNWIND@. 78 \item 79 @_UA_HANDLER_FRAME@ means the personality function must install a handler. It 80 is also passed in during the clean-up phase and is in addition to the clean-up 81 action. libunwind provides several helpers for the personality function. Once 82 it is done, the personality function returns @_URC_INSTALL_CONTEXT@. 64 83 \end{itemize} 65 The personality function is given a number of other arguments. Some ar e for66 compatabilityand there is the @struct _Unwind_Context@ pointer which67 passed to many helpers to get information about the current stack frame.84 The personality function is given a number of other arguments. Some arguments 85 are for compatibility, and there is the @struct _Unwind_Context@ pointer which 86 is passed to many helpers to get information about the current stack frame. 68 87 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 88 For cancellation, forced-unwind only performs the clean-up phase. It takes 89 three arguments: a pointer to the exception, a pointer to the stop function and 90 a pointer to the stop parameter. It does most of the same actions as phase two 91 of raise-exception but passes in an extra action to the personality function on 92 each stack frame, @_UA_FORCE_UNWIND@, which means a handler cannot be 75 93 installed. 76 94 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 callsthe79 s top function. The stop function receives all the same arguments as the80 personality function will and the stop parameter supplied toforced-unwind.95 As well, forced-unwind calls the stop function each time it steps into a frame, 96 before calling the personality function. The stop function receives all the 97 same arguments as the personality function and the stop parameter supplied to 98 forced-unwind. 81 99 82 100 The 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 markedby setting101 stack frames have been removed. The standard API marks this frame by setting 84 102 the stack pointer inside the context passed to the stop function. However both 85 103 GCC and Clang add an extra action for this case @_UA_END_OF_STACK@. 86 104 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. 105 Each time the stop function is called, it can do one or two things. When it is 106 not the end of the stack it can return @_URC_NO_REASON@ to continue unwinding. 90 107 % 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 a re provided to do it.108 The other option is to use some other means to transfer control elsewhere and 109 never return to its caller. libunwind provides no additional tools for 110 alternate transfers of control. 94 111 95 112 \section{\texorpdfstring{\CFA Implementation}{Cforall Implementation}} 96 113 97 To use libunwind, \CFA provides several wrappers, its own storage, 98 personalityfunctions, and a stop function.114 To use libunwind, \CFA provides several wrappers, its own storage, personality 115 functions, and a stop function. 99 116 100 117 The wrappers perform three tasks: set-up, clean-up and controlling the … … 108 125 The core control code is called every time a throw -- after set-up -- or 109 126 re-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 then127 if one is found. If no handler is found and raise-exception returns, then 111 128 forced-unwind is called to run all destructors on the stack before terminating 112 129 the process. 113 130 114 The stop function is very simple. It checksthe end of stack flag to see if115 it is finished unwinding. If so, it calls @exit@ to end the process, 116 otherwise itreturns with no-reason to continue unwinding.131 The stop function is simple. It checks for the end of stack flag to see if 132 unwinding is finished. If so, it calls @exit@ to end the process, otherwise it 133 returns with no-reason to continue unwinding. 117 134 % Yeah, this is going to have to change. 118 135 119 136 The personality routine is more complex because it has to obtain information 120 about the function by scanning the L SDA (Language Specific Data Area). This137 about the function by scanning the Language Specific Data Area (LSDA). This 121 138 step allows a single personality function to be used for multiple functions and 122 let that personaliity function figure out exactly where in the function123 execution was, what is currently in the stack frame and what handlers should124 bechecked.139 lets that personality function figure out exactly where in the function 140 execution is, what is currently in the stack frame, and what handlers should be 141 checked. 125 142 % Not that we do that yet. 126 143 127 However, generating the LSDA is difficult. It requires knowledge about the 128 location of the instruction pointer and stack layout, which varies with129 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.144 It is also necessary to generate the LSDA, which is difficult. It requires 145 knowledge about the location of the instruction pointer and stack layout, which 146 varies with compiler and optimization levels. Fortunately, for frames where 147 there are only destructors, GCC's attribute cleanup with the @-fexception@ flag 148 is sufficient to handle unwinding. 132 149 133 The only functions that require more than that are those that contain134 @try@ statements. A @try@ statement has a @try@ 135 clause, some number of @catch@ clauses and @catchResume@ 136 c lauses 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.150 The only functions that require more information are those containing @try@ 151 statements. Specifically, only @try@ statements with @catch@ clauses need to be 152 transformed. The @try@ statement is converted into a series of closures that 153 can access other parts of the function according to scoping rules but can be 154 passed around. The @catch@ clauses are converted into two functions: the match 155 function and the handler function. 139 156 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. 157 Together the match function and the catch function form the code that runs when 158 an exception passes out of the guarded block for a try statement. The match 159 function is used during the search phase: it is passed an exception and checks 160 each handler to see if the raised exception matches the handler exception. It 161 returns an index that represents which handler matched or there is no 162 match. The catch function is used during the clean-up phase, it is passed an 163 exception and the index of a handler. It casts the exception to the exception 164 type declared in that handler and then runs the handler's body. 145 165 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 166 These three functions are passed to @try_terminate@, which is an 156 167 % 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 doesthe exception handling in \CFA. During normal159 execution all this function does is call the try function and then return.160 It is onlywhen exceptions are thrown that anything interesting happens.168 internal hand-written function that has its own personality function and custom 169 assembly LSDA for doing the exception handling in \CFA. During normal 170 execution, this function calls the try function and then return. It is only 171 when exceptions are thrown that anything interesting happens. 161 172 162 173 During 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 the174 function and calls it. If the match function returns a handler index, the 164 175 personality 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 inst alls the handler, which is setting the instruction pointer in169 @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.176 otherwise unwinding continues. During the clean-up phase, the personality 177 function only performs an action, when a handler is found in a frame. For each 178 found frame, the personality function installs the handler, which sets the 179 instruction pointer in @try_terminate@ to an otherwise unused section that 180 calls 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 182 control has returned to normal control flow. 172 183 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.