1 // Copyright (C) 2018 The Android Open Source Project
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 // http://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 #include "aemu/base/SubAllocator.h"
15
16 #include "aemu/base/ArraySize.h"
17 #include "aemu/base/files/MemStream.h"
18
19 #include <gtest/gtest.h>
20
21 #include <random>
22 #include <string>
23
24 namespace android {
25 namespace base {
26
27 // Test: can allocate/free memory of various sizes,
28 // and if the allocation reasonably cannot be satisfied,
29 // the allocation fails.
TEST(SubAllocator,Basic)30 TEST(SubAllocator, Basic) {
31 const size_t pageSizesToTest[] = {
32 1, 2, 4, 8, 16, 32, 64, 128,
33 256, 512, 1024, 2048, 4096,
34 8192, 16384, 32768, 65536,
35 };
36
37 const size_t sizesToTest[] = {
38 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
39 11, 12, 13, 14, 15, 16, 32, 33, 64, 65,
40 127, 129, 1023, 1024,
41 2047, 2048, 2049,
42 4096, 16384, 65535
43 };
44
45 const size_t allocCounts[] = {
46 1, 2, 3, 4,
47 };
48
49 const size_t bufferSize = 65536;
50
51 std::vector<uint8_t> buffer(bufferSize);
52
53 for (size_t pageSize : pageSizesToTest) {
54 SubAllocator subAlloc(
55 buffer.data(),
56 (uint64_t)bufferSize,
57 pageSize);
58 EXPECT_TRUE(subAlloc.empty());
59
60 for (size_t allocCount : allocCounts) {
61 std::vector<void*> ptrs;
62
63 for (size_t allocSize : sizesToTest) {
64
65 size_t trySize = allocSize / allocCount;
66
67 size_t atomSize =
68 pageSize *
69 ((trySize + pageSize - 1) / pageSize);
70
71 size_t total = 0;
72
73 for (size_t i = 0; i < allocCount; ++i) {
74
75 void* ptr = subAlloc.alloc(trySize);
76
77 if (ptr) {
78 total += atomSize;
79 } else {
80 EXPECT_TRUE(
81 (trySize == 0) ||
82 (total + atomSize > bufferSize)) <<
83 "pageSize " << pageSize <<
84 "allocCount " << allocCount <<
85 "trySize " << trySize <<
86 "try# " << i <<
87 "allocedSoFar " << total;
88 }
89
90 ptrs.push_back(ptr);
91 }
92
93 for (auto ptr : ptrs) {
94 subAlloc.free(ptr);
95 }
96 EXPECT_TRUE(subAlloc.empty());
97 }
98 }
99 }
100 }
101
102 // Test: freeAll resets the state and allows more allocation
103 // without individual freeing.
TEST(SubAllocator,FreeAll)104 TEST(SubAllocator, FreeAll) {
105 const size_t pageSize = 64;
106 const size_t bufferSize = 65536;
107
108 std::vector<uint8_t> buffer(bufferSize);
109
110 SubAllocator subAlloc(
111 buffer.data(),
112 (uint64_t)bufferSize,
113 (uint64_t)pageSize);
114
115 const size_t fillCount = bufferSize / pageSize;
116 const size_t numTrials = 10;
117
118 for (size_t i = 0; i < numTrials; ++i) {
119 for (size_t j = 0; j < fillCount; ++j) {
120 void* ptr = subAlloc.alloc(pageSize);
121 EXPECT_NE(nullptr, ptr);
122 }
123 subAlloc.freeAll();
124 EXPECT_TRUE(subAlloc.empty());
125 }
126 }
127
128 // Test: Random testing
TEST(SubAllocator,Random)129 TEST(SubAllocator, Random) {
130 // Given the buffer size, any combination of
131 // page size, alloc size, and count should work
132 // over a single run.
133 const size_t pageSizesToTest[] = {
134 1, 2, 4, 8, 16, 32, 64, 128,
135 256, 512, 1024, 2048, 4096,
136 };
137
138 const size_t sizesToTest[] = {
139 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
140 11, 12, 13, 14, 15, 16, 32, 33, 64, 65,
141 127, 129, 1023, 1024,
142 2047, 2048, 2049,
143 4096,
144 };
145
146 const size_t allocCounts[] = {
147 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
148 };
149
150 const size_t numSizes = arraySize(sizesToTest);
151 const size_t numCounts = arraySize(allocCounts);
152
153 const size_t bufferSize = 65536;
154 std::vector<uint8_t> buffer(bufferSize);
155
156 const size_t numTrials = 1000;
157
158 std::default_random_engine generator;
159 generator.seed(0);
160
161 std::uniform_int_distribution<int> sizeDistribution(0, numSizes - 1);
162 std::uniform_int_distribution<int> countDistribution(0, numCounts - 1);
163
164 for (auto pageSize : pageSizesToTest) {
165 SubAllocator subAlloc(
166 buffer.data(),
167 (uint64_t)bufferSize,
168 pageSize);
169
170 for (size_t i = 0; i < numTrials; ++i) {
171 size_t count =
172 allocCounts[countDistribution(generator)];
173
174 std::vector<void*> ptrs;
175
176 size_t total = 0;
177
178 for (size_t j = 0; j < count; ++j) {
179 size_t allocSize =
180 sizesToTest[sizeDistribution(generator)];
181 void* ptr = subAlloc.alloc(allocSize);
182
183 if (ptr) {
184 total += allocSize;
185 }
186
187 ptrs.push_back(ptr);
188 EXPECT_NE(nullptr, ptr) <<
189 "pageSize " << pageSize <<
190 "runCount " << count <<
191 "alloc# " << j <<
192 "size " << allocSize <<
193 "total " << total;
194 }
195
196 for (auto ptr : ptrs) {
197 subAlloc.free(ptr);
198 }
199 EXPECT_TRUE(subAlloc.empty());
200 }
201 }
202 }
203
204 // Test save/load of suballocator snapshot
TEST(SubAllocator,Snapshot)205 TEST(SubAllocator, Snapshot) {
206 MemStream snapshotStream;
207 std::vector<uint8_t*> storage(4096, 0);
208
209 SubAllocator subAlloc(
210 storage.data(), (uint64_t)storage.size(), 8);
211
212 const size_t numBufs = 6;
213
214 // Alloc/free a few things.
215
216 uint8_t* bufs[numBufs] = {
217 (uint8_t*)subAlloc.alloc(16),
218 (uint8_t*)subAlloc.alloc(8),
219 (uint8_t*)subAlloc.alloc(32),
220 (uint8_t*)subAlloc.alloc(64),
221 (uint8_t*)subAlloc.alloc(8),
222 (uint8_t*)subAlloc.alloc(128),
223 };
224
225 subAlloc.free(bufs[3]);
226 bufs[3] = (uint8_t*)subAlloc.alloc(24);
227 subAlloc.free(bufs[4]);
228 bufs[4] = (uint8_t*)subAlloc.alloc(64);
229 subAlloc.free(bufs[0]);
230 bufs[0] = (uint8_t*)subAlloc.alloc(8);
231
232 for (uint32_t i = 0; i < numBufs; ++i) {
233 EXPECT_NE(nullptr, bufs[i]);
234 }
235
236 // Record offsets
237
238 uint64_t offs[numBufs];
239
240 for (uint32_t i = 0; i < numBufs; ++i) {
241 offs[i] = subAlloc.getOffset(bufs[i]);
242 }
243
244 // Write special values
245 for (uint32_t i = 0; i < numBufs; ++i) {
246 *(bufs[i]) = (uint8_t)i;
247 }
248
249 // Save/load the snapshot
250 subAlloc.save(&snapshotStream);
251 subAlloc.load(&snapshotStream);
252 EXPECT_FALSE(subAlloc.empty());
253
254 // Set the post load buffer to our original one
255 EXPECT_TRUE(subAlloc.postLoad(storage.data()));
256
257 // Do some allocations. None should intersect with any
258 // previously allocated buffer.
259 for (uint32_t i = 0; i < 10; ++i) {
260 uint8_t* buf = (uint8_t*)subAlloc.alloc(8);
261 if (!buf) continue;
262 for (uint32_t j = 0; j < numBufs; ++j) {
263 EXPECT_NE(bufs[j], buf);
264 }
265 }
266
267 // Expect all data to remain unchanged
268 for (uint32_t i = 0; i < numBufs; ++i) {
269 EXPECT_EQ((uint8_t)i, *(bufs[i]));
270 }
271
272 // Expect all offsets to be the same
273 for (uint32_t i = 0; i < numBufs; ++i) {
274 EXPECT_EQ(offs[i], subAlloc.getOffset(bufs[i]));
275 }
276
277 // Freeing everything should still work
278 for (uint32_t i = 0; i < numBufs; ++i) {
279 EXPECT_TRUE(subAlloc.free(bufs[i]));
280 }
281
282 // Allocate all buffers again
283 for (uint32_t i = 0; i < numBufs; ++i) {
284 bufs[i] = (uint8_t*)subAlloc.alloc(8);
285 EXPECT_NE(nullptr, bufs[i]);
286 }
287 }
288
289 } // namespace base
290 } // namespace android
291