[ELF] --oformat=binary: use LMA to compute file offsets

[MaskRay]

Summary

--oformat=binary is rare (used in a few places in FreeBSD, see stand/i386/mbr/Makefile LDFLAGS_BIN)
The result should be identical to a normal output transformed by objcopy -O binary.

The current implementation ignores addresses and lays out sections by
respecting output section alignments. It can fail when an output section
address is specified, e.g. .rodata ALIGN(16) : (PR33651).

Fix PR33651 by respecting LMA. The code is similar to
tools/llvm-objcop/ELF/Object.cpp BinaryWriter::finalize after D71035 and D79229.
Unforunately for an output section without PT_LOAD, we assume its LMA is equal
to its VMA. So the result is still incorrect when an output section LMA
(AT(...)) is specified

Also drop alignTo(off, config->wordsize). GNU ld does not round up the file size.

[grimar]

There is a GNU ld bug about --oformat=binary "Linking with --oformat=binary discards non-static global variables" (https://sourceware.org/bugzilla/show_bug.cgi?id=12524).
The last 2 comments are saying:

1. "ld --oformat is a misfeature. Don't use it. As you have found, it doesn't work except for the simplest of object files, and only then on a very limited set of targets. You are much better off linking to your usual target, then converting the file with objcopy.",
2. "I only added support for --oformat=binary to gold because the Linux kernel build uses it.".

So I am not sure that we want to add more complication for the existent logic of --oformat binary implemented in LLD?

[MaskRay]

In D85086#2190130, @grimar wrote:

There is a GNU ld bug about --oformat=binary "Linking with --oformat=binary discards non-static global variables" (https://sourceware.org/bugzilla/show_bug.cgi?id=12524).
The last 2 comments are saying:

1. "ld --oformat is a misfeature. Don't use it. As you have found, it doesn't work except for the simplest of object files, and only then on a very limited set of targets. You are much better off linking to your usual target, then converting the file with objcopy.",
2. "I only added support for --oformat=binary to gold because the Linux kernel build uses it.".

So I am not sure that we want to add more complication for the existent logic of --oformat binary implemented in LLD?

I think the complexity is acceptable: 7 lines of code + 2 lines of comments + 1 blank line. For a misfeature, we either not implement it, approximate it, or fully implement it, but should not leave it in a known broken state if a reasonable fix is available. For this case I consider we have a perfect emulation. We cannot simply drop the feature because there are still use cases (in latest Linux kernel it appears to only exist in documentation; in FreeBSD it is still used).

I also question Alan's conclusion that "--oformat=binary is a misfeature". We can say it is redundant, because "objcopy -O binary" performs the task, but I can't find evidence that this feature was misdesigned. It was possible that the feature cannot be reasonable implemented on other binary formats, so Alan called it a misfeature, but for ELF --oformat=binary should be good.

[jhenderson]

FWIW, I don't really agree that --oformat=binary is necessarily a misfeature in a linker - it saves the extra objcopy step to produce binary output, and the logic in the linker should be much simpler, since the linker already knows everything about the program layout, without having to come up with complicated heuristics to figure out what to do in some edge cases (e.g. what to do with empty sections on segment edges). That being said, I don't have any use-case in my area, so I don't really care whether it is implemented or not.

lld/ELF/Writer.cpp

2561

laided -> laid

[psmith]

I agree with MaskRay that if we do support the feature then we should make sure it works or document its limitations, even if our limitations are "Implemented to the degree that it supports the FreeBSD Kernel, we recommend producing an ELF file and using llvm-objcopy --output-target=binary."

FWIW the modifications here look like an improvement and are localised to a small error so no objections from me for the improvement. I'm surprised to see we don't generate Program Headers for oformat binary. I would expect us to generate but not allocate addresses or write out the ELF header or program headers to the file. I think this would be the equivalent of writing an ELF file then using objcopy on it.

[MaskRay]

Fix a typo

[grimar]

OK. I have no more objections about this then. Happy if others are happy.

lld/ELF/Writer.cpp

2567

Consider setting the offset field just once and deduplicating the
sec->type != SHT_NOBITS && (sec->flags & SHF_ALLOC) && sec->size > 0 condition:

E.g.

auto needsOffset = [](OutputSection &sec) {
  return sec.type != SHT_NOBITS && (sec.flags & SHF_ALLOC) && sec.size > 0;
};

uint64_t minAddr = UINT64_MAX;
for (OutputSection *sec : outputSections)
  if (needsOffset(*sec))
    minAddr = std::min(minAddr, sec->getLMA());

fileSize = 0;
for (OutputSection *sec : outputSections)
  if (needsOffset(*sec)) {
    sec->offset = sec->getLMA() - minAddr;
    fileSize = std::max(fileSize, sec->offset + sec->size);
  }

Or

uint64_t minAddr = UINT64_MAX;
std::vector<OutputSection *> sections;
for (OutputSection *sec : outputSections) {
  if (sec.type = SHT_NOBITS && (sec.flags & SHF_ALLOC) && sec.size > 0) {
    minAddr = std::min(minAddr, sec->getLMA());
    sections.push_back(sec);
  }
}

fileSize = 0;
for (OutputSection *sec : sections) {
  sec->offset = sec->getLMA() - minAddr;
  fileSize = std::max(fileSize, sec->offset + sec->size);
}

[psmith]

No objections from me either. I guess LGTM if George's last comment can be resolved.

[MaskRay]

Add lambda needsOffset

lld/ELF/Writer.cpp

static uint64_t setFileOffset(OutputSection *os, uint64_t off) {
   os->offset = off;
 
   if (os->type == SHT_NOBITS)
     return off;
   return off + os->size;
 }
 
 template <class ELFT> void Writer<ELFT>::assignFileOffsetsBinary() {
-  uint64_t off = 0;
+  // Compute the minimum LMA of all non-empty non-NOBITS sections as minAddr.
+  auto needsOffset = [](OutputSection &sec) {
+    return sec.type != SHT_NOBITS && (sec.flags & SHF_ALLOC) && sec.size > 0;
+  };
+  uint64_t minAddr = UINT64_MAX;
   for (OutputSection *sec : outputSections)
-    if (sec->flags & SHF_ALLOC)
-      off = setFileOffset(sec, off);
-  fileSize = alignTo(off, config->wordsize);
+    if (needsOffset(*sec)) {
+      sec->offset = sec->getLMA();
+      minAddr = std::min(minAddr, sec->offset);
+    }
+
+  // Sections are laid out at LMA minus minAddr.
+  fileSize = 0;
+  for (OutputSection *sec : outputSections)
+    if (needsOffset(*sec)) {
+      sec->offset -= minAddr;
+      fileSize = std::max(fileSize, sec->offset + sec->size);
+    }
 }
 
 static std::string rangeToString(uint64_t addr, uint64_t len) {
   return "[0x" + utohexstr(addr) + ", 0x" + utohexstr(addr + len - 1) + "]";
 }
 
 // Assign file offsets to output sections.
 template <class ELFT> void Writer<ELFT>::assignFileOffsets() {

lld/test/ELF/oformat-binary-ttext.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
 # RUN: ld.lld -N -Ttext 0x100 -o %t.out %t --oformat binary
 # RUN: od -t x1 -v %t.out | FileCheck %s --check-prefix=BIN
 
-# BIN:      0000000 90 00 00 00 00 00 00 00
-# BIN-NEXT: 0000010
-# BIN-NOT:  0000020
+# BIN:      0000000 90
+# BIN-NEXT: 0000001
 
 ## The same but without OMAGIC.
 # RUN: ld.lld -Ttext 0x100 -o %t.out %t --oformat binary
 # RUN: od -t x1 -v %t.out | FileCheck %s --check-prefix=BIN
 
 .text
 .globl _start
 _start:
  nop

lld/test/ELF/oformat-binary.s

 # REQUIRES: x86
 # RUN: llvm-mc -filetype=obj -triple=x86_64-unknown-linux %s -o %t
 
 # RUN: ld.lld -o %t.out %t --oformat binary
 # RUN: od -t x1 -v %t.out | FileCheck %s
-# CHECK: 000000 90 11 22 00 00 00 00 00
-# CHECK-NOT: 00000010
+# CHECK:      0000000 90 11 22
+# CHECK-NEXT: 0000003
 
 ## Check case when linkerscript is used.
 # RUN: echo "SECTIONS { . = 0x1000; }" > %t.script
 # RUN: ld.lld -o %t2.out --script %t.script %t --oformat binary
 # RUN: od -t x1 -v %t2.out | FileCheck %s
 
 # RUN: echo "SECTIONS { }" > %t.script
 # RUN: ld.lld -o %t2.out --script %t.script %t --oformat binary
 # RUN: od -t x1 -v %t2.out | FileCheck %s
 
+## LMA(.text)=0x100, LMA(.mysec)=0x108. The minimum LMA of all non-empty sections is 0x100.
+## We place an output section at its LMA minus 0x100.
+# RUN: echo 'SECTIONS { .text 0x100 : {*(.text)} .mysec ALIGN(8) : {*(.mysec*)} }' > %talign.lds
+# RUN: ld.lld -T %talign.lds %t --oformat binary -o %talign
+# RUN: od -Ax -t x1 %talign | FileCheck %s --check-prefix=ALIGN --ignore-case
+
+# ALIGN:      000000 90 00 00 00 00 00 00 00 11 22
+# ALIGN-NEXT: 00000a
+
+## The empty section .data is ignored when computing the file size.
+# RUN: echo 'SECTIONS { .text : {*(.text .mysec*)} .data 0x100 : {keep = .;}}' > %tempty.lds
+# RUN: ld.lld -T %tempty.lds %t --oformat binary -o %tempty
+# RUN: od -t x1 %tempty | FileCheck %s
+
+## NOBITS sections are ignored as well.
+# RUN: echo 'SECTIONS { .text : {*(.text .mysec*)} .data 0x100 (NOLOAD) : {BYTE(0)}}' > %tnobits.lds
+# RUN: ld.lld -T %tnobits.lds %t --oformat binary -o %tnobits
+# RUN: od -t x1 %tnobits | FileCheck %s
+
+## FIXME .mysec should be placed at file offset 1.
+## This does not work because for a section without PT_LOAD, we consider LMA = VMA.
+# RUN: echo 'SECTIONS { .text : {*(.text)} .mysec 0x8 : AT(1) {*(.mysec*)} }' > %tlma.lds
+# RUN: ld.lld -T %tlma.lds %t --oformat binary -o %tlma
+# RUN: od -Ax -t x1 %tlma | FileCheck %s --check-prefix=ALIGN --ignore-case
+
 # RUN: not ld.lld -o /dev/null %t --oformat foo 2>&1 \
 # RUN:   | FileCheck %s --check-prefix ERR
 # ERR: unknown --oformat value: foo
 
 # RUN: ld.lld -o /dev/null %t --oformat elf
 # RUN: ld.lld -o /dev/null %t --oformat elf-foo
 
 .text