Skip to content

Commit bf1b294

Browse files
roberthroberth
authored
Merge pull request NixOS#9617 from 9999years/stack-overflow-segfault
Fix segfault on infinite recursion in some cases
2 parents a21c762 + 7434cac commit bf1b294

12 files changed

Lines changed: 358 additions & 4 deletions

‎doc/manual/rl-next/stack-overflow-segfaults.md‎

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
---
2+
synopsis: Some stack overflow segfaults are fixed
3+
issues: 9616
4+
prs: 9617
5+
---
6+
7+
The number of nested function calls has been restricted, to detect and report
8+
infinite function call recursions. The default maximum call depth is 10,000 and
9+
can be set with [the `max-call-depth`
10+
option](@docroot@/command-ref/conf-file.md#conf-max-call-depth).
11+
12+
This fixes segfaults or the following unhelpful error message in many cases:
13+
14+
error: stack overflow (possible infinite recursion)
15+
16+
Before:
17+
18+
```
19+
$ nix-instantiate --eval --expr '(x: x x) (x: x x)'
20+
Segmentation fault: 11
21+
```
22+
23+
After:
24+
25+
```
26+
$ nix-instantiate --eval --expr '(x: x x) (x: x x)'
27+
error: stack overflow
28+
29+
at «string»:1:14:
30+
1| (x: x x) (x: x x)
31+
| ^
32+
```

‎src/libexpr/eval-settings.hh‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -124,6 +124,9 @@ struct EvalSettings : Config
124124

125125
Setting<bool> traceVerbose{this, false, "trace-verbose",
126126
"Whether `builtins.traceVerbose` should trace its first argument when evaluated."};
127+
128+
Setting<unsigned int> maxCallDepth{this, 10000, "max-call-depth",
129+
"The maximum function call depth to allow before erroring."};
127130
};
128131

129132
extern EvalSettings evalSettings;

‎src/libexpr/eval.cc‎

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1505,9 +1505,27 @@ void ExprLambda::eval(EvalState & state, Env & env, Value & v)
15051505
v.mkLambda(&env, this);
15061506
}
15071507

1508+
namespace {
1509+
/** Increments a count on construction and decrements on destruction.
1510+
*/
1511+
class CallDepth {
1512+
size_t & count;
1513+
public:
1514+
CallDepth(size_t & count) : count(count) {
1515+
++count;
1516+
}
1517+
~CallDepth() {
1518+
--count;
1519+
}
1520+
};
1521+
};
15081522

15091523
void EvalState::callFunction(Value & fun, size_t nrArgs, Value * * args, Value & vRes, const PosIdx pos)
15101524
{
1525+
if (callDepth > evalSettings.maxCallDepth)
1526+
error("stack overflow; max-call-depth exceeded").atPos(pos).template debugThrow<EvalError>();
1527+
CallDepth _level(callDepth);
1528+
15111529
auto trace = evalSettings.traceFunctionCalls
15121530
? std::make_unique<FunctionCallTrace>(positions[pos])
15131531
: nullptr;

‎src/libexpr/eval.hh‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -622,6 +622,11 @@ private:
622622
const SourcePath & basePath,
623623
std::shared_ptr<StaticEnv> & staticEnv);
624624

625+
/**
626+
* Current Nix call stack depth, used with `max-call-depth` setting to throw stack overflow hopefully before we run out of system stack.
627+
*/
628+
size_t callDepth = 0;
629+
625630
public:
626631

