debuggers.hg

annotate xen/common/ac_timer.c @ 3658:0ef6e8e6e85d

bitkeeper revision 1.1159.212.71 (4200f0afX_JumfbEHQex6TdFENULMQ)

Merge labyrinth.cl.cam.ac.uk:/auto/groups/xeno-xenod/BK/xen-unstable.bk
into labyrinth.cl.cam.ac.uk:/auto/groups/xeno/users/iap10/xeno-clone/xen-unstable.bk
author iap10@labyrinth.cl.cam.ac.uk
date Wed Feb 02 15:24:31 2005 +0000 (2005-02-02)
parents d0353c3d3ebd beb0887c54bc
children bbe8541361dd 4294cfa9fad3
rev   line source
iap10@274 1 /* -*- Mode:C; c-basic-offset:4; tab-width:4 -*-
iap10@274 2 ****************************************************************************
kaf24@695 3 * (C) 2002-2003 - Rolf Neugebauer - Intel Research Cambridge
kaf24@695 4 * (C) 2002-2003 University of Cambridge
iap10@274 5 ****************************************************************************
iap10@274 6 *
iap10@274 7 * File: ac_timer.c
iap10@274 8 * Author: Rolf Neugebauer (neugebar@dcs.gla.ac.uk)
kaf24@695 9 * Keir Fraser (kaf24@cl.cam.ac.uk)
iap10@274 10 *
iap10@274 11 * Environment: Xen Hypervisor
iap10@274 12 * Description: Accurate timer for the Hypervisor
iap10@274 13 */
iap10@274 14
kaf24@1248 15 #include <xen/config.h>
kaf24@1248 16 #include <xen/init.h>
kaf24@1248 17 #include <xen/types.h>
kaf24@1248 18 #include <xen/errno.h>
kaf24@1248 19 #include <xen/sched.h>
kaf24@1248 20 #include <xen/lib.h>
kaf24@1248 21 #include <xen/smp.h>
kaf24@1248 22 #include <xen/perfc.h>
kaf24@1248 23 #include <xen/time.h>
kaf24@1544 24 #include <xen/softirq.h>
kaf24@1248 25 #include <xen/ac_timer.h>
kaf24@1248 26 #include <xen/keyhandler.h>
iap10@274 27 #include <asm/system.h>
iap10@274 28 #include <asm/desc.h>
iap10@274 29
kaf24@695 30 /*
iap10@274 31 * We pull handlers off the timer list this far in future,
iap10@274 32 * rather than reprogramming the time hardware.
kaf24@695 33 */
iap10@274 34 #define TIMER_SLOP (50*1000) /* ns */
iap10@274 35
kaf24@848 36 #define DEFAULT_HEAP_LIMIT 127
kaf24@848 37
iap10@274 38 /* A timer list per CPU */
iap10@274 39 typedef struct ac_timers_st
iap10@274 40 {
kaf24@848 41 spinlock_t lock;
kaf24@848 42 struct ac_timer **heap;
iap10@274 43 } __cacheline_aligned ac_timers_t;
iap10@274 44 static ac_timers_t ac_timers[NR_CPUS];
iap10@274 45
iap10@274 46
kaf24@848 47 /****************************************************************************
kaf24@848 48 * HEAP OPERATIONS.
kaf24@848 49 */
kaf24@848 50
kaf24@848 51 #define GET_HEAP_SIZE(_h) ((int)(((u16 *)(_h))[0]))
kaf24@848 52 #define SET_HEAP_SIZE(_h,_v) (((u16 *)(_h))[0] = (u16)(_v))
kaf24@848 53
kaf24@848 54 #define GET_HEAP_LIMIT(_h) ((int)(((u16 *)(_h))[1]))
kaf24@848 55 #define SET_HEAP_LIMIT(_h,_v) (((u16 *)(_h))[1] = (u16)(_v))
kaf24@848 56
kaf24@848 57 /* Sink down element @pos of @heap. */
kaf24@848 58 static void down_heap(struct ac_timer **heap, int pos)
kaf24@848 59 {
kaf24@848 60 int sz = GET_HEAP_SIZE(heap), nxt;
kaf24@848 61 struct ac_timer *t = heap[pos];
kaf24@848 62
kaf24@848 63 while ( (nxt = (pos << 1)) <= sz )
kaf24@848 64 {
kaf24@848 65 if ( ((nxt+1) <= sz) && (heap[nxt+1]->expires < heap[nxt]->expires) )
kaf24@848 66 nxt++;
kaf24@848 67 if ( heap[nxt]->expires > t->expires )
kaf24@848 68 break;
kaf24@848 69 heap[pos] = heap[nxt];
kaf24@848 70 heap[pos]->heap_offset = pos;
kaf24@848 71 pos = nxt;
kaf24@848 72 }
kaf24@848 73
kaf24@848 74 heap[pos] = t;
kaf24@848 75 t->heap_offset = pos;
kaf24@848 76 }
kaf24@848 77
kaf24@848 78 /* Float element @pos up @heap. */
kaf24@848 79 static void up_heap(struct ac_timer **heap, int pos)
kaf24@848 80 {
kaf24@848 81 struct ac_timer *t = heap[pos];
kaf24@848 82
kaf24@848 83 while ( (pos > 1) && (t->expires < heap[pos>>1]->expires) )
kaf24@848 84 {
kaf24@848 85 heap[pos] = heap[pos>>1];
kaf24@848 86 heap[pos]->heap_offset = pos;
kaf24@848 87 pos >>= 1;
kaf24@848 88 }
kaf24@848 89
kaf24@848 90 heap[pos] = t;
kaf24@848 91 t->heap_offset = pos;
kaf24@848 92 }
kaf24@848 93
kaf24@848 94
kaf24@848 95 /* Delete @t from @heap. Return TRUE if new top of heap. */
kaf24@848 96 static int remove_entry(struct ac_timer **heap, struct ac_timer *t)
kaf24@848 97 {
kaf24@848 98 int sz = GET_HEAP_SIZE(heap);
kaf24@848 99 int pos = t->heap_offset;
kaf24@848 100
kaf24@848 101 t->heap_offset = 0;
kaf24@848 102
kaf24@848 103 if ( unlikely(pos == sz) )
kaf24@848 104 {
kaf24@848 105 SET_HEAP_SIZE(heap, sz-1);
kaf24@848 106 goto out;
kaf24@848 107 }
kaf24@848 108
kaf24@848 109 heap[pos] = heap[sz];
kaf24@848 110 heap[pos]->heap_offset = pos;
kaf24@848 111
kaf24@848 112 SET_HEAP_SIZE(heap, --sz);
kaf24@848 113
kaf24@848 114 if ( (pos > 1) && (heap[pos]->expires < heap[pos>>1]->expires) )
kaf24@848 115 up_heap(heap, pos);
kaf24@848 116 else
kaf24@848 117 down_heap(heap, pos);
kaf24@848 118
kaf24@848 119 out:
kaf24@848 120 return (pos == 1);
kaf24@848 121 }
kaf24@848 122
kaf24@848 123
kaf24@848 124 /* Add new entry @t to @heap. Return TRUE if new top of heap. */
kaf24@848 125 static int add_entry(struct ac_timer **heap, struct ac_timer *t)
kaf24@848 126 {
kaf24@848 127 int sz = GET_HEAP_SIZE(heap);
kaf24@848 128
kaf24@848 129 /* Copy the heap if it is full. */
kaf24@848 130 if ( unlikely(sz == GET_HEAP_LIMIT(heap)) )
kaf24@848 131 {
kaf24@848 132 int i, limit = (GET_HEAP_LIMIT(heap)+1) << 1;
iap10@3650 133 struct ac_timer **new_heap = xmalloc_array(struct ac_timer *, limit);
kaf24@848 134 if ( new_heap == NULL ) BUG();
kaf24@1592 135 memcpy(new_heap, heap, (limit>>1)*sizeof(struct ac_timer *));
kaf24@848 136 for ( i = 0; i < smp_num_cpus; i++ )
kaf24@848 137 if ( ac_timers[i].heap == heap )
kaf24@848 138 ac_timers[i].heap = new_heap;
kaf24@1958 139 xfree(heap);
kaf24@848 140 heap = new_heap;
kaf24@848 141 SET_HEAP_LIMIT(heap, limit-1);
kaf24@848 142 }
kaf24@848 143
kaf24@848 144 SET_HEAP_SIZE(heap, ++sz);
kaf24@848 145 heap[sz] = t;
kaf24@848 146 t->heap_offset = sz;
kaf24@848 147 up_heap(heap, sz);
kaf24@848 148 return (t->heap_offset == 1);
kaf24@848 149 }
kaf24@848 150
kaf24@848 151
kaf24@848 152 /****************************************************************************
kaf24@848 153 * TIMER OPERATIONS.
kaf24@848 154 */
kaf24@848 155
kaf24@1544 156 static inline void __add_ac_timer(struct ac_timer *timer)
iap10@274 157 {
kaf24@368 158 int cpu = timer->cpu;
kaf24@848 159 if ( add_entry(ac_timers[cpu].heap, timer) )
kaf24@1544 160 cpu_raise_softirq(cpu, AC_TIMER_SOFTIRQ);
kaf24@368 161 }
iap10@274 162
kaf24@368 163 void add_ac_timer(struct ac_timer *timer)
kaf24@368 164 {
kaf24@368 165 int cpu = timer->cpu;
kaf24@1544 166 unsigned long flags;
kaf24@368 167
kaf24@368 168 spin_lock_irqsave(&ac_timers[cpu].lock, flags);
kaf24@368 169 ASSERT(timer != NULL);
kaf24@368 170 ASSERT(!active_ac_timer(timer));
kaf24@1544 171 __add_ac_timer(timer);
iap10@274 172 spin_unlock_irqrestore(&ac_timers[cpu].lock, flags);
iap10@274 173 }
iap10@274 174
kaf24@368 175
kaf24@1544 176 static inline void __rem_ac_timer(struct ac_timer *timer)
iap10@274 177 {
kaf24@368 178 int cpu = timer->cpu;
kaf24@848 179 if ( remove_entry(ac_timers[cpu].heap, timer) )
kaf24@1544 180 cpu_raise_softirq(cpu, AC_TIMER_SOFTIRQ);
kaf24@368 181 }
rn@340 182
kaf24@368 183 void rem_ac_timer(struct ac_timer *timer)
kaf24@368 184 {
kaf24@368 185 int cpu = timer->cpu;
kaf24@1544 186 unsigned long flags;
kaf24@368 187
kaf24@368 188 spin_lock_irqsave(&ac_timers[cpu].lock, flags);
kaf24@368 189 ASSERT(timer != NULL);
kaf24@368 190 if ( active_ac_timer(timer) )
kaf24@1544 191 __rem_ac_timer(timer);
iap10@274 192 spin_unlock_irqrestore(&ac_timers[cpu].lock, flags);
iap10@274 193 }
iap10@274 194
kaf24@368 195
kaf24@368 196 void mod_ac_timer(struct ac_timer *timer, s_time_t new_time)
iap10@274 197 {
kaf24@368 198 int cpu = timer->cpu;
kaf24@1544 199 unsigned long flags;
kaf24@368 200
kaf24@368 201 spin_lock_irqsave(&ac_timers[cpu].lock, flags);
kaf24@368 202 ASSERT(timer != NULL);
kaf24@368 203 if ( active_ac_timer(timer) )
kaf24@1544 204 __rem_ac_timer(timer);
iap10@274 205 timer->expires = new_time;
kaf24@1544 206 __add_ac_timer(timer);
kaf24@368 207 spin_unlock_irqrestore(&ac_timers[cpu].lock, flags);
iap10@274 208 }
iap10@274 209
kaf24@368 210
kaf24@1543 211 static void ac_timer_softirq_action(void)
iap10@274 212 {
rn@328 213 int cpu = smp_processor_id();
kaf24@848 214 struct ac_timer *t, **heap;
kaf24@983 215 s_time_t now;
kaf24@985 216 void (*fn)(unsigned long);
kaf24@848 217
kaf24@983 218 spin_lock_irq(&ac_timers[cpu].lock);
kaf24@983 219
kaf24@983 220 do {
kaf24@983 221 heap = ac_timers[cpu].heap;
kaf24@983 222 now = NOW();
kaf24@983 223
kaf24@983 224 while ( (GET_HEAP_SIZE(heap) != 0) &&
kaf24@983 225 ((t = heap[1])->expires < (now + TIMER_SLOP)) )
kaf24@983 226 {
kaf24@983 227 remove_entry(heap, t);
kaf24@985 228
kaf24@985 229 if ( (fn = t->function) != NULL )
kaf24@985 230 {
kaf24@985 231 unsigned long data = t->data;
kaf24@985 232 spin_unlock_irq(&ac_timers[cpu].lock);
kaf24@985 233 (*fn)(data);
kaf24@985 234 spin_lock_irq(&ac_timers[cpu].lock);
kaf24@985 235 }
kaf24@985 236
kaf24@983 237 /* Heap may have grown while the lock was released. */
kaf24@983 238 heap = ac_timers[cpu].heap;
kaf24@983 239 }
iap10@274 240 }
kaf24@983 241 while ( !reprogram_ac_timer(GET_HEAP_SIZE(heap) ? heap[1]->expires : 0) );
kaf24@368 242
kaf24@983 243 spin_unlock_irq(&ac_timers[cpu].lock);
kaf24@368 244 }
kaf24@368 245
kaf24@695 246
kaf24@2842 247 static void dump_timerq(unsigned char key)
iap10@274 248 {
kaf24@848 249 struct ac_timer *t;
kaf24@848 250 unsigned long flags;
kaf24@848 251 s_time_t now = NOW();
kaf24@848 252 int i, j;
iap10@274 253
rn@328 254 printk("Dumping ac_timer queues: NOW=0x%08X%08X\n",
iap10@274 255 (u32)(now>>32), (u32)now);
kaf24@695 256
kaf24@695 257 for ( i = 0; i < smp_num_cpus; i++ )
kaf24@695 258 {
rn@328 259 printk("CPU[%02d] ", i);
rn@328 260 spin_lock_irqsave(&ac_timers[i].lock, flags);
kaf24@848 261 for ( j = 1; j <= GET_HEAP_SIZE(ac_timers[i].heap); j++ )
kaf24@848 262 {
kaf24@848 263 t = ac_timers[i].heap[j];
kaf24@848 264 printk (" %d : %p ex=0x%08X%08X %lu\n",
kaf24@848 265 j, t, (u32)(t->expires>>32), (u32)t->expires, t->data);
kaf24@848 266 }
rn@328 267 spin_unlock_irqrestore(&ac_timers[i].lock, flags);
rn@328 268 printk("\n");
rn@328 269 }
iap10@274 270 }
iap10@274 271
iap10@274 272
iap10@274 273 void __init ac_timer_init(void)
iap10@274 274 {
iap10@274 275 int i;
iap10@274 276
kaf24@1543 277 open_softirq(AC_TIMER_SOFTIRQ, ac_timer_softirq_action);
kaf24@368 278
kaf24@848 279 for ( i = 0; i < smp_num_cpus; i++ )
iap10@274 280 {
iap10@3650 281 ac_timers[i].heap = xmalloc_array(struct ac_timer *, DEFAULT_HEAP_LIMIT+1);
kaf24@848 282 if ( ac_timers[i].heap == NULL ) BUG();
kaf24@848 283 SET_HEAP_SIZE(ac_timers[i].heap, 0);
kaf24@848 284 SET_HEAP_LIMIT(ac_timers[i].heap, DEFAULT_HEAP_LIMIT);
iap10@274 285 spin_lock_init(&ac_timers[i].lock);
iap10@274 286 }
kaf24@695 287
kaf24@3008 288 register_keyhandler('a', dump_timerq, "dump ac_timer queues");
iap10@274 289 }