[dsymutil] Skip duplicates files with identical time stamps in the debug map

[JDevlieghere]

Summary

Static archives can contain multiple files with the same file name, in which case the timestamp is used to disambiguate. Because timestamps are expressed in seconds since epoch timestamp collisions are far from impossible. Furthermore, to facilitate reproducible builds, the static linker can be told to emit no timestamps at all.

dsymutil already detects timestamp mismatches between the debug map and the object files. However, it does not handle timestamp collisions within the debug maps (STABS). Currently, we arbitrarily pick the first debug map entry and ignore the rest. This is incorrect: if a symbol exists in multiple object files, the linker might not have picked the one from the first object file. This also results in missing symbol warnings for all the symbols not defined in the first object file.

Given that in this scenario, dsymutil does not have enough information to disambiguate, it should instead print a single informative warning and skip the ambiguous debug map objects.

rdar://110374836

[JDevlieghere]

s/time stamp/timestamp/

[pete]

LGTM!

[aprantl]

llvm/tools/dsymutil/MachODebugMapParser.cpp

246

Maybe also use a DenseSet here? Once we're printing the warning the overhead for the memory allocation probably doesn't matter any more.

710

Is it legal that Empty == Tombstone?

[aprantl]

llvm/tools/dsymutil/MachODebugMapParser.cpp

48

A hack I used in other places was to use a struct that inherits from std::pair<StringRef, uint64_t> and write accessors, then you don't need to define all the hashing and comparison functions.

[JDevlieghere]

Use a std::pair instead of a custom struct to avoid hasing boilerplate.

[leonardchan]

Hi. Looks like the static-archive-collision.test test is failing on our builders at https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8778475674577642785/overview. Would you mind sending out a fix or revert?

[JDevlieghere]

In D152585#4414840, @leonardchan wrote:

Hi. Looks like the static-archive-collision.test test is failing on our builders at https://luci-milo.appspot.com/ui/p/fuchsia/builders/toolchain.ci/clang-linux-x64/b8778475674577642785/overview. Would you mind sending out a fix or revert?

This should've been fixed by 9cacc22640ef.

llvm/test/tools/dsymutil/ARM/static-archive-collision.test

+$ cat f.c
+int f() {
+  volatile int i;
+  return i;
+}
+$ cat g.c
+int g() {
+  volatile int i;
+  return i;
+}
+$ cat main.c
+int f();
+int g();
+
+int main() {
+  return f() + g();
+}
+$ clang -g f.c -c -o f/foo.o
+$ clang -g g.c -c -o g/foo.o
+$ libtool -static f/foo.o g/foo.o -o foo.a
+$ clang main.o foo.a -o main.out
+
+RUN: dsymutil -oso-prepend-path %p/../Inputs %p/../Inputs/private/tmp/collision/main.out --dump-debug-map 2>&1 | FileCheck %s
+CHECK: skipping debug map object with duplicate name and timestamp: 1969-12-31 16:00:00.000000000 /private/tmp/collision/foo.a(foo.o)
+CHECK-NOT: could not find object file symbol for symbol _g
+CHECK-NOT: could not find object file symbol for symbol _f

llvm/tools/dsymutil/MachODebugMapParser.cpp

 //===- tools/dsymutil/MachODebugMapParser.cpp - Parse STABS debug maps ----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "BinaryHolder.h"
 #include "DebugMap.h"
 #include "MachOUtils.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/Object/MachO.h"
