Snippets

Renato Cunha Arbitrary number of timers implementation using only a single physical timer

Created by Renato Cunha
View revision

File test-timers.c Added

  • Ignore whitespace
  • Hide word diff 
+/*
+ * Copyright (C) 2015 Renato L. F. Cunha
+ *
+ * A program to test the timer implementation.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "timers.h"
+
+#define TIMERS 10
+
+int main(int argc, char *argv[]) {
+    int i;
+
+    timers_init();
+
+    char storage[TIMERS] = {0};
+
+    for (i = 0; i < TIMERS; i++) {
+        if (timer_declare(TIMERS - i, &storage[i]) == NULL) {
+            printf("Failed to set timer %d :(\n", i);
+            abort();
+        }
+    }
+
+    for (;;) {
+        pause();
+        for (i = TIMERS-1; i >= 0; i--) {
+            if (storage[i]) {
+                printf("Timer %d fired\r", i);
+                fflush(NULL);
+            }
+        }
+        if (storage[0]) {
+            printf("\n");
+            break;
+        }
+    }
+}

File timers.c Added

  • Ignore whitespace
  • Hide word diff 
+/*
+ * Copyright (C) 1990 Don Libes
+ * Copyright (C) 2015 Renato L. F. Cunha
+ *
+ * An implementation of an arbitrary set of timers that use a single "real"
+ * timer (with the alarm function, in this case).
+ *
+ * This implementation most completely based on Don Libes' notes found at
+ * http://www.kohala.com/start/libes.timers.txt - The only things I changed
+ * were that I actually used a timer, and actually implemented signal
+ * blocking/unblocking.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+#include <unistd.h>
+#include <signal.h>
+
+#include <time.h>
+#include <limits.h>
+
+#include "timers.h"
+
+static sigset_t oldset;                 /* < backup storage for the old signal mask */
+static TIME time_timer_set, time_now;   /* < internal timers */
+static struct timer *timer_next = NULL; /* < the next timer that might be fired */
+
+static void sig_alarm();
+static void timers_update(TIME);
+
+/**
+ * Disables interrupts by blocking all signals with a call to sigprocmask.
+ */
+static void disable_interrupts() {
+    sigset_t set;
+    sigfillset(&set);
+    sigprocmask(SIG_BLOCK, &set, &oldset);
+}
+
+/**
+ * Re-enables interrupts by restoring the original signal mask.
+ */
+static void enable_interrupts() {
+    sigprocmask(SIG_SETMASK, &oldset, NULL);
+}
+
+/**
+ * The original document suggests the current time can be a volatile variable
+ * that's updated by some other thread, or by the OS, whatever. We don't have
+ * it here, so, every time we have to read the current time, we must call this
+ * function to update our internal clock.
+ */
+static inline void update_time_now() {
+    struct timespec tp;
+    clock_gettime(CLOCK_REALTIME, &tp);
+    time_now = tp.tv_sec;
+}
+
+/**
+ * Starts the "physical" timer by calling alarm(time).
+ */
+static void start_physical_timer(TIME time) {
+    if (signal(SIGALRM, sig_alarm) == SIG_ERR) {
+        fprintf(stderr, "Can't catch SIGALRM\n");
+        abort();
+    }
+    alarm(time);
+}
+
+/**
+ * The original timer interrupt handler. Updates the current time, updates all
+ * timers and, if there is a timer to expire in the future, re-starts the
+ * "physical" timer to the closest possible.
+ */
+static inline void timer_interrupt_handler() {
+    update_time_now();
+    timers_update(time_now - time_timer_set);
+
+    /* start physical timer for next shortest time if one exists */
+    if (timer_next) {
+        time_timer_set = time_now;
+        start_physical_timer(timer_next->time);
+    }
+}
+
+/**
+ * Just a handler to SIGALRM.
+ */
+static void sig_alarm(int signo) {
+    timer_interrupt_handler();
+}
+
+/**
+ * "Constructor". Initializes the set of timers.
+ */
+void timers_init() {
+    struct timer *t;
+
+    for (t = timers; t < &timers[MAX_TIMERS]; t++) {
+        t->inuse = false;
+    }
+}
+
+/**
+ * Updates all timers.
+ */
+static void timers_update(TIME time) {
+    static struct timer timer_last = { /* This is just a placeholder */
+        false,                         /* in use */
+        VERY_LONG_TIME,                /* time */
+        NULL                           /* event pointer */
+    };
+
+    struct timer *t;
+
+    timer_next = &timer_last;
+
+    for (t=timers; t < &timers[MAX_TIMERS]; t++) {
+        if (t->inuse) {
+            if (time < t->time) { /* haven't expired yet */
+                t->time -= time;
+                if (t->time < timer_next->time) {
+                    timer_next = t;
+                }
+            } else { /* expired */
+                /*
+                 * FIXME: Add a callback functionality to invoke
+                 * "scheduler"
+                 */
+                *t->event = true;
+                t->inuse = 0; /* remove timer, since it is done */
+            }
+        }
+    }
+
+    if (!timer_next->inuse) {
+        timer_next = 0;
+    }
+}
+
+/**
+ * Declares a new timer.
+ *      time  -> In this many seconds the timer must go off
+ *      event -> Will be set to true when this timer does expire
+ *
+ * Returns a pointer to the newly created timer.
+ */
+struct timer *timer_declare(unsigned int time, char *event) {
+    struct timer *t;
+
+    disable_interrupts();
+
+
+    for (t=timers; t < &timers[MAX_TIMERS]; t++) {
+        if (!t->inuse) {
+            break;
+        }
+    }
+
+    /* out of timers? */
+    if (t == &timers[MAX_TIMERS]) {
+        enable_interrupts();
+        return NULL;
+    }
+
+    /* install new timer */
+    t->event = event;
+    t->time = time;
+    update_time_now();
+    if (!timer_next) {
+        /* no timers, this is the shortest */
+        time_timer_set = time_now;
+        start_physical_timer((timer_next = t)->time);
+    } else if ((time + time_now) < (timer_next->time + time_timer_set)) {
+        /* new timer is shorter than current one, so update it */
+        timers_update(time_now - time_timer_set);
+        time_timer_set = time_now;
+        start_physical_timer((timer_next = t)->time);
+    } else {
+        /* nothing to do */
+    }
+
+    t->inuse = true;
+    enable_interrupts();
+    return t;
+}
+
+/**
+ * Deallocates a timer returned by timer_declare.
+ */
+void timer_undeclare(struct timer *t) {
+    disable_interrupts();
+
+    if (!t->inuse) {
+        enable_interrupts();
+        return;
+    }
+
+    t->inuse = false;
+
+    /* check if we were waiting on this one */
+    if (t == timer_next) {
+        update_time_now();
+        timers_update(time_now - time_timer_set);
+        if (timer_next) {
+            start_physical_timer(timer_next->time);
+            time_timer_set = time_now;
+        }
+    }
+    enable_interrupts();
+}

File timers.h Added

  • Ignore whitespace
  • Hide word diff 
+/*
+ * Copyright (C) 1990 Don Libes
+ * Copyright (C) 2015 Renato L. F. Cunha
+ *
+ * An implementation of an arbitrary set of timers that use a single "real"
+ * timer (with the alarm function, in this case).
+ *
+ * This implementation most completely based on Don Libes' notes found at
+ * http://www.kohala.com/start/libes.timers.txt - The only things I changed
+ * were that I actually used a timer, and actually implemented signal
+ * blocking/unblocking.
+ */
+
+#ifndef _TIMERS_H_
+#define _TIMERS_H_
+
+#include <stdbool.h>
+
+#define MAX_TIMERS      64
+#define VERY_LONG_TIME  INT_MAX
+
+typedef unsigned TIME;
+
+struct timer {
+    bool inuse;
+    TIME time;
+    char *event;
+} timers[MAX_TIMERS];
+
+void timers_init();
+void timer_undeclare(struct timer *);
+struct timer *timer_declare(unsigned int, char *);
+
+#endif
HTTPS SSH

You can clone a snippet to your computer for local editing. Learn more.