On the implications of table-based platform unwind APIs and SBCL. Alastair Bridgewater, February 2009. [STATUS: DRAFT] INTRODUCTION Modern platform ABIs contain exception-handling and unwind APIs to support language functionality such as C++ destructors. In a survey of platforms including linux/x86, linux/x86-64, MacOS X (all platforms), linux/ARM, Win32 and Windows x64, only one platform (Win32) does not use a table-based unwind interface. This is also the only platform that SBCL does anything close to the right thing in terms of interoperation with alien code during stack unwinding (both for unwinding alien stack frames and for alien code unwinding lisp stack frames). With one further exception (Windows x64), all of these platforms use DWARF debugging data as their unwind table format. As such, we will concentrate on the details of a DWARF-based implementation. Creation, maintainance, and use of table-based unwind data is a largely unexplored field for SBCL. Possibilities include better interoperability with alien code (such as C++ or Java) that have their own equivalents to unwind-protect and condition-handling such as handler-case, cheaper runtime cost of establishing an unwind-protect block, possibly cheaper cost of establishing a handler-bind, more reliable backtraces on x86oid systems, including not requiring frame-pointers in x86-64 C code and possibly other advantages as well. We have five major areas to expound. First, the Lisp unwind semantics of C++ destructors and catch blocks. Second, how to implement Lisp semantics on top of the exception-handling ABI. Third, the compiler and runtime support required to properly support table-based unwinding. Fourth, the quick-and-dirty solution. Fifth, how to take advantage of the presence of unwind data in debugging. THE LISP UNWIND SEMANTICS OF C++ DESTRUCTORS AND CATCH BLOCKS A C++ destructor is called for stack-allocated objects when the stack is unwound. This is roughly analogous to a Lisp UNWIND-PROTECT form, though with the caveat that the body must not perform a non-local exit (that is, it must not cancel the unwind). In terms of the personality routine, a destructor does not cause a handler to be found for a frame, and any landing pad used will end with a call to _Unwind_Resume(). A catch block, on the other hand, can involve a handler. There are two basic use-cases. The first is roughly equivalent to HANDLER-CASE. It is used to catch specific exceptions, deal with them in some manner, and then continue executing the code after the HANDLER-CASE form. The second is used more as an UNWIND-PROTECT, but is implemented as a HANDLER-CASE for all condition types followed by resignalling the condition (not resignalling as in CLHS 9.1.4.1.1, as the use of HANDLER-CASE effectively terminates the dynamic extent of the original signalling process) as if by means of ERROR (rather than CERROR or SIGNAL). It has been argued that stack unwinding for Lisp conditions should be decided only by Lisp condition handling, and not by alien code. This is implementable, and would cover the case of using SIGNAL for event notification rather than error handling, but is at the same time a clear violation of the implied semantics of the intervening C++ stack frames. One possible solution is to have separate search mechanisms for handlers depending on if the condition was signalled via SIGNAL or ERROR or CERROR. Entirely out of scope, at any rate. IMPLEMENTING LISP SEMANTICS IN TERMS OF THE EXCEPTION-HANDLING ABI Lisp semantics involve a two-phase condition-handling mechanism which completely decouples the decision logic about how to handle a given condition with the unwinding of the stack and restarting the program at a chosen place. For our purposes, we need to consider the handler search process and the stack unwind process. There are two models of stack-unwind behavior defined for the Lisp world, known as EXIT-EXTENT:MINIMAL (the actual standard) and EXIT-EXTENT:MEDIUM (what almost everyone actually implements). In both models it is legal to perform a non-local exit from an unwind-protect cleanup, the main difference is as to what exit points are legal to exit to. With EXIT-EXTENT:MINIMAL the only legal option is to extend the unwind further "up" the stack. With EXIT-EXTENT:MEDIUM an unwind can be cut short by unwinding to anywhere "above" the unwind-protect form. These models are incompatible with the notion of "forced" unwinding provided by the exception-handling API, as it does not allow for landing-pads to do anything other than resume unwinding once they are done. Effectively, a forced unwind (or an "exit" unwind on win32) abandons -all- exit points for the duration of the unwind and then re-adopts the exit points that would not have been abandoned had the forced unwind instead been a normal lisp unwind. As a practical upshot, this means that we need to use the _Unwind_RaiseException() interface to perform unwinds and use the catch-and-rethrow semantic of C++ to implement unwind-protect. As a practical matter, if an unwind-protect cleanup does a non-local exit to abort an unwind, and the exception being used to drive the unwind process is a "foreign" exception, then we need to call _Unwind_DeleteException() to deallocate the memory associated with the exception structure. Note also that we must heap-allocate and pin our exception objects (along with any arguments for a throw or return) in order for them not to be clobbered by the stack unwinding. Finding a handler can be trickier. We have two options. Simplest is to keep doing what we do now, which is entirely independent of the exception-handling machinery, but does not give C++ or other alien handlers an opportunity to handle Lisp exceptions. More complicated is to use the exception-handling system to search for a suitable handler, which could allow for cheaper handler-bind for unused handlers, alien code that handles lisp exceptions, etc. Using the exception-handling system to do handler search also fully supports the handler-case-and-resignal semantic model for C++ catch blocks. This would require a way to distinguish the two exception types (handler-find and unwind), but that's not a big deal. In order to use the exception-handling system to search for condition handlers, we need to take advantage of the promise of "resumptive" exception handling documented as being one of the reasons to use a two-phase exception-handling scheme. Unfortunately, while the ABI documents describe this benefit, it does not explain -how- to "dismiss" an exception during the search phase. Some research, however, has suggested that it is "safe" to unwind through the unwinder, as it appears to only allocate memory on the stack during the search phase. An upshot of simply unwinding _Unwind_RaiseException() in search phase is that it doesn't need any special handling, it would be covered by the usual non-local exit used to handle an exception in the first place. COMPILER AND RUNTIME SUPPORT FOR UNWIND TABLES The hooks for telling the unwinder about dynamically-generated code such as is produced by SBCL or a JIT compiler such as modern Java VMs are "__register_frame" and "__deregister_frame", exported from libgcc_s.so.1. James Knight has a proof-of-concept for using these functions to tell the glibc backtrace() function about the SBCL stack frame format at . What we need from the compiler is to create suitable unwind table information for each code-object. This will possibly be a variation on the existing debug-fun dumper. What we need from the runtime is to minimize the number of unwind tables by maintaining the unwind information in contiguous blocks and unregistering and reregistering them when they are changed due to GC, new function loading (either by fasload or by compilation), etc. We also need runtime (or assembler-routine) functions to implement the personality routine for SBCL frames, for landing pads for unwind-protect and other handlers, etc. At this time the actual changes and support required are largely unexplored, as figuring out the semantics was deemed to be a prerequisite to assessing the implementation requirements. THE QUICK AND DIRTY SOLUTION FOR UNWIND INTEROPERATION First, use the current method for finding handlers. It breaks the C++ semantic, but means less work up front. Next, establish a single FDE for the entire lisp heap. Or one FDE per space. This FDE merely describes how to find the frame pointer and return IP for each frame and points to a custom personality routine. Unwind now has to allocate an exception structure, populate it with the saved values to return and the target frame or catch-block, and pass the whole mess off to _Unwind_RaiseException(). The personality routine checks for two things. First, if the exception is from a lisp unwind and this is the target frame, handle the exception via a landing-pad, copy the saved values out of the exception structure, and pass control to the target. Otherwise, if the current frame contains an active unwind-protect (which would always be the current unwind-protect block), either handle the exception (adding an unwind-protect to _Unwind_DeleteException() the exception structure if a non-local exit occurs) or use a landing-pad to run the unwind-protect block if in a forced-unwind scenario. %continue-unwind therefore needs to do the right thing in both the normal and forced-unwind scenarios. It shouldn't be too hard to arrange. Upsides to this solution: It's doable in short order and provides basic interoperation with C++ stack unwinding. Similar unwind logic changes have already been implemented for Win32, so there is some precedent. The unwind logic changes and the personality routine logic would be necessary anyway. It wouldn't take much more to also do the handler search through the exception-handling system. Downsides to this solution: It doesn't provide any real optimization opportunities. USING UNWIND TABLES IN THE DEBUGGER The primary use-case for unwind table data in the debugger is reliable backtraces, even for platforms (such as x86-64) which prefer to elide frame-pointers in compiled code. This can even be implemented without having implemented the unwind interoperation described in previous sections. That said, it does require reimplementing part of the system unwind mechanisms (except on Windows x64, which has a VirtualUnwind function) in order to find frame pointers and return addresses. The important hook in this case is provided from libgcc_s.so.1 on all platforms under consideration (most critically, linux/x86-64 and MacOS X/x86-64), and is called "_Unwind_Find_FDE". Given an address, this function returns the address of the "FDE" structure describing how to unwind the function containing the address, along with the context required to interpret it. FIXME: How do we integrate this with the current debugger? XXX: Is _Unwind_Find_FDE really available on OSX/x86-64? EOF