Skip to content

Commit 7c1e882

Browse files
liaoxin01Xin Liao
authored andcommitted
[fix](rle) Fix infinite loop when a repeated run reaches 2^30 values (#69100)
### What problem does this PR solve? Problem Summary: `RleEncoder::FlushRepeatedRun()` wrote `repeat_count_ << 1` into an `int32_t`. `repeat_count_` was an `int`, so a repeated run of 2^30 or more values overflowed the indicator into a negative number. `BitWriter::PutVlqInt()` then took that as an `int32_t` and shifted it right arithmetically: ```cpp inline void BitWriter::PutVlqInt(int32_t v) { while ((v & 0xFFFFFF80) != 0L) { PutAligned<uint8_t>((v & 0x7F) | 0x80, 1); v >>= 7; } PutAligned<uint8_t>(v & 0x7F, 1); } ``` An arithmetic right shift of a negative value converges to `-1` and stays there, and `-1 & 0xFFFFFF80` is non-zero, so **the loop never exits**. It appends `0xFF` to the output buffer forever, pinning a core at 100% and growing the buffer without bound. #### How it was hit A base compaction in a production cluster wedged on a table with many nullable `text` columns. Two `BaseCompactionT` threads sat in this stack for over a month: ``` #0 inline_memcpy (size=348057208) #2 doris::faststring::GrowArray (newcapacity=502825728) #4 doris::BitWriter::GetNextBytePtr (num_bytes=1) #5 doris::BitWriter::PutAligned<unsigned char> (val=255 '\377') #6 doris::BitWriter::PutVlqInt (v=-1) bit_stream_utils.inline.h:91 #7 doris::RleEncoder<bool>::FlushRepeatedRun rle_encoding.h:499 #9 doris::segment_v2::NullBitmapBuilder::finish #11 doris::segment_v2::ScalarColumnWriter::finish #15 doris::Merger::vertical_compact_one_group (is_key=false, max_rows_per_segment=1073741824) #20 doris::CloudBaseCompaction::execute_compact ``` `v=-1` together with `val=255` pins it down exactly: the loop is emitting `0xFF` with `v` stuck at `-1`. Two existing behaviours combined to produce a 2^30-value run: - Vertical compaction derives the segment row limit from `vertical_compaction_max_segment_size / avg_bytes_per_row` ([`Compaction::get_avg_segment_rows()`](https://github.com/apache/doris/blob/master/be/src/olap/compaction.cpp)). For this table the average row size integer-divided to `0`, so the divisor degenerated to `1` and the limit became the config default `1073741824` = 2^30 rows — visible as `max_rows_per_segment=1073741824` in the stack above. - `ScalarColumnWriter::append_nulls()` never checks whether the page is full, unlike `append_data()`, and NULLs never reach the page builder. So an all-NULL column accumulated a single null-bitmap run spanning the whole 2^30-row segment in one page. Because the stuck tasks kept the base compaction slots occupied (`max_base_compaction_task_num_per_disk` defaults to 2), `_generate_cloud_compaction_tasks()` computed `base_n = 0` and stopped picking any tablet, so **no base compaction ran on that backend again** and compaction scores climbed to the cap across the instance. ### What this PR changes 1. **`PutVlqInt()` takes `uint32_t`.** A logical shift always converges to 0, so the loop terminates for every possible input. This is the backstop that makes a hang impossible regardless of what callers pass. 2. **`repeat_count_` widened to `int64_t`, and long runs are split.** Runs longer than `MAX_VALUES_PER_REPEATED_RUN` (2^30 - 1) are emitted as several back-to-back repeated runs of the same value. Readers already merge adjacent runs carrying the same value (`RleDecoder::GetNextRun`), so splitting is invisible to them. The cap keeps the indicator inside `int32_t`'s positive range — exactly the range previous versions could encode — so **output stays byte-identical for every run length that used to work**, and no reader change is needed. 3. **`faststring::reserve()` grows geometrically** via the existing `GrowToAtLeast()` instead of reallocating to exactly the requested capacity. `BitWriter` reserves a handful of bytes at a time, so exact growth reallocated and memcpy'd the entire buffer every 8 bytes, making an n-byte append cost O(n^2). This is what turned the infinite loop into a thread stuck in `memcpy` with a ~500MB buffer, and it slows down every other large RLE buffer as well. Measured: reaching 1 MiB now takes 26 reallocations instead of ~131,000. Deliberately **not** in this PR, each worth its own change: - `ScalarColumnWriter::append_nulls()` still lets a page grow without bound. - `Compaction::get_avg_segment_rows()` still degenerates to the configured byte size when the average row size rounds down to zero. ### Release note Fix a BE hang in RLE encoding when a column produces a run of 2^30 or more identical values (for example an all-NULL column in a very large segment), which could permanently stall base compaction on that backend. ### Check List (For Author) - Test - [x] Unit Test New tests: | Test | Covers | |---|---| | `TestRle.TestRepeatedRunExceedingIndicatorRange` | Run lengths around and far beyond 2^30 encode compactly and decode back to the original length | | `TestBitStreamUtil.TestPutVlqIntRoundTrip` | `PutVlqInt` round-trips every `uint32_t`, including values `>= 2^31` that used to hang | | `FaststringTest.TestReserve_ExponentiallyExpand` | `reserve()` does not reallocate on every call | Verified that the new tests actually catch the bug: built the exact repro (`RleEncoder<bool>::Put(true, 1 << 30)` followed by `Flush()`) against unpatched master and it never returns (killed by timeout); with this patch it completes and emits 8 bytes. All pre-existing tests in `rle_encoding_test`, `bit_stream_utils_test` and `faststring_test` pass (29 tests, with `LOOP_LESS_OR_MORE` forced to the slow/thorough branch). Also confirmed no format regression: a short run encoded via `Put(v)` in a loop and via `Put(v, n)` in one call still produce byte-identical output. - Behavior changed: - [x] No. Encoded output is unchanged for every run length that previously encoded correctly; only run lengths that used to hang now produce (correct, readable) output. - Does this need documentation? - [x] No. Co-authored-by: Xin Liao <[email protected]>
1 parent 9ffd818 commit 7c1e882

7 files changed

Lines changed: 139 additions & 13 deletions

File tree

‎be/src/util/bit_stream_utils.h‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -60,7 +60,9 @@ class BitWriter {
6060

6161
// Write a Vlq encoded int to the buffer. The value is written byte aligned.
6262
// For more details on vlq: en.wikipedia.org/wiki/Variable-length_quantity
63-
void PutVlqInt(int32_t v);
63+
// Takes an unsigned value on purpose: the encoding shifts `v` right until it
64+
// is exhausted, which only terminates for a logical shift.
65+
void PutVlqInt(uint32_t v);
6466

6567
// Get the index to the next aligned byte and advance the underlying buffer by num_bytes.
6668
size_t GetByteIndexAndAdvance(int num_bytes) {

‎be/src/util/bit_stream_utils.inline.h‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -86,12 +86,12 @@ void BitWriter::PutAligned(T val, int num_bytes) {
8686
memcpy(ptr, &val, num_bytes);
8787
}
8888

89-
inline void BitWriter::PutVlqInt(int32_t v) {
90-
while ((v & 0xFFFFFF80) != 0L) {
91-
PutAligned<uint8_t>((v & 0x7F) | 0x80, 1);
89+
inline void BitWriter::PutVlqInt(uint32_t v) {
90+
while ((v & 0xFFFFFF80U) != 0U) {
91+
PutAligned<uint8_t>(static_cast<uint8_t>((v & 0x7F) | 0x80), 1);
9292
v >>= 7;
9393
}
94-
PutAligned<uint8_t>(v & 0x7F, 1);
94+
PutAligned<uint8_t>(static_cast<uint8_t>(v & 0x7F), 1);
9595
}
9696

9797
inline BitReader::BitReader(const uint8_t* buffer, int buffer_len)

‎be/src/util/faststring.h‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -106,7 +106,10 @@ class faststring : private Allocator<false, false, false, DefaultMemoryAllocator
106106
if (newcapacity <= capacity_) [[likely]] {
107107
return;
108108
}
109-
GrowArray(newcapacity);
109+
// Grow by at least 50% rather than to exactly `newcapacity`. Callers such
110+
// as BitWriter reserve a few bytes at a time, and reallocating on every
111+
// call makes appending n bytes cost O(n^2) in memcpy.
112+
GrowToAtLeast(newcapacity);
110113
}
111114

112115
// Append the given data to the string, resizing capacity as necessary.

‎be/src/util/rle_encoding.h‎

Lines changed: 29 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,8 @@
1818

1919
#include <glog/logging.h>
2020

21+
#include <algorithm>
22+
#include <cstdint>
2123
#include <limits> // IWYU pragma: keep
2224

2325
#include "common/cast_set.h"
@@ -157,6 +159,16 @@ class RleEncoder {
157159
Clear();
158160
}
159161

162+
// The largest number of values a single repeated run can describe.
163+
//
164+
// A repeated run is written as a vlq-encoded indicator holding
165+
// `run_length << 1` (see FlushRepeatedRun) and read back into a uint32_t by
166+
// BitReader::GetVlqInt. Capping the run length here keeps the indicator
167+
// inside int32_t's positive range, which is exactly the range every released
168+
// version could already encode, so the output stays byte-identical for any
169+
// run length that used to work.
170+
static constexpr int64_t MAX_VALUES_PER_REPEATED_RUN = (int64_t {1} << 30) - 1;
171+
160172
// Reserve 'num_bytes' bytes for a plain encoded header, set each
161173
// byte with 'val': this is used for the RLE-encoded data blocks in
162174
// order to be able to able to store the initial ordinal position
@@ -213,7 +225,7 @@ class RleEncoder {
213225
// if we are in a literal run. If the repeat_count_ get high enough, we switch
214226
// to encoding repeated runs.
215227
uint64_t current_value_;
216-
int repeat_count_;
228+
int64_t repeat_count_;
217229

218230
// Number of literals in the current run. This does not include the literals
219231
// that might be in buffered_values_. Only after we've got a group big enough
@@ -438,7 +450,7 @@ void RleEncoder<T>::Put(T value, size_t run_length) {
438450
// Fast path: if this is a continuation of the current repeated run and
439451
// we've already buffered enough values, just increment repeat_count_
440452
if (current_value_ == value && repeat_count_ >= 8 && run_length > 0) [[likely]] {
441-
repeat_count_ += run_length;
453+
repeat_count_ += static_cast<int64_t>(run_length);
442454
return;
443455
}
444456

@@ -458,7 +470,7 @@ void RleEncoder<T>::Put(T value, size_t run_length) {
458470
// After flushing, if we still have a repeated run and more values,
459471
// we can add them directly to repeat_count_
460472
if (repeat_count_ >= 8 && run_length > 0) {
461-
repeat_count_ += run_length;
473+
repeat_count_ += static_cast<int64_t>(run_length);
462474
return;
463475
}
464476
}
@@ -515,11 +527,21 @@ void RleEncoder<T>::FlushLiteralRun(bool update_indicator_byte) {
515527
template <typename T>
516528
void RleEncoder<T>::FlushRepeatedRun() {
517529
DCHECK_GT(repeat_count_, 0);
518-
// The lsb of 0 indicates this is a repeated run
519-
int32_t indicator_value = repeat_count_ << 1 | 0;
520-
bit_writer_.PutVlqInt(indicator_value);
521-
bit_writer_.PutAligned(current_value_, BitUtil::Ceil(bit_width_, 8));
530+
// A run longer than MAX_VALUES_PER_REPEATED_RUN cannot be described by a
531+
// single indicator, so emit it as several back-to-back repeated runs of the
532+
// same value. Decoders stitch those back together transparently
533+
// (RleDecoder::GetNextRun merges adjacent runs carrying the same value), so
534+
// splitting is invisible to readers.
535+
while (repeat_count_ > 0) {
536+
const int64_t run_length = std::min(repeat_count_, MAX_VALUES_PER_REPEATED_RUN);
537+
// The lsb of 0 indicates this is a repeated run
538+
bit_writer_.PutVlqInt(static_cast<uint32_t>(run_length) << 1);
539+
bit_writer_.PutAligned(current_value_, BitUtil::Ceil(bit_width_, 8));
540+
repeat_count_ -= run_length;
541+
}
522542
num_buffered_values_ = 0;
543+
// The loop above drains repeat_count_; assign it anyway so the postcondition
544+
// holds even if it somehow entered non-positive.
523545
repeat_count_ = 0;
524546
}
525547

‎be/test/util/bit_stream_utils_test.cpp‎

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -218,4 +218,29 @@ TEST(TestBitStreamUtil, TestUint64) {
218218
reader.GetValue(16, &v4);
219219
EXPECT_EQ(v4, 126);
220220
}
221+
// PutVlqInt() must terminate for every uint32_t. It used to take an int32_t and
222+
// shift it right arithmetically, so any value with the sign bit set (>= 2^31)
223+
// made the loop spin forever appending 0xFF.
224+
TEST(TestBitStreamUtil, TestPutVlqIntRoundTrip) {
225+
const int max_vlq_byte_len = BitReader::MAX_VLQ_BYTE_LEN;
226+
const std::vector<uint32_t> values = {
227+
0, 1, 0x7F, 0x80, 0x3FFF, 0x4000,
228+
0x1FFFFF, 0x200000, 0xFFFFFFF, 0x10000000, 0x7FFFFFFE, 0x7FFFFFFF,
229+
0x80000000, 0x80000001, 0xFFFFFFFE, 0xFFFFFFFF,
230+
};
231+
232+
for (uint32_t value : values) {
233+
faststring buffer;
234+
BitWriter writer(&buffer);
235+
writer.PutVlqInt(value);
236+
writer.Flush();
237+
EXPECT_LE(writer.bytes_written(), max_vlq_byte_len) << "value=" << value;
238+
239+
BitReader reader(buffer.data(), buffer.size());
240+
uint32_t decoded = 0;
241+
ASSERT_TRUE(reader.GetVlqInt(&decoded)) << "value=" << value;
242+
EXPECT_EQ(value, decoded) << "value=" << value;
243+
}
244+
}
245+
221246
} // namespace doris

‎be/test/util/faststring_test.cpp‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -135,4 +135,28 @@ TEST_F(FaststringTest, TestAppend_ExponentiallyExpand) {
135135
}
136136
}
137137

138+
// reserve() must grow geometrically. BitWriter reserves a handful of bytes at a
139+
// time, so reallocating to the exact requested size made appending n bytes cost
140+
// O(n^2) in memcpy -- enough to stall a thread outright once the buffer reached
141+
// hundreds of megabytes.
142+
TEST_F(FaststringTest, TestReserve_ExponentiallyExpand) {
143+
constexpr size_t kTargetSize = 1 * 1024 * 1024;
144+
145+
faststring s;
146+
size_t last_capacity = s.capacity();
147+
int reallocations = 0;
148+
for (size_t i = 0; i < kTargetSize; ++i) {
149+
s.reserve(i + 1);
150+
if (s.capacity() != last_capacity) {
151+
++reallocations;
152+
last_capacity = s.capacity();
153+
}
154+
}
155+
156+
EXPECT_GE(s.capacity(), kTargetSize);
157+
// Growing 1.5x at a time from kInitialCapacity needs ~26 steps to pass 1 MiB.
158+
// Exact growth would instead reallocate on (almost) every one of the 1M calls.
159+
EXPECT_LT(reallocations, 64);
160+
}
161+
138162
} // namespace doris

‎be/test/util/rle_encoding_test.cpp‎

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -698,6 +698,56 @@ TEST_F(TestRle, TestPutFlushThenFastPath) {
698698
}
699699
}
700700

701+
// Regression test for a hang on repeated runs that a single run indicator
702+
// cannot describe.
703+
//
704+
// FlushRepeatedRun() used to write `repeat_count_ << 1` into an int32_t, so a
705+
// run of 2^30 or more values overflowed into a negative indicator.
706+
// BitWriter::PutVlqInt() then took an int32_t and shifted it right
707+
// arithmetically, which sticks at -1 instead of reaching 0 -- an infinite loop
708+
// appending 0xFF to the output buffer. In the wild this showed up as a base
709+
// compaction thread spinning forever while flushing the null bitmap of a
710+
// nullable column whose page held one run of 2^30 null rows.
711+
TEST_F(TestRle, TestRepeatedRunExceedingIndicatorRange) {
712+
constexpr int64_t kMaxRun = RleEncoder<bool>::MAX_VALUES_PER_REPEATED_RUN;
713+
const std::vector<int64_t> run_lengths = {
714+
kMaxRun - 1,
715+
kMaxRun,
716+
kMaxRun + 1,
717+
int64_t {1} << 30, // smallest run length that used to overflow
718+
(int64_t {1} << 30) + 12345,
719+
int64_t {1} << 31,
720+
3 * (int64_t {1} << 30),
721+
};
722+
723+
for (int64_t run_length : run_lengths) {
724+
faststring buffer;
725+
RleEncoder<bool> encoder(&buffer, 1);
726+
// Put() extends an established run in O(1), so this stays cheap even for
727+
// billions of values.
728+
encoder.Put(true, run_length);
729+
const int encoded_len = encoder.Flush();
730+
731+
// A split run stays compact: one short header per emitted run.
732+
const int64_t expected_runs = (run_length + kMaxRun - 1) / kMaxRun;
733+
EXPECT_LE(encoded_len, expected_runs * 8 + 8) << "run_length=" << run_length;
734+
735+
// GetNextRun() merges adjacent repeated runs carrying the same value, so
736+
// splitting is invisible to readers: this must read back as one run of
737+
// the original length.
738+
RleDecoder<bool> decoder(buffer.data(), encoded_len, 1);
739+
int64_t decoded = 0;
740+
while (decoded < run_length) {
741+
bool val = false;
742+
size_t run = decoder.GetNextRun(&val, static_cast<size_t>(run_length - decoded));
743+
ASSERT_GT(run, 0u) << "run_length=" << run_length << " decoded=" << decoded;
744+
ASSERT_TRUE(val) << "run_length=" << run_length << " decoded=" << decoded;
745+
decoded += static_cast<int64_t>(run);
746+
}
747+
EXPECT_EQ(decoded, run_length) << "run_length=" << run_length;
748+
}
749+
}
750+
701751
// Benchmark for Put function performance with consecutive equal values
702752
// This test compares:
703753
// 1. Put(value) called N times in a loop

0 commit comments

Comments
 (0)