Skip to content

Commit 898e12e

Browse files
authored
ARROW-16692: [C++] StackOverflow in merge generator causes segmentation fault in scan (#13691)
Fix for the merged generator to avoid a potential stack overflow Authored-by: Weston Pace <[email protected]> Signed-off-by: Weston Pace <[email protected]>
1 parent 4e37149 commit 898e12e

3 files changed

Lines changed: 102 additions & 38 deletions

File tree

‎cpp/src/arrow/dataset/scanner_test.cc‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -766,6 +766,12 @@ TEST_P(TestScanner, FromReader) {
766766
Invalid, ::testing::HasSubstr("OneShotFragment was already scanned"),
767767
std::move(maybe_batch_it));
768768
}
769+
770+
// TODO(ARROW-16072) At the moment, we can't be sure that the scanner has completely
771+
// shutdown, even though the plan has finished, because errors are not handled cleanly
772+
// in the scanner/execplan relationship. Once ARROW-16072 is fixed this should be
773+
// reliable and we can get rid of this. See also ARROW-17198
774+
::arrow::internal::GetCpuThreadPool()->WaitForIdle();
769775
}
770776

771777
INSTANTIATE_TEST_SUITE_P(TestScannerThreading, TestScanner,

‎cpp/src/arrow/util/async_generator.h‎

Lines changed: 77 additions & 38 deletions
Original file line numberDiff line numberDiff line change
@@ -1093,7 +1093,7 @@ class MergedGenerator {
10931093
state_->all_finished.MarkFinished();
10941094
} else {
10951095
delivered_job->deliverer().AddCallback(
1096-
InnerCallback{state_, delivered_job->index});
1096+
InnerCallback(state_, delivered_job->index));
10971097
}
10981098
return std::move(delivered_job->value);
10991099
}
@@ -1253,6 +1253,9 @@ class MergedGenerator {
12531253
};
12541254

