1 // Copyright 2021 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/strings/cord_buffer.h"
16
17
18 #include <algorithm>
19 #include <cstring>
20 #include <limits>
21 #include <string>
22 #include <utility>
23
24 #include "gmock/gmock.h"
25 #include "gtest/gtest.h"
26 #include "absl/base/config.h"
27 #include "absl/strings/internal/cord_internal.h"
28 #include "absl/strings/internal/cord_rep_flat.h"
29 #include "absl/strings/internal/cord_rep_test_util.h"
30 #include "absl/strings/string_view.h"
31 #include "absl/types/span.h"
32
33 using testing::Eq;
34 using testing::Ge;
35 using testing::Le;
36 using testing::Ne;
37
38 namespace absl {
39 ABSL_NAMESPACE_BEGIN
40
41 class CordBufferTestPeer {
42 public:
ConsumeValue(CordBuffer & buffer,absl::string_view & short_value)43 static cord_internal::CordRep* ConsumeValue(CordBuffer& buffer,
44 absl::string_view& short_value) {
45 return buffer.ConsumeValue(short_value);
46 }
47 };
48
49 namespace {
50
51 using ::absl::cordrep_testing::CordToString;
52
53 constexpr size_t kInlinedSize = sizeof(CordBuffer) - 1;
54 constexpr size_t kDefaultLimit = CordBuffer::kDefaultLimit;
55 constexpr size_t kCustomLimit = CordBuffer::kCustomLimit;
56 constexpr size_t kMaxFlatSize = cord_internal::kMaxFlatSize;
57 constexpr size_t kMaxFlatLength = cord_internal::kMaxFlatLength;
58 constexpr size_t kFlatOverhead = cord_internal::kFlatOverhead;
59
60 constexpr size_t k8KiB = 8 << 10;
61 constexpr size_t k16KiB = 16 << 10;
62 constexpr size_t k64KiB = 64 << 10;
63 constexpr size_t k1MB = 1 << 20;
64
65 class CordBufferTest : public testing::TestWithParam<size_t> {};
66
67 INSTANTIATE_TEST_SUITE_P(MediumSize, CordBufferTest,
68 testing::Values(1, kInlinedSize - 1, kInlinedSize,
69 kInlinedSize + 1, kDefaultLimit - 1,
70 kDefaultLimit));
71
TEST_P(CordBufferTest,MaximumPayload)72 TEST_P(CordBufferTest, MaximumPayload) {
73 EXPECT_THAT(CordBuffer::MaximumPayload(), Eq(kMaxFlatLength));
74 EXPECT_THAT(CordBuffer::MaximumPayload(512), Eq(512 - kFlatOverhead));
75 EXPECT_THAT(CordBuffer::MaximumPayload(k64KiB), Eq(k64KiB - kFlatOverhead));
76 EXPECT_THAT(CordBuffer::MaximumPayload(k1MB), Eq(k64KiB - kFlatOverhead));
77 }
78
TEST(CordBufferTest,ConstructDefault)79 TEST(CordBufferTest, ConstructDefault) {
80 CordBuffer buffer;
81 EXPECT_THAT(buffer.capacity(), Eq(sizeof(CordBuffer) - 1));
82 EXPECT_THAT(buffer.length(), Eq(0));
83 EXPECT_THAT(buffer.data(), Ne(nullptr));
84 EXPECT_THAT(buffer.available().data(), Eq(buffer.data()));
85 EXPECT_THAT(buffer.available().size(), Eq(buffer.capacity()));
86 memset(buffer.data(), 0xCD, buffer.capacity());
87 }
88
TEST(CordBufferTest,CreateSsoWithDefaultLimit)89 TEST(CordBufferTest, CreateSsoWithDefaultLimit) {
90 CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(3);
91 EXPECT_THAT(buffer.capacity(), Ge(3));
92 EXPECT_THAT(buffer.capacity(), Le(sizeof(CordBuffer)));
93 EXPECT_THAT(buffer.length(), Eq(0));
94 memset(buffer.data(), 0xCD, buffer.capacity());
95
96 memcpy(buffer.data(), "Abc", 3);
97 buffer.SetLength(3);
98 EXPECT_THAT(buffer.length(), Eq(3));
99 absl::string_view short_value;
100 EXPECT_THAT(CordBufferTestPeer::ConsumeValue(buffer, short_value),
101 Eq(nullptr));
102 EXPECT_THAT(absl::string_view(buffer.data(), 3), Eq("Abc"));
103 EXPECT_THAT(short_value, Eq("Abc"));
104 }
105
TEST_P(CordBufferTest,Available)106 TEST_P(CordBufferTest, Available) {
107 const size_t requested = GetParam();
108 CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(requested);
109 EXPECT_THAT(buffer.available().data(), Eq(buffer.data()));
110 EXPECT_THAT(buffer.available().size(), Eq(buffer.capacity()));
111
112 buffer.SetLength(2);
113 EXPECT_THAT(buffer.available().data(), Eq(buffer.data() + 2));
114 EXPECT_THAT(buffer.available().size(), Eq(buffer.capacity() - 2));
115 }
116
TEST_P(CordBufferTest,IncreaseLengthBy)117 TEST_P(CordBufferTest, IncreaseLengthBy) {
118 const size_t requested = GetParam();
119 CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(requested);
120 buffer.IncreaseLengthBy(2);
121 EXPECT_THAT(buffer.length(), Eq(2));
122 buffer.IncreaseLengthBy(5);
123 EXPECT_THAT(buffer.length(), Eq(7));
124 }
125
TEST_P(CordBufferTest,AvailableUpTo)126 TEST_P(CordBufferTest, AvailableUpTo) {
127 const size_t requested = GetParam();
128 CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(requested);
129 size_t expected_up_to = std::min<size_t>(3, buffer.capacity());
130 EXPECT_THAT(buffer.available_up_to(3).data(), Eq(buffer.data()));
131 EXPECT_THAT(buffer.available_up_to(3).size(), Eq(expected_up_to));
132
133 buffer.SetLength(2);
134 expected_up_to = std::min<size_t>(3, buffer.capacity() - 2);
135 EXPECT_THAT(buffer.available_up_to(3).data(), Eq(buffer.data() + 2));
136 EXPECT_THAT(buffer.available_up_to(3).size(), Eq(expected_up_to));
137 }
138
139 // Returns the maximum capacity for a given block_size and requested size.
MaxCapacityFor(size_t block_size,size_t requested)140 size_t MaxCapacityFor(size_t block_size, size_t requested) {
141 requested = (std::min)(requested, cord_internal::kMaxLargeFlatSize);
142 // Maximum returned size is always capped at block_size - kFlatOverhead.
143 return block_size - kFlatOverhead;
144 }
145
TEST_P(CordBufferTest,CreateWithDefaultLimit)146 TEST_P(CordBufferTest, CreateWithDefaultLimit) {
147 const size_t requested = GetParam();
148 CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(requested);
149 EXPECT_THAT(buffer.capacity(), Ge(requested));
150 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(kMaxFlatSize, requested)));
151 EXPECT_THAT(buffer.length(), Eq(0));
152
153 memset(buffer.data(), 0xCD, buffer.capacity());
154
155 std::string data(requested - 1, 'x');
156 memcpy(buffer.data(), data.c_str(), requested);
157 buffer.SetLength(requested);
158
159 EXPECT_THAT(buffer.length(), Eq(requested));
160 EXPECT_THAT(absl::string_view(buffer.data()), Eq(data));
161 }
162
TEST(CordBufferTest,CreateWithDefaultLimitAskingFor2GB)163 TEST(CordBufferTest, CreateWithDefaultLimitAskingFor2GB) {
164 constexpr size_t k2GiB = 1U << 31;
165 CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(k2GiB);
166 // Expect to never be awarded more than a reasonable memory size, even in
167 // cases where a (debug) memory allocator may grant us somewhat more memory
168 // than `kDefaultLimit` which should be no more than `2 * kDefaultLimit`
169 EXPECT_THAT(buffer.capacity(), Le(2 * CordBuffer::kDefaultLimit));
170 EXPECT_THAT(buffer.length(), Eq(0));
171 EXPECT_THAT(buffer.data(), Ne(nullptr));
172 memset(buffer.data(), 0xCD, buffer.capacity());
173 }
174
TEST_P(CordBufferTest,MoveConstruct)175 TEST_P(CordBufferTest, MoveConstruct) {
176 const size_t requested = GetParam();
177 CordBuffer from = CordBuffer::CreateWithDefaultLimit(requested);
178 const size_t capacity = from.capacity();
179 memcpy(from.data(), "Abc", 4);
180 from.SetLength(4);
181
182 CordBuffer to(std::move(from));
183 EXPECT_THAT(to.capacity(), Eq(capacity));
184 EXPECT_THAT(to.length(), Eq(4));
185 EXPECT_THAT(absl::string_view(to.data()), Eq("Abc"));
186
187 EXPECT_THAT(from.length(), Eq(0)); // NOLINT
188 }
189
TEST_P(CordBufferTest,MoveAssign)190 TEST_P(CordBufferTest, MoveAssign) {
191 const size_t requested = GetParam();
192 CordBuffer from = CordBuffer::CreateWithDefaultLimit(requested);
193 const size_t capacity = from.capacity();
194 memcpy(from.data(), "Abc", 4);
195 from.SetLength(4);
196
197 CordBuffer to;
198 to = std::move(from);
199 EXPECT_THAT(to.capacity(), Eq(capacity));
200 EXPECT_THAT(to.length(), Eq(4));
201 EXPECT_THAT(absl::string_view(to.data()), Eq("Abc"));
202
203 EXPECT_THAT(from.length(), Eq(0)); // NOLINT
204 }
205
TEST_P(CordBufferTest,ConsumeValue)206 TEST_P(CordBufferTest, ConsumeValue) {
207 const size_t requested = GetParam();
208 CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(requested);
209 memcpy(buffer.data(), "Abc", 4);
210 buffer.SetLength(3);
211
212 absl::string_view short_value;
213 if (cord_internal::CordRep* rep =
214 CordBufferTestPeer::ConsumeValue(buffer, short_value)) {
215 EXPECT_THAT(CordToString(rep), Eq("Abc"));
216 cord_internal::CordRep::Unref(rep);
217 } else {
218 EXPECT_THAT(short_value, Eq("Abc"));
219 }
220 EXPECT_THAT(buffer.length(), Eq(0));
221 }
222
TEST_P(CordBufferTest,CreateWithCustomLimitWithinDefaultLimit)223 TEST_P(CordBufferTest, CreateWithCustomLimitWithinDefaultLimit) {
224 const size_t requested = GetParam();
225 CordBuffer buffer =
226 CordBuffer::CreateWithCustomLimit(kMaxFlatSize, requested);
227 EXPECT_THAT(buffer.capacity(), Ge(requested));
228 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(kMaxFlatSize, requested)));
229 EXPECT_THAT(buffer.length(), Eq(0));
230
231 memset(buffer.data(), 0xCD, buffer.capacity());
232
233 std::string data(requested - 1, 'x');
234 memcpy(buffer.data(), data.c_str(), requested);
235 buffer.SetLength(requested);
236
237 EXPECT_THAT(buffer.length(), Eq(requested));
238 EXPECT_THAT(absl::string_view(buffer.data()), Eq(data));
239 }
240
TEST(CordLargeBufferTest,CreateAtOrBelowDefaultLimit)241 TEST(CordLargeBufferTest, CreateAtOrBelowDefaultLimit) {
242 CordBuffer buffer = CordBuffer::CreateWithCustomLimit(k64KiB, kDefaultLimit);
243 EXPECT_THAT(buffer.capacity(), Ge(kDefaultLimit));
244 EXPECT_THAT(buffer.capacity(),
245 Le(MaxCapacityFor(kMaxFlatSize, kDefaultLimit)));
246
247 buffer = CordBuffer::CreateWithCustomLimit(k64KiB, 3178);
248 EXPECT_THAT(buffer.capacity(), Ge(3178));
249 }
250
TEST(CordLargeBufferTest,CreateWithCustomLimit)251 TEST(CordLargeBufferTest, CreateWithCustomLimit) {
252 ASSERT_THAT((kMaxFlatSize & (kMaxFlatSize - 1)) == 0, "Must be power of 2");
253
254 for (size_t size = kMaxFlatSize; size <= kCustomLimit; size *= 2) {
255 CordBuffer buffer = CordBuffer::CreateWithCustomLimit(size, size);
256 size_t expected = size - kFlatOverhead;
257 ASSERT_THAT(buffer.capacity(), Ge(expected));
258 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(size, expected)));
259 }
260 }
261
TEST(CordLargeBufferTest,CreateWithTooLargeLimit)262 TEST(CordLargeBufferTest, CreateWithTooLargeLimit) {
263 CordBuffer buffer = CordBuffer::CreateWithCustomLimit(k64KiB, k1MB);
264 ASSERT_THAT(buffer.capacity(), Ge(k64KiB - kFlatOverhead));
265 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(k64KiB, k1MB)));
266 }
267
TEST(CordLargeBufferTest,CreateWithHugeValueForOverFlowHardening)268 TEST(CordLargeBufferTest, CreateWithHugeValueForOverFlowHardening) {
269 for (size_t dist_from_max = 0; dist_from_max <= 32; ++dist_from_max) {
270 size_t capacity = std::numeric_limits<size_t>::max() - dist_from_max;
271
272 CordBuffer buffer = CordBuffer::CreateWithDefaultLimit(capacity);
273 ASSERT_THAT(buffer.capacity(), Ge(kDefaultLimit));
274 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(kMaxFlatSize, capacity)));
275
276 for (size_t limit = kMaxFlatSize; limit <= kCustomLimit; limit *= 2) {
277 CordBuffer buffer = CordBuffer::CreateWithCustomLimit(limit, capacity);
278 ASSERT_THAT(buffer.capacity(), Ge(limit - kFlatOverhead));
279 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(limit, capacity)));
280 }
281 }
282 }
283
TEST(CordLargeBufferTest,CreateWithSmallLimit)284 TEST(CordLargeBufferTest, CreateWithSmallLimit) {
285 CordBuffer buffer = CordBuffer::CreateWithCustomLimit(512, 1024);
286 ASSERT_THAT(buffer.capacity(), Ge(512 - kFlatOverhead));
287 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(512, 1024)));
288
289 // Ask for precise block size, should return size - kOverhead
290 buffer = CordBuffer::CreateWithCustomLimit(512, 512);
291 ASSERT_THAT(buffer.capacity(), Ge(512 - kFlatOverhead));
292 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(512, 512)));
293
294 // Corner case: 511 < block_size, but 511 + kOverhead is above
295 buffer = CordBuffer::CreateWithCustomLimit(512, 511);
296 ASSERT_THAT(buffer.capacity(), Ge(512 - kFlatOverhead));
297 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(512, 511)));
298
299 // Corner case: 498 + kOverhead < block_size
300 buffer = CordBuffer::CreateWithCustomLimit(512, 498);
301 ASSERT_THAT(buffer.capacity(), Ge(512 - kFlatOverhead));
302 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(512, 498)));
303 }
304
TEST(CordLargeBufferTest,CreateWasteFull)305 TEST(CordLargeBufferTest, CreateWasteFull) {
306 // 15 KiB gets rounded down to next pow2 value.
307 const size_t requested = (15 << 10);
308 CordBuffer buffer = CordBuffer::CreateWithCustomLimit(k16KiB, requested);
309 ASSERT_THAT(buffer.capacity(), Ge(k8KiB - kFlatOverhead));
310 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(k8KiB, requested)));
311 }
312
TEST(CordLargeBufferTest,CreateSmallSlop)313 TEST(CordLargeBufferTest, CreateSmallSlop) {
314 const size_t requested = k16KiB - 2 * kFlatOverhead;
315 CordBuffer buffer = CordBuffer::CreateWithCustomLimit(k16KiB, requested);
316 ASSERT_THAT(buffer.capacity(), Ge(k16KiB - kFlatOverhead));
317 EXPECT_THAT(buffer.capacity(), Le(MaxCapacityFor(k16KiB, requested)));
318 }
319
320 } // namespace
321 ABSL_NAMESPACE_END
322 } // namespace absl
323