LWN: Comments on "Rust for Linux redux"

"anything moved from Rust into C++"

tialaramex — Wed, 11 Aug 2021 02:14:01 +0000

> which is why I'd assume it is `FnMut`: so it can "remember" such things

I expect it's FnMut because the standard advice is to choose callable trait bounds in order of preference: FnOnce, FnMut, Fn. By using the broadest bounds in this case, and the narrowest bounds when writing functions or closures, you promote re-usability.

Since we can expect to call this more than once FnOnce isn't viable, so FnMut is next best. However although I did write an implementation to check it's actually possible to implement e.g. a closure that matches various couples kissing in Unicode but not anything else it was rather awkward to do this, and I don't anticipate such uses predominating. Instead I expect that once Pattern stabilizes people will write adaptors to make Patterns out of other things you could plausibly want.

Rust for Linux redux

mkru — Thu, 29 Jul 2021 05:18:10 +0000

Compiling for platforms with and without CheriABI still will be possible.
The old hardware will be replaced by the new one, probably slowly, but still, it will.
I guess you mean that people with older hardware want to be sure that they kernel is safe.
As Linux is considering adding Rust as the second language, I guess someone has counted how many bugs it would help to avoid in the last X years.
Does anyone know where such report is available?

Rust for Linux redux

mpr22 — Wed, 28 Jul 2021 18:42:14 +0000

Remember that even once devices with CHERI support enter the market, there will remain a large installed base of non-CHERI devices that people want to run the Linux kernel on.

"anything moved from Rust into C++"

mathstuf — Wed, 28 Jul 2021 14:01:35 +0000

Agh. I got terms confused. `u8` is the "code unit" of UTF-8. Yes, scalars are code points. *face palm*

