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 "bytecode_instruction-inl.h"
17 #include "file_items.h"
18 #include "macros.h"
19 #include "include/runtime.h"
20
21 #include "utils/logger.h"
22
23 #include "util/str.h"
24
25 #include "cflow_status.h"
26 #include "cflow_info.h"
27
28 #include <iomanip>
29
30 #include "cflow_iterate_inl.h"
31
32 #include "verification/jobs/cache.h"
33 #include "verification/jobs/thread_pool.h"
34 #include "verification/cflow/cflow_common.h"
35
36 #include "verifier_messages.h"
37
38 namespace panda::verifier {
39
FillInstructionsMap(InstructionsMap * inst_map_ptr,ExceptionSourceMap * exc_src_map_ptr)40 CflowStatus FillInstructionsMap(InstructionsMap *inst_map_ptr, ExceptionSourceMap *exc_src_map_ptr)
41 {
42 auto &inst_map = *inst_map_ptr;
43 auto &exc_src_map = *exc_src_map_ptr;
44 auto status = IterateOverInstructions(
45 inst_map.AddrStart<const uint8_t *>(), inst_map.AddrStart<const uint8_t *>(),
46 inst_map.AddrEnd<const uint8_t *>(),
47 [&inst_map, &exc_src_map]([[maybe_unused]] auto typ, const uint8_t *pc, size_t sz, bool exception_source,
48 [[maybe_unused]] auto tgt) -> std::optional<CflowStatus> {
49 if (!inst_map.PutInstruction(pc, sz)) {
50 LOG_VERIFIER_CFLOW_INVALID_INSTRUCTION(OffsetAsHexStr(inst_map.AddrStart<void *>(), pc));
51 return CflowStatus::ERROR;
52 }
53 if (exception_source && !exc_src_map.PutExceptionSource(pc)) {
54 LOG_VERIFIER_CFLOW_INVALID_INSTRUCTION(OffsetAsHexStr(inst_map.AddrStart<void *>(), pc));
55 return CflowStatus::ERROR;
56 }
57 const uint8_t *next_inst_pc = &pc[sz]; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
58 if (next_inst_pc <= inst_map.AddrEnd<const uint8_t *>()) {
59 return std::nullopt;
60 }
61 return CflowStatus::OK;
62 });
63 return status;
64 }
65
FillJumpsMapAndGetLastInstructionType(const InstructionsMap & inst_map,JumpsMap * jumps_map_ptr,const uint8_t * pc_start_ptr,const uint8_t * pc_end_ptr,InstructionType * last_inst_type_ptr)66 CflowStatus FillJumpsMapAndGetLastInstructionType(const InstructionsMap &inst_map, JumpsMap *jumps_map_ptr,
67 const uint8_t *pc_start_ptr, const uint8_t *pc_end_ptr,
68 InstructionType *last_inst_type_ptr)
69 {
70 ASSERT(jumps_map_ptr != nullptr);
71
72 JumpsMap &jumps_map = *jumps_map_ptr;
73 auto result = IterateOverInstructions(
74 pc_start_ptr, inst_map.AddrStart<const uint8_t *>(), inst_map.AddrEnd<const uint8_t *>(),
75 [&pc_end_ptr, &inst_map, &jumps_map, last_inst_type_ptr](InstructionType typ, const uint8_t *pc, size_t sz,
76 [[maybe_unused]] bool exception_source,
77 const uint8_t *target) -> std::optional<CflowStatus> {
78 const uint8_t *next_inst_pc = &pc[sz]; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
79 if (typ == InstructionType::JUMP || typ == InstructionType::COND_JUMP) {
80 if (!inst_map.CanJumpTo(target)) {
81 LOG_VERIFIER_CFLOW_INVALID_JUMP_INTO_MIDDLE_OF_INSTRUCTION(
82 OffsetAsHexStr(inst_map.AddrStart<void *>(), target),
83 OffsetAsHexStr(inst_map.AddrStart<void *>(), pc));
84 return CflowStatus::ERROR;
85 }
86 if (!jumps_map.PutJump(pc, target)) {
87 LOG_VERIFIER_CFLOW_INVALID_JUMP(OffsetAsHexStr(inst_map.AddrStart<void *>(), pc),
88 OffsetAsHexStr(inst_map.AddrStart<void *>(), target));
89 return CflowStatus::ERROR;
90 }
91 }
92 // pc_end_ptr is expected to point to the last instruction/byte of the block
93 if (next_inst_pc > pc_end_ptr) {
94 // last instruction should terminate control-flow: jump, return, throw
95 // conditional jumps is problem here, since condition in general could not be precisely
96 // evaluated
97 if (last_inst_type_ptr != nullptr) {
98 *last_inst_type_ptr = typ;
99 }
100
101 return CflowStatus::OK;
102 }
103 return std::nullopt;
104 });
105 return result;
106 }
107
FillCflowBlockInfo(const InstructionsMap & inst_map,CflowBlockInfo * code_block_info)108 CflowStatus FillCflowBlockInfo(const InstructionsMap &inst_map, CflowBlockInfo *code_block_info)
109 {
110 return FillJumpsMapAndGetLastInstructionType(inst_map, &code_block_info->JmpsMap, code_block_info->Start,
111 code_block_info->End, &code_block_info->LastInstType);
112 }
113
114 template <class F>
DebugDump(const LibCache::CachedCatchBlock & catch_block,const F & get_offset)115 static void DebugDump(const LibCache::CachedCatchBlock &catch_block, const F &get_offset)
116 {
117 auto try_start_pc = catch_block.try_block_start;
118 auto try_end_pc = catch_block.try_block_end;
119 auto &exception = catch_block.exception_type;
120 auto pc_start_ptr = catch_block.handler_bytecode;
121 auto size = catch_block.handler_bytecode_size;
122
123 bool catch_all = !LibCache::IsValid(exception);
124 PandaString exc_name = catch_all ? PandaString {"null"} : LibCache::GetName(exception);
125 auto try_range = PandaString {"[ "} + get_offset(try_start_pc) + ", " + get_offset(try_end_pc) + " ]";
126 PandaString exc_handler_range;
127 if (size == 0) {
128 exc_handler_range = get_offset(pc_start_ptr);
129 } else {
130 exc_handler_range = PandaString {"[ "};
131 exc_handler_range += get_offset(pc_start_ptr) + ", ";
132 exc_handler_range += get_offset(&pc_start_ptr[size - 1]); // NOLINT
133 exc_handler_range += " ]";
134 }
135 LOG_VERIFIER_CFLOW_EXC_HANDLER_INFO(exc_handler_range, try_range, exc_name);
136 }
137
138 template <class F>
ProcessCatchBlocks(const LibCache::CachedMethod & method,AddrMap * addr_map,const F & get_offset,InstructionsMap * inst_map,PandaVector<CflowExcHandlerInfo> * exc_handlers,LibCache & cache)139 static bool ProcessCatchBlocks(const LibCache::CachedMethod &method, [[maybe_unused]] AddrMap *addr_map,
140 [[maybe_unused]] const F &get_offset, InstructionsMap *inst_map,
141 PandaVector<CflowExcHandlerInfo> *exc_handlers, LibCache &cache)
142 {
143 bool result = true;
144
145 LOG(DEBUG, VERIFIER) << "Tracing exception handlers.";
146
147 for (const auto &catch_block : method.catch_blocks) {
148 OptionalConstRef<LibCache::CachedClass> cached_class_of_exception = LibCache::Visit(
149 catch_block.exception_type,
150 [](const LibCache::CachedClass &cached_class) { return OptionalConstRef(cached_class); },
151 [&cache, &method](const LibCache::DescriptorString &descriptor) {
152 if (!descriptor.IsValid()) {
153 return OptionalConstRef<LibCache::CachedClass> {}; // catch_all
154 }
155 OptionalConstRef<CachedClass> cc = cache.FastAPI().ResolveAndLink(method.GetSourceLang(), descriptor);
156 return cc;
157 });
158
159 #ifndef NDEBUG
160 DebugDump(catch_block, get_offset);
161 #endif
162 CflowBlockInfo block_info {catch_block.try_block_start,
163 catch_block.try_block_end,
164 {inst_map->AddrStart<const uint8_t *>(), inst_map->AddrEnd<const uint8_t *>()},
165 InstructionType::NORMAL};
166 exc_handlers->push_back(
167 {block_info, catch_block.handler_bytecode, catch_block.handler_bytecode_size, cached_class_of_exception});
168 if (FillCflowBlockInfo(*inst_map, &exc_handlers->back().TryBlock) == CflowStatus::ERROR) {
169 LOG_VERIFIER_CFLOW_CANNOT_FILL_JUMPS_OF_EXC_HANDLER_BLOCK();
170 result = false;
171 break;
172 }
173 }
174
175 return result;
176 }
177
GetCflowMethodInfo(const LibCache::CachedMethod & method,LibCache & cache)178 PandaUniquePtr<CflowMethodInfo> GetCflowMethodInfo(const LibCache::CachedMethod &method, LibCache &cache)
179 {
180 const uint8_t *method_pc_start_ptr = method.bytecode;
181 size_t code_size = method.bytecode_size;
182 const uint8_t *method_pc_end_ptr =
183 &method_pc_start_ptr[code_size - 1]; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
184
185 auto cflow_info = MakePandaUnique<CflowMethodInfo>(method_pc_start_ptr, code_size);
186
187 LOG(DEBUG, VERIFIER) << "Build control flow info for method " << method.GetName();
188
189 // 1. fill instructions map
190 LOG(DEBUG, VERIFIER) << "Build instructions map.";
191 if (FillInstructionsMap(&(*cflow_info).InstMap_, &(*cflow_info).ExcSrcMap_) == CflowStatus::ERROR) {
192 LOG_VERIFIER_CFLOW_CANNOT_FILL_INSTRUCTIONS_MAP()
193 return {};
194 }
195
196 // 2. fill jumps map
197 LOG(DEBUG, VERIFIER) << "Build jumps map.";
198 if (FillJumpsMapAndGetLastInstructionType((*cflow_info).InstMap_, &(*cflow_info).JmpsMap_, method_pc_start_ptr,
199 method_pc_end_ptr, nullptr) == CflowStatus::ERROR) {
200 LOG_VERIFIER_CFLOW_CANNOT_FILL_JUMPS_MAP()
201 return {};
202 }
203
204 // 3. get method body blocks (exception handlers are not limited to the end of method)
205 // and exception handlers blocks at once
206 AddrMap addr_map {method_pc_start_ptr, method_pc_end_ptr};
207 addr_map.InvertMarks();
208
209 auto get_offset = [&addr_map](const uint8_t *ptr) { return OffsetAsHexStr(addr_map.AddrStart<void *>(), ptr); };
210
211 bool result =
212 ProcessCatchBlocks(method, &addr_map, get_offset, &cflow_info->InstMap_, &cflow_info->ExcHandlers_, cache);
213 if (!result) {
214 return {};
215 }
216
217 LOG(DEBUG, VERIFIER) << "Trace method body code blocks.";
218 addr_map.EnumerateMarkedBlocks<const uint8_t *>(
219 [&result, &cflow_info, &get_offset](const uint8_t *pc_start_ptr, const uint8_t *pc_end_ptr) {
220 auto body = CflowBlockInfo {pc_start_ptr, pc_end_ptr,
221 JumpsMap {(*cflow_info).InstMap_.AddrStart<const uint8_t *>(),
222 (*cflow_info).InstMap_.AddrEnd<const uint8_t *>()},
223 InstructionType::NORMAL};
224 if (FillCflowBlockInfo((*cflow_info).InstMap_, &body) == CflowStatus::ERROR) {
225 LOG_VERIFIER_CFLOW_CANNOT_FILL_JUMPS_OF_CODE_BLOCK(get_offset(pc_start_ptr), get_offset(pc_end_ptr));
226 return result = false;
227 }
228 (*cflow_info).BodyBlocks_.push_back(body);
229 return true;
230 });
231 LOG(DEBUG, VERIFIER) << "/Trace method body code blocks.";
232
233 if (!result) {
234 return {};
235 }
236
237 return cflow_info;
238 }
239
240 } // namespace panda::verifier
241