valtrees and padding

[lcnr]

we intend to transition const generics over to valtrees, this representation erases padding bytes.

We also intend to allow the following example to compile:

const fn some_operation::<const N: usize>() -> usize { N }
const fn other_operation(x: usize) -> usize { x + 1 }

fn outer<const N: usize>() -> [u8; other_operation(some_operation::<N>())] {
    inner::<{ some_operation::<N>() }>()
}
fn inner<const M: usize>() -> [u8; other_operation(M)] {
    [u0; other_operation(M)]
}

for this to compile, we have to unify the constant other_operation(some_operation::<N>()) with the constant other_operation(M) using the generic argument some_operation::<N>() as argument for M. This is sound as long as const eval doesn't have side effects.

A concern is the interaction between padding bytes and valtrees. We intend to not remember padding bytes in constants used in the type system, but do remember them during const eval and can soundly get their value (afaik). This means that putting values into the type system in the middle of const eval can have observable effects, e.g. consider

#![feature(generic_const_exprs, adt_const_params)]

#[repr(C)]
#[derive(PartialEq, Eq)]
struct Foo {
    v1: u8,
    // _padding: u8,
    v2: u16,
}

#[repr(C)]
struct FooWithPadding {
    v1: u8,
    padding: u8,
    v2: u16,
}

const fn with_valid_padding<const N: u32>() -> &'static Foo {
    unsafe {
        &*(&N as *const u32).cast::<Foo>()
    }
}

const fn reads_padding(v: &'static Foo) -> usize {
    unsafe {
        &*(v as *const Foo).cast::<FooWithPadding>()
    }.padding as usize
}

fn direct_use<const N: u32>() -> [u8; reads_padding(with_valid_padding::<N>())] {
    generic_reads_padding::<{ with_valid_padding::<N>() }>()
}

fn generic_reads_padding<const FOO: &'static Foo>() -> [u8; reads_padding(FOO)] {
    [0; reads_padding(FOO)]
}

fn main() {
    println!("{:x}", direct_use::<0x0000bb00>().len());
}

direct_use must not compile with valtrees as the behavior of reads_padding differs between the two constants.

cc @RalfJung @oli-obk

[lcnr]

Potential ways I can think of to fix this would be:

• prevent direct_use from compiling by not unifying these generic constants, at least in cases when can cause problems.
  • which causes actually cause problems? any kind of indirection?
• when converting stuff to valtrees, require all "reachable" allocations to not have initialized padding bytes. This would cause the usage of with_valid_padding as a const argument to cause an error.
• somehow change const eval to always make padding bytes invalid if they pass through a context which is "transparent" to the type system. This causes reads_padding to fail even in the reads_padding(with_valid_padding::<N>()) const.
  • that seems a bit difficult to implement and is also really surprising.

I currently think that the second option is the best one of these three.

[oli-obk]

The behaviour only differs in as far as [0; reads_padding(FOO)] in generic_reads_padding will error, because the padding will have gotten turned into undef when converting from valtree back to Allocation. Is that a problem? I guess it is another post-monomorphization-error, but complex enough unsafe code can always have that and we can't avoid it.

[lcnr]

Is that a problem?

I assume it is because due to the way const equality works, we can probably end up with trait solving only evaluating one of the two constants, so while probably not unsound in an exploitable way, it would definitely be bad for this to compile and then break due to some unrelated change in the compiler or library 😓

[oli-obk]

oh... yea, since we compare generic consts by their body, we can indeed only evaluate one of them.

But, whatever equivalence algorithm we come up with knows there is a valtree conversion in there, and we can check that the types that undergo a valtree conversion have no padding. Concepts like Pod: Copy: Clone have come up before and would help here, too.

Although we also have problems around relocations if we ever expose something like guaranteed_eq and someone uses it wrongly.

There's probably other things, too, like if someone feeds two unrelated pointers into an unsafe function that expects them to point into the same allocation.

Basically all UB is a problem here, as it could be fine without valtrees and only be UB after a valtree roundtrip.

So, in summary:

• I don't think your preferred solution (2) is enough.
• (3) is also not enough
• (1) is only feasible with Pod types not containing relocations.

I think I am overthinking the situation.

The safe solution is to make sure all constants are evaluated, even if they get deduplicated, just like we do with MIR optimizations. That's fairly annoying, but seems like the safe route.

