mcs-lock/mcs-lock.h

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