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
22namespace art {
23
24class ArenaAllocatorTest : public testing::Test {
25 protected:
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
35TEST_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
45TEST_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
67TEST_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
128TEST_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
140TEST_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
233TEST_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