Ban integer overflow in the Nix language#11188
Conversation
ff3442d to
f5bcbf5
Compare
|
@lf- You can fix the format issues like this: |
roberth
left a comment
There was a problem hiding this comment.
Suggestions for the reference documentation.
Or |
50954d9 to
0b1d6f3
Compare
| auto & v = check_value_in(value); | ||
| assert(v.type() == nix::nInt); | ||
| return v.integer(); | ||
| return v.integer().value; |
There was a problem hiding this comment.
Can't v.integer() return NixInt::Inner? It would make the diff a lot smaller.
Alternatively, there could be an implicit conversion from NixInt to NixInt::Inner.
There was a problem hiding this comment.
This is deliberately explicit so that it's impossible to deal with values originating from user code without doing safe arithmetic.
Without this deliberate break, I would not have caught the broken JSON conversions from uint64_t and others.
There was a problem hiding this comment.
I like that, but it isn't quite obvious at the usage sites.
Should it be .integer().toUnchecked()?
|
Thank you very much @lf- for porting this over to us! I really appreciate it. |
This comment was marked as outdated.
This comment was marked as outdated.
Sorry, something went wrong.
The actual motive here is the avoidance of integer overflow if we were to make these use checked NixInts and retain the subtraction. However, the actual *intent* of this code is a three-way comparison, which can be done with operator<=>, so we should just do *that* instead. Change-Id: I7f9a7da1f3176424b528af6d1b4f1591e4ab26bf
This is in preparation for adding checked arithmetic to the evaluator. Change-Id: I6e115ce8f5411feda1706624977a4dcd5efd4d13
This also bans various sneaking of negative numbers from the language into unsuspecting builtins as was exposed while auditing the consequences of changing the Nix language integer type to a newtype. It's unlikely that this change comprehensively ensures correctness when passing integers out of the Nix language and we should probably add a checked-narrowing function or something similar, but that's out of scope for the immediate change. During the development of this I found a few fun facts about the language: - You could overflow integers by converting from unsigned JSON values. - You could overflow unsigned integers by converting negative numbers into them when going into Nix config, into fetchTree, and into flake inputs. The flake inputs and Nix config cannot actually be tested properly since they both ban thunks, however, we put in checks anyway because it's possible these could somehow be used to do such shenanigans some other way. Note that Lix has banned Nix language integer overflows since the very first public beta, but threw a SIGILL about them because we run with -fsanitize=signed-overflow -fsanitize-undefined-trap-on-error in production builds. Since the Nix language uses signed integers, overflow was simply undefined behaviour, and since we defined that to trap, it did. Trapping on it was a bad UX, but we didn't even entirely notice that we had done this at all until it was reported as a bug a couple of months later (which is, to be fair, that flag working as intended), and it's got enough production time that, aside from code that is IMHO buggy (and which is, in any case, not in nixpkgs) such as https://git.lix.systems/lix-project/lix/issues/445, we don't think anyone doing anything reasonable actually depends on wrapping overflow. Even for weird use cases such as doing funny bit crimes, it doesn't make sense IMO to have wrapping behaviour, since two's complement arithmetic overflow behaviour is so *aggressively* not what you want for *any* kind of mathematics/algorithms. The Nix language exists for package management, a domain where bit crimes are already only dubiously in scope to begin with, and it makes a lot more sense for that domain for the integers to never lose precision, either by throwing errors if they would, or by being arbitrary-precision. Fixes: NixOS#10968 Original-CL: https://gerrit.lix.systems/c/lix/+/1596 Change-Id: I51f253840c4af2ea5422b8a420aa5fafbf8fae75
Change-Id: Ie8a1b31035f2d27a220e5df2e9e178ec3b39ee68
Change-Id: Ib75ab5b8b4d879035d7ee7678f9cd0c491a39c0a
0b1d6f3 to
5878b14
Compare
|
From the maintainer team meeting: We'll postpone merging to after the 2.24 release. |
|
Here are the benchmarks of this change: I fussed around with it a bunch in vtune, and as far as I can tell, the reason for the 0.2-0.7% negligible impact is probably just code size or cache fiddliness. The only actually remotely hot part of it is in Also I have learned that zfs on Linux is extraordinarily bad for stable benchmark execution times; this is from a non-zfs machine and it just worked without any outliers. |
2.24 released :P |
|
I tested this PR against this expression, which is known as Tower of Hanoi: hanoi/default.nixlet
digits = 15;
# Move the last digit from a to b
move =
{ src, dest }:
{
src = src / digits;
dest = if src == 0 then dest else dest * digits + src - (src / digits) * digits;
};
step =
{
i,
a,
b,
c,
}:
if i == 1 then
let
moved = move {
src = a;
dest = b;
};
in
{
a = moved.src;
b = moved.dest;
inherit c;
}
else
let
step1 = step {
i = i - 1;
inherit a;
b = c;
c = b;
};
step2 = move {
src = step1.a; # a
dest = step1.b; # c
};
step3 = step {
i = i - 1;
a = step1.c; # b
b = step2.src; # a
c = step2.dest; # c
};
in
step3;
gen = i: result: if i == 0 then result else gen (i - 1) (digits * result + i);
question =
i:
step {
inherit i;
a = gen i 0;
b = 0;
c = 0;
};
in
question 1414 is chosen because any numbers larger will cause a |
|
I also did a 20,000 lines of random addition/subtraction of two-digits random numbers, which is also almost impossible to tell the difference between the two |
|
I believe this can be merged now that 2.24 is out? |
|
Hi there, @lf- the author and Nix maintainers, I changed my mind, the performance impact seems to be very minimal because indeed the Nix evaluator itself does not have much integer computing in comparison to native languages (as the profiling shows). I apologize for my previous comment. My professional experience includes optimizing native language compilers, where we've long considered factors like sanitizers, wrapping, and undefined behavior. However, the intuitions I've developed for those languages don't apply to Nix as they actually do not share the hot path. |
|
Can you please apply the desired changes when merging it? I don't feel like fighting git today, and I am out of energy for porting this to CppNix (it has taken 10 times the round trip latency and several times the energy as my average Lix change). |
|
This pull request has been mentioned on NixOS Discourse. There might be relevant details there: |
|
So, this has made doing bitshift operations in Nix much harder; c.f. #10387 and oddlama/nixos-extra-modules#1 |
Motivation
Fixes #10968.
Context
You can review this by looking through it commit-by-commit since that was its original form and it is intended to be read that way.
This is approximately this stack from Lix: https://gerrit.lix.systems/c/lix/+/1597 (with its parents lower in the list), with the following after-the-fact oopsie fixes added into the commits themselves:
Priorities and Process
Add 👍 to pull requests you find important.
The Nix maintainer team uses a GitHub project board to schedule and track reviews.