Segfault when comparing infinite data structures

gaelan commented

2024-05-19 01:07:05 +00:00

Describe the bug

When comparing two infinitely nested data structures (and pointer equality doesn't suffice), Lix segfaults.

Steps To Reproduce

let a = rec { foo = [foo]; }; b = rec { foo = [foo]; }; in a == b

Causes Lix to segfault.

Expected behavior

If possible, define a result (I have no idea if there's a sensible argument to be made for either true or false, nor whether there's any way to efficiently determine this result). Otherwise, fail with a nice error instead of segfaulting.

`nix --version` output

nix (Lix, like Nix) 2.90.0-beta.1-lixpre20240506-b6799ab

Additional context

Inherited from Nix, present since at least 2022.

## Describe the bug When comparing two infinitely nested data structures (and pointer equality doesn't suffice), Lix segfaults. ## Steps To Reproduce ``` let a = rec { foo = [foo]; }; b = rec { foo = [foo]; }; in a == b ``` Causes Lix to segfault. ## Expected behavior If possible, define a result (I have no idea if there's a sensible argument to be made for either true or false, nor whether there's any way to efficiently determine this result). Otherwise, fail with a nice error instead of segfaulting. ## `nix --version` output nix (Lix, like Nix) 2.90.0-beta.1-lixpre20240506-b6799ab ## Additional context Inherited from Nix, present since at least 2022.

gaelan added the

bug

label 2024-05-19 01:07:05 +00:00

pennae commented

2024-05-23 19:25:33 +00:00

Owner

defining a result won't really be possible, but we should definitely limit recursion depth on comparisons (lix already does this for the evaluator itself, but comparisons themselves aren't subject to this yet). reusing the same stack depth limit we already have for eval should be fine, and give an obvious place to tune if anyfew run into this trapping.

qyriad added the

Area/evaluator

E/help wanted

labels 2024-05-24 21:24:19 +00:00

lulu-berlin commented

2024-10-07 04:35:01 +00:00

When I run either nix or lix with:

nix eval --expr 'let a = rec { foo = [foo]; }; b = rec { foo = [foo]; }; in a == b'

or do the same in nix repl, I get:

error: stack overflow (possible infinite recursion)

Is this what you mean by segfault?

When I run either `nix` or `lix` with: ```sh nix eval --expr 'let a = rec { foo = [foo]; }; b = rec { foo = [foo]; }; in a == b' ``` or do the same in `nix repl`, I get: ``` error: stack overflow (possible infinite recursion) ``` Is this what you mean by segfault?

jade commented

2024-10-07 04:42:42 +00:00

Owner

ah, Darwin not having the stack overflow detector strikes again. so yeah it's segfaulting due to infinite recursion, but it would be reasonably plausible to decide that after 1000 or 100 depth or something, the values are not going to become equal all of a sudden and return false.

