From owner-freebsd-arch Wed Dec 13 23:27:44 2000 From owner-freebsd-arch@FreeBSD.ORG Wed Dec 13 23:27:40 2000 Return-Path: Delivered-To: freebsd-arch@freebsd.org Received: from hand.dotat.at (sfo-gw.covalent.net [207.44.198.62]) by hub.freebsd.org (Postfix) with ESMTP id 2E17537B400; Wed, 13 Dec 2000 23:27:40 -0800 (PST) Received: from fanf by hand.dotat.at with local (Exim 3.15 #3) id 146Snh-00003b-00; Thu, 14 Dec 2000 07:27:37 +0000 Date: Thu, 14 Dec 2000 07:27:37 +0000 From: Tony Finch To: Matt Dillon Cc: Alfred Perlstein , Kirk McKusick , arch@FreeBSD.ORG, net@FreeBSD.ORG Subject: Re: patch to cleanup inflight desciptor handling. Message-ID: <20001214072737.A92196@hand.dotat.at> References: <200012131852.KAA17423@beastie.mckusick.com> <200012132106.eBDL6Sg86570@earth.backplane.com> <20001213141917.Q16205@fw.wintelcom.net> <20001213145341.S16205@fw.wintelcom.net> <20001213153649.T16205@fw.wintelcom.net> <200012140125.eBE1Pbi89951@earth.backplane.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2i In-Reply-To: <200012140125.eBE1Pbi89951@earth.backplane.com> Organization: Covalent Technologies, Inc Sender: fanf@dotat.at Sender: owner-freebsd-arch@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG Matt Dillon wrote: > > No waste at all, Alfred, the file descriptor passing code had been > broken for over 10 years precisely because of its complexity. Rewriting > the GC to be more efficient essentially requires using deep graph theory > to locate isolated loops of arbitrary complexity. Most efficient GCers don't involve much graph theory (the notable exception is concurrent collectors); instead they rely on various strategies to drastically reduce the proportion of the arena that they need to examine in most GC runs. In principle mark-sweep collectors are as simple as they get, but unp_gc suffers from the interaction with refcounting. You can use the idea of scanning less of the arena to improve unp_gc as follows. I suggest that you keep two additional lists: one of open unix domain sockets, and one of in-flight sockets. Instead of the existing breadth-first search of the whole file table at the start of unp_gc, it should first clear the mark on each descriptor on the in-flight list, then do a depth-first search of all the descriptors reachable from the unix domain sockets list, marking each one. The loop after the big comment in unp_gc should then scan the in-flight list looking for unmarked descriptors instead of the whole file table. The descriptor freeing loops stay as they are now. I think this should solve the problem at hand, i.e. a lock being held on an important resource while something complicated is being done; instead you would hold locks on two much less important lists (the unix domain list and the in-flight list). > p.s. many object oriented language garbage collectors have the same > problem. create object A, create object B, A references B, B references A, > drop A, drop B. A and B still have references and don't get cleaned up. > Fun. Most modern GCers don't use reference counting partly for that reason, and partly because the overhead of maintaining reference counts is too great. Tony. -- f.a.n.finch fanf@covalent.net dot@dotat.at "Well, as long as they can think we'll have our problems. But those whom we're using cannot think." To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-arch" in the body of the message