Changeset View
Standalone View
tools/llvm-objcopy/Object.cpp
| Show First 20 Lines • Show All 403 Lines • ▼ Show 20 Lines | |||||
| // range. | // range. | ||||
| static bool segmentOverlapsSegment(const Segment &Child, | static bool segmentOverlapsSegment(const Segment &Child, | ||||
| const Segment &Parent) { | const Segment &Parent) { | ||||
| return Parent.OriginalOffset <= Child.OriginalOffset && | return Parent.OriginalOffset <= Child.OriginalOffset && | ||||
| Parent.OriginalOffset + Parent.FileSize > Child.OriginalOffset; | Parent.OriginalOffset + Parent.FileSize > Child.OriginalOffset; | ||||
| } | } | ||||
| static bool compareSegments(const Segment *A, const Segment *B) { | static bool compareSegmentsByOffset(const Segment *A, const Segment *B) { | ||||
jhenderson: I think this function should probably be renamed to "compareSegmentsByOffset" and the new… | |||||
| // Any segment without a parent segment should come before a segment | // Any segment without a parent segment should come before a segment | ||||
| // that has a parent segment. | // that has a parent segment. | ||||
| if (A->OriginalOffset < B->OriginalOffset) | if (A->OriginalOffset < B->OriginalOffset) | ||||
| return true; | return true; | ||||
| if (A->OriginalOffset > B->OriginalOffset) | if (A->OriginalOffset > B->OriginalOffset) | ||||
| return false; | return false; | ||||
| return A->Index < B->Index; | return A->Index < B->Index; | ||||
| } | } | ||||
| static bool compareSegmentsByPAddr(const Segment *A, const Segment *B) { | |||||
Not Done ReplyInline ActionsI'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. jakehehrlich: I'm wondering if using a member point is ok here because it would let you dedup these two… | |||||
Not Done ReplyInline ActionsI don't think I've ever seen such a feature used before! jhenderson: I don't think I've ever seen such a feature used before! | |||||
Not Done ReplyInline ActionsIt'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. jakehehrlich: It's honestly what you get when you follow the very basic deduplication principal "make the… | |||||
| if (A->PAddr < B->PAddr) | |||||
| return true; | |||||
| if (A->PAddr > B->PAddr) | |||||
| return false; | |||||
| return A->Index < B->Index; | |||||
| } | |||||
| template <class ELFT> | template <class ELFT> | ||||
| void Object<ELFT>::readProgramHeaders(const ELFFile<ELFT> &ElfFile) { | void Object<ELFT>::readProgramHeaders(const ELFFile<ELFT> &ElfFile) { | ||||
| uint32_t Index = 0; | uint32_t Index = 0; | ||||
| for (const auto &Phdr : unwrapOrError(ElfFile.program_headers())) { | for (const auto &Phdr : unwrapOrError(ElfFile.program_headers())) { | ||||
| ArrayRef<uint8_t> Data{ElfFile.base() + Phdr.p_offset, | ArrayRef<uint8_t> Data{ElfFile.base() + Phdr.p_offset, | ||||
| (size_t)Phdr.p_filesz}; | (size_t)Phdr.p_filesz}; | ||||
| Segments.emplace_back(llvm::make_unique<Segment>(Data)); | Segments.emplace_back(llvm::make_unique<Segment>(Data)); | ||||
| Segment &Seg = *Segments.back(); | Segment &Seg = *Segments.back(); | ||||
| Show All 21 Lines | void Object<ELFT>::readProgramHeaders(const ELFFile<ELFT> &ElfFile) { | ||||
| // segments. | // segments. | ||||
| for (auto &Child : Segments) { | for (auto &Child : Segments) { | ||||
| for (auto &Parent : Segments) { | for (auto &Parent : Segments) { | ||||
| // Every segment will overlap with itself but we don't want a segment to | // Every segment will overlap with itself but we don't want a segment to | ||||
| // be it's own parent so we avoid that situation. | // be it's own parent so we avoid that situation. | ||||
| if (&Child != &Parent && segmentOverlapsSegment(*Child, *Parent)) { | if (&Child != &Parent && segmentOverlapsSegment(*Child, *Parent)) { | ||||
| // We want a canonical "most parental" segment but this requires | // We want a canonical "most parental" segment but this requires | ||||
| // inspecting the ParentSegment. | // inspecting the ParentSegment. | ||||
| if (compareSegments(Parent.get(), Child.get())) | if (compareSegmentsByOffset(Parent.get(), Child.get())) | ||||
| if (Child->ParentSegment == nullptr || | if (Child->ParentSegment == nullptr || | ||||
| compareSegments(Parent.get(), Child->ParentSegment)) { | compareSegmentsByOffset(Parent.get(), Child->ParentSegment)) { | ||||
| Child->ParentSegment = Parent.get(); | Child->ParentSegment = Parent.get(); | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| } | } | ||||
| template <class ELFT> | template <class ELFT> | ||||
| ▲ Show 20 Lines • Show All 309 Lines • ▼ Show 20 Lines | static uint64_t alignToAddr(uint64_t Offset, uint64_t Addr, uint64_t Align) { | ||||
| // (Offset + Diff) & -Align == Addr & -Align will still hold. | // (Offset + Diff) & -Align == Addr & -Align will still hold. | ||||
| if (Diff < 0) | if (Diff < 0) | ||||
| Diff += Align; | Diff += Align; | ||||
| return Offset + Diff; | return Offset + Diff; | ||||
| } | } | ||||
| // Orders segments such that if x = y->ParentSegment then y comes before x. | // Orders segments such that if x = y->ParentSegment then y comes before x. | ||||
| static void OrderSegments(std::vector<Segment *> &Segments) { | static void OrderSegments(std::vector<Segment *> &Segments) { | ||||
| std::stable_sort(std::begin(Segments), std::end(Segments), compareSegments); | std::stable_sort(std::begin(Segments), std::end(Segments), | ||||
| compareSegmentsByOffset); | |||||
| } | } | ||||
| // This function finds a consistent layout for a list of segments starting from | // This function finds a consistent layout for a list of segments starting from | ||||
| // an Offset. It assumes that Segments have been sorted by OrderSegments and | // an Offset. It assumes that Segments have been sorted by OrderSegments and | ||||
| // returns an Offset one past the end of the last segment. | // returns an Offset one past the end of the last segment. | ||||
| static uint64_t LayoutSegments(std::vector<Segment *> &Segments, | static uint64_t LayoutSegments(std::vector<Segment *> &Segments, | ||||
| uint64_t Offset) { | uint64_t Offset) { | ||||
| assert(std::is_sorted(std::begin(Segments), std::end(Segments), | assert(std::is_sorted(std::begin(Segments), std::end(Segments), | ||||
| compareSegments)); | compareSegmentsByOffset)); | ||||
| // The only way a segment should move is if a section was between two | // 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 | // 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 | // 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 | // segments. So we can simply layout segments one after the other accounting | ||||
| // for alignment. | // for alignment. | ||||
| for (auto &Segment : Segments) { | for (auto &Segment : Segments) { | ||||
| // We assume that segments have been ordered by OriginalOffset and Index | // We assume that segments have been ordered by OriginalOffset and Index | ||||
| // such that a parent segment will always come before a child segment in | // such that a parent segment will always come before a child segment in | ||||
| // OrderedSegments. This means that the Offset of the ParentSegment should | // OrderedSegments. This means that the Offset of the ParentSegment should | ||||
Not Done ReplyInline ActionsUnfortunately 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 jakehehrlich: Unfortunately the lowest PAddr will not necessarily come from the Segment with the lowest… | |||||
| // already be set and we can set our offset relative to it. | // already be set and we can set our offset relative to it. | ||||
| if (Segment->ParentSegment != nullptr) { | if (Segment->ParentSegment != nullptr) { | ||||
| auto Parent = Segment->ParentSegment; | auto Parent = Segment->ParentSegment; | ||||
| Segment->Offset = | Segment->Offset = | ||||
| Parent->Offset + Segment->OriginalOffset - Parent->OriginalOffset; | Parent->Offset + Segment->OriginalOffset - Parent->OriginalOffset; | ||||
| } else { | } else { | ||||
| Offset = alignToAddr(Offset, Segment->VAddr, Segment->Align); | Offset = alignToAddr(Offset, Segment->VAddr, Segment->Align); | ||||
| Segment->Offset = Offset; | Segment->Offset = Offset; | ||||
| ▲ Show 20 Lines • Show All 128 Lines • ▼ Show 20 Lines | template <class ELFT> void BinaryObject<ELFT>::finalize() { | ||||
| // that will affect layout of allocated sections so we only add those. | // that will affect layout of allocated sections so we only add those. | ||||
| std::vector<Segment *> OrderedSegments; | std::vector<Segment *> OrderedSegments; | ||||
| for (auto &Section : this->Sections) { | for (auto &Section : this->Sections) { | ||||
| if ((Section->Flags & SHF_ALLOC) != 0 && | if ((Section->Flags & SHF_ALLOC) != 0 && | ||||
| Section->ParentSegment != nullptr) { | Section->ParentSegment != nullptr) { | ||||
| OrderedSegments.push_back(Section->ParentSegment); | OrderedSegments.push_back(Section->ParentSegment); | ||||
| } | } | ||||
| } | } | ||||
| OrderSegments(OrderedSegments); | |||||
| // For binary output, we're going to use physical addresses instead of | |||||
| // virtual addresses, since a binary output is used for cases like ROM | |||||
| // loading and physical addresses are intended for ROM loading. | |||||
Not Done ReplyInline ActionsNit: rom should be capitalized, i.e. ROM, since it's an abbreviation. jhenderson: Nit: rom should be capitalized, i.e. ROM, since it's an abbreviation. | |||||
| // However, if no segment has a physical address, we'll fallback to using | |||||
| // virtual addresses for all. | |||||
| if (std::all_of(std::begin(OrderedSegments), std::end(OrderedSegments), | |||||
| [](const Segment *Segment) { | |||||
| return Segment->PAddr == 0; | |||||
| })) | |||||
| for (const auto &Segment: OrderedSegments) | |||||
| Segment->PAddr = Segment->VAddr; | |||||
| std::stable_sort(std::begin(OrderedSegments), std::end(OrderedSegments), | |||||
| compareSegmentsByPAddr); | |||||
Not Done ReplyInline ActionsFor 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. jakehehrlich: For the std::unique call to work below identical pointers need to be next to each other so this… | |||||
| // Because we add a ParentSegment for each section we might have duplicate | // Because we add a ParentSegment for each section we might have duplicate | ||||
| // segments in OrderedSegments. If there were duplicates then LayoutSegments | // segments in OrderedSegments. If there were duplicates then LayoutSegments | ||||
| // would do very strange things. | // would do very strange things. | ||||
| auto End = | auto End = | ||||
| std::unique(std::begin(OrderedSegments), std::end(OrderedSegments)); | std::unique(std::begin(OrderedSegments), std::end(OrderedSegments)); | ||||
| OrderedSegments.erase(End, 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 | // 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 | // our layout algorithm to proceed as expected while not out writing out the | ||||
| // gap at the start. | // gap at the start. | ||||
| if (!OrderedSegments.empty()) { | if (!OrderedSegments.empty()) { | ||||
| auto Seg = OrderedSegments[0]; | auto Seg = OrderedSegments[0]; | ||||
Not Done ReplyInline ActionsCan we use std::find_if and a lambda here instead? jakehehrlich: Can we use std::find_if and a lambda here instead? | |||||
Not Done ReplyInline ActionsBetter yet, we can use std::any_of here, to remove the need for the std::end check. jhenderson: Better yet, we can use std::any_of here, to remove the need for the std::end check. | |||||
| auto Sec = Seg->firstSection(); | auto Sec = Seg->firstSection(); | ||||
| auto Diff = Sec->OriginalOffset - Seg->OriginalOffset; | auto Diff = Sec->OriginalOffset - Seg->OriginalOffset; | ||||
| Seg->OriginalOffset += Diff; | Seg->OriginalOffset += Diff; | ||||
| // The size needs to be shrunk as well | // The size needs to be shrunk as well | ||||
| Seg->FileSize -= Diff; | Seg->FileSize -= Diff; | ||||
| Seg->MemSize -= Diff; | // The PAddr needs to be increased to remove the gap | ||||
Not Done ReplyInline ActionsThe VAddr needs -> The VAddr and PAddr need jhenderson: The VAddr needs -> The VAddr and PAddr need | |||||
Not Done ReplyInline ActionsDo 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. jhenderson: Do you need to adjust VAddr any more? As far as I can see, it isn't used at all after PAddr has… | |||||
Not Done ReplyInline ActionsActually yeah, I should have caught this. Following that logic there was never really a reason to update MemSize either. jakehehrlich: Actually yeah, I should have caught this. Following that logic there was never really a reason… | |||||
jhendersonUnsubmitted Not Done ReplyInline ActionsNit: 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." jhenderson: Nit: full stop at end of comment.
Also, what gap? I assume you mean the gap at the start of… | |||||
| // The VAddr needs to be adjusted so that the alignment is correct as well | Seg->PAddr += Diff; | ||||
| Seg->VAddr += Diff; | uint64_t LowestPAddr = Seg->PAddr; | ||||
| Seg->PAddr = Seg->VAddr; | for (auto &Segment : OrderedSegments) { | ||||
| // We don't want this to be shifted by alignment so we need to set the | Segment->Offset = Segment->PAddr - LowestPAddr; | ||||
Not Done ReplyInline ActionsJust want to check, but are NOBITS sections allocated space on disk for binary output? I assume not, but thought it best to double check... jhenderson: Just want to check, but are NOBITS sections allocated space on disk for binary output? I assume… | |||||
Not Done ReplyInline ActionsIf 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: If they're inside a segment and not at the end of the file then space is allocated to them. If… | |||||
| // alignment to zero. | Offset = std::max(Offset, Segment->Offset + Segment->FileSize); | ||||
| Seg->Align = 0; | } | ||||
Not Done ReplyInline ActionsI think this block can be removed now, since we don't align segments at all for binary output. jhenderson: I think this block can be removed now, since we don't align segments at all for binary output. | |||||
| } | } | ||||
| uint64_t Offset = LayoutSegments(OrderedSegments, 0); | |||||
| // TODO: generalize LayoutSections to take a range. Pass a special range | // TODO: generalize LayoutSections to take a range. Pass a special range | ||||
Not Done ReplyInline ActionsI think you should inline the new algorithm for binary segment layout here and LayoutSegments can just be for ELF file layout. jakehehrlich: I think you should inline the new algorithm for binary segment layout here and LayoutSegments… | |||||
| // constructed from an iterator that skips values for which a predicate does | // constructed from an iterator that skips values for which a predicate does | ||||
| // not hold. Then pass such a range to LayoutSections instead of constructing | // not hold. Then pass such a range to LayoutSections instead of constructing | ||||
| // AllocatedSections here. | // AllocatedSections here. | ||||
| std::vector<SectionBase *> AllocatedSections; | std::vector<SectionBase *> AllocatedSections; | ||||
| for (auto &Section : this->Sections) { | for (auto &Section : this->Sections) { | ||||
| if ((Section->Flags & SHF_ALLOC) == 0) | if ((Section->Flags & SHF_ALLOC) == 0) | ||||
| continue; | continue; | ||||
| AllocatedSections.push_back(Section.get()); | AllocatedSections.push_back(Section.get()); | ||||
| Show All 32 Lines | |||||
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.