root/trunk/infrastructure/st/stackcontext.d

/******************************************************
 * StackThreads are userland, cooperative, lightweight
 * threads. StackThreads are very efficient, requiring
 * much less time per context switch than real threads.
 * They also require far fewer resources than real
 * threads, which allows many more StackThreads to exist
 * simultaneously. In addition, StackThreads do not
 * require explicit synchronization since they are
 * non-preemptive.  There is no requirement that code
 * be reentrant.
 *
 * This module implements the code necessary for context
 * switching.  StackContexts can be used independently
 * of StackThreads, and may be used for implementing
 * coroutines, custom scheduling or complex iterators.
 *
 * Thanks to Lars Ivar Igesunde (larsivar@igesundes.no)
 * for the ucontext bindings on Linux used in earlier
 * implementations.
 *
 * Version: 0.12
 * Date: October 17, 2006
 * Authors: Mikola Lysenko, mclysenk@mtu.edu
 * License: Use/copy/modify freely, just give credit.
 * Copyright: Public domain.
 *
 * Bugs:
 *  Debug builds will eat more stack space than release
 *  builds.  To prevent this, you can allocate some
 *  extra stack in debug mode.  This is not that tragic,
 *  since overflows are now trapped.
 *
 *  DMD has a bug on linux with multiple delegates in a
 *  scope.  Be aware that the linux version may have
 *  issues due to a lack of proper testing.
 *
 *  Due to the way DMD handles windows exceptions, it is
 *  impossible to trap for stack overflows.  Once this
 *  gets fixed, it will be possible to allocate dynamic
 *  stacks.
 *
 *  To prevent memory leaks, compile with -version=LEAK_FIX
 *  This will slow down the application, but it will
 *  improve memory usage.  In an ideal world, it would be
 *  the default behavior, but due to issues with Phobos'
 *  removeRange I have set it as optional.
 *
 *  GDC version does not support assembler optimizations, since
 *  it uses a different calling convention. 
 *
 * History:
 *  v0.12 - Workaround for DMD bug.
 *
 *  v0.11 - Implementation is now thread safe.
 *
 *  v0.10 - Added the LEAK_FIX flag to work around the
 *          slowness of std.gc.removeRange
 *
 *  v0.9 - Switched linux to an asm implementation.
 *
 *  v0.8 - Added throwYield.
 *
 *  v0.7 - Switched to system specific allocators
 *      (VirtualAlloc, mmap) in order to catch stack
 *      overflows.
 *
 *  v0.6 - Fixed a bug with the window version.  Now saves
 *      EBX, ESI, EDI across switches.
 *
 *  v0.5 - Linux now fully supported.  Discovered the cause
 *      of the exception problems: Bug in DMD.
 *
 *  v0.4 - Fixed the GC, added some linux support
 *
 *  v0.3 - Major refactoring
 *
 *  v0.2 - Fixed exception handling
 *
 *  v0.1 - Initial release
 *
 ******************************************************/
module st.stackcontext;

private import
    std.thread,
    std.stdio,
    std.string,
    std.gc,
    st.tls;

//Handle versions
version(D_InlineAsm_X86)
{
    version(DigitalMars)
    {
        version(Win32) version = SC_WIN_ASM;
        version(linux) version = SC_LIN_ASM;
    }
    
    //GDC uses a different calling conventions, need to reverse engineer them later
}


/// The default size of a StackContext's stack
const size_t DEFAULT_STACK_SIZE = 0x40000;

/// The minimum size of a StackContext's stack
const size_t MINIMUM_STACK_SIZE = 0x1000;

/// The state of a context object
enum CONTEXT_STATE
{
    READY,      /// When a StackContext is in ready state, it may be run
    RUNNING,    /// When a StackContext is running, it is currently in use, and cannot be run
    DEAD,       /// When a StackContext is dead, it may no longer be run
}

/******************************************************
 * A ContextException is generated whenever there is a
 * problem in the StackContext system.  ContextExceptions
 * can be triggered by running out of memory, or errors
 * relating to doubly starting threads.
 ******************************************************/
public class ContextException : Exception
{
    this(char[] msg) { super( msg ); }
    
