[LinkerScript] Implement `MEMORY` command

[meadori]

Summary

Hi All,

This is a work in progress patch for implementing the MEMORY command as specified here:

• https://sourceware.org/binutils/docs/ld/MEMORY.html#MEMORY

There are two deviations from what is specified for GNU ld:

1. Only integer constants and *not* constant expressions are allowed in LENGTH and ORIGIN initializations.
2. The I and L attributes are *not* implemented.

With (1) there is currently no easy way to evaluate integer
only constant expressions. This can be enhanced in the
future.

With (2) it isn't clear how these flags map to the SHF_*
flags or if they even make sense for an ELF linker.

[ruiu]

This generally seems good. One thing I can say is it needs more comments to describe the code for the first-time readers.

[grimar]

Few comments.

ELF/LinkerScript.cpp

743

Should it be error instead ?

1988

You do not use AttrStr, so you can just use 'next()'.
May be worth to emit warning/error here about that attributes are not yet supported ?

2000

I think you do not need Tok:

if (!readInteger(next(), Origin))

2012

Same here.

ELF/LinkerScript.h

193

You do not need initialize Name I think, it is empty by default.

[grimar]

ELF/LinkerScript.cpp

1988

Ah you're still working on attributes, please ignore this comment then.

[meadori]

ELF/LinkerScript.cpp

743

I think so. Thanks.

2000

You're right. Will fix.

2012

Will fix.

[meadori]

1. Finished attribute implementation.

2. Added tests.

[ruiu]

ELF/LinkerScript.cpp

412

Comment.

523

Comment.

532

I don't think we are using `' to quote a word. I believe we write '' instead. (So please make it look similar to other code.)

541

We don't usually use auto in this context.

735–747

Revert this style change.

1990

Factor out the body of this if to a separate function which returns std::pair<uint32_t, uint32_t>.

ELF/LinkerScript.h

192

As I said in the previous comment, this needs a comment.

201

We do not write multiple definitions in one one like that. If in doubt, please look at other code and follow the convention.

232

Needs a comment.

[meadori]

ELF/LinkerScript.cpp

412

Will fix.

523

Will fix.

532

Will fix.

541

This is iterating a map, thus the direct declaration would be something gross like llvm::DenseMap<llvm::StringRef, MemoryRegion>::value_type. Personally, I think the auto is cleaner.

Also, there is precedence in the existing code with things like:

for (auto I = Cmd->Commands.begin(); I != E; ++I)
    process(**I);

735–747

Will fix.

1990

Will fix.

ELF/LinkerScript.h

192

Will fix.

201

Will fix.

232

Will fix.

[ruiu]

ELF/LinkerScript.cpp

541

Got it. Then can you use a temporary variable like this so that the type becomes obvious?

MemroyRegion &M = MR.second;

[meadori]

Address review feedback concerning code style and comments.

[grimar]

ELF/LinkerScript.cpp

2033

I would probably split this into separate function and rewrite to something like:

static uint32_t convertToFlags(char Attr) {
  if (Attr == 'w' || Attr == 'W')
    return SHF_WRITE;
  if (Attr == 'x' || Attr == 'X')
    return SHF_EXECINSTR;
  if (Attr == 'a' || Attr == 'A')
    return SHF_ALLOC;
  if (Attr != 'r' && Attr != 'R')
    setError("invalid memory region attribute: " + Attr);
return 0;
} 

