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