Unlocking Efficient and Declarative State Machine Implementation in Firmware Using SML Library 📚 (p1)

Abstract

Today we’re talking about a crucial aspect of firmware design – the Finite State Machine (FSM), commonly known as the State Machine. While the term might ring a bell for all engineers and most firmware developers, it’s interesting how often we overlook its explicit usage in our designs. Yet, at its core, every firmware or software program embodies a state machine or a cluster of them. However, when we use the state machines we usually rely on simplistic if/else or switch implementations.

We are going to elevate our mastery of state machines by introducing a game-changing, header-only library designed for state machine implementation – SML written by Kris Jusiak. Goodbye to spaghetti-like if/else and switch cases in your code; with this library, you’ll have an explicit transition table, enhancing the clarity of your implementation.

In our article today, we’re not just about theory; we’re diving into the practical side. we will talk about the significance of state machines in firmware design. In the next part, We will build a tangible project using the SML library, addressing the burning questions often pondered by embedded systems developers before adopting a new tool or library. We’ll initially construct it using the conventional if/else style, only to pivot later and implement it with the SML library. The burning question: Is SML truly worth the switch?

The project we will build is a counter built with: RP2040, two buttons to set the counter, 4 digits seven segments with a driver chip, and a buzzer. For sure this is not the best Hardware design for a counter, but I’ve built on purpose to have a realistic firmware with a good level of complexity with hardware limitation to make the state machine more challenging.

As a sneak peek, this is what the transition table will look like in SML. Even without knowing more details, I believe it looks informative and handy to you. Don’t worry about this code; we will explain it in detail later:

using namespace sml;
make_transition_table(
 *"src_state"_s + event<my_event> [ guard ] / action = "dst_state"_s,
  "dst_state"_s + event<game_over> = X
);

Today marks an experience I’m eager to explore by introducing a new type of content on this blog: integrating both video and written formats. If you’re interested in watching the same content in video format, please view the recording. Your comments are highly welcomed to make this experience successful.

A recap about state machine

In many small teams, start-up companies, and even hobby projects, the most popular coding style is to simply open up your favorite code editor or IDE and start coding without a clear firmware architecture in mind. Usually, only the hardware features are taken into account, and the code evolves through a process of trial and error. This approach is commonly known as “code now, debug later.” or I can call it “code now, architect as you go, or restructure later.” The question is not whether it is right or wrong, because many firmware and embedded systems engineers follow this approach and release successful products to the market.

Before we dive in, let’s acknowledge a crucial note: much like everything in life, designing firmware isn’t binary. It’s not a one-size-fits-all scenario, and the use of a state machine isn’t a universal rule for every situation. As Jacob wisely notes in his book:

/tab

All design and development cycles will not be alike! Some teams can successfully deliver their products using minimal design and processes. This is because they have a smaller problem domain.

For example, other teams, maybe ones working in the safety-critical system, have a much larger problem domain, resulting in more development processes to ensure success. The key is to identify your challenges correctly to balance your design and development processes to maximize the chances of success!

“Embedded Software Design: A Practical Approach to Architecture, Processes, and Coding Techniques” by Jacob Beningo

Beyond the technical lens, consider the psychological angle—having a clear or somewhat clear structure, even if imperfect, proves invaluable for maintaining focus. In the words of blogger Scott Young, “Ambiguity kills focus.” State machine, a guiding tool to monitor your final goal, and track progress, and achievements.

The state machine has various representations, and for our discussion, we’ll be using the UML state machine. UML, short for Unified Modeling Language, offers a standardized method for visualizing system designs. While the UML specification encompasses various design diagrams, our attention today is solely on state machines.

It is important to understand the following representation which is the building block for the state machine. A source state may transition to a destination state triggered by a specific event and a valid condition. During this transition, a designated action is executed, and the destination state becomes the new state of the system.

Example: A turnstile with a coin collector

Let’s consider a practical example: envision a turnstile equipped with a coin collector. By default, the gate is in the “locked” state. Now, when the event of inserting a coin occurs, the firmware checks if the coin is valid. If both the event and the condition align, the state transitions to “unlocked.” To revert to the “locked” state, one must push the gate, completing the cycle. This simple yet illustrative scenario showcases the essence of state machine dynamics, where events, conditions, and actions dictate transitions between different states.

