posix: time (#180)

Hi,

(this is a reply to a github notification)

I'll fix the swtimer (like discussed in one f2f meeting) to make the abstraction from cycles to seconds as easy as possible...next step.

this component should use one hwtimer to multiplex N swtimers on it.

I've put quite some thought in how to implement timers lately. I've even started with the API (cp hwtimer.h vtimer.h, s/hwtimer/vtimer/... :wink: ), realizing that we should really think it through this time.

There are two things that I think will be challenging:

1. How do we keep realtime characteristics? A simple priority queue for the timers will lead to O(n) runtime, so if we want our new timer to be THE timer the, e.g., drivers will use, this is not acceptable. Some clever data structure combined with maybe a limited number of timer slots will be necessary.

2. On which stack do we run the callback function of a timer? On most (all?) platforms so far, hwtimer executes the callback in interrupt context.

We might decide that this is fine for the next layer of abstraction. We might just execute the callback on the thread's stack.

We might also give the user the option to specify a callback stack for each timer or one shared one... This would also pave the road to POSIX like signals.

What do you think?

We've had utimers, swtimers, (I believe there was an mtimers), vtimers and now swtimers again. Let's do it right this time...

Kaspar

Hi Kaspar,

1. How do we keep realtime characteristics?

important issue.

+1

2. On which stack do we run the callback function of a timer?

I thought we agreed to remove functions like vtimer_set_cb() because firing callbacks from the timer interrupt are error prone and break the microkernel concept. Just firing messages and wakeup() should be sufficient.

We've had utimers, swtimers, (I believe there was an mtimers), vtimers and now swtimers again. Let's do it right this time...

Well, there are still plenty of letters left. :wink:

Cheers, Oleg

Hi Oleg,

2. On which stack do we run the callback function of a timer?

I thought we agreed to remove functions like vtimer_set_cb() because firing callbacks from the timer interrupt are error prone and break the microkernel concept. Just firing messages and wakeup() should be sufficient.

Did we? That would basically reduce timers to multiple timer_wait(). Quite different from what other timer APIs can do.

Makes implementation easier, though... :slight_smile:

We could pre-implement some kind of timer message multiplexing thread that fires the callbacks and so mimicks standard APIs using defined stacks etc. But stack space is expensive.

Something like:

vtimer_cb_thread() {   while(1) {     timer_msg = msg_receive();     timer = (struct timer*) timer_msg->cb;     timer->cb(timer->data);   } }

main() {   int timer_pid = vtimer_start_cb_thread(stacksize, priority);   vtimer_set(timer_pid, offset, timer);   [...] }

Thoughts?

Kaspar

Hey!

>I thought we agreed to remove functions like vtimer_set_cb() because firing >callbacks from the timer interrupt are error prone and break the >microkernel concept. Just firing messages and wakeup() should be >sufficient. Did we? That would basically reduce timers to multiple timer_wait().

I don't get it. Where's the big semantic difference between firing a callback and sending a message?

We could pre-implement some kind of timer message multiplexing thread that fires the callbacks and so mimicks standard APIs using defined stacks etc. But stack space is expensive.

I guess that's the current state of the art timer usage in RIOT. But I think you could mostly avoid this, if you design your system according to the microkernel paradigm right from the beginning. Nevertheless, we'll probably need this multiplexing thread to enable some standard APIs.

Cheers, Oleg

Hi,

Did we? That would basically reduce timers to multiple timer_wait().

I don't get it. Where's the big semantic difference between firing a callback and sending a message?

A message needs to be "polled" (msg_receive). A callback will be fired asynchronously.

First case: 1. set timer 2. do stuff 3. call msg_receive to see whether there's a message with might happen to be our timer-has-fired message.

Second case: 1. set timer 2. do stuff. If timer fires, the callback gets executed somehow somewhere.

You can implement 1. using 2. (have the callback just send a message), not the other way around without blocking in msg_receive in another thread.

Kaspar

Hi!

Second case: 1. set timer 2. do stuff. If timer fires, the callback gets executed somehow somewhere.

That's the point: if the callback get executed somehow somewhere anyway, why not just let a separate thread handle the timer?

A timer callback will always consume some stack space somewhere. Hence, in my opinion this option should be limited to hwtimer (e.g., kernel space), where you could expect a programmer to know what he does. If the user space programmer, using (u|sw|v|m|�)timer needs to take care of the stack space where the timer will get executed, it seems to be much less error-prone to me.

Cheers, Oleg

Hi!

Second case: 1. set timer 2. do stuff. If timer fires, the callback gets executed somehow somewhere.

That's the point: if the callback get executed somehow somewhere anyway, why not just let a separate thread handle the timer?

Well, once you have a listener, there's no semantic difference between a callback that gets directly executed and one that get's executed by a thread waiting for the message.

A timer callback will always consume some stack space somewhere. Hence, in my opinion this option should be limited to hwtimer (e.g., kernel space), where you could expect a programmer to know what he does. If the user space programmer, using (u|sw|v|m|�)timer needs to take care of the stack space where the timer will get executed, it seems to be much less error-prone to me.

Good if the user decides?

You have mostly convinced me.

If a programmer would know how much stack his callback needs, and that callback would be executed on his main stack, he'd need to reserve (maximum main stack usage + maximum callback stack usage) anyway. So the only overhead here is our thread overhead. (and IPC /context switch overhead for the actual messages).

Let's see if this is fast enough for those 99% of the use cases we're targeting at. :wink:

And then let's review all drivers and force our driver model on them, which includes that you have to use the "right" timers.

Kaspar

Hi,

the main advantage of an event to al callback is convinience and code structure. You can have the event handled in the same function that requested the timer. A callback allways goes into another function which will scatter your sourcecode. You are also losing local data.

Heiko

+1

And then let's review all drivers and force our driver model on them, which includes that you have to use the "right" timers.

Plus, we should provide a guideline.

Hi!

A simple priority queue for the timers will lead to O(n) runtime, so if we want our new timer to be THE timer the, e.g., drivers will use, this is not acceptable. Some clever data structure combined with maybe a limited number of timer slots will be necessary.

Do you have any data structure for that in mind? I guess, the perfect data structure would have similar characteristics to a hash table (insertion and search should be O(1)), but instead of searching a particular element we would need finding the minimum in O(1). For removing an arbitrary timer, a higher runtime might be acceptable.

Cheers, Oleg