futex-emulation.h 9 KB
Newer Older
binji's avatar
binji committed
1 2 3 4
// 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.

5 6
#ifndef V8_EXECUTION_FUTEX_EMULATION_H_
#define V8_EXECUTION_FUTEX_EMULATION_H_
binji's avatar
binji committed
7 8 9

#include <stdint.h>

10 11 12
#include <map>

#include "include/v8.h"
13
#include "src/base/atomicops.h"
binji's avatar
binji committed
14 15 16 17
#include "src/base/lazy-instance.h"
#include "src/base/macros.h"
#include "src/base/platform/condition-variable.h"
#include "src/base/platform/mutex.h"
18 19
#include "src/base/platform/time.h"
#include "src/tasks/cancelable-task.h"
20
#include "src/utils/allocation.h"
binji's avatar
binji committed
21 22 23 24 25 26 27

// Support for emulating futexes, a low-level synchronization primitive. They
// are natively supported by Linux, but must be emulated for other platforms.
// This library emulates them on all platforms using mutexes and condition
// variables for consistency.
//
// This is used by the Futex API defined in the SharedArrayBuffer draft spec,
28
// found here: https://github.com/tc39/ecmascript_sharedmem
binji's avatar
binji committed
29 30 31 32 33

namespace v8 {

namespace base {
class TimeDelta;
34
}  // namespace base
binji's avatar
binji committed
35 36 37

namespace internal {

38
class BackingStore;
39 40
class FutexWaitList;

marja's avatar
marja committed
41 42
template <typename T>
class Handle;
binji's avatar
binji committed
43
class Isolate;
44
class JSArrayBuffer;
binji's avatar
binji committed
45

46 47 48 49 50 51 52 53 54 55 56 57
class AtomicsWaitWakeHandle {
 public:
  explicit AtomicsWaitWakeHandle(Isolate* isolate) : isolate_(isolate) {}

  void Wake();
  inline bool has_stopped() const { return stopped_; }

 private:
  Isolate* isolate_;
  bool stopped_ = false;
};

binji's avatar
binji committed
58 59
class FutexWaitListNode {
 public:
60 61 62 63 64 65 66 67
  // Create a sync FutexWaitListNode.
  FutexWaitListNode() = default;

  // Create an async FutexWaitListNode.
  FutexWaitListNode(const std::shared_ptr<BackingStore>& backing_store,
                    size_t wait_addr, Handle<JSObject> promise_capability,
                    Isolate* isolate);
  ~FutexWaitListNode();
68 69
  FutexWaitListNode(const FutexWaitListNode&) = delete;
  FutexWaitListNode& operator=(const FutexWaitListNode&) = delete;
70 71

  void NotifyWake();
binji's avatar
binji committed
72

73 74 75 76 77
  bool IsAsync() const { return isolate_for_async_waiters_ != nullptr; }

  // Returns false if the cancelling failed, true otherwise.
  bool CancelTimeoutTask();

78
  class V8_NODISCARD ResetWaitingOnScopeExit {
79 80 81
   public:
    explicit ResetWaitingOnScopeExit(FutexWaitListNode* node) : node_(node) {}
    ~ResetWaitingOnScopeExit() { node_->waiting_ = false; }
82 83
    ResetWaitingOnScopeExit(const ResetWaitingOnScopeExit&) = delete;
    ResetWaitingOnScopeExit& operator=(const ResetWaitingOnScopeExit&) = delete;
84 85 86 87 88

   private:
    FutexWaitListNode* node_;
  };

binji's avatar
binji committed
89 90 91 92
 private:
  friend class FutexEmulation;
  friend class FutexWaitList;

93 94 95 96 97
  // Set only for async FutexWaitListNodes.
  Isolate* isolate_for_async_waiters_ = nullptr;
  std::shared_ptr<TaskRunner> task_runner_;
  CancelableTaskManager* cancelable_task_manager_ = nullptr;

binji's avatar
binji committed
98
  base::ConditionVariable cond_;
99
  // prev_ and next_ are protected by FutexEmulation::mutex_.
100 101 102
  FutexWaitListNode* prev_ = nullptr;
  FutexWaitListNode* next_ = nullptr;

103
  std::weak_ptr<BackingStore> backing_store_;
104
  size_t wait_addr_ = 0;
105 106 107 108 109 110 111 112 113 114 115

  // The memory location the FutexWaitListNode is waiting on. Equals
  // backing_store_->buffer_start() + wait_addr_ at FutexWaitListNode creation
  // time. Storing the wait_location_ separately is needed, since we can't
  // necessarily reconstruct it, because the BackingStore might get deleted
  // while the FutexWaitListNode is still alive. FutexWaitListNode must know its
  // wait location, since they are stored in per-location lists, and to remove
  // the node, we need to be able to find the list it's on (to be able to
  // update the head and tail of the list).
  int8_t* wait_location_ = nullptr;

116
  // waiting_ and interrupted_ are protected by FutexEmulation::mutex_
117 118
  // if this node is currently contained in FutexEmulation::wait_list_
  // or an AtomicsWaitWakeHandle has access to it.
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136
  bool waiting_ = false;
  bool interrupted_ = false;

  // Only for async FutexWaitListNodes. Weak Global handle. Must not be
  // synchronously resolved by a non-owner Isolate.
  v8::Global<v8::Promise> promise_;

  // Only for async FutexWaitListNodes. Weak Global handle.
  v8::Global<v8::Context> native_context_;

  // Only for async FutexWaitListNodes. If async_timeout_time_ is
  // base::TimeTicks(), this async waiter doesn't have a timeout or has already
  // been notified. Values other than base::TimeTicks() are used for async
  // waiters with an active timeout.
  base::TimeTicks async_timeout_time_;