Another one is to always pick one specific constant (the one with the valtree roundtrip), which is kind of your (3) solution, but only if two constants aren't perfectly the same. This basically makes the valtree-rounddrip an explicit part of comparing generic constants. We could even go as far as making comparison of two generic constants (A and B) actually be a "produce a constant C that if it evaluates successfully, means A and B would evaluate successfully and to the same value". This is kind of like finding lubs for lifetimes. You create a new lifetime, and relate it to your two input lifetimes.

[RalfJung]

We intend to not remember padding bytes in constants used in the type system, but do remember them during const eval and can soundly get their value (afaik).

This seems to be the crux here: the new constraint that is imposed by examples like this is that two CTFE values, if they are equal after creating valtrees, must be fully observationally equivalent. That is a lot stronger than the requirement that I thought would be necessary.

I think in a first step it would probably be better to not do this kind of unification in these cases. ("These cases" being the ones where valtree construction is lossy, which AFAIK is only the case for types that have padding.)

Longer-term, could partially solve this by fixing CTFE: indeed I consider it to be a bug that the value in padding is preserved when a value gets copied around; this does not represent the actual intended semantics of Rust. But indeed in your example the padding is behind an indirection, and then there really is no UB here: it is perfectly legitimate for unsafe code to look at the padding byte of a &Foo, if it somehow knows that that byte is indeed initialized.

Basically all UB is a problem here, as it could be fine without valtrees and only be UB after a valtree roundtrip.

The thing is, there is no UB in the non-valtree-roundtrip version of this code.

---

In fact I think this is at the very least rather surprising even if we disregard the unification problem: I might have const code that works fine, where one const directly refers to another. (This means it directly uses the underlying Allocation so padding is preserved.) Then I abstract that away via cosnt generics, and now the second const suddenly uses the valtree of the first, padding is lost, and behavior of the code changes. We should entirely rule out any types with padding for const generics until we are very sure how we want to handle this...

(The original example here is even more tricky since it starts not even with one const directly referring to another, but with a single CTFE computation where the data is passed from one function to another.)

Allocation identity

As @oli-obk mentioned, another concern besides padding here could be pointer identity. But there we already have the stance that consts do not have addresses and allocations might be (de)duplicated by the compiler [we could probably document this better though]. Also AFAIK even with unsafe code this is not observable inside CTFE; guaranteed_eq should be fine since it should always return false if one of the pointers is a const.

Although we also have problems around relocations if we ever expose something like guaranteed_eq and someone uses it wrongly.

What would be an example of that? I think this would be a bug in guaranteed_eq. That function needs to be carefully written such that a valtree roundtrip (or other changes in alloocation identity that we consider permissible) does not change the behavior of guaranteed_eq.

There's probably other things, too, like if someone feeds two unrelated pointers into an unsafe function that expects them to point into the same allocation.

Besides ptr equality, the only way to observe this is to mutate the memory, and valtree construction must error out if it ever reads from mutable memory. So this, too, should be excluded.

[lcnr]

We should entirely rule out any types with padding for const generics until we are very sure how we want to handle this...

the same issue also without padding, but "oversized" allocations. Is that intended to be UB?

#![feature(generic_const_exprs, adt_const_params)]

const fn shrink<const N: u64>() -> &'static u32 {
    unsafe {
        &*(&N as *const u64).cast::<u32>()
    }
}

const fn grow(v: &'static u32) -> u64 {
    unsafe {
        *(v as *const u32).cast::<u64>()
    }
}

fn direct_use<const N: u64>() -> [u8; grow(shrink::<N>()) as usize] {
    inner::<{ shrink::<N>() }>()
}

fn inner<const FOO: &'static u32>() -> [u8; grow(FOO) as usize] {
    [0; grow(FOO) as usize]
}

fn main() {
    println!("{:x}", direct_use::<0x0000bb00>().len());
}

[RalfJung]

Ah, good catch. Inside a single CTFE execution this is clearly entirely fine.

Generally it seems super hard to try and argue that a single execution can be equivalently split into two separate executions with just a valtree passed from the first to the second -- unsafe Rust code makes a lot of things observable, and intentionally so since it is made for low-level programming.

[RalfJung]

for this to compile, we have to unify the constant other_operation(some_operation::()) with the constant other_operation(M) using the generic argument some_operation::() as argument for M. This is sound as long as const eval doesn't have side effects.

