Pre-RFC: placement box with Placer trait


#1
  • Start Date: (fill me in with today’s date, YYYY-MM-DD)
  • RFC PR: (leave this empty)
  • Rust Issue: (leave this empty)

Summary

Add user-defined placement box expression (more succinctly, “a box expression”), an operator analogous to “placement new” in C++. This provides a way for a user to specify (1.) how the backing storage for some datum should be allocated, (2.) that the allocation should be ordered before the evaluation of the datum, and (3.) that the datum should preferably be stored directly into the backing storage (rather than temporary storage on the stack and then copying the datum from the stack into the backing storage).

Motivation

As put by Bjarne Stroustrup, “The Design and Evolution of C++”:

Two related problems were solved by a common mechanism:

  1. We needed a mechanism for placing an object at a specific address, for example, placing an object representing a process at the address required by special-purpose hardware.

  2. We needed a mechanism for allocating objects from a specific arena, for example, for allocating an object in the shared memory of a multi-processor or from an arena controlled by a persistent object manager.

In C++, the solution was overload the pre-existing new operator with an additional “new (buf) X” form known as “the placement syntax”, where the static type of the buf input dictates which overloaded variant is used.

We also want to solve the above two problems in Rust. Moreover, we want to do so in an efficient manner.

Why ptr::write is not sufficient

Today, one can emulate both goals (1.) and (2.) above by using unsafe native pointers and copying already constructed values into the target addresses via unsafe code. In particular, one can write code like this, which takes an input value, allocates a place for it, and writes it into place.

fn allocate_t(t: T) -> MyBoxOfTee {
    unsafe {
        let place = heap::allocate(mem::size_of::<T>(), mem::align_of::<T>());
        let place : *mut T = mem::transmute(place);

        // `place` is uninitialized; don't run dtor (if any) for T at place.
        ptr::write(place, t);

        MyBoxOfTee { my_t: place }
    }
}

However, this is inefficient; using this API requires that one write code like this allocate_t(make_value()), which to the rustc compiler means something like this:

    let value : T = make_value();
    let my_box = allocate_t(value);

This is not ideal: it is creating a temporary value for T on the stack, and then copies it into the final target location once it has been allocated within the body of allocate_t. Even if the compiler manages to inline the body of allocate_t into the callsite above, it will still be quite difficult for it to get rid of the intermdiate stack-allocation and the copy, because to do so requires moving the heap::allocate call up above the make_value() call, which usually will not be considered a semantics-preserving transformation by the rustc compiler and its LLVM backend.

Doing allocation prior to value construction

The Rust development team has known about the above problem for a long time; long enough that it established the box expression syntax ahead of time to deal with this exact problem (though with much debate about what exact syntax to use):

The point is to provide some syntactic special form that takes two expressions: a <place-expr> and <value-expr>. (For context, in rustc today one writes the special form as box (<place-expr>) <value-expr>.) The <place-expr> dicates the allocation of the backing storage (as well as the type used as a handle to the allocated value, if any); the <value-expr> dicates the actual datum to store into the backing storage.

We need to provide both expressions to the special form because we need to do the allocation of the backing storage before we evalute <value-expr>, but we want to ensure that the resulting value is written into the backing storage (initializing it) before the address of the backing storage possibly leaks to any code that assumes it to be initialized.

Placement box as an (overloaded) operator

While the original motivation for adding placement new in C++ was for placing objects at specific memory addresses, the C++ design was also made general enough so that the operation could be overloaded: statically dispatched at compile-time based on the type of the target place. This allows for distinct allocation protocols to be expressed via a single syntax, where the static type of <place-expr> indicates a particular allocation method. Rust can also benefit from such a generalization, as illustrated by some examples adapted from rust meeting October 2013:

// (used below)
let mut arena : Arena = ...;
let mut my_vector : Vec<Foo> = ...;

// Allocates an `RcBox<Thing>` (includes ref-count word on backing
// storage), initializes associated payload to result of evaluating
// `Thing::init("hello")` and returns an `Rc<Thing>`. Uses singleton
// (static) constant `RC` to signal this allocation protocol.
let my_thing : Rc<Thing> = box(RC) Thing::init("hello");

// Allocates an entry in a locally-allocated arena, then stores result
// of `Foo::new()` into it, returning shared pointer into the arena.
let a_foo : &Foo = box(arena) Foo::new()

