test/mcs-lock.cc

   1 #include <stdio.h>
   2 #include <threads.h>
   3
   4 #include "libinterface.h"
   5
   6 // mcs on stack
   7
   8 struct mcs_node {
   9         MCID _mnext; mcs_node * next;
  10         int gate;
  11
  12         mcs_node() {
  13                 MC2_nextOpStore(MCID_NODEP, MCID_NODEP);
  14                 store_64(&next, 0);
  15                 MC2_nextOpStore(MCID_NODEP, MCID_NODEP);
  16                 store_32(&gate, 0);
  17         }
  18 };
  19
  20 struct mcs_mutex {
  21 public:
  22         // tail is null when lock is not held
  23         mcs_node * m_tail;
  24
  25         mcs_mutex() {
  26                 MC2_nextOpStore(MCID_NODEP, MCID_NODEP);
  27                 store_64(&m_tail, (uint64_t)NULL);
  28         }
  29         ~mcs_mutex() {
  30                 // ASSERT( m_tail.load() == NULL );
  31         }
  32
  33         class guard {
  34         public:
  35                 mcs_mutex * m_t;
  36                 mcs_node    m_node; // node held on the stack
  37
  38                 guard(MCID _mt, mcs_mutex * t) : m_t(t) { t->lock(MCID_NODEP, this); }
  39                 ~guard() { m_t->unlock(MCID_NODEP, this); }
  40         };
  41
  42         void lock(MCID _mI, guard * I) {
  43                 MCID _mme; mcs_node * me = &(I->m_node);
  44
  45                 // set up my node :
  46                 // not published yet so relaxed :
  47
  48                 void * _p0 = &me->next;
  49                 MCID _fn0 = MC2_function(1, MC2_PTR_LENGTH, (uint64_t)_p0, (uint64_t)_mme); MC2_nextOpStore(_fn0, MCID_NODEP);
  50                 store_64(_p0, (uint64_t)NULL);
  51
  52                 void * _p1 = &me->gate;
  53                 MCID _fn1 = MC2_function(1, MC2_PTR_LENGTH, (uint64_t)_p1, (uint64_t)_mme); MC2_nextOpStore(_fn1, MCID_NODEP);
  54                 store_32(_p1, 1);
  55
  56                 // publish my node as the new tail :
  57                 // mcs_node * pred = m_tail.exchange(me, std::mo_acq_rel);
  58                 MCID _rmw0 = MC2_nextRMW(MCID_NODEP, _mme, MCID_NODEP);
  59                 MCID _mpred; mcs_node * pred = (mcs_node *)rmw_64(EXC, &m_tail, (uint64_t) me, (uint64_t) NULL);
  60                 MCID _br0;
  61                 if ( pred != NULL ) {
  62                         // (*1) race here
  63                         // unlock of pred can see me in the tail before I fill next
  64
  65                         // publish me to previous lock-holder :
  66                         _br0 = MC2_branchUsesID(_rmw0, 1, 2, true);
  67
  68                         void * _p2 = &pred->next;
  69                         MCID _fn2 = MC2_function(1, MC2_PTR_LENGTH, (uint64_t)_p2, (uint64_t)_mpred); MC2_nextOpStore(_fn2, _mme);
  70                         store_64(_p2, (uint64_t)me);
  71
  72                         // (*2) pred not touched any more
  73
  74                         // now this is the spin -
  75                         // wait on predecessor setting my flag -
  76                         MC2_enterLoop();
  77                         while ( true ) {
  78                                 MCID _br1;
  79                                 void * _p99 = &me->gate;
  80                                 MCID _fn99 = MC2_function(1, MC2_PTR_LENGTH, (uint64_t)_p99, (uint64_t)_mme); MC2_nextOpLoad(_fn99);
  81                                 int c88 = !load_32(_p99);
  82                                 MCID _fn88 = MC2_function(1, MC2_PTR_LENGTH, c88, _p99);
  83                                 if (c88) {
  84                                         _br1 = MC2_branchUsesID(_fn88, 1, 2, true);
  85                                         break;
  86                                 } else {
  87                                         _br1 = MC2_branchUsesID(_fn88, 0, 2, true);
  88                                         ;
  89                                         MC2_merge(_br1);
  90                                 }
  91                                 thrd_yield();
  92                         }
  93 MC2_exitLoop();
  94
  95                         MC2_merge(_br0);
  96                 } else { _br0 = MC2_branchUsesID(_rmw0, 0, 2, true);    MC2_merge(_br0);
  97                  }
  98         }
  99
 100         void unlock(MCID _mI, guard * I) {
 101                 MCID _mme; mcs_node * me;
 102                 me = &(I->m_node);
 103
 104                 MCID _fn6;
 105                 void * _p3 = &me->next;
 106                 MCID _mnext; MCID _fn3 = MC2_function(1, MC2_PTR_LENGTH, (uint64_t)_p3, _mme); _mnext=MC2_nextOpLoad(_fn3); mcs_node * next = (mcs_node *)load_64(_p3);
 107                 MCID _br2;
 108                 if ( next == NULL )
 109                 {
 110                         _br2 = MC2_branchUsesID(_mnext, 1, 2, true);
 111                         mcs_node * tail_was_me = me;
 112                         //if ( m_tail.compare_exchange_strong( tail_was_me,NULL,std::mo_acq_rel) ) {
 113                         MCID _br3;
 114                         MCID _rmw77 = MC2_nextRMW(MCID_NODEP, MCID_NODEP, MCID_NODEP);
 115                         if (rmw_64(CAS, &m_tail, (uint64_t)tail_was_me, (uint64_t)NULL)) {
 116                                 // got null in tail, mutex is unlocked
 117                                 _br3 = MC2_branchUsesID(_rmw77, 1, 2, true);
 118                                 return;
 119                         } else { _br3 = MC2_branchUsesID(_rmw77, 0, 2, true);   MC2_merge(_br3);
 120                          }
 121
 122                         // (*1) catch the race :
 123                         MC2_enterLoop();
 124                         while(true) {
 125
 126                                 void * _p4 = &me->next;
 127                                 MCID _fn4 = MC2_function(1, MC2_PTR_LENGTH, (uint64_t)_p4, _mme); _fn6=MC2_nextOpLoad(_fn4), next = (mcs_node *)load_64(_p4);
 128                                 _fn6 = MC2_function(1, sizeof (next), (uint64_t)next, (uint64_t)_fn6);
 129                                 MCID _br4;
 130                                 if ( next != NULL ) {
 131                                         _br4 = MC2_branchUsesID(_fn6, 1, 2, true);
 132                                         break;
 133                                 } else {
 134                                         _br4 = MC2_branchUsesID(_fn6, 0, 2, true);
 135                                         ;
 136                                         MC2_merge(_br4);
 137                                 }
 138                                 thrd_yield();
 139                         }
 140 MC2_exitLoop();
 141
 142                         MC2_merge(_br2);
 143                 } else { _br2 = MC2_branchUsesID(_mnext, 0, 2, true);   MC2_merge(_br2);
 144                  }
 145
 146                 // (*2) - store to next must be done,
 147                 //  so no locker can be viewing my node any more
 148
 149                 // let next guy in :
 150
 151         void * _p5 = &next->gate;
 152         MCID _fn5 = MC2_function(1, MC2_PTR_LENGTH, (uint64_t)_p5, _fn6); MC2_nextOpStore(_fn5, MCID_NODEP);
 153         store_32(_p5, 0);
 154         }
 155 };
 156
 157 struct mcs_mutex *mutex;
 158 static uint32_t shared;
 159
 160 void threadA(void *arg)
 161 {
 162         mcs_mutex::guard g(MCID_NODEP, mutex);
 163         printf("store: %d\n", 17);
 164         MC2_nextOpStore(MCID_NODEP, MCID_NODEP);
 165         store_32(&shared, 17);
 166         mutex->unlock(MCID_NODEP, &g);
 167         mutex->lock(MCID_NODEP, &g);
 168         printf("load: %u\n", load_32(&shared));
 169 }
 170
 171 void threadB(void *arg)
 172 {
 173         mcs_mutex::guard g(MCID_NODEP, mutex);
 174         printf("load: %u\n", load_32(&shared));
 175         mutex->unlock(MCID_NODEP, &g);
 176         mutex->lock(MCID_NODEP, &g);
 177         printf("store: %d\n", 17);
 178         MC2_nextOpStore(MCID_NODEP, MCID_NODEP);
 179         store_32(&shared, 17);
 180 }
 181
 182 int user_main(int argc, char **argv)
 183 {
 184         thrd_t A; thrd_t B;
 185
 186         mutex = new mcs_mutex();
 187
 188         thrd_create(&A, &threadA, NULL);
 189         thrd_create(&B, &threadB, NULL);
 190         thrd_join(A);
 191         thrd_join(B);
 192         return 0;
 193 }