Heap allocations in constants

[oli-obk]

Current proposal/summary: #20 (comment)

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?

Current proposal/summary: #20 (comment)

[RalfJung]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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.

[strega-nil]

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]

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?

[strega-nil]

@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]

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]

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.