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 "Futex.h"
13 #include "Mutex.h"
14 
15 #include "config/linux/syscall.h" // For syscall functions.
16 #include "include/sys/syscall.h"  // For syscall numbers.
17 #include "include/threads.h"      // For values like thrd_success etc.
18 
19 #include <linux/futex.h> // For futex operations.
20 #include <stdatomic.h>   // For atomic operations
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     FutexWord 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     return Mutex::init(&cv->qmtx, mtx_plain);
42   }
43 
44   static void destroy(CndVar *cv) {
45     cv->waitq_front = cv->waitq_back = nullptr;
46   }
47 
48   int wait(Mutex *m) {
49     // The goal is to perform "unlock |m| and wait" in an
50     // atomic operation. However, it is not possible to do it
51     // in the true sense so we do it in spirit. Before unlocking
52     // |m|, a new waiter object is added to the waiter queue with
53     // the waiter queue locked. Iff a signalling thread signals
54     // the waiter before the waiter actually starts waiting, the
55     // wait operation will not begin at all and the waiter immediately
56     // returns.
57 
58     CndWaiter waiter;
59     {
60       MutexLock ml(&qmtx);
61       CndWaiter *old_back = nullptr;
62       if (waitq_front == nullptr) {
63         waitq_front = waitq_back = &waiter;
64       } else {
65         old_back = waitq_back;
66         waitq_back->next = &waiter;
67         waitq_back = &waiter;
68       }
69 
70       if (m->unlock() != thrd_success) {
71         // If we do not remove the queued up waiter before returning,
72         // then another thread can potentially signal a non-existing
73         // waiter. Note also that we do this with |qmtx| locked. This
74         // ensures that another thread will not signal the withdrawing
75         // waiter.
76         waitq_back = old_back;
77         if (waitq_back == nullptr)
78           waitq_front = nullptr;
79         else
80           waitq_back->next = nullptr;
81 
82         return thrd_error;
83       }
84     }
85 
86     __llvm_libc::syscall(SYS_futex, &waiter.futex_word, FUTEX_WAIT, WS_Waiting,
87                          0, 0, 0);
88 
89     // At this point, if locking |m| fails, we can simply return as the
90     // queued up waiter would have been removed from the queue.
91     return m->lock();
92   }
93 
94   int notify_one() {
95     // We don't use an RAII locker in this method as we want to unlock
96     // |qmtx| and signal the waiter using a single FUTEX_WAKE_OP signal.
97     qmtx.lock();
98     if (waitq_front == nullptr) {
99       qmtx.unlock();
100       return thrd_success;
101     }
102 
103     CndWaiter *first = waitq_front;
104     waitq_front = waitq_front->next;
105     if (waitq_front == nullptr)
106       waitq_back = nullptr;
107 
108     atomic_store(&qmtx.futex_word, Mutex::MS_Free);
109 
110     __llvm_libc::syscall(
111         SYS_futex, &qmtx.futex_word, FUTEX_WAKE_OP, 1, 1, &first->futex_word,
112         FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting));
113     return thrd_success;
114   }
115 
116   int broadcast() {
117     MutexLock ml(&qmtx);
118     FutexWord dummy_futex_word;
119     CndWaiter *waiter = waitq_front;
120     waitq_front = waitq_back = nullptr;
121     while (waiter != nullptr) {
122       // FUTEX_WAKE_OP is used instead of just FUTEX_WAKE as it allows us to
123       // atomically update the waiter status to WS_Signalled before waking
124       // up the waiter. A dummy location is used for the other futex of
125       // FUTEX_WAKE_OP.
126       __llvm_libc::syscall(
127           SYS_futex, &dummy_futex_word, FUTEX_WAKE_OP, 1, 1,
128           &waiter->futex_word,
129           FUTEX_OP(FUTEX_OP_SET, WS_Signalled, FUTEX_OP_CMP_EQ, WS_Waiting));
130       waiter = waiter->next;
131     }
132     return thrd_success;
133   }
134 };
135 
136 static_assert(sizeof(CndVar) == sizeof(cnd_t),
137               "Mismatch in the size of the "
138               "internal representation of condition variable and the public "
139               "cnd_t type.");
140 
141 } // namespace __llvm_libc
142 
143 #endif // LLVM_LIBC_SRC_THREADS_LINUX_CNDVAR_H
144