Sholck

不积跬步,无以至千里.不积小流,无以成江海

0%

cmpxchg kernel-api学习

cmpxchg kernel api

cmpxchg是一个内核x86经常用到的api,功能是用来比较和交换的,带着以下疑问研究此api

  1. 为什么需要设计成原子性的
  2. 如何实现原子性

函数设计

函数原型设计如下:

1
2
3
4
5
6
7
8
9
10
11
cmpxchg(A, C, B)

include/linux/atomic/atomic-instrumented.h

#define cmpxchg(ptr, ...) \
({ \
typeof(ptr) __ai_ptr = (ptr); \
kcsan_mb(); \
instrument_atomic_write(__ai_ptr, sizeof(*__ai_ptr)); \
arch_cmpxchg(__ai_ptr, __VA_ARGS__); \
})

函数实现大体分为三部分

  1. kcsan_mb, 2019年google新加检测设计,不开启KCSAN无用
  2. instrument_atomic_write 当开启KASAN时,在实际的写发生前,通过检查影子内存来判定访问地址和地址内存是否合规
  3. arch_cmpxchg 平台强相关,通过汇编部分完成硬件辅助实现原子操作

因此重点研究arch_cmpxchg

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#define arch_cmpxchg(ptr, old, new)                                     \    
__cmpxchg(ptr, old, new, sizeof(*(ptr)))

#define __cmpxchg(ptr, old, new, size) \
__raw_cmpxchg((ptr), (old), (new), (size), LOCK_PREFIX)

//__raw_cmpxchg实现了不同字长的数据交换

/*
* Atomic compare and exchange. Compare OLD with MEM, if identical,
* store NEW in MEM. Return the initial value in MEM. Success is
* indicated by comparing RETURN with OLD.
*/
#define __raw_cmpxchg(ptr, old, new, size, lock) \
({ \
__typeof__(*(ptr)) __ret; \
__typeof__(*(ptr)) __old = (old); \
__typeof__(*(ptr)) __new = (new); \
switch (size) { \
case __X86_CASE_B: \
{ \
volatile u8 *__ptr = (volatile u8 *)(ptr); \
asm volatile(lock "cmpxchgb %2,%1" \
: "=a" (__ret), "+m" (*__ptr) \
: "q" (__new), "0" (__old) \
: "memory"); \
break; \
} \
case __X86_CASE_W: \
{ \
volatile u16 *__ptr = (volatile u16 *)(ptr); \
asm volatile(lock "cmpxchgw %2,%1" \
: "=a" (__ret), "+m" (*__ptr) \
: "r" (__new), "0" (__old) \
: "memory"); \
break; \
} \
case __X86_CASE_L: \
{ \
volatile u32 *__ptr = (volatile u32 *)(ptr); \
asm volatile(lock "cmpxchgl %2,%1" \
: "=a" (__ret), "+m" (*__ptr) \
: "r" (__new), "0" (__old) \
: "memory"); \
break; \
} \
case __X86_CASE_Q: \
{ \
volatile u64 *__ptr = (volatile u64 *)(ptr); \
asm volatile(lock "cmpxchgq %2,%1" \
: "=a" (__ret), "+m" (*__ptr) \
: "r" (__new), "0" (__old) \
: "memory"); \
break; \
} \
default: \
__cmpxchg_wrong_size(); \
} \
__ret; \
})

看一下汇编的逻辑:

1
2
3
4
5
6
7
8
9
case __X86_CASE_L:                                              \                                                                                                                                           
{ \
volatile u32 *__ptr = (volatile u32 *)(ptr); \
asm volatile(lock "cmpxchgl %2,%1" \
: "=a" (__ret), "+m" (*__ptr) \
: "r" (__new), "0" (__old) \
: "memory"); \
break; \
}

这段内嵌汇编有两个操作数(占位符) ,对应如下

1
2
3
4
5
6
操作数          操作数说明          c语言表达式
%0(输出部分) "=a" __ret = 代表输出操作数只写 a是eax寄存器 ,整体意思是运算完成需要将eax的结果存入__ret
%1(输出部分) "+m" *__ptr + 代表输出操作数可读可写 m指明是内存变量 *__ptr的值,不需要绑定寄存器,即操作数是放在内存中的,不是寄存器
%2(输入部分) "r" __new r指将输入变量放入到通用寄存器(动态分配)
%3(输入部分) "0" __old 0是用来匹配的,即__old操作数将用来和指定的操作数匹配
被修改部分 "memory" 因为 __new__old是被从内存装载到寄存器的,在内嵌汇编之后再使用这些变量,应该从内存重新装载,而不是使用寄存器的值,因为寄存器的值可能已经发生改变

