mkoegler@xxxxxxxxxxxxxxxxx (Martin Koegler) writes:
> Maybe something like this could help:
>>From 32be177cbb0825fc019200b172f3d79117b28140 Mon Sep 17 00:00:00 2001
> From: Martin Koegler <mkoegler@xxxxxxxxxxxxxxxxx>
> 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.
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
