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#include <inttypes.h> 9 10#include <fbl/algorithm.h> 11 12#include "common.h" 13 14namespace { 15 16static bool ralloc_region_pools_test() { 17 BEGIN_TEST; 18 19 // Create a default constructed allocator on the stack. 20 RegionAllocator alloc; 21 22 { 23 // Make sure that it refuses to perform any operations because it has no 24 // RegionPool assigned to it yet. 25 RegionAllocator::Region::UPtr tmp; 26 EXPECT_EQ(ZX_ERR_BAD_STATE, alloc.AddRegion({ 0u, 1u })); 27 EXPECT_EQ(ZX_ERR_BAD_STATE, alloc.GetRegion(1, tmp)); 28 EXPECT_EQ(ZX_ERR_BAD_STATE, alloc.GetRegion({ 0u, 1u }, tmp)); 29 EXPECT_NULL(alloc.GetRegion(1)); 30 EXPECT_NULL(alloc.GetRegion({ 0u, 1u })); 31 } 32 33 // Make a region pool to manage bookkeeping allocations. 34 auto pool = RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE); 35 ASSERT_NONNULL(pool); 36 37 // Assign our pool to our allocator, but hold onto the pool for now. 38 ASSERT_EQ(ZX_OK, alloc.SetRegionPool(pool)); 39 EXPECT_NONNULL(pool); 40 41 // Create another allocator and transfer ownership of our region pool 42 // reference to it. Then let the allocator go out of scope. 43 { 44 RegionAllocator alloc2(fbl::move(pool)); 45 EXPECT_NULL(pool); 46 } 47 EXPECT_NULL(pool); 48 49 // Add some regions to our allocator. 50 for (size_t i = 0; i < fbl::count_of(GOOD_REGIONS); ++i) 51 EXPECT_EQ(ZX_OK, alloc.AddRegion(GOOD_REGIONS[i])); 52 53 // Make a new pool and try to assign it to the allocator. This should fail 54 // because the allocator is currently using resources from its currently 55 // assigned pool. 56 auto pool2 = RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE); 57 ASSERT_NONNULL(pool2); 58 EXPECT_EQ(ZX_ERR_BAD_STATE, alloc.SetRegionPool(pool2)); 59 60 // Add a bunch of adjacent regions to our pool. Try to add so many 61 // that we would normally run out of bookkeeping space. We should not 62 // actually run out, however, because the regions should get merged as they 63 // get added. 64 { 65 ralloc_region_t tmp = { .base = GOOD_MERGE_REGION_BASE, 66 .size = GOOD_MERGE_REGION_SIZE }; 67 for (size_t i = 0; i < OOM_RANGE_LIMIT; ++i) { 68 ASSERT_EQ(ZX_OK, alloc.AddRegion(tmp)); 69 tmp.base += tmp.size; 70 } 71 } 72 73 // Attempt (and fail) to add some bad regions (regions which overlap, 74 // regions which wrap the address space) 75 for (size_t i = 0; i < fbl::count_of(BAD_REGIONS); ++i) 76 EXPECT_EQ(ZX_ERR_INVALID_ARGS, alloc.AddRegion(BAD_REGIONS[i])); 77 78 // Force the region bookkeeping pool to run out of memory by adding more and 79 // more regions until we eventually run out of room. Make sure that the 80 // regions are not adjacent, or the internal bookkeeping will just merge 81 // them. 82 { 83 size_t i; 84 ralloc_region_t tmp = { .base = BAD_MERGE_REGION_BASE, 85 .size = BAD_MERGE_REGION_SIZE }; 86 for (i = 0; i < OOM_RANGE_LIMIT; ++i) { 87 zx_status_t res; 88 89 res = alloc.AddRegion(tmp); 90 if (res != ZX_OK) { 91 EXPECT_EQ(ZX_ERR_NO_MEMORY, res); 92 break; 93 } 94 95 tmp.base += tmp.size + 1; 96 } 97 98 EXPECT_LT(i, OOM_RANGE_LIMIT); 99 } 100 101 // Reset allocator. All of the existing available regions we had previously 102 // added will be returned to the pool. 103 alloc.Reset(); 104 105 // Now assign pool2 to the allocator. Now that it is no longer using any 106 // resources, this should succeed. 107 EXPECT_EQ(ZX_OK, alloc.SetRegionPool(fbl::move(pool2))); 108 EXPECT_NULL(pool2); 109 110 END_TEST; 111} 112 113static bool ralloc_by_size_test() { 114 BEGIN_TEST; 115 116 // Make a pool and attach it to an allocator. Then add the test regions to it. 117 RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); 118 119 for (size_t i = 0; i < fbl::count_of(ALLOC_BY_SIZE_REGIONS); ++i) 120 ASSERT_EQ(ZX_OK, alloc.AddRegion(ALLOC_BY_SIZE_REGIONS[i])); 121 122 // Run the alloc by size tests. Hold onto the regions it allocates so they 123 // don't automatically get returned to the pool. 124 RegionAllocator::Region::UPtr regions[fbl::count_of(ALLOC_BY_SIZE_TESTS)]; 125 126 for (size_t i = 0; i < fbl::count_of(ALLOC_BY_SIZE_TESTS); ++i) { 127 const alloc_by_size_alloc_test_t* TEST = ALLOC_BY_SIZE_TESTS + i; 128 zx_status_t res = alloc.GetRegion(TEST->size, TEST->align, regions[i]); 129 130 // Make sure we get the test result we were expecting. 131 EXPECT_EQ(TEST->res, res); 132 133 // If the allocation claimed to succeed, we should have gotten 134 // back a non-null region. Otherwise, we should have gotten a 135 // null region back. 136 if (res == ZX_OK) { 137 ASSERT_NONNULL(regions[i]); 138 } else { 139 EXPECT_NULL(regions[i]); 140 } 141 142 // If the allocation succeeded, and we expected it to succeed, 143 // the allocation should have come from the test region we 144 // expect and be aligned in the way we asked. 145 if ((res == ZX_OK) && (TEST->res == ZX_OK)) { 146 ASSERT_LT(TEST->region, fbl::count_of(ALLOC_BY_SIZE_TESTS)); 147 EXPECT_TRUE(region_contains_region(ALLOC_BY_SIZE_REGIONS + TEST->region, 148 regions[i].get())); 149 EXPECT_EQ(0u, regions[i]->base & (TEST->align - 1)); 150 } 151 152 } 153 154 // No need for any explicit cleanup. Our region references will go out of 155 // scope first and be returned to the allocator. Then the allocator will 156 // clean up, and release its bookkeeping pool reference in the process. 157 158 END_TEST; 159} 160 161static bool ralloc_specific_test() { 162 BEGIN_TEST; 163 164 // Make a pool and attach it to an allocator. Then add the test regions to it. 165 RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); 166 167 for (size_t i = 0; i < fbl::count_of(ALLOC_SPECIFIC_REGIONS); ++i) 168 ASSERT_EQ(ZX_OK, alloc.AddRegion(ALLOC_SPECIFIC_REGIONS[i])); 169 170 // Run the alloc specific tests. Hold onto the regions it allocates so they 171 // don't automatically get returned to the pool. 172 RegionAllocator::Region::UPtr regions[fbl::count_of(ALLOC_SPECIFIC_TESTS)]; 173 174 for (size_t i = 0; i < fbl::count_of(ALLOC_SPECIFIC_TESTS); ++i) { 175 const alloc_specific_alloc_test_t* TEST = ALLOC_SPECIFIC_TESTS + i; 176 zx_status_t res = alloc.GetRegion(TEST->req, regions[i]); 177 178 // Make sure we get the test result we were expecting. 179 EXPECT_EQ(TEST->res, res); 180 181 // If the allocation claimed to succeed, we should have gotten back a 182 // non-null region which exactly matches our requested region. 183 if (res == ZX_OK) { 184 ASSERT_NONNULL(regions[i]); 185 EXPECT_EQ(TEST->req.base, regions[i]->base); 186 EXPECT_EQ(TEST->req.size, regions[i]->size); 187 } else { 188 EXPECT_NULL(regions[i]); 189 } 190 } 191 192 // No need for any explicit cleanup. Our region references will go out of 193 // scope first and be returned to the allocator. Then the allocator will 194 // clean up, and release its bookkeeping pool reference in the process. 195 196 END_TEST; 197} 198 199static bool ralloc_add_overlap_test() { 200 BEGIN_TEST; 201 202 // Make a pool and attach it to an allocator. Then add the test regions to it. 203 RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); 204 205 // Add each of the regions specified by the test and check the expected results. 206 for (size_t i = 0; i < fbl::count_of(ADD_OVERLAP_TESTS); ++i) { 207 const alloc_add_overlap_test_t* TEST = ADD_OVERLAP_TESTS + i; 208 209 zx_status_t res = alloc.AddRegion(TEST->reg, TEST->ovl); 210 211 EXPECT_EQ(TEST->res, res); 212 EXPECT_EQ(TEST->cnt, alloc.AvailableRegionCount()); 213 } 214 215 END_TEST; 216} 217 218static bool ralloc_subtract_test() { 219 BEGIN_TEST; 220 221 // Make a pool and attach it to an allocator. Then add the test regions to it. 222 RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); 223 224 // Run the test sequence, adding and subtracting regions and verifying the results. 225 for (size_t i = 0; i < fbl::count_of(SUBTRACT_TESTS); ++i) { 226 const alloc_subtract_test_t* TEST = SUBTRACT_TESTS + i; 227 228 zx_status_t res; 229 if (TEST->add) 230 res = alloc.AddRegion(TEST->reg); 231 else 232 res = alloc.SubtractRegion(TEST->reg, TEST->incomplete); 233 234 EXPECT_EQ(TEST->res ? ZX_OK : ZX_ERR_INVALID_ARGS, res); 235 EXPECT_EQ(TEST->cnt, alloc.AvailableRegionCount()); 236 } 237 238 END_TEST; 239} 240 241static bool ralloc_alloc_walk_test() { 242 BEGIN_TEST; 243 244 const ralloc_region_t test_regions[] = { 245 { .base = 0x00000000, .size = 1 << 20 }, 246 { .base = 0x10000000, .size = 1 << 20 }, 247 { .base = 0x20000000, .size = 1 << 20 }, 248 { .base = 0x30000000, .size = 1 << 20 }, 249 { .base = 0x40000000, .size = 1 << 20 }, 250 { .base = 0x50000000, .size = 1 << 20 }, 251 { .base = 0x60000000, .size = 1 << 20 }, 252 { .base = 0x70000000, .size = 1 << 20 }, 253 { .base = 0x80000000, .size = 1 << 20 }, 254 { .base = 0x90000000, .size = 1 << 20 }, 255 }; 256 constexpr size_t r_cnt = fbl::count_of(test_regions); 257 258 RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); 259 EXPECT_EQ(ZX_OK, alloc.AddRegion({ .base = 0, .size = UINT64_MAX})); 260 261 // Pull each region defined above out of the allocator and stash their UPtrs 262 // for the time being. Then the lambda can walk the allocated regions and 263 // verify that they are in-order and match the expected values. 264 RegionAllocator::Region::UPtr r[r_cnt]; 265 for (unsigned i = 0; i < r_cnt; i++) { 266 EXPECT_EQ(ZX_OK, alloc.GetRegion(test_regions[i], r[i])); 267 } 268 269 uint8_t pos = 0; 270 uint64_t end = 0; 271 auto f = [&](const ralloc_region_t* r) -> bool { 272 ASSERT_EQ(r->base, test_regions[pos].base); 273 ASSERT_EQ(r->size, test_regions[pos].size); 274 pos++; 275 276 // attempt to exit early if end is set to a value > 0 277 return (end) ? (pos != end) : true; 278 }; 279 280 alloc.WalkAllocatedRegions(f); 281 ASSERT_EQ(r_cnt, pos); 282 283 // Test that exiting early works, no matter where we are in the region list. 284 // Every time the function is called we increment the counter and then at 285 // the end ensure we've only been called as many times as expected, within 286 // the bounds of [1, r_cnt]. 287 for (size_t cnt = 0; cnt < 1024; cnt++) { 288 pos = 0; 289 end = (rand() % r_cnt) + 1; 290 alloc.WalkAllocatedRegions(f); 291 ASSERT_EQ(pos, end); 292 } 293 294 END_TEST; 295} 296 297} //namespace 298 299BEGIN_TEST_CASE(ralloc_tests) 300RUN_NAMED_TEST("Region Pools", ralloc_region_pools_test) 301RUN_NAMED_TEST("Alloc by size", ralloc_by_size_test) 302RUN_NAMED_TEST("Alloc specific", ralloc_specific_test) 303RUN_NAMED_TEST("Add/Overlap", ralloc_add_overlap_test) 304RUN_NAMED_TEST("Subtract", ralloc_subtract_test) 305RUN_NAMED_TEST("Allocated Walk", ralloc_alloc_walk_test) 306END_TEST_CASE(ralloc_tests) 307