[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

22–38

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

223–232

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

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

25

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.

80

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

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

80

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

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

Good point :)

[ruiu]

lld/MachO/OutputSegment.cpp

20

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

40

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

43

!empty()

47–48

Looks like you can directly assign to segRef.

lld/MachO/OutputSegment.h

35

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

lld/MachO/SyntheticSections.cpp

157–159

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.

69

!empty()

lld/MachO/Writer.cpp

112

!empty()

[ruiu]

lld/MachO/Writer.cpp

120

Use a concrete type instead of auto.

122–126

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

123

Expand auto.

223

Can you add a function comment?

224

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

243

nit: omit else after return.

246–248

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

120

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.

224

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

246–248

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

224

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

[ruiu]

lld/MachO/Writer.cpp

246–248

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

22

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

40

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

157

index might be clearer than strx.

lld/MachO/SyntheticSections.h

33

Shouldn't all of these be inheriting from SyntheticSection?

114

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

lld/MachO/Writer.cpp

125

Nit: drop the braces.

246–248

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

40

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

157

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.

114

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

lld/MachO/Writer.cpp

246–248

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

246–248

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

246–248

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

40

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

lld/MachO/SyntheticSections.cpp

85

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

lld/MachO/SyntheticSections.h

97

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

lld/MachO/Writer.cpp

235

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

85

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

97

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

85

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

if (args.hasArg(OPT_v)) {
     message(getLLDVersion());
     std::vector<StringRef> &searchPaths = config->searchPaths;
     message("Library search paths:\n" +
             llvm::join(searchPaths.begin(), searchPaths.end(), "\n"));
     freeArena();
     return !errorCount();
   }
 
-  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 uint64_t getFileSize() const { return getSize(); }
+  uint64_t getFileOffset() const;
+  // Don't emit section_64 headers for hidden sections.
+  virtual bool isHidden() const { return false; }
+  // Unneeded sections are omitted 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;
+
+  // TODO these properties ought to live in an OutputSection class.
+  // Move them once available.
   uint64_t addr = 0;
   uint32_t align = 1;
+  uint32_t sectionIndex = 0;
   uint32_t flags = 0;
 
   std::vector<Reloc> relocs;
 };
 
 extern std::vector<InputSection *> inputSections;
 
 } // namespace macho
 } // namespace lld
 
 #endif

lld/MachO/InputSection.cpp

 //===- InputSection.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 "InputSection.h"
+#include "OutputSegment.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "lld/Common/Memory.h"
 #include "llvm/Support/Endian.h"
 
 using namespace llvm::MachO;
 using namespace llvm::support;
 using namespace lld;
 using namespace lld::macho;
 
 std::vector<InputSection *> macho::inputSections;
 
