[En-Nut-Discussion] RFC - Redesigning Timer Interrupt Processing

[Harald Kipp]

Hi all,

This is based on a long phone call I had with Matthias Ringwald
a few months ago and on several emails with him and other people.

The current situation (Nut/OS 3.9.7):
-------------------------------------

The timer interrupt routine processes the nutTimerList, a linked
list of NUTTIMERINFO structures. This list is sorted by
the time at which the timers will elapse, with the shortest
time on top. Let's assume we have three timers, two of them
will elapse after 5 ticks, the third after 7 ticks. Then
the list will contain:

Timer-1: 5 Ticks
Timer-2: 0 Ticks
Timer-3: 2 Ticks

As we can see, each timer is entered with the remaining
period, the number of ticks left after all timers, which
are in front, will have been elapsed.

This way, only the top entry needs to be decremented.
If its counter value reaches zero, it is removed from the
list. If the next entry is zero too, it will also be removed...
and so on. This removal is non-deterministic, as it depends
on the number of timers, which will elapse at the same time.

The removal itself is even worse. Each timer is associated
to a callback function, which is called during removal.
For example, if an application directly or indirectly calls
NutEventWait() with a time out value, then a new entry is
added to the timer list with NutEventTimeout() as the callback.
The processing of this function depends on the number of
threads and the priority of the thread, which called
NutEventWait(). Furthermore, the application can provide its
own callback, in which case the required processing is out of
control for Nut/OS.

So far we looked to one-shot timers. Periodic timers are
re-inserted after they elapsed. Re-inserting timers is,
you guessed it, non-deterministic regarding processing time.

And all this happens in interrupt context, blocking any other
interrupt.

Finally, NUTTIMERINFO structures are allocated from heap. Thus,
the interrupt routine is not allowed to free it. Instead,
one-shot timers are added to a second list, named nutTimerPool.
These structures will be re-used, when a new timer is created.

Bored? OK, let's turn to the interesting stuff.


Proposal for new timer handling:
--------------------------------

Instead of removing all elapsed timers, only the first one will be
removed. If all timers in the list with equal life periods are
sorted by priority, this is just fine. However, the NUTTIMERINFO
doesn't contain the priority of the thread.

When a timer elapses, one has to walk to the list of threads to
find the one that is currently associated to this timer.

Adding a pointer to the NUTTHREADINFO structure will help in both
function.

Instead of calling the callback and instead of re-inserting periodic
timers, the NUTTIMERINFO structure will be removed from the list
and added to nutTimerPool only. Because of cooperative multithreading,
all other required processing can be delayed until the currently
active thread is willing to give up the CPU. This way, all
non-deterministic functions are moved away from interrupt context
to NutThreadResume().

The final timer interrupt routine will look like

static void NutTimerIntr(void *arg)
{
     nut_ticks++;
     if (nutTimerList) {
         if (nutTimerList->tn_ticks_left) {
             nutTimerList->tn_ticks_left--;
         }
         if (nutTimerList->tn_ticks_left == 0) {
             NUTTIMERINFO *tnp = nutTimerList;
             nutTimerList = nutTimerList->tn_next;
             tnp->tn_next = nutTimerPool;
             nutTimerPool = tnp;
         }
     }
}

Note too, that just one tick counter is used (see my previous
post). Now it is possible to simply calculate the worst case
processing time of the timer interrupt handler.

Now the bad part. Since its first release, Nut/OS provides
NutTimerStart() and offers the capability to specify custom
callback functions. For example, os/msg.c uses this and it can
be assumed, that several applications are using it. Removing
the callback from interrupt processing may break these applications.

One option may be to make this a configurable preprocessor macro
and optionally compile Nut/OS with or without callbacks in interrupt
context. I'd like to avoid this. It adds complexity to release
testing.

Another option is, to create a completely new set of functions
for exclusive use by the kernel. In this case the old NutTimerStart()
may set an additional flag in NUTTIMERINFO, which the new one,
e.g. NutSysTimerStart() won't. For all flagged timers, interrupt
processing is passed to the old (slightly modified) interrupt
handler. This way deterministic interrupt handling is maintained
for applications, which do not call NutTimerStart() themselves.

May be it is even possible to enhance the old style timer routines
towards a more general timer API, like Ole suggested.

That's it for today,
Harald