Eric Day: Non-blocking State Machines
If you’ve ever done any non-blocking programming (usually for socket I/O), you’ve probably had to come up with a non-trivial state machine to handle all the places where everything can pause. Say you’re reading an application level packet from a socket, and half way through the read() system call it screams EAGAIN. You need to stop, save any state, and exit out of whatever chain of functions got you there so the calling application can regain control. I’m going to explain a few techniques I’ve come up with over the years, each with their strengths and weaknesses, and I hope this will spur some conversation of what other folks have done. While I’m fairly happy with how I handle these state machines now, but I’m always looking for a more succinct way of handling things. Please share your thoughts!
Switch Statements
The obvious way to handle non-blocking I/O is with one or more switch statements. Say we need to check the status of something by sending a request over a TCP connection, possibly connecting to the remote host first, and then reading the response. Here is a bit of pseudo-code that demonstrates how this could work (ignoring some error cases, efficient buffer handling, and non-blocking connect cases):
int check_status(struct connection *con)
{
switch (con->state)
{
case CONNECTION_STATE_NONE:
getaddrinfo(...);
con->fd = socket(...);
/* Fall through to next state. */
case CONNECTION_STATE_CONNECT:
ret = connect(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
{
con->state = CONNECTION_STATE_CONNECT;
return WAIT_FOR_WRITE;
}
/* Fall through to next state. */
case CONNECTION_STATE_REQUEST:
ret = write(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
{
con->state = CONNECTION_STATE_REQUEST;
return WAIT_FOR_WRITE;
}
/* Fall through to next state. */
case CONNECTION_STATE_RESPONSE_HEADER:
ret = read(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
{
con->state = CONNECTION_STATE_RESPONSE_HEADER;
return WAIT_FOR_READ;
}
/* Save header. */
/* Fall through to next state. */
case CONNECTION_STATE_RESPONSE:
ret = read(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
{
con->state = CONNECTION_STATE_RESPONSE;
return WAIT_FOR_READ;
}
/* Save response. */
/* Set this here so we skip the connect state next time around. */
con->state = CONNECTION_STATE_REQUEST;
break;
}
}
The first thing you may cringe at is the fall-through cases in switch statements. The alternative is to set a new state at the end of each case, break, and then reevaluate the switch again with that new state (wrapping the above switch in a while loop). I skipped that version since those are some extra ops that are just not necessary. The above machine may be a bit clunky, but it works for simple cases. But what about when you have more complex states that have loops, non-sequential state execution, or nested switch statements? The above has the potential to grow into an unwieldy mess of code. For example, say if we need to read multiple responses back in the last state above, this could be expanded to:
int check_status(struct connection *con)
{
switch (con->state)
{
...
/* Fall through to next state. */
case CONNECTION_STATE_RESPONSE:
while (1)
{
if (con->need_header)
{
ret = read(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
{
con->state = CONNECTION_STATE_RESPONSE;
return WAIT_FOR_READ;
}
/* Save header. */
con->need_header = false;
}
ret = read(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
{
con->state = CONNECTION_STATE_RESPONSE;
return WAIT_FOR_READ;
}
/* Save response. */
if (last_response)
break;
con->need_header = true;
}
/* Set this here so we skip the connect state next time around. */
con->state = CONNECTION_STATE_REQUEST;
break;
}
}
As you can see, another state variable has been added as a boolean (con->need_header). What if responses were not made up of simple header and body? What if there are more nested levels? We can add more switch statements and start breaking this up some into nested functions to make it more readable, but the complexity is still there. For non-trivial non-blocking state machines, this approach is not scalable.
Nested switch/while Statements
Early on in my C years I stumbled upon Duff’s Device. At first I was confused, is that even valid C? Oh, it compiles! Then I was offended. Eventually it clicked and I appreciated the cleverness of the code. Nesting while/for/if with switch statements. I went off to re-write my non-blocking state machines with this new trick:
int check_status(struct connection *con)
{
switch (con->state)
{
...
/* Fall through to next state. */
while (1)
{
case CONNECTION_STATE_RESPONSE_HEADER:
ret = read(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
{
con->state = CONNECTION_STATE_RESPONSE_HEADER;
return WAIT_FOR_READ;
}
/* Save header. */
/* Fall through to next state. */
case CONNECTION_STATE_RESPONSE:
ret = read(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
{
con->state = CONNECTION_STATE_RESPONSE;
return WAIT_FOR_READ;
}
/* Save response. */
if (last_response)
break;
}
/* Set this here so we skip the connect state next time around. */
con->state = CONNECTION_STATE_REQUEST;
break;
}
}
Yup, that’s correct. Shove that while loop right in there. Think of it this way: write your state machine as you would if it were blocking, nesting as deep as you need with for/if/while statements. Next, put a switch around the entire thing, and toss a case statement in wherever something could hit a non-blocking condition (regardless of scope or nesting level). Some folks have commented this feels a lot like using gotos, but I disagree. With switch, you have structure, and compiler warnings for when things are missing (like a case). Sure, it may not be the most elegant solution, but you avoid the nested switch statements and multiple state variables. I still use this today for some things (like inside of the Gearman C server and library), but only when they are fairly simple state machines.
Function Pointer Stack
Last year I started writing a non-blocking C library for MySQL. When I head about Drizzle, I decided to focus my effort there (while keeping the MySQL compatibility), and renamed it to libdrizzle. Today it supports the Drizzle protocol and the most common parts of the MySQL protocol. The protocols for these projects are a bit more involved, so when I began writing the library, I went through a few iterations of state machines and didn’t find anything I was happy with. After some brainstorming I came up with an alternative design, I usually refer to it as a “function pointer stack” or “callback stack”. Please let me know if you have seen something like this and point me to the proper name. :)
This works by creating a traditional stack (LIFO structure) of function pointers. When a state needs to be executed, push it on, when a state is complete, it can pop itself off. It’s similar to a program execution stack, but maintained in user space and state is kept so you know where things left off. Still not getting it? Lets look at the code. First, one quick note about function pointer typedefs:
typedef int (state_fn)(struct connection *con);
These are not required of course, but it makes things a bit more legible. This is saying ’state_fn’ is now a type that points to a function with the given signature. It’s a lot easier that having to write the function signature out every time you have a variable of this type.
Now, the code:
typedef int (state_fn)(struct connection *con);
struct connection
{
...
state_fn *state_stack[STACK_SIZE];
int state_current;
};
/* These functions operation on the function pointer stack. */
static inline bool state_none(struct connection *con)
{
return con->state_current == 0;
}
static inline void state_push(struct connection *con, state_fn *function)
{
assert(con->state_current STACK_SIZE);
con->state_stack[con->state_current]= function;
con->state_current++;
}
static inline void state_pop(struct connection *con)
{
con->state_current--;
}
int state_run(struct connection *con)
{
int ret;
while (!state_none(con))
{
ret= con->state_stack[con->state_current - 1](con);
if (ret)
return ret;
}
return 0;
}
/* These are the states that can be pushed onto the stack. */
int start_state(struct connection *con)
{
getaddrinfo(...);
con->fd = socket(...);
state_pop(con);
state_push(con, connect_state);
return 0;
}
int connect_state(struct connection *con)
{
ret = connect(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
return WAIT_FOR_WRITE;
state_pop(con);
return 0;
}
int request_state(struct connection *con)
{
if (not connected)
{
state_push(con, start_state);
return 0;
}
ret = write(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
return WAIT_FOR_WRITE;
state_pop(con);
state_push(con, response_header_state);
return 0;
}
int response_header_state(struct connection *con)
{
ret = read(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
return WAIT_FOR_READ;
/* Save header. */
state_pop(con);
state_push(con, response_state);
return 0;
}
int response_state(struct connection *con)
{
ret = read(con->fd, ...);
if (ret == -1 && errno == EAGAIN)
return WAIT_FOR_READ;
/* Save response. */
state_pop(con);
if (have_more_responses)
state_push(con, response_header_state);
return 0;
}
/* Here is a function you would make public in the API to start the state machine. */
int check_status(struct connection *con)
{
/* If we are coming back into this after a blocking event,
make sure we don't push a new state on again. */
if (state_none(con))
state_push(con, request_state);
return state_run(con);
}
As you can see, we still start in the check_status function, but push a state if there is no state and then go into our run loop. You can follow along the various functions (sort of like a choose your own adventure book) but eventually you should end up with an empty stack. When this happens, the state_run() function returns 0 and the call is complete.
This may be a bit overkill for such a simple state machine, but as your state execution flow becomes non-sequential (random jumps, recursion, …) the power and flexibility of this design becomes apparent. And what? No switch statements? As far as performance is concerned, you may have more function calls, but you are eliminating jumps (those nested if/switches). For example, if your state is five levels deep and you need to keep pausing and returning to that point, you hit all those switch statements every time. With the above approach? You jump directly into the function you left off in. I’m not sure which one is faster in general (really depends on application), but the cost of switches vs function calls will be insignificant compared to what normal applications are actually doing (like system calls for I/O).
I have working C and C++ examples of what a complete state machine looks like. There is also some micro-benchmarking numbers in there comparing C vs C++ (you take a hit in C++ due to inheritance, but that cost is fairly insignificant).
Thoughts?
Another choice I didn’t bother to mention is to have one thread per connection and let it block, but that doesn’t scale. What methods have you used to solve this? Do the nested switch/whiles offend you? Are the function pointer stacks elegant or spaghetti code?
URL: http://oddments.org/?p=157
_______________________________________________ Mailing list: https://launchpad.net/~drizzle-discuss Post to : [email protected] Unsubscribe : https://launchpad.net/~drizzle-discuss More help : https://help.launchpad.net/ListHelp
