clang/test/mcs-lock_unannotated.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         mcs_node * next;
  10         int gate;
  11
  12         mcs_node() {
  13                 store_64(&next, 0);
  14                 store_32(&gate, 0);
  15         }
  16 };
  17
  18 struct mcs_mutex {
  19 public:
  20         // tail is null when lock is not held
  21         mcs_node * m_tail;
  22
  23         mcs_mutex() {
  24                 store_64(&m_tail, (uint64_t)NULL);
  25         }
  26         ~mcs_mutex() {
  27                 // ASSERT( m_tail.load() == NULL );
  28         }
  29
  30         class guard {
  31         public:
  32                 mcs_mutex * m_t;
  33                 mcs_node    m_node; // node held on the stack
  34
  35                 guard(mcs_mutex * t) : m_t(t) { t->lock(this); }
  36                 ~guard() { m_t->unlock(this); }
  37         };
  38
  39         void lock(guard * I) {
  40                 mcs_node * me = &(I->m_node);
  41
  42                 // set up my node :
  43                 // not published yet so relaxed :
  44                 store_64(&me->next, (uint64_t)NULL);
  45                 store_32(&me->gate, 1);
  46
  47                 // publish my node as the new tail :
  48                 // mcs_node * pred = m_tail.exchange(me, std::mo_acq_rel);
  49                 mcs_node * pred = (mcs_node *)rmw_64(EXC, &m_tail, (uint64_t) me, (uint64_t) NULL);
  50                 if ( pred != NULL ) {
  51                         // (*1) race here
  52                         // unlock of pred can see me in the tail before I fill next
  53
  54                         // publish me to previous lock-holder :
  55                         store_64(&pred->next, (uint64_t)me);
  56
  57                         // (*2) pred not touched any more
  58
  59                         // now this is the spin -
  60                         // wait on predecessor setting my flag -
  61                         while ( true ) {
  62                                 if (!load_32(&me->gate)) {
  63                                         break;
  64                                 } else {
  65                                         ;
  66                                 }
  67                                 thrd_yield();
  68                         }
  69                 }
  70         }
  71
  72         void unlock(guard * I) {
  73                 mcs_node * me = &(I->m_node);
  74
  75                 mcs_node * next = (mcs_node *)load_64(&me->next);
  76                 if ( next == NULL )
  77                 {
  78                         mcs_node * tail_was_me = me;
  79                         //if ( m_tail.compare_exchange_strong( tail_was_me,NULL,std::mo_acq_rel) ) {
  80                         if (rmw_64(CAS, &m_tail, (uint64_t)tail_was_me, (uint64_t)NULL)) {
  81                                 // got null in tail, mutex is unlocked
  82                                 return;
  83                         }
  84
  85                         // (*1) catch the race :
  86                         while(true) {
  87                                 next = (mcs_node *)load_64(&me->next);
  88                                 if ( next != NULL ) {
  89                                         break;
  90                                 } else {
  91                                         ;
  92                                 }
  93                                 thrd_yield();
  94                         }
  95                 }
  96
  97                 // (*2) - store to next must be done,
  98                 //  so no locker can be viewing my node any more
  99
 100                 // let next guy in :
 101         store_32(&next->gate, 0);
 102         }
 103 };
 104
 105 struct mcs_mutex *mutex;
 106 static uint32_t shared;
 107
 108 void threadA(void *arg)
 109 {
 110         mcs_mutex::guard g(mutex);
 111         printf("store: %d\n", 17);
 112         store_32(&shared, 17);
 113         mutex->unlock(&g);
 114         mutex->lock(&g);
 115         printf("load: %u\n", load_32(&shared));
 116 }
 117
 118 void threadB(void *arg)
 119 {
 120         mcs_mutex::guard g(mutex);
 121         printf("load: %u\n", load_32(&shared));
 122         mutex->unlock(&g);
 123         mutex->lock(&g);
 124         printf("store: %d\n", 17);
 125         store_32(&shared, 17);
 126 }
 127
 128 int user_main(int argc, char **argv)
 129 {
 130         thrd_t A; thrd_t B;
 131
 132         mutex = new mcs_mutex();
 133
 134         thrd_create(&A, &threadA, NULL);
 135         thrd_create(&B, &threadB, NULL);
 136         thrd_join(A);
 137         thrd_join(B);
 138         return 0;
 139 }