- 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:
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.
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:
-
Support evaluating a value into a specific address, without an intermediate copy,
-
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
-
Still handle task failure/panic properly.
Detailed design
The presentation of the design is broken into the following sections.
-
Section 1, Syntax: The placement
boxsyntax assumed by this RFC, which has been in place withinrustcfor 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
boxsemantics, 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
boxsyntax. 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 placementboxprotocol as described in "Section 2, Semantics", this trait is a little more complicated to implement than most of the others incore::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 aTon the inter-task exchange heap), you can use the shorthandbox () <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 shorthandbox <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:
- Evaluate
<place-expr>first (call the resulting valuePLACE). - Perform an operation on
PLACEthat allocates the backing storage for the<value-expr>and extracts the associated native pointerADDRto the storage. - Evaluate the
<value-expr>and write the result directly into the backing storage. - Convert the
PLACEandADDRto 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::HEAPallocates backing storage from the inter-task exchange heap, yieldingBox<T>. -
The global constant
std::rc::RCallocates task-local backing storage from some heap and adds reference count meta-data to the payload, yieldingRc<T> -
It seems likely we would also provide a
Vec::emplace_back(&mut self)method (illustrated in the example code in Placementboxas an (overloaded) operator), which allocates backing storage from the receiver vector, and returns(). (Or perhapsuint; 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
Databeing stored and theOwnerthat will be returned in the end by the box expression; the need for these two follows from Placementboxas an (overloaded) operator. The third type parameter is used for the return value ofmake_place, which we explain next. -
The return value of
make_placeis a so-called "interim agent" with two methods. It is effectively an&uninitreference: 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
newforshared_ptrin C++; however, you will use placementnew(orbox) forRCin Rust (the equivalent). For this reason I suspect that placementnewwill 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
&uninitrather than having the protocol rely on the unsafe methods inPlacementAgent?