git describe --contains doesn't work properly for a commit

Hi,
I have just encountered an old kernel git commit:
commit c854363e80b49dd04a4de18ebc379eb8c8806674
Author: Dave Chinner [off-list ref]
Date:   Sat Feb 6 12:39:36 2010 +1100

    xfs: Use delayed write for inodes rather than async V2
[...]

which cannot be described properly:
$ git describe --contains c854363e80b49dd04a4de18ebc379eb8c8806674
fatal: cannot describe 'c854363e80b49dd04a4de18ebc379eb8c8806674'

but it seems to find a tag on which the commit is based:
$ git describe c854363e80b49dd04a4de18ebc379eb8c8806674
v2.6.33-rc4-49-gc854363e80b4

if I follow parents
sha=c854363e80b49dd04a4de18ebc379eb8c8806674; 
while true
do 
	parent=$(git show --format=%P $sha | head -1)
	echo $sha $parent
	git describe --contains $parent && break
	sha=$parent
done
c854363e80b49dd04a4de18ebc379eb8c8806674 777df5afdb26c71634edd60582be620ff94e87a0
fatal: cannot describe '777df5afdb26c71634edd60582be620ff94e87a0'
777df5afdb26c71634edd60582be620ff94e87a0 d5db0f97fbbeff11c88dec1aaf1536a975afbaeb
fatal: cannot describe 'd5db0f97fbbeff11c88dec1aaf1536a975afbaeb'
d5db0f97fbbeff11c88dec1aaf1536a975afbaeb 388f1f0c346b533b06d8bc792f7204ebc3e4b7da
v2.6.34-rc1~278^2~14

I am using:
$ git --version
git version 2.1.4

but the same seems to be the case with older git version (1.8.5.6).
$ git rev-list c854363e80b49dd04a4de18ebc379eb8c8806674..v2.6.34 | wc -l
11648

So there seems to be a line between the two commits AFAIU.

Is the history somehow broken or is it a bug in git?
-- 
Michal Hocko
SUSE Labs

On Thu 26-02-15 14:35:34, Michal Hocko wrote:

Hi,
I have just encountered an old kernel git commit:
commit c854363e80b49dd04a4de18ebc379eb8c8806674
Author: Dave Chinner [off-list ref]
Date:   Sat Feb 6 12:39:36 2010 +1100

    xfs: Use delayed write for inodes rather than async V2
[...]

 
OK, I've managed to recreate this in a simple repo with 3 commits:
$ git log --format="%H %cd"
ab0efec2b697f2f9f864bb0e2cd77308d1f04561 Thu Feb 26 15:18:36 2015 +0100
d63972e4e4e7eda0444e56739ad09bfbc476b9bd Wed Feb 26 15:18:30 2014 +0100
108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3 Thu Feb 26 14:57:29 2015 +0100

The commit in the middle was ammended to have committer date in the
past.
$ git describe --contains d63972e4e4e7eda0444e56739ad09bfbc476b9bd
tag~1

but
$ git describe --contains 108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3
fatal: cannot describe '108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3'

I guess this is the same issue reported previously here:
http://git.661346.n2.nabble.com/git-describe-contains-fails-on-given-tree-td5448286.html

Can this be fixed somehow or it would lead to other kind of issues?
-- 
Michal Hocko
SUSE Labs

On Thu, Feb 26, 2015 at 03:23:14PM +0100, Michal Hocko wrote:

The commit in the middle was ammended to have committer date in the
past.
$ git describe --contains d63972e4e4e7eda0444e56739ad09bfbc476b9bd
tag~1

but
$ git describe --contains 108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3
fatal: cannot describe '108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3'

I guess this is the same issue reported previously here:
http://git.661346.n2.nabble.com/git-describe-contains-fails-on-given-tree-td5448286.html

Yes, the "describe --contains" algorithm uses timestamps to cut off the
traversal, so it can do the wrong thing if there's clock skew. It has a
"slop" margin of one day, but skew larger than that can fool it.

