Implementing user mode timers

[rdos]

How is this best done?

In kernel mode it's rather easy. My logic is part of the preemption timer which can either preempt the running thread or trigger a timer. However, the callbacks for kernel mode timers are asynchronous and cannot be used directly to implement user mode timers.

Also, the timers would be started in user-mode, and so ideally some user mode area would link timers in expire order and then the head element would do a wait until syscall which uses kernel mode timers.

A possible solution might be to start a new thread for timers and let it wait until the head element expires. When there are no timers, the timer thread could be terminated.

I think in Posix this is part of libc, but since I want to be able to use this without involving the runtime library (it would eventually be part of the new file API to force flush of files), and so it would need to be handled by the executable loader.

[Schol-R-LEA]

Just to clarify, could you provide a use case for how you want it to work?

Since you mentioned that the timer is asynchronous, my impression is that you intend to use it for event-driven code, in which a thread would set a timer, continue working on some task, then when the timer notification comes in it would interrupt the processing to service the timer event. Is this correct, or am I misconstruing the goal?

If this is the use case you have in mind, then the general solution is to have an event loop polling an event queue, either in a single thread which captures all of the events and handles them directly, or in a master thread which then dispatches various waiting threads to service the events.

Most libraries/languages which support event-driven programming (e.g., MFC, .Net, the various Java frameworks, etc.) hide this loop behind callbacks, but it is present.

I'm guessing that you already know all of this, but laying it out explicitly puts everyone on the same level.

Either way, it may not have the timing resolution you want, since it involves polling the event queue, and relies on the thread to pause periodically to handle the event loop. You could special-case timers to put them at the front of the event queue, but that still depends on how long the processing loop is.

If this is meant for a single specific case, you could tune it to have a reasonable timer resolution, but it would still require a polling loop. I'm not aware of any way to handle incoming events in purely userland threads without polling. Kernel threads could be a different story, but even then I think the asynchronous aspect (that of trying to process something until a timer goes off) would still require a polling loop.

A possible solution might be to start a new thread for timers and let it wait until the head element expires. When there are no timers, the timer thread could be terminated.

This would work, I think, but you would still have the problem of notifying the working thread that the timer it is waiting for has expired. It would help with the timing resolution, perhaps, but this would still require the operating thread to have an event loop with a very short operation time.

Of course, all of this is guesswork on my part, as we would need to know more about the intended use, and whether it is a one-off, a library for timers in general, or part of a general event-handling framework.

[nullplan]

However, the callbacks for kernel mode timers are asynchronous and cannot be used directly to implement user mode timers.

Why not? As long as you implement some "wait for timer" system call that suspends the calling thread until the timer hits, a synchronous approach can be implemented in asynchronous terms.

I think in Posix this is part of libc,

Partly. POSIX doesn't specify what's a system call and what a library call- Actually strike that: POSIX only specifies library calls, and the implementation is up to ... the implementation.

The most versatile timer API is timer_create(), which allows you to be notified via nothing, a signal, or a thread. In Linux, timer_create is a system call, but the thread creation stuff is implemented i userspace. So the system call only sends a signal, either to the process or the thread, and the library - if requested - creates a new thread to receive the signal. So hey, division of labor.

The way I plan on implementing timers in kernel space is by way of priority queue with callback. The PQ is ordered by deadline according to hardware counter. An interrupt is scheduled the next deadline. The interrupt handler executes all the callbacks of the timers that have elapsed. This way, sleep functions should be able to be implemented as functions that loop, calling the scheduler, until the callback is triggered. Thus the system call can be implemented in exactly the same way. The problem is going to be to implement all of this in an interrupt-safe manner.,

[rdos]

However, the callbacks for kernel mode timers are asynchronous and cannot be used directly to implement user mode timers.

Why not? As long as you implement some "wait for timer" system call that suspends the calling thread until the timer hits, a synchronous approach can be implemented in asynchronous terms.

Yes, this is how I implement WaitUntil and WaitMs. The thread starts a kernel timer and then gets blocked. The callback from the timer then wakes it up. A similar timeout can be used on general events, and then the callback with use the Signal function to wake up the thread. However, the timer callback is like an IRQ, and can happen at any time, even when the scheduler runs, and so cannot execute code that might block.

The way I plan on implementing timers in kernel space is by way of priority queue with callback. The PQ is ordered by deadline according to hardware counter. An interrupt is scheduled the next deadline. The interrupt handler executes all the callbacks of the timers that have elapsed. This way, sleep functions should be able to be implemented as functions that loop, calling the scheduler, until the callback is triggered. Thus the system call can be implemented in exactly the same way. The problem is going to be to implement all of this in an interrupt-safe manner.,

