A Study in (Linux) Timers

I watched ThePrimeagen do a LeetCode problem where he was asked to implement debounce. I realised that I have no idea on how to do this in C. Therefore I set out to figure it out and this is what I came up with.

The Problem

2627. Debounce

Given a function `fn` and a time in milliseconds `t`, return a **debounced**
version of that function.

A **debounced** function is a function whose execution is delayed by `t`
milliseconds and whose execution is cancelled if it is called again within
that window of time. The debounced function should also receive the passed
parameters.

For example, lets say `t = 50ms`, and the function was called at `30ms`,
`60ms`, and `100ms`.

The first 2 function calls would be cancelled, and the 3rd function call
would be executed at 150ms.

If instead `t = 35ms`. The 1st function call would be cancelled, the 2nd
would be executed at `95ms`, and the 3rd would be executed at `135ms`.

From LeetCode: https://leetcode.com/problems/debounce/description/

via ThePrimeagen: https://youtu.be/nO7J6pBEkJw?t=4793

Attempt One: debounce_itimer.h

The first thing I investigated was getitimer(2) and setitimer(2) which sets an interval timer. When the timer expires a signal is raised and the debounced function can be executed from the signal handler. I managed to get it to work in debounce_itimer.c but it has several limitations.

  1. There is only one interval timer which means that only one function can be debounced at a time.

  2. My solution relies on a lot of global data and boilerplate that is necessary for each function that you want to debounce. This global data reinforces the problem with 1: only one function can be debounced at a time.

  3. Higher order functions in C is a mess. The ideal interface that I wanted is the one suggested in LeetCode code skeleton: a function dx = debounce(x) where x is a function and dx is a debounced version of x, but this is hard to accomplish in C.

An example usage of debounce_itimer is

    void (*dadd)(int, int) = debounce_add(50);

    millisleep(30);
    (*dadd)(1, 2);
    millisleep(30);
    (*dadd)(1, 3);
    millisleep(40);
    (*dadd)(1, 4);

This is the only solution where I managed to have a function return a callable function, but as you will notice it is not called debounce. debounce_add is a manually created boilerplate function that must be created for every function that you want to debounce.

You could argue that C is not meant to have inner functions or overloaded functions and that wrestling with it is counterproductive and whatever solution you end up with is not pythonic (but for C).

Here is the boilerplate required.

    int global_a = 0;
    int global_b = 0;
    int global_add_t = 0;

    // This function is run when the timer expires
    void add_alarm_handler(int signum) {
        add(global_a, global_b);
    }

    // This is the function that gets executed when the user calls the
    // debounced add. It sets global data, sighandler, and (re)starts the
    // timer.
    void debouncer_add(int a, int b) {
        global_a = a;
        global_b = b;
        set_signalhandler_and_clock(global_add_t, add_alarm_handler);
    }

    void (*debounce_add(int t))(int, int) {
        global_add_t = t;
        return debouncer_add;
    }

Attempt Two: timeout.h

After a careful reading of setitimer(2) it notes that setitimer has been obsoleted in favour of timer_settime(2) and related functions.

When ThePrimeagen solved this problem he did it using setTimeout in Javascript. Therefore, instead of going directly to implement debounce, I set out to first implement setTimeout using timer_settime(2).

Here is how to use it.

    timer_t id;
    struct AddArgs args;
    args.a = 1;
    args.b = 2;
    id = setTimeout(timeout_add, 50, &args);

This interface requires a struct AddArgs that stores the parameters for the timeouted function. It also requires a function timeout_add which is executed after the timer has expired and unpacks the struct and calls the function add.

    struct AddArgs {
        int a;
        int b;
    };

    void timeout_add(void *p) {
        struct AddArgs *a = (struct AddArgs*) p;
        add(a->a, a->b);
    }

Different this time is that when the timer expires it is possible to have the timer start a new thread and execute the timeouted function in parallel instead of concurrently. Or it is possible to continue using signals. Threads is probably the superior option.

