[llvm-objcopy][ELF] -O binary: use LMA instead of sh_offset to decide where to write section contents

[MaskRay]

Summary

.text sh_address=0x1000 sh_offset=0x1000
.data sh_address=0x3000 sh_offset=0x2000

In an objcopy -O binary output, the distance between two sections equal
their LMA differences (0x3000-0x1000), instead of their sh_offset
differences (0x2000-0x1000). This patch changes our behavior to match
GNU.

This rule gets more complex when the containing PT_LOAD has
p_vaddr!=p_paddr. GNU objcopy essentially computes
sh_offset-p_offset+p_paddr for each candidate section, and removes the
gap before the first address.

Added two tests to binary-paddr.test to catch the compatibility problem.

[MaskRay]

Delete unneeded parts of the test

[jhenderson]

I'd like to do some experiments with GNU objcopy on this subject before reviewing, but my Linux machine is unavailable until some time next week, so I'm going to have to wait until then. Sorry!

[MaskRay]

No hurry! We have an objcopy -I ihex -O binary user. I noticed the difference (when the difference between sh_address'es does not equal the difference between sh_offset's) while migrating them to use llvm-objcopy. They have switched to a checked-in binary instead as using objcopy does not make their build any better (the original ihex is an opaque binary anyway). I posted the patch because it actually seems to simplify code and may probably address problems of future users.

[jhenderson]

I've been playing around with the YAML from the test to experiment with other situations using GNU objcopy, and I'm not convinced that your statement about the algorithm is quite accurate, and indeed I see behaviour differences between GNU objcopy and llvm-objcopy with this patch. Unfortunately, I haven't been able to figure out what the actual algorithm is, so it's possible I'm just misunderstanding something. Here is an example I used:

Input:

--- !ELF
FileHeader:
  Class:           ELFCLASS64
  Data:            ELFDATA2LSB
  Type:            ET_EXEC
  Machine:         EM_X86_64
Sections:
  - Name:            .text
    Type:            SHT_PROGBITS
    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
    Address:         0x1000
    AddressAlign:    0x0000000000001000
    Content:         "c3c3c3c3"
  - Name:            .data
    Type:            SHT_PROGBITS
    Flags:           [ SHF_ALLOC ]
    Address:         0x3000
    AddressAlign:    0x0000000000001000
    Content:         "3232"
  - Name: .baz
    Type: SHT_PROGBITS
    Size: 0x2000
ProgramHeaders:
  - Type: PT_LOAD
    Flags: [ PF_R, PF_W ]
    VAddr: 0x2000
    PAddr: 0x4000
    FileSize: 0x1800
    MemSize: 0x1800
    Sections:
      - Section: .data

GNU objcopy output:

000000 c3c3 c3c3 0000 0000 0000 0000 0000 0000
000010 0000 0000 0000 0000 0000 0000 0000 0000
*
003000 3232
003002

llvm-objcopy output:

000000 c3c3 c3c3 0000 0000 0000 0000 0000 0000
000010 0000 0000 0000 0000 0000 0000 0000 0000
*
004000 3232
004002

I also noticed several differences that may be unrelated to this issue when sections are not in segments. Speaking of which, did you mean for this to be the case for .text in this test?

[MaskRay]

Fix formula: sh_offset - p_offset + p_paddr

See bfd/elf.c:1182 for a reference.

/* We used to use the same adjustment for SEC_LOAD

	   sections, but that doesn't work if the segment
	   is packed with code from multiple VMAs.
	   Instead we calculate the section LMA based on
	   the segment LMA.  It is assumed that the
	   segment will contain sections with contiguous
	   LMAs, even if the VMAs are not.  */

newsect->lma = (phdr->p_paddr + hdr->sh_offset - phdr->p_offset);

For sections not in a PT_LOAD, the BFD code uses a different formula.

		newsect->lma = (phdr->p_paddr
				+ hdr->sh_addr - phdr->p_vaddr);

We don't need care about that because -O binary does not dump non-SHF_ALLOC sections.

[jhenderson]

llvm/test/tools/llvm-objcopy/ELF/binary-paddr.test

25

This section isn't n a segment. Is that deliberate? If so, it probably needs a comment saying this.

34

Does this comment still make sense? The numbers don't line up with the p_vaddr below, and the comment along with it (Also sh_address -> sh_addr).

111

Same comment as above: is this section deliberately not in a segment?

