LLD: Core: Fix file ordinals of archive members.

[ruiu]

Summary

Previously archive file members got random-ish file ordinals because
file ordinals were assigned in the same order as the resolver needs
them. In LLD, atoms in the output should be ordered in the same as
in the command line, but it was not true for archive files.

This patch (partially) fixes the issue. Now, member files get larger
file ordinals than the archive file but not larger than the next file.
So, after atoms are sorted by file ordinals, they are sorted in the
same order as in the command line.

The reason why it's partial is because the order of members in the
same archive still depends on the resolution order. This needs to be
fixed in future.

[• shankar.easwaran]

At least on Gnu/ELF what I have seen is the order in the output is how symbols/files were resolved. No?? Do you have a test that fails on Gnu flavor and ELF that doesn't match real gnu behavior?

[ruiu]

I believed that you wrote this code and was aware of the thing. But as a refresher, the order of symbol resolution and file resolution are not the same. Only object files are visited in order. Files in an archive file is visited only when it's needed. If archive files are grouped with -( and -), the order to visit files in the archives is not the same as the order in the input file list.

Previously we set a new and largest ordinal to a file in an archive file as we visit that. So the files in archive files got ordinals in the resolution order, not in the input file order.

[shankarke]

lib/Core/Resolver.cpp

84

The member ordinal seems wrong, it should be the next ordinal available for GNU.

include/lld/Core/LinkingContext.h

public:
   /// run on the merged/linked graph of all input files.
   virtual void addPasses(PassManager &pm);
 
   /// Calls through to the writeFile() method on the specified Writer.
   ///
   /// \param linkedFile This is the merged/linked graph of all input file Atoms.
   virtual std::error_code writeFile(const File &linkedFile) const;
 
-  /// Return the next ordinal and Increment it.
-  virtual uint64_t getNextOrdinalAndIncrement() const { return _nextOrdinal++; }
+  /// Return the next file ordinal. File ordinals are used by the writer
+  /// to sort file contents as their file order in the command line. All files
+  /// including archive files get one file ordinal. Ordinals are large numbers.
+  /// Least significant 32 bits are reserved for archive file members.
+  uint64_t nextFileOrdinal() const { return _nextFileOrdinal++ << 32; }
 
   // This function is called just before the Resolver kicks in.
   // Derived classes may use that chance to rearrange the input files.
   virtual void maybeSortInputFiles() {}
 
   TaskGroup &getTaskGroup() { return _taskGroup; }
 
   /// @}
protected:
   bool _allowShlibUndefines;
   OutputFileType _outputFileType;
   std::vector<StringRef> _deadStripRoots;
   std::map<std::string, std::string> _aliasSymbols;
   std::vector<const char *> _llvmOptions;
   StringRefVector _initialUndefinedSymbols;
   std::vector<std::unique_ptr<Node>> _nodes;
   mutable llvm::BumpPtrAllocator _allocator;
-  mutable uint64_t _nextOrdinal;
+  mutable uint64_t _nextFileOrdinal;
   Registry _registry;
 
 private:
   /// Validate the subclass bits. Only called by validate.
   virtual bool validateImpl(raw_ostream &diagnostics) = 0;
   TaskGroup _taskGroup;
 };
 
 } // end namespace lld
 
 #endif

include/lld/Core/Resolver.h

 class LinkingContext;
 
 /// \brief The Resolver is responsible for merging all input object files
 /// and producing a merged graph.
 class Resolver {
 public:
   Resolver(LinkingContext &ctx)
       : _ctx(ctx), _symbolTable(ctx), _result(new MergedFile()),
-        _fileIndex(0) {}
+        _memberOrdinal(1), _fileIndex(0) {}
 
   // InputFiles::Handler methods
   void doDefinedAtom(const DefinedAtom&);
   bool doUndefinedAtom(const UndefinedAtom &);
   void doSharedLibraryAtom(const SharedLibraryAtom &);
   void doAbsoluteAtom(const AbsoluteAtom &);
 
   // Handle files, this adds atoms from the current file thats
private:
   LinkingContext &_ctx;
   SymbolTable _symbolTable;
   std::vector<const Atom *>     _atoms;
   std::set<const Atom *>        _deadStripRoots;
   llvm::DenseSet<const Atom *>  _liveAtoms;
   llvm::DenseSet<const Atom *>  _deadAtoms;
   std::unique_ptr<MergedFile>   _result;
   llvm::DenseMap<const Atom *, llvm::DenseSet<const Atom *>> _reverseRef;
+  uint64_t _memberOrdinal;
 
   // --start-group and --end-group
   std::vector<File *> _files;
   std::map<File *, bool> _newUndefinesAdded;
   size_t _fileIndex;
 
   // Preloading
   std::map<StringRef, ArchiveLibraryFile *> _archiveMap;
 };
 
 } // namespace lld
 
 #endif // LLD_CORE_RESOLVER_H

