From e80c0b3536e1bdee68a874d529a9ba951faffe8b Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 27 Nov 2020 09:40:56 -0800 Subject: Export of internal Abseil changes -- d85f04af95a6fdafb102f7dc393d78d4431b47e5 by Abseil Team : Internal change for cord ring PiperOrigin-RevId: 344541196 -- 1ff57908e31a09ec0c98d8316da1263092cc3a1c by Abseil Team : Fix typo in comment. PiperOrigin-RevId: 344214280 GitOrigin-RevId: d85f04af95a6fdafb102f7dc393d78d4431b47e5 Change-Id: I58b3c28f62a5d10dd665b17d58a121f371e1260a --- absl/flags/internal/commandlineflag.h | 2 +- absl/strings/BUILD.bazel | 5 +- absl/strings/CMakeLists.txt | 1 + absl/strings/cord.cc | 137 ++++++++-------------------------- absl/strings/internal/cord_internal.h | 14 +++- absl/strings/internal/cord_rep_flat.h | 129 ++++++++++++++++++++++++++++++++ 6 files changed, 179 insertions(+), 109 deletions(-) create mode 100644 absl/strings/internal/cord_rep_flat.h (limited to 'absl') diff --git a/absl/flags/internal/commandlineflag.h b/absl/flags/internal/commandlineflag.h index cb46fe2e..ebfe81ba 100644 --- a/absl/flags/internal/commandlineflag.h +++ b/absl/flags/internal/commandlineflag.h @@ -24,7 +24,7 @@ ABSL_NAMESPACE_BEGIN namespace flags_internal { // An alias for flag fast type id. This value identifies the flag value type -// simialarly to typeid(T), without relying on RTTI being available. In most +// similarly to typeid(T), without relying on RTTI being available. In most // cases this id is enough to uniquely identify the flag's value type. In a few // cases we'll have to resort to using actual RTTI implementation if it is // available. diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 30a8dd28..a1579a4a 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -267,7 +267,10 @@ cc_test( cc_library( name = "cord_internal", - hdrs = ["internal/cord_internal.h"], + hdrs = [ + "internal/cord_internal.h", + "internal/cord_rep_flat.h", + ], copts = ABSL_DEFAULT_COPTS, visibility = ["//visibility:private"], deps = [ diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 2b994a71..af0b57d8 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -557,6 +557,7 @@ absl_cc_library( SRCS "cord.cc" "internal/cord_internal.h" + "internal/cord_rep_flat.h" COPTS ${ABSL_DEFAULT_COPTS} DEPS diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index ec1e9709..7c4f6c92 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc @@ -36,6 +36,7 @@ #include "absl/container/inlined_vector.h" #include "absl/strings/escaping.h" #include "absl/strings/internal/cord_internal.h" +#include "absl/strings/internal/cord_rep_flat.h" #include "absl/strings/internal/resize_uninitialized.h" #include "absl/strings/str_cat.h" #include "absl/strings/str_format.h" @@ -48,8 +49,12 @@ ABSL_NAMESPACE_BEGIN using ::absl::cord_internal::CordRep; using ::absl::cord_internal::CordRepConcat; using ::absl::cord_internal::CordRepExternal; +using ::absl::cord_internal::CordRepFlat; using ::absl::cord_internal::CordRepSubstring; +using ::absl::cord_internal::kMinFlatLength; +using ::absl::cord_internal::kMaxFlatLength; + using ::absl::cord_internal::CONCAT; using ::absl::cord_internal::EXTERNAL; using ::absl::cord_internal::FLAT; @@ -90,64 +95,9 @@ inline const CordRepExternal* CordRep::external() const { } // namespace cord_internal -static const size_t kFlatOverhead = offsetof(CordRep, data); - -// Largest and smallest flat node lengths we are willing to allocate -// Flat allocation size is stored in tag, which currently can encode sizes up -// to 4K, encoded as multiple of either 8 or 32 bytes. -// If we allow for larger sizes, we need to change this to 8/64, 16/128, etc. -// kMinFlatSize is bounded by tag needing to be at least FLAT * 8 bytes, and -// ideally a 'nice' size aligning with allocation and cacheline sizes like 32. -// kMaxFlatSize is bounded by the size resulting in a computed tag no greater -// than MAX_FLAT_TAG. MAX_FLAT_TAG provides for additional 'high' tag values. -static constexpr size_t kMinFlatSize = 32; -static constexpr size_t kMaxFlatSize = 4096; -static constexpr size_t kMaxFlatLength = kMaxFlatSize - kFlatOverhead; -static constexpr size_t kMinFlatLength = kMinFlatSize - kFlatOverhead; - -static constexpr size_t AllocatedSizeToTagUnchecked(size_t size) { - return (size <= 1024) ? size / 8 : 128 + size / 32 - 1024 / 32; -} - -static_assert(kMinFlatSize / 8 >= FLAT, ""); -static_assert(AllocatedSizeToTagUnchecked(kMaxFlatSize) <= MAX_FLAT_TAG, ""); - // Prefer copying blocks of at most this size, otherwise reference count. static const size_t kMaxBytesToCopy = 511; -// Helper functions for rounded div, and rounding to exact sizes. -static size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; } -static size_t RoundUp(size_t n, size_t m) { return DivUp(n, m) * m; } - -// Returns the size to the nearest equal or larger value that can be -// expressed exactly as a tag value. -static size_t RoundUpForTag(size_t size) { - return RoundUp(size, (size <= 1024) ? 8 : 32); -} - -// Converts the allocated size to a tag, rounding down if the size -// does not exactly match a 'tag expressible' size value. The result is -// undefined if the size exceeds the maximum size that can be encoded in -// a tag, i.e., if size is larger than TagToAllocatedSize(). -static uint8_t AllocatedSizeToTag(size_t size) { - const size_t tag = AllocatedSizeToTagUnchecked(size); - assert(tag <= std::numeric_limits::max()); - return tag; -} - -// Converts the provided tag to the corresponding allocated size -static constexpr size_t TagToAllocatedSize(uint8_t tag) { - return (tag <= 128) ? (tag * 8) : (1024 + (tag - 128) * 32); -} - -// Converts the provided tag to the corresponding available data length -static constexpr size_t TagToLength(uint8_t tag) { - return TagToAllocatedSize(tag) - kFlatOverhead; -} - -// Enforce that kMaxFlatSize maps to a well-known exact tag value. -static_assert(TagToAllocatedSize(224) == kMaxFlatSize, "Bad tag logic"); - constexpr uint64_t Fibonacci(unsigned char n, uint64_t a = 0, uint64_t b = 1) { return n == 0 ? a : Fibonacci(n - 1, b, a + b); } @@ -269,9 +219,7 @@ static void UnrefInternal(CordRep* rep) { continue; } } else if (rep->tag == EXTERNAL) { - CordRepExternal* rep_external = rep->external(); - assert(rep_external->releaser_invoker != nullptr); - rep_external->releaser_invoker(rep_external); + CordRepExternal::Delete(rep); rep = nullptr; } else if (rep->tag == SUBSTRING) { CordRepSubstring* rep_substring = rep->substring(); @@ -283,17 +231,7 @@ static void UnrefInternal(CordRep* rep) { continue; } } else { - // Flat CordReps are allocated and constructed with raw ::operator new - // and placement new, and must be destructed and deallocated - // accordingly. -#if defined(__cpp_sized_deallocation) - size_t size = TagToAllocatedSize(rep->tag); - rep->~CordRep(); - ::operator delete(rep, size); -#else - rep->~CordRep(); - ::operator delete(rep); -#endif + CordRepFlat::Delete(rep); rep = nullptr; } @@ -383,22 +321,6 @@ static CordRep* MakeBalancedTree(CordRep** reps, size_t n) { return reps[0]; } -// Create a new flat node. -static CordRep* NewFlat(size_t length_hint) { - if (length_hint <= kMinFlatLength) { - length_hint = kMinFlatLength; - } else if (length_hint > kMaxFlatLength) { - length_hint = kMaxFlatLength; - } - - // Round size up so it matches a size we can exactly express in a tag. - const size_t size = RoundUpForTag(length_hint + kFlatOverhead); - void* const raw_rep = ::operator new(size); - CordRep* rep = new (raw_rep) CordRep(); - rep->tag = AllocatedSizeToTag(size); - return VerifyTree(rep); -} - // Create a new tree out of the specified array. // The returned node has a refcount of 1. static CordRep* NewTree(const char* data, @@ -409,7 +331,7 @@ static CordRep* NewTree(const char* data, size_t n = 0; do { const size_t len = std::min(length, kMaxFlatLength); - CordRep* rep = NewFlat(len + alloc_hint); + CordRep* rep = CordRepFlat::New(len + alloc_hint); rep->length = len; memcpy(rep->data, data, len); reps[n++] = VerifyTree(rep); @@ -473,7 +395,7 @@ inline CordRep* Cord::InlineRep::force_tree(size_t extra_hint) { return data_.as_tree.rep; } - CordRep* result = NewFlat(len + extra_hint); + CordRep* result = CordRepFlat::New(len + extra_hint); result->length = len; static_assert(kMinFlatLength >= sizeof(data_.as_chars), ""); memcpy(result->data, data_.as_chars, sizeof(data_.as_chars)); @@ -535,7 +457,7 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region, } const size_t in_use = dst->length; - const size_t capacity = TagToLength(dst->tag); + const size_t capacity = static_cast(dst)->Capacity(); if (in_use == capacity) { *region = nullptr; *size = 0; @@ -579,10 +501,9 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size, } // Allocate new node. - CordRep* new_node = - NewFlat(std::max(static_cast(root->length), max_length)); - new_node->length = - std::min(static_cast(TagToLength(new_node->tag)), max_length); + CordRepFlat* new_node = + CordRepFlat::New(std::max(static_cast(root->length), max_length)); + new_node->length = std::min(new_node->Capacity(), max_length); *region = new_node->data; *size = new_node->length; replace_tree(Concat(root, new_node)); @@ -607,8 +528,8 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size) { } // Allocate new node. - CordRep* new_node = NewFlat(root->length); - new_node->length = TagToLength(new_node->tag); + CordRepFlat* new_node = CordRepFlat::New(root->length); + new_node->length = new_node->Capacity(); *region = new_node->data; *size = new_node->length; replace_tree(Concat(root, new_node)); @@ -618,7 +539,7 @@ void Cord::InlineRep::GetAppendRegion(char** region, size_t* size) { // will return true. static bool RepMemoryUsageLeaf(const CordRep* rep, size_t* total_mem_usage) { if (rep->tag >= FLAT) { - *total_mem_usage += TagToAllocatedSize(rep->tag); + *total_mem_usage += static_cast(rep)->AllocatedSize(); return true; } if (rep->tag == EXTERNAL) { @@ -716,7 +637,8 @@ Cord& Cord::operator=(absl::string_view src) { return *this; } if (tree != nullptr && tree->tag >= FLAT && - TagToLength(tree->tag) >= length && tree->refcount.IsOne()) { + static_cast(tree)->Capacity() >= length && + tree->refcount.IsOne()) { // Copy in place if the existing FLAT node is reusable. memmove(tree->data, data, length); tree->length = length; @@ -770,8 +692,9 @@ void Cord::InlineRep::AppendArray(const char* src_data, size_t src_size) { // either double the inlined size, or the added size + 10%. const size_t size1 = inline_length * 2 + src_size; const size_t size2 = inline_length + src_size / 10; - root = NewFlat(std::max(size1, size2)); - appended = std::min(src_size, TagToLength(root->tag) - inline_length); + root = CordRepFlat::New(std::max(size1, size2)); + appended = std::min( + src_size, static_cast(root)->Capacity() - inline_length); memcpy(root->data, data_.as_chars, inline_length); memcpy(root->data + inline_length, src_data, appended); root->length = inline_length + appended; @@ -1747,7 +1670,7 @@ absl::string_view Cord::FlattenSlowPath() { // Try to put the contents into a new flat rep. If they won't fit in the // biggest possible flat node, use an external rep instead. if (total_size <= kMaxFlatLength) { - new_rep = NewFlat(total_size); + new_rep = CordRepFlat::New(total_size); new_rep->length = total_size; new_buffer = new_rep->data; CopyToArraySlowPath(new_buffer); @@ -1862,7 +1785,8 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os) { *os << absl::CEscape(std::string(rep->external()->base, rep->length)); *os << "]\n"; } else { - *os << "FLAT cap=" << TagToLength(rep->tag) << " ["; + *os << "FLAT cap=" << static_cast(rep)->Capacity() + << " ["; if (include_data) *os << absl::CEscape(std::string(rep->data, rep->length)); *os << "]\n"; @@ -1910,8 +1834,9 @@ static bool VerifyNode(CordRep* root, CordRep* start_node, worklist.push_back(node->concat()->left); } } else if (node->tag >= FLAT) { - ABSL_INTERNAL_CHECK(node->length <= TagToLength(node->tag), - ReportError(root, node)); + ABSL_INTERNAL_CHECK( + node->length <= static_cast(node)->Capacity(), + ReportError(root, node)); } else if (node->tag == EXTERNAL) { ABSL_INTERNAL_CHECK(node->external()->base != nullptr, ReportError(root, node)); @@ -1987,14 +1912,14 @@ std::ostream& operator<<(std::ostream& out, const Cord& cord) { } namespace strings_internal { -size_t CordTestAccess::FlatOverhead() { return kFlatOverhead; } -size_t CordTestAccess::MaxFlatLength() { return kMaxFlatLength; } +size_t CordTestAccess::FlatOverhead() { return cord_internal::kFlatOverhead; } +size_t CordTestAccess::MaxFlatLength() { return cord_internal::kMaxFlatLength; } size_t CordTestAccess::FlatTagToLength(uint8_t tag) { - return TagToLength(tag); + return cord_internal::TagToLength(tag); } uint8_t CordTestAccess::LengthToTag(size_t s) { ABSL_INTERNAL_CHECK(s <= kMaxFlatLength, absl::StrCat("Invalid length ", s)); - return AllocatedSizeToTag(s + kFlatOverhead); + return cord_internal::AllocatedSizeToTag(s + cord_internal::kFlatOverhead); } size_t CordTestAccess::SizeofCordRepConcat() { return sizeof(CordRepConcat); } size_t CordTestAccess::SizeofCordRepExternal() { diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h index 195a7988..ec2c767b 100644 --- a/absl/strings/internal/cord_internal.h +++ b/absl/strings/internal/cord_internal.h @@ -108,8 +108,9 @@ class Refcount { // functions in the base class. struct CordRepConcat; -struct CordRepSubstring; struct CordRepExternal; +struct CordRepFlat; +struct CordRepSubstring; // Various representations that we allow enum CordRepKind { @@ -180,6 +181,10 @@ struct CordRepExternal : public CordRep { const char* base; // Pointer to function that knows how to call and destroy the releaser. ExternalReleaserInvoker releaser_invoker; + + // Deletes (releases) the external rep. + // Requires rep != nullptr and rep->tag == EXTERNAL + static void Delete(CordRep* rep); }; struct Rank1 {}; @@ -220,6 +225,13 @@ struct CordRepExternalImpl } }; +inline void CordRepExternal::Delete(CordRep* rep) { + assert(rep != nullptr && rep->tag == EXTERNAL); + auto* rep_external = static_cast(rep); + assert(rep_external->releaser_invoker != nullptr); + rep_external->releaser_invoker(rep_external); +} + template struct ConstInitExternalStorage { ABSL_CONST_INIT static CordRepExternal value; diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h new file mode 100644 index 00000000..3e2cd33c --- /dev/null +++ b/absl/strings/internal/cord_rep_flat.h @@ -0,0 +1,129 @@ +// Copyright 2020 The Abseil Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_ +#define ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_ + +#include +#include +#include +#include + +#include "absl/strings/internal/cord_internal.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace cord_internal { + +// Note: all constants below are never ODR used and internal to cord, we define +// these as static constexpr to avoid 'in struct' definition and usage clutter. + +// Largest and smallest flat node lengths we are willing to allocate +// Flat allocation size is stored in tag, which currently can encode sizes up +// to 4K, encoded as multiple of either 8 or 32 bytes. +// If we allow for larger sizes, we need to change this to 8/64, 16/128, etc. +// kMinFlatSize is bounded by tag needing to be at least FLAT * 8 bytes, and +// ideally a 'nice' size aligning with allocation and cacheline sizes like 32. +// kMaxFlatSize is bounded by the size resulting in a computed tag no greater +// than MAX_FLAT_TAG. MAX_FLAT_TAG provides for additional 'high' tag values. +static constexpr size_t kFlatOverhead = offsetof(CordRep, data); +static constexpr size_t kMinFlatSize = 32; +static constexpr size_t kMaxFlatSize = 4096; +static constexpr size_t kMaxFlatLength = kMaxFlatSize - kFlatOverhead; +static constexpr size_t kMinFlatLength = kMinFlatSize - kFlatOverhead; + +static constexpr size_t AllocatedSizeToTagUnchecked(size_t size) { + return (size <= 1024) ? size / 8 : 128 + size / 32 - 1024 / 32; +} + +static_assert(kMinFlatSize / 8 >= FLAT, ""); +static_assert(AllocatedSizeToTagUnchecked(kMaxFlatSize) <= MAX_FLAT_TAG, ""); + +// Helper functions for rounded div, and rounding to exact sizes. +static size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; } +static size_t RoundUp(size_t n, size_t m) { return DivUp(n, m) * m; } + +// Returns the size to the nearest equal or larger value that can be +// expressed exactly as a tag value. +static size_t RoundUpForTag(size_t size) { + return RoundUp(size, (size <= 1024) ? 8 : 32); +} + +// Converts the allocated size to a tag, rounding down if the size +// does not exactly match a 'tag expressible' size value. The result is +// undefined if the size exceeds the maximum size that can be encoded in +// a tag, i.e., if size is larger than TagToAllocatedSize(). +static uint8_t AllocatedSizeToTag(size_t size) { + const size_t tag = AllocatedSizeToTagUnchecked(size); + assert(tag <= MAX_FLAT_TAG); + return tag; +} + +// Converts the provided tag to the corresponding allocated size +static constexpr size_t TagToAllocatedSize(uint8_t tag) { + return (tag <= 128) ? (tag * 8) : (1024 + (tag - 128) * 32); +} + +// Converts the provided tag to the corresponding available data length +static constexpr size_t TagToLength(uint8_t tag) { + return TagToAllocatedSize(tag) - kFlatOverhead; +} + +// Enforce that kMaxFlatSize maps to a well-known exact tag value. +static_assert(TagToAllocatedSize(224) == kMaxFlatSize, "Bad tag logic"); + +struct CordRepFlat : public CordRep { + // Creates a new flat node. + static CordRepFlat* New(size_t len) { + if (len <= kMinFlatLength) { + len = kMinFlatLength; + } else if (len > kMaxFlatLength) { + len = kMaxFlatLength; + } + + // Round size up so it matches a size we can exactly express in a tag. + const size_t size = RoundUpForTag(len + kFlatOverhead); + void* const raw_rep = ::operator new(size); + CordRepFlat* rep = new (raw_rep) CordRepFlat(); + rep->tag = AllocatedSizeToTag(size); + return rep; + } + + // Deletes a CordRepFlat instance created previously through a call to New(). + // Flat CordReps are allocated and constructed with raw ::operator new and + // placement new, and must be destructed and deallocated accordingly. + static void Delete(CordRep*rep) { + assert(rep->tag >= FLAT); +#if defined(__cpp_sized_deallocation) + size_t size = TagToAllocatedSize(rep->tag); + rep->~CordRep(); + ::operator delete(rep, size); +#else + rep->~CordRep(); + ::operator delete(rep); +#endif + } + + // Returns the maximum capacity (payload size) of this instance. + size_t Capacity() const { return TagToLength(tag); } + + // Returns the allocated size (payload + overhead) of this instance. + size_t AllocatedSize() const { return TagToAllocatedSize(tag); } +}; + +} // namespace cord_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_ -- cgit v1.2.3