C++ force stack unwinding inside function

Question

I'm in the process of learning C++ and currently I'm fiddling with the following code:

class Bar;
struct Callback {
    virtual void Continue(Bar&) = 0;
};

// ...

void Foo(Bar& _x, Callback& result)
{
    // Do stuff with _x

    if(/* some condition */) {
        // TODO: Force unwind of stack
        result.Continue(_x);
        return;
    }

    // Do more stuff with _x

    if(/* some other condition */) {
        // TODO: Force unwind of stack
        result.Continue(_x);
        return;
    }

    // TODO: Force unwind of stack
    Bar y; // allocate something on the stack
    result.Continue(y);
}

The main idea is that I know that at every site result.Continue is called, the function Foo will return too. Therefore the stack can be unwound before calling the continuation.

As the user code will use this in a recursive way, I'm worried that this code may lead into stackoverflows. As far as my understanding goes, the parameters _x and result are kept on the stack when result.Continue is executed, because the stack is unwound only when Foo returns.

Edit: The Continue function may (and probably will) call the Foo method: resulting in recursion. Simply tail-call optimizing Continue and not Foo can lead to a stackoverflow.

What can I do to force unwinding of the stack, before the return of Foo, keeping result in a temporary (register?) variable and then execute that continuation?

Answer 1

You can use a design I have found that solves this problem. The design assumes an event-driven program (but you can create a fake event loop otherwise).

For clarity, let's forget about your particular problem and instead focus on the problem of an interface between two objects: a sender object sending data packets to a receiver object. The sender always has to wait for the receiver to finish processing any data packet before sending another. The interface is defined by two calls:

• Send() - called by sender to start sending a data packet, implemented by receiver
• Done() - called by receiver to inform the sender that the send operation is complete and it is possible to send more packets

None of these calls return anything. The receiver always reports completion of the operation by calling Done(). As you can see, this interface is conceptually similar to what you have presented, and suffers from the same problem of recursion between Send() and Done(), possibly resulting in a stack overflow.

My solution was the introduction of a job queue into the event loop. The job queue is a LIFO queue (stack) of events waiting to be dispatched. The event loop treats the job on top of the queue as a maximum-priority event. In other words, when the event loop has to decide which event to dispatch, it will always dispatch the top job in the job queue if the queue is not empty, and not any other event.

The interface described above is then modified to make both the Send() and Done() calls queued. This means that when the sender calls Send(), all that happens is that a job is pushed to the job queue, and this job, when dispatched by the event loop, will call the receiver's real implementation of Send(). Done() works the same way - called by the receiver, it just pushes a job which, when dispatched, calls the sender's implementation of Done().

See how the queue design provides three major benefits.

1. It avoids stack overflow because there is no explicit recursion between Send() and Done(). But the sender can still call Send() again right from its Done() callback, and the receiver can call Done() right from its Send() callback.

2. It blurs the difference between (I/O) operations that have completed immediately and those that take some time, i.e. the receiver has to wait for some system-level event. For example, when using non-blocking sockets, the implementation of Send() in the receiver calls the send() syscall, which either manages to send something, or returns EAGAIN/EWOULDBLOCK, in which case the receiver asks the event loop to inform it when the socket is writable. It retries the send() syscall when it's informed by the event loop that the socket is writable, which likely succeeds, in which case it informs the sender that the operation is complete by calling Done() from this event handler. Whichever happens, it's the same from the perspective of the sender - its Done() function is called when the send operation is complete, immediately or after some time.

3. It makes error handling orthogonal to the actual I/O. Error handling can be implemented by having the receiver call an Error() callback which handles the error somehow. See how the sender and receiver can be independent reusable modules that don't know anything about errors. In case of error (e.g. send() syscall fails with a real error code, not EAGAIN/EWOULDBLOCK), the sender and receiver can simply be destroyed from the Error() callback, which is likely part of the same code that created the sender and receiver.

Together, these features enable elegant flow-based programming in event-driven programs. I have implemented the queue design and flow-based programming in my BadVPN software project, with great success.

Finally, some clarification on why the job queue should be a LIFO. The LIFO scheduling policy provides coarse-grained control over the order of dispatching of jobs. For instance, suppose you are calling some method of some object, and want to do something after this method has executed, and after all the jobs it pushed have been dispatched, recursively. All you have to do is push a job of your own right before calling this method, and do your work from the event handler of this job.

There is also the nice property that you can always cancel this postponed work by dequeuing the job. For instance, if something this function did (including the jobs it pushed) resulted in an error and consequent destruction of our own object, our destructor can dequeue the job that we pushed, avoiding a crash that would happen if the job executed and accessed data that no longer exists.

Answer 2

You can't explicitly force stack unwinding as you call it (destruction of _x and result in the code sample) before the function ends. If your recursion (you didn't show it) is amenable to tail call optimisation then good compilers will be able to handle the recursion without creating a new stack frame.

Answer 3

Unless I misunderstood, why not something like this (a single function causing a stackoverflow is a design flaw imo, but if there are lots of locals in your original Foo() then calling DoFoo() may alleviate the problem):

class Bar;
struct Callback {
    virtual void Continue(Bar&) = 0;
};

// ...

enum { use_x, use_y };

int DoFoo(Bar& _x)
{
    // Do stuff with _x

    if(/* some condition */) {
        return use_x;
    }

    // Do more stuff with _x

    if(/* some other condition */) {
        return use_x;
    }

    return use_y;
}

void Foo(Bar& _x, Callback& result)
{
    int result = DoFoo(_x);
    if (result == use_x)
    {
       result.Continue(_x);
       return;
    }

    Bar y; // allocate something on the stack
    result.Continue(y);
}

Answer 4

I've found another way, but this is specific to Windows and Visual C++:

void* growstk(size_t sz, void (*ct)(void*))
{
    void* p;
    __asm
    {
        sub esp, [sz]
        mov p, esp
    }
    ct(p);
    __asm
    {
        add esp, [sz]
    }
}

The continuation void (*ct)(void*) will have access to the void* p; stack-allocated memory. Whenever the continuation returns, the memory is deallocated by restoring the stack pointer esp to the usual level.