js/src/vm/AtomsTable.h

   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 /*
   8  * Implementation details of the atoms table.
   9  */
  10
  11 #ifndef vm_AtomsTable_h
  12 #define vm_AtomsTable_h
  13
  14 #include "gc/Barrier.h"
  15 #include "js/GCHashTable.h"
  16 #include "js/TypeDecls.h"
  17 #include "js/Vector.h"
  18 #include "vm/StringType.h"
  19
  20 /*
  21  * The atoms table is a mapping from strings to JSAtoms that supports
  22  * incremental sweeping.
  23  */
  24
  25 namespace js {
  26
  27 struct AtomHasher {
  28   struct Lookup;
  29   static inline HashNumber hash(const Lookup& l);
  30   static MOZ_ALWAYS_INLINE bool match(const WeakHeapPtr<JSAtom*>& entry,
  31                                       const Lookup& lookup);
  32   static void rekey(WeakHeapPtr<JSAtom*>& k,
  33                     const WeakHeapPtr<JSAtom*>& newKey) {
  34     k = newKey;
  35   }
  36 };
  37
  38 struct js::AtomHasher::Lookup {
  39   union {
  40     const JS::Latin1Char* latin1Chars;
  41     const char16_t* twoByteChars;
  42     const char* utf8Bytes;
  43   };
  44   enum { TwoByteChar, Latin1, UTF8 } type;
  45   size_t length;
  46   size_t byteLength;
  47   const JSAtom* atom; /* Optional. */
  48   JS::AutoCheckCannotGC nogc;
  49
  50   HashNumber hash;
  51
  52   MOZ_ALWAYS_INLINE Lookup(const char* utf8Bytes, size_t byteLen, size_t length,
  53                            HashNumber hash)
  54       : utf8Bytes(utf8Bytes),
  55         type(UTF8),
  56         length(length),
  57         byteLength(byteLen),
  58         atom(nullptr),
  59         hash(hash) {}
  60
  61   MOZ_ALWAYS_INLINE Lookup(const char16_t* chars, size_t length)
  62       : twoByteChars(chars),
  63         type(TwoByteChar),
  64         length(length),
  65         atom(nullptr),
  66         hash(mozilla::HashString(chars, length)) {}
  67
  68   MOZ_ALWAYS_INLINE Lookup(const JS::Latin1Char* chars, size_t length)
  69       : latin1Chars(chars),
  70         type(Latin1),
  71         length(length),
  72         atom(nullptr),
  73         hash(mozilla::HashString(chars, length)) {}
  74
  75   MOZ_ALWAYS_INLINE Lookup(HashNumber hash, const char16_t* chars,
  76                            size_t length)
  77       : twoByteChars(chars),
  78         type(TwoByteChar),
  79         length(length),
  80         atom(nullptr),
  81         hash(hash) {
  82     MOZ_ASSERT(hash == mozilla::HashString(chars, length));
  83   }
  84
  85   MOZ_ALWAYS_INLINE Lookup(HashNumber hash, const JS::Latin1Char* chars,
  86                            size_t length)
  87       : latin1Chars(chars),
  88         type(Latin1),
  89         length(length),
  90         atom(nullptr),
  91         hash(hash) {
  92     MOZ_ASSERT(hash == mozilla::HashString(chars, length));
  93   }
  94
  95   inline explicit Lookup(const JSAtom* atom)
  96       : type(atom->hasLatin1Chars() ? Latin1 : TwoByteChar),
  97         length(atom->length()),
  98         atom(atom),
  99         hash(atom->hash()) {
 100     if (type == Latin1) {
 101       latin1Chars = atom->latin1Chars(nogc);
 102       MOZ_ASSERT(mozilla::HashString(latin1Chars, length) == hash);
 103     } else {
 104       MOZ_ASSERT(type == TwoByteChar);
 105       twoByteChars = atom->twoByteChars(nogc);
 106       MOZ_ASSERT(mozilla::HashString(twoByteChars, length) == hash);
 107     }
 108   }
 109
 110   // Return: true iff the string in |atom| matches the string in this Lookup.
 111   bool StringsMatch(const JSAtom& atom) const;
 112 };
 113
 114 // Note: Use a 'class' here to make forward declarations easier to use.
 115 class AtomSet : public JS::GCHashSet<WeakHeapPtr<JSAtom*>, AtomHasher,
 116                                      SystemAllocPolicy> {
 117   using Base =
 118       JS::GCHashSet<WeakHeapPtr<JSAtom*>, AtomHasher, SystemAllocPolicy>;
 119
 120  public:
 121   AtomSet() = default;
 122   explicit AtomSet(size_t length) : Base(length) {};
 123 };
 124
 125 // This class is a wrapper for AtomSet that is used to ensure the AtomSet is
 126 // not modified. It should only expose read-only methods from AtomSet.
 127 // Note however that the atoms within the table can be marked during GC.
 128 class FrozenAtomSet {
 129   AtomSet* mSet;
 130
 131  public:
 132   // This constructor takes ownership of the passed-in AtomSet.
 133   explicit FrozenAtomSet(AtomSet* set) { mSet = set; }
 134
 135   ~FrozenAtomSet() { js_delete(mSet); }
 136
 137   MOZ_ALWAYS_INLINE AtomSet::Ptr readonlyThreadsafeLookup(
 138       const AtomSet::Lookup& l) const;
 139
 140   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 141     return mSet->shallowSizeOfIncludingThis(mallocSizeOf);
 142   }
 143
 144   using Range = AtomSet::Range;
 145
 146   AtomSet::Range all() const { return mSet->all(); }
 147 };
 148
 149 class AtomsTable {
 150   // Use a low initial capacity for atom hash tables to avoid penalizing
 151   // runtimes which create a small number of atoms.
 152   static const size_t InitialTableSize = 16;
 153
 154   // The main atoms set.
 155   AtomSet atoms;
 156
 157   // Set of atoms added while the |atoms| set is being swept.
 158   AtomSet* atomsAddedWhileSweeping;
 159
 160   // List of pinned atoms that are traced in every GC.
 161   Vector<JSAtom*, 0, SystemAllocPolicy> pinnedAtoms;
 162
 163  public:
 164   // An iterator used for sweeping atoms incrementally.
 165   using SweepIterator = AtomSet::Enum;
 166
 167   AtomsTable();
 168   ~AtomsTable();
 169   bool init();
 170
 171   template <typename CharT>
 172   MOZ_ALWAYS_INLINE JSAtom* atomizeAndCopyCharsNonStaticValidLength(
 173       JSContext* cx, const CharT* chars, size_t length,
 174       const mozilla::Maybe<uint32_t>& indexValue,
 175       const AtomHasher::Lookup& lookup);
 176
 177   bool maybePinExistingAtom(JSContext* cx, JSAtom* atom);
 178
 179   void tracePinnedAtoms(JSTracer* trc);
 180
 181   // Sweep all atoms non-incrementally.
 182   void traceWeak(JSTracer* trc);
 183
 184   bool startIncrementalSweep(mozilla::Maybe<SweepIterator>& atomsToSweepOut);
 185
 186   // Sweep some atoms incrementally and return whether we finished.
 187   bool sweepIncrementally(SweepIterator& atomsToSweep, JS::SliceBudget& budget);
 188
 189   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
 190
 191  private:
 192   void mergeAtomsAddedWhileSweeping();
 193 };
 194
 195 bool AtomIsPinned(JSContext* cx, JSAtom* atom);
 196
 197 }  // namespace js
 198
 199 #endif /* vm_AtomsTable_h */