Source code

Revision control

Other Tools

/* -*- 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 */
* Implementation details of the atoms table.
#ifndef vm_AtomsTable_h
#define vm_AtomsTable_h
#include <type_traits> // std::{enable_if_t,is_const_v}
#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;
explicit AutoLockAllAtoms(JSRuntime* rt);
// 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;
AtomStateEntry() : bits(0) {}
AtomStateEntry(const AtomStateEntry& other) = default;
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 {
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;
// 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);
using Range = AtomSet::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);
// 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;
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();
explicit SweepIterator(AtomsTable& atoms);
bool empty() const;
AtomStateEntry front() const;
void removeFront();
void popFront();
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 = std::enable_if_t<!std::is_const_v<CharT>>>
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);
bool atomIsPinned(JSRuntime* rt, JSAtom* atom);
void maybePinExistingAtom(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; }
size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const;
// 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();
bool AtomIsPinned(JSContext* cx, JSAtom* atom);
} // namespace js
#endif /* vm_AtomsTable_h */