Hardware timer per thread?

[robfinch]

Contemplating the use of hardware timers. How many timers is enough? I think this can be done in hardware. If they had a pre-scaler they do not all have to operate in parallel. For instance, if pre-scaled by 32, 32 parallel hardware timers could be turned into 1024 timers using dedicated RAM to keep track of the counts and sequencing through the timers using the 32 pre-scaler counts. A larger pre-scale and more RAM would allow more timers. Would a timer per thread be enough?
Pre-scaling could affect the timer resolution, but would still allow high-resolution.

[rdos]

Contemplating the use of hardware timers. How many timers is enough? I think this can be done in hardware. If they had a pre-scaler they do not all have to operate in parallel. For instance, if pre-scaled by 32, 32 parallel hardware timers could be turned into 1024 timers using dedicated RAM to keep track of the counts and sequencing through the timers using the 32 pre-scaler counts. A larger pre-scale and more RAM would allow more timers. Would a timer per thread be enough?
Pre-scaling could affect the timer resolution, but would still allow high-resolution.

I think you are too much influenced by the BIOS timer which is implemented with the PIT. This kind of timers are not good for anything. You get one tick every 1/18.2 seconds, but the PIT has microsecond resolution. For timers, you either need one per system or one per processor core, the latter being optimal. Then you keep a list of active timers per system or per core. The API would have a timeout time (in whatever resolution you desire, like PIT tics, nanoseconds) and a callback. The OS then starts the timer (if the request is at the head) by programming the hardware timer. When the timer IRQ happens, the callback is called (in the IRQ context). This provides microsecond resolution using the PIT. Then there is also another user case: You want to know elapsed time. This is best implemented by having a three-running counter/timer per system, like the HPET, but the PIT can be used too. You read the timer in the API and then add to an accumulated count. No IRQ is required, as the accumulated count can be updated in the scheduler to avoid timer/counter wrap. This too can be implemented with microsecond resolution (with PIT), or nanosecond with better timers.

[robfinch]

I was thinking of timers with micro-second or better resolution. For instance, with a 100 MHz base clock the clock can be divided (scaled) by 100 and still have micro-second resolution.

The appeal of having a large number of timers is that there are no lists to manage. I think it would be possible that the OS does not need to manage the timers in the same manner.

It might be possible to have a callback directly into the app, with the app managing the timer. Sleep(timeout, callback). TimeThis(signal, callback). Although the OS would still need to be present.

I have been trying to move some of the OS functions into hardware. It may help to get rid of the timer lists.

[nullplan]

Have you guys ever heard of the LAPIC timer? It is a timer that runs on each thread separately, and runs as fast as the TSC. It has also been the standard way of interrupting a core in a time-based way for decades now.

[robfinch]

Yes, I read of the LAPIC a while ago. I think there is only one timer per hardware thread (processing core / CPU) for the LAPIC. I was referring to a timer per software thread. I should have been more specific. The system is running a custom (hobby) based system, no LAPIC available. The hardware is all on one FPGA chip. CPU / chipset varies. Current rendition is for a 68010 CPU.

[rdos]

I reasoned based on existing x86 hardware. Then you need to have a software API that doesn't depend on the hardware it runs on. If the LAPIC is available, it's the best choice.

