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