Friday, 19 April 2013

Big heap o' stack frames

Why can't stack frames be allocated on the heap?

Of course I don't mean the heap, I want a stack frame to grow dynamically as much as anyone else, so a fresh memory map region might need allocating for each function cough; but of course dear reader you really want to know why.

Working with Samba multiple concurrent(ish) asynchronous network functions much work is done with continuations or callback functions which are invoked when forwarded network'd rpc responses are returned.

Co-routines

I had previously tried another way of working this by writing in synchronous style using libpcl, and spawning such functions as a private coroutine.

With every rpc-send function Samba has an rpc-receive function which will block in a nested event loop until the response packet is received (if the response has not already been received).

I modified the nested event loop code to switch back to the main co-routine. The packet-received callback routine then just has to switch back to my private co-routine and the rpc-receive function would then return with the now received packet.

It worked well enough but highlighted other bugs which came to light when concurrency became possible; such as use of a connection before it is properly established.

The reason co-routines were used here at all was to obtain a private stack as a simple way to preserve state when waiting for the response, as well as aid debugging - after all a linear stack trace is nicer than a state-machine state any day!

But if the main aim is to protect the stack from being torn down and destroyed, why not allocate the stack frame on a heap? This would allow a function to return to the caller (in some fashion) while preserving state so that mid-re-entry could be achieved at the callback. This is what C#'s yield return does and is perhaps along the lines of native C-ish support for call-with-current-continuation from Scheme (or Lisp). It would not be a full implementation of course unless a full copy of the application environment were made - but we don't want to re-invoke the return path anyway.

So can lightweight fibres be built into C, using such notation as:

do_something_slow(int a, int b) {
  int answer = callback(ask_question(a));
  printf("Answer %d\n", answer);
}

heap(do_something_slow(a, b));
printf("Task started\n");

where control will return to print "Task started" but sometime later the answer will be printed?

Of the two magic words heap and callback, the word heap signifies that a new non-returning stack frame would be allocated and the word callback signifies that the function ask_question will receive a callback address in some form which would cause execution to continue on the next line. This looks all very hand-wavy but of course the callback mechanism would have to be standardized, probably based on the event-loop mechanism by which the callbacks would be delivered.

This all corresponds very closely to my original case where a callback function was explicitly provided to the async function, and the sole role of the callback function was to switch execution to the saved stack. Having called the async function we then switch to the main stack and therefore the process which invoked heap.

I'll post my libpcl code soon, it has some custom varargs task launchers.

1 comment:

  1. I found that this is called a cactus stack

    ReplyDelete