Re: bug in name-rev on linux-2.6 repo?

Jonathan Nieder [off-list ref] writes:

Hi maks,

maximilian attems wrote:

quoted

~/src/linux-2.6$ git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
 a1de02dccf906faba2ee2d99cac56799bda3b96a undefined

Thanks for pointing it out.  This is weird.

The commit doesn’t seem to be part of any tagged release, nor linus’s
master:

$ git branch --contains a1de02dccf906faba2ee2d99cac56799bda3b96a
* master
$ git merge-base v2.6.34-rc1 a1de02dccf906faba2ee2d99cac56799bda3b96a
a1de02dccf906faba2ee2d99cac56799bda3b96a
git merge-base v2.6.33 a1de02dccf906faba2ee2d99cac56799bda3b96a
724e6d3fe8003c3f60bf404bf22e4e331327c596

So it has been merged beween v2.6.33 and v2.6.34-rc1

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

On Thu, Apr 22, 2010 at 04:29:29PM +0200, Andreas Schwab wrote:

Jonathan Nieder [off-list ref] writes:

quoted

Hi maks,

maximilian attems wrote:

quoted

~/src/linux-2.6$ git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
 a1de02dccf906faba2ee2d99cac56799bda3b96a undefined

Thanks for pointing it out.  This is weird.

The commit doesn’t seem to be part of any tagged release, nor linus’s
master:

$ git branch --contains a1de02dccf906faba2ee2d99cac56799bda3b96a
* master
$ git merge-base v2.6.34-rc1 a1de02dccf906faba2ee2d99cac56799bda3b96a
a1de02dccf906faba2ee2d99cac56799bda3b96a
git merge-base v2.6.33 a1de02dccf906faba2ee2d99cac56799bda3b96a
724e6d3fe8003c3f60bf404bf22e4e331327c596

So it has been merged beween v2.6.33 and v2.6.34-rc1

Hmm. Maybe clock skew in the commit timestamps is at fault? With this
patch to git:

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 06a38ac..7a024ab 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c

