Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Stacked Borrows and VolatileCell #265

Closed
chorman0773 opened this issue Dec 15, 2020 · 19 comments
Closed

Stacked Borrows and VolatileCell #265

chorman0773 opened this issue Dec 15, 2020 · 19 comments
Labels
A-memory Topic: Related to memory accesses

Comments

@chorman0773
Copy link
Contributor

chorman0773 commented Dec 15, 2020

I have a type in a library for embedded development, called VolatileCell<T>, which sits over a memory address, and provides shared volatile access. However, I have been told this is unsound, as it uses &VolatileCell<T>, which allows synthesized reads.
This, however, got me thinking. Would this not also apply inherently to any Sync wrapper on an UnsafeCell, which offers mutation, such as Atomic or Mutex? After all, if the compiler can insert normal reads to the bytes behind an UnsafeCell, and a different thread performs even an atomic write that's not protected by a happens-before relationship, that a data race and immediate UB (according, at least, to the C++ memory model, which I have not heard rust diverge from enough to save this).
I'm wondering if it makes sense to relax the rules for references, to "if a read occurs, it can be moved anywhere in the function (absent operations that bar reordering), even if the read may not be evaluated", rather than "the compiler can invent reads out of thin air", at least for things that contain an UnsafeCell.

Note: While the post is asking specifically about VolatileCell and a similar AtomicCell which derives from it (and locks interrupts on reads/writes, giving interrupt-level atomicy), it generalizes to any such abstraction.

@RustyYato
Copy link

iirc The difference is that volatile reads are effectful, but reads to atomics/mutex/etc. are not. i.e. reading from volatile memory can have side effects.

@chorman0773
Copy link
Contributor Author

Indeed, though, I'd argue that "undefined behaviour" is effectful. While it's not necessarily a problem where a data race merely has compile-time effects, one could imagine an target where concurrent access to a memory location isn't permitted, and traps in some way (possibly with SIGBUS or an equivalent).

@chorman0773
Copy link
Contributor Author

