git fsck segmentation fault

git fsck segmentation fault

[Simon Hausmann]

Hi,

when running git fsck --full -v (version 1.6.0.4.26.g7c30c) on a medium sized
(930M) repository I get a segfault.

The backtrace indicates an infinite recursion. Here's the output from the last
few lines:

Checking commit ffffb0556074699814751f3b34526b3d6850c6f7
Checking blob ffffb4e9edf03e7f5643abc5603ca57e745c313d
Checking tree ffffde1114cdd0937cb798069b45f4ceadccd22f
Checking tree ffffe7e34be267ca55a6ae823f8bf31d7a8ef3cd
Checking blob ffffe8bbfc4d7adcb4e5fa00f1b4c99e26591b76
Checking tree ffffea81b8790b194ac215807165e3ff7f824320
Checking blob ffffec79ba618a429dee33bb0acb0ab36cb1310d
Checking tree fffff62eaba873e3ea3cfd7535e6ac514fd18332
Checking blob fffff6519569fac30b11b7bc830d61e296b7c5e2
Segmentation fault (core dumped)

gdb on the core file produces the following backtrace:

#0  0x0000000000487684 in unpack_object_header (p=0x26ad4c0, w_curs=0x7fff72f8a060, curpos=0x7fff72f8a058, sizep=0x7fff72f8a0c8) at sha1_file.c:1400
1400            base = use_pack(p, w_curs, *curpos, &left);


