Status at end of GSoC

So GSoC has officially come to an end, it’s time to summarize what has been and has not been achieved during this time.

Two of the goals were achieved, while the third is quite far off right now.

1. The callout “wheel” was replaced with a binary heap. This forms the basis of the suggested improvements to the callout subsystem. The binary heap was implemented as a set of macros which provide a min-heap as well as a max-heap, for various general-purpose priority queues. More information can be found in the comments in the kernel source file sys/sys/bheap.h and in the previous blog posts.

2. The new API was implemented from the “client-side”, i.e. the functionality is usable by callout consumers now, instead of the existing API. It was greatly simplified, though there could be some more modifications to make it more useful. The API stands as follows :

• callout_handle_t — The handle (actually a typedef’s struct) used to identify a single callout (can be reused). The client should malloc a callout_handle_t and zero it out before using it.

• hwclocktick_t — A semi-opaque hardware-dependent clock tick count. Clients need to use auxiliary functions to convert to/from real time and hardware-dependent time. The hwclocktick_t is limited to nanosecond resolution (because the conversion functions currently use timespec)

• absolute_time_to_hw_time(const struct timespec* a, hwclocktick_t* t) — This function converts a timespec to a hardware dependent tick count. The timespec structure can hold time in the format of seconds + nanosecond.

• hw_time_to_absolute_time(const hwclocktick_t* t, struct timespec* a) — This function converts given hardware-dependent ticks into a timespec.

• time_interval_to_hw_time(int interval, hwclocktick_t* h, enum time_scale ts) — This is probably the function which will be used the most. It converts a given number of real time units into a hwclocktick_t which can be later used to schedule a callout. The time_scale is used to describe what units interval is specified in, and can be one of: TIMESCALE_SECOND, TIMESCALE_MS, TIMESCALE_US (microsecond), TIMESCALE_NS or TIMESCALE_MINUTE.

The above 3 functions can be used to create a hwclocktick_t of the appropriate duration. If the same duration will be used frequently, it makes sense to do the conversion once and cache the resultant hwclocktick_t.

Behind the scenes, the callout subsystem will “ask” the current timer hardware to do the conversion for it. This will use the Kobj kernel object system with a common interface that each timer hardware will need to specify. Currently this is not in a working state yet, so the functions use traditional hz arithmetic to do the conversions. In any case, this is transparent to the callout client.

Once the required hardware-dependent tick count is generated, a new callout can be armed by calling:

callout_arm(callout_handle_t* c, hwclocktick_t when, void (*func)(void*), void* arg, int flags, mtx* mutex) — Pass the allocated callout handle, the required callback time as a hw tick, a pointer to the callback function, an argument to pass to it, some flags (same as old API) and any mutex as required. This combines the functionality of callout_init(), callout_init_mtx(), callout_reset() etc. all in one function. This might be a good thing or a bad thing.

There is no callout_init[_mtx]() anymore. The callout_arm() function will handle initialization. There is no reason to call callout_cancel() on an unarmed callout, so explicitly initializing it is not needed. But if your design does require it, make sure to zero out the callout_handle_t structure after memory for it is acquired. Calls to callout_cancel() with an unarmed callout handle will simply fail. Results of calling callout_cancel() without a zeroed-out, unarmed callout are undefined!

If you frequently need to re-arm callouts, for which only the callout time changes, callout_rearm() can be used as a shorthand. Obviously callout_rearm() should only be called with a callout handle that has been armed before (else results are undefind).

Calling callout_arm() on an already pending callout will also simply reschedule it, so if you need a different callback function or have to pass another argument in addition to rescheduling it, this method will suffice. Note that this is different from the current behaviour where the function and argument must also match for most functions.

There is also callout_[re]arm_within() — this function can be used to arm or re-arm a callout with an imprecise time-out. That is to say, one can specify a time period during which the callout can be serviced. This will allow for optimizations in the future. Currently we take the lazy approach and schedule such callouts to the farthest time specified.

callout_cancel() and callout_drain() remain basically the same. When the underlying implementation will be rewritten, atomic operation of callout_cancel() will be guaranteed - i.e. if the callback function has not already been executed, upon return of callout_cancel(), the callout will be guaranteed to have been stopped. There will not be a grey-zone during which if callout_cancel() is called, the callout may still run. This is not implemented yet!

That is about it for the new API. As mentioned before they are currently simply wrappers around existing implementation, and both implementations currently exist in the kernel (in my experimental branch).

I modified the iwi driver to use the new API as a quick test and demonstration. It works, but we’re not using it in the most efficient way yet. I’ll be checking the driver’s logic in more detail so we can replace most instances of callout_arm() with callout_rearm() instead and avoid internally re-initializing the callout structure.

On the Kobj side, I’ve started writing the interface and implemented a timer_hz class which will source off the traditional periodic timer via hardclock(). The idea is that various timer hardware can implement this timer interface to vend its services, and register with the callback system at boot-time (or even run-time). The user (or system) will then select whichever timer it needs. This part has also not been implemented yet.

So to summarize:

1. The callout internally uses a binary heap which should be more efficient specially when re-arming existing callouts.

2. The new API is basically usable, although still works as a wrapper layer over the existing implementation.

3. Multiple hardware timer support is still in its very early implementation stages, Kobj will be used for this.

4. Tickless capability is dependent on point 3 being finished.

I plan to continue working on the project so hopefully in the next month or two, #3 and subsequently #4 will be done and we can have a high-resolution, tickless capable callout subsystem in FreeBSD!