lib/Core/LinkingContext.cpp

LinkingContext::LinkingContext()
     : _deadStrip(false), _allowDuplicates(false),
       _globalsAreDeadStripRoots(false),
       _searchArchivesToOverrideTentativeDefinitions(false),
       _searchSharedLibrariesToOverrideTentativeDefinitions(false),
       _warnIfCoalesableAtomsHaveDifferentCanBeNull(false),
       _warnIfCoalesableAtomsHaveDifferentLoadName(false),
       _printRemainingUndefines(true), _allowRemainingUndefines(false),
       _logInputFiles(false), _allowShlibUndefines(false),
-      _outputFileType(OutputFileType::Default), _nextOrdinal(0) {}
+      _outputFileType(OutputFileType::Default), _nextFileOrdinal(1) {}
 
 LinkingContext::~LinkingContext() {}
 
 bool LinkingContext::validate(raw_ostream &diagnostics) {
   return validateImpl(diagnostics);
 }
 
 std::error_code LinkingContext::writeFile(const File &linkedFile) const {

lib/Core/Resolver.cpp

 bool Resolver::handleArchiveFile(const File &file) {
   const ArchiveLibraryFile *archiveFile = cast<ArchiveLibraryFile>(&file);
   bool searchForOverrides =
       _ctx.searchArchivesToOverrideTentativeDefinitions();
   bool undefAdded = false;
   forEachUndefines(searchForOverrides,
                    [&](StringRef undefName, bool dataSymbolOnly) {
     if (const File *member = archiveFile->find(undefName, dataSymbolOnly)) {
-      member->setOrdinal(_ctx.getNextOrdinalAndIncrement());
+      member->setOrdinal(archiveFile->ordinal() + _memberOrdinal++);
       const_cast<File *>(member)->beforeLink();
       undefAdded = handleFile(*member) || undefAdded;
     }
   });
   return undefAdded;
 }
 
 void Resolver::handleSharedLibrary(const File &file) {
for (;;) {
     case File::kindObject:
       // The same file may be visited more than once if the file is
       // in --start-group and --end-group. Only library files should
       // be processed more than once.
       if (seen.count(file))
         break;
       seen.insert(file);
       assert(!file->hasOrdinal());
-      file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
+      file->setOrdinal(_ctx.nextFileOrdinal());
       undefAdded = handleFile(*file);
       break;
     case File::kindArchiveLibrary:
       if (!file->hasOrdinal())
-        file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
+        file->setOrdinal(_ctx.nextFileOrdinal());
       undefAdded = handleArchiveFile(*file);
       break;
     case File::kindSharedLibrary:
       if (!file->hasOrdinal())
-        file->setOrdinal(_ctx.getNextOrdinalAndIncrement());
+        file->setOrdinal(_ctx.nextFileOrdinal());
       handleSharedLibrary(*file);
       break;
     }
     _newUndefinesAdded[file] = undefAdded;
   }
 }
 
 // switch all references to undefined or coalesced away atoms

lib/ReaderWriter/ELF/AArch64/AArch64RelocationPass.cpp

