benchmark/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
  17 struct mcs_mutex {
  18 public:
  19         // tail is null when lock is not held
  20         std::atomic<mcs_node *> m_tail;
  21
  22         mcs_mutex() {
  23                 /**
  24                         @Begin
  25                 @Entry_point
  26                         @End
  27                 */
  28                 m_tail.store( NULL );
  29         }
  30         ~mcs_mutex() {
  31                 ASSERT( m_tail.load() == NULL );
  32         }
  33
  34         // Each thread will have their own guard.
  35         class guard {
  36         public:
  37                 mcs_mutex * m_t;
  38                 mcs_node    m_node; // node held on the stack
  39
  40                 guard(mcs_mutex * t) : m_t(t) { t->lock(this); }
  41                 ~guard() { m_t->unlock(this); }
  42         };
  43
  44         /**
  45                 @Begin
  46                 @Options:
  47                         LANG = CPP;
  48                         CLASS = mcs_mutex;
  49                 @Global_define:
  50                         @DeclareVar:
  51                                 bool _lock_acquired;
  52                         @InitVar:
  53                                 _lock_acquired = false;
  54                 @Happens_before:
  55                         Unlock -> Lock
  56                 @End
  57         */
  58
  59         /**
  60                 @Begin
  61                 @Interface: Lock
  62                 @Commit_point_set: Lock_Enqueue_Point1 | Lock_Enqueue_Point2
  63                 @Check:
  64                         _lock_acquired == false;
  65                 @Action:
  66                         _lock_acquired = true;
  67                 @End
  68         */
  69         void lock(guard * I) {
  70                 mcs_node * me = &(I->m_node);
  71
  72                 // set up my node :
  73                 // not published yet so relaxed :
  74                 me->next.store(NULL, std::mo_relaxed );
  75                 me->gate.store(1, std::mo_relaxed );
  76
  77                 // publish my node as the new tail :
  78                 mcs_node * pred = m_tail.exchange(me, std::mo_acq_rel);
  79                 /**
  80                         @Begin
  81                         @Commit_point_define_check: pred == NULL
  82                         @Label: Lock_Enqueue_Point1
  83                         @End
  84                 */
  85                 if ( pred != NULL ) {
  86                         // (*1) race here
  87                         // unlock of pred can see me in the tail before I fill next
  88
  89                         // publish me to previous lock-holder :
  90                         pred->next.store(me, std::mo_release );
  91
  92                         // (*2) pred not touched any more
  93
  94                         // now this is the spin -
  95                         // wait on predecessor setting my flag -
  96                         rl::linear_backoff bo;
  97                         int my_gate = 1;
  98                         while (my_gate ) {
  99                                 my_gate = me->gate.load(std::mo_acquire);
 100                                 /**
 101                                         @Begin
 102                                         @Commit_point_define_check: my_gate == 0
 103                                         @Label: Lock_Enqueue_Point2
 104                                         @End
 105                                 */
 106                                 thrd_yield();
 107                         }
 108                 }
 109         }
 110
 111         /**
 112                 @Begin
 113                 @Interface: Unlock
 114                 @Commit_point_set:
 115                         Unlock_Point_Success_1 | Unlock_Point_Success_2
 116                 @Check:
 117                         _lock_acquired == true
 118                 @Action:
 119                         _lock_acquired = false;
 120                 @End
 121         */
 122         void unlock(guard * I) {
 123                 mcs_node * me = &(I->m_node);
 124
 125                 mcs_node * next = me->next.load(std::mo_acquire);
 126                 if ( next == NULL )
 127                 {
 128                         mcs_node * tail_was_me = me;
 129                         bool success;
 130                         success = m_tail.compare_exchange_strong(
 131                                 tail_was_me,NULL,std::mo_acq_rel);
 132                         /**
 133                                 @Begin
 134                                 @Commit_point_define_check: success == true
 135                                 @Label: Unlock_Point_Success_1
 136                                 @End
 137                         */
 138                         if (success) {
 139
 140                                 // got null in tail, mutex is unlocked
 141                                 return;
 142                         }
 143
 144                         // (*1) catch the race :
 145                         rl::linear_backoff bo;
 146                         for(;;) {
 147                                 next = me->next.load(std::mo_acquire);
 148                                 if ( next != NULL )
 149                                         break;
 150                                 thrd_yield();
 151                         }
 152                 }
 153
 154                 // (*2) - store to next must be done,
 155                 //  so no locker can be viewing my node any more
 156
 157                 // let next guy in :
 158                 next->gate.store( 0, std::mo_release );
 159                 /**
 160                         @Begin
 161                         @Commit_point_define_check: true
 162                         @Label: Unlock_Point_Success_2
 163                         @End
 164                 */
 165         }
 166 };
 167 /**
 168         @Begin
 169         @Class_end
 170         @End
 171 */