threads / discuss / 3603

endless loop: ?

Subject: endless loop: ?

## tl;dr

4 messages between Mar 8, 2006 and Mar 9, 2006.

replies: 3people: 2as markdown or json

Matthias Urlichs· Mar 8, 2006, 20:04 UTC · lore

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

Matthias Urlichs· Mar 9, 2006, 04:04 UTC · re: Matthias Urlichs · lore

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

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

Linus Torvalds· Mar 9, 2006, 05:48 UTC · re: Matthias Urlichs · lore

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

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

smurf@smurf.noris.de· Mar 9, 2006, 10:20 UTC · re: Linus Torvalds · lore

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

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