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