[ELF] - Implemented linkerscript sections padding.

[grimar]

Summary

BSD linker scripts contain special cases to add NOP padding to code sections. Syntax is next:

.init:
 {
   KEEP (*(.init))
 } =0x90909090

(0x90 is NOP)

This patch implements that functionality.

[ruiu]

ELF/InputSection.cpp

250–261

This is not a right place to add this code. You want to add code to OutputSection<ELFT>::writeTo instead. I think the following code should suffice as an initial implementation.

+static void fill(uint8_t *Buf, size_t Size, ArrayRef<uint8_t> A) {
+  size_t I = 0;
+  for (; I < Size; I += A.size())
+    memcpy(Buf + I, A.data(), A.size());
+  memcpy(Buf + I, A.data(), Size - I);
+}
+
 template <class ELFT> void OutputSection<ELFT>::writeTo(uint8_t *Buf) {
+  ArrayRef<uint8_t> Filler = Script->getFiller(Name);
+  if (!Filler.empty())
+    fill(Buf, getSize(), Filler);
   for (InputSection<ELFT> *C : Sections)
     C->writeTo(Buf);
 }

[grimar]

ELF/InputSection.cpp

250–261

Your code mixes the filling byters order it seems. I mean if we have two sections, 1 byte each with alignment 4, then if we have =0x11223344 filler:

My code will produce: [SEC1] 0x11 0x22 0x33 [SEC2].
Your one will have [SEC1] 0x22 0x33 0x44 [SEC2].

I am not sure how much that is important as I saw fillers are used for NOPs which always were 0x90909090. If we are assuming that that is not important at all, then instead of fill() call we can use

memset(Buf, Filler[0], getSize());

But if we want to support the order (and use all bytes), then I will adopt the algorithm.
Anyways I dont think we should use the fill() as it is now since it is somewhere in the middle.
What do you think ?

[ruiu]

ELF/InputSection.cpp

250–261

I understand your point. As you might have implied, fill() should just work, so I'd like to go with that. That is way simpler than the current approach and probably faster (memcpy is usually pretty fast, which I experimented with Windows LLD.) I don't think setting the first byte is a good idea. NOP is one byte instruction on x86, but on RISC processors it is not.

[grimar]

• Addressed review comments.

[grimar]

ELF/InputSection.cpp

250–261

Well, and the last means that version of fill() from above will not work as expected on RISC. It anyways will not work as expected for cases where one byte is not enough (because of shifted bytes). Moreover, what it worse, some times it _can_ work correctly, so that is random bug.

I don't argue about it is faster and simplier than current approach. Thats true. I just want to say that fill() should ideally be fixed to be correct and I am ready to do that. Since you insisted to use it as is, I did that in current patch iteration (just fixed the buffer overrun).

Current implementation should at least have assert/error that checks that all 4 bytes are equal I think.

[ruiu]

ELF/LinkerScript.cpp

413–420

So you cannot use getAsInteger because it may be larger than the integer size.

ELF/LinkerScript.h

41

I realized that I didn't actually understand what you said until now (because my approach should work and memcpy is the right way to copy filler to the section). You seems to misunderstand the feature.

If a filler is of the form 0x<hex digits>, then it is an arbitrary long sequence of hex digits. It is not a four byte value.

So this type needs to be std::vector<uint8_t>.

[grimar]

ELF/LinkerScript.h

41

Let me try to explain again then. Consider the next script and code:

SECTIONS {
 .mysec : { *(.mysec*) } =0x11223344 
}

.section        .mysec.1,"a"
.align  4
.byte   0x66

.section        .mysec.2,"a"
.align  4
.byte   0x66

.globl _start
_start:
 nop

Output from my initial implementation would be: 0x66 0x11 0x22 0x33 0x66. What is equal to gold and bytes are used correctly (in growing order, started from first for each 'hole' heeds filling).

Output from your approach is: 0x66 0x22 0x33 0x44 0x66. So bytes are shifted what makes no sence in using bytes at all, since result is unexpected.

