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 #pragma once
6
7 #include <region-alloc/region-alloc.h>
8 #include <stddef.h>
9
10 // Constants and common tables used by both the C and C++ API tests.
11 #ifdef __cplusplus
12 static constexpr size_t REGION_POOL_MAX_SIZE = (RegionAllocator::RegionPool::SLAB_SIZE << 1);
13 #else
14 #define REGION_POOL_MAX_SIZE (REGION_POOL_SLAB_SIZE << 1)
15 #endif
16
17 #define OOM_RANGE_LIMIT (1000u)
18
19 #define GOOD_MERGE_REGION_BASE ((uint64_t)0x3000000000000000)
20 #define GOOD_MERGE_REGION_SIZE (16u << 10)
21
22 #define BAD_MERGE_REGION_BASE ((uint64_t)0x4000000000000000)
23 #define BAD_MERGE_REGION_SIZE (16u << 10)
24
25 static const ralloc_region_t GOOD_REGIONS[] = {
26 { .base = 0x10000000, .size = 256 << 10 },
27 { .base = 0x20000000 - 1 * (256 << 10), .size = 256 << 10 },
28 { .base = 0x20000000 + 3 * (256 << 10), .size = 256 << 10 },
29 { .base = 0x20000000, .size = 256 << 10 }, // Merges with before (ndx 1)
30 { .base = 0x20000000 + 2 * (256 << 10), .size = 256 << 10 }, // Merges with after (ndx 2)
31 { .base = 0x20000000 + 1 * (256 << 10), .size = 256 << 10 }, // Merges with before/after
32 { .base = 0x1000000000000000, .size = 256 << 10 },
33 { .base = 0x2000000000000000, .size = 256 << 10 },
34 };
35
36 static const ralloc_region_t BAD_REGIONS[] = {
37 { .base = 0x10000000 - (256 << 10) + 1, .size = 256 << 10 },
38 { .base = 0x10000000 - 1, .size = 256 << 10 },
39 { .base = 0x10000000 + (256 << 10) - 1, .size = 256 << 10 },
40 { .base = 0x10000000 - 1, .size = 512 << 10 },
41 { .base = 0x10000000 + 1, .size = 128 << 10 },
42
43 { .base = 0x1000000000000000 - (256 << 10) + 1, .size = 256 << 10 },
44 { .base = 0x1000000000000000 - 1, .size = 256 << 10 },
45 { .base = 0x1000000000000000 + (256 << 10) - 1, .size = 256 << 10 },
46 { .base = 0x1000000000000000 - 1, .size = 512 << 10 },
47 { .base = 0x1000000000000000 + 1, .size = 128 << 10 },
48
49 { .base = 0x2000000000000000 - (256 << 10) + 1, .size = 256 << 10 },
50 { .base = 0x2000000000000000 - 1, .size = 256 << 10 },
51 { .base = 0x2000000000000000 + (256 << 10) - 1, .size = 256 << 10 },
52 { .base = 0x2000000000000000 - 1, .size = 512 << 10 },
53 { .base = 0x2000000000000000 + 1, .size = 128 << 10 },
54
55 { .base = 0xFFFFFFFFFFFFFFFF, .size = 0x1 },
56 { .base = 0xFFFFFFFF00000000, .size = 0x100000000 },
57 };
58
region_contains_region(const ralloc_region_t * contained_by,const ralloc_region_t * contained)59 static inline bool region_contains_region(
60 const ralloc_region_t* contained_by,
61 const ralloc_region_t* contained) {
62 uint64_t contained_end = contained->base + contained->size - 1;
63 uint64_t contained_by_end = contained_by->base + contained_by->size - 1;
64
65 return ((contained->base >= contained_by->base) &&
66 (contained_end >= contained_by->base) &&
67 (contained->base <= contained_by_end) &&
68 (contained_end <= contained_by_end));
69 }
70
71 #define ALLOC_BY_SIZE_SMALL_REGION_BASE (0x0) // All alignments
72 #define ALLOC_BY_SIZE_SMALL_REGION_SIZE (4 << 10) // 4KB slice
73
74 #define ALLOC_BY_SIZE_LARGE_REGION_BASE (0x100000) // 1MB alignment
75 #define ALLOC_BY_SIZE_LARGE_REGION_SIZE (1 << 20) // 1MB slice
76
77 static const ralloc_region_t ALLOC_BY_SIZE_REGIONS[] = {
78 { .base = ALLOC_BY_SIZE_SMALL_REGION_BASE, .size = ALLOC_BY_SIZE_SMALL_REGION_SIZE },
79 { .base = ALLOC_BY_SIZE_LARGE_REGION_BASE, .size = ALLOC_BY_SIZE_LARGE_REGION_SIZE },
80 };
81
82 typedef struct {
83 uint64_t size;
84 uint64_t align;
85 zx_status_t res;
86 size_t region;
87 } alloc_by_size_alloc_test_t;
88
89 static const alloc_by_size_alloc_test_t ALLOC_BY_SIZE_TESTS[] = {
90 // Invalid parameter failures
91 { .size = 0x00000000, .align = 0x00000001, .res = ZX_ERR_INVALID_ARGS, 0 }, // bad size
92 { .size = 0x00000001, .align = 0x00000000, .res = ZX_ERR_INVALID_ARGS, 0 }, // bad align
93 { .size = 0x00000001, .align = 0x00001001, .res = ZX_ERR_INVALID_ARGS, 0 }, // bad align
94
95 // Initially unsatisfiable
96 { .size = 0x10000000, .align = 0x00000001, .res = ZX_ERR_NOT_FOUND, 0 }, // too large
97 { .size = 0x00005000, .align = 0x10000000, .res = ZX_ERR_NOT_FOUND, 0 }, // Cannot align
98
99 // Should succeed, all pulled from first chunk
100 { .size = (1 << 0), .align = (1 << 1), .res = ZX_OK, .region = 0 },
101 { .size = (1 << 1), .align = (1 << 2), .res = ZX_OK, .region = 0 },
102 { .size = (1 << 2), .align = (1 << 3), .res = ZX_OK, .region = 0 },
103 { .size = (1 << 3), .align = (1 << 4), .res = ZX_OK, .region = 0 },
104 { .size = (1 << 4), .align = (1 << 5), .res = ZX_OK, .region = 0 },
105 { .size = (1 << 5), .align = (1 << 6), .res = ZX_OK, .region = 0 },
106 { .size = (1 << 6), .align = (1 << 7), .res = ZX_OK, .region = 0 },
107 { .size = (1 << 7), .align = (1 << 8), .res = ZX_OK, .region = 0 },
108 { .size = (1 << 8), .align = (1 << 9), .res = ZX_OK, .region = 0 },
109 { .size = (1 << 9), .align = (1 << 10), .res = ZX_OK, .region = 0 },
110 { .size = (1 << 10), .align = (1 << 11), .res = ZX_OK, .region = 0 },
111
112 // Perform some allocations which are large enough that they can only be
113 // satisfied with results from region 1. Exercise the various range
114 // splitting cases.
115 { .size = (4 << 10), .align = (4 << 10), .res = ZX_OK, .region = 1 }, // front of region 1
116 { .size = (4 << 10), .align = (4 << 11), .res = ZX_OK, .region = 1 }, // middle of region 1
117 { .size = 0xfc000, .align = (4 << 12), .res = ZX_OK, .region = 1 }, // back of region 1
118
119 // Repeat the small allocation pass again. Because of the alignment
120 // restrictions, the first pass should have fragmented the first region.
121 // This pass should soak up those fragments.
122 { .size = (3), .align = (1 << 0), .res = ZX_OK, .region = 0 },
123 { .size = (1 << 1), .align = (1 << 1), .res = ZX_OK, .region = 0 },
124 { .size = (1 << 2), .align = (1 << 2), .res = ZX_OK, .region = 0 },
125 { .size = (1 << 3), .align = (1 << 3), .res = ZX_OK, .region = 0 },
126 { .size = (1 << 4), .align = (1 << 4), .res = ZX_OK, .region = 0 },
127 { .size = (1 << 5), .align = (1 << 5), .res = ZX_OK, .region = 0 },
128 { .size = (1 << 6), .align = (1 << 6), .res = ZX_OK, .region = 0 },
129 { .size = (1 << 7), .align = (1 << 7), .res = ZX_OK, .region = 0 },
130 { .size = (1 << 8), .align = (1 << 8), .res = ZX_OK, .region = 0 },
131 { .size = (1 << 9), .align = (1 << 9), .res = ZX_OK, .region = 0 },
132 { .size = (1 << 10), .align = (1 << 10), .res = ZX_OK, .region = 0 },
133
134 // Region 0 should be exhausted at this point. Asking for even one more
135 // byte should give us an allocation from from region 1.
136 { .size = 1, .align = 1, .res = ZX_OK, .region = 1 },
137
138 // All that should be left in the pool is a 4k region and a 4k - 1 byte
139 // region. Ask for two 4k regions with arbitrary alignment. The first
140 // request should succeed while the second request should fail.
141 { .size = (4 << 10), .align = 1, .res = ZX_OK, .region = 1 },
142 { .size = (4 << 10), .align = 1, .res = ZX_ERR_NOT_FOUND, 0 },
143
144 // Finally, soak up the last of the space with a 0xFFF byte allocation.
145 // Afterwards, we should be unable to allocate even a single byte
146 { .size = 0xFFF, .align = 1, .res = ZX_OK, .region = 1 },
147 { .size = 1, .align = 1, .res = ZX_ERR_NOT_FOUND, 0 },
148 };
149
150 #define ALLOC_SPECIFIC_REGION_BASE (0x1000)
151 #define ALLOC_SPECIFIC_REGION_SIZE (4 << 10)
152
153 static const ralloc_region_t ALLOC_SPECIFIC_REGIONS[] = {
154 { .base = ALLOC_SPECIFIC_REGION_BASE, .size = ALLOC_SPECIFIC_REGION_SIZE },
155 };
156
157 typedef struct {
158 ralloc_region_t req;
159 zx_status_t res;
160 } alloc_specific_alloc_test_t;
161
162 static const alloc_specific_alloc_test_t ALLOC_SPECIFIC_TESTS[] = {
163 // Invalid parameter failures
164 { .req = { .base = 0x0000000000000000, .size = 0x00 }, .res = ZX_ERR_INVALID_ARGS }, // 0 size
165 { .req = { .base = 0xffffffffffffffff, .size = 0x01 }, .res = ZX_ERR_INVALID_ARGS }, // wraps
166 { .req = { .base = 0xfffffffffffffff0, .size = 0x20 }, .res = ZX_ERR_INVALID_ARGS }, // wraps
167
168 // Bad requests
169 { .req = { .base = 0x0800, .size = 0x1 }, .res = ZX_ERR_NOT_FOUND }, // total miss
170 { .req = { .base = 0x0fff, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND }, // clips the front
171 { .req = { .base = 0x1f01, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND }, // clips the back
172 { .req = { .base = 0x2000, .size = 0x1 }, .res = ZX_ERR_NOT_FOUND }, // total miss
173
174 // Good requests
175 { .req = { .base = 0x1000, .size = 0x100 }, .res = ZX_OK }, // front of range.
176 { .req = { .base = 0x1f00, .size = 0x100 }, .res = ZX_OK }, // back of range.
177 { .req = { .base = 0x1700, .size = 0x200 }, .res = ZX_OK }, // middle of range.
178
179 // Requests which would have been good initially, but are bad now.
180 { .req = { .base = 0x1000, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND },
181 { .req = { .base = 0x1080, .size = 0x80 }, .res = ZX_ERR_NOT_FOUND },
182 { .req = { .base = 0x10ff, .size = 0x1 }, .res = ZX_ERR_NOT_FOUND },
183 { .req = { .base = 0x10ff, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND },
184
185 { .req = { .base = 0x1f00, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND },
186 { .req = { .base = 0x1e01, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND },
187 { .req = { .base = 0x1e81, .size = 0x80 }, .res = ZX_ERR_NOT_FOUND },
188 { .req = { .base = 0x1eff, .size = 0x2 }, .res = ZX_ERR_NOT_FOUND },
189
190 { .req = { .base = 0x1800, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND },
191 { .req = { .base = 0x1880, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND },
192 { .req = { .base = 0x1780, .size = 0x100 }, .res = ZX_ERR_NOT_FOUND },
193
194 // Soak up the remaining regions. There should be 2 left.
195 { .req = { .base = 0x1100, .size = 0x600 }, .res = ZX_OK },
196 { .req = { .base = 0x1900, .size = 0x600 }, .res = ZX_OK },
197 };
198
199 typedef struct {
200 ralloc_region_t reg; // Region to add
201 bool ovl; // Whether to allow overlap or not.
202 size_t cnt; // Expected available region count afterwards.
203 zx_status_t res; // Expected result.
204 } alloc_add_overlap_test_t;
205
206 static const alloc_add_overlap_test_t ADD_OVERLAP_TESTS[] = {
207 // Add a region, then try to add it again without allowing overlap. This
208 // should fail. Then add the region again, this time allowing overlap.
209 // This should succeed.
210 { .reg = { .base = 0x10000, .size = 0x1000 }, .ovl = false, .cnt = 1, .res = ZX_OK },
211 { .reg = { .base = 0x10000, .size = 0x1000 }, .ovl = false, .cnt = 1, .res = ZX_ERR_INVALID_ARGS },
212 { .reg = { .base = 0x10000, .size = 0x1000 }, .ovl = true, .cnt = 1, .res = ZX_OK },
213
214 // Current: [0x10000, 0x11000)
215 // Add a region to the front which fits perfectly with the existing region.
216 // This should succeed, even when we do not allow overlapping.
217 { .reg = { .base = 0xF800, .size = 0x800 }, .ovl = false, .cnt = 1, .res = ZX_OK },
218 { .reg = { .base = 0xF800, .size = 0x800 }, .ovl = true, .cnt = 1, .res = ZX_OK },
219
220 // Current: [0xF800, 0x11000)
221 // Same exercise, but this time add to the back.
222 { .reg = { .base = 0x11000, .size = 0x800 }, .ovl = false, .cnt = 1, .res = ZX_OK },
223 { .reg = { .base = 0x11000, .size = 0x800 }, .ovl = true, .cnt = 1, .res = ZX_OK },
224
225 // Current: [0xF800, 0x11800)
226 // Now attempt to add a region which overlaps the front by a single byte.
227 // This should fail unless we explicitly permit it.
228 { .reg = { .base = 0xF000, .size = 0x801 }, .ovl = false, .cnt = 1, .res = ZX_ERR_INVALID_ARGS },
229 { .reg = { .base = 0xF000, .size = 0x801 }, .ovl = true, .cnt = 1, .res = ZX_OK },
230
231 // Current: [0xF000, 0x12000)
232 // Same exercise, this time adding to the back.
233 { .reg = { .base = 0x117FF, .size = 0x801 }, .ovl = false, .cnt = 1, .res = ZX_ERR_INVALID_ARGS },
234 { .reg = { .base = 0x117FF, .size = 0x801 }, .ovl = true, .cnt = 1, .res = ZX_OK },
235
236 // Current: [0xE000, 0x13000)
237 // Add a region which completely contains the existing region.
238 { .reg = { .base = 0xE000, .size = 0x5000 }, .ovl = false, .cnt = 1, .res = ZX_ERR_INVALID_ARGS },
239 { .reg = { .base = 0xE000, .size = 0x5000 }, .ovl = true, .cnt = 1, .res = ZX_OK },
240
241 // Add some regions which are not connected to the existing region.
242 { .reg = { .base = 0x14000, .size = 0x1000 }, .ovl = false, .cnt = 2, .res = ZX_OK },
243 { .reg = { .base = 0x16000, .size = 0x1000 }, .ovl = false, .cnt = 3, .res = ZX_OK },
244 { .reg = { .base = 0x18000, .size = 0x1000 }, .ovl = false, .cnt = 4, .res = ZX_OK },
245 { .reg = { .base = 0x1A000, .size = 0x1000 }, .ovl = false, .cnt = 5, .res = ZX_OK },
246 { .reg = { .base = 0x1C000, .size = 0x1000 }, .ovl = false, .cnt = 6, .res = ZX_OK },
247
248 // Current: [0xE000, 0x13000) [0x14000, 0x15000) [0x16000, 0x17000) [0x18000, 0x19000)
249 // [0x1A000, 0x1B000) [0x1C000, 0x1D000)
250
251 // Add a region which ties two regions together.
252 { .reg = { .base = 0x12FFF, .size = 0x1002 }, .ovl = false, .cnt = 6, .res = ZX_ERR_INVALID_ARGS },
253 { .reg = { .base = 0x12FFF, .size = 0x1002 }, .ovl = true, .cnt = 5, .res = ZX_OK },
254
255 // Current: [0xE000, 0x15000) [0x16000, 0x17000) [0x18000, 0x19000) [0x1A000, 0x1B000)
256 // [0x1C000, 0x1D000)
257
258 // Add a region which completely consumes one region, and intersects the
259 // front of another.
260 { .reg = { .base = 0x15800, .size = 0x3000 }, .ovl = false, .cnt = 5, .res = ZX_ERR_INVALID_ARGS },
261 { .reg = { .base = 0x15800, .size = 0x3000 }, .ovl = true, .cnt = 4, .res = ZX_OK },
262
263 // Current: [0xE000, 0x15000) [0x15800, 0x19000) [0x1A000, 0x1B000) [0x1C000, 0x1D000)
264
265 // Same test as before, but this time from the end.
266 { .reg = { .base = 0x18800, .size = 0x3000 }, .ovl = false, .cnt = 4, .res = ZX_ERR_INVALID_ARGS },
267 { .reg = { .base = 0x18800, .size = 0x3000 }, .ovl = true, .cnt = 3, .res = ZX_OK },
268
269 // Current: [0xE000, 0x15000) [0x15800, 0x1B800) [0x1C000, 0x1D000)
270
271 // Add one more region, this one should consume and unify all regions in the
272 // set.
273 { .reg = { .base = 0xD000, .size = 0x11000 }, .ovl = false, .cnt = 3, .res = ZX_ERR_INVALID_ARGS },
274 { .reg = { .base = 0xD000, .size = 0x11000 }, .ovl = true, .cnt = 1, .res = ZX_OK },
275
276 // Current: [0xD000, 0x1E000)
277 };
278
279 typedef struct {
280 ralloc_region_t reg; // Region to add or subtract
281 bool add; // Whether to this is an add operation or not.
282 bool incomplete; // If subtracting, do we allow incomplete subtraction?
283 size_t cnt; // Expected available region count the operation.
284 bool res; // Whether we expect succes ZX_ERR_INVALID_ARGS.
285 } alloc_subtract_test_t;
286
287 // Temp macro to help make the test table pretty.
288 #define REG(_b, _s) { .base = (_b), .size = (_s) }
289
290 static const alloc_subtract_test_t SUBTRACT_TESTS[] = {
291 // Try to subtract a region while the allocator is empty. This should fail unless we allow
292 // incomplete subtraction.
293 { .reg = REG(0x1000, 0x1000), .add = false, .incomplete = false, .cnt = 0, .res = false },
294 { .reg = REG(0x1000, 0x1000), .add = false, .incomplete = true, .cnt = 0, .res = true },
295
296 // allow_incomplete == false
297 // Tests where incomplete subtraction is not allowed.
298
299 // Add a region, then subtract it out.
300 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
301 { .reg = REG(0x1000, 0x1000), .add = false, .incomplete = false, .cnt = 0, .res = true },
302
303 // Add a region, then trim the front of it. Finally, cleanup by removing
304 // the specific regions which should be left.
305 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
306 { .reg = REG(0x1000, 0x800), .add = false, .incomplete = false, .cnt = 1, .res = true },
307 { .reg = REG(0x1800, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
308
309 // Add a region, then trim the back of it. Then cleanup.
310 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
311 { .reg = REG(0x1800, 0x800), .add = false, .incomplete = false, .cnt = 1, .res = true },
312 { .reg = REG(0x1000, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
313
314 // Add a region, then punch a hole in the middle of it. then cleanup.
315 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
316 { .reg = REG(0x1600, 0x400), .add = false, .incomplete = false, .cnt = 2, .res = true },
317 { .reg = REG(0x1000, 0x600), .add = false, .incomplete = false, .cnt = 1, .res = true },
318 { .reg = REG(0x1A00, 0x600), .add = false, .incomplete = false, .cnt = 0, .res = true },
319
320 // Add a region, then fail to remove parts of it with a number of attempts
321 // which would require trimming or splitting the region. Then cleanup.
322 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
323 { .reg = REG( 0x800, 0x1000), .add = false, .incomplete = false, .cnt = 1, .res = false },
324 { .reg = REG(0x1800, 0x1000), .add = false, .incomplete = false, .cnt = 1, .res = false },
325 { .reg = REG( 0x800, 0x2000), .add = false, .incomplete = false, .cnt = 1, .res = false },
326 { .reg = REG(0x1000, 0x1000), .add = false, .incomplete = false, .cnt = 0, .res = true },
327
328 // allow_incomplete == true
329 // Tests where incomplete subtraction is allowed. Start by repeating the
330 // tests for allow_incomplete = false where success was expected. These
331 // should work too.
332
333 // Add a region, then subtract it out.
334 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
335 { .reg = REG(0x1000, 0x1000), .add = false, .incomplete = true, .cnt = 0, .res = true },
336
337 // Add a region, then trim the front of it. Finally, cleanup by removing
338 // the specific regions which should be left.
339 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
340 { .reg = REG(0x1000, 0x800), .add = false, .incomplete = true, .cnt = 1, .res = true },
341 { .reg = REG(0x1800, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
342
343 // Add a region, then trim the back of it. Then cleanup.
344 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
345 { .reg = REG(0x1800, 0x800), .add = false, .incomplete = true, .cnt = 1, .res = true },
346 { .reg = REG(0x1000, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
347
348 // Add a region, then punch a hole in the middle of it. then cleanup.
349 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
350 { .reg = REG(0x1600, 0x400), .add = false, .incomplete = true, .cnt = 2, .res = true },
351 { .reg = REG(0x1000, 0x600), .add = false, .incomplete = false, .cnt = 1, .res = true },
352 { .reg = REG(0x1A00, 0x600), .add = false, .incomplete = false, .cnt = 0, .res = true },
353
354 // Now try scenarios which only work when allow_incomplete is true.
355 // Add a region, then trim the front.
356 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
357 { .reg = REG( 0x800, 0x1000), .add = false, .incomplete = true, .cnt = 1, .res = true },
358 { .reg = REG(0x1800, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
359
360 // Add a region, then trim the back.
361 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
362 { .reg = REG(0x1800, 0x1000), .add = false, .incomplete = true, .cnt = 1, .res = true },
363 { .reg = REG(0x1000, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
364
365 // Add a region, then consume the whole thing.
366 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
367 { .reg = REG( 0x800, 0x2000), .add = false, .incomplete = true, .cnt = 0, .res = true },
368
369 // Add a bunch of separate regions, then consume them all using a subtract
370 // which lines up perfectly with the begining and the end of the regions.
371 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
372 { .reg = REG(0x3000, 0x1000), .add = true, .incomplete = false, .cnt = 2, .res = true },
373 { .reg = REG(0x5000, 0x1000), .add = true, .incomplete = false, .cnt = 3, .res = true },
374 { .reg = REG(0x7000, 0x1000), .add = true, .incomplete = false, .cnt = 4, .res = true },
375 { .reg = REG(0x9000, 0x1000), .add = true, .incomplete = false, .cnt = 5, .res = true },
376 { .reg = REG(0x1000, 0xA000), .add = false, .incomplete = true, .cnt = 0, .res = true },
377
378 // Same as before, but this time, trim past the start
379 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
380 { .reg = REG(0x3000, 0x1000), .add = true, .incomplete = false, .cnt = 2, .res = true },
381 { .reg = REG(0x5000, 0x1000), .add = true, .incomplete = false, .cnt = 3, .res = true },
382 { .reg = REG(0x7000, 0x1000), .add = true, .incomplete = false, .cnt = 4, .res = true },
383 { .reg = REG(0x9000, 0x1000), .add = true, .incomplete = false, .cnt = 5, .res = true },
384 { .reg = REG( 0x800, 0xA800), .add = false, .incomplete = true, .cnt = 0, .res = true },
385
386 // Same as before, but this time, trim past the end
387 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
388 { .reg = REG(0x3000, 0x1000), .add = true, .incomplete = false, .cnt = 2, .res = true },
389 { .reg = REG(0x5000, 0x1000), .add = true, .incomplete = false, .cnt = 3, .res = true },
390 { .reg = REG(0x7000, 0x1000), .add = true, .incomplete = false, .cnt = 4, .res = true },
391 { .reg = REG(0x9000, 0x1000), .add = true, .incomplete = false, .cnt = 5, .res = true },
392 { .reg = REG(0x1000, 0xA800), .add = false, .incomplete = true, .cnt = 0, .res = true },
393
394 // Same as before, but this time, trim past both ends
395 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
396 { .reg = REG(0x3000, 0x1000), .add = true, .incomplete = false, .cnt = 2, .res = true },
397 { .reg = REG(0x5000, 0x1000), .add = true, .incomplete = false, .cnt = 3, .res = true },
398 { .reg = REG(0x7000, 0x1000), .add = true, .incomplete = false, .cnt = 4, .res = true },
399 { .reg = REG(0x9000, 0x1000), .add = true, .incomplete = false, .cnt = 5, .res = true },
400 { .reg = REG( 0x800, 0xB000), .add = false, .incomplete = true, .cnt = 0, .res = true },
401
402 // Same as before, but this time, don't consume all of the first region.
403 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
404 { .reg = REG(0x3000, 0x1000), .add = true, .incomplete = false, .cnt = 2, .res = true },
405 { .reg = REG(0x5000, 0x1000), .add = true, .incomplete = false, .cnt = 3, .res = true },
406 { .reg = REG(0x7000, 0x1000), .add = true, .incomplete = false, .cnt = 4, .res = true },
407 { .reg = REG(0x9000, 0x1000), .add = true, .incomplete = false, .cnt = 5, .res = true },
408 { .reg = REG(0x1800, 0x9800), .add = false, .incomplete = true, .cnt = 1, .res = true },
409 { .reg = REG(0x1000, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
410
411 // Same as before, but this time, don't consume all of the last region.
412 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
413 { .reg = REG(0x3000, 0x1000), .add = true, .incomplete = false, .cnt = 2, .res = true },
414 { .reg = REG(0x5000, 0x1000), .add = true, .incomplete = false, .cnt = 3, .res = true },
415 { .reg = REG(0x7000, 0x1000), .add = true, .incomplete = false, .cnt = 4, .res = true },
416 { .reg = REG(0x9000, 0x1000), .add = true, .incomplete = false, .cnt = 5, .res = true },
417 { .reg = REG(0x1000, 0x8800), .add = false, .incomplete = true, .cnt = 1, .res = true },
418 { .reg = REG(0x9800, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
419
420 // Same as before, but this time, don't consume all of the first or last regions.
421 { .reg = REG(0x1000, 0x1000), .add = true, .incomplete = false, .cnt = 1, .res = true },
422 { .reg = REG(0x3000, 0x1000), .add = true, .incomplete = false, .cnt = 2, .res = true },
423 { .reg = REG(0x5000, 0x1000), .add = true, .incomplete = false, .cnt = 3, .res = true },
424 { .reg = REG(0x7000, 0x1000), .add = true, .incomplete = false, .cnt = 4, .res = true },
425 { .reg = REG(0x9000, 0x1000), .add = true, .incomplete = false, .cnt = 5, .res = true },
426 { .reg = REG(0x1800, 0x8000), .add = false, .incomplete = true, .cnt = 2, .res = true },
427 { .reg = REG(0x1000, 0x800), .add = false, .incomplete = false, .cnt = 1, .res = true },
428 { .reg = REG(0x9800, 0x800), .add = false, .incomplete = false, .cnt = 0, .res = true },
429 };
430
431 #undef REG
432
433 // context structure for region allocator walk tests
434 typedef struct ralloc_walk_test_ctx {
435 int i;
436 int end;
437 const ralloc_region_t* regions;
438 } ralloc_walk_test_ctx_t;
439
440