多线程读写无锁链表： 之前有没有相同的实现？ (更新)

wlmqgzm

zylthinking 发表于 2017-04-18 20:51
回复 79# wlmqgzm

没错， 在纯理论上， 我的实现的理论基础是站在下风但要注意, 我的碰撞降低是倾向于 ...

基本上, 各家公司的具体实现上, 如果push返回false, 表示 队列buffer 已经满了, 紧接的代码都是 std::this_thread::yield(), 直接出让CPU控制权, 不会在那里循环死等.

lxyscls

zylthinking 发表于 2017-04-18 18:52
回复 69# wlmqgzm

读毛代码，一看就知道buf[tail].load(std::memory_order_acquire) == invalid_val

其实在X86平台上面，memory_order_acquire/memory_order_release最后连指令都看不到，因为X86只存在store/load reorder，其他三种乱序不存在，只要保证没有编译器优化乱序就行了。
下面所有输出均来自https://gcc.godbolt.org

1. #include <atomic>
   
2. using namespace std;
   
3. 
   
4. int flag = 0;
   
5. int data = 0;
   
6. 
   
7. int foo() {
   
8.     int val = 0;
   
9.     if (flag) {
   
10.         atomic_thread_fence(memory_order_acquire);
    
11.         val = data;
    
12.     }
    
13.     return val;
    
14. }
    
15. 
    
16. void bar() {
    
17.     data = 123;
    
18.     atomic_thread_fence(memory_order_release);
    
19.     flag = 1;
    
20. }

复制代码

x86-64 gcc 6.2 -O3 -std=c++11 -fno-verbose-asm -Wall -Wextra

1. foo():
   
2.         mov     eax, DWORD PTR flag[rip]
   
3.         test    eax, eax
   
4.         cmovne  eax, DWORD PTR data[rip]
   
5.         ret
   
6. bar():
   
7.         mov     DWORD PTR data[rip], 123
   
8.         mov     DWORD PTR flag[rip], 1
   
9.         ret
   
10. data:
    
11.         .zero   4
    
12. flag:
    
13.         .zero   4

复制代码

x86-64 clang 3.9.0 -O3 -std=c++11 -fno-verbose-asm -Wall -Wextra

1. foo():
   
2.         xor     eax, eax
   
3.         cmp     dword ptr [rip + flag], 0
   
4.         je      .LBB0_2
   
5.         mov     eax, dword ptr [rip + data]
   
6. .LBB0_2:
   
7.         ret
   
8. 
   
9. bar():
   
10.         mov     dword ptr [rip + data], 123
    
11.         mov     dword ptr [rip + flag], 1
    
12.         ret
    
13. 
    
14. flag:
    
15.         .long   0
    
16. 
    
17. data:
    
18.         .long   0

复制代码

换种写法

1. #include <atomic>
   
2. using namespace std;
   
3. 
   
4. atomic<int> flag = {0};
   
5. int data = 0;
   
6. 
   
7. int foo() {
   
8.     int val = 0;
   
9.     if (flag.load(memory_order_acquire)) {
   
10.         val = data;
    
11.     }
    
12.     return val;
    
13. }
    
14. 
    
15. void bar() {
    
16.     data = 123;
    
17.     flag.store(1, memory_order_release);
    
18. }

复制代码

x86-64 gcc 6.2 -O3 -std=c++11 -fno-verbose-asm -Wall -Wextra

1. foo():
   
2.         mov     eax, DWORD PTR flag[rip]
   
3.         test    eax, eax
   
4.         mov     eax, 0
   
5.         cmovne  eax, DWORD PTR data[rip]
   
6.         ret
   
7. bar():
   
8.         mov     DWORD PTR data[rip], 123
   
9.         mov     DWORD PTR flag[rip], 1
   
10.         ret
    
11. data:
    
12.         .zero   4
    
13. flag:
    
14.         .zero   4

复制代码

x86-64 clang 3.9.0 -O3 -std=c++11 -fno-verbose-asm -Wall -Wextra

1. foo():
   
2.         mov     eax, dword ptr [rip + flag]
   
3.         test    eax, eax
   
4.         cmovne  eax, dword ptr [rip + data]
   
5.         ret
   
6. 
   
7. bar():
   
8.         mov     dword ptr [rip + data], 123
   
