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
|
//===-- Utility condition variable class ------------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H
#define LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H
#include "Futex.h"
#include "Mutex.h"
#include "config/linux/syscall.h" // For syscall functions.
#include "include/sys/syscall.h" // For syscall numbers.
#include "include/threads.h" // For values like thrd_success etc.
#include <linux/futex.h> // For futex operations.
#include <stdatomic.h> // For atomic operations
namespace __llvm_libc {
struct CndVar {
enum CndWaiterStatus : uint32_t {
WS_Waiting = 0xE,
WS_Signalled = 0x5,
};
struct CndWaiter {
FutexWord futex_word = WS_Waiting;
CndWaiter *next = nullptr;
};
CndWaiter *waitq_front;
CndWaiter *waitq_back;
Mutex qmtx;
static int init(CndVar *cv) {
cv->waitq_front = cv->waitq_back = nullptr;
return Mutex::init(&cv->qmtx, mtx_plain);
}
static void destroy(CndVar *cv) {
cv->waitq_front = cv->waitq_back = nullptr;
}
int wait(Mutex *m) {
// The goal is to perform "unlock |m| and wait" in an
// atomic operation. However, it is not possible to do it
// in the true sense so we do it in spirit. Before unlocking
// |m|, a new waiter object is added to the waiter queue with
// the waiter queue locked. Iff a signalling thread signals
// the waiter before the waiter actually starts waiting, the
// wait operation will not begin at all and the waiter immediately
// returns.
CndWaiter waiter;
{
MutexLock ml(&qmtx);
CndWaiter *old_back = nullptr;
if (waitq_front == nullptr) {
waitq_front = waitq_back = &waiter;
} else {
old_back = waitq_back;
waitq_back->next = &waiter;
waitq_back = &waiter;
}
if (m->unlock() != thrd_success) {
// If we do not remove the queued up waiter before returning,
// then another thread can potentially signal a non-existing
// waiter. Note also that we do this with |qmtx| locked. This
// ensures that another thread will not signal the withdrawing
// waiter.
waitq_back = old_back;
if (waitq_back == nullptr)
waitq_front = nullptr;
else
waitq_back->next = nullptr;
return thrd_error;
}
}
__llvm_libc::syscall(SYS_futex, &waiter.futex_word, FUTEX_WAIT, WS_Waiting,
0, 0, 0);
// At this point, if locking |m| fails, we can simply return as the
// queued up waiter would have been removed from the queue.
return m->lock();
}
int notify_one() {
// We don't use an RAII locker in this method as we want to unlock
// |qmtx| and signal the waiter using a single FUTEX_WAKE_OP signal.
qmtx.lock();
if (waitq_front == nullptr) {
qmtx.unlock();
return thrd_success;
}
CndWaiter *first = waitq_front;
waitq_front = waitq_front->next;
if (waitq_front == nullptr)
waitq_back = nullptr;
atomic_store(&qmtx.futex_word, Mutex::MS_Free);
__llvm_libc::syscall(
SYS_futex, &qmtx.futex_word, FUTEX_WAKE_OP, 1, 1, &first->futex_word,
FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting));
return thrd_success;
}
int broadcast() {
MutexLock ml(&qmtx);
FutexWord dummy_futex_word;
CndWaiter *waiter = waitq_front;
waitq_front = waitq_back = nullptr;
while (waiter != nullptr) {
// FUTEX_WAKE_OP is used instead of just FUTEX_WAKE as it allows us to
// atomically update the waiter status to WS_Signalled before waking
// up the waiter. A dummy location is used for the other futex of
// FUTEX_WAKE_OP.
__llvm_libc::syscall(
SYS_futex, &dummy_futex_word, FUTEX_WAKE_OP, 1, 1,
&waiter->futex_word,
FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting));
waiter = waiter->next;
}
return thrd_success;
}
};
static_assert(sizeof(CndVar) == sizeof(cnd_t),
"Mismatch in the size of the "
"internal representation of condition variable and the public "
"cnd_t type.");
} // namespace __llvm_libc
#endif // LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H
|