A recap about “Rise of the State Machines” talk?

What inspired me to create this article was a compelling talk by Kris Jusiak, the creator of the SML library, at the Cpp Now 2019 conference titled “Rise of the State Machines.” In this talk, Kris astoundingly compared over eight ways to implement a state machine. Each method was scrutinized through demo code, showcasing their respective pros and cons. What sets Kris Jusiak’s presentation apart is his comparison of state machines, including his own creation, the State Machine Library SML (or boost-ext::sml).

While Kris’s talk is outstanding, it delves into details that might not captivate all firmware developers. Additionally, embedded systems developers are inherently focused, especially when dealing with resource-constrained circuits. Hence, I’ve taken the initiative to distill and focus on Kris’s insights within the firmware context.

These considerations provide a comprehensive view of the library’s suitability for embedded systems. Kris Jusiak’s “Rise of the State Machines” talk introduced various methods for implementing state machines, categorized as follows:

1- Naive: if/else (C++98) switch/enum (C++98) inheritance/state pattern (C++98).

2- STL: std::variant(C++17) Coroutines(C++20).

3- Boost: Boost.Statechart(C++98) Boost.MSM(C++98) [Boost].SML(C++14).

In Kris talk, he presented over eight different possible implementations for a demo system connection feature as shown bellow.

if/else and switch/enum implementations

Using if/else and switch/enum statements is quite common due to their small memory footprint and potential for inlining. However, they can get a bit tricky to manage and extend down the road, especially for developers who didn’t write the original code. In firmware development, where keeping things simple and understandable is key, it’s essential to consider the long-term maintainability of our code. You can check the attached code in Kris talk for if/else implementation and for switch/enum. Both implementation are: 🟢inlined – 🟢No heap usage – 🟡Hard to reuse.

inheritance/state pattern implementations

Another approach to implementing state machines is by using the State Pattern from object-oriented programming design patterns. While this approach is easier to extend and maintain compared to if/else and switch statements, it tends to consume more memory and relies on heap allocation, which may not be ideal for many cases.You can check the attached code in Kris talk for inheritance/state pattern implementations implementation. This implementation is: 🟢Easy to extend/reuse – 🟡High-ish memory usage – 🔴Heap usage – 🔴use devirtualization.

variant implementation

std::variant is a type-safe union that allows storing values of different types, ensuring type safety at compile-time. Kris utilized std::variant to hold the states in his implementation. While std::variant offers advantages such as 🟢reducing memory footprint and 🟢potentially enabling code inlining (particularly in Clang), it also presents 🟡challenges in terms of reusability. You can check the attached code in Kris talk for variant.

Coroutines implementation

“A coroutine is a special type of function that can be suspended and later resumed. When a coroutine is suspended, its state is saved, and it can be resumed from where it left off”. I can imagine how horrific it seems for embedded developers. That will require unbelievable care for the stack memory and will look like as if we are writing a small RTOS for the state machine. I personally, would not choose it for an MCU program. In this implementation, there will not be an explicit state as a variable.

I don’t have experience with coroutine, but by reading a well-written blog post called “The downsides of C++ coroutines” I can see how complicated and costly to adapt coroutines. I don’t advocate ignorance, but in the embedded systems context, such features are not adopted unless there is a real need for it. You can check the attached code in Kris talk for coroutines implantation code. This implementation is: 🟢inlined – 🟢No heap usage – 🔴Hard to reuse.

Boost.Statechart and Boost.MSM implementations

Both Statechart and MSM are Boost libraries dedicated for state machines implementation in C++. Both support UML (UML 1.5v for Statechart and UML 2.0 for MSM). However Statechart library suffers from: 🔴Dynamic allocation usage – 🔴High footprint. On the other hand, MSM is: 🟢Declarative – 🟢small memory footprint – 🟡Slow compilation time – 🟡Macro based. You can check the attached code in Kris talk for Statechart and MSM.

SML Library: Simplified Overview

let’s take a moment to grasp the fundamentals of this library. Here are some facts about the library:

• This library is “header-only,”. Essentially, you only need to acquire the header file and include it in your code to start using the SML library. It’s as straightforward as adding the line: #include <boost/sml.hpp>.
• A good aspect of SML is that it’s built using C++14, a widely supported standard in many Software Development Kits (SDKs) and Real-Time Operating Systems (RTOSs). You’ll find support for C++14 in various platforms such as Arduino cores, Mbed OS, Raspberry Pi Pico SDK, and Zephyr.
• SML offers a Domain Specific Language (DSL) for implementing state machines. The DSL is used while creating the transition table.

