Index: llvm/trunk/test/tools/llvm-objcopy/adjacent-segments.test =================================================================== --- llvm/trunk/test/tools/llvm-objcopy/adjacent-segments.test +++ llvm/trunk/test/tools/llvm-objcopy/adjacent-segments.test @@ -0,0 +1,62 @@ +# This test tests that if two non-overlapping segments are right next to each +# other no problems arise. + +# RUN: yaml2obj %s -o %t +# RUN: llvm-objcopy %t %t2 +# RUN: llvm-readobj --program-headers %t2 | FileCheck %s + +!ELF +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + Type: ET_EXEC + Machine: EM_X86_64 +Sections: + - Name: .text + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 24 + - Name: .text2 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x10 + Size: 16 +ProgramHeaders: + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text2 + +#CHECK: ProgramHeaders [ +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x1000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 24 +#CHECK-NEXT: MemSize: 24 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x1020 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 16 +#CHECK-NEXT: MemSize: 16 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 16 +#CHECK-NEXT: } +#CHECK-NEXT:] Index: llvm/trunk/test/tools/llvm-objcopy/identical-segments.test =================================================================== --- llvm/trunk/test/tools/llvm-objcopy/identical-segments.test +++ llvm/trunk/test/tools/llvm-objcopy/identical-segments.test @@ -0,0 +1,82 @@ +# This test tests that if two possible parent segments have the same offset that +# they're disambiguated based on their original index. This ensures that cycles +# do not occur. + +# RUN: yaml2obj %s -o %t +# RUN: llvm-objcopy %t %t2 +# RUN: llvm-readobj --program-headers %t2 | FileCheck %s + +!ELF +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + Type: ET_EXEC + Machine: EM_X86_64 +Sections: + - Name: .text + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text2 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 +ProgramHeaders: + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text2 + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text + - Section: .text2 + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text + - Section: .text2 + +#CHECK: ProgramHeaders [ +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x2000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 4096 +#CHECK-NEXT: MemSize: 4096 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x1000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 8192 +#CHECK-NEXT: MemSize: 8192 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x1000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 8192 +#CHECK-NEXT: MemSize: 8192 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT:] Index: llvm/trunk/test/tools/llvm-objcopy/overlap-chain.test =================================================================== --- llvm/trunk/test/tools/llvm-objcopy/overlap-chain.test +++ llvm/trunk/test/tools/llvm-objcopy/overlap-chain.test @@ -0,0 +1,117 @@ +# This test tests how ParentSegment is set for Segments. In particular this test +# tests that if a chain of parents forms, the offsets are chosen for parents +# first despite the order of the list. It also tests multiple branches of the +# code that assigns parents. + +# RUN: yaml2obj %s -o %t +# RUN: llvm-objcopy %t %t2 +# RUN: llvm-readobj -program-headers %t2 | FileCheck %s + +!ELF +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + Type: ET_EXEC + Machine: EM_X86_64 +Sections: + - Name: .text + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text2 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text3 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text4 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text5 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 +ProgramHeaders: + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text + - Section: .text2 + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text4 + - Section: .text5 + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text3 + - Section: .text4 + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text2 + - Section: .text3 + +#CHECK: ProgramHeaders [ +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x1000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 8192 +#CHECK-NEXT: MemSize: 8192 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x4000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 8192 +#CHECK-NEXT: MemSize: 8192 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x3000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 8192 +#CHECK-NEXT: MemSize: 8192 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x2000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 8192 +#CHECK-NEXT: MemSize: 8192 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT:] Index: llvm/trunk/test/tools/llvm-objcopy/pt-phdr.test =================================================================== --- llvm/trunk/test/tools/llvm-objcopy/pt-phdr.test +++ llvm/trunk/test/tools/llvm-objcopy/pt-phdr.test @@ -0,0 +1,71 @@ +# This test simply tests a simple but common real world example of overlapping +# segments. + +# RUN: llvm-objcopy %p/Inputs/pt-phdr.elf %t +# RUN: llvm-readobj -program-headers %t | FileCheck %s + +#CHECK: ProgramHeaders [ +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_PHDR +#CHECK-NEXT: Offset: 0x40 +#CHECK-NEXT: VirtualAddress: 0x200040 +#CHECK-NEXT: PhysicalAddress: 0x200040 +#CHECK-NEXT: FileSize: 280 +#CHECK-NEXT: MemSize: 280 +#CHECK-NEXT: Flags [ +#CHECK-NEXT: PF_R +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 8 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD +#CHECK-NEXT: Offset: 0x0 +#CHECK-NEXT: VirtualAddress: 0x200000 +#CHECK-NEXT: PhysicalAddress: 0x200000 +#CHECK-NEXT: FileSize: 344 +#CHECK-NEXT: MemSize: 344 +#CHECK-NEXT: Flags [ +#CHECK-NEXT: PF_R +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD +#CHECK-NEXT: Offset: 0x1000 +#CHECK-NEXT: VirtualAddress: 0x201000 +#CHECK-NEXT: PhysicalAddress: 0x201000 +#CHECK-NEXT: FileSize: 1 +#CHECK-NEXT: MemSize: 1 +#CHECK-NEXT: Flags [ +#CHECK-NEXT: PF_R +#CHECK-NEXT: PF_X +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD +#CHECK-NEXT: Offset: 0x2000 +#CHECK-NEXT: VirtualAddress: 0x202000 +#CHECK-NEXT: PhysicalAddress: 0x202000 +#CHECK-NEXT: FileSize: 14 +#CHECK-NEXT: MemSize: 14 +#CHECK-NEXT: Flags [ +#CHECK-NEXT: PF_R +#CHECK-NEXT: PF_W +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_GNU_STACK (0x6474E551) +#CHECK-NEXT: Offset: 0x0 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 0 +#CHECK-NEXT: MemSize: 0 +#CHECK-NEXT: Flags [ +#CHECK-NEXT: PF_R +#CHECK-NEXT: PF_W +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 0 +#CHECK-NEXT: } +#CHECK-NEXT:] Index: llvm/trunk/test/tools/llvm-objcopy/triple-overlap.test =================================================================== --- llvm/trunk/test/tools/llvm-objcopy/triple-overlap.test +++ llvm/trunk/test/tools/llvm-objcopy/triple-overlap.test @@ -0,0 +1,123 @@ +# This test tests that each segment is assigned a canonical parent segment. +# Importantly if two segments could be the parent segment of a segment this test +# should cover the case where a new parent replaces the old parent and the case +# where an old parent is not replaced by a new parent. + +# RUN: yaml2obj %s -o %t +# RUN: llvm-objcopy %t %t2 +# RUN: llvm-readobj --program-headers %t2 | FileCheck %s + +!ELF +FileHeader: + Class: ELFCLASS64 + Data: ELFDATA2LSB + Type: ET_EXEC + Machine: EM_X86_64 +Sections: + - Name: .text + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text2 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text3 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text4 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 + - Name: .text5 + Type: SHT_PROGBITS + Flags: [ SHF_ALLOC, SHF_EXECINSTR ] + AddressAlign: 0x1000 + Size: 4096 +ProgramHeaders: + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text4 + - Section: .text5 + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text3 + - Section: .text4 + - Section: .text5 + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text + - Section: .text2 + - Section: .text3 + - Section: .text4 + - Section: .text5 + - Type: PT_LOAD + Flags: [ PF_X, PF_R ] + Sections: + - Section: .text2 + - Section: .text3 + - Section: .text4 + - Section: .text5 + +#CHECK: ProgramHeaders [ +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x4000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 8192 +#CHECK-NEXT: MemSize: 8192 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x3000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 12288 +#CHECK-NEXT: MemSize: 12288 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x1000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 20480 +#CHECK-NEXT: MemSize: 20480 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT: ProgramHeader { +#CHECK-NEXT: Type: PT_LOAD (0x1) +#CHECK-NEXT: Offset: 0x2000 +#CHECK-NEXT: VirtualAddress: 0x0 +#CHECK-NEXT: PhysicalAddress: 0x0 +#CHECK-NEXT: FileSize: 16384 +#CHECK-NEXT: MemSize: 16384 +#CHECK-NEXT: Flags [ (0x5) +#CHECK-NEXT: PF_R (0x4) +#CHECK-NEXT: PF_X (0x1) +#CHECK-NEXT: ] +#CHECK-NEXT: Alignment: 4096 +#CHECK-NEXT: } +#CHECK-NEXT:] Index: llvm/trunk/tools/llvm-objcopy/Object.h =================================================================== --- llvm/trunk/tools/llvm-objcopy/Object.h +++ llvm/trunk/tools/llvm-objcopy/Object.h @@ -72,6 +72,7 @@ uint64_t VAddr; uint64_t OriginalOffset; + Segment *ParentSegment; Segment(llvm::ArrayRef Data) : Contents(Data) {} void finalize(); Index: llvm/trunk/tools/llvm-objcopy/Object.cpp =================================================================== --- llvm/trunk/tools/llvm-objcopy/Object.cpp +++ llvm/trunk/tools/llvm-objcopy/Object.cpp @@ -240,6 +240,15 @@ Segment.Offset + Segment.FileSize >= Section.OriginalOffset + SecSize; } +// Returns true IFF a segment's original offset is inside of another segment's +// range. +static bool segmentOverlapsSegment(const Segment &Child, + const Segment &Parent) { + + return Parent.OriginalOffset <= Child.OriginalOffset && + Parent.OriginalOffset + Parent.FileSize > Child.OriginalOffset; +} + template void Object::readProgramHeaders(const ELFFile &ElfFile) { uint32_t Index = 0; @@ -268,6 +277,30 @@ } } } + // Now we do an O(n^2) loop through the segments in order to match up + // segments. + for (auto &Child : Segments) { + for (auto &Parent : Segments) { + // Every segment will overlap with itself but we don't want a segment to + // be it's own parent so we avoid that situation. + if (&Child != &Parent && segmentOverlapsSegment(*Child, *Parent)) { + // We want a canonical "most parental" segment but this requires + // inspecting the ParentSegment. + if (Child->ParentSegment != nullptr) { + if (Child->ParentSegment->OriginalOffset > Parent->OriginalOffset) { + Child->ParentSegment = Parent.get(); + } else if (Child->ParentSegment->Index > Parent->Index) { + // They must have equal OriginalOffsets so we need to disambiguate. + // To decide which is the parent we'll choose the one with the + // higher index. + Child->ParentSegment = Parent.get(); + } + } else { + Child->ParentSegment = Parent.get(); + } + } + } + } } template @@ -497,13 +530,30 @@ } template void ELFObject::assignOffsets() { + // We need a temporary list of segments that has a special order to it + // so that we know that anytime ->ParentSegment is set that segment has + // already had it's offset properly set. + std::vector OrderedSegments; + for (auto &Segment : this->Segments) + OrderedSegments.push_back(Segment.get()); + auto 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; + }; + std::stable_sort(std::begin(OrderedSegments), std::end(OrderedSegments), + CompareSegments); // The size of ELF + program headers will not change so it is ok to assume // that the first offset of the first segment is a good place to start // outputting sections. This covers both the standard case and the PT_PHDR // case. uint64_t Offset; - if (!this->Segments.empty()) { - Offset = this->Segments[0]->Offset; + if (!OrderedSegments.empty()) { + Offset = OrderedSegments[0]->Offset; } else { Offset = sizeof(Elf_Ehdr); } @@ -512,10 +562,20 @@ // 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 : this->Segments) { - Offset = alignTo(Offset, Segment->Align); - Segment->Offset = Offset; - Offset += Segment->FileSize; + for (auto &Segment : OrderedSegments) { + // 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 = alignTo(Offset, Segment->Align == 0 ? 1 : Segment->Align); + Segment->Offset = Offset; + Offset += Segment->FileSize; + } } // Now the offset of every segment has been set we can assign the offsets // of each section. For sections that are covered by a segment we should use