HICSC
007 番外:JVM CAS机制的实现原理

这篇文章原本是放在信号量相关的文章中,但考虑到这部分内容与进程管理关系不大,且属于源码分析类文章,最终还是把它抽出来单独成文。由于是源码类文章,在内容上可能有些松散,建议边读文章边去源码里面翻翻,不管能不能读懂,总会有所收获。关于汇编的那部分内容,我在阅读整理时,花了很多心血,肯定对你有所帮助的。废话不多说了,下面进入正题。

CAS即比较并设置,它将当前的值与内存中的实际值比较,如果相等,才将内存修改为新的值,如果这期间有其它线程修改了这个值,那么CAS失败。比如,要修改变量A的值,先读取到A=1,等到真正修改的时候,需要先判断A在内存中的值还是不是1,如果是,则可以修改A的值,如果不是,则需要重新获取A的值,再去修改,如此反复,直到修改成功。

弄清楚CAS的基本概念后,从JDK的源码开始。

// java.util.concurrent.locks.AbstractQueuedSynchronizer
protected final boolean compareAndSetState(int expect, int update) {
    // See below for intrinsics setup to support this
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

JDK中的compareAndSetState方法调用的是unsafe.compareAndSwapInt方法,它是一个native方法,得去JVM源码中查看实现方式:

UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapObject(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jobject e_h, jobject x_h))
  UnsafeWrapper("Unsafe_CompareAndSwapObject");
  // 更新后的值 
  oop x = JNIHandles::resolve(x_h);
  // 内存期望值
  oop e = JNIHandles::resolve(e_h);
  // 要改变的对象
  oop p = JNIHandles::resolve(obj);
  // 获取要更新的对象偏移地址
  HeapWord* addr = (HeapWord *)index_oop_from_field_offset_long(p, offset);
    // 垃圾回收相关,暂不讨论
  if (UseCompressedOops) {
    update_barrier_set_pre((narrowOop*)addr, e);
  } else {
    update_barrier_set_pre((oop*)addr, e);
  }
  // 执行CAS操作
  oop res = oopDesc::atomic_compare_exchange_oop(x, addr, e);
  jboolean success  = (res == e);
  if (success)
    update_barrier_set((void*)addr, x);
  return success;
UNSAFE_END

再继续看oopDesc::atomic_compare_exchange_oop的源码:

inline oop oopDesc::atomic_compare_exchange_oop(oop exchange_value,
                                                volatile HeapWord *dest,
                                                oop compare_value) {
    // 如果开启了压缩普通对象指针的话,需要对值做相应的处理
   // 把数据存入内存时,先压缩,取数据后,再解压,以达到节约内存的目的
   // 所以在cas时,也需要先压缩后再与内存中的值比较,而返回时则需要解压缩
  if (UseCompressedOops) {
    // encode exchange and compare value from oop to T
    narrowOop val = encode_heap_oop(exchange_value);
    narrowOop cmp = encode_heap_oop(compare_value);
      // 执行CAS操作    
    narrowOop old = (narrowOop) Atomic::cmpxchg(val, (narrowOop*)dest, cmp);
    // decode old from T to oop
    return decode_heap_oop(old);
  } else {
    return (oop)Atomic::cmpxchg_ptr(exchange_value, (oop*)dest, compare_value);
  }
}

再往下就是Atomic::cmpxchg函数,通过函数名可以看出,其功能大致是调用汇编指令:cmpxchg来完成比较与设值,这个方法实现了不同类型数据的比较设值,且不同的平台,其调用汇编指令的方式也不一样,所以,这里我们抛开许多细枝末节的代码,直接看最简单的,即在Linux x86平台下CompareAndSetInt的实现,即实现整型数据的比较与设值。

//openjdk-jdk8u源码:/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();
  // LOCK_IF_MP是宏定义
  // #define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "
  __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;
}

这段在C++中内联了汇编的代码阅读起来有点困难,所以,接下来我会花一点时间解读这段代码。在此之前,可以考虑为什么要在C中直接执行汇编指令?汇编作为最底层的低级语言,其指令只要还原成二进制就可以直接被CPU执行,因此,想要保证对数据的原子操作,最好的方法就是直接操作CPU。也是基于此,几乎所有的语言底层实现原子操作时,都是直接使用汇编指令。而C/C++内联汇编的特性架起了这样一座桥梁:一边是C语言,一边是汇编语言,在汇编中可以接收C传过来的参数,并且汇编指令也可以把值写入C语言变量中。内联汇编是一个非常重要且有用的特性,值得我们花点时间研究。

内嵌汇编

在C/C++中内嵌汇编都是使用如下格式:

// 内嵌汇编模板
// 第1行:汇编语句
asm ( assembler template
     // 第2行:输出参数,以','分割
      : output operands               (optional)
     // 第3行:输入参数,以','分割
      : input operands                (optional)
        // 被使用的寄存器列表
     // 用来告诉GCC等编译器,这些寄存器已经被asm使用,暂时不要在asm程序外使用它们,否则可能代码未知的后果
     // 这里的寄存器都是执行指令需要用到的寄存器,而输入输出用到的寄存器不需要放入其中
      : list of clobbered registers   
        (optional)   
);

对照下面的源码,关键字asm__asm__用于说明随后的字符串是内联汇编代码块。volatile__volatile__ 是可选的,可以将它们添加到 asm 后面,禁止某些编译器的优化。其实,asm__asm__几乎是相同的,惟一的区别是,当预处理程序宏中使用内联汇编时,asm在编译过程中可能会引发警告,volatile也是同样的道理。因此Atomic::cmpxchg函数中汇编指令部分源码可以作如下解读:

// 宏定义表达的意思,后面再说
// 第1行:表示汇编指令 cmpxchgl
__asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
        // 输出参数,"=a"表示把数据保存到eax寄存器中,"="表示这类操作数是只写的
      // 这里的意思就是把 exchange_value的值保存到CPU的eax寄存器当中
      : "=a" (exchange_value)
      // 输入参数:"r"表示任意寄存器,"a"表示eax寄存器
      : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
      // 这里列出需要使用的寄存器:cc表示汇编代码将改变条件寄存器,memory表示有内存被修改
      // 前面也提到过,这里仅列出指令改变的寄存器,输入输出使用的寄存器不放入其中,因此'a'不需要放到这儿
      // 如果汇编指令修改了eax而输入输出没有用到eax,那么就需要在这儿加上'a'
      : "cc", "memory");

代码中还有类似于%n的符号,可以理解为引用占位符。把输出参数和输入参数从左到右依次排序,并从0开始编号,即%0表示引用输出参数中"=a" (exchange_value)%4表示引用"r" (mp)。那么,cmpxchgl指令的部分,翻译成汇编即为:

; compare_value 表示 期望内存中的值,即旧值
; exchange_value 表示 更新后的值,即新值
; dest 表示 java对象对应属性的内存地址, (dest) 获取地址dest指向的值
cmpxchgl exchange_value (dest)

cmpxchg指令即交换比较指令,让目标操作数先和AL,AX,EAX寄存器中的值进行比较:

更具体的内容可以参考:CMPXCHG - 中文版CMPXCHG - 英文版

那上面的代码中哪一个是源操作数,哪一个是目标操作数?这又涉及到汇编语言编程风格的问题,在DOS/Windows下的汇编语言采用Intel风格,而Unix和Linux系统中,更多采用的是AT&T风格,这两者在语法格式上有很大不同,具体到操作数,有如下区别:

还有一个需要注意的区别就是:操作数的字长。

更多关于AT&T与Intel汇编的区别可以参考:Linux 汇编语言开发指南,关于「GCC内嵌汇编」的内容请查阅参考资料1和2,或自行谷歌搜索GCC-Inline-Assembly-HOWTO

NOW,应该基本可以理解这段代码:EAX寄存器中存的是"a" (compare_value),目标操作数是dest指向的值,即内存中存储的值,源操作数是exchange_value,即新值。将期望内存中的值与实际内存值比较,如果相等,则把exchange_value新值装载到dest内存中,并把新值写入EAX中;如果不相等,把dest地址的实际值放入EAX中。

在阅读这类代码时,要特别注意两种汇编语言风格的差异,否则很容易出错,我看到很多文章并没有说明这一点,特别容易让人产生疑惑。

到这儿,这段代码还有最后一个问题没有解决:LOCK_IF_MP(%4)这句代码如何理解?LOCK_IF_MP是一个宏定义,包含了多条汇编指令(汇编指令使用分号或换行来风格):

; #define LOCK_IF_MP(mp) "cmp $0, " #mp "; je 1f; lock; 1: "
; cmp是比较命令,两个操作数:$0表示立即操作数0,理解为常量吧
; mp为参数,从%4处引用而来,而%4表示 "r"(mp),即把mp的值存储到任意寄存器
; mp如何来?看函数代码的第一句:int mp = os::is_MP(),用于判断是否是多处理器机器
cmp $0, #mp;
; je为跳转指令,当ZF=1时,跳转到指定位置,这里表示跳转到标签1处
je lf;
; lock前缀
lock;
; 表示标签,类似于goto语句
1: cmpxchgl %1,(%3)

