This is an archive of the discontinued LLVM Phabricator instance.

[ELF] - Linkerscript: implemented simple heuristic for placing orphan sections.
AbandonedPublic

Authored by grimar on Aug 10 2016, 8:03 AM.

Details

Reviewers
ruiu
rafael
Summary

Previously we put orphans to the end. Patch implements simple heuristic instead.
Each orphan is placed after the last section in sequence with the same access
attributes.

Testcase is provided to show the behavior.
Currently it looks the same or very close to what ld do.

Diff Detail

Event Timeline

grimar updated this revision to Diff 67522.Aug 10 2016, 8:03 AM
grimar retitled this revision from to [ELF] - Linkerscript: implemented simple heuristic for placing orphan sections..
grimar updated this object.
grimar added a reviewer: ruiu.
grimar added subscribers: llvm-commits, grimar, evgeny777, davide.
ruiu edited edge metadata.Aug 10 2016, 6:26 PM

What's the motivation behind it? I think our general stance to the user is "if you don't like our orphan section layout, you need to specify precise layout yourself."

grimar added a comment.EditedAug 11 2016, 1:37 AM
In D23352#512203, @ruiu wrote:

What's the motivation behind it? I think our general stance to the user is "if you don't like our orphan section layout, you need to specify precise layout yourself."

I think that was that before. But as Davide mentioned "If FreeBSD can change his linker script, fine, great for them. But not everybody has the same luxury."
Basing on that we probably want to implement something very simple and short. This heuristics looks work equal to ld and it is just a single method, probably
it can meet the needs of users well.

I also think we can implement a warning, saying there are orphan sections found to force users to update their scripts in a soft way.

I think, the motivation is that listing all sections in linker script is not always a good idea. For example we have about dozen of linker scripts and more than hundred of projects which are linked using those scripts, so that single script is shared between several projects. The set of sections from project to project might be different, so without any heuristic I have to investigate all of them and modify scripts to cover all possible layouts. Needless to say, that serious amount of work may be required, so if heuristic can be implemented with a dozen lines of code then I'd like to have it as well.

grimar updated this revision to Diff 67672.Aug 11 2016, 4:05 AM
grimar edited edge metadata.
  • Rebased.
evgeny777 added inline comments.Aug 11 2016, 4:14 AM
ELF/LinkerScript.cpp
62

I suggest not using Current here, because it is not needed outside of addOrphan. Let's minimize side effects:

OutputSectionBase<ELFT> *Orphan;
bool IsNew;
std::tie(Orphan, IsNew) = Facrory.Create(...);
// ...
grimar updated this revision to Diff 67684.Aug 11 2016, 6:57 AM
  • Addressed review comments
  • Cosmetic changes
grimar added inline comments.Aug 11 2016, 6:59 AM
ELF/LinkerScript.cpp
62

Sounds reasonable.

ruiu added a comment.Aug 11 2016, 2:19 PM

I imagine that if you want to implement a logic for orphan sections, you want to implement the same rule for the non-linker-script case. I'ts hard to review because there are many patches on the fly. I'm wondering how this change will relate to https://reviews.llvm.org/D23315.

In D23352#513092, @ruiu wrote:

I imagine that if you want to implement a logic for orphan sections, you want to implement the same rule for the non-linker-script case. I'ts hard to review because there are many patches on the fly. I'm wondering how this change will relate to https://reviews.llvm.org/D23315.

Sorry, but I don't understand the idea I think. Why we would want to implement the same rule as we have for non-script case ?
In non-script case there is no oprhans, sections just grouped together by attributes. When script is present, sections should be placed
in a order specified by script. That violates the non-scripted rule.
This patch places orphans to be in group with the sections with the same attributes. So here it is close to what non-scripted case do.
The only difference that script has a priority against any other rules and that is what expected I think.

I guess D23315 is no more actual, I am going to rebase and update this one soon.

grimar updated this revision to Diff 67818.Aug 12 2016, 4:02 AM
  • Rebased.

By the way with this change orphans section order in kernel is almost the same as ld does:
lld output:

Segment Sections...
 00     
 01     .interp 
 02     .interp .hash .dynsym .dynstr 
 03     .text 
 04     .rodata set_sysctl_set set_sysinit_set set_sysuninit_set set_modmetadata_set set_ah_chips set_ah_rfs set_kbddriver_set set_cons_set usb_host_id set_vt_drv_set set_sdt_providers_set set_sdt_probes_set set_sdt_argtypes_set set_kdb_dbbe_set set_ratectl_set set_crypto_set set_ieee80211_ioctl_getset set_ieee80211_ioctl_setset set_scanner_set set_videodriver_set set_scterm_set set_scrndr_set set_vga_set kern_conf .eh_frame 
 05     .dynamic .data .bss set_pcpu 
 06     .dynamic 
 07     .dynamic 
 08

ld output:

