lib/magma/tests/unit_tests/test_address_space_allocator.cc

// 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 "magma_util/dlog.h"
#include "magma_util/retry_allocator.h"
#include "magma_util/simple_allocator.h"
#include "gtest/gtest.h"
#include <list>

#define ROUNDUP(a, b) (((a) + ((b)-1)) & ~((b)-1))
#define ALIGN(a, b) ROUNDUP(a, b)

namespace {

class Region {
public:
    Region(magma::AddressSpaceAllocator* allocator, uint64_t addr)
        : allocator_(allocator), addr_(addr)
    {
    }
    ~Region() { EXPECT_EQ(true, allocator_->Free(addr_)); }

    magma::AddressSpaceAllocator* allocator_;
    uint64_t addr_;
};
} // namespace

static void test_simple_allocator(magma::SimpleAllocator* allocator, uint8_t align_pow2)
{
    DLOG("test_simple_allocator align_pow2 0x%x\n", align_pow2);

    uint64_t expected_addr = allocator->base();
    uint64_t addr;
    size_t size;
    bool ret;

    std::list<Region> allocs;

    // size zero invalid
    ret = allocator->Alloc(0, align_pow2, &addr);
    EXPECT_EQ(ret, false);

    ret = allocator->GetSize(0, &size);
    EXPECT_EQ(ret, false);

    // the maximum size
    ret = allocator->Alloc(allocator->size(), align_pow2, &addr);
    EXPECT_EQ(ret, true);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        allocs.emplace_back(allocator, addr);

        ret = allocator->GetSize(addr, &size);
        EXPECT_EQ(ret, true);
        EXPECT_EQ(size, allocator->size());

        ret = allocator->Alloc(1, align_pow2, &addr);
        EXPECT_EQ(ret, false);

        // free the big kahuna
        allocs.clear();
    }

    ret = allocator->Alloc(PAGE_SIZE, align_pow2, &addr);
    EXPECT_EQ(ret, allocator->size() >= expected_addr + PAGE_SIZE);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        expected_addr = ALIGN(expected_addr + PAGE_SIZE, 1 << align_pow2);
        allocs.emplace_back(allocator, addr);
    }

    ret = allocator->Alloc(PAGE_SIZE - 1, align_pow2, &addr);
    EXPECT_EQ(ret, allocator->size() >= expected_addr + PAGE_SIZE);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        expected_addr = ALIGN(expected_addr + PAGE_SIZE, 1 << align_pow2);
        allocs.emplace_back(allocator, addr);
    }

    ret = allocator->Alloc(PAGE_SIZE + 1, align_pow2, &addr);
    EXPECT_EQ(ret, allocator->size() >= expected_addr + 2 * PAGE_SIZE);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        expected_addr = ALIGN(expected_addr + 2 * PAGE_SIZE, 1 << align_pow2);
        allocs.emplace_back(allocator, addr);
    }

    ret = allocator->Alloc(PAGE_SIZE * 20, align_pow2, &addr);
    EXPECT_EQ(ret, allocator->size() >= expected_addr + 20 * PAGE_SIZE);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        allocs.emplace_back(allocator, addr);
    }
}

static void stress_test_allocator(magma::AddressSpaceAllocator* allocator, uint8_t align_pow2,
                                  unsigned int num_iterations, size_t max_alloc_size)
{
    unsigned int num_init = allocator->size() / max_alloc_size * 3 / 2;

    DLOG("test_allocator align_pow2 0x%x num_iterations %d num_init %u\n", align_pow2,
         num_iterations, num_init);

    std::vector<std::unique_ptr<Region>> allocs;
    uint64_t addr;

    srand(1);

    for (unsigned int n = 0; n < num_init; n++) {
        size_t size = rand() % max_alloc_size + 1;
        bool ret = allocator->Alloc(size, align_pow2, &addr);
        EXPECT_EQ(ret, true);
        if (ret)
            allocs.emplace_back(new Region(allocator, addr));
    }

    for (unsigned int n = 0; n < num_iterations; n++) {
        size_t size = rand() % max_alloc_size + 1;
        bool ret = allocator->Alloc(size, align_pow2, &addr);
        EXPECT_EQ(ret, true);
        if (ret) {
            unsigned int index = rand() % allocs.size();
            DASSERT(index < allocs.size());
            allocs[index] = std::unique_ptr<Region>(new Region(allocator, addr));
        }
    }
}

