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 "include/sys/syscall.h" // For syscall numbers.
13 #include "include/threads.h"     // For values like thrd_success etc.
14 #include "src/__support/CPP/atomic.h"
15 #include "src/__support/OSUtil/syscall.h" // For syscall functions.
16 #include "src/__support/threads/linux/futex_word.h"
17 #include "src/__support/threads/mutex.h"
18 
19 #include <linux/futex.h> // For futex operations.
20 #include <stdint.h>
21 
22 namespace __llvm_libc {
23 
24 struct 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 
initCndVar39   static int init(CndVar *cv) {
40     cv->waitq_front = cv->waitq_back = nullptr;
41     auto err = Mutex::init(&cv->qmtx, false, false, false);
42     return err == MutexError::NONE ? thrd_success : thrd_error;
43   }
44 
destroyCndVar45   static void destroy(CndVar *cv) {
46     cv->waitq_front = cv->waitq_back = nullptr;
47   }
48 
waitCndVar49   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     __llvm_libc::syscall(SYS_futex, &waiter.futex_word.val, FUTEX_WAIT,
88                          WS_Waiting, 0, 0, 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 
notify_oneCndVar96   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     __llvm_libc::syscall(
113         SYS_futex, &qmtx.futex_word.val, FUTEX_WAKE_OP, 1, 1,
114         &first->futex_word.val,
115         FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting));
116     return thrd_success;
117   }
118 
broadcastCndVar119   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       __llvm_libc::syscall(
130           SYS_futex, &dummy_futex_word, FUTEX_WAKE_OP, 1, 1,
131           &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 
139 static_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 __llvm_libc
145 
146 #endif // LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H
147