    this(StackContext context, char[] msg)
    {
        if(context is null)
        {
            debug (StackContext) writefln("Generated an exception: %s", msg);
            super(msg);
        }
        else
        {
            debug (StackContext) writefln("%s generated an exception: %s", context.toString, msg);
            super(format("Context %s: %s", context.toString, msg));
        }
    }
}



/******************************************************
 * A ContextError is generated whenever something
 * horrible and unrecoverable happens.  Like writing out
 * of the stack.
 ******************************************************/
public class ContextError : Error
{
    this(char[] msg)
    {
        super(msg);
    }
}




/******************************************************
 * The StackContext is building block of the
 * StackThread system. It allows the user to swap the
 * stack of the running program.
 *
 * For most applications, there should be no need to use
 * the StackContext, since the StackThreads are simpler.
 * However, the StackContext can provide useful features
 * for custom schedulers and coroutines.
 * 
 * Any non running context may be restarted.  A restarted
 * context starts execution from the beginning of its
 * delegate.
 *
 * Contexts may be nested arbitrarily, ie Context A invokes
 * Context B, such that when B yields A is resumed.
 *
 * Calling run on already running or dead context will
 * result in an exception.
 *
 * If an exception is generated in a context and it is
 * not caught, then it will be rethrown from the run
 * method.  A program calling 'run' must be prepared 
 * to deal with any exceptions that might be thrown.  Once
 * a context has thrown an exception like this, it dies
 * and must be restarted before it may be run again.
 *
 * Example:
 * <code><pre>
 * // Here is a trivial example using contexts. 
 * // More sophisticated uses of contexts can produce
 * // iterators, concurrent state machines and coroutines
 * //
 * void func1()
 * {
 *     writefln("Context 1 : Part 1");
 *     StackContext.yield();
 *     writefln("Context 1 : Part 2");
 * }
 * void func2()
 * {
 *     writefln("Context 2 : Part 1");
 *     StackContext.yield();
 *     writefln("Context 2 : Part 2");
 * }
 * //Create the contexts
 * StackContext ctx1 = new StackContext(&func1);
 * StackContext ctx2 = new StackContext(&func2);
 *
 * //Run the contexts
 * ctx1.run();     // Prints "Context 1 : Part 1"
 * ctx2.run();     // Prints "Context 2 : Part 1"
 * ctx1.run();     // Prints "Context 1 : Part 2"
 * ctx2.run();     // Prints "Context 2 : Part 2"
 *
 * //Here is a more sophisticated example using
 * //exceptions
 * //
 * void func3()
 * {
 *      writefln("Going to throw");
 *      StackContext.yield();
 *      throw new Exception("Test Exception");
 * }
 * //Create the context
 * StackContext ctx3 = new StackContext(&func3);
 *
 * //Now run the context
 * try
 * {
 *      ctx3.run();     // Prints "Going to throw"
 *      ctx3.run();     // Throws an exception
 *      writefln("Bla");// Never gets here
 * }
 * catch(Exception e)
 * {
 *      e.print();      // Prints "Test Exception"
 *      //We can't run ctx3 anymore unless we restart it
 *      ctx3.restart();
 *      ctx3.run();     // Prints "Going to throw"
 * }
 *
 * //A final example illustrating context nesting
 * //
 * StackContext A, B;
 *
 * void funcA()
 * {
 *     writefln("A : Part 1");
 *     B.run();
 *     writefln("A : Part 2");
 *     StackContext.yield();
 *     writefln("A : Part 3");
 * }
 * void funcB()
 * {
 *      writefln("B : Part 1");
 *      StackContext.yield();
 *      writefln("B : Part 2");
 * }
 * A = new StackContext(&funcA);
 * B = new StackContext(&funcB);
 *
 * //We first run A
 * A.run();     //Prints "A : Part 1"
 *              //       "B : Part 1"
 *              //       "A : Part 2"
 *              //
 * //Now we run B
 * B.run();     //Prints "B : Part 2"
 *              //
 * //Now we finish A
 * A.run();     //Prints "A : Part 3"
 *
 * </pre></code>
 * 
 ******************************************************/
