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
16namespace v8 {
17namespace internal {
18
19base::LazyMutex FutexEmulation::mutex_ = LAZY_MUTEX_INITIALIZER;
20base::LazyInstance<FutexWaitList>::type FutexEmulation::wait_list_ =
21    LAZY_INSTANCE_INITIALIZER;
22
23
24void 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
41FutexWaitList::FutexWaitList() : head_(nullptr), tail_(nullptr) {}
42
43
44void 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
58void 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
75Object* 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()) {
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
191Object* 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
216Object* 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
254Object* 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