tor-browser

SharedImmutableStringsCache.h (13750B)

---

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