public final class StackContext
{
    /**
     * Create a StackContext with the given stack size,
     * using a delegate.
     *
     * Params:
     *  fn = The delegate we will be running.
     *  stack_size = The size of the stack for this thread
     *  in bytes.  Note, Must be greater than the minimum
     *  stack size.
     *
     * Throws:
     *  A ContextException if there is insufficient memory
     *  for the stack.
     */
    public this(void delegate() fn, size_t stack_size = DEFAULT_STACK_SIZE)
    in
    {
        assert(fn !is null);
        assert(stack_size >= MINIMUM_STACK_SIZE);
    }
    body
    {
        //Initalize the delegate
        proc = fn;
        
        //Set up the stack
        setupStack(stack_size);
        
        debug (StackContext) writefln("Created %s", this.toString);
    }
    
    /**
     * Create a StackContext with the given stack size,
     * using a function pointer.
     *
     * Params:
     *  fn = The function pointer we are using
     *  stack_size = The size of the stack for this thread
     *  in bytes.  Note, Must be greater than the minimum
     *  stack size.
     *
     * Throws:
     *  A ContextException if there is insufficient memory
     *  for the stack.
     */
    public this(void function() fn, size_t stack_size = DEFAULT_STACK_SIZE)
    in
    {
        assert(fn !is null);
        assert(stack_size >= MINIMUM_STACK_SIZE);
    }
    body
    {
        //Caste fn to delegate
        f_proc = fn;
        proc = &to_dg;
        
        setupStack(stack_size);
        
        debug (StackContext) writefln("Created %s", this.toString);
    }
    
    
    /**
     * Release the stack context.  Note that since stack
     * contexts are NOT GARBAGE COLLECTED, they must be
     * explicitly freed.  This usually taken care of when
     * the user creates the StackContext implicitly via
     * StackThreads, but in the case of a Context, it must
     * be handled on a per case basis.
     *
     * Throws:
     *  A ContextError if the stack is corrupted.
     */
    ~this()
    in
    {
        assert(state != CONTEXT_STATE.RUNNING);
        assert(current_context.val !is this);
    }
    body
    {
        debug (StackContext) writefln("Deleting %s", this.toString);
        
        //Delete the stack if we are not dead
        deleteStack();
    }
    
    /**
     * Run the context once.  This causes the function to
     * run until it invokes the yield method in this
     * context, at which point control returns to the place
     * where code invoked the program.
     *
     * Throws:
     *  A ContextException if the context is not READY.
     *
     *  Any exceptions generated in the context are 
     *  bubbled up through this method.
     */
    public final void run()
    {
        debug (StackContext) writefln("Running %s", this.toString);
        
        //We must be ready to run
        assert(state == CONTEXT_STATE.READY, 
            "Context is not in a runnable state");
        
        //Save the old context
        StackContext tmp = current_context.val;
        
        version(LEAK_FIX)
        {
            //Mark GC info
            debug (LogGC) writefln("Adding range: %8x-%8x", &tmp, getStackBottom());
            addRange(cast(void*)&tmp, getStackBottom());
        }
        
        //Set new context
        current_context.val = this;
        ctx.switchIn();
        current_context.val = tmp;
        
        assert(state != CONTEXT_STATE.RUNNING);
        
        version(LEAK_FIX)
        {
            //Clear GC info
            debug (LogGC) writefln("Removing range: %8x", &tmp);
            removeRange(cast(void*)&tmp);
            
            
            //If we are dead, we need to release the GC
            if(state == CONTEXT_STATE.DEAD && 
                gc_start !is null)
            {
                debug (LogGC) writefln("Removing range: %8x", gc_start);
                removeRange(gc_start);
                gc_start = null;
            }
        }
        
        // Pass any exceptions generated up the stack
        if(last_exception !is null)
        {
            debug (StackContext) writefln("%s generated an exception: %s", this.toString, last_exception.toString);
            
            //Clear the exception
            Object tmpo = last_exception;
            last_exception = null;
            
            //Pass it up
            throw tmpo;
        }
        
        debug (StackContext) writefln("Done running context: %s", this.toString);
    }
    
    
    /**
     * Returns control of the application to the routine
     * which invoked the StackContext.  At which point,
     * the application runs.
     *
     * Throws:
     *  A ContextException when there is no currently
     *  running context.
     */
    public final static void yield()
    {
        StackContext cur_ctx = current_context.val;
        
        //Make sure we are actually running
        assert(cur_ctx !is null,
            "Tried to yield without any running contexts.");
        
        debug (StackContext) writefln("Yielding %s", cur_ctx.toString);
        
        assert(cur_ctx.running);
        
        //Leave the current context
        cur_ctx.state = CONTEXT_STATE.READY;
        StackContext tmp = cur_ctx;
        
        version(LEAK_FIX)
        {
            //Save the GC range
            cur_ctx.gc_start = cast(void*)&tmp;
            debug (LogGC) writefln("Adding range: %8x-%8x",
                cur_ctx.gc_start, cur_ctx.ctx.stack_top);
            addRange(cur_ctx.gc_start, cur_ctx.ctx.stack_top);
        }
        
        //Swap
        cur_ctx.ctx.switchOut();
        
        version(LEAK_FIX)
        {
            StackContext t_ctx = current_context.val;
            
            //Remove the GC range
            debug (LogGC) writefln("Removing range: %8x",
                t_ctx.gc_start);
            assert(t_ctx.gc_start !is null);
            removeRange(t_ctx.gc_start);
            t_ctx.gc_start = null;
        }
        
        //Return
        current_context.val = tmp;
        tmp.state = CONTEXT_STATE.RUNNING;
        
        debug (StackContext) writefln("Resuming context: %s", tmp.toString);
    }
    
