[BOLT] Change order of new sections

[maksfb]

Summary

While the order of new sections in the output binary was deterministic
in the past (i.e. there was no run-to-run variation), it wasn't always
rational as we used size to define the precedence of allocatable
sections within "code" or "data" groups (probably unintentionally).
Fix that by defining stricter section-ordering rules.

Other than the order of sections, this should be NFC.

[maksfb]

Fix MachO. Add a test case.

[rafauler]

LGTM

bolt/include/bolt/Core/BinarySection.h

 
 class BinaryContext;
 class BinaryData;
 
 /// A class to manage binary sections that also manages related relocations.
 class BinarySection {
   friend class BinaryContext;
 
+  /// Count the number of sections created.
+  static uint64_t Count;
+
   BinaryContext &BC;           // Owning BinaryContext
   std::string Name;            // Section name
   const SectionRef Section;    // SectionRef (may be null)
   StringRef Contents;          // Input section contents
   const uint64_t Address;      // Address of section in input binary (may be 0)
   const uint64_t Size;         // Input section size
   uint64_t InputFileOffset{0}; // Offset in the input binary
   unsigned Alignment;          // alignment in bytes (must be > 0)
class BinarySection {
   bool IsFinalized{false};         // Has this section had output information
                                    // finalized?
   std::string OutputName;          // Output section name (if the section has
                                    // been renamed)
   uint64_t OutputAddress{0};       // Section address for the rewritten binary.
   uint64_t OutputSize{0};          // Section size in the rewritten binary.
   uint64_t OutputFileOffset{0};    // File offset in the rewritten binary file.
   StringRef OutputContents;        // Rewritten section contents.
+  const uint64_t SectionNumber;    // Order in which the section was created.
   unsigned SectionID{-1u};         // Unique ID used for address mapping.
                                    // Set by ExecutableFileMemoryManager.
   uint32_t Index{0};               // Section index in the output file.
   mutable bool IsReordered{false}; // Have the contents been reordered?
   bool IsAnonymous{false};         // True if the name should not be included
                                    // in the output file.
 
   uint64_t hash(const BinaryData &BD,
public:
   /// Copy a section.
   explicit BinarySection(BinaryContext &BC, StringRef Name,
                          const BinarySection &Section)
       : BC(BC), Name(Name), Section(Section.getSectionRef()),
         Contents(Section.getContents()), Address(Section.getAddress()),
         Size(Section.getSize()), Alignment(Section.getAlignment()),
         ELFType(Section.getELFType()), ELFFlags(Section.getELFFlags()),
         Relocations(Section.Relocations),
-        PendingRelocations(Section.PendingRelocations), OutputName(Name) {}
+        PendingRelocations(Section.PendingRelocations), OutputName(Name),
+        SectionNumber(++Count) {}
 
   BinarySection(BinaryContext &BC, SectionRef Section)
       : BC(BC), Name(getName(Section)), Section(Section),
         Contents(getContents(Section)), Address(Section.getAddress()),
         Size(Section.getSize()), Alignment(Section.getAlignment()),
-        OutputName(Name) {
+        OutputName(Name), SectionNumber(++Count) {
     if (isELF()) {
       ELFType = ELFSectionRef(Section).getType();
       ELFFlags = ELFSectionRef(Section).getFlags();
       InputFileOffset = ELFSectionRef(Section).getOffset();
     } else if (isMachO()) {
       auto *O = cast<MachOObjectFile>(Section.getObject());
       InputFileOffset =
           O->is64Bit() ? O->getSection64(Section.getRawDataRefImpl()).offset
                        : O->getSection(Section.getRawDataRefImpl()).offset;
     }
   }
 
   // TODO: pass Data as StringRef/ArrayRef? use StringRef::copy method.
   BinarySection(BinaryContext &BC, StringRef Name, uint8_t *Data, uint64_t Size,
                 unsigned Alignment, unsigned ELFType, unsigned ELFFlags)
       : BC(BC), Name(Name),
         Contents(reinterpret_cast<const char *>(Data), Data ? Size : 0),
         Address(0), Size(Size), Alignment(Alignment), ELFType(ELFType),
         ELFFlags(ELFFlags), IsFinalized(true), OutputName(Name),
-        OutputSize(Size), OutputContents(Contents) {
+        OutputSize(Size), OutputContents(Contents), SectionNumber(++Count) {
     assert(Alignment > 0 && "section alignment must be > 0");
   }
 
   ~BinarySection();
 
   /// Helper function to generate the proper ELF flags from section properties.
   static unsigned getFlags(bool IsReadOnly = true, bool IsText = false,
                            bool IsAllocatable = false) {
public:
   }
 
   bool operator!=(const BinarySection &Other) const {
     return !operator==(Other);
   }
 
   // Order sections by their immutable properties.
   bool operator<(const BinarySection &Other) const {
-    return (getAddress() < Other.getAddress() ||
-            (getAddress() == Other.getAddress() &&
-             (getSize() < Other.getSize() ||
-              (getSize() == Other.getSize() && getName() < Other.getName()))));
+    // Allocatable before non-allocatable.
+    if (isAllocatable() != Other.isAllocatable())
+      return isAllocatable() > Other.isAllocatable();
+
+    // Input sections take precedence.
+    if (hasSectionRef() != Other.hasSectionRef())
+      return hasSectionRef() > Other.hasSectionRef();
+
+    // Compare allocatable input sections by their address.
+    if (getAddress() != Other.getAddress())
+      return getAddress() < Other.getAddress();
+    if (getAddress() && getSize() != Other.getSize())
+      return getSize() < Other.getSize();
+
+    // Code before data.
+    if (isText() != Other.isText())
+      return isText() > Other.isText();
+
+    // Read-only before writable.
+    if (isReadOnly() != Other.isReadOnly())
+      return isReadOnly() > Other.isReadOnly();
+
+    // BSS at the end.
+    if (isBSS() != Other.isBSS())
+      return isBSS() < Other.isBSS();
+
+    // Otherwise, preserve the order of creation.
+    return SectionNumber < Other.SectionNumber;
   }
 
   ///
   /// Basic property access.
   ///
   BinaryContext &getBinaryContext() { return BC; }
   bool isELF() const;
   bool isMachO() const;
   StringRef getName() const { return Name; }
   uint64_t getAddress() const { return Address; }
   uint64_t getEndAddress() const { return Address + Size; }
   uint64_t getSize() const { return Size; }
   uint64_t getInputFileOffset() const { return InputFileOffset; }
   uint64_t getAlignment() const { return Alignment; }
   bool isText() const {
     if (isELF())
       return (ELFFlags & ELF::SHF_EXECINSTR);
-    return getSectionRef().isText();
+    return hasSectionRef() && getSectionRef().isText();
   }
   bool isData() const {
     if (isELF())
       return (ELFType == ELF::SHT_PROGBITS &&
               (ELFFlags & (ELF::SHF_ALLOC | ELF::SHF_WRITE)));
-    return getSectionRef().isData();
+    return hasSectionRef() && getSectionRef().isData();
   }
   bool isBSS() const {
     return (ELFType == ELF::SHT_NOBITS &&
             (ELFFlags & (ELF::SHF_ALLOC | ELF::SHF_WRITE)));
   }
   bool isTLS() const { return (ELFFlags & ELF::SHF_TLS); }
   bool isTBSS() const { return isBSS() && isTLS(); }
   bool isVirtual() const { return ELFType == ELF::SHT_NOBITS; }

bolt/lib/Core/BinarySection.cpp

 using namespace llvm;
 using namespace bolt;
 
 namespace opts {
 extern cl::opt<bool> PrintRelocations;
 extern cl::opt<bool> HotData;
 } // namespace opts
 
+uint64_t BinarySection::Count = 0;
+
 bool BinarySection::isELF() const { return BC.isELF(); }
 
 bool BinarySection::isMachO() const { return BC.isMachO(); }
 
 uint64_t
 BinarySection::hash(const BinaryData &BD,
                     std::map<const BinaryData *, uint64_t> &Cache) const {
   auto Itr = Cache.find(&BD);

bolt/test/runtime/X86/section-order.test

+REQUIRES: system-linux
+
+RUN: %clang %p/Inputs/basic-instrumentation.s -Wl,-q -o %t.exe
+RUN: llvm-bolt %t.exe -o %t --instrument
+RUN: llvm-readelf --section-headers %t | FileCheck %s
+
+## Verify that llvm-bolt outputs new sections in expected order.
+CHECK: .text.bolt.extra.1
+CHECK: .rodata.bolt.extra.1
+CHECK: .data.bolt.extra.1
+CHECK: .bss.bolt.extra.1
+