Unsafe & CompareAndSwap

A Short and Sweet (and Deep) Brain Dump –

About Unsafe and CompareAndSwap (and NonBlockingHashMap).

A reader asked me: where is the volatile-like orderings guaranteed in NBHM?

Jargon:

  1. CAS – Compare-And-Swap instruction (or on IBM Power chips: Load-Linked / Store-Conditional).  The unit of Atomic Update on all modern CPUs, required for any sort of multi-cpu programming.
  2. Unsafe – Java-level access to raw memory.  In old-school speak: ”peek” and “poke”.  (and when I mean “old-school” I mean the talk elite hackers use BEFORE the use of “leet speak” came about; I suppose this means I’m older than dirt…).  This bypasses all the managed runtime safety guarantees, and thus isn’t available to normal Java programs.  You can get it e.g. by hacking the JVM’s boot-class-path.
  3. NBHM – Non-Blocking Hash Map.  A very high performance multi-threaded-safe non-blocking hash map.  See this SourceForge link for the code.  I’ll mention KEY/VAL below to mean any key/value pair in the mapping.

Annoying horizontal lines are meant to give you time to chew&swallow, before moving on to the next byte…


I’m using sun.misc.Unsafe.compareAndSwapObject.
It makes no guarantees about volatile ordering.  That is, the docs are silent.
It’s implementation (at the Java level) is a native call.
Like all native calls, the docs are silent as to the exact semantics.

I’m highlighting the word “docs” here because there are a ton of actual requirements demanded by the Real World.

The typical native call implementation is a CAS instruction on X86/Sparc/Azul/IA64, or a LL/SC on IBM Power.
Sometimes the JIT’s inline the native call to a hardware CAS instruction.
The hardware provides volatile-like semantics for CAS ops on X86/Sparc.
The hardware does NOT provide volatile-like semantics for CAS on Azul or IBM Power.  I don’t know about IA64.
Some JITs on some platforms may inline additional memory fences, and thus provide additional guarantees.

HotSpot, in the C2 server compiler, includes extra fences.
sun.misc.Unsafe, since it has no spec, is free to ignore the volatile-ness of anything and everything.
It is, after all, Unsafe.


java.util.concurrent.Atomic.* uses sun.misc.Unsafe.*.
sun.misc.Unsafe does not make any volatile guarantees.
java.util.concurrent.Atomic.* DOES make volatile guarantees (and uses a volatile variable).
Hence, for a JIT’d inlined version of s.m.U.compareAndSwap to be the proper implementation for any j.u.c.A.CAS call, s.m.U.compareAndSwap needs to include some volatile-smarts.  This happens “for free” on X86 or Sparc, because the X86 hardware CAS op includes volatile-like orderings.  This is definitely not “for free” on an Azul box because our CAS does NOT provide any orderings.


Frequently, I have uses for CAS that do not require orderings and that adding orderings would entail excessive cost.  Several of the CAS ops in NBHM do not require orderings; nor do any of the scalable counters (including the CAT counter).  Hence for these uses the Azul version of s.m.U.* does a plain Azul CAS op with no orderings.  The same could be true for e.g. a IBM Power implementation, or for any hardware for which scaling to lots of CPUs is hard and unneeded fencing would slow things down unnecessarily.

Since Azul’s CAS op (hence our s.m.U.* implementation) does not force orderings, our version of the j.u.c.A.CAS ops includes extra fences to force volatile orderings (both in the native code implementation and the JIT’d inlined code).


So back to the original question about NBHM orderings….
On the PUT (i.e. writer) side:

  • if a KEY is newly inserted I may not end up writing to a volatile, but I will do a CAS.  On X86/Sparc platforms the CAS includes the needed orderings.  On Azul, our simple store-buffers has the same effect… but definitely not a happy situation.  There’s no Java-level guarantee (just a guarantee on X86, or with C2/HotSpot).  Technically a bug on, e.g.,  Power platforms.  Thanks for spotting this.
  • if the KEY already exists, and only the VAL is written – the same arguments apply.  CAS suffices on X86, and Azul’s simple processors suffice.

On the GET side:

  • I explicitly do a volatile-read before every key-compare (even if the keys are pointer-equivalent), and a key-compare is needed to get a “hit”.  Hence there is a volatile-read before any GET call returns anything.

Thus for NBHM, (except for non-HotSpot JVMs on Power) there is a volatile-write before any Put and a volatile-read before any Get.


Cliff