*"established"_s + event<release>          / send_fin  = "fin wait 1"_s,
 "fin wait 1"_s  + event<ack> [ is_valid ]             = "fin wait 2"_s,
 "fin wait 2"_s  + event<fin> [ is_valid ] / send_ack  = "timed wait"_s,
 "timed wait"_s  + event<timeout> 

Example: TCP connection transition table

struct tcp_release {
  auto operator()() const {
    using namespace sml;
    return make_transition_table(
      *"established"_s + event<release>          / send_fin  = "fin wait 1"_s,
       "fin wait 1"_s  + event<ack> [ is_valid ]             = "fin wait 2"_s,
       "fin wait 2"_s  + event<fin> [ is_valid ] / send_ack  = "timed wait"_s,
       "timed wait"_s  + event<timeout>                      = X
    );
  }
};
}

• The * symbol specifies the initial state of the state machine.
• Text enclosed in double quotations with the _s suffix defines a state name. These state names are later referenced in the state machine’s operations, such as sm.is("fin wait 1"_s), which sets the state to “fin wait 1”. The = sign is used to set the destination state.
• The event<fin> [ is_valid ] / send_ack notation represents an event fin with a condition (guard) is_valid that must evaluate to true. Upon triggering, the action send_ack is executed. Note: An transition may not have an action or a guard.
• X represents the terminate state, indicating the end of event processing.

This structured approach provides clarity and flexibility in defining the behavior of the state machine within the SML framework.

Postfix and Prefix Notations

It’s worth noting that the SML library supports both postfix and prefix notations for defining state machine transitions. For instance:

In postfix notation, we start with the source state and end with the destination state like bellow:

"fin wait 1"_s + event<ack> [ is_valid ] = "fin wait 2"_s

In prefix notation, we start with the destination state and end with the source state like bellow:

"fin wait 2"_s <= "fin wait 1"_s + event<ack> [ is_valid ]

Both notations achieve the same result, offering flexibility in expressing state transitions within the SML framework. Developers can choose the notation that best fits their coding style and preferences.

PlantUML and SML

The author of the library designed the SML’s DSL to be as close as possible to plantuml scripting language. Check how close it is from bellow. Using the online PlantUML compiler, try how the generated state machine will look like using PlantUML.

@startuml
[*] --> established
established -> fin_wait_1: release / send_fin 
fin_wait_1 -> fin_wait_2: ack[is_valid] 
fin_wait_2 -> timed_wait : fin[is_valid] / send_ack
timed_wait --> [*] : timeout
@enduml

Event and Guards

State transitions in SML are triggered by events, which should be of a unique type, typically implemented as a struct. Here’s an example for the TCP release connection:

struct ack { bool valid{}; };
struct fin { int id{}; bool valid{}; };
struct release {};
struct timeout {};  

Guards and actions in SML execute once an event occurs, and they need to be callable objects. One convenient way to define them is using C++ lambda functions. Here’s an example of how you can use lambda functions for guards and actions:

const auto is_valid = [](const ack&) { return true; };
const auto send_fin = [] {};
const auto send_ack = [] {};

Creating a state machine instance

Using the previously created struct tcp_release , we create a state machine instance like bellow:

  using namespace sml;

  sm<tcp_release> sm;
  assert(sm.is("established"_s));

The assert(sm.is("established"_s)); will check if the created state machine instance has the correct initial state.

assert(sm.is(sml::X)); can be used to check whether a State Machine is in terminate state or not. We can do the same to check if the state machine is in an expected state or not.

  sm.process_event(release{});
  assert(sm.is("fin wait 1"_s));

  sm.process_event(ack{});
  assert(sm.is("fin wait 2"_s));

  sm.process_event(fin{});
  assert(sm.is("timed wait"_s));

  sm.process_event(timeout{});
  assert(sm.is(X));

Sub-states

In certain situations, we might encounter composite or sub-states, and the SML library supports this. Consider the following example: A device that operates with a main state machine for the overall system and a subsidiary one specifically for managing connections.

The main system state machine is like what we saw previously except that the transition from Idel is going to transit to the sub-state machine Connection.

