[RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Ævar Arnfjörð Bjarmason]

The difference between "master" and "git-for-windows/main" is large
enough that comparing the two will segfault on my system. This is
because the range-diff code does some expensive calculations and will
overflow the "int" type.

Fixing this wasn't trivial, our st_*() macros only work for unsigned
types, but as signed overflow is undefined in C detecting it is a lot
more painful. The range-diff code needs to store -1 in various places
(not inherently, but changing that looked a lot more painful).

Furthermore even if the range-diff.c and linear-assignment.c code were
fixed we'd still segfault due to the used string-list.c code using an
"int" type. Or rather, we tracked its "unsigned int" with an "int". If
we used "unsigned" we won't segfault on master..git-for-windows/main,
but we would soon enough on slightly larger divergent history.

This series changes the relevant APIs to use size_t where possible,
but as noted we need to use a signed type for range-diff.c. That's now
intmax_t.

We detect signed overflow first 8/10 with a GCC and Clang-specific
__builtin*() function, and then in the subsequent commit portably by
importing intprops.h from Gnulib.

Perhaps there's an easier way to do this, but this works for me, and
using the portable intprops.h (see its source for all the hard-won
lessons encdoded therein) seems like a good way forward. It *is*
slightly slower than our current unsigned-only detection, but as
discussed in 09/10 we should probably just switch to it anyway. This
series does not make that switch.

We still have various st_*() calls in the codebase where we use signed
types, presumably this is as broken as the not-really-working
detection discussed in 02/10, but I didn't looki into those in any
detail.

This is an RFC because there's some rather painful merge conflicts
in-flight due to the changeover from "unsigned int nr" to "size_t nr"
in the string-list.h API. There's also a CI failure on 32 bit linux
due to a format in 03/10, but it's an easily fixable bug.

And more generally it's an RFC perhaps this direction is a good one
for fixing that and any similar segfauls we have, and maybe it
isn't. I'm not all that sure about it, but this seems to work, and
certainly beats segfaulting...

Ævar Arnfjörð Bjarmason (10):
  string-list API: change "nr" and "alloc" to "size_t"
  range-diff.c: don't use st_mult() for signed "int"
  range-diff.c: use "size_t" to refer to "struct string_list"'s "nr"
  range-diff: zero out elements in "cost" first
  linear-assignment.c: split up compute_assignment() function
  linear-assignment.c: take "size_t", not "int" for *_count
  linear-assignment.c: convert a macro to a "static inline" function
  linear-assignment.c: detect signed add/mul on GCC and Clang
  linear-assignment.c: add and use intprops.h from Gnulib
  linear-assignment.c: use "intmax_t" instead of "int"

 builtin/receive-pack.c       |   6 +-
 builtin/shortlog.c           |   8 +-
 bundle.c                     |   4 +-
 commit-graph.c               |   4 +-
 compat/gnulib/.gitattributes |   1 +
 compat/gnulib/intprops.h     | 637 +++++++++++++++++++++++++++++++++++
 linear-assignment.c          | 149 +++++---
 linear-assignment.h          |   9 +-
 mailmap.c                    |   4 +-
 merge-ort.c                  |   2 +-
 range-diff.c                 |  32 +-
 string-list.h                |   2 +-
 t/helper/test-run-command.c  |   4 +-
 wt-status.c                  |   8 +-
 14 files changed, 781 insertions(+), 89 deletions(-)
 create mode 100644 compat/gnulib/.gitattributes
 create mode 100644 compat/gnulib/intprops.h

-- 
2.34.1.930.g0f9292b224d

[RFC PATCH 01/10] string-list API: change "nr" and "alloc" to "size_t"

[Ævar Arnfjörð Bjarmason]

As with the recent change to the "struct strvec" let's change "struct
string_list"'s "alloc" and "nr" to be a "size_t" as well. This will be
used to fix an overflow in range-diff.c. See 8d133a4653a (strvec: use
size_t to store nr and alloc, 2021-09-11) for the recent change to
"struct strvec".

As with the "struct strvec" change I think it would make sense to go
through the users of the current "unsigned int" field and change
anyone copying it to an "int" or "unsigned int" to "size_t", but as
seen in [1] others disagree, so let's only change the things the
compiler complains about here.

1. https://lore.kernel.org/git/87mtog4pai.fsf@evledraar.gmail.com/

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 builtin/receive-pack.c      | 6 +++---
 builtin/shortlog.c          | 8 ++++----
 bundle.c                    | 4 ++--
 commit-graph.c              | 4 ++--
 mailmap.c                   | 4 ++--
 merge-ort.c                 | 2 +-
 string-list.h               | 2 +-
 t/helper/test-run-command.c | 4 ++--
 wt-status.c                 | 8 ++++----
 9 files changed, 21 insertions(+), 21 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 49b846d9605..4c681a64784 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -827,12 +827,12 @@ static int run_and_feed_hook(const char *hook_name, feed_fn feed,
 	proc.trace2_hook_name = hook_name;
 
 	if (feed_state->push_options) {
-		int i;
+		size_t i;
 		for (i = 0; i < feed_state->push_options->nr; i++)
 			strvec_pushf(&proc.env_array,
-				     "GIT_PUSH_OPTION_%d=%s", i,
+				     "GIT_PUSH_OPTION_%"PRIuMAX"=%s", i,
 				     feed_state->push_options->items[i].string);
-		strvec_pushf(&proc.env_array, "GIT_PUSH_OPTION_COUNT=%d",
+		strvec_pushf(&proc.env_array, "GIT_PUSH_OPTION_COUNT=%"PRIuMAX"",
 			     feed_state->push_options->nr);
 	} else
 		strvec_pushf(&proc.env_array, "GIT_PUSH_OPTION_COUNT");
diff --git a/builtin/shortlog.c b/builtin/shortlog.c
index e7f7af5de3f..32c457956c7 100644
--- a/builtin/shortlog.c
+++ b/builtin/shortlog.c
@@ -434,7 +434,7 @@ static void add_wrapped_shortlog_msg(struct strbuf *sb, const char *s,
 
 void shortlog_output(struct shortlog *log)
 {
-	int i, j;
+	size_t i, j;
 	struct strbuf sb = STRBUF_INIT;
 
 	if (log->sort_by_number)
@@ -447,10 +447,10 @@ void shortlog_output(struct shortlog *log)
 				(int)UTIL_TO_INT(item), item->string);
 		} else {
 			struct string_list *onelines = item->util;
-			fprintf(log->file, "%s (%d):\n",
+			fprintf(log->file, "%s (%"PRIuMAX"):\n",
 				item->string, onelines->nr);
-			for (j = onelines->nr - 1; j >= 0; j--) {
-				const char *msg = onelines->items[j].string;
+			for (j = onelines->nr; j >= 1; j--) {
+				const char *msg = onelines->items[j - 1].string;
 
 				if (log->wrap_lines) {
 					strbuf_reset(&sb);
diff --git a/bundle.c b/bundle.c
index a0bb687b0f4..54dff6d9960 100644
--- a/bundle.c
+++ b/bundle.c
@@ -255,7 +255,7 @@ int verify_bundle(struct repository *r,
 
 		r = &header->references;
 		printf_ln(Q_("The bundle contains this ref:",
-			     "The bundle contains these %d refs:",
+			     "The bundle contains these %"PRIuMAX" refs:",
 			     r->nr),
 			  r->nr);
 		list_refs(r, 0, NULL);
@@ -264,7 +264,7 @@ int verify_bundle(struct repository *r,
 			printf_ln(_("The bundle records a complete history."));
 		} else {
 			printf_ln(Q_("The bundle requires this ref:",
-				     "The bundle requires these %d refs:",
+				     "The bundle requires these %"PRIuMAX" refs:",
 				     r->nr),
 				  r->nr);
 			list_refs(r, 0, NULL);
diff --git a/commit-graph.c b/commit-graph.c
index 2706683acfe..88a7621f2f7 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -1687,8 +1687,8 @@ static int fill_oids_from_packs(struct write_commit_graph_context *ctx,
 	dirlen = packname.len;
 	if (ctx->report_progress) {
 		strbuf_addf(&progress_title,
-			    Q_("Finding commits for commit graph in %d pack",
-			       "Finding commits for commit graph in %d packs",
+			    Q_("Finding commits for commit graph in %"PRIuMAX" pack",
+			       "Finding commits for commit graph in %"PRIuMAX" packs",
 			       pack_indexes->nr),
 			    pack_indexes->nr);
 		ctx->progress = start_delayed_progress(progress_title.buf, 0);
diff --git a/mailmap.c b/mailmap.c
index 40ce152024d..9ce15a9e2fd 100644
--- a/mailmap.c
+++ b/mailmap.c
@@ -43,7 +43,7 @@ static void free_mailmap_info(void *p, const char *s)
 static void free_mailmap_entry(void *p, const char *s)
 {
 	struct mailmap_entry *me = (struct mailmap_entry *)p;
-	debug_mm("mailmap: removing entries for <%s>, with %d sub-entries\n",
+	debug_mm("mailmap: removing entries for <%s>, with %"PRIuMAX" sub-entries\n",
 		 s, me->namemap.nr);
 	debug_mm("mailmap: - simple: '%s' <%s>\n",
 		 debug_str(me->name), debug_str(me->email));
@@ -250,7 +250,7 @@ int read_mailmap(struct string_list *map)
 
 void clear_mailmap(struct string_list *map)
 {
-	debug_mm("mailmap: clearing %d entries...\n", map->nr);
+	debug_mm("mailmap: clearing %"PRIuMAX" entries...\n", map->nr);
 	map->strdup_strings = 1;
 	string_list_clear_func(map, free_mailmap_entry);
 	debug_mm("mailmap: cleared\n");
diff --git a/merge-ort.c b/merge-ort.c
index 0342f104836..28a7cffdb96 100644
--- a/merge-ort.c
+++ b/merge-ort.c
@@ -4004,7 +4004,7 @@ static void process_entries(struct merge_options *opt,
 	trace2_region_enter("merge", "process_entries cleanup", opt->repo);
 	if (dir_metadata.offsets.nr != 1 ||
 	    (uintptr_t)dir_metadata.offsets.items[0].util != 0) {
-		printf("dir_metadata.offsets.nr = %d (should be 1)\n",
+		printf("dir_metadata.offsets.nr = %"PRIuMAX" (should be 1)\n",
 		       dir_metadata.offsets.nr);
 		printf("dir_metadata.offsets.items[0].util = %u (should be 0)\n",
 		       (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);
diff --git a/string-list.h b/string-list.h
index 267d6e5769d..ab331643685 100644
--- a/string-list.h
+++ b/string-list.h
@@ -86,7 +86,7 @@ typedef int (*compare_strings_fn)(const char *, const char *);
  */
 struct string_list {
 	struct string_list_item *items;
-	unsigned int nr, alloc;
+	size_t nr, alloc;
 	unsigned int strdup_strings:1;
 	compare_strings_fn cmp; /* NULL uses strcmp() */
 };
diff --git a/t/helper/test-run-command.c b/t/helper/test-run-command.c
index 3c4fb862234..8e932700201 100644
--- a/t/helper/test-run-command.c
+++ b/t/helper/test-run-command.c
@@ -180,7 +180,7 @@ static int testsuite(int argc, const char **argv)
 	if (max_jobs > suite.tests.nr)
 		max_jobs = suite.tests.nr;
 
-	fprintf(stderr, "Running %d tests (%d at a time)\n",
+	fprintf(stderr, "Running %"PRIuMAX" tests (%d at a time)\n",
 		suite.tests.nr, max_jobs);
 
 	ret = run_processes_parallel(max_jobs, next_test, test_failed,
@@ -188,7 +188,7 @@ static int testsuite(int argc, const char **argv)
 
 	if (suite.failed.nr > 0) {
 		ret = 1;
-		fprintf(stderr, "%d tests failed:\n\n", suite.failed.nr);
+		fprintf(stderr, "%"PRIuMAX" tests failed:\n\n", suite.failed.nr);
 		for (i = 0; i < suite.failed.nr; i++)
 			fprintf(stderr, "\t%s\n", suite.failed.items[i].string);
 	}
diff --git a/wt-status.c b/wt-status.c
index 5d215f4e4f1..79b83caa0f3 100644
--- a/wt-status.c
+++ b/wt-status.c
@@ -1368,8 +1368,8 @@ static void show_rebase_information(struct wt_status *s,
 			status_printf_ln(s, color, _("No commands done."));
 		else {
 			status_printf_ln(s, color,
-				Q_("Last command done (%d command done):",
-					"Last commands done (%d commands done):",
+				Q_("Last command done (%"PRIuMAX" command done):",
+					"Last commands done (%"PRIuMAX" commands done):",
 					have_done.nr),
 				have_done.nr);
 			for (i = (have_done.nr > nr_lines_to_show)
@@ -1387,8 +1387,8 @@ static void show_rebase_information(struct wt_status *s,
 					 _("No commands remaining."));
 		else {
 			status_printf_ln(s, color,
-				Q_("Next command to do (%d remaining command):",
-					"Next commands to do (%d remaining commands):",
+				Q_("Next command to do (%"PRIuMAX" remaining command):",
+					"Next commands to do (%"PRIuMAX" remaining commands):",
 					yet_to_do.nr),
 				yet_to_do.nr);
 			for (i = 0; i < nr_lines_to_show && i < yet_to_do.nr; i++)
-- 
2.34.1.930.g0f9292b224d

[RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Ævar Arnfjörð Bjarmason]

As documented in 320d0b493a2 (add helpers for detecting size_t
overflow, 2016-02-19) the arguments to st_mult() and st_add() "must be
unsigned". This code added in d9c66f0b5bf (range-diff: first
rudimentary implementation, 2018-08-13) operates on signed int.

In subsequent commits further overflows resulting in segfaults will be
fixed in this code, but let's start by removing this supposed guard
that does nothing except give us a false sense of
security. E.g. providing an "n" of INT_MAX here will result in "1" on
my system, causing us to write into memory.

There are other such issues left in the codebase, e.g. the code in
"builtin/clean.c" changed in 50a6c8efa2b (use st_add and st_mult for
allocation size computation, 2016-02-22). But let's focus on
range-diff.c for now.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 range-diff.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/range-diff.c b/range-diff.c
index cac89a2f4f2..170e8623313 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -312,7 +312,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 	int *cost, c, *a2b, *b2a;
 	int i, j;
 
-	ALLOC_ARRAY(cost, st_mult(n, n));
+	ALLOC_ARRAY(cost, n * n);
 	ALLOC_ARRAY(a2b, n);
 	ALLOC_ARRAY(b2a, n);
 
-- 
2.34.1.930.g0f9292b224d

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Jeff King]

On Thu, Dec 09, 2021 at 08:19:19PM +0100, Ævar Arnfjörð Bjarmason wrote:

> As documented in 320d0b493a2 (add helpers for detecting size_t
> overflow, 2016-02-19) the arguments to st_mult() and st_add() "must be
> unsigned".

This isn't correct. The comment that says "must be unsigned" is for
unsigned_mult_overflows(). Which indeed would not work correctly for a
signed type. But st_add() is a separate function (and not a macro)
because that means its arguments will always be promoted or converted
into a size_t. And so no matter what you pass it, it will always itself
pass a size_t into unsigned_mult_overflows().

> In subsequent commits further overflows resulting in segfaults will be
> fixed in this code, but let's start by removing this supposed guard
> that does nothing except give us a false sense of
> security. E.g. providing an "n" of INT_MAX here will result in "1" on
> my system, causing us to write into memory.

This guard doesn't do nothing. Your patch here:

> @@ -312,7 +312,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
>  	int *cost, c, *a2b, *b2a;
>  	int i, j;
>  
> -	ALLOC_ARRAY(cost, st_mult(n, n));
> +	ALLOC_ARRAY(cost, n * n);
>  	ALLOC_ARRAY(a2b, n);
>  	ALLOC_ARRAY(b2a, n);

makes things strictly worse, because that "n * n" may overflow and cause
us to under-allocate the array. You can see it in isolation with some
extra code like this:

diff --git a/git.c b/git.c
index 5ff21be21f..63349e4b79 100644
--- a/git.c
+++ b/git.c
@@ -850,11 +850,23 @@ static int run_argv(int *argcp, const char ***argv)
 	return done_alias;
 }
 
+static void foo(void)
+{
+	int n = 2 << 16;
+
+	printf("n = %d\n", n);
+	printf("raw mult = %"PRIuMAX"\n", (uintmax_t)(n * n));
+	printf("st_mult = %"PRIuMAX"\n", (uintmax_t)st_mult(n, n));
+	exit(0);
+}
+
 int cmd_main(int argc, const char **argv)
 {
 	const char *cmd;
 	int done_help = 0;
 
+	foo();
+
 	cmd = argv[0];
 	if (!cmd)
 		cmd = "git-help";

With st_mult, we get the correct answer of 16GB. Without it, we end up
with 0!

Back to the original code, if you generate a test setup like this:

diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
index e30bc48a29..f552d3086e 100755
--- a/t/t3206-range-diff.sh
+++ b/t/t3206-range-diff.sh
@@ -772,4 +772,11 @@ test_expect_success '--left-only/--right-only' '
 	test_cmp expect actual
 '
 
+test_expect_success 'giant case' '
+	test_commit base &&
+	test_commit_bulk --ref=refs/heads/v1 --message="v1 commit %s" 32768 &&
+	test_commit_bulk --ref=refs/heads/v2 --message="v2 commit %s" 32768 &&
+	git range-diff base v1 v2
+'
+
 test_done

Then we'd allocate a 0-length array for "cost" and segfault as soon as
we try to put anything in it. You can confirm this by applying your
patch, running under gdb, and stopping at the xmalloc() call inside
get_correspondences(). With st_mult(), then we come up with the correct
value of 16GB (or complain about overflow on a 32-bit system).

So st_add() is working as advertised here; it's goal is just to make
sure we never under-allocate. You are right, though, that the code after
that in get_correspondences() has trouble because of the signedness. If
the code used an "unsigned int", it would still be _wrong_. But when it
overflowed, it would always come up with a value under 4GB. So it might
produce a wrong answer, but it couldn't possibly point outside the
bounds of the array and cause a security problem.

But because it's a signed int, we overflow to a negative value and try
to look at memory far before the start of the array. So I can see how it
is tempting to argue that this st_mult() isn't really helping since we
segfault anyway. But I'd disagree. By correctly computing the value of
16GB instead of "0", we know that the ALLOC_ARRAY() line is doing the
right thing. And it may choose not to continue if it can't allocate
16GB. That may happen because you don't have the RAM, but also because
of GIT_ALLOC_LIMIT.

So if you set GIT_ALLOC_LIMIT=4g, for example, you are immune to the bug
here. We'd refuse the allocation and die there, which protects
downstream code from trying to fill in the array with bogus arithmetic.

Dropping the st_mult() does nothing to fix the actual problem (which is
that this function should use a more appropriate type), but introduces
new failure modes.

-Peff

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Ævar Arnfjörð Bjarmason]

On Thu, Dec 09 2021, Jeff King wrote:

> On Thu, Dec 09, 2021 at 08:19:19PM +0100, Ævar Arnfjörð Bjarmason wrote:
>
>> As documented in 320d0b493a2 (add helpers for detecting size_t
>> overflow, 2016-02-19) the arguments to st_mult() and st_add() "must be
>> unsigned".
>
> This isn't correct. The comment that says "must be unsigned" is for
> unsigned_mult_overflows(). Which indeed would not work correctly for a
> signed type. But st_add() is a separate function (and not a macro)
> because that means its arguments will always be promoted or converted
> into a size_t. And so no matter what you pass it, it will always itself
> pass a size_t into unsigned_mult_overflows().
>
>> In subsequent commits further overflows resulting in segfaults will be
>> fixed in this code, but let's start by removing this supposed guard
>> that does nothing except give us a false sense of
>> security. E.g. providing an "n" of INT_MAX here will result in "1" on
>> my system, causing us to write into memory.
>
> This guard doesn't do nothing. Your patch here:
>
>> @@ -312,7 +312,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
>>  	int *cost, c, *a2b, *b2a;
>>  	int i, j;
>>  
>> -	ALLOC_ARRAY(cost, st_mult(n, n));
>> +	ALLOC_ARRAY(cost, n * n);
>>  	ALLOC_ARRAY(a2b, n);
>>  	ALLOC_ARRAY(b2a, n);
>
> makes things strictly worse, because that "n * n" may overflow and cause
> us to under-allocate the array. You can see it in isolation with some
> extra code like this:
>
> diff --git a/git.c b/git.c
> index 5ff21be21f..63349e4b79 100644
> --- a/git.c
> +++ b/git.c
> @@ -850,11 +850,23 @@ static int run_argv(int *argcp, const char ***argv)
>  	return done_alias;
>  }
>  
> +static void foo(void)
> +{
> +	int n = 2 << 16;
> +
> +	printf("n = %d\n", n);
> +	printf("raw mult = %"PRIuMAX"\n", (uintmax_t)(n * n));
> +	printf("st_mult = %"PRIuMAX"\n", (uintmax_t)st_mult(n, n));
> +	exit(0);
> +}
> +
>  int cmd_main(int argc, const char **argv)
>  {
>  	const char *cmd;
>  	int done_help = 0;
>  
> +	foo();
> +
>  	cmd = argv[0];
>  	if (!cmd)
>  		cmd = "git-help";
>
> With st_mult, we get the correct answer of 16GB. Without it, we end up
> with 0!
>
> Back to the original code, if you generate a test setup like this:
>
> diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh
> index e30bc48a29..f552d3086e 100755
> --- a/t/t3206-range-diff.sh
> +++ b/t/t3206-range-diff.sh
> @@ -772,4 +772,11 @@ test_expect_success '--left-only/--right-only' '
>  	test_cmp expect actual
>  '
>  
> +test_expect_success 'giant case' '
> +	test_commit base &&
> +	test_commit_bulk --ref=refs/heads/v1 --message="v1 commit %s" 32768 &&
> +	test_commit_bulk --ref=refs/heads/v2 --message="v2 commit %s" 32768 &&
> +	git range-diff base v1 v2
> +'
> +
>  test_done
>
> Then we'd allocate a 0-length array for "cost" and segfault as soon as
> we try to put anything in it. You can confirm this by applying your
> patch, running under gdb, and stopping at the xmalloc() call inside
> get_correspondences(). With st_mult(), then we come up with the correct
> value of 16GB (or complain about overflow on a 32-bit system).
>
> So st_add() is working as advertised here; it's goal is just to make
> sure we never under-allocate. You are right, though, that the code after
> that in get_correspondences() has trouble because of the signedness. If
> the code used an "unsigned int", it would still be _wrong_. But when it
> overflowed, it would always come up with a value under 4GB. So it might
> produce a wrong answer, but it couldn't possibly point outside the
> bounds of the array and cause a security problem.
>
> But because it's a signed int, we overflow to a negative value and try
> to look at memory far before the start of the array. So I can see how it
> is tempting to argue that this st_mult() isn't really helping since we
> segfault anyway. But I'd disagree. By correctly computing the value of
> 16GB instead of "0", we know that the ALLOC_ARRAY() line is doing the
> right thing. And it may choose not to continue if it can't allocate
> 16GB. That may happen because you don't have the RAM, but also because
> of GIT_ALLOC_LIMIT.
>
> So if you set GIT_ALLOC_LIMIT=4g, for example, you are immune to the bug
> here. We'd refuse the allocation and die there, which protects
> downstream code from trying to fill in the array with bogus arithmetic.
>
> Dropping the st_mult() does nothing to fix the actual problem (which is
> that this function should use a more appropriate type), but introduces
> new failure modes.

Yes you're entirely right. I had some stupid blinders on while writing
this. FWIW I think I was experimenting with some local macros and
conflated a testing of the overflow of n*n in gdb with the caste'd
version, which you rightly point out here won't have the overflow issue
at all. Sorry.

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Jeff King]

On Fri, Dec 10, 2021 at 11:22:59AM +0100, Ævar Arnfjörð Bjarmason wrote:

> > Dropping the st_mult() does nothing to fix the actual problem (which is
> > that this function should use a more appropriate type), but introduces
> > new failure modes.
> 
> Yes you're entirely right. I had some stupid blinders on while writing
> this. FWIW I think I was experimenting with some local macros and
> conflated a testing of the overflow of n*n in gdb with the caste'd
> version, which you rightly point out here won't have the overflow issue
> at all. Sorry.

I'm not sure if this is helpful or not, but this is the minimal fix I
came up with that runs the testcase I showed earlier. It's basically
just swapping out "int" for "ssize_t" for any variables we use to index
the arrays (though note a few are themselves held in arrays, and we have
to cross some function boundaries).

I won't be surprised if it doesn't hit all cases, or if it even hits a
few it doesn't need to (e.g., should "phase" be dragged along with "i"
and "j" in the first hunk?). I mostly did guess-and-check on the
test-case, fixing whatever segfaulted and then running again until it
worked. I didn't even really read the code very carefully.

I think you _did_ do more of that careful reading, and broke down the
refactorings into separate patches in your series. Which is good. So I
think what we'd want is to pick out those parts of your series that end
up switching the variable type. My goal in sharing this here is just to
show that the end result of the fix can (and IMHO should) be around this
same order of magnitude.

---
diff --git a/linear-assignment.c b/linear-assignment.c
index ecffc09be6..3efa30c50b 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -13,11 +13,11 @@
  * i is `cost[j + column_count * i].
  */
 void compute_assignment(int column_count, int row_count, int *cost,
-			int *column2row, int *row2column)
+			ssize_t *column2row, ssize_t *row2column)
 {
 	int *v, *d;
 	int *free_row, free_count = 0, saved_free_count, *pred, *col;
-	int i, j, phase;
+	ssize_t i, j, phase;
 
 	if (column_count < 2) {
 		memset(column2row, 0, sizeof(int) * column_count);
@@ -31,7 +31,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
 
 	/* column reduction */
 	for (j = column_count - 1; j >= 0; j--) {
-		int i1 = 0;
+		ssize_t i1 = 0;
 
 		for (i = 1; i < row_count; i++)
 			if (COST(j, i1) > COST(j, i))
@@ -51,7 +51,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
 	/* reduction transfer */
 	ALLOC_ARRAY(free_row, row_count);
 	for (i = 0; i < row_count; i++) {
-		int j1 = row2column[i];
+		ssize_t j1 = row2column[i];
 		if (j1 == -1)
 			free_row[free_count++] = i;
 		else if (j1 < -1)
@@ -74,13 +74,13 @@ void compute_assignment(int column_count, int row_count, int *cost,
 
 	/* augmenting row reduction */
 	for (phase = 0; phase < 2; phase++) {
-		int k = 0;
+		ssize_t k = 0;
 
 		saved_free_count = free_count;
 		free_count = 0;
 		while (k < saved_free_count) {
 			int u1, u2;
-			int j1 = 0, j2, i0;
+			ssize_t j1 = 0, j2, i0;
 
 			i = free_row[k++];
 			u1 = COST(j1, i) - v[j1];
@@ -130,7 +130,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
 	ALLOC_ARRAY(pred, column_count);
 	ALLOC_ARRAY(col, column_count);
 	for (free_count = 0; free_count < saved_free_count; free_count++) {
-		int i1 = free_row[free_count], low = 0, up = 0, last, k;
+		ssize_t i1 = free_row[free_count], low = 0, up = 0, last, k;
 		int min, c, u1;
 
 		for (j = 0; j < column_count; j++) {
@@ -192,7 +192,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
 		/* augmentation */
 		do {
 			if (j < 0)
-				BUG("negative j: %d", j);
+				BUG("negative j: %"PRIdMAX, (intmax_t)j);
 			i = pred[j];
 			column2row[j] = i;
 			SWAP(j, row2column[i]);
diff --git a/linear-assignment.h b/linear-assignment.h
index 1dfea76629..7005521d61 100644
--- a/linear-assignment.h
+++ b/linear-assignment.h
@@ -14,7 +14,7 @@
  * row_count).
  */
 void compute_assignment(int column_count, int row_count, int *cost,
-			int *column2row, int *row2column);
+			ssize_t *column2row, ssize_t *row2column);
 
 /* The maximal cost in the cost matrix (to prevent integer overflows). */
 #define COST_MAX (1<<16)
diff --git a/range-diff.c b/range-diff.c
index cac89a2f4f..f1e1e27bf9 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -308,9 +308,10 @@ static int diffsize(const char *a, const char *b)
 static void get_correspondences(struct string_list *a, struct string_list *b,
 				int creation_factor)
 {
-	int n = a->nr + b->nr;
-	int *cost, c, *a2b, *b2a;
-	int i, j;
+	size_t n = a->nr + b->nr;
+	int *cost, c;
+	ssize_t *a2b, *b2a;
+	size_t i, j;
 
 	ALLOC_ARRAY(cost, st_mult(n, n));
 	ALLOC_ARRAY(a2b, n);

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Ævar Arnfjörð Bjarmason]

On Fri, Dec 10 2021, Jeff King wrote:

> On Fri, Dec 10, 2021 at 11:22:59AM +0100, Ævar Arnfjörð Bjarmason wrote:
>
>> > Dropping the st_mult() does nothing to fix the actual problem (which is
>> > that this function should use a more appropriate type), but introduces
>> > new failure modes.
>> 
>> Yes you're entirely right. I had some stupid blinders on while writing
>> this. FWIW I think I was experimenting with some local macros and
>> conflated a testing of the overflow of n*n in gdb with the caste'd
>> version, which you rightly point out here won't have the overflow issue
>> at all. Sorry.
>
> I'm not sure if this is helpful or not, but this is the minimal fix I
> came up with that runs the testcase I showed earlier. It's basically
> just swapping out "int" for "ssize_t" for any variables we use to index
> the arrays (though note a few are themselves held in arrays, and we have
> to cross some function boundaries).
>
> I won't be surprised if it doesn't hit all cases, or if it even hits a
> few it doesn't need to (e.g., should "phase" be dragged along with "i"
> and "j" in the first hunk?). I mostly did guess-and-check on the
> test-case, fixing whatever segfaulted and then running again until it
> worked. I didn't even really read the code very carefully.
>
> I think you _did_ do more of that careful reading, and broke down the
> refactorings into separate patches in your series. Which is good. So I
> think what we'd want is to pick out those parts of your series that end
> up switching the variable type. My goal in sharing this here is just to
> show that the end result of the fix can (and IMHO should) be around this
> same order of magnitude.
>
> [...]
>  void compute_assignment(int column_count, int row_count, int *cost,
> -			int *column2row, int *row2column);
> +			ssize_t *column2row, ssize_t *row2column);
>  
>  /* The maximal cost in the cost matrix (to prevent integer overflows). */
>  #define COST_MAX (1<<16)
> diff --git a/range-diff.c b/range-diff.c
> index cac89a2f4f..f1e1e27bf9 100644
> --- a/range-diff.c
> +++ b/range-diff.c
> @@ -308,9 +308,10 @@ static int diffsize(const char *a, const char *b)
>  static void get_correspondences(struct string_list *a, struct string_list *b,
>  				int creation_factor)
>  {
> -	int n = a->nr + b->nr;
> -	int *cost, c, *a2b, *b2a;
> -	int i, j;
> +	size_t n = a->nr + b->nr;
> +	int *cost, c;
> +	ssize_t *a2b, *b2a;
> +	size_t i, j;
>  
>  	ALLOC_ARRAY(cost, st_mult(n, n));
>  	ALLOC_ARRAY(a2b, n);

I think I was just chasing butterflies making this intmax_t at all. I
just submitted a v2, and explained that case in a bit more detail in
https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com

I *think* it fixes all the cases we plausible run into, i.e. storing the
"cost" in an "int" was enough, we just needed a size_t as an offset. It
passes the regression test you noted[3].

The first thing I tried when hacking on this some months ago (I picked
these patches up again after running into the segfault again) was this
s/int/ssize_t/ change.

I don't think using ssize_t like that is portable, and that we'd need
something like intmax_t if we needed this in another context.

Firstly it's not standard C, it's just in POSIX, intmax_t is standard C
as of C99, which and we have in-tree code that already depends on it
(and uintmax_t).

But more importantly it's not "as big as size_t, just signed" in
POSIX. size_t is "no greater than the width of type long"[1] and
LONG_MAX is at least 2^31-1 [2].

Whereas ssize_t is not a "signed size_t", but a type that stores
-1..SSIZE_MAX, and SSIZE_MAX has a minimum value of 2^15-1. I.e. I think
on that basis some implemenations would make it the same as a "short
int" under the hood.

On my linux system it's just mapped to the longest available signed
integer, but that doesn't seem to be a portable assumption.

1. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_types.h.html
2. https://pubs.opengroup.org/onlinepubs/009696899/basedefs/limits.h.html

3. B.t.w. a thing I ended up ejecting out of this was that I made a
   "test_commit_bulkier" which is N times faster than "test_commit_bulk",
   it just makes the same commit N times with the printf-repeating feature
   and feeds it to fast-import, but the test took so long in any case that
   I couldn't find a plausible way to get it in-tree).

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Phillip Wood]

Hi Ævar

On 10/12/2021 12:31, Ævar Arnfjörð Bjarmason wrote:
> 
> [...] 
> I think I was just chasing butterflies making this intmax_t at all. I
> just submitted a v2, and explained that case in a bit more detail in
> https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com
> 
> I *think* it fixes all the cases we plausible run into, i.e. storing the
> "cost" in an "int" was enough, we just needed a size_t as an offset. It
> passes the regression test you noted[3].
> 
> The first thing I tried when hacking on this some months ago (I picked
> these patches up again after running into the segfault again) was this
> s/int/ssize_t/ change.
> 
> I don't think using ssize_t like that is portable, and that we'd need
> something like intmax_t if we needed this in another context.
 >
> Firstly it's not standard C, it's just in POSIX, intmax_t is standard C
> as of C99, which and we have in-tree code that already depends on it
> (and uintmax_t).

I'm not objecting to using intmax_t particularly for code that needs to 
store negative values other than -1 but we're already using ssize_t in a 
lot of places so I don't think we need to worry about it not being 
supported.

> But more importantly it's not "as big as size_t, just signed" in
> POSIX. size_t is "no greater than the width of type long"[1]

The full text is

     The implementation shall support one or more programming
     environments in which the widths of blksize_t, pid_t, size_t,
     ssize_t, and suseconds_t are no greater than the width of type
     long. The names of these programming environments can be obtained
     using the confstr() function or the getconf utility.

so "no greater than the width of type long" applies to ssize_t as well 
as size_t.

> and
> LONG_MAX is at least 2^31-1 [2].
> 
> Whereas ssize_t is not a "signed size_t", but a type that stores
> -1..SSIZE_MAX, and SSIZE_MAX has a minimum value of 2^15-1. I.e. I think
> on that basis some implemenations would make it the same as a "short
> int" under the hood.

The minimum value of SIZE_MAX is 2^16-1[1], I'm not sure you can read 
much into the width of ssize_t from the minimum value of SSIZE_MAX. If 
you think about where ssize_t is used as the return value of read() and 
write() that take a size_t as the number of bytes to read/write then it 
would be very odd if ssize_t was a different width to size_t.

Best Wishes

Phillip

[1] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/stdint.h.html

> On my linux system it's just mapped to the longest available signed
> integer, but that doesn't seem to be a portable assumption.
> 
> 1. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_types.h.html
> 2. https://pubs.opengroup.org/onlinepubs/009696899/basedefs/limits.h.html
> 
> 3. B.t.w. a thing I ended up ejecting out of this was that I made a
>     "test_commit_bulkier" which is N times faster than "test_commit_bulk",
>     it just makes the same commit N times with the printf-repeating feature
>     and feeds it to fast-import, but the test took so long in any case that
>     I couldn't find a plausible way to get it in-tree).
> 

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Jeff King]

On Fri, Dec 10, 2021 at 01:31:10PM +0100, Ævar Arnfjörð Bjarmason wrote:

> I don't think using ssize_t like that is portable, and that we'd need
> something like intmax_t if we needed this in another context.
> 
> Firstly it's not standard C, it's just in POSIX, intmax_t is standard C
> as of C99, which and we have in-tree code that already depends on it
> (and uintmax_t).
> 
> But more importantly it's not "as big as size_t, just signed" in
> POSIX. size_t is "no greater than the width of type long"[1] and
> LONG_MAX is at least 2^31-1 [2].

Thanks, I didn't know that about ssize_t. I do wonder how often it is
_not_ the case that it is of the same magnitude as size_t. Certainly I
can see how write() could decide to just work in SSIZE_MAX chunks, since
the caller has to be prepared to loop anyway. But it seems like the
obvious implementation is for it to be a signed size_t; I'd be curious
to hear of any platforms that diverge from this (i.e., is this a real
portability concern, or like NULL pointers that aren't all-zeroes, one
that we don't care about in practice).

I do suspect we've already made that assumption elsewhere, though it's
hard to easily see. Grepping for ssize_t turns up lots of reasonable and
legitimate uses. Though some like the one in strbuf_realpath() are
questionable (it's assigning from an int!).

> 3. B.t.w. a thing I ended up ejecting out of this was that I made a
>    "test_commit_bulkier" which is N times faster than "test_commit_bulk",
>    it just makes the same commit N times with the printf-repeating feature
>    and feeds it to fast-import, but the test took so long in any case that
>    I couldn't find a plausible way to get it in-tree).

Yes, I noticed it was rather slow. The main culprit is Git writing out
new blobs and trees for each commit, which is what I assume your
"bulkier" version skipped (the existing "bulk" one is careful not to
use any sub-processes).  You can instruct test_commit_bulk to use
identical content in each commit, which saves a lot of time.

It's also highly non-linear in the number of commits when the tree
changes. That suggests that fast-import's tree-handling could be
improved. Here are the results of the hacky perf script below, showing
both the non-linearity in the "full" case and how much faster the
"quick" (commits-only) case is:

  Test                 this tree        
  --------------------------------------
  1234.2: full 1000    0.35(0.27+0.08)  
  1234.3: full 2000    0.85(0.81+0.04)  
  1234.4: full 4000    3.21(3.09+0.11)  
  1234.5: full 8000    12.13(11.85+0.27)
  1234.6: quick 1000   0.14(0.12+0.02)  
  1234.7: quick 2000   0.20(0.18+0.03)  
  1234.8: quick 4000   0.31(0.28+0.04)  
  1234.9: quick 8000   0.58(0.55+0.03)  

-- >8 --
#!/bin/sh

test_description='foo'
. ./perf-lib.sh

test_expect_success 'empty repo' 'git init'

test_perf 'full 1000' 'test_commit_bulk --id=full 1000'
test_perf 'full 2000' 'test_commit_bulk --id=full 2000'
test_perf 'full 4000' 'test_commit_bulk --id=full 4000'
test_perf 'full 8000' 'test_commit_bulk --id=full 8000'

test_perf 'quick 1000' 'test_commit_bulk --id=quick --filename=foo --contents=bar 1000'
test_perf 'quick 2000' 'test_commit_bulk --id=quick --filename=foo --contents=bar 2000'
test_perf 'quick 4000' 'test_commit_bulk --id=quick --filename=foo --contents=bar 4000'
test_perf 'quick 8000' 'test_commit_bulk --id=quick --filename=foo --contents=bar 8000'

test_done
-- >8 --

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Johannes Schindelin]

[-- Attachment #1: Type: text/plain, Size: 5324 bytes --]

Hi Peff,

On Fri, 10 Dec 2021, Jeff King wrote:

> On Fri, Dec 10, 2021 at 11:22:59AM +0100, Ævar Arnfjörð Bjarmason wrote:
>
> > > Dropping the st_mult() does nothing to fix the actual problem (which is
> > > that this function should use a more appropriate type), but introduces
> > > new failure modes.
> >
> > Yes you're entirely right. I had some stupid blinders on while writing
> > this. FWIW I think I was experimenting with some local macros and
> > conflated a testing of the overflow of n*n in gdb with the caste'd
> > version, which you rightly point out here won't have the overflow issue
> > at all. Sorry.
>
> I'm not sure if this is helpful or not, but this is the minimal fix I
> came up with that runs the testcase I showed earlier. It's basically
> just swapping out "int" for "ssize_t" for any variables we use to index
> the arrays (though note a few are themselves held in arrays, and we have
> to cross some function boundaries).
>
> I won't be surprised if it doesn't hit all cases, or if it even hits a
> few it doesn't need to (e.g., should "phase" be dragged along with "i"
> and "j" in the first hunk?). I mostly did guess-and-check on the
> test-case, fixing whatever segfaulted and then running again until it
> worked. I didn't even really read the code very carefully.
>
> I think you _did_ do more of that careful reading, and broke down the
> refactorings into separate patches in your series. Which is good. So I
> think what we'd want is to pick out those parts of your series that end
> up switching the variable type. My goal in sharing this here is just to
> show that the end result of the fix can (and IMHO should) be around this
> same order of magnitude.

I am in favor of this patch. Will you have time to submit this with a
commit message?

Thank you,
Dscho

>
> ---
> diff --git a/linear-assignment.c b/linear-assignment.c
> index ecffc09be6..3efa30c50b 100644
> --- a/linear-assignment.c
> +++ b/linear-assignment.c
> @@ -13,11 +13,11 @@
>   * i is `cost[j + column_count * i].
>   */
>  void compute_assignment(int column_count, int row_count, int *cost,
> -			int *column2row, int *row2column)
> +			ssize_t *column2row, ssize_t *row2column)
>  {
>  	int *v, *d;
>  	int *free_row, free_count = 0, saved_free_count, *pred, *col;
> -	int i, j, phase;
> +	ssize_t i, j, phase;
>
>  	if (column_count < 2) {
>  		memset(column2row, 0, sizeof(int) * column_count);
> @@ -31,7 +31,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
>
>  	/* column reduction */
>  	for (j = column_count - 1; j >= 0; j--) {
> -		int i1 = 0;
> +		ssize_t i1 = 0;
>
>  		for (i = 1; i < row_count; i++)
>  			if (COST(j, i1) > COST(j, i))
> @@ -51,7 +51,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
>  	/* reduction transfer */
>  	ALLOC_ARRAY(free_row, row_count);
>  	for (i = 0; i < row_count; i++) {
> -		int j1 = row2column[i];
> +		ssize_t j1 = row2column[i];
>  		if (j1 == -1)
>  			free_row[free_count++] = i;
>  		else if (j1 < -1)
> @@ -74,13 +74,13 @@ void compute_assignment(int column_count, int row_count, int *cost,
>
>  	/* augmenting row reduction */
>  	for (phase = 0; phase < 2; phase++) {
> -		int k = 0;
> +		ssize_t k = 0;
>
>  		saved_free_count = free_count;
>  		free_count = 0;
>  		while (k < saved_free_count) {
>  			int u1, u2;
> -			int j1 = 0, j2, i0;
> +			ssize_t j1 = 0, j2, i0;
>
>  			i = free_row[k++];
>  			u1 = COST(j1, i) - v[j1];
> @@ -130,7 +130,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
>  	ALLOC_ARRAY(pred, column_count);
>  	ALLOC_ARRAY(col, column_count);
>  	for (free_count = 0; free_count < saved_free_count; free_count++) {
> -		int i1 = free_row[free_count], low = 0, up = 0, last, k;
> +		ssize_t i1 = free_row[free_count], low = 0, up = 0, last, k;
>  		int min, c, u1;
>
>  		for (j = 0; j < column_count; j++) {
> @@ -192,7 +192,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
>  		/* augmentation */
>  		do {
>  			if (j < 0)
> -				BUG("negative j: %d", j);
> +				BUG("negative j: %"PRIdMAX, (intmax_t)j);
>  			i = pred[j];
>  			column2row[j] = i;
>  			SWAP(j, row2column[i]);
> diff --git a/linear-assignment.h b/linear-assignment.h
> index 1dfea76629..7005521d61 100644
> --- a/linear-assignment.h
> +++ b/linear-assignment.h
> @@ -14,7 +14,7 @@
>   * row_count).
>   */
>  void compute_assignment(int column_count, int row_count, int *cost,
> -			int *column2row, int *row2column);
> +			ssize_t *column2row, ssize_t *row2column);
>
>  /* The maximal cost in the cost matrix (to prevent integer overflows). */
>  #define COST_MAX (1<<16)
> diff --git a/range-diff.c b/range-diff.c
> index cac89a2f4f..f1e1e27bf9 100644
> --- a/range-diff.c
> +++ b/range-diff.c
> @@ -308,9 +308,10 @@ static int diffsize(const char *a, const char *b)
>  static void get_correspondences(struct string_list *a, struct string_list *b,
>  				int creation_factor)
>  {
> -	int n = a->nr + b->nr;
> -	int *cost, c, *a2b, *b2a;
> -	int i, j;
> +	size_t n = a->nr + b->nr;
> +	int *cost, c;
> +	ssize_t *a2b, *b2a;
> +	size_t i, j;
>
>  	ALLOC_ARRAY(cost, st_mult(n, n));
>  	ALLOC_ARRAY(a2b, n);
>

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Ævar Arnfjörð Bjarmason]

On Fri, Dec 10 2021, Johannes Schindelin wrote:

> Hi Peff,
>
> On Fri, 10 Dec 2021, Jeff King wrote:
>
>> On Fri, Dec 10, 2021 at 11:22:59AM +0100, Ævar Arnfjörð Bjarmason wrote:
>>
>> > > Dropping the st_mult() does nothing to fix the actual problem (which is
>> > > that this function should use a more appropriate type), but introduces
>> > > new failure modes.
>> >
>> > Yes you're entirely right. I had some stupid blinders on while writing
>> > this. FWIW I think I was experimenting with some local macros and
>> > conflated a testing of the overflow of n*n in gdb with the caste'd
>> > version, which you rightly point out here won't have the overflow issue
>> > at all. Sorry.
>>
>> I'm not sure if this is helpful or not, but this is the minimal fix I
>> came up with that runs the testcase I showed earlier. It's basically
>> just swapping out "int" for "ssize_t" for any variables we use to index
>> the arrays (though note a few are themselves held in arrays, and we have
>> to cross some function boundaries).
>>
>> I won't be surprised if it doesn't hit all cases, or if it even hits a
>> few it doesn't need to (e.g., should "phase" be dragged along with "i"
>> and "j" in the first hunk?). I mostly did guess-and-check on the
>> test-case, fixing whatever segfaulted and then running again until it
>> worked. I didn't even really read the code very carefully.
>>
>> I think you _did_ do more of that careful reading, and broke down the
>> refactorings into separate patches in your series. Which is good. So I
>> think what we'd want is to pick out those parts of your series that end
>> up switching the variable type. My goal in sharing this here is just to
>> show that the end result of the fix can (and IMHO should) be around this
>> same order of magnitude.
>
> I am in favor of this patch. Will you have time to submit this with a
> commit message?

I'd also be happy to pick it up as a massaging of my s/int/intmax_t/
change. I think per[1] that intmax_t is more portable here than ssize_t,
but I'm very likely to be missing something. Corrections most welcome.

Per [1] I ejected that out of my v2 because I think the "cost" being
larger than 1<<16 might not be all that useful. I.e. the limiting that's
in get_correspondences().

But I'll happily admit ignorance on how the actual guts of range-diff
work, I just wanted to fix a segfault I kept running into locally at
some point, and figured I'd submit this RFC.

Doesn't an enlargement of the "int" from an assumed 32 bit unsigned to
say a 64bit unsigned require that 16bit unsigned COST_MAX to be
correspondingly bumped to 32bit unsigned? I.e. we'd define it as 1/2 of
whatever "intmax_t" (or "ssize_t" or "long long int" or whatever) is
defined as?

That may be a question under the umbrella of "Ævar doesn't actually
understand range-diff", but think I recall playing with bumping one and
not the other (or bumping COST_MAX too close to the size of the
container type) and running into errors...

1. https://lore.kernel.org/git/211210.86czm4d3zo.gmgdl@evledraar.gmail.com/

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Johannes Schindelin]

[-- Attachment #1: Type: text/plain, Size: 1510 bytes --]

Hi Ævar,

On Fri, 10 Dec 2021, Ævar Arnfjörð Bjarmason wrote:

> But I'll happily admit ignorance on how the actual guts of range-diff
> work, I just wanted to fix a segfault I kept running into locally at
> some point, and figured I'd submit this RFC.

I understand that it is super tempting to avoid spending the time to
understand how range-diff works and simply make changes until the
segmentation fault is gone, and then shoot off several iterations of the
patch series in the hopes that it gets merged at some point, and that
maybe reviewers who do spend the time to become familiar with the logic
help avoid introduce new bugs.

However, as a reviewer I am totally unsympathetic of this approach. I do
not want to review patches that even go so far as renaming functions when
they claim to "just fix a segfault" and the author even admits that
they're unfamiliar with what the code is supposed to do, without any
indication that they're inclined to invest the effort to change that.

If all you want to do is to fix the segmentation fault, and want to skip
the due diligence of studying the business logic, then just fix that
segmentation fault (I strongly suspect that using `COST()` after modifying
it to use `st_*()` would accomplish that). No need to inflate that to 5
patches. Unless you're thinking of the commit-per-author count as some
sort of scoreboard where you want to win. In which case I am even less
interested in reviewing the patches.

Ciao,
Johannes

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Ævar Arnfjörð Bjarmason]

On Sat, Dec 11 2021, Johannes Schindelin wrote:

> Hi Ævar,
>
> On Fri, 10 Dec 2021, Ævar Arnfjörð Bjarmason wrote:
>
>> But I'll happily admit ignorance on how the actual guts of range-diff
>> work, I just wanted to fix a segfault I kept running into locally at
>> some point, and figured I'd submit this RFC.
>
> I understand that it is super tempting to avoid spending the time to
> understand how range-diff works and simply make changes until the
> segmentation fault is gone, and then shoot off several iterations of the
> patch series in the hopes that it gets merged at some point, and that
> maybe reviewers who do spend the time to become familiar with the logic
> help avoid introduce new bugs.
>
> However, as a reviewer I am totally unsympathetic of this approach. I do
> not want to review patches that even go so far as renaming functions when
> they claim to "just fix a segfault" and the author even admits that
> they're unfamiliar with what the code is supposed to do, without any
> indication that they're inclined to invest the effort to change that.

What you're eliding here is the context where I say that I must not be
getting something because you're apparently endorsing the WIP
s/int/intmax_t/g patch Jeff King inlined upthread without a
corresponding change to COST_MAX.

Don't those two go hand-in-hand, and changing one without the other
would lead to a subtle bug?

> If all you want to do is to fix the segmentation fault, and want to skip
> the due diligence of studying the business logic, then just fix that
> segmentation fault (I strongly suspect that using `COST()` after modifying
> it to use `st_*()` would accomplish that).

Well, this is an RFC series for a bug that I encountered & which seems
to be fixed by these changes, but in an area which I'll happily admit
that I'm not confident enough to say that this is *the* right fix, and I
think both the "RFC" label and both cover letters make that clear.

> No need to inflate that to 5
> patches. Unless you're thinking of the commit-per-author count as some
> sort of scoreboard where you want to win. In which case I am even less
> interested in reviewing the patches.

Can you mention specific things you'd like to have squashed? I do think
this split-up makes thinsg easier to review.

E.g. if we're using the COST() macro in range-diff.c then splitting 4/5
from 5/5 means you don't need to spend as much time mentally splitting
the meaningful changes from a variable rename (which is required for
using that macro).

I agree that 1-3/5 aren't strictly necessary. I did try to do this
without those, but found e.g. reasoning about changing the
one-giant-function in linear-assignment.c harder when it came to the
segfault fix, and likewise the mechanical change from "int" to "size_t"
is (I think) easier to review & reason about.

Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed "int"

[Jeff King]

On Fri, Dec 10, 2021 at 03:27:24PM +0100, Johannes Schindelin wrote:

> > I'm not sure if this is helpful or not, but this is the minimal fix I
> > came up with that runs the testcase I showed earlier. It's basically
> > just swapping out "int" for "ssize_t" for any variables we use to index
> > the arrays (though note a few are themselves held in arrays, and we have
> > to cross some function boundaries).
> >
> > I won't be surprised if it doesn't hit all cases, or if it even hits a
> > few it doesn't need to (e.g., should "phase" be dragged along with "i"
> > and "j" in the first hunk?). I mostly did guess-and-check on the
> > test-case, fixing whatever segfaulted and then running again until it
> > worked. I didn't even really read the code very carefully.
> >
> > I think you _did_ do more of that careful reading, and broke down the
> > refactorings into separate patches in your series. Which is good. So I
> > think what we'd want is to pick out those parts of your series that end
> > up switching the variable type. My goal in sharing this here is just to
> > show that the end result of the fix can (and IMHO should) be around this
> > same order of magnitude.
> 
> I am in favor of this patch. Will you have time to submit this with a
> commit message?

I'm not at all sure that it's sufficient. It avoids overflowing the
cost array accesses, and was tested on a square input of 2^15. But:

  - some of the other ints may need changing, too (e.g., column_count).
    Probably 2^31 commits is out of reach in practice (and probably
    other parts of Git run into problems there anyway). But some of
    those arguments may just be (a->nr * b->nr), whereas I was testing
    overflow at (a->nr + b->nr)^2.

  - I threw around ssize_t willy-nilly. Some of those could be size_t,
    and I think Ævar's patches go in the direction of splitting the two,
    which is good.

  - some light refactoring may be helpful to split those cases ahead of
    time.

So I was hoping Ævar would take this approach and run with it. I just
reviewed his follow-up series, though, and it looks like it is still
putting bounds-checks into the COST macro, which I think is not
sufficient.

-Peff

[RFC PATCH 03/10] range-diff.c: use "size_t" to refer to "struct string_list"'s "nr"

[Ævar Arnfjörð Bjarmason]

In a preceding commit the "nr" member of "struct string_list" was
changed to be "size_t" instead of an "unsigned int". Let's follow suit
here and do the same for our corresponding index variables.

We can also use the st_mult() helper again prepare the argument to
ALLOC_ARRAY(), but this time correctly as the "n" is unsigned. The
same goes for a new addition of "st_add()" for "a->nr + b->nr".

There was a segfault in range-diff.c and linear-assignment.c due to an
"int" overflow. This doesn't solve that problem, but on my system
moves it around a bit. Before this we'd segfault in the
"get_correspondences()" function in range-diff.c, specifically on this
line in the first loop in that function:

    cost[i + n * j] = 0

Now we'll instead make it all the way into compute_assignment() called
by that same function, and segfault on line 37 of linear-assignment.c in:

    if (COST(j, i1) > COST(j, i))

Which is defined as:

    #define COST(column, row) cost[(column) + column_count * (row)]

And will overflow thusly, with a segfault as we try to use that as a
negative index into "cost":

    (GDB) p j + column_count * i
    $10 = -2147454537

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 range-diff.c | 10 +++++-----
 1 file changed, 5 insertions(+), 5 deletions(-)

diff --git a/range-diff.c b/range-diff.c
index 170e8623313..41003033752 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -237,7 +237,7 @@ static int patch_util_cmp(const void *dummy, const struct patch_util *a,
 static void find_exact_matches(struct string_list *a, struct string_list *b)
 {
 	struct hashmap map = HASHMAP_INIT((hashmap_cmp_fn)patch_util_cmp, NULL);
-	int i;
+	size_t i;
 
 	/* First, add the patches of a to a hash map */
 	for (i = 0; i < a->nr; i++) {
@@ -308,11 +308,11 @@ static int diffsize(const char *a, const char *b)
 static void get_correspondences(struct string_list *a, struct string_list *b,
 				int creation_factor)
 {
-	int n = a->nr + b->nr;
+	size_t n = st_add(a->nr, b->nr);
 	int *cost, c, *a2b, *b2a;
-	int i, j;
+	size_t i, j;
 
-	ALLOC_ARRAY(cost, n * n);
+	ALLOC_ARRAY(cost, st_mult(n, n));
 	ALLOC_ARRAY(a2b, n);
 	ALLOC_ARRAY(b2a, n);
 
@@ -473,7 +473,7 @@ static void output(struct string_list *a, struct string_list *b,
 {
 	struct strbuf buf = STRBUF_INIT, dashes = STRBUF_INIT;
 	int patch_no_width = decimal_width(1 + (a->nr > b->nr ? a->nr : b->nr));
-	int i = 0, j = 0;
+	size_t i = 0, j = 0;
 	struct diff_options opts;
 	struct strbuf indent = STRBUF_INIT;
 
-- 
2.34.1.930.g0f9292b224d

[RFC PATCH 04/10] range-diff: zero out elements in "cost" first

[Ævar Arnfjörð Bjarmason]

Have the get_correspondences() function use CALLOC_ARRAY instead of
looping over the newly allocated "cost" to zero out some of its
elements.

The for-loop that zero'd out elements in "cost" wasn't the first loop
in that function, nor did it cover all of its elements, but regardless
of that this change doesn't affect its end-state. None of the
for-loops touched the same items in the array, so we could have (and
an earlier WIP version of this change did) moved the for-loop we're
deleting to come first in get_correspondences().

This can be seen from a careful reading of this code added in in
d9c66f0b5bf (range-diff: first rudimentary implementation,
2018-08-13) (as well as adding some printf-debugging) we'll set all
elements in the in the "n * n" allocated array. That's "n = A+B" where
"A" and "B" are the number of commits in our respective ranges.

So let's just allocate this with CALLOC_ARRAY(), and skip these two
for-loops. Furthermore let's remove the early exit condition from
compute_assignment() in favor of an assert that it must be called with
"column_count > 1", then "get_correspondences()" can skip calling it
when no further filling of the "a2b" and "b2a" arrays is needed.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c |  7 +------
 range-diff.c        | 13 +++++--------
 2 files changed, 6 insertions(+), 14 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index ecffc09be6e..0c0786a63b6 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -19,12 +19,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
 	int *free_row, free_count = 0, saved_free_count, *pred, *col;
 	int i, j, phase;
 
-	if (column_count < 2) {
-		memset(column2row, 0, sizeof(int) * column_count);
-		memset(row2column, 0, sizeof(int) * row_count);
-		return;
-	}
-
+	assert(column_count > 1);
 	memset(column2row, -1, sizeof(int) * column_count);
 	memset(row2column, -1, sizeof(int) * row_count);
 	ALLOC_ARRAY(v, column_count);
diff --git a/range-diff.c b/range-diff.c
index 41003033752..b0ccb46ff4c 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -312,9 +312,9 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 	int *cost, c, *a2b, *b2a;
 	size_t i, j;
 
-	ALLOC_ARRAY(cost, st_mult(n, n));
-	ALLOC_ARRAY(a2b, n);
-	ALLOC_ARRAY(b2a, n);
+	CALLOC_ARRAY(cost, st_mult(n, n));
+	CALLOC_ARRAY(a2b, n);
+	CALLOC_ARRAY(b2a, n);
 
 	for (i = 0; i < a->nr; i++) {
 		struct patch_util *a_util = a->items[i].util;
@@ -346,11 +346,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 			cost[i + n * j] = c;
 	}
 
-	for (i = a->nr; i < n; i++)
-		for (j = b->nr; j < n; j++)
-			cost[i + n * j] = 0;
-
-	compute_assignment(n, n, cost, a2b, b2a);
+	if (n > 1)
+		compute_assignment(n, n, cost, a2b, b2a);
 
 	for (i = 0; i < a->nr; i++)
 		if (a2b[i] >= 0 && a2b[i] < b->nr) {
-- 
2.34.1.930.g0f9292b224d

[RFC PATCH 05/10] linear-assignment.c: split up compute_assignment() function

[Ævar Arnfjörð Bjarmason]

Split up the the long compute_assignment() function to make it easier
to reason about, particularly when it comes to what variables are used
later, and which aren't.

The grouping of "int" v.s. "int *" in function signatures is there to
make subsequent diffs smaller, if we're ever going to have a "nr"
member with a "size_t", but allocate e.g. "int *", and in anticipation
of the type names becoming longer than "int", which would require
re-wrapping.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c | 103 +++++++++++++++++++++++++++++++++-----------
 linear-assignment.h |   3 +-
 2 files changed, 79 insertions(+), 27 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index 0c0786a63b6..7f85745e541 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -8,21 +8,12 @@
 
 #define COST(column, row) cost[(column) + column_count * (row)]
 
-/*
- * The parameter `cost` is the cost matrix: the cost to assign column j to row
- * i is `cost[j + column_count * i].
- */
-void compute_assignment(int column_count, int row_count, int *cost,
-			int *column2row, int *row2column)
+static void columns_reduction(int column_count, int row_count,
+			      int *cost,
+			      int *column2row, int *row2column,
+			      int *v)
 {
-	int *v, *d;
-	int *free_row, free_count = 0, saved_free_count, *pred, *col;
-	int i, j, phase;
-
-	assert(column_count > 1);
-	memset(column2row, -1, sizeof(int) * column_count);
-	memset(row2column, -1, sizeof(int) * row_count);
-	ALLOC_ARRAY(v, column_count);
+	int i, j;
 
 	/* column reduction */
 	for (j = column_count - 1; j >= 0; j--) {
@@ -42,13 +33,21 @@ void compute_assignment(int column_count, int row_count, int *cost,
 			column2row[j] = -1;
 		}
 	}
+}
+
+static void reduction_transfer(int column_count, int row_count,
+			       int *cost,
+			       int *free_row, int *free_count,
+			       int *column2row, int *row2column,
+			       int *v)
+{
+	int i, j;
 
 	/* reduction transfer */
-	ALLOC_ARRAY(free_row, row_count);
 	for (i = 0; i < row_count; i++) {
 		int j1 = row2column[i];
 		if (j1 == -1)
-			free_row[free_count++] = i;
+			free_row[(*free_count)++] = i;
 		else if (j1 < -1)
 			row2column[i] = -2 - j1;
 		else {
@@ -59,21 +58,25 @@ void compute_assignment(int column_count, int row_count, int *cost,
 			v[j1] -= min;
 		}
 	}
+}
 
-	if (free_count ==
-	    (column_count < row_count ? row_count - column_count : 0)) {
-		free(v);
-		free(free_row);
-		return;
-	}
+static void augmenting_row_reduction(int column_count,
+				     int *cost,
+				     int *column2row, int *row2column,
+				     int *free_row, int *free_count, int *saved_free_count,
+				     int *v)
+{
+	int phase;
 
 	/* augmenting row reduction */
 	for (phase = 0; phase < 2; phase++) {
+		int i;
 		int k = 0;
 
-		saved_free_count = free_count;
-		free_count = 0;
-		while (k < saved_free_count) {
+		*saved_free_count = *free_count;
+		*free_count = 0;
+		while (k < *saved_free_count) {
+			int j;
 			int u1, u2;
 			int j1 = 0, j2, i0;
 
@@ -112,12 +115,24 @@ void compute_assignment(int column_count, int row_count, int *cost,
 				if (u1 < u2)
 					free_row[--k] = i0;
 				else
-					free_row[free_count++] = i0;
+					free_row[(*free_count)++] = i0;
 			}
 			row2column[i] = j1;
 			column2row[j1] = i;
 		}
 	}
+}
+
+static void augmentation(int column_count,
+			 int *cost,
+			 int *column2row, int *row2column,
+			 int *free_row, int free_count,
+			 int *v)
+{
+	int i, j;
+	int *d;
+	int *pred, *col;
+	int saved_free_count;
 
 	/* augmentation */
 	saved_free_count = free_count;
@@ -197,6 +212,42 @@ void compute_assignment(int column_count, int row_count, int *cost,
 	free(col);
 	free(pred);
 	free(d);
+}
+
+/*
+ * The parameter `cost` is the cost matrix: the cost to assign column j to row
+ * i is `cost[j + column_count * i].
+ */
+void compute_assignment(int column_count, int row_count,
+			int *cost,
+			int *column2row, int *row2column)
+{
+	int *v;
+	int *free_row, free_count = 0, saved_free_count;
+
+	assert(column_count > 1);
+	memset(column2row, -1, sizeof(int) * column_count);
+	memset(row2column, -1, sizeof(int) * row_count);
+	ALLOC_ARRAY(v, column_count);
+
+	columns_reduction(column_count, row_count, cost, column2row,
+			  row2column, v);
+
+	ALLOC_ARRAY(free_row, row_count);
+	reduction_transfer(column_count, row_count, cost, free_row,
+			   &free_count, column2row, row2column, v);
+	if (free_count ==
+	    (column_count < row_count ? row_count - column_count : 0))
+		goto cleanup;
+
+	augmenting_row_reduction(column_count, cost, column2row,
+				 row2column, free_row, &free_count,
+				 &saved_free_count,v);
+
+	augmentation(column_count, cost, column2row, row2column,
+		     free_row, free_count, v);
+
+cleanup:
 	free(v);
 	free(free_row);
 }
diff --git a/linear-assignment.h b/linear-assignment.h
index 1dfea766290..ef9946bdbfc 100644
--- a/linear-assignment.h
+++ b/linear-assignment.h
@@ -13,7 +13,8 @@
  * assignments (-1 for unassigned, which can happen only if column_count !=
  * row_count).
  */
-void compute_assignment(int column_count, int row_count, int *cost,
+void compute_assignment(int column_count, int row_count,
+			int *cost,
 			int *column2row, int *row2column);
 
 /* The maximal cost in the cost matrix (to prevent integer overflows). */
-- 
2.34.1.930.g0f9292b224d

[RFC PATCH 06/10] linear-assignment.c: take "size_t", not "int" for *_count

[Ævar Arnfjörð Bjarmason]

Future-proof and clarify the compute_assignment() interface by having
it take a "size_t" for the count of its that it's processing. For the
content itself we need to be able to store a "-1", but there's no
reason we can't use a "size_t" for the size of the number of "int"'s
we've got.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c | 10 +++++-----
 linear-assignment.h |  2 +-
 2 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index 7f85745e541..1f8329701a0 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -8,7 +8,7 @@
 
 #define COST(column, row) cost[(column) + column_count * (row)]
 
-static void columns_reduction(int column_count, int row_count,
+static void columns_reduction(size_t column_count, size_t row_count,
 			      int *cost,
 			      int *column2row, int *row2column,
 			      int *v)
@@ -35,7 +35,7 @@ static void columns_reduction(int column_count, int row_count,
 	}
 }
 
-static void reduction_transfer(int column_count, int row_count,
+static void reduction_transfer(size_t column_count, size_t row_count,
 			       int *cost,
 			       int *free_row, int *free_count,
 			       int *column2row, int *row2column,
@@ -60,7 +60,7 @@ static void reduction_transfer(int column_count, int row_count,
 	}
 }
 
-static void augmenting_row_reduction(int column_count,
+static void augmenting_row_reduction(size_t column_count,
 				     int *cost,
 				     int *column2row, int *row2column,
 				     int *free_row, int *free_count, int *saved_free_count,
@@ -123,7 +123,7 @@ static void augmenting_row_reduction(int column_count,
 	}
 }
 
-static void augmentation(int column_count,
+static void augmentation(size_t column_count,
 			 int *cost,
 			 int *column2row, int *row2column,
 			 int *free_row, int free_count,
@@ -218,7 +218,7 @@ static void augmentation(int column_count,
  * The parameter `cost` is the cost matrix: the cost to assign column j to row
  * i is `cost[j + column_count * i].
  */
-void compute_assignment(int column_count, int row_count,
+void compute_assignment(size_t column_count, size_t row_count,
 			int *cost,
 			int *column2row, int *row2column)
 {
diff --git a/linear-assignment.h b/linear-assignment.h
index ef9946bdbfc..9ff055baac1 100644
--- a/linear-assignment.h
+++ b/linear-assignment.h
@@ -13,7 +13,7 @@
  * assignments (-1 for unassigned, which can happen only if column_count !=
  * row_count).
  */
-void compute_assignment(int column_count, int row_count,
+void compute_assignment(size_t column_count, size_t row_count,
 			int *cost,
 			int *column2row, int *row2column);
 
-- 
2.34.1.930.g0f9292b224d

[RFC PATCH 07/10] linear-assignment.c: convert a macro to a "static inline" function

[Ævar Arnfjörð Bjarmason]

Change the COST() macro to be a "static inline" function. On GCC this
makes no difference in performance, but this improves the readability
of the function. In a subsequent commit we'll make use of this to
extend this function with overflow detection.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index 1f8329701a0..e9cec16132a 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -6,7 +6,16 @@
 #include "cache.h"
 #include "linear-assignment.h"
 
-#define COST(column, row) cost[(column) + column_count * (row)]
+static inline int cost_index(int *cost, int a, int b, int c)
+{
+	int r;
+
+	r = b + a * c;
+
+	return r;
+}
+
+#define COST(column, row) cost[cost_index(cost, column_count, column, row)]
 
 static void columns_reduction(size_t column_count, size_t row_count,
 			      int *cost,
-- 
2.34.1.930.g0f9292b224d

[RFC PATCH 08/10] linear-assignment.c: detect signed add/mul on GCC and Clang

[Ævar Arnfjörð Bjarmason]

Extend the cost_index() inline function added in the preceding commit
with signed overflow detection that'll work on GCC[1] and
Clang[2]. See 320d0b493a2 (add helpers for detecting size_t overflow,
2016-02-19) for the existing git-compat-util.h helpers to detect
signed overflow.

This fixes a segfault on that happens when "range-diff" is given a
very large range to work with, such as the difference between
git.git's "master" the git-for-windows fork:

    $ git -P range-diff --creation-factor=50 origin/master...git-for-windows/main
    fatal: integer overflow in cost[47395 + ((47396 * 45309) = -2147454537)] addition

There are known bugs with using these functions in some versions of
GCC, as we'll see in a subsequent commit we're better off detecting
those with the "intprops.h" library, but for now let's add a simpler
implementation that relies on the bare minimum of compiler checking.

1. https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html#Integer-Overflow-Builtins
2. https://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/linear-assignment.c b/linear-assignment.c
index e9cec16132a..b6597b622c8 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -10,7 +10,14 @@ static inline int cost_index(int *cost, int a, int b, int c)
 {
 	int r;
 
+#if defined(__GNUC__) || defined(__clang__)
+	if (__builtin_mul_overflow(a, c, &r))
+		die(_("integer overflow in cost[%d + %d * %c] multiplication"), b, a, c);
+	if (__builtin_add_overflow(b, r, &r))
+		die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r);
+#else
 	r = b + a * c;
+#endif
 
 	return r;
 }
-- 
2.34.1.930.g0f9292b224d

Re: [RFC PATCH 08/10] linear-assignment.c: detect signed add/mul on GCC and Clang

[Jeff King]

On Thu, Dec 09, 2021 at 08:19:25PM +0100, Ævar Arnfjörð Bjarmason wrote:

> diff --git a/linear-assignment.c b/linear-assignment.c
> index e9cec16132a..b6597b622c8 100644
> --- a/linear-assignment.c
> +++ b/linear-assignment.c
> @@ -10,7 +10,14 @@ static inline int cost_index(int *cost, int a, int b, int c)
>  {
>  	int r;
>  
> +#if defined(__GNUC__) || defined(__clang__)
> +	if (__builtin_mul_overflow(a, c, &r))
> +		die(_("integer overflow in cost[%d + %d * %c] multiplication"), b, a, c);
> +	if (__builtin_add_overflow(b, r, &r))
> +		die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r);
> +#else
>  	r = b + a * c;
> +#endif

I think having an inline #if here is the wrong direction. We already
have signed_add_overflows() which you could use for the second check.
We haven't needed signed_mult_overflows() yet, but we could add one.

Those helpers don't use intrinsics yet. I think it would be reasonable
to have them do so when they're available. One of the big reasons we
haven't done so yet is that they're not generally in hot paths. We
generally use them while allocating, where the extra integer operations
and conditional aren't a big deal.

Here you depart from that and do the check on every index computation.
I'm not completely opposed to that approach, but I think a simpler
method (and what most spots have done so far) is to make sure the array
allocation itself is computed correctly, and then have code which
accesses it use an appropriate type to avoid overflow. In this case just
using size_t for the index computation would work, wouldn't it?

(Likewise, if you really want a negative value, then ssize_t should be
OK. It can't represent the full range of size_t, but if it would
overflow that implies the original allocation was consuming more than
half of the address space, which would have failed at the time of
allocation).

I do see that the following patch replaces this #if with similar helpers
from gnulib, which is better. And if we are going to go the route of
using intrinsics in our helpers, then it might be a good idea to use
gnulib's helpers to avoid portability pitfalls. But in that case we
should probably be converting over callers of the existing helpers (and
getting rid of those helpers).

IMHO it isn't really worth it, though, if we can solve this just by
switching to a more appropriate type here (and assuming there's not a
big performance benefit to the other helper call sites).

-Peff

[RFC PATCH 09/10] linear-assignment.c: add and use intprops.h from Gnulib

[Ævar Arnfjörð Bjarmason]

In the preceding commit we started optimistically using
__builtin_{add,mul}_overflow under GCC and Clang, but as reading
through the intprops.h being added here from gnulib reveals, using
just those functions is a rabbit hole of version-specific GCC and
Clang bugs, compiler detection etc.

Let's outsource all that detection to the macro-only intprops.h from
Gnulib. This header is licensed under the LGPL 2.1, the same license
that xdiff/* and compat/regex/* are under. So there's no license
reason for why we can't import this.

This is the latest version from
gnulib.git (https://git.savannah.gnu.org/git/gnulib.git), last
modified with 5d88f13109 (regex: sync with glibc, 2021-09-21). The
once change to it is the removal of:

    #include <limits.h>

Which we'll get from git-compat-util.h.

Now we'll still die the same way on overflow, i.e:

    git -P range-diff --creation-factor=50 origin/master...git-for-windows/main
    fatal: integer overflow in cost[47395 + ((47396 * 45309) = -2147454537)] addition

But this time we don't need compiler-specific checks in our main
sources to do so, this even works on e.g. Intel ICC.

Note that this file has various "git diff --check" issues, hence the
"compat/gnulib/.gitattributes" being added here. These are external
sources, we should import them as close to as-is as we can, to make it
easier to upgrade them in the future.

We could go a step further here and replace the various
unsigned_*_overflows() in "git-compat-util.h" with macros from this
intprops.h header. See [1][2][3][4][5] for our home-grown
implementation of overflow checking. That could be done as simply
replacing them with:

    #include "compat/gnulib/intprops.h"
    #define signed_add_overflows(a, b) INT_ADD_OVERFLOW(a, b)
    #define unsigned_add_overflows(a, b) INT_ADD_OVERFLOW(a, b)
    #define unsigned_mult_overflows(a, b) INT_MULTIPLY_OVERFLOW(a, b)
    #define unsigned_left_shift_overflows(a, shift) INT_LEFT_SHIFT_OVERFLOW(a, shift)

The benefit of doing so is that we'd end up with implementations that
would be more robust, as they'd detect both signed and unsigned
overflows (we should then also rename our own macros).

The disadvantage is that it's a bit slower. I forward-ported the
benchmark program [6] written in 2016. Using the above macro
definitions the slowdown measured with git-hyperfine[7] is the
following:

    $ git hyperfine -L rev HEAD~1,HEAD~0 -s 'make CFLAGS=-O3 git-strbuf-grow' './git-strbuf-grow'
    Benchmark 1: ./git-strbuf-grow' in 'HEAD~1
      Time (mean ± σ):      2.661 s ±  0.025 s    [User: 2.657 s, System: 0.004 s]
      Range (min … max):    2.626 s …  2.713 s    10 runs

    Benchmark 2: ./git-strbuf-grow' in 'HEAD~0
      Time (mean ± σ):      2.875 s ±  0.031 s    [User: 2.871 s, System: 0.004 s]
      Range (min … max):    2.832 s …  2.948 s    10 runs

    Summary
      './git-strbuf-grow' in 'HEAD~1' ran
        1.08 ± 0.02 times faster than './git-strbuf-grow' in 'HEAD~0'

The slowdown is not overhead in Gnulib's intprops.h, but happens under
both GCC and Clang if we use __builtin_add_overflow() itself, so the
difference is in the infinite precision addition the compilers need to
do. We should probably not care and use them anyway, but let's just
narrowly fix the signed overflow issue for now.

1. c03c83152d6 (do not depend on signed integer overflow, 2010-10-05)
2. 1368f65002b (compat: helper for detecting unsigned overflow, 2010-10-10)
3. 320d0b493a2 (add helpers for detecting size_t overflow, 2016-02-19)
4. 935de81289c (add helpers for detecting size_t overflow, 2016-02-19)
5. e2ffeae3f67 (git-compat-util: introduce more size_t helpers, 2021-11-02)
6. https://lore.kernel.org/git/20160601210713.GA18118@sigill.intra.peff.net/
7. https://github.com/avar/git-hyperfine/

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 compat/gnulib/.gitattributes |   1 +
 compat/gnulib/intprops.h     | 637 +++++++++++++++++++++++++++++++++++
 linear-assignment.c          |  11 +-
 3 files changed, 642 insertions(+), 7 deletions(-)
 create mode 100644 compat/gnulib/.gitattributes
 create mode 100644 compat/gnulib/intprops.h

diff --git a/compat/gnulib/.gitattributes b/compat/gnulib/.gitattributes
new file mode 100644
index 00000000000..4ea1db2cd88
--- /dev/null
+++ b/compat/gnulib/.gitattributes
@@ -0,0 +1 @@
+intprops.h whitespace=-indent-with-non-tab
diff --git a/compat/gnulib/intprops.h b/compat/gnulib/intprops.h
new file mode 100644
index 00000000000..20aa90ad2a5
--- /dev/null
+++ b/compat/gnulib/intprops.h
@@ -0,0 +1,637 @@
+/* intprops.h -- properties of integer types
+
+   Copyright (C) 2001-2021 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify it
+   under the terms of the GNU Lesser General Public License as published
+   by the Free Software Foundation; either version 2.1 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public License
+   along with this program.  If not, see <https://www.gnu.org/licenses/>.  */
+
+
+#ifndef _GL_INTPROPS_H
+#define _GL_INTPROPS_H
+
+/* Return a value with the common real type of E and V and the value of V.
+   Do not evaluate E.  */
+#define _GL_INT_CONVERT(e, v) ((1 ? 0 : (e)) + (v))
+
+/* Act like _GL_INT_CONVERT (E, -V) but work around a bug in IRIX 6.5 cc; see
+   <https://lists.gnu.org/r/bug-gnulib/2011-05/msg00406.html>.  */
+#define _GL_INT_NEGATE_CONVERT(e, v) ((1 ? 0 : (e)) - (v))
+
+/* The extra casts in the following macros work around compiler bugs,
+   e.g., in Cray C 5.0.3.0.  */
+
+/* True if the arithmetic type T is an integer type.  bool counts as
+   an integer.  */
+#define TYPE_IS_INTEGER(t) ((t) 1.5 == 1)
+
+/* True if the real type T is signed.  */
+#define TYPE_SIGNED(t) (! ((t) 0 < (t) -1))
+
+/* Return 1 if the real expression E, after promotion, has a
+   signed or floating type.  Do not evaluate E.  */
+#define EXPR_SIGNED(e) (_GL_INT_NEGATE_CONVERT (e, 1) < 0)
+
+
+/* Minimum and maximum values for integer types and expressions.  */
+
+/* The width in bits of the integer type or expression T.
+   Do not evaluate T.  T must not be a bit-field expression.
+   Padding bits are not supported; this is checked at compile-time below.  */
+#define TYPE_WIDTH(t) (sizeof (t) * CHAR_BIT)
+
+/* The maximum and minimum values for the integer type T.  */
+#define TYPE_MINIMUM(t) ((t) ~ TYPE_MAXIMUM (t))
+#define TYPE_MAXIMUM(t)                                                 \
+  ((t) (! TYPE_SIGNED (t)                                               \
+        ? (t) -1                                                        \
+        : ((((t) 1 << (TYPE_WIDTH (t) - 2)) - 1) * 2 + 1)))
+
+/* The maximum and minimum values for the type of the expression E,
+   after integer promotion.  E is not evaluated.  */
+#define _GL_INT_MINIMUM(e)                                              \
+  (EXPR_SIGNED (e)                                                      \
+   ? ~ _GL_SIGNED_INT_MAXIMUM (e)                                       \
+   : _GL_INT_CONVERT (e, 0))
+#define _GL_INT_MAXIMUM(e)                                              \
+  (EXPR_SIGNED (e)                                                      \
+   ? _GL_SIGNED_INT_MAXIMUM (e)                                         \
+   : _GL_INT_NEGATE_CONVERT (e, 1))
+#define _GL_SIGNED_INT_MAXIMUM(e)                                       \
+  (((_GL_INT_CONVERT (e, 1) << (TYPE_WIDTH (+ (e)) - 2)) - 1) * 2 + 1)
+
+/* Work around OpenVMS incompatibility with C99.  */
+#if !defined LLONG_MAX && defined __INT64_MAX
+# define LLONG_MAX __INT64_MAX
+# define LLONG_MIN __INT64_MIN
+#endif
+
+/* This include file assumes that signed types are two's complement without
+   padding bits; the above macros have undefined behavior otherwise.
+   If this is a problem for you, please let us know how to fix it for your host.
+   This assumption is tested by the intprops-tests module.  */
+
+/* Does the __typeof__ keyword work?  This could be done by
+   'configure', but for now it's easier to do it by hand.  */
+#if (2 <= __GNUC__ \
+     || (4 <= __clang_major__) \
+     || (1210 <= __IBMC__ && defined __IBM__TYPEOF__) \
+     || (0x5110 <= __SUNPRO_C && !__STDC__))
+# define _GL_HAVE___TYPEOF__ 1
+#else
+# define _GL_HAVE___TYPEOF__ 0
+#endif
+
+/* Return 1 if the integer type or expression T might be signed.  Return 0
+   if it is definitely unsigned.  T must not be a bit-field expression.
+   This macro does not evaluate its argument, and expands to an
+   integer constant expression.  */
+#if _GL_HAVE___TYPEOF__
+# define _GL_SIGNED_TYPE_OR_EXPR(t) TYPE_SIGNED (__typeof__ (t))
+#else
+# define _GL_SIGNED_TYPE_OR_EXPR(t) 1
+#endif
+
+/* Bound on length of the string representing an unsigned integer
+   value representable in B bits.  log10 (2.0) < 146/485.  The
+   smallest value of B where this bound is not tight is 2621.  */
+#define INT_BITS_STRLEN_BOUND(b) (((b) * 146 + 484) / 485)
+
+/* Bound on length of the string representing an integer type or expression T.
+   T must not be a bit-field expression.
+
+   Subtract 1 for the sign bit if T is signed, and then add 1 more for
+   a minus sign if needed.
+
+   Because _GL_SIGNED_TYPE_OR_EXPR sometimes returns 1 when its argument is
+   unsigned, this macro may overestimate the true bound by one byte when
+   applied to unsigned types of size 2, 4, 16, ... bytes.  */
+#define INT_STRLEN_BOUND(t)                                     \
+  (INT_BITS_STRLEN_BOUND (TYPE_WIDTH (t) - _GL_SIGNED_TYPE_OR_EXPR (t)) \
+   + _GL_SIGNED_TYPE_OR_EXPR (t))
+
+/* Bound on buffer size needed to represent an integer type or expression T,
+   including the terminating null.  T must not be a bit-field expression.  */
+#define INT_BUFSIZE_BOUND(t) (INT_STRLEN_BOUND (t) + 1)
+
+
+/* Range overflow checks.
+
+   The INT_<op>_RANGE_OVERFLOW macros return 1 if the corresponding C
+   operators might not yield numerically correct answers due to
+   arithmetic overflow.  They do not rely on undefined or
+   implementation-defined behavior.  Their implementations are simple
+   and straightforward, but they are harder to use and may be less
+   efficient than the INT_<op>_WRAPV, INT_<op>_OK, and
+   INT_<op>_OVERFLOW macros described below.
+
+   Example usage:
+
+     long int i = ...;
+     long int j = ...;
+     if (INT_MULTIPLY_RANGE_OVERFLOW (i, j, LONG_MIN, LONG_MAX))
+       printf ("multiply would overflow");
+     else
+       printf ("product is %ld", i * j);
+
+   Restrictions on *_RANGE_OVERFLOW macros:
+
+   These macros do not check for all possible numerical problems or
+   undefined or unspecified behavior: they do not check for division
+   by zero, for bad shift counts, or for shifting negative numbers.
+
+   These macros may evaluate their arguments zero or multiple times,
+   so the arguments should not have side effects.  The arithmetic
+   arguments (including the MIN and MAX arguments) must be of the same
+   integer type after the usual arithmetic conversions, and the type
+   must have minimum value MIN and maximum MAX.  Unsigned types should
+   use a zero MIN of the proper type.
+
+   Because all arguments are subject to integer promotions, these
+   macros typically do not work on types narrower than 'int'.
+
+   These macros are tuned for constant MIN and MAX.  For commutative
+   operations such as A + B, they are also tuned for constant B.  */
+
+/* Return 1 if A + B would overflow in [MIN,MAX] arithmetic.
+   See above for restrictions.  */
+#define INT_ADD_RANGE_OVERFLOW(a, b, min, max)          \
+  ((b) < 0                                              \
+   ? (a) < (min) - (b)                                  \
+   : (max) - (b) < (a))
+
+/* Return 1 if A - B would overflow in [MIN,MAX] arithmetic.
+   See above for restrictions.  */
+#define INT_SUBTRACT_RANGE_OVERFLOW(a, b, min, max)     \
+  ((b) < 0                                              \
+   ? (max) + (b) < (a)                                  \
+   : (a) < (min) + (b))
+
+/* Return 1 if - A would overflow in [MIN,MAX] arithmetic.
+   See above for restrictions.  */
+#define INT_NEGATE_RANGE_OVERFLOW(a, min, max)          \
+  ((min) < 0                                            \
+   ? (a) < - (max)                                      \
+   : 0 < (a))
+
+/* Return 1 if A * B would overflow in [MIN,MAX] arithmetic.
+   See above for restrictions.  Avoid && and || as they tickle
+   bugs in Sun C 5.11 2010/08/13 and other compilers; see
+   <https://lists.gnu.org/r/bug-gnulib/2011-05/msg00401.html>.  */
+#define INT_MULTIPLY_RANGE_OVERFLOW(a, b, min, max)     \
+  ((b) < 0                                              \
+   ? ((a) < 0                                           \
+      ? (a) < (max) / (b)                               \
+      : (b) == -1                                       \
+      ? 0                                               \
+      : (min) / (b) < (a))                              \
+   : (b) == 0                                           \
+   ? 0                                                  \
+   : ((a) < 0                                           \
+      ? (a) < (min) / (b)                               \
+      : (max) / (b) < (a)))
+
+/* Return 1 if A / B would overflow in [MIN,MAX] arithmetic.
+   See above for restrictions.  Do not check for division by zero.  */
+#define INT_DIVIDE_RANGE_OVERFLOW(a, b, min, max)       \
+  ((min) < 0 && (b) == -1 && (a) < - (max))
+
+/* Return 1 if A % B would overflow in [MIN,MAX] arithmetic.
+   See above for restrictions.  Do not check for division by zero.
+   Mathematically, % should never overflow, but on x86-like hosts
+   INT_MIN % -1 traps, and the C standard permits this, so treat this
+   as an overflow too.  */
+#define INT_REMAINDER_RANGE_OVERFLOW(a, b, min, max)    \
+  INT_DIVIDE_RANGE_OVERFLOW (a, b, min, max)
+
+/* Return 1 if A << B would overflow in [MIN,MAX] arithmetic.
+   See above for restrictions.  Here, MIN and MAX are for A only, and B need
+   not be of the same type as the other arguments.  The C standard says that
+   behavior is undefined for shifts unless 0 <= B < wordwidth, and that when
+   A is negative then A << B has undefined behavior and A >> B has
+   implementation-defined behavior, but do not check these other
+   restrictions.  */
+#define INT_LEFT_SHIFT_RANGE_OVERFLOW(a, b, min, max)   \
+  ((a) < 0                                              \
+   ? (a) < (min) >> (b)                                 \
+   : (max) >> (b) < (a))
+
+/* True if __builtin_add_overflow (A, B, P) and __builtin_sub_overflow
+   (A, B, P) work when P is non-null.  */
+/* __builtin_{add,sub}_overflow exists but is not reliable in GCC 5.x and 6.x,
+   see <https://gcc.gnu.org/bugzilla/show_bug.cgi?id=98269>.  */
+#if 7 <= __GNUC__ && !defined __ICC
+# define _GL_HAS_BUILTIN_ADD_OVERFLOW 1
+#elif defined __has_builtin
+# define _GL_HAS_BUILTIN_ADD_OVERFLOW __has_builtin (__builtin_add_overflow)
+#else
+# define _GL_HAS_BUILTIN_ADD_OVERFLOW 0
+#endif
+
+/* True if __builtin_mul_overflow (A, B, P) works when P is non-null.  */
+#ifdef __clang__
+/* Work around Clang bug <https://bugs.llvm.org/show_bug.cgi?id=16404>.  */
+# define _GL_HAS_BUILTIN_MUL_OVERFLOW 0
+#else
+# define _GL_HAS_BUILTIN_MUL_OVERFLOW _GL_HAS_BUILTIN_ADD_OVERFLOW
+#endif
+
+/* True if __builtin_add_overflow_p (A, B, C) works, and similarly for
+   __builtin_sub_overflow_p and __builtin_mul_overflow_p.  */
+#if defined __clang__ || defined __ICC
+/* Clang 11 lacks __builtin_mul_overflow_p, and even if it did it
+   would presumably run afoul of Clang bug 16404.  ICC 2021.1's
+   __builtin_add_overflow_p etc. are not treated as integral constant
+   expressions even when all arguments are.  */
+# define _GL_HAS_BUILTIN_OVERFLOW_P 0
+#elif defined __has_builtin
+# define _GL_HAS_BUILTIN_OVERFLOW_P __has_builtin (__builtin_mul_overflow_p)
+#else
+# define _GL_HAS_BUILTIN_OVERFLOW_P (7 <= __GNUC__)
+#endif
+
+/* The _GL*_OVERFLOW macros have the same restrictions as the
+   *_RANGE_OVERFLOW macros, except that they do not assume that operands
+   (e.g., A and B) have the same type as MIN and MAX.  Instead, they assume
+   that the result (e.g., A + B) has that type.  */
+#if _GL_HAS_BUILTIN_OVERFLOW_P
+# define _GL_ADD_OVERFLOW(a, b, min, max)                               \
+   __builtin_add_overflow_p (a, b, (__typeof__ ((a) + (b))) 0)
+# define _GL_SUBTRACT_OVERFLOW(a, b, min, max)                          \
+   __builtin_sub_overflow_p (a, b, (__typeof__ ((a) - (b))) 0)
+# define _GL_MULTIPLY_OVERFLOW(a, b, min, max)                          \
+   __builtin_mul_overflow_p (a, b, (__typeof__ ((a) * (b))) 0)
+#else
+# define _GL_ADD_OVERFLOW(a, b, min, max)                                \
+   ((min) < 0 ? INT_ADD_RANGE_OVERFLOW (a, b, min, max)                  \
+    : (a) < 0 ? (b) <= (a) + (b)                                         \
+    : (b) < 0 ? (a) <= (a) + (b)                                         \
+    : (a) + (b) < (b))
+# define _GL_SUBTRACT_OVERFLOW(a, b, min, max)                           \
+   ((min) < 0 ? INT_SUBTRACT_RANGE_OVERFLOW (a, b, min, max)             \
+    : (a) < 0 ? 1                                                        \
+    : (b) < 0 ? (a) - (b) <= (a)                                         \
+    : (a) < (b))
+# define _GL_MULTIPLY_OVERFLOW(a, b, min, max)                           \
+   (((min) == 0 && (((a) < 0 && 0 < (b)) || ((b) < 0 && 0 < (a))))       \
+    || INT_MULTIPLY_RANGE_OVERFLOW (a, b, min, max))
+#endif
+#define _GL_DIVIDE_OVERFLOW(a, b, min, max)                             \
+  ((min) < 0 ? (b) == _GL_INT_NEGATE_CONVERT (min, 1) && (a) < - (max)  \
+   : (a) < 0 ? (b) <= (a) + (b) - 1                                     \
+   : (b) < 0 && (a) + (b) <= (a))
+#define _GL_REMAINDER_OVERFLOW(a, b, min, max)                          \
+  ((min) < 0 ? (b) == _GL_INT_NEGATE_CONVERT (min, 1) && (a) < - (max)  \
+   : (a) < 0 ? (a) % (b) != ((max) - (b) + 1) % (b)                     \
+   : (b) < 0 && ! _GL_UNSIGNED_NEG_MULTIPLE (a, b, max))
+
+/* Return a nonzero value if A is a mathematical multiple of B, where
+   A is unsigned, B is negative, and MAX is the maximum value of A's
+   type.  A's type must be the same as (A % B)'s type.  Normally (A %
+   -B == 0) suffices, but things get tricky if -B would overflow.  */
+#define _GL_UNSIGNED_NEG_MULTIPLE(a, b, max)                            \
+  (((b) < -_GL_SIGNED_INT_MAXIMUM (b)                                   \
+    ? (_GL_SIGNED_INT_MAXIMUM (b) == (max)                              \
+       ? (a)                                                            \
+       : (a) % (_GL_INT_CONVERT (a, _GL_SIGNED_INT_MAXIMUM (b)) + 1))   \
+    : (a) % - (b))                                                      \
+   == 0)
+
+/* Check for integer overflow, and report low order bits of answer.
+
+   The INT_<op>_OVERFLOW macros return 1 if the corresponding C operators
+   might not yield numerically correct answers due to arithmetic overflow.
+   The INT_<op>_WRAPV macros compute the low-order bits of the sum,
+   difference, and product of two C integers, and return 1 if these
+   low-order bits are not numerically correct.
+   These macros work correctly on all known practical hosts, and do not rely
+   on undefined behavior due to signed arithmetic overflow.
+
+   Example usage, assuming A and B are long int:
+
+     if (INT_MULTIPLY_OVERFLOW (a, b))
+       printf ("result would overflow\n");
+     else
+       printf ("result is %ld (no overflow)\n", a * b);
+
+   Example usage with WRAPV flavor:
+
+     long int result;
+     bool overflow = INT_MULTIPLY_WRAPV (a, b, &result);
+     printf ("result is %ld (%s)\n", result,
+             overflow ? "after overflow" : "no overflow");
+
+   Restrictions on these macros:
+
+   These macros do not check for all possible numerical problems or
+   undefined or unspecified behavior: they do not check for division
+   by zero, for bad shift counts, or for shifting negative numbers.
+
+   These macros may evaluate their arguments zero or multiple times, so the
+   arguments should not have side effects.
+
+   The WRAPV macros are not constant expressions.  They support only
+   +, binary -, and *.
+
+   Because the WRAPV macros convert the result, they report overflow
+   in different circumstances than the OVERFLOW macros do.  For
+   example, in the typical case with 16-bit 'short' and 32-bit 'int',
+   if A, B and R are all of type 'short' then INT_ADD_OVERFLOW (A, B)
+   returns false because the addition cannot overflow after A and B
+   are converted to 'int', whereas INT_ADD_WRAPV (A, B, &R) returns
+   true or false depending on whether the sum fits into 'short'.
+
+   These macros are tuned for their last input argument being a constant.
+
+   Return 1 if the integer expressions A * B, A - B, -A, A * B, A / B,
+   A % B, and A << B would overflow, respectively.  */
+
+#define INT_ADD_OVERFLOW(a, b) \
+  _GL_BINARY_OP_OVERFLOW (a, b, _GL_ADD_OVERFLOW)
+#define INT_SUBTRACT_OVERFLOW(a, b) \
+  _GL_BINARY_OP_OVERFLOW (a, b, _GL_SUBTRACT_OVERFLOW)
+#if _GL_HAS_BUILTIN_OVERFLOW_P
+# define INT_NEGATE_OVERFLOW(a) INT_SUBTRACT_OVERFLOW (0, a)
+#else
+# define INT_NEGATE_OVERFLOW(a) \
+   INT_NEGATE_RANGE_OVERFLOW (a, _GL_INT_MINIMUM (a), _GL_INT_MAXIMUM (a))
+#endif
+#define INT_MULTIPLY_OVERFLOW(a, b) \
+  _GL_BINARY_OP_OVERFLOW (a, b, _GL_MULTIPLY_OVERFLOW)
+#define INT_DIVIDE_OVERFLOW(a, b) \
+  _GL_BINARY_OP_OVERFLOW (a, b, _GL_DIVIDE_OVERFLOW)
+#define INT_REMAINDER_OVERFLOW(a, b) \
+  _GL_BINARY_OP_OVERFLOW (a, b, _GL_REMAINDER_OVERFLOW)
+#define INT_LEFT_SHIFT_OVERFLOW(a, b) \
+  INT_LEFT_SHIFT_RANGE_OVERFLOW (a, b, \
+                                 _GL_INT_MINIMUM (a), _GL_INT_MAXIMUM (a))
+
+/* Return 1 if the expression A <op> B would overflow,
+   where OP_RESULT_OVERFLOW (A, B, MIN, MAX) does the actual test,
+   assuming MIN and MAX are the minimum and maximum for the result type.
+   Arguments should be free of side effects.  */
+#define _GL_BINARY_OP_OVERFLOW(a, b, op_result_overflow)        \
+  op_result_overflow (a, b,                                     \
+                      _GL_INT_MINIMUM (_GL_INT_CONVERT (a, b)), \
+                      _GL_INT_MAXIMUM (_GL_INT_CONVERT (a, b)))
+
+/* Store the low-order bits of A + B, A - B, A * B, respectively, into *R.
+   Return 1 if the result overflows.  See above for restrictions.  */
+#if _GL_HAS_BUILTIN_ADD_OVERFLOW
+# define INT_ADD_WRAPV(a, b, r) __builtin_add_overflow (a, b, r)
+# define INT_SUBTRACT_WRAPV(a, b, r) __builtin_sub_overflow (a, b, r)
+#else
+# define INT_ADD_WRAPV(a, b, r) \
+   _GL_INT_OP_WRAPV (a, b, r, +, _GL_INT_ADD_RANGE_OVERFLOW)
+# define INT_SUBTRACT_WRAPV(a, b, r) \
+   _GL_INT_OP_WRAPV (a, b, r, -, _GL_INT_SUBTRACT_RANGE_OVERFLOW)
+#endif
+#if _GL_HAS_BUILTIN_MUL_OVERFLOW
+# if ((9 < __GNUC__ + (3 <= __GNUC_MINOR__) \
+       || (__GNUC__ == 8 && 4 <= __GNUC_MINOR__)) \
+      && !defined __ICC)
+#  define INT_MULTIPLY_WRAPV(a, b, r) __builtin_mul_overflow (a, b, r)
+# else
+   /* Work around GCC bug 91450.  */
+#  define INT_MULTIPLY_WRAPV(a, b, r) \
+    ((!_GL_SIGNED_TYPE_OR_EXPR (*(r)) && EXPR_SIGNED (a) && EXPR_SIGNED (b) \
+      && _GL_INT_MULTIPLY_RANGE_OVERFLOW (a, b, 0, (__typeof__ (*(r))) -1)) \
+     ? ((void) __builtin_mul_overflow (a, b, r), 1) \
+     : __builtin_mul_overflow (a, b, r))
+# endif
+#else
+# define INT_MULTIPLY_WRAPV(a, b, r) \
+   _GL_INT_OP_WRAPV (a, b, r, *, _GL_INT_MULTIPLY_RANGE_OVERFLOW)
+#endif
+
+/* Nonzero if this compiler has GCC bug 68193 or Clang bug 25390.  See:
+   https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68193
+   https://llvm.org/bugs/show_bug.cgi?id=25390
+   For now, assume all versions of GCC-like compilers generate bogus
+   warnings for _Generic.  This matters only for compilers that
+   lack relevant builtins.  */
+#if __GNUC__ || defined __clang__
+# define _GL__GENERIC_BOGUS 1
+#else
+# define _GL__GENERIC_BOGUS 0
+#endif
+
+/* Store the low-order bits of A <op> B into *R, where OP specifies
+   the operation and OVERFLOW the overflow predicate.  Return 1 if the
+   result overflows.  See above for restrictions.  */
+#if 201112 <= __STDC_VERSION__ && !_GL__GENERIC_BOGUS
+# define _GL_INT_OP_WRAPV(a, b, r, op, overflow) \
+   (_Generic \
+    (*(r), \
+     signed char: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \
+                        signed char, SCHAR_MIN, SCHAR_MAX), \
+     unsigned char: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \
+                        unsigned char, 0, UCHAR_MAX), \
+     short int: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \
+                        short int, SHRT_MIN, SHRT_MAX), \
+     unsigned short int: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \
+                        unsigned short int, 0, USHRT_MAX), \
+     int: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \
+                        int, INT_MIN, INT_MAX), \
+     unsigned int: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \
+                        unsigned int, 0, UINT_MAX), \
+     long int: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \
+                        long int, LONG_MIN, LONG_MAX), \
+     unsigned long int: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \
+                        unsigned long int, 0, ULONG_MAX), \
+     long long int: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long long int, \
+                        long long int, LLONG_MIN, LLONG_MAX), \
+     unsigned long long int: \
+       _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long long int, \
+                        unsigned long long int, 0, ULLONG_MAX)))
+#else
+/* Store the low-order bits of A <op> B into *R, where OP specifies
+   the operation and OVERFLOW the overflow predicate.  If *R is
+   signed, its type is ST with bounds SMIN..SMAX; otherwise its type
+   is UT with bounds U..UMAX.  ST and UT are narrower than int.
+   Return 1 if the result overflows.  See above for restrictions.  */
+# if _GL_HAVE___TYPEOF__
+#  define _GL_INT_OP_WRAPV_SMALLISH(a,b,r,op,overflow,st,smin,smax,ut,umax) \
+    (TYPE_SIGNED (__typeof__ (*(r))) \
+     ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, st, smin, smax) \
+     : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, ut, 0, umax))
+# else
+#  define _GL_INT_OP_WRAPV_SMALLISH(a,b,r,op,overflow,st,smin,smax,ut,umax) \
+    (overflow (a, b, smin, smax) \
+     ? (overflow (a, b, 0, umax) \
+        ? (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a,b,op,unsigned,st), 1) \
+        : (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a,b,op,unsigned,st)) < 0) \
+     : (overflow (a, b, 0, umax) \
+        ? (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a,b,op,unsigned,st)) >= 0 \
+        : (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a,b,op,unsigned,st), 0)))
+# endif
+
+# define _GL_INT_OP_WRAPV(a, b, r, op, overflow) \
+   (sizeof *(r) == sizeof (signed char) \
+    ? _GL_INT_OP_WRAPV_SMALLISH (a, b, r, op, overflow, \
+                                 signed char, SCHAR_MIN, SCHAR_MAX, \
+                                 unsigned char, UCHAR_MAX) \
+    : sizeof *(r) == sizeof (short int) \
+    ? _GL_INT_OP_WRAPV_SMALLISH (a, b, r, op, overflow, \
+                                 short int, SHRT_MIN, SHRT_MAX, \
+                                 unsigned short int, USHRT_MAX) \
+    : sizeof *(r) == sizeof (int) \
+    ? (EXPR_SIGNED (*(r)) \
+       ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \
+                          int, INT_MIN, INT_MAX) \
+       : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \
+                          unsigned int, 0, UINT_MAX)) \
+    : _GL_INT_OP_WRAPV_LONGISH(a, b, r, op, overflow))
+# ifdef LLONG_MAX
+#  define _GL_INT_OP_WRAPV_LONGISH(a, b, r, op, overflow) \
+    (sizeof *(r) == sizeof (long int) \
+     ? (EXPR_SIGNED (*(r)) \
+        ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \
+                           long int, LONG_MIN, LONG_MAX) \
+        : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \
+                           unsigned long int, 0, ULONG_MAX)) \
+     : (EXPR_SIGNED (*(r)) \
+        ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long long int, \
+                           long long int, LLONG_MIN, LLONG_MAX) \
+        : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long long int, \
+                           unsigned long long int, 0, ULLONG_MAX)))
+# else
+#  define _GL_INT_OP_WRAPV_LONGISH(a, b, r, op, overflow) \
+    (EXPR_SIGNED (*(r)) \
+     ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \
+                        long int, LONG_MIN, LONG_MAX) \
+     : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \
+                        unsigned long int, 0, ULONG_MAX))
+# endif
+#endif
+
+/* Store the low-order bits of A <op> B into *R, where the operation
+   is given by OP.  Use the unsigned type UT for calculation to avoid
+   overflow problems.  *R's type is T, with extrema TMIN and TMAX.
+   T must be a signed integer type.  Return 1 if the result overflows.  */
+#define _GL_INT_OP_CALC(a, b, r, op, overflow, ut, t, tmin, tmax) \
+  (overflow (a, b, tmin, tmax) \
+   ? (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a, b, op, ut, t), 1) \
+   : (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a, b, op, ut, t), 0))
+
+/* Return the low-order bits of A <op> B, where the operation is given
+   by OP.  Use the unsigned type UT for calculation to avoid undefined
+   behavior on signed integer overflow, and convert the result to type T.
+   UT is at least as wide as T and is no narrower than unsigned int,
+   T is two's complement, and there is no padding or trap representations.
+   Assume that converting UT to T yields the low-order bits, as is
+   done in all known two's-complement C compilers.  E.g., see:
+   https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html
+
+   According to the C standard, converting UT to T yields an
+   implementation-defined result or signal for values outside T's
+   range.  However, code that works around this theoretical problem
+   runs afoul of a compiler bug in Oracle Studio 12.3 x86.  See:
+   https://lists.gnu.org/r/bug-gnulib/2017-04/msg00049.html
+   As the compiler bug is real, don't try to work around the
+   theoretical problem.  */
+
+#define _GL_INT_OP_WRAPV_VIA_UNSIGNED(a, b, op, ut, t) \
+  ((t) ((ut) (a) op (ut) (b)))
+
+/* Return true if the numeric values A + B, A - B, A * B fall outside
+   the range TMIN..TMAX.  Arguments should be integer expressions
+   without side effects.  TMIN should be signed and nonpositive.
+   TMAX should be positive, and should be signed unless TMIN is zero.  */
+#define _GL_INT_ADD_RANGE_OVERFLOW(a, b, tmin, tmax) \
+  ((b) < 0 \
+   ? (((tmin) \
+       ? ((EXPR_SIGNED (_GL_INT_CONVERT (a, (tmin) - (b))) || (b) < (tmin)) \
+          && (a) < (tmin) - (b)) \
+       : (a) <= -1 - (b)) \
+      || ((EXPR_SIGNED (a) ? 0 <= (a) : (tmax) < (a)) && (tmax) < (a) + (b))) \
+   : (a) < 0 \
+   ? (((tmin) \
+       ? ((EXPR_SIGNED (_GL_INT_CONVERT (b, (tmin) - (a))) || (a) < (tmin)) \
+          && (b) < (tmin) - (a)) \
+       : (b) <= -1 - (a)) \
+      || ((EXPR_SIGNED (_GL_INT_CONVERT (a, b)) || (tmax) < (b)) \
+          && (tmax) < (a) + (b))) \
+   : (tmax) < (b) || (tmax) - (b) < (a))
+#define _GL_INT_SUBTRACT_RANGE_OVERFLOW(a, b, tmin, tmax) \
+  (((a) < 0) == ((b) < 0) \
+   ? ((a) < (b) \
+      ? !(tmin) || -1 - (tmin) < (b) - (a) - 1 \
+      : (tmax) < (a) - (b)) \
+   : (a) < 0 \
+   ? ((!EXPR_SIGNED (_GL_INT_CONVERT ((a) - (tmin), b)) && (a) - (tmin) < 0) \
+      || (a) - (tmin) < (b)) \
+   : ((! (EXPR_SIGNED (_GL_INT_CONVERT (tmax, b)) \
+          && EXPR_SIGNED (_GL_INT_CONVERT ((tmax) + (b), a))) \
+       && (tmax) <= -1 - (b)) \
+      || (tmax) + (b) < (a)))
+#define _GL_INT_MULTIPLY_RANGE_OVERFLOW(a, b, tmin, tmax) \
+  ((b) < 0 \
+   ? ((a) < 0 \
+      ? (EXPR_SIGNED (_GL_INT_CONVERT (tmax, b)) \
+         ? (a) < (tmax) / (b) \
+         : ((INT_NEGATE_OVERFLOW (b) \
+             ? _GL_INT_CONVERT (b, tmax) >> (TYPE_WIDTH (+ (b)) - 1) \
+             : (tmax) / -(b)) \
+            <= -1 - (a))) \
+      : INT_NEGATE_OVERFLOW (_GL_INT_CONVERT (b, tmin)) && (b) == -1 \
+      ? (EXPR_SIGNED (a) \
+         ? 0 < (a) + (tmin) \
+         : 0 < (a) && -1 - (tmin) < (a) - 1) \
+      : (tmin) / (b) < (a)) \
+   : (b) == 0 \
+   ? 0 \
+   : ((a) < 0 \
+      ? (INT_NEGATE_OVERFLOW (_GL_INT_CONVERT (a, tmin)) && (a) == -1 \
+         ? (EXPR_SIGNED (b) ? 0 < (b) + (tmin) : -1 - (tmin) < (b) - 1) \
+         : (tmin) / (a) < (b)) \
+      : (tmax) / (b) < (a)))
+
+/* The following macros compute A + B, A - B, and A * B, respectively.
+   If no overflow occurs, they set *R to the result and return 1;
+   otherwise, they return 0 and may modify *R.
+
+   Example usage:
+
+     long int result;
+     if (INT_ADD_OK (a, b, &result))
+       printf ("result is %ld\n", result);
+     else
+       printf ("overflow\n");
+
+   A, B, and *R should be integers; they need not be the same type,
+   and they need not be all signed or all unsigned.
+
+   These macros work correctly on all known practical hosts, and do not rely
+   on undefined behavior due to signed arithmetic overflow.
+
+   These macros are not constant expressions.
+
+   These macros may evaluate their arguments zero or multiple times, so the
+   arguments should not have side effects.
+
+   These macros are tuned for B being a constant.  */
+
+#define INT_ADD_OK(a, b, r) ! INT_ADD_WRAPV (a, b, r)
+#define INT_SUBTRACT_OK(a, b, r) ! INT_SUBTRACT_WRAPV (a, b, r)
+#define INT_MULTIPLY_OK(a, b, r) ! INT_MULTIPLY_WRAPV (a, b, r)
+
+#endif /* _GL_INTPROPS_H */
diff --git a/linear-assignment.c b/linear-assignment.c
index b6597b622c8..e45099d651a 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -5,19 +5,16 @@
  */
 #include "cache.h"
 #include "linear-assignment.h"
+#include "compat/gnulib/intprops.h"
 
 static inline int cost_index(int *cost, int a, int b, int c)
 {
 	int r;
 
-#if defined(__GNUC__) || defined(__clang__)
-	if (__builtin_mul_overflow(a, c, &r))
-		die(_("integer overflow in cost[%d + %d * %c] multiplication"), b, a, c);
-	if (__builtin_add_overflow(b, r, &r))
+	if (INT_MULTIPLY_WRAPV(a, c, &r))
+		die(_("integer overflow in cost[%d + %d * %d] multiplication"), b, a, c);
+	if (INT_ADD_WRAPV(b, r, &r))
 		die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r);
-#else
-	r = b + a * c;
-#endif
 
 	return r;
 }
-- 
2.34.1.930.g0f9292b224d

[RFC PATCH 10/10] linear-assignment.c: use "intmax_t" instead of "int"

[Ævar Arnfjörð Bjarmason]

Change the "int" type used by compute_assignment() to "intmax_t". On
64 bit systems this changes the overflow "die" added in the preceding
commit (which before that was a segfault) to something that merely
takes a very long time and a lot of memory to run.

On my relatively beefy system this completes:

    git -P range-diff --creation-factor=50 origin/master...git-for-windows/main

In around 300 seconds, with a reported max RSS of just under 18GB, but
it does give you correct results for all ~50k commitsin that range.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c | 92 ++++++++++++++++++++++-----------------------
 linear-assignment.h |  8 +---
 range-diff.c        | 11 +++---
 3 files changed, 54 insertions(+), 57 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index e45099d651a..ccd760520f8 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -7,14 +7,14 @@
 #include "linear-assignment.h"
 #include "compat/gnulib/intprops.h"
 
-static inline int cost_index(int *cost, int a, int b, int c)
+static inline intmax_t cost_index(intmax_t *cost, intmax_t a, intmax_t b, intmax_t c)
 {
-	int r;
+	intmax_t r;
 
 	if (INT_MULTIPLY_WRAPV(a, c, &r))
-		die(_("integer overflow in cost[%d + %d * %d] multiplication"), b, a, c);
+		die(_("integer overflow in cost[%"PRIuMAX" + %"PRIuMAX" * %"PRIuMAX"] multiplication"), b, a, c);
 	if (INT_ADD_WRAPV(b, r, &r))
-		die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r);
+		die(_("integer overflow in cost[%"PRIuMAX" + ((%"PRIuMAX" * %"PRIuMAX") = %"PRIuMAX")] addition"), b, a, c, r);
 
 	return r;
 }
@@ -22,15 +22,15 @@ static inline int cost_index(int *cost, int a, int b, int c)
 #define COST(column, row) cost[cost_index(cost, column_count, column, row)]
 
 static void columns_reduction(size_t column_count, size_t row_count,
-			      int *cost,
-			      int *column2row, int *row2column,
-			      int *v)
+			      intmax_t *cost,
+			      intmax_t *column2row, intmax_t *row2column,
+			      intmax_t *v)
 {
-	int i, j;
+	intmax_t i, j;
 
 	/* column reduction */
 	for (j = column_count - 1; j >= 0; j--) {
-		int i1 = 0;
+		intmax_t i1 = 0;
 
 		for (i = 1; i < row_count; i++)
 			if (COST(j, i1) > COST(j, i))
@@ -49,22 +49,22 @@ static void columns_reduction(size_t column_count, size_t row_count,
 }
 
 static void reduction_transfer(size_t column_count, size_t row_count,
-			       int *cost,
-			       int *free_row, int *free_count,
-			       int *column2row, int *row2column,
-			       int *v)
+			       intmax_t *cost,
+			       intmax_t *free_row, intmax_t *free_count,
+			       intmax_t *column2row, intmax_t *row2column,
+			       intmax_t *v)
 {
-	int i, j;
+	intmax_t i, j;
 
 	/* reduction transfer */
 	for (i = 0; i < row_count; i++) {
-		int j1 = row2column[i];
+		intmax_t j1 = row2column[i];
 		if (j1 == -1)
 			free_row[(*free_count)++] = i;
 		else if (j1 < -1)
 			row2column[i] = -2 - j1;
 		else {
-			int min = COST(!j1, i) - v[!j1];
+			intmax_t min = COST(!j1, i) - v[!j1];
 			for (j = 1; j < column_count; j++)
 				if (j != j1 && min > COST(j, i) - v[j])
 					min = COST(j, i) - v[j];
@@ -74,31 +74,31 @@ static void reduction_transfer(size_t column_count, size_t row_count,
 }
 
 static void augmenting_row_reduction(size_t column_count,
-				     int *cost,
-				     int *column2row, int *row2column,
-				     int *free_row, int *free_count, int *saved_free_count,
-				     int *v)
+				     intmax_t *cost,
+				     intmax_t *column2row, intmax_t *row2column,
+				     intmax_t *free_row, intmax_t *free_count, intmax_t *saved_free_count,
+				     intmax_t *v)
 {
 	int phase;
 
 	/* augmenting row reduction */
 	for (phase = 0; phase < 2; phase++) {
-		int i;
-		int k = 0;
+		intmax_t i;
+		intmax_t k = 0;
 
 		*saved_free_count = *free_count;
 		*free_count = 0;
 		while (k < *saved_free_count) {
-			int j;
-			int u1, u2;
-			int j1 = 0, j2, i0;
+			intmax_t j;
+			intmax_t u1, u2;
+			intmax_t j1 = 0, j2, i0;
 
 			i = free_row[k++];
 			u1 = COST(j1, i) - v[j1];
 			j2 = -1;
-			u2 = INT_MAX;
+			u2 = INTMAX_MAX;
 			for (j = 1; j < column_count; j++) {
-				int c = COST(j, i) - v[j];
+				intmax_t c = COST(j, i) - v[j];
 				if (u2 > c) {
 					if (u1 < c) {
 						u2 = c;
@@ -137,15 +137,15 @@ static void augmenting_row_reduction(size_t column_count,
 }
 
 static void augmentation(size_t column_count,
-			 int *cost,
-			 int *column2row, int *row2column,
-			 int *free_row, int free_count,
-			 int *v)
+			 intmax_t *cost,
+			 intmax_t *column2row, intmax_t *row2column,
+			 intmax_t *free_row, intmax_t free_count,
+			 intmax_t *v)
 {
-	int i, j;
-	int *d;
-	int *pred, *col;
-	int saved_free_count;
+	intmax_t i, j;
+	intmax_t *d;
+	intmax_t *pred, *col;
+	intmax_t saved_free_count;
 
 	/* augmentation */
 	saved_free_count = free_count;
@@ -153,8 +153,8 @@ static void augmentation(size_t column_count,
 	ALLOC_ARRAY(pred, column_count);
 	ALLOC_ARRAY(col, column_count);
 	for (free_count = 0; free_count < saved_free_count; free_count++) {
-		int i1 = free_row[free_count], low = 0, up = 0, last, k;
-		int min, c, u1;
+		intmax_t i1 = free_row[free_count], low = 0, up = 0, last, k;
+		intmax_t min, c, u1;
 
 		for (j = 0; j < column_count; j++) {
 			d[j] = COST(j, i1) - v[j];
@@ -184,7 +184,7 @@ static void augmentation(size_t column_count,
 
 			/* scan a row */
 			do {
-				int j1 = col[low++];
+				intmax_t j1 = col[low++];
 
 				i = column2row[j1];
 				u1 = COST(j1, i) - v[j1] - min;
@@ -208,14 +208,14 @@ static void augmentation(size_t column_count,
 update:
 		/* updating of the column pieces */
 		for (k = 0; k < last; k++) {
-			int j1 = col[k];
+			intmax_t j1 = col[k];
 			v[j1] += d[j1] - min;
 		}
 
 		/* augmentation */
 		do {
 			if (j < 0)
-				BUG("negative j: %d", j);
+				BUG("negative j: %"PRIuMAX, j);
 			i = pred[j];
 			column2row[j] = i;
 			SWAP(j, row2column[i]);
@@ -232,15 +232,15 @@ static void augmentation(size_t column_count,
  * i is `cost[j + column_count * i].
  */
 void compute_assignment(size_t column_count, size_t row_count,
-			int *cost,
-			int *column2row, int *row2column)
+			intmax_t *cost,
+			intmax_t *column2row, intmax_t *row2column)
 {
-	int *v;
-	int *free_row, free_count = 0, saved_free_count;
+	intmax_t *v;
+	intmax_t *free_row, free_count = 0, saved_free_count;
 
 	assert(column_count > 1);
-	memset(column2row, -1, sizeof(int) * column_count);
-	memset(row2column, -1, sizeof(int) * row_count);
+	memset(column2row, -1, sizeof(intmax_t) * column_count);
+	memset(row2column, -1, sizeof(intmax_t) * row_count);
 	ALLOC_ARRAY(v, column_count);
 
 	columns_reduction(column_count, row_count, cost, column2row,
diff --git a/linear-assignment.h b/linear-assignment.h
index 9ff055baac1..ee2726a7c8b 100644
--- a/linear-assignment.h
+++ b/linear-assignment.h
@@ -14,10 +14,6 @@
  * row_count).
  */
 void compute_assignment(size_t column_count, size_t row_count,
-			int *cost,
-			int *column2row, int *row2column);
-
-/* The maximal cost in the cost matrix (to prevent integer overflows). */
-#define COST_MAX (1<<16)
-
+			intmax_t *cost,
+			intmax_t *column2row, intmax_t *row2column);
 #endif
diff --git a/range-diff.c b/range-diff.c
index b0ccb46ff4c..3442ebdd65c 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -302,20 +302,21 @@ static int diffsize(const char *a, const char *b)
 		return count;
 
 	error(_("failed to generate diff"));
-	return COST_MAX;
+	return INT_MAX;
 }
 
 static void get_correspondences(struct string_list *a, struct string_list *b,
 				int creation_factor)
 {
 	size_t n = st_add(a->nr, b->nr);
-	int *cost, c, *a2b, *b2a;
+	intmax_t *cost, c, *a2b, *b2a;
 	size_t i, j;
 
 	CALLOC_ARRAY(cost, st_mult(n, n));
 	CALLOC_ARRAY(a2b, n);
 	CALLOC_ARRAY(b2a, n);
 
+
 	for (i = 0; i < a->nr; i++) {
 		struct patch_util *a_util = a->items[i].util;
 
@@ -327,12 +328,12 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 			else if (a_util->matching < 0 && b_util->matching < 0)
 				c = diffsize(a_util->diff, b_util->diff);
 			else
-				c = COST_MAX;
+				c = INT_MAX;
 			cost[i + n * j] = c;
 		}
 
 		c = a_util->matching < 0 ?
-			a_util->diffsize * creation_factor / 100 : COST_MAX;
+			a_util->diffsize * creation_factor / 100 : INT_MAX;
 		for (j = b->nr; j < n; j++)
 			cost[i + n * j] = c;
 	}
@@ -341,7 +342,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 		struct patch_util *util = b->items[j].util;
 
 		c = util->matching < 0 ?
-			util->diffsize * creation_factor / 100 : COST_MAX;
+			util->diffsize * creation_factor / 100 : INT_MAX;
 		for (i = a->nr; i < n; i++)
 			cost[i + n * j] = c;
 	}
-- 
2.34.1.930.g0f9292b224d

Re: [RFC PATCH 10/10] linear-assignment.c: use "intmax_t" instead of "int"

[Jeff King]

On Thu, Dec 09, 2021 at 08:19:27PM +0100, Ævar Arnfjörð Bjarmason wrote:

> Change the "int" type used by compute_assignment() to "intmax_t". On
> 64 bit systems this changes the overflow "die" added in the preceding
> commit (which before that was a segfault) to something that merely
> takes a very long time and a lot of memory to run.
> 
> On my relatively beefy system this completes:
> 
>     git -P range-diff --creation-factor=50 origin/master...git-for-windows/main
> 
> In around 300 seconds, with a reported max RSS of just under 18GB, but
> it does give you correct results for all ~50k commitsin that range.

So here you do what I think is the "real" fix. And at this point I
suspect that the overflow checks here:

> -static inline int cost_index(int *cost, int a, int b, int c)
> +static inline intmax_t cost_index(intmax_t *cost, intmax_t a, intmax_t b, intmax_t c)
>  {
> -	int r;
> +	intmax_t r;
>  
>  	if (INT_MULTIPLY_WRAPV(a, c, &r))
> -		die(_("integer overflow in cost[%d + %d * %d] multiplication"), b, a, c);
> +		die(_("integer overflow in cost[%"PRIuMAX" + %"PRIuMAX" * %"PRIuMAX"] multiplication"), b, a, c);
>  	if (INT_ADD_WRAPV(b, r, &r))
> -		die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r);
> +		die(_("integer overflow in cost[%"PRIuMAX" + ((%"PRIuMAX" * %"PRIuMAX") = %"PRIuMAX")] addition"), b, a, c, r);
>  
>  	return r;

cannot be triggered. We are indexing an array that is already limited to
size_t. So using that type should be sufficient (or else we have
problems even outside of overflow).

And for that reason I'd probably pick size_t (or ssize_t; you don't need
it in the hunk above, but presumably some of the other code cares about
signedness. And as I said earlier, it's effectively the same from a
protection standpoint).

-Peff

[RFC PATCH v2 0/5] range-diff: fix segfault due to integer overflow

[Ævar Arnfjörð Bjarmason]

Now a much smaller and hopefully more sensible fix for an overflow in
range-diff, thanks a lot to Jeff King for comments on the previous
(bad) direction in v1.

Ævar Arnfjörð Bjarmason (5):
  range-diff: zero out elements in "cost" first
  linear-assignment.c: split up compute_assignment() function
  linear-assignment.c: take "size_t", not "int" for *_count
  range-diff.c: rename "n" to "column_count" in get_correspondences()
  range-diff: fix integer overflow & segfault on cost[i + n * j]

 linear-assignment.c | 110 +++++++++++++++++++++++++++++++-------------
 linear-assignment.h |  20 +++++++-
 range-diff.c        |  25 +++++-----
 3 files changed, 107 insertions(+), 48 deletions(-)

Range-diff against v1:
 1:  7c929096381 <  -:  ----------- string-list API: change "nr" and "alloc" to "size_t"
 2:  bd7d014c531 <  -:  ----------- range-diff.c: don't use st_mult() for signed "int"
 3:  183418f1223 <  -:  ----------- range-diff.c: use "size_t" to refer to "struct string_list"'s "nr"
 4:  fe9dcb2d453 !  1:  068c203adc6 range-diff: zero out elements in "cost" first
    @@ linear-assignment.c: void compute_assignment(int column_count, int row_count, in
      ## range-diff.c ##
     @@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,
      	int *cost, c, *a2b, *b2a;
    - 	size_t i, j;
    + 	int i, j;
      
     -	ALLOC_ARRAY(cost, st_mult(n, n));
     -	ALLOC_ARRAY(a2b, n);
 5:  0e1e2d107cd =  2:  2233872545e linear-assignment.c: split up compute_assignment() function
 6:  9b697720e00 =  3:  580b76c0759 linear-assignment.c: take "size_t", not "int" for *_count
10:  46395080b64 !  4:  f8bbe1954fc linear-assignment.c: use "intmax_t" instead of "int"
    @@ Metadata
     Author: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
     
      ## Commit message ##
    -    linear-assignment.c: use "intmax_t" instead of "int"
    +    range-diff.c: rename "n" to "column_count" in get_correspondences()
     
    -    Change the "int" type used by compute_assignment() to "intmax_t". On
    -    64 bit systems this changes the overflow "die" added in the preceding
    -    commit (which before that was a segfault) to something that merely
    -    takes a very long time and a lot of memory to run.
    -
    -    On my relatively beefy system this completes:
    -
    -        git -P range-diff --creation-factor=50 origin/master...git-for-windows/main
    -
    -    In around 300 seconds, with a reported max RSS of just under 18GB, but
    -    it does give you correct results for all ~50k commitsin that range.
    +    In preparation for using the COST macro in linear-assignment.c rename
    +    the "n" variable, it assumes that the "n" in "a + n * b" is named
    +    "column_count".
     
         Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
     
    - ## linear-assignment.c ##
    -@@
    - #include "linear-assignment.h"
    - #include "compat/gnulib/intprops.h"
    - 
    --static inline int cost_index(int *cost, int a, int b, int c)
    -+static inline intmax_t cost_index(intmax_t *cost, intmax_t a, intmax_t b, intmax_t c)
    - {
    --	int r;
    -+	intmax_t r;
    - 
    - 	if (INT_MULTIPLY_WRAPV(a, c, &r))
    --		die(_("integer overflow in cost[%d + %d * %d] multiplication"), b, a, c);
    -+		die(_("integer overflow in cost[%"PRIuMAX" + %"PRIuMAX" * %"PRIuMAX"] multiplication"), b, a, c);
    - 	if (INT_ADD_WRAPV(b, r, &r))
    --		die(_("integer overflow in cost[%d + ((%d * %d) = %d)] addition"), b, a, c, r);
    -+		die(_("integer overflow in cost[%"PRIuMAX" + ((%"PRIuMAX" * %"PRIuMAX") = %"PRIuMAX")] addition"), b, a, c, r);
    - 
    - 	return r;
    - }
    -@@ linear-assignment.c: static inline int cost_index(int *cost, int a, int b, int c)
    - #define COST(column, row) cost[cost_index(cost, column_count, column, row)]
    - 
    - static void columns_reduction(size_t column_count, size_t row_count,
    --			      int *cost,
    --			      int *column2row, int *row2column,
    --			      int *v)
    -+			      intmax_t *cost,
    -+			      intmax_t *column2row, intmax_t *row2column,
    -+			      intmax_t *v)
    - {
    --	int i, j;
    -+	intmax_t i, j;
    - 
    - 	/* column reduction */
    - 	for (j = column_count - 1; j >= 0; j--) {
    --		int i1 = 0;
    -+		intmax_t i1 = 0;
    - 
    - 		for (i = 1; i < row_count; i++)
    - 			if (COST(j, i1) > COST(j, i))
    -@@ linear-assignment.c: static void columns_reduction(size_t column_count, size_t row_count,
    - }
    - 
    - static void reduction_transfer(size_t column_count, size_t row_count,
    --			       int *cost,
    --			       int *free_row, int *free_count,
    --			       int *column2row, int *row2column,
    --			       int *v)
    -+			       intmax_t *cost,
    -+			       intmax_t *free_row, intmax_t *free_count,
    -+			       intmax_t *column2row, intmax_t *row2column,
    -+			       intmax_t *v)
    - {
    --	int i, j;
    -+	intmax_t i, j;
    - 
    - 	/* reduction transfer */
    - 	for (i = 0; i < row_count; i++) {
    --		int j1 = row2column[i];
    -+		intmax_t j1 = row2column[i];
    - 		if (j1 == -1)
    - 			free_row[(*free_count)++] = i;
    - 		else if (j1 < -1)
    - 			row2column[i] = -2 - j1;
    - 		else {
    --			int min = COST(!j1, i) - v[!j1];
    -+			intmax_t min = COST(!j1, i) - v[!j1];
    - 			for (j = 1; j < column_count; j++)
    - 				if (j != j1 && min > COST(j, i) - v[j])
    - 					min = COST(j, i) - v[j];
    -@@ linear-assignment.c: static void reduction_transfer(size_t column_count, size_t row_count,
    - }
    - 
    - static void augmenting_row_reduction(size_t column_count,
    --				     int *cost,
    --				     int *column2row, int *row2column,
    --				     int *free_row, int *free_count, int *saved_free_count,
    --				     int *v)
    -+				     intmax_t *cost,
    -+				     intmax_t *column2row, intmax_t *row2column,
    -+				     intmax_t *free_row, intmax_t *free_count, intmax_t *saved_free_count,
    -+				     intmax_t *v)
    - {
    - 	int phase;
    - 
    - 	/* augmenting row reduction */
    - 	for (phase = 0; phase < 2; phase++) {
    --		int i;
    --		int k = 0;
    -+		intmax_t i;
    -+		intmax_t k = 0;
    - 
    - 		*saved_free_count = *free_count;
    - 		*free_count = 0;
    - 		while (k < *saved_free_count) {
    --			int j;
    --			int u1, u2;
    --			int j1 = 0, j2, i0;
    -+			intmax_t j;
    -+			intmax_t u1, u2;
    -+			intmax_t j1 = 0, j2, i0;
    - 
    - 			i = free_row[k++];
    - 			u1 = COST(j1, i) - v[j1];
    - 			j2 = -1;
    --			u2 = INT_MAX;
    -+			u2 = INTMAX_MAX;
    - 			for (j = 1; j < column_count; j++) {
    --				int c = COST(j, i) - v[j];
    -+				intmax_t c = COST(j, i) - v[j];
    - 				if (u2 > c) {
    - 					if (u1 < c) {
    - 						u2 = c;
    -@@ linear-assignment.c: static void augmenting_row_reduction(size_t column_count,
    - }
    - 
    - static void augmentation(size_t column_count,
    --			 int *cost,
    --			 int *column2row, int *row2column,
    --			 int *free_row, int free_count,
    --			 int *v)
    -+			 intmax_t *cost,
    -+			 intmax_t *column2row, intmax_t *row2column,
    -+			 intmax_t *free_row, intmax_t free_count,
    -+			 intmax_t *v)
    - {
    --	int i, j;
    --	int *d;
    --	int *pred, *col;
    --	int saved_free_count;
    -+	intmax_t i, j;
    -+	intmax_t *d;
    -+	intmax_t *pred, *col;
    -+	intmax_t saved_free_count;
    - 
    - 	/* augmentation */
    - 	saved_free_count = free_count;
    -@@ linear-assignment.c: static void augmentation(size_t column_count,
    - 	ALLOC_ARRAY(pred, column_count);
    - 	ALLOC_ARRAY(col, column_count);
    - 	for (free_count = 0; free_count < saved_free_count; free_count++) {
    --		int i1 = free_row[free_count], low = 0, up = 0, last, k;
    --		int min, c, u1;
    -+		intmax_t i1 = free_row[free_count], low = 0, up = 0, last, k;
    -+		intmax_t min, c, u1;
    - 
    - 		for (j = 0; j < column_count; j++) {
    - 			d[j] = COST(j, i1) - v[j];
    -@@ linear-assignment.c: static void augmentation(size_t column_count,
    - 
    - 			/* scan a row */
    - 			do {
    --				int j1 = col[low++];
    -+				intmax_t j1 = col[low++];
    - 
    - 				i = column2row[j1];
    - 				u1 = COST(j1, i) - v[j1] - min;
    -@@ linear-assignment.c: static void augmentation(size_t column_count,
    - update:
    - 		/* updating of the column pieces */
    - 		for (k = 0; k < last; k++) {
    --			int j1 = col[k];
    -+			intmax_t j1 = col[k];
    - 			v[j1] += d[j1] - min;
    - 		}
    - 
    - 		/* augmentation */
    - 		do {
    - 			if (j < 0)
    --				BUG("negative j: %d", j);
    -+				BUG("negative j: %"PRIuMAX, j);
    - 			i = pred[j];
    - 			column2row[j] = i;
    - 			SWAP(j, row2column[i]);
    -@@ linear-assignment.c: static void augmentation(size_t column_count,
    -  * i is `cost[j + column_count * i].
    -  */
    - void compute_assignment(size_t column_count, size_t row_count,
    --			int *cost,
    --			int *column2row, int *row2column)
    -+			intmax_t *cost,
    -+			intmax_t *column2row, intmax_t *row2column)
    - {
    --	int *v;
    --	int *free_row, free_count = 0, saved_free_count;
    -+	intmax_t *v;
    -+	intmax_t *free_row, free_count = 0, saved_free_count;
    - 
    - 	assert(column_count > 1);
    --	memset(column2row, -1, sizeof(int) * column_count);
    --	memset(row2column, -1, sizeof(int) * row_count);
    -+	memset(column2row, -1, sizeof(intmax_t) * column_count);
    -+	memset(row2column, -1, sizeof(intmax_t) * row_count);
    - 	ALLOC_ARRAY(v, column_count);
    - 
    - 	columns_reduction(column_count, row_count, cost, column2row,
    -
    - ## linear-assignment.h ##
    -@@
    -  * row_count).
    -  */
    - void compute_assignment(size_t column_count, size_t row_count,
    --			int *cost,
    --			int *column2row, int *row2column);
    --
    --/* The maximal cost in the cost matrix (to prevent integer overflows). */
    --#define COST_MAX (1<<16)
    --
    -+			intmax_t *cost,
    -+			intmax_t *column2row, intmax_t *row2column);
    - #endif
    -
      ## range-diff.c ##
     @@ range-diff.c: static int diffsize(const char *a, const char *b)
    - 		return count;
    - 
    - 	error(_("failed to generate diff"));
    --	return COST_MAX;
    -+	return INT_MAX;
    - }
    - 
      static void get_correspondences(struct string_list *a, struct string_list *b,
      				int creation_factor)
      {
    - 	size_t n = st_add(a->nr, b->nr);
    --	int *cost, c, *a2b, *b2a;
    -+	intmax_t *cost, c, *a2b, *b2a;
    - 	size_t i, j;
    - 
    - 	CALLOC_ARRAY(cost, st_mult(n, n));
    - 	CALLOC_ARRAY(a2b, n);
    - 	CALLOC_ARRAY(b2a, n);
    +-	int n = a->nr + b->nr;
    ++	int column_count = st_add(a->nr, b->nr);
    + 	int *cost, c, *a2b, *b2a;
    + 	int i, j;
    + 
    +-	CALLOC_ARRAY(cost, st_mult(n, n));
    +-	CALLOC_ARRAY(a2b, n);
    +-	CALLOC_ARRAY(b2a, n);
    ++	CALLOC_ARRAY(cost, st_mult(column_count, column_count));
    ++	CALLOC_ARRAY(a2b, column_count);
    ++	CALLOC_ARRAY(b2a, column_count);
      
    -+
      	for (i = 0; i < a->nr; i++) {
      		struct patch_util *a_util = a->items[i].util;
    - 
     @@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,
    - 			else if (a_util->matching < 0 && b_util->matching < 0)
      				c = diffsize(a_util->diff, b_util->diff);
      			else
    --				c = COST_MAX;
    -+				c = INT_MAX;
    - 			cost[i + n * j] = c;
    + 				c = COST_MAX;
    +-			cost[i + n * j] = c;
    ++			cost[i + column_count * j] = c;
      		}
      
      		c = a_util->matching < 0 ?
    --			a_util->diffsize * creation_factor / 100 : COST_MAX;
    -+			a_util->diffsize * creation_factor / 100 : INT_MAX;
    - 		for (j = b->nr; j < n; j++)
    - 			cost[i + n * j] = c;
    + 			a_util->diffsize * creation_factor / 100 : COST_MAX;
    +-		for (j = b->nr; j < n; j++)
    +-			cost[i + n * j] = c;
    ++		for (j = b->nr; j < column_count; j++)
    ++			cost[i + column_count * j] = c;
      	}
    + 
    + 	for (j = 0; j < b->nr; j++) {
     @@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,
    - 		struct patch_util *util = b->items[j].util;
      
      		c = util->matching < 0 ?
    --			util->diffsize * creation_factor / 100 : COST_MAX;
    -+			util->diffsize * creation_factor / 100 : INT_MAX;
    - 		for (i = a->nr; i < n; i++)
    - 			cost[i + n * j] = c;
    + 			util->diffsize * creation_factor / 100 : COST_MAX;
    +-		for (i = a->nr; i < n; i++)
    +-			cost[i + n * j] = c;
    ++		for (i = a->nr; i < column_count; i++)
    ++			cost[i + column_count * j] = c;
      	}
    + 
    +-	if (n > 1)
    +-		compute_assignment(n, n, cost, a2b, b2a);
    ++	if (column_count > 1)
    ++		compute_assignment(column_count, column_count, cost, a2b, b2a);
    + 
    + 	for (i = 0; i < a->nr; i++)
    + 		if (a2b[i] >= 0 && a2b[i] < b->nr) {
 7:  a82771413f7 !  5:  9194965635a linear-assignment.c: convert a macro to a "static inline" function
    @@ Metadata
     Author: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
     
      ## Commit message ##
    -    linear-assignment.c: convert a macro to a "static inline" function
    +    range-diff: fix integer overflow & segfault on cost[i + n * j]
     
    -    Change the COST() macro to be a "static inline" function. On GCC this
    -    makes no difference in performance, but this improves the readability
    -    of the function. In a subsequent commit we'll make use of this to
    -    extend this function with overflow detection.
    +    in preceding commits the "column_count" and the "int*"'s we malloc()
    +    were changed to track their length with a size_t, so we're able to
    +    track as many "cost" items as malloc() will give us.
    +
    +    But we'd still segfault on relatively large range comparisons,
    +    e.g. this would segfault:
    +
    +        git -P range-diff --creation-factor=50 origin/master...git-for-windows/main
    +
    +    The reason for that is that we'd still use integer types to compute an
    +    array index into the "cost" array, which would overflow. The result of
    +    a signed overflow in C is undefined, but on my system it'll result in
    +    a negative number, and a prompt segfault as we'll try to access a
    +    negative array index.
    +
    +    Luckily we used the COST() macro in linear-assignment.c already for
    +    all of these lookups, and in a preceding commit we renamed "n" in
    +    "range-diff.c"'s get_correspondences() to "column_count" in
    +    preparation for using it here.
    +
    +    So let's use it for the three occurrences of "cost" indexing in
    +    range-diff.c, and have the COST() macro itself do overflow checking
    +    with st_mult() and st_add(). Due to the cast to "size_t" from "int"
    +    we'll avoid the segfault, and will end up correctly pointing to the
    +    relevant "int *".
    +
    +    It's not important that we use the new cost_offset() inline function
    +    here, we could also use the st_*() macros inline. By using it we'll
    +    get a more meaningful backtrace in a debugger to the relevant
    +    addition/multiplication line if we end up calling die() here.
    +
    +    It's still possible for us to overflow even with this change, that's
    +    because the iteration variables (such as "i" and "j" in this diff
    +    context are all "int"), even if we changed those to "size_t" or
    +    "intmax_t" (not trivial, as we depend on them being negative in some
    +    places) the underlying "struct string_list"'s "nr" member is an
    +    "unsigned int", which would eventually overflow.
    +
    +    However the danger of that overflow isn't as great, as we were
    +    overflowing on "i + column_count * j" before this change, it'll
    +    require a much bigger range for us to have an integer overflow on the
    +    number of commits we're processing.
    +
    +    We're unlikely to encounter a 2-4 billion commit history on 32 bit
    +    platforms. Even if we did one of the types in the underlying object
    +    machinery would probably overflow before we overflowed here. So let's
    +    punt that for now. If we're ever going to solve that issue [1] to
    +    change the "struct string_list"'s "nr" member to a "size_t" might be a
    +    good start.
    +
    +    1. https://lore.kernel.org/git/RFC-patch-01.10-7c929096381-20211209T191653Z-avarab@gmail.com/
     
         Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
     
    @@ linear-assignment.c
      #include "linear-assignment.h"
      
     -#define COST(column, row) cost[(column) + column_count * (row)]
    -+static inline int cost_index(int *cost, int a, int b, int c)
    +-
    + static void columns_reduction(size_t column_count, size_t row_count,
    + 			      int *cost,
    + 			      int *column2row, int *row2column,
    +
    + ## linear-assignment.h ##
    +@@ linear-assignment.h: void compute_assignment(size_t column_count, size_t row_count,
    + 			int *cost,
    + 			int *column2row, int *row2column);
    + 
    ++/**
    ++ * Get an overflow-proof offset into the "cost" array.
    ++ */
    ++static inline size_t cost_offset(const size_t column,
    ++				 const size_t column_count, const size_t row)
     +{
    -+	int r;
    ++	const size_t a = st_mult(column_count, row);
    ++	const size_t b = st_add(column, a);
     +
    -+	r = b + a * c;
    -+
    -+	return r;
    ++	return b;
     +}
     +
    -+#define COST(column, row) cost[cost_index(cost, column_count, column, row)]
    ++/**
    ++ * Convenience macro for doing the cost[] lookup using cost_offset().
    ++ */
    ++#define COST(column, row) cost[cost_offset((column), (column_count), (row))]
    ++
    + /* The maximal cost in the cost matrix (to prevent integer overflows). */
    + #define COST_MAX (1<<16)
      
    - static void columns_reduction(size_t column_count, size_t row_count,
    - 			      int *cost,
    +
    + ## range-diff.c ##
    +@@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,
    + 				c = diffsize(a_util->diff, b_util->diff);
    + 			else
    + 				c = COST_MAX;
    +-			cost[i + column_count * j] = c;
    ++			COST(i, j) = c;
    + 		}
    + 
    + 		c = a_util->matching < 0 ?
    + 			a_util->diffsize * creation_factor / 100 : COST_MAX;
    + 		for (j = b->nr; j < column_count; j++)
    +-			cost[i + column_count * j] = c;
    ++			COST(i, j) = c;
    + 	}
    + 
    + 	for (j = 0; j < b->nr; j++) {
    +@@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,
    + 		c = util->matching < 0 ?
    + 			util->diffsize * creation_factor / 100 : COST_MAX;
    + 		for (i = a->nr; i < column_count; i++)
    +-			cost[i + column_count * j] = c;
    ++			COST(i, j) = c;
    + 	}
    + 
    + 	if (column_count > 1)
 8:  794d494bedd <  -:  ----------- linear-assignment.c: detect signed add/mul on GCC and Clang
 9:  2026b4bff90 <  -:  ----------- linear-assignment.c: add and use intprops.h from Gnulib
-- 
2.34.1.932.g36842105b61

[RFC PATCH v2 1/5] range-diff: zero out elements in "cost" first

[Ævar Arnfjörð Bjarmason]

Have the get_correspondences() function use CALLOC_ARRAY instead of
looping over the newly allocated "cost" to zero out some of its
elements.

The for-loop that zero'd out elements in "cost" wasn't the first loop
in that function, nor did it cover all of its elements, but regardless
of that this change doesn't affect its end-state. None of the
for-loops touched the same items in the array, so we could have (and
an earlier WIP version of this change did) moved the for-loop we're
deleting to come first in get_correspondences().

This can be seen from a careful reading of this code added in in
d9c66f0b5bf (range-diff: first rudimentary implementation,
2018-08-13) (as well as adding some printf-debugging) we'll set all
elements in the in the "n * n" allocated array. That's "n = A+B" where
"A" and "B" are the number of commits in our respective ranges.

So let's just allocate this with CALLOC_ARRAY(), and skip these two
for-loops. Furthermore let's remove the early exit condition from
compute_assignment() in favor of an assert that it must be called with
"column_count > 1", then "get_correspondences()" can skip calling it
when no further filling of the "a2b" and "b2a" arrays is needed.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c |  7 +------
 range-diff.c        | 13 +++++--------
 2 files changed, 6 insertions(+), 14 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index ecffc09be6e..0c0786a63b6 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -19,12 +19,7 @@ void compute_assignment(int column_count, int row_count, int *cost,
 	int *free_row, free_count = 0, saved_free_count, *pred, *col;
 	int i, j, phase;
 
-	if (column_count < 2) {
-		memset(column2row, 0, sizeof(int) * column_count);
-		memset(row2column, 0, sizeof(int) * row_count);
-		return;
-	}
-
+	assert(column_count > 1);
 	memset(column2row, -1, sizeof(int) * column_count);
 	memset(row2column, -1, sizeof(int) * row_count);
 	ALLOC_ARRAY(v, column_count);
diff --git a/range-diff.c b/range-diff.c
index cac89a2f4f2..b2fcc6f66e0 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -312,9 +312,9 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 	int *cost, c, *a2b, *b2a;
 	int i, j;
 
-	ALLOC_ARRAY(cost, st_mult(n, n));
-	ALLOC_ARRAY(a2b, n);
-	ALLOC_ARRAY(b2a, n);
+	CALLOC_ARRAY(cost, st_mult(n, n));
+	CALLOC_ARRAY(a2b, n);
+	CALLOC_ARRAY(b2a, n);
 
 	for (i = 0; i < a->nr; i++) {
 		struct patch_util *a_util = a->items[i].util;
@@ -346,11 +346,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 			cost[i + n * j] = c;
 	}
 
-	for (i = a->nr; i < n; i++)
-		for (j = b->nr; j < n; j++)
-			cost[i + n * j] = 0;
-
-	compute_assignment(n, n, cost, a2b, b2a);
+	if (n > 1)
+		compute_assignment(n, n, cost, a2b, b2a);
 
 	for (i = 0; i < a->nr; i++)
 		if (a2b[i] >= 0 && a2b[i] < b->nr) {
-- 
2.34.1.932.g36842105b61

Re: [RFC PATCH v2 1/5] range-diff: zero out elements in "cost" first

[Jeff King]

On Fri, Dec 10, 2021 at 01:30:38PM +0100, Ævar Arnfjörð Bjarmason wrote:

> Have the get_correspondences() function use CALLOC_ARRAY instead of
> looping over the newly allocated "cost" to zero out some of its
> elements.
> 
> The for-loop that zero'd out elements in "cost" wasn't the first loop
> in that function, nor did it cover all of its elements, but regardless
> of that this change doesn't affect its end-state. None of the
> for-loops touched the same items in the array, so we could have (and
> an earlier WIP version of this change did) moved the for-loop we're
> deleting to come first in get_correspondences().
> 
> This can be seen from a careful reading of this code added in in
> d9c66f0b5bf (range-diff: first rudimentary implementation,
> 2018-08-13) (as well as adding some printf-debugging) we'll set all
> elements in the in the "n * n" allocated array. That's "n = A+B" where
> "A" and "B" are the number of commits in our respective ranges.

It took me several readings to understand this argument. I think it's
just:

  When setting up the 2-dimensional "cost" array, we first fill in all
  rows 0..a->nr, and then all columns 0..b->nr. After that, we zero the
  rest of the array: slots which are both in rows greater than a->nr
  _and_ columns greater than b->nr.

  We can instead just zero everything from the start with
  CALLOC_ARRAY() and skip the final zero-ing.

I'm not necessarily asking for a re-roll with the message, but just
re-stating it to make sure I understand what's going on.

> So let's just allocate this with CALLOC_ARRAY(), and skip these two
> for-loops.

The first part tells us it's not wrong to do this change. But it doesn't
give us a "why". Is it just simpler code? We think it might be faster to
calloc than hand-rolling?

The "two for-loops" confused me for a minute. Really there are two
separate cases:

  - we can calloc the "cost" array and drop the final zero-ing loop in
    get_correspondences(), per the argument above

  - we can calloc the a2b and b2a arrays, which saves
    compute_assignment() from doing it itself later. Though this is a
    little weird, since it may zero them or it may set all entries to
    -1.

Given the large explanation needed for the first one (above), and then
this totally distinct explanation for the second one:

> Furthermore let's remove the early exit condition from
> compute_assignment() in favor of an assert that it must be called with
> "column_count > 1", then "get_correspondences()" can skip calling it
> when no further filling of the "a2b" and "b2a" arrays is needed.

...it kind of feels like they ought to be separate patches. At the very
least, it would be nice if the two cases were laid out more clearly at
the start of the commit message.

I do find the movement of this column_count check strange. It feels like
it's breaking the encapsulation of compute_assignment(); now its caller
knows more about when it might zero things and when it might do an
actual computation. And it makes things more complicated (we have a
conditional in the sole caller _and_ we have an assert to make sure the
caller checked that conditional).

But maybe this is really important for some later refactor. I'll keep
reading...

-Peff

[RFC PATCH v2 2/5] linear-assignment.c: split up compute_assignment() function

[Ævar Arnfjörð Bjarmason]

Split up the the long compute_assignment() function to make it easier
to reason about, particularly when it comes to what variables are used
later, and which aren't.

The grouping of "int" v.s. "int *" in function signatures is there to
make subsequent diffs smaller, if we're ever going to have a "nr"
member with a "size_t", but allocate e.g. "int *", and in anticipation
of the type names becoming longer than "int", which would require
re-wrapping.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c | 103 +++++++++++++++++++++++++++++++++-----------
 linear-assignment.h |   3 +-
 2 files changed, 79 insertions(+), 27 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index 0c0786a63b6..7f85745e541 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -8,21 +8,12 @@
 
 #define COST(column, row) cost[(column) + column_count * (row)]
 
-/*
- * The parameter `cost` is the cost matrix: the cost to assign column j to row
- * i is `cost[j + column_count * i].
- */
-void compute_assignment(int column_count, int row_count, int *cost,
-			int *column2row, int *row2column)
+static void columns_reduction(int column_count, int row_count,
+			      int *cost,
+			      int *column2row, int *row2column,
+			      int *v)
 {
-	int *v, *d;
-	int *free_row, free_count = 0, saved_free_count, *pred, *col;
-	int i, j, phase;
-
-	assert(column_count > 1);
-	memset(column2row, -1, sizeof(int) * column_count);
-	memset(row2column, -1, sizeof(int) * row_count);
-	ALLOC_ARRAY(v, column_count);
+	int i, j;
 
 	/* column reduction */
 	for (j = column_count - 1; j >= 0; j--) {
@@ -42,13 +33,21 @@ void compute_assignment(int column_count, int row_count, int *cost,
 			column2row[j] = -1;
 		}
 	}
+}
+
+static void reduction_transfer(int column_count, int row_count,
+			       int *cost,
+			       int *free_row, int *free_count,
+			       int *column2row, int *row2column,
+			       int *v)
+{
+	int i, j;
 
 	/* reduction transfer */
-	ALLOC_ARRAY(free_row, row_count);
 	for (i = 0; i < row_count; i++) {
 		int j1 = row2column[i];
 		if (j1 == -1)
-			free_row[free_count++] = i;
+			free_row[(*free_count)++] = i;
 		else if (j1 < -1)
 			row2column[i] = -2 - j1;
 		else {
@@ -59,21 +58,25 @@ void compute_assignment(int column_count, int row_count, int *cost,
 			v[j1] -= min;
 		}
 	}
+}
 
-	if (free_count ==
-	    (column_count < row_count ? row_count - column_count : 0)) {
-		free(v);
-		free(free_row);
-		return;
-	}
+static void augmenting_row_reduction(int column_count,
+				     int *cost,
+				     int *column2row, int *row2column,
+				     int *free_row, int *free_count, int *saved_free_count,
+				     int *v)
+{
+	int phase;
 
 	/* augmenting row reduction */
 	for (phase = 0; phase < 2; phase++) {
+		int i;
 		int k = 0;
 
-		saved_free_count = free_count;
-		free_count = 0;
-		while (k < saved_free_count) {
+		*saved_free_count = *free_count;
+		*free_count = 0;
+		while (k < *saved_free_count) {
+			int j;
 			int u1, u2;
 			int j1 = 0, j2, i0;
 
@@ -112,12 +115,24 @@ void compute_assignment(int column_count, int row_count, int *cost,
 				if (u1 < u2)
 					free_row[--k] = i0;
 				else
-					free_row[free_count++] = i0;
+					free_row[(*free_count)++] = i0;
 			}
 			row2column[i] = j1;
 			column2row[j1] = i;
 		}
 	}
+}
+
+static void augmentation(int column_count,
+			 int *cost,
+			 int *column2row, int *row2column,
+			 int *free_row, int free_count,
+			 int *v)
+{
+	int i, j;
+	int *d;
+	int *pred, *col;
+	int saved_free_count;
 
 	/* augmentation */
 	saved_free_count = free_count;
@@ -197,6 +212,42 @@ void compute_assignment(int column_count, int row_count, int *cost,
 	free(col);
 	free(pred);
 	free(d);
+}
+
+/*
+ * The parameter `cost` is the cost matrix: the cost to assign column j to row
+ * i is `cost[j + column_count * i].
+ */
+void compute_assignment(int column_count, int row_count,
+			int *cost,
+			int *column2row, int *row2column)
+{
+	int *v;
+	int *free_row, free_count = 0, saved_free_count;
+
+	assert(column_count > 1);
+	memset(column2row, -1, sizeof(int) * column_count);
+	memset(row2column, -1, sizeof(int) * row_count);
+	ALLOC_ARRAY(v, column_count);
+
+	columns_reduction(column_count, row_count, cost, column2row,
+			  row2column, v);
+
+	ALLOC_ARRAY(free_row, row_count);
+	reduction_transfer(column_count, row_count, cost, free_row,
+			   &free_count, column2row, row2column, v);
+	if (free_count ==
+	    (column_count < row_count ? row_count - column_count : 0))
+		goto cleanup;
+
+	augmenting_row_reduction(column_count, cost, column2row,
+				 row2column, free_row, &free_count,
+				 &saved_free_count,v);
+
+	augmentation(column_count, cost, column2row, row2column,
+		     free_row, free_count, v);
+
+cleanup:
 	free(v);
 	free(free_row);
 }
diff --git a/linear-assignment.h b/linear-assignment.h
index 1dfea766290..ef9946bdbfc 100644
--- a/linear-assignment.h
+++ b/linear-assignment.h
@@ -13,7 +13,8 @@
  * assignments (-1 for unassigned, which can happen only if column_count !=
  * row_count).
  */
-void compute_assignment(int column_count, int row_count, int *cost,
+void compute_assignment(int column_count, int row_count,
+			int *cost,
 			int *column2row, int *row2column);
 
 /* The maximal cost in the cost matrix (to prevent integer overflows). */
-- 
2.34.1.932.g36842105b61

Re: [RFC PATCH v2 2/5] linear-assignment.c: split up compute_assignment() function

[Jeff King]

On Fri, Dec 10, 2021 at 01:30:39PM +0100, Ævar Arnfjörð Bjarmason wrote:

> Split up the the long compute_assignment() function to make it easier
> to reason about, particularly when it comes to what variables are used
> later, and which aren't.

OK, this refactor seems reasonable. I don't know enough about the
linear-assignment algorithm to know whether the names you've picked are
meaningful.

> +void compute_assignment(int column_count, int row_count,
> +			int *cost,
> +			int *column2row, int *row2column)
> +{
> +	int *v;
> +	int *free_row, free_count = 0, saved_free_count;
> +
> +	assert(column_count > 1);
> +	memset(column2row, -1, sizeof(int) * column_count);
> +	memset(row2column, -1, sizeof(int) * row_count);
> +	ALLOC_ARRAY(v, column_count);

So this is the code where we would have kept the column_count check and
zero'd column2row and row2column, had we not moved it in the previous
commit. I actually think it would fit fine here in the refactored
compute_assignment() if you had left it.

-Peff

[RFC PATCH v2 3/5] linear-assignment.c: take "size_t", not "int" for *_count

[Ævar Arnfjörð Bjarmason]

Future-proof and clarify the compute_assignment() interface by having
it take a "size_t" for the count of its that it's processing. For the
content itself we need to be able to store a "-1", but there's no
reason we can't use a "size_t" for the size of the number of "int"'s
we've got.

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c | 10 +++++-----
 linear-assignment.h |  2 +-
 2 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index 7f85745e541..1f8329701a0 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -8,7 +8,7 @@
 
 #define COST(column, row) cost[(column) + column_count * (row)]
 
-static void columns_reduction(int column_count, int row_count,
+static void columns_reduction(size_t column_count, size_t row_count,
 			      int *cost,
 			      int *column2row, int *row2column,
 			      int *v)
@@ -35,7 +35,7 @@ static void columns_reduction(int column_count, int row_count,
 	}
 }
 
-static void reduction_transfer(int column_count, int row_count,
+static void reduction_transfer(size_t column_count, size_t row_count,
 			       int *cost,
 			       int *free_row, int *free_count,
 			       int *column2row, int *row2column,
@@ -60,7 +60,7 @@ static void reduction_transfer(int column_count, int row_count,
 	}
 }
 
-static void augmenting_row_reduction(int column_count,
+static void augmenting_row_reduction(size_t column_count,
 				     int *cost,
 				     int *column2row, int *row2column,
 				     int *free_row, int *free_count, int *saved_free_count,
@@ -123,7 +123,7 @@ static void augmenting_row_reduction(int column_count,
 	}
 }
 
-static void augmentation(int column_count,
+static void augmentation(size_t column_count,
 			 int *cost,
 			 int *column2row, int *row2column,
 			 int *free_row, int free_count,
@@ -218,7 +218,7 @@ static void augmentation(int column_count,
  * The parameter `cost` is the cost matrix: the cost to assign column j to row
  * i is `cost[j + column_count * i].
  */
-void compute_assignment(int column_count, int row_count,
+void compute_assignment(size_t column_count, size_t row_count,
 			int *cost,
 			int *column2row, int *row2column)
 {
diff --git a/linear-assignment.h b/linear-assignment.h
index ef9946bdbfc..9ff055baac1 100644
--- a/linear-assignment.h
+++ b/linear-assignment.h
@@ -13,7 +13,7 @@
  * assignments (-1 for unassigned, which can happen only if column_count !=
  * row_count).
  */
-void compute_assignment(int column_count, int row_count,
+void compute_assignment(size_t column_count, size_t row_count,
 			int *cost,
 			int *column2row, int *row2column);
 
-- 
2.34.1.932.g36842105b61

Re: [RFC PATCH v2 3/5] linear-assignment.c: take "size_t", not "int" for *_count

[Jeff King]

On Fri, Dec 10, 2021 at 01:30:40PM +0100, Ævar Arnfjörð Bjarmason wrote:

> Future-proof and clarify the compute_assignment() interface by having
> it take a "size_t" for the count of its that it's processing. For the
> content itself we need to be able to store a "-1", but there's no
> reason we can't use a "size_t" for the size of the number of "int"'s
> we've got.

Makes sense. I'm happy to see the counts dealt with independently here,
and the reasoning that we can use a straight size_t. The earlier
refactoring is paying off a bit, though I think it would be possible
without it.

-Peff

[RFC PATCH v2 4/5] range-diff.c: rename "n" to "column_count" in get_correspondences()

[Ævar Arnfjörð Bjarmason]

In preparation for using the COST macro in linear-assignment.c rename
the "n" variable, it assumes that the "n" in "a + n * b" is named
"column_count".

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 range-diff.c | 22 +++++++++++-----------
 1 file changed, 11 insertions(+), 11 deletions(-)

diff --git a/range-diff.c b/range-diff.c
index b2fcc6f66e0..b2e7db2c954 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -308,13 +308,13 @@ static int diffsize(const char *a, const char *b)
 static void get_correspondences(struct string_list *a, struct string_list *b,
 				int creation_factor)
 {
-	int n = a->nr + b->nr;
+	int column_count = st_add(a->nr, b->nr);
 	int *cost, c, *a2b, *b2a;
 	int i, j;
 
-	CALLOC_ARRAY(cost, st_mult(n, n));
-	CALLOC_ARRAY(a2b, n);
-	CALLOC_ARRAY(b2a, n);
+	CALLOC_ARRAY(cost, st_mult(column_count, column_count));
+	CALLOC_ARRAY(a2b, column_count);
+	CALLOC_ARRAY(b2a, column_count);
 
 	for (i = 0; i < a->nr; i++) {
 		struct patch_util *a_util = a->items[i].util;
@@ -328,13 +328,13 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 				c = diffsize(a_util->diff, b_util->diff);
 			else
 				c = COST_MAX;
-			cost[i + n * j] = c;
+			cost[i + column_count * j] = c;
 		}
 
 		c = a_util->matching < 0 ?
 			a_util->diffsize * creation_factor / 100 : COST_MAX;
-		for (j = b->nr; j < n; j++)
-			cost[i + n * j] = c;
+		for (j = b->nr; j < column_count; j++)
+			cost[i + column_count * j] = c;
 	}
 
 	for (j = 0; j < b->nr; j++) {
@@ -342,12 +342,12 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 
 		c = util->matching < 0 ?
 			util->diffsize * creation_factor / 100 : COST_MAX;
-		for (i = a->nr; i < n; i++)
-			cost[i + n * j] = c;
+		for (i = a->nr; i < column_count; i++)
+			cost[i + column_count * j] = c;
 	}
 
-	if (n > 1)
-		compute_assignment(n, n, cost, a2b, b2a);
+	if (column_count > 1)
+		compute_assignment(column_count, column_count, cost, a2b, b2a);
 
 	for (i = 0; i < a->nr; i++)
 		if (a2b[i] >= 0 && a2b[i] < b->nr) {
-- 
2.34.1.932.g36842105b61

Re: [RFC PATCH v2 4/5] range-diff.c: rename "n" to "column_count" in get_correspondences()

[Jeff King]

On Fri, Dec 10, 2021 at 01:30:41PM +0100, Ævar Arnfjörð Bjarmason wrote:

> In preparation for using the COST macro in linear-assignment.c rename
> the "n" variable, it assumes that the "n" in "a + n * b" is named
> "column_count".

OK, makes sense.

One funny thing:

> diff --git a/range-diff.c b/range-diff.c
> index b2fcc6f66e0..b2e7db2c954 100644
> --- a/range-diff.c
> +++ b/range-diff.c
> @@ -308,13 +308,13 @@ static int diffsize(const char *a, const char *b)
>  static void get_correspondences(struct string_list *a, struct string_list *b,
>  				int creation_factor)
>  {
> -	int n = a->nr + b->nr;
> +	int column_count = st_add(a->nr, b->nr);

Assigning the result of st_add() to an int nullifies the point of using
it in the first place. :)

I suspect this was a mistake from rebasing, and you meant only to change
the name here, and leave the st_add() for the next commit when the type
changes.

> [...]

The rest looks good.

-Peff

[RFC PATCH v2 5/5] range-diff: fix integer overflow & segfault on cost[i + n * j]

[Ævar Arnfjörð Bjarmason]

in preceding commits the "column_count" and the "int*"'s we malloc()
were changed to track their length with a size_t, so we're able to
track as many "cost" items as malloc() will give us.

But we'd still segfault on relatively large range comparisons,
e.g. this would segfault:

    git -P range-diff --creation-factor=50 origin/master...git-for-windows/main

The reason for that is that we'd still use integer types to compute an
array index into the "cost" array, which would overflow. The result of
a signed overflow in C is undefined, but on my system it'll result in
a negative number, and a prompt segfault as we'll try to access a
negative array index.

Luckily we used the COST() macro in linear-assignment.c already for
all of these lookups, and in a preceding commit we renamed "n" in
"range-diff.c"'s get_correspondences() to "column_count" in
preparation for using it here.

So let's use it for the three occurrences of "cost" indexing in
range-diff.c, and have the COST() macro itself do overflow checking
with st_mult() and st_add(). Due to the cast to "size_t" from "int"
we'll avoid the segfault, and will end up correctly pointing to the
relevant "int *".

It's not important that we use the new cost_offset() inline function
here, we could also use the st_*() macros inline. By using it we'll
get a more meaningful backtrace in a debugger to the relevant
addition/multiplication line if we end up calling die() here.

It's still possible for us to overflow even with this change, that's
because the iteration variables (such as "i" and "j" in this diff
context are all "int"), even if we changed those to "size_t" or
"intmax_t" (not trivial, as we depend on them being negative in some
places) the underlying "struct string_list"'s "nr" member is an
"unsigned int", which would eventually overflow.

However the danger of that overflow isn't as great, as we were
overflowing on "i + column_count * j" before this change, it'll
require a much bigger range for us to have an integer overflow on the
number of commits we're processing.

We're unlikely to encounter a 2-4 billion commit history on 32 bit
platforms. Even if we did one of the types in the underlying object
machinery would probably overflow before we overflowed here. So let's
punt that for now. If we're ever going to solve that issue [1] to
change the "struct string_list"'s "nr" member to a "size_t" might be a
good start.

1. https://lore.kernel.org/git/RFC-patch-01.10-7c929096381-20211209T191653Z-avarab@gmail.com/

Signed-off-by: Ævar Arnfjörð Bjarmason <avarab@gmail.com>
---
 linear-assignment.c |  2 --
 linear-assignment.h | 17 +++++++++++++++++
 range-diff.c        |  6 +++---
 3 files changed, 20 insertions(+), 5 deletions(-)

diff --git a/linear-assignment.c b/linear-assignment.c
index 1f8329701a0..88d15c2ad32 100644
--- a/linear-assignment.c
+++ b/linear-assignment.c
@@ -6,8 +6,6 @@
 #include "cache.h"
 #include "linear-assignment.h"
 
-#define COST(column, row) cost[(column) + column_count * (row)]
-
 static void columns_reduction(size_t column_count, size_t row_count,
 			      int *cost,
 			      int *column2row, int *row2column,
diff --git a/linear-assignment.h b/linear-assignment.h
index 9ff055baac1..5f8bcedc2c5 100644
--- a/linear-assignment.h
+++ b/linear-assignment.h
@@ -17,6 +17,23 @@ void compute_assignment(size_t column_count, size_t row_count,
 			int *cost,
 			int *column2row, int *row2column);
 
+/**
+ * Get an overflow-proof offset into the "cost" array.
+ */
+static inline size_t cost_offset(const size_t column,
+				 const size_t column_count, const size_t row)
+{
+	const size_t a = st_mult(column_count, row);
+	const size_t b = st_add(column, a);
+
+	return b;
+}
+
+/**
+ * Convenience macro for doing the cost[] lookup using cost_offset().
+ */
+#define COST(column, row) cost[cost_offset((column), (column_count), (row))]
+
 /* The maximal cost in the cost matrix (to prevent integer overflows). */
 #define COST_MAX (1<<16)
 
diff --git a/range-diff.c b/range-diff.c
index b2e7db2c954..b4f015213af 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -328,13 +328,13 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 				c = diffsize(a_util->diff, b_util->diff);
 			else
 				c = COST_MAX;
-			cost[i + column_count * j] = c;
+			COST(i, j) = c;
 		}
 
 		c = a_util->matching < 0 ?
 			a_util->diffsize * creation_factor / 100 : COST_MAX;
 		for (j = b->nr; j < column_count; j++)
-			cost[i + column_count * j] = c;
+			COST(i, j) = c;
 	}
 
 	for (j = 0; j < b->nr; j++) {
@@ -343,7 +343,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,
 		c = util->matching < 0 ?
 			util->diffsize * creation_factor / 100 : COST_MAX;
 		for (i = a->nr; i < column_count; i++)
-			cost[i + column_count * j] = c;
+			COST(i, j) = c;
 	}
 
 	if (column_count > 1)
-- 
2.34.1.932.g36842105b61

Re: [RFC PATCH v2 5/5] range-diff: fix integer overflow & segfault on cost[i + n * j]

[Jeff King]

On Fri, Dec 10, 2021 at 01:30:42PM +0100, Ævar Arnfjörð Bjarmason wrote:

> in preceding commits the "column_count" and the "int*"'s we malloc()
> were changed to track their length with a size_t, so we're able to
> track as many "cost" items as malloc() will give us.
> 
> But we'd still segfault on relatively large range comparisons,
> e.g. this would segfault:
> 
>     git -P range-diff --creation-factor=50 origin/master...git-for-windows/main
> 
> The reason for that is that we'd still use integer types to compute an
> array index into the "cost" array, which would overflow. The result of
> a signed overflow in C is undefined, but on my system it'll result in
> a negative number, and a prompt segfault as we'll try to access a
> negative array index.

Note that this isn't just access. We'll first write to cost[i + n * j]
to start. In practice because of the iteration, and signed overflow
being implemented as it usually is, we'd always first write a single int
that's 2GB before the array. And that should segfault.

I do wonder if this can be turned into a heap overflow exploit. I think
you'd probably need to manage to get 2GB on the heap to avoid an
immediate segfault.

> Luckily we used the COST() macro in linear-assignment.c already for
> all of these lookups, and in a preceding commit we renamed "n" in
> "range-diff.c"'s get_correspondences() to "column_count" in
> preparation for using it here.
> 
> So let's use it for the three occurrences of "cost" indexing in
> range-diff.c, and have the COST() macro itself do overflow checking
> with st_mult() and st_add(). Due to the cast to "size_t" from "int"
> we'll avoid the segfault, and will end up correctly pointing to the
> relevant "int *".

Is it actually necessary to do bounds checking here? If we know the
arrays are sized correctly, and we use an appropriate integer type,
wouldn't we know that our computations are always in bounds?

(I saw your other discussion of the unreliability of ssize_t; if we
don't want to assume it's of the same magnitude as size_t, then intmax_t
would work).

The reason I ask in particular is that I wonder if these non-intrinsic
st_* helpers might introduce a measurable slowdown. When I suggested
them earlier it was because I was also suggesting that we'd have done
all of our bounds-checks up front, during the allocation.

> It's still possible for us to overflow even with this change, that's
> because the iteration variables (such as "i" and "j" in this diff
> context are all "int"), even if we changed those to "size_t" or
> "intmax_t" (not trivial, as we depend on them being negative in some
> places) the underlying "struct string_list"'s "nr" member is an
> "unsigned int", which would eventually overflow.

The string_list overflow is something I do think we ought to fix. But we
know from past experiments that it can't actually cause a heap overflow.
Can overflowing one of the ints, though?

If we're computing i*n+j, and j goes negative, then cast to a size_t
that will turn into a big number. But depending how negative it is, it
might not overflow a size_t. But it would still be well outside the
bounds of the allocated array. E.g., consider code like this:

        int j = INT_MAX;
        while (1) {
                printf("int = %d\n", j);
                printf("size_t = %"PRIuMAX"\n", (uintmax_t)st_add(0, j));
                j++;
        }

which shows what happens when i=0, but j approaches overflow. We wrap to
-2^31, which is a large but representable size_t. So st_add() does not
trigger, but I think we'd still be out of bounds.

I suspect it's OK in practice from a security perspective, because it's
so far out of bounds as to cause a segfault and not any kind of heap
overflow. But it really feels like the fix is incomplete. Whereas using
the correct types avoids the segfault.

> We're unlikely to encounter a 2-4 billion commit history on 32 bit
> platforms. Even if we did one of the types in the underlying object
> machinery would probably overflow before we overflowed here. So let's
> punt that for now. If we're ever going to solve that issue [1] to
> change the "struct string_list"'s "nr" member to a "size_t" might be a
> good start.

I'm less concerned about "unlikely" and more about "what can bad actors
trigger". 2 billion is probably out of reach in practice though
(typically I've seen things get untenable around a few hundred million
objects total).

Still, it feels a bit hand-wavy.

-Peff

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Johannes Schindelin]

[-- Attachment #1: Type: text/plain, Size: 802 bytes --]

Hi Ævar,

On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:

> The difference between "master" and "git-for-windows/main" is large
> enough that comparing the two will segfault on my system. This is
> because the range-diff code does some expensive calculations and will
> overflow the "int" type.

You are holding this thing wrong.

The `main` branch of Git for Windows uses merging rebases, therefore you
need to use a commit range like
`git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and
compare it to `git-for-windows/main..master`.

Failing that, you will receive only bogus results.

As to the patch series, it likely does the wrong thing. Just like we error
out on insanely large input in libxdiff, `range-diff` should do the same.

Ciao,
Johannes

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Ævar Arnfjörð Bjarmason]

On Fri, Dec 10 2021, Johannes Schindelin wrote:

> Hi Ævar,
>
> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:
>
>> The difference between "master" and "git-for-windows/main" is large
>> enough that comparing the two will segfault on my system. This is
>> because the range-diff code does some expensive calculations and will
>> overflow the "int" type.
>
> You are holding this thing wrong.
>
> The `main` branch of Git for Windows uses merging rebases, therefore you
> need to use a commit range like
> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and
> compare it to `git-for-windows/main..master`.
>
> Failing that, you will receive only bogus results.

Indeed. FWIW I got this segfault on an actual local range-diff that's
useful for a very large range & started digging.

I then tried to come up with some arbitrary command someone with a
git.git clone might be able to run that would reproduce it without
having to tell them to clone chromium.git or <other very large repo>.

> As to the patch series, it likely does the wrong thing. Just like we error
> out on insanely large input in libxdiff, `range-diff` should do the same.

I haven't come up with an actual use-case for diffing something large
(maybe someone storing DNA sequences as text would?), but have run into
practical cases where range-diff would be useful on range where it
currently segfaults. E.g. repos that get 500-1000 commits/day someone
cherry-picks commits between branches & rewords/adjusts, and you're
trying to range-diff it 2 months later looking for differences...

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Philip Oakley]

Sorry for the late comment..

On 10/12/2021 14:31, Johannes Schindelin wrote:
> Hi Ævar,
>
> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:
>
>> The difference between "master" and "git-for-windows/main" is large
>> enough that comparing the two will segfault on my system. This is
>> because the range-diff code does some expensive calculations and will
>> overflow the "int" type.
> You are holding this thing wrong.
>
> The `main` branch of Git for Windows uses merging rebases, therefore you
> need to use a commit range like
> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and
> compare it to `git-for-windows/main..master`.

I'm not sure that a Git repo has an established way of indicating to how
it's branching/merging/releasing workflow is set up, especially for
projects with non-normative use cases, such as Git for Windows. We don't
have a git document for covering  the different workflows in common use
for easy reference and consistent terminology.

The merging rebase flow, with 'fake' merge does solve a problem that
git.git doesn't have but could easily be a common process for 'friendly
forks' that follow an upstream with local patches. The choice of
'{/^Start.the.merging}' is currently specific to the Git-for-Windows
case making it harder to discover this useful maintainer method.

I fully agree that the range-diff should probably have a patch limit at
some sensible value.

The 'confusion' between the types size_t, long and int, does ripple
through a lot of portable code, as shown in the series. Not an easy problem.

>
> Failing that, you will receive only bogus results.
>
> As to the patch series, it likely does the wrong thing. Just like we error
> out on insanely large input in libxdiff, `range-diff` should do the same.
>
> Ciao,
> Johannes
--
Philip

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Ævar Arnfjörð Bjarmason]

On Tue, Dec 21 2021, Philip Oakley wrote:

> Sorry for the late comment..
>
> On 10/12/2021 14:31, Johannes Schindelin wrote:
>> Hi Ævar,
>>
>> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:
>>
>>> The difference between "master" and "git-for-windows/main" is large
>>> enough that comparing the two will segfault on my system. This is
>>> because the range-diff code does some expensive calculations and will
>>> overflow the "int" type.
>> You are holding this thing wrong.
>>
>> The `main` branch of Git for Windows uses merging rebases, therefore you
>> need to use a commit range like
>> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and
>> compare it to `git-for-windows/main..master`.
>
> I'm not sure that a Git repo has an established way of indicating to how
> it's branching/merging/releasing workflow is set up, especially for
> projects with non-normative use cases, such as Git for Windows. We don't
> have a git document for covering  the different workflows in common use
> for easy reference and consistent terminology.
>
> The merging rebase flow, with 'fake' merge does solve a problem that
> git.git doesn't have but could easily be a common process for 'friendly
> forks' that follow an upstream with local patches. The choice of
> '{/^Start.the.merging}' is currently specific to the Git-for-Windows
> case making it harder to discover this useful maintainer method.

Yes, but let's not get lost in the weeds here. As I noted I just picked
GFW as a handy example of a large history & that command as a handy
example of something that segfaults on "master".

So the point really isn't to say that we should fix range-diff becase
it'll allow us to run this practically useful command on a git.git fork.

> I fully agree that the range-diff should probably have a patch limit at
> some sensible value.

Why would it? If I'm willing to spend the CPU to produce a range-diff of
an absurdly large range and I've got the memory why shouldn't we support
it?

We don't in cases like xdiff where it's not trivial to just raise the
limits, but here it seems relatively easy.

I think limits to save users from spending CPU time they didn't expect
are reasonable, but then we can handle them like the diff/merge rename
detection limits, i.e. print a warning/advice, and allow the user to
opt-out.

That also doesn't really apply here since "diff/merge" will/might still
do something useful in those scenarios, whereas range-diff would just
have truncated output.

> The 'confusion' between the types size_t, long and int, does ripple
> through a lot of portable code, as shown in the series. Not an easy problem.

Yes, although here we're not just casting and overflowing types, but
overflowing on multiplication and addition, whereas usually we'd just
overflow on "nr" being too big for "int" or similar.

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Johannes Schindelin]

[-- Attachment #1: Type: text/plain, Size: 1311 bytes --]

Hi Ævar,

On Wed, 22 Dec 2021, Ævar Arnfjörð Bjarmason wrote:

> On Tue, Dec 21 2021, Philip Oakley wrote:
>
> > I fully agree that the range-diff should probably have a patch limit at
> > some sensible value.
>
> Why would it? If I'm willing to spend the CPU to produce a range-diff of
> an absurdly large range and I've got the memory why shouldn't we support
> it?
>
> We don't in cases like xdiff where it's not trivial to just raise the
> limits, but here it seems relatively easy.

To raise the limits you would have to understand the purpose of the
calculations so that you can understand the range their data type needs to
handle. The weights of the Hungarian Algorithm are distinctly _not_
pointers, therefore using `size_t` is most likely the wrong thing to do.

Of course you can glance over the details and try to avoid digging into
the algorithm to understand what it does before changing the data types
and introducing `st_mult()`-like functions and macros, but that only makes
it "relatively easy", at the price of "maybe incorrect". That would be in
line with what I unfortunately have had to come to expect of your patches.

The _actual_ "relatively easy" way is to imitate the limits we use in
xdiff (for similar reasons). As I said before.

Ciao,
Johannes

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Jeff King]

On Wed, Dec 22, 2021 at 09:50:50PM +0100, Johannes Schindelin wrote:

> To raise the limits you would have to understand the purpose of the
> calculations so that you can understand the range their data type needs to
> handle. The weights of the Hungarian Algorithm are distinctly _not_
> pointers, therefore using `size_t` is most likely the wrong thing to do.
> 
> Of course you can glance over the details and try to avoid digging into
> the algorithm to understand what it does before changing the data types
> and introducing `st_mult()`-like functions and macros, but that only makes
> it "relatively easy", at the price of "maybe incorrect". That would be in
> line with what I unfortunately have had to come to expect of your patches.

:( Whether you're frustrated with this topic or not, can we please stick
to technical critiques? Either proposed changes are the right thing or
not, and we can talk about that.

I know it can get hard if the review is "gee, it looks like this is
going in the wrong direction, but I don't have time to dig in and tell
you _exactly_ how it is wrong right now". And I think that is an OK
thing to express, but your response here has a bit more bite to it than
I think is strictly necessary.

> The _actual_ "relatively easy" way is to imitate the limits we use in
> xdiff (for similar reasons). As I said before.

I had a similar thought at first, too. But because one of the array
sizes we compute is (nr_a + nr_b)^2, I fear the limits end up pretty low
(e.g., my 32767 by 32767 example). That's a pretty big range diff, but
it doesn't seem like an outrageous input to throw at the system
(especially if most of the entries end up finding a match and showing
one line of equality).

It may be that there are multiple limits to consider, though. E.g., the
square of the sum of the sides, as above, is one. But there may be some
benefit to making that work (by using size_t and st_add) but putting a
hard limit like 2^30 on the number of commits on one side (e.g., for
ranking scores). And that's where understanding exactly what the
algorithm is doing becomes necessary.

-Peff

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Philip Oakley]

On 21/12/2021 23:36, Ævar Arnfjörð Bjarmason wrote:
> On Tue, Dec 21 2021, Philip Oakley wrote:
>
>> Sorry for the late comment..
>>
>> On 10/12/2021 14:31, Johannes Schindelin wrote:
>>> Hi Ævar,
>>>
>>> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:
>>>
>>>> The difference between "master" and "git-for-windows/main" is large
>>>> enough that comparing the two will segfault on my system. This is
>>>> because the range-diff code does some expensive calculations and will
>>>> overflow the "int" type.
>>> You are holding this thing wrong.
>>>
>>> The `main` branch of Git for Windows uses merging rebases, therefore you
>>> need to use a commit range like
>>> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and
>>> compare it to `git-for-windows/main..master`.
>> I'm not sure that a Git repo has an established way of indicating to how
>> it's branching/merging/releasing workflow is set up, especially for
>> projects with non-normative use cases, such as Git for Windows. We don't
>> have a git document for covering  the different workflows in common use
>> for easy reference and consistent terminology.
>>
>> The merging rebase flow, with 'fake' merge does solve a problem that
>> git.git doesn't have but could easily be a common process for 'friendly
>> forks' that follow an upstream with local patches. The choice of
>> '{/^Start.the.merging}' is currently specific to the Git-for-Windows
>> case making it harder to discover this useful maintainer method.
> Yes, but let's not get lost in the weeds here. As I noted I just picked
> GFW as a handy example of a large history & that command as a handy
> example of something that segfaults on "master".

Had you already experienced the segfault locally, without using the GFW
example? How many commits were present in that case?

The GFW example seems like it's taken the discussion in the wrong direction.

For me:
$ git log git/master..origin/main --pretty=oneline | wc -l
62105

That's a lot of commits to have in a range diff. It's almost as big as
the whole of git/master

$ git log git/master --pretty=oneline | wc -l
65400

Personally I'd like a way of trimming 'deadheads' that's a bit easier
that needing to remember Dscho's magic string [1], but time will tell.
> So the point really isn't to say that we should fix range-diff becase
> it'll allow us to run this practically useful command on a git.git fork.
>
>> I fully agree that the range-diff should probably have a patch limit at
>> some sensible value.
> Why would it? If I'm willing to spend the CPU to produce a range-diff of
> an absurdly large range and I've got the memory why shouldn't we support
> it?

There will always be a limit somewhere, and if it's not commit count or
other easily explained & checked limit it will be hard to rationalise
about why Git suddenly fails with an error (or segfault) in those
humungous case.
>
> We don't in cases like xdiff where it's not trivial to just raise the
> limits, but here it seems relatively easy.
>
> I think limits to save users from spending CPU time they didn't expect
> are reasonable, but then we can handle them like the diff/merge rename
> detection limits, i.e. print a warning/advice, and allow the user to
> opt-out.
>
> That also doesn't really apply here since "diff/merge" will/might still
> do something useful in those scenarios, whereas range-diff would just
> have truncated output.
>
>> The 'confusion' between the types size_t, long and int, does ripple
>> through a lot of portable code, as shown in the series. Not an easy problem.
> Yes, although here we're not just casting and overflowing types, but
> overflowing on multiplication and addition, whereas usually we'd just
> overflow on "nr" being too big for "int" or similar.
I've been very slowly looking at the `long` limits on GFW which have
very similar arithmetic issues for pointers, often with no clear answers.

--

Wishing you all the best for Christmas.
Philip

[1]
https://lore.kernel.org/git/01fe28d8-2887-bc42-c91b-c3237b5186a7@iee.email/

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Ævar Arnfjörð Bjarmason]

On Fri, Dec 24 2021, Philip Oakley wrote:

> On 21/12/2021 23:36, Ævar Arnfjörð Bjarmason wrote:
>> On Tue, Dec 21 2021, Philip Oakley wrote:
>>
>>> Sorry for the late comment..
>>>
>>> On 10/12/2021 14:31, Johannes Schindelin wrote:
>>>> Hi Ævar,
>>>>
>>>> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:
>>>>
>>>>> The difference between "master" and "git-for-windows/main" is large
>>>>> enough that comparing the two will segfault on my system. This is
>>>>> because the range-diff code does some expensive calculations and will
>>>>> overflow the "int" type.
>>>> You are holding this thing wrong.
>>>>
>>>> The `main` branch of Git for Windows uses merging rebases, therefore you
>>>> need to use a commit range like
>>>> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and
>>>> compare it to `git-for-windows/main..master`.
>>> I'm not sure that a Git repo has an established way of indicating to how
>>> it's branching/merging/releasing workflow is set up, especially for
>>> projects with non-normative use cases, such as Git for Windows. We don't
>>> have a git document for covering  the different workflows in common use
>>> for easy reference and consistent terminology.
>>>
>>> The merging rebase flow, with 'fake' merge does solve a problem that
>>> git.git doesn't have but could easily be a common process for 'friendly
>>> forks' that follow an upstream with local patches. The choice of
>>> '{/^Start.the.merging}' is currently specific to the Git-for-Windows
>>> case making it harder to discover this useful maintainer method.
>> Yes, but let's not get lost in the weeds here. As I noted I just picked
>> GFW as a handy example of a large history & that command as a handy
>> example of something that segfaults on "master".
>
> Had you already experienced the segfault locally, without using the GFW
> example? How many commits were present in that case?

Yes, I ran into it "orginally" just range-diffing as part of a local
build process.

I could dig up what revision range it was exactly, but does it matter?

> The GFW example seems like it's taken the discussion in the wrong direction.
>
> For me:
> $ git log git/master..origin/main --pretty=oneline | wc -l
> 62105
>
> That's a lot of commits to have in a range diff. It's almost as big as
> the whole of git/master
>
> $ git log git/master --pretty=oneline | wc -l
> 65400
>
> Personally I'd like a way of trimming 'deadheads' that's a bit easier
> that needing to remember Dscho's magic string [1], but time will tell.

There are some repos that move forward by 500-1k commits/day, and people
do cherry-pick patches etc. So wanting to range-diff after a couple of
months is something you might do...

>> So the point really isn't to say that we should fix range-diff becase
>> it'll allow us to run this practically useful command on a git.git fork.
>>
>>> I fully agree that the range-diff should probably have a patch limit at
>>> some sensible value.
>> Why would it? If I'm willing to spend the CPU to produce a range-diff of
>> an absurdly large range and I've got the memory why shouldn't we support
>> it?
>
> There will always be a limit somewhere, and if it's not commit count or
> other easily explained & checked limit it will be hard to rationalise
> about why Git suddenly fails with an error (or segfault) in those
> humungous case.

I think it's fairly easy to explain the "your system wouldn't let us
malloc more, we're dying" that we get from xmalloc(), st_*() and the
like.

>>
>> We don't in cases like xdiff where it's not trivial to just raise the
>> limits, but here it seems relatively easy.
>>
>> I think limits to save users from spending CPU time they didn't expect
>> are reasonable, but then we can handle them like the diff/merge rename
>> detection limits, i.e. print a warning/advice, and allow the user to
>> opt-out.
>>
>> That also doesn't really apply here since "diff/merge" will/might still
>> do something useful in those scenarios, whereas range-diff would just
>> have truncated output.
>>
>>> The 'confusion' between the types size_t, long and int, does ripple
>>> through a lot of portable code, as shown in the series. Not an easy problem.
>> Yes, although here we're not just casting and overflowing types, but
>> overflowing on multiplication and addition, whereas usually we'd just
>> overflow on "nr" being too big for "int" or similar.
> I've been very slowly looking at the `long` limits on GFW which have
> very similar arithmetic issues for pointers, often with no clear answers.

Right, that's to do with the whole "long" or whatever use in the
object.c and related code, but I don't think that's applicable here, is
it?

Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow

[Philip Oakley]

On 24/12/2021 16:46, Ævar Arnfjörð Bjarmason wrote:
> On Fri, Dec 24 2021, Philip Oakley wrote:
>
>> On 21/12/2021 23:36, Ævar Arnfjörð Bjarmason wrote:
>>> On Tue, Dec 21 2021, Philip Oakley wrote:
>>>
>>>> Sorry for the late comment..
>>>>
>>>> On 10/12/2021 14:31, Johannes Schindelin wrote:
>>>>> Hi Ævar,
>>>>>
>>>>> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:
>>>>>
>>>>>> The difference between "master" and "git-for-windows/main" is large
>>>>>> enough that comparing the two will segfault on my system. This is
>>>>>> because the range-diff code does some expensive calculations and will
>>>>>> overflow the "int" type.
>>>>> You are holding this thing wrong.
>>>>>
>>>>> The `main` branch of Git for Windows uses merging rebases, therefore you
>>>>> need to use a commit range like
>>>>> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and
>>>>> compare it to `git-for-windows/main..master`.
>>>> I'm not sure that a Git repo has an established way of indicating to how
>>>> it's branching/merging/releasing workflow is set up, especially for
>>>> projects with non-normative use cases, such as Git for Windows. We don't
>>>> have a git document for covering  the different workflows in common use
>>>> for easy reference and consistent terminology.
>>>>
>>>> The merging rebase flow, with 'fake' merge does solve a problem that
>>>> git.git doesn't have but could easily be a common process for 'friendly
>>>> forks' that follow an upstream with local patches. The choice of
>>>> '{/^Start.the.merging}' is currently specific to the Git-for-Windows
>>>> case making it harder to discover this useful maintainer method.
>>> Yes, but let's not get lost in the weeds here. As I noted I just picked
>>> GFW as a handy example of a large history & that command as a handy
>>> example of something that segfaults on "master".
>> Had you already experienced the segfault locally, without using the GFW
>> example? How many commits were present in that case?
> Yes, I ran into it "orginally" just range-diffing as part of a local
> build process.
>
> I could dig up what revision range it was exactly, but does it matter?
No the particular range-diff doesn't matter, I was checking that this
wasn't a confusion about the Git for Windows workflow.

>
>> The GFW example seems like it's taken the discussion in the wrong direction.
>>
>> For me:
>> $ git log git/master..origin/main --pretty=oneline | wc -l
>> 62105
>>
>> That's a lot of commits to have in a range diff. It's almost as big as
>> the whole of git/master
>>
>> $ git log git/master --pretty=oneline | wc -l
>> 65400
>>
>> Personally I'd like a way of trimming 'deadheads' that's a bit easier
>> that needing to remember Dscho's magic string [1], but time will tell.
> There are some repos that move forward by 500-1k commits/day, and people
> do cherry-pick patches etc. So wanting to range-diff after a couple of
> months is something you might do...

It feels to me that in such cases that maybe the algorithm may need
tweaking for the needle in a haystack case ;-)
>
>>> So the point really isn't to say that we should fix range-diff becase
>>> it'll allow us to run this practically useful command on a git.git fork.
>>>
>>>> I fully agree that the range-diff should probably have a patch limit at
>>>> some sensible value.
>>> Why would it? If I'm willing to spend the CPU to produce a range-diff of
>>> an absurdly large range and I've got the memory why shouldn't we support
>>> it?
>> There will always be a limit somewhere, and if it's not commit count or
>> other easily explained & checked limit it will be hard to rationalise
>> about why Git suddenly fails with an error (or segfault) in those
>> humungous case.
> I think it's fairly easy to explain the "your system wouldn't let us
> malloc more, we're dying" that we get from xmalloc(), st_*() and the
> like.
That's better than a segfault, but does it give actionable information
to the user as to what (& how much) they should do? Hence the comment
about a commit count measure.

>>> We don't in cases like xdiff where it's not trivial to just raise the
>>> limits, but here it seems relatively easy.
>>>
>>> I think limits to save users from spending CPU time they didn't expect
>>> are reasonable, but then we can handle them like the diff/merge rename
>>> detection limits, i.e. print a warning/advice, and allow the user to
>>> opt-out.
>>>
>>> That also doesn't really apply here since "diff/merge" will/might still
>>> do something useful in those scenarios, whereas range-diff would just
>>> have truncated output.
>>>
>>>> The 'confusion' between the types size_t, long and int, does ripple
>>>> through a lot of portable code, as shown in the series. Not an easy problem.
>>> Yes, although here we're not just casting and overflowing types, but
>>> overflowing on multiplication and addition, whereas usually we'd just
>>> overflow on "nr" being too big for "int" or similar.
>> I've been very slowly looking at the `long` limits on GFW which have
>> very similar arithmetic issues for pointers, often with no clear answers.
> Right, that's to do with the whole "long" or whatever use in the
> object.c and related code, but I don't think that's applicable here, is
> it?

That question was more about the policy aspects of ensuring that any
proposals aren't 'head against a brick wall' when it comes to the
potential intrusiveness.

Thanks for the clarifications.

Philip