So, essentially the problem here depends on the type of M. We can probably "split computations" at simple types like i32, but the moment there is a pointer indirection, doing such a cut... just doesn't seem realistic.

But this also means that we should be really suspicious of any place where a valtree has to be converted back to a Miri value. Which... seems like a problem for the entire valtree scheme?

[lcnr]

I think

when converting stuff to valtrees, require all "reachable" allocations to not have initialized padding bytes. This would cause the usage of `with_valid_padding as a const argument to cause an error.

is enough for this to be correct. We would have to additionally verify that the valtree conversion works at each potential "split", but that doesn't seem too bad.

or probably even "all initialized bytes in the value have to be used during the conversion", i.e. the valtree conversion has to be a bijective function.

If unused initialized bytes happen frequently, e.g. when changing enum variants to a smaller one or something? We could erase them at all potential "split"s.

Generally a bit surprised that we didn't realize this earlier, but I feel like there are good enough solutions ^^

[RalfJung]

We would have to additionally verify that the valtree conversion works at each potential "split", but that doesn't seem too bad.

It seems pretty bad TBH -- we would have to do a valtree check basically each time a "typed copy" is made, or at least each time values pass across function boundaries. It will be truly horrendous for performance. This is also very fragile due to trying to enforce things that go beyond what the Rust spec is about, so I expect a permanent struggle of fixing other "leaks" that we discover.

Generally a bit surprised that we didn't realize this earlier, but I feel like there are good enough solutions ^^

Well, I had so far basically refused to even think about the unification problem, since I felt we had enough issues on our plate without considering "partial executions". And I think this issue proves me right to be worried about further dragons awaiting in those unexplored parts of this dungeon.

Doing this for integer values (or anything without a pointer) seems fine, but I am now honestly very skeptical about ever doing this for values that contain pointers. This goes totally against how Rust has been designed, and there is a fundamental conflict between allowing unsafe code during CTFE and doing this kind of high-level reasoning.

[lcnr]

It seems pretty bad TBH -- we would have to do a valtree check basically each time a "typed copy" is made, or at least each time values pass across function boundaries. It will be truly horrendous for performance.

I don't intend to look inside of functions for unification so e.g. the constant other_operation(some_operation::<N>()) has only 1 such potential split point. I generally expect that the actual constants used for const generics will be quite simple - and have to be, moving all the complexity into named functions or constants. I don't believe that this will impact the perf of rustc as a whole in any meaningful way.

Well, I had so far basically refused to even think about the unification problem, since I felt we had enough issues on our plate without considering "partial executions".

"partial executions" are needed for other reasons as well, e.g. we want the following snippet to compile

struct Foo<const N: Option<usize>>;

impl<const N: usize> Foo<{ Some(N) }> {}

error[E0207]: the const parameter `N` is not constrained by the impl trait, self type, or predicates
 --> src/lib.rs:3:12
  |
3 | impl<const N: usize> Foo<{ Some(N) }> {}
  |            ^ unconstrained const parameter
  |
  = note: expressions using a const parameter must map each value to a distinct output value
  = note: proving the result of expressions other than the parameter are unique is not supported

We still have a lot of time to figure all of this out, and to do a lot of cleanup of our code so that it's clear whether there's something that could go wrong. It should obviously be a prerequisite that we have a firm understanding of what could go wrong before we start to work on stabilizing stuff here.

[RalfJung]

I don't intend to look inside of functions for unification so e.g. the constant other_operation(some_operation::()) has only 1 such potential split point. I generally expect that the actual constants used for const generics will be quite simple - and have to be, moving all the complexity into named functions or constants. I don't believe that this will impact the perf of rustc as a whole in any meaningful way.

It doesn't really matter what the typical const generic constants are though, we'd have to do this kind of roundtrip for every function call since it might be part of a const generic. It's also odd (IMO) to special-case function calls in the semantics, and it is very surprising that values are adjusted at all in a function call -- that's just not how Rust programs typically behave.

"partial executions" are needed for other reasons as well, e.g. we want the following snippet to compile

I am not sure where there is a partial execution in that example?

[RalfJung]

rust-lang/rust#99798 (comment) made me realize that this is already at least partially implemented?!? I would have expected that to be done a bit more carefully TBH.^^

So, how do I trigger these "abstract" consts to be created? I tried this but there does not seem to be a valtree roundtrip there.