翻译过来就是,如果是在多处理器上运行则先添加LOCK#前缀后,再执行cmpxchgl命令,如果是单处理器,则直接执行cmpxchgl命令。那为什么在多处理器机器上要先添加LOCK#前缀,它又有何作用?这得先从CPU的结构说起。

CPU结构简单介绍

现代计算机系统,CPU核心已经不再直连到主存,而是与高速缓存相连,高速缓存与主存都连接到系统总线上,这条总线同时还用于与其它组件通信,大致的示意图如下。

图一:最简单的CPU缓存配置示意图

CPU向内存发出访问请求时,会先查看缓存内是否存在所需数据,如果存在,则直接返回该数据;如果不存在,则先从内存中取出数据并载入缓存,再将其返回处理器。目前主流的CPU一般都分为3级缓存,容量也越来越大,它们之间的区别和作用有兴趣的同学,可自行查阅,下文所述内容也仅把缓存当做一个整体看待。

现代的CPU也仅保证对内存的基本操作是原子且安全的,比如从内存中读取或者写入一个字节。实际上,CPU可以保证处理器对同一个缓存行里进行的16/32/64位操作是原子的,但是复杂的内存操作,处理器不自动保证原子性。

一个被Java开发者熟知的例子就是,JVM对long和double型数据的写入操作是不保证原子的。在Java中,long和double数据类型是64位的,在32位机器上对其它们的读取或写入操作会被分成两个单独的32位操作,这个过程中可能会出现一次上下文切换。而在64位机器上呢?答案是不一定。因为JVM规范中并没有要求对普通long和double型数据的读写必须是原子的,要看具体的实现。顺便再提一句,JVM规范要求对volatile long与volatile double的读写必须是原子的,但也仅限于读和写操作,仍然不保证i++这样的操作是原子的,即使它被声明为volatile的。

理解了这些,再回过头来看CMPXCHG指令,它涉及一次内存读和一次内存写,在单处理器环境下可以保证其顺序执行,不受干扰,但在多处理器环境下,并不能保证当前CPU在读写这段内存时不会有其他CPU在写这段内存。为了对复杂内存操作的原子性提供支持,CPU提供了总线锁机制,通过这种机制,CPU可以在总线上输出一个LOCK#信号,用来锁定总线,这时,其他处理器均不能通过总线访问内存。这就是为什么在多处理器环境执行CMPXCHG指令,要在指令前面增加LOCK前缀。

早期的CPU都是采用总线锁的方式来保证复杂指令操作的原子性,但这种方式缺陷也很明显,即开销大,本来,在某个时刻,仅需要保证对某个内存地址的操作是原子的,但现在却把处理器和内存之间的通信给掐断了,其他处理器也不能操作任何内存的数据。因此,Intel从P6架构开始改用Ringbus + MESI协议来对此进行优化,这种技术被称为缓存锁

其大致的实现方法是:若干个CPU核心通过Ringbus连接在一起,每个核心都维护自己的Cache状态,如果同一份数据在多个CPU Core里多有缓存,则Cache的状态为S(Shared),一旦有一个CPU Core改了这个数据,其状态变为M(Modified),且会将数据在其他CPU读取这个数据之前,将其写会内存并将缓存状态恢复为S,而其他CPU Core也能通过Ringbus瞬间感知到这个修改,从而把自己的Cache状态变成I(Invalid),当CPU Core读取缓存时,发现缓存已经失效,就会从内存中去获取,同时其缓存状态恢复为S。还有一种状态E(Exclusive),即数据仅存在自己的缓存内,且与内存中一致,可以理解为独占缓存。MESI协议中的MESI也就对应着这4种状态,其也被称为缓存一致性协议。但缓存锁也有自己的适应场景,如果不能使用缓存锁时,CPU仍然会采用锁总线的方式。更多关于缓存一致性的内容可以参考:缓存一致性(Cache Coherency)入门

这相当于给缓存单独做了一套总线,所以叫做Ringbus(环装总线),而在Intel目前的CPU中,Ringbus的结构已经变得更加复杂,其功能也不仅仅是侦听缓存的变化,各种Data、请求、响应、侦听等数据均可以在Ringbus上流动,以提升CPU的性能。

参考资料

  1. GCC-Inline-Assembly-HOWTO「阅读有困难的话,可以看翻译版本:GCC 内联汇编 HOWTO
  2. 内联汇编 - 从头开始
  3. EAX、ECX、EDX、EBX寄存器的作用
  4. Linux 汇编语言开发指南
  5. 原子操作是如何实现的
  6. 缓存一致性(Cache Coherency)入门
封面图:Rodrigo Soares on Unsplash

Comments

Post a Message

人生在世,错别字在所难免,无需纠正。

提交评论