Adding events is now accomplished in O(1) time

5 files changed, 104 insertions, 94 deletions

diff --git a/include/linux/hrtimer.h b/include/linux/hrtimer.h
index 573cb3419625..0315d04211f3 100644
--- a/include/linux/hrtimer.h
+++ b/include/linux/hrtimer.h
@@ -378,8 +378,8 @@ extern void hrtimer_start_on_info_init(struct hrtimer_start_on_info *info);
 extern int hrtimer_start_on(int cpu, struct hrtimer_start_on_info *info,
                         struct hrtimer *timer, ktime_t time,
                         const enum hrtimer_mode mode);
-extern void hrtimer_pull_cancel(int cpu, struct hrtimer *timer,
-                                struct hrtimer_start_on_info *info);
+extern int hrtimer_pull_cancel(int cpu, struct hrtimer *timer,
+                               struct hrtimer_start_on_info *info);
 #endif
 
 extern int hrtimer_cancel(struct hrtimer *timer);
diff --git a/include/litmus/event_group.h b/include/litmus/event_group.h
index 90ddd0bfe673..b0654e0ec5e6 100644
--- a/include/litmus/event_group.h
+++ b/include/litmus/event_group.h
@@ -3,6 +3,8 @@
 
 #define EVENT_QUEUE_SLOTS 127 /* prime */
 
+#define NUM_EVENT_PRIORITIES 4 /* num crit levels really */
+
 struct rt_event;
 typedef void (*fire_event_t)(struct rt_event *e);
 
