1 // Copyright 2015 the V8 project authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "src/futex-emulation.h"
6
7 #include <limits>
8
9 #include "src/base/macros.h"
10 #include "src/base/platform/time.h"
11 #include "src/conversions.h"
12 #include "src/handles-inl.h"
13 #include "src/isolate.h"
14 #include "src/list-inl.h"
15
16 namespace v8 {
17 namespace internal {
18
19 base::LazyMutex FutexEmulation::mutex_ = LAZY_MUTEX_INITIALIZER;
20 base::LazyInstance<FutexWaitList>::type FutexEmulation::wait_list_ =
21 LAZY_INSTANCE_INITIALIZER;
22
23
NotifyWake()24 void FutexWaitListNode::NotifyWake() {
25 // Lock the FutexEmulation mutex before notifying. We know that the mutex
26 // will have been unlocked if we are currently waiting on the condition
27 // variable.
28 //
29 // The mutex may also not be locked if the other thread is currently handling
30 // interrupts, or if FutexEmulation::Wait was just called and the mutex
31 // hasn't been locked yet. In either of those cases, we set the interrupted
32 // flag to true, which will be tested after the mutex is re-locked.
33 base::LockGuard<base::Mutex> lock_guard(FutexEmulation::mutex_.Pointer());
34 if (waiting_) {
35 cond_.NotifyOne();
36 interrupted_ = true;
37 }
38 }
39
40
FutexWaitList()41 FutexWaitList::FutexWaitList() : head_(nullptr), tail_(nullptr) {}
42
43
AddNode(FutexWaitListNode * node)44 void FutexWaitList::AddNode(FutexWaitListNode* node) {
45 DCHECK(node->prev_ == nullptr && node->next_ == nullptr);
46 if (tail_) {
47 tail_->next_ = node;
48 } else {
49 head_ = node;
50 }
51
52 node->prev_ = tail_;
53 node->next_ = nullptr;
54 tail_ = node;
55 }
56
57
RemoveNode(FutexWaitListNode * node)58 void FutexWaitList::RemoveNode(FutexWaitListNode* node) {
59 if (node->prev_) {
60 node->prev_->next_ = node->next_;
61 } else {
62 head_ = node->next_;
63 }
64
65 if (node->next_) {
66 node->next_->prev_ = node->prev_;
67 } else {
68 tail_ = node->prev_;
69 }
70
71 node->prev_ = node->next_ = nullptr;
72 }
73
74
Wait(Isolate * isolate,Handle<JSArrayBuffer> array_buffer,size_t addr,int32_t value,double rel_timeout_ms)75 Object* FutexEmulation::Wait(Isolate* isolate,
76 Handle<JSArrayBuffer> array_buffer, size_t addr,
77 int32_t value, double rel_timeout_ms) {
78 DCHECK(addr < NumberToSize(isolate, array_buffer->byte_length()));
79
80 void* backing_store = array_buffer->backing_store();
81 int32_t* p =
82 reinterpret_cast<int32_t*>(static_cast<int8_t*>(backing_store) + addr);
83
84 base::LockGuard<base::Mutex> lock_guard(mutex_.Pointer());
85
86 if (*p != value) {
87 return Smi::FromInt(Result::kNotEqual);
88 }
89
90 FutexWaitListNode* node = isolate->futex_wait_list_node();
91
92 node->backing_store_ = backing_store;
93 node->wait_addr_ = addr;
94 node->waiting_ = true;
95
96 bool use_timeout = rel_timeout_ms != V8_INFINITY;
97
98 base::TimeDelta rel_timeout;
99 if (use_timeout) {
100 // Convert to nanoseconds.
101 double rel_timeout_ns = rel_timeout_ms *
102 base::Time::kNanosecondsPerMicrosecond *
103 base::Time::kMicrosecondsPerMillisecond;
104 if (rel_timeout_ns >
105 static_cast<double>(std::numeric_limits<int64_t>::max())) {
106 // 2**63 nanoseconds is 292 years. Let's just treat anything greater as
107 // infinite.
108 use_timeout = false;
109 } else {
110 rel_timeout = base::TimeDelta::FromNanoseconds(
111 static_cast<int64_t>(rel_timeout_ns));
112 }
113 }
114
115 base::TimeTicks start_time = base::TimeTicks::Now();
116 base::TimeTicks timeout_time = start_time + rel_timeout;
117 base::TimeTicks current_time = start_time;
118
119 wait_list_.Pointer()->AddNode(node);
120
121 Object* result;
122
123 while (true) {
124 bool interrupted = node->interrupted_;
125 node->interrupted_ = false;
126
127 // Unlock the mutex here to prevent deadlock from lock ordering between
128 // mutex_ and mutexes locked by HandleInterrupts.
129 mutex_.Pointer()->Unlock();
130
131 // Because the mutex is unlocked, we have to be careful about not dropping
132 // an interrupt. The notification can happen in three different places:
133 // 1) Before Wait is called: the notification will be dropped, but
134 // interrupted_ will be set to 1. This will be checked below.
135 // 2) After interrupted has been checked here, but before mutex_ is
136 // acquired: interrupted is checked again below, with mutex_ locked.
137 // Because the wakeup signal also acquires mutex_, we know it will not
138 // be able to notify until mutex_ is released below, when waiting on the
139 // condition variable.
140 // 3) After the mutex is released in the call to WaitFor(): this
141 // notification will wake up the condition variable. node->waiting() will
142 // be false, so we'll loop and then check interrupts.
143 if (interrupted) {
144 Object* interrupt_object = isolate->stack_guard()->HandleInterrupts();
145 if (interrupt_object->IsException(isolate)) {
146 result = interrupt_object;
147 mutex_.Pointer()->Lock();
148 break;
149 }
150 }
151
152 mutex_.Pointer()->Lock();
153
154 if (node->interrupted_) {
155 // An interrupt occured while the mutex_ was unlocked. Don't wait yet.
156 continue;
157 }
158
159 if (!node->waiting_) {
160 result = Smi::FromInt(Result::kOk);
161 break;
162 }
163
164 // No interrupts, now wait.
165 if (use_timeout) {
166 current_time = base::TimeTicks::Now();
167 if (current_time >= timeout_time) {
168 result = Smi::FromInt(Result::kTimedOut);
169 break;
170 }
171
172 base::TimeDelta time_until_timeout = timeout_time - current_time;
173 DCHECK(time_until_timeout.InMicroseconds() >= 0);
174 bool wait_for_result =
175 node->cond_.WaitFor(mutex_.Pointer(), time_until_timeout);
176 USE(wait_for_result);
177 } else {
178 node->cond_.Wait(mutex_.Pointer());
179 }
180
181 // Spurious wakeup, interrupt or timeout.
182 }
183
184 wait_list_.Pointer()->RemoveNode(node);
185 node->waiting_ = false;
186
187 return result;
188 }
189
190
Wake(Isolate * isolate,Handle<JSArrayBuffer> array_buffer,size_t addr,int num_waiters_to_wake)191 Object* FutexEmulation::Wake(Isolate* isolate,
192 Handle<JSArrayBuffer> array_buffer, size_t addr,
193 int num_waiters_to_wake) {
194 DCHECK(addr < NumberToSize(isolate, array_buffer->byte_length()));
195
196 int waiters_woken = 0;
197 void* backing_store = array_buffer->backing_store();
198
199 base::LockGuard<base::Mutex> lock_guard(mutex_.Pointer());
200 FutexWaitListNode* node = wait_list_.Pointer()->head_;
201 while (node && num_waiters_to_wake > 0) {
202 if (backing_store == node->backing_store_ && addr == node->wait_addr_) {
203 node->waiting_ = false;
204 node->cond_.NotifyOne();
205 --num_waiters_to_wake;
206 waiters_woken++;
207 }
208
209 node = node->next_;
210 }
211
212 return Smi::FromInt(waiters_woken);
213 }
214
215
WakeOrRequeue(Isolate * isolate,Handle<JSArrayBuffer> array_buffer,size_t addr,int num_waiters_to_wake,int32_t value,size_t addr2)216 Object* FutexEmulation::WakeOrRequeue(Isolate* isolate,
217 Handle<JSArrayBuffer> array_buffer,
218 size_t addr, int num_waiters_to_wake,
219 int32_t value, size_t addr2) {
220 DCHECK(addr < NumberToSize(isolate, array_buffer->byte_length()));
221 DCHECK(addr2 < NumberToSize(isolate, array_buffer->byte_length()));
222
223 void* backing_store = array_buffer->backing_store();
224 int32_t* p =
225 reinterpret_cast<int32_t*>(static_cast<int8_t*>(backing_store) + addr);
226
227 base::LockGuard<base::Mutex> lock_guard(mutex_.Pointer());
228 if (*p != value) {
229 return Smi::FromInt(Result::kNotEqual);
230 }
231
232 // Wake |num_waiters_to_wake|
233 int waiters_woken = 0;
234 FutexWaitListNode* node = wait_list_.Pointer()->head_;
235 while (node) {
236 if (backing_store == node->backing_store_ && addr == node->wait_addr_) {
237 if (num_waiters_to_wake > 0) {
238 node->waiting_ = false;
239 node->cond_.NotifyOne();
240 --num_waiters_to_wake;
241 waiters_woken++;
242 } else {
243 node->wait_addr_ = addr2;
244 }
245 }
246
247 node = node->next_;
248 }
249
250 return Smi::FromInt(waiters_woken);
251 }
252
253
NumWaitersForTesting(Isolate * isolate,Handle<JSArrayBuffer> array_buffer,size_t addr)254 Object* FutexEmulation::NumWaitersForTesting(Isolate* isolate,
255 Handle<JSArrayBuffer> array_buffer,
256 size_t addr) {
257 DCHECK(addr < NumberToSize(isolate, array_buffer->byte_length()));
258 void* backing_store = array_buffer->backing_store();
259
260 base::LockGuard<base::Mutex> lock_guard(mutex_.Pointer());
261
262 int waiters = 0;
263 FutexWaitListNode* node = wait_list_.Pointer()->head_;
264 while (node) {
265 if (backing_store == node->backing_store_ && addr == node->wait_addr_ &&
266 node->waiting_) {
267 waiters++;
268 }
269
270 node = node->next_;
271 }
272
273 return Smi::FromInt(waiters);
274 }
275
276 } // namespace internal
277 } // namespace v8
278