Assuming it is, there may be scope for a test where both sections are in segments.

llvm/tools/llvm-objcopy/ELF/Object.cpp

2257

The minimum LMA of what? Please specify that in the comment.

[MaskRay]

Fix tests.

In GNU objcopy, LMA = sh_offset-p_offset+p_paddr for a section contained in a PT_LOAD.

The rules that llvm-objcopy and GNU objcopy use to decide whether a section is contained in a PT_LOAD are different.
We use sh_offset for non-SHT_NOBITS sections, but GNU objcopy appears to use sh_addr (see readelf -l output)
So some properties (VAddr: 0x20000) can cause different behaviors, but we probably don't bother testing that because "VAddr != sh_addr of the first section" is unrealistic.

Changed the tests to have same behaviors with llvm-objcopy and GNU objcopy.

[MaskRay]

Improve a comment.

[MaskRay]

llvm/test/tools/llvm-objcopy/ELF/binary-paddr.test

34

Changed to:

1. The computed LMA is sh_offset-p_offset+p_paddr = 0x2000-0x2000+0x4000 = 0x4000.

[jhenderson]

LGTM, but it would probably be wise to get a second pair of eyes on this change.

[MaskRay]

Is it ok for me to commit if there is still no other people interested in this patch for, say, 10 hours? 😂

I tested it on an internal objcopy -I ihex -O binary use case that motivated me to send the patch. With this patch, the section content layout is now the same.

[jhenderson]

In D71035#1783026, @MaskRay wrote:

Is it ok for me to commit if there is still no other people interested in this patch for, say, 10 hours? 😂

I tested it on an internal objcopy -I ihex -O binary use case that motivated me to send the patch. With this patch, the section content layout is now the same.

Let's give it until after the weekend. We've been stung on a few occasions by issues with binary output, so I want to give people ample opportunity to point out anything else we've missed!

[rupprecht]

In D71035#1783196, @jhenderson wrote:

In D71035#1783026, @MaskRay wrote:

Is it ok for me to commit if there is still no other people interested in this patch for, say, 10 hours? 😂

I tested it on an internal objcopy -I ihex -O binary use case that motivated me to send the patch. With this patch, the section content layout is now the same.

Let's give it until after the weekend. We've been stung on a few occasions by issues with binary output, so I want to give people ample opportunity to point out anything else we've missed!

+1 to just committing after the weekend. Since you mentiond ihex, adding Eugene who implemented the reading/writing so might have something to say about the patch, although it looks like this the ihex patches didn't touch binary output.

Do you have a reduced ihex test case to add too?

I'll watch out for other failures internally post-commit.

[MaskRay]

In D71035#1783958, @rupprecht wrote:

In D71035#1783196, @jhenderson wrote:

In D71035#1783026, @MaskRay wrote:

Is it ok for me to commit if there is still no other people interested in this patch for, say, 10 hours? 😂

I tested it on an internal objcopy -I ihex -O binary use case that motivated me to send the patch. With this patch, the section content layout is now the same.

Let's give it until after the weekend. We've been stung on a few occasions by issues with binary output, so I want to give people ample opportunity to point out anything else we've missed!

+1 to just committing after the weekend. Since you mentiond ihex, adding Eugene who implemented the reading/writing so might have something to say about the patch, although it looks like this the ihex patches didn't touch binary output.

Do you have a reduced ihex test case to add too?

I'll watch out for other failures internally post-commit.

ihex is not directly related the the -O binary issue. It just makes it easy to craft an ELF with (sec2.sh_addr-sec1.sh_addr != sec2.sh_offset-sec1.sh_offset), which may not easy with a linker.

Address can be specified

// ':' + Length + Address + Type + Checksum with empty data ':LLAAAATTCC'

OK, I'll commit after the weekend.

[MaskRay]

Fix tests. Verified all 3 output files are identical to GNU objcopy's

llvm/test/tools/llvm-objcopy/ELF/binary-paddr.test

-# RUN: yaml2obj %s -o %t
-# RUN: llvm-objcopy -O binary %t %t2
-# RUN: od -t x2 %t2 | FileCheck %s --ignore-case
-# RUN: wc -c < %t2 | FileCheck %s --check-prefix=SIZE
+## The computed LMA of a section in a PT_LOAD equals sh_offset-p_offset+p_paddr.
+## The byte offset difference between two sections equals the difference between their LMAs.
 