So this type needs to be std::vector<uint8_t>.

Agree here, just checked gold, it allows any length filler it seems:

SECTIONS
{
  . = 0x08048000 + SIZEOF_HEADERS;
  .mysec        : { *(.mysec*) } =0x11223344556677889911223344
}

[ruiu]

ELF/LinkerScript.h

41

I think I completely understand your point, and still I prefer my approach.

Speaking of Filler's type, can you change the type to std::vector<uint8_t>?

[grimar]

• Addressed review comments

[ruiu]

ELF/LinkerScript.cpp

52–55

Why don't you just do

for (OutSection &C : OutSections)
  if (C.Name == Name)
    return C.Filler;
return {};

?

62–63

This is a bit odd way of doing it because we can use lambdas.

auto I = std::find_if(Begin, End, [](OutSection &C) { return C.Name == A; });
auto J = std::find_if(Begin, End, [](OutSection &C) { return C.Name == B; });

432–439

Define this piece of code as a separate function, say,

std::vector<uint8_t> readHex(StringRef S);

and replace this code with

OutSec.Filler = readHex(Tok);

[grimar]

• Addressed review comments.
• Updated testcase.

ELF/LinkerScript.cpp

62–63

That because I used this functor in getFiller() either before.
Not sure that labdas are looking better here now.

btw that can be something like:

OutSection *I = nullptr;
OutSection *J = nullptr;
for (OutSection &C : OutSections) {
  if (!I && C.Name == A)
    I = &C;
  if (!J && C.Name == B)
    J = &C;
  if (I && J)
    return I < J ? -1 : 1;
}
return 0;

[ruiu]

ELF/LinkerScript.cpp

62–63

This new code with lambdas looks good to me.

400

Let's rename parseHex. (Because readSomething usually reads Something from the current token stream.)

402

I don't think you need to call reserve. We are handling tiny data, so allocation cost should be negligible.

406

slice(2, S.size()) -> substr(2)

430–431

Do you need to add check here? You can just go proceed.

[grimar]

• Addressed review comments

ELF/LinkerScript.cpp

400

Done.

402

Removed.

406

Done.

430–431

Removed check.

[ruiu]

LGTM

ELF/LinkerScript.cpp

50

return{} -> return {}

423

This is not safe because Tok may be empty.

if (Tok.startswith("="))

[grimar]

ELF/LinkerScript.cpp

423

Done.

[grimar]

ELF/LinkerScript.cpp

50

Done.

[grimar]

r262020

ELF/InputSection.h

public:
 
   // Relocation sections that refer to this one.
   SmallVector<const Elf_Shdr *, 1> RelocSections;
 
   // The offset from beginning of the output sections this section was assigned
   // to. The writer sets a value.
   uint64_t OutSecOff = 0;
 
+  // Amount of bytes padded from previous input section in the same output if
+  // any is exist.
+  uint64_t PadBehind = 0;
+
   static bool classof(const InputSectionBase<ELFT> *S);
 };
 
 // MIPS .reginfo section provides information on the registers used by the code
 // in the object file. Linker should collect this information and write a single
 // .reginfo section in the output file. The output section contains a union of
 // used registers masks taken from input .reginfo sections and final value
 // of the `_gp` symbol.  For details: Chapter 4 / "Register Information" at

ELF/InputSection.cpp

