Alarm infrastructure
authorBarret Rhoden <brho@cs.berkeley.edu>
Tue, 3 May 2011 22:28:50 +0000 (15:28 -0700)
committerKevin Klues <klueska@cs.berkeley.edu>
Thu, 3 Nov 2011 00:36:01 +0000 (17:36 -0700)
Allows you to block a kthread for a while or to run a handler after a
while.  These alarms are grouped in sorted chains, which are attached to
an interrupt source.  Currently, there are chains for the per-core timer
interrupts.

Check out k/i/alarm.h for a quick howto.

kern/arch/i686/smp_boot.c
kern/arch/sparc/smp.c
kern/include/alarm.h [new file with mode: 0644]
kern/include/smp.h
kern/src/Makefrag
kern/src/alarm.c [new file with mode: 0644]
kern/src/timer.c

index ad62926..864cf75 100644 (file)
@@ -314,4 +314,6 @@ void smp_percpu_init(void)
        
        /* need to init perfctr before potentiall using it in timer handler */
        perfmon_init();
+       /* Initialize the per-core timer chain */
+       init_timer_chain(&per_cpu_info[coreid].tchain, set_pcpu_alarm_interrupt);
 }
index 6fd880b..267e86e 100644 (file)
@@ -158,4 +158,6 @@ void smp_percpu_init(void)
        STAILQ_INIT(&per_cpu_info[coreid].immed_amsgs);
        spinlock_init(&per_cpu_info[coreid].routine_amsg_lock);
        STAILQ_INIT(&per_cpu_info[coreid].routine_amsgs);
+       /* Initialize the per-core timer chain */
+       init_timer_chain(&per_cpu_info[coreid].tchain, set_pcpu_alarm_interrupt);
 }
