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 12static 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 25static 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 36static 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 59static 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 77static 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 82typedef 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 89static 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 153static const ralloc_region_t ALLOC_SPECIFIC_REGIONS[] = { 154 { .base = ALLOC_SPECIFIC_REGION_BASE, .size = ALLOC_SPECIFIC_REGION_SIZE }, 155}; 156 157typedef struct { 158 ralloc_region_t req; 159 zx_status_t res; 160} alloc_specific_alloc_test_t; 161 162static 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 199typedef 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 206static 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 279typedef 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 290static 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 434typedef 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