Make force_ptr a total operation, and ptr-to-int-casts not require extra machine state

[RalfJung]

Currently, force_bits is a total operation in the sense that it will never go wrong in Miri (it can fail in CTFE though), but force_ptr can fail. That is very annoying, it means that we have to call force_ptr at just the right spot or we'll either causes errors in well-behaved code by converting too early, or re-do the conversion all the time because we do it too late. (See rust-lang/rust#62441 for some very careful force_ptr placement.)

I think it might be a good idea to make force_ptr never fail. The way this could be done is by designating a particular AllocId as representing the "integer allocation" and having base address 0, so that a pointer with offset o is equal to the integer o. This would mean that every pointer-sized value has two equivalent representations (returned by force_bits and force_ptr, respectively) -- which is maybe suboptimal, but IMO it is better than the current situation where only some pointer-sized values have two representations.

Potentially, that would also let us use Pointer instead of Scalar in MemPlace, simplifying (I think) lots of code. However, that would mean even CTFE has two different representations for the same value. But given that the engine will have to handle that anyway, I am not sure if it is a problem.

@oli-obk will recognize this as basically bringing back the "ZST allocation" or whatever it used to be called. It was a mess back then, but I think removing it only helped because it meant we had a canonical representation for every value -- a property we already lost with intptrcast.

What do you think?

Current proposal: #841 (comment)

[oli-obk]

🤣 do it.

Long version:

There are two kinds of ConstValue::Scalar that we really use in the compiler: array sizes and enum discriminants. I do not think we'll get a measurable perf impact if we stop using ConstValue::Scalar for anything but array sizes. What we will get though is a measurable memory usage reduction if we stop using 128 + 8 bits for a scalar (plus loads of padding) and just use Pointer everywhere. The other cases would be encoded via ByRef.

Now if we suddenly get many many more integer constants (non-usize) due to const generics this may become an issue. cc @eddyb @varkor

We've gone back and forth on this topic. I don't think it's a problem, it's more like we're moving from a local minimum to another. But if we get something out of it, let's do it.

[eddyb]

Can we keep ConstValue the way it is today and only have the allocation hack within miri itself?
And using something called Pointer everywhere seems a bit silly IMO, at that point you can just rename it to Scalar?

[oli-obk]

Well, it's specifically PointerSizedScalar, maybe RawPointer?

[eddyb]

TargetUsizeScalar? But really, all it is is Scalar64 :P

EDIT: but I'd prefer if we kept the full u128, unless it's bad for perf or something.

[RalfJung]

There are two kinds of ConstValue::Scalar that we really use in the compiler: array sizes and enum discriminants. I do not think we'll get a measurable perf impact if we stop using ConstValue::Scalar for anything but array sizes. What we will get though is a measurable memory usage reduction if we stop using 128 + 8 bits for a scalar (plus loads of padding) and just use Pointer everywhere. The other cases would be encoded via ByRef.

So you are saying that ConstValue should also change? I did not think it would, but sure.

That makes naming annoying though, indeed. One crucial property of Pointer is that if it is dereferencable, then it will have a "valid" AllocId and does not need any further conversion or so to be used for memory accesses. PointerSizedScalar lacks that connotation.

[RalfJung]

What would be even better is if we could somehow move from "either 128 or Pointer" to "always a memory address, sometimes with provenance".

When defining a formal memory model with int-ptr-casts, the best choice (in my opinion) is to say that a Pointer is basically an integer (corresponding to the actual value this pointer is going to have on the machine) "plus stuff". That stuff is called "provenance", and the UCG glossary now contains an example. This has several advantages:

• Getting the "run-time representation" of a Pointer is a "pure" operation that can be defined on the value itself, without having to talk to any kind of global state. So something.force_bits(size) would be possible.
• When doing a partial load of a pointer from memory, if we just look at the representation bytes and ignore the "relocations" (should be called "provenance" then), we basically get the result of a ptr-int-cast, which makes partial loads very easy to implement.
• When doing pointer arithmetic that has to be checked for overflow, we can actually do this properly (currently we check if the offset overflows, which is not the same thing).

So if we had just Miri to consider, I would lobby heavily for doing it this way. It'll make things much simpler. But we also have CTFE to consider, and CTFE does not want to support ptr-int-casts. So if we want to go with this strategy, we need some way to abstract this that is not messy. I'll think about this. Any proposals?

[oli-obk]

we could eagerly create integers by checking a flag on the engine. We'd not have the additional provenance of the AllocId though, you'd need to call int->ptr to get that, which may be expensive to to everywhere

[RalfJung]

Well also CTFE would then have to pick a base address, which does not seem great.

What about (something like) this: we define Scalar as:

struct Scalar<Tag> {
  /// The size of this scalar, in bytes.
  size: u8,
  /// The raw data of this scalar. All but the least significant `size` bytes are 0.
  raw: u128,
  /// If this is a pointer, the allocation it points to, and further machine-dependent provenance.
  ptr_provenance: Option<(AllocId, Tag)>,
}