> (But I believe you're right that what a human would perceive as "a character" is what Unicode calls an extended grapheme cluster, which is (confusingly) a sequence of Rust chars. The name "char" seems like a bad decision by Rust - e.g. Go uses "rune" as the type for code points, which is a bit weird but is much less misleading. And Rust doesn't natively handle grapheme clusters at all, you need a third-party crate for that, unlike e.g. Swift where String is defined as a sequence of Characters and Character is defined as a grapheme cluster (and you have to use non-default APIs if you want access to a String's Unicode Scalar Values or its UTF-8 code units).)

I think Rust got it right keeping grapheme clusters out of the language proper. What sequence of code points constitutes a grapheme cluster changes from standard to standard as new codepoints and rules for combining are added. For example, `<person><join><heart><join><person>` is now a single grapheme cluster, but wasn't in older versions of Unicode. Unless languages are tacking on `Unicode_12_0` on their `grapheme_length()` methods, it means that as the language updates its tables for newer standards, these methods can change their minds depending on what combinations are newly allowed.

Yes, `char` is not the greatest name, `upoint` may have been better (as `unicode_point` is too long). However, I think `rune` is also poor since that brings to my mind "grapheme (cluster)" more than "code point".

"anything moved from Rust into C++"

excors — Wed, 28 Jul 2021 13:36:43 +0000

> Just to nitpick, `u8` is the UTF-8 scalar (the smallest unit of the data stream). Rust's `char` is a codepoint (which may have come from multiple scalars).

Just to nitpick further, I think that's entirely wrong :-) . The Rust documentation says char is a Unicode Scalar Value, which Unicode defines as "Any Unicode code point except high-surrogate and low-surrogate code points", i.e. it's not the same as a code point. And u8 is not a specifically UTF-8 type - it's just an unsigned 8-bit integer, which happens to match the definition of a UTF-8 code unit (which nobody ever calls a "UTF-8 scalar").

(But I believe you're right that what a human would perceive as "a character" is what Unicode calls an extended grapheme cluster, which is (confusingly) a sequence of Rust chars. The name "char" seems like a bad decision by Rust - e.g. Go uses "rune" as the type for code points, which is a bit weird but is much less misleading. And Rust doesn't natively handle grapheme clusters at all, you need a third-party crate for that, unlike e.g. Swift where String is defined as a sequence of Characters and Character is defined as a grapheme cluster (and you have to use non-default APIs if you want access to a String's Unicode Scalar Values or its UTF-8 code units).)

Rust for Linux redux

mkru — Wed, 28 Jul 2021 13:11:10 +0000

I am not a kernel developer, but I have written a few simple drivers.
I am wondering whether adding Rust to the kernel is really the best approach for achieving memory safety.
There is (maybe are?) other alternative solution that is not yet available, but is on the horizon and seems to be much more inline with the C and how OS'es are implemented.
Namely, the CheriABI.

Rust is relatively complex language, adding it to the kernel will greatly increase cognitive complexity.
Imagine 2 alternative scenarios:
1. C + compiler warnings + CheriABI + a larger number of potential reviewers.
2. Rust.

How many errors/vulnerabilities can 2 help to avoid comparing to 1?
Is anyone able to estimate this?
Is greatly increasing the complexity still worth?

https://www.cl.cam.ac.uk/research/security/ctsrd/cheri/
https://dl.acm.org/doi/10.1145/3297858.3304042
https://www.cl.cam.ac.uk/research/security/ctsrd/pdfs/202...

"anything moved from Rust into C++"

mathstuf — Wed, 28 Jul 2021 12:57:40 +0000

> a particular Unicode scalar (approximately a single code point, so a Poop emoji or the capital A, but not a flag or two women kissing) is a match that'll let you ask whether a string.contains(it) or string.ends_with(it) or just to string.find(it) and these all work today.

Just to nitpick, `u8` is the UTF-8 scalar (the smallest unit of the data stream). Rust's `char` is a codepoint (which may have come from multiple scalars). What users see as a single grapheme (or grapheme cluster) may have come from multiple codepoints (including flags or the "two+ people" emoji). So that pattern function can "see" `A` alone, but is going to see a decomposed `á` as `a` and a combining character since it is two codepoints (which is why I'd assume it is `FnMut`: so it can "remember" such things).

Rust for Linux redux

tialaramex — Wed, 28 Jul 2021 03:53:01 +0000

In the end I don't think I'd want it here because you are making several of them but rarely need the actual type, but arguably

type Block = [u8; BLOCK_LEN];

makes it clearer since that's in fact what this is, and then:

let mut parents_array = ArrayVec::<&Block, MAX_SIMD_DEGREE_OR_2>::new();

... feels like a pretty reasonable type, it's an ArrayVec of references to Blocks, right you are. Const generics helped more though.

"anything moved from Rust into C++"

tialaramex — Wed, 28 Jul 2021 03:36:41 +0000

Why would such a claim "make all subsequent statements suspect" when it seems to be a very reasonable position?

The shortest path wouldn't be through Rust, but lots of key C++ people have exposure to stuff that they could in principle have seen somewhere else earlier but ended up learning in Rust because of Rust's popularity.

Take P2216. Rather modestly this proposal suggested that, since languages such as Rust treat nonsensical formats as a compile time error, rather than waiting until your code runs before inevitably complaining that the format is nonsense C++ could match the state of the art in this area and refuse to compile the program.

Did Rust _invent_ this practice? No of course not. But, in C++ 20 (as originally shipped) the nonsense compiled, and in Rust it did not, the author and Library Evolution Working Group both saw that this is obviously superior, and so it was accepted for C++ 23 and "backported" into the standard library specification. P2216 doesn't try to find out historically which postgraduate student first wrote a program that could do this, perhaps in 1985 in Lisp, it just points out that today Rust is a popular language that gets this right and C++ should join it.

Or P1679. Once again, Rust doesn't take centre stage here, the author merely acknowledges that "Bananas".contains("nanas") exists in Rust† whereas in C++ you were expected to construct a string or string_view and then run find("nanas") and confirm the result is npos. Which, if you come from any language (not just Rust) with "Bananas".contains("nanas") seems silly. Why am I paying the cognitive price of a find method I don't need when all I wanted to do was check whether one thing is contained in another ?

† Behind the scenes something clever is happening here. Today the C++ 23 feature is a bunch of overloads on string and string_view and so on. But the Rust feature isn't, it's relying on an (unstable for now) Trait named std::str::pattern::Pattern. If a future standard C++ adds any more things you might reasonably expect to be parameters for string.contains() they'll be additional overloads. That isn't inherited by your own string-like classes, you too will need to add the overloads explicitly, likewise if you currently add overloads to string.find() for your own needs, you'll want to add the same overloads to string.contains() for symmetry.

But thanks to Pattern in Rust both those things happen for free when you simply use Pattern. For example Rust already provided an implementation of Pattern for any F: FnMut(char) -> bool -- and so, if you write any function or closure that can decide whether a particular Unicode scalar (approximately a single code point, so a Poop emoji or the capital A, but not a flag or two women kissing) is a match that'll let you ask whether a string.contains(it) or string.ends_with(it) or just to string.find(it) and these all work today.

Footguns

farnz — Tue, 27 Jul 2021 13:40:06 +0000

Different to taint mode - taint in Perl attaches to data, not operations. Perl's taint says "this data is from the user and therefore untrusted until sanitised" (even if minimally sanitised). Rust's unsafe says "this operation has human-checked invariants that can result in UB if not correctly checked".

You can implement Perl's taint system easily in Rust, with a struct Tainted<T>(T) expressing that it holds tainted data, and some way to extract the tainted data and feed it back to the rest of the program. You can't implement unsafe easily in Perl 5, because Perl does not have the same ability to represent a function that breaks the abstract machine's invariants if misapplied.

Footguns

flussence — Tue, 27 Jul 2021 13:14:36 +0000

But that's just a thing akin to Perl's taint mode, right? I wouldn't call it a new capability.

Rust for Linux redux

mathstuf — Mon, 26 Jul 2021 16:23:57 +0000

Yes, that was the "mergable PEP" I was referring to. Weren't there prior attempts for similar things that went nowhere or am I crossing signals in my memory?

Rust for Linux redux

oconnor663 — Mon, 26 Jul 2021 14:21:52 +0000

Hi, I wrote that code. So here's a bunch of Rust details that no one asked for :) This is the starting example (https://github.com/BLAKE3-team/BLAKE3/blob/0.1.0/src/lib....):

let mut parents_array = ArrayVec::<[&[u8; BLOCK_LEN]; MAX_SIMD_DEGREE_OR_2]>::new();

A couple pieces of punctuation in that example comes from the fact that prior to the release of Rust 1.51 this March, Rust didn't properly support const generics. So types like ArrayVec needed to work around that with shenanigans. But now that we do have const generics and an updated version of ArrayVec, the code looks like this (https://github.com/BLAKE3-team/BLAKE3/blob/1.0.0/src/lib....):

let mut parents_array = ArrayVec::<&[u8; BLOCK_LEN], MAX_SIMD_DEGREE_OR_2>::new();

That is, an "ArrayVec of at most MAX_SIMD_DEGREE_OR_2 elements, each of type 'reference to a byte array of length BLOCK_LEN'". One interesting thing to notice here is that the element type is actually optional. This will also compile (and would have in v0.1.0 too):

let mut parents_array = ArrayVec::<_, MAX_SIMD_DEGREE_OR_2>::new();

That is, an "ArrayVec of at most MAX_SIMD_DEGREE_OR_2 elements, each of some type that's deduced by the compiler." I chose to write the full type out explicitly, because this is highly optimized code doing tricky things, and I think this version is actually easier to understand for someone who's familiar with Rust. But opinions can definitely differ here.

Another thing to think about is that in C, this might have been just "char**". What all this extra typing is buying us in Rust, is that the function is 100% memory safe. (It's going to call some SIMD code that isn't, but ignore that for now.) Even though the ArrayVec is variable-length, it's still allocated on the stack, and pushes into it are guaranteed to panic rather than overrunning its stack footprint. The array pointers inside it are also length checked during construction by array_ref!() in the code below. (Which I would probably replace with standard .try_into() if I was refactoring this code today.)

Another source of punctuation woes in Rust is lifetime annotations. I think it's interesting to notice that we don't see any of those here. The compiler doesn't need any help to figure out that parents_array is scoped to the current function, so putting array pointers inside of it isn't going to cause problems. But if we wanted to say return that array, we would need explicit lifetime annotations in the function signature in this case.

Rust for Linux redux

smurf — Mon, 26 Jul 2021 08:01:19 +0000

> Pattern-matching […] (or into a mergable PEP for Python for that matter).

Huh? PEP 634 has been merged into what's going to be 3.10 since February 26th, commit 145bf26.

Rust for Linux redux

mathstuf — Sun, 25 Jul 2021 20:45:12 +0000

> The code can be found here: https://docs.rs/blake3/0.1.0/src/blake3/lib.rs.html which is the official implementation of BLAKE3 in Rust. Take of that what you will. We will see what kind of Rust code you are going to find in the Linux kernel.

Hmm. Well, I found `parents_array` at least. Not *quite* sure why it needs to be specified there (possibly the length?), but type aliases would certainly make it much more readable IMO.

As for `input_ptrs`, that is deep in AVX2 code…so yeah, that's probably going to get a bit hairy (and, indeed, has a comment about its safety).

Either way, given the *other* restrictions on code such as this, it's not where I'd look for "normal" Rust code (unless I was coding up replacements for the sections doing similar machinations in the kernel today).

> Perhaps a recent one would have served you better, then.

I used the post you linked to… Which, FWIW, I had actually read in the last week, though I missed that it was from 2019 (IIRC, it was from a link on HN or somewhere). Either case, yes, Ada is older than Rust. I'm not doubting that. I'm doubting the "Ada finally has pointers!" would have happened without Rust showing how to do lifetime tracking without runtime overhead:

> I think it was work on the ParaSail language, and the emergence of the Rust language, that first made us look again into supporting this feature. Pointer ownership models did not appear explicitly within Rust, but Rust made the restrictions associated with them look tractable, and maybe even desirable from a safety point of view.

makes it seem like Rust is what made the SPARK team look at doing more rigorous pointer lifetime analysis. Later:

> But this is not great, as now I have a memory leak. Indeed, the value previously stored in My_Dictionary is no longer accessible and it has not been deallocated. The SPARK tool does not currently complain about this problem, even though the SPARK definition says it should (it has not been implemented yet).

> But this is not supported yet by the proof tool, as it raises the complex issue of tracking modifications of X that were done through Y during its lifetime:

So maybe these things are complete, but links to further progress would be helpful.

Rust for Linux redux

mpr22 — Sun, 25 Jul 2021 19:28:32 +0000

Looking at both of those things for a few minutes:

It appears that the Ada Kernel Module Framework only exists as a proof of concept, and has not been the target of any publicly visible work in the original github repository or the two visible github forks.

EwoK looks like it may well be quite an interesting project, but it's 100% its own thing and nothing to do with the Linux kernel.

Rust for Linux redux

joshc — Sun, 25 Jul 2021 18:19:33 +0000

A quick search tells me that such a thing exists for Ada.

Source code: https://github.com/alkhimey/Ada_Kernel_Module_Framework
Blog posts can be found here: http://www.nihamkin.com/tag/kernel.html

I do not believe that it uses SPARK though. You might want to check out https://wookey-project.github.io/ewok/ada_spark.html for something like that.

Rust for Linux redux

Coconut — Sun, 25 Jul 2021 18:19:20 +0000

Thanks, that answers my question.

Rust for Linux redux

Coconut — Sun, 25 Jul 2021 18:19:15 +0000

> Neither of these look like idiomatic code at all.

The code can be found here: https://docs.rs/blake3/0.1.0/src/blake3/lib.rs.html which is the official implementation of BLAKE3 in Rust. Take of that what you will. We will see what kind of Rust code you are going to find in the Linux kernel.

> Interesting how "cannot store pointers in structures" is considered suitable for "no longer an issue" in something like the kernel. That is still under active research and/or implementation by my reading of that post.

Perhaps a recent one would have served you better, then.

> so how would that have worked out before Rust came onto the scene?

How can you comment on this and the previous one with so much certainty if you have seemingly have not done your research? I obviously omitted a lot of information on Ada/SPARK. I am not supposed to sell it to you. That is not the point of the comment. I just wanted to know if Ada has been ever considered given that it is *perfectly suitable* for kernel development and is actually more safe than Rust (yes, it actually is, perhaps go through all of my links, then). To answer your question: they were actually working on it before Rust.

> I think the Linux kernel is about as interested in crates.io as they are about PyPI.

I mentioned it because it is a common reaction from people that "Ada is not modern, it does not even have a package manager!".

Rust for Linux redux

mathstuf — Sun, 25 Jul 2021 13:49:17 +0000

I suspect you're talking about the standards level, but implementations have definitely been paying attention (see the MSVC post in the sibling comment). However, to say that Rust is not exerting some pressure on C++ is to ignore what is happening.

The epochs proposal[1] was directly inspired by Rust's edition mechanism to allow for syntactic evolution of the language without breaking everything. Unfortunately, C++ has semantics tied too tightly to the syntax that even deprecating `0` or `NULL` for `nullptr` is a no-go due to ADL, type coercion, and confused template rules. While it'd be a nice thing to be able to bundle up terrible promotion rules to specific modules, the way that templates expand mean that you need to decide whether to evaluate them with the declaration's epoch rules or the instantiator's epoch rules because concepts care quite a bit about whether specific syntactic constructions are valid. Getting implementations to warn "under epoch X, we find that type deduction and ADL take a different path because `0` no longer converts to `T*` silently" is not something anyone is going to want to handle. Either "no one" updates to the new epoch because their codebase is not clean under `clang-tidy`'s "modernize-*" lints or only new code uses it because it's an error for them anyways.

Pattern-matching calls out Rust as a language to compare C++'s proposals against and is also called out for how to issue warnings due to incomplete matching. Pattern matching has been around since "forever" with various ML languages, but I wouldn't be surprised if Rust's success with it was the "oomph" that ignited the interest of it enough to actually get it in front of the committee for C++ (or into a mergable PEP for Python for that matter).

I'm sure there are other Rust-inspired proposals around, but I suspect a number of them are in the library track (which I don't have time to follow).

[1] http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p...

Rust for Linux redux

mathstuf — Sun, 25 Jul 2021 13:34:10 +0000

> Have they considered Ada/SPARK?

The Linux kernel was not "seeking" a new language to add. Developers did the work and showed how Rust could be used in it and *then* came to the kernel. Where was this done for Ada/SPARK for "them" to consider?

> let mut parents_array = ArrayVec::<[&[u8; BLOCK_LEN]; MAX_SIMD_DEGREE_OR_2]>::new()
> let input_ptrs: &[*const u8; DEGREE] = &*(inputs.as_ptr() as *const [*const u8; DEGREE]);

Sure, syntactically, all kinds of abominations are possible. Crafting a grammar to only accept "beautiful" code is likely a doomed endeavour for any "useful" language. Neither of these look like idiomatic code at all. The former because the type is probably deduced elsewhere by what APIs accept `parents_array` (or, if not, that `[u8; BLOCK_LEN]` deserves its own type name; as does the `MAX_SIMD_DEGREE_OR_2`-sized array) so you end up with either:

let mut parents_array = ArrayVec::new();
// parents_array.push(&simd_blocks); // type deduced here

or:

let mut parents_array = ArrayVec::<SimdBlockRefs>::new();

The latter `input_ptrs` is not idiomatic because it is desperately in need of an `unsafe` specifier and a comment describing what it does is safe. Slinging around an array of pointers is also not very Rust-like. The need for casts on the right and left side is also just weird…type deduction should make the left-hand type unnecessary (ignoring the unsafe-ness being presented).

> Plus, pointers are no longer an issue either: https://blog.adacore.com/using-pointers-in-spark.

Interesting how "cannot store pointers in structures" is considered suitable for "no longer an issue" in something like the kernel. That is still under active research and/or implementation by my reading of that post. And, without Rust, Ada/SPARK might still be without pointers, so how would that have worked out before Rust came onto the scene?

> I would also like to add, that Ada has a package manager as well, namely Alire

I think the Linux kernel is about as interested in crates.io as they are about PyPI. Handy, but almost zero code there is suitable for usage in the kernel's context (except for usage in build-time or other useful tools *related* to the kernel).

Rust for Linux redux

rahulsundaram — Sun, 25 Jul 2021 12:32:26 +0000

> To suggest that anything moved from Rust into C++ makes all subsequent statements suspect, thus >probably not even worth reading.

https://devblogs.microsoft.com/cppblog/new-safety-rules-i...

"C++ often falls behind Rust when it comes to programming safety. Visual Studio 2019 version 16.7 contains four new rules in C++ Core Check to incorporate some safety features from Rust into C++."

Rust for Linux redux

mpr22 — Sun, 25 Jul 2021 09:47:47 +0000

> Check them out. After you are done, can you tell me why Rust over Ada/SPARK?

Because Rust advocates were willing to do the work (including the non-technical work of persuading the likes of Linus and Greg that their proposal is worthy of consideration at all), and Ada/SPARK advocates have apparently not been willing to do the work.

Of course, I'd be surprised if the average Ada/SPARK advocate was interested in touching the Linux kernel in the first place (at least without a hazmat suit and long-handled tongs).

Rust for Linux redux

ncm — Sun, 25 Jul 2021 02:54:17 +0000

To suggest that anything moved from Rust into C++ makes all subsequent statements suspect, thus probably not even worth reading.

Especially, C++ Concepts predate even the first proposal of Rust as a project.

Rust for Linux redux

Coconut — Sun, 25 Jul 2021 02:27:05 +0000

Have they considered Ada/SPARK? If they did, why did they decide against it and pick Rust over it? Ada/SPARK provides all the safety Rust does without sacrificing performance, and it provides even more! Its type system is great. You can have pre- and post-conditions. You can have ranged integer types. You can eliminate runtime errors and prove correctness of your code through formal verification. Just take a look at projects from https://github.com/Componolit. Plus, pointers are no longer an issue either: https://blog.adacore.com/using-pointers-in-spark. I would also like to add, that Ada has a package manager as well, namely Alire[2].

Given all that, my honest question is: why not Ada/SPARK when it is undoubtedly much better when it comes to safety, and much easier to read and write (to each their own, I suppose, but normal Rust can have 7 (!)[1] symbols next to each other and what it does (in generally, too) is way too hidden as opposed to the verbose (but not annoyingly so) Ada. You look at Ada and you immediately know what it does. The same cannot be said about Rust. It is almost akin to Perl. Seriously.

Useful links:

- https://docs.adacore.com/spark2014-docs/html/ug/en/usage_...
- https://docs.adacore.com/spark2014-docs/html/ug/en/source...
- https://docs.adacore.com/spark2014-docs/html/ug/en/source...
- https://www.electronicdesign.com/technologies/dev-tools/a...
- https://blog.adacore.com/from-rust-to-spark-formally-prov...
- https://en.wikibooks.org/wiki/Ada_Programming/Contract_Ba...
- https://www.adacore.com/gems/gem-31
- https://www.adacore.com/uploads/books/pdf/AdaCore-Tech-Cy...

Check them out. After you are done, can you tell me why Rust over Ada/SPARK?

[1]

let mut parents_array = ArrayVec::<[&[u8; BLOCK_LEN]; MAX_SIMD_DEGREE_OR_2]>::new()
let input_ptrs: &[*const u8; DEGREE] = &*(inputs.as_ptr() as *const [*const u8; DEGREE]);

[2] https://alire.ada.dev/

Footguns

MrWim — Sat, 24 Jul 2021 22:40:06 +0000

Also you can call unsafe functions.

Footguns

gbutler69 — Sat, 24 Jul 2021 16:03:48 +0000

> I believe Rust only lets you do 3 things in unsafe code that you weren't anyway allowed to do in safe code. You can dereference a raw pointer. You can access fields in a union. You can mutate statics. That's all.

There is a 4th thing. It lets you make FFI calls to C. And also a 5th thing. It lets you implement unsafe traits.

Signal

Avamander — Sat, 24 Jul 2021 15:11:32 +0000

I think it's really not about the languages that much, those can be learned albeit with time. But a first contributor can't improve the accessibility and user experience of bug triaging, discussion and patch submission, but they absolutely are dissuaded by those being outdated or poor. I really don't think C has the need to be marketable other than the fact that it's required for now. On the other hand things like mailing lists, git-email, bugzilla or IRC are real anti-advertisements for many. I mean, why bother with Linux if there are plethora of other projects that don't place such annoyances in front of you in addition to writing good code itself?

Rust / C risk management for undefined behavior (UB)

nix — Fri, 23 Jul 2021 09:41:07 +0000

> What are the UB cases ? C standard enlists all UB cases.

It's not that easy! It lists *some*. Undefined behaviour is behaviour the Standard does not define: nothing more, nothing less. It does list some of them, but not all (that list would be much longer): but things the Standard does not mention are also things it does not define, and undefined behaviour. (Some of them might be defined in other standards: POSIX defines a bunch of stuff C99 leaves either explicitly or implicitly undefined, for example.)

Pointer provenance

foom — Thu, 22 Jul 2021 02:14:21 +0000

https://wg21.link/P1726R5
https://wg21.link/P2414R0

Pointer provenance

mathstuf — Wed, 21 Jul 2021 19:32:25 +0000

I'll note these two papers for the C++ committee which describe and propose resolutions to the provenance issue (for C++):

P1726R5 (describing the problem)
P2414R0 (proposed solutions)

I believe they are publicly available, but in an abundance of caution, I'll leave them unlinked in case they are not (but those with access should be able to find them given these IDs).

Rust for Linux redux

smurf — Wed, 21 Jul 2021 15:46:27 +0000

Well, obviously it matters whether we're talking about "X is retroactively declared to be UB" (evaluate "be||!be" to be zero, or "realloc()" to poison the pointer you pass to it), or "X is a bug which didn't trigger any misbehavior due to Y but now does" (e.g. Y = memory layout or register allocation, when X is a write-beyond-end-of-array or use-after-free bug).

Without this context, both the statement itself and arguing about it is meaningless.

Rust for Linux redux

ma4ris5 — Wed, 21 Jul 2021 15:37:22 +0000

> This reads a lot like C++ contracts to me. C could adopt something like those, but I imagine the C++ committee is going to forge the main path there and C can take it or leave it.

I agree:

Easiest low hanging fruit are the features that are already implemented and used
actively at C++ side, concepts, which were taken from Rust into C++.

Kernel's requirements might be too detailed compared to generic C/C++, thus
a domain language for attributes could possibly fix the remaining gap
for additional checks and optimizations.

I mean items like:
Value compaction: negative return value is for an error, while >= 0 value is success case.
Value bit range classification: some bits are used independently from others.

So with domain language for attributes, static analysis and compile time optimization could
possibly improve runtime performance, and show places for potential overflows or leaks
from those ranges of values.

I found following research title, which possibly might be near the idea:

https://www.researchgate.net/publication/328988822_A_Gene...

I'm thinking more like the "printf" formatting checks:
If that could be generalized for functions and variables (into compile time/static check time),
then it could improve robustness.

In a way that the attribute declaration could be specified in the source code,
so that the compiler could verify the checks efficiently (enough) and optimize accordingly.

LTO side approaches this without code changes: it tracks value ranges between functions,
and can see possible overflow cases.
Attribute declarations could show developer's intention in these corner cases,
so compiler could warn about remaining possible issues.

Thus code could be proven to have no overflow issues, or accidental collisions between error values and valid values (to reduce risk for some of the rare problems).

Also C-to-Rust automatic conversion could pick those declarations and generate better wrappers.

Standardizing every new attribute feels too slow to have efficient progress for Kernel development,
so standardizing language for attribute declarations could be better.

Rust for Linux redux

nye — Wed, 21 Jul 2021 13:35:59 +0000

> “It has been working for decades” is just not something that justifies any expectation for that program to continue running

I'm saddened that we've reached the point where I genuinely can't tell if this statement is meant seriously or not.

Rust for Linux redux

mathstuf — Wed, 21 Jul 2021 00:34:58 +0000

> __attribute_value_range__(0, 0, 64) /* return value's value range is [0 - 64] */
> __attribute_value_range__(1, 0, 256) /* First argument's value range is [0 - 256] */
> int foo (int i) { return i >> 2; }

This reads a lot like C++ contracts to me. C could adopt something like those, but I imagine the C++ committee is going to forge the main path there and C can take it or leave it.

Rust for Linux redux

ma4ris5 — Tue, 20 Jul 2021 17:49:20 +0000

Rust, C and C++ are compiler front end languages, both are using same compiler back end libraries for the same compiler suite.

Detailed attributes seem to be the working solution to inform compiler about how the function behaves.
Both front ends can use same attribute mechanisms to make compiler back end libraries informed about function behavior.

realloc() bug example isn't actually C or Kernel issue at all: It seems to be LLVM C compiler front end bug,
and it affects "rustc" LLVM frontend implementation: "rustc" can't use realloc().

Here is the "realloc()" "noalias" issue analysis.
Correct return value is "2 2" which GCC gives,
and incorrect result comes from LLVM compiler (Fedora 34)
Test case was shown in https://lwn.net/Articles/862521/

$ clang -O3 realloc_test.c -o realloc_test ; ./realloc_test
1 2
$ gcc -O3 realloc_test.c -o realloc_test ; ./realloc_test
2 2

What is significant, "stdlib.h" doesn't have "noalias" attribute for realloc()".
Even while "noalias" is absent, "clang" hard codes "noalias" for the function:

/usr/include/stdlib.h contains (Fedora 34):
/* __attribute_malloc__ is not used, because if realloc returns
the same pointer that was passed to it, aliasing needs to be allowed
between objects pointed by the old and new pointers. */
extern void *realloc (void *__ptr, size_t __size)
__THROW __attribute_warn_unused_result__ __attribute_alloc_size__ ((2));

The above proves, that "stdlib.h" is clean, and doesn't contain the "noalias" attribute,
so the bug is within "clang" LLVM compiler, for example when -O3 is used there.

After realloc() definition, stdlib.h has function "reallocarray()", which is also interesting,
because it declares __attribute_alloc_size__ ((2, 3).

/* Re-allocate the previously allocated block in PTR, making the new
block large enough for NMEMB elements of SIZE bytes each. */
/* __attribute_malloc__ is not used, because if reallocarray returns
the same pointer that was passed to it, aliasing needs to be allowed
between objects pointed by the old and new pointers. */
extern void *reallocarray (void *__ptr, size_t __nmemb, size_t __size)
__THROW __attribute_warn_unused_result__
__attribute_alloc_size__ ((2, 3));
#endif

I think that there could be room for detailed function definition,
by adding already usable attributes into Kernel library functions.

Also adding new attributes into Kernel and compiler could be useful.

It might be even possible to add a domain language for custom attribute declarations,
which could be consumed by C compiler(s), for a precise function use validation.
I don't know if this has been considered.

Also "C headers to Rust" automatic conversions could take advantage of those
additional attributes.

For example a value range could be useful, something like:
__attribute_value_range__(0, 0, 64) /* return value's value range is [0 - 64] */
__attribute_value_range__(1, 0, 256) /* First argument's value range is [0 - 256] */
int foo (int i) { return i >> 2; }

__attribute_value_errnum_with_range__(0, -255, -10, 0, 64) /* error within [-255,-10], value within [0 - 64] */
__attribute_value_errnum_with_range__(1, -255, -10, 0, 256) /* error within [-255,-10], value within [0 - 256] */
int foo (int i) { if (i < 0) return i else return i >> 2; }

These should be such that they should be sane, and could be mapped into "C back end" libraries easily.

Personally I think that "always inline" functions could be used instead of macros, when this facility
is needed, and macro kind of inlining behaviour is necessary.

So if the additional attribute declaration is useful for C, and also looks good from following point of views:
C++, C-to-Rust, Rust, and it is correct, readable and manageable, it should be worth adding.

Compiler verification for having a working compiler:
- make sure (old) compiler doesn't generate bad code
make c_compile_bug_check
- Make sure errors / warnings are reported (including relevant undefined behaviour cases for the Kernel):
make c_compile_error_warning_check

Consume CERT Kernel warnings:
- Add already existing attributes to function definitions and variables.
- Introduce new attributes into for example value ranges, so that compiler can see whether integer could overflow.

For example integer overflow mitigation could be something like:
1. Enable or add (per C file) compilation flag for overflow reporting for making patches.
2. Compiler (must) track value's ranges and classifications (errors, warnings),
only warn about possible overflow cases.
3. Add attributes for value's range, to tell compiler what range the number has => unnecessary warnings go away. LTO / static check can validate these.
4. Add overflow check, or add overflow semantics for a calculation with a warning (may wrap, saturate to MIN_INT, 0 or, MAX_INT) => UB warning goes away.

5. Deliver individual patches for C header files for fixing overflow warning issues (add the range semantics),
to fix large code base issues.
6. Deliver patches that fix a single C file for remaining issues, until the C file doesn't have integer overflow risk, 7. Last patch could enable "integer overflow" compiler warning, to make sure integer overflow is absent or visible in future Kernel patches (static analysis bot could watch these).

A bot could also search for opportunities to enable the "integer overflow compiler check" for files that don't have issues currently.

Rust for Linux redux

Wol — Tue, 20 Jul 2021 17:01:01 +0000

> > I still maintain that "if it isn't a ring or a field, I can't reason about it" is overreach. I mean, people do manage to write correct floating point software, for example.

Ah ... so the OP was correct in saying it is overreach, but not for the reasons I understood ... fp is *almost* a ring :-) (if you use the "approximately equal" rather than the "equals" operator :-)

Cheers,
Wol

Rust for Linux redux

excors — Tue, 20 Jul 2021 15:25:00 +0000

> But isn't the set of all floating point numbers a finite set? Not that I know what the words "ring" or "field" actually mean in this context

A ring is a set of values plus a pair of operators ('+' and '*'), which have the properties listed on https://mathworld.wolfram.com/Ring.html . Floating point with addition and multiplication operators does not meet those properties, e.g. not all values have an additive inverse (you can't subtract anything from Infinity or NaN to get 0), and it doesn't guarantee a*(b+c) == a*b + a*c (so it's not even a semiring), etc. A field is a ring with some additional properties on the '*' operator. You can reason about floating point numbers, but not using any of those common algebraic concepts.

Rust for Linux redux

Wol — Tue, 20 Jul 2021 14:58:22 +0000

> I still maintain that "if it isn't a ring or a field, I can't reason about it" is overreach. I mean, people do manage to write correct floating point software, for example.

But isn't the set of all floating point numbers a finite set? Not that I know what the words "ring" or "field" actually mean in this context, but surely the set of valid REAL*4 numbers is smaller than the set of int32 numbers.

So it's easy to reason about floating point in exactly the same way as we reason about ints. It only becomes a problem if we forget that floating point numbers and irrational numbers are disjoint sets ...

Cheers,
Wol

Footguns

farnz — Tue, 20 Jul 2021 11:54:27 +0000

> The only thing I said is always true is that you can't dereference something you can't prove not to be NULL and expect it to not be UB; the check reordering is allowed because it was UB before and we can assume at that point what the author wanted. This doesn't mean a warning should not be emitted unless (somehow) specified otherwise. If there's a check before in the same function it's trivial to prove it's no longer NULL after that. Besides, you don't need to know whether an optimization resulted from the UB. Knowing it exists is enough. And AFAICT that can be known before transforming to IR.

This is the difference between your model, and the C model. In C, you can dereference something that you can't prove not to be NULL, and expect it to not be UB; it's only UB if, on a specific execution, the thing is NULL. If it happens not to be NULL, then there's no UB. This comes down to whole program analysis - as a programmer, you might ensure that you only call ub(config) with non-NULL pointers, and thus it's fine.

So the C compiler is able to reason backwards - if thing *is* NULL, then there is UB. Ergo is must not be NULL, because UB isn't allowed, which permits optimization on the basis that it's not NULL. This is fine if the explicit NULL check is (e.g.) from a macro, or in generated code, or left over from refactoring and not yet removed; you've taken out something that's always false in this context, and just deleted the dead code.

It only becomes a problem where the human is surprised by the deletion of dead code - i.e. where the human thought the check was still important, but it's actually considered always false (or always true) by the compiler. And as deletion of dead code takes place at every level - from AST, through IR, through machine instruction choice - the compiler needs to link back its elimination of dead code and determine whether or not the human would be surprised by this particular elimination.

And that's what makes it a hard problem - we may know that ub(config) is only ever called with a non-NULL pointer, but that needs a whole program analysis which the compiler cannot perform. We may also know this simply because we've refactored so that callers of ub(config) do the NULL check themselves, and the extra NULL check inside the function may be there because a preprocessor (which can be outside the compiler!) has used a general form of code that works regardless of the presence of the NULL checks; why use two macros and force the human to think about whether or not a NULL check has happened already, when you can use one?