static void test_retry_allocator(magma::RetryAllocator* allocator, uint8_t align_pow2)
{
    DLOG("test_retry_allocator align_pow2 0x%x\n", align_pow2);

    uint64_t expected_addr = allocator->base();
    uint64_t addr;
    bool ret;

    std::list<Region> allocs;

    // size zero invalid
    ret = allocator->Alloc(0, align_pow2, [](uint64_t addr) { return true; }, &addr);
    EXPECT_FALSE(ret);

    // the maximum size
    ret =
        allocator->Alloc(allocator->size(), align_pow2, [](uint64_t addr) { return true; }, &addr);
    EXPECT_TRUE(ret);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);

        ret = allocator->Alloc(1, align_pow2, [](uint64_t addr) { return true; }, &addr);
        EXPECT_EQ(ret, false);

        allocator->Free(addr, allocator->size());
    }

    ret = allocator->Alloc(PAGE_SIZE, align_pow2, [](uint64_t addr) { return true; }, &addr);
    EXPECT_EQ(ret, allocator->size() >= expected_addr + PAGE_SIZE);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        expected_addr = ALIGN(expected_addr + PAGE_SIZE, 1 << align_pow2);
    }

    ret = allocator->Alloc(PAGE_SIZE - 1, align_pow2, [](uint64_t addr) { return true; }, &addr);
    EXPECT_EQ(ret, allocator->size() >= expected_addr + PAGE_SIZE);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        expected_addr = ALIGN(expected_addr + PAGE_SIZE, 1 << align_pow2);
    }

    ret = allocator->Alloc(PAGE_SIZE + 1, align_pow2, [](uint64_t addr) { return true; }, &addr);
    EXPECT_EQ(ret, allocator->size() >= expected_addr + 2 * PAGE_SIZE);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        expected_addr = ALIGN(expected_addr + 2 * PAGE_SIZE, 1 << align_pow2);
    }

    ret = allocator->Alloc(PAGE_SIZE * 20, align_pow2, [](uint64_t addr) { return true; }, &addr);
    EXPECT_EQ(ret, allocator->size() >= expected_addr + 20 * PAGE_SIZE);
    if (ret) {
        EXPECT_EQ(addr, expected_addr);
        EXPECT_TRUE(addr % (1 << align_pow2) == 0);
    }

    for (uint32_t i = 0; i < 10; i++) {
        ret = allocator->Alloc(PAGE_SIZE, align_pow2,
                               [](uint64_t addr) { return addr % (PAGE_SIZE * 2) == 0; }, &addr);
        EXPECT_EQ(ret, allocator->size() >= expected_addr + PAGE_SIZE);
        if (ret) {
            EXPECT_EQ(0u, addr % (2 * PAGE_SIZE));
            EXPECT_TRUE(addr % (1 << align_pow2) == 0);
        }
    }
}

TEST(AddressSpaceAllocator, SimpleAllocator)
{
    test_simple_allocator(magma::SimpleAllocator::Create(0, 4 * PAGE_SIZE).get(), 0);

    const size_t _4g = 4ULL * 1024 * 1024 * 1024;
    test_simple_allocator(magma::SimpleAllocator::Create(0, _4g).get(), 0);
    test_simple_allocator(magma::SimpleAllocator::Create(0, _4g).get(), 1);
    test_simple_allocator(magma::SimpleAllocator::Create(0, _4g).get(), 12);
    test_simple_allocator(magma::SimpleAllocator::Create(0, _4g).get(), 13);

    stress_test_allocator(magma::SimpleAllocator::Create(0, _4g).get(), 0, 100000,
                          16ULL * 1024 * 1024);
}

TEST(AddressSpaceAllocator, RetryAllocator)
{
    test_retry_allocator(magma::RetryAllocator::Create(0, 4 * PAGE_SIZE).get(), 0);

    const size_t _4g = 4ULL * 1024 * 1024 * 1024;
    test_retry_allocator(magma::RetryAllocator::Create(0, _4g).get(), 0);
    test_retry_allocator(magma::RetryAllocator::Create(0, _4g).get(), 1);
    test_retry_allocator(magma::RetryAllocator::Create(0, _4g).get(), 12);
    test_retry_allocator(magma::RetryAllocator::Create(0, _4g).get(), 13);
}