| 1 |
//===- llvm/unittest/Support/AddresRangeTest.cpp --------------------------===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
|
| 9 |
#include "llvm/ADT/AddressRanges.h" |
| 10 |
#include "llvm/Testing/Support/Error.h" |
| 11 |
|
| 12 |
#include "gmock/gmock.h" |
| 13 |
#include "gtest/gtest.h" |
| 14 |
#include <string> |
| 15 |
|
| 16 |
using namespace llvm; |
| 17 |
|
| 18 |
TEST(AddressRangeTest, TestRanges) { |
| 19 |
// test llvm::AddressRange. |
| 20 |
const uint64_t StartAddr = 0x1000; |
| 21 |
const uint64_t EndAddr = 0x2000; |
| 22 |
// Verify constructor and API to ensure it takes start and end address. |
| 23 |
const AddressRange Range(StartAddr, EndAddr); |
| 24 |
EXPECT_EQ(Range.size(), EndAddr - StartAddr); |
| 25 |
|
| 26 |
// Verify llvm::AddressRange::contains(). |
| 27 |
EXPECT_FALSE(Range.contains(0)); |
| 28 |
EXPECT_FALSE(Range.contains(StartAddr - 1)); |
| 29 |
EXPECT_TRUE(Range.contains(StartAddr)); |
| 30 |
EXPECT_TRUE(Range.contains(EndAddr - 1)); |
| 31 |
EXPECT_FALSE(Range.contains(EndAddr)); |
| 32 |
EXPECT_FALSE(Range.contains(UINT64_MAX)); |
| 33 |
|
| 34 |
const AddressRange RangeSame(StartAddr, EndAddr); |
| 35 |
const AddressRange RangeDifferentStart(StartAddr + 1, EndAddr); |
| 36 |
const AddressRange RangeDifferentEnd(StartAddr, EndAddr + 1); |
| 37 |
const AddressRange RangeDifferentStartEnd(StartAddr + 1, EndAddr + 1); |
| 38 |
// Test == and != with values that are the same |
| 39 |
EXPECT_EQ(Range, RangeSame); |
| 40 |
EXPECT_FALSE(Range != RangeSame); |
| 41 |
// Test == and != with values that are the different |
| 42 |
EXPECT_NE(Range, RangeDifferentStart); |
| 43 |
EXPECT_NE(Range, RangeDifferentEnd); |
| 44 |
EXPECT_NE(Range, RangeDifferentStartEnd); |
| 45 |
EXPECT_FALSE(Range == RangeDifferentStart); |
| 46 |
EXPECT_FALSE(Range == RangeDifferentEnd); |
| 47 |
EXPECT_FALSE(Range == RangeDifferentStartEnd); |
| 48 |
|
| 49 |
// Test "bool operator<(const AddressRange &, const AddressRange &)". |
| 50 |
EXPECT_FALSE(Range < RangeSame); |
| 51 |
EXPECT_FALSE(RangeSame < Range); |
| 52 |
EXPECT_LT(Range, RangeDifferentStart); |
| 53 |
EXPECT_LT(Range, RangeDifferentEnd); |
| 54 |
EXPECT_LT(Range, RangeDifferentStartEnd); |
| 55 |
// Test "bool operator<(const AddressRange &, uint64_t)" |
| 56 |
EXPECT_LT(Range.start(), StartAddr + 1); |
| 57 |
// Test "bool operator<(uint64_t, const AddressRange &)" |
| 58 |
EXPECT_LT(StartAddr - 1, Range.start()); |
| 59 |
|
| 60 |
// Verify llvm::AddressRange::isContiguousWith() and |
| 61 |
// llvm::AddressRange::intersects(). |
| 62 |
const AddressRange EndsBeforeRangeStart(0, StartAddr - 1); |
| 63 |
const AddressRange EndsAtRangeStart(0, StartAddr); |
| 64 |
const AddressRange OverlapsRangeStart(StartAddr - 1, StartAddr + 1); |
| 65 |
const AddressRange InsideRange(StartAddr + 1, EndAddr - 1); |
| 66 |
const AddressRange OverlapsRangeEnd(EndAddr - 1, EndAddr + 1); |
| 67 |
const AddressRange StartsAtRangeEnd(EndAddr, EndAddr + 0x100); |
| 68 |
const AddressRange StartsAfterRangeEnd(EndAddr + 1, EndAddr + 0x100); |
| 69 |
|
| 70 |
EXPECT_FALSE(Range.intersects(EndsBeforeRangeStart)); |
| 71 |
EXPECT_FALSE(Range.intersects(EndsAtRangeStart)); |
| 72 |
EXPECT_TRUE(Range.intersects(OverlapsRangeStart)); |
| 73 |
EXPECT_TRUE(Range.intersects(InsideRange)); |
| 74 |
EXPECT_TRUE(Range.intersects(OverlapsRangeEnd)); |
| 75 |
EXPECT_FALSE(Range.intersects(StartsAtRangeEnd)); |
| 76 |
EXPECT_FALSE(Range.intersects(StartsAfterRangeEnd)); |
| 77 |
|
| 78 |
// Test the functions that maintain address ranges: |
| 79 |
// "bool AddressRange::contains(uint64_t Addr) const;" |
| 80 |
// "void AddressRanges::insert(const AddressRange &R);" |
| 81 |
AddressRanges Ranges; |
| 82 |
Ranges.insert(AddressRange(0x1000, 0x2000)); |
| 83 |
Ranges.insert(AddressRange(0x2000, 0x3000)); |
| 84 |
Ranges.insert(AddressRange(0x4000, 0x5000)); |
| 85 |
|
| 86 |
EXPECT_FALSE(Ranges.contains(0)); |
| 87 |
EXPECT_FALSE(Ranges.contains(0x1000 - 1)); |
| 88 |
EXPECT_TRUE(Ranges.contains(0x1000)); |
| 89 |
EXPECT_TRUE(Ranges.contains(0x2000)); |
| 90 |
EXPECT_TRUE(Ranges.contains(0x4000)); |
| 91 |
EXPECT_TRUE(Ranges.contains(0x2000 - 1)); |
| 92 |
EXPECT_TRUE(Ranges.contains(0x3000 - 1)); |
| 93 |
EXPECT_FALSE(Ranges.contains(0x3000 + 1)); |
| 94 |
EXPECT_TRUE(Ranges.contains(0x5000 - 1)); |
| 95 |
EXPECT_FALSE(Ranges.contains(0x5000 + 1)); |
| 96 |
EXPECT_FALSE(Ranges.contains(UINT64_MAX)); |
| 97 |
|
| 98 |
EXPECT_FALSE(Ranges.contains(AddressRange())); |
| 99 |
EXPECT_FALSE(Ranges.contains(AddressRange(0x1000 - 1, 0x1000))); |
| 100 |
EXPECT_FALSE(Ranges.contains(AddressRange(0x1000, 0x1000))); |
| 101 |
EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x1000 + 1))); |
| 102 |
EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000))); |
| 103 |
EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2001))); |
| 104 |
EXPECT_TRUE(Ranges.contains(AddressRange(0x2000, 0x3000))); |
| 105 |
EXPECT_FALSE(Ranges.contains(AddressRange(0x2000, 0x3001))); |
| 106 |
EXPECT_FALSE(Ranges.contains(AddressRange(0x3000, 0x3001))); |
| 107 |
EXPECT_FALSE(Ranges.contains(AddressRange(0x1500, 0x4500))); |
| 108 |
EXPECT_FALSE(Ranges.contains(AddressRange(0x5000, 0x5001))); |
| 109 |
|
| 110 |
// Verify that intersecting ranges get combined |
| 111 |
Ranges.clear(); |
| 112 |
Ranges.insert(AddressRange(0x1100, 0x1F00)); |
| 113 |
// Verify a wholy contained range that is added doesn't do anything. |
| 114 |
Ranges.insert(AddressRange(0x1500, 0x1F00)); |
| 115 |
EXPECT_EQ(Ranges.size(), 1u); |
| 116 |
EXPECT_EQ(Ranges[0], AddressRange(0x1100, 0x1F00)); |
| 117 |
|
| 118 |
// Verify a range that starts before and intersects gets combined. |
| 119 |
Ranges.insert(AddressRange(0x1000, Ranges[0].start() + 1)); |
| 120 |
EXPECT_EQ(Ranges.size(), 1u); |
| 121 |
EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x1F00)); |
| 122 |
|
| 123 |
// Verify a range that starts inside and extends ranges gets combined. |
| 124 |
Ranges.insert(AddressRange(Ranges[0].end() - 1, 0x2000)); |
| 125 |
EXPECT_EQ(Ranges.size(), 1u); |
| 126 |
EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000)); |
| 127 |
|
| 128 |
// Verify that adjacent ranges get combined |
| 129 |
Ranges.insert(AddressRange(0x2000, 0x2fff)); |
| 130 |
EXPECT_EQ(Ranges.size(), 1u); |
| 131 |
EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2fff)); |
| 132 |
|
| 133 |
// Verify that ranges having 1 byte gap do not get combined |
| 134 |
Ranges.insert(AddressRange(0x3000, 0x4000)); |
| 135 |
EXPECT_EQ(Ranges.size(), 2u); |
| 136 |
EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2fff)); |
| 137 |
EXPECT_EQ(Ranges[1], AddressRange(0x3000, 0x4000)); |
| 138 |
|
| 139 |
// Verify if we add an address range that intersects two ranges |
| 140 |
// that they get combined |
| 141 |
Ranges.insert(AddressRange(Ranges[0].end() - 1, Ranges[1].start() + 1)); |
| 142 |
EXPECT_EQ(Ranges.size(), 1u); |
| 143 |
EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x4000)); |
| 144 |
|
| 145 |
Ranges.insert(AddressRange(0x3000, 0x4000)); |
| 146 |
Ranges.insert(AddressRange(0x4000, 0x5000)); |
| 147 |
Ranges.insert(AddressRange(0x2000, 0x4500)); |
| 148 |
EXPECT_EQ(Ranges.size(), 1u); |
| 149 |
EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x5000)); |
| 150 |
} |
| 151 |
|
| 152 |
TEST(AddressRangeTest, TestRangesMap) { |
| 153 |
AddressRangesMap<int> Ranges; |
| 154 |
|
| 155 |
EXPECT_EQ(Ranges.size(), 0u); |
| 156 |
EXPECT_TRUE(Ranges.empty()); |
| 157 |
|
| 158 |
// Add single range. |
| 159 |
Ranges.insert(AddressRange(0x1000, 0x2000), 0xfe); |
| 160 |
EXPECT_EQ(Ranges.size(), 1u); |
| 161 |
EXPECT_FALSE(Ranges.empty()); |
| 162 |
EXPECT_TRUE(Ranges.contains(0x1500)); |
| 163 |
EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000))); |
| 164 |
|
| 165 |
// Clear ranges. |
| 166 |
Ranges.clear(); |
| 167 |
EXPECT_EQ(Ranges.size(), 0u); |
| 168 |
EXPECT_TRUE(Ranges.empty()); |
| 169 |
|
| 170 |
// Add range and check value. |
| 171 |
Ranges.insert(AddressRange(0x1000, 0x2000), 0xfe); |
| 172 |
EXPECT_EQ(Ranges.size(), 1u); |
| 173 |
EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xfe); |
| 174 |
|
| 175 |
// Add adjacent range and check value. |
| 176 |
Ranges.insert(AddressRange(0x2000, 0x3000), 0xfc); |
| 177 |
EXPECT_EQ(Ranges.size(), 1u); |
| 178 |
EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xfc); |
| 179 |
EXPECT_EQ(Ranges.getRangeValueThatContains(0x2000)->second, 0xfc); |
| 180 |
EXPECT_EQ(Ranges.getRangeValueThatContains(0x2900)->second, 0xfc); |
| 181 |
EXPECT_FALSE(Ranges.getRangeValueThatContains(0x3000)); |
| 182 |
|
| 183 |
// Add intersecting range and check value. |
| 184 |
Ranges.insert(AddressRange(0x2000, 0x3000), 0xff); |
| 185 |
EXPECT_EQ(Ranges.size(), 1u); |
| 186 |
EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xff); |
| 187 |
|
| 188 |
// Add second range and check values. |
| 189 |
Ranges.insert(AddressRange(0x4000, 0x5000), 0x0); |
| 190 |
EXPECT_EQ(Ranges.size(), 2u); |
| 191 |
EXPECT_EQ(Ranges[0].second, 0xff); |
| 192 |
EXPECT_EQ(Ranges[1].second, 0x0); |
| 193 |
EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xff); |
| 194 |
EXPECT_EQ(Ranges.getRangeValueThatContains(0x4000)->second, 0x0); |
| 195 |
|
| 196 |
// Add intersecting range and check value. |
| 197 |
Ranges.insert(AddressRange(0x0, 0x6000), 0x1); |
| 198 |
EXPECT_EQ(Ranges.size(), 1u); |
| 199 |
EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0x1); |
| 200 |
|
| 201 |
// Check that values are correctly preserved for combined ranges. |
| 202 |
Ranges.clear(); |
| 203 |
Ranges.insert(AddressRange(0x0, 0xff), 0x1); |
| 204 |
Ranges.insert(AddressRange(0x100, 0x1ff), 0x2); |
| 205 |
Ranges.insert(AddressRange(0x200, 0x2ff), 0x3); |
| 206 |
Ranges.insert(AddressRange(0x300, 0x3ff), 0x4); |
| 207 |
Ranges.insert(AddressRange(0x400, 0x4ff), 0x5); |
| 208 |
Ranges.insert(AddressRange(0x500, 0x5ff), 0x6); |
| 209 |
Ranges.insert(AddressRange(0x600, 0x6ff), 0x7); |
| 210 |
|
| 211 |
Ranges.insert(AddressRange(0x150, 0x350), 0xff); |
| 212 |
EXPECT_EQ(Ranges.size(), 5u); |
| 213 |
EXPECT_EQ(Ranges[0].first, AddressRange(0x0, 0xff)); |
| 214 |
EXPECT_EQ(Ranges[0].second, 0x1); |
| 215 |
EXPECT_EQ(Ranges[1].first, AddressRange(0x100, 0x3ff)); |
| 216 |
EXPECT_EQ(Ranges[1].second, 0xff); |
| 217 |
EXPECT_EQ(Ranges[2].first, AddressRange(0x400, 0x4ff)); |
| 218 |
EXPECT_EQ(Ranges[2].second, 0x5); |
| 219 |
EXPECT_EQ(Ranges[3].first, AddressRange(0x500, 0x5ff)); |
| 220 |
EXPECT_EQ(Ranges[3].second, 0x6); |
| 221 |
EXPECT_EQ(Ranges[4].first, AddressRange(0x600, 0x6ff)); |
| 222 |
EXPECT_EQ(Ranges[4].second, 0x7); |
| 223 |
|
| 224 |
Ranges.insert(AddressRange(0x3ff, 0x400), 0x5); |
| 225 |
EXPECT_EQ(Ranges.size(), 4u); |
| 226 |
EXPECT_EQ(Ranges[0].first, AddressRange(0x0, 0xff)); |
| 227 |
EXPECT_EQ(Ranges[0].second, 0x1); |
| 228 |
EXPECT_EQ(Ranges[1].first, AddressRange(0x100, 0x4ff)); |
| 229 |
EXPECT_EQ(Ranges[1].second, 0x5); |
| 230 |
EXPECT_EQ(Ranges[2].first, AddressRange(0x500, 0x5ff)); |
| 231 |
EXPECT_EQ(Ranges[2].second, 0x6); |
| 232 |
EXPECT_EQ(Ranges[3].first, AddressRange(0x600, 0x6ff)); |
| 233 |
EXPECT_EQ(Ranges[3].second, 0x7); |
| 234 |
} |