The Next Steps for Single Ownership and RAII
vale.dev
vale.dev
The "destructors with parameters" are interesting, but it's not clear what prevents using the object (or trying to) after destroying it.
None of this seems to address locking. The trouble with locking in C-type languages is that the language has no idea what data the lock covers, and thus it's hard to do an analysis for race conditions.
"We made two tiny classes, Request and RequestHandle. Each had only a pointer to the other. When one was destroyed, it would reach into the other to null out the pointer, thus severing the connection."
I've wanted something like that for Rust. Rust has problems with back references in trees and lists. There's no safe way to do those. What you need for a back reference is something like what Vale has there. The back reference has to be a non-owning optional reference. The only allowed values which can be assigned to it are the owner and None. Changing the ownership implicitly sets it.
(This is one of the two big safety holes in Rust. The other is partially initializing an array. There's no way to say to the language that "0..N of this array are initalized". So "Vec" has to be unsafe. If both of those holes were plugged, there would be far fewer excuses for "unsafe")
There are three things preventing someone from using the object after destroying it:
* If it was an owning reference, the compiler will ensure nobody else uses it.
* The program will halt if there are any live constraint references to an object we destroy, preventing anyone using one of those.
* If it was a weak reference, the language will (conceptually) null that out when we destroy the object.
* By default, an object can't be visible to two threads, every thread has its own isolated region (similar to Pony and Rust).
* We can use a mutex to contain a region, and Vale's "region borrow checking" can make sure references don't escape the lock's duration.
[1]: roguelike.vale, https://github.com/ValeLang/Vale/blob/9541d414ce6b1c2745de19...
All variables are supposed to be initialized before use. But a Rust Vec, like a C++ std::vector<T>, has both an in-use "size" and a usually-larger pre-allocated "capacity". This allows adding elements without getting a new memory block.
Implementing Vec safely in Rust runs into the problem of initializing the capacity not yet used. Not initializing it is unsafe, so Vec has to have "unsafe" code.
I'd argue for this:
First, data types should be divided into "fully mapped" and "not fully mapped". A fully mapped type is one where all bit combinations are valid. Fully mapped types don't have to be initialized to be memory-safe. This includes integers, floating point on most systems, but not booleans. (C++ calls this "plain old data", or POD, but allows Booleans and enums. Whether Booleans with values other than 0 or 1, or out of range enums, should be considered "plain old data" is a good question for a language designer.)
If it's not fully mapped (worst case, it has a pointer or reference in it), what do you do about uninitialized data in the unused "capacity" area? If it's not initialized, you have a pointer with a junk value, as far as the language is concerned. If it has to be initialized, you have a problem if initialization requires an input value.
So I'd argue for the concept of a partially initialized array as a language feature. For simplicity, only being initialized from the beginning to a limit (0..N) should be supported. (Yes, there is such a thing as a giant sparsely initialized hash table where allocation info is stored outside the table. See Google's sparse hash table. That's very rare.) The idea is that you designate some field of the structure as the "size", and accessing beyond "size-1" is a subscript error. But you can initialize at "size", and this increases "size" by 1. You can decrease "size" if you own the whole object.
If you have both of those features in a Rust-like language, you should not need "unsafe". Except to call other languages, maybe.
Of course a language and its clever implementation can make reading unintialized values from malloc()‘d objects UB with all that implies, but that’s a spec choice.
So I believe you could define what’s returned by malloc() as safely castable to one or more “fully mapped types”, which would solve the problem for vectors at least of those types.
The problem I was discussing is with growable arrays, where the memory underneath is partially initialized.
I haven't looked at google's sparse hash table yet, I'll have to codesearch that =)
Interesting. Cone has every known approach to memory management. GC, refcounts, arenas, pools, single ownership, thread local... Worth an experiment, but you probably don't want to go there for a widely used language. Think of the library compatibility problems.
For locking purposes, there's an argument for thread-local, shared, and transferable objects. Transferable objects are what you put in a queue between two threads. They're single-thread and don't need locking when in use, but can be handed off to another thread.
It's useful if transferable objects are transferable by copy. This is useful for machines where not all memory is shared. We're headed there; cache management gets harder and harder as the number of cores starts to approach 3 digits. So think ahead here.
I can imagine having programs which are tree-like hierarchies of regions, but I'm starting to suspect we can have directed acyclic graphs, and perhaps even very small cycles in them...
It's likely these are well motivated design decisions since you designed this with knowledge of Rust. As a programmer relieved by the transition from C++ to Rust, going back "halfway" in the direction of C++ will be a hard sell, even if it makes some things easier.
There are three things that we'll have to show the world:
1. While Rust's references are safe and efficient, they force other would-be-references into less efficient patterns (the afterword dives into this a bit).
2. The article didn't mention this, but Rust's approach has a lot of run-time checking too. Every expect/unwrap and every Rc<RefCell<T>>'s borrow/mut() is an assertion, just like Vale's constraint refs.
3. These run-time "halts" won't actually be panics. In debug mode, it can pause and let you continue after a key-press (and even whitelist on a class-by-class basis). Then, once done running the program, one can easily convert that constraint ref to a weak ref in code if desired.
Also, the guarantees for thread safety should be the same as Rust, could you elaborate on that?
Anyway, even if the above three reasons aren't enough, Vale's ease-of-use should be more than worth it, for those who find Rust's approach too restrictive.
It'll be challenging to show readers the broader picture, and that Rust and Vale are two equivalent approaches to safety, but we're up to the challenge =)
I would say, that if you’ve a lot of RefCells in your code, then you most likely doing it wrong.
Having just a few RefCells for higher level, bigger structures seems to make more sense. If you get these structures from a RefCell all the further access on them can be statically verified during compile time.
It’s not only about the performance but about the correctness of your code, how easy you can reason about it. The more dynamic checks you have, the less you can be sure about your code.
The other approach that I like for mitigating the cost of mutable aliasing (in Rust and Vale and some other languages) is to rearchitect the program such that the world (or some subset of it) is frozen, we do a lot of heavy calculation and make an "effect", and then unfreeze the world to apply it. Vale's region borrow checker [1] will make that zero-cost, like Rust's borrow checker does.
If we must have mutable aliasing, I like the balance you speak of, where one can use a blend of runtime-checked aliasing at the high level and borrow checking at the low level. I hope that borrow checker zen moves in that direction. Cone [2] emphasizes that exact balance, and I think there's a lot of promise there.
Consider visiting a tree:
enum Tree {
Branch(Box<Tree>, Box<Tree>), // left, right
Leaf(i32)
}
fn postorder_visit(t: &mut Tree, f: fn(&mut Tree)) {
// ???
}
So an overflow-safe implementation must use unsafe, but still wants to have confidence in ordered destruction. You could make it a `Vec<*mut Tree>`, but now there are zero checks!
The idea here is, in debug mode only, replace `Box` with `Rc` that checks its refcount upon drop, and `&mut Tree` with Rc as well. Now your debug mode does not require unsafe, and your release mode is fast. You have dynamically enforced ownership in a regime inaccessible to the borrow checker.
How does this deal with concurrency? Must you now always use mutexes when handling this kind of pointers?
Also the discussion about destructors having a return value or taking arguments forgets to mention a simple trick: an rvalue-reference qualified member function. To call it you must use std::move() on the object. Linters can then warn about use-after-move. That method can do the real work of destruction while the destructor can be quite trivial.
Vale, like Rust, isolates its threads' memory regions from each other, and also allows borrowing from mutexes. (Vale will use region-based borrow checking rather than Rust's object-based kind)
You're quite right about the rvalue-reference qualified member functions! There's one hiccup though; it can't be used with unique_ptr. I think theres an obscure note in the article that mentions that C++ could use Rust's "Arbitrary Self Types" to really close this hole. At that point, C++ might be able to have this kind of improved RAII!
Mutable references are exclusive. If you Send an &mut T to another thread then it isn't really your memory any more—you can't read from it or write to it unless the other thread somehow Sends the reference back.
That there are mechanisms by which the isolation boundary can shift does not change that.
In one sense it's true that in Rust terms the actual ownership of the memory remains with the original thread, and the receiving thread is only borrowing it, but the reality is a bit stricter than that would imply since the borrowing thread has exclusive access for the duration of the borrow and can't be forced to give it up. To me, "which stack was the object allocated from" is less important than "which thread actually has control right now".
That's true. But according to your blog post, neither does Vale: it makes you choose between unsafe mode and reference-counting-overhead mode. From what I can tell, the advantages you're claiming are:
1. Optimized reference counting: Valid, though I'm wondering how much difference it makes.
2. Constraint references: Valid, but as far as I can tell this could be easily implemented as a wrapper around Rc like the C++ version is around shared_ptr.
3. Mutable aliasing: I think this is the most important one. In Rust you can do this by wrapping all your struct fields in Cell or RefCell (so that the 'immutable' references you get from Rc are actually mutable ones), but the ergonomics are poor. Other reference-counting languages (e.g. Swift) do this ergonomically, but have no way to opt out and use a borrow checker for increased performance. There's definitely room for a language to combine features of both.
4. Ability to compile the same code as either fast or safe: Doesn't appeal to me, because safety matters most in production where you might actually get exploited; but YMMV. I know game developers tend to have a different outlook.
Fast mode is as fast as even C++, and strictly safer than e.g. the C++ + ASan approach, but Resilient Mode is where the speed+safety story gets interesting.
I didn't have much opportunity to go into it in the article (it was already going on 15 pages, hah!) but there are some other aspects to Vale which should drastically cut down on reference-counting overhead:
* Immutable region borrowing: we guarantee an entire is immutable, so all references into it are temporary and zero-cost, verified by the region borrow checker)
* Bump-calling: a pure function can make its own new region which uses a bump-allocator for all allocations, and at the end we copy out the return value.
* As mentioned, optimized ref-counting; we hope to reuse Lobster's algorithm, which removes 95% of ref counts.
* Non-atomic ref-counting, because of the region isolation (like Rust's Rc, as opposed to its Arc), which is faster and more optimizable.
I think it's hard to talk about these examples, but I'm having a hard time putting what I want to say into words.
I am very interested to see these benchmarks :)
Is there any risk of the compile flag influencing which object owns the reference, and therefore causing a kind of "heisenbug" where it doesn't crash during the safe mode but still has dangling pointers in the fast mode?
Behavior will be the same in all three modes. There is however a chance that testing and development didn't cover a certain code path, and we would trigger unsafety in production, similar to unsafe blocks in Rust. When one encounters unsafety in Vale, they'll be able to just re-run in normal mode to instantly identify what caused it.
Normal Mode is very conservative (halts early when a constraint ref becomes dangling, rather than when it's dereferenced), so combined with test coverage, it can give high confidence in safety, and is strictly better than even C++ and ASan.
If that's not enough, Resilient Mode has zero unsafety, and with the optimizations we'll be using (nonatomic RC, Lobster's algorithm, immutable region borrowing, bump calling, etc) should be incredibly fast in practice, possibly on par with Rust and C++, and exceeding them in certain cases, with bump calling.
Er, why wouldn't you just use automatic storage duration? That would look even simpler than the Vale implementation and have the same benefits:
class BigClass {
A a;
B b{&a};
C c{&a};
D d{&a, &c};
};
> Destructor Parameters
This can be done in C++: both unique and shared ptrs can take a deleter instance. So for the rollback example:
std::unique_ptr<Transaction, Transaction::RollbackWithMode> tx(
new Transaction(), Transaction::RollbackWithMode(mode));
Transaction tx(conn, Transaction::ROLLBACK_MODE_TUMBLE);
...
if (ok) { tx.commit(); } return;
Similarly with the Future example -- IMO this is far clearer:
void Producer(Future<T> future) {
auto auto_reject = AutoRun([&] {
if (!future.ready()) future.reject();
});
...code, including potentially many branches....
}
template <typename Functor>
auto AutoRun(Functor f) {
class AutoRunner {
public:
AutoRunner(Functor f) : f_(f) {}
~AutoRunner() { f_(); }
private:
Functor f_;
};
return AutoRunner(f);
}In some cases, you do know the destruction parameters up-front, and there I would agree that a deleter is great.
Sometimes you can't know the parameters up front, so can't easily get them into the deleter when you initialize. The call-once std::function and the future are good examples: These both take parameters which you might not know until later on. If you already know the values of a future when you're creating it, it probably wouldn't be a future.
future.~resolve(resultOfSomeAsynchronousCalculation);
Also, someone mentioned yesterday that this is a form of linear typing, since everything must be destructed exactly once. But we would still run into a problem if we did make any objects with no zero-arg destructor...
...except now that I'm typing this out, it occurs to me that we could just use the "Bailing Past Destructors" [1] rule says: hold the error, call the appropriate destructor, and continue returning the error upwards. (Vale would use a Result type, not exceptions)
Wow, the solution was there all along, and I never thought to retrofit it to C++. Perhaps I'll revise the article tonight to take out the mention of exceptions =)
[1] "Vale: The Interesting Parts", https://docs.google.com/document/d/1t0zzW0K9jilbCkuAulZfDlZc... (fair warning, written for language enthusiasts!)