Re: [Xen-devel] [PATCH 0/2] range timer support

["Yu Ke" <mr.yuke@xxxxxxxxx>]

2008/10/28 Keir Fraser <keir.fraser@xxxxxxxxxxxxx>:
> On 28/10/08 06:57, "Yu, Ke" <ke.yu@xxxxxxxxx> wrote:
>
> You'll have to explain how the implementation in timer.c works. I'm not sure
> I believe it really does.
>
>  -- Keir
>

Oh, fair enough. Let me explain how the range timer is implemented.

Basically, the timer softirq handler (timer_softirq_action) need to do
two tasks: execute the expired timer and find the nearest unexpired
timer deadline to reprogram the hardware timer (local APIC timer in
x86).

Currently, the timer deadline is single point, and these two tasks are
accomplished with the help of timer heap. The timer heap is ordered by
the timer deadline, and the first element of the heap always has the
nearest deadline. So the two tasks can be done by continuously picking
the first element. If the element is expired, then execute. If the
element is not expired, then the nearest unexpired deadline is found.

Things become a little bit complicated when the timer link list is
introduced. Link list is used to store the timer when heap is out of
memory. So timer softirq handler need to firstly allocate heap memory
and move the timer from link list back to heap, then the rest
processing is the same as before. if there is still timer in the link
list after the processing, softirq timer handler need to do one more
thing: go through the link list one by one to execute the expired
timer and find the nearest timer deadline.

With the range timer introduced, the timer deadline becomes a range,
saying [Tstart, Tend], the timer can be executed at any time in
[Tstart,Tend]. Firstly, let's see how the nearest deadline is
calculated. We still let the timer heap be ordered by Tstart, i.e.
Timer heap is organized as [Ts1, Te1], [Ts2, Te2], …, [TsN,TeN], where
Ts1<Ts2<… <TsN. And the nearest deadline range [Ts', Te'] =
intersection of [Ts1, Te1] [Ts2, Te2] … [TsK, TeK], where K is the
largest integer that [Ts', Te'] is not NULL.
For example, if there are 4 timers:
    T1=[100, 103], T2=[101, 104], T3=[102,104], T4=[104, 106],
Then the nearest deadline range is:
    [Ts',Te'] = [102, 103], i.e.  Intersection of T1, T2, T3. (if T4
is added, [Ts' Te'] will become NULL),
and the timer T1, T2, T3 can executed in range [102, 103].

The following code from range-core.patch do the things above:
+    start = 0;
+    end   = STIME_MAX;
+    while ( (GET_HEAP_SIZE(heap) != 0) &&
+            ((t = heap[1])->expires <= end) )
+    {
+        remove_from_heap(heap, t);
+
+        start = t->expires;
+        if ( end > t->expires_end)
+            end = t->expires_end;
+
+        t->list_next = ts->ready_list;
+        ts->ready_list = t;
+        t->status = TIMER_STATUS_in_ready_list;
+    }
+    this_cpu(timer_deadline) = (start + end) / 2;
Note that the timer T1, T2, T3 are removed from heap during the
calculation, so a ready list is added in "struct timers" to store
these ready timers, so that these timers can be executed  once the
deadline is reached.

If there is link list timer, we need to move the link list timer to
heap first.  If there is ready timer, we also need to move the ready
timer to heap first. Heap memory is reallocated if necessary.

queue_ready_timer() do the things mentioned above.

Another thing is to execute the expired timer.  The only extra thing
is to execute the ready timer; the rest is similar as the original
code path.

That is all the required change, not so complicated as it looks, right :)

Best Regards
Ke

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxxxxxxxx
http://lists.xensource.com/xen-devel