*************** *** 25,62 **** #include #include #include /* * per-CPU timer vector definitions: */ - #define TVN_BITS 6 - #define TVR_BITS 8 - #define TVN_SIZE (1 << TVN_BITS) - #define TVR_SIZE (1 << TVR_BITS) - #define TVN_MASK (TVN_SIZE - 1) - #define TVR_MASK (TVR_SIZE - 1) - - typedef struct tvec_s { - int index; - struct list_head vec[TVN_SIZE]; - } tvec_t; - - typedef struct tvec_root_s { - int index; - struct list_head vec[TVR_SIZE]; - } tvec_root_t; - struct tvec_t_base_s { spinlock_t lock; unsigned long timer_jiffies; - struct timer_list *running_timer; - tvec_root_t tv1; - tvec_t tv2; - tvec_t tv3; - tvec_t tv4; - tvec_t tv5; } ____cacheline_aligned_in_smp; typedef struct tvec_t_base_s tvec_base_t; --- 27,70 ---- #include #include + #include + #include + #include #include + #ifndef IF_HIGH_RES + #ifdef CONFIG_HIGH_RES_TIMERS + /* + * ifdef eliminator macro... + */ + #define IF_HIGH_RES(a) a + #else + #define IF_HIGH_RES(a) + #endif + #endif + #ifdef CONFIG_SMP + #undef IF_SMP + #define IF_SMP(a) a + #define SMP 1 + #else + #undef IF_SMP + #define IF_SMP(a) + #define SMP 0 + #endif + #ifndef CONFIG_NEW_TIMER_LISTSIZE + #define CONFIG_NEW_TIMER_LISTSIZE 512 + #endif + #define NEW_TVEC_SIZE CONFIG_NEW_TIMER_LISTSIZE + #define NEW_TVEC_MASK (NEW_TVEC_SIZE - 1) /* * per-CPU timer vector definitions: */ struct tvec_t_base_s { spinlock_t lock; unsigned long timer_jiffies; + volatile struct timer_list * volatile running_timer; + struct list_head tv[NEW_TVEC_SIZE]; } ____cacheline_aligned_in_smp; typedef struct tvec_t_base_s tvec_base_t; *************** *** 66,107 **** /* Fake initialization needed to avoid compiler breakage */ static DEFINE_PER_CPU(struct tasklet_struct, timer_tasklet) = { NULL }; - static inline void internal_add_timer(tvec_base_t *base, struct timer_list *timer) - { - unsigned long expires = timer->expires; - unsigned long idx = expires - base->timer_jiffies; - struct list_head *vec; - - if (idx < TVR_SIZE) { - int i = expires & TVR_MASK; - vec = base->tv1.vec + i; - } else if (idx < 1 << (TVR_BITS + TVN_BITS)) { - int i = (expires >> TVR_BITS) & TVN_MASK; - vec = base->tv2.vec + i; - } else if (idx < 1 << (TVR_BITS + 2 * TVN_BITS)) { - int i = (expires >> (TVR_BITS + TVN_BITS)) & TVN_MASK; - vec = base->tv3.vec + i; - } else if (idx < 1 << (TVR_BITS + 3 * TVN_BITS)) { - int i = (expires >> (TVR_BITS + 2 * TVN_BITS)) & TVN_MASK; - vec = base->tv4.vec + i; - } else if ((signed long) idx < 0) { - /* - * Can happen if you add a timer with expires == jiffies, - * or you set a timer to go off in the past - */ - vec = base->tv1.vec + base->tv1.index; - } else if (idx <= 0xffffffffUL) { - int i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK; - vec = base->tv5.vec + i; - } else { - /* Can only get here on architectures with 64-bit jiffies */ - INIT_LIST_HEAD(&timer->entry); - return; - } - /* - * Timers are FIFO: - */ - list_add_tail(&timer->entry, vec); } /*** --- 74,174 ---- /* Fake initialization needed to avoid compiler breakage */ static DEFINE_PER_CPU(struct tasklet_struct, timer_tasklet) = { NULL }; + static inline void internal_add_timer(tvec_base_t *base, + struct timer_list *timer) + { + /* + * must be cli-ed when calling this + */ + unsigned long expires = timer->expires; + IF_HIGH_RES(int sub_expires = timer->sub_expires;) + int indx; + struct list_head *pos,*list_start; + + if ( time_before(expires, base->timer_jiffies) ){ + /* + * already expired, schedule for next tick + * would like to do better here + * Actually this now works just fine with the + * back up of timer_jiffies in "run_timer_list". + * Note that this puts the timer on a list other + * than the one it idexes to. We don't want to + * change the expires value in the timer as it is + * used by the repeat code in setitimer and the + * POSIX timers code. + */ + expires = base->timer_jiffies; + IF_HIGH_RES(sub_expires = 0); + } + + indx = expires & NEW_TVEC_MASK; + if ((expires - base->timer_jiffies) <= NEW_TVEC_SIZE) { + #ifdef CONFIG_HIGH_RES_TIMERS + unsigned long jiffies_f; + /* + * The high diff bits are the same, goes to the head of + * the list, sort on sub_expire. + */ + for (pos = (list_start = &base->tv[indx])->next; + pos != list_start; + pos = pos->next){ + struct timer_list *tmr = + list_entry(pos, + struct timer_list, + entry); + if ((tmr->sub_expires >= sub_expires) || + (tmr->expires != expires)){ + break; + } + } + list_add_tail(&timer->entry, pos); + /* + * Notes to me. Use jiffies here instead of + * timer_jiffies to prevent adding unneeded interrupts. + * Running_timer is NULL if we are NOT currently + * activly dispatching timers. Since we are under + * the same spin lock, it being false means that + * it has dropped the spinlock to call the timer + * function, which could well be who called us. + * In any case, we don't need a new interrupt as + * the timer dispach code (run_timer_list) will + * pick this up when the function it is calling + * returns. + */ + if ( expires == (jiffies_f = jiffies) && + list_start->next == &timer->entry && + (base->running_timer == NULL)) { + schedule_next_int(jiffies_f, sub_expires,1); + } + #else + pos = (&base->tv[indx])->next; + list_add_tail(&timer->entry, pos); + #endif + }else{ + /* + * The high diff bits differ, search from the tail + * The for will pick up an empty list. + */ + for (pos = (list_start = &base->tv[indx])->prev; + pos != list_start; + pos = pos->prev){ + struct timer_list *tmr = + list_entry(pos, + struct timer_list, + entry); + if (time_after(tmr->expires, expires)){ + continue; + } + IF_HIGH_RES( + if ((tmr->expires != expires) || + (tmr->sub_expires < sub_expires)) { + break; + } + ); + } + list_add(&timer->entry, pos); + } + } /*** *************** *** 152,160 **** * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an * active timer returns 1.) */ int mod_timer(struct timer_list *timer, unsigned long expires) { - tvec_base_t *old_base, *new_base; unsigned long flags; int ret = 0; --- 219,229 ---- * (ie. mod_timer() of an inactive timer returns 0, mod_timer() of an * active timer returns 1.) */ + #ifndef CONFIG_HIGH_RES_TIMERS int mod_timer(struct timer_list *timer, unsigned long expires) { + tvec_base_t *new_base; + IF_SMP( tvec_base_t *old_base;) unsigned long flags; int ret = 0; *************** *** 290,344 **** #endif - static int cascade(tvec_base_t *base, tvec_t *tv) - { - /* cascade all the timers from tv up one level */ - struct list_head *head, *curr, *next; - - head = tv->vec + tv->index; - curr = head->next; - /* - * We are removing _all_ timers from the list, so we don't have to - * detach them individually, just clear the list afterwards. - */ - while (curr != head) { - struct timer_list *tmp; - - tmp = list_entry(curr, struct timer_list, entry); - if (tmp->base != base) - BUG(); - next = curr->next; - internal_add_timer(base, tmp); - curr = next; - } - INIT_LIST_HEAD(head); - - return tv->index = (tv->index + 1) & TVN_MASK; - } - - /*** - * __run_timers - run all expired timers (if any) on this CPU. - * @base: the timer vector to be processed. - * - * This function cascades all vectors and executes all expired timer - * vectors. */ - static inline void __run_timers(tvec_base_t *base) { spin_lock_irq(&base->lock); while ((long)(jiffies - base->timer_jiffies) >= 0) { struct list_head *head, *curr; - /* - * Cascade timers: */ - if (!base->tv1.index && - (cascade(base, &base->tv2) == 1) && - (cascade(base, &base->tv3) == 1) && - cascade(base, &base->tv4) == 1) - cascade(base, &base->tv5); repeat: - head = base->tv1.vec + base->tv1.index; curr = head->next; if (curr != head) { void (*fn)(unsigned long); --- 437,478 ---- #endif + /* + * run_timer_list is ALWAYS called from softirq which calls with irq enabled. + * We may assume this and not save the flags. */ + + + static void __run_timers(tvec_base_t *base) { + IF_HIGH_RES( unsigned long jiffies_f; + long sub_jiff = -1; + long sub_jiffie_f); spin_lock_irq(&base->lock); + #ifdef CONFIG_HIGH_RES_TIMERS + read_lock(&xtime_lock); + jiffies_f = jiffies; + sub_jiffie_f = sub_jiffie() + quick_get_cpuctr(); + read_unlock(&xtime_lock); + while ( unlikely(sub_jiffie_f >= cycles_per_jiffies)){ + sub_jiffie_f -= cycles_per_jiffies; + jiffies_f++; + } + while ((long)(jiffies_f - base->timer_jiffies) >= 0) { + #else while ((long)(jiffies - base->timer_jiffies) >= 0) { + #endif + struct list_head *head, *curr; + head = base->tv + + (base->timer_jiffies & NEW_TVEC_MASK); /* + * Note that we never move "head" but continue to + * pick the first entry from it. This allows new + * entries to be inserted while we unlock for the + * function call below. */ repeat: curr = head->next; if (curr != head) { void (*fn)(unsigned long); *************** *** 346,373 **** struct timer_list *timer; timer = list_entry(curr, struct timer_list, entry); - fn = timer->function; - data = timer->data; - - list_del(&timer->entry); - timer->base = NULL; - #if CONFIG_SMP - base->running_timer = timer; #endif - spin_unlock_irq(&base->lock); - if (!fn) - printk("Bad: timer %p has NULL fn. (data: %08lx)\n", timer, data); - else fn(data); - spin_lock_irq(&base->lock); - goto repeat; } ++base->timer_jiffies; - base->tv1.index = (base->tv1.index + 1) & TVR_MASK; } - #if CONFIG_SMP base->running_timer = NULL; - #endif spin_unlock_irq(&base->lock); } --- 480,547 ---- struct timer_list *timer; timer = list_entry(curr, struct timer_list, entry); + #ifdef CONFIG_HIGH_RES_TIMERS + /* + * This would be simpler if we never got behind + * i.e. if timer_jiffies == jiffies, we could + * drop one of the tests. Since we may get + * behind, (in fact we don't up date until + * we are behind to allow sub_jiffie entries) + * we need a way to negate the sub_jiffie + * test in that case... + */ + if (time_before(timer->expires, jiffies_f)|| + ((timer->expires == jiffies_f) && + timer->sub_expires <= sub_jiffie_f)) + #else + if (time_before_eq(timer->expires, jiffies)) #endif + {fn = timer->function; + data= timer->data; + + list_del(&timer->entry); + timer->base = NULL; + timer->entry.next = timer->entry.prev = NULL; + base->running_timer = timer; + spin_unlock_irq(&base->lock); fn(data); + spin_lock_irq(&base->lock); + goto repeat; + } + #ifdef CONFIG_HIGH_RES_TIMERS + else{ + /* + * The new timer list is not always emptied + * here as it contains: + * a.) entries (list size)^N*jiffies out and + * b.) entries that match in jiffies, but have + * sub_expire times further out than now. + */ + if (timer->expires == jiffies_f ){ + sub_jiff = timer->sub_expires; + } + } + #endif } ++base->timer_jiffies; } + /* + * It is faster to back out the last bump, than to prevent it. + * This allows zero time inserts as well as sub_jiffie values in + * the current jiffie. Did not work for the cascade as tv1.index + * also needs adjusting. + */ + --base->timer_jiffies; base->running_timer = NULL; + + IF_HIGH_RES(if (schedule_next_int( jiffies_f, sub_jiff, 0)){ + /* + * If schedule_next_int says the time has passed + * bump the tasklet lock so we go round again + */ + run_local_timers(); + }); + spin_unlock_irq(&base->lock); }