path: root/js/src/vm/SharedImmutableStringsCache.h

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

#ifndef vm_SharedImmutableStringsCache_h
#define vm_SharedImmutableStringsCache_h

#include "mozilla/Maybe.h"
#include "mozilla/UniquePtr.h"

#include <cstring>
#include <new> // for placement new

#include "jsstr.h"

#include "js/HashTable.h"
#include "js/Utility.h"

#include "threading/ExclusiveData.h"

#include "vm/MutexIDs.h"

namespace js {

class SharedImmutableString;
class SharedImmutableTwoByteString;

/**
 * The `SharedImmutableStringsCache` allows for safely sharing and deduplicating
 * immutable strings (either `const char*` or `const char16_t*`) between
 * threads.
 *
 * The locking mechanism is dead-simple and coarse grained: a single lock guards
 * all of the internal table itself, the table's entries, and the entries'
 * reference counts. It is only safe to perform any mutation on the cache or any
 * data stored within the cache when this lock is acquired.
 */
class SharedImmutableStringsCache
{
    friend class SharedImmutableString;
    friend class SharedImmutableTwoByteString;
    struct Hasher;

  public:
    using OwnedChars = mozilla::UniquePtr<char[], JS::FreePolicy>;
    using OwnedTwoByteChars = mozilla::UniquePtr<char16_t[], JS::FreePolicy>;

    /**
     * Get the canonical, shared, and de-duplicated version of the given `const
     * char*` string. If such a string does not exist, call `intoOwnedChars` and
     * add the string it returns to the cache.
     *
     * `intoOwnedChars` must create an owned version of the given string, and
     * must have one of the following types:
     *
     *     mozilla::UniquePtr<char[], JS::FreePolicy>   intoOwnedChars();
     *     mozilla::UniquePtr<char[], JS::FreePolicy>&& intoOwnedChars();
     *
     * It can be used by callers to elide a copy of the string when it is safe
     * to give up ownership of the lookup string to the cache. It must return a
     * `nullptr` on failure.
     *
     * On success, `Some` is returned. In the case of OOM failure, `Nothing` is
     * returned.
     */
    template <typename IntoOwnedChars>
    MOZ_MUST_USE mozilla::Maybe<SharedImmutableString>
    getOrCreate(const char* chars, size_t length, IntoOwnedChars intoOwnedChars);

    /**
     * Take ownership of the given `chars` and return the canonical, shared and
     * de-duplicated version.
     *
     * On success, `Some` is returned. In the case of OOM failure, `Nothing` is
     * returned.
     */
    MOZ_MUST_USE mozilla::Maybe<SharedImmutableString>
    getOrCreate(OwnedChars&& chars, size_t length);

    /**
     * Do not take ownership of the given `chars`. Return the canonical, shared
     * and de-duplicated version. If there is no extant shared version of
     * `chars`, make a copy and insert it into the cache.
     *
     * On success, `Some` is returned. In the case of OOM failure, `Nothing` is
     * returned.
     */
    MOZ_MUST_USE mozilla::Maybe<SharedImmutableString>
    getOrCreate(const char* chars, size_t length);

    /**
     * Get the canonical, shared, and de-duplicated version of the given `const
     * char16_t*` string. If such a string does not exist, call `intoOwnedChars`
     * and add the string it returns to the cache.
     *
     * `intoOwnedTwoByteChars` must create an owned version of the given string,
     * and must have one of the following types:
     *
     *     mozilla::UniquePtr<char16_t[], JS::FreePolicy>   intoOwnedTwoByteChars();
     *     mozilla::UniquePtr<char16_t[], JS::FreePolicy>&& intoOwnedTwoByteChars();
     *
     * It can be used by callers to elide a copy of the string when it is safe
     * to give up ownership of the lookup string to the cache. It must return a
     * `nullptr` on failure.
     *
     * On success, `Some` is returned. In the case of OOM failure, `Nothing` is
     * returned.
     */
    template <typename IntoOwnedTwoByteChars>
    MOZ_MUST_USE mozilla::Maybe<SharedImmutableTwoByteString>
    getOrCreate(const char16_t* chars, size_t length, IntoOwnedTwoByteChars intoOwnedTwoByteChars);

    /**
     * Take ownership of the given `chars` and return the canonical, shared and
     * de-duplicated version.
     *
     * On success, `Some` is returned. In the case of OOM failure, `Nothing` is
     * returned.
     */
    MOZ_MUST_USE mozilla::Maybe<SharedImmutableTwoByteString>
    getOrCreate(OwnedTwoByteChars&& chars, size_t length);

    /**
     * Do not take ownership of the given `chars`. Return the canonical, shared
     * and de-duplicated version. If there is no extant shared version of
     * `chars`, then make a copy and insert it into the cache.
     *
     * On success, `Some` is returned. In the case of OOM failure, `Nothing` is
     * returned.
     */
    MOZ_MUST_USE mozilla::Maybe<SharedImmutableTwoByteString>
    getOrCreate(const char16_t* chars, size_t length);

    size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
        MOZ_ASSERT(inner_);
        size_t n = mallocSizeOf(inner_);

