Reorgs added benchmarks (put them in misc folder)
[libcds.git] / cds / misc / mcs-lock.h
1 #ifndef _MCS_LOCK_H
2 #define _MCS_LOCK_H
3
4 #include "backoff.h"
5 #include <atomic>
6 #include <cds/algo/backoff_strategy.h>
7 #include <thread>
8
9 namespace cds_others {
10
11 size_t BackoffTraits::lower_bound = 16;
12 size_t BackoffTraits::upper_bound = 1024;
13
14 // Forward declaration
15 struct mcs_node;
16 struct mcs_mutex;
17
18 struct mcs_node {
19   std::atomic<mcs_node *> next;
20   std::atomic<int> gate;
21
22   mcs_node() {
23     next.store(0);
24     gate.store(0);
25   }
26 };
27
28 struct mcs_mutex {
29 public:
30   // tail is null when lock is not held
31   std::atomic<mcs_node *> m_tail;
32
33   mcs_mutex() { m_tail.store(nullptr); }
34   ~mcs_mutex() { assert(m_tail.load() == nullptr); }
35
36   class guard {
37   public:
38     mcs_mutex *m_t;
39     mcs_node m_node; // node held on the stack
40
41     // Call the wrapper (instrument every lock/unlock)
42     guard(mcs_mutex *t) : m_t(t) { t->lock(this); }
43     ~guard() { m_t->unlock(this); }
44   };
45
46   void lock(guard *I) {
47     mcs_node *me = &(I->m_node);
48
49     // set up my node :
50     // not published yet so relaxed :
51     me->next.store(nullptr, std::memory_order_relaxed);
52     me->gate.store(1, std::memory_order_relaxed);
53
54     // publish my node as the new tail :
55     mcs_node *pred = m_tail.exchange(me, std::memory_order_acq_rel);
56     if (pred != nullptr) {
57       // (*1) race here
58       // unlock of pred can see me in the tail before I fill next
59
60       // If this is relaxed, the store 0 to gate will be read before and
61       // that lock will never ends.
62       // publish me to previous lock-holder :
63       pred->next.store(me, std::memory_order_release);
64
65       // (*2) pred not touched any more
66
67       // now this is the spin -
68       // wait on predecessor setting my flag -
69       ExpBackoff backoff;
70       while (me->gate.load(std::memory_order_acquire)) {
71         backoff();
72       }
73     }
74   }
75
76   void unlock(guard *I) {
77     mcs_node *me = &(I->m_node);
78     mcs_node *next = me->next.load(std::memory_order_acquire);
79     if (next == nullptr) {
80       mcs_node *tail_was_me = me;
81
82       // This was mo_acq_rel, which is stronger than necessary
83       if (m_tail.compare_exchange_strong(tail_was_me, nullptr,
84                                          std::memory_order_release)) {
85         // got null in tail, mutex is unlocked
86         return;
87       }
88
89       // (*1) catch the race :
90       ExpBackoff backoff;
91       for (;;) {
92         next = me->next.load(std::memory_order_acquire);
93         if (next != nullptr)
94           break;
95         backoff();
96       }
97     }
98
99     // (*2) - store to next must be done,
100     //  so no locker can be viewing my node any more
101
102     next->gate.store(0, std::memory_order_release);
103   }
104 };
105
106 } // namespace cds_others
107
108 #endif