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 } 235