search

fitzgen / bumpalo

A fast bump allocation arena for Rust
https://docs.rs/bumpalo
Apache License 2.0
1.36k stars 111 forks source link

Remove ptr-int-ptr casts #145

Closed saethlin closed 2 years ago

saethlin commented 2 years ago

This replaces ptr-int-ptr roundtrips as well as ptr-int casts which were used to produce usize values to do arithmetic on instead of doing pointer arithmetic operations on pointers to u8. These ptr-int-ptr roundtrips are a thorny case for aliasing models to deal with, and thus play havoc with unsafe checkers such as Miri, and complicate alias analysis and aliasing models. Removing them does not necessarily remove UB, but it significantly simplifies the semantics of this code and makes it easier to rule out definite forms of UB.

saethlin commented 2 years ago

This PR is not concerned with ptr-int casts, it is concerned with ptr-int-ptr roundtrips done via casts (doing the roundtrip by transmutes is UB for sure, just to head that off). The problem with these roundtrips is that selecting a provenance for the new pointer is a nightmare. As far as I can tell, a formal aliasing model which supports provenance-based optimizations (which are done in all major compilers) needs to pick at least one of:

  1. Ban restrict/noalias from the language (rustc already emits noalias so this would be a bit odd)
  2. Pick a model that has (exponential?) state space explosion/memory usage inside a checking interpreter
  3. Rely on a very complicated formal model which nobody has yet come up with
  4. Make dereferencing a pointer that has been round-tripped through an integer UB

It seems like C is going for option 2 and Rust is going with one of 3 or 4. Option 4 is the only option which is actionable for users of Rust code, and I'm pursuing it because it's the only way we have to run a checker for an aliasing model which accomodates the optimizations produced by LLVM's noalias attribute, which rustc currently applies to mutable references. This is MIRIFLAGS=-Zmiri-tag-raw-pointers. By default Miri checks a more complicated aliasing model which permits integers to be cast back to pointers, but it permits code which is UB with how rustc currently emits noalias.

The Strict Provenance experiment is concerned with eliminating ptr-int casts. It would be nifty if we could do this, but doing so is not an option for library implementors right now because the whole idea relies on a bunch of standard library APIs that are behind a feature gate, and the API you're supposed to use to inspect the bits of a pointer is currently implemented with a ptr-int cast with a TODO comment about making it an intrinsic.

Alignment checks in particular suck. A lot. We should eventually have a #![feature(strict_provenance)] API for doing alignment checks. Currently, align_offset exists but (and it documents this clearly) it is completely broken in const fn and perhaps in Miri (because Miri mostly uses the const fn machinery).

fitzgen commented 2 years ago

Ah okay, thanks. I was misunderstanding that it is specifically the last link of pointer --> int --> pointer that this PR was eliminating. Everything makes sense now.

Happy to merge once the nitpicks are addressed.