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:%d\n", __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:%d\n", __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:%d\n", __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:%d\n",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;

}