minor fix
[cdsspec-compiler.git] / 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 };