// Adds an uninitialized entry to the end of the `Vec`, then stores
// result of `Foo::new()` into it, returning `()`, or perhaps the
// `uint` of the associated index. (It is a library design detail;
// this system should support either.)
box(my_vector.emplace_back()) Foo::new()

In addition, one can imagine a further generalization of the arena example to support full-blown reaps, a form of arena that supports both owned references (where the associated memory can be given back to the reap and reallocated) and shared references.

let reap : reap::Reap = ...;

let a_foo : &Foo = {
    // both of afoo_{1,2} own their respective handles into the reap
    let afoo_1 : reap::OwningRef<Foo> = box(reap) Foo::new();
    let afoo_2 : reap::OwningRef<Foo> = box(reap) Foo::new();

    let shared_foo : &Foo = afoo_1.to_shared();
    shared_foo // here storage of afoo_2 is returned to the reap
};

...

Failure handling

One final detail: Rust supports task failure, and thus the placement box syntax needs to make sure it has a sane story for properly unwinding its intermediate state if the <value-expr> fails.

To be concrete: we established in Doing allocation prior to value construction that we must do the allocation of the backing storage before we start evaluating <value-expr>. But this implies that if <value-expr> causes a failure, then we are also responsible for properly deallocating that backing storage, or otherwise tearing down any state that was set up as part of that allocation.

Summary of motivations

So the goals are:

  1. Support evaluating a value into a specific address, without an intermediate copy,

  2. Provide user-extensible access to the syntax, so that one can control the types and executed code for both (2a.) the backing storage of the value, and (2b.) the resulting wrapper type representing the handle (this “handle” may be either owned or shared, depending on the design of library), and

  3. Still handle task failure/panic properly.

Detailed design

The presentation of the design is broken into the following sections.

  • Section 1, Syntax: The placement box syntax assumed by this RFC, which has been in place within rustc for a while, but remains a point of contention for some, and thus is worth teasing out from the other parts. (Note that the Alternatives section does discuss some of the alternative high-level syntaxes that have been proposed.)

  • Section 2, Semantics: The placement box semantics, as observed by a client of the syntax using it with whatever standard library types support it. This section should be entirely uncontroversial, as it follows essentially from the goals given in the motivation section.

  • Section 3, API: The method for library types to provide their own overloads of the placement box syntax. In keeping with how other operators in Rust are handled today, this RFC specifies a trait that one implements to provide an operator overload. However, due to the special needs of the placement box protocol as described in "Section 2, Semantics", this trait is a little more complicated to implement than most of the others in core::ops.

Section 1: Syntax

As stated in Doing allocation prior to value construction, we need a special form that takes a <place-expr> and a <value-expr>.

The form that was merged in Rust PR 10929 takes the following form:

box (<place-expr>) <value-expr>