as mentioned there is a recursion limit implemented in the evaluator. if you want to find the code i would suggest checking the 2.90 release notes in the manual (https://docs.lix.systems or in rl-2.90.md in the code in doc/manual/release-notes or so), it's mentioned in there with a link to the code change.

ah, Darwin not having the stack overflow detector strikes again. so yeah it's segfaulting due to infinite recursion, but it would be reasonably plausible to decide that after 1000 or 100 depth or something, the values are not going to become equal all of a sudden and return false. as mentioned there is a recursion limit implemented in the evaluator. if you want to find the code i would suggest checking the 2.90 release notes in the manual (https://docs.lix.systems or in rl-2.90.md in the code in doc/manual/release-notes or so), it's mentioned in there with a link to the code change.

pennae commented

2024-10-07 10:39:53 +00:00

Owner

it would be reasonably plausible to decide that after 1000 or 100 depth or something, the values are not going to become equal all of a sudden and return false.

big oof, no, if anything we should throw. the recursion limit currently only applies to function calls, not value comparisons; if we applied the recursion limit here too we'd naturally get an exception instead of a crash.

> it would be reasonably plausible to decide that after 1000 or 100 depth or something, the values are not going to become equal all of a sudden and return false. big oof, no, if anything we should throw. the recursion limit currently only applies to function calls, not value comparisons; if we applied the recursion limit here too we'd naturally get an exception instead of a crash.

lulu-berlin commented

2024-10-08 23:31:57 +00:00

I read through the code that was mentioned by @jade and found this Nix PR and this CL.

I would like to share my thoughts about how to approach this issue with regards to infinitely nested attrsets and ask for your feedback:

This issue affects the evaluation of == and !=. I'm guessing that it's because EvalState::eqValues calls itself recursively if v1 and v2 are both non-derivation attrsets for each attribute that has the same name (line 2510):

         case nAttrs: {
             /* If both sets denote a derivation (type = "derivation"),
                then compare their outPaths. */
             if (isDerivation(v1) && isDerivation(v2)) {
                 Bindings::iterator i = v1.attrs->find(sOutPath);
                 Bindings::iterator j = v2.attrs->find(sOutPath);
                 if (i != v1.attrs->end() && j != v2.attrs->end())
                     return eqValues(*i->value, *j->value, pos, errorCtx);
             }
             if (v1.attrs->size() != v2.attrs->size()) return false;
             /* Otherwise, compare the attributes one by one. */
             Bindings::iterator i, j;
             for (i = v1.attrs->begin(), j = v2.attrs->begin(); i != v1.attrs->end(); ++i, ++j)
                 if (i->name != j->name || !eqValues(*i->value, *j->value, pos, errorCtx))
                     return false;
             return true;
         }

I tried to see if any other attrset operation (like //) has a similar effect and it doesn't seem to be the case.
So to follow the same approach of handling infinite recursion in function calls, we should probably have a depth counter in EvalState, maybe attrEqDepth? Then the counter should be incremented every time we reach the case of evaluating the equality of non-derivation attrsets quoted above. Before incrementing it, we can check if attrEqDepth exceeded evalSettings.maxAttrEqDepth and throw an exception ("stack overflow: max-attr-eq-depth exceeded") with a stack trace.
This can then be tested with a functional test, just like tests/functional/lang/eval-fail-infinite-recursion-lambda.nix.

What do you think?

I read through the code that was mentioned by @jade and found [this Nix PR](https://github.com/NixOS/nix/pull/9617) and [this CL](https://gerrit.lix.systems/c/lix/+/205). I would like to share my thoughts about how to approach this issue with regards to infinitely nested attrsets and ask for your feedback: - This issue affects the evaluation of `==` and `!=`. I'm guessing that it's because `EvalState::eqValues` calls itself recursively if `v1` and `v2` are both non-derivation attrsets for each attribute that has the same name (line 2510): https://git.lix.systems/lix-project/lix/src/commit/0012887310f24283e8a9ca08e0c2a49219ea4ff5/src/libexpr/eval.cc#L2495-L2514 - I tried to see if any other attrset operation (like `//`) has a similar effect and it doesn't seem to be the case. - So to follow the same approach of handling infinite recursion in function calls, we should probably have a depth counter in `EvalState`, maybe `attrEqDepth`? Then the counter should be incremented every time we reach the case of evaluating the equality of non-derivation attrsets quoted above. Before incrementing it, we can check if `attrEqDepth` exceeded `evalSettings.maxAttrEqDepth` and throw an exception ("stack overflow: max-attr-eq-depth exceeded") with a stack trace. - This can then be tested with a functional test, just like `tests/functional/lang/eval-fail-infinite-recursion-lambda.nix`. What do you think?

jade commented

2024-10-09 01:00:57 +00:00

Owner

hmmm. is there a reason why we would have to keep this as part of EvalState rather than as a parameter to eqValues? If it's that it has to conform to some signature we can make it a wrapper over a function that takes it as a parameter. I don't like non-reentrant state where avoidable.

I don't think that equality comparison should ever hit any other parts of the evaluator such that it would have to be passed elsewhere, so it should be possible to make a parameter.

hmmm. is there a reason why we would have to keep this as part of `EvalState` rather than as a parameter to eqValues? If it's that it has to conform to some signature we can make it a wrapper over a function that takes it as a parameter. I don't like non-reentrant state where avoidable. I don't *think* that equality comparison should ever hit any other parts of the evaluator such that it would have to be passed elsewhere, so it *should* be possible to make a parameter.

lulu-berlin commented

2024-10-09 01:20:21 +00:00

Good idea! :)
I'm all for it. I'll add a parameter with a default value of 0 for the external callers.

It's probably still good to have an evalSettings.maxAttrEqDepth for setting the boundary, right?

Good idea! :) I'm all for it. I'll add a parameter with a default value of 0 for the external callers. It's probably still good to have an `evalSettings.maxAttrEqDepth` for setting the boundary, right?

lulu-berlin commented

2024-10-09 01:28:38 +00:00

Another question is whether I should check the boundary at the beginning of the function or right before the recursive call.

I think that performance-wise, it would be better to make the check before the recursive call so that in most cases it can be skipped.

Another question is whether I should check the boundary at the beginning of the function or right before the recursive call. I think that performance-wise, it would be better to make the check before the recursive call so that in most cases it can be skipped.

jade commented

2024-10-09 01:55:46 +00:00

Owner

Good idea! :)
I'm all for it. I'll add a parameter with a default value of 0 for the external callers.