That's similar to how I do it. The timer callbacks can only do a few very restricted things, and should be kept short. Basically, the same thing that any IRQ can do. It can only interact with the scheduler by placing blocked threads in the "wake up" list, either directly or with Signal.

For multicore, each core has it's own PQ, and the core that starts the timer will use one of it's own local timers.

[rdos]

Just to clarify, could you provide a use case for how you want it to work?

Since you mentioned that the timer is asynchronous, my impression is that you intend to use it for event-driven code, in which a thread would set a timer, continue working on some task, then when the timer notification comes in it would interrupt the processing to service the timer event. Is this correct, or am I misconstruing the goal?

If this is the use case you have in mind, then the general solution is to have an event loop polling an event queue, either in a single thread which captures all of the events and handles them directly, or in a master thread which then dispatches various waiting threads to service the events.

Most libraries/languages which support event-driven programming (e.g., MFC, .Net, the various Java frameworks, etc.) hide this loop behind callbacks, but it is present.

No, that's not how I want it to work. This can easily be implemented without real timers. The only thing that is required is to have some form of timestamp function.

Either way, it may not have the timing resolution you want, since it involves polling the event queue, and relies on the thread to pause periodically to handle the event loop. You could special-case timers to put them at the front of the event queue, but that still depends on how long the processing loop is.

I don't want polling, and ideally, the solution should minimize syscalls too.

This would work, I think, but you would still have the problem of notifying the working thread that the timer it is waiting for has expired.

Not necessarily. It could also modify some shared variable or trigger a multiwait wakeup. In the file system case, a thread would write to a file, start a timer, write some more, retrigger the timer and so on until the timer expires and scans the memory mapped file for modified pages and writes them to disc. The same can be used with sockets, where timeouts typically cause things to be sent (I typically use a push method, but this is not part of the typical socket API). It's mostly this function I want. The problem is that it needs to be retriggered frequently without issuing syscalls more than sporadically.

It would help with the timing resolution, perhaps, but this would still require the operating thread to have an event loop with a very short operation time.

It's more a problem of being able to read the current timestamp without syscalls. This is because when you start a timer and you want it to expire in x ms, you will need the current timestamp and then you add the expire time to this and set the new expire timestamp for the timer. If the timestamp can be acquired without syscalls, then retriggering the timer will not require syscalls. The timer thread will wait for the earliest expire timestamp, and when it comes back it will read the expire timestamp again, and if it hasn't occurred yet, it will do another wait. The only case when the timer thread will need to be triggered directly is when a new earlier expire timestamp is added.

There is probably also a need for synchronizing the timers, but the futex-based "sections" I have will only do syscalls when there is contention, which should be the exceptional case.

So, the main problem is to create a millisecond timestamp that can be read from user mode. There is a kernel timestamp that the kernel timers update. The preemption timer for threads is one millisecond, and so the kernel timestamp should have at least one millisecond resolution even when only read. I think it should be possible to create a 4k page, map this in all user mode address spaces, and then write a copy of the kernel timestamp there every time it is updated.

[thewrongchristian]

It would help with the timing resolution, perhaps, but this would still require the operating thread to have an event loop with a very short operation time.

It's more a problem of being able to read the current timestamp without syscalls. This is because when you start a timer and you want it to expire in x ms, you will need the current timestamp and then you add the expire time to this and set the new expire timestamp for the timer. If the timestamp can be acquired without syscalls, then retriggering the timer will not require syscalls. The timer thread will wait for the earliest expire timestamp, and when it comes back it will read the expire timestamp again, and if it hasn't occurred yet, it will do another wait. The only case when the timer thread will need to be triggered directly is when a new earlier expire timestamp is added.

There is probably also a need for synchronizing the timers, but the futex-based "sections" I have will only do syscalls when there is contention, which should be the exceptional case.

So, the main problem is to create a millisecond timestamp that can be read from user mode. There is a kernel timestamp that the kernel timers update. The preemption timer for threads is one millisecond, and so the kernel timestamp should have at least one millisecond resolution even when only read. I think it should be possible to create a 4k page, map this in all user mode address spaces, and then write a copy of the kernel timestamp there every time it is updated.

I'm confused. How is the kernel supposed to know to trigger your user timer, if you're not prepared to tell the kernel about your desired timer with a syscall? How will your user process know when the timer has expired? Do you propose polling the mapped millisecond timestamp from user space? If the timer has not expired, what does your user process do? Sleep? Continue on doing whatever else it has to do?

[rdos]

