XEN-ARM定时器管理算法简要总结

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: XEN-ARM定时器管理算法简要总结

/*


XEN-ARM的定时器优先队列管理算法采用的是最小堆。关于最小堆的知识,请参考


《算法导论》第二版第6章堆。


下面是简要流程。欢迎讨论


*/


/*初始化定时器*/


void __init timer_init(void)


{


static struct timer *dummy_heap;


int i;


open_softirq(TIMER_SOFTIRQ, timer_softirq_action);


/*


* All CPUs initially share an empty dummy heap. Only those CPUs that


* are brought online will be dynamically allocated their own heap.


*/


SET_HEAP_SIZE(&dummy_heap, 0);


SET_HEAP_LIMIT(&dummy_heap, 0);


for ( i = 0; i < NR_CPUS; i++ )


{


spin_lock_init(&timers[i].lock);


timers[i].heap = &dummy_heap;


}


}


/*


当软中断发生时,函数执行


在定时器优先队列中查找满足expires的定时器,从队列中摘除,然后执行之


*/


static void timer_softirq_action(void)


{


int           cpu = smp_processor_id();


struct timer *t, **heap;


s_time_t      now;


void        (*fn)(void *);


void         *data;


DPRINTK(5, “%s:%dn”, __FUNCTION__, __LINE__);


spin_lock_irq(&timers[cpu].lock);


do {


heap = timers[cpu].heap;


now  = NOW();


//以此取定时器优先队列中最优先定时器


//然后执行其过程


while ( (GET_HEAP_SIZE(heap) != 0) && ( (t = heap[1])->expires < (now + (s_time_t)TIMER_SLOP) ) )


{


remove_entry(heap, t);


timers[cpu].running = t;


fn   = t->function;


data = t->data;


//printk(“fn:%x”, fn);


spin_unlock_irq(&timers[cpu].lock);


//执行定时器操作


(*fn)(data);


DPRINTK(5, “%s:%dn”, __FUNCTION__, __LINE__);


spin_lock_irq(&timers[cpu].lock);


/* Heap may have grown while the lock was released. */


heap = timers[cpu].heap;


}


timers[cpu].running = NULL;


}while ( !reprogram_timer(GET_HEAP_SIZE(heap) ? heap[1]->expires : 0) );//如果有定时器,小于now(),那么就继续loop


DPRINTK(5, “%s:%dn”, __FUNCTION__, __LINE__);


spin_unlock_irq(&timers[cpu].lock);


}


/*


Delete @t from @heap. Return TRUE if new top of heap.


摘除定时器会用到down_heap 和 up_heap来调整最小堆。


*/


static int remove_entry(struct timer **heap, struct timer *t)


{


int sz = GET_HEAP_SIZE(heap);


int pos = t->heap_offset;


//t->heap_offset


t->heap_offset = 0;


//–如果删除的元素是最后的,那么就不需要做调整啦~~,仅仅是heap-size减一就可以咯


if ( unlikely(pos == sz) )


{


SET_HEAP_SIZE(heap, sz-1);


goto out;


}


//–把最后一个元素填上来,这是最小堆的精髓!


heap[pos] = heap[sz];


heap[pos]->heap_offset = pos;


SET_HEAP_SIZE(heap, –sz);


//如果是中间节点,并且小于父母的,那么就需要up_heap


//如果是根结点,或者暂时不小于父母的,那么就是down_heap


if ( (pos > 1) && (heap[pos]->expires < heap[pos>>1]->expires) )


up_heap(heap, pos);


else


down_heap(heap, pos);


out:


return (pos == 1);


}


/* Float element @pos up @heap. */


static void up_heap(struct timer **heap, int pos)


{


struct timer *t = heap[pos];


//根节点的expires最小--


//具体算法是,自底向上,循环保证最小堆的性质


while ( (pos > 1) && (t->expires < heap[pos>>1]->expires) )


{


heap[pos] = heap[pos>>1];


heap[pos]->heap_offset = pos;


pos >>= 1;


}


heap[pos] = t;


t->heap_offset = pos;


}


/* Sink down element @pos of @heap. */


static void down_heap(struct timer **heap, int pos)


{


//自顶向下插入一个元素时的方法


int sz = GET_HEAP_SIZE(heap), nxt;


struct timer *t = heap[pos];


while ( (nxt = (pos << 1)) <= sz )


{


//nxt是left-subtree nxt+1是right-subtree


if ( ((nxt+1) <= sz) && (heap[nxt+1]->expires < heap[nxt]->expires) )


nxt++;//–better than the book of < the introduction of algorithm >


if ( heap[nxt]->expires > t->expires )//如果保证了最小堆,就是找到了~~


break;


heap[pos] = heap[nxt];


heap[pos]->heap_offset = pos;


pos = nxt;


}


heap[pos] = t;


t->heap_offset = pos;


}


/*下面附上相关的一些函数*/


/****************************************************************************


* HEAP OPERATIONS.


*/


#define GET_HEAP_SIZE(_h)     ((int)(((u16 *)(_h))[0]))


#define SET_HEAP_SIZE(_h,_v)  (((u16 *)(_h))[0] = (u16)(_v))


#define GET_HEAP_LIMIT(_h)    ((int)(((u16 *)(_h))[1]))


#define SET_HEAP_LIMIT(_h,_v) (((u16 *)(_h))[1] = (u16)(_v))


/****************************************************************************


* TIMER OPERATIONS.


*/


static inline void __add_timer(struct timer *timer)


{


static int tmp_count;


printk(“__add_timer:%dn”,tmp_count++);


int cpu = timer->cpu;


if ( add_entry(&timers[cpu].heap, timer) ){//如果是在最高优先级,那么就需要调用一下softirq


cpu_raise_softirq(cpu, TIMER_SOFTIRQ);


}


}


static inline void __stop_timer(struct timer *timer)


{


int cpu = timer->cpu;


if ( remove_entry(timers[cpu].heap, timer) )//如果删除了最优先的timer,才需要


cpu_raise_softirq(cpu, TIMER_SOFTIRQ);


}


static inline void timer_lock(struct timer *timer)


void set_timer(struct timer *timer, s_time_t expires)


{


unsigned long flags;


timer_lock_irqsave(timer, flags);


//现检测timer是否在队列中


if ( active_timer(timer) )


__stop_timer(timer);//从队列中除去先


timer->expires = expires;//更新expires


if ( likely(!timer->killed) )


__add_timer(timer);


timer_unlock_irqrestore(timer, flags);


}


void stop_timer(struct timer *timer)


{


unsigned long flags;


timer_lock_irqsave(timer, flags);


if ( active_timer(timer) )


__stop_timer(timer);


timer_unlock_irqrestore(timer, flags);


}


int reprogram_timer(s_time_t timeout)


{


s_time_t    now;


s_time_t    expire;


if ( timeout == 0 )


return 1;


now = NOW();


expire = timeout – now; /* value from now */


if ( expire <= 0 )


return 0;


return 1;


}

From Li Haifeng's Blog, post XEN-ARM定时器管理算法简要总结

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: