Protothread implementation in Contiki OS -- why the state variable is not static?

Question

I'm reading the source code of a protothread implementation in Contiki OS, which is developed by Adam Dunkels from SICS, Sweden. And I'm really confused by one slightly difference between its implementation and the co-routines idea demonstrated by Simon Tatham -- that is, why the state variable has not to be static in Adam's protothread implementation while declared static in Simon's paper?

Let's first take a close look at Simon's discussion. For example, it would nice to be able to write a function that says

int function(void) {
   int i;
   for(i=0; i<10; i++)
       return i; //actually won't work in C
}

and have ten successive calls to the function return the numbers 0 through 9.

This could be achieved by using following macros in this function:

#define crBegin static int state=0; switch(state) { case 0:
#define crReturn(i,x) do { state=__LINE__; return x; \
case __LINE__:; } while (0)
#define crFinish }
int function(void) {
    static int i;
    crBegin;
    for (i = 0; i < 10; i++)
        crReturn(1, i);
    crFinish;
}

Calling this function ten times will give 0 through 9, as expected.

Unfortunately, this won't work if we use Adam's local continuation macros wrapped-up switch-case like this(/core/sys/lc-switch.h in Contiki src tree), even if you make the state variable s static:

typedef unsigned short lc_t;
#define LC_INIT(s) s = 0; // the ";" must be a mistake...
#define LC_RESUME(s) switch(s) { case 0:
#define LC_SET(s) s = __LINE__; case __LINE__:
#define LC_END(s) }
int function(void) {
    static int i;
    lc_t s;
    LC_INIT(s);
    LC_RESUME(s);
    for (i = 0; i < 10; i++)
    {    return i;
         LC_SET(s);
    }
    LC_END(s);
}

Here, like Simon's example, s works as a state variable which preserves the position (yield point) set by LC_SET(s). And when the function later resumes execution (from beginning), it will switch according to the value of s. This behavior gives the effect that the function continues running after the yield position set by previous invocation.

The differences between these two sets of macros are:

1. the state variable s is static in Simon's example but non-static in Adam's LC definition;
2. the crReturn sets the state right before it returns the result, while in Adam's LC definition, LC_SET(s) purely sets the the state and marks the yield point.

Of course the latter won't work with this for loop case in the function. The key to this "return and continue" behavior resides in both the state variable being static and the state being set right before return statement. Apparently the LC macros meet neither requirements. So why the LC macros are designed in this way?

All I can speculate right now is that these LC macros are only very low level primitives and should not be used in the way shown in this for loop example. We need to further build those PT macros wrapped-up these LC primitives to make them really useful. And the crReturn macro is only for demonstration purpose to specifically fit the for loop case, since not every time you want to yield your execution by return from a function.

Answer 1

As you correctly guessed, all function-local variables that should have their values saved between coroute returns should be static, and in addition, the variable of of type lc_t that describes the current state of the couroutine also should be static. To fix your example, add static in front of declaration of s.

Another thing is that you want to return a value. Contiki protothreads have no support for returning arbitrary values; they just a code that describes whether the thread is in still active or has already finished (PT_WAITING, PT_YIELDED, PT_EXITED and PT_ENDED states).

However, you can easily make this work by using the LC_xxx macros; you'll need one more flag (the idea is the same as in PT_YIELD()):

int function(void) {
    static int i;
    static lc_t s;
    int flag = 0; // not static!
    LC_INIT(s);
    LC_RESUME(s);
    for (i = 0; i < 10; i++) {
        flag = 1;
        LC_SET(s);
        if (flag) { /* don't return if came to this point straight from the invocation of the coroutine `function` */
          return i;
        }
    }
    LC_END(s);
}

The Contiki protothread library uses these LC_xxx macros to implement PT_xxx macros, which in turn are used to create support for application-levels processed (the PROCESS_xxx macros).

The lc_t state variable is in fact the same as the state of a protothread: in https://github.com/contiki-os/contiki/blob/master/core/sys/pt.h, the pt structure is defined simply as:

struct pt {
  lc_t lc;
};

The pt structure is in turn included as a member in process structure (see https://github.com/contiki-os/contiki/blob/master/core/sys/process.h). And process structures in Contiki are global variables, therefore the protothread state is stored across different invocations of the protothread coroutine.

The fact that most of the couroutine-local variables also need to be static is usually described (in research papers) as the one of the main limitation of this programming model, but in practice it's not a big deal.

Answer 2

The state variable does need to be in statically allocated memory, which includes globals as in the Dunkels example you linked to. If it is an automatic variable (on the stack, not static), its value will be lost from one invocation of the function to the next, except for in the most trivial of programs.

When using the lc-switch implementation, you can modify Tatham's crReturn() to be a LC_SET_AND_RETURN() macro that adds the ability to return, as shown below, for functions that need to return a value, and just call LC_SET(s); return; for void functions.

#include "lc.h"
#define LC_SET_AND_RETURN(lc, retval) do { lc = __LINE__ ; return retval; case __LINE__: } while (0)

int function(void) {
    static int i;
    static lc_t s;
    LC_RESUME(s);
    for (i = 0; i < 10; i++) {
        LC_SET_AND_RETURN(s, i);
    }
    return -1; // done
    LC_END(s);
}

LC_INIT() looks like it is meant to be called like LC_INIT(static lc_t s);. The code

static lc_t s;
LC_INIT(s);

expands to

static lc_t s;
s = 0;;

which is not equivalent to static lc_t s = 0;, and causes the code to behave in an unintended way.

You could use static lc_t LC_INIT(s); to expand to static lc_t s = 0;; but that looks funny.