What Is CAS (Compare and Swap) in Java?

The previous article, What on Earth Is the AQS Everyone Keeps Talking About?, mentioned spin CAS and volatile. Today we’ll discuss CAS, and next time volatile.

CAS (compare and swap) literally means compare and swap. It’s usually combined with spinning and volatile. This article covers CAS; a later one digs into volatile.

Why Compare Before Swap

The classic variable operation is increment: turning 1 into 2. Single-threaded, no problem. But the moment two threads operate on the same variable, trouble appears — that’s related to Java’s memory model, JMM, which I’ll cover in the next article on volatile. If thread A already changed the variable to 2 while thread B increments at the same time without seeing that change and also sets it to 2, two increments should give 3 but give 2 instead. That’s what brings CAS in.

You might think adding volatile guarantees visibility of the change, but volatile can’t guarantee atomicity. Next article.

If we compare before swapping with CAS, the problem above goes away. When thread B increments, it carries the old value 1 and the new value 2 and asks to replace the variable with the new value. Because thread A already changed it to 2, the old value doesn’t match on comparison, so the write fails. That’s an optimistic lock, really — let’s take the classic atomic integer as an example.

Optimistic Locking

While we’re here, a word on optimistic vs pessimistic locking. These aren’t specific locks but ways of thinking, usable beyond Java programming — SQL updates too.

• Optimistic locking is optimistic: it assumes conflict is unlikely, so it’s not exclusive and lets others modify alongside; it just checks before writing whether someone else already changed it.

• Pessimistic locking is pessimistic: it assumes conflict is certain, so it’s exclusive — take a lock that forbids others from modifying, and release it only after you’re done.

Atomic Operations

The classic case is AtomicInteger.getAndIncrement. First the code:

public final int getAndIncrement() {
    return unsafe.getAndAddInt(this, valueOffset, 1);
}

One line, calling into Unsafe. Let’s set that aside and keep reading:

public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        var5 = this.getIntVolatile(var1, var2);
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    return var5;
}

I forgot to explain valueOffset. Where does it come from? valueOffset = unsafe.objectFieldOffset — a native method, not the focus here. It gets the object’s memory address offset; it’s fine if that doesn’t click yet, just think of it as a memory address.

It spins via while. getIntVolatile is also native and fetches the latest value. The key part is compareAndSwapInt, another native method — to read its code you’d have to go into the C++ side; everyone can look up the HotSpot JVM source themselves. I’ll only paste the key part of unsafe.cpp:

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

Can’t read it? No worries, we can guess. It calls Atomic::cmpxchg, so let’s go take a look at that too:

inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

Still unreadable — but we can look up how the experts explain it. LOCK_IF_MP is a macro definition; let’s not dig into it. The instruction it finally assembles to is lock cmpxchgl, and that’s assembly already. Digging further would mean looking at the CPU, which is too far afield. Back to the point.

From that exploration we know AtomicInteger’s operations rely on CAS, CAS is implemented by the Unsafe class, Unsafe relies on the JVM’s C++ code, and that C++ uses assembly to make the CPU do the work, ensuring atomicity and safety.

The Unsafe Class

Plenty of expert code trails eventually lead into Unsafe. Does the name mean it’s unsafe?

When we write Java, the JVM stands between us and real memory, operating it on our behalf, with GC reclaiming memory — so Java is a safe language.

Unsafe is the unsafe part: it can operate memory directly. Allocate memory: allocateMemory; expand memory: reallocateMemory; free memory: freeMemory; set values in a given memory block: setMemory; load a class without security checks: defineClass; atomically update a value at an object’s given offset address: compareAndSwapObject; read system load: getLoadAverage, and so on. Very dangerous indeed.

Can we use something this dangerous directly? Let me keep you in suspense — first the normal usage, Unsafe unsafe = Unsafe.getUnsafe():

public static Unsafe getUnsafe() {
    Class var0 = Reflection.getCallerClass();
    if (!VM.isSystemDomainLoader(var0.getClassLoader())) {
        throw new SecurityException("Unsafe");
    } else {
        return theUnsafe;
    }
}

It checks VM.isSystemDomainLoader(var0.getClassLoader()), which really asks whether the class loader is null, throwing an exception if not. When is it null? Only classes loaded by the BootstrapClassLoader have a null loader, so normally we’re forbidden from using Unsafe for these unsafe operations directly. But what about abnormal cases?

Reflection to the rescue! We can bypass getUnsafe entirely through reflection:

Class klass = Unsafe.class;
Field field = klass.getDeclaredField("theUnsafe");
field.setAccessible(true);
Unsafe unsafe = (Unsafe) field.get(null);
System.out.println(unsafe.toString());

Using Unsafe isn’t the point of this article, so I’ll skim it. My take: Unsafe is a “back door” SUN left behind, letting Java touch memory for unsafe memory operations.

Spinning

I mentioned spinning earlier, and it’s very common too. When we update a variable concurrently, we may lose the race and need to keep retrying.

Then why not use thread sleep/wake to yield the CPU instead of burning cycles spinning?

CPUs are extremely fast, so our code runs extremely fast; the thread holding the resource may finish and release it in an instant. Adding thread state transitions on top would be wasteful — better to wait a moment. Spinning can beat a thread state switch, so spinning earns its place.

Is spinning perfect? Far from it — I’ll cover spinning’s drawbacks in the next article on volatile.

The ABA Problem

CAS looks flawless, but there’s still ABA. Suppose thread 1 changes a variable from A to B and then back to A. When thread 2 comes to modify with CAS, both the old value and the current value are A, so it concludes nobody touched it — but thread 1 actually did. That’s ABA.

The fix is essentially adding a version number, like AtomicStampedReference, which bumps the version on every modification. ABA solved.