Re: epic fsck SIGSEGV! (was Recovering from epic fail (deleted .git/objects/pack))

From: Linus Torvalds <torvalds@linux-foundation.org>
Date: Dec 11, 2008, 03:44 UTC
Message-ID: <alpine.LFD.2.00.0812101930590.3340@localhost.localdomain>
In-Reply-To: <alpine.LFD.2.00.0812101854230.3340@localhost.localdomain>

On Wed, 10 Dec 2008, Linus Torvalds wrote:

Show 17 quoted lines

> 
> On Wed, 10 Dec 2008, Nicolas Pitre wrote:
> 
> > On Wed, 10 Dec 2008, Linus Torvalds wrote:
> > 
> > > But we should definitely fix this braindamage in fsck. Rather than 
> > > recursively walk the commits, we should add them to a commit list and just 
> > > walk the list iteratively.
> > 
> > What about:
> > 
> > 	http://marc.info/?l=git&m=122889563424786&w=2
> 
> Not very pretty. The basic notion is ok, but wouldn't it be nicer to at 
> least use a "struct object_array" instead?
> 
> Let me try to cook something up.

I dunno. I like this patch better. It's a bit larger. I think it's a bit more clearly separated (ie a "mark_object_reachable()" _literally_ just puts the object on a list, and the whole traversal is a whole separate phase), but I guess it's a matter of taste.

It has gotten no real testing. Caveat emptor. And I didn't even bother to check that it can run with less stack or that it makes any other difference.

			Linus

---
 builtin-fsck.c |   38 +++++++++++++++++++++++++++++++-------
 1 files changed, 31 insertions(+), 7 deletions(-)

diff --git a/builtin-fsck.c b/builtin-fsck.c
index afded5e..297b2c4 100644
--- a/builtin-fsck.c
+++ b/builtin-fsck.c
@@ -64,11 +64,11 @@ static int fsck_error_func(struct object *obj, int type, const char *err, ...)
 	return (type == FSCK_WARN) ? 0 : 1;
 }
 
+static struct object_array pending;
+
 static int mark_object(struct object *obj, int type, void *data)
 {
-	struct tree *tree = NULL;
 	struct object *parent = data;
-	int result;
 
 	if (!obj) {
 		printf("broken link from %7s %s\n",
@@ -96,6 +96,20 @@ static int mark_object(struct object *obj, int type, void *data)
 		return 1;
 	}
 
+	add_object_array(obj, (void *) parent, &pending);
+	return 0;
+}
+
+static void mark_object_reachable(struct object *obj)
+{
+	mark_object(obj, OBJ_ANY, 0);
+}
+
+static int traverse_one_object(struct object *obj, struct object *parent)
+{
+	int result;
+	struct tree *tree = NULL;
+
 	if (obj->type == OBJ_TREE) {
 		obj->parsed = 0;
 		tree = (struct tree *)obj;
@@ -107,15 +121,22 @@ static int mark_object(struct object *obj, int type, void *data)
 		free(tree->buffer);
 		tree->buffer = NULL;
 	}
-	if (result < 0)
-		result = 1;
-
 	return result;
 }
 
-static void mark_object_reachable(struct object *obj)
+static int traverse_reachable(void)
 {
-	mark_object(obj, OBJ_ANY, 0);
+	int result = 0;
+	while (pending.nr) {
+		struct object_array_entry *entry;
+		struct object *obj, *parent;
+
+		entry = pending.objects + --pending.nr;
+		obj = entry->item;
+		parent = (struct object *) entry->name;
+		result |= traverse_one_object(obj, parent);
+	}
+	return !!result;
 }
 
 static int mark_used(struct object *obj, int type, void *data)
@@ -237,6 +258,9 @@ static void check_connectivity(void)
 {
 	int i, max;
 
+	/* Traverse the pending reachable objects */
+	traverse_reachable();
+
 	/* Look up all the requirements, warn about missing objects.. */
 	max = get_max_object_index();
 	if (verbose)