mcs-lock/mcs-lock.h

   1 // mcs on stack
   2
   3 #include <stdatomic.h>
   4 #include <unrelacy.h>
   5
   6 struct mcs_node {
   7         std::atomic<mcs_node *> next;
   8         std::atomic<int> gate;
   9
  10         mcs_node() {
  11                 next.store(0);
  12                 gate.store(0);
  13         }
  14 };
  15
  16 struct mcs_mutex {
  17 public:
  18         // tail is null when lock is not held
  19         std::atomic<mcs_node *> m_tail;
  20
  21         mcs_mutex() {
  22                 m_tail.store( NULL );
  23         }
  24         ~mcs_mutex() {
  25                 ASSERT( m_tail.load() == NULL );
  26         }
  27
  28         class guard {
  29         public:
  30                 mcs_mutex * m_t;
  31                 mcs_node    m_node; // node held on the stack
  32
  33                 guard(mcs_mutex * t) : m_t(t) { t->lock(this); }
  34                 ~guard() { m_t->unlock(this); }
  35         };
  36
  37         void lock(guard * I) {
  38                 mcs_node * me = &(I->m_node);
  39
  40                 // set up my node :
  41                 // not published yet so relaxed :
  42                 me->next.store(NULL, std::mo_relaxed );
  43                 me->gate.store(1, std::mo_relaxed );
  44
  45                 // publish my node as the new tail :
  46                 mcs_node * pred = m_tail.exchange(me, std::mo_acq_rel);
  47                 if ( pred != NULL ) {
  48                         // (*1) race here
  49                         // unlock of pred can see me in the tail before I fill next
  50
  51                         // publish me to previous lock-holder :
  52                         pred->next.store(me, std::mo_release );
  53
  54                         // (*2) pred not touched any more
  55
  56                         // now this is the spin -
  57                         // wait on predecessor setting my flag -
  58                         rl::linear_backoff bo;
  59                         while ( me->gate.load(std::mo_acquire) ) {
  60                                 bo.yield();
  61                         }
  62                 }
  63         }
  64
  65         void unlock(guard * I) {
  66                 mcs_node * me = &(I->m_node);
  67
  68                 mcs_node * next = me->next.load(std::mo_acquire);
  69                 if ( next == NULL )
  70                 {
  71                         mcs_node * tail_was_me = me;
  72                         if ( m_tail.compare_exchange_strong( tail_was_me,NULL,std::mo_acq_rel) ) {
  73                                 // got null in tail, mutex is unlocked
  74                                 return;
  75                         }
  76
  77                         // (*1) catch the race :
  78                         rl::linear_backoff bo;
  79                         for(;;) {
  80                                 next = me->next.load(std::mo_acquire);
  81                                 if ( next != NULL )
  82                                         break;
  83                                 bo.yield();
  84                         }
  85                 }
  86
  87                 // (*2) - store to next must be done,
  88                 //  so no locker can be viewing my node any more
  89
  90                 // let next guy in :
  91                 next->gate.store( 0, std::mo_release );
  92         }
  93 };