A number of problems have been identified with our current callout code and I have been thinking about and discussed various aspects with people during the EuroBSDcon2007 conference.

A lot of people are interested in this, so here is a quick sketch of what I'm thinking about:

The Problems

------------

1. We need better resolution than a periodic "hz" clock can give us. Highspeed networking, gaming servers and other real-time apps want this.

2. We "pollute" our call-wheel with tons of callouts that we know are unlikely to happen.

3. We have many operations on the callout wheel because certain callouts gets rearmed for later in the future. (TCP keepalives).

4. We execute all callouts on one CPU only.

5. Most of the specified timeouts are bogus, because of the imprecision inheret in the current 1/hz method of scheduling them.

and a number of other issues.

The proposed API

----------------

tick_t XXX_ns_tick(unsigned nsec, unsigned *low, unsigned *high); Caculate the tick value for a given timeout. Optionally return theoretical lower and upper limits to actual value,

tick_t XXX_s_tick(unsigned seconds) Caculate the tick value for a given timeout.

The point behind these two functions is that we do not want to incur a scaling operating at every arming of a callout. Very few callouts use varying timeouts (and for those, no avoidance is possible), but for the rest, precalculating the correct (opaque) number is a good optimization.

XXX_arm(struct xxx*, tick_t, func *, arg *, int flag, struct mtx *); Arm timer. Struct xxx must be zeroed before first call.

If mtx pointer is non-NULL, acq mutex before calling.

flags: XXX_REPEAT XXX_UNLIKELY

Arm a callout with a number of optional behaviours specified.

XXX_rearm(struct xxx*, tick_t) Rearm timer.

XXX_disarm(struct xxx*) Unarm the timer.

XXX_drain(struct xxx*) Drain the timer.

The functions above will actually be wrappers for a more generic set of the same family, which also takes a pointer to a callout-group.

This is so that we can have different groups of callouts, for instance one group for the/each netstack and one for the disk-I/O stuff etc.

Implementation

--------------

Behind the scenes, we will have to support hardware that only has a HZ style periodic interrupt but also hardware that can do deadline interrupts (like HPET).

Short callouts, less than 2 seconds, will be stored in a binary heap (A tree where a node is numerically lower than its parents.)

The depth of the heap is Log2(nodes) and there are very efficient ways to store and access the heap.

Locking will be with one mutex for the heap.

The top element which is always the next one to be executed, will be left in place during execution, so that any rescheduling (automatic or explicit) will only have to do as little work as necessary to trickle it down to the right place in the heap.

Rescheduling a callout is a matter of trickling it up- or downwards in the tree to a correct position.

For the long callouts, and for callouts unlikely to happen, a group of lists are used for storage.

Imagine the number of lists is four, we then label them with Tnow+2s, Tnow+8s, Tnow+32s and "the rest".

Armed callouts go into the first list that is labeled with a higher strike time.

If a callout is rescheduled to later, it's timeout is updated, but it is not moved in the list.

If a callout is cancled, it is removed from the list.

Twice per second, the first list is scanned, and any due callouts called and any callouts later than the lists strike time is moved into the right list.

When "Tnow+2s" rolls around, the lists are rotated to the left: the Tnow+8s becomes "Tnow+2s" etc.

The idea behind this (untried) scheme for the long callouts, is to distribute the callouts somewhat evenly in the lists, while maintaining only the relevant entries in the first list, the point being that most of them (TCP keepalive, CAM etc) will never happen, so spending time sorting them more than necessary is pointless. Obviously, this algorithm needs to be tested in practice and tuned/changed/discared depending on the results.

All numbers given are subject to tuning.