/*
* 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