Callout system rework: status report 1

[Prashant Vaibhav]

Hi,

After a late start because of connectivity problems, I've made some  
progress with my project.

During the past 2 weeks I have worked on two main areas -

— Implemented a generic priority queue based on binary heap. This part  
has been tested and is complete. MIN and MAX heaps are done, each  
supporting insert item, peek at highest priority item, extract item  
and modify item's priority (key). For MIN heaps, insertion can be  
arbitrary but removal is always in order of increasing key (and  
decreasing key for MAX heaps). I've used most of the same conventions  
as the queues and trees from sys/queue.h and sys/tree.h, so usage is  
quite similar. The priority queue provides O(1) insertion, removal and  
key modification on an average, with upper-bound O(log n), and peek/ 
extract highest priority item at worst case O(1), thus it can find use  
in various other parts of the kernel apart from maintaining callout/ 
timeout lists.

— Re-write kern/kern_timeout.c and sys/callout.h to replace the  
callout 'wheel' data structure with the new binary heap, thus freeing  
the kernel from relying on a periodic timer interrupt. This is still a  
work in progress and hasn't been tested yet. About half of the job is  
done, most of the auxiliary functions, including softclock(), have  
been implemented, except for the main functions which arm a callout  
and to cancel an armed callout using the callout_* API. For these I am  
studying the locking mechanism to make sure clients get the same  
behaviour with the new implementation. timeout() and untimeout() which  
need to allocate callout structures locally are implemented but I'm  
still debating on what could be a better way. I'm looking to use  
uma(9) instead of maintaining our own used/free list of callouts.

I'll send another mail when perforce has been synced (ie. get branches  
working..) with the work done so far.

During the next few days I will continue to modify kern_timeout.c so  
that the existing API works transparently, but using the binary heap  
as the back-end. Once this is done, I will begin adding the newly- 
proposed API functions, and thereafter the interface for generic timers.

Best,
Prashant Vaibhav