[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Xen-changelog] [xen-unstable] Change timer implementation to allow variable 'slop' in how late



# HG changeset patch
# User Keir Fraser <keir.fraser@xxxxxxxxxx>
# Date 1225461759 0
# Node ID f12d9595d07ceaa1b624a3e91774a3591f2cfc8c
# Parent  85ba96069dfb3edf180656991aafa6cc8e368773
Change timer implementation to allow variable 'slop' in how late
timers are fired. The default continues to be 50us, but this can be
configured on Xen's command line.

Signed-off-by: Yu Ke <ke.yu@xxxxxxxxx>
Signed-off-by: Wei Gang <gang.wei@xxxxxxxxx>
Signed-off-by: Keir Fraser <keir.fraser@xxxxxxxxxx>
---
 xen/arch/x86/hpet.c     |    2 
 xen/common/timer.c      |  125 +++++++++++++++++++++++++++++-------------------
 xen/include/xen/time.h  |    1 
 xen/include/xen/timer.h |    3 -
 4 files changed, 79 insertions(+), 52 deletions(-)

diff -r 85ba96069dfb -r f12d9595d07c xen/arch/x86/hpet.c
--- a/xen/arch/x86/hpet.c       Thu Oct 30 15:04:27 2008 +0000
+++ b/xen/arch/x86/hpet.c       Fri Oct 31 14:02:39 2008 +0000
@@ -14,8 +14,6 @@
 #include <asm/div64.h>
 #include <asm/hpet.h>
 
-#define STIME_MAX ((s_time_t)((uint64_t)~0ull>>1))
-
 #define MAX_DELTA_NS MILLISECS(10*1000)
 #define MIN_DELTA_NS MICROSECS(20)
 
diff -r 85ba96069dfb -r f12d9595d07c xen/common/timer.c
--- a/xen/common/timer.c        Thu Oct 30 15:04:27 2008 +0000
+++ b/xen/common/timer.c        Fri Oct 31 14:02:39 2008 +0000
@@ -25,10 +25,12 @@
  * We pull handlers off the timer list this far in future,
  * rather than reprogramming the time hardware.
  */
