Unix Select+Timers

Introduction

When developing real-time network protocols and other embedded time sensitive systems, it is common having to read from one or more file-descriptors while keeping track of various timeouts at the same time.

This post discusses a method to implements timers and  file-descriptors polling in a single loop. It's very limited in the resource usage and relatively fast for a small number of timers and file descriptors. This conditions are usually met in embedded systems, where either is not allowed or expected for a device to serve too many clients.

The solution is fairly portable among UNIX like OSs as it uses POSIX calls. I wont claim that this is the best method to do it, but I have to say it's being successfully used in some time sensitive protocol implementations.

Timers

To implement the timers we have to keep track of the time, this is performed by a clock. The clock is a monotonic counter obtained through the clock_gettime(CLOCK_MONOTONIC) system call. And, usually,  it represents an absolute time since the system start up. The reference or epoch of the clock doesn't really matter, the important thing is that it can' t be subjected to corrections like NTP.

The timers are represented in the same way the clock is. Active timers (not expired) have their times set in the future. The timers with a time in the past are expired and are consider inactive. We compare the clock value with the timers values to determine when a timer expire and an appropriate action can be taken. One approach is to associate callback functions with the timers.

To improve the performance on 32bits systems, for the clock and timers we use only the first 32bits of the value, this way the time will wraps each 4294 seconds or 71 minutes. That means that to unequivocally determine if a timer timeout is in the future it should be at most at 1/2 of the wrapping value or about 35.5 minutes. This is more than enough for most of real-time applications. If this is not your case consider using a milliseconds clock reference (see bellow).

To setup a timer timeout it's just a matter of adding the timeout time in microseconds to the clock. In the example bellow we use a value of 0 to represent an inactive timer. So if the value of the clock plus the timeout time wraps to 0 we add 1 microsecond to avoid this condition. Other more elaborated methods can be used but this have the advantage of avoiding an extra memory reference when polling the timers.  

Polling

The idea is to use the select() system call to poll for the files-descriptors adjusting the timeout parameter according to the expiration time of the timers. We compare all the timers with the current clock and selects the smallest difference, higher than zero, between the expiration time an current time.

The select() system call has the advantage of being fast and conservative regarding resources usage, for a small number of file descriptors. The call by itself will not depend much of the number of the file-descriptors as it depends on the value of the last file-descriptor in the set. Another advantage of select() is portability.

#include <stlib.h>
#include <stdint.h>
#include <time.h>

#define ONE_SECOND 1000000
#define TMR_MAX 8
#define FD_MAX 8

/* get the system monotonic clock value in microseconds. */
static uint32_t get_clock_us(void)
{
    struct timespec tv;
    clock_gettime(CLOCK_MONOTONIC, &tv);
    return (tv.tv_sec * 1000000) + (tv.tv_nsec / 1000);
}

/* the maximum timer timeout allowed is 
   2147 seconds ~ 35 minutes */

uint32_t tmr[TMR_MAX]; /* List of timers */
unsigned int tmr_cnt; /* Number of timers in the list */

int fd[FD_MAX]; /* List of file descriptors */
unsigned int fd_cnt; /* Number of descriptors in the list */

static void * my_task(void * arg)
{
    struct timeval tv;
    uint32_t clock;
    int fd_max;
    fd_set rs;
    int ret;
    int i;


    for (;;) {
        /* get the current time in mircosseconds */
        clock = get_clock_us();

        /* clear the fd set */
        FD_ZERO(&rs);
        /* initialize dt_min to 1 minute */
        dt_min = 60 * ONE_SECOND;
        /* initialize fd_max */
        fd_max = 0;

        for (i = 0; i < tmr_cnt; i++) {
            int32_t dt;
            if (tmr[i] == 0) /* timer is inactive */
                continue;
            if ((dt = (int32_t)(tmr[i] - clock)) <= 0) {
                /* timer timeout */
                on_timeout(i);
            } else if (dt < dt_min) {
                /* adjust the minimum timeout time */
                dt_min = dt;
            }
        }

        tv.tv_usec = dt_min;
        tv.tv_sec = 0;

        for (i = 0; i < fd_cnt; i++) {
            if (fd[i] != -1) {
                FD_SET(fd[i], &rs);
                if (fd[i] > fd_max)
                    fd_max = fd[i];
            }
        }


        ret = select(fd_max + 1, &rs, NULL, NULL, &tv);

        if (ret < 0) {
            if (errno == EINTR) /* select() interrupted */
                continue;
            /* select() failed */
            return ret;
        }

        for (i = 0; i < fd_cnt; i++) {
            if ((fd[i] != -1) && FD_ISSET(fd[i], &rs)) {
                /* read from the file descriptor */
                on_recv(fd[i]);
            }
        }
    }
}

void timer_set(unsigned int id, unsigned int tmo_us)
{
    tmr[id] = clock + tmo_us;
    if (tmr[id] == 0)
        tmr[id]++;
}

I've tried to keep the example as short as possible, so the structure is far from ideal in terms of encapsulation. If the list of timers or file descriptors is changes dynamically, a mutual exclusion mechanism should be implemented as well. This is to avoid race conditions when evaluating the timers or the file descriptors.

Minor improvements

It may be a good idea to avoid arithmetic divisions in platforms that don't have an equivalent div instruction, like ARM v4  and v5 (ARM7-9). This will improve the performance a little bit. The following code is an alternative to the original one that uses sums of shifts to get an approximation of the 'by 1000' division, when calculating the number of microseconds.

static inline uint32_t get_sys_clock_us(void)
{
   struct timespec ts;

   clock_gettime(CLOCK_MONOTONIC, &ts);
   /* This is a fast, no division, good approximation to: 
      tv_nsec / 1000. The maximum error is 74 microseconds
      It costs only 5 structions on ARMv5 */
   return (ts.tv_sec * 1000000) + (ts.tv_nsec >> 10) +  
   (ts.tv_nsec >> 15) - (ts.tv_nsec >> 17) + (ts.tv_nsec >> 21);
}

If timers with more than 35 minutes are needed the clock function can be modified to count in milliseconds instead of microseconds. Follows the non-division implementation of the clock function, and the conversion to microseconds to set-up the timeval struct:

static uint32_t get_clock_ms(void)
{

   struct timespec ts;

clock_gettime(CLOCK_MONOTONIC, &ts);
    /* This is a fast, no division, good approximation to: tv_nsec / 1000000. */
    return (ts.tv_sec * 1000) + (ts.tv_nsec >> 20) + 
        (ts.tv_nsec >> 25) - (ts.tv_nsec >> 26) + 
        (ts.tv_nsec >> 28) + (ts.tv_nsec >> 29);
}

... 

tv.tv_usec = dt_min * 1000;