#0  0x0000000000487684 in unpack_object_header (p=0x26ad4c0, w_curs=0x7fff72f8a060, curpos=0x7fff72f8a058, sizep=0x7fff72f8a0c8) at sha1_file.c:1400
#1  0x000000000048827e in unpack_entry (p=0x26ad4c0, obj_offset=490508859, type=0x7fff72f8cd14, sizep=0x7fff72f8a004) at sha1_file.c:1693
#2  0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=490581247, type=0x7fff72f8cd14, sizep=0x7fff72f8a148) at sha1_file.c:1647
#3  0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=490679881, type=0x7fff72f8cd14, sizep=0x7fff72f8a1c8) at sha1_file.c:1647
#4  0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=490685453, type=0x7fff72f8cd14, sizep=0x7fff72f8a248) at sha1_file.c:1647
#5  0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=490689484, type=0x7fff72f8cd14, sizep=0x7fff72f8a2c8) at sha1_file.c:1647
#6  0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=490738466, type=0x7fff72f8cd14, sizep=0x7fff72f8a348) at sha1_file.c:1647
#7  0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=490744208, type=0x7fff72f8cd14, sizep=0x7fff72f8a3c8) at sha1_file.c:1647
#8  0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=490755670, type=0x7fff72f8cd14, sizep=0x7fff72f8a448) at sha1_file.c:1647
#9  0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491146004, type=0x7fff72f8cd14, sizep=0x7fff72f8a4c8) at sha1_file.c:1647
#10 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491148469, type=0x7fff72f8cd14, sizep=0x7fff72f8a548) at sha1_file.c:1647
#11 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491150324, type=0x7fff72f8cd14, sizep=0x7fff72f8a5c8) at sha1_file.c:1647
#12 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491150930, type=0x7fff72f8cd14, sizep=0x7fff72f8a648) at sha1_file.c:1647
#13 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491549282, type=0x7fff72f8cd14, sizep=0x7fff72f8a6c8) at sha1_file.c:1647
#14 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491552398, type=0x7fff72f8cd14, sizep=0x7fff72f8a748) at sha1_file.c:1647
#15 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491552652, type=0x7fff72f8cd14, sizep=0x7fff72f8a7c8) at sha1_file.c:1647
#16 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491553208, type=0x7fff72f8cd14, sizep=0x7fff72f8a848) at sha1_file.c:1647
#17 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491556704, type=0x7fff72f8cd14, sizep=0x7fff72f8a8c8) at sha1_file.c:1647
#18 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491560658, type=0x7fff72f8cd14, sizep=0x7fff72f8a948) at sha1_file.c:1647
#19 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491582507, type=0x7fff72f8cd14, sizep=0x7fff72f8a9c8) at sha1_file.c:1647
#20 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491604310, type=0x7fff72f8cd14, sizep=0x7fff72f8aa48) at sha1_file.c:1647
#21 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491614312, type=0x7fff72f8cd14, sizep=0x7fff72f8aac8) at sha1_file.c:1647
#22 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491666142, type=0x7fff72f8cd14, sizep=0x7fff72f8ab48) at sha1_file.c:1647
#23 0x0000000000488352 in unpack_entry (p=0x26ad4c0, obj_offset=491901113, type=0x7fff72f8cd14, sizep=0x7fff72f8cd08) at sha1_file.c:1647
#24 0x00000000004887ca in read_packed_sha1 (sha1=0x336ba64 "�W\004�\037d\203g��;v\032vF�>�R�", type=0x7fff72f8cd14, size=0x7fff72f8cd08) at sha1_file.c:1957
#25 0x00000000004889fe in read_object (sha1=0x336ba64 "�W\004�\037d\203g��;v\032vF�>�R�", type=0x7fff72f8cd14, size=0x7fff72f8cd08) at sha1_file.c:2047
#26 0x0000000000488bcc in read_sha1_file (sha1=0x26ad4c0 "", type=0x7fff72f8a060, size=0x1d3c923b) at sha1_file.c:2063
#27 0x000000000048f3fd in parse_tree (item=0x336ba60) at tree.c:224
#28 0x0000000000423a32 in mark_object (obj=0x336ba60, type=2, data=<value optimized out>) at builtin-fsck.c:102
#29 0x00000000004673bc in fsck_walk (obj=<value optimized out>, walk=0x423880 <mark_object>, data=0x336ba38) at fsck.c:26
#30 0x0000000000423a4a in mark_object (obj=0x336ba38, type=2, data=<value optimized out>) at builtin-fsck.c:105
#31 0x00000000004673bc in fsck_walk (obj=<value optimized out>, walk=0x423880 <mark_object>, data=0x66fff78) at fsck.c:26
#32 0x0000000000423a4a in mark_object (obj=0x66fff78, type=2, data=<value optimized out>) at builtin-fsck.c:105
#33 0x00000000004673bc in fsck_walk (obj=<value optimized out>, walk=0x423880 <mark_object>, data=0x66c9a28) at fsck.c:26
#34 0x0000000000423a4a in mark_object (obj=0x66c9a28, type=2, data=<value optimized out>) at builtin-fsck.c:105
#35 0x0000000000467299 in fsck_walk (obj=0x6bea7b0, walk=0x423880 <mark_object>, data=0x6bea7b0) at fsck.c:50
#36 0x000000000042390d in mark_object (obj=0x6bea7b0, type=1, data=<value optimized out>) at builtin-fsck.c:105
#37 0x00000000004672d1 in fsck_walk (obj=<value optimized out>, walk=0x423880 <mark_object>, data=0x3283fd0) at fsck.c:57
#38 0x000000000042390d in mark_object (obj=0x3283fd0, type=1, data=<value optimized out>) at builtin-fsck.c:105
#39 0x00000000004672d1 in fsck_walk (obj=<value optimized out>, walk=0x423880 <mark_object>, data=0x3283f88) at fsck.c:57
#40 0x000000000042390d in mark_object (obj=0x3283f88, type=1, data=<value optimized out>) at builtin-fsck.c:105
[...]

The stack trace in total has about ~80000 frames.

Does anyone have any suggestions on how to debug this?

Thanks,
Simon

Re: git fsck segmentation fault

[Nicolas Pitre]

On Thu, 27 Nov 2008, Simon Hausmann wrote:

> Hi,
> 
> when running git fsck --full -v (version 1.6.0.4.26.g7c30c) on a medium sized

That version doesn't exist in the git repo.

> (930M) repository I get a segfault.
> 
> The backtrace indicates an infinite recursion. Here's the output from the last
> few lines:
[...]

Could you try with latest master branch please?  It is more robust 
against some kind of pack corruptions that could send the code into 
infinite loops.


Nicolas

Re: git fsck segmentation fault

[Simon Hausmann]

On Thursday 27 November 2008 18:47:41 Nicolas Pitre wrote:
> On Thu, 27 Nov 2008, Simon Hausmann wrote:
> > Hi,
> >
> > when running git fsck --full -v (version 1.6.0.4.26.g7c30c) on a medium
> > sized
>
> That version doesn't exist in the git repo.

