djm's scribble

I have been playing around with replacing or renovating parts of OpenSSH’s sshd server, especially replacing the hand-crafted (and brittle) mainloop with Niels’ libevent. While playing with this on the bus, it occurred to me that several large chunks of the application would be more clear if the state machines they implemented were more explicit. The privilege separation monitor and the channels system (port forwarding, login session, etc.) are good examples of this.

Because there are several places I’d like to do this, I wrote a small code generator to help: cfsm. cfsm takes a simple text state machine specification and outputs a C source and header file and optionally a graphviz dot file for plotting (see below). The code it generates includes transition checking, so it should be impossible to make any transition not expliclty defined. It also allows for the definition of precondition callbacks that muct be satisfied before a transition is allowed. A small example:

state T1a
        initial-state
        next-state T2
	onexit-func do_something
state T1b
        initial-state
        next-state T2
state T2
        next-state T3
	exit-precondition is_bottom_half_of_the_hour
state T3
        next-state T2
        next-state T3
        next-state T4
state T4
	entry-precondition am_i_in_a_good_mood

This produces the following FSM API: (comments abridged)

enum state { T1a = 0, T1b = 1, T2 = 2, T3 = 3, T4 = 4, };
struct fsm;
struct fsm *state_init(enum state initial_state,
    char *errbuf, size_t errlen);          /* Allocate a FSM */
void state_free(struct fsm *fsm);          /* Free a FSM */
int state_advance(struct fsm *fsm, enum state new_state,
    char *errbuf, size_t errlen);          /* Move to a new state */
const char *state_ntop(enum state);        /* State number -> name */
const char *state_ntop_safe(enum state);   /* Same, but doesn't return NULL */
enum state state_current(struct fsm *fsm); /* Returns the current state */

The user of the API will need to provide the callback functions:

/* Preconditions - must return 0 on success */
int is_bottom_half_of_the_hour(enum state current_state, enum state new_state);
int am_i_in_a_good_mood(enum state current_state, enum state new_state);
/* Transition function */
int do_something(enum state current_state, enum state new_state);

In case you are wondering what the graphviz output looks like, here is an example:

(yes, I know I am abusing standard notation)

This is all very basic stuff, but I think that having simple tools like this around saves time (well, when amortised over their lifespans) and reduces mistakes. The code for cfsm is in anonymous CVS (:ext:anoncvs@anoncvs.mindrot.org/cvs via SSH) and is browsable via cvsweb. If anyone is interested I can make a tarball release of it - just let me know via email.