????2??__mod_timer(timer??expires?? false?? TIMER_NOT_PINNED);
???????????????????
timer->expires = expires;
if (time_before(timer->expires?? base->next_timer) &&
!tbase_get_deferrable(timer->base))
base->next_timer = timer->expires;
internal_add_timer(base?? timer);
internal_add_timer(base??timer);???????????????????
static void internal_add_timer(struct tvec_base *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->timer_jiffies & TVR_MASK);
} else {
int i;
/* If the timeout is larger than 0xffffffff on 64-bit
* architectures then we use the maximum timeout:
*/
if (idx > 0xffffffffUL) {
idx = 0xffffffffUL;
expires = idx + base->timer_jiffies;
}
i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
vec = base->tv5.vec + i;
}
/*
* Timers are FIFO:
*/
list_add_tail(&timer->entry?? vec);
}
????internal_add_timer?????????????
????1??
????<span style="font-family:'Liberation Serif'?? serif;">        unsigned long expires = timer->expires;
????unsigned long idx = expires - base->timer_jiffies;
????struct list_head *vec;</span>
????unsignedlong expires = timer->expires;?????????????????
??????base->timer_jiffies????????????????????絽?????
???????unsignedlong idx = expires - base->timer_jiffies;
?????????????????????2??????????????絽????????????????????????
????????????????????????????????С??????????????????
????2??
<span style="font-family:'Liberation Serif'?? serif;">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->timer_jiffies & TVR_MASK);
} else {
int i;
/* If the timeout is larger than 0xffffffff on 64-bit
* architectures then we use the maximum timeout:
*/
if (idx > 0xffffffffUL) {
idx = 0xffffffffUL;
expires = idx + base->timer_jiffies;
}
i = (expires >> (TVR_BITS + 3 * TVN_BITS)) & TVN_MASK;
vec = base->tv5.vec + i;
}</span>
??????????????idx???????????????????ò????????????????????У?tv1--tv5.
??????????????????idx= 240??????????????????????????256??jiffies??λ?л??????????????tv1?У?
????if(idx < TVR_SIZE) {
????inti = expires & TVR_MASK;
????vec= base->tv1.vec + i;
????}
???????idx??256??19384???????????tv2?У?
????elseif (idx < 1 << (TVR_BITS + TVN_BITS)) {
????inti = (expires >> TVR_BITS) & TVN_MASK;
????vec= base->tv2.vec + i;
????}
??????(expires>> TVR_BITS) & TVN_MASK??????????????tv2?μ??????????С?
?????????????
???????????????????????????idx?????С???????????tv1--tv5????????????????????????????
?????????С     ?????????????????
????tv1?? 256                           1
????tv2?? 64                             2<<8 =256
????tv3?? 64                             2<<(8+6)= 16384
????tv4?? 64                             2<<(8+2*6)=1048576
????tv5?? 64                             2<<(8+3*6)=67108864
??????tv1?У?????????????????????????????
????????tv2?У?64?????????е?????????ж????????256??????????????????????????????????????????????ж?????????
???????????Щ?????????????????tv2?е??????????е?????????ж??????????????????е????????????????С??????????????е??????е???????????????????tv1?е?????<tv2<tv3<tv4<tv5.
?????????????????????2^32?????Χ???????????256+64+64+64+64 = 256 ?????????
????3??list_add_tail(&timer->entry??vec);
??????????????timer?????list_head??entry???????????????timer????vec??β????
???????????????????????????????????:
????????????????????????????????????????ж????????
????run_timer_softirq
/*
* This function runs timers and the timer-tq in bottom half context.
*/
static void run_timer_softirq(struct softirq_action *h)
{
struct tvec_base *base = __get_cpu_var(tvec_bases);
hrtimer_run_pending();
if (time_after_eq(jiffies?? base->timer_jiffies))
__run_timers(base);
}
if(time_after_eq(jiffies?? base->timer_jiffies))
__run_timers(base);
?????????????jiffies????????base->timer_jiffies(?????????е??絽?????)?????????__run_timers(base);
???????????????????￡?
????/**
????*__run_timers - run all expired timers (if any) on this CPU.
????*@base: the timer vector to be processed.
????*
????*This function cascades all vectors andexecutes all expired timer
????*vectors.
????*/
????__run_timers?????е????????????????????е??????????????
????__run_timers????к??????￡?
pin_lock_irq(&base->lock);
while (time_after_eq(jiffies?? base->timer_jiffies)) {
struct list_head work_list;
struct list_head *head = &work_list;
int index = base->timer_jiffies & TVR_MASK;
/*
* Cascade timers:
*/
if (!index &&
(!cascade(base?? &base->tv2?? INDEX(0))) &&
(!cascade(base?? &base->tv3?? INDEX(1))) &&
!cascade(base?? &base->tv4?? INDEX(2)))
cascade(base?? &base->tv5?? INDEX(3));
++base->timer_jiffies;
list_replace_init(base->tv1.vec + index?? &work_list);
while (!list_empty(head)) {
void (*fn)(unsigned long);
unsigned long data;
timer = list_first_entry(head?? struct timer_list??entry);
fn = timer->function;
data = timer->data;
timer_stats_account_timer(timer);
set_running_timer(base?? timer);
detach_timer(timer?? 1);
spin_lock_irq(&base->lock);
???????????????????????ж??
????????while???while(time_after_eq(jiffies?? base->timer_jiffies))
??????base->timer_jiffies????jiffies???while???????????
????????????????????裺
????A?? structlist_head work_list;
????struct list_head *head =&work_list;
????intindex = base->timer_jiffies & TVR_MASK;
???????base->tv1?е?????index?????index???????0?????tv1?и?????????
?????????й?????????tv2?н?base->tv2.vec+1?????е??????????tv1?У?????????????????tv2?е?1????У?????????256??511?????????tv2?????????0???????63????????tv1?а???0??255??????tv2???0???????????????????????????tv2 tv3 tv4???0??????????ж????????????????????????????????????hash??????????????0;??????????????tv3?е????????16k = 63*256 ??tv2??63?????+ 256*1??tv1??256???????
?????????????????????__run_timers???tv2?????????????????tv1?У????????????????????
?????????index??tv1??????
????INDEX(0)??tv2??????
????INDEX(1)??tv3??????
????INDEX(2)??tv4??????
????INDEX(3)??tv5??????
????????INDEX????壺
????#defineINDEX(N) ((base->timer_jiffies >> (TVR_BITS + (N) *TVN_BITS)) & TVN_MASK)
??????????index???÷?????????
??????tv2?????????????????tv1??????casecade?????????
cascade(base??&base->tv2?? INDEX(0))
staticint cascade(struct tvec_base *base?? struct tvec *tv?? int index)
{
/*cascade all the timers from tv up one level */
structtimer_list *timer?? *tmp;
structlist_head tv_list;
list_replace_init(tv->vec+ index?? &tv_list);
/*
* We are removing _all_ timers from the list?? so we
* don't have to detach them individually.
*/
list_for_each_entry_safe(timer??tmp?? &tv_list?? entry) {
BUG_ON(tbase_get_base(timer->base)!= base);
internal_add_timer(base??timer);
}
returnindex;
}
??????????tv2?е???????????tv1?????????????INDEX(0)??1??
????list_replace_init(tv->vec+ index?? &tv_list);
??????????????tv2????????????????
????list_for_each_entry_safe(timer??tmp?? &tv_list?? entry) {
????BUG_ON(tbase_get_base(timer->base)!= base);
????internal_add_timer(base??timer);
????}
??????????????????????????????????????????????????????
????????????????
???????tv1?а????????256????????????????????tv2????????????????256—512???????????????????????????tv1?е?????????????????????tv2?е??????е????????????256?????????????????
?????????internal_add_timer(base??timer);?????и???idx???????????????tv???????????????????????????tv1?С?
???????????????????????????tv3?е????????????tv1??tv2?У??????????
???????????????????????
????B??++base->timer_jiffies;???1??
????C??list_replace_init(base->tv1.vec+ index?? &work_list);//??????????????tv1?е???????????????????????
????while(!list_empty(head)) {
????……
????}
??????????index????????base->tv1.vec+ index????256????е?????????while???????????е??????й???????????????
????{
????void(*fn)(unsigned long);
????unsignedlong data;
????timer= list_first_entry(head?? struct timer_list??entry);
????fn= timer->function;
????data= timer->data;
????timer_stats_account_timer(timer);
????set_running_timer(base??timer);
????detach_timer(timer??1);
????……
????trace_timer_expire_entry(timer);
????fn(data);
????trace_timer_expire_exit(timer);
????timer= list_first_entry(head?? structtimer_list??entry);??????container_of??????????list_head???????????????
????fn = timer->function;
????data= timer->data;
????fn??data?????????????趨??????????
????detach_timer(timer??1);?????????????????????
????fn(data); ????fn(timer->function )????;
????????????????ж?????????????hash??linux????е?????????????????????????????????????????????????????????????????????????????
?????????????+??????????hash????????????????????????????????????????
????????????blog???????????ο??????????д?????????????
????linux2.6??????????????????
????linux ??????? timer_list???
????????????????????????????????????????????????????????????ο???????????￡?
????Linux ?????????????????
????kernel/timer.c designIngo Molnar ?? linux ?е????????????????????
????Linux??????????????????single-shottimer??????timer??????????????????????timer?????????????repeatingtimer???????????????????????????????????????????????????????????????????????????????????????????????????