|
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] RE: [Xen-devel] [PATCH 0/2] range timer support
Keir Fraser wrote:
> On 31/10/08 07:50, "Yu, Ke" <ke.yu@xxxxxxxxx> wrote:
>
>> I see. Then I will start to revise the range timer patch as follow:
>> - remove the TIMER_SLOP macro
>> - add "global timer slop" xen option, and make set_timer to use the
>> global slop.
>> - remove the set_range_timer API, since it is not easy to use
>> currently
>
> Sounds reasonable.
>
> -- Keir
This is the updated range timer patch. I have done basic test on 50ns and 1ms
timer slop, both looks fine.
Best Regards
Ke
===========================
Add range timer support
this patch convert the timer into range timer, which can expires at any time
within the range. A configurable global timer slop is introduced to config the
timer's default range as [deadline, deadline + timer_slop].
Signed-off-by: Yu Ke <ke.yu@xxxxxxxxx>
Wei Gang <gang.wei@xxxxxxxxx>
diff -r bec755616e8e 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 bec755616e8e xen/common/timer.c
--- a/xen/common/timer.c
+++ b/xen/common/timer.c
@@ -25,13 +25,15 @@
* 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 ns */
+integer_param("timer_slop", timer_slop);
struct timers {
spinlock_t lock;
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 +87,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 +206,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 +234,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,7 +293,7 @@ static inline void timer_unlock(struct t
#define timer_unlock_irqrestore(t, flags) \
do { timer_unlock(t); local_irq_restore(flags); } while ( 0 )
-
+/* Set timer that can expire in period [expires, expires + timer_slop] */
void set_timer(struct timer *timer, s_time_t expires)
{
unsigned long flags;
@@ -257,14 +303,14 @@ 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 + timer_slop;
if ( likely(timer->status != TIMER_STATUS_killed) )
__add_timer(timer);
timer_unlock_irqrestore(timer, flags);
}
-
void stop_timer(struct timer *timer)
{
@@ -343,54 +389,92 @@ 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;
+}
+
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 )
+ {
+ 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)) )
+ ((t = heap[1])->expires < now ) )
{
remove_entry(ts, t);
@@ -404,16 +488,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;
+ if ( t->expires >= now )
break;
- }
ts->list = t->list_next;
t->status = TIMER_STATUS_inactive;
@@ -430,8 +508,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 bec755616e8e 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 bec755616e8e 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;
};
Attachment:
range-timer.patch _______________________________________________ Xen-devel mailing list Xen-devel@xxxxxxxxxxxxxxxxxxx http://lists.xensource.com/xen-devel
|
 |
Lists.xenproject.org is hosted with RackSpace, monitoring our |