1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/xen/common/timer.c	Fri Jan 13 00:16:07 2006 +0100
     1.3 @@ -0,0 +1,288 @@
     1.4 +/******************************************************************************
     1.5 + * timer.c
     1.6 + * 
     1.7 + * Copyright (c) 2002-2003 Rolf Neugebauer
     1.8 + * Copyright (c) 2002-2005 K A Fraser
     1.9 + */
    1.10 +
    1.11 +#include <xen/config.h>
    1.12 +#include <xen/init.h>
    1.13 +#include <xen/types.h>
    1.14 +#include <xen/errno.h>
    1.15 +#include <xen/sched.h>
    1.16 +#include <xen/lib.h>
    1.17 +#include <xen/smp.h>
    1.18 +#include <xen/perfc.h>
    1.19 +#include <xen/time.h>
    1.20 +#include <xen/softirq.h>
    1.21 +#include <xen/timer.h>
    1.22 +#include <xen/keyhandler.h>
    1.23 +#include <asm/system.h>
    1.24 +#include <asm/desc.h>
    1.25 +
    1.26 +/*
    1.27 + * We pull handlers off the timer list this far in future,
    1.28 + * rather than reprogramming the time hardware.
    1.29 + */
    1.30 +#define TIMER_SLOP (50*1000) /* ns */
    1.31 +
    1.32 +struct timers {
    1.33 +    spinlock_t     lock;
    1.34 +    struct timer **heap;
    1.35 +} __cacheline_aligned;
    1.36 +
    1.37 +struct timers timers[NR_CPUS];
    1.38 +
    1.39 +extern int reprogram_timer(s_time_t timeout);
    1.40 +
    1.41 +/****************************************************************************
    1.42 + * HEAP OPERATIONS.
    1.43 + */
    1.44 +
    1.45 +#define GET_HEAP_SIZE(_h)     ((int)(((u16 *)(_h))[0]))
    1.46 +#define SET_HEAP_SIZE(_h,_v)  (((u16 *)(_h))[0] = (u16)(_v))
    1.47 +
    1.48 +#define GET_HEAP_LIMIT(_h)    ((int)(((u16 *)(_h))[1]))
    1.49 +#define SET_HEAP_LIMIT(_h,_v) (((u16 *)(_h))[1] = (u16)(_v))
    1.50 +
    1.51 +/* Sink down element @pos of @heap. */
    1.52 +static void down_heap(struct timer **heap, int pos)
    1.53 +{
    1.54 +    int sz = GET_HEAP_SIZE(heap), nxt;
    1.55 +    struct timer *t = heap[pos];
    1.56 +
    1.57 +    while ( (nxt = (pos << 1)) <= sz )
    1.58 +    {
    1.59 +        if ( ((nxt+1) <= sz) && (heap[nxt+1]->expires < heap[nxt]->expires) )
    1.60 +            nxt++;
    1.61 +        if ( heap[nxt]->expires > t->expires )
    1.62 +            break;
    1.63 +        heap[pos] = heap[nxt];
    1.64 +        heap[pos]->heap_offset = pos;
    1.65 +        pos = nxt;
    1.66 +    }
    1.67 +
    1.68 +    heap[pos] = t;
    1.69 +    t->heap_offset = pos;
    1.70 +}
    1.71 +
    1.72 +/* Float element @pos up @heap. */
    1.73 +static void up_heap(struct timer **heap, int pos)
    1.74 +{
    1.75 +    struct timer *t = heap[pos];
    1.76 +
    1.77 +    while ( (pos > 1) && (t->expires < heap[pos>>1]->expires) )
    1.78 +    {
    1.79 +        heap[pos] = heap[pos>>1];
    1.80 +        heap[pos]->heap_offset = pos;
    1.81 +        pos >>= 1;
    1.82 +    }
    1.83 +
    1.84 +    heap[pos] = t;
    1.85 +    t->heap_offset = pos;
    1.86 +}
    1.87 +
    1.88 +
    1.89 +/* Delete @t from @heap. Return TRUE if new top of heap. */
    1.90 +static int remove_entry(struct timer **heap, struct timer *t)
    1.91 +{
    1.92 +    int sz = GET_HEAP_SIZE(heap);
    1.93 +    int pos = t->heap_offset;
    1.94 +
    1.95 +    t->heap_offset = 0;
    1.96 +
    1.97 +    if ( unlikely(pos == sz) )
    1.98 +    {
    1.99 +        SET_HEAP_SIZE(heap, sz-1);
   1.100 +        goto out;
   1.101 +    }
   1.102 +
   1.103 +    heap[pos] = heap[sz];
   1.104 +    heap[pos]->heap_offset = pos;
   1.105 +
   1.106 +    SET_HEAP_SIZE(heap, --sz);
   1.107 +
   1.108 +    if ( (pos > 1) && (heap[pos]->expires < heap[pos>>1]->expires) )
   1.109 +        up_heap(heap, pos);
   1.110 +    else
   1.111 +        down_heap(heap, pos);
   1.112 +
   1.113 + out:
   1.114 +    return (pos == 1);
   1.115 +}
   1.116 +
   1.117 +
   1.118 +/* Add new entry @t to @heap. Return TRUE if new top of heap. */
   1.119 +static int add_entry(struct timer ***pheap, struct timer *t)
   1.120 +{
   1.121 +    struct timer **heap = *pheap;
   1.122 +    int sz = GET_HEAP_SIZE(heap);
   1.123 +
   1.124 +    /* Copy the heap if it is full. */
   1.125 +    if ( unlikely(sz == GET_HEAP_LIMIT(heap)) )
   1.126 +    {
   1.127 +        /* old_limit == (2^n)-1; new_limit == (2^(n+4))-1 */
   1.128 +        int old_limit = GET_HEAP_LIMIT(heap);
   1.129 +        int new_limit = ((old_limit + 1) << 4) - 1;
   1.130 +        heap = xmalloc_array(struct timer *, new_limit + 1);
   1.131 +        BUG_ON(heap == NULL);
   1.132 +        memcpy(heap, *pheap, (old_limit + 1) * sizeof(*heap));
   1.133 +        SET_HEAP_LIMIT(heap, new_limit);
   1.134 +        if ( old_limit != 0 )
   1.135 +            xfree(*pheap);
   1.136 +        *pheap = heap;
   1.137 +    }
   1.138 +
   1.139 +    SET_HEAP_SIZE(heap, ++sz);
   1.140 +    heap[sz] = t;
   1.141 +    t->heap_offset = sz;
   1.142 +    up_heap(heap, sz);
   1.143 +    return (t->heap_offset == 1);
   1.144 +}
   1.145 +
   1.146 +
   1.147 +/****************************************************************************
   1.148 + * TIMER OPERATIONS.
   1.149 + */
   1.150 +
   1.151 +static inline void __add_timer(struct timer *timer)
   1.152 +{
   1.153 +    int cpu = timer->cpu;
   1.154 +    if ( add_entry(&timers[cpu].heap, timer) )
   1.155 +        cpu_raise_softirq(cpu, TIMER_SOFTIRQ);
   1.156 +}
   1.157 +
   1.158 +
   1.159 +static inline void __stop_timer(struct timer *timer)
   1.160 +{
   1.161 +    int cpu = timer->cpu;
   1.162 +    if ( remove_entry(timers[cpu].heap, timer) )
   1.163 +        cpu_raise_softirq(cpu, TIMER_SOFTIRQ);
   1.164 +}
   1.165 +
   1.166 +
   1.167 +void set_timer(struct timer *timer, s_time_t expires)
   1.168 +{
   1.169 +    int           cpu = timer->cpu;
   1.170 +    unsigned long flags;
   1.171 +
   1.172 +    spin_lock_irqsave(&timers[cpu].lock, flags);
   1.173 +    ASSERT(timer != NULL);
   1.174 +    if ( active_timer(timer) )
   1.175 +        __stop_timer(timer);
   1.176 +    timer->expires = expires;
   1.177 +    __add_timer(timer);
   1.178 +    spin_unlock_irqrestore(&timers[cpu].lock, flags);
   1.179 +}
   1.180 +
   1.181 +
   1.182 +void stop_timer(struct timer *timer)
   1.183 +{
   1.184 +    int           cpu = timer->cpu;
   1.185 +    unsigned long flags;
   1.186 +
   1.187 +    spin_lock_irqsave(&timers[cpu].lock, flags);
   1.188 +    ASSERT(timer != NULL);
   1.189 +    if ( active_timer(timer) )
   1.190 +        __stop_timer(timer);
   1.191 +    spin_unlock_irqrestore(&timers[cpu].lock, flags);
   1.192 +}
   1.193 +
   1.194 +
   1.195 +static void timer_softirq_action(void)
   1.196 +{
   1.197 +    int           cpu = smp_processor_id();
   1.198 +    struct timer *t, **heap;
   1.199 +    s_time_t      now;
   1.200 +    void        (*fn)(void *);
   1.201 +    void         *data;
   1.202 +
   1.203 +    spin_lock_irq(&timers[cpu].lock);
   1.204 +    
   1.205 +    do {
   1.206 +        heap = timers[cpu].heap;
   1.207 +        now  = NOW();
   1.208 +
   1.209 +        while ( (GET_HEAP_SIZE(heap) != 0) &&
   1.210 +                ((t = heap[1])->expires < (now + TIMER_SLOP)) )
   1.211 +        {
   1.212 +            remove_entry(heap, t);
   1.213 +
   1.214 +            fn   = t->function;
   1.215 +            data = t->data;
   1.216 +
   1.217 +            if ( fn != NULL )
   1.218 +            {
   1.219 +                spin_unlock_irq(&timers[cpu].lock);
   1.220 +                (*fn)(data);
   1.221 +                spin_lock_irq(&timers[cpu].lock);
   1.222 +            }
   1.223 +
   1.224 +            /* Heap may have grown while the lock was released. */
   1.225 +            heap = timers[cpu].heap;
   1.226 +        }
   1.227 +    }
   1.228 +    while ( !reprogram_timer(GET_HEAP_SIZE(heap) ? heap[1]->expires : 0) );
   1.229 +
   1.230 +    spin_unlock_irq(&timers[cpu].lock);
   1.231 +}
   1.232 +
   1.233 +
   1.234 +static void dump_timerq(unsigned char key)
   1.235 +{
   1.236 +    struct timer *t;
   1.237 +    unsigned long flags; 
   1.238 +    s_time_t      now = NOW();
   1.239 +    int           i, j;
   1.240 +
   1.241 +    printk("Dumping timer queues: NOW=0x%08X%08X\n",
   1.242 +           (u32)(now>>32), (u32)now); 
   1.243 +
   1.244 +    for_each_online_cpu( i )
   1.245 +    {
   1.246 +        printk("CPU[%02d] ", i);
   1.247 +        spin_lock_irqsave(&timers[i].lock, flags);
   1.248 +        for ( j = 1; j <= GET_HEAP_SIZE(timers[i].heap); j++ )
   1.249 +        {
   1.250 +            t = timers[i].heap[j];
   1.251 +            printk ("  %d : %p ex=0x%08X%08X %p\n",
   1.252 +                    j, t, (u32)(t->expires>>32), (u32)t->expires, t->data);
   1.253 +        }
   1.254 +        spin_unlock_irqrestore(&timers[i].lock, flags);
   1.255 +        printk("\n");
   1.256 +    }
   1.257 +}
   1.258 +
   1.259 +
   1.260 +void __init timer_init(void)
   1.261 +{
   1.262 +    static struct timer *dummy_heap;
   1.263 +    int i;
   1.264 +
   1.265 +    open_softirq(TIMER_SOFTIRQ, timer_softirq_action);
   1.266 +
   1.267 +    /*
   1.268 +     * All CPUs initially share an empty dummy heap. Only those CPUs that
   1.269 +     * are brought online will be dynamically allocated their own heap.
   1.270 +     */
   1.271 +    SET_HEAP_SIZE(&dummy_heap, 0);
   1.272 +    SET_HEAP_LIMIT(&dummy_heap, 0);
   1.273 +
   1.274 +    for ( i = 0; i < NR_CPUS; i++ )
   1.275 +    {
   1.276 +        spin_lock_init(&timers[i].lock);
   1.277 +        timers[i].heap = &dummy_heap;
   1.278 +    }
   1.279 +
   1.280 +    register_keyhandler('a', dump_timerq, "dump timer queues");
   1.281 +}
   1.282 +
   1.283 +/*
   1.284 + * Local variables:
   1.285 + * mode: C
   1.286 + * c-set-style: "BSD"
   1.287 + * c-basic-offset: 4
   1.288 + * tab-width: 4
   1.289 + * indent-tabs-mode: nil
   1.290 + * End:
   1.291 + */

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/xen/include/xen/timer.h	Fri Jan 13 00:16:07 2006 +0100
     2.3 @@ -0,0 +1,81 @@
     2.4 +/******************************************************************************
     2.5 + * timer.h
     2.6 + * 
     2.7 + * Copyright (c) 2002-2003 Rolf Neugebauer
     2.8 + * Copyright (c) 2002-2005 K A Fraser
     2.9 + */
    2.10 +
    2.11 +#ifndef _TIMER_H_
    2.12 +#define _TIMER_H_
    2.13 +
    2.14 +#include <xen/spinlock.h>
    2.15 +#include <xen/time.h>
    2.16 +#include <xen/string.h>
    2.17 +
    2.18 +struct timer {
    2.19 +    /* System time expiry value (nanoseconds since boot). */
    2.20 +    s_time_t      expires;
    2.21 +    /* CPU on which this timer will be installed and executed. */
    2.22 +    unsigned int  cpu;
    2.23 +    /* On expiry, '(*function)(data)' will be executed in softirq context. */
    2.24 +    void        (*function)(void *);
    2.25 +    void         *data;
    2.26 +    /* Timer-heap offset. */
    2.27 +    unsigned int  heap_offset;
    2.28 +};
    2.29 +
    2.30 +/*
    2.31 + * All functions below can be called for any CPU from any CPU in any context.
    2.32 + */
    2.33 +
    2.34 +/* Returns TRUE if the given timer is on a timer list. */
    2.35 +static __inline__ int active_timer(struct timer *timer)
    2.36 +{
    2.37 +    return (timer->heap_offset != 0);
    2.38 +}
    2.39 +
    2.40 +/*
    2.41 + * It initialises the static fields of the timer structure.
    2.42 + * It can be called multiple times to reinitialise a single (inactive) timer.
    2.43 + */
    2.44 +static __inline__ void init_timer(
    2.45 +    struct timer *timer,
    2.46 +    void           (*function)(void *),
    2.47 +    void            *data,
    2.48 +    unsigned int     cpu)
    2.49 +{
    2.50 +    memset(timer, 0, sizeof(*timer));
    2.51 +    timer->function = function;
    2.52 +    timer->data     = data;
    2.53 +    timer->cpu      = cpu;
    2.54 +}
    2.55 +
    2.56 +/*
    2.57 + * Set the expiry time and activate a timer (which must previously have been
    2.58 + * initialised by init_timer).
    2.59 + */
    2.60 +extern void set_timer(struct timer *timer, s_time_t expires);
    2.61 +
    2.62 +/*
    2.63 + * Deactivate a timer (which must previously have been initialised by
    2.64 + * init_timer). This function has no effect if the timer is not currently
    2.65 + * active.
    2.66 + */
    2.67 +extern void stop_timer(struct timer *timer);
    2.68 +
    2.69 +/*
    2.70 + * Initialisation. Must be called before any other timer function.
    2.71 + */
    2.72 +extern void timer_init(void);
    2.73 +
    2.74 +#endif /* _TIMER_H_ */
    2.75 +
    2.76 +/*
    2.77 + * Local variables:
    2.78 + * mode: C
    2.79 + * c-set-style: "BSD"
    2.80 + * c-basic-offset: 4
    2.81 + * tab-width: 4
    2.82 + * indent-tabs-mode: nil
    2.83 + * End:
    2.84 + */