bitkeeper revision 1.499 (3f867c85oOyUdtcboCzrLgktKtvdgA)

ac_timer.h, ac_timer.c:
  Xen ac timers now use a heap to find earliest timeout.

2 files changed, 167 insertions, 158 deletions

diff --git a/xen/common/ac_timer.c b/xen/common/ac_timer.c
index 48b0aea7b9..f4752ca3fb 100644
--- a/xen/common/ac_timer.c
+++ b/xen/common/ac_timer.c
@@ -39,58 +39,139 @@
  */
 #define TIMER_SLOP (50*1000) /* ns */
 
+#define DEFAULT_HEAP_LIMIT 127
+
 /* A timer list per CPU */
 typedef struct ac_timers_st
 {
-    spinlock_t lock;
-    struct list_head timers;
-    s_time_t    max_diff;
+    spinlock_t        lock;
+    struct ac_timer **heap;
 } __cacheline_aligned ac_timers_t;
 static ac_timers_t ac_timers[NR_CPUS];
 
 
-/*****************************************************************************
- * add a timer.
- * return value: CPU mask of remote processors to send an event to
- *****************************************************************************/
-static inline unsigned long __add_ac_timer(struct ac_timer *timer)
+/****************************************************************************
+ * HEAP OPERATIONS.
+ */
+
+#define GET_HEAP_SIZE(_h)     ((int)(((u16 *)(_h))[0]))
+#define SET_HEAP_SIZE(_h,_v)  (((u16 *)(_h))[0] = (u16)(_v))
+
+#define GET_HEAP_LIMIT(_h)    ((int)(((u16 *)(_h))[1]))
+#define SET_HEAP_LIMIT(_h,_v) (((u16 *)(_h))[1] = (u16)(_v))
+
+/* Sink down element @pos of @heap. */
+static void down_heap(struct ac_timer **heap, int pos)
 {
-    int cpu = timer->cpu;
+    int sz = GET_HEAP_SIZE(heap), nxt;
+    struct ac_timer *t = heap[pos];
 
-    /*
-     * Add timer to the list. If it gets added to the front we schedule
-     * a softirq. This will reprogram the timer, or handle the timer event
-     * immediately, depending on whether alarm is sufficiently ahead in the
-     * future.
-     */
-    if ( list_empty(&ac_timers[cpu].timers) )
+    while ( (nxt = (pos << 1)) <= sz )
     {
-        list_add(&timer->timer_list, &ac_timers[cpu].timers);
-        goto send_softirq;
-    } 
-    else 
+        if ( ((nxt+1) <= sz) && (heap[nxt+1]->expires < heap[nxt]->expires) )
+            nxt++;
+        if ( heap[nxt]->expires > t->expires )
+            break;
+        heap[pos] = heap[nxt];
+        heap[pos]->heap_offset = pos;
+        pos = nxt;
+    }
+
+    heap[pos] = t;
+    t->heap_offset = pos;
+}
+
+/* Float element @pos up @heap. */
+static void up_heap(struct ac_timer **heap, int pos)
+{
+    struct ac_timer *t = heap[pos];
+
+    while ( (pos > 1) && (t->expires < heap[pos>>1]->expires) )
     {
-        struct list_head *pos;
-        struct ac_timer  *t;
+        heap[pos] = heap[pos>>1];
+        heap[pos]->heap_offset = pos;
+        pos >>= 1;
+    }
+
+    heap[pos] = t;
+    t->heap_offset = pos;
+}
 
-        list_for_each ( pos, &ac_timers[cpu].timers )
-        {
-            t = list_entry(pos, struct ac_timer, timer_list);
-            if ( t->expires > timer->expires )
-                break;
-        }
 
