1 files changed, 218 insertions, 0 deletions
diff --git a/js/src/gc/NurseryAwareHashMap.h b/js/src/gc/NurseryAwareHashMap.h
new file mode 100644
index 0000000000..5b2e1f02fa
--- /dev/null
+++ b/js/src/gc/NurseryAwareHashMap.h
@@ -0,0 +1,218 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
+ * vim: set ts=8 sts=2 et sw=2 tw=80:
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef gc_NurseryAwareHashMap_h
+#define gc_NurseryAwareHashMap_h
+
+#include "gc/Barrier.h"
+#include "gc/Marking.h"
+#include "js/GCHashTable.h"
+#include "js/GCPolicyAPI.h"
+#include "js/HashTable.h"
+
+namespace js {
+
+namespace detail {
+// This class only handles the incremental case and does not deal with nursery
+// pointers. The only users should be for NurseryAwareHashMap; it is defined
+// externally because we need a GCPolicy for its use in the contained map.
+template <typename T>
+class UnsafeBareWeakHeapPtr : public ReadBarriered<T> {
+ public:
+  UnsafeBareWeakHeapPtr() : ReadBarriered<T>(JS::SafelyInitialized<T>()) {}
+  MOZ_IMPLICIT UnsafeBareWeakHeapPtr(const T& v) : ReadBarriered<T>(v) {}
+  explicit UnsafeBareWeakHeapPtr(const UnsafeBareWeakHeapPtr& v)
+      : ReadBarriered<T>(v) {}
+  UnsafeBareWeakHeapPtr(UnsafeBareWeakHeapPtr&& v)
+      : ReadBarriered<T>(std::move(v)) {}
+
+  UnsafeBareWeakHeapPtr& operator=(const UnsafeBareWeakHeapPtr& v) {
+    this->value = v.value;
+    return *this;
+  }
+
+  UnsafeBareWeakHeapPtr& operator=(const T& v) {
+    this->value = v;
+    return *this;
+  }
+
+  const T get() const {
+    if (!InternalBarrierMethods<T>::isMarkable(this->value)) {
+      return JS::SafelyInitialized<T>();
+    }
+    this->read();
+    return this->value;
+  }
+
+  explicit operator bool() const { return bool(this->value); }
+
+  const T unbarrieredGet() const { return this->value; }
+  T* unsafeGet() { return &this->value; }
+  T const* unsafeGet() const { return &this->value; }
+};
+}  // namespace detail
+
+enum : bool { DuplicatesNotPossible, DuplicatesPossible };
+
+// The "nursery aware" hash map is a special case of GCHashMap that is able to
+// treat nursery allocated members weakly during a minor GC: e.g. it allows for
+// nursery allocated objects to be collected during nursery GC where a normal
+// hash table treats such edges strongly.
+//
+// Doing this requires some strong constraints on what can be stored in this
+// table and how it can be accessed. At the moment, this table assumes that
+// all values contain a strong reference to the key. It also requires the
+// policy to contain an |isTenured| and |needsSweep| members, which is fairly
+// non-standard. This limits its usefulness to the CrossCompartmentMap at the
+// moment, but might serve as a useful base for other tables in future.
+template <typename Key, typename Value,
+          typename HashPolicy = DefaultHasher<Key>,
+          typename AllocPolicy = TempAllocPolicy,
+          bool AllowDuplicates = DuplicatesNotPossible>
+class NurseryAwareHashMap {
+  using BarrieredValue = detail::UnsafeBareWeakHeapPtr<Value>;
+  using MapType =
+      GCRekeyableHashMap<Key, BarrieredValue, HashPolicy, AllocPolicy>;
+  MapType map;
+
+  // Keep a list of all keys for which JS::GCPolicy<Key>::isTenured is false.
+  // This lets us avoid a full traveral of the map on each minor GC, keeping
+  // the minor GC times proportional to the nursery heap size.
+  Vector<Key, 0, AllocPolicy> nurseryEntries;
+
+ public:
+  using Lookup = typename MapType::Lookup;
+  using Ptr = typename MapType::Ptr;
+  using Range = typename MapType::Range;
+  using Entry = typename MapType::Entry;
+
+  explicit NurseryAwareHashMap(AllocPolicy a = AllocPolicy())
+      : map(a), nurseryEntries(std::move(a)) {}
+  explicit NurseryAwareHashMap(size_t length) : map(length) {}
+  NurseryAwareHashMap(AllocPolicy a, size_t length)
+      : map(a, length), nurseryEntries(std::move(a)) {}
+
+  bool empty() const { return map.empty(); }
+  Ptr lookup(const Lookup& l) const { return map.lookup(l); }
+  void remove(Ptr p) { map.remove(p); }
+  Range all() const { return map.all(); }
+  struct Enum : public MapType::Enum {
+    explicit Enum(NurseryAwareHashMap& namap) : MapType::Enum(namap.map) {}
+  };
+  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
+    return map.shallowSizeOfExcludingThis(mallocSizeOf) +
+           nurseryEntries.sizeOfExcludingThis(mallocSizeOf);
+  }
+  size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
+    return map.shallowSizeOfIncludingThis(mallocSizeOf) +
+           nurseryEntries.sizeOfIncludingThis(mallocSizeOf);
+  }
+
+  MOZ_MUST_USE bool put(const Key& k, const Value& v) {
+    auto p = map.lookupForAdd(k);
+    if (p) {
+      if (!JS::GCPolicy<Key>::isTenured(k) ||
+          !JS::GCPolicy<Value>::isTenured(v)) {
+        if (!nurseryEntries.append(k)) {
+          return false;
+        }
+      }
+      p->value() = v;
+      return true;
+    }
+
+    bool ok = map.add(p, k, v);
+    if (!ok) {
+      return false;
+    }
+
+    if (!JS::GCPolicy<Key>::isTenured(k) ||
+        !JS::GCPolicy<Value>::isTenured(v)) {
+      if (!nurseryEntries.append(k)) {
+        map.remove(k);
+        return false;
+      }
+    }
+
+    return true;
+  }
+
+  void sweepAfterMinorGC(JSTracer* trc) {
+    for (auto& key : nurseryEntries) {
+      auto p = map.lookup(key);
+      if (!p) {
+        continue;
+      }
+
+      // Drop the entry if the value is not marked.
+      if (JS::GCPolicy<BarrieredValue>::needsSweep(&p->value())) {
+        map.remove(key);
+        continue;
+      }
+
+      // Update and relocate the key, if the value is still needed.
+      //
+      // Non-string Values will contain a strong reference to Key, as per
+      // its use in the CrossCompartmentWrapperMap, so the key will never
+      // be dying here. Strings do *not* have any sort of pointer from
+      // wrapper to wrappee, as they are just copies. The wrapper map
+      // entry is merely used as a cache to avoid re-copying the string,
+      // and currently that entire cache is flushed on major GC.
+      Key copy(key);
+      bool sweepKey = JS::GCPolicy<Key>::needsSweep(&copy);
+      if (sweepKey) {
+        map.remove(key);
+        continue;
+      }
+      if (AllowDuplicates) {
+        // Drop duplicated keys.
+        //
+        // A key can be forwarded to another place. In this case, rekey the
+        // item. If two or more different keys are forwarded to the same new
+        // key, simply drop the later ones.
+        if (key == copy) {
+          // No rekey needed.
+        } else if (map.has(copy)) {
+          // Key was forwarded to the same place that another key was already
+          // forwarded to.
+          map.remove(key);
+        } else {
+          map.rekeyAs(key, copy, copy);
+        }
+      } else {
+        MOZ_ASSERT(key == copy || !map.has(copy));
+        map.rekeyIfMoved(key, copy);
+      }
+    }
+    nurseryEntries.clear();
+  }
+
+  void sweep() { map.sweep(); }
+
+  void clear() {
+    map.clear();
+    nurseryEntries.clear();
+  }
+
+  bool hasNurseryEntries() const { return !nurseryEntries.empty(); }
+};
+
+}  // namespace js
+
+namespace JS {
+template <typename T>
+struct GCPolicy<js::detail::UnsafeBareWeakHeapPtr<T>> {
+  static void trace(JSTracer* trc, js::detail::UnsafeBareWeakHeapPtr<T>* thingp,
+                    const char* name) {
+    js::TraceEdge(trc, thingp, name);
+  }
+  static bool needsSweep(js::detail::UnsafeBareWeakHeapPtr<T>* thingp) {
+    return js::gc::IsAboutToBeFinalized(thingp);
+  }
+};
+}  // namespace JS
+
+#endif  // gc_NurseryAwareHashMap_h