{"thread":{"id":"64039","subject":"[PATCH] range-diff: add configurable memory limit for cost matrix","startedAt":"2025-08-26T17:18:16Z","lastAt":"2025-08-29T16:33:58Z","messageCount":18,"participants":["Paulo Casaretto via GitGitGadget","Junio C Hamano","pcasaretto via GitGitGadget","Elijah Newren","Paulo L F Casaretto"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"524980","messageId":"pull.1958.git.1756228693233.gitgitgadget@gmail.com","threadId":"64039","inReplyTo":null,"subject":"[PATCH] range-diff: add configurable memory limit for cost matrix","fromName":"Paulo Casaretto via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-08-26T17:18:13Z","receivedAt":"2025-08-26T17:18:16Z","isPatch":true,"sender":{"key":"name:Paulo Casaretto","avatar":null},"body":"From: pcasaretto \n\nWhen comparing large commit ranges (e.g., 250,000+ commits), range-diff\nattempts to allocate an n×n cost matrix that can exhaust available\nmemory. For example, with 256,784 commits (n = 513,568), the matrix\nwould require approximately 256GB of memory (513,568² × 4 bytes),\ncausing either immediate segmentation faults due to integer overflow or\nsystem hangs.\n\nAdd a memory limit check in get_correspondences() before allocating the\ncost matrix. This check uses the total size in bytes (n² × sizeof(int))\nand compares it against a configurable maximum, preventing both\nexcessive memory usage and integer overflow issues.\n\nThe limit is configurable via a new --max-memory option that accepts\nhuman-readable sizes (e.g., \"1G\", \"500M\"). The default is 4GB for 64 bit\nsystems and 2GB for 32 bit systems. This allows comparing ranges of\napproximately 32,000 (16,000) commits - generous for real-world use cases\nwhile preventing impractical operations.\n\nWhen the limit is exceeded, range-diff now displays a clear error\nmessage showing both the requested memory size and the maximum allowed,\nformatted in human-readable units for better user experience.\n\nExample usage:\n git range-diff --max-memory=1G branch1...branch2\n git range-diff --max-memory=500M base..topic1 base..topic2\n\nThis approach was chosen over alternatives:\n- Pre-counting commits: Would require spawning additional git processes\n and reading all commits twice\n- Limiting by commit count: Less precise than actual memory usage\n- Streaming approach: Would require significant refactoring of the\n current algorithm\n\nThis issue was previously discussed in:\nhttps://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n\nAcked-by: Johannes Schindelin johannes.schindelin@gmx.de\nSigned-off-by: pcasaretto \n---\n range-diff: add configurable memory limit for cost matrix\n \n \n Problem Description\n ===================\n \n When git range-diff is given extremely large ranges, it can result in\n either:\n \n 1. Segmentation fault due to integer overflow in array index\n calculations\n 2. Excessive memory consumption leading to system hangs or OOM kills\n 3. Poor user experience with the command appearing to hang for minutes\n \n \n Reproduction Case\n =================\n \n In a Shopify's large monorepo a range-diff command like this crashes\n after several minutes with a SIGBUS error\n \n $ git range-diff 4430f36511..316c1276c6 cb5240b6a8..2bbd292091\n \n \n Range statistics:\n \n * First range: 256,783 commits\n * Second range: 1 commit\n * Total: 256,784 commits\n * Memory required for cost matrix: n² × 4 bytes = ~260GB\n \n \n Stack Trace (Segmentation Fault)\n ================================\n \n (lldb) bt\n * thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x6e000ae3b8)\n * frame #0: 0x000000010029a284 git`get_correspondences(a=0x000000016fde6188, b=0x000000016fde6160, creation_factor=60) at range-diff.c:356:20\n frame #1: 0x0000000100299310 git`show_range_diff(range1=\"4430f36511cbacf5c517c6851e2b8508a72dfd30..316c1276c63f55ad9413fa18bf3b6483564a9cf4\", range2=\"cb5240b6a8ba59b4a1f282559ee0742721b0cafc..2bbd292091e376d177ce62e264dae8872ca6be5a\", range_diff_opts=0x000000016fde6308) at range-diff.c:593:3\n frame #2: 0x00000001000c719c git`cmd_range_diff(argc=2, argv=0x0000600000bcd8c0, prefix=\"areas/core/shopify/\", repo=0x0000000100468b20) at range-diff.c:167:8\n frame #3: 0x000000010000277c git`run_builtin(p=0x00000001004408d8, argc=3, argv=0x0000600000bcd8c0, repo=0x0000000100468b20) at git.c:480:11\n frame #4: 0x0000000100001020 git`handle_builtin(args=0x000000016fde6c70) at git.c:746:9\n frame #5: 0x0000000100002074 git`run_argv(args=0x000000016fde6c70) at git.c:813:4\n frame #6: 0x0000000100000d3c git`cmd_main(argc=3, argv=0x000000016fde7350) at git.c:953:19\n frame #7: 0x000000010012750c git`main(argc=4, argv=0x000000016fde7348) at common-main.c:9:11\n frame #8: 0x000000018573ab98 dyld`start + 6076\n \n \n \n Root Cause Analysis\n ===================\n \n The crash occurs in get_correspondences() at line 356:\n \n static void get_correspondences(struct string_list *a, struct string_list *b, ...)\n {\n int n = a->nr + b->nr; // Integer overflow: 256,784 fits in int\n ...\n ALLOC_ARRAY(cost, st_mult(n, n)); // Would allocate ~260GB\n ...\n cost[i + n * j] = c; // Line 356: Invalid memory access\n }\n \n \n Problems:\n \n 1. Integer overflow: While n=256,784 fits in an int, n*n overflows\n 2. Memory allocation: Even with proper types, allocating 260GB is\n impractical\n \n \n Solution\n ========\n \n Add a memory limit check in get_correspondences() before allocating the\n cost matrix. This check uses the total size in bytes (n² × sizeof(int))\n and compares it against a configurable maximum, preventing both\n excessive memory usage and integer overflow issues.\n \n The limit is configurable via a new --max-memory option that accepts\n human-readable sizes (e.g., \"1G\", \"500M\"). The default is 4GB for 64 bit\n systems and 2GB for 32 bit systems. This allows comparing ranges of\n approximately 32,000 (16,000) commits - generous for real-world use\n cases while preventing impractical operations.\n \n When the limit is exceeded, range-diff now displays a clear error\n message showing both the requested memory size and the maximum allowed,\n formatted in human-readable units for better user experience.\n \n Example usage: git range-diff --max-memory=1G branch1...branch2 git\n range-diff --max-memory=500M base..topic1 base..topic2\n \n This approach was chosen over alternatives:\n \n * Pre-counting commits: Would require spawning additional git processes\n and reading all commits twice\n * Limiting by commit count: Less precise than actual memory usage\n * Streaming approach: Would require significant refactoring of the\n current algorithm\n \n This issue was previously discussed in:\n https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n \n Acked-by: Johannes Schindelin johannes.schindelin@gmx.de\n [https://github.com/gitgitgadget/git/pull/1958#issuecomment-3224133138]\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1958%2Fpcasaretto%2Frange-diff-size-limit-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1958/pcasaretto/range-diff-size-limit-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1958\n\n builtin/log.c | 1 +\n builtin/range-diff.c | 30 ++++++++++++++++++++++++++----\n log-tree.c | 1 +\n range-diff.c | 35 +++++++++++++++++++++++++----------\n range-diff.h | 5 +++++\n 5 files changed, 58 insertions(+), 14 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex c2f8bbf8630..5f552d14c0f 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1404,6 +1404,7 @@ static void make_cover_letter(struct rev_info *rev, int use_separate_file,\n \t\tstruct range_diff_options range_diff_opts = {\n \t\t\t.creation_factor = rev->creation_factor,\n \t\t\t.dual_color = 1,\n+\t\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t\t.diffopt = &opts,\n \t\t\t.other_arg = &other_arg\n \t\t};\ndiff --git a/builtin/range-diff.c b/builtin/range-diff.c\nindex a563abff5fe..10fa82fd285 100644\n--- a/builtin/range-diff.c\n+++ b/builtin/range-diff.c\n@@ -6,6 +6,7 @@\n #include \"parse-options.h\"\n #include \"range-diff.h\"\n #include \"config.h\"\n+#include \"parse.h\"\n \n \n static const char * const builtin_range_diff_usage[] = {\n@@ -15,6 +16,22 @@ N_(\"git range-diff [] \"),\n NULL\n };\n \n+static int parse_max_memory(const struct option *opt, const char *arg, int unset)\n+{\n+\tsize_t *max_memory = opt->value;\n+\tuintmax_t val;\n+\n+\tif (unset) {\n+\t\treturn 0;\n+\t}\n+\n+\tif (!git_parse_unsigned(arg, &val, SIZE_MAX))\n+\t\treturn error(_(\"invalid max-memory value: %s\"), arg);\n+\n+\t*max_memory = (size_t)val;\n+\treturn 0;\n+}\n+\n int cmd_range_diff(int argc,\n \t\t const char **argv,\n \t\t const char *prefix,\n@@ -25,6 +42,7 @@ int cmd_range_diff(int argc,\n \tstruct strvec diff_merges_arg = STRVEC_INIT;\n \tstruct range_diff_options range_diff_opts = {\n \t\t.creation_factor = RANGE_DIFF_CREATION_FACTOR_DEFAULT,\n+\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t.diffopt = &diffopt,\n \t\t.other_arg = &other_arg\n \t};\n@@ -33,17 +51,21 @@ int cmd_range_diff(int argc,\n \t\tOPT_INTEGER(0, \"creation-factor\",\n \t\t\t &range_diff_opts.creation_factor,\n \t\t\t N_(\"percentage by which creation is weighted\")),\n+\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n+\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n+\t\tOPT_BOOL(0, \"left-only\", &left_only,\n+\t\t\t N_(\"only emit output related to the first range\")),\n+\t\tOPT_CALLBACK(0, \"max-memory\", &range_diff_opts.max_memory,\n+\t\t\t N_(\"size\"),\n+\t\t\t N_(\"maximum memory for cost matrix (default 4G)\"),\n+\t\t\t parse_max_memory),\n \t\tOPT_BOOL(0, \"no-dual-color\", &simple_color,\n \t\t\t N_(\"use simple diff colors\")),\n \t\tOPT_PASSTHRU_ARGV(0, \"notes\", &other_arg,\n \t\t\t\t N_(\"notes\"), N_(\"passed to 'git log'\"),\n \t\t\t\t PARSE_OPT_OPTARG),\n-\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n-\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n \t\tOPT_PASSTHRU_ARGV(0, \"remerge-diff\", &diff_merges_arg, NULL,\n \t\t\t\t N_(\"passed to 'git log'\"), PARSE_OPT_NOARG),\n-\t\tOPT_BOOL(0, \"left-only\", &left_only,\n-\t\t\t N_(\"only emit output related to the first range\")),\n \t\tOPT_BOOL(0, \"right-only\", &right_only,\n \t\t\t N_(\"only emit output related to the second range\")),\n \t\tOPT_END()\ndiff --git a/log-tree.c b/log-tree.c\nindex 233bf9f227c..73d21f71764 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -717,6 +717,7 @@ static void show_diff_of_diff(struct rev_info *opt)\n \t\tstruct range_diff_options range_diff_opts = {\n \t\t\t.creation_factor = opt->creation_factor,\n \t\t\t.dual_color = 1,\n+\t\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t\t.diffopt = &opts\n \t\t};\n \ndiff --git a/range-diff.c b/range-diff.c\nindex 8a2dcbee322..6e9b6b115e5 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -21,6 +21,7 @@\n #include \"apply.h\"\n #include \"revision.h\"\n \n+\n struct patch_util {\n \t/* For the search for an exact match */\n \tstruct hashmap_entry e;\n@@ -287,8 +288,8 @@ static void find_exact_matches(struct string_list *a, struct string_list *b)\n }\n \n static int diffsize_consume(void *data,\n-\t\t\t char *line UNUSED,\n-\t\t\t unsigned long len UNUSED)\n+\t\t\t char *line UNUSED,\n+\t\t\t unsigned long len UNUSED)\n {\n \t(*(int *)data)++;\n \treturn 0;\n@@ -325,13 +326,24 @@ static int diffsize(const char *a, const char *b)\n }\n \n static void get_correspondences(struct string_list *a, struct string_list *b,\n-\t\t\t\tint creation_factor)\n+\t\t\t\tint creation_factor, size_t max_memory)\n {\n \tint n = a->nr + b->nr;\n \tint *cost, c, *a2b, *b2a;\n \tint i, j;\n-\n-\tALLOC_ARRAY(cost, st_mult(n, n));\n+\tsize_t cost_size = st_mult(n, n);\n+\tsize_t cost_bytes = st_mult(sizeof(int), cost_size);\n+\tif (cost_bytes >= max_memory) {\n+\t\tstruct strbuf cost_str = STRBUF_INIT;\n+\t\tstruct strbuf max_str = STRBUF_INIT;\n+\t\tstrbuf_humanise_bytes(&cost_str, cost_bytes);\n+\t\tstrbuf_humanise_bytes(&max_str, max_memory);\n+\t\tdie(_(\"range-diff: unable to compute the range-diff, since it \"\n+\t\t \"exceeds the maximum memory for the cost matrix: %s \"\n+\t\t \"(%\"PRIuMAX\" bytes) needed, %s (%\"PRIuMAX\" bytes) available\"),\n+\t\t cost_str.buf, (uintmax_t)cost_bytes, max_str.buf, (uintmax_t)max_memory);\n+\t}\n+\tALLOC_ARRAY(cost, cost_size);\n \tALLOC_ARRAY(a2b, n);\n \tALLOC_ARRAY(b2a, n);\n \n@@ -351,7 +363,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\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\t a_util->diffsize * creation_factor / 100 :\n+\t\t\t COST_MAX;\n \t\tfor (j = b->nr; j < n; j++)\n \t\t\tcost[i + n * j] = c;\n \t}\n@@ -360,7 +373,8 @@ 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\t util->diffsize * creation_factor / 100 :\n+\t\t\t COST_MAX;\n \t\tfor (i = a->nr; i < n; i++)\n \t\t\tcost[i + n * j] = c;\n \t}\n@@ -539,7 +553,7 @@ static void output(struct string_list *a, struct string_list *b,\n \t\tif (i < a->nr && a_util->matching < 0) {\n \t\t\tif (!range_diff_opts->right_only)\n \t\t\t\toutput_pair_header(&opts, patch_no_width,\n-\t\t\t\t\t &buf, &dashes, a_util, NULL);\n+\t\t\t\t\t\t &buf, &dashes, a_util, NULL);\n \t\t\ti++;\n \t\t\tcontinue;\n \t\t}\n@@ -548,7 +562,7 @@ static void output(struct string_list *a, struct string_list *b,\n \t\twhile (j < b->nr && b_util->matching < 0) {\n \t\t\tif (!range_diff_opts->left_only)\n \t\t\t\toutput_pair_header(&opts, patch_no_width,\n-\t\t\t\t\t &buf, &dashes, NULL, b_util);\n+\t\t\t\t\t\t &buf, &dashes, NULL, b_util);\n \t\t\tb_util = ++j < b->nr ? b->items[j].util : NULL;\n \t\t}\n \n@@ -591,7 +605,8 @@ int show_range_diff(const char *range1, const char *range2,\n \tif (!res) {\n \t\tfind_exact_matches(&branch1, &branch2);\n \t\tget_correspondences(&branch1, &branch2,\n-\t\t\t\t range_diff_opts->creation_factor);\n+\t\t\t\t range_diff_opts->creation_factor,\n+\t\t\t\t range_diff_opts->max_memory);\n \t\toutput(&branch1, &branch2, range_diff_opts);\n \t}\n \ndiff --git a/range-diff.h b/range-diff.h\nindex cd85000b5a0..9d39818e349 100644\n--- a/range-diff.h\n+++ b/range-diff.h\n@@ -5,6 +5,10 @@\n #include \"strvec.h\"\n \n #define RANGE_DIFF_CREATION_FACTOR_DEFAULT 60\n+#define RANGE_DIFF_MAX_MEMORY_DEFAULT \\\n+\t(sizeof(void*) >= 8 ? \\\n+\t\t((size_t)(1024L * 1024L) * (size_t)(4L * 1024L)) : /* 4GB on 64-bit */ \\\n+\t\t((size_t)(1024L * 1024L) * (size_t)(2L * 1024L))) /* 2GB on 32-bit */\n \n /*\n * A much higher value than the default, when we KNOW we are comparing\n@@ -17,6 +21,7 @@ struct range_diff_options {\n \tunsigned dual_color:1;\n \tunsigned left_only:1, right_only:1;\n \tunsigned include_merges:1;\n+\tsize_t max_memory;\n \tconst struct diff_options *diffopt; /* may be NULL */\n \tconst struct strvec *other_arg; /* may be NULL */\n };\n\nbase-commit: 954d33a9757fcfab723a824116902f1eb16e05f7\n-- \ngitgitgadget\n"},{"id":"524995","messageId":"xmqqzfblj3hq.fsf@gitster.g","threadId":"64039","inReplyTo":"pull.1958.git.1756228693233.gitgitgadget@gmail.com","subject":"Re: [PATCH] range-diff: add configurable memory limit for cost matrix","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-26T19:18:41Z","receivedAt":"2025-08-26T19:18:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Paulo Casaretto via GitGitGadget\" writes:\n\n> From: pcasaretto \n\n\n\nIt is usual to see a less human readable name embedded in the commit\nobject than the mail header when a mail comes from GGG. \n\nJust in case you want to be known to this community as \"Paulo\nCasaretto\", not \"pcasaretto\", I thought I'd point it out that you\nmay want to redo the commit. I do not mind what name you like to\nuse, as long as it is identifiable, and From: identity matches the\nidentity you add your Signed-off-by: with.\n\n\n\n> Acked-by: Johannes Schindelin johannes.schindelin@gmx.de\n\nIt is unusual to lack <> around e-mail address here.\n\n> Signed-off-by: pcasaretto \n> ---\n> range-diff: add configurable memory limit for cost matrix\n\n> +static int parse_max_memory(const struct option *opt, const char *arg, int unset)\n> +{\n> +\tsize_t *max_memory = opt->value;\n> +\tuintmax_t val;\n> +\n> +\tif (unset) {\n> +\t\treturn 0;\n> +\t}\n\nNo unnecessary {braces} around a single statement, please.\n\n> +\tif (!git_parse_unsigned(arg, &val, SIZE_MAX))\n> +\t\treturn error(_(\"invalid max-memory value: %s\"), arg);\n> +\n> +\t*max_memory = (size_t)val;\n> +\treturn 0;\n> +}\n\n> @@ -33,17 +51,21 @@ int cmd_range_diff(int argc,\n> \t\tOPT_INTEGER(0, \"creation-factor\",\n> \t\t\t &range_diff_opts.creation_factor,\n> \t\t\t N_(\"percentage by which creation is weighted\")),\n> +\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n> +\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n> +\t\tOPT_BOOL(0, \"left-only\", &left_only,\n> +\t\t\t N_(\"only emit output related to the first range\")),\n> +\t\tOPT_CALLBACK(0, \"max-memory\", &range_diff_opts.max_memory,\n> +\t\t\t N_(\"size\"),\n> +\t\t\t N_(\"maximum memory for cost matrix (default 4G)\"),\n> +\t\t\t parse_max_memory),\n> \t\tOPT_BOOL(0, \"no-dual-color\", &simple_color,\n> \t\t\t N_(\"use simple diff colors\")),\n> \t\tOPT_PASSTHRU_ARGV(0, \"notes\", &other_arg,\n> \t\t\t\t N_(\"notes\"), N_(\"passed to 'git log'\"),\n> \t\t\t\t PARSE_OPT_OPTARG),\n> -\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n> -\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n> \t\tOPT_PASSTHRU_ARGV(0, \"remerge-diff\", &diff_merges_arg, NULL,\n> \t\t\t\t N_(\"passed to 'git log'\"), PARSE_OPT_NOARG),\n> -\t\tOPT_BOOL(0, \"left-only\", &left_only,\n> -\t\t\t N_(\"only emit output related to the first range\")),\n> \t\tOPT_BOOL(0, \"right-only\", &right_only,\n> \t\t\t N_(\"only emit output related to the second range\")),\n> \t\tOPT_END()\n\nThis seems to mix unrelated changes. Please don't.\n\nOr if the reordering of options do have a reason to exist in _this_\ncommit, please justify it in your proposed log message. Even if\nthere were a good reason for reordering existing options, I strongly\nsuspect that the change would want to be done in a separate,\npreparatory-clean-up commit (i.e., making this topic a two-patch\nseries), because it has nothing to do with preventing inefficient\ncost matrix computation from consuming too much memory, which _is_\nthe theme of this commit.\n\n> diff --git a/range-diff.c b/range-diff.c\n> index 8a2dcbee322..6e9b6b115e5 100644\n> --- a/range-diff.c\n> +++ b/range-diff.c\n> @@ -21,6 +21,7 @@\n> #include \"apply.h\"\n> #include \"revision.h\"\n> \n> +\n\nUnrelated, unexplained, and unnecessary change snuck in? Please\nproof-read the patch yourself before sending.\n\n> @@ -287,8 +288,8 @@ static void find_exact_matches(struct string_list *a, struct string_list *b)\n> }\n> \n> static int diffsize_consume(void *data,\n> -\t\t\t char *line UNUSED,\n> -\t\t\t unsigned long len UNUSED)\n> +\t\t\t char *line UNUSED,\n> +\t\t\t unsigned long len UNUSED)\n\nWhat is this change about???\n\n> static void get_correspondences(struct string_list *a, struct string_list *b,\n> -\t\t\t\tint creation_factor)\n> +\t\t\t\tint creation_factor, size_t max_memory)\n> {\n> \tint n = a->nr + b->nr;\n> \tint *cost, c, *a2b, *b2a;\n> \tint i, j;\n> -\n> -\tALLOC_ARRAY(cost, st_mult(n, n));\n> +\tsize_t cost_size = st_mult(n, n);\n> +\tsize_t cost_bytes = st_mult(sizeof(int), cost_size);\n> +\tif (cost_bytes >= max_memory) {\n> +\t\tstruct strbuf cost_str = STRBUF_INIT;\n> +\t\tstruct strbuf max_str = STRBUF_INIT;\n> +\t\tstrbuf_humanise_bytes(&cost_str, cost_bytes);\n> +\t\tstrbuf_humanise_bytes(&max_str, max_memory);\n> +\t\tdie(_(\"range-diff: unable to compute the range-diff, since it \"\n> +\t\t \"exceeds the maximum memory for the cost matrix: %s \"\n> +\t\t \"(%\"PRIuMAX\" bytes) needed, %s (%\"PRIuMAX\" bytes) available\"),\n> +\t\t cost_str.buf, (uintmax_t)cost_bytes, max_str.buf, (uintmax_t)max_memory);\n> +\t}\n> +\tALLOC_ARRAY(cost, cost_size);\n\nNicely done.\n\n> @@ -351,7 +363,8 @@ static void get_correspondences(struct string_list *a, struct string_list *b,\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\t a_util->diffsize * creation_factor / 100 :\n> +\t\t\t COST_MAX;\n> \t\tfor (j = b->nr; j < n; j++)\n> \t\t\tcost[i + n * j] = c;\n> \t}\n\nThere seem to be other unrelated changes indentation-only changes\nmixed in to the changes to this file, not just this one.\n\nAs a style fix, \n\n\t\tc = a_util->matching < 0\n\t\t ? a_util->diffsize * creation_factor / 100\n\t\t : COST_MAX;\n\nwould be easier to follow and read, but please do not do such a\ncosmetic clean-up in the same patch. Do them in a separate\npreliminary clean-up patch before the \"real work\".\n\n> @@ -591,7 +605,8 @@ int show_range_diff(const char *range1, const char *range2,\n> \tif (!res) {\n> \t\tfind_exact_matches(&branch1, &branch2);\n> \t\tget_correspondences(&branch1, &branch2,\n> -\t\t\t\t range_diff_opts->creation_factor);\n> +\t\t\t\t range_diff_opts->creation_factor,\n> +\t\t\t\t range_diff_opts->max_memory);\n> \t\toutput(&branch1, &branch2, range_diff_opts);\n> \t}\n\nOK.\n"},{"id":"525088","messageId":"pull.1958.v2.git.1756370289.gitgitgadget@gmail.com","threadId":"64039","inReplyTo":"pull.1958.git.1756228693233.gitgitgadget@gmail.com","subject":"[PATCH v2 0/2] range-diff: add configurable memory limit for cost matrix","fromName":"Paulo Casaretto via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-08-28T08:38:06Z","receivedAt":"2025-08-28T08:38:13Z","isPatch":true,"sender":{"key":"name:Paulo Casaretto","avatar":null},"body":"\nProblem Description\n===================\n\nWhen git range-diff is given extremely large ranges, it can result in\neither:\n\n 1. Segmentation fault due to integer overflow in array index calculations\n 2. Excessive memory consumption leading to system hangs or OOM kills\n 3. Poor user experience with the command appearing to hang for minutes\n\n\nReproduction Case\n=================\n\nIn a Shopify's large monorepo a range-diff command like this crashes after\nseveral minutes with a SIGBUS error\n\n$ git range-diff 4430f36511..316c1276c6 cb5240b6a8..2bbd292091\n\n\nRange statistics:\n\n * First range: 256,783 commits\n * Second range: 1 commit\n * Total: 256,784 commits\n * Memory required for cost matrix: n² × 4 bytes = ~260GB\n\n\nStack Trace (Segmentation Fault)\n================================\n\n(lldb) bt\n* thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x6e000ae3b8)\n * frame #0: 0x000000010029a284 git`get_correspondences(a=0x000000016fde6188, b=0x000000016fde6160, creation_factor=60) at range-diff.c:356:20\n frame #1: 0x0000000100299310 git`show_range_diff(range1=\"4430f36511cbacf5c517c6851e2b8508a72dfd30..316c1276c63f55ad9413fa18bf3b6483564a9cf4\", range2=\"cb5240b6a8ba59b4a1f282559ee0742721b0cafc..2bbd292091e376d177ce62e264dae8872ca6be5a\", range_diff_opts=0x000000016fde6308) at range-diff.c:593:3\n frame #2: 0x00000001000c719c git`cmd_range_diff(argc=2, argv=0x0000600000bcd8c0, prefix=\"areas/core/shopify/\", repo=0x0000000100468b20) at range-diff.c:167:8\n frame #3: 0x000000010000277c git`run_builtin(p=0x00000001004408d8, argc=3, argv=0x0000600000bcd8c0, repo=0x0000000100468b20) at git.c:480:11\n frame #4: 0x0000000100001020 git`handle_builtin(args=0x000000016fde6c70) at git.c:746:9\n frame #5: 0x0000000100002074 git`run_argv(args=0x000000016fde6c70) at git.c:813:4\n frame #6: 0x0000000100000d3c git`cmd_main(argc=3, argv=0x000000016fde7350) at git.c:953:19\n frame #7: 0x000000010012750c git`main(argc=4, argv=0x000000016fde7348) at common-main.c:9:11\n frame #8: 0x000000018573ab98 dyld`start + 6076\n\n\n\nRoot Cause Analysis\n===================\n\nThe crash occurs in get_correspondences() at line 356:\n\nstatic void get_correspondences(struct string_list *a, struct string_list *b, ...)\n{\n int n = a->nr + b->nr; // Integer overflow: 256,784 fits in int\n ...\n ALLOC_ARRAY(cost, st_mult(n, n)); // Would allocate ~260GB\n ...\n cost[i + n * j] = c; // Line 356: Invalid memory access\n}\n\n\nProblems:\n\n 1. Integer overflow: While n=256,784 fits in an int, n*n overflows\n 2. Memory allocation: Even with proper types, allocating 260GB is\n impractical\n\n\nSolution\n========\n\nAdd a memory limit check in get_correspondences() before allocating the cost\nmatrix. This check uses the total size in bytes (n² × sizeof(int)) and\ncompares it against a configurable maximum, preventing both excessive memory\nusage and integer overflow issues.\n\nThe limit is configurable via a new --max-memory option that accepts\nhuman-readable sizes (e.g., \"1G\", \"500M\"). The default is 4GB for 64 bit\nsystems and 2GB for 32 bit systems. This allows comparing ranges of\napproximately 32,000 (16,000) commits - generous for real-world use cases\nwhile preventing impractical operations.\n\nWhen the limit is exceeded, range-diff now displays a clear error message\nshowing both the requested memory size and the maximum allowed, formatted in\nhuman-readable units for better user experience.\n\nExample usage: git range-diff --max-memory=1G branch1...branch2 git\nrange-diff --max-memory=500M base..topic1 base..topic2\n\nThis approach was chosen over alternatives:\n\n * Pre-counting commits: Would require spawning additional git processes and\n reading all commits twice\n * Limiting by commit count: Less precise than actual memory usage\n * Streaming approach: Would require significant refactoring of the current\n algorithm\n\nThis issue was previously discussed in:\nhttps://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n\nAcked-by: Johannes Schindelin johannes.schindelin@gmx.de\n[https://github.com/gitgitgadget/git/pull/1958#issuecomment-3224133138]\n\npcasaretto (2):\n range-diff: reorder options lexicographically\n range-diff: add configurable memory limit for cost matrix\n\n builtin/log.c | 1 +\n builtin/range-diff.c | 29 +++++++++++++++++++++++++----\n log-tree.c | 1 +\n range-diff.c | 20 ++++++++++++++++----\n range-diff.h | 5 +++++\n 5 files changed, 48 insertions(+), 8 deletions(-)\n\n\nbase-commit: 954d33a9757fcfab723a824116902f1eb16e05f7\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1958%2Fpcasaretto%2Frange-diff-size-limit-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1958/pcasaretto/range-diff-size-limit-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1958\n\nRange-diff vs v1:\n\n -: ----------- > 1: ec5dcdf9d00 range-diff: reorder options lexicographically\n 1: 5cf3e8921a7 ! 2: c81f920fee0 range-diff: add configurable memory limit for cost matrix\n @@ Commit message\n This issue was previously discussed in:\n https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n \n - Acked-by: Johannes Schindelin johannes.schindelin@gmx.de\n - Signed-off-by: pcasaretto \n + Acked-by: Johannes Schindelin \n + Signed-off-by: Paulo Casaretto \n \n ## builtin/log.c ##\n @@ builtin/log.c: static void make_cover_letter(struct rev_info *rev, int use_separate_file,\n @@ builtin/range-diff.c: N_(\"git range-diff [] \"\n +\tsize_t *max_memory = opt->value;\n +\tuintmax_t val;\n +\n -+\tif (unset) {\n ++\tif (unset)\n +\t\treturn 0;\n -+\t}\n +\n +\tif (!git_parse_unsigned(arg, &val, SIZE_MAX))\n +\t\treturn error(_(\"invalid max-memory value: %s\"), arg);\n @@ builtin/range-diff.c: int cmd_range_diff(int argc,\n \t\t.other_arg = &other_arg\n \t};\n @@ builtin/range-diff.c: int cmd_range_diff(int argc,\n - \t\tOPT_INTEGER(0, \"creation-factor\",\n - \t\t\t &range_diff_opts.creation_factor,\n - \t\t\t N_(\"percentage by which creation is weighted\")),\n -+\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n -+\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n -+\t\tOPT_BOOL(0, \"left-only\", &left_only,\n -+\t\t\t N_(\"only emit output related to the first range\")),\n + \t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n + \t\tOPT_BOOL(0, \"left-only\", &left_only,\n + \t\t\t N_(\"only emit output related to the first range\")),\n +\t\tOPT_CALLBACK(0, \"max-memory\", &range_diff_opts.max_memory,\n +\t\t\t N_(\"size\"),\n +\t\t\t N_(\"maximum memory for cost matrix (default 4G)\"),\n @@ builtin/range-diff.c: int cmd_range_diff(int argc,\n \t\tOPT_BOOL(0, \"no-dual-color\", &simple_color,\n \t\t\t N_(\"use simple diff colors\")),\n \t\tOPT_PASSTHRU_ARGV(0, \"notes\", &other_arg,\n - \t\t\t\t N_(\"notes\"), N_(\"passed to 'git log'\"),\n - \t\t\t\t PARSE_OPT_OPTARG),\n --\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n --\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n - \t\tOPT_PASSTHRU_ARGV(0, \"remerge-diff\", &diff_merges_arg, NULL,\n - \t\t\t\t N_(\"passed to 'git log'\"), PARSE_OPT_NOARG),\n --\t\tOPT_BOOL(0, \"left-only\", &left_only,\n --\t\t\t N_(\"only emit output related to the first range\")),\n - \t\tOPT_BOOL(0, \"right-only\", &right_only,\n - \t\t\t N_(\"only emit output related to the second range\")),\n - \t\tOPT_END()\n \n ## log-tree.c ##\n @@ log-tree.c: static void show_diff_of_diff(struct rev_info *opt)\n @@ log-tree.c: static void show_diff_of_diff(struct rev_info *opt)\n \n \n ## range-diff.c ##\n -@@\n - #include \"apply.h\"\n - #include \"revision.h\"\n - \n -+\n - struct patch_util {\n - \t/* For the search for an exact match */\n - \tstruct hashmap_entry e;\n -@@ range-diff.c: static void find_exact_matches(struct string_list *a, struct string_list *b)\n - }\n - \n - static int diffsize_consume(void *data,\n --\t\t\t char *line UNUSED,\n --\t\t\t unsigned long len UNUSED)\n -+\t\t\t char *line UNUSED,\n -+\t\t\t unsigned long len UNUSED)\n - {\n - \t(*(int *)data)++;\n - \treturn 0;\n @@ range-diff.c: static int diffsize(const char *a, const char *b)\n }\n \n @@ range-diff.c: static int diffsize(const char *a, const char *b)\n \tALLOC_ARRAY(a2b, n);\n \tALLOC_ARRAY(b2a, n);\n \n -@@ range-diff.c: static void get_correspondences(struct string_list *a, struct string_list *b,\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\t a_util->diffsize * creation_factor / 100 :\n -+\t\t\t COST_MAX;\n - \t\tfor (j = b->nr; j < n; j++)\n - \t\t\tcost[i + n * j] = c;\n - \t}\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\t util->diffsize * creation_factor / 100 :\n -+\t\t\t COST_MAX;\n - \t\tfor (i = a->nr; i < n; i++)\n - \t\t\tcost[i + n * j] = c;\n - \t}\n -@@ range-diff.c: static void output(struct string_list *a, struct string_list *b,\n - \t\tif (i < a->nr && a_util->matching < 0) {\n - \t\t\tif (!range_diff_opts->right_only)\n - \t\t\t\toutput_pair_header(&opts, patch_no_width,\n --\t\t\t\t\t &buf, &dashes, a_util, NULL);\n -+\t\t\t\t\t\t &buf, &dashes, a_util, NULL);\n - \t\t\ti++;\n - \t\t\tcontinue;\n - \t\t}\n -@@ range-diff.c: static void output(struct string_list *a, struct string_list *b,\n - \t\twhile (j < b->nr && b_util->matching < 0) {\n - \t\t\tif (!range_diff_opts->left_only)\n - \t\t\t\toutput_pair_header(&opts, patch_no_width,\n --\t\t\t\t\t &buf, &dashes, NULL, b_util);\n -+\t\t\t\t\t\t &buf, &dashes, NULL, b_util);\n - \t\t\tb_util = ++j < b->nr ? b->items[j].util : NULL;\n - \t\t}\n - \n @@ range-diff.c: int show_range_diff(const char *range1, const char *range2,\n \tif (!res) {\n \t\tfind_exact_matches(&branch1, &branch2);\n\n-- \ngitgitgadget\n"},{"id":"525089","messageId":"ec5dcdf9d00473417b1f0b676a485f01076ce075.1756370289.git.gitgitgadget@gmail.com","threadId":"64039","inReplyTo":"pull.1958.v2.git.1756370289.gitgitgadget@gmail.com","subject":"[PATCH v2 1/2] range-diff: reorder options lexicographically","fromName":"pcasaretto via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-08-28T08:38:07Z","receivedAt":"2025-08-28T08:38:14Z","isPatch":true,"sender":{"key":"name:pcasaretto","avatar":null},"body":"From: pcasaretto \n\nReorder the command-line options in builtin/range-diff.c to be in\nlexicographic order for better organization and readability. This is\na preparatory cleanup with no functional changes.\n\nSigned-off-by: Paulo Casaretto \n---\n builtin/range-diff.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/range-diff.c b/builtin/range-diff.c\nindex a563abff5fee..283583a80d0b 100644\n--- a/builtin/range-diff.c\n+++ b/builtin/range-diff.c\n@@ -33,17 +33,17 @@ int cmd_range_diff(int argc,\n \t\tOPT_INTEGER(0, \"creation-factor\",\n \t\t\t &range_diff_opts.creation_factor,\n \t\t\t N_(\"percentage by which creation is weighted\")),\n+\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n+\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n+\t\tOPT_BOOL(0, \"left-only\", &left_only,\n+\t\t\t N_(\"only emit output related to the first range\")),\n \t\tOPT_BOOL(0, \"no-dual-color\", &simple_color,\n \t\t\t N_(\"use simple diff colors\")),\n \t\tOPT_PASSTHRU_ARGV(0, \"notes\", &other_arg,\n \t\t\t\t N_(\"notes\"), N_(\"passed to 'git log'\"),\n \t\t\t\t PARSE_OPT_OPTARG),\n-\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n-\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n \t\tOPT_PASSTHRU_ARGV(0, \"remerge-diff\", &diff_merges_arg, NULL,\n \t\t\t\t N_(\"passed to 'git log'\"), PARSE_OPT_NOARG),\n-\t\tOPT_BOOL(0, \"left-only\", &left_only,\n-\t\t\t N_(\"only emit output related to the first range\")),\n \t\tOPT_BOOL(0, \"right-only\", &right_only,\n \t\t\t N_(\"only emit output related to the second range\")),\n \t\tOPT_END()\n-- \ngitgitgadget\n\n"},{"id":"525090","messageId":"c81f920fee0ed8672783728fae70b6435e800f82.1756370289.git.gitgitgadget@gmail.com","threadId":"64039","inReplyTo":"pull.1958.v2.git.1756370289.gitgitgadget@gmail.com","subject":"[PATCH v2 2/2] range-diff: add configurable memory limit for cost matrix","fromName":"pcasaretto via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-08-28T08:38:08Z","receivedAt":"2025-08-28T08:38:17Z","isPatch":true,"sender":{"key":"name:pcasaretto","avatar":null},"body":"From: pcasaretto \n\nWhen comparing large commit ranges (e.g., 250,000+ commits), range-diff\nattempts to allocate an n×n cost matrix that can exhaust available\nmemory. For example, with 256,784 commits (n = 513,568), the matrix\nwould require approximately 256GB of memory (513,568² × 4 bytes),\ncausing either immediate segmentation faults due to integer overflow or\nsystem hangs.\n\nAdd a memory limit check in get_correspondences() before allocating the\ncost matrix. This check uses the total size in bytes (n² × sizeof(int))\nand compares it against a configurable maximum, preventing both\nexcessive memory usage and integer overflow issues.\n\nThe limit is configurable via a new --max-memory option that accepts\nhuman-readable sizes (e.g., \"1G\", \"500M\"). The default is 4GB for 64 bit\nsystems and 2GB for 32 bit systems. This allows comparing ranges of\napproximately 32,000 (16,000) commits - generous for real-world use cases\nwhile preventing impractical operations.\n\nWhen the limit is exceeded, range-diff now displays a clear error\nmessage showing both the requested memory size and the maximum allowed,\nformatted in human-readable units for better user experience.\n\nExample usage:\n git range-diff --max-memory=1G branch1...branch2\n git range-diff --max-memory=500M base..topic1 base..topic2\n\nThis approach was chosen over alternatives:\n- Pre-counting commits: Would require spawning additional git processes\n and reading all commits twice\n- Limiting by commit count: Less precise than actual memory usage\n- Streaming approach: Would require significant refactoring of the\n current algorithm\n\nThis issue was previously discussed in:\nhttps://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n\nAcked-by: Johannes Schindelin \nSigned-off-by: Paulo Casaretto \n---\n builtin/log.c | 1 +\n builtin/range-diff.c | 21 +++++++++++++++++++++\n log-tree.c | 1 +\n range-diff.c | 20 ++++++++++++++++----\n range-diff.h | 5 +++++\n 5 files changed, 44 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex c2f8bbf86301..5f552d14c0fe 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1404,6 +1404,7 @@ static void make_cover_letter(struct rev_info *rev, int use_separate_file,\n \t\tstruct range_diff_options range_diff_opts = {\n \t\t\t.creation_factor = rev->creation_factor,\n \t\t\t.dual_color = 1,\n+\t\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t\t.diffopt = &opts,\n \t\t\t.other_arg = &other_arg\n \t\t};\ndiff --git a/builtin/range-diff.c b/builtin/range-diff.c\nindex 283583a80d0b..79956d83e400 100644\n--- a/builtin/range-diff.c\n+++ b/builtin/range-diff.c\n@@ -6,6 +6,7 @@\n #include \"parse-options.h\"\n #include \"range-diff.h\"\n #include \"config.h\"\n+#include \"parse.h\"\n \n \n static const char * const builtin_range_diff_usage[] = {\n@@ -15,6 +16,21 @@ N_(\"git range-diff [] \"),\n NULL\n };\n \n+static int parse_max_memory(const struct option *opt, const char *arg, int unset)\n+{\n+\tsize_t *max_memory = opt->value;\n+\tuintmax_t val;\n+\n+\tif (unset)\n+\t\treturn 0;\n+\n+\tif (!git_parse_unsigned(arg, &val, SIZE_MAX))\n+\t\treturn error(_(\"invalid max-memory value: %s\"), arg);\n+\n+\t*max_memory = (size_t)val;\n+\treturn 0;\n+}\n+\n int cmd_range_diff(int argc,\n \t\t const char **argv,\n \t\t const char *prefix,\n@@ -25,6 +41,7 @@ int cmd_range_diff(int argc,\n \tstruct strvec diff_merges_arg = STRVEC_INIT;\n \tstruct range_diff_options range_diff_opts = {\n \t\t.creation_factor = RANGE_DIFF_CREATION_FACTOR_DEFAULT,\n+\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t.diffopt = &diffopt,\n \t\t.other_arg = &other_arg\n \t};\n@@ -37,6 +54,10 @@ int cmd_range_diff(int argc,\n \t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n \t\tOPT_BOOL(0, \"left-only\", &left_only,\n \t\t\t N_(\"only emit output related to the first range\")),\n+\t\tOPT_CALLBACK(0, \"max-memory\", &range_diff_opts.max_memory,\n+\t\t\t N_(\"size\"),\n+\t\t\t N_(\"maximum memory for cost matrix (default 4G)\"),\n+\t\t\t parse_max_memory),\n \t\tOPT_BOOL(0, \"no-dual-color\", &simple_color,\n \t\t\t N_(\"use simple diff colors\")),\n \t\tOPT_PASSTHRU_ARGV(0, \"notes\", &other_arg,\ndiff --git a/log-tree.c b/log-tree.c\nindex 233bf9f227c6..73d21f71764e 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -717,6 +717,7 @@ static void show_diff_of_diff(struct rev_info *opt)\n \t\tstruct range_diff_options range_diff_opts = {\n \t\t\t.creation_factor = opt->creation_factor,\n \t\t\t.dual_color = 1,\n+\t\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t\t.diffopt = &opts\n \t\t};\n \ndiff --git a/range-diff.c b/range-diff.c\nindex 8a2dcbee322e..e31f71c73d20 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -325,13 +325,24 @@ static int diffsize(const char *a, const char *b)\n }\n \n static void get_correspondences(struct string_list *a, struct string_list *b,\n-\t\t\t\tint creation_factor)\n+\t\t\t\tint creation_factor, size_t max_memory)\n {\n \tint n = a->nr + b->nr;\n \tint *cost, c, *a2b, *b2a;\n \tint i, j;\n-\n-\tALLOC_ARRAY(cost, st_mult(n, n));\n+\tsize_t cost_size = st_mult(n, n);\n+\tsize_t cost_bytes = st_mult(sizeof(int), cost_size);\n+\tif (cost_bytes >= max_memory) {\n+\t\tstruct strbuf cost_str = STRBUF_INIT;\n+\t\tstruct strbuf max_str = STRBUF_INIT;\n+\t\tstrbuf_humanise_bytes(&cost_str, cost_bytes);\n+\t\tstrbuf_humanise_bytes(&max_str, max_memory);\n+\t\tdie(_(\"range-diff: unable to compute the range-diff, since it \"\n+\t\t \"exceeds the maximum memory for the cost matrix: %s \"\n+\t\t \"(%\"PRIuMAX\" bytes) needed, %s (%\"PRIuMAX\" bytes) available\"),\n+\t\t cost_str.buf, (uintmax_t)cost_bytes, max_str.buf, (uintmax_t)max_memory);\n+\t}\n+\tALLOC_ARRAY(cost, cost_size);\n \tALLOC_ARRAY(a2b, n);\n \tALLOC_ARRAY(b2a, n);\n \n@@ -591,7 +602,8 @@ int show_range_diff(const char *range1, const char *range2,\n \tif (!res) {\n \t\tfind_exact_matches(&branch1, &branch2);\n \t\tget_correspondences(&branch1, &branch2,\n-\t\t\t\t range_diff_opts->creation_factor);\n+\t\t\t\t range_diff_opts->creation_factor,\n+\t\t\t\t range_diff_opts->max_memory);\n \t\toutput(&branch1, &branch2, range_diff_opts);\n \t}\n \ndiff --git a/range-diff.h b/range-diff.h\nindex cd85000b5a0d..9d39818e349c 100644\n--- a/range-diff.h\n+++ b/range-diff.h\n@@ -5,6 +5,10 @@\n #include \"strvec.h\"\n \n #define RANGE_DIFF_CREATION_FACTOR_DEFAULT 60\n+#define RANGE_DIFF_MAX_MEMORY_DEFAULT \\\n+\t(sizeof(void*) >= 8 ? \\\n+\t\t((size_t)(1024L * 1024L) * (size_t)(4L * 1024L)) : /* 4GB on 64-bit */ \\\n+\t\t((size_t)(1024L * 1024L) * (size_t)(2L * 1024L))) /* 2GB on 32-bit */\n \n /*\n * A much higher value than the default, when we KNOW we are comparing\n@@ -17,6 +21,7 @@ struct range_diff_options {\n \tunsigned dual_color:1;\n \tunsigned left_only:1, right_only:1;\n \tunsigned include_merges:1;\n+\tsize_t max_memory;\n \tconst struct diff_options *diffopt; /* may be NULL */\n \tconst struct strvec *other_arg; /* may be NULL */\n };\n-- \ngitgitgadget\n"},{"id":"525115","messageId":"xmqqa53jxyiz.fsf@gitster.g","threadId":"64039","inReplyTo":"ec5dcdf9d00473417b1f0b676a485f01076ce075.1756370289.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 1/2] range-diff: reorder options lexicographically","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-28T15:21:24Z","receivedAt":"2025-08-28T15:21:27Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"pcasaretto via GitGitGadget\" writes:\n\n> From: pcasaretto \n>\n> Reorder the command-line options in builtin/range-diff.c to be in\n> lexicographic order for better organization and readability. This is\n> a preparatory cleanup with no functional changes.\n>\n> Signed-off-by: Paulo Casaretto \n> ---\n> builtin/range-diff.c | 8 ++++----\n> 1 file changed, 4 insertions(+), 4 deletions(-)\n\nThanks for splitting this out into its own commit.\n\nI am not sure if \"lexicographic order\" fits well in the context of\n\"git cmd -h\" that spews out many many options, shown with related\noptions together in groups. I find it aggressively annoying to show\nleft/right-only far apart. A user unfamiliar with the command would\nlook at the list, find \"left-only\" sitting in the list alone, and\nwaste time and break concentration wondering what in the first range\nis so special to deserve such an option, until they see \"right-only\"\nfurther down to realize that they are symmetric.\n\nI'd rather not to see this \"lexicographic\" change done, but others\nmay have better justification (note: \"for better organization and\nreadability\" I just disagreed is a good justification) that may make\nme change my mind.\n\nWhat I would change, if there is something suboptimal in the current\noutput from \"git range-diff -h\" that deserves improvement, is the\nlack of the grouping header before the options for range-diff\noperation (i.e. creation-factor to left/right-only, before the next\n\"diff output\" group begins).\n\nThanks.\n\n> diff --git a/builtin/range-diff.c b/builtin/range-diff.c\n> index a563abff5fee..283583a80d0b 100644\n> --- a/builtin/range-diff.c\n> +++ b/builtin/range-diff.c\n> @@ -33,17 +33,17 @@ int cmd_range_diff(int argc,\n> \t\tOPT_INTEGER(0, \"creation-factor\",\n> \t\t\t &range_diff_opts.creation_factor,\n> \t\t\t N_(\"percentage by which creation is weighted\")),\n> +\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n> +\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n> +\t\tOPT_BOOL(0, \"left-only\", &left_only,\n> +\t\t\t N_(\"only emit output related to the first range\")),\n> \t\tOPT_BOOL(0, \"no-dual-color\", &simple_color,\n> \t\t\t N_(\"use simple diff colors\")),\n> \t\tOPT_PASSTHRU_ARGV(0, \"notes\", &other_arg,\n> \t\t\t\t N_(\"notes\"), N_(\"passed to 'git log'\"),\n> \t\t\t\t PARSE_OPT_OPTARG),\n> -\t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n> -\t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n> \t\tOPT_PASSTHRU_ARGV(0, \"remerge-diff\", &diff_merges_arg, NULL,\n> \t\t\t\t N_(\"passed to 'git log'\"), PARSE_OPT_NOARG),\n> -\t\tOPT_BOOL(0, \"left-only\", &left_only,\n> -\t\t\t N_(\"only emit output related to the first range\")),\n> \t\tOPT_BOOL(0, \"right-only\", &right_only,\n> \t\t\t N_(\"only emit output related to the second range\")),\n> \t\tOPT_END()\n"},{"id":"525123","messageId":"CABPp-BEDje5dYZHEyYMN6j_LdR5CqRN1cxc0riRK06qK-OxiTA@mail.gmail.com","threadId":"64039","inReplyTo":"c81f920fee0ed8672783728fae70b6435e800f82.1756370289.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/2] range-diff: add configurable memory limit for cost matrix","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-08-28T17:04:53Z","receivedAt":"2025-08-28T17:05:05Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Aug 28, 2025 at 2:00 AM pcasaretto via GitGitGadget\n wrote:\n>\n> From: pcasaretto \n> Signed-off-by: Paulo Casaretto \n\nThe names (and emails) in these should match; I believe the name in\nthe From field is set by Gitgitgadget based on your profile settings;\nsee https://github.com/settings/profile and set your name there.\n\n> static void get_correspondences(struct string_list *a, struct string_list *b,\n> - int creation_factor)\n> + int creation_factor, size_t max_memory)\n> {\n> int n = a->nr + b->nr;\n> int *cost, c, *a2b, *b2a;\n> int i, j;\n> -\n> - ALLOC_ARRAY(cost, st_mult(n, n));\n> + size_t cost_size = st_mult(n, n);\n> + size_t cost_bytes = st_mult(sizeof(int), cost_size);\n> + if (cost_bytes >= max_memory) {\n> + struct strbuf cost_str = STRBUF_INIT;\n> + struct strbuf max_str = STRBUF_INIT;\n> + strbuf_humanise_bytes(&cost_str, cost_bytes);\n> + strbuf_humanise_bytes(&max_str, max_memory);\n> + die(_(\"range-diff: unable to compute the range-diff, since it \"\n> + \"exceeds the maximum memory for the cost matrix: %s \"\n> + \"(%\"PRIuMAX\" bytes) needed, %s (%\"PRIuMAX\" bytes) available\"),\n\navailable? I'm worried the error message will report in users\nchecking system memory, claiming they have 14GB available on their\nsystem, and then reporting a \"bug\".\n\nPerhaps something like:\n\n+ \"(%\"PRIuMAX\" bytes) needed, limited to %s\n(%\"PRIuMAX\" bytes)\"),\n\n?\n\n\nThe rest of the patch looks good to me.\n"},{"id":"525126","messageId":"CABPp-BGRHajFf5z91CvvKvahpknbt1KraCR3_rOmAjvxz36_Ag@mail.gmail.com","threadId":"64039","inReplyTo":"xmqqa53jxyiz.fsf@gitster.g","subject":"Re: [PATCH v2 1/2] range-diff: reorder options lexicographically","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-08-28T17:12:35Z","receivedAt":"2025-08-28T17:12:47Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Aug 28, 2025 at 8:24 AM Junio C Hamano wrote:\n>\n> \"pcasaretto via GitGitGadget\" writes:\n>\n> > From: pcasaretto \n> > Signed-off-by: Paulo Casaretto \n\nSame issue with name here.\n\n> I am not sure if \"lexicographic order\" fits well in the context of\n> \"git cmd -h\" that spews out many many options, shown with related\n> options together in groups. I find it aggressively annoying to show\n> left/right-only far apart. A user unfamiliar with the command would\n> look at the list, find \"left-only\" sitting in the list alone, and\n> waste time and break concentration wondering what in the first range\n> is so special to deserve such an option, until they see \"right-only\"\n> further down to realize that they are symmetric.\n>\n> I'd rather not to see this \"lexicographic\" change done, but others\n> may have better justification (note: \"for better organization and\n> readability\" I just disagreed is a good justification) that may make\n> me change my mind.\n>\n> What I would change, if there is something suboptimal in the current\n> output from \"git range-diff -h\" that deserves improvement, is the\n> lack of the grouping header before the options for range-diff\n> operation (i.e. creation-factor to left/right-only, before the next\n> \"diff output\" group begins).\n>\n> Thanks.\n\nI do like lexicographic ordering for unrelated options, but I prefer\noptions to be grouped by intent/use first, then by lexicographic\nordering. And here, not only are--left-only & --right-only related as\nJunio points out, to me --diff-merges and --remerge-diff are a similar\ngrouping that belong together. So, my $0.02 is that I'd lean towards\ncalling both changes in the patch a reduction in organization rather\nthan an improvement.\n"},{"id":"525155","messageId":"xmqqiki7ta3e.fsf@gitster.g","threadId":"64039","inReplyTo":"CABPp-BEDje5dYZHEyYMN6j_LdR5CqRN1cxc0riRK06qK-OxiTA@mail.gmail.com","subject":"Re: [PATCH v2 2/2] range-diff: add configurable memory limit for cost matrix","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-28T21:22:45Z","receivedAt":"2025-08-28T21:22:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> wrote:\n>>\n>> From: pcasaretto \n>> Signed-off-by: Paulo Casaretto \n>\n> The names (and emails) in these should match; I believe the name in\n> the From field is set by Gitgitgadget based on your profile settings;\n> see https://github.com/settings/profile and set your name there.\n>\n>> static void get_correspondences(struct string_list *a, struct string_list *b,\n>> - int creation_factor)\n>> + int creation_factor, size_t max_memory)\n>> {\n>> int n = a->nr + b->nr;\n>> int *cost, c, *a2b, *b2a;\n>> int i, j;\n>> -\n>> - ALLOC_ARRAY(cost, st_mult(n, n));\n>> + size_t cost_size = st_mult(n, n);\n>> + size_t cost_bytes = st_mult(sizeof(int), cost_size);\n>> + if (cost_bytes >= max_memory) {\n>> + struct strbuf cost_str = STRBUF_INIT;\n>> + struct strbuf max_str = STRBUF_INIT;\n>> + strbuf_humanise_bytes(&cost_str, cost_bytes);\n>> + strbuf_humanise_bytes(&max_str, max_memory);\n>> + die(_(\"range-diff: unable to compute the range-diff, since it \"\n>> + \"exceeds the maximum memory for the cost matrix: %s \"\n>> + \"(%\"PRIuMAX\" bytes) needed, %s (%\"PRIuMAX\" bytes) available\"),\n>\n> available? I'm worried the error message will report in users\n> checking system memory, claiming they have 14GB available on their\n> system, and then reporting a \"bug\".\n>\n> Perhaps something like:\n>\n> + \"(%\"PRIuMAX\" bytes) needed, limited to %s\n> (%\"PRIuMAX\" bytes)\"),\n\nSounds like a good idea.\n\nI am not a huge fan of configuration variables that do not have a\ncommand line option. Assuming that it is not like you'd be doing\noverly huge range-diff that would not fit your memory every day,\nshouldn't we start this with a command line option without a\nconfiguration variable to gauge how useful it would be for users\nwith such a need, and then after it proves useful and we identify a\nworkflow where a user would be passing this option all the time, add\na configuration to allow it always be in effect (with command line\noverride still available)?\n\n\n"},{"id":"525158","messageId":"CABPp-BF1z7iS6m4FzM6555j8UQeqfTZuCbwwK=Zh0zQ1+qfMZA@mail.gmail.com","threadId":"64039","inReplyTo":"xmqqiki7ta3e.fsf@gitster.g","subject":"Re: [PATCH v2 2/2] range-diff: add configurable memory limit for cost matrix","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-08-28T21:34:21Z","receivedAt":"2025-08-28T21:34:33Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Thu, Aug 28, 2025 at 2:22 PM Junio C Hamano wrote:\n>\n> I am not a huge fan of configuration variables that do not have a\n> command line option. Assuming that it is not like you'd be doing\n> overly huge range-diff that would not fit your memory every day,\n> shouldn't we start this with a command line option without a\n> configuration variable to gauge how useful it would be for users\n> with such a need, and then after it proves useful and we identify a\n> workflow where a user would be passing this option all the time, add\n> a configuration to allow it always be in effect (with command line\n> override still available)?\n\nIsn't that what Paulo's patch does? Maybe I'm just blind, but I've\nlooked over the patch a couple times and don't see where he's reading\nfrom a configuration variable; am I just missing it?\n"},{"id":"525160","messageId":"xmqqecsvt917.fsf@gitster.g","threadId":"64039","inReplyTo":"CABPp-BF1z7iS6m4FzM6555j8UQeqfTZuCbwwK=Zh0zQ1+qfMZA@mail.gmail.com","subject":"Re: [PATCH v2 2/2] range-diff: add configurable memory limit for cost matrix","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-28T21:45:40Z","receivedAt":"2025-08-28T21:45:42Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elijah Newren writes:\n\n> On Thu, Aug 28, 2025 at 2:22 PM Junio C Hamano wrote:\n>>\n>> I am not a huge fan of configuration variables that do not have a\n>> command line option. Assuming that it is not like you'd be doing\n>> overly huge range-diff that would not fit your memory every day,\n>> shouldn't we start this with a command line option without a\n>> configuration variable to gauge how useful it would be for users\n>> with such a need, and then after it proves useful and we identify a\n>> workflow where a user would be passing this option all the time, add\n>> a configuration to allow it always be in effect (with command line\n>> override still available)?\n>\n> Isn't that what Paulo's patch does? Maybe I'm just blind, but I've\n> looked over the patch a couple times and don't see where he's reading\n> from a configuration variable; am I just missing it?\n\nAh, I just blindly trusted that the \"configurable memory limit\" on\nthe subject line is talking about configuring memory limit with some\nmechanism. Thanks for correcting me.\n\n"},{"id":"525187","messageId":"CABEf2MkN0BNVuiA4Q0SrP=vFb18tSEKcD09qDzs40CowHjO3rg@mail.gmail.com","threadId":"64039","inReplyTo":"CABPp-BGRHajFf5z91CvvKvahpknbt1KraCR3_rOmAjvxz36_Ag@mail.gmail.com","subject":"Re: [PATCH v2 1/2] range-diff: reorder options lexicographically","fromName":"Paulo L F Casaretto","fromEmail":"pcasaretto@gmail.com","sentAt":"2025-08-29T10:56:29Z","receivedAt":"2025-08-29T10:56:43Z","isPatch":true,"sender":{"key":"pcasaretto@gmail.com","avatar":null},"body":"Yes, I concur. I noticed these were \"out of order\" when I added the\nnew flag but now it's obvious that there was order. I'll remove this\ncommit.\nRegarding the name problem, I've checked and I do have \"Paulo\nCasaretto\" set as my name in my Github public profile.\nI fixed my local git config and apparently that fixed it.\n\n\nOn Thu, Aug 28, 2025 at 7:12 PM Elijah Newren wrote:\n>\n> On Thu, Aug 28, 2025 at 8:24 AM Junio C Hamano wrote:\n> >\n> > \"pcasaretto via GitGitGadget\" writes:\n> >\n> > > From: pcasaretto \n> > > Signed-off-by: Paulo Casaretto \n>\n> Same issue with name here.\n>\n> > I am not sure if \"lexicographic order\" fits well in the context of\n> > \"git cmd -h\" that spews out many many options, shown with related\n> > options together in groups. I find it aggressively annoying to show\n> > left/right-only far apart. A user unfamiliar with the command would\n> > look at the list, find \"left-only\" sitting in the list alone, and\n> > waste time and break concentration wondering what in the first range\n> > is so special to deserve such an option, until they see \"right-only\"\n> > further down to realize that they are symmetric.\n> >\n> > I'd rather not to see this \"lexicographic\" change done, but others\n> > may have better justification (note: \"for better organization and\n> > readability\" I just disagreed is a good justification) that may make\n> > me change my mind.\n> >\n> > What I would change, if there is something suboptimal in the current\n> > output from \"git range-diff -h\" that deserves improvement, is the\n> > lack of the grouping header before the options for range-diff\n> > operation (i.e. creation-factor to left/right-only, before the next\n> > \"diff output\" group begins).\n> >\n> > Thanks.\n>\n> I do like lexicographic ordering for unrelated options, but I prefer\n> options to be grouped by intent/use first, then by lexicographic\n> ordering. And here, not only are--left-only & --right-only related as\n> Junio points out, to me --diff-merges and --remerge-diff are a similar\n> grouping that belong together. So, my $0.02 is that I'd lean towards\n> calling both changes in the patch a reduction in organization rather\n> than an improvement.\n\n\n\n-- \nPaulo L F Casaretto\n"},{"id":"525188","messageId":"pull.1958.v3.git.1756465231183.gitgitgadget@gmail.com","threadId":"64039","inReplyTo":"pull.1958.v2.git.1756370289.gitgitgadget@gmail.com","subject":"[PATCH v3] range-diff: add configurable memory limit for cost matrix","fromName":"Paulo Casaretto via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2025-08-29T11:00:31Z","receivedAt":"2025-08-29T11:00:35Z","isPatch":true,"sender":{"key":"name:Paulo Casaretto","avatar":null},"body":"From: Paulo Casaretto \n\nWhen comparing large commit ranges (e.g., 250,000+ commits), range-diff\nattempts to allocate an n×n cost matrix that can exhaust available\nmemory. For example, with 256,784 commits (n = 513,568), the matrix\nwould require approximately 256GB of memory (513,568² × 4 bytes),\ncausing either immediate segmentation faults due to integer overflow or\nsystem hangs.\n\nAdd a memory limit check in get_correspondences() before allocating the\ncost matrix. This check uses the total size in bytes (n² × sizeof(int))\nand compares it against a configurable maximum, preventing both\nexcessive memory usage and integer overflow issues.\n\nThe limit is configurable via a new --max-memory option that accepts\nhuman-readable sizes (e.g., \"1G\", \"500M\"). The default is 4GB for 64 bit\nsystems and 2GB for 32 bit systems. This allows comparing ranges of\napproximately 32,000 (16,000) commits - generous for real-world use cases\nwhile preventing impractical operations.\n\nWhen the limit is exceeded, range-diff now displays a clear error\nmessage showing both the requested memory size and the maximum allowed,\nformatted in human-readable units for better user experience.\n\nExample usage:\n git range-diff --max-memory=1G branch1...branch2\n git range-diff --max-memory=500M base..topic1 base..topic2\n\nThis approach was chosen over alternatives:\n- Pre-counting commits: Would require spawning additional git processes\n and reading all commits twice\n- Limiting by commit count: Less precise than actual memory usage\n- Streaming approach: Would require significant refactoring of the\n current algorithm\n\nThis issue was previously discussed in:\nhttps://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n\nAcked-by: Johannes Schindelin \nSigned-off-by: Paulo Casaretto \n---\n range-diff: add configurable memory limit for cost matrix\n \n \n Problem Description\n ===================\n \n When git range-diff is given extremely large ranges, it can result in\n either:\n \n 1. Segmentation fault due to integer overflow in array index\n calculations\n 2. Excessive memory consumption leading to system hangs or OOM kills\n 3. Poor user experience with the command appearing to hang for minutes\n \n \n Reproduction Case\n =================\n \n In a Shopify's large monorepo a range-diff command like this crashes\n after several minutes with a SIGBUS error\n \n $ git range-diff 4430f36511..316c1276c6 cb5240b6a8..2bbd292091\n \n \n Range statistics:\n \n * First range: 256,783 commits\n * Second range: 1 commit\n * Total: 256,784 commits\n * Memory required for cost matrix: n² × 4 bytes = ~260GB\n \n \n Stack Trace (Segmentation Fault)\n ================================\n \n (lldb) bt\n * thread #1, queue = 'com.apple.main-thread', stop reason = EXC_BAD_ACCESS (code=2, address=0x6e000ae3b8)\n * frame #0: 0x000000010029a284 git`get_correspondences(a=0x000000016fde6188, b=0x000000016fde6160, creation_factor=60) at range-diff.c:356:20\n frame #1: 0x0000000100299310 git`show_range_diff(range1=\"4430f36511cbacf5c517c6851e2b8508a72dfd30..316c1276c63f55ad9413fa18bf3b6483564a9cf4\", range2=\"cb5240b6a8ba59b4a1f282559ee0742721b0cafc..2bbd292091e376d177ce62e264dae8872ca6be5a\", range_diff_opts=0x000000016fde6308) at range-diff.c:593:3\n frame #2: 0x00000001000c719c git`cmd_range_diff(argc=2, argv=0x0000600000bcd8c0, prefix=\"areas/core/shopify/\", repo=0x0000000100468b20) at range-diff.c:167:8\n frame #3: 0x000000010000277c git`run_builtin(p=0x00000001004408d8, argc=3, argv=0x0000600000bcd8c0, repo=0x0000000100468b20) at git.c:480:11\n frame #4: 0x0000000100001020 git`handle_builtin(args=0x000000016fde6c70) at git.c:746:9\n frame #5: 0x0000000100002074 git`run_argv(args=0x000000016fde6c70) at git.c:813:4\n frame #6: 0x0000000100000d3c git`cmd_main(argc=3, argv=0x000000016fde7350) at git.c:953:19\n frame #7: 0x000000010012750c git`main(argc=4, argv=0x000000016fde7348) at common-main.c:9:11\n frame #8: 0x000000018573ab98 dyld`start + 6076\n \n \n \n Root Cause Analysis\n ===================\n \n The crash occurs in get_correspondences() at line 356:\n \n static void get_correspondences(struct string_list *a, struct string_list *b, ...)\n {\n int n = a->nr + b->nr; // Integer overflow: 256,784 fits in int\n ...\n ALLOC_ARRAY(cost, st_mult(n, n)); // Would allocate ~260GB\n ...\n cost[i + n * j] = c; // Line 356: Invalid memory access\n }\n \n \n Problems:\n \n 1. Integer overflow: While n=256,784 fits in an int, n*n overflows\n 2. Memory allocation: Even with proper types, allocating 260GB is\n impractical\n \n \n Solution\n ========\n \n Add a memory limit check in get_correspondences() before allocating the\n cost matrix. This check uses the total size in bytes (n² × sizeof(int))\n and compares it against a configurable maximum, preventing both\n excessive memory usage and integer overflow issues.\n \n The limit is configurable via a new --max-memory option that accepts\n human-readable sizes (e.g., \"1G\", \"500M\"). The default is 4GB for 64 bit\n systems and 2GB for 32 bit systems. This allows comparing ranges of\n approximately 32,000 (16,000) commits - generous for real-world use\n cases while preventing impractical operations.\n \n When the limit is exceeded, range-diff now displays a clear error\n message showing both the requested memory size and the maximum allowed,\n formatted in human-readable units for better user experience.\n \n Example usage: git range-diff --max-memory=1G branch1...branch2 git\n range-diff --max-memory=500M base..topic1 base..topic2\n \n This approach was chosen over alternatives:\n \n * Pre-counting commits: Would require spawning additional git processes\n and reading all commits twice\n * Limiting by commit count: Less precise than actual memory usage\n * Streaming approach: Would require significant refactoring of the\n current algorithm\n \n This issue was previously discussed in:\n https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n \n Acked-by: Johannes Schindelin johannes.schindelin@gmx.de\n [https://github.com/gitgitgadget/git/pull/1958#issuecomment-3224133138]\n\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1958%2Fpcasaretto%2Frange-diff-size-limit-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1958/pcasaretto/range-diff-size-limit-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/1958\n\nRange-diff vs v2:\n\n 1: ec5dcdf9d0 < -: ---------- range-diff: reorder options lexicographically\n 2: c81f920fee ! 1: 6d7ff43e56 range-diff: add configurable memory limit for cost matrix\n @@\n ## Metadata ##\n -Author: pcasaretto \n +Author: Paulo Casaretto \n \n ## Commit message ##\n range-diff: add configurable memory limit for cost matrix\n @@ Commit message\n https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n \n Acked-by: Johannes Schindelin \n - Signed-off-by: Paulo Casaretto \n + Signed-off-by: Paulo Casaretto \n \n ## builtin/log.c ##\n @@ builtin/log.c: static void make_cover_letter(struct rev_info *rev, int use_separate_file,\n @@ builtin/range-diff.c: int cmd_range_diff(int argc,\n \t\t.other_arg = &other_arg\n \t};\n @@ builtin/range-diff.c: int cmd_range_diff(int argc,\n + \t\t\t\t PARSE_OPT_OPTARG),\n + \t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n \t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n - \t\tOPT_BOOL(0, \"left-only\", &left_only,\n - \t\t\t N_(\"only emit output related to the first range\")),\n +\t\tOPT_CALLBACK(0, \"max-memory\", &range_diff_opts.max_memory,\n +\t\t\t N_(\"size\"),\n +\t\t\t N_(\"maximum memory for cost matrix (default 4G)\"),\n +\t\t\t parse_max_memory),\n - \t\tOPT_BOOL(0, \"no-dual-color\", &simple_color,\n - \t\t\t N_(\"use simple diff colors\")),\n - \t\tOPT_PASSTHRU_ARGV(0, \"notes\", &other_arg,\n + \t\tOPT_PASSTHRU_ARGV(0, \"remerge-diff\", &diff_merges_arg, NULL,\n + \t\t\t\t N_(\"passed to 'git log'\"), PARSE_OPT_NOARG),\n + \t\tOPT_BOOL(0, \"left-only\", &left_only,\n \n ## log-tree.c ##\n @@ log-tree.c: static void show_diff_of_diff(struct rev_info *opt)\n\n\n builtin/log.c | 1 +\n builtin/range-diff.c | 21 +++++++++++++++++++++\n log-tree.c | 1 +\n range-diff.c | 20 ++++++++++++++++----\n range-diff.h | 5 +++++\n 5 files changed, 44 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/log.c b/builtin/log.c\nindex c2f8bbf863..5f552d14c0 100644\n--- a/builtin/log.c\n+++ b/builtin/log.c\n@@ -1404,6 +1404,7 @@ static void make_cover_letter(struct rev_info *rev, int use_separate_file,\n \t\tstruct range_diff_options range_diff_opts = {\n \t\t\t.creation_factor = rev->creation_factor,\n \t\t\t.dual_color = 1,\n+\t\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t\t.diffopt = &opts,\n \t\t\t.other_arg = &other_arg\n \t\t};\ndiff --git a/builtin/range-diff.c b/builtin/range-diff.c\nindex a563abff5f..aafcc99b96 100644\n--- a/builtin/range-diff.c\n+++ b/builtin/range-diff.c\n@@ -6,6 +6,7 @@\n #include \"parse-options.h\"\n #include \"range-diff.h\"\n #include \"config.h\"\n+#include \"parse.h\"\n \n \n static const char * const builtin_range_diff_usage[] = {\n@@ -15,6 +16,21 @@ N_(\"git range-diff [] \"),\n NULL\n };\n \n+static int parse_max_memory(const struct option *opt, const char *arg, int unset)\n+{\n+\tsize_t *max_memory = opt->value;\n+\tuintmax_t val;\n+\n+\tif (unset)\n+\t\treturn 0;\n+\n+\tif (!git_parse_unsigned(arg, &val, SIZE_MAX))\n+\t\treturn error(_(\"invalid max-memory value: %s\"), arg);\n+\n+\t*max_memory = (size_t)val;\n+\treturn 0;\n+}\n+\n int cmd_range_diff(int argc,\n \t\t const char **argv,\n \t\t const char *prefix,\n@@ -25,6 +41,7 @@ int cmd_range_diff(int argc,\n \tstruct strvec diff_merges_arg = STRVEC_INIT;\n \tstruct range_diff_options range_diff_opts = {\n \t\t.creation_factor = RANGE_DIFF_CREATION_FACTOR_DEFAULT,\n+\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t.diffopt = &diffopt,\n \t\t.other_arg = &other_arg\n \t};\n@@ -40,6 +57,10 @@ int cmd_range_diff(int argc,\n \t\t\t\t PARSE_OPT_OPTARG),\n \t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n \t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n+\t\tOPT_CALLBACK(0, \"max-memory\", &range_diff_opts.max_memory,\n+\t\t\t N_(\"size\"),\n+\t\t\t N_(\"maximum memory for cost matrix (default 4G)\"),\n+\t\t\t parse_max_memory),\n \t\tOPT_PASSTHRU_ARGV(0, \"remerge-diff\", &diff_merges_arg, NULL,\n \t\t\t\t N_(\"passed to 'git log'\"), PARSE_OPT_NOARG),\n \t\tOPT_BOOL(0, \"left-only\", &left_only,\ndiff --git a/log-tree.c b/log-tree.c\nindex 233bf9f227..73d21f7176 100644\n--- a/log-tree.c\n+++ b/log-tree.c\n@@ -717,6 +717,7 @@ static void show_diff_of_diff(struct rev_info *opt)\n \t\tstruct range_diff_options range_diff_opts = {\n \t\t\t.creation_factor = opt->creation_factor,\n \t\t\t.dual_color = 1,\n+\t\t\t.max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,\n \t\t\t.diffopt = &opts\n \t\t};\n \ndiff --git a/range-diff.c b/range-diff.c\nindex 8a2dcbee32..e31f71c73d 100644\n--- a/range-diff.c\n+++ b/range-diff.c\n@@ -325,13 +325,24 @@ static int diffsize(const char *a, const char *b)\n }\n \n static void get_correspondences(struct string_list *a, struct string_list *b,\n-\t\t\t\tint creation_factor)\n+\t\t\t\tint creation_factor, size_t max_memory)\n {\n \tint n = a->nr + b->nr;\n \tint *cost, c, *a2b, *b2a;\n \tint i, j;\n-\n-\tALLOC_ARRAY(cost, st_mult(n, n));\n+\tsize_t cost_size = st_mult(n, n);\n+\tsize_t cost_bytes = st_mult(sizeof(int), cost_size);\n+\tif (cost_bytes >= max_memory) {\n+\t\tstruct strbuf cost_str = STRBUF_INIT;\n+\t\tstruct strbuf max_str = STRBUF_INIT;\n+\t\tstrbuf_humanise_bytes(&cost_str, cost_bytes);\n+\t\tstrbuf_humanise_bytes(&max_str, max_memory);\n+\t\tdie(_(\"range-diff: unable to compute the range-diff, since it \"\n+\t\t \"exceeds the maximum memory for the cost matrix: %s \"\n+\t\t \"(%\"PRIuMAX\" bytes) needed, %s (%\"PRIuMAX\" bytes) available\"),\n+\t\t cost_str.buf, (uintmax_t)cost_bytes, max_str.buf, (uintmax_t)max_memory);\n+\t}\n+\tALLOC_ARRAY(cost, cost_size);\n \tALLOC_ARRAY(a2b, n);\n \tALLOC_ARRAY(b2a, n);\n \n@@ -591,7 +602,8 @@ int show_range_diff(const char *range1, const char *range2,\n \tif (!res) {\n \t\tfind_exact_matches(&branch1, &branch2);\n \t\tget_correspondences(&branch1, &branch2,\n-\t\t\t\t range_diff_opts->creation_factor);\n+\t\t\t\t range_diff_opts->creation_factor,\n+\t\t\t\t range_diff_opts->max_memory);\n \t\toutput(&branch1, &branch2, range_diff_opts);\n \t}\n \ndiff --git a/range-diff.h b/range-diff.h\nindex cd85000b5a..9d39818e34 100644\n--- a/range-diff.h\n+++ b/range-diff.h\n@@ -5,6 +5,10 @@\n #include \"strvec.h\"\n \n #define RANGE_DIFF_CREATION_FACTOR_DEFAULT 60\n+#define RANGE_DIFF_MAX_MEMORY_DEFAULT \\\n+\t(sizeof(void*) >= 8 ? \\\n+\t\t((size_t)(1024L * 1024L) * (size_t)(4L * 1024L)) : /* 4GB on 64-bit */ \\\n+\t\t((size_t)(1024L * 1024L) * (size_t)(2L * 1024L))) /* 2GB on 32-bit */\n \n /*\n * A much higher value than the default, when we KNOW we are comparing\n@@ -17,6 +21,7 @@ struct range_diff_options {\n \tunsigned dual_color:1;\n \tunsigned left_only:1, right_only:1;\n \tunsigned include_merges:1;\n+\tsize_t max_memory;\n \tconst struct diff_options *diffopt; /* may be NULL */\n \tconst struct strvec *other_arg; /* may be NULL */\n };\n\nbase-commit: 954d33a9757fcfab723a824116902f1eb16e05f7\n-- \ngitgitgadget\n"},{"id":"525207","messageId":"xmqqsehap3a9.fsf@gitster.g","threadId":"64039","inReplyTo":"CABEf2MkN0BNVuiA4Q0SrP=vFb18tSEKcD09qDzs40CowHjO3rg@mail.gmail.com","subject":"Re: [PATCH v2 1/2] range-diff: reorder options lexicographically","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-29T15:15:42Z","receivedAt":"2025-08-29T15:15:44Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Paulo L F Casaretto writes:\n\n> Yes, I concur. I noticed these were \"out of order\" when I added the\n> new flag but now it's obvious that there was order. I'll remove this\n> commit.\n> Regarding the name problem, I've checked and I do have \"Paulo\n> Casaretto\" set as my name in my Github public profile.\n> I fixed my local git config and apparently that fixed it.\n\nYeah, these in-body From: lines GigGitGadget adds come from the\nauthorship of the commits you are sending (in other words, what you\nsee in \"git cat-file commit \" for these commits), and your\nGitHub profile would not affect it (and you do not want your GitHub\nprofile name be used---otherwise you cannot send a series that\ncontains a change written by somebody else without overtaking the\nauthorship of their commits).\n\nI see v3 posted there; thanks.\n"},{"id":"525208","messageId":"CABPp-BHnCHiTFNKCrnpKF5STkeGNQWMxdVMZ_v-Rp2judZVEgw@mail.gmail.com","threadId":"64039","inReplyTo":"pull.1958.v3.git.1756465231183.gitgitgadget@gmail.com","subject":"Re: [PATCH v3] range-diff: add configurable memory limit for cost matrix","fromName":"Elijah Newren","fromEmail":"newren@gmail.com","sentAt":"2025-08-29T15:21:24Z","receivedAt":"2025-08-29T15:21:36Z","isPatch":true,"sender":{"key":"newren@gmail.com","avatar":"https://avatars.githubusercontent.com/u/5455730?v=4"},"body":"On Fri, Aug 29, 2025 at 4:00 AM Paulo Casaretto via GitGitGadget\n wrote:\n> -\n> - ALLOC_ARRAY(cost, st_mult(n, n));\n> + size_t cost_size = st_mult(n, n);\n> + size_t cost_bytes = st_mult(sizeof(int), cost_size);\n> + if (cost_bytes >= max_memory) {\n> + struct strbuf cost_str = STRBUF_INIT;\n> + struct strbuf max_str = STRBUF_INIT;\n> + strbuf_humanise_bytes(&cost_str, cost_bytes);\n> + strbuf_humanise_bytes(&max_str, max_memory);\n> + die(_(\"range-diff: unable to compute the range-diff, since it \"\n> + \"exceeds the maximum memory for the cost matrix: %s \"\n> + \"(%\"PRIuMAX\" bytes) needed, %s (%\"PRIuMAX\" bytes) available\"),\n> + cost_str.buf, (uintmax_t)cost_bytes, max_str.buf, (uintmax_t)max_memory);\n> + }\n> + ALLOC_ARRAY(cost, cost_size);\n> ALLOC_ARRAY(a2b, n);\n> ALLOC_ARRAY(b2a, n);\n>\n\nThis still has the same wording issue that I commented on in v2:\nhttps://lore.kernel.org/git/CABPp-BEDje5dYZHEyYMN6j_LdR5CqRN1cxc0riRK06qK-OxiTA@mail.gmail.com/\n"},{"id":"525214","messageId":"xmqqecsup25j.fsf@gitster.g","threadId":"64039","inReplyTo":"pull.1958.v3.git.1756465231183.gitgitgadget@gmail.com","subject":"Re: [PATCH v3] range-diff: add configurable memory limit for cost matrix","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2025-08-29T15:40:08Z","receivedAt":"2025-08-29T15:40:11Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Paulo Casaretto via GitGitGadget\" writes:\n\n> From: Paulo Casaretto \n>\n> When comparing large commit ranges (e.g., 250,000+ commits), range-diff\n> attempts to allocate an n×n cost matrix that can exhaust available\n> memory. For example, with 256,784 commits (n = 513,568), the matrix\n> would require approximately 256GB of memory (513,568² × 4 bytes),\n> causing either immediate segmentation faults due to integer overflow or\n> system hangs.\n>\n> Add a memory limit check in get_correspondences() before allocating the\n> cost matrix. This check uses the total size in bytes (n² × sizeof(int))\n> and compares it against a configurable maximum, preventing both\n> excessive memory usage and integer overflow issues.\n>\n> The limit is configurable via a new --max-memory option that accepts\n> human-readable sizes (e.g., \"1G\", \"500M\"). The default is 4GB for 64 bit\n> systems and 2GB for 32 bit systems. This allows comparing ranges of\n> approximately 32,000 (16,000) commits - generous for real-world use cases\n> while preventing impractical operations.\n>\n> When the limit is exceeded, range-diff now displays a clear error\n> message showing both the requested memory size and the maximum allowed,\n> formatted in human-readable units for better user experience.\n>\n> Example usage:\n> git range-diff --max-memory=1G branch1...branch2\n> git range-diff --max-memory=500M base..topic1 base..topic2\n>\n> This approach was chosen over alternatives:\n> - Pre-counting commits: Would require spawning additional git processes\n> and reading all commits twice\n> - Limiting by commit count: Less precise than actual memory usage\n> - Streaming approach: Would require significant refactoring of the\n> current algorithm\n>\n> This issue was previously discussed in:\n> https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/\n>\n> Acked-by: Johannes Schindelin \n> Signed-off-by: Paulo Casaretto \n> ---\n\nLooks good, especially without the reordering existing entries in\nthe options list. The authorship information above looks much\nbetter, too.\n\n> @@ -40,6 +57,10 @@ int cmd_range_diff(int argc,\n> \t\t\t\t PARSE_OPT_OPTARG),\n> \t\tOPT_PASSTHRU_ARGV(0, \"diff-merges\", &diff_merges_arg,\n> \t\t\t\t N_(\"style\"), N_(\"passed to 'git log'\"), 0),\n> +\t\tOPT_CALLBACK(0, \"max-memory\", &range_diff_opts.max_memory,\n> +\t\t\t N_(\"size\"),\n> +\t\t\t N_(\"maximum memory for cost matrix (default 4G)\"),\n> +\t\t\t parse_max_memory),\n> \t\tOPT_PASSTHRU_ARGV(0, \"remerge-diff\", &diff_merges_arg, NULL,\n> \t\t\t\t N_(\"passed to 'git log'\"), PARSE_OPT_NOARG),\n> \t\tOPT_BOOL(0, \"left-only\", &left_only,\n\nAmong existing options (an excerpt from \"git range-diff h\")\n\n --[no-]creation-factor \n percentage by which creation is weighted\n\n This controls how correspondence between commits on old and new\n branches are computed.\n\n --no-dual-color use simple diff colors\n --dual-color opposite of --no-dual-color\n\n These control how the findings are shown, by painting the lines\n in distinct colors. \n\n --[no-]notes[=]\n passed to 'git log'\n --[no-]diff-merges