Start support for linking object files with split stacks

[saugustine]

Summary

Implement linking object files compiled with -fsplit-stack, including tests.

This revision supports x86_64 (in both 32-bit and 64-bit variants). Support for other targets is simply a matter
of adding prologue adjustments.

[ruiu]

If you have other patches in the series, could you also send it for review? It would be easier for me to review individual patch once I get a whole idea about how you are going to support -fsplit-stack.

ELF/InputFiles.cpp

658

remove //

675–676

else { if -> else if

ELF/InputFiles.h

213–214

I'd think you don't need to add this comment because that's true to some other members too.

218

nit: add a blank line just like the above.

[grimar]

In D46653#1094768, @ruiu wrote:

If you have other patches in the series, could you also send it for review? It would be easier for me to review individual patch once I get a whole idea about how you are going to support -fsplit-stack.

+1. Please let us see the whole implementation plan.

ELF/InputFiles.cpp

663

I'm not an expert in licenses. I do not know if we can quote the text like that. It probably belongs to a different code license. I think we usually write own comments and just add a link if we need. Can you do the same here?

675–676

No need to do 'else' at all, the first branch ends with the return.

[saugustine]

Implement split stack support and tests.

[saugustine]

ELF/InputFiles.cpp

663

I've just kept the cross reference and deleted everything else.

[pcc]

ELF/InputFiles.cpp

657

I don't think Rust actually uses segmented stacks any more.
https://mail.mozilla.org/pipermail/rust-dev/2013-November/006314.html

[ruiu]

ELF/Arch/X86_64.cpp

482

We generally don't use the table-driven coding pattern that much in lld, especially when compared to other LLVM subprojects. I prefer less abstracted code. I'd write this as a (boring but simple) sequence of "if" and "else if" that calls memcmp() and memcpy() to replace a matched pattern.

ELF/InputFiles.cpp

663

I believe quoting that amount of text should be fine, but if you are cautious, please write a comment with your own words instead of deleting the comment entirely. That was a helpful comment.

ELF/InputSection.cpp

825

What does this function do? Please write a function comment.

This function seems a bit too long. Please consider splitting.

852

This function seems too slow to call for each relocation. The number of relocation can be an order of tens of millions, so per-relocation processing needs to be really fast.

[mgrang]

ELF/InputSection.cpp

873

Please use llvm::sort instead of std::sort. See https://llvm.org/docs/CodingStandards.html#beware-of-non-deterministic-sorting-order-of-equal-elements.

879

Same here.

[saugustine]

I've addressed all the comments. Have another look if you would.

[ruiu]

Could you read other functions in the same file and other files in the same directory and make your code look the same as others in coding style? Consistency is really important, and it is hard for me to read some code in this patch because of lack of consistency.

ELF/Arch/X86_64.cpp

478

This is inconsistent in style with other functions in the same file. Please remove the blank line.

483–486

Please write more directly and concise as we do in other places in the same file.

if (Loc + 8 < End && memcmp(Loc, "\x64\x3b\x24\x25", 4)) {
  memcpy(Loc, "\xf9\x0f\x1f\x84\x00\x00\x00\x00", 8);
  return true;
}

490

Style issue: put a blank line before comment.

ELF/InputSection.cpp

222

Style issue.

227

Style issue. You should use clang-format to fix format issues.

872

This function looks too dense because of the lack of any blank lines. Please make your new code look the same as other code in style.

[pcc]

ELF/Arch/X86_64.cpp

490

I think this should say %r10d, not %r10. Similarly %r11d below.

[saugustine]

In D46653#1118480, @ruiu wrote:

Could you read other functions in the same file and other files in the same directory and make your code look the same as others in coding style? Consistency is really important, and it is hard for me to read some code in this patch because of lack of consistency.

There is a variety of styles already in the file. I had followed Retpoline<ELFT>::writePltHeader for the format of the byte arrays and such. But I have no strong preference here.

So done.

ELF/Arch/X86_64.cpp

482

That means every single target that implements split stack also has to hand code the if-the-else routine for each replacement. That's a lot of boilerplate, but done.

483–486

There are two styles for this in the file. This function had followed Retpoline<ELFT>::writePltHeader (and those around it).

But done.

ELF/InputSection.cpp

852

Not sure if you are referring to getEnclosingFunction, or adjustCrossSplitFunctionPrologues. Either way:

1. This processing only happens if the input section was an executable split-stack section.

2. This loop does several very cheap checks on each relocation before it does the heavy lifting, and therefore skips most of them . I have rewritten it a bit to show that more accurately.

Also, I have added an additional filter that checks if the relocation references a function, which should limit the heavy work even more.

3. getEnclosingFunction (which is the really expensive part) is only called when the relocation crosses a split-stack to non-split-stack boundary. There are likely only very few of those. Nevertheless, I have updated the code to check if the enclosing prologue was already found. This should reduce the heavy lifting quite a bit more.

If performance is still too slow, making this fast probably means building a table of functions and their sizes per executable section, or possibly building it lazily and caching the results. What is your preferred solution?

[saugustine]

Respond to comments by rewriting parts, and reformatting.

[ruiu]

It has too many style issue which distracted me from actually reviewing code. Can you format your patch with clang-format-diff and upload again?

ELF/Arch/X86_64.cpp

479

I don't think we really need to support a split-stack for the x32 ABI because IIUC split-stack is used virtually only by Go, and Go doesn't support the x32.

482

Yes, it requires hand-coded if-else-if expressions, but that's in my opinion easier to read.

ELF/InputSection.cpp

222

Can you fix?

227

Ditto

842

L and R

846

Generally we use shorter names for variable name and function name. MorestackCallIter -> It

851

Please use pre-++ instead of post-++.

864

style

875

Style issue.

876

We generally avoid std::set because it is an ordered map and slower than llvm::DenseMap. If you don't need an ordered map, please use DenseMap instead.

881

Style

885

Style issue

889

Style issue.

902–903

Style

ELF/Target.h

66

Please follow the local convention -- all other functions that fail by default are in the .cpp file and uses llvm_unreachable to report an (impossible) error.

[saugustine]

Fix for new objdump issues. Finally figure out style issues. Update for other comments.

[grimar]

ELF/InputSection.cpp

223

When can this happen? That code is perhaps dead.

864

This line never executes when running the test cases.

883

This 'continue' is untested by a test case. The code is "dead" because of that.

888

This 'continue' is untested by a test case it seems.

901

The same - untested.

908

Untested.

910

Untested. enclosingPrologueAdjusted always returns false when running tests.

918

This error is untested (because of the broken tests first of all I believe).

test/ELF/Inputs/x86-64-split-stack-main.s

2

Excessive empty line.

13

Excessive empty line.

test/ELF/x86-64-split-stack-prologue-adjust-fail.s

6

/usr/local/google/home/saugustine/binutils/build/gold/ld-new -> ld.lld here and below

11

Looks like a mistype, you need to change "|&" to "|" as currently, it triggers "shell parser error" when trying to run tests under windows.

14

I do not know where these strings are coming from, I think you need to test the "Function call at ..." error message here
and these strings are coming from gold probably? (because of /usr/local/google/home/saugustine/binutils/build/gold/ld-new).

test/ELF/x86-64-split-stack-prologue-adjust-silent.s

7

You need to use llvm-objdump and not GNU objdump.

[ruiu]

ELF/Arch/X86_64.cpp

505

Isn't this function the same as the function which this function overrides? Can you remove?

ELF/InputSection.cpp

227–228

if (A && B) if (C && D) → if (A && B && C && D)

891

What else symbol can start with __morestack? Is this documented?

[MaskRay]

ELF/InputSection.cpp

891

% ar x /usr/lib/gcc/x86_64-linux-gnu/8/libgcc.a morestack.o 
% llvm-nm -U morestack.o | grep morestack
0000000000000037 T __morestack
0000000000000159 T __morestack_get_guard
000000000000011c T __morestack_large_model
000000000000016d T __morestack_make_guard
0000000000000000 T __morestack_non_split
0000000000000163 T __morestack_set_guard

generic-morestack.o in libgcc.a also defines some __morestack_* functions. I'm not sure whether they are related.

901

Not related to the revision. Are you using -fprofile-arcs -ftest-coverage + llvm-cov (http://lists.llvm.org/pipermail/llvm-dev/2018-April/122782.html) to collect coverage information?

[grimar]

ELF/InputSection.cpp

901

Yes.

But in simple cases (for writing/reviewing the patches, for example) just placing assert(false) or putting a breakpoint
is sufficient to check possible dead places.

[ruiu]

We do not need to aim for 100% test coverage for new code, just like the existing code is not covered 100% by the existing tests. I'd say we should aim for reasonable test coverage though.

[saugustine]

Much better code coverage in tests. Fix various style issues.

[saugustine]

Finally figured out the source of my clang-format problems (/usr/bin/clang-format was giving different results that $build_dir/bin/clang-format, so hopefully all the style issues are solved now.

Updated the test cases for changes to llvm-objdump, fixed other issues.

Also, thanks for all the code coverage comments. I have added several bits of code to the test-cases to ensure additional paths are taken, but I haven't managed to get all of them.

If the goal is 100% code coverage, the code will have to be much less conservative in its error checking.

ELF/Arch/X86_64.cpp

505

I get link errors if I remove the entire implementation (because the template <class ELFT> class X86_64 declares adjustPrologueForCrossSplitStack), so there needs to be some implementation for ELF32. I think the only way around that would be to add another layer of inheritance, which seems overkill.

Deleting the implementation also gives up feature parity with gnu gold, which does support 32-bit here. That's not important to me, but worth making an explicit decision over.

ELF/InputSection.cpp

223

This function was refactored out of getLocation, and the check was added there for https://reviews.llvm.org/D30889. getLocation still does the check.

Any synthetic section won't have a backing file. I have added a comment to that effect.

I don't think an assert would be any better for a client than returning a nullptr here, but I'll switch it if we want 100% code coverage. Up to you.

876

This is a pure set (keys but no values), so done with DenseSet instead of DenseMap.

If you would rather DenseMap, should I just duplicate the key for the value?

883

I've spent quite a bit of time trying to write a test case that triggers executes the continue, but I haven't managed to figure one out.

So I'm not sufficiently clever to write a test case to trigger this line, but I'm not convinced it can never happen.

888

I've tried to write test-cases to execute this continue, but have been unable to do so. They protect against an erroneous or strange input.

I've just deleted these two lines, if someone manages to trigger this case, lld will just crash.

891

They are related.

I don't know of any formal documentation of the other functions, but we really don't want to mess around with any of them.

901

I have added code to test this case.

908

I have deleted these lines. Again, this seems somewhat risky to me, but I have been unable to write a test case where it would happen.

test/ELF/x86-64-split-stack-prologue-adjust-silent.s

7

Of course. This was waiting for https://reviews.llvm.org/D48554 to land. And now that it has, I have switched it.

[ruiu]

ELF/InputSection.cpp

876

Oh sorry I should have said DenseSet. That was just a typo.

915

Error messages should start with a lowercase letter and shouldn't end with a period.

[grimar]

ELF/InputSection.cpp

223

I do not think it is possible to call this function for synthetic sections for your case.

getLocation already have the check and your new code does not seem is able to call it for synthetics,
because I believe they have Relocations empty, so this piece is dead.
I would just remove it, assert would be excessive as code anyways would crash.

883

The following test triggers this continue.

# REQUIRES: x86
# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
# RUN: ld.lld %t1.o -o %t

.local foo
foo:

.section .text,"ax",@progbits
 .quad foo
	
.section	.note.GNU-stack,"",@progbits
.section	.note.GNU-split-stack,"",@progbits

You could merge it with x86-64-split-stack-prologue-adjust-success.s I think.

888

The lines are still there.

I was able to trigger this case after adding the call foo@plt and -shared
to your x86-64-split-stack-prologue-adjust-success.s test:

# RUN: ld.lld --defsym __morestack=0x100 --defsym __morestack_non_split=0x200 %t1.o %t2.o -shared -o %t
...

.size	split,. - split

call foo@plt
	
.section	.note.GNU-stack,"",@progbits
.section	.note.GNU-split-stack,"",@progbits

[saugustine]

Cleanup error message. Small amounts of additional coverage.

[saugustine]

ELF/InputSection.cpp

888

Using "-shared" creates problems because llvm-objdump doesn't support .plt sections very well.

https://bugs.llvm.org/show_bug.cgi?id=38186

Any check using both -shared and llvm-objdump will likely be effectively a bitwise comparison.

I would like not to block this change on getting that bug fixed, just so that we can have a single extra line of coverage, in near trivial code.

Can we just not have coverage for this single line?

[grimar]

I have no more comments here.

ELF/InputSection.cpp

888

Go ahead, I'll handle this after your commit.

[saugustine]

I have committed this change as r337332.

[saugustine]

Ruiu is out until next week, but his last round of comments were just with error message formatting, and I have addressed them. Committed as r337332.

ELF/Arch/X86_64.cpp

public:
 
   RelExpr adjustRelaxExpr(RelType Type, const uint8_t *Data,
                           RelExpr Expr) const override;
   void relaxGot(uint8_t *Loc, uint64_t Val) const override;
   void relaxTlsGdToIe(uint8_t *Loc, RelType Type, uint64_t Val) const override;
   void relaxTlsGdToLe(uint8_t *Loc, RelType Type, uint64_t Val) const override;
   void relaxTlsIeToLe(uint8_t *Loc, RelType Type, uint64_t Val) const override;
   void relaxTlsLdToLe(uint8_t *Loc, RelType Type, uint64_t Val) const override;
+  bool adjustPrologueForCrossSplitStack(uint8_t *Loc,
+                                        uint8_t *End) const override;
 
 private:
   void relaxGotNoPic(uint8_t *Loc, uint64_t Val, uint8_t Op,
                      uint8_t ModRm) const;
 };
 } // namespace
 
 template <class ELFT> X86_64<ELFT>::X86_64() {
void X86_64<ELFT>::relaxGot(uint8_t *Loc, uint64_t Val) const {
   // Convert "jmp *foo@GOTPCREL(%rip)" to "jmp foo; nop".
   // jmp doesn't return, so it is fine to use nop here, it is just a stub.
   assert(ModRm == 0x25);
   Loc[-2] = 0xe9; // jmp
   Loc[3] = 0x90;  // nop
   write32le(Loc - 1, Val + 1);
 }
 
+// A split-stack prologue starts by checking the amount of stack remaining
+// in one of two ways:
+// A) Comparing of the stack pointer to a field in the tcb.
+// B) Or a load of a stack pointer offset with an lea to r10 or r11.
+template <>
+bool X86_64<ELF64LE>::adjustPrologueForCrossSplitStack(uint8_t *Loc,
+                                                       uint8_t *End) const {
+  // Replace "cmp %fs:0x70,%rsp" and subsequent branch
+  // with "stc, nopl 0x0(%rax,%rax,1)"
+  if (Loc + 8 < End && memcmp(Loc, "\x64\x48\x3b\x24\x25", 4) == 0) {
+    memcpy(Loc, "\xf9\x0f\x1f\x84\x00\x00\x00\x00", 8);
+    return true;
+  }
+
+  // Adjust "lea -0x200(%rsp),%r10" to lea "-0x4200(%rsp),%r10"
+  if (Loc + 7 < End && memcmp(Loc, "\x4c\x8d\x94\x24\x00\xfe\xff", 7) == 0) {
+    memcpy(Loc, "\x4c\x8d\x94\x24\x00\xbe\xff", 7);
+    return true;
+  }
+
+  // Adjust "lea -0x200(%rsp),%r11" to lea "-0x4200(%rsp),%r11"
+  if (Loc + 7 < End && memcmp(Loc, "\x4c\x8d\x9c\x24\x00\xfe\xff", 7) == 0) {
+    memcpy(Loc, "\x4c\x8d\x9c\x24\x00\xbe\xff", 7);
+    return true;
+  }
+  return false;
+}
+
+template <>
+bool X86_64<ELF32LE>::adjustPrologueForCrossSplitStack(uint8_t *Loc,
+                                                       uint8_t *End) const {
+  llvm_unreachable("Target doesn't support split stacks.");
+}
+
 // These nonstandard PLT entries are to migtigate Spectre v2 security
 // vulnerability. In order to mitigate Spectre v2, we want to avoid indirect
 // branch instructions such as `jmp *GOTPLT(%rip)`. So, in the following PLT
 // entries, we use a CALL followed by MOV and RET to do the same thing as an
 // indirect jump. That instruction sequence is so-called "retpoline".
 //
 // We have two types of retpoline PLTs as a size optimization. If `-z now`
 // is specified, all dynamic symbols are resolved at load-time. Thus, when

ELF/InputFiles.h

public:
   // R_MIPS_GPREL16 / R_MIPS_GPREL32 relocations.
   uint32_t MipsGp0 = 0;
 
   // Name of source file obtained from STT_FILE symbol value,
   // or empty string if there is no such symbol in object file
   // symbol table.
   StringRef SourceFile;
 
+  // True if the file defines functions compiled with
+  // -fsplit-stack. Usually false.
+  bool SplitStack = false;
+
+  // True if the file defines functions compiled with -fsplit-stack,
+  // but had one or more functions with the no_split_stack attribute.
+  bool SomeNoSplitStack = false;
+
 private:
   void
   initializeSections(llvm::DenseSet<llvm::CachedHashStringRef> &ComdatGroups);
   void initializeSymbols();
   void initializeJustSymbols();
   void initializeDwarf();
   InputSectionBase *getRelocTarget(const Elf_Shdr &Sec);
   InputSectionBase *createInputSection(const Elf_Shdr &Sec);

ELF/InputFiles.cpp

InputSectionBase *ObjFile<ELFT>::createInputSection(const Elf_Shdr &Sec) {
   // reasons. Failure to do so may result in a serious security issue.
   // Therefore, we make LLD always add PT_GNU_STACK unless it is
   // explicitly told to do otherwise (by -z execstack). Because the stack
   // executable-ness is controlled solely by command line options,
   // .note.GNU-stack sections are simply ignored.
   if (Name == ".note.GNU-stack")
     return &InputSection::Discarded;
 
-  // Split stacks is a feature to support a discontiguous stack. At least
-  // as of 2017, it seems that the feature is not being used widely.
-  // Only GNU gold supports that. We don't. For the details about that,
-  // see https://gcc.gnu.org/wiki/SplitStacks
+  // Split stacks is a feature to support a discontiguous stack,
+  // commonly used in the programming language Go. For the details,
+  // see https://gcc.gnu.org/wiki/SplitStacks. An object file compiled
+  // for split stack will include a .note.GNU-split-stack section.
   if (Name == ".note.GNU-split-stack") {
-    error(toString(this) +
-          ": object file compiled with -fsplit-stack is not supported");
+    if (Config->Relocatable) {
+      error("Cannot mix split-stack and non-split-stack in a relocatable link");
+      return &InputSection::Discarded;
+    }
+    this->SplitStack = true;
+    return &InputSection::Discarded;
+  }
+
+  // An object file cmpiled for split stack, but where some of the
+  // functions were compiled with the no_split_stack_attribute will
+  // include a .note.GNU-no-split-stack section.
+  if (Name == ".note.GNU-no-split-stack") {
+    this->SomeNoSplitStack = true;
     return &InputSection::Discarded;
   }
 
   // The linkonce feature is a sort of proto-comdat. Some glibc i386 object
   // files contain definitions of symbol "__x86.get_pc_thunk.bx" in linkonce
   // sections. Drop those sections to avoid duplicate symbol errors.
   // FIXME: This is glibc PR20543, we should remove this hack once that has been
   // fixed for a while.
   if (Name.startswith(".gnu.linkonce."))
     return &InputSection::Discarded;
 

ELF/InputSection.h

public:
 
   InputSectionBase(InputFile *File, uint64_t Flags, uint32_t Type,
                    uint64_t Entsize, uint32_t Link, uint32_t Info,
                    uint32_t Alignment, ArrayRef<uint8_t> Data, StringRef Name,
                    Kind SectionKind);
 
   static bool classof(const SectionBase *S) { return S->kind() != Output; }
 
-  // The file which contains this section. It's dynamic type is always
+  // The file which contains this section. Its dynamic type is always
   // ObjFile<ELFT>, but in order to avoid ELFT, we use InputFile as
   // its static type.
   InputFile *File;
 
   template <class ELFT> ObjFile<ELFT> *getFile() const {
     return cast_or_null<ObjFile<ELFT>>(File);
   }
 
public:
   // InputSections that are dependent on us (reverse dependency for GC)
   llvm::TinyPtrVector<InputSection *> DependentSections;
 
   // Returns the size of this section (even if this is a common or BSS.)
   size_t getSize() const;
 
   InputSection *getLinkOrderDep() const;
 
+  // Get the function symbol that encloses this offset from within the
+  // section.
+  template <class ELFT>
+  Defined *getEnclosingFunction(uint64_t Offset);
+
   // Compilers emit zlib-compressed debug sections if the -gz option
   // is given. This function checks if this section is compressed, and
   // if so, decompress in memory.
   void maybeDecompress();
 
   // Returns a source location string. Used to construct an error message.
   template <class ELFT> std::string getLocation(uint64_t Offset);
   std::string getSrcMsg(const Symbol &Sym, uint64_t Offset);
   std::string getObjMsg(uint64_t Offset);
 
   // Each section knows how to relocate itself. These functions apply
   // relocations, assuming that Buf points to this section's copy in
   // the mmap'ed output buffer.
   template <class ELFT> void relocate(uint8_t *Buf, uint8_t *BufEnd);
   void relocateAlloc(uint8_t *Buf, uint8_t *BufEnd);
 
   // The native ELF reloc data type is not very convenient to handle.
   // So we convert ELF reloc records to our own records in Relocations.cpp.
   // This vector contains such "cooked" relocations.
   std::vector<Relocation> Relocations;
 
+  // A function compiled with -fsplit-stack calling a function
+  // compiled without -fsplit-stack needs its prologue adjusted. Find
+  // such functions and adjust their prologues.  This is very similar
+  // to relocation. See https://gcc.gnu.org/wiki/SplitStacks for more
+  // information.
+  template <typename ELFT>
+  void adjustSplitStackFunctionPrologues(uint8_t *Buf, uint8_t *End);
+
+
   template <typename T> llvm::ArrayRef<T> getDataAs() const {
     size_t S = Data.size();
     assert(S % sizeof(T) == 0);
     return llvm::makeArrayRef<T>((const T *)Data.data(), S / sizeof(T));
   }
 
 private:
   // A pointer that owns decompressed data if a section is compressed by zlib.

ELF/InputSection.cpp

 //===- InputSection.cpp ---------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputSection.h"
 #include "Config.h"
 #include "EhFrame.h"
 #include "InputFiles.h"
 #include "LinkerScript.h"
 #include "OutputSections.h"
 #include "Relocations.h"
+#include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "Thunks.h"
 #include "lld/Common/ErrorHandler.h"
 #include "lld/Common/Memory.h"
 #include "llvm/Object/Decompressor.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Compression.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Threading.h"
 #include "llvm/Support/xxhash.h"
+#include <algorithm>
 #include <mutex>
+#include <set>
+#include <vector>
 
 using namespace llvm;
 using namespace llvm::ELF;
 using namespace llvm::object;
 using namespace llvm::support;
 using namespace llvm::support::endian;
 using namespace llvm::sys;
 

 }
 
 InputSection *InputSectionBase::getLinkOrderDep() const {
   assert(Link);
   assert(Flags & SHF_LINK_ORDER);
   return cast<InputSection>(File->getSections()[Link]);
 }
 
+// Find a function symbol that encloses a given location.
+template <class ELFT>
+Defined *InputSectionBase::getEnclosingFunction(uint64_t Offset) {
+  // We don't have a file for synthetic sections.
+  if (getFile<ELFT>() == nullptr)
+    return nullptr;
+
+  for (Symbol *B : File->getSymbols())
+    if (Defined *D = dyn_cast<Defined>(B))
+      if (D->Section == this && D->Type == STT_FUNC &&
+          D->Value <= Offset && Offset < D->Value + D->Size)
+        return D;
+  return nullptr;
+}
+
 // Returns a source location string. Used to construct an error message.
 template <class ELFT>
 std::string InputSectionBase::getLocation(uint64_t Offset) {
   // We don't have file for synthetic sections.
   if (getFile<ELFT>() == nullptr)
     return (Config->OutputFile + ":(" + Name + "+0x" + utohexstr(Offset) + ")")
         .str();
 
   // First check if we can get desired values from debugging information.
   std::string LineInfo = getFile<ELFT>()->getLineInfo(this, Offset);
   if (!LineInfo.empty())
     return LineInfo;
 
   // File->SourceFile contains STT_FILE symbol that contains a
   // source file name. If it's missing, we use an object file name.
   std::string SrcFile = getFile<ELFT>()->SourceFile;
   if (SrcFile.empty())
     SrcFile = toString(File);
 
-  // Find a function symbol that encloses a given location.
-  for (Symbol *B : File->getSymbols())
-    if (auto *D = dyn_cast<Defined>(B))
-      if (D->Section == this && D->Type == STT_FUNC)
-        if (D->Value <= Offset && Offset < D->Value + D->Size)
-          return SrcFile + ":(function " + toString(*D) + ")";
+  if (Defined *D = getEnclosingFunction<ELFT>(Offset))
 
   // If there's no symbol, print out the offset in the section.
   return (SrcFile + ":(" + Name + "+0x" + utohexstr(Offset) + ")").str();
 }
 
 // This function is intended to be used for constructing an error message.
 // The returned message looks like this:
 //
if (Sym.isTls() && !Out::TlsPhdr)
       Target->relocateOne(BufLoc, Type, 0);
     else
       Target->relocateOne(BufLoc, Type, SignExtend64<Bits>(Sym.getVA(Addend)));
   }
 }
 
 template <class ELFT>
 void InputSectionBase::relocate(uint8_t *Buf, uint8_t *BufEnd) {
+  if (Flags & SHF_EXECINSTR)
+    adjustSplitStackFunctionPrologues<ELFT>(Buf, BufEnd);
+
   if (Flags & SHF_ALLOC) {
     relocateAlloc(Buf, BufEnd);
     return;
   }
 
   auto *Sec = cast<InputSection>(this);
   if (Sec->AreRelocsRela)
     Sec->relocateNonAlloc<ELFT>(Buf, Sec->template relas<ELFT>());
case R_PPC_CALL:
       break;
     default:
       Target->relocateOne(BufLoc, Type, TargetVA);
       break;
     }
   }
 }
 
