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>