Add range timer support
As Xen introduce the C state support, it become important to optimize the C
state residency. The key point to the optimization is reducing the breaking
events. Since timer interrupt is the major part of the breaking event, this
patch is the first step to reduce the timer interrupts.
The basic idea of this patch is that certain timer does not require to stick to
one exact firing point, instead, it is fine with firing period, e.g. period [a,
b]. With the firing period introduced, it is possible to group multiple ac
timers, whose firing periods has non-null period intersection. for example,
suppose ac timer x, y has firing period [a1, b1], [a2, b2], and [a1,b1]^[a2,b2]
= [a3,b3] (where ^ stands for set intersection). in this case, xen can group ac
timer x and y, and fire them at any time in [a3,b3], this in turn will reduce
the timer interrupt. And this type of ac timer is called range timer.
This patch adds new ac timer API set_range_timer for the range timer.
Signed-off-by: Yu Ke <ke.yu@intel.com>
Wei Gang <gang.wei@intel.com>
diff -r 874d0d673ecb xen/arch/x86/hpet.c
--- a/xen/arch/x86/hpet.c
+++ b/xen/arch/x86/hpet.c
@@ -13,8 +13,6 @@
#include <asm/fixmap.h>
#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 874d0d673ecb xen/common/timer.c
--- a/xen/common/timer.c
+++ b/xen/common/timer.c
@@ -32,6 +32,7 @@ struct timers {
struct timer **heap;
struct timer *list;
struct timer *running;
+ struct timer *ready_list; /* ready timers for next fire */
} __cacheline_aligned;
static DEFINE_PER_CPU(struct timers, timers);
@@ -85,6 +86,33 @@ static void up_heap(struct timer **heap,
t->heap_offset = pos;
}
+/* Grow heap memory. Return the allocated heap, NULL if failed */
+static struct timer** grow_heap(struct timers *ts)
+{
+ int old_limit, new_limit;
+ struct timer **heap, **newheap;
+
+ heap = ts->heap;
+
+ /* old_limit == (2^n)-1; new_limit == (2^(n+4))-1 */
+ old_limit = GET_HEAP_LIMIT(heap);
+ new_limit = ((old_limit + 1) << 4) - 1;
+
+ newheap = xmalloc_array(struct timer *, new_limit + 1);
+
+ if ( newheap != NULL )
+ {
+ spin_lock_irq(&ts->lock);
+ memcpy(newheap, heap, (old_limit + 1) * sizeof(*heap));
+ SET_HEAP_LIMIT(newheap, new_limit);
+ ts->heap = newheap;
+ spin_unlock_irq(&ts->lock);
+ if ( old_limit != 0 )
+ xfree(heap);
+ }
+
+ return newheap;
+}
/* Delete @t from @heap. Return TRUE if new top of heap. */
static int remove_from_heap(struct timer **heap, struct timer *t)
@@ -177,6 +205,9 @@ static int remove_entry(struct timers *t
case TIMER_STATUS_in_list:
rc = remove_from_list(&timers->list, t);
break;
+ case TIMER_STATUS_in_ready_list:
+ rc = remove_from_list(&timers->ready_list, t);
+ break;
default:
rc = 0;
BUG();
@@ -202,6 +233,20 @@ static int add_entry(struct timers *time
/* Fall back to adding to the slower linked list. */
t->status = TIMER_STATUS_in_list;
return add_to_list(&timers->list, t);
+}
+
+static void move_list_to_heap(struct timers *ts, struct timer **list)
+{
+ struct timer *t, *next;
+
+ next = *list;
+ *list = NULL;
+ while ( (t = next) != NULL )
+ {
+ next = t->list_next;
+ t->status = TIMER_STATUS_inactive;
+ add_entry(ts, t);
+ }
}
static inline void __add_timer(struct timer *timer)
@@ -247,8 +292,8 @@ static inline void timer_unlock(struct t
#define timer_unlock_irqrestore(t, flags) \
do { timer_unlock(t); local_irq_restore(flags); } while ( 0 )
-
-void set_timer(struct timer *timer, s_time_t expires)
+/* Set timer that can expire in period [expires, expires_end] */
+void set_range_timer(struct timer *timer, s_time_t expires, s_time_t
expires_end)
{
unsigned long flags;
@@ -257,7 +302,8 @@ void set_timer(struct timer *timer, s_ti
if ( active_timer(timer) )
__stop_timer(timer);
- timer->expires = expires;
+ timer->expires = expires;
+ timer->expires_end = expires_end;
if ( likely(timer->status != TIMER_STATUS_killed) )
__add_timer(timer);
@@ -265,6 +311,10 @@ void set_timer(struct timer *timer, s_ti
timer_unlock_irqrestore(timer, flags);
}
+void set_timer(struct timer *timer, s_time_t expires)
+{
+ set_range_timer(timer, expires, expires);
+}
void stop_timer(struct timer *timer)
{
@@ -343,51 +393,89 @@ void kill_timer(struct timer *timer)
cpu_relax();
}
+static void queue_ready_timer(struct timers* ts)
+{
+ struct timer *t, **heap;
+ s_time_t start, end;
+
+ if ( unlikely (ts->ready_list != NULL) )
+ move_list_to_heap(ts, &ts->ready_list);
+
+ while ( unlikely (ts->list != NULL) )
+ {
+ spin_unlock_irq(&ts->lock);
+ if ( unlikely (grow_heap(ts) == NULL) )
+ {
+ printk(XENLOG_ERR "timer heap grow failed\n");
+ spin_lock_irq(&ts->lock);
+ break;
+ }
+ spin_lock_irq(&ts->lock);
+
+ move_list_to_heap(ts, &ts->list);
+ }
+
+ heap = ts->heap;
+ start = 0;
+ end = STIME_MAX;
+
+ while ( (GET_HEAP_SIZE(heap) != 0) &&
+ ((t = heap[1])->expires <= end) )
+ {
+ remove_from_heap(heap, t);
+
+ start = t->expires;
+ if ( end > t->expires_end)
+ end = t->expires_end;
+
+ t->list_next = ts->ready_list;
+ ts->ready_list = t;
+ t->status = TIMER_STATUS_in_ready_list;
+ }
+ this_cpu(timer_deadline) = (start + end) / 2;
+}
+
static void timer_softirq_action(void)
{
- struct timer *t, **heap, *next;
+ struct timer *t, **heap;
struct timers *ts;
- s_time_t now, deadline;
+ s_time_t now;
void (*fn)(void *);
void *data;
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) )
- {
- /* old_limit == (2^n)-1; new_limit == (2^(n+4))-1 */
- int old_limit = GET_HEAP_LIMIT(heap);
- int new_limit = ((old_limit + 1) << 4) - 1;
- struct timer **newheap = xmalloc_array(struct timer *, new_limit + 1);
- if ( newheap != NULL )
- {
- spin_lock_irq(&ts->lock);
- memcpy(newheap, heap, (old_limit + 1) * sizeof(*heap));
- SET_HEAP_LIMIT(newheap, new_limit);
- ts->heap = newheap;
- spin_unlock_irq(&ts->lock);
- if ( old_limit != 0 )
- xfree(heap);
- heap = newheap;
- }
- }
+ grow_heap(ts);
+ heap = ts->heap;
spin_lock_irq(&ts->lock);
/* Try to move timers from overflow linked list to more efficient heap. */
- next = ts->list;
- ts->list = NULL;
- while ( unlikely((t = next) != NULL) )
- {
- next = t->list_next;
- t->status = TIMER_STATUS_inactive;
- add_entry(ts, t);
- }
+ move_list_to_heap (ts, &ts->list);
now = NOW();
+
+ /* Execute ready timer first */
+ if ( this_cpu(timer_deadline) < now + TIMER_SLOP )
+ {
+ while ( likely((t = ts->ready_list)!= NULL) )
+ {
+ fn = t->function;
+ data = t->data;
+
+ ts->ready_list = t->list_next;
+ t->status = TIMER_STATUS_inactive;
+
+ ts->running = t;
+
+ spin_unlock_irq(&ts->lock);
+ (*fn)(data);
+ spin_lock_irq(&ts->lock);
+ }
+ }
while ( (GET_HEAP_SIZE(heap) != 0) &&
((t = heap[1])->expires < (now + TIMER_SLOP)) )
@@ -404,16 +492,10 @@ static void timer_softirq_action(void)
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) )
- {
- if ( (deadline == 0) || (deadline > t->expires) )
- deadline = t->expires;
break;
- }
ts->list = t->list_next;
t->status = TIMER_STATUS_inactive;
@@ -430,8 +512,8 @@ static void timer_softirq_action(void)
ts->running = NULL;
- this_cpu(timer_deadline) = deadline;
- if ( !reprogram_timer(deadline) )
+ queue_ready_timer(ts);
+ if ( !reprogram_timer(this_cpu(timer_deadline)) )
raise_softirq(TIMER_SOFTIRQ);
spin_unlock_irq(&ts->lock);
diff -r 874d0d673ecb xen/include/xen/time.h
--- a/xen/include/xen/time.h
+++ b/xen/include/xen/time.h
@@ -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 874d0d673ecb xen/include/xen/timer.h
--- a/xen/include/xen/timer.h
+++ b/xen/include/xen/timer.h
@@ -15,6 +15,7 @@ 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 {
@@ -36,6 +37,7 @@ struct timer {
#define TIMER_STATUS_killed 1 /* Not in use; canot be activated. */
#define TIMER_STATUS_in_heap 2 /* In use; on timer heap. */
#define TIMER_STATUS_in_list 3 /* In use; on overflow linked list. */
+#define TIMER_STATUS_in_ready_list 4 /* In use; on ready linked list. */
uint8_t status;
};
@@ -76,6 +78,9 @@ static inline void init_timer(
* been initialised by init_timer() (so that callback details are known).
*/
extern void set_timer(struct timer *timer, s_time_t expires);
+
+/* Set timer that can expire in period [start, end] */
+extern void set_range_timer(struct timer *timer, s_time_t start, s_time_t end);
/*
* Deactivate a timer This function has no effect if the timer is not currently
_______________________________________________
Xen-devel mailing list
Xen-devel@lists.xensource.com
http://lists.xensource.com/xen-devel