[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 ↗

(On Diff #47993)

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 ↗

(On Diff #47993)

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 ↗

(On Diff #47993)

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 ↗

(On Diff #47993)

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

444–451

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

ELF/LinkerScript.h

45

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

45

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

45

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

63–66

Why don't you just do

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

?

69–70

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; });

462–469

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

69–70

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

69–70

This new code with lambdas looks good to me.

417

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

419

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

423

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

460–461

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

[grimar]

• Addressed review comments

ELF/LinkerScript.cpp

417

Done.

419

Removed.

423

Done.

460–461

Removed check.

[ruiu]

LGTM

ELF/LinkerScript.cpp

61

return{} -> return {}

453

This is not safe because Tok may be empty.

if (Tok.startswith("="))

[grimar]

ELF/LinkerScript.cpp

453

Done.

[grimar]

ELF/LinkerScript.cpp

61

Done.

[grimar]

r262020

ELF/LinkerScript.h

public:
 
   // KEEP command saves unused sections even if --gc-sections is specified.
   bool Keep = false;
 
 private:
   StringRef SectionPattern;
 };
 
+struct OutSection {
+  StringRef Name;
+  std::vector<uint8_t> Filler;
+};
+
 // 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);
+  ArrayRef<uint8_t> getFiller(StringRef Name);
   template <class ELFT> bool isDiscarded(InputSectionBase<ELFT> *S);
   template <class ELFT> bool shouldKeep(InputSectionBase<ELFT> *S);
   int compareSections(StringRef A, StringRef B);
 
 private:
   template <class ELFT> SectionRule *find(InputSectionBase<ELFT> *S);
 
   // 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

bool LinkerScript::isDiscarded(InputSectionBase<ELFT> *S) {
   return getOutputSection(S) == "/DISCARD/";
 }
 
 template <class ELFT> bool LinkerScript::shouldKeep(InputSectionBase<ELFT> *S) {
   SectionRule *R = find(S);
   return R && R->Keep;
 }
 
+ArrayRef<uint8_t> LinkerScript::getFiller(StringRef Name) {
+  for (OutSection &C : OutSections)
+    if (C.Name == Name)
+      return C.Filler;
+  return{};
+}
+
 // 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,
+                        [&](OutSection &C) { return C.Name == A; });
+  auto J = std::find_if(OutSections.begin(), E,
+                        [&](OutSection &C) { return C.Name == B; });
   if (I == E || J == E)
     return 0;
   return I < J ? -1 : 1;
 }
 
 // Returns true if S matches T. S can contain glob meta-characters.
 // The asterisk ('*') matches zero or more characacters, and the question
 // mark ('?') matches one character.
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();
   void readGroup();
   void readInclude();
   void readNothing() {}
   void readOutput();
   void readOutputArch();
   void readOutputFormat();
   void readSearchDir();
   void readSections();
 
   void readOutputSectionDescription();
   void readSectionPatterns(StringRef OutSec, bool Keep);
 
+  std::vector<uint8_t> readHex(StringRef S);
+
   StringSaver Saver;
   std::vector<StringRef> Tokens;
   const static StringMap<Handler> Cmd;
   size_t Pos = 0;
   bool IsUnderSysroot;
   bool Error = false;
 };
 
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::readSectionPatterns(StringRef OutSec, bool Keep) {
   expect("(");
   while (!Error && !skip(")"))
     Script->Sections.emplace_back(OutSec, next(), Keep);
 }
 
+std::vector<uint8_t> ScriptParser::readHex(StringRef S) {
+  std::vector<uint8_t> Hex;
+  Hex.reserve((S.size() + 1) / 2);
+
+  while (!S.empty()) {
+    StringRef B = S.substr(0, 2);
+    S = S.slice(2, S.size());
+    uint8_t H;
+    if (B.getAsInteger(16, H)) {
+      setError("Not a HEX value: " + B);
+      return {};
+    }
+    Hex.push_back(H);
+  }
+  return Hex;
+}
+
 void ScriptParser::readOutputSectionDescription() {
-  StringRef OutSec = next();
-  Script->SectionOrder.push_back(OutSec);
+  OutSection OutSec;
+  OutSec.Name = next();
   expect(":");
   expect("{");
   while (!Error && !skip("}")) {
     StringRef Tok = next();
     if (Tok == "*") {
-      readSectionPatterns(OutSec, false);
+      readSectionPatterns(OutSec.Name, false);
     } else if (Tok == "KEEP") {
       expect("(");
       next(); // Skip *
-      readSectionPatterns(OutSec, true);
+      readSectionPatterns(OutSec.Name, true);
       expect(")");
     } else {
       setError("Unknown command " + Tok);
     }
   }
+  StringRef Tok = peek();
+  if (Tok[0] == '=') {
+    if (!Tok.startswith("=0x")) {
+      setError("Filler should be a HEX value");
+      return;
+    }
+    Tok = Tok.substr(3); // Skip '=0x'
+    OutSec.Filler = readHex(Tok);
+    if (Error)
+      return;
+    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) {

ELF/OutputSections.cpp

 //===- OutputSections.cpp -------------------------------------------------===//
 //
 //                             The LLVM Linker
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "OutputSections.h"
 #include "Config.h"
+#include "LinkerScript.h"
 #include "SymbolTable.h"
 #include "Target.h"
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/MathExtras.h"
 #include <map>
 
 using namespace llvm;
 using namespace llvm::dwarf;
if (!Config->Shared)
     return false;
   if (Body->getVisibility() != STV_DEFAULT)
     return false;
   if (Config->Bsymbolic || (Config->BsymbolicFunctions && Body->isFunc()))
     return false;
   return true;
 }
 
+static void fill(uint8_t *Buf, size_t Size, ArrayRef<uint8_t> A) {
+  size_t I = 0;
+  for (; I + A.size() < 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);
 }
 
 template <class ELFT>
 EHOutputSection<ELFT>::EHOutputSection(StringRef Name, uint32_t Type,
                                        uintX_t Flags)
     : OutputSectionBase<ELFT>(Name, Type, Flags) {

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*) } =0x112233445566778899 }" > %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 22 33 44 55 66 77 88 99 11 22 33 44 55 66 77
+
+## Confirming that address was correct:
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x998877665544332211 }" > %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 88 77 66 55 44 33 22 11 99 88 77 66 55 44
+
+## Default padding value is 0x00:
+# 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 00 00 00 00 00 00 00 00 00 00 00 00
+
+## Filler should be a hex value (1):
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =99 }" > %t.script
+# RUN: not ld.lld -o %t.out --script %t.script %t 2>&1 \
+# RUN:   | FileCheck --check-prefix=ERR %s
+# ERR: Filler should be a HEX value
+
+## Filler should be a hex value (2):
+# RUN: echo "SECTIONS { .mysec : { *(.mysec*) } =0x99XX }" > %t.script
+# RUN: not ld.lld -o %t.out --script %t.script %t 2>&1 \
+# RUN:   | FileCheck --check-prefix=ERR2 %s
+# ERR2: Not a HEX value: XX
+
+.section        .mysec.1,"a"
+.align  16
+.byte   0x66
+
+.section        .mysec.2,"a"
+.align  16
+.byte   0x66
+
+.globl _start
+_start:
+ nop