| // 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 "chromiumos-wide-profiling/address_mapper.h" |
| |
| #include <algorithm> |
| #include <memory> |
| |
| #include "base/logging.h" |
| #include "base/macros.h" |
| |
| #include "chromiumos-wide-profiling/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; |
| |
| 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_->GetMappedAddress(addr, &mapped_addr)); |
| EXPECT_EQ(expected_mapped_addr + offset, mapped_addr); |
| |
| uint64_t mapped_offset; |
| uint64_t mapped_id; |
| EXPECT_TRUE( |
| mapper_->GetMappedIDAndOffset(addr, &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_->GetMappedAddress(range.addr + range.size - 1, |
| &mapped_addr)); |
| 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; |
| EXPECT_FALSE(mapper_->GetMappedAddress(range.addr - 1, &mapped_addr)); |
| EXPECT_FALSE(mapper_->GetMappedAddress(range.addr - 0x100, &mapped_addr)); |
| EXPECT_FALSE(mapper_->GetMappedAddress(range.addr + range.size, |
| &mapped_addr)); |
| EXPECT_FALSE(mapper_->GetMappedAddress(range.addr + range.size + 0x100, |
| &mapped_addr)); |
| 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; |
| 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_->GetMappedAddress(range.addr - 1, &mapped_addr)); |
| EXPECT_FALSE(mapper_->GetMappedAddress(range.addr - 0x100, &mapped_addr)); |
| EXPECT_FALSE(mapper_->GetMappedAddress(range.addr + range.size, |
| &mapped_addr)); |
| EXPECT_FALSE(mapper_->GetMappedAddress(range.addr + range.size + 0x100, |
| &mapped_addr)); |
| } |
| |
| // 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_->GetMappedAddress(addr, &mapped_addr)); |
| } |
| |
| // 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; |
| bool map_success = mapper_->GetMappedAddress(addr, &mapped_addr); |
| 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; |
| bool map_success = mapper_->GetMappedAddress(addr, &mapped_addr); |
| 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; |
| EXPECT_FALSE( |
| mapper_->GetMappedAddress(kOutOfBoundsRegion.addr + 0x100, &mapped_addr)); |
| } |
| |
| // 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 |