with the following special cases:

  • if you want the default owned box Box<T> (which allocates a T on the inter-task exchange heap), you can use the shorthand box () <value-expr>, omiting the <place-expr>.

  • as an additional special case for Box<T>: if <value-expr> has no surrounding parentheses (i.e. if <value-expr> starts with a token other than (), then you can use the shorthand box <value-expr>.

(The combination of the above two shorthands do imply that if for some strange reason you want to create a boxed instance of the unit value (), i.e. a value of type Box<()>, you need to write either box () (), or box (HEAP) () where HEAP is an identifier that evaluates to the inter-task exchange heap’s placer value.)

Section 2: Semantics

From the viewpoint of a end programmer, the semantics of box (<place-expr>) <value-expr> is meant to be:

  1. Evaluate <place-expr> first (call the resulting value PLACE).
  2. Perform an operation on PLACE that allocates the backing storage for the <value-expr> and extracts the associated native pointer ADDR to the storage.
  3. Evaluate the <value-expr> and write the result directly into the backing storage.
  4. Convert the PLACE and ADDR to a final value of appropriate type; the associated type is a function of the static types of <place-expr> and <value-expr>.

(Note that it is possible that in some instances of the protocol that PLACE and ADDR may be the same value, or at least in a one-to-one mapping.)

The type of the <place-expr> also indicates what kind of boxed value should be constructed.

In addition, if a failure occurs during step 3, then instead of proceeding with step 4, we instead deallocate the backing storage as part of unwinding the continuation (i.e. stack) associated with the placement box expression.

Examples of valid <place-expr> that will be provided by the standard library:

  • The global constant std::boxed::HEAP allocates backing storage from the inter-task exchange heap, yielding Box<T>.

  • The global constant std::rc::RC allocates task-local backing storage from some heap and adds reference count meta-data to the payload, yielding Rc<T>

  • It seems likely we would also provide a Vec::emplace_back(&mut self) method (illustrated in the example code in Placement box as an (overloaded) operator), which allocates backing storage from the receiver vector, and returns (). (Or perhaps uint; the point is that it does not return an owning reference.)

Section 3: API

How a library provides its own overload of placement box.

The standard library provides two new traits in core::ops:

/// Interface to user-implementations of `box (<placer_expr>) <value_expr>`.
///
/// `box (P) V` effectively expands into:
/// `{ let b = P.make_place(); let v = V; unsafe { ptr::write(b.pointer(), v); b.finalize() } }`
pub trait Placer<Sized? Data, Owner, Interim: PlacementAgent<Data, Owner>> {
    /// Allocates a place for the data to live, returning an
    /// intermediate agent to negotiate ownership.
    fn make_place(&mut self) -> Interim;
}

/// Helper trait for expansion of `box (P) V`.
///
/// A placement agent can be thought of as a special representation
/// for a hypothetical `&uninit` reference (which Rust cannot
/// currently express directly). That is, it represents a pointer to
/// uninitialized storage.
///
/// The client is responsible for two steps: First, initializing the
/// payload (it can access its address via the `pointer()`
/// method). Second, converting the agent to an instance of the owning
/// pointer, via the `finalize()` method.
///
/// The expectation is that both of these operations are cheap; in
/// particular, clients expect the backing storage to have already
/// been allocated during the call to `Placer::make_place`.  It would
/// be a violation of that expectation to delay the allocation to the
/// invocation of `pointer()`.
///
/// See also `Placer`.
pub trait PlacementAgent<Sized? Data, Owner> {
    /// Returns a pointer to the offset in the place where the data lives.
    unsafe fn pointer(&self) -> *mut Data;

    /// Converts this intermediate agent into owning pointer for the data,
    /// forgetting self in the process.
    unsafe fn finalize(self) -> Owner;
}

The necessity of a Placer trait is largely unsuprising: it has a single make_place method, which is the first thing invoked by the placement box operator. The interesting aspects of Placer are:

  • It has three type parameters. The first two are the Data being stored and the Owner that will be returned in the end by the box expression; the need for these two follows from Placement box as an (overloaded) operator. The third type parameter is used for the return value of make_place, which we explain next.

  • The return value of make_place is a so-called "interim agent" with two methods. It is effectively an &uninit reference: i.e. it represents a pointer to uninitialized storage.

The library designer is responsible for implementing the two traits above in a manner compatible with the hypothetical (hygienic) syntax expansion:

            box (P) V
               ==>
    { let b = P.make_place(); let v = V; unsafe { ptr::write(b.pointer(), v); b.finalize() } }

In addition, any type implementing PlacementAgent is likely to want also to implement Drop: the way that this design provides Failure handling is to couple any necessary cleanup code with the drop for the interim agent. Of course, when doing this, one will also want to ensure that such drop code does not run at the end of a call to PlacementAgent::finalize(self); that is why the documentation for that method methods that it should forget self (as in mem::forget(self);), in order to ensure that its destructor is not run.

The following two examples are taken from a concrete prototype implementation of the above API in Rust PR 18233.

API Example: Box

Here is an adaptation of code to go into alloc::boxed to work with this API.

pub static HEAP: ExchangeHeapSingleton =
    ExchangeHeapSingleton { _force_singleton: () };

/// This the singleton type used solely for `boxed::HEAP`.
pub struct ExchangeHeapSingleton { _force_singleton: () }

pub struct IntermediateBox<Sized? T>{
    ptr: *mut u8,
    size: uint,
    align: uint,
}

impl<T> Placer<T, Box<T>, IntermediateBox<T>> for ExchangeHeapSingleton {
    fn make_place(&self) -> IntermediateBox<T> {
        let size = mem::size_of::<T>();
        let align = mem::align_of::<T>();

        let p = if size == 0 {
            heap::EMPTY as *mut u8
        } else {
            unsafe {
                heap::allocate(size, align)
            }
        };

        IntermediateBox { ptr: p, size: size, align: align }
    }
}

impl<Sized? T> PlacementAgent<T, Box<T>> for IntermediateBox<T> {
    unsafe fn pointer(&self) -> *mut T {
        self.ptr as *mut T
    }
    unsafe fn finalize(self) -> Box<T> {
        let p = self.ptr as *mut T;
        mem::forget(self);
        mem::transmute(p)
    }
}

#[unsafe_destructor]
impl<Sized? T> Drop for IntermediateBox<T> {
    fn drop(&mut self) {
        if self.size > 0 {
            unsafe {
                heap::deallocate(self.ptr as *mut u8, self.size, self.align)
            }
        }
    }
}

API Example: Vec::emplace_back

struct EmplaceBack<'a, T:'a> {
    vec: &'a mut Vec<T>,
}


struct EmplaceBackAgent<T> {
    vec_ptr: *mut Vec<T>,
    offset: uint,
}

impl<'a, T> Placer<T, (), EmplaceBackAgent<T>> for EmplaceBack<'a, T> {
    fn make_place(&self) -> EmplaceBackAgent<T> {
        let len = self.vec.len();
        let v = self.vec as *mut Vec<T>;
        unsafe {
            (*v).reserve_additional(1);
        }
        EmplaceBackAgent { vec_ptr: v, offset: len }
    }
}

impl<T> PlacementAgent<T, ()> for EmplaceBackAgent<T> {
    unsafe fn pointer(&self) -> *mut T {
        assert_eq!((*self.vec_ptr).len(), self.offset);
        assert!(self.offset < (*self.vec_ptr).capacity());
        (*self.vec_ptr).as_mut_ptr().offset(self.offset.to_int().unwrap())
    }

    unsafe fn finalize(self) -> () {
        assert_eq!((*self.vec_ptr).len(), self.offset);
        assert!(self.offset < (*self.vec_ptr).capacity());
        (*self.vec_ptr).set_len(self.offset + 1);
    }
}

#[unsafe_destructor]
impl<T> Drop for EmplaceBackAgent<T> {
    fn drop(&mut self) {
        // Do not need to do anything; all `make_place` did was ensure
        // we had some space reserved, it did not touch the state of
        // the vector itself.
    }
}

Drawbacks

We have been getting by without user-defined box so far, so one might argue that we do not need it now. My suspicion is that people do want support for the features listed in the motivation section.

In fact, as the rust-dev December 2013 thread was winding down, pcwalton pointed out:

Rust and C++ are different. You don’t use placement new for shared_ptr in C++; however, you will use placement new (or box) for RC in Rust (the equivalent). For this reason I suspect that placement new will be much commoner in Rust than in C++.

Alternatives

Same semantics, but different surface syntax

There were a variety of suggestions listed on rust-dev November 2013 rust-dev December 2013 rust-dev July 2014.

In addition, RFC Issue 405 provides yet another list of alternatives.

The complaints listed on RFC Issue 405 are largely about the use of parentheses in the syntax especially given its special cases (as described in Section 1: Syntax).

Some example alternatives from RFC Issue 405:

  • box (in <place-expr>) <value-expr>
  • box <value-expr> in <place-expr>
  • box::(<place-expr>) <value-expr>

The author (Felix) personally wants to keep the <place-expr> lexically to the left of <value-expr>, to remind the reader about the evaluation order. But perhaps in <place-expr> box <value-expr> would be alternative acceptable to the author of RFC Issue 405?

Just desugar into once-functions, not implementations of traits

At the rust meeting August 2014, the team thought we could do a simpler desugaring that would wrap the <value-expr> in a once-function closure; this way, you would still force the expected order-of-evaluation (do the allocation first, then run the closure, letting return value optimization handle writing the result into the backing storage).

The most obvious place where this completely falls down is that it does not do the right thing for something like this:

let b: PBox<T> = box (place) try!(run_code())

because under the once-function desugaring, that gets turned into something like:

place.make_box(|once: | -> T { try!(run_code()) })

which will not do the right thing when run_code returns an Err variant, and in fact will not even type-check.

So the only way to make the once-function desugaring work would be to either severely restrict the kinds of expressions that “work” as the <value-expr>, or to make the desugaring a much more invasive transformation of the <value-expr>; neither of these options is really palatable.

Get rid of Placer and just use the PlacementAgent trait.

Hypothetically, if we are willing to revise our API’s for interacting with placement box, then we could get rid of the Placer trait.

In particular, if we change the protocol so that <place-expr> itself is responsible for returning an instance of PlacementAgent, then we would not need Placer at all.

This would mean we could no longer write box (rc::RC) <value-expr> or box (boxed::HEAP) <value-expr>; it would have to be something like box (rc::RC()) <value-expr> and box (boxed::HEAP()) `, at best.

I am not sure this would be much of a real win.

Unresolved questions

  • Is there a significant benefit to building in linguistic support for &uninit rather than having the protocol rely on the unsafe methods in PlacementAgent?

Placement NWBI<- FAQ (New/Box/In/Left Arrow)
#2

You mean *b.pointer()? Isn’t this technically an incorrect expansion, as assigning in that way would attempt to drop the old contents?


#3

@comex good point; i should be calling ptr::write there (which is what the expansion itself actually does in the prototype).


#4

The mutability of self changes in make_place from section to section. Unclear which is desired? Seems like you’d want &mut since this should be a owning action, but I guess that doesn’t work with something like the static heap singleton?

Would it be possible for the placer syntax to take a function that it calls? Then box (rc::RC) <value-expr> would still work, without some of the ownership mess that the Placer type introduces.

I’m also unclear why the asserts and to_int() conversion are necessary in emplace_back. Just being fancy, or are these actual concerns?


#5

This all looks good to me.

With respect to the unresolved question regarding &uninit, there is no way we could add support for &uninit in short term, even if we had an agreed upon design, so the only option would be delaying box. So perhaps the question is better phrased “Is it worth leaving box in its current crippled form in hopes that it can benefit from a future, more general design for uninitialized memory?” Personally I think the question answers itself: it is at most a minor wart if box includes a primitive version of uninit, and there are a lot of unresolved questions in my mind about uninit in any case.


#6

Actually, re-reading Gankro’s comment and the RFC, I got to thinking about the mutability of varous things here.

  1. I suspect that the pointer method on PlacementAgent ought to take &mut self.
  2. I don’t see why it matters or should be expected for "pointer" to be cheap in particular. We expect to call it once, after all.
  3. The use of &self on the Placer trait isn’t ideal. Perhaps removing the Placer trait and having just the PlacementAgent would be the right thing after all.

It would be nice if you could write all of the following:

  1. box(in RC) foo
  2. box(in vec.emplace_back()) foo
  3. box(in arena) foo

(I’m not sure yet which syntax I prefer, I thought i’d experiment)

But I’m not sure we can have all three. But maybe that’s just fine.

The first one seems to work most anyway we do it. RC is a global constant, so it is actually an rvalue at the moment, but even if we eventually allowed global constants to be lvalues, then it could implement Copy as it has no state, and hence it could potentially serve as the placement agent (though the expansion would have to carry the data type T externally).

The second one really prefers no placer at all.

The third one wants the current design.

Finally, looking forward to when we have customizable memory allocators, we probably want a fourth use case, which is the ability to put a box in a specific allocator. The protocol can accommodate this fine, but it’s another instance where, similar to emplace_back, you don’t really need the Placer trait. I imagine it would look something like:

box(in Rc(alloc)) foo

Anyway, I’ll try to sketch out what I mean in more detail, but atm I am leaning towards saying we can remove the Placer trait after all (I know I poopoo’d the idea last time you raised it, sorry).


#7

An idea that came up on RFC is to have:

  • box foo – expands to something that uses return type to decide what box to use. Intended for “global allocator smart pointers”, e.g., Box<T>, Rc<T>, etc
  • in(place) foo – for the case where you want to specify a place value

#8

Serious and data-oriented applications tend to get both custom pools/arenas and custom smart pointers (intrusive for example), so it would be valuable to be able to specify using these as easily as the standard ones.

One reason many developers of embedded and performance critical programs are a bit uneasy about using standard collections is the typical lack of control over where these algorithms allocate.


#9

@nikomatsakis

box foo – expands to something that uses return type to decide what box to use. Intended for “global allocator smart pointers”, e.g., Box, Rc, etc

I like this idea a lot. It always seemed strange and kind of warty to me that a built-in operator like box would default to or otherwise be tied to a library-defined type like Box<T>. Having the resulting type from box be inferred (when not explicitly specified) seems much more consistent with how Rust works in other areas.

(Bikeshed: if box and Box<T> aren’t going to be intrinsically tied to each other, might it make sense to rename one of them to avoid confusion? Thought perhaps this should be discussed as a separate topic…)


#10

posted an actual RFC for placement in (i.e. the final draft of the original material posted on this topic).

I plan to write a separate RFC for box foo inferring what kind of box to use from the expression’s context (i.e. its “return type”)