bug in name-rev on linux-2.6 repo?

bug in name-rev on linux-2.6 repo?

[maximilian attems]

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


 git --version
 git version 1.7.0.4


~/src/linux-2.6$ git branch | grep ^*
* master

never happened to me before but don't seem to get ancestry of
that ext4 merge, can you check what is wrong there?
bug verified also on older git 1.6.5

thanks

-- 
maks

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

[Tay Ray Chuan]

Hi,

On Thu, Apr 22, 2010 at 3:58 AM, maximilian attems <max@stro.at> wrote:
> ~/src/linux-2.6$ git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
>  a1de02dccf906faba2ee2d99cac56799bda3b96a undefined

have you fetched tags too?

-- 
Cheers,
Ray Chuan

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

[maximilian attems]

On Thu, 22 Apr 2010, Tay Ray Chuan wrote:

> Hi,
> 
> On Thu, Apr 22, 2010 at 3:58 AM, maximilian attems <max@stro.at> wrote:
> > ~/src/linux-2.6$ git name-rev a1de02dccf906faba2ee2d99cac56799bda3b96a
> >  a1de02dccf906faba2ee2d99cac56799bda3b96a undefined
> 
> have you fetched tags too?

~/src/linux-2.6$ git tag | grep v2.6.34-rc1

v2.6.34-rc1

did you try to reproduce at aboves repo the specific commit?
-- 
maks

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

[Jonathan Nieder]

Hi maks,

maximilian attems wrote:

> ~/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 log ^v2.6.34-rc5 ^origin/master a1de02dccf --oneline
| a1de02d ext4: fix async i/o writes beyond 4GB to a sparse file

So maybe it was rewritten; searching for a commit with the same subject:

| $ git log v2.6.33..origin/master --grep='ext4: fix async' --oneline
| a1de02d ext4: fix async i/o writes beyond 4GB to a sparse file

Huh?  Is it included in origin/master or not?

| $ git version
| git version 1.7.1.rc1

Jonathan

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

[Andreas Schwab]

Jonathan Nieder <jrnieder@gmail.com> writes:

> Hi maks,
>
> maximilian attems wrote:
>
>> ~/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."

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

[Jeff King]

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

> Jonathan Nieder <jrnieder@gmail.com> writes:
> 
> > Hi maks,
> >
> > maximilian attems wrote:
> >
> >> ~/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

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

[Jeff King]

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

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

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

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

[Jonathan Nieder]

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

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

[Jeff King]

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

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

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

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

[Jonathan Nieder]

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:
>> 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
[...]
> 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

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

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

[Linus Torvalds]

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

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

[tytso]

On Thu, Apr 22, 2010 at 11:20:34AM -0700, Linus Torvalds wrote:
> 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.
>
> > 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

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

[Jonathan Nieder]

Andreas Schwab wrote:
> Jonathan Nieder <jrnieder@gmail.com> writes:

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