/*
|
* Copyright (C) 2019 The Android Open Source Project
|
*
|
* Licensed under the Apache License, Version 2.0 (the "License");
|
* you may not use this file except in compliance with the License.
|
* You may obtain a copy of the License at
|
*
|
* http://www.apache.org/licenses/LICENSE-2.0
|
*
|
* Unless required by applicable law or agreed to in writing, software
|
* distributed under the License is distributed on an "AS IS" BASIS,
|
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
* See the License for the specific language governing permissions and
|
* limitations under the License.
|
*/
|
|
#include "memory_type_table.h"
|
|
#include <limits>
|
|
#include <gtest/gtest.h>
|
|
namespace art {
|
|
TEST(memory_type_range, range) {
|
MemoryTypeRange<int> r(0x1000u, 0x2000u, 42);
|
EXPECT_EQ(r.Start(), 0x1000u);
|
EXPECT_EQ(r.Limit(), 0x2000u);
|
EXPECT_EQ(r.Type(), 42);
|
}
|
|
TEST(memory_type_range, range_contains) {
|
MemoryTypeRange<int> r(0x1000u, 0x2000u, 42);
|
EXPECT_FALSE(r.Contains(0x0fffu));
|
EXPECT_TRUE(r.Contains(0x1000u));
|
EXPECT_TRUE(r.Contains(0x1fffu));
|
EXPECT_FALSE(r.Contains(0x2000u));
|
}
|
|
TEST(memory_type_range, range_overlaps) {
|
static const int kMemoryType = 42;
|
MemoryTypeRange<int> a(0x1000u, 0x2000u, kMemoryType);
|
|
{
|
// |<----- a ----->|<----- b ----->|
|
MemoryTypeRange<int> b(a.Limit(), a.Limit() + a.Size(), kMemoryType);
|
EXPECT_FALSE(a.Overlaps(b));
|
EXPECT_FALSE(b.Overlaps(a));
|
}
|
|
{
|
// |<----- a ----->| |<----- c ----->|
|
MemoryTypeRange<int> c(a.Limit() + a.Size(), a.Limit() + 2 * a.Size(), kMemoryType);
|
EXPECT_FALSE(a.Overlaps(c));
|
EXPECT_FALSE(c.Overlaps(a));
|
}
|
|
{
|
// |<----- a ----->|
|
// |<- d ->|
|
MemoryTypeRange<int> d(a.Start() + a.Size() / 4, a.Limit() - a.Size() / 4, kMemoryType);
|
EXPECT_TRUE(a.Overlaps(d));
|
EXPECT_TRUE(d.Overlaps(a));
|
}
|
|
{
|
// |<----- a ----->|
|
// |<- e ->|
|
MemoryTypeRange<int> e(a.Start(), a.Start() + a.Size() / 2, kMemoryType);
|
EXPECT_TRUE(a.Overlaps(e));
|
EXPECT_TRUE(e.Overlaps(a));
|
}
|
|
{
|
// |<----- a ----->|
|
// |<- f ->|
|
MemoryTypeRange<int> f(a.Start() + a.Size() / 2, a.Limit(), kMemoryType);
|
EXPECT_TRUE(a.Overlaps(f));
|
EXPECT_TRUE(f.Overlaps(a));
|
}
|
|
{
|
// |<----- a ----->|
|
// |<----- g ----->|
|
MemoryTypeRange<int> g(a.Start() + a.Size() / 2, a.Limit() + a.Size() / 2, kMemoryType);
|
EXPECT_TRUE(a.Overlaps(g));
|
EXPECT_TRUE(g.Overlaps(a));
|
}
|
}
|
|
TEST(memory_type_range, range_adjoins) {
|
static const int kMemoryType = 42;
|
MemoryTypeRange<int> a(0x1000u, 0x2000u, kMemoryType);
|
|
{
|
// |<--- a --->|<--- b --->|
|
MemoryTypeRange<int> b(a.Limit(), a.Limit() + a.Size(), kMemoryType);
|
EXPECT_TRUE(a.Adjoins(b));
|
EXPECT_TRUE(b.Adjoins(a));
|
}
|
|
{
|
// |<--- a --->| |<--- c --->|
|
MemoryTypeRange<int> c(a.Limit() + a.Size(), a.Limit() + 2 * a.Size(), kMemoryType);
|
EXPECT_FALSE(a.Adjoins(c));
|
EXPECT_FALSE(c.Adjoins(a));
|
}
|
|
{
|
// |<--- a --->|
|
// |<--- d --->|
|
MemoryTypeRange<int> d(a.Start() + a.Size() / 2, a.Limit() + a.Size() / 2, kMemoryType);
|
EXPECT_FALSE(a.Adjoins(d));
|
EXPECT_FALSE(d.Adjoins(a));
|
}
|
}
|
|
TEST(memory_type_range, combinable_with) {
|
// Adjoining ranges of same type.
|
EXPECT_TRUE(MemoryTypeRange<int>(0x1000, 0x2000, 0)
|
.CombinableWith(MemoryTypeRange<int>(0x800, 0x1000, 0)));
|
EXPECT_TRUE(MemoryTypeRange<int>(0x800, 0x1000, 0)
|
.CombinableWith(MemoryTypeRange<int>(0x1000, 0x2000, 0)));
|
// Adjoining ranges of different types.
|
EXPECT_FALSE(MemoryTypeRange<int>(0x1000, 0x2000, 0)
|
.CombinableWith(MemoryTypeRange<int>(0x800, 0x1000, 1)));
|
EXPECT_FALSE(MemoryTypeRange<int>(0x800, 0x1000, 1)
|
.CombinableWith(MemoryTypeRange<int>(0x1000, 0x2000, 0)));
|
// Disjoint ranges.
|
EXPECT_FALSE(MemoryTypeRange<int>(0x0800, 0x1000, 0)
|
.CombinableWith(MemoryTypeRange<int>(0x1f00, 0x2000, 0)));
|
EXPECT_FALSE(MemoryTypeRange<int>(0x1f00, 0x2000, 0)
|
.CombinableWith(MemoryTypeRange<int>(0x800, 0x1000, 0)));
|
// Overlapping ranges.
|
EXPECT_FALSE(MemoryTypeRange<int>(0x0800, 0x2000, 0)
|
.CombinableWith(MemoryTypeRange<int>(0x1f00, 0x2000, 0)));
|
}
|
|
TEST(memory_type_range, is_valid) {
|
EXPECT_TRUE(MemoryTypeRange<int>(std::numeric_limits<uintptr_t>::min(),
|
std::numeric_limits<uintptr_t>::max(),
|
0).IsValid());
|
EXPECT_TRUE(MemoryTypeRange<int>(1u, 2u, 0).IsValid());
|
EXPECT_TRUE(MemoryTypeRange<int>(0u, 0u, 0).IsValid());
|
EXPECT_FALSE(MemoryTypeRange<int>(2u, 1u, 0).IsValid());
|
EXPECT_FALSE(MemoryTypeRange<int>(std::numeric_limits<uintptr_t>::max(),
|
std::numeric_limits<uintptr_t>::min(),
|
0).IsValid());
|
}
|
|
TEST(memory_type_range, range_equality) {
|
static const int kMemoryType = 42;
|
MemoryTypeRange<int> a(0x1000u, 0x2000u, kMemoryType);
|
|
MemoryTypeRange<int> b(a.Start(), a.Limit(), a.Type());
|
EXPECT_TRUE(a == b);
|
EXPECT_FALSE(a != b);
|
|
MemoryTypeRange<int> c(a.Start() + 1, a.Limit(), a.Type());
|
EXPECT_FALSE(a == c);
|
EXPECT_TRUE(a != c);
|
|
MemoryTypeRange<int> d(a.Start(), a.Limit() + 1, a.Type());
|
EXPECT_FALSE(a == d);
|
EXPECT_TRUE(a != d);
|
|
MemoryTypeRange<int> e(a.Start(), a.Limit(), a.Type() + 1);
|
EXPECT_FALSE(a == e);
|
EXPECT_TRUE(a != e);
|
}
|
|
TEST(memory_type_table_builder, add_lookup) {
|
MemoryTypeTable<int>::Builder builder;
|
MemoryTypeRange<int> range(0x1000u, 0x2000u, 0);
|
EXPECT_EQ(builder.Size(), 0u);
|
EXPECT_EQ(builder.Add(range), true);
|
EXPECT_EQ(builder.Lookup(range.Start() - 1u), nullptr);
|
EXPECT_EQ(builder.Size(), 1u);
|
|
const MemoryTypeRange<int>* first = builder.Lookup(range.Start());
|
ASSERT_TRUE(first != nullptr);
|
EXPECT_EQ(range, *first);
|
|
const MemoryTypeRange<int>* last = builder.Lookup(range.Limit() - 1u);
|
ASSERT_TRUE(last != nullptr);
|
EXPECT_EQ(range, *last);
|
|
EXPECT_EQ(builder.Lookup(range.Limit()), nullptr);
|
}
|
|
TEST(memory_type_table_builder, add_lookup_multi) {
|
MemoryTypeTable<char>::Builder builder;
|
MemoryTypeRange<char> ranges[3] = {
|
MemoryTypeRange<char>(0x1, 0x2, 'a'),
|
MemoryTypeRange<char>(0x2, 0x4, 'b'),
|
MemoryTypeRange<char>(0x4, 0x8, 'c'),
|
};
|
|
for (const auto& range : ranges) {
|
builder.Add(range);
|
}
|
|
ASSERT_EQ(builder.Size(), sizeof(ranges) / sizeof(ranges[0]));
|
ASSERT_TRUE(builder.Lookup(0x0) == nullptr);
|
ASSERT_TRUE(builder.Lookup(0x8) == nullptr);
|
for (const auto& range : ranges) {
|
auto first = builder.Lookup(range.Start());
|
ASSERT_TRUE(first != nullptr);
|
EXPECT_EQ(*first, range);
|
|
auto last = builder.Lookup(range.Limit() - 1);
|
ASSERT_TRUE(last != nullptr);
|
EXPECT_EQ(*last, range);
|
}
|
}
|
|
TEST(memory_type_table_builder, add_overlapping) {
|
MemoryTypeTable<int>::Builder builder;
|
MemoryTypeRange<int> range(0x1000u, 0x2000u, 0);
|
builder.Add(range);
|
EXPECT_EQ(builder.Size(), 1u);
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x0800u, 0x2800u, 0)));
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x0800u, 0x1800u, 0)));
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x1800u, 0x2800u, 0)));
|
EXPECT_EQ(builder.Size(), 1u);
|
}
|
|
TEST(memory_type_table_builder, add_zero_size) {
|
MemoryTypeTable<int>::Builder builder;
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x1000u, 0x1000u, 0)));
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x1000u, 0x1001u, 0)));
|
// Checking adjoining zero length don't get included
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x1000u, 0x1000u, 0)));
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x1001u, 0x1001u, 0)));
|
// Check around extremes
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x0u, 0x0u, 0)));
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(~0u, ~0u, 0)));
|
}
|
|
TEST(memory_type_table_builder, add_invalid_range) {
|
MemoryTypeTable<int>::Builder builder;
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x1000u, 0x1000u, 0)));
|
EXPECT_FALSE(builder.Add(MemoryTypeRange<int>(0x2000u, 0x1000u, 0)));
|
}
|
|
TEST(memory_type_table_builder, add_adjoining) {
|
MemoryTypeTable<int>::Builder builder;
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x1000u, 0x2000u, 0)));
|
EXPECT_EQ(builder.Size(), 1u);
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x0800u, 0x1000u, 0)));
|
EXPECT_EQ(builder.Size(), 1u);
|
ASSERT_NE(builder.Lookup(0x0900u), nullptr);
|
EXPECT_EQ(builder.Lookup(0x0900u)->Start(), 0x0800u);
|
EXPECT_EQ(builder.Lookup(0x0900u)->Limit(), 0x2000u);
|
EXPECT_EQ(builder.Lookup(0x0900u)->Type(), 0);
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x2000u, 0x2100u, 0)));
|
EXPECT_EQ(builder.Size(), 1u);
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x3000u, 0x3100u, 0)));
|
EXPECT_EQ(builder.Size(), 2u);
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x2100u, 0x3000u, 0)));
|
ASSERT_NE(builder.Lookup(0x2000u), nullptr);
|
EXPECT_EQ(builder.Lookup(0x2000u)->Start(), 0x0800u);
|
EXPECT_EQ(builder.Lookup(0x2000u)->Limit(), 0x3100u);
|
EXPECT_EQ(builder.Lookup(0x2000u)->Type(), 0);
|
EXPECT_EQ(builder.Size(), 1u);
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x4000u, 0x4100u, 0)));
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x4f00u, 0x5000u, 0)));
|
EXPECT_EQ(builder.Size(), 3u);
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x4100u, 0x4f00u, 0)));
|
ASSERT_NE(builder.Lookup(0x4f00u), nullptr);
|
ASSERT_EQ(builder.Lookup(0x4f00u)->Start(), 0x4000u);
|
ASSERT_EQ(builder.Lookup(0x4f00u)->Limit(), 0x5000u);
|
ASSERT_EQ(builder.Lookup(0x4f00u)->Type(), 0);
|
EXPECT_EQ(builder.Size(), 2u);
|
ASSERT_NE(builder.Lookup(0x4f00u), nullptr);
|
}
|
|
TEST(memory_type_table_builder, add_adjoining_different_type) {
|
MemoryTypeTable<int>::Builder builder;
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x0000u, 0x1000u, 1)));
|
EXPECT_EQ(builder.Size(), 1u);
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x1000u, 0x2000u, 2)));
|
EXPECT_EQ(builder.Size(), 2u);
|
EXPECT_TRUE(builder.Add(MemoryTypeRange<int>(0x2000u, 0x3000u, 3)));
|
EXPECT_EQ(builder.Size(), 3u);
|
}
|
|
TEST(memory_type_table, create) {
|
MemoryTypeTable<int>::Builder builder;
|
builder.Add(MemoryTypeRange<int>(0x1000u, 0x2000u, 0));
|
builder.Add(MemoryTypeRange<int>(0x2000u, 0x3000u, 1));
|
builder.Add(MemoryTypeRange<int>(0x4000u, 0x5000u, 2));
|
|
MemoryTypeTable<int> table = builder.Build();
|
EXPECT_TRUE(table.Lookup(0x0000u) == nullptr);
|
EXPECT_TRUE(table.Lookup(0x0800u) == nullptr);
|
EXPECT_TRUE(table.Lookup(0x3000u) == nullptr);
|
EXPECT_TRUE(table.Lookup(0x3fffu) == nullptr);
|
EXPECT_TRUE(table.Lookup(0x5000u) == nullptr);
|
EXPECT_TRUE(table.Lookup(~0u) == nullptr);
|
|
ASSERT_TRUE(table.Lookup(0x1000u) != nullptr);
|
ASSERT_TRUE(table.Lookup(0x1fffu) != nullptr);
|
EXPECT_EQ(*table.Lookup(0x1000u), MemoryTypeRange<int>(0x1000u, 0x2000u, 0));
|
EXPECT_EQ(*table.Lookup(0x1fffu), MemoryTypeRange<int>(0x1000u, 0x2000u, 0));
|
ASSERT_TRUE(table.Lookup(0x2000u) != nullptr);
|
ASSERT_TRUE(table.Lookup(0x2fffu) != nullptr);
|
EXPECT_EQ(*table.Lookup(0x2000u), MemoryTypeRange<int>(0x2000u, 0x3000u, 1));
|
EXPECT_EQ(*table.Lookup(0x2fffu), MemoryTypeRange<int>(0x2000u, 0x3000u, 1));
|
ASSERT_TRUE(table.Lookup(0x4000u) != nullptr);
|
ASSERT_TRUE(table.Lookup(0x4fffu) != nullptr);
|
EXPECT_EQ(*table.Lookup(0x4000u), MemoryTypeRange<int>(0x4000u, 0x5000u, 2));
|
EXPECT_EQ(*table.Lookup(0x4fffu), MemoryTypeRange<int>(0x4000u, 0x5000u, 2));
|
}
|
|
TEST(memory_type_table, find_all) {
|
static constexpr size_t kRangeCount = 64;
|
static constexpr uintptr_t kRangeSize = 1024;
|
|
MemoryTypeTable<int>::Builder builder;
|
for (size_t i = 0; i < kRangeCount; i++) {
|
const uintptr_t start = i * kRangeSize;
|
builder.Add(MemoryTypeRange<int>(start, start + kRangeSize, static_cast<int>(i)));
|
}
|
|
for (size_t delta = 0; delta < kRangeSize; delta += kRangeSize / 2) {
|
for (size_t i = 0; i < kRangeCount; i++) {
|
const uintptr_t start = i * kRangeSize;
|
const MemoryTypeRange<int> expected(start, start + kRangeSize, static_cast<int>(i));
|
const uintptr_t address = i * kRangeSize + delta;
|
const MemoryTypeRange<int>* actual = builder.Lookup(address);
|
ASSERT_TRUE(actual != nullptr) << reinterpret_cast<void*>(address);
|
EXPECT_EQ(expected, *actual) << reinterpret_cast<void*>(address);
|
}
|
}
|
|
MemoryTypeTable<int> table = builder.Build();
|
for (size_t delta = 0; delta < kRangeSize; delta += kRangeSize / 2) {
|
for (size_t i = 0; i < kRangeCount; i++) {
|
const uintptr_t start = i * kRangeSize;
|
const MemoryTypeRange<int> expected(start, start + kRangeSize, static_cast<int>(i));
|
const uintptr_t address = i * kRangeSize + delta;
|
const MemoryTypeRange<int>* actual = table.Lookup(address);
|
ASSERT_TRUE(actual != nullptr) << reinterpret_cast<void*>(address);
|
EXPECT_EQ(expected, *actual) << reinterpret_cast<void*>(address);
|
}
|
}
|
}
|
|
} // namespace art
|
