Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
| 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 | |
| 41 | FutexWaitList::FutexWaitList() : head_(nullptr), tail_(nullptr) {} |
| 42 | |
| 43 | |
| 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 | |
| 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 | |
| 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(); |
Ben Murdoch | 61f157c | 2016-09-16 13:49:30 +0100 | [diff] [blame] | 145 | if (interrupt_object->IsException(isolate)) { |
Ben Murdoch | 4a90d5f | 2016-03-22 12:00:34 +0000 | [diff] [blame] | 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 | |
| 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 | |
| 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 | |
| 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 |