Re: [PATCH 1/2] git-commit: Disallow unchanged tree in non-merge mode

On Thu, 13 Sep 2007, Linus Torvalds wrote:

Ok, I'm downloading those tar-balls to reproduce and hopefully see what's 
going on, but I'm not going to be able to get at it today.

Ok, I'm seeing it, and there are serious problems in the diffcore-rename 
code.

The problems include things like actual overflow in 31 bits (a signed 
integer) from the multiplication of "num_create * num_src".

But you'll almost certainly never even get there, because you'd long since 
have given up on the O(n^2) behaviour of the "cheap tests", that aren't 
really cheap enough, if only because even just comparing the 20-byte SHA1 
hashes will basically take forever since they will always miss in the 
cache for lots of names.

So yes, we really *have* to have a rename limit, even if it's only to 
avoid the technical bug of overflowing the multiplication.

Testing this actually showed another bug too: "git diff" would actually 
never call "diff_setup_done() at all, if "diffopt.output_format" had been 
set explicitly to something. So doing a "git diff --stat" would totally 
ignore all the sanity checks (and, what caused me to find it, the 
initialization of "diffopt.rename_limit") that diff_setup_done() is 
supposed to do!

So I'm going to send out two patches - one to fix the "diff_setup_done()" 
bug, and one that replaces the default rename_limit with something saner. 
Both seem to be real bugs.

			Linus

For some inexplicable reason, "git diff" would call "diff_setup_done()" 
iff we hadn't given an explicit output format.

That makes no sense, since much of what diff_setup_done() does is exactly 
about checking the output format!

This just moves the call to "diff_setup_done()" out of the conditional, 
and to where we've actually done all of the diffopt changes.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---
 builtin-diff.c |    7 +++----
 1 files changed, 3 insertions(+), 4 deletions(-)

diff --git a/builtin-diff.c b/builtin-diff.c
index f77352b..cb4743b 100644
--- a/builtin-diff.c
+++ b/builtin-diff.c

@@ -252,13 +252,12 @@ int cmd_diff(int argc, const char **argv, const char *prefix)
 		argc = 0;
 	else
 		argc = setup_revisions(argc, argv, &rev, NULL);
-	if (!rev.diffopt.output_format) {
+	if (!rev.diffopt.output_format)
 		rev.diffopt.output_format = DIFF_FORMAT_PATCH;
-		if (diff_setup_done(&rev.diffopt) < 0)
-			die("diff_setup_done failed");
-	}
 	rev.diffopt.allow_external = 1;
 	rev.diffopt.recursive = 1;
+	if (diff_setup_done(&rev.diffopt) < 0)
+		die("diff_setup_done failed");
 
 	/* If the user asked for our exit code then don't start a
 	 * pager or we would end up reporting its exit code instead.

This adds more proper rename detection limits. Instead of just checking 
the limit against the number of potential rename destinations, we verify 
that the rename matrix (which is what really matters) doesn't grow 
ridiculously large, and we also make sure that we don't overflow when 
doing the matrix size calculation.

This also changes the default limits from unlimited, to a rename matrix 
that is limited to 100 entries on a side. You can raise it with the config 
entry, or by using the "-l<n>" command line flag, but at least the default 
is now a sane number that avoids spending lots of time (and memory) in 
situations that likely don't merit it.

The choice of default value is of course very debatable. Limiting the 
rename matrix to a 100x100 size will mean that even if you have just one 
obvious rename, but you also create (or delete) 10,000 files, the rename 
matrix will be so big that we disable the heuristics. Sounds reasonable to 
me, but let's see if people hit this (and, perhaps more importantly, 
actually *care*) in real life.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

Due to the overflow issue (and yes, Dmitry's test-case actually triggered 
an overflow even on 64-bit machines, because the math was done on "int" 
types), I really think this was a real bug.

Now, whether this is necessarily the right way to fix it, I dunno, but it 
also *does* fix the old broken limit handling that was based just on the 
number of target files, and didn't take the number of potential source 
files into account.

But the fix to that logic also means that the meaning of "-l<n>" changes 
subtly. For the better, I think, but changes nonetheless.

I'd also like to apologize to the change in wt-status.c, but that code 
doesn't use the regular diffopt setup logic, so it really is a special 
case and needs to be handled as such. Do we want to teach "git runstatus" 
to actually honor command line flags for diff generation etc? That's a 
separate question, this patch just makes it use the same rename default as 
the normal diffs now do.

 diff.c            |    2 +-
 diffcore-rename.c |   19 +++++++++++++++++--
 wt-status.c       |    1 +
 3 files changed, 19 insertions(+), 3 deletions(-)

diff --git a/diff.c b/diff.c
index 1aca5df..0ee9ea1 100644
--- a/diff.c
+++ b/diff.c

@@ -17,7 +17,7 @@
 #endif
 
 static int diff_detect_rename_default;
-static int diff_rename_limit_default = -1;
+static int diff_rename_limit_default = 100;
 static int diff_use_color_default;
 int diff_auto_refresh_index = 1;
 

diff --git a/diffcore-rename.c b/diffcore-rename.c
index 6bde439..41b35c3 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c

@@ -298,10 +298,25 @@ void diffcore_rename(struct diff_options *options)
 		else if (detect_rename == DIFF_DETECT_COPY)
 			register_rename_src(p->one, 1, p->score);
 	}
-	if (rename_dst_nr == 0 || rename_src_nr == 0 ||
-	    (0 < rename_limit && rename_limit < rename_dst_nr))
+	if (rename_dst_nr == 0 || rename_src_nr == 0)
 		goto cleanup; /* nothing to do */
 