std::pair<uint32_t, uint32_t> ScriptParser::readMemoryAttributes() {
  uint32_t Flags = 0;
  uint32_t NotFlags = 0;
  bool Invert = false;
  for (auto C : next()) {
    if (C == '!)
      Invert = !Invert;
    else if (Invert)
      NotFlags |= convertToFlags(C);
    else
      Flags |= convertToFlags(C);
  }
  return {Flags, NotFlags};
}

2056

Looks you do not really need that break.

[meadori]

ELF/LinkerScript.cpp

541

Sure, will do.

2033

I do find that more readable. Thanks.

2056

You are right. Thanks!

[meadori]

Address more style comments from review feedback.

[ruiu]

ELF/LinkerScript.cpp

419–422

You don't want to call error twice for one error. You can print out a multi-line error just by adding "\n" in middle of a message.

539–540

Do you need this? A nullptr will naturally be returned without this, I think.

547

Return &MR here and remove MatchingMemRegion

549

Why do you have to clear this?

2020

You can change this to

Opt.MemoryRegions[Name] = {Name, Origin, Length, Flags, NotFlags};

can't you?

2026

You can make this a static non-member function (which is generally preferred because it makes clear that the function does not depend on any class.)

ELF/LinkerScript.h

196

Instead of defining this constructor, can you set default values by adding = 0 to all these fields?

197–198

I think you can remove this constructor if you initialize a struct using {} as I mentioned below.

[meadori]

ELF/LinkerScript.cpp

419–422

I originally did that, but the formatting looks bad:

./bin/ld.lld: error: section '.data' will not fit in region 'ram'
region 'ram' overflowed by 3084 bytes

Personally I think the following is easier to understand:

./bin/ld.lld: error: section '.data' will not fit in region 'ram'
./bin/ld.lld: error: region 'ram' overflowed by 3084 bytes

539–540

A nullptr will be returned, but the error at the bottom of the function might be triggered as well. To avoid (1) executing nop-code on an empty region map and (2) to avoid hitting that error path I chose to do an early return.

547

Will fix.

549

I don't, that was a left over from a previous revision. Thank you for catching it.

2020

I can't b/c of reasons cited in previous comments.

2026

I can't call setError if I do that. I think it is better to just inline that code back into readMemoryAttributes.

ELF/LinkerScript.h

196

I can't b/c of the error I describe in the following comment. Since I can't remove the second constructor I have to have a default one (otherwise the compiler doesn't provide one for me).

197–198

That doesn't work. I get errors like:

error: no match for ‘operator=’ (operand types are ‘lld::elf::MemoryRegion’ and ‘<brace-enclosed initializer list>’)

[ruiu]

ELF/LinkerScript.cpp

419–422

Semantically I want to emit one error: for each error. I don't think this needs to be in two lines -- how about concatenating these messages with ": " instead of "\n"?

1996

You want to return from the function when you find an error in this function to prevent cascading error messages.

2045

s/auto/char/

ELF/LinkerScript.h

197–198

Sorry, the number of initializers did not match with the number of members. Does this work?

{Name, Origin, Length, Origin, Flags, NotFlags}

[meadori]

ELF/LinkerScript.cpp

419–422

That works. It looks like this now:

error: section '.data' will not fit in region 'ram': overflowed by 3084 bytes

ELF/LinkerScript.h

197–198

I accounted for that. It seems that in-class field initialization and braced initializer lists are not compatible:

$ c++ --version
c++ (Ubuntu 4.8.4-2ubuntu1~14.04.3) 4.8.4
Copyright (C) 2013 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

meadori@build1-trusty-cs:/scratch/meadori/llvm-mainline/obj/llvm$ cat -b test.cpp
     1  struct T {
     2    unsigned x = 0;
     3  };
     4  int main(void) {
     5    T t = {1};
     6    return 0;
     7  }
meadori@build1-trusty-cs:/scratch/meadori/llvm-mainline/obj/llvm$ c++ -std=c++11 test.cpp
test.cpp: In function ‘int main()’:
test.cpp:5:11: error: could not convert ‘{1}’ from ‘<brace-enclosed initializer list>’ to ‘T’
   T t = {1};
           ^

If I remove the in-class initializers, it works.

[ruiu]

ELF/LinkerScript.cpp

419–422

Looks nice.

ELF/LinkerScript.h

197–198

Sure. Then I think you can remove the C++11-style intializers. I think we don't need it.

[meadori]

1. Shorten overflow error message.
2. Get rid of MemoryRegion constructors.
3. A few more style changes.

[ruiu]

LGTM with a few nits.

Please verify that your new tests pass with BFD linker so that LLD's behavior is the same as BFD.

ELF/LinkerScript.cpp

539–540

Then can you move this piece of code to the beginning of this function to return earlier?

550

You can remove != 0 because any if (X) is equivalent to if ((X) != 0).

ELF/LinkerScript.h

199

I found that Index is a bit confusing. Maybe Offset?

[meadori]

I will fix the remaining nits and double-check with gold\ld. Thanks for all the review!

ELF/LinkerScript.cpp

550

Will fix.

ELF/LinkerScript.h

199

SGTM. I will change it.

ELF/LinkerScript.h

 #ifndef LLD_ELF_LINKER_SCRIPT_H
 #define LLD_ELF_LINKER_SCRIPT_H
 
 #include "Config.h"
 #include "Strings.h"
 #include "Writer.h"
 #include "lld/Core/LLVM.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <cstddef>
 #include <cstdint>
 #include <functional>
 #include <memory>
 #include <vector>
struct OutputSectionCommand : BaseCommand {
   Expr AlignExpr;
   Expr LMAExpr;
   Expr SubalignExpr;
   std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   uint32_t Filler = 0;
   ConstraintKind Constraint = ConstraintKind::NoConstraint;
   std::string Location;
+  std::string MemoryRegionName;
 };
 
 // This struct represents one section match pattern in SECTIONS() command.
 // It can optionally have negative match pattern for EXCLUDED_FILE command.
 // Also it may be surrounded with SORT() command, so contains sorting rules.
 struct SectionPattern {
   SectionPattern(StringMatcher &&Pat1, StringMatcher &&Pat2)
       : ExcludedFilePat(Pat1), SectionPat(Pat2) {}
struct PhdrsCommand {
   StringRef Name;
   unsigned Type;
   bool HasFilehdr;
   bool HasPhdrs;
   unsigned Flags;
   Expr LMAExpr;
 };
 
+struct MemoryRegion {
+  MemoryRegion() : Name(""), Origin(0), Length(0), Index(0) {}
+  MemoryRegion(StringRef N, uint64_t O, uint64_t L)
+      : Name(N), Origin(O), Length(L), Index(O) {}
+
+  std::string Name;
+  uint64_t Origin;
+  uint64_t Length;
+  uint64_t Index;
+};
+
 class LinkerScriptBase {
 protected:
   ~LinkerScriptBase() = default;
 
 public:
   virtual uint64_t getHeaderSize() = 0;
   virtual uint64_t getSymbolValue(const Twine &Loc, StringRef S) = 0;
   virtual bool isDefined(StringRef S) = 0;
struct ScriptConfiguration {
   // Used to assign sections to headers.
   std::vector<PhdrsCommand> PhdrsCommands;
 
   bool HasSections = false;
 
   // List of section patterns specified with KEEP commands. They will
   // be kept even if they are unused and --gc-sections is specified.
   std::vector<InputSectionDescription *> KeptSections;
+
+  llvm::DenseMap<llvm::StringRef, MemoryRegion> MemoryRegions;
 };
 
 extern ScriptConfiguration *ScriptConfig;
 
 // This is a runner of the linker script.
 template <class ELFT> class LinkerScript final : public LinkerScriptBase {
   typedef typename ELFT::uint uintX_t;
 
private:
   ScriptConfiguration &Opt = *ScriptConfig;
 
   std::vector<size_t> getPhdrIndices(StringRef SectionName);
   size_t getPhdrIndex(const Twine &Loc, StringRef PhdrName);
 
   uintX_t Dot;
   uintX_t LMAOffset = 0;
   OutputSectionBase *CurOutSec = nullptr;
+  MemoryRegion *CurMemRegion = nullptr;
   uintX_t ThreadBssOffset = 0;
   void switchTo(OutputSectionBase *Sec);
   void flush();
   void output(InputSection<ELFT> *Sec);
   void process(BaseCommand &Base);
   llvm::DenseSet<OutputSectionBase *> AlreadyOutputOS;
   llvm::DenseSet<InputSectionData *> AlreadyOutputIS;
 };

ELF/LinkerScript.cpp

template <class ELFT> void LinkerScript<ELFT>::output(InputSection<ELFT> *S) {
   S->OutSecOff = Pos - CurOutSec->Addr;
   Pos += S->getSize();
 
   // Update output section size after adding each section. This is so that
   // SIZEOF works correctly in the case below:
   // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
   CurOutSec->Size = Pos - CurOutSec->Addr;
 
+  if (CurMemRegion) {
+    CurMemRegion->Index += CurOutSec->Size;
+    uint64_t CurSize = CurMemRegion->Index - CurMemRegion->Origin;
+    if (CurSize > CurMemRegion->Length) {
+      uint64_t OverflowAmt = CurSize - CurMemRegion->Length;
+      error("a.out section `" + CurOutSec->Name + "' will not fit in region `" +
+            CurMemRegion->Name + "'");
+      error("region `" + CurMemRegion->Name + "' overflowed by " +
+            Twine(OverflowAmt) + " bytes");
+    }
+  }
+
   if (IsTbss)
     ThreadBssOffset = Pos - Dot;
   else
     Dot = Pos;
 }
 
 template <class ELFT> void LinkerScript<ELFT>::flush() {
   if (!CurOutSec || !AlreadyOutputOS.insert(CurOutSec).second)

 findSections(StringRef Name, const std::vector<OutputSectionBase *> &Sections) {
   std::vector<OutputSectionBase *> Ret;
   for (OutputSectionBase *Sec : Sections)
     if (Sec->getName() == Name)
       Ret.push_back(Sec);
   return Ret;
 }
 
 // This function assigns offsets to input sections and an output section
 // for a single sections command (e.g. ".text { *(.text); }").
 template <class ELFT>
 void LinkerScript<ELFT>::assignOffsets(OutputSectionCommand *Cmd) {
   if (Cmd->LMAExpr)
     LMAOffset = Cmd->LMAExpr(Dot) - Dot;
   std::vector<OutputSectionBase *> Sections =
       findSections<ELFT>(Cmd->Name, *OutputSections);
   if (Sections.empty())
     return;
   switchTo(Sections[0]);
 
   // Find the last section output location. We will output orphan sections
   // there so that end symbols point to the correct location.
   auto E = std::find_if(Cmd->Commands.rbegin(), Cmd->Commands.rend(),
                         [](const std::unique_ptr<BaseCommand> &Cmd) {
                           return !isa<SymbolAssignment>(*Cmd);
                         })
                .base();
   for (auto I = Cmd->Commands.begin(); I != E; ++I)
     process(**I);
   for (OutputSectionBase *Base : Sections)
     switchTo(Base);
   flush();
   std::for_each(E, Cmd->Commands.end(),
                 [this](std::unique_ptr<BaseCommand> &B) { process(*B.get()); });
 }
 
 template <class ELFT> void LinkerScript<ELFT>::removeEmptyCommands() {
   // It is common practice to use very generic linker scripts. So for any
   // given run some of the output sections in the script will be empty.
   // We could create corresponding empty output sections, but that would
   // clutter the output.
   // We instead remove trivially empty sections. The bfd linker seems even
   // more aggressive at removing them.
   auto Pos = std::remove_if(
for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     }
 
     if (auto *Cmd = dyn_cast<AssertCommand>(Base.get())) {
       Cmd->Expression(Dot);
       continue;
     }
 
     auto *Cmd = cast<OutputSectionCommand>(Base.get());
-    if (Cmd->AddrExpr)
+    if (Cmd->AddrExpr) {
       Dot = Cmd->AddrExpr(Dot);
+    } else if (!Cmd->MemoryRegionName.empty()) {
+      auto It = Opt.MemoryRegions.find(Cmd->MemoryRegionName);
+      if (It != Opt.MemoryRegions.end()) {
+        CurMemRegion = &It->second;
+        Dot = CurMemRegion->Index;
+      } else {
+        warn("memory region `" + Cmd->MemoryRegionName + "' not declared");
+      }
+    }
     assignOffsets(Cmd);
+    CurMemRegion = nullptr;
   }
 
   uintX_t MinVA = std::numeric_limits<uintX_t>::max();
   for (OutputSectionBase *Sec : *OutputSections) {
     if (Sec->Flags & SHF_ALLOC)
       MinVA = std::min<uint64_t>(MinVA, Sec->Addr);
     else
       Sec->Addr = 0;

 private:
   void addFile(StringRef Path);
 
   void readAsNeeded();
   void readEntry();
   void readExtern();
   void readGroup();
   void readInclude();
+  void readMemory();
   void readOutput();
   void readOutputArch();
   void readOutputFormat();
   void readPhdrs();
   void readSearchDir();
   void readSections();
   void readVersion();
   void readVersionScriptCommand();
while (!atEOF()) {
     } else if (Tok == "ENTRY") {
       readEntry();
     } else if (Tok == "EXTERN") {
       readExtern();
     } else if (Tok == "GROUP" || Tok == "INPUT") {
       readGroup();
     } else if (Tok == "INCLUDE") {
       readInclude();
+    } else if (Tok == "MEMORY") {
+      readMemory();
     } else if (Tok == "OUTPUT") {
       readOutput();
     } else if (Tok == "OUTPUT_ARCH") {
       readOutputArch();
     } else if (Tok == "OUTPUT_FORMAT") {
       readOutputFormat();
     } else if (Tok == "PHDRS") {
       readPhdrs();
while (!Error && !consume("}")) {
     } else if (Tok == "SORT") {
       readSort();
     } else if (peek() == "(") {
       Cmd->Commands.emplace_back(readInputSectionDescription(Tok));
     } else {
       setError("unknown command " + Tok);
     }
   }
+
+  if (consume(">"))
+    Cmd->MemoryRegionName = next();
+
   Cmd->Phdrs = readOutputSectionPhdrs();
 
   if (consume("="))
     Cmd->Filler = readOutputSectionFiller(next());
   else if (peek().startswith("="))
     Cmd->Filler = readOutputSectionFiller(next().drop_front());
 
   // Consume optional comma following output section command.
while (!Error && peek() != "}") {
     expect(";");
   }
 
   expect("}");
   expect(";");
   return Ret;
 }
 
+void ScriptParser::readMemory() {
+  // As specified in:
+  // https://sourceware.org/binutils/docs/ld/MEMORY.html#MEMORY
+
+  expect("{");
+  while (!Error && !consume("}")) {
+    StringRef Name = next();
+    if (consume("(")) {
+      StringRef AttrStr = next();
+      expect(")");
+    }
+    expect(":");
+
+    // `ORIGIN = <num>`.
+    if (!(consume("ORIGIN") || consume("org") || consume("o")))
+      setError("expected one of: ORIGIN, org, or o");
+    expect("=");
+    uint64_t Origin;
+    // TODO: Fully support constant expressions.
+    StringRef Tok = next();
+    if (!readInteger(Tok, Origin))
+      setError("nonconstant expression for origin");
+
+    expect(",");
+
+    // `LENGTH = <num>`.
+    if (!(consume("LENGTH") || consume("len") || consume("l")))
+      setError("expected one of: LENGTH, len, or l");
+    expect("=");
+    uint64_t Length;
+    Tok = next();
+    // TODO: Fully support constant expressions.
+    if (!readInteger(Tok, Length))
+      setError("nonconstant expression for length");
+
+    Opt.MemoryRegions[Name] = MemoryRegion(Name, Origin, Length);
+  }
+}
+
 void elf::readLinkerScript(MemoryBufferRef MB) {
   ScriptParser(MB).readLinkerScript();
 }
 
 void elf::readVersionScript(MemoryBufferRef MB) {
   ScriptParser(MB).readVersionScript();
 }
 
 void elf::readDynamicList(MemoryBufferRef MB) {
   ScriptParser(MB).readDynamicList();
 }
 
 template class elf::LinkerScript<ELF32LE>;
 template class elf::LinkerScript<ELF32BE>;
 template class elf::LinkerScript<ELF64LE>;
 template class elf::LinkerScript<ELF64BE>;