1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
|
#pragma once
#include <util/system/rwlock.h>
#include <util/system/sanitizers.h>
#if defined(_linux_)
/* TLightRWLock is optimized for read lock and very fast lock/unlock switching.
Read lock increments counter.
Write lock sets highest bit of counter (makes counter negative).
Whenever a thread tries to acquire read lock that thread increments
the counter. If the thread gets negative value of the counter right just
after the increment that means write lock was acquired in another thread.
In that case the thread decrements the counter back, wakes one thread on
UnshareFutex, waits on the TrappedFutex and then tries acquire read lock
from the beginning.
If the thread gets positive value of the counter after the increment
then read lock was successfully acquired and
the thread can proceed execution.
Whenever a thread tries to acquire write lock that thread set the highest bit
of the counter. If the thread determine that the bit was set previously then
write lock was acquired in another thread. In that case the thread waits on
the TrappedFutex and then tries again from the beginning.
If the highest bit was successfully set then thread check if any read lock
exists at the moment. If so the thread waits on UnshareFutex. If there is
no more read locks then write lock was successfully acquired and the thread
can proceed execution.
*/
#include <linux/futex.h>
#include <unistd.h>
#include <sys/syscall.h>
#include <errno.h>
namespace NS_LightRWLock {
static int Y_FORCE_INLINE AtomicFetchAdd(volatile int& item, int value) {
return __atomic_fetch_add(&item, value, __ATOMIC_SEQ_CST);
}
#if defined(_x86_64_) || defined(_i386_)
static char Y_FORCE_INLINE AtomicSetBit(volatile int& item, unsigned bit) {
char ret;
__asm__ __volatile__(
"lock bts %2,%0\n"
"setc %1\n"
: "+m"(item), "=rm"(ret)
: "r"(bit)
: "cc");
// msan doesn't treat ret as initialized
NSan::Unpoison(&ret, sizeof(ret));
return ret;
}
static char Y_FORCE_INLINE AtomicClearBit(volatile int& item, unsigned bit) {
char ret;
__asm__ __volatile__(
"lock btc %2,%0\n"
"setc %1\n"
: "+m"(item), "=rm"(ret)
: "r"(bit)
: "cc");
// msan doesn't treat ret as initialized
NSan::Unpoison(&ret, sizeof(ret));
return ret;
}
#else
static char Y_FORCE_INLINE AtomicSetBit(volatile int& item, unsigned bit) {
int prev = __atomic_fetch_or(&item, 1 << bit, __ATOMIC_SEQ_CST);
return (prev & (1 << bit)) != 0 ? 1 : 0;
}
static char Y_FORCE_INLINE
AtomicClearBit(volatile int& item, unsigned bit) {
int prev = __atomic_fetch_and(&item, ~(1 << bit), __ATOMIC_SEQ_CST);
return (prev & (1 << bit)) != 0 ? 1 : 0;
}
#endif
#if defined(_x86_64_) || defined(_i386_) || defined (__aarch64__) || defined (__arm__) || defined (__powerpc64__)
static bool AtomicLockHighByte(volatile int& item) {
union TA {
int x;
char y[4];
};
volatile TA* ptr = reinterpret_cast<volatile TA*>(&item);
char zero = 0;
return __atomic_compare_exchange_n(&(ptr->y[3]), &zero, (char)128, true,
__ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
}
#endif
template <typename TInt>
static void Y_FORCE_INLINE AtomicStore(volatile TInt& var, TInt value) {
__atomic_store_n(&var, value, __ATOMIC_RELEASE);
}
template <typename TInt>
static void Y_FORCE_INLINE SequenceStore(volatile TInt& var, TInt value) {
__atomic_store_n(&var, value, __ATOMIC_SEQ_CST);
}
template <typename TInt>
static TInt Y_FORCE_INLINE AtomicLoad(const volatile TInt& var) {
return __atomic_load_n(&var, __ATOMIC_ACQUIRE);
}
static void Y_FORCE_INLINE FutexWait(volatile int& fvar, int value) {
for (;;) {
int result =
syscall(SYS_futex, &fvar, FUTEX_WAIT_PRIVATE, value, NULL, NULL, 0);
if (Y_UNLIKELY(result == -1)) {
if (errno == EWOULDBLOCK)
return;
if (errno == EINTR)
continue;
Y_FAIL("futex error");
}
}
}
static void Y_FORCE_INLINE FutexWake(volatile int& fvar, int amount) {
const int result =
syscall(SYS_futex, &fvar, FUTEX_WAKE_PRIVATE, amount, NULL, NULL, 0);
if (Y_UNLIKELY(result == -1))
Y_FAIL("futex error");
}
}
class alignas(64) TLightRWLock {
public:
TLightRWLock(ui32 spinCount = 10)
: Counter_(0)
, TrappedFutex_(0)
, UnshareFutex_(0)
, SpinCount_(spinCount)
{
}
TLightRWLock(const TLightRWLock&) = delete;
void operator=(const TLightRWLock&) = delete;
Y_FORCE_INLINE void AcquireWrite() {
using namespace NS_LightRWLock;
if (AtomicLockHighByte(Counter_)) {
if ((AtomicLoad(Counter_) & 0x7FFFFFFF) == 0)
return;
return WaitForUntrappedShared();
}
WaitForExclusiveAndUntrappedShared();
}
Y_FORCE_INLINE void AcquireRead() {
using namespace NS_LightRWLock;
if (Y_LIKELY(AtomicFetchAdd(Counter_, 1) >= 0))
return;
WaitForUntrappedAndAcquireRead();
}
Y_FORCE_INLINE void ReleaseWrite() {
using namespace NS_LightRWLock;
AtomicClearBit(Counter_, 31);
if (AtomicLoad(TrappedFutex_)) {
SequenceStore(TrappedFutex_, 0);
FutexWake(TrappedFutex_, 0x7fffffff);
}
}
Y_FORCE_INLINE void ReleaseRead() {
using namespace NS_LightRWLock;
if (Y_LIKELY(AtomicFetchAdd(Counter_, -1) >= 0))
return;
if (!AtomicLoad(UnshareFutex_))
return;
if ((AtomicLoad(Counter_) & 0x7fffffff) == 0) {
SequenceStore(UnshareFutex_, 0);
FutexWake(UnshareFutex_, 1);
}
}
private:
volatile int Counter_;
volatile int TrappedFutex_;
volatile int UnshareFutex_;
const ui32 SpinCount_;
void WaitForUntrappedShared();
void WaitForExclusiveAndUntrappedShared();
void WaitForUntrappedAndAcquireRead();
};
#else
class TLightRWLock: public TRWMutex {
public:
TLightRWLock() {
}
TLightRWLock(ui32) {
}
};
#endif
using TLightReadGuard = TReadGuardBase<TLightRWLock>;
using TLightWriteGuard = TWriteGuardBase<TLightRWLock>;
|