I'd also note, I don't believe llvm allows dereferenceable(n) pointers to just be read out of thin air (please correct me if I'm wrong), but it follows my suggested behaviour which is "reads in this function may be moved arbitrarily, provided they aren't blocked by some fence or synchronization op".

@RustyYato
Copy link

https://releases.llvm.org/8.0.1/docs/LangRef.html

dereferenceable(< n >)
This indicates that the parameter or return pointer is dereferenceable. This attribute may only be applied to pointer typed parameters. A pointer that is dereferenceable can be loaded from speculatively without a risk of trapping. The number of bytes known to be dereferenceable must be provided in parentheses. It is legal for the number of bytes to be less than the size of the pointee type. The nonnull attribute does not imply dereferenceability (consider a pointer to one element past the end of an array), however dereferenceable() does imply nonnull in addrspace(0) (which is the default address space).

So spurious reads to dereferenceable is allowed in LLVM.

@chorman0773
Copy link
Contributor Author

Brilliant. I suppose that works fine in llvm, as a data race yields poison, not UB. Though I think my general point for SB stands (though having this feature would be useful, as I am not a fan of "magic pointers", and in some cases, an address I need volatile access to may not be fixed at compile time). The compiler can spuriously read a &AtomicU8, and in rust, if that causes a data race (which can happen if a different threads writes to it, unsequenced from the read, all of these ops are safe), that is UB.

@RalfJung
Copy link
Member

The compiler can spuriously read a &AtomicU8, and in rust, if that causes a data race (which can happen if a different threads writes to it, unsequenced from the read, all of these ops are safe), that is UB.

Indeed, as you observed, the Rust compiler is not allowed to insert spurious MIR-level reads in situations where that might introduce a data-race (basically, when there is an UnsafeCell). However, it is conceivable that Rust/MIR could internally have another kind of non-atomic read where data races are not UB, and instead yields Uninit. Those reads could be spuriously introduced. Just because such reads currently do not exist in MIR, does not mean that they can be introduced later (and introducing them would not be considered a breaking change currently).

@RalfJung RalfJung added the A-memory Topic: Related to memory accesses label Dec 19, 2020
@chorman0773
Copy link
Contributor Author

chorman0773 commented Dec 19, 2020

Just because such reads currently do not exist in MIR, does not mean that they can be introduced later

Indeed. My proposal is that, to support abstractions that depend on the read not occuring, we provide that such reads cannot be introduced in this case, unless they already exist within the function. It would also include that the compiler cannot permit llvm to introduce any reads either in this case (that is, when an UnsafeCell is involved).

I would add that, to benefit optimizations, merely the fact that the read operation occurs within the function (even if it's not evaluated), protected by any kind of reordering barrier, should be sufficient to allow non-volatile reads to be moved and introduced. I can't see a circumstance where optimizations could benefit from spuriously reading something that is never read by a function, or that is only read using read_volatile.

Possible wording for this could be:

A read to a pointer or reference potentially occurs during a call to a function if evaluation of any full expression would result evaluate a call to core::ptr::read, core::ptr::read_unaligned with that pointer as an argument, or that copies or moves out of the result of dereferencing the pointer, even if that expression may not be evaluated as part of a call to the function. If a read of a reference potentially occurs, the implementation may assume that no side effects occur as a result of evaluating the read Note - the behaviour is undefined if such an assumption is made, and a side effect would occur as a result of that read - End Note.

@chorman0773
Copy link
Contributor Author

chorman0773 commented Dec 19, 2020

I would add that these rules would be necessary to have an operation be both atomic and volatile, IE. guaranteed for it's side effects, and well-ordered wrt. other threads of execution. (Something necessary for the api, as it has to communicate with interrupt handlers)

@RalfJung
Copy link
Member

merely the fact that the read operation occurs within the function (even if it's not evaluated), protected by any kind of reordering barrier, should be sufficient to allow [...]

I think we should stick to the principle that dead code has no effect. It will be really hard to have a proper Abstract Machine definition otherwise.

I am also not sure why you are proposing a spec change; what is the intended effect of this? Do you want to make VolatileCell sound? There has been lots of prior discussions on this and the two main ideas are:

  • Have some kind of type which opts-out of dereferencable the way UnsafeCell opts out of noalias.
  • Ask people to use raw pointers instead of references, possibly a more ergonomic form of raw pointers (&unsafe or whatever).

@chorman0773
Copy link
Contributor Author

chorman0773 commented Dec 21, 2020 via email

@Lokathor
Copy link
Contributor

Note that it is already possible to use volatile soundly by storing and passing the address (as a newtyped ptr or usize) rather than using the Cell pattern.

Which isn't to say that the other proposed fixes can't still improve the situation further.

@chorman0773
Copy link
Contributor Author

chorman0773 commented Dec 21, 2020 via email

@Lokathor
Copy link
Contributor

In that situation, something like this would probably work.

let vol_addr = VolAddr::new(SYMBOL as usize);

@repnop
Copy link

repnop commented Jan 14, 2021

This pattern of &VolatileWrapper where the wrapper contains UnsafeCell and you're expected to access it via a reference to then do volatile read/writes seems to be extremely common in the ecosystem for MMIO, like volatile and register, and I would imagine the way most implement their own types (like I have in my projects) because it provides a really ergonomic interface since all you need to do is model the layout of the mapped registers in a struct and access fields as you would with any other struct.

The alternative, from what it sounds, is to make a wrapper type that stores only a pointer to the base of the memory region, then exposes the fields as a type that wraps the pointer to that field, which doesn't seem as nice as just modeling it as a regular struct type by using a RawCell type that opts out of dereferencable, which then also makes fixing the already existing crates a lot easier so I +1 that solution if its something that could happen.

Otherwise, it seems likely that a proc macro to generate an interface from a layout definition would be the easiest thing to do, which can be undesirable because of the impact that proc macros can have on compile times and its quite possible to have many such structs in a single crate that needs to access a lot of memory mapped devices. If anyone has any other suggestions for how this could be done though, do mention 👍

@Lokathor
Copy link
Contributor

That's not really how you'd model it

@RalfJung
Copy link
Member

That's not really how you'd model it

Do you have an example for how one would model it?

@Lokathor
Copy link
Contributor

Okay so I ended up having this chat with Repnop on Discord, so let me put down some notes.

I'd like to prefix things with a big warning: Everything I'm about to suggest is about Rust as-is, not about how Rust should be. I'm describing the best setup to use in a world where &UnsafeCell is broken for MMIO, but I'm not saying that it should be broken for MMIO like it is. We can discuss the details of different possible fixes separately (because I also want MMIO to be much better than it is!), but for this post I'm focusing on "rust today".

Okay so repnop (via Discord) had an example struct like this:

#[repr(C)]
pub struct Plic {
    source_priorities: [registers::Priority; 1024],
    interrupt_pending: registers::InterruptPending,
    _padding1: [u8; 3968],
    interrupt_enable: [registers::Context<registers::InterruptEnable>; 15872],
    _padding2: [u8; 57344],
    threshold_and_claim: [registers::Context<registers::ThresholdAndClaim>; 15872],
    _padding3: [u8; 8184],
}

And then was thinking that you'd have something like:

let my_plic_addr = VolAddress::new(0x123456 /* wherever */);

And then you'd read and write my_plic_addr . This is what you don't do.

That's absolutely too much data to be reading and writing all the time. A VolAddress should point to a type that's register sized or smaller. Something you can read or write as a single instruction. Not because it must, but simply because that's what's going to give you good performance, otherwise you're doing excessive reading or excessive writing.

So what you'd do instead is similar to what repnop said, except that we'd manually "push down" the volatile property to the "fields" by making them methods which return the correctly offset address from the base address of our "struct".

pub struct PlicAddr(usize);
impl PlicAddr {
  // here, use min_const_generics, or possibly typenum crate on older compilers
  pub fn source_priorities(self) -> VolBlock<registers::Priority, 1024> {
    VolBlock::new(self.0)
  }
  pub fn interrupt_pending(self) -> VolAddress<registers::InterruptPending> {
    // offset to this "field" manually
    VolAddress::new(self.0 + size_of::<registers::Priority>() * 1024)
  }
  pub fn interrupt_enable(self) -> VolBlock<registers::Context<registers::InterruptEnable>, 15872> {
    // offset manually
    VolAddress::new(self.0 + size_of::<registers::Priority>() * 1024 + 3968)
  }
  // etc etc
}

(In the case of an array, you'd use a "Volatile Block" type that allows further indexing from its own base address to a position within the memory block. This is provided in the voladdress crate but there's nothing magical about it and you can write your own.)

I agree that it's more trouble to write it out like this, but it's a very obvious sort of code translation so a proc-macro (or even a macro-rules) can do it fairly simply. And this generally goes into a "hardware definitions" crate so it's not like you're re-running the whole proc-macro all the time.

In terms of readability of this code style, your code would go from being something like

p.source_priorities[5].read()

into something more like

p.source_priorities().index(5).read()

Which is certainly close enough to my eyes.

And again, I don't think Rust should always work like this, I just think that this whole dumb thing is what you have to do until there's whatever Language level changes made in the future to make MMIO not be a second class citizen.

Personally, I'd just like a *vol T type. Probably the simplest fix.

@elahn
Copy link

elahn commented Jan 25, 2022

Just because such reads currently do not exist in MIR, does not mean that they can't be introduced later

I really want to use this to do a non-atomic search for zero-values, followed by:

compare_exchange_weak(0, new_value, Ordering::AcqRel, Ordering::Relaxed)

If it fails, keep searching and try again. Uninit is perfect for a heuristic search.

Thank you, @Lokathor. Voladdress is awesome! I'll use read_volatile() until things change. 🙂

@chorman0773
Copy link
Contributor Author

Mentioned in connection to #33 today during the Backlog Bonanza. This issue is being closed in favour of #411.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
A-memory Topic: Related to memory accesses
Projects
None yet
Development

No branches or pull requests

6 participants