Principia Embedded: Strings in State-Time

Recap and Reflection

Getting ready to get back on the road, celebrate a few life-changing events, followed by a week in the country.

Can’t wait.

Nothing better than meandering through state-time at a quiet spot by the lake, the girls taking in fresh smells, my baby girl and I getting the ‘time’ — to reconnect without life getting in the way.

Can’t wait.

I’ve also been thinking a bit about our last installment. The arc we built as we traveled from simple decision trees through state machines. Things got ugly pretty quickly when reality showed up, and what began as a simple recipe for brewing a cup of coffee led to the creation of a machine that was no longer easily recognizable.

I’ve said this before in discussions on grinders and standards: I’m prudent when it comes to choosing the tools and methods for a particular situation.

And I’ll be fair as we venture into the strings of state-time:

There are no utopian solutions, and every decision creates consequences.

The nuance — the art of doing — is often the management of that line between principles and consequences.

And if there’s anything I’ve learned along the journey, it’s this:

Last time, we left the coffee maker at the edge of a question...

What if we could keep the clean, linear feel of the original recipe without falling back into the blocking trap?

Here’s a quick recap of the recipe:

• We check that there’s enough water.
• We wait until the pod cover is closed and the start button is pushed.
• We activate a heater to bring the water up to the desired temperature.
• We set a timer based on the size of the cup ((flow rate x time) == volume)
• We start a pump to dispense the water.
• We wait until the timer has expired.
• We turn off the pump.
• We turn off the heater.
• We return home.

Now consider the elegant simplicity of protothreads:

/**
 * @brief Run the coffee maker as a protothread.
 *
 * This version expresses the brew sequence in a linear, recipe-like form
 * while still allowing the system scheduler/super-loop to call it
 * cooperatively.
 *
 * @param pt Pointer to the protothread control structure.
 *
 * @return Protothread status.
 */
PT_THREAD(make_coffee(struct pt *pt))
{
    PT_BEGIN(pt);

    while (1)
    {
        /*
         * Wait until the user has closed the pod cover
         * and pressed the start button.
         */
        PT_WAIT_UNTIL(pt, pod_is_closed() && button_pushed());

        /*
         * If there is not enough water, tell the user and wait.
         */
        if (!reservoir_is_full())
        {
            display("add water\r\n");

            PT_WAIT_UNTIL(pt, reservoir_is_full() || pod_is_open());
        }
        if (pod_is_open())
        {
            display("wanna try again?\r\n");
            continue;
        }

        /*
         * Start heating.
         */
        start_heater();

        /*
         * Wait until the water reaches temperature,
         * or until the user opens the pod cover.
         */
        PT_WAIT_UNTIL(pt,
            (get_heater_temp() >= COFFEE_TEMPERATURE) ||
            pod_is_open()
        );

        /*
         * If the pod was opened while heating, fault out of this cycle.
         */
        if (pod_is_open())
        {
            stop_heater();
            display("wanna try again?\r\n");
            continue;
        }

        /*
         * Dispense.
         */
        start_timer(cup_size_time);
        start_water_pump();

        /*
         * Wait until dispense time expires,
         * or until the user opens the pod cover.
         */
        PT_WAIT_UNTIL(pt,
            timer_elapsed() ||
            pod_is_open()
        );

        stop_water_pump();
        stop_heater();

        if (pod_is_open())
        {
            display("wanna try again?\r\n");
        }
        else
        {
            display("enjoy your coffee!\r\n");
        }
    }

    PT_END(pt);
}

Let's look at what happened.

The state didn't disappear.

The waiting's still there.

The fault paths are still there, but expressed naturally. No special cases, no extra points on the map.

Time's still there but the expression changed.

We're no longer jumping between named states in a switch statement.

The execution flow itself now carries much of the state.

The enum said: COFFEE_HEATING

The protothread says:

PT_WAIT_UNTIL(pt, get_heater_temp() >= COFFEE_TEMPERATURE)

Same idea.

Different expression.

So how does this all work?

To take a peek under the hood, we’d have to start with Tom Duff. In November of 1983 while working at Lucasfilm, Tom was working to speed up a real-time animation program. Now I can’t speak for Tom, or what he was thinking, but this is certainly clear to me:

Assume a loop of this form:

do {
    *dest = *source++;
} while (--iterations);