    /**
     * Throws an exception and yields.  The exception
     * will propagate out of the run method, while the
     * context will remain alive and functioning.
     * The context may be resumed after the exception has
     * been thrown.
     *
     * Params:
     *  t = The exception object we will propagate.
     */
    public final static void throwYield(Object t)
    {
        current_context.val.last_exception = t;
        yield();
    }
    
    /**
     * Resets the context to its original state.
     *
     * Throws:
     *  A ContextException if the context is running.
     */
    public final void restart()
    {
        debug (StackContext) writefln("Restarting %s", this.toString);
        
        assert(state != CONTEXT_STATE.RUNNING,
            "Cannot restart a context while it is running");
        
        //Reset the context
        restartStack();
    }
    
    /**
     * Recycles the context by restarting it with a new delegate. This
     * can save resources by allowing a program to reuse previously
     * allocated contexts.
     *
     * Params:
     *  dg = The delegate which we will be running.
     */
    public final void recycle(void delegate() dg)
    {
        debug (StackContext) writefln("Recycling %s", this.toString);
        
        assert(state != CONTEXT_STATE.RUNNING,
            "Cannot recycle a context while it is running");
        
        //Set the delegate and restart
        proc = dg;
        restartStack();
    }
    
    /**
     * Immediately sets the context state to dead. This
     * can be used as an alternative to deleting the 
     * context since it releases any GC references, and
     * may be easily reallocated.
     *
     * Throws:
     *  A ContextException if the context is not READY.
     */
    public final void kill()
    {
        assert(state != CONTEXT_STATE.RUNNING,
            "Cannot kill a context while it is running.");
        
        
        version(LEAK_FIX)
        {
            if(state == CONTEXT_STATE.DEAD)
            {
                return;
            }
            
            //Clear the GC ranges if necessary
            if(gc_start !is null)
            {
                debug (LogGC) writefln("Removing range: %8x", gc_start);
                removeRange(gc_start);
                gc_start = null;
            }
        }
        
        state = CONTEXT_STATE.DEAD;
    }
    
    /**
     * Convert the context into a human readable string,
     * for debugging purposes.
     *
     * Returns: A string describing the context.
     */
    public final char[] toString()
    {
        static char[][] state_names = 
        [
            "RDY",
            "RUN",
            "XXX",
        ];
        
        //horrid hack for getting the address of a delegate
        union hack
        {
            struct dele
            {
                void * frame;
                void * fptr;
            }
            
            dele d;
            void delegate () dg;
        }
        hack h;
        if(f_proc !is null)
            h.d.fptr = cast(void*)f_proc;
        else
            h.dg = proc;
        
        return format(
            "Context[sp:%8x,st:%s,fn:%8x]",
            ctx.stack_pointer,
            state_names[cast(int)state],
            h.d.fptr);
    }
    
