Common Embedded Patterns: Finite State Machine

This is the third part of the series re-exploring common embedded patterns. This one focuses on the finite state machine. The complete, tested source lives in the companion repo: ileanmjr88/tetzontli. Each pattern in this series is its own module with a full GoogleTest suite, so you can clone it and run the tests yourself. The suite also wires up the full motor controller used throughout this post, so it doubles as the usage example. Basic Concept A finite state machine is one of the most common ways we design behavior into a system, and in embedded it is especially important. Behavior is what turns hardware into a product: the system has to know what it is doing right now, and what to do when something happens. Think of it like following a recipe for bread. You gather the ingredients, mix the dry ones, mix the wet ones, then combine the two. Each step is a state. You are in exactly one at a time, and you only move on when that step is done. The recipe also has notes like "if the dough is too watery, add flour; if it is too firm, add water." Those notes are the interesting part. Something happens (you check the dough), a condition decides which note applies (too watery or too firm), and you take an action (add flour or water) before carrying on. That is all a state machine is: states, the events that arrive while you are in them, the conditions (guards) that decide which rule applies, and the actions you take. Modeling behavior this way is what lets a system adapt. We would all like perfect, ideal conditions, but the real world is chaotic, and the system has to handle it anyway. Almost every embedded system is a state machine: a button debouncer, a modem driver, a battery charger, a bootloader. Most start life as switch(state) with a nested switch(event) in each case. That works for three states and four events. By ten states it is a wall of cases where the behavior is scattered across hundreds of lines, entry and exit logic is copy-pasted, and nobody can answer "what happens if OVERTEMP arrives while we are CHARGING?" without reading all of it. The Idea The recipe showed that we all already use state machines. Before looking at an example state machine, let's pin down the vocabulary, since every representation that follows uses the same five ideas. State: what the system is doing right now. In the recipe, each step is a state. The system is always in exactly one. Event: something that happens and needs a response, like an input, a timer firing, or a sensor reading. In the recipe, checking the dough. Guard: a condition that decides whether a rule applies. In the recipe: is the dough too watery? Action: what the system does in response. In the recipe: add flour. Transition: moving from one state to another because of an event (and its guard). In the recipe: the dough is ready, so you move on to the next step. Here's the motor controller from the GoogleTest suite, written the switch way. It has four states (IDLE, ARMED, RUNNING, FAULT) and events like EV_ARM, EV_START, and EV_ESTOP. if (event == EV_ESTOP) { /* any state / motor_off(); state = FAULT; return; } switch (state) { case IDLE: if (event == EV_ARM) { state = ARMED; } break; case ARMED: switch (event) { case EV_DISARM: state = IDLE; break; case EV_START: if (battery_ok()) { state = RUNNING; } else { warn_battery_low(); / stay ARMED / } break; default: break; } break; case RUNNING: switch (event) { case EV_STOP: state = ARMED; break; case EV_SET_SPEED: set_speed(); / stay RUNNING / break; case EV_OVERCURRENT: motor_off(); state = FAULT; break; default: break; } break; case FAULT: if (event == EV_RESET && fault_cleared()) { state = IDLE; } break; } It works, but look at what's already happening with just four states. The emergency stop had to live outside the switch, because a rule that applies to every state has no natural home. To answer "what does EV_START do when the battery is low?" you have to trace nested branches. And every case needs its break: my first draft of this example was missing several, and it silently fell through from IDLE into ARMED. Add ten states and twenty events, and this becomes hundreds of lines where nobody can see the whole behavior at once. Table-Driven State Machine Here's the same behavior as a table: static const sm_transition_t kMotorTable[] = { // from event guard action to {SM_ANY_STATE, EV_ESTOP, NULL, motor_off, FAULT}, {IDLE, EV_ARM, NULL, NULL, ARMED}, {ARMED, EV_DISARM, NULL, NULL, IDLE}, {ARMED, EV_START, battery_ok, NULL, RUNNING}, {ARMED, EV_START, NULL, warn_battery_low, ARMED}, {RUNNING, EV_STOP, NULL, NULL, ARMED}, {RUNNING, EV_SET_SPEED, NULL, set_speed, RUNNING}, {RUNNING, EV_OVERCURRENT, NULL, motor_off, FAULT}, {FAULT, EV_RESET, fault_cleared, NULL, IDLE}, }; Each row defines a single rule. The from state and the event together act as the key: when an event arrives, the state machine looks for a row that matches its current state and that event. The guard is an optional condition that has to be true for the rule to apply. If it is, the machine runs the action (if there is one) and moves to the to state. Rules are checked from top to bottom, and the first matching rule wins. That one convention does a lot of work: The SM_ANY_STATE row for EV_ESTOP sits at the top, so an emergency stop wins from any state. It finally has a natural home. The two ARMED, EV_START rows depend on order: the rule guarded by battery_ok is checked first, and the unguarded rule underneath is the fallback that warns about the battery. Swap them, and the warning always fires. If no rule fires, like EV_RESET while the fault hasn't cleared (the row matches, but its guard says no), nothing happens and the machine stays where it is. The whole behavior now fits on one screen, and it reads like a specification. Answering "what does EV_START do when the battery is low?" means reading two rows instead of tracing nested branches. Implementation Having compared a switch-based state machine with a table-driven one, the natural question is: what actually triggers the guards and actions? The short answer is sm_dispatch, but first we need the pieces it works with. The behavior lives in two caller-owned tables: the transition table (sm_transition_t), which defines how the machine responds to events, and an optional hooks table (sm_state_hooks_t), which defines what each state does when it's entered, while it's active, and when it's left. Table Structs The transition table. Each row reads as one sentence: in from, on event, if guard passes, run action and go to to. // modules/state_machine/state_machine.h typedef struct { sm_state_t from; /< State, or SM_ANY_STATE. */ sm_event_t event; /< Triggering event. */ sm_guard_fn guard; /< NULL = always passes. */ sm_action_fn action; /< NULL = no action. */ sm_state_t to; /< Next state. */ } sm_transition_t; The hooks table (optional). One entry per state, each with on_entry, on_exit, and on_run. Entry and exit logic live in one place per state, instead of being repeated on every transition that touches it. // modules/state_machine/state_machine.h typedef struct { sm_action_fn on_entry; /< NULL = none. */ sm_action_fn on_exit; /< NULL = none. */ sm_run_fn on_run; /< NULL = none. */ } sm_state_hooks_t; For the motor, the hooks table looks like this: static const sm_state_hooks_t kMotorHooks[STATE_COUNT] = { // on_entry on_exit on_run {idle_entry, NULL, NULL}, // IDLE {NULL, NULL, NULL}, // ARMED {running_entry, running_exit, running_run}, // RUNNING {fault_entry, NULL, NULL}, // FAULT }; One entry per state, in enum order. IDLE and FAULT engage the brake when entered, ARMED needs nothing, and RUNNING turns the PWM output on in running_entry, off in running_exit, and polls the motor current in running_run. State Machine Struct The caller owns everything: the tables, the struct, the context. The library never allocates, which matters on systems where malloc isn't welcome (see the memory pool post). // modules/state_machine/state_machine.h typedef struct { const sm_transition_t *table; size_t count; const sm_state_hooks_t *hooks; sm_state_t state_count; sm_state_t current; bool started; void *ctx; } sm_t; Types Looking over the structs we used to define the tables, you may be wondering about some of the data types that aren't familiar. They're custom types defined by the library. // modules/state_machine/state_machine.h typedef uint8_t sm_state_t; /< 0 .. state_count - 1; 0xFF reserved. */ typedef uint8_t sm_event_t; /< Caller-defined; 0xFF reserved. */ #define SM_ANY_STATE ((sm_state_t)0xFFu) /< from wildcard: any state. */ #define SM_NO_EVENT ((sm_event_t)0xFFu) /< on_run: nothing to dispatch. */ typedef bool (*sm_guard_fn)(void *ctx); /< true = allow the row. */ typedef void (*sm_action_fn)(void *ctx); /< Action, entry or exit. */ typedef sm_event_t (*sm_run_fn)(void *ctx); /< Event or SM_NO_EVENT. */ sm_state_t and sm_event_t are uint8_t. The library can't know your states and events, so you define your own enum and the library just stores the numbers. Eight bits keep each table row small, at the cost of a limit: 255 states and events, with 0xFF reserved as a sentinel (SM_ANY_STATE for states, SM_NO_EVENT for events). For a firmware state machine, that's plenty. sm_guard_fn returns bool: should this row apply? It answers a question and changes nothing. sm_action_fn does the work. The same type serves transition actions and the on_entry and on_exit hooks, since they all have the same shape: do something, return nothing. sm_run_fn is the interesting one: it returns an event. A state's on_run can watch the world (poll a sensor, check a timeout) and report what happened, or return SM_NO_EVENT if nothing did. That's how a state generates its own events without the caller having to. Every callback takes void *ctx. The machine passes your context pointer through, so callbacks never need globals. That means you can run several independent machines, and in tests you can hand in a fake context and check exactly what happened. The functions that drive the machine return an sm_result_t, so the caller always knows what happened to an event: // modules/state_machine/state_machine.h typedef enum { SM_HANDLED, /< A row fired, or sm_run() had nothing to do. */ SM_UNHANDLED, /< No row matches. */ SM_GUARD_REJECTED, /< Rows matched; every guard rejected. */ SM_ERROR /*< NULL, not started, or state out of range. */ } sm_result_t; SM_HANDLED: a rule matched and fired, or sm_run() had nothing to do. SM_UNHANDLED: no rule exists for this state and event. The event was ignored. SM_GUARD_REJECTED: rules existed for this state and event, but every guard said no. The event was understood but blocked. SM_ERROR: misuse, not behavior. It covers a NULL argument, a machine that hasn't been started, or a state out of range. Init Function Like the ring buffer and memory pool, the state machine needs an init function. The caller owns the sm_t and the tables; sm_init validates them and wires them together. // modules/state_machine/state_machine.c bool sm_init(sm_t *sm, const sm_transition_t *table, size_t count, const sm_state_hooks_t *hooks, sm_state_t state_count, sm_state_t initial, void *ctx) { if (sm == NULL) { return false; } *sm = (sm_t){0}; if (table == NULL || count == 0u || state_count == 0u || initial >= state_count) { return false; } for (size_t i = 0u; i < count; i++) { if (table[i].from != SM_ANY_STATE && table[i].from >= state_count) { return false; } if (table[i].to >= state_count || table[i].event == SM_NO_EVENT) { return false; } } sm->table = table; sm->count = count; sm->hooks = hooks; sm->state_count = state_count; sm->ctx = ctx; sm->current = initial; return true; } NULL check on sm first. Without somewhere to write, there's nothing else to do. *sm = (sm_t){0}; happens before the rest of the validation, on purpose. If any later check fails, the caller is left with a zeroed machine: started is false and table is NULL. sm_start refuses it, and sm_dispatch and sm_run return SM_ERROR instead of acting on garbage. A failed init leaves the machine in a known safe state. Basic argument checks: the table must exist, count and state_count can't be zero, and initial must be a valid state. Every row is validated once, up front: from must be a real state or SM_ANY_STATE. to must be a real state. Since SM_ANY_STATE is 0xFF, which is always >= state_count, "any state" is automatically rejected as a destination. You can't transition to any state, and the check falls out for free. event can't be SM_NO_EVENT, since that value is reserved to mean "nothing happened." Then the fields are stored. Note what's not set: started stays false. Helper Functions Before we start the machine, let's look at two small helpers that keep the hooks optional at every level: // modules/state_machine/state_machine.c static void run_entry(const sm_t *sm, sm_state_t state) { if (sm->hooks != NULL && sm->hooks[state].on_entry != NULL) { sm->hooks[state].on_entry(sm->ctx); } } static void run_exit(const sm_t *sm, sm_state_t state) { if (sm->hooks != NULL && sm->hooks[state].on_exit != NULL) { sm->hooks[state].on_exit(sm->ctx); } } static: they're private to state_machine.c. Callers never invoke hooks directly; the machine decides when they run. Two NULL checks, two levels of "optional": the whole hooks table can be NULL (a machine with no hooks at all), and any single hook in it can be NULL (a state that only needs on_entry, say). Either way, nothing runs. Indexed by state, with no bounds check here. The helpers trust state, because every state that reaches them has already been validated: the initial state in sm_init, and each to state when its row was checked. Validate once at the edges, and the inner code stays simple. The caller's ctx is passed through, so hooks work on the caller's data, never globals. Start Function sm_init wires the machine together, but it doesn't run anything. Starting is a separate step: sm_start enters the initial state, running its on_entry hook, and marks the machine as live. // modules/state_machine/state_machine.c bool sm_start(sm_t *sm) { if (sm == NULL || sm->table == NULL || sm->started) { return false; } run_entry(sm, sm->current); sm->started = true; return true; } sm->table == NULL catches a failed init. Because sm_init zeroes the struct before validating, a machine that failed to initialize has a NULL table, so sm_start refuses it. That's the payoff of zeroing first. sm->started guards against starting twice. A second call would run the current state's on_entry again: re-enabling hardware or resetting a timer that's already running. Returning false makes the mistake visible instead of silently repeating side effects. run_entry(sm, sm->current) runs the initial state's on_entry hook, if there's a hooks table and that state has one, passing along the caller's ctx. Then started is set and the function returns true. Dispatch Function sm_dispatch does the heavy lifting: given an event, it finds the first rule that applies to the current state and carries it out. // modules/state_machine/state_machine.c sm_result_t sm_dispatch(sm_t *sm, sm_event_t event) { if (sm == NULL || !sm->started || sm->current >= sm->state_count) { return SM_ERROR; } bool matched = false; for (size_t i = 0u; i < sm->count; i++) { const sm_transition_t *row = &sm->table[i]; if ((row->from != sm->current && row->from != SM_ANY_STATE) || row->event != event) { continue; } matched = true; if (row->guard != NULL && !row->guard(sm->ctx)) { continue; } if (row->to != sm->current) { run_exit(sm, sm->current); } if (row->action != NULL) { row->action(sm->ctx); } if (row->to != sm->current) { sm->current = row->to; run_entry(sm, sm->current); } return SM_HANDLED; } return matched ? SM_GUARD_REJECTED : SM_UNHANDLED; } Defensive checks: a NULL machine, a machine that was never started (including one whose init failed), or a current state outside the valid range all return SM_ERROR. sm_init already validated the table, but this check is cheap insurance against a corrupted struct. A linear scan, top to bottom. A row matches when its from is the current state (or SM_ANY_STATE) and its event matches. Everything else is skipped. matched = true is set before the guard is checked. That one flag is what separates SM_UNHANDLED (no rule exists) from SM_GUARD_REJECTED (rules existed, but every guard said no). A failed guard means continue, not return. The scan keeps looking, which is exactly how the fallback works: in ARMED, the battery_ok row fails, so the next EV_START row (the battery warning) gets its chance. The order of a transition is exit, then action, then entry. The old state cleans up, the transition does its work, and then the new state sets itself up. First match wins: the function returns SM_HANDLED immediately, so later rows never run. Self-transitions don't re-run the hooks. When to equals the current state (like RUNNING on EV_SET_SPEED), only the action runs. Exit and entry are skipped. Changing speed shouldn't stop and restart the motor, which is exactly what running running_exit and then running_entry would do to the PWM output. Some frameworks re-run the hooks on self-transitions; I chose not to, because in embedded code entry and exit usually touch hardware. Guards, actions, and hooks must not call sm_dispatch or sm_run. During the action, the old state has already exited, but current hasn't been updated yet. A nested dispatch would see a state that's halfway through a transition. A nested call from a guard is no better: the outer scan is still partway down the table, and it would carry on comparing rows against a current that may have changed underneath it. If an action needs to trigger another event, queue it, and dispatch after the first one returns. (The ring buffer from part one is a natural event queue.) Run Function sm_run is what gets called from the main loop. Where sm_dispatch reacts to events someone else delivers, sm_run gives the current state a chance to look at the world and report its own. // modules/state_machine/state_machine.c sm_result_t sm_run(sm_t *sm) { if (sm == NULL || !sm->started || sm->current >= sm->state_count) { return SM_ERROR; } if (sm->hooks == NULL || sm->hooks[sm->current].on_run == NULL) { return SM_HANDLED; } sm_event_t ev = sm->hooks[sm->current].on_run(sm->ctx); if (ev == SM_NO_EVENT) { return SM_HANDLED; } return sm_dispatch(sm, ev); } Same defensive checks as sm_dispatch. Misuse returns SM_ERROR before any user code runs. No on_run, nothing to do. If there's no hooks table, or the current state has no on_run, it returns SM_HANDLED. That makes it safe to call sm_run on every pass of the loop, even when the current state only reacts to events from outside. The current state's on_run gets the caller's ctx and returns an event. This is where polling lives: reading a sensor, comparing a timer against a timeout, or checking a flag an ISR set. SM_NO_EVENT means nothing happened, which is the common case, so it returns SM_HANDLED. This is also why sm_init rejects any row with SM_NO_EVENT as its event: that value can never be dispatched. Anything else goes straight to sm_dispatch, and its result is returned as is. An event reported by on_run goes through the same table as one from the caller, so every transition takes the same path. This is why on_run returns an event instead of calling sm_dispatch itself. Returning lets the hook finish before the transition starts, so the machine never dispatches from inside one of its own hooks. It's the same rule as for actions: hooks report what happened, and the machine decides what to do about it. In the simplest case, where every event comes from a state's on_run, the main loop is a single call: for (;;) { sm_run(&motor_sm); } Most machines aren't that simple. In the motor example, EV_ARM, EV_START, and EV_ESTOP come from outside, so they still go through sm_dispatch. Current State Function The last function is the simplest: sm_state returns the state the machine is currently in. // modules/state_machine/state_machine.c sm_state_t sm_state(const sm_t *sm) { return (sm == NULL) ? SM_ANY_STATE : sm->current; } Read-only. It takes a const sm_t *, so asking can't change anything. The fields of sm_t are readable, but going through sm_state keeps callers from reaching into the struct. NULL returns SM_ANY_STATE. Since 0xFF can never be a real state, it doubles as "no answer." There's no need for a bool return and an out parameter the way ring_buffer_get does it. It doesn't check started. Before sm_start, it returns the initial state from sm_init. After a failed init it returns 0, from the zeroed struct, which looks like a real state. Check the return value of sm_init instead of relying on sm_state to tell you something went wrong. It's mostly for tests and logging. A typical test dispatches an event and then checks sm_state to confirm where the machine landed. Wrap-Up That's a complete state machine. The behavior lives in a table instead of a wall of switch cases, so the whole machine fits on one screen and reads like a specification. It does no dynamic allocation, validates its transition table once at init, and sends every event down the same path, whether it came from the caller or from a state's own on_run. The trades, all deliberate: Not ISR-safe or thread-safe. sm_dispatch reads and writes current with no protection. Events from an ISR go into a queue and get dispatched from one context. No re-entrant calls. Guards, actions, and hooks must not call sm_dispatch or sm_run on the same machine. on_run returns its event instead, and anything else gets queued. Guards must be side-effect free. A guard can run for a row that never fires, so it answers a question and changes nothing. Row order is behavior. The first match wins, so SM_ANY_STATE safety rows go first and guarded rows go above their fallbacks. Reordering the table changes what the machine does. Self-transitions skip entry and exit. Only the action runs, so changing speed doesn't stop and restart the motor. Linear scan. Each dispatch walks the table top to bottom, which is fine for dozens of rows. Flat machine. There are no hierarchical states, so behavior shared across states goes in SM_ANY_STATE rows. 255 states and 255 events. uint8_t keeps each row small, and 0xFF is reserved for SM_ANY_STATE and SM_NO_EVENT. The hooks table size isn't checked. sm_init only gets a pointer, so it can't tell whether hooks has state_count entries, and a short table means jumping through a garbage function pointer. Declare it as hooks[STATE_COUNT], with STATE_COUNT as the last value of your state enum. The compiler flags extra entries (build with -Werror to make that a hard error), and missing ones are zero-filled to NULL, which means no hook. sm_t fields are read-only. They're readable for debugging, but writing them skips the validation sm_init did. Ask sm_state where the machine is. Three patterns in, and this is the one where the data starts to mean something. Most embedded applications break down into a state machine once you list what the system can be doing and what can happen to it, and writing that list as a table forces you to answer every "what if" up front. The ring buffer and the pool gave us storage that didn't care what it held. The state machine decides what happens next, and since sm_event_t is a single byte, the ring buffer from part one can carry its events as they are. Next in the series is the command dispatcher. It reads its input straight out of a ring buffer and maps each command to the function that handles it, the same table-driven idea applied to text instead of events. See you there.