From: "pcasaretto via GitGitGadget" <gitgitgadget@gmail•com>
To: git@vger•kernel.org
Cc: Paulo Casaretto <pcasaretto@gmail•com>,
pcasaretto <paulo.casaretto@shopify•com>
Subject: [PATCH v2 2/2] range-diff: add configurable memory limit for cost matrix
Date: Thu, 28 Aug 2025 08:38:08 +0000 [thread overview]
Message-ID: <c81f920fee0ed8672783728fae70b6435e800f82.1756370289.git.gitgitgadget@gmail.com> (raw)
In-Reply-To: <pull.1958.v2.git.1756370289.gitgitgadget@gmail.com>
From: pcasaretto <paulo.casaretto@shopify•com>
When comparing large commit ranges (e.g., 250,000+ commits), range-diff
attempts to allocate an n×n cost matrix that can exhaust available
memory. For example, with 256,784 commits (n = 513,568), the matrix
would require approximately 256GB of memory (513,568² × 4 bytes),
causing either immediate segmentation faults due to integer overflow or
system hangs.
Add a memory limit check in get_correspondences() before allocating the
cost matrix. This check uses the total size in bytes (n² × sizeof(int))
and compares it against a configurable maximum, preventing both
excessive memory usage and integer overflow issues.
The limit is configurable via a new --max-memory option that accepts
human-readable sizes (e.g., "1G", "500M"). The default is 4GB for 64 bit
systems and 2GB for 32 bit systems. This allows comparing ranges of
approximately 32,000 (16,000) commits - generous for real-world use cases
while preventing impractical operations.
When the limit is exceeded, range-diff now displays a clear error
message showing both the requested memory size and the maximum allowed,
formatted in human-readable units for better user experience.
Example usage:
git range-diff --max-memory=1G branch1...branch2
git range-diff --max-memory=500M base..topic1 base..topic2
This approach was chosen over alternatives:
- Pre-counting commits: Would require spawning additional git processes
and reading all commits twice
- Limiting by commit count: Less precise than actual memory usage
- Streaming approach: Would require significant refactoring of the
current algorithm
This issue was previously discussed in:
https://lore.kernel.org/git/RFC-cover-v2-0.5-00000000000-20211210T122901Z-avarab@gmail.com/
Acked-by: Johannes Schindelin <johannes.schindelin@gmx•de>
Signed-off-by: Paulo Casaretto <paulo.casaretto@shopify•com>
---
builtin/log.c | 1 +
builtin/range-diff.c | 21 +++++++++++++++++++++
log-tree.c | 1 +
range-diff.c | 20 ++++++++++++++++----
range-diff.h | 5 +++++
5 files changed, 44 insertions(+), 4 deletions(-)
diff --git a/builtin/log.c b/builtin/log.c
index c2f8bbf86301..5f552d14c0fe 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -1404,6 +1404,7 @@ static void make_cover_letter(struct rev_info *rev, int use_separate_file,
struct range_diff_options range_diff_opts = {
.creation_factor = rev->creation_factor,
.dual_color = 1,
+ .max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,
.diffopt = &opts,
.other_arg = &other_arg
};
diff --git a/builtin/range-diff.c b/builtin/range-diff.c
index 283583a80d0b..79956d83e400 100644
--- a/builtin/range-diff.c
+++ b/builtin/range-diff.c
@@ -6,6 +6,7 @@
#include "parse-options.h"
#include "range-diff.h"
#include "config.h"
+#include "parse.h"
static const char * const builtin_range_diff_usage[] = {
@@ -15,6 +16,21 @@ N_("git range-diff [<options>] <base> <old-tip> <new-tip>"),
NULL
};
+static int parse_max_memory(const struct option *opt, const char *arg, int unset)
+{
+ size_t *max_memory = opt->value;
+ uintmax_t val;
+
+ if (unset)
+ return 0;
+
+ if (!git_parse_unsigned(arg, &val, SIZE_MAX))
+ return error(_("invalid max-memory value: %s"), arg);
+
+ *max_memory = (size_t)val;
+ return 0;
+}
+
int cmd_range_diff(int argc,
const char **argv,
const char *prefix,
@@ -25,6 +41,7 @@ int cmd_range_diff(int argc,
struct strvec diff_merges_arg = STRVEC_INIT;
struct range_diff_options range_diff_opts = {
.creation_factor = RANGE_DIFF_CREATION_FACTOR_DEFAULT,
+ .max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,
.diffopt = &diffopt,
.other_arg = &other_arg
};
@@ -37,6 +54,10 @@ int cmd_range_diff(int argc,
N_("style"), N_("passed to 'git log'"), 0),
OPT_BOOL(0, "left-only", &left_only,
N_("only emit output related to the first range")),
+ OPT_CALLBACK(0, "max-memory", &range_diff_opts.max_memory,
+ N_("size"),
+ N_("maximum memory for cost matrix (default 4G)"),
+ parse_max_memory),
OPT_BOOL(0, "no-dual-color", &simple_color,
N_("use simple diff colors")),
OPT_PASSTHRU_ARGV(0, "notes", &other_arg,
diff --git a/log-tree.c b/log-tree.c
index 233bf9f227c6..73d21f71764e 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -717,6 +717,7 @@ static void show_diff_of_diff(struct rev_info *opt)
struct range_diff_options range_diff_opts = {
.creation_factor = opt->creation_factor,
.dual_color = 1,
+ .max_memory = RANGE_DIFF_MAX_MEMORY_DEFAULT,
.diffopt = &opts
};
diff --git a/range-diff.c b/range-diff.c
index 8a2dcbee322e..e31f71c73d20 100644
--- a/range-diff.c
+++ b/range-diff.c
@@ -325,13 +325,24 @@ static int diffsize(const char *a, const char *b)
}
static void get_correspondences(struct string_list *a, struct string_list *b,
- int creation_factor)
+ int creation_factor, size_t max_memory)
{
int n = a->nr + b->nr;
int *cost, c, *a2b, *b2a;
int i, j;
-
- ALLOC_ARRAY(cost, st_mult(n, n));
+ size_t cost_size = st_mult(n, n);
+ size_t cost_bytes = st_mult(sizeof(int), cost_size);
+ if (cost_bytes >= max_memory) {
+ struct strbuf cost_str = STRBUF_INIT;
+ struct strbuf max_str = STRBUF_INIT;
+ strbuf_humanise_bytes(&cost_str, cost_bytes);
+ strbuf_humanise_bytes(&max_str, max_memory);
+ die(_("range-diff: unable to compute the range-diff, since it "
+ "exceeds the maximum memory for the cost matrix: %s "
+ "(%"PRIuMAX" bytes) needed, %s (%"PRIuMAX" bytes) available"),
+ cost_str.buf, (uintmax_t)cost_bytes, max_str.buf, (uintmax_t)max_memory);
+ }
+ ALLOC_ARRAY(cost, cost_size);
ALLOC_ARRAY(a2b, n);
ALLOC_ARRAY(b2a, n);
@@ -591,7 +602,8 @@ int show_range_diff(const char *range1, const char *range2,
if (!res) {
find_exact_matches(&branch1, &branch2);
get_correspondences(&branch1, &branch2,
- range_diff_opts->creation_factor);
+ range_diff_opts->creation_factor,
+ range_diff_opts->max_memory);
output(&branch1, &branch2, range_diff_opts);
}
diff --git a/range-diff.h b/range-diff.h
index cd85000b5a0d..9d39818e349c 100644
--- a/range-diff.h
+++ b/range-diff.h
@@ -5,6 +5,10 @@
#include "strvec.h"
#define RANGE_DIFF_CREATION_FACTOR_DEFAULT 60
+#define RANGE_DIFF_MAX_MEMORY_DEFAULT \
+ (sizeof(void*) >= 8 ? \
+ ((size_t)(1024L * 1024L) * (size_t)(4L * 1024L)) : /* 4GB on 64-bit */ \
+ ((size_t)(1024L * 1024L) * (size_t)(2L * 1024L))) /* 2GB on 32-bit */
/*
* A much higher value than the default, when we KNOW we are comparing
@@ -17,6 +21,7 @@ struct range_diff_options {
unsigned dual_color:1;
unsigned left_only:1, right_only:1;
unsigned include_merges:1;
+ size_t max_memory;
const struct diff_options *diffopt; /* may be NULL */
const struct strvec *other_arg; /* may be NULL */
};
--
gitgitgadget
next prev parent reply other threads:[~2025-08-28 8:38 UTC|newest]
Thread overview: 18+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-08-26 17:18 [PATCH] range-diff: add configurable memory limit for cost matrix Paulo Casaretto via GitGitGadget
2025-08-26 19:18 ` Junio C Hamano
2025-08-28 8:38 ` [PATCH v2 0/2] " Paulo Casaretto via GitGitGadget
2025-08-28 8:38 ` [PATCH v2 1/2] range-diff: reorder options lexicographically pcasaretto via GitGitGadget
2025-08-28 15:21 ` Junio C Hamano
2025-08-28 17:12 ` Elijah Newren
2025-08-29 10:56 ` Paulo L F Casaretto
2025-08-29 15:15 ` Junio C Hamano
2025-08-28 8:38 ` pcasaretto via GitGitGadget [this message]
2025-08-28 17:04 ` [PATCH v2 2/2] range-diff: add configurable memory limit for cost matrix Elijah Newren
2025-08-28 21:22 ` Junio C Hamano
2025-08-28 21:34 ` Elijah Newren
2025-08-28 21:45 ` Junio C Hamano
2025-08-29 11:00 ` [PATCH v3] " Paulo Casaretto via GitGitGadget
2025-08-29 15:21 ` Elijah Newren
2025-08-29 16:33 ` Junio C Hamano
2025-08-29 15:40 ` Junio C Hamano
2025-08-29 16:02 ` [PATCH v4] " Paulo Casaretto via GitGitGadget
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=c81f920fee0ed8672783728fae70b6435e800f82.1756370289.git.gitgitgadget@gmail.com \
--to=gitgitgadget@gmail$(echo .)com \
--cc=git@vger$(echo .)kernel.org \
--cc=paulo.casaretto@shopify$(echo .)com \
--cc=pcasaretto@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox