1 /*
2 * Copyright (C) 2016 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 "gtest/gtest.h"
18
19 #include "chre/util/memory_pool.h"
20 #include "chre/util/nested_data_ptr.h"
21
22 #include <random>
23 #include <vector>
24
25 using ::chre::MemoryPool;
26 using ::chre::NestedDataPtr;
27
TEST(MemoryPool,ExhaustPool)28 TEST(MemoryPool, ExhaustPool) {
29 MemoryPool<int, 3> memoryPool;
30 EXPECT_EQ(memoryPool.getFreeBlockCount(), 3);
31 EXPECT_NE(memoryPool.allocate(), nullptr);
32 EXPECT_EQ(memoryPool.getFreeBlockCount(), 2);
33 EXPECT_NE(memoryPool.allocate(), nullptr);
34 EXPECT_EQ(memoryPool.getFreeBlockCount(), 1);
35 EXPECT_NE(memoryPool.allocate(), nullptr);
36 EXPECT_EQ(memoryPool.getFreeBlockCount(), 0);
37 EXPECT_EQ(memoryPool.allocate(), nullptr);
38 EXPECT_EQ(memoryPool.getFreeBlockCount(), 0);
39 }
40
TEST(MemoryPool,OwnershipDeallocation)41 TEST(MemoryPool, OwnershipDeallocation) {
42 MemoryPool<int, 3> firstMemoryPool;
43 MemoryPool<int, 3> secondMemoryPool;
44
45 int *firstMemoryElement = firstMemoryPool.allocate();
46 EXPECT_TRUE(firstMemoryPool.containsAddress(firstMemoryElement));
47 EXPECT_FALSE(secondMemoryPool.containsAddress(firstMemoryElement));
48
49 EXPECT_DEATH(secondMemoryPool.deallocate(firstMemoryElement), "");
50 firstMemoryPool.deallocate(firstMemoryElement);
51 }
52
TEST(MemoryPool,ExhaustPoolThenDeallocateOneAndAllocateOne)53 TEST(MemoryPool, ExhaustPoolThenDeallocateOneAndAllocateOne) {
54 MemoryPool<int, 3> memoryPool;
55
56 // Exhaust the pool.
57 int *element1 = memoryPool.allocate();
58 int *element2 = memoryPool.allocate();
59 int *element3 = memoryPool.allocate();
60
61 // Perform some simple assignments. There is a chance we crash here if things
62 // are not implemented correctly.
63 *element1 = 0xcafe;
64 *element2 = 0xbeef;
65 *element3 = 0xface;
66
67 // Free one element and then allocate another.
68 memoryPool.deallocate(element1);
69 EXPECT_EQ(memoryPool.getFreeBlockCount(), 1);
70 element1 = memoryPool.allocate();
71 EXPECT_NE(element1, nullptr);
72
73 // Ensure that the pool remains exhausted.
74 EXPECT_EQ(memoryPool.allocate(), nullptr);
75
76 // Perform another simple assignment. There is a hope that this can crash if
77 // the pointer returned is very bad (like nullptr).
78 *element1 = 0xfade;
79
80 // Verify that the values stored were not corrupted by the deallocate
81 // allocate cycle.
82 EXPECT_EQ(*element1, 0xfade);
83 EXPECT_EQ(*element2, 0xbeef);
84 EXPECT_EQ(*element3, 0xface);
85 }
86
87 /*
88 * Pair an allocated pointer with the expected value that should be stored in
89 * that location.
90 */
91 struct AllocationExpectedValuePair {
92 size_t *allocation;
93 size_t expectedValue;
94 };
95
TEST(MemoryPool,ExhaustPoolThenRandomDeallocate)96 TEST(MemoryPool, ExhaustPoolThenRandomDeallocate) {
97 // The number of times to allocate and deallocate in random order.
98 const size_t kStressTestCount = 64;
99
100 // Construct a memory pool and a vector to maintain a list of all allocations.
101 const size_t kMemoryPoolSize = 64;
102 MemoryPool<size_t, kMemoryPoolSize> memoryPool;
103 std::vector<AllocationExpectedValuePair> allocations;
104
105 for (size_t i = 0; i < kStressTestCount; i++) {
106 // Exhaust the memory pool.
107 for (size_t j = 0; j < kMemoryPoolSize; j++) {
108 AllocationExpectedValuePair allocation = {
109 .allocation = memoryPool.allocate(),
110 .expectedValue = j,
111 };
112
113 *allocation.allocation = j;
114 allocations.push_back(allocation);
115 }
116
117 // Seed a random number generator with the loop iteration so that order is
118 // preserved across test runs.
119 std::mt19937 randomGenerator(i);
120
121 while (!allocations.empty()) {
122 // Generate a number with a uniform distribution between zero and the
123 // number of allocations remaining.
124 std::uniform_int_distribution<> distribution(0, allocations.size() - 1);
125 size_t deallocateIndex = distribution(randomGenerator);
126
127 // Verify the expected value and free the allocation.
128 EXPECT_EQ(*allocations[deallocateIndex].allocation,
129 allocations[deallocateIndex].expectedValue);
130 memoryPool.deallocate(allocations[deallocateIndex].allocation);
131
132 // Remove the freed allocation from the allocation list.
133 allocations.erase(allocations.begin() + deallocateIndex);
134 }
135 }
136 }
137
TEST(MemoryPool,FindAnElement)138 TEST(MemoryPool, FindAnElement) {
139 MemoryPool<int, 4> memoryPool;
140
141 // Exhaust the pool.
142 int *element1 = memoryPool.allocate();
143 int *element2 = memoryPool.allocate();
144 int *element3 = memoryPool.allocate();
145 int *element4 = memoryPool.allocate();
146
147 // Perform some simple assignments. There is a chance we crash here if things
148 // are not implemented correctly.
149 *element1 = 0xcafe;
150 *element2 = 0xbeef;
151 *element3 = 0xface;
152 *element4 = 0xface;
153
154 // Do a find with a known element.
155 int *foundElement = memoryPool.find(
156 [](int *element, void *data) {
157 NestedDataPtr<int> value(data);
158 return *element == value;
159 },
160 NestedDataPtr<int>(0xface));
161 EXPECT_NE(foundElement, nullptr);
162 EXPECT_EQ(foundElement, element3);
163
164 // Do a find with an unknown element.
165 foundElement = memoryPool.find(
166 [](int *element, void *data) {
167 NestedDataPtr<int> value(data);
168 return *element == value;
169 },
170 NestedDataPtr<int>(0xaaaa));
171 EXPECT_EQ(foundElement, nullptr);
172 }
173
TEST(MemoryPool,FindAnElementAfterDeallocation)174 TEST(MemoryPool, FindAnElementAfterDeallocation) {
175 MemoryPool<int, 4> memoryPool;
176
177 // Exhaust the pool.
178 int *element1 = memoryPool.allocate();
179 int *element2 = memoryPool.allocate();
180 int *element3 = memoryPool.allocate();
181 int *element4 = memoryPool.allocate();
182
183 // Perform some simple assignments. There is a chance we crash here if things
184 // are not implemented correctly.
185 *element1 = 0xcafe;
186 *element2 = 0xbeef;
187 *element3 = 0xface;
188 *element4 = 0xface;
189
190 // Deallocate element 3 then try to find element 4.
191 memoryPool.deallocate(element3);
192 int *foundElement = memoryPool.find(
193 [](int *element, void *data) {
194 NestedDataPtr<int> value(data);
195 return *element == value;
196 },
197 NestedDataPtr<int>(0xface));
198 EXPECT_NE(foundElement, nullptr);
199 EXPECT_EQ(foundElement, element4);
200 }
201
TEST(MemoryPool,FindAnElementAfterAllMatchingAreDeallocated)202 TEST(MemoryPool, FindAnElementAfterAllMatchingAreDeallocated) {
203 MemoryPool<int, 4> memoryPool;
204
205 // Exhaust the pool.
206 int *element1 = memoryPool.allocate();
207 int *element2 = memoryPool.allocate();
208 int *element3 = memoryPool.allocate();
209 int *element4 = memoryPool.allocate();
210
211 // Perform some simple assignments. There is a chance we crash here if things
212 // are not implemented correctly.
213 *element1 = 0xcafe;
214 *element2 = 0xbeef;
215 *element3 = 0xface;
216 *element4 = 0xface;
217
218 // Deallocate element 3 then try to find element 4.
219 memoryPool.deallocate(element3);
220 int *foundElement = memoryPool.find(
221 [](int *element, void *data) {
222 NestedDataPtr<int> value(data);
223 return *element == value;
224 },
225 NestedDataPtr<int>(0xface));
226 EXPECT_NE(foundElement, nullptr);
227 EXPECT_EQ(foundElement, element4);
228
229 // Deallocate element 4 and try to find again.
230 memoryPool.deallocate(element4);
231 foundElement = memoryPool.find(
232 [](int *element, void *data) {
233 NestedDataPtr<int> value(data);
234 return *element == value;
235 },
236 NestedDataPtr<int>(0xface));
237 EXPECT_EQ(foundElement, nullptr);
238 }
239
TEST(MemoryPool,FindAnElementAfterDeallocationLargeSize)240 TEST(MemoryPool, FindAnElementAfterDeallocationLargeSize) {
241 constexpr size_t kNumElements = 1000;
242 MemoryPool<int, kNumElements> memoryPool;
243 int *elements[kNumElements];
244
245 for (size_t i = 0; i < kNumElements; ++i) {
246 elements[i] = memoryPool.allocate();
247 *elements[i] = i;
248 }
249
250 // Deallocate even elements.
251 for (size_t i = 0; i < kNumElements; ++i) {
252 if (i % 2 == 0) {
253 memoryPool.deallocate(elements[i]);
254 }
255 }
256
257 // Find odd elements.
258 for (size_t i = 0; i < kNumElements; ++i) {
259 int *foundElement = memoryPool.find(
260 [](int *element, void *data) {
261 NestedDataPtr<int> value(data);
262 return *element == value;
263 },
264 NestedDataPtr<int>(i));
265 if (i % 2 == 0) {
266 EXPECT_EQ(foundElement, nullptr);
267 } else {
268 EXPECT_NE(foundElement, nullptr);
269 EXPECT_EQ(foundElement, elements[i]);
270 }
271 }
272 }
273