-        list_add(&(timer->timer_list), pos->prev);
+/* Delete @t from @heap. Return TRUE if new top of heap. */
+static int remove_entry(struct ac_timer **heap, struct ac_timer *t)
+{
+    int sz = GET_HEAP_SIZE(heap);
+    int pos = t->heap_offset;
+
+    t->heap_offset = 0;
 
-        if ( timer->timer_list.prev == &ac_timers[cpu].timers )
-            goto send_softirq;
+    if ( unlikely(pos == sz) )
+    {
+        SET_HEAP_SIZE(heap, sz-1);
+        goto out;
     }
 
-    return 0;
+    heap[pos] = heap[sz];
+    heap[pos]->heap_offset = pos;
+
+    SET_HEAP_SIZE(heap, --sz);
+
+    if ( (pos > 1) && (heap[pos]->expires < heap[pos>>1]->expires) )
+        up_heap(heap, pos);
+    else
+        down_heap(heap, pos);
+
+ out:
+    return (pos == 1);
+}
+
+
+/* Add new entry @t to @heap. Return TRUE if new top of heap. */
+static int add_entry(struct ac_timer **heap, struct ac_timer *t)
+{
+    int sz = GET_HEAP_SIZE(heap);
+
+    /* Copy the heap if it is full. */
+    if ( unlikely(sz == GET_HEAP_LIMIT(heap)) )
+    {
+        int i, limit = (GET_HEAP_LIMIT(heap)+1) << 1;
+        struct ac_timer **new_heap = kmalloc(
+            limit * sizeof(struct ac_timer *), GFP_KERNEL);
+        if ( new_heap == NULL ) BUG();
+        memcpy(new_heap, heap, (limit>>1) * sizeof(struct ac_timer *));
+        for ( i = 0; i < smp_num_cpus; i++ )
+            if ( ac_timers[i].heap == heap )
+                ac_timers[i].heap = new_heap;
+        kfree(heap);
+        heap = new_heap;
+        SET_HEAP_LIMIT(heap, limit-1);
+    }
 
- send_softirq:
-    __cpu_raise_softirq(cpu, AC_TIMER_SOFTIRQ);
-    return (cpu != smp_processor_id()) ? 1<<cpu : 0;
+    SET_HEAP_SIZE(heap, ++sz);
+    heap[sz] = t;
+    t->heap_offset = sz;
+    up_heap(heap, sz);
+    return (t->heap_offset == 1);
+}
+
+
+/****************************************************************************
+ * TIMER OPERATIONS.
+ */
+
+static inline unsigned long __add_ac_timer(struct ac_timer *timer)
+{
+    int cpu = timer->cpu;
+    unsigned long cpu_mask = 0;
+
+    if ( add_entry(ac_timers[cpu].heap, timer) )
+    {
+        __cpu_raise_softirq(cpu, AC_TIMER_SOFTIRQ);
+        cpu_mask = (cpu != smp_processor_id()) ? 1<<cpu : 0;
+    }
+
+    return cpu_mask;
 }
 
 void add_ac_timer(struct ac_timer *timer) 
@@ -109,54 +190,18 @@ void add_ac_timer(struct ac_timer *timer)
 }
 
 
-/*****************************************************************************
- * detach a timer (no locking)
- * return values:
- *  0: success
- * -1: bogus timer
- *****************************************************************************/
-static inline void detach_ac_timer(struct ac_timer *timer)
-{  
-    TRC(printk("ACT  [%02d] detach(): \n", cpu));
-    list_del(&timer->timer_list);
-    timer->timer_list.next = NULL;
-}
-
-
-/*****************************************************************************
- * remove a timer
- * return values: CPU mask of remote processors to send an event to
- *****************************************************************************/
 static inline unsigned long __rem_ac_timer(struct ac_timer *timer)
 {
     int cpu = timer->cpu;
+    unsigned long cpu_mask = 0;
 
-    TRC(printk("ACT  [%02d] remove(): timo=%lld \n", cpu, timer->expires));
-    ASSERT(timer->timer_list.next);
-
-    detach_ac_timer(timer);
-    
-    if ( timer->timer_list.prev == &ac_timers[cpu].timers ) 
+    if ( remove_entry(ac_timers[cpu].heap, timer) )
     {
-        /* just removed the head */
-        if ( list_empty(&ac_timers[cpu].timers) ) 
-        {
-            goto send_softirq;
-        } 
-        else 
-        {
-            timer = list_entry(ac_timers[cpu].timers.next,
-                               struct ac_timer, timer_list);
-            if ( timer->expires > (NOW() + TIMER_SLOP) )
-                goto send_softirq;
-        }
+        __cpu_raise_softirq(cpu, AC_TIMER_SOFTIRQ);
+        cpu_mask = (cpu != smp_processor_id()) ? 1<<cpu : 0;
     }
 
-    return 0;
-
- send_softirq:
-    __cpu_raise_softirq(cpu, AC_TIMER_SOFTIRQ);
-    return (cpu != smp_processor_id()) ? 1<<cpu : 0;
+    return cpu_mask;
 }
 
 void rem_ac_timer(struct ac_timer *timer)
@@ -175,13 +220,6 @@ void rem_ac_timer(struct ac_timer *timer)
 }
 
 
