MCS锁实现中的死锁

Question

硬件：达尔文内核版本13.2.0:Thu Apr 17 23:03:13 PDT 2014；root:xnu-2422.10.13~1/REEASE_X86_64 X86_64

原子.hpp1#ifndef ATOMIC_UTILS_H2#定义ATOMIC_UTILS_H3.4#包括5.6#define BARRIER((__asm_volatile("：："内存"(7.8#定义CPURELAX((__asm_volatile("暂停\n\t"：："内存"(910#define STORE_FENCE((__asm_volatile("mfence"：："内存"(；1112类AtomicUtils13{14公众：1516/**17*检查addr处的值是否等于oldval，如果是，请将其替换为newva l18*并返回旧值19*/20内联静态size_t compareAndExchange(易失性size_t*addr、size_t oldval、size_tnewval(21{22大小_t ret；23 __asm_volatile("锁定cmpxchgq%2，%1\n\t"24:"=a"(ret(，"+m"(*addr(25:"r"(newval(，"0"(oldval(26："内存"(；27回油口；28｝2930/**31*将x原子存储到addr中，并返回上一个存储在addr中的32*33*/34内联静态size_t loadAndStore(size_t x，volatile size_t*addr(36{37 size_t ret；38 __asm_volatile("锁定xchgq%1，%0\n\t"39:"+m"(*addr(，"=r"(ret(40:"1"(x((；41回风口；42}4344}；4546#endif

mcs.hpp1#如果MCS_LOCK_H2#定义MCS_LOCK_H3.4#包含"atomics.hpp"5#包括6.7级MCSLock8{9结构体mcs_lock_t10{11 mcs_lock_t((：next(0(，locked(false(｛｝12结构体mcs_lock_t*next；13 bool锁定；14}；1516公众：17 typedef结构体mcs_lock_t mcs_lock；1819私人：20 mcs_锁**尾；21静态提升：：thread_specific_ptr tls_node；2223公众：24 MCSLock(mcs_lock**lock_tail(：tail(lock_tail25{26如果(tls_node.get((==0(27 tls_node.reset(new mcs_lock(((；28｝2930空心锁((31{32 mcs_lock*thread_node=tls_node.get((；33线程节点->next=0；34 thread_node->locked=true；3536易失性mcs_lock*pred=relpret_cast(37原子库：：加载和存储(38 interpret_ cast(线程节点(，39 reinterpret_cast(尾部(40(41(；42如果(pred！=0(43{44pred->next=*尾部；4546 STORE_FENCE((；47//屏障((；//需要防止在prev->next=tail和thread_node->locked之间重新排序。(WR harzard(4849//对局部变量进行旋转。有人解锁我，plz！！50 while(thread_node->locked(51 CPU_RELAX((；5253}54}5556无效解锁((57{58 mcs_lock*thread_node=tls_node.get((；59如果(thread_node->next==0(60{61//如果为false，则我们有一个新线程请求锁定。现在松开新线程的锁62如果(63 AtomicUtils:：compareAndExchange(64个interpret_ cast(tail(，65 interpret_ cast(线程节点(，66 067(==interpret_cast(线程节点(68(69{70返回；71}7273 while(thread_node->next==0(74 CPU_RELAX((；75}7677 thread_node->next->locked=false；78}79}；8081 boost:：thread_specific_ptr MCSLock:：tls_node；82#endif

mcs_test.cpp
  1 #include "mcs.hpp"
  2 #include <iostream>
  3 #include <pthread.h>
  4 #include <vector>
  5 #define NUM_THREADS 16
  6 #define NUM_ITERATIONS 100
  7
  8 std::vector<int> elements;
  9 MCSLock::mcs_lock *tail = 0;
 10
 11 void* thread_run( void* data )
 12 {
 13   MCSLock lock( &tail );
 14   for( int i = 0; i < NUM_ITERATIONS; ++i )
 15   {
 16       lock.lock();
 17       elements.push_back( i );
 18       lock.unlock();
 19   }
 20
 21   return 0;
 22 }
 23
 24 int main()
 25 {
 26     pthread_t threads[ NUM_THREADS ];
 27     elements.reserve( NUM_THREADS * NUM_ITERATIONS );
 28
 29     {
 30         for( int i = 0; i < NUM_THREADS; ++i )
 31             pthread_create( &threads[i], NULL, thread_run, NULL );
 32
 33         for( int i = 0; i < NUM_THREADS; ++i )
 34             pthread_join( threads[i], NULL );
 35
 36         std::cout <<"nExiting main thread: " << std::endl;
 37     }
 38 }

以上代码是使用clang 编译的

问题：

我看到第50行中有1或2个线程被锁定((。除了主线程、被锁定的线程((之外，没有其他线程处于活动状态。这意味着，当其他线程调用unlock((时，它们不会为其他变量设置locked=false并退出。

有关于调试的建议吗？

困在这个问题上好几个小时都没有任何线索。

Answer 1

clang没有为这些内联asm块(如gcc的__sync_val_compare_and_swap(内置吗？为什么要重新发明轮子？

其次，我真的会考虑将内存阻塞器添加到loadAndStore中。在执行xchgq之前，您需要确保编译器保存在寄存器中的任何写入都被刷新到内存中。类似地，它将阻止gcc优化xchgq之前的内存读取。两者都不好。

第三，我将检查while循环的asm输出(thread_node->locked和thread_node->next(。由于这些变量不是易失性的，gcc可以对此进行优化，只执行一次读取。

这些可能不能解决你的问题，但这就是我的出发点。