| // Copyright 2022 The Centipede Authors. |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| #include "./centipede/control_flow.h" |
| |
| #include <filesystem> // NOLINT |
| #include <fstream> |
| #include <queue> |
| #include <string> |
| #include <vector> |
| |
| #include "absl/strings/match.h" |
| #include "./centipede/command.h" |
| #include "./centipede/defs.h" |
| #include "./centipede/logging.h" |
| #include "./centipede/util.h" |
| |
| namespace centipede { |
| |
| PCTable GetPcTableFromBinary(std::string_view binary_path, |
| std::string_view objdump_path, |
| std::string_view tmp_path, |
| bool *uses_legacy_trace_pc_instrumentation) { |
| PCTable res = GetPcTableFromBinaryWithPcTable(binary_path, tmp_path); |
| if (res.empty()) { |
| LOG(WARNING) |
| << "Failed to dump PC table directly from binary using linked-in " |
| "runner; see target execution logs above; falling back to legacy PC " |
| "table extraction using trace-pc and objdump"; |
| res = GetPcTableFromBinaryWithTracePC(binary_path, objdump_path, tmp_path); |
| if (res.empty()) { |
| LOG(ERROR) << "Failed to extract PC table from binary using objdump; see " |
| "objdump execution logs above"; |
| } |
| *uses_legacy_trace_pc_instrumentation = true; |
| } else { |
| *uses_legacy_trace_pc_instrumentation = false; |
| } |
| return res; |
| } |
| |
| PCTable GetPcTableFromBinaryWithPcTable(std::string_view binary_path, |
| std::string_view tmp_path) { |
| const std::string stdout_stderr_path = absl::StrCat(tmp_path, ".log"); |
| Command cmd(binary_path, {}, |
| {absl::StrCat("CENTIPEDE_RUNNER_FLAGS=:dump_pc_table:arg1=", |
| tmp_path, ":")}, |
| stdout_stderr_path); |
| int exit_code = cmd.Execute(); |
| std::filesystem::remove(stdout_stderr_path); |
| if (exit_code) { |
| std::filesystem::remove(tmp_path); |
| return {}; |
| } |
| ByteArray pc_infos_as_bytes; |
| ReadFromLocalFile(tmp_path, pc_infos_as_bytes); |
| std::filesystem::remove(tmp_path); |
| CHECK_EQ(pc_infos_as_bytes.size() % sizeof(PCInfo), 0); |
| size_t pc_table_size = pc_infos_as_bytes.size() / sizeof(PCInfo); |
| const auto *pc_infos = reinterpret_cast<PCInfo *>(pc_infos_as_bytes.data()); |
| PCTable pc_table{pc_infos, pc_infos + pc_table_size}; |
| CHECK_EQ(pc_table.size(), pc_table_size); |
| return pc_table; |
| } |
| |
| PCTable GetPcTableFromBinaryWithTracePC(std::string_view binary_path, |
| std::string_view objdump_path, |
| std::string_view tmp_path) { |
| const std::string stderr_path = absl::StrCat(tmp_path, ".log"); |
| Command cmd(objdump_path, {"-d", std::string(binary_path)}, {}, tmp_path, |
| stderr_path); |
| int exit_code = cmd.Execute(); |
| std::filesystem::remove(stderr_path); |
| if (exit_code != EXIT_SUCCESS) { |
| std::filesystem::remove(tmp_path); |
| return {}; |
| } |
| PCTable pc_table; |
| std::ifstream in(std::string{tmp_path}); |
| CHECK(in.good()) << VV(tmp_path); |
| bool saw_new_function = false; |
| |
| // Read the objdump output, find lines that start a function |
| // and lines that have a call to __sanitizer_cov_trace_pc. |
| // Reconstruct the PCTable from those. |
| for (std::string line; std::getline(in, line);) { |
| if (absl::EndsWith(line, ">:")) { // new function. |
| saw_new_function = true; |
| continue; |
| } |
| if (!absl::EndsWith(line, "<__sanitizer_cov_trace_pc>") && |
| !absl::EndsWith(line, "<__sanitizer_cov_trace_pc@plt>")) |
| continue; |
| uintptr_t pc = std::stoul(line, nullptr, 16); |
| uintptr_t flags = saw_new_function ? PCInfo::kFuncEntry : 0; |
| saw_new_function = false; // next trace_pc will be in the same function. |
| pc_table.push_back({pc, flags}); |
| } |
| std::filesystem::remove(tmp_path); |
| return pc_table; |
| } |
| |
| CFTable GetCfTableFromBinary(std::string_view binary_path, |
| std::string_view tmp_path) { |
| const std::string stdout_stderr_path = absl::StrCat(tmp_path, ".log"); |
| Command cmd(binary_path, {}, |
| {absl::StrCat("CENTIPEDE_RUNNER_FLAGS=:dump_cf_table:arg1=", |
| tmp_path, ":")}, |
| stdout_stderr_path); |
| int cmd_exit_code = cmd.Execute(); |
| std::filesystem::remove(stdout_stderr_path); |
| if (cmd_exit_code != EXIT_SUCCESS) { |
| LOG(ERROR) << "Failed to dump CF table from binary using linked-in runner; " |
| "see logs above. Note: binary should be built with at least " |
| "Clang 16 and with -fsanitize-coverage=control-flow flag"; |
| std::filesystem::remove(tmp_path); |
| return {}; |
| } |
| ByteArray cf_infos_as_bytes; |
| ReadFromLocalFile(tmp_path, cf_infos_as_bytes); |
| std::filesystem::remove(tmp_path); |
| |
| size_t cf_table_size = cf_infos_as_bytes.size() / sizeof(CFTable::value_type); |
| const auto *cf_infos = |
| reinterpret_cast<CFTable::value_type *>(cf_infos_as_bytes.data()); |
| CFTable cf_table{cf_infos, cf_infos + cf_table_size}; |
| CHECK_EQ(cf_table.size(), cf_table_size); |
| return cf_table; |
| } |
| |
| void ControlFlowGraph::InitializeControlFlowGraph(const CFTable &cf_table, |
| const PCTable &pc_table) { |
| CHECK(!cf_table.empty()); |
| func_entries_.resize(pc_table.size()); |
| reachability_.resize(pc_table.size()); |
| |
| for (size_t j = 0; j < cf_table.size();) { |
| std::vector<uintptr_t> successors; |
| auto curr_pc = cf_table[j]; |
| ++j; |
| |
| // Iterate over successors. |
| while (cf_table[j]) { |
| successors.push_back(cf_table[j]); |
| ++j; |
| } |
| ++j; // Step over the delimiter. |
| |
| // Record the list of successors |
| graph_[curr_pc] = std::move(successors); |
| // TODO(ussuri): Remove after debugging. |
| VLOG(100) << "Added PC: " << curr_pc; |
| |
| // Iterate over callees. |
| while (cf_table[j]) { |
| ++j; |
| } |
| ++j; // Step over the delimiter. |
| CHECK_LE(j, cf_table.size()); |
| } |
| // Calculate cyclomatic complexity for all functions. |
| for (PCIndex i = 0; i < pc_table.size(); ++i) { |
| pc_index_map_[pc_table[i].pc] = i; |
| if (pc_table[i].has_flag(PCInfo::kFuncEntry)) { |
| func_entries_[i] = true; |
| uintptr_t func_pc = pc_table[i].pc; |
| auto func_comp = ComputeFunctionCyclomaticComplexity(func_pc, *this); |
| function_complexities_[func_pc] = func_comp; |
| } |
| } |
| } |
| |
| const std::vector<uintptr_t> &ControlFlowGraph::GetSuccessors( |
| uintptr_t basic_block) const { |
| auto it = graph_.find(basic_block); |
| CHECK(it != graph_.end()) << VV(basic_block); |
| return it->second; |
| } |
| |
| std::vector<uintptr_t> ControlFlowGraph::ComputeReachabilityForPc( |
| uintptr_t pc) const { |
| absl::flat_hash_set<uintptr_t> visited_pcs; |
| std::queue<uintptr_t> worklist; |
| |
| worklist.push(pc); |
| while (!worklist.empty()) { |
| auto current_pc = worklist.front(); |
| worklist.pop(); |
| if (!visited_pcs.insert(current_pc).second) continue; |
| for (const auto &successor : graph_.at(current_pc)) { |
| if (!exists(successor)) continue; |
| worklist.push(successor); |
| } |
| } |
| return {visited_pcs.begin(), visited_pcs.end()}; |
| } |
| |
| uint32_t ComputeFunctionCyclomaticComplexity(uintptr_t pc, |
| const ControlFlowGraph &cfg) { |
| size_t edge_num = 0, node_num = 0; |
| |
| absl::flat_hash_set<uintptr_t> visited_pcs; |
| std::queue<uintptr_t> worklist; |
| |
| worklist.push(pc); |
| |
| while (!worklist.empty()) { |
| auto current_pc = worklist.front(); |
| worklist.pop(); |
| if (!visited_pcs.insert(current_pc).second) continue; |
| ++node_num; |
| for (auto &successor : cfg.GetSuccessors(current_pc)) { |
| if (!cfg.exists(successor)) continue; |
| ++edge_num; |
| worklist.push(successor); |
| } |
| } |
| |
| return edge_num - node_num + 2; |
| } |
| |
| } // namespace centipede |