Single Ownership and Memory Safety without Borrow Checking, Reference Counting, or Garbage Collection

Single ownership is once of those concepts that’s both easier and more powerful than we realize.

People often think it’s complex, because it most often appears in languages that are already complex for separate reasons.

Let’s dispel that myth, and figure out what it really is!

Even if you already know what single ownership is, you’ll probably find some interesting surprises:

  • You don’t need borrow checking for memory-safe single ownership.
  • You can use it to enforce all sorts of compile-time guarantees.
  • You can blend it with other memory management techniques!

Below, I’ll explain single ownership from a C foundation, and then we’ll see the weird things it can do.

We often track single ownership manually in C

With manual memory management, we usually make it clear who’s responsible for eventually freeing certain memory, via documentation or naming.

For example, strdup will return a heap-allocated buffer, which the caller then owns. From GLib’s strdup documentation:

The caller of the function takes ownership of the data, and is responsible for freeing it.

So we make sure to eventually deliver this data to another function that destroys it.

If we don’t do that, we get a memory leak; the memory is unusable for the rest of the program’s run.

void main() {
  char* myBuffer = GetRealPath("./myfile.txt");

  // prints: /Users/Valerian/Bogglewoggle/myfile.txt
  printf("Real path: %s\n", myBuffer);

  // uh oh, we forgot to free(myBuffer)!
  // Memory leak.
}

If we accidentally do it multiple times, the program might crash or exhibit undefined behavior.

void main() {
  char* myBuffer = GetRealPath("./myfile.txt");

  // prints: /Users/Valerian/Bogglewoggle/myfile.txt
  printf("Real path: %s\n", myBuffer);

  free(myBuffer);
  // Shenanigans ensue!
  free(myBuffer);
}

As any C programmer knows, we carefully track who owns the data, all the way from when it’s created, to when it’s finally destroyed.

At any given time in between, we can generally identify who “owns” certain data, whether it be a certain local variable or a field in some struct somewhere.

Of course, other pointers to the data can exist, they just don’t own the data. We have a mental distinction between owning pointers and non-owning pointers.

If you’ve ever implemented a balancing binary search tree like a red-black tree or an AVL tree, recall that a parent conceptually has “owning” pointers to its children, and its children have non-owning pointers back to their parents.

Single ownership isn’t just for pointers and malloc and free, it’s to anything that we have a future responsibility for.

For example, pthread_create creates a handle that we’re responsible for eventually pthread_destroying. We generalize this a bit more later, but for now let’s just think about heap allocations.


Source link