{"thread":{"id":"38657","subject":"git describe --contains doesn't work properly for a commit","startedAt":"2015-02-26T13:35:34Z","lastAt":"2015-03-05T06:00:08Z","messageCount":9,"participants":["Michal Hocko","Jeff King","Michael J Gruber","Junio C Hamano","Mike Hommey"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"256687","messageId":"20150226133534.GB14878@dhcp22.suse.cz","threadId":"38657","inReplyTo":null,"subject":"git describe --contains doesn't work properly for a commit","fromName":"Michal Hocko","fromEmail":"mhocko@suse.cz","sentAt":"2015-02-26T13:35:34Z","receivedAt":"2015-02-26T13:35:34Z","isPatch":false,"sender":{"key":"mhocko@suse.cz","avatar":null},"body":"Hi,\nI have just encountered an old kernel git commit:\ncommit c854363e80b49dd04a4de18ebc379eb8c8806674\nAuthor: Dave Chinner <david@fromorbit.com>\nDate:   Sat Feb 6 12:39:36 2010 +1100\n\n    xfs: Use delayed write for inodes rather than async V2\n[...]\n\nwhich cannot be described properly:\n$ git describe --contains c854363e80b49dd04a4de18ebc379eb8c8806674\nfatal: cannot describe 'c854363e80b49dd04a4de18ebc379eb8c8806674'\n\nbut it seems to find a tag on which the commit is based:\n$ git describe c854363e80b49dd04a4de18ebc379eb8c8806674\nv2.6.33-rc4-49-gc854363e80b4\n\nif I follow parents\nsha=c854363e80b49dd04a4de18ebc379eb8c8806674; \nwhile true\ndo \n\tparent=$(git show --format=%P $sha | head -1)\n\techo $sha $parent\n\tgit describe --contains $parent && break\n\tsha=$parent\ndone\nc854363e80b49dd04a4de18ebc379eb8c8806674 777df5afdb26c71634edd60582be620ff94e87a0\nfatal: cannot describe '777df5afdb26c71634edd60582be620ff94e87a0'\n777df5afdb26c71634edd60582be620ff94e87a0 d5db0f97fbbeff11c88dec1aaf1536a975afbaeb\nfatal: cannot describe 'd5db0f97fbbeff11c88dec1aaf1536a975afbaeb'\nd5db0f97fbbeff11c88dec1aaf1536a975afbaeb 388f1f0c346b533b06d8bc792f7204ebc3e4b7da\nv2.6.34-rc1~278^2~14\n\nI am using:\n$ git --version\ngit version 2.1.4\n\nbut the same seems to be the case with older git version (1.8.5.6).\n$ git rev-list c854363e80b49dd04a4de18ebc379eb8c8806674..v2.6.34 | wc -l\n11648\n\nSo there seems to be a line between the two commits AFAIU.\n\nIs the history somehow broken or is it a bug in git?\n-- \nMichal Hocko\nSUSE Labs\n"},{"id":"256690","messageId":"20150226142314.GC14878@dhcp22.suse.cz","threadId":"38657","inReplyTo":"20150226133534.GB14878@dhcp22.suse.cz","subject":"Re: git describe --contains doesn't work properly for a commit","fromName":"Michal Hocko","fromEmail":"mhocko@suse.cz","sentAt":"2015-02-26T14:23:14Z","receivedAt":"2015-02-26T14:23:14Z","isPatch":false,"sender":{"key":"mhocko@suse.cz","avatar":null},"body":"On Thu 26-02-15 14:35:34, Michal Hocko wrote:\n> Hi,\n> I have just encountered an old kernel git commit:\n> commit c854363e80b49dd04a4de18ebc379eb8c8806674\n> Author: Dave Chinner <david@fromorbit.com>\n> Date:   Sat Feb 6 12:39:36 2010 +1100\n> \n>     xfs: Use delayed write for inodes rather than async V2\n> [...]\n \nOK, I've managed to recreate this in a simple repo with 3 commits:\n$ git log --format=\"%H %cd\"\nab0efec2b697f2f9f864bb0e2cd77308d1f04561 Thu Feb 26 15:18:36 2015 +0100\nd63972e4e4e7eda0444e56739ad09bfbc476b9bd Wed Feb 26 15:18:30 2014 +0100\n108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3 Thu Feb 26 14:57:29 2015 +0100\n\nThe commit in the middle was ammended to have committer date in the\npast.\n$ git describe --contains d63972e4e4e7eda0444e56739ad09bfbc476b9bd\ntag~1\n\nbut\n$ git describe --contains 108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3\nfatal: cannot describe '108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3'\n\nI guess this is the same issue reported previously here:\nhttp://git.661346.n2.nabble.com/git-describe-contains-fails-on-given-tree-td5448286.html\n\nCan this be fixed somehow or it would lead to other kind of issues?\n-- \nMichal Hocko\nSUSE Labs\n"},{"id":"256990","messageId":"20150304105408.GA19693@peff.net","threadId":"38657","inReplyTo":"20150226142314.GC14878@dhcp22.suse.cz","subject":"Re: git describe --contains doesn't work properly for a commit","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-04T10:54:08Z","receivedAt":"2015-03-04T10:54:08Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Feb 26, 2015 at 03:23:14PM +0100, Michal Hocko wrote:\n\n> The commit in the middle was ammended to have committer date in the\n> past.\n> $ git describe --contains d63972e4e4e7eda0444e56739ad09bfbc476b9bd\n> tag~1\n> \n> but\n> $ git describe --contains 108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3\n> fatal: cannot describe '108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3'\n> \n> I guess this is the same issue reported previously here:\n> http://git.661346.n2.nabble.com/git-describe-contains-fails-on-given-tree-td5448286.html\n\nYes, the \"describe --contains\" algorithm uses timestamps to cut off the\ntraversal, so it can do the wrong thing if there's clock skew. It has a\n\"slop\" margin of one day, but skew larger than that can fool it.\n\n> Can this be fixed somehow or it would lead to other kind of issues?\n\nThe options are basically:\n\n  1. Stop cutting off the traversal based on timestamps. This will make\n     the common case of valid timestamps much slower, though, as it will\n     have to walk all the way to the roots.\n\n  2. Use a different slop mechanism. For example, keep walking up to 5\n     commits past a commit suspected to be past the cutoff. This is\n     relatively easy to do (we do it for \"--since\" checks), and would\n     catch your case above. But of course it does not catch all cases of\n     skew.\n\n  3. Introduce a more trust-worthy mechanism for ordering commits. The\n     timestamp here is really just a proxy for the oft-discussed\n     \"generation number\" of the commit within the graph. We've avoided\n     adding generation numbers because of the storage/complexity issues.\n\n-Peff\n"},{"id":"257003","messageId":"54F71F69.3080500@drmicha.warpmail.net","threadId":"38657","inReplyTo":"20150304105408.GA19693@peff.net","subject":"Re: git describe --contains doesn't work properly for a commit","fromName":"Michael J Gruber","fromEmail":"git@drmicha.warpmail.net","sentAt":"2015-03-04T15:06:17Z","receivedAt":"2015-03-04T15:06:17Z","isPatch":false,"sender":{"key":"git@grubix.eu","avatar":"https://avatars.githubusercontent.com/u/233215?v=4"},"body":"Jeff King venit, vidit, dixit 04.03.2015 11:54:\n> On Thu, Feb 26, 2015 at 03:23:14PM +0100, Michal Hocko wrote:\n> \n>> The commit in the middle was ammended to have committer date in the\n>> past.\n>> $ git describe --contains d63972e4e4e7eda0444e56739ad09bfbc476b9bd\n>> tag~1\n>>\n>> but\n>> $ git describe --contains 108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3\n>> fatal: cannot describe '108a0d5972fd2e5f25b2f38cfd2fee73031ff9d3'\n>>\n>> I guess this is the same issue reported previously here:\n>> http://git.661346.n2.nabble.com/git-describe-contains-fails-on-given-tree-td5448286.html\n> \n> Yes, the \"describe --contains\" algorithm uses timestamps to cut off the\n> traversal, so it can do the wrong thing if there's clock skew. It has a\n> \"slop\" margin of one day, but skew larger than that can fool it.\n> \n>> Can this be fixed somehow or it would lead to other kind of issues?\n> \n> The options are basically:\n> \n>   1. Stop cutting off the traversal based on timestamps. This will make\n>      the common case of valid timestamps much slower, though, as it will\n>      have to walk all the way to the roots.\n> \n>   2. Use a different slop mechanism. For example, keep walking up to 5\n>      commits past a commit suspected to be past the cutoff. This is\n>      relatively easy to do (we do it for \"--since\" checks), and would\n>      catch your case above. But of course it does not catch all cases of\n>      skew.\n> \n>   3. Introduce a more trust-worthy mechanism for ordering commits. The\n>      timestamp here is really just a proxy for the oft-discussed\n>      \"generation number\" of the commit within the graph. We've avoided\n>      adding generation numbers because of the storage/complexity issues.\n\nHmmh.\n\nStorage: one int (or maybe less) per commit doesn't sound too bad. We\ncan probably do without on bare repos by default.\n\nComplexity: Was that due to replace refs? Other than that, it seemed to\nbe simple: max(parent generation numbers)+1.\n\n... or can reachability bitmaps help???\n\nMichael\n"},{"id":"257007","messageId":"20150304180529.GA28074@peff.net","threadId":"38657","inReplyTo":"54F71F69.3080500@drmicha.warpmail.net","subject":"Re: git describe --contains doesn't work properly for a commit","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-04T18:05:29Z","receivedAt":"2015-03-04T18:05:29Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 04, 2015 at 04:06:17PM +0100, Michael J Gruber wrote:\n\n> >   3. Introduce a more trust-worthy mechanism for ordering commits. The\n> >      timestamp here is really just a proxy for the oft-discussed\n> >      \"generation number\" of the commit within the graph. We've avoided\n> >      adding generation numbers because of the storage/complexity issues.\n> \n> Hmmh.\n> \n> Storage: one int (or maybe less) per commit doesn't sound too bad. We\n> can probably do without on bare repos by default.\n> \n> Complexity: Was that due to replace refs? Other than that, it seemed to\n> be simple: max(parent generation numbers)+1.\n\nCalculating them is simple. Caching and storage is the bigger question.\nWhen we do we generate them? Where do we store them? What do we do with\nreplace-refs and grafts?\n\nI think the answers are \"at repack time\", \"in an auxiliary file alongside\nthe pack idx\", and \"we turn it off completely when these features are in\nuse\".\n\nSee:\n\n  http://thread.gmane.org/gmane.comp.version-control.git/214916\n\nfor a sample implementation.\n\n> ... or can reachability bitmaps help???\n\nSometimes. If you are asking about --contains traversals, then bitmaps\ncan let you stop the traversal early. We have some patches that do this\nthat are running in production at GitHub, but they are kind of gnarly.\nOne of my goals is to clean them up and get them upstream.\n\nIt's also part of why I didn't pursue the series above further. Making\n\"--contains\" faster is one goal, but making \"rev-list --objects --all\"\nfaster was more important (since we do it for every fetch). And making\ncommits faster is only half the equation there.\n\n-Peff\n"},{"id":"257015","messageId":"xmqq7fuw8pgq.fsf@gitster.dls.corp.google.com","threadId":"38657","inReplyTo":"20150304180529.GA28074@peff.net","subject":"Re: git describe --contains doesn't work properly for a commit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-04T20:41:57Z","receivedAt":"2015-03-04T20:41:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, Mar 04, 2015 at 04:06:17PM +0100, Michael J Gruber wrote:\n>\n>> Complexity: Was that due to replace refs? Other than that, it seemed to\n>> be simple: max(parent generation numbers)+1.\n>\n> Calculating them is simple. Caching and storage is the bigger question.\n\nYes, also having to handle the ones whose generation numbers haven't\nbeen computed yet adds to the complexity.\n\nThis one, and $gmane/264101, are a few instances of this known issue\nraised here recently.  I have been wondering if we can do something\nalong the following (these are not alternatives) as a cheaper\nworkaround:\n\n (1) Introduce '--skewed-timestamps[=(allow|warn|reject)' to all\n     commands that create new commit objects.  If the committer\n     timestamp being used is older than any of the parent commits,\n     \"warn\" or \"reject\" depending on the setting.\n\n     Make 'reject' the default for commands that are purely local\n     (i.e. recording your own progress by cherry-picking,\n     committing, rebasing, reverting, etc.) and 'warn' the default\n     for commands that merge other peoples' history that you may\n     lack the power to rewind and correct (e.g. 'pull' and 'merge'\n     from remote tracking refs).\n\n (2) Compute a bitmap whose timestamps are suspect when we pack to\n     mark commits.  When revision.c:limit_list() tries to see if\n     there still are interesting commits, an UNINTERESTING commit\n     marked as such shouldn't be counted as \"not interesting because\n     it is old enough\".  Use the same hint in the walker used in\n     \"describe --contains\".\n"},{"id":"257031","messageId":"20150304220553.GA24801@glandium.org","threadId":"38657","inReplyTo":"xmqq7fuw8pgq.fsf@gitster.dls.corp.google.com","subject":"Re: git describe --contains doesn't work properly for a commit","fromName":"Mike Hommey","fromEmail":"mh@glandium.org","sentAt":"2015-03-04T22:05:53Z","receivedAt":"2015-03-04T22:05:53Z","isPatch":false,"sender":{"key":"mh@glandium.org","avatar":"https://avatars.githubusercontent.com/u/1038527?v=4"},"body":"On Wed, Mar 04, 2015 at 12:41:57PM -0800, Junio C Hamano wrote:\n> Jeff King <peff@peff.net> writes:\n> \n> > On Wed, Mar 04, 2015 at 04:06:17PM +0100, Michael J Gruber wrote:\n> >\n> >> Complexity: Was that due to replace refs? Other than that, it seemed to\n> >> be simple: max(parent generation numbers)+1.\n> >\n> > Calculating them is simple. Caching and storage is the bigger question.\n> \n> Yes, also having to handle the ones whose generation numbers haven't\n> been computed yet adds to the complexity.\n> \n> This one, and $gmane/264101, are a few instances of this known issue\n> raised here recently.  I have been wondering if we can do something\n> along the following (these are not alternatives) as a cheaper\n> workaround:\n> \n>  (1) Introduce '--skewed-timestamps[=(allow|warn|reject)' to all\n>      commands that create new commit objects.  If the committer\n>      timestamp being used is older than any of the parent commits,\n>      \"warn\" or \"reject\" depending on the setting.\n> \n>      Make 'reject' the default for commands that are purely local\n>      (i.e. recording your own progress by cherry-picking,\n>      committing, rebasing, reverting, etc.) and 'warn' the default\n>      for commands that merge other peoples' history that you may\n>      lack the power to rewind and correct (e.g. 'pull' and 'merge'\n>      from remote tracking refs).\n\nPlease note that a common cause (for me, at least) of skewed timestamps\nis importing from a foreign VCS.\n\nMike\n"},{"id":"257052","messageId":"20150305051211.GA3344@peff.net","threadId":"38657","inReplyTo":"xmqq7fuw8pgq.fsf@gitster.dls.corp.google.com","subject":"Re: git describe --contains doesn't work properly for a commit","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2015-03-05T05:12:11Z","receivedAt":"2015-03-05T05:12:11Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Mar 04, 2015 at 12:41:57PM -0800, Junio C Hamano wrote:\n\n> > Calculating them is simple. Caching and storage is the bigger question.\n> \n> Yes, also having to handle the ones whose generation numbers haven't\n> been computed yet adds to the complexity.\n\nI'm not sure it's that bad. If you cache generation numbers for all\nknown commits when you repack, then worst case you have to traverse all\ncommits not in the pack.\n\n> This one, and $gmane/264101, are a few instances of this known issue\n> raised here recently.\n\nIf $gmane/264101 is caused by clock skew, I'd find that disturbing.\nThose algorithms are supposed to be \"correct, but slower\" in the face of\nskew, not ever incorrect.\n\n> I have been wondering if we can do something\n> along the following (these are not alternatives) as a cheaper\n> workaround:\n> \n>  (1) Introduce '--skewed-timestamps[=(allow|warn|reject)' to all\n>      commands that create new commit objects.  If the committer\n>      timestamp being used is older than any of the parent commits,\n>      \"warn\" or \"reject\" depending on the setting.\n\nI think this idea has come up before. If it's _your_ timestamp that is\nscrewed up, this detects it, which is good. But if it's somebody else's\ntimestamp that is screwed up, there's often not much you can do. It's\nalready baked into the history.\n\nI don't mind it as an extra layer of protection, I guess. But my\nrecollection of the great skew survey[1] is that most of these problems\ndon't come from actual clock skew, but from software bugs or bogus data\nin imported commits. True skew is generally less than a day, and can be\nhandled with a fixed slop time.\n\n[1] http://article.gmane.org/gmane.comp.version-control.git/159065\n\n>  (2) Compute a bitmap whose timestamps are suspect when we pack to\n>      mark commits.  When revision.c:limit_list() tries to see if\n>      there still are interesting commits, an UNINTERESTING commit\n>      marked as such shouldn't be counted as \"not interesting because\n>      it is old enough\".  Use the same hint in the walker used in\n>      \"describe --contains\".\n\nIf you see mismatched timestamps between a parent and child commit, it's\noften not clear which one is suspicious.  Is the parent skewed to the\nfuture, or is the child skewed to the past? Which one do you mark as\nsuspect?\n\nIMHO, if you are going to go to the trouble to detect and store skew,\nyou should just go to the trouble to calculate and store reliable\ngeneration numbers.\n\n-Peff\n"},{"id":"257054","messageId":"xmqq385k56hj.fsf@gitster.dls.corp.google.com","threadId":"38657","inReplyTo":"20150305051211.GA3344@peff.net","subject":"Re: git describe --contains doesn't work properly for a commit","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2015-03-05T06:00:08Z","receivedAt":"2015-03-05T06:00:08Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> On Wed, Mar 04, 2015 at 12:41:57PM -0800, Junio C Hamano wrote:\n>\n>\n>> This one, and $gmane/264101, are a few instances of this known issue\n>> raised here recently.\n>\n> If $gmane/264101 is caused by clock skew, I'd find that disturbing.\n> Those algorithms are supposed to be \"correct, but slower\" in the face of\n> skew, not ever incorrect.\n\nMy understanding is that the commit painting done by merge-base is\ndesigned to be always correct, but the A..B revision traversal\ndepends on SLOP being big enough.  When the traversal queue is\nfilled with all UNINTERESTING commits, some of which needs to be dug\nto reveal newer commits that are not yet painted as UNINTERESTING in\norder to get the complete picture, the still_interesting() logic\nwill end up stopping prematurely, leaving commits that are actually\nUNINTERESTING in the topological sense unpainted in the resulting\nnewlist that is assigned to revs->commits in limit_list(), yielding\nan incorrect result.\n\n>> > Calculating them is simple. Caching and storage is the bigger question.\n>> \n>> Yes, also having to handle the ones whose generation numbers haven't\n>> been computed yet adds to the complexity.\n>\n> I'm not sure it's that bad. If you cache generation numbers for all\n> known commits when you repack, then worst case you have to traverse all\n> commits not in the pack.\n> ...\n> IMHO, if you are going to go to the trouble to detect and store skew,\n> you should just go to the trouble to calculate and store reliable\n> generation numbers.\n\nI would actually prefer a solution with generation numbers, of\ncourse, because that would give us provably correct result.  If it\ncan be done without too much hassle, I am all for it.  Scrap the\nhalf-baked \"I've been wondering\" compromise ;-)\n\nThanks.\n"}]}