1 /*
2  * Copyright (C) 2013 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 "base/arena_allocator.h"
18 #include "base/arena_bit_vector.h"
19 #include "base/memory_tool.h"
20 #include "gtest/gtest.h"
21 
22 namespace art {
23 
24 class ArenaAllocatorTest : public testing::Test {
25  protected:
NumberOfArenas(ArenaAllocator * arena)26   size_t NumberOfArenas(ArenaAllocator* arena) {
27     size_t result = 0u;
28     for (Arena* a = arena->arena_head_; a != nullptr; a = a->next_) {
29       ++result;
30     }
31     return result;
32   }
33 };
34 
TEST_F(ArenaAllocatorTest,Test)35 TEST_F(ArenaAllocatorTest, Test) {
36   ArenaPool pool;
37   ArenaAllocator arena(&pool);
38   ArenaBitVector bv(&arena, 10, true);
39   bv.SetBit(5);
40   EXPECT_EQ(1U, bv.GetStorageSize());
41   bv.SetBit(35);
42   EXPECT_EQ(2U, bv.GetStorageSize());
43 }
44 
TEST_F(ArenaAllocatorTest,MakeDefined)45 TEST_F(ArenaAllocatorTest, MakeDefined) {
46   // Regression test to make sure we mark the allocated area defined.
47   ArenaPool pool;
48   static constexpr size_t kSmallArraySize = 10;
49   static constexpr size_t kLargeArraySize = 50;
50   uint32_t* small_array;
51   {
52     // Allocate a small array from an arena and release it.
53     ArenaAllocator arena(&pool);
54     small_array = arena.AllocArray<uint32_t>(kSmallArraySize);
55     ASSERT_EQ(0u, small_array[kSmallArraySize - 1u]);
56   }
57   {
58     // Reuse the previous arena and allocate more than previous allocation including red zone.
59     ArenaAllocator arena(&pool);
60     uint32_t* large_array = arena.AllocArray<uint32_t>(kLargeArraySize);
61     ASSERT_EQ(0u, large_array[kLargeArraySize - 1u]);
62     // Verify that the allocation was made on the same arena.
63     ASSERT_EQ(small_array, large_array);
64   }
65 }
66 
TEST_F(ArenaAllocatorTest,LargeAllocations)67 TEST_F(ArenaAllocatorTest, LargeAllocations) {
68   {
69     ArenaPool pool;
70     ArenaAllocator arena(&pool);
71     // Note: Leaving some space for memory tool red zones.
72     void* alloc1 = arena.Alloc(Arena::kDefaultSize * 5 / 8);
73     void* alloc2 = arena.Alloc(Arena::kDefaultSize * 2 / 8);
74     ASSERT_NE(alloc1, alloc2);
75     ASSERT_EQ(1u, NumberOfArenas(&arena));
76   }
77   {
78     ArenaPool pool;
79     ArenaAllocator arena(&pool);
80     void* alloc1 = arena.Alloc(Arena::kDefaultSize * 13 / 16);
81     void* alloc2 = arena.Alloc(Arena::kDefaultSize * 11 / 16);
82     ASSERT_NE(alloc1, alloc2);
83     ASSERT_EQ(2u, NumberOfArenas(&arena));
84     void* alloc3 = arena.Alloc(Arena::kDefaultSize * 7 / 16);
85     ASSERT_NE(alloc1, alloc3);
86     ASSERT_NE(alloc2, alloc3);
87     ASSERT_EQ(3u, NumberOfArenas(&arena));
88   }
89   {
90     ArenaPool pool;
91     ArenaAllocator arena(&pool);
92     void* alloc1 = arena.Alloc(Arena::kDefaultSize * 13 / 16);
93     void* alloc2 = arena.Alloc(Arena::kDefaultSize * 9 / 16);
94     ASSERT_NE(alloc1, alloc2);
95     ASSERT_EQ(2u, NumberOfArenas(&arena));
96     // Note: Leaving some space for memory tool red zones.
97     void* alloc3 = arena.Alloc(Arena::kDefaultSize * 5 / 16);
98     ASSERT_NE(alloc1, alloc3);
99     ASSERT_NE(alloc2, alloc3);
100     ASSERT_EQ(2u, NumberOfArenas(&arena));
101   }
102   {
103     ArenaPool pool;
104     ArenaAllocator arena(&pool);
105     void* alloc1 = arena.Alloc(Arena::kDefaultSize * 9 / 16);
106     void* alloc2 = arena.Alloc(Arena::kDefaultSize * 13 / 16);
107     ASSERT_NE(alloc1, alloc2);
108     ASSERT_EQ(2u, NumberOfArenas(&arena));
109     // Note: Leaving some space for memory tool red zones.
110     void* alloc3 = arena.Alloc(Arena::kDefaultSize * 5 / 16);
111     ASSERT_NE(alloc1, alloc3);
112     ASSERT_NE(alloc2, alloc3);
113     ASSERT_EQ(2u, NumberOfArenas(&arena));
114   }
115   {
116     ArenaPool pool;
117     ArenaAllocator arena(&pool);
118     // Note: Leaving some space for memory tool red zones.
119     for (size_t i = 0; i != 15; ++i) {
120       arena.Alloc(Arena::kDefaultSize * 1 / 16);    // Allocate 15 times from the same arena.
121       ASSERT_EQ(i + 1u, NumberOfArenas(&arena));
122       arena.Alloc(Arena::kDefaultSize * 17 / 16);   // Allocate a separate arena.
123       ASSERT_EQ(i + 2u, NumberOfArenas(&arena));
124     }
125   }
126 }
127 
TEST_F(ArenaAllocatorTest,AllocAlignment)128 TEST_F(ArenaAllocatorTest, AllocAlignment) {
129   ArenaPool pool;
130   ArenaAllocator arena(&pool);
131   for (size_t iterations = 0; iterations <= 10; ++iterations) {
132     for (size_t size = 1; size <= ArenaAllocator::kAlignment + 1; ++size) {
133       void* allocation = arena.Alloc(size);
134       EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(allocation))
135           << reinterpret_cast<uintptr_t>(allocation);
136     }
137   }
138 }
139 
TEST_F(ArenaAllocatorTest,ReallocReuse)140 TEST_F(ArenaAllocatorTest, ReallocReuse) {
141   // Realloc does not reuse arenas when running under sanitization. So we cannot do those
142   if (RUNNING_ON_MEMORY_TOOL != 0) {
143     printf("WARNING: TEST DISABLED FOR MEMORY_TOOL\n");
144     return;
145   }
146 
147   {
148     // Case 1: small aligned allocation, aligned extend inside arena.
149     ArenaPool pool;
150     ArenaAllocator arena(&pool);
151 
152     const size_t original_size = ArenaAllocator::kAlignment * 2;
153     void* original_allocation = arena.Alloc(original_size);
154 
155     const size_t new_size = ArenaAllocator::kAlignment * 3;
156     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
157     EXPECT_EQ(original_allocation, realloc_allocation);
158   }
159 
160   {
161     // Case 2: small aligned allocation, non-aligned extend inside arena.
162     ArenaPool pool;
163     ArenaAllocator arena(&pool);
164 
165     const size_t original_size = ArenaAllocator::kAlignment * 2;
166     void* original_allocation = arena.Alloc(original_size);
167 
168     const size_t new_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2);
169     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
170     EXPECT_EQ(original_allocation, realloc_allocation);
171   }
172 
173   {
174     // Case 3: small non-aligned allocation, aligned extend inside arena.
175     ArenaPool pool;
176     ArenaAllocator arena(&pool);
177 
178     const size_t original_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2);
179     void* original_allocation = arena.Alloc(original_size);
180 
181     const size_t new_size = ArenaAllocator::kAlignment * 4;
182     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
183     EXPECT_EQ(original_allocation, realloc_allocation);
184   }
185 
186   {
187     // Case 4: small non-aligned allocation, aligned non-extend inside arena.
188     ArenaPool pool;
189     ArenaAllocator arena(&pool);
190 
191     const size_t original_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2);
192     void* original_allocation = arena.Alloc(original_size);
193 
194     const size_t new_size = ArenaAllocator::kAlignment * 3;
195     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
196     EXPECT_EQ(original_allocation, realloc_allocation);
197   }
198 
199   // The next part is brittle, as the default size for an arena is variable, and we don't know about
200   // sanitization.
201 
202   {
203     // Case 5: large allocation, aligned extend into next arena.
204     ArenaPool pool;
205     ArenaAllocator arena(&pool);
206 
207     const size_t original_size = Arena::kDefaultSize - ArenaAllocator::kAlignment * 5;
208     void* original_allocation = arena.Alloc(original_size);
209 
210     const size_t new_size = Arena::kDefaultSize + ArenaAllocator::kAlignment * 2;
211     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
212     EXPECT_NE(original_allocation, realloc_allocation);
213   }
214 
215   {
216     // Case 6: large allocation, non-aligned extend into next arena.
217     ArenaPool pool;
218     ArenaAllocator arena(&pool);
219 
220     const size_t original_size = Arena::kDefaultSize -
221         ArenaAllocator::kAlignment * 4 -
222         ArenaAllocator::kAlignment / 2;
223     void* original_allocation = arena.Alloc(original_size);
224 
225     const size_t new_size = Arena::kDefaultSize +
226         ArenaAllocator::kAlignment * 2 +
227         ArenaAllocator::kAlignment / 2;
228     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
229     EXPECT_NE(original_allocation, realloc_allocation);
230   }
231 }
232 
TEST_F(ArenaAllocatorTest,ReallocAlignment)233 TEST_F(ArenaAllocatorTest, ReallocAlignment) {
234   {
235     // Case 1: small aligned allocation, aligned extend inside arena.
236     ArenaPool pool;
237     ArenaAllocator arena(&pool);
238 
239     const size_t original_size = ArenaAllocator::kAlignment * 2;
240     void* original_allocation = arena.Alloc(original_size);
241     ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation));
242 
243     const size_t new_size = ArenaAllocator::kAlignment * 3;
244     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
245     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation));
246 
247     void* after_alloc = arena.Alloc(1);
248     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc));
249   }
250 
251   {
252     // Case 2: small aligned allocation, non-aligned extend inside arena.
253     ArenaPool pool;
254     ArenaAllocator arena(&pool);
255 
256     const size_t original_size = ArenaAllocator::kAlignment * 2;
257     void* original_allocation = arena.Alloc(original_size);
258     ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation));
259 
260     const size_t new_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2);
261     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
262     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation));
263 
264     void* after_alloc = arena.Alloc(1);
265     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc));
266   }
267 
268   {
269     // Case 3: small non-aligned allocation, aligned extend inside arena.
270     ArenaPool pool;
271     ArenaAllocator arena(&pool);
272 
273     const size_t original_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2);
274     void* original_allocation = arena.Alloc(original_size);
275     ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation));
276 
277     const size_t new_size = ArenaAllocator::kAlignment * 4;
278     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
279     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation));
280 
281     void* after_alloc = arena.Alloc(1);
282     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc));
283   }
284 
285   {
286     // Case 4: small non-aligned allocation, aligned non-extend inside arena.
287     ArenaPool pool;
288     ArenaAllocator arena(&pool);
289 
290     const size_t original_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2);
291     void* original_allocation = arena.Alloc(original_size);
292     ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation));
293 
294     const size_t new_size = ArenaAllocator::kAlignment * 3;
295     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
296     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation));
297 
298     void* after_alloc = arena.Alloc(1);
299     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc));
300   }
301 
302   // The next part is brittle, as the default size for an arena is variable, and we don't know about
303   // sanitization.
304 
305   {
306     // Case 5: large allocation, aligned extend into next arena.
307     ArenaPool pool;
308     ArenaAllocator arena(&pool);
309 
310     const size_t original_size = Arena::kDefaultSize - ArenaAllocator::kAlignment * 5;
311     void* original_allocation = arena.Alloc(original_size);
312     ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation));
313 
314     const size_t new_size = Arena::kDefaultSize + ArenaAllocator::kAlignment * 2;
315     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
316     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation));
317 
318     void* after_alloc = arena.Alloc(1);
319     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc));
320   }
321 
322   {
323     // Case 6: large allocation, non-aligned extend into next arena.
324     ArenaPool pool;
325     ArenaAllocator arena(&pool);
326 
327     const size_t original_size = Arena::kDefaultSize -
328         ArenaAllocator::kAlignment * 4 -
329         ArenaAllocator::kAlignment / 2;
330     void* original_allocation = arena.Alloc(original_size);
331     ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation));
332 
333     const size_t new_size = Arena::kDefaultSize +
334         ArenaAllocator::kAlignment * 2 +
335         ArenaAllocator::kAlignment / 2;
336     void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size);
337     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation));
338 
339     void* after_alloc = arena.Alloc(1);
340     EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc));
341   }
342 }
343 
344 
345 }  // namespace art
346