Add m-esr52 at 52.6.0

1 files changed, 468 insertions, 0 deletions

diff --git a/js/src/vm/SharedImmutableStringsCache.h b/js/src/vm/SharedImmutableStringsCache.h
new file mode 100644
index 000000000..ddb6ff87f
--- /dev/null
+++ b/js/src/vm/SharedImmutableStringsCache.h
@@ -0,0 +1,468 @@
+/* -*- 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