DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Mercurial (b6d82b1a6b02)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 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/. */

/*
 * Implementation details of the atoms table.
 */

#ifndef vm_AtomsTable_h
#define vm_AtomsTable_h

#include <type_traits>  // std::{enable_if,is_const}

#include "js/GCHashTable.h"
#include "js/TypeDecls.h"
#include "vm/JSAtom.h"

/*
 * The atoms table is a mapping from strings to JSAtoms that supports concurrent
 * access and incremental sweeping.
 *
 * The table is partitioned based on the key into multiple sub-tables. Each
 * sub-table is protected by a lock to ensure safety when accessed by helper
 * threads. Concurrent access improves performance of off-thread parsing which
 * frequently creates large numbers of atoms. Locking is only required when
 * off-thread parsing is running.
 */

namespace js {

// Take all atoms table locks to allow iterating over cells in the atoms zone.
class MOZ_RAII AutoLockAllAtoms {
  JSRuntime* runtime;

 public:
  explicit AutoLockAllAtoms(JSRuntime* rt);
  ~AutoLockAllAtoms();
};

// This is a tagged pointer to an atom that duplicates the atom's pinned flag so
// that we don't have to check the atom itself when marking pinned atoms (there
// can be a great many atoms). See bug 1445196.
class AtomStateEntry {
  uintptr_t bits;

  static const uintptr_t NO_TAG_MASK = uintptr_t(-1) - 1;

 public:
  AtomStateEntry() : bits(0) {}
  AtomStateEntry(const AtomStateEntry& other) : bits(other.bits) {}
  AtomStateEntry(JSAtom* ptr, bool tagged)
      : bits(uintptr_t(ptr) | uintptr_t(tagged)) {
    MOZ_ASSERT((uintptr_t(ptr) & 0x1) == 0);
  }

  bool isPinned() const { return bits & 0x1; }

  /*
   * Non-branching code sequence. Note that the const_cast is safe because
   * the hash function doesn't consider the tag to be a portion of the key.
   */
  void setPinned(bool pinned) const {
    const_cast<AtomStateEntry*>(this)->bits |= uintptr_t(pinned);
  }

  JSAtom* asPtrUnbarriered() const {
    MOZ_ASSERT(bits);
    return reinterpret_cast<JSAtom*>(bits & NO_TAG_MASK);
  }

  JSAtom* asPtr(JSContext* cx) const;

  bool needsSweep() {
    JSAtom* atom = asPtrUnbarriered();
    return gc::IsAboutToBeFinalizedUnbarriered(&atom);
  }
};

struct AtomHasher {
  struct Lookup;
  static inline HashNumber hash(const Lookup& l);
  static MOZ_ALWAYS_INLINE bool match(const AtomStateEntry& entry,
                                      const Lookup& lookup);
  static void rekey(AtomStateEntry& k, const AtomStateEntry& newKey) {
    k = newKey;
  }
};

using AtomSet = JS::GCHashSet<AtomStateEntry, AtomHasher, SystemAllocPolicy>;

// This class is a wrapper for AtomSet that is used to ensure the AtomSet is
// not modified. It should only expose read-only methods from AtomSet.
// Note however that the atoms within the table can be marked during GC.
class FrozenAtomSet {
  AtomSet* mSet;

 public:
  // This constructor takes ownership of the passed-in AtomSet.
  explicit FrozenAtomSet(AtomSet* set) { mSet = set; }

  ~FrozenAtomSet() { js_delete(mSet); }

  MOZ_ALWAYS_INLINE AtomSet::Ptr readonlyThreadsafeLookup(
      const AtomSet::Lookup& l) const;

  size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
    return mSet->shallowSizeOfIncludingThis(mallocSizeOf);
  }

  typedef AtomSet::Range Range;

  AtomSet::Range all() const { return mSet->all(); }
};

class AtomsTable {
  static const size_t PartitionShift = 5;
  static const size_t PartitionCount = 1 << PartitionShift;

  // Use a low initial capacity for atom hash tables to avoid penalizing
  // runtimes which create a small number of atoms.
  static const size_t InitialTableSize = 16;

  // A single partition, representing a subset of the atoms in the table.
  struct Partition {
    explicit Partition(uint32_t index);
    ~Partition();

    // Lock that must be held to access this set.
    Mutex lock;

    // The atoms in this set.
    AtomSet atoms;

    // Set of atoms added while the |atoms| set is being swept.
    AtomSet* atomsAddedWhileSweeping;
  };

  Partition* partitions[PartitionCount];

#ifdef DEBUG
  bool allPartitionsLocked = false;
#endif

 public:
  class AutoLock;

  // An iterator used for sweeping atoms incrementally.
  class SweepIterator {
    AtomsTable& atoms;
    size_t partitionIndex;
    mozilla::Maybe<AtomSet::Enum> atomsIter;

    void settle();
    void startSweepingPartition();
    void finishSweepingPartition();

   public:
    explicit SweepIterator(AtomsTable& atoms);
    bool empty() const;
    JSAtom* front() const;
    void removeFront();
    void popFront();
  };

  ~AtomsTable();
  bool init();

  template <typename Chars>
  MOZ_ALWAYS_INLINE JSAtom* atomizeAndCopyChars(
      JSContext* cx, Chars chars, size_t length, PinningBehavior pin,
      const mozilla::Maybe<uint32_t>& indexValue,
      const AtomHasher::Lookup& lookup);

  template <typename CharT, typename = typename std::enable_if<
                                !std::is_const<CharT>::value>::type>
  MOZ_ALWAYS_INLINE JSAtom* atomizeAndCopyChars(
      JSContext* cx, CharT* chars, size_t length, PinningBehavior pin,
      const mozilla::Maybe<uint32_t>& indexValue,
      const AtomHasher::Lookup& lookup) {
    return atomizeAndCopyChars(cx, const_cast<const CharT*>(chars), length, pin,
                               indexValue, lookup);
  }

  void pinExistingAtom(JSContext* cx, JSAtom* atom);

  void tracePinnedAtoms(JSTracer* trc, const AutoAccessAtomsZone& access);

  // Sweep all atoms non-incrementally.
  void traceWeak(JSTracer* trc);

  bool startIncrementalSweep();

  // Sweep some atoms incrementally and return whether we finished.
  bool sweepIncrementally(SweepIterator& atomsToSweep, SliceBudget& budget);

#ifdef DEBUG
  bool mainThreadHasAllLocks() const { return allPartitionsLocked; }
#endif

  size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const;

 private:
  // Map a key to a partition based on its hash.
  MOZ_ALWAYS_INLINE size_t getPartitionIndex(const AtomHasher::Lookup& lookup);

  void tracePinnedAtomsInSet(JSTracer* trc, AtomSet& atoms);
  void mergeAtomsAddedWhileSweeping(Partition& partition);

  friend class AutoLockAllAtoms;
  void lockAll();
  void unlockAll();
};

}  // namespace js

#endif /* vm_AtomsTable_h */