For every operation there’s a conditional test. If for the sake of this example, the time taken to execute the test is the same as the time to perform the actual operation, the efficiency of this move is 50%.

Tom unrolled the loop and changed it to look something like this…

n = iterations / 8;
 do {
    *dest = *source++;
    *dest = *source++;
    *dest = *source++;
    *dest = *source++;
    *dest = *source++;
    *dest = *source++;
    *dest = *source++;
    *dest = *source++;
} while (--n);

Now we have 8 operations for every test. Much faster, and more efficient.

Alright Dave, you ask - “I get it. Tom made a better loop. It's faster. How does this affect our coffee maker?”

I haven’t finished. What happens when the number of iterations isn’t equally divisible by 8?

And therein lies the magic.

It’s elegant, but it’s also ugly. Going back to the grinder - MISRA, CERT-C,... unbelievably ugly.

Remember how good engineering was the art of mitigating risk? Well I’m not a puritan, and this is a risk worth taking.

Tom found that he could exploit the C loophole that allows for case labels and case label fall-throughs to be embedded inside loops. He could jump anywhere inside the loop and fall through without penalty.

So now look at this:

n = (iterations + 7) / 8;
switch (iterations % 8)
{ 
    case 0: do { *dest = *source++;
    case 7:      *dest = *source++;
    case 6:      *dest = *source++;
    case 5:      *dest = *source++;
    case 4:      *dest = *source++;
    case 3:      *dest = *source++;
    case 2:      *dest = *source++;
    case 1:      *dest = *source++;
    } while (--n);
}

Adam Dunkels told me that he “knew of this work, wanted to do something with it, and was very happy that protothreads could be implemented so nicely with it”.

How the trick becomes the thread

Since Duff showed us that a switch can fall inside a loop, it creates this strange doorway to store a continuation point - a place to return to when the condition we're waiting on finally arrives.

Logically this:

remember_this_spot();
if (!condition)
{
    return;
}
resume_here_later;

Is this:

PT_WAIT_UNTIL(pt, condition);

where pt stores the spot we return to.

On the first call, the thread reaches PT_WAIT_UNTIL, sees that the water is not hot, stores its place, and returns.

On the next call, it resumes at that same wait. Still not hot? It returns again.

When the temperature finally arrives, execution simply flows forward to the next line of the recipe.

Dr. Dunkels provided an incredible tour under the hood - https://dunkels.com/adam/pt/expansion.html. It’s a simple, yet elegant expansion of Duff’s work, and it's significantly affected the body of my own.

Setting reasonable expectations

Protothreads are stackless. There's no call stack being preserved — just a place on the state map to return to.

A consequence of that design decision, necessary but not limited to resource constrained applications, was that protothreads can only be used at the “top” level of a function. “A protothread may call normal C functions, but it cannot block inside a nested function call. The waiting points need to live within the protothread’s own resumable control flow.” - https://dunkels.com/adam/pt/about.html. Local variables also need care because they’re not preserved across blocking operations. Anything that’s assumed to be preserved should be explicitly declared static.

In applications like our coffee maker, this limitation is of little interest. Our focus was the reduced cognitive loading, reduced entropy, and the conservation of complexity. On those fronts, it’s a solid win.

Where to from here

There are as many operating systems as there are opinions about them, and so I'm not going to pretend pico is something it isn't. It is the product of my passion for embedded clockwork, combined with an evolution of needs.

I was intrigued by task control blocks that could be linked to a variety of lists, and I found it particularly useful for every thread to have access to a soft timer. In fact I gave it two. One for delays, another for general purpose timing. Timers provide a mechanism to WAIT_UNTIL with timeouts, or to delay for a specified period of time.

typedef struct pt tcb_pt_t;

typedef struct
{
    k_list_t tcb_link;
    timer_t  timer;
    timer_t  gptimer;
    uint8_t  flags;
    uint8_t  task_env;
    tcb_pt_t tcbpt;
    int      ( *p_thread )( tcb_pt_t *);
} tcb_entry_t;

The TCB forms a wrapper around protothreads - and next week we'll open it up, dig a little deeper into protothreads within the “pico” cooperative OS, and in future installments cover the areas I know I’ve fallen short, and areas I’d still love to improve.

As always, I look forward to comments and suggestions.