I'm confused. How is the kernel supposed to know to trigger your user timer, if you're not prepared to tell the kernel about your desired timer with a syscall? How will your user process know when the timer has expired? Do you propose polling the mapped millisecond timestamp from user space? If the timer has not expired, what does your user process do? Sleep? Continue on doing whatever else it has to do?

A dedicated timer thread will be started as soon as a user timer is added. It will be waiting for the head timestamp to expire in kernel space (with a usual wait until). As long as the head timestamp is not decreased, other threads changing timers will not have to go to kernel space. To add a timer, the user mode visible timestamp is read and then the timeout is added, and a new timer is inserted. To change an already running timer, just update its expire timestamp. To remove a running timer just remove it. The only operation that requires syscalls is when there is contention for the timer structure, or when the head timestamp is decreased. When a more recent head timestamp is set the dedicated timer thread will need to be triggered (from kernel space with a Signal) so it can load the correct head timestamp and do a new wait until using the new timestamp.

[Schol-R-LEA]

I probably should have stuck to asking about the use case, rather than speculating about it. Could you tell us more about what you are trying to accomplish with this timestamp?

[rdos]

I probably should have stuck to asking about the use case, rather than speculating about it. Could you tell us more about what you are trying to accomplish with this timestamp?

Basically, it's what Posix timers call "thread notification" function. Link: https://man7.org/conf/lca2006/Linux_2.6 ... tmr_3.html

You set up a timer with a callback procedure, optional data to pass, and an expiration time (either absolute or relative). It should be possible to update the expiration time and to kill the timer before it expires. The system will create a thread (if it doesn't already exist) and then this thread will read the head timer and do a wait until using the expiration time. When it returns it will check for expired timers and "trigger" them by calling the callback function and remove them from active timers. It will then check the head timer again and either terminate or do another wait until with the new head timer.

Right now I have a functional interface to read the current timestamp (a 64-bit value) without syscalls with a precision of one millisecond. The value increases with the PIT frequency (1.193 MHz).

The primary usage case is to be able to automatically flush files without explicit calls to flush, and potentially to handle timeouts on sockets. Another usage case is to implement Posix timers.

[rdos]

This is getting interesting again. I think the idea to keep the list of timeouts in userspace would work well and reduce syscalls. The futex mechanism has been extended to kernel space too, so a kernel thread can acquire it and release it.

However, I foresee a more advanced function. I will want to be able to start timers from other processes too, with callbacks in kernel space. This will be needed for updating files, but also to force file descriptors to be flushed. The kernel timer list must be kept private in kernel space, as otherwise user space can add callbacks into kernel.

I think this function can also be used to send Posix signals from kernel space to specific processes, for instance the "kill" signal.

The server thread must run in the process to be able to easily access process memory, which means that the API must include process ID, and each process must have it's own thread.

The user timer list might contain an offset in user mode, a pointer and an expire time. The kernel timer list might contain a 48-bit kernel address, a pointer and an expire time. An alternative is to save CPU register state in the timer list entries. This is how I make server calls to the file system, and it has definite advantages over only using pointers. This interface also has well-tested code that queues requests in a 4k page. I could also use the "request code" idea so that one request code is start a timer with a timeout, and another might be flush a file descriptor or send a signal to the application.

Maybe the user mode timer list will only contain a pointer, callback and expire time, and a futex for inserting new entries. If the head is changed, then the server will need to be signalled (with a syscall), otherwise, no syscalls are required.

The kernel might use the register & request code approach, and then creates a private timer list with callback, CPU registers, a request code and expire time.

The server thread must process the request list in kernel, and check the head timeout in kernel and user space. If all of those are idle, it will start a wait with the most recent expire time.

[rdos]

There is an obvious optimization that can be made. If the server thread polls the request queue periodically, like with a 100 ms interval, then queue entries that expire further into the future than 100 ms (or maybe 90 ms to be safe), don't need to be signaled. This method would preferently be implemented with a FIFO queue in user space, not a time-order sorted list. The server thread then can maintain a kernel mode timer list that combines user mode and kernel mode requests in a time-ordered sorted list.

There also is a need to be able to retrigger a timer. To identify a timer, the caller would include an ID, which could be the address of the timer struc or object. To retrigger, there is a need for another list of active timers with their IDs and expire times. The retrigger function would then search the list of active timers to find out if it has expired, in which case the function would return failure and exit. If the timer is found, the expire time would be examined. If it is more than 100 ms into the future then the entry can safely be added to the FIFO, otherwise a syscall would be performed that either updates the timer or returns failure.

Stopping a timer would be similar to retriggering. The same method can be used.