-#define TIMER_SLOP (50*1000) /* ns */
+static unsigned int timer_slop __read_mostly = 50000; /* 50 us */
+integer_param("timer_slop", timer_slop);
 
 struct timers {
     spinlock_t     lock;
+    bool_t         overflow;
     struct timer **heap;
     struct timer  *list;
     struct timer  *running;
@@ -200,6 +202,7 @@ static int add_entry(struct timers *time
         return rc;
 
     /* Fall back to adding to the slower linked list. */
+    timers->overflow = 1;
     t->status = TIMER_STATUS_in_list;
     return add_to_list(&timers->list, t);
 }
@@ -258,6 +261,7 @@ void set_timer(struct timer *timer, s_ti
         __stop_timer(timer);
 
     timer->expires = expires;
+    timer->expires_end = expires + timer_slop;
 
     if ( likely(timer->status != TIMER_STATUS_killed) )
         __add_timer(timer);
@@ -344,19 +348,30 @@ void kill_timer(struct timer *timer)
 }
 
 
+static void execute_timer(struct timers *ts, struct timer *t)
+{
+    void (*fn)(void *) = t->function;
+    void *data = t->data;
+
+    ts->running = t;
+    spin_unlock_irq(&ts->lock);
+    (*fn)(data);
+    spin_lock_irq(&ts->lock);
+    ts->running = NULL;
+}
+
+
 static void timer_softirq_action(void)
 {
     struct timer  *t, **heap, *next;
     struct timers *ts;
-    s_time_t       now, deadline;
-    void         (*fn)(void *);
-    void          *data;
+    s_time_t       now;
 
     ts = &this_cpu(timers);
     heap = ts->heap;
 
-    /* If we are using overflow linked list, try to allocate a larger heap. */
-    if ( unlikely(ts->list != NULL) )
+    /* If we overflowed the heap, try to allocate a larger heap. */
+    if ( unlikely(ts->overflow) )
     {
         /* old_limit == (2^n)-1; new_limit == (2^(n+4))-1 */
         int old_limit = GET_HEAP_LIMIT(heap);
@@ -377,7 +392,26 @@ static void timer_softirq_action(void)
 
     spin_lock_irq(&ts->lock);
 
-    /* Try to move timers from overflow linked list to more efficient heap. */
+    now = NOW();
+
+    /* Execute ready heap timers. */
+    while ( (GET_HEAP_SIZE(heap) != 0) &&
+            ((t = heap[1])->expires_end < now) )
+    {
+        remove_from_heap(heap, t);
+        t->status = TIMER_STATUS_inactive;
+        execute_timer(ts, t);
+    }
+
+    /* Execute ready list timers. */
+    while ( ((t = ts->list) != NULL) && (t->expires_end < now) )
+    {
+        ts->list = t->list_next;
+        t->status = TIMER_STATUS_inactive;
+        execute_timer(ts, t);
+    }
+
+    /* Try to move timers from linked list to more efficient heap. */
     next = ts->list;
     ts->list = NULL;
     while ( unlikely((t = next) != NULL) )
@@ -387,51 +421,44 @@ static void timer_softirq_action(void)
         add_entry(ts, t);
     }
 
-    now = NOW();
-
-    while ( (GET_HEAP_SIZE(heap) != 0) &&
-            ((t = heap[1])->expires < (now + TIMER_SLOP)) )
-    {
-        remove_entry(ts, t);
-
-        ts->running = t;
-
-        fn   = t->function;
-        data = t->data;
-
-        spin_unlock_irq(&ts->lock);
-        (*fn)(data);
-        spin_lock_irq(&ts->lock);
-    }
-
-    deadline = GET_HEAP_SIZE(heap) ? heap[1]->expires : 0;
-
-    while ( unlikely((t = ts->list) != NULL) )
-    {
-        if ( t->expires >= (now + TIMER_SLOP) )
+    ts->overflow = (ts->list != NULL);
+    if ( unlikely(ts->overflow) )
+    {
+        /* Find earliest deadline at head of list or top of heap. */
+        this_cpu(timer_deadline) = ts->list->expires;
+        if ( (GET_HEAP_SIZE(heap) != 0) &&
+             ((t = heap[1])->expires < this_cpu(timer_deadline)) )
+            this_cpu(timer_deadline) = t->expires;
+    }
+    else
+    {
+        /*
+         * Find the earliest deadline that encompasses largest number of timers
+         * on the heap. To do this we take timers from the heap while their
+         * valid deadline ranges continue to intersect.
+         */
+        s_time_t start = 0, end = STIME_MAX;
+        struct timer **list_tail = &ts->list;
+
+        while ( (GET_HEAP_SIZE(heap) != 0) &&
+                ((t = heap[1])->expires <= end) )
         {
-            if ( (deadline == 0) || (deadline > t->expires) )
-                deadline = t->expires;
-            break;
+            remove_entry(ts, t);
+
+            t->status = TIMER_STATUS_in_list;
+            t->list_next = NULL;
+            *list_tail = t;
+            list_tail = &t->list_next;
+
+            start = t->expires;
+            if ( end > t->expires_end )
+                end = t->expires_end;
         }
 
-        ts->list = t->list_next;
-        t->status = TIMER_STATUS_inactive;
-
-        ts->running = t;
-
-        fn   = t->function;
-        data = t->data;
-
-        spin_unlock_irq(&ts->lock);
-        (*fn)(data);
-        spin_lock_irq(&ts->lock);
-    }
-
-    ts->running = NULL;
-
-    this_cpu(timer_deadline) = deadline;
-    if ( !reprogram_timer(deadline) )
+        this_cpu(timer_deadline) = start;
+    }
+
+    if ( !reprogram_timer(this_cpu(timer_deadline)) )
         raise_softirq(TIMER_SOFTIRQ);
 
     spin_unlock_irq(&ts->lock);
diff -r 85ba96069dfb -r f12d9595d07c xen/include/xen/time.h
--- a/xen/include/xen/time.h    Thu Oct 30 15:04:27 2008 +0000
+++ b/xen/include/xen/time.h    Fri Oct 31 14:02:39 2008 +0000
@@ -52,6 +52,7 @@ struct tm gmtime(unsigned long t);
 #define SECONDS(_s)     ((s_time_t)((_s)  * 1000000000ULL))
 #define MILLISECS(_ms)  ((s_time_t)((_ms) * 1000000ULL))
 #define MICROSECS(_us)  ((s_time_t)((_us) * 1000ULL))
+#define STIME_MAX ((s_time_t)((uint64_t)~0ull>>1))
 
 extern void update_vcpu_system_time(struct vcpu *v);
 extern void update_domain_wallclock_time(struct domain *d);
diff -r 85ba96069dfb -r f12d9595d07c xen/include/xen/timer.h
--- a/xen/include/xen/timer.h   Thu Oct 30 15:04:27 2008 +0000
+++ b/xen/include/xen/timer.h   Fri Oct 31 14:02:39 2008 +0000
@@ -15,12 +15,13 @@ struct timer {
 struct timer {
     /* System time expiry value (nanoseconds since boot). */
     s_time_t expires;
+    s_time_t expires_end;
 
     /* Position in active-timer data structure. */
     union {
         /* Timer-heap offset. */
         unsigned int heap_offset;
-        /* Overflow linked list. */
+        /* Linked list. */
         struct timer *list_next;
     };
 

_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog


 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.