[llvm-objcopy] Use physical instead of virtual address when aligning and placing sections in binary

[owenpshaw]

Summary

For sections with different virtual and physical addresses, alignment and placement in the output binary should be based on the physical address.

Ran into this problem with a bare metal ARM project where llvm-objcopy added a lot of zero-padding before the .data section that had differing addresses. GNU objcopy did not add the padding, and after this fix, neither does llvm-objcopy.

Update a test case so a section has different physical and virtual addresses.

Fixes B35708

[jakehehrlich]

This change as is might cause us to fail the following requirement

As ``Program Loading'' describes in this chapter of the processor supplement, loadable process segments must have congruent values for p_vaddr and p_offset, modulo the page size. This member gives the value to which the segments are aligned in memory and in the file. Values 0 and 1 mean no alignment is required. Otherwise, p_align should be a positive, integral power of 2, and p_vaddr should equal p_offset, modulo p_align.

If PAddr and VAddr differ modulo Align then this change will cause the above to be violated and there's no getting around that with this sort of solution. If this bug is to be fixed it will need to be with code that violates the above invariant in some principled way and it isn't clear to me what that principle should be. One principal that should I think should not be violated is that if EI_OSABI is ELFOSABI_NONE (e.g. System V) then the above alignment constraint should always be respected. This leaves room if EI_OSABI is something else for this requirement to change. I'm not sure how exactly that should be handled though.

Additionally as long as EI_OSABI is ELFOSABI_NONE PAddr is not a defined value per the following

On systems for which physical addressing is relevant, this member is reserved for the segment's physical address. Because System V ignores physical addressing for application programs, this member has unspecified contents for executable files and shared objects.

So as is this change does not seem acceptable to me.

[owenpshaw]

Still learning the process here, so let me know how you'd like to proceed. I really only opened this to get a discussion going because there wasn't activity on the bug after a week or so...maybe too impatient, after all it was the holidays :)

So I'm fine closing this review if we want to focus discussion over on the bug since it has more information now. I'm also fine leaving this open if its a handy way to review new patches.

I agree we shouldn't violate the spec, but also I still think there should be some fix for this bare metal use case and for gnu compatibility.

[jakehehrlich]

In D41619#966100, @owenpshaw wrote:

Still learning the process here, so let me know how you'd like to proceed. I really only opened this to get a discussion going because there wasn't activity on the bug after a week or so...maybe too impatient, after all it was the holidays :)

Eh, I'm not really to clear on this either. I probably should have moved discussion about the proper solution here instead of letting it continue on bugzilla.

So I'm fine closing this review if we want to focus discussion over on the bug since it has more information now. I'm also fine leaving this open if its a handy way to review new patches.

No need for that. This is an issue that needs to be fixed and this is where that review should happen.

I agree we shouldn't violate the spec, but also I still think there should be some fix for this bare metal use case and for gnu compatibility.

After your digging in the bfd code I think I'm happy with changing the binary layout algorithm to use PAddr instead of VAddr but I want the ELF layout to explicitly use VAddr. I want the VAddr alignment property to obviously hold.

[owenpshaw]

Updated patch to only use PAddr for binary output, and to populate PAddr with VAddr if every segment has a 0 value for PAddr initially. Added new tests instead modifying existing alignment test.

[jakehehrlich]

Other than the one inline comment I'm happy with this. I want James to take a look at this as well however. He's in England and will probably look at this tonight or the next day. I believe he had the same vacation days as me so he should be back as of tonight. I'd also really like someone with more embedded background to look at this but the evidence from BFD seems like an acceptable replacement.

Nice work.

tools/llvm-objcopy/Object.cpp

893

Can we use std::find_if and a lambda here instead?

[owenpshaw]

Updated to use std::find_if

[jhenderson]

Could you also add a test for non-binary output, with PAddr set, to show that it is ignored, please.

I don't have any experience with using differing physical and virtual addresses, so I can't really comment on the validity of this. The code looks like it does as desired though. I assume that the virtual address alignment requirement for binary output is not the same as for ELF output, i.e. that it does not have to be congruent to offset mod the alignment?

