endless loop: ?

endless loop: ?

[Matthias Urlichs]

Hmmm...

# ps axurw
smurf    26367 84.1  0.2   3200  2068 pts/1    R    20:08  40:30 /usr/bin/git-rev-list --objects 5771c72e2908fb68906020d07d4e0cb77d2

# strace -p 26367
stat64("/daten/src/noris/kundet.git/.git/objects/23/ae4dd0bab2f05dba8a3c77d4c792542b07b73e", {st_mode=S_IFREG|0644, st_size=204, ...}) = 0
[ lots of different filenames, however ..:]

# strace -p 26367 | grep ae4dd
stat64("/daten/src/noris/kundet.git/.git/objects/23/ae4dd0bab2f05dba8a3c77d4c792542b07b73e", {st_mode=S_IFREG|0644, st_size=204, ...}) = 0
[ lots of repetitions of the same filename => we're in a bad loop of some sort ]

# gdb /daten/src/git/git/git-rev-list 26367
(gdb) whe
#0  0xffffe410 in __kernel_vsyscall ()
#1  0xb7ec08f8 in _xstat () from /lib/tls/i686/cmov/libc.so.6
#2  0x0804e2f0 in find_sha1_file (
    sha1=0x81ddb20 "#\uffffM\u043a\uffff\uffff]\uffff\212<w\uffff\uffff\222T+\a\uffff>\uffffr\005\b\uffff\uffff\035\b",
    st=0xbf87b450) at stat.h:366
#3  0x0804e752 in has_sha1_file (
    sha1=0x81ddb20 "#\uffffM\u043a\uffff\uffff]\uffff\212<w\uffff\uffff\222T+\a\uffff>\uffffr\005\b\uffff\uffff\035\b")
    at sha1_file.c:1600
#4  0x080514f8 in mark_parents_uninteresting (commit=0x0) at revision.c:106
#5  0x080514ed in mark_parents_uninteresting (commit=0x0) at revision.c:96
[ bah ]
#104 0x080514ed in mark_parents_uninteresting (commit=0x0) at revision.c:96
#105 0x080516d8 in prepare_revision_walk (revs=0x8066560) at revision.c:347
#106 0x08049ab4 in main (argc=1, argv=0xbf87c294) at rev-list.c:352

I'll dig further tomorrow...

[PATCH] Don't recurse into parents marked uninteresting.

[Matthias Urlichs]

revision.c:make_parents_uninteresting() is exponential with the number
of merges in the tree. That's fine -- unless some other part of git
already has pulled the whole commit tree into memory ...

---

... or, in other words, "Don't do that, please."

With this patch, all tests still succeed, and the "git push" which
triggered the problem takes 5min instead of an estimated 10mio years.

---

 revision.c |   24 +++++++++++++-----------
 1 files changed, 13 insertions(+), 11 deletions(-)

32c9750691d1ef225ca1641fdf6902e53c25fe5b
diff --git a/revision.c b/revision.c
index 2a33637..713f27e 100644
--- a/revision.c
+++ b/revision.c
@@ -82,18 +82,20 @@ void mark_parents_uninteresting(struct c
 
 	while (parents) {
 		struct commit *commit = parents->item;
-		commit->object.flags |= UNINTERESTING;
+		if (!(commit->object.flags & UNINTERESTING)) {
+			commit->object.flags |= UNINTERESTING;
 
-		/*
-		 * Normally we haven't parsed the parent
-		 * yet, so we won't have a parent of a parent
-		 * here. However, it may turn out that we've
-		 * reached this commit some other way (where it
-		 * wasn't uninteresting), in which case we need
-		 * to mark its parents recursively too..
-		 */
-		if (commit->parents)
-			mark_parents_uninteresting(commit);
+			/*
+			 * Normally we haven't parsed the parent
+			 * yet, so we won't have a parent of a parent
+			 * here. However, it may turn out that we've
+			 * reached this commit some other way (where it
+			 * wasn't uninteresting), in which case we need
+			 * to mark its parents recursively too..
+			 */
+			if (commit->parents)
+				mark_parents_uninteresting(commit);
+		}
 
 		/*
 		 * A missing commit is ok iff its parent is marked
-- 
Matthias Urlichs

Re: [PATCH] Don't recurse into parents marked uninteresting.

[Linus Torvalds]

On Thu, 9 Mar 2006, Matthias Urlichs wrote:
>
> revision.c:make_parents_uninteresting() is exponential with the number
> of merges in the tree. That's fine -- unless some other part of git
> already has pulled the whole commit tree into memory ...

Good call.

However, I would have expected the normal case to be that we haven't even 
parsed the parent yet (as per the comment), so the parent normally 
shouldn't even have the parent pointer (due to not having been parsed).

So what was it that triggered this "parents had already been parsed" 
situation? Is it because we've generated a huge list of "I have it" 
objects when pulling? That would explain it..

		Linus

Re: [PATCH] Don't recurse into parents marked uninteresting.

[smurf]

Hi,

Linus Torvalds:
> So what was it that triggered this "parents had already been parsed" 
> situation? Is it because we've generated a huge list of "I have it" 
> objects when pulling? That would explain it..
> 
Something like that. I've converted a large number of older heads
(ranging from a few months to a few years) from $EVIL_SCM to git,
and tried to push them up to our main repository, which contains the
current development.

-- 
Matthias Urlichs   |   {M:U} IT Design @ m-u-it.de   |  smurf@smurf.noris.de
Disclaimer: The quote was selected randomly. Really. | http://smurf.noris.de
 - -
:read-only user: n. Describes a {luser} who uses computers almost
   exclusively for reading Usenet, bulletin boards, and/or email, rather
   than writing code or purveying useful information. See {twink},
   {terminal junkie}, {lurker}.