Sat
Sep 26

Writing asynchronous device drivers with synchronous code

This post is about device drivers and owes a lot to papers written by Leonid Ryzhyk.

Most devices are asynchronous. You tell the device to do something, then some time later it lets you know that it's finished. The typical programming model for asynchronous devices uses callbacks, something like this:

read_bytes():
    write_to_device_register(READ_DATA)

device_irq_handler():
    if(read_from_device_register(STATUS) & DATA_READY)
        ...

The problem with this model is that it's kind of hard to read. It's particularly annoying if you are doing something which involves lots of interaction with the device, such as initialisation:

void init(int state)
{
    register_callback(init, state);
    static int counter;

    try_again:
    switch(state) {
        case 1:
            write_to_device_register(SETUP1, ...);
            break;
        case 2:
            if(there was an error) {
                counter += 1;
                if (counter < 10) {
                    goto try_again;
                } else {
                    die();
                }
            }
            write_to_device_register(SETUP2, ...);
            break;
        case 4:
            handle possible errors;
        default:
            panic();
    }
}

void device_irq_handler(void)
{
    if(callback registered) {
        callback();
    }
}

It would be much easier to read the code if the device behaved synchronously. Then you could just write this:

void init(void) 
{
    int counter;

    for(counter = 0; counter < 10; counter++) {
        write_to_device_register(SETUP1, ...);
        if(no error encountered);
            break;
    }

    if(error_encountered) {
        die();
    }

    write_to_device_register(SETUP2, ...);
    handle possible errors;
}

So how do you make an asynchronous device behave synchronously? There are lots of ways. The most obvious way is simply to poll the device. This may even be feasible for some devices in some situations (for example, when initialising the device), but, in general it's not a feasible option, because the cycles consumed by polling the device could be better spent doing something (anything!) else.

The second way is to use threads. Under this approach, write_to_device_register() would go to sleep on some synchronisation primitive. The IRQ handler would wake up any thread sleeping on the synch primitive. This approach is pretty much what the Linux kernel does.

Threads have their problems: they really require a lot of thinking to make sure you get both correctness and performance out of the device driver you're writing. For example, Linux allows multiple threads to execute device driver code simultaneously. Multi-threaded drivers are signficant source of device driver bugs.

But I wasn't at the stage of writing concurrency bugs. I just didn't want to manage more than one thread. So instead I abused the pre-processor to create the illusion of synchronous device operation while secretly using callbacks.

Here's how that device init function looks using this approach:

EC_FUNCTION(init)
    static int counter;

    EC_START
    for(counter = 0; counter < 10; counter++) {
        EC_WRITE(SETUP1, ...);
        if(no_error)
            break;
    }

    if(error) {
        die();
    }

    EC_WRITE(SETUP2, ...);
    handle_possible_errors();
    EC_END
EC_FUNCTION_END

This has the same block structure as the threading version, and is pretty easy to read (once you get over the yucky pre-processor macros). But what is that tell-tale "static" doing in front of "int counter"?

That's right, this is just syntactic sugar over a callback-based model. After preprocessing, it looks something like this:

void init(struct device_info *info)
{
    static int counter;

    static void *__label = &&label0;
    goto *__label;

label0:
    for(counter = 0; counter < 10; counter++) {
        __label = &&label1;
        device_write(SETUP1, ..., init, info);
        goto end;
label1:
        if(no_error)
            break;
    }

    if(error) {
        die();
    }

    __label = &&label2;
    device_write(SETUP2, ..., init, info);
    goto end;
label2:
    handle_possible_errors();
    __label = &&label0;
end:
    ;
}

Hideous, huh? The good thing is, you only need to get this sort of thing right once, and then you don't need to see it again.

This approach has some really good points: firstly, you get complete control over where you could be pre-empted in a very intuitive way: when you interact with the device. Any internal state manipulation has no chance of being corrupted. It's not perfect, though: as you can see, you can't use local variables. If you do want to make use of local variables, you need to add some code to save and restore the stack -- essentially continuations.

You can download my preprocessor macros here: event_chain.h.

If you find this sort of thing interesting you should look at Leonid Ryzhyk's publications, particularly "Dingo: taming device drivers".

EDIT: This page gives another summary of the same technique (thanks to Benno for the link)