tools/llvm-objcopy/Object.cpp

893

Better yet, we can use std::any_of here, to remove the need for the std::end check.

898

The VAddr needs -> The VAddr and PAddr need

[jakehehrlich]

I assume that the virtual address alignment requirement for binary output is not the same as for ELF output

There's no spec to go off for that case so I'm not sure. One the one hand it means there's no spec to violate but on the other hand there might be a colloquially correct option that we have no means of looking up. My normal goto on questions like this is Roland here but Roland is OOO from some unknown amount of time. No one else I've talked to knows the answer to this either.

[owenpshaw]

Looks like binutils doesn't bother with any alignment, and just offsets everything from the lowest PAddr, which seems reasonable given that in the embedded case the binary will likely be loaded on a device as-is at that lowest PAddr. I can update the patch to do this when using PAddr instead of calling align.

[owenpshaw]

If I ignore alignment for binary output and offset segments based on their distance from the lowest PAddr, a few tests break. I think the tests need to change, but looking for other opinions before proceeding.

basic-align-copy.test - Uses binary output in the test. Should it change to using elf output? Or was it intended to test binary alignment, which we're now changing?

two-seg-remove-end.test, two-seg-remove-first.test, two-seg-remove-third-sec.test - All use binary output, but define two segments with identical PAddr, so they're output on top of each other using this new offset logic. Do we actually want to test identical PAddrs, or is that just an oversight in the test that didn't matter before? Should these tests use binary output, or change to elf?

[jhenderson]

In D41619#970577, @owenpshaw wrote:

basic-align-copy.test - Uses binary output in the test. Should it change to using elf output? Or was it intended to test binary alignment, which we're now changing?

Yes, this was intended for testing binary alignment (see D34480, which added support for binary output). The key feature of the test is that the second section needs to be aligned, based on it's address alignment, so this can change as we change the behaviour.

two-seg-remove-end.test, two-seg-remove-first.test, two-seg-remove-third-sec.test - All use binary output, but define two segments with identical PAddr, so they're output on top of each other using this new offset logic. Do we actually want to test identical PAddrs, or is that just an oversight in the test that didn't matter before? Should these tests use binary output, or change to elf?

I feel like this is a mistake in the tests - the virtual and physical address of each segment should be different (note that the sections assigned to them have specific addresses themselves), but please wait for Jake to confirm.

[jakehehrlich]

two-seg-remove-* tests having the same physical on different segments was a mistake that didn't matter until now. I'll fix those. The alignment behavior was 100% intended and I should be able to reproduce the results with objcopy if memory serves. I'll post an example. Perhaps I just messed that up though.

[jakehehrlich]