public:
   ArrayRef<uint8_t> rawContent() const override {
     return ArrayRef<uint8_t>(AArch64PltAtomContent, 16);
   }
 };
 
 class ELFPassFile : public SimpleFile {
 public:
   ELFPassFile(const ELFLinkingContext &eti) : SimpleFile("ELFPassFile") {
-    setOrdinal(eti.getNextOrdinalAndIncrement());
+    setOrdinal(eti.nextFileOrdinal());
   }
 
   llvm::BumpPtrAllocator _alloc;
 };
 
 /// \brief CRTP base for handling relocations.
 template <class Derived> class AArch64RelocationPass : public Pass {
   /// \brief Handle a specific reference.

lib/ReaderWriter/ELF/ARM/ARMRelocationPass.cpp

public:
   ArrayRef<uint8_t> rawContent() const override {
     return llvm::makeArrayRef(Veneer_THM_B_BL_StaticAtomContent);
   }
 };
 
 class ELFPassFile : public SimpleFile {
 public:
   ELFPassFile(const ELFLinkingContext &eti) : SimpleFile("ELFPassFile") {
-    setOrdinal(eti.getNextOrdinalAndIncrement());
+    setOrdinal(eti.nextFileOrdinal());
   }
 
   llvm::BumpPtrAllocator _alloc;
 };
 
 /// \brief CRTP base for handling relocations.
 template <class Derived> class ARMRelocationPass : public Pass {
   /// \brief Handle a specific reference.

lib/ReaderWriter/ELF/Hexagon/HexagonTargetHandler.cpp

public:
   ArrayRef<uint8_t> rawContent() const override {
     return makeArrayRef(hexagonPltAtomContent);
   }
 };
 
 class ELFPassFile : public SimpleFile {
 public:
   ELFPassFile(const ELFLinkingContext &eti) : SimpleFile("ELFPassFile") {
-    setOrdinal(eti.getNextOrdinalAndIncrement());
+    setOrdinal(eti.nextFileOrdinal());
   }
 
   llvm::BumpPtrAllocator _alloc;
 };
 
 /// \brief Create GOT and PLT entries for relocations. Handles standard GOT/PLT
 template <class Derived> class GOTPLTPass : public Pass {
   /// \brief Handle a specific reference.

lib/ReaderWriter/ELF/Mips/MipsRelocationPass.cpp

ArrayRef<uint8_t> rawContent() const override {
     return llvm::makeArrayRef(micromipsLA25AtomContent);
   }
 };
 
 class RelocationPassFile : public SimpleFile {
 public:
   RelocationPassFile(const ELFLinkingContext &ctx)
       : SimpleFile("RelocationPassFile") {
-    setOrdinal(ctx.getNextOrdinalAndIncrement());
+    setOrdinal(ctx.nextFileOrdinal());
   }
 
   llvm::BumpPtrAllocator _alloc;
 };
 
 template <typename ELFT> class RelocationPass : public Pass {
 public:
   RelocationPass(MipsLinkingContext &ctx);

lib/ReaderWriter/ELF/X86_64/X86_64RelocationPass.cpp

public:
   ArrayRef<uint8_t> rawContent() const override {
     return ArrayRef<uint8_t>(x86_64PltAtomContent, 16);
   }
 };
 
 class ELFPassFile : public SimpleFile {
 public:
   ELFPassFile(const ELFLinkingContext &eti) : SimpleFile("ELFPassFile") {
-    setOrdinal(eti.getNextOrdinalAndIncrement());
+    setOrdinal(eti.nextFileOrdinal());
   }
 
   llvm::BumpPtrAllocator _alloc;
 };
 
 /// \brief CRTP base for handling relocations.
 template <class Derived> class RelocationPass : public Pass {
   /// \brief Handle a specific reference.

lib/ReaderWriter/PECOFF/Atoms.h

 
 // An instance of this class represents "input file" for atoms created in a
 // pass. Atoms need to be associated to an input file even if it's not read from
 // a file, so we use this class for that.
 class VirtualFile : public SimpleFile {
 public:
   VirtualFile(const LinkingContext &ctx)
       : SimpleFile("<virtual-file>"), _nextOrdinal(0) {
-    setOrdinal(ctx.getNextOrdinalAndIncrement());
+    setOrdinal(ctx.nextFileOrdinal());
   }
 
   uint64_t getNextOrdinal() { return _nextOrdinal++; }
 
 private:
   uint64_t _nextOrdinal;
 };
 

test/mach-o/library-rescan.yaml

undefined-symbols:
   - name:            _bar
     type:            N_UNDF
     scope:           [ N_EXT ]
     value:           0x0000000000000000
 
 ...
 
 # CHECK:  {{[0-9a-f]+}} (__TEXT,__text) external _main
-# CHECK:  {{[0-9a-f]+}} (__TEXT,__text) external _bar
 # CHECK:  {{[0-9a-f]+}} (__TEXT,__text) external _foo
+# CHECK:  {{[0-9a-f]+}} (__TEXT,__text) external _bar