If a memory object has only one pointer to it, that pointer is theownerof the memory object. With the single owner, it becomes straightforward tomanage the memory for the object. It also becomes trivial to synchronize accessto that memory object among multiple threads, because it can only be accessedby the thread that controls that single pointer.
This can be generalized to a graph of memory objects interconnected by pointers,where only a single pointer connects to that graph from elsewhere. That singlepointer becomes theowner of all the memory objects in that graph.
When the owner of the graph is no longer needed, then the graph of memoryobjects it points to is no longer needed and can be safely disposed of. If the owneritself is no longer in use (i.e. is no longerlive) and the owned memoryobjects are not disposed of, an error can be diagnosed.
Hence, the following errors can be statically detected:
int* allocate();// allocate a memory objectvoid release(int*);// deallocate a memory object@livevoid test(){auto p = allocate();}// error: p is not disposed of@livevoid test(){auto p = allocate(); release(p); release(p);// error: p was already disposed of}@livevoid test(){int* p =void; release(p);// error, p does not have a defined value}@livevoid test(){auto p = allocate(); p = allocate();// error: p was not disposed of release(p);}
Functions with the@live attribute enable diagnosing these sorts of errors bytracking the status of owner pointers.
Tracking the ownership status of a pointer can be safely extended by adding thecapability of temporarillyborrowing ownership of a pointer from theowner.Theowner can no longer use the pointer as long as theborrower is stillusing the pointer value (i.e. it islive). Once theborrower is no longerlive, theowner can resume using it. Only oneborrower can be liveat any point.
Multipleborrower pointers can simultaneously exist if all of them arepointers to read only (const orimmutable) data, i.e. none of them can modify the memoryobject(s) pointed to.
This is collectively called anOwnership/Borrowing system. It can be stated as:
At any point in the program, for each memory object,there is exactly one live mutable pointer to it or all the live pointers toit are read-only.
Function declarations annotated with the@live attribute are checked for compliance withthe Ownership/Borrowing rules. The checks are run after other semantic processing is complete.The checking does not influence code generation.
Whether a pointer is allocated memory using the GC or some otherstorage allocator is immaterial to OB, they are not distinguished and arehandled identically.
Class references are assumed to be allocated using either the GC or are allocatedon the stack asscope classes, and are not tracked.
If@live functionscall non-@live functions, those called functions are expected to presentan@live compatible interface, although it is not checked.if non-@live functions call@live functions, arguments passed areexpected to follow@live conventions.
It will not detect attempts to dereferencenull pointers or possiblynull pointers. This is unworkable because there is no current methodof annotating a type as a non-null pointer.
The only pointers that are tracked are those declared in the@live functionasthis, function parameters or local variables. Variables from otherfunctions are not tracked, even@live ones, as the analysis of interactionswith other functions dependsentirely on that function signature, not its internals.Parameters that areconst are not tracked.
Each tracked pointer is in one of the following states:
void consume(int* o);// o is owner@liveint* f(int* p)// p is owner{ writeln(*p);// transfer ownership to `consume` consume(p);// p is now undefined//writeln(*p); // errorint* q =newint;// q is owner writeln(*q); p = q;// transfer ownership// q is now undefined//writeln(*q); // error writeln(*p);return p;}
void consume(int* o);// o is ownervoid borrow(scopeint* b);// b is borrowed@livevoid g(scopeint* p)// p is borrowed{//consume(p); // error, p is not owner borrow(p);// lend p to qint* q = p;// q is inferred as scope// <-- using p here would end q's lifetime writeln(*q);// lifetime of q ends before p is used writeln(*p);// OK}
@livevoid h(scopeint* p){// acquire 2 read only pointersconst q = p;const r = q;// <-- borrowing or using p here would end q and r's lifetime// both q and r are live writeln(*q); writeln(*r);// using p ends all its read only pointer lifetimes writeln(*p);//writeln(*q); // error}
The lifetime of a Borrowed or Readonly pointer value starts when it isassigned a value from an Owner or another Borrowed pointer, and ends atthe last read of that value.
This is also known asNon-Lexical Lifetimes.
A pointer changes its state when one of these operations is done to it:
Borrowers are considered Owners if they are initialized from other thana pointer.
@livevoid uhoh(){scope p = malloc();// p is considered an Ownerscopeconst pc = malloc();// pc is not considered an Owner}// dangling pointer pc is not detected on exit
The analysis assumes no exceptions are thrown.
@livevoid leaky(){auto p = malloc(); pitcher();// throws exception, p leaks free(p);}
One solution is to usescope(exit):
@livevoid waterTight(){auto p = malloc();scope(exit) free(p); pitcher();}
or use RAII objects or call onlynothrow functions.
Lazy parameters are not considered.
Conflation of different memory pools:
void* xmalloc(size_t);void xfree(void*);void* ymalloc(size_t);void yfree(void*);auto p = xmalloc(20);yfree(p);// should call xfree() instead
is not detected.
This can be mitigated by using type-specific pools:
U* umalloc();void ufree(U*);V* vmalloc();void vfree(V*);auto p = umalloc();vfree(p);// type mismatch
and perhaps disabling implicit conversions tovoid* in@live functions.
Arguments to variadic functions (such asprintf) are considered to be consumed.
