文章>探底分析Java原子类CAS的实现原理—从HotSpot源码到CPU指令cmpxchg>

探底分析Java原子类CAS的实现原理—从HotSpot源码到CPU指令cmpxchg

二进制之路
java
jvm
2月前

在Java的java.util.concurrent.atomic包中,提供了许多原子类。这些原子类,主要都是依赖于底层的CAS机制来实现内部值的原子更新操作。

AtomicInteger源码

以下为JDK 1.8的AtomicInteger部分源码:

public class AtomicInteger extends Number implements java.io.Serializable {

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset; // 值内存偏移量

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;

    public AtomicInteger(int initialValue) {
        value = initialValue;
    }

    public AtomicInteger() {
    }

    /**
     * 如果当前对象的value值与expect相等,则原子的将变量value的值设置为update
     */
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

AtomicInteger的内部值保存在变量value中,valueOffset表示value字段在对象中的内存偏移量,compareAndSet()方法用于原子的比较并更新value的值。

对于compareAndSet()方法,只是简单的调用了Unsafe的compareAndSwapInt()方法,该方法通过value字段的内存偏移量valueOffset来对字段进行操作。

Unsafe源码

sun.misc.Unsafe类的compareAndSwapInt()方法声明如下:

    /**
     * 原子的将对象o在offset偏移量的值替换为x,前提条件是其旧值与expected相等
     */
    public final native boolean compareAndSwapInt(Object o, long offset,
                                                  int expected,
                                                  int x);

Unsafe类的compareAndSwapInt是一个native方法,具体的实现在hotspot源代码的/src/share/vm/prims/unsafe.cpp文件中。

unsafe.cpp源码

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

实现逻辑在第2至4行,其中第2、3行主要是根据字段的偏移量计算出字段的地址。

关键是第4行代码,主要是调用了Atomic::cmpxchg方法,实现字段值的比较交换操作(CAS)。

linux_x86的cmpxchg方法

对于linux_x86平台,cmpxchg对应的源代码在:hotspot\src\os_cpu\linux_x86\vm\atomic_linux_x86.inline.hpp。

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;
}

第一行用于判断是否有多个处理器,如果是则mp为1,否则mp为0。

__asm__

表示后面的括号内为汇编指令,由4部分组成。

括号内的各部分以英文冒号:分隔,主要关注前3部分,分别表示汇编指令、输出参数列表和输入参数列表。

按照输出和输入参数列表的顺序,汇编指令中对它们的引用依次编号如下(汇编指令中的编号和输入输出参数的对照关系):

%0"=a" (exchange_value) // 第1个输出参数。cmpxchgl指令执行结束后,将寄存器eax的值保存到exchange_value,在方法执行结束后返回
%1"r" (exchange_value) //  第1个输入参数。编译器会选择任意一个可用的寄存器来存储exchange_value,例如使用寄存器ecx。
%2"a" (compare_value) // 第2个输入参数。使用寄存器eax来存储待比较的值compare_value,执行cmpxchgl指令时会用到寄存器eax。
%3"r" (dest) // 第3个输入参数。编译器会选择任意一个可用的寄存器来存储目标地址dest,例如使用寄存器edx。
%4"r" (mp) //  第4个输入参数。编译器会选择任意一个可用的寄存器来存储多处理器标志

其中,约束符a表示寄存器eax。约束符r代表寄存器(register),编译器会选择任意一个可用的寄存器来使用。对于每一个参数的说明,见上面的注释。

%1和%3引用的操作数,前面都有一个约束符r,即编译器可以选择任意一个可用的寄存器来操作数据。
假设分别使用了寄存器ecx和edx,则cmpxchgl指令替换后如下:

cmpxchgl %%ecx,(%%edx)

