1 // Protocol Buffers - Google's data interchange format
2 // Copyright 2023 Google Inc. All rights reserved.
3 //
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file or at
6 // https://developers.google.com/open-source/licenses/bsd
7 //
8 // This file defines the internal StringBlock class
9
10 #ifndef GOOGLE_PROTOBUF_STRING_BLOCK_H__
11 #define GOOGLE_PROTOBUF_STRING_BLOCK_H__
12
13 #include <algorithm>
14 #include <cstddef>
15 #include <cstdint>
16 #include <string>
17
18 #include "absl/base/attributes.h"
19 #include "absl/log/absl_check.h"
20 #include "google/protobuf/arena_align.h"
21 #include "google/protobuf/port.h"
22
23 // Must be included last.
24 #include "google/protobuf/port_def.inc"
25
26 namespace google {
27 namespace protobuf {
28 namespace internal {
29
30 // StringBlock provides heap allocated, dynamically sized blocks (mini arenas)
31 // for allocating std::string instances. StringBlocks are allocated through
32 // the `New` function, and must be freed using the `Delete` function.
33 // StringBlocks are automatically sized from 256B to 8KB depending on the
34 // `next` instance provided in the `New` function to keep the average maximum
35 // unused space limited to 25%, or up to 4KB.
36 class alignas(std::string) StringBlock {
37 public:
38 StringBlock() = delete;
39 StringBlock(const StringBlock&) = delete;
40 StringBlock& operator=(const StringBlock&) = delete;
41
42 // Returns the size of the next string block based on the size information
43 // stored in `block`. `block` may be null in which case the size of the
44 // initial string block is returned.
45 static size_t NextSize(StringBlock* block);
46
47 // Allocates a new StringBlock pointing to `next`, which can be null.
48 // The size of the returned block depends on the allocated size of `next`.
49 static StringBlock* New(StringBlock* next);
50
51 // Allocates a new string block `in place`. `n` must be the value returned
52 // from a previous call to `StringBlock::NextSize(next)`
53 static StringBlock* Emplace(void* p, size_t n, StringBlock* next);
54
55 // Deletes `block` if `block` is heap allocated. `block` must not be null.
56 // Returns the allocated size of `block`, or 0 if the block was emplaced.
57 static size_t Delete(StringBlock* block);
58
59 StringBlock* next() const;
60
61 // Returns the string instance at offset `offset`.
62 // `offset` must be a multiple of sizeof(std::string), and be less than or
63 // equal to `effective_size()`. `AtOffset(effective_size())` returns the
64 // end of the allocated string instances and must not be de-referenced.
65 ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* AtOffset(size_t offset);
66
67 // Returns a pointer to the first string instance in this block.
68 ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* begin();
69
70 // Returns a pointer directly beyond the last string instance in this block.
71 ABSL_ATTRIBUTE_RETURNS_NONNULL std::string* end();
72
73 // Returns the total allocation size of this instance.
allocated_size()74 size_t allocated_size() const { return allocated_size_; }
75
76 // Returns true if this block is heap allocated, false if emplaced.
heap_allocated()77 bool heap_allocated() const { return heap_allocated_; }
78
79 // Returns the effective size available for allocation string instances.
80 // This value is guaranteed to be a multiple of sizeof(std::string), and
81 // guaranteed to never be zero.
82 size_t effective_size() const;
83
84 private:
85 using size_type = uint16_t;
86
87 static_assert(alignof(std::string) <= sizeof(void*), "");
88 static_assert(alignof(std::string) <= ArenaAlignDefault::align, "");
89
90 ~StringBlock() = default;
91
StringBlock(StringBlock * next,bool heap_allocated,size_type size,size_type next_size)92 explicit StringBlock(StringBlock* next, bool heap_allocated, size_type size,
93 size_type next_size) noexcept
94 : next_(next),
95 allocated_size_(size),
96 next_size_(next_size),
97 heap_allocated_(heap_allocated) {}
98
min_size()99 static constexpr size_type min_size() { return size_type{256}; }
max_size()100 static constexpr size_type max_size() { return size_type{8192}; }
101
102 // Returns `size` rounded down such that we can fit a perfect number
103 // of std::string instances inside a StringBlock of that size.
104 static constexpr size_type RoundedSize(size_type size);
105
106 // Returns the size of the next block.
next_size()107 size_t next_size() const { return next_size_; }
108
109 StringBlock* const next_;
110 const size_type allocated_size_;
111 const size_type next_size_;
112 const bool heap_allocated_;
113 };
114
RoundedSize(size_type size)115 constexpr StringBlock::size_type StringBlock::RoundedSize(size_type size) {
116 return size - (size - sizeof(StringBlock)) % sizeof(std::string);
117 }
118
NextSize(StringBlock * block)119 inline size_t StringBlock::NextSize(StringBlock* block) {
120 return block ? block->next_size() : min_size();
121 }
122
Emplace(void * p,size_t n,StringBlock * next)123 inline StringBlock* StringBlock::Emplace(void* p, size_t n, StringBlock* next) {
124 const auto count = static_cast<size_type>(n);
125 ABSL_DCHECK_EQ(count, NextSize(next));
126 size_type doubled = count * 2;
127 size_type next_size = next ? std::min(doubled, max_size()) : min_size();
128 return new (p) StringBlock(next, false, RoundedSize(count), next_size);
129 }
130
New(StringBlock * next)131 inline StringBlock* StringBlock::New(StringBlock* next) {
132 // Compute required size, rounding down to a multiple of sizeof(std:string)
133 // so that we can optimize the allocation path. I.e., we incur a (constant
134 // size) MOD() operation cost here to avoid any MUL() later on.
135 size_type size = min_size();
136 size_type next_size = min_size();
137 if (next) {
138 size = next->next_size_;
139 next_size = std::min<size_type>(size * 2, max_size());
140 }
141 size = RoundedSize(size);
142 void* p = ::operator new(size);
143 return new (p) StringBlock(next, true, size, next_size);
144 }
145
Delete(StringBlock * block)146 inline size_t StringBlock::Delete(StringBlock* block) {
147 ABSL_DCHECK(block != nullptr);
148 if (!block->heap_allocated_) return size_t{0};
149 size_t size = block->allocated_size();
150 internal::SizedDelete(block, size);
151 return size;
152 }
153
next()154 inline StringBlock* StringBlock::next() const { return next_; }
155
effective_size()156 inline size_t StringBlock::effective_size() const {
157 return allocated_size_ - sizeof(StringBlock);
158 }
159
AtOffset(size_t offset)160 ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::AtOffset(
161 size_t offset) {
162 ABSL_DCHECK_LE(offset, effective_size());
163 return reinterpret_cast<std::string*>(reinterpret_cast<char*>(this + 1) +
164 offset);
165 }
166
begin()167 ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::begin() {
168 return AtOffset(0);
169 }
170
end()171 ABSL_ATTRIBUTE_RETURNS_NONNULL inline std::string* StringBlock::end() {
172 return AtOffset(effective_size());
173 }
174
175 } // namespace internal
176 } // namespace protobuf
177 } // namespace google
178
179 #include "google/protobuf/port_undef.inc"
180
181 #endif // GOOGLE_PROTOBUF_STRING_BLOCK_H__
182