    /**
     * Returns: The state of this stack context.
     */
    public CONTEXT_STATE getState()
    {
        return state;
    }
    
    /**
     * Returns: True if the context can be run.
     */
    public bool ready()
    {
        return state == CONTEXT_STATE.READY;
    }
    
    /**
     * Returns: True if the context is currently running
     */
    public bool running()
    {
        return state == CONTEXT_STATE.RUNNING;
    }
    
    /**
     * Returns: True if the context is currenctly dead
     */
    public bool dead()
    {
        return state == CONTEXT_STATE.DEAD;
    }
    
    /**
     * Returns: The currently running stack context.
     *  null if no context is currently running.
     */
    public static StackContext getRunning()
    {
        return current_context.val;
    }
    
    invariant
    {
        
        switch(state)
        {
            case CONTEXT_STATE.RUNNING:
                //Make sure context is running
                //assert(ctx.old_stack_pointer !is null);
                assert(current_context.val !is null);
            
            case CONTEXT_STATE.READY:
                //Make sure state is ready
                assert(ctx.stack_bottom !is null);
                assert(ctx.stack_top !is null);
                assert(ctx.stack_top >= ctx.stack_bottom);
                assert(ctx.stack_top - ctx.stack_bottom >= MINIMUM_STACK_SIZE);
                assert(ctx.stack_pointer !is null);
                assert(ctx.stack_pointer >= ctx.stack_bottom);
                assert(ctx.stack_pointer <= ctx.stack_top);
                assert(proc !is null);
            break;
            
            case CONTEXT_STATE.DEAD:
                //Make sure context is dead
                //assert(gc_start is null);
            break;
            
            default: assert(false);
        }
    }
        
    version(LEAK_FIX)
    {
        // Start of GC range
        private void * gc_start = null;
    }
    
    // The system context
    private SysContext ctx;

    // Context state
    private CONTEXT_STATE state;
    
    // The last exception generated
    private static Object last_exception = null;
    
/*BEGIN TLS {*/
        
    // The currently running stack context
    private static ThreadLocal!(StackContext) current_context = null;
    
/*} END TLS*/
    
    // The procedure this context is running
    private void delegate() proc = null;

    // Used to convert a function pointer to a delegate
    private void function() f_proc = null;
    private void to_dg() { f_proc(); }
    

    /**
     * Initialize the stack for the context.
     */
    private void setupStack(size_t stack_size)
    {
        //Initialize the stack
        ctx.initStack(stack_size);
        
        //Initialize context state
        state = CONTEXT_STATE.READY;
        
        version(LEAK_FIX)
        {
            assert(gc_start is null);
            gc_start = null;
        }
        else
        {
            addRange(ctx.getStackStart, ctx.getStackEnd);
        }
    }
    
    /**
     * Restart the context.
     */
    private void restartStack()
    {
        version(LEAK_FIX)
        {
            //Clear the GC ranges if necessary
            if(gc_start !is null)
            {
                debug (LogGC) writefln("Removing range: %8x", gc_start);
                removeRange(gc_start);
                gc_start = null;
            }
        }
        
        ctx.resetStack();
        state = CONTEXT_STATE.READY;
    }
    
    /**
     * Delete the stack
     */
    private void deleteStack()
    {
        version(LEAK_FIX)
        {
            //Clear the GC ranges if necessary
            if(gc_start !is null)
            {
                debug (LogGC) writefln("Removing range: %8x", gc_start);
                removeRange(gc_start);
                gc_start = null;
            }
        }
        else
        {
            removeRange(ctx.getStackStart);
        }
        
        // Clear state
        state = CONTEXT_STATE.DEAD;
        proc = null;
        f_proc = null;
        
        // Kill the stack
        ctx.killStack();
    }
    
    /**
     * Run the context
     */
    private static extern(C) void startContext()
    in
    {
        assert(current_context.val !is null);
        version</