MicroThreads

Version 1.0
Jon Mayo <jon.mayo@gmail.com>

January 29, 2007 :Author: Jon Mayo


Introduction

MicroThreads is a simple C hack to allow for the continuation of a function at an arbitrary point of its execution. The application of this construct is similar to cooperative threading, and in reality it is a toolkit for creating complex state machines without explicitly defining every state.

MicroThreads is inspired by Protothreads by Adam Dunkels.


Usage

Typical usage is to think of a state machine as if it were a thread. It can be useful for processing multiple flows of data. User input as string data, or streams of packets to represent a protocol.

Implementations using this library or similar libraries include a config file parser, a telnet command line interface, and a TCP/IP stack for microcontrollers.


Caveats

Local variables are not saved or re-initialized on reentry. All client state much be passed through the function directly or indirectly. Generally it is simplest to create a structure holding the state variables and any values that need to cross over reentrancy.

Usage of UT_RESTART() in buffer producer-consumer implementations must allow successful handling of returning UT_STATUS_WAITING even though the buffer was not consumed. Implementations that do not need UT_RESTART() could treat this state as an error and exit, to avoid tight loops.

Subroutines called with in the microthread routine cannot make use of the UT_ macros. The subroutines must be completely independent and run "one shot". Although it is permissible to add another state variable and have a subroutine called as a microthread within a microthread. This can be useful if the system is modular and the microthreads are very independent. It can result in complex code and complex bug if they are interdependent.


API Reference

struct ut_state;

structure used to track the current state of a reentrant microthread.

UT_STATUS_WAITING

non-zero value, used to indicated that the state machine is not finished and is waiting for more data.

UT_STATUS_EXITED

zero value. used to indicated that the state machine has completed processing.

UT_BEGIN(struct ut_state *)

begin the reentrant section of code. anything above this line is executed every entry.

UT_END(struct ut_state *)

end the reentrant section of code. this returns from the function with a UT_STATUS_EXITED.

UT_INITIALIZE(struct ut_state *)

initializes or reinitializes the state variable to start at the beginning of the reentrant function.

UT_INITIALIZER

alternative macro used in initializer declarations.

UT_SET(struct ut_state *)

marks the current position as an entry point. the next call will enter here unless changed by a later macro.

UT_WAIT_WHILE(struct ut_state *, expression)

wrapper for UT_SET that causes the function to return UT_STATUS_WAITING if the conditional expression is non-zero (false)

UT_WAIT_UNTIL(struct ut_state *, expression)

wrapper for UT_SET that causes the function to return UT_STATUS_WAITING if the conditional expression is zero (true). Opposite of UT_WAIT_WHILE.

UT_RESTART(struct ut_state *)

reinitialize the state variable and cause the function to return UT_STATUS_WAITING.

UT_EXIT(struct ut_state *)

reinitialize the state variable and cause the function to return UT_STATUS_EXIT. This can be called if a code path needs to terminate the protothread instance without transversing to UT_END().

UT_LINE(uts)

evaluates to the line number of the last UT_SET() macro call. This is purely a debugging aid.


Example

Basic Example:

/* ut-demo1.c - basic example of using MicroThreads */
/* Jon Mayo - PUBLIC DOMAIN - August 23, 2005 */
#include <stdio.h>
#include "ut.h"

/* this thread keeps going until count is 5 */
unsigned example_th(struct ut_state *uts, int count) {
        printf("%s():enter. count=%d\n", __func__, count);
        UT_BEGIN(uts);
        printf("%s():This only done the first time. count=%d\n", __func__, count);
        UT_WAIT_WHILE(uts, count < 5);
        printf("%s():complete. count=%d\n", __func__, count);
        UT_END(uts);
}
int main(int argc, char **argv) {
        struct ut_state ex = UT_INITIALIZER;

        int count = 1;

        /* keep calling the thread's reentry until it returns non-zero */
        while(example_th(&ex, count)) {
                printf("%s():Looping...\n", __func__);
                count++;
        }

        return 0;
}

Very Complex Example:

/* ut-demo2.c - complex example of using MicroThreads */
/* Jon Mayo - PUBLIC DOMAIN - January 29, 2007 */

#define NDEBUG

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include "ut.h"

#define NR(x) (sizeof(x)/sizeof*(x))    /* number of elements in an array */

struct client_state {
        struct ut_state uts;
        unsigned cmdid;
        char tinybuf[16]; /* very small buffer! */
        unsigned len;
        int keep_going; /* flag if command input should continue */
};

/* returns -1 if there is not a complete word in the buffer */
static int has_word(const char *buf, unsigned len) {
        unsigned i;
        for(i=0;i<len;i++, buf++) {
                if(isspace(*buf)) {
                        return i;
                }
        }
        return -1;
}

/* returns -1 if there is not a line in the buffer */
static int has_line(const char *buf, unsigned len) {
        unsigned i;
        for(i=0;i<len;i++, buf++) {
                if(*buf=='\n') {
                        return i;
                }
        }
        return -1;
}

