> On Sun, 28 Feb 1999, Alan Cox wrote:
> > I've been pondering this one (you are the third report I've seen). It
> > basically implies a bug in the mark/sweep garbage collector, or a race
> > of some kind.
>
> Latter. Patch follows (I've sent it to Alexey a minute ago):
Screw it. The race is pretty real, but there was another problem (kudos to
Alexey for pointing to it). Here's much better fix - it eliminates
separately allocated stack at all and simplifies the mark phase:
diff -urN linux.vanilla/include/net/sock.h linux.bird-unix-gc/include/net/sock.h
--- linux.vanilla/include/net/sock.h Tue Feb 23 15:59:28 1999
+++ linux.bird-unix-gc/include/net/sock.h Sun Feb 28 13:03:53 1999
@@ -99,8 +99,7 @@
struct semaphore readsem;
struct sock * other;
struct sock ** list;
- int marksweep;
-#define MARKED 1
+ struct sock * gc_tree;
int inflight;
};
diff -urN linux.vanilla/net/unix/garbage.c linux.bird-unix-gc/net/unix/garbage.c
--- linux.vanilla/net/unix/garbage.c Fri Nov 13 18:02:09 1998
+++ linux.bird-unix-gc/net/unix/garbage.c Sun Feb 28 13:12:04 1999
@@ -17,11 +17,12 @@
*
* - explicit stack instead of recursion
* - tail recurse on first born instead of immediate push/pop
+ * - we gather the stuff that should not be killed into tree
+ * and stack is just a path from root to the current pointer.
*
* Future optimizations:
*
* - don't just push entire root set; process in place
- * - use linked list for internal stack
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
@@ -51,6 +52,14 @@
* That might be the reason of random oopses on close_fp() in
* unrelated processes.
*
+ * AV 28 Feb 1999
+ * Kill the explicit allocation of stack. Now we keep the tree
+ * with root in dummy + pointer (gc_current) to one of the nodes.
+ * Stack is represented as path from gc_current to dummy. Unmark
+ * now means "add to tree". Push == "make it a son of gc_current".
+ * Pop == "move gc_current to parent". We keep only pointers to
+ * parents (->gc_tree).
+ *
*/
#include <linux/kernel.h>
@@ -65,7 +74,6 @@
#include <linux/netdevice.h>
#include <linux/file.h>
#include <linux/proc_fs.h>
-#include <linux/vmalloc.h>
#include <net/sock.h>
#include <net/tcp.h>
@@ -74,9 +82,8 @@
/* Internal data structures and random procedures: */
-static unix_socket **stack; /* stack of objects to mark */
-static int in_stack = 0; /* first free entry in stack */
-static int max_stack; /* Top of stack */
+static unix_socket dummy;
+static unix_socket *gc_current=&dummy; /* stack of objects to mark */
extern inline unix_socket *unix_get_socket(struct file *filp)
{
@@ -122,32 +129,25 @@
/*
* Garbage Collector Support Functions
*/
-
-extern inline void push_stack(unix_socket *x)
-{
- if (in_stack == max_stack)
- panic("can't push onto full stack");
- stack[in_stack++] = x;
-}
extern inline unix_socket *pop_stack(void)
{
- if (in_stack == 0)
- panic("can't pop empty gc stack");
- return stack[--in_stack];
+ unix_socket *p=gc_current;
+ gc_current = p->protinfo.af_unix.gc_tree;
+ return p;
}
extern inline int empty_stack(void)
{
- return in_stack == 0;
+ return gc_current == &dummy;
}
extern inline void maybe_unmark_and_push(unix_socket *x)
{
- if (!(x->protinfo.af_unix.marksweep&MARKED))
+ if (x->protinfo.af_unix.gc_tree)
return;
- x->protinfo.af_unix.marksweep&=~MARKED;
- push_stack(x);
+ x->protinfo.af_unix.gc_tree = gc_current;
+ gc_current = x;
}
@@ -169,23 +169,9 @@
return;
in_unix_gc=1;
- if(stack==NULL || max_files>max_stack)
- {
- if(stack)
- vfree(stack);
- stack=(unix_socket **)vmalloc(max_files*sizeof(struct unix_socket *));
- if(stack==NULL)
- {
- printk(KERN_NOTICE "unix_gc: deferred due to low memory.\n");
- in_unix_gc=0;
- return;
- }
- max_stack=max_files;
- }
-
forall_unix_sockets(i, s)
{
- s->protinfo.af_unix.marksweep|=MARKED;
+ s->protinfo.af_unix.gc_tree=NULL;
}
/*
* Everything is now marked
@@ -276,9 +262,9 @@
if (f)
{
- if ((f->protinfo.af_unix.marksweep&MARKED))
+ if (!f->protinfo.af_unix.gc_tree)
{
- f->protinfo.af_unix.marksweep&=~MARKED;
+ f->protinfo.af_unix.gc_tree=&dummy;
x=f;
f=NULL;
goto tail;
@@ -290,7 +276,7 @@
forall_unix_sockets(i, s)
{
- if (s->protinfo.af_unix.marksweep&MARKED)
+ if (!s->protinfo.af_unix.gc_tree)
{
struct sk_buff *nextsk;
skb=skb_peek(&s->receive_queue);
Cheers,
Al
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/