Ownership

Ownership is a concept used to help manage memory in Boson.

Problem

Consider the following example in C.

void reportResult(struct result *res);
struct result *processWidget(struct record *r);

void processRecords(struct record *r, size_t record_count) {
	for (int i = 0; i < record_count; i++) {
		res = processWidget(r + i);
		reportResult(res);
	}
}

The basic idea above is straight-forward. Accept an array of records and process them. However we have a problem. There may be leaks in this function, but we actually can’t know unless we look at other code.

For instance, it’s likely that processWidget is implemented something like this:

struct result *processWidget(struct record *r) {
	struct result *res = malloc(sizeof *r);
	res->stats = ...;
	return res;
}

In which case, we need to free the struct result * in processRecords.

void processRecords(struct record *r, size_t record_count) {
	for (int i = 0; i < record_count; i++) {
		struct result *res = processWidget(r + i);
		reportResult(res);
		free(res);
	}
}

Or do we? What does reportResult do? “’ void reportResult(struct result *res) { writeResult(…); free(res); } “’

If ‘reportResultfrees thestruct result *then we can't do it inprocessRecords`, or we’ll have an error, but we don’t know if it does unless we look at the code. C programmers may roll their eyes at this example. It may be contrived, and there are common practices and idioms that help manage this issue. But this example still illustrates the point. If it’s down to idiom and common practice, mistakes will always be made. Code gets much more complex than this example, and reasoning about it can get a lot more difficult. Worse, the compiler and language itself does nothing to help you.

Solution

We introduce the concept of the “owner” of a pointer. Every pointer has exactly one owner, and that owner has exactly one responsibility: to give up ownership to someone else. Every owner must give up its ownership to someone else before the end of its scope. Ownership is given up by passing an owned pointer to a function that takes an owned pointer argument. After passing an owned pointer to a function that accepts an owned pointer argument, the caller no longer owns the pointer.

In our example above, ownership might be used as follows:

func processWidget(r *record) (owned *result) {
	var res owned *record = alloc(result);
	res->stats = ...;
	return res;
}

func reportResult(res owned *result) {
	writeResult(...);
	// We own res, so we *must* pass its ownership off somewhere before returning.
	// In this case, we will pass ownership to free()
	free(res);
}

func processRecords(r []record, record_count isize) {
	for var i int = 0; i < record_count; i++ {
		var res owned *result = processWidget(&r[i]);
		reportResult(res);
		// Here, res is still a pointer, but it is no longer owned, so we *cannot* call free()
		// free(res);
	}
}

Problems With the Solution.

Ownership will ensure that every allocated object is freed exactly once, but it doesn’t help solve dangling pointers. Above, processRecords still has a pointer to res even after ownership is given to reportResults and it is freed.

In order to be memory safe, we need to ensure pointers to free memory can’t be dereferenced. How?

Possible Solutions To the Problems With the Solution

A train of thought…

Rust does lifetime analysis. Can we do that? Probably not. The borrow checker and analyzer is one of Rust’s key features, and building something comparable would require massive complexity.

We *should* be thinking about object lifetimes, though.

Prevent assignment of non-owned pointers. This could work. Thinking again about lifetimes, we can assume that a non-owned pointer is valid only as long as its lexical scope. Saving the pointer off somewhere that may live longer than the thing pointed to, i.e. storing it in a data structure, etc. can be considered invalid.

We may need compiler-support for some special kind of reference-counted pointer for instances where multiple data structures need pointers to the same object.

In fact, the only thing that needs to be restricted here is assigning an un-owned pointer into an object whose lifetime is unknown, i.e. another struct that has been alloc’d

Maybe with [Unsafe], which has yet to be designed, something like C++’s shared_ptr or Rust’s Rc or Arc can be developed.

This might be bolstered by the fact that alloc probably can’t allocate a struct with unowned pointers anyway.

The only way I’ve imagined to initialize a struct with unowned pointers is with a literal:

type somestruct struct {
		ptr *foo
		someCount int
}

var s somestruct = somestruct{ ptr: &foo, someCount: 0 }

but I haven’t fully baked struct declaration and initialization in my head yet.

Returning unowned pointers also needs to be restricted, since that is a way for them to escape their scope. If that is the case, though, it is impossible for e.g. a map data structure to return an unowned pointer to a value it is holding. This is where Rust’s lifetimes help… being able to associate the lifetime of the pointer with the lifetime of the map…

Some kind of lifetime analysis is probably required, if this is going to be a viable language.

Lifetime Analysis

I think lifetime analysis should be possible with a couple rules.

1. Owned pointer variables can only be assigned once, never reassigned (reassigning an owned pointer will leak the pointer)

2. unowned pointers cannot be struct members. We can’t guarantee two objects have the same lifetime.

3. when returning an unowned pointer from a function, it must have the same lifetime as one of the function’s arguments.

Hmmm… what about

func example(m *map) {
    var w *widget = map_get(m, "key"); // w pointer has same lifetime as m.
    map_delete(m, "key");
    // w points at freed memory
}

Rust has mutable and immutable refs…. am I just reinventing Rust?

Yes, but thats ok. I want to have a self-hosting language small and simple enough to port, but with some nice features from modern languages.