Let’s unleash some memory-safety mixed martial arts

June 22, 2023

 — 

Evan Ovadia

 — 

Sponsor on GitHub
or Patreon!

Adding memory safety to C++ is a very difficult problem, to say the least.

I’ve spent most of the last decade exploring this area (mainly to design Vale‘s memory safety) and I’ve discovered some surprising things.

The world largely believes that the only ways to make code memory safe are through reference counting, tracing garbage collection, or borrow checking.

It turns out, there’s at least eleven more methods 0 1 with more being discovered all the time if you know where to look. 2

Someone asked me recently, can we use these techniques to add memory safety to C++?

We can! It’s something I’ve been thinking about for a while, and it’s about time I write it all down.

The Challenges

Our ultimate goal is to find simple ways to make C++ memory-safe, simple enough that they can be checked via static analysis tooling or linters, without extending the language.

We’re going to do this without reference counting, or tracing garbage collection, or Rust-style borrow checking.

Not because they’re bad, of course. They have some great benefits:

  • Tracing GC is the simplest model for the user, and helps with time management and development velocity, two very important aspects of software engineering.
  • Reference counting is simple, allows for more predictable destruction of objects, and doesn’t require a VM like tracing GC does.
  • Borrow checking is very fast, and helps avoid data races.

However, they each have their drawbacks too:

  • Tracing GC can have some unpredictable pauses sometimes, while it stops the world to figure out which objects are still alive.
  • Reference counting is often the slowest approach (though I think that will change in the next decade 3).
  • Borrow checking is incompatible with some useful patterns and optimizations (described later on), and its infectious constraints can have trouble coexisting with non-borrow-checked code. 4

They also have their pragmatic limitations:

  • Making tracing GC work well with C++ would be tricky, since the GC would need to find everywhere the normal C++ objects have references to garbage-collection-managed objects. 5
  • Reference counting is pretty doable actually, as shown by shared_ptr.
  • Borrow checking has a high complexity cost in the type system, such as its annotations. It would be difficult to add that to C++ which is a very complex language already.

I’m about to describe some different approaches, each with their own tradeoffs. None are silver bullets, and I wouldn’t claim that they’re the best way to do things. They’re merely interesting possibilities.

For a sneak peek, here they are: constraint references, generational references, random generational references, regions, arenas, mutable value semantics, interaction nets, basil memory stacks, CHERI capabilities, neverfree, MMM++, SPARK, and linear types. More than eleven really, but there is some overlap.

1

One day, I want to write about all these methods, and call the book the “Memory Safety Grimoire”. That’d be pretty sweet!

3

I think a language will come along that blends reference counting with regions and linear or unique types. That would eliminate the vast majority of reference counting operations, which might make RC competitive again.

4

This is why Rust has Rc and RefCell, and also why we’re about to introduce generational references and constraint references.

5

This has been done though, see the Boehm-Demers-Weiser garbage collector.

The techniques

We’re going to blend four main ingredients to achieve our memory safety:

  • “Borrowless affine style”, via unique_ptr and owned values (from Vale, Val, and Austral)
  • Constraint references (from Gel, Inko, and Vale)
  • Generational references and random generational references (from Vale)
  • Simplified borrowing (from Val)

These techniques are all possible, as far as I know. Between Vale, Val, Austral, Rust, Inko, and a few others, these techniques have all been implemented one place or another. There are a few other blends which use completely different techniques 6, but let’s start with this one. It starts off a bit rocky, but has that nice “zero-cost abstraction” feel to it, and generational references let us code with a familiar C++-like spirit.

These techniques provide the tools we need, and then a separate static analysis tool could ensure that we use them for the entire program, or in certain scopes, or for certain types. 7 8

Some caveats up-front:

  • There is no such thing as zero-overhead memory safety for any language; some of these techniques could incur extra cloning, bounds checking, hashing, etc.
  • Using these techniques will feel awkward or restrictive at first, almost Rust-esque at times. Further below, we blend in some other techniques to relax these restrictions and make it easier.
  • These techniques will have varying levels of composability with existing unsafe C++ code.

With that, let’s dive in!

6

Some other blends:

If you want to hear more about these, let me know!

7

Or maybe even just a well-crafted linter.

8

If anyone wants to actually attempt this, let me know!

Borrowless Affine Style

This technique blew my mind pretty spectacularly, especially when I realized that it was already hidden beneath the surface in languages like Vale, Austral, Val, and Rust.

This technique shows that we don’t need tracing GC, reference counting, borrow checking, or anything for memory safety. We just need to change the way we move data around.

We’re going to start by identifying some memory-safe patterns that are already in C++, and then we’ll slowly expand it until we have a minimum viable memory-safe subset of C++. 9 After that, we’ll add some mechanisms to make it more usable, so it’s not so restrictive.

9

Easter egg, this note will disappear in two hours!

A pigeon named G. I. Joe was awarded the Dickin Medal for gallantry for saving the British 56th infantry division and the inhabitants of Calvi Vecchia, Italy.

G. I. Joe successfully flew a last-resort message to the nearby allied artillery to cancel bombarding the city, which the infantry had just successfully taken over. o7, you brave bird!