Ah, oops, it was a merge commit, corresponding to maint as of 5aa3bd.

> > (930M) repository I get a segfault.
> >
> > The backtrace indicates an infinite recursion. Here's the output from the
> > last few lines:
>
> [...]
>
> Could you try with latest master branch please?  It is more robust
> against some kind of pack corruptions that could send the code into
> infinite loops.

Same problem with git version 1.6.0.4.790.gaa14a

:-/

Simon

Re: git fsck segmentation fault

[Simon Hausmann]

On Thursday 27 November 2008 20:10:20 Simon Hausmann wrote:
> On Thursday 27 November 2008 18:47:41 Nicolas Pitre wrote:
> > On Thu, 27 Nov 2008, Simon Hausmann wrote:
> > > Hi,
> > >
> > > when running git fsck --full -v (version 1.6.0.4.26.g7c30c) on a medium
> > > sized
> >
> > That version doesn't exist in the git repo.
>
> Ah, oops, it was a merge commit, corresponding to maint as of 5aa3bd.
>
> > > (930M) repository I get a segfault.
> > >
> > > The backtrace indicates an infinite recursion. Here's the output from
> > > the last few lines:
> >
> > [...]
> >
> > Could you try with latest master branch please?  It is more robust
> > against some kind of pack corruptions that could send the code into
> > infinite loops.
>
> Same problem with git version 1.6.0.4.790.gaa14a

Forgot to paste the changed line numbers of the recursion:

#54 0x0000000000493c6d in parse_tree (item=0x20d0178) at tree.c:224
#55 0x0000000000424ca2 in mark_object (obj=0x20d0178, type=2, data=<value 
optimized out>) at builtin-fsck.c:102
#56 0x0000000000468d1c in fsck_walk (obj=<value optimized out>, walk=0x424af0 
<mark_object>, data=0x20d0128) at fsck.c:26
#57 0x0000000000424cba in mark_object (obj=0x20d0128, type=2, data=<value 
optimized out>) at builtin-fsck.c:105
#58 0x0000000000468d1c in fsck_walk (obj=<value optimized out>, walk=0x424af0 
<mark_object>, data=0x1edb448) at fsck.c:26
#59 0x0000000000424cba in mark_object (obj=0x1edb448, type=2, data=<value 
optimized out>) at builtin-fsck.c:105
#60 0x0000000000468d1c in fsck_walk (obj=<value optimized out>, walk=0x424af0 
<mark_object>, data=0x1edb420) at fsck.c:26
#61 0x0000000000424cba in mark_object (obj=0x1edb420, type=2, data=<value 
optimized out>) at builtin-fsck.c:105
#62 0x0000000000468bf9 in fsck_walk (obj=0x241a750, walk=0x424af0 
<mark_object>, data=0x241a750) at fsck.c:50
#63 0x0000000000424b7d in mark_object (obj=0x241a750, type=1, data=<value 
optimized out>) at builtin-fsck.c:105
#64 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
<mark_object>, data=0x241a708) at fsck.c:57
#65 0x0000000000424b7d in mark_object (obj=0x241a708, type=1, data=<value 
optimized out>) at builtin-fsck.c:105
#66 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
<mark_object>, data=0x4dea0b0) at fsck.c:57
#67 0x0000000000424b7d in mark_object (obj=0x4dea0b0, type=1, data=<value 
optimized out>) at builtin-fsck.c:105
#68 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
<mark_object>, data=0x488ff78) at fsck.c:57
#69 0x0000000000424b7d in mark_object (obj=0x488ff78, type=1, data=<value 
optimized out>) at builtin-fsck.c:105
#70 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
<mark_object>, data=0x488bd18) at fsck.c:57
#71 0x0000000000424b7d in mark_object (obj=0x488bd18, type=1, data=<value 
optimized out>) at builtin-fsck.c:105
#72 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
<mark_object>, data=0x313c0b0) at fsck.c:57
#73 0x0000000000424b7d in mark_object (obj=0x313c0b0, type=1, data=<value 
optimized out>) at builtin-fsck.c:105
[recursion between line 105 and 57]

Simon

