Initial commit

1 files changed, 321 insertions, 0 deletions

diff --git a/src/timer.c b/src/timer.c
new file mode 100644
index 0000000..b663e10
--- /dev/null
+++ b/src/timer.c
@@ -0,0 +1,321 @@
+/*
+ * Copyright (c) 2017 Richard Braun.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ */
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+#include <lib/list.h>
+#include <lib/macros.h>
+
+#include "cpu.h"
+#include "mutex.h"
+#include "panic.h"
+#include "thread.h"
+#include "timer.h"
+
+#define TIMER_STACK_SIZE 4096
+
+/*
+ * When determining whether a point in time is in the future or the past,
+ * it's important to remember that the value is always finite. Here,
+ * the ticks use a 32-bits type (unsigned long on i386), so, assuming
+ * a 100Hz frequency, time wraps around about every 497 days. Therefore,
+ * the implementation needs a way to partition time between the future
+ * and the past. To do so, it considers that all values from a reference
+ * up to a threshold are in the future (except the present), and all other
+ * values are in the past. This macro defines that threshold.
+ *
+ * Currently, the threshold is half of the maximum value, which is
+ * equivalent to using a signed integer where positive values would denote
+ * the future and negative ones the past, except that overflows on signed
+ * integers are undefined behaviour, whereas overflows on unsigned
+ * integers are well specified (3.4.3 Undefined Behaviour and 6.2.5 Types).
+ */
+#define TIMER_THRESHOLD (((unsigned long)-1) / 2)
+
+/*
+ * The current time, in ticks.
+ */
+static unsigned long timer_ticks;
+
+/*
+ * List of timers, sorted by time.
+ *
+ * The timer mutex must be locked when accessing the timer list.
+ */
+static struct list timer_list;
+static struct mutex timer_mutex;
+
+/*
+ * The timer thread, which provides context for all timer callbacks.
+ */
+static struct thread *timer_thread;
+
+/*
+ * True if the timer list is empty.
+ *
+ * This is a copy of list_empty(&timer_list) which may be used from
+ * interrupt context, where locking a mutex is impossible.
+ *
+ * Interrupts must be disabled when accessing this variable.
+ */
+static bool timer_list_empty;
+
+/*
+ * Time in ticks of the first timer on the timer list.
+ *
+ * Only valid if the list isn't empty.
+ *
+ * Interrupts must be disabled when accessing this variable.
+ */
+static unsigned long timer_wakeup_ticks;
+
+bool
+timer_ticks_expired(unsigned long ticks, unsigned long ref)
+{
+    return (ticks - ref) > TIMER_THRESHOLD;
+}
+
+bool
+timer_ticks_occurred(unsigned long ticks, unsigned long ref)
+{
+    return (ticks == ref) || timer_ticks_expired(ticks, ref);
+}
+
+static bool
+timer_work_pending(void)
+{
+    assert(!cpu_intr_enabled());
+
+    return !timer_list_empty
+           && timer_ticks_occurred(timer_wakeup_ticks, timer_ticks);
+}
+
+static bool
+timer_scheduled(const struct timer *timer)
+{
+    return !list_node_unlinked(&timer->node);
+}
+
+static bool
+timer_expired(const struct timer *timer, unsigned long ref)
+{
+    return timer_ticks_expired(timer->ticks, ref);
+}
+
+static bool
+timer_occurred(const struct timer *timer, unsigned long ref)
+{
+    return timer_ticks_occurred(timer->ticks, ref);
+}
+
+static void
+timer_process(struct timer *timer)
+{
+    timer->fn(timer->arg);
+}
+
+static void
+timer_process_list(unsigned long now)
+{
+    struct timer *timer;
+    uint32_t eflags;
+
+    mutex_lock(&timer_mutex);
+
+    while (!list_empty(&timer_list)) {
+        timer = list_first_entry(&timer_list, typeof(*timer), node);
+
+        if (!timer_occurred(timer, now)) {
+            break;
+        }
+
+        list_remove(&timer->node);
+        list_node_init(&timer->node);
+        mutex_unlock(&timer_mutex);
+
+        timer_process(timer);
+
+        mutex_lock(&timer_mutex);
+    }
+
+    eflags = cpu_intr_save();
+
+    timer_list_empty = list_empty(&timer_list);
+
+    if (!timer_list_empty) {
+        timer = list_first_entry(&timer_list, typeof(*timer), node);
+        timer_wakeup_ticks = timer->ticks;
+    }
+
+    cpu_intr_restore(eflags);
+
+    mutex_unlock(&timer_mutex);
+}
+
+static void
+timer_run(void *arg)
+{
+    unsigned long now;
+    uint32_t eflags;
+
+    (void)arg;
+
+    for (;;) {
+        thread_preempt_disable();
+        eflags = cpu_intr_save();
+
+        for (;;) {
+            now = timer_ticks;
+
+            if (timer_work_pending()) {
+                break;
+            }
+
+            thread_sleep();
+        }
+
+        cpu_intr_restore(eflags);
+        thread_preempt_enable();
+
+        timer_process_list(now);
+    }
+}
+
+void
+timer_setup(void)
+{
+    int error;
+
+    timer_ticks = 0;
+    timer_list_empty = true;
+
+    list_init(&timer_list);
+    mutex_init(&timer_mutex);
+
+    error = thread_create(&timer_thread, timer_run, NULL,
+                          "timer", TIMER_STACK_SIZE, THREAD_MAX_PRIORITY);
+
+    if (error) {
+        panic("timer: unable to create thread");
+    }
+}
+
+unsigned long
+timer_now(void)
+{
+    unsigned long ticks;
+    uint32_t eflags;
+
+    eflags = cpu_intr_save();
+    ticks = timer_ticks;
+    cpu_intr_restore(eflags);
+
+    return ticks;
+}
+
+void
+timer_init(struct timer *timer, timer_fn_t fn, void *arg)
+{
+    list_node_init(&timer->node);
+    timer->fn = fn;
+    timer->arg = arg;
+}
+
+unsigned long
+timer_get_time(const struct timer *timer)
+{
+    unsigned long ticks;
+
+    mutex_lock(&timer_mutex);
+    ticks = timer->ticks;
+    mutex_unlock(&timer_mutex);
+
+    return ticks;
+}
+
+void
+timer_schedule(struct timer *timer, unsigned long ticks)
+{
+    struct timer *tmp;
+    uint32_t eflags;
+
+    mutex_lock(&timer_mutex);
+
+    assert(!timer_scheduled(timer));
+
+    timer->ticks = ticks;
+
+    /*
+     * Find the insertion point,
+     *
+     * This makes timer scheduling an O(n) operation, and assumes a low
+     * number of timers. This is also why a mutex is used instead of
+     * disabling preemption, since preemption then remains enabled,
+     * allowing higher priority threads to run.
+     *
+     * [1] https://en.wikipedia.org/wiki/Big_O_notation
+     */
+    list_for_each_entry(&timer_list, tmp, node) {
+        if (!timer_expired(tmp, ticks)) {
+            break;
+        }
+    }
+
+    list_insert_before(&tmp->node, &timer->node);
+
+    timer = list_first_entry(&timer_list, typeof(*timer), node);
+
+    /*
+     * This interrupt-based critical section could be moved outside the
+     * mutex-based one, which would make the latter shorter. The downside
+     * of this approach is that a timer interrupt occurring after unlocking
+     * the mutex but before disabling interrupts will wake up the timer
+     * thread, if there was work pending already. The timer thread may
+     * preempt the current thread and process all timers before the current
+     * thread resumes and clears the list empty flag. At the next timer
+     * interrupt, the handler will determine that there is work pending and
+     * wake up the timer thread, despite the fact that there is actually no
+     * timer in the list.
+     *
+     * By holding the mutex while clearing the list empty flag, potential
+     * spurious wake-ups are completely avoided.
+     */
+    eflags = cpu_intr_save();
+    timer_list_empty = false;
+    timer_wakeup_ticks = timer->ticks;
+    cpu_intr_restore(eflags);
+
+    mutex_unlock(&timer_mutex);
+}
+
+void
+timer_report_tick(void)
+{
+    timer_ticks++;
+
+    if (timer_work_pending()) {
+        thread_wakeup(timer_thread);
+    }
+}