Segment Sections...
 00     
 01     .interp 
 02     .interp .hash .dynsym .dynstr .text .rodata set_sysctl_set set_sysinit_set set_sysuninit_set set_modmetadata_set set_ah_chips set_ah_rfs set_kbddriver_set set_cons_set usb_host_id set_vt_drv_set set_sdt_providers_set set_sdt_probes_set set_sdt_argtypes_set set_kdb_dbbe_set set_ratectl_set set_crypto_set set_ieee80211_ioctl_getset set_ieee80211_ioctl_setset set_scanner_set set_videodriver_set set_scterm_set set_scrndr_set set_vga_set kern_conf .eh_frame 
 03     .dynamic .got.plt .data set_pcpu .bss 
 04     .dynamic 
 05

Difference is that ld creates less segments, but that is unrelative to this patch.

ruiu added inline comments.Aug 12 2016, 2:47 PM
ELF/LinkerScript.cpp
212

Let's name this getPermissions as this is RWX permissions.

225

Orphan sections are a concept of input sections. I don't think we call output sections containing orphan sections as orphan sections. So let's name this OutSec.

231

Why do you have to use rbegin and rend?

236–252

This code is hard to understand. In short, what are you trying to do in this function?

grimar added inline comments.Aug 15 2016, 12:02 AM
ELF/LinkerScript.cpp
231

I am searching the last section with the same access attributes to place orphan right after. So I had to search from the end to start.

I`ve added notes for each piece of code below.

234
  1. At first I search the last section with the attributes equal to atributes of orphan I am inserting.
241
  1. If there is no section with the same attributes - I just add orphan to the end, also I create and add output section command either to the end.
244
  1. I add orphan to the position I found above and take the name of the section which goes before the orphan. This name is required to find the proper position for new OutputSectionCommand.
252

Please see new notes above. That piece is:

  1. Find the proper place for new OutputSectionCommand and add it. This position matches the position of orphan section added:

OutputSections content: Sec1 Sec2 Oprhan Sec4
ScriptConfig->Commands content: Cmd_Sec1 Cmd_Sec2 Cmd_Orphan Cmd_Sec4

grimar updated this revision to Diff 68034.Aug 15 2016, 6:59 AM
  • Addressed review comments.
ELF/LinkerScript.cpp
212

Done.

225

Done.

ruiu added inline comments.Aug 15 2016, 3:22 PM
ELF/LinkerScript.cpp
90

I think I understand what you are trying to do, but still it seems a bit too complicated. Isn't there any way to simplify?

silvas added a subscriber: silvas.Aug 15 2016, 9:04 PM

Thanks for working on this George, this is really helpful for building the FreeBSD kernel. One comment inline.

FYI, Michael and I are also debugging why the bootloader doesn't like LLD produced binaries. Besides the issue addressed by this patch, so far we have identified two other issues (there are more, but these are the ones we've identified so far):

  • __start_SECNAME/__stop_SECNAME are not exported in the dynamic symbol table. This is needed for the loader which looks up __start_set_modmetadata_set/__stop_set_modmetadata_set.
  • LLD does not honor MAXPAGESIZE (needs to be 2M for amd64), this causes the kernel load address to get set far too low (at 4K, close to where the loader lives), which clobbers the loader's text / data structures when copying in the kernel :)

Hopefully it saves you some time!

ELF/LinkerScript.cpp
70

I think this also needs to check && !(S->getType() & SHT_NOBITS) so that we don't add a PROGBITS section into BSS.

E.g. with this patch applied I get this error during a FreeBSD kernel build:

BFD: stc5VrZP: section set_pcpu lma 0xffffffff81529d80 overlaps previous sections
BFD: stc5VrZP: section `set_pcpu' can't be allocated in segment 5
objcopy: stc5VrZP: Bad value
BFD: stc5VrZP: section set_pcpu lma 0xffffffff81529d80 overlaps previous sections
BFD: stc5VrZP: section `set_pcpu' can't be allocated in segment 5
objcopy: stc5VrZP: Bad value
*** Error code 1

Relevant section of readelf --sections output on the binary produced by this patch:

[33] .data             PROGBITS         ffffffff81401000  01015000
     000000000012823c  0000000000000000  WA       0     0     32
[34] .bss              NOBITS           ffffffff81529280  0113d23c
     0000000000207ad0  0000000000000000  WA       0     0     128
[35] set_pcpu          PROGBITS         ffffffff81730d80  0113dd80
     00000000000010b0  0000000000000000  WA       0     0     128
  • __start_SECNAME/__stop_SECNAME are not exported in the dynamic symbol table. This is needed for the loader which looks up __start_set_modmetadata_set/__stop_set_modmetadata_set.
  • LLD does not honor MAXPAGESIZE (needs to be 2M for amd64), this causes the kernel load address to get set far too low (at 4K, close to where the loader lives), which clobbers the loader's text / data structures when copying in the kernel :)

Hopefully it saves you some time!

I`ll take a look on these, thanks a lot for this info !

