coverage.cc

// 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/coverage.h"

#include <string.h>

#include <cstdint>
#include <limits>
#include <ostream>
#include <sstream>
#include <string>
#include <string_view>
#include <vector>

#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/strings/str_split.h"
#include "absl/synchronization/mutex.h"
#include "./centipede/control_flow.h"
#include "./centipede/feature.h"
#include "./centipede/pc_info.h"
#include "./centipede/symbol_table.h"

namespace centipede {

Coverage::Coverage(const PCTable &pc_table, const PCIndexVec &pci_vec)
    : func_entries_(pc_table.size()),
      fully_covered_funcs_vec_(pc_table.size()),
      covered_pcs_vec_(pc_table.size()) {
  CHECK_LT(pc_table.size(), std::numeric_limits<PCIndex>::max());
  absl::flat_hash_set<PCIndex> covered_pcs(pci_vec.begin(), pci_vec.end());
  // Iterate though all the pc_table entries.
  // The first one is some function's kFuncEntry.
  // Then find the next kFuncEntry or the table end.
  // Everything in between corresponds to the current function.
  // For fully (un)covered functions, add their entry PCIndex
  // to fully_covered_funcs or uncovered_funcs correspondingly.
  // For all others add them to partially_covered_funcs.
  for (size_t this_func = 0; this_func < pc_table.size();) {
    CHECK(pc_table[this_func].has_flag(PCInfo::kFuncEntry));
    func_entries_[this_func] = true;
    // Find next entry.
    size_t next_func = this_func + 1;
    while (next_func < pc_table.size() &&
           !pc_table[next_func].has_flag(PCInfo::kFuncEntry)) {
      next_func++;
    }
    // Collect covered and uncovered indices.
    PartiallyCoveredFunction pcf;
    for (size_t i = this_func; i < next_func; i++) {
      if (covered_pcs.contains(i)) {
        pcf.covered.push_back(i);
        covered_pcs_vec_[i] = true;
      } else {
        pcf.uncovered.push_back(i);
      }
    }
    // Put this function into one of
    // {fully_covered_funcs, uncovered_funcs, partially_covered_funcs}
    size_t num_func_pcs = next_func - this_func;
    if (num_func_pcs == pcf.covered.size()) {
      fully_covered_funcs.push_back(this_func);
      fully_covered_funcs_vec_[this_func] = true;
    } else if (pcf.covered.empty()) {
      uncovered_funcs.push_back(this_func);
    } else {
      CHECK(!pcf.covered.empty());
      CHECK(!pcf.uncovered.empty());
      CHECK_EQ(pcf.covered.size() + pcf.uncovered.size(), num_func_pcs);
      partially_covered_funcs.push_back(pcf);
    }
    // Move to the next function.
    this_func = next_func;
  }
}

void Coverage::Print(const SymbolTable &symbols, std::ostream &out) {
  // Print symbolized function names for all covered functions.
  for (auto pc_index : fully_covered_funcs) {
    out << "FULL: " << symbols.full_description(pc_index) << "\n";
  }
  // Same for uncovered functions.
  for (auto pc_index : uncovered_funcs) {
    out << "NONE: " << symbols.full_description(pc_index) << "\n";
  }
  // For every partially covered function, first print its name,
  // then print its covered edges, then uncovered edges.
  for (auto &pcf : partially_covered_funcs) {
    out << "PARTIAL: " << symbols.full_description(pcf.covered[0]) << "\n";
    for (auto pc_index : pcf.covered) {
      out << "  + " << symbols.full_description(pc_index) << "\n";
    }
    for (auto pc_index : pcf.uncovered) {
      out << "  - " << symbols.full_description(pc_index) << "\n";
    }
  }
}

//---------------------- NewCoverageLogger
std::string CoverageLogger::ObserveAndDescribeIfNew(PCIndex pc_index) {
  if (pc_table_.empty()) return "";  // Fast-path return (symbolization is off).
  absl::MutexLock l(&mu_);
  if (!observed_indices_.insert(pc_index).second) return "";
  std::ostringstream os;
  if (pc_index >= pc_table_.size()) {
    os << "FUNC/EDGE index: " << pc_index;
  } else {
    os << (pc_table_[pc_index].has_flag(PCInfo::kFuncEntry) ? "FUNC: "
                                                            : "EDGE: ");
    os << symbols_.full_description(pc_index);
    if (!observed_descriptions_.insert(os.str()).second) return "";
  }
  return os.str();
}

FunctionFilter::FunctionFilter(std::string_view functions_to_filter,
                               const SymbolTable &symbols) {
  // set pcs_[idx] to 1, for any idx that belongs to a filtered function.
  // keep pcs_ empty, if no filtered functions are found in symbols.
  for (auto &func : absl::StrSplit(functions_to_filter, ',')) {
    for (size_t idx = 0, n = symbols.size(); idx < n; ++idx) {
      if (func == symbols.func(idx)) {
        if (pcs_.empty()) {
          pcs_.resize(n);
        }
        pcs_[idx] = 1;
      }
    }
  }
}

bool FunctionFilter::filter(const FeatureVec &features) const {
  if (pcs_.empty()) return true;
  for (auto feature : features) {
    if (!feature_domains::kPCs.Contains(feature)) continue;
    size_t idx = ConvertPCFeatureToPcIndex(feature);
    // idx should normally be within the range. Ignore it if it's not.
    if (idx >= pcs_.size()) continue;
    if (pcs_[idx]) return true;
  }
  return false;
}

static uint8_t SelectMultiplierByCoverageKind(uint8_t uncovered_knob,
                                              uint8_t partially_covered_knob,
                                              uint8_t fully_covered_knob,
                                              PCIndex callee_idx,
                                              const Coverage &coverage) {
  if (coverage.FunctionIsFullyCovered(callee_idx)) return fully_covered_knob;
  if (coverage.BlockIsCovered(callee_idx)) return partially_covered_knob;
  return uncovered_knob;
}

uint32_t ComputeFrontierWeight(const Coverage &coverage,
                               const ControlFlowGraph &cfg,
                               const std::vector<uintptr_t> &callees) {
  // Multiplication factors for different coverage types.
  // TODO(ussuri): replace with actual knobs (cl/486229527).
  uint8_t uncovered_knob = 153;         // ~ (255 * 0.6)
  uint8_t partially_covered_knob = 77;  // ~ (255 * 0.3)
  uint8_t fully_covered_knob = 25;      // ~ (255 * 0.1)

  uint32_t weight = 0;
  for (auto callee : callees) {
    // TODO(ussuri): Figure out a better way for determining the complexity
    // of indirect callee. For now using cyclomatic_comp = 1, and factor of
    // non-covered callee.
    if (callee == -1ULL) {
      weight += uncovered_knob;
      continue;
    }
    // This function's body is not in this DSO, like library functions. For now
    // skipping it as we have no coverage kind (Fully/Partially covered or
    // uncovered) and no complexity for it.
    if (!cfg.IsInPcTable(callee)) continue;

    // Retrieve cyclomatic complexity
    auto cyclomatic_comp = cfg.GetCyclomaticComplexity(callee);
    // Determine knob based on callee coverage kind.
    auto callee_idx = cfg.GetPcIndex(callee);
    CHECK(cfg.BlockIsFunctionEntry(callee_idx));
    auto coverage_multiplier = SelectMultiplierByCoverageKind(
        uncovered_knob, partially_covered_knob, fully_covered_knob, callee_idx,
        coverage);

    weight += coverage_multiplier * cyclomatic_comp;
  }
  return weight;
}

}  // namespace centipede