strings/internal/cord_rep_flat.h

0001 // Copyright 2020 The Abseil Authors
0002 //
0003 // Licensed under the Apache License, Version 2.0 (the "License");
0004 // you may not use this file except in compliance with the License.
0005 // You may obtain a copy of the License at
0006 //
0007 //     https://www.apache.org/licenses/LICENSE-2.0
0008 //
0009 // Unless required by applicable law or agreed to in writing, software
0010 // distributed under the License is distributed on an "AS IS" BASIS,
0011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0012 // See the License for the specific language governing permissions and
0013 // limitations under the License.
0014
0015 #ifndef ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_
0016 #define ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_
0017
0018 #include <cassert>
0019 #include <cstddef>
0020 #include <cstdint>
0021 #include <memory>
0022
0023 #include "absl/base/config.h"
0024 #include "absl/base/macros.h"
0025 #include "absl/strings/internal/cord_internal.h"
0026
0027 namespace absl {
0028 ABSL_NAMESPACE_BEGIN
0029 namespace cord_internal {
0030
0031 // Note: all constants below are never ODR used and internal to cord, we define
0032 // these as static constexpr to avoid 'in struct' definition and usage clutter.
0033
0034 // Largest and smallest flat node lengths we are willing to allocate
0035 // Flat allocation size is stored in tag, which currently can encode sizes up
0036 // to 4K, encoded as multiple of either 8 or 32 bytes.
0037 // If we allow for larger sizes, we need to change this to 8/64, 16/128, etc.
0038 // kMinFlatSize is bounded by tag needing to be at least FLAT * 8 bytes, and
0039 // ideally a 'nice' size aligning with allocation and cacheline sizes like 32.
0040 // kMaxFlatSize is bounded by the size resulting in a computed tag no greater
0041 // than MAX_FLAT_TAG. MAX_FLAT_TAG provides for additional 'high' tag values.
0042 static constexpr size_t kFlatOverhead = offsetof(CordRep, storage);
0043 static constexpr size_t kMinFlatSize = 32;
0044 static constexpr size_t kMaxFlatSize = 4096;
0045 static constexpr size_t kMaxFlatLength = kMaxFlatSize - kFlatOverhead;
0046 static constexpr size_t kMinFlatLength = kMinFlatSize - kFlatOverhead;
0047 static constexpr size_t kMaxLargeFlatSize = 256 * 1024;
0048 static constexpr size_t kMaxLargeFlatLength = kMaxLargeFlatSize - kFlatOverhead;
0049
0050 // kTagBase should make the Size <--> Tag computation resilient
0051 // against changes to the value of FLAT when we add a new tag..
0052 static constexpr uint8_t kTagBase = FLAT - 4;
0053
0054 // Converts the provided rounded size to the corresponding tag
0055 constexpr uint8_t AllocatedSizeToTagUnchecked(size_t size) {
0056   return static_cast<uint8_t>(size <= 512 ? kTagBase + size / 8
0057                               : size <= 8192
0058                                   ? kTagBase + 512 / 8 + size / 64 - 512 / 64
0059                                   : kTagBase + 512 / 8 + ((8192 - 512) / 64) +
0060                                         size / 4096 - 8192 / 4096);
0061 }
0062
0063 // Converts the provided tag to the corresponding allocated size
0064 constexpr size_t TagToAllocatedSize(uint8_t tag) {
0065   return (tag <= kTagBase + 512 / 8) ? tag * 8 - kTagBase * 8
0066          : (tag <= kTagBase + (512 / 8) + ((8192 - 512) / 64))
0067              ? 512 + tag * 64 - kTagBase * 64 - 512 / 8 * 64
0068              : 8192 + tag * 4096 - kTagBase * 4096 -
0069                    ((512 / 8) + ((8192 - 512) / 64)) * 4096;
0070 }
0071
0072 static_assert(AllocatedSizeToTagUnchecked(kMinFlatSize) == FLAT, "");
0073 static_assert(AllocatedSizeToTagUnchecked(kMaxLargeFlatSize) == MAX_FLAT_TAG,
0074               "");
0075
0076 // RoundUp logically performs `((n + m - 1) / m) * m` to round up to the nearest
0077 // multiple of `m`, optimized for the invariant that `m` is a power of 2.
0078 constexpr size_t RoundUp(size_t n, size_t m) {
0079   return (n + m - 1) & (0 - m);
0080 }
0081
0082 // Returns the size to the nearest equal or larger value that can be
0083 // expressed exactly as a tag value.
0084 inline size_t RoundUpForTag(size_t size) {
0085   return RoundUp(size, (size <= 512) ? 8 : (size <= 8192 ? 64 : 4096));
0086 }
0087
0088 // Converts the allocated size to a tag, rounding down if the size
0089 // does not exactly match a 'tag expressible' size value. The result is
0090 // undefined if the size exceeds the maximum size that can be encoded in
0091 // a tag, i.e., if size is larger than TagToAllocatedSize(<max tag>).
0092 inline uint8_t AllocatedSizeToTag(size_t size) {
0093   const uint8_t tag = AllocatedSizeToTagUnchecked(size);
0094   assert(tag <= MAX_FLAT_TAG);
0095   return tag;
0096 }
0097
0098 // Converts the provided tag to the corresponding available data length
0099 constexpr size_t TagToLength(uint8_t tag) {
0100   return TagToAllocatedSize(tag) - kFlatOverhead;
0101 }
0102
0103 // Enforce that kMaxFlatSize maps to a well-known exact tag value.
0104 static_assert(TagToAllocatedSize(MAX_FLAT_TAG) == kMaxLargeFlatSize,
0105               "Bad tag logic");
0106
0107 struct CordRepFlat : public CordRep {
0108   // Tag for explicit 'large flat' allocation
0109   struct Large {};
0110
0111   // Creates a new flat node.
0112   template <size_t max_flat_size, typename... Args>
0113   static CordRepFlat* NewImpl(size_t len, Args... args ABSL_ATTRIBUTE_UNUSED) {
0114     if (len <= kMinFlatLength) {
0115       len = kMinFlatLength;
0116     } else if (len > max_flat_size - kFlatOverhead) {
0117       len = max_flat_size - kFlatOverhead;
0118     }
0119
0120     // Round size up so it matches a size we can exactly express in a tag.
0121     const size_t size = RoundUpForTag(len + kFlatOverhead);
0122     void* const raw_rep = ::operator new(size);
0123     // GCC 13 has a false-positive -Wstringop-overflow warning here.
0124     #if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(13, 0)
0125     #pragma GCC diagnostic push
0126     #pragma GCC diagnostic ignored "-Wstringop-overflow"
0127     #endif
0128     CordRepFlat* rep = new (raw_rep) CordRepFlat();
0129     rep->tag = AllocatedSizeToTag(size);
0130     #if ABSL_INTERNAL_HAVE_MIN_GNUC_VERSION(13, 0)
0131     #pragma GCC diagnostic pop
0132     #endif
0133     return rep;
0134   }
0135
0136   static CordRepFlat* New(size_t len) { return NewImpl<kMaxFlatSize>(len); }
0137
0138   static CordRepFlat* New(Large, size_t len) {
0139     return NewImpl<kMaxLargeFlatSize>(len);
0140   }
0141
0142   // Deletes a CordRepFlat instance created previously through a call to New().
0143   // Flat CordReps are allocated and constructed with raw ::operator new and
0144   // placement new, and must be destructed and deallocated accordingly.
0145   static void Delete(CordRep*rep) {
0146     assert(rep->tag >= FLAT && rep->tag <= MAX_FLAT_TAG);
0147
0148 #if defined(__cpp_sized_deallocation)
0149     size_t size = TagToAllocatedSize(rep->tag);
0150     rep->~CordRep();
0151     ::operator delete(rep, size);
0152 #else
0153     rep->~CordRep();
0154     ::operator delete(rep);
0155 #endif
0156   }
0157
0158   // Create a CordRepFlat containing `data`, with an optional additional
0159   // extra capacity of up to `extra` bytes. Requires that `data.size()`
0160   // is less than kMaxFlatLength.
0161   static CordRepFlat* Create(absl::string_view data, size_t extra = 0) {
0162     assert(data.size() <= kMaxFlatLength);
0163     CordRepFlat* flat = New(data.size() + (std::min)(extra, kMaxFlatLength));
0164     memcpy(flat->Data(), data.data(), data.size());
0165     flat->length = data.size();
0166     return flat;
0167   }
0168
0169   // Returns a pointer to the data inside this flat rep.
0170   char* Data() { return reinterpret_cast<char*>(storage); }
0171   const char* Data() const { return reinterpret_cast<const char*>(storage); }
0172
0173   // Returns the maximum capacity (payload size) of this instance.
0174   size_t Capacity() const { return TagToLength(tag); }
0175
0176   // Returns the allocated size (payload + overhead) of this instance.
0177   size_t AllocatedSize() const { return TagToAllocatedSize(tag); }
0178 };
0179
0180 // Now that CordRepFlat is defined, we can define CordRep's helper casts:
0181 inline CordRepFlat* CordRep::flat() {
0182   assert(tag >= FLAT && tag <= MAX_FLAT_TAG);
0183   return reinterpret_cast<CordRepFlat*>(this);
0184 }
0185
0186 inline const CordRepFlat* CordRep::flat() const {
0187   assert(tag >= FLAT && tag <= MAX_FLAT_TAG);
0188   return reinterpret_cast<const CordRepFlat*>(this);
0189 }
0190
0191 }  // namespace cord_internal
0192 ABSL_NAMESPACE_END
0193 }  // namespace absl
0194
0195 #endif  // ABSL_STRINGS_INTERNAL_CORD_REP_FLAT_H_