/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 * 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 "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();
};

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 CharT>
    MOZ_ALWAYS_INLINE JSAtom* atomizeAndCopyChars(JSContext* cx,
                                                  const CharT* tbchars, size_t length,
                                                  PinningBehavior pin,
                                                  const mozilla::Maybe<uint32_t>& indexValue,
                                                  const AtomHasher::Lookup& lookup);

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

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

    // Sweep all atoms non-incrementally.
    void sweepAll(JSRuntime* rt);

    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 */