+uint64_t InputSection::getFileOffset() const {
+  return parent->fileOff + addr - parent->firstSection()->addr;
+}
+
 void InputSection::writeTo(uint8_t *buf) {
   memcpy(buf, data.data(), data.size());
 
   for (Reloc &r : relocs) {
     uint64_t va = 0;
     if (auto *s = r.target.dyn_cast<Symbol *>()) {
       if (auto *dylibSymbol = dyn_cast<DylibSymbol>(s)) {
         va = in.got->addr - ImageBase + dylibSymbol->gotIndex * WordSize;

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.empty() || name == segment_names::linkEdit;
+  }
+
+  void addSection(InputSection *);
+
+  const llvm::MapVector<StringRef, std::vector<InputSection *>> &
+  getSections() const {
+    return sections;
+  }
+
+  uint64_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"
+#include "llvm/BinaryFormat/MachO.h"
 
 using namespace llvm;
+using namespace llvm::MachO;
 using namespace lld;
 using namespace lld::macho;
 
+static uint32_t initProt(StringRef name) {
+  if (name == segment_names::text)
+    return VM_PROT_READ | VM_PROT_EXECUTE;
+  if (name == segment_names::pageZero)
+    return 0;
+  if (name == segment_names::linkEdit)
+    return VM_PROT_READ;
+  return VM_PROT_READ | VM_PROT_WRITE;
+}
+
+static uint32_t maxProt(StringRef name) {
+  if (name == segment_names::pageZero)
+    return 0;
+  return VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE;
+}
+
+void OutputSegment::addSection(InputSection *isec) {
+  isec->parent = this;
+  std::vector<InputSection *> &vec = sections[isec->name];
+  if (vec.empty() && !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;
-
-  auto *os = make<OutputSegment>();
-  os->name = name;
-  os->perms = perms;
-  outputSegments.push_back(os);
-  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;
+
+  segRef = make<OutputSegment>();
+  segRef->name = name;
+  segRef->maxProt = maxProt(name);
+  segRef->initProt = initProt(name);
+
+  outputSegments.push_back(segRef);
+  return segRef;
 }

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 *pageZero = "__pagezero";
+constexpr const char *header = "__mach_header";
+constexpr const char *binding = "__binding";
+
+} // namespace section_names
+
 class DylibSymbol;
+class LoadCommand;
+
+// The header of the Mach-O file, which must have a file offset of zero.
+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;
+};
+
+// A hidden section that exists solely for the purpose of creating the
+// __PAGEZERO segment, which is used to catch null pointer dereferences.
+class PageZeroSection : public InputSection {
+public:
+  PageZeroSection();
+  bool isHidden() const override { return true; }
+  size_t getSize() const override { return ImageBase; }
+  uint64_t getFileSize() const override { return 0; }
+};
 
 // This section will be populated by dyld with addresses to non-lazily-loaded
 // dylib symbols.
 class GotSection : public InputSection {
 public:
   GotSection();
 
   void addEntry(DylibSymbol &sym);
   const llvm::SetVector<const DylibSymbol *> &getEntries() const {
     return entries;
   }
 
   size_t getSize() const override { return entries.size() * WordSize; }
 
+  bool isNeeded() const override { return !entries.empty(); }
+
   void writeTo(uint8_t *buf) override {
     // Nothing to write, GOT contains all zeros at link time; it's populated at
     // runtime by dyld.
   }
 
 private:
   llvm::SetVector<const DylibSymbol *> entries;
 };
 
+// Stores bind opcodes for telling dyld which symbols to load non-lazily.
+class BindingSection : public InputSection {
+public:
+  BindingSection();
+  void finalizeContents();
+  size_t getSize() const override { return contents.size(); }
+  // Like other sections in __LINKEDIT, the binding section is special: its
+  // offsets are recorded in the LC_DYLD_INFO_ONLY load 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 "InputFiles.h"
+#include "OutputSegment.h"
 #include "Symbols.h"
+#include "Writer.h"
 
+#include "lld/Common/ErrorHandler.h"
+#include "llvm/Support/EndianStream.h"
+#include "llvm/Support/LEB128.h"
+
+using namespace llvm;
 using namespace llvm::MachO;
+using namespace llvm::support;
 
 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(); }
+
+// Emit bind opcodes, which are a stream of byte-sized opcodes that dyld
+// interprets to update a record with the following fields:
+//  * segment index (of the segment to write the symbol addresses to, typically
+//    the __DATA_CONST segment which contains the GOT)
+//  * offset within the segment, indicating the next location to write a binding
+//  * symbol type
+//  * symbol library ordinal (the index of its library's LC_LOAD_DYLIB command)
+//  * symbol name
+//  * addend
+// When dyld sees BIND_OPCODE_DO_BIND, it uses the current record state to bind
+// a symbol in the GOT, and increments the segment offset to point to the next
+// entry. It does *not* clear the record state after doing the bind, so
+// subsequent opcodes only need to encode the differences between bindings.
+void BindingSection::finalizeContents() {
+  if (!isNeeded())
+    return;
+
+  raw_svector_ostream os{contents};
+  os << static_cast<uint8_t>(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 << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
+                                 sym->file->ordinal);
+    } else {
+      error("TODO: Support larger dylib symbol ordinals");
+      continue;
+    }
+    os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
+       << sym->getName() << '\0'
+       << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER)
+       << static_cast<uint8_t>(BIND_OPCODE_DO_BIND);
+  }
+
+  os << static_cast<uint8_t>(BIND_OPCODE_DONE);
+}
+
+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

 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/BinaryFormat/MachO.h"
-#include "llvm/Support/EndianStream.h"
-#include "llvm/Support/LEB128.h"
 #include "llvm/Support/MathExtras.h"
 
 using namespace llvm;
 using namespace llvm::MachO;
-using namespace llvm::support;
 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 createLoadCommands();
   void scanRelocations();
-  void assignAddresses();
-
-  void createDyldInfoContents();
+  void createHiddenSections();
+  void sortSections();
+  void createLoadCommands();
+  void assignAddresses(OutputSegment *);
+  void createSymtabContents();
 
   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;
+  uint64_t fileOff = 0;
+  MachHeaderSection *headerSection = nullptr;
+  BindingSection *bindingSection = nullptr;
 };
 
+// LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
 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()) {
+      c->bind_off = bindingSection->getFileOffset();
+      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().empty())
+      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;
+      ArrayRef<InputSection *> sections = p.second;
+      for (InputSection *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;
-      sectHdr->offset = sections[0]->addr - ImageBase;
+      sectHdr->offset = sections[0]->getFileOffset();
       sectHdr->align = sections[0]->align;
       uint32_t maxAlign = 0;
       for (const InputSection *section : sections)
         maxAlign = std::max(maxAlign, section->align);
       sectHdr->align = Log2_32(maxAlign);
       sectHdr->flags = sections[0]->flags;
       sectHdr->size = sections.back()->addr + sections.back()->getSize() -
                       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";
 };
