{"thread":{"id":"32061","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","startedAt":"2012-11-10T19:56:24Z","lastAt":"2012-11-13T06:08:38Z","messageCount":15,"participants":["Philip Oakley","Jean-Jacques Lafay","Pat Thoyts","René Scharfe","Jeff King","Johannes Schindelin","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"202780","messageId":"03ED9D50D1F64467863C051959CFC433@PhilipOakley","threadId":"32061","inReplyTo":"1352568970-4669-1-git-send-email-jeanjacques.lafay@gmail.com","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.org","sentAt":null,"receivedAt":"2012-11-10T19:56:24Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"From: \"Jean-Jacques Lafay\" Sent: Saturday, \nNovember 10, 2012 5:36 PM\n> In large repos, the recursion implementation of contains(commit, \n> commit_list)\n> may result in a stack overflow. Replace the recursion with a loop to \n> fix it.\n>\n> Signed-off-by: Jean-Jacques Lafay \n\nThis is a change to the main git code so it is better to submit it to \nthe main git list at git@vger.kernel.org (plain text, no HTML, first \npost usually has a delay ;-)\n\nIt sounds reasonable but others may have opinions and comments.\n\nHave you actually suffered from the stack overflow issue? You only \nsuggest it as a possibility, rather than a real problem.\n\nPhilip\n\n> ---\n> builtin/tag.c | 83 \n> ++++++++++++++++++++++++++++++++++++++++------------------\n> t/t7004-tag.sh | 21 +++++++++++++++\n> 2 files changed, 78 insertions(+), 26 deletions(-)\n>\n> diff --git a/builtin/tag.c b/builtin/tag.c\n> index 9c3e067..4be67dd 100644\n> --- a/builtin/tag.c\n> +++ b/builtin/tag.c\n> @@ -73,40 +73,71 @@ static int in_commit_list(const struct commit_list \n> *want, struct commit *c)\n> return 0;\n> }\n>\n> -static int contains_recurse(struct commit *candidate,\n> - const struct commit_list *want)\n> -{\n> - struct commit_list *p;\n> -\n> - /* was it previously marked as containing a want commit? */\n> - if (candidate->object.flags & TMP_MARK)\n> - return 1;\n> - /* or marked as not possibly containing a want commit? */\n> - if (candidate->object.flags & UNINTERESTING)\n> - return 0;\n> - /* or are we it? */\n> - if (in_commit_list(want, candidate))\n> - return 1;\n> +struct commit_list_list {\n> + struct commit *item;\n> + struct commit_list *next_item;\n> + struct commit_list_list *next;\n> +};\n>\n> - if (parse_commit(candidate) < 0)\n> - return 0;\n> +static void mark_path(struct commit_list_list *path, int status)\n> +{\n> + struct commit_list_list *temp;\n> + while (path) {\n> + path->item->object.flags |= status;\n> + temp = path;\n> + path = temp->next;\n> + free(temp);\n> + }\n> +}\n>\n> - /* Otherwise recurse and mark ourselves for future traversals. */\n> - for (p = candidate->parents; p; p = p->next) {\n> - if (contains_recurse(p->item, want)) {\n> - candidate->object.flags |= TMP_MARK;\n> +static int contains(struct commit *candidate,\n> + const struct commit_list *want)\n> +{\n> + /* previously implemented with a recursion, but could stack overflow \n> in large repos */\n> + struct commit_list_list *p, *tmp;\n> + p = xmalloc(sizeof(struct commit_list_list));\n> + p->item = candidate;\n> + p->next_item = NULL;\n> + p->next = NULL;\n> +\n> + while (p) {\n> + candidate = p->item;\n> +\n> + /* is it ok : */\n> + /* was it previously marked as containing a want commit? */\n> + /* or are we it? */\n> + if (candidate->object.flags & TMP_MARK || in_commit_list(want, \n> candidate)) {\n> + mark_path(p, TMP_MARK);\n> return 1;\n> }\n> + /* is it not ok : */\n> + /* was it previously marked as not possibly containing a want \n> commit? */\n> + /* do we have parents? */\n> + if (candidate->object.flags & UNINTERESTING || \n> parse_commit(candidate) < 0 || !candidate->parents) {\n> + candidate->object.flags |= UNINTERESTING;\n> + /* then backtrack, marking as UNINTERESTING along the way */\n> + while (p && !p->next_item) {\n> + p->item->object.flags |= UNINTERESTING;\n> + tmp = p;\n> + p = tmp->next;\n> + free(tmp);\n> + }\n> + if (p) {\n> + p->item = p->next_item->item;\n> + p->next_item = p->next_item->next;\n> + }\n> + } else {\n> + /* let's check the parents */\n> + tmp = xmalloc(sizeof(struct commit_list_list));\n> + tmp->item = candidate->parents->item;\n> + tmp->next_item = candidate->parents->next;\n> + tmp->next = p;\n> + p = tmp;\n> + }\n> }\n> - candidate->object.flags |= UNINTERESTING;\n> return 0;\n> }\n>\n> -static int contains(struct commit *candidate, const struct \n> commit_list *want)\n> -{\n> - return contains_recurse(candidate, want);\n> -}\n> -\n> static void show_tag_lines(const unsigned char *sha1, int lines)\n> {\n> int i;\n> diff --git a/t/t7004-tag.sh b/t/t7004-tag.sh\n> index 5189446..196ac54 100755\n> --- a/t/t7004-tag.sh\n> +++ b/t/t7004-tag.sh\n> @@ -1365,4 +1365,25 @@ test_expect_success 'multiple --points-at are \n> OR-ed together' '\n> test_cmp expect actual\n> '\n>\n> +# what about a deep repo ?\n> +\n> +>expect\n> +test_expect_success '--contains works in a deep repo' '\n> + i=1\n> + while test $i -lt 40000\n> + do\n> + echo \"commit refs/heads/master\n> +committer A U Thor $((1000000000 + $i * 100)) \n> +0200\n> +data < +commit #$i\n> +EOF\"\n> + test $i == 1 && echo \"from refs/heads/master^0\"\n> + i=$(($i + 1))\n> + done | git fast-import\n> + git checkout master\n> + git tag far-far-away HEAD^\n> + git tag --contains HEAD >actual &&\n> + test_cmp expect actual\n> +'\n> +\n> test_done\n> -- \n> 1.8.0.msysgit.0.1.geed93bd.dirty\n>\n> -- \n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"202784","messageId":"d9843c09-3ca9-406e-9df8-78603235d985@googlegroups.com","threadId":"32061","inReplyTo":"03ED9D50D1F64467863C051959CFC433@PhilipOakley","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jean-Jacques Lafay","fromEmail":"jeanjacques.lafay@gmail.com","sentAt":"2012-11-10T21:13:53Z","receivedAt":"2012-11-10T21:13:53Z","isPatch":true,"sender":{"key":"jeanjacques.lafay@gmail.com","avatar":null},"body":"Le samedi 10 novembre 2012 21:00:10 UTC+1, Philip Oakley a écrit :\n\n> From: \"Jean-Jacques Lafay\" > Sent: \n> Saturday, \n> November 10, 2012 5:36 PM \n> > In large repos, the recursion implementation of contains(commit, \n> > commit_list) \n> > may result in a stack overflow. Replace the recursion with a loop to \n> > fix it. \n> > \n> > Signed-off-by: Jean-Jacques Lafay > \n>\n> This is a change to the main git code so it is better to submit it to \n> the main git list at g...@vger.kernel.org (plain text, no \n> HTML, first \n> post usually has a delay ;-) \n>\n> It sounds reasonable but others may have opinions and comments. \n>\n> Have you actually suffered from the stack overflow issue? You only \n> suggest it as a possibility, rather than a real problem. \n>\n> Philip \n>\n\nYes, it actually crashed on me, and since the call is made by GitExtension \nwhile browsing the commit history, it was quickly annoying to have windows \npopping a \"git.exe stopped working\" message box at my face every time I \nclicked on a line of the history ;-) (well, you can sort of work around it \nby having the \"file tree\" or \"diff\" tab active)\n\nCoincidentally, as I was having a glance at the recent topics, I saw that \nsomeone else experienced it.\n\nHowever, I couldn't reproduce it on Linux : where the windows \nimplementations crashes at a ~32000 depth (*not* exactly 32768, mind you), \non linux it happily went through 100000 commits. I didn't take time to look \nmuch further, but maybe on my 64 bit Linux VM, the process can afford to \nreserve a much bigger address range for the stack of each thread than the \n1Mb given to 32 bit processes on windows.\n \nJean-Jacques.\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"202785","messageId":"CABNJ2G+hnCgs9u64c83s+2fnVyp584e4PPX7F6BF34T1ieDrhA@mail.gmail.com","threadId":"32061","inReplyTo":"d9843c09-3ca9-406e-9df8-78603235d985@googlegroups.com","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Pat Thoyts","fromEmail":"patthoyts@gmail.com","sentAt":"2012-11-10T21:33:24Z","receivedAt":"2012-11-10T21:33:24Z","isPatch":true,"sender":{"key":"patthoyts@gmail.com","avatar":"https://gravatar.com/avatar/bee887a777c790bd241f398217723fbe4b854428671db83db32216a28654cb25?d=mp&s=160"},"body":"On 10 November 2012 21:13, Jean-Jacques Lafay\n wrote:\n> Le samedi 10 novembre 2012 21:00:10 UTC+1, Philip Oakley a écrit :\n>>\n>> From: \"Jean-Jacques Lafay\" Sent: Saturday,\n>> November 10, 2012 5:36 PM\n>> > In large repos, the recursion implementation of contains(commit,\n>> > commit_list)\n>> > may result in a stack overflow. Replace the recursion with a loop to\n>> > fix it.\n>> >\n>> > Signed-off-by: Jean-Jacques Lafay \n>>\n>> This is a change to the main git code so it is better to submit it to\n>> the main git list at g...@vger.kernel.org (plain text, no HTML, first\n>> post usually has a delay ;-)\n>>\n>> It sounds reasonable but others may have opinions and comments.\n>>\n>> Have you actually suffered from the stack overflow issue? You only\n>> suggest it as a possibility, rather than a real problem.\n>>\n>> Philip\n>\n>\n> Yes, it actually crashed on me, and since the call is made by GitExtension\n> while browsing the commit history, it was quickly annoying to have windows\n> popping a \"git.exe stopped working\" message box at my face every time I\n> clicked on a line of the history ;-) (well, you can sort of work around it\n> by having the \"file tree\" or \"diff\" tab active)\n>\n> Coincidentally, as I was having a glance at the recent topics, I saw that\n> someone else experienced it.\n>\n> However, I couldn't reproduce it on Linux : where the windows\n> implementations crashes at a ~32000 depth (*not* exactly 32768, mind you),\n> on linux it happily went through 100000 commits. I didn't take time to look\n> much further, but maybe on my 64 bit Linux VM, the process can afford to\n> reserve a much bigger address range for the stack of each thread than the\n> 1Mb given to 32 bit processes on windows.\n>\n> Jean-Jacques.\n\nI checked this on msysGit - the test causes a crash on Windows when\nusing the 1.8.0 release and recompiling with this patch applied fixes\nthis. As mentioned, its best to have this reviewed upstream too as its\nlikely that windows just has a smaller stack so causes the crash\nearlier.\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"202874","messageId":"509FD668.20609@lsrfire.ath.cx","threadId":"32061","inReplyTo":"d9843c09-3ca9-406e-9df8-78603235d985@googlegroups.com","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"René Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2012-11-11T16:46:32Z","receivedAt":"2012-11-11T16:46:32Z","isPatch":true,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Am 10.11.2012 22:13, schrieb Jean-Jacques Lafay:\n> Le samedi 10 novembre 2012 21:00:10 UTC+1, Philip Oakley a écrit :\n>\n> From: \"Jean-Jacques Lafay\" >\n> Sent: Saturday,\n> November 10, 2012 5:36 PM\n> > In large repos, the recursion implementation of contains(commit,\n> > commit_list)\n> > may result in a stack overflow. Replace the recursion with a loop to\n> > fix it.\n> >\n> > Signed-off-by: Jean-Jacques Lafay >\n>\n> This is a change to the main git code so it is better to submit it to\n> the main git list at g...@vger.kernel.org (plain text,\n> no HTML, first\n> post usually has a delay ;-)\n>\n> It sounds reasonable but others may have opinions and comments.\n>\n> Have you actually suffered from the stack overflow issue? You only\n> suggest it as a possibility, rather than a real problem.\n>\n> Philip\n>\n>\n> Yes, it actually crashed on me, and since the call is made by\n> GitExtension while browsing the commit history, it was quickly annoying\n> to have windows popping a \"git.exe stopped working\" message box at my\n> face every time I clicked on a line of the history ;-) (well, you can\n> sort of work around it by having the \"file tree\" or \"diff\" tab active)\n>\n> Coincidentally, as I was having a glance at the recent topics, I saw\n> that someone else experienced it.\n>\n> However, I couldn't reproduce it on Linux : where the windows\n> implementations crashes at a ~32000 depth (*not* exactly 32768, mind\n> you), on linux it happily went through 100000 commits. I didn't take\n> time to look much further, but maybe on my 64 bit Linux VM, the process\n> can afford to reserve a much bigger address range for the stack of each\n> thread than the 1Mb given to 32 bit processes on windows.\n> Jean-Jacques.\n\nI can reproduce it on Linux (Debian testing amd64) with ulimit -s 1000 \nto reduce the stack size from its default value of 8MB.\n\nAfter reverting ffc4b8012d9a4f92ef238ff72c0d15e9e1b402ed (tag: speed up \n--contains calculation) the test passes even with the smaller stack, but \nit makes \"git tag --contains\" take thrice the time as before.\n\nRené\n"},{"id":"202877","messageId":"20121111165431.GA25884@sigill.intra.peff.net","threadId":"32061","inReplyTo":"509FD668.20609@lsrfire.ath.cx","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-11T16:54:31Z","receivedAt":"2012-11-11T16:54:31Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote:\n\n> >However, I couldn't reproduce it on Linux : where the windows\n> >implementations crashes at a ~32000 depth (*not* exactly 32768, mind\n> >you), on linux it happily went through 100000 commits. I didn't take\n> >time to look much further, but maybe on my 64 bit Linux VM, the process\n> >can afford to reserve a much bigger address range for the stack of each\n> >thread than the 1Mb given to 32 bit processes on windows.\n> >Jean-Jacques.\n> \n> I can reproduce it on Linux (Debian testing amd64) with ulimit -s\n> 1000 to reduce the stack size from its default value of 8MB.\n> \n> After reverting ffc4b8012d9a4f92ef238ff72c0d15e9e1b402ed (tag: speed\n> up --contains calculation) the test passes even with the smaller\n> stack, but it makes \"git tag --contains\" take thrice the time as\n> before.\n\nRight, I am not too surprised. That function replaced the original\nalgorithm with a much faster depth-first recursive one. I haven't looked\nclosely yet at Jean-Jacques' iterative adaptation, but that direction\nseems like a good fix for now.\n\nUltimately, I have some ideas for doing this in a breadth-first way,\nwhich would make it more naturally iterative. It would involve having N\nbits of storage per commit to check N tags, but it would mean that we\ncould get accurate answers in the face of clock skew (like the\nmerge-base calculation, it would merely get slower in the face of skew).\n\nBut since I haven't worked on that at all, fixing the depth-first\nalgorithm to be iterative makes sense to me.\n\n-Peff\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"202930","messageId":"alpine.DEB.1.00.1211112308220.5793@bonsai2","threadId":"32061","inReplyTo":"20121111165431.GA25884@sigill.intra.peff.net","subject":"Re: Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2012-11-11T23:10:04Z","receivedAt":"2012-11-11T23:10:04Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sun, 11 Nov 2012, Jeff King wrote:\n\n> On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote:\n> \n> > >However, I couldn't reproduce it on Linux : where the windows\n> > >implementations crashes at a ~32000 depth (*not* exactly 32768, mind\n> > >you), on linux it happily went through 100000 commits. I didn't take\n> > >time to look much further, but maybe on my 64 bit Linux VM, the\n> > >process can afford to reserve a much bigger address range for the\n> > >stack of each thread than the 1Mb given to 32 bit processes on\n> > >windows. Jean-Jacques.\n> > \n> > I can reproduce it on Linux (Debian testing amd64) with ulimit -s 1000\n> > to reduce the stack size from its default value of 8MB.\n> > \n> > After reverting ffc4b8012d9a4f92ef238ff72c0d15e9e1b402ed (tag: speed\n> > up --contains calculation) the test passes even with the smaller\n> > stack, but it makes \"git tag --contains\" take thrice the time as\n> > before.\n> \n> Right, I am not too surprised. That function replaced the original\n> algorithm with a much faster depth-first recursive one. I haven't looked\n> closely yet at Jean-Jacques' iterative adaptation, but that direction\n> seems like a good fix for now.\n> \n> Ultimately, I have some ideas for doing this in a breadth-first way,\n> which would make it more naturally iterative. It would involve having N\n> bits of storage per commit to check N tags, but it would mean that we\n> could get accurate answers in the face of clock skew (like the\n> merge-base calculation, it would merely get slower in the face of skew).\n> \n> But since I haven't worked on that at all, fixing the depth-first\n> algorithm to be iterative makes sense to me.\n\nHave you tried the latest tag-contains branch of\ngit://github.com/msysgit/git/? It contains a couple of brush-ups and a\nre-write of the recursion (which I hope is right, I had only time to work\non it during an unwanted layover at O'Hare). The SHA-1 is\nfc4f42787a0dd0022d202627681362081a66ef70.\n\nCiao,\nJohannes\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"203010","messageId":"CA+TMuX2p4ck0qXijH+OOcBoveBC42U8PqnXdisau57RXwt1isg@mail.gmail.com","threadId":"32061","inReplyTo":"20121111165431.GA25884@sigill.intra.peff.net","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jean-Jacques Lafay","fromEmail":"jeanjacques.lafay@gmail.com","sentAt":"2012-11-12T22:27:14Z","receivedAt":"2012-11-12T22:27:14Z","isPatch":true,"sender":{"key":"jeanjacques.lafay@gmail.com","avatar":null},"body":"2012/11/11 Jeff King :\n> On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote:\n>\n> Ultimately, I have some ideas for doing this in a breadth-first way,\n> which would make it more naturally iterative. It would involve having N\n> bits of storage per commit to check N tags, but it would mean that we\n> could get accurate answers in the face of clock skew (like the\n> merge-base calculation, it would merely get slower in the face of skew).\n\nI guess the optimal algorithm may also depend on the commit graph\ngeneral shape, but intuitively, I'd say that the critical factor is\nthe number and distribution of tags. As soon as you have a significant\nnumber of tags (let's say 1% of the commits are tagged, evenly\ndistributed), you'll quickly end up with every commit marked as\ncontaining or not the target commit, so that each additional tag check\nis cheap.\n\nThis suggests a complexity of O(number of commits) more often then\nnot, however you choose to traverse the graph.\n\nAt least on my almost-real-life repo*, with ~140,000 commits and\n~2,000 tags, tag --contains takes a few seconds, of course more than\nthe worst-case test on a 40,000 commit / 1 tag repo, but still in the\nsame order of magnitude.\n\n* : meaning we're in the process of migrating from clearcase (deep\nsighs allowed !), and for now I kept almost everything in a single git\nrepo, which may not be the eventual choice\n\nJean-Jacques.\n"},{"id":"203017","messageId":"20121112231453.GA21679@sigill.intra.peff.net","threadId":"32061","inReplyTo":"CA+TMuX2p4ck0qXijH+OOcBoveBC42U8PqnXdisau57RXwt1isg@mail.gmail.com","subject":"Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-12T23:14:53Z","receivedAt":"2012-11-12T23:14:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 12, 2012 at 11:27:14PM +0100, Jean-Jacques Lafay wrote:\n\n> 2012/11/11 Jeff King :\n> > On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote:\n> >\n> > Ultimately, I have some ideas for doing this in a breadth-first way,\n> > which would make it more naturally iterative. It would involve having N\n> > bits of storage per commit to check N tags, but it would mean that we\n> > could get accurate answers in the face of clock skew (like the\n> > merge-base calculation, it would merely get slower in the face of skew).\n> \n> I guess the optimal algorithm may also depend on the commit graph\n> general shape, but intuitively, I'd say that the critical factor is\n> the number and distribution of tags. As soon as you have a significant\n> number of tags (let's say 1% of the commits are tagged, evenly\n> distributed), you'll quickly end up with every commit marked as\n> containing or not the target commit, so that each additional tag check\n> is cheap.\n> \n> This suggests a complexity of O(number of commits) more often then\n> not, however you choose to traverse the graph.\n\nWe can do much better than O(number of commits), though, if we stop\ntraversing down a path when its timestamp shows that it is too old to\ncontain the commits we are searching for. The problem is that the\ntimestamps cannot always be trusted, because they are generated on\nmachines with wrong clocks, or by buggy software. This could be solved\nby calculating and caching a \"generation\" number, but last time it was\ndiscussed there was a lot of arguing and nothing got done.\n\nAnother approach, used by the merge-base calculation, is to treat\nparents in a breadth-first way, but sort them by timestamp, and walk\nbackwards to find the merge-base (and if you get to a merge-base, you\ncan stop). In that case, bad timestamps may cause you to look at extra\ncommits (because you process a commit prematurely and end up going\ndeeper than the merge base), but it can never give you a wrong answer.\n\nThinking on it more, though, the merge-base style of computation would\nmean you always have to walk backwards to the oldest tag. Which is in\nthe same order of magnitude as the number of commits, assuming you have\ntags near the start of history. So I think we will always want to keep a\ncutoff, anyway, and there is not much point in switching off of a\ndepth-first approach (but of course it does make sense to use iteration\ninstead of recursion to do so).\n\n> At least on my almost-real-life repo*, with ~140,000 commits and\n> ~2,000 tags, tag --contains takes a few seconds, of course more than\n> the worst-case test on a 40,000 commit / 1 tag repo, but still in the\n> same order of magnitude.\n\nTry \"git rev-list --count --all\" to get a sense of how long O(# of\ncommits) takes. Before the depth-first implementation, \"tag --contains\"\nwas O(commits * tags) in the worst case. With depth first, it's\nO(commits), and then with the timestamp cutoff, it's really O(commits\nsince needle), where \"needle\" is the oldest thing you're looking for.\nHere are those numbers on linux-2.6 (with linux-stable tags):\n\n [to get a sense of the repo size]\n $ git for-each-ref refs/tags | wc -l\n 909\n $ git rev-list --count --all\n 363413\n\n [this is O(commits)]\n $ time git rev-list --count --all\n real 0m4.034s\n user 0m3.960s\n sys 0m0.056s\n\n [before depth-first, ffc4b80^; you can see that it is much worse than\n O(commits), though not as bad as the worst case (because finding the\n merge bases for recent tags is not O(commits)]\n $ time git tag --contains HEAD~200\n real 0m42.838s\n user 0m42.527s\n sys 0m0.156s\n\n [after depth-first, ffc4b80; you can see that this is O(commits),\n because we will go depth-first down to the roots, but do only a\n single traversal]\n $ time git tag --contains HEAD~200\n real 0m3.939s\n user 0m3.784s\n sys 0m0.140s\n\n [with my generation patches; much faster]\n $ time git tag --contains HEAD~200\n real 0m0.037s\n user 0m0.020s\n sys 0m0.012s\n\nI was thinking we had merged the timestamp cutoff (which has the same\nperformance characteristics as generations, just with the skew issue) to\nmaster, but it looks like we didn't.\n\n-Peff\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"203035","messageId":"alpine.DEB.1.00.1211130114180.13573@bonsai2","threadId":"32061","inReplyTo":"20121112231453.GA21679@sigill.intra.peff.net","subject":"Re: Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2012-11-13T01:16:01Z","receivedAt":"2012-11-13T01:16:01Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Mon, 12 Nov 2012, Jeff King wrote:\n\n> On Mon, Nov 12, 2012 at 11:27:14PM +0100, Jean-Jacques Lafay wrote:\n> \n> > 2012/11/11 Jeff King :\n> > > On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote:\n> > >\n> > > Ultimately, I have some ideas for doing this in a breadth-first way,\n> > > which would make it more naturally iterative. It would involve\n> > > having N bits of storage per commit to check N tags, but it would\n> > > mean that we could get accurate answers in the face of clock skew\n> > > (like the merge-base calculation, it would merely get slower in the\n> > > face of skew).\n> > \n> > I guess the optimal algorithm may also depend on the commit graph\n> > general shape, but intuitively, I'd say that the critical factor is\n> > the number and distribution of tags. As soon as you have a significant\n> > number of tags (let's say 1% of the commits are tagged, evenly\n> > distributed), you'll quickly end up with every commit marked as\n> > containing or not the target commit, so that each additional tag check\n> > is cheap.\n> > \n> > This suggests a complexity of O(number of commits) more often then\n> > not, however you choose to traverse the graph.\n> \n> We can do much better than O(number of commits), though, if we stop\n> traversing down a path when its timestamp shows that it is too old to\n> contain the commits we are searching for. The problem is that the\n> timestamps cannot always be trusted, because they are generated on\n> machines with wrong clocks, or by buggy software. This could be solved\n> by calculating and caching a \"generation\" number, but last time it was\n> discussed there was a lot of arguing and nothing got done.\n\nSadly, not only machines with skewed clocks, but in particular buggy\n3rd-party SCMs make this more than just problematic. In a git-svn clone\nthat was used as base for heavy Git development, I encountered quite a lot\nof Jan 1, 1970 commits.\n\nIt just cannot be helped, we must distrust timestamps completely.\n\nCiao,\nDscho\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"203039","messageId":"20121113034605.GB8387@sigill.intra.peff.net","threadId":"32061","inReplyTo":"alpine.DEB.1.00.1211130114180.13573@bonsai2","subject":"Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-13T03:46:05Z","receivedAt":"2012-11-13T03:46:05Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 13, 2012 at 01:16:01AM +0000, Johannes Schindelin wrote:\n\n> > We can do much better than O(number of commits), though, if we stop\n> > traversing down a path when its timestamp shows that it is too old to\n> > contain the commits we are searching for. The problem is that the\n> > timestamps cannot always be trusted, because they are generated on\n> > machines with wrong clocks, or by buggy software. This could be solved\n> > by calculating and caching a \"generation\" number, but last time it was\n> > discussed there was a lot of arguing and nothing got done.\n> \n> Sadly, not only machines with skewed clocks, but in particular buggy\n> 3rd-party SCMs make this more than just problematic. In a git-svn clone\n> that was used as base for heavy Git development, I encountered quite a lot\n> of Jan 1, 1970 commits.\n\nYeah. We tolerate a certain amount of skew (24 hours for --name-rev, and\n5 broken commits in a row for --since). But the big ones are usually\nsoftware bugs (the big kernel ones were from broken \"guilt\", I think) or\nbroken imports (when I published a bunch of skew statistics last year,\nthe interesting ones were all imports; I don't know if they were\nsoftware bugs, or just garbage in, garbage out).\n\n> It just cannot be helped, we must distrust timestamps completely.\n\nNote that name-rev will produce wrong answers in the face of clock skew.\nAnd I think that you even wrote that code. :)\n\n-Peff\n"},{"id":"203043","messageId":"alpine.DEB.1.00.1211130400030.13573@bonsai2","threadId":"32061","inReplyTo":"20121113034605.GB8387@sigill.intra.peff.net","subject":"Re: Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2012-11-13T04:01:11Z","receivedAt":"2012-11-13T04:01:11Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Mon, 12 Nov 2012, Jeff King wrote:\n\n> On Tue, Nov 13, 2012 at 01:16:01AM +0000, Johannes Schindelin wrote:\n> \n> > > We can do much better than O(number of commits), though, if we stop\n> > > traversing down a path when its timestamp shows that it is too old to\n> > > contain the commits we are searching for. The problem is that the\n> > > timestamps cannot always be trusted, because they are generated on\n> > > machines with wrong clocks, or by buggy software. This could be solved\n> > > by calculating and caching a \"generation\" number, but last time it was\n> > > discussed there was a lot of arguing and nothing got done.\n> > \n> > Sadly, not only machines with skewed clocks, but in particular buggy\n> > 3rd-party SCMs make this more than just problematic. In a git-svn clone\n> > that was used as base for heavy Git development, I encountered quite a lot\n> > of Jan 1, 1970 commits.\n> \n> Yeah. We tolerate a certain amount of skew (24 hours for --name-rev, and\n> 5 broken commits in a row for --since). But the big ones are usually\n> software bugs (the big kernel ones were from broken \"guilt\", I think) or\n> broken imports (when I published a bunch of skew statistics last year,\n> the interesting ones were all imports; I don't know if they were\n> software bugs, or just garbage in, garbage out).\n> \n> > It just cannot be helped, we must distrust timestamps completely.\n> \n> Note that name-rev will produce wrong answers in the face of clock skew.\n> And I think that you even wrote that code. :)\n\nIIRC the cute code to short-circuit using the date is not from me. If it\nis, I am very ashamed.\n\nCiao,\nJohannes\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"203044","messageId":"20121113040541.GA9439@sigill.intra.peff.net","threadId":"32061","inReplyTo":"alpine.DEB.1.00.1211130400030.13573@bonsai2","subject":"Re: Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-13T04:05:41Z","receivedAt":"2012-11-13T04:05:41Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Nov 13, 2012 at 04:01:11AM +0000, Johannes Schindelin wrote:\n\n> > Note that name-rev will produce wrong answers in the face of clock skew.\n> > And I think that you even wrote that code. :)\n> \n> IIRC the cute code to short-circuit using the date is not from me. If it\n> is, I am very ashamed.\n\nSorry, but it was:\n\n $ git blame -L'/commit->date < cutoff/',+1 builtin/name-rev.c\n bd321bcc name-rev.c (Johannes Schindelin 2005-10-26 15:10:20 +0200 32)\n if (commit->date < cutoff)\n\nBut it is never too late to fix it. :)\n\n-Peff\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"203045","messageId":"7vwqxqf6li.fsf@alter.siamese.dyndns.org","threadId":"32061","inReplyTo":"20121113034605.GB8387@sigill.intra.peff.net","subject":"Re: Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-11-13T04:51:37Z","receivedAt":"2012-11-13T04:51:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> Yeah. We tolerate a certain amount of skew (24 hours for --name-rev, and\n> 5 broken commits in a row for --since). But the big ones are usually\n> software bugs (the big kernel ones were from broken \"guilt\", I think) or\n> broken imports (when I published a bunch of skew statistics last year,\n> the interesting ones were all imports; I don't know if they were\n> software bugs, or just garbage in, garbage out).\n\nI was hoping that 2e6bdd3 (test-generation: compute generation\nnumbers and clock skews, 2012-09-04) may be a good first step to\ncome up with a practical and cheap solution on top of it.\n\nThe traversal can be fooled by clock skews when it sees a commit\nthat has a timestamp that is older than it should, causing it to\ngive up, incorrectly thinking that there won't be newer commits that\nit is interested in behind the problematic commit.\n\nThe logic implemented by the change is to identify these problematic\ncommits, and we could record these commits with the value of the\ntimestamps they should have had (e.g. the timestamp of the newest\nancestor for each of these commits) in a notes tree. Then the\ntraversal logic (commit-list-insert-by-date) could be updated use\nthat \"corrected\" timestamp instead not to be fooled by the clock\nskew.\n\nSuch a notes tree can be built once and updated by only \"appending\",\nas a commit will never acquire more ancestors in its parents chain\nonce it is made.\n\nIs it too simplistic, or too costly? In git.git we have three such\ncommits whose timestamp need to be corrected, while in the Linux\nkernel there were 2.2k skewed commits when I counted them a few\nmonths ago.\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"203046","messageId":"alpine.DEB.1.00.1211130452200.13573@bonsai2","threadId":"32061","inReplyTo":"20121113040541.GA9439@sigill.intra.peff.net","subject":"Re: Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2012-11-13T04:52:48Z","receivedAt":"2012-11-13T04:52:48Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Mon, 12 Nov 2012, Jeff King wrote:\n\n> On Tue, Nov 13, 2012 at 04:01:11AM +0000, Johannes Schindelin wrote:\n> \n> > > Note that name-rev will produce wrong answers in the face of clock skew.\n> > > And I think that you even wrote that code. :)\n> > \n> > IIRC the cute code to short-circuit using the date is not from me. If it\n> > is, I am very ashamed.\n> \n> Sorry, but it was:\n> \n> $ git blame -L'/commit->date < cutoff/',+1 builtin/name-rev.c\n> bd321bcc name-rev.c (Johannes Schindelin 2005-10-26 15:10:20 +0200 32)\n> if (commit->date < cutoff)\n> \n> But it is never too late to fix it. :)\n\nI will now go and find a hole to hide in. Or alternatively finally go to\nsleep.\n\nCiao,\nJohannes\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"},{"id":"203053","messageId":"20121113060838.GD10995@sigill.intra.peff.net","threadId":"32061","inReplyTo":"7vwqxqf6li.fsf@alter.siamese.dyndns.org","subject":"Re: Re: [PATCH] git tag --contains : avoid stack overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-11-13T06:08:38Z","receivedAt":"2012-11-13T06:08:38Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, Nov 12, 2012 at 08:51:37PM -0800, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > Yeah. We tolerate a certain amount of skew (24 hours for --name-rev, and\n> > 5 broken commits in a row for --since). But the big ones are usually\n> > software bugs (the big kernel ones were from broken \"guilt\", I think) or\n> > broken imports (when I published a bunch of skew statistics last year,\n> > the interesting ones were all imports; I don't know if they were\n> > software bugs, or just garbage in, garbage out).\n> \n> I was hoping that 2e6bdd3 (test-generation: compute generation\n> numbers and clock skews, 2012-09-04) may be a good first step to\n> come up with a practical and cheap solution on top of it.\n>\n> The traversal can be fooled by clock skews when it sees a commit\n> that has a timestamp that is older than it should, causing it to\n> give up, incorrectly thinking that there won't be newer commits that\n> it is interested in behind the problematic commit.\n\nI wrote a similar skew-finding tool last year, though some of the\nnumbers it came up with were different (I remember having many fewer\nskewed commits in the kernel repo).\n\nOne problem is that it identifies commits which behave badly with\ncertain algorithms, but it does not identify commits which are wrong.\nIf I skew backwards, it will find my commit. But if I skew forwards, it\nwill label my children as wrong.\n\n> The logic implemented by the change is to identify these problematic\n> commits, and we could record these commits with the value of the\n> timestamps they should have had (e.g. the timestamp of the newest\n> ancestor for each of these commits) in a notes tree. Then the\n> traversal logic (commit-list-insert-by-date) could be updated use\n> that \"corrected\" timestamp instead not to be fooled by the clock\n> skew.\n> \n> Such a notes tree can be built once and updated by only \"appending\",\n> as a commit will never acquire more ancestors in its parents chain\n> once it is made.\n> \n> Is it too simplistic, or too costly? In git.git we have three such\n> commits whose timestamp need to be corrected, while in the Linux\n> kernel there were 2.2k skewed commits when I counted them a few\n> months ago.\n\nThis came up in the big generations discussion last summer, and I think\nI even implemented a proof of concept. I couldn't find the actual code,\nthough but only that I got \"pleasing performance results using a notes\ntree to store a list of commits with bogus timestamps\":\n\n http://article.gmane.org/gmane.comp.version-control.git/161101\n\nIt is a little wasteful in space if you have a lot of skewed commits\n(the notes tree stores a 160-bit hash pointing to a blob object storing\na 32-bit integer).\n\nMy personal preference at this point would be:\n\n 1. introduce an auxiliary metadata file that would live alongside the\n pack index and contain generation numbers\n\n 2. generate the metadata file during pack indexing.\n\n 3. If we have a generation metadata file, but a particular object is\n not in it, compute the generation; this should be quick because we\n will hit a file with a stored generation eventually\n\n 4. If we do not have any generation metadata files, or if grafts or\n replace objects are in use, do not use cutoffs in algorithms. Be\n safe but slow.\n\nOn the other hand, just switching to doing a single traversal instead of\none merge-base computation per tag already got rid of the really awful\nperformance cases. Nobody has complained since that went in, so maybe\nnobody cares about shaving a few seconds per operation down to a few\ntens of milliseconds. The real win was shaving tens of seconds down to a\nfew seconds.\n\n-Peff\n\n-- \n*** Please reply-to-all at all times ***\n*** (do not pretend to know who is subscribed and who is not) ***\n*** Please avoid top-posting. ***\nThe msysGit Wiki is here: https://github.com/msysgit/msysgit/wiki - Github accounts are free.\n\nYou received this message because you are subscribed to the Google\nGroups \"msysGit\" group.\nTo post to this group, send email to msysgit@googlegroups.com\nTo unsubscribe from this group, send email to\nmsysgit+unsubscribe@googlegroups.com\nFor more options, and view previous threads, visit this group at\nhttp://groups.google.com/group/msysgit?hl=en_US?hl=en\n"}]}