If you read this note, leave a comment (HN / r/cpp), nobody will believe you.

unique_ptr

C++11’s unique_ptr is a class that tracks who has sole responsibility for destroying an object.

This one little class singlehandedly brought the concepts of single ownership and move semantics into the mainstream, and it will serve as the starting point for our memory safety.

Our first principle is that dereferencing a unique_ptr is safe, as long as we follow these two rules:

Rule 1: Always initialize a unique_ptr to contain something. 10

Rule 2: Don’t use a unique_ptr local variable after moving from it. 11

It wouldn’t be hard to make some static analysis or a linter for these, plenty enforce that second one already.

So far, this is pretty obvious. A lot of us follow these rules already in our codebases.

The next part will be obvious too, and after that things get more interesting.

10

If you want a nullable unique_ptr, consider wrapping it in an optional.

11

Linters enforce this for local variables, but not for fields. We’ll have another rule to address that below.

Stack objects are safe too

Our next principle is that, of course, accessing the fields of an object on the stack is safe too.

That doesn’t include making a pointer to a stack-allocated object and then dereferencing. 12 Only accessing a field directly is safe, at least so far.

struct Ship { int fuel; };
int main() {
  Ship ship{ 42 };
  // Safe to access ship's fields.
  cout << ship.fuel << endl;
}

Now that the more obvious principles are out of the way, let's get to the interesting stuff!

12

Technically, the compiler might produce a temporary reference when we say the name of a variable. That's fine, as long as we don't make references or pointers directly.

Avoid raw pointers and references 13

I know, that sounds impossible and ridiculous.

"How in the world would we get anything done without raw pointers and references?" I can hear you say.

But I assure you, it is possible. And don't worry, we'll be adding pointers back in later.

But for now, here are some rules to understand how to make programs without aliasing.

Rule 3: When you want to take a pointer or a reference as a parameter, instead take (and return) a unique_ptr or a stack object.

Instead of taking a Ship pointer like this:

struct Ship { int fuel; };
void print(Ship* ship) {
  cout << ship.fuel << endl;
}

...print would take (and return) it:

struct Ship { int fuel; };
Ship print(Ship ship) {
  cout << ship.fuel << endl;
  return ship;
}

Rule 4: When you want a raw pointer as a field, use an index or an ID instead.

Instead of a Ship having a Port* like this...

struct Port { string name; };
struct Ship { Port* port; };

Ship print(Ship ship) {
  cout << ship.port->name << endl;
  return ship;
}

...we would do something conceptually similar to this, where print uses the portId to read the Port from a map.

struct Port { string name; };
struct Ship { int portId; };

Ship print(unordered_map* ports, Ship ship) {
  cout << ports[ship.portId].name << endl;
  return ship;
}

Of course, we'll need to change that pointer parameter according to rule 3. We'll instead take and return the vector directly:

struct Port { string name; };
struct Ship { int portId; };

tuple, Ship> print(
    unordered_map ports,
    Ship ship) {
  cout << ports[ship.portId].name << endl;
  return make_tuple(ports, ship);
}

That's pretty verbose! We'll see some ways to make it less verbose further below.

These two rules may seem familiar to those who have used Rust; taking and returning a Ship is semantically equivalent to taking an &mut Ship, and the borrow checker often makes reference struct fields into indices/IDs as well.

However, we'll be deviating from Rust's direction pretty sharply.

13

We'll still be using them indirectly of course; dereferencing a unique_ptr produces a temporary reference. But we won't be using raw pointers or references directly.

Reading fields: swapping, move-destructuring

Later, we can access fields pretty easily using "simplified borrowing" like in Val. Until we get to those, I'll show how we can access fields using only this "borrowless affine style", for completeness.

Rule 5: We can only read a field by taking ownership of it, by either swapping something into its place or destroying the containing struct.

In this example, a Ship contains a unique_ptr.

We'll use std::exchange 14 to swap the unique_ptr out to read it.

struct Engine {
  int fuel;
  Engine(int fuel_) : fuel(fuel_) {}
};

struct Ship {
  unique_ptr engine;
  Ship(unique_ptr engine_) :
      engine(move(engine_)) {}
};