9.         mov     dword ptr [rip + flag], 1
   
10.         ret
    
11. 
    
12. flag:
    
13.         .zero   4
    
14. 
    
15. data:
    
16.         .long   0

复制代码

folklore

回复 81# wlmqgzm

yield本身就要成百上千条指令， 它是一个系统调用。。。。

wlmqgzm

folklore 发表于 2017-04-19 10:54
回复 81# wlmqgzm

yield本身就要成百上千条指令， 它是一个系统调用。。。。

std::this_thread::yield 严格意义上说， 存在两种可能性，
第一种：如果没有其他线程在等待执行， 那么这个调用将在113纳秒的时间里返回，此时间不足以产生一次系统调用。
第2种：如果有其他线程在等待执行， 是系统调用，作用是切换线程。

这里使用yield的原因是， 如果队列已经满了， 一般就意味着需要很多的时间，队列才会被消费者处理完毕，变成empty(),  因此，生产者线程可以挂起来了， 把CPU切换到其他有效的任务去执行， 而不是在这里无效的循环等待，降低系统总体的处理能力。

wlmqgzm

lxyscls 发表于 2017-04-19 10:43
其实在X86平台上面，memory_order_acquire/memory_order_release最后连指令都看不到，因为X86只存在store ...

这个跟编译器的类型， 与编译器的优化都相关，还与是否启用多线程也相关，与CPU的类型也有关，

我印象中，如果启用了多线程以后，
memory_order_acquire   等效于 读屏障
memory_order_release   等效于  写屏障  

在单线程下，这两条指令会被编译器的优化掉

lxyscls

wlmqgzm 发表于 2017-04-19 12:56
这个跟编译器的类型， 与编译器的优化都相关，还与是否启用多线程也相关，与CPU的类型也有关，

我印象 ...

X86/X86-64是强内存模型系统（Memory ordering from wiki），只要保证了编译期没乱序，那么就不需要再插入任何内存指令了，跟是否是多线程无关
asm volatile("":::"memory")这个指令只是指导编译器不要乱序的，编译后就没有了



这张图来自<Acquire and Release Semantics>

当然，如果是ARM这种弱内存模型系统，就会生成一些内存屏障指令了

wlmqgzm

回复 86# lxyscls
其实我最早读过的无锁队列， 是非常古老的linux的X86早期核心代码，印象当中作者是使用了写内存屏障。

以下是一些资料：
LINUX对于x86而言，在为UP体系统架构下，调用barrier()进行通用内存屏障。在SMP体系架构下，若为64位CPU或支持mfence、lfence、sfence指令的32位CPU，则smp_mb()、smp_rmb()、smp_smb()对应通用内存屏障、写屏障和读屏障；而不支持mfence、lfence、sfence指令的32位CPU则smp_mb()、smp_rmb()、smp_smb()对应LOCK操作。源码请参见《内存屏障源码分析》一节。


内存屏障源码分析

/include/asm-generic/system.h：

053 #ifdef CONFIG_SMP

054 #define smp_mb()        mb()

055 #define smp_rmb()       rmb()

056 #define smp_wmb()       wmb()

057 #else

058 #define smp_mb()        barrier()

059 #define smp_rmb()       barrier()

060 #define smp_wmb()       barrier()

061 #endif

在x86 UP体系架构中，smp_mb、smp_rmb、smp_wmb被翻译成barrier：

012 #define barrier() __asm__ __volatile__("": : :"memory")

__volatile告诉编译器此条语句不进行任何优化，"": : :"memory" 内存单元已被修改、需要重新读入。



在x86 SMP体系架构中，smp_mb、smp_rmb、smp_wmb如下定义：

/arch/x86/include/asm/system.h：

352 /*

353  * Force strict CPU ordering.

354  * And yes, this is required on UP too when we're talking

355  * to devices.

356  */

357 #ifdef CONFIG_X86_32

358 /*

359  * Some non-Intel clones support out of order store. wmb() ceases to be a

360  * nop for these.

361  */

362 #define mb() alternative("lock; addl $0,0(%%esp)", "mfence", X86_FEATURE_XMM2)

363 #define rmb() alternative("lock; addl $0,0(%%esp)", "lfence", X86_FEATURE_XMM2)

