1 /*
2 * Copyright 2018 The Hafnium Authors.
3 *
4 * Use of this source code is governed by a BSD-style
5 * license that can be found in the LICENSE file or at
6 * https://opensource.org/licenses/BSD-3-Clause.
7 */
8
9 #include <gmock/gmock.h>
10
11 extern "C" {
12 #include "hf/mpool.h"
13 }
14
15 namespace
16 {
17 using ::testing::Eq;
18 using ::testing::IsNull;
19 using ::testing::NotNull;
20
21 /**
22 * Checks that the given allocations come from the given chunks.
23 */
check_allocs(std::vector<std::unique_ptr<char[]>> & chunks,std::vector<uintptr_t> & allocs,size_t entries_per_chunk,size_t entry_size)24 bool check_allocs(std::vector<std::unique_ptr<char[]>>& chunks,
25 std::vector<uintptr_t>& allocs, size_t entries_per_chunk,
26 size_t entry_size)
27 {
28 size_t i, j;
29
30 if (allocs.size() != chunks.size() * entries_per_chunk) {
31 return false;
32 }
33
34 sort(allocs.begin(), allocs.end());
35 sort(chunks.begin(), chunks.end(),
36 [](const std::unique_ptr<char[]>& a,
37 const std::unique_ptr<char[]>& b) {
38 return a.get() < b.get();
39 });
40
41 for (i = 0; i < chunks.size(); i++) {
42 if ((uintptr_t)chunks[i].get() !=
43 allocs[i * entries_per_chunk]) {
44 return false;
45 }
46
47 for (j = 1; j < entries_per_chunk; j++) {
48 size_t k = i * entries_per_chunk + j;
49 if (allocs[k] != allocs[k - 1] + entry_size) {
50 return false;
51 }
52 }
53 }
54
55 return true;
56 }
57
58 /**
59 * Add chunks to the given mem pool and chunk vector.
60 */
add_chunks(std::vector<std::unique_ptr<char[]>> & chunks,struct mpool * p,size_t count,size_t size)61 static void add_chunks(std::vector<std::unique_ptr<char[]>>& chunks,
62 struct mpool* p, size_t count, size_t size)
63 {
64 size_t i;
65
66 for (i = 0; i < count; i++) {
67 chunks.emplace_back(std::make_unique<char[]>(size));
68 mpool_add_chunk(p, chunks.back().get(), size);
69 }
70 }
71
72 /**
73 * Validates allocations from a memory pool.
74 */
TEST(mpool,allocation)75 TEST(mpool, allocation)
76 {
77 struct mpool p;
78 constexpr size_t entry_size = 16;
79 constexpr size_t entries_per_chunk = 10;
80 constexpr size_t chunk_count = 10;
81 std::vector<std::unique_ptr<char[]>> chunks;
82 std::vector<uintptr_t> allocs;
83 void* ret;
84
85 mpool_init(&p, entry_size);
86
87 /* Allocate from an empty pool. */
88 EXPECT_THAT(mpool_alloc(&p), IsNull());
89
90 /*
91 * Add a chunk that is too small, it should be ignored, and allocation
92 * should return NULL.
93 */
94 mpool_add_chunk(&p, NULL, entry_size - 1);
95 EXPECT_THAT(mpool_alloc(&p), IsNull());
96
97 /* Allocate a number of chunks and add them to the pool. */
98 add_chunks(chunks, &p, chunk_count, entries_per_chunk * entry_size);
99
100 /* Allocate from the pool until we run out of memory. */
101 while ((ret = mpool_alloc(&p))) {
102 allocs.push_back((uintptr_t)ret);
103 }
104
105 /* Check that returned entries are within chunks that were added. */
106 ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
107 true);
108 }
109
110 /**
111 * Validates frees into a memory pool.
112 */
TEST(mpool,freeing)113 TEST(mpool, freeing)
114 {
115 struct mpool p;
116 constexpr size_t entry_size = 16;
117 constexpr size_t entries_per_chunk = 12;
118 constexpr size_t chunk_count = 10;
119 std::vector<std::unique_ptr<char[]>> chunks;
120 std::vector<uintptr_t> allocs;
121 size_t i;
122 alignas(entry_size) char entry[entry_size];
123 void* ret;
124
125 mpool_init(&p, entry_size);
126
127 /* Allocate from an empty pool. */
128 EXPECT_THAT(mpool_alloc(&p), IsNull());
129
130 /* Free an entry into the pool, then allocate it back. */
131 mpool_free(&p, &entry[0]);
132 EXPECT_THAT(mpool_alloc(&p), (void*)&entry[0]);
133 EXPECT_THAT(mpool_alloc(&p), IsNull());
134
135 /* Allocate a number of chunks and add them to the pool. */
136 add_chunks(chunks, &p, chunk_count, entries_per_chunk * entry_size);
137
138 /*
139 * Free again into the pool. Ensure that we get entry back on next
140 * allocation instead of something from the chunks.
141 */
142 mpool_free(&p, &entry[0]);
143 EXPECT_THAT(mpool_alloc(&p), (void*)&entry[0]);
144
145 /* Allocate from the pool until we run out of memory. */
146 while ((ret = mpool_alloc(&p))) {
147 allocs.push_back((uintptr_t)ret);
148 }
149
150 /*
151 * Free again into the pool. Ensure that we get entry back on next
152 * allocation instead of something from the chunks.
153 */
154 mpool_free(&p, &entry[0]);
155 EXPECT_THAT(mpool_alloc(&p), (void*)&entry[0]);
156
157 /* Add entries back to the pool by freeing them. */
158 for (i = 0; i < allocs.size(); i++) {
159 mpool_free(&p, (void*)allocs[i]);
160 }
161 allocs.clear();
162
163 /* Allocate from the pool until we run out of memory. */
164 while ((ret = mpool_alloc(&p))) {
165 allocs.push_back((uintptr_t)ret);
166 }
167
168 /* Check that returned entries are within chunks that were added. */
169 ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
170 true);
171 }
172
173 /**
174 * Initialises a memory pool from an existing one.
175 */
TEST(mpool,init_from)176 TEST(mpool, init_from)
177 {
178 struct mpool p, q;
179 constexpr size_t entry_size = 16;
180 constexpr size_t entries_per_chunk = 10;
181 constexpr size_t chunk_count = 10;
182 std::vector<std::unique_ptr<char[]>> chunks;
183 std::vector<uintptr_t> allocs;
184 size_t i;
185 void* ret;
186
187 mpool_init(&p, entry_size);
188
189 /* Allocate a number of chunks and add them to the pool. */
190 add_chunks(chunks, &p, chunk_count, entries_per_chunk * entry_size);
191
192 /* Allocate half of the elements. */
193 for (i = 0; i < entries_per_chunk * chunk_count / 2; i++) {
194 void* ret = mpool_alloc(&p);
195 ASSERT_THAT(ret, NotNull());
196 allocs.push_back((uintptr_t)ret);
197 }
198
199 /* Add entries back to the pool by freeing them. */
200 for (i = 0; i < allocs.size(); i++) {
201 mpool_free(&p, (void*)allocs[i]);
202 }
203 allocs.clear();
204
205 /* Initialise q from p. */
206 mpool_init_from(&q, &p);
207
208 /* Allocation from p must now fail. */
209 EXPECT_THAT(mpool_alloc(&p), IsNull());
210
211 /* Allocate from q until we run out of memory. */
212 while ((ret = mpool_alloc(&q))) {
213 allocs.push_back((uintptr_t)ret);
214 }
215
216 /* Check that returned entries are within chunks that were added. */
217 ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
218 true);
219 }
220
221 /**
222 * Initialises a memory pool from an existing one.
223 */
TEST(mpool,alloc_contiguous)224 TEST(mpool, alloc_contiguous)
225 {
226 struct mpool p;
227 constexpr size_t entry_size = 16;
228 constexpr size_t entries_per_chunk = 12;
229 constexpr size_t chunk_count = 10;
230 std::vector<std::unique_ptr<char[]>> chunks;
231 std::vector<uintptr_t> allocs;
232 size_t i;
233 void* ret;
234 uintptr_t next;
235
236 mpool_init(&p, entry_size);
237
238 /* Allocate a number of chunks and add them to the pool. */
239 add_chunks(chunks, &p, chunk_count, entries_per_chunk * entry_size);
240
241 /*
242 * Allocate entries until the remaining chunk is aligned to 2 entries,
243 * but not aligned to 4 entries.
244 */
245 do {
246 ret = mpool_alloc(&p);
247 ASSERT_THAT(ret, NotNull());
248 allocs.push_back((uintptr_t)ret);
249 next = ((uintptr_t)ret / entry_size) + 1;
250 } while ((next % 4) != 2);
251
252 /* Allocate 5 entries with an alignment of 4. So two must be skipped. */
253 ret = mpool_alloc_contiguous(&p, 5, 4);
254 ASSERT_THAT(ret, NotNull());
255 ASSERT_THAT((uintptr_t)ret, (next + 2) * entry_size);
256 for (i = 0; i < 5; i++) {
257 allocs.push_back((uintptr_t)ret + i * entry_size);
258 }
259
260 /* Allocate a whole chunk. */
261 ret = mpool_alloc_contiguous(&p, entries_per_chunk, 1);
262 ASSERT_THAT(ret, NotNull());
263 for (i = 0; i < entries_per_chunk; i++) {
264 allocs.push_back((uintptr_t)ret + i * entry_size);
265 }
266
267 /* Allocate 2 entries that are already aligned. */
268 ret = mpool_alloc_contiguous(&p, 2, 1);
269 ASSERT_THAT(ret, NotNull());
270 allocs.push_back((uintptr_t)ret);
271 allocs.push_back((uintptr_t)ret + entry_size);
272
273 /* Allocate from p until we run out of memory. */
274 while ((ret = mpool_alloc(&p))) {
275 allocs.push_back((uintptr_t)ret);
276 }
277
278 /* Check that returned entries are within chunks that were added. */
279 ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
280 true);
281 }
282
TEST(mpool,allocation_with_fallback)283 TEST(mpool, allocation_with_fallback)
284 {
285 struct mpool fallback;
286 struct mpool p;
287 constexpr size_t entry_size = 16;
288 constexpr size_t entries_per_chunk = 10;
289 constexpr size_t chunk_count = 10;
290 std::vector<std::unique_ptr<char[]>> chunks;
291 std::vector<uintptr_t> allocs;
292 void* ret;
293
294 mpool_init(&fallback, entry_size);
295 mpool_init_with_fallback(&p, &fallback);
296
297 /* Allocate from an empty pool. */
298 EXPECT_THAT(mpool_alloc(&p), IsNull());
299
300 /* Allocate a number of chunks and add them to the fallback pool. */
301 add_chunks(chunks, &fallback, chunk_count,
302 entries_per_chunk * entry_size);
303
304 /* Allocate from the pool until we run out of memory. */
305 while ((ret = mpool_alloc(&p))) {
306 allocs.push_back((uintptr_t)ret);
307 }
308
309 /* Check that returned entries are within chunks that were added. */
310 ASSERT_THAT(check_allocs(chunks, allocs, entries_per_chunk, entry_size),
311 true);
312 }
313
TEST(mpool,free_with_fallback)314 TEST(mpool, free_with_fallback)
315 {
316 struct mpool fallback;
317 struct mpool p;
318 constexpr size_t entry_size = 16;
319 constexpr size_t entries_per_chunk = 1;
320 constexpr size_t chunk_count = 1;
321 std::vector<std::unique_ptr<char[]>> chunks;
322 std::vector<uintptr_t> allocs;
323 void* ret;
324
325 mpool_init(&fallback, entry_size);
326 mpool_init_with_fallback(&p, &fallback);
327
328 /* Allocate a number of chunks and add them to the fallback pool. */
329 add_chunks(chunks, &fallback, chunk_count,
330 entries_per_chunk * entry_size);
331
332 /* Allocate, making use of the fallback and free again. */
333 ret = mpool_alloc(&p);
334 mpool_free(&p, ret);
335
336 /* The entry is not available in the fallback. */
337 EXPECT_THAT(mpool_alloc(&fallback), IsNull());
338
339 /* The entry will be allocated by the local pool. */
340 EXPECT_THAT(mpool_alloc(&p), Eq(ret));
341
342 /* Return the memory to the local pool and then to the fallback. */
343 mpool_free(&p, ret);
344 mpool_fini(&p);
345
346 /* The fallback can now allocate the entry. */
347 EXPECT_THAT(mpool_alloc(&fallback), Eq(ret));
348 }
349
350 } /* namespace */
351