Re: [PATCH] git tag --contains : avoid stack overflow

2014-04-17 Thread Johannes Schindelin
Hi Peff, On Wed, 16 Apr 2014, Jeff King wrote: On Wed, Apr 16, 2014 at 04:15:19PM +0200, Stepan Kasal wrote: From: Jean-Jacques Lafay at Sat, 10 Nov 2012 18:36:10 +0100 In large repos, the recursion implementation of contains(commit, commit_list) may result in a stack overflow.

Re: [PATCH] git tag --contains : avoid stack overflow

2014-04-17 Thread Jeff King
On Thu, Apr 17, 2014 at 07:31:54PM +0200, Johannes Schindelin wrote: bash -c ulimit -s 64 git tag --contains HEAD actual [...] Please see https://github.com/msysgit/git/c63d196 for the fixup, and https://github.com/msysgit/git/compare/tag-contains%5E...tag-contains for the updated

Re: [PATCH] git tag --contains : avoid stack overflow

2014-04-17 Thread Johannes Schindelin
Hi Peff, On Thu, 17 Apr 2014, Jeff King wrote: On Thu, Apr 17, 2014 at 07:31:54PM +0200, Johannes Schindelin wrote: bash -c ulimit -s 64 git tag --contains HEAD actual [...] Please see https://github.com/msysgit/git/c63d196 for the fixup, and

Re: [PATCH] git tag --contains : avoid stack overflow

2014-04-17 Thread Jeff King
On Thu, Apr 17, 2014 at 11:52:56PM +0200, Johannes Schindelin wrote: I tried running the test on my Linux box, but it doesn't fail with the existing recursive code. I cannot recall how I came to choose 64, but I *think* I only tested on Windows, and I *think* I reduced the number of tags

[PATCH] git tag --contains : avoid stack overflow

2014-04-16 Thread Stepan Kasal
From: Jean-Jacques Lafay jeanjacques.la...@gmail.com Date: Sat, 10 Nov 2012 18:36:10 +0100 In large repos, the recursion implementation of contains(commit, commit_list) may result in a stack overflow. Replace the recursion with a loop to fix it. This problem is more apparent on Windows than on

Re: [PATCH] git tag --contains : avoid stack overflow

2014-04-16 Thread Jeff King
On Wed, Apr 16, 2014 at 04:15:19PM +0200, Stepan Kasal wrote: From: Jean-Jacques Lafay jeanjacques.la...@gmail.com Date: Sat, 10 Nov 2012 18:36:10 +0100 In large repos, the recursion implementation of contains(commit, commit_list) may result in a stack overflow. Replace the recursion with

Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-12 Thread Jeff King
On Mon, Nov 12, 2012 at 11:27:14PM +0100, Jean-Jacques Lafay wrote: 2012/11/11 Jeff King p...@peff.net: On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote: Ultimately, I have some ideas for doing this in a breadth-first way, which would make it more naturally iterative. It

Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-12 Thread Johannes Schindelin
Hi Peff, On Mon, 12 Nov 2012, Jeff King wrote: On Mon, Nov 12, 2012 at 11:27:14PM +0100, Jean-Jacques Lafay wrote: 2012/11/11 Jeff King p...@peff.net: On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote: Ultimately, I have some ideas for doing this in a breadth-first way,

Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-12 Thread Jeff King
On Tue, Nov 13, 2012 at 01:16:01AM +, Johannes Schindelin wrote: We can do much better than O(number of commits), though, if we stop traversing down a path when its timestamp shows that it is too old to contain the commits we are searching for. The problem is that the timestamps

Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-12 Thread Johannes Schindelin
Hi Peff, On Mon, 12 Nov 2012, Jeff King wrote: On Tue, Nov 13, 2012 at 01:16:01AM +, Johannes Schindelin wrote: We can do much better than O(number of commits), though, if we stop traversing down a path when its timestamp shows that it is too old to contain the commits we are

Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-12 Thread Jeff King
On Tue, Nov 13, 2012 at 04:01:11AM +, Johannes Schindelin wrote: Note that name-rev will produce wrong answers in the face of clock skew. And I think that you even wrote that code. :) IIRC the cute code to short-circuit using the date is not from me. If it is, I am very ashamed.

Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-12 Thread Junio C Hamano
Jeff King p...@peff.net writes: Yeah. We tolerate a certain amount of skew (24 hours for --name-rev, and 5 broken commits in a row for --since). But the big ones are usually software bugs (the big kernel ones were from broken guilt, I think) or broken imports (when I published a bunch of skew

Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-12 Thread Johannes Schindelin
Hi Peff, On Mon, 12 Nov 2012, Jeff King wrote: On Tue, Nov 13, 2012 at 04:01:11AM +, Johannes Schindelin wrote: Note that name-rev will produce wrong answers in the face of clock skew. And I think that you even wrote that code. :) IIRC the cute code to short-circuit using the

Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-12 Thread Jeff King
On Mon, Nov 12, 2012 at 08:51:37PM -0800, Junio C Hamano wrote: Jeff King p...@peff.net writes: Yeah. We tolerate a certain amount of skew (24 hours for --name-rev, and 5 broken commits in a row for --since). But the big ones are usually software bugs (the big kernel ones were from

Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-11 Thread Jeff King
On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote: However, I couldn't reproduce it on Linux : where the windows implementations crashes at a ~32000 depth (*not* exactly 32768, mind you), on linux it happily went through 10 commits. I didn't take time to look much further, but

Re: [msysGit] Re: [PATCH] git tag --contains : avoid stack overflow

2012-11-11 Thread Johannes Schindelin
Hi, On Sun, 11 Nov 2012, Jeff King wrote: On Sun, Nov 11, 2012 at 05:46:32PM +0100, René Scharfe wrote: However, I couldn't reproduce it on Linux : where the windows implementations crashes at a ~32000 depth (*not* exactly 32768, mind you), on linux it happily went through 10

Re: [msysGit] [PATCH] git tag --contains : avoid stack overflow

2012-11-10 Thread Philip Oakley
From: Jean-Jacques Lafay jeanjacques.la...@gmail.com Sent: Saturday, November 10, 2012 5:36 PM In large repos, the recursion implementation of contains(commit, commit_list) may result in a stack overflow. Replace the recursion with a loop to fix it. Signed-off-by: Jean-Jacques Lafay

Re: [msysGit] [PATCH] git tag --contains : avoid stack overflow

2012-11-10 Thread Pat Thoyts
On 10 November 2012 21:13, Jean-Jacques Lafay jeanjacques.la...@gmail.com wrote: Le samedi 10 novembre 2012 21:00:10 UTC+1, Philip Oakley a écrit : From: Jean-Jacques Lafay jeanjacq...@gmail.com Sent: Saturday, November 10, 2012 5:36 PM In large repos, the recursion implementation of