After some further testing (read, writing strange assembly files and linker scripts) it seems like segments are indeed layed out to create a proper memory image (Owen's current recommendation) however allocated sections that are not in segments are pushed to alignment regardless of address. So I believe your change would be consistent with that. I'm not sure how I got the idea that these were being pushed to alignment especially considering that I explicitly checked to see if it was creating a memory image or if it was pushing to alignment. I believe at the time of writing that test (was like the second non-trivial feature added) I was using yaml2obj to produce sections to test that on and I must not have used program headers.

So my current recommendation is that segments be laid out such that the lowest physical address is assigned offset zero and subsequent segments are assigned offsets by subtracting the lowest physical address from their physical address. Sections are then written out as they currently are. The front part of the first segment still needs to be chopped off by adding/subtracting Diff from all the needed values so that the first section is properly handled.

I think in a nut shell the segments should be laid out the way the loader would lay them out and the section layout should basically stay the same. Thanks for getting to the bottom of this Owen!

[owenpshaw]

New patch offsets segments according to difference from lowest PAddr.

I've updated the test cases we discussed, but can back those changes out if you've already taken care of them. The new binary align test makes sure there's a small gap as expected based on PAddrs.

[jakehehrlich]

test/tools/llvm-objcopy/basic-align-copy.test

1 ↗

(On Diff #129159)

Can you rename this file to "binary-segment-layout" or something that that relates to what the test now actually tests since it no longer tests that alignment is respected.

33 ↗

(On Diff #129159)

This will violate the p_addr == p_offset (MOD p_align) requirement as is. If you don't want these to be on seperate pages change the Address Align of the sections. Ideally we would have small AddressAlign's and large ProgramHeader alignment but unfortunately I haven't updated the layout strategy of yaml2obj to make that work properly yet so I've been getting by with this.

tools/llvm-objcopy/Object.cpp

734

Unfortunately the lowest PAddr will not necessarily come from the Segment with the lowest offset. You'll need to use std::min_element to find the one you're looking for. In fact because the order that segments might need to be laid out in might differ from the order they're presented to this function in it's not clear this function should be used. I *think* this winds up working because in practice the only Segments in the Segments vector here are PT_LOAD segments are not nested inside of anything so consequently the only case that will run is the "Offset = Segment->PAddr - LowestPAddr;".. More over if that's the only case that's ever going to be hit I don't think we need to embed it in such a complicated function as this one. I think the code is different enough now that we can just inline the layout algorithm for the binary case in BinaryObject<ELFT>::finalize() and remove the UsePAddr argument and the if condition. Two simple more obviously correct algorithms are better than one
slightly more complicated algorithm. Especially when it comes layout (which has historically been the hardest thing to get right)

906

I think you should inline the new algorithm for binary segment layout here and LayoutSegments can just be for ELF file layout.

[owenpshaw]

Inlined the binary segment layout and renamed the test.

I changed the segment ordering to compare using PAddr, which make getting the lowest PAddr easy, but also ensures the Segment[0] to be adjusted for a starting gap is really the one that will be output first in the binary.

[jakehehrlich]

tools/llvm-objcopy/Object.cpp

894

For the std::unique call to work below identical pointers need to be next to each other so this needs to compare the pointers if PAddr is equal. This would happen if for instance we had multiple empty sections inside the same empty segment (Call it segment A) and then another non-empty segment (with a section in it, call it segment B) that had the same PAddr. It could happen that OrderedSegments was [A, B, A] to start and then stable_sort would produce [A, B, A] as well because as far as stable_sort is concerned [A, B, A] is sorted. Then when std::unqiue is run [A, B, A] would remain unchanged.

[owenpshaw]

Fix comparison to handle cases two segments have the same PAddr

[jakehehrlich]

So Roland looked at this and said this seems reasonable to him. It should agree with our personal use case as well. Between my testing, Owen looking and linking us to the BFD code, and Roland's approval I'm confident this approach is correct. This code LGTM but as always I'd like to wait for James for the final LGTM. Also I'm waiting for feed back on use of member pointers in llvm. Using rare little known features is generally frowned on so I wanted to make sure first. If I don't hear back we can just have a bit of duplicated code.

tools/llvm-objcopy/Object.cpp

355

I'm wondering if using a member point is ok here because it would let you dedup these two functions. Something like

compareSegmentsUsing(uint64_t Segment::*Member, const Segment *A, const Segment *B) {
  if (A->*Member < B->*Member)
    return true;
  if (A->*Member > B->*Member)
    return false;
  return A->Index < B->Index;
}

Then to pass the function you can use std::bind(compareSegmentsUsing, &Segment::PAddr)

This might be discouraged by llvm though since it's so uncommonly used that many people aren't aware of this feature.

[jhenderson]

Overall design looks okay, but I've got a few comments that need addressing before I give it a LGTM.

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

1 ↗

(On Diff #129198)

I wonder whether it would be beneficial to have a another test-case here, or possibly extend this one to have a gap in the physical address range, a bit like binary-segment-layout does for virtual addresses. I assume that the binary layout code should then preserve the gap between these two segments.

tools/llvm-objcopy/Object.cpp

345

I think this function should probably be renamed to "compareSegmentsByOffset" and the new function "compareSegmentsByPAddr" (assuming we don't follow Jake's suggestion). Also, I think "By" sounds better than "Using", but it's incredibly trivial, so I don't mind.

355

I don't think I've ever seen such a feature used before!

881–882

Nit: rom should be capitalized, i.e. ROM, since it's an abbreviation.

899

Do you need to adjust VAddr any more? As far as I can see, it isn't used at all after PAddr has been initialized to it. Also, the comment above it needs updating to reflect our new usage of PAddr and why we update it.

901–903

I think this block can be removed now, since we don't align segments at all for binary output.

907

Just want to check, but are NOBITS sections allocated space on disk for binary output? I assume not, but thought it best to double check...

[jakehehrlich]

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

1 ↗

(On Diff #129198)

That seems like a good additional thing to add. The gap should be preserved for segments but not for sections that are outside of segments.

tools/llvm-objcopy/Object.cpp

355

It's honestly what you get when you follow the very basic deduplication principal "make the parts that are different a parameter" but it's very very rarely used. Even this case is kind of academic THB.

899

Actually yeah, I should have caught this. Following that logic there was never really a reason to update MemSize either.

907

If they're inside a segment and not at the end of the file then space is allocated to them. If they're not in a segment or if they're at the end of the last segment then they're left out.

[jakehehrlich]

Also IRC gave the greenlight on pointer to members. I'm not I really care *that* much but using pointers to members would allow for a generic "compareSegmentsBy" when used in conjunction with std::bind.

[owenpshaw]

Updated according to suggestions. I didn't change to using member pointers, but can if you prefer. While I usually agree that de-duplication is best, in this case I feel like it makes the calling code more difficult to decipher in exchange for little gain in de-duplication.

std::stable_sort(start, end, compareSegmentsByOffset);

// vs

using namespace std::placeholders;
std::stable_sort(start, end, std::bind(compareSegmentsBy, &Segment::OriginalOffset, _1, _2))

[jakehehrlich]

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

35 ↗

(On Diff #129336)

We don't know where the .data section will end up only that it will have 4-byte alignment It's possible (even quite likely) for the the offset of the .data section (which decides the offset of the program header unfortunately, not the other way around) to be such that the p_offset % p_align != p_vaddr % p_align. This is still not a valid ELF file (at least it isn't assured).

[owenpshaw]

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

35 ↗

(On Diff #129336)

I guess I'm missing something with this alignment stuff. Having possibly invalid values in the elf doesn't seem to affect what we're testing, but I agree it'd be good to use proper input if possible. What values would make it valid?

[jhenderson]

Looks good to me, with the suggested changes. Just get Jake to give one final approval to address his concern in the test.

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

35 ↗

(On Diff #129336)

Maybe try PAddr 0x4000 and PVaddr 0x2000, and then use .data AddrAlign of 0x1000?

tools/llvm-objcopy/Object.cpp

903

Nit: full stop at end of comment.

Also, what gap? I assume you mean the gap at the start of the file, so I'd say "remove the gap before the first section."

[jakehehrlich]

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

35 ↗

(On Diff #129336)

That would work.

[owenpshaw]

Updated with latest suggestions

[jakehehrlich]

LGTM

[owenpshaw]

Thanks for the help getting this one sorted out! I don't have commit access.

[jakehehrlich]

In D41619#973662, @owenpshaw wrote:

Thanks for the help getting this one sorted out! I don't have commit access.

I'll land it for you then. No worries.

[owenpshaw]

Just wanted to check in on this one since it hasn't landed yet. Is there anything else I need to do?

[jakehehrlich]

In D41619#984043, @owenpshaw wrote:

Just wanted to check in on this one since it hasn't landed yet. Is there anything else I need to do?

No this is my fault. I'll land it right now.

[jakehehrlich]

This comment was removed by jakehehrlich.

test/tools/llvm-objcopy/check-addr-offset-align-binary.test

- 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:         0x1008
+    Address:         0x1010
     AddressAlign:    0x0000000000000008
     Content:         "3232"
 ProgramHeaders:
   - Type: PT_LOAD
     Flags: [ PF_X, PF_R ]
     VAddr: 0x1000
     PAddr: 0x1000
     Align: 0x1000
     Sections:
       - Section: .text
   - Type: PT_LOAD
     Flags: [ PF_R, PF_W ]
-    VAddr: 0x1008
+    VAddr: 0x1010
     PAddr: 0x1008
     Align: 0x1000
     Sections:
       - Section: .data
 
 # CHECK: 0000000 c3 c3 c3 c3 00 00 00 00 32 32

tools/llvm-objcopy/Object.cpp

 // range.
 static bool segmentOverlapsSegment(const Segment &Child,
                                    const Segment &Parent) {
 
   return Parent.OriginalOffset <= Child.OriginalOffset &&
          Parent.OriginalOffset + Parent.FileSize > Child.OriginalOffset;
 }
 
 static bool compareSegments(const Segment *A, const Segment *B) {
   // Any segment without a parent segment should come before a segment
   // that has a parent segment.
   if (A->OriginalOffset < B->OriginalOffset)
     return true;
   if (A->OriginalOffset > B->OriginalOffset)
     return false;
   return A->Index < B->Index;
 }
 
 template <class ELFT>
 void Object<ELFT>::readProgramHeaders(const ELFFile<ELFT> &ElfFile) {
   uint32_t Index = 0;
   for (const auto &Phdr : unwrapOrError(ElfFile.program_headers())) {
     ArrayRef<uint8_t> Data{ElfFile.base() + Phdr.p_offset,
                            (size_t)Phdr.p_filesz};
     Segments.emplace_back(llvm::make_unique<Segment>(Data));
     Segment &Seg = *Segments.back();
     Seg.Type = Phdr.p_type;
static uint64_t LayoutSegments(std::vector<Segment *> &Segments,
   // The only way a segment should move is if a section was between two
   // segments and that section was removed. If that section isn't in a segment
   // then it's acceptable, but not ideal, to simply move it to after the
   // segments. So we can simply layout segments one after the other accounting
   // for alignment.
   for (auto &Segment : Segments) {
     // We assume that segments have been ordered by OriginalOffset and Index
     // such that a parent segment will always come before a child segment in
     // OrderedSegments. This means that the Offset of the ParentSegment should
     // already be set and we can set our offset relative to it.
     if (Segment->ParentSegment != nullptr) {
       auto Parent = Segment->ParentSegment;
       Segment->Offset =
           Parent->Offset + Segment->OriginalOffset - Parent->OriginalOffset;
     } else {
-      Offset = alignToAddr(Offset, Segment->VAddr, Segment->Align);
+      Offset = alignToAddr(Offset, Segment->PAddr, Segment->Align);
       Segment->Offset = Offset;
     }
     Offset = std::max(Offset, Segment->Offset + Segment->FileSize);
   }
   return Offset;
 }
 
 // This function finds a consistent layout for a list of sections. It assumes
template <class ELFT> void BinaryObject<ELFT>::finalize() {
   for (auto &Section : this->Sections) {
     if ((Section->Flags & SHF_ALLOC) != 0 &&
         Section->ParentSegment != nullptr) {
       OrderedSegments.push_back(Section->ParentSegment);
     }
   }
   OrderSegments(OrderedSegments);
   // 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));
 
   // Modify the first segment so that there is no gap at the start. This allows
   // our layout algorithm to proceed as expected while not out writing out the
   // gap at the start.
   if (!OrderedSegments.empty()) {
     auto Seg = OrderedSegments[0];
     auto Sec = Seg->firstSection();
     auto Diff = Sec->OriginalOffset - Seg->OriginalOffset;
     Seg->OriginalOffset += Diff;
     // The size needs to be shrunk as well
     Seg->FileSize -= Diff;
     Seg->MemSize -= Diff;
     // The VAddr needs to be adjusted so that the alignment is correct as well
     Seg->VAddr += Diff;
     Seg->PAddr = Seg->VAddr;
     // We don't want this to be shifted by alignment so we need to set the
     // alignment to zero.
     Seg->Align = 0;
   }
 
   uint64_t Offset = LayoutSegments(OrderedSegments, 0);
 
   // TODO: generalize LayoutSections to take a range. Pass a special range
   // constructed from an iterator that skips values for which a predicate does
   // not hold. Then pass such a range to LayoutSections instead of constructing
   // AllocatedSections here.
   std::vector<SectionBase *> AllocatedSections;
   for (auto &Section : this->Sections) {
     if ((Section->Flags & SHF_ALLOC) == 0)
       continue;