From owner-freebsd-net Thu Dec 14 10:30: 0 2000 From owner-freebsd-net@FreeBSD.ORG Thu Dec 14 10:29:50 2000 Return-Path: Delivered-To: freebsd-net@freebsd.org Received: from hand.dotat.at (sfo-gw.covalent.net [207.44.198.62]) by hub.freebsd.org (Postfix) with ESMTP id 6E97937B402; Thu, 14 Dec 2000 10:29:49 -0800 (PST) Received: from fanf by hand.dotat.at with local (Exim 3.15 #3) id 146d8N-000Ll1-00; Thu, 14 Dec 2000 18:29:39 +0000 Date: Thu, 14 Dec 2000 18:29:39 +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: <20001214182939.B92196@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> <20001214072737.A92196@hand.dotat.at> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline User-Agent: Mutt/1.2i In-Reply-To: <20001214072737.A92196@hand.dotat.at> Organization: Covalent Technologies, Inc Sender: fanf@dotat.at Sender: owner-freebsd-net@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.org Tony Finch wrote: > >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. Actually that isn't right. The order of the search doesn't matter; what is important is that the trick that the existing code uses (with the FDEFER flag and unp_defer) to perform the scan using no additional space won't work: you must use a more conventional scanning algorithm instead. But anyway, I have found a much better algorithm in the garbage collection book [1]. The algorithm you want [2] isn't directly described in the book; instead they explain a lazy variant [3] which has some additional mechanism to delay running the GC in order to amortise the cost, which is not something we want to do here. AFAICT though the core is the same, so I'll describe it in pseudocode below. It scans the theoretical minimum number of file descriptors :-) When closing a unix domain descriptor with descriptors in flight, do this: count_local_refs(fp); find_external_refs(fp); close_unreffed(fp); count_local_refs counts all the references within the graph of fds reachable from the fd we are closing, taking into account loops: [The foreach syntax is an abbreviation for code like lines 1120 to 1150 of uipc_usrreq.c.] count_local_refs(struct file *fp) { if (!(fp->f_flag & FMAYBEFREE)) { fp->f_flag |= FMAYBEFREE; foreach child (in_flight(fp)) { child->f_count--; count_local_refs(child); } } } find_external_refs finds subgraphs that are reachable externally and marks them as such: find_external_refs(struct file *fp) { if (fp->f_flag & FMAYBEFREE) if (fp->f_count) mark_external_refs(fp); else { fp->f_flag |= FREALLYFREE; foreach child (in_flight(fp)) find_external_refs(child); } } mark_external_refs(struct file *fp) { fp->f_flag &= ~FMAYBEFREE; foreach child (in_flight(fp)) { child->f_count++; if (fp->f_flag & FMAYBEFREE) mark_external_refs(child); } } close_unreffed then closes all the unreferenced descriptors. close_unreffed(struct file *fp) { if (fp->f_flag & FREALLYFREE) { fp->f_flag &= ~(FMAYBEFREE|FREALLYFREE); foreach child (in_flight(fp)) close_unreffed(child); /* XXX: here we probably need to set fp->f_count to 1 to avoid a panic */ close(fp); } } There are a few problems with this as I have described it, but I think they are reasonably easily fixed: * The recursive algorithms may overflow the kernel stack so they should be replaced with iterative ones. * The way it fools around with refcounts will cause trouble if any other processes do things with the descriptors that the algorithm is dealing with; perhaps the first pass through the graph should lock all the descriptors to avoid this. * It will fail if it is run concurrently on two overlapping graphs; there should be a mutex around the unix domain socket close code to prevent this happening. * The unix domain socket close code must detect when it is called recursively by this code (i.e. fp->f_flag & REALLYFREE) and avoid calling the gc again recursively. Here are the references. According to someone at the San Francisco Public Library there aren't any copies of Information Processing Letters in the Bay Area, which I find hard to believe since it implies that there aren't any good computer science or academic periodical libraries here. [1] R. E. Jones, R. D. Lins: "Garbage Collection"; Wiley (Chichester, 1996). [2] A. D. Martinez, R. Wachenauzer, R. D. Lins: "Cyclic Reference Counting with Local Mark-Scan"; Information Processing Letters 34:31-35, 1990 [3] R. D. Lins: "Cyclic Reference Counting with Local Mark-Scan"; Information Processing Letters 44(4):215-220, 1992; University of Kent at Canterbury Computing Laboratory Technical Report 75, July 1990. [4] R. D. Lins, M. A. Vasques: University of Kent at Canterbury Computing Laboratory Technical Report 92, August 1991. Tony. -- f.a.n.finch fanf@covalent.net dot@dotat.at "Because all you of Earth are idiots!" To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-net" in the body of the message