@@ -29,9 +29,6 @@ static void name_rev(struct commit *commit,
 	if (!commit->object.parsed)
 		parse_commit(commit);
 
-	if (commit->date < cutoff)
-		return;
-
 	if (deref) {
 		char *new_name = xmalloc(strlen(tip_name)+3);
 		strcpy(new_name, tip_name);

I get:

  $ $ git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
  a1de02dccf906faba2ee2d99cac56799bda3b96a tags/v2.6.34-rc1~199^2~35

but I haven't tracked down the problematic commit and timestamp yet.

-Peff

Andreas Schwab wrote:

Jonathan Nieder [off-list ref] writes:

quoted

The commit doesn’t seem to be part of any tagged release, nor linus’s
master:

$ git branch --contains a1de02dccf906faba2ee2d99cac56799bda3b96a
* master
$ git merge-base v2.6.34-rc1 a1de02dccf906faba2ee2d99cac56799bda3b96a
a1de02dccf906faba2ee2d99cac56799bda3b96a
git merge-base v2.6.33 a1de02dccf906faba2ee2d99cac56799bda3b96a
724e6d3fe8003c3f60bf404bf22e4e331327c596

So it has been merged beween v2.6.33 and v2.6.34-rc1

To first commit after rc8, to be exact.  But for some reason, the
revision walker doesn’t notice that:

 $ git rev-list origin/master..a1de02dcc | wc -l
 1

The tip of the relevant branch before merging was 64e290e (thanks to
Johan’s --ancestor-path suggestion and Junio’s nice implementation).
So we can walk up through the revisions:

 $ git rev-parse 64e290e~35
 a1de02dccf906faba2ee2d99cac56799bda3b96a
 $ git rev-list origin/master..64e290e~35 | wc -l
 0
 $ git rev-list origin/master..$(git rev-parse 64e290e~35) | wc -l
 1
 $ for i in 36 35 34 33 32 31 30
 > do
 >	printf "%d " "$i"
 >	git rev-list origin/master..$(git rev-parse 64e290e~$i) | wc -l
 > done
 36 0
 35 1
 34 2
 33 3
 32 4
 31 0
 30 0

Using v2.6.34-rc1~199 (the ext4 merge commit) instead of origin/master
reveals the same problem.  v2.6.34-rc1~199^2 (the tip of the ext4
branch) does not.

Hope that helps.
Jonathan

On Thu, Apr 22, 2010 at 10:44:33AM -0400, Jeff King wrote:

Still looking, but definitely some kind of skew problem. Reverting the
patch above and doing this also works:

diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index 06a38ac..198e04d 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c

@@ -5,7 +5,7 @@
 #include "refs.h"
 #include "parse-options.h"
 
-#define CUTOFF_DATE_SLOP 86400 /* one day */
+#define CUTOFF_DATE_SLOP (60*86400)
 
 typedef struct rev_name {
 	const char *tip_name;

but a 59-day slop does not.

-Peff

Jeff King wrote:

Still looking, but definitely some kind of skew problem.

That explains it, then:

$ git log --format=%cd' %h' 19f5fb7 ^v2.6.34-rc1~200
Sun Jan 24 14:34:07 2010 -0500 19f5fb7
Mon Dec 7 10:36:20 2009 -0500 d2eecb0
Fri Jan 1 01:00:21 2010 -0500 f8ec9d6
Wed Dec 23 07:45:44 2009 -0500 71f2be2
Fri Jan 22 17:40:42 2010 -0500 1f2acb6
Mon Feb 15 20:17:55 2010 -0500 15121c1
Thu Feb 4 23:58:38 2010 -0500 a1de02d

This part of the history is linear.

Is the rule that every commit must be at most one day before each of
its parents?  This should probably be documented somewhere, since it
is possible to override the committer date with GIT_COMMITTER_DATE.

Jonathan

On Thu, Apr 22, 2010 at 10:03:25AM -0500, Jonathan Nieder wrote:

Jeff King wrote:

quoted

Still looking, but definitely some kind of skew problem.

That explains it, then:

$ git log --format=%cd' %h' 19f5fb7 ^v2.6.34-rc1~200
Sun Jan 24 14:34:07 2010 -0500 19f5fb7
Mon Dec 7 10:36:20 2009 -0500 d2eecb0
Fri Jan 1 01:00:21 2010 -0500 f8ec9d6
Wed Dec 23 07:45:44 2009 -0500 71f2be2
Fri Jan 22 17:40:42 2010 -0500 1f2acb6
Mon Feb 15 20:17:55 2010 -0500 15121c1
Thu Feb 4 23:58:38 2010 -0500 a1de02d

This part of the history is linear.

Thanks for confirming, that was the same stretch of history I ended up
looking at.

Is the rule that every commit must be at most one day before each of
its parents?  This should probably be documented somewhere, since it
is possible to override the committer date with GIT_COMMITTER_DATE.

There is no hard and fast rule. We have to deal with _some_ clock skew,
but I think it has been anybody's guess how much. One can always treat
the graph purely topologically (which is what my first patch removing
the cutoff_date check did), but that usually means more computation. In
this case, we go all the way to the roots instead of looking at a
"recent" subgraph. I think we also look at timestamps in rev-list when
linearizing to avoid doing a full topo-sort, but I don't remember what
effects clock skew can have there.

So what should we do with this incident?

  1. Declare it too much clock skew and ignore it.

  2. Drop the cutoff optimization in favor of correctness. We already do
     this for --stdin, as there is no sensible cutoff for multiple
     inputs. So you can see how much slower it is:

       $ time git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
       a1de02dccf906faba2ee2d99cac56799bda3b96a undefined

       real    0m0.163s
       user    0m0.140s
       sys     0m0.020s

       $ time echo a1de02dccf906faba2ee2d99cac56799bda3b96a |
         git name-rev --stdin
       a1de02dccf906faba2ee2d99cac56799bda3b96a (tags/v2.6.34-rc1~199^2~35)

       real    0m3.411s
       user    0m3.244s
       sys     0m0.164s

     So perhaps it is something one would want to enable with a
     command-line option. Or even something we could fall back on
     automatically as a "slow case" when coming up with an un-nameable
     rev.

  3. Bump the slop date. 60 days would work here. What's reasonable? A
     year? At one year, we are still noticeably slower:

       # patched for CUTOFF_SLOP_DATE (365*86400)
       $ time git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
       a1de02dccf906faba2ee2d99cac56799bda3b96a
       tags/v2.6.34-rc1~199^2~35

       real    0m1.075s
       user    0m1.028s
       sys     0m0.044s

-Peff

Hi Ted,

maximilian attems attems noticed that ‘git name-rev’ has trouble with
some commits from the ext4 tree [1].  Jeff King investigated:

Jeff King wrote:

On Thu, Apr 22, 2010 at 10:03:25AM -0500, Jonathan Nieder wrote:

quoted

Jeff King wrote:

quoted

quoted

Still looking, but definitely some kind of skew problem.

That explains it, then:

$ git log --format=%cd' %h' 19f5fb7 ^v2.6.34-rc1~200
Sun Jan 24 14:34:07 2010 -0500 19f5fb7
Mon Dec 7 10:36:20 2009 -0500 d2eecb0

[...]

Thanks for confirming, that was the same stretch of history I ended up
looking at.

It seems that the committer date is set to coincide with the author
date for ext4 patches, which breaks some assumptions by git that each
commit has a later or equal committer date than all parents (modulo
some skew).

How is the ext4 tree generated from your patch queue?

Jonathan

[1] http://thread.gmane.org/gmane.comp.version-control.git/145449

quoted

Is the rule that every commit must be at most one day before each of
its parents?  This should probably be documented somewhere, since it
is possible to override the committer date with GIT_COMMITTER_DATE.

There is no hard and fast rule. We have to deal with _some_ clock skew,
but I think it has been anybody's guess how much. One can always treat
the graph purely topologically (which is what my first patch removing
the cutoff_date check did), but that usually means more computation. In
this case, we go all the way to the roots instead of looking at a
"recent" subgraph. I think we also look at timestamps in rev-list when
linearizing to avoid doing a full topo-sort, but I don't remember what
effects clock skew can have there.

So what should we do with this incident?

  1. Declare it too much clock skew and ignore it.

  2. Drop the cutoff optimization in favor of correctness. We already do
     this for --stdin, as there is no sensible cutoff for multiple
     inputs. So you can see how much slower it is:

       $ time git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
       a1de02dccf906faba2ee2d99cac56799bda3b96a undefined

       real    0m0.163s
       user    0m0.140s
       sys     0m0.020s

       $ time echo a1de02dccf906faba2ee2d99cac56799bda3b96a |
         git name-rev --stdin
       a1de02dccf906faba2ee2d99cac56799bda3b96a (tags/v2.6.34-rc1~199^2~35)

       real    0m3.411s
       user    0m3.244s
       sys     0m0.164s

     So perhaps it is something one would want to enable with a
     command-line option. Or even something we could fall back on
     automatically as a "slow case" when coming up with an un-nameable
     rev.

  3. Bump the slop date. 60 days would work here. What's reasonable? A
     year? At one year, we are still noticeably slower:

       # patched for CUTOFF_SLOP_DATE (365*86400)
       $ time git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
       a1de02dccf906faba2ee2d99cac56799bda3b96a
       tags/v2.6.34-rc1~199^2~35

       real    0m1.075s
       user    0m1.028s
       sys     0m0.044s

-Peff

On Thu, 22 Apr 2010, Jonathan Nieder wrote:

Hi Ted, [ nip ]

It seems that the committer date is set to coincide with the author
date for ext4 patches, which breaks some assumptions by git that each
commit has a later or equal committer date than all parents (modulo
some skew).

Argh. Yeah, that's just _evil_. Admittedly, git should never care, but in 
practice it does, because doing the whole graph walk can be _very_ 
expensive. So git wants to think that the committer dates at least have 
_some_ real-life significance.

		Linus

On Thu, Apr 22, 2010 at 11:20:34AM -0700, Linus Torvalds wrote:

On Thu, 22 Apr 2010, Jonathan Nieder wrote:

quoted

Hi Ted, [ nip ]

It seems that the committer date is set to coincide with the author
date for ext4 patches, which breaks some assumptions by git that each
commit has a later or equal committer date than all parents (modulo
some skew).

Argh. Yeah, that's just _evil_. Admittedly, git should never care, but in 
practice it does, because doing the whole graph walk can be _very_ 
expensive. So git wants to think that the committer dates at least have 
_some_ real-life significance.

quoted

How is the ext4 tree generated from your patch queue?

Argh, sorry, I didn't realize git cared.  I didn't realize it was
doing optimizations based on the committer dates.

I'm using guilt to generate the ext4 tree.  The realize why I like
guilt is that keep the patch queue stored in git, both for revision
history purposes and because it allows other people to see and
potentially collaborate on the patch queue maintenance.

A long time ago (as in years), I put in a feature request to the guilt
maintainer that the author and committer dates should be set from the
file modtimes.  This has the property that when I go back and forth
between commits, it doesn't generate excess garbage for git to deal
with, since with the author and committer dates the same, if I do a
"guilt pop" followed by a "guilt push", the commit id of HEAD stays
the same.

So far, so good, until it happens that I decide I need to rewind the
patch queue and update a patch description (maybe to add a kernel
bugzilla entry, or an tested-by, etc.)  Since that touches the
modtime, you can end up with crazy date sequences such as this:

Sun Jan 24 14:34:07 2010 -0500 19f5fb7
Mon Dec 7 10:36:20 2009 -0500 d2eecb0
Fri Jan 1 01:00:21 2010 -0500 f8ec9d6
Wed Dec 23 07:45:44 2009 -0500 71f2be2
Fri Jan 22 17:40:42 2010 -0500 1f2acb6
Mon Feb 15 20:17:55 2010 -0500 15121c1
Thu Feb 4 23:58:38 2010 -0500 a1de02d

In any case, I didn't realize this causes problems, so I can add some
manual processing to make sure this doesn't happen in the future, and
I can look into hacking guilt so that enforces the invariant that the
commiter time/date must always be increasing.

Sorry about causing problems,

					- Ted