diff --git a/kern/include/alarm.h b/kern/include/alarm.h
new file mode 100644 (file)
index 0000000..1e0ce54
--- /dev/null
@@ -0,0 +1,88 @@
+/* Copyright (c) 2011 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Alarms.  This includes various ways to sleep for a while or defer work on a
+ * specific timer.  These can be per-core, global or whatever.  Deferred work
+ * is a function pointer which runs in interrupt context when the alarm goes off
+ * (picture running the ksched then).  The other style is to block/sleep on the
+ * awaiter after the alarm is set.
+ *
+ * Like with most systems, you won't wake up til after the time you specify (for
+ * now).  This might change, esp if we tweak things to coalesce alarms.
+ *
+ * If you're using a global alarm timer_chain, you'll probably need to grab a
+ * lock.  The only current user is pcpu tchains, though the code ought be able
+ * to handle other uses.
+ *
+ * Quick howto, using the pcpu tchains:
+ *     struct timer_chain *tchain = &per_cpu_info[core_id()].tchain;
+ *     struct alarm_waiter a_waiter;
+ * 1) To block your kthread on an alarm:
+ *     init_awaiter(&a_waiter, 0);
+ *     set_awaiter_rel(&a_waiter, USEC);
+ *     set_alarm(tchain, &a_waiter);
+ *     sleep_on_awaiter(&a_waiter);
+ * 2) To set a handler to run on an alarm:
+ *     init_awaiter(&a_waiter, HANDLER);
+ *     set_awaiter_rel(&a_waiter, USEC);
+ *     set_alarm(tchain, &a_waiter);
+ * If you want the HANDLER to run again, do this at the end of it::
+ *     set_awaiter_rel(waiter, USEC);
+ *     set_alarm(tchain, waiter);
+ * */
+
+#ifndef ROS_KERN_ALARM_H
+#define ROS_KERN_ALARM_H
+
+#include <ros/common.h>
+#include <sys/queue.h>
+#include <kthread.h>
+
+/* These structures allow code to block or defer work for a certain amount of
+ * time.  Timer chains (like off a per-core timer) are made of lists/trees of
+ * these. 
+ *
+ * If you have a func pointer, that handler will run when the alarm goes off.
+ * If you don't have a func pointer, you sleep on the semaphore and block your
+ * kthread.  In the latter case, you ought to allocate space for them on the
+ * stack of the thread you're about to block on. */
+struct alarm_waiter {
+       uint64_t                                        wake_up_time;   /* ugh, this is a TSC for now */
+       void (*func) (struct alarm_waiter *waiter);     /* either this, or a kthread */
+       struct semaphore                        sem;                    /* kthread will sleep on this */
+       void                                            *data;
+       TAILQ_ENTRY(alarm_waiter)       next;
+};
+TAILQ_HEAD(awaiters_tailq, alarm_waiter);              /* ideally not a LL */
+
+/* One of these per alarm source, such as a per-core timer.  Based on the
+ * source, you may need a lock (such as for a global timer).  set_interrupt() is
+ * a method for setting the interrupt source. */
+struct timer_chain {
+       struct awaiters_tailq           waiters;
+       uint64_t                                        earliest_time;
+       uint64_t                                        latest_time;
+       void (*set_interrupt) (uint64_t time, struct timer_chain *);
+};
+
+/* Called once per timer chain, currently in per_cpu_init() */
+void init_timer_chain(struct timer_chain *tchain,
+                      void (*set_interrupt) (uint64_t, struct timer_chain *));
+/* For fresh alarm waiters.  func == 0 for kthreads */
+void init_awaiter(struct alarm_waiter *waiter,
+                  void (*func) (struct alarm_waiter *));
+/* Sets the time an awaiter goes off */
+void set_awaiter_abs(struct alarm_waiter *waiter, uint64_t abs_time);
+void set_awaiter_rel(struct alarm_waiter *waiter, uint64_t usleep);
+/* Arms/disarms the alarm */
+void set_alarm(struct timer_chain *tchain, struct alarm_waiter *waiter);
+void unset_alarm(struct timer_chain *tchain, struct alarm_waiter *waiter);
+/* Blocks on the alarm waiter */
+int sleep_on_awaiter(struct alarm_waiter *waiter);
+/* Interrupt handlers needs to call this.  Don't call it directly. */
+void trigger_tchain(struct timer_chain *tchain);
+/* How to set a specific alarm: the per-cpu timer interrupt */
+void set_pcpu_alarm_interrupt(uint64_t time, struct timer_chain *tchain);
+
+#endif /* ROS_KERN_ALARM_H */
index bc0bb9a..076ebca 100644 (file)
@@ -16,6 +16,7 @@
 #include <atomic.h>
 #include <process.h>
 #include <syscall.h>
+#include <alarm.h>
 
 #ifdef __SHARC__
 typedef sharC_env_t;