The following code creates the timer with either a thread handler or a signal handler.

    /**
     * Sets up a timer according to `USE_THREAD`.
     */
    int setup_timer(
            void *data,
            void (*thread_handler)(union sigval),
            void (*signal_handler)(int, siginfo_t*, void*),
            timer_t *timerid) {

        struct sigevent sev = {};
        sev.sigev_value.sival_ptr = data;  // The data to be passed

    #if USE_THREADS
        assert(thread_handler);
        sev.sigev_notify = SIGEV_THREAD;
        sev.sigev_notify_function = thread_handler;
    #else
        assert(signal_handler);
        // Establish signal handler for timer signal
        struct sigaction sa;
        sa.sa_flags = SA_SIGINFO;
        sa.sa_sigaction = signal_handler;
        sigemptyset(&sa.sa_mask);
        if (sigaction(SIGTIMER, &sa, NULL) == -1) {
            perror("sigaction");
            return -1;
        }

        sev.sigev_notify = SIGEV_SIGNAL;
        sev.sigev_signo = SIGTIMER;
    #endif

        // Create the timer
        if (timer_create(CLOCKID, &sev, timerid) == -1) {
            perror("timer_create");
            return -1;
        }
        return 0;
    }

Attempt Three: debounce.h

I was now ready to implement debounce using timeout.h, but as I started doing this I realised that I did not want to use it. The code I had written to implement timeout.h was easily reused though to set up a timer and handlers.

    struct Debounce dadd = {};
    dadd.ms = ts[i];
    dadd.fn = add_h;
    debounce(&dadd);
    struct AddArgs aa = { .a = 0, .b = 0 };
    struct AddArgs bb = { .a = 1, .b = 1 };
    struct AddArgs cc = { .a = 2, .b = 2 };

    millisleep(30);
    debounce_call(&dadd, &aa);
    millisleep(30);
    debounce_call(&dadd, &bb);
    millisleep(40);
    debounce_call(&dadd, &cc);

This solution requires the user to fill in a struct Debounce with the function that is to be executed when the timer expires and the time until expiration. The function expects to be of the format void (*)(void*) and a struct per debounced is still necessary for the parameters.

    struct AddArgs {
        int a;
        int b;
    };

    void add_h(void *p) {
        struct AddArgs *a = (struct AddArgs*) p;
        add(a->a, a->b);
    }

Different this time is mutexes. The Debounce struct contains a mutex since it would be bad if the timer expires and the main thread changes the parameters while the debounced function is executing.

Attempt Four: debounce2.h

This time I wanted to do the crazy macro. I don't know how to feel about these macros. They make the interface better for the caller but is it worth the cost. In this case I think it might. The macros that I made are quite readable.

    debounce(dadd, add, 50);

    millisleep(30);
    debounce_add(&dadd, 0, 0);
    millisleep(30);
    debounce_add(&dadd, 1, 1);
    millisleep(40);
    debounce_add(&dadd, 2, 2);

The boilerplate necessary for this is

    DEBOUNCEABLE2(add, int, int);

Where DEBOUNCABLE2 is a big macro that defines 3 things:

  1. the struct add_args.
  2. the handler function add_h.
  3. and the debounce function debounce_add.

The 2 in DEBOUNCABLE2 refers to the number of parameters the function takes. This means that a new macro has to be made for every function that requires a new number of parameters. This is not as bad as it might seem. The macros copy paste pretty easily and there is only a few lines that need editing. But it would be nice if C supported better macros, with say recursion or nested definitions.

debounce is also a macro and it looks like this:

    #define debounce(Debounced, Function, Milliseconds)                         \
        struct Function ## _args Debounced ## _args = {};                       \
        struct Debounce Debounced = {};                                         \
        Debounced.ms = Milliseconds;                                            \
        Debounced.fn = Function ## _h;                                          \
        Debounced.args = & Debounced ## _args;                                  \
        debounce(&Debounced);

It declares and fills in automatically the struct Debounce from debounce.h. It also creates a struct add_args where the parameters are stored.

Unfortunately I don't think it is possible to get the Javascript syntax of dx = debounce(fn, t) because you would need to return a function from debounce which depends on the given function fn. Perhaps if debounce returned a variadic function but that might be problematic if the user then accidentally calls it with the wrong number of parameters.

Testing

When print and add are executed they write an output string into a simple buffer which contains the time since the testcase began. This made it easy to then afterwards just parse the lines of this buffer and extract the timing to check if it was correct. This was also protected by a mutex.

    // Print also writes the string into `buffer` and advances `bindex`.
    // This is so that the test-functions can easily assert on the timing
    // and argument `s`.
    int length = snprintf(
        &buffer[bindex], BUFFER_SIZE-bindex,
        "[%lf ms] Hello '%s'\n", ms, s
    );
    bindex += length;

The assert reads this buffer with sscanf(3).

    matches = sscanf(
        &buffer[index], "[%f ms] Hello '%60[^]']'\n%n",
        &ms, string, &bytes
    );

What has not been easy to test is the mutexes and other race conditions.

Conclusion