原子操作

原子操作的定义

原子（atom）本意是“不能被进一步分割的最小粒子”，而所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch （切换到另一个线程）。

硬件支持

处理器通过缓存加锁或总线加锁方式来实现。

原子操作的函数

GCC内部提供的原子操作接口，主要针对Intel架构处理器，其它处理不保证可用。

函数	说明
type __sync_fetch_and_add (type *ptr, type value, …)	将value加到ptr上，结果更新到ptr，并返回操作之前*ptr的值
type __sync_fetch_and_sub (type *ptr, type value, …)	从ptr减去value，结果更新到ptr，并返回操作之前*ptr的值
type __sync_fetch_and_or (type *ptr, type value, …)	将ptr与value相或，结果更新到ptr，并返回操作之前*ptr的值
type __sync_fetch_and_and (type *ptr, type value, …)	将ptr与value相与，结果更新到ptr，并返回操作之前*ptr的值
type __sync_fetch_and_xor (type *ptr, type value, …)	将ptr与value异或，结果更新到ptr，并返回操作之前*ptr的值
type __sync_fetch_and_nand (type *ptr, type value, …)	将ptr取反后，与value相与，结果更新到ptr，并返回操作之前*ptr的值
type __sync_add_and_fetch (type *ptr, type value, …)	将value加到ptr上，结果更新到ptr，并返回操作之后新*ptr的值
type __sync_sub_and_fetch (type *ptr, type value, …)	从ptr减去value，结果更新到ptr，并返回操作之后新*ptr的值
type __sync_or_and_fetch (type *ptr, type value, …)	将ptr与value相或，结果更新到ptr，并返回操作之后新*ptr的值
type __sync_and_and_fetch (type *ptr, type value, …)	将ptr与value相与，结果更新到ptr，并返回操作之后新*ptr的值
type __sync_xor_and_fetch (type *ptr, type value, …)	将ptr与value异或，结果更新到ptr，并返回操作之后新*ptr的值
type __sync_nand_and_fetch (type *ptr, type value, …)	将ptr取反后，与value相与，结果更新到ptr，并返回操作之后新*ptr的值
bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, …)	比较ptr与oldval的值，如果两者相等，则将newval更新到ptr并返回true
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, …)	比较ptr与oldval的值，如果两者相等，则将newval更新到ptr并返回操作之前*ptr的值
__sync_synchronize (…)	发出完整内存栅栏
type __sync_lock_test_and_set (type *ptr, type value, …)	将value写入ptr，对ptr加锁，并返回操作之前*ptr的值。即，try spinlock语义
void __sync_lock_release (type *ptr, …)	将0写入到ptr，并对ptr解锁。即，unlock spinlock语义

例子

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char* argv[])
{
  long value = 2;
  printf("value=%ld\n", __sync_add_and_fetch(&value, 3));

  return 0;
}

我分别用gcc,mingw32和android clang编译器，基于x86_64和armv7a处理器架构进行编译生成汇编代码。

$ gcc -S atom.c -o atom.s
$ x86_64-w64-mingw32-gcc -S atom.c -o atom_mingw32.s
$ x86_64-linux-android26-clang -S atom.c -o atom_clang_x86_64.s
$ armv7a-linux-androideabi26-clang -S atom.c -o atom_clang_armv7a.s

	.file	"atom.c"
	.text
	.section	.rodata
.LC0:
	.string	"value=%ld\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB6:
	.cfi_startproc
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movl	%edi, -20(%rbp)
	movq	%rsi, -32(%rbp)
	movq	$2, -8(%rbp)
	movl	$3, %eax
	lock xaddq	%rax, -8(%rbp)
	addq	$3, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	main, .-main
	.ident	"GCC: (Debian 8.3.0-6) 8.3.0"
	.section	.note.GNU-stack,"",@progbits

	.file	"atom.c"
	.text
	.def	__main;	.scl	2;	.type	32;	.endef
	.section .rdata,"dr"
.LC0:
	.ascii "value=%ld\12\0"
	.text
	.globl	main
	.def	main;	.scl	2;	.type	32;	.endef
	.seh_proc	main
main:
	pushq	%rbp
	.seh_pushreg	%rbp
	movq	%rsp, %rbp
	.seh_setframe	%rbp, 0
	subq	$48, %rsp
	.seh_stackalloc	48
	.seh_endprologue
	movl	%ecx, 16(%rbp)
	movq	%rdx, 24(%rbp)
	call	__main
	movl	$2, -4(%rbp)
	movl	$3, %eax
	lock xaddl	%eax, -4(%rbp)
	addl	$3, %eax
	movl	%eax, %edx
	leaq	.LC0(%rip), %rcx
	call	printf
	movl	$0, %eax
	addq	$48, %rsp
	popq	%rbp
	ret
	.seh_endproc
	.ident	"GCC: (GNU) 8.3-posix 20190406"
	.def	printf;	.scl	2;	.type	32;	.endef

	.text
	.file	"atom.c"
	.globl	main                    # -- Begin function main
	.p2align	4, 0x90
	.type	main,@function
main:                                   # @main
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset %rbp, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register %rbp
	subq	$32, %rsp
	movl	$0, -4(%rbp)
	movl	%edi, -8(%rbp)
	movq	%rsi, -16(%rbp)
	movq	$2, -24(%rbp)
	movl	$3, %esi
	lock		xaddq	%rsi, -24(%rbp)
	addq	$3, %rsi
	leaq	.L.str(%rip), %rdi
	movb	$0, %al
	callq	printf@PLT
	xorl	%ecx, %ecx
	movl	%eax, -28(%rbp)         # 4-byte Spill
	movl	%ecx, %eax
	addq	$32, %rsp
	popq	%rbp
	.cfi_def_cfa %rsp, 8
	retq