grimar updated this revision to Diff 68151.Aug 16 2016, 3:15 AM
  • Addressed review comments.
grimar added inline comments.Aug 16 2016, 3:22 AM
ELF/LinkerScript.cpp
70

Done, thanks !

90

I refactored that.
Though there are probably not much space to simplify since
I need to insert different things into two different async lists.

  • LLD does not honor MAXPAGESIZE (needs to be 2M for amd64), this causes the kernel load address to get set far too low (at 4K, close to where the loader lives), which clobbers the loader's text / data structures when copying in the kernel :)

So I wonder do we want implement -z max-page-size (D19600, this will require adding that option to FreeBSD cmd line I think)
or change X86_64TargetInfo::PageSize to handle this ?

grimar updated this revision to Diff 68530.Aug 18 2016, 6:37 AM
  • Rebased.
  • Added more comments.
ruiu added inline comments.Aug 18 2016, 1:12 PM
ELF/LinkerScript.cpp
90

I think the complexity comes from the very fact that you need to insert new commands into existing commands to keep two parallel arrays consistent. Parallel arrays are easy to create when you create one array from the other, but parallel arrays are not suitable for modification because you need to keep them consistent when you remove or add new elements. If you can do this without a parallel array, it would be easier to understand than this. (I'm not sure if it's doable, but I believe it's worth trying.)

grimar updated this revision to Diff 68671.Aug 19 2016, 5:00 AM
  • Addressed review comment.
ELF/LinkerScript.cpp
90

Ok, that makes sense. What about updated variant ? (I had to use void* because output command is not template class, but change affects only one local method so I think that should not be a problem).

ruiu added inline comments.Aug 19 2016, 9:31 AM
ELF/LinkerScript.cpp
69

That's what you are doing, but why do you have to do that?

94

What I meant by "parallel array", I meant ScriptConfig->Commands and OutputSections. You are inserting new elements as you create new output sections, so you are still maintaining them as a parallel array. Is this intended?

grimar added inline comments.Aug 19 2016, 2:49 PM
ELF/LinkerScript.cpp
69

That is just a variant of possible heuristic.
That works for orphans in freebsd script and probably will work for other scripts.
Attemp to group sections together by attributes seems reasonable.
Do you think about some different algorithm ?

94

Yes, intended, but approach was changed:
I am creating the elements of ScriptConfig->Commands at first. And then at the end of createSections() construct OutputSections entries from ScriptConfig->Commands. So I do not need to mantain both arrays at the same time during sections creation and processing orphans anymore. Was not that the point ?

ruiu added a comment.Aug 29 2016, 3:53 PM

Please ping me again once D23866 has landed.

ruiu added inline comments.Aug 29 2016, 4:09 PM
ELF/LinkerScript.cpp
77

Why rbegin and rend? If it doesn't have to be rbegin/rend, use begin/end.

89

What is base()?

In D23352#528358, @ruiu wrote:

Please ping me again once D23866 has landed.

It seems that it will never be landed. If we decide to go with multiple output sections solution so support SHT_MERGE,
there is no more point to do D23866.
So this patch is still uses Factory, what is looks what we want.

ELF/LinkerScript.cpp
77

I am searching the last section with the same access attributes to place orphan right after. So I had to search from the end to start.

89

base() converts reverse iterator to regular:
http://en.cppreference.com/w/cpp/iterator/reverse_iterator/base

grimar updated this revision to Diff 70331.Sep 5 2016, 7:44 AM
  • Rebased.
emaste added a subscriber: emaste.Sep 8 2016, 7:38 AM

While attempting to apply the patch locally for testing I encountered line ending issues and two conflicts marked above.

ELF/LinkerScript.cpp
294

patch failed to apply for me with a conflict here

test/ELF/linkerscript/symbols-synthetic.s
53–65

conflict here

grimar added inline comments.Sep 8 2016, 8:24 AM
ELF/LinkerScript.cpp
294

Yes, it is already outdated. I`ll rebase it soon.

While attempting to apply the patch locally for testing I encountered line ending issues and two conflicts marked above.

Sorry, Ed. I think I want to spend more time before updating this patch. After change we had about we can have multiple output sections fot single description I do not like the result after just rebasing this. It was not ideal before, but now it is even more complicated, I am going to rework it and unfortunately have no good ideas right now.

grimar updated this revision to Diff 71734.Sep 17 2016, 10:08 AM
  • Rebased/reimplemented. Latest changes in lld (r281778) allowed to simplify this patch a lot.
grimar updated this revision to Diff 71736.Sep 17 2016, 10:15 AM
  • Updated comment.
grimar abandoned this revision.Sep 22 2016, 8:21 AM

Patch was about placing orphans right after the other sections with the same attributes instead of placing them to the end.
As far I understand, that is already solved with use sorting in latest changes.
And as I mentioned in llvm discussion, this patch does not do something new here for orphans, so I am abandoning it.