Home | History | Annotate | Download | only in src 
      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();
    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 
    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
    278