+#include "llvm/Support/Chrono.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
 #include <optional>
 #include <vector>
 
 namespace {
 using namespace llvm;
 using namespace llvm::dsymutil;
 using namespace llvm::object;
 
 class MachODebugMapParser {
 public:
   MachODebugMapParser(llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS,
                       StringRef BinaryPath, ArrayRef<std::string> Archs,
                       StringRef PathPrefix = "",
                       bool PaperTrailWarnings = false, bool Verbose = false)
       : BinaryPath(std::string(BinaryPath)), Archs(Archs.begin(), Archs.end()),
         PathPrefix(std::string(PathPrefix)),
         PaperTrailWarnings(PaperTrailWarnings), BinHolder(VFS, Verbose),
-        CurrentDebugMapObject(nullptr) {}
+        CurrentDebugMapObject(nullptr), SkipDebugMapObject(false) {}
 
   /// Parses and returns the DebugMaps of the input binary. The binary contains
   /// multiple maps in case it is a universal binary.
   /// \returns an error in case the provided BinaryPath doesn't exist
   /// or isn't of a supported type.
   ErrorOr<std::vector<std::unique_ptr<DebugMap>>> parse();
 
   /// Walk the symbol table and dump it.
   bool dumpStab();
 
+  using OSO = std::pair<llvm::StringRef, uint64_t>;
+
 private:
   std::string BinaryPath;
   SmallVector<StringRef, 1> Archs;
   std::string PathPrefix;
   bool PaperTrailWarnings;
 
   /// Owns the MemoryBuffer for the main binary.
   BinaryHolder BinHolder;
private:
   StringMap<std::optional<uint64_t>> CurrentObjectAliasMap;
 
   /// If CurrentObjectAliasMap has been computed for a given address.
   SmallSet<uint64_t, 4> SeenAliasValues;
 
   /// Element of the debug map corresponding to the current object file.
   DebugMapObject *CurrentDebugMapObject;
 
+  /// Whether we need to skip the current debug map object.
+  bool SkipDebugMapObject;
+
   /// Holds function info while function scope processing.
   const char *CurrentFunctionName;
   uint64_t CurrentFunctionAddress;
 
   std::unique_ptr<DebugMap> parseOneBinary(const MachOObjectFile &MainBinary,
                                            StringRef BinaryPath);
+  void handleStabDebugMap(
+      const MachOObjectFile &MainBinary,
+      std::function<void(uint32_t, uint8_t, uint8_t, uint16_t, uint64_t)> F);
 
   void
   switchToNewDebugMapObject(StringRef Filename,
                             sys::TimePoint<std::chrono::seconds> Timestamp);
   void resetParserState();
   uint64_t getMainBinarySymbolAddress(StringRef Name);
   std::vector<StringRef> getMainBinarySymbolNames(uint64_t Value);
   void loadMainBinarySymbols(const MachOObjectFile &MainBinary);
   void loadCurrentObjectFileSymbols(const object::MachOObjectFile &Obj);
+
+  void handleStabOSOEntry(uint32_t StringIndex, uint8_t Type,
+                          uint8_t SectionIndex, uint16_t Flags, uint64_t Value,
+                          llvm::DenseSet<OSO> &OSOs,
+                          llvm::SmallSet<OSO, 4> &Duplicates);
   void handleStabSymbolTableEntry(uint32_t StringIndex, uint8_t Type,
                                   uint8_t SectionIndex, uint16_t Flags,
-                                  uint64_t Value);
+                                  uint64_t Value,
+                                  const llvm::SmallSet<OSO, 4> &Duplicates);
 
-  template <typename STEType> void handleStabDebugMapEntry(const STEType &STE) {
-    handleStabSymbolTableEntry(STE.n_strx, STE.n_type, STE.n_sect, STE.n_desc,
-                               STE.n_value);
+  template <typename STEType>
+  void handleStabDebugMapEntry(
+      const STEType &STE,
+      std::function<void(uint32_t, uint8_t, uint8_t, uint16_t, uint64_t)> F) {
+    F(STE.n_strx, STE.n_type, STE.n_sect, STE.n_desc, STE.n_value);
   }
 
   void addCommonSymbols();
 
   /// Dump the symbol table output header.
   void dumpSymTabHeader(raw_ostream &OS, StringRef Arch);
 
   /// Dump the contents of nlist entries.

 /// file. This is to be called after an object file is finished
 /// processing.
 void MachODebugMapParser::resetParserState() {
   CommonSymbols.clear();
   CurrentObjectAddresses.clear();
   CurrentObjectAliasMap.clear();
   SeenAliasValues.clear();
   CurrentDebugMapObject = nullptr;
+  SkipDebugMapObject = false;
 }
 
 /// Commons symbols won't show up in the symbol map but might need to be
 /// relocated. We can add them to the symbol table ourselves by combining the
 /// information in the object file (the symbol name) and the main binary (the
 /// address).
 void MachODebugMapParser::addCommonSymbols() {
   for (auto &CommonSymbol : CommonSymbols) {
void MachODebugMapParser::switchToNewDebugMapObject(
   loadCurrentObjectFileSymbols(*Object);
 }
 
 static std::string getArchName(const object::MachOObjectFile &Obj) {
   Triple T = Obj.getArchTriple();
   return std::string(T.getArchName());
 }
 
+void MachODebugMapParser::handleStabDebugMap(
+    const MachOObjectFile &MainBinary,
+    std::function<void(uint32_t, uint8_t, uint8_t, uint16_t, uint64_t)> F) {
+  for (const SymbolRef &Symbol : MainBinary.symbols()) {
+    const DataRefImpl &DRI = Symbol.getRawDataRefImpl();
+    if (MainBinary.is64Bit())
+      handleStabDebugMapEntry(MainBinary.getSymbol64TableEntry(DRI), F);
+    else
+      handleStabDebugMapEntry(MainBinary.getSymbolTableEntry(DRI), F);
+  }
+}
+
 std::unique_ptr<DebugMap>
 MachODebugMapParser::parseOneBinary(const MachOObjectFile &MainBinary,
                                     StringRef BinaryPath) {
   Result = std::make_unique<DebugMap>(MainBinary.getArchTriple(), BinaryPath,
                                       MainBinary.getUuid());
   loadMainBinarySymbols(MainBinary);
   MainBinaryStrings = MainBinary.getStringTableData();
-  for (const SymbolRef &Symbol : MainBinary.symbols()) {
-    const DataRefImpl &DRI = Symbol.getRawDataRefImpl();
-    if (MainBinary.is64Bit())
-      handleStabDebugMapEntry(MainBinary.getSymbol64TableEntry(DRI));
-    else
-      handleStabDebugMapEntry(MainBinary.getSymbolTableEntry(DRI));
-  }
+
+  // Static archives can contain multiple object files with identical names, in
+  // which case the timestamp is used to disambiguate. However, if both are
+  // identical, there's no way to tell them apart. Detect this and skip
+  // duplicate debug map objects.
+  llvm::DenseSet<OSO> OSOs;
+  llvm::SmallSet<OSO, 4> Duplicates;
+
+  // Iterate over all the STABS to find duplicate OSO entries.
+  handleStabDebugMap(MainBinary,
+                     [&](uint32_t StringIndex, uint8_t Type,
+                         uint8_t SectionIndex, uint16_t Flags, uint64_t Value) {
+                       handleStabOSOEntry(StringIndex, Type, SectionIndex,
+                                          Flags, Value, OSOs, Duplicates);
+                     });
+
+  // Print an informative warning with the duplicate object file name and time
+  // stamp.
+  for (const auto &OSO : Duplicates) {
+    std::string Buffer;
+    llvm::raw_string_ostream OS(Buffer);
+    OS << sys::TimePoint<std::chrono::seconds>(sys::toTimePoint(OSO.second));
+    Warning("skipping debug map object with duplicate name and timestamp: " +
+            OS.str() + Twine(" ") + Twine(OSO.first));
+  }
+
+  // Build the debug map by iterating over the STABS again but ignore the
+  // duplicate debug objects.
+  handleStabDebugMap(MainBinary, [&](uint32_t StringIndex, uint8_t Type,
+                                     uint8_t SectionIndex, uint16_t Flags,
+                                     uint64_t Value) {
+    handleStabSymbolTableEntry(StringIndex, Type, SectionIndex, Flags, Value,
+                               Duplicates);
+  });
 
   resetParserState();
   return std::move(Result);
 }
 
 // Table that maps Darwin's Mach-O stab constants to strings to allow printing.
 // llvm-nm has very similar code, the strings used here are however slightly
 // different and part of the interface of dsymutil (some project's build-systems
ErrorOr<std::vector<std::unique_ptr<DebugMap>>> MachODebugMapParser::parse() {
   std::vector<std::unique_ptr<DebugMap>> Results;
   for (const auto *Object : *Objects)
     if (shouldLinkArch(Archs, Object->getArchTriple().getArchName()))
       Results.push_back(parseOneBinary(*Object, BinaryPath));
 
   return std::move(Results);
 }
 
+void MachODebugMapParser::handleStabOSOEntry(
+    uint32_t StringIndex, uint8_t Type, uint8_t SectionIndex, uint16_t Flags,
+    uint64_t Value, llvm::DenseSet<OSO> &OSOs,
+    llvm::SmallSet<OSO, 4> &Duplicates) {
+  if (Type != MachO::N_OSO)
+    return;
+
+  OSO O(&MainBinaryStrings.data()[StringIndex], Value);
+  if (!OSOs.insert(O).second)
+    Duplicates.insert(O);
+}
+
 /// Interpret the STAB entries to fill the DebugMap.
-void MachODebugMapParser::handleStabSymbolTableEntry(uint32_t StringIndex,
-                                                     uint8_t Type,
-                                                     uint8_t SectionIndex,
-                                                     uint16_t Flags,
-                                                     uint64_t Value) {
+void MachODebugMapParser::handleStabSymbolTableEntry(
+    uint32_t StringIndex, uint8_t Type, uint8_t SectionIndex, uint16_t Flags,
+    uint64_t Value, const llvm::SmallSet<OSO, 4> &Duplicates) {
   if (!(Type & MachO::N_STAB))
     return;
 
   const char *Name = &MainBinaryStrings.data()[StringIndex];
 
   // An N_OSO entry represents the start of a new object file description.
-  if (Type == MachO::N_OSO)
+  if (Type == MachO::N_OSO) {
+    if (Duplicates.count(OSO(Name, Value))) {
+      SkipDebugMapObject = true;
+      return;
+    }
     return switchToNewDebugMapObject(Name, sys::toTimePoint(Value));
+  }
+
+  if (SkipDebugMapObject)
+    return;
 
   if (Type == MachO::N_AST) {
     SmallString<80> Path(PathPrefix);
     sys::path::append(Path, Name);
     Result->addDebugMapObject(Path, sys::toTimePoint(Value), Type);
     return;
   }
 

 namespace llvm {
 namespace dsymutil {
 llvm::ErrorOr<std::vector<std::unique_ptr<DebugMap>>>
 parseDebugMap(llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS,
               StringRef InputFile, ArrayRef<std::string> Archs,
               StringRef PrependPath, bool PaperTrailWarnings, bool Verbose,
               bool InputIsYAML) {
   if (InputIsYAML)
     return DebugMap::parseYAMLDebugMap(InputFile, PrependPath, Verbose);
 
   MachODebugMapParser Parser(VFS, InputFile, Archs, PrependPath,
                              PaperTrailWarnings, Verbose);
   return Parser.parse();
 }
 
 bool dumpStab(llvm::IntrusiveRefCntPtr<llvm::vfs::FileSystem> VFS,
               StringRef InputFile, ArrayRef<std::string> Archs,
               StringRef PrependPath) {
   MachODebugMapParser Parser(VFS, InputFile, Archs, PrependPath, false);
   return Parser.dumpStab();
 }
 } // namespace dsymutil
 } // namespace llvm