364 #define wmb() alternative("lock; addl $0,0(%%esp)", "sfence", X86_FEATURE_XMM)

365 #else

366 #define mb()    asm volatile("mfence":::"memory")

367 #define rmb()   asm volatile("lfence":::"memory")

368 #define wmb()   asm volatile("sfence" ::: "memory")

369 #endif

362~364行针对x86的32位CPU，366~368行针对x86的64位CPU。



在x86的64位CPU中，mb()宏实际为：

asm volatile("sfence" ::: "memory")。

volatile告诉编译器严禁在此处汇编语句与其它语句重组优化，memory强制编译器假设RAM所有内存单元均被汇编指令修改，"sfence" ::: 表示在此插入一条串行化汇编指令sfence。

mfence：串行化发生在mfence指令之前的读写操作

lfence：串行化发生在mfence指令之前的读操作、但不影响写操作

sfence：串行化发生在mfence指令之前的写操作、但不影响读操作



在x86的32位CPU中，mb()宏实际为：

mb() alternative("lock; addl $0,0(%%esp)", "mfence", X86_FEATURE_XMM2)

由于x86的32位CPU有可能不提供mfence、lfence、sfence三条汇编指令的支持，故在不支持mfence的指令中使用："lock; addl $0,0(%%esp)", "mfence"。lock表示将“addl $0,0(%%esp)”语句作为内存屏障。

关于lock的实现：cpu上有一根pin #HLOCK连到北桥,lock前缀会在执行这条指令前先去拉这根pin，持续到这个指令结束时放开#HLOCK pin，在这期间，北桥会屏蔽掉一切外设以及AGP的内存操作。也就保证了这条指令的atomic。



参考资料

《memroy-barries.txt》，/Documentation/memory-barriers.txt

《LINUX内核内存屏障》，http://blog.csdn.net/ljl1603/article/details/6793982

lxyscls

wlmqgzm 发表于 2017-04-19 14:55
回复 86# lxyscls
其实我最早读过的无锁队列， 是非常古老的linux的X86早期核心代码，印象当中作者是使用 ...

我大概扫了一下，您贴的部分基本来自Paul E. McKenney的雄文：<LINUX KERNEL MEMORY BARRIERS>.

但是lfence不对应memory_order_acquire语义，sfence也不对应memory_order_release语义，只有mfence对应memory_order_seq_cst

Performs a serializing operation on all store-to-memory instructions that were issued prior the SFENCE instruction.
This serializing operation guarantees that every store instruction that precedes the SFENCE instruction in program
order becomes globally visible before any store instruct ion that follows the SFENCE instruction.

这个是intel指令手册中对sfence的说明

Release semantics is a property which can only apply to operations which write to shared memory, whether they are read-modify-write operations or plain stores. The operation is then considered a write-release. Release semantics prevent memory reordering of the write-release with any read or write operation which precedes it in program order.

对比可见，sfence只负责“屏障”之前的store操作，而不符合write-release的语义

linux 3.10, arch/x86/include/asm/barrier.h中，其实smp_rmb和smp_wmb对应的都是barrier，而这个barrier就是我前面讲的asm volatile("":::"memory")，负责通告编译器不优化乱序的

PS: 内核代码不熟，找错讲错勿怪

wlmqgzm

早期linux内核kqueue, 是我最早仔细读过的无锁队列，  这个库支持任意长度的对象入队列，代码不到百行，效率之高，令人叫赞。

刚才已经找不到源代码了，印象中分析过：
早期的X86不需要使用写内存屏障，
然后自从开始支持SMP 多核CPU体系，就需要在代码中增加 写内存屏障。
中期X86只需要使用写内存屏障， 不需要使用读内存屏障。例：无锁队列 kqueue.h
后期X86 CPU开始 具备 多发射和乱序执行 指令，因此， 就必须要增加 读内存屏障

wlmqgzm

回复 88# lxyscls

早期的X86不需要使用写内存屏障，
然后自从开始支持SMP 多核CPU体系，就需要在代码中增加 写内存屏障。
中期X86只需要使用写内存屏障， 不需要使用读内存屏障。例：无锁队列 kqueue.h
后期X86 CPU开始 具备 多发射和乱序执行 指令，因此， 就必须要增加 读内存屏障