Finite-state machines

4 minute read

All services in the Lely CANopen stack are asynchronous and therefore implemented as event-driven finite-state machines (FSMs). Each implementation follows the pattern shown here. To ensure the maintainability and extensibility of these state machines, the pattern was designed to have the following properties:

Adding a new event does not affect existing states;
Adding a new state is a local change; it does not modify existing functions.

Additionally, the implementation should support parametrized events and transient states (states which transition to another state without an external event). The latter greatly simplifies error handling.

The first property excludes implementations based on a state transition table, while the second excludes enum-based state machines. Additionally, transient states are hard to implement in either approach.

The implementation shown here is an extension of the function-pointer-based state machine and is similar to the object-oriented state design pattern. The state machine is an object containing the context and a pointer to the current state. Each state is a (constant) array of pointers to transitions functions, one for each event. The transition functions return a pointer to the next state, or NULL if no transition occurs. There are two special (optional) transition functions, on_enter() and on_leave(), called when a state is entered or left, respectively. A transient state is simply a state whose on_enter() function exists and returns a pointer to another state.

Example of a public C header (lely/lib/fsm.h):

#ifndef LELY_LIB_FSM_H_
#define LELY_LIB_FSM_H_

typedef struct fsm fsm_t;

#ifdef __cplusplus
extern "C" {
#endif

// Checks if the FSM is currently in the idle state.
int fsm_is_idle(const fsm_t *fsm);

// Issues a request to the FSM. This function returns 0 on success, or -1 on
// error (e.g., because the FSM is not in the idle state).
int fsm_req(fsm_t *fsm, Args... args);

#ifdef __cplusplus
}
#endif

#endif // !LELY_LIB_FSM_H_

Example of the C implementation (fsm.c):

#include <lely/lib/fsm.h>
#include <lely/libc/time.h>
#include <lely/util/errnum.h>

#include <assert.h>

// A state is a constant collection of function pointers.
typedef const struct fsm_state fsm_state_t;

struct fsm {
	...
	// A pointer to the current state.
	fsm_state_t *state;
	...
};

// A helper function for entering a new state.
static void fsm_enter(fsm_t *fsm, fsm_state_t *next);

// A helper function for generating an event and invoking the corresponding
// transition function.
static inline void fsm_emit_event(fsm_t *fsm, Args... args);

// A helper function for generating a timeout event.
static inline void fsm_emit_time(fsm_t *fsm, const struct timespec *tp);

struct fsm_state {
	// The function called when the state is entered. If this function is
	// specified, its return value is taken to be the next state and a
	// transition will automatically occur.
	fsm_state_t *(*on_enter)(fsm_t *fsm);
	// Events can carry parameters which are passed as arguments to the
	// transition function.
	fsm_state_t *(*on_event)(fsm_t *fsm, Args... args);
	// It is common for services to define a timeout event.
	fsm_state_t *(*on_time)(fsm_t *fsm, const struct timespec *tp);
	// The function called when a state is left. This function cannot return
	// another state, since the next state is already specified.
	void (*on_leave)(fsm_t *fsm);
};

// A macro designed to improve the readability of state definitions.
#define LELY_LIB_DEFINE_STATE(name, ...) \
	static fsm_state_t *const name = &(fsm_state_t){ __VA_ARGS__ };

// The idle state does not contain any transition functions.
LELY_LIB_DEFINE_STATE(fsm_idle_state, NULL)

// The initialization state is transient and only specifies on_enter().
static fsm_state_t *fsm_init_on_enter(fsm_t *fsm);
LELY_LIB_DEFINE_STATE(fsm_init_state,
	.on_enter = &fsm_init_on_enter
)

// The waiting state responds to events and timeouts.
static fsm_state_t *fsm_wait_on_event(fsm_t *fsm, Args... args);
static fsm_state_t *fsm_wait_on_time(fsm_t *fsm, const struct timespec *tp);
LELY_LIB_DEFINE_STATE(fsm_wait_state,
	.on_event = &fsm_wait_on_event,
	.on_time = &fsm_wait_on_time
)

// Like the initialization state, the finalization state is transient.
static fsm_state_t *fsm_fini_on_enter(fsm_t *fsm);
LELY_LIB_DEFINE_STATE(fsm_fini_state,
	.on_enter = &fsm_fini_on_enter
)

#undef LELY_LIB_DEFINE_STATE

struct fsm *
fsm_init(struct fsm *fsm, Args... args)
{
	...

	fsm->state = NULL;
	// Enter the idle state and wait for the user to issue a request.
	fsm_enter(fsm, fsm_idle_state);

	...
}

int
fsm_is_idle(const fsm_t *fsm)
{
	assert(fsm);

	// States are uniquely identified by their address and can be compared
	// directly.
	return fsm->state == fsm_idle_state;
}

int
fsm_req(fsm_t *fsm, Args... args)
{
	assert(fsm);

	if (!fsm_is_idle(fsm)) {
		set_errnum(ERRNUM_INPROGRESS)
		return -1;
	}

	// Construct request based on args.
	...

	// Enter the initialization state.
	fsm_enter(fsm, fsm_init_state);
	return 0;
}

static void
fsm_enter(fsm_t *fsm, fsm_state_t *next)
{
	assert(fsm);

	// Use a loop to allow transient state sequences of arbitrary length.
	while (next) {
		// Set the next state before invoking on_leave(). It is common
		// for services to invoke a user-defined callback function from
		// on_leave(). By setting the next state before doing so, it
		// becomes possible for the callback function to issue the next
		// request without waiting for on_leave() to complete.
		fsm_state_t *prev = fsm->state;
		sdo->state = next;

		// Invoke the on_leave() function if specified.
		if (prev->on_leave)
			prev->on_leave(fsm);

		// Enter the next state and invoke its on_enter() function, if
		// specified. If this function returns another state, enter it
		// in the next iteration.
		next = next->on_enter ? next->on_enter(fsm) : NULL;
	}
}

static inline void
fsm_emit_event(fsm_t *fsm, Args... args)
{
	assert(fsm);
	assert(fsm->state);
	// We could choose to do nothing if no transition function is specified,
	// but an assertion allows us to detect unexpected events.
	assert(fsm->state->on_event);

	fsm_enter(fsm, fsm->state->on_event(fsm, args...));
}

static inline void
fsm_emit_time(fsm_t *fsm, const struct timespec *tp)
{
	assert(fsm);
	assert(fsm->state);
	assert(fsm->state->on_time);

	fsm_enter(fsm, fsm->state->on_time(fsm, tp));
}

static fsm_state_t *
fsm_init_on_enter(fsm_t *fsm)
{
	assert(fsm);

	// Perform initialization.
	...

	// This is a transient state; it transitions to the waiting state
	// without waiting for an event.
	return fsm_wait_state;
}

static fsm_state_t *
fsm_wait_on_event(fsm_t *fsm, Args... args)
{
	assert(fsm);

	// Process the event.
	...

	// If the event completes the request, enter the finalization state.
	return fsm_fini_state;
}

static fsm_state_t *
fsm_wait_on_time(fsm_t *fsm, const struct timespec *tp)
{
	assert(fsm);

	// A timeout occurred. Abort and clean up.
	...

	// Abort the request by returning to the idle state.
	return fsm_idle_state;
}

static fsm_state_t *
fsm_fini_on_enter(fsm_t *fsm)
{
	assert(fsm);

	// Perform finalization.
	...

	// This is a transient state; it automatically transitions to the idle
	// state.
	return fsm_idle_state;
}