1//===-- Utility condition variable class ------------------------*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#ifndef LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H
10#define LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H
11
12#include "src/__support/CPP/atomic.h"
13#include "src/__support/OSUtil/syscall.h" // For syscall functions.
14#include "src/__support/threads/linux/futex_word.h"
15#include "src/__support/threads/mutex.h"
16
17#include <linux/futex.h> // For futex operations.
18#include <stdint.h>
19#include <sys/syscall.h> // For syscall numbers.
20#include <threads.h> // For values like thrd_success etc.
21
22namespace LIBC_NAMESPACE {
23
24struct CndVar {
25 enum CndWaiterStatus : uint32_t {
26 WS_Waiting = 0xE,
27 WS_Signalled = 0x5,
28 };
29
30 struct CndWaiter {
31 cpp::Atomic<uint32_t> futex_word = WS_Waiting;
32 CndWaiter *next = nullptr;
33 };
34
35 CndWaiter *waitq_front;
36 CndWaiter *waitq_back;
37 Mutex qmtx;
38
39 static int init(CndVar *cv) {
40 cv->waitq_front = cv->waitq_back = nullptr;
41 auto err = Mutex::init(mutex: &cv->qmtx, istimed: false, isrecur: false, isrobust: false);
42 return err == MutexError::NONE ? thrd_success : thrd_error;
43 }
44
45 static void destroy(CndVar *cv) {
46 cv->waitq_front = cv->waitq_back = nullptr;
47 }
48
49 int wait(Mutex *m) {
50 // The goal is to perform "unlock |m| and wait" in an
51 // atomic operation. However, it is not possible to do it
52 // in the true sense so we do it in spirit. Before unlocking
53 // |m|, a new waiter object is added to the waiter queue with
54 // the waiter queue locked. Iff a signalling thread signals
55 // the waiter before the waiter actually starts waiting, the
56 // wait operation will not begin at all and the waiter immediately
57 // returns.
58
59 CndWaiter waiter;
60 {
61 MutexLock ml(&qmtx);
62 CndWaiter *old_back = nullptr;
63 if (waitq_front == nullptr) {
64 waitq_front = waitq_back = &waiter;
65 } else {
66 old_back = waitq_back;
67 waitq_back->next = &waiter;
68 waitq_back = &waiter;
69 }
70
71 if (m->unlock() != MutexError::NONE) {
72 // If we do not remove the queued up waiter before returning,
73 // then another thread can potentially signal a non-existing
74 // waiter. Note also that we do this with |qmtx| locked. This
75 // ensures that another thread will not signal the withdrawing
76 // waiter.
77 waitq_back = old_back;
78 if (waitq_back == nullptr)
79 waitq_front = nullptr;
80 else
81 waitq_back->next = nullptr;
82
83 return thrd_error;
84 }
85 }
86
87 LIBC_NAMESPACE::syscall_impl<long>(number: FUTEX_SYSCALL_ID, ts: &waiter.futex_word.val,
88 FUTEX_WAIT, ts: WS_Waiting, ts: 0, ts: 0, ts: 0);
89
90 // At this point, if locking |m| fails, we can simply return as the
91 // queued up waiter would have been removed from the queue.
92 auto err = m->lock();
93 return err == MutexError::NONE ? thrd_success : thrd_error;
94 }
95
96 int notify_one() {
97 // We don't use an RAII locker in this method as we want to unlock
98 // |qmtx| and signal the waiter using a single FUTEX_WAKE_OP signal.
99 qmtx.lock();
100 if (waitq_front == nullptr) {
101 qmtx.unlock();
102 return thrd_success;
103 }
104
105 CndWaiter *first = waitq_front;
106 waitq_front = waitq_front->next;
107 if (waitq_front == nullptr)
108 waitq_back = nullptr;
109
110 qmtx.futex_word = FutexWordType(Mutex::LockState::Free);
111
112 LIBC_NAMESPACE::syscall_impl<long>(
113 number: FUTEX_SYSCALL_ID, ts: &qmtx.futex_word.val, FUTEX_WAKE_OP, ts: 1, ts: 1,
114 ts: &first->futex_word.val,
115 FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting));
116 return thrd_success;
117 }
118
119 int broadcast() {
120 MutexLock ml(&qmtx);
121 uint32_t dummy_futex_word;
122 CndWaiter *waiter = waitq_front;
123 waitq_front = waitq_back = nullptr;
124 while (waiter != nullptr) {
125 // FUTEX_WAKE_OP is used instead of just FUTEX_WAKE as it allows us to
126 // atomically update the waiter status to WS_Signalled before waking
127 // up the waiter. A dummy location is used for the other futex of
128 // FUTEX_WAKE_OP.
129 LIBC_NAMESPACE::syscall_impl<long>(
130 number: FUTEX_SYSCALL_ID, ts: &dummy_futex_word, FUTEX_WAKE_OP, ts: 1, ts: 1,
131 ts: &waiter->futex_word.val,
132 FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting));
133 waiter = waiter->next;
134 }
135 return thrd_success;
136 }
137};
138
139static_assert(sizeof(CndVar) == sizeof(cnd_t),
140 "Mismatch in the size of the "
141 "internal representation of condition variable and the public "
142 "cnd_t type.");
143
144} // namespace LIBC_NAMESPACE
145
146#endif // LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H
147

source code of libc/src/threads/linux/CndVar.h