The perils of pinning
C programmers take full responsibility for the allocation of memory and the placement of data structures in that memory. Rust, instead, takes most of that work — and the associated control — out of the programmer's hands. There are a number of interesting behaviors that result from this control, one of which being that the Rust compiler will happily move objects in memory whenever that seems like the thing to do. Since the compiler knows where the references to an object are, it can move that object safely — most of the time.
Things can go badly, though, when dealing with self-referential data structures. Consider the humble (C) list_head structure that is heavily used in the kernel:
struct list_head {
struct list_head *next, *prev;
};
It is possible to create a Rust wrapper around a type like this, but there are complications. As an example, initializing a list_head structure to indicate an empty list is done by setting both the next and prev fields to point to the structure itself. If, after that happens, the compiler decides to move the structure, those pointers will now point to the wrong place; the resulting disorder does not demonstrate the sort of memory safety that Rust hopes to provide. The same thing can happen with non-empty lists, of course, and with a number of other kernel data structures.
Benno Lossin started his Kangrejos talk by saying that Rust provides a mechanism to deal with this problem, which can also arise in pure Rust code. That mechanism is the Pin wrapper type; placing an object of some other type into a Pin will nail down its location in memory so that it can no longer be moved. There are numerous complications, including the need to use unsafe code to access fields within a pinned structure and to implement "pin projection" to make those fields available generally.
![[Benno Lossin]](https://static.lwn.net/images/conf/2022/kang/BennoLossin-sm.png "Benno Lossin")
The really big challenge, though, is in a surprising area: initialization.
Fully understanding the issues involved requires a level of Rust guru status far
beyond anything your editor could hope to attain, but it seems to come down
to a
couple of aspects of how Rust treats objects. Rust goes out of its way to
ensure that, if an object exists, it has been properly initialized. Object
initialization in Rust tends to happen on the stack, but objects that need
to live indefinitely will need to move to the heap before being pinned.
That movement will break a self-referential object, but pinning before
initialization will break Rust's memory-safety rules.
Solutions exist, but require a lot of unsafe code; Lossin has been working on alternatives. He initially tried to use const generics to track initialization, but the solution required the use of procedural macros and was complex overall. And, at the end, it was "unsound", a Rust-community term indicating that it was not able to properly handle all cases. So that approach was abandoned.
Instead, he has come up with a solution that uses (or abuses) struct initialization and macros. Your editor will not attempt a full description of how it works; the whole thing can be seen in Lossin's slides. Among other things, it requires using some complex macros that implement a not-Rust-like syntax, making the code look foreign even to those who are accustomed to Rust.
The response in the room was that, while this work is clearly a clever hack, it looks like a workaround for a limitation of the Rust language. It's the kind of thing that can create resistance within the kernel community, many members of which already find Rust hard to read (though it should be said that kernel developers are entirely willing to merge C preprocessor hackery when it gets the job done). There was a strong desire to see a different solution.
Xuan "Gary" Guo stepped up to show an alternative approach. In C, he began, it is easy to create an object without initializing it, or to initialize an object twice. In Rust, anything that circumvents the normal initialization routine requires unsafe code. Tracking the initialization of such objects can require maintaining an initial variable to hold the current state, which would be a good thing to avoid. Other approaches can require additional memory allocations, which are also not good for the kernel.
![[Xuan Guo]](https://static.lwn.net/images/conf/2022/kang/XuanGuo-sm.png "Xuan Guo")
There have been attempts to address the problem with, for example, the pin_init
crate. But
pin_init still is unable to initialize self-referential structures, and has
to do its own parsing of Rust structures and expressions. That requires
the syn crate, which is not
really suitable for kernel building.
A proper solution for the kernel, he said, would have a number of characteristics. It should be safe, impose no extra cost, and require no additional memory allocations. Aggregation should work; a structure containing multiple pinned objects should initialize properly. The mechanism used should not look much different from normal Rust. There should also be no assumptions about whether initialization can fail or not.
Guo's solution (which can be seen in his slides), looks a bit closer to normal Rust than Lossin's, but it still depends on complex macro trickery and has not managed to avoid using the syn crate. And it still can't handle self-referential structures properly. But it is arguably a step in the right direction.
Once again, though, the proposed solution looked like an impressive hack, but the response was not entirely favorable. Kent Overstreet described it as "really gross", adding that this job should be done by the compiler. Wedson Almeida Filho responded that the compiler developers would just suggest using procedural macros instead. One compiler developer, Josh Triplett, happened to be in the room; he said that there could be help provided by the language, but that requires an RFC describing the desired behavior, and nobody has written it yet. The session wound down without any specific conclusions other than, perhaps, a desire to pursue a better solution within the Rust language rather than trying to work around it.
[Thanks to LWN subscribers for supporting my travel to this event.]
| Index entries for this article | |
|---|---|
| Kernel | Development tools/Rust |
| Conference | Kangrejos/2022 |
Posted Sep 15, 2022 14:38 UTC (Thu)
by mb (subscriber, #50428)
[Link] (5 responses)
Why?
>that the compiler developers would just suggest using procedural macros instead.
What's wrong with that? Why not use proc macros?
Posted Sep 16, 2022 2:35 UTC (Fri)
by milesrout (subscriber, #126894)
[Link] (4 responses)
>Why?
There are a few reasons a crate might not be suitable for kernel building. The most important that I can think of would be if the crate requires the standard library. Rust for Linux, as far as I am aware, requires a freestanding (no-std) environment. Looking at the pin-init crate, it requires 'syn' as a runtime dependency (not just a compile-time ("dev") dependency)[0].
[0]: https://github.com/nbdd0121/pin-init/blob/trunk/pin-init-...
> What's wrong with that? Why not use proc macros?
As the article notes:
>> it requires using some complex macros that implement a not-Rust-like syntax, making the code look foreign even to those who are accustomed to Rust.
and later
>> it still depends on complex macro trickery and has not managed to avoid using the syn crate. And it still can't handle self-referential structures properly.
So, complexity for one thing. Creating additional sublanguages isn't really ideal. Would you need to write code that uses these procedural macros in every structure that includes a list head? In every self-referential structure? In every structure that includes a self-referential structure? In every structure that includes those structures? Etc?
Procedural macros are also known for slowing down compilation times if used too much. If there is a procedural macro invocation in the definition of every structure that can be part of a linked list, that might significantly slow down compilation times compared to a solution that did not require procedural macros. Rust compile times are already pretty slow, even without procedural macros, compared to C, so making them even worse would not be ideal.
Posted Sep 16, 2022 6:54 UTC (Fri)
by mb (subscriber, #50428)
[Link] (3 responses)
But not for building.
>Would you need to write code that uses these procedural macros in every structure that includes a list head? In every self-referential structure? In every structure that includes a self-referential structure? In every structure that includes those structures? Etc?
I don't see why this would be a blocker. Especially for a thing that could eventually be migrated over to a solution provided by the rust compiler or core.
And the whole "sublanguage" thing is the whole point of macros. Also in C. Look at what the kernel does with C macros. That's a completely separate language.
Have you looked at the slides for the proposed proc macros? The only non-idiomatic thing is that a dot (.) appears in an unusual place.
Posted Sep 16, 2022 12:27 UTC (Fri)
by milesrout (subscriber, #126894)
[Link] (2 responses)
>The part of the article and my question was about building.
pin-init does not require the syn crate just for building. As I said, and as demonstrated in my link, it requires it as a dependency (run-time dependency), not as a dev dependency (Rust lingo for a build-time dependency).
>I don't see why this would be a blocker. Especially for a thing that could eventually be migrated over to a solution provided by the rust compiler or core.
As noted in the article: "Once again, though, the proposed solution looked like an impressive hack, but the response was not entirely favorable. Kent Overstreet described it as "really gross", adding that this job should be done by the compiler. Wedson Almeida Filho responded that the compiler developers would just suggest using procedural macros instead. One compiler developer, Josh Triplett, happened to be in the room; he said that there could be help provided by the language, but that requires an RFC describing the desired behavior, and nobody has written it yet."
So there is absolutely no guarantee that it would just be a thing that would "eventually" be migrated over - as with most stopgap measures in the world of software, it would probably end up being permanent.
> And the whole "sublanguage" thing is the whole point of macros.
The supposed point of using Rust for the Linux kernel as opposed to one of the other millions of memory-safe languages out there (recall that almost all programming languages are memory-safe) is that it is well-suited to interfacing with C and writing low-level code using the "unsafe" escape hatch while allowing those uses to be wrapped in type-safe memory-safe wrappers. If, to accomplish the most basic low-level task (of working with these sorts of structures), it requires the use of procedural macros, it strongly suggests that the language isn't actually ready. After all, if the point of Rust is that Rust is well-suited to this, then by definition *Rust* is well-suited to it, not Rust-with-various-extensions. It's one thing to write macros to reduce boilerplate, but this is writing macros to cover over a gaping hole in the most basic functionality of the language, at least if the language claims to be designed for efficient interoperability with C code.
This isn't meant to be a criticism of Rust in general. I'm just explaining why people would balk at the idea of needing to use procedural macros for something so basic - needing to extend the language to deal with this means people will expect that it will need to be extended for lots more things in the future, yknow? Then you aren't really using Rust, you're using Rust++, so why use Rust in the first place?
> Also in C. Look at what the kernel does with C macros. That's a completely separate language.
What the kernel does with C macros is certainly not a "completely separate language" - in fact, what the kernel does with macros is done in such a way as to make their use mostly invisible. The vast majority of the time you do not need to know, when you write foo(x), whether foo is a macro or a function. That is why the Linux kernel uses lower case macro names: they're designed to blend in, not to stick out like a sore thumb as ALL_UPPER_CASE macros do.
C macros are also not procedural. They involve simple text substitution. Rust has macro_rules or whatever for that kind of relatively simple macro. This is different: it is significantly more complicated and produces significantly slower compilation times.
Posted Sep 16, 2022 14:27 UTC (Fri)
by Bigos (subscriber, #96807)
[Link] (1 responses)
Posted Sep 17, 2022 3:22 UTC (Sat)
by milesrout (subscriber, #126894)
[Link]
Posted Sep 15, 2022 14:57 UTC (Thu)
by 0x3333 (subscriber, #158599)
[Link] (11 responses)
Posted Sep 15, 2022 15:05 UTC (Thu)
by mb (subscriber, #50428)
[Link] (1 responses)
I don't know, if you're the only one. But Kernels and lots of bare metal code have already been developed in Rust.
Rust in Linux is merely fighting with the existing C interfaces and C concepts. These have never been developed with Rust in mind and they cannot be changed just to support Rust.
I also don't think that these problems make it unsuitable. It just means that we have to live with a couple more unsafe statements for now.
Posted Sep 15, 2022 15:12 UTC (Thu)
by 0x3333 (subscriber, #158599)
[Link]
Well, I was referring to Linux Kernel, I used rust for embedded microcontrollers, but for Linux Kernel it looks(from outside) that is too much to fight.
Anyways, it's good to see safety landing on the kernel.
Posted Sep 16, 2022 15:13 UTC (Fri)
by calumapplepie (guest, #143655)
[Link] (8 responses)
Expecting Rust to interface with all that without any nasty hacks is a little unfair.
Posted Sep 17, 2022 3:37 UTC (Sat)
by milesrout (subscriber, #126894)
[Link] (7 responses)
It's not really "unfair" to expect Rust to interface with all that, because Rust people advertise their language as being good at interfacing with C. That surely means something more than "can make ABI calls to C"? Almost every language out there can call functions using the platform C ABI. I would expect "good at interfacing with C" to mean that the language has good support for the same sorts of things people do in C. C is all about communication and openness.[0] If you can't do that kind of development, it's not really a "C-friendly" language, standards-compliance or no.
[0]: https://www.humprog.org/~stephen/research/papers/kell17so...
Posted Sep 18, 2022 17:56 UTC (Sun)
by foom (subscriber, #14868)
[Link] (6 responses)
The Linux kernel depends on a great many weird and ill-specified GCC compiler extensions -- some of them explicitly designed for the kernel's needs, as well as other long standing special compiler modes that allow you to get away with violating fundamental rules of the language (e.g. that forbid treating the same location in memory as multiple types.) And even with all that, you cannot even build the kernel with optimizations disabled -- it's dependent on the whims of the optimizer, too!
(But, of course, you can certainly have a self-referential struct in C without doing anything strange. So, there is that.)
Posted Sep 18, 2022 18:37 UTC (Sun)
by Wol (subscriber, #4433)
[Link] (5 responses)
The point is NO formal language will let you do most of the stuff Linux does. (Of course assembler will let you, because assembler has no formal model.)
Linux is an operating system. It is MEANT to talk to other devices, with other controllers, that do their own thing. NO formal language can cope with other systems doing things behind its back.
So basically, the less "unsafe" code there is the better, because safe code means the compiler has proven that the code will work as intended (barring programmer "sillies"). But at the end of the day, there will still need to be a lot of "unsafe" code, because ...
If your code is reading from the receive buffer of a network card, you really do not want a language that assumes memory only changes when you write to it! What was that about GCC assuming reading from uninitialised memory is UB and can be optimised away? Bang goes your networking!
Cheers,
Posted Sep 19, 2022 9:02 UTC (Mon)
by tialaramex (subscriber, #21167)
[Link] (2 responses)
Rust actually reflects what your machine code can do for that network card receive buffer. You can say look, just perform actual fetches for all the "memory".
let recvd = std::ptr::read_volatile<NetworkBuffer>(recv_buffer); /* Rust will bit-wise copy the values in the buffer. */
This function is unsafe, because it fetches some arbitrary memory so clearly you can blow up the world (e.g. unaligned read on an architecture where those are forbidden, or just point it out of bounds), but it's very well defined if recv_buffer actually points at a NetworkBuffer size blob of suitably aligned and addressable "memory" we can load values from, it will emit actual loads for those values and not try to cache them or assume it knows their value or whatever.
That's a contrast from C which has us actually pretend recv_buffer is just pointing at an actual NetworkBuffer with a "volatile" qualifier and so then we can go around doing operations to it, even though in practice that's a bad idea and the only thing we ought to do is copy it somewhere. On a good day that's all the C (or worse C++) does with a volatile, on a bad day you need to guess whether the programmer knew what's really going or whether the code you're reading is full of unintentional races.
There was an effort to get C++ to move towards intrinsics for fetch/ store like Rust rather than C's volatile qualifier hack. But this got some very angry push back, and I anticipate there will not be any further attempts.
Posted Sep 19, 2022 18:16 UTC (Mon)
by kreijack (guest, #43513)
[Link] (1 responses)
> That's a contrast from C which has us actually pretend recv_buffer is just pointing
I don't think to understood your sentence. But my understood is that you can wrote a
read_volatile(recv_buffer)
that copy the data to a "volatile" buffer. IIRC When a pointer is passed to a function
Posted Sep 20, 2022 8:40 UTC (Tue)
by farnz (subscriber, #17727)
[Link]
I'm going to stick to C syntax throughout, since I think that's easier for kernel programmers to follow than Rust.
In C, you might have code like:
It's then tempting (but often wrong) to write code that does things like buf->ip_hdr.src_addr, when this isn't actually a good idea because of the volatile reads that will be done.
Rust doesn't have a volatile qualifier on storage that changes all codegen accessing that storage. Instead it has the equivalent of void * memcpy_volatile(void * dest, volatile void * src, size_t count); (but using generics from Rust's type system to replace void * and size_t count). Because your only dependable operation on the buffer is to copy out of the shared space that can change underneath you at no notice (imagine that, for example, NetworkBuffer actually lives in memory the far side of the PCIe bus, on the NIC itself), that's what you'll do.
Posted Sep 19, 2022 18:11 UTC (Mon)
by kreijack (guest, #43513)
[Link] (1 responses)
I think that C++ does...
Posted Sep 21, 2022 11:24 UTC (Wed)
by tialaramex (subscriber, #21167)
[Link]
Sometimes the abstract machine's differences from a real machine just have performance consequences, for example most doubly linked list operations look really clever in the abstract machine and have reasonable performance, but this has lousy performance on an actual computer you can buy today because of caches.
But often there are simply practical differences, the abstract model lacks entirely something the real machine has. A higher level C++ application needn't care but the Linux kernel does. For some thing Linux relies on inline assembler, the same thing works in Rust, and the same trick kernels written in C++ use. In other places Linux is relying on semantics which are not offered by the formal language and which likewise are not offered in ISO C++ but do happen to work in the chosen compiler.
Posted Sep 15, 2022 15:01 UTC (Thu)
by GhePeU (subscriber, #56133)
[Link] (4 responses)
https://twitter.com/LinaAsahi/status/1567752082060619776
https://twitter.com/LinaAsahi/status/1570119306461204481
Posted Sep 15, 2022 16:15 UTC (Thu)
by excors (subscriber, #95769)
[Link] (3 responses)
Posted Sep 16, 2022 3:14 UTC (Fri)
by developer122 (guest, #152928)
[Link] (2 responses)
Posted Sep 19, 2022 14:10 UTC (Mon)
by Wol (subscriber, #4433)
[Link] (1 responses)
It might not be much, but papercuts add up.
Dunno how they'll fix it but it needs fixing ...
Cheers,
Posted Sep 21, 2022 1:25 UTC (Wed)
by D1plo1d (guest, #161018)
[Link]
https://y86-dev.github.io/blog/return-value-optimization/placement-by-return.html
For what it's worth as a Rust user, these Rust for Linux issues seem to be becoming a very helpful forcing function to improve Rust itself.
Posted Sep 15, 2022 15:16 UTC (Thu)
by mathstuf (subscriber, #69389)
[Link] (3 responses)
My understanding is that "unsound" comes from type theory and is basically the equivalent of "if this is true, we can prove 1=2". Rust might extend that to also involve "you can break invariants without using `unsafe` with this API", but, AFAIK, the term itself is not a "Rust community" term.
Posted Sep 15, 2022 21:03 UTC (Thu)
by riking (subscriber, #95706)
[Link]
Posted Sep 15, 2022 22:09 UTC (Thu)
by khim (subscriber, #9252)
[Link]
You are 100% correct. It's not “Rust community” term. It's Rust reference term:
Posted Sep 16, 2022 16:00 UTC (Fri)
by epa (subscriber, #39769)
[Link]
Posted Sep 15, 2022 15:22 UTC (Thu)
by Bigos (subscriber, #96807)
[Link] (12 responses)
You do not place an object in Pin. Instead, you place a "pointer type" (a shared/exclusive reference, Box, etc.) inside it.
From what I recall, the contract is that if you create a Pin<P> (where P is a pointer, like &mut T) you promise you will never move the pointed-to object (unless it implements Unpin, which is a trait automatically implemented unless opted-out; self-referential types must not implement it, though).
If object initialization (like setting self-referent pointer to itself for list_head) requires the object to be Pinned, that indeed is problematic. The common case is to initialize the object without any pinning and when it is placed where it should only Pin it there. This is how Futures work (the first Future::poll() call pins the future, so it can be moved and combined before that happens).
Could MaybeUninit help represent the uninitialized, not-pinned object state? It indeed requires the use of unsafe, but safe wrappers could Pin the object, initialize it and return a Pin<&mut T>.
Posted Sep 15, 2022 16:42 UTC (Thu)
by atnot (subscriber, #124910)
[Link] (11 responses)
Indeed this is why I think describing pinning in terms of the Rust compiler implicitly moving things around is confusing and unhelpful: C moves things around implicitly just as much as Rust.
If you take a struct in C and pass it somewhere by value, that struct is now in a new location. If you do that with a self referential struct, it is now invalid in the new location. This applies identically to both languages. However, safe Rust would not let you do that, because self reference requires borrowing, and borrowed values can not be moved/passed by value.
So where is the problem then? Well, Rust also allows users to *explicitly* do things like use std::mem::swap to swap the contents of two mutable references. This means that if you can get an exclusive reference to something, you can move it. That is why pointer types to location aware things are a problem and need to be wrapped in another type that prevents access, like Pin.
Posted Sep 15, 2022 19:33 UTC (Thu)
by fw (subscriber, #26023)
[Link] (10 responses)
Posted Sep 15, 2022 20:23 UTC (Thu)
by mb (subscriber, #50428)
[Link] (7 responses)
No. Not really.
The only difference is that in Rust the "the old object is still around" is zero time.
The difference between a copy and a move is that the lifetime of the old object is terminated immediately and not at some later point. And based on that the compiler might be able to apply some optimizations to omit the copy altogether.
And if you copy a self referential object, it's by definition not self referential after copy. It references another object (the original one!). Not self.
Posted Sep 16, 2022 1:59 UTC (Fri)
by JoeBuck (subscriber, #2330)
[Link] (3 responses)
Posted Sep 16, 2022 18:10 UTC (Fri)
by tialaramex (subscriber, #21167)
[Link] (2 responses)
Rust's Clone trait, which is what happens if you clone() something that admits it can be cloned, is a function you can implement. For example my Multiplicity https://docs.rs/misfortunate/1.0.0/misfortunate/struct.Mu... wrapper type claims to be Clone, despite the fact all it asks of your wrapped type T is that it should be Default. Multiplicity's clone() implementation just makes a Default::default() of your type, which is type correct but presumably not what you wanted. (The name is a reference to the 1996 Andie MacDowell comedy in which Michael Keaton clones himself repeatedly and gradually the clones deteriorate in quality)
But you deliberately can't intervene in the simple memcpy() behaviour when the compiler decides to move your object in memory. The Rust compiler reserves the rights to do this more often than you expect, or less often, and in different places, as it sees fit. Pinning stops it from doing that, at some potential cost in performance.
Posted Sep 22, 2022 6:44 UTC (Thu)
by Homer512 (subscriber, #85295)
[Link] (1 responses)
If the compiler already has facilities to detect when an object should not be moved, why is it so hard to give it facilities to invoke a custom function for the move instead?
Posted Sep 27, 2022 9:27 UTC (Tue)
by farnz (subscriber, #17727)
[Link]
It's hard because the consequence of adding a "move fix-up" function is to break the mental model people have of Rust code.
In today's world, the maximum cost of a move in Rust (or a copy for things that impl Copy) is a memory copy of the object. The cost of a move is thus predictable.
If Rust adds a "move fix-up" function of some form, that predictability goes away - you now depend on the implementation of the move function being high-quality. C++ goes this route, of having hidden fix-up functions (operator=, move and copy constructors), and thus provides an illustration of the benefits of that approach (where all developers are skilled) and of the costs (where some developers are unskilled and don't realise that they're invoking a lot of code doing a move).
Actually implementing the changed semantics in the compiler would be trivial - it's the human cost of learning how the new semantics work that's non-trivial.
Posted Sep 17, 2022 14:01 UTC (Sat)
by jezuch (subscriber, #52988)
[Link] (1 responses)
Posted Sep 18, 2022 14:57 UTC (Sun)
by matthias (subscriber, #94967)
[Link]
And for correctness of self referential objects, you have to assume that the object might be physically moved if it is logically moved. Also, for unpinned and unaliased objects, the compiler is free to move it around for code optimization, even without a logical move.
Posted Sep 18, 2022 17:40 UTC (Sun)
by fw (subscriber, #26023)
[Link]
Posted Sep 15, 2022 23:06 UTC (Thu)
by atnot (subscriber, #124910)
[Link] (1 responses)
Of course, this is a completely moot point in C because it's always possible to get any memory into an arbitrary state anyway. But Rust doesn't have the luxury of being able to tell people just not to do things. Hence unlike C, it does not allow you to access the old object after a copy (unless it's marked with the special Copy trait). Which is after all the only difference between a copy and a move, it's not like the old memory disappears.
Posted Sep 16, 2022 2:15 UTC (Fri)
by wahern (subscriber, #37304)
[Link]
Rather, Rust has the luxury of telling people they *can't* do things. Which is critical to and in some cases necessary for Rust being able to provide its safety guarantees. Complex, memory-aware data structures (e.g. cyclical, self-referential, etc) have *always* been a sore point for Rust. Most Rust developers come from the world of scripting languages or similar environments (e.g. Java) where hash tables are the primary, even sometimes exclusive primitive (beyond arrays) for building higher-order data structures, so they don't feel any loss. For this group, more complex data structures always come by way of magic libraries with generic interfaces that you glue together; building thin, bespoke data structures for your specific functional problems as a matter of course is a foreign concept.
Many solutions Linux has adopted for higher performance, lower latency, multi-core scalability, etc simply wouldn't have even been considered at all when writing everything in scratch from Rust. It's probably the case that equally (or at least sufficiently) performant Rust-consonant alternatives exist for most individual cases. The real question is whether at scale, when you're stitching all these solutions together into what is essentially a single, complex data structure, you can end up in the same place in terms of performance; or if the solutions Rust demands intrinsically impose greater costs when composed together.
Posted Sep 15, 2022 15:38 UTC (Thu)
by atnot (subscriber, #124910)
[Link]
To clarify, unsoundness means that an abstraction allows you to subvert the safety guarantees of Rust, violating some contract between the programmer and the compiler. For example, by allowing you to obtain an invalid pointer under some usually contrived circumstance.
This is different from being unsafe, where an interface has requirements that can not be automatically proven, and a bug or vulnerability, where the interface is still sound but the code is not implemented correctly. Hence the jargon.
> The session wound down without any specific conclusions other than, perhaps, a desire to pursue a better solution within the Rust language rather than trying to work around it.
I'm personally excited about what the kernel can bring here. The reason Rust doesn't really have a nice solution to pinning is that in almost every case, self referential types can be replaced with indexes at no loss (or even a gain) to clarity or performance. In the few exceptions that existed, adding another allocation or some unsafe code was not a big deal.
I expect that will still be the case most of the time within the kernel, but integrating with a codebase that makes very heavy use of self reference has great potential to increase the motivation to fix some of the papercuts and warts in this area.
Posted Sep 15, 2022 21:45 UTC (Thu)
by gray_-_wolf (subscriber, #131074)
[Link] (16 responses)
With that said, I have two questions about this:
> As an example, initializing a list_head structure to indicate an empty list is done by setting both the next and prev fields to point to the structure itself.
1) Why thought? Isn't the idiomatic C way setting the next and prev to 0? Assuming that is not possible in rust (to prevent null dereference I assume), why not use rust-version of std::optional?
2) How does this work together with C code? Are the next and prev converted between &self and 0 every time they are passed over the boundary? Or does kernel use &self as well instead of 0?
Posted Sep 15, 2022 22:36 UTC (Thu)
by Sesse (subscriber, #53779)
[Link] (1 responses)
Posted Sep 15, 2022 22:43 UTC (Thu)
by khim (subscriber, #9252)
[Link]
It's double-linked list in Linus's good taste. The idea is that there are never any And, of course, when you convert that data structure to Rust you want to keep that property… and you couldn't! Rust doesn't have any constructors and structures are created in one place (on stack) and then are moved into proper position. This was never a problem for new Rust code, but it's very often quite awkward. And indeed, language-level solution would be great. But before it can be implemented it first needs to be imagined and it's not that easy here.
Posted Sep 15, 2022 22:36 UTC (Thu)
by khim (subscriber, #9252)
[Link] (6 responses)
Both are possible. You couldn't use references in these self-referential data structures because mutable references are, but definition, unique. And pointers are C is not fussy about uninitialized memory. You just create an empty structure and then fill with pointers. Of course that is possible to do in The problem here is not how to do that, but how to do that in a safe way. Because if you driver have pile of
Posted Sep 15, 2022 23:24 UTC (Thu)
by excors (subscriber, #95769)
[Link] (3 responses)
I think that's not right in general. "&mut T" references are unique, but 'mut' does not mean mutable. Many objects are mutable through a "&T" reference. The difference is that the compiler can't statically prove that you're only mutating it through a single "&T" at once, so T has to either guarantee that mutations are atomic (std::sync::atomic, Cell) or implement dynamic checks to prevent concurrent mutation (RefCell, Mutex).
If you can design your self-referential data structure with interior mutability like that, then you can mutate it through non-unique references. There may be practical difficulties with using interior mutability in those specific cases, because it often needs extra memory for the dynamic state and dynamic error handling when you violate the rules, but that's a different problem.
("&mut T" should really be called an exclusive reference (while "&T" is a shared reference), because "mutable reference" is actively misleading. I think the "mut" keyword is a design flaw in the language, albeit a fairly minor one that could be worked around with better documentation, and it's possible all the other proposed solutions were equally flawed. See also https://docs.rs/dtolnay/latest/dtolnay/macro._02__referen... which makes the same points.)
Posted Sep 16, 2022 2:49 UTC (Fri)
by milesrout (subscriber, #126894)
[Link] (1 responses)
Is that a bit backwards? "mut" doesn't mean mutable because some things are mutable without it? Wouldn't it be more accurate to say that "&T" doesn't mean "immutable"? "&mut T" still does mean mut, and "mut T" definitely does mean it's a mutable T.
>If you can design your self-referential data structure with interior mutability like that, then you can mutate it through non-unique references.
This sounds very similar to the "const means thread-safe" idea that AFAIK was first introduced into the C++ community by Herb Sutter: essentially (if I am remembering correctly), the point was that if you have a T const& t (equivalent to Rust &T) then it should always be thread-safe to access t, because a strict reading of the language specification essentially requires const member functions on objects to access mutable members (equivalent to Rust interior mutability, I guess?) only in a thread-safe manner.
https://isocpp.org/blog/2012/12/you-dont-know-const-and-m... (best link I can find)
Posted Sep 16, 2022 4:08 UTC (Fri)
by Cyberax (✭ supporter ✭, #52523)
[Link]
It's quite a bit different. In C++ const functions do not change the "logical" state and can be called through a const pointer/reference. But there's nothing preventing you from sharing a mutable reference across threads and changing the object while a `const` function is running.
Rust goes further. The language guarantees that at any given time there is only one reference through which you can change an object and no other references.
Posted Sep 16, 2022 22:18 UTC (Fri)
by ssokolow (guest, #94568)
[Link]
Posted Sep 16, 2022 1:32 UTC (Fri)
by tialaramex (subscriber, #21167)
[Link] (1 responses)
MaybeUninit is a union (and thus can't be accessed by safe code directly) of uninitialized nothingness, with your type T. The compiler can see this may be uninitialized, and therefore no stunts which assume it's a T are allowed, and yet it might be a T and so we can (unsafely) write to elements of T.
While we're initializing it, the MaybeUninit<T> type is clearly not a T as far as other code is concerned, there's no risk anybody mistakenly thinks this is a T and tries to use it as one. Once we're done we can unsafely assume_init() to get a T, and if we're right this is fine, if we lied everything might catch fire but that's a programming error. If T is some structure that only some people want to perform gradual initialization on, MaybeUninit also has a write() method where we can safely just give it a T, and say look, I don't want to manually initialize this, here's a perfectly nice T, overwrite the uninitialized memory with that.
So you could imagine some NetworkThing struct, and Linux has an API which gives you a MaybeUninit<NetworkThing> and maybe the 100Gbps network card which costs more than my laptop really does carefully initialize NetworkThings via the MaybeUninit in order to shave a few CPU cycles off the fast path for a packet send, but chances are my 10Mbps USB 2 dongle can just write() a NetworkThing and it makes no measurable difference to how slow a 10Mbps network connection is.
The 100Gbps driver does need to write unsafe code to initialize a NetworkThing in its fast path, but the USB ethernet driver does not, in exchange for which it's a little slower than it might have been. That feels like a reasonable trade.
Posted Sep 16, 2022 2:27 UTC (Fri)
by khim (subscriber, #9252)
[Link]
Maybe for Rust designers, but I doubt Linux driver writers would agree. Remember: we are talking about guys who often raise a fuss when compiler adds couple of spurious commands. On the other hand these are the same guys who already know how to make C compiler generate code they want and Rust in not much different. They would try to solve that issue and probably would invent something. Most likely some After all that's how Rust solved these issues for
Posted Sep 16, 2022 7:52 UTC (Fri)
by Karellen (subscriber, #67644)
[Link] (6 responses)
I'm at a similar level of knowledge with rust, and I'm getting stuck on: the Rust compiler will happily move objects in memory whenever that seems like the thing to do. Since the compiler knows where the references to an object are, it can move that object safely — most of the time. [...] initializing a list_head structure to indicate an empty list is done by setting both the next and prev fields to point to the structure itself. If, after that happens, the compiler decides to move the structure, those pointers will now point to the wrong place; If the compiler knows where the references to an object are, and can presumably update them, why doesn't it update prev and next when it does the move?
Posted Sep 16, 2022 8:27 UTC (Fri)
by rsidd (subscriber, #2582)
[Link] (5 responses)
That is, if A refers to B, and you move B, you can update A since you know A refers to it. But if B refers to B and you move B, it doesn't update.
Why not (ie, why doesn't it recognize that B refers to B and update it) is an interesting question. Maybe it's somewhere deep in the language design: reference-counting doesn't include self-references? And maybe it's hard to fix?
Actually I have a more basic confusion: how does the compiler move objects in memory? Isn't that a run-time thing?
Posted Sep 16, 2022 10:33 UTC (Fri)
by Bigos (subscriber, #96807)
[Link] (4 responses)
When the object is owned, the compiler knows there exist no reference to it. It can then just update the internal state to know the location of the moved object without updating anything really. This is basically what happens when Foo::new() returns Foo object and you then Box::new() it to put it on the heap.
Self-referent types are foreign to the Rust borrow rules. You cannot have a reference to itself (the lifetime cannot be defined), so these are usually raw pointers in disguise. And Rust will happily memcpy raw pointers without any consideration as it is the user's responsibility to correctly maintain raw pointers (which is why they are unsafe to dereference).
So it is not about "A refers to B vs B refers to B" but "A has a reference to B vs B has a raw pointer to B".
And you cannot even move B if it is referred by A. If a type is referenced, it means it is borrowed and is no longer owned**.
Unlike C++, Rust has been designed not to be able to alter how object move is implemented. You thus cannot alter the memcpy behavior. This is why Pin<> is important as it effectively disallows object moves - which is necessary for self-referent types.
The thing about "compiler moving objects" is obviously a simplification. The object must be moved, i.e. placed in a specific memory location, and the compiler can use various strategies to make that happen. It can perform memcpy at runtime. Or it can make it so that the original object is created in the move destination already (often called "move elision").
* There is std::mem::swap() (and its friends) that can move things that are not owned but just referenced by an exclusive reference &mut T. However, we cannot really use these with self-referent types anyway.
** Again, exclusive references could make that happen. But if B has an exclusive reference to A, it is the only object that knows A's address, so only B has to be updated when A is moved. Exclusive references are not how you usually model a linked list as then you cannot even iterate over a list without consuming it.
Posted Sep 16, 2022 10:55 UTC (Fri)
by rsidd (subscriber, #2582)
[Link]
Posted Sep 16, 2022 14:34 UTC (Fri)
by kkdwivedi (subscriber, #130744)
[Link] (2 responses)
Posted Sep 16, 2022 15:03 UTC (Fri)
by mathstuf (subscriber, #69389)
[Link] (1 responses)
Posted Sep 16, 2022 22:34 UTC (Fri)
by ssokolow (guest, #94568)
[Link]
I'm not sure about the details in C++, so I don't know how they differ, but there's been interest and discussion around designing something placement new-like for Rust for a long time. (The earliest RFC I could find in a quick search was #1228 from two months after Rust 1.0 in 2015, and it's clearly a continuation of plans for placement new already in progress. My impression is that it just keeps getting bumped down the priority queue in favour of higher-demand/ROI things like support for C-style untagged (caniuse.rs is a good way to quickly get an overview of what got stabilized when and The Unstable Book is a good overview of the compiler features that are currently implemented for some definition of "implemented" but haven't been committed to stable channel and the language stability promise.)
Posted Sep 16, 2022 0:34 UTC (Fri)
by jengelh (guest, #33263)
[Link]
Posted Sep 16, 2022 7:49 UTC (Fri)
by epa (subscriber, #39769)
[Link] (5 responses)
Posted Sep 16, 2022 9:33 UTC (Fri)
by rvolgers (guest, #63218)
[Link] (4 responses)
Posted Sep 16, 2022 11:01 UTC (Fri)
by mathstuf (subscriber, #69389)
[Link] (3 responses)
But per the article, that's how an *empty* list is indicated. What is the actual encoding for a linked list of length 1?
Posted Sep 16, 2022 11:12 UTC (Fri)
by Wol (subscriber, #4433)
[Link] (1 responses)
So, and I'm GUESSING, a list with one value contains one entry with the value, and one null entry.
iiuc, this is how it knows where the head of the list is - it's the null entry.
Cheers,
Posted Sep 16, 2022 23:14 UTC (Fri)
by wahern (subscriber, #37304)
[Link]
Posted Sep 17, 2022 2:46 UTC (Sat)
by ejr (subscriber, #51652)
[Link]
Removals / deletions remain the pain point. Hence the RCU mechanisms.
Posted Sep 16, 2022 8:05 UTC (Fri)
by kkdwivedi (subscriber, #130744)
[Link] (2 responses)
One observation is that it is rare you'll be 'moving' around such a self referential struct, atleast for the list_head case. I can't find a lot of examples in the kernel where it can simply assume memcpy is equal to move for such cases. It really cannot. You have to have a 'move constructor' thing similar to C++ that does the non-trivial stuff for such special fields.
Even then, it's unlikely you're going to copy such structures around. Yes, that argument doesn't work from a language design standpoint, but at least for the BPF runtime it's going to hold. We're kind of designing the language and the standard 'BPF library' together in concert, to give a better analogy. So it's also possible to reap the benefits of such an approach.
Secondly, the core problem here is about initializing on stack and then moving into the Boxed object. Instead of that, as long as the pointer has not really escaped the program, it is technically possible to model the heap precisely, and track the state of fields. It would be the same as tracking the state of memory on the stack as long as it doesn't escape the program.
This initialization on stack and move might be the way Rust does things, and it may be non-trivial to accommodate such idea of direct initialization on heap into the language rules, but that is pretty much how we're planning to make it work properly for BPF.
It will be possible to also have such 'bpf_list_head' on stack, but then you'd call an initialization helper that does the right thing, and we already precisely track the state of stack in BPF, so we know its constructed and you cannot reinitialize it.
Ofcourse, one can argue that Rust's approach is much more systematic, applies evenly to more complicated cases, and doesn't really hard code semantics of a particular implementation, etc.
Posted Sep 16, 2022 20:30 UTC (Fri)
by riking (subscriber, #95706)
[Link] (1 responses)
Rust used to do this! It was called "box syntax". It's been removed on the crusade to make the compiler stop giving Box special permissions that mean you can't actually implement MyBox without being the standard library.
Posted Sep 20, 2022 1:34 UTC (Tue)
by cplaplante (subscriber, #107196)
[Link]
Posted Sep 16, 2022 21:42 UTC (Fri)
by comex (subscriber, #71521)
[Link] (6 responses)
A prerequisite to supporting structs that require in-place initialization for soundness is supporting in-place initialization in the first place (aka "placement new"). Rust has had a number of RFCs and other discussions about this, of varying levels of quality, over many years:
https://github.com/rust-lang/rfcs/pull/809
https://web.archive.org/web/20201109030838/https://github...
https://internals.rust-lang.org/t/pre-rfc-move-references...
https://github.com/rust-lang/rfcs/pull/2884
https://github.com/rust-lang/rust/issues/27779#issuecomme...
But I haven't seen a design that's truly satisfying.
One problem is that the most obvious design would be to take the idea of "out pointers" from C and add them to Rust in a compiler-enforced way, but this is impossible. Why not? Because Rust code is allowed to unwind on panic, in which case you'd return to an outer stack frame without actually initializing the pointer. Rust does support a no-unwinding mode, which is used by Rust for Linux and many other users, but it's not the standard mode, and Rust would be unwilling to add major language features that only work in this mode.
A bigger problem is that the existing ecosystem of Rust code is already used to initializing things out of place.
In C, if you're writing a function that initializes some struct, you'll probably have it take a pointer to that struct as an argument, and initialize it in place. In C++, class constructors always initialize the class in place. But in Rust, the current idiom is to have functions like `fn new() -> MyStruct`, which construct a local copy of the struct and then return it by value (implicitly memcpying it to the destination). If some new language construct is added for in-place initialization, it will probably become the preferred way to initialize everything, rendering all existing code unidiomatic and causing a ton of churn.
The most recent RFC I linked (from 2020) tries to sidestep that problem using the idea of guaranteed move elision of function return values, similar to what C++ added in C++17. A function like `fn new() -> MyStruct` is *already* transformed by the compiler into something like `fn new(out_ptr: *mut MyStruct)`. It takes a pointer and initializes it. So even without changing the source code at all, the compiler could theoretically generate code that initializes the struct in place. But instead it will usually create one or more temporary copies on the stack (on the caller and/or callee side) and memcpy between them. The idea here is to fix the compiler to stop making those copies, and then guarantee as a language feature that no copies will be made, under some reasonable conditions. That way you could get in-place construction everywhere, without having to change the idiom!
But this approach has serious limitations. Most importantly, a lot of functions are not `fn new() -> MyStruct` but rather `fn new() -> Result<MyStruct, MyError>`. In those cases, you might want the compiler to transform it to something like `fn new(out_ptr: *mut MyStruct) -> Option<MyError>` – that is, construct the MyStruct in place while returning the error separately – but currently you get `fn new(out_ptr: *mut Result<MyStruct, MyError>)` – that is, construct the whole Result object contiguously in memory. It's not clear to me if it's possible to transform it to the former without breaking language semantics in edge cases.
Another limitation is that it would still produce some API churn. Right now, you might write `Box::new(MyStruct::new())` (to put the struct in a new heap allocation) or `vec.push(MyStruct::new())` (to append the struct to a vector, which might require allocation). Ideally this kind of code would also magically get transformed by the compiler to initialize the struct in place. But as written, the code calls MyStruct::new() *before* allocating (and then moves the struct to the newly allocated destination), whereas in-place initialization would require allocating first. That's not a semantics-preserving transformation. So the 2020 RFC adds new functions that take closures: `Box::new_with(|| MyStruct::new())`, `vec.push_with(|| MyStruct::new())`. The function implementation would first allocate and then call the closure, avoiding the ordering problem. And since the struct is the closure's return value, return value move elision would kick in, rather than needing to create a separate 'function argument move elision' feature. Neat trick, but then there would be two different ways to create a Box or append to a Vec (creating churn), and the "best" way would be the uglier of the two. C++ has a similar problem, having added `emplace_back` to std::vector after previously having `push_back`.
And finally, if in-place initialization is treated as an optimization (even a guaranteed one), it might be confusing. It would be hard to tell just by reading some code whether the optimization is kicking in or not. And if this was extended to support self-referential structs, you'd end up with code that seems trivially unsound (making a self-referential struct and then moving it), which is only sound due to the 'optimization'.
So we're kind of stuck. Apologies for the off-topic rant, but this is one of my most-desired features in Rust, and I'm afraid the language is going to end up never supporting it.
Posted Sep 16, 2022 22:23 UTC (Fri)
by Wol (subscriber, #4433)
[Link] (4 responses)
So what's wrong/impossible about a "return by reference" version of new? Or does the borrow checker get itself in a tangle trying to work out who owns what? If return by reference can't support a chunk of "new" functionality, then that'll discourage people from using it unless they need to.
Cheers,
Posted Sep 16, 2022 22:45 UTC (Fri)
by ssokolow (guest, #94568)
[Link] (2 responses)
It's fundamental to the Rust semantic model that references don't transfer ownership of what they point to. Compiler transformations aside, returning a newly constructed object by reference would be like some of the UB cases that trip people up in C or C++ as far as programmer comprehension is concerned, and they're trying very hard not to become C++. (Discussion in RFCs spends time explicitly focusing on a given new feature's effect on the language's learnability and words like "complexity budget" get thrown around.)
Posted Sep 16, 2022 23:36 UTC (Fri)
by Wol (subscriber, #4433)
[Link] (1 responses)
(All this stuff feels odd to me, because as a FORTRAN and DataBASIC programmer, neither language has pointers, and even as a C programmer I never really used them. I always treated pointers like arrays.)
Cheers,
Posted Sep 17, 2022 8:51 UTC (Sat)
by ssokolow (guest, #94568)
[Link]
A pointer can be owned by an object, but you still have to either own what it's pointing to or use Rust's lifetime system to prove that it won't outlive what it points to. The former is how The latter is how Rust's reference types ( Owning bindings, by contrast, are mutually exclusive by definition. It's a potentially a bit misleading since the defining property of "owner" is "responsible for cleanup", so having two owning bindings to the same thing will result in a double-free. If it helps, think of Rust as a compiler that enforces compile-time-provable reader-writer locking. (That's what There is a way to make a reference that sort of owns itself... but it's using constructs like
Posted Sep 17, 2022 5:46 UTC (Sat)
by notriddle (subscriber, #130608)
[Link]
Naively, it would seem like the solution is to force the function to write to it using the same control flow analysis as used for locals. Unfortunately, because of unwinding, even something as simple as adding two numbers can result in exiting a function without writing to the out pointer, basically making it unusable.
Posted Oct 13, 2022 11:36 UTC (Thu)
by martinling (guest, #71591)
[Link]
I have sketched out another possible approach here, and would be interested in your thoughts on it:
Posted Sep 17, 2022 2:54 UTC (Sat)
by ejr (subscriber, #51652)
[Link] (4 responses)
Yeah, I have a formal background. And I have not learned much of Rust beyond things that could be taken disparagingly.
And then the next language, and the next... Rust, TO ME, seems a curly-braced attempt to be a more popular ML derivative. But I'm just me. There is no true language here. Just the ones we use to express intentions to the machines and each other.
Posted Sep 17, 2022 3:33 UTC (Sat)
by milesrout (subscriber, #126894)
[Link] (3 responses)
Rust is enthusiastically and proudly "ML with Algol syntax" at its core.
>C has mountains of undefined behavior. Is Rust defining some of that for more recent architectural views?
LLVM was designed to compile C++. It leaves a lot "undefined" because that behaviour is undefined in C++ anyway. There is no reason it couldn't all be defined as "whatever the hardware does" (which is very different from UB), but it just isn't.
Rust compiles to LLVM. That means that "unsafe" code in Rust can exhibit undefined behaviour, because it is implemented in terms of LLVM. There is, however, no reason why that would have to be so. Rust could give well-defined behaviour to every syntactically-valid program if it had its own backend. For portability, some things might behave differently on different platforms - it would still be well-defined, just defined as "depends on the platform, not portable behaviour" rather than "no idea, caveat emptor, if you do the wrong thing the compiler will optimise assuming that doing the wrong thing is IMPOSSIBLE, nasal demons, etc.".
Overall, Rust has much less undefined behaviour than C, and I think the goal is that all syntactically-valid programs that do not use "unsafe" will have entirely well-defined behaviour, even though it compiles to LLVM (i.e. the language/type system/borrow checker prevents you from doing things that would compile to LLVM IR that would exhibit UB). For example, signed overflow (and unsigned overflow, if I remember correctly) traps in Rust. If you want wrapping or saturating arithmetic you need to use special types. Those types also have well-defined (but different) behaviour.
Posted Sep 17, 2022 11:21 UTC (Sat)
by matthias (subscriber, #94967)
[Link] (2 responses)
This is exactly what the programming language that is called "safe rust" promises to provide. Every syntactically correct program in safe rust cannot produce undefined behaviour (modulo bugs in the compiler). However this is not what people want, at least not always. Unsafe rust is there to allow programs that do not have undefined behaviour, but still cannot represented in safe rust. E.g. using uninitialized memory. You cannot predict what you get when you just do a read on the memory. Of course you can enforce that all memory is initialized before first use. This is what safe rust does. But sometimes people want the extra performance that you can get by avoiding the initialization step. But then they have to prove that the code is sound, because they explicitly opted out of the compiler heuristics that automatically avoid initialization whenever the compiler can prove that it is safe to do, because the memory is written to before first use. And in the compiler there can only be heuristics, because the problem of computing whether there is some read before the first write is clearly undecidable. So there will always be cases where a human can prove that the program is sound, but the compiler cannot (because the used heuristics is not good enough).
Another category of clearly undefined behaviour are data races. In many cases not even the hardware defined clearly what can happen. Not only that the concrete behaviour depends on precise timings of events that you have no control over. But also what are the possible outcomes? Which reorderings are possible inside the CPU if you do not enforce memory barriers? Is it possible that you can read some clearly invalid data that results from a partial store? The hardware manufacturers will not provide any specs, because they want to have the freedom to change the inner behaviour of the CPU. Of course, you can enforce that there are always memory barriers in place. This is what safe rust does. Sometimes people want to have more performance by doing crazy optimizations themselves. This is what unsafe rust is. As also the problem of statically verifying whether there can be data races is undecidable, there can be no compiler that allows every program without undefined behaviour while rejecting all programs with undefined behaviour.
There is a constant development to increase the expressiveness of safe rust, e.g., have a better borrow checker that allows more code, because there are more cases where it can verify that the code is sound. Thus the things that you can provide in safe rust will grow. However there will always be unsafe rust for the cases that the compiler cannot (yet) verify.
TL;DR You already have the language that forbids undefined behaviour. It is called safe rust. And unsafe rust is especially there to allow programs where the compiler cannot verify that there is no undefined behaviour. As there will always be such programs and people want to have that extra performance gain, there is a place for unsafe rust.
Posted Sep 17, 2022 11:42 UTC (Sat)
by milesrout (subscriber, #126894)
[Link] (1 responses)
To be nitpicky: no it doesn't, because "safe Rust" does not give a meaning to every syntactically valid Rust programs - some of those programs use unsafe.
>However this is not what people want, at least not always. Unsafe rust is there to allow programs that do not have undefined behaviour, but still cannot represented in safe rust. E.g. using uninitialized memory. You cannot predict what you get when you just do a read on the memory. Of course you can enforce that all memory is initialized before first use.
"Well-defined" does not mean "predictable". Reading from uninitialised memory could be given a perfectly well-defined behaviour: you get unspecified results. Saying that uninitialised memory has unspecified contents is different from saying that reading from uninitialised memory is undefined behaviour. In the latter case, modern optimising compilers are designed around the assumption that they only compile code that does not exhibit undefined behaviour, which means that for example they assume that uninitialised memory is never read. That means that if you write a function that looks like this:
foo(y) {
then the compiler is permitted to assume that foo is only called with the parameter 0. If you call foo with a non-zero parameter, the compiler is entitled to optimise that out, because it is permitted to assume that that code is unreachable, etc. This is very different from saying "uninitialised memory has unspecified contents, may be anything, might be different each time you read it, might give you torn writes, etc."
Reading from uninitialised memory is still potentially *unsafe*, because you might get bit patterns that do not correspond to a valid element of the type: an uninitialised pointer of type 'NonNullPtr<T>' might happen to be 0. So it's still unsafe, but it doesn't have to be undefined. It could be well-defined but unspecified.
The same is generally true of all undefined behaviour. They didn't have to say "signed overflow is UB, and the compiler is permitted to assume that any branch in which signed overflow occurs is IMPOSSIBLE", and I don't think they even intended to do so. They could have said "signed overflow produces unspecified, potentially nondeterministic, but valid, results."
>Another category of clearly undefined behaviour are data races. In many cases not even the hardware defined clearly what can happen. Not only that the concrete behaviour depends on precise timings of events that you have no control over. But also what are the possible outcomes? Which reorderings are possible inside the CPU if you do not enforce memory barriers? Is it possible that you can read some clearly invalid data that results from a partial store? The hardware manufacturers will not provide any specs, because they want to have the freedom to change the inner behaviour of the CPU. Of course, you can enforce that there are always memory barriers in place. This is what safe rust does. Sometimes people want to have more performance by doing crazy optimizations themselves. This is what unsafe rust is.
The problem is that there is no in-between. There's no reason that there cannot be a mode "semisafe" halfway between safe and unsafe where these things have unspecified, platform-dependent, unknowable, possibly nondeterministic behaviour, but they still are always guaranteed to, at the very least, have behaviour of some sort. Compiler developers claim that this would result in huge numbers of lost optimisation opportunities, but I'm not sure I entirely believe them. As far as I know, the Linux kernel compiles with a few UB-assumption-based optimisations disabled (-fno-delete-null-pointer-checks, for example) and nobody is clamouring to re-enable them for the critical performance improvements that would entail.
Data races are relatively simple: just say "a read that races with a write may produce a value corresponding to any arbitrary bit pattern - the result will be implementation-dependent". Then the compiler developers can provide more details than that, they might say "aligned 64-bit values cannot result in tearing". Or they might not. Portable code could not rely on the behaviour of data races, but could at least rely on the compiler not doing really stupid things like optimising out safety checks that it thinks are unreachable based on some detected UB.
Posted Sep 17, 2022 12:44 UTC (Sat)
by matthias (subscriber, #94967)
[Link]
There is nothing well defined about this. The compiler will (and should) clearly assume that the pointer is non null. However it will be regarded as non-null in some cases (e.g. a test against 0 will be optimized away) but it will be null in other cases (e.g. before a copy there is no test against zero). The result of comparisons against this pointer will be non-deterministic, can be different every time you do a comparison. And this affects all the code dealing with this value transitively. There is no way of giving any sensible semantics to what can happen after reading uninitialized memory.
> Data races are relatively simple: just say "a read that races with a write may produce a value corresponding to any arbitrary bit pattern - the result will be implementation-dependent".
It is much more complicated than that. The problem is that one read in the programming language can lead to multiple reads in machine code. So you do not only get an arbitrary bit pattern, but also a bit pattern that suddenly changes at the moment where the value needs to be read a second time because it was evicted from the register. To guard against this in the presence of data races, every read needs to be changed to a copy. And this will clearly have some performance impact. And again this will effect anything that deals with this data value. If you pass the value to some function, the compiler is free to inline the function and inside this function you have a passed value that changes, just because it was evicted from the register and read a second time.
> ... where these things have unspecified, platform-dependent, unknowable, possibly nondeterministic behaviour, but they still are always guaranteed to, at the very least, have behaviour of some sort.
This is exactly what we call undefined behaviour. There clearly is some behaviour, but you cannot say which one it is. What do you want to do with a program that writes garbage to the stack (i.e. overwriting return addresses)? Clearly it will have some behaviour, but it is not defined in any way. You can do this in unsafe rust. If you want to disallow this in unsafe rust, you either have to solve the halting problem or to disallow many programs that do not have undefined behaviour. There is no other choice.
Posted Sep 17, 2022 18:53 UTC (Sat)
by willy (subscriber, #9762)
[Link] (6 responses)
11x. Think about that. No, I don't do much per entry, just load an int and accumulate it. Still, that's a good match for much kernel code.
Kernel programmers are terrified of allocating memory (because it can fail) and use these ridiculous data structures that avoid memory allocation instead. It's time to get over those fears and kill linux/list.h
Posted Sep 17, 2022 19:40 UTC (Sat)
by Cyberax (✭ supporter ✭, #52523)
[Link] (1 responses)
The other thing is the lifetime management. With standard growable vectors you need to manage the lifetime of the container and control references to the elements, because they might get invalidated when the container grows.
Posted Sep 17, 2022 19:51 UTC (Sat)
by willy (subscriber, #9762)
[Link]
Posted Sep 18, 2022 14:26 UTC (Sun)
by atnot (subscriber, #124910)
[Link]
At the time, I recall there were some discussions around the strong limitations Rust imposes on locking by requiring data to be wrapped in a lock type. There were lots of points about the sort of clever constructions that this would make more difficult. A few months later, there was an unrelated blog post series by Daniel Vetter[1] that heavily urged people to stop being so clever with their locking and design their architectures around simple locking hierarchies and sharing instead. The constraints there, like "Protect Data, not Code", having a clear relationship between locks and data, keeping the locking rules the same over time etc. heavily reminded me of Rust's rules, and the concerns I had seen about them before.
That is not to say that Rust's abstractions are infallible, perfect for the kernel, or always better than what the kernel has. But between locks, complex lifetimes and linked lists, it does create the impression that a lot of the difficulties are really going with the grain of where people have been wanting to move the kernel anyway. I'm curious if those examples will continue.
Posted Sep 19, 2022 4:40 UTC (Mon)
by koverstreet (✭ supporter ✭, #4296)
[Link] (1 responses)
Lock waitlists are typically short - expected length of 1! - and we aren't ever walking the whole thing, the operations are adding to the end of the list and waking up the waiter at the head of the list, so we actually end up with less pointer chasing with a linked list.
Posted Sep 19, 2022 7:04 UTC (Mon)
by willy (subscriber, #9762)
[Link]
Posted Oct 3, 2022 20:19 UTC (Mon)
by Vipketsh (guest, #134480)
[Link]
With array walking you don't have that dependency chain so the processor can load the next pointers out-of-order with whatever processing occurs on the element and operate on a whole slew of elements in parallel. As soon as the amount of processing on each element exceeds the CPU's speculation window (or is barred from doing so, by e.g., a branch miss predict) the array walk won't be much faster than the linked list, if at all.
When benchmarking you really need to know what you are benchmarking. In this case you are checking your CPU's speculation performance, which may not be what you really wanted to measure. As another random example: a few decades ago the drhystone benchmark was very popular. These days you don't see much of it because it is so short that in effect it is benchmarking the CPU's speculation window of how many iterations of the benchmark's loop it can execute in parallel and little on how fast the CPU can finish the calculations in it (amongst various other problems).
A data structure needs to be evaluated by a lot more metrics than a (non-realistic) performance measurement on traversal, for example:
Every data structure has its place, even if you have a serious dislike for it.
The perils of pinning
The perils of pinning
The perils of pinning
The part of the article and my question was about building.
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
In C every statement is unsafe.
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
Wol
The perils of pinning
The perils of pinning
> at an actual NetworkBuffer with a "volatile" qualifier and so then we can go around
> doing operations to it, even though in practice that's a bad idea and the only thing
> we ought to do is copy it somewhere. On a good day that's all the C (or worse C++)
> does with a volatile, on a bad day you need to guess whether the programmer knew
> what's really going or whether the code you're reading is full of unintentional races.
function in C
the compiler stops any assumption to the pointed data.
The perils of pinning
struct NetworkBuffer {
struct IpHeader ip_hdr;
union {
struct TcpSegment tcp;
struct UdpSegment udp;
};
};
volatile * NetworkBuffer buf;
The perils of pinning
> (Of course assembler will let you, because assembler has no formal model.)
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
Wol
The perils of pinning
The perils of pinning
The perils of pinning
> AFAIK, the term itself is not a "Rust community" term.
The perils of pinning
It is the programmer's responsibility when writing
unsafe code to ensure that any safe code interacting with the unsafe code cannot trigger these behaviors. unsafe code that satisfies this property for any safe client is called sound; if unsafe code can be misused by safe code to exhibit undefined behavior, it is unsound.
If it doesn't handle all cases, then I would call it incomplete. To be unsound would mean it can produce incorrect results.
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
If you take a struct in C and pass it somewhere by value, that struct is now in a new location. If you do that with a self referential struct, it is now invalid in the new location.
C only has copies, not moves, so the result is completely valid. It's just that the new object is not self-referential anymore: its pointers refer to the old object instead. But these pointers remain valid while the old object is still around. That's completely different with Rust move semantics.
The perils of pinning
Everything else is the same.
Rust can't rip out memory from your machine. Therefore it also technically copies.
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
- the object is moved from the stack to the heap
- the object is moved between different allocations on the heap
- the object is moved to a function parameter (if the function is not inlined, then the object has to be moved to the place where the function expect its input, for inlined funtions, the move will usually be avoided)
The perils of pinning
Rust can't rip out memory from your machine. Therefore it also technically copies.
Aren't Rust semantics such that the moved-from object becomes invalid as part of the move? What happens in a concrete computer implementation does not really matter for correctness if the abstract machine behaves differently. If the object is gone in the abstract machine, compilers can and will eventually optimize based on the assumption that accesses to it will not happen during the execution of the program.
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
NULL pointers and thus never need to deal with them.
> 1) Why thought? Isn't the idiomatic C way setting the next and prev to 0? Assuming that is not possible in rust (to prevent null dereference I assume), why not use rust-version of std::optional?
The perils of pinning
unsafe but nullable. Using <Option> would be bad idea, though.unsafe Rust, too.unsafe which you have to carefully review and where compiler doesn't guarantee anything, then what's the point? C already gives you means to do that!The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
("&mut T" should really be called an exclusive reference (while "&T" is a shared reference), because "mutable reference" is actively misleading. I think the "mut" keyword is a design flaw in the language, albeit a fairly minor one that could be worked around with better documentation, and it's possible all the other proposed solutions were equally flawed. See also https://docs.rs/dtolnay/latest/dtolnay/macro._02__reference_types.html which makes the same points.)
There was actually discussion around that (&mut being better as something like &uniq), but it didn't go anywhere.
People who want more information should search "mutpocalypse". (It's been many years but, if my mental timeline is correct, coined as a callback to the "leakpocalypse", when it was discovered that the first attempt at a scoped thread API was unsound in the face of things like memory leaks from Rc/Arc reference cycles.)
The perils of pinning
>The 100Gbps driver does need to write unsafe code to initialize a NetworkThing in its fast path, but the USB ethernet driver does not, in exchange for which it's a little slower than it might have been. That feels like a reasonable trade.
The perils of pinning
unsafe behind pile of macroses.async why not here, too?The perils of pinning
I am guessing it knows where the references to an object are other than self-references.The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
unions in the FFI side of things (yes, they weren't present in stable-channel Rust until version 1.19), async/await, GATs, and so on.The perils of pinning
On the other hand, if a language can't directly deal with self references (list_head won't be last struct of such kind), then maybe it's not the right language to start with.
Linked list start and end
As an example, initializing a list_head structure to indicate an empty list is done by setting both the next and prev fields to point to the structure itself.
Why is this done? Wouldn't it make more sense to set these two fields to null?
Linked list start and end
Linked list start and end
Linked list start and end
Wol
NULL isn't used as a sentinel for this type of list, the head itself is the sentinel. See, e.g., https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?h=v6.0-rc5#n290
Linked list start and end
static inline int list_empty(const struct list_head *head)
{
return READ_ONCE(head->next) == head;
}
and https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/list.h?h=v6.0-rc5#n368
static inline int list_is_singular(const struct list_head *head)
{
return !list_empty(head) && (head->next == head->prev);
}
Linked list start and end
The perils of pinning
This is also possible to do when you receive ownership of an object from an 'external' source, but then the default state you can assume for the fields is unknown. This can be further refined by ensuring they are only manipulated using some specific functions, and then you can reason more precisely about the state of the fields (either pointing to itself or to some other list_head).
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
Wol
The perils of pinning
The perils of pinning
Wol
The perils of pinning
Box<T>, Rc<T>, Arc<T>, Vec<T>, etc. are implemented. They use unsafe and Raw/C-style pointers internally, but the part that lives on the stack is still singly-owned... things like Rc and Arc just use internal reference counts and raw heap pointers to implement multiple ownership in a "Compiler, you can't verify this, but I've audited it and it works" way and, instead of the compiler inserting memory-freeing code, their implementation of the Drop trait (effectively, a destructor) decrements the reference counts and/or frees the memory allocated when they were initialized as appropriate.& and &mut) work. Any object which contains a reference must expose that reference's lifetime as part of its type signature, and then the compiler solves the resulting system of constraints to prove that dangling pointers are not possible.& vs. &mut is, but the analogy can be useful for thinking about owner vs. borrows.) You're essentially asking why you can't force the reader-writer lock to hand out two exclusive/writer handles simultaneously.Box::leak, which are intended for detaching something from the ownership system without freeing them. They're mainly intended for two situations:
Box::from_raw to reattach it to the ownership system, and then letting it drop to free it with the same allocator that allocated it.The perils of pinning
The perils of pinning
How much of this is that a new language displays undefined behavior in a preceeding language?
How much of this is that a new language displays undefined behavior in a preceeding language?
How much of this is that a new language displays undefined behavior in a preceeding language?
How much of this is that a new language displays undefined behavior in a preceeding language?
int x;
if (y == 0) {
x = 0;
}
printf("%d\n", x);
}
How much of this is that a new language displays undefined behavior in a preceeding language?
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
The perils of pinning
- Cost of insertion/removal (quite high for an array-of-pointers)
- Cost of the operation v.s. the walking
- Operation context considerations (e.g. places you can't allocate memory -- free list for an allocator?)
- Limitations on the array size (the kernel doesn't like to do high-order allocations)
- The cost of traversal may not matter (think LRU type structures)