If you are creating an FPGA solution (like I've done too), then you can have any number of timers. Just create the clocks you need for your application, either in hardware (Verilog/VHDL) or export them to processor implementations.

Still, I don't see the utility of this. In the FPGA, you just add a register and count down to create a "timer". In my old design, everything is Verilog, and then data is exported via PCIe to a standard PC. This implementation doesn't use timers; instead, it operates with IRQs delivered via PCIe. The analysis application does use timers, but that's standard OS timers. In my new FPGA using a Xilinx Zynq core, I have a real-time dual-core ARM processor. My idea is that it will poll hardware registers implemented in Verilog, and will not have any timers either. It will be entirely event-based. There is also a quad-core ARM processor where I will run AMDs(Xilinxs) Linux implementation. It will not have any dedicated timers from the FPGA, rather will operate like a typical memory mapped device. The real-time processor will create memory mapped requests that are then served under Linux. For this application microsecond timers are not enough, not even nanosecond. Instead, I will use a 64-bit free-running counter that is incremented at 500 MHz, and which also has eight "sub-tics" since the ADC runs are 4 GHz. Samples will be tagged using this counter and when they are analysed the timing information will refer to the sampling counter.

[rdos]

Have you guys ever heard of the LAPIC timer? It is a timer that runs on each thread separately, and runs as fast as the TSC. It has also been the standard way of interrupting a core in a time-based way for decades now.

Earlier versions of the LAPIC were quite problematic given that their frequency depended on the CPU core frequency. On those CPUs, the LAPIC cannot be used even if it is present. Also, for x86 OSes, you need to consider hardware with only PIT.

[Octocontrabass]

I was referring to a timer per software thread.

That seems like it would be too many timers (or not enough software threads).

What's your plan for a thread that wants two timers? What are you going to do with all the extra timers when most threads don't use them?

[nullplan]

I was referring to a timer per software thread. I should have been more specific.

Octo already asked the "but why?" question. Let me expand upon it: You can just collect all things that need timeouts into a priority queue sorted by deadline. Then in the timer interrupt, you dequeue all elements whose deadlines have passed (that is, you dequeue-min until the minimum element has a deadline in the future) and execute their callback functions. That way, more than one timer interrupt source is just unnecessary, although it might be nice to spread the load.

Oh, and try to maintain the system time from hardware counters like the TSC or such, that way you don't need to count timer interrupts.

Earlier versions of the LAPIC were quite problematic given that their frequency depended on the CPU core frequency. On those CPUs, the LAPIC cannot be used even if it is present.

Right, in that case the LAPIC timer cannot be used to interrupt at a certain real time in the future. However, the LAPIC timer can still be used as scheduler tick, because if a task is active, the CPU isn't sleeping, and so neither is the TSC. And on multi-core systems, using the LAPIC timer for this is nicer than the PIT, because the latter leads to a bucket chain (where the PIT interrupts some core which then has to send an IPI to the correct core). It's not awful, just not as nice as it could be.

Also, for x86 OSes, you need to consider hardware with only PIT.

Well, if you want to be technical about it, x86 is only the CPU architecture, and nothing obligates the machine in question to follow ISA guide lines. See for example the PlayStation 4, an x86 computer that is so definitely not an ISA PC they had to massively patch the Linux kernel to get it to run on there. That was also because Sony made some boneheaded decisions, but I distinctly remember the lack of PIT being one thing they had to address.

Which is to say, you also need to consider the case where you don't have a PIT and need some other known-frequency timer source to calibrate the TSC.

[robfinch]

What's your plan for a thread that wants two timers? What are you going to do with all the extra timers when most threads don't use them?

I was going to have a pool of timers that threads could allocate from. Timers and threads do not have to be 1:1 mapped. I do not know how many timers are typically used in a system, what the ratio is. I was going to have threads open '/dev/timer' and get a handle to a timer. A thread would be able to open more than one timer, or not open any at all.

The extra timers can sit there idle. There would be fewer real timers since the counts are being maintained in a RAM. 32 timers sequenced 32 times could give 1024 timers. The real timers could sit in a low power sleep mode if not needed.

Octo already asked the "but why?" question. Let me expand upon it: You can just collect all things that need timeouts into a priority queue sorted by deadline. Then in the timer interrupt, you dequeue all elements whose deadlines have passed (that is, you dequeue-min until the minimum element has a deadline in the future) and execute their callback functions. That way, more than one timer interrupt source is just unnecessary, although it might be nice to spread the load.

That is close to the way the system currently works. I just saw the possibility of having loads of timers and wondered if it could be done differently. If timer handling in the OS can be made simple enough, it could use hardware. The OS currently has a timeout list sorted by timeout. It decrements the timer for the top thread, popping the timeout list if the timeout expired. Timeouts are stored as deltas compared to the previous thread. It does not jump to a callback routine, it just resumes the thread from where the timeout was requested. (sleep(),waitmsg())

[nullplan]

he OS currently has a timeout list sorted by timeout. It decrements the timer for the top thread, popping the timeout list if the timeout expired.

That's why I was suggesting a priority queue. If you worry about having loads of timers, then the complexity of handling the queue is going to be important. What you are describing, even if you avoid the pitfalls, still has at least O(n) insert time and O(1) dequeue-min time. While a priority queue has O(log n) for both.

It does not jump to a callback routine, it just resumes the thread from where the timeout was requested.

Well, I was thinking of a more general system to do timed work, not just unblocking threads. Because you sometimes need to do some things with timing in drivers, for example. Often enough, a timeout is needed to abort a transfer if the hardware doesn't want to cooperate.

[robfinch]

Well, I was thinking of a more general system to do timed work, not just unblocking threads. Because you sometimes need to do some things with timing in drivers, for example. Often enough, a timeout is needed to abort a transfer if the hardware doesn't want to cooperate.

I have added alarms to the OS which may call a callback function and/or send a message to a given mailbox on timeout. A second timer was used with a priority queue. To perform the callback function, the process id (app id) and the MMU page directory need to be set to values corresponding to the memory map of the callback. Or the callback could be limited to using only kernel memory.

How are callbacks restricted from taking up too much time? If there are a lot of callbacks with time consuming code, the ISR could take a long time.

That's why I was suggesting a priority queue. If you worry about having loads of timers, then the complexity of handling the queue is going to be important. What you are describing, even if you avoid the pitfalls, still has at least O(n) insert time and O(1) dequeue-min time. While a priority queue has O(log n) for both.

Not sure about the need for priority queues with O(n) insert time with loads of timers (LOT). I was not going to insert the timers into any queues. I think each timer could individually manage the callback. The timer has a associated callback register, and the timer ISR knows which timers timed-out. I think this could be handled by examining the timeout status register in the timer controls and invoking the callback for each timed-out timer. There are no priority queues because each timer counts the full timeout required.

[thewrongchristian]

Well, I was thinking of a more general system to do timed work, not just unblocking threads. Because you sometimes need to do some things with timing in drivers, for example. Often enough, a timeout is needed to abort a transfer if the hardware doesn't want to cooperate.

I have added alarms to the OS which may call a callback function and/or send a message to a given mailbox on timeout. A second timer was used with a priority queue. To perform the callback function, the process id (app id) and the MMU page directory need to be set to values corresponding to the memory map of the callback. Or the callback could be limited to using only kernel memory.

How are callbacks restricted from taking up too much time? If there are a lot of callbacks with time consuming code, the ISR could take a long time.

I wouldn't advocate calling callbacks in the ISR at all.

I would recommend a timer thread, which just waits for the timer interrupt to trigger, and when triggered, the ISR just unblocks the timer thread.

The timer thread then handles are pending timers whose timeout have expired, then re-triggers the timer for the next new head of the list.

Having the timers on a separate thread is also more likely to move the thread between cores, if your kernel is so inclined, rather than hitting any particular core that services the timer interrupt.

This is actually how I handle all my interrupts. The ISR does very little, generally just resuming some high priroty thread to handle most of the interupt. The only processing my timer interrupt does in the ISR is atomically update a time of day counter (as well as resuming the timer thread.)

That's why I was suggesting a priority queue. If you worry about having loads of timers, then the complexity of handling the queue is going to be important. What you are describing, even if you avoid the pitfalls, still has at least O(n) insert time and O(1) dequeue-min time. While a priority queue has O(log n) for both.

Not sure about the need for priority queues with O(n) insert time with loads of timers (LOT). I was not going to insert the timers into any queues. I think each timer could individually manage the callback. The timer has a associated callback register, and the timer ISR knows which timers timed-out. I think this could be handled by examining the timeout status register in the timer controls and invoking the callback for each timed-out timer. There are no priority queues because each timer counts the full timeout required.

So, to avoid an O(n) insert time, you want the ISR to do an O(n) search of outstanding timers looking for expired timers?

If that is the case, stop now, and rethink.

You want the ISR code as lean as possible, to do as little work as possible.

You'll be triggering timeouts regularly, and with a sorted priority queue, you'll only have to examine as many timers (+1) that have expired, stopping at the first timer that has not expired.

And maintaining a sorted priority queue need not be O(n) for insert. You can use any fully or partially sorted structure to make inserts efficient O(log n) if your n is large. You can use a binary heap or binary search tree for that.

https://en.wikipedia.org/wiki/Binary_heap

But, you could also just use a sorted array, and suck up the O(n) insert, to be blazing fast and simple in the ISR (where performance actually really matters.)

Whatever you choose, you'll likely only have a single interrupt source, per CPU certainly, but perhaps per system, so you've going to have to multiplex that single timer at some point.

[robfinch]

wouldn't advocate calling callbacks in the ISR at all.

I would recommend a timer thread, which just waits for the timer interrupt to trigger, and when triggered, the ISR just unblocks the timer thread.

Yeah, that is what I was thinking by providing a mailbox to send a message to on timeout. A timer thread would block on a waitmsg() then become unblocked by the postmsg() in the timer ISR. Callbacks seem pretty risky to me, who knows what might end up in the callback routine.

So, to avoid an O(n) insert time, you want the ISR to do an O(n) search of outstanding timers looking for expired timers?

Yes, it is an O(n) search but I think it could be done extremely fast. 1024 timers could be represented by 32 32-bit timeout status flags. It is just a matter of searching 32 regs for a non-zero status indicating a timer timed out. It may also be possible to have hardware accelerate the bit search, so it would just be a loop for how many ever timers expired. Another possibility may be to have a separate interrupt ISR for each timer. Then there would be no need to search. But that is a lot of ISRs.

[nullplan]

I have added alarms to the OS which may call a callback function and/or send a message to a given mailbox on timeout. A second timer was used with a priority queue. To perform the callback function, the process id (app id) and the MMU page directory need to be set to values corresponding to the memory map of the callback. Or the callback could be limited to using only kernel memory.

Yes, I am using that last one. The callbacks can only use kernel memory.

How are callbacks restricted from taking up too much time?

By avoiding any operation that may block for a long time. No sleeping, no taking mutexes. At most, taking a spinlock (those aren't meant to be held for long). But if you want some technical means to prevent them from overrunning, then I have none.

Not sure about the need for priority queues with O(n)

Look again, the O(n) was for the "sorted queue" you wrote about. Priority queues have O(log n) for both insert and dequeue-min.

wouldn't advocate calling callbacks in the ISR at all.

I would recommend a timer thread, which just waits for the timer interrupt to trigger, and when triggered, the ISR just unblocks the timer thread.

Those are just threaded interrupt handlers, and yes, that is a great interrupt handling model.

Callbacks seem pretty risky to me, who knows what might end up in the callback routine.

I do. I develop the kernel, I know what that callbacks can and cannot do.