This blog post will refer primarily to the FORGE Operating System, a new project I am working on with a primary goal of being able to host various different websites. This project is in C (not C++, as Pedigree was), and I have been working on it over a number of months. Progress is slow; I am currently not spending too much time working on the codebase and rather working on other things such as finishing my university course.
As an aside, the name FORGE is partially because I’d love to host the site that’s hosting it on it (QuokForge), and partially because the idea of a “forge” for any cool ideas I come up with appeals to me. It’s awesome to be able to sit back and think of something different or unique for memory management or caching or something and be able to just design it and implement it straight into FORGE. In that sense, it’s kind of like an incubator for ideas.
Anyway – one thing I really like in FORGE is the timer API. In a modern operating system, time is an important resource. The scheduler typically uses ticks to determine when a process should be interrupted, some operations need to be given a timeout, and yet more operations need to happen at a particular time in the future (whether regularly, or once-off). To add to the complexity, on x86 alone there are a variety of timers available, including the tried-and-true programmable interval timer (PIT), the high precision event timer (HPET), and even the system’s real time clock (RTC) can be used for this purpose. Other platforms such as ARM can have even more clocks, each with their own individual characteristics. And timers such as the HPET may not be present on all hardware – particularly legacy machines.
So, conceptually, time is simple in an operating system. Practically, it is a nightmare.
In FORGE, I happened to already know this fact from my experience with Pedigree and my other OS projects before that. I also knew that trying to integrate the HPET back into Pedigree (as an example) was going to be painful – so whatever I came up with for FORGE had to be flexible and ready to handle any potential new timing mechanism that might come up in the future. That means I can’t ever assume a particular type of device, and the frequencies and even semantics of the timer must be configurable.
First up, there are a number of different timer types that FORGE is capable of dealing with (these can be OR-d together, too):
- One-shot. These type of timers designate a time in the future at which the timer should fire (or, a time period from the current time).
- Periodic. These timers fire at regular time intervals. This is the most conventional type of timer that just about everyone (should) know about.
- UNIX Timestamp. Okay, this isn’t a timer, but it’s an important feature regardless. The ability for a clock to provide a UNIX timestamp (that is, to know the current time and date) is very useful for a variety of system modules. For example, a filesystem driver might want to use this kind of timer to change the access time of a file.
- Tick count. Similar to the UNIX timestamp type – not a timer, but useful. Here, we simply count ticks of an arbitrary time period.
- Useless. Really only useful for a timer which has been disabled. Any timer that the system knows about, but can’t do any of the above, will go under this category.
Okay, so that’s the types of timer that we can use – what about time resolution? Again, these can be OR-d together to indicate multiple granularity are supported.
- Terrible. Higher granularity than seconds. Perhaps useful only for timers with time periods measured in days/months/years.
- Seconds. As the name suggests, time periods measured in seconds. For example, a timer which needs to trigger in an hour’s time.
- Milliseconds. A millisecond timer. This is more useful for things such as a scheduler which might need to tick at 100 Hz.
- Microseconds, and nanoseconds. Very high-resolution timing.
As each driver that configures and provides a timing device to the system completes its initialisation, it will register the timer with the system with a mix of the above features. Each time the timer ‘ticks’ (eg, the PIT IRQ fires), it will call a function provided by the timer API which registers the tick.
Modules, drivers, and kernel code all hook into the timer API by installing what is essentially a callback. This callback is installed with a request for a particular type and resolution (eg, one-shot, fire in 500 time units, time unit is milliseconds) and this is then added to the queue of pending callbacks. Eventually, this will be stored in an optimal data structure that places the callbacks with the lowest remaining time first. Callbacks are assigned the best possible timer for the request.
This is where things get really cool. Each tick that comes in needs to be normalised to the highest possible resolution (to simplify operations across the numerous timer resolutions that could be present). Each callback in the queue that has hooked this particular timer has its ‘remaining time’ reduced by this tick’s time. If the time period has completed (ie, remaining time is less than or equal to zero), the callback is called. Should the callback type be ‘periodic’, a copy of the callback is made and prepared for the next trigger.
This all hides a lot of the details from the developer – all a developer needs to do is ask for a particular timer type, at a particular resolution, and it all “just works”. That is, assuming the resolution is attainable. If it is not, the callback is not installed.
The nice part about having every timer in the system integrated under one module is that I can do some really handy things as a result. The canonical example, which I think is just awesome, is to implement one-shot timers on top of periodic timers where a hardware-supported one-shot timer is not available, and vice versa. This means that in systems where one-shot timing is not available, it is still possible to request a one-shot timer – the implementation will just recognise this and avoid reinstalling the callback after it fires.
So far, this has worked beautifully in the scheduler for FORGE, and I can see it being incredibly useful for more complex code down the track, including networking or USB. It also makes implementing a function to put a thread to sleep for a period of time ridiculously easy – install a callback, acquire a mutex that only the callback can release, release it in the callback (greatly simplified – multi-core and even multi-thread issues abound, but you get the idea).
The code linked above is unfortunately fairly messy and the implementation is in need of a cleanup, but at this stage it’s fully functional and entirely available for perusal. The license for FORGE is permissive, so by all means have a look around and use anything you like (albeit with appropriate attribution). And I’m always open to constructive criticism (it’s an excellent way to build my skills) or questions – just hit the comments below.
So that’s the timer API in FORGE – flexible, usable, and quite powerful.