Java CAS底层实现详解

Posted by phantomVK on February 8, 2018

前言

这篇文章将深入介绍CASJDK具体的实现方式,填补Java源码系列(7) – AtomicInteger中相关内容的空缺,主要从高层调用开始,经历JDK、JNI和asm汇编,最终调用处理器CAS指令集,带你浏览整个实现过程。

阅读需扎实Java基本功,了解或能看懂JNI和C语言。汇编没看过也没有关系,文章参考链接附带本文涉及所有汇编知识点以供查阅。

一、什么是CAS

多线程不可避免带来了更多的元素同步处理。要在多线程环境中构成同步原语(如信号量和互斥),我们经常会提到被称为比较和交换 (CAS) 的原子操作。

CAS的伪代码:

compare_and_swap (*p, oldval, newval):
      if (*p == oldval)
          *p = newval;
          success;
      else
         fail;

首先比较内存位置 p (*p) 的内容与已知值 oldval(这应该是当前线程中 *p 的值)。只有当它们是相同值时,才会将 newval 写入 *p。若其他线程之前已经修改该内存位置,那么比较操作会失败。

参考自内联汇编 - 从头开始,有删改

二、Unsafe

JDK8该方法名为compareAndSwapInt,在Unsafe类中:

public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

JDK9命名为compareAndSetInt,也在Unsafe类中:

public final native boolean compareAndSetInt(Object var1, long var2, int var4, int var5);

本文用JDK9来介绍。进入正题,首先看该方法的原生实现,对应unsafe.cpp文件的1198行,文件路径jdk9/hotspot/src/share/vm/prims/

下面unsafe.cpp尾段有个保存方法对应关系的静态数组:

static JNINativeMethod jdk_internal_misc_Unsafe_methods[] = {
    ......
    
    {CC "compareAndSetInt",   CC "(" OBJ "J""I""I"")Z",  FN_PTR(Unsafe_CompareAndSetInt)},
    {CC "compareAndSetLong",  CC "(" OBJ "J""J""J"")Z",  FN_PTR(Unsafe_CompareAndSetLong)},
    {CC "compareAndExchangeObject", CC "(" OBJ "J" OBJ "" OBJ ")" OBJ, FN_PTR(Unsafe_CompareAndExchangeObject)},
    {CC "compareAndExchangeInt",  CC "(" OBJ "J""I""I"")I", FN_PTR(Unsafe_CompareAndExchangeInt)},
    {CC "compareAndExchangeLong", CC "(" OBJ "J""J""J"")J", FN_PTR(Unsafe_CompareAndExchangeLong)},
    ......
}