+	/*
+	 * This basically does a test for the rename matrix not
+	 * growing larger than a "rename_limit" square matrix, ie:
+	 *
+	 *    rename_dst_nr * rename_src_nr > rename_limit * rename_limit
+	 *
+	 * but handles the potential overflow case specially (and we
+	 * assume at least 32-bit integers)
+	 */
+	if (rename_limit <= 0 || rename_limit > 32767)
+		rename_limit = 32767;
+	if (rename_dst_nr > rename_limit && rename_src_nr > rename_limit)
+		goto cleanup;
+	if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)
+		goto cleanup;
+
 	/* We really want to cull the candidates list early
 	 * with cheap tests in order to avoid doing deltas.
 	 * The first round matches up the up-to-date entries,

diff --git a/wt-status.c b/wt-status.c
index 5205420..10ce6ee 100644
--- a/wt-status.c
+++ b/wt-status.c

@@ -227,6 +227,7 @@ static void wt_status_print_updated(struct wt_status *s)
 	rev.diffopt.format_callback = wt_status_print_updated_cb;
 	rev.diffopt.format_callback_data = s;
 	rev.diffopt.detect_rename = 1;
+	rev.diffopt.rename_limit = 100;
 	wt_read_cache(s);
 	run_diff_index(&rev, 1);
 }

On Fri, 14 Sep 2007, Linus Torvalds wrote:

... and we also make sure that we don't overflow when doing the matrix 
size calculation.

Side note: by "make sure", I don't really mean a total guarantee.

We could be even more careful here. In particular:

 - we later do end up allocating the matrix with 

	sizeof(*mx) * num_create * num_src

   and I didn't actually fix the overflow that is possible due to the
   "sizeof(*mx)" multiplication.

 - even after we've checked that not *both* of the source and destination 
   counts are larger than the rename_limit, we could still overflow the 
   multiplication in just the limit check.

.. but with the rename_limit being set to 100, in practice neither of 
these are really even close to realistic (ie you'd need to have less than 
100 new files, and deleted over twenty million files to overflow, or vice 
versa).

So with a rename_limit of 100, it's all good (I'm pretty sure you'd have 
*other* issues long before you'd hit the integer overflows on renames ;)

But if somebody sets the rename_limit to something bigger, it gets 
increasingly easier to screw it up.

If somebody wants to be *really* careful, they'd need to do something like

	unsigned long max;

	/* This isn't going to overflow, since we limited 'rename_limit' */
	max = rename_limit * rename_limit;

	/*
	 * But we should also check that multiplying by "sizeof(*mx)" 
	 * won't make it overlof either..
	 */
	while ((sizeof(*mx) * max) / sizeof(*mx) != max)
		max >>= 1;

	/*
	 * And then avoid multiplying "rename_dst_nr" and "rename_src_nr"
	 * together by turning it into a division instead
	 */
	if (max / rename_dst_nr > rename_src_nr)
		goto cleanup;

but the patch I sent out was the "obvious" first one that at least avoided 
the overflow for the triggerable case that Dmitry had, and as per above 
likely in all reasonable cases...

			Linus

On Fri, 14 Sep 2007, Linus Torvalds wrote:

but the patch I sent out was the "obvious" first one that at least avoided 
the overflow for the triggerable case that Dmitry had, and as per above 
likely in all reasonable cases...

Final note (I promise): the patch I sent out took "git runstatus" times on 
the workload I replicated from Dmitry down from "so long you'd ^C it" to 
about two seconds..

So I wanted to point out that this was not just the correctness issue of 
the overflow, but that the rename limiting really does need to be done for 
purely practical time reasons - doing the math in 64 bits would have 
avoided the overflow, but wouldn't have avoided the real reason for not 
wanting to do these kinds of things in the first place!

		Linus