1 /**
2 * Copyright (c) 2021-2022 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include <cstdlib>
17 #include <ctime>
18 #include <climits>
19 #include <random>
20 #include "gtest/gtest.h"
21
22 #include "mem/mem.h"
23 #include "mem/mem_range.h"
24
25 namespace panda::test::mem_range {
26
27 constexpr uintptr_t MAX_PTR = std::numeric_limits<uintptr_t>::max();
28
29 constexpr uint64_t NUM_RANDOM_TESTS = 100;
30 constexpr uint64_t NUM_ITER_PER_TEST = 1000;
31 constexpr uintptr_t RANDOM_AREA_SIZE = 100000;
32
33 std::default_random_engine generator;
34 std::uniform_int_distribution<uintptr_t> distribution(0, MAX_PTR);
35
36 // support function to generate random uintptr_t
RandomUintptr()37 static uintptr_t RandomUintptr()
38 {
39 return distribution(generator);
40 }
41
42 // function to generate MemRange randomly from given range
RandomMemRange(uintptr_t min_start,uintptr_t max_end)43 static panda::mem::MemRange RandomMemRange(uintptr_t min_start, uintptr_t max_end)
44 {
45 ASSERT(max_end > min_start);
46
47 uintptr_t rand_1 = min_start + RandomUintptr() % (max_end - min_start + 1);
48 uintptr_t rand_2 = min_start + RandomUintptr() % (max_end - min_start + 1);
49
50 if (rand_1 < rand_2) {
51 return panda::mem::MemRange(rand_1, rand_2);
52 } else if (rand_1 > rand_2) {
53 return panda::mem::MemRange(rand_2, rand_1);
54 } else {
55 if (rand_1 > 0) {
56 return panda::mem::MemRange(rand_1 - 1, rand_1);
57 } else {
58 return panda::mem::MemRange(rand_1, rand_1 + 1);
59 }
60 }
61 }
62
63 // test constructor and simple methods
TEST(MemRangeTest,BasicTest)64 TEST(MemRangeTest, BasicTest)
65 {
66 constexpr uintptr_t START = 10, END = 10000;
67 constexpr uintptr_t LOWER_THAN_START = 0, HIGHER_THAN_END = 50000;
68
69 auto mem_range = panda::mem::MemRange(START, END);
70
71 // test correct start and end addresses
72 ASSERT_EQ(START, mem_range.GetStartAddress());
73 ASSERT_EQ(END, mem_range.GetEndAddress());
74
75 // test inner addresses
76 ASSERT_TRUE(mem_range.IsAddressInRange(START));
77 ASSERT_TRUE(mem_range.IsAddressInRange(END));
78 ASSERT_TRUE(mem_range.IsAddressInRange((START + END) / 2));
79
80 // test outer addresses
81 ASSERT_FALSE(mem_range.IsAddressInRange(LOWER_THAN_START));
82 ASSERT_FALSE(mem_range.IsAddressInRange(START - 1));
83 ASSERT_FALSE(mem_range.IsAddressInRange(END + 1));
84 ASSERT_FALSE(mem_range.IsAddressInRange(HIGHER_THAN_END));
85
86 // test mem_range with the same start and end
87 auto mem_range_with_one_element = panda::mem::MemRange(START, START);
88 }
89
90 // test constructor with incorrect args
TEST(MemRangeTest,AssertTest)91 TEST(MemRangeTest, AssertTest)
92 {
93 constexpr uintptr_t MIN = 10000, MAX = 50000;
94
95 ASSERT_DEBUG_DEATH(panda::mem::MemRange(MAX, MIN), "");
96 }
97
98 // test IsIntersect method
TEST(MemRangeTest,IntersectTest)99 TEST(MemRangeTest, IntersectTest)
100 {
101 constexpr uintptr_t START_1 = 10, END_1 = 100;
102 constexpr uintptr_t START_2 = 101, END_2 = 200;
103 constexpr uintptr_t START_3 = 50, END_3 = 500;
104 constexpr uintptr_t START_4 = 500, END_4 = 600;
105 constexpr uintptr_t START_5 = 10, END_5 = 100;
106
107 auto mem_range_1 = panda::mem::MemRange(START_1, END_1);
108 auto mem_range_2 = panda::mem::MemRange(START_2, END_2);
109 auto mem_range_3 = panda::mem::MemRange(START_3, END_3);
110 auto mem_range_4 = panda::mem::MemRange(START_4, END_4);
111 auto mem_range_5 = panda::mem::MemRange(START_5, END_5);
112
113 // ranges are not intersecting
114 ASSERT_FALSE(mem_range_1.IsIntersect(mem_range_2));
115 ASSERT_FALSE(mem_range_2.IsIntersect(mem_range_1));
116
117 // ranges are partly intersecting
118 ASSERT_TRUE(mem_range_1.IsIntersect(mem_range_3));
119 ASSERT_TRUE(mem_range_3.IsIntersect(mem_range_1));
120
121 // ranges are nested
122 ASSERT_TRUE(mem_range_2.IsIntersect(mem_range_3));
123 ASSERT_TRUE(mem_range_3.IsIntersect(mem_range_2));
124
125 // ranges have common bound
126 ASSERT_TRUE(mem_range_3.IsIntersect(mem_range_4));
127 ASSERT_TRUE(mem_range_4.IsIntersect(mem_range_3));
128
129 // ranges are equal
130 ASSERT_TRUE(mem_range_1.IsIntersect(mem_range_5));
131
132 // test self
133 ASSERT_TRUE(mem_range_1.IsIntersect(mem_range_1));
134 }
135
136 // function to conduct num_iter random tests with addresses in given bounds
RandomTestInBounds(uintptr_t from,uintptr_t to,uint64_t num_iter=NUM_ITER_PER_TEST)137 static void RandomTestInBounds(uintptr_t from, uintptr_t to, uint64_t num_iter = NUM_ITER_PER_TEST)
138 {
139 ASSERT(from < to);
140
141 panda::mem::MemRange mem_range_1(0, 1);
142 panda::mem::MemRange mem_range_2(0, 1);
143 // check intersection via cycle
144 for (uint64_t iter = 0; iter < num_iter; iter++) {
145 mem_range_1 = RandomMemRange(from, to);
146 mem_range_2 = RandomMemRange(from, to);
147
148 if (mem_range_1.GetStartAddress() < mem_range_2.GetStartAddress()) {
149 for (uintptr_t i = mem_range_1.GetStartAddress(); i < MAX_PTR; i++) {
150 if (i == mem_range_2.GetStartAddress()) {
151 ASSERT_TRUE(mem_range_1.IsIntersect(mem_range_2));
152 ASSERT_TRUE(mem_range_2.IsIntersect(mem_range_1));
153 break;
154 }
155 if (i == mem_range_1.GetEndAddress()) {
156 ASSERT_FALSE(mem_range_1.IsIntersect(mem_range_2));
157 ASSERT_FALSE(mem_range_2.IsIntersect(mem_range_1));
158 break;
159 }
160 }
161 } else if (mem_range_1.GetStartAddress() > mem_range_2.GetStartAddress()) {
162 for (uintptr_t i = mem_range_2.GetStartAddress(); i < MAX_PTR; i++) {
163 if (i == mem_range_1.GetStartAddress()) {
164 ASSERT_TRUE(mem_range_1.IsIntersect(mem_range_2));
165 ASSERT_TRUE(mem_range_2.IsIntersect(mem_range_1));
166 break;
167 }
168 if (i == mem_range_2.GetEndAddress()) {
169 ASSERT_FALSE(mem_range_1.IsIntersect(mem_range_2));
170 ASSERT_FALSE(mem_range_2.IsIntersect(mem_range_1));
171 break;
172 }
173 }
174 } else {
175 // case with equal start addresses
176 ASSERT_TRUE(mem_range_1.IsIntersect(mem_range_2));
177 ASSERT_TRUE(mem_range_2.IsIntersect(mem_range_1));
178 }
179 }
180 }
181
182 // set of random tests with different address ranges
183 // no bug detected during a lot of tries with different parameters
TEST(MemRangeTest,RandomIntersectTest)184 TEST(MemRangeTest, RandomIntersectTest)
185 {
186 unsigned int seed_;
187 #ifdef PANDA_NIGHTLY_TEST_ON
188 seed_ = std::time(NULL);
189 #else
190 seed_ = 0xDEADBEEF;
191 #endif
192 srand(seed_);
193 generator.seed(seed_);
194
195 // random tests in interesting ranges
196 RandomTestInBounds(0, RANDOM_AREA_SIZE);
197 RandomTestInBounds(MAX_PTR - RANDOM_AREA_SIZE, MAX_PTR);
198
199 // tests in random ranges
200 uintptr_t position;
201 for (uint64_t i = 0; i < NUM_RANDOM_TESTS; i++) {
202 position = RandomUintptr();
203 if (position > RANDOM_AREA_SIZE) {
204 RandomTestInBounds(position - RANDOM_AREA_SIZE, position);
205 } else {
206 RandomTestInBounds(position, position + RANDOM_AREA_SIZE);
207 }
208 }
209 }
210
211 } // namespace panda::test::mem_range
212