+// For each function-defining prologue, find any calls to __morestack,
+// and replace them with calls to __morestack_non_split.
+static void switchMorestackCallsToMorestackNonSplit(
+    llvm::DenseSet<Defined *>& Prologues,
+    std::vector<Relocation *>& MorestackCalls) {
+
+  // If the target adjusted a function's prologue, all calls to
+  // __morestack inside that function should be switched to
+  // __morestack_non_split.
+  Symbol *MoreStackNonSplit = Symtab->find("__morestack_non_split");
+
+  // Sort both collections to compare addresses efficiently.
+  llvm::sort(MorestackCalls.begin(), MorestackCalls.end(),
+             [](const Relocation *L, const Relocation *R) {
+               return L->Offset < R->Offset;
+             });
+  std::vector<Defined *> Functions(Prologues.begin(), Prologues.end());
+  llvm::sort(
+      Functions.begin(), Functions.end(),
+      [](const Defined *L, const Defined *R) { return L->Value < R->Value; });
+
+  auto It = MorestackCalls.begin();
+  for (Defined *F : Functions) {
+    // Find the first call to __morestack within the function.
+    while (It != MorestackCalls.end() && (*It)->Offset < F->Value)
+      ++It;
+    // Adjust all calls inside the function.
+    while (It != MorestackCalls.end() && (*It)->Offset < F->Value + F->Size) {
+      (*It)->Sym = MoreStackNonSplit;
+      ++It;
+    }
+  }
+}
+
+static bool
+enclosingPrologueAdjusted(uint64_t Offset,
+                          const llvm::DenseSet<Defined *> &Prologues) {
+  for (Defined *F : Prologues)
+    if (F->Value <= Offset && Offset < F->Value + F->Size)
+      return true;
+  return false;
+}
+
+// If a function compiled for split stack calls a function not
+// compiled for split stack, then the caller needs its prologue
+// adjusted to ensure that the called function will have enough stack
+// available. Find those functions, and adjust their prologues.
+template <class ELFT>
+void InputSectionBase::adjustSplitStackFunctionPrologues(uint8_t *Buf,
+                                                         uint8_t *End) {
+  if (!getFile<ELFT>()->SplitStack)
+    return;
+  llvm::DenseSet<Defined *> AdjustedPrologues;
+  std::vector<Relocation *> MorestackCalls;
+
+  for (Relocation &Rel : Relocations) {
+    // Local symbols can't possibly be cross-calls, and should have been
+    // resolved long before this line.
+    if (Rel.Sym->isLocal())
+      continue;
+
+    Defined *D = dyn_cast<Defined>(Rel.Sym);
+    // A reference to an undefined symbol was an error, and should not
+    // have gotten to this point.
+    if (!D)
+      continue;
+
+    // Ignore calls into the split-stack api.
+    if (D->getName().startswith("__morestack")) {
+      if (D->getName().equals("__morestack"))
+        MorestackCalls.push_back(&Rel);
+      continue;
+    }
+
+    // A relocation to non-function isn't relevant. Sometimes
+    // __morestack is not marked as a function, so this check comes
+    // after the name check.
+    if (D->Type != STT_FUNC)
+      continue;
+
+    if (enclosingPrologueAdjusted(Rel.Offset, AdjustedPrologues))
+      continue;
+
+    if (Defined *F = getEnclosingFunction<ELFT>(Rel.Offset)) {
+      if (Target->adjustPrologueForCrossSplitStack(Buf + F->Value, End)) {
+        AdjustedPrologues.insert(F);
+        continue;
+      }
+    }
+    if (!getFile<ELFT>()->SomeNoSplitStack)
+      error("Function call at " + getErrorLocation(Buf + Rel.Offset) +
+            "crosses a split-stack boundary, but unable " +
+            "to adjust the enclosing function's prologue.");
+  }
+  switchMorestackCallsToMorestackNonSplit(AdjustedPrologues, MorestackCalls);
+}
+
 template <class ELFT> void InputSection::writeTo(uint8_t *Buf) {
   if (Type == SHT_NOBITS)
     return;
 
   if (auto *S = dyn_cast<SyntheticSection>(this)) {
     S->writeTo(Buf + OutSecOff);
     return;
   }

ELF/Target.h

public:
   // a dynamic relocation.
   virtual bool usesOnlyLowPageBits(RelType Type) const;
 
   // Decide whether a Thunk is needed for the relocation from File
   // targeting S.
   virtual bool needsThunk(RelExpr Expr, RelType RelocType,
                           const InputFile *File, uint64_t BranchAddr,
                           const Symbol &S) const;
+
+  // The function with a prologue starting at Loc was compiled with
+  // -fsplit-stack and it calls a function compiled without. Adjust the prologue
+  // to do the right thing. See https://gcc.gnu.org/wiki/SplitStacks.
+  virtual bool adjustPrologueForCrossSplitStack(uint8_t *Loc,
+                                                uint8_t *End) const;
+
   // Return true if we can reach Dst from Src with Relocation RelocType
   virtual bool inBranchRange(RelType Type, uint64_t Src,
                              uint64_t Dst) const;
   virtual RelExpr getRelExpr(RelType Type, const Symbol &S,
                              const uint8_t *Loc) const = 0;
 
   virtual void relocateOne(uint8_t *Loc, RelType Type, uint64_t Val) const = 0;
 

ELF/Target.cpp

 
 bool TargetInfo::usesOnlyLowPageBits(RelType Type) const { return false; }
 
 bool TargetInfo::needsThunk(RelExpr Expr, RelType Type, const InputFile *File,
                             uint64_t BranchAddr, const Symbol &S) const {
   return false;
 }
 
+bool TargetInfo::adjustPrologueForCrossSplitStack(uint8_t *Loc,
+                                                  uint8_t *End) const {
+  llvm_unreachable("Target doesn't support split stacks.");
+}
+
+
 bool TargetInfo::inBranchRange(RelType Type, uint64_t Src, uint64_t Dst) const {
   return true;
 }
 
 void TargetInfo::writeIgotPlt(uint8_t *Buf, const Symbol &S) const {
   writeGotPlt(Buf, S);
 }
 

test/ELF/Inputs/x86-64-split-stack-main.s

+  .text
+
+  .global non_split
+  .type non_split,@function
+non_split:
+  retq
+  .size non_split,. - non_split
+
+  .global non_function_text_symbol
+non_function_text_symbol:
+  .byte 0x01
+  .type non_function_text_symbol,@STT_OBJECT
+  .size non_function_text_symbol, 1
+
+
+  .section  .note.GNU-stack,"",@progbits

test/ELF/splitstacks.s

-# REQUIRES: x86
-# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
-
-# RUN: not ld.lld %t1.o -o %t 2>&1 | FileCheck %s
-# CHECK: .o: object file compiled with -fsplit-stack is not supported
-
-.globl _start
-_start:
- nop
-
-.section .note.GNU-split-stack,"",@progbits

test/ELF/x86-64-split-stack-prologue-adjust-fail.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/x86-64-split-stack-main.s -o %t2.o
+
+# RUN: not ld.lld --defsym __morestack=0x100 %t1.o %t2.o -o %t 2>&1 | FileCheck %s
+
+# An unknown prologue gives a match failure
+# CHECK: unable to adjust the enclosing function's
+
+# RUN: not ld.lld -r --defsym __morestack=0x100 %t1.o %t2.o -o %t 2>&1 | FileCheck %s -check-prefix=RELOCATABLE
+# RELOCATABLE: Cannot mix split-stack and non-split-stack in a relocatable link
+
+  .text
+
+  .global unknown_prologue
+  .type unknown_prologue,@function
+unknown_prologue:
+  push  %rbp
+  mov %rsp,%rbp
+  cmp %fs:0x70,%rsp
+  jae 1f
+  callq __morestack
+  retq
+1:
+  callq non_split
+  leaveq
+  retq
+
+  .size unknown_prologue,. - unknown_prologue
+
+  .section  .note.GNU-split-stack,"",@progbits

test/ELF/x86-64-split-stack-prologue-adjust-silent.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/x86-64-split-stack-main.s -o %t2.o
+
+# RUN: ld.lld --defsym __morestack=0x100 %t1.o %t2.o -o %t
+# RUN: llvm-objdump -d %t 2>&1 | FileCheck %s
+
+# An unknown prologue ordinarily gives a match failure, except that this
+# object file includes a .note.GNU-no-split-stack section, which tells the
+# linker to expect such prologues, and therefore not error.
+
+# CHECK: __morestack
+
+  .text
+
+  .global unknown_prologue
+  .type unknown_prologue,@function
+unknown_prologue:
+  push %rbp
+  mov %rsp,%rbp
+  cmp %fs:0x70,%rsp
+  jae 1f
+  callq __morestack
+  retq
+1:
+  callq non_split
+  leaveq
+  retq
+
+  .size unknown_prologue,. - unknown_prologue
+  .section .note.GNU-split-stack,"",@progbits
+  .section .note.GNU-no-split-stack,"",@progbits

test/ELF/x86-64-split-stack-prologue-adjust-success.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t1.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %p/Inputs/x86-64-split-stack-main.s -o %t2.o
+
+# RUN: ld.lld --defsym __morestack=0x100 --defsym __morestack_non_split=0x200 %t1.o %t2.o -o %t
+# RUN: llvm-objdump -d %t | FileCheck %s
+
+# Avoid duplicating the prologue for every test via macros.
+
+.macro prologue1 function_to_call
+  .global prologue1_calls_\function_to_call
+  .type prologue1_calls_\function_to_call,@function
+prologue1_calls_\function_to_call:
+  cmp %fs:0x70,%rsp
+  jae 1f
+  callq __morestack
+  retq
+1:
+  # Various and duplicate calls to ensure every code path is taken.
+  callq \function_to_call
+  callq \function_to_call
+  callq 1b
+  callq non_function_text_symbol
+  retq
+  .size  prologue1_calls_\function_to_call,. - prologue1_calls_\function_to_call
+.endm
+
+.macro prologue2 function_to_call register
+  .global prologue2_calls_\function_to_call\register
+  .type prologue2_calls_\function_to_call\register,@function
+prologue2_calls_\function_to_call\register:
+  lea -0x200(%rsp),%\register
+  cmp %fs:0x70,%\register
+  jae 1f
+  callq __morestack
+  retq
+1:
+  # Various and duplicate calls to ensure every code path is taken.
+  callq \function_to_call
+  callq \function_to_call
+  callq 1b
+  callq non_function_text_symbol
+  retq
+  .size  prologue2_calls_\function_to_call\register,. - prologue2_calls_\function_to_call\register
+.endm
+
+  .text
+
+# For split-stack code calling split-stack code, ensure prologue v1 still
+# calls plain __morestack, and that any raw bytes written to the prologue
+# make sense.
+# CHECK: prologue1_calls_split:
+# CHECK-NEXT: cmp{{.*}}%fs:{{[^,]*}},{{.*}}%rsp
+# CHECK: jae{{.*$}}
+# CHECK-NEXT: callq{{.*}}<__morestack>
+
+prologue1 split
+
+# For split-stack code calling split-stack code, ensure prologue v2 still
+# calls plain __morestack, that any raw bytes written to the prologue
+# make sense, and that the register number is preserved.
+# CHECK: prologue2_calls_splitr10:
+# CHECK-NEXT: lea{{.*}} -{{[0-9]+}}(%rsp),{{.*}}%r10
+# CHECK: cmp{{.*}}%fs:{{[^,]*}},{{.*}}%r{{[0-9]+}}
+# CHECK: jae{{.*}}
+# CHECK-NEXT: callq{{.*}}<__morestack>
+
+prologue2 split r10
+
+# CHECK: prologue2_calls_splitr11:
+# CHECK-NEXT: lea{{.*}} -{{[0-9]+}}(%rsp),{{.*}}%r11
+# CHECK: cmp{{.*}}%fs:{{[^,]*}},{{.*}}%r{{[0-9]+}}
+# CHECK: jae{{.*}}
+# CHECK-NEXT: callq{{.*}}<__morestack>
+
+prologue2 split r11
+
+# For split-stack code calling non-split-stack code, ensure prologue v1
+# calls __morestack_non_split, and that any raw bytes written to the prologue
+# make sense.
+# CHECK: prologue1_calls_non_split:
+# CHECK-NEXT: stc{{.*$}}
+# CHECK-NEXT: nopl{{.*$}}
+# CHECK: jae{{.*$}}
+# CHECK-NEXT: callq{{.*}}<__morestack_non_split>
+
+prologue1 non_split
+
+# For split-stack code calling non-split-stack code, ensure prologue v2
+# calls __morestack_non_split, that any raw bytes written to the prologue
+# make sense, and that the register number is preserved
+# CHECK: prologue2_calls_non_splitr10:
+# CHECK-NEXT: lea{{.*$}}
+# CHECK: cmp{{.*}}%fs:{{[^,]*}},{{.*}}%r10
+# CHECK: jae{{.*$}}
+# CHECK-NEXT: callq{{.*}}<__morestack_non_split>
+
+prologue2 non_split r10
+
+# CHECK: prologue2_calls_non_splitr11:
+# CHECK-NEXT: lea{{.*$}}
+# CHECK: cmp{{.*}}%fs:{{[^,]*}},{{.*}}%r11
+# CHECK: jae{{.*$}}
+# CHECK-NEXT: callq{{.*}}<__morestack_non_split>
+
+prologue2 non_split r11
+
+
+  .global split
+  .type split,@function
+split:
+  retq
+
+  .size split,. - split
+
+  .section  .note.GNU-stack,"",@progbits
+  .section  .note.GNU-split-stack,"",@progbits