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