# HG changeset patch
# User Keir Fraser <keir.fraser@xxxxxxxxxx>
# Date 1219839875 -3600
# Node ID 070688cdf62c7a1ed78404e5277ece18a9b88364
# Parent 6c6bda7f09cde36fa875941d7202e77620fdc687
Fall back to a timer linked list when the timer heap overflows.
Signed-off-by: Keir Fraser <keir.fraser@xxxxxxxxxx>
---
xen/common/timer.c | 177 ++++++++++++++++++++++++++++++++++++++----------
xen/include/xen/timer.h | 33 ++++++--
2 files changed, 165 insertions(+), 45 deletions(-)
diff -r 6c6bda7f09cd -r 070688cdf62c xen/common/timer.c
--- a/xen/common/timer.c Wed Aug 27 11:47:02 2008 +0100
+++ b/xen/common/timer.c Wed Aug 27 13:24:35 2008 +0100
@@ -30,6 +30,7 @@ struct timers {
struct timers {
spinlock_t lock;
struct timer **heap;
+ struct timer *list;
struct timer *running;
} __cacheline_aligned;
@@ -86,12 +87,10 @@ static void up_heap(struct timer **heap,
/* Delete @t from @heap. Return TRUE if new top of heap. */
-static int remove_entry(struct timer **heap, struct timer *t)
+static int remove_from_heap(struct timer **heap, struct timer *t)
{
int sz = GET_HEAP_SIZE(heap);
int pos = t->heap_offset;
-
- t->heap_offset = 0;
if ( unlikely(pos == sz) )
{
@@ -115,7 +114,7 @@ static int remove_entry(struct timer **h
/* Add new entry @t to @heap. Return TRUE if new top of heap. */
-static int add_entry(struct timer ***pheap, struct timer *t)
+static int add_to_heap(struct timer ***pheap, struct timer *t)
{
struct timer **heap = *pheap;
int sz = GET_HEAP_SIZE(heap);
@@ -126,8 +125,11 @@ static int add_entry(struct timer ***phe
/* 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;
+ if ( in_irq() )
+ goto out;
heap = xmalloc_array(struct timer *, new_limit + 1);
- BUG_ON(heap == NULL);
+ if ( heap == NULL )
+ goto out;
memcpy(heap, *pheap, (old_limit + 1) * sizeof(*heap));
SET_HEAP_LIMIT(heap, new_limit);
if ( old_limit != 0 )
@@ -139,7 +141,38 @@ static int add_entry(struct timer ***phe
heap[sz] = t;
t->heap_offset = sz;
up_heap(heap, sz);
+ out:
return (t->heap_offset == 1);
+}
+
+
+/****************************************************************************
+ * LINKED LIST OPERATIONS.
+ */
+
+static int remove_from_list(struct timer **pprev, struct timer *t)
+{
+ struct timer *curr, **_pprev = pprev;
+
+ while ( (curr = *_pprev) != t )
+ _pprev = &curr->list_next;
+
+ *_pprev = t->list_next;
+
+ return (_pprev == pprev);
+}
+
+static int add_to_list(struct timer **pprev, struct timer *t)
+{
+ struct timer *curr, **_pprev = pprev;
+
+ while ( ((curr = *_pprev) != NULL) && (curr->expires <= t->expires) )
+ _pprev = &curr->list_next;
+
+ t->list_next = curr;
+ *_pprev = t;
+
+ return (_pprev == pprev);
}
@@ -147,18 +180,56 @@ static int add_entry(struct timer ***phe
* TIMER OPERATIONS.
*/
+static int remove_entry(struct timers *timers, struct timer *t)
+{
+ int rc;
+
+ switch ( t->status )
+ {
+ case TIMER_STATUS_in_heap:
+ rc = remove_from_heap(timers->heap, t);
+ break;
+ case TIMER_STATUS_in_list:
+ rc = remove_from_list(&timers->list, t);
+ break;
+ default:
+ rc = 0;
+ BUG();
+ }
+
+ t->status = TIMER_STATUS_inactive;
+ return rc;
+}
+
+static int add_entry(struct timers *timers, struct timer *t)
+{
+ int rc;
+
+ ASSERT(t->status == TIMER_STATUS_inactive);
+
+ /* Try to add to heap. t->heap_offset indicates whether we succeed. */
+ t->heap_offset = 0;
+ t->status = TIMER_STATUS_in_heap;
+ rc = add_to_heap(&timers->heap, t);
+ if ( t->heap_offset != 0 )
+ return rc;
+
+ /* Fall back to adding to the slower linked list. */
+ t->status = TIMER_STATUS_in_list;
+ return add_to_list(&timers->list, t);
+}
+
static inline void __add_timer(struct timer *timer)
{
int cpu = timer->cpu;
- if ( add_entry(&per_cpu(timers, cpu).heap, timer) )
+ if ( add_entry(&per_cpu(timers, cpu), timer) )
cpu_raise_softirq(cpu, TIMER_SOFTIRQ);
}
-
static inline void __stop_timer(struct timer *timer)
{
int cpu = timer->cpu;
- if ( remove_entry(per_cpu(timers, cpu).heap, timer) )
+ if ( remove_entry(&per_cpu(timers, cpu), timer) )
cpu_raise_softirq(cpu, TIMER_SOFTIRQ);
}
@@ -203,7 +274,7 @@ void set_timer(struct timer *timer, s_ti
timer->expires = expires;
- if ( likely(!timer->killed) )
+ if ( likely(timer->status != TIMER_STATUS_killed) )
__add_timer(timer);
timer_unlock_irqrestore(timer, flags);
@@ -278,7 +349,7 @@ void kill_timer(struct timer *timer)
if ( active_timer(timer) )
__stop_timer(timer);
- timer->killed = 1;
+ timer->status = TIMER_STATUS_killed;
timer_unlock_irqrestore(timer, flags);
@@ -290,43 +361,76 @@ void kill_timer(struct timer *timer)
static void timer_softirq_action(void)
{
- struct timer *t, **heap;
+ struct timer *t, **heap, *next;
struct timers *ts;
- s_time_t now;
+ s_time_t now, deadline;
void (*fn)(void *);
void *data;
ts = &this_cpu(timers);
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);
+ }
- do {
+ heap = ts->heap;
+ 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);
+
+ /* Heap may have grown while the lock was released. */
heap = ts->heap;
- now = NOW();
-
- while ( (GET_HEAP_SIZE(heap) != 0) &&
- ((t = heap[1])->expires < (now + TIMER_SLOP)) )
+ }
+
+ deadline = GET_HEAP_SIZE(heap) ? heap[1]->expires : 0;
+
+ while ( unlikely((t = ts->list) != NULL) )
+ {
+ if ( t->expires >= (now + TIMER_SLOP) )
{
- remove_entry(heap, t);
-
- ts->running = t;
-
- fn = t->function;
- data = t->data;
-
- spin_unlock_irq(&ts->lock);
- (*fn)(data);
- spin_lock_irq(&ts->lock);
-
- /* Heap may have grown while the lock was released. */
- heap = ts->heap;
+ if ( (deadline == 0) || (deadline > t->expires) )
+ deadline = t->expires;
+ break;
}
- ts->running = NULL;
-
- this_cpu(timer_deadline) = GET_HEAP_SIZE(heap) ? heap[1]->expires : 0;
- }
- while ( !reprogram_timer(this_cpu(timer_deadline)) );
+ 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) )
+ raise_softirq(TIMER_SOFTIRQ);
spin_unlock_irq(&ts->lock);
}
@@ -364,6 +468,9 @@ static void dump_timerq(unsigned char ke
printk (" %d : %p ex=0x%08X%08X %p\n",
j, t, (u32)(t->expires>>32), (u32)t->expires, t->data);
}
+ for ( t = ts->list, j = 0; t != NULL; t = t->list_next, j++ )
+ printk (" L%d : %p ex=0x%08X%08X %p\n",
+ j, t, (u32)(t->expires>>32), (u32)t->expires, t->data);
spin_unlock_irqrestore(&ts->lock, flags);
printk("\n");
}
diff -r 6c6bda7f09cd -r 070688cdf62c xen/include/xen/timer.h
--- a/xen/include/xen/timer.h Wed Aug 27 11:47:02 2008 +0100
+++ b/xen/include/xen/timer.h Wed Aug 27 13:24:35 2008 +0100
@@ -14,16 +14,29 @@
struct timer {
/* System time expiry value (nanoseconds since boot). */
- s_time_t expires;
+ s_time_t expires;
+
+ /* Position in active-timer data structure. */
+ union {
+ /* Timer-heap offset. */
+ unsigned int heap_offset;
+ /* Overflow linked list. */
+ struct timer *list_next;
+ };
+
+ /* On expiry, '(*function)(data)' will be executed in softirq context. */
+ void (*function)(void *);
+ void *data;
+
/* CPU on which this timer will be installed and executed. */
- unsigned int cpu;
- /* On expiry, '(*function)(data)' will be executed in softirq context. */
- void (*function)(void *);
- void *data;
- /* Timer-heap offset. */
- unsigned int heap_offset;
- /* Has this timer been killed (cannot be activated)? */
- int killed;
+ uint16_t cpu;
+
+ /* Timer status. */
+#define TIMER_STATUS_inactive 0 /* Not in use; can be activated. */
+#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. */
+ uint8_t status;
};
/*
@@ -37,7 +50,7 @@ struct timer {
*/
static inline int active_timer(struct timer *timer)
{
- return (timer->heap_offset != 0);
+ return (timer->status >= TIMER_STATUS_in_heap);
}
/*
_______________________________________________
Xen-changelog mailing list
Xen-changelog@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-changelog
|
Home