Ownership

Before writing this entry I searched for the word ownership in this blog. It appears twice. Once I mention briefly that I do not agree with individual code ownership. The other occurrence is in an entry that presents the relation between smart pointers and cloning objects. Smart pointers are said to own objects. The objects are deallocated from the heap when they have no owner. Of course, this is all in the C++ land where there is no garbage collection (GC), only deterministic deallocation. Today I'll talk about Java though. So, why would I care about ownership in a language that has GC? The notion of ownership I'm going to talk about is different and it is used to limit aliasing (different names in the program can refer to the same object).

Imagine the heap as a graph of objects with two types of edges. The `line' edge from x to y means that x has a reference to y. This means that, at the current point of execution, either a member field of x points to y or a local variable of a method of object x points to y. The `dashed' edge from z to x means that z owns object x. What exactly `owns' means varies from an author to another but in general it is some form of restriction on the legal reference edges. The following specific meanings are identified by Boyapati.

• Object encapsulation: When z != y, if z owns transitively y but not x, then x does not refer to y.
• Owners as dominators: There is a special root object r such that if x owns y then all reference-paths from r to y go thru x.
• Owners naming: Object x can refer to y only if it can name y's owner.

The above is true for all x, y, and z. The node r is fixed for a given program. It is a dummy node that refers to all the local (object) variables of main and to all static objects. The owners naming property implies that an object can have at most one owner.

What is the difference between object encapsulation and owners as dominators? The former does not refer to a root and hence we have reasons to believe it is stronger. Can we build a heap for which owners are dominators but objects are not encapsulated? Yes, we can. Imagine an application that uses a linked list to store some data. According to the ownership as dominators rule data can refer to the nodes, but not according to object encapsulation. In order to get a better feeling of what the rules say you might find it useful to stop a moment to figure out why. Another exercise that gives a little more insight is to explore what happens if the ownership edge from root to list is removed.

So we saw a clear example where the two properties are different. My question is, and this is not an exercise, can we give a precise description of the relation between the two properties? In other words, what are the necessary conditions such that owners as dominators implies object encapsulation?

While the program is running the heap changes: objects are allocated and deallocated, ownership relations appear and disappear, and references appear and disappear. If we know that one of the above properties holds then we have a restriction on the possible heaps and therefore on the possible modifications of the heap. The advantage of the extra structure is that the legal programs are easier to reason about. One application of ownership is to ensure that a locking discipline is obeyed. Imagine that you use a tree data structure, say TreeSet, to represent a set in a multithreaded program. Because the internals of the TreeSet object are not visible (they are encapsulated) it can act as the lock object for its internals. In other words you can use the root of an ownership tree as a lock for every object inside that ownership domain. This is an informal and inexact statement that tries to convey the intuition behind what has been done. The existing solution, that of Boyapati and Rinard, ensures that there are no data races in a well typed program by ensuring (only) the owners naming property. The type system also precludes changes in the ownership apart from those that accompany allocating objects.

Of course, ownership can also be enforced at run-time. Such an approach allows changing the ownership relation while the program is running. A mix of static and run-time checks comes with the Universes type system.

In the next episode we will see that a more flexible approach to study aliasing is separation logic. It was designed to be used in reasoning about low-level imperative programs that have a heap. Basically they took Hoare's language, added a heap, and the means to express concisely statements about it.