for (size_t I = 0; I < Num; ++I) {
     Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc, SymVA + A, Size + A,
                         findMipsPairedReloc(Buf, SymIndex, Type, NextRelocs));
   }
 }
 
 template <class ELFT> void InputSection<ELFT>::writeTo(uint8_t *Buf) {
   if (this->Header->sh_type == SHT_NOBITS)
     return;
+
+  // If there is some padding behind and value for padding is
+  // not null, this one fills the space repeating 4 bytes of
+  // padding value.
+  if (PadBehind && OutSec->PaddingValue) {
+    llvm::support::ubig32_t Bytes(OutSec->PaddingValue);
+    int I = OutSecOff - PadBehind;
+    while (PadBehind) {
+      Buf[OutSecOff - PadBehind] =
+          ((uint8_t *)&Bytes)[(OutSecOff - PadBehind - I) % 4];
+      --PadBehind;
+    }
+  }
+
   // Copy section contents from source object file to output file.
   ArrayRef<uint8_t> Data = this->getSectionData();
   memcpy(Buf + OutSecOff, Data.data(), Data.size());
 
   ELFFile<ELFT> &EObj = this->File->getObj();
   uint8_t *BufEnd = Buf + OutSecOff + Data.size();
   // Iterate over all relocation sections that apply to this section.
   for (const Elf_Shdr *RelSec : this->RelocSections) {

ELF/LinkerScript.h

public:
   template <class ELFT> bool match(InputSectionBase<ELFT> *S);
 
   StringRef Dest;
 
 private:
   StringRef SectionPattern;
 };
 
+struct OutSection {
+  StringRef Name;
+  uint32_t Padding = 0x0;
+};
+
 // This is a runner of the linker script.
 class LinkerScript {
   friend class ScriptParser;
 
 public:
   // Parses a linker script. Calling this function may update
   // this object and Config.
   void read(MemoryBufferRef MB);
 
-  template <class ELFT> StringRef getOutputSection(InputSectionBase<ELFT> *S);
+  template <class ELFT> StringRef getOutSectionName(InputSectionBase<ELFT> *S);
+  const OutSection *getOutputSection(StringRef Name) const;
   template <class ELFT> bool isDiscarded(InputSectionBase<ELFT> *S);
   int compareSections(StringRef A, StringRef B);
 
 private:
   // SECTIONS commands.
   std::vector<SectionRule> Sections;
 
-  // Output sections are sorted by this order.
-  std::vector<StringRef> SectionOrder;
+  // Output sections information.
+  // They are sorted by the order of the container.
+  std::vector<OutSection> OutSections;
 
   llvm::BumpPtrAllocator Alloc;
 };
 
 extern LinkerScript *Script;
 
 } // namespace elf2
 } // namespace lld
 
 #endif

ELF/LinkerScript.cpp

 using namespace llvm;
 using namespace llvm::object;
 using namespace lld;
 using namespace lld::elf2;
 
 LinkerScript *elf2::Script;
 
 template <class ELFT>
-StringRef LinkerScript::getOutputSection(InputSectionBase<ELFT> *S) {
+StringRef LinkerScript::getOutSectionName(InputSectionBase<ELFT> *S) {
   for (SectionRule &R : Sections)
     if (R.match(S))
       return R.Dest;
   return "";
 }
 
 template <class ELFT>
 bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
-  return getOutputSection(S) == "/DISCARD/";
+  return getOutSectionName(S) == "/DISCARD/";
 }
 
+struct FindSec {
+  StringRef Val;
+  bool operator()(const OutSection &C) { return C.Name == Val; }
+};
+
+const OutSection *LinkerScript::getOutputSection(StringRef Name) const {
+  auto I = std::find_if(OutSections.begin(), OutSections.end(), FindSec{Name});
+  if (I == OutSections.end())
+    return nullptr;
+  return &*I;
+}
 // A compartor to sort output sections. Returns -1 or 1 if both
 // A and B are mentioned in linker scripts. Otherwise, returns 0
 // to use the default rule which is implemented in Writer.cpp.
 int LinkerScript::compareSections(StringRef A, StringRef B) {
-  auto E = SectionOrder.end();
-  auto I = std::find(SectionOrder.begin(), E, A);
-  auto J = std::find(SectionOrder.begin(), E, B);
+  auto E = OutSections.end();
+  auto I = std::find_if(OutSections.begin(), E, FindSec{A});
+  auto J = std::find_if(OutSections.begin(), E, FindSec{B});
   if (I == E || J == E)
     return 0;
   return I < J ? -1 : 1;
 }
 
 // Returns true if S matches T. S may contain a meta character '*'
 // which matches zero or more occurrences of any character.
 static bool matchStr(StringRef S, StringRef T) {
public:
   void run();
 
 private:
   void setError(const Twine &Msg);
   static std::vector<StringRef> tokenize(StringRef S);
   static StringRef skipSpace(StringRef S);
   bool atEOF();
   StringRef next();
+  StringRef peek();
   bool skip(StringRef Tok);
   void expect(StringRef Expect);
 
   void addFile(StringRef Path);
 
   void readAsNeeded();
   void readEntry();
   void readExtern();
if (Error)
     return "";
   if (atEOF()) {
     setError("unexpected EOF");
     return "";
   }
   return Tokens[Pos++];
 }
 