@@ -30,6 +31,7 @@ struct per_cpu_info {
        struct trapframe actual_tf;     /* storage for cur_tf */
        struct syscall *cur_sysc;       /* ptr is into cur_proc's address space */
        struct kthread *spare;          /* useful when restarting */
+       struct timer_chain tchain;      /* for the per-core alarm */
 
 #ifdef __SHARC__
        // held spin-locks. this will have to go elsewhere if multiple kernel
index d6da11e..22307d0 100644 (file)
@@ -52,6 +52,7 @@ KERN_SRCFILES := $(KERN_ARCH_SRCFILES) \
                  $(KERN_SRC_DIR)/eth_audio.c \
                  $(KERN_SRC_DIR)/net.c \
                  $(KERN_SRC_DIR)/event.c \
+                 $(KERN_SRC_DIR)/alarm.c \
                  $(KERN_SRC_DIR)/arsc.c
 
 # Only build files if they exist.
diff --git a/kern/src/alarm.c b/kern/src/alarm.c
new file mode 100644 (file)
index 0000000..48e99d4
--- /dev/null
@@ -0,0 +1,264 @@
+/* Copyright (c) 2011 The Regents of the University of California
+ * Barret Rhoden <brho@cs.berkeley.edu>
+ * See LICENSE for details.
+ *
+ * Alarms.  This includes various ways to sleep for a while or defer work on a
+ * specific timer.  These can be per-core, global or whatever.  Like with most
+ * systems, you won't wake up til after the time you specify. (for now, this
+ * might change).
+ *
+ * TODO:
+ *     - have a kernel sense of time, instead of just the TSC or whatever timer the
+ *     chain uses...
+ *     - coalesce or otherwise deal with alarms that are close to cut down on
+ *     interrupt overhead. */
+
+#include <ros/common.h>
+#include <sys/queue.h>
+#include <kthread.h>
+#include <alarm.h>
+#include <stdio.h>
+#include <smp.h>
+
+/* Helper, resets the earliest/latest times, based on the elements of the list.
+ * If the list is empty, any new waiters will be earlier and later than the
+ * current (which is none). */
+static void reset_tchain_times(struct timer_chain *tchain)
+{
+       if (TAILQ_EMPTY(&tchain->waiters)) {
+               tchain->earliest_time = (uint64_t)-1;
+               tchain->latest_time = 0;
+       } else {
+               tchain->earliest_time = TAILQ_FIRST(&tchain->waiters)->wake_up_time;
+               tchain->latest_time =
+                       TAILQ_LAST(&tchain->waiters, awaiters_tailq)->wake_up_time;
+       }
+}
+
+/* One time set up of a tchain, currently called in per_cpu_init() */
+void init_timer_chain(struct timer_chain *tchain,
+                      void (*set_interrupt) (uint64_t, struct timer_chain *))
+{
+       TAILQ_INIT(&tchain->waiters);
+       tchain->set_interrupt = set_interrupt;
+       reset_tchain_times(tchain);
+}
+
+/* Initializes a new awaiter.  Pass 0 for the function if you want it to be a
+ * kthread-alarm, and sleep on it after you set the alarm later. */
+void init_awaiter(struct alarm_waiter *waiter,
+                  void (*func) (struct alarm_waiter *awaiter))
+{
+       waiter->wake_up_time = (uint64_t)-1;
+       waiter->func = func;
+       if (!func)
+               init_sem(&waiter->sem, 0);
+}
+
+/* Give this the absolute time.  For now, abs_time is the TSC time that you want
+ * the alarm to go off. */
+void set_awaiter_abs(struct alarm_waiter *waiter, uint64_t abs_time)
+{
+       waiter->wake_up_time = abs_time;
+}
+
+/* Give this a relative time from now, in microseconds.  This might be easier to
+ * use than dealing with the TSC. */
+void set_awaiter_rel(struct alarm_waiter *waiter, uint64_t usleep)
+{
+       uint64_t now = read_tsc();
+       set_awaiter_abs(waiter, now + usleep * (system_timing.tsc_freq / 1000000));
+}
+
+/* Helper, makes sure the interrupt is turned on at the right time.  Most of the
+ * heavy lifting is in the timer-source specific function pointer. */
+static void reset_tchain_interrupt(struct timer_chain *tchain)
+{
+       assert(!irq_is_enabled());
+       if (TAILQ_EMPTY(&tchain->waiters)) {
+               /* Turn it off */
+               tchain->set_interrupt(0, tchain);
+       } else {
+               /* Make sure it is on and set to the earliest time */
+               /* TODO: check for times in the past or very close to now */
+               tchain->set_interrupt(tchain->earliest_time, tchain);
+       }
+}
+
+/* When an awaiter's time has come, this gets called.  If it was a kthread, it
+ * will wake up.  o/w, it will call the func ptr stored in the awaiter. */
+static void wake_awaiter(struct alarm_waiter *waiter)
+{
+       if (waiter->func) {
+               waiter->func(waiter);
+       } else {
+               /* Might encaps this */
+               struct kthread *sleeper;
+               sleeper = __up_sem(&waiter->sem);
+               if (sleeper)
+                       kthread_runnable(sleeper);
+               assert(TAILQ_EMPTY(&waiter->sem.waiters));
+       }
+}
+
+/* This is called when an interrupt triggers a tchain, and needs to wake up
+ * everyone whose time is up. */
+void trigger_tchain(struct timer_chain *tchain)
+{
+       struct alarm_waiter *i, *temp;
+       uint64_t now = read_tsc();
+       bool changed_list = FALSE;
+       assert(!irq_is_enabled());
+       TAILQ_FOREACH_SAFE(i, &tchain->waiters, next, temp) {
+               printd("Trying to wake up %08p who is due at %llu and it is now %llu\n",
+                      i, i->wake_up_time, now);
+               /* TODO: Could also do something in cases where we're close to now */
+               if (i->wake_up_time <= now) {
+                       changed_list = TRUE;
+                       TAILQ_REMOVE(&tchain->waiters, i, next);
+                       wake_awaiter(i);
+               } else {
+                       break;
+               }
+       }
+       if (changed_list) {
+               reset_tchain_times(tchain);
+       }
+       /* Need to reset the interrupt no matter what */
+       reset_tchain_interrupt(tchain);
+}
+
+/* Sets the alarm.  If it is a kthread-style alarm (func == 0), sleep on it
+ * later.  Hold the lock, if applicable.  If this is a per-core tchain, the
+ * interrupt-disabling ought to suffice. */
+void set_alarm(struct timer_chain *tchain, struct alarm_waiter *waiter)
+{
+       struct alarm_waiter *i, *temp;
+       bool reset_int = FALSE;
+       int8_t irq_state = 0;
+       bool inserted = FALSE;
+
+       disable_irqsave(&irq_state);
+       /* Set the tchains upper and lower bounds, possibly needing a change to the
+        * interrupt time. */
+       if (waiter->wake_up_time < tchain->earliest_time) {
+               tchain->earliest_time = waiter->wake_up_time;
+               /* later on, set the core time to go off at the new, earliest time */
+               reset_int = TRUE;
+       }
+       if (waiter->wake_up_time > tchain->latest_time) {
+               tchain->latest_time = waiter->wake_up_time;
+               /* Proactively put it at the end if we know we're last */
+               TAILQ_INSERT_TAIL(&tchain->waiters, waiter, next);
+               inserted = TRUE;
+       }
+       /* Insert before the first one you are earlier than.  This won't scale well
+        * (TODO) if we have a lot of inserts.  The proactive insert_tail up above
+        * will help a bit. */
+       if (!inserted) {
+               TAILQ_FOREACH_SAFE(i, &tchain->waiters, next, temp) {
+                       if (waiter->wake_up_time < i->wake_up_time) {
+                               TAILQ_INSERT_BEFORE(i, waiter, next);
+                               inserted = TRUE;
+                               break;
+                       }
+               }
+       }
+       /* Still not in?  The list ought to be empty. */
+       if (!inserted) {
+               assert(TAILQ_EMPTY(&tchain->waiters));
+               TAILQ_INSERT_HEAD(&tchain->waiters, waiter, next);
+       }
+       if (reset_int)
+               reset_tchain_interrupt(tchain);
+       enable_irqsave(&irq_state);
+}
+
+/* Removes waiter from the tchain before it goes off.  */
+void unset_alarm(struct timer_chain *tchain, struct alarm_waiter *waiter)
+{
+       struct alarm_waiter *temp;
+       bool reset_int = FALSE;         /* whether or not to reset the interrupt */
+       int8_t irq_state = 0;
+
+       disable_irqsave(&irq_state);
+       /* Need to make sure earliest and latest are set, in case we're mucking with
+        * the first and/or last element of the chain. */
+       if (TAILQ_FIRST(&tchain->waiters) == waiter) {
+               temp = TAILQ_NEXT(waiter, next);
+               tchain->earliest_time = (temp) ? temp->wake_up_time : (uint64_t)-1;
+               reset_int = TRUE;               /* we'll need to reset the timer later */
+       }
+       if (TAILQ_LAST(&tchain->waiters, awaiters_tailq) == waiter) {
+               temp = TAILQ_PREV(waiter, awaiters_tailq, next);
+               tchain->latest_time = (temp) ? temp->wake_up_time : 0;
+       }
+       TAILQ_REMOVE(&tchain->waiters, waiter, next);
+       if (reset_int)
+               reset_tchain_interrupt(tchain);
+       enable_irqsave(&irq_state);
+}
+
+/* Attempts to sleep on the alarm.  Could fail if you aren't allowed to kthread
+ * (process limit, etc).  Don't call it on a waiter that is an event-handler. */
+int sleep_on_awaiter(struct alarm_waiter *waiter)
+{
+       if (waiter->func)
+               panic("Tried blocking on a waiter %08p with a func %08p!", waiter,
+                     waiter->func);
+       /* Put the kthread to sleep.  TODO: This can fail (or at least it will be
+        * able to in the future) and we'll need to handle that. */
+       sleep_on(&waiter->sem);
+       return 0;
+}
+
+/* Sets the Alarm interrupt, per-core style.  Also is an example of what any
+ * similar function needs to do (this is the func ptr in the tchain). 
+ * Note the tchain is our per-core one, and we don't need tchain passed to us to
+ * figure that out.  It's kept around in case other tchain-usage wants it -
+ * might not be necessary in the future.
+ *
+ * Needs to set the interrupt to trigger tchain at the given time, or disarm it
+ * if time is 0.   Any function like this needs to do a few things:
+ *     - Make sure the interrupt is on and will go off when we want
+ *     - Make sure the interrupt source can find tchain
+ *     - Make sure the interrupt handler calls trigger_tchain(tchain)
+ *     - Make sure you don't clobber an old tchain here (a bug) 
+ * This implies the function knows how to find its timer source/void */
+void set_pcpu_alarm_interrupt(uint64_t time, struct timer_chain *tchain)
+{
+       uint64_t rel_usec, now;
+       struct timer_chain *pcpui_tchain = &per_cpu_info[core_id()].tchain;
+       if (time) {
+               /* Arm the alarm.  For times in the past, we just need to make sure it
+                * goes off. */
+               now = read_tsc();
+               if (time <= now)
+                       rel_usec = 1;
+               else
+                       rel_usec = ((time - now) / (system_timing.tsc_freq / 1000000));
+               printd("Setting alarm for %llu, it is now %llu, rel_time %llu "
+                      "tchain %08p\n", time, now, rel_usec, pcpui_tchain);
+               /* Note that sparc doesn't honor the one-shot setting, so you might get
+                * spurious interrupts. */
+               set_core_timer(rel_usec);       /* TODO: Want this to be one-shot */
+               /* Make sure the caller is setting the right tchain */
+               assert(pcpui_tchain == tchain);
+       } else  {
+               /* Disarm */
+               set_core_timer(0);
+       }
+}
+
+/* Debug helpers */
+void print_chain(struct timer_chain *tchain)
+{
+       struct alarm_waiter *i;
+       printk("Chain %08p is%s empty, early: %llu latest: %llu\n", tchain,
+              TAILQ_EMPTY(&tchain->waiters) ? "" : " not",
+              tchain->earliest_time,
+              tchain->latest_time);
+       TAILQ_FOREACH(i, &tchain->waiters, next) {
+               printk("\tWaiter %08p, time: %llu\n", i, i->wake_up_time);
+       }
+}
index 3bee85d..0170715 100644 (file)
@@ -11,6 +11,7 @@
 #include <schedule.h>
 #include <multiboot.h>
 #include <pmap.h>
+#include <smp.h>
 
 /* timing_overhead
  * Any user space process that links to this file will get its own copy.  
@@ -79,9 +80,11 @@ void train_timing()
        timing_overhead = training_overhead;
 }
 
-/* Typical per-core timer interrupt handler.  Note that sparc's timer is
- * periodic by nature, so if you want it to not be periodic, turn off the alarm
- * in here. */
+/* Convenience wrapper called when a core's timer interrupt goes off.  Not to be
+ * confused with global timers (like the PIC).  Do not put your code here.  If
+ * you want something to happen in the future, set an alarm. */
 void timer_interrupt(struct trapframe *tf, void *data)
 {
+       struct timer_chain *pcpui_tchain = &per_cpu_info[core_id()].tchain;
+       trigger_tchain(pcpui_tchain);
 }