Re: git fsck segmentation fault

[Nicolas Pitre]

On Thu, 27 Nov 2008, Simon Hausmann wrote:

> On Thursday 27 November 2008 20:10:20 Simon Hausmann wrote:
> > On Thursday 27 November 2008 18:47:41 Nicolas Pitre wrote:
> > > On Thu, 27 Nov 2008, Simon Hausmann wrote:
> > > > Hi,
> > > >
> > > > when running git fsck --full -v (version 1.6.0.4.26.g7c30c) on a medium
> > > > sized
> > >
> > > That version doesn't exist in the git repo.
> >
> > Ah, oops, it was a merge commit, corresponding to maint as of 5aa3bd.
> >
> > > > (930M) repository I get a segfault.
> > > >
> > > > The backtrace indicates an infinite recursion. Here's the output from
> > > > the last few lines:
> > >
> > > [...]
> > >
> > > Could you try with latest master branch please?  It is more robust
> > > against some kind of pack corruptions that could send the code into
> > > infinite loops.
> >
> > Same problem with git version 1.6.0.4.790.gaa14a
> 
> Forgot to paste the changed line numbers of the recursion:
[...]

Well... Your initial backtrace showed recursion in unpack_entry() which 
was rather odd in the first place.  Your latest backtrace shows a loop 
in make_object() which has nothing to do what so ever with 
unpack_entry().  So the backtrace might not be really useful.

I suspect you'll have to bisect git to find the issue, given that some 
old version can be found to be good.  For example, does it work with 
v1.5.2.5?


Nicolas

Re: git fsck segmentation fault

[Simon Hausmann]

On Thursday 27 November 2008 Nicolas Pitre, wrote:
> On Thu, 27 Nov 2008, Simon Hausmann wrote:
> > On Thursday 27 November 2008 20:10:20 Simon Hausmann wrote:
> > > On Thursday 27 November 2008 18:47:41 Nicolas Pitre wrote:
> > > > On Thu, 27 Nov 2008, Simon Hausmann wrote:
> > > > > Hi,
> > > > >
> > > > > when running git fsck --full -v (version 1.6.0.4.26.g7c30c) on a
> > > > > medium sized
> > > >
> > > > That version doesn't exist in the git repo.
> > >
> > > Ah, oops, it was a merge commit, corresponding to maint as of 5aa3bd.
> > >
> > > > > (930M) repository I get a segfault.
> > > > >
> > > > > The backtrace indicates an infinite recursion. Here's the output
> > > > > from the last few lines:
> > > >
> > > > [...]
> > > >
> > > > Could you try with latest master branch please?  It is more robust
> > > > against some kind of pack corruptions that could send the code into
> > > > infinite loops.
> > >
> > > Same problem with git version 1.6.0.4.790.gaa14a
> >
> > Forgot to paste the changed line numbers of the recursion:
>
> [...]
>
> Well... Your initial backtrace showed recursion in unpack_entry() which
> was rather odd in the first place.  Your latest backtrace shows a loop
> in make_object() which has nothing to do what so ever with
> unpack_entry().  So the backtrace might not be really useful.
>
> I suspect you'll have to bisect git to find the issue, given that some
> old version can be found to be good.  For example, does it work with
> v1.5.2.5?

Ah yes, v1.5.2.5 works! (phew, and it verified that the repo is fine)

Ok, I bisected and "git bisect run" identified the following commit as first bad 
commit:

commit 271b8d25b25e49b367087440e093e755e5f35aa9
Author: Martin Koegler <mkoegler@auto.tuwien.ac.at>
Date:   Mon Feb 25 22:46:05 2008 +0100

    builtin-fsck: move away from object-refs to fsck_walk




Simon

Re: git fsck segmentation fault

[Nicolas Pitre]

Has this been looked at?  Martin?

On Fri, 28 Nov 2008, Simon Hausmann wrote:

> On Thursday 27 November 2008 Nicolas Pitre, wrote:
> > On Thu, 27 Nov 2008, Simon Hausmann wrote:
> > > On Thursday 27 November 2008 20:10:20 Simon Hausmann wrote:
> > > > On Thursday 27 November 2008 18:47:41 Nicolas Pitre wrote:
> > > > > On Thu, 27 Nov 2008, Simon Hausmann wrote:
> > > > > > Hi,
> > > > > >
> > > > > > when running git fsck --full -v (version 1.6.0.4.26.g7c30c) on a
> > > > > > medium sized
> > > > >
> > > > > That version doesn't exist in the git repo.
> > > >
> > > > Ah, oops, it was a merge commit, corresponding to maint as of 5aa3bd.
> > > >
> > > > > > (930M) repository I get a segfault.
> > > > > >
> > > > > > The backtrace indicates an infinite recursion. Here's the output
> > > > > > from the last few lines:
> > > > >
> > > > > [...]
> > > > >
> > > > > Could you try with latest master branch please?  It is more robust
> > > > > against some kind of pack corruptions that could send the code into
> > > > > infinite loops.
> > > >
> > > > Same problem with git version 1.6.0.4.790.gaa14a
> > >
> > > Forgot to paste the changed line numbers of the recursion:
> >
> > [...]
> >
> > Well... Your initial backtrace showed recursion in unpack_entry() which
> > was rather odd in the first place.  Your latest backtrace shows a loop
> > in make_object() which has nothing to do what so ever with
> > unpack_entry().  So the backtrace might not be really useful.
> >
> > I suspect you'll have to bisect git to find the issue, given that some
> > old version can be found to be good.  For example, does it work with
> > v1.5.2.5?
> 
> Ah yes, v1.5.2.5 works! (phew, and it verified that the repo is fine)
> 
> Ok, I bisected and "git bisect run" identified the following commit as first bad 
> commit:
> 
> commit 271b8d25b25e49b367087440e093e755e5f35aa9
> Author: Martin Koegler <mkoegler@auto.tuwien.ac.at>
> Date:   Mon Feb 25 22:46:05 2008 +0100
> 
>     builtin-fsck: move away from object-refs to fsck_walk
> 
> 
> 
> 
> Simon
> 

Re: git fsck segmentation fault

[Martin Koegler]

On Tue, Dec 09, 2008 at 02:09:58PM -0500, Nicolas Pitre wrote:
> Has this been looked at?  Martin?

I have not noticed this message.

> #54 0x0000000000493c6d in parse_tree (item=0x20d0178) at tree.c:224
> #55 0x0000000000424ca2 in mark_object (obj=0x20d0178, type=2, data=<value 
> optimized out>) at builtin-fsck.c:102
> #56 0x0000000000468d1c in fsck_walk (obj=<value optimized out>, walk=0x424af0 
> <mark_object>, data=0x20d0128) at fsck.c:26
> #57 0x0000000000424cba in mark_object (obj=0x20d0128, type=2, data=<value 
> optimized out>) at builtin-fsck.c:105
> #58 0x0000000000468d1c in fsck_walk (obj=<value optimized out>, walk=0x424af0 
> <mark_object>, data=0x1edb448) at fsck.c:26
> #59 0x0000000000424cba in mark_object (obj=0x1edb448, type=2, data=<value 
> optimized out>) at builtin-fsck.c:105
> #60 0x0000000000468d1c in fsck_walk (obj=<value optimized out>, walk=0x424af0 
> <mark_object>, data=0x1edb420) at fsck.c:26
> #61 0x0000000000424cba in mark_object (obj=0x1edb420, type=2, data=<value 
> optimized out>) at builtin-fsck.c:105
> #62 0x0000000000468bf9 in fsck_walk (obj=0x241a750, walk=0x424af0 
> <mark_object>, data=0x241a750) at fsck.c:50
> #63 0x0000000000424b7d in mark_object (obj=0x241a750, type=1, data=<value 
> optimized out>) at builtin-fsck.c:105
> #64 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
> <mark_object>, data=0x241a708) at fsck.c:57
> #65 0x0000000000424b7d in mark_object (obj=0x241a708, type=1, data=<value 
> optimized out>) at builtin-fsck.c:105
> #66 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
> <mark_object>, data=0x4dea0b0) at fsck.c:57
> #67 0x0000000000424b7d in mark_object (obj=0x4dea0b0, type=1, data=<value 
> optimized out>) at builtin-fsck.c:105
> #68 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
> <mark_object>, data=0x488ff78) at fsck.c:57
> #69 0x0000000000424b7d in mark_object (obj=0x488ff78, type=1, data=<value 
> optimized out>) at builtin-fsck.c:105
> #70 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
> <mark_object>, data=0x488bd18) at fsck.c:57
> #71 0x0000000000424b7d in mark_object (obj=0x488bd18, type=1, data=<value 
> optimized out>) at builtin-fsck.c:105
> #72 0x0000000000468c31 in fsck_walk (obj=<value optimized out>, walk=0x424af0 
> <mark_object>, data=0x313c0b0) at fsck.c:57
> #73 0x0000000000424b7d in mark_object (obj=0x313c0b0, type=1, data=<value 
> optimized out>) at builtin-fsck.c:105
> [recursion between line 105 and 57]

