From owner-soc-status@FreeBSD.ORG Sun Jun 21 21:29:18 2009 Return-Path: Delivered-To: soc-status@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 3F218106566C for ; Sun, 21 Jun 2009 21:29:18 +0000 (UTC) (envelope-from admin@mercurysquad.com) Received: from mail-pz0-f194.google.com (mail-pz0-f194.google.com [209.85.222.194]) by mx1.freebsd.org (Postfix) with ESMTP id 1DF9C8FC18 for ; Sun, 21 Jun 2009 21:29:17 +0000 (UTC) (envelope-from admin@mercurysquad.com) Received: by pzk32 with SMTP id 32so32437pzk.3 for ; Sun, 21 Jun 2009 14:29:17 -0700 (PDT) Received: by 10.142.51.1 with SMTP id y1mr2363024wfy.92.1245618276128; Sun, 21 Jun 2009 14:04:36 -0700 (PDT) Received: from ?10.100.2.50? ([117.197.66.31]) by mx.google.com with ESMTPS id 30sm73611wfa.15.2009.06.21.14.04.33 (version=TLSv1/SSLv3 cipher=RC4-MD5); Sun, 21 Jun 2009 14:04:35 -0700 (PDT) Sender: Prashant Vaibhav Message-Id: <42748670-F8BC-4CAC-A3E9-B7F39E41B4F9@freebsd.org> From: Prashant Vaibhav To: soc-status@freebsd.org Content-Type: text/plain; charset=WINDOWS-1252; format=flowed; delsp=yes Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Apple Message framework v935.3) Date: Mon, 22 Jun 2009 02:34:30 +0530 X-Mailer: Apple Mail (2.935.3) Cc: Attilio Rao , Ed Maste Subject: Callout system rework: status report 1 X-BeenThere: soc-status@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Summer of Code Status Reports and Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sun, 21 Jun 2009 21:29:18 -0000 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=