Re: git fsck segmentation fault

mkoegler@auto.tuwien.ac.at (Martin Koegler) writes:

Maybe something like this could help:

quoted

From 32be177cbb0825fc019200b172f3d79117b28140 Mon Sep 17 00:00:00 2001

From: Martin Koegler <redacted>
Date: Wed, 10 Dec 2008 08:42:08 +0100
Subject: [PATCH] fsck: use fewer stack

This patch moves the state while traversing the tree
from the stack to the heap.

Hmm, after the change:

	* mark_object() marks the object as reachable, and pushes the
	  objects to the objectstack;

	* mark_object_reachable() marks the object using mark_object(),
          and repeatedly calls mark_child_object() until the objectstack
          is fully drained;

	* mark_child_object() inspects the object taken from the
          objectstack, calls fsck_walk() on it, with mark_object as the
          callback;

	  * fsck_walk() calls the callback function (i.e. mark_object) on
            the object given, and the objects immediately reachable from
            it;

            * mark_object() does not recurse, so these immediately
              reachable objects are left in the objectstack, without a
              deep recursion.
        
That seems to be what is going on, and this should be a good fix.

A similar change would be needed for other callers of fsck_walk(), no?
There seem to be one in builtin-unpack-objects.c (check_object calls
fsck_walk as itself as the callback). 

Another caller is in index-pack.c (sha1_object() calls fsck_walk with
mark_link as the callback), but I do not think it would  recurse for the
depth of the history, so we are safe there.

I initially expected that the fix would be to introduce this "userspace
work queue" (i.e. your objectstack) to be maintained on the
fsck.c:fsck_walk() side (perhaps as an extra parameter to an actual queue
for reentrancy), not by making the callee not to recurse, though.

On Wed, Dec 10, 2008 at 06:33:20PM -0800, Junio C Hamano wrote:

mkoegler@auto.tuwien.ac.at (Martin Koegler) writes:
A similar change would be needed for other callers of fsck_walk(), no?
There seem to be one in builtin-unpack-objects.c (check_object calls
fsck_walk as itself as the callback). 

buitin-unpack-objects.c is different. First, its intended for the
small case [default unpack_limit is 100; it keeps the unpacked content
of trees/commits in memory], which will not overflow the
stack. Second, it may only write an object after all of its connected
objects have been written out. So it would need a totally different
logic.

Another caller is in index-pack.c (sha1_object() calls fsck_walk with
mark_link as the callback), but I do not think it would  recurse for the
depth of the history, so we are safe there.

mark_link only sets a flag on the direct connected objects, so yes, it
needs no change.

I initially expected that the fix would be to introduce this "userspace
work queue" (i.e. your objectstack) to be maintained on the
fsck.c:fsck_walk() side (perhaps as an extra parameter to an actual queue
for reentrancy), not by making the callee not to recurse, though.

fsck_walk has been designed to call a function on all directly
connected objected. There are callers, which expected this behaviour
(eg. index-pack, mark_used in fsck).

mfg Martin Kögler