tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

NurseryAwareHashMap.h (8230B)

      1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
      2 * vim: set ts=8 sts=2 et sw=2 tw=80:
      3 * This Source Code Form is subject to the terms of the Mozilla Public
      4 * License, v. 2.0. If a copy of the MPL was not distributed with this
      5 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
      6 
      7 #ifndef gc_NurseryAwareHashMap_h
      8 #define gc_NurseryAwareHashMap_h
      9 
     10 #include "gc/Barrier.h"
     11 #include "gc/Tracer.h"
     12 #include "js/GCHashTable.h"
     13 #include "js/GCPolicyAPI.h"
     14 #include "js/GCVector.h"
     15 #include "js/Utility.h"
     16 
     17 namespace js {
     18 
     19 namespace detail {
     20 
     21 // This class only handles the incremental case and does not deal with nursery
     22 // pointers. The only users should be for NurseryAwareHashMap; it is defined
     23 // externally because we need a GCPolicy for its use in the contained map.
     24 template <typename T>
     25 class UnsafeBareWeakHeapPtr : public ReadBarriered<T> {
     26 public:
     27  UnsafeBareWeakHeapPtr()
     28      : ReadBarriered<T>(JS::SafelyInitialized<T>::create()) {}
     29  MOZ_IMPLICIT UnsafeBareWeakHeapPtr(const T& v) : ReadBarriered<T>(v) {}
     30  explicit UnsafeBareWeakHeapPtr(const UnsafeBareWeakHeapPtr& v)
     31      : ReadBarriered<T>(v) {}
     32  UnsafeBareWeakHeapPtr(UnsafeBareWeakHeapPtr&& v)
     33      : ReadBarriered<T>(std::move(v)) {}
     34 
     35  UnsafeBareWeakHeapPtr& operator=(const UnsafeBareWeakHeapPtr& v) {
     36    this->value = v.value;
     37    return *this;
     38  }
     39 
     40  UnsafeBareWeakHeapPtr& operator=(const T& v) {
     41    this->value = v;
     42    return *this;
     43  }
     44 
     45  const T get() const {
     46    if (!InternalBarrierMethods<T>::isMarkable(this->value)) {
     47      return JS::SafelyInitialized<T>::create();
     48    }
     49    this->read();
     50    return this->value;
     51  }
     52 
     53  explicit operator bool() const { return bool(this->value); }
     54 
     55  const T unbarrieredGet() const { return this->value; }
     56  T* unsafeGet() { return &this->value; }
     57  T const* unsafeGet() const { return &this->value; }
     58 };
     59 }  // namespace detail
     60 
     61 enum : bool { DuplicatesNotPossible, DuplicatesPossible };
     62 
     63 // The "nursery aware" hash map is a special case of GCHashMap that is able to
     64 // treat nursery allocated members weakly during a minor GC: e.g. it allows for
     65 // nursery allocated objects to be collected during nursery GC where a normal
     66 // hash table treats such edges strongly.
     67 //
     68 // Doing this requires some strong constraints on what can be stored in this
     69 // table and how it can be accessed. At the moment, this table assumes that all
     70 // values contain a strong reference to the key. This limits its usefulness to
     71 // the CrossCompartmentMap at the moment, but might serve as a useful base for
     72 // other tables in future.
     73 template <typename Key, typename Value, typename AllocPolicy = TempAllocPolicy,
     74          bool AllowDuplicates = DuplicatesNotPossible>
     75 class NurseryAwareHashMap {
     76  using MapKey = UnsafeBarePtr<Key>;
     77  using MapValue = detail::UnsafeBareWeakHeapPtr<Value>;
     78  using HashPolicy = DefaultHasher<MapKey>;
     79  using MapType = GCRekeyableHashMap<MapKey, MapValue, HashPolicy, AllocPolicy>;
     80  MapType map;
     81 
     82  // Keep a list of all keys for which key->isTenured() is false. This lets us
     83  // avoid a full traversal of the map on each minor GC, keeping the minor GC
     84  // times proportional to the nursery heap size.
     85  using KeyVector = GCVector<Key, 0, AllocPolicy>;
     86  KeyVector nurseryEntries;
     87 
     88 public:
     89  using Lookup = typename MapType::Lookup;
     90  using Ptr = typename MapType::Ptr;
     91  using Range = typename MapType::Range;
     92  using Entry = typename MapType::Entry;
     93 
     94  explicit NurseryAwareHashMap(AllocPolicy a = AllocPolicy())
     95      : map(a), nurseryEntries(std::move(a)) {}
     96  explicit NurseryAwareHashMap(size_t length) : map(length) {}
     97  NurseryAwareHashMap(AllocPolicy a, size_t length)
     98      : map(a, length), nurseryEntries(std::move(a)) {}
     99 
    100  bool empty() const { return map.empty(); }
    101  Ptr lookup(const Lookup& l) const { return map.lookup(l); }
    102  void remove(Ptr p) { map.remove(p); }
    103  Range all() const { return map.all(); }
    104  struct Enum : public MapType::Enum {
    105    explicit Enum(NurseryAwareHashMap& namap) : MapType::Enum(namap.map) {}
    106  };
    107  size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
    108    return map.shallowSizeOfExcludingThis(mallocSizeOf) +
    109           nurseryEntries.sizeOfExcludingThis(mallocSizeOf);
    110  }
    111  size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
    112    return mallocSizeOf(this) + sizeOfExcludingThis(mallocSizeOf);
    113  }
    114 
    115  [[nodiscard]] bool put(const Key& key, const Value& value) {
    116    if ((!key->isTenured() || !value->isTenured()) &&
    117        !nurseryEntries.append(key)) {
    118      return false;
    119    }
    120 
    121    auto p = map.lookupForAdd(key);
    122    if (p) {
    123      p->value() = value;
    124      return true;
    125    }
    126 
    127    return map.add(p, key, value);
    128  }
    129 
    130  void sweepAfterMinorGC(JSTracer* trc) {
    131    nurseryEntries.mutableEraseIf([this, trc](Key& key) {
    132      auto p = map.lookup(key);
    133      if (!p) {
    134        return true;
    135      }
    136 
    137      // Drop the entry if the value is not marked.
    138      if (!JS::GCPolicy<MapValue>::traceWeak(trc, &p->value())) {
    139        map.remove(p);
    140        return true;
    141      }
    142 
    143      // Update and relocate the key, if the value is still needed.
    144      //
    145      // Non-string Values will contain a strong reference to Key, as per its
    146      // use in the CrossCompartmentWrapperMap, so the key will never be dying
    147      // here. Strings do *not* have any sort of pointer from wrapper to
    148      // wrappee, as they are just copies. The wrapper map entry is merely used
    149      // as a cache to avoid re-copying the string, and currently that entire
    150      // cache is flushed on major GC.
    151      //
    152      // Since |key| is a reference, this updates the content of the
    153      // nurseryEntries vector.
    154      Key prior = key;
    155      if (!TraceManuallyBarrieredWeakEdge(trc, &key,
    156                                          "NurseryAwareHashMap key")) {
    157        map.remove(p);
    158        return true;
    159      }
    160 
    161      bool valueIsTenured = p->value().unbarrieredGet()->isTenured();
    162 
    163      if constexpr (AllowDuplicates) {
    164        // Drop duplicated keys.
    165        //
    166        // A key can be forwarded to another place. In this case, rekey the
    167        // item. If two or more different keys are forwarded to the same new
    168        // key, simply drop the later ones.
    169        if (key == prior) {
    170          // No rekey needed.
    171        } else if (map.has(key)) {
    172          // Key was forwarded to the same place that another key was already
    173          // forwarded to.
    174          map.remove(p);
    175          return true;
    176        } else {
    177          map.rekeyAs(prior, key, key);
    178        }
    179      } else {
    180        MOZ_ASSERT(key == prior || !map.has(key));
    181        map.rekeyIfMoved(prior, key);
    182      }
    183 
    184      return key->isTenured() && valueIsTenured;
    185    });
    186 
    187    checkNurseryEntries();
    188  }
    189 
    190  void checkNurseryEntries() const {
    191 #ifdef DEBUG
    192    AutoEnterOOMUnsafeRegion oomUnsafe;
    193    HashSet<Key, DefaultHasher<Key>, SystemAllocPolicy> set;
    194    for (const auto& key : nurseryEntries) {
    195      if (!set.put(key)) {
    196        oomUnsafe.crash("NurseryAwareHashMap::checkNurseryEntries");
    197      }
    198    }
    199 
    200    for (auto i = map.iter(); !i.done(); i.next()) {
    201      Key key = i.get().key().get();
    202      MOZ_ASSERT(gc::IsCellPointerValid(key));
    203      MOZ_ASSERT_IF(IsInsideNursery(key), set.has(key));
    204 
    205      Value value = i.get().value().unbarrieredGet();
    206      MOZ_ASSERT(gc::IsCellPointerValid(value));
    207      MOZ_ASSERT_IF(IsInsideNursery(value), set.has(key));
    208    }
    209 #endif
    210  }
    211 
    212  void traceWeak(JSTracer* trc) { map.traceWeak(trc); }
    213 
    214  void clear() {
    215    map.clear();
    216    nurseryEntries.clear();
    217  }
    218 
    219  bool hasNurseryEntries() const { return !nurseryEntries.empty(); }
    220 };
    221 
    222 }  // namespace js
    223 
    224 namespace JS {
    225 
    226 template <typename T>
    227 struct GCPolicy<js::detail::UnsafeBareWeakHeapPtr<T>>
    228    : public GCPolicyBase<js::detail::UnsafeBareWeakHeapPtr<T>> {
    229  static void trace(JSTracer* trc, js::detail::UnsafeBareWeakHeapPtr<T>* thingp,
    230                    const char* name) {
    231    js::TraceEdge(trc, thingp, name);
    232  }
    233  static bool traceWeak(JSTracer* trc,
    234                        js::detail::UnsafeBareWeakHeapPtr<T>* thingp) {
    235    return js::TraceWeakEdge(trc, thingp, "UnsafeBareWeakHeapPtr");
    236  }
    237 };
    238 
    239 }  // namespace JS
    240 
    241 namespace mozilla {}  // namespace mozilla
    242 
    243 #endif  // gc_NurseryAwareHashMap_h