-!ELF
+## Corollary: if two sections are in the same PT_LOAD, the byte offset
+## difference equals the difference between their sh_addr fields.
+
+# RUN: yaml2obj --docnum=1 %s -o %t1
+# RUN: llvm-objcopy -O binary %t1 %t1.out
+# RUN: od -A x -t x2 %t1.out | FileCheck %s --check-prefix=CHECK1 --ignore-case
+# RUN: wc -c %t1.out | FileCheck %s --check-prefix=SIZE1
+
+# CHECK1:      000000 c3c3 c3c3 0000 0000 0000 0000 0000 0000
+# CHECK1-NEXT: 000010 0000 0000 0000 0000 0000 0000 0000 0000
+# CHECK1-NEXT: *
+# CHECK1-NEXT: 001000 3232
+# SIZE1:       4098
+
+--- !ELF
 FileHeader:
   Class:           ELFCLASS64
   Data:            ELFDATA2LSB
   Type:            ET_EXEC
   Machine:         EM_X86_64
 Sections:
   - Name:            .text
     Type:            SHT_PROGBITS
     Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
     Address:         0x1000
-    AddressAlign:    0x0000000000001000
+    AddressAlign:    0x1000
     Content:         "c3c3c3c3"
   - Name:            .data
     Type:            SHT_PROGBITS
-    Flags:           [ SHF_ALLOC ]
+    Flags:           [ SHF_ALLOC, SHF_WRITE ]
     Address:         0x2000
-    AddressAlign:    0x0000000000001000
+    AddressAlign:    0x1000
     Content:         "3232"
 ProgramHeaders:
   - Type: PT_LOAD
-    Flags: [ PF_X, PF_R ]
-    VAddr: 0x1000
-    PAddr: 0x1000
-    Align: 0x1000
+    Flags: [ PF_R, PF_W ]
     Sections:
       - Section: .text
+      - Section: .data
+
+## The computed LMA of a section not in a PT_LOAD equals its sh_addr.
+
+# RUN: yaml2obj --docnum=2 %s -o %t2
+# RUN: llvm-objcopy -O binary %t2 %t2.out
+# RUN: od -A x -t x2 %t2.out | FileCheck %s --check-prefix=CHECK2 --ignore-case
+# RUN: wc -c %t2.out | FileCheck %s --check-prefix=SIZE2
+
+## The computed LMA of .data is 0x4000. The minimum LMA of all sections is 0x1000.
+## The content of .data will be written at 0x4000-0x1000 = 0x3000.
+# CHECK2:      000000 c3c3 c3c3 0000 0000 0000 0000 0000 0000
+# CHECK2-NEXT: 000010 0000 0000 0000 0000 0000 0000 0000 0000
+# CHECK2-NEXT: *
+# CHECK2-NEXT: 003000 3232
+# SIZE2:       12290
+
+--- !ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_EXEC
+  Machine:         EM_X86_64
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    ## Not in a PT_LOAD. LMA = sh_addr = 0x1000.
+    Address:         0x1000
+    AddressAlign:    0x1000
+    Content:         "c3c3c3c3"
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_WRITE ]
+    ## LMA = sh_offset-p_offset+p_paddr = 0x2000-0x2000+0x4000 = 0x4000.
+    Address:         0x2000
+    AddressAlign:    0x1000
+    Content:         "3232"
+ProgramHeaders:
   - Type: PT_LOAD
     Flags: [ PF_R, PF_W ]
     VAddr: 0x2000
+    ## p_vaddr is increased from 0x2000 to 0x4000.
     PAddr: 0x4000
-    Align: 0x1000
     Sections:
       - Section: .data
 
