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 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 42 FutexWaitList::FutexWaitList() : head_(nullptr), tail_(nullptr) {} 43 44 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 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 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 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 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
