blob: 6b87461d00c08ebfdc21c0f328e904c69ab39681 [file] [log] [blame] [edit]
// Copyright 2019 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "tools/fidlcat/lib/comparator.h"
#include <zircon/assert.h>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
namespace fidlcat {
void Comparator::CompareInput(std::string_view syscall_inputs, std::string_view actual_process_name,
uint64_t actual_pid, uint64_t actual_tid) {
// remove header from the message
syscall_inputs = AnalyzesAndRemovesHeader(syscall_inputs);
auto actual_message_node = actual_message_graph_.InsertMessage(actual_process_name, actual_pid,
actual_tid, syscall_inputs);
// Is there a unique match for this message in the golden messages? If so, we propagate this
// match.
std::shared_ptr<GoldenNode> matching_golden_node = UniqueMatchToGolden(actual_message_node);
if (matching_golden_node) {
PropagateMatch(actual_message_node, matching_golden_node, false);
}
last_unmatched_input_from_tid_[actual_tid] = actual_message_node;
}
void Comparator::CompareOutput(std::string_view syscall_outputs,
std::string_view actual_process_name, uint64_t actual_pid,
uint64_t actual_tid) {
// If present, remove header from message
syscall_outputs = AnalyzesAndRemovesHeader(syscall_outputs);
// Create the output node, linking it to its corresponding input node if there is one.
auto matching_input = last_unmatched_input_from_tid_.find(actual_tid);
auto actual_message_node =
matching_input != last_unmatched_input_from_tid_.end()
? actual_message_graph_.InsertMessage(actual_process_name, actual_pid, actual_tid,
syscall_outputs, matching_input->second)
: actual_message_graph_.InsertMessage(actual_process_name, actual_pid, actual_tid,
syscall_outputs);
// Is there a unique match for this message in the golden messages? If so, we propagate this
// match.
std::shared_ptr<GoldenNode> matching_golden_node = UniqueMatchToGolden(actual_message_node);
if (matching_golden_node) {
PropagateMatch(actual_message_node, matching_golden_node, false);
}
}
void Comparator::DecodingError(std::string_view error) {
compare_results_ << "Unexpected decoding error in the current execution:\n" << error;
}
std::shared_ptr<GoldenMessageNode> Comparator::UniqueMatchToGolden(
std::shared_ptr<ActualMessageNode> actual_message_node) {
auto poss_golden_messages =
golden_message_graph_.message_nodes().find(actual_message_node->message());
if (poss_golden_messages == golden_message_graph_.message_nodes().end()) { // No message matched
compare_results_ << "No golden message could match " << *actual_message_node;
return nullptr;
}
if (poss_golden_messages->second.size() == 1) {
// exactly one message from golden matched this string
return poss_golden_messages->second[0];
}
// More than one golden message matched
return nullptr;
}
bool Comparator::PropagateMatch(std::shared_ptr<ActualNode> actual_node,
std::shared_ptr<GoldenNode> golden_node, bool reverse_propagate) {
if (!actual_node || !golden_node) {
return false;
}
if (actual_node->matching_golden_node()) {
if (actual_node->matching_golden_node() == golden_node) {
return true;
}
compare_results_ << "Conflicting matches for " << *actual_node << "matched to " << *golden_node
<< " and " << *(actual_node->matching_golden_node()) << "\n";
return false;
}
if (golden_node->has_matching_actual_node()) {
compare_results_ << *golden_node << "was matched twice.\n";
return false;
}
if (golden_node->dependencies().size() != actual_node->dependencies().size()) {
compare_results_ << *actual_node << " with " << actual_node->dependencies().size()
<< " dependencies was matched with " << *golden_node << " which has "
<< golden_node->dependencies().size() << " dependencies \n";
return false;
}
actual_node->set_matching_golden_node(golden_node);
golden_node->set_has_matching_actual_node();
auto golden_i = golden_node->dependencies().begin();
for (auto i = actual_node->dependencies().begin(); i != actual_node->dependencies().end(); i++) {
auto actual_dependency_node = i->second;
// The golden node that should match actual_dependency_node according to the dependency links
// of golden_node
auto golden_dependency_node = golden_i->second;
if (!PropagateMatch(actual_dependency_node, golden_dependency_node, reverse_propagate)) {
return false;
}
golden_i++;
}
if (reverse_propagate) {
return ReversePropagateMatch(actual_node);
}
return true;
}
bool Comparator::ReversePropagateMatch(std::shared_ptr<ActualNode> actual_node) {
// Should only be called after Propagate has been called on actual_node, so actual_node should
// have a matching golden_node.
auto golden_node = actual_node->matching_golden_node();
ZX_ASSERT(golden_node != nullptr);
// We can only propagate along a reverse dependency if it is the only one of its type.
for (auto actual_link_type_pair = actual_node->reverse_dependencies().begin();
actual_link_type_pair != actual_node->reverse_dependencies().end();
actual_link_type_pair++) {
size_t actual_nb_link_of_type = actual_link_type_pair->second.size();
if (actual_nb_link_of_type > 1) {
// multiple links with same type, we can't do any propagation
continue;
}
auto golden_link_type_pair =
golden_node->get_reverse_dependencies_by_type(actual_link_type_pair->first);
// This reverse link is not present in golden_node, there is no possible matching between the
// current execution and the one stored in the golden file.
if (golden_link_type_pair == golden_node->reverse_dependencies().end()) {
compare_results_ << *actual_node << " with a reverse dependency of type "
<< actual_link_type_pair->first.second << " was matched to " << *golden_node
<< " which has no such reverse dependency \n";
return false;
}
size_t golden_nb_link_of_type = golden_link_type_pair->second.size();
// golden node also has more reverse dependencies than actual_node, this means the matching is
// not possible as we only call ReversePropagate when the actual_message_graph_ is complete
if (golden_nb_link_of_type > 1) {
compare_results_ << *actual_node << " with one reverse dependency of type "
<< actual_link_type_pair->first.second << " was matched to " << *golden_node
<< " which has " << golden_nb_link_of_type
<< " such reverse dependencies \n";
return false;
}
auto actual_dependency_node = actual_link_type_pair->second[0].lock();
auto golden_dependency_node = golden_link_type_pair->second[0].lock();
if (!PropagateMatch(actual_dependency_node, golden_dependency_node, true)) {
return false;
}
}
return true;
}
void Comparator::ParseGolden(std::string_view golden_file_contents) {
size_t processed_char_count = 0;
// We use this map to link output messages to their corresponding input messages.
std::map<uint64_t, std::shared_ptr<GoldenMessageNode>> last_unmatched_input_from_tid_golden;
std::string_view cur_msg = GetMessage(golden_file_contents, &processed_char_count);
uint64_t previous_pid = 0;
uint64_t previous_tid = 0;
std::string previous_process_name;
while (!cur_msg.empty()) {
uint64_t pid = 0, tid = 0;
std::string process_name;
cur_msg = AnalyzesAndRemovesHeader(cur_msg, &process_name, &pid, &tid);
// AnalyzesAndRemovesHeader did not update the values of pid, tid and process_name, as there was
// no header to the message (or it could not be parsed).
if (pid == 0) {
pid = previous_pid;
tid = previous_tid;
process_name = previous_process_name;
}
auto last_unmatched = last_unmatched_input_from_tid_golden.find(tid);
if (last_unmatched != last_unmatched_input_from_tid_golden.end()) {
// This is an output message, with a corresponding input messge
auto message_node = golden_message_graph_.InsertMessage(process_name, pid, tid, cur_msg,
last_unmatched->second);
last_unmatched_input_from_tid_golden.erase(tid);
} else {
auto message_node = golden_message_graph_.InsertMessage(process_name, pid, tid, cur_msg);
if (HasReturn(cur_msg)) {
last_unmatched_input_from_tid_golden[tid] = message_node;
}
}
golden_file_contents = golden_file_contents.substr(processed_char_count);
cur_msg = GetMessage(golden_file_contents, &processed_char_count);
previous_pid = pid;
previous_tid = tid;
previous_process_name = process_name;
}
}
std::string_view Comparator::GetMessage(std::string_view messages, size_t* processed_char_count) {
// begin points to the beginning of the line, end to its end.
size_t begin = 0;
size_t end = messages.find('\n', begin);
// Ignore fidlcat startup lines or empty lines.
while (end != std::string::npos) {
if (!IgnoredLine(messages.substr(begin, end - begin))) {
break;
}
begin = end + 1;
end = messages.find('\n', begin);
}
// Now we get the message.
size_t bpos = begin;
while (end != std::string::npos) {
// New line indicates end of syscall input or output.
if (bpos < begin && end == begin && messages[begin] == '\n') {
break;
}
// Beginning of syscall output display.
if (bpos < begin && messages.substr(begin, end - begin).find(" ->") == 0) {
break;
}
// If the current line is the beginning of a multiline "sent " or "received ", we skip lines
// until we get to the closing " }". To find this closing "}", we rely on fidl_codec printing
// indentation: if the message is a request (begins with " sent"), indentation is 2 spaces, if
// it is a response (" received"), indentation is 4. Note: if fidl_codec fails to find the
// direction fo the message (request or response), this may fail to separate the messages
// properly, or if the first line of the message contains an opening { and some more {} couples,
// we mail fail to detect this as the beginning of a mutliline message. This should be removed
// when we can get access to a serialized version of the messages, and not only their text
// representation.
std::string_view cur_line = messages.substr(begin, end - begin);
bool is_received = cur_line.rfind(" received ", 0) != std::string::npos;
bool is_sent = cur_line.rfind(" sent ", 0) != std::string::npos;
if (is_sent || is_received) {
// This is the beginning of a request/response message
size_t pos_open = cur_line.find('{');
if (pos_open != std::string::npos &&
cur_line.substr(pos_open).find('}') == std::string::npos) {
// We have an open '{', we hence skip lines until we find the matching closing '}'
size_t indentation = is_sent ? 2 : 4;
while (end != std::string::npos &&
!ClosingSequence(messages.substr(begin, end - begin), indentation)) {
begin = end + 1;
end = messages.find('\n', begin);
}
}
}
begin = end + 1;
end = messages.find('\n', begin);
}
*processed_char_count = begin;
// Note that as expected_output_ is a string_view, substr() returns a string_view as well.
return messages.substr(bpos, begin - bpos);
}
bool Comparator::ClosingSequence(std::string_view line, size_t indentation) {
if (line.length() < indentation + 1) {
return false;
}
// exactly one tabulation before the first closing ] or }
for (size_t i = 0; i < indentation; i++) {
if (line[i] != ' ') {
return false;
}
}
if (line[indentation] != ']' && line[indentation] != '}') {
return false;
}
// then a sequence of " ]" or " }"
size_t pos = indentation + 1;
while (pos + 2 <= line.length()) {
if (line[pos] != ' ') {
return false;
}
if (line[pos + 1] != '}' && line[pos + 1] != ']') {
return false;
}
pos += 2;
}
return true;
}
bool Comparator::IgnoredLine(std::string_view line) {
if (line.length() == 0) {
return true;
}
if (line.length() == 1 && line[0] == '\n') {
return true;
}
static std::vector<std::string> to_be_ignored = {"Checking", "Debug", "Launched", "Monitoring",
"Stop"};
for (size_t i = 0; i < to_be_ignored.size(); i++) {
if (line.find(to_be_ignored[i]) == 0) {
return true;
}
}
return false;
}
std::string_view Comparator::AnalyzesAndRemovesHeader(std::string_view message,
std::string* process_name, uint64_t* pid,
uint64_t* tid) {
constexpr size_t kMinNbCharHeader = 5;
// The message is a syscall output with no header.
if (message.find("->") <= kMinNbCharHeader) {
return message;
}
size_t pos_pid = message.find(' ');
size_t pos_tid = message.find(':');
// Either there is no header, or we cannot parse it so leave it as is.
if (pos_pid == std::string::npos || pos_tid == std::string::npos) {
return message;
}
// If we have pointers to pid, tid and process_name, update those.
if (pid) {
*pid = ExtractUint64(message.substr(pos_pid + 1));
}
if (tid) {
*tid = ExtractUint64(message.substr(pos_tid + 1));
}
if (process_name) {
*process_name = message.substr(0, pos_pid);
}
size_t end_header = message.find(' ', pos_tid);
if (end_header != std::string::npos) {
return message.substr(end_header + 1);
}
return message;
}
uint64_t Comparator::ExtractUint64(std::string_view str) {
uint64_t result = 0;
for (size_t i = 0; i < str.size(); ++i) {
char value = str[i];
if ((value < '0') || (value > '9')) {
break;
}
result = 10 * result + (value - '0');
}
return result;
}
bool Comparator::HasReturn(std::string_view message) {
// Only three syscalls have no return value. Besides as we removed the header from the message,
// the syscall name is the first word of the message.
if (message.find("zx_thread_exit") == 0 || message.find("zx_process_exit") == 0 ||
message.find("zx_futex_wake_handle_close_thread_exit") == 0) {
return false;
}
return true;
}
void Comparator::FinishComparison() {
// All the messages have been intercepted, we now want to check our graph:
// - First propagates matchings along reverse dependencies now that the graph is complete,
// - Then checks if there still are unmatched nodes, either golden or actual.
for (auto i = actual_message_graph_.message_nodes().begin();
i != actual_message_graph_.message_nodes().end(); i++) {
for (size_t j = 0; j < i->second.size(); j++) {
if (i->second[j]->matching_golden_node() && !ReversePropagateMatch(i->second[j])) {
// The matching failed, with a proper error message
return;
}
}
}
for (auto i = actual_message_graph_.pid_nodes().begin();
i != actual_message_graph_.pid_nodes().end(); i++) {
if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
return;
}
}
for (auto i = actual_message_graph_.tid_nodes().begin();
i != actual_message_graph_.tid_nodes().end(); i++) {
if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
return;
}
}
for (auto i = actual_message_graph_.handle_nodes().begin();
i != actual_message_graph_.handle_nodes().end(); i++) {
if (i->second->matching_golden_node() && !ReversePropagateMatch(i->second)) {
return;
}
}
// We check that all message nodes are matched to a golden node.
bool unmatched_message = false;
for (auto i = actual_message_graph_.message_nodes().begin();
i != actual_message_graph_.message_nodes().end(); i++) {
for (size_t j = 0; j < i->second.size(); j++) {
if (!i->second[j]->matching_golden_node()) {
compare_results_ << "Unmatched actual message " << i->second[j]->message();
unmatched_message = true;
}
}
}
for (auto i = golden_message_graph_.message_nodes().begin();
i != golden_message_graph_.message_nodes().end(); i++) {
for (size_t j = 0; j < i->second.size(); j++) {
if (!i->second[j]->has_matching_actual_node()) {
compare_results_ << "Unmatched golden message " << i->second[j]->message();
unmatched_message = true;
}
}
}
// There is no need to check that handles, pids and tids are matched: as all of them have at least
// one message that depends from them, if all messages are matched, so are they.
if (!unmatched_message) {
compare_results_ << "Messages from the current execution matched the golden file.\n";
}
}
} // namespace fidlcat