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