class System {
  struct Connection; // Connection State Machine

 public:
  auto operator()() const {
    using namespace sml;
    return make_transition_table(
     * "Idle"_s          + event<power_up> [ has_battery and
                                             is_healthy ] / setup = state<Connection>,
       state<Connection> + event<suspend>                         = "Suspended"_s,
       "Suspended"_s     + event<resume>                          = state<Connection>
    );
  }
};

The sub-state machine will be another regular transition table like:

struct Connection {
    auto operator()() const {
      using namespace sml;
      // clang-format off
      return make_transition_table(
        * "Disconnected"_s  + event<connect> / establish                = "Connecting"_s,
          "Connecting"_s    + event<established>                        = "Connected"_s,
          "Connected"_s     + event<ping> [ is_valid ] / resetTimeout,
          "Connected"_s     + event<timeout> / establish                = "Connecting"_s,
          "Connected"_s     + event<disconnect> / close                 = "Disconnected"_s
      );
      // clang-format on
    }
  };

Orthogonal Regions

Another important aspect of state machines is the concept of orthogonal regions, where a system can have multiple state machines operating concurrently. An example of this is the watchdog timer often found in embedded systems.

struct System {
  struct Connection; // Connection State Machine
  auto operator()() const {
    return make_transition_table(
     * "Idle"_s          + event<power_up> [ has_battery and
                                             is_healthy ] / setup = state<Connection>,
       state<Connection> + event<suspend>                         = "Suspended"_s,
       "Suspended"_s     + event<resume>                          = state<Connection>
       "Suspended"_s     + event<ping> / defer
     // ----------------------------------------------------------------------------- //
     * "Watchdog"_s      + event<tick> / resetTimeout,
       "Watchdog"_s      + event<timeout>                         = X
    );
  }
};

Note: In orthogonal regions you can notice how we have two initial states; one for each state machine.

Debugging/Logging

A common question that arises for firmware developers is related to debugging support in such a library. Fortunately, Kris has already taken this into consideration and included logging support in his library. All you need to do is implement your logging struct as shown below:

struct my_logger {
  template<class T>
  auto name() { return sml::aux::get_type_name<T>(); }

  template <class SM, class TEvent>
  void log_process_event(const TEvent&) {
    printf("[%s][process_event] %s\n", name<SM>(), name<TEvent>());
  }
  template <class SM, class TGuard, class TEvent>
  void log_guard(const TGuard&, const TEvent&, bool result) {
    printf("[%s][guard] %s %s %s\n", name<SM>(), name<TGuard>(), name<TEvent>(),
      (result ? "[OK]" : "[Reject]"));
  }
  template <class SM, class TAction, class TEvent>
  void log_action(const TAction&, const TEvent&) {
    printf("[%s][action] %s %s\n", name<SM>(), name<TAction>(), name<TEvent>());
  }
  template <class SM, class TSrcState, class TDstState>
  void log_state_change(const TSrcState& src, const TDstState& dst) {
    printf("[%s][transition] %s -> %s\n", name<SM>(), src.c_str(), dst.c_str());
  }
};

Then you need to pass it as a template argument while creating the state machine:

my_logger logger;
sml::sm<logging, sml::logger<my_logger>> sm{logger};

Other functions can be used to do other kind of debugging like:

assert(connection.is("Connecting"_s));

And visit_current_states to print the current state name. Like that:

connection.visit_current_states([](auto state) {
  std::cout << state.c_str() << std::endl;
});

SML to PlantUML Converter

Let’s conclude this brief introduction to SML by showcasing a code snippet from Kris, which allows you to convert the transition table into PlantUML format. This feature facilitates visualizing the state machine transitions, enhancing understanding and debugging capabilities.

#include <boost/sml.hpp>
#include <cstdio>
#include <iostream>

namespace sml = boost::sml;

