Date: Thu, 14 Dec 2000 18:29:39 +0000 From: Tony Finch <dot@dotat.at> To: Matt Dillon <dillon@earth.backplane.com> Cc: Alfred Perlstein <bright@wintelcom.net>, Kirk McKusick <mckusick@mckusick.com>, arch@FreeBSD.ORG, net@FreeBSD.ORG Subject: Re: patch to cleanup inflight desciptor handling. Message-ID: <20001214182939.B92196@hand.dotat.at> In-Reply-To: <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> <20001214072737.A92196@hand.dotat.at>
next in thread | previous in thread | raw e-mail | index | archive | help
Tony Finch <dot@dotat.at> 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-arch" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?20001214182939.B92196>