1 /*
2 * Copyright (C) 2025 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "gmock/gmock.h"
18 #include "gtest/gtest.h"
19
20 #include "berberis/runtime_primitives/guest_code_region.h"
21
22 namespace berberis {
23
24 namespace {
25
26 using testing::ElementsAre;
27
TEST(GuestCodeRegion,Smoke)28 TEST(GuestCodeRegion, Smoke) {
29 Arena arena;
30 GuestCodeRegion region(&arena);
31
32 EXPECT_TRUE(region.branch_targets().empty());
33
34 {
35 // 42 - 50 ->{8, 100}
36 auto* bb = region.NewBasicBlock(42, 8, ArenaVector<GuestAddr>({8, 100}, &arena));
37 EXPECT_EQ(bb->start_addr(), 42u);
38 EXPECT_EQ(bb->size(), 8u);
39 EXPECT_EQ(bb->end_addr(), 50u);
40 EXPECT_THAT(bb->out_edges(), ElementsAre(8, 100));
41 EXPECT_TRUE(bb->in_edges().empty());
42 }
43
44 EXPECT_THAT(region.branch_targets(), ElementsAre(8, 100));
45
46 {
47 // 56 - 60 -> {42, 120}
48 auto* bb = region.NewBasicBlock(56, 4, ArenaVector<GuestAddr>({42, 50}, &arena));
49 EXPECT_EQ(bb->start_addr(), 56u);
50 EXPECT_EQ(bb->size(), 4u);
51 EXPECT_EQ(bb->end_addr(), 60u);
52 EXPECT_THAT(bb->out_edges(), ElementsAre(42, 50));
53 EXPECT_TRUE(bb->in_edges().empty());
54 }
55
56 EXPECT_THAT(region.branch_targets(), ElementsAre(8, 42, 50, 100));
57
58 region.ResolveEdges();
59
60 auto& basic_blocks = region.basic_blocks();
61
62 EXPECT_EQ(basic_blocks.size(), 2u);
63
64 ASSERT_TRUE(basic_blocks.contains(42));
65 ASSERT_TRUE(basic_blocks.contains(56));
66
67 {
68 auto& bb = basic_blocks.at(42);
69 EXPECT_THAT(bb.in_edges(), ElementsAre(56));
70 }
71
72 {
73 auto& bb = basic_blocks.at(56);
74 EXPECT_TRUE(bb.in_edges().empty());
75 }
76 }
77
TEST(GuestCodeRegion,ResolveEdges)78 TEST(GuestCodeRegion, ResolveEdges) {
79 Arena arena;
80 GuestCodeRegion region(&arena);
81
82 // 42 - 54
83 region.NewBasicBlock(42, 12, ArenaVector<GuestAddr>({100, 150, 200}, &arena));
84
85 EXPECT_THAT(region.branch_targets(), ElementsAre(100, 150, 200));
86
87 // 100 - 120
88 region.NewBasicBlock(100, 20, ArenaVector<GuestAddr>({8, 200, 1000}, &arena));
89
90 EXPECT_THAT(region.branch_targets(), ElementsAre(8, 100, 150, 200, 1000));
91
92 // 200 - 240
93 region.NewBasicBlock(200, 40, ArenaVector<GuestAddr>({80, 120}, &arena));
94
95 EXPECT_THAT(region.branch_targets(), ElementsAre(8, 80, 100, 120, 150, 200, 1000));
96
97 region.ResolveEdges();
98
99 auto& basic_blocks = region.basic_blocks();
100 ASSERT_EQ(basic_blocks.size(), 3u);
101 ASSERT_TRUE(basic_blocks.contains(42));
102 ASSERT_TRUE(basic_blocks.contains(100));
103 ASSERT_TRUE(basic_blocks.contains(200));
104
105 {
106 auto bb = basic_blocks.at(42);
107 EXPECT_TRUE(bb.in_edges().empty());
108 }
109
110 {
111 auto bb = basic_blocks.at(100);
112 EXPECT_THAT(bb.in_edges(), ElementsAre(42));
113 }
114
115 {
116 auto bb = basic_blocks.at(200);
117 EXPECT_THAT(bb.in_edges(), ElementsAre(42, 100));
118 }
119 }
120
TEST(GuestCodeRegion,SplitBasicBlock)121 TEST(GuestCodeRegion, SplitBasicBlock) {
122 Arena arena;
123 GuestCodeRegion region(&arena);
124
125 // 42 - 54
126 region.NewBasicBlock(42, 12, ArenaVector<GuestAddr>({110, 150, 220}, &arena));
127
128 EXPECT_THAT(region.branch_targets(), ElementsAre(110, 150, 220));
129
130 // 100 - 120
131 region.NewBasicBlock(100, 20, ArenaVector<GuestAddr>({8, 50, 1000}, &arena));
132
133 EXPECT_THAT(region.branch_targets(), ElementsAre(8, 50, 110, 150, 220, 1000));
134
135 // 200 - 240
136 region.NewBasicBlock(200, 40, ArenaVector<GuestAddr>({80, 120, 240}, &arena));
137
138 EXPECT_THAT(region.branch_targets(), ElementsAre(8, 50, 80, 110, 120, 150, 220, 240, 1000));
139
140 // 240 - 250
141 region.NewBasicBlock(240, 50, ArenaVector<GuestAddr>({10, 210, 230}, &arena));
142
143 EXPECT_THAT(region.branch_targets(),
144 ElementsAre(8, 10, 50, 80, 110, 120, 150, 210, 220, 230, 240, 1000));
145
146 region.ResolveEdges();
147
148 auto& basic_blocks = region.basic_blocks();
149 ASSERT_EQ(basic_blocks.size(), 9u);
150 ASSERT_TRUE(basic_blocks.contains(42));
151 ASSERT_TRUE(basic_blocks.contains(50));
152 ASSERT_TRUE(basic_blocks.contains(100));
153 ASSERT_TRUE(basic_blocks.contains(110));
154 ASSERT_TRUE(basic_blocks.contains(200));
155 ASSERT_TRUE(basic_blocks.contains(210));
156 ASSERT_TRUE(basic_blocks.contains(220));
157 ASSERT_TRUE(basic_blocks.contains(230));
158 ASSERT_TRUE(basic_blocks.contains(240));
159
160 {
161 auto bb = basic_blocks.at(42);
162 EXPECT_EQ(bb.start_addr(), 42u);
163 EXPECT_EQ(bb.size(), 8u);
164 EXPECT_EQ(bb.end_addr(), 50u);
165 EXPECT_THAT(bb.out_edges(), ElementsAre(50));
166 EXPECT_TRUE(bb.in_edges().empty());
167 }
168
169 {
170 auto bb = basic_blocks.at(50);
171 EXPECT_EQ(bb.start_addr(), 50u);
172 EXPECT_EQ(bb.size(), 4u);
173 EXPECT_EQ(bb.end_addr(), 54u);
174 EXPECT_THAT(bb.out_edges(), ElementsAre(110, 150, 220));
175 EXPECT_THAT(bb.in_edges(), ElementsAre(42, 110));
176 }
177
178 {
179 auto bb = basic_blocks.at(100);
180 EXPECT_EQ(bb.start_addr(), 100u);
181 EXPECT_EQ(bb.size(), 10u);
182 EXPECT_EQ(bb.end_addr(), 110u);
183 EXPECT_THAT(bb.out_edges(), ElementsAre(110));
184 EXPECT_TRUE(bb.in_edges().empty());
185 }
186
187 {
188 auto bb = basic_blocks.at(110);
189 EXPECT_EQ(bb.start_addr(), 110u);
190 EXPECT_EQ(bb.size(), 10u);
191 EXPECT_EQ(bb.end_addr(), 120u);
192 EXPECT_THAT(bb.out_edges(), ElementsAre(8, 50, 1000));
193 EXPECT_THAT(bb.in_edges(), ElementsAre(50, 100));
194 }
195
196 {
197 auto bb = basic_blocks.at(200);
198 EXPECT_EQ(bb.start_addr(), 200u);
199 EXPECT_EQ(bb.size(), 10u);
200 EXPECT_EQ(bb.end_addr(), 210u);
201 EXPECT_THAT(bb.out_edges(), ElementsAre(210));
202 EXPECT_TRUE(bb.in_edges().empty());
203 }
204
205 {
206 auto bb = basic_blocks.at(210);
207 EXPECT_EQ(bb.start_addr(), 210u);
208 EXPECT_EQ(bb.size(), 10u);
209 EXPECT_EQ(bb.end_addr(), 220u);
210 EXPECT_THAT(bb.out_edges(), ElementsAre(220));
211 EXPECT_THAT(bb.in_edges(), ElementsAre(200, 240));
212 }
213
214 {
215 auto bb = basic_blocks.at(220);
216 EXPECT_EQ(bb.start_addr(), 220u);
217 EXPECT_EQ(bb.size(), 10u);
218 EXPECT_EQ(bb.end_addr(), 230u);
219 EXPECT_THAT(bb.out_edges(), ElementsAre(230));
220 EXPECT_THAT(bb.in_edges(), ElementsAre(50, 210));
221 }
222
223 {
224 auto bb = basic_blocks.at(230);
225 EXPECT_EQ(bb.start_addr(), 230u);
226 EXPECT_EQ(bb.size(), 10u);
227 EXPECT_EQ(bb.end_addr(), 240u);
228 EXPECT_THAT(bb.out_edges(), ElementsAre(80, 120, 240));
229 EXPECT_THAT(bb.in_edges(), ElementsAre(220, 240));
230 }
231
232 {
233 auto bb = basic_blocks.at(240);
234 EXPECT_EQ(bb.start_addr(), 240u);
235 EXPECT_EQ(bb.size(), 50u);
236 EXPECT_EQ(bb.end_addr(), 290u);
237 EXPECT_THAT(bb.out_edges(), ElementsAre(10, 210, 230));
238 EXPECT_THAT(bb.in_edges(), ElementsAre(230));
239 }
240 }
241
TEST(GuestCodeRegion,InvalidRegion)242 TEST(GuestCodeRegion, InvalidRegion) {
243 Arena arena;
244 GuestCodeRegion region(&arena);
245
246 // Overlapping code blocks are not allowed
247 region.NewBasicBlock(100, 60, ArenaVector<GuestAddr>({}, &arena));
248 region.NewBasicBlock(150, 50, ArenaVector<GuestAddr>({}, &arena));
249
250 EXPECT_DEATH(region.ResolveEdges(), "");
251 }
252
TEST(GuestCodeRegion,NoResolveEdgesTwice)253 TEST(GuestCodeRegion, NoResolveEdgesTwice) {
254 Arena arena;
255 GuestCodeRegion region(&arena);
256
257 region.NewBasicBlock(100, 60, ArenaVector<GuestAddr>({}, &arena));
258
259 region.ResolveEdges();
260
261 EXPECT_DEATH(region.ResolveEdges(), "");
262 }
263
TEST(GuestCodeRegion,ResolveEdgesExpectsNoInEdges)264 TEST(GuestCodeRegion, ResolveEdgesExpectsNoInEdges) {
265 Arena arena;
266 GuestCodeRegion region(&arena);
267
268 auto* bb = region.NewBasicBlock(100, 60, ArenaVector<GuestAddr>({}, &arena));
269 bb->AddInEdge(5);
270
271 EXPECT_DEATH(region.ResolveEdges(), "");
272 }
273
TEST(GuestCodeRegion,NoNewBasicBlockAfterResolveRegion)274 TEST(GuestCodeRegion, NoNewBasicBlockAfterResolveRegion) {
275 Arena arena;
276 GuestCodeRegion region(&arena);
277
278 region.NewBasicBlock(100, 60, ArenaVector<GuestAddr>({}, &arena));
279
280 region.ResolveEdges();
281
282 EXPECT_DEATH(region.NewBasicBlock(200, 20, ArenaVector<GuestAddr>({}, &arena)), "");
283 }
284
285 } // namespace
286
287 } // namespace berberis
288