(DRAFT DRAFT DRAFT)

Summary

Java's synchronization mechanism requires that there is a monitor in the header of every object on the heap (including Java arrays). The monitor is used by only a small fraction of all objects. The semantics, as fixed by the JVMS and JLS, are too inflexible for some use cases, and for many others the extra header word is just wasted space. For still other use cases, the monitor is too weak, since the JMM allows racing memory accesses to defeat synchronization.

We propose to make more flexible use of the per-object monitor and, in a class-specific way, allow it to be either expanded or eliminated, to support a wider range of use cases. In particular, we will support the use cases of single-thread confinement, permanent immutability, and episodic immutability, by providing a "hook" to exclude racing accesses to appropriately configured objects.

Description

An object which is under synchronization is owned by a thread, but its public non-final fields (and, if an array, its elements) are still subject to racing writes.

Likewise, if an object is serving as a handle to off-heap memory resources (like a DirectByteBuffer), it may prevent racing access to itself by ensuring single-threaded access, but it cannot prevent racing accesses to its off-heap storage without unusual measures such as locking a monitor on every access, measures which are often rejected as too expensive. The possibility of racing accesses to deallocated memory prevents us from creating a safe API for deallocating off-heap memory resources, which is a serious and recurrent problem for many customers working with memory intensive applications.

We need a new kind of locking, with the following characteristics:

• Mutable variables, both fields and array elements, can be declared as lockable. (They can be viewed as more structured volatiles.)
• Racing accesses to lockable variables in a locked object throw an error.
• At least some arrays (of each element type) will have lockable elements. Given that all array accesses must perform range checks, it seems reasonable to endow all of them with lockability.
• An object (or array) can be locked as frozen, treating all write access as racing, but treating read access as never racing.
• An object (or array) can be locked to an owner thread, treating all access (read or write) as a race, except within the owner thread.
• An object (or array) can be locked to an owner terminal, a non-thread object of a special class, treating all access (read or write) as a race.
• There is a safe, atomic handoff API for transferring a locked object from one owner (thread or terminal) to another, or to the frozen state, or to the unlocked state.
• The handoff API ensures linear chain of custody for any object with lockable variables.
• A lockable field in the unlocked state can be read or written at any time, but races relative to other field states are excluded by a micro-lock (such as a seq-lock). (Thus, a lockable field is more efficient in the locked state than the unlocked state.)
• Lockable fields of value types which are (a) declared non-tearable, and (b) too big to fit into an atomically updateable memory unit will thus fulfill their atomicity contract.
• Non-lockable fields of such value types will either be forbidden, or else be processed using additional lock states on the containing object.
• Objects with lockable fields will be constructable as usual with constructors; in the body of the constructor the object will be locked to the current thread, but as the constructor returns normally the object will be placed some specified selected state, such as frozen, locked to a given terminal, or locked to some thread. The object class itself will have control over which such states are available to clients.

Contention for a variable can be handled in two ways: Blocking or throwing. The existing Java sychronization supports blocking, which means that contention must be resolved actively among the current owner and a pool of waiting threads, and this must be done at every release of a lock. This makes both lock acquisition and lock release very expensive to implement, requiring inter-processor communication (via fenced or volatile memory accesses).

Throwing, on the other hand, immediately eliminates contending threads. It forces the programmer to think about the top-level contention structure of the program, and deploy a smaller number of explicitly coded blocking monitors to manage the exclusion needs of all the objects in the program.

When managing contention with throwing, the monitor-enter operation simply consists of verifying that the object header has an expected bit pattern, corresponding to the current thread. (If the object is not frozen, a read access must check for that bit pattern also.) There is nothing to do for monitor-exit (1+0).

Since the object header cannot change from a valid state to an invalid state without the current thread making the change, the lock check can easily be commoned up and hoisted out of loops, just like null checks or range checks.

(This property of hoistability is a very strong one, allowing cheap but safe data access, but also strongly constraining the allowable lock state transitions. It seems likely that once an object is made immutable its lock state can never change again.)

Hoistable lock checking is cheap enough to justify creating the new class of lockable fields, for which every access is preceded by a throwing contention check. Of course, some users will still prefer "naked" mutable fields, but the requirement to perform defensive copy of racy objects will in some cases turn out to be more burdensome than allowing the JVM to exclude races by managing field locks.

Biased locking recalled: At one point it seemed to many that the technique of biased locking could render Java synchronization cheap enough to use freely. What we learned from that adventure was that objects which are stably "owned" by one thread can indeed be easily verified by all parties to be in that state. We also learned that lock revocation can be so expensive as to make the whole scheme impractical. Lock revocation must occur when an object X is biased to a thread T1 that no longer cares about it, and another thread T2 is trying to get access. To grant the lock to T2, T1 must be interrupted and brought to a provably safe state relative to X. This in general requires walking the stack of T1 to discover any lingering references to X that might logically be synchronized to T1. The problem here is not with biased ownership, but with the user model in which the hand-off from T1 to T2 is implicit, and can occur between any two episodes of synchronization by T1. The new form of object locking fixes the problems with biased locking while retaining the benefits.

Field locking interoperates with classic Java synchronization. When a new thread enters the monitor of an object (monitor-enter), it requests a handoff from old owner of the object. When the old owner grants the request, the new thread becomes the object's owner, and all lockable fields are exclusively available to the new thread. When the monitor is exited (monitor-exit) the ownership is handed back to the old owner (if it was a terminal) or perhaps some other state determined by the object's class. During the critical section, the owning thread can (and should) nominate the successor lock state for the locked object. This state is chosen from:

• another terminal
• another specific thread
• a waiting thread selected by the JVM
• the previous terminal or thread (if any)
• the unlocked state
• the frozen state

With respect to lock states, the monitor-exit operation is similar to a return from a constructor. In both cases, there is a controlled handoff from the current thread (which is either constructing a new object or modifying an old one) to the next owner.

A standard terminal will be supplied which has no specific properties but will grant access to any thread. Locking an object to this terminal has the effect of temporarily disabling all reads or writes, until a thread picks up the object and does something else with it.