1 // Copyright 2016 The Fuchsia Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include <region-alloc/region-alloc.h>
6 #include <stdio.h>
7 #include <unittest/unittest.h>
8
9 #include "common.h"
10
ralloc_pools_c_api_test(void)11 static bool ralloc_pools_c_api_test(void) {
12 BEGIN_TEST;
13
14 // Make a pool for the bookkeeping. Do not allow it to be very large.
15 // Require that this succeeds, we will not be able to run the tests without
16 // it.
17 ralloc_pool_t* pool;
18 ASSERT_EQ(ZX_OK, ralloc_create_pool(REGION_POOL_MAX_SIZE, &pool), "");
19 ASSERT_NONNULL(pool, "");
20
21 // Create an allocator.
22 ralloc_allocator_t* alloc;
23 ASSERT_EQ(ZX_OK, ralloc_create_allocator(&alloc), "");
24 ASSERT_NONNULL(alloc, "");
25
26 {
27 // Make sure that it refuses to perform any operations because it has no
28 // RegionPool assigned to it yet.
29 const ralloc_region_t tmp = { .base = 0u, .size = 1u };
30 const ralloc_region_t* out;
31
32 EXPECT_EQ(ZX_ERR_BAD_STATE, ralloc_add_region(alloc, &tmp, false), "");
33 EXPECT_EQ(ZX_ERR_BAD_STATE, ralloc_get_sized_region_ex(alloc, 1u, 1u, &out), "");
34 EXPECT_EQ(ZX_ERR_BAD_STATE, ralloc_get_specific_region_ex(alloc, &tmp, &out), "");
35 EXPECT_NULL(ralloc_get_sized_region(alloc, 1u, 1u), "");
36 EXPECT_NULL(ralloc_get_specific_region(alloc, &tmp), "");
37 }
38
39 // Assign our pool to our allocator, but hold onto the pool for now.
40 EXPECT_EQ(ZX_OK, ralloc_set_region_pool(alloc, pool), "");
41
42 // Release our pool reference. The allocator should be holding onto its own
43 // reference at this point.
44 ralloc_release_pool(pool);
45 pool = NULL;
46
47 // Add some regions to our allocator.
48 for (size_t i = 0; i < countof(GOOD_REGIONS); ++i)
49 EXPECT_EQ(ZX_OK, ralloc_add_region(alloc, &GOOD_REGIONS[i], false), "");
50
51 // Make a new pool and try to assign it to the allocator. This should fail
52 // because the allocator is currently using resources from its currently
53 // assigned pool.
54 ASSERT_EQ(ZX_OK, ralloc_create_pool(REGION_POOL_MAX_SIZE, &pool), "");
55 ASSERT_NONNULL(pool, "");
56 EXPECT_EQ(ZX_ERR_BAD_STATE, ralloc_set_region_pool(alloc, pool), "");
57
58 // Add a bunch of adjacent regions to our pool. Try to add so many
59 // that we would normally run out of bookkeeping space. We should not
60 // actually run out, however, because the regions should get merged as they
61 // get added.
62 {
63 ralloc_region_t tmp = { .base = GOOD_MERGE_REGION_BASE,
64 .size = GOOD_MERGE_REGION_SIZE };
65 for (size_t i = 0; i < OOM_RANGE_LIMIT; ++i) {
66 ASSERT_EQ(ZX_OK, ralloc_add_region(alloc, &tmp, false), "");
67 tmp.base += tmp.size;
68 }
69 }
70
71 // Attempt (and fail) to add some bad regions (regions which overlap,
72 // regions which wrap the address space)
73 for (size_t i = 0; i < countof(BAD_REGIONS); ++i)
74 EXPECT_EQ(ZX_ERR_INVALID_ARGS, ralloc_add_region(alloc, &BAD_REGIONS[i], false), "");
75
76 // Force the region bookkeeping pool to run out of memory by adding more and
77 // more regions until we eventuall run out of room. Make sure that the
78 // regions are not adjacent, or the internal bookkeeping will just merge
79 // them.
80 {
81 size_t i;
82 ralloc_region_t tmp = { .base = BAD_MERGE_REGION_BASE,
83 .size = BAD_MERGE_REGION_SIZE };
84 for (i = 0; i < OOM_RANGE_LIMIT; ++i) {
85 zx_status_t res;
86
87 res = ralloc_add_region(alloc, &tmp, false);
88 if (res != ZX_OK) {
89 EXPECT_EQ(ZX_ERR_NO_MEMORY, res, "");
90 break;
91 }
92
93 tmp.base += tmp.size + 1;
94 }
95
96 EXPECT_LT(i, OOM_RANGE_LIMIT, "");
97 }
98
99 // Reset allocator. All of the existing available regions we had previously
100 // added will be returned to the pool.
101 ralloc_reset_allocator(alloc);
102
103 // Now assign the second pool to the allocator. Now that the allocator is
104 // no longer using any resources, this should succeed.
105 EXPECT_EQ(ZX_OK, ralloc_set_region_pool(alloc, pool), "");
106
107 // Release our pool reference.
108 ralloc_release_pool(pool);
109
110 // Destroy our allocator.
111 ralloc_destroy_allocator(alloc);
112
113 END_TEST;
114 }
115
ralloc_by_size_c_api_test(void)116 static bool ralloc_by_size_c_api_test(void) {
117 BEGIN_TEST;
118
119 // Make a pool and attach it to an allocator. Then add the test regions to it.
120 ralloc_allocator_t* alloc = NULL;
121 {
122 ralloc_pool_t* pool;
123 ASSERT_EQ(ZX_OK, ralloc_create_pool(REGION_POOL_MAX_SIZE, &pool), "");
124 ASSERT_NONNULL(pool, "");
125
126 // Create an allocator and add our region pool to it.
127 ASSERT_EQ(ZX_OK, ralloc_create_allocator(&alloc), "");
128 ASSERT_NONNULL(alloc, "");
129 ASSERT_EQ(ZX_OK, ralloc_set_region_pool(alloc, pool), "");
130
131 // Release our pool reference. The allocator should be holding onto its own
132 // reference at this point.
133 ralloc_release_pool(pool);
134 }
135
136 for (size_t i = 0; i < countof(ALLOC_BY_SIZE_REGIONS); ++i)
137 EXPECT_EQ(ZX_OK, ralloc_add_region(alloc, &ALLOC_BY_SIZE_REGIONS[i], false), "");
138
139 // Run the alloc by size tests. Hold onto the regions it allocates so they
140 // can be cleaned up properly when the test finishes.
141 const ralloc_region_t* regions[countof(ALLOC_BY_SIZE_TESTS)];
142 memset(regions, 0, sizeof(regions));
143
144 for (size_t i = 0; i < countof(ALLOC_BY_SIZE_TESTS); ++i) {
145 const alloc_by_size_alloc_test_t* TEST = ALLOC_BY_SIZE_TESTS + i;
146 zx_status_t res = ralloc_get_sized_region_ex(alloc,
147 TEST->size,
148 TEST->align,
149 regions + i);
150
151 // Make sure we get the test result we were expecting.
152 EXPECT_EQ(TEST->res, res, "");
153
154 // If the allocation claimed to succeed, we should have gotten
155 // back a non-null region. Otherwise, we should have gotten a
156 // null region back.
157 if (res == ZX_OK) {
158 ASSERT_NONNULL(regions[i], "");
159 } else {
160 EXPECT_NULL(regions[i], "");
161 }
162
163 // If the allocation succeeded, and we expected it to succeed,
164 // the allocation should have come from the test region we
165 // expect and be aligned in the way we asked.
166 if ((res == ZX_OK) && (TEST->res == ZX_OK)) {
167 ASSERT_LT(TEST->region, countof(ALLOC_BY_SIZE_TESTS), "");
168 EXPECT_TRUE(region_contains_region(ALLOC_BY_SIZE_REGIONS + TEST->region,
169 regions[i]), "");
170 EXPECT_EQ(0u, regions[i]->base & (TEST->align - 1), "");
171 }
172 }
173
174 // Put the regions we have allocated back in the allocator.
175 for (size_t i = 0; i < countof(regions); ++i)
176 if (regions[i])
177 ralloc_put_region(regions[i]);
178
179 // Destroy our allocator.
180 ralloc_destroy_allocator(alloc);
181
182 END_TEST;
183 }
184
185
ralloc_specific_c_api_test(void)186 static bool ralloc_specific_c_api_test(void) {
187 BEGIN_TEST;
188
189 // Make a pool and attach it to an allocator. Then add the test regions to it.
190 ralloc_allocator_t* alloc = NULL;
191 {
192 ralloc_pool_t* pool;
193 ASSERT_EQ(ZX_OK, ralloc_create_pool(REGION_POOL_MAX_SIZE, &pool), "");
194 ASSERT_NONNULL(pool, "");
195
196 // Create an allocator and add our region pool to it.
197 ASSERT_EQ(ZX_OK, ralloc_create_allocator(&alloc), "");
198 ASSERT_NONNULL(alloc, "");
199 ASSERT_EQ(ZX_OK, ralloc_set_region_pool(alloc, pool), "");
200
201 // Release our pool reference. The allocator should be holding onto its own
202 // reference at this point.
203 ralloc_release_pool(pool);
204 }
205
206 for (size_t i = 0; i < countof(ALLOC_SPECIFIC_REGIONS); ++i)
207 EXPECT_EQ(ZX_OK, ralloc_add_region(alloc, &ALLOC_SPECIFIC_REGIONS[i], false), "");
208
209 // Run the alloc by size tests. Hold onto the regions it allocates so they
210 // can be cleaned up properly when the test finishes.
211 const ralloc_region_t* regions[countof(ALLOC_SPECIFIC_TESTS)];
212 memset(regions, 0, sizeof(regions));
213
214 for (size_t i = 0; i < countof(ALLOC_SPECIFIC_TESTS); ++i) {
215 const alloc_specific_alloc_test_t* TEST = ALLOC_SPECIFIC_TESTS + i;
216 zx_status_t res = ralloc_get_specific_region_ex(alloc, &TEST->req, regions + i);
217
218 // Make sure we get the test result we were expecting.
219 EXPECT_EQ(TEST->res, res, "");
220
221 // If the allocation claimed to succeed, we should have gotten back a
222 // non-null region which exactly matches our requested region.
223 if (res == ZX_OK) {
224 ASSERT_NONNULL(regions[i], "");
225 EXPECT_EQ(TEST->req.base, regions[i]->base, "");
226 EXPECT_EQ(TEST->req.size, regions[i]->size, "");
227 } else {
228 EXPECT_NULL(regions[i], "");
229 }
230 }
231
232 // Put the regions we have allocated back in the allocator.
233 for (size_t i = 0; i < countof(regions); ++i)
234 if (regions[i])
235 ralloc_put_region(regions[i]);
236
237 // Destroy our allocator.
238 ralloc_destroy_allocator(alloc);
239
240 END_TEST;
241 }
242
ralloc_add_overlap_c_api_test(void)243 static bool ralloc_add_overlap_c_api_test(void) {
244 BEGIN_TEST;
245
246 // Make a pool and attach it to an allocator.
247 ralloc_allocator_t* alloc = NULL;
248 {
249 ralloc_pool_t* pool;
250 ASSERT_EQ(ZX_OK, ralloc_create_pool(REGION_POOL_MAX_SIZE, &pool), "");
251 ASSERT_NONNULL(pool, "");
252
253 // Create an allocator and add our region pool to it.
254 ASSERT_EQ(ZX_OK, ralloc_create_allocator(&alloc), "");
255 ASSERT_NONNULL(alloc, "");
256 ASSERT_EQ(ZX_OK, ralloc_set_region_pool(alloc, pool), "");
257
258 // Release our pool reference. The allocator should be holding onto its own
259 // reference at this point.
260 ralloc_release_pool(pool);
261 }
262
263 // Add each of the regions specified by the test and check the expected results.
264 for (size_t i = 0; i < countof(ADD_OVERLAP_TESTS); ++i) {
265 const alloc_add_overlap_test_t* TEST = ADD_OVERLAP_TESTS + i;
266
267 zx_status_t res = ralloc_add_region(alloc, &TEST->reg, TEST->ovl);
268
269 EXPECT_EQ(TEST->res, res, "");
270 EXPECT_EQ(TEST->cnt, ralloc_get_available_region_count(alloc), "");
271 }
272
273 // Destroy our allocator.
274 ralloc_destroy_allocator(alloc);
275
276 END_TEST;
277 }
278
ralloc_subtract_c_api_test(void)279 static bool ralloc_subtract_c_api_test(void) {
280 BEGIN_TEST;
281
282 // Make a pool and attach it to an allocator.
283 ralloc_allocator_t* alloc = NULL;
284 {
285 ralloc_pool_t* pool;
286 ASSERT_EQ(ZX_OK, ralloc_create_pool(REGION_POOL_MAX_SIZE, &pool), "");
287 ASSERT_NONNULL(pool, "");
288
289 // Create an allocator and add our region pool to it.
290 ASSERT_EQ(ZX_OK, ralloc_create_allocator(&alloc), "");
291 ASSERT_NONNULL(alloc, "");
292 ASSERT_EQ(ZX_OK, ralloc_set_region_pool(alloc, pool), "");
293
294 // Release our pool reference. The allocator should be holding onto its own
295 // reference at this point.
296 ralloc_release_pool(pool);
297 }
298
299 // Run the test sequence, adding and subtracting regions and verifying the results.
300 for (size_t i = 0; i < countof(SUBTRACT_TESTS); ++i) {
301 const alloc_subtract_test_t* TEST = SUBTRACT_TESTS + i;
302
303 zx_status_t res;
304 if (TEST->add)
305 res = ralloc_add_region(alloc, &TEST->reg, false);
306 else
307 res = ralloc_sub_region(alloc, &TEST->reg, TEST->incomplete);
308
309 EXPECT_EQ(TEST->res ? ZX_OK : ZX_ERR_INVALID_ARGS, res, "");
310 EXPECT_EQ(TEST->cnt, ralloc_get_available_region_count(alloc), "");
311 }
312
313 // Destroy our allocator.
314 ralloc_destroy_allocator(alloc);
315
316 END_TEST;
317 }
318
ralloc_walk_cb(const ralloc_region_t * r,void * ctx)319 static bool ralloc_walk_cb(const ralloc_region_t* r, void* ctx) {
320 ralloc_walk_test_ctx_t* ctx_ = (ralloc_walk_test_ctx_t*)ctx;
321 ASSERT_EQ(r->base, ctx_->regions[ctx_->i].base, "");
322 ASSERT_EQ(r->size, ctx_->regions[ctx_->i].size, "");
323 ctx_->i++;
324
325 // attempt to exit early if end is set to a value >= 0
326 return (ctx_->end == -1) ? true : (ctx_->i != ctx_->end);
327 }
328
ralloc_alloc_walk_c_api_test(void)329 static bool ralloc_alloc_walk_c_api_test(void) {
330 BEGIN_TEST;
331
332 const ralloc_region_t test_regions[] = {
333 { .base = 0x00000000, .size = 1 << 20 },
334 { .base = 0x10000000, .size = 1 << 20 },
335 { .base = 0x20000000, .size = 1 << 20 },
336 { .base = 0x30000000, .size = 1 << 20 },
337 { .base = 0x40000000, .size = 1 << 20 },
338 { .base = 0x50000000, .size = 1 << 20 },
339 { .base = 0x60000000, .size = 1 << 20 },
340 { .base = 0x70000000, .size = 1 << 20 },
341 { .base = 0x80000000, .size = 1 << 20 },
342 { .base = 0x90000000, .size = 1 << 20 },
343 };
344 const size_t r_cnt = countof(test_regions);
345
346 // Create the pool for our allocator
347 ralloc_pool_t* pool;
348 ASSERT_EQ(ZX_OK, ralloc_create_pool(REGION_POOL_MAX_SIZE, &pool), "");
349 ASSERT_NONNULL(pool, "");
350
351 // Create an allocator and add our region pool to it.
352 ralloc_allocator_t* alloc;
353 ASSERT_EQ(ZX_OK, ralloc_create_allocator(&alloc), "");
354 ASSERT_NONNULL(alloc, "");
355 ASSERT_EQ(ZX_OK, ralloc_set_region_pool(alloc, pool), "");
356 ralloc_region_t full_region = { .base = 0, .size = UINT64_MAX };
357 ASSERT_EQ(ZX_OK, ralloc_add_region(alloc, &full_region, false), "");
358
359 // Pull each region defined above out of the allocator and stash their UPtrs
360 // for the time being. Then the lambda can walk the allocated regions and
361 // verify that they are in-order and match the expected values.
362 const ralloc_region_t* tmp_regions[r_cnt];
363 for (unsigned i = 0; i < r_cnt; i++) {
364 tmp_regions[i] = ralloc_get_specific_region(alloc, &test_regions[i]);
365 }
366
367 ralloc_walk_test_ctx_t ctx = { 0, -1, test_regions };
368 ralloc_walk_allocated_regions(alloc, ralloc_walk_cb, (void*)&ctx);
369 EXPECT_EQ(r_cnt, (size_t)ctx.i, "");
370
371 // Test that exiting early works, no matter where we are in the region list.
372 // Every time the function is called we increment the counter and then at
373 // the end ensure we've only been called as many times as expected, within
374 // the bounds of [1, r_cnt].
375 for (size_t cnt = 0; cnt < 1024; cnt++) {
376 ctx.i = 0;
377 ctx.end = (int)(rand() % r_cnt) + 1;
378 ralloc_walk_allocated_regions(alloc, ralloc_walk_cb, (void*)&ctx);
379 ASSERT_EQ(ctx.i, ctx.end, "");
380 }
381
382 // Clean up the allocated regions, pool, then allocator
383 for (size_t i = 0; i < r_cnt; i++) {
384 ralloc_put_region(tmp_regions[i]);
385 }
386 ralloc_release_pool(pool);
387 ralloc_destroy_allocator(alloc);
388
389 END_TEST;
390 }
391
392 BEGIN_TEST_CASE(ralloc_c_api_tests)
393 RUN_NAMED_TEST("Region Pools (C-API)", ralloc_pools_c_api_test)
394 RUN_NAMED_TEST("Alloc by size (C-API)", ralloc_by_size_c_api_test)
395 RUN_NAMED_TEST("Alloc specific (C-API)", ralloc_specific_c_api_test)
396 RUN_NAMED_TEST("Subtract (C-API)", ralloc_subtract_c_api_test)
397 RUN_NAMED_TEST("Allocated Walk (C-API)", ralloc_alloc_walk_c_api_test)
398 END_TEST_CASE(ralloc_c_api_tests)
399