News for hackers. Stuff that matters.
Re:So You Want to Rust the Linux Kernel? by gpderetta on Monday October 11, 2021 @07:19AM (#28827058)
I can't access the article at $JOB, but if I understand correctly, Rust would guarantee that usage of the RCU API si correct, but it would be silent on the API implementation itself as it would be written with unsafe (but crossbeam-rs). On the other hand the author is probably saying that the kernel RCU C API itself has been proven correct, either manually or by machine checking (directly the C code or a translation of it in a proof assistant); usages of the API might not be proven correct though.

Also note that the author of the article is the actual inventor of RCU.

Re:So You Want to Rust the Linux Kernel? by volta83 on Monday October 11, 2021 @07:33AM (#28827171)
> Also note that the author of the article is the actual inventor of RCU.

I know, so?

> On the other hand the author is probably saying that the kernel RCU C API itself has been proven correct,

But this is not true right?

There is no formal proof, e.g., in Coq, that proves a useful subset of the RCU C API correct (as in, if you stick to this useful subset, you can't introduce UB).

OTOH, a safe Rust API could be proved correct to use at least, and an implementation of it that uses unsafe, like the one in crossbeam-rs, is typically very amenable to theorem provers (much more than C).

So what I am saying is that the author is ignoring the value of providing a safe Rust API for RCU, like crossbeam-rs.

If the Linux RCU APIs can't be mapped to it, then maybe they are incorrect to use, and this is why we can't prove them correct.

Doing the work of mapping them, and understanding any issues, could lead to changes to those APIs that might allow us to prove them correct.

Re:So You Want to Rust the Linux Kernel? by gpderetta on Monday October 11, 2021 @07:42AM (#28827231)
A quick search shows a bunch of papers about RCU possibly containing proofs. I don't know if there is a coq proof, but there are other dedicated tools to model lock-free algorithms, or possibly the proofs were done by hand.

Of course that's still not proving the actual C code, the translation probably still need to checked by hand.

Re:So You Want to Rust the Linux Kernel? by pca006132 on Monday October 11, 2021 @08:53AM (#28827769)
> an implementation of it that uses unsafe, like the one in crossbeam-rs, is typically very amenable to theorem provers (much more than C)

Just wondering, how many unsafe code in commonly used libraries (standard library, tokio etc.) are proved using theorem provers?

Re:So You Want to Rust the Linux Kernel? by steveklabnik on Monday October 11, 2021 @10:17AM (#28828570)
Don't have comprehensive enough data to know, but part of the standard library was proven via the Rustbelt project, and it found some places where there were bugs, as well as some places where things could safely be loosened up.
Re:So You Want to Rust the Linux Kernel? by volta83 on Tuesday October 12, 2021 @08:41AM (#28838948)
Most of the unsafe code in libcore is proved in Iris.

Some of the unsafe code in the standard library also.

Some parts of crossbeam have pencil&paper proofs documented.