Index: include/llvm/Support/Path.h =================================================================== --- include/llvm/Support/Path.h +++ include/llvm/Support/Path.h @@ -430,6 +430,15 @@ /// @result True if path was changed bool remove_dots(SmallVectorImpl &path, bool remove_dot_dot = false); +/// @brief compute common path prefix of given paths. +/// +/// When common prefix is found, it would always end with separator. +/// Performs component comparisons. I.e. common_prefix({"/usr/bin/a", "/u/b"}) +/// is "/". +// +/// @result longest common path prefix. +std::string common_prefix(const std::vector &paths); + } // end namespace path } // end namespace sys } // end namespace llvm Index: lib/Support/Path.cpp =================================================================== --- lib/Support/Path.cpp +++ lib/Support/Path.cpp @@ -1143,6 +1143,44 @@ return false; } +std::string common_prefix(const std::vector &Paths) { + if (Paths.empty()) + return ""; + + std::vector CommonPrefix; + bool First = true; + bool Removed = false; + for (StringRef P : Paths) { + int I = 0; + for (StringRef C : llvm::make_range(path::begin(P), path::end(P))) { + if (First) + CommonPrefix.push_back(C); + else if (CommonPrefix[I] != C) { + CommonPrefix.erase(CommonPrefix.begin() + I, CommonPrefix.end()); + Removed = true; + break; + } + + I++; + } + + First = false; + } + + SmallString<128> result; + for (StringRef C : CommonPrefix) { + append(result, C); + } + + // Append trailing "/" if needed. + if (Paths.size() > 1 && !CommonPrefix.empty() && Removed && + result.rfind(preferred_separator) != result.size() - 1) { + result += preferred_separator; + } + + return result.str(); +} + } // end namespace path } // end namsspace sys } // end namespace llvm Index: test/tools/sancov/covered_functions.test =================================================================== --- test/tools/sancov/covered_functions.test +++ test/tools/sancov/covered_functions.test @@ -1,7 +1,7 @@ REQUIRES: x86_64-linux -RUN: sancov -obj %p/Inputs/test-linux_x86_64 -covered_functions %p/Inputs/test-linux_x86_64.sancov | FileCheck %s -RUN: sancov -obj %p/Inputs/test-linux_x86_64 -covered_functions %p/Inputs/test-linux_x86_64-1.sancov | FileCheck --check-prefix=MULTIPLE_FILES %s -RUN: sancov -obj %p/Inputs/test-linux_x86_64 -demangle=0 -covered_functions %p/Inputs/test-linux_x86_64.sancov | FileCheck --check-prefix=NO_DEMANGLE %s +RUN: sancov -obj %p/Inputs/test-linux_x86_64 -covered-functions %p/Inputs/test-linux_x86_64.sancov | FileCheck %s +RUN: sancov -obj %p/Inputs/test-linux_x86_64 -covered-functions %p/Inputs/test-linux_x86_64-1.sancov | FileCheck --check-prefix=MULTIPLE_FILES %s +RUN: sancov -obj %p/Inputs/test-linux_x86_64 -demangle=0 -covered-functions %p/Inputs/test-linux_x86_64.sancov | FileCheck --check-prefix=NO_DEMANGLE %s CHECK: Inputs{{[/\\]}}test.cpp:12 bar(std::string) CHECK: Inputs{{[/\\]}}test.cpp:14 main Index: test/tools/sancov/not_covered_functions.test =================================================================== --- /dev/null +++ test/tools/sancov/not_covered_functions.test @@ -0,0 +1,7 @@ +REQUIRES: x86_64-linux +RUN: sancov -obj %p/Inputs/test-linux_x86_64 -not-covered-functions %p/Inputs/test-linux_x86_64.sancov | FileCheck %s +RUN: sancov -obj %p/Inputs/test-linux_x86_64 -not-covered-functions %p/Inputs/test-linux_x86_64-1.sancov | FileCheck --check-prefix=CHECK1 --allow-empty %s + +CHECK: Inputs{{[/\\]}}foo.cpp:5 foo() +CHECK1-NOT: {{.}}* + Index: tools/sancov/CMakeLists.txt =================================================================== --- tools/sancov/CMakeLists.txt +++ tools/sancov/CMakeLists.txt @@ -1,4 +1,8 @@ set(LLVM_LINK_COMPONENTS + AllTargetsAsmPrinters + AllTargetsDescs + AllTargetsDisassemblers + AllTargetsInfos DebugInfoDWARF DebugInfoPDB Object Index: tools/sancov/sancov.cc =================================================================== --- tools/sancov/sancov.cc +++ tools/sancov/sancov.cc @@ -12,6 +12,18 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/STLExtras.h" #include "llvm/DebugInfo/Symbolize/Symbolize.h" +#include "llvm/MC/MCAsmInfo.h" +#include "llvm/MC/MCContext.h" +#include "llvm/MC/MCDisassembler.h" +#include "llvm/MC/MCInst.h" +#include "llvm/MC/MCInstPrinter.h" +#include "llvm/MC/MCInstrAnalysis.h" +#include "llvm/MC/MCInstrInfo.h" +#include "llvm/MC/MCObjectFileInfo.h" +#include "llvm/MC/MCRegisterInfo.h" +#include "llvm/MC/MCSubtargetInfo.h" +#include "llvm/Object/Binary.h" +#include "llvm/Object/ObjectFile.h" #include "llvm/Support/CommandLine.h" #include "llvm/Support/Errc.h" #include "llvm/Support/ErrorOr.h" @@ -22,6 +34,8 @@ #include "llvm/Support/Path.h" #include "llvm/Support/PrettyStackTrace.h" #include "llvm/Support/Signals.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" #include "llvm/Support/ToolOutputFile.h" #include "llvm/Support/raw_ostream.h" @@ -35,13 +49,19 @@ // --------- COMMAND LINE FLAGS --------- -enum ActionType { PrintAction, CoveredFunctionsAction }; +enum ActionType { + PrintAction, + CoveredFunctionsAction, + NotCoveredFunctionsAction +}; cl::opt Action( cl::desc("Action (required)"), cl::Required, cl::values(clEnumValN(PrintAction, "print", "Print coverage addresses"), - clEnumValN(CoveredFunctionsAction, "covered_functions", + clEnumValN(CoveredFunctionsAction, "covered-functions", "Print all covered funcions."), + clEnumValN(NotCoveredFunctionsAction, "not-covered-functions", + "Print all not covered funcions."), clEnumValEnd)); static cl::list ClInputFiles(cl::Positional, cl::OneOrMore, @@ -68,31 +88,262 @@ // --------- +static void FailIfError(std::error_code Error) { + if (!Error) + return; + errs() << "Error: " << Error.message() << "(" << Error.value() << ")\n"; + exit(1); +} + template static void FailIfError(const ErrorOr &E) { - if (E) + FailIfError(E.getError()); +} + +static void FailIfNotEmpty(const std::string &E) { + if (E.empty()) return; + errs() << "Error: " << E << "\n"; + exit(1); +} - auto Error = E.getError(); - errs() << "Error: " << Error.message() << "(" << Error.value() << ")\n"; - exit(-2); +template +static void FailIfEmpty(const std::unique_ptr &Ptr, + const std::string &Message) { + if (Ptr.get()) + return; + errs() << "Error: " << Message << "\n"; + exit(1); } template static void readInts(const char *Start, const char *End, - std::vector *V) { + std::set *Ints) { const T *S = reinterpret_cast(Start); const T *E = reinterpret_cast(End); - V->reserve(E - S); - std::copy(S, E, std::back_inserter(*V)); + std::copy(S, E, std::inserter(*Ints, Ints->end())); +} + +struct FileLoc { + bool operator<(const FileLoc &RHS) const { + return std::tie(FileName, Line) < std::tie(RHS.FileName, RHS.Line); + } + + std::string FileName; + uint32_t Line; +}; + +struct FunctionLoc { + bool operator<(const FunctionLoc &RHS) const { + return std::tie(Loc, FunctionName) < std::tie(RHS.Loc, RHS.FunctionName); + } + + FileLoc Loc; + std::string FunctionName; +}; + +// Compute [FileLoc -> FunctionName] map for given addresses. +static std::map +computeFunctionsMap(const std::set &Addrs) { + std::map Fns; + + symbolize::LLVMSymbolizer::Options SymbolizerOptions; + SymbolizerOptions.Demangle = ClDemangle; + SymbolizerOptions.UseSymbolTable = true; + symbolize::LLVMSymbolizer Symbolizer(SymbolizerOptions); + + // Fill in Fns map. + for (auto Addr : Addrs) { + auto InliningInfo = Symbolizer.symbolizeInlinedCode(ClBinaryName, Addr); + FailIfError(InliningInfo); + for (uint32_t i = 0; i < InliningInfo->getNumberOfFrames(); ++i) { + auto FrameInfo = InliningInfo->getFrame(i); + SmallString<256> FileName(FrameInfo.FileName); + sys::path::remove_dots(FileName, /* remove_dot_dot */ true); + FileLoc Loc = {FileName.str(), FrameInfo.Line}; + Fns[Loc] = FrameInfo.FunctionName; + } + } + + return Fns; +} + +// Compute functions for given addresses. It keeps only the first +// occurence of a function within a file. +std::set computeFunctionLocs(const std::set &Addrs) { + std::map Fns = computeFunctionsMap(Addrs); + + std::set result; + std::string LastFileName; + std::set ProcessedFunctions; + + for (const auto &P : Fns) { + std::string FileName = P.first.FileName; + std::string FunctionName = P.second; + + if (LastFileName != FileName) + ProcessedFunctions.clear(); + LastFileName = FileName; + + if (!ProcessedFunctions.insert(FunctionName).second) + continue; + + result.insert(FunctionLoc{P.first, P.second}); + } + + return result; +} + +// Locate __sanitizer_cov function address. +static uint64_t findSanitizerCovFunction(const object::ObjectFile &O) { + for (const object::SymbolRef &Symbol : O.symbols()) { + ErrorOr AddressOrErr = Symbol.getAddress(); + FailIfError(AddressOrErr); + + ErrorOr Name = Symbol.getName(); + FailIfError(Name); + + if (Name.get() == "__sanitizer_cov") { + return AddressOrErr.get(); + } + } + FailIfNotEmpty("__sanitizer_cov not found"); + return 0; // not reachable. } -static std::string CommonPrefix(std::string A, std::string B) { - if (A.size() > B.size()) - return std::string(B.begin(), - std::mismatch(B.begin(), B.end(), A.begin()).first); +// Locate addresses of all coverage points in a file. Coverage point +// is defined as the 'address of instruction following __sanitizer_cov +// call - 1'. +static void getObjectCoveragePoints(const object::ObjectFile &O, + std::set *Addrs) { + Triple TheTriple("unknown-unknown-unknown"); + TheTriple.setArch(Triple::ArchType(O.getArch())); + auto TripleName = TheTriple.getTriple(); + + std::string Error; + const Target *TheTarget = TargetRegistry::lookupTarget(TripleName, Error); + FailIfNotEmpty(Error); + + std::unique_ptr STI( + TheTarget->createMCSubtargetInfo(TripleName, "", "")); + FailIfEmpty(STI, "no subtarget info for target " + TripleName); + + std::unique_ptr MRI( + TheTarget->createMCRegInfo(TripleName)); + FailIfEmpty(MRI, "no register info for target " + TripleName); + + std::unique_ptr AsmInfo( + TheTarget->createMCAsmInfo(*MRI, TripleName)); + FailIfEmpty(AsmInfo, "no asm info for target " + TripleName); + + std::unique_ptr MOFI(new MCObjectFileInfo); + MCContext Ctx(AsmInfo.get(), MRI.get(), MOFI.get()); + std::unique_ptr DisAsm( + TheTarget->createMCDisassembler(*STI, Ctx)); + FailIfEmpty(DisAsm, "no disassembler info for target " + TripleName); + + std::unique_ptr MII(TheTarget->createMCInstrInfo()); + FailIfEmpty(MII, "no instruction info for target " + TripleName); + + std::unique_ptr MIA( + TheTarget->createMCInstrAnalysis(MII.get())); + FailIfEmpty(MIA, "no instruction analysis info for target " + TripleName); + + uint64_t SanCovAddr = findSanitizerCovFunction(O); + + for (const auto Section : O.sections()) { + if (Section.isVirtual() || !Section.isText()) + continue; + uint64_t SectionAddr = Section.getAddress(); + uint64_t SectSize = Section.getSize(); + if (!SectSize) + continue; + + StringRef SectionName; + FailIfError(Section.getName(SectionName)); + + StringRef BytesStr; + FailIfError(Section.getContents(BytesStr)); + ArrayRef Bytes(reinterpret_cast(BytesStr.data()), + BytesStr.size()); + + for (uint64_t Index = 0, Size = 0; Index < Section.getSize(); + Index += Size) { + MCInst Inst; + if (!DisAsm->getInstruction(Inst, Size, Bytes.slice(Index), + SectionAddr + Index, nulls(), nulls())) { + if (Size == 0) + Size = 1; + continue; + } + uint64_t Target; + if (MIA->isCall(Inst) && + MIA->evaluateBranch(Inst, SectionAddr + Index, Size, Target)) { + if (Target == SanCovAddr) { + // Sanitizer coverage uses the address of the next instruction - 1. + Addrs->insert(Index + SectionAddr + Size - 1); + } + } + } + } +} + +static void getArchiveCoveragePoints(const object::Archive &A, + std::set *Addrs) { + for (auto &ErrorOrChild : A.children()) { + FailIfError(ErrorOrChild); + const object::Archive::Child &C = *ErrorOrChild; + ErrorOr> ChildOrErr = C.getAsBinary(); + FailIfError(ChildOrErr); + if (object::ObjectFile *O = + dyn_cast(&*ChildOrErr.get())) + getObjectCoveragePoints(*O, Addrs); + else + FailIfError(object::object_error::invalid_file_type); + } +} + +// Locate addresses of all coverage points in a file. Coverage point +// is defined as the 'address of instruction following __sanitizer_cov +// call - 1'. +std::set getCoveragePoints(std::string FileName) { + std::set Result; + + ErrorOr> BinaryOrErr = + object::createBinary(FileName); + FailIfError(BinaryOrErr); + + object::Binary &Binary = *BinaryOrErr.get().getBinary(); + if (object::Archive *A = dyn_cast(&Binary)) + getArchiveCoveragePoints(*A, &Result); + else if (object::ObjectFile *O = dyn_cast(&Binary)) + getObjectCoveragePoints(*O, &Result); else - return std::string(A.begin(), - std::mismatch(A.begin(), A.end(), B.begin()).first); + FailIfError(object::object_error::invalid_file_type); + + return Result; +} + +static void printFunctionLocs(const std::set &FnLocs, + raw_ostream &OS) { + if (FnLocs.empty()) + return; + + // Compute file names common prefix. + std::vector Paths; + Paths.reserve(FnLocs.size()); + for (const auto &FnLoc : FnLocs) + Paths.push_back(FnLoc.Loc.FileName); + std::string FilePrefix = llvm::sys::path::common_prefix(Paths); + + for (const FunctionLoc &FnLoc : FnLocs) { + std::string FileName = FnLoc.Loc.FileName; + + if (FileName.size() > FilePrefix.size()) + FileName = FileName.substr(FilePrefix.size()); + + OS << FileName << ":" << FnLoc.Loc.Line << " " << FnLoc.FunctionName + << "\n"; + } } class CoverageData { @@ -116,7 +367,7 @@ return make_error_code(errc::illegal_byte_sequence); } - auto Addrs = llvm::make_unique>(); + auto Addrs = llvm::make_unique>(); switch (Header->Bitness) { case Bitness64: @@ -138,15 +389,12 @@ // Merge multiple coverage data together. static std::unique_ptr merge(const std::vector> &Covs) { - std::set Addrs; + auto Addrs = llvm::make_unique>(); for (const auto &Cov : Covs) - Addrs.insert(Cov->Addrs->begin(), Cov->Addrs->end()); + Addrs->insert(Cov->Addrs->begin(), Cov->Addrs->end()); - auto AddrsVector = llvm::make_unique>( - Addrs.begin(), Addrs.end()); - return std::unique_ptr( - new CoverageData(std::move(AddrsVector))); + return std::unique_ptr(new CoverageData(std::move(Addrs))); } // Read list of files and merges their coverage info. @@ -163,83 +411,39 @@ } // Print coverage addresses. - void printAddrs(raw_ostream &out) { + void printAddrs(raw_ostream &OS) { for (auto Addr : *Addrs) { - out << "0x"; - out.write_hex(Addr); - out << "\n"; + OS << "0x"; + OS.write_hex(Addr); + OS << "\n"; } } // Print list of covered functions. // Line format: : - void printCoveredFunctions(raw_ostream &out) { - if (Addrs->empty()) - return; - symbolize::LLVMSymbolizer::Options SymbolizerOptions; - SymbolizerOptions.Demangle = ClDemangle; - symbolize::LLVMSymbolizer Symbolizer(SymbolizerOptions); - - struct FileLoc { - std::string FileName; - uint32_t Line; - bool operator<(const FileLoc &Rhs) const { - return std::tie(FileName, Line) < std::tie(Rhs.FileName, Rhs.Line); - } - }; - - // FileLoc -> FunctionName - std::map Fns; - - // Fill in Fns map. - for (auto Addr : *Addrs) { - auto InliningInfo = Symbolizer.symbolizeInlinedCode(ClBinaryName, Addr); - FailIfError(InliningInfo); - for (uint32_t i = 0; i < InliningInfo->getNumberOfFrames(); ++i) { - auto FrameInfo = InliningInfo->getFrame(i); - SmallString<256> FileName(FrameInfo.FileName); - sys::path::remove_dots(FileName, /* remove_dot_dot */ true); - FileLoc Loc = { FileName.str(), FrameInfo.Line }; - Fns[Loc] = FrameInfo.FunctionName; - } - } - - // Compute file names common prefix. - std::string FilePrefix = Fns.begin()->first.FileName; - for (const auto &P : Fns) - FilePrefix = CommonPrefix(FilePrefix, P.first.FileName); - - // Print first function occurence in a file. - { - std::string LastFileName; - std::set ProcessedFunctions; - - for (const auto &P : Fns) { - std::string FileName = P.first.FileName; - std::string FunctionName = P.second; - uint32_t Line = P.first.Line; - - if (LastFileName != FileName) - ProcessedFunctions.clear(); - LastFileName = FileName; - - if (!ProcessedFunctions.insert(FunctionName).second) - continue; - - // Don't strip prefix if we only have a single file. - if (FileName.size() > FilePrefix.size()) - FileName = FileName.substr(FilePrefix.size()); + void printCoveredFunctions(raw_ostream &OS) { + printFunctionLocs(computeFunctionLocs(*Addrs), OS); + } - out << FileName << ":" << Line << " " << FunctionName << "\n"; - } - } + // Print list of not covered functions. + // Line format: : + void printNotCoveredFunctions(raw_ostream &OS) { + std::set AllFns = + computeFunctionLocs(getCoveragePoints(ClBinaryName)); + std::set CoveredFns = computeFunctionLocs(*Addrs); + + std::set NotCoveredFns; + std::set_difference(AllFns.begin(), AllFns.end(), CoveredFns.begin(), + CoveredFns.end(), + std::inserter(NotCoveredFns, NotCoveredFns.end())); + printFunctionLocs(NotCoveredFns, OS); } - private: - explicit CoverageData(std::unique_ptr> Addrs) +private: + explicit CoverageData(std::unique_ptr> Addrs) : Addrs(std::move(Addrs)) {} - std::unique_ptr> Addrs; + std::unique_ptr> Addrs; }; } // namespace @@ -249,6 +453,10 @@ PrettyStackTraceProgram X(argc, argv); llvm_shutdown_obj Y; // Call llvm_shutdown() on exit. + llvm::InitializeAllTargetInfos(); + llvm::InitializeAllTargetMCs(); + llvm::InitializeAllDisassemblers(); + cl::ParseCommandLineOptions(argc, argv, "Sanitizer Coverage Processing Tool"); auto CovData = CoverageData::readAndMerge(ClInputFiles); @@ -263,5 +471,11 @@ CovData.get()->printCoveredFunctions(outs()); return 0; } + case NotCoveredFunctionsAction: { + CovData.get()->printNotCoveredFunctions(outs()); + return 0; + } } + + llvm_unreachable("unsupported action"); } Index: unittests/Support/Path.cpp =================================================================== --- unittests/Support/Path.cpp +++ unittests/Support/Path.cpp @@ -947,4 +947,21 @@ EXPECT_EQ("c", Path1); #endif } + +TEST(Support, CommonPrefix) { +#if defined(LLVM_ON_WIN32) +#define EXPECT_PATH_IS(expected_not_windows__, expected_windows__, path__) \ + EXPECT_EQ(expected_windows__, path__); +#else +#define EXPECT_PATH_IS(expected_not_windows__, expected_windows__, path__) \ + EXPECT_EQ(expected_not_windows__, path__); +#endif + EXPECT_PATH_IS("", "", path::common_prefix({})); + EXPECT_PATH_IS("/a/b/c", "\\a\\b\\a", path::common_prefix({"/a/b/c"})); + EXPECT_PATH_IS("/a/b", "\\a\\b", path::common_prefix({"/a/b", "/a/b"})); + EXPECT_PATH_IS("/a/", "\\a\\", path::common_prefix({"/a/b/c", "/a/d"})); + EXPECT_PATH_IS("/", "\\", path::common_prefix({"/usr/a", "/usb/b"})); +#undef EXPECT_PATH_IS +} + } // anonymous namespace