-# CHECK:       0000000 c3c3 c3c3 0000 0000 0000 0000 0000 0000
-# CHECK-NEXT:  0000020 0000 0000 0000 0000 0000 0000 0000 0000
-# CHECK-NEXT:  *
-# CHECK-NEXT:  0030000 3232
-# SIZE:        12290
+## Check that we use sh_offset instead of sh_addr to decide where to write section contents.
+
+# RUN: yaml2obj --docnum=3 %s -o %t3
+# RUN: llvm-objcopy -O binary %t3 %t3.out
+# RUN: od -A x -t x2 %t3.out | FileCheck %s --check-prefix=CHECK3 --ignore-case
+# RUN: wc -c %t3.out | FileCheck %s --check-prefix=SIZE3
+
+## The minimum LMA of all sections is 0x1000.
+## The content of .data will be written at 0x3000-0x1000 = 0x2000.
+# CHECK3:      000000 c3c3 c3c3 0000 0000 0000 0000 0000 0000
+# CHECK3-NEXT: 000010 0000 0000 0000 0000 0000 0000 0000 0000
+# CHECK3-NEXT: *
+# CHECK3-NEXT: 002000 3232
+# SIZE3:       8194
+
+--- !ELF
+FileHeader:
+  Class:           ELFCLASS64
+  Data:            ELFDATA2LSB
+  Type:            ET_EXEC
+  Machine:         EM_X86_64
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    ## Not in a PT_LOAD. LMA = sh_addr = 0x1000.
+    Address:         0x1000
+    AddressAlign:    0x1000
+    Content:         "c3c3c3c3"
+  - Name:            .data
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_WRITE ]
+    ## sh_addr is increased from 0x2000 to 0x3000, but it is ignored.
+    ## LMA = sh_offset-p_offset+p_paddr = 0x2000-0x2000+0x3000 = 0x3000.
+    Address:         0x3000
+    AddressAlign:    0x1000
+    Content:         "3232"
+ProgramHeaders:
+  - Type: PT_LOAD
+    Flags: [ PF_R, PF_W ]
+    VAddr: 0x3000
+    PAddr: 0x3000
+    Sections:
+      - Section: .data

llvm/tools/llvm-objcopy/ELF/Object.cpp

Error BinaryWriter::finalize() {
 
   // Because we add a ParentSegment for each section we might have duplicate
   // segments in OrderedSegments. If there were duplicates then layoutSegments
   // would do very strange things.
   auto End =
       std::unique(std::begin(OrderedSegments), std::end(OrderedSegments));
   OrderedSegments.erase(End, std::end(OrderedSegments));
 
-  uint64_t Offset = 0;
-
-  // Modify the first segment so that there is no gap at the start. This allows
-  // our layout algorithm to proceed as expected while not writing out the gap
-  // at the start.
-  if (!OrderedSegments.empty()) {
-    Segment *Seg = OrderedSegments[0];
-    const SectionBase *Sec = Seg->firstSection();
-    auto Diff = Sec->OriginalOffset - Seg->OriginalOffset;
-    Seg->OriginalOffset += Diff;
-    // The size needs to be shrunk as well.
-    Seg->FileSize -= Diff;
-    // The PAddr needs to be increased to remove the gap before the first
-    // section.
-    Seg->PAddr += Diff;
-    uint64_t LowestPAddr = Seg->PAddr;
-    for (Segment *Segment : OrderedSegments) {
-      Segment->Offset = Segment->PAddr - LowestPAddr;
-      Offset = std::max(Offset, Segment->Offset + Segment->FileSize);
-    }
+  // Compute the section LMA based on its sh_offset and the containing segment's
+  // p_offset and p_paddr. Also compute the minimum LMA of all sections as
+  // MinAddr. In the output, the contents between address 0 and MinAddr will be
+  // skipped.
+  uint64_t MinAddr = UINT64_MAX;
+  for (SectionBase &Sec : Obj.allocSections()) {
+    if (Sec.ParentSegment != nullptr)
+      Sec.Addr =
+          Sec.Offset - Sec.ParentSegment->Offset + Sec.ParentSegment->PAddr;
+    MinAddr = std::min(MinAddr, Sec.Addr);
   }
 
-  layoutSections(Obj.allocSections(), Offset);
-
   // Now that every section has been laid out we just need to compute the total
   // file size. This might not be the same as the offset returned by
   // layoutSections, because we want to truncate the last segment to the end of
   // its last section, to match GNU objcopy's behaviour.
   TotalSize = 0;
-  for (const SectionBase &Sec : Obj.allocSections())
+  for (SectionBase &Sec : Obj.allocSections()) {
+    Sec.Offset = Sec.Addr - MinAddr;
     if (Sec.Type != SHT_NOBITS)
       TotalSize = std::max(TotalSize, Sec.Offset + Sec.Size);
+  }
 
   if (Error E = Buf.allocate(TotalSize))
     return E;
   SecWriter = std::make_unique<BinarySectionWriter>(Buf);
   return Error::success();
 }
 
 bool IHexWriter::SectionCompare::operator()(const SectionBase *Lhs,