+StringRef ScriptParser::peek() {
+  StringRef Tok = next();
+  if (Error)
+    return "";
+  --Pos;
+  return Tok;
+}
+
 bool ScriptParser::skip(StringRef Tok) {
   if (Error)
     return false;
   if (atEOF()) {
     setError("unexpected EOF");
     return false;
   }
   if (Tok != Tokens[Pos])

 }
 
 void ScriptParser::readSections() {
   expect("{");
   while (!Error && !skip("}"))
     readOutputSectionDescription();
 }
 
 void ScriptParser::readOutputSectionDescription() {
-  StringRef OutSec = next();
-  Script->SectionOrder.push_back(OutSec);
+  OutSection OutSec;
+  OutSec.Name = next();
   expect(":");
   expect("{");
   while (!Error && !skip("}")) {
     next(); // Skip input file name.
     expect("(");
     while (!Error && !skip(")"))
-      Script->Sections.push_back({OutSec, next()});
+      Script->Sections.push_back({OutSec.Name, next()});
+  }
+  StringRef Tok = peek();
+  if (Tok[0] == '=') {
+    Tok = Tok.substr(1);
+    uint32_t Val;
+    if (Tok.getAsInteger(0, Val)) {
+      error("Integer can't be parsed: " + Tok);
+      return;
+    }
+    OutSec.Padding = Val;
+    next();
   }
+  Script->OutSections.push_back(OutSec);
 }
 
 static bool isUnderSysroot(StringRef Path) {
   if (Config->Sysroot == "")
     return false;
   for (; !Path.empty(); Path = sys::path::parent_path(Path))
     if (sys::fs::equivalent(Config->Sysroot, Path))
       return true;
   return false;
 }
 
 // Entry point. The other functions or classes are private to this file.
 void LinkerScript::read(MemoryBufferRef MB) {
   StringRef Path = MB.getBufferIdentifier();
   ScriptParser(&Alloc, MB.getBuffer(), isUnderSysroot(Path)).run();
 }
 
-template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32LE> *);
-template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF32BE> *);
-template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64LE> *);
-template StringRef LinkerScript::getOutputSection(InputSectionBase<ELF64BE> *);
+template StringRef LinkerScript::getOutSectionName(InputSectionBase<ELF32LE> *);
+template StringRef LinkerScript::getOutSectionName(InputSectionBase<ELF32BE> *);
+template StringRef LinkerScript::getOutSectionName(InputSectionBase<ELF64LE> *);
+template StringRef LinkerScript::getOutSectionName(InputSectionBase<ELF64BE> *);
 
 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32LE> *);
 template bool LinkerScript::isDiscarded(InputSectionBase<ELF32BE> *);
 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64LE> *);
 template bool LinkerScript::isDiscarded(InputSectionBase<ELF64BE> *);
 
 template bool SectionRule::match(InputSectionBase<ELF32LE> *);
 template bool SectionRule::match(InputSectionBase<ELF32BE> *);
 template bool SectionRule::match(InputSectionBase<ELF64LE> *);
 template bool SectionRule::match(InputSectionBase<ELF64BE> *);

ELF/OutputSections.h

public:
   void setFileOffset(uintX_t Off) { Header.sh_offset = Off; }
   void setSHName(unsigned Val) { Header.sh_name = Val; }
   void writeHeaderTo(Elf_Shdr *SHdr);
   StringRef getName() { return Name; }
 
   virtual void addSection(InputSectionBase<ELFT> *C) {}
 
   unsigned SectionIndex;