        auto locked = inner_->lock();
        if (!locked->set.initialized())
            return n;

        // Size of the table.
        n += locked->set.sizeOfExcludingThis(mallocSizeOf);

        // Sizes of the strings and their boxes.
        for (auto r = locked->set.all(); !r.empty(); r.popFront()) {
            n += mallocSizeOf(r.front().get());
            if (const char* chars = r.front()->chars())
                n += mallocSizeOf(chars);
        }

        return n;
    }

    /**
     * Construct a new cache of shared, immutable strings. Returns
     * `mozilla::Nothing` on out of memory failure.
     */
    static mozilla::Maybe<SharedImmutableStringsCache> Create() {
        auto inner = js_new<ExclusiveData<Inner>>(mutexid::SharedImmutableStringsCache);
        if (!inner)
            return mozilla::Nothing();

        auto locked = inner->lock();
        return mozilla::Some(SharedImmutableStringsCache(locked));
    }

    SharedImmutableStringsCache(SharedImmutableStringsCache&& rhs)
      : inner_(rhs.inner_)
    {
        MOZ_ASSERT(inner_);
        rhs.inner_ = nullptr;
    }

    SharedImmutableStringsCache& operator=(SharedImmutableStringsCache&& rhs) {
        MOZ_ASSERT(this != &rhs, "self move not allowed");
        new (this) SharedImmutableStringsCache(mozilla::Move(rhs));
        return *this;
    }

    SharedImmutableStringsCache& operator=(const SharedImmutableStringsCache&) = delete;

    SharedImmutableStringsCache clone() {
        MOZ_ASSERT(inner_);
        auto locked = inner_->lock();
        return SharedImmutableStringsCache(locked);
    }

    ~SharedImmutableStringsCache() {
        if (!inner_)
            return;

        bool shouldDestroy = false;
        {
            // ~ExclusiveData takes the lock, so be sure to drop the lock before
            // attempting to destroy the inner.
            auto locked = inner_->lock();
            MOZ_ASSERT(locked->refcount > 0);
            locked->refcount--;
            if (locked->refcount == 0)
                shouldDestroy = true;
        }
        if (shouldDestroy)
            js_delete(inner_);
    }

    /**
     * Purge the cache of all refcount == 0 entries.
     */
    void purge() {
        auto locked = inner_->lock();
        MOZ_ASSERT(locked->refcount > 0);

        if (!locked->set.initialized())
            return;

        for (Inner::Set::Enum e(locked->set); !e.empty(); e.popFront()) {
            if (e.front()->refcount == 0) {
                // The chars should be eagerly freed when refcount reaches zero.
                MOZ_ASSERT(!e.front()->chars());
                e.removeFront();
            } else {
                // The chars should exist as long as the refcount is non-zero.
                MOZ_ASSERT(e.front()->chars());
            }
        }
    }

  private:
    class StringBox
    {
        friend class SharedImmutableString;

        OwnedChars chars_;
        size_t length_;

      public:
        mutable size_t refcount;

        using Ptr = mozilla::UniquePtr<StringBox, JS::DeletePolicy<StringBox>>;

        StringBox(OwnedChars&& chars, size_t length)
          : chars_(mozilla::Move(chars))
          , length_(length)
          , refcount(0)
        {
            MOZ_ASSERT(chars_);
        }

        static Ptr Create(OwnedChars&& chars, size_t length) {
            return Ptr(js_new<StringBox>(mozilla::Move(chars), length));
        }

        StringBox(const StringBox&) = delete;
        StringBox& operator=(const StringBox&) = delete;

        ~StringBox() {
            MOZ_RELEASE_ASSERT(refcount == 0,
                               "There are `SharedImmutable[TwoByte]String`s outliving their "
                               "associated cache! This always leads to use-after-free in the "
                               "`~SharedImmutableString` destructor!");
        }

        const char* chars() const { return chars_.get(); }
        size_t length() const { return length_; }
    };

    struct Hasher
    {
        /**
         * A structure used when querying for a `const char*` string in the cache.
         */
        class Lookup
        {
            friend struct Hasher;

            HashNumber hash_;
            const char* chars_;
            size_t length_;

          public:
            Lookup(HashNumber hash, const char* chars, size_t length)
              : hash_(hash)
              , chars_(chars)
              , length_(length)
            {
                MOZ_ASSERT(chars_);
                MOZ_ASSERT(hash == Hasher::hashLongString(chars, length));
            }

            Lookup(HashNumber hash, const char16_t* chars, size_t length)
              : Lookup(hash, reinterpret_cast<const char*>(chars), length * sizeof(char16_t))
            { }
        };

        static const size_t SHORT_STRING_MAX_LENGTH = 8192;
        static const size_t HASH_CHUNK_LENGTH = SHORT_STRING_MAX_LENGTH / 2;

