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

Heap allocations in constants #20

Open
oli-obk opened this issue Dec 14, 2018 · 43 comments

Comments

@oli-obk
Copy link
Collaborator

commented Dec 14, 2018

Motivation

In order to totally outdo any other constant evaluators out there, it is desirable to allow things like using serde to deserialize e.g. json or toml files into constants. In order to not duplicate code between const eval and runtime, this will require types like Vec and String. Otherwise every type with a String field would either need to be generic and support &str and String in that field, or just outright have a mirror struct for const eval. Both ways seem too restrictive and not in the spirit of "const eval that just works".

Design

Allocating and Deallocating

Allow allocating and deallocating heap inside const eval. This means Vec, String, Box
* Similar to how panic is handled, we intercept calls to an allocator's alloc method and never actually call that method. Instead the miri-engine runs const eval specific code for producing an allocation that "counts as heap" during const eval, but if it ends up in the final constant, it becomes an unnamed static. If it is leaked without any leftover references to it, the value simply disappears after const eval is finished. If the value is deallocated, the call to dealloc in intercepted and the miri engine removes the allocation. Pointers to dead allocations will cause a const eval error if they end up in the final constant.

Final values of constants and statics

If a constant's final value were of type String, and the string is not empty, it would be very problematic to use such a constant:

const FOO: String = String::from("foo");
let x = FOO;
drop(x);
// how do we ensure that we don't run `deallocate`
// on the pointer to the unnamed static containing the bye sequence "foo"?

While there are a few options that could be considered, all of them are very hard to reason about and easy to get wrong. I'm listing them for completeness:

  • just set the capacity to zero during const eval
    • will prevent deallocation from doing anything
    • seems like it would require crazy hacks in const eval which know about types with heap allocations inside
    • Not sure how that would work for Box
  • use a custom allocator that just doesn't deallocate
    • requires making every single datastructure generic over the allocator in use
    • doesn't fit the "const eval that just works" mantra
  • actually turn const eval heap allocations into real heap allocations on instantiation
    • not zero cost
    • use of a constant will trigger a heap allocation

We cannot ban types that contain heap allocations, because

struct Foo;

impl Drop for Foo {
    fn drop(&mut self) {
        println!("foo");
    }
}

const FOO: Foo = Foo;

is perfectly legal stable Rust today. While we could try to come up with a scheme that forbids types that can contain allocations inside, this is impossible very hard to do.

There's a dynamic way to check whether dropping the value is problematic:

run Drop::drop on a copy of the final value (in const eval), if it tries to deallocate anything during that run, emit an error

Now this seems very dynamic in a way that means changing the code inside a const impl Drop is a breaking change if it causes any deallocations where it did not before. This also means that it's a breaking change to add any allocations to code modifying or creating such values. So if SmallVec (a type not heap allocating for N elements, but allocating for anything beyond that) changes the N, that's a breaking change.

But the rule would give us the best of all worlds:

const A: String = String::new(); // Ok
const B: String = String::from("foo"); // Not OK
const C: &String = &String::from("foo"); // Ok
const D: &str = &String::from("foo"); // Ok

More alternatives? Ideas? Code snippets to talk about?

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Dec 19, 2018

Instead the miri-engine runs const eval specific code for producing an allocation that "counts as heap" during const eval, but if it ends up in the final constant, it becomes an unnamed static. If it is leaked without any leftover references to it, the value simply disappears after const eval is finished. If the value is deallocated, the call to dealloc in intercepted and the miri engine removes the allocation. Pointers to dead allocations will cause a const eval error if they end up in the final constant.

Sounds perfect!

If a constant's final value were of type String, and the string is not empty, it would be very problematic to use such a constant