-/*****************************************************************************
- * modify a timer, i.e., set a new timeout value
- * return value:
- *  0: sucess
- *  1: timeout error
- * -1: bogus timer
- *****************************************************************************/
 void mod_ac_timer(struct ac_timer *timer, s_time_t new_time)
 {
     int           cpu = timer->cpu;
@@ -203,35 +241,25 @@ void mod_ac_timer(struct ac_timer *timer, s_time_t new_time)
 }
 
 
-/*****************************************************************************
- * do_ac_timer
- * deal with timeouts and run the handlers
- *****************************************************************************/
 void do_ac_timer(void)
 {
     int              cpu = smp_processor_id();
     unsigned long    flags;
-    struct ac_timer  *t;
-    s_time_t diff, now = NOW();
-    long max;
+    struct ac_timer *t, **heap;
+    s_time_t         diff, now = NOW();
+    long             max;
 
     spin_lock_irqsave(&ac_timers[cpu].lock, flags);
 
  do_timer_again:
     TRC(printk("ACT  [%02d] do(): now=%lld\n", cpu, NOW()));
-        
-    /* Sanity: is the timer list empty? */
-    if ( list_empty(&ac_timers[cpu].timers) ) 
-        goto out;
 
-    /* Handle all timeouts in the near future. */
-    while ( !list_empty(&ac_timers[cpu].timers) )
-    {
-        t = list_entry(ac_timers[cpu].timers.next,struct ac_timer, timer_list);
-        if ( t->expires > (NOW() + TIMER_SLOP) ) 
-            break;
+    heap = ac_timers[cpu].heap;
 
-        ASSERT(t->cpu == cpu);
+    while ( (GET_HEAP_SIZE(heap) != 0) &&
+            ((t = heap[1])->expires < (NOW() + TIMER_SLOP)) )
+    {
+        remove_entry(heap, t);
 
         /* Do some stats collection. */
         diff = (now - t->expires);
@@ -241,31 +269,25 @@ void do_ac_timer(void)
         if ( diff > max ) 
             perfc_seta(ac_timer_max, cpu, diff);
 
-        detach_ac_timer(t);
-
         spin_unlock_irqrestore(&ac_timers[cpu].lock, flags);
         if ( t->function != NULL ) 
             t->function(t->data);
         spin_lock_irqsave(&ac_timers[cpu].lock, flags);
+
+        /* Heap may have grown while the lock was released. */
+        heap = ac_timers[cpu].heap;
     }
-        
-    /* If list not empty then reprogram timer to new head of list */
-    if ( !list_empty(&ac_timers[cpu].timers) )
+
+    if ( GET_HEAP_SIZE(heap) != 0 )
     {
-        t = list_entry(ac_timers[cpu].timers.next,struct ac_timer, timer_list);
-        TRC(printk("ACT  [%02d] do(): reprog timo=%lld\n",cpu,t->expires));
-        if ( !reprogram_ac_timer(t->expires) )
-        {
-            TRC(printk("ACT  [%02d] do(): again\n", cpu));
+        if ( !reprogram_ac_timer(heap[1]->expires) )
             goto do_timer_again;
-        }
     } 
     else 
     {
-        reprogram_ac_timer((s_time_t) 0);
+        reprogram_ac_timer(0);
     }
 
- out:
     spin_unlock_irqrestore(&ac_timers[cpu].lock, flags);
     TRC(printk("ACT  [%02d] do(): end\n", cpu));
 }
@@ -273,31 +295,29 @@ void do_ac_timer(void)
 
 static void ac_timer_softirq_action(struct softirq_action *a)
 {
-    int           cpu = smp_processor_id();
-    unsigned long flags;
-    struct ac_timer *t;
-    struct list_head *tlist;
-    int process_timer_list = 0;
+    int               cpu = smp_processor_id();
+    unsigned long     flags;
+    struct ac_timer  *t;
+    int               process_timer_list = 0;
 
     spin_lock_irqsave(&ac_timers[cpu].lock, flags);
     
-    tlist = &ac_timers[cpu].timers;
-    if ( list_empty(tlist) ) 
-    {
-        /* No deadline to program the timer with.*/
-        reprogram_ac_timer((s_time_t)0);
-    }
-    else
+    if ( GET_HEAP_SIZE(ac_timers[cpu].heap) != 0 )
     {
         /*
          * Reprogram timer with earliest deadline. If that has already passed
          * then we will process the timer list as soon as we release the lock.
          */
-        t = list_entry(tlist, struct ac_timer, timer_list);
+        t = ac_timers[cpu].heap[1];
         if ( (t->expires < (NOW() + TIMER_SLOP)) ||
              !reprogram_ac_timer(t->expires) )
             process_timer_list = 1;
     }
+    else
+    {
+        /* No deadline to program the timer with.*/
+        reprogram_ac_timer((s_time_t)0);
+    }
 
     spin_unlock_irqrestore(&ac_timers[cpu].lock, flags);
 
@@ -306,32 +326,12 @@ static void ac_timer_softirq_action(struct softirq_action *a)
 }
 
 
-static void dump_tqueue(struct list_head *queue, char *name)
-{
-    struct list_head *list;
-    int loop = 0;
-    struct ac_timer  *t;
-
-    printk ("QUEUE %s %lx   n: %lx, p: %lx\n", name,  (unsigned long)queue,
-            (unsigned long) queue->next, (unsigned long) queue->prev);
-
-    list_for_each ( list, queue ) 
-    {
-        t = list_entry(list, struct ac_timer, timer_list);
-        printk ("  %s %d : %lx ex=0x%08X%08X %lu  n: %lx, p: %lx\n",
-                name, loop++, 
-                (unsigned long)list,
-                (u32)(t->expires>>32), (u32)t->expires, t->data,
-                (unsigned long)list->next, (unsigned long)list->prev);
-    }
-}
-
-
 static void dump_timerq(u_char key, void *dev_id, struct pt_regs *regs)
 {
-    u_long   flags; 
-    s_time_t now = NOW();
-    int i;
+    struct ac_timer *t;
+    unsigned long    flags; 
+    s_time_t         now = NOW();
+    int              i, j;
 
     printk("Dumping ac_timer queues: NOW=0x%08X%08X\n",
            (u32)(now>>32), (u32)now); 
@@ -340,7 +340,12 @@ static void dump_timerq(u_char key, void *dev_id, struct pt_regs *regs)
     {
         printk("CPU[%02d] ", i);
         spin_lock_irqsave(&ac_timers[i].lock, flags);
-        dump_tqueue(&ac_timers[i].timers, "ac_time"); 
+        for ( j = 1; j <= GET_HEAP_SIZE(ac_timers[i].heap); j++ )
+        {
+            t = ac_timers[i].heap[j];
+            printk ("  %d : %p ex=0x%08X%08X %lu\n",
+                    j, t, (u32)(t->expires>>32), (u32)t->expires, t->data);
+        }
         spin_unlock_irqrestore(&ac_timers[i].lock, flags);
         printk("\n");
     }
@@ -355,9 +360,13 @@ void __init ac_timer_init(void)
 
     open_softirq(AC_TIMER_SOFTIRQ, ac_timer_softirq_action, NULL);
 
-    for (i = 0; i < NR_CPUS; i++)
+    for ( i = 0; i < smp_num_cpus; i++ )
     {
-        INIT_LIST_HEAD(&ac_timers[i].timers);
+        ac_timers[i].heap = kmalloc(
+            (DEFAULT_HEAP_LIMIT+1) * sizeof(struct ac_timer *), GFP_KERNEL);
+        if ( ac_timers[i].heap == NULL ) BUG();
+        SET_HEAP_SIZE(ac_timers[i].heap, 0);
+        SET_HEAP_LIMIT(ac_timers[i].heap, DEFAULT_HEAP_LIMIT);
         spin_lock_init(&ac_timers[i].lock);
     }
 
diff --git a/xen/include/xeno/ac_timer.h b/xen/include/xeno/ac_timer.h
index bcc5a89f83..78b380d76f 100644
--- a/xen/include/xeno/ac_timer.h
+++ b/xen/include/xeno/ac_timer.h
@@ -43,11 +43,11 @@
  */
 
 struct ac_timer {
-    struct list_head timer_list;
     s_time_t         expires;   /* system time time out value */
     unsigned long    data;
     void             (*function)(unsigned long);
-    int              cpu;
+    unsigned int     cpu;
+    unsigned int     heap_offset;
 };
 
 /* interface for "clients" */
@@ -57,12 +57,12 @@ extern void mod_ac_timer(struct ac_timer *timer, s_time_t new_time);
 static __inline__ void init_ac_timer(struct ac_timer *timer, int cpu)
 {
     timer->cpu = cpu;
-    timer->timer_list.next = NULL;
+    timer->heap_offset = 0;
 }
 /* check if ac_timer is active, i.e., on the list */
 static __inline__ int active_ac_timer(struct ac_timer *timer)
 {
-    return (timer->timer_list.next != NULL);
+    return (timer->heap_offset != 0);
 }
 
 /* interface used by programmable timer, implemented hardware dependent */