+  uint32_t PaddingValue = 0x0;
 
   // Returns the size of the section in the output file.
   uintX_t getSize() const { return Header.sh_size; }
   void setSize(uintX_t Val) { Header.sh_size = Val; }
   uintX_t getFlags() { return Header.sh_flags; }
   uintX_t getFileOff() { return Header.sh_offset; }
   uintX_t getAlign() {
     // The ELF spec states that a value of 0 means the section has no alignment

ELF/OutputSections.cpp

 template <class ELFT>
 void OutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   auto *S = cast<InputSection<ELFT>>(C);
   Sections.push_back(S);
   S->OutSec = this;
   uint32_t Align = S->getAlign();
   this->updateAlign(Align);
 
-  uintX_t Off = this->Header.sh_size;
-  Off = alignTo(Off, Align);
+  uintX_t Off = alignTo(this->Header.sh_size, Align);
+  S->PadBehind = Off - this->Header.sh_size;
   S->OutSecOff = Off;
   Off += S->getSize();
   this->Header.sh_size = Off;
 }
 
 // If an input string is in the form of "foo.N" where N is a number,
 // return N. Otherwise, returns 65536, which is one greater than the
 // lowest priority.

ELF/Writer.cpp

for (SharedSymbol<ELFT> *C : Syms) {
     C->OffsetInBss = Off;
     Off += Sym.st_size;
   }
   Out<ELFT>::Bss->setSize(Off);
 }
 
 template <class ELFT>
 StringRef Writer<ELFT>::getOutputSectionName(InputSectionBase<ELFT> *S) const {
-  StringRef Dest = Script->getOutputSection<ELFT>(S);
+  StringRef Dest = Script->getOutSectionName<ELFT>(S);
   if (!Dest.empty())
     return Dest;
 
   StringRef Name = S->getSectionName();
   for (StringRef V : {".text.", ".rodata.", ".data.rel.ro.", ".data.", ".bss.",
                       ".init_array.", ".fini_array.", ".ctors.", ".dtors."})
     if (Name.startswith(V))
       return V.drop_back();
case InputSectionBase<ELFT>::EHFrame:
     break;
   case InputSectionBase<ELFT>::Merge:
     Sec = new MergeOutputSection<ELFT>(Key.Name, Key.Type, Key.Flags);
     break;
   case InputSectionBase<ELFT>::MipsReginfo:
     Sec = new MipsReginfoOutputSection<ELFT>();
     break;
   }
+
+  if (const OutSection *S = Script->getOutputSection(OutsecName))
+    Sec->PaddingValue = S->Padding;
+
   return {Sec, true};
 }
 
 template <class ELFT>
 OutputSectionBase<ELFT> *OutputSectionFactory<ELFT>::lookup(StringRef Name,
                                                             uint32_t Type,
                                                             uintX_t Flags) {
   return Map.lookup({Name, Type, Flags, 0});

test/ELF/linkerscript-sections-padding.s

+# REQUIRES: x86
+# RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
+
+## Check that padding value works:
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x11223344 }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: hexdump -C %t.out | FileCheck -check-prefix=YES %s
+# YES: 00000120  66 11 22 33 66
+
+## Confirming that address was correct:
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x55667788 }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: hexdump -C %t.out | FileCheck -check-prefix=YES2 %s
+# YES2: 00000120  66 55 66 77 66
+
+## Default padding value is 0x00000000
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } }" > %t.script
+# RUN: ld.lld -o %t.out --script %t.script %t
+# RUN: hexdump -C %t.out | FileCheck -check-prefix=NO %s
+# NO: 00000120  66 00 00 00 66
+
+.section        .mysec.1,"a"
+.align  4
+.byte   0x66
+
+.section        .mysec.2,"a"
+.align  4
+.byte   0x66
+
+.globl _start
+_start:
+ nop