// Copyright (c) 2013 The Chromium OS 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 "address_mapper.h"
#include <algorithm>
#include <memory>
#include "base/logging.h"
#include "base/macros.h"
#include "compat/test.h"
namespace quipper {
namespace {
struct Range {
uint64_t addr;
uint64_t size;
uint64_t id;
uint64_t base_offset;
Range() : addr(0), size(0), id(0), base_offset(0) {}
Range(uint64_t addr, uint64_t size, uint64_t id, uint64_t base_offset)
: addr(addr), size(size), id(id), base_offset(base_offset) {}
bool contains(const uint64_t check_addr) const {
return (check_addr >= addr && check_addr < addr + size);
}
};
// Some address ranges to map. It is important that none of these overlap with
// each other, nor are any two of them contiguous.
const Range kMapRanges[] = {
Range(0xff000000, 0x100000, 0xdeadbeef, 0),
Range(0x00a00000, 0x10000, 0xcafebabe, 0),
Range(0x0c000000, 0x1000000, 0x900df00d, 0),
Range(0x00001000, 0x30000, 0x9000091e, 0),
};
// List of real addresses that are not in the above ranges.
const uint64_t kAddressesNotInRanges[] = {
0x00000000, 0x00000100, 0x00038000, 0x00088888, 0x00100000, 0x004fffff,
0x00a20000, 0x00cc0000, 0x00ffffff, 0x03e00000, 0x0b000000, 0x0d100000,
0x0fffffff, 0x1fffffff, 0x7ffffff0, 0xdffffff0, 0xfe000000, 0xffffffff,
};
// Number of regularly-spaced intervals within a mapped range to test.
const int kNumRangeTestIntervals = 8;
// A simple test function to convert a real address to a mapped address.
// Address ranges in |ranges| are mapped starting at address 0.
uint64_t GetMappedAddressFromRanges(const Range* ranges,
const unsigned int num_ranges,
const uint64_t addr) {
unsigned int i;
uint64_t mapped_range_addr;
for (i = 0, mapped_range_addr = 0; i < num_ranges;
mapped_range_addr += ranges[i].size, ++i) {
const Range& range = ranges[i];
if (range.contains(addr)) return (addr - range.addr) + mapped_range_addr;
}
return static_cast<uint64_t>(-1);
}
} // namespace
// The unit test class for AddressMapper.
class AddressMapperTest : public ::testing::Test {
public:
AddressMapperTest() {}
~AddressMapperTest() {}
virtual void SetUp() { mapper_.reset(new AddressMapper); }
protected:
// Maps a range using the AddressMapper and makes sure that it was successful.
// Uses all fields of |range|, including id and base_offset.
bool MapRange(const Range& range, bool remove_old_mappings) {
VLOG(1) << "Mapping range at " << std::hex << range.addr
<< " with length of " << range.size << " and id " << range.id;
return mapper_->MapWithID(range.addr, range.size, range.id,
range.base_offset, remove_old_mappings);
}
// Tests a range that has been mapped. |expected_mapped_addr| is the starting
// address that it should have been mapped to. This mapper will test the start
// and end addresses of the range, as well as a bunch of addresses inside it.
// Also checks lookup of ID and offset.
void TestMappedRange(const Range& range, uint64_t expected_mapped_addr) {
uint64_t mapped_addr = UINT64_MAX;
AddressMapper::MappingList::const_iterator addr_iter;
VLOG(1) << "Testing range at " << std::hex << range.addr
<< " with length of " << std::hex << range.size;
// Check address at the beginning of the range and at subsequent intervals.
for (int i = 0; i < kNumRangeTestIntervals; ++i) {
const uint64_t offset = i * (range.size / kNumRangeTestIntervals);
uint64_t addr = range.addr + offset;
EXPECT_TRUE(mapper_->GetMappedAddressAndListIterator(addr, &mapped_addr,
&addr_iter));
EXPECT_EQ(expected_mapped_addr + offset, mapped_addr);
uint64_t mapped_offset;
uint64_t mapped_id;
mapper_->GetMappedIDAndOffset(addr, addr_iter, &mapped_id,
&mapped_offset);
EXPECT_EQ(range.base_offset + offset, mapped_offset);
EXPECT_EQ(range.id, mapped_id);
}
// Check address at end of the range.
EXPECT_TRUE(mapper_->GetMappedAddressAndListIterator(
range.addr + range.size - 1, &mapped_addr, &addr_iter));
EXPECT_EQ(expected_mapped_addr + range.size - 1, mapped_addr);
}
std::unique_ptr<AddressMapper> mapper_;
};
// Map one range at a time and test looking up addresses.
TEST_F(AddressMapperTest, MapSingle) {
for (const Range& range : kMapRanges) {
mapper_.reset(new AddressMapper);
ASSERT_TRUE(MapRange(range, false));
EXPECT_EQ(1U, mapper_->GetNumMappedRanges());
TestMappedRange(range, 0);
// Check addresses before the mapped range, should be invalid.
uint64_t mapped_addr;
AddressMapper::MappingList::const_iterator iter;
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(range.addr - 1,
&mapped_addr, &iter));
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(range.addr - 0x100,
&mapped_addr, &iter));
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(
range.addr + range.size, &mapped_addr, &iter));
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(
range.addr + range.size + 0x100, &mapped_addr, &iter));
EXPECT_EQ(range.size, mapper_->GetMaxMappedLength());
}
}
// Map all the ranges at once and test looking up addresses.
TEST_F(AddressMapperTest, MapAll) {
uint64_t size_mapped = 0;
for (const Range& range : kMapRanges) {
ASSERT_TRUE(MapRange(range, false));
size_mapped += range.size;
}
EXPECT_EQ(arraysize(kMapRanges), mapper_->GetNumMappedRanges());
// Check the max mapped length in quipper space.
EXPECT_EQ(size_mapped, mapper_->GetMaxMappedLength());
// For each mapped range, test addresses at the start, middle, and end.
// Also test the address right before and after each range.
uint64_t mapped_addr;
AddressMapper::MappingList::const_iterator iter;
for (const Range& range : kMapRanges) {
TestMappedRange(range, GetMappedAddressFromRanges(
kMapRanges, arraysize(kMapRanges), range.addr));
// Check addresses before and after the mapped range, should be invalid.
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(range.addr - 1,
&mapped_addr, &iter));
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(range.addr - 0x100,
&mapped_addr, &iter));
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(
range.addr + range.size, &mapped_addr, &iter));
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(
range.addr + range.size + 0x100, &mapped_addr, &iter));
}
// Test some addresses that are out of these ranges, should not be able to
// get mapped addresses.
for (uint64_t addr : kAddressesNotInRanges)
EXPECT_FALSE(
mapper_->GetMappedAddressAndListIterator(addr, &mapped_addr, &iter));
}
// Map all the ranges at once and test looking up IDs and offsets.
TEST_F(AddressMapperTest, MapAllWithIDsAndOffsets) {
for (const Range& range : kMapRanges) {
LOG(INFO) << "Mapping range at " << std::hex << range.addr
<< " with length of " << std::hex << range.size;
ASSERT_TRUE(mapper_->MapWithID(range.addr, range.size, range.id, 0, false));
}
EXPECT_EQ(arraysize(kMapRanges), mapper_->GetNumMappedRanges());
// For each mapped range, test addresses at the start, middle, and end.
// Also test the address right before and after each range.
for (const Range& range : kMapRanges) {
TestMappedRange(range, GetMappedAddressFromRanges(
kMapRanges, arraysize(kMapRanges), range.addr));
}
}
// Test overlap detection.
TEST_F(AddressMapperTest, OverlapSimple) {
// Map all the ranges first.
for (const Range& range : kMapRanges) ASSERT_TRUE(MapRange(range, false));
// Attempt to re-map each range, but offset by size / 2.
for (const Range& range : kMapRanges) {
Range new_range;
new_range.addr = range.addr + range.size / 2;
new_range.size = range.size;
// The maps should fail because of overlap with an existing mapping.
EXPECT_FALSE(MapRange(new_range, false));
}
// Re-map each range with the same offset. Only this time, remove any old
// mapped range that overlaps with it.
for (const Range& range : kMapRanges) {
Range new_range;
new_range.addr = range.addr + range.size / 2;
new_range.size = range.size;
EXPECT_TRUE(MapRange(new_range, true));
// Make sure the number of ranges is unchanged (one deleted, one added).
EXPECT_EQ(arraysize(kMapRanges), mapper_->GetNumMappedRanges());
// The range is shifted in real space but should still be the same in
// quipper space.
TestMappedRange(
new_range, GetMappedAddressFromRanges(kMapRanges, arraysize(kMapRanges),
range.addr));
}
}
// Test mapping of a giant map that overlaps with all existing ranges.
TEST_F(AddressMapperTest, OverlapBig) {
// A huge region that overlaps with all ranges in |kMapRanges|.
const Range kBigRegion(0xa00, 0xff000000, 0x1234, 0);
// Map all the ranges first.
for (const Range& range : kMapRanges) ASSERT_TRUE(MapRange(range, false));
// Make sure overlap is detected before removing old ranges.
ASSERT_FALSE(MapRange(kBigRegion, false));
ASSERT_TRUE(MapRange(kBigRegion, true));
EXPECT_EQ(1U, mapper_->GetNumMappedRanges());
TestMappedRange(kBigRegion, 0);
// Given the list of previously unmapped addresses, test that the ones within
// |kBigRegion| are now mapped; for the ones that are not, test that they are
// not mapped.
for (uint64_t addr : kAddressesNotInRanges) {
uint64_t mapped_addr = UINT64_MAX;
AddressMapper::MappingList::const_iterator addr_iter;
bool map_success = mapper_->GetMappedAddressAndListIterator(
addr, &mapped_addr, &addr_iter);
if (kBigRegion.contains(addr)) {
EXPECT_TRUE(map_success);
EXPECT_EQ(addr - kBigRegion.addr, mapped_addr);
} else {
EXPECT_FALSE(map_success);
}
}
// Check that addresses in the originally mapped ranges no longer map to the
// same addresses if they fall within |kBigRegion|, and don't map at all if
// they are not within |kBigRegion|.
for (const Range& range : kMapRanges) {
for (uint64_t addr = range.addr; addr < range.addr + range.size;
addr += range.size / kNumRangeTestIntervals) {
uint64_t mapped_addr = UINT64_MAX;
AddressMapper::MappingList::const_iterator addr_iter;
bool map_success = mapper_->GetMappedAddressAndListIterator(
addr, &mapped_addr, &addr_iter);
if (kBigRegion.contains(addr)) {
EXPECT_TRUE(map_success);
EXPECT_EQ(addr - kBigRegion.addr, mapped_addr);
} else {
EXPECT_FALSE(map_success);
}
}
}
EXPECT_EQ(kBigRegion.size, mapper_->GetMaxMappedLength());
}
// Test a mapping at the end of memory space.
TEST_F(AddressMapperTest, EndOfMemory) {
// A region that extends to the end of the address space.
const Range kEndRegion(0xffffffff00000000, 0x100000000, 0x3456, 0);
ASSERT_TRUE(MapRange(kEndRegion, true));
EXPECT_EQ(1U, mapper_->GetNumMappedRanges());
TestMappedRange(kEndRegion, 0);
}
// Test mapping of an out-of-bounds mapping.
TEST_F(AddressMapperTest, OutOfBounds) {
// A region toward the end of address space that overruns the end of the
// address space.
const Range kOutOfBoundsRegion(0xffffffff00000000, 0x00000000, 0xccddeeff, 0);
ASSERT_FALSE(MapRange(kOutOfBoundsRegion, false));
ASSERT_FALSE(MapRange(kOutOfBoundsRegion, true));
EXPECT_EQ(0, mapper_->GetNumMappedRanges());
uint64_t mapped_addr;
AddressMapper::MappingList::const_iterator iter;
EXPECT_FALSE(mapper_->GetMappedAddressAndListIterator(
kOutOfBoundsRegion.addr + 0x100, &mapped_addr, &iter));
}
// Test mapping of a region that covers the entire memory space. Then map other
// regions over it.
TEST_F(AddressMapperTest, FullRange) {
// A huge region that covers all of the available space.
const Range kFullRegion(0, UINT64_MAX, 0xaabbccdd, 0);
ASSERT_TRUE(MapRange(kFullRegion, false));
size_t num_expected_ranges = 1;
EXPECT_EQ(num_expected_ranges, mapper_->GetNumMappedRanges());
TestMappedRange(kFullRegion, 0);
// Map some smaller ranges.
for (const Range& range : kMapRanges) {
// Check for collision first.
ASSERT_FALSE(MapRange(range, false));
ASSERT_TRUE(MapRange(range, true));
// Make sure the number of mapped ranges has increased by two. The mapping
// should have split an existing range.
num_expected_ranges += 2;
EXPECT_EQ(num_expected_ranges, mapper_->GetNumMappedRanges());
}
}
// Test mapping of one range in the middle of an existing range. The existing
// range should be split into two to accommodate it. Also tests the use of base
// offsets.
TEST_F(AddressMapperTest, SplitRangeWithOffsetBase) {
// Define the two ranges, with distinct IDs.
const Range kFirstRange(0x10000, 0x4000, 0x11223344, 0x5000);
const Range kSecondRange(0x12000, 0x1000, 0x55667788, 0);
// As a sanity check, make sure the second range is fully contained within the
// first range.
EXPECT_LT(kFirstRange.addr, kSecondRange.addr);
EXPECT_GT(kFirstRange.addr + kFirstRange.size,
kSecondRange.addr + kSecondRange.size);
// Map the two ranges.
ASSERT_TRUE(MapRange(kFirstRange, true));
ASSERT_TRUE(MapRange(kSecondRange, true));
// The first range should have been split into two parts to make way for the
// second range. There should be a total of three ranges.
EXPECT_EQ(3U, mapper_->GetNumMappedRanges());
// Now make sure the mappings are correct.
// The first range has been split up. Define the expected ranges here.
const Range kFirstRangeHead(0x10000, 0x2000, kFirstRange.id, 0x5000);
const Range kFirstRangeTail(0x13000, 0x1000, kFirstRange.id, 0x8000);
// Test the two remaining parts of the first range.
TestMappedRange(kFirstRangeHead, 0);
TestMappedRange(kFirstRangeTail, kFirstRangeTail.addr - kFirstRangeHead.addr);
// Test the second range normally.
TestMappedRange(kSecondRange, kSecondRange.addr - kFirstRange.addr);
}
// Test mappings that are not aligned to mmap page boundaries.
TEST_F(AddressMapperTest, NotPageAligned) {
mapper_->set_page_alignment(0x1000);
// Some address ranges that do not begin on a page boundary.
const Range kUnalignedRanges[] = {
Range(0xff000100, 0x1fff00, 0xdeadbeef, 0x100),
Range(0x00a00180, 0x10000, 0xcafebabe, 0x180),
Range(0x0c000300, 0x1000800, 0x900df00d, 0x4300),
Range(0x000017f0, 0x30000, 0x9000091e, 0x7f0),
};
// Map the ranges.
for (const Range& range : kUnalignedRanges)
ASSERT_TRUE(MapRange(range, true));
EXPECT_EQ(4U, mapper_->GetNumMappedRanges());
// Now make sure the mappings are correct.
// First region is mapped as usual, except it does not start at the page
// boundary.
TestMappedRange(kUnalignedRanges[0], 0x00000100);
// Second region follows at the end of the first, but notice that its length
// is a full number of pages, which means...
TestMappedRange(kUnalignedRanges[1], 0x00200180);
// ... the third region starts beyond the next page boundary: 0x211000 instead
// of 0x210000.
TestMappedRange(kUnalignedRanges[2], 0x00211300);
// Similarly, the fourth region starts beyond the next page boundary:
// 0x1212000 instead of 0x1211000.
TestMappedRange(kUnalignedRanges[3], 0x012127f0);
}
// Have one mapping in the middle of another, with a nonzero page alignment
// parameter.
TEST_F(AddressMapperTest, SplitRangeWithPageAlignment) {
mapper_->set_page_alignment(0x1000);
// These should map just fine.
const Range kRange0(0x3000, 0x8000, 0xdeadbeef, 0);
const Range kRange1(0x5000, 0x2000, 0xfeedbabe, 0);
EXPECT_TRUE(MapRange(kRange0, true));
EXPECT_TRUE(MapRange(kRange1, true));
EXPECT_EQ(3U, mapper_->GetNumMappedRanges());
// Determine the expected split mappings.
const Range kRange0Head(0x3000, 0x2000, 0xdeadbeef, 0);
const Range kRange0Tail(0x7000, 0x4000, 0xdeadbeef, 0x4000);
// Everything should be mapped and split as usual.
TestMappedRange(kRange0Head, 0);
TestMappedRange(kRange0Tail, 0x4000);
TestMappedRange(kRange1, 0x2000);
}
// Have one mapping in the middle of another, with a nonzero page alignment
// parameter. The overlapping region will not be aligned to page boundaries.
TEST_F(AddressMapperTest, MisalignedSplitRangeWithPageAlignment) {
mapper_->set_page_alignment(0x1000);
const Range kRange0(0x3000, 0x8000, 0xdeadbeef, 0);
const Range kMisalignedRange(0x4800, 0x2000, 0xfeedbabe, 0);
EXPECT_TRUE(MapRange(kRange0, true));
// The misaligned mapping should not find enough space to split the existing
// range. It is not allowed to move the existing mapping.
EXPECT_FALSE(MapRange(kMisalignedRange, true));
}
} // namespace quipper