+
+class SectionComparator {
+public:
+  struct OrderInfo {
+    uint32_t segmentOrder;
+    DenseMap<StringRef, uint32_t> sectionOrdering;
+  };
+
+  SectionComparator() {
+    // This defines the order of segments and the sections within each segment.
+    // Segments that are not mentioned here will end up at defaultPosition;
+    // sections that are not mentioned will end up at the end of the section
+    // list for their given segment.
+    std::vector<std::pair<StringRef, std::vector<StringRef>>> ordering{
+        {segment_names::pageZero, {}},
+        {segment_names::text, {section_names::header}},
+        {defaultPosition, {}},
+        // Make sure __LINKEDIT is the last segment (i.e. all its hidden
+        // sections must be ordered after other sections).
+        {segment_names::linkEdit, {section_names::binding}},
+    };
+
+    for (uint32_t i = 0, n = ordering.size(); i < n; ++i) {
+      auto &p = ordering[i];
+      StringRef segname = p.first;
+      const std::vector<StringRef> &sectOrdering = p.second;
+      OrderInfo &info = orderMap[segname];
+      info.segmentOrder = i;
+      for (uint32_t j = 0, m = sectOrdering.size(); j < m; ++j)
+        info.sectionOrdering[sectOrdering[j]] = j;
+    }
+  }
+
+  // Return a {segmentOrder, sectionOrder} pair. Using this as a key will
+  // ensure that all sections in the same segment are sorted contiguously.
+  std::pair<uint32_t, uint32_t> order(const InputSection *isec) {
+    auto it = orderMap.find(isec->segname);
+    if (it == orderMap.end())
+      return {orderMap[defaultPosition].segmentOrder, 0};
+    OrderInfo &info = it->second;
+    auto sectIt = info.sectionOrdering.find(isec->name);
+    if (sectIt != info.sectionOrdering.end())
+      return {info.segmentOrder, sectIt->second};
+    return {info.segmentOrder, info.sectionOrdering.size()};
+  }
+
+  bool operator()(const InputSection *a, const InputSection *b) {
+    return order(a) < order(b);
+  }
+
+private:
+  const StringRef defaultPosition = StringRef();
+  DenseMap<StringRef, OrderInfo> orderMap;
+};
+
 } // namespace
 
+template <typename SectionType, typename... ArgT>
+SectionType *createInputSection(ArgT &&... args) {
+  auto *section = make<SectionType>(std::forward<ArgT>(args)...);
+  inputSections.push_back(section);
+  return section;
+}
+
+void Writer::scanRelocations() {
+  for (InputSection *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::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 = 1; // LCPagezero is a segment load command
+  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 (InputSection *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::createHiddenSections() {
+  headerSection = createInputSection<MachHeaderSection>();
+  bindingSection = createInputSection<BindingSection>();
+  createInputSection<PageZeroSection>();
 }
 
-void Writer::assignAddresses() {
-  uint64_t addr = ImageBase + sizeof(mach_header_64);
+void Writer::sortSections() {
+  llvm::stable_sort(inputSections, SectionComparator());
 
-  uint64_t size = 0;
-  for (LoadCommand *lc : loadCommands)
-    size += lc->getSize();
-  sizeofCmds = size;
-  addr += size;
+  // TODO This is wrong; input sections ought to be grouped into
+  // output sections, which are then organized like this.
+  uint32_t sectionIndex = 0;
+  // Add input sections to output segments.
+  for (InputSection *isec : inputSections) {
+    if (isec->isNeeded()) {
+      if (!isec->isHidden())
+        isec->sectionIndex = ++sectionIndex;
+      getOrCreateOutputSegment(isec->segname)->addSection(isec);
+    }
+  }
+}
 
-  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) {
-    // Emit bind opcodes, which tell dyld which dylib symbols to load.
-
-    // Tell dyld to write to the section containing the GOT.
-    os << static_cast<uint8_t>(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 << static_cast<uint8_t>(BIND_OPCODE_SET_DYLIB_ORDINAL_IMM |
-                                   sym->file->ordinal);
-      } else {
-        error("TODO: Support larger dylib symbol ordinals");
-        continue;
-      }
-      os << static_cast<uint8_t>(BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM)
-         << sym->getName() << '\0'
-         << static_cast<uint8_t>(BIND_OPCODE_SET_TYPE_IMM | BIND_TYPE_POINTER)
-         << static_cast<uint8_t>(BIND_OPCODE_DO_BIND);
-    }
-
-    os << static_cast<uint8_t>(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) {
+    uint64_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();
+  // Sort and assign sections to their respective segments. No more sections can
+  // be created after this method runs.
+  sortSections();
+  // dyld requires __LINKEDIT segment to always exist (even if empty).
+  getOrCreateOutputSegment(segment_names::linkEdit);
+  // No more segments can be created after this method runs.
+  createLoadCommands();
+
+  // Ensure that segments (and the sections they contain) are allocated
+  // addresses in ascending order, which dyld requires.
+  //
+  // Note that 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.
+  bindingSection->finalizeContents();
 
-  // 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. We don't have to recalculate the other segments
+  // since sortSections() ensures that __LINKEDIT is the last segment.
+  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);
+  in.got = createInputSection<GotSection>();
 }

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