namespace {

struct connect {};
struct ping { bool valid = false; };
struct established {};
struct timeout {};
struct disconnect {};

const auto establish = []{ std::puts("establish"); };
const auto close = []{ std::puts("close"); };
const auto is_valid = [](const auto& event) { return event.valid; };
const auto resetTimeout = [] { std::puts("resetTimeout"); };

struct Connection {
  auto operator()() const {
    using namespace sml;
    return make_transition_table(
      * "Disconnected"_s + event<connect> / establish                = "Connecting"_s,
        "Connecting"_s   + event<established>                        = "Connected"_s,
        "Connected"_s    + event<ping> [ is_valid ] / resetTimeout,
        "Connected"_s    + event<timeout> / establish                = "Connecting"_s,
        "Connected"_s    + event<disconnect> / close                 = "Disconnected"_s
    );
  }
};

template<class T>
auto name() { return  boost::sml::aux::get_type_name<T>(); }

template <class T>
void dump_transition() noexcept {
  auto src_state = std::string{sml::aux::string<typename T::src_state>{}.c_str()};
  auto dst_state = std::string{sml::aux::string<typename T::dst_state>{}.c_str()};
  if (dst_state == "X") {
    dst_state = "[*]";
  }

  if (T::initial) {
    std::cout << "[*] --> " << src_state << std::endl;
  }

  std::cout << src_state << " --> " << dst_state;

  const auto has_event = !sml::aux::is_same<typename T::event, sml::anonymous>::value;
  const auto has_guard = !sml::aux::is_same<typename T::guard, sml::front::always>::value;
  const auto has_action = !sml::aux::is_same<typename T::action, sml::front::none>::value;

  if (has_event || has_guard || has_action) {
    std::cout << " :";
  }

  if (has_event) {
    std::cout << " " << name<typename T::event>();
  }

  if (has_guard) {
    std::cout << " [" << name<typename T::guard>() << "]";
  }

  if (has_action) {
    std::cout << " / " << name<typename T::action>();
  }

  std::cout << std::endl;
}

template <template <class...> class T, class... Ts>
void dump_transitions(const T<Ts...>&) noexcept {
  (dump_transition<Ts>(), ...);
}

template <class SM>
void dump(const SM&) noexcept {
  std::cout << "@startuml" << std::endl << std::endl;
  dump_transitions(typename SM::transitions{});
  std::cout << std::endl << "@enduml" << std::endl;
}

}

int main() {
  sml::sm<Connection> connection{};
  dump(connection);
}

SML Policies

The SML library offers policies that enable developers to customize the state machine implementation at compile time. For instance, you can choose different dispatching mechanisms such as jump table, switch, if/else, or fold expressions.

Name	POLICY
Jump Table	jump_table
Switch	switch_stm
If/else	branch_stm
Fold expressions	fold_expr

You specify the policy at state machine instance creation like bellow:

sml::sm<Connection, sml::dispatch<sml::back::policies::POLICY>> sm{};

How good is the SML (Benchmark) ?

Kris mentioned a benchmark to measure various metrics, including compilation time, execution time, memory usage, executable size, and lines of code (LoC). These metrics provide valuable insights into the performance and efficiency of different state machine implementations. By comparing these metrics across different implementations, developers can make informed decisions about which approach best suits their project requirements and constraints.

The test includes 50 states with 50 transitions like below

The results of the test setup:

The implementation code for each case can be found in the library repository. Additionally, Kris’s slides provide detailed benchmarks comparing metrics such as lines of code (LoC), assembly lines, execution time, compilation time, and more across the eight various state machine implementation techniques mentioned in his talk.

Notable Firmware Example with SML State Machine

Discovering numerous questions about the boost::SML library across platforms like StackOverflow, the Arduino Forum, and GitHub issues is a strong indicator of its widespread adoption by developers, which is generally a positive sign. Interestingly, I’ve noticed employees from various companies seeking assistance with SML in their code, although these companies may not publicly disclose their code structure or tools. One notable example of a commercial product utilizing the SML library is Leka, a playful educational companion robot designed for children with disabilities. Built on top of Mbed OS, Leka implements SML beautifully—a shoutout to the team behind it!

In StateMachine.h you will find the transition table. You need to go through the code to understand how other drivers and parts of the code interact with the state machine.

Read more

By reaching this point, we’ve covered the most important aspects of the SML library. However, it’s important to note that this introduction may not cover all details comprehensively. To gain a deeper understanding, I recommend attending Kris’s talk or reading the official documentation provided by the library. These resources will provide you with more in-depth information and insights into utilizing the SML library effectively.

• SML Tutorial
• SML User guide
• SML Examples
• “Rise of the State Machines” – Cpp Now 2019
• “Embedding a Meta State Machine” at EmBo++ 2018