// Copyright 2015 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "src/futex-emulation.h"
#include <limits>
#include "src/base/macros.h"
#include "src/base/platform/time.h"
#include "src/conversions.h"
#include "src/handles-inl.h"
#include "src/isolate.h"
#include "src/list-inl.h"
namespace v8 {
namespace internal {
base::LazyMutex FutexEmulation::mutex_ = LAZY_MUTEX_INITIALIZER;
base::LazyInstance<FutexWaitList>::type FutexEmulation::wait_list_ =
LAZY_INSTANCE_INITIALIZER;
void FutexWaitListNode::NotifyWake() {
// Lock the FutexEmulation mutex before notifying. We know that the mutex
// will have been unlocked if we are currently waiting on the condition
// variable.
//
// The mutex may also not be locked if the other thread is currently handling
// interrupts, or if FutexEmulation::Wait was just called and the mutex
// hasn't been locked yet. In either of those cases, we set the interrupted
// flag to true, which will be tested after the mutex is re-locked.
base::LockGuard<base::Mutex> lock_guard(FutexEmulation::mutex_.Pointer());
if (waiting_) {
cond_.NotifyOne();
interrupted_ = true;
}
}
FutexWaitList::FutexWaitList() : head_(nullptr), tail_(nullptr) {}
void FutexWaitList::AddNode(FutexWaitListNode* node) {
DCHECK(node->prev_ == nullptr && node->next_ == nullptr);
if (tail_) {
tail_->next_ = node;
} else {
head_ = node;
}
node->prev_ = tail_;
node->next_ = nullptr;
tail_ = node;
}
void FutexWaitList::RemoveNode(FutexWaitListNode* node) {
if (node->prev_) {
node->prev_->next_ = node->next_;
} else {
head_ = node->next_;
}
if (node->next_) {
node->next_->prev_ = node->prev_;
} else {
tail_ = node->prev_;
}
node->prev_ = node->next_ = nullptr;
}
Object* FutexEmulation::Wait(Isolate* isolate,
Handle<JSArrayBuffer> array_buffer, size_t addr,
int32_t value, double rel_timeout_ms) {
DCHECK(addr < NumberToSize(isolate, array_buffer->byte_length()));
void* backing_store = array_buffer->backing_store();
int32_t* p =
reinterpret_cast<int32_t*>(static_cast<int8_t*>(backing_store) + addr);
base::LockGuard<base::Mutex> lock_guard(mutex_.Pointer());
if (*p != value) {
return Smi::FromInt(Result::kNotEqual);
}
FutexWaitListNode* node = isolate->futex_wait_list_node();
node->backing_store_ = backing_store;
node->wait_addr_ = addr;
node->waiting_ = true;
bool use_timeout = rel_timeout_ms != V8_INFINITY;
base::TimeDelta rel_timeout;
if (use_timeout) {
// Convert to nanoseconds.
double rel_timeout_ns = rel_timeout_ms *
base::Time::kNanosecondsPerMicrosecond *
base::Time::kMicrosecondsPerMillisecond;
if (rel_timeout_ns >
static_cast<double>(std::numeric_limits<int64_t>::max())) {
// 2**63 nanoseconds is 292 years. Let's just treat anything greater as
// infinite.
use_timeout = false;
} else {
rel_timeout = base::TimeDelta::FromNanoseconds(
static_cast<int64_t>(rel_timeout_ns));
}
}
base::TimeTicks start_time = base::TimeTicks::Now();
base::TimeTicks timeout_time = start_time + rel_timeout;
base::TimeTicks current_time = start_time;
wait_list_.Pointer()->AddNode(node);
Object* result;
while (true) {
bool interrupted = node->interrupted_;
node->interrupted_ = false;
// Unlock the mutex here to prevent deadlock from lock ordering between
// mutex_ and mutexes locked by HandleInterrupts.
mutex_.Pointer()->Unlock();
// Because the mutex is unlocked, we have to be careful about not dropping
// an interrupt. The notification can happen in three different places:
// 1) Before Wait is called: the notification will be dropped, but
// interrupted_ will be set to 1. This will be checked below.
// 2) After interrupted has been checked here, but before mutex_ is
// acquired: interrupted is checked again below, with mutex_ locked.
// Because the wakeup signal also acquires mutex_, we know it will not
// be able to notify until mutex_ is released below, when waiting on the
// condition variable.
// 3) After the mutex is released in the call to WaitFor(): this
// notification will wake up the condition variable. node->waiting() will
// be false, so we'll loop and then check interrupts.
if (interrupted) {
Object* interrupt_object = isolate->stack_guard()->HandleInterrupts();
if (interrupt_object->IsException()) {
result = interrupt_object;
mutex_.Pointer()->Lock();
break;
}
}
mutex_.Pointer()->Lock();
if (node->interrupted_) {
// An interrupt occured while the mutex_ was unlocked. Don't wait yet.
continue;
}
if (!node->waiting_) {
result = Smi::FromInt(Result::kOk);
break;
}
// No interrupts, now wait.
if (use_timeout) {
current_time = base::TimeTicks::Now();
if (current_time >= timeout_time) {
result = Smi::FromInt(Result::kTimedOut);
break;
}
base::TimeDelta time_until_timeout = timeout_time - current_time;
DCHECK(time_until_timeout.InMicroseconds() >= 0);
bool wait_for_result =
node->cond_.WaitFor(mutex_.Pointer(), time_until_timeout);
USE(wait_for_result);
} else {
node->cond_.Wait(mutex_.Pointer());
}
// Spurious wakeup, interrupt or timeout.
}
wait_list_.Pointer()->RemoveNode(node);
node->waiting_ = false;
return result;
}
Object* FutexEmulation::Wake(Isolate* isolate,
Handle<JSArrayBuffer> array_buffer, size_t addr,
int num_waiters_to_wake) {
DCHECK(addr < NumberToSize(isolate, array_buffer->byte_length()));
int waiters_woken = 0;
void* backing_store = array_buffer->backing_store();
base::LockGuard<base::Mutex> lock_guard(mutex_.Pointer());
FutexWaitListNode* node = wait_list_.Pointer()->head_;
while (node && num_waiters_to_wake > 0) {
if (backing_store == node->backing_store_ && addr == node->wait_addr_) {
node->waiting_ = false;
node->cond_.NotifyOne();
--num_waiters_to_wake;
waiters_woken++;
}
node = node->next_;
}
return Smi::FromInt(waiters_woken);
}
Object* FutexEmulation::WakeOrRequeue(Isolate* isolate,
Handle<JSArrayBuffer> array_buffer,
size_t addr, int num_waiters_to_wake,
int32_t value, size_t addr2) {
DCHECK(addr < NumberToSize(isolate, array_buffer->byte_length()));
DCHECK(addr2 < NumberToSize(isolate, array_buffer->byte_length()));
void* backing_store = array_buffer->backing_store();
int32_t* p =
reinterpret_cast<int32_t*>(static_cast<int8_t*>(backing_store) + addr);
base::LockGuard<base::Mutex> lock_guard(mutex_.Pointer());
if (*p != value) {
return Smi::FromInt(Result::kNotEqual);
}
// Wake |num_waiters_to_wake|
int waiters_woken = 0;
FutexWaitListNode* node = wait_list_.Pointer()->head_;
while (node) {
if (backing_store == node->backing_store_ && addr == node->wait_addr_) {
if (num_waiters_to_wake > 0) {
node->waiting_ = false;
node->cond_.NotifyOne();
--num_waiters_to_wake;
waiters_woken++;
} else {
node->wait_addr_ = addr2;
}
}
node = node->next_;
}
return Smi::FromInt(waiters_woken);
}
Object* FutexEmulation::NumWaitersForTesting(Isolate* isolate,
Handle<JSArrayBuffer> array_buffer,
size_t addr) {
DCHECK(addr < NumberToSize(isolate, array_buffer->byte_length()));
void* backing_store = array_buffer->backing_store();
base::LockGuard<base::Mutex> lock_guard(mutex_.Pointer());
int waiters = 0;
FutexWaitListNode* node = wait_list_.Pointer()->head_;
while (node) {
if (backing_store == node->backing_store_ && addr == node->wait_addr_ &&
node->waiting_) {
waiters++;
}
node = node->next_;
}
return Smi::FromInt(waiters);
}
} // namespace internal
} // namespace v8