chromiumos-wide-profiling/address_mapper_test.cc - mirrors/cros/chromiumos/platform2 - Git at Google

 // 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 "chromiumos-wide-profiling/limits.h"
 #include "chromiumos-wide-profiling/quipper_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(kUint64Max), base_offset(0) {}

   Range(uint64_t addr, uint64_t size)
       : addr(addr), size(size), id(kUint64Max), base_offset(0) {}

   Range(uint64_t addr, uint64_t size, uint64_t id)
       : addr(addr), size(size), id(id), 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),
   Range(0x00a00000,    0x10000, 0xcafebabe),
   Range(0x0c000000,  0x1000000, 0x900df00d),
   Range(0x00001000,    0x30000, 0x9000091e),
 };

 // 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,
 };

 // A huge region that overlaps with all ranges in |kMapRanges|.
 const Range kBigRegion = Range(0xa00, 0xff000000);

 // A region that extends to the end of the address space.
 const Range kEndRegion = Range(0xffffffff00000000, 0x100000000);

 // A region toward the end of address space that overruns the end of the address
 // space.
 const Range kOutOfBoundsRegion = Range(0xffffffff00000000, 0x200000000);

 // A huge region that covers all of the available space.
 const Range kFullRegion = Range(0, kUint64Max);

 // Number of regularly-spaced intervals within a mapped range to test.
 const int kNumRangeTestIntervals = 8;

 // The default range ID when it is not explicitly defined during a mapping.
 const uint64_t kUndefinedRangeID = kUint64Max;

 // 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.
   // Does not specify a range ID.
   bool MapRange(const Range& range, bool remove_old_mappings) {
     LOG(INFO) << "Mapping range at " << std::hex << range.addr
               << " with length of " << std::hex << range.size;
     return mapper_->Map(range.addr, range.size, remove_old_mappings);
   }

   // Maps a range using the AddressMapper and makes sure that it was successful.
   // Provides a specific range ID.
   bool MapRangeWithID(const Range& range, bool remove_old_mappings) {
     LOG(INFO) << "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 address mapping without checking for a particular ID.
   void TestMappedRange(const Range& range,
                        const uint64_t expected_mapped_addr) {
     TestMappedRangeWithID(range, expected_mapped_addr, kUndefinedRangeID, 0);
   }

   // 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 TestMappedRangeWithID(const Range& range,
                              const uint64_t expected_mapped_addr,
                              const uint64_t expected_id,
                              const uint64_t expected_base_offset) {
     uint64_t mapped_addr = kUint64Max;

     LOG(INFO) << "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(expected_base_offset + offset, mapped_offset);
       EXPECT_EQ(expected_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 (unsigned int i = 0; i < arraysize(kMapRanges); ++i) {
     mapper_.reset(new AddressMapper);
     const Range& range = kMapRanges[i];
     ASSERT_TRUE(MapRange(range, false));
     EXPECT_EQ(1, 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) {
   unsigned int i;
   uint64_t size_mapped = 0;
   for (i = 0; i < arraysize(kMapRanges); ++i) {
     ASSERT_TRUE(MapRange(kMapRanges[i], false));
     size_mapped += kMapRanges[i].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 (i = 0; i < arraysize(kMapRanges); ++i) {
     const Range& range = kMapRanges[i];
     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 (i = 0; i < arraysize(kAddressesNotInRanges); ++i) {
     EXPECT_FALSE(mapper_->GetMappedAddress(kAddressesNotInRanges[i],
                  &mapped_addr));
   }
 }

 // Map all the ranges at once and test looking up IDs and offsets.
 TEST_F(AddressMapperTest, MapAllWithIDsAndOffsets) {
   unsigned int i;
   for (i = 0; i < arraysize(kMapRanges); ++i) {
     const Range& range = kMapRanges[i];
     LOG(INFO) << "Mapping range at " << std::hex << range.addr
               << " with length of " << std::hex << range.size;
     ASSERT_TRUE(mapper_->MapWithID(kMapRanges[i].addr,
                                    kMapRanges[i].size,
                                    kMapRanges[i].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 (i = 0; i < arraysize(kMapRanges); ++i) {
     const Range& range = kMapRanges[i];
     TestMappedRangeWithID(range,
                           GetMappedAddressFromRanges(kMapRanges,
                                                      arraysize(kMapRanges),
                                                      range.addr),
                           range.id,
                           0);
   }
 }

 // Test overlap detection.
 TEST_F(AddressMapperTest, OverlapSimple) {
   unsigned int i;
   // Map all the ranges first.
   for (i = 0; i < arraysize(kMapRanges); ++i)
     ASSERT_TRUE(MapRange(kMapRanges[i], false));

   // Attempt to re-map each range, but offset by size / 2.
   for (i = 0; i < arraysize(kMapRanges); ++i) {
     Range range;
     range.addr = kMapRanges[i].addr + kMapRanges[i].size / 2;
     range.size = kMapRanges[i].size;
     // The maps should fail because of overlap with an existing mapping.
     EXPECT_FALSE(MapRange(range, false));
   }

   // Re-map each range with the same offset.  Only this time, remove any old
   // mapped range that overlaps with it.
   for (i = 0; i < arraysize(kMapRanges); ++i) {
     Range range;
     range.addr = kMapRanges[i].addr + kMapRanges[i].size / 2;
     range.size = kMapRanges[i].size;
     EXPECT_TRUE(MapRange(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(range,
                     GetMappedAddressFromRanges(kMapRanges,
                                                arraysize(kMapRanges),
                                                kMapRanges[i].addr));
   }
 }

 // Test mapping of a giant map that overlaps with all existing ranges.
 TEST_F(AddressMapperTest, OverlapBig) {
   unsigned int i;
   // Map all the ranges first.
   for (i = 0; i < arraysize(kMapRanges); ++i)
     ASSERT_TRUE(MapRange(kMapRanges[i], false));

   // Make sure overlap is detected before removing old ranges.
   ASSERT_FALSE(MapRange(kBigRegion, false));
   ASSERT_TRUE(MapRange(kBigRegion, true));
   EXPECT_EQ(1, 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 (i = 0; i < arraysize(kAddressesNotInRanges); ++i) {
     uint64_t addr = kAddressesNotInRanges[i];
     uint64_t mapped_addr = kUint64Max;
     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 (i = 0; i < arraysize(kMapRanges); ++i) {
     const Range& range = kMapRanges[i];
     for (uint64_t addr = range.addr;
          addr < range.addr + range.size;
          addr += range.size / kNumRangeTestIntervals) {
       uint64_t mapped_addr = kUint64Max;
       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) {
   ASSERT_TRUE(MapRange(kEndRegion, true));
   EXPECT_EQ(1, mapper_->GetNumMappedRanges());
   TestMappedRange(kEndRegion, 0);
 }

 // Test mapping of an out-of-bounds mapping.
 TEST_F(AddressMapperTest, OutOfBounds) {
   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) {
   ASSERT_TRUE(MapRange(kFullRegion, false));
   int num_expected_ranges = 1;
   EXPECT_EQ(num_expected_ranges, mapper_->GetNumMappedRanges());

   TestMappedRange(kFullRegion, 0);

   // Map some smaller ranges.
   for (size_t i = 0; i < arraysize(kMapRanges); ++i) {
     const Range& range = kMapRanges[i];
     // 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, 0);
   const Range kSecondRange(0x12000, 0x1000, 1);

   // 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(MapRangeWithID(kFirstRange, true));
   ASSERT_TRUE(MapRangeWithID(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(3, mapper_->GetNumMappedRanges());

   // Now make sure the mappings are correct.

   // The first range has been split up. Define the expected ranges here.
   const Range kFirstRangeHead(kFirstRange.addr,
                               kSecondRange.addr - kFirstRange.addr,
                               kFirstRange.id);
   const Range kFirstRangeTail(kSecondRange.addr + kSecondRange.size,
                               kFirstRange.addr + kFirstRange.size -
                                   (kSecondRange.addr + kSecondRange.size),
                               kFirstRange.id,
                               kSecondRange.addr + kSecondRange.size);

   // Test the two remaining parts of the first range.
   TestMappedRangeWithID(kFirstRangeHead, 0, kFirstRangeHead.id, 0);
   TestMappedRangeWithID(kFirstRangeTail,
                         kFirstRangeTail.addr - kFirstRangeHead.addr,
                         kFirstRangeTail.id,
                         kFirstRangeTail.addr - kFirstRangeHead.addr);

   // Test the second range normally.
   TestMappedRangeWithID(kSecondRange, kSecondRange.addr - kFirstRange.addr,
                         kSecondRange.id, 0);
 }

 }  // namespace quipper

 int main(int argc, char * argv[]) {
   ::testing::InitGoogleTest(&argc, argv);
   return RUN_ALL_TESTS();
 }
	// 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 "chromiumos-wide-profiling/limits.h"
	#include "chromiumos-wide-profiling/quipper_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(kUint64Max), base_offset(0) {}

	Range(uint64_t addr, uint64_t size)
	: addr(addr), size(size), id(kUint64Max), base_offset(0) {}

	Range(uint64_t addr, uint64_t size, uint64_t id)
	: addr(addr), size(size), id(id), 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),
	Range(0x00a00000, 0x10000, 0xcafebabe),
	Range(0x0c000000, 0x1000000, 0x900df00d),
	Range(0x00001000, 0x30000, 0x9000091e),
	};

	// 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,
	};

	// A huge region that overlaps with all ranges in \|kMapRanges\|.
	const Range kBigRegion = Range(0xa00, 0xff000000);

	// A region that extends to the end of the address space.
	const Range kEndRegion = Range(0xffffffff00000000, 0x100000000);

	// A region toward the end of address space that overruns the end of the address
	// space.
	const Range kOutOfBoundsRegion = Range(0xffffffff00000000, 0x200000000);

	// A huge region that covers all of the available space.
	const Range kFullRegion = Range(0, kUint64Max);

	// Number of regularly-spaced intervals within a mapped range to test.
	const int kNumRangeTestIntervals = 8;

	// The default range ID when it is not explicitly defined during a mapping.
	const uint64_t kUndefinedRangeID = kUint64Max;

	// 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.
	// Does not specify a range ID.
	bool MapRange(const Range& range, bool remove_old_mappings) {
	LOG(INFO) << "Mapping range at " << std::hex << range.addr
	<< " with length of " << std::hex << range.size;
	return mapper_->Map(range.addr, range.size, remove_old_mappings);
	}

	// Maps a range using the AddressMapper and makes sure that it was successful.
	// Provides a specific range ID.
	bool MapRangeWithID(const Range& range, bool remove_old_mappings) {
	LOG(INFO) << "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 address mapping without checking for a particular ID.
	void TestMappedRange(const Range& range,
	const uint64_t expected_mapped_addr) {
	TestMappedRangeWithID(range, expected_mapped_addr, kUndefinedRangeID, 0);
	}

	// 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 TestMappedRangeWithID(const Range& range,
	const uint64_t expected_mapped_addr,
	const uint64_t expected_id,
	const uint64_t expected_base_offset) {
	uint64_t mapped_addr = kUint64Max;

	LOG(INFO) << "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(expected_base_offset + offset, mapped_offset);
	EXPECT_EQ(expected_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 (unsigned int i = 0; i < arraysize(kMapRanges); ++i) {
	mapper_.reset(new AddressMapper);
	const Range& range = kMapRanges[i];
	ASSERT_TRUE(MapRange(range, false));
	EXPECT_EQ(1, 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) {
	unsigned int i;
	uint64_t size_mapped = 0;
	for (i = 0; i < arraysize(kMapRanges); ++i) {
	ASSERT_TRUE(MapRange(kMapRanges[i], false));
	size_mapped += kMapRanges[i].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 (i = 0; i < arraysize(kMapRanges); ++i) {
	const Range& range = kMapRanges[i];
	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 (i = 0; i < arraysize(kAddressesNotInRanges); ++i) {
	EXPECT_FALSE(mapper_->GetMappedAddress(kAddressesNotInRanges[i],
	&mapped_addr));
	}
	}

	// Map all the ranges at once and test looking up IDs and offsets.
	TEST_F(AddressMapperTest, MapAllWithIDsAndOffsets) {
	unsigned int i;
	for (i = 0; i < arraysize(kMapRanges); ++i) {
	const Range& range = kMapRanges[i];
	LOG(INFO) << "Mapping range at " << std::hex << range.addr
	<< " with length of " << std::hex << range.size;
	ASSERT_TRUE(mapper_->MapWithID(kMapRanges[i].addr,
	kMapRanges[i].size,
	kMapRanges[i].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 (i = 0; i < arraysize(kMapRanges); ++i) {
	const Range& range = kMapRanges[i];
	TestMappedRangeWithID(range,
	GetMappedAddressFromRanges(kMapRanges,
	arraysize(kMapRanges),
	range.addr),
	range.id,
	0);
	}
	}

	// Test overlap detection.
	TEST_F(AddressMapperTest, OverlapSimple) {
	unsigned int i;
	// Map all the ranges first.
	for (i = 0; i < arraysize(kMapRanges); ++i)
	ASSERT_TRUE(MapRange(kMapRanges[i], false));

	// Attempt to re-map each range, but offset by size / 2.
	for (i = 0; i < arraysize(kMapRanges); ++i) {
	Range range;
	range.addr = kMapRanges[i].addr + kMapRanges[i].size / 2;
	range.size = kMapRanges[i].size;
	// The maps should fail because of overlap with an existing mapping.
	EXPECT_FALSE(MapRange(range, false));
	}

	// Re-map each range with the same offset. Only this time, remove any old
	// mapped range that overlaps with it.
	for (i = 0; i < arraysize(kMapRanges); ++i) {
	Range range;
	range.addr = kMapRanges[i].addr + kMapRanges[i].size / 2;
	range.size = kMapRanges[i].size;
	EXPECT_TRUE(MapRange(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(range,
	GetMappedAddressFromRanges(kMapRanges,
	arraysize(kMapRanges),
	kMapRanges[i].addr));
	}
	}

	// Test mapping of a giant map that overlaps with all existing ranges.
	TEST_F(AddressMapperTest, OverlapBig) {
	unsigned int i;
	// Map all the ranges first.
	for (i = 0; i < arraysize(kMapRanges); ++i)
	ASSERT_TRUE(MapRange(kMapRanges[i], false));

	// Make sure overlap is detected before removing old ranges.
	ASSERT_FALSE(MapRange(kBigRegion, false));
	ASSERT_TRUE(MapRange(kBigRegion, true));
	EXPECT_EQ(1, 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 (i = 0; i < arraysize(kAddressesNotInRanges); ++i) {
	uint64_t addr = kAddressesNotInRanges[i];
	uint64_t mapped_addr = kUint64Max;
	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 (i = 0; i < arraysize(kMapRanges); ++i) {
	const Range& range = kMapRanges[i];
	for (uint64_t addr = range.addr;
	addr < range.addr + range.size;
	addr += range.size / kNumRangeTestIntervals) {
	uint64_t mapped_addr = kUint64Max;
	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) {
	ASSERT_TRUE(MapRange(kEndRegion, true));
	EXPECT_EQ(1, mapper_->GetNumMappedRanges());
	TestMappedRange(kEndRegion, 0);
	}

	// Test mapping of an out-of-bounds mapping.
	TEST_F(AddressMapperTest, OutOfBounds) {
	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) {
	ASSERT_TRUE(MapRange(kFullRegion, false));
	int num_expected_ranges = 1;
	EXPECT_EQ(num_expected_ranges, mapper_->GetNumMappedRanges());

	TestMappedRange(kFullRegion, 0);

	// Map some smaller ranges.
	for (size_t i = 0; i < arraysize(kMapRanges); ++i) {
	const Range& range = kMapRanges[i];
	// 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, 0);
	const Range kSecondRange(0x12000, 0x1000, 1);

	// 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(MapRangeWithID(kFirstRange, true));
	ASSERT_TRUE(MapRangeWithID(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(3, mapper_->GetNumMappedRanges());

	// Now make sure the mappings are correct.

	// The first range has been split up. Define the expected ranges here.
	const Range kFirstRangeHead(kFirstRange.addr,
	kSecondRange.addr - kFirstRange.addr,
	kFirstRange.id);
	const Range kFirstRangeTail(kSecondRange.addr + kSecondRange.size,
	kFirstRange.addr + kFirstRange.size -
	(kSecondRange.addr + kSecondRange.size),
	kFirstRange.id,
	kSecondRange.addr + kSecondRange.size);

	// Test the two remaining parts of the first range.
	TestMappedRangeWithID(kFirstRangeHead, 0, kFirstRangeHead.id, 0);
	TestMappedRangeWithID(kFirstRangeTail,
	kFirstRangeTail.addr - kFirstRangeHead.addr,
	kFirstRangeTail.id,
	kFirstRangeTail.addr - kFirstRangeHead.addr);

	// Test the second range normally.
	TestMappedRangeWithID(kSecondRange, kSecondRange.addr - kFirstRange.addr,
	kSecondRange.id, 0);
	}

	} // namespace quipper

	int main(int argc, char * argv[]) {
	::testing::InitGoogleTest(&argc, argv);
	return RUN_ALL_TESTS();
	}