Can this be fixed somehow or it would lead to other kind of issues?

The options are basically:

  1. Stop cutting off the traversal based on timestamps. This will make
     the common case of valid timestamps much slower, though, as it will
     have to walk all the way to the roots.

  2. Use a different slop mechanism. For example, keep walking up to 5
     commits past a commit suspected to be past the cutoff. This is
     relatively easy to do (we do it for "--since" checks), and would
     catch your case above. But of course it does not catch all cases of
     skew.

  3. Introduce a more trust-worthy mechanism for ordering commits. The
     timestamp here is really just a proxy for the oft-discussed
     "generation number" of the commit within the graph. We've avoided
     adding generation numbers because of the storage/complexity issues.

-Peff

Jeff King venit, vidit, dixit 04.03.2015 11:54:

On Thu, Feb 26, 2015 at 03:23:14PM +0100, Michal Hocko wrote:

quoted

The commit in the middle was ammended to have committer date in the
past.
$ git describe --contains d63972e4e4e7eda0444e56739ad09bfbc476b9bd
tag~1

but
$ git describe --contains 108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3
fatal: cannot describe '108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3'

I guess this is the same issue reported previously here:
http://git.661346.n2.nabble.com/git-describe-contains-fails-on-given-tree-td5448286.html

Yes, the "describe --contains" algorithm uses timestamps to cut off the
traversal, so it can do the wrong thing if there's clock skew. It has a
"slop" margin of one day, but skew larger than that can fool it.

quoted

Can this be fixed somehow or it would lead to other kind of issues?

The options are basically:

  1. Stop cutting off the traversal based on timestamps. This will make
     the common case of valid timestamps much slower, though, as it will
     have to walk all the way to the roots.

  2. Use a different slop mechanism. For example, keep walking up to 5
     commits past a commit suspected to be past the cutoff. This is
     relatively easy to do (we do it for "--since" checks), and would
     catch your case above. But of course it does not catch all cases of
     skew.

  3. Introduce a more trust-worthy mechanism for ordering commits. The
     timestamp here is really just a proxy for the oft-discussed
     "generation number" of the commit within the graph. We've avoided
     adding generation numbers because of the storage/complexity issues.

Hmmh.

Storage: one int (or maybe less) per commit doesn't sound too bad. We
can probably do without on bare repos by default.

Complexity: Was that due to replace refs? Other than that, it seemed to
be simple: max(parent generation numbers)+1.

... or can reachability bitmaps help???

Michael

On Wed, Mar 04, 2015 at 04:06:17PM +0100, Michael J Gruber wrote:

quoted

  3. Introduce a more trust-worthy mechanism for ordering commits. The
     timestamp here is really just a proxy for the oft-discussed
     "generation number" of the commit within the graph. We've avoided
     adding generation numbers because of the storage/complexity issues.

Hmmh.

Storage: one int (or maybe less) per commit doesn't sound too bad. We
can probably do without on bare repos by default.

Complexity: Was that due to replace refs? Other than that, it seemed to
be simple: max(parent generation numbers)+1.

Calculating them is simple. Caching and storage is the bigger question.
When we do we generate them? Where do we store them? What do we do with
replace-refs and grafts?

I think the answers are "at repack time", "in an auxiliary file alongside
the pack idx", and "we turn it off completely when these features are in
use".

See:

  http://thread.gmane.org/gmane.comp.version-control.git/214916

for a sample implementation.

... or can reachability bitmaps help???

Sometimes. If you are asking about --contains traversals, then bitmaps
can let you stop the traversal early. We have some patches that do this
that are running in production at GitHub, but they are kind of gnarly.
One of my goals is to clean them up and get them upstream.

It's also part of why I didn't pursue the series above further. Making
"--contains" faster is one goal, but making "rev-list --objects --all"
faster was more important (since we do it for every fetch). And making
commits faster is only half the equation there.

-Peff