Simple work scheduler and test harness for microcontroller projects in C.

scheduler.c

#include "scheduler.h"
#include <stddef.h>
#include <stdbool.h>

//
// Compatibility macros
//

// Missing from Arduino toolchain
#ifndef UINT16_MAX
#define UINT16_MAX 0xFFFF
#endif

// Missing from Arduino toolchain
#ifndef UINT32_MAX
#define UINT32_MAX 0xFFFFFFFF
#endif

// Just in case
#ifndef __has_builtin
  #define __has_builtin(x) 0
#endif

//
// Globals
//

// Root of the scheduler's linked list of work units.
static struct scheduler_work the_scheduler_head;
// Optimization to prevent a full scheduler search in scheduler_run when a work
// unit removes itself.
static struct scheduler_work *the_current_unit;

//
// Internal API
//

// Overflow-aware time comparison.
static inline _Bool _scheduler_time_is_less_than_time(unsigned long time1, unsigned long time2) {
  // Comparing within an overflow window that is (UINT16_MAX * 2) wide.
  //
  // Visually, where ... is > (UINT32_MAX / 2)
  // 0---time2'---time1'---...---time1---time2---UNSIGNED_LONG_MAX
  //
  // Comparison      | Result| Math            | Visual math result          | Explanation
  // ----------------+-------+-----------------+-----------------------------+-----------------------------------
  // time1  < time2  | TRUE  | time2  - time1  | ---                         | time1 is < time2
  // time1  < time2' | TRUE  | time2' - time1  | --- + ---                   | subtraction causes major overflow
  // time1' < time2' | FALSE | time2' - time1' | --- + --- + --- + ---...--- | subtraction causes minor underflow
  // time1' < time2  | FALSE | time2  - time1' | ---...--- + ---             | time1' is > time2
  
  return (time2 - time1) < (UINT32_MAX / 2);
}

//
// Public API
//

void scheduler_init() {}

void scheduler_add(struct scheduler_work *unit) {
  unit->fire_next = millis() + unit->delay_millis;
  
  struct scheduler_work *later_unit = &the_scheduler_head;
  struct scheduler_work *earlier_unit;
  do {
    earlier_unit = later_unit;
    later_unit = later_unit->later;
  } while(later_unit && _scheduler_time_is_less_than_time(later_unit->fire_next, unit->fire_next));
  
  earlier_unit->later = unit;
  unit->later = later_unit;
}

void scheduler_remove(struct scheduler_work *unit) {
  struct scheduler_work *earlier_unit = &the_scheduler_head;
  while(earlier_unit != NULL && earlier_unit->later != unit) {
    earlier_unit = earlier_unit->later;
  }
  
  if (earlier_unit) {
    earlier_unit->later = unit->later;
  } else {
    // The work unit was not scheduled. This is a programmer error.
#if __has_builtin(__builtin_trap)
    __builtin_trap();
#endif
  }
}

void scheduler_run(void) {
  while(the_scheduler_head.later != NULL) {
    // Sleep until it's time for the next job.
    unsigned long delay_in_millis = the_scheduler_head.later->fire_next - millis();
    // Watch out for underflow! Delays are limited to uint16_t milliseconds.
    if (delay_in_millis > 0 && delay_in_millis <= UINT16_MAX) {
      delay(delay_in_millis);
    }
    
    the_current_unit = the_scheduler_head.later;
    the_current_unit->callback(the_current_unit->callback_context);
    
    // Re-enqueue job if it wasn't modified by its callback
    if (the_scheduler_head.later == the_current_unit) {
      scheduler_remove(the_current_unit);
      scheduler_add(the_current_unit);
    }
  }
}

scheduler.h

#pragma once

#include <stdint.h>

// Sorry about the member order, required for padding.
struct scheduler_work {
  // sizeof(void *)
  void (*callback)(void *); // parameter - must be non-NULL
  void *callback_context; // parameter
  struct scheduler_work *later; // private
  // sizeof(long)
  unsigned long fire_next; // private
  // sizeof(short)
  uint16_t delay_millis; // parameter - should be > 0
};

// Must be called once before any other calls into the scheduler API
void scheduler_init(void);

// Insert a work unit to the schedule.
// If the work unit is already scheduled, unwanted behaviour will result.
void scheduler_add(struct scheduler_work *unit);

// Remove a work unit from the schedule.
void scheduler_remove(struct scheduler_work *unit);

// This function will not return until/unless there are no jobs scheduled.
void scheduler_run(void);

scheduler_tests.c

#include "scheduler.h"
#include <assert.h>
#include <string.h>
#include <stdio.h>

// Build and run tests with: clang -Werror -Wall -g scheduler_tests.c && a.out

//
// Test harness conveniences
//

static int failures = 0;
static int tests = 0;

#define test(cond) do { \
  tests++; \
  if(!(cond)) { \
    printf("F"); \
    failures++; \
  } else { \
    printf("."); \
  } \
} while(0)