627632
/**

‎src/libutil/error.cc‎

Lines changed: 107 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,32 @@ std::ostream & operator <<(std::ostream & str, const AbstractPos & pos)
5050
return str;
5151
}
5252

53+
/**
54+
* An arbitrarily defined value comparison for the purpose of using traces in the key of a sorted container.
55+
*/
56+
inline bool operator<(const Trace& lhs, const Trace& rhs)
57+
{
58+
// `std::shared_ptr` does not have value semantics for its comparison
59+
// functions, so we need to check for nulls and compare the dereferenced
60+
// values here.
61+
if (lhs.pos != rhs.pos) {
62+
if (!lhs.pos)
63+
return true;
64+
if (!rhs.pos)
65+
return false;
66+
if (*lhs.pos != *rhs.pos)
67+
return *lhs.pos < *rhs.pos;
68+
}
69+
// This formats a freshly formatted hint string and then throws it away, which
70+
// shouldn't be much of a problem because it only runs when pos is equal, and this function is
71+
// used for trace printing, which is infrequent.
72+
return std::forward_as_tuple(lhs.hint.str(), lhs.frame)
73+
< std::forward_as_tuple(rhs.hint.str(), rhs.frame);
74+
}
75+
inline bool operator> (const Trace& lhs, const Trace& rhs) { return rhs < lhs; }
76+
inline bool operator<=(const Trace& lhs, const Trace& rhs) { return !(lhs > rhs); }
77+
inline bool operator>=(const Trace& lhs, const Trace& rhs) { return !(lhs < rhs); }
78+
5379
std::optional<LinesOfCode> AbstractPos::getCodeLines() const
5480
{
5581
if (line == 0)
@@ -185,6 +211,69 @@ static bool printPosMaybe(std::ostream & oss, std::string_view indent, const std
185211
return hasPos;
186212
}
187213

214+
void printTrace(
215+
std::ostream & output,
216+
const std::string_view & indent,
217+
size_t & count,
218+
const Trace & trace)
219+
{
220+
output << "\n" << "… " << trace.hint.str() << "\n";
221+
222+
if (printPosMaybe(output, indent, trace.pos))
223+
count++;
224+
}
225+
226+
void printSkippedTracesMaybe(
227+
std::ostream & output,
228+
const std::string_view & indent,
229+
size_t & count,
230+
std::vector<Trace> & skippedTraces,
231+
std::set<Trace> tracesSeen)
232+
{
233+
if (skippedTraces.size() > 0) {
234+
// If we only skipped a few frames, print them out normally;
235+
// messages like "1 duplicate frames omitted" aren't helpful.
236+
if (skippedTraces.size() <= 5) {
237+
for (auto & trace : skippedTraces) {
238+
printTrace(output, indent, count, trace);
239+
}
240+
} else {
241+
output << "\n" << ANSI_WARNING "(" << skippedTraces.size() << " duplicate frames omitted)" ANSI_NORMAL << "\n";
242+
// Clear the set of "seen" traces after printing a chunk of
243+
// `duplicate frames omitted`.
244+
//
245+
// Consider a mutually recursive stack trace with:
246+
// - 10 entries of A
247+
// - 10 entries of B
248+
// - 10 entries of A
249+
//
250+
// If we don't clear `tracesSeen` here, we would print output like this:
251+
// - 1 entry of A
252+
// - (9 duplicate frames omitted)
253+
// - 1 entry of B
254+
// - (19 duplicate frames omitted)
255+
//
256+
// This would obscure the control flow, which went from A,
257+
// to B, and back to A again.
258+
//
259+
// In contrast, if we do clear `tracesSeen`, the output looks like this:
260+
// - 1 entry of A
261+
// - (9 duplicate frames omitted)
262+
// - 1 entry of B
263+
// - (9 duplicate frames omitted)
264+
// - 1 entry of A
265+
// - (9 duplicate frames omitted)
266+
//
267+
// See: `tests/functional/lang/eval-fail-mutual-recursion.nix`
268+
tracesSeen.clear();
269+
}
270+
}
271+
// We've either printed each trace in `skippedTraces` normally, or
272+
// printed a chunk of `duplicate frames omitted`. Either way, we've
273+
// processed these traces and can clear them.
274+
skippedTraces.clear();
275+
}
276+
188277
std::ostream & showErrorInfo(std::ostream & out, const ErrorInfo & einfo, bool showTrace)
189278
{
190279
std::string prefix;
@@ -333,7 +422,13 @@ std::ostream & showErrorInfo(std::ostream & out, const ErrorInfo & einfo, bool s
333422

334423
bool frameOnly = false;
335424
if (!einfo.traces.empty()) {
425+
// Stack traces seen since we last printed a chunk of `duplicate frames
426+
// omitted`.
427+
std::set<Trace> tracesSeen;
428+
// A consecutive sequence of stack traces that are all in `tracesSeen`.
429+
std::vector<Trace> skippedTraces;
336430
size_t count = 0;
431+
337432
for (const auto & trace : einfo.traces) {
338433
if (trace.hint.str().empty()) continue;
339434
if (frameOnly && !trace.frame) continue;
@@ -343,14 +438,21 @@ std::ostream & showErrorInfo(std::ostream & out, const ErrorInfo & einfo, bool s
343438
break;
344439
}
345440

441+
if (tracesSeen.count(trace)) {
442+
skippedTraces.push_back(trace);
443+
continue;
444+
}
445+
tracesSeen.insert(trace);
446+
447+
printSkippedTracesMaybe(oss, ellipsisIndent, count, skippedTraces, tracesSeen);
448+
346449
count++;
347450
frameOnly = trace.frame;
348451

349-
oss << "\n" << "… " << trace.hint.str() << "\n";
350-
351-
if (printPosMaybe(oss, ellipsisIndent, trace.pos))
352-
count++;
452+
printTrace(oss, ellipsisIndent, count, trace);
353453
}
454+
455+
printSkippedTracesMaybe(oss, ellipsisIndent, count, skippedTraces, tracesSeen);
354456
oss << "\n" << prefix;
355457
}
356458

@@ -369,4 +471,5 @@ std::ostream & showErrorInfo(std::ostream & out, const ErrorInfo & einfo, bool s
369471

370472
return out;
371473
}
474+
372475
}

‎src/libutil/error.hh‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@
2525
#include <memory>
2626
#include <map>
2727
#include <optional>
28+
#include <compare>
2829

2930
#include <sys/types.h>
3031
#include <sys/stat.h>
@@ -88,6 +89,8 @@ struct AbstractPos
8889
std::optional<LinesOfCode> getCodeLines() const;
8990

9091
virtual ~AbstractPos() = default;
92+
93+
inline auto operator<=>(const AbstractPos& rhs) const = default;
9194
};
9295

9396
std::ostream & operator << (std::ostream & str, const AbstractPos & pos);
@@ -103,6 +106,11 @@ struct Trace {
103106
bool frame;
104107
};
105108

109+
inline bool operator<(const Trace& lhs, const Trace& rhs);
110+
inline bool operator> (const Trace& lhs, const Trace& rhs);
111+
inline bool operator<=(const Trace& lhs, const Trace& rhs);
112+
inline bool operator>=(const Trace& lhs, const Trace& rhs);
113+
106114
struct ErrorInfo {
107115
Verbosity level;
108116
hintformat msg;

‎tests/functional/lang/eval-fail-duplicate-traces.err.exp‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
error:
2+
… from call site
3+
at /pwd/lang/eval-fail-duplicate-traces.nix:9:3:
4+
8| in
5+
9| throwAfter 2
6+
| ^
7+
10|
8+
9+
… while calling 'throwAfter'
10+
at /pwd/lang/eval-fail-duplicate-traces.nix:4:16:
11+
3| let
12+
4| throwAfter = n:
13+
| ^
14+
5| if n > 0
15+
16+
… from call site
17+
at /pwd/lang/eval-fail-duplicate-traces.nix:6:10:
18+
5| if n > 0
19+
6| then throwAfter (n - 1)
20+
| ^
21+
7| else throw "Uh oh!";
22+
23+
… while calling 'throwAfter'
24+
at /pwd/lang/eval-fail-duplicate-traces.nix:4:16:
25+
3| let
26+
4| throwAfter = n:
27+
| ^
28+
5| if n > 0
29+
30+
… from call site
31+
at /pwd/lang/eval-fail-duplicate-traces.nix:6:10:
32+
5| if n > 0
33+
6| then throwAfter (n - 1)
34+
| ^
35+
7| else throw "Uh oh!";
36+
37+
… while calling 'throwAfter'
38+
at /pwd/lang/eval-fail-duplicate-traces.nix:4:16:
39+
3| let
40+
4| throwAfter = n:
41+
| ^
42+
5| if n > 0
43+
44+
error: Uh oh!

‎tests/functional/lang/eval-fail-duplicate-traces.nix‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
# Check that we only omit duplicate stack traces when there's a bunch of them.
2+
# Here, there's only a couple duplicate entries, so we output them all.
3+
let
4+
throwAfter = n:
5+
if n > 0
6+
then throwAfter (n - 1)
7+
else throw "Uh oh!";
8+
in
9+
throwAfter 2

‎tests/functional/lang/eval-fail-infinite-recursion-lambda.err.exp‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
error:
2+
… from call site
3+
at /pwd/lang/eval-fail-infinite-recursion-lambda.nix:1:1:
4+
1| (x: x x) (x: x x)
5+
| ^
6+
2|
7+
8+
… while calling anonymous lambda
9+
at /pwd/lang/eval-fail-infinite-recursion-lambda.nix:1:2:
10+
1| (x: x x) (x: x x)
11+
| ^
12+
2|
13+
14+
… from call site
15+
at /pwd/lang/eval-fail-infinite-recursion-lambda.nix:1:5:
16+
1| (x: x x) (x: x x)
17+
| ^
18+
2|
19+
20+
… while calling anonymous lambda
21+
at /pwd/lang/eval-fail-infinite-recursion-lambda.nix:1:11:
22+
1| (x: x x) (x: x x)
23+
| ^
24+
2|
25+
26+
… from call site
27+
at /pwd/lang/eval-fail-infinite-recursion-lambda.nix:1:14:
28+
1| (x: x x) (x: x x)
29+
| ^
30+
2|
31+
32+
(19997 duplicate frames omitted)
33+
34+
error: stack overflow; max-call-depth exceeded
35+
at /pwd/lang/eval-fail-infinite-recursion-lambda.nix:1:14:
36+
1| (x: x x) (x: x x)
37+
| ^
38+
2|

‎tests/functional/lang/eval-fail-infinite-recursion-lambda.nix‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
(x: x x) (x: x x)

0 commit comments

Comments
 (0)