(Maybe we can save some space by e.g. exploiting that a Scalar with an alloc will always be ptr-sized, so it technically does not need the size field and could use a shorter bits field. But this is just conceptual anyway.)

Then we can have a machine function that can turn a Scalar into Option<(AllocId, Size)> (an alloc-offset pair), which forms the basis for every memory access. CTFE would just convert raw to Size, but Miri could start by reading the provenance to get the AllocId and take into account the allocation's base address, and if there is no AllocId it could to the int-to-ptr-cast-thing.

We would also have a machine function that can turn a Scalar into Option<u128>, and that function would not have access to any machine state. For CTFE, if provenance is set, this fails (pointers cannot be turned into raw bits); but otherwise (and on Miri) it just returns raw.

The benefit is basically what I laid out above. In memory, the ptr_provenance part of the data would be stored "out-of-band" like relocations, but the raw would be stored directly. In particular, this means that when running in Miri, if we ignore the out-of-band data, we don't get garbage -- we get the result of a ptr-to-int cast! This would make @christianpoveda's live infinitely easier when implementing partial loads of a pointer.

The risk here is that we must make sure that nothing in CTFE thinks the raw bits actually have any meaning except when ptr_provenance is None. We thus also have to be careful about "forgetting" that provenance. So, these operations should likely all be run through some machine functions to make sure the engine cannot get this wrong.

So, taking this into account, maybe Scalar should look more like this:

/// Look ma, the fields are private!
struct Scalar<PtrData> {
  /// The size of this scalar, in bytes.
  size: u8,
  /// The raw data of this scalar. All but the least significant `size` bytes are 0.
  raw: u128,
  /// If this is a pointer, the machine adds some provenance.
  ptr_data: Option<PtrData>,
}

impl<PtrData: PtrProvenance> Scalar<PtrData> {
  // Some methods will require this `PtrProvenance` trait.
}

trait PtrProvenance {
  /// Whether with this provenance, it is legal to access the `raw` part of a `Scalar` directly.
  const ALLOW_RAW_ACCESS: bool;
}

trait Machine {
  type PtrData: PtrProvenance; // replaces `Tag`

  fn get_ptr_alloc_offset(&InterpCx, ptr: Scalar<PtrData>) -> InterpResult<'_, (AllocId, Size)>;
}

This way, at least there is no way for anything to use the AllocId in Scalar the wrong way, it all goes through get_ptr_alloc_offset. Then if we also make bits private and make sure the methods on Scalar always check ALLOW_RAW_ACCESS before handing out any bits, we know that raw bits will also only be interpreted the right way.

If we wanted to be really sure about that, we would have to put the u128 into the machine as well... well at that point we would basically put Scalar into the machine, with a trait like

trait ScalarT: Copy {
  fn from_int(...) -> Self;
  fn from_uint(...) -> Self;

  fn to_bits(self) -> InterpResult<'_, u128>;
}

trait Machine {
  type Scalar: ScalarT;

  fn get_ptr_alloc_offset(&InterpCx, ptr: Scalar) -> InterpResult<'_, (AllocId, Size)>;
}

That seems extreme. But maybe it actually helps?

EDIT: Ah, but ScalarT would need to offer some way to converted scalars into whatever can be stored in memory. So we likely could not entirely seal access to bits even for CTFE, Allocation after all needs those bits to store them separate from the out-of-band data.

[oli-obk]

(Maybe we can save some space by e.g. exploiting that a Scalar with an alloc will always be ptr-sized, so it technically does not need the size field and could use a shorter bits field. But this is just conceptual anyway.)

That's what we do today. We have an enum around the two cases. And I think we should keep it (for the memory size benefits). You can just wrap it in a newtype and add the accessors on that. Best of both worlds.

What will ctfe do with bits? Also store the result of a ptr to int cast? or will we get some difference between ctfe and miri?

[RalfJung]

That's what we do today. We have an enum around the two cases. And I think we should keep it (for the memory size benefits). You can just wrap it in a newtype and add the accessors on that. Best of both worlds.

That might be the conclusion here, yes. The Pointer type would go away though, embedded into Scalar::Ptr, and offset would be renamed to address.

What will ctfe do with bits? Also store the result of a ptr to int cast? or will we get some difference between ctfe and miri?

My thinking was it would store the offset in the bits. We don't want anything resembling ptr-to-int casts in CTFE. So yes there would be a difference between CTFE and Miri, that's why I proposed some trait stuff above.

[RalfJung]

My hope was we could first talk conceptual and then see how we can get the memory size optimized again, but maybe that doesn't work so well, so here's a strawman proposal:

Instead of Tag, we make PtrData part of the Machine trait. And there's also a trait for it, tentatively called PtrToInt:

/// The fact that these are two variants should mostly not be visible to the outside.
/// Storing things into an `Allocation` should be the only time this abstraction is ever
/// "lifted" -- that's both in the `rustc::mir::interpret` module so we can even help a bit with privacy!
enum ScalarPriv<PtrData> {
  Raw { /* like now */ },
  Ptr { addr: u64, data: PtrData },
}
/// We want to keep the ScalarPriv constructors are private, so we need to wrap this.
pub struct Scalar<PtrData>(ScalarPriv<PtrData>);