从查找对应关系知道compareAndSetIntUnsafe_CompareAndSetInt,位于相同文件1031行:

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSetInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x)) {
  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

逻辑执行流程:

  • objAtomicInteger对象,通过 JNIHandles::resolve() 获取obj在内存中OOP实例p;
  • 根据value的内存偏移值offset去内存中取指针addr;
  • 获得更新值x、指针addr、期待值e三个参数后,调用Atomic::cmpxchg(x, addr, e);
  • 通过Atomic::cmpxchg(x, addr, e)实现CAS

三、CAS本体

3.1 Atomic::cmpxchg

jdk9/hotspot/src/os_cpu/linux_x86/vm/atomic_linux_x86第100行,并调用asm汇编。

注意:形参order是JDK9中新加的,JDK8u没有该形参

inline jint Atomic::cmpxchg(jint exchange_value,
                            volatile jint* dest,
                            jint compare_value,
                            cmpxchg_memory_order order) {
  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;
}

按顺序就是%1%4,exchange_value是%1,dest是%3r代表任意一个寄存器,a代表eax寄存器。

: “r” (exchange_value), “a” (compare_value), “r” (dest), “r” (mp)

经过初步了解,cmpxchgl就容易理解多了:

cmpxchgl %1,(%3)

奇怪的是%2没有用上,需要查证cmpxchgl的用法,它用到了一个隐含的操作数,即eax。在前面的输入操作数中,对应的%2没有在汇编模板里出现,但通过修饰符a把它存放到了eax寄存器,因此这里被cmpxchg指令隐含使用。

指令cmpxchg比较eax(也就是compare_value)与dest的值。如果相等,那么将exchange_value的值赋值给dest;否则,将dest的值赋值给eax。

: “=a” (exchange_value)

3.2 os::is_MP

方法is_MP()实现在jdk9/hotspot/src/share/vm/runtime/os.hpp206行:

int mp = os::is_MP();

用于获取当前系统处理器核心数,如果_processor_count在引导过程尚未初始化,就默认假设其是多处理器以保证线程安全。

static int _processor_count;                // number of processors
static int _initial_active_processor_count; // number of active processors during initialization.

// Interface for detecting multiprocessor system
static inline bool is_MP() {
  // During bootstrap if _processor_count is not yet initialized
  // we claim to be MP as that is safest. If any platform has a
  // stub generator that might be triggered in this phase and for
  // which being declared MP when in fact not, is a problem - then
  // the bootstrap routine for the stub generator needs to check
  // the processor count directly and leave the bootstrap routine
  // in place until called after initialization has ocurred.
  return (_processor_count != 1) || AssumeMP;
}

3.3 LOCK_IF_MP(mp)

获取成功后把核心数保存在整形值mp中,实际起到布尔值的作用。为0意味系统是单处理器系统,大于0是多处理器系统,并作为实参调起宏定义LOCK_IF_MP(mp)

// Adding a lock prefix to an instruction on MP machine
#define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "

宏定义用"cmp $0, " #mp "检查核心是否为单核:

  • 是:跳到1f,执行CPU指令cmpxchgl %1,(%3)1f的意思是1after,参看参考链接-6;
  • 不是:则跳到1f前先通过lock给总线上锁,令物理处理器的其他核心不能通过总线访存,保证指令操作的原子性。

值得一提的是,如果我们对一个变量使用volatile修饰符,汇编中也会增加lock指令前缀以保证该变量线程可见性和指令执行有序性。

3.4 __asm__ volatile (“”: : :”memory”)

还有一个结构:

__asm__ volatile ("": : :"memory")

此结构告诉编译器添加一个内存屏障禁止相关区域内的操作指令重排序,但如何执行还会受到具体处理器的影响。详见参考链接-3

Creates a compiler level memory barrier forcing optimizer to not re-order memory accesses across the barrier.

3.5 伪代码

说了这么多还是不易理解,毕竟上述代码是C语言混编asm,翻译为Java-like伪代码:

// @param _processor_count processor count
// @param assumeMP         assume is multiprocessor when is not yet initialized
// @param compare_value    be comparing
// @param dest             set as new value if true
@AsmVolatileMemory
private void isMultiProcessCAS(int _processor_count,
                               boolean assumeMP,
                               int compare_value,
                               int dest) {              
    if (_processor_count != 1 || assumeMP) {
        lock();
    }
    cmpxchgl(compare_value, dest);
    // Should unlock after cmpxchgl(int, int)???
}

有人提议参考链接-12os::is_MP()AssumeMP改为true提升性能。且在2017-10-03的JDK10b13实现了该提议,所以上述伪代码可以进一步演进为:

// @param _processor_count processor count
// @param compare_value    be comparing
// @param dest             set as new value if true
@AsmVolatileMemory
private void isMultiProcessCAS(int _processor_count,
                               int compare_value,
                               int dest) {
    if (_processor_count != 1) {
        lock();
    }
    cmpxchgl(compare_value, dest);
    // Should unlock after cmpxchgl(int, int)???
}

到这里Java CAS底层实现全部讲解完毕。如果还有疑问,下面参考链接应该能给你所有需要的解答。

四、参考链接

1. Java CAS 原理剖析 - 卡巴拉的树 - 掘金

2. Assembly language je jump function - Stackoverflow

3. Working of asm volatile (“” : : : “memory”) - Stackoverflow

4. JNI: converting unsigned int to jint - Stackoverflow

5. CMPXCHG - Compare and Exchange

6. 1b and 1f in GNU assembly - Stackoverflow

7. cmp je/jg how they work in assembly - Stackoverflow

8. Intel x86 JUMP quick reference

9. 朴素linux: 内联汇编 - Github

10. 内联汇编 - 从头开始 - IBM

11. 什么是桩代码(Stub)- 知乎

12. JDK-8185062 : Set AssumeMP to true and deprecate the flag

13. Is x86 CMPXCHG atomic? - Stackoverflow