@@ -17,7 +19,8 @@ struct event_group {
  * A group of actions to fire at a given time
  */
 struct event_list {
-        struct list_head events;
+        /* Use multiple list heads so that inserts are O(1) */
+        struct list_head events[NUM_EVENT_PRIORITIES];
 
         /* For timer firing */
         lt_t                            fire_time;
diff --git a/kernel/hrtimer.c b/kernel/hrtimer.c
index a8c3135dfed5..c215ddbf49d0 100644
--- a/kernel/hrtimer.c
+++ b/kernel/hrtimer.c
@@ -1083,8 +1083,8 @@ void hrtimer_pull(void)
 /**
  * hrtimer_pull_cancel - Cancel a remote timer pull
  */
-void hrtimer_pull_cancel(int cpu, struct hrtimer *timer,
-                         struct hrtimer_start_on_info *info)
+int hrtimer_pull_cancel(int cpu, struct hrtimer *timer,
+                        struct hrtimer_start_on_info *info)
 {
         struct hrtimer_cpu_base *base = &per_cpu(hrtimer_bases, cpu);
 
@@ -1093,7 +1093,7 @@ void hrtimer_pull_cancel(int cpu, struct hrtimer *timer,
         raw_spin_unlock(&base->lock);
 
         atomic_set(&info->state, HRTIMER_START_ON_INACTIVE);
-        hrtimer_try_to_cancel(timer);
+        return hrtimer_try_to_cancel(timer);
 }
 
 /**
diff --git a/litmus/event_group.c b/litmus/event_group.c
index 4a54881fb256..81bc87e98bbd 100644
--- a/litmus/event_group.c
+++ b/litmus/event_group.c
@@ -29,71 +29,55 @@ static unsigned int time2slot(lt_t time)
  */
 static enum hrtimer_restart on_timer(struct hrtimer *timer)
 {
-        unsigned long num = 0;
+        int prio, num;
         struct event_list *el;
         struct rt_event *e;
-        struct list_head *pos, events;
+        struct list_head *pos, events[NUM_EVENT_PRIORITIES];
+        raw_spinlock_t *queue_lock;
 
         el = container_of(timer, struct event_list, timer);
+        queue_lock = &el->group->queue_lock;
 
-        raw_spin_lock(&el->group->queue_lock);
+        raw_spin_lock(queue_lock);
 
-        /* Remove event_list from hashtable so no more events
+        /* Remove event_list from hashtable so that no more events
          * are added to it.
          */
-        VTRACE("Removing event list 0x%p\n", el);
+        VTRACE("Removing event list 0x%x\n", el);
         list_del_init(&el->queue_node);
 
-        /* Empty event list so that it can be re-used as soon
-         * as the lock is released.
+        /* Copy over events so that the event_list can re-used when the lock
+         * is released.
          */
-        VTRACE("Emptying event list 0x%p\n", el);
-        list_replace_init(&el->events, &events);
-
-        /* Fire events */
-        for (pos = events.next; prefetch(pos->next), events.next != &events;
-             pos = events.next, num++) {
+        VTRACE("Emptying event list 0x%x\n", el);
+        for (prio = 0; prio < NUM_EVENT_PRIORITIES; prio++) {
+                list_replace_init(&el->events[prio], &events[prio]);
+        }
 
-                e = list_entry(pos, struct rt_event, events_node);
-                list_del_init(pos);
-                raw_spin_unlock(&el->group->queue_lock);
+        for (prio = 0; prio < NUM_EVENT_PRIORITIES; prio++) {
+                /* Fire events. Complicated loop is used so that events
+                 * in the list can be canceled (removed) while other events are
+                 * executing.
+                 */
+                for (pos = events[prio].next, num = 0;
+                     prefetch(pos->next), events[prio].next != &events[prio];
+                     pos = events[prio].next, num++) {
 
-                VTRACE("Dequeueing event 0x%p with prio %d from 0x%p\n",
-                      e, e->prio, el);
+                        e = list_entry(pos, struct rt_event, events_node);
+                        list_del_init(pos);
+                        raw_spin_unlock(queue_lock);
 
-                e->function(e);
+                        VTRACE("Dequeueing event 0x%x with prio %d from 0x%x\n",
+                               e, e->prio, el);
+                        e->function(e);
 
-                raw_spin_lock(&el->group->queue_lock);
-        }
-        raw_spin_unlock(&el->group->queue_lock);
-        VTRACE("Exhausted %d events from list 0x%p\n", num, el);
-        /* sched_trace_action(NULL, num); */
-        return HRTIMER_NORESTART;
-}
-
-/*
- * Insert event in event-list, respecting priority order.
- */
-void insert_event(struct event_list *el, struct rt_event *e)
-{
-        struct list_head *pos, *last = NULL;
-        struct rt_event *queued;
-        list_for_each(pos, &el->events) {
-                queued = list_entry(pos, struct rt_event, events_node);
-                last = pos;
-                if (e->prio < queued->prio) {
-                        VTRACE("Inserting priority %d event 0x%p before %d 0x%p "
-                               "in 0x%p, pos 0x%p\n", e->prio, e,
-                               queued->prio, &queued->events_node, el, pos);
-                        BUG_ON(!list_empty(&e->events_node));
-                        list_add_tail(&e->events_node, pos);
-                        return;
+                        raw_spin_lock(queue_lock);
                 }
         }
-        VTRACE("Inserting  priority %d event 0x%p at end of 0x%p, last 0x%p\n",
-               e->prio, e, el, last);
-        BUG_ON(!list_empty(&e->events_node));
-        list_add(&e->events_node, (last) ? last : pos);
+        raw_spin_unlock(queue_lock);
+
+        VTRACE("Exhausted %d events from list 0x%x\n", num, el);
+        return HRTIMER_NORESTART;
 }
 
 /*
@@ -111,7 +95,7 @@ static struct event_list* get_event_list(struct event_group *group,
         unsigned int slot = time2slot(fire);
         int remaining = 300;
 
-        VTRACE("Getting list for time %llu, event 0x%p\n", fire, e);
+        VTRACE("Getting list for time %llu, event 0x%x\n", fire, e);
 
         /* Initialize pos for the case that the list is empty */
         pos = group->event_queue[slot].next;
@@ -120,7 +104,7 @@ static struct event_list* get_event_list(struct event_group *group,
                 tmp = list_entry(pos, struct event_list, queue_node);
                 if (lt_after_eq(fire, tmp->fire_time) &&
                     lt_before(fire, tmp->fire_time + group->res)) {
-                        VTRACE("Found match 0x%p at time %llu\n",
+                        VTRACE("Found match 0x%x at time %llu\n",
                                tmp, tmp->fire_time);
                         el = tmp;
                         break;
@@ -142,7 +126,7 @@ static struct event_list* get_event_list(struct event_group *group,
                 tmp->fire_time = fire;
                 tmp->group = group;
                 /* Add to queue */
-                VTRACE("Using list 0x%p for priority %d and time %llu\n",
+                VTRACE("Using list 0x%x for priority %d and time %llu\n",
                        tmp, e->prio, fire);
                 BUG_ON(!list_empty(&tmp->queue_node));
                 list_add(&tmp->queue_node, pos->prev);
@@ -154,18 +138,23 @@ static struct event_list* get_event_list(struct event_group *group,
 /*
  * Prepare a release list for a new set of events.
  */
-static void reinit_event_list(struct rt_event *e)
+static void reinit_event_list(struct event_group *group, struct rt_event *e)
 {
+        int prio, t_ret;
         struct event_list *el = e->event_list;
-        int ret;
-        VTRACE("Reinitting list 0x%p for event 0x%p\n", el, e);
-        ret = hrtimer_try_to_cancel(&el->timer);
-        BUG_ON(ret == 1);
-        if (ret == -1) {
+
+        VTRACE("Reinitting list 0x%x for event 0x%x\n", el, e);
+
+        /* Cancel timer */
+        t_ret = hrtimer_pull_cancel(group->cpu, &el->timer, &el->info);
+        BUG_ON(t_ret == 1);
+        if (t_ret == -1) {
+                /* The on_timer callback is running for this list */
                 VTRACE("Timer is running concurrently!\n");
         }
-        INIT_LIST_HEAD(&el->events);
-        atomic_set(&el->info.state, HRTIMER_START_ON_INACTIVE);
+        /* Clear event lists */
+        for (prio = 0; prio < NUM_EVENT_PRIORITIES; prio++)
+                INIT_LIST_HEAD(&el->events[prio]);
 }
 
 /**
@@ -176,7 +165,7 @@ void add_event(struct event_group *group, struct rt_event *e, lt_t fire)
         struct event_list *el;
         int in_use;
 
-        VTRACE("Adding event 0x%p with priority %d for time %llu\n",
+        VTRACE("Adding event 0x%x with priority %d for time %llu\n",
                e, e->prio, fire);
 
         /* A NULL group means use the group of the currently executing CPU  */
@@ -190,18 +179,19 @@ void add_event(struct event_group *group, struct rt_event *e, lt_t fire)
         if (!el) {
                 /* Use our own, but drop lock first */
                 raw_spin_unlock(&group->queue_lock);
-                reinit_event_list(e);
+                reinit_event_list(group, e);
                 raw_spin_lock(&group->queue_lock);
                 el = get_event_list(group, e, fire, 1);
         }
 
         /* Add event to sorted list */
-        insert_event(el, e);
+        VTRACE("Inserting event 0x%x at end of event_list 0x%x\n", e, el);
+        list_add(&e->events_node, &el->events[e->prio]);
         raw_spin_unlock(&group->queue_lock);
 
         /* Arm timer if we are the owner */
         if (el == e->event_list) {
-                VTRACE("Arming timer on event 0x%p for %llu\n", e, fire);
+                VTRACE("Arming timer on event 0x%x for %llu\n", e, fire);
                 in_use = hrtimer_start_on(group->cpu, &el->info,
                                           &el->timer, ns_to_ktime(el->fire_time),
                                           HRTIMER_MODE_ABS_PINNED);
@@ -216,56 +206,73 @@ void add_event(struct event_group *group, struct rt_event *e, lt_t fire)
  */
 void cancel_event(struct rt_event *e)
 {
-        struct rt_event *swap;
+        int prio, cancel;
+        struct rt_event *swap, *entry;
         struct event_list *tmp;
-        struct event_group *group = e->_event_group;
+        struct event_group *group;
+        struct list_head *list, *pos;
 
-        VTRACE("Canceling event 0x%p with priority %d\n", e, e->prio);
+        VTRACE("Canceling event 0x%x with priority %d\n", e, e->prio);
+        group = e->_event_group;
         if (!group) return;
 
-        /* If our event_list contains any events, it is in use */
         raw_spin_lock(&group->queue_lock);
-        if (!list_empty(&e->event_list->events)) {
-                VTRACE("List 0x%p is not empty\n", e->event_list);
 
-                /* If our event_list contains events, we are the first element
-                 * in that list. If there is anyone after us in the list, then
-                 * swap our list with theirs to that the event_list can still
-                 * trigger the queued events.
-                 */
-                if (!list_is_singular(&e->event_list->events)) {
-                        swap = list_entry(e->events_node.next, struct rt_event,
-                                          events_node);
-                        VTRACE("Swapping with event 0x%p of priority %d\n",
-                               swap, swap->prio);
-                        tmp = swap->event_list;
-                        swap->event_list = e->event_list;
-                        e->event_list = tmp;
+        /* Relies on the fact that an event_list's owner is ALWAYS present
+         * as one of the event_list's events.
+         */
+        for (prio = 0, cancel = 0, swap = NULL;
+             prio < NUM_EVENT_PRIORITIES && !swap;
+             prio++) {
+
+                list = &e->event_list->events[prio];
+                cancel |= !list_empty(list);
+
+                /* Find any element which is not the event_list's owner */
+                list_for_each(pos, list) {
+                        entry = list_entry(pos, struct rt_event, events_node);
+                        if (entry != e) {
+                                swap = entry;
+                                break;
+                        }
                 }
+        }
 
-                /* Disable the event_list */
+        if (swap) {
+                /* Give the other guy ownership of the event_list */
+                VTRACE("Swapping list 0x%x with event 0x%x event list 0x%x\n",
+                       e->event_list, swap, swap->event_list);
+                tmp = swap->event_list;
+                swap->event_list = e->event_list;
+                BUG_ON(!tmp);
+                e->event_list = tmp;
+        } else if (cancel) {
+                /* Cancel the event_list we own */
                 hrtimer_pull_cancel(group->cpu,
                                     &e->event_list->timer,
                                     &e->event_list->info);
                 list_del_init(&e->event_list->queue_node);
-        } else {
-                VTRACE("List 0x%p is empty\n", e->event_list);
         }
+        /* Remove ourselves from any list we may be a part of */
         list_del_init(&e->events_node);
-        raw_spin_unlock(&group->queue_lock);
         e->_event_group = NULL;
+
+        raw_spin_unlock(&group->queue_lock);
 }
 
 struct kmem_cache *event_list_cache;
 
 struct event_list* event_list_alloc(int gfp_flags)
 {
+        int prio;
         struct event_list *el = kmem_cache_alloc(event_list_cache, gfp_flags);
         if (el) {
                 hrtimer_init(&el->timer, CLOCK_MONOTONIC, HRTIMER_MODE_ABS);
                 INIT_LIST_HEAD(&el->queue_node);
                 el->timer.function = on_timer;
                 hrtimer_start_on_info_init(&el->info);
+                for (prio = 0; prio < NUM_EVENT_PRIORITIES; prio++)
+                        INIT_LIST_HEAD(&el->events[prio]);
         } else {
                 VTRACE("Failed to allocate event list!\n");
                 printk(KERN_CRIT "Failed to allocate event list.\n");
diff --git a/litmus/sched_mc.c b/litmus/sched_mc.c
index 1d1ecbb8c9c4..5067b79b026b 100644
--- a/litmus/sched_mc.c
+++ b/litmus/sched_mc.c
@@ -987,8 +987,8 @@ void mc_finish_switch(struct task_struct *prev)
 {
         struct cpu_entry* entry = &__get_cpu_var(cpus);
         entry->scheduled = is_realtime(current) ? current : NULL;
-        TRACE_TASK(prev, "Switched away from to (something/%d)\n",
-                   ((entry->scheduled) ? entry->scheduled->pid : 0));
+        TRACE_TASK(prev, "Switched away from to " TS,
+                   TA(entry->scheduled));
 }
 
 /*