Skip site navigation (1)Skip section navigation (2)
Date:      Mon, 22 Jun 2009 02:34:30 +0530
From:      Prashant Vaibhav <pvaibhav@freebsd.org>
To:        soc-status@freebsd.org
Cc:        Attilio Rao <attilio@freebsd.org>, Ed Maste <emaste@freebsd.org>
Subject:   Callout system rework: status report 1
Message-ID:  <42748670-F8BC-4CAC-A3E9-B7F39E41B4F9@freebsd.org>

next in thread | raw e-mail | index | archive | help
Hi,

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

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

=97 Implemented a generic priority queue based on binary heap. This part =
=20
has been tested and is complete. MIN and MAX heaps are done, each =20
supporting insert item, peek at highest priority item, extract item =20
and modify item's priority (key). For MIN heaps, insertion can be =20
arbitrary but removal is always in order of increasing key (and =20
decreasing key for MAX heaps). I've used most of the same conventions =20=

as the queues and trees from sys/queue.h and sys/tree.h, so usage is =20
quite similar. The priority queue provides O(1) insertion, removal and =20=

key modification on an average, with upper-bound O(log n), and peek/=20
extract highest priority item at worst case O(1), thus it can find use =20=

in various other parts of the kernel apart from maintaining callout/=20
timeout lists.

=97 Re-write kern/kern_timeout.c and sys/callout.h to replace the =20
callout 'wheel' data structure with the new binary heap, thus freeing =20=

the kernel from relying on a periodic timer interrupt. This is still a =20=

work in progress and hasn't been tested yet. About half of the job is =20=

done, most of the auxiliary functions, including softclock(), have =20
been implemented, except for the main functions which arm a callout =20
and to cancel an armed callout using the callout_* API. For these I am =20=

studying the locking mechanism to make sure clients get the same =20
behaviour with the new implementation. timeout() and untimeout() which =20=

need to allocate callout structures locally are implemented but I'm =20
still debating on what could be a better way. I'm looking to use =20
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 =20=

working..) with the work done so far.

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

Best,
Prashant Vaibhav=



Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?42748670-F8BC-4CAC-A3E9-B7F39E41B4F9>