Page MenuHomePhabricator

Linker script handing of file patterns with COMMON defs
ClosedPublic

Authored by dmikulin on Sep 5 2017, 12:38 PM.

Details

Summary

Currently lld creates a single section to collect all commons. There is no way to separate commons based on file name patterns. The following linker script construct does not work because commons are allocated before section placement is done and the only synthesized BssSection that holds all commons has no file associated with it:
SECTIONS { .common_0 : { *file0.o(COMMON) }}

The idea here is to create a common section for each set of commons matching a COMMON file pattern in the linker script. Each section will have a file name of one of the member symbols attached to it so that subsequent processing of SECTION commands can match against it and place it into an appropriate output section.

Diff Detail

Repository
rL LLVM

Event Timeline

dmikulin created this revision.Sep 5 2017, 12:38 PM
ruiu edited edge metadata.Sep 5 2017, 2:28 PM

Perhaps a more straightforward (though inefficient) way of doing it is to create a Common section for each symbol instead of trying to group them from beginning. It might be too inefficient, but I think it's worth a try.

lld/ELF/LinkerScript.cpp
331 ↗(On Diff #113877)

I don't remember why you can't discard common sections. If it works without this piece of code, can you just remove the code?

My initial thought was to create a section for each common, but I immediately discarded it as too inefficient. Also, it would complicate sorting commons according to their alignment requirements (as it's currently done).

lld/ELF/LinkerScript.cpp
331 ↗(On Diff #113877)

There's a test which specifically checks for attempts to discard COMMONs. Other than that, the rest of them pass with no issues. I can fix the test and remove the code that checks for common sections.

ruiu added a comment.Sep 5 2017, 3:15 PM

Did you try the naive-but-possibly-inefficient algorithm? It may or may not work, but I wouldn't turn it down unless it is shown to be too inefficient.

As to sorting, I think finding sequences of Common sections and sorting them isn't too hard.

Intuitively it didn't seem like the right thing to do. Why do you think it's worth pursuing?
I've just made the change to allocate a section per common (without sorting) and it kind of works, failing some tests due to lack of sorting.
Is there a good real-life benchmark with lots of commons to quantify the efficiency? Or a generated synthetic test case good enough?

ruiu added a comment.Sep 5 2017, 4:16 PM

I don't think it is intuitively a wrong approach. One advantage of the approach is that it eliminates dependency to linker scripts when creating Common sections as it'll instantiate all Common sections without knowing anything about linker scripts. As a benchmark, I'd first try to link Clang with/without a patch to see if there's a measurable difference.

Linking clang takes less than a second and link time is dominated by processing of things other than commons. If there is a difference, it's not very significant in the overall link time.
Linking a synthetic test with 100K commons almost doubles user time when section-per-common is used.

ruiu added a comment.Sep 5 2017, 6:02 PM

What if you build LLVM/clang with debug info? (I don't think that makes a difference, but it would make link time longer from <1 seconds to ~10 seconds.)

I think debug link will mask processing of commons even more, as the number of commons is more or less the same, but link time is dominated by processing debug info.
The synthetic test case confirms the inefficiency of allocating a section per common. The question is: can we tolerate the inefficiency?

dmikulin updated this revision to Diff 114069.Sep 6 2017, 2:05 PM

Changed the implementation to allocate a common section for each common symbol.
Per Rui's comment, removed a check for common sections in LinkerScript::discard() to allow discarding them.

A couple of data points:

  • linking a synthetic test with 100K commons takes ~0.550secs of user time vs ~0.325secs with grouping symbols.
  • memory consumption goes up by ~16M,
  • linking clang shows no measurable difference between the two allocation schemes.
ruiu added a comment.Sep 7 2017, 2:54 PM

When I link clang, lld doesn't actually create any Common section because no input file has common symbols. I haven't thought about that until now, but that makes sense -- I personally don't write code that depends on common symbols too. Maybe common symbols are not that common these days as people have been trained to add extern to global varaible declarations.

We are sorting common symbols because it is believed to pack common symbols well. But we didn't verify that when we add that code to lld. It's a copy of GNU linker's behavior. Maybe we should stop doing that.

Are there Fortran FEs to LLVM? Might still be fairly common there.
If it doesn't cost much, keeping the sorting doesn't hurt, may save us a few alignment holes. Most of the cost is from section per common, not from sorting.

ruiu added a comment.Sep 7 2017, 3:18 PM

Our philosophy of re-implementing a linker is to not copy features without verifying that doing that makes sense. So I think we shouldn't have sorted common symbols in the first place. We can bring it back when it is proved to be useful, but until then, I think I prefer removing the code to sort common symbols.

dmikulin updated this revision to Diff 114273.Sep 7 2017, 3:59 PM

Now without sorting the commons by alignment.

ruiu added inline comments.Sep 7 2017, 4:35 PM
lld/ELF/Symbols.h
177 ↗(On Diff #114273)
Section = nullptr
lld/ELF/SyntheticSections.cpp
57–58 ↗(On Diff #114273)

clang-format

59 ↗(On Diff #114273)

By convention, Ret is preferred over SV. In general, I found that giving the same name to a variable regardless of its type is more readable than naming it based on type. So, I prefer naming a symbol (whether it is defined or not) Sym instead of DC or something like that.

64 ↗(On Diff #114273)

So, let's name this Sym

lld/ELF/SyntheticSections.h
757 ↗(On Diff #114273)

I think you can now remove this member.

dmikulin updated this revision to Diff 114287.Sep 7 2017, 4:58 PM
dmikulin marked 6 inline comments as done.

Addressed latest comments.

ruiu accepted this revision.Sep 7 2017, 5:07 PM

LGTM with these changes.

lld/ELF/SyntheticSections.cpp
58–60 ↗(On Diff #114287)

I believe this is slightly more readable.

if (!Config->DefineCommon)
  return {};

std::vector<InputSection *> Ret;
for (Symbol *S : ...) {
lld/ELF/Writer.cpp
305–306 ↗(On Diff #114287)

In lld, we don't use auto unless it is obvious in a very local context (typically RHS). This is not the case.

for (InputSection *S : createCommonSections())
  add(S)
This revision is now accepted and ready to land.Sep 7 2017, 5:07 PM
This revision was automatically updated to reflect the committed changes.

Hi Dmitry, Ruiu - this change breaks lld for references to garbage collected common symbols.

Could you please take a look at: https://reviews.llvm.org/D37718.