        // For strings longer than SHORT_STRING_MAX_LENGTH, we only hash the
        // first HASH_CHUNK_LENGTH and last HASH_CHUNK_LENGTH characters in the
        // string. This increases the risk of collisions, but in practice it
        // should be rare, and it yields a large speedup for hashing long
        // strings.
        static HashNumber hashLongString(const char* chars, size_t length) {
            MOZ_ASSERT(chars);
            return length <= SHORT_STRING_MAX_LENGTH
                ? mozilla::HashString(chars, length)
                : mozilla::AddToHash(mozilla::HashString(chars, HASH_CHUNK_LENGTH),
                                     mozilla::HashString(chars + length - HASH_CHUNK_LENGTH,
                                                         HASH_CHUNK_LENGTH));
        }

        static HashNumber hash(const Lookup& lookup) {
            return lookup.hash_;
        }

        static bool match(const StringBox::Ptr& key, const Lookup& lookup) {
            MOZ_ASSERT(lookup.chars_);

            if (!key->chars() || key->length() != lookup.length_)
                return false;

            if (key->chars() == lookup.chars_)
                return true;

            return memcmp(key->chars(), lookup.chars_, key->length()) == 0;
        }
    };

    // The `Inner` struct contains the actual cached contents, and is reference
    // counted and shared between all `SharedImmutableStringsCache` and
    // `SharedImmutable[TwoByte]String` holders.
    struct Inner
    {
        using Set = HashSet<StringBox::Ptr, Hasher, SystemAllocPolicy>;

        size_t refcount;
        Set set;

        Inner()
          : refcount(0)
          , set()
        { }

        Inner(const Inner&) = delete;
        Inner& operator=(const Inner&) = delete;

        ~Inner()
        {
            MOZ_ASSERT(refcount == 0);
        }
    };

    const ExclusiveData<Inner>* inner_;

    explicit SharedImmutableStringsCache(ExclusiveData<Inner>::Guard& locked)
      : inner_(locked.parent())
    {
        locked->refcount++;
    }
};

/**
 * The `SharedImmutableString` class holds a reference to a `const char*` string
 * from the `SharedImmutableStringsCache` and releases the reference upon
 * destruction.
 */
class SharedImmutableString
{
    friend class SharedImmutableStringsCache;
    friend class SharedImmutableTwoByteString;

    mutable SharedImmutableStringsCache cache_;
    mutable SharedImmutableStringsCache::StringBox* box_;

    SharedImmutableString(ExclusiveData<SharedImmutableStringsCache::Inner>::Guard& locked,
                          SharedImmutableStringsCache::StringBox* box);

  public:
    /**
     * `SharedImmutableString`s are move-able. It is an error to use a
     * `SharedImmutableString` after it has been moved.
     */
    SharedImmutableString(SharedImmutableString&& rhs);
    SharedImmutableString& operator=(SharedImmutableString&& rhs);

    /**
     * Create another shared reference to the underlying string.
     */
    SharedImmutableString clone() const;

    // If you want a copy, take one explicitly with `clone`!
    SharedImmutableString& operator=(const SharedImmutableString&) = delete;

    ~SharedImmutableString();

    /**
     * Get a raw pointer to the underlying string. It is only safe to use the
     * resulting pointer while this `SharedImmutableString` exists.
     */
    const char* chars() const {
        MOZ_ASSERT(box_);
        MOZ_ASSERT(box_->refcount > 0);
        MOZ_ASSERT(box_->chars());
        return box_->chars();
    }

    /**
     * Get the length of the underlying string.
     */
    size_t length() const {
        MOZ_ASSERT(box_);
        MOZ_ASSERT(box_->refcount > 0);
        MOZ_ASSERT(box_->chars());
        return box_->length();
    }
};

/**
 * The `SharedImmutableTwoByteString` class holds a reference to a `const
 * char16_t*` string from the `SharedImmutableStringsCache` and releases the
 * reference upon destruction.
 */
class SharedImmutableTwoByteString
{
    friend class SharedImmutableStringsCache;

    // If a `char*` string and `char16_t*` string happen to have the same bytes,
    // the bytes will be shared but handed out as different types.
    SharedImmutableString string_;

    explicit SharedImmutableTwoByteString(SharedImmutableString&& string);
    SharedImmutableTwoByteString(ExclusiveData<SharedImmutableStringsCache::Inner>::Guard& locked,
                                 SharedImmutableStringsCache::StringBox* box);

  public:
    /**
     * `SharedImmutableTwoByteString`s are move-able. It is an error to use a
     * `SharedImmutableTwoByteString` after it has been moved.
     */
    SharedImmutableTwoByteString(SharedImmutableTwoByteString&& rhs);
    SharedImmutableTwoByteString& operator=(SharedImmutableTwoByteString&& rhs);

    /**
     * Create another shared reference to the underlying string.
     */
    SharedImmutableTwoByteString clone() const;

    // If you want a copy, take one explicitly with `clone`!
    SharedImmutableTwoByteString& operator=(const SharedImmutableTwoByteString&) = delete;

    /**
     * Get a raw pointer to the underlying string. It is only safe to use the
     * resulting pointer while this `SharedImmutableTwoByteString` exists.
     */
    const char16_t* chars() const { return reinterpret_cast<const char16_t*>(string_.chars()); }

    /**
     * Get the length of the underlying string.
     */
    size_t length() const { return string_.length() / sizeof(char16_t); }
};

} // namespace js

#endif // vm_SharedImmutableStringsCache_h