trait PtrToInt {
  /// Says whether the `addr` field of `ScalarPriv::Ptr` can be interpreted as raw bytes.
  const ADDR_IS_RAW: bool;
}

// Some `Scalar` methods need that trait.
impl<Ptr: PtrToInt> Scalar<Ptr> {
  // Internal helper methods:
  fn get_size(self, cx: &impl HasDataLayout) -> Size {
    let this = self.0;
    match this {
      Raw { size, data } => Size::from(size),
      Ptr { .. } => cx.pointer_size(),
    }
  }
  fn try_get_bits(self) -> Option<u128> {
    let this = self.0;
    match this {
      Raw { size, data } => Some(data),
      Ptr { addr, data } => if PtrToInt::ADDR_IS_RAW { Some(addr as u128) } else { None },
    }
  }
}

trait Machine {
  /// Extra data carried with each pointer.
  /// This type also defines how the `addr` field in `ScalarPriv::Ptr` is being interpreted!
  type PtrData: PtrToInt + Copy;

  /// "int to ptr" cast.
  /// This forms the basis for a "normalization" method that adds `PtrData` to a `Scalar` that doesn't have it yet.
  /// Note that this method cannot fail!
  fn get_ptr_data(mem: &Memory<'mir, 'tcx, Self>, addr: u64) -> PtrData;

  /// Get the alloc-offset pair from a `Scalar::Ptr`.
  fn get_alloc_offset(mem: &Memory<'mir, 'tcx, Self>, addr: u64, data: PtrData) -> InterpResult<'tcx, (AllocId, Size)>;
}

CTFE's PtrData type would be Option<AllocId> (I guess we can make AllocId a NonZero to still stay in our size budget), and the addr field is interpreted as "offset". ADDR_IS_RAW is false. Its get_ptr_data would always return None. get_alloc_offset errors if data is None ("int-ptr-cast not supported"), and otherwise returns addr as the offset and data as the allocation ID.

Miri's PtrData would be an Option<AllocId> and Stacked Borrow's Tag; the addr field is interpreted as the integer address. ADDR_IS_RAW is true. Its get_ptr_data would run the int-to-ptr cast machinery to find an AllocId, defaulting to None. get_alloc_offset would error if the PtrData has a None allocation ("dereferencing integer pointer", or so); and otherwise it gets the base address of the allocation (there's an AllocId in PtrData), and then subtracts that base address from addr for the resulting offset.

Compared to today, (a) ptr-to-int-casts are "pure" and don't need machine access, and (b) get_ptr_data is total so we can aggressively call it when we expect something to be a pointer value. We might even still have a Pointer type, holding an addr: u64 and a data: PtrData. Then Scalar would look pretty much exactly like today, in fact. ;) And maybe data should be called provenance.

Does this make sense?

[RalfJung]

We could also add a size field to the Ptr variant of Scalar, to avoid having to pass in impl HasDataLayout all the time (only constructing a Scalar from a Pointer would need it then). That will not increase the size of Scalar.

OTOH, requiring that for ptr-to-scalar conversion might also be annoying. Not sure which is worse.

[oli-obk]

I don't like having a size field on the pointer. I mean it only exists on Scalar as a sanity assert that I don't think we've triggered in a long time. All the ops are type based, so we can remove that field.

[RalfJung]

I mean it only exists on Scalar as a sanity assert that I don't think we've triggered in a long time.

You mean in about one hour? rust-random/getrandom#73 was found by that assert. ;)

I am strongly in favor of keeping the field. I don't feel I could confidently work on Miri without this check.

[oli-obk]

We can make it a field that only exists in debug mode, but yea i remember triggering asserts during development.

General note: create a special ConstValue specific type that is not the Scalar used during interpretation. Then we're free to mess with the representation without having to consider const eval things. As a start, just duplicate the type so conversion is trivial, and all future changes will need to convert. Since we have the type available during conversion, we can create the size field's value during conversion.

[RalfJung]

Given that the field does not increase the size of the enum, I think making it debug-only would mostly manage to increase the messiness of the code. We could make the actual size checks debug-only if you want, but I'd prefer only doing this if that actually gives a measurable performance increase. I doubt it will.

General note: create a special ConstValue specific type that is not the Scalar used during interpretation. Then we're free to mess with the representation without having to consider const eval things. As a start, just duplicate the type so conversion is trivial, and all future changes will need to convert. Since we have the type available during conversion, we can create the size field's value during conversion.

This sounds reasonable (then we could also finally move Scalar back into librustc_mir), but also sounds like a ton of work. We'd have to duplicate Scalar and Pointer, and how much of their API surface? And would it really be a good idea for ConstScalar not to have the size field, given that size mismatches can occur anywhere?

It looks like the main representation change for this issue is to replace AllocId in Pointer by Option<AllocId>. Not sure how painful that would be for the rest of the compiler, vs how painful it would be to duplicate everything.

[oli-obk]

I don't think duplicating would be much of a pain. We don't use any of the methods on scalars if obtained from a ScalarValue except for getting an int out of it