Yup, was my thought. Don't even need any fancy state, just add one to it when you recurse.

It's probably still good to have an evalSettings.maxAttrEqDepth for setting the boundary, right?

I think it's probably reasonable that it uses the same depth limit setting as we use for the rest of the language so there's just one knob.

As to when to check it, it should not cause a perf problem to do it right at the start because branch predictors exist and will ignore it. If you're worried you can probably put an unlikely annotation on the if statement, but I don't think this code is terribly hot to begin with. I think we recurse in a couple of places so it's going to be slightly easier to maintain if we only have one check.

> Good idea! :) > I'm all for it. I'll add a parameter with a default value of 0 for the external callers. Yup, was my thought. Don't even need any fancy state, just add one to it when you recurse. > It's probably still good to have an `evalSettings.maxAttrEqDepth` for setting the boundary, right? I think it's probably reasonable that it uses the same depth limit setting as we use for the rest of the language so there's just one knob. As to when to check it, it should not cause a perf problem to do it right at the start because branch predictors exist and will ignore it. If you're worried you can probably put an unlikely annotation on the if statement, but I don't think this code is terribly hot to begin with. I think we recurse in a couple of places so it's going to be slightly easier to maintain if we only have one check.

lulu-berlin commented

2024-10-09 21:29:26 +00:00

I've just tried it with a low hard-coded callDepth boundary of 10:

    // Limit the nesting level depth when comparing attribute sets to avoid infinite recursion.
    if (callDepth > 10uz)
        error<EvalError>("stack overflow; max-call-depth exceeded").atPos(pos).debugThrow();

and while it works with:

nix-repl> a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = []; }; }; }; }; }; }; }; }; }; }; }

nix-repl> b = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = []; }; }; }; }; }; }; }; }; }; }; }

nix-repl> a == b
error: stack overflow; max-call-depth exceeded
       at «string»:1:3:
            1| a == b
             |   ^

it doesn't work with infinitely nested recursive attribute sets, like the example at the top of the issue.

It simply aborts with:

error: stack overflow (possible infinite recursion)

I need to investigate further why it's not working with infinitely nested recursive attribute sets.

I've just tried it with a low hard-coded `callDepth` boundary of `10`: ```cpp // Limit the nesting level depth when comparing attribute sets to avoid infinite recursion. if (callDepth > 10uz) error<EvalError>("stack overflow; max-call-depth exceeded").atPos(pos).debugThrow(); ``` and while it works with: ```nix nix-repl> a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = []; }; }; }; }; }; }; }; }; }; }; } nix-repl> b = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = { a = []; }; }; }; }; }; }; }; }; }; }; } nix-repl> a == b error: stack overflow; max-call-depth exceeded at «string»:1:3: 1| a == b | ^ ``` it doesn't work with infinitely nested recursive attribute sets, like the example at the top of the issue. It simply aborts with: ``` error: stack overflow (possible infinite recursion) ``` I need to investigate further why it's not working with infinitely nested recursive attribute sets.

lulu-berlin commented

2024-10-10 11:32:06 +00:00

Ok, this was silly. I figured it out. I only incremented callDepth for nested attributes sets, but not for nested lists... The example had rec { foo = [foo]; } so it's nesting attrset -> list -> attrset -> list -> ...

Ok, this was silly. I figured it out. I only incremented `callDepth` for nested attributes sets, but not for nested lists... The example had `rec { foo = [foo]; }` so it's nesting attrset -> list -> attrset -> list -> ...

Segfault when comparing infinite data structures #330

Describe the bug

Steps To Reproduce

Expected behavior

nix --version output

Additional context

`nix --version` output