[lld-macho] Extend SyntheticSections to cover all segment load commands

[int3]

Summary

Previously, the special segments __PAGEZERO and __LINKEDIT were implemented as special LoadCommands. This diff implements them using special sections instead which have an isHidden() attribute. We do not emit section headers for hidden sections, but we use their addresses and file offsets to determine that of their containing segments. In addition to allowing us to share more segment-related code, this refactor is also important for the next step of emitting dylibs:

1. dylibs don't have segments like __PAGEZERO, so we need an easy way of omitting them w/o messing up segment indices
2. Unlike the kernel, which is happy to run an executable with out-of-order segments, dyld requires dylibs to have their segment load commands arranged in increasing address order. The refactor makes it easier to implement sorting of sections and segments.

Depends on D76252: [lld-macho] Add basic support for linking against dylibs.

[int3]

update

[int3]

update

lld/MachO/SyntheticSections.h

23–24

The names of hidden sections don't make it to the final executable; they're just for distinguishing the InputSections within lld code and so can be any unique string. But I've picked the same names as the corresponding Atoms in ld64 for easy reference.

[int3]

lld/MachO/OutputSegment.cpp

20–36

this is more or less what ld64 does

lld/MachO/Writer.h

17

Had to move this to the header so that MachHeaderSection's implementation in SyntheticSections.cpp could access it. That said, I'm a bit undecided on whether it really makes sense for things like MachHeaderSection to be there -- while it technically is a synthetic section, if it only gets used by one component of the linker (i.e. in Writer.cpp), maybe it should be defined there?

[int3]

add InputSection::getFileOffset()

[int3]

update

[int3]

lld/MachO/Writer.cpp

229–238

this was copypasted from the ELF implementation; we may want to factor it out into Common/ later

[int3]

rebase

[ruiu]

Overall I'd like to see more comments. All functions and classes that are not trivial should have a comment explaining what they represent or what they are supposed to do.

lld/MachO/InputSection.cpp

24 ↗

