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