ia64/xen-unstable

changeset 18392:070688cdf62c

Fall back to a timer linked list when the timer heap overflows.
Signed-off-by: Keir Fraser <keir.fraser@citrix.com>
author Keir Fraser <keir.fraser@citrix.com>
date Wed Aug 27 13:24:35 2008 +0100 (2008-08-27)
parents 6c6bda7f09cd
children 2397555ebcc2
files xen/common/timer.c xen/include/xen/timer.h
line diff
     1.1 --- a/xen/common/timer.c	Wed Aug 27 11:47:02 2008 +0100
     1.2 +++ b/xen/common/timer.c	Wed Aug 27 13:24:35 2008 +0100
     1.3 @@ -30,6 +30,7 @@
     1.4  struct timers {
     1.5      spinlock_t     lock;
     1.6      struct timer **heap;
     1.7 +    struct timer  *list;
     1.8      struct timer  *running;
     1.9  } __cacheline_aligned;
    1.10  
    1.11 @@ -86,13 +87,11 @@ static void up_heap(struct timer **heap,
    1.12  
    1.13  
    1.14  /* Delete @t from @heap. Return TRUE if new top of heap. */
    1.15 -static int remove_entry(struct timer **heap, struct timer *t)
    1.16 +static int remove_from_heap(struct timer **heap, struct timer *t)
    1.17  {
    1.18      int sz = GET_HEAP_SIZE(heap);
    1.19      int pos = t->heap_offset;
    1.20  
    1.21 -    t->heap_offset = 0;
    1.22 -
    1.23      if ( unlikely(pos == sz) )
    1.24      {
    1.25          SET_HEAP_SIZE(heap, sz-1);
    1.26 @@ -115,7 +114,7 @@ static int remove_entry(struct timer **h
    1.27  
    1.28  
    1.29  /* Add new entry @t to @heap. Return TRUE if new top of heap. */
    1.30 -static int add_entry(struct timer ***pheap, struct timer *t)
    1.31 +static int add_to_heap(struct timer ***pheap, struct timer *t)
    1.32  {
    1.33      struct timer **heap = *pheap;
    1.34      int sz = GET_HEAP_SIZE(heap);
    1.35 @@ -126,8 +125,11 @@ static int add_entry(struct timer ***phe
    1.36          /* old_limit == (2^n)-1; new_limit == (2^(n+4))-1 */
    1.37          int old_limit = GET_HEAP_LIMIT(heap);
    1.38          int new_limit = ((old_limit + 1) << 4) - 1;
    1.39 +        if ( in_irq() )
    1.40 +            goto out;
    1.41          heap = xmalloc_array(struct timer *, new_limit + 1);
    1.42 -        BUG_ON(heap == NULL);
    1.43 +        if ( heap == NULL )
    1.44 +            goto out;
    1.45          memcpy(heap, *pheap, (old_limit + 1) * sizeof(*heap));
    1.46          SET_HEAP_LIMIT(heap, new_limit);
    1.47          if ( old_limit != 0 )
    1.48 @@ -139,26 +141,95 @@ static int add_entry(struct timer ***phe
    1.49      heap[sz] = t;
    1.50      t->heap_offset = sz;
    1.51      up_heap(heap, sz);
    1.52 + out:
    1.53      return (t->heap_offset == 1);
    1.54  }
    1.55  
    1.56  
    1.57  /****************************************************************************
    1.58 + * LINKED LIST OPERATIONS.
    1.59 + */
    1.60 +
    1.61 +static int remove_from_list(struct timer **pprev, struct timer *t)
    1.62 +{
    1.63 +    struct timer *curr, **_pprev = pprev;
    1.64 +
    1.65 +    while ( (curr = *_pprev) != t )
    1.66 +        _pprev = &curr->list_next;
    1.67 +
    1.68 +    *_pprev = t->list_next;
    1.69 +
    1.70 +    return (_pprev == pprev);
    1.71 +}
    1.72 +
    1.73 +static int add_to_list(struct timer **pprev, struct timer *t)
    1.74 +{
    1.75 +    struct timer *curr, **_pprev = pprev;
    1.76 +
    1.77 +    while ( ((curr = *_pprev) != NULL) && (curr->expires <= t->expires) )
    1.78 +        _pprev = &curr->list_next;
    1.79 +
    1.80 +    t->list_next = curr;
    1.81 +    *_pprev = t;
    1.82 +
    1.83 +    return (_pprev == pprev);
    1.84 +}
    1.85 +
    1.86 +
    1.87 +/****************************************************************************
    1.88   * TIMER OPERATIONS.
    1.89   */
    1.90  
    1.91 +static int remove_entry(struct timers *timers, struct timer *t)
    1.92 +{
    1.93 +    int rc;
    1.94 +
    1.95 +    switch ( t->status )
    1.96 +    {
    1.97 +    case TIMER_STATUS_in_heap:
    1.98 +        rc = remove_from_heap(timers->heap, t);
    1.99 +        break;
   1.100 +    case TIMER_STATUS_in_list:
   1.101 +        rc = remove_from_list(&timers->list, t);
   1.102 +        break;
   1.103 +    default:
   1.104 +        rc = 0;
   1.105 +        BUG();
   1.106 +    }
   1.107 +
   1.108 +    t->status = TIMER_STATUS_inactive;
   1.109 +    return rc;
   1.110 +}
   1.111 +
   1.112 +static int add_entry(struct timers *timers, struct timer *t)
   1.113 +{
   1.114 +    int rc;
   1.115 +
   1.116 +    ASSERT(t->status == TIMER_STATUS_inactive);
   1.117 +
   1.118 +    /* Try to add to heap. t->heap_offset indicates whether we succeed. */
   1.119 +    t->heap_offset = 0;
   1.120 +    t->status = TIMER_STATUS_in_heap;
   1.121 +    rc = add_to_heap(&timers->heap, t);
   1.122 +    if ( t->heap_offset != 0 )
   1.123 +        return rc;
   1.124 +
   1.125 +    /* Fall back to adding to the slower linked list. */
   1.126 +    t->status = TIMER_STATUS_in_list;
   1.127 +    return add_to_list(&timers->list, t);
   1.128 +}
   1.129 +
   1.130  static inline void __add_timer(struct timer *timer)
   1.131  {
   1.132      int cpu = timer->cpu;
   1.133 -    if ( add_entry(&per_cpu(timers, cpu).heap, timer) )
   1.134 +    if ( add_entry(&per_cpu(timers, cpu), timer) )
   1.135          cpu_raise_softirq(cpu, TIMER_SOFTIRQ);
   1.136  }
   1.137  
   1.138 -
   1.139  static inline void __stop_timer(struct timer *timer)
   1.140  {
   1.141      int cpu = timer->cpu;
   1.142 -    if ( remove_entry(per_cpu(timers, cpu).heap, timer) )
   1.143 +    if ( remove_entry(&per_cpu(timers, cpu), timer) )
   1.144          cpu_raise_softirq(cpu, TIMER_SOFTIRQ);
   1.145  }
   1.146  
   1.147 @@ -203,7 +274,7 @@ void set_timer(struct timer *timer, s_ti
   1.148  
   1.149      timer->expires = expires;
   1.150  
   1.151 -    if ( likely(!timer->killed) )
   1.152 +    if ( likely(timer->status != TIMER_STATUS_killed) )
   1.153          __add_timer(timer);
   1.154  
   1.155      timer_unlock_irqrestore(timer, flags);
   1.156 @@ -278,7 +349,7 @@ void kill_timer(struct timer *timer)
   1.157  
   1.158      if ( active_timer(timer) )
   1.159          __stop_timer(timer);
   1.160 -    timer->killed = 1;
   1.161 +    timer->status = TIMER_STATUS_killed;
   1.162  
   1.163      timer_unlock_irqrestore(timer, flags);
   1.164  
   1.165 @@ -290,43 +361,76 @@ void kill_timer(struct timer *timer)
   1.166  
   1.167  static void timer_softirq_action(void)
   1.168  {
   1.169 -    struct timer  *t, **heap;
   1.170 +    struct timer  *t, **heap, *next;
   1.171      struct timers *ts;
   1.172 -    s_time_t       now;
   1.173 +    s_time_t       now, deadline;
   1.174      void         (*fn)(void *);
   1.175      void          *data;
   1.176  
   1.177      ts = &this_cpu(timers);
   1.178  
   1.179      spin_lock_irq(&ts->lock);
   1.180 -    
   1.181 -    do {
   1.182 -        heap = ts->heap;
   1.183 -        now  = NOW();
   1.184 -
   1.185 -        while ( (GET_HEAP_SIZE(heap) != 0) &&
   1.186 -                ((t = heap[1])->expires < (now + TIMER_SLOP)) )
   1.187 -        {
   1.188 -            remove_entry(heap, t);
   1.189  
   1.190 -            ts->running = t;
   1.191 -
   1.192 -            fn   = t->function;
   1.193 -            data = t->data;
   1.194 +    /* Try to move timers from overflow linked list to more efficient heap. */
   1.195 +    next = ts->list;
   1.196 +    ts->list = NULL;
   1.197 +    while ( unlikely((t = next) != NULL) )
   1.198 +    {
   1.199 +        next = t->list_next;
   1.200 +        t->status = TIMER_STATUS_inactive;
   1.201 +        add_entry(ts, t);
   1.202 +    }
   1.203 +    
   1.204 +    heap = ts->heap;
   1.205 +    now  = NOW();
   1.206  
   1.207 -            spin_unlock_irq(&ts->lock);
   1.208 -            (*fn)(data);
   1.209 -            spin_lock_irq(&ts->lock);
   1.210 +    while ( (GET_HEAP_SIZE(heap) != 0) &&
   1.211 +            ((t = heap[1])->expires < (now + TIMER_SLOP)) )
   1.212 +    {
   1.213 +        remove_entry(ts, t);
   1.214  
   1.215 -            /* Heap may have grown while the lock was released. */
   1.216 -            heap = ts->heap;
   1.217 +        ts->running = t;
   1.218 +
   1.219 +        fn   = t->function;
   1.220 +        data = t->data;
   1.221 +
   1.222 +        spin_unlock_irq(&ts->lock);
   1.223 +        (*fn)(data);
   1.224 +        spin_lock_irq(&ts->lock);
   1.225 +
   1.226 +        /* Heap may have grown while the lock was released. */
   1.227 +        heap = ts->heap;
   1.228 +    }
   1.229 +
   1.230 +    deadline = GET_HEAP_SIZE(heap) ? heap[1]->expires : 0;
   1.231 +
   1.232 +    while ( unlikely((t = ts->list) != NULL) )
   1.233 +    {
   1.234 +        if ( t->expires >= (now + TIMER_SLOP) )
   1.235 +        {
   1.236 +            if ( (deadline == 0) || (deadline > t->expires) )
   1.237 +                deadline = t->expires;
   1.238 +            break;
   1.239          }
   1.240  
   1.241 -        ts->running = NULL;
   1.242 +        ts->list = t->list_next;
   1.243 +        t->status = TIMER_STATUS_inactive;
   1.244  
   1.245 -        this_cpu(timer_deadline) = GET_HEAP_SIZE(heap) ? heap[1]->expires : 0;
   1.246 +        ts->running = t;
   1.247 +
   1.248 +        fn   = t->function;
   1.249 +        data = t->data;
   1.250 +
   1.251 +        spin_unlock_irq(&ts->lock);
   1.252 +        (*fn)(data);
   1.253 +        spin_lock_irq(&ts->lock);
   1.254      }
   1.255 -    while ( !reprogram_timer(this_cpu(timer_deadline)) );
   1.256 +
   1.257 +    ts->running = NULL;
   1.258 +
   1.259 +    this_cpu(timer_deadline) = deadline;
   1.260 +    if ( !reprogram_timer(deadline) )
   1.261 +        raise_softirq(TIMER_SOFTIRQ);
   1.262  
   1.263      spin_unlock_irq(&ts->lock);
   1.264  }
   1.265 @@ -364,6 +468,9 @@ static void dump_timerq(unsigned char ke
   1.266              printk ("  %d : %p ex=0x%08X%08X %p\n",
   1.267                      j, t, (u32)(t->expires>>32), (u32)t->expires, t->data);
   1.268          }
   1.269 +        for ( t = ts->list, j = 0; t != NULL; t = t->list_next, j++ )
   1.270 +            printk (" L%d : %p ex=0x%08X%08X %p\n",
   1.271 +                    j, t, (u32)(t->expires>>32), (u32)t->expires, t->data);
   1.272          spin_unlock_irqrestore(&ts->lock, flags);
   1.273          printk("\n");
   1.274      }
     2.1 --- a/xen/include/xen/timer.h	Wed Aug 27 11:47:02 2008 +0100
     2.2 +++ b/xen/include/xen/timer.h	Wed Aug 27 13:24:35 2008 +0100
     2.3 @@ -14,16 +14,29 @@
     2.4  
     2.5  struct timer {
     2.6      /* System time expiry value (nanoseconds since boot). */
     2.7 -    s_time_t      expires;
     2.8 -    /* CPU on which this timer will be installed and executed. */
     2.9 -    unsigned int  cpu;
    2.10 +    s_time_t expires;
    2.11 +
    2.12 +    /* Position in active-timer data structure. */
    2.13 +    union {
    2.14 +        /* Timer-heap offset. */
    2.15 +        unsigned int heap_offset;
    2.16 +        /* Overflow linked list. */
    2.17 +        struct timer *list_next;
    2.18 +    };
    2.19 +
    2.20      /* On expiry, '(*function)(data)' will be executed in softirq context. */
    2.21 -    void        (*function)(void *);
    2.22 -    void         *data;
    2.23 -    /* Timer-heap offset. */
    2.24 -    unsigned int  heap_offset;
    2.25 -    /* Has this timer been killed (cannot be activated)? */
    2.26 -    int           killed;
    2.27 +    void (*function)(void *);
    2.28 +    void *data;
    2.29 +
    2.30 +    /* CPU on which this timer will be installed and executed. */
    2.31 +    uint16_t cpu;
    2.32 +
    2.33 +    /* Timer status. */
    2.34 +#define TIMER_STATUS_inactive 0 /* Not in use; can be activated.    */
    2.35 +#define TIMER_STATUS_killed   1 /* Not in use; canot be activated.  */
    2.36 +#define TIMER_STATUS_in_heap  2 /* In use; on timer heap.           */
    2.37 +#define TIMER_STATUS_in_list  3 /* In use; on overflow linked list. */
    2.38 +    uint8_t status;
    2.39  };
    2.40  
    2.41  /*
    2.42 @@ -37,7 +50,7 @@ struct timer {
    2.43   */
    2.44  static inline int active_timer(struct timer *timer)
    2.45  {
    2.46 -    return (timer->heap_offset != 0);
    2.47 +    return (timer->status >= TIMER_STATUS_in_heap);
    2.48  }
    2.49  
    2.50  /*