(了解上面的汇编语法可参考:x86内联汇编

cmpxchgl指令说明

cmpxchgl指令的作用:
比较寄存器eax和目标操作数edx对应的内存单元的值是否相等。
如果相等,则将寄存器ecx的值保存到操作数edx对应的内存单元中,替换掉旧值。
如果不相等,则将edx对应内存单元的值加载到寄存器eax中。

在cmpxchg()方法的最后,会将exchange_value作为方法的返回结果。实际上,在cmpxchgl指令执行结束后,exchange_value会被更新为寄存器eax对应的值。

因此,cmpxchg()方法返回的可能是原来传入的compare_value,也可能是目标地址dest对应的内存单元的值,这取决于cmpxchgl指令是否成功的更新了目标地址的值。

(cmpxchg指令参考:Intel x86比较交换指令cmpxchg的作用与原理

在cmpxchgl指令的前面,还使用了一个宏定义LOCK_IF_MP。

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

LOCK_IF_MP宏带有一个参数mp,定义了一段汇编代码。

将宏代码格式化,并将cmpxchgl的代码合并进来完整的看一下:

cmp $0, " #mp "
je 1f
lock 
1: cmpxchgl %%ecx,(%%edx)

这段代码,就是整个cmpxchg()方法的核心逻辑。

首先,使用cmp指令比较入参mp的值是否为0。

然后,使用je指令根据比较的结果进行跳转。

如果cmp比较结果相等,则跳到1的位置继续执行,即执行cmpxchgl指令。

如果cmp比较结果不相等,则简单的往后执行。即先执行lock指令,再执行cmpxchgl指令。

显然,当mp的值为1时(多处理器),cmp的结果为不相等,此时会执行多一条lock前缀指令。

lock前缀

通过《Intel® 64 and IA-32 architectures software developers manual combined volumes 3A, 3B, 3C, and 3D System programming guide》第8章(8.1)可以了解到:

使用LOCK#信号可以锁定总线。

而使用lock前缀指令,可以用来声言LOCK#信号。也就是说,在指令中添加前缀lock,能够实现触发LOCK#信号。

对于Intel486和Pentium处理器,始终会在LOCK锁操作期间在总线上声言LOCK#信号,即使正在锁定的内存区域已缓存在处理器中。

而对于P6及之后的处理器,如果LOCK锁操作正在锁定的内存区域,已经缓存在处理器中,则不会声言LOCK#信号。
相反,它会锁定这块内存区域的缓存,并回写到内存中。同时,使用缓存一致性机制来确保修改操作的原子性。这被称为缓存锁定。

缓存一致性机制,会自动阻止"已缓存同一内存区域的两个或多个处理器同时修改该区域中的数据"。

windows_x86的cmpxchg方法

对于windows_x86平台,cmpxchg对应的源代码在:hotspot\src\os_cpu\windows_x86\vm\atomic_windows_x86.inline.hpp。

// Adding a lock prefix to an instruction on MP machine
// VC++ doesn't like the lock prefix to be on a single line
// so we can't insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:

inline jint     Atomic::cmpxchg    (jint     exchange_value, volatile jint*     dest, jint     compare_value) {
  // alternative for InterlockedCompareExchange
  int mp = os::is_MP();
  __asm {
    mov edx, dest
    mov ecx, exchange_value
    mov eax, compare_value
    LOCK_IF_MP(mp)
    cmpxchg dword ptr [edx], ecx
  }
}

将LOCK_IF_MP宏代码和方法的汇编代码合并到一起,整体代码如下:

    mov edx, dest			// 目标地址保存到寄存器edx
    mov ecx, exchange_value	// 新值保存到寄存器ecx
    mov eax, compare_value	// 待比较的值保存到寄存器eax
    cmp mp, 0				// 使用cmp指令比较入参mp的值是否为0
    je L0					// 如果mp的值为0,表示为单处理器,则直接跳到L0的位置执行cmpxchg指令
    _emit 0xF0				// 如果mp的值不为0,表示为多处理器,则执行lock前缀指令。_emit 0xF0会转化为lock前缀指令。
    L0:
    cmpxchg dword ptr [edx], ecx  // 执行CPU的cmpxchg指令

可以看到,windows_x86和linux_x86对于cmpxchg方法的实现原理是相同的。只不过于由于不同平台,不同的汇编语法,在代码的写法上存在一些差异而已。

小结

Java中的原子类,主要是依赖于CAS机制来实现原子的更新操作。

Java库中的CAS相关方法,都是由sun.misc.Unsafe类来提供。

Unsafe类中定义的方法,实际上都是基于native实现的。

Unsafe类本地方法具体的实现,在hotspot源代码的/src/share/vm/prims/unsafe.cpp文件中。

CAS在底层的实现,最终调用的是Atomic::cmpxchg方法。

在不同的操作系统平台上,HotSpot虚拟机为Atomic::cmpxchg方法提供了不同的实现,但原理是相同的。

因此,对于Java的CAS机制,实际上是通过调用处理器的cmpxchg指令来实现的。

但是,当在多处理器上执行cmpxchg指令时,将会在该指令的前面添加一条lock前缀指令。因为cmpxchg指令本身并不是一个原子操作,因此需要通过lock前缀指令加锁来让指令实现原子操作。

通过 Intel x86比较交换指令cmpxchg的作用与原理 这篇文章可以了解到,cmpxchg指令包含了几个操作。
为了确保在多处理器上指令的原子性,如果服务器有多个处理器,就需要通过添加lock前缀来实现cmpxchg指令的原子执行。

如果想更好的理解上面的汇编代码,可以先看看以下几篇文章,再回过头来看就容易多了:

x86汇编指南之寄存器与内存寻址模式

GCC汇编语法与Intel汇编语法的几个差异点

x86内联汇编

Intel x86比较交换指令cmpxchg的作用与原理

参考

Intel文档:https://software.intel.com/content/www/us/en/develop/articles/intel-sdm.html

Conditionals: Goto and Branch Instructionshttps://www.cs.uaf.edu/2015/fall/cs301/lecture/09_11_loops.html

Loops and Branches in Assemblyhttps://www.cs.uaf.edu/2012/fall/cs301/lecture/09_12_jmp.html


公众号:二进制之路

博客:binarylife.icu

1513 阅读
请先登录,再评论

评论列表

我也以为是一条指令呢,谢谢,学习到了

https://a.perfma.net/img/2382850
LGY源2月前

很详细,cmpxchg,赞

gesgood2月前

原以为 CAS是对应一条原子的机器指令,不知道还有这么些细节~ 赞一个

ACS是多线程减少锁对资源的耗时影响,减少内核态多用户态的切换,有利于多线程间减少竞争。值得学习

苏科2月前

赞一个

https://a.perfma.net/img/2382850
2月前

cmpxchg

https://a.perfma.net/img/2382850
Daniel172月前

学习👍🏻