| // Copyright 2016 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include <region-alloc/region-alloc.h> |
| #include <stdio.h> |
| #include <unittest/unittest.h> |
| #include <inttypes.h> |
| |
| #include <fbl/algorithm.h> |
| |
| #include <utility> |
| |
| #include "common.h" |
| |
| namespace { |
| |
| static bool ralloc_region_pools_test() { |
| BEGIN_TEST; |
| |
| // Create a default constructed allocator on the stack. |
| RegionAllocator alloc; |
| |
| { |
| // Make sure that it refuses to perform any operations because it has no |
| // RegionPool assigned to it yet. |
| RegionAllocator::Region::UPtr tmp; |
| EXPECT_EQ(ZX_ERR_BAD_STATE, alloc.AddRegion({ 0u, 1u })); |
| EXPECT_EQ(ZX_ERR_BAD_STATE, alloc.GetRegion(1, tmp)); |
| EXPECT_EQ(ZX_ERR_BAD_STATE, alloc.GetRegion({ 0u, 1u }, tmp)); |
| EXPECT_NULL(alloc.GetRegion(1)); |
| EXPECT_NULL(alloc.GetRegion({ 0u, 1u })); |
| } |
| |
| // Make a region pool to manage bookkeeping allocations. |
| auto pool = RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE); |
| ASSERT_NONNULL(pool); |
| |
| // Assign our pool to our allocator, but hold onto the pool for now. |
| ASSERT_EQ(ZX_OK, alloc.SetRegionPool(pool)); |
| EXPECT_NONNULL(pool); |
| |
| // Create another allocator and transfer ownership of our region pool |
| // reference to it. Then let the allocator go out of scope. |
| { |
| RegionAllocator alloc2(std::move(pool)); |
| EXPECT_NULL(pool); |
| } |
| EXPECT_NULL(pool); |
| |
| // Add some regions to our allocator. |
| for (size_t i = 0; i < fbl::count_of(GOOD_REGIONS); ++i) |
| EXPECT_EQ(ZX_OK, alloc.AddRegion(GOOD_REGIONS[i])); |
| |
| // Make a new pool and try to assign it to the allocator. This should fail |
| // because the allocator is currently using resources from its currently |
| // assigned pool. |
| auto pool2 = RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE); |
| ASSERT_NONNULL(pool2); |
| EXPECT_EQ(ZX_ERR_BAD_STATE, alloc.SetRegionPool(pool2)); |
| |
| // Add a bunch of adjacent regions to our pool. Try to add so many |
| // that we would normally run out of bookkeeping space. We should not |
| // actually run out, however, because the regions should get merged as they |
| // get added. |
| { |
| ralloc_region_t tmp = { .base = GOOD_MERGE_REGION_BASE, |
| .size = GOOD_MERGE_REGION_SIZE }; |
| for (size_t i = 0; i < OOM_RANGE_LIMIT; ++i) { |
| ASSERT_EQ(ZX_OK, alloc.AddRegion(tmp)); |
| tmp.base += tmp.size; |
| } |
| } |
| |
| // Attempt (and fail) to add some bad regions (regions which overlap, |
| // regions which wrap the address space) |
| for (size_t i = 0; i < fbl::count_of(BAD_REGIONS); ++i) |
| EXPECT_EQ(ZX_ERR_INVALID_ARGS, alloc.AddRegion(BAD_REGIONS[i])); |
| |
| // Force the region bookkeeping pool to run out of memory by adding more and |
| // more regions until we eventually run out of room. Make sure that the |
| // regions are not adjacent, or the internal bookkeeping will just merge |
| // them. |
| { |
| size_t i; |
| ralloc_region_t tmp = { .base = BAD_MERGE_REGION_BASE, |
| .size = BAD_MERGE_REGION_SIZE }; |
| for (i = 0; i < OOM_RANGE_LIMIT; ++i) { |
| zx_status_t res; |
| |
| res = alloc.AddRegion(tmp); |
| if (res != ZX_OK) { |
| EXPECT_EQ(ZX_ERR_NO_MEMORY, res); |
| break; |
| } |
| |
| tmp.base += tmp.size + 1; |
| } |
| |
| EXPECT_LT(i, OOM_RANGE_LIMIT); |
| } |
| |
| // Reset allocator. All of the existing available regions we had previously |
| // added will be returned to the pool. |
| alloc.Reset(); |
| |
| // Now assign pool2 to the allocator. Now that it is no longer using any |
| // resources, this should succeed. |
| EXPECT_EQ(ZX_OK, alloc.SetRegionPool(std::move(pool2))); |
| EXPECT_NULL(pool2); |
| |
| END_TEST; |
| } |
| |
| static bool ralloc_by_size_test() { |
| BEGIN_TEST; |
| |
| // Make a pool and attach it to an allocator. Then add the test regions to it. |
| RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); |
| |
| for (size_t i = 0; i < fbl::count_of(ALLOC_BY_SIZE_REGIONS); ++i) |
| ASSERT_EQ(ZX_OK, alloc.AddRegion(ALLOC_BY_SIZE_REGIONS[i])); |
| |
| // Run the alloc by size tests. Hold onto the regions it allocates so they |
| // don't automatically get returned to the pool. |
| RegionAllocator::Region::UPtr regions[fbl::count_of(ALLOC_BY_SIZE_TESTS)]; |
| |
| for (size_t i = 0; i < fbl::count_of(ALLOC_BY_SIZE_TESTS); ++i) { |
| const alloc_by_size_alloc_test_t* TEST = ALLOC_BY_SIZE_TESTS + i; |
| zx_status_t res = alloc.GetRegion(TEST->size, TEST->align, regions[i]); |
| |
| // Make sure we get the test result we were expecting. |
| EXPECT_EQ(TEST->res, res); |
| |
| // If the allocation claimed to succeed, we should have gotten |
| // back a non-null region. Otherwise, we should have gotten a |
| // null region back. |
| if (res == ZX_OK) { |
| ASSERT_NONNULL(regions[i]); |
| } else { |
| EXPECT_NULL(regions[i]); |
| } |
| |
| // If the allocation succeeded, and we expected it to succeed, |
| // the allocation should have come from the test region we |
| // expect and be aligned in the way we asked. |
| if ((res == ZX_OK) && (TEST->res == ZX_OK)) { |
| ASSERT_LT(TEST->region, fbl::count_of(ALLOC_BY_SIZE_TESTS)); |
| EXPECT_TRUE(region_contains_region(ALLOC_BY_SIZE_REGIONS + TEST->region, |
| regions[i].get())); |
| EXPECT_EQ(0u, regions[i]->base & (TEST->align - 1)); |
| } |
| |
| } |
| |
| // No need for any explicit cleanup. Our region references will go out of |
| // scope first and be returned to the allocator. Then the allocator will |
| // clean up, and release its bookkeeping pool reference in the process. |
| |
| END_TEST; |
| } |
| |
| static bool ralloc_specific_test() { |
| BEGIN_TEST; |
| |
| // Make a pool and attach it to an allocator. Then add the test regions to it. |
| RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); |
| |
| for (size_t i = 0; i < fbl::count_of(ALLOC_SPECIFIC_REGIONS); ++i) |
| ASSERT_EQ(ZX_OK, alloc.AddRegion(ALLOC_SPECIFIC_REGIONS[i])); |
| |
| // Run the alloc specific tests. Hold onto the regions it allocates so they |
| // don't automatically get returned to the pool. |
| RegionAllocator::Region::UPtr regions[fbl::count_of(ALLOC_SPECIFIC_TESTS)]; |
| |
| for (size_t i = 0; i < fbl::count_of(ALLOC_SPECIFIC_TESTS); ++i) { |
| const alloc_specific_alloc_test_t* TEST = ALLOC_SPECIFIC_TESTS + i; |
| zx_status_t res = alloc.GetRegion(TEST->req, regions[i]); |
| |
| // Make sure we get the test result we were expecting. |
| EXPECT_EQ(TEST->res, res); |
| |
| // If the allocation claimed to succeed, we should have gotten back a |
| // non-null region which exactly matches our requested region. |
| if (res == ZX_OK) { |
| ASSERT_NONNULL(regions[i]); |
| EXPECT_EQ(TEST->req.base, regions[i]->base); |
| EXPECT_EQ(TEST->req.size, regions[i]->size); |
| } else { |
| EXPECT_NULL(regions[i]); |
| } |
| } |
| |
| // No need for any explicit cleanup. Our region references will go out of |
| // scope first and be returned to the allocator. Then the allocator will |
| // clean up, and release its bookkeeping pool reference in the process. |
| |
| END_TEST; |
| } |
| |
| static bool ralloc_add_overlap_test() { |
| BEGIN_TEST; |
| |
| // Make a pool and attach it to an allocator. Then add the test regions to it. |
| RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); |
| |
| // Add each of the regions specified by the test and check the expected results. |
| for (size_t i = 0; i < fbl::count_of(ADD_OVERLAP_TESTS); ++i) { |
| const alloc_add_overlap_test_t* TEST = ADD_OVERLAP_TESTS + i; |
| |
| zx_status_t res = alloc.AddRegion(TEST->reg, TEST->ovl); |
| |
| EXPECT_EQ(TEST->res, res); |
| EXPECT_EQ(TEST->cnt, alloc.AvailableRegionCount()); |
| } |
| |
| END_TEST; |
| } |
| |
| static bool ralloc_subtract_test() { |
| BEGIN_TEST; |
| |
| // Make a pool and attach it to an allocator. Then add the test regions to it. |
| RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); |
| |
| // Run the test sequence, adding and subtracting regions and verifying the results. |
| for (size_t i = 0; i < fbl::count_of(SUBTRACT_TESTS); ++i) { |
| const alloc_subtract_test_t* TEST = SUBTRACT_TESTS + i; |
| |
| zx_status_t res; |
| if (TEST->add) |
| res = alloc.AddRegion(TEST->reg); |
| else |
| res = alloc.SubtractRegion(TEST->reg, TEST->incomplete); |
| |
| EXPECT_EQ(TEST->res ? ZX_OK : ZX_ERR_INVALID_ARGS, res); |
| EXPECT_EQ(TEST->cnt, alloc.AvailableRegionCount()); |
| } |
| |
| END_TEST; |
| } |
| |
| static bool ralloc_alloc_walk_test() { |
| BEGIN_TEST; |
| |
| const ralloc_region_t test_regions[] = { |
| { .base = 0x00000000, .size = 1 << 20 }, |
| { .base = 0x10000000, .size = 1 << 20 }, |
| { .base = 0x20000000, .size = 1 << 20 }, |
| { .base = 0x30000000, .size = 1 << 20 }, |
| { .base = 0x40000000, .size = 1 << 20 }, |
| { .base = 0x50000000, .size = 1 << 20 }, |
| { .base = 0x60000000, .size = 1 << 20 }, |
| { .base = 0x70000000, .size = 1 << 20 }, |
| { .base = 0x80000000, .size = 1 << 20 }, |
| { .base = 0x90000000, .size = 1 << 20 }, |
| }; |
| constexpr size_t r_cnt = fbl::count_of(test_regions); |
| |
| RegionAllocator alloc(RegionAllocator::RegionPool::Create(REGION_POOL_MAX_SIZE)); |
| EXPECT_EQ(ZX_OK, alloc.AddRegion({ .base = 0, .size = UINT64_MAX})); |
| |
| // Pull each region defined above out of the allocator and stash their UPtrs |
| // for the time being. Then the lambda can walk the allocated regions and |
| // verify that they are in-order and match the expected values. |
| RegionAllocator::Region::UPtr r[r_cnt]; |
| for (unsigned i = 0; i < r_cnt; i++) { |
| EXPECT_EQ(ZX_OK, alloc.GetRegion(test_regions[i], r[i])); |
| } |
| |
| uint8_t pos = 0; |
| uint64_t end = 0; |
| auto f = [&](const ralloc_region_t* r) -> bool { |
| ASSERT_EQ(r->base, test_regions[pos].base); |
| ASSERT_EQ(r->size, test_regions[pos].size); |
| pos++; |
| |
| // attempt to exit early if end is set to a value > 0 |
| return (end) ? (pos != end) : true; |
| }; |
| |
| alloc.WalkAllocatedRegions(f); |
| ASSERT_EQ(r_cnt, pos); |
| |
| // Test that exiting early works, no matter where we are in the region list. |
| // Every time the function is called we increment the counter and then at |
| // the end ensure we've only been called as many times as expected, within |
| // the bounds of [1, r_cnt]. |
| for (size_t cnt = 0; cnt < 1024; cnt++) { |
| pos = 0; |
| end = (rand() % r_cnt) + 1; |
| alloc.WalkAllocatedRegions(f); |
| ASSERT_EQ(pos, end); |
| } |
| |
| END_TEST; |
| } |
| |
| } //namespace |
| |
| BEGIN_TEST_CASE(ralloc_tests) |
| RUN_NAMED_TEST("Region Pools", ralloc_region_pools_test) |
| RUN_NAMED_TEST("Alloc by size", ralloc_by_size_test) |
| RUN_NAMED_TEST("Alloc specific", ralloc_specific_test) |
| RUN_NAMED_TEST("Add/Overlap", ralloc_add_overlap_test) |
| RUN_NAMED_TEST("Subtract", ralloc_subtract_test) |
| RUN_NAMED_TEST("Allocated Walk", ralloc_alloc_walk_test) |
| END_TEST_CASE(ralloc_tests) |