On the stack-unwinding mechanism used in SBCL. Alastair Bridgewater, February 2009. [STATUS: DRAFT] INTRODUCTION Common Lisp defines three basic mechanisms for a non-local control transfer. These methods are TAGBODY / GO, BLOCK / RETURN-FROM and CATCH / THROW. Two of these mechanisms (RETURN-FROM and THROW) also allow for passing an arbitrary number of values when performing the control transfer. There is also a mechanism for performing various cleanup actions during such a transfer, UNWIND-PROTECT. The required behavior of such a non-local transfer (non-local exit, or nlx) is defined in CLHS 5.2, though the actual behavior implemented by SBCL is known as EXIT-EXTENT:MEDIUM, as documented in the cleanup issue EXIT-EXTENT:MINIMAL. The mechanism by which SBCL does stack unwinding is simple to implement, but has some up-front costs for setting up an exit point that could be largely or completely eliminated by using a "smarter" unwind procedure. What I hope to show is the current implementation of unwinding in SBCL, how it is implemented in the compiler, where it intersects with operations requiring cleanup such as dynamic binding and unwind-protect, and a design and implementation plan for a smarter unwind procedure. THE CURRENT IMPLEMENTATION OF UNWIND In broad strokes, unwinding is accomplished by determining the exit point to unwind to (represented as an unwind-block or a catch-block) and any values to be passed to the exit point and calling the assembly-routine UNWIND. UNWIND, in turn, calls the landing-pad of each intervening unwind-protect block between the current frame and the target exit point, unlinking each unwind-protect block as it goes. It then calls to the landing-pad of the target exit point, passing the values that were originally given. This explanation, of course, ignores a lot of detail. Landing-pads are invoked by a direct control transfer (a jump) rather than a call instruction that would save the return address. They are passed three values: The catch-or-unwind-block representing the target of the unwind, the number of values being passed and the location on the stack of the values being passed. When an unwind-protect cleanup is complete, the landing-pad calls the "magical compiler frob" %CONTINUE-UNWIND, which is just UNWIND again with another name, passing the same three values it received. This preserves the illusion of a single "unwind" function calling each unwind-protect cleanup in turn before passing control to the target exit point without actually implementing it that way. Each landing-pad is responsible for restoring its dynamic environment, typically by performing an unbind-to-here with a saved binding-stack pointer and restoring number-stack, alien-stack and current catch-block pointers from saved copies. THROW is implemented by another assembly-routine, which takes a target tag value and a pointer to and count of values to pass. This routine searches the catch-block chain for a catch-block with a matching tag and jumps into UNWIND, passing the block thus found and the value information. ________________________________________________________________ throw assembly-routine, VOP target start count Arguments: TARGET is the tag for a CATCH BLOCK to throw to. START is the location on the control stack for the values to return from the CATCH BLOCK. COUNT is the number of values to return from the CATCH BLOCK. Description: THROW searches through the chain of CATCH BLOCKs stored in *CURRENT-CATCH-BLOCK* for one which has a TAG value equal to TARGET. If it doesn't find one, it invokes an error trap (UNSEEN-THROW-TAG-ERROR). If it does find one, it invokes UNWIND, passing the CATCH BLOCK, START, and COUNT. ________________________________________________________________ unwind (:translate %continue-unwind) assembly-routine, VOP block start count Arguments: BLOCK is an UNWIND BLOCK to invoke. START is the location on the control stack for the values to return from the UNWIND BLOCK. COUNT is the number of values to return from the UNWIND BLOCK. Description: UNWIND first checks to see if BLOCK is a NULL pointer. If so, it invokes an error trap (INVALID-UNWIND-ERROR). UNWIND next checks to see if there is an UNWIND-PROTECT set in place since BLOCK was created. If there is, it invokes the UNWIND-BLOCK for the UNWIND-PROTECT, passing BLOCK, START, and COUNT. If there is no UNWIND-PROTECT set, UNWIND invokes BLOCK, passing START and COUNT. When an UNWIND-PROTECT finishes executing its cleanup forms, it invokes UNWIND again, as %CONTINUE-UNWIND, passing the same BLOCK, START, and COUNT arguments that it received, thus continuing the unwind process. ________________________________________________________________ unwind-block primitive-type current-uwp current-cont current-code entry-pc Fields: CURRENT-UWP is the value of *CURRENT-UNWIND-PROTECT-BLOCK* when the UNWIND-BLOCK was created. CURRENT-CONT (current context) is the value of the control stack frame pointer when the UNWINDBLOCK was created. CURRENT-CODE is only on non-x86, non-x86-64 systems, and is the containing function for the UNWIND BLOCK. ENTRY-PC is the program counter value at which to resume execution when the UNWIND BLOCK is invoked. Description: An UNWIND BLOCK is the system representation of what the spec calls an "exit point". ________________________________________________________________ catch-block primitive-type current-uwp current-cont current-code entry-pc tag previous-catch Fields: CURRENT-UWP, CURRENT-CONT, CURRENT-CODE, ENTRY-PC: See the definition of UNWIND-BLOCK. TAG: The TAG used to establish this CATCH BLOCK. PREVIOUS-CATCH: The value of *CURRENT-CATCH-BLOCK* when this CATCH BLOCK was created. Description: A CATCH BLOCK is a superset of an UNWIND BLOCK, used to hold the additional data (catch tag and chain pointer) for the CATCH special form. COMPILER SUPPORT FOR UNWIND FIXME: Describe IR1 and IR2 magic here, including cleanups. ________________________________________________________________ make-unwind-block VOP tn Args: TN is a TN for the area within the current stack frame in which to build the unwind block. Description: MAKE-UNWIND-BLOCK sets up the minimum amount of information in an UNWIND BLOCK required for it to be able to serve as an exit point (the CURRENT-UWP, CURRENT-CONT, ENTRY-PC slots, and the CURRENT-CODE slot on non-x86oid systems). ________________________________________________________________ make-catch-block VOP tn tag Args: TN is a TN for the area within the current stack frame in which to build the CATCH BLOCK. TAG is the tag value associated with the CATCH. Description: MAKE-CATCH-BLOCK does essentially the same as MAKE-UNWIND-BLOCK, but also sets the TAG and PREVIOUS-CATCH slots and points *CURRENT-CATCH-BLOCK* at the new CATCH BLOCK. ________________________________________________________________ set-unwind-protect VOP tn Args: TN is a TN for the area within the current stack frame in which the UNWIND BLOCK was built. Description: SET-UNWIND-PROTECT stores a pointer to the area indicated to by TN in *CURRENT-UNWIND-PROTECT-BLOCK*. ________________________________________________________________ unlink-catch-block (:translate %catch-breakup) VOP Description: Unlinks the topmost CATCH BLOCK from *CURRENT-CATCH-BLOCK*. ________________________________________________________________ unlink-unwind-protect (:translate %unwind-protect-breakup) VOP Description: Unlinks the topmost UNWIND BLOCK from *CURRENT-UNWIND-PROTECT-BLOCK*. I LIED: UNWIND ON WIN32 Win32 provides its own unwind procedure, which is used extensively in the implementation of the platform API, and also serves as a mechanism for dealing with machine exceptions such as writing to read-only memory or executing a breakpoint instruction (both scenarios are used in the implementation of SBCL). In order to interoperate properly with the Windows APIs, SBCL needs to interoperate with the provided unwind mechanism. The Win32 unwind (SEH) mechanism operates in a similar manner to how catch blocks work in SBCL. Each SEH frame is a two-word structure on the stack containing pointers to the next SEH frame and a handler function that can dismiss exceptions (useful for a write barrier on a GC'd heap, for example) and have execution resume from where the exception occurred, request an unwind to a given point in the stack or, if an unwind is actually in progress, perform some cleanup action. In effect, it is simultaneously a HANDLER-BIND for machine exceptions and an UNWIND-PROTECT. A pointer to the most recent SEH frame established is stored at the location [FS:0], part of the Thread Information Block (TIB) for the current thread. The _RtlUnwind() function takes as a parameter the address of the SEH frame to unwind to (leaving it as topmost on the stack, removing those more recent), with the post-unwind landing-pad expected to deallocate the freed stack space. Interoperation with the Win32 unwind mechanism was achieved by: * Adding slots for the two words of an SEH frame to both catch-blocks and unwind-blocks. * Altering the VOPs MAKE-UNWIND-BLOCK and MAKE-CATCH-BLOCK to store the address of the current topmost SEH frame in the new block. * Altering the VOP SET-UNWIND-PROTECT to store the address of a new assembler-routine that serves as a landing-pad for unwind processing in the SEH frame of the unwind bloock and store the address of the SEH frame in [FS:0], linking it in as the most recent SEH frame. * Altering call_into_lisp to establish an SEH frame and save the binding stack pointer prior to establishing the new Lisp stack frame. * Altering handle_exception() to check to see if it is being unwound, and if so to perform an unbind_to_here() with the saved binding stack pointer from call_into_lisp. * Changing UNWIND to no longer translate %CONTINUE-UNWIND, to call _RtlUnwind() to perform the unwind proper and to then jump to the landing-pad for the target exit point. * Adding a new assembly-routine without a VOP, UWP-SEH-HANDLER which triggers when an unwind is actually occurring. It saves all the general-purpose registers, fakes up a stack frame, finds the current unwind-block, unlinks it from the unwind-block chain, and jumps to the landing-pad, passing a bogus target exit point and value count and the frame pointer for the fake frame as the value start location. * Adding a new assembly-routine and VOP, CONTINUE-UNWIND that translates %CONTINUE-UNWIND. It restores the faked-up frame pointer from the passed-in value start location, restores the saved registers from the stack and returns ExceptionContinueSearch to allow the unwind to proceed. There is still a hole in the interoperation semantics provided, and that is a so-called "exit unwind", used during normal thread exit. In this case, the unwind landing-pads are not supposed to perform any nlx to outside their scope (in lisp terms, all exit points in the thread have been abandoned), but no provision is made to prevent this. A SMARTER UNWIND PROCEDURE FIXME: Fill this out. XXX: The basis for the smarter unwinder is parsing the backtrace information from the debug information emitted by the compiler, specially annotated with dynamic binding lifetimes, cleanups, etc. XXX: The actual optimizations for UWP-establishment are largely a reduction in extra register loads due to the unwinder knowing how to do the register restoration. An implication of this is that it should be possible to do special-unbinding based on knowing when special-binding happens, thus no longer needing to keep track of the bindstack pointer in catch blocks. In fact, looking over the storage requirements of catch-blocks and unwind-blocks, the only thing that actually needs keeping (can't be recovered from stack unwinding and debug-fun information) is a catch tag. XXX: Note that if we can make unbinding happen based on the above, we can get rid of the unbind-sentinels used by unwind-to-frame-and-call-vop. EOF