(On Diff #253753)

It is safer to use uint64_t to represent file offsets. At least on Linux, we actually create binaries that are larger than 4 GiB.

lld/MachO/OutputSegment.cpp

23

nit: we generally omit else after return, so

if (...)
  return ...;
if (...)
  return ...;
return ...;

lld/MachO/OutputSegment.h

38

nit: add a blank line after this line

lld/MachO/SyntheticSections.h

23–24

Actually this kind of one-shot temporary can be inlined, and in particular for these names, we don't have to have then as global constants because we are not really referring them.

32

Please add a class comment to explain what this class represents.

74

Can you expand the comment a bit? I'd explain what the bind opcode in more details.

[int3]

address comments

[int3]

update

[int3]

update

lld/MachO/InputSection.cpp

24 ↗

(On Diff #253753)

Sections are limited to 32-bit file offsets even in 64-bit MachO binaries. Even hidden sections addressed by e.g. LC_DYLD_LOAD_INFO must be 32-bit. Segments can have 64-bit file offsets though... so I've changed fileOff in OutputSegment but kept this 32-bit.

lld/MachO/SyntheticSections.h

23–24

they're referenced in sectionOrder(), so they're not exactly one-shot

74

hm, I think the explanation of bind opcodes would make more sense in encode()... I'll elaborate there

[int3]

update

[ruiu]

lld/MachO/InputSection.cpp

24 ↗

(On Diff #253753)

For PE/COFF, we are using uint64 as file offsets at least in some part of the code instead of uint32 even though PE/COFF file is limited to <4GiB, because it makes it easy to find errors when we are creating a file that is too large. If we are using 32-bit integers, we need to have an error check for integer wraparound at many places, but if we are using 64-bit integers, we can just proceed until we create an actual file and then we can do an error check at that point.

I don't know if that technique is useful to this particular function, but that's something you want to keep in mind.

[int3]

64 bit

lld/MachO/InputSection.cpp

24 ↗

(On Diff #253753)

Good point :)

[ruiu]

lld/MachO/OutputSegment.cpp

18

I believe the LLVM coding style recommends making functions private using static instead of surrounding a function definition with an anonymous namespace.

38

Since you have using namespace lld::macho, I guess you can omit macho::?

41

!empty()

61

Looks like you can directly assign to segRef.

lld/MachO/OutputSegment.h

35

nit: !sections.empty() is more conventional.

lld/MachO/SyntheticSections.cpp

150–152

This function makes a copy of a string which is then copied to the output buffer, which isn't very efficient. You can avoid the extra string copy by eliminating the output stream as well as SmallVector, and instead storing strings as std::vector<StringRef>.

lld/MachO/SyntheticSections.h

46–47

Thank you for the comment, that's very helpful.

64

!empty()

lld/MachO/Writer.cpp

117

!empty()

[ruiu]

lld/MachO/Writer.cpp

125

Use a concrete type instead of auto.

127–132

We usually use ArrayRef<T> instead of const std::vector<T>.

128

Expand auto.

229

Can you add a function comment?

230

You are always passing sectionOrder function as the second argument, so it looks like you can eliminate the second parameter and always using sectionOrder.

249

nit: omit else after return.

252–254

So it looks like the function returns only 4 possible values -- 0, 1, linkEditOffset, or linkEditOffset+1. Can't you use 0, 1, 2, 3 instead?

[int3]

lld/MachO/Writer.cpp

125

The types appear in the next two lines... is it really necessary to repeat them here?

I did a quick grep, it seems that lld/ELF tends to use explicit types for pairs, but lld/COFF seems to favor auto.

230

as mentioned in the comment below, this is likely sharable with a similar function in lld/ELF... I can factor it out now to make the 2nd parameter actually useful

252–254

The idea is to make it easily extensible -- there may be other special sections that we want to order before the __LINKEDIT sections.

[int3]

address comments

[int3]

update

[int3]

lld/MachO/Writer.cpp

230

On second thought, I don't think that really needs to be a standalone function at all. Simplified things...

[ruiu]

lld/MachO/Writer.cpp

252–254

Got it, but I don't think you have to prepare this tiny function for future extension. You can just make it return 0,1,2,3 and then in a later change when you actually need to use linkEditOffset, you can start returning linkEditOffset and linkEditOffset+1.

[smeenai]

Nice, I *really* like this design of representing all these special segments as synthetic sections.

@ruiu, how does this look to you now?

lld/MachO/InputSection.h

38

isHidden implies you *don't* emit the header, right? I'd clarify that in the comment.

40

Same here, since you *wouldn't* omit it if isNeeded.

lld/MachO/OutputSegment.cpp

20

Same comment here about logic based on section names, though I'm not sure if doing it differently would end up cleaner.

38

Hmm, what's up with the vec.empty() condition? Doesn't that mean numNonHiddenSections will only ever be 0 or 1, depending on if the first section addSection was called on for a particular segment was hidden or not?

lld/MachO/OutputSegment.h

35

Looks like this one still needs to be addressed?

35

ld64 commonly checks segment or section names and takes particular actions based on that name. I'm not a fan of that design, personally, since it ties a lot of logic to those names. Having named constants for the names is a big improvement already, but I'm wondering if there's any way to design this that would sidestep the issue altogether.

For example, we could have a property of an OutputSegment like alwaysNeeded, which would be set for the linkEdit segment at its point of creation. Alternatively, we could have a LinkEditSegment override of OutputSegment which overrides isNeeded. The point would be to try to represent properties of the segment as attributes or subclasses, instead of computing them based on the name.

I'm not sure how that'd end up looking in practice though, or if it's worth it in all cases. @int3, @ruiu, what do you think?

lld/MachO/SyntheticSections.cpp

150

index might be clearer than strx.

lld/MachO/SyntheticSections.h

33

Shouldn't all of these be inheriting from SyntheticSection?

108

How come you're calling this the StringPoolSection instead of the StringTableSection? I thought string table was the standard terminology.

lld/MachO/Writer.cpp

130

Nit: drop the braces.

252–254

Looks like this comment still needs a response.

lld/MachO/Writer.h

17

I think either design is justifiable ... we can just leave them where they are for now and see how things shake out when we have more of the linker implemented.

[int3]

address comments

[int3]

Sorry about the delay, got sidetracked for a bit...

lld/MachO/OutputSegment.cpp

38

This is to handle merged sections (well, aside from the fact that the rest of the code doesn't really do that yet). vec.empty() checks to see if we're creating a new output section or adding to an existing one.

lld/MachO/OutputSegment.h

35

Personally I try to avoid abstractions until they're definitively needed. At this point I'm not aware of any other segment that will benefit from alwaysNeeded

lld/MachO/SyntheticSections.cpp

150

it's named this way because its value ends up populating n_list::n_strx

lld/MachO/SyntheticSections.h

33

I haven't defined such a class yet, mostly because I'm not yet sure what it should contain that InputSection doesn't. I'm thinking we can sort out the class hierarchy after we have a proper OutputSection class set up.

108

ld64 calls it the string pool ¯\_(ツ)_/¯ I'm fine with either though

lld/MachO/Writer.cpp

252–254

You can just make it return 0,1,2,3 and then in a later change when you actually need to use linkEditOffset, you can start returning linkEditOffset and linkEditOffset+1.

I'd actually forgotten to add the symbol table / string pool sections to the ordering after rebasing, oops. So we do actually have a bunch of __LINKEDIT sections to order in this diff already.

In any case, I've refactored things so that the ordering can be specified a bit more declaratively, though it does add a bit more code... let me know what you think, I can revert to the if-else chain if you'd prefer.

[int3]

This comment was removed by int3.

[int3]

rebase

[int3]

lld/MachO/Writer.cpp

252–254

I'd actually forgotten to add the symbol table / string pool sections to the ordering after rebasing

Nevermind, I've instead swapped the stack position of this diff with that of D76742, so those sections are added later...

[int3]

order section name declarations by output order

[int3]

lld/MachO/Writer.cpp

252–254

I was debugging an issue locally that boiled down to sections not actually being arranged contiguously by the sort. There's currently nothing enforcing that property, aside from relying on us to correctly update the ordering list each time a new section is created. As such, I'm changing the sorting comparator to operate on segment names first followed by section names.

[int3]

update sorter

[int3]

rebase

[smeenai]

LGTM with the comments addressed. @ruiu, what do you think?

lld/MachO/OutputSegment.cpp

38

Got it. Flagging this for @Ktwu to adjust as part of the section merging, if she isn't already.

lld/MachO/SyntheticSections.cpp

78

Any reason to have this one-liner not be part of the header?

lld/MachO/SyntheticSections.h

91

I'd prefer StringTable over StringPool, since string table is the standard terminology used in the Mach-O reference.

lld/MachO/Writer.cpp

288

Hmm, I'm not sure if I found this or the if-ladder clearer. On the one hand, this is more declarative, but on the other, you have to parse the code below to understand what this is doing. It should be easy enough to change in a follow-up if we want though, so I don't care too much right now.

[int3]

lld/MachO/SyntheticSections.cpp

78

The declaration of InStruct appears at the end of the header file, so in isn't visible at isNeeded()'s declaration.

lld/MachO/SyntheticSections.h

91

D'oh, this entire section should be added in the symtab diff. Rebasing headaches 😅

Will move it over and rename

[int3]

address comments

[smeenai]

lld/MachO/SyntheticSections.cpp

78

Sure, but we could move that order around :) (You'd just need a struct GotSection; forward declaration.)

I don't think it really matters though ... I doubt the cost of not inlining this in the writer would be significant (and LTO would be able to inline it regardless, if you really cared about perf).

[smeenai]

LGTM

[vitalybuka]

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/40817/steps/check-lld%20ubsan/logs/stdio

ommand Output (stderr):
--
/b/sanitizer-x86_64-linux-fast/build/llvm-project/lld/MachO/InputSection.cpp:29:15: runtime error: null pointer passed as argument 2, which is declared to never be null
/usr/include/string.h:43:28: note: nonnull attribute specified here
    #0 0xc7f0ba in lld::macho::InputSection::writeTo(unsigned char*) /b/sanitizer-x86_64-linux-fast/build/llvm-project/lld/MachO/InputSection.cpp:29:3
    #1 0xc85687 in writeSections /b/sanitizer-x86_64-linux-fast/build/llvm-project/lld/MachO/Writer.cpp:449:15
    #2 0xc85687 in (anonymous namespace)::Writer::run() /b/sanitizer-x86_64-linux-fast/build/llvm-project/lld/MachO/Writer.cpp:490:3
    #3 0xc8418c in lld::macho::writeResult() /b/sanitizer-x86_64-linux-fast/build/llvm-project/lld/MachO/Writer.cpp:496:38
    #4 0xc79269 in lld::macho::link(llvm::ArrayRef<char const*>, bool, llvm::raw_ostream&, llvm::raw_ostream&) /b/sanitizer-x86_64-linux-fast/build/llvm-project/lld/MachO/Driver.cpp:170:3
    #5 0x835016 in main /b/sanitizer-x86_64-linux-fast/build/llvm-project/lld/tools/lld/lld.cpp:163:13
    #6 0x7f441c63809a in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2409a)
    #7 0x81e579 in _start (/b/sanitizer-x86_64-linux-fast/build/llvm_build_ubsan/bin/lld+0x81e579)

SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /b/sanitizer-x86_64-linux-fast/build/llvm-project/lld/MachO/InputSection.cpp:29:15 in

[smeenai]

Thanks for the report, taking a look.

[smeenai]

(I'll revert if we can't figure this out soon, but there's a bunch of dependents so I wanna try fixing forward first.)

[smeenai]

I have a repro, and we think we know the issue. Testing that out.

[smeenai]

Committed a fix for one issue in rGaf40bff32db7840cfbe07278ff0c498604acc5f0, and reverted the other two commits in rGb52bc2653bbc8da852a804afbb34836bb7f1e58a and rGfbae153ca583588de73d8fae84ec262c24d09025. We'll recommit those with a fix for the UB and keep an eye on the bot. Sorry for the breakage.

lld/MachO/Driver.cpp

bool macho::link(llvm::ArrayRef<const char *> argsArr, bool canExitEarly,
   config = make<Configuration>();
   symtab = make<SymbolTable>();
   target = createTargetInfo(args);
 
   config->entry = symtab->addUndefined(args.getLastArgValue(OPT_e, "_main"));
   config->outputFile = args.getLastArgValue(OPT_o, "a.out");
   config->searchPaths = getSearchPaths(args);
 
-  getOrCreateOutputSegment("__TEXT", VM_PROT_READ | VM_PROT_EXECUTE);
-  getOrCreateOutputSegment("__DATA", VM_PROT_READ | VM_PROT_WRITE);
-  getOrCreateOutputSegment("__DATA_CONST", VM_PROT_READ | VM_PROT_WRITE);
-
   for (opt::Arg *arg : args) {
     switch (arg->getOption().getID()) {
     case OPT_INPUT:
       addFile(arg->getValue());
       break;
     case OPT_l:
       if (Optional<std::string> path = findDylib(arg->getValue()))
         addFile(*path);
       break;
     }
   }
 
   if (!isa<Defined>(config->entry)) {
     error("undefined symbol: " + config->entry->getName());
     return false;
   }
 
   createSyntheticSections();
 
   // Initialize InputSections.
   for (InputFile *file : inputFiles)
     for (InputSection *sec : file->sections)
       inputSections.push_back(sec);
 
-  // Add input sections to output segments.
-  for (InputSection *isec : inputSections) {
-    OutputSegment *os =
-        getOrCreateOutputSegment(isec->segname, VM_PROT_READ | VM_PROT_WRITE);
-    isec->parent = os;
-    os->sections[isec->name].push_back(isec);
-  }
-
   // Write to an output file.
   writeResult();
 
   if (canExitEarly)
     exitLld(errorCount() ? 1 : 0);
 
   freeArena();
   return !errorCount();
 }

lld/MachO/InputSection.h

struct Reloc {
   uint32_t addend;
   uint32_t offset;
   llvm::PointerUnion<Symbol *, InputSection *> target;
 };
 
 class InputSection {
 public:
   virtual ~InputSection() = default;
-  virtual void writeTo(uint8_t *buf);
   virtual size_t getSize() const { return data.size(); }
+  virtual uint32_t getFileSize() const { return getSize(); }
+  // Whether to emit a section_64  header for this section.
+  virtual bool isHidden() const { return false; }
+  // Whether to omit this section entirely (header and body).
+  virtual bool isNeeded() const { return true; }
+  virtual void writeTo(uint8_t *buf);
 
   InputFile *file = nullptr;
   OutputSegment *parent = nullptr;
   StringRef name;
   StringRef segname;
 
   ArrayRef<uint8_t> data;
   uint64_t addr = 0;

lld/MachO/OutputSegment.h

 #define LLD_MACHO_OUTPUT_SEGMENT_H
 
 #include "lld/Common/LLVM.h"
 #include "llvm/ADT/MapVector.h"
 
 namespace lld {
 namespace macho {
 
+namespace segment_names {
+
+constexpr const char *text = "__TEXT";
+constexpr const char *pageZero = "__PAGEZERO";
+constexpr const char *linkEdit = "__LINKEDIT";
+
+} // namespace segment_names
+
 class InputSection;
 
 class OutputSegment {
 public:
   InputSection *firstSection() const { return sections.front().second.at(0); }
 
   InputSection *lastSection() const { return sections.back().second.back(); }
 
+  bool isNeeded() const {
+    return sections.size() != 0 || name == segment_names::linkEdit;
+  }
+
+  void addSection(InputSection *);
+  const llvm::MapVector<StringRef, std::vector<InputSection *>> &
+  getSections() const {
+    return sections;
+  }
+
+  uint32_t fileOff = 0;
   StringRef name;
-  uint32_t perms;
+  uint32_t numNonHiddenSections = 0;
+  uint32_t maxProt = 0;
+  uint32_t initProt = 0;
   uint8_t index;
+private:
   llvm::MapVector<StringRef, std::vector<InputSection *>> sections;
 };
 
 extern std::vector<OutputSegment *> outputSegments;
 
-OutputSegment *getOrCreateOutputSegment(StringRef name, uint32_t perms);
+OutputSegment *getOutputSegment(StringRef name);
+OutputSegment *getOrCreateOutputSegment(StringRef name);
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/OutputSegment.cpp

 //===- OutputSegment.cpp --------------------------------------------------===//
 //
 // 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 "OutputSegment.h"
+#include "InputSection.h"
 #include "lld/Common/Memory.h"
 
 using namespace llvm;
+using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
+namespace {
+
+uint32_t initProt(StringRef name) {
+  if (name == segment_names::text)
+    return VM_PROT_READ | VM_PROT_EXECUTE;
+  else if (name == segment_names::pageZero)
+    return 0;
+  else if (name == segment_names::linkEdit)
+    return VM_PROT_READ;
+  else
+    return VM_PROT_READ | VM_PROT_WRITE;
+}
+
+uint32_t maxProt(StringRef name) {
+  if (name == segment_names::pageZero)
+    return 0;
+  else
+    return VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE;
+}
+
+} // namespace
+
+void macho::OutputSegment::addSection(InputSection *isec) {
+  isec->parent = this;
+  std::vector<InputSection *> &vec = sections[isec->name];
+  if (vec.size() == 0 && !isec->isHidden()) {
+    ++numNonHiddenSections;
+  }
+  vec.push_back(isec);
+}
+
+static llvm::DenseMap<StringRef, OutputSegment *> nameToOutputSegment;
 std::vector<OutputSegment *> macho::outputSegments;
 
-OutputSegment *macho::getOrCreateOutputSegment(StringRef name, uint32_t perms) {
-  for (OutputSegment *os : outputSegments)
-    if (os->name == name)
-      // TODO: assert that os->perms == perms, once we figure out what to do
-      // about default-created segments.
-      return os;
+OutputSegment *macho::getOutputSegment(StringRef name) {
+  return nameToOutputSegment.lookup(name);
+}
+
+OutputSegment *macho::getOrCreateOutputSegment(StringRef name) {
+  OutputSegment *&segRef = nameToOutputSegment[name];
+  if (segRef != nullptr)
+    return segRef;
 
   auto *os = make<OutputSegment>();
   os->name = name;
-  os->perms = perms;
+  os->maxProt = maxProt(name);
+  os->initProt = initProt(name);
+
+  segRef = os;
   outputSegments.push_back(os);
   return os;
 }

lld/MachO/SyntheticSections.h

 //===- SyntheticSections.h -------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_SYNTHETIC_SECTIONS_H
 #define LLD_MACHO_SYNTHETIC_SECTIONS_H
 
 #include "InputSection.h"
 #include "Target.h"
 #include "llvm/ADT/SetVector.h"
 
+using namespace llvm::MachO;
+
 namespace lld {
 namespace macho {
 
+namespace section_names {
+
+constexpr const char *binding = "__binding";
+constexpr const char *header = "__mach_header";
+constexpr const char *pageZero = "__pagezero";
+
+} // namespace section_names
+
 class DylibSymbol;
+class LoadCommand;
+
+class MachHeaderSection : public InputSection {
+public:
+  MachHeaderSection();
+  void addLoadCommand(LoadCommand *);
+  bool isHidden() const override { return true; }
+  size_t getSize() const override;
+  void writeTo(uint8_t *buf) override;
+
+private:
+  std::vector<LoadCommand *> loadCommands;
+  uint32_t sizeOfCmds = 0;
+};
+
+class PageZeroSection : public InputSection {
+public:
+  PageZeroSection();
+  bool isHidden() const override { return true; }
+  size_t getSize() const override { return ImageBase; }
+  uint32_t getFileSize() const override { return 0; }
+};
 
 class GotSection : public InputSection {
 public:
   GotSection();
 
   void addEntry(DylibSymbol &sym);
-  const llvm::SetVector<const DylibSymbol *>& getEntries() const {
+  const llvm::SetVector<const DylibSymbol *> &getEntries() const {
     return entries;
   }
 
   size_t getSize() const override { return entries.size() * WordSize; }
 
+  bool isNeeded() const override { return entries.size() != 0; }
+
   void writeTo(uint8_t *buf) override {
     // Nothing to write, GOT starts as all zeroes
   }
+
 private:
   llvm::SetVector<const DylibSymbol *> entries;
 };
 
+class BindingSection : public InputSection {
+public:
+  BindingSection();
+  size_t getSize() const override { return contents.size(); }
+  // The sections in __LINKEDIT are special: their offsets are emitted in
+  // an LC_DYLD_INFO_ONLY command, instead of in section headers.
+  bool isHidden() const override { return true; }
+  bool isNeeded() const override;
+  void writeTo(uint8_t *buf) override;
+
+  SmallVector<char, 128> contents;
+};
+
 struct InStruct {
-  GotSection *got;
+  GotSection *got = nullptr;
 };
 
 extern InStruct in;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/SyntheticSections.cpp

 //===- SyntheticSections.cpp ---------------------------------------------===//
 //
 // 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 "SyntheticSections.h"
+#include "OutputSegment.h"
 #include "Symbols.h"
+#include "Writer.h"
 
 using namespace llvm::MachO;
 
 namespace lld {
 namespace macho {
 
+MachHeaderSection::MachHeaderSection() {
+  // dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
+  // from the beginning of the file (i.e. the header).
+  segname = segment_names::text;
+  name = section_names::header;
+}
+
+void MachHeaderSection::addLoadCommand(LoadCommand *lc) {
+  loadCommands.push_back(lc);
+  sizeOfCmds += lc->getSize();
+}
+
+size_t MachHeaderSection::getSize() const {
+  return sizeof(mach_header_64) + sizeOfCmds;
+}
+
+void MachHeaderSection::writeTo(uint8_t *buf) {
+  auto *hdr = reinterpret_cast<mach_header_64 *>(buf);
+  hdr->magic = MH_MAGIC_64;
+  hdr->cputype = CPU_TYPE_X86_64;
+  hdr->cpusubtype = CPU_SUBTYPE_X86_64_ALL | CPU_SUBTYPE_LIB64;
+  hdr->filetype = MH_EXECUTE;
+  hdr->ncmds = loadCommands.size();
+  hdr->sizeofcmds = sizeOfCmds;
+  hdr->flags = MH_NOUNDEFS | MH_DYLDLINK | MH_TWOLEVEL;
+
+  uint8_t *p = reinterpret_cast<uint8_t *>(hdr + 1);
+  for (LoadCommand *lc : loadCommands) {
+    lc->writeTo(p);
+    p += lc->getSize();
+  }
+}
+
+PageZeroSection::PageZeroSection() {
+  segname = segment_names::pageZero;
+  name = section_names::pageZero;
+}
+
 GotSection::GotSection() {
   segname = "__DATA_CONST";
   name = "__got";
   align = 8;
   flags = S_NON_LAZY_SYMBOL_POINTERS;
 
   // TODO: section_64::reserved1 should be an index into the indirect symbol
   // table, which we do not currently emit
 }
 
 void GotSection::addEntry(DylibSymbol &sym) {
   if (entries.insert(&sym)) {
     sym.gotIndex = entries.size() - 1;
   }
 }
 
+BindingSection::BindingSection() {
+  segname = segment_names::linkEdit;
+  name = section_names::binding;
+}
+
+bool BindingSection::isNeeded() const { return in.got->isNeeded(); }
+
+void BindingSection::writeTo(uint8_t *buf) {
+  memcpy(buf, contents.data(), contents.size());
+}
+
 InStruct in;
 
 } // namespace macho
 } // namespace lld

lld/MachO/Writer.h

 //===- Writer.h -------------------------------------------------*- C++ -*-===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLD_MACHO_WRITER_H
 #define LLD_MACHO_WRITER_H
 
+#include <cstdint>
+
 namespace lld {
 namespace macho {
 
+class LoadCommand {
+public:
+  virtual ~LoadCommand() = default;
+  virtual uint32_t getSize() const = 0;
+  virtual void writeTo(uint8_t *buf) const = 0;
+};
+
 void writeResult();
 
 void createSyntheticSections();
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/Writer.cpp

 using namespace lld;
 using namespace lld::macho;
 
 namespace {
 class LCLinkEdit;
 class LCDyldInfo;
 class LCSymtab;
 
-class LoadCommand {
-public:
-  virtual ~LoadCommand() = default;
-  virtual uint32_t getSize() const = 0;
-  virtual void writeTo(uint8_t *buf) const = 0;
-};
-
 class Writer {
 public:
   Writer() : buffer(errorHandler().outputBuffer) {}
 
+  void sortSections();
   void createLoadCommands();
   void scanRelocations();
-  void assignAddresses();
+  void createHiddenSections();
+  void assignAddresses(OutputSegment *);
 
   void createDyldInfoContents();
 
   void openFile();
-  void writeHeader();
   void writeSections();
 
   void run();
 
-  std::vector<LoadCommand *> loadCommands;
   std::unique_ptr<FileOutputBuffer> &buffer;
-  uint64_t fileSize = 0;
-  uint64_t sizeofCmds = 0;
-  LCLinkEdit *linkEditSeg = nullptr;
-  LCDyldInfo *dyldInfoSeg = nullptr;
-  LCSymtab *symtabSeg = nullptr;
-};
-
-class LCPagezero : public LoadCommand {
-public:
-  uint32_t getSize() const override { return sizeof(segment_command_64); }
-
-  void writeTo(uint8_t *buf) const override {
-    auto *c = reinterpret_cast<segment_command_64 *>(buf);
-    c->cmd = LC_SEGMENT_64;
-    c->cmdsize = getSize();
-    strcpy(c->segname, "__PAGEZERO");
-    c->vmsize = PageSize;
-  }
-};
-
-class LCLinkEdit : public LoadCommand {
-public:
-  uint32_t getSize() const override { return sizeof(segment_command_64); }
-
-  void writeTo(uint8_t *buf) const override {
-    auto *c = reinterpret_cast<segment_command_64 *>(buf);
-    c->cmd = LC_SEGMENT_64;
-    c->cmdsize = getSize();
-    strcpy(c->segname, "__LINKEDIT");
-    c->vmaddr = addr;
-    c->fileoff = fileOff;
-    c->filesize = c->vmsize = contents.size();
-    c->maxprot = VM_PROT_READ | VM_PROT_WRITE;
-    c->initprot = VM_PROT_READ;
-  }
-
-  uint64_t getOffset() const { return fileOff + contents.size(); }
-
-  uint64_t fileOff = 0;
   uint64_t addr = 0;
-  SmallVector<char, 128> contents;
+  uint32_t fileOff = 0;
+  MachHeaderSection *headerSection = nullptr;
+  BindingSection *bindingSection = nullptr;
 };
 
 class LCDyldInfo : public LoadCommand {
 public:
+  LCDyldInfo(BindingSection *bindingSection) : bindingSection(bindingSection) {}
+
   uint32_t getSize() const override { return sizeof(dyld_info_command); }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<dyld_info_command *>(buf);
     c->cmd = LC_DYLD_INFO_ONLY;
     c->cmdsize = getSize();
-    c->bind_off = bindOff;
-    c->bind_size = bindSize;
+    if (bindingSection->isNeeded()) {
+      OutputSegment *linkEditSeg = bindingSection->parent;
+      c->bind_off = linkEditSeg->fileOff + bindingSection->addr -
+                    linkEditSeg->firstSection()->addr;
+      c->bind_size = bindingSection->getFileSize();
+    }
     c->export_off = exportOff;
     c->export_size = exportSize;
   }
 
-  uint64_t bindOff = 0;
-  uint64_t bindSize = 0;
+  BindingSection *bindingSection;
   uint64_t exportOff = 0;
   uint64_t exportSize = 0;
 };
 
 class LCDysymtab : public LoadCommand {
 public:
   uint32_t getSize() const override { return sizeof(dysymtab_command); }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<dysymtab_command *>(buf);
     c->cmd = LC_DYSYMTAB;
     c->cmdsize = getSize();
   }
 };
 
 class LCSegment : public LoadCommand {
 public:
   LCSegment(StringRef name, OutputSegment *seg) : name(name), seg(seg) {}
 
   uint32_t getSize() const override {
     return sizeof(segment_command_64) +
-           seg->sections.size() * sizeof(section_64);
+           seg->numNonHiddenSections * sizeof(section_64);
   }
 
   void writeTo(uint8_t *buf) const override {
     auto *c = reinterpret_cast<segment_command_64 *>(buf);
     buf += sizeof(segment_command_64);
 
     c->cmd = LC_SEGMENT_64;
     c->cmdsize = getSize();
     memcpy(c->segname, name.data(), name.size());
+    c->fileoff = seg->fileOff;
+    c->maxprot = seg->maxProt;
+    c->initprot = seg->initProt;
 
-    // dyld3's MachOLoaded::getSlide() assumes that the __TEXT segment starts
-    // from the beginning of the file (i.e. the header).
-    // TODO: replace this logic by creating a synthetic __TEXT,__mach_header
-    // section instead.
-    c->fileoff = name == "__TEXT" ? 0 : seg->firstSection()->addr - ImageBase;
-    c->vmaddr = c->fileoff + ImageBase;
-    c->vmsize = c->filesize =
+    if (seg->getSections().size() == 0)
+      return;
+
+    c->vmaddr = seg->firstSection()->addr;
+    c->vmsize =
         seg->lastSection()->addr + seg->lastSection()->getSize() - c->vmaddr;
-    c->maxprot = VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE;
-    c->initprot = seg->perms;
-    c->nsects = seg->sections.size();
+    c->nsects = seg->numNonHiddenSections;
 
-    for (auto &p : seg->sections) {
+    for (auto &p : seg->getSections()) {
       StringRef s = p.first;
-      std::vector<InputSection *> &sections = p.second;
+      const std::vector<InputSection *> &sections = p.second;
+      for (auto *isec : sections)
+        c->filesize += isec->getFileSize();
+      if (sections[0]->isHidden()) {
+        continue;
+      }
 
       auto *sectHdr = reinterpret_cast<section_64 *>(buf);
       buf += sizeof(section_64);
 
       memcpy(sectHdr->sectname, s.data(), s.size());
       memcpy(sectHdr->segname, name.data(), name.size());
 
       sectHdr->addr = sections[0]->addr;
void writeTo(uint8_t *buf) const override {
     buf[path.size()] = '\0';
   }
 
 private:
   // Recent versions of Darwin won't run any binary that has dyld at a
   // different location.
   const StringRef path = "/usr/lib/dyld";
 };
+
+static void sortByOrder(MutableArrayRef<InputSection *> in,
+                        llvm::function_ref<uint32_t(InputSection *s)> order) {
+  std::vector<std::pair<uint32_t, InputSection *>> v;
+  for (InputSection *s : in)
+    v.push_back({order(s), s});
+  llvm::stable_sort(v, less_first());
+
+  for (size_t i = 0; i < v.size(); ++i)
+    in[i] = v[i].second;
+}
+
+uint32_t sectionOrder(const InputSection *isec) {
+  // Make sure __LINKEDIT is the last segment (i.e. all its hidden sections
+  // must be ordered after other sections).
+  constexpr uint32_t linkEditOffset = 0xffff;
+
+  if (isec->name == section_names::pageZero)
+    return 0;
+  else if (isec->name == section_names::header)
+    return 1;
+  else if (isec->name == section_names::binding)
+    return linkEditOffset + 1;
+  else
+    return linkEditOffset;
+}
+
 } // namespace
 
+void Writer::sortSections() {
+  sortByOrder(inputSections, sectionOrder);
+  // Add input sections to output segments.
+  for (InputSection *isec : inputSections)
+    if (isec->isNeeded())
+      getOrCreateOutputSegment(isec->segname)->addSection(isec);
+}
+
 void Writer::createLoadCommands() {
-  linkEditSeg = make<LCLinkEdit>();
-  dyldInfoSeg = make<LCDyldInfo>();
-  symtabSeg = make<LCSymtab>();
-
-  loadCommands.push_back(linkEditSeg);
-  loadCommands.push_back(dyldInfoSeg);
-  loadCommands.push_back(symtabSeg);
-  loadCommands.push_back(make<LCPagezero>());
-  loadCommands.push_back(make<LCLoadDylinker>());
-  loadCommands.push_back(make<LCDysymtab>());
-  loadCommands.push_back(make<LCMain>());
+  headerSection->addLoadCommand(make<LCDyldInfo>(bindingSection));
+  headerSection->addLoadCommand(make<LCLoadDylinker>());
+  headerSection->addLoadCommand(make<LCSymtab>());
+  headerSection->addLoadCommand(make<LCDysymtab>());
+  headerSection->addLoadCommand(make<LCMain>());
 
-  uint8_t segIndex = 2; // LCPagezero and LCLinkEdit are segment load commands
+  uint8_t segIndex = 0;
   for (OutputSegment *seg : outputSegments) {
-    if (!seg->sections.empty()) {
-      loadCommands.push_back(make<LCSegment>(seg->name, seg));
+    if (seg->isNeeded()) {
+      headerSection->addLoadCommand(make<LCSegment>(seg->name, seg));
       seg->index = segIndex++;
     }
   }
 
   uint64_t dylibOrdinal = 1;
   for (InputFile *file : inputFiles) {
     if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
-      loadCommands.push_back(make<LCLoadDylib>(dylibFile->dylibName));
+      headerSection->addLoadCommand(make<LCLoadDylib>(dylibFile->dylibName));
       dylibFile->ordinal = dylibOrdinal++;
     }
   }
   // TODO: dyld requires libSystem to be loaded. libSystem is a universal
   // binary and we don't have support for that yet, so mock it out here.
-  loadCommands.push_back(make<LCLoadDylib>("/usr/lib/libSystem.B.dylib"));
+  headerSection->addLoadCommand(
+      make<LCLoadDylib>("/usr/lib/libSystem.B.dylib"));
 }
 
 void Writer::scanRelocations() {
   for (auto &sect : inputSections)
     for (Reloc &r : sect->relocs)
       if (auto *s = r.target.dyn_cast<Symbol *>())
         if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s))
           in.got->addEntry(*dylibSymbol);
 }
 
-void Writer::assignAddresses() {
-  uint64_t addr = ImageBase + sizeof(mach_header_64);
+void Writer::createHiddenSections() {
+  headerSection = make<MachHeaderSection>();
+  bindingSection = make<BindingSection>();
 
-  uint64_t size = 0;
-  for (LoadCommand *lc : loadCommands)
-    size += lc->getSize();
-  sizeofCmds = size;
-  addr += size;
+  inputSections.push_back(make<PageZeroSection>());
+  inputSections.push_back(headerSection);
+  inputSections.push_back(bindingSection);
+}
 
-  for (OutputSegment *seg : outputSegments) {
-    addr = alignTo(addr, PageSize);
+void Writer::assignAddresses(OutputSegment *seg) {
+  fileOff = alignTo(fileOff, PageSize);
+  seg->fileOff = fileOff;
 
-    for (auto &p : seg->sections) {
-      ArrayRef<InputSection *> sections = p.second;
-      for (InputSection *isec : sections) {
-        addr = alignTo(addr, isec->align);
-        isec->addr = addr;
-        addr += isec->getSize();
-      }
-    }
-  }
+  for (auto &p : seg->getSections()) {
+      fileOff += isec->getFileSize();
 
-  addr = alignTo(addr, PageSize);
-  linkEditSeg->addr = addr;
-  linkEditSeg->fileOff = addr - ImageBase;
-}
-
 // LC_DYLD_INFO_ONLY contains symbol import/export information. Imported
 // symbols are described by a sequence of bind opcodes, which allow for a
 // compact encoding. Exported symbols are described using a trie.
 void Writer::createDyldInfoContents() {
-  uint64_t sectionStart = linkEditSeg->getOffset();
-  raw_svector_ostream os{linkEditSeg->contents};
-
-  if (in.got->getSize() != 0) {
+  raw_svector_ostream os{bindingSection->contents};
+  if (in.got->isNeeded()) {
     // Emit bind opcodes, which tell dyld which dylib symbols to load.
 
     // Tell dyld to write to the section containing the GOT.
     os << (char)(BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB |
                  in.got->parent->index);
     encodeULEB128(in.got->addr - in.got->parent->firstSection()->addr, os);
     for (const DylibSymbol *sym : in.got->getEntries()) {
       // TODO: Implement compact encoding -- we only need to encode the
       // differences between consecutive symbol entries.
       if (sym->file->ordinal <= BIND_IMMEDIATE_MASK) {
         os << (char)(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM | sym->file->ordinal);
       } else {
         error("TODO: Support larger dylib symbol ordinals");
         continue;
       }
       os << (char)BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM;
       os << sym->getName() << '\0';
       os << (char)(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER);
       os << (char)BIND_OPCODE_DO_BIND;
     }
 
     os << (char)BIND_OPCODE_DONE;
-
-    dyldInfoSeg->bindOff = sectionStart;
-    dyldInfoSeg->bindSize = linkEditSeg->getOffset() - sectionStart;
   }
 
   // TODO: emit bind opcodes for lazy symbols.
   // TODO: Implement symbol export trie.
 }
 
 void Writer::openFile() {
   Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr =
-      FileOutputBuffer::create(config->outputFile, fileSize,
+      FileOutputBuffer::create(config->outputFile, fileOff,
                                FileOutputBuffer::F_executable);
 
   if (!bufferOrErr)
     error("failed to open " + config->outputFile + ": " +
           llvm::toString(bufferOrErr.takeError()));
   else
     buffer = std::move(*bufferOrErr);
 }
 
-void Writer::writeHeader() {
-  auto *hdr = reinterpret_cast<mach_header_64 *>(buffer->getBufferStart());
-  hdr->magic = MH_MAGIC_64;
-  hdr->cputype = CPU_TYPE_X86_64;
-  hdr->cpusubtype = CPU_SUBTYPE_X86_64_ALL | CPU_SUBTYPE_LIB64;
-  hdr->filetype = MH_EXECUTE;
-  hdr->ncmds = loadCommands.size();
-  hdr->sizeofcmds = sizeofCmds;
-  hdr->flags = MH_NOUNDEFS | MH_DYLDLINK | MH_TWOLEVEL;
-
-  uint8_t *p = reinterpret_cast<uint8_t *>(hdr + 1);
-  for (LoadCommand *lc : loadCommands) {
-    lc->writeTo(p);
-    p += lc->getSize();
-  }
-}
-
 void Writer::writeSections() {
   uint8_t *buf = buffer->getBufferStart();
-
-  for (OutputSegment *seg : outputSegments)
-    for (auto &sect : seg->sections)
-      for (InputSection *isec : sect.second)
-        isec->writeTo(buf + isec->addr - ImageBase);
-
-  memcpy(buf + linkEditSeg->fileOff, linkEditSeg->contents.data(),
-         linkEditSeg->contents.size());
+  for (OutputSegment *seg : outputSegments) {
+    uint32_t fileOff = seg->fileOff;
+    for (auto &sect : seg->getSections()) {
+      for (InputSection *isec : sect.second) {
+        isec->writeTo(buf + fileOff);
+        fileOff += isec->getFileSize();
+      }
+    }
+  }
 }
 
 void Writer::run() {
-  createLoadCommands();
   scanRelocations();
-  assignAddresses();
+  createHiddenSections();
+  sortSections();
+  // dyld requires __LINKEDIT segment to always exist (even if empty).
+  getOrCreateOutputSegment(segment_names::linkEdit);
+  createLoadCommands();
 
-  // Fill __LINKEDIT contents
+  // At this point, __LINKEDIT sections are empty, but we need to determine
+  // addresses of other segments/sections before generating its contents.
+  for (OutputSegment *seg : outputSegments)
+    assignAddresses(seg);
+
+  // Fill __LINKEDIT contents.
   createDyldInfoContents();
-  fileSize = linkEditSeg->fileOff + linkEditSeg->contents.size();
+
+  // Now that __LINKEDIT is filled out, do a proper calculation of its
+  // addresses and offsets.
+  assignAddresses(getOutputSegment(segment_names::linkEdit));
 
   openFile();
   if (errorCount())
     return;
 
-  writeHeader();
   writeSections();
 
   if (auto e = buffer->commit())
     error("failed to write to the output file: " + toString(std::move(e)));
 }
 
 void macho::writeResult() { Writer().run(); }
 
 void macho::createSyntheticSections() {
   in.got = make<GotSection>();
   inputSections.push_back(in.got);
 }

lld/test/MachO/segments.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
 # RUN: lld -flavor darwinnew -o %t %t.o
 # RUN: llvm-readobj --macho-segment %t | FileCheck %s
 
-# These segments must always be present.
-# CHECK-DAG: Name: __PAGEZERO
-# CHECK-DAG: Name: __LINKEDIT
-# CHECK-DAG: Name: __TEXT
+## These two segments must always be present at the start of an executable.
+# CHECK-NOT:  Segment {
+# CHECK:      Segment {
+# CHECK:        Cmd: LC_SEGMENT_64
+# CHECK:        Name: __PAGEZERO
+# CHECK:        Size: 72
+# CHECK:        vmaddr:
+# CHECK:        vmsize:
+# CHECK:        fileoff: 0
+# CHECK:        filesize: 0
+## The kernel won't execute a binary with the wrong protections for __PAGEZERO.
+# CHECK:        maxprot: ---
+# CHECK:        initprot: ---
+# CHECK:        nsects: 0
+# CHECK:        flags: 0x0
+# CHECK:      }
+# CHECK:      Segment {
+# CHECK:        Cmd: LC_SEGMENT_64
+# CHECK:        Name: __TEXT
+# CHECK:        Size: 152
+# CHECK:        vmaddr:
+# CHECK:        vmsize:
+## dyld3 assumes that the __TEXT segment starts from the file header
+# CHECK:        fileoff: 0
+# CHECK:        filesize:
+# CHECK:        maxprot: rwx
+# CHECK:        initprot: r-x
+# CHECK:        nsects: 1
+# CHECK:        flags: 0x0
+# CHECK:      }
 
-# Check that we handle max-length names correctly.
-# CHECK-DAG: Name: maxlen_16ch_name
+## Check that we handle max-length names correctly.
+# CHECK:      Cmd: LC_SEGMENT_64
+# CHECK-NEXT: Name: maxlen_16ch_name
+
+## This segment must always be present at the end of an executable.
+# CHECK:      Name: __LINKEDIT
+# CHECK:      maxprot: rwx
+# CHECK:      initprot: r--
+# CHECK-NOT:  Cmd: LC_SEGMENT_64
 
 .text
 .global _main
 _main:
   mov $0, %rax
   ret
 
 .section maxlen_16ch_name,foo

lld/test/MachO/text-segment.s

-# REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-apple-darwin %s -o %t.o
-# RUN: lld -flavor darwinnew -o %t %t.o
-# RUN: llvm-readobj --macho-segment %t | FileCheck %s
-
-# CHECK: Name: __TEXT
-# CHECK-NOT: }
-# dyld3 assumes that the __TEXT segment starts from the file header
-# CHECK:       fileoff: 0
-
-.text
-.global _main
-_main:
-  mov $0, %rax
-  ret