diff options
author | kaf24@scramble.cl.cam.ac.uk <kaf24@scramble.cl.cam.ac.uk> | 2003-10-10 09:31:49 +0000 |
---|---|---|
committer | kaf24@scramble.cl.cam.ac.uk <kaf24@scramble.cl.cam.ac.uk> | 2003-10-10 09:31:49 +0000 |
commit | f5ecfd754290ed8ca28da55530886af4d86aeaef (patch) | |
tree | 838f9e000e06d0c596aafce3f21411b48d8e3a2c | |
parent | 3fbfd4aa46c75af08a04570a0d8f7e3599362fcf (diff) | |
download | xen-f5ecfd754290ed8ca28da55530886af4d86aeaef.tar.gz xen-f5ecfd754290ed8ca28da55530886af4d86aeaef.tar.bz2 xen-f5ecfd754290ed8ca28da55530886af4d86aeaef.zip |
bitkeeper revision 1.499 (3f867c85oOyUdtcboCzrLgktKtvdgA)
ac_timer.h, ac_timer.c:
Xen ac timers now use a heap to find earliest timeout.
-rw-r--r-- | xen/common/ac_timer.c | 317 | ||||
-rw-r--r-- | xen/include/xeno/ac_timer.h | 8 |
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 */ |