If I look at the backtrace, nothing seems wrong. The obj pointers for
mark_object are all different, so its not stuck in a loop. If you look
at type, you will see that it traverses commits (type=1) untils
#63. Then it traverses trees (type=2).

At my option, there is a commit with a very long ancestory (~40.000
[stack frame count/2]). As we do depth first search for the reachability
check, we need about 80.000 frames.

I suggest, that you retry with a very much bigger stack (ulimit -s).

mfg Martin Kögler

Re: git fsck segmentation fault

[Martin Koegler]

Maybe something like this could help:

>From 32be177cbb0825fc019200b172f3d79117b28140 Mon Sep 17 00:00:00 2001
From: Martin Koegler <mkoegler@auto.tuwien.ac.at>
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.

Not-really-tested-by: Martin Koegler
Signed-off-by: Martin Koegler <mkoegler@auto.tuwien.ac.at>
---
 builtin-fsck.c |   19 +++++++++++++++++--
 1 files changed, 17 insertions(+), 2 deletions(-)

diff --git a/builtin-fsck.c b/builtin-fsck.c
index afded5e..8184699 100644
--- a/builtin-fsck.c
+++ b/builtin-fsck.c
@@ -36,6 +36,9 @@ static int verbose;
 #define DIRENT_SORT_HINT(de) ((de)->d_ino)
 #endif
 
+static int objectstack_nr, objectstack_alloc;
+struct object **objectstack;
+
 static void objreport(struct object *obj, const char *severity,
                       const char *err, va_list params)
 {
@@ -66,9 +69,7 @@ static int fsck_error_func(struct object *obj, int type, const char *err, ...)
 
 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",
@@ -95,6 +96,15 @@ static int mark_object(struct object *obj, int type, void *data)
 		}
 		return 1;
 	}
+	ALLOC_GROW(objectstack, objectstack_nr + 1, objectstack_alloc);
+	objectstack[objectstack_nr++] = obj;
+	return 0;
+}
+
+static int mark_child_object(struct object *obj)
+{
+	struct tree *tree = NULL;
+	int result;
 
 	if (obj->type == OBJ_TREE) {
 		obj->parsed = 0;
@@ -116,6 +126,11 @@ static int mark_object(struct object *obj, int type, void *data)
 static void mark_object_reachable(struct object *obj)
 {
 	mark_object(obj, OBJ_ANY, 0);
+	while (objectstack_nr > 0) {
+		struct object *obj = objectstack[--objectstack_nr];
+		if (mark_child_object(obj) < 0)
+			break;
+	}
 }
 
 static int mark_used(struct object *obj, int type, void *data)
-- 
1.6.1.rc2.283.g32be1

Re: git fsck segmentation fault

[Junio C Hamano]

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

> Maybe something like this could help:

>>From 32be177cbb0825fc019200b172f3d79117b28140 Mon Sep 17 00:00:00 2001
> From: Martin Koegler <mkoegler@auto.tuwien.ac.at>
> 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.

Re: git fsck segmentation fault

[Martin Koegler]

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

Re: git fsck segmentation fault

[Junio C Hamano]

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

> 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).

Yes, that is where my "initially expected" comes from.  I was not
complaining or suggesting the behaviour to change.

I was fooled by the word *walk* in the name, which implies an
implementation of walking connectivity fully, with or without an ability
for the callback to tell the machinery when to or not to dig deeper.  It
wouldn't have been confusing if it were named "fsck_step()", which is what
the function is about: performing a single step of digging deeper.