.Lfunc_end0:
	.size	main, .Lfunc_end0-main
	.cfi_endproc
                                        # -- End function
	.type	.L.str,@object          # @.str
	.section	.rodata.str1.1,"aMS",@progbits,1
.L.str:
	.asciz	"value=%ld\n"
	.size	.L.str, 11


	.ident	"Android (5220042 based on r346389c) clang version 8.0.7 (https://android.googlesource.com/toolchain/clang b55f2d4ebfd35bf643d27dbca1bb228957008617) (https://android.googlesource.com/toolchain/llvm 3c393fe7a7e13b0fba4ac75a01aa683d7a5b11cd) (based on LLVM 8.0.7svn)"
	.section	".note.GNU-stack","",@progbits

可以看到x86_64架构下生成的汇编代码基本一至，其中lock xaddq就是原子操作。除了lock前缀，所以x打头的指令也代表原子操作。

text
	.syntax unified
	.eabi_attribute	67, "2.09"	@ Tag_conformance
	.eabi_attribute	6, 10	@ Tag_CPU_arch
	.eabi_attribute	7, 65	@ Tag_CPU_arch_profile
	.eabi_attribute	8, 1	@ Tag_ARM_ISA_use
	.eabi_attribute	9, 2	@ Tag_THUMB_ISA_use
	.fpu	neon
	.eabi_attribute	34, 1	@ Tag_CPU_unaligned_access
	.eabi_attribute	15, 1	@ Tag_ABI_PCS_RW_data
	.eabi_attribute	16, 1	@ Tag_ABI_PCS_RO_data
	.eabi_attribute	17, 2	@ Tag_ABI_PCS_GOT_use
	.eabi_attribute	20, 1	@ Tag_ABI_FP_denormal
	.eabi_attribute	21, 1	@ Tag_ABI_FP_exceptions
	.eabi_attribute	23, 3	@ Tag_ABI_FP_number_model
	.eabi_attribute	24, 1	@ Tag_ABI_align_needed
	.eabi_attribute	25, 1	@ Tag_ABI_align_preserved
	.eabi_attribute	38, 1	@ Tag_ABI_FP_16bit_format
	.eabi_attribute	18, 4	@ Tag_ABI_PCS_wchar_t
	.eabi_attribute	26, 2	@ Tag_ABI_enum_size
	.eabi_attribute	14, 0	@ Tag_ABI_PCS_R9_use
	.file	"atom.c"
	.globl	main                    @ -- Begin function main
	.p2align	2
	.type	main,%function
	.code	32                      @ @main
main:
	.fnstart
@ %bb.0:
	.save	{r11, lr}
	push	{r11, lr}
	.setfp	r11, sp
	mov	r11, sp
	.pad	#24
	sub	sp, sp, #24
	movw	r2, #0
	str	r2, [r11, #-4]
	str	r0, [r11, #-8]
	str	r1, [sp, #12]
	movw	r0, #2
	str	r0, [sp, #8]
	dmb	ish
.LBB0_1:                                @ =>This Inner Loop Header: Depth=1
	add	r0, sp, #8
	ldrex	r0, [r0]
	add	r1, r0, #3
	add	r2, sp, #8
	strex	r3, r1, [r2]
	cmp	r3, #0
	str	r0, [sp, #4]            @ 4-byte Spill
	bne	.LBB0_1
@ %bb.2:
	ldr	r0, .LCPI0_0
.LPC0_0:
	add	r0, pc, r0
	dmb	ish
	ldr	r1, [sp, #4]            @ 4-byte Reload
	add	r1, r1, #3
	bl	printf
	movw	r1, #0
	str	r0, [sp]                @ 4-byte Spill
	mov	r0, r1
	mov	sp, r11
	pop	{r11, pc}
	.p2align	2
@ %bb.3:
.LCPI0_0:
	.long	.L.str-(.LPC0_0+8)
.Lfunc_end0:
	.size	main, .Lfunc_end0-main
	.cantunwind
	.fnend
                                        @ -- End function
	.type	.L.str,%object          @ @.str
	.section	.rodata.str1.1,"aMS",%progbits,1
.L.str:
	.asciz	"value=%ld\n"
	.size	.L.str, 11


	.ident	"Android (5220042 based on r346389c) clang version 8.0.7 (https://android.googlesource.com/toolchain/clang b55f2d4ebfd35bf643d27dbca1bb228957008617) (https://android.googlesource.com/toolchain/llvm 3c393fe7a7e13b0fba4ac75a01aa683d7a5b11cd) (based on LLVM 8.0.7svn)"
	.section	".note.GNU-stack","",%progbits

ARM架构下原子操作的的相关汇编指令是ldrex、strex。

原子操作的应用

全局自增序号应用

__sync_fetch_and_add = i++

__sync_add_and_fetch = ++i

互斥锁

互斥锁是一种数据结构，使你可以执行一系列互斥操作。而原子操作是互斥的单个操作，这意味着没有其他线程可以打断它。

所以说原子布尔类型只可以实现互斥锁的部分功能。

__sync_bool_compare_and_swap(&mutex, false, true) return true 加锁成功

__sync_bool_compare_and_swap(&mutex, true, false) return true 解锁成功

自旋锁

互斥锁会让资源申请者进入睡眠状态，而自旋锁不会引起调用者睡眠，会一直循环判断该锁是否成功获取。自旋锁是专为防止多处理器并发而引入的一种锁。

__sync_lock_test_and_set -> trylock

__sync_lock_release -> tryunlock