1 files changed, 425 insertions, 0 deletions
diff --git a/js/src/vm/SharedImmutableStringsCache.h b/js/src/vm/SharedImmutableStringsCache.h
new file mode 100644
index 0000000000..a10ff416a4
--- /dev/null
+++ b/js/src/vm/SharedImmutableStringsCache.h
@@ -0,0 +1,425 @@
+/* -*- 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 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 <utility>  // std::move
+
+#include "js/AllocPolicy.h"
+#include "js/HashTable.h"
+#include "js/UniquePtr.h"
+#include "js/Utility.h"
+
+#include "threading/ExclusiveData.h"
+
+namespace js {
+
+class SharedImmutableString;
+class SharedImmutableTwoByteString;
+
+/**
+ * The `SharedImmutableStringsCache` allows safely sharing and deduplicating
+ * immutable strings (either `const char*` [any encoding, not restricted to
+ * only Latin-1 or only UTF-8] 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 {
+  static SharedImmutableStringsCache singleton_;
+
+  friend class SharedImmutableString;
+  friend class SharedImmutableTwoByteString;
+  struct Hasher;
+
+ public:
+  using OwnedChars = JS::UniqueChars;
+  using OwnedTwoByteChars = JS::UniqueTwoByteChars;
+
+  /**
+   * 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:
+   *
+   *     JS::UniqueChars   intoOwnedChars();
+   *     JS::UniqueChars&& 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>
+  [[nodiscard]] 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.
+   */
+  [[nodiscard]] 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.
+   */
+  [[nodiscard]] 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:
+   *
+   *     JS::UniqueTwoByteChars   intoOwnedTwoByteChars();
+   *     JS::UniqueTwoByteChars&& 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>
+  [[nodiscard]] 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.
+   */
+  [[nodiscard]] 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.
+   */
+  [[nodiscard]] 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();
+
+    // Size of the table.
+    n += locked->set.shallowSizeOfExcludingThis(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;
+  }
+
+ private:
+  bool init();
+  void free();
+
+ public:
+  static bool initSingleton();
+  static void freeSingleton();
+
+  static SharedImmutableStringsCache& getSingleton() {
+    MOZ_ASSERT(singleton_.inner_);
+    return singleton_;
+  }
+
+ private:
+  SharedImmutableStringsCache() = default;
+  ~SharedImmutableStringsCache() = default;
+
+ public:
+  SharedImmutableStringsCache(const SharedImmutableStringsCache& rhs) = delete;
+  SharedImmutableStringsCache(SharedImmutableStringsCache&& rhs) = delete;
+
+  SharedImmutableStringsCache& operator=(SharedImmutableStringsCache&& rhs) =
+      delete;
+
+  SharedImmutableStringsCache& operator=(const SharedImmutableStringsCache&) =
+      delete;
+
+  /**
+   * Purge the cache of all refcount == 0 entries.
+   */
+  void purge() {
+    auto locked = inner_->lock();
+
+    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:
+  struct Inner;
+  class StringBox {
+    friend class SharedImmutableString;
+
+    OwnedChars chars_;
+    size_t length_;
+    const ExclusiveData<Inner>* cache_;
+
+   public:
+    mutable size_t refcount;
+
+    using Ptr = js::UniquePtr<StringBox>;
+
+    StringBox(OwnedChars&& chars, size_t length,
+              const ExclusiveData<Inner>* cache)
+        : chars_(std::move(chars)),
+          length_(length),
+          cache_(cache),
+          refcount(0) {
+      MOZ_ASSERT(chars_);
+    }
+
+    static Ptr Create(OwnedChars&& chars, size_t length,
+                      const ExclusiveData<Inner>* cache) {
+      return js::MakeUnique<StringBox>(std::move(chars), length, cache);
+    }
+
+    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 shared between
+  // the `SharedImmutableStringsCache` singleton and all
+  // `SharedImmutable[TwoByte]String` holders.
+  struct Inner {
+    using Set = HashSet<StringBox::Ptr, Hasher, SystemAllocPolicy>;
+
+    Set set;
+
+    Inner() = default;
+
+    Inner(const Inner&) = delete;
+    Inner& operator=(const Inner&) = delete;
+  };
+
+  const ExclusiveData<Inner>* inner_ = nullptr;
+};
+
+/**
+ * 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::StringBox* box_;
+
+  explicit SharedImmutableString(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);
+  SharedImmutableString() { box_ = nullptr; }
+
+  /**
+   * 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;
+  explicit operator bool() const { return box_ != nullptr; }
+
+  ~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);
+  explicit SharedImmutableTwoByteString(
+      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);
+  SharedImmutableTwoByteString() { string_.box_ = nullptr; }
+
+  /**
+   * 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;
+  explicit operator bool() const { return string_.box_ != nullptr; }
+  /**
+   * 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