You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@arrow.apache.org by "lriggs (via GitHub)" <gi...@apache.org> on 2026/06/16 01:32:52 UTC
[PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
lriggs opened a new pull request, #50187:
URL: https://github.com/apache/arrow/pull/50187
### Rationale for this change
Gandiva's REPLACE hardcodes a 65535-byte output buffer, throwing Buffer overflow for output string whenever the result exceeds 64 KB. The cap is arbitrary: Gandiva's variable-length output column already grows dynamically and is only bounded by the int32 offset width (~2 GB). Real queries that replace into large concatenated/aggregated strings fail unnecessarily.
### What changes are included in this PR
replace_utf8_utf8_utf8 now sizes the output buffer to the exact result instead of using a fixed cap. The output length of a replace is deterministic:
out_len = text_len + num_matches * (to_str_len - from_str_len)
The wrapper does a single counting pass over the input to find the number of non-overlapping matches of from_str (mirroring the match loop already used in the implementation), computes the exact size in gdv_int64 to avoid intermediate overflow, and passes that as max_length.
The internal replace_with_max_len_utf8_utf8_utf8 is unchanged — its bounds checks now act purely as a correctness backstop (they should never fire with an exact bound), and its explicit-max-length signature remains for the existing unit tests.
When to is shorter than from, the result shrinks and max_length <= text_len, so the shrinking path is sized correctly too.
### Are these changes tested?
Yes. Added regression cases to TestStringOps.TestReplace in string_ops_test.cc:
A 35000-char 'X' input with X → XY, producing a 70000-byte result (previously overflowed at 65535) — asserts no error and exact length/content.
A 70000-char shrinking case (XX → X) to cover the shrink path on a >64 KB input.
Full precompiled suite passes locally (132/132), including the existing explicit-max_len overflow tests, which call the internal function directly and are unaffected.
### Are there any user-facing changes?
REPLACE now succeeds on results larger than 64 KB instead of erroring. No API or signature changes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3454682996
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1946,9 +1914,33 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Count non-overlapping matches to size the output buffer exactly, so large
+ // results are not capped by an arbitrary limit.
+ gdv_int64 num_matches = 0;
Review Comment:
I just pushed a new approach that does a hybrid. preallocates when possible and the counts when necessary.
<p style="white-space: pre-wrap; margin-top: 0.1em; margin-bottom: 0.2em; color: rgb(97, 97, 97); font-family: -apple-system, "system-ui", "Segoe UI", Roboto, sans-serif; font-size: 13px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;"><strong>Perf.</strong> Sizing the buffer needs the output length up front (the arena allocator is bump-pointer; it can't grow in place). The straightforward approach — count matches in a pre-pass — adds an O(n) scan. Microbenchmarks (<code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px; word-break: break-word; font-size: 0.9em;">-O2</code>) s
howed that scan costing <strong>~27% on dense matches and up to ~95% on sparse</strong> matches (it's a genuine second pass, not a debug artifact).</p><p style="white-space: pre-wrap; margin-top: 0.1em; margin-bottom: 0.2em; color: rgb(97, 97, 97); font-family: -apple-system, "system-ui", "Segoe UI", Roboto, sans-serif; font-size: 13px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">To avoid it, output sizing now branches:</p><ul style="padding-inline-start: 2em; color: rgb(97, 97, 97); font-family: -apple-system, "system-ui", "Segoe UI", Roboto, sans-serif; font-size: 13px; font-style: normal; font-variant-ligatures: normal; font-variant-ca
ps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; white-space: normal; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;"><li><strong>shrink / no-match</strong><span> </span>(<code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px; word-break: break-word; font-size: 0.9em;">to_len ≤ from_len</code>): bound by<span> </span><code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px; word-break: break-word; font-size: 0.9em;">text_len</code>, no scan.</li><li><strong>small expansion</strong><span> </span>(<code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px;
word-break: break-word; font-size: 0.9em;">to_len − from_len ≤ from_len</code>, i.e. result ≤ ~2× input — the common case incl. the original<span> </span><code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px; word-break: break-word; font-size: 0.9em;">'X'→'XY'</code>): allocate an<span> </span><strong>O(1) upper bound</strong><span> </span><code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px; word-break: break-word; font-size: 0.9em;">text_len + (text_len/from_len)·(to_len−from_len)</code><span> </span>and do a single pass,<span> </span><strong>no scan</strong>. Over-allocates at most ~<code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px; word-break: break-word; font-size: 0.9em;">text_len</code><span> </span>of tran
sient arena scratch.</li><li><strong>large expansion</strong>: fall back to the exact match-counting scan, since an upper bound would over-allocate unboundedly for sparse input (and is gated on<span> </span><code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px; word-break: break-word; font-size: 0.9em;">≤ INT_MAX</code>).</li></ul><p style="white-space: pre-wrap; margin-top: 0.1em; margin-bottom: 0.2em; color: rgb(97, 97, 97); font-family: -apple-system, "system-ui", "Segoe UI", Roboto, sans-serif; font-size: 13px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">Result: the sca
n overhead is eliminated for the common case (~0% vs a no-scan single pass), and retained only where it's actually needed:</p>
case | before (count-always) | after
-- | -- | --
dense a→ab, 4 MB | +26.9% | +1.5%
sparse a→ab, 4 MB | +86.3% | +1.3%
dense bigexp a→abcd, 4 MB | — | +24.5% (fallback scan)
sparse bigexp a→abcd, 4 MB | — | +86.0% (fallback scan)
<p style="white-space: pre-wrap; margin-top: 0.1em; margin-bottom: 0.2em; color: rgb(97, 97, 97); font-family: -apple-system, "system-ui", "Segoe UI", Roboto, sans-serif; font-size: 13px; font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-align: start; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-thickness: initial; text-decoration-style: initial; text-decoration-color: initial;">Known limitation: a <strong>dense</strong> big-expansion (e.g. <code style="font-family: monospace; color: rgb(163, 21, 21); background-color: rgba(0, 0, 0, 0.1); padding: 2px 4px; border-radius: 3px; word-break: break-word; font-size: 0.9em;">a→abcd</code> where every position matches) still scans even though the upper bound would have been exact — density can't be known without scanning, so the gate is conservative (≤2×
over-allocation). The gate factor can be widened if dense big-expansions are a hot path.</p>
case (input size / match density) | Before: count-always | After: upper-bound + fallback
-- | -- | --
small/dense a→ab | +26.8% | −0.5%
small/sparse a→ab | +58.4% | +0.4%
medium/dense a→ab | +26.1% | −1.6%
medium/sparse a→ab | +95.4% | −0.0%
large/dense a→ab | +26.9% | +1.5%
large/sparse a→ab | +86.3% | +1.3%
large/dense shrink ab→a | +0.4% | +0.7%
large/dense bigexp a→abcd | (n/a) | +24.5%
large/sparse bigexp a→abcd | (n/a) | +86.0%
<br class="Apple-interchange-newline">
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "dmitry-chirkov-dremio (via GitHub)" <gi...@apache.org>.
dmitry-chirkov-dremio commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3454011725
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1946,9 +1914,33 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Count non-overlapping matches to size the output buffer exactly, so large
+ // results are not capped by an arbitrary limit.
+ gdv_int64 num_matches = 0;
Review Comment:
I talked to Logan about this and I'm ok accepting this as is given lack of better options.
In all the years of REPLACE function being there we just now got our first real customer case of "Buffer overflow"
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on PR #50187:
URL: https://github.com/apache/arrow/pull/50187#issuecomment-5257167974
@kou any chance this can be merged?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "dmitry-chirkov-dremio (via GitHub)" <gi...@apache.org>.
dmitry-chirkov-dremio commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3455496910
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1895,8 +1864,7 @@ const char* replace_with_max_len_utf8_utf8_utf8(gdv_int64 context, const char* t
for (; text_index <= text_len - from_str_len;) {
if (memcmp(text + text_index, from_str, from_str_len) == 0) {
if (out_index + text_index - last_match_index + to_str_len > max_length) {
Review Comment:
Nice catch reordering the subtraction first!
I think we still want to widen this to gdv_int64, though. All three operands here are still gdv_int32, so when max_length is close to INT_MAX, the sum itself can still overflow before the comparison runs. For example, out_index = INT_MAX - 10, span = 8, and to_str_len = 8 should cleanly trip the guard, but the intermediate addition is already out of range for signed 32-bit.
Could we compute a gdv_int64 prospective_len here (and in the final tail check below) and compare against static_cast<gdv_int64>(max_length)? That would make the new near-2GB path fully safe.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3437707169
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1946,9 +1914,33 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Count non-overlapping matches to size the output buffer exactly, so large
+ // results are not capped by an arbitrary limit.
+ gdv_int64 num_matches = 0;
+ if (from_str_len > 0 && from_str_len <= text_len) {
+ for (gdv_int32 i = 0; i <= text_len - from_str_len;) {
+ if (memcmp(text + i, from_str, from_str_len) == 0) {
+ num_matches++;
+ i += from_str_len;
+ } else {
+ i++;
+ }
+ }
+ }
+ gdv_int64 max_length =
+ static_cast<gdv_int64>(text_len) + num_matches * (to_str_len - from_str_len);
+ // Gandiva variable-length output uses int32 offsets, so a single output string
+ // cannot exceed INT_MAX bytes. Report this explicitly instead of letting the
+ // cast below wrap silently.
+ if (max_length > INT_MAX) {
+ gdv_fn_context_set_error_msg(context,
+ "REPLACE: output string exceeds maximum size of 2GB");
+ *out_len = 0;
+ return "";
+ }
return replace_with_max_len_utf8_utf8_utf8(context, text, text_len, from_str,
- from_str_len, to_str, to_str_len, 65535,
- out_len);
+ from_str_len, to_str, to_str_len,
+ static_cast<gdv_int32>(max_length), out_len);
Review Comment:
Yes, thats how the function know how much memory to allocate for the output string.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "dmitry-chirkov-dremio (via GitHub)" <gi...@apache.org>.
dmitry-chirkov-dremio commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3469168765
##########
cpp/src/gandiva/precompiled/CMakeLists.txt:
##########
@@ -84,3 +84,19 @@ add_gandiva_test(precompiled-test
GANDIVA_UNIT_TEST=1
ARROW_STATIC
GANDIVA_STATIC)
+
+# microbenchmark (built as a gandiva test so it links the precompiled sources
+# directly; run on demand via the gandiva-precompiled-benchmark binary)
+add_gandiva_test(precompiled-benchmark
Review Comment:
Did you mean to add this? It would seems such an addition would make benchmark a regular test, NOT on demand.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "conbench-apache-arrow[bot] (via GitHub)" <gi...@apache.org>.
conbench-apache-arrow[bot] commented on PR #50187:
URL: https://github.com/apache/arrow/pull/50187#issuecomment-5267123104
After merging your PR, Conbench analyzed the 4 benchmarking runs that have been run so far on merge-commit b38b5c5bf8ece4522e36115ead3c95f84cb99761.
There were no benchmark performance regressions. 🎉
The [full Conbench report](https://github.com/apache/arrow/runs/94121594866) has more details. It also includes information about 55 possible false positives for unstable benchmarks that are known to sometimes produce them.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3686938563
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1948,9 +1956,55 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Size the output buffer so large results are not capped by an arbitrary
+ // limit, while avoiding a second pass over the input in the common case.
+ // - No replacement possible, or the result can only shrink/stay equal:
+ // text_len is a safe exact-or-upper bound, no scan.
+ // - Small expansion (replacement at most ~2x the match): use an O(1) upper
+ // bound that assumes every position matches. This over-allocates by at
+ // most ~text_len bytes but skips the match-counting scan entirely.
+ // - Large expansion: that upper bound could be many times the input for
+ // sparse matches, so count non-overlapping matches for the exact size.
+ gdv_int64 max_length;
+ if (from_str_len <= 0 || from_str_len > text_len || to_str_len <= from_str_len) {
+ max_length = text_len;
+ } else {
+ gdv_int32 delta = to_str_len - from_str_len; // > 0
+ gdv_int64 upper_bound = static_cast<gdv_int64>(text_len) +
+ (static_cast<gdv_int64>(text_len) / from_str_len) * delta;
+ if (delta <= from_str_len && upper_bound <= INT_MAX) {
Review Comment:
good point. I updated this to a lower limit.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3437704913
##########
cpp/src/gandiva/precompiled/string_ops_test.cc:
##########
@@ -1971,6 +1971,42 @@ TEST(TestStringOps, TestReplace) {
EXPECT_EQ(std::string(out_str, out_len), "TestString");
EXPECT_FALSE(ctx.has_error());
+ // Large output (>64 KB) must not overflow: buffer is sized to the exact result.
Review Comment:
Tested one byte past the limit (INT_MAX + 1) rather than exactly INT_MAX, because a result of exactly INT_MAX is allowed and would force a real ~2 GB arena allocation — not something to do in a unit test. The boundary test confirms the guard triggers at precisely the right point.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3438187179
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1946,9 +1914,33 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Count non-overlapping matches to size the output buffer exactly, so large
+ // results are not capped by an arbitrary limit.
+ gdv_int64 num_matches = 0;
Review Comment:
old vs new is measured without a separate build: the old wrapper was literally replace_with_max_len_utf8_utf8_utf8(…, 65535, …), and that inner function is unchanged. So new = replace_utf8_utf8_utf8 (counting scan + exact alloc) and old = replace_with_max_len_utf8_utf8_utf8 given an adequately-sized buffer (the pre-change algorithm, no scan). The delta is purely the O(n) scan.
Results
| case | text_len | matches | new ns/call | old ns/call | delta |
|----|------|-----|-----|----------|-----------|
|small/dense expand a->ab | 256 | 256 | 3013.5 | 2250.3 | +33.9%|
|small/sparse expand a->ab | 256 | 4 | 1738.6 | 922.1 | +88.5%|
|medium/dense expand a->ab | 65536 | 65536 | 753132.4 | 573520.9 | +31.3%|
|medium/sparse expand a->ab | 65536 | 1024 | 436435.6 | 224018.2 | +94.8%|
|large/dense expand a->ab | 4194304 | 4194304 | 52924267.0 | 40737654.2 | +29.9%|
|large/sparse expand a->ab | 4194304 | 65536 | 28408644.3 | 14630748.5 | +94.2%|
|large/dense shrink ab->a | 4194304 | 0 | 12771361.1 | 12659342.5 | +0.9%|
Interpretation:
The scan's relative cost is consistent across sizes (~30% dense, ~90% sparse), as expected for an O(n) pass — it scales with input length, not match count.
Sparse is the worst case (+90%): with few matches, the old replace pass is mostly cheap byte-copying, so adding a full second comparison pass nearly doubles the work. Dense (+30%): the replace pass already does expansion-copying, so the scan is a smaller fraction.
Shrink path: +0.9% — confirms the refinement works; when to ≤ from the scan is skipped and there's no measurable overhead.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3476039799
##########
cpp/src/gandiva/precompiled/CMakeLists.txt:
##########
@@ -84,3 +84,19 @@ add_gandiva_test(precompiled-test
GANDIVA_UNIT_TEST=1
ARROW_STATIC
GANDIVA_STATIC)
+
+# microbenchmark (built as a gandiva test so it links the precompiled sources
+# directly; run on demand via the gandiva-precompiled-benchmark binary)
+add_gandiva_test(precompiled-benchmark
Review Comment:
fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "akravchukdremio (via GitHub)" <gi...@apache.org>.
akravchukdremio commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3444127160
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1895,8 +1864,7 @@ const char* replace_with_max_len_utf8_utf8_utf8(gdv_int64 context, const char* t
for (; text_index <= text_len - from_str_len;) {
if (memcmp(text + text_index, from_str, from_str_len) == 0) {
if (out_index + text_index - last_match_index + to_str_len > max_length) {
Review Comment:
As far as C++ evaluates this expression left-to-right, `out_index + text_index` can overflow before subtracting `last_match_index`, even when the final prospective output length is legal. This matters now, because before this PR, the wrapper function always passed `max_length = 65535`, but now the wrapper function may pass `max_length` close to `INT_MAX`, so the now we can have here large `out_index` values. To fix it we can use intermediate variable with result type of `gdv_int64` and casting all operands to this type (e.g. `static_cast<gdv_int64>(out_index)`). Or we can just do subtraction in first order in such way:
```suggestion
if (out_index + (text_index - last_match_index) + to_str_len > max_length) {
```
But maybe this is a very rare case and we can ignore it (?)
##########
cpp/src/gandiva/precompiled/string_ops_test.cc:
##########
@@ -1971,6 +1971,62 @@ TEST(TestStringOps, TestReplace) {
EXPECT_EQ(std::string(out_str, out_len), "TestString");
EXPECT_FALSE(ctx.has_error());
+ // Large output (>64 KB) must not overflow: buffer is sized to the exact result.
+ std::string large_in(35000, 'X');
+ std::string large_expected(70000, '\0');
+ for (int i = 0; i < 35000; ++i) {
+ large_expected[2 * i] = 'X';
+ large_expected[2 * i + 1] = 'Y';
+ }
+ out_str = replace_utf8_utf8_utf8(ctx_ptr, large_in.data(),
+ static_cast<int32_t>(large_in.size()), "X", 1, "XY", 2,
+ &out_len);
+ EXPECT_EQ(out_len, 70000);
+ EXPECT_EQ(std::string(out_str, out_len), large_expected);
+ EXPECT_FALSE(ctx.has_error());
+
+ // Large shrinking output ("XX" -> "X") on a >64 KB input.
+ std::string large_shrink_in(70000, 'X');
+ std::string large_shrink_expected(35000, 'X');
+ out_str = replace_utf8_utf8_utf8(ctx_ptr, large_shrink_in.data(),
+ static_cast<int32_t>(large_shrink_in.size()), "XX", 2,
+ "X", 1, &out_len);
+ EXPECT_EQ(out_len, 35000);
+ EXPECT_EQ(std::string(out_str, out_len), large_shrink_expected);
+ EXPECT_FALSE(ctx.has_error());
+
+ // Edge case: result size of exactly 0 (every byte of text is removed). Takes
+ // the no-scan shrink path (to_str_len <= from_str_len).
+ out_str = replace_utf8_utf8_utf8(ctx_ptr, "aaaa", 4, "a", 1, "", 0, &out_len);
+ EXPECT_EQ(out_len, 0);
+ EXPECT_EQ(std::string(out_str, out_len), "");
+ EXPECT_FALSE(ctx.has_error());
+
+ // Edge case: result size one past the INT_MAX boundary. 65536 single-char
+ // matches each expanding to 32768 bytes gives max_length = 65536 * 32768 =
+ // 2^31 = INT_MAX + 1, so it is reported cleanly (guard fires before any alloc).
Review Comment:
nit: we can add test case when we have just max_length = `INT_MAX`, so code should proceed without returning error
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1946,9 +1914,41 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Size the output buffer to the exact result, so large results are not capped
+ // by an arbitrary limit. When the replacement is no longer than the matched
+ // text, the result can only shrink or stay the same, so text_len is a safe
+ // bound and we can skip scanning. Otherwise count non-overlapping matches to
+ // get the exact expanded size.
+ gdv_int64 max_length;
+ if (to_str_len <= from_str_len) {
+ max_length = text_len;
+ } else {
+ gdv_int64 num_matches = 0;
+ if (from_str_len > 0 && from_str_len <= text_len) {
+ for (gdv_int32 i = 0; i <= text_len - from_str_len;) {
+ if (memcmp(text + i, from_str, from_str_len) == 0) {
+ num_matches++;
+ i += from_str_len;
+ } else {
+ i++;
+ }
+ }
+ }
+ max_length =
Review Comment:
nit: if `num_matches == 0`, we can do early return to avoid calling helper method:
```cpp
if (num_matches == 0) {
*out_len = text_len;
return text;
}
```
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1931,7 +1899,7 @@ const char* replace_with_max_len_utf8_utf8_utf8(gdv_int64 context, const char* t
}
if (out_index + text_len - last_match_index > max_length) {
Review Comment:
Same here as above
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "akravchukdremio (via GitHub)" <gi...@apache.org>.
akravchukdremio commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3444194634
##########
cpp/src/gandiva/precompiled/string_ops_test.cc:
##########
@@ -1971,6 +1971,62 @@ TEST(TestStringOps, TestReplace) {
EXPECT_EQ(std::string(out_str, out_len), "TestString");
EXPECT_FALSE(ctx.has_error());
+ // Large output (>64 KB) must not overflow: buffer is sized to the exact result.
+ std::string large_in(35000, 'X');
+ std::string large_expected(70000, '\0');
+ for (int i = 0; i < 35000; ++i) {
+ large_expected[2 * i] = 'X';
+ large_expected[2 * i + 1] = 'Y';
+ }
+ out_str = replace_utf8_utf8_utf8(ctx_ptr, large_in.data(),
+ static_cast<int32_t>(large_in.size()), "X", 1, "XY", 2,
+ &out_len);
+ EXPECT_EQ(out_len, 70000);
+ EXPECT_EQ(std::string(out_str, out_len), large_expected);
+ EXPECT_FALSE(ctx.has_error());
+
+ // Large shrinking output ("XX" -> "X") on a >64 KB input.
+ std::string large_shrink_in(70000, 'X');
+ std::string large_shrink_expected(35000, 'X');
+ out_str = replace_utf8_utf8_utf8(ctx_ptr, large_shrink_in.data(),
+ static_cast<int32_t>(large_shrink_in.size()), "XX", 2,
+ "X", 1, &out_len);
+ EXPECT_EQ(out_len, 35000);
+ EXPECT_EQ(std::string(out_str, out_len), large_shrink_expected);
+ EXPECT_FALSE(ctx.has_error());
+
+ // Edge case: result size of exactly 0 (every byte of text is removed). Takes
+ // the no-scan shrink path (to_str_len <= from_str_len).
+ out_str = replace_utf8_utf8_utf8(ctx_ptr, "aaaa", 4, "a", 1, "", 0, &out_len);
+ EXPECT_EQ(out_len, 0);
+ EXPECT_EQ(std::string(out_str, out_len), "");
+ EXPECT_FALSE(ctx.has_error());
+
+ // Edge case: result size one past the INT_MAX boundary. 65536 single-char
+ // matches each expanding to 32768 bytes gives max_length = 65536 * 32768 =
+ // 2^31 = INT_MAX + 1, so it is reported cleanly (guard fires before any alloc).
Review Comment:
nit: we can add test case when we have just max_length = `INT_MAX`, so code should proceed without returning error
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3476037996
##########
cpp/src/gandiva/precompiled/string_ops_benchmark.cc:
##########
@@ -0,0 +1,160 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Microbenchmark comparing the current REPLACE implementation against the
+// pre-change one, to measure the cost of the O(n) match-counting scan that the
+// fix added to size the output buffer exactly.
+//
+// new = replace_utf8_utf8_utf8 (counting scan + exact allocation)
+// old = replace_with_max_len_utf8_utf8_utf8(..., capacity, ...)
+// The old wrapper was literally a call to this with a fixed cap of
+// 65535; given a buffer large enough to hold the result it is the
+// pre-change algorithm with no counting scan, so new-vs-old isolates
+// the scan overhead. (The shipped old cap of 65535 additionally errored
+// out for any result above ~64 KB -- the bug this change fixes.)
+//
+// Reported time includes one ExecutionContext::Reset() per call in both arms
+// (it cancels out in the delta), mirroring per-call arena reuse.
+
+#include <chrono>
+#include <cinttypes>
+#include <cstdint>
+#include <cstdio>
+#include <functional>
+#include <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "gandiva/execution_context.h"
+#include "gandiva/precompiled/types.h"
+
+namespace gandiva {
+namespace {
+
+// Builds a `len`-byte string whose `match` byte occurs once every `stride`
+// bytes (the rest filled with `filler`), giving len/stride non-overlapping
+// matches.
+std::string MakeText(int64_t len, int stride, char match, char filler) {
+ std::string s(static_cast<size_t>(len), filler);
+ for (int64_t i = 0; i < len; i += stride) {
+ s[static_cast<size_t>(i)] = match;
+ }
+ return s;
+}
+
+double TimeNsPerCall(const std::function<void()>& fn, int iters) {
+ auto t0 = std::chrono::steady_clock::now();
+ for (int i = 0; i < iters; ++i) {
+ fn();
+ }
+ auto t1 = std::chrono::steady_clock::now();
+ return std::chrono::duration<double, std::nano>(t1 - t0).count() / iters;
+}
+
+struct Case {
+ std::string name;
+ int64_t text_len;
+ int stride; // a match every `stride` bytes
+ std::string from;
+ std::string to;
+ int iters;
+};
+
+} // namespace
+
+TEST(StringOpsBenchmark, Replace) {
+ ExecutionContext ctx;
+ int64_t ctx_ptr = reinterpret_cast<int64_t>(&ctx);
+
+ const int64_t kSmall = 256;
+ const int64_t kMedium = 64 * 1024;
+ const int64_t kLarge = 4 * 1024 * 1024;
+
+ std::vector<Case> cases = {
+ // Expansion cases (to longer than from) -- these take the O(n) scan path.
+ {"small/dense expand a->ab", kSmall, 1, "a", "ab", 200000},
+ {"small/sparse expand a->ab", kSmall, 64, "a", "ab", 200000},
+ {"medium/dense expand a->ab", kMedium, 1, "a", "ab", 4000},
+ {"medium/sparse expand a->ab", kMedium, 64, "a", "ab", 4000},
+ {"large/dense expand a->ab", kLarge, 1, "a", "ab", 80},
+ {"large/sparse expand a->ab", kLarge, 64, "a", "ab", 80},
+ // Big-expansion cases (to_len - from_len > from_len) -- these fall back to
+ // the exact match-counting scan, so new should still show the scan delta.
+ {"large/dense bigexp a->abcd", kLarge, 1, "a", "abcd", 80},
+ {"large/sparse bigexp a->abcd", kLarge, 64, "a", "abcd", 80},
+ // Shrink case (to no longer than from) -- new skips the scan entirely.
+ {"large/dense shrink ab->a", kLarge, 2, "ab", "a", 80},
+ };
+
+ printf("\n%-28s %10s %9s %12s %12s %9s\n", "case", "text_len", "matches", "new ns/call",
+ "old ns/call", "delta");
+ printf("%s\n", std::string(92, '-').c_str());
+
+ for (const auto& c : cases) {
+ std::string text = MakeText(c.text_len, c.stride, c.from[0], 'x');
+ const char* tp = text.data();
+ auto tlen = static_cast<int32_t>(text.size());
+ const char* fp = c.from.data();
+ auto flen = static_cast<int32_t>(c.from.size());
+ const char* op = c.to.data();
+ auto olen = static_cast<int32_t>(c.to.size());
+
+ // Count matches and compute the exact output size to give the "old" arm a
+ // buffer large enough to complete (precomputed -- not part of the timing).
+ int64_t matches = 0;
+ if (flen > 0 && flen <= tlen) {
+ for (int32_t i = 0; i <= tlen - flen;) {
+ if (memcmp(tp + i, fp, flen) == 0) {
+ ++matches;
+ i += flen;
+ } else {
+ ++i;
+ }
+ }
+ }
+ auto out_capacity = static_cast<int32_t>(tlen + matches * (olen - flen));
+
+ auto run_new = [&]() {
+ int32_t out_len = 0;
+ replace_utf8_utf8_utf8(ctx_ptr, tp, tlen, fp, flen, op, olen, &out_len);
+ ctx.Reset();
+ };
+ auto run_old = [&]() {
+ int32_t out_len = 0;
+ replace_with_max_len_utf8_utf8_utf8(ctx_ptr, tp, tlen, fp, flen, op, olen,
+ out_capacity, &out_len);
+ ctx.Reset();
+ };
+
+ // Warm up (and verify both produce the same length / no error).
+ run_new();
+ ASSERT_FALSE(ctx.has_error());
Review Comment:
fixed
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "dmitry-chirkov-dremio (via GitHub)" <gi...@apache.org>.
dmitry-chirkov-dremio commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3469176577
##########
cpp/src/gandiva/precompiled/string_ops_benchmark.cc:
##########
@@ -0,0 +1,160 @@
+// Licensed to the Apache Software Foundation (ASF) under one
+// or more contributor license agreements. See the NOTICE file
+// distributed with this work for additional information
+// regarding copyright ownership. The ASF licenses this file
+// to you under the Apache License, Version 2.0 (the
+// "License"); you may not use this file except in compliance
+// with the License. You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing,
+// software distributed under the License is distributed on an
+// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+// KIND, either express or implied. See the License for the
+// specific language governing permissions and limitations
+// under the License.
+
+// Microbenchmark comparing the current REPLACE implementation against the
+// pre-change one, to measure the cost of the O(n) match-counting scan that the
+// fix added to size the output buffer exactly.
+//
+// new = replace_utf8_utf8_utf8 (counting scan + exact allocation)
+// old = replace_with_max_len_utf8_utf8_utf8(..., capacity, ...)
+// The old wrapper was literally a call to this with a fixed cap of
+// 65535; given a buffer large enough to hold the result it is the
+// pre-change algorithm with no counting scan, so new-vs-old isolates
+// the scan overhead. (The shipped old cap of 65535 additionally errored
+// out for any result above ~64 KB -- the bug this change fixes.)
+//
+// Reported time includes one ExecutionContext::Reset() per call in both arms
+// (it cancels out in the delta), mirroring per-call arena reuse.
+
+#include <chrono>
+#include <cinttypes>
+#include <cstdint>
+#include <cstdio>
+#include <functional>
+#include <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "gandiva/execution_context.h"
+#include "gandiva/precompiled/types.h"
+
+namespace gandiva {
+namespace {
+
+// Builds a `len`-byte string whose `match` byte occurs once every `stride`
+// bytes (the rest filled with `filler`), giving len/stride non-overlapping
+// matches.
+std::string MakeText(int64_t len, int stride, char match, char filler) {
+ std::string s(static_cast<size_t>(len), filler);
+ for (int64_t i = 0; i < len; i += stride) {
+ s[static_cast<size_t>(i)] = match;
+ }
+ return s;
+}
+
+double TimeNsPerCall(const std::function<void()>& fn, int iters) {
+ auto t0 = std::chrono::steady_clock::now();
+ for (int i = 0; i < iters; ++i) {
+ fn();
+ }
+ auto t1 = std::chrono::steady_clock::now();
+ return std::chrono::duration<double, std::nano>(t1 - t0).count() / iters;
+}
+
+struct Case {
+ std::string name;
+ int64_t text_len;
+ int stride; // a match every `stride` bytes
+ std::string from;
+ std::string to;
+ int iters;
+};
+
+} // namespace
+
+TEST(StringOpsBenchmark, Replace) {
+ ExecutionContext ctx;
+ int64_t ctx_ptr = reinterpret_cast<int64_t>(&ctx);
+
+ const int64_t kSmall = 256;
+ const int64_t kMedium = 64 * 1024;
+ const int64_t kLarge = 4 * 1024 * 1024;
+
+ std::vector<Case> cases = {
+ // Expansion cases (to longer than from) -- these take the O(n) scan path.
+ {"small/dense expand a->ab", kSmall, 1, "a", "ab", 200000},
+ {"small/sparse expand a->ab", kSmall, 64, "a", "ab", 200000},
+ {"medium/dense expand a->ab", kMedium, 1, "a", "ab", 4000},
+ {"medium/sparse expand a->ab", kMedium, 64, "a", "ab", 4000},
+ {"large/dense expand a->ab", kLarge, 1, "a", "ab", 80},
+ {"large/sparse expand a->ab", kLarge, 64, "a", "ab", 80},
+ // Big-expansion cases (to_len - from_len > from_len) -- these fall back to
+ // the exact match-counting scan, so new should still show the scan delta.
+ {"large/dense bigexp a->abcd", kLarge, 1, "a", "abcd", 80},
+ {"large/sparse bigexp a->abcd", kLarge, 64, "a", "abcd", 80},
+ // Shrink case (to no longer than from) -- new skips the scan entirely.
+ {"large/dense shrink ab->a", kLarge, 2, "ab", "a", 80},
+ };
+
+ printf("\n%-28s %10s %9s %12s %12s %9s\n", "case", "text_len", "matches", "new ns/call",
+ "old ns/call", "delta");
+ printf("%s\n", std::string(92, '-').c_str());
+
+ for (const auto& c : cases) {
+ std::string text = MakeText(c.text_len, c.stride, c.from[0], 'x');
+ const char* tp = text.data();
+ auto tlen = static_cast<int32_t>(text.size());
+ const char* fp = c.from.data();
+ auto flen = static_cast<int32_t>(c.from.size());
+ const char* op = c.to.data();
+ auto olen = static_cast<int32_t>(c.to.size());
+
+ // Count matches and compute the exact output size to give the "old" arm a
+ // buffer large enough to complete (precomputed -- not part of the timing).
+ int64_t matches = 0;
+ if (flen > 0 && flen <= tlen) {
+ for (int32_t i = 0; i <= tlen - flen;) {
+ if (memcmp(tp + i, fp, flen) == 0) {
+ ++matches;
+ i += flen;
+ } else {
+ ++i;
+ }
+ }
+ }
+ auto out_capacity = static_cast<int32_t>(tlen + matches * (olen - flen));
+
+ auto run_new = [&]() {
+ int32_t out_len = 0;
+ replace_utf8_utf8_utf8(ctx_ptr, tp, tlen, fp, flen, op, olen, &out_len);
+ ctx.Reset();
+ };
+ auto run_old = [&]() {
+ int32_t out_len = 0;
+ replace_with_max_len_utf8_utf8_utf8(ctx_ptr, tp, tlen, fp, flen, op, olen,
+ out_capacity, &out_len);
+ ctx.Reset();
+ };
+
+ // Warm up (and verify both produce the same length / no error).
+ run_new();
+ ASSERT_FALSE(ctx.has_error());
Review Comment:
you are resetting context in lambdas so this assert is asserting what exactly?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "Copilot (via GitHub)" <gi...@apache.org>.
Copilot commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3763871494
##########
cpp/src/gandiva/tests/CMakeLists.txt:
##########
@@ -51,6 +51,24 @@ if(ARROW_BUILD_STATIC)
"gandiva"
EXTRA_LINK_LIBS
gandiva_static)
+
+ # Calls the precompiled REPLACE functions directly, so it compiles
+ # string_ops.cc/context_helper.cc with GANDIVA_UNIT_TEST=1 (which exposes them
+ # as linkable symbols). Only built when ARROW_BUILD_BENCHMARKS is ON.
Review Comment:
The comment mentions compiling both string_ops.cc and context_helper.cc with GANDIVA_UNIT_TEST=1, but this target only compiles ../precompiled/string_ops.cc directly; context_helper.cc comes from gandiva_static (and won’t be affected by the target’s compile definitions). Please update the comment to match the actual build wiring.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "kou (via GitHub)" <gi...@apache.org>.
kou merged PR #50187:
URL: https://github.com/apache/arrow/pull/50187
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "lriggs (via GitHub)" <gi...@apache.org>.
lriggs commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3438187179
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1946,9 +1914,33 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Count non-overlapping matches to size the output buffer exactly, so large
+ // results are not capped by an arbitrary limit.
+ gdv_int64 num_matches = 0;
Review Comment:
old vs new is measured without a separate build: the old wrapper was literally replace_with_max_len_utf8_utf8_utf8(…, 65535, …), and that inner function is unchanged. So new = replace_utf8_utf8_utf8 (counting scan + exact alloc) and old = replace_with_max_len_utf8_utf8_utf8 given an adequately-sized buffer (the pre-change algorithm, no scan). The delta is purely the O(n) scan.
Results
| case | text_len | matches | new ns/call | old ns/call | delta |
|----|------|-----|-----|----------|-----------|
|small/dense |expand a->ab | 256 | 256 | 3013.5 | 2250.3 | +33.9%|
|small/sparse |expand a->ab | 256 | 4 | 1738.6 | 922.1 | +88.5%|
|medium/dense | expand a->ab | 65536 | 65536 | 753132.4 | 573520.9 | +31.3%|
|medium/sparse |expand a->ab | 65536 | 1024 | 436435.6 | 224018.2 | +94.8%|
|large/dense | expand a->ab | 4194304 | 4194304 | 52924267.0 | 40737654.2 | +29.9%|
|large/sparse expand |a->ab | 4194304 | 65536 | 28408644.3 | 14630748.5 | +94.2%|
|large/dense |shrink ab->a | 4194304 | 0 | 12771361.1 | 12659342.5 | +0.9%|
Interpretation:
The scan's relative cost is consistent across sizes (~30% dense, ~90% sparse), as expected for an O(n) pass — it scales with input length, not match count.
Sparse is the worst case (+90%): with few matches, the old replace pass is mostly cheap byte-copying, so adding a full second comparison pass nearly doubles the work. Dense (+30%): the replace pass already does expansion-copying, so the scan is a smaller fraction.
Shrink path: +0.9% — confirms the refinement works; when to ≤ from the scan is skipped and there's no measurable overhead.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "dmitry-chirkov-dremio (via GitHub)" <gi...@apache.org>.
dmitry-chirkov-dremio commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3423575326
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1946,9 +1914,33 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Count non-overlapping matches to size the output buffer exactly, so large
+ // results are not capped by an arbitrary limit.
+ gdv_int64 num_matches = 0;
Review Comment:
We just reviewed base64 encoding few weeks back and didn't accept double pass variant. See if you can reduce the logic back to single pass or provide benchmarks for single-vs-double variants (0/few/lots replacements) as perhaps resizing is more costly.
##########
cpp/src/gandiva/precompiled/string_ops_test.cc:
##########
@@ -1971,6 +1971,42 @@ TEST(TestStringOps, TestReplace) {
EXPECT_EQ(std::string(out_str, out_len), "TestString");
EXPECT_FALSE(ctx.has_error());
+ // Large output (>64 KB) must not overflow: buffer is sized to the exact result.
Review Comment:
I'd feel more comfortable with few specific edge cases but I would not block the PR. Examples:
- INT_MAX resulting size
- 0 resulting size
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1946,9 +1914,33 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Count non-overlapping matches to size the output buffer exactly, so large
+ // results are not capped by an arbitrary limit.
+ gdv_int64 num_matches = 0;
+ if (from_str_len > 0 && from_str_len <= text_len) {
+ for (gdv_int32 i = 0; i <= text_len - from_str_len;) {
+ if (memcmp(text + i, from_str, from_str_len) == 0) {
+ num_matches++;
+ i += from_str_len;
+ } else {
+ i++;
+ }
+ }
+ }
+ gdv_int64 max_length =
+ static_cast<gdv_int64>(text_len) + num_matches * (to_str_len - from_str_len);
+ // Gandiva variable-length output uses int32 offsets, so a single output string
+ // cannot exceed INT_MAX bytes. Report this explicitly instead of letting the
+ // cast below wrap silently.
+ if (max_length > INT_MAX) {
+ gdv_fn_context_set_error_msg(context,
+ "REPLACE: output string exceeds maximum size of 2GB");
+ *out_len = 0;
+ return "";
+ }
return replace_with_max_len_utf8_utf8_utf8(context, text, text_len, from_str,
- from_str_len, to_str, to_str_len, 65535,
- out_len);
+ from_str_len, to_str, to_str_len,
+ static_cast<gdv_int32>(max_length), out_len);
Review Comment:
Do we even need this argument in the function signature?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "laurentgo (via GitHub)" <gi...@apache.org>.
laurentgo commented on code in PR #50187:
URL: https://github.com/apache/arrow/pull/50187#discussion_r3685443931
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1948,9 +1956,55 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Size the output buffer so large results are not capped by an arbitrary
+ // limit, while avoiding a second pass over the input in the common case.
+ // - No replacement possible, or the result can only shrink/stay equal:
+ // text_len is a safe exact-or-upper bound, no scan.
+ // - Small expansion (replacement at most ~2x the match): use an O(1) upper
+ // bound that assumes every position matches. This over-allocates by at
+ // most ~text_len bytes but skips the match-counting scan entirely.
+ // - Large expansion: that upper bound could be many times the input for
+ // sparse matches, so count non-overlapping matches for the exact size.
+ gdv_int64 max_length;
+ if (from_str_len <= 0 || from_str_len > text_len || to_str_len <= from_str_len) {
+ max_length = text_len;
+ } else {
+ gdv_int32 delta = to_str_len - from_str_len; // > 0
+ gdv_int64 upper_bound = static_cast<gdv_int64>(text_len) +
+ (static_cast<gdv_int64>(text_len) / from_str_len) * delta;
+ if (delta <= from_str_len && upper_bound <= INT_MAX) {
Review Comment:
how comfortable are we allocating INT_MAX automatically, should we consider a lower limit?
##########
cpp/src/gandiva/precompiled/string_ops.cc:
##########
@@ -1948,9 +1956,55 @@ const char* replace_utf8_utf8_utf8(gdv_int64 context, const char* text,
gdv_int32 text_len, const char* from_str,
gdv_int32 from_str_len, const char* to_str,
gdv_int32 to_str_len, gdv_int32* out_len) {
+ // Size the output buffer so large results are not capped by an arbitrary
+ // limit, while avoiding a second pass over the input in the common case.
+ // - No replacement possible, or the result can only shrink/stay equal:
+ // text_len is a safe exact-or-upper bound, no scan.
+ // - Small expansion (replacement at most ~2x the match): use an O(1) upper
Review Comment:
it is as small as `text_length`. If `text_length` is large, I'm not sure I would qualify this as a small expansion
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] GH-50186: [C++][Gandiva] REPLACE throws "Buffer overflow for output string" for results larger than 64 KB [arrow]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #50187:
URL: https://github.com/apache/arrow/pull/50187#issuecomment-4714032839
:warning: GitHub issue #50186 **has been automatically assigned in GitHub** to PR creator.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: github-unsubscribe@arrow.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org