{"thread":{"id":"57059","subject":"[RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","startedAt":"2021-12-09T19:19:33Z","lastAt":"2021-12-24T18:31:55Z","messageCount":44,"participants":["Ævar Arnfjörð Bjarmason","Jeff King","Johannes Schindelin","Phillip Wood","Philip Oakley"],"isPatch":true,"patchVersion":1,"patchTotal":10},"messages":[{"id":"443671","messageId":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":null,"subject":"[RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:17Z","receivedAt":"2021-12-09T19:19:33Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"The difference between \"master\" and \"git-for-windows/main\" is large\nenough that comparing the two will segfault on my system. This is\nbecause the range-diff code does some expensive calculations and will\noverflow the \"int\" type.\n\nFixing this wasn't trivial, our st_*() macros only work for unsigned\ntypes, but as signed overflow is undefined in C detecting it is a lot\nmore painful. The range-diff code needs to store -1 in various places\n(not inherently, but changing that looked a lot more painful).\n\nFurthermore even if the range-diff.c and linear-assignment.c code were\nfixed we'd still segfault due to the used string-list.c code using an\n\"int\" type. Or rather, we tracked its \"unsigned int\" with an \"int\". If\nwe used \"unsigned\" we won't segfault on master..git-for-windows/main,\nbut we would soon enough on slightly larger divergent history.\n\nThis series changes the relevant APIs to use size_t where possible,\nbut as noted we need to use a signed type for range-diff.c. That's now\nintmax_t.\n\nWe detect signed overflow first 8/10 with a GCC and Clang-specific\n__builtin*() function, and then in the subsequent commit portably by\nimporting intprops.h from Gnulib.\n\nPerhaps there's an easier way to do this, but this works for me, and\nusing the portable intprops.h (see its source for all the hard-won\nlessons encdoded therein) seems like a good way forward. It *is*\nslightly slower than our current unsigned-only detection, but as\ndiscussed in 09/10 we should probably just switch to it anyway. This\nseries does not make that switch.\n\nWe still have various st_*() calls in the codebase where we use signed\ntypes, presumably this is as broken as the not-really-working\ndetection discussed in 02/10, but I didn't looki into those in any\ndetail.\n\nThis is an RFC because there's some rather painful merge conflicts\nin-flight due to the changeover from \"unsigned int nr\" to \"size_t nr\"\nin the string-list.h API. There's also a CI failure on 32 bit linux\ndue to a format in 03/10, but it's an easily fixable bug.\n\nAnd more generally it's an RFC perhaps this direction is a good one\nfor fixing that and any similar segfauls we have, and maybe it\nisn't. I'm not all that sure about it, but this seems to work, and\ncertainly beats segfaulting...\n\nÆvar Arnfjörð Bjarmason (10):\n string-list API: change \"nr\" and \"alloc\" to \"size_t\"\n range-diff.c: don't use st_mult() for signed \"int\"\n range-diff.c: use \"size_t\" to refer to \"struct string_list\"'s \"nr\"\n range-diff: zero out elements in \"cost\" first\n linear-assignment.c: split up compute_assignment() function\n linear-assignment.c: take \"size_t\", not \"int\" for *_count\n linear-assignment.c: convert a macro to a \"static inline\" function\n linear-assignment.c: detect signed add/mul on GCC and Clang\n linear-assignment.c: add and use intprops.h from Gnulib\n linear-assignment.c: use \"intmax_t\" instead of \"int\"\n\n builtin/receive-pack.c | 6 +-\n builtin/shortlog.c | 8 +-\n bundle.c | 4 +-\n commit-graph.c | 4 +-\n compat/gnulib/.gitattributes | 1 +\n compat/gnulib/intprops.h | 637 +++++++++++++++++++++++++++++++++++\n linear-assignment.c | 149 +++++---\n linear-assignment.h | 9 +-\n mailmap.c | 4 +-\n merge-ort.c | 2 +-\n range-diff.c | 32 +-\n string-list.h | 2 +-\n t/helper/test-run-command.c | 4 +-\n wt-status.c | 8 +-\n 14 files changed, 781 insertions(+), 89 deletions(-)\n create mode 100644 compat/gnulib/.gitattributes\n create mode 100644 compat/gnulib/intprops.h\n\n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443672","messageId":"RFC-patch-01.10-7c929096381-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 01/10] string-list API: change \"nr\" and \"alloc\" to \"size_t\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:18Z","receivedAt":"2021-12-09T19:19:37Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"As with the recent change to the \"struct strvec\" let's change \"struct\nstring_list\"'s \"alloc\" and \"nr\" to be a \"size_t\" as well. This will be\nused to fix an overflow in range-diff.c. See 8d133a4653a (strvec: use\nsize_t to store nr and alloc, 2021-09-11) for the recent change to\n\"struct strvec\".\n\nAs with the \"struct strvec\" change I think it would make sense to go\nthrough the users of the current \"unsigned int\" field and change\nanyone copying it to an \"int\" or \"unsigned int\" to \"size_t\", but as\nseen in [1] others disagree, so let's only change the things the\ncompiler complains about here.\n\n1. https://lore.kernel.org/git/87mtog4pai.fsf@evledraar.gmail.com/\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n builtin/receive-pack.c | 6 +++---\n builtin/shortlog.c | 8 ++++----\n bundle.c | 4 ++--\n commit-graph.c | 4 ++--\n mailmap.c | 4 ++--\n merge-ort.c | 2 +-\n string-list.h | 2 +-\n t/helper/test-run-command.c | 4 ++--\n wt-status.c | 8 ++++----\n 9 files changed, 21 insertions(+), 21 deletions(-)\n\ndiff --git a/builtin/receive-pack.c b/builtin/receive-pack.c\nindex 49b846d9605..4c681a64784 100644\n--- a/builtin/receive-pack.c\n+++ b/builtin/receive-pack.c\n@@ -827,12 +827,12 @@ static int run_and_feed_hook(const char *hook_name, feed_fn feed,\n \tproc.trace2_hook_name = hook_name;\n \n \tif (feed_state->push_options) {\n-\t\tint i;\n+\t\tsize_t i;\n \t\tfor (i = 0; i < feed_state->push_options->nr; i++)\n \t\t\tstrvec_pushf(&proc.env_array,\n-\t\t\t\t \"GIT_PUSH_OPTION_%d=%s\", i,\n+\t\t\t\t \"GIT_PUSH_OPTION_%\"PRIuMAX\"=%s\", i,\n \t\t\t\t feed_state->push_options->items[i].string);\n-\t\tstrvec_pushf(&proc.env_array, \"GIT_PUSH_OPTION_COUNT=%d\",\n+\t\tstrvec_pushf(&proc.env_array, \"GIT_PUSH_OPTION_COUNT=%\"PRIuMAX\"\",\n \t\t\t feed_state->push_options->nr);\n \t} else\n \t\tstrvec_pushf(&proc.env_array, \"GIT_PUSH_OPTION_COUNT\");\ndiff --git a/builtin/shortlog.c b/builtin/shortlog.c\nindex e7f7af5de3f..32c457956c7 100644\n--- a/builtin/shortlog.c\n+++ b/builtin/shortlog.c\n@@ -434,7 +434,7 @@ static void add_wrapped_shortlog_msg(struct strbuf *sb, const char *s,\n \n void shortlog_output(struct shortlog *log)\n {\n-\tint i, j;\n+\tsize_t i, j;\n \tstruct strbuf sb = STRBUF_INIT;\n \n \tif (log->sort_by_number)\n@@ -447,10 +447,10 @@ void shortlog_output(struct shortlog *log)\n \t\t\t\t(int)UTIL_TO_INT(item), item->string);\n \t\t} else {\n \t\t\tstruct string_list *onelines = item->util;\n-\t\t\tfprintf(log->file, \"%s (%d):\\n\",\n+\t\t\tfprintf(log->file, \"%s (%\"PRIuMAX\"):\\n\",\n \t\t\t\titem->string, onelines->nr);\n-\t\t\tfor (j = onelines->nr - 1; j >= 0; j--) {\n-\t\t\t\tconst char *msg = onelines->items[j].string;\n+\t\t\tfor (j = onelines->nr; j >= 1; j--) {\n+\t\t\t\tconst char *msg = onelines->items[j - 1].string;\n \n \t\t\t\tif (log->wrap_lines) {\n \t\t\t\t\tstrbuf_reset(&sb);\ndiff --git a/bundle.c b/bundle.c\nindex a0bb687b0f4..54dff6d9960 100644\n--- a/bundle.c\n+++ b/bundle.c\n@@ -255,7 +255,7 @@ int verify_bundle(struct repository *r,\n \n \t\tr = &header->references;\n \t\tprintf_ln(Q_(\"The bundle contains this ref:\",\n-\t\t\t \"The bundle contains these %d refs:\",\n+\t\t\t \"The bundle contains these %\"PRIuMAX\" refs:\",\n \t\t\t r->nr),\n \t\t\t r->nr);\n \t\tlist_refs(r, 0, NULL);\n@@ -264,7 +264,7 @@ int verify_bundle(struct repository *r,\n \t\t\tprintf_ln(_(\"The bundle records a complete history.\"));\n \t\t} else {\n \t\t\tprintf_ln(Q_(\"The bundle requires this ref:\",\n-\t\t\t\t \"The bundle requires these %d refs:\",\n+\t\t\t\t \"The bundle requires these %\"PRIuMAX\" refs:\",\n \t\t\t\t r->nr),\n \t\t\t\t r->nr);\n \t\t\tlist_refs(r, 0, NULL);\ndiff --git a/commit-graph.c b/commit-graph.c\nindex 2706683acfe..88a7621f2f7 100644\n--- a/commit-graph.c\n+++ b/commit-graph.c\n@@ -1687,8 +1687,8 @@ static int fill_oids_from_packs(struct write_commit_graph_context *ctx,\n \tdirlen = packname.len;\n \tif (ctx->report_progress) {\n \t\tstrbuf_addf(&progress_title,\n-\t\t\t Q_(\"Finding commits for commit graph in %d pack\",\n-\t\t\t \"Finding commits for commit graph in %d packs\",\n+\t\t\t Q_(\"Finding commits for commit graph in %\"PRIuMAX\" pack\",\n+\t\t\t \"Finding commits for commit graph in %\"PRIuMAX\" packs\",\n \t\t\t pack_indexes->nr),\n \t\t\t pack_indexes->nr);\n \t\tctx->progress = start_delayed_progress(progress_title.buf, 0);\ndiff --git a/mailmap.c b/mailmap.c\nindex 40ce152024d..9ce15a9e2fd 100644\n--- a/mailmap.c\n+++ b/mailmap.c\n@@ -43,7 +43,7 @@ static void free_mailmap_info(void *p, const char *s)\n static void free_mailmap_entry(void *p, const char *s)\n {\n \tstruct mailmap_entry *me = (struct mailmap_entry *)p;\n-\tdebug_mm(\"mailmap: removing entries for <%s>, with %d sub-entries\\n\",\n+\tdebug_mm(\"mailmap: removing entries for <%s>, with %\"PRIuMAX\" sub-entries\\n\",\n \t\t s, me->namemap.nr);\n \tdebug_mm(\"mailmap: - simple: '%s' <%s>\\n\",\n \t\t debug_str(me->name), debug_str(me->email));\n@@ -250,7 +250,7 @@ int read_mailmap(struct string_list *map)\n \n void clear_mailmap(struct string_list *map)\n {\n-\tdebug_mm(\"mailmap: clearing %d entries...\\n\", map->nr);\n+\tdebug_mm(\"mailmap: clearing %\"PRIuMAX\" entries...\\n\", map->nr);\n \tmap->strdup_strings = 1;\n \tstring_list_clear_func(map, free_mailmap_entry);\n \tdebug_mm(\"mailmap: cleared\\n\");\ndiff --git a/merge-ort.c b/merge-ort.c\nindex 0342f104836..28a7cffdb96 100644\n--- a/merge-ort.c\n+++ b/merge-ort.c\n@@ -4004,7 +4004,7 @@ static void process_entries(struct merge_options *opt,\n \ttrace2_region_enter(\"merge\", \"process_entries cleanup\", opt->repo);\n \tif (dir_metadata.offsets.nr != 1 ||\n \t (uintptr_t)dir_metadata.offsets.items[0].util != 0) {\n-\t\tprintf(\"dir_metadata.offsets.nr = %d (should be 1)\\n\",\n+\t\tprintf(\"dir_metadata.offsets.nr = %\"PRIuMAX\" (should be 1)\\n\",\n \t\t dir_metadata.offsets.nr);\n \t\tprintf(\"dir_metadata.offsets.items[0].util = %u (should be 0)\\n\",\n \t\t (unsigned)(uintptr_t)dir_metadata.offsets.items[0].util);\ndiff --git a/string-list.h b/string-list.h\nindex 267d6e5769d..ab331643685 100644\n--- a/string-list.h\n+++ b/string-list.h\n@@ -86,7 +86,7 @@ typedef int (*compare_strings_fn)(const char *, const char *);\n */\n struct string_list {\n \tstruct string_list_item *items;\n-\tunsigned int nr, alloc;\n+\tsize_t nr, alloc;\n \tunsigned int strdup_strings:1;\n \tcompare_strings_fn cmp; /* NULL uses strcmp() */\n };\ndiff --git a/t/helper/test-run-command.c b/t/helper/test-run-command.c\nindex 3c4fb862234..8e932700201 100644\n--- a/t/helper/test-run-command.c\n+++ b/t/helper/test-run-command.c\n@@ -180,7 +180,7 @@ static int testsuite(int argc, const char **argv)\n \tif (max_jobs > suite.tests.nr)\n \t\tmax_jobs = suite.tests.nr;\n \n-\tfprintf(stderr, \"Running %d tests (%d at a time)\\n\",\n+\tfprintf(stderr, \"Running %\"PRIuMAX\" tests (%d at a time)\\n\",\n \t\tsuite.tests.nr, max_jobs);\n \n \tret = run_processes_parallel(max_jobs, next_test, test_failed,\n@@ -188,7 +188,7 @@ static int testsuite(int argc, const char **argv)\n \n \tif (suite.failed.nr > 0) {\n \t\tret = 1;\n-\t\tfprintf(stderr, \"%d tests failed:\\n\\n\", suite.failed.nr);\n+\t\tfprintf(stderr, \"%\"PRIuMAX\" tests failed:\\n\\n\", suite.failed.nr);\n \t\tfor (i = 0; i < suite.failed.nr; i++)\n \t\t\tfprintf(stderr, \"\\t%s\\n\", suite.failed.items[i].string);\n \t}\ndiff --git a/wt-status.c b/wt-status.c\nindex 5d215f4e4f1..79b83caa0f3 100644\n--- a/wt-status.c\n+++ b/wt-status.c\n@@ -1368,8 +1368,8 @@ static void show_rebase_information(struct wt_status *s,\n \t\t\tstatus_printf_ln(s, color, _(\"No commands done.\"));\n \t\telse {\n \t\t\tstatus_printf_ln(s, color,\n-\t\t\t\tQ_(\"Last command done (%d command done):\",\n-\t\t\t\t\t\"Last commands done (%d commands done):\",\n+\t\t\t\tQ_(\"Last command done (%\"PRIuMAX\" command done):\",\n+\t\t\t\t\t\"Last commands done (%\"PRIuMAX\" commands done):\",\n \t\t\t\t\thave_done.nr),\n \t\t\t\thave_done.nr);\n \t\t\tfor (i = (have_done.nr > nr_lines_to_show)\n@@ -1387,8 +1387,8 @@ static void show_rebase_information(struct wt_status *s,\n \t\t\t\t\t _(\"No commands remaining.\"));\n \t\telse {\n \t\t\tstatus_printf_ln(s, color,\n-\t\t\t\tQ_(\"Next command to do (%d remaining command):\",\n-\t\t\t\t\t\"Next commands to do (%d remaining commands):\",\n+\t\t\t\tQ_(\"Next command to do (%\"PRIuMAX\" remaining command):\",\n+\t\t\t\t\t\"Next commands to do (%\"PRIuMAX\" remaining commands):\",\n \t\t\t\t\tyet_to_do.nr),\n \t\t\t\tyet_to_do.nr);\n \t\t\tfor (i = 0; i < nr_lines_to_show && i < yet_to_do.nr; i++)\n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443673","messageId":"RFC-patch-02.10-bd7d014c531-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:19Z","receivedAt":"2021-12-09T19:19:38Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"As documented in 320d0b493a2 (add helpers for detecting size_t\noverflow, 2016-02-19) the arguments to st_mult() and st_add() \"must be\nunsigned\". This code added in d9c66f0b5bf (range-diff: first\nrudimentary implementation, 2018-08-13) operates on signed int.\n\nIn subsequent commits further overflows resulting in segfaults will be\nfixed in this code, but let's start by removing this supposed guard\nthat does nothing except give us a false sense of\nsecurity. E.g. providing an \"n\" of INT_MAX here will result in \"1\" on\nmy system, causing us to write into memory.\n\nThere are other such issues left in the codebase, e.g. the code in\n\"builtin/clean.c\" changed in 50a6c8efa2b (use st_add and st_mult for\nallocation size computation, 2016-02-22). But let's focus on\nrange-diff.c for now.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n range-diff.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/range-diff.c b/range-diff.c\nindex cac89a2f4f2..170e8623313 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -312,7 +312,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \tint *cost, c, *a2b, *b2a;\n \tint i, j;\n \n-\tALLOC_ARRAY(cost, st_mult(n, n));\n+\tALLOC_ARRAY(cost, n * n);\n \tALLOC_ARRAY(a2b, n);\n \tALLOC_ARRAY(b2a, n);\n \n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443674","messageId":"RFC-patch-03.10-183418f1223-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 03/10] range-diff.c: use \"size_t\" to refer to \"struct string_list\"'s \"nr\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:20Z","receivedAt":"2021-12-09T19:19:45Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"In a preceding commit the \"nr\" member of \"struct string_list\" was\nchanged to be \"size_t\" instead of an \"unsigned int\". Let's follow suit\nhere and do the same for our corresponding index variables.\n\nWe can also use the st_mult() helper again prepare the argument to\nALLOC_ARRAY(), but this time correctly as the \"n\" is unsigned. The\nsame goes for a new addition of \"st_add()\" for \"a->nr + b->nr\".\n\nThere was a segfault in range-diff.c and linear-assignment.c due to an\n\"int\" overflow. This doesn't solve that problem, but on my system\nmoves it around a bit. Before this we'd segfault in the\n\"get_correspondences()\" function in range-diff.c, specifically on this\nline in the first loop in that function:\n\n cost[i + n * j] = 0\n\nNow we'll instead make it all the way into compute_assignment() called\nby that same function, and segfault on line 37 of linear-assignment.c in:\n\n if (COST(j, i1) > COST(j, i))\n\nWhich is defined as:\n\n #define COST(column, row) cost[(column) + column_count * (row)]\n\nAnd will overflow thusly, with a segfault as we try to use that as a\nnegative index into \"cost\":\n\n (GDB) p j + column_count * i\n $10 = -2147454537\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n range-diff.c | 10 +++++-----\n 1 file changed, 5 insertions(+), 5 deletions(-)\n\ndiff --git a/range-diff.c b/range-diff.c\nindex 170e8623313..41003033752 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -237,7 +237,7 @@ static int patch_util_cmp(const void *dummy, const struct patch_util *a,\n static void find_exact_matches(struct string_list *a, struct string_list *b)\n {\n \tstruct hashmap map = HASHMAP_INIT((hashmap_cmp_fn)patch_util_cmp, NULL);\n-\tint i;\n+\tsize_t i;\n \n \t/* First, add the patches of a to a hash map */\n \tfor (i = 0; i < a->nr; i++) {\n@@ -308,11 +308,11 @@ static int diffsize(const char *a, const char *b)\n static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\t\tint creation_factor)\n {\n-\tint n = a->nr + b->nr;\n+\tsize_t n = st_add(a->nr, b->nr);\n \tint *cost, c, *a2b, *b2a;\n-\tint i, j;\n+\tsize_t i, j;\n \n-\tALLOC_ARRAY(cost, n * n);\n+\tALLOC_ARRAY(cost, st_mult(n, n));\n \tALLOC_ARRAY(a2b, n);\n \tALLOC_ARRAY(b2a, n);\n \n@@ -473,7 +473,7 @@ static void output(struct string_list *a, struct string_list *b,\n {\n \tstruct strbuf buf = STRBUF_INIT, dashes = STRBUF_INIT;\n \tint patch_no_width = decimal_width(1 + (a->nr > b->nr ? a->nr : b->nr));\n-\tint i = 0, j = 0;\n+\tsize_t i = 0, j = 0;\n \tstruct diff_options opts;\n \tstruct strbuf indent = STRBUF_INIT;\n \n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443675","messageId":"RFC-patch-05.10-0e1e2d107cd-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 05/10] linear-assignment.c: split up compute_assignment() function","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:22Z","receivedAt":"2021-12-09T19:19:50Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Split up the the long compute_assignment() function to make it easier\nto reason about, particularly when it comes to what variables are used\nlater, and which aren't.\n\nThe grouping of \"int\" v.s. \"int *\" in function signatures is there to\nmake subsequent diffs smaller, if we're ever going to have a \"nr\"\nmember with a \"size_t\", but allocate e.g. \"int *\", and in anticipation\nof the type names becoming longer than \"int\", which would require\nre-wrapping.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 103 +++++++++++++++++++++++++++++++++-----------\n linear-assignment.h | 3 +-\n 2 files changed, 79 insertions(+), 27 deletions(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex 0c0786a63b6..7f85745e541 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -8,21 +8,12 @@\n \n #define COST(column, row) cost[(column) + column_count * (row)]\n \n-/*\n- * The parameter `cost` is the cost matrix: the cost to assign column j to row\n- * i is `cost[j + column_count * i].\n- */\n-void compute_assignment(int column_count, int row_count, int *cost,\n-\t\t\tint *column2row, int *row2column)\n+static void columns_reduction(int column_count, int row_count,\n+\t\t\t int *cost,\n+\t\t\t int *column2row, int *row2column,\n+\t\t\t int *v)\n {\n-\tint *v, *d;\n-\tint *free_row, free_count = 0, saved_free_count, *pred, *col;\n-\tint i, j, phase;\n-\n-\tassert(column_count > 1);\n-\tmemset(column2row, -1, sizeof(int) * column_count);\n-\tmemset(row2column, -1, sizeof(int) * row_count);\n-\tALLOC_ARRAY(v, column_count);\n+\tint i, j;\n \n \t/* column reduction */\n \tfor (j = column_count - 1; j >= 0; j--) {\n@@ -42,13 +33,21 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \t\t\tcolumn2row[j] = -1;\n \t\t}\n \t}\n+}\n+\n+static void reduction_transfer(int column_count, int row_count,\n+\t\t\t int *cost,\n+\t\t\t int *free_row, int *free_count,\n+\t\t\t int *column2row, int *row2column,\n+\t\t\t int *v)\n+{\n+\tint i, j;\n \n \t/* reduction transfer */\n-\tALLOC_ARRAY(free_row, row_count);\n \tfor (i = 0; i < row_count; i++) {\n \t\tint j1 = row2column[i];\n \t\tif (j1 == -1)\n-\t\t\tfree_row[free_count++] = i;\n+\t\t\tfree_row[(*free_count)++] = i;\n \t\telse if (j1 < -1)\n \t\t\trow2column[i] = -2 - j1;\n \t\telse {\n@@ -59,21 +58,25 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \t\t\tv[j1] -= min;\n \t\t}\n \t}\n+}\n \n-\tif (free_count ==\n-\t (column_count < row_count ? row_count - column_count : 0)) {\n-\t\tfree(v);\n-\t\tfree(free_row);\n-\t\treturn;\n-\t}\n+static void augmenting_row_reduction(int column_count,\n+\t\t\t\t int *cost,\n+\t\t\t\t int *column2row, int *row2column,\n+\t\t\t\t int *free_row, int *free_count, int *saved_free_count,\n+\t\t\t\t int *v)\n+{\n+\tint phase;\n \n \t/* augmenting row reduction */\n \tfor (phase = 0; phase < 2; phase++) {\n+\t\tint i;\n \t\tint k = 0;\n \n-\t\tsaved_free_count = free_count;\n-\t\tfree_count = 0;\n-\t\twhile (k < saved_free_count) {\n+\t\t*saved_free_count = *free_count;\n+\t\t*free_count = 0;\n+\t\twhile (k < *saved_free_count) {\n+\t\t\tint j;\n \t\t\tint u1, u2;\n \t\t\tint j1 = 0, j2, i0;\n \n@@ -112,12 +115,24 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \t\t\t\tif (u1 < u2)\n \t\t\t\t\tfree_row[--k] = i0;\n \t\t\t\telse\n-\t\t\t\t\tfree_row[free_count++] = i0;\n+\t\t\t\t\tfree_row[(*free_count)++] = i0;\n \t\t\t}\n \t\t\trow2column[i] = j1;\n \t\t\tcolumn2row[j1] = i;\n \t\t}\n \t}\n+}\n+\n+static void augmentation(int column_count,\n+\t\t\t int *cost,\n+\t\t\t int *column2row, int *row2column,\n+\t\t\t int *free_row, int free_count,\n+\t\t\t int *v)\n+{\n+\tint i, j;\n+\tint *d;\n+\tint *pred, *col;\n+\tint saved_free_count;\n \n \t/* augmentation */\n \tsaved_free_count = free_count;\n@@ -197,6 +212,42 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \tfree(col);\n \tfree(pred);\n \tfree(d);\n+}\n+\n+/*\n+ * The parameter `cost` is the cost matrix: the cost to assign column j to row\n+ * i is `cost[j + column_count * i].\n+ */\n+void compute_assignment(int column_count, int row_count,\n+\t\t\tint *cost,\n+\t\t\tint *column2row, int *row2column)\n+{\n+\tint *v;\n+\tint *free_row, free_count = 0, saved_free_count;\n+\n+\tassert(column_count > 1);\n+\tmemset(column2row, -1, sizeof(int) * column_count);\n+\tmemset(row2column, -1, sizeof(int) * row_count);\n+\tALLOC_ARRAY(v, column_count);\n+\n+\tcolumns_reduction(column_count, row_count, cost, column2row,\n+\t\t\t row2column, v);\n+\n+\tALLOC_ARRAY(free_row, row_count);\n+\treduction_transfer(column_count, row_count, cost, free_row,\n+\t\t\t &free_count, column2row, row2column, v);\n+\tif (free_count ==\n+\t (column_count < row_count ? row_count - column_count : 0))\n+\t\tgoto cleanup;\n+\n+\taugmenting_row_reduction(column_count, cost, column2row,\n+\t\t\t\t row2column, free_row, &free_count,\n+\t\t\t\t &saved_free_count,v);\n+\n+\taugmentation(column_count, cost, column2row, row2column,\n+\t\t free_row, free_count, v);\n+\n+cleanup:\n \tfree(v);\n \tfree(free_row);\n }\ndiff --git a/linear-assignment.h b/linear-assignment.h\nindex 1dfea766290..ef9946bdbfc 100644\n--- a/linear-assignment.h\n+++ b/linear-assignment.h\n@@ -13,7 +13,8 @@\n * assignments (-1 for unassigned, which can happen only if column_count !=\n * row_count).\n */\n-void compute_assignment(int column_count, int row_count, int *cost,\n+void compute_assignment(int column_count, int row_count,\n+\t\t\tint *cost,\n \t\t\tint *column2row, int *row2column);\n \n /* The maximal cost in the cost matrix (to prevent integer overflows). */\n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443676","messageId":"RFC-patch-04.10-fe9dcb2d453-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 04/10] range-diff: zero out elements in \"cost\" first","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:21Z","receivedAt":"2021-12-09T19:19:50Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Have the get_correspondences() function use CALLOC_ARRAY instead of\nlooping over the newly allocated \"cost\" to zero out some of its\nelements.\n\nThe for-loop that zero'd out elements in \"cost\" wasn't the first loop\nin that function, nor did it cover all of its elements, but regardless\nof that this change doesn't affect its end-state. None of the\nfor-loops touched the same items in the array, so we could have (and\nan earlier WIP version of this change did) moved the for-loop we're\ndeleting to come first in get_correspondences().\n\nThis can be seen from a careful reading of this code added in in\nd9c66f0b5bf (range-diff: first rudimentary implementation,\n2018-08-13) (as well as adding some printf-debugging) we'll set all\nelements in the in the \"n * n\" allocated array. That's \"n = A+B\" where\n\"A\" and \"B\" are the number of commits in our respective ranges.\n\nSo let's just allocate this with CALLOC_ARRAY(), and skip these two\nfor-loops. Furthermore let's remove the early exit condition from\ncompute_assignment() in favor of an assert that it must be called with\n\"column_count > 1\", then \"get_correspondences()\" can skip calling it\nwhen no further filling of the \"a2b\" and \"b2a\" arrays is needed.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 7 +------\n range-diff.c | 13 +++++--------\n 2 files changed, 6 insertions(+), 14 deletions(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex ecffc09be6e..0c0786a63b6 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -19,12 +19,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \tint *free_row, free_count = 0, saved_free_count, *pred, *col;\n \tint i, j, phase;\n \n-\tif (column_count < 2) {\n-\t\tmemset(column2row, 0, sizeof(int) * column_count);\n-\t\tmemset(row2column, 0, sizeof(int) * row_count);\n-\t\treturn;\n-\t}\n-\n+\tassert(column_count > 1);\n \tmemset(column2row, -1, sizeof(int) * column_count);\n \tmemset(row2column, -1, sizeof(int) * row_count);\n \tALLOC_ARRAY(v, column_count);\ndiff --git a/range-diff.c b/range-diff.c\nindex 41003033752..b0ccb46ff4c 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -312,9 +312,9 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \tint *cost, c, *a2b, *b2a;\n \tsize_t i, j;\n \n-\tALLOC_ARRAY(cost, st_mult(n, n));\n-\tALLOC_ARRAY(a2b, n);\n-\tALLOC_ARRAY(b2a, n);\n+\tCALLOC_ARRAY(cost, st_mult(n, n));\n+\tCALLOC_ARRAY(a2b, n);\n+\tCALLOC_ARRAY(b2a, n);\n \n \tfor (i = 0; i < a->nr; i++) {\n \t\tstruct patch_util *a_util = a->items[i].util;\n@@ -346,11 +346,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\tcost[i + n * j] = c;\n \t}\n \n-\tfor (i = a->nr; i < n; i++)\n-\t\tfor (j = b->nr; j < n; j++)\n-\t\t\tcost[i + n * j] = 0;\n-\n-\tcompute_assignment(n, n, cost, a2b, b2a);\n+\tif (n > 1)\n+\t\tcompute_assignment(n, n, cost, a2b, b2a);\n \n \tfor (i = 0; i < a->nr; i++)\n \t\tif (a2b[i] >= 0 && a2b[i] < b->nr) {\n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443677","messageId":"RFC-patch-06.10-9b697720e00-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 06/10] linear-assignment.c: take \"size_t\", not \"int\" for *_count","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:23Z","receivedAt":"2021-12-09T19:19:52Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Future-proof and clarify the compute_assignment() interface by having\nit take a \"size_t\" for the count of its that it's processing. For the\ncontent itself we need to be able to store a \"-1\", but there's no\nreason we can't use a \"size_t\" for the size of the number of \"int\"'s\nwe've got.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 10 +++++-----\n linear-assignment.h | 2 +-\n 2 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex 7f85745e541..1f8329701a0 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -8,7 +8,7 @@\n \n #define COST(column, row) cost[(column) + column_count * (row)]\n \n-static void columns_reduction(int column_count, int row_count,\n+static void columns_reduction(size_t column_count, size_t row_count,\n \t\t\t int *cost,\n \t\t\t int *column2row, int *row2column,\n \t\t\t int *v)\n@@ -35,7 +35,7 @@ static void columns_reduction(int column_count, int row_count,\n \t}\n }\n \n-static void reduction_transfer(int column_count, int row_count,\n+static void reduction_transfer(size_t column_count, size_t row_count,\n \t\t\t int *cost,\n \t\t\t int *free_row, int *free_count,\n \t\t\t int *column2row, int *row2column,\n@@ -60,7 +60,7 @@ static void reduction_transfer(int column_count, int row_count,\n \t}\n }\n \n-static void augmenting_row_reduction(int column_count,\n+static void augmenting_row_reduction(size_t column_count,\n \t\t\t\t int *cost,\n \t\t\t\t int *column2row, int *row2column,\n \t\t\t\t int *free_row, int *free_count, int *saved_free_count,\n@@ -123,7 +123,7 @@ static void augmenting_row_reduction(int column_count,\n \t}\n }\n \n-static void augmentation(int column_count,\n+static void augmentation(size_t column_count,\n \t\t\t int *cost,\n \t\t\t int *column2row, int *row2column,\n \t\t\t int *free_row, int free_count,\n@@ -218,7 +218,7 @@ static void augmentation(int column_count,\n * The parameter `cost` is the cost matrix: the cost to assign column j to row\n * i is `cost[j + column_count * i].\n */\n-void compute_assignment(int column_count, int row_count,\n+void compute_assignment(size_t column_count, size_t row_count,\n \t\t\tint *cost,\n \t\t\tint *column2row, int *row2column)\n {\ndiff --git a/linear-assignment.h b/linear-assignment.h\nindex ef9946bdbfc..9ff055baac1 100644\n--- a/linear-assignment.h\n+++ b/linear-assignment.h\n@@ -13,7 +13,7 @@\n * assignments (-1 for unassigned, which can happen only if column_count !=\n * row_count).\n */\n-void compute_assignment(int column_count, int row_count,\n+void compute_assignment(size_t column_count, size_t row_count,\n \t\t\tint *cost,\n \t\t\tint *column2row, int *row2column);\n \n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443678","messageId":"RFC-patch-07.10-a82771413f7-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 07/10] linear-assignment.c: convert a macro to a \"static inline\" function","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:24Z","receivedAt":"2021-12-09T19:19:57Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Change the COST() macro to be a \"static inline\" function. On GCC this\nmakes no difference in performance, but this improves the readability\nof the function. In a subsequent commit we'll make use of this to\nextend this function with overflow detection.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 11 ++++++++++-\n 1 file changed, 10 insertions(+), 1 deletion(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex 1f8329701a0..e9cec16132a 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -6,7 +6,16 @@\n #include \"cache.h\"\n #include \"linear-assignment.h\"\n \n-#define COST(column, row) cost[(column) + column_count * (row)]\n+static inline int cost_index(int *cost, int a, int b, int c)\n+{\n+\tint r;\n+\n+\tr = b + a * c;\n+\n+\treturn r;\n+}\n+\n+#define COST(column, row) cost[cost_index(cost, column_count, column, row)]\n \n static void columns_reduction(size_t column_count, size_t row_count,\n \t\t\t int *cost,\n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443679","messageId":"RFC-patch-08.10-794d494bedd-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 08/10] linear-assignment.c: detect signed add/mul on GCC and Clang","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:25Z","receivedAt":"2021-12-09T19:19:58Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Extend the cost_index() inline function added in the preceding commit\nwith signed overflow detection that'll work on GCC[1] and\nClang[2]. See 320d0b493a2 (add helpers for detecting size_t overflow,\n2016-02-19) for the existing git-compat-util.h helpers to detect\nsigned overflow.\n\nThis fixes a segfault on that happens when \"range-diff\" is given a\nvery large range to work with, such as the difference between\ngit.git's \"master\" the git-for-windows fork:\n\n $ git -P range-diff --creation-factor=50 origin/master...git-for-windows/main\n fatal: integer overflow in cost[47395 + ((47396 * 45309) = -2147454537)] addition\n\nThere are known bugs with using these functions in some versions of\nGCC, as we'll see in a subsequent commit we're better off detecting\nthose with the \"intprops.h\" library, but for now let's add a simpler\nimplementation that relies on the bare minimum of compiler checking.\n\n1. https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html#Integer-Overflow-Builtins\n2. https://clang.llvm.org/docs/LanguageExtensions.html#checked-arithmetic-builtins\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 7 +++++++\n 1 file changed, 7 insertions(+)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex e9cec16132a..b6597b622c8 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -10,7 +10,14 @@ static inline int cost_index(int *cost, int a, int b, int c)\n {\n \tint r;\n \n+#if defined(__GNUC__) || defined(__clang__)\n+\tif (__builtin_mul_overflow(a, c, &r))\n+\t\tdie(_(\"integer overflow in cost[%d + %d * %c] multiplication\"), b, a, c);\n+\tif (__builtin_add_overflow(b, r, &r))\n+\t\tdie(_(\"integer overflow in cost[%d + ((%d * %d) = %d)] addition\"), b, a, c, r);\n+#else\n \tr = b + a * c;\n+#endif\n \n \treturn r;\n }\n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443681","messageId":"RFC-patch-09.10-2026b4bff90-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 09/10] linear-assignment.c: add and use intprops.h from Gnulib","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:26Z","receivedAt":"2021-12-09T19:20:00Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"In the preceding commit we started optimistically using\n__builtin_{add,mul}_overflow under GCC and Clang, but as reading\nthrough the intprops.h being added here from gnulib reveals, using\njust those functions is a rabbit hole of version-specific GCC and\nClang bugs, compiler detection etc.\n\nLet's outsource all that detection to the macro-only intprops.h from\nGnulib. This header is licensed under the LGPL 2.1, the same license\nthat xdiff/* and compat/regex/* are under. So there's no license\nreason for why we can't import this.\n\nThis is the latest version from\ngnulib.git (https://git.savannah.gnu.org/git/gnulib.git), last\nmodified with 5d88f13109 (regex: sync with glibc, 2021-09-21). The\nonce change to it is the removal of:\n\n #include \n\nWhich we'll get from git-compat-util.h.\n\nNow we'll still die the same way on overflow, i.e:\n\n git -P range-diff --creation-factor=50 origin/master...git-for-windows/main\n fatal: integer overflow in cost[47395 + ((47396 * 45309) = -2147454537)] addition\n\nBut this time we don't need compiler-specific checks in our main\nsources to do so, this even works on e.g. Intel ICC.\n\nNote that this file has various \"git diff --check\" issues, hence the\n\"compat/gnulib/.gitattributes\" being added here. These are external\nsources, we should import them as close to as-is as we can, to make it\neasier to upgrade them in the future.\n\nWe could go a step further here and replace the various\nunsigned_*_overflows() in \"git-compat-util.h\" with macros from this\nintprops.h header. See [1][2][3][4][5] for our home-grown\nimplementation of overflow checking. That could be done as simply\nreplacing them with:\n\n #include \"compat/gnulib/intprops.h\"\n #define signed_add_overflows(a, b) INT_ADD_OVERFLOW(a, b)\n #define unsigned_add_overflows(a, b) INT_ADD_OVERFLOW(a, b)\n #define unsigned_mult_overflows(a, b) INT_MULTIPLY_OVERFLOW(a, b)\n #define unsigned_left_shift_overflows(a, shift) INT_LEFT_SHIFT_OVERFLOW(a, shift)\n\nThe benefit of doing so is that we'd end up with implementations that\nwould be more robust, as they'd detect both signed and unsigned\noverflows (we should then also rename our own macros).\n\nThe disadvantage is that it's a bit slower. I forward-ported the\nbenchmark program [6] written in 2016. Using the above macro\ndefinitions the slowdown measured with git-hyperfine[7] is the\nfollowing:\n\n $ git hyperfine -L rev HEAD~1,HEAD~0 -s 'make CFLAGS=-O3 git-strbuf-grow' './git-strbuf-grow'\n Benchmark 1: ./git-strbuf-grow' in 'HEAD~1\n Time (mean ± σ): 2.661 s ± 0.025 s [User: 2.657 s, System: 0.004 s]\n Range (min … max): 2.626 s … 2.713 s 10 runs\n\n Benchmark 2: ./git-strbuf-grow' in 'HEAD~0\n Time (mean ± σ): 2.875 s ± 0.031 s [User: 2.871 s, System: 0.004 s]\n Range (min … max): 2.832 s … 2.948 s 10 runs\n\n Summary\n './git-strbuf-grow' in 'HEAD~1' ran\n 1.08 ± 0.02 times faster than './git-strbuf-grow' in 'HEAD~0'\n\nThe slowdown is not overhead in Gnulib's intprops.h, but happens under\nboth GCC and Clang if we use __builtin_add_overflow() itself, so the\ndifference is in the infinite precision addition the compilers need to\ndo. We should probably not care and use them anyway, but let's just\nnarrowly fix the signed overflow issue for now.\n\n1. c03c83152d6 (do not depend on signed integer overflow, 2010-10-05)\n2. 1368f65002b (compat: helper for detecting unsigned overflow, 2010-10-10)\n3. 320d0b493a2 (add helpers for detecting size_t overflow, 2016-02-19)\n4. 935de81289c (add helpers for detecting size_t overflow, 2016-02-19)\n5. e2ffeae3f67 (git-compat-util: introduce more size_t helpers, 2021-11-02)\n6. https://lore.kernel.org/git/20160601210713.GA18118@sigill.intra.peff.net/\n7. https://github.com/avar/git-hyperfine/\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n compat/gnulib/.gitattributes | 1 +\n compat/gnulib/intprops.h | 637 +++++++++++++++++++++++++++++++++++\n linear-assignment.c | 11 +-\n 3 files changed, 642 insertions(+), 7 deletions(-)\n create mode 100644 compat/gnulib/.gitattributes\n create mode 100644 compat/gnulib/intprops.h\n\ndiff --git a/compat/gnulib/.gitattributes b/compat/gnulib/.gitattributes\nnew file mode 100644\nindex 00000000000..4ea1db2cd88\n--- /dev/null\n+++ b/compat/gnulib/.gitattributes\n@@ -0,0 +1 @@\n+intprops.h whitespace=-indent-with-non-tab\ndiff --git a/compat/gnulib/intprops.h b/compat/gnulib/intprops.h\nnew file mode 100644\nindex 00000000000..20aa90ad2a5\n--- /dev/null\n+++ b/compat/gnulib/intprops.h\n@@ -0,0 +1,637 @@\n+/* intprops.h -- properties of integer types\n+\n+ Copyright (C) 2001-2021 Free Software Foundation, Inc.\n+\n+ This program is free software: you can redistribute it and/or modify it\n+ under the terms of the GNU Lesser General Public License as published\n+ by the Free Software Foundation; either version 2.1 of the License, or\n+ (at your option) any later version.\n+\n+ This program is distributed in the hope that it will be useful,\n+ but WITHOUT ANY WARRANTY; without even the implied warranty of\n+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n+ GNU Lesser General Public License for more details.\n+\n+ You should have received a copy of the GNU Lesser General Public License\n+ along with this program. If not, see . */\n+\n+\n+#ifndef _GL_INTPROPS_H\n+#define _GL_INTPROPS_H\n+\n+/* Return a value with the common real type of E and V and the value of V.\n+ Do not evaluate E. */\n+#define _GL_INT_CONVERT(e, v) ((1 ? 0 : (e)) + (v))\n+\n+/* Act like _GL_INT_CONVERT (E, -V) but work around a bug in IRIX 6.5 cc; see\n+ . */\n+#define _GL_INT_NEGATE_CONVERT(e, v) ((1 ? 0 : (e)) - (v))\n+\n+/* The extra casts in the following macros work around compiler bugs,\n+ e.g., in Cray C 5.0.3.0. */\n+\n+/* True if the arithmetic type T is an integer type. bool counts as\n+ an integer. */\n+#define TYPE_IS_INTEGER(t) ((t) 1.5 == 1)\n+\n+/* True if the real type T is signed. */\n+#define TYPE_SIGNED(t) (! ((t) 0 < (t) -1))\n+\n+/* Return 1 if the real expression E, after promotion, has a\n+ signed or floating type. Do not evaluate E. */\n+#define EXPR_SIGNED(e) (_GL_INT_NEGATE_CONVERT (e, 1) < 0)\n+\n+\n+/* Minimum and maximum values for integer types and expressions. */\n+\n+/* The width in bits of the integer type or expression T.\n+ Do not evaluate T. T must not be a bit-field expression.\n+ Padding bits are not supported; this is checked at compile-time below. */\n+#define TYPE_WIDTH(t) (sizeof (t) * CHAR_BIT)\n+\n+/* The maximum and minimum values for the integer type T. */\n+#define TYPE_MINIMUM(t) ((t) ~ TYPE_MAXIMUM (t))\n+#define TYPE_MAXIMUM(t) \\\n+ ((t) (! TYPE_SIGNED (t) \\\n+ ? (t) -1 \\\n+ : ((((t) 1 << (TYPE_WIDTH (t) - 2)) - 1) * 2 + 1)))\n+\n+/* The maximum and minimum values for the type of the expression E,\n+ after integer promotion. E is not evaluated. */\n+#define _GL_INT_MINIMUM(e) \\\n+ (EXPR_SIGNED (e) \\\n+ ? ~ _GL_SIGNED_INT_MAXIMUM (e) \\\n+ : _GL_INT_CONVERT (e, 0))\n+#define _GL_INT_MAXIMUM(e) \\\n+ (EXPR_SIGNED (e) \\\n+ ? _GL_SIGNED_INT_MAXIMUM (e) \\\n+ : _GL_INT_NEGATE_CONVERT (e, 1))\n+#define _GL_SIGNED_INT_MAXIMUM(e) \\\n+ (((_GL_INT_CONVERT (e, 1) << (TYPE_WIDTH (+ (e)) - 2)) - 1) * 2 + 1)\n+\n+/* Work around OpenVMS incompatibility with C99. */\n+#if !defined LLONG_MAX && defined __INT64_MAX\n+# define LLONG_MAX __INT64_MAX\n+# define LLONG_MIN __INT64_MIN\n+#endif\n+\n+/* This include file assumes that signed types are two's complement without\n+ padding bits; the above macros have undefined behavior otherwise.\n+ If this is a problem for you, please let us know how to fix it for your host.\n+ This assumption is tested by the intprops-tests module. */\n+\n+/* Does the __typeof__ keyword work? This could be done by\n+ 'configure', but for now it's easier to do it by hand. */\n+#if (2 <= __GNUC__ \\\n+ || (4 <= __clang_major__) \\\n+ || (1210 <= __IBMC__ && defined __IBM__TYPEOF__) \\\n+ || (0x5110 <= __SUNPRO_C && !__STDC__))\n+# define _GL_HAVE___TYPEOF__ 1\n+#else\n+# define _GL_HAVE___TYPEOF__ 0\n+#endif\n+\n+/* Return 1 if the integer type or expression T might be signed. Return 0\n+ if it is definitely unsigned. T must not be a bit-field expression.\n+ This macro does not evaluate its argument, and expands to an\n+ integer constant expression. */\n+#if _GL_HAVE___TYPEOF__\n+# define _GL_SIGNED_TYPE_OR_EXPR(t) TYPE_SIGNED (__typeof__ (t))\n+#else\n+# define _GL_SIGNED_TYPE_OR_EXPR(t) 1\n+#endif\n+\n+/* Bound on length of the string representing an unsigned integer\n+ value representable in B bits. log10 (2.0) < 146/485. The\n+ smallest value of B where this bound is not tight is 2621. */\n+#define INT_BITS_STRLEN_BOUND(b) (((b) * 146 + 484) / 485)\n+\n+/* Bound on length of the string representing an integer type or expression T.\n+ T must not be a bit-field expression.\n+\n+ Subtract 1 for the sign bit if T is signed, and then add 1 more for\n+ a minus sign if needed.\n+\n+ Because _GL_SIGNED_TYPE_OR_EXPR sometimes returns 1 when its argument is\n+ unsigned, this macro may overestimate the true bound by one byte when\n+ applied to unsigned types of size 2, 4, 16, ... bytes. */\n+#define INT_STRLEN_BOUND(t) \\\n+ (INT_BITS_STRLEN_BOUND (TYPE_WIDTH (t) - _GL_SIGNED_TYPE_OR_EXPR (t)) \\\n+ + _GL_SIGNED_TYPE_OR_EXPR (t))\n+\n+/* Bound on buffer size needed to represent an integer type or expression T,\n+ including the terminating null. T must not be a bit-field expression. */\n+#define INT_BUFSIZE_BOUND(t) (INT_STRLEN_BOUND (t) + 1)\n+\n+\n+/* Range overflow checks.\n+\n+ The INT__RANGE_OVERFLOW macros return 1 if the corresponding C\n+ operators might not yield numerically correct answers due to\n+ arithmetic overflow. They do not rely on undefined or\n+ implementation-defined behavior. Their implementations are simple\n+ and straightforward, but they are harder to use and may be less\n+ efficient than the INT__WRAPV, INT__OK, and\n+ INT__OVERFLOW macros described below.\n+\n+ Example usage:\n+\n+ long int i = ...;\n+ long int j = ...;\n+ if (INT_MULTIPLY_RANGE_OVERFLOW (i, j, LONG_MIN, LONG_MAX))\n+ printf (\"multiply would overflow\");\n+ else\n+ printf (\"product is %ld\", i * j);\n+\n+ Restrictions on *_RANGE_OVERFLOW macros:\n+\n+ These macros do not check for all possible numerical problems or\n+ undefined or unspecified behavior: they do not check for division\n+ by zero, for bad shift counts, or for shifting negative numbers.\n+\n+ These macros may evaluate their arguments zero or multiple times,\n+ so the arguments should not have side effects. The arithmetic\n+ arguments (including the MIN and MAX arguments) must be of the same\n+ integer type after the usual arithmetic conversions, and the type\n+ must have minimum value MIN and maximum MAX. Unsigned types should\n+ use a zero MIN of the proper type.\n+\n+ Because all arguments are subject to integer promotions, these\n+ macros typically do not work on types narrower than 'int'.\n+\n+ These macros are tuned for constant MIN and MAX. For commutative\n+ operations such as A + B, they are also tuned for constant B. */\n+\n+/* Return 1 if A + B would overflow in [MIN,MAX] arithmetic.\n+ See above for restrictions. */\n+#define INT_ADD_RANGE_OVERFLOW(a, b, min, max) \\\n+ ((b) < 0 \\\n+ ? (a) < (min) - (b) \\\n+ : (max) - (b) < (a))\n+\n+/* Return 1 if A - B would overflow in [MIN,MAX] arithmetic.\n+ See above for restrictions. */\n+#define INT_SUBTRACT_RANGE_OVERFLOW(a, b, min, max) \\\n+ ((b) < 0 \\\n+ ? (max) + (b) < (a) \\\n+ : (a) < (min) + (b))\n+\n+/* Return 1 if - A would overflow in [MIN,MAX] arithmetic.\n+ See above for restrictions. */\n+#define INT_NEGATE_RANGE_OVERFLOW(a, min, max) \\\n+ ((min) < 0 \\\n+ ? (a) < - (max) \\\n+ : 0 < (a))\n+\n+/* Return 1 if A * B would overflow in [MIN,MAX] arithmetic.\n+ See above for restrictions. Avoid && and || as they tickle\n+ bugs in Sun C 5.11 2010/08/13 and other compilers; see\n+ . */\n+#define INT_MULTIPLY_RANGE_OVERFLOW(a, b, min, max) \\\n+ ((b) < 0 \\\n+ ? ((a) < 0 \\\n+ ? (a) < (max) / (b) \\\n+ : (b) == -1 \\\n+ ? 0 \\\n+ : (min) / (b) < (a)) \\\n+ : (b) == 0 \\\n+ ? 0 \\\n+ : ((a) < 0 \\\n+ ? (a) < (min) / (b) \\\n+ : (max) / (b) < (a)))\n+\n+/* Return 1 if A / B would overflow in [MIN,MAX] arithmetic.\n+ See above for restrictions. Do not check for division by zero. */\n+#define INT_DIVIDE_RANGE_OVERFLOW(a, b, min, max) \\\n+ ((min) < 0 && (b) == -1 && (a) < - (max))\n+\n+/* Return 1 if A % B would overflow in [MIN,MAX] arithmetic.\n+ See above for restrictions. Do not check for division by zero.\n+ Mathematically, % should never overflow, but on x86-like hosts\n+ INT_MIN % -1 traps, and the C standard permits this, so treat this\n+ as an overflow too. */\n+#define INT_REMAINDER_RANGE_OVERFLOW(a, b, min, max) \\\n+ INT_DIVIDE_RANGE_OVERFLOW (a, b, min, max)\n+\n+/* Return 1 if A << B would overflow in [MIN,MAX] arithmetic.\n+ See above for restrictions. Here, MIN and MAX are for A only, and B need\n+ not be of the same type as the other arguments. The C standard says that\n+ behavior is undefined for shifts unless 0 <= B < wordwidth, and that when\n+ A is negative then A << B has undefined behavior and A >> B has\n+ implementation-defined behavior, but do not check these other\n+ restrictions. */\n+#define INT_LEFT_SHIFT_RANGE_OVERFLOW(a, b, min, max) \\\n+ ((a) < 0 \\\n+ ? (a) < (min) >> (b) \\\n+ : (max) >> (b) < (a))\n+\n+/* True if __builtin_add_overflow (A, B, P) and __builtin_sub_overflow\n+ (A, B, P) work when P is non-null. */\n+/* __builtin_{add,sub}_overflow exists but is not reliable in GCC 5.x and 6.x,\n+ see . */\n+#if 7 <= __GNUC__ && !defined __ICC\n+# define _GL_HAS_BUILTIN_ADD_OVERFLOW 1\n+#elif defined __has_builtin\n+# define _GL_HAS_BUILTIN_ADD_OVERFLOW __has_builtin (__builtin_add_overflow)\n+#else\n+# define _GL_HAS_BUILTIN_ADD_OVERFLOW 0\n+#endif\n+\n+/* True if __builtin_mul_overflow (A, B, P) works when P is non-null. */\n+#ifdef __clang__\n+/* Work around Clang bug . */\n+# define _GL_HAS_BUILTIN_MUL_OVERFLOW 0\n+#else\n+# define _GL_HAS_BUILTIN_MUL_OVERFLOW _GL_HAS_BUILTIN_ADD_OVERFLOW\n+#endif\n+\n+/* True if __builtin_add_overflow_p (A, B, C) works, and similarly for\n+ __builtin_sub_overflow_p and __builtin_mul_overflow_p. */\n+#if defined __clang__ || defined __ICC\n+/* Clang 11 lacks __builtin_mul_overflow_p, and even if it did it\n+ would presumably run afoul of Clang bug 16404. ICC 2021.1's\n+ __builtin_add_overflow_p etc. are not treated as integral constant\n+ expressions even when all arguments are. */\n+# define _GL_HAS_BUILTIN_OVERFLOW_P 0\n+#elif defined __has_builtin\n+# define _GL_HAS_BUILTIN_OVERFLOW_P __has_builtin (__builtin_mul_overflow_p)\n+#else\n+# define _GL_HAS_BUILTIN_OVERFLOW_P (7 <= __GNUC__)\n+#endif\n+\n+/* The _GL*_OVERFLOW macros have the same restrictions as the\n+ *_RANGE_OVERFLOW macros, except that they do not assume that operands\n+ (e.g., A and B) have the same type as MIN and MAX. Instead, they assume\n+ that the result (e.g., A + B) has that type. */\n+#if _GL_HAS_BUILTIN_OVERFLOW_P\n+# define _GL_ADD_OVERFLOW(a, b, min, max) \\\n+ __builtin_add_overflow_p (a, b, (__typeof__ ((a) + (b))) 0)\n+# define _GL_SUBTRACT_OVERFLOW(a, b, min, max) \\\n+ __builtin_sub_overflow_p (a, b, (__typeof__ ((a) - (b))) 0)\n+# define _GL_MULTIPLY_OVERFLOW(a, b, min, max) \\\n+ __builtin_mul_overflow_p (a, b, (__typeof__ ((a) * (b))) 0)\n+#else\n+# define _GL_ADD_OVERFLOW(a, b, min, max) \\\n+ ((min) < 0 ? INT_ADD_RANGE_OVERFLOW (a, b, min, max) \\\n+ : (a) < 0 ? (b) <= (a) + (b) \\\n+ : (b) < 0 ? (a) <= (a) + (b) \\\n+ : (a) + (b) < (b))\n+# define _GL_SUBTRACT_OVERFLOW(a, b, min, max) \\\n+ ((min) < 0 ? INT_SUBTRACT_RANGE_OVERFLOW (a, b, min, max) \\\n+ : (a) < 0 ? 1 \\\n+ : (b) < 0 ? (a) - (b) <= (a) \\\n+ : (a) < (b))\n+# define _GL_MULTIPLY_OVERFLOW(a, b, min, max) \\\n+ (((min) == 0 && (((a) < 0 && 0 < (b)) || ((b) < 0 && 0 < (a)))) \\\n+ || INT_MULTIPLY_RANGE_OVERFLOW (a, b, min, max))\n+#endif\n+#define _GL_DIVIDE_OVERFLOW(a, b, min, max) \\\n+ ((min) < 0 ? (b) == _GL_INT_NEGATE_CONVERT (min, 1) && (a) < - (max) \\\n+ : (a) < 0 ? (b) <= (a) + (b) - 1 \\\n+ : (b) < 0 && (a) + (b) <= (a))\n+#define _GL_REMAINDER_OVERFLOW(a, b, min, max) \\\n+ ((min) < 0 ? (b) == _GL_INT_NEGATE_CONVERT (min, 1) && (a) < - (max) \\\n+ : (a) < 0 ? (a) % (b) != ((max) - (b) + 1) % (b) \\\n+ : (b) < 0 && ! _GL_UNSIGNED_NEG_MULTIPLE (a, b, max))\n+\n+/* Return a nonzero value if A is a mathematical multiple of B, where\n+ A is unsigned, B is negative, and MAX is the maximum value of A's\n+ type. A's type must be the same as (A % B)'s type. Normally (A %\n+ -B == 0) suffices, but things get tricky if -B would overflow. */\n+#define _GL_UNSIGNED_NEG_MULTIPLE(a, b, max) \\\n+ (((b) < -_GL_SIGNED_INT_MAXIMUM (b) \\\n+ ? (_GL_SIGNED_INT_MAXIMUM (b) == (max) \\\n+ ? (a) \\\n+ : (a) % (_GL_INT_CONVERT (a, _GL_SIGNED_INT_MAXIMUM (b)) + 1)) \\\n+ : (a) % - (b)) \\\n+ == 0)\n+\n+/* Check for integer overflow, and report low order bits of answer.\n+\n+ The INT__OVERFLOW macros return 1 if the corresponding C operators\n+ might not yield numerically correct answers due to arithmetic overflow.\n+ The INT__WRAPV macros compute the low-order bits of the sum,\n+ difference, and product of two C integers, and return 1 if these\n+ low-order bits are not numerically correct.\n+ These macros work correctly on all known practical hosts, and do not rely\n+ on undefined behavior due to signed arithmetic overflow.\n+\n+ Example usage, assuming A and B are long int:\n+\n+ if (INT_MULTIPLY_OVERFLOW (a, b))\n+ printf (\"result would overflow\\n\");\n+ else\n+ printf (\"result is %ld (no overflow)\\n\", a * b);\n+\n+ Example usage with WRAPV flavor:\n+\n+ long int result;\n+ bool overflow = INT_MULTIPLY_WRAPV (a, b, &result);\n+ printf (\"result is %ld (%s)\\n\", result,\n+ overflow ? \"after overflow\" : \"no overflow\");\n+\n+ Restrictions on these macros:\n+\n+ These macros do not check for all possible numerical problems or\n+ undefined or unspecified behavior: they do not check for division\n+ by zero, for bad shift counts, or for shifting negative numbers.\n+\n+ These macros may evaluate their arguments zero or multiple times, so the\n+ arguments should not have side effects.\n+\n+ The WRAPV macros are not constant expressions. They support only\n+ +, binary -, and *.\n+\n+ Because the WRAPV macros convert the result, they report overflow\n+ in different circumstances than the OVERFLOW macros do. For\n+ example, in the typical case with 16-bit 'short' and 32-bit 'int',\n+ if A, B and R are all of type 'short' then INT_ADD_OVERFLOW (A, B)\n+ returns false because the addition cannot overflow after A and B\n+ are converted to 'int', whereas INT_ADD_WRAPV (A, B, &R) returns\n+ true or false depending on whether the sum fits into 'short'.\n+\n+ These macros are tuned for their last input argument being a constant.\n+\n+ Return 1 if the integer expressions A * B, A - B, -A, A * B, A / B,\n+ A % B, and A << B would overflow, respectively. */\n+\n+#define INT_ADD_OVERFLOW(a, b) \\\n+ _GL_BINARY_OP_OVERFLOW (a, b, _GL_ADD_OVERFLOW)\n+#define INT_SUBTRACT_OVERFLOW(a, b) \\\n+ _GL_BINARY_OP_OVERFLOW (a, b, _GL_SUBTRACT_OVERFLOW)\n+#if _GL_HAS_BUILTIN_OVERFLOW_P\n+# define INT_NEGATE_OVERFLOW(a) INT_SUBTRACT_OVERFLOW (0, a)\n+#else\n+# define INT_NEGATE_OVERFLOW(a) \\\n+ INT_NEGATE_RANGE_OVERFLOW (a, _GL_INT_MINIMUM (a), _GL_INT_MAXIMUM (a))\n+#endif\n+#define INT_MULTIPLY_OVERFLOW(a, b) \\\n+ _GL_BINARY_OP_OVERFLOW (a, b, _GL_MULTIPLY_OVERFLOW)\n+#define INT_DIVIDE_OVERFLOW(a, b) \\\n+ _GL_BINARY_OP_OVERFLOW (a, b, _GL_DIVIDE_OVERFLOW)\n+#define INT_REMAINDER_OVERFLOW(a, b) \\\n+ _GL_BINARY_OP_OVERFLOW (a, b, _GL_REMAINDER_OVERFLOW)\n+#define INT_LEFT_SHIFT_OVERFLOW(a, b) \\\n+ INT_LEFT_SHIFT_RANGE_OVERFLOW (a, b, \\\n+ _GL_INT_MINIMUM (a), _GL_INT_MAXIMUM (a))\n+\n+/* Return 1 if the expression A B would overflow,\n+ where OP_RESULT_OVERFLOW (A, B, MIN, MAX) does the actual test,\n+ assuming MIN and MAX are the minimum and maximum for the result type.\n+ Arguments should be free of side effects. */\n+#define _GL_BINARY_OP_OVERFLOW(a, b, op_result_overflow) \\\n+ op_result_overflow (a, b, \\\n+ _GL_INT_MINIMUM (_GL_INT_CONVERT (a, b)), \\\n+ _GL_INT_MAXIMUM (_GL_INT_CONVERT (a, b)))\n+\n+/* Store the low-order bits of A + B, A - B, A * B, respectively, into *R.\n+ Return 1 if the result overflows. See above for restrictions. */\n+#if _GL_HAS_BUILTIN_ADD_OVERFLOW\n+# define INT_ADD_WRAPV(a, b, r) __builtin_add_overflow (a, b, r)\n+# define INT_SUBTRACT_WRAPV(a, b, r) __builtin_sub_overflow (a, b, r)\n+#else\n+# define INT_ADD_WRAPV(a, b, r) \\\n+ _GL_INT_OP_WRAPV (a, b, r, +, _GL_INT_ADD_RANGE_OVERFLOW)\n+# define INT_SUBTRACT_WRAPV(a, b, r) \\\n+ _GL_INT_OP_WRAPV (a, b, r, -, _GL_INT_SUBTRACT_RANGE_OVERFLOW)\n+#endif\n+#if _GL_HAS_BUILTIN_MUL_OVERFLOW\n+# if ((9 < __GNUC__ + (3 <= __GNUC_MINOR__) \\\n+ || (__GNUC__ == 8 && 4 <= __GNUC_MINOR__)) \\\n+ && !defined __ICC)\n+# define INT_MULTIPLY_WRAPV(a, b, r) __builtin_mul_overflow (a, b, r)\n+# else\n+ /* Work around GCC bug 91450. */\n+# define INT_MULTIPLY_WRAPV(a, b, r) \\\n+ ((!_GL_SIGNED_TYPE_OR_EXPR (*(r)) && EXPR_SIGNED (a) && EXPR_SIGNED (b) \\\n+ && _GL_INT_MULTIPLY_RANGE_OVERFLOW (a, b, 0, (__typeof__ (*(r))) -1)) \\\n+ ? ((void) __builtin_mul_overflow (a, b, r), 1) \\\n+ : __builtin_mul_overflow (a, b, r))\n+# endif\n+#else\n+# define INT_MULTIPLY_WRAPV(a, b, r) \\\n+ _GL_INT_OP_WRAPV (a, b, r, *, _GL_INT_MULTIPLY_RANGE_OVERFLOW)\n+#endif\n+\n+/* Nonzero if this compiler has GCC bug 68193 or Clang bug 25390. See:\n+ https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68193\n+ https://llvm.org/bugs/show_bug.cgi?id=25390\n+ For now, assume all versions of GCC-like compilers generate bogus\n+ warnings for _Generic. This matters only for compilers that\n+ lack relevant builtins. */\n+#if __GNUC__ || defined __clang__\n+# define _GL__GENERIC_BOGUS 1\n+#else\n+# define _GL__GENERIC_BOGUS 0\n+#endif\n+\n+/* Store the low-order bits of A B into *R, where OP specifies\n+ the operation and OVERFLOW the overflow predicate. Return 1 if the\n+ result overflows. See above for restrictions. */\n+#if 201112 <= __STDC_VERSION__ && !_GL__GENERIC_BOGUS\n+# define _GL_INT_OP_WRAPV(a, b, r, op, overflow) \\\n+ (_Generic \\\n+ (*(r), \\\n+ signed char: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \\\n+ signed char, SCHAR_MIN, SCHAR_MAX), \\\n+ unsigned char: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \\\n+ unsigned char, 0, UCHAR_MAX), \\\n+ short int: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \\\n+ short int, SHRT_MIN, SHRT_MAX), \\\n+ unsigned short int: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \\\n+ unsigned short int, 0, USHRT_MAX), \\\n+ int: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \\\n+ int, INT_MIN, INT_MAX), \\\n+ unsigned int: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \\\n+ unsigned int, 0, UINT_MAX), \\\n+ long int: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \\\n+ long int, LONG_MIN, LONG_MAX), \\\n+ unsigned long int: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \\\n+ unsigned long int, 0, ULONG_MAX), \\\n+ long long int: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long long int, \\\n+ long long int, LLONG_MIN, LLONG_MAX), \\\n+ unsigned long long int: \\\n+ _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long long int, \\\n+ unsigned long long int, 0, ULLONG_MAX)))\n+#else\n+/* Store the low-order bits of A B into *R, where OP specifies\n+ the operation and OVERFLOW the overflow predicate. If *R is\n+ signed, its type is ST with bounds SMIN..SMAX; otherwise its type\n+ is UT with bounds U..UMAX. ST and UT are narrower than int.\n+ Return 1 if the result overflows. See above for restrictions. */\n+# if _GL_HAVE___TYPEOF__\n+# define _GL_INT_OP_WRAPV_SMALLISH(a,b,r,op,overflow,st,smin,smax,ut,umax) \\\n+ (TYPE_SIGNED (__typeof__ (*(r))) \\\n+ ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, st, smin, smax) \\\n+ : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, ut, 0, umax))\n+# else\n+# define _GL_INT_OP_WRAPV_SMALLISH(a,b,r,op,overflow,st,smin,smax,ut,umax) \\\n+ (overflow (a, b, smin, smax) \\\n+ ? (overflow (a, b, 0, umax) \\\n+ ? (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a,b,op,unsigned,st), 1) \\\n+ : (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a,b,op,unsigned,st)) < 0) \\\n+ : (overflow (a, b, 0, umax) \\\n+ ? (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a,b,op,unsigned,st)) >= 0 \\\n+ : (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a,b,op,unsigned,st), 0)))\n+# endif\n+\n+# define _GL_INT_OP_WRAPV(a, b, r, op, overflow) \\\n+ (sizeof *(r) == sizeof (signed char) \\\n+ ? _GL_INT_OP_WRAPV_SMALLISH (a, b, r, op, overflow, \\\n+ signed char, SCHAR_MIN, SCHAR_MAX, \\\n+ unsigned char, UCHAR_MAX) \\\n+ : sizeof *(r) == sizeof (short int) \\\n+ ? _GL_INT_OP_WRAPV_SMALLISH (a, b, r, op, overflow, \\\n+ short int, SHRT_MIN, SHRT_MAX, \\\n+ unsigned short int, USHRT_MAX) \\\n+ : sizeof *(r) == sizeof (int) \\\n+ ? (EXPR_SIGNED (*(r)) \\\n+ ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \\\n+ int, INT_MIN, INT_MAX) \\\n+ : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned int, \\\n+ unsigned int, 0, UINT_MAX)) \\\n+ : _GL_INT_OP_WRAPV_LONGISH(a, b, r, op, overflow))\n+# ifdef LLONG_MAX\n+# define _GL_INT_OP_WRAPV_LONGISH(a, b, r, op, overflow) \\\n+ (sizeof *(r) == sizeof (long int) \\\n+ ? (EXPR_SIGNED (*(r)) \\\n+ ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \\\n+ long int, LONG_MIN, LONG_MAX) \\\n+ : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \\\n+ unsigned long int, 0, ULONG_MAX)) \\\n+ : (EXPR_SIGNED (*(r)) \\\n+ ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long long int, \\\n+ long long int, LLONG_MIN, LLONG_MAX) \\\n+ : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long long int, \\\n+ unsigned long long int, 0, ULLONG_MAX)))\n+# else\n+# define _GL_INT_OP_WRAPV_LONGISH(a, b, r, op, overflow) \\\n+ (EXPR_SIGNED (*(r)) \\\n+ ? _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \\\n+ long int, LONG_MIN, LONG_MAX) \\\n+ : _GL_INT_OP_CALC (a, b, r, op, overflow, unsigned long int, \\\n+ unsigned long int, 0, ULONG_MAX))\n+# endif\n+#endif\n+\n+/* Store the low-order bits of A B into *R, where the operation\n+ is given by OP. Use the unsigned type UT for calculation to avoid\n+ overflow problems. *R's type is T, with extrema TMIN and TMAX.\n+ T must be a signed integer type. Return 1 if the result overflows. */\n+#define _GL_INT_OP_CALC(a, b, r, op, overflow, ut, t, tmin, tmax) \\\n+ (overflow (a, b, tmin, tmax) \\\n+ ? (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a, b, op, ut, t), 1) \\\n+ : (*(r) = _GL_INT_OP_WRAPV_VIA_UNSIGNED (a, b, op, ut, t), 0))\n+\n+/* Return the low-order bits of A B, where the operation is given\n+ by OP. Use the unsigned type UT for calculation to avoid undefined\n+ behavior on signed integer overflow, and convert the result to type T.\n+ UT is at least as wide as T and is no narrower than unsigned int,\n+ T is two's complement, and there is no padding or trap representations.\n+ Assume that converting UT to T yields the low-order bits, as is\n+ done in all known two's-complement C compilers. E.g., see:\n+ https://gcc.gnu.org/onlinedocs/gcc/Integers-implementation.html\n+\n+ According to the C standard, converting UT to T yields an\n+ implementation-defined result or signal for values outside T's\n+ range. However, code that works around this theoretical problem\n+ runs afoul of a compiler bug in Oracle Studio 12.3 x86. See:\n+ https://lists.gnu.org/r/bug-gnulib/2017-04/msg00049.html\n+ As the compiler bug is real, don't try to work around the\n+ theoretical problem. */\n+\n+#define _GL_INT_OP_WRAPV_VIA_UNSIGNED(a, b, op, ut, t) \\\n+ ((t) ((ut) (a) op (ut) (b)))\n+\n+/* Return true if the numeric values A + B, A - B, A * B fall outside\n+ the range TMIN..TMAX. Arguments should be integer expressions\n+ without side effects. TMIN should be signed and nonpositive.\n+ TMAX should be positive, and should be signed unless TMIN is zero. */\n+#define _GL_INT_ADD_RANGE_OVERFLOW(a, b, tmin, tmax) \\\n+ ((b) < 0 \\\n+ ? (((tmin) \\\n+ ? ((EXPR_SIGNED (_GL_INT_CONVERT (a, (tmin) - (b))) || (b) < (tmin)) \\\n+ && (a) < (tmin) - (b)) \\\n+ : (a) <= -1 - (b)) \\\n+ || ((EXPR_SIGNED (a) ? 0 <= (a) : (tmax) < (a)) && (tmax) < (a) + (b))) \\\n+ : (a) < 0 \\\n+ ? (((tmin) \\\n+ ? ((EXPR_SIGNED (_GL_INT_CONVERT (b, (tmin) - (a))) || (a) < (tmin)) \\\n+ && (b) < (tmin) - (a)) \\\n+ : (b) <= -1 - (a)) \\\n+ || ((EXPR_SIGNED (_GL_INT_CONVERT (a, b)) || (tmax) < (b)) \\\n+ && (tmax) < (a) + (b))) \\\n+ : (tmax) < (b) || (tmax) - (b) < (a))\n+#define _GL_INT_SUBTRACT_RANGE_OVERFLOW(a, b, tmin, tmax) \\\n+ (((a) < 0) == ((b) < 0) \\\n+ ? ((a) < (b) \\\n+ ? !(tmin) || -1 - (tmin) < (b) - (a) - 1 \\\n+ : (tmax) < (a) - (b)) \\\n+ : (a) < 0 \\\n+ ? ((!EXPR_SIGNED (_GL_INT_CONVERT ((a) - (tmin), b)) && (a) - (tmin) < 0) \\\n+ || (a) - (tmin) < (b)) \\\n+ : ((! (EXPR_SIGNED (_GL_INT_CONVERT (tmax, b)) \\\n+ && EXPR_SIGNED (_GL_INT_CONVERT ((tmax) + (b), a))) \\\n+ && (tmax) <= -1 - (b)) \\\n+ || (tmax) + (b) < (a)))\n+#define _GL_INT_MULTIPLY_RANGE_OVERFLOW(a, b, tmin, tmax) \\\n+ ((b) < 0 \\\n+ ? ((a) < 0 \\\n+ ? (EXPR_SIGNED (_GL_INT_CONVERT (tmax, b)) \\\n+ ? (a) < (tmax) / (b) \\\n+ : ((INT_NEGATE_OVERFLOW (b) \\\n+ ? _GL_INT_CONVERT (b, tmax) >> (TYPE_WIDTH (+ (b)) - 1) \\\n+ : (tmax) / -(b)) \\\n+ <= -1 - (a))) \\\n+ : INT_NEGATE_OVERFLOW (_GL_INT_CONVERT (b, tmin)) && (b) == -1 \\\n+ ? (EXPR_SIGNED (a) \\\n+ ? 0 < (a) + (tmin) \\\n+ : 0 < (a) && -1 - (tmin) < (a) - 1) \\\n+ : (tmin) / (b) < (a)) \\\n+ : (b) == 0 \\\n+ ? 0 \\\n+ : ((a) < 0 \\\n+ ? (INT_NEGATE_OVERFLOW (_GL_INT_CONVERT (a, tmin)) && (a) == -1 \\\n+ ? (EXPR_SIGNED (b) ? 0 < (b) + (tmin) : -1 - (tmin) < (b) - 1) \\\n+ : (tmin) / (a) < (b)) \\\n+ : (tmax) / (b) < (a)))\n+\n+/* The following macros compute A + B, A - B, and A * B, respectively.\n+ If no overflow occurs, they set *R to the result and return 1;\n+ otherwise, they return 0 and may modify *R.\n+\n+ Example usage:\n+\n+ long int result;\n+ if (INT_ADD_OK (a, b, &result))\n+ printf (\"result is %ld\\n\", result);\n+ else\n+ printf (\"overflow\\n\");\n+\n+ A, B, and *R should be integers; they need not be the same type,\n+ and they need not be all signed or all unsigned.\n+\n+ These macros work correctly on all known practical hosts, and do not rely\n+ on undefined behavior due to signed arithmetic overflow.\n+\n+ These macros are not constant expressions.\n+\n+ These macros may evaluate their arguments zero or multiple times, so the\n+ arguments should not have side effects.\n+\n+ These macros are tuned for B being a constant. */\n+\n+#define INT_ADD_OK(a, b, r) ! INT_ADD_WRAPV (a, b, r)\n+#define INT_SUBTRACT_OK(a, b, r) ! INT_SUBTRACT_WRAPV (a, b, r)\n+#define INT_MULTIPLY_OK(a, b, r) ! INT_MULTIPLY_WRAPV (a, b, r)\n+\n+#endif /* _GL_INTPROPS_H */\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex b6597b622c8..e45099d651a 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -5,19 +5,16 @@\n */\n #include \"cache.h\"\n #include \"linear-assignment.h\"\n+#include \"compat/gnulib/intprops.h\"\n \n static inline int cost_index(int *cost, int a, int b, int c)\n {\n \tint r;\n \n-#if defined(__GNUC__) || defined(__clang__)\n-\tif (__builtin_mul_overflow(a, c, &r))\n-\t\tdie(_(\"integer overflow in cost[%d + %d * %c] multiplication\"), b, a, c);\n-\tif (__builtin_add_overflow(b, r, &r))\n+\tif (INT_MULTIPLY_WRAPV(a, c, &r))\n+\t\tdie(_(\"integer overflow in cost[%d + %d * %d] multiplication\"), b, a, c);\n+\tif (INT_ADD_WRAPV(b, r, &r))\n \t\tdie(_(\"integer overflow in cost[%d + ((%d * %d) = %d)] addition\"), b, a, c, r);\n-#else\n-\tr = b + a * c;\n-#endif\n \n \treturn r;\n }\n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443680","messageId":"RFC-patch-10.10-46395080b64-20211209T191653Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH 10/10] linear-assignment.c: use \"intmax_t\" instead of \"int\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-09T19:19:27Z","receivedAt":"2021-12-09T19:20:02Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Change the \"int\" type used by compute_assignment() to \"intmax_t\". On\n64 bit systems this changes the overflow \"die\" added in the preceding\ncommit (which before that was a segfault) to something that merely\ntakes a very long time and a lot of memory to run.\n\nOn my relatively beefy system this completes:\n\n git -P range-diff --creation-factor=50 origin/master...git-for-windows/main\n\nIn around 300 seconds, with a reported max RSS of just under 18GB, but\nit does give you correct results for all ~50k commitsin that range.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 92 ++++++++++++++++++++++-----------------------\n linear-assignment.h | 8 +---\n range-diff.c | 11 +++---\n 3 files changed, 54 insertions(+), 57 deletions(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex e45099d651a..ccd760520f8 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -7,14 +7,14 @@\n #include \"linear-assignment.h\"\n #include \"compat/gnulib/intprops.h\"\n \n-static inline int cost_index(int *cost, int a, int b, int c)\n+static inline intmax_t cost_index(intmax_t *cost, intmax_t a, intmax_t b, intmax_t c)\n {\n-\tint r;\n+\tintmax_t r;\n \n \tif (INT_MULTIPLY_WRAPV(a, c, &r))\n-\t\tdie(_(\"integer overflow in cost[%d + %d * %d] multiplication\"), b, a, c);\n+\t\tdie(_(\"integer overflow in cost[%\"PRIuMAX\" + %\"PRIuMAX\" * %\"PRIuMAX\"] multiplication\"), b, a, c);\n \tif (INT_ADD_WRAPV(b, r, &r))\n-\t\tdie(_(\"integer overflow in cost[%d + ((%d * %d) = %d)] addition\"), b, a, c, r);\n+\t\tdie(_(\"integer overflow in cost[%\"PRIuMAX\" + ((%\"PRIuMAX\" * %\"PRIuMAX\") = %\"PRIuMAX\")] addition\"), b, a, c, r);\n \n \treturn r;\n }\n@@ -22,15 +22,15 @@ static inline int cost_index(int *cost, int a, int b, int c)\n #define COST(column, row) cost[cost_index(cost, column_count, column, row)]\n \n static void columns_reduction(size_t column_count, size_t row_count,\n-\t\t\t int *cost,\n-\t\t\t int *column2row, int *row2column,\n-\t\t\t int *v)\n+\t\t\t intmax_t *cost,\n+\t\t\t intmax_t *column2row, intmax_t *row2column,\n+\t\t\t intmax_t *v)\n {\n-\tint i, j;\n+\tintmax_t i, j;\n \n \t/* column reduction */\n \tfor (j = column_count - 1; j >= 0; j--) {\n-\t\tint i1 = 0;\n+\t\tintmax_t i1 = 0;\n \n \t\tfor (i = 1; i < row_count; i++)\n \t\t\tif (COST(j, i1) > COST(j, i))\n@@ -49,22 +49,22 @@ static void columns_reduction(size_t column_count, size_t row_count,\n }\n \n static void reduction_transfer(size_t column_count, size_t row_count,\n-\t\t\t int *cost,\n-\t\t\t int *free_row, int *free_count,\n-\t\t\t int *column2row, int *row2column,\n-\t\t\t int *v)\n+\t\t\t intmax_t *cost,\n+\t\t\t intmax_t *free_row, intmax_t *free_count,\n+\t\t\t intmax_t *column2row, intmax_t *row2column,\n+\t\t\t intmax_t *v)\n {\n-\tint i, j;\n+\tintmax_t i, j;\n \n \t/* reduction transfer */\n \tfor (i = 0; i < row_count; i++) {\n-\t\tint j1 = row2column[i];\n+\t\tintmax_t j1 = row2column[i];\n \t\tif (j1 == -1)\n \t\t\tfree_row[(*free_count)++] = i;\n \t\telse if (j1 < -1)\n \t\t\trow2column[i] = -2 - j1;\n \t\telse {\n-\t\t\tint min = COST(!j1, i) - v[!j1];\n+\t\t\tintmax_t min = COST(!j1, i) - v[!j1];\n \t\t\tfor (j = 1; j < column_count; j++)\n \t\t\t\tif (j != j1 && min > COST(j, i) - v[j])\n \t\t\t\t\tmin = COST(j, i) - v[j];\n@@ -74,31 +74,31 @@ static void reduction_transfer(size_t column_count, size_t row_count,\n }\n \n static void augmenting_row_reduction(size_t column_count,\n-\t\t\t\t int *cost,\n-\t\t\t\t int *column2row, int *row2column,\n-\t\t\t\t int *free_row, int *free_count, int *saved_free_count,\n-\t\t\t\t int *v)\n+\t\t\t\t intmax_t *cost,\n+\t\t\t\t intmax_t *column2row, intmax_t *row2column,\n+\t\t\t\t intmax_t *free_row, intmax_t *free_count, intmax_t *saved_free_count,\n+\t\t\t\t intmax_t *v)\n {\n \tint phase;\n \n \t/* augmenting row reduction */\n \tfor (phase = 0; phase < 2; phase++) {\n-\t\tint i;\n-\t\tint k = 0;\n+\t\tintmax_t i;\n+\t\tintmax_t k = 0;\n \n \t\t*saved_free_count = *free_count;\n \t\t*free_count = 0;\n \t\twhile (k < *saved_free_count) {\n-\t\t\tint j;\n-\t\t\tint u1, u2;\n-\t\t\tint j1 = 0, j2, i0;\n+\t\t\tintmax_t j;\n+\t\t\tintmax_t u1, u2;\n+\t\t\tintmax_t j1 = 0, j2, i0;\n \n \t\t\ti = free_row[k++];\n \t\t\tu1 = COST(j1, i) - v[j1];\n \t\t\tj2 = -1;\n-\t\t\tu2 = INT_MAX;\n+\t\t\tu2 = INTMAX_MAX;\n \t\t\tfor (j = 1; j < column_count; j++) {\n-\t\t\t\tint c = COST(j, i) - v[j];\n+\t\t\t\tintmax_t c = COST(j, i) - v[j];\n \t\t\t\tif (u2 > c) {\n \t\t\t\t\tif (u1 < c) {\n \t\t\t\t\t\tu2 = c;\n@@ -137,15 +137,15 @@ static void augmenting_row_reduction(size_t column_count,\n }\n \n static void augmentation(size_t column_count,\n-\t\t\t int *cost,\n-\t\t\t int *column2row, int *row2column,\n-\t\t\t int *free_row, int free_count,\n-\t\t\t int *v)\n+\t\t\t intmax_t *cost,\n+\t\t\t intmax_t *column2row, intmax_t *row2column,\n+\t\t\t intmax_t *free_row, intmax_t free_count,\n+\t\t\t intmax_t *v)\n {\n-\tint i, j;\n-\tint *d;\n-\tint *pred, *col;\n-\tint saved_free_count;\n+\tintmax_t i, j;\n+\tintmax_t *d;\n+\tintmax_t *pred, *col;\n+\tintmax_t saved_free_count;\n \n \t/* augmentation */\n \tsaved_free_count = free_count;\n@@ -153,8 +153,8 @@ static void augmentation(size_t column_count,\n \tALLOC_ARRAY(pred, column_count);\n \tALLOC_ARRAY(col, column_count);\n \tfor (free_count = 0; free_count < saved_free_count; free_count++) {\n-\t\tint i1 = free_row[free_count], low = 0, up = 0, last, k;\n-\t\tint min, c, u1;\n+\t\tintmax_t i1 = free_row[free_count], low = 0, up = 0, last, k;\n+\t\tintmax_t min, c, u1;\n \n \t\tfor (j = 0; j < column_count; j++) {\n \t\t\td[j] = COST(j, i1) - v[j];\n@@ -184,7 +184,7 @@ static void augmentation(size_t column_count,\n \n \t\t\t/* scan a row */\n \t\t\tdo {\n-\t\t\t\tint j1 = col[low++];\n+\t\t\t\tintmax_t j1 = col[low++];\n \n \t\t\t\ti = column2row[j1];\n \t\t\t\tu1 = COST(j1, i) - v[j1] - min;\n@@ -208,14 +208,14 @@ static void augmentation(size_t column_count,\n update:\n \t\t/* updating of the column pieces */\n \t\tfor (k = 0; k < last; k++) {\n-\t\t\tint j1 = col[k];\n+\t\t\tintmax_t j1 = col[k];\n \t\t\tv[j1] += d[j1] - min;\n \t\t}\n \n \t\t/* augmentation */\n \t\tdo {\n \t\t\tif (j < 0)\n-\t\t\t\tBUG(\"negative j: %d\", j);\n+\t\t\t\tBUG(\"negative j: %\"PRIuMAX, j);\n \t\t\ti = pred[j];\n \t\t\tcolumn2row[j] = i;\n \t\t\tSWAP(j, row2column[i]);\n@@ -232,15 +232,15 @@ static void augmentation(size_t column_count,\n * i is `cost[j + column_count * i].\n */\n void compute_assignment(size_t column_count, size_t row_count,\n-\t\t\tint *cost,\n-\t\t\tint *column2row, int *row2column)\n+\t\t\tintmax_t *cost,\n+\t\t\tintmax_t *column2row, intmax_t *row2column)\n {\n-\tint *v;\n-\tint *free_row, free_count = 0, saved_free_count;\n+\tintmax_t *v;\n+\tintmax_t *free_row, free_count = 0, saved_free_count;\n \n \tassert(column_count > 1);\n-\tmemset(column2row, -1, sizeof(int) * column_count);\n-\tmemset(row2column, -1, sizeof(int) * row_count);\n+\tmemset(column2row, -1, sizeof(intmax_t) * column_count);\n+\tmemset(row2column, -1, sizeof(intmax_t) * row_count);\n \tALLOC_ARRAY(v, column_count);\n \n \tcolumns_reduction(column_count, row_count, cost, column2row,\ndiff --git a/linear-assignment.h b/linear-assignment.h\nindex 9ff055baac1..ee2726a7c8b 100644\n--- a/linear-assignment.h\n+++ b/linear-assignment.h\n@@ -14,10 +14,6 @@\n * row_count).\n */\n void compute_assignment(size_t column_count, size_t row_count,\n-\t\t\tint *cost,\n-\t\t\tint *column2row, int *row2column);\n-\n-/* The maximal cost in the cost matrix (to prevent integer overflows). */\n-#define COST_MAX (1<<16)\n-\n+\t\t\tintmax_t *cost,\n+\t\t\tintmax_t *column2row, intmax_t *row2column);\n #endif\ndiff --git a/range-diff.c b/range-diff.c\nindex b0ccb46ff4c..3442ebdd65c 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -302,20 +302,21 @@ static int diffsize(const char *a, const char *b)\n \t\treturn count;\n \n \terror(_(\"failed to generate diff\"));\n-\treturn COST_MAX;\n+\treturn INT_MAX;\n }\n \n static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\t\tint creation_factor)\n {\n \tsize_t n = st_add(a->nr, b->nr);\n-\tint *cost, c, *a2b, *b2a;\n+\tintmax_t *cost, c, *a2b, *b2a;\n \tsize_t i, j;\n \n \tCALLOC_ARRAY(cost, st_mult(n, n));\n \tCALLOC_ARRAY(a2b, n);\n \tCALLOC_ARRAY(b2a, n);\n \n+\n \tfor (i = 0; i < a->nr; i++) {\n \t\tstruct patch_util *a_util = a->items[i].util;\n \n@@ -327,12 +328,12 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\telse if (a_util->matching < 0 && b_util->matching < 0)\n \t\t\t\tc = diffsize(a_util->diff, b_util->diff);\n \t\t\telse\n-\t\t\t\tc = COST_MAX;\n+\t\t\t\tc = INT_MAX;\n \t\t\tcost[i + n * j] = c;\n \t\t}\n \n \t\tc = a_util->matching < 0 ?\n-\t\t\ta_util->diffsize * creation_factor / 100 : COST_MAX;\n+\t\t\ta_util->diffsize * creation_factor / 100 : INT_MAX;\n \t\tfor (j = b->nr; j < n; j++)\n \t\t\tcost[i + n * j] = c;\n \t}\n@@ -341,7 +342,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\tstruct patch_util *util = b->items[j].util;\n \n \t\tc = util->matching < 0 ?\n-\t\t\tutil->diffsize * creation_factor / 100 : COST_MAX;\n+\t\t\tutil->diffsize * creation_factor / 100 : INT_MAX;\n \t\tfor (i = a->nr; i < n; i++)\n \t\t\tcost[i + n * j] = c;\n \t}\n-- \n2.34.1.930.g0f9292b224d\n\n"},{"id":"443728","messageId":"YbLL/YWbjc/sPRyH@coredump.intra.peff.net","threadId":"57059","inReplyTo":"RFC-patch-02.10-bd7d014c531-20211209T191653Z-avarab@gmail.com","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-10T03:39:41Z","receivedAt":"2021-12-10T03:39:43Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 09, 2021 at 08:19:19PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> As documented in 320d0b493a2 (add helpers for detecting size_t\n> overflow, 2016-02-19) the arguments to st_mult() and st_add() \"must be\n> unsigned\".\n\nThis isn't correct. The comment that says \"must be unsigned\" is for\nunsigned_mult_overflows(). Which indeed would not work correctly for a\nsigned type. But st_add() is a separate function (and not a macro)\nbecause that means its arguments will always be promoted or converted\ninto a size_t. And so no matter what you pass it, it will always itself\npass a size_t into unsigned_mult_overflows().\n\n> In subsequent commits further overflows resulting in segfaults will be\n> fixed in this code, but let's start by removing this supposed guard\n> that does nothing except give us a false sense of\n> security. E.g. providing an \"n\" of INT_MAX here will result in \"1\" on\n> my system, causing us to write into memory.\n\nThis guard doesn't do nothing. Your patch here:\n\n> @@ -312,7 +312,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n> \tint *cost, c, *a2b, *b2a;\n> \tint i, j;\n> \n> -\tALLOC_ARRAY(cost, st_mult(n, n));\n> +\tALLOC_ARRAY(cost, n * n);\n> \tALLOC_ARRAY(a2b, n);\n> \tALLOC_ARRAY(b2a, n);\n\nmakes things strictly worse, because that \"n * n\" may overflow and cause\nus to under-allocate the array. You can see it in isolation with some\nextra code like this:\n\ndiff --git a/git.c b/git.c\nindex 5ff21be21f..63349e4b79 100644\n--- a/git.c\n+++ b/git.c\n@@ -850,11 +850,23 @@ static int run_argv(int *argcp, const char ***argv)\n \treturn done_alias;\n }\n \n+static void foo(void)\n+{\n+\tint n = 2 << 16;\n+\n+\tprintf(\"n = %d\\n\", n);\n+\tprintf(\"raw mult = %\"PRIuMAX\"\\n\", (uintmax_t)(n * n));\n+\tprintf(\"st_mult = %\"PRIuMAX\"\\n\", (uintmax_t)st_mult(n, n));\n+\texit(0);\n+}\n+\n int cmd_main(int argc, const char **argv)\n {\n \tconst char *cmd;\n \tint done_help = 0;\n \n+\tfoo();\n+\n \tcmd = argv[0];\n \tif (!cmd)\n \t\tcmd = \"git-help\";\n\nWith st_mult, we get the correct answer of 16GB. Without it, we end up\nwith 0!\n\nBack to the original code, if you generate a test setup like this:\n\ndiff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh\nindex e30bc48a29..f552d3086e 100755\n--- a/t/t3206-range-diff.sh\n+++ b/t/t3206-range-diff.sh\n@@ -772,4 +772,11 @@ test_expect_success '--left-only/--right-only' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'giant case' '\n+\ttest_commit base &&\n+\ttest_commit_bulk --ref=refs/heads/v1 --message=\"v1 commit %s\" 32768 &&\n+\ttest_commit_bulk --ref=refs/heads/v2 --message=\"v2 commit %s\" 32768 &&\n+\tgit range-diff base v1 v2\n+'\n+\n test_done\n\nThen we'd allocate a 0-length array for \"cost\" and segfault as soon as\nwe try to put anything in it. You can confirm this by applying your\npatch, running under gdb, and stopping at the xmalloc() call inside\nget_correspondences(). With st_mult(), then we come up with the correct\nvalue of 16GB (or complain about overflow on a 32-bit system).\n\nSo st_add() is working as advertised here; it's goal is just to make\nsure we never under-allocate. You are right, though, that the code after\nthat in get_correspondences() has trouble because of the signedness. If\nthe code used an \"unsigned int\", it would still be _wrong_. But when it\noverflowed, it would always come up with a value under 4GB. So it might\nproduce a wrong answer, but it couldn't possibly point outside the\nbounds of the array and cause a security problem.\n\nBut because it's a signed int, we overflow to a negative value and try\nto look at memory far before the start of the array. So I can see how it\nis tempting to argue that this st_mult() isn't really helping since we\nsegfault anyway. But I'd disagree. By correctly computing the value of\n16GB instead of \"0\", we know that the ALLOC_ARRAY() line is doing the\nright thing. And it may choose not to continue if it can't allocate\n16GB. That may happen because you don't have the RAM, but also because\nof GIT_ALLOC_LIMIT.\n\nSo if you set GIT_ALLOC_LIMIT=4g, for example, you are immune to the bug\nhere. We'd refuse the allocation and die there, which protects\ndownstream code from trying to fill in the array with bogus arithmetic.\n\nDropping the st_mult() does nothing to fix the actual problem (which is\nthat this function should use a more appropriate type), but introduces\nnew failure modes.\n\n-Peff\n"},{"id":"443741","messageId":"YbLQA820y+WuGwRU@coredump.intra.peff.net","threadId":"57059","inReplyTo":"RFC-patch-08.10-794d494bedd-20211209T191653Z-avarab@gmail.com","subject":"Re: [RFC PATCH 08/10] linear-assignment.c: detect signed add/mul on GCC and Clang","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-10T03:56:51Z","receivedAt":"2021-12-10T03:56:53Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 09, 2021 at 08:19:25PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> diff --git a/linear-assignment.c b/linear-assignment.c\n> index e9cec16132a..b6597b622c8 100644\n> --- a/linear-assignment.c\n> +++ b/linear-assignment.c\n> @@ -10,7 +10,14 @@ static inline int cost_index(int *cost, int a, int b, int c)\n> {\n> \tint r;\n> \n> +#if defined(__GNUC__) || defined(__clang__)\n> +\tif (__builtin_mul_overflow(a, c, &r))\n> +\t\tdie(_(\"integer overflow in cost[%d + %d * %c] multiplication\"), b, a, c);\n> +\tif (__builtin_add_overflow(b, r, &r))\n> +\t\tdie(_(\"integer overflow in cost[%d + ((%d * %d) = %d)] addition\"), b, a, c, r);\n> +#else\n> \tr = b + a * c;\n> +#endif\n\nI think having an inline #if here is the wrong direction. We already\nhave signed_add_overflows() which you could use for the second check.\nWe haven't needed signed_mult_overflows() yet, but we could add one.\n\nThose helpers don't use intrinsics yet. I think it would be reasonable\nto have them do so when they're available. One of the big reasons we\nhaven't done so yet is that they're not generally in hot paths. We\ngenerally use them while allocating, where the extra integer operations\nand conditional aren't a big deal.\n\nHere you depart from that and do the check on every index computation.\nI'm not completely opposed to that approach, but I think a simpler\nmethod (and what most spots have done so far) is to make sure the array\nallocation itself is computed correctly, and then have code which\naccesses it use an appropriate type to avoid overflow. In this case just\nusing size_t for the index computation would work, wouldn't it?\n\n(Likewise, if you really want a negative value, then ssize_t should be\nOK. It can't represent the full range of size_t, but if it would\noverflow that implies the original allocation was consuming more than\nhalf of the address space, which would have failed at the time of\nallocation).\n\nI do see that the following patch replaces this #if with similar helpers\nfrom gnulib, which is better. And if we are going to go the route of\nusing intrinsics in our helpers, then it might be a good idea to use\ngnulib's helpers to avoid portability pitfalls. But in that case we\nshould probably be converting over callers of the existing helpers (and\ngetting rid of those helpers).\n\nIMHO it isn't really worth it, though, if we can solve this just by\nswitching to a more appropriate type here (and assuming there's not a\nbig performance benefit to the other helper call sites).\n\n-Peff\n"},{"id":"443742","messageId":"YbLQxId7DLkbT7mQ@coredump.intra.peff.net","threadId":"57059","inReplyTo":"RFC-patch-10.10-46395080b64-20211209T191653Z-avarab@gmail.com","subject":"Re: [RFC PATCH 10/10] linear-assignment.c: use \"intmax_t\" instead of \"int\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-10T04:00:04Z","receivedAt":"2021-12-10T04:00:06Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Dec 09, 2021 at 08:19:27PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> Change the \"int\" type used by compute_assignment() to \"intmax_t\". On\n> 64 bit systems this changes the overflow \"die\" added in the preceding\n> commit (which before that was a segfault) to something that merely\n> takes a very long time and a lot of memory to run.\n> \n> On my relatively beefy system this completes:\n> \n> git -P range-diff --creation-factor=50 origin/master...git-for-windows/main\n> \n> In around 300 seconds, with a reported max RSS of just under 18GB, but\n> it does give you correct results for all ~50k commitsin that range.\n\nSo here you do what I think is the \"real\" fix. And at this point I\nsuspect that the overflow checks here:\n\n> -static inline int cost_index(int *cost, int a, int b, int c)\n> +static inline intmax_t cost_index(intmax_t *cost, intmax_t a, intmax_t b, intmax_t c)\n> {\n> -\tint r;\n> +\tintmax_t r;\n> \n> \tif (INT_MULTIPLY_WRAPV(a, c, &r))\n> -\t\tdie(_(\"integer overflow in cost[%d + %d * %d] multiplication\"), b, a, c);\n> +\t\tdie(_(\"integer overflow in cost[%\"PRIuMAX\" + %\"PRIuMAX\" * %\"PRIuMAX\"] multiplication\"), b, a, c);\n> \tif (INT_ADD_WRAPV(b, r, &r))\n> -\t\tdie(_(\"integer overflow in cost[%d + ((%d * %d) = %d)] addition\"), b, a, c, r);\n> +\t\tdie(_(\"integer overflow in cost[%\"PRIuMAX\" + ((%\"PRIuMAX\" * %\"PRIuMAX\") = %\"PRIuMAX\")] addition\"), b, a, c, r);\n> \n> \treturn r;\n\ncannot be triggered. We are indexing an array that is already limited to\nsize_t. So using that type should be sufficient (or else we have\nproblems even outside of overflow).\n\nAnd for that reason I'd probably pick size_t (or ssize_t; you don't need\nit in the hunk above, but presumably some of the other code cares about\nsignedness. And as I said earlier, it's effectively the same from a\nprotection standpoint).\n\n-Peff\n"},{"id":"443776","messageId":"211210.86lf0sdah1.gmgdl@evledraar.gmail.com","threadId":"57059","inReplyTo":"YbLL/YWbjc/sPRyH@coredump.intra.peff.net","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T10:22:59Z","receivedAt":"2021-12-10T10:23:59Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Thu, Dec 09 2021, Jeff King wrote:\n\n> On Thu, Dec 09, 2021 at 08:19:19PM +0100, Ævar Arnfjörð Bjarmason wrote:\n>\n>> As documented in 320d0b493a2 (add helpers for detecting size_t\n>> overflow, 2016-02-19) the arguments to st_mult() and st_add() \"must be\n>> unsigned\".\n>\n> This isn't correct. The comment that says \"must be unsigned\" is for\n> unsigned_mult_overflows(). Which indeed would not work correctly for a\n> signed type. But st_add() is a separate function (and not a macro)\n> because that means its arguments will always be promoted or converted\n> into a size_t. And so no matter what you pass it, it will always itself\n> pass a size_t into unsigned_mult_overflows().\n>\n>> In subsequent commits further overflows resulting in segfaults will be\n>> fixed in this code, but let's start by removing this supposed guard\n>> that does nothing except give us a false sense of\n>> security. E.g. providing an \"n\" of INT_MAX here will result in \"1\" on\n>> my system, causing us to write into memory.\n>\n> This guard doesn't do nothing. Your patch here:\n>\n>> @@ -312,7 +312,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n>> \tint *cost, c, *a2b, *b2a;\n>> \tint i, j;\n>> \n>> -\tALLOC_ARRAY(cost, st_mult(n, n));\n>> +\tALLOC_ARRAY(cost, n * n);\n>> \tALLOC_ARRAY(a2b, n);\n>> \tALLOC_ARRAY(b2a, n);\n>\n> makes things strictly worse, because that \"n * n\" may overflow and cause\n> us to under-allocate the array. You can see it in isolation with some\n> extra code like this:\n>\n> diff --git a/git.c b/git.c\n> index 5ff21be21f..63349e4b79 100644\n> --- a/git.c\n> +++ b/git.c\n> @@ -850,11 +850,23 @@ static int run_argv(int *argcp, const char ***argv)\n> \treturn done_alias;\n> }\n> \n> +static void foo(void)\n> +{\n> +\tint n = 2 << 16;\n> +\n> +\tprintf(\"n = %d\\n\", n);\n> +\tprintf(\"raw mult = %\"PRIuMAX\"\\n\", (uintmax_t)(n * n));\n> +\tprintf(\"st_mult = %\"PRIuMAX\"\\n\", (uintmax_t)st_mult(n, n));\n> +\texit(0);\n> +}\n> +\n> int cmd_main(int argc, const char **argv)\n> {\n> \tconst char *cmd;\n> \tint done_help = 0;\n> \n> +\tfoo();\n> +\n> \tcmd = argv[0];\n> \tif (!cmd)\n> \t\tcmd = \"git-help\";\n>\n> With st_mult, we get the correct answer of 16GB. Without it, we end up\n> with 0!\n>\n> Back to the original code, if you generate a test setup like this:\n>\n> diff --git a/t/t3206-range-diff.sh b/t/t3206-range-diff.sh\n> index e30bc48a29..f552d3086e 100755\n> --- a/t/t3206-range-diff.sh\n> +++ b/t/t3206-range-diff.sh\n> @@ -772,4 +772,11 @@ test_expect_success '--left-only/--right-only' '\n> \ttest_cmp expect actual\n> '\n> \n> +test_expect_success 'giant case' '\n> +\ttest_commit base &&\n> +\ttest_commit_bulk --ref=refs/heads/v1 --message=\"v1 commit %s\" 32768 &&\n> +\ttest_commit_bulk --ref=refs/heads/v2 --message=\"v2 commit %s\" 32768 &&\n> +\tgit range-diff base v1 v2\n> +'\n> +\n> test_done\n>\n> Then we'd allocate a 0-length array for \"cost\" and segfault as soon as\n> we try to put anything in it. You can confirm this by applying your\n> patch, running under gdb, and stopping at the xmalloc() call inside\n> get_correspondences(). With st_mult(), then we come up with the correct\n> value of 16GB (or complain about overflow on a 32-bit system).\n>\n> So st_add() is working as advertised here; it's goal is just to make\n> sure we never under-allocate. You are right, though, that the code after\n> that in get_correspondences() has trouble because of the signedness. If\n> the code used an \"unsigned int\", it would still be _wrong_. But when it\n> overflowed, it would always come up with a value under 4GB. So it might\n> produce a wrong answer, but it couldn't possibly point outside the\n> bounds of the array and cause a security problem.\n>\n> But because it's a signed int, we overflow to a negative value and try\n> to look at memory far before the start of the array. So I can see how it\n> is tempting to argue that this st_mult() isn't really helping since we\n> segfault anyway. But I'd disagree. By correctly computing the value of\n> 16GB instead of \"0\", we know that the ALLOC_ARRAY() line is doing the\n> right thing. And it may choose not to continue if it can't allocate\n> 16GB. That may happen because you don't have the RAM, but also because\n> of GIT_ALLOC_LIMIT.\n>\n> So if you set GIT_ALLOC_LIMIT=4g, for example, you are immune to the bug\n> here. We'd refuse the allocation and die there, which protects\n> downstream code from trying to fill in the array with bogus arithmetic.\n>\n> Dropping the st_mult() does nothing to fix the actual problem (which is\n> that this function should use a more appropriate type), but introduces\n> new failure modes.\n\nYes you're entirely right. I had some stupid blinders on while writing\nthis. FWIW I think I was experimenting with some local macros and\nconflated a testing of the overflow of n*n in gdb with the caste'd\nversion, which you rightly point out here won't have the overflow issue\nat all. Sorry.\n"},{"id":"443792","messageId":"YbM85W3N0ySi5k+H@coredump.intra.peff.net","threadId":"57059","inReplyTo":"211210.86lf0sdah1.gmgdl@evledraar.gmail.com","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-10T11:41:25Z","receivedAt":"2021-12-10T11:41:28Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 10, 2021 at 11:22:59AM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> > Dropping the st_mult() does nothing to fix the actual problem (which is\n> > that this function should use a more appropriate type), but introduces\n> > new failure modes.\n> \n> Yes you're entirely right. I had some stupid blinders on while writing\n> this. FWIW I think I was experimenting with some local macros and\n> conflated a testing of the overflow of n*n in gdb with the caste'd\n> version, which you rightly point out here won't have the overflow issue\n> at all. Sorry.\n\nI'm not sure if this is helpful or not, but this is the minimal fix I\ncame up with that runs the testcase I showed earlier. It's basically\njust swapping out \"int\" for \"ssize_t\" for any variables we use to index\nthe arrays (though note a few are themselves held in arrays, and we have\nto cross some function boundaries).\n\nI won't be surprised if it doesn't hit all cases, or if it even hits a\nfew it doesn't need to (e.g., should \"phase\" be dragged along with \"i\"\nand \"j\" in the first hunk?). I mostly did guess-and-check on the\ntest-case, fixing whatever segfaulted and then running again until it\nworked. I didn't even really read the code very carefully.\n\nI think you _did_ do more of that careful reading, and broke down the\nrefactorings into separate patches in your series. Which is good. So I\nthink what we'd want is to pick out those parts of your series that end\nup switching the variable type. My goal in sharing this here is just to\nshow that the end result of the fix can (and IMHO should) be around this\nsame order of magnitude.\n\n---\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex ecffc09be6..3efa30c50b 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -13,11 +13,11 @@\n * i is `cost[j + column_count * i].\n */\n void compute_assignment(int column_count, int row_count, int *cost,\n-\t\t\tint *column2row, int *row2column)\n+\t\t\tssize_t *column2row, ssize_t *row2column)\n {\n \tint *v, *d;\n \tint *free_row, free_count = 0, saved_free_count, *pred, *col;\n-\tint i, j, phase;\n+\tssize_t i, j, phase;\n \n \tif (column_count < 2) {\n \t\tmemset(column2row, 0, sizeof(int) * column_count);\n@@ -31,7 +31,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \n \t/* column reduction */\n \tfor (j = column_count - 1; j >= 0; j--) {\n-\t\tint i1 = 0;\n+\t\tssize_t i1 = 0;\n \n \t\tfor (i = 1; i < row_count; i++)\n \t\t\tif (COST(j, i1) > COST(j, i))\n@@ -51,7 +51,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \t/* reduction transfer */\n \tALLOC_ARRAY(free_row, row_count);\n \tfor (i = 0; i < row_count; i++) {\n-\t\tint j1 = row2column[i];\n+\t\tssize_t j1 = row2column[i];\n \t\tif (j1 == -1)\n \t\t\tfree_row[free_count++] = i;\n \t\telse if (j1 < -1)\n@@ -74,13 +74,13 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \n \t/* augmenting row reduction */\n \tfor (phase = 0; phase < 2; phase++) {\n-\t\tint k = 0;\n+\t\tssize_t k = 0;\n \n \t\tsaved_free_count = free_count;\n \t\tfree_count = 0;\n \t\twhile (k < saved_free_count) {\n \t\t\tint u1, u2;\n-\t\t\tint j1 = 0, j2, i0;\n+\t\t\tssize_t j1 = 0, j2, i0;\n \n \t\t\ti = free_row[k++];\n \t\t\tu1 = COST(j1, i) - v[j1];\n@@ -130,7 +130,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \tALLOC_ARRAY(pred, column_count);\n \tALLOC_ARRAY(col, column_count);\n \tfor (free_count = 0; free_count < saved_free_count; free_count++) {\n-\t\tint i1 = free_row[free_count], low = 0, up = 0, last, k;\n+\t\tssize_t i1 = free_row[free_count], low = 0, up = 0, last, k;\n \t\tint min, c, u1;\n \n \t\tfor (j = 0; j < column_count; j++) {\n@@ -192,7 +192,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \t\t/* augmentation */\n \t\tdo {\n \t\t\tif (j < 0)\n-\t\t\t\tBUG(\"negative j: %d\", j);\n+\t\t\t\tBUG(\"negative j: %\"PRIdMAX, (intmax_t)j);\n \t\t\ti = pred[j];\n \t\t\tcolumn2row[j] = i;\n \t\t\tSWAP(j, row2column[i]);\ndiff --git a/linear-assignment.h b/linear-assignment.h\nindex 1dfea76629..7005521d61 100644\n--- a/linear-assignment.h\n+++ b/linear-assignment.h\n@@ -14,7 +14,7 @@\n * row_count).\n */\n void compute_assignment(int column_count, int row_count, int *cost,\n-\t\t\tint *column2row, int *row2column);\n+\t\t\tssize_t *column2row, ssize_t *row2column);\n \n /* The maximal cost in the cost matrix (to prevent integer overflows). */\n #define COST_MAX (1<<16)\ndiff --git a/range-diff.c b/range-diff.c\nindex cac89a2f4f..f1e1e27bf9 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -308,9 +308,10 @@ static int diffsize(const char *a, const char *b)\n static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\t\tint creation_factor)\n {\n-\tint n = a->nr + b->nr;\n-\tint *cost, c, *a2b, *b2a;\n-\tint i, j;\n+\tsize_t n = a->nr + b->nr;\n+\tint *cost, c;\n+\tssize_t *a2b, *b2a;\n+\tsize_t i, j;\n \n \tALLOC_ARRAY(cost, st_mult(n, n));\n \tALLOC_ARRAY(a2b, n);\n"},{"id":"443794","messageId":"RFC-patch-v2-1.5-068c203adc6-20211210T122901Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com","subject":"[RFC PATCH v2 1/5] range-diff: zero out elements in \"cost\" first","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T12:30:38Z","receivedAt":"2021-12-10T12:30:50Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Have the get_correspondences() function use CALLOC_ARRAY instead of\nlooping over the newly allocated \"cost\" to zero out some of its\nelements.\n\nThe for-loop that zero'd out elements in \"cost\" wasn't the first loop\nin that function, nor did it cover all of its elements, but regardless\nof that this change doesn't affect its end-state. None of the\nfor-loops touched the same items in the array, so we could have (and\nan earlier WIP version of this change did) moved the for-loop we're\ndeleting to come first in get_correspondences().\n\nThis can be seen from a careful reading of this code added in in\nd9c66f0b5bf (range-diff: first rudimentary implementation,\n2018-08-13) (as well as adding some printf-debugging) we'll set all\nelements in the in the \"n * n\" allocated array. That's \"n = A+B\" where\n\"A\" and \"B\" are the number of commits in our respective ranges.\n\nSo let's just allocate this with CALLOC_ARRAY(), and skip these two\nfor-loops. Furthermore let's remove the early exit condition from\ncompute_assignment() in favor of an assert that it must be called with\n\"column_count > 1\", then \"get_correspondences()\" can skip calling it\nwhen no further filling of the \"a2b\" and \"b2a\" arrays is needed.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 7 +------\n range-diff.c | 13 +++++--------\n 2 files changed, 6 insertions(+), 14 deletions(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex ecffc09be6e..0c0786a63b6 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -19,12 +19,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \tint *free_row, free_count = 0, saved_free_count, *pred, *col;\n \tint i, j, phase;\n \n-\tif (column_count < 2) {\n-\t\tmemset(column2row, 0, sizeof(int) * column_count);\n-\t\tmemset(row2column, 0, sizeof(int) * row_count);\n-\t\treturn;\n-\t}\n-\n+\tassert(column_count > 1);\n \tmemset(column2row, -1, sizeof(int) * column_count);\n \tmemset(row2column, -1, sizeof(int) * row_count);\n \tALLOC_ARRAY(v, column_count);\ndiff --git a/range-diff.c b/range-diff.c\nindex cac89a2f4f2..b2fcc6f66e0 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -312,9 +312,9 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \tint *cost, c, *a2b, *b2a;\n \tint i, j;\n \n-\tALLOC_ARRAY(cost, st_mult(n, n));\n-\tALLOC_ARRAY(a2b, n);\n-\tALLOC_ARRAY(b2a, n);\n+\tCALLOC_ARRAY(cost, st_mult(n, n));\n+\tCALLOC_ARRAY(a2b, n);\n+\tCALLOC_ARRAY(b2a, n);\n \n \tfor (i = 0; i < a->nr; i++) {\n \t\tstruct patch_util *a_util = a->items[i].util;\n@@ -346,11 +346,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\tcost[i + n * j] = c;\n \t}\n \n-\tfor (i = a->nr; i < n; i++)\n-\t\tfor (j = b->nr; j < n; j++)\n-\t\t\tcost[i + n * j] = 0;\n-\n-\tcompute_assignment(n, n, cost, a2b, b2a);\n+\tif (n > 1)\n+\t\tcompute_assignment(n, n, cost, a2b, b2a);\n \n \tfor (i = 0; i < a->nr; i++)\n \t\tif (a2b[i] >= 0 && a2b[i] < b->nr) {\n-- \n2.34.1.932.g36842105b61\n\n"},{"id":"443795","messageId":"RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"[RFC PATCH v2 0/5] range-diff: fix segfault due to integer overflow","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T12:30:37Z","receivedAt":"2021-12-10T12:30:50Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Now a much smaller and hopefully more sensible fix for an overflow in\nrange-diff, thanks a lot to Jeff King for comments on the previous\n(bad) direction in v1.\n\nÆvar Arnfjörð Bjarmason (5):\n range-diff: zero out elements in \"cost\" first\n linear-assignment.c: split up compute_assignment() function\n linear-assignment.c: take \"size_t\", not \"int\" for *_count\n range-diff.c: rename \"n\" to \"column_count\" in get_correspondences()\n range-diff: fix integer overflow & segfault on cost[i + n * j]\n\n linear-assignment.c | 110 +++++++++++++++++++++++++++++++-------------\n linear-assignment.h | 20 +++++++-\n range-diff.c | 25 +++++-----\n 3 files changed, 107 insertions(+), 48 deletions(-)\n\nRange-diff against v1:\n 1: 7c929096381 < -: ----------- string-list API: change \"nr\" and \"alloc\" to \"size_t\"\n 2: bd7d014c531 < -: ----------- range-diff.c: don't use st_mult() for signed \"int\"\n 3: 183418f1223 < -: ----------- range-diff.c: use \"size_t\" to refer to \"struct string_list\"'s \"nr\"\n 4: fe9dcb2d453 ! 1: 068c203adc6 range-diff: zero out elements in \"cost\" first\n @@ linear-assignment.c: void compute_assignment(int column_count, int row_count, in\n ## range-diff.c ##\n @@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,\n \tint *cost, c, *a2b, *b2a;\n - \tsize_t i, j;\n + \tint i, j;\n \n -\tALLOC_ARRAY(cost, st_mult(n, n));\n -\tALLOC_ARRAY(a2b, n);\n 5: 0e1e2d107cd = 2: 2233872545e linear-assignment.c: split up compute_assignment() function\n 6: 9b697720e00 = 3: 580b76c0759 linear-assignment.c: take \"size_t\", not \"int\" for *_count\n10: 46395080b64 ! 4: f8bbe1954fc linear-assignment.c: use \"intmax_t\" instead of \"int\"\n @@ Metadata\n Author: Ævar Arnfjörð Bjarmason \n \n ## Commit message ##\n - linear-assignment.c: use \"intmax_t\" instead of \"int\"\n + range-diff.c: rename \"n\" to \"column_count\" in get_correspondences()\n \n - Change the \"int\" type used by compute_assignment() to \"intmax_t\". On\n - 64 bit systems this changes the overflow \"die\" added in the preceding\n - commit (which before that was a segfault) to something that merely\n - takes a very long time and a lot of memory to run.\n -\n - On my relatively beefy system this completes:\n -\n - git -P range-diff --creation-factor=50 origin/master...git-for-windows/main\n -\n - In around 300 seconds, with a reported max RSS of just under 18GB, but\n - it does give you correct results for all ~50k commitsin that range.\n + In preparation for using the COST macro in linear-assignment.c rename\n + the \"n\" variable, it assumes that the \"n\" in \"a + n * b\" is named\n + \"column_count\".\n \n Signed-off-by: Ævar Arnfjörð Bjarmason \n \n - ## linear-assignment.c ##\n -@@\n - #include \"linear-assignment.h\"\n - #include \"compat/gnulib/intprops.h\"\n - \n --static inline int cost_index(int *cost, int a, int b, int c)\n -+static inline intmax_t cost_index(intmax_t *cost, intmax_t a, intmax_t b, intmax_t c)\n - {\n --\tint r;\n -+\tintmax_t r;\n - \n - \tif (INT_MULTIPLY_WRAPV(a, c, &r))\n --\t\tdie(_(\"integer overflow in cost[%d + %d * %d] multiplication\"), b, a, c);\n -+\t\tdie(_(\"integer overflow in cost[%\"PRIuMAX\" + %\"PRIuMAX\" * %\"PRIuMAX\"] multiplication\"), b, a, c);\n - \tif (INT_ADD_WRAPV(b, r, &r))\n --\t\tdie(_(\"integer overflow in cost[%d + ((%d * %d) = %d)] addition\"), b, a, c, r);\n -+\t\tdie(_(\"integer overflow in cost[%\"PRIuMAX\" + ((%\"PRIuMAX\" * %\"PRIuMAX\") = %\"PRIuMAX\")] addition\"), b, a, c, r);\n - \n - \treturn r;\n - }\n -@@ linear-assignment.c: static inline int cost_index(int *cost, int a, int b, int c)\n - #define COST(column, row) cost[cost_index(cost, column_count, column, row)]\n - \n - static void columns_reduction(size_t column_count, size_t row_count,\n --\t\t\t int *cost,\n --\t\t\t int *column2row, int *row2column,\n --\t\t\t int *v)\n -+\t\t\t intmax_t *cost,\n -+\t\t\t intmax_t *column2row, intmax_t *row2column,\n -+\t\t\t intmax_t *v)\n - {\n --\tint i, j;\n -+\tintmax_t i, j;\n - \n - \t/* column reduction */\n - \tfor (j = column_count - 1; j >= 0; j--) {\n --\t\tint i1 = 0;\n -+\t\tintmax_t i1 = 0;\n - \n - \t\tfor (i = 1; i < row_count; i++)\n - \t\t\tif (COST(j, i1) > COST(j, i))\n -@@ linear-assignment.c: static void columns_reduction(size_t column_count, size_t row_count,\n - }\n - \n - static void reduction_transfer(size_t column_count, size_t row_count,\n --\t\t\t int *cost,\n --\t\t\t int *free_row, int *free_count,\n --\t\t\t int *column2row, int *row2column,\n --\t\t\t int *v)\n -+\t\t\t intmax_t *cost,\n -+\t\t\t intmax_t *free_row, intmax_t *free_count,\n -+\t\t\t intmax_t *column2row, intmax_t *row2column,\n -+\t\t\t intmax_t *v)\n - {\n --\tint i, j;\n -+\tintmax_t i, j;\n - \n - \t/* reduction transfer */\n - \tfor (i = 0; i < row_count; i++) {\n --\t\tint j1 = row2column[i];\n -+\t\tintmax_t j1 = row2column[i];\n - \t\tif (j1 == -1)\n - \t\t\tfree_row[(*free_count)++] = i;\n - \t\telse if (j1 < -1)\n - \t\t\trow2column[i] = -2 - j1;\n - \t\telse {\n --\t\t\tint min = COST(!j1, i) - v[!j1];\n -+\t\t\tintmax_t min = COST(!j1, i) - v[!j1];\n - \t\t\tfor (j = 1; j < column_count; j++)\n - \t\t\t\tif (j != j1 && min > COST(j, i) - v[j])\n - \t\t\t\t\tmin = COST(j, i) - v[j];\n -@@ linear-assignment.c: static void reduction_transfer(size_t column_count, size_t row_count,\n - }\n - \n - static void augmenting_row_reduction(size_t column_count,\n --\t\t\t\t int *cost,\n --\t\t\t\t int *column2row, int *row2column,\n --\t\t\t\t int *free_row, int *free_count, int *saved_free_count,\n --\t\t\t\t int *v)\n -+\t\t\t\t intmax_t *cost,\n -+\t\t\t\t intmax_t *column2row, intmax_t *row2column,\n -+\t\t\t\t intmax_t *free_row, intmax_t *free_count, intmax_t *saved_free_count,\n -+\t\t\t\t intmax_t *v)\n - {\n - \tint phase;\n - \n - \t/* augmenting row reduction */\n - \tfor (phase = 0; phase < 2; phase++) {\n --\t\tint i;\n --\t\tint k = 0;\n -+\t\tintmax_t i;\n -+\t\tintmax_t k = 0;\n - \n - \t\t*saved_free_count = *free_count;\n - \t\t*free_count = 0;\n - \t\twhile (k < *saved_free_count) {\n --\t\t\tint j;\n --\t\t\tint u1, u2;\n --\t\t\tint j1 = 0, j2, i0;\n -+\t\t\tintmax_t j;\n -+\t\t\tintmax_t u1, u2;\n -+\t\t\tintmax_t j1 = 0, j2, i0;\n - \n - \t\t\ti = free_row[k++];\n - \t\t\tu1 = COST(j1, i) - v[j1];\n - \t\t\tj2 = -1;\n --\t\t\tu2 = INT_MAX;\n -+\t\t\tu2 = INTMAX_MAX;\n - \t\t\tfor (j = 1; j < column_count; j++) {\n --\t\t\t\tint c = COST(j, i) - v[j];\n -+\t\t\t\tintmax_t c = COST(j, i) - v[j];\n - \t\t\t\tif (u2 > c) {\n - \t\t\t\t\tif (u1 < c) {\n - \t\t\t\t\t\tu2 = c;\n -@@ linear-assignment.c: static void augmenting_row_reduction(size_t column_count,\n - }\n - \n - static void augmentation(size_t column_count,\n --\t\t\t int *cost,\n --\t\t\t int *column2row, int *row2column,\n --\t\t\t int *free_row, int free_count,\n --\t\t\t int *v)\n -+\t\t\t intmax_t *cost,\n -+\t\t\t intmax_t *column2row, intmax_t *row2column,\n -+\t\t\t intmax_t *free_row, intmax_t free_count,\n -+\t\t\t intmax_t *v)\n - {\n --\tint i, j;\n --\tint *d;\n --\tint *pred, *col;\n --\tint saved_free_count;\n -+\tintmax_t i, j;\n -+\tintmax_t *d;\n -+\tintmax_t *pred, *col;\n -+\tintmax_t saved_free_count;\n - \n - \t/* augmentation */\n - \tsaved_free_count = free_count;\n -@@ linear-assignment.c: static void augmentation(size_t column_count,\n - \tALLOC_ARRAY(pred, column_count);\n - \tALLOC_ARRAY(col, column_count);\n - \tfor (free_count = 0; free_count < saved_free_count; free_count++) {\n --\t\tint i1 = free_row[free_count], low = 0, up = 0, last, k;\n --\t\tint min, c, u1;\n -+\t\tintmax_t i1 = free_row[free_count], low = 0, up = 0, last, k;\n -+\t\tintmax_t min, c, u1;\n - \n - \t\tfor (j = 0; j < column_count; j++) {\n - \t\t\td[j] = COST(j, i1) - v[j];\n -@@ linear-assignment.c: static void augmentation(size_t column_count,\n - \n - \t\t\t/* scan a row */\n - \t\t\tdo {\n --\t\t\t\tint j1 = col[low++];\n -+\t\t\t\tintmax_t j1 = col[low++];\n - \n - \t\t\t\ti = column2row[j1];\n - \t\t\t\tu1 = COST(j1, i) - v[j1] - min;\n -@@ linear-assignment.c: static void augmentation(size_t column_count,\n - update:\n - \t\t/* updating of the column pieces */\n - \t\tfor (k = 0; k < last; k++) {\n --\t\t\tint j1 = col[k];\n -+\t\t\tintmax_t j1 = col[k];\n - \t\t\tv[j1] += d[j1] - min;\n - \t\t}\n - \n - \t\t/* augmentation */\n - \t\tdo {\n - \t\t\tif (j < 0)\n --\t\t\t\tBUG(\"negative j: %d\", j);\n -+\t\t\t\tBUG(\"negative j: %\"PRIuMAX, j);\n - \t\t\ti = pred[j];\n - \t\t\tcolumn2row[j] = i;\n - \t\t\tSWAP(j, row2column[i]);\n -@@ linear-assignment.c: static void augmentation(size_t column_count,\n - * i is `cost[j + column_count * i].\n - */\n - void compute_assignment(size_t column_count, size_t row_count,\n --\t\t\tint *cost,\n --\t\t\tint *column2row, int *row2column)\n -+\t\t\tintmax_t *cost,\n -+\t\t\tintmax_t *column2row, intmax_t *row2column)\n - {\n --\tint *v;\n --\tint *free_row, free_count = 0, saved_free_count;\n -+\tintmax_t *v;\n -+\tintmax_t *free_row, free_count = 0, saved_free_count;\n - \n - \tassert(column_count > 1);\n --\tmemset(column2row, -1, sizeof(int) * column_count);\n --\tmemset(row2column, -1, sizeof(int) * row_count);\n -+\tmemset(column2row, -1, sizeof(intmax_t) * column_count);\n -+\tmemset(row2column, -1, sizeof(intmax_t) * row_count);\n - \tALLOC_ARRAY(v, column_count);\n - \n - \tcolumns_reduction(column_count, row_count, cost, column2row,\n -\n - ## linear-assignment.h ##\n -@@\n - * row_count).\n - */\n - void compute_assignment(size_t column_count, size_t row_count,\n --\t\t\tint *cost,\n --\t\t\tint *column2row, int *row2column);\n --\n --/* The maximal cost in the cost matrix (to prevent integer overflows). */\n --#define COST_MAX (1<<16)\n --\n -+\t\t\tintmax_t *cost,\n -+\t\t\tintmax_t *column2row, intmax_t *row2column);\n - #endif\n -\n ## range-diff.c ##\n @@ range-diff.c: static int diffsize(const char *a, const char *b)\n - \t\treturn count;\n - \n - \terror(_(\"failed to generate diff\"));\n --\treturn COST_MAX;\n -+\treturn INT_MAX;\n - }\n - \n static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\t\tint creation_factor)\n {\n - \tsize_t n = st_add(a->nr, b->nr);\n --\tint *cost, c, *a2b, *b2a;\n -+\tintmax_t *cost, c, *a2b, *b2a;\n - \tsize_t i, j;\n - \n - \tCALLOC_ARRAY(cost, st_mult(n, n));\n - \tCALLOC_ARRAY(a2b, n);\n - \tCALLOC_ARRAY(b2a, n);\n +-\tint n = a->nr + b->nr;\n ++\tint column_count = st_add(a->nr, b->nr);\n + \tint *cost, c, *a2b, *b2a;\n + \tint i, j;\n + \n +-\tCALLOC_ARRAY(cost, st_mult(n, n));\n +-\tCALLOC_ARRAY(a2b, n);\n +-\tCALLOC_ARRAY(b2a, n);\n ++\tCALLOC_ARRAY(cost, st_mult(column_count, column_count));\n ++\tCALLOC_ARRAY(a2b, column_count);\n ++\tCALLOC_ARRAY(b2a, column_count);\n \n -+\n \tfor (i = 0; i < a->nr; i++) {\n \t\tstruct patch_util *a_util = a->items[i].util;\n - \n @@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,\n - \t\t\telse if (a_util->matching < 0 && b_util->matching < 0)\n \t\t\t\tc = diffsize(a_util->diff, b_util->diff);\n \t\t\telse\n --\t\t\t\tc = COST_MAX;\n -+\t\t\t\tc = INT_MAX;\n - \t\t\tcost[i + n * j] = c;\n + \t\t\t\tc = COST_MAX;\n +-\t\t\tcost[i + n * j] = c;\n ++\t\t\tcost[i + column_count * j] = c;\n \t\t}\n \n \t\tc = a_util->matching < 0 ?\n --\t\t\ta_util->diffsize * creation_factor / 100 : COST_MAX;\n -+\t\t\ta_util->diffsize * creation_factor / 100 : INT_MAX;\n - \t\tfor (j = b->nr; j < n; j++)\n - \t\t\tcost[i + n * j] = c;\n + \t\t\ta_util->diffsize * creation_factor / 100 : COST_MAX;\n +-\t\tfor (j = b->nr; j < n; j++)\n +-\t\t\tcost[i + n * j] = c;\n ++\t\tfor (j = b->nr; j < column_count; j++)\n ++\t\t\tcost[i + column_count * j] = c;\n \t}\n + \n + \tfor (j = 0; j < b->nr; j++) {\n @@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,\n - \t\tstruct patch_util *util = b->items[j].util;\n \n \t\tc = util->matching < 0 ?\n --\t\t\tutil->diffsize * creation_factor / 100 : COST_MAX;\n -+\t\t\tutil->diffsize * creation_factor / 100 : INT_MAX;\n - \t\tfor (i = a->nr; i < n; i++)\n - \t\t\tcost[i + n * j] = c;\n + \t\t\tutil->diffsize * creation_factor / 100 : COST_MAX;\n +-\t\tfor (i = a->nr; i < n; i++)\n +-\t\t\tcost[i + n * j] = c;\n ++\t\tfor (i = a->nr; i < column_count; i++)\n ++\t\t\tcost[i + column_count * j] = c;\n \t}\n + \n +-\tif (n > 1)\n +-\t\tcompute_assignment(n, n, cost, a2b, b2a);\n ++\tif (column_count > 1)\n ++\t\tcompute_assignment(column_count, column_count, cost, a2b, b2a);\n + \n + \tfor (i = 0; i < a->nr; i++)\n + \t\tif (a2b[i] >= 0 && a2b[i] < b->nr) {\n 7: a82771413f7 ! 5: 9194965635a linear-assignment.c: convert a macro to a \"static inline\" function\n @@ Metadata\n Author: Ævar Arnfjörð Bjarmason \n \n ## Commit message ##\n - linear-assignment.c: convert a macro to a \"static inline\" function\n + range-diff: fix integer overflow & segfault on cost[i + n * j]\n \n - Change the COST() macro to be a \"static inline\" function. On GCC this\n - makes no difference in performance, but this improves the readability\n - of the function. In a subsequent commit we'll make use of this to\n - extend this function with overflow detection.\n + in preceding commits the \"column_count\" and the \"int*\"'s we malloc()\n + were changed to track their length with a size_t, so we're able to\n + track as many \"cost\" items as malloc() will give us.\n +\n + But we'd still segfault on relatively large range comparisons,\n + e.g. this would segfault:\n +\n + git -P range-diff --creation-factor=50 origin/master...git-for-windows/main\n +\n + The reason for that is that we'd still use integer types to compute an\n + array index into the \"cost\" array, which would overflow. The result of\n + a signed overflow in C is undefined, but on my system it'll result in\n + a negative number, and a prompt segfault as we'll try to access a\n + negative array index.\n +\n + Luckily we used the COST() macro in linear-assignment.c already for\n + all of these lookups, and in a preceding commit we renamed \"n\" in\n + \"range-diff.c\"'s get_correspondences() to \"column_count\" in\n + preparation for using it here.\n +\n + So let's use it for the three occurrences of \"cost\" indexing in\n + range-diff.c, and have the COST() macro itself do overflow checking\n + with st_mult() and st_add(). Due to the cast to \"size_t\" from \"int\"\n + we'll avoid the segfault, and will end up correctly pointing to the\n + relevant \"int *\".\n +\n + It's not important that we use the new cost_offset() inline function\n + here, we could also use the st_*() macros inline. By using it we'll\n + get a more meaningful backtrace in a debugger to the relevant\n + addition/multiplication line if we end up calling die() here.\n +\n + It's still possible for us to overflow even with this change, that's\n + because the iteration variables (such as \"i\" and \"j\" in this diff\n + context are all \"int\"), even if we changed those to \"size_t\" or\n + \"intmax_t\" (not trivial, as we depend on them being negative in some\n + places) the underlying \"struct string_list\"'s \"nr\" member is an\n + \"unsigned int\", which would eventually overflow.\n +\n + However the danger of that overflow isn't as great, as we were\n + overflowing on \"i + column_count * j\" before this change, it'll\n + require a much bigger range for us to have an integer overflow on the\n + number of commits we're processing.\n +\n + We're unlikely to encounter a 2-4 billion commit history on 32 bit\n + platforms. Even if we did one of the types in the underlying object\n + machinery would probably overflow before we overflowed here. So let's\n + punt that for now. If we're ever going to solve that issue [1] to\n + change the \"struct string_list\"'s \"nr\" member to a \"size_t\" might be a\n + good start.\n +\n + 1. https://lore.kernel.org/git/RFC-patch-01.10-7c929096381-20211209T191653Z-avarab@gmail.com/\n \n Signed-off-by: Ævar Arnfjörð Bjarmason \n \n @@ linear-assignment.c\n #include \"linear-assignment.h\"\n \n -#define COST(column, row) cost[(column) + column_count * (row)]\n -+static inline int cost_index(int *cost, int a, int b, int c)\n +-\n + static void columns_reduction(size_t column_count, size_t row_count,\n + \t\t\t int *cost,\n + \t\t\t int *column2row, int *row2column,\n +\n + ## linear-assignment.h ##\n +@@ linear-assignment.h: void compute_assignment(size_t column_count, size_t row_count,\n + \t\t\tint *cost,\n + \t\t\tint *column2row, int *row2column);\n + \n ++/**\n ++ * Get an overflow-proof offset into the \"cost\" array.\n ++ */\n ++static inline size_t cost_offset(const size_t column,\n ++\t\t\t\t const size_t column_count, const size_t row)\n +{\n -+\tint r;\n ++\tconst size_t a = st_mult(column_count, row);\n ++\tconst size_t b = st_add(column, a);\n +\n -+\tr = b + a * c;\n -+\n -+\treturn r;\n ++\treturn b;\n +}\n +\n -+#define COST(column, row) cost[cost_index(cost, column_count, column, row)]\n ++/**\n ++ * Convenience macro for doing the cost[] lookup using cost_offset().\n ++ */\n ++#define COST(column, row) cost[cost_offset((column), (column_count), (row))]\n ++\n + /* The maximal cost in the cost matrix (to prevent integer overflows). */\n + #define COST_MAX (1<<16)\n \n - static void columns_reduction(size_t column_count, size_t row_count,\n - \t\t\t int *cost,\n +\n + ## range-diff.c ##\n +@@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,\n + \t\t\t\tc = diffsize(a_util->diff, b_util->diff);\n + \t\t\telse\n + \t\t\t\tc = COST_MAX;\n +-\t\t\tcost[i + column_count * j] = c;\n ++\t\t\tCOST(i, j) = c;\n + \t\t}\n + \n + \t\tc = a_util->matching < 0 ?\n + \t\t\ta_util->diffsize * creation_factor / 100 : COST_MAX;\n + \t\tfor (j = b->nr; j < column_count; j++)\n +-\t\t\tcost[i + column_count * j] = c;\n ++\t\t\tCOST(i, j) = c;\n + \t}\n + \n + \tfor (j = 0; j < b->nr; j++) {\n +@@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,\n + \t\tc = util->matching < 0 ?\n + \t\t\tutil->diffsize * creation_factor / 100 : COST_MAX;\n + \t\tfor (i = a->nr; i < column_count; i++)\n +-\t\t\tcost[i + column_count * j] = c;\n ++\t\t\tCOST(i, j) = c;\n + \t}\n + \n + \tif (column_count > 1)\n 8: 794d494bedd < -: ----------- linear-assignment.c: detect signed add/mul on GCC and Clang\n 9: 2026b4bff90 < -: ----------- linear-assignment.c: add and use intprops.h from Gnulib\n-- \n2.34.1.932.g36842105b61\n\n"},{"id":"443796","messageId":"RFC-patch-v2-2.5-2233872545e-20211210T122901Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com","subject":"[RFC PATCH v2 2/5] linear-assignment.c: split up compute_assignment() function","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T12:30:39Z","receivedAt":"2021-12-10T12:30:53Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Split up the the long compute_assignment() function to make it easier\nto reason about, particularly when it comes to what variables are used\nlater, and which aren't.\n\nThe grouping of \"int\" v.s. \"int *\" in function signatures is there to\nmake subsequent diffs smaller, if we're ever going to have a \"nr\"\nmember with a \"size_t\", but allocate e.g. \"int *\", and in anticipation\nof the type names becoming longer than \"int\", which would require\nre-wrapping.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 103 +++++++++++++++++++++++++++++++++-----------\n linear-assignment.h | 3 +-\n 2 files changed, 79 insertions(+), 27 deletions(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex 0c0786a63b6..7f85745e541 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -8,21 +8,12 @@\n \n #define COST(column, row) cost[(column) + column_count * (row)]\n \n-/*\n- * The parameter `cost` is the cost matrix: the cost to assign column j to row\n- * i is `cost[j + column_count * i].\n- */\n-void compute_assignment(int column_count, int row_count, int *cost,\n-\t\t\tint *column2row, int *row2column)\n+static void columns_reduction(int column_count, int row_count,\n+\t\t\t int *cost,\n+\t\t\t int *column2row, int *row2column,\n+\t\t\t int *v)\n {\n-\tint *v, *d;\n-\tint *free_row, free_count = 0, saved_free_count, *pred, *col;\n-\tint i, j, phase;\n-\n-\tassert(column_count > 1);\n-\tmemset(column2row, -1, sizeof(int) * column_count);\n-\tmemset(row2column, -1, sizeof(int) * row_count);\n-\tALLOC_ARRAY(v, column_count);\n+\tint i, j;\n \n \t/* column reduction */\n \tfor (j = column_count - 1; j >= 0; j--) {\n@@ -42,13 +33,21 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \t\t\tcolumn2row[j] = -1;\n \t\t}\n \t}\n+}\n+\n+static void reduction_transfer(int column_count, int row_count,\n+\t\t\t int *cost,\n+\t\t\t int *free_row, int *free_count,\n+\t\t\t int *column2row, int *row2column,\n+\t\t\t int *v)\n+{\n+\tint i, j;\n \n \t/* reduction transfer */\n-\tALLOC_ARRAY(free_row, row_count);\n \tfor (i = 0; i < row_count; i++) {\n \t\tint j1 = row2column[i];\n \t\tif (j1 == -1)\n-\t\t\tfree_row[free_count++] = i;\n+\t\t\tfree_row[(*free_count)++] = i;\n \t\telse if (j1 < -1)\n \t\t\trow2column[i] = -2 - j1;\n \t\telse {\n@@ -59,21 +58,25 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \t\t\tv[j1] -= min;\n \t\t}\n \t}\n+}\n \n-\tif (free_count ==\n-\t (column_count < row_count ? row_count - column_count : 0)) {\n-\t\tfree(v);\n-\t\tfree(free_row);\n-\t\treturn;\n-\t}\n+static void augmenting_row_reduction(int column_count,\n+\t\t\t\t int *cost,\n+\t\t\t\t int *column2row, int *row2column,\n+\t\t\t\t int *free_row, int *free_count, int *saved_free_count,\n+\t\t\t\t int *v)\n+{\n+\tint phase;\n \n \t/* augmenting row reduction */\n \tfor (phase = 0; phase < 2; phase++) {\n+\t\tint i;\n \t\tint k = 0;\n \n-\t\tsaved_free_count = free_count;\n-\t\tfree_count = 0;\n-\t\twhile (k < saved_free_count) {\n+\t\t*saved_free_count = *free_count;\n+\t\t*free_count = 0;\n+\t\twhile (k < *saved_free_count) {\n+\t\t\tint j;\n \t\t\tint u1, u2;\n \t\t\tint j1 = 0, j2, i0;\n \n@@ -112,12 +115,24 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \t\t\t\tif (u1 < u2)\n \t\t\t\t\tfree_row[--k] = i0;\n \t\t\t\telse\n-\t\t\t\t\tfree_row[free_count++] = i0;\n+\t\t\t\t\tfree_row[(*free_count)++] = i0;\n \t\t\t}\n \t\t\trow2column[i] = j1;\n \t\t\tcolumn2row[j1] = i;\n \t\t}\n \t}\n+}\n+\n+static void augmentation(int column_count,\n+\t\t\t int *cost,\n+\t\t\t int *column2row, int *row2column,\n+\t\t\t int *free_row, int free_count,\n+\t\t\t int *v)\n+{\n+\tint i, j;\n+\tint *d;\n+\tint *pred, *col;\n+\tint saved_free_count;\n \n \t/* augmentation */\n \tsaved_free_count = free_count;\n@@ -197,6 +212,42 @@ void compute_assignment(int column_count, int row_count, int *cost,\n \tfree(col);\n \tfree(pred);\n \tfree(d);\n+}\n+\n+/*\n+ * The parameter `cost` is the cost matrix: the cost to assign column j to row\n+ * i is `cost[j + column_count * i].\n+ */\n+void compute_assignment(int column_count, int row_count,\n+\t\t\tint *cost,\n+\t\t\tint *column2row, int *row2column)\n+{\n+\tint *v;\n+\tint *free_row, free_count = 0, saved_free_count;\n+\n+\tassert(column_count > 1);\n+\tmemset(column2row, -1, sizeof(int) * column_count);\n+\tmemset(row2column, -1, sizeof(int) * row_count);\n+\tALLOC_ARRAY(v, column_count);\n+\n+\tcolumns_reduction(column_count, row_count, cost, column2row,\n+\t\t\t row2column, v);\n+\n+\tALLOC_ARRAY(free_row, row_count);\n+\treduction_transfer(column_count, row_count, cost, free_row,\n+\t\t\t &free_count, column2row, row2column, v);\n+\tif (free_count ==\n+\t (column_count < row_count ? row_count - column_count : 0))\n+\t\tgoto cleanup;\n+\n+\taugmenting_row_reduction(column_count, cost, column2row,\n+\t\t\t\t row2column, free_row, &free_count,\n+\t\t\t\t &saved_free_count,v);\n+\n+\taugmentation(column_count, cost, column2row, row2column,\n+\t\t free_row, free_count, v);\n+\n+cleanup:\n \tfree(v);\n \tfree(free_row);\n }\ndiff --git a/linear-assignment.h b/linear-assignment.h\nindex 1dfea766290..ef9946bdbfc 100644\n--- a/linear-assignment.h\n+++ b/linear-assignment.h\n@@ -13,7 +13,8 @@\n * assignments (-1 for unassigned, which can happen only if column_count !=\n * row_count).\n */\n-void compute_assignment(int column_count, int row_count, int *cost,\n+void compute_assignment(int column_count, int row_count,\n+\t\t\tint *cost,\n \t\t\tint *column2row, int *row2column);\n \n /* The maximal cost in the cost matrix (to prevent integer overflows). */\n-- \n2.34.1.932.g36842105b61\n\n"},{"id":"443797","messageId":"RFC-patch-v2-3.5-580b76c0759-20211210T122901Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com","subject":"[RFC PATCH v2 3/5] linear-assignment.c: take \"size_t\", not \"int\" for *_count","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T12:30:40Z","receivedAt":"2021-12-10T12:30:54Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"Future-proof and clarify the compute_assignment() interface by having\nit take a \"size_t\" for the count of its that it's processing. For the\ncontent itself we need to be able to store a \"-1\", but there's no\nreason we can't use a \"size_t\" for the size of the number of \"int\"'s\nwe've got.\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 10 +++++-----\n linear-assignment.h | 2 +-\n 2 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex 7f85745e541..1f8329701a0 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -8,7 +8,7 @@\n \n #define COST(column, row) cost[(column) + column_count * (row)]\n \n-static void columns_reduction(int column_count, int row_count,\n+static void columns_reduction(size_t column_count, size_t row_count,\n \t\t\t int *cost,\n \t\t\t int *column2row, int *row2column,\n \t\t\t int *v)\n@@ -35,7 +35,7 @@ static void columns_reduction(int column_count, int row_count,\n \t}\n }\n \n-static void reduction_transfer(int column_count, int row_count,\n+static void reduction_transfer(size_t column_count, size_t row_count,\n \t\t\t int *cost,\n \t\t\t int *free_row, int *free_count,\n \t\t\t int *column2row, int *row2column,\n@@ -60,7 +60,7 @@ static void reduction_transfer(int column_count, int row_count,\n \t}\n }\n \n-static void augmenting_row_reduction(int column_count,\n+static void augmenting_row_reduction(size_t column_count,\n \t\t\t\t int *cost,\n \t\t\t\t int *column2row, int *row2column,\n \t\t\t\t int *free_row, int *free_count, int *saved_free_count,\n@@ -123,7 +123,7 @@ static void augmenting_row_reduction(int column_count,\n \t}\n }\n \n-static void augmentation(int column_count,\n+static void augmentation(size_t column_count,\n \t\t\t int *cost,\n \t\t\t int *column2row, int *row2column,\n \t\t\t int *free_row, int free_count,\n@@ -218,7 +218,7 @@ static void augmentation(int column_count,\n * The parameter `cost` is the cost matrix: the cost to assign column j to row\n * i is `cost[j + column_count * i].\n */\n-void compute_assignment(int column_count, int row_count,\n+void compute_assignment(size_t column_count, size_t row_count,\n \t\t\tint *cost,\n \t\t\tint *column2row, int *row2column)\n {\ndiff --git a/linear-assignment.h b/linear-assignment.h\nindex ef9946bdbfc..9ff055baac1 100644\n--- a/linear-assignment.h\n+++ b/linear-assignment.h\n@@ -13,7 +13,7 @@\n * assignments (-1 for unassigned, which can happen only if column_count !=\n * row_count).\n */\n-void compute_assignment(int column_count, int row_count,\n+void compute_assignment(size_t column_count, size_t row_count,\n \t\t\tint *cost,\n \t\t\tint *column2row, int *row2column);\n \n-- \n2.34.1.932.g36842105b61\n\n"},{"id":"443798","messageId":"RFC-patch-v2-4.5-f8bbe1954fc-20211210T122901Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com","subject":"[RFC PATCH v2 4/5] range-diff.c: rename \"n\" to \"column_count\" in get_correspondences()","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T12:30:41Z","receivedAt":"2021-12-10T12:30:55Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"In preparation for using the COST macro in linear-assignment.c rename\nthe \"n\" variable, it assumes that the \"n\" in \"a + n * b\" is named\n\"column_count\".\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n range-diff.c | 22 +++++++++++-----------\n 1 file changed, 11 insertions(+), 11 deletions(-)\n\ndiff --git a/range-diff.c b/range-diff.c\nindex b2fcc6f66e0..b2e7db2c954 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -308,13 +308,13 @@ static int diffsize(const char *a, const char *b)\n static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\t\tint creation_factor)\n {\n-\tint n = a->nr + b->nr;\n+\tint column_count = st_add(a->nr, b->nr);\n \tint *cost, c, *a2b, *b2a;\n \tint i, j;\n \n-\tCALLOC_ARRAY(cost, st_mult(n, n));\n-\tCALLOC_ARRAY(a2b, n);\n-\tCALLOC_ARRAY(b2a, n);\n+\tCALLOC_ARRAY(cost, st_mult(column_count, column_count));\n+\tCALLOC_ARRAY(a2b, column_count);\n+\tCALLOC_ARRAY(b2a, column_count);\n \n \tfor (i = 0; i < a->nr; i++) {\n \t\tstruct patch_util *a_util = a->items[i].util;\n@@ -328,13 +328,13 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\t\tc = diffsize(a_util->diff, b_util->diff);\n \t\t\telse\n \t\t\t\tc = COST_MAX;\n-\t\t\tcost[i + n * j] = c;\n+\t\t\tcost[i + column_count * j] = c;\n \t\t}\n \n \t\tc = a_util->matching < 0 ?\n \t\t\ta_util->diffsize * creation_factor / 100 : COST_MAX;\n-\t\tfor (j = b->nr; j < n; j++)\n-\t\t\tcost[i + n * j] = c;\n+\t\tfor (j = b->nr; j < column_count; j++)\n+\t\t\tcost[i + column_count * j] = c;\n \t}\n \n \tfor (j = 0; j < b->nr; j++) {\n@@ -342,12 +342,12 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \n \t\tc = util->matching < 0 ?\n \t\t\tutil->diffsize * creation_factor / 100 : COST_MAX;\n-\t\tfor (i = a->nr; i < n; i++)\n-\t\t\tcost[i + n * j] = c;\n+\t\tfor (i = a->nr; i < column_count; i++)\n+\t\t\tcost[i + column_count * j] = c;\n \t}\n \n-\tif (n > 1)\n-\t\tcompute_assignment(n, n, cost, a2b, b2a);\n+\tif (column_count > 1)\n+\t\tcompute_assignment(column_count, column_count, cost, a2b, b2a);\n \n \tfor (i = 0; i < a->nr; i++)\n \t\tif (a2b[i] >= 0 && a2b[i] < b->nr) {\n-- \n2.34.1.932.g36842105b61\n\n"},{"id":"443799","messageId":"RFC-patch-v2-5.5-9194965635a-20211210T122901Z-avarab@gmail.com","threadId":"57059","inReplyTo":"RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com","subject":"[RFC PATCH v2 5/5] range-diff: fix integer overflow & segfault on cost[i + n * j]","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T12:30:42Z","receivedAt":"2021-12-10T12:30:55Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"in preceding commits the \"column_count\" and the \"int*\"'s we malloc()\nwere changed to track their length with a size_t, so we're able to\ntrack as many \"cost\" items as malloc() will give us.\n\nBut we'd still segfault on relatively large range comparisons,\ne.g. this would segfault:\n\n git -P range-diff --creation-factor=50 origin/master...git-for-windows/main\n\nThe reason for that is that we'd still use integer types to compute an\narray index into the \"cost\" array, which would overflow. The result of\na signed overflow in C is undefined, but on my system it'll result in\na negative number, and a prompt segfault as we'll try to access a\nnegative array index.\n\nLuckily we used the COST() macro in linear-assignment.c already for\nall of these lookups, and in a preceding commit we renamed \"n\" in\n\"range-diff.c\"'s get_correspondences() to \"column_count\" in\npreparation for using it here.\n\nSo let's use it for the three occurrences of \"cost\" indexing in\nrange-diff.c, and have the COST() macro itself do overflow checking\nwith st_mult() and st_add(). Due to the cast to \"size_t\" from \"int\"\nwe'll avoid the segfault, and will end up correctly pointing to the\nrelevant \"int *\".\n\nIt's not important that we use the new cost_offset() inline function\nhere, we could also use the st_*() macros inline. By using it we'll\nget a more meaningful backtrace in a debugger to the relevant\naddition/multiplication line if we end up calling die() here.\n\nIt's still possible for us to overflow even with this change, that's\nbecause the iteration variables (such as \"i\" and \"j\" in this diff\ncontext are all \"int\"), even if we changed those to \"size_t\" or\n\"intmax_t\" (not trivial, as we depend on them being negative in some\nplaces) the underlying \"struct string_list\"'s \"nr\" member is an\n\"unsigned int\", which would eventually overflow.\n\nHowever the danger of that overflow isn't as great, as we were\noverflowing on \"i + column_count * j\" before this change, it'll\nrequire a much bigger range for us to have an integer overflow on the\nnumber of commits we're processing.\n\nWe're unlikely to encounter a 2-4 billion commit history on 32 bit\nplatforms. Even if we did one of the types in the underlying object\nmachinery would probably overflow before we overflowed here. So let's\npunt that for now. If we're ever going to solve that issue [1] to\nchange the \"struct string_list\"'s \"nr\" member to a \"size_t\" might be a\ngood start.\n\n1. https://lore.kernel.org/git/RFC-patch-01.10-7c929096381-20211209T191653Z-avarab@gmail.com/\n\nSigned-off-by: Ævar Arnfjörð Bjarmason \n---\n linear-assignment.c | 2 --\n linear-assignment.h | 17 +++++++++++++++++\n range-diff.c | 6 +++---\n 3 files changed, 20 insertions(+), 5 deletions(-)\n\ndiff --git a/linear-assignment.c b/linear-assignment.c\nindex 1f8329701a0..88d15c2ad32 100644\n--- a/linear-assignment.c\n+++ b/linear-assignment.c\n@@ -6,8 +6,6 @@\n #include \"cache.h\"\n #include \"linear-assignment.h\"\n \n-#define COST(column, row) cost[(column) + column_count * (row)]\n-\n static void columns_reduction(size_t column_count, size_t row_count,\n \t\t\t int *cost,\n \t\t\t int *column2row, int *row2column,\ndiff --git a/linear-assignment.h b/linear-assignment.h\nindex 9ff055baac1..5f8bcedc2c5 100644\n--- a/linear-assignment.h\n+++ b/linear-assignment.h\n@@ -17,6 +17,23 @@ void compute_assignment(size_t column_count, size_t row_count,\n \t\t\tint *cost,\n \t\t\tint *column2row, int *row2column);\n \n+/**\n+ * Get an overflow-proof offset into the \"cost\" array.\n+ */\n+static inline size_t cost_offset(const size_t column,\n+\t\t\t\t const size_t column_count, const size_t row)\n+{\n+\tconst size_t a = st_mult(column_count, row);\n+\tconst size_t b = st_add(column, a);\n+\n+\treturn b;\n+}\n+\n+/**\n+ * Convenience macro for doing the cost[] lookup using cost_offset().\n+ */\n+#define COST(column, row) cost[cost_offset((column), (column_count), (row))]\n+\n /* The maximal cost in the cost matrix (to prevent integer overflows). */\n #define COST_MAX (1<<16)\n \ndiff --git a/range-diff.c b/range-diff.c\nindex b2e7db2c954..b4f015213af 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -328,13 +328,13 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\t\t\tc = diffsize(a_util->diff, b_util->diff);\n \t\t\telse\n \t\t\t\tc = COST_MAX;\n-\t\t\tcost[i + column_count * j] = c;\n+\t\t\tCOST(i, j) = c;\n \t\t}\n \n \t\tc = a_util->matching < 0 ?\n \t\t\ta_util->diffsize * creation_factor / 100 : COST_MAX;\n \t\tfor (j = b->nr; j < column_count; j++)\n-\t\t\tcost[i + column_count * j] = c;\n+\t\t\tCOST(i, j) = c;\n \t}\n \n \tfor (j = 0; j < b->nr; j++) {\n@@ -343,7 +343,7 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\n \t\tc = util->matching < 0 ?\n \t\t\tutil->diffsize * creation_factor / 100 : COST_MAX;\n \t\tfor (i = a->nr; i < column_count; i++)\n-\t\t\tcost[i + column_count * j] = c;\n+\t\t\tCOST(i, j) = c;\n \t}\n \n \tif (column_count > 1)\n-- \n2.34.1.932.g36842105b61\n\n"},{"id":"443800","messageId":"211210.86czm4d3zo.gmgdl@evledraar.gmail.com","threadId":"57059","inReplyTo":"YbM85W3N0ySi5k+H@coredump.intra.peff.net","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T12:31:10Z","receivedAt":"2021-12-10T12:44:00Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Dec 10 2021, Jeff King wrote:\n\n> On Fri, Dec 10, 2021 at 11:22:59AM +0100, Ævar Arnfjörð Bjarmason wrote:\n>\n>> > Dropping the st_mult() does nothing to fix the actual problem (which is\n>> > that this function should use a more appropriate type), but introduces\n>> > new failure modes.\n>> \n>> Yes you're entirely right. I had some stupid blinders on while writing\n>> this. FWIW I think I was experimenting with some local macros and\n>> conflated a testing of the overflow of n*n in gdb with the caste'd\n>> version, which you rightly point out here won't have the overflow issue\n>> at all. Sorry.\n>\n> I'm not sure if this is helpful or not, but this is the minimal fix I\n> came up with that runs the testcase I showed earlier. It's basically\n> just swapping out \"int\" for \"ssize_t\" for any variables we use to index\n> the arrays (though note a few are themselves held in arrays, and we have\n> to cross some function boundaries).\n>\n> I won't be surprised if it doesn't hit all cases, or if it even hits a\n> few it doesn't need to (e.g., should \"phase\" be dragged along with \"i\"\n> and \"j\" in the first hunk?). I mostly did guess-and-check on the\n> test-case, fixing whatever segfaulted and then running again until it\n> worked. I didn't even really read the code very carefully.\n>\n> I think you _did_ do more of that careful reading, and broke down the\n> refactorings into separate patches in your series. Which is good. So I\n> think what we'd want is to pick out those parts of your series that end\n> up switching the variable type. My goal in sharing this here is just to\n> show that the end result of the fix can (and IMHO should) be around this\n> same order of magnitude.\n>\n> [...]\n> void compute_assignment(int column_count, int row_count, int *cost,\n> -\t\t\tint *column2row, int *row2column);\n> +\t\t\tssize_t *column2row, ssize_t *row2column);\n> \n> /* The maximal cost in the cost matrix (to prevent integer overflows). */\n> #define COST_MAX (1<<16)\n> diff --git a/range-diff.c b/range-diff.c\n> index cac89a2f4f..f1e1e27bf9 100644\n> --- a/range-diff.c\n> +++ b/range-diff.c\n> @@ -308,9 +308,10 @@ static int diffsize(const char *a, const char *b)\n> static void get_correspondences(struct string_list *a, struct string_list *b,\n> \t\t\t\tint creation_factor)\n> {\n> -\tint n = a->nr + b->nr;\n> -\tint *cost, c, *a2b, *b2a;\n> -\tint i, j;\n> +\tsize_t n = a->nr + b->nr;\n> +\tint *cost, c;\n> +\tssize_t *a2b, *b2a;\n> +\tsize_t i, j;\n> \n> \tALLOC_ARRAY(cost, st_mult(n, n));\n> \tALLOC_ARRAY(a2b, n);\n\nI think I was just chasing butterflies making this intmax_t at all. I\njust submitted a v2, and explained that case in a bit more detail in\nhttps://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com\n\nI *think* it fixes all the cases we plausible run into, i.e. storing the\n\"cost\" in an \"int\" was enough, we just needed a size_t as an offset. It\npasses the regression test you noted[3].\n\nThe first thing I tried when hacking on this some months ago (I picked\nthese patches up again after running into the segfault again) was this\ns/int/ssize_t/ change.\n\nI don't think using ssize_t like that is portable, and that we'd need\nsomething like intmax_t if we needed this in another context.\n\nFirstly it's not standard C, it's just in POSIX, intmax_t is standard C\nas of C99, which and we have in-tree code that already depends on it\n(and uintmax_t).\n\nBut more importantly it's not \"as big as size_t, just signed\" in\nPOSIX. size_t is \"no greater than the width of type long\"[1] and\nLONG_MAX is at least 2^31-1 [2].\n\nWhereas ssize_t is not a \"signed size_t\", but a type that stores\n-1..SSIZE_MAX, and SSIZE_MAX has a minimum value of 2^15-1. I.e. I think\non that basis some implemenations would make it the same as a \"short\nint\" under the hood.\n\nOn my linux system it's just mapped to the longest available signed\ninteger, but that doesn't seem to be a portable assumption.\n\n1. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_types.h.html\n2. https://pubs.opengroup.org/onlinepubs/009696899/basedefs/limits.h.html\n\n3. B.t.w. a thing I ended up ejecting out of this was that I made a\n \"test_commit_bulkier\" which is N times faster than \"test_commit_bulk\",\n it just makes the same commit N times with the printf-repeating feature\n and feeds it to fast-import, but the test took so long in any case that\n I couldn't find a plausible way to get it in-tree).\n\n"},{"id":"443804","messageId":"nycvar.QRO.7.76.6.2112101526540.90@tvgsbejvaqbjf.bet","threadId":"57059","inReplyTo":"YbM85W3N0ySi5k+H@coredump.intra.peff.net","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-12-10T14:27:24Z","receivedAt":"2021-12-10T14:27:44Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Peff,\n\nOn Fri, 10 Dec 2021, Jeff King wrote:\n\n> On Fri, Dec 10, 2021 at 11:22:59AM +0100, Ævar Arnfjörð Bjarmason wrote:\n>\n> > > Dropping the st_mult() does nothing to fix the actual problem (which is\n> > > that this function should use a more appropriate type), but introduces\n> > > new failure modes.\n> >\n> > Yes you're entirely right. I had some stupid blinders on while writing\n> > this. FWIW I think I was experimenting with some local macros and\n> > conflated a testing of the overflow of n*n in gdb with the caste'd\n> > version, which you rightly point out here won't have the overflow issue\n> > at all. Sorry.\n>\n> I'm not sure if this is helpful or not, but this is the minimal fix I\n> came up with that runs the testcase I showed earlier. It's basically\n> just swapping out \"int\" for \"ssize_t\" for any variables we use to index\n> the arrays (though note a few are themselves held in arrays, and we have\n> to cross some function boundaries).\n>\n> I won't be surprised if it doesn't hit all cases, or if it even hits a\n> few it doesn't need to (e.g., should \"phase\" be dragged along with \"i\"\n> and \"j\" in the first hunk?). I mostly did guess-and-check on the\n> test-case, fixing whatever segfaulted and then running again until it\n> worked. I didn't even really read the code very carefully.\n>\n> I think you _did_ do more of that careful reading, and broke down the\n> refactorings into separate patches in your series. Which is good. So I\n> think what we'd want is to pick out those parts of your series that end\n> up switching the variable type. My goal in sharing this here is just to\n> show that the end result of the fix can (and IMHO should) be around this\n> same order of magnitude.\n\nI am in favor of this patch. Will you have time to submit this with a\ncommit message?\n\nThank you,\nDscho\n\n>\n> ---\n> diff --git a/linear-assignment.c b/linear-assignment.c\n> index ecffc09be6..3efa30c50b 100644\n> --- a/linear-assignment.c\n> +++ b/linear-assignment.c\n> @@ -13,11 +13,11 @@\n> * i is `cost[j + column_count * i].\n> */\n> void compute_assignment(int column_count, int row_count, int *cost,\n> -\t\t\tint *column2row, int *row2column)\n> +\t\t\tssize_t *column2row, ssize_t *row2column)\n> {\n> \tint *v, *d;\n> \tint *free_row, free_count = 0, saved_free_count, *pred, *col;\n> -\tint i, j, phase;\n> +\tssize_t i, j, phase;\n>\n> \tif (column_count < 2) {\n> \t\tmemset(column2row, 0, sizeof(int) * column_count);\n> @@ -31,7 +31,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n>\n> \t/* column reduction */\n> \tfor (j = column_count - 1; j >= 0; j--) {\n> -\t\tint i1 = 0;\n> +\t\tssize_t i1 = 0;\n>\n> \t\tfor (i = 1; i < row_count; i++)\n> \t\t\tif (COST(j, i1) > COST(j, i))\n> @@ -51,7 +51,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n> \t/* reduction transfer */\n> \tALLOC_ARRAY(free_row, row_count);\n> \tfor (i = 0; i < row_count; i++) {\n> -\t\tint j1 = row2column[i];\n> +\t\tssize_t j1 = row2column[i];\n> \t\tif (j1 == -1)\n> \t\t\tfree_row[free_count++] = i;\n> \t\telse if (j1 < -1)\n> @@ -74,13 +74,13 @@ void compute_assignment(int column_count, int row_count, int *cost,\n>\n> \t/* augmenting row reduction */\n> \tfor (phase = 0; phase < 2; phase++) {\n> -\t\tint k = 0;\n> +\t\tssize_t k = 0;\n>\n> \t\tsaved_free_count = free_count;\n> \t\tfree_count = 0;\n> \t\twhile (k < saved_free_count) {\n> \t\t\tint u1, u2;\n> -\t\t\tint j1 = 0, j2, i0;\n> +\t\t\tssize_t j1 = 0, j2, i0;\n>\n> \t\t\ti = free_row[k++];\n> \t\t\tu1 = COST(j1, i) - v[j1];\n> @@ -130,7 +130,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n> \tALLOC_ARRAY(pred, column_count);\n> \tALLOC_ARRAY(col, column_count);\n> \tfor (free_count = 0; free_count < saved_free_count; free_count++) {\n> -\t\tint i1 = free_row[free_count], low = 0, up = 0, last, k;\n> +\t\tssize_t i1 = free_row[free_count], low = 0, up = 0, last, k;\n> \t\tint min, c, u1;\n>\n> \t\tfor (j = 0; j < column_count; j++) {\n> @@ -192,7 +192,7 @@ void compute_assignment(int column_count, int row_count, int *cost,\n> \t\t/* augmentation */\n> \t\tdo {\n> \t\t\tif (j < 0)\n> -\t\t\t\tBUG(\"negative j: %d\", j);\n> +\t\t\t\tBUG(\"negative j: %\"PRIdMAX, (intmax_t)j);\n> \t\t\ti = pred[j];\n> \t\t\tcolumn2row[j] = i;\n> \t\t\tSWAP(j, row2column[i]);\n> diff --git a/linear-assignment.h b/linear-assignment.h\n> index 1dfea76629..7005521d61 100644\n> --- a/linear-assignment.h\n> +++ b/linear-assignment.h\n> @@ -14,7 +14,7 @@\n> * row_count).\n> */\n> void compute_assignment(int column_count, int row_count, int *cost,\n> -\t\t\tint *column2row, int *row2column);\n> +\t\t\tssize_t *column2row, ssize_t *row2column);\n>\n> /* The maximal cost in the cost matrix (to prevent integer overflows). */\n> #define COST_MAX (1<<16)\n> diff --git a/range-diff.c b/range-diff.c\n> index cac89a2f4f..f1e1e27bf9 100644\n> --- a/range-diff.c\n> +++ b/range-diff.c\n> @@ -308,9 +308,10 @@ static int diffsize(const char *a, const char *b)\n> static void get_correspondences(struct string_list *a, struct string_list *b,\n> \t\t\t\tint creation_factor)\n> {\n> -\tint n = a->nr + b->nr;\n> -\tint *cost, c, *a2b, *b2a;\n> -\tint i, j;\n> +\tsize_t n = a->nr + b->nr;\n> +\tint *cost, c;\n> +\tssize_t *a2b, *b2a;\n> +\tsize_t i, j;\n>\n> \tALLOC_ARRAY(cost, st_mult(n, n));\n> \tALLOC_ARRAY(a2b, n);\n>\n"},{"id":"443805","messageId":"nycvar.QRO.7.76.6.2112101528200.90@tvgsbejvaqbjf.bet","threadId":"57059","inReplyTo":"RFC-cover-00.10-00000000000-20211209T191653Z-avarab@gmail.com","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-12-10T14:31:14Z","receivedAt":"2021-12-10T14:31:30Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Ævar,\n\nOn Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n\n> The difference between \"master\" and \"git-for-windows/main\" is large\n> enough that comparing the two will segfault on my system. This is\n> because the range-diff code does some expensive calculations and will\n> overflow the \"int\" type.\n\nYou are holding this thing wrong.\n\nThe `main` branch of Git for Windows uses merging rebases, therefore you\nneed to use a commit range like\n`git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and\ncompare it to `git-for-windows/main..master`.\n\nFailing that, you will receive only bogus results.\n\nAs to the patch series, it likely does the wrong thing. Just like we error\nout on insanely large input in libxdiff, `range-diff` should do the same.\n\nCiao,\nJohannes\n"},{"id":"443806","messageId":"211210.868rwscxcw.gmgdl@evledraar.gmail.com","threadId":"57059","inReplyTo":"nycvar.QRO.7.76.6.2112101526540.90@tvgsbejvaqbjf.bet","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T14:58:43Z","receivedAt":"2021-12-10T15:07:52Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Dec 10 2021, Johannes Schindelin wrote:\n\n> Hi Peff,\n>\n> On Fri, 10 Dec 2021, Jeff King wrote:\n>\n>> On Fri, Dec 10, 2021 at 11:22:59AM +0100, Ævar Arnfjörð Bjarmason wrote:\n>>\n>> > > Dropping the st_mult() does nothing to fix the actual problem (which is\n>> > > that this function should use a more appropriate type), but introduces\n>> > > new failure modes.\n>> >\n>> > Yes you're entirely right. I had some stupid blinders on while writing\n>> > this. FWIW I think I was experimenting with some local macros and\n>> > conflated a testing of the overflow of n*n in gdb with the caste'd\n>> > version, which you rightly point out here won't have the overflow issue\n>> > at all. Sorry.\n>>\n>> I'm not sure if this is helpful or not, but this is the minimal fix I\n>> came up with that runs the testcase I showed earlier. It's basically\n>> just swapping out \"int\" for \"ssize_t\" for any variables we use to index\n>> the arrays (though note a few are themselves held in arrays, and we have\n>> to cross some function boundaries).\n>>\n>> I won't be surprised if it doesn't hit all cases, or if it even hits a\n>> few it doesn't need to (e.g., should \"phase\" be dragged along with \"i\"\n>> and \"j\" in the first hunk?). I mostly did guess-and-check on the\n>> test-case, fixing whatever segfaulted and then running again until it\n>> worked. I didn't even really read the code very carefully.\n>>\n>> I think you _did_ do more of that careful reading, and broke down the\n>> refactorings into separate patches in your series. Which is good. So I\n>> think what we'd want is to pick out those parts of your series that end\n>> up switching the variable type. My goal in sharing this here is just to\n>> show that the end result of the fix can (and IMHO should) be around this\n>> same order of magnitude.\n>\n> I am in favor of this patch. Will you have time to submit this with a\n> commit message?\n\nI'd also be happy to pick it up as a massaging of my s/int/intmax_t/\nchange. I think per[1] that intmax_t is more portable here than ssize_t,\nbut I'm very likely to be missing something. Corrections most welcome.\n\nPer [1] I ejected that out of my v2 because I think the \"cost\" being\nlarger than 1<<16 might not be all that useful. I.e. the limiting that's\nin get_correspondences().\n\nBut I'll happily admit ignorance on how the actual guts of range-diff\nwork, I just wanted to fix a segfault I kept running into locally at\nsome point, and figured I'd submit this RFC.\n\nDoesn't an enlargement of the \"int\" from an assumed 32 bit unsigned to\nsay a 64bit unsigned require that 16bit unsigned COST_MAX to be\ncorrespondingly bumped to 32bit unsigned? I.e. we'd define it as 1/2 of\nwhatever \"intmax_t\" (or \"ssize_t\" or \"long long int\" or whatever) is\ndefined as?\n\nThat may be a question under the umbrella of \"Ævar doesn't actually\nunderstand range-diff\", but think I recall playing with bumping one and\nnot the other (or bumping COST_MAX too close to the size of the\ncontainer type) and running into errors...\n\n1. https://lore.kernel.org/git/211210.86czm4d3zo.gmgdl@evledraar.gmail.com/\n"},{"id":"443807","messageId":"211210.864k7gcx3r.gmgdl@evledraar.gmail.com","threadId":"57059","inReplyTo":"nycvar.QRO.7.76.6.2112101528200.90@tvgsbejvaqbjf.bet","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-10T15:07:15Z","receivedAt":"2021-12-10T15:13:04Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Dec 10 2021, Johannes Schindelin wrote:\n\n> Hi Ævar,\n>\n> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n>\n>> The difference between \"master\" and \"git-for-windows/main\" is large\n>> enough that comparing the two will segfault on my system. This is\n>> because the range-diff code does some expensive calculations and will\n>> overflow the \"int\" type.\n>\n> You are holding this thing wrong.\n>\n> The `main` branch of Git for Windows uses merging rebases, therefore you\n> need to use a commit range like\n> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and\n> compare it to `git-for-windows/main..master`.\n>\n> Failing that, you will receive only bogus results.\n\nIndeed. FWIW I got this segfault on an actual local range-diff that's\nuseful for a very large range & started digging.\n\nI then tried to come up with some arbitrary command someone with a\ngit.git clone might be able to run that would reproduce it without\nhaving to tell them to clone chromium.git or .\n\n> As to the patch series, it likely does the wrong thing. Just like we error\n> out on insanely large input in libxdiff, `range-diff` should do the same.\n\nI haven't come up with an actual use-case for diffing something large\n(maybe someone storing DNA sequences as text would?), but have run into\npractical cases where range-diff would be useful on range where it\ncurrently segfaults. E.g. repos that get 500-1000 commits/day someone\ncherry-picks commits between branches & rewords/adjusts, and you're\ntrying to range-diff it 2 months later looking for differences...\n"},{"id":"443834","messageId":"e881a455-88b5-9c87-03a8-caaee68bb344@gmail.com","threadId":"57059","inReplyTo":"211210.86czm4d3zo.gmgdl@evledraar.gmail.com","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Phillip Wood","fromEmail":"phillip.wood123@gmail.com","sentAt":"2021-12-10T19:24:21Z","receivedAt":"2021-12-10T19:24:26Z","isPatch":true,"sender":{"key":"phillip.wood@dunelm.org.uk","avatar":null},"body":"Hi Ævar\n\nOn 10/12/2021 12:31, Ævar Arnfjörð Bjarmason wrote:\n> \n> [...] \n> I think I was just chasing butterflies making this intmax_t at all. I\n> just submitted a v2, and explained that case in a bit more detail in\n> https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com\n> \n> I *think* it fixes all the cases we plausible run into, i.e. storing the\n> \"cost\" in an \"int\" was enough, we just needed a size_t as an offset. It\n> passes the regression test you noted[3].\n> \n> The first thing I tried when hacking on this some months ago (I picked\n> these patches up again after running into the segfault again) was this\n> s/int/ssize_t/ change.\n> \n> I don't think using ssize_t like that is portable, and that we'd need\n> something like intmax_t if we needed this in another context.\n >\n> Firstly it's not standard C, it's just in POSIX, intmax_t is standard C\n> as of C99, which and we have in-tree code that already depends on it\n> (and uintmax_t).\n\nI'm not objecting to using intmax_t particularly for code that needs to \nstore negative values other than -1 but we're already using ssize_t in a \nlot of places so I don't think we need to worry about it not being \nsupported.\n\n> But more importantly it's not \"as big as size_t, just signed\" in\n> POSIX. size_t is \"no greater than the width of type long\"[1]\n\nThe full text is\n\n The implementation shall support one or more programming\n environments in which the widths of blksize_t, pid_t, size_t,\n ssize_t, and suseconds_t are no greater than the width of type\n long. The names of these programming environments can be obtained\n using the confstr() function or the getconf utility.\n\nso \"no greater than the width of type long\" applies to ssize_t as well \nas size_t.\n\n> and\n> LONG_MAX is at least 2^31-1 [2].\n> \n> Whereas ssize_t is not a \"signed size_t\", but a type that stores\n> -1..SSIZE_MAX, and SSIZE_MAX has a minimum value of 2^15-1. I.e. I think\n> on that basis some implemenations would make it the same as a \"short\n> int\" under the hood.\n\nThe minimum value of SIZE_MAX is 2^16-1[1], I'm not sure you can read \nmuch into the width of ssize_t from the minimum value of SSIZE_MAX. If \nyou think about where ssize_t is used as the return value of read() and \nwrite() that take a size_t as the number of bytes to read/write then it \nwould be very odd if ssize_t was a different width to size_t.\n\nBest Wishes\n\nPhillip\n\n[1] https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/stdint.h.html\n\n> On my linux system it's just mapped to the longest available signed\n> integer, but that doesn't seem to be a portable assumption.\n> \n> 1. https://pubs.opengroup.org/onlinepubs/9699919799/basedefs/sys_types.h.html\n> 2. https://pubs.opengroup.org/onlinepubs/009696899/basedefs/limits.h.html\n> \n> 3. B.t.w. a thing I ended up ejecting out of this was that I made a\n> \"test_commit_bulkier\" which is N times faster than \"test_commit_bulk\",\n> it just makes the same commit N times with the printf-repeating feature\n> and feeds it to fast-import, but the test took so long in any case that\n> I couldn't find a plausible way to get it in-tree).\n> \n\n"},{"id":"443888","messageId":"nycvar.QRO.7.76.6.2112111453040.90@tvgsbejvaqbjf.bet","threadId":"57059","inReplyTo":"211210.868rwscxcw.gmgdl@evledraar.gmail.com","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-12-11T14:01:03Z","receivedAt":"2021-12-11T14:01:39Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Ævar,\n\nOn Fri, 10 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n\n> But I'll happily admit ignorance on how the actual guts of range-diff\n> work, I just wanted to fix a segfault I kept running into locally at\n> some point, and figured I'd submit this RFC.\n\nI understand that it is super tempting to avoid spending the time to\nunderstand how range-diff works and simply make changes until the\nsegmentation fault is gone, and then shoot off several iterations of the\npatch series in the hopes that it gets merged at some point, and that\nmaybe reviewers who do spend the time to become familiar with the logic\nhelp avoid introduce new bugs.\n\nHowever, as a reviewer I am totally unsympathetic of this approach. I do\nnot want to review patches that even go so far as renaming functions when\nthey claim to \"just fix a segfault\" and the author even admits that\nthey're unfamiliar with what the code is supposed to do, without any\nindication that they're inclined to invest the effort to change that.\n\nIf all you want to do is to fix the segmentation fault, and want to skip\nthe due diligence of studying the business logic, then just fix that\nsegmentation fault (I strongly suspect that using `COST()` after modifying\nit to use `st_*()` would accomplish that). No need to inflate that to 5\npatches. Unless you're thinking of the commit-per-author count as some\nsort of scoreboard where you want to win. In which case I am even less\ninterested in reviewing the patches.\n\nCiao,\nJohannes\n"},{"id":"443901","messageId":"211212.861r2hbtb5.gmgdl@evledraar.gmail.com","threadId":"57059","inReplyTo":"nycvar.QRO.7.76.6.2112111453040.90@tvgsbejvaqbjf.bet","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-12T17:44:43Z","receivedAt":"2021-12-12T17:56:57Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Sat, Dec 11 2021, Johannes Schindelin wrote:\n\n> Hi Ævar,\n>\n> On Fri, 10 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n>\n>> But I'll happily admit ignorance on how the actual guts of range-diff\n>> work, I just wanted to fix a segfault I kept running into locally at\n>> some point, and figured I'd submit this RFC.\n>\n> I understand that it is super tempting to avoid spending the time to\n> understand how range-diff works and simply make changes until the\n> segmentation fault is gone, and then shoot off several iterations of the\n> patch series in the hopes that it gets merged at some point, and that\n> maybe reviewers who do spend the time to become familiar with the logic\n> help avoid introduce new bugs.\n>\n> However, as a reviewer I am totally unsympathetic of this approach. I do\n> not want to review patches that even go so far as renaming functions when\n> they claim to \"just fix a segfault\" and the author even admits that\n> they're unfamiliar with what the code is supposed to do, without any\n> indication that they're inclined to invest the effort to change that.\n\nWhat you're eliding here is the context where I say that I must not be\ngetting something because you're apparently endorsing the WIP\ns/int/intmax_t/g patch Jeff King inlined upthread without a\ncorresponding change to COST_MAX.\n\nDon't those two go hand-in-hand, and changing one without the other\nwould lead to a subtle bug?\n\n> If all you want to do is to fix the segmentation fault, and want to skip\n> the due diligence of studying the business logic, then just fix that\n> segmentation fault (I strongly suspect that using `COST()` after modifying\n> it to use `st_*()` would accomplish that).\n\nWell, this is an RFC series for a bug that I encountered & which seems\nto be fixed by these changes, but in an area which I'll happily admit\nthat I'm not confident enough to say that this is *the* right fix, and I\nthink both the \"RFC\" label and both cover letters make that clear.\n\n> No need to inflate that to 5\n> patches. Unless you're thinking of the commit-per-author count as some\n> sort of scoreboard where you want to win. In which case I am even less\n> interested in reviewing the patches.\n\nCan you mention specific things you'd like to have squashed? I do think\nthis split-up makes thinsg easier to review.\n\nE.g. if we're using the COST() macro in range-diff.c then splitting 4/5\nfrom 5/5 means you don't need to spend as much time mentally splitting\nthe meaningful changes from a variable rename (which is required for\nusing that macro).\n\nI agree that 1-3/5 aren't strictly necessary. I did try to do this\nwithout those, but found e.g. reasoning about changing the\none-giant-function in linear-assignment.c harder when it came to the\nsegfault fix, and likewise the mechanical change from \"int\" to \"size_t\"\nis (I think) easier to review & reason about.\n"},{"id":"444104","messageId":"Ybid3ajK5/zimo6/@coredump.intra.peff.net","threadId":"57059","inReplyTo":"RFC-patch-v2-1.5-068c203adc6-20211210T122901Z-avarab@gmail.com","subject":"Re: [RFC PATCH v2 1/5] range-diff: zero out elements in \"cost\" first","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-14T13:36:29Z","receivedAt":"2021-12-14T13:36:33Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 10, 2021 at 01:30:38PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> Have the get_correspondences() function use CALLOC_ARRAY instead of\n> looping over the newly allocated \"cost\" to zero out some of its\n> elements.\n> \n> The for-loop that zero'd out elements in \"cost\" wasn't the first loop\n> in that function, nor did it cover all of its elements, but regardless\n> of that this change doesn't affect its end-state. None of the\n> for-loops touched the same items in the array, so we could have (and\n> an earlier WIP version of this change did) moved the for-loop we're\n> deleting to come first in get_correspondences().\n> \n> This can be seen from a careful reading of this code added in in\n> d9c66f0b5bf (range-diff: first rudimentary implementation,\n> 2018-08-13) (as well as adding some printf-debugging) we'll set all\n> elements in the in the \"n * n\" allocated array. That's \"n = A+B\" where\n> \"A\" and \"B\" are the number of commits in our respective ranges.\n\nIt took me several readings to understand this argument. I think it's\njust:\n\n When setting up the 2-dimensional \"cost\" array, we first fill in all\n rows 0..a->nr, and then all columns 0..b->nr. After that, we zero the\n rest of the array: slots which are both in rows greater than a->nr\n _and_ columns greater than b->nr.\n\n We can instead just zero everything from the start with\n CALLOC_ARRAY() and skip the final zero-ing.\n\nI'm not necessarily asking for a re-roll with the message, but just\nre-stating it to make sure I understand what's going on.\n\n> So let's just allocate this with CALLOC_ARRAY(), and skip these two\n> for-loops.\n\nThe first part tells us it's not wrong to do this change. But it doesn't\ngive us a \"why\". Is it just simpler code? We think it might be faster to\ncalloc than hand-rolling?\n\nThe \"two for-loops\" confused me for a minute. Really there are two\nseparate cases:\n\n - we can calloc the \"cost\" array and drop the final zero-ing loop in\n get_correspondences(), per the argument above\n\n - we can calloc the a2b and b2a arrays, which saves\n compute_assignment() from doing it itself later. Though this is a\n little weird, since it may zero them or it may set all entries to\n -1.\n\nGiven the large explanation needed for the first one (above), and then\nthis totally distinct explanation for the second one:\n\n> Furthermore let's remove the early exit condition from\n> compute_assignment() in favor of an assert that it must be called with\n> \"column_count > 1\", then \"get_correspondences()\" can skip calling it\n> when no further filling of the \"a2b\" and \"b2a\" arrays is needed.\n\n...it kind of feels like they ought to be separate patches. At the very\nleast, it would be nice if the two cases were laid out more clearly at\nthe start of the commit message.\n\nI do find the movement of this column_count check strange. It feels like\nit's breaking the encapsulation of compute_assignment(); now its caller\nknows more about when it might zero things and when it might do an\nactual computation. And it makes things more complicated (we have a\nconditional in the sole caller _and_ we have an assert to make sure the\ncaller checked that conditional).\n\nBut maybe this is really important for some later refactor. I'll keep\nreading...\n\n-Peff\n"},{"id":"444105","messageId":"YbiemFN4F0ebr796@coredump.intra.peff.net","threadId":"57059","inReplyTo":"RFC-patch-v2-2.5-2233872545e-20211210T122901Z-avarab@gmail.com","subject":"Re: [RFC PATCH v2 2/5] linear-assignment.c: split up compute_assignment() function","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-14T13:39:36Z","receivedAt":"2021-12-14T13:39:39Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 10, 2021 at 01:30:39PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> Split up the the long compute_assignment() function to make it easier\n> to reason about, particularly when it comes to what variables are used\n> later, and which aren't.\n\nOK, this refactor seems reasonable. I don't know enough about the\nlinear-assignment algorithm to know whether the names you've picked are\nmeaningful.\n\n> +void compute_assignment(int column_count, int row_count,\n> +\t\t\tint *cost,\n> +\t\t\tint *column2row, int *row2column)\n> +{\n> +\tint *v;\n> +\tint *free_row, free_count = 0, saved_free_count;\n> +\n> +\tassert(column_count > 1);\n> +\tmemset(column2row, -1, sizeof(int) * column_count);\n> +\tmemset(row2column, -1, sizeof(int) * row_count);\n> +\tALLOC_ARRAY(v, column_count);\n\nSo this is the code where we would have kept the column_count check and\nzero'd column2row and row2column, had we not moved it in the previous\ncommit. I actually think it would fit fine here in the refactored\ncompute_assignment() if you had left it.\n\n-Peff\n"},{"id":"444106","messageId":"Ybie4nePnPtFLRHa@coredump.intra.peff.net","threadId":"57059","inReplyTo":"RFC-patch-v2-3.5-580b76c0759-20211210T122901Z-avarab@gmail.com","subject":"Re: [RFC PATCH v2 3/5] linear-assignment.c: take \"size_t\", not \"int\" for *_count","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-14T13:40:50Z","receivedAt":"2021-12-14T13:40:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 10, 2021 at 01:30:40PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> Future-proof and clarify the compute_assignment() interface by having\n> it take a \"size_t\" for the count of its that it's processing. For the\n> content itself we need to be able to store a \"-1\", but there's no\n> reason we can't use a \"size_t\" for the size of the number of \"int\"'s\n> we've got.\n\nMakes sense. I'm happy to see the counts dealt with independently here,\nand the reasoning that we can use a straight size_t. The earlier\nrefactoring is paying off a bit, though I think it would be possible\nwithout it.\n\n-Peff\n"},{"id":"444107","messageId":"YbifXSlwXfMX+Wgl@coredump.intra.peff.net","threadId":"57059","inReplyTo":"RFC-patch-v2-4.5-f8bbe1954fc-20211210T122901Z-avarab@gmail.com","subject":"Re: [RFC PATCH v2 4/5] range-diff.c: rename \"n\" to \"column_count\" in get_correspondences()","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-14T13:42:53Z","receivedAt":"2021-12-14T13:42:55Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 10, 2021 at 01:30:41PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> In preparation for using the COST macro in linear-assignment.c rename\n> the \"n\" variable, it assumes that the \"n\" in \"a + n * b\" is named\n> \"column_count\".\n\nOK, makes sense.\n\nOne funny thing:\n\n> diff --git a/range-diff.c b/range-diff.c\n> index b2fcc6f66e0..b2e7db2c954 100644\n> --- a/range-diff.c\n> +++ b/range-diff.c\n> @@ -308,13 +308,13 @@ static int diffsize(const char *a, const char *b)\n> static void get_correspondences(struct string_list *a, struct string_list *b,\n> \t\t\t\tint creation_factor)\n> {\n> -\tint n = a->nr + b->nr;\n> +\tint column_count = st_add(a->nr, b->nr);\n\nAssigning the result of st_add() to an int nullifies the point of using\nit in the first place. :)\n\nI suspect this was a mistake from rebasing, and you meant only to change\nthe name here, and leave the st_add() for the next commit when the type\nchanges.\n\n> [...]\n\nThe rest looks good.\n\n-Peff\n"},{"id":"444108","messageId":"YbikbfdEH2EKZE1p@coredump.intra.peff.net","threadId":"57059","inReplyTo":"RFC-patch-v2-5.5-9194965635a-20211210T122901Z-avarab@gmail.com","subject":"Re: [RFC PATCH v2 5/5] range-diff: fix integer overflow & segfault on cost[i + n * j]","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-14T14:04:29Z","receivedAt":"2021-12-14T14:04:35Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 10, 2021 at 01:30:42PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> in preceding commits the \"column_count\" and the \"int*\"'s we malloc()\n> were changed to track their length with a size_t, so we're able to\n> track as many \"cost\" items as malloc() will give us.\n> \n> But we'd still segfault on relatively large range comparisons,\n> e.g. this would segfault:\n> \n> git -P range-diff --creation-factor=50 origin/master...git-for-windows/main\n> \n> The reason for that is that we'd still use integer types to compute an\n> array index into the \"cost\" array, which would overflow. The result of\n> a signed overflow in C is undefined, but on my system it'll result in\n> a negative number, and a prompt segfault as we'll try to access a\n> negative array index.\n\nNote that this isn't just access. We'll first write to cost[i + n * j]\nto start. In practice because of the iteration, and signed overflow\nbeing implemented as it usually is, we'd always first write a single int\nthat's 2GB before the array. And that should segfault.\n\nI do wonder if this can be turned into a heap overflow exploit. I think\nyou'd probably need to manage to get 2GB on the heap to avoid an\nimmediate segfault.\n\n> Luckily we used the COST() macro in linear-assignment.c already for\n> all of these lookups, and in a preceding commit we renamed \"n\" in\n> \"range-diff.c\"'s get_correspondences() to \"column_count\" in\n> preparation for using it here.\n> \n> So let's use it for the three occurrences of \"cost\" indexing in\n> range-diff.c, and have the COST() macro itself do overflow checking\n> with st_mult() and st_add(). Due to the cast to \"size_t\" from \"int\"\n> we'll avoid the segfault, and will end up correctly pointing to the\n> relevant \"int *\".\n\nIs it actually necessary to do bounds checking here? If we know the\narrays are sized correctly, and we use an appropriate integer type,\nwouldn't we know that our computations are always in bounds?\n\n(I saw your other discussion of the unreliability of ssize_t; if we\ndon't want to assume it's of the same magnitude as size_t, then intmax_t\nwould work).\n\nThe reason I ask in particular is that I wonder if these non-intrinsic\nst_* helpers might introduce a measurable slowdown. When I suggested\nthem earlier it was because I was also suggesting that we'd have done\nall of our bounds-checks up front, during the allocation.\n\n> It's still possible for us to overflow even with this change, that's\n> because the iteration variables (such as \"i\" and \"j\" in this diff\n> context are all \"int\"), even if we changed those to \"size_t\" or\n> \"intmax_t\" (not trivial, as we depend on them being negative in some\n> places) the underlying \"struct string_list\"'s \"nr\" member is an\n> \"unsigned int\", which would eventually overflow.\n\nThe string_list overflow is something I do think we ought to fix. But we\nknow from past experiments that it can't actually cause a heap overflow.\nCan overflowing one of the ints, though?\n\nIf we're computing i*n+j, and j goes negative, then cast to a size_t\nthat will turn into a big number. But depending how negative it is, it\nmight not overflow a size_t. But it would still be well outside the\nbounds of the allocated array. E.g., consider code like this:\n\n int j = INT_MAX;\n while (1) {\n printf(\"int = %d\\n\", j);\n printf(\"size_t = %\"PRIuMAX\"\\n\", (uintmax_t)st_add(0, j));\n j++;\n }\n\nwhich shows what happens when i=0, but j approaches overflow. We wrap to\n-2^31, which is a large but representable size_t. So st_add() does not\ntrigger, but I think we'd still be out of bounds.\n\nI suspect it's OK in practice from a security perspective, because it's\nso far out of bounds as to cause a segfault and not any kind of heap\noverflow. But it really feels like the fix is incomplete. Whereas using\nthe correct types avoids the segfault.\n\n> We're unlikely to encounter a 2-4 billion commit history on 32 bit\n> platforms. Even if we did one of the types in the underlying object\n> machinery would probably overflow before we overflowed here. So let's\n> punt that for now. If we're ever going to solve that issue [1] to\n> change the \"struct string_list\"'s \"nr\" member to a \"size_t\" might be a\n> good start.\n\nI'm less concerned about \"unlikely\" and more about \"what can bad actors\ntrigger\". 2 billion is probably out of reach in practice though\n(typically I've seen things get untenable around a few hundred million\nobjects total).\n\nStill, it feels a bit hand-wavy.\n\n-Peff\n"},{"id":"444110","messageId":"YbirjNDX2bQPqRPD@coredump.intra.peff.net","threadId":"57059","inReplyTo":"211210.86czm4d3zo.gmgdl@evledraar.gmail.com","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-14T14:34:52Z","receivedAt":"2021-12-14T14:34:54Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 10, 2021 at 01:31:10PM +0100, Ævar Arnfjörð Bjarmason wrote:\n\n> I don't think using ssize_t like that is portable, and that we'd need\n> something like intmax_t if we needed this in another context.\n> \n> Firstly it's not standard C, it's just in POSIX, intmax_t is standard C\n> as of C99, which and we have in-tree code that already depends on it\n> (and uintmax_t).\n> \n> But more importantly it's not \"as big as size_t, just signed\" in\n> POSIX. size_t is \"no greater than the width of type long\"[1] and\n> LONG_MAX is at least 2^31-1 [2].\n\nThanks, I didn't know that about ssize_t. I do wonder how often it is\n_not_ the case that it is of the same magnitude as size_t. Certainly I\ncan see how write() could decide to just work in SSIZE_MAX chunks, since\nthe caller has to be prepared to loop anyway. But it seems like the\nobvious implementation is for it to be a signed size_t; I'd be curious\nto hear of any platforms that diverge from this (i.e., is this a real\nportability concern, or like NULL pointers that aren't all-zeroes, one\nthat we don't care about in practice).\n\nI do suspect we've already made that assumption elsewhere, though it's\nhard to easily see. Grepping for ssize_t turns up lots of reasonable and\nlegitimate uses. Though some like the one in strbuf_realpath() are\nquestionable (it's assigning from an int!).\n\n> 3. B.t.w. a thing I ended up ejecting out of this was that I made a\n> \"test_commit_bulkier\" which is N times faster than \"test_commit_bulk\",\n> it just makes the same commit N times with the printf-repeating feature\n> and feeds it to fast-import, but the test took so long in any case that\n> I couldn't find a plausible way to get it in-tree).\n\nYes, I noticed it was rather slow. The main culprit is Git writing out\nnew blobs and trees for each commit, which is what I assume your\n\"bulkier\" version skipped (the existing \"bulk\" one is careful not to\nuse any sub-processes). You can instruct test_commit_bulk to use\nidentical content in each commit, which saves a lot of time.\n\nIt's also highly non-linear in the number of commits when the tree\nchanges. That suggests that fast-import's tree-handling could be\nimproved. Here are the results of the hacky perf script below, showing\nboth the non-linearity in the \"full\" case and how much faster the\n\"quick\" (commits-only) case is:\n\n Test this tree \n --------------------------------------\n 1234.2: full 1000 0.35(0.27+0.08) \n 1234.3: full 2000 0.85(0.81+0.04) \n 1234.4: full 4000 3.21(3.09+0.11) \n 1234.5: full 8000 12.13(11.85+0.27)\n 1234.6: quick 1000 0.14(0.12+0.02) \n 1234.7: quick 2000 0.20(0.18+0.03) \n 1234.8: quick 4000 0.31(0.28+0.04) \n 1234.9: quick 8000 0.58(0.55+0.03) \n\n-- >8 --\n#!/bin/sh\n\ntest_description='foo'\n. ./perf-lib.sh\n\ntest_expect_success 'empty repo' 'git init'\n\ntest_perf 'full 1000' 'test_commit_bulk --id=full 1000'\ntest_perf 'full 2000' 'test_commit_bulk --id=full 2000'\ntest_perf 'full 4000' 'test_commit_bulk --id=full 4000'\ntest_perf 'full 8000' 'test_commit_bulk --id=full 8000'\n\ntest_perf 'quick 1000' 'test_commit_bulk --id=quick --filename=foo --contents=bar 1000'\ntest_perf 'quick 2000' 'test_commit_bulk --id=quick --filename=foo --contents=bar 2000'\ntest_perf 'quick 4000' 'test_commit_bulk --id=quick --filename=foo --contents=bar 4000'\ntest_perf 'quick 8000' 'test_commit_bulk --id=quick --filename=foo --contents=bar 8000'\n\ntest_done\n-- >8 --\n"},{"id":"444111","messageId":"YbitRxAmkM/O7xDg@coredump.intra.peff.net","threadId":"57059","inReplyTo":"nycvar.QRO.7.76.6.2112101526540.90@tvgsbejvaqbjf.bet","subject":"Re: [RFC PATCH 02/10] range-diff.c: don't use st_mult() for signed \"int\"","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-14T14:42:15Z","receivedAt":"2021-12-14T14:42:18Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Fri, Dec 10, 2021 at 03:27:24PM +0100, Johannes Schindelin wrote:\n\n> > I'm not sure if this is helpful or not, but this is the minimal fix I\n> > came up with that runs the testcase I showed earlier. It's basically\n> > just swapping out \"int\" for \"ssize_t\" for any variables we use to index\n> > the arrays (though note a few are themselves held in arrays, and we have\n> > to cross some function boundaries).\n> >\n> > I won't be surprised if it doesn't hit all cases, or if it even hits a\n> > few it doesn't need to (e.g., should \"phase\" be dragged along with \"i\"\n> > and \"j\" in the first hunk?). I mostly did guess-and-check on the\n> > test-case, fixing whatever segfaulted and then running again until it\n> > worked. I didn't even really read the code very carefully.\n> >\n> > I think you _did_ do more of that careful reading, and broke down the\n> > refactorings into separate patches in your series. Which is good. So I\n> > think what we'd want is to pick out those parts of your series that end\n> > up switching the variable type. My goal in sharing this here is just to\n> > show that the end result of the fix can (and IMHO should) be around this\n> > same order of magnitude.\n> \n> I am in favor of this patch. Will you have time to submit this with a\n> commit message?\n\nI'm not at all sure that it's sufficient. It avoids overflowing the\ncost array accesses, and was tested on a square input of 2^15. But:\n\n - some of the other ints may need changing, too (e.g., column_count).\n Probably 2^31 commits is out of reach in practice (and probably\n other parts of Git run into problems there anyway). But some of\n those arguments may just be (a->nr * b->nr), whereas I was testing\n overflow at (a->nr + b->nr)^2.\n\n - I threw around ssize_t willy-nilly. Some of those could be size_t,\n and I think Ævar's patches go in the direction of splitting the two,\n which is good.\n\n - some light refactoring may be helpful to split those cases ahead of\n time.\n\nSo I was hoping Ævar would take this approach and run with it. I just\nreviewed his follow-up series, though, and it looks like it is still\nputting bounds-checks into the COST macro, which I think is not\nsufficient.\n\n-Peff\n"},{"id":"444673","messageId":"59ec39af-fdb1-a86a-d2be-37e5954e245f@iee.email","threadId":"57059","inReplyTo":"nycvar.QRO.7.76.6.2112101528200.90@tvgsbejvaqbjf.bet","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2021-12-21T23:22:00Z","receivedAt":"2021-12-21T23:22:04Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"Sorry for the late comment..\n\nOn 10/12/2021 14:31, Johannes Schindelin wrote:\n> Hi Ævar,\n>\n> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n>\n>> The difference between \"master\" and \"git-for-windows/main\" is large\n>> enough that comparing the two will segfault on my system. This is\n>> because the range-diff code does some expensive calculations and will\n>> overflow the \"int\" type.\n> You are holding this thing wrong.\n>\n> The `main` branch of Git for Windows uses merging rebases, therefore you\n> need to use a commit range like\n> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and\n> compare it to `git-for-windows/main..master`.\n\nI'm not sure that a Git repo has an established way of indicating to how\nit's branching/merging/releasing workflow is set up, especially for\nprojects with non-normative use cases, such as Git for Windows. We don't\nhave a git document for covering  the different workflows in common use\nfor easy reference and consistent terminology.\n\nThe merging rebase flow, with 'fake' merge does solve a problem that\ngit.git doesn't have but could easily be a common process for 'friendly\nforks' that follow an upstream with local patches. The choice of\n'{/^Start.the.merging}' is currently specific to the Git-for-Windows\ncase making it harder to discover this useful maintainer method.\n\nI fully agree that the range-diff should probably have a patch limit at\nsome sensible value.\n\nThe 'confusion' between the types size_t, long and int, does ripple\nthrough a lot of portable code, as shown in the series. Not an easy problem.\n\n>\n> Failing that, you will receive only bogus results.\n>\n> As to the patch series, it likely does the wrong thing. Just like we error\n> out on insanely large input in libxdiff, `range-diff` should do the same.\n>\n> Ciao,\n> Johannes\n--\nPhilip\n"},{"id":"444677","messageId":"211222.86r1a5plsm.gmgdl@evledraar.gmail.com","threadId":"57059","inReplyTo":"59ec39af-fdb1-a86a-d2be-37e5954e245f@iee.email","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-21T23:36:51Z","receivedAt":"2021-12-21T23:42:37Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Tue, Dec 21 2021, Philip Oakley wrote:\n\n> Sorry for the late comment..\n>\n> On 10/12/2021 14:31, Johannes Schindelin wrote:\n>> Hi Ævar,\n>>\n>> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n>>\n>>> The difference between \"master\" and \"git-for-windows/main\" is large\n>>> enough that comparing the two will segfault on my system. This is\n>>> because the range-diff code does some expensive calculations and will\n>>> overflow the \"int\" type.\n>> You are holding this thing wrong.\n>>\n>> The `main` branch of Git for Windows uses merging rebases, therefore you\n>> need to use a commit range like\n>> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and\n>> compare it to `git-for-windows/main..master`.\n>\n> I'm not sure that a Git repo has an established way of indicating to how\n> it's branching/merging/releasing workflow is set up, especially for\n> projects with non-normative use cases, such as Git for Windows. We don't\n> have a git document for covering  the different workflows in common use\n> for easy reference and consistent terminology.\n>\n> The merging rebase flow, with 'fake' merge does solve a problem that\n> git.git doesn't have but could easily be a common process for 'friendly\n> forks' that follow an upstream with local patches. The choice of\n> '{/^Start.the.merging}' is currently specific to the Git-for-Windows\n> case making it harder to discover this useful maintainer method.\n\nYes, but let's not get lost in the weeds here. As I noted I just picked\nGFW as a handy example of a large history & that command as a handy\nexample of something that segfaults on \"master\".\n\nSo the point really isn't to say that we should fix range-diff becase\nit'll allow us to run this practically useful command on a git.git fork.\n\n> I fully agree that the range-diff should probably have a patch limit at\n> some sensible value.\n\nWhy would it? If I'm willing to spend the CPU to produce a range-diff of\nan absurdly large range and I've got the memory why shouldn't we support\nit?\n\nWe don't in cases like xdiff where it's not trivial to just raise the\nlimits, but here it seems relatively easy.\n\nI think limits to save users from spending CPU time they didn't expect\nare reasonable, but then we can handle them like the diff/merge rename\ndetection limits, i.e. print a warning/advice, and allow the user to\nopt-out.\n\nThat also doesn't really apply here since \"diff/merge\" will/might still\ndo something useful in those scenarios, whereas range-diff would just\nhave truncated output.\n\n> The 'confusion' between the types size_t, long and int, does ripple\n> through a lot of portable code, as shown in the series. Not an easy problem.\n\nYes, although here we're not just casting and overflowing types, but\noverflowing on multiplication and addition, whereas usually we'd just\noverflow on \"nr\" being too big for \"int\" or similar.\n"},{"id":"444824","messageId":"nycvar.QRO.7.76.6.2112222143080.347@tvgsbejvaqbjf.bet","threadId":"57059","inReplyTo":"211222.86r1a5plsm.gmgdl@evledraar.gmail.com","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2021-12-22T20:50:50Z","receivedAt":"2021-12-22T20:51:12Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi Ævar,\n\nOn Wed, 22 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n\n> On Tue, Dec 21 2021, Philip Oakley wrote:\n>\n> > I fully agree that the range-diff should probably have a patch limit at\n> > some sensible value.\n>\n> Why would it? If I'm willing to spend the CPU to produce a range-diff of\n> an absurdly large range and I've got the memory why shouldn't we support\n> it?\n>\n> We don't in cases like xdiff where it's not trivial to just raise the\n> limits, but here it seems relatively easy.\n\nTo raise the limits you would have to understand the purpose of the\ncalculations so that you can understand the range their data type needs to\nhandle. The weights of the Hungarian Algorithm are distinctly _not_\npointers, therefore using `size_t` is most likely the wrong thing to do.\n\nOf course you can glance over the details and try to avoid digging into\nthe algorithm to understand what it does before changing the data types\nand introducing `st_mult()`-like functions and macros, but that only makes\nit \"relatively easy\", at the price of \"maybe incorrect\". That would be in\nline with what I unfortunately have had to come to expect of your patches.\n\nThe _actual_ \"relatively easy\" way is to imitate the limits we use in\nxdiff (for similar reasons). As I said before.\n\nCiao,\nJohannes\n"},{"id":"444825","messageId":"YcOUl4lIMRy7rzK8@coredump.intra.peff.net","threadId":"57059","inReplyTo":"nycvar.QRO.7.76.6.2112222143080.347@tvgsbejvaqbjf.bet","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2021-12-22T21:11:51Z","receivedAt":"2021-12-22T21:12:01Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Dec 22, 2021 at 09:50:50PM +0100, Johannes Schindelin wrote:\n\n> To raise the limits you would have to understand the purpose of the\n> calculations so that you can understand the range their data type needs to\n> handle. The weights of the Hungarian Algorithm are distinctly _not_\n> pointers, therefore using `size_t` is most likely the wrong thing to do.\n> \n> Of course you can glance over the details and try to avoid digging into\n> the algorithm to understand what it does before changing the data types\n> and introducing `st_mult()`-like functions and macros, but that only makes\n> it \"relatively easy\", at the price of \"maybe incorrect\". That would be in\n> line with what I unfortunately have had to come to expect of your patches.\n\n:( Whether you're frustrated with this topic or not, can we please stick\nto technical critiques? Either proposed changes are the right thing or\nnot, and we can talk about that.\n\nI know it can get hard if the review is \"gee, it looks like this is\ngoing in the wrong direction, but I don't have time to dig in and tell\nyou _exactly_ how it is wrong right now\". And I think that is an OK\nthing to express, but your response here has a bit more bite to it than\nI think is strictly necessary.\n\n> The _actual_ \"relatively easy\" way is to imitate the limits we use in\n> xdiff (for similar reasons). As I said before.\n\nI had a similar thought at first, too. But because one of the array\nsizes we compute is (nr_a + nr_b)^2, I fear the limits end up pretty low\n(e.g., my 32767 by 32767 example). That's a pretty big range diff, but\nit doesn't seem like an outrageous input to throw at the system\n(especially if most of the entries end up finding a match and showing\none line of equality).\n\nIt may be that there are multiple limits to consider, though. E.g., the\nsquare of the sum of the sides, as above, is one. But there may be some\nbenefit to making that work (by using size_t and st_add) but putting a\nhard limit like 2^30 on the number of commits on one side (e.g., for\nranking scores). And that's where understanding exactly what the\nalgorithm is doing becomes necessary.\n\n-Peff\n"},{"id":"444901","messageId":"c2bf8e3b-d758-6c60-506b-293d5be49eb6@iee.email","threadId":"57059","inReplyTo":"211222.86r1a5plsm.gmgdl@evledraar.gmail.com","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2021-12-24T11:15:52Z","receivedAt":"2021-12-24T11:15:55Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"\nOn 21/12/2021 23:36, Ævar Arnfjörð Bjarmason wrote:\n> On Tue, Dec 21 2021, Philip Oakley wrote:\n>\n>> Sorry for the late comment..\n>>\n>> On 10/12/2021 14:31, Johannes Schindelin wrote:\n>>> Hi Ævar,\n>>>\n>>> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n>>>\n>>>> The difference between \"master\" and \"git-for-windows/main\" is large\n>>>> enough that comparing the two will segfault on my system. This is\n>>>> because the range-diff code does some expensive calculations and will\n>>>> overflow the \"int\" type.\n>>> You are holding this thing wrong.\n>>>\n>>> The `main` branch of Git for Windows uses merging rebases, therefore you\n>>> need to use a commit range like\n>>> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and\n>>> compare it to `git-for-windows/main..master`.\n>> I'm not sure that a Git repo has an established way of indicating to how\n>> it's branching/merging/releasing workflow is set up, especially for\n>> projects with non-normative use cases, such as Git for Windows. We don't\n>> have a git document for covering  the different workflows in common use\n>> for easy reference and consistent terminology.\n>>\n>> The merging rebase flow, with 'fake' merge does solve a problem that\n>> git.git doesn't have but could easily be a common process for 'friendly\n>> forks' that follow an upstream with local patches. The choice of\n>> '{/^Start.the.merging}' is currently specific to the Git-for-Windows\n>> case making it harder to discover this useful maintainer method.\n> Yes, but let's not get lost in the weeds here. As I noted I just picked\n> GFW as a handy example of a large history & that command as a handy\n> example of something that segfaults on \"master\".\n\nHad you already experienced the segfault locally, without using the GFW\nexample? How many commits were present in that case?\n\nThe GFW example seems like it's taken the discussion in the wrong direction.\n\nFor me:\n$ git log git/master..origin/main --pretty=oneline | wc -l\n62105\n\nThat's a lot of commits to have in a range diff. It's almost as big as\nthe whole of git/master\n\n$ git log git/master --pretty=oneline | wc -l\n65400\n\nPersonally I'd like a way of trimming 'deadheads' that's a bit easier\nthat needing to remember Dscho's magic string [1], but time will tell.\n> So the point really isn't to say that we should fix range-diff becase\n> it'll allow us to run this practically useful command on a git.git fork.\n>\n>> I fully agree that the range-diff should probably have a patch limit at\n>> some sensible value.\n> Why would it? If I'm willing to spend the CPU to produce a range-diff of\n> an absurdly large range and I've got the memory why shouldn't we support\n> it?\n\nThere will always be a limit somewhere, and if it's not commit count or\nother easily explained & checked limit it will be hard to rationalise\nabout why Git suddenly fails with an error (or segfault) in those\nhumungous case.\n>\n> We don't in cases like xdiff where it's not trivial to just raise the\n> limits, but here it seems relatively easy.\n>\n> I think limits to save users from spending CPU time they didn't expect\n> are reasonable, but then we can handle them like the diff/merge rename\n> detection limits, i.e. print a warning/advice, and allow the user to\n> opt-out.\n>\n> That also doesn't really apply here since \"diff/merge\" will/might still\n> do something useful in those scenarios, whereas range-diff would just\n> have truncated output.\n>\n>> The 'confusion' between the types size_t, long and int, does ripple\n>> through a lot of portable code, as shown in the series. Not an easy problem.\n> Yes, although here we're not just casting and overflowing types, but\n> overflowing on multiplication and addition, whereas usually we'd just\n> overflow on \"nr\" being too big for \"int\" or similar.\nI've been very slowly looking at the `long` limits on GFW which have\nvery similar arithmetic issues for pointers, often with no clear answers.\n\n--\n\nWishing you all the best for Christmas.\nPhilip\n\n[1]\nhttps://lore.kernel.org/git/01fe28d8-2887-bc42-c91b-c3237b5186a7@iee.email/\n"},{"id":"444905","messageId":"211224.86zgoqgd7q.gmgdl@evledraar.gmail.com","threadId":"57059","inReplyTo":"c2bf8e3b-d758-6c60-506b-293d5be49eb6@iee.email","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Ævar Arnfjörð Bjarmason","fromEmail":"avarab@gmail.com","sentAt":"2021-12-24T16:46:26Z","receivedAt":"2021-12-24T16:49:34Z","isPatch":true,"sender":{"key":"avarab@gmail.com","avatar":"https://avatars.githubusercontent.com/u/45301?v=4"},"body":"\nOn Fri, Dec 24 2021, Philip Oakley wrote:\n\n> On 21/12/2021 23:36, Ævar Arnfjörð Bjarmason wrote:\n>> On Tue, Dec 21 2021, Philip Oakley wrote:\n>>\n>>> Sorry for the late comment..\n>>>\n>>> On 10/12/2021 14:31, Johannes Schindelin wrote:\n>>>> Hi Ævar,\n>>>>\n>>>> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n>>>>\n>>>>> The difference between \"master\" and \"git-for-windows/main\" is large\n>>>>> enough that comparing the two will segfault on my system. This is\n>>>>> because the range-diff code does some expensive calculations and will\n>>>>> overflow the \"int\" type.\n>>>> You are holding this thing wrong.\n>>>>\n>>>> The `main` branch of Git for Windows uses merging rebases, therefore you\n>>>> need to use a commit range like\n>>>> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and\n>>>> compare it to `git-for-windows/main..master`.\n>>> I'm not sure that a Git repo has an established way of indicating to how\n>>> it's branching/merging/releasing workflow is set up, especially for\n>>> projects with non-normative use cases, such as Git for Windows. We don't\n>>> have a git document for covering  the different workflows in common use\n>>> for easy reference and consistent terminology.\n>>>\n>>> The merging rebase flow, with 'fake' merge does solve a problem that\n>>> git.git doesn't have but could easily be a common process for 'friendly\n>>> forks' that follow an upstream with local patches. The choice of\n>>> '{/^Start.the.merging}' is currently specific to the Git-for-Windows\n>>> case making it harder to discover this useful maintainer method.\n>> Yes, but let's not get lost in the weeds here. As I noted I just picked\n>> GFW as a handy example of a large history & that command as a handy\n>> example of something that segfaults on \"master\".\n>\n> Had you already experienced the segfault locally, without using the GFW\n> example? How many commits were present in that case?\n\nYes, I ran into it \"orginally\" just range-diffing as part of a local\nbuild process.\n\nI could dig up what revision range it was exactly, but does it matter?\n\n> The GFW example seems like it's taken the discussion in the wrong direction.\n>\n> For me:\n> $ git log git/master..origin/main --pretty=oneline | wc -l\n> 62105\n>\n> That's a lot of commits to have in a range diff. It's almost as big as\n> the whole of git/master\n>\n> $ git log git/master --pretty=oneline | wc -l\n> 65400\n>\n> Personally I'd like a way of trimming 'deadheads' that's a bit easier\n> that needing to remember Dscho's magic string [1], but time will tell.\n\nThere are some repos that move forward by 500-1k commits/day, and people\ndo cherry-pick patches etc. So wanting to range-diff after a couple of\nmonths is something you might do...\n\n>> So the point really isn't to say that we should fix range-diff becase\n>> it'll allow us to run this practically useful command on a git.git fork.\n>>\n>>> I fully agree that the range-diff should probably have a patch limit at\n>>> some sensible value.\n>> Why would it? If I'm willing to spend the CPU to produce a range-diff of\n>> an absurdly large range and I've got the memory why shouldn't we support\n>> it?\n>\n> There will always be a limit somewhere, and if it's not commit count or\n> other easily explained & checked limit it will be hard to rationalise\n> about why Git suddenly fails with an error (or segfault) in those\n> humungous case.\n\nI think it's fairly easy to explain the \"your system wouldn't let us\nmalloc more, we're dying\" that we get from xmalloc(), st_*() and the\nlike.\n\n>>\n>> We don't in cases like xdiff where it's not trivial to just raise the\n>> limits, but here it seems relatively easy.\n>>\n>> I think limits to save users from spending CPU time they didn't expect\n>> are reasonable, but then we can handle them like the diff/merge rename\n>> detection limits, i.e. print a warning/advice, and allow the user to\n>> opt-out.\n>>\n>> That also doesn't really apply here since \"diff/merge\" will/might still\n>> do something useful in those scenarios, whereas range-diff would just\n>> have truncated output.\n>>\n>>> The 'confusion' between the types size_t, long and int, does ripple\n>>> through a lot of portable code, as shown in the series. Not an easy problem.\n>> Yes, although here we're not just casting and overflowing types, but\n>> overflowing on multiplication and addition, whereas usually we'd just\n>> overflow on \"nr\" being too big for \"int\" or similar.\n> I've been very slowly looking at the `long` limits on GFW which have\n> very similar arithmetic issues for pointers, often with no clear answers.\n\nRight, that's to do with the whole \"long\" or whatever use in the\nobject.c and related code, but I don't think that's applicable here, is\nit?\n"},{"id":"444923","messageId":"54e16578-93f3-33e7-bd31-8909992e3407@iee.email","threadId":"57059","inReplyTo":"211224.86zgoqgd7q.gmgdl@evledraar.gmail.com","subject":"Re: [RFC PATCH 00/10] range-diff: fix segfault due to integer overflow","fromName":"Philip Oakley","fromEmail":"philipoakley@iee.email","sentAt":"2021-12-24T18:31:50Z","receivedAt":"2021-12-24T18:31:55Z","isPatch":true,"sender":{"key":"philipoakley@iee.email","avatar":"https://avatars.githubusercontent.com/u/914343?v=4"},"body":"On 24/12/2021 16:46, Ævar Arnfjörð Bjarmason wrote:\n> On Fri, Dec 24 2021, Philip Oakley wrote:\n>\n>> On 21/12/2021 23:36, Ævar Arnfjörð Bjarmason wrote:\n>>> On Tue, Dec 21 2021, Philip Oakley wrote:\n>>>\n>>>> Sorry for the late comment..\n>>>>\n>>>> On 10/12/2021 14:31, Johannes Schindelin wrote:\n>>>>> Hi Ævar,\n>>>>>\n>>>>> On Thu, 9 Dec 2021, Ævar Arnfjörð Bjarmason wrote:\n>>>>>\n>>>>>> The difference between \"master\" and \"git-for-windows/main\" is large\n>>>>>> enough that comparing the two will segfault on my system. This is\n>>>>>> because the range-diff code does some expensive calculations and will\n>>>>>> overflow the \"int\" type.\n>>>>> You are holding this thing wrong.\n>>>>>\n>>>>> The `main` branch of Git for Windows uses merging rebases, therefore you\n>>>>> need to use a commit range like\n>>>>> `git-for-windows/main^{/^Start.the.merging}..git-for-windows/main` and\n>>>>> compare it to `git-for-windows/main..master`.\n>>>> I'm not sure that a Git repo has an established way of indicating to how\n>>>> it's branching/merging/releasing workflow is set up, especially for\n>>>> projects with non-normative use cases, such as Git for Windows. We don't\n>>>> have a git document for covering  the different workflows in common use\n>>>> for easy reference and consistent terminology.\n>>>>\n>>>> The merging rebase flow, with 'fake' merge does solve a problem that\n>>>> git.git doesn't have but could easily be a common process for 'friendly\n>>>> forks' that follow an upstream with local patches. The choice of\n>>>> '{/^Start.the.merging}' is currently specific to the Git-for-Windows\n>>>> case making it harder to discover this useful maintainer method.\n>>> Yes, but let's not get lost in the weeds here. As I noted I just picked\n>>> GFW as a handy example of a large history & that command as a handy\n>>> example of something that segfaults on \"master\".\n>> Had you already experienced the segfault locally, without using the GFW\n>> example? How many commits were present in that case?\n> Yes, I ran into it \"orginally\" just range-diffing as part of a local\n> build process.\n>\n> I could dig up what revision range it was exactly, but does it matter?\nNo the particular range-diff doesn't matter, I was checking that this\nwasn't a confusion about the Git for Windows workflow.\n\n>\n>> The GFW example seems like it's taken the discussion in the wrong direction.\n>>\n>> For me:\n>> $ git log git/master..origin/main --pretty=oneline | wc -l\n>> 62105\n>>\n>> That's a lot of commits to have in a range diff. It's almost as big as\n>> the whole of git/master\n>>\n>> $ git log git/master --pretty=oneline | wc -l\n>> 65400\n>>\n>> Personally I'd like a way of trimming 'deadheads' that's a bit easier\n>> that needing to remember Dscho's magic string [1], but time will tell.\n> There are some repos that move forward by 500-1k commits/day, and people\n> do cherry-pick patches etc. So wanting to range-diff after a couple of\n> months is something you might do...\n\nIt feels to me that in such cases that maybe the algorithm may need\ntweaking for the needle in a haystack case ;-)\n>\n>>> So the point really isn't to say that we should fix range-diff becase\n>>> it'll allow us to run this practically useful command on a git.git fork.\n>>>\n>>>> I fully agree that the range-diff should probably have a patch limit at\n>>>> some sensible value.\n>>> Why would it? If I'm willing to spend the CPU to produce a range-diff of\n>>> an absurdly large range and I've got the memory why shouldn't we support\n>>> it?\n>> There will always be a limit somewhere, and if it's not commit count or\n>> other easily explained & checked limit it will be hard to rationalise\n>> about why Git suddenly fails with an error (or segfault) in those\n>> humungous case.\n> I think it's fairly easy to explain the \"your system wouldn't let us\n> malloc more, we're dying\" that we get from xmalloc(), st_*() and the\n> like.\nThat's better than a segfault, but does it give actionable information\nto the user as to what (& how much) they should do? Hence the comment\nabout a commit count measure.\n\n>>> We don't in cases like xdiff where it's not trivial to just raise the\n>>> limits, but here it seems relatively easy.\n>>>\n>>> I think limits to save users from spending CPU time they didn't expect\n>>> are reasonable, but then we can handle them like the diff/merge rename\n>>> detection limits, i.e. print a warning/advice, and allow the user to\n>>> opt-out.\n>>>\n>>> That also doesn't really apply here since \"diff/merge\" will/might still\n>>> do something useful in those scenarios, whereas range-diff would just\n>>> have truncated output.\n>>>\n>>>> The 'confusion' between the types size_t, long and int, does ripple\n>>>> through a lot of portable code, as shown in the series. Not an easy problem.\n>>> Yes, although here we're not just casting and overflowing types, but\n>>> overflowing on multiplication and addition, whereas usually we'd just\n>>> overflow on \"nr\" being too big for \"int\" or similar.\n>> I've been very slowly looking at the `long` limits on GFW which have\n>> very similar arithmetic issues for pointers, often with no clear answers.\n> Right, that's to do with the whole \"long\" or whatever use in the\n> object.c and related code, but I don't think that's applicable here, is\n> it?\n\nThat question was more about the policy aspects of ensuring that any\nproposals aren't 'head against a brick wall' when it comes to the\npotential intrusiveness.\n\nThanks for the clarifications.\n\nPhilip\n\n"}]}