12551255
struct InnerCallback {
1256+
InnerCallback(std::shared_ptr<State> state, std::size_t index, bool recursive = false)
1257+
: state(std::move(state)), index(index), recursive(recursive) {}
1258+
12561259
void operator()(const Result<T>& maybe_next_ref) {
12571260
// An item has been delivered by one of the inner subscriptions
12581261
Future<T> next_fut;
@@ -1332,6 +1335,10 @@ class MergedGenerator {
13321335
}
13331336

13341337
if (pull_next_sub) {
1338+
if (recursive) {
1339+
was_empty = true;
1340+
return;
1341+
}
13351342
// We pulled an end token so we need to start a new subscription
13361343
// in our spot
13371344
state->PullSource().AddCallback(OuterCallback{state, index});
@@ -1340,7 +1347,7 @@ class MergedGenerator {
13401347
// so lets fetch the next result from our subscription
13411348
sink.MarkFinished(*maybe_next);
13421349
next_fut = state->active_subscriptions[index]();
1343-
if (next_fut.TryAddCallback([this]() { return *this; })) {
1350+
if (next_fut.TryAddCallback([this]() { return InnerCallback(state, index); })) {
13441351
return;
13451352
}
13461353
// Already completed. Avoid very deep recursion by looping
@@ -1355,49 +1362,81 @@ class MergedGenerator {
13551362
}
13561363
std::shared_ptr<State> state;
13571364
std::size_t index;
1365+
bool recursive;
1366+
bool was_empty = false;
13581367
};
13591368

13601369
struct OuterCallback {
1361-
void operator()(const Result<AsyncGenerator<T>>& maybe_next) {
1362-
// We have been given a new inner subscription
1363-
bool should_continue = false;
1364-
bool should_mark_gen_complete = false;
1365-
bool should_deliver_error = false;
1366-
bool source_exhausted = maybe_next.ok() && IsIterationEnd(*maybe_next);
1367-
Future<T> error_sink;
1368-
{
1369-
auto guard = state->mutex.Lock();
1370-
if (!maybe_next.ok() || source_exhausted || state->broken) {
1371-
// If here then we will not pull any more from the outer source
1372-
if (!state->broken && !maybe_next.ok()) {
1373-
state->SignalErrorUnlocked(guard);
1374-
// If here then we are the first error so we need to deliver it
1375-
should_deliver_error = true;
1376-
if (!state->waiting_jobs.empty()) {
1377-
error_sink = std::move(*state->waiting_jobs.front());
1378-
state->waiting_jobs.pop_front();
1370+
void operator()(const Result<AsyncGenerator<T>>& initial_maybe_next) {
1371+
Result<AsyncGenerator<T>> maybe_next = initial_maybe_next;
1372+
while (true) {
1373+
// We have been given a new inner subscription
1374+
bool should_continue = false;
1375+
bool should_mark_gen_complete = false;
1376+
bool should_deliver_error = false;
1377+
bool source_exhausted = maybe_next.ok() && IsIterationEnd(*maybe_next);
1378+
Future<T> error_sink;
1379+
{
1380+
auto guard = state->mutex.Lock();
1381+
if (!maybe_next.ok() || source_exhausted || state->broken) {
1382+
// If here then we will not pull any more from the outer source
1383+
if (!state->broken && !maybe_next.ok()) {
1384+
state->SignalErrorUnlocked(guard);
1385+
// If here then we are the first error so we need to deliver it
1386+
should_deliver_error = true;
1387+
if (!state->waiting_jobs.empty()) {
1388+
error_sink = std::move(*state->waiting_jobs.front());
1389+
state->waiting_jobs.pop_front();
1390+
}
13791391
}
1392+
if (source_exhausted) {
1393+
state->source_exhausted = true;
1394+
state->num_running_subscriptions--;
1395+
}
1396+
if (state->MarkTaskFinishedUnlocked(guard)) {
1397+
should_mark_gen_complete = true;
1398+
}
1399+
} else {
1400+
state->active_subscriptions[index] = *maybe_next;
1401+
should_continue = true;
13801402
}
1381-
if (source_exhausted) {
1382-
state->source_exhausted = true;
1383-
state->num_running_subscriptions--;
1384-
}
1385-
if (state->MarkTaskFinishedUnlocked(guard)) {
1386-
should_mark_gen_complete = true;
1403+
}
1404+
if (should_deliver_error) {
1405+
state->MarkFinalError(maybe_next.status(), std::move(error_sink));
1406+
}
1407+
if (should_mark_gen_complete) {
1408+
state->MarkFinishedAndPurge();
1409+
}
1410+
if (should_continue) {
1411+
// There is a possibility that a large sequence of immediately available inner
1412+
// callbacks could lead to a stack overflow. To avoid this we need to
1413+
// synchronously loop through inner/outer callbacks until we either find an
1414+
// unfinished future or we find an actual item to deliver.
1415+
Future<T> next_item = (*maybe_next)();
1416+
if (!next_item.TryAddCallback([this] { return InnerCallback(state, index); })) {
1417+
// By setting recursive to true we signal to the inner callback that, if it is
1418+
// empty, instead of adding a new outer callback, it should just immediately
1419+
// return, flagging was_empty so that we know we need to check the next
1420+
// subscription.
1421+
InnerCallback immediate_inner(state, index, /*recursive=*/true);
1422+
immediate_inner(next_item.result());
1423+
if (immediate_inner.was_empty) {
1424+
Future<AsyncGenerator<T>> next_source = state->PullSource();
1425+
if (next_source.TryAddCallback([this] {
1426+
return OuterCallback{state, index};
1427+
})) {
1428+
// We hit an unfinished future so we can stop looping
1429+
return;
1430+
}
1431+
// The current subscription was immediately and synchronously empty
1432+
// and we were able to synchronously pull the next subscription so we
1433+
// can keep looping.
1434+
maybe_next = next_source.result();
1435+
continue;
1436+
}
13871437
}
1388-
} else {
1389-
state->active_subscriptions[index] = *maybe_next;
1390-
should_continue = true;
13911438
}
1392-
}
1393-
if (should_deliver_error) {
1394-
state->MarkFinalError(maybe_next.status(), std::move(error_sink));
1395-
}
1396-
if (should_mark_gen_complete) {
1397-
state->MarkFinishedAndPurge();
1398-
}
1399-
if (should_continue) {
1400-
(*maybe_next)().AddCallback(InnerCallback{state, index});
1439+
return;
14011440
}
14021441
}
14031442
std::shared_ptr<State> state;

‎cpp/src/arrow/util/async_generator_test.cc‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -762,6 +762,25 @@ TEST_P(MergedGeneratorTestFixture, MergedRecursion) {
762762
}
763763
}
764764

765+
TEST_P(MergedGeneratorTestFixture, DeepOuterGeneratorStackOverflow) {
766+
// Simulate a very deep and very quick outer generator that yields simple
767+
// inner generators. Everything completes synchronously. This is to
768+
// try and provoke a stack overflow the simulates ARROW-16692
769+
constexpr int kNumItems = 10000;
770+
constexpr int kMaxSubscriptions = 8;
771+
std::vector<AsyncGenerator<TestInt>> inner_generators;
772+
for (int i = 0; i < kNumItems; i++) {
773+
inner_generators.push_back(MakeVectorGenerator<TestInt>({}));
774+
}
775+
AsyncGenerator<AsyncGenerator<TestInt>> outer_generator =
776+
MakeVectorGenerator(inner_generators);
777+
AsyncGenerator<TestInt> merged =
778+
MakeMergedGenerator(outer_generator, kMaxSubscriptions);
779+
ASSERT_FINISHES_OK_AND_ASSIGN(std::vector<TestInt> collected,
780+
CollectAsyncGenerator(std::move(merged)));
781+
ASSERT_TRUE(collected.empty());
782+
}
783+
765784
INSTANTIATE_TEST_SUITE_P(MergedGeneratorTests, MergedGeneratorTestFixture,
766785
::testing::Values(false, true));
767786

0 commit comments

Comments
 (0)