因此cmpxchgl %2,%1可以理解为 cmpxchgl __new, *__ptr

cmxchgl 指令的作用是比较并交换 (寄存器/内存变量)和 (寄存器) 的值,该指令集语法如下

1
2
3
Intel语法: 目的操作数,源操作数   CMPXCHG EBX,ECX ;如果EAX与EBX相等,则ECX送EBX且ZF置1;否则EBX送EAX,且ZF清0

AT&T语法:源操作数,目的操作数 cmpxchg %ecx, %ebx;如果EAX与EBX相等,则ECX送EBX且ZF置1;否则EBX送EAX,且ZF清0

这里需要注意

  1. linux内核用的AT&T汇编语言,包括目前启动时的arch/x86/boot/header.S, 早期的linux kernel开始时的bootsect.s和setu.s是用intel的汇编
  2. inter的汇编只能用在inter的x86上,AT&T是可以在多种cpu上使用的,arm也有自己的汇编

因此这里按照AT&T语法解读为:__new读出给ecx寄存器, *__ptr为目标内存变量,__old作为匹配数,存放到EAX

1
2
3
//__raw_cmpxchg(ptr, old, new, size, lock)
%ebx(mem) %eax %ecx
*__ptr __old __new

if(*__ptr == __old) __ptr = __new
if(
__ptr != __old) __old = *__ptr

因此api cmpxchg逻辑可以理解为函数如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//R=cmpxchg(A, C, B)
cmpxchg(__ptr, __old, __new){
if(*__ptr == __old) {
*__ptr = __new;
} else {
__old = *__ptr;
}
return __old;
}

//执行完成只有输出部分会改变, 即__ptr指向的内存, __old的值内存上不会改变,因为是作用为寄存器上的。

//从结果来看,我们可以从R和C的值对比检查A是否有更新
if A==C C不变, return C
if A!=C C=A return C

疑问解答

  1. 为什么需要设计成原子性?
    保证共享内存操作是多处理器下线程同步的

  2. 为什么不使用锁机制?
    锁性能较差,需要减少锁的使用,这一行为称为lockless,即无锁机制

  3. 硬件辅助是如何保证原子性的?

    a. 内嵌汇编使用volatile, 为__volatile__别名,告知编译器不会对内嵌汇编进行优化,指令保持原样

    b. 内嵌汇编时使用lock, 带lock的指令在操作前会锁总线,xchg指令默认就是会锁总线的,保证指令执行的原子性(什么是锁总线?锁总线为什么能保持指令的原子性)

    1
    2
    3
    4
    5
    6
    7
    //arch/x86/include/asm/cmpxchg.h
    /*
    * Note: no "lock" prefix even on SMP: xchg always implies lock anyway.
    * Since this is generally used to protect other memory information, we
    * use "asm volatile" and "memory" clobbers to prevent gcc from moving
    * information around.
    */

    c. 内嵌汇编clobbers部分使用memory修饰

     memory告知gcc编译器:
         1. 不要将这段指令和内嵌汇编前的指令重新排序,也就是在执行内嵌汇编代码之前,它前面的指令都执行完毕
         2. 不要将内存变量缓存到寄存器,因为指令中可能用到了内存变量,而这些变量可能会因为其他原因改变,比如*__ptr。
         3. 在内嵌汇编之后再使用内嵌汇编中的变量,应该从内存重新装载,而不是使用寄存器的值,因为寄存器的值可能已经发生改变, 比如__old

扩展

  1. 编译器优化

  2. volatile修饰变量指的是变量可能被其他线程改变,因此不将该变量存入寄存器,每次读取都从内存读取

  3. 锁总线, 锁缓存

  4. memory barrier 内存屏障

  5. 缓存一致性

参考

  1. Linux内核中的cmpxchg函数

  2. 内嵌汇编 %0,%1 是什么

  3. 嵌入式汇编(内联汇编)

  4. 内嵌汇编

  5. GNU C内嵌汇编语言

  6. linux内核是用8086汇编还是Intel汇编还是AT&T汇编写的?

  7. AT&T汇编、Intel汇编、arm汇编关联

  8. 内嵌汇编 - cmpxchgl 指令学习笔记

  9. GCC在C语言中内嵌汇编 asm volatile 对编译器优化有很好的描述

  10. GCC在C语言中内嵌汇编 asm volatile (2)

  11. 原子性操作atomic_t

  12. linux xchgl 汇编含义,X86 xchgl和cmpxchgl指令替换案例分享

深入:

  1. 深入理解原子操作的本质

  2. 【译】CPU 高速缓存原理和应用