/* takes an array of strings and finds a matching entry */
static int word_to_int(const char *word, unsigned wordlen, const char * const *wordlist, unsigned nr_wordlist) {
        unsigned i;
        for(i=0;i<nr_wordlist;i++) {
                if(strncmp(word,wordlist[i],wordlen)==0
                   && strlen(wordlist[i])==wordlen) {
                        return i;
                }
        }
        return -1;
}

/* runs a command */
static void command_run(struct client_state *cl, int cmdid, const char *args) {
        switch(cmdid) {
                case 0:
                        printf("enable: not yet implemented\n");
                        break;
                case 1:
                        printf("disable: not yet implemented\n");
                        break;
                case 2:
                        printf("show: not yet implemented\n");
                        break;
                case 3:
                        printf("service: not yet implemented\n");
                        break;
                case 4:
                        printf("access-list: not yet implemented\n");
                        break;
                case 5:
                        printf("ping: not yet implemented\n");
                        break;
                case 6:
                        printf("diag: not yet implemented\n");
                        break;
                case 7:
                        printf("configure: not yet implemented\n");
                        break;
                case 8:
                        printf("reset: not yet implemented\n");
                        break;
                case 9:
                        printf( "Help\n"
                                "====\n"
                                "quit\n"
                                "reset\n"
                                "configure\n"
                                "diag\n"
                                "ping\n"
                                "access-list\n"
                                "service\n"
                                "show\n"
                                "disable\n"
                                "enable\n");
                        break;
                case 10:
                case 11:
                        cl->keep_going=0;
                        break;
                default:
                        printf("Unknown command %d\n", cmdid);
        }
}

/* buf - provide length terminated string data.
 * len - pointer to length of string, modified to indicate consumption
 */
static int parser_th(struct client_state *cl, char *buf, unsigned *len) {
        static const char * const command_str[] = {
                "enable",
                "disable",
                "show",
                "service",
                "access-list",
                "ping",
                "diag",
                "configure",
                "reset",
                "help",
                "quit",
                "exit"
        };
        int tmplen;

#ifndef NDEBUG
        printf("%s():enter. len=%d\n", __func__, *len);
#endif
        UT_BEGIN(&cl->uts);

        /* command word */
        UT_WAIT_UNTIL(&cl->uts, (tmplen=has_word(buf, *len)) != -1);

        printf("COMMAND: '%.*s'\n", tmplen, buf);

        /* save the command as a number so we can empty the buffer */
        cl->cmdid=word_to_int(buf, tmplen, command_str, NR(command_str));

        /* eat trailing whitespaces if there are any left in this buffer, does
         * not eat any of the whitespaces that might be send in the next buffer
         */
        while(tmplen<*len && buf[tmplen]==' ' && buf[tmplen]=='\t') tmplen++;

        /* shift consumed buffer */
        *len-=tmplen;
        memmove(buf, buf+tmplen, *len);

        /* arguments of command */
        /* TODO: figure out how to consume leading whitespaces */
        /* TODO: handle each argument as a word to minimize buffer space, it
         * would make this function massively more complex but allow for very
         * long commands to be entered and make for easier command completion
         * in the future. */
         UT_WAIT_UNTIL(&cl->uts, (tmplen=has_line(buf, *len)) != -1);

        printf("ARGS: '%.*s'\n", tmplen, buf);

        buf[tmplen++]=0; /* null terminate buffer (write over \n) */
        command_run(cl, cl->cmdid, buf);

        /* shift consumed buffer */
        *len-=tmplen;
        memmove(buf, buf+tmplen, *len);

#ifndef NDEBUG
        printf("%s():complete. len=%d\n", __func__, *len);
#endif

        UT_END(&cl->uts);
}

static void client_init(struct client_state *cl) {
        assert(cl != NULL);
        UT_INITIALIZE(&cl->uts);
        cl->cmdid=-1;
        cl->len=0;
        cl->keep_going=1;
        memset(cl->tinybuf, 0, sizeof cl->tinybuf);
}

static int get_command(struct client_state *cl) {
        assert(cl != NULL);
        /* keep calling the thread's reentry until it returns non-zero */
        while(cl->keep_going && (printf("> "),fgets(cl->tinybuf+cl->len, sizeof cl->tinybuf-cl->len, stdin))) {
                /* fill the buffer with data */
                cl->len+=strlen(cl->tinybuf+cl->len);

                if(parser_th(cl, cl->tinybuf, &cl->len)==UT_STATUS_EXITED)  {
                        /* completed command */
                        printf("\n");
                }

                if(cl->len >= sizeof cl->tinybuf-1) { /* nothing was consumed */
                        fprintf(stderr, "error:Buffer Overflow?\n");
                        return 0;
                }

#ifndef NDEBUG
                printf("%s():Looping...\n", __func__);
#endif
        }
        return 1;
}

int main(int argc, char **argv) {
        struct client_state ex;

        client_init(&ex);
        printf("Welcome. type 'help' for help.\n");
        if(!get_command(&ex)) {
                printf("\nThere was a fatal error.\n");
                return EXIT_FAILURE;
        }
        return 0;
}


Last updated 29-Jan-2007 15:58:41 PDT