diff options
Diffstat (limited to 'chromium/third_party/blink/renderer/platform/wtf')
34 files changed, 659 insertions, 181 deletions
diff --git a/chromium/third_party/blink/renderer/platform/wtf/BUILD.gn b/chromium/third_party/blink/renderer/platform/wtf/BUILD.gn index 294afeb47c8..8c627534974 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/BUILD.gn +++ b/chromium/third_party/blink/renderer/platform/wtf/BUILD.gn @@ -109,6 +109,7 @@ jumbo_component("wtf") { "text/case_map.cc", "text/case_map.h", "text/character_names.h", + "text/character_visitor.h", "text/integer_to_string_conversion.h", "text/line_ending.cc", "text/line_ending.h", diff --git a/chromium/third_party/blink/renderer/platform/wtf/DEPS b/chromium/third_party/blink/renderer/platform/wtf/DEPS index 43cd2e6f12f..9ccf4961abb 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/DEPS +++ b/chromium/third_party/blink/renderer/platform/wtf/DEPS @@ -1,5 +1,5 @@ include_rules = [ - # To whitelist base/ stuff Blink is allowed to include, we list up all + # To only allow a subset of base/ in Blink, we explicitly list all # directories and files instead of writing 'base/'. "+base/allocator/partition_allocator", "+base/atomic_ref_count.h", diff --git a/chromium/third_party/blink/renderer/platform/wtf/allocator/Allocator.md b/chromium/third_party/blink/renderer/platform/wtf/allocator/Allocator.md index 0a978a43ccb..3bd4780be9f 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/allocator/Allocator.md +++ b/chromium/third_party/blink/renderer/platform/wtf/allocator/Allocator.md @@ -4,10 +4,8 @@ All objects in Blink are expected to be allocated with PartitionAlloc or Oilpan. Blink uses different PartitionAlloc partitions, for different kinds of objects: -* LayoutObject partition: A partition to allocate `LayoutObject`s. -The LayoutObject partition is a `SizeSpecificPartitionAllocator`. This means -that no extra padding is needed to allocate a `LayoutObject` object. Different -sizes of `LayoutObject`s are allocated in different buckets. Having a dedicated +* LayoutObject partition: A partition to allocate `LayoutObject`s. The +LayoutObject partition is a `ThreadUnsafePartitionAllocator`. Having a dedicated partition for `LayoutObject`s improves cache locality and thus performance. * Buffer partition: A partition to allocate objects that have a strong risk diff --git a/chromium/third_party/blink/renderer/platform/wtf/allocator/allocator.h b/chromium/third_party/blink/renderer/platform/wtf/allocator/allocator.h index 66fc9943d46..b135f379ddf 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/allocator/allocator.h +++ b/chromium/third_party/blink/renderer/platform/wtf/allocator/allocator.h @@ -7,6 +7,7 @@ #include <atomic> +#include "base/check_op.h" #include "build/build_config.h" #include "third_party/blink/renderer/platform/wtf/allocator/partitions.h" #include "third_party/blink/renderer/platform/wtf/assertions.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions.cc b/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions.cc index abb17cad6d9..f2ab11772d1 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions.cc @@ -33,8 +33,6 @@ #include "base/allocator/partition_allocator/memory_reclaimer.h" #include "base/allocator/partition_allocator/oom.h" #include "base/allocator/partition_allocator/page_allocator.h" -#include "base/allocator/partition_allocator/partition_alloc.h" -#include "base/allocator/partition_allocator/partition_root_base.h" #include "base/debug/alias.h" #include "third_party/blink/renderer/platform/wtf/allocator/partition_allocator.h" #include "third_party/blink/renderer/platform/wtf/wtf.h" @@ -48,10 +46,10 @@ bool Partitions::initialized_ = false; // These statics are inlined, so cannot be LazyInstances. We create the values, // and then set the pointers correctly in Initialize(). -base::PartitionRootGeneric* Partitions::fast_malloc_root_ = nullptr; -base::PartitionRootGeneric* Partitions::array_buffer_root_ = nullptr; -base::PartitionRootGeneric* Partitions::buffer_root_ = nullptr; -base::PartitionRoot* Partitions::layout_root_ = nullptr; +base::ThreadSafePartitionRoot* Partitions::fast_malloc_root_ = nullptr; +base::ThreadSafePartitionRoot* Partitions::array_buffer_root_ = nullptr; +base::ThreadSafePartitionRoot* Partitions::buffer_root_ = nullptr; +base::ThreadUnsafePartitionRoot* Partitions::layout_root_ = nullptr; // static void Partitions::Initialize() { @@ -61,10 +59,10 @@ void Partitions::Initialize() { // static bool Partitions::InitializeOnce() { - static base::PartitionAllocatorGeneric fast_malloc_allocator{}; - static base::PartitionAllocatorGeneric array_buffer_allocator{}; - static base::PartitionAllocatorGeneric buffer_allocator{}; - static base::SizeSpecificPartitionAllocator<1024> layout_allocator{}; + static base::PartitionAllocator fast_malloc_allocator{}; + static base::PartitionAllocator array_buffer_allocator{}; + static base::PartitionAllocator buffer_allocator{}; + static base::ThreadUnsafePartitionAllocator layout_allocator{}; base::PartitionAllocGlobalInit(&Partitions::HandleOutOfMemory); diff --git a/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions.h b/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions.h index 4dcc3564ed8..b8b89b1f7ec 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions.h +++ b/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions.h @@ -31,17 +31,12 @@ #ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_ALLOCATOR_PARTITIONS_H_ #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_ALLOCATOR_PARTITIONS_H_ -#include "base/logging.h" +#include "base/allocator/partition_allocator/partition_alloc.h" +#include "base/check.h" #include "base/memory/scoped_refptr.h" #include "base/numerics/checked_math.h" #include "third_party/blink/renderer/platform/wtf/wtf_export.h" -namespace base { -class PartitionStatsDumper; -struct PartitionRoot; -struct PartitionRootGeneric; -} // namespace base - namespace WTF { class WTF_EXPORT Partitions { @@ -55,17 +50,17 @@ class WTF_EXPORT Partitions { static void StartPeriodicReclaim( scoped_refptr<base::SequencedTaskRunner> task_runner); - ALWAYS_INLINE static base::PartitionRootGeneric* ArrayBufferPartition() { + ALWAYS_INLINE static base::ThreadSafePartitionRoot* ArrayBufferPartition() { DCHECK(initialized_); return array_buffer_root_; } - ALWAYS_INLINE static base::PartitionRootGeneric* BufferPartition() { + ALWAYS_INLINE static base::ThreadSafePartitionRoot* BufferPartition() { DCHECK(initialized_); return buffer_root_; } - ALWAYS_INLINE static base::PartitionRoot* LayoutPartition() { + ALWAYS_INLINE static base::ThreadUnsafePartitionRoot* LayoutPartition() { DCHECK(initialized_); return layout_root_; } @@ -94,7 +89,7 @@ class WTF_EXPORT Partitions { static void HandleOutOfMemory(size_t size); private: - ALWAYS_INLINE static base::PartitionRootGeneric* FastMallocPartition() { + ALWAYS_INLINE static base::ThreadSafePartitionRoot* FastMallocPartition() { DCHECK(initialized_); return fast_malloc_root_; } @@ -103,10 +98,10 @@ class WTF_EXPORT Partitions { static bool initialized_; // See Allocator.md for a description of these partitions. - static base::PartitionRootGeneric* fast_malloc_root_; - static base::PartitionRootGeneric* array_buffer_root_; - static base::PartitionRootGeneric* buffer_root_; - static base::PartitionRoot* layout_root_; + static base::ThreadSafePartitionRoot* fast_malloc_root_; + static base::ThreadSafePartitionRoot* array_buffer_root_; + static base::ThreadSafePartitionRoot* buffer_root_; + static base::ThreadUnsafePartitionRoot* layout_root_; }; } // namespace WTF diff --git a/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions_test.cc b/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions_test.cc index a44f1f9c795..3f6867cfa45 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions_test.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/allocator/partitions_test.cc @@ -3,9 +3,11 @@ // found in the LICENSE file. #include "third_party/blink/renderer/platform/wtf/allocator/partitions.h" + +#include <vector> + #include "base/allocator/partition_allocator/memory_reclaimer.h" #include "build/build_config.h" - #include "testing/gtest/include/gtest/gtest.h" namespace WTF { @@ -22,16 +24,27 @@ class PartitionsTest : public ::testing::Test { }; TEST_F(PartitionsTest, MemoryIsInitiallyCommitted) { + // std::vector to explicitly not use PartitionAlloc. + std::vector<void*> allocated_pointers; + size_t committed_before = Partitions::TotalSizeOfCommittedPages(); - void* data = Partitions::BufferMalloc(1, ""); - ASSERT_TRUE(data); + // Need to allocate enough memory to require a new super page. Unless nothing + // else in the process has allocated anything, this can be after several + // iterations. + while (Partitions::TotalSizeOfCommittedPages() == committed_before) { + void* data = Partitions::BufferMalloc(100, ""); + ASSERT_TRUE(data); + allocated_pointers.push_back(data); + } size_t committed_after = Partitions::TotalSizeOfCommittedPages(); // No buffer data committed initially, hence committed size increases. EXPECT_GT(committed_after, committed_before); // Increase is larger than the allocation. - EXPECT_GT(committed_after, committed_before + 1); - Partitions::BufferFree(data); + EXPECT_GT(committed_after, committed_before + allocated_pointers.size()); + + for (void* data : allocated_pointers) + Partitions::BufferFree(data); // Decommit is not triggered by deallocation. size_t committed_after_free = Partitions::TotalSizeOfCommittedPages(); @@ -39,12 +52,19 @@ TEST_F(PartitionsTest, MemoryIsInitiallyCommitted) { } TEST_F(PartitionsTest, Decommit) { + std::vector<void*> allocated_pointers; + size_t committed_before = Partitions::TotalSizeOfCommittedPages(); - void* data = Partitions::BufferMalloc(1, ""); - ASSERT_TRUE(data); - Partitions::BufferFree(data); + while (Partitions::TotalSizeOfCommittedPages() == committed_before) { + void* data = Partitions::BufferMalloc(100, ""); + ASSERT_TRUE(data); + allocated_pointers.push_back(data); + } size_t committed_after = Partitions::TotalSizeOfCommittedPages(); + for (void* data : allocated_pointers) + Partitions::BufferFree(data); + // Decommit is not triggered by deallocation. EXPECT_GT(committed_after, committed_before); // Decommit works. diff --git a/chromium/third_party/blink/renderer/platform/wtf/assertions_test.cc b/chromium/third_party/blink/renderer/platform/wtf/assertions_test.cc index e5535ff0747..1f0649e3e46 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/assertions_test.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/assertions_test.cc @@ -4,6 +4,7 @@ #include "third_party/blink/renderer/platform/wtf/assertions.h" +#include "base/notreached.h" #include "testing/gtest/include/gtest/gtest.h" #include "third_party/blink/renderer/platform/wtf/text/string_builder.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/decimal.cc b/chromium/third_party/blink/renderer/platform/wtf/decimal.cc index 58720c931f3..c1dc5537ed9 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/decimal.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/decimal.cc @@ -34,6 +34,7 @@ #include <cfloat> #include "base/macros.h" +#include "base/notreached.h" #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h" #include "third_party/blink/renderer/platform/wtf/math_extras.h" #include "third_party/blink/renderer/platform/wtf/text/string_builder.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/deque.h b/chromium/third_party/blink/renderer/platform/wtf/deque.h index 3a3c59e071f..3cad25b9956 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/deque.h +++ b/chromium/third_party/blink/renderer/platform/wtf/deque.h @@ -613,7 +613,7 @@ inline void Deque<T, inlineCapacity, Allocator>::erase(wtf_size_t position) { template <typename T, wtf_size_t inlineCapacity, typename Allocator> inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase() - : deque_(0) {} + : deque_(nullptr) {} template <typename T, wtf_size_t inlineCapacity, typename Allocator> inline DequeIteratorBase<T, inlineCapacity, Allocator>::DequeIteratorBase( diff --git a/chromium/third_party/blink/renderer/platform/wtf/hash_functions.h b/chromium/third_party/blink/renderer/platform/wtf/hash_functions.h index 9b9ec92aec7..2983b6c4977 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/hash_functions.h +++ b/chromium/third_party/blink/renderer/platform/wtf/hash_functions.h @@ -27,6 +27,7 @@ #include "base/bit_cast.h" #include "base/memory/scoped_refptr.h" #include "build/build_config.h" +#include "third_party/blink/renderer/platform/wtf/hash_table_deleted_value_type.h" #include "third_party/blink/renderer/platform/wtf/std_lib_extras.h" namespace WTF { @@ -277,6 +278,59 @@ struct DefaultHash<std::pair<T, U>> { using Hash = PairHash<T, U>; }; +// Wrapper for integral type to extend to have 0 and max keys. +template <typename T> +struct IntegralWithAllKeys { + IntegralWithAllKeys() : IntegralWithAllKeys(0, ValueType::kEmpty) {} + explicit IntegralWithAllKeys(T value) + : IntegralWithAllKeys(value, ValueType::kValid) {} + explicit IntegralWithAllKeys(HashTableDeletedValueType) + : IntegralWithAllKeys(0, ValueType::kDeleted) {} + + bool IsHashTableDeletedValue() const { + return value_type_ == ValueType::kDeleted; + } + + unsigned Hash() const { + return HashInts(value_, static_cast<unsigned>(value_type_)); + } + + bool operator==(const IntegralWithAllKeys& b) const { + return value_ == b.value_ && value_type_ == b.value_type_; + } + + private: + enum class ValueType : uint8_t { kEmpty, kValid, kDeleted }; + + IntegralWithAllKeys(T value, ValueType value_type) + : value_(value), value_type_(value_type) { + static_assert(std::is_integral<T>::value, + "Only integral types are supported."); + } + + T value_; + ValueType value_type_; +}; + +// Specialization for integral type to have all possible values for key +// including 0 and max. +template <typename T> +struct IntegralWithAllKeysHash { + static unsigned GetHash(const IntegralWithAllKeys<T>& key) { + return key.Hash(); + } + static bool Equal(const IntegralWithAllKeys<T>& a, + const IntegralWithAllKeys<T>& b) { + return a == b; + } + static const bool safe_to_compare_to_empty_or_deleted = true; +}; + +template <typename T> +struct DefaultHash<IntegralWithAllKeys<T>> { + using Hash = IntegralWithAllKeysHash<T>; +}; + } // namespace WTF using WTF::DefaultHash; diff --git a/chromium/third_party/blink/renderer/platform/wtf/hash_traits.h b/chromium/third_party/blink/renderer/platform/wtf/hash_traits.h index f5149002584..19dfe94dddf 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/hash_traits.h +++ b/chromium/third_party/blink/renderer/platform/wtf/hash_traits.h @@ -231,6 +231,12 @@ struct SimpleClassHashTraits : GenericHashTraits<T> { } }; +// Default traits disallow both 0 and max as keys -- use these traits to allow +// all values as keys. +template <typename T> +struct HashTraits<IntegralWithAllKeys<T>> + : SimpleClassHashTraits<IntegralWithAllKeys<T>> {}; + template <typename P> struct HashTraits<scoped_refptr<P>> : SimpleClassHashTraits<scoped_refptr<P>> { static_assert(sizeof(void*) == sizeof(scoped_refptr<P>), diff --git a/chromium/third_party/blink/renderer/platform/wtf/linked_hash_set.h b/chromium/third_party/blink/renderer/platform/wtf/linked_hash_set.h index 87f30a5e433..a84feeba20c 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/linked_hash_set.h +++ b/chromium/third_party/blink/renderer/platform/wtf/linked_hash_set.h @@ -1037,7 +1037,8 @@ class NewLinkedHashSet { } template <typename VisitorDispatcher, typename A = Allocator> - std::enable_if_t<A::kIsGarbageCollected> Trace(VisitorDispatcher visitor) { + std::enable_if_t<A::kIsGarbageCollected> Trace( + VisitorDispatcher visitor) const { value_to_index_.Trace(visitor); list_.Trace(visitor); } diff --git a/chromium/third_party/blink/renderer/platform/wtf/stack_util.cc b/chromium/third_party/blink/renderer/platform/wtf/stack_util.cc index 1aaaa1c60d2..f8aa9d89e38 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/stack_util.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/stack_util.cc @@ -6,6 +6,7 @@ #include "third_party/blink/renderer/platform/wtf/stack_util.h" +#include "base/notreached.h" #include "third_party/blink/renderer/platform/wtf/assertions.h" #include "third_party/blink/renderer/platform/wtf/threading.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/ascii_ctype.h b/chromium/third_party/blink/renderer/platform/wtf/text/ascii_ctype.h index b152126b544..de982bb0e29 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/ascii_ctype.h +++ b/chromium/third_party/blink/renderer/platform/wtf/text/ascii_ctype.h @@ -29,6 +29,7 @@ #ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_ASCII_CTYPE_H_ #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_ASCII_CTYPE_H_ +#include "base/check_op.h" #include "third_party/blink/renderer/platform/wtf/assertions.h" #include "third_party/blink/renderer/platform/wtf/text/unicode.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/ascii_fast_path.h b/chromium/third_party/blink/renderer/platform/wtf/text/ascii_fast_path.h index bb2566fadfe..7a15023d847 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/ascii_fast_path.h +++ b/chromium/third_party/blink/renderer/platform/wtf/text/ascii_fast_path.h @@ -27,6 +27,7 @@ #include "base/compiler_specific.h" #include "build/build_config.h" #include "third_party/blink/renderer/platform/wtf/std_lib_extras.h" +#include "third_party/blink/renderer/platform/wtf/text/ascii_ctype.h" #include "third_party/blink/renderer/platform/wtf/text/unicode.h" #if defined(OS_MACOSX) && defined(ARCH_CPU_X86_FAMILY) @@ -77,8 +78,8 @@ inline bool IsAllASCII(MachineWord word) { // Note: This function assume the input is likely all ASCII, and // does not leave early if it is not the case. template <typename CharacterType> -inline bool CharactersAreAllASCII(const CharacterType* characters, - size_t length) { +ALWAYS_INLINE bool CharactersAreAllASCII(const CharacterType* characters, + size_t length) { DCHECK_GT(length, 0u); MachineWord all_char_bits = 0; const CharacterType* end = characters + length; @@ -108,6 +109,88 @@ inline bool CharactersAreAllASCII(const CharacterType* characters, return !(all_char_bits & non_ascii_bit_mask); } +template <typename CharacterType> +ALWAYS_INLINE bool IsLowerASCII(const CharacterType* characters, + size_t length) { + bool contains_upper_case = false; + for (wtf_size_t i = 0; i < length; i++) { + contains_upper_case |= IsASCIIUpper(characters[i]); + } + return !contains_upper_case; +} + +template <typename CharacterType> +ALWAYS_INLINE bool IsUpperASCII(const CharacterType* characters, + size_t length) { + bool contains_lower_case = false; + for (wtf_size_t i = 0; i < length; i++) { + contains_lower_case |= IsASCIILower(characters[i]); + } + return !contains_lower_case; +} + +class LowerConverter { + public: + template <typename CharType> + ALWAYS_INLINE static bool IsCorrectCase(CharType* characters, size_t length) { + return IsLowerASCII(characters, length); + } + + template <typename CharType> + ALWAYS_INLINE static CharType Convert(CharType ch) { + return ToASCIILower(ch); + } +}; + +class UpperConverter { + public: + template <typename CharType> + ALWAYS_INLINE static bool IsCorrectCase(CharType* characters, size_t length) { + return IsUpperASCII(characters, length); + } + + template <typename CharType> + ALWAYS_INLINE static CharType Convert(CharType ch) { + return ToASCIIUpper(ch); + } +}; + +template <typename StringType, typename Converter, typename Allocator> +ALWAYS_INLINE typename Allocator::ResultStringType ConvertASCIICase( + const StringType& string, + Converter&& converter, + Allocator&& allocator) { + CHECK_LE(string.length(), std::numeric_limits<wtf_size_t>::max()); + + // First scan the string for uppercase and non-ASCII characters: + wtf_size_t length = string.length(); + if (string.Is8Bit()) { + if (converter.IsCorrectCase(string.Characters8(), length)) { + return allocator.CoerceOriginal(string); + } + + LChar* data8; + auto new_impl = allocator.Alloc(length, data8); + + for (wtf_size_t i = 0; i < length; ++i) { + data8[i] = converter.Convert(string.Characters8()[i]); + } + return new_impl; + } + + if (converter.IsCorrectCase(string.Characters16(), length)) { + return allocator.CoerceOriginal(string); + } + + UChar* data16; + auto new_impl = allocator.Alloc(length, data16); + + for (wtf_size_t i = 0; i < length; ++i) { + data16[i] = converter.Convert(string.Characters16()[i]); + } + return new_impl; +} + inline void CopyLCharsFromUCharSource(LChar* destination, const UChar* source, size_t length) { diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/atomic_string_table.cc b/chromium/third_party/blink/renderer/platform/wtf/text/atomic_string_table.cc index 2d9af4b7184..2692f849855 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/atomic_string_table.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/text/atomic_string_table.cc @@ -4,40 +4,15 @@ #include "third_party/blink/renderer/platform/wtf/text/atomic_string_table.h" +#include "base/notreached.h" #include "third_party/blink/renderer/platform/wtf/text/string_hash.h" #include "third_party/blink/renderer/platform/wtf/text/utf8.h" namespace WTF { -AtomicStringTable::AtomicStringTable() { - for (StringImpl* string : StringImpl::AllStaticStrings().Values()) - Add(string); -} - -AtomicStringTable::~AtomicStringTable() { - for (StringImpl* string : table_) { - if (!string->IsStatic()) { - DCHECK(string->IsAtomic()); - string->SetIsAtomic(false); - } - } -} - -void AtomicStringTable::ReserveCapacity(unsigned size) { - table_.ReserveCapacityForSize(size); -} - -template <typename T, typename HashTranslator> -scoped_refptr<StringImpl> AtomicStringTable::AddToStringTable(const T& value) { - HashSet<StringImpl*>::AddResult add_result = - table_.AddWithTranslator<HashTranslator>(value); - - // If the string is newly-translated, then we need to adopt it. - // The boolean in the pair tells us if that is so. - return add_result.is_new_entry ? base::AdoptRef(*add_result.stored_value) - : *add_result.stored_value; -} +namespace { +// TODO(ajwong): consider replacing with a span in the future. template <typename CharacterType> struct HashTranslatorCharBuffer { const CharacterType* s; @@ -147,6 +122,85 @@ struct HashAndUTF8CharactersTranslator { } }; +struct StringViewLookupTranslator { + static unsigned GetHash(const StringView& buf) { + StringImpl* shared_impl = buf.SharedImpl(); + if (LIKELY(shared_impl)) + return shared_impl->GetHash(); + + if (buf.Is8Bit()) { + return StringHasher::ComputeHashAndMaskTop8Bits(buf.Characters8(), + buf.length()); + } else { + return StringHasher::ComputeHashAndMaskTop8Bits(buf.Characters16(), + buf.length()); + } + } + + static bool Equal(StringImpl* const& str, const StringView& buf) { + return *str == buf; + } +}; + +struct LowercaseStringViewLookupTranslator { + template <typename CharType> + static UChar ToASCIILowerUChar(CharType ch) { + return ToASCIILower(ch); + } + + static unsigned GetHash(const StringView& buf) { + // If possible, use cached hash if the string is lowercased. + StringImpl* shared_impl = buf.SharedImpl(); + if (LIKELY(shared_impl && buf.IsLowerASCII())) + return shared_impl->GetHash(); + + if (buf.Is8Bit()) { + return StringHasher::ComputeHashAndMaskTop8Bits<LChar, + ToASCIILowerUChar<LChar>>( + buf.Characters8(), buf.length()); + } else { + return StringHasher::ComputeHashAndMaskTop8Bits<UChar, + ToASCIILowerUChar<UChar>>( + buf.Characters16(), buf.length()); + } + } + + static bool Equal(StringImpl* const& str, const StringView& buf) { + return EqualIgnoringASCIICase(StringView(str), buf); + } +}; + +} // namespace + +AtomicStringTable::AtomicStringTable() { + for (StringImpl* string : StringImpl::AllStaticStrings().Values()) + Add(string); +} + +AtomicStringTable::~AtomicStringTable() { + for (StringImpl* string : table_) { + if (!string->IsStatic()) { + DCHECK(string->IsAtomic()); + string->SetIsAtomic(false); + } + } +} + +void AtomicStringTable::ReserveCapacity(unsigned size) { + table_.ReserveCapacityForSize(size); +} + +template <typename T, typename HashTranslator> +scoped_refptr<StringImpl> AtomicStringTable::AddToStringTable(const T& value) { + HashSet<StringImpl*>::AddResult add_result = + table_.AddWithTranslator<HashTranslator>(value); + + // If the string is newly-translated, then we need to adopt it. + // The boolean in the pair tells us if that is so. + return add_result.is_new_entry ? base::AdoptRef(*add_result.stored_value) + : *add_result.stored_value; +} + scoped_refptr<StringImpl> AtomicStringTable::Add(const UChar* s, unsigned length) { if (!s) @@ -220,6 +274,67 @@ scoped_refptr<StringImpl> AtomicStringTable::AddUTF8( HashAndUTF8CharactersTranslator>(buffer); } +AtomicStringTable::WeakResult AtomicStringTable::WeakFindSlow( + StringImpl* string) { + DCHECK(string->length()); + const auto& it = table_.find(string); + if (it == table_.end()) + return WeakResult(); + return WeakResult(*it); +} + +AtomicStringTable::WeakResult AtomicStringTable::WeakFindSlow( + const StringView& string) { + DCHECK(string.length()); + const auto& it = table_.Find<StringViewLookupTranslator>(string); + if (it == table_.end()) + return WeakResult(); + return WeakResult(*it); +} + +AtomicStringTable::WeakResult AtomicStringTable::WeakFindLowercasedSlow( + const StringView& string) { + DCHECK(string.length()); + const auto& it = table_.Find<LowercaseStringViewLookupTranslator>(string); + if (it == table_.end()) + return WeakResult(); + return WeakResult(*it); +} + +AtomicStringTable::WeakResult AtomicStringTable::WeakFind(const LChar* chars, + unsigned length) { + if (!chars) + return WeakResult(); + + // Mirror the empty logic in Add(). + if (!length) + return WeakResult(StringImpl::empty_); + + LCharBuffer buffer = {chars, length}; + const auto& it = table_.Find<LCharBufferTranslator>(buffer); + if (it == table_.end()) + return WeakResult(); + + return WeakResult(*it); +} + +AtomicStringTable::WeakResult AtomicStringTable::WeakFind(const UChar* chars, + unsigned length) { + if (!chars) + return WeakResult(); + + // Mirror the empty logic in Add(). + if (!length) + return WeakResult(StringImpl::empty_); + + UCharBuffer buffer = {chars, length}; + const auto& it = table_.Find<UCharBufferTranslator>(buffer); + if (it == table_.end()) + return WeakResult(); + + return WeakResult(*it); +} + void AtomicStringTable::Remove(StringImpl* string) { DCHECK(string->IsAtomic()); auto iterator = table_.find(string); diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/atomic_string_table.h b/chromium/third_party/blink/renderer/platform/wtf/text/atomic_string_table.h index 33dce8b8485..78c06758a0a 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/atomic_string_table.h +++ b/chromium/third_party/blink/renderer/platform/wtf/text/atomic_string_table.h @@ -46,6 +46,78 @@ class WTF_EXPORT AtomicStringTable final { scoped_refptr<StringImpl> AddUTF8(const char* characters_start, const char* characters_end); + // Returned as part of the WeakFind() APIs below. Represents the result of + // the non-creating lookup within the AtomicStringTable. See the WeakFind() + // documentation for a description of how it can be used. + class WeakResult { + public: + WeakResult() = default; + explicit WeakResult(StringImpl* str) + : ptr_value_(reinterpret_cast<uintptr_t>(str)) { + CHECK(!str || str->IsAtomic() || str == StringImpl::empty_); + } + + bool operator==(const AtomicString& s) const { return *this == s.Impl(); } + bool operator==(const String& s) const { return *this == s.Impl(); } + bool operator==(const StringImpl* str) const { + return reinterpret_cast<uintptr_t>(str) == ptr_value_; + } + + bool IsNull() const { return ptr_value_ != 0; } + + private: + // Contains the pointer a string in a non-deferenceable form. Do NOT cast + // back to a StringImpl and dereference. The object may no longer be alive. + uintptr_t ptr_value_ = 0; + }; + + // Checks for existence of a string in the AtomicStringTable without + // unnecessarily creating an AtomicString. Useful to optimize fast-path + // non-existence checks inside collections of AtomicStrings. + // + // Specifically, if WeakFind() returns an IsNull() WeakResult, then a + // collection search can be skipped because the AtomicString cannot exist + // in the collection. If WeakFind() returns a non-null WeakResult, then + // assuming the target collection has no concurrent access, this lookup + // can be reused to check for existence in the collection without + // requiring either an AtomicString collection or another lookup within + // the AtomicStringTable. + WeakResult WeakFind(StringImpl* string) { + // Mirror the empty logic in Add(). + if (UNLIKELY(!string->length())) + return WeakResult(StringImpl::empty_); + + if (LIKELY(string->IsAtomic())) + return WeakResult(string); + + return WeakFindSlow(string); + } + + WeakResult WeakFind(const StringView& string) { + // Mirror the empty logic in Add(). + if (UNLIKELY(!string.length())) + return WeakResult(StringImpl::empty_); + + if (LIKELY(string.IsAtomic())) + return WeakResult(string.SharedImpl()); + + return WeakFindSlow(string); + } + + WeakResult WeakFind(const LChar* chars, unsigned length); + WeakResult WeakFind(const UChar* chars, unsigned length); + + WeakResult WeakFindLowercased(const StringView& string) { + // Mirror the empty logic in Add(). + if (UNLIKELY(!string.length())) + return WeakResult(StringImpl::empty_); + + if (LIKELY(string.IsAtomic() && string.IsLowerASCII())) + return WeakResult(string.SharedImpl()); + + return WeakFindLowercasedSlow(string); + } + // This is for ~StringImpl to unregister a string before destruction since // the table is holding weak pointers. It should not be used directly. void Remove(StringImpl*); @@ -54,6 +126,10 @@ class WTF_EXPORT AtomicStringTable final { template <typename T, typename HashTranslator> inline scoped_refptr<StringImpl> AddToStringTable(const T& value); + WeakResult WeakFindSlow(StringImpl*); + WeakResult WeakFindSlow(const StringView&); + WeakResult WeakFindLowercasedSlow(const StringView& string); + HashSet<StringImpl*> table_; DISALLOW_COPY_AND_ASSIGN(AtomicStringTable); diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/case_map.cc b/chromium/third_party/blink/renderer/platform/wtf/text/case_map.cc index 729497cf0f0..3b0bcf074ef 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/case_map.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/text/case_map.cc @@ -6,6 +6,7 @@ #include <unicode/casemap.h> +#include "base/notreached.h" #include "third_party/blink/renderer/platform/wtf/text/atomic_string.h" #include "third_party/blink/renderer/platform/wtf/text/character_names.h" #include "third_party/blink/renderer/platform/wtf/text/string_impl.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/character_visitor.h b/chromium/third_party/blink/renderer/platform/wtf/text/character_visitor.h new file mode 100644 index 00000000000..2c41ca5671c --- /dev/null +++ b/chromium/third_party/blink/renderer/platform/wtf/text/character_visitor.h @@ -0,0 +1,42 @@ +// Copyright 2020 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_CHARACTER_VISITOR_H_ +#define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_CHARACTER_VISITOR_H_ + +namespace WTF { + +// Visits the characters of a WTF::String, StringView or compatible type. +// +// Intended to be used with a generic lambda or other functor overloaded to +// handle either LChar* or UChar*. Reduces code duplication in many cases. +// The functor should return the same type in both branches. +// +// Callers should ensure that characters exist (i.e. the string is not null) +// first. +// +// Example: +// +// if (string.IsNull()) +// return false; +// +// return WTF::VisitCharacters(string, [&](const auto* chars, unsigned len) { +// bool contains_space = false; +// for (unsigned i = 0; i < len; i++) +// contains_space |= IsASCIISpace(chars[i]); +// return contains_space; +// }); +// +// This will instantiate the functor for both LChar (8-bit) and UChar (16-bit) +// automatically. +template <typename StringType, typename Functor> +decltype(auto) VisitCharacters(const StringType& string, + const Functor& functor) { + return string.Is8Bit() ? functor(string.Characters8(), string.length()) + : functor(string.Characters16(), string.length()); +} + +} // namespace WTF + +#endif // THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_CHARACTER_VISITOR_H_ diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/math_transform.cc b/chromium/third_party/blink/renderer/platform/wtf/text/math_transform.cc index d8a257029d6..1d76435dbbb 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/math_transform.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/text/math_transform.cc @@ -4,6 +4,7 @@ #include "third_party/blink/renderer/platform/wtf/text/math_transform.h" +#include "base/check.h" #include "third_party/blink/renderer/platform/wtf/text/ascii_ctype.h" #include "third_party/blink/renderer/platform/wtf/text/character_names.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/number_parsing_options.h b/chromium/third_party/blink/renderer/platform/wtf/text/number_parsing_options.h index 4b5ea50a60d..25f5faa6a3b 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/number_parsing_options.h +++ b/chromium/third_party/blink/renderer/platform/wtf/text/number_parsing_options.h @@ -5,7 +5,7 @@ #ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_NUMBER_PARSING_OPTIONS_H_ #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_NUMBER_PARSING_OPTIONS_H_ -#include "base/logging.h" +#include "base/check_op.h" #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/string_hasher.h b/chromium/third_party/blink/renderer/platform/wtf/text/string_hasher.h index 492cb7bb114..83673c53d79 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/string_hasher.h +++ b/chromium/third_party/blink/renderer/platform/wtf/text/string_hasher.h @@ -196,8 +196,9 @@ class StringHasher { } private: + // The StringHasher works on UChar so all converters should normalize input + // data into being a UChar. static UChar DefaultConverter(UChar character) { return character; } - static UChar DefaultConverter(LChar character) { return character; } unsigned AvalancheBits() const { diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/string_impl.cc b/chromium/third_party/blink/renderer/platform/wtf/text/string_impl.cc index a02a45ef137..6a9fcfd1335 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/string_impl.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/text/string_impl.cc @@ -338,79 +338,26 @@ wtf_size_t StringImpl::CopyTo(UChar* buffer, return number_of_characters_to_copy; } -scoped_refptr<StringImpl> StringImpl::LowerASCII() { - // First scan the string for uppercase and non-ASCII characters: - if (Is8Bit()) { - wtf_size_t first_index_to_be_lowered = length_; - for (wtf_size_t i = 0; i < length_; ++i) { - LChar ch = Characters8()[i]; - if (IsASCIIUpper(ch)) { - first_index_to_be_lowered = i; - break; - } - } - - // Nothing to do if the string is all ASCII with no uppercase. - if (first_index_to_be_lowered == length_) { - return this; - } - - LChar* data8; - scoped_refptr<StringImpl> new_impl = CreateUninitialized(length_, data8); - memcpy(data8, Characters8(), first_index_to_be_lowered); +class StringImplAllocator { + public: + using ResultStringType = scoped_refptr<StringImpl>; - for (wtf_size_t i = first_index_to_be_lowered; i < length_; ++i) { - LChar ch = Characters8()[i]; - data8[i] = IsASCIIUpper(ch) ? ToASCIILower(ch) : ch; - } - return new_impl; + template <typename CharType> + scoped_refptr<StringImpl> Alloc(wtf_size_t length, CharType*& buffer) { + return StringImpl::CreateUninitialized(length, buffer); } - bool no_upper = true; - UChar ored = 0; - const UChar* end = Characters16() + length_; - for (const UChar* chp = Characters16(); chp != end; ++chp) { - if (IsASCIIUpper(*chp)) - no_upper = false; - ored |= *chp; + scoped_refptr<StringImpl> CoerceOriginal(const StringImpl& string) { + return const_cast<StringImpl*>(&string); } - // Nothing to do if the string is all ASCII with no uppercase. - if (no_upper && !(ored & ~0x7F)) - return this; - - CHECK_LE(length_, static_cast<wtf_size_t>(numeric_limits<wtf_size_t>::max())); - wtf_size_t length = length_; - - UChar* data16; - scoped_refptr<StringImpl> new_impl = CreateUninitialized(length_, data16); +}; - for (wtf_size_t i = 0; i < length; ++i) { - UChar c = Characters16()[i]; - data16[i] = IsASCIIUpper(c) ? ToASCIILower(c) : c; - } - return new_impl; +scoped_refptr<StringImpl> StringImpl::LowerASCII() { + return ConvertASCIICase(*this, LowerConverter(), StringImplAllocator()); } scoped_refptr<StringImpl> StringImpl::UpperASCII() { - if (Is8Bit()) { - LChar* data8; - scoped_refptr<StringImpl> new_impl = CreateUninitialized(length_, data8); - - for (wtf_size_t i = 0; i < length_; ++i) { - LChar c = Characters8()[i]; - data8[i] = IsASCIILower(c) ? ToASCIIUpper(c) : c; - } - return new_impl; - } - - UChar* data16; - scoped_refptr<StringImpl> new_impl = CreateUninitialized(length_, data16); - - for (wtf_size_t i = 0; i < length_; ++i) { - UChar c = Characters16()[i]; - data16[i] = IsASCIILower(c) ? ToASCIIUpper(c) : c; - } - return new_impl; + return ConvertASCIICase(*this, UpperConverter(), StringImplAllocator()); } scoped_refptr<StringImpl> StringImpl::Fill(UChar character) { diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/string_view.cc b/chromium/third_party/blink/renderer/platform/wtf/text/string_view.cc index 6f0bb8874b6..9a56ddff705 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/string_view.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/text/string_view.cc @@ -9,6 +9,26 @@ #include "third_party/blink/renderer/platform/wtf/text/wtf_string.h" namespace WTF { +namespace { +class StackStringViewAllocator { + public: + explicit StackStringViewAllocator( + StringView::StackBackingStore& backing_store) + : backing_store_(backing_store) {} + using ResultStringType = StringView; + + template <typename CharType> + StringView Alloc(wtf_size_t length, CharType*& buffer) { + buffer = backing_store_.Realloc<CharType>(length); + return StringView(buffer, length); + } + + StringView CoerceOriginal(StringView string) { return string; } + + private: + StringView::StackBackingStore& backing_store_; +}; +} // namespace StringView::StringView(const UChar* chars) : StringView(chars, chars ? LengthOfNullTerminatedString(chars) : 0) {} @@ -109,4 +129,10 @@ bool EqualIgnoringASCIICase(const StringView& a, const StringView& b) { return EqualIgnoringASCIICase(a.Characters16(), b.Characters16(), a.length()); } +StringView StringView::LowerASCIIMaybeUsingBuffer( + StackBackingStore& buffer) const { + return ConvertASCIICase(*this, LowerConverter(), + StackStringViewAllocator(buffer)); +} + } // namespace WTF diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/string_view.h b/chromium/third_party/blink/renderer/platform/wtf/text/string_view.h index 06611ab2a58..0178c7b0c59 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/string_view.h +++ b/chromium/third_party/blink/renderer/platform/wtf/text/string_view.h @@ -33,6 +33,47 @@ class WTF_EXPORT StringView { DISALLOW_NEW(); public: + // A buffer that allows for short strings to be held on the stack during a + // transform. This is a performance optimization for very hot paths and + // should rarely need to be used. + class StackBackingStore { + public: + // Returns a pointer to a buffer of size |length| that is valid for as long + // the StackBackingStore object is alive and Realloc() has not been called + // again. + template <typename CharT> + CharT* Realloc(int length) { + size_t size = length * sizeof(CharT); + if (UNLIKELY(size > sizeof(stackbuf16_))) { + heapbuf_.reset(reinterpret_cast<char*>( + WTF::Partitions::BufferMalloc(size, "StackBackingStore"))); + return reinterpret_cast<CharT*>(heapbuf_.get()); + } + + // If the Realloc() shrinks the buffer size, |heapbuf_| will keep a copy + // of the old string. A reset can be added here, but given this is a + // transient usage, deferring to the destructor is just as good and avoids + // another branch. + static_assert(alignof(decltype(stackbuf16_)) % alignof(CharT) == 0, + "stack buffer must be sufficiently aligned"); + return reinterpret_cast<CharT*>(&stackbuf16_[0]); + } + + public: + struct BufferDeleter { + void operator()(void* buffer) { WTF::Partitions::BufferFree(buffer); } + }; + + static_assert(sizeof(UChar) != sizeof(char), + "A char array will trigger -fstack-protect an produce " + "overkill stack canaries all over v8 bindings"); + + // The size 64 is just a guess on a good size. No data was used in its + // selection. + UChar stackbuf16_[64]; + std::unique_ptr<char[], BufferDeleter> heapbuf_; + }; + // Null string. StringView() { Clear(); } @@ -70,7 +111,7 @@ class WTF_EXPORT StringView { // From a literal string or LChar buffer: StringView(const LChar* chars, unsigned length) - : impl_(StringImpl::empty_), characters8_(chars), length_(length) {} + : impl_(StringImpl::empty_), bytes_(chars), length_(length) {} StringView(const char* chars, unsigned length) : StringView(reinterpret_cast<const LChar*>(chars), length) {} StringView(const LChar* chars) @@ -83,9 +124,7 @@ class WTF_EXPORT StringView { // From a wide literal string or UChar buffer. StringView(const UChar* chars, unsigned length) - : impl_(StringImpl::empty16_bit_), - characters16_(chars), - length_(length) {} + : impl_(StringImpl::empty16_bit_), bytes_(chars), length_(length) {} StringView(const UChar* chars); StringView(const char16_t* chars) : StringView(reinterpret_cast<const UChar*>(chars)) {} @@ -104,6 +143,15 @@ class WTF_EXPORT StringView { return impl_->Is8Bit(); } + bool IsAtomic() const { return SharedImpl() && SharedImpl()->IsAtomic(); } + + bool IsLowerASCII() const { + if (Is8Bit()) { + return WTF::IsLowerASCII(Characters8(), length()); + } + return WTF::IsLowerASCII(Characters16(), length()); + } + void Clear(); UChar operator[](unsigned i) const { @@ -115,22 +163,22 @@ class WTF_EXPORT StringView { const LChar* Characters8() const { DCHECK(Is8Bit()); - return characters8_; + return static_cast<const LChar*>(bytes_); } const UChar* Characters16() const { DCHECK(!Is8Bit()); - return characters16_; + return static_cast<const UChar*>(bytes_); } base::span<const LChar> Span8() const { DCHECK(Is8Bit()); - return {characters8_, length_}; + return {static_cast<const LChar*>(bytes_), length_}; } base::span<const UChar> Span16() const { DCHECK(!Is8Bit()); - return {characters16_, length_}; + return {static_cast<const UChar*>(bytes_), length_}; } UChar32 CodepointAt(unsigned i) const { @@ -157,6 +205,15 @@ class WTF_EXPORT StringView { return nullptr; } + // This will return a StringView with a version of |this| that has all ASCII + // characters lowercased. The returned StringView is guarantee to be valid for + // as long as |backing_store| is valid. + // + // The odd lifetime of the returned object occurs because lowercasing may + // require allocation. When that happens, |backing_store| is used as the + // backing store and the returned StringView has the same lifetime. + StringView LowerASCIIMaybeUsingBuffer(StackBackingStore& backing_store) const; + String ToString() const; AtomicString ToAtomicString() const; @@ -174,11 +231,7 @@ class WTF_EXPORT StringView { #else StringImpl* impl_; #endif - union { - const LChar* characters8_; - const UChar* characters16_; - const void* bytes_; - }; + const void* bytes_; unsigned length_; }; @@ -188,9 +241,9 @@ inline StringView::StringView(const StringView& view, : impl_(view.impl_), length_(length) { SECURITY_DCHECK(offset + length <= view.length()); if (Is8Bit()) - characters8_ = view.Characters8() + offset; + bytes_ = view.Characters8() + offset; else - characters16_ = view.Characters16() + offset; + bytes_ = view.Characters16() + offset; } inline StringView::StringView(const StringImpl* impl) { @@ -236,9 +289,9 @@ inline void StringView::Set(const StringImpl& impl, length_ = length; impl_ = const_cast<StringImpl*>(&impl); if (impl.Is8Bit()) - characters8_ = impl.Characters8() + offset; + bytes_ = impl.Characters8() + offset; else - characters16_ = impl.Characters16() + offset; + bytes_ = impl.Characters16() + offset; } // Unicode aware case insensitive string matching. Non-ASCII characters might diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/text_codec.cc b/chromium/third_party/blink/renderer/platform/wtf/text/text_codec.cc index 2943851dc39..fbe7de479dd 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/text_codec.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/text/text_codec.cc @@ -25,6 +25,7 @@ */ #include "third_party/blink/renderer/platform/wtf/text/text_codec.h" +#include "base/notreached.h" namespace WTF { diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/text_codec.h b/chromium/third_party/blink/renderer/platform/wtf/text/text_codec.h index 3d4f4108d57..4f524c5500e 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/text_codec.h +++ b/chromium/third_party/blink/renderer/platform/wtf/text/text_codec.h @@ -29,6 +29,7 @@ #include <memory> #include "base/macros.h" +#include "base/notreached.h" #include "third_party/blink/renderer/platform/wtf/forward.h" #include "third_party/blink/renderer/platform/wtf/text/unicode.h" #include "third_party/blink/renderer/platform/wtf/text/wtf_string.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/text/text_codec_icu.cc b/chromium/third_party/blink/renderer/platform/wtf/text/text_codec_icu.cc index 810d1cd9181..b62573550a1 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/text/text_codec_icu.cc +++ b/chromium/third_party/blink/renderer/platform/wtf/text/text_codec_icu.cc @@ -32,6 +32,7 @@ #include <unicode/ucnv_cb.h> #include "base/memory/ptr_util.h" +#include "base/notreached.h" #include "third_party/blink/renderer/platform/wtf/assertions.h" #include "third_party/blink/renderer/platform/wtf/text/character_names.h" #include "third_party/blink/renderer/platform/wtf/text/string_builder.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/threading.h b/chromium/third_party/blink/renderer/platform/wtf/threading.h index 0a21c3fb321..0943e791cf5 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/threading.h +++ b/chromium/third_party/blink/renderer/platform/wtf/threading.h @@ -33,7 +33,7 @@ #include <stdint.h> #include <memory> -#include "base/logging.h" +#include "base/check_op.h" #include "base/macros.h" #include "base/threading/platform_thread.h" #include "build/build_config.h" diff --git a/chromium/third_party/blink/renderer/platform/wtf/tree_node.h b/chromium/third_party/blink/renderer/platform/wtf/tree_node.h index b25022a62b9..6aa4e744cfb 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/tree_node.h +++ b/chromium/third_party/blink/renderer/platform/wtf/tree_node.h @@ -31,6 +31,7 @@ #ifndef THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TREE_NODE_H_ #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TREE_NODE_H_ +#include "base/check_op.h" #include "third_party/blink/renderer/platform/wtf/assertions.h" namespace WTF { diff --git a/chromium/third_party/blink/renderer/platform/wtf/type_traits.h b/chromium/third_party/blink/renderer/platform/wtf/type_traits.h index 44c6f9219ca..60893080de3 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/type_traits.h +++ b/chromium/third_party/blink/renderer/platform/wtf/type_traits.h @@ -132,6 +132,19 @@ class Visitor; namespace WTF { +namespace internal { +// IsTraceMethodConst is used to verify that all Trace methods are marked as +// const. It is equivalent to IsTraceable but for a non-const object. +template <typename T, typename = void> +struct IsTraceMethodConst : std::false_type {}; + +template <typename T> +struct IsTraceMethodConst<T, + base::void_t<decltype(std::declval<const T>().Trace( + std::declval<blink::Visitor*>()))>> + : std::true_type {}; +} // namespace internal + template <typename T, typename = void> struct IsTraceable : std::false_type { // Fail on incomplete types. @@ -142,7 +155,13 @@ struct IsTraceable : std::false_type { template <typename T> struct IsTraceable<T, base::void_t<decltype(std::declval<T>().Trace( - std::declval<blink::Visitor*>()))>> : std::true_type {}; + std::declval<blink::Visitor*>()))>> : std::true_type { + // All Trace methods should be marked as const. If an object of type + // 'T' is traceable then any object of type 'const T' should also + // be traceable. + static_assert(internal::IsTraceMethodConst<T>(), + "Trace methods should be marked as const."); +}; template <typename T, typename U> struct IsTraceable<std::pair<T, U>> diff --git a/chromium/third_party/blink/renderer/platform/wtf/vector.h b/chromium/third_party/blink/renderer/platform/wtf/vector.h index 267eb905013..959dffbf5f7 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/vector.h +++ b/chromium/third_party/blink/renderer/platform/wtf/vector.h @@ -74,6 +74,19 @@ class Deque; // If you want to change the behavior of your type, take a look at VectorTraits // (defined in VectorTraits.h), too. +// Tracing assumes the entire backing store is safe to access. To guarantee +// that, tracing a backing store starts by marking the whole backing store +// capacity as accessible. With concurrent marking enabled, annotating size +// changes could conflict with marking the whole store as accessible, causing +// a race. +#define MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, buffer, capacity, \ + old_size, new_size) \ + if (Allocator::kIsGarbageCollected && Allocator::IsIncrementalMarking()) { \ + ANNOTATE_CHANGE_SIZE(buffer, capacity, 0, capacity); \ + } else { \ + ANNOTATE_CHANGE_SIZE(buffer, capacity, old_size, new_size) \ + } + template <bool needsDestruction, typename T> struct VectorDestructor; @@ -848,8 +861,10 @@ class VectorBuffer : protected VectorBufferBase<T, Allocator> { DCHECK(other_source_begin); DCHECK_EQ(Buffer(), InlineBuffer()); DCHECK_EQ(other.Buffer(), other.InlineBuffer()); - ANNOTATE_CHANGE_SIZE(buffer_, inlineCapacity, size_, other.size_); - ANNOTATE_CHANGE_SIZE(other.buffer_, inlineCapacity, other.size_, size_); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, buffer_, inlineCapacity, + size_, other.size_); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, other.buffer_, + inlineCapacity, other.size_, size_); std::swap(size_, other.size_); } @@ -950,11 +965,10 @@ class VectorBuffer : protected VectorBufferBase<T, Allocator> { return unsafe_reinterpret_cast_ptr<const T*>(inline_buffer_); } - template <bool = Allocator::kIsGarbageCollected> - void InitInlinedBuffer() {} - template <> - void InitInlinedBuffer<true>() { - memset(&inline_buffer_, 0, kInlineBufferSize); + void InitInlinedBuffer() { + if (Allocator::kIsGarbageCollected) { + memset(&inline_buffer_, 0, kInlineBufferSize); + } } alignas(T) char inline_buffer_[kInlineBufferSize]; @@ -1536,7 +1550,8 @@ operator=(const Vector<T, inlineCapacity, Allocator>& other) { DCHECK(begin()); } - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, other.size()); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + other.size()); TypeOperations::Copy(other.begin(), other.begin() + size(), begin()); TypeOperations::UninitializedCopy(other.begin() + size(), other.end(), end()); size_ = other.size(); @@ -1565,7 +1580,8 @@ operator=(const Vector<T, otherCapacity, Allocator>& other) { DCHECK(begin()); } - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, other.size()); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + other.size()); TypeOperations::Copy(other.begin(), other.begin() + size(), begin()); TypeOperations::UninitializedCopy(other.begin() + size(), other.end(), end()); size_ = other.size(); @@ -1609,7 +1625,8 @@ operator=(std::initializer_list<T> elements) { DCHECK(begin()); } - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, input_size); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + input_size); TypeOperations::Copy(elements.begin(), elements.begin() + size_, begin()); TypeOperations::UninitializedCopy(elements.begin() + size_, elements.end(), end()); @@ -1662,7 +1679,8 @@ Vector<T, inlineCapacity, Allocator>::Fill(const T& val, wtf_size_t new_size) { DCHECK(begin()); } - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, new_size); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + new_size); std::fill(begin(), end(), val); TypeOperations::UninitializedFill(end(), begin() + new_size, val); size_ = new_size; @@ -1722,11 +1740,13 @@ inline void Vector<T, inlineCapacity, Allocator>::resize(wtf_size_t size) { if (size <= size_) { TypeOperations::Destruct(begin() + size, end()); ClearUnusedSlots(begin() + size, end()); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size); } else { if (size > capacity()) ExpandCapacity(size); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size); TypeOperations::Initialize(end(), begin() + size); } @@ -1738,7 +1758,8 @@ void Vector<T, inlineCapacity, Allocator>::Shrink(wtf_size_t size) { DCHECK_LE(size, size_); TypeOperations::Destruct(begin() + size, end()); ClearUnusedSlots(begin() + size, end()); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size); size_ = size; } @@ -1747,7 +1768,8 @@ void Vector<T, inlineCapacity, Allocator>::Grow(wtf_size_t size) { DCHECK_GE(size, size_); if (size > capacity()) ExpandCapacity(size); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size); TypeOperations::Initialize(end(), begin() + size); size_ = size; } @@ -1831,7 +1853,8 @@ template <typename U> ALWAYS_INLINE void Vector<T, inlineCapacity, Allocator>::push_back(U&& val) { DCHECK(Allocator::IsAllocationAllowed()); if (LIKELY(size() != capacity())) { - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ + 1); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size_ + 1); ConstructTraits<T, VectorTraits<T>, Allocator>::ConstructAndNotifyElement( end(), std::forward<U>(val)); ++size_; @@ -1849,7 +1872,8 @@ ALWAYS_INLINE T& Vector<T, inlineCapacity, Allocator>::emplace_back( if (UNLIKELY(size() == capacity())) ExpandCapacity(size() + 1); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ + 1); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size_ + 1); T* t = ConstructTraits<T, VectorTraits<T>, Allocator>::ConstructAndNotifyElement( end(), std::forward<Args>(args)...); @@ -1869,7 +1893,8 @@ void Vector<T, inlineCapacity, Allocator>::Append(const U* data, } CHECK_GE(new_size, size_); T* dest = end(); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, new_size); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + new_size); VectorCopier<VectorTraits<T>::kCanCopyWithMemcpy, T, Allocator>::UninitializedCopy(data, &data[data_size], dest); size_ = new_size; @@ -1884,7 +1909,8 @@ NOINLINE void Vector<T, inlineCapacity, Allocator>::AppendSlowCase(U&& val) { ptr = ExpandCapacity(size() + 1, ptr); DCHECK(begin()); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ + 1); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size_ + 1); ConstructTraits<T, VectorTraits<T>, Allocator>::ConstructAndNotifyElement( end(), std::forward<U>(*ptr)); ++size_; @@ -1933,7 +1959,8 @@ inline void Vector<T, inlineCapacity, Allocator>::insert(wtf_size_t position, data = ExpandCapacity(size() + 1, data); DCHECK(begin()); } - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ + 1); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size_ + 1); T* spot = begin() + position; TypeOperations::MoveOverlapping(spot, end(), spot + 1); ConstructTraits<T, VectorTraits<T>, Allocator>::ConstructAndNotifyElement( @@ -1954,7 +1981,8 @@ void Vector<T, inlineCapacity, Allocator>::insert(wtf_size_t position, DCHECK(begin()); } CHECK_GE(new_size, size_); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, new_size); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + new_size); T* spot = begin() + position; TypeOperations::MoveOverlapping(spot, end(), spot + data_size); VectorCopier<VectorTraits<T>::kCanCopyWithMemcpy, T, @@ -2011,7 +2039,8 @@ inline void Vector<T, inlineCapacity, Allocator>::EraseAt(wtf_size_t position) { spot->~T(); TypeOperations::MoveOverlapping(spot + 1, end(), spot); ClearUnusedSlots(end() - 1, end()); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ - 1); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size_ - 1); --size_; } @@ -2046,7 +2075,8 @@ inline void Vector<T, inlineCapacity, Allocator>::EraseAt(wtf_size_t position, TypeOperations::Destruct(begin_spot, end_spot); TypeOperations::MoveOverlapping(end_spot, end(), begin_spot); ClearUnusedSlots(end() - length, end()); - ANNOTATE_CHANGE_SIZE(begin(), capacity(), size_, size_ - length); + MARKING_AWARE_ANNOTATE_CHANGE_SIZE(Allocator, begin(), capacity(), size_, + size_ - length); size_ -= length; } diff --git a/chromium/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h b/chromium/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h index ef44f8f604e..e9f93acd773 100644 --- a/chromium/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h +++ b/chromium/third_party/blink/renderer/platform/wtf/vector_backed_linked_list.h @@ -52,7 +52,8 @@ class VectorBackedLinkedListNode { default; template <typename VisitorDispathcer, typename A = Allocator> - std::enable_if_t<A::kIsGarbageCollected> Trace(VisitorDispathcer visitor) { + std::enable_if_t<A::kIsGarbageCollected> Trace( + VisitorDispathcer visitor) const { visitor->Trace(value_); } @@ -183,7 +184,8 @@ class VectorBackedLinkedList { } template <typename VisitorDispatcher, typename A = Allocator> - std::enable_if_t<A::kIsGarbageCollected> Trace(VisitorDispatcher visitor) { + std::enable_if_t<A::kIsGarbageCollected> Trace( + VisitorDispatcher visitor) const { nodes_.Trace(visitor); } |