OSDev.org

The Place to Start for Operating System Developers
It is currently Thu Mar 28, 2024 12:44 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Implementing user mode timers
PostPosted: Wed Mar 10, 2021 10:32 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
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.


Top
 Profile  
 
 Post subject: Re: Implementing user mode timers
PostPosted: Wed Mar 10, 2021 11:48 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
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.

rdos wrote:
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.

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Last edited by Schol-R-LEA on Wed Mar 10, 2021 12:14 pm, edited 10 times in total.

Top
 Profile  
 
 Post subject: Re: Implementing user mode timers
PostPosted: Wed Mar 10, 2021 11:50 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 1593
rdos wrote:
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.
rdos wrote:
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.,

_________________
Carpe diem!


Top
 Profile  
 
 Post subject: Re: Implementing user mode timers
PostPosted: Wed Mar 10, 2021 2:29 pm 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
nullplan wrote:
rdos wrote:
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.

nullplan wrote:
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.


Top
 Profile  
 
 Post subject: Re: Implementing user mode timers
PostPosted: Wed Mar 10, 2021 3:09 pm 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
Schol-R-LEA wrote:
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.

Schol-R-LEA wrote:
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.

Schol-R-LEA wrote:
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.

Schol-R-LEA wrote:
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.


Top
 Profile  
 
 Post subject: Re: Implementing user mode timers
PostPosted: Wed Mar 10, 2021 6:25 pm 
Offline
Member
Member

Joined: Tue Apr 03, 2018 2:44 am
Posts: 401
rdos wrote:
Schol-R-LEA wrote:
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?


Top
 Profile  
 
 Post subject: Re: Implementing user mode timers
PostPosted: Thu Mar 11, 2021 1:40 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
thewrongchristian wrote:
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.


Top
 Profile  
 
 Post subject: Re: Implementing user mode timers
PostPosted: Thu Mar 11, 2021 8:41 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1925
Location: Athens, GA, USA
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?

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
Ordo OS Project
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: Implementing user mode timers
PostPosted: Thu Mar 11, 2021 9:20 am 
Offline
Member
Member

Joined: Wed Oct 01, 2008 1:55 pm
Posts: 3191
Schol-R-LEA wrote:
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.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 9 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 39 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group