[ELF] - Linkerscript: implemented ALIGN modificatior of output sections.

[grimar]

Summary

Output section description can contain ALIGN modificator:
https://sourceware.org/binutils/docs/ld/Output-Section-Description.html#Output-Section-Description

Patch implements it.

[davide]

FWIW, this is very important because both FreeBSD and Linux rely on it (kernel).

[davide]

I think this one is OK. Please wait for Rui for final sign-off.

[ruiu]

ALIGN shouldn't be implemented as a special feature that is allowed only after ":" in SECTIONS subcommands. It is a generic function as described in https://sourceware.org/binutils/docs/ld/Builtin-Functions.html#Builtin-Functions.

If you support an expression after ":" in the context and the ALIGN built-in function, this feature is going to naturally be supported.

[grimar]

In D22674#493846, @ruiu wrote:

ALIGN shouldn't be implemented as a special feature that is allowed only after ":" in SECTIONS subcommands. It is a generic function as described in https://sourceware.org/binutils/docs/ld/Builtin-Functions.html#Builtin-Functions.

If you support an expression after ":" in the context and the ALIGN built-in function, this feature is going to naturally be supported.

I think we have different typese of ALIGN here. One is a output section description modificator.
3.6.1 Output Section Description explicitly says that ALIGN is a part of description.
(https://sourceware.org/binutils/docs/ld/Output-Section-Description.html#Output-Section-Description).
That is what this patch implements.

The other ALIGN is a generic function, as you mentioned.

I think location counter value in output secrion description is "global", but
in expressions inside declaration is "local" (relative to OutSec start address).
So ALIGN in declarations allows to use global location counter and layout the section
properly.

Because of above I think patch implements it in a correct way.

[grimar]

So, the full description of an output section looks like this:
(https://sourceware.org/binutils/docs/ld/Output-Section-Description.html#Output-Section-Description)

section [address] [(type)] :
  [AT(lma)]
  [ALIGN(section_align) | ALIGN_WITH_INPUT]
  [SUBALIGN(subsection_align)]
  [constraint]
  {
    output-section-command
    output-section-command
    ...
  } [>region] [AT>lma_region] [:phdr :phdr ...] [=fillexp] [,]

There are just a few things that can be between ":" and "{". One of them is ALIGN.
ALIGN also can be meet as regular command after "{", but it will have different meaning,
it will work with localcounter that is not absolete address, but offset from start of the section.
This way I think it is unnatural to treat everything between ":" and "{" as possible expression,
as the only possible expression is ALIGN. But that is not expression, but output section modificator.
So I believe logic of the patch is fine, I just plan to rebase it after recent changes soon.

[grimar]

• Rebased.

[ruiu]

Instead of adding new code to the function, can you create a new function that processes only ALIGN option?

ELF/LinkerScript.cpp

664–665

if (skip("ALIGN"))
  readAlign(Cmd);

[grimar]

• Rebased, addressed review comments.

[grimar]

In D22674#495326, @ruiu wrote:

Instead of adding new code to the function, can you create a new function that processes only ALIGN option?

I moved the handling to a assignAddresses() method, IMO more appropriate for that, and so handling is just 2 lines now.
I am not sure if moving to new function worth that now, when it is just 2 lines ? I guess no.
And the reason I moved it to assignAddresses() is that I found that location counter can be used in
ALIGN, like:
.aaa : ALIGN(4096 + . * 100) { ... }
Though I never saw this in real linkerscripts, it still looks as a more correct place, since we know the value
of location counter only in that place. What do you think ?

ELF/LinkerScript.cpp

664–665

Done.

[ruiu]

LGTM

[• Octav]

Does llvm ld support the ALIGN_WITH_INPUT option?

[MaskRay]

In D22674#1617615, @Octav wrote:

Does llvm ld support the ALIGN_WITH_INPUT option?

@Octav It doesn't. You can verify that the token "ALIGN_WITH_INPUT" is not mentioned in lld/ELF. What would be helpful is to give your minimized linker script which uses ALIGN_WITH_INPUT.

ELF/LinkerScript.h

 // and ONLY_IF_RW respectively.
 enum ConstraintKind { NoConstraint, ReadOnly, ReadWrite };
 
 struct OutputSectionCommand : BaseCommand {
   OutputSectionCommand(StringRef Name)
       : BaseCommand(OutputSectionKind), Name(Name) {}
   static bool classof(const BaseCommand *C);
   StringRef Name;
+  Expr AlignExpr;
   std::vector<std::unique_ptr<BaseCommand>> Commands;
   std::vector<StringRef> Phdrs;
   std::vector<uint8_t> Filler;
   ConstraintKind Constraint = NoConstraint;
 };
 
 struct InputSectionDescription : BaseCommand {
   InputSectionDescription() : BaseCommand(InputSectionKind) {}

ELF/LinkerScript.cpp

 LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
   typedef const std::unique_ptr<ObjectFile<ELFT>> ObjectFile;
   std::vector<OutputSectionBase<ELFT> *> Result;
   DenseSet<OutputSectionBase<ELFT> *> Removed;
 
   // Add input section to output section. If there is no output section yet,
   // then create it and add to output section list.
   auto AddInputSec = [&](InputSectionBase<ELFT> *C, StringRef Name,
-                         ConstraintKind Constraint) {
+                         ConstraintKind Constraint, uintX_t Align) {
     OutputSectionBase<ELFT> *Sec;
     bool IsNew;
     std::tie(Sec, IsNew) = Factory.create(C, Name);
-    if (IsNew)
+    if (IsNew) {
       Result.push_back(Sec);
+      Sec->updateAlignment(Align);
+    }
     if ((!(C->getSectionHdr()->sh_flags & SHF_WRITE)) &&
         Constraint == ReadWrite) {
       Removed.insert(Sec);
       return;
     }
     if ((C->getSectionHdr()->sh_flags & SHF_WRITE) && Constraint == ReadOnly) {
       Removed.insert(Sec);
       return;
for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     if (!OutCmd)
       continue;
 
     for (const std::unique_ptr<BaseCommand> &Cmd : OutCmd->Commands) {
       auto *InCmd = dyn_cast<InputSectionDescription>(Cmd.get());
       if (!InCmd)
         continue;
 
+      uint64_t Align = OutCmd->AlignExpr ? OutCmd->AlignExpr(Dot) : 0;
       for (ObjectFile &F : Symtab<ELFT>::X->getObjectFiles()) {
         for (InputSectionBase<ELFT> *S : F->getSections()) {
           if (isDiscarded(S) || S->OutSec)
             continue;
 
           if (match(S->getSectionName(), InCmd->Patterns)) {
             if (OutCmd->Name == "/DISCARD/")
               S->Live = false;
             else
-              AddInputSec(S, OutCmd->Name, OutCmd->Constraint);
+              AddInputSec(S, OutCmd->Name, OutCmd->Constraint, Align);
           }
         }
       }
     }
   }
 
   // Add all other input sections, which are not listed in script.
   for (ObjectFile &F : Symtab<ELFT>::X->getObjectFiles())
     for (InputSectionBase<ELFT> *S : F->getSections()) {
       if (!isDiscarded(S)) {
         if (!S->OutSec)
-          AddInputSec(S, getOutputSectionName(S), NoConstraint);
+          AddInputSec(S, getOutputSectionName(S), NoConstraint, 0);
       } else
         reportDiscarded(S, F);
     }
 
   // Remove from the output all the sections which did not met the constraints.
   Result.erase(std::remove_if(Result.begin(), Result.end(),
                               [&](OutputSectionBase<ELFT> *Sec) {
                                 return Removed.count(Sec);
private:
   void readSearchDir();
   void readSections();
 
   SymbolAssignment *readAssignment(StringRef Name);
   void readOutputSectionDescription(StringRef OutSec);
   std::vector<StringRef> readOutputSectionPhdrs();
   unsigned readPhdrType();
   void readProvide(bool Hidden);
+  void readAlign(OutputSectionCommand *Cmd);
 
   Expr readExpr();
   Expr readExpr1(Expr Lhs, int MinPrec);
   Expr readPrimary();
   Expr readTernary(Expr Cond);
   Expr combine(StringRef Op, Expr Lhs, Expr Rhs);
 
   const static StringMap<Handler> Cmd;
return StringSwitch<int>(Op)
       .Case(">=", 2)
       .Case("<=", 2)
       .Case("==", 2)
       .Case("!=", 2)
       .Case("&", 1)
       .Default(-1);
 }
 
+void ScriptParser::readAlign(OutputSectionCommand *Cmd) {
+  expect("ALIGN");
+  expect("(");
+  Cmd->AlignExpr = readExpr();
+  expect(")");
+}
+
 void ScriptParser::readOutputSectionDescription(StringRef OutSec) {
   OutputSectionCommand *Cmd = new OutputSectionCommand(OutSec);
   Opt.Commands.emplace_back(Cmd);
   expect(":");
 
+  if (peek() == "ALIGN")
+    readAlign(Cmd);
+
   // Parse constraints.
   if (skip("ONLY_IF_RO"))
     Cmd->Constraint = ReadOnly;
   if (skip("ONLY_IF_RW"))
     Cmd->Constraint = ReadWrite;
   expect("{");
 
   while (!Error && !skip("}")) {

test/ELF/linkerscript/linkerscript-align.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
+## Check that ALIGN command workable using location counter
 # RUN: echo "SECTIONS { \
 # RUN:  . = 0x10000; \
 # RUN:  .aaa : \
 # RUN:  { \
 # RUN:   *(.aaa) \
 # RUN:  } \
 # RUN:  . = ALIGN(4096); \
 # RUN:  .bbb : \

 # RUN: llvm-objdump -section-headers %t1 | FileCheck %s
 # CHECK:      Sections:
 # CHECK-NEXT: Idx Name          Size      Address          Type
 # CHECK-NEXT:   0               00000000 0000000000000000
 # CHECK-NEXT:   1 .aaa          00000008 0000000000010000 DATA
 # CHECK-NEXT:   2 .bbb          00000008 0000000000011000 DATA
 # CHECK-NEXT:   3 .ccc          00000008 0000000000014000 DATA
 
+## Check output sections ALIGN modificator
+# RUN: echo "SECTIONS { \
+# RUN:  . = 0x10000; \
+# RUN:  .aaa : \
+# RUN:  { \
+# RUN:   *(.aaa) \
+# RUN:  } \
+# RUN:  .bbb : ALIGN(4096) \
+# RUN:  { \
+# RUN:   *(.bbb) \
+# RUN:  } \
+# RUN:  .ccc : ALIGN(4096 * 4) \
+# RUN:  { \
+# RUN:   *(.ccc) \
+# RUN:  } \
+# RUN: }" > %t2.script
+# RUN: ld.lld -o %t2 --script %t2.script %t
+# RUN: llvm-objdump -section-headers %t1 | FileCheck %s
+
 .global _start
 _start:
  nop
 
 .section .aaa, "a"
 .quad 0
 
 .section .bbb, "a"
 .quad 0
 
 .section .ccc, "a"
 .quad 0