Ouch. :( Why are Drop types allowed in constants?!?

run Drop::drop on a copy of the final value (in const eval), if it tries to deallocate anything during that run, emit an error

I don't think we should do this: This means that any difference between compile-time and run-time execution becomes an immediate soundness error.

Also, it's not just Drop that causes trouble: Say I have a copy of String in my own library, the only difference being that the destructor does nothing. Then the following code is accepted by your check, but will be doing something very wrong at run-time:

const B: String = String::from("foo");
let mut b = B;
b.push_str("bar"); // reallocates the "heap"-allocated buffer
@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Dec 19, 2018

The problem with push_str affects statics as well:

static B: Mutex<String> = Mutex::new(String::from("foo"));
let mut s = B.lock().unwrap();
s.push_str("bar"); // reallocates the "heap"-allocated buffer
@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Dec 19, 2018

Ugh. Looks like we painted ourselves into a corner. Let's see if we can spiderman our way out.

So... new rule. The final value of a constant/static may either be

  1. an immutable reference to any value, even one containing const-heap pointers
    • if an UnsafeCell is encountered, continue with 2.
  2. an owned value with no const-heap pointers anywhere in the value, even behind relocations. The analysis continues with 1. if safe references are encountered

The analyis happens completely on a constant's value+type combination

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Dec 20, 2018

Looks like we painted ourselves into a corner.

Note that contrary to what I thought, rejecting types with Drop does not help as my hypothetical example with a drop-free leaking String shows.

Right now, even if we could change the past, I don't know something we could have done that would help here.

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Jan 9, 2019

Note that contrary to what I thought, rejecting types with Drop does not help as my hypothetical example with a drop-free leaking String shows.

Yea I realized that from your example, too.

I believe that the two step value+type analysis covers all cases. We'd allow &String but not &Mutex<String>. We'd allow SomeOwnedTypeWithDrop as long as it doesn't contain heap pointers. So String is not allowed because it contains a raw pointer to a heap somewhere. (i32, &String) is also ok, because of the immutable safe reference.

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Jan 25, 2019

So just having rule (1) would mean if there is a ptr (value) that is not of type &T, that's an error? I think for an analysis like this, we want to restrict ourselves to the publicly visible type. Otherwise it makes a difference whether some private field is a shared ref or not, which makes me uneasy.

I am not sure I understand what (2) changes now. Does that mean if I encounter a pointer that is not a &T (with T: Frozen), it must NOT be a heap ptr? I am not sure if the "analysis continues with 1" describes an exception to "no heap pointers".


Btw, I just wondered why we don't rule out pointers to allocations of type "heap". Those are the only ones where deallocation is allowed, so if there are no such pointers, we are good. You say

We cannot ban types that contain heap allocations, because

but the example that follows doesn't do anything on the heap, so I don't understand.

We currently do not allow heap allocation, so allowing it but not allowing such pointers in the final value must be fully backwards-compatible -- right?

The thing is that you also want to allow

const C: &String = &String::from("foo"); // Ok
const D: &str = &String::from("foo"); // Ok

and that's where it gets hard.

And now what you are trying to exploit is some guarantee of the form "data behind a frozen shared ref cannot be deallocated", and hence allow some heap pointers based on that? I think this is hereditary, meaning I don't understand why you seem to restrict this to 1 level of indirection. Consider

const E: &Vec<String> = &vec![String::from("foo")]; // OK?

Given that types have free reign over their invariants, I am not convinced this kind of reasoning holds. I do think we could allow (publicly visible) &[mut] T to be heap pointers, because we can assume such references to satisfy the safety invariant and always remain allocated. I am very skeptical of anything going beyond that. That would allow non-empty &str but not &String.

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Jan 25, 2019

const E: &Vec<String> = &vec![String::from("foo")]; // OK?

Hm... yea, I did not think about this properly. A raw pointer can just be *const () but be used after casting to *const UnsafeCell<T> internally, thus destroying all static analysis we could ever do.

So... we would also allow &&T where both indirections are heap pointers.. but how do we ensure that a private &T field in a type is not also accepted? I mean we'd probably want to allow (&T, u32) but not SomeType::new() with struct SomeType { t: &'static T } because that field might have been obtained by Box::leakand might point to stuff that hasUnsafeCellin it, andSomeTypemight transmute the&'static Tto&'static UnsafeCell`.

I'm not sure if it is legal to transmute &'static UnsafeCell to &'static T where T only has private fields.

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Feb 4, 2019

but how do we ensure that a private &T field in a type is not also accepted?

I think we can have a privacy-sensitive value visitor.

but not SomeType::new() with struct SomeType { t: &'static T } because that field might have been obtained by Box::leak and might point to stuff that hasUnsafeCellin it, andSomeTypemight transmute the &'static T to &'static UnsafeCell.

Yeah that's why I suggested only going for public fields. I think such a type would be invalid anyway (it would still have a shared reference around, and Stacked Borrows will very quickly get angry at you for modifying what is behind that reference). But that seems somewhat shady, and anyway there doesn't seem to be much benefit from allowing private shared references.

OTOH, none of this would allow &String because there we have a private raw pointer to a heap allocation. I feel like I can cook up a (weird, artificial) example where allowing private raw pointers to the heap would be a huge footgun at least.

I think if we want to allow that, we will have to ask for explicit consent from the user: some kind of annotation on the field saying that we will not perform mutation or deallocation on that field on methods taking &self, or so.

@gnzlbg

This comment has been minimized.

Copy link

commented Feb 15, 2019

we intercept calls to an allocator's alloc

This should intercept calls to #[allocator], methods like alloc_zeroed (and many others) might callcalloc instead of malloc, other methods call realloc, etc. Currently the #[allocator] attribute is super unstable (is its existance even documented anywhere?), but requires a function returning a pointer, and it states that this pointer does not alias with any other pointer in the whole program (it must point to new memory). It currently marks this pointer with noalias, but there are extensions in the air (e.g. see: gnzlbg/jemallocator#108 (comment)), where we might want to tell LLVM about the size of the allocation and its alignment as a function of the arguments of the allocator function.

If it is leaked without any leftover references to it, the value simply disappears after const eval is finished.

Does this run destructors?

If the value is deallocated, the call to dealloc in intercepted and the miri engine removes the allocation.

Sounds good in const eval, but as you discovered below, this does not work if run-time code tries to dealloc (or possibly also grow) the String.

While there are a few options that could be considered, all of them are very hard to reason about and easy to get wrong.

I don't like any of them, so I'd say, ban that. That is:

const fn foo() -> String {
   const S: String = "foo".to_string(); // OK
   let mut s = "foo".to_string(); // OK
   s.push("!"); // OK
   if true { 
       S // OK
    } else {
        s // OK  
    }
} 
fn bar() -> String {
     const S: String = foo(); // OK
     let s = S.clone(); // OK
     if true {
        S // ERROR 
     } else {
         s // OK
     }
}

I think that either we make the const String to String "conversion" an error in bar, or we make it work such that:

unknown_ffi_dealloc_String(bar());

works. That is, an unknown FFI function must be able to deallocate a const String at run-time. If we don't know how to make it work, we could see if banning this is reasonable at the beginning. To say that certain consts cannot "escape" const evaluation somehow.

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Feb 16, 2019

Since we can call foo at runtime, too, allowing S in there will get us into the same problems that bar would get us into.

Does this run destructors?

const FOO: () = mem::leak(String::from("foo"));

would not run any destructors, but also not keep around the memory because we know there are no pointers to it anymore when const eval for FOO is done.

@ubsan

This comment has been minimized.

Copy link

commented Feb 24, 2019

Since this feature was just merged into C++20, the paper doing this would probably be useful to read as prior art: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0784r5.html

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Feb 25, 2019

The key requirements seem to be

We therefore propose that a non-transient constexpr allocation be a valid result for a constexpr variable initializer if:

  • the result of evaluating the initializer is an object with a nontrivial constexpr destructor, and
  • evaluating that destructor would be a valid core constant expression and would deallocate all the non-transient allocations produced by the evaluation of expr.

Furthermore, we specify that an attempt to deallocate a non-transiently allocated object by any other means results in undefined behavior. (Note that this is unlikely because the object pointing to the allocated storage is immutable.)

I am a bit puzzled by the hypothetical part about "would we a valid core constant expression and would deallocate". @ubsan do you know what is the purpose of this? (The paper unfortunately just states a bunch of rules with no motivation.)

Also, the part at the end about being "immutable" confuses me. Can't I use a constexpr to initialize a static, and then later mutate that static? Or use a constexpr to initialize a local variable and later mutate that?

@ubsan

This comment has been minimized.

Copy link

commented Feb 25, 2019

@RalfJung These are specifically for constexpr variables, which are variables which live in read only memory. You can allocate and everything at compile time, but if it's not stored to a constexpr variable (the first bit) whose allocation is deallocated by something the compiler can easily see (that second bit), then you must have allocation at compile-time - otherwise, it'll be a run-time allocation. Importantly, these compile time allocations are frozen at compile time, and put into read-only memory.

Initializing a non-constexpr variable with a constant expression (known as constinit) is also valid, but less interesting, because the allocations are not leaked to romem, and are done at runtime. constexpr variables are those which are known at compile time - mutable variables cannot be known at compile time, since one could mutate them. (it would be very weird to support allocation at compile time for runtime data, since one would expect to be able to reallocate that information as opposed to just mutating the data itself)

@gnzlbg

This comment has been minimized.

Copy link

commented Feb 25, 2019

am a bit puzzled by the hypothetical part about "would we a valid core constant expression and would deallocate"

@RalfJung These rules are for the initialization of constexpr variables. So in:

constexpr auto foo = bar();

ifbar() returns allocated memory, then foo must have a constexpr destructor, and this destructor must properly free the memory it owns. AFAICT this means that non-transient (see below) allocations must be deallocated, no leaks allowed (EDIT: non-transient allocations are those that don't leak to callers, so if you don't run the destructor of an allocation, that kinds of makes it transient by definition).

Can't I use a constexpr to initialize a static, and then later mutate that static?

Note that the rules you quote are for non-transient allocations, that is, allocations that are created and free'd during constant evaluation and that do not escape it, e.g.,

constexpr int foo() { 
    std::vector<int> _v{1, 2, 3};
    return 3;
}

where the memory allocated by foo for _v is allocated and deallocated at compile-time and never escapes into the caller of foo.

Transient allocations are those that scape to the caller, e.g, if foo above returns the vector _v. These are promoted to static memory storage.

That is, in

constexpr vector<int> foo = alloc_vec();
static vector<int> bar = foo;

the vector<int> in foo points to its memory in immutable static storage, and bar executes the run-time copy constructor of foo, which allocates memory at run-time, and copies the elements of foo, before main starts executing.

EDIT: In particular, the memory of bar does not live in immutable static storage. The memory of bar fields (e.g. ptr, len, cap) live in mutable static storage, but the data pointed to by its pointer field lives on the heap.

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Feb 25, 2019

Ok, so basically C++ avoids the issues we've talked about here by using copy constructors whenever it moves to a non-constexpr space.

This basically is

const A: String = String::new(); // Ok
const B: String = String::from("foo"); // Not OK
const C: &String = &String::from("foo"); // Ok
const D: &str = &String::from("foo"); // Ok

because C can be used as C.clone() when an owned value is desired and B is never ok.

@gnzlbg

This comment has been minimized.

Copy link

commented Feb 25, 2019

Ok, so basically C++ avoids the issues we've talked about here by using copy constructors whenever it moves to a non-constexpr space.

I'm not sure, maybe there is some sort of optimization that might be guaranteed to apply here in C++ that would elide this, but I don't know why Rust should do the same. To me Rust is even simpler.

The key thing is separating allocations that are free'd within constant evaluation (which C++ calls transient) and allocations that escape constant evaluation (which C++ calls non-transient), which get put in read-only static memory, where this memory can be read, but it cannot be written to, nor free'd.

So if String::from is a const fn:

const C: String = String::from("foo");
static S: String = C;
let v: String = S.clone();

during constant evaluation String::from would allocate a String in its stack (ptr, len, cap), and then the String would do a compile-time heap memory allocation, writing "foo" to that memory. When the String is returned, this allocation does not escape constant evaluation yet, because C is a const. If nothing uses C I'd expect the static memory segment to not contain the allocation as a guaranteed "optimization".

When we write static S: String = C; the allocation of C escapes constant-evaluation and gets byte-wise copied into read-only static memory. The ptr, cap, and len fields are byte-wise copied to S, where ptr is changed to point to the allocation in the read-only static memory segment .

That is, allocations that "escape" to C do not escape constant-evaluation because C is a const. The escaping happens when using C to create S, that is, when the const-universe interfaces with the non-const-universe.

S is immutable, can't be moved from, and it is never dropped, so AFAICT there is no risk of String::drop attempting to free read-only memory (that would be bad).

Creating v by calling clone does the obvious thing, copying the memory from the static memory segment into a heap allocation at run-time as usual.

A consequence of this is that:

const C: String = String::from("foo");
static S: String = C;
static S2: String = C;
// S === S2

Here S and S2 would be exactly identical, and their ptrs would be equal and refer to the same allocation.

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Feb 26, 2019

The problem occurs when you move to a static that contains interior mutability. So e.g.

static S: Mutex<String> = Mutex::new(C);
*S.lock() = String::new();

The old value is dropped and a new one is obtained. Now we could state that we simply forbid heap pointers in values with interior mutability, so the above static is not legal, but

static S: Mutex<Option<String>> = Mutex::new(None);

is legal.

This rule also is problematic, because when you have e.g.

static S: Vec<Mutex<String>> = vec![Mutex::new(C)];

we have a datastructure Vec, which is ptr, cap and len and no rules that we can see from the type about any interior mutability in any of the values. ptr is just a raw pointer, so we can't recurse into it for any kind of analysis.

This is the same problem we'd have with

const FOO: &Vec<Mutex<String>> = &vec![Mutex::new(C)];
@gnzlbg

This comment has been minimized.

Copy link

commented Feb 26, 2019

We discussed my previous comment on Discord yesterday, and the summary is that it is 100% flawed because it assumed that this was not possible in stable Rust today:

struct S;
impl Drop for S {
    fn drop(&mut self) {}
}
const X: S = S;
let _ = X;

and also because it did not take into account moving consts into statics with interior mutability.

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Feb 26, 2019

@ubsan

These are specifically for constexpr variables, which are variables which live in read only memory.

Oh, so there are special global variables like this that you can only get const pointers to, or so?

What would go wrong if the destructor check would not be done? The compiler can easily see all the pointers in the constexpr initial value just by looking at the value it computed, can't it?

Initializing a non-constexpr variable with a constant expression (known as constinit) is also valid, but less interesting, because the allocations are not leaked to romem, and are done at runtime.

Oh, I thought there'd be some magic here but this is basically what @oli-obk says, it just calls the copy constructor in the static initializer?

Ok, so basically C++ avoids the issues we've talked about here by using copy constructors whenever it moves to a non-constexpr space.

Well, plus it lets you write arbitrary code in a static initializer that actually gets run at compile-time.

@ubsan

This comment has been minimized.

Copy link

commented Feb 26, 2019

constexpr auto x = ...; // this variable can be used when a constant expression is needed
// it cannot be mutated
// one can only access a const lvalue which refers to x

constinit auto x = ...; // this variable is initialized at compile time
// it cannot be used when a constant expression is needed
// it can be mutated

The "copy constructors" aren't magical at all - it's simply using a T const& to get a T through a clone.

The thing that Rust does is kind of... extremely odd. Basically, it treats const items as non-linear and thus breaks the idea of linearity -- const X : Y = Z; is more similar to a nullary function than to a const variable.

Leaking would, in theory, be valid, but I imagine they don't allow it in order to catch bugs.

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Feb 27, 2019

constinit auto x = ...; // this variable is initialized at compile time

If the initializer involves non-transient allocations, @gnzlbg said above that they would become run-time allocations. How does that work, then, to initialize at compile-time a run-time allocation?

The thing that Rust does is kind of... extremely odd. Basically, it treats const items as non-linear and thus breaks the idea of linearity -- const X : Y = Z; is more similar to a nullary function than to a const variable.

Yeah, that's a good way of viewing it. const items can be used arbitrarily often not because they are Copy, but because they can be re-computed any time, like a nullary function. And moreover the result of the computation is always the same so we can just use that result immediately. Except, of course, with "non-transient allocations", the result would not always be the same, and making it always the same is what causes all the trouble here.

@gnzlbg

This comment has been minimized.

Copy link

commented Feb 27, 2019

If the initializer involves non-transient allocations, @gnzlbg said above that they would become run-time allocations.

If the initializer involves non-transient allocations, the content of the allocation is put into the read-only static memory segment of the binary at compile-time.

If you then use that to initialize a static, then the copy constructor is invoked AFAICT, which can heap allocate at run-time, and copy the memory from the static memory segment to the heap. All of this happens in "life before main".

@gnzlbg

This comment has been minimized.

Copy link

commented Feb 27, 2019

then the copy constructor is invoked AFAICT

I'm not 100% sure about this, and it is kind of implicit in the proposal, but AFAICT there is no other way that this could work in C++ because either the copy constructor or move constructor must be invoked, and you can't "move" out of a constexpr variable, so that leaves only the copy constructor available.

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Feb 27, 2019

If you then use that to initialize a static, then the copy constructor is invoked AFAICT, which can heap allocate at run-time, and copy the memory from the static memory segment to the heap. All of this happens in "life before main".

But what if I use that to initialize a constinit? (All of this constexpr business was added to C++ after I stopped working with it, so I am mostly clueless here.)

@gnzlbg

This comment has been minimized.

Copy link

commented Feb 27, 2019

But what if I use that to initialize a constinit?

None of these proposals has been merged into the standard (the heap-allocation one has the "good to go", but there is a long way from there to being merged), and they do not consider each other. That is, the constinit proposal assumes that constexpr functions don't do this, and the "heap-allocations in constexpr functions" proposal assumes that constinit does not exist.

So AFAICT, when heap-allocation in constexpr functions get merged, the it will be constinit problem to figure this out, and if it can't, then C++ won't have constinit.

I will ask around though.

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Feb 27, 2019

So from what @gnzlbg said on Zulip, it seems non-transient constexpr allocations did not make it for C++20, while transient allocations did.

And indeed, there is very little concern with transient heap allocations for Rust as well, from what I can see. So how about we start with getting that done? Basically, interning/validation can check whether the pointers we are interning point to the CTFE heap, and reject the constant if they do.
Well, that'd be the dynamic part of the check, anyway. If we also want a static check ("const qualification" style), that'd be harder...

@gnzlbg

This comment has been minimized.

Copy link

commented Feb 27, 2019

So how about we start with getting that done?

+1. Those seem very uncontroversial and deliver instant value. It makes no sense to block that on solving how to deal with non-transient allocations.

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Feb 27, 2019

As Ralf mentioned. Statically checking for transience is necessary for associated constants in trait declarations (assoc constants may not be evaluable immediately because they depend on other associated consts that the impl needs to define)

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Mar 1, 2019

So... @gnzlbg had a discussion on discord that I'm going to summarize here. The TLDR is that we believe a good solution is to have (names bikesheddable!) ConstSafe and ConstRefSafe unsafe auto traits.

ConstSafe types may appear in constants directly. This includes all types except

  • &T: ConstSafe where T: ConstRefSafe
  • &mut T: !ConstSafe

Other types may (or may not) appear behind references by implementing the ConstRefSafe trait (or not)

  • *const T: !ConstRefSafe
  • *mut T: !ConstRefSafe
  • String: ConstRefSafe
  • UnsafeCell<T>: !ConstRefSafe
  • i32: ConstRefSafe + ConstSafe.
    • the same for other primitives
  • [T]: ConstRefSafe where T: ConstRefSafe
  • the data pointer of a fat pointer follows the same rules as the root value of an allocation
    • rationale: the value itself could be on the heap, but you can't do anything bad with it since trait methods at worst can get a &self if you start with a &Trait. Further heap pointers inside the are forbidden, just like in root values of constants.
  • ... and so on (needs full list and rationale before stabilization)

Additionally values that contain no pointers to heap allocations are allowed as the final value of a constant.

Our rationale is that

  1. we want to forbid types like

    struct Foo(*mut ());

    whose methods convert the raw pointer to a raw pointer to the actual type (which might contain an unsafe cell) and the modify that value.

  2. we want to allow types like String (at least behind references), since we know the user can't do anything bad with them as they have no interior mutability. String is pretty much equivalent to

    struct String(*mut u8, usize, usize);

    Which is indistinguishable from the Foo type via pure type based analysis.

In order to distinguish these two types, we need to get some information from the user. The user can write

unsafe impl ConstRefSafe for String {}

and declare that they have read and understood the ConstRefSafe documentation and solemly swear that String is only up to good things.

Backcompat issue 1

Now one issue with this is that we'd suddenly forbid

struct Foo(*mut ());
const FOO: Foo = Foo(std::ptr::null_mut());

which is perfectly sane and legal on stable Rust. The problems only happen once there are pointers to actual heap allocations or to mutable statics in the pointer field. Thus we allow any type directly in the root of a constant, as long as there are none such pointers in there.

Backcompat issue 2

Another issue is that

struct Foo(*mut ());
const FOO: &'static Foo = &Foo(std::ptr::null_mut());

is also perfectly sane and legal on stable Rust. Basically as long as there are no heap pointers, we'll just allow any value, but if there are heap pointers, we require ConstSafe and ConstRefSafe

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Mar 31, 2019

I like the idea of using a trait or two to make the programmer opt in to this explicitly!

I think to follow this approach, we should figure out what exactly it the proof obligation that unsafe impl ConstSafe for T comes with. That should then inform which types it can be implemented for. Hopefully, for unsafe impl ConstRefSafe for T the answer can be "that's basically unsafe impl ConstSafe for &T".

I think the proof obligation will be something along the lines of: the data can be placed in static memory and the entire safe API surface of this type is still fine. Basically that means there is no deallocation. However, how does this interact with whether data is placed in constant or mutable memory?

@gnzlbg

This comment has been minimized.

Copy link

commented Aug 11, 2019

Could we change the semantics of using a const ? Right now, a const is copied on use, but could we make it so that if a const is !Copy + Clone then using the const calls Clone::clone instead ? If the const contains a compile-time allocation, we can forbid the uses of these consts if they do not implement Clone.

@eddyb

This comment has been minimized.

Copy link

commented Aug 11, 2019

@gnzlbg You can have a const of uncloneable type e.g. Option<&mut T> (it would just not have uncopyable leaf data, i.e. it would need to be None).

But also, I don't feel great about calling Clone automatically...

@gnzlbg

This comment has been minimized.

Copy link

commented Aug 11, 2019

But also, I don't feel great about calling Clone automatically...

Doesn't feel great to me either. I don't see any reasons why the following code would be unsound and think we should try to accept it:

const V: Vec<i32> = allocates_at_compile_time();
let v = V.clone();

It only uses a explicit clone though, so there is no need to do clone automatically as long as we avoid expanding that to something like:

let v = { 
    let mut tmp = copy V;
    tmp.clone()
    // drops tmp => UB
};

like we currently do (EDIT: e.g. we do this for the case where the Vec is empty, but that only works there).

@rpjohnst

This comment has been minimized.

Copy link

commented Aug 12, 2019

That seems like something that would work better as a static V than a const, or else as something like const V: &Vec<i32> = &allocates(); V.clone(), or even const V: &[i32] = leaks(); V.into_vec().

The contortions needed to make const V: Vec<i32> work, not to mention backwards compatible, don't seem worth it with so many potential alternative solutions.

@gnzlbg

This comment has been minimized.

Copy link

commented Aug 12, 2019

The contortions needed to make const V: Vec work, not to mention backwards compatible, don't seem worth it with so many potential alternative solutions.

@rpjohnst Are there cases where one could use const V: T but it wouldn't be trivial to use const V: &T instead ?

@eddyb

This comment has been minimized.

Copy link

commented Aug 12, 2019

I think the tricky examples would have to involve something like a &HashMap<K, V> because you can't just get a &[T] out of it.

IMO, exposing "compile-time heap pointers" immutably is much more acceptable (it's even mentioned in "the" pre-miri post) than trying to somehow auto-generate runtime heap allocations.

@mtak-

This comment has been minimized.

Copy link

commented Aug 28, 2019

A little out of my league here, so hopefully this is useful feedback. My not so secret ulterior motive is to lobby for the stabilization of Freeze.

ConstRefSafe types are a subset of Freeze types - as it is currently defined. ConstRefSafe requires immutability transitively whereas Freeze is not transitive through pointers. Prior art for ConstRefSafe might be the immutable storage class of D which @jeehoonkang pointed me to.

All Freeze types are safe to memcpy as long as the memcpy's capture the lifetime of the value immutably, and all memcpy's are forgotten before the original value is dropped. The lifetime restriction is not important to const's. This could simplify the implementation a bit for supporting const V: Vec<i32> = allocates_at_compile_time().

Desugaring this:

const V: Vec<i32> = allocates_at_compile_time();
let v = V.clone();

into this:

let v = { 
    let tmp = ManuallyDrop::new(copy V);
    (*tmp).clone()
    // drops tmp => OK
};

is safe. Generally using forget/ManuallyDrop on memcpy's of anything that is currently accepted as const is safe (I think).

Is there a use case for implementing ConstSafe manually?


@eddyb points out that there is no conceivable trait that can capture all values that are currently OK to use in a const (Option<Anything> is allowed if None). Since analyzing the value of consts is effectively required, is this is enough for the definition of ConstRefSafe?

unsafe auto trait Immutable {}
impl<T: ?Sized> !Immutable for UnsafeCell<T> {}

It permits String/Vec/etc, and forbids Mutex/Cell/etc.

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Aug 28, 2019

All Freeze types are safe to memcpy as long as the memcpy's capture the lifetime of the value immutably, and all memcpy's are forgotten before the original value is dropped.

What do you mean by this? Address identity is also still observable in Rust.


On another note, I wonder how this interacts with the dynamic checks that make sure that constants cannot be mutated. We should intern heap allocations that were created by constants as immutable. But they get created mutably, meaning that we basically can only silently clamp mutability during interning -- but then code like this could compile:

const MUTABLE_BEHIND_RAW: *mut i32 = Box::into_raw(Box::new(42));

But then later *MUTABLE_BEHIND_RAW = 99; would be UB because we are writing to immutable memory.

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Aug 28, 2019

const MUTABLE_BEHIND_RAW: *mut i32 = &1 as *const _ as *mut _;

will also end up as mutable allocation (and compiles on stable). Is there any reason we need to treat heap allocations differently except maybe user expectations?

I think we can safely say you should not be mutating anything you got from a constant except the value itself?

@gnzlbg

This comment has been minimized.

Copy link

commented Aug 28, 2019

@mtak-

Desugaring this: [...] into this [...] is safe.

I agree, but I don't know what value does allowing this add. If we require const V: &Vec = alloc_at_compile_time(); the user just needs to write let vec = V.clone();. OTOH, doing that would add the cost of implicit clones to the language, which is something that Rust never does. We'll have to change all teaching material from "clones are explicit" to "clones are explicit unless [insert complex set of rules]".

I think we can safely say you should not be mutating anything you got from a constant except the value itself?

What do you mean with "except the value itself" ?

@eddyb

This comment has been minimized.

Copy link

commented Aug 28, 2019

will also end up as mutable allocation (and compiles on stable)

That's a regression, I'm pretty sure we used to make that immutable before miri.

@oli-obk

This comment has been minimized.

Copy link
Collaborator Author

commented Aug 28, 2019

That's a regression, I'm pretty sure we used to make that immutable before miri.

Probably. If we unify the promoted scheme between constants and functions that will be immutable again

@RalfJung

This comment has been minimized.

Copy link
Collaborator

commented Aug 28, 2019

Is there any reason we need to treat heap allocations differently except maybe user expectations?

For that one we can argue that it is mutating through a pointer obtained from a shared reference (&0). If we could somehow reflect that in alloc.mutability...

That's a regression, I'm pretty sure we used to make that immutable before miri.

It is possible that this changed with rust-lang/rust#58351. And the previous code was rather too aggressive with marking things immutable in a static.

If we unify the promoted scheme between constants and functions that will be immutable again

Or we just have to merge rust-lang/rust#63955.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
7 participants
You can’t perform that action at this time.