From owner-freebsd-arch@FreeBSD.ORG Thu Apr 15 15:39:23 2004 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from mx1.FreeBSD.org (mx1.freebsd.org [216.136.204.125]) by hub.freebsd.org (Postfix) with ESMTP id 0481916A4D0 for ; Thu, 15 Apr 2004 15:39:23 -0700 (PDT) Received: from mail4.speakeasy.net (mail4.speakeasy.net [216.254.0.204]) by mx1.FreeBSD.org (Postfix) with ESMTP id A001D43D62 for ; Thu, 15 Apr 2004 15:39:22 -0700 (PDT) (envelope-from jmg@hydrogen.funkthat.com) Received: (qmail 26844 invoked from network); 15 Apr 2004 22:39:21 -0000 Received: from dsl017-045-168.spk4.dsl.speakeasy.net (HELO hydrogen.funkthat.com) ([69.17.45.168]) (envelope-sender ) by mail4.speakeasy.net (qmail-ldap-1.03) with SMTP for ; 15 Apr 2004 22:39:21 -0000 Received: from hydrogen.funkthat.com (qpszcd@localhost.funkthat.com [127.0.0.1])i3FMdKOE031416; Thu, 15 Apr 2004 15:39:21 -0700 (PDT) (envelope-from jmg@hydrogen.funkthat.com) Received: (from jmg@localhost) by hydrogen.funkthat.com (8.12.10/8.12.10/Submit) id i3FMdKVt031415; Thu, 15 Apr 2004 15:39:20 -0700 (PDT) Date: Thu, 15 Apr 2004 15:39:20 -0700 From: John-Mark Gurney To: "Brian F. Feldman" Message-ID: <20040415223920.GT567@funkthat.com> Mail-Followup-To: "Brian F. Feldman" , Robert Watson , Seigo Tanimura , Pawel Jakub Dawidek , freebsd-arch@freebsd.org References: <20040409180106.GM567@funkthat.com> <200404152036.i3FKaUd5018165@green.homeunix.org> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <200404152036.i3FKaUd5018165@green.homeunix.org> User-Agent: Mutt/1.4.1i X-Operating-System: FreeBSD 4.2-RELEASE i386 X-PGP-Fingerprint: B7 EC EF F8 AE ED A7 31 96 7A 22 B3 D8 56 36 F4 X-Files: The truth is out there X-URL: http://resnet.uoregon.edu/~gurney_j/ X-Resume: http://resnet.uoregon.edu/~gurney_j/resume.html cc: Pawel Jakub Dawidek cc: Seigo Tanimura cc: Robert Watson cc: freebsd-arch@freebsd.org Subject: locking down kqueue (was some other completely unrelated topic) X-BeenThere: freebsd-arch@freebsd.org X-Mailman-Version: 2.1.1 Precedence: list Reply-To: John-Mark Gurney List-Id: Discussion related to FreeBSD architecture List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 15 Apr 2004 22:39:23 -0000 Brian F. Feldman wrote this message on Thu, Apr 15, 2004 at 16:36 -0400: > John-Mark Gurney wrote: > > How does this sound to people? I have some code starting to implement > > this, but I haven't gotten very far with it yet... > > You know, now I think Seigo's right on the money that due to the nature of > the recursion of kqueue's current implementation, it's impossible to get > right with this train of thought. So, let's redesign: > * The kqueue object the user controls needs a mutex. > * The lists (selinfo, mostly) that knotes are on need locking. > * The filterops that kqueue calls out MUST be called with some > kind of locking on the lists that the kqueue is on, and the > user MUST be able to grab any kind of lock from inside a > filterop. You need to be more specific on this.. which filterops should be allowed to grab any locks? In my opinion, filterops should only be allowed to grab a limited number of locks and these are the object lock and the kqueue (list) locks as necessary... > * At some point the object being observed must call back into > kqueue to add itself. We'll end up getting deadlocks if the > locks kqueue holds are not the ones required to add the > object to klists and held when we do the f_attach(). Yes, we need to prevent lock order inversion.. > * Anything that calls KNOTE() or KNOTE_ACTIVATE() directly > will end up recursing back on itself if we don't convert > it to putting the new event on a work queue. How > filt_procattach() calls KNOTE_ACTIVATE() or filt_proc() > calls kqueue_register() is a very good example. Hmmm. I'm going to have to mull on the filt_proc problem a bit.. > * The functions that need to be exported are: > * KNOTE()/KNOTE_ACTIVATE() <- put on a workqueue > * kqueue_register() <- put on a workqueue > * knote klist/(kn_selnext) linking and unlinking > * knote klist/(kn_selnext) is disappearing > The last two are the only ones that are not called recursively > and should have easy locking semantics. Personally, I'd prefer to invert the logic, and have linking/unlinking and disappearing done via a work queue, and KNOTE/kqueue_register done in line if possible... It's also difficult because we need to optimize for both cases of long existing events, and ONE_SHOT events where we are constantly adding/removing events... The reason I say this is because I have a visit for a webserver that uses multiple processors but a single kqueue to handle events, and if we use ONE_SHOT, then we are guarnateed that we are notified of each event once... We need to make sure that the work queue will not be a significant problem... > Nothing is currently designed to work with anything even remotely not > looking like spl(), so we have to either flatten it out (using workqueues) > or change semantics so that when KNOTE() is called it acts like the closure > that we pretend it is. Of course, the easy way to do this is with a worker > queue/condvar/mutex/thread. What other ways do we have available to turn > KNOTE() into a closure, bearing in mind that the entire point of the > mechanism is that there is no memory allocation at the time of event > generation -- only when events are defined (by the user or recursively by > other events). The proc case should be treated special as it is an [ab]use of the kevent system with following children... I'm looking at it more.. -- John-Mark Gurney Voice: +1 415 225 5579 "All that I will do, has been done, All that I have, has not."