benchmark/mcs-lock/mcs-lock.h

   1 // mcs on stack
   2
   3 #include <stdatomic.h>
   4 #include <unrelacy.h>
   5
   6
   7 /**
   8         Properties to check:
   9         1. At any point, only one thread can acquire the mutex; when any thread
  10                 nlock the mutex, he must have it in his hand.
  11         2. The sequence of the lock is guaranteed, which means there is a queue for
  12                 all the lock operations.
  13         ####
  14         3. Should establish the happens-before relationship between unlock and lock
  15 */
  16
  17 /**
  18         @Begin
  19         @Global_define:
  20                 # The invariant is that the thread that has a guard at the head of the
  21                 # queue should be the one who currently has the lock.
  22
  23                 int __lock_acquired = 0;
  24                 queue<guard*> __lock_waiting_queue;
  25
  26         @Happens-before:
  27                 # Without any specifying, this means the beginning of a successful Unlock()
  28                 # happens before the end of the next successful Lock().
  29                 Unlock -> Lock
  30         @End
  31 */
  32
  33 struct mcs_node {
  34         std::atomic<mcs_node *> next;
  35         std::atomic<int> gate;
  36
  37         mcs_node() {
  38                 next.store(0);
  39                 gate.store(0);
  40         }
  41 };
  42
  43 struct mcs_mutex {
  44 public:
  45         // tail is null when lock is not held
  46         std::atomic<mcs_node *> m_tail;
  47
  48         mcs_mutex() {
  49                 m_tail.store( NULL );
  50         }
  51         ~mcs_mutex() {
  52                 ASSERT( m_tail.load() == NULL );
  53         }
  54
  55         // Each thread will have their own guard.
  56         class guard {
  57         public:
  58                 mcs_mutex * m_t;
  59                 mcs_node    m_node; // node held on the stack
  60
  61                 guard(mcs_mutex * t) : m_t(t) { t->lock(this); }
  62                 ~guard() { m_t->unlock(this); }
  63         };
  64
  65
  66         /**
  67                 @Begin
  68                 # This function will soon enqueue the current guard to the queue to make
  69                 # sure it will get fair lock successfully.
  70                 @Interface: Lock
  71                 @Commit_point_set: Lock_Enqueue_Point
  72                 @Action:
  73                         @Code:
  74                         __lock_waiting_queue.enqueue(I);
  75                 @Post_action:
  76                         __lock_acquired++;
  77                 @Post_check:
  78                         # Make sure when it successfully locks, the lock is not acquired yet
  79                         # and the locking is in a FIFO order
  80                         __lock_acquired == 1 && I == __lock_waiting_queue.peak()
  81                 @End
  82         */
  83         void lock(guard * I) {
  84                 mcs_node * me = &(I->m_node);
  85
  86                 // set up my node :
  87                 // not published yet so relaxed :
  88                 me->next.store(NULL, std::mo_relaxed );
  89                 me->gate.store(1, std::mo_relaxed );
  90
  91                 // publish my node as the new tail :
  92                 mcs_node * pred = m_tail.exchange(me, std::mo_acq_rel);
  93                 /**
  94                         # Once the exchange completes, the thread already claimed the next
  95                         # available slot for the lock
  96                         @Begin
  97                         @Commit_point_check_define: true
  98                         @Label: Lock_Enqueue_Point
  99                         @End
 100                 */
 101                 if ( pred != NULL ) {
 102                         // (*1) race here
 103                         // unlock of pred can see me in the tail before I fill next
 104
 105                         // publish me to previous lock-holder :
 106                         pred->next.store(me, std::mo_release );
 107
 108                         // (*2) pred not touched any more
 109
 110                         // now this is the spin -
 111                         // wait on predecessor setting my flag -
 112                         rl::linear_backoff bo;
 113                         int my_gate = 1;
 114                         while ( (my_gate = me->gate.load(std::mo_acquire)) ) {
 115                                 thrd_yield();
 116                         }
 117                 }
 118         }
 119
 120         /**
 121                 @Begin
 122                 @Interface: Unlock
 123                 @Commit_point_set:
 124                         Unlock = Unlock_Point_Success_1 | Unlock_Point_Success_2
 125                 @Check:
 126                         lock_acquired == 1 && I == lock_waiting_queue.peak()
 127                 @Action:
 128                         @Code:
 129                         lock_acquired--;
 130                         lock_waiting_queue.dequeue();
 131                 @End
 132         */
 133         void unlock(guard * I) {
 134                 mcs_node * me = &(I->m_node);
 135
 136                 mcs_node * next = me->next.load(std::mo_acquire);
 137                 if ( next == NULL )
 138                 {
 139                         mcs_node * tail_was_me = me;
 140                         bool success;
 141                         if ( (success = m_tail.compare_exchange_strong(
 142                                 tail_was_me,NULL,std::mo_acq_rel)) ) {
 143                                 /**
 144                                         @Begin
 145                                         @Commit_point_check_define: __ATOMIC_RET__ == true
 146                                         @Label: Unlock_Point_Success_1
 147                                         @End
 148                                 */
 149                                 // got null in tail, mutex is unlocked
 150                                 return;
 151                         }
 152
 153                         // (*1) catch the race :
 154                         rl::linear_backoff bo;
 155                         for(;;) {
 156                                 next = me->next.load(std::mo_acquire);
 157                                 if ( next != NULL )
 158                                         break;
 159                                 thrd_yield();
 160                         }
 161                 }
 162
 163                 // (*2) - store to next must be done,
 164                 //  so no locker can be viewing my node any more
 165
 166                 // let next guy in :
 167                 next->gate.store( 0, std::mo_release );
 168                 /**
 169                         @Begin
 170                         @Commit_point_check_define: true
 171                         @Label: Unlock_Point_Success_2
 172                         @End
 173                 */
 174         }
 175 };