int main() {
  auto ship =
      make_unique(
          make_unique(42));

  // Swap it out
  auto engine =
    exchange(
      ship->engine,
      make_unique(0);

  // Read engine
  cout << engine.fuel << endl;

  // Move it back
  ship->engine = move(engine);

  ...
}

Note how we're doing a make_unique(0), making a temporary engine to swap into its place. This ensures that if someone else references the engine, they'll get something of the expected shape.

Alternatively, Ship could have a optional>, so we can just swap a nullopt into its place. 15

"Wait, can't we skip all this swapping and just read it, if we know nobody else accesses it?"

We can! But we'll get to that later on, when we talk about simplified borrowing and how we might use it for C++.

The rule mentioned that we can also destroy the containing struct to read its members, let's see an example of that.

This example is similar, a Ship contains a unique_ptr.

We remove the unique_ptr from the containing Ship, and then destroy the Ship.

struct Engine {
  int fuel;
  Engine(int fuel_) : fuel(fuel_) {}
};

struct Ship {
  unique_ptr engine;
  Ship(unique_ptr engine_) :
      engine(move(engine_)) {}
};

int main() {
  auto ship =
      make_unique(
          make_unique(42));

  auto engine = move(ship->engine);
  ship = nullptr; // Deallocates ship
  // Can't use ship again, per rule 2

  cout << engine.fuel << endl;
}

This is such a common operation that other single-ownership based languages have syntax for destroying a struct and extracting its members.

Vale's move-destructuring does this, e.g. [engine] = ship; but the static analysis tool could enforce we do it manually for C++.

The above example is fairly simple, but it could get a bit more difficult if we don't have ownership of the containing struct conveniently nearby.

We may need to refactor and pipe ownership of the containing struct all the way to here. Further below, we'll talk about this drawback and ways to address it.

14

Thanks to u/wearingdepends for the suggestion to use std::exchange here!

15

Or we can put nullptr into that unique_ptr instead of having an optional, though that would require some adjustments to our scheme elsewhere.

Resizable Collections

Rule 6: Only use std::array and resizable collections, don't use raw arrays directly.

This is because raw arrays temporarily risk some unsafety when we first make them and when we're destroying them.

There are a lot of ways we can later relax these restrictions.

For example, we could have a runtime-sized array where we construct it with a size N and a closure, and the library (or language) will invoke that closure N times, filling the array's elements with the closure calls' results.

Or we can make something halfway between std::array and std::vector, which doesn't resize past its initial capacity, but still has size and capacity fields and methods like push, pop etc.

Vale's arrays are like that, and they're used to implement the standard library's array list, hash map, etc.

Bounds-checked array slices could also make life easier, so that functions could take in an arbitrary range of elements.

Reading from Collections

Rule 7: To access an element of an array, we need to take ownership of it by removing it.

This is pretty easy for a collection like a hash map. Simply remove the element, and put it back when we're done.

Nobody should access the hash map in the meantime. It wouldn't cause any unsafety, but could be a logic error.

Arrays are a bit trickier. When we temporarily remove an element, we have to either:

  • Shift all the later elements down by one slot, and once we're done, unshift them all and put the element back in.
  • Temporarily swap the last element into its place, and when we're done, do the reverse.

Another way to get an element out of the array is to destroy the entire thing, thus taking ownership of all its elements. Sometimes this can be pretty useful.

Branching

A few last rules to make this work:

  • We must move (or destroy) the same variables from both branches of an if-statement.
  • If we move (or destroy) something from inside a loop, we need to reinitialize it in that same iteration.

These might sound irksome, but we can always wrap a local in an optional to work around it.

The approach so far

So far, we've talked about:

  • How unique_ptr and owned values are safe to access.
  • How we can write a program using just those, without non-owning pointers/references.
  • How we can use structs (including swapping and destructuring).
  • How we can use collections.
  • How we can safely use if-statements and loops.

The foundational rules above form "borrowless affine style", and they've achieved their goal: we now have a memory-safe subset of C++.

But let's take a step back and recognize its drawbacks, and see how we might address them by blending in some other techniques.

Besides being verbose, there are also some architectural consequences:

Drawback 1: Since Rule 3 requires us to change our function signature (by borrowing the vector), and all of our callers' callers' callers, this technique has become a viral leaky abstraction.

Drawback 2: Rule 4 puts a lot of our objects into collections, making our program almost similar to a relational database.

Drawback 3: Since we can't use raw pointers and references, we effectively cut ourselves off from mutable aliasing. This means we can't use fast approaches like intrusive data structures and graphs, and we can't use useful patterns like observers, back-references, dependency references, callbacks, delegates and many forms of RAII.

These are familiar to Rust users; &mut is semantically equivalent to everything we're doing here and has the same drawbacks. This is the downside of eliminating mutable aliasing. Luckily, Rust partially resolves them with Rc and RefCell, for those willing to use them.

So should we do something like shared_ptr> then, or are there any other options?

There are indeed other options! Let's talk about generational references, random generational references, and constraint references.

Generational References

A generational reference is where each object has a current "generation number".

  • When we want to point to an object, we remember its address and its generation.
  • When we free an object, we increment its generation number.
  • To get access to an object, we first check ("generation check") that the current generation number matches the remembered generation number. If not, we safely signal a segmentation fault.

It's equivalent to the generational indices method, but applied to an entire heap.

To learn more, check out this article which talks about how we added them to Vale (though, the next section talks about an improved version).

Vale has some additional mechanisms that help generational references, but we'll need to add something extra for C++.

Above, when I mentioned we can "get access to an object", I didn't actually mean dereferencing. We'll need an extra step of "checking out" the contents to take ownership of it from the original owner. Before the end of the scope, we're required to put something back into that spot. 16 17

Using a generational reference would look something like this snippet. 18

An object lives inside a gowned wrapper.

We use its ref() method to make a gref to it. 19

We can open a gref, which does a generation check and gives us something we can dereference.

// Makes an object
gowned ship =
    make_gowned(42);

// Makes a generational reference to it
gref shipRef = ship.ref();

// Does a generation check
auto shipHandle = shipRef.open();

// Prints 42
cout << shipHandle->fuel << endl;

There's a couple downsides so far:

  • It forces objects onto the heap, like Rc and shared_ptr.
  • It uses an allocator which segregates by size class and never releases memory back to the OS, to ensure that nobody messes with the generation number of the object and there is no reusing of numbers.

We can address both by keep the generations in a separate thread-local table. 20

There's also an alternative technique that's about 3x faster than that though: random generational references!

16

This is basically the same thing as Rust's RefCell.

17

We might also need enable_genref_from_this, for the same reasons enable_shared_from_this exists.

18

Let me know if you want some example code for this and I can dig it up from the Vale histories.

19

We can also just copy an existing gref.

20

Vale used to do this, but switched to random generational references which are about 3x faster. Someone also made a Rust crate for this table-based approach!

Random Generational References

A random generational reference is a generational reference with one adjustment: it uses a pseudo-random generation number for every object, or even a thread-local ever-increasing integer. 21 22

Usage would be the same as the above generational references, and I include a sample implementation further below.

If you've ever heard of Arm's memory tagging, this is like that but with a wider tag.

While this approach is promising, it's still ultimately unknown. I'd recommend waiting until it's studied more before using it.

This approach has a lot of benefits:

  • The object can live on the stack, inside other objects, directly inside arrays, or even inside custom allocators.
  • We can reuse a specific spot in memory as many times as we want.
  • We're able to release memory back to the OS, in environments with virtual memory. 23

This is a very strong stochastic approach, similar to how passwords work.

It does have a theoretical downside. For example, if we have an invalid access in our server code that's causing (worst case) six million loud errors a second and we decide to ignore it, then after 73,250 years 24 on average it could reuse the same generation as something that was there before, in which case the invalid access bug could cause some unsafety.

Those well-versed in statistics will recognize that this isn't really a problem, but let's explore it a little.

The odds of an invalid access happening undetected is always 1/2^64 for a 64-bit generation.

  • The odds don't change with the number of live objects.
  • The odds don't change with the how long the program's been running.
  • The odds don't change with the the number of objects that have lived in that particular location.
  • The odds don't change with the the number of previous generation check failures, because the first one brings down the entire process.

It also helps to keep in mind that these probabilities only apply to the error detection mechanism, not to the program itself.

One of my beta readers asked:

"How does this compare to Rust? It seems like the probabilistic detection wouldn't be as good."

That would be true, except that most Rust programs use unsafe or have it in their dependencies, even when you don't count the standard library.

When someone uses unsafe to get around the borrow checker's restrictions, even if they think really hard about unsafe's more arcane interactions, bugs can remain hidden for a long time, stealthily causing undefined behavior in the unsafe block and in the safe code around it.

We'd similarly use random generational references to get around the restrictions of affine style, and fortunately, any invalid accesses are detected very loudly as a check failure brings down the entire program. Bugs are discovered very quickly, instead of causing mysterious behavior for years.

So it's better in some ways, worse in others. It's just a different approach.

Vale actually went one step further and replaced unsafe with a "skip-check dereference" operator to skip a generation check in release mode. The major benefit is that a compiler flag can ignore these in dependencies, so we no longer have to trust that our dependencies used unsafety well.

Even without that, when we're interoperating with a large amount of existing unsafe C++ code, this seems like an improvement over the pre-existing code.

There are a couple complications for adding this to C++:

  • If nearby unsafe C++ code leaks a generation number (such as via a buffer bleed) and some unsafe code somehow makes a generational reference from user input somehow, an attacker could exploit that.
  • The optimizer might notice that we're intentionally reading the generation number of freed memory in some cases (undefined behavior, in other words), and start reacting in mysterious ways. 25 We'd need to either:
    • Put our data on a thread-local side-stack instead of the actual stack.
    • Preemptively detect the cases that the optimizer would detect, which could be quite difficult.
    • Modify the toolchain (which would be out of scope for our quest). 26

Usage would be the same as the above normal generational references, and a simple C++ implementation would look roughly like the below code (also available here).

extern size_t vrefNextKey;

template
class vref {
public:
  vref(vowned* own_) :
    own(own_),
    rememberedKey(own_->currentKey) {}
  ~vref() {}

  vref_guard open() {
    return vref_guard(own, rememberedKey);
  }

private:
  size_t rememberedKey;
  vowned* own;
};

template
class vref_guard {
public:
  vref_guard(vowned* own_, size_t rememberedKey) :
      own(own_) {
    assert(rememberedKey == own->currentKey);
    assert(own->present);
    own->present = false;
  }
  ~vref_guard() {
    own->present = true;
  }

  T* operator->() { return &own->contents; }
  const T* operator->() const { return &own->contents; }

private:
  vowned* own;
};

template
class vowned {
public:
  vowned(T contents_) :
      present(true),
      currentKey(vrefNextKey++),
      contents(std::move(contents_)) {}
  ~vowned() {
    assert(present);
  }

  vref ref() {
    return vref(this);
  }

private:
  friend class vref;
  friend class vref_guard;

  bool present : 1;
  size_t currentKey : 63;
  T contents;
};

template
vowned make_vowned(P&&... params) {
  return vowned(T(std::forward

(params)...)); }

This simple implementation uses:

  • A monotonically incrementing global vrefNextKey integer as its "pseudo-random" number generator.
  • A 63 bit generation (so we can use 1 bit for the present boolean), making the odds of a false negative about 1/2^63.

This approach has one additional benefit. For domains where its appropriate, it can be turned completely off for production code, and it would be as efficient as normal C++. This can be a pretty stellar tradeoff for single player games, compilers, or sandboxed situations like webassembly modules or apps.

21

Increasing it monotonically could have some security implications though, so perhaps use some randomness.

22

It could also be global. Vale does neither, and has an implicit restrict uint64_t* parameter to every function, which optimizes very nicely.

23

This relies on the OS detecting accesses to released memory and raising segmentation faults.

24

Given a 64 bit generation, it will take an average of 13 quintillion tries to trigger a false negative.

If there's only one failure per second, it's 439 billion years on average to cause unsafety.

If there's only one failure per week, it would take 266 quadrillion years on average to cause unsafety.

If there's six million check failures per second (the largest DDoS in history), it's 73,250 years on average to cause any unsafety.

Comfortable odds, I'd say!

Still, I'd recommend waiting on this approach until it's explored a bit more by the broader security community.

25

Normally the optimizer won't realize it's undefined behavior, but we can contrive some cases, such as if we return a reference to some stack-allocated memory.

26

Or, if we're willing to modify the language or compiler, then we could either:

  • Modify the optimizer.
  • Somehow communicate to it that this is fine.
  • Add random generational references in after all the optimization passes.

Constraint References

Another option is to use something called a constraint reference, which allows for memory-safe mutable aliasing, while allowing objects to live on the stack or directly inside another object.

Basically, we:

  • Put the reference count directly inside the object.
  • We refer to the object with a constraint_ref which works similarly to a shared_ptr.
  • When the object goes out of scope, it asserts that the count is zero, that no objects point to it any more.

A simplified implementation would look something like this (also available here):

template
class cref {
public:
  cref(cowned* own_) : own(own_) { own->refCount++; }
  ~cref() { own->refCount--; }
  cref_guard open() { return cref_guard(own); }

private:
  cowned* own;
};

template
class cref_guard {
public:
  cref_guard(cowned* own_) :
      own(own_) {
    assert(own->present);
    own->present = false;
  }
  ~cref_guard() {
    own->present = true;
  }
  T* operator->() { return &own->contents; }
  const T* operator->() const { return &own->contents; }

private:
  cowned* own;
};

template
class cowned {
public:
  cowned(T contents_) :
      present(true),
      refCount(0),
      contents(move(contents_)) {}
  ~cowned() {
  	assert(present);
  	assert(refCount == 0);
  }

  cref ref() {
  	return cref(this);
  }

private:
  friend class cref;
  friend class cref_guard;

  bool present : 1;
  size_t refCount : 63;
  T contents;
};

It works similarly to a foreign key constraint in SQL, hence the name constraint reference. 27

This was also explored by Adam Dingle and David Bacon in their paper Ownership You Can Count On:
A Hybrid Approach to Safe Explicit Memory Management
, who made an entire C# variant using this, named Gel. This is also one of the mechanisms behind the language Inko, as described in the article Friendship ended with the garbage collector.

To get the object from the constraint_ref, we "check out" the contents and take ownership of it from the original owner. Before the end of the scope, we're required to put something back into that spot, via a constraint_guard object. 28 29

The obvious downside, of course, is that if you violate the constraint, your entire program halts. Still, this can be useful in development mode, and then we can compile these to raw pointers or generational references in release mode. 30

27

If you want to read more about constraint references, check out The Next Steps for Single Ownership and RAII. The ones described in there are slightly different in that they don't require "checking out" the object.

28

This is basically the same thing as Rust's RefCell.

29

We might also need enable_constraint_from_this, for the same reasons enable_shared_from_this exists.

30

Older versions of Vale used these for development mode, and would compile them into generational references for release mode. Later on, we managed to make generational references so efficient in Vale (by combining them with regions and something like the aforementioned affine style) that we defaulted everything to generational references in both modes.

The approach so far

So far, we've talked about this "borrowless affine style", where we only access things through unique_ptrs and owned values.

Then, we added some mutable aliasing goodness, via constraint references and generational references. Now it's a little more ergonomic.

But let's see what else we could do!

Let's talk about adding some limited aliasing via simplified borrowing. It doesn't require a full Rust-style borrow checker, lifetimes, or annotations, so it should be possible to implement it in a basic static analysis tool.

Simpified Borrowing

Above, when we were swapping out a Ships Engine so we could read it, we asked:

"Wait, can't we skip all this swapping and just read it, if we know nobody else accesses it?"

One might think that we would need a full borrow checker for this. But is there a simpler way?

There is! We can use a technique from Val, a sort of simplified borrowing. 31

Rust's Graydon Hoare talked about this kind of system in his article The Rust I Wanted Had No Future:

I wanted & to be a "second-class" parameter-passing mode, not a first-class type, and I still think this is the sweet spot for the feature. In other words I didn't think you should be able to return & from a function or put it in a structure. I think the cognitive load doesn't cover the benefits. Especially not when it grows to the next part.

and then:

It did not reason about lifetime compatibility nor represent lifetimes as variables, and I objected to that feature, and still think it doesn't really pay for itself. They were supposed to all be inferred ...

Austral's Fernando Boretti wrote a really good article on this. He mentions that it's even more restrictive than Rust's borrow checker, but that's why we're pairing it with mutable aliasing via generational references and constraint references. 32

Let's make it a little more concrete!

Simplified Unique Borrowing

We'll add mutable non-owning pointers back in, with these rules:

  • Don't access the original object while it exists.
  • Don't return them.
  • Don't store them in structs/arrays.
  • Don't alias them.

With these rules, we don't need a full borrow checker 33 or any annotations.

We could call this a unique borrow.

This snippet is similar to the example from before, where a Ship contains an Engine.

Except now, we're just reading the engine directly with a unique borrow.

struct Engine {
  int fuel;
  Engine(int fuel_) : fuel(fuel_) {}
};

struct Ship {
  unique_ptr engine;
  Ship(unique_ptr engine_) :
      engine(move(engine_)) {}
};

int main() {
  auto ship =
      make_unique(
          make_unique(42));

  Engine& engine_borrow = *ship.engine;
  // Can't use ship while engine_borrow exists

  cout << engine.fuel << endl;
}

Let's talk about that second rule, "don't return them". This seems like it would make getters complicated.

For example, this shipAt method wouldn't compile.

struct Ship {
  int fuel;
};
struct Shipyard {
  vector ships;
};
Ship& shipAt(
    Shipyard& shipyard,
    int index) {
  // Error, can't return this.
  return shipyard.ships[index];
}

int main() {
  Shipyard shipyard = ...;

  shipAt(shipyard, 3).fuel = 42;
}

That's because shipAt returns a unique borrow, which isn't allowed in our rules.

There is a workaround, however. We can make shipAt take a function as an argument, like this.

struct Ship {
  int fuel;
};
struct Shipyard {
  vector ships;
};
Ship& shipAt(
    Shipyard& shipyard,
    int index,
    std::function func) {
  func(shipyard.ships[index]);
}

int main() {
  Shipyard shipyard = ...;

  shipAt(shipyard, 3, [](Ship& ship){
    ship.fuel = 42;
  });
}

Here, shipAt takes a function that it will then give a Ship&.

Now, we aren't violating the "don't return them" rule. Instead of returning it, shipAt is just passing it to another function which was supplied by the caller.

This function returns void but we can make one that returns a T that the function returns. We can also take an arbitrary callable, instead of the (sometimes slower) std::function.

Adding syntactic sugar is out of scope for our hypothetical static analysis tool, but I'm a language nerd, so I'll mention Swift's trailing closure syntax, or Kotlin's inline function syntax.

The previous callsite:

shipAt(shipyard, 3, [](Ship& ship){
  ship.fuel = 42;
});

...could look like this instead:

shipAt(shipyard, 3) [](Ship& ship){
  ship.fuel = 42;
};

Or, if we want to go overboard and use generic lambdas under the hood, we could even make it look like this. 34

shipAt(shipyard, 3) (ship){
  ship.fuel = 42;
}

But alas, we're explicitly not modifying the C++ language or compiler in this article; this syntactic sugar is just an interesting thought experiment.

31

We're blending Val and Vale! If only we had something from Vala too, we'd have the whole set!

32

By the way, if you haven't checked out Austral, give it a look! It uses one of my favorite features, linear types.

33

It could be said that this is a borrow checker, which would make the title of this article a bit awkward. However, most people are coming into this article thinking that "borrow checker" means something like Rust's borrow checker, so the title is trying to work within that pre-existing connotation.

34

In other words, it would expand that (ship){ to something like [](auto& ship){ under the hood. I also removed a semicolon here, because this is all theoretical and nobody can stop me in my madness.

Simplified Immutable Borrowing

We could get away with just having this "affine style" and the unique borrows described above, but we can also add a simplified immutable borrowing as well.

We can add it to our little theoretical C++ static analysis tool, since it still doesn't require a full borrow checker with annotations.

We would add immutable non-owning pointers back in, and we'd follow these rules:

  • Don't access the original object while it exists.
  • Don't return them.
  • Don't store them in structs/arrays.
  • Don't modify anything through them.
  • When accessing a field through a const*, immediately cast it to another const*.

It's pretty similar to the previous simplified unique borrowing, except we can alias them, and can't modify things through them.

Fun fact: This enables seamless fearless structured concurrency, as long as we don't choose to introduce data coloring (such as Rust's Sync/Send). 35 We'll talk more about concurrency further below.

The approach so far

So far, we've talked about this "borrowless affine style", where we only access things through unique_ptrs and owned values.

We also just added simplified borrowing, which is a little restrictive but resolves some of the awkwardness of borrowless affine style.

That combination alone is still quite difficult. Just like with Rust, we'll find ourselves doing a lot of cloning, bounds checking, and hashing to work around its restrictions, and we can't do patterns like observers, back-references, dependency references, callbacks, delegates and many forms of RAII.

Luckily, we also have mutable aliasing via constraint references and generational references, to handle all those and make things feel a little more like the C++ spirit we're used to.

A pretty good combination so far!

35

More specifically, as long as we don't choose to add escape hatches for immutable references, such as how Rust's RefCell acts as an escape hatch for their shared references.

We'll of course be adding something like shared_ptr.

The reason we haven't yet is because I wanted to show you that we don't need reference counting to add memory safety to C++. 36

So just for fun, let's ask the question: how much do we really need reference counting?

This is a familiar question to anyone who has used Rust. One of my favorite things to do in Rust is to see how far we can get by just using the borrow checker, and not using Rc>. However, that Rust usage had the same three drawbacks we mentioned above for affine style:

  • When we need a &mut, we're required to change the signature of the containing function, its callers, its callers' callers and so on, becoming a viral leaky abstraction.
  • When we need to mutate something, we often need to put a lot of our objects into collections, making our program almost similar to a relational database.
  • Since we don't have mutable aliasing, we can't use fast approaches like intrusive data structures, observers and graphs, and we can't use useful patterns like observers, back-references, dependency references, callbacks, delegates and many forms of RAII 37.

In my opinion, this shows the wisdom of the Rust language designers in adding Rc and RefCell to their standard library.

So does all this mean we should add something like Rc>?

Perhaps.

We already have gref, vref, and cref above, which all add mutable aliasing, so it's unclear if we need reference counting.

We also have some techniques available to us that Rust doesn't. For example, in cases where there would only be two people with references to an object, we could make a bidirectional optional reference, where if we destroy one side we null out the other. 38

In fact, Vale doesn't have any sort of shared ownership quite yet, so that we can explore these techniques for a while longer. However, we'll likely add it before 1.0, because we can contrive a few situations where it's unavoidable. For example, we might want a FileCache object that counted how many classes had a file open for reading. If anyone knows of an alternative to that, let me know!

So, all that said, let's talk about how we might add shared ownership in!

36

Besides, the title kind of promises no reference counting, and I stretched the title's veracity enough by adding simplified borrowing!

37

RAII is about automatically affecting the world outside our object. To affect the outside world, the borrow checker often requires us to take a &mut parameter or return a value, but we can't change drop's signature. To see this in action, try to make a handle that automatically removes something from a central collection. Under the hood we usually use unsafe mechanisms, including FFI.

38

I even made a thread-safe version of these with two mutexes, when I was working on Earth.

It would likely take the form of a shared_ptr>.

We would "check out" the value by using the .value() method and then swapping something into its place.

After we're done using it, we would put the object back into the shared_ptr's optional.

// Makes an object
auto original_ship =
    make_shared>(
        make_optional(42));

// Makes another reference to it
auto shipRef = original_ship;

// Check it out.
// This value() asserts it's present
auto ship = shipRef->value()

// Prints 42
cout << ship.fuel << endl;

// Put it back
*shipRef = make_optional(ship);

We could also make a "handle" object that uses RAII to ensure we put that ship back into the shared_ptr, similar to what we did with vref/cref.

The approach so far

So far we have:

  • Borrowless affine style, via unique_ptr and owned values.
  • Constraint references.
  • Generational references, random generational references.
  • Simplified borrowing.

Between all these, we might be able to add some memory safety to C++!

This isn't the only blend, of course. There are more!

  • Something based on single-threaded reference counting, but with Vale-style region borrowing for structured concurrency and to eliminate most refcounts, then we'd throw in some value types like in Swift and C#'s struct for better performance. Bake at 400 degrees for 20 minutes.
  • An approach blending arenas with Vale-style region borrowing. I talked about this a bit at Handmade Seattle, and it would be similar in spirit to Verona but without garbage collection.
  • An approach along the lines of the "MMM++" (mentioned here) and the theoretical Arrrlang.

...but this article is already 20+ pages! So let's stay with this blend for now.

Let me know if you want to hear about those, and I'll be happy to make this into a series. (Also consider sponsoring on patreon or GitHub!)

Interoperability with existing code

I like this general approach of finding a memory-safe subset of C++, because we can gradually migrate existing C++ to it.

For this particular blend, we would migrate on a type-by-type basis. We'd have a whitelist file where we list all the classes that should follow these rules. Alternately, we can have a tooling-recognizable comment above any classes that follow these rules, or have them inherit a certain marker class.

I think this is a better starting point than the usual approach of having "safe functions", because for a function to be safe, all arguments handed in have to be safe, which quickly becomes a viral leaky abstraction. Same thing goes for scopes and files.

We should have both. Safe functions/scopes/files will be useful in the late stages of migrations after we've migrated over most types.

As an extra benefit, generational references and constraint references can be turned off with #defines, making them exactly equivalent to bare C++. This means we can gradually migrate our programs to use them turned off, and then try flipping them on all at once.

Concurrency safety

All these techniques are either concurrency-safe already or can be made concurrency-safe fairly easily. By "concurrency-safe", I mean safe from risk of data races.

Borrowless affine style is already safe, since only one thread has access to an object at any given time. Though, it could be awkward to use in practice, because other threads with IDs can't actually read the object they're referring to. Luckily, we're blending other mechanisms in.

Simplified unique/immutable borrowing is already thread safe.

One might think that shared_ptr> can't be made thread-safe, because Rust's Rc> isn't thread-safe. However, that's because of a (mis)feature in RefCell's design. Instead, let's make it so that accessing a shared_ptr via an immutable borrow will always produce another immutable borrow. With that, it's safe to concurrently read a shared_ptr from multiple threads. We wouldn't even need any data coloring like Sync/Send, which is nice.

Alternately, we can add something like Rust's Mutex, perhaps called std::mutexed. We would then be able to use it like shared_ptr>, and it would be thread-safe.

Random generational references can be made safe if we "scramble" the generations that cross thread boundaries. Like in Vale's design, we could add the same random number to the object's generation, all indirectly owned objects' generations, and any generational references inside them 39, recursively.

Regular generational references can also be made safe, though the thread-crossing "scramble" would require a two-pass recursion: the first pass would gather a hash map of all objects in the hierarchy and their new generations, and the second pass would update any contained references to each other.

Constraint references would do something similar, with some recursions and a hash map. It would note all the objects in the hierarchy, and then assert that there are no references outside to anything inside the hierarchy.

Alternately, something like Vale's region borrowing could avoid any of the scrambling or assertions for generational references or constraint references. Basically, we'd make it so pure functions or "pure blocks" could immutably access everything outside their scope. I talk about this more in Seamless, Fearless, and Structured Concurrency.

39

This is so that references to another object inside the same hierarchy are also updated.

How could we make all this happen?

The nice thing about all of this is that it wouldn't require any big language changes or committees or standards. It could be implemented with some static analysis, since these are all pretty simple locally-verifiable rules. Perhaps it would only be enabled for certain types, or any types with a certain suffix.

If someone wants to investigate this, let me know and I'd be happy to pool knowledge!

I can even imagine a future where there's some sort of "C++ safe mode" where this static analysis is enabled by default, and then we break out of it with unsafe blocks.

Or perhaps a project like Carbon or CppFront could support something like these approaches. 40

A lot of people are working on adding memory safety to C++, from a lot of really promising angles! Here are just a few:

Huge thanks to mttd and gavinray for a lot of these links!

40

Herb/Chandler, let me know you ever want to talk memory safety over some cider!

Conclusion

Thats it! I hope you enjoyed this whirlwind tour of the various ways we can add memory safety to C++.

If you enjoyed this article, please consider donating via patreon or GitHub! With your support, I can write articles like this more often, and perhaps even do it full-time one day.

If you have any questions, feel free to message me on twitter, the discord server, or subreddit.

Until next time!

- Evan Ovadia

With your help, we can launch a language with speed, safety, flexibility, and ease of use.

We’re a very small team of passionate individuals, working on this on our own and not backed by any corporation.

If you want to support our work, please consider sponsoring us on GitHub!


Sponsor us on GitHub

Those who sponsor us also get extra benefits, including:

  • Early access to all of our articles!
  • A sneak peek at some of our more ambitious designs, such as memory-safe allocators based on algebraic effects, an async/await/goroutine hybrid that works without data coloring or function coloring, and more.
  • Your name on the vale.dev home page!

With enough sponsorship, we can:

  • Start a a 501(c)(3) non-profit organization to hold ownership of Vale. 41
  • Buy the necessary computers to support more architectures.
  • Work on this full-time.
  • Make Vale into a production-ready language, and push it into the mainstream!

We have a strong track record, and during this quest we've discovered and implemented a lot of completely new techniques:

  • The Linear-Aliasing Model that lets us use linear types where we need speed, and generational references where we need the flexibility of shared mutability.
  • Region Borrowing, which makes it easier to write efficient code by composing shared mutability with the ability to temporarily freeze data.
  • Higher RAII, where the language adds logic safety by enforcing that we eventually perform a specific future operation.
  • Perfect Replayability makes debugging race conditions obsolete by recording all inputs and replaying execution exactly.

These have been successfully prototyped. With your sponsorship we can polish them, integrate them, and bring these techniques into the mainstream. 42

Our next steps are focused on making Vale more user-friendly by:

  1. Finalizing the compiler's error messages and improving compile speeds.
  2. Polishing interop with other languages.
  3. Growing the standard library and ecosystem!

We aim to combine and add to the benefits of our favorite languages:

We need your help to make this happen!

If you're impressed by our track record and believe in the direction we're heading, please consider sponsoring us:


Sponsor us on GitHub

If you have any questions, always feel free to reach out via email, twitter, discord, or the subreddit. Cheers!

41

Tentatively named the Vale Software Foundation.

42

Generational references, the linear-aliasing model, and higher RAII are all complete, and Region borrowing, fearless FFI, and perfect replayability have been successfully prototyped. Be sure to check out the experimental version of the compiler!

Read More