1 /*
2 * Copyright (C) 2018 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "utils/base/arena.h"
18
19 #include "utils/base/logging.h"
20 #include "utils/base/macros.h"
21 #include "gtest/gtest.h"
22
23 namespace libtextclassifier3 {
24
25 //------------------------------------------------------------------------
26 // Write random data to allocated memory
TestMemory(void * mem,int size)27 static void TestMemory(void* mem, int size) {
28 // Do some memory allocation to check that the arena doesn't mess up
29 // the internal memory allocator
30 char* tmp[100];
31 for (int i = 0; i < TC3_ARRAYSIZE(tmp); i++) {
32 tmp[i] = new char[i * i + 1];
33 }
34
35 memset(mem, 0xcc, size);
36
37 // Free up the allocated memory;
38 for (char* s : tmp) {
39 delete[] s;
40 }
41 }
42
43 //------------------------------------------------------------------------
44 // Check memory ptr
CheckMemory(void * mem,int size)45 static void CheckMemory(void* mem, int size) {
46 TC3_CHECK(mem != nullptr);
47 TestMemory(mem, size);
48 }
49
50 //------------------------------------------------------------------------
51 // Check memory ptr and alignment
CheckAlignment(void * mem,int size,int alignment)52 static void CheckAlignment(void* mem, int size, int alignment) {
53 TC3_CHECK(mem != nullptr);
54 ASSERT_EQ(0, (reinterpret_cast<uintptr_t>(mem) & (alignment - 1)))
55 << "mem=" << mem << " alignment=" << alignment;
56 TestMemory(mem, size);
57 }
58
59 //------------------------------------------------------------------------
60 template <class A>
TestArena(const char * name,A * a,int blksize)61 void TestArena(const char* name, A* a, int blksize) {
62 TC3_VLOG(INFO) << "Testing arena '" << name << "': blksize = " << blksize
63 << ": actual blksize = " << a->block_size();
64
65 int s;
66 blksize = a->block_size();
67
68 // Allocate zero bytes
69 TC3_CHECK(a->is_empty());
70 a->Alloc(0);
71 TC3_CHECK(a->is_empty());
72
73 // Allocate same as blksize
74 CheckMemory(a->Alloc(blksize), blksize);
75 TC3_CHECK(!a->is_empty());
76
77 // Allocate some chunks adding up to blksize
78 s = blksize / 4;
79 CheckMemory(a->Alloc(s), s);
80 CheckMemory(a->Alloc(s), s);
81 CheckMemory(a->Alloc(s), s);
82
83 int s2 = blksize - (s * 3);
84 CheckMemory(a->Alloc(s2), s2);
85
86 // Allocate large chunk
87 CheckMemory(a->Alloc(blksize * 2), blksize * 2);
88 CheckMemory(a->Alloc(blksize * 2 + 1), blksize * 2 + 1);
89 CheckMemory(a->Alloc(blksize * 2 + 2), blksize * 2 + 2);
90 CheckMemory(a->Alloc(blksize * 2 + 3), blksize * 2 + 3);
91
92 // Allocate aligned
93 s = blksize / 2;
94 CheckAlignment(a->AllocAligned(s, 1), s, 1);
95 CheckAlignment(a->AllocAligned(s + 1, 2), s + 1, 2);
96 CheckAlignment(a->AllocAligned(s + 2, 2), s + 2, 2);
97 CheckAlignment(a->AllocAligned(s + 3, 4), s + 3, 4);
98 CheckAlignment(a->AllocAligned(s + 4, 4), s + 4, 4);
99 CheckAlignment(a->AllocAligned(s + 5, 4), s + 5, 4);
100 CheckAlignment(a->AllocAligned(s + 6, 4), s + 6, 4);
101
102 // Free
103 for (int i = 0; i < 100; i++) {
104 int i2 = i * i;
105 a->Free(a->Alloc(i2), i2);
106 }
107
108 // Memdup
109 char mem[500];
110 for (int i = 0; i < 500; i++) mem[i] = i & 255;
111 char* mem2 = a->Memdup(mem, sizeof(mem));
112 TC3_CHECK_EQ(0, memcmp(mem, mem2, sizeof(mem)));
113
114 // MemdupPlusNUL
115 const char* msg_mpn = "won't use all this length";
116 char* msg2_mpn = a->MemdupPlusNUL(msg_mpn, 10);
117 TC3_CHECK_EQ(0, strcmp(msg2_mpn, "won't use "));
118 a->Free(msg2_mpn, 11);
119
120 // Strdup
121 const char* msg = "arena unit test is cool...";
122 char* msg2 = a->Strdup(msg);
123 TC3_CHECK_EQ(0, strcmp(msg, msg2));
124 a->Free(msg2, strlen(msg) + 1);
125
126 // Strndup
127 char* msg3 = a->Strndup(msg, 10);
128 TC3_CHECK_EQ(0, strncmp(msg3, msg, 10));
129 a->Free(msg3, 10);
130 TC3_CHECK(!a->is_empty());
131
132 // Reset
133 a->Reset();
134 TC3_CHECK(a->is_empty());
135
136 // Realloc
137 char* m1 = a->Alloc(blksize / 2);
138 CheckMemory(m1, blksize / 2);
139 TC3_CHECK(!a->is_empty());
140 CheckMemory(a->Alloc(blksize / 2), blksize / 2); // Allocate another block
141 m1 = a->Realloc(m1, blksize / 2, blksize);
142 CheckMemory(m1, blksize);
143 m1 = a->Realloc(m1, blksize, 23456);
144 CheckMemory(m1, 23456);
145
146 // Shrink
147 m1 = a->Shrink(m1, 200);
148 CheckMemory(m1, 200);
149 m1 = a->Shrink(m1, 100);
150 CheckMemory(m1, 100);
151 m1 = a->Shrink(m1, 1);
152 CheckMemory(m1, 1);
153 a->Free(m1, 1);
154 TC3_CHECK(!a->is_empty());
155
156 // Calloc
157 char* m2 = a->Calloc(2000);
158 for (int i = 0; i < 2000; ++i) {
159 TC3_CHECK_EQ(0, m2[i]);
160 }
161
162 // bytes_until_next_allocation
163 a->Reset();
164 TC3_CHECK(a->is_empty());
165 int alignment = blksize - a->bytes_until_next_allocation();
166 TC3_VLOG(INFO) << "Alignment overhead in initial block = " << alignment;
167
168 s = a->bytes_until_next_allocation() - 1;
169 CheckMemory(a->Alloc(s), s);
170 TC3_CHECK_EQ(a->bytes_until_next_allocation(), 1);
171 CheckMemory(a->Alloc(1), 1);
172 TC3_CHECK_EQ(a->bytes_until_next_allocation(), 0);
173
174 CheckMemory(a->Alloc(2 * blksize), 2 * blksize);
175 TC3_CHECK_EQ(a->bytes_until_next_allocation(), 0);
176
177 CheckMemory(a->Alloc(1), 1);
178 TC3_CHECK_EQ(a->bytes_until_next_allocation(), blksize - 1);
179
180 s = blksize / 2;
181 char* m0 = a->Alloc(s);
182 CheckMemory(m0, s);
183 TC3_CHECK_EQ(a->bytes_until_next_allocation(), blksize - s - 1);
184 m0 = a->Shrink(m0, 1);
185 CheckMemory(m0, 1);
186 TC3_CHECK_EQ(a->bytes_until_next_allocation(), blksize - 2);
187
188 a->Reset();
189 TC3_CHECK(a->is_empty());
190 TC3_CHECK_EQ(a->bytes_until_next_allocation(), blksize - alignment);
191 }
192
EnsureNoAddressInRangeIsPoisoned(void * buffer,size_t range_size)193 static void EnsureNoAddressInRangeIsPoisoned(void* buffer, size_t range_size) {
194 #ifdef ADDRESS_SANITIZER
195 TC3_CHECK_EQ(nullptr, __asan_region_is_poisoned(buffer, range_size));
196 #endif
197 }
198
DoTest(const char * label,int blksize,char * buffer)199 static void DoTest(const char* label, int blksize, char* buffer) {
200 {
201 UnsafeArena ua(buffer, blksize);
202 TestArena((std::string("UnsafeArena") + label).c_str(), &ua, blksize);
203 }
204 EnsureNoAddressInRangeIsPoisoned(buffer, blksize);
205 }
206
207 //------------------------------------------------------------------------
208 class BasicTest : public ::testing::TestWithParam<int> {};
209
210 INSTANTIATE_TEST_SUITE_P(AllSizes, BasicTest,
211 ::testing::Values(BaseArena::kDefaultAlignment + 1, 10,
212 100, 1024, 12345, 123450, 131072,
213 1234500));
214
TEST_P(BasicTest,DoTest)215 TEST_P(BasicTest, DoTest) {
216 const int blksize = GetParam();
217
218 // Allocate some memory from heap first
219 char* tmp[100];
220 for (int i = 0; i < TC3_ARRAYSIZE(tmp); i++) {
221 tmp[i] = new char[i * i];
222 }
223
224 // Initial buffer for testing pre-allocated arenas
225 char* buffer = new char[blksize + BaseArena::kDefaultAlignment];
226
227 DoTest("", blksize, nullptr);
228 DoTest("(p0)", blksize, buffer + 0);
229 DoTest("(p1)", blksize, buffer + 1);
230 DoTest("(p2)", blksize, buffer + 2);
231 DoTest("(p3)", blksize, buffer + 3);
232 DoTest("(p4)", blksize, buffer + 4);
233 DoTest("(p5)", blksize, buffer + 5);
234
235 // Free up the allocated heap memory
236 for (char* s : tmp) {
237 delete[] s;
238 }
239
240 delete[] buffer;
241 }
242
243 //------------------------------------------------------------------------
244 // NOTE: these stats will only be accurate in non-debug mode (otherwise
245 // they'll all be 0). So: if you want accurate timing, run in "normal"
246 // or "opt" mode. If you want accurate stats, run in "debug" mode.
ShowStatus(const char * const header,const BaseArena::Status & status)247 void ShowStatus(const char* const header, const BaseArena::Status& status) {
248 printf("\n--- status: %s\n", header);
249 printf(" %zu bytes allocated\n", status.bytes_allocated());
250 }
251
252 // This just tests the arena code proper, without use of allocators of
253 // gladiators or STL or anything like that
TestArena2(UnsafeArena * const arena)254 void TestArena2(UnsafeArena* const arena) {
255 const char sshort[] = "This is a short string";
256 char slong[3000];
257 memset(slong, 'a', sizeof(slong));
258 slong[sizeof(slong) - 1] = '\0';
259
260 char* s1 = arena->Strdup(sshort);
261 char* s2 = arena->Strdup(slong);
262 char* s3 = arena->Strndup(sshort, 100);
263 char* s4 = arena->Strndup(slong, 100);
264 char* s5 = arena->Memdup(sshort, 10);
265 char* s6 = arena->Realloc(s5, 10, 20);
266 arena->Shrink(s5, 10); // get s5 back to using 10 bytes again
267 char* s7 = arena->Memdup(slong, 10);
268 char* s8 = arena->Realloc(s7, 10, 5);
269 char* s9 = arena->Strdup(s1);
270 char* s10 = arena->Realloc(s4, 100, 10);
271 char* s11 = arena->Realloc(s4, 10, 100);
272 char* s12 = arena->Strdup(s9);
273 char* s13 = arena->Realloc(s9, sizeof(sshort) - 1, 100000); // won't fit :-)
274
275 TC3_CHECK_EQ(0, strcmp(s1, sshort));
276 TC3_CHECK_EQ(0, strcmp(s2, slong));
277 TC3_CHECK_EQ(0, strcmp(s3, sshort));
278 // s4 was realloced so it is not safe to read from
279 TC3_CHECK_EQ(0, strncmp(s5, sshort, 10));
280 TC3_CHECK_EQ(0, strncmp(s6, sshort, 10));
281 TC3_CHECK_EQ(s5, s6); // Should have room to grow here
282 // only the first 5 bytes of s7 should match; the realloc should have
283 // caused the next byte to actually go to s9
284 TC3_CHECK_EQ(0, strncmp(s7, slong, 5));
285 TC3_CHECK_EQ(s7, s8); // Realloc-smaller should cause us to realloc in place
286 // s9 was realloced so it is not safe to read from
287 TC3_CHECK_EQ(s10, s4); // Realloc-smaller should cause us to realloc in place
288 // Even though we're back to prev size, we had to move the pointer. Thus
289 // only the first 10 bytes are known since we grew from 10 to 100
290 TC3_CHECK_NE(s11, s4);
291 TC3_CHECK_EQ(0, strncmp(s11, slong, 10));
292 TC3_CHECK_EQ(0, strcmp(s12, s1));
293 TC3_CHECK_NE(s12, s13); // too big to grow-in-place, so we should move
294 }
295
296 //--------------------------------------------------------------------
297 // Test some fundamental STL containers
298
299 template <typename T>
300 struct test_hash {
operator ()libtextclassifier3::test_hash301 int operator()(const T&) const { return 0; }
operator ()libtextclassifier3::test_hash302 inline bool operator()(const T& s1, const T& s2) const { return s1 < s2; }
303 };
304 template <>
305 struct test_hash<const char*> {
operator ()libtextclassifier3::test_hash306 int operator()(const char*) const { return 0; }
307
operator ()libtextclassifier3::test_hash308 inline bool operator()(const char* s1, const char* s2) const {
309 return (s1 != s2) &&
310 (s2 == nullptr || (s1 != nullptr && strcmp(s1, s2) < 0));
311 }
312 };
313
314 // temp definitions from strutil.h, until the compiler error
315 // generated by #including that file is fixed.
316 struct streq {
operator ()libtextclassifier3::streq317 bool operator()(const char* s1, const char* s2) const {
318 return ((s1 == nullptr && s2 == nullptr) ||
319 (s1 && s2 && *s1 == *s2 && strcmp(s1, s2) == 0));
320 }
321 };
322 struct strlt {
operator ()libtextclassifier3::strlt323 bool operator()(const char* s1, const char* s2) const {
324 return (s1 != s2) &&
325 (s2 == nullptr || (s1 != nullptr && strcmp(s1, s2) < 0));
326 }
327 };
328
DoPoisonTest(BaseArena * b,size_t size)329 void DoPoisonTest(BaseArena* b, size_t size) {
330 #ifdef ADDRESS_SANITIZER
331 TC3_LOG(INFO) << "DoPoisonTest(" << b << ", " << size << ")";
332 char* c1 = b->SlowAlloc(size);
333 char* c2 = b->SlowAlloc(size);
334 TC3_CHECK_EQ(nullptr, __asan_region_is_poisoned(c1, size));
335 TC3_CHECK_EQ(nullptr, __asan_region_is_poisoned(c2, size));
336 char* c3 = b->SlowRealloc(c2, size, size / 2);
337 TC3_CHECK_EQ(nullptr, __asan_region_is_poisoned(c3, size / 2));
338 TC3_CHECK_NE(nullptr, __asan_region_is_poisoned(c2, size));
339 b->Reset();
340 TC3_CHECK_NE(nullptr, __asan_region_is_poisoned(c1, size));
341 TC3_CHECK_NE(nullptr, __asan_region_is_poisoned(c2, size));
342 TC3_CHECK_NE(nullptr, __asan_region_is_poisoned(c3, size / 2));
343 #endif
344 }
345
TEST(ArenaTest,TestPoison)346 TEST(ArenaTest, TestPoison) {
347 {
348 UnsafeArena arena(512);
349 DoPoisonTest(&arena, 128);
350 DoPoisonTest(&arena, 256);
351 DoPoisonTest(&arena, 512);
352 DoPoisonTest(&arena, 1024);
353 }
354
355 char* buffer = new char[512];
356 {
357 UnsafeArena arena(buffer, 512);
358 DoPoisonTest(&arena, 128);
359 DoPoisonTest(&arena, 256);
360 DoPoisonTest(&arena, 512);
361 DoPoisonTest(&arena, 1024);
362 }
363 EnsureNoAddressInRangeIsPoisoned(buffer, 512);
364
365 delete[] buffer;
366 }
367
368 //------------------------------------------------------------------------
369
370 template <class A>
TestStrndupUnterminated()371 void TestStrndupUnterminated() {
372 const char kFoo[3] = {'f', 'o', 'o'};
373 char* source = new char[3];
374 memcpy(source, kFoo, sizeof(kFoo));
375 A arena(4096);
376 char* dup = arena.Strndup(source, sizeof(kFoo));
377 TC3_CHECK_EQ(0, memcmp(dup, kFoo, sizeof(kFoo)));
378 delete[] source;
379 }
380
TEST(ArenaTest,StrndupWithUnterminatedStringUnsafe)381 TEST(ArenaTest, StrndupWithUnterminatedStringUnsafe) {
382 TestStrndupUnterminated<UnsafeArena>();
383 }
384
385 } // namespace libtextclassifier3
386