  CancelableTaskManager::Id timeout_task_id_ =
      CancelableTaskManager::kInvalidTaskId;
binji's avatar
binji committed
137 138 139 140
};

class FutexEmulation : public AllStatic {
 public:
141 142
  enum WaitMode { kSync = 0, kAsync };

143 144 145
  // Pass to Wake() to wake all waiters.
  static const uint32_t kWakeAll = UINT32_MAX;

146
  // Check that array_buffer[addr] == value, and return "not-equal" if not. If
binji's avatar
binji committed
147 148 149
  // they are equal, block execution on |isolate|'s thread until woken via
  // |Wake|, or when the time given in |rel_timeout_ms| elapses. Note that
  // |rel_timeout_ms| can be Infinity.
150
  // If woken, return "ok", otherwise return "timed-out". The initial check and
binji's avatar
binji committed
151
  // the decision to wait happen atomically.
152 153 154
  static Object WaitJs32(Isolate* isolate, WaitMode mode,
                         Handle<JSArrayBuffer> array_buffer, size_t addr,
                         int32_t value, double rel_timeout_ms);
155 156

  // An version of WaitJs32 for int64_t values.
157 158 159
  static Object WaitJs64(Isolate* isolate, WaitMode mode,
                         Handle<JSArrayBuffer> array_buffer, size_t addr,
                         int64_t value, double rel_timeout_ms);
160 161 162

  // Same as WaitJs above except it returns 0 (ok), 1 (not equal) and 2 (timed
  // out) as expected by Wasm.
163 164 165 166
  V8_EXPORT_PRIVATE static Object WaitWasm32(Isolate* isolate,
                                             Handle<JSArrayBuffer> array_buffer,
                                             size_t addr, int32_t value,
                                             int64_t rel_timeout_ns);
167 168 169

  // Same as Wait32 above except it checks for an int64_t value in the
  // array_buffer.
170 171 172 173
  V8_EXPORT_PRIVATE static Object WaitWasm64(Isolate* isolate,
                                             Handle<JSArrayBuffer> array_buffer,
                                             size_t addr, int64_t value,
                                             int64_t rel_timeout_ns);
binji's avatar
binji committed
174 175

  // Wake |num_waiters_to_wake| threads that are waiting on the given |addr|.
176 177 178
  // |num_waiters_to_wake| can be kWakeAll, in which case all waiters are
  // woken. The rest of the waiters will continue to wait. The return value is
  // the number of woken waiters.
179 180 181
  V8_EXPORT_PRIVATE static Object Wake(Handle<JSArrayBuffer> array_buffer,
                                       size_t addr,
                                       uint32_t num_waiters_to_wake);
binji's avatar
binji committed
182

183 184 185 186 187
  // Called before |isolate| dies. Removes async waiters owned by |isolate|.
  static void IsolateDeinit(Isolate* isolate);

  // Return the number of threads or async waiters waiting on |addr|. Should
  // only be used for testing.
188 189
  static Object NumWaitersForTesting(Handle<JSArrayBuffer> array_buffer,
                                     size_t addr);
binji's avatar
binji committed
190

191 192 193 194 195 196 197 198 199 200
  // Return the number of async waiters (which belong to |isolate|) waiting.
  // Should only be used for testing.
  static Object NumAsyncWaitersForTesting(Isolate* isolate);

  // Return the number of async waiters which were waiting for |addr| and are
  // now waiting for the Promises to be resolved. Should only be used for
  // testing.
  static Object NumUnresolvedAsyncPromisesForTesting(
      Handle<JSArrayBuffer> array_buffer, size_t addr);

binji's avatar
binji committed
201
 private:
202
  friend class FutexWaitListNode;
203
  friend class AtomicsWaitWakeHandle;
204 205 206 207 208 209 210 211 212 213 214 215
  friend class ResolveAsyncWaiterPromisesTask;
  friend class AsyncWaiterTimeoutTask;

  template <typename T>
  static Object Wait(Isolate* isolate, WaitMode mode,
                     Handle<JSArrayBuffer> array_buffer, size_t addr, T value,
                     double rel_timeout_ms);

  template <typename T>
  static Object Wait(Isolate* isolate, WaitMode mode,
                     Handle<JSArrayBuffer> array_buffer, size_t addr, T value,
                     bool use_timeout, int64_t rel_timeout_ns);
216

217
  template <typename T>
218 219 220
  static Object WaitSync(Isolate* isolate, Handle<JSArrayBuffer> array_buffer,
                         size_t addr, T value, bool use_timeout,
                         int64_t rel_timeout_ns);
221

222
  template <typename T>
223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
  static Object WaitAsync(Isolate* isolate, Handle<JSArrayBuffer> array_buffer,
                          size_t addr, T value, bool use_timeout,
                          int64_t rel_timeout_ns);

  // Resolve the Promises of the async waiters which belong to |isolate|.
  static void ResolveAsyncWaiterPromises(Isolate* isolate);

  static void ResolveAsyncWaiterPromise(FutexWaitListNode* node);

  static void HandleAsyncWaiterTimeout(FutexWaitListNode* node);

  static void NotifyAsyncWaiter(FutexWaitListNode* node);

  // Remove the node's Promise from the NativeContext's Promise set.
  static void CleanupAsyncWaiterPromise(FutexWaitListNode* node);
binji's avatar
binji committed
238
};
239 240
}  // namespace internal
}  // namespace v8
binji's avatar
binji committed
241

242
#endif  // V8_EXECUTION_FUTEX_EMULATION_H_