static uint32_t the_time_in_millis;
static uint32_t calls_to_delay;

//
// Black box tests
//

// Ensure scheduler_run returns immediately when the schedule is empty
static void test_scheduler_empty(void) {
  the_time_in_millis = 0;
  calls_to_delay = 0;
  scheduler_run();
  test(the_time_in_millis == 0);
  test(calls_to_delay == 0);
}

// Ensure the max allowed interval size works correctly
static int _test_scheduler_max_interval_calls = 0;
static void _test_scheduler_max_interval_callback(void *context) {
  _test_scheduler_max_interval_calls++;
  if (_test_scheduler_max_interval_calls == 2) {
    struct scheduler_work *unit = (struct scheduler_work *)context;
    scheduler_remove(unit);
  }
}
static void test_scheduler_max_interval(void) {
  the_time_in_millis = 0;

  struct scheduler_work unit;
  bzero(&unit, sizeof(struct scheduler_work));
  unit.callback = _test_scheduler_max_interval_callback;
  unit.callback_context = &unit;
  unit.delay_millis = UINT16_MAX;
  scheduler_add(&unit);
  scheduler_run();
  // Check that the callback happened only twice.
  test(_test_scheduler_max_interval_calls == 2);
  // Check that we did actually overflow correctly.
  test(the_time_in_millis != 0);
}

// Test that scheduler works properly when millis() overflows
static int _test_scheduler_overflow_calls = 0;
static void _test_scheduler_overflow_callback(void *context) {
  _test_scheduler_overflow_calls++;
  if (_test_scheduler_overflow_calls == 2) {
    struct scheduler_work *unit = (struct scheduler_work *)context;
    scheduler_remove(unit);
  }
}
static void test_scheduler_overflow(void) {
  struct scheduler_work unit;
  const unsigned delay = 50;
  bzero(&unit, sizeof(struct scheduler_work));
  the_time_in_millis = -delay;
  unit.callback = _test_scheduler_overflow_callback;
  unit.callback_context = &unit;
  unit.delay_millis = delay;
  scheduler_add(&unit);
  scheduler_run();
  // Check that the callback happened only twice.
  test(_test_scheduler_overflow_calls == 2);
  // Check that we did actually overflow correctly.
  test(the_time_in_millis == delay);
}

// Classic fizzbuzz, in scheduler form
// job 1 every 3ms
// job 2 every 5ms
// 3 5 6 9 10 12 15
// 1 2 1 1  2  1 1&2
static int _test_scheduler_fb_fizz_calls = 0;
static int _test_scheduler_fb_buzz_calls = 0;
static void _test_scheduler_fb_fizz_callback(void *context) {
  _test_scheduler_fb_fizz_calls++;
  test(the_time_in_millis % 3 == 0);
  if (the_time_in_millis == 15) {
    test(_test_scheduler_fb_fizz_calls == 5);
    struct scheduler_work *unit = (struct scheduler_work *)context;
    scheduler_remove(unit);
  }
  test(the_time_in_millis <= 15);
}
static void _test_scheduler_fb_buzz_callback(void *context) {
  _test_scheduler_fb_buzz_calls++;
  test(the_time_in_millis % 5 == 0);
  if (the_time_in_millis == 15) {
    test(_test_scheduler_fb_buzz_calls == 3);
  }
  if (the_time_in_millis == 30) {
    test(_test_scheduler_fb_buzz_calls == 6);
    struct scheduler_work *unit = (struct scheduler_work *)context;
    scheduler_remove(unit);
  }
  test(the_time_in_millis <= 30);
}
static void test_scheduler_fb(void) {
  the_time_in_millis = 0;
  
  struct scheduler_work fizz;
  bzero(&fizz, sizeof(struct scheduler_work));
  fizz.callback = _test_scheduler_fb_fizz_callback;
  fizz.callback_context = &fizz;
  fizz.delay_millis = 3;
  scheduler_add(&fizz);

  struct scheduler_work buzz;
  bzero(&buzz, sizeof(struct scheduler_work));
  buzz.callback = _test_scheduler_fb_buzz_callback;
  buzz.callback_context = &buzz;
  buzz.delay_millis = 5;
  scheduler_add(&buzz);

  scheduler_run();
  
  test(the_time_in_millis == 30);
}

// Fizz fuzz, two work units with the same delay
static int _test_scheduler_ff_fizz_calls = 0;
static int _test_scheduler_ff_fuzz_calls = 0;
static void _test_scheduler_ff_fizz_callback(void *context) {
  _test_scheduler_ff_fizz_calls++;
  test(the_time_in_millis % 3 == 0);
  if (the_time_in_millis == 15) {
    test(_test_scheduler_ff_fizz_calls == 5);
    struct scheduler_work *unit = (struct scheduler_work *)context;
    scheduler_remove(unit);
  }
  test(the_time_in_millis <= 15);
}
static void _test_scheduler_ff_fuzz_callback(void *context) {
  _test_scheduler_ff_fuzz_calls++;
  test(the_time_in_millis % 3 == 0);
  if (the_time_in_millis == 15) {
    test(_test_scheduler_ff_fuzz_calls == 5);
    struct scheduler_work *unit = (struct scheduler_work *)context;
    scheduler_remove(unit);
  }
  test(the_time_in_millis <= 30);
}
static void test_scheduler_ff(void) {
  the_time_in_millis = 0;
  
  struct scheduler_work fizz;
  bzero(&fizz, sizeof(struct scheduler_work));
  fizz.callback = _test_scheduler_ff_fizz_callback;
  fizz.callback_context = &fizz;
  fizz.delay_millis = 3;
  scheduler_add(&fizz);

  struct scheduler_work fuzz;
  bzero(&fuzz, sizeof(struct scheduler_work));
  fuzz.callback = _test_scheduler_ff_fuzz_callback;
  fuzz.callback_context = &fuzz;
  fuzz.delay_millis = 3;
  scheduler_add(&fuzz);

  scheduler_run();
  
  test(the_time_in_millis == 15);
}

// Starvation test, one work unit has a delay of 0
static int _test_scheduler_starve_fizz_calls = 0;
static int _test_scheduler_starve_fuzz_calls = 0;
static void _test_scheduler_starve_fizz_callback(void *context) {
  _test_scheduler_starve_fizz_calls++;
  
  // Callbacks will always take time, this one takes 500ns
  the_time_in_millis = _test_scheduler_starve_fizz_calls / 5;
  
  if (the_time_in_millis == 15) {
    // test(_test_scheduler_starve_fizz_calls == 15);
    struct scheduler_work *unit = (struct scheduler_work *)context;
    scheduler_remove(unit);
  }
  test(the_time_in_millis <= 15);
}
static void _test_scheduler_starve_fuzz_callback(void *context) {
  _test_scheduler_starve_fuzz_calls++;
  test(the_time_in_millis % 3 == 0);
  if (the_time_in_millis == 15) {
    test(_test_scheduler_starve_fuzz_calls == 5);
    struct scheduler_work *unit = (struct scheduler_work *)context;
    scheduler_remove(unit);
  }
  test(the_time_in_millis <= 30);
}
static void test_scheduler_starve(void) {
  the_time_in_millis = 0;
  
  struct scheduler_work fizz;
  bzero(&fizz, sizeof(struct scheduler_work));
  fizz.callback = _test_scheduler_starve_fizz_callback;
  fizz.callback_context = &fizz;
  fizz.delay_millis = 0;
  scheduler_add(&fizz);

  struct scheduler_work fuzz;
  bzero(&fuzz, sizeof(struct scheduler_work));
  fuzz.callback = _test_scheduler_starve_fuzz_callback;
  fuzz.callback_context = &fuzz;
  fuzz.delay_millis = 3;
  scheduler_add(&fuzz);

  scheduler_run();
  
  test(the_time_in_millis == 15);
}

//
// Symbol dependencies of code under test
//

static void delay(unsigned long millis) {
  test(millis != 0);
  test(millis <= UINT16_MAX);
  printf("[%lu]", millis);
  calls_to_delay++;
  the_time_in_millis += millis;
}

static unsigned long millis(void) {
  return the_time_in_millis;
}

//
// Code under test
//

#include "scheduler.c"

//
// White box tests
//

static void test_scheduler_time_is_less_than_time(void) {
  // _Bool _scheduler_time_is_less_than_time(unsigned long time1, unsigned long time2)
  test(_scheduler_time_is_less_than_time(0, 20));
  test(!_scheduler_time_is_less_than_time(20, 0));
  test(_scheduler_time_is_less_than_time((unsigned long)(-10), 10));
  test(!_scheduler_time_is_less_than_time(10, (unsigned long)(-10)));
}

//
// Test runner
//

int main() {
  scheduler_init();
  
  // Editors with multiple carats are the best. Find all: "static void test[underscore]", select whole word, copy, paste, call.
  test_scheduler_empty();
  test_scheduler_max_interval();
  test_scheduler_overflow();
  test_scheduler_fb();
  test_scheduler_ff();
  test_scheduler_starve();
  test_scheduler_time_is_less_than_time();
  
  printf("\n%d failures in %d checks\n", failures, tests);
  return 0;
}

MIT license. Depends on void delay(unsigned long millis) and unsigned long millis(void).

Tests build and run with: clang -Werror -Wall -g scheduler_tests.c && a.out. GCC probably works too.

Compiles and passes tests with gcc -Wall -Werror, provided you replace #include <libc.h> with #include <string.h> and also set the